【机器学习算法】【2】--K近邻算法

K最近邻(k-Nearest Neighbor，KNN)，是一种常用于分类的算法，是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是：如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别，即近朱者赤，近墨者黑。显然，对当前待分类样本的分类，需要大量已知分类的样本的支持，因此KNN是一种有监督学习算法。

---

k-最近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概念。

一、基于实例的学习

1. 已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。
   从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。
2. 基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。
3. 基于实例方法的不足
   • 分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。
   • 当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。

二、k-最近邻法算法简介

        K最近邻(K-Nearest Neighbor,KNN)算法，是著名的模式识别统计学方法，在机器学习分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算法之一，也是基于实例的学习方法中最基本的，又是最好的文本分类算法之一。

       如果你要了解一个人，可以从他k个最亲近的朋友去推测他是什么样的人。k是一个超参数。k表示最近的k个邻居，是表示个数，不是表示距离。

超参数k的作用：

                       

                        左图中“?”处绿点是一个待分类的样本，
                        也就是说“?”到底是红色三角形，还是
                        蓝色正方形，暂时还不知道。
                        若令k=3，则“?”被分类为红色三角形。
                        若令k=5，则“?”被分类蓝色正方形。

 

超参数k对算法的影响：

      k越大，就需要找出越多的邻居，计算量越大。K越大，则相当于做分类时的样本数越多，所以统计意义会更强。但是，如果这k个邻居离待分类样本太远的话，则统计意义就反而变弱了。所以，实践中不宜把k值取得太大。

K值的选择：（借鉴李航--统计学习方法）

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

K值较小：就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小， K值的减小就意味着整体模型变得复杂，容易发生过拟合； 

K值较大：就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。k很大，那么可以减少干扰数据的影响，但是此时就导致了系统性偏差（K值太小会造成过度拟合），比如如果取k为总的训练数据数，那么每次投票肯定都是训练数据中多的类别胜利。显然训练数据的系统性偏差会影响结果。 

通常情况下，我们需要对 k 经过多种尝试，来决定到底使用多大的 k 来作为最终参数。k通常会在3～10直接取值，或者是k等于训练数据的平方根。比如15个数据，可能会取k=4。 

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

三、K近邻算法的原理

首先，K近邻算法的推导实在是过于简单，这里就只描述下算法的设计流程。

kNN分类算法的具体步骤如下：
1）计算待分类样本点与所有已标注样本点之间的距离(如果样本多将非常耗时、耗空间)
2）按照距离从小到大排序(对于每一个待分类的样本点，都要排序。耗时、耗空间)
3）选取与待分类样本点距离最小的k个点
4）确定前k个点中，每个类别的出现次数
5）返回次数最高的那个类别

这里要注意，距离的计算方法。

由于sklearn中有现成的算法，这里根据算法中的参数来进行说明，我们使用sklearn.neighbors.KNeighborsClassifier就可以是实现上小结，我们实现的k-近邻算法。

KNeighborsClassifier函数一共有8个参数

class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, 

metric='minkowski', metric_params=None, n_jobs=1, **kwargs)

KNneighborsClassifier参数说明：

• n_neighbors：默认为5，就是k-NN的k的值，选取最近的k个点。
• weights：默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
• algorithm：快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。
• leaf_size：默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
• metric：用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
• p：距离度量公式。在上小结，我们使用欧氏距离公式进行距离度量。除此之外，还有其他的度量方法，例如曼哈顿距离。这个参数默认为2，也就是默认使用欧式距离公式进行距离度量。也可以设置为1，使用曼哈顿距离公式进行距离度量。
• metric_params：距离公式的其他关键参数，这个可以不管，使用默认的None即可。
• n_jobs：并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。

闵可夫斯基距离：minkowski

闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：

那么，闵可夫斯基距离定义为：

该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：

绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。

其中，在计算距离的过程中，有几下几点需要特别注意：

• 对于类别性变量，在计算之前需要先进行独热编码，转化为距离计算可以理解的数字型变量
• 对于连续性变量，可以进行无量纲化的处理。

四、KNN算法实现

4.1 KNN算法蛮力实现

首先我们看看最想当然的方式。

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

　  既然蛮力实现在特征多，样本多的时候很有局限性，那么我们有没有其他的好办法呢？有！这里我们讲解两种办法，一个是KD树实现，一个是球树实现。

4.2 KD树实现原理

       KD树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是KD树，建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树，注意这里的K和KNN中的K的意思不同。KNN中的K代表特征输出类别，KD树中的K代表样本特征的维数。为了防止混淆，后面我们称特征维数为n。

　　KD树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测

KD树的建立：

　  我们首先来看建树的方法。KD树建树采用的是从m个样本的n维特征中，分别计算n个特征的取值的方差，用方差最大的第k维特征来作为根节点。对于这个特征，我们选择特征的取值的中位数对应的样本作为划分点，对于所有第k维特征的取值小于的样本，我们划入左子树，对于第k维特征的取值大于等于nkvnkv的样本，我们划入右子树，对于左子树和右子树，我们采用和刚才同样的办法来找方差最大的特征来做根节点，递归的生成KD树。

比如我们有二维样本6个，{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，构建kd树的具体步骤为：

　　　1）找到划分的特征。6个数据点在x，y维度上的数据方差分别为6.97，5.37，所以在x轴上方差更大，用第1维特征建树。

　　　2）确定划分点（7,2）。根据x维上的值将数据排序，6个数据的中值(所谓中值，即中间大小的值)为7，所以划分点的数据是（7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于：划分点维度的直线x=7；（很显然，中位数为6 ，这里选择（5,4）或者(7,2)都是可以的。这种情况任选一个即可）

　　　3）确定左子空间和右子空间。 分割超平面x=7将整个空间分为两部分：x<=7的部分为左子空间，包含3个节点={(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点={(9,6)，(8,1)}。

　　　4）用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6)，(8,1)}。最终得到KD树。

　　　　最后得到的KD树如下：

KD树搜索最近邻

      当我们生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目标点，我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。

　  从上面的描述可以看出，KD树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

　 我们用3.1建立的KD树，来看对点(2,4.5)找最近邻的过程。

　 先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<(7,2)，(5,4)，(4,7)>，但 （4,7）与目标查找点的距离为3.202，而（5,4）与查找点之间的距离为3.041，所以（5,4）为查询点的最近点； 以（2，4.5）为圆心，以3.041为半径作圆，如下图所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找，也就是将（2,3）节点加入搜索路径中得<(7,2)，(2,3)>；于是接着搜索至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5；回溯查找至（5,4），直到最后回溯到根结点（7,2）的时候，以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图所示。至此，搜索路径回溯完，返回最近邻点（2,3），最近距离1.5。

对应的图如下：

4.3 球树实现原理

       KD树算法虽然提高了KNN搜索的效率，但是在某些时候效率并不高，比如当处理不均匀分布的数据集时,不管是近似方形，还是矩形，甚至正方形，都不是最好的使用形状，因为他们都有角。一个例子如下图：

         如果黑色的实例点离目标点星点再远一点，那么虚线圆会如红线所示那样扩大，导致与左上方矩形的右下角相交，既然相 交了，那么就要检查这个左上方矩形，而实际上，最近的点离星点的距离很近，检查左上方矩形区域已是多余。于此我们看见，KD树把二维平面划分成一个一个矩形，但矩形区域的角却是个难以处理的问题。

　　为了优化超矩形体导致的搜索效率的问题，牛人们引入了球树，这种结构可以优化上面的这种问题。

　　我们现在来看看球树建树和搜索最近邻的算法。

球树的建立

球树，顾名思义，就是每个分割块都是超球体，而不是KD树里面的超矩形体。

我们看看具体的建树流程：

　　1) 先构建一个超球体，这个超球体是可以包含所有样本的最小球体。

　　2) 从球中选择一个离球的中心最远的点，然后选择第二个点离第一个点最远，将球中所有的点分配到离这两个聚类中心最近的一个上，然后计算每个聚类的中心，以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体，和KD树里面的左右子树对应。（PS:这里选择两个点后，就以这两个点来聚类，所以先确定的是以这两个点为中心来计算其他点到该中心的距离。当所有点都确定自己的中心后，再重新计算一次该超球体的半径和球心。）

　　　　3)对于这两个子超球体，递归执行步骤2). 最终得到了一个球树。

　　　　可以看出KD树和球树类似，主要区别在于球树得到的是节点样本组成的最小超球体，而KD得到的是节点样本组成的超矩形体，这个超球体要与对应的KD树的超矩形体小，这样在做最近邻搜索的时候，可以避免一些无谓的搜索。

五、KNN算法小结

　　KNN算法是很基本的机器学习算法了，它非常容易学习，在维度很高的时候也有很好的分类效率，因此运用也很广泛，这里总结下KNN的优缺点。

　　KNN的主要优点有：

　　1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归

　　2） 可用于非线性分类

　　3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)

　　4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

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

　　6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

　　KNN的主要缺点有：

　　1）计算量大，尤其是特征数非常多的时候

　　2）样本不平衡的时候，对稀有类别的预测准确率低

　　3）KD树，球树之类的模型建立需要大量的内存

　　4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

　　5）相比决策树模型，KNN模型可解释性不强

六、适用场合

1. kNN是一个有监督算法，需要有标注好的样本。
2. 从算法复杂度的角度来看，更适合特征个数较少，已标注样本数量不是过多的场合。
3. kNN的可解释性较差。无法给出决策树那样的规则，也无法象逻辑回归那样对数据给出整齐的划分。事实上，kNN更适合处理一些分类规则相对复杂的问题。

参考资料：

https://blog.csdn.net/qq_36330643/article/details/77532161

http://cuijiahua.com/blog/2017/11/ml_1_knn.html

https://www.cnblogs.com/pinard/p/6061661.html