K近邻(KNN)算法详解及Python实现

KNN依然是一种监督学习算法

KNN（K Nearest Neighbors,K近邻 ）算法是机器学习所有算法中理论最简单，最好理解的。KNN是一种基于实例的学习，通过计算新数据与训练数据特征值之间的距离，然后选取 K（K>=1）个距离最近的邻居进行分类判断（投票法）或者回归。如果K=1，那么新数据被简单分配给其近邻的类。KNN算法算是监督学习还是无监 督学习呢？首先来看一下监督学习和无监督学习的定义。对于监督学习，数据都有明确的label（分类针对离散分布，回归针对连续分布），根据机器学习产生 的模型可以将新数据分到一个明确的类或得到一个预测值。对于非监督学习，数据没有label，机器学习出的模型是从数据中提取出来的pattern（提取 决定性特征或者聚类等）。例如聚类是机器根据学习得到的模型来判断新数据“更像”哪些原数据集合。KNN算法用于分类时，每个训练数据都有明确的 label，也可以明确的判断出新数据的label，KNN用于回归时也会根据邻居的值预测出一个明确的值，因此KNN属于监督学习。

KNN算法的过程为:

• 选择一种距离计算方式, 通过数据所有的特征计算新数据与已知类别数据集中的数据点的距离
• 按照距离递增次序进行排序，选取与当前距离最小的k个点
• 对于离散分类，返回k个点出现频率最多的类别作预测分类；对于回归则返回k个点的加权值作为预测值

KNN算法关键

KNN算法的理论和过程就是那么简单，为了使其获得更好的学习效果，有下面几个需要注意的地方。

• 数据的所有特征都要做可比较的量化。
  若是数据特征中存在非数值的类型，必须采取手段将其量化为数值。举个例子，若样本特征中包含颜色（红 黑蓝）一项，颜色之间是没有距离可言的，可通过将颜色转换为灰度值来实现距离计算。另外，样本有多个参数，每一个参数都有自己的定义域和取值范围，他们对 distance计算的影响也就不一样，如取值较大的影响力会盖过取值较小的参数。为了公平，样本参数必须做一些scale处理，最简单的方式就是所有特 征的数值都采取归一化处置。
• 需要一个distance函数以计算两个样本之间的距离。
  距离的定义有很多，如欧氏距离、余弦距离、汉明距离、曼哈顿距离等等，关于相似性度量的方法可参考：机器学习中距离和相似性度量方法 。 一般情况下，选欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，汉明距离可以用来作为度量。通常情况下，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法。
• 确定K的值
  K是一个自定义的常数，K的值也直接影响最后的估计，一种选择K值得方法是使用 cross-validate（交叉验证）误差统计选择法。交叉验证的概念之前提过，就是数据样本的一部分作为训练样本，一部分作为测试样本，比如选择 95%作为训练样本，剩下的用作测试样本。通过训练数据训练一个机器学习模型，然后利用测试数据测试其误差率。 cross-validate（交叉验证）误差统计选择法就是比较不同K值时的交叉验证平均误差率，选择误差率最小的那个K值。例如选择 K=1,2,3,... ， 对每个K=i做100次交叉验证，计算出平均误差，然后比较、选出最小的那个。

KNN分类

训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签（喜欢或者不喜欢、保留或者删除）。分类算法常采用“多数表决”决定，即k个邻居中 出现次数最多的那个类作为预测类。“多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果，那是因为他们比较大可能出现在测试点的K邻 域而测试点的属性又是通过K领域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将K个邻居到测试点的距离考虑进去。例如，若样本到测试点距离 为d，则选1/d为该邻居的权重（也就是得到了该邻居所属类的权重），接下来统计统计k个邻居所有类标签的权重和，值最大的那个就是新数据点的预测类标 签。

举例，K=5，计算出新数据点到最近的五个邻居的举例是（1,3,3,4,5），五个邻居的类标签是（yes，no，no，yes，no）

若是按照多数表决法，则新数据点类别为no（3个no，2个yes）；若考虑距离权重类别则为yes（no：2/3+1/5,yes：1+1/4）。

下面的Python程序是采用KNN算法的实例（计算欧氏距离，多数表决法决断）：一个是采用KNN算法改进约会网站配对效果，另一个是采用KNN算法进行手写识别。

约会网站配对效果改进的例子是根据男子的每年的飞行里程、视频游戏时间比和每周冰激凌耗量三个特征来判断其是否是海伦姑娘喜欢的类型（类别为很喜欢、一般和讨厌），决策采用多数表决法。由于三个特征的取值范围不同，这里采用的scale策略为归一化。

使用KNN分类器的手写识别系统 只能识别数字0到9。需要识别的数字使用图形处理软件，处理成具有相同的色 彩和大小 ：宽髙是32像素X32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间,为了方便理解，这里已经将将图像转换为文本格式。训练数据中每 个数字大概有200个样本，程序中将图像样本格式化处理为向量,即一个把一个32x32的二进制图像矩阵转换为一个1x1024的向量。

from numpy import *  import operator  from os import listdir  import matplotlib  import matplotlib.pyplot as plt  import pdb    def classify0(inX, dataSet, labels, k=3):      #pdb.set_trace()      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() #ascend sorted,      #return the index of unsorted, that is to choose the least 3 item          classCount={}                for i in range(k):          voteIlabel = labels[sortedDistIndicies[i]]          classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1# a dict with label as key and occurrence number as value      sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)      '''descend sorted according to value, '''      return sortedClassCount[0][0]      def file2matrix(filename):      fr = open(filename)      #pdb.set_trace()      L = fr.readlines()      numberOfLines = len(L)         #get the number of lines in the file      returnMat = zeros((numberOfLines,3))        #prepare matrix to return      classLabelVector = []                       #prepare labels return             index = 0      for line in L:          line = line.strip()          listFromLine = line.split('\t')          returnMat[index,:] = listFromLine[0:3]          classLabelVector.append(int(listFromLine[-1]))          #classLabelVector.append((listFromLine[-1]))          index += 1      fr.close()      return returnMat,classLabelVector    def plotscattter():      datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file      fig = plt.figure()      ax1 = fig.add_subplot(111)      ax2 = fig.add_subplot(111)      ax3 = fig.add_subplot(111)      ax1.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))      #ax2.scatter(datingDataMat[:,0],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))      #ax2.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))      plt.show()              def autoNorm(dataSet):      minVals = dataSet.min(0)      maxVals = dataSet.max(0)      ranges = maxVals - minVals      normDataSet = zeros(shape(dataSet))      m = dataSet.shape[0]      normDataSet = dataSet - tile(minVals, (m,1))      normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide      return normDataSet, ranges, minVals       def datingClassTest(hoRatio = 0.20):      #hold out 10%      datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file      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: %.2f%%" % (100*errorCount/float(numTestVecs))      print 'testcount is %s, errorCount is %s' %(numTestVecs,errorCount)    def classifyPerson():      '''      input a person , decide like or not, then update the DB      '''      resultlist = ['not at all','little doses','large doses']      percentTats = float(raw_input('input the person\' percentage of time playing video games:'))      ffMiles = float(raw_input('flier miles in a year:'))      iceCream = float(raw_input('amount of iceCream consumed per year:'))      datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')      normMat, ranges, minVals = autoNorm(datingDataMat)      normPerson = (array([ffMiles,percentTats,iceCream])-minVals)/ranges      result = classify0(normPerson, normMat, datingLabels, 3)      print 'you will probably like this guy in:', resultlist[result -1]        #update the datingTestSet      print 'update dating DB'      tmp = '\t'.join([repr(ffMiles),repr(percentTats),repr(iceCream),repr(result)])+'\n'        with open('datingTestSet2.txt','a') as fr:          fr.write(tmp)    def img2file(filename):      #vector = zeros(1,1024)      with open(filename) as fr:          L=fr.readlines()      vector =[int(L[i][j]) for i in range(32) for j in range(32)]      return array(vector,dtype = float)              def handwritingClassTest():      hwLabels = []      trainingFileList = listdir('trainingDigits')           #load the training set      m = len(trainingFileList)      trainingMat = zeros((m,1024))      for i in range(m):          fileNameStr = trainingFileList[i]          fileStr = fileNameStr.split('.')[0]     #take off .txt          classNumStr = int(fileStr.split('_')[0])          hwLabels.append(classNumStr)          trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)      testFileList = listdir('testDigits')        #iterate through the test set      errorCount = 0.0      mTest = len(testFileList)      for i in range(mTest):          fileNameStr = testFileList[i]          fileStr = fileNameStr.split('.')[0]     #take off .txt          classNumStr = int(fileStr.split('_')[0])          vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)          classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)          print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)          if (classifierResult != classNumStr): errorCount += 1.0      print "\nthe total number of errors is: %d" % errorCount      print "\nthe total error rate is: %f" % (errorCount/float(mTest))    if __name__ == '__main__':      datingClassTest()      #handwritingClassTest()

KNN回归

数据点的类别标签是连续值时应用KNN算法就是回归，与KNN分类算法过程相同，区别在于对K个邻居的处理上。KNN回归是取K个邻居类标签值得加 权作为新数据点的预测值。加权方法有：K个近邻的属性值的平均值（最差）、1/d为权重（有效的衡量邻居的权重，使较近邻居的权重比较远邻居的权重大）、 高斯函数（或者其他适当的减函数）计算权重= gaussian(distance) （距离越远得到的值就越小，加权得到更为准确的估计。

总结

K-近邻算法是分类数据最简单最有效的算法，其学习基于实例，使用算法时我们必须有接近实际数据的训练样本数据。K-近邻算法必须保存全部数据集， 如果训练数据集的很大，必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。k-近邻算法的另一个缺陷是它 无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。