ch2_kNN

from numpy import *

import operator

from os import listdir

def createDataSet():

group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

labels = ['A','A','B','B']

return group, labels

'''KNN算法的伪代码

对未知类别属性的数据集中的每个点依次执行以下操作：

(1)计算已知类别数据集中的点与当前点之间的距离

(2)按照距离递增次序排序

(3)选取与当前点距离最小的k个点

(4)确定前k个点所在类别的出现频率

(5)返回前k个点出现频率最高的类别作为当前点的预测分类'''

def classify0(inX, dataSet, labels, k): #默认输入4个参数，inX表示用于分类的输入向量；dataSet为训练样本集；labels为标签向量；k表示用于选择最近邻居的数目

dataSetSize = dataSet.shape[0] #训练样本集的样本个数

diffMat = tile(inX, (dataSetSize,1)) - dataSet #计算距离

sqDiffMat = diffMat ** 2 #欧氏距离法分别计算每个维度差平方

sqDistances = sqDiffMat.sum(axis=1) #横向每个维度的差平方求和

distances = sqDistances ** 0.5 #差平方求和结果开根号求出欧氏距离

sortedDistIndicies = distances.argsort() #将得到的欧氏距离阵列，这种numpyarray从小到大排列，并提取原本的index

classCount = {} #建立分类字典

for i in range(k):

voteIlabel = labels[sortedDistIndicies[i]] #逐次查找最小的index对应的类标签

classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #如果字典classCount中有voteIlabel类则返回该值+1否则返回0+1

sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),reverse=True) #提取classCount中的项，提取其中的值倒叙排列，并返回一个排好的字典

return sortedClassCount[0][0] #返回第一个项的键（数量最大的值对应的键）

'''约会网站上使用k近邻算法，该函数输入为文件名字字符串，输出为训练样本矩阵和类标签向量

(1)收集数据：提供文本文件

(2)准备数据

(3)分析数据：使用matplotlib画二维散点图

(4)训练算法：此步骤不适用于k近邻算法

(5)测试算法

(6)使用算法'''

def file2matrix(filename):

fr = open(filename)

arrayOflines = fr.readlines()

numberOfLines = len(arrayOflines) #得到文件的行数

returnMat = zeros((numberOfLines,3)) #创建返回Numpy的矩阵

classLabelVector = [] #创建文本类标签向量的list

index = 0

for line in arrayOflines: #解析文件数据到列表

line = line.strip() #截取掉所有回车字符

listFromLine = line.split('\t') #使用tab字符(\t)将整行数据截取为元素列表

returnMat[index,:] = listFromLine[0:3] #选取前三个元素储存到特征矩阵中。

classLabelVector.append(int(listFromLine[-1])) #最后一列存储到向量classLabelVector中，处理对象说明为整型否则按字符串处理

index += 1

return returnMat, classLabelVector

'''分析数据使用Matplotlib制作原始数据的散点图

>>>reload(kNN)

>>>datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')

>>>datingDataMat

>>>datingLabels[0:20]

>>>import matplotlib

>>>import matplotlib.pyplot as plt

>>>fig = plt.figure()

>>>ax = fig.add_subplot(111)

>>>ax.scatter(datingDataMat[:,1], datingDataMat[:,2])

>>>plt.show()

'''

'''归一化数值，由于数据取值范围不同，当相同权重时，同种不同组数据若相差影响最终结果过大，会有所偏差，

再次引入归一化数值的方法，将所有数据取值范围变为0-1之间。

计算公式：新的数值=(原始数值-最小值)/(最大值-最小值)'''

def autoNorm(dataSet):

minVals = dataSet.min(0) #将每列数据中最小的数字放入变量minVals。参数(0)表示：在列维度求值，(1)表示在行维度求

maxVals = dataSet.max(0) #同理最大数字放入maxVals

ranges = maxVals - minVals

normDataSet = zeros(shape(dataSet))

m = dataSet.shape[0] #得到数据集中共有多少行数据

normDataSet = dataSet - tile(minVals, (m,1)) #计算公式的分子：数值-最小值

normDataSet = normDataSet/tile(ranges, (m,1)) #计算公式的分母：最大值-最小值

return normDataSet, ranges, minVals

'''在autoNorm函数中，将每列的最小值放到minVals，最大值放到maxVals计算最大最小差值。min(0)中参数0表示，函数可以从列维度

中选取最小值。最后函数返回一个新的矩阵，为归一化结果。

设特征值矩阵1000x3，而minVals和ranges都为1x3，用tile()解决这个问题。'''

#测试算法

def datingClassTest():

hoRatio = 0.10

datingDataMat,datingLabels = file2matrix('datingTestSet.txt')

normMat, ranges, minVals = autoNorm(datingDataMat)

m = normMat.shape[0]

numTestVecs = int(m*hoRatio)

errorCount = 0.0

for i in range(numTestVecs):

classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)

print("The classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))

if (classifierResult != datingLabels[i]):

errorCount += 1.0

print ("The total error rate is : %f" % (errorCount/float(numTestVecs)))

'''使用kNN构造手写数字识别系统。

(1)收集数据：提供文本文件

(2)准备数据：编写函数classify0()， 将图像格式转换为分类器使用的list格式

(3)分析数据：在Python命令提示符中检查数据，确保符合要求

(4)训练算法：

(5)测试算法：使用提供的部分数据集作为测试样本，测试样本与非测试样本区别在于

测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为错误

(6)使用算法：本例没有完成'''

def img2vector(filename): #将图像转化为向量的函数

returnVect = zeros((1,1024)) #初始化一个1x1024的向量

fr = open(filename) #读取文件

for i in range(32): #将32x32的原始图像转化为1x1024的向量

lineStr = fr.readline()

for j in range(32):

returnVect[0,32*i+j] = int(lineStr[j])

return returnVect #返回得到的向量

'''测试算法，使用k-近邻算法识别手写数字，img2vector将数据处理成分类器可以识别的模式，

handwritingClassTest函数是检测分类器执行结果。listdir是os库中的函数，可以列出给定目录的文件名'''

def handwritingClassTest():

hwLabels = [] #hwLabels类型为list用来记录标签

trainingFileList = listdir('trainingDigits') #测试集数据文件名，要作为标签使用

m = len(trainingFileList)

trainingMat = zeros((m,1024)) #初始化矩阵

for i in range(m):

fileNameStr = trainingFileList[i] #遍历所有标签

fileStr = fileNameStr.split('.')[0]

classNumStr = int(fileStr.split('_')[0]) #这两步表示将数据本来类别名从文件名中提取出来

hwLabels.append(classNumStr) #标签集增加

trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr) #得到最终训练结果

testFileList = listdir('testDigits') #测试集文件名开始

errorCount = 0.0 #初始化错误数

mTest = len(testFileList) #得到测试集个数

errorList = {} #用字典记录分类器分类错误的图像及错误结果

for i in range(mTest):

fileNameStr = testFileList[i] #遍历测试集

fileStr = fileNameStr.split('.')[0] #得到测试集标签

classNumStr = int(fileStr.split('_')[0]) #用于验证精度

vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)

classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) #分类器本体

#print("the clasifier came back with : %d, the real answer is: %d" % (classifierResult, classNumStr))

if (classifierResult != classNumStr): #若分类器结果与读取的测试集结果不相等

errorCount += 1.0 #错误数增加1

errorList[fileStr] = classifierResult

print("the total number of error is : %d" % errorCount)

errorRate = errorCount/float(mTest)

print("the total error rate is : %f" % errorRate) #用总错误数/总测试集个数表示精度

print("the error list is :", end = ' ')

print(errorList)