第2章k-近邻算法(kNN)引言本章介绍kNN算法的基本理论以及如何使用距离测量的方法分类物品。
其次，将使用python从文本文件中导入并解析数据，然后，当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见的错识。
2.1 k-近邻算法概述k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类。
它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。
一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。
最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。
适用于数值和离散型数据。
2.1.1 准备知识：使用python导入数据首先，创建名为kNN.py的python模块，然后添加下面代码：from numpy import * #引入科学计算包import operator #经典python函数库。
运算符模块。
#创建数据集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测试：>>> import kNN>>> group,labels=kNN.createDataSet()注意：要将kNN.py文件放到Python27文件夹下，否则提示找不到文件。
2.2.2 实施kNN算法使用k-近邻算法将每组数据划分到某个类中，其伪代码如下：对未知类别属性的数据集中的每个点依次执行以下操作：1.计算已知类别数据集中的点与当前点之间的距离；2.按照距离递增交序排序；3.选取与当前点距离最小的k个点；4.确定前k个点所在类别的出现频率；5.返回前k个点出现频率最高的类别作为当前点的预测分类。
用欧氏距离公式，计算两个向量点xA和xB之间的距离：例如，点(0, 0)与(1, 2)之间的距离计算为:python函数classify()程序如下所示：#算法核心#inX：用于分类的输入向量。
即将对其进行分类。
#dataSet：训练样本集#labels:标签向量def classfy0(inX,dataSet,labels,k):#距离计算#得到数组的行数。
即知道有几个训练数据dataSetSize =dataSet.shape[0]#用欧氏距离公式计算距离diffMat =tile(inX,(dataSetSize,1))-dataSet #将inX扩展为4行2列的向量，两个矩阵相减sqDiffMat =diffMat**2 #平方sqDistances =sqDiffMat.sum(axis=1) #asis=1是按行相加distances =sqDistances**0.5 #开方sortedDistIndicies=distances.argsort() #升序排列#选择距离最小的k个点。
classCount={}for i in range(k):voteIlabel=labels[sortedDistIndicies[i]]classCount[voteIlabel]=classCount.get(voteIlabel,0)+1#排序，降序sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),revers e=True)return sortedClassCount[0][0]测试:>>>kNN .classify0([0,0],group, labels,3)2.2示例：使用k-近邻算法改进约会网站的配对结果在约会网站上使用k-近邻算法的步骤：1.收集数据：提供文本文件。
2.准备数据：使用python解析文本文件。
3.分析数据：使用Matplotlib画二维扩散图。
4.训练算法：此步骤不适用于k-近邻算法。
5.测试算法：使用部分数据作为测试样本。
测试样本与非测试样本的区别在于：测试样本是已经完成分类的数据，如果预没分类与实际类别不同，则标记为一个error.6.使用算法：产生简单的命令行程序，然后可以输入一些特征数据以判断对方是否为自己喜欢的类型。
2.2.1准备数据：从文本文件中解析数据将数据存放到文本文件，每一个样本数据占据一行。
首先，必须将特处理数据改变为分类器可以接受的格式。
在kNN.py中创建file2matrix的函数，以此来处理输入格式问题。
将文本记录转换为NumPy的解析程序如下所示：def file2matrix(filename):# 打开训练集文件fr = open(filename)# 获取文件行数，即训练集的样本个数numberOfLines = len(fr.readlines())# 初始化特征矩阵returnMat = zeros((numberOfLines,3))# 初始化标签向量classLabelVector = []# 特征矩阵的行号也即样本序号index = 0# 遍历训练集文件中的所有行for line in fr.readlines():# 去掉行头行尾的换行符，制表符。
line = line.strip()# 以制表符分割行listFromLine = line.split('\t')# 将该行特征部分数据存入特征矩阵returnMat[index,:] = listFromLine[0:3]# 将该行标签部分数据存入标签矩阵classLabelVector.append(int(listFromLine[-1]))# 样本序号+1index += 1#返回训练样本矩阵和类标签向量。
return returnMat,classLabelVector测试：>>>reload(kNN)>>>datingDataMat,datingLabels=kNN.file2matrix('datingTestSe t2.txt')注意：文件中不要包含字符串，否则运行会出错。
2.2.2分析数据：使用Matplotlib创建散点图首先我们使用Matplotlib制作原始数据的散点图.如下程序所示：import matplotlibimport matplotlib.pyplot as plt# 新建一个图对象fig = plt.figure()# 设置1行1列个图区域，并选择其中的第1个区域展示数据。
ax = fig.add_subplot(111)# 以训练集第一列(玩网游所消耗的时间比)为数据分析图的行，第二列(每年消费的冰淇淋公升数)为数据分析图的列。
ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0*numpy.array(datingLabels), 15.0*numpy.array(datingLabels))# 坐标轴定界ax.axis([-2,25,-0.2,2.0])# 坐标轴说明(matplotlib配置中文显示有点麻烦这里直接用英文的好了)plt.xlabel('Percentage of Time Spent Playing Online Games')1plt.ylabel('Liters of Ice Cream Consumed Per Week')# 展示数据分析图plt.show()2.2.3 准备数据：归一化数值我们分析的这三个特征，在距离计算公式中所占的权重是不同的：飞机历程肯定要比吃冰淇淋的公升数大多了。
因此，需要将它们转为同样的一个数量区间，再进行距离计算。
--- 这个步骤就叫做数据归一化。
可以使用如下公式对数据进行归一化：newValue = (oldValue - min) / (max - min)即用旧的特征值去减它取到的最小的值，然后再除以它的取值范围。
很显然，所有得到的新值取值均在0 -1 。
这部分代码如下：def autoNorm(dataSet):# 获得每列最小值minVals = dataSet.min(0)# 获得每列最大值maxVals = dataSet.max(0)# 获得每列特征的取值范围ranges = maxVals - minVals# 构建初始矩阵(模型同dataSet)normDataSet = numpy.zeros(numpy.shape(dataSet))# 数据归一化矩阵运算m = dataSet.shape[0]normDataSet = dataSet - numpy.tile(minVals, (m,1))# 注意/是特征值相除法。
/在别的函数库也许是矩阵除法的意思。
normDataSet = normDataSet/numpy.tile(ranges, (m,1))return normDataSet第四步：测试算法测试的策略是随机取10%的数据进行分析，再判断分类准确率如何。
第五步：使用算法构建完整可用系统运行结果：至此，该系统编写完毕。
2.3 示例：手写识别系统编程实现，大概分为三个步骤：（1）将每个图片（即txt文本，以下提到图片都指txt文本）转化为一个向量，即32*32的向量转化为1*1024的特征向量。
（2）训练样本中有10*10个图片，可以合并成一个100*1024的矩阵，每一行对应一个图片。
（这是为了方便计算，很多机器学习算法在计算的时候采用矩阵运算，可以简化代码，有时还可以减少计算复杂度）。
（3）测试样本中有10*5个图片，我们要让程序自动判断每个图片所表示的数字。
同样的，对于测试图片，将其转化为1*1024的向量，然后计算它与训练样本中各个图片的“距离”（这里两个向量的距离采用欧式距离），然后对距离排序，选出较小的前k个，因为这k个样本来自训练集，是已知其代表的数字的，所以被测试图片所代表的数字就可以确定为这k个中出现次数最多的那个数字。
除了书上的代码以外自己需要加的图像处理部分：#将图像转换成0和1的像素点def compress(img, h1, h2, w1, w2):for h in range(h1, h2):for w in range(w1, w2):pixel = img.getpixel((w,h))if pixel[0] == 0:return1return0#将数字以像素点32*32的向量的形式取出来def getRange(img):imgSize = img.sizehMax = 0hMin = imgSize[1]wMax = 0wMin = imgSize[0]for h in range(imgSize[1]):for w in range(imgSize[0]):if img.getpixel((w, h))[0] == 0:if w > wMax:wMax = wif w < wMin:wMin = wif h > hMax:hMax = hif h < hMin:hMin = hwRange = wMax - wMinhRange = hMax - hMinwMin = wMin - wRange/6wMax = wMax + wRange/6hMin = hMin - hRange/6hMax = hMax + hRange/6if wMin < 0:wMin = 0if wMax > imgSize[0]:wMax = imgSize[0]if hMin < 0:hMin = 0if hMax > imgSize[1]:hMax = imgSize[1]return (hMin, hMax, wMin, wMax)#将像素点转化成图像的形式存储def image2File(imagePath, filePath):img = Image.open(imagePath, 'r')(hMin, hMax, wMin, wMax) = getRange(img)wArray = linspace(wMin, wMax, 33)hArray = linspace(hMin, hMax, 33)wList = [int(x) for x in wArray]hList = [int(x) for x in hArray]fw = open(filePath,'w')for h in range(32):for w in range(32):number = compress(img, hList[h], hList[h+1]+1, wList[w], wList[w+1]+1)fw.write(str(number))fw.write('\n')fw.close()运行结果：2.4小结k-近邻算法是分类数据最简单最有效的算法，本章通过两个例子讲述了如何使用k-近邻算法构造分类器。