k近邻算法概述

K近邻（k-Nearest Neighbor,简称kNN）算法，是一种应用很广泛的监督学习算法。它非常有效且易于掌握，其工作机制也很简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个"邻居"的信息来进行预测。K近邻既可以用于分类又可以用于回归，在分类问题中：我们使用"投票法"，即选择这k个样本中出现最多的类别标记作为预测结果；在回归问题中：我们使用"平均法"，即将这k个样本的输出的平均值作为预测结果。但是在工业界，knn被广泛应用，因此在本次介绍中，我们将着重介绍k近邻在分类方面的应用。

                                                     什么时候使用k近邻呢？

通常在评估一个算法时，我们通常看三个方面：

易于解释
时间复杂度
预测效果

                                                   k近邻算法是如何工作的呢？

我们来举个例子说明下如何用k近邻来分类爱情片和动作片。有人曾统计过很多电影的打斗镜头和接吻镜头，下图显示了6部电影的打斗镜头和接吻镜头数。假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？

首先我们需要知道这个未知镜头存在多少个打斗镜头和接吻镜头，上图的问号位置是该未知电影出现的镜头数图形化展示，具体数字参见下表：

现在我们就可以利用knn来利用一种度量方式，计算未知电影与样本中其他电影的距离，如下表所示：

现在我们得到了样本中所有电影与未知电影的距离，将距离升序排序，可以找到离未知样本距离最近的k个顶啊应。比如说本题中取k=3,那么最靠近未知电影的三个电影分别是He's Not Really into Dudes、Beautiful Woman 和Califinia Man。K近邻算法然后按照这三部电影的类型决定未知电影的类型，而这电影全是爱情片，因此我们就判定未知电影是爱情片。

到底有哪些度量方法以及k是如何确定的呢？

度量方法又叫"metric learning"，这个概念在计算机视觉领域比较常见到。这种度量方法一般是距离度量，空间上有欧氏距离，路径上有曼哈顿距离，国际象棋上的一致范数：切比雪夫距离等等。一般来说需要根据不同的应用场景选择不同的度量方法。

说完了，度量方法，那么knn算法中的k到底该如何取值呢？首先我们得尝试去理解k在算法中是如何起作用的。所以我们直接在实际环境中应用k紧邻算法来说明k值得选择。
 

用python语言实现k近邻算法

其python实现如下：

from numpy import *  
import operator  
from os import listdir  
   
def classify0(inX, dataSet, labels, k):  
#inx:用于分类的输入向量
#dataSet:输入的训练样本集
#labels:标签向量
#k:选择最近邻的数目
    dataSetSize = dataSet.shape[0]  
    diffMat = tile(inX, (dataSetSize,1)) - dataSet  #行方向重复dataSetSize次，列方向1次
    sqDiffMat = diffMat**2  
    sqDistances = sqDiffMat.sum(axis=1)  
    distances = sqDistances**0.5  #求距离
    sortedDistIndicies = distances.argsort()   #排序    
    classCount={}            
    for i in range(k):  
        voteIlabel = labels[sortedDistIndicies[i]]  
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1  #字典get方法
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  #reverse降序、iteritem返回迭代器、itemgetter(1)取value
    return sortedClassCount[0][0]  
我们从网上download一个在线约会网站的例子，一部分数据如下图所示：

其中每一行是一条会员的信息，依次为每年获得的飞行常客里程数，玩视频游戏所耗时间百分比，每周消费的冰淇淋公升数。

，我们取前两列的数据来画一个二维的散点图，如下图所示：

这里因为数据差值比较大，在应用knn算法前我们先将原始数据做一个归一化处理，将任意取值范围的特征值转化为0到1区间的值。公式如下：

归一化代码如下：

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  

测试算法

上面我们已经将knn算法实现了，那么我们怎么才能对这个算法做个评估呢？这里我们采用最原始的做法即：错误率，对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数。那么我们测试数据的代码如下所示：

def datingClassTest():  
    hoRatio = 0.10      #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: %f" % (errorCount/float(numTestVecs)))  
    print(errorCount)  
这里我们默认取k=3，每测试一条数据就打印输出，最后汇总错误率。log打印输出如下：

可以看到，分类错误总计五个，错误率为5%。

我们随机找个人的信息输入进去，测试结果如下：

K值的确定

说了这么多，我们还是没说如何确定k值。我们是这样思考的：选定训练集和对应的测试机，然后选取不同的k值，把其中错误率最低的k作为分类的k值，当有新的训练集更新时，我们再运行模型，不断迭代更新。我们用上面的例子，将k的取值范围定位3-20（一般来说k是不超过20的整数）,运行结果如下：

最终我们确定可最佳k为7。