k最近邻算法(kNN)_k近邻算法

k最近邻算法(kNN)

参考http://www.cnblogs.com/v-July-v/archive/2012/11/20/3125419.html

http://www.cnblogs.com/pinard/p/6065607.html

《统计学习方法》

算法描述

kNN是一种基本的分类和回归方法。kNN的输入是测试数据和训练样本数据集，输出是测试样本的类别。kNN没有显示的训练过程，在测试时，计算测试样本和所有训练样本的距离，根据最近的K个训练样本的类别，通过多数投票的方式进行预测。算法描述如下：

输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$，其中$x_i\in R^n,y_i\in \{c_1,c_2,...,c_K\}$和测试数据$x$

输出：实例$x$所属的类别

1. 根据给定的距离度量，在训练集T中找到与x距离最近的k个样本，涵盖这k个点的x的邻域记作$N_k(x)$

2. 在$N_k(x)$中根据分类规则(如多数表决)确定x的类别y：

   $$y=arg\;max_j\;\;\sum_{x_i\in N_k(x)}I\{y_i=c_j\}\;, \;i=1,2,...,n;j=1,2,...,K$$

模型和三要素

从kNN的算法描述中可以发现，有三个元素很重要，分别是距离度量，k的大小和分类规则，这便是kNN模型的三要素。在kNN中，当训练数据集和三要素确定后，相当于将特征空间划分成一些子空间，对于每个训练实例$x_i$，距离该点比距离其它点更近的所有点组成了一个区域，每个区域的类别由决策规则确定且唯一，从而将整个区域划分。对于任何一个测试点，找到其所属的子空间，其类别即为该子空间的类别。

距离度量

距离度量有很多种方式，要根据具体情况选择合适的距离度量方式。常用的是闵可夫斯基距离(Minkowski Distance)，定义为

$$D(x,y)=(\sum_{i=1}^m|x_i-y_i|^p)^{\frac{1}{p}}$$

其中$p\ge1$

当$p=2$时，是欧氏距离，当$p=1$时，是曼哈顿距离。

k的选择

k的选择会对算法的结果产生重大影响。

如果k值较小，就相当于用较小邻域中的训练实例进行预测，极端情况下k=1，测试实例只和最接近的一个样本有关，训练误差很小(0)，但是如果这个样本恰好是噪声，预测就会出错，测试误差很大。也就是所，当k值较小的，会产生过拟合的现象。

如果k值较大，就相当于用很大邻域中的训练实例进行预测，极端情况是k=n，测试实例的结果是训练数据集中实例最多的类，这样会产生欠拟合。

在应用中，一般选择较小k并且k是奇数。通常采用交叉验证的方法来选取合适的k值。

分类规则

kNN中的分类决策规则通常是多数表决，即由测试样本的k个临近样本的多数类决定测试样本的类别。多数表决规则有如下解释：给定测试样本$x$，其最邻近的k个训练实例构成集合$N_k(x)$，分类损失函数为0-1损失。如果涵盖$N_k(x)$区域的类别为$c_j$，则分类误差率是

$$\frac{1}{k}\sum_{x_i\in N_k(x)}I\{y_i\neq c_j\}=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I\{y_i=c_j\}$$

要使得分类误差率小即经验风险最小，所以多数表决等价于经验风险最小化。而kNN的模型相当于对任意的$x$得到$N_k(x)$，损失函数是0-1损失，优化策略是经验风险最小。总的来说就是对$N_k(x)$中的样本应用多数表决。

算法实现

蛮力实现

既然要找到k个最近的邻居来做预测，那么只需要计算预测样本和所有训练集中的样本的距离，然后计算出最小的k个距离即可，接着多数表决，很容易做出预测。这个方法的确简单直接，在样本量少，样本特征少的时候有效。但是在实际运用中很多时候用不上，为什么呢？因为我们经常碰到样本的特征数有上千以上，样本量有几十万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很成问题。因此，这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用。

kd树

kd(k-dimension tree)树算法没有一开始就计算测试样本和所有训练样本的距离，而是先用kd树存储训练数据集，建好了kd树模型后再对测试集做预测，可以减少计算距离的次数。所谓的kd树就是k个特征维度的树，注意这里的k和kNN中的k的意思不同。kNN中的k代表k个邻近样本，kd树中的k代表样本特征的维数。为了防止混淆，后面我们称特征维数为m。

kd树算法包括三步，第一步是构造kd树，第二部是搜索k近邻，最后一步是预测。

构造kd树

kd树是数据的一种存储结构，是一颗平衡二叉树，同时也是对数据所在空间的划分。就是把整个数据空间划分为几个部分，然后在特定的空间内进行操作。

构造kd树的具体流程如下：

算法直到需要被划分的子树为空是停止。

如下图是《统计学习方法》中的一个2维空间例子

左图是对空间的划分，每一个样本点都在划分线上。右图是划分过程中构建的树。可以看出，树每个节点都是一个分割超平面，用垂直于坐标轴的超平面将空间分成两个部分。每次划分时，划分依据的那个点作为kd树中该部分的根节点。比如整个数据集是根据样本(7,2)划分为两部分，所以用(7,2)作了根节点。左半部分是根据(5,4)划分了两部分，(5,4)便作为了左半部的根节点。直到所有划分好的区域中没有样本，算法停止。

搜索k近邻

首先来看如何搜索最近邻，然后通过一个最大堆优先队列寻找k近邻

利用kd树搜索最近邻的过程如下：

输入：已经构造的kd树，测试样本$x$
输出：$x$的最近邻

1. 如果kd树为空，返回null
2. 进行二叉查找，在kd树中找到包含x的叶节点，并生成搜索路径。从根节点开始，递归的向下访问kd树。首先将节点压入表示搜索路径的栈中，如果目标点x当前维的坐标小于切分点的坐标，进入左子节点，否则进入右子节点。直到子节点为空。
3. 回溯查找。根据得到的搜索路径栈，栈顶的元素为‘当前最近点’，将该元素出栈，并计算该点与x的距离d。对于当前栈顶的元素，首先将元素出栈，以x为圆心，d为半径画圆，如果与该元素对应的分割超平面相交，计算该元素和x的距离，如果小于d，则将该元素更新为‘当前最近点’，d也需要更新；如果不相交，则继续对搜索路径的栈顶元素重复相同的操作。同时对元素的另一半子空间对应的子树进行步骤2，搜索的点加入搜索路径。直到搜索路径栈为空。此时得到的‘当前最近点’即为x的最邻近点，d为最邻近距离。

伪代码如下：

1. 如果kd树为空，将距离设置为无穷大并返回

2. 进行二叉查找，生成搜索路径

   kdPoint=kd.root
   while(kdPoint!=null)
       push(kdPoint) into searchPath
       s=kdPoint.split
       if x[s]<kdPoint.data[s]
           kdPoint=kdPoint.left
       else kdPoint=kdPoint.right
   1
   2
   3
   4
   5
   6
   7

3. 回溯查找

   res=searchPath.pop()   //当前最近点
   d=dist(res,x)
   while(searchPath!=null)
       backPoint=seatchPath.pop()
       s=backPoint.split
       if dist(x[s],backPoint.data[s])<d  //需要进入另一半子空间
           if dist(x,backPoint.data)<d
                   res=bachPoint
                   d=dist(x,backPoint.data)
           if x[s]<backPoint.data[s]
               对以backPoint.right为根节点的子树进行二叉查找，并将对应的子搜索路径加入searchPath
          else 对以backPoint.left为根节点的子树进行二叉查找，并将对应的子搜索路径加入searchPath
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13

关于kd树更多知识见http://blog.csdn.net/likika2012/article/details/39619687

有了利用kd树寻找最近邻的算法之后，可以结合最大堆优先队列寻找k近邻。

寻找与x最近的k个样本，首先需要建立一个大小为k的最大堆，在寻找最近邻的算法中，每计算一次距离，将对应的样本和距离加入最大堆中，直到最大堆建立完成。继续寻找最近邻算法，之后计算的距离与堆顶元素比较，如果小于堆顶元素，则替换，并维护最大堆，如果大于堆顶元素，则继续寻找最近邻。直到算法结束。堆中的样本即为x的k个近邻。建立堆的时间是O（k），更新堆的时间为logk，总费时为费时O（k+（n-k）*logk）=O（n*logk）。

这里有类很重要的算法：寻找最小(最大)的k个数

有两种比较常用的方法：1、类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X（随机选取枢纽元，可做到线性期望时间O（N）的复杂度），把数组划分为Sa和Sb俩部分，Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素，否则返回Sa中所有元素+Sb中小的k-|Sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，在最坏情况下亦能做到O（N）的复杂度。不过值得一提的是，这个快速选择SELECT算法是选取数组中“中位数的中位数”作为枢纽元，而非随机选取枢纽元。2、维护k个元素的最大堆(找最小元素用最大堆，找最大元素用最小堆)，用容量为k的最大堆存储最先遍历到的k个数，并假设它们是最小的k个数，建堆费时O（k）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x

预测样本类别

找到测试样本x的k个近邻之后，得到$N_x(x)$,统计$N_k(x)$中每个类别的样本数，然后选择样本数最多的类作为x的类别。即

$$y=arg\;max_j\;\;\sum_{x_i\in N_k(x)}I\{y_i=c_j\}\;, \;i=1,2,...,n;j=1,2,...,K$$

总结

kNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时。另外，kNN算法不能给出数据间的结构信息，所以无法提取样本的特征。

kNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。

kNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。

kNN很耗时，除了蛮力实现的方法，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。

sklearn.neighbors

scikit-learn实现了两个不同的kNN分类器：KNeighborsClassifier基于每个点的k个最近邻实现学习，其中k是用户指定的整数值。 RadiusNeighborsClassifier基于每个点在固定半径r内的样本数量学习，其中r是用户指定的浮点值。
KNeighborsClassifier更常用。k的最佳选择是高度依赖于数据的：通常较大的k抑制噪声对分类准确率的影响，但是使得分类边界不太明显。
在数据不均匀分布的情况下，RadiusNeighborsClassifier是更好的选择。用户指定一个固定的半径r，使得位于稀疏区域中的测试点使用较少的邻点进行分类。对于高维参数空间，由于所谓的“维度灾难”，该方法变得不太有效。

kNN一般使用uniform权重：即所有的权重都一样，在投票是一样重要。在某些情况下，最好对邻点加权重，使较近的点在投票中更加重要。这可以通过权重关键字来实现。默认值weights=’uniform’为每个邻居分配均匀权重。 weight =’distance’分配与查询点距离的倒数成反比的权重。或者，可以自定义权重。

API如下：

从上表可以看出，sklearn.neighbors非监督，分类和回归算法。其中NearestNeighbors是非监督分类算法，寻找一个点的最邻近点，是监督算法的基本。寻找临近点有三种方式：KD-tree，Ball-tree和暴法，类BallTree和KDTree是这两个是实现这两个算法的类。监督算法分为分类和回归，取决于数据标签是离散的还是连续的。分类和回归中都有两个方法，分类中有KNrighborsClassifier和RadiusneighborsClassifier，回归中有KneighborsRegressor和RadiusNeighborsRegressor.另外还有NearestCentroid分类算法。

常用4类算法参数比较

class KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1, **kwargs)

class RadiusNeighborsClassifier(radius=1.0, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', outlier_label=None, metric_params=None, **kwargs)

class KNeighborsRegressor(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1, **kwargs)

class RadiusNeighborsRegressor(radius=1.0, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, **kwargs)
1
2
3
4
5
6
7

k算法和Radius算法的优点

用kNN分类,根据指定的k值，选定距离最近的k个数据来投票。对于均匀分布的数据效果较好。k值大，可以一直噪声的影响，但是分类边界不明显

kNN算法，给定半径，用半径以内的样本来投票。对于不均匀分布的数据也有很好的效果，位于稀疏区域的点，用来投票的样本点少，而位于稠密区域的点，用来投票的样本多。

方法

总结

from sklearn.neighbors import KneighborsClassifier #导入包
clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights) #实例化对象
clf.fit(X, y)  #构造分类器
predictLabels = clf.predict(testData) #预测测试数据的标签
acc=clf.score(testSet,testLabels)
1
2
3
4
5

最近邻居的快速计算是机器学习研究的一个活跃领域。最简单的暴力算法：对于D维N个样本，计算预测点和训练集中每个样本的距离，时间复杂度为O[DN^ 2]。 对于小数据样本，选择该方法。 然而，随着样本数量N的增长，暴力方法的时间迅速增加。 在sklearn.neighbors中的类中，使用关键字algorithm =’brute’指定暴力搜索。

为了解决暴力方法的计算效率低下，已经发明了各种基于树的数据结构。 通常，这些结构试图通过有效地编码样本的总距离信息来减少所需的距离计算数量。 基本思想是，如果A点距B点很远，B点非常接近C点，那么我们知道A点和C点非常遥远，而不必明确地计算它们的距离。 以这种方式，最近邻搜索的计算成本可以减小到O [D N \ log（N）]或更好。 这是对大型大型数据的暴力算法有显着改善。

而KD树，则是最早被广泛用于代替BF进行搜索的算法，并且KD树是一个比四叉树（2维）和八叉树（3维）更加抽象的K维树。KD树使用了二叉树作为基本结构，他用递归的方式对数据进行划分（每一层进行一个维度的划分）。KD树的构建过程是十分迅速的，因为他只需要根据坐标轴进行划分，不用计算多维度的距离。而且只要KD树建立起来，对于每一个点的搜索，其时间复杂度都只有O[\log(N)] 了。在不太高的维度（小于20）下，KD树的效果是很不错的，不过当维度走向更高时，KD树的效率也会随之下降，这也呼应了我们之前提到的“维度之殇”的问题。
在scikit-learn当中，如果需要使用这个算法，设置algorithm为‘kd_tree’就可以了，具体的计算代码可以参照KDTree里的代码。

k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。

然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。

为了解决上面的问题，我们引入了ball tree。

KD-Tree是为了解决Brute Force的效率问题，那么Ball-Tree也就是为了解决KD-Tree在高维情况下的效率不佳的另一个做法了。KD树是在笛卡尔坐标系中进行数据划分的，而Ball树则是在 nesting hyper-spheres当中（大概是网状超球面下，我也不大好翻译）划分的。Ball树在构建的时候，比起KD树要复杂许多，不过在最后的搜索过程中，其表现就会非常好。

Ball树根据质心，C和半径r对数据进行递归的划分，每一个数据点都会被划分到一个特定的圆心C和半径r的的超球体里面，在搜索的时候，候选的点会使用如下的不等式进行筛选：
|x+y| <= |x| + |y|
通过这样的筛选，只用根据半径和圆心就可以计算出一个球体里包含点的距离的上界和下界，那么这样就可以减少很多点的计算了。一个超球体里面包含的点，距离其质心都是有一定的距离范围的，那么对于这一个球体里的所有值，我们只需要首先计算和质心的距离，就可以（根据上下界）判定我们是否需要进一步的搜索了。

在scikit-learn当中，如果要使用Ball树，可以algorithm = ‘ball_tree’的设置，相关代码在sklearn.neighbors.BallTree里

如何选择用哪个算法计算临近点呢？取决于以下几点：

1. 样本个数N和特征数D：当N和D均较小时(N<30)，选择使用暴力算法，查询时间是O(ND)；当N较大D较小(D<20),选择KD_Tree，查询时间是O(D\log(N))；当N和D都较大是，选择Ball_Tree,查询时间是O(D\log(N))
2. 数据结构：根据数据的本征维度(数据的维度很大，但在参数空间下维度和表面维度不一样)和稀疏度。当数据是稀疏的时候，sklearn.neighbors中自动选择使用暴力算法，因为KD_Tree并不能很明显的提高运算速度
3. 临近点个数K：暴力算法通常不受k的影响，但是kd_Tree和Ball_Tree随着K的增大速度减小，因为k增大需要搜索更大的空间，而且当k>1时，需要内部排序(?)
4. 测试样本的个数：因为树是需要构建的，如果测试样本数据量大，需要多次查询，则构建树的时间分摊到每次查询，总体比暴力查询效果好。但是如果仅需要很少次查询，则构建时间占用大部分，和暴力算法效果接近。

leaf_size的影响

leaf_size参数是树结构特有的。leaf_size对算法的性能有以下影响：

1. 构建树的时间：leaf_size较大时，构建时间较短，因为需要构建的内部节点很少
2. 查询时间：较大或较小的leaf_size都会增加查询时间。当leaf_size接近1是，相当于顺序搜索，当接近样本数是，相当于暴力搜索。所以根据样本数和特征数权衡大小，默认设置30
3. 内存空间：随着leaf_size的增大，存储空间减少。