K-近邻算法（二）

三、 kd 树

问题导⼊：

        实现k 近邻算法时， 主要考虑的问题是如何对训练数据进⾏快速 k 近邻搜索。这在特征空间的维数⼤及训练数据容量⼤时尤其必要。

k 近邻法最简单的实现是线性扫描（穷举搜索），即要计算输⼊实例与每⼀个训练实例的距离。计算并存储好以后，再 查找 K 近邻。 当训练集很⼤时，计算⾮常耗时。

为了提⾼ kNN 搜索的效率，可以考虑使⽤特殊的结构存储训练数据，以减⼩计算距离的次数。

3.1 kd 树简介

3.1.1 什么是 kd 树

根据 KNN 每次需要预测⼀个点时，我们都需要计算训练数据集⾥每个点到这个点的距离，然后选出距离最近的 k 个点进

⾏投票。 当数据集很⼤时，这个计算成本⾮常⾼，针对 N 个样本， D 个特征的数据集，其算法复杂度为 O （ DN 2 ） 。

kd 树 ：为了避免每次都重新计算⼀遍距离，算法会把距离信息保存在⼀棵树⾥，这样在计算之前从树⾥查询距离信息， 尽量避免重新计算。其基本原理是，如果 A 和 B 距离很远， B 和 C 距离很近，那么 A 和 C 的距离也很远 。有了这个信息， 就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到 O （ DNlog （ N ））。感兴趣的读者可参阅论⽂： Bentley ， J.L. ， Communications of the ACM（ 1975 ）。

1989 年，另外⼀种称为 Ball Tree 的算法，在 kd Tree 的基础上对性能进⼀步进⾏了优化。感兴趣的读者可以搜索 Five balltree construction algorithms 来了解详细的算法信息。

1. 树的建⽴；

2. 最近邻域搜索（ Nearest-Neighbor Lookup ）

kd 树 (K-dimension tree) 是 ⼀种对 k 维空间中的实例点进⾏存储以便对其进⾏快速检索的树形数据结构。 kd 树是⼀种⼆叉 树，表示对k 维空间的⼀个划分， 构造 kd 树相当于不断地⽤垂直于坐标轴的超平⾯将 K 维空间切分，构成⼀系列的 K 维超 矩形区域 。 kd 树的每个结点对应于⼀个 k 维超矩形区域。 利⽤ kd 树可以省去对⼤部分数据点的搜索，从⽽减少搜索的计 算量。

类⽐ “ ⼆分查找 ” ：给出⼀组数据： [9 1 4 7 2 5 0 3 8] ，要查找 8 。如果挨个查找（线性扫描），那么将会把数据集都遍历 ⼀遍。⽽如果排⼀下序那数据集就变成了：[0 1 2 3 4 5 6 7 8 9] ，按前⼀种⽅式我们进⾏了很多没有必要的查找，现在 如果我们以5 为分界点，那么数据集就被划分为了左右两个 “ 簇 ” [0 1 2 3 4] 和 [6 7 8 9] 。

因此，根本就没有必要进⼊第⼀个簇，可以直接进⼊第⼆个簇进⾏查找。把⼆分查找中的数据点换成 k 维数据点，这样 的划分就变成了⽤超平⾯对k 维空间的划分。空间划分就是对数据点进⾏类， “ 挨得近 ” 的数据点就在⼀个空间⾥⾯。

2 构造⽅法

（ 1 ） 构造根结点，使根结点对应于 K 维空间中包含所有实例点的超矩形区域；

（ 2 ） 通过递归的⽅法，不断地对 k 维空间进⾏切分，⽣成⼦结点。 在超矩形区域上选择⼀个坐标轴和在此坐标轴上的⼀ 个切分点，确定⼀个超平⾯，这个超平⾯通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（⼦结点）；这时，实例被分到两个⼦区域。

（ 3 ） 上述过程直到⼦区域内没有实例时终⽌（终⽌时的结点为叶结点） 。在此过程中，将实例保存在相应的结点上。

（ 4 ）通常，循环的选择坐标轴对空间切分，选择训练实例点在坐标轴上的中位数为切分点，这样得到的 kd 树是平衡的 （平衡⼆叉树：它是⼀棵空树，或其左⼦树和右⼦树的深度之差的绝对值不超过1 ，且它的左⼦树和右⼦树都是平衡⼆ 叉树）。

KD 树中每个节点是⼀个向量，和⼆叉树按照数的⼤⼩划分不同的是， KD 树每层需要选定向量中的某⼀维，然后根据这

⼀维按左⼩右⼤的⽅式划分数据。在构建 KD 树时，关键需要解决 2 个问题：

（ 1 ）选择向量的哪⼀维进⾏划分；

（ 2 ）如何划分数据；

第⼀个问题简单的解决⽅法可以是随机选择某⼀维或按顺序选择，但是 更好的⽅法应该是在数据⽐较分散的那⼀维进⾏ 划分（分散的程度可以根据⽅差来衡量） 。

第⼆个问题中，好的划分⽅法可以使构建的树⽐较平衡，可以每次选择中位数来进⾏划分。