**导语**：在上一篇《[kd 树算法之思路篇](https://www.joinquant.com/post/2627)》中，我们介绍了如何用二叉树格式记录空间内的距离，并以其为依据进行高效的索引。在本篇文章中，我们将详细介绍 kd 树的构造以及 kd 树上的 kNN 算法。 $ $ ``` 作者：肖睿 编辑：宏观经济算命师 本文由JoinQuant量化课堂推出，本文的难度属于进阶（下），深度为 level-1 ``` 阅读本文前请掌握 [kNN](https://www.joinquant.com/post/2227?f=study&m=math)（**level-1**）的知识。 $ $ #### **kd 树的结构** kd树是一个二叉树结构，它的每一个节点记载了【特征坐标，切分轴，指向左枝的指针，指向右枝的指针】。 其中，特征坐标是线性空间 $\mathbb R^n$ 中的一个点 $(x_1,x_2,…,x_n)$。 切分轴由一个整数 $r$ 表示，这里 $1\leq r\leq n$，是我们在 $n$ 维空间中沿第 $r$ 维进行一次分割。 节点的左枝和右枝分别都是 kd 树，并且满足：如果 $y$ 是左枝的一个特征坐标，那么 $y_r\leq x_r$；并且如果 $z$ 是右枝的一个特征坐标，那么 $z_r\geq x_r$。 给定一个数据样本集 $S\subseteq R^n$ 和切分轴 $r$，以下递归算法将构建一个基于该数据集的 kd 树，每一次循环制作一个节点： $-$ 如果 $|S|=1$，记录 $S$ 中唯一的一个点为当前节点的特征数据，并且不设左枝和右枝。（$|S|$ 指集合 $S$ 中元素的数量） $-$ 如果 $|S|>1$： $\qquad \bullet$ 将 $S$ 内所有点按照第 $r$ 个坐标的大小进行排序； $\qquad \bullet$ 选出该排列后的中位元素（如果一共有偶数个元素，则选择中位左边或右边的元素，左或右并无影响），作为当前节点的特征坐$\qquad \ \ \ $标，并且记录切分轴 $r$； $\qquad \bullet$ 将 $S_L$ 设为在 $S$ 中所有排列在中位元素之前的元素； $S_R$ 设为在 $S$ 中所有排列在中位元素后的元素； $\qquad \bullet$ 当前节点的左枝设为以 $S_L$ 为数据集并且 $r$ 为切分轴制作出的 kd 树；当前节点的右枝设为以 $S_R$ 为数据集并且 $r$ 为切分轴制作出$\qquad \ \ \ $的 kd 树。再设 $r \leftarrow (r+1) \mod n$。（这里，我们想轮流沿着每一个维度进行分割；$\mod n$ 是因为一共有 $n$ 个维度，在$\qquad \ \ \ $沿着最后一个维度进行分割之后再重新回到第一个维度。） $ $ #### **构造 kd 树的例子** 上面抽象的定义和算法确实是很不好理解，举一个例子会清楚很多。首先随机在 $\mathbb R^2$ 中随机生成 13 个点作为我们的数据集。起始的切分轴 $r=0$；这里 $r=0$ 对应 $x$ 轴，而 $r=1$ 对应 $y$ 轴。 ![1.png][1] 首先先沿 $x$ 坐标进行切分，我们选出 $x$ 坐标的中位点，获取最根部节点的坐标 ![树1.png][2] 并且按照该点的x坐标将空间进行切分，所有 $x$ 坐标小于 $6.27$ 的数据用于构建左枝，$x$坐标大于 $6.27$ 的点用于构建右枝。 ![2.png][3] 在下一步中 $r=0+1=1 \mod 2$ 对应 $y$ 轴，左右两边再按照 $y$ 轴的排序进行切分，中位点记载于左右枝的节点。得到下面的树，左边的$x$ 是指这该层的节点都是沿 $x$ 轴进行分割的。 ![树2.png][4] 空间的切分如下 ![3.png][5] 下一步中 $r\equiv 1+1\equiv 0 \mod 2$，对应 $x$ 轴，所以下面再按照 $x$ 坐标进行排序和切分，有 ![树3.png][6] ![4.png][7] 最后每一部分都只剩一个点，将他们记在最底部的节点中。因为不再有未被记录的点，所以不再进行切分。 ![树4.png][8] ![5.png][9] 就此完成了 kd 树的构造。 $ $ #### **kd 树上的 kNN 算法** 给定一个构建于一个样本集的 kd 树，下面的算法可以寻找距离某个点 $p$ 最近的 $k$ 个样本。 零、设 $L$ 为一个有 $k$ 个空位的列表，用于保存已搜寻到的最近点。 一、根据 $p$ 的坐标值和每个节点的切分向下搜索（也就是说，如果树的节点是按照 $x_r=a$ 进行切分，并且 $p$ 的 $r$ 坐标小于 $a$，则向左枝$\ \ \ \ \ \ $进行搜索；反之则走右枝）。 二、当达到一个底部节点时，将其标记为访问过。如果 $L$ 里不足 $k$ 个点，则将当前节点的特征坐标加入 $L$ ；如果 $L$ 不为空并且当前节点$\ \ \ \ \ \ $的特征与 $p$ 的距离小于 $L$ 里最长的距离，则用当前特征替换掉 $L$ 中离 $p$ 最远的点。 三、如果当前节点不是整棵树最顶端节点，执行 (a)；反之，输出 $L$，算法完成。 $\qquad a.$ 向上爬一个节点。如果当前（向上爬之后的）节点未曾被访问过，将其标记为被访问过，然后执行 (1) 和 (2)；如果当前节点被访$\qquad \ \ \ \ $问过，再次执行 (a)。 $\qquad \qquad 1.$ 如果此时 $L$ 里不足 $k$ 个点，则将节点特征加入 $L$；如果 $L$ 中已满 $k$ 个点，且当前节点与 $p$ 的距离小于 $L$ 里最长的距离，$\qquad \ \ \ \qquad\ $则用节点特征替换掉 $L$ 中离最远的点。 $\qquad \qquad 2.$ 计算 $p$ 和当前节点切分线的距离。如果该距离大于等于 $L$ 中距离 $p$ 最远的距离**并且** $L$ 中已有 $k$ 个点，则在切分线另一边不会有更近的点，执行 $\qquad \ \ \ \qquad\ $(三)；如果该距离小于 $L$ 中最远的距离**或者** $L$ 中不足 $k$ 个点，则切分线另一边可能有更近的点，因此在当前节点的另一个枝从 (一) 开始执行。 $ $ #### **啊呃… 被这算法噎住了，赶紧喝一口下面的例子** 设我们想查询的点为 $p=(-1,-5)$，设距离函数是普通的 $L_2$ 距离，我们想找距离问题点最近的 $k=3$ 个点。如下： ![6.png][10] 首先执行 (一)，我们按照切分找到最底部节点。首先，我们在顶部开始 ![树5.png][11] 和这个节点的 $x$ 轴比较一下， ![findleaf1.png][12] $p$ 的 $x$ 轴更小。因此我们向左枝进行搜索： ![树7.png][13] 这次对比 $y$ 轴， ![findleaf2.png][14] $p$ 的 $y$ 值更小，因此向左枝进行搜索： ![树8.png][15] 这个节点只有一个子枝，就不需要对比了。由此找到了最底部的节点 $(-4.6,-10.55)$。 ![树9.png][16] 在二维图上是 ![7.png][17] 此时我们执行 (二)。将当前结点标记为访问过，并记录下 $L=[(-4.6,-10.55)]$。啊，访问过的节点就在二叉树上显示为被划掉的好了。 然后执行 (三)，嗯，不是最顶端节点。好，执行 (a)，我爬。上面的是 $(-6.88,-5.4)$。 ![树10.png][18] ![8.png][19] 执行 (1)，因为我们记录下的点只有一个，小于 $k=3$，所以也将当前节点记录下，有 $L=[(-4.6,-10.55),(-6.88,-5.4)]$。再执行 (2)，因为当前节点的左枝是空的，所以直接跳过，回到步骤 (三)。(三) 看了一眼，好，不是顶部，交给你了，(a)。于是乎 (a) 又往上爬了一节。 ![树11.png][20] ![9.png][21] (1) 说，由于还是不够三个点，于是将当前点也记录下，有 $L=[(-4.6,-10.55),(-6.88,-5.4),(1.24,-2.86)]$。当然，当前结点变为被访问过的。 (2) 又发现，当前节点有其他的分枝，并且经计算得出 $p$ 点和 $L$ 中的三个点的距离分别是 $6.62,5.89,3.10$，但是 $p$ 和当前节点的分割线的距离只有 $2.14$，小于与 $L$ 的最大距离： ![10.png][22] 因此，在分割线的另一端可能有更近的点。于是我们在当前结点的另一个分枝从头执行 (一)。好，我们在红线这里： ![树12.png][23] 要用 $p$ 和这个节点比较 $x$ 坐标: ![findleaf3.png][24] $p$ 的 $x$ 坐标更大，因此探索右枝 $(1.75,12.26)$，并且发现右枝已经是最底部节点，因此启动 (二)。 ![树13.png][25] 经计算，$(1.75,12.26)$ 与 $p$ 的距离是 $17.48$，要大于 $p$ 与 $L$ 的距离，因此我们不将其放入记录中。 ![11.png][26] 然后 (三) 判断出不是顶端节点，呼出 (a)，爬。 ![树14.png][27] (1) 出来一算，这个节点与 $p$ 的距离是 $4.91$，要小于 $p$ 与 $L$ 的最大距离 $6.62$。 ![12.png][28] 因此，我们用这个新的节点替代 $L$ 中离 $p$ 最远的 $(-4.6,-10.55)$。 ![13.png][29] 然后 (2) 又来了，我们比对 $p$ 和当前节点的分割线的距离 ![14.png][30] 这个距离小于 $L$ 与 $p$ 的最小距离，因此我们要到当前节点的另一个枝执行 (一)。当然，那个枝只有一个点，直接到 (二)。 ![树15.png][31] 计算距离发现这个点离 $p$ 比 $L$ 更远，因此不进行替代。 ![15.png][32] (三) 发现不是顶点，所以呼出 (a)。我们向上爬， ![图16.png][33] 这个是已经访问过的了，所以再来（a）， ![图17.png][34] 好，（a）再爬， ![图18.png][35] 啊！到顶点了。所以完了吗？当然不，还没轮到 (三) 呢。现在是 (1) 的回合。 我们进行计算比对发现顶端节点与p的距离比L还要更远，因此不进行更新。 ![16.png][36] 然后是 (2)，计算 $p$ 和分割线的距离发现也是更远。 ![17.png][37] 因此也不需要检查另一个分枝。 然后执行 (三)，判断当前节点是顶点，因此计算完成！输出距离 $p$ 最近的三个样本是 $L=[(-6.88,-5.4),(1.24,-2.86),(-2.96,-2.5)]$。 $ $ #### **结语** kd 树的 kNN 算法节约了很大的计算量（虽然这点在少量数据上很难体现），但在理解上偏于复杂，希望本篇中的实例可以让读者清晰地理解这个算法。喜欢动手的读者可以尝试自己用代码实现 kd 树算法，但也可以用现成的机器学习包 scikit-learn 来进行计算。量化课堂的[下一篇文章](https://www.joinquant.com/post/3227?f=study&m=math)就将讲解如何用 scikit-learn 进行 kNN 分类。 \[ \] ``` 本文由JoinQuant量化课堂推出，版权归JoinQuant所有，商业转载请联系我们获得授权，非商业转载请注明出处。 文章更迭记录： v1.2，2016-11-01，修正算法，感谢 nemo1982 指出 v1.1，2016-09-14，修正错字，感谢 nico 指出 v1.0，2016-09-12，文章上线 ``` [1]: https://image.joinquant.com/9e6b366ad5cea5d1e9ba095742f73915 [2]: https://image.joinquant.com/444ee82b59f7d06794ebedf775b4b27f [3]: https://image.joinquant.com/e3a15951870d45761087e3b31dda7cf4 [4]: https://image.joinquant.com/0bd623cd64f9c8b9e7a6795de0cd2bcd [5]: https://image.joinquant.com/f6d65a04593ec7911cc3f1f0615bf6f4 [6]: https://image.joinquant.com/1160e95d646cb593b7ea4fdb9444d4e0 [7]: https://image.joinquant.com/d514c71a5dbccaecffdea6c0f407780e [8]: https://image.joinquant.com/78ea8d88dcbb837ca74cda77805c8c4b [9]: https://image.joinquant.com/93494bbff8ac9e96cd7cd671a54a7885 [10]: https://image.joinquant.com/880ee4b91acd0d801bd8cbecddbd5b39 [11]: https://image.joinquant.com/6258242090a8b86310b2dd1d465bba3f [12]: https://image.joinquant.com/e84a7e1ba8e4a33730558c09d635a1aa [13]: https://image.joinquant.com/0d128b8d1efab58726ffdabdb858a2ae [14]: https://image.joinquant.com/995d91276f4351ead1f4b644735228aa [15]: https://image.joinquant.com/50f6eaaa6e2dcd7bf3ebe1e22139f9be [16]: https://image.joinquant.com/1c69996ad65ee3284fa43ae89793e88d [17]: https://image.joinquant.com/1848ac29db08416ef7baed2a008eb017 [18]: https://image.joinquant.com/0002c2968f4a97ba5e68930b5d7b533d [19]: https://image.joinquant.com/f1a504b1f679bd9748bf4018ea1c71d9 [20]: https://image.joinquant.com/2bbf3758124830de7e11e4456900a951 [21]: https://image.joinquant.com/f39d547deeafbdc29c58bfdd65da6ea3 [22]: https://image.joinquant.com/2a755c9cca7b2697d49b267166f14553 [23]: https://image.joinquant.com/b8d5fb100d4608b79a41201c2f73410e [24]: https://image.joinquant.com/dc00ae0dcb5212d814b8c7910bb277e4 [25]: https://image.joinquant.com/357e68430d1a80927ab96cd284860196 [26]: https://image.joinquant.com/ca6cc29e28640d76c60d384e204bda0e [27]: https://image.joinquant.com/b990e692fd701da85f24f7e5a3638708 [28]: https://image.joinquant.com/ab27a1147c11c3fda33be82d84562ea8 [29]: https://image.joinquant.com/3b637a26fb0af76b0ce2f027a1b4606e [30]: https://image.joinquant.com/3b03de2b0c240c69a55c5ff1f3bd2277 [31]: https://image.joinquant.com/c3aa4fe8215cbf59d9518955056b88ff [32]: https://image.joinquant.com/3e88b7d5ae4bbc0fca2d32ad28f103ce [33]: https://image.joinquant.com/2715846daf0cf26655b391e8d1dc569a [34]: https://image.joinquant.com/cc51536c66b8f7492df3782c24aff8f2 [35]: https://image.joinquant.com/ecc53901c03d25bedf5febe9e496b7ca [36]: https://image.joinquant.com/24a59cf9391c80cd818ed9942b63fb44 [37]: https://image.joinquant.com/5b8ea4b5aba82d4a6c17f74b6b8f0d6b