第5章

K近邻




在前几章中，笔者分别介绍了线性回归、逻辑回归及模型的改善与泛化。从这章开始，我们将继续学习下一个新的算法模型——K近邻(KNearest Neighbor, KNN)。什么是K近邻呢?
5.1K近邻思想
某一天，你和几位朋友准备去外面聚餐，但是就晚上吃什么菜一直各持己见。最后，无奈的你提出用少数人服从多数人的原则进行选择。于是你们每个人都将自己想要吃的东西写在了纸条上，最后的统计情况是： 3个人赞成吃火锅、2个人赞成吃炒菜、1个人赞成吃自助。当然，最后你们一致同意按照多数人的意见去吃了火锅。那这个吃火锅和K近邻有什么关系呢？吃火锅确实跟K近邻没关系，但是整个决策的过程却完全体现了K近邻算法的决策过程。
5.2K近邻原理
5.2.1算法原理

如图51所示，黑色样本点为原始的训练数据，并且包含了0、1、2这3个类别(分别为图中不同形状的样本点)。现在得到一个新的样本点(图中黑色倒三角)，需要对其所属类别进行分类。K近邻是如何对其进行分类的呢？


图51K近邻原理示意图


首先K近邻会确定一个K值，然后选择离自己(黑色倒三角样本点)最近的K个样本点，最后根据投票的规则(Majority Voting Rule)确定新样本所属的类别。如图51所示，示例中选择了离三角形样本点最近的14个样本点(正方形4个、圆形7个、星形3个)，并且在图中，离三角形样本点最近的14个样本中最多的为圆形样本，所以K近邻算法将把新样本归类为类别1。
因此，对于K近邻算法的原理可以总结为如下3个步骤： 
1. 确定一个K值
用于选择离自己(三角形样本点)最近的样本数。
2. 选择一种度量距离
用来计算并得到离自己最近的K个样本，示例中采用了应用最为广泛的欧氏距离。
3. 确定一种决策规则 
用来判定新样本所属类别，示例中采用了基于投票的分类规则。
可以看出，K近邻分类的3个步骤其实对应了3个超参数的选择，但是，通常来讲，对于决策规则的选择基本上采用了基于投票的分类规则，因此下面对于这个问题也就不再进行额外讨论了。





5.2.2K值选择
K值的选择会极大程度上影响K近邻的分类结果。如图52所示，可以想象，如果在分类过程中选择较小的K值，则会使模型的训练误差减小从而使模型的泛化误差增大，也就是模型过于复杂而产生了过拟合现象。当选择较大的K值时，将使模型趋于简单，容易发生欠拟合的情况。极端情况下，如果直接将K值设置为样本总数，则无论新输入的样本点位于什么地方，模型都会简单地将它预测为训练样本最多的类别，并且恒定不变，因此，对于K值的选择，依然建议使用第4章所介绍的交叉验证方法进行选择。


图52K值选择图形


5.2.3距离度量
在样本空间中，任意两个样本点之间的距离都可以看作两个样本点之间相似性的度量。两个样本点之间的距离越近，也就意味着这两个样本点越相似。在第10章介绍聚类算法时，同样也会用到样本点间相似性的度量。同时，不同的距离度量方式将会产生不同的距离，进而最后产生不同的分类结果。虽然一般情况下K近邻使用的是欧氏距离，但也可以是其他距离，例如更一般的LP距离或者Minkowski距离李航.统计学习方法［M］.2版.北京： 清华大学出版社,2019.。
设训练样本X={x(1),x(2),…,x(n)}，其中x(i)={x(i)1,x(i)2,…,x(i)m}∈
Rm，即每个样本包含m个特征维度，则Lp距离定义为

Lp(x(i),x(j))=∑mk=1|x(i)k-x(j)k|p1p;p≥1(51)

(1) 当p=1时称为曼哈顿(Manhattan Distance)，即

L1(x(i),x(j))=∑mk=1|x(i)k-x(j)k|(52)

从式(52)可以看出，曼哈顿距离计算的是各个维度之间距离的绝对值累加和。
(2) 当p=2时称为欧氏距离(Euclidean Distance)，即

L2(x(i),x(j))= ∑mk=1|x(i)k-x(j)k|212(53)
(3) 当p=∞时，它是各个坐标距离中的最大值，即

L∞(x(i),x(j))= maxk|x(i)k-x(j)k|(54)

当然，p同样能取其他任意的正整数，然后按照式(51)进行计算即可。
例如现有二维空间的3个样本点x(1)=(0,0)、x(2)=(4,0)、x(3)=(3,3)，则其在不同取值p下，距离样本点x(1)最近邻的点为

L1(x(1),x(2))=|0-4|+|0-0|=4

L1(x(1),x(3))=|0-3|+|0-3|=6

L2(x(1),x(2))=(0-4)2+(0-0)2=4

L2(x(1),x(3))=(0-3)2+(0-3)2≈4.2

L∞(x(1),x(2))=max{|0-4|,|0-0|}=4

L∞(x(1),x(3))=max{|0-3|,|0-3|}=3
(55)
由式(55)可知，当p=1、2、∞时，离样本点x(1)最近的样本点分别是x(2)、x(2)、x(3)。
5.3sklearn接口与示例代码
5.3.1sklearn接口介绍

在正式介绍如何使用sklearn库完成K近邻的建模任务前，笔者先来总结一下sklearn的使用方法，这样更加有利于对后续内容的学习。
根据第2、3、4章中的示例代码可以发现，sklearn在实现各类算法模型时基本上遵循了统一的接口风格，这使我们在刚开始学习的时候很容易入门。总结起来，在sklearn中对于各类模型的使用，基本上遵循着以下3个步骤。
1. 建立模型
这一步通常来讲在对应的路径下导入我们需要用到的模型类，例如可以通过代码来导入一个基于梯度下降算法优化的分类器，代码如下：



from sklearn.linear_model import SGDClassifier





在导入模型类后，需要通过传入模型对应的参数来实例化这个模型，例如可以通过代码实例化一个逻辑回归模型，代码如下：



model = SGDClassifier(loss='log',penalty='l2', alpha=0.5)





同时，由于sklearn在迭代更新中可能会更改一些接口的名称或者位置，所以具体的路径信息可以查看官方的API说明文档PEDREGOSA.scikitlearn: Machine Learning in Python［J］.JMLR 12,2011: 28252830.。
2. 训练模型
在sklearn中，所有模型的训练(或者计算)过程都是通过model.fit()方法来完成的，并且一般情况下需要按实际情况在调用model.fit()时传入相应参数。如果是有监督模型，则一般是model.fit(x,y)，如果是无监督模型，则一般是mode.fit(x)。同时，还可以调用model.score(x,y)来对模型的结果进行评估。
3. 模型预测
在训练好一个模型后，通常要对测试集或者新输入的数据进行预测。在sklearn中一般通过模型类对应的model.predict(x)方法实现，但这也不是绝对的，例如在对数据进行预处理时，调用model.fit()方法在训练集上计算并得到相应的参数后，往往通过model.transform()方法来对测试集(或新数据)进行变换。
总体上来讲，在sklearn中基本上算法模型可以通过上面这3个步骤来完成对模型的建立、训练与预测。
5.3.2K近邻示例代码
从5.2节的分析可知，其实K近邻在分类过程中同之前算法模型不一样，即有一个训练求解参数的过程。这是因为K近邻算法根本就没有可训练的参数，只有3个超参数，而K近邻算法的核心在于如何快速地找到距离任意一个样本最近的K个样本点。当然，最直接的办法就是遍历样本点进行距离计算，但是当样本点达到一定数量级后这种做法显然是行不通的，所以此时可以通过建立KD树(KD Tree)或者Ball树(Ball Tree)来解决这一问题。不过这里暂时不做介绍，先直接通过开源库sklearn实现。
本次示例的数据集仍旧采用第4章中所介绍的手写体分类数据集。同时，在下面示例中笔者将介绍如何通过网格搜索(Grid Search)来快速完成模型的选择，完整代码见Book/Chapter05/01_knn_train.py文件。
1. 模型选择
由于在4.6.1节中已经详细介绍了该数据集的载入和预处理方法，所以这里就不再赘述了。从上面的分析可以得知，K近邻算法有两个(另外一个暂不考虑)超参数，即K值和度量方式P值。假设两者的取值分别为n_neighbors = ［5, 6, 7, 8, 9, 10］、p=［1, 2］，则此时一共有12个备选模型。同时，如果采用5折交叉验证，则一共需要进行60次模型拟合，并且需要3个循环实现。不过好在sklearn中提供了网格搜索的功能可以帮助我们通过4行代码实现上述功能，代码如下： 



from sklearn.neighbors import KNeighborsClassifier

from sklearn.model_selection import GridSearchCV

def model_selection(x_train, y_train):

paras = {'n_neighbors': ［5, 6, 7, 8, 9, 10］, 'p': ［1, 2］}

model = KNeighborsClassifier()

gs = GridSearchCV(model, paras, verbose=2, cv=5)

gs.fit(x_train, y_train)

print('最佳模型:', gs.best_params_, '准确率：',gs.best_score_)





在上述代码中，第4行以字典的形式定义了超参数的取值情况，并且需要注意的是，字典的key必须是类KNeighborsClassifier中参数的名字。其中，类KNeighborsClassifier就是sklearn中所实现的K近邻算法模型，因此，该类也包含了K近邻中最基本的两个参数K值和P值。第5行定义了一个K近邻模型，但值得注意的是此时并没有在定义模型的时候就传入相应的参数，即以KNeighborsClassifier(n_neighbors=2, p=2)的形式(其中n_neighbors就是K值)来实例化这个类。因为在使用网格搜索时，需要将模型作为一个参数传入GridSearchCV类中，同时也需要将模型对应的超参数以字典的形式传入。第6行在实例化GridSearchCV类时便传入了定义的K近邻模型及参数字典，其中verbose用来控制训练过程中输出提示信息的详细程度，cv=5表示在训练过程中使用5折交叉验证。最后，根据传入的训练集，便可以对模型进行训练。
在模型训练完成后，便可以输出最佳模型(超参数组合)，以及此时对应的模型得分，结果如下：



Fitting 5 folds for each of 12 candidates, totalling 60 fits

［CV］ END ...................n_neighbors=5, p=1; total time=   0.0s

［CV］ END ...................n_neighbors=5, p=2; total time=   0.0s

…

…

最佳模型: {'n_neighbors': 5, 'p': 1 准确率：0.971}





从最终的输出结果可知，当K取值为5且P取值为1时所对应的模型最佳。同时，由于模型在进行交叉验证时各个拟合过程之间是相互独立的，为了提高整个过程的训练速度，GridSearchCV还支持以并行的方式进行参数搜索。当在实例化类GridSearchCV时，只需同时指定n_jobs=2即可实现参数的并行搜索，它表示同时使用CPU的两个核进行计算。当然也可以指定为-1，即使用所有的核同时进行计算。
2. 模型测试
在经过网格搜索并得到最优参数组合后，便可以再用完整的训练集重新训练一次模型，然后来评估其在测试集上的泛化误差。当然，在这里也可以直接使用GridSearchCV中的predict()和score()方法来得到测试集的预测结果及对应的准确率，即gs.predict(x_test)和gs.score(x_test,y_test)，代码如下：



def train(x_train, x_test, y_train, y_test):

model = KNeighborsClassifier(5, p=1)

model.fit(x_train, y_train)

y_pred = model.predict(x_test)

print(classification_report(y_test,y_pred))

print("Accuracy: ", model.score(x_test, y_test))#0.963





这样，便能够得到模型在测试集上的泛化误差。
5.3.3小结
在这节内容中，笔者首先通过一个引例介绍了K近邻分类器的主要思想，接着介绍了K值对算法结果的影响，以及介绍了衡量样本间距离的不同度量方式，最后笔者通过开源的sklearn框架介绍了如何建模及使用K近邻分类器，并且同时还总结了sklearn中模型使用的3个步骤及如何使用GridSearch实现超参数的并行搜索。
5.4kd树
在前面几节内容中，笔者分别介绍了K近邻分类器的基本原理及其如何通过开源的sklearn框架实现K近邻的建模。不过到目前为止，还有一个问题没有解决，也就是如何快速地找到当前样本点周围最近的K个样本点。通常来讲，这一问题可以通过kd树来解决，下面开始介绍其具体原理。
5.4.1构造kd树


图53二叉搜索树


kd树(kDimensional Tree)是一种空间划分数据结构，用于组织k维空间中的点，其本质上等同于二叉搜索树。不同的是，在kd树中每个节点存储的并不是一个值，而是一个k维的样本点https://en.wikipedia.org/wiki/Kd_tree.。在二叉搜索树中，任意节点中的值都大于其左子树中的所有值，小于或等于其右子树中的所有值，如图53所示。
在kd树中，所有节点满足类似二叉搜索树的特性，即左子树中所有的样本点均“小于”其父节点中的样本点，而右子树中所有的样本点均“大于”或“等于”其父节点中的样本点，因此可以看出，构造kd树的关键就在于如何定义任意两个k维样本点之间的大小关系。
具体地，在构造kd树时，每一层的节点在划分左右子树时只会循环地选择k维中的一个维度进行比较。例如样本点中一共有x和y两个维度，那么在对根节点进行划分时可以以维度x对左右子树进行划分，接着以维度y对根节点的“孩子”进行左右子树划分，进一步，根节点的“孩子”的“孩子”再以维度x进行左右子树划分，以此循环http://web.stanford.edu/class/cs106l/.。同时，为了使最后得到的是一棵平衡的kd树，所以在kd的构建过程中每次都会选择当前子树中对应维度的中位数作为切分点。
例如现在有样本点［5,7］、［3,8］、［6,2］、［8,5］、［15,6］、［10,4］、［12,13］、［9,10］、［11,14］，那么根据上述规则便可以构造得到如图54所示的kd树。


图54kd树示例


从图54可以看出，对于根节点来讲其左子树中所有样本点的x维度均小于9，其右子树的x维度均大于或等于9。对于根节点的左“孩子”来讲其左子树中所有样本点的y维度均小于7，其右子树中所有样本点的y维度均大于或等于7。当然，对于其他节点也满足类似的特性。同时，根据kd树交替选择特征维度对样本空间进行划分的特性，以图54中的划分方式还可以得到如图55所示的特征空间。


图55kd树特征空间


从图55中可以看出，整个二维平面首先被样本点［9,10］划分成左右两部分(对应图54中的左右子树)，接着左右两部分又各自分别被［5,7］和［15,6］划分成上下两部分，直到划分结束。至此，对于kd树的构造就介绍完了，接下来讲解如何通过kd树来完成搜索任务。
5.4.2最近邻kd树搜索
在正式介绍K近邻(最近的K个样本点)搜索前，笔者先来介绍如何利用kd树进行最近邻搜索。总地来讲，在已知kd树中搜索离给定样本点q最近的样本点时，首先设定一个当前全局最佳点和一个当前全局最短距离，分别用来保存当前离q最近的样本点及对应的距离，然后从根节点开始以类似生成kd树的规则来递归地遍历kd树中的节点，如果当前节点离q的距离小于全局最短距离，则更新全局最佳点和全局最短距离； 如果被搜索点到当前节点划分维度的距离小于全局最短距离，则再递归遍历当前节点另外一个子树，直至整个递归过程结束。具体步骤可以总结为
http://web.stanford.edu/class/cs106l/. 
(1) 设定一个当前全局最佳点和全局最短距离，分别用来保存当前离搜索点最近的样本点和最短距离，初始值分别为空和无穷大。 
(2) 从根节点开始，并设其为当前节点。
(3) 如果当前节点为空，则结束。 
(4) 如果当前节点到被搜索点的距离小于当前全局最短距离，则更新全局最佳点和最短距离。 
(5) 如果被搜索点的划分维度小于当前节点的划分维度，则设当前节点的左“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。反之设当前节点的右“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。 
(6) 如果被搜索点到当前节点划分维度的距离小于全局最短距离，则说明全局最佳点可能存在于当前节点的另外一个子树中，所以设当前节点的另外一个“孩子”为当前节点并执行步骤(3)(4)(5)(6)。 


图56子空间排除原理示意图


递归完成后，此时的全局最佳点就是在kd树中离被搜索点最近的样本点。
这里需要明白的一点是，利用步骤(6)中的规则来判断另外一个子树中是否可能存在全局最佳点的原理如图56所示。
在图56中，右上角为当前全局最佳点，五角星为被搜索点。可以看到，此时的整个空间被下方的样本点划分成了左右两部分(子树)，并且五角星离左子树中样本点的最短距离为五角星到当前划分维度的距离d。显然，如果被搜索点到当前全局最佳点的距离r小于距离d，则此时左子树中就不可能存在更优的全局最佳点。
当然，上述步骤还可以通过一个更清晰的伪代码进行表达，代码如下： 



bestNode, bestDist = None, inf

def NearestNodeSearch(curr_node):

if curr_node == None:

return

if distance(curr_node, q) <bestDist:

bestDist = distance(curr_node, q)

bestNode = curr_node

if q_i<curr_node_i:

NearestNodeSearch(curr_node.left)

else:

NearestNodeSearch(curr_node.right)

if |curr_node_i - q_i| <bestDist:

NearestNodeSearch(curr_node.other)





在上述代码中，q_i和curr_node_i分别表示被搜索点和当前节点的划分维度，curr_node.other表示curr_node.left和curr_node.right中先前未被访问过的子树。
5.4.3最近邻搜索示例
在介绍完最近邻的搜索原理后再来看几个实际的搜索示例，以便对搜索过程有更加清晰的理解。如图57所示，左右两边分别是5.4.1节中所得到的kd树和特征划分空间，同时右图中的五角星为给定的被搜索点q，接下来开始在左边的kd树中搜索离q点最近的样本点。


图57最近邻搜索图


在搜索伊始，全局最佳点和全局最短距离分别为空和无穷大。第1次递归： 此时设根节点［9,10］为当前节点，因满足步骤(4)，即当前节点到被搜索点的距离小于当前全局最短距离，所以将当前最佳点更新为［9,10］，将全局最短距离更新为7.07。接着，由于被搜索点的划分维度10大于当前节点的划分维度9，因此将当前节点的右“孩子”［15,6］设为新的当前节点。第2次递归： 继续执行步骤(4)，由于此时当前节点到被搜索点的距离为5.83，小于全局最短距离，所以将当前最佳点更新为［15,6］，将全局最短距离更新为5.83。进一步，由于被搜索点的划分维度3小于当前节点的划分维度6，因此将当前节点的左“孩子”［10,4］设为新的当前节点。第3次递归： 继续执行步骤(4)，由于此时当前节点到被搜索点的距离为1，小于全局最短距离，所以将当前最佳点更新为［10,4］，将全局最短距离更新为1。此时，由于被搜索点的划分维度10大于或等于当前节点的划分维度10，因此将当前节点的右“孩子”设为新的当前节点，并进入第4次递归。
第4次递归： 由于此时当前节点为空，所以第4次递归结束并返回第3次递归，即此时的当前节点为［10,4］，并继续执行步骤(6)。由于被搜索点［10,3］到当前划分维度x=10的距离为0，小于全局最短距离1，说明全局最佳点可能存在于当前节点的左子树中(此时可以想象假如kd树中存在点［9.9,3］)，所以将当前节点的左“孩子”设为新的当前节点。第5次递归： 由于当前节点为空，所以第5次递归结束并回到第3次递归中。返回第3次递归后，此时的当前节点为［10,4］，并且已执行完步骤(6)，返回第2次递归中。返回第2次递归后，此时的当前节点为［15,6］，并继续执行步骤(6)。由于被搜索点［10,3］到当前划分维度y=6的距离为3，大于全局最短距离，说明节点［15,6］的右子树中不可能存在全局最佳点，此时返回第1次递归中。返回第1次递归后，此时的当前节点为根节点［9,10］，并继续执行步骤(6)。由于被搜索点［10,3］到当前划分维度x=9的距离为1，大于或等于全局最短距离1，所以当前节点的左子树中不可能存在全局最佳点。至此步骤(6)执行结束，即所有的递归过程执行完毕了。此时的全局最佳点中保存的点［10,4］便是kd树中离被搜索点［10,3］最近的样本点。
经过上述步骤后，相信读者对于kd树的搜索过程已经有了清晰的认识。同时，各位读者也可以自己来试着从上述kd树中搜索离［8.9,4］最近的样本点。在搜索的过程中会发现，一开始会从根节点进入左子树，并找到［8,5］为当前全局最佳点，但是当一步步回溯后会发现，原来右子树中的［10,4］才是真正离［8.9,4］最近的样本点。
5.4.4K近邻kd树搜索
在介绍完最近邻的kd树搜索原理后便可以轻松地理解K近邻的kd树搜索过程。需要注意的是，这里的两个K分别表示两种不同的含义，前者表示要搜索并得到离给定点最近的K个样本点，而后者表示的是样本点的维度。
总地来讲，K近邻的搜索过程和最近邻的搜索过程类似，只是需要额外地维护一个大小为K的有序列表。在整个列表中，当前距离被搜索点最近的样本点放在首位，而距离被搜索点最远的样本点放在末尾。具体的搜索过程可以总结为
(1) 设定大小为K的有序列表用来保存当前离搜索点最近的K个样本点。 
(2) 从根节点开始，并设其为当前节点。 
(3) 如果当前节点为空，则结束。 
(4) 如果列表不满，则直接将当前样本插入列表中； 如果列表已满，则判断当前样本到被搜索点的距离是否小于列表最后一个元素到被搜索点的距离，成立则将列表中最后一个元素删除，并插入当前样本(每次插入后仍有序)。
(5) 如果被搜索点的划分维度小于当前节点的划分维度，则设当前节点的左“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。反之设当前节点的右“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。 
(6) 如果列表不满，或者如果被搜索点到当前节点划分维度的距离小于列表中最后一个元素到被搜索点的距离，则设当前节点的另外一个“孩子”为当前节点并执行步骤(3)(4)(5)(6)。 
递归完成后，此时离被搜索点最近的K个样本点就是有序列表中的K个元素。
上述步骤同样可以通过一个更清晰的伪代码进行表达，代码如下： 



KNearestNodes, n = ［］, 0

def KNearestNodeSearch(curr_node):

if curr_node == None:

return

if n < K:

n+=1

KNearestNodes.insert(curr_node)  #插入后保持有序









else:

if distance(curr_node, q) < distance(q,KNearestNodes［-1］):

KNearestNodes.pop()

KNearestNodes.insert(curr_node)  #插入后保持有序

if q_i<curr_node_i:

KNearestNodeSearch(curr_node.left)

else:

KNearestNodeSearch(curr_node.right)

if n < K or | curr_node_i - q_i | <distance(q, KNearestNodes［-1］):

KNearestNodeSearch(curr_node.other)





在上述代码中，KNearestNodes［-1］表示取有序列表中的最后一个元素，q_i和curr_node_i分别表示被搜索点和当前节点的划分维度，curr_node.other表示curr_node.left和curr_node.right中先前未被访问过的子树。
5.4.5K近邻搜索示例
下面以图57中的kd树为例，来搜索离［10,3］最近的3个样本点。
在搜索伊始，有序列表为空，K为3。第一次递归： 此时将根节点［9,10］设为当前节点，因满足步骤(4)中的列表为空的条件，所以直接将根节点加入列表中，即此时KNearestNodes=(［9,10］)。接着，由于被搜索点的划分维度10大于当前节点的划分维度9，因此将当前节点的右“孩子”［15,6］设为新的当前节点。第2次递归： 继续执行步骤(4)，由于此时列表未满，所以直接将当前节点插入列表中，即此时KNearestNodes=(［15,6］, ［9,10］)。进一步，由于被搜索点的划分维度3小于当前节点的划分维度6，因此将当前节点的左“孩子”［10,4］设为新的当前节点。第3次递归： 继续执行步骤(4)，由于此时列表未满，所以直接将当前节点插入列表中，并且由于［10,4］当前离被搜索点最近，所以应该放在列表最前面，即此时KNearestNodes=(［10,4］, ［15,6］, ［9,10］)。进一步，由于被搜索点的划分维度10大于或等于当前节点的划分维度10，所以将当前节点的右“孩子”设为新的当前节点，并进入第4次递归。
第4次递归： 由于此时当前节点为空，所以第4次递归结束并返回第3次递归中，即此时的当前节点为［10,4］，并继续执行步骤(6)。此时列表已满，但由于被搜索点［10,3］到当前划分维度x=10的距离为0，小于被搜索点到有序列表中最后一个样本点距离，说明可能存在一个比有序列表中最后一个元素更佳的样本点，所以将当前节点的左“孩子”设为新的当前节点。第5次递归： 由于当前节点为空，所以第5次递归结束并回到第3次递归中。返回第3次递归后，此时的当前节点为［10,4］，并且已执行完步骤(6)，返回第2次递归中。返回第2次递归后，此时的当前节点为［15,6］，并继续执行步骤(6)。此时列表已满，但由于被搜索点［10,3］到当前划分维度y=6的距离为3，小于被搜索点到［9,10］的距离7.07，说明在当前节点［15,6］的右子树中可能存在一个比［9,10］更佳的样本点，所以将［15,6］的右“孩子”［12,13］设为新的当前节点。第6次递归： 此时列表已满，并且由于当前节点到被搜索点的距离10.19大于被搜索点到［9,10］的距离，所以继续执行步骤(5)。由于被搜索点的划分维度10小于当前节点的划分维度12，所以将［11,14］设为新的当前节点，并进入第7次递归。
第7次递归： 此时列表已满，并且由于当前节点到被搜索点的距离11.04大于被搜索点到［9,10］的距离，所以继续执行步骤(5)。由于被搜索点的划分维度3小于当前节点的划分维度14，所以将［11,14］的左“孩子”设为新的当前节点。第8次递归： 由于此时当前节点为空，所以第8次递归结束并返回第7次递归中，即此时的当前节点为［11,14］，并继续执行步骤(6)。此时列表已满，并且由于被搜索点［10,3］到当前划分维度y=14的距离为11，大于被搜索点到有序列表中最后一个样本点距离，所以第7次递归结束并回到第6次递归。
返回第6次递归后，此时的当前节点为［12,13］，继续执行步骤(6)。此时列表已满，并且由于被搜索点［10,3］到当前划分维度x=12的距离为2，小于被搜索点到有序列表中最后一个样本点的距离，说明当前节点［12,13］的右子树中存在比［9,10］更近的点(可以想象假设存在点［12.1,6.1］)，所以将［12,13］的右“孩子”设为新的当前节点。第9次递归： 由于此时当前节点为空，所以第9次递归结束并返回第6次递归中，即此时的当前节点为［12,13］，并且已经执行完步骤(6)，进而返回第2次递归。返回第2次递归后，此时的当前节点为［15,6］，并且已执行完步骤(6)，进而返回第1次递归中。
返回第1次递归后，此时的当前节点为［9,10］，继续执行步骤(6)。此时列表已满，但由于被搜索点［10,3］到当前划分维度x=9的距离为1，小于被搜索点到有序列表中最后一个样本点的距离，说明当前节点［9,10］的左子树中存在比［9,10］更近的点(从图57中一眼便能看出，例如点［8,5］)，所以将［5,7］设为新的当前节点。第10次递归： 此时列表已满，但由于当前节点到被搜索点的距离6.4小于被搜索点到有序列表中最后一个样本点［9,10］的距离7.07，因此更新KNearestNodes=(［10,4］, ［15,6］, ［5,7］)，并继续执行步骤(5)。由于被搜索点的划分维度3小于当前节点的划分维度7，所以将［8,5］设为新的当前节点，并进入第11次递归。
第11次递归： 此时列表已满，但由于当前节点到被搜索点的距离2.83小于被搜索点到有序列表中最后一个样本点［5,7］的距离6.4，因此更新KNearestNodes=(［10,4］, ［8,5］, ［15,6］)，并继续执行步骤(5)。由于被搜索点的划分维度10大于当前节点的划分维度8，所以将［8,5］的右“孩子”设为新的当前节点。第12次递归： 由于此时当前节点为空，所以第12次递归结束并返回第11次递归中，即此时的当前节点为［8,5］，并继续执行步骤(6)。此时列表已满，但由于被搜索点［10,3］到当前划分维度x=8的距离为2，小于被搜索点到有序列表中最后一个样本点的距离，所以将［6,3］设为新的当前节点，并进入第13次递归。
第13次递归： 此时列表已满，但由于当前节点到被搜索点的距离4.0小于被搜索点到有序列表中最后一个样本点［15,6］的距离5.83，因此更新KNearestNodes=(［10,4］, ［8,5］, ［6,3］)，并继续执行步骤(5)。由于被搜索点的划分维度3大于或等于当前节点的划分维度3，所以将［6,3］的右“孩子”设为新的当前节点。第14次递归： 由于此时当前节点为空，所以第14次递归结束并返回第13次递归中，即此时的当前节点为［6,3］，并继续执行步骤(6)。此时列表已满，但由于被搜索点［10,3］到当前划分维度y=3的距离为0，小于被搜索点到有序列表中最后一个样本点的距离，说明［6,3］的左子树中存在比［6,3］更近的点(可以想象假设存在点［7,2.9］)，所以将［6,3］的左“孩子”设为新的当前节点，并进入第15次递归。
第15次递归： 由于此时当前节点为空，所以第15次递归结束并返回第13次递归中，即此时的当前节点为［6,3］，并且已经执行完步骤(6)并进一步返回第11次递归中。返回第11次递归后，此时的当前节点为［8,5］，并且已经执行完步骤(6)并进一步返回第10次递归中。返回第10次递归后，当前节点为［5,7］，继续执行步骤(6)。由于此时列表已满，并且被搜索点［10,3］到当前划分维度y=7的距离4大于或等于被搜索点到有序列表中最后一个样本点［6,3］的距离，所以［5,7］的右子树中不可能存在比［6,3］更近的点，故返回第1次递归。
在返回第1次递归后，此时的当前节点为［9,10］，并且已执行完步骤(6)，即所有的递归过程结束。此时有序列表中的元素便为kd树中离被搜索点［10,3］最近的3个样本点，即KNearestNodes=(［10,4］, ［8,5］, ［6,3］)。整个递归过程的执行顺序如图58所示。


图58K近邻搜索递归过程的执行顺序


至此，对于K近邻算法的原理就介绍完了。
5.4.6小结
在本节中，笔者首先介绍了kd树的基本原理，以及如何构造一棵kd树，接着介绍了如何通过kd树来搜索离给定点最近的样本点，并通过一个实际的搜索示例进行了详细介绍，最后介绍了如何在最近邻的基础上，在kd树中搜索离给定点最近的K个样本点，即K最近邻搜索。
总结一下，在本章中笔者首先介绍了K近邻算法的主要思想及其原理，包括K值选择和距离的度量方式等，接着简单地总结了sklearn框架接口的设计风格及通用的建模步骤，然后介绍了如何通过sklearn建立完整的K近邻分类器，包括模型训练、模型选择、并行搜索和交叉验证等，最后详细介绍了如何通过kd树实现K近邻中K近邻样本点的搜索。