【K近邻算法介绍】

目前常用的分类算法主要有：朴素贝叶斯分类算法（Naïve Bayes）、支持向量机分类算法（Support Vector Machines）、 KNN最近邻算法(k-Nearest Neighbors)、神经网络算法（NNet）以及决策树（Decision Tree）等等

 

K Nearest Neighbor算法又叫KNN算法，这个算法是机器学习里面一个比较经典的算法， 总体来说KNN算法是相对比较容易理解的算法。

 

K近邻算法工作原理：存在一个样本数据集合（训练样本集），并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据。最后，选择k个最相似数据中出现次数最多的分类，最为新数据的分类。

 

“邻近性”用距离度量，距离越大，表示两个点越不相似。

计算距离的方法：欧几里得距离、曼哈顿距离或其它距离。但多采用欧几里得距离（简单）。

 

 

K值的选择会对k近邻法的结果产生重大影响。

如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合。

 

如果选择较大的K值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时，与输入实例较远（不相似的）训练实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单。

 

如果K=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类。模型过于简单，忽略了训练实例中大量有用信息。

 

在实际应用中，K值一般取一个比较小的数值。例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。

 

 

 

K近邻算法流程

1)准备数据，对数据进行预处理

2)选用合适的数据结构存储训练数据和测试元组

3)设定参数，如k

4)维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列

5)遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列中的最大距离Lmax

6)进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队。

7)遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。

8)测试元组集测试完毕后计算误差率，继续设定不同的k 值重新进行训练，最后取误差率最小的k 值。

 

 

K近邻算法优缺点

优点

简单，易于理解，易于实现，无需估计参数，无需训练；

适合对稀有事件进行分类；

特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。

懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢；

当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；

可解释性较差，无法给出决策树那样的规则。

 

 

缺点

k值的设定

k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。

如何选取恰当的K值也成为KNN的研究热点。k值通常是采用交叉检验来确定（以k=1为基准）。

经验规则：k一般低于训练样本数的平方根。

 

类别的判定方式

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。

 

距离度量方式的选择

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。

变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

 

训练样本的参考原则

学者们对于训练样本的选择进行研究，以达到减少计算的目的，这些算法大致可分为两类。第一类,减少训练集的大小。KNN算法存储的样本数据,这些样本数据包含了大量冗余数据,这些冗余的数据增了存储的开销和计算代价。缩小训练样本的方法有:在原有的样本中删掉一部分与分类相关不大的样本样本,将剩下的样本作为新的训练样本;或在原来的训练样本集中选取一些代表样本作为新的训练样本；或通过聚类,将聚类所产生的中心点作为新的训练样本。

在训练集中，有些样本可能是更值得依赖的。可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

 

性能问题

kNN是一种懒惰算法，而懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。

已经有一些方法提高计算的效率，例如压缩训练样本量等。