Python实现K维树(KD-Tree)算法查找最近邻项目实战

预设条件

1. 中级IDE使用经验（Jetbrain Pycharm优先）
2. 了解Python运行环境及其命令使用
3. 对Python编程语言有很好的理解
4. 基本了解Pandas(处理数据框架)、Numpy、Scikit Learn和Matplot库
5. 一些统计学知识，对分析数据是有帮助的

运行环境

以下运行软件的版本号是经过验证的可成功运行的版本号，以供参考。

项目背景

K维树（KD Tree, KDT）是一种改良的二叉搜索树（Binary Search Tree, BST），KD树能够进行多维搜索，这也是被称为K维的原因。

KDT与BST的不同在于叶子节点，KDT里的每个叶子节点都是一个K维向量空间的点。

什么是识别器（Discriminate）？

一棵KD树，节点范围是从0到k-1，识别器（Discriminator）是用来进行分支决策的，它的基本原理是用与树的层级（Level）相关的特定搜索key。

什么是树的层级？我们一起复习一下层级的概念。

树的层级（Level）定义：

• 根节点（Root）：树的最顶层节点，通常位于第0层（Level 0）
• 子节点（Child）：根节点的直接下级节点，位于第1层（Level 1）
• 孙子节点（Grandchild）：子节点的直接下级节点，位于第2层（Level 2）
• 以此类推：树中的每个节点都有一个层级，层级是从根节点开始逐层向下递增的

所有的节点都具有相同的识别器，所以根节点使用0做识别器，它的子节点使用1做识别器，以此类推。

如何构建一棵KD树？

在一个2维平面中，每个点有x和y坐标两个参数。首先用x坐标进行第一次分割，然后再用y坐标进行第二次分割，接着以此类推，先用x坐标，再用y坐标，一直分割下去。

看下图，首先把分割线L1左边的点集称为Z-left，把右边的点集称为Z-right。

然后再用分割线L2把Z-left进行水平分割，如下图所示：

同样道理，用分割线L3把Z-right也进行水平分割，如下图所示：

现在对L2和L3分割出来的点集，再进行垂直分割，所以我们可以得到结论，用垂直线分割的子树深度是偶数，用水平线分割的子树深度是奇数，如下图所示：

那么我们什么时候下用水平线来分割？什么时候用垂直先来分割呢？基本原理是，通过选择中位数来确定分割线，然后用这个中位数的坐标来确定分割平面。

n个点的KD树的空间复杂度=O(n)，时间复杂度=O(n logn)。

构建KD树需要注意方面

有3点需要特别关注：

1. 先分割哪个数轴？先分割最宽的数轴
2. 要分割哪个数？选择中位数进行分割，或者数轴中所有数的中心
3. 什么时候停止分割？当剩下的数据点少于特定值m时

在KD树上如何使用近邻检索

每个节点都会存储以下三个基本信息：

1. 用于分割的X轴和Y轴
2. 分割的数值
3. 边界框-它是包含该节点内所有点的最小框，如下图所示：

KD树实现

用sklearn库来实现KD树的算法。比如，先定义一个2维向量平面的点集Z，如下：

Z = [(5,23),(6,28),(8,24),(10,28),(9,26),(10,30),(7,22),(9,18),

(6,24),(8,32),(9,20),(7,32),(7,27),(18,30),(11,22),(17,31),

(13,28),(16,24),(19,26),(10,28),(14,27),(18,23),(17,22),(18,24)]

sklearn提供了一个NearestNeigbors类，这个类中'提供了多个方法实现近邻查询。

比如以下代码定义了一个KD树：

from sklearn.neighbors import NearestNeighbors

neigh = NearestNeighbors(n_neighbors=2, radius=0.4, algorithm = 'kd_tree')

其中，参数n_neighbors表示查询多少个邻居，radius用于 radius_neighbors 查询的参数空间范围，algorithm 表示计算最近邻居的算法，取值为“auto”，“ball_tree”，“kd_tree”，“brute”，默认为auto，ball_tree将使用BallTree，kd_tree将使用 KDTree，brute将使用暴力搜索，auto将尝试基于传递给 fit 方法的值决定最合适的算法。

然后我们使用fit方法对样本数据进行拟合，代码如下：

neigh.fit(Z)

参数Z是采样数据，这里是前面定义的2维空间向量点集。

最后就可以计算某一个点的最近邻，比如设置一个点(10,28) ，并计算出这个点附近的3个最近的邻居，编写代码如下：

X=[[10,28]]

idxs = neigh.kneighbors(X=X, n_neighbors=3, return_distance=False)

其中，参数X是查询点或点集，n_neighbors表示每个样本所需的邻居数量，return_distance代表是否返回距离。

返回结果是：

[[ 3 19 5]]

这里的返回的结果是查询点的3个最近点的数组索引。可以用以下代码打印出样本值：

[print(x, y, Z[y]) for (x,y) in np.ndenumerate(idxs)]

显示的结果如下：

(0, 0) 3 (10, 28)

(0, 1) 19 (11, 27)

(0, 2) 5 (10, 30)

其中，第一列的表示序号，第二列表示数组索引，第三列表示数组元素

这样我们就可以得到查询点的3个最近的点分别是：(10, 28)、(11, 27)、(10, 30)。

KD树在地理坐标系统上的应用

Scipy提供了一个可用于KD树的快速查询的scipy.spatial.kdtree类，这个类提供了一个索引，这个索引标识了K维的数据点，用于进行快速查找出所有点的最近邻点。

例如，我们选取了印度城市的地理坐标的经纬度数据，然后用这些数据可以获取到某一个城市的最近邻城市，如图所示：

其中坐标数据的代码如下：

Z = [(19.076,72.877),(18.52,73.85),(12.97,77.59),(22.71,75.85),(28.704,77.10),(28.45,77.026),(13.0827,80.27)]，

对应这些坐标数据的城市分别是：Mumbai, Pune, Bangalore, Indore, Delhi, Gurugram, Chennai，代码如下：

Z_name_list = ["Mumbai", "Pune", "Bangalore", "Indore", "Delhi", "Gurugram", "Chennai"]

数据准备好后，我们构建一棵KD树，代码如下：

tree = spatial.KDTree(Z)

其中，参数Z是坐标数据。

现在以Mumbai作为查询城市，他的坐标数据是(19.076,72.877)，来看看他的2个最近邻的城市是什么，代码如下：

idxs = tree.query(Z[0], 3)

其中参数Z[0]是代表Mumbai这个城市, 3是返回3个最近邻的城市（包括Mumbai自己），返回结果如下：

Mumbai Pune Indore

排除Mumbai之后，得到2个最近邻的城市分别为：Pune、Indore。

再比如，以Bangalorew为起点，得到一个距离由近到远的城市列表，代码如下：

idxs = tree.query(Z[2], 7)

其中，Z[2]表示Bangalorew这个城市坐标数据，7表示返回7个最近邻的城市（因为本例中的样本数据就是7条），执行结果如下：

Bangalore, Chennai, Mumbai, Pune, Indore, Gurugram, Delhi,

分析结果可以看出，Mumbai比Delhi到Bangalore的距离更近，这个结论与地图上显示出来的按照道路的距离远近的实际情况并不相符，因为从地图上看，按照绘制的道路情况，从Mumbai出发到Bangalore需要先经过Delhi，当然也不排除有Mumbai直接通往Bangalore的道路，但这里的地图并没有绘制出来，所以本文暂不考虑这种情况，只做一般性推论。所以这个结果的最近邻城市列表是按照每两个城市经纬度坐标的直线距离比较的，而不是按照地图中道路的距离比较，这一点需要特别注意。

另外再看一下与首都Delhi的其他城市远近的情况，代码如下：

idxs = tree.query(Z[4], len(Z))

执行结果为：

Delhi, Gurugram, Indore, Mumbai, Pune, Bangalore, Chennai,

从结果中可以看出，Gurugram是离首都最近的城市，而Bangalore和Chennai相对离首都就比较远了，这些知识也是比较符合实际情况的。

结论

本文主要介绍了通过使用KD树算法进行建模和预测的实战项目案例，希望能够帮助你学习和理解决策树算法的核心内容。如果你还想学习更多人工智能/机器学习/深度学习相关的知识，请继续阅读我编写的其他内容的文章。

本文涉及到的机器学习实战项目文件（附带数据+代码+文档）名称如下：

kd_tree.py

MLAP8-机器学习项目实战8-Python实现K维树（KD-Tree）算法查找最近邻项目实战.pdf