数据挖掘十大经典算法(8) kNN
1、K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空 间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本， 而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的 邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
4、 该算法在分类时有个主要的不足是 ，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 算法分类过程如下：
1 首先我们事先定下k值（就是指k近邻方法的k的大小，代表对于一个待分类的数据点，我们要寻找几个它的邻居）。这边为了说明问题，我们取两个k值，分别为3和9；
2 根据事先确定的距离度量公式（如：欧氏距离），得出待分类数据点和所有已知类别的样本点中，距离最近的k个样本。
3 统计这k个样本点中，各个类别的数量。根据k个样本中，数量最多的样本是什么类别，我们就把这个数据点定为什么类别。
训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量 （查询或测试点）将被归类为最接近该点的K个样本点中最频繁使用的一类。
一般情况下，将欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，
另一个度量——重叠度量（或海明距离）可以用来作为度量。通常情况下，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法。
“多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果，那是因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过K领域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将样本到测试点的距离考虑进去。
K值得选择
如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取，比如，交叉验证。
噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[3]，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。
K近邻算法也适用于连续变量估计，比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有：
1、从目标区域抽样计算欧式或马氏距离；
2、在交叉验证后的RMSE基础上选择启发式最优的K邻域；
3、计算多元k-最近邻居的距离倒数加权平均。
