1.KNN定义    

    KNN属于有监督的学习，其基本思想是：在已知分类的一个训练数据集中，输入新的未知分类的实例，通过与训练数据集中的数据一一对比，找到与该实例最近的k个实例，这k个实例的多数属于某个类，则将该输入实例分为这个类。

    如下图，绿色圆作为未知分类的数据被输入，此时我们根据周围邻居的类别对其进行判断。①当K=3时，红色三角形占比为2/3，蓝色正方形占比为1/3，绿色圆将被判定为红色三角形；②当K=5时，红色三角形占比为2/5，蓝色正方形占比为3/5，因此绿色圆被判定为蓝色正方形。

2.KNN中K值的选择

    如上所述，这里K值的大小可以任意设定（当K=1时，称算法为最近邻算法），但是k值的选择会对KNN的结果产生重大影响，因此K值的选择具有极其重要的意义。

    当选择的K值较小时，用于预测的训练数据集则较小（同上面情形①），此时近似误差会减小，但是其估计误差会增大，预测结果对近邻的实例点非常敏感。若此时近邻的实例点是噪声，预测就会出错。

    当选择的K值较大时，用于预测的训练数据集则较大（同上面情形②），此时估计误差会减小，但是其近似误差又会增大，此时与输入实例较远(不相似)的实例也会对预测起作用，使预测发生错误。

    在实际的应用中，通常会选择较小的K值。由于K值小时意味着整体的模型变得复杂，容易形成过拟合，因此通常采用交叉验证的方式选择最优的K值。

3.KNN相似度计算

    特征空间中两个实例点的距离是衡量两个实例点相似度的基本度量单位。机器学习中存在多种距离计算方式，通常使用的使欧式距离，也可使用切比雪夫距离或闵可夫斯基距离。

    以上距离公式中，当p=1时，称为曼哈顿距离；当p=2时，即为欧式距离，我们常使用欧式距离计算两点间相似度；当p=∞时，称为切比雪夫距离。p值的不同会造成为输入数据选择的近邻不一样。

4.KNN算法

输入：训练数据集T={(x1,y1),(x2,y2),(x3,y3),...,(xn,yn)}，其中x为实例特征向量，该向量可以是1维也可以是多维；y为实例的类别，当类别为2时称二分类，类别较多时则称为多分类

输出：未知实例x的类别

①根据给定的距离度量，在训练集T中找出与输入实例x最相近的k个点；

②在这k个点中根据分类决策规则（如多数表决）判定x的类别

#--*-- coding:utf-8 --*--

from numpy import *

def knn(input, train_datas, label, k, p = 2):
    dataSize = train_datas.shape[0]

    #距离计算
    diff = tile(input,(dataSize,1)) - train_datas
    sqdiff = diff ** p   #默认p为2，即欧式距离
    squareDistance = sum(sqdiff,axis = 1)
    dist = squareDistance ** (float(1) / p)

    sortedDistIndex = dist.argsort() #将dist中的元素从小到大排列,并返回该元素之前的索引值

    classCount = {}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        #对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1

    #选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    print ‘输入实例属于：‘+ str(classes) + ‘类，其该类近邻数有‘,str(maxCount) + ‘个‘

if __name__ == ‘__main__‘:
    x = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    y = [‘A‘,‘A‘,‘B‘,‘B‘]
    i = array([0.1,0.1])
    knn(i, x , y ,k=3,p=1)

输出结果为：

输入实例属于：B类，其该类近邻数有 2个

reference:

《统计学习学习方法》

《机器学习》 

本文出自 “abe” 博客，请务必保留此出处http://abezoo.blog.51cto.com/7223683/1945696

K-近邻(KNN)