第5.4节 kd树原理与K近邻搜索
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果你觉得本期内容对你所有帮助欢迎点个赞、关个注、下回更新不迷路。为方便大家提问交流，专栏订阅用户可微信私信掌柜“MLWM”进入专属答疑群。
5.4 kd树 5.4.1 构造kd树 5.4.2 最近邻kd树搜索 5.4.3 最近邻搜索示例 5.4.4 K近邻kd树搜索 5.4.5 K 近邻搜索示例 5.4.6 小结
5.4 kd树
在前面几节内容中，笔者分别介绍了近邻分类器的基本原理及其如何通过开源的sklearn框架实现近邻的建模。不过到目前为止，还有一个问题没有解决，也就是如何快速地找到当前样本点周围最近的个样本点。通常来讲，这一问题可以通过kd树来解决，下面开始介绍其具体原理。
5.4.1 构造kd树
kd树（k-Dimensional Tree）是一种空间划分数据结构，用于组织维空间中的点，其本质上等同于二叉搜索树。不同的是，在kd树中每个节点存储的并不是一个值，而是一个维的样本点[1]。在二叉搜索树中，任意节点中的值都大于其左子树中的所有值，小于或等于其右子树中的所有值，如图5-3所示。
在kd树中，所有节点满足类似二叉搜索树的特性，即左子树中所有的样本点均“小于”其父节点中的样本点，而右子树中所有的样本点均“大于”或“等于”其父节点中的样本点，因此可以看出，构造kd树的关键就在于如何定义任意两个维样本点之间的大小关系。
具体地，在构造kd树时，每一层的节点在划分左右子树时只会循环地选择维中的一个维度进行比较。例如样本点中一共有和两个维度，那么在对根节点进行划分时可以以维度对左右子树进行划分，接着以维度对根节点的“孩子”进行左右子树划分，进一步，根节点的“孩子”的“孩子”再以维度进行左右子树划分，以此循环[2]。同时，为了使最后得到的是一棵平衡的kd树，所以在kd的构建过程中每次都会选择当前子树中对应维度的中位数作为切分点。
例如现在有样本点[5,7]、[3,8]、[6,3]、[8,5]、[15,6]、[10,4]、[12,13]、[9,10]、[11,14]，那么根据上述规则便可以构造得到如图5-4所示的kd树。
从图5-4可以看出，对于根节点来讲其左子树中所有样本点的维度均小于9，其右子树的维度均大于或等于9。对于根节点的左“孩子”来讲其左子树中所有样本点的维度均小于7，其右子树中所有样本点的维度均大于或等于7。当然，对于其他节点也满足类似的特性。同时，根据kd树交替选择特征维度对样本空间进行划分的特性，以图5-4中的划分方式还可以得到如图5-5所示的特征空间。
从图5-5中可以看出，整个二维平面首先被样本点[9,10]划分成左右两部分（对应图5-4中的左右子树），接着左右两部分又各自分别被[5,7]和[15,6]划分成上下两部分，直到划分结束。至此，对于kd树的构造就介绍完了，接下来讲解如何通过kd树来完成搜索任务。
5.4.2 最近邻kd树搜索
在正式介绍近邻（最近的个样本点）搜索前，笔者先来介绍如何利用kd树进行最近邻搜索。总地来讲，在已知kd树中搜索离给定样本点最近的样本点时，首先设定一个当前全局最佳点和一个当前全局最短距离，分别用来保存当前离最近的样本点及对应的距离，然后从根节点开始以类似生成kd树的规则来递归地遍历kd树中的节点，如果当前节点离的距离小于全局最短距离，则更新全局最佳点和全局最短距离；如果被搜索点到当前节点划分维度的距离小于全局最短距离，则再递归遍历当前节点另外一个子树，直至整个递归过程结束。具体步骤可以总结为[2]
(1) 设定一个当前全局最佳点和全局最短距离，分别用来保存当前离搜索点最近的样本点和最短距离，初始值分别为空和无穷大。
(2) 从根节点开始，并设其为当前节点。
(3) 如果当前节点为空，则结束。
(4) 如果当前节点到被搜索点的距离小于当前全局最短距离，则更新全局最佳点和最短距离。
(5) 如果被搜索点的划分维度小于当前节点的划分维度，则设当前节点的左“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。反之设当前节点的右“孩子”为新的当前节点并执行步骤(3)(4)(5)(6)。
(6) 如果被搜索点到当前节点划分维度的距离小于全局最短距离，则说明全局最佳点可能存在于当前节点的另外一个子树中，所以设当前节点的另外一个“孩子”为当前节点并执行步骤(3)(4)(5)(6)。
递归完成后，此时的全局最佳点就是在kd树中离被搜索点最近的样本点。
这里需要明白的一点是，利用步骤(6)中的规则来判断另外一个子树中是否可能存在全局最佳点的原理如图5-6所示。
在图5-6中，右上角为当前全局最佳点，五角星为被搜索点。可以看到，此时的整个空间被下方的样本点划分成了左右两部分（子树），并且五角星离左子树中样本点的最短距离为五角星到当前划分维度的距离。显然，如果被搜索点到当前全局最佳点的距离小于距离，则此时左子树中就不可能存在更优的全局最佳点。
当然，上述步骤还可以通过一个更清晰的伪代码进行表达，代码如下：
1 bestNode, bestDist = None, inf
2 def NearestNodeSearch(curr_node):
3 if curr_node == None:
4 return
5 if distance(curr_node, bestNode) <bestDist:
6 bestDist = distance(curr_node, bestNode)
7 bestNode = curr_node
8 if q_i < curr_node_i:
9 NearestNodeSearch(curr_node.left)
10 else:
11 NearestNodeSearch(curr_node.right)
12 if |curr_node_i - q_i| < bestDist:
13 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树和特征划分空间，同时右图中的五角星为给定的被搜索点，接下来开始在左边的kd树中搜索离点最近的样本点。