K最近邻(k-Nearest Neighbor，KNN)，是⼀种常⽤于分类的算法，是有成熟理论⽀撑的、较为简单的经典机器学习算法之⼀。该⽅法的基本思路是：如果⼀个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类别，即近朱者⾚，近墨者⿊。显然，对当前待分类样本的分类，需要⼤量已知分类的样本的⽀持，因此KNN是⼀种有监督学习算法。 k-最近邻算法是基于实例的学习⽅法中最基本的，先介绍基于实例学习的相关概念。 ⼀、基于实例的学习
1. 已知⼀系列的训练样例，很多学习⽅法为⽬标函数建⽴起明确的⼀般化描述；但与此不同，基于实例的学习⽅法只是简单地把训练样 例存储起来。
从这些实例中泛化的⼯作被推迟到必须分类新的实例时。每当学习器遇到⼀个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把⼀个⽬标函数值赋给新实例。
2. 基于实例的⽅法可以为不同的待分类查询实例建⽴不同的⽬标函数逼近。事实上，很多技术只建⽴⽬标函数的局部逼近，将其应⽤于
与新查询实例邻近的实例，⽽从不建⽴在整个实例空间上都表现良好的逼近。当⽬标函数很复杂，但它可⽤不太复杂的局部逼近描述时，这样做有显著的优势。
3. 基于实例⽅法的不⾜
1. 分类新实例的开销可能很⼤。这是因为⼏乎所有的计算都发⽣在分类时，⽽不是在第⼀次遇到训练样例时。所以，如何有效地索
引训练样例，以减少查询时所需计算是⼀个重要的实践问题。
2. 当从存储器中检索相似的训练样例时，它们⼀般考虑实例的所有属性。如果⽬标概念仅依赖于很多属性中的⼏个时，那么真正
最“相似”的实例之间很可能相距甚远。
⼆、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中有现成的算法，这⾥根据算法中的参数来进⾏说明，我们使⽤ighbors.KNeighborsClassifier就可以是实现上⼩结，我们实现的k-近邻算法。武警成都医院
KNeighborsClassifier函数⼀共有8个参数
ighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1, **kwargs)
021导弹艇KNneighborsClassifier参数说明：
闵可夫斯基距离：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树⾥⾯的超矩形体。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议