闵可夫斯基距离
铝塑板安装方法-6月英文缩写
2023年2月20日发(作者：探索创新)机器学习算法（2）之K近邻算法
K最近邻(k-NearestNeighbor，KNN)，是⼀种常⽤于分类的算法，是有成熟理论⽀撑的、较为简单的经典机器学习算法之⼀。该⽅法的基
本思路是：如果⼀个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类
别，即近朱者⾚，近墨者⿊。显然，对当前待分类样本的分类，需要⼤量已知分类的样本的⽀持，因此KNN是⼀种有监督学习算法。
k-最近邻算法是基于实例的学习⽅法中最基本的，先介绍基于实例学习的相关概念。
⼀、基于实例的学习
1.已知⼀系列的训练样例，很多学习⽅法为⽬标函数建⽴起明确的⼀般化描述；但与此不同，基于实例的学习⽅法只是简单地把训练样
例存储起来。
从这些实例中泛化的⼯作被推迟到必须分类新的实例时。每当学习器遇到⼀个新的查询实例，它分析这个新实例与以前存储的实例的
关系，并据此把⼀个⽬标函数值赋给新实例。
2.基于实例的⽅法可以为不同的待分类查询实例建⽴不同的⽬标函数逼近。事实上，很多技术只建⽴⽬标函数的局部逼近，将其应⽤于
与新查询实例邻近的实例，⽽从不建⽴在整个实例空间上都表现良好的逼近。当⽬标函数很复杂，但它可⽤不太复杂的局部逼近描述
时，这样做有显著的优势。
3.基于实例⽅法的不⾜
1.分类新实例的开销可能很⼤。这是因为⼏乎所有的计算都发⽣在分类时，⽽不是在第⼀次遇到训练样例时。所以，如何有效地索
引训练样例，以减少查询时所需计算是⼀个重要的实践问题。
2.当从存储器中检索相似的训练样例时，它们⼀般考虑实例的所有属性。如果⽬标概念仅依赖于很多属性中的⼏个时，那么真正
最“相似”的实例之间很可能相距甚远。
⼆、k-最近邻法算法简介
K最近邻(K-NearestNeighbor,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中有现成的算法，这⾥根据算法中的参数来进⾏说明，我们使⽤borsClassifier就可以是实现上⼩
结，我们实现的k-近邻算法。
KNeighborsClassifier函数⼀共有8个参数
borsClassifier(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时效率⾼。balltree是为了克服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
闵可夫斯基距离（Minkowskidistance）是衡量数值点之间距离的⼀种⾮常常见的⽅法，假设数值点P和Q坐标如下：
那么，闵可夫斯基距离定义为：
该距离最常⽤的p是2和1,前者是欧⼏⾥得距离（Euclideandistance），后者是曼哈顿距离（Manhattandistance）。假设在曼哈顿
街区乘坐出租车从P点到Q点，⽩⾊表⽰⾼楼⼤厦，灰⾊表⽰街道：
绿⾊的斜线表⽰欧⼏⾥得距离，在现实中是不可能的。其他三条折线表⽰了曼哈顿距离，这三条折线的长度是相等的。
其中，在计算距离的过程中，有⼏下⼏点需要特别注意：
对于类别性变量，在计算之前需要先进⾏独热编码，转化为距离计算可以理解的数字型变量
对于连续性变量，可以进⾏⽆量纲化的处理。
四、KNN算法实现
4.1KNN算法蛮⼒实现
⾸先我们看看最想当然的⽅式。
既然我们要找到k个最近的邻居来做预测，那么我们只需要计算预测样本和所有训练集中的样本的距离，然后计算出最⼩的k个距离即
可，接着多数表决，很容易做出预测。这个⽅法的确简单直接，在样本量少，样本特征少的时候有效。但是在实际运⽤中很多时候⽤不上，
为什么呢？因为我们经常碰到样本的特征数有上千以上，样本量有⼏⼗万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很
成问题。因此，这个⽅法我们⼀般称之为蛮⼒实现。⽐较适合于少量样本的简单模型的时候⽤。
既然蛮⼒实现在特征多，样本多的时候很有局限性，那么我们有没有其他的好办法呢？有！这⾥我们讲解两种办法，⼀个是KD树实现，
⼀个是球树实现。
4.2KD树实现原理
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），形成搜索路径，但（4,7）与⽬标查找点的距离为3.202，⽽（5,4）与查找点之间的距离为
3.041，所以（5,4）为查询点的最近点；以（2，4.5）为圆⼼，以3.041为半径作圆，如下图所⽰。可见该圆和y=4超平⾯交割，所以
需要进⼊（5,4）左⼦空间进⾏查找，也就是将（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模型可解释性不强
六、适⽤场合
是⼀个有监督算法，需要有标注好的样本。
2.从算法复杂度的⾓度来看，更适合特征个数较少，已标注样本数量不是过多的场合。
的可解释性较差。⽆法给出决策树那样的规则，也⽆法象逻辑回归那样对数据给出整齐的划分。事实上，kNN更适合处理⼀些分类
规则相对复杂的问题。
参考资料：