k-近邻算法的初步研究

k-近邻算法

目录

​​k-近邻算法    1 ​​

​​1    算法介绍    2​​

​​2    适用场景    2​​

​​3    方法步骤（案例）    2​​

​​3.1    首先我们事先定下k值    3​​

​​3.2    根据事先确定的距离度量公式（如：欧氏距离），得出待分类数据点和所有已知类别的样本点中，距离最近的k个样本。    3​​

​​3.3    统计这k个样本点中，各个类别的数量。    3​​

​​3.4    手写识别系统的实现    4​​

​​4    代码实现    5​​

​​5    发展    5​​

​​6    不足    6​​

​​6.1    寻找适当的训练数据集    6​​

​​6.2    确定距离函数    6​​

​​6.3    决定K的取值    6​​

​​7    参考    7​​

算法介绍

K最近邻(k-Nearest Neighbour，KNN)分类算法，是最简单的机器学习算法之一。

该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别（相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。），通常，k是不大于20的整数。

KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。

适用场景

由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比（　较近邻居的权重比较远邻居的权重大。）（一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。这个方案是一个线性插值的推广。）

K近邻算法也适用于​​连续变量​​估计，比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有：

从目标区域抽样计算欧式或马氏距离；

在交叉验证后的RMSE基础上选择启发式最优的K邻域；

计算多元k-最近邻居的距离倒数加权平均。

方法步骤（案例）

我们考虑样本为二维的情况下，利用knn方法进行二分类的问题。图中三角形和方形是已知类别的样本点，这里我们假设三角形为正类，方形为负类。图中圆形点是未知类别的数据，我们要利用这些已知类别的样本对它进行分类。

首先我们事先定下k值

（就是指k近邻方法的k的大小，代表对于一个待分类的数据点，我们要寻找几个它的邻居）。这边为了说明问题，我们取两个k值，分别为3和9；

根据事先确定的距离度量公式（如：​​欧氏距离​​），得出待分类数据点和所有已知类别的样本点中，距离最近的k个样本。

统计这k个样本点中，各个类别的数量。

如上图，如果我们选定k值为3，则正类样本（三角形）有1个，负类样本（圆形）有2个，那么我们就把这个方形数据点定为负类；而如果我们选择k值为9，则正类样本（三角形）有5个，负类样本（圆形）有4个，那么我们这个数据点定为正类。即，根据k个样本中，数量最多的样本是什么类别，我们就把这个数据点定为什么类别。

训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量 （查询或测试点）将被归类为最接近该点的K个样本点中最频繁使用的一类。 一般情况下，将欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，另一个度量——重叠度量（或海明距离）可以用来作为度量。通常情况下，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法。

输入：训练数据集D={(Xi,Yi),1≤i≤N}，其中Xi是第i个样本的条件属性，Yi是类别,新样本X，距离函数d。 

输出:X的类别Y。 for i=1 to N do 

计算X和Xi之间的距离d(Xi,X)； end for 

对距离排序，得到d(X,Xi1) ≤d(X,Xi2) ≤… ≤d(X,XiN)； 选择前K个样本：S={(Xi1,Yi1)…(XiK,YiK)}； 统计S中每个类别出现的次数，确定X的类别Y 。

手写识别系统的实现

原始图片（举例）：

经过转换后的向量图（举例）：

假定识别数字0-9,（实际情况可能为识别车牌号、验证码，总之为有限个（且不是非常多）符号），具体实现步骤为：

收集数据（采集数字图片）

采集手写数字图片，每个数字约定采集样本数据为200张，共2000张数字图片，同时另外采集200张数字图片作为测试数据。

准备数据（将图像转换为测试向量）

将32*32的二进制图像矩阵格式化为1*1024的向量（数组），存储方式为Map<Integer,byte[]>

Byte数组大小为1024，存储0或1（表示该单元格有被写入或未被写入），Map大小为2000，同时设定k为1（取相似度最高的一个）。

测试数据

将测试图片200张转换为向量数据，依次传入算法中，每张测试图片需计算2000次，找出与byte数组中匹配最大的值，取出其Map中的KEY，即为转换后的数字，计算误差率，并调整K值，分析K值对错误率的影响。

代码实现

发展

然而k最近邻居法因为计算量相当的大，所以相当的耗时，Ko与Seo提出一算法TCFP(text categorization using feature projection)，尝试利用特征投影法来降低与分类无关的特征对于系统的影响，并借此提升系统效能，其实实验结果显示其分类效果与k最近邻居法相近，但其运算所需时间仅需k最近邻居法运算时间的五十分之一。

除了针对文件分类的效率，尚有研究针对如何促进k最近邻居法在文件分类方面的效果，如Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

不足

1. 
   

   寻找适当的训练数据集

   
   

算法要求对选取的样本数据必须要尽可能的对历史数据的一个很好的覆盖，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算"最近的"邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进；另外一点是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

确定距离函数

距离函数决定了哪些样本是待分类本的K个最近邻居，它的选取取决于实际的数据和决策问题。如果样本是空间中点，最常用的是欧几里德距离。其它常用的距离函是由绝对距离、平方差和标准差。

欧几里德距离：

点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为

向量 

 的自然长度，即该点到原点的距离为

.

它是一个纯数值。在欧几里得度量下，两点之间直线最短。

决定K的取值 

邻居的个数对分类的结果有一定的影响，一般先确定一个初始值，再进行调整，直到找到合适的值为止。

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取，比如，交叉验证。

噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

参考

百度百科：k近邻算法 http://baike.baidu.com/view/8349300.htm

Wiki百科：最近邻居算法 https://zh.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E9%84%B0%E5%B1%85%E6%B3%95

百度文库：http://wenku.baidu.com/view/e1eb70d4b9f3f90f76c61be9.html

《机器学习实战》 k近邻算法