算法概述
1、指导思想
kNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。
计算步骤如下：
1）算距离：给定测试对象，计算它与训练集中的每个对象的距离
2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻
3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类
2、距离或相似度的衡量
1）在计算距离时，如果具有最大差值的属性值对距离的影响非常大时，需要对数据进行归一化（例如：newValue=oldValue/（MaxValue-MinValue））。
2）什么是合适的距离衡量？距离越近应该意味着这两个点属于一个分类的可能性越大。
觉的距离衡量包括欧式距离、夹角余弦等。
对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。
3、类别的判定
1）投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。
2）加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）
优缺点
1、优点
简单，易于理解，易于实现，无需估计参数，无需训练
适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）
特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好
2、缺点
懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢
可解释性较差，无法给出决策树那样的规则。
常见问题
1、k值设定为多大？
k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）
k值通常是采用交叉检验来确定（以k=1为基准）
经验规则：k一般低于训练样本数的平方根
2、类别如何判定最合适？
投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。
3、如何选择合适的距离衡量？
高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。
变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。
4、训练样本是否要一视同仁？
在训练集中，有些样本可能是更值得依赖的。
可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。
5、性能问题？
kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。
懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。
已经有一些方法提高计算的效率，例如压缩训练样本量等。
6、能否大幅减少训练样本量，同时又保持分类精度？
浓缩技术(condensing)
编辑技术(editing)
使用示例
电影分类
简介： 电影有很多种，这里仅考虑两种，爱情片和动作片，爱情片里也会有打斗场景，动作片里也会有接吻镜头，因此不能单纯的依靠有无对影片进行分类，那这种时候，我们应该怎么去划分一个影片是爱情片还是动作片呢，这时候，我们可以利用该算法。
方法： 首先一部影片中，接吻的镜头和打斗的镜头是可以进行量化的，比如我们可以数一下，有多少个打斗镜头，有多少个接吻镜头等等，因此，针对每个影片我们可以得到一个长度为2的数组c（接吻镜头数，打斗镜头数） ，同时我们需要寻找一些以知分类的影片同时我们知道这些电影的镜头信息。这些每个电影都可以在二维坐标系里面对应一个坐标点。 当我们需要对一部影片进行分类的时候，我们统计该影片的镜头信息，去计算这个影片和所有以知分类的影片间的距离，然后选取和这个影片距离最近的K个电影，然后看看这K个电影所属的分类，选取权重最高的1个电影分类（注意这里提到了是权重，而不是数目，因为有些情况下，可能需要考虑实际应用的关系，根据数据的可信程度，距离关系等对分类信息进行加权，从而提高分类的准确性），作为该电影的类别或者也可以得到该影片属于不同类别的概率。
1 | print 'a' |