第2章k近邻算法

1、kNN特点特点 kNN 是一种基于向量空间的分类方法 该方法非常简单，也容易实现 在大多数情况下，kNN的效果比朴素贝叶斯和中心向量法要好 如果你急切需要一种精度很高分类器并很快投入运行 . . . . . 如果你不是特别关注效率 . . . . . . 那么就使用kNN工作原理工作原理 测量不同特征值之间的距离方法进行分类 优点：精度高、对异常值不敏感、无数据输入假定 缺点：计算复杂度高、空间复杂度高 适用数据范围：数值型和标称型计算新数据与样本数据的相似度计算新数据与样本数据的相似度样本集（有标签的数据集）新数据集选择样本数据集中前k个最相似的数据出现最多的分类作为新数据的分类创建数据集和

2、标签创建数据集和标签def createDataSet(): group = array(1.0,1.1,1.0,1.0,0,0,0,0.1) labels = A,A,B,B return group, labelsK-近邻算法：带有近邻算法：带有4个数据点的数据集个数据点的数据集import kNNgroup,labels=kNN.createDataSet()import matplotlibimport matplotlib.pyplot as pltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(group:,0,group:,1)

3、plt.show()kNN算法算法计算已知类别数据集中的每个点依次执行以下操作： 计算已知类别数据集中的点与当前点之间的距离 按照距离递增次序排序 选取与当前点距离最小的k个点 确定前k个点所在类别的出现频率 返回前k个点出现频率最高的类别作为当前点的预测分类K-近邻算法近邻算法def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape0 diffMat = tile(inX, (dataSetSize,1) - dataSet sqDiffMat = diffMat*2 sqDistances = sqDiffMat

4、.sum(axis=1) distances = sqDistances*0.5 sortedDistIndicies = distances.argsort() classCount= for i in range(k): voteIlabel = labelssortedDistIndiciesi classCountvoteIlabel = classCount.get(voteIlabel,0) + 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

5、return sortedClassCount00axis=1是将一个矩阵的每一行向量相加import numpy as npnp.sum(0,1,2,2,1,3,axis=1)的结果就是：array（3,6）Classify0()中的参数中的参数输入参数： inX 待分类的输入向量 dataSet 输入的训练样本集 Labels 标签向量 K 用于选择最近邻居的数目计算两个向量点计算两个向量点xA和和xB之间的欧之间的欧氏距离氏距离211200)xBxAxBxAd一些函数介绍：一些函数介绍：Tile(A,n)将数组A重复n次，构成一个新的数组如：A=0,1,2B=tile(a,2)Barra

6、y(0,1,2,0,1,2)Operator.itemgetter函数函数用于获取对象的哪些维的数据，参数为一些序号，如：a=1,2,3B=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(文件)。 第三类是

7、你定义的任何包含_iter_()或_getitem_()方法的类的对象。Sorted用法sorted(iterable,cmp,key,reverse=True)作用：Return a new sorted list from the items in iterable. 第一个参数是一个iterable，返回值是一个对iterable中元素进行排序后的列表(list)。可选的参数有三个，cmp、key和reverse。1)cmp指定一个定制的比较函数，这个函数接收两个参数（iterable的元素），如果第一个参数小于第二个参数，返回一个负数；如果第一个参数等于第二个参数，返回零；如果第一个参

8、数大于第二个参数，返回一个正数。默认值为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()方便-如果你不

9、需要原始的list，list.sort()方法效率会稍微高一些。 a=5,2,3,1,4 a.sort() a1,2,3,4,5另一个区别在于list.sort()方法只为list定义。而sorted()函数可以接收任何的iterable。Key Functions(关键字函数关键字函数) sorted(This is a test string from Andrew.split(), key=str.lower) a, Andrew, from, is, string, test, Thiskey的值应该是一个函数，这个函数接收一个参数并且返回一个用于比较的关键字。这种技术比较快，原因在于

10、对每个输入记录，这个函数只会被调用一次。对复杂对象的比较通常是使用对象的切片作为关键字。例如： student_tuples = (john, A, 15), (jane, B, 12), (dave, B, 10), sorted(student_tuples, key=lambda student: student2) # sort by age (dave, B, 10), (jane, B, 12), (john, A, 15)调用调用kNN.createDataSet(),创建数据集作为样本数据创建数据集作为样本数据,调用调用kNN.classify0(),对向量对向量0,0分类分类

11、例：使用例：使用k-近邻算法改进约会网站的配对效果近邻算法改进约会网站的配对效果 步骤1. 收集数据：提供文本文件2. 准备数据：使用python解析文本文件3. 分析数据：使用matplotlib画二维散点图4. 训练算法5. 测试算法：使用提供的部分数据作为测试样本6. 使用算法：产生简单的命令行程序，用户输入一些特征数据以作判断样本数据（样本数据（datingTestSet2.txt）10001000条数据，每条数据一行，前三列条数据，每条数据一行，前三列为特征数据，第四列为标签。为特征数据，第四列为标签。前三列的含义为：前三列的含义为：1.1. 每年获得的飞行里程数每年获得的飞行里程数

12、2.2. 玩视频游戏所耗时间百分比玩视频游戏所耗时间百分比3.3. 每周消费的冰激凌公升数每周消费的冰激凌公升数将文本记录转换为矩阵将文本记录转换为矩阵 file2matrix()def file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines() #get the number of lines in the file returnMat = zeros(numberOfLines,3) #prepare matrix to return classLabelVector = #prepare la

13、bels return fr = open(filename) index = 0 for line in fr.readlines(): line = line.strip() # 截掉n listFromLine = line.split(t) #根据t获得数组 returnMatindex,: = listFromLine0:3 classLabelVector.append(int(listFromLine-1) #将倒数第一列字符转换为整数并添加到标签向量中 index += 1 return returnMat,classLabelVector将导出的样本文件数据画出散点图将导出的

14、样本文件数据画出散点图import kNNdatingDataMat,datingLabels=kNN.file2matrix(datingTestSet2.txt)import matplotlib.pyplot as pltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat:,1,datingDataMat:,2)plt.show()fig.savefig(ex2_02.png)只取第只取第2和第和第3个特征的数据集个特征的数据集加上颜色和不同大小的散点图加上颜色和不同大小的散点图from numpy import

15、 *Import kNNdatingDataMat,datingLabels=kNN.file2matrix(datingTestSet2.txt)import matplotlibimport matplotlib.pyplot as pltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat:,1,datingDataMat:,2,15.0*array(datingLabels),15.0*array(datingLabels)绘制不同颜色的点绘制不同颜色的点说明：说明： From numpy import * #

16、为了使用array ax.scatter(datingDataMat:,1,datingDataMat:,2,15.0*array(datingLabels),15.0*array(datingLabels)#第三个参数表示点的大小#第四个参数表示颜色特征数据的影响（特征数据的影响（ex2_05.py)使用前两列数据进行绘图，飞行里程数对于计算结果的影响远大于其它两个特征：MatplotlibMatplotlib功能强大： Matlab的语法、python语言、latex的画图质量,（还可以使用内嵌的latex引擎绘制的数学公式）Matplotlib绘图库绘图库matplotlib实际上是一套

17、面向对象的绘图库，它所绘制的图表中的每个绘图元素，例如线条Line2D、文字Text、刻度等在内存中都有一个对象与之对应。为了方便快速绘图matplotlib通过pyplot模块提供了一套和MATLAB类似的绘图API，将众多绘图对象所构成的复杂结构隐藏在这套API内部。我们只需要调用pyplot模块所提供的函数就可以实现快速绘图以及设置图表的各种细节。Pyplot 模块虽然用法简单，但不适合在较大的 应用程序中使用。 为了将面向对象的绘图库包装成只使用函数的调用接口，pyplot 模块的内部保存了当前图表以及当前子图等信息。当前的图表和子图可以使用plt.gcf() 和 plt.gca()获

18、得，分别表示 “Get Current Figure“ 和 Get Current Axes。在 pyplot 模块中，许多函数都是对当前的 Figure 或 Axes 对象进行处理，比如说： plt.plot() 实际上会通过 plt.gca() 获得当前的 Axes 对象 ax ，然后再调用 ax.plot() 方法实现真正的绘图。 可以在 Ipython 中输入类似 “plt.plot?“ 的命令查看 pyplot 模块的函数是如何对各种绘图对象进行包装的Matplotlib举例举例import numpy as npimport matplotlib.pyplot as pltplt.

19、figure(1)plt.figure(2)ax1=plt.subplot(211)ax2=plt.subplot(212)x=np.linspace(0,3,100)for i in xrange(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)数据的归一化处理数据的归一化处理 为了避免特征数据由于数值

20、范围不一样而造 成对结果影响的不同，需要将特征数据进行归一化处理 newValue=(oldValue-min)/(max-min)归一化特征值归一化特征值autoNorm(dataSet)def autoNorm(dataSet):minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = zeros(shape(dataSet)m = dataSet.shape0normDataSet = dataSet - tile(minVals, (m,1)normDataSet =

21、normDataSet/tile(ranges, (m,1) #element wise dividereturn normDataSet, ranges, minVals归一化样本数据归一化样本数据import kNNdatingDataMat,datingLabels=kNN.file2matrix(datingTestSet2.txt)normMat,ranges,minVals=kNN.autoNorm(datingDataMat)normMatrangesminVals归一化后的样本数据归一化后的样本数据2.2.4 验证分类器验证分类器def datingClassTest(): h

22、oRatio = 0.50 #hold out 10% datingDataMat,datingLabels = file2matrix(datingTestSet2.txt) #load data setfrom file normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape0 numTestVecs = int(m*hoRatio) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMati,:,no

23、rmMatnumTestVecs:m,:,datingLabelsnumTestVecs:m,3) print the classifier came back with: %d, the real answer is: %d % (classifierResult, datingLabelsi) if (classifierResult != datingLabelsi): errorCount += 1.0 print the total error rate is: %f % (errorCount/float(numTestVecs) print errorCountimport kN

24、NkNN.datingClassTest()the total error rate is: 0.064000构建完整可用的分类系统构建完整可用的分类系统 ClassifyPerson()def classifyPerson():resultList=not at all,in small doses,in large dosespercentTats=float(raw_input(percentage of time spent playing video games?)ffMiles=float(raw_input(frequent flier miles earned per year

25、?)iceCream=float(raw_input(liters of ice cream consumed per year?)datingDataMat,datingLabels=file2matrix(datingTestSet2.txt)normMat,ranges,minVals=autoNorm(datingDataMat)inArr=array(ffMiles,percentTats,iceCream)classifierResult=classify0(inArr-minVals)/ranges,normMat,datingLabels,3)print You will pr

26、obably like this person:,resultListclassifierResult-1运行结果运行结果:2.3 手写识别系统手写识别系统 收集数据：提供文本文件 准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式 分析数据：在python命令提示符中检查数据，确保它符合要求 训练算法 测试算法：编写函数使用提供的部分数据集作为测试样本； 使用算法一、准备数据，将图像转换为测试向量一、准备数据，将图像转换为测试向量（ch02/digits/trainingDigits,来源：来源：/ml)将图像

27、格式化处理为一个向量将图像格式化处理为一个向量 将32*32的二进制图像矩阵转换为1*1024的向量 Img2vector()def img2vector(filename):returnVect = zeros(1,1024)fr = open(filename)for i in range(32):lineStr = fr.readline()for j in range(32):returnVect0,32*i+j = int(lineStrj)return returnVect测试将图像转变为向量测试将图像转变为向量import kNNtestVector=kNN.img2vector

28、(digits/testDigits/0_13.txt)testVector0,0:31测试：使用测试：使用k-近邻算法识别手写数字近邻算法识别手写数字def handwritingClassTest(): hwLabels = trainingFileList = listdir(digits/trainingDigits) #load the training set m = len(trainingFileList) trainingMat = zeros(m,1024) for i in range(m): fileNameStr = trainingFileListi fileStr = fileNameStr.split(.)0 #