M小白 2018/1/28
完整python代码：关注“技术杂学铺”微信公众号，回复 k临近算法 获取

k临近算法

1.算法原理

问题模型：给定一个样本数据集，样本中有n个特征值（自变量）与1个标签（结果）。通过分析这些数据，预测一个有n个特征值的新数据的标签是什么。
解决方法：在样本数据集中选择与需要估测的数据最相近的k个数据，这k个数据中，哪个标签出现的次数最多，需要估测的数据就属于这个标签。
k临近算法对异常值不敏感，但计算复杂度高，运行时间长。

图片来自网络

2.算法实现

文字描述：

1. 计算需要估测数据与已知所有数据的相似度
2. 根据相似度，对已知数据排序
3. 选择最相近的k个数据
4. 确定这k个数据中各个标签出现的频率
5. 返回出现频率最高的标签作为预测标签

python代码：
(完整python代码关注“技术杂学铺”微信公众号，回复"k临近算法"获得)

from numpy import *
#k临近算法 主要函数 
def classify0(inX, dataSet, labels, k):             #inX为需要判断的样本,dataSet为坐标数据集 m*n大小 labels为数据集对应的标签，1*n大小                                              
    dataSetSize = dataSet.shape[0]                  #计算行数 n

    #计算距离
    diffMat = tile(inX, (dataSetSize,1)) - dataSet  #距离差 先把inX扩展，再求差矩阵
    sqDiffMat = diffMat**2                          #所有元素平方 [n,2]的array
    sqDistances = sqDiffMat.sum(axis=1)             #求每行的和[n,1]
    distances = sqDistances**0.5                    #所有元素开根号

    #选择距离最小的k个点
    sortedDistIndicies = distances.argsort()        #距离远近排序,[1,n]的array,第k行代表distances中第k小的索引
    classCount = {}                                 #建立一个字典
    for i in range (k):
        voteIlabel = labels[sortedDistIndicies[i]]  #获取离inX第i近元素的标签 sortedDistIndicies[i] 第i小的索引值
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 
                                                    #改变字典中元素 voteIlabel是字典中的键key
                                                    #get(key, default=None)：返回指定键的值，如果值不在字典中返回default值
    
    #排序
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) 
                                                    #按照classCount的第二个元素大小，逆排序(大到小)
    return sortedClassCount[0][0]                   #返回第一名的第二个元素（labels标签）

3.使用技巧

3.1 数据归一化

计算相似度往往是计算两个数据各个特征值的差的平方，再求和（距离公式）

欧式距离公式
但如果有的特征值本来数据就大，有的本来数据就小，则单纯的求距离公式就会出现数据大的特征值对结果的影响比数据小的特征值影响大。

比如判断一辆车是否应该报废，假设我们评判标准有两个特征值：行驶公里数和使用了几年。我们再假设这两个评判标准对结果各有50%的影响。

公里数往往是上万、上十万的，而使用了几年最多是一个两位数。各个车之前行驶的公里数可以相差上千、上万，但是使用时长就是一个个位数。

因此，假设我们想让各个特征值对结果的影响相同，可以把数据等比缩放到0至1之间（或者-1至1之间）

缩放公式：结果 =（原数据 - 数据最小值）/（数据最大值 - 数据最小值）

参考书籍：机器学习实战
欢迎关注微信公众号：技术杂学铺