k-进邻算法

概述

原理

存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

步骤

1. 计算已知类别数据集中的点与当前点之间的距离；
2. 按照距离递增次序排序；
3. 选取与当前点距离最小的k个点；
4. 确定前k个点所在类别的出现频率；
5. 返回前k个点所出现频率最高的类别作为当前点的预测分类。

相关公式（欧氏距离）

核心代码如下

def classify0(inX, dataSet, labels, k):
    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()     
    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), reverse=True)
    return sortedClassCount[0][0]

注意事项

数据要做归一化，要不其中一项的影响会特别大

比如距离的范围0到5000，年龄范围0到100，在算距离的时候，距离这个特征产生的影响远远比年龄大，导致年龄这个特征不起作用，正确做法是把所有特征变为【0,1】之间，python代码如下

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

简单例子

判断一个电影是爱情片还是武打片，取两个特征打斗镜头和接吻镜头，由于这两个特征是否归一化影响不大，所以这里忽略归一化，有了这四个训练集，现在测试数据有一部电影打斗镜头101次,接吻镜头20次，是什么类型的电影

 通过计算，我们可以得到如下结果：

(101,20)->动作片(108,5)的距离约为16.55
(101,20)->动作片(115,8)的距离约为18.44
(101,20)->爱情片(5,89)的距离约为118.22
(101,20)->爱情片(1,101)的距离约为128.69
 

通过计算可知，电影到动作片 (108,5)的距离最近，为16.55。如果算法直接根据这个结果，判断该红色圆点标记的电影为动作片，这个算法就是最近邻算法，而非k-近邻算法。k-近邻算法，我们假设k=3，也就是取距离最近前三个的最大值作为其结果，最近的前三个为

动作片(108,5)的距离约为16.55

动作片(115,8)的距离约为18.44

爱情片(5,89)的距离约为118.22

里面出现动作片次数2大于爱情片1，所以(101,20)利用k-进邻算法的结果是动作片
喜欢的小伙伴可以给个赞哦