第2章k近邻算法

K-近邻算法（KNN）kNN特点kNN是一种基于向量空间的分类方法该方法非常简单，也容易实现在大多数情况下，kNN的效果比朴素贝叶斯和中心向量法要好如果你急切需要一种精度很高分类器并很快投入运行.....如果你不是特别关注效率......那么就使用kNN工作原理测量不同特征值之间的距离方法进行分类优点：精度高、对异常值不敏感、无数据输入假定缺点：计算复杂度高、空间复杂度高适用数据范围：数值型和标称型计算新数据与样本数据的相似度样本集（有标签的数据集）新数据集选择样本数据集中前k个最相似的数据出现最多的分类作为新数据的分类创建数据集和标签defcreateDataSet():group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])labels=['A','A','B','B']returngroup,labelsK-近邻算法：带有4个数据点的数据集importkNNgroup,labels=kNN.createDataSet()importmatplotlibimportmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(group[:,0],group[:,1])plt.show()kNN算法计算已知类别数据集中的每个点依次执行以下操作：计算已知类别数据集中的点与当前点之间的距离按照距离递增次序排序选取与当前点距离最小的k个点确定前k个点所在类别的出现频率返回前k个点出现频率最高的类别作为当前点的预测分类K-近邻算法defclassify0(inX,dataSet,labels,k):dataSetSize=dataSet.shape[0]diffMat=tile(inX,(dataSetSize,1))-dataSetsqDiffMat=diffMat**2sqDistances=sqDiffMat.sum(axis=1)distances=sqDistances**0.5sortedDistIndicies=distances.argsort()classCount={}foriinrange(k):voteIlabel=labels[sortedDistIndicies[i]]classCount[voteIlabel]=classCount.get(voteIlabel,0)+1sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)returnsortedClassCount[0][0]axis=1是将一个矩阵的每一行向量相加

importnumpyasnpnp.sum([[0,1,2],[2,1,3],axis=1)的结果就是：array（[3,6]）Classify0()中的参数输入参数：inX待分类的输入向量dataSet输入的训练样本集Labels标签向量K用于选择最近邻居的数目计算两个向量点xA和xB之间的欧氏距离一些函数介绍：Tile(A,n)将数组A重复n次，构成一个新的数组如：A=[0,1,2]B=tile(a,2)Barray([0,1,2,0,1,2])Operator.itemgetter函数用于获取对象的哪些维的数据，参数为一些序号，如：a=[1,2,3]B=operator.itemgetter(1)B(a)2B=operator.itemgetter(1,0)B(a)(2,1)Python中sorted（）的用法iterable，中文意思是迭代器iteralbe指的是能够一次返回它的一个成员的对象。iterable主要包括3类：第一类是所有的序列类型，比如list(列表)、str(字符串)、tuple(元组)。第二类是一些非序列类型，比如dict(字典)、file(文件)。第三类是你定义的任何包含__iter__()或__getitem__()方法的类的对象。Sorted用法sorted(iterable[,cmp,[,key[,reverse=True]]])作用：Returnanewsortedlistfromtheitemsiniterable.

第一个参数是一个iterable，返回值是一个对iterable中元素进行排序后的列表(list)。可选的参数有三个，cmp、key和reverse。1)cmp指定一个定制的比较函数，这个函数接收两个参数（iterable的元素），如果第一个参数小于第二个参数，返回一个负数；如果第一个参数等于第二个参数，返回零；如果第一个参数大于第二个参数，返回一个正数。默认值为None。2)key指定一个接收一个参数的函数，这个函数用于从每个元素中提取一个用于比较的关键字。默认值为None。3)reverse是一个布尔值。如果设置为True，列表元素将被倒序排列。通常来说，key和reverse比一个等价的cmp函数处理速度要快。这是因为对于每个列表元素，cmp都会被调用多次，而key和reverse只被调用一次。具体的用法如下：>>>sorted([5,2,3,1,4])[1,2,3,4,5]你也可以使用list的list.sort()方法。这个方法会修改原始的list（返回值为None）。通常这个方法不如sorted()方便-如果你不需要原始的list，list.sort()方法效率会稍微高一些。>>>a=[5,2,3,1,4]>>>a.sort()>>>a[1,2,3,4,5]另一个区别在于list.sort()方法只为list定义。而sorted()函数可以接收任何的iterable。KeyFunctions(关键字函数)>>>sorted("ThisisateststringfromAndrew".split(),key=str.lower)['a','Andrew','from','is','string','test','This']key的值应该是一个函数，这个函数接收一个参数并且返回一个用于比较的关键字。这种技术比较快，原因在于对每个输入记录，这个函数只会被调用一次。对复杂对象的比较通常是使用对象的切片作为关键字。例如：>>>student_tuples=[('john','A',15),('jane','B',12),('dave','B',10),]

>>>sorted(student_tuples,key=lambdastudent:student[2])#sortbyage[('dave','B',10),('jane','B',12),('john','A',15)]调用kNN.createDataSet(),创建数据集作为样本数据,调用kNN.classify0(),对向量[0,0]分类例：使用k-近邻算法改进约会网站的配对效果步骤收集数据：提供文本文件准备数据：使用python解析文本文件分析数据：使用matplotlib画二维散点图训练算法测试算法：使用提供的部分数据作为测试样本使用算法：产生简单的命令行程序，用户输入一些特征数据以作判断样本数据（datingTestSet2.txt）1000条数据，每条数据一行，前三列为特征数据，第四列为标签。前三列的含义为：每年获得的飞行里程数玩视频游戏所耗时间百分比每周消费的冰激凌公升数将文本记录转换为矩阵file2matrix()deffile2matrix(filename):fr=open(filename)numberOfLines=len(fr.readlines())#getthenumberoflinesinthefilereturnMat=zeros((numberOfLines,3))#preparematrixtoreturnclassLabelVector=[]#preparelabelsreturnfr=open(filename)index=0forlineinfr.readlines():line=line.strip()#截掉\nlistFromLine=line.split(‘\t’)#根据\t获得数组returnMat[index,:]=listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))#将倒数第一列字符转换为整数并添加到标签向量中index+=1returnreturnMat,classLabelVector将导出的样本文件数据画出散点图importkNNdatingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')importmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat[:,1],datingDataMat[:,2])plt.show()fig.savefig('ex2_02.png')只取第2和第3个特征的数据集加上颜色和不同大小的散点图fromnumpyimport*ImportkNNdatingDataMat,datingLabels=kNN.file2matrix(‘datingTestSet2.txt’)importmatplotlibimportmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))绘制不同颜色的点说明：Fromnumpyimport*#为了使用arrayax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))#第三个参数表示点的大小#第四个参数表示颜色特征数据的影响（ex2_05.py)使用前两列数据进行绘图，飞行里程数对于计算结果的影响远大于其它两个特征：MatplotlibMatplotlib功能强大：Matlab的语法、python语言、latex的画图质量,（还可以使用内嵌的latex引擎绘制的数学公式）Matplotlib绘图库matplotlib实际上是一套面向对象的绘图库，它所绘制的图表中的每个绘图元素，例如线条Line2D、文字Text、刻度等在内存中都有一个对象与之对应。为了方便快速绘图matplotlib通过pyplot模块提供了一套和MATLAB类似的绘图API，将众多绘图对象所构成的复杂结构隐藏在这套API内部。我们只需要调用pyplot模块所提供的函数就可以实现快速绘图以及设置图表的各种细节。Pyplot模块虽然用法简单，但不适合在较大的应用程序中使用。

为了将面向对象的绘图库包装成只使用函数的调用接口，pyplot模块的内部保存了当前图表以及当前子图等信息。当前的图表和子图可以使用plt.gcf()和plt.gca()获得，分别表示“Get

Current

Figure“和"Get

Current

Axes"。在pyplot模块中，许多函数都是对当前的Figure或Axes对象进行处理，比如说：

plt.plot()实际上会通过plt.gca()获得当前的Axes对象ax，然后再调用ax.plot()方法实现真正的绘图。

可以在Ipython中输入类似“plt.plot??“的命令查看pyplot模块的函数是如何对各种绘图对象进行包装的Matplotlib举例importnumpyasnpimportmatplotlib.pyplotaspltplt.figure(1)plt.figure(2)ax1=plt.subplot(211)ax2=plt.subplot(212)x=np.linspace(0,3,100)foriinxrange(5):plt.figure(1)plt.plot(x,np.exp(i*x/3))plt.sca(ax1)plt.plot(x,np.sin(i*x))plt.sca(ax2)plt.plot(x,np.cos(i*x))plt.show()画出的图将画出的图保存下来fig.savefig(‘temp.png’)数据的归一化处理为了避免特征数据由于数值范围不一样而造成对结果影响的不同，需要将特征数据进行归一化处理newValue=(oldValue-min)/(max-min)归一化特征值autoNorm(dataSet)defautoNorm(dataSet):minVals=dataSet.min(0)maxVals=dataSet.max(0)ranges=maxVals-minValsnormDataSet=zeros(shape(dataSet))m=dataSet.shape[0]normDataSet=dataSet-tile(minVals,(m,1))normDataSet=normDataSet/tile(ranges,(m,1))#elementwisedividereturnnormDataSet,ranges,minVals归一化样本数据importkNNdatingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')normMat,ranges,minVals=kNN.autoNorm(datingDataMat)normMatrangesminVals归一化后的样本数据2.2.4验证分类器defdatingClassTest():hoRatio=0.50#holdout10%datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')#loaddatasetfromfilenormMat,ranges,minVals=autoNorm(datingDataMat)m=normMat.shape[0]numTestVecs=int(m*hoRatio)errorCount=0.0foriinrange(numTestVecs):classifierResult=classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)print"theclassifiercamebackwith:%d,therealansweris:%d"%(classifierResult,datingLabels[i])if(classifierResult!=datingLabels[i]):errorCount+=1.0print"thetotalerrorrateis:%f"%(errorCount/float(numTestVecs))printerrorCountimportkNNkNN.datingClassTest()thetotalerrorrateis:0.064000构建完整可用的分类系统ClassifyPerson()defclassifyPerson():resultList=['notatall','insmalldoses','inlargedoses']percentTats=float(raw_input("percentageoftimespentplayingvideogames?"))ffMiles=float(raw_input("frequentfliermilesearnedperyear?"))iceCream=float(raw_input("litersoficecreamconsumedperyear?"))datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')normMat,ranges,minVals=autoNorm(datingDataMat)inArr=array([ffMiles,percentTats,iceCream])classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)print"Youwillprobablylikethisperson:",resultList[classifierResult-1]运行结果:2.3手写识别系统收集数据：提供文本文件准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式分析数据：在python命令提示符中检查数据，确保它符合要求训练算法测试算法：编写函数使用提供的部分数据集作为测试样本；使用算法一、准备数据，将图像转换为测试向量（ch02/digits/trainingDigits,来源：/ml)将图像格式化处理为一个向量将32*32的二进制图像矩阵转换为1*1024的向量Img2vector()defimg2vector(filename):returnVect=zeros((1,1024))fr=open(filename)foriinrange(32):lineStr=fr.readline()forjinrange(32):returnVect[0,32*i+j]=int(lineStr[j])returnreturnVect测试将图像转变为向量importkNNtestVector=kNN.img2vector('digits/testDigits/0_13.txt')testVector[0,0:31]测试：使用k-近邻算法识别手写数字defhandwritingClassTest():hwLabels=[]trainingFileList=listdir('digits/trainingDigits')#loadthetrainingsetm=len(trainingFileList)trainingMat=zeros((m,1024))foriinrange(m):fileNameStr=trainingFileList[i]fileStr=fileNameStr.split('.')[0]#takeoff.txtclassNumStr=int(fileStr.split('_')[0])