kd 树 (k-dimensional 树的简称), 是一种分割 k 维数据空间的数据结构, 主要应用于多维空间关键数据的近邻查找(Nearest Neighbor) 和近似最近邻查找(Approximate Nearest Neighbor).
一, Kd-tree
其实 KDTree 就是二叉查找树 (Binary Search Tree,BST) 的变种. 二叉查找树的性质如下:
1)若它的左子树不为空, 则左子树上所有结点的值均小于它的根结点的值;
2)若它的右子树不为空, 则右子树上所有结点的值均大于它的根结点的值;
3)它的左, 右子树也分别为二叉排序树;
例如:
如果我们要处理的对象集合是一个 K 维空间中的数据集, 我们首先需要确定是: 怎样将一个 K 维数据划分到左子树或右子树?
在构造 1 维 BST 树类似, 只不过对于 Kd 树, 在当前节点的比较并不是通过对 K 维数据进行整体的比较, 而是选择某一个维度 d, 然后比较两个 K 维数据在该维度 d 上的大小关系, 即每次选择一个维度 d 来对 K 维数据进行划分, 相当于用一个垂直于该维度 d 的超平面将 K 维数据空间一分为二, 平面一边的所有 K 维数据 在 d 维度上的值小于平面另一边的所有 K 维数据对应维度上的值. 也就是说, 我们每选择一个维度进行如上的划分, 就会将 K 维数据空间划分为两个部分, 如果我 们继续分别对这两个子 K 维空间进行如上的划分, 又会得到新的子空间, 对新的子空间又继续划分, 重复以上过程直到每个子空间都不能再划分为止. 以上就是构造 Kd-Tree 的过程, 上述过程中涉及到两个重要的问题:
每次对子空间的划分时, 怎样确定在哪个维度上进行划分;
在某个维度上进行划分时, 怎样确保建立的树尽量地平衡, 树越平衡代表着分割得越平均, 搜索的时间也就是越少.
1, 在哪个维度上进行划分?
一种选取轴点的策略是 median of the most spread dimension pivoting strategy, 统计样本在每个维度上的数据方差, 挑选出对应方差最大值的那个维度. 数据方差大说明沿该坐标轴方向上数据点分散的比较开. 这个方向上, 进行数据分割可以获得最好的平衡.
2, 怎样确保建立的树尽量地平衡?
给定一个数组, 怎样才能得到两个子数组, 这两个数组包含的元素 个数差不多且其中一个子数组中的元素值都小于另一个子数组呢? 方法很简单, 找到数组中的中值 (即中位数, median), 然后将数组中所有元素与中值进行 比较, 就可以得到上述两个子数组. 同样, 在维度 d 上进行划分时, 划分点(pivot) 就选择该维度 d 上所有数据的中值, 这样得到的两个子集合数据个数就基本相同了.
二, Kd-Tree 的构建
1), 在 K 维数据集合中选择具有最大方差的维度 k, 然后在该维度上选择中值 m 为 pivot 对该数据集合进行划分, 得到两个子集合; 同时创建一个树结点 node, 用于存储;
2), 对两个子集合重复 (1) 步骤的过程, 直至所有子集合都不能再划分为止;
举个例子:
假设有 6 个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}, 数据点位于二维空间内(如下图中黑点所示).kd 树算法就是要确定图 1 中这些分割空间的分割线(多维空间即为分割平面, 一般为超平面). 下面就要通过一步步展示 kd 树是如何确定这些分割线的.
分别计算 x,y 方向上数据的方差, 得知 x 方向上的方差最大;
根据 x 轴方向的值 2,5,9,4,8,7 排序选出中值为 7, 所以该 node 中的 data = (7,2). 这样, 该节点的分割超平面就是通过 (7,2) 并垂直于 x 轴的直线 x = 7;
确定左子空间和右子空间. 分割超平面 x = 7 将整个空间分为两部分, 如下图所示. x <= 7 的部分为左子空间, 包含 3 个节点{(2,3),(5,4),(4,7)}; 另一部分为右子空间, 包含 2 个节点{(9,6),(8,1)}.
k-d 树的构建是一个递归的过程. 然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点 (5,4) 和(9,6)(也就是左右子空间的'根'节点), 同时将空间和数据集进一步细分. 如此反复直到空间中只包含一个数据点, 如下图所示:
三, Kd-Tree 的最近邻查找
(1)将查询数据 Q 从根结点开始, 按照 Q 与各个结点的比较结果向下访问 Kd-Tree, 直至达到叶子结点.
其中 Q 与结点的比较指的是将 Q 对应于结点中的 k 维度上的值与中值 m 进行比较, 若 Q(k) < m, 则访问左子树, 否则访问右子树. 达到叶子结点时, 计算 Q 与叶子结点上保存的数据之间的距离, 记录下最小距离对应的数据点, 记为当前最近邻点 nearest 和最小距离 dis.
(2)进行回溯操作, 该操作是为了找到离 Q 更近的 "最近邻点". 即判断未被访问过的分支里是否还有离 Q 更近的点, 它们之间的距离小于 dis.
如果 Q 与其父结点下的未被访问过的分支之间的距离小于 dis, 则认为该分支中存在离 P 更近的数据, 进入该结点, 进行 (1) 步骤一样的查找过程, 如果找到更近的数据点, 则更新为当前的最近邻点 nearest, 并更新 dis.
如果 Q 与其父结点下的未被访问过的分支之间的距离大于 dis, 则说明该分支内不存在与 Q 更近的点.
回溯的判断过程是从下往上进行的, 直到回溯到根结点时已经不存在与 P 更近的分支为止.
注: 判断未被访问过的树分支中是否还有离 Q 更近的点, 就是判断 "Q 与未被访问的树分支的距离 | Q(k) - m|" 是否小于 "Q 到当前的最近邻点 nearest 的距离 dis". 从几何空间上来看, 就是判断以 Q 为中心, 以 dis 为半径超球面是否与未被访问的树分支代表的超矩形相交.
下面举两个例子来演示一下最近邻查找的过程.
假设我们的 kd 树就是上面通过样本集 {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)} 创建的.
例 1: 查找点 Q(2.1,3.1)
如下图所示, 红色的点即为要查找的点. 通过图 4 二叉搜索, 顺着搜索路径很快就能找到当前的最邻近点(2,3).
在上述搜索过程中, 产生的搜索路径节点有 <(7,2),(5,4),(2,3)>. 为了找到真正的最近邻, 还需要进行'回溯'操作, 首先以(2,3) 作为当前最近邻点 nearest, 计算其到查询点 Q(2.1,3.1)的距离 dis 为 0.1414, 然后回溯到其父节点 (5,4), 并判断在该父节点的其他子节点空间中是否有距离查询点 Q 更近的数据点. 以(2.1,3.1) 为圆心, 以 0.1414 为半径画圆, 如图 6 所示. 发现该圆并不和超平面 y = 4 交割, 即这里:|Q(k) - m|=|3.1 - 4|=0.9> 0.1414, 因此不用进入 (5,4) 节点右子空间中去搜索.
再回溯到 (7,2), 以(2.1,3.1) 为圆心, 以 0.1414 为半径的圆更不会与 x = 7 超平面交割, 因此不用进入 (7,2) 右子空间进行查找. 至此, 搜索路径中的节点已经全部回溯完, 结束整个搜索, 返回最近邻点(2,3), 最近距离为 0.1414.
例 2: 查找点 Q(2,4.5)
如下图所示, 同样经过图 4 的二叉搜索, 可得当前的最邻近点 (4,7), 产生的搜索路径节点有<(7,2),(5,4),(4,7)>. 首先以(4,7) 作为当前最近邻点 nearest, 计算其到查询点 Q(2,4.5)的距离 dis 为 3.202, 然后回溯到其父节点 (5,4), 并判断在该父节点的其他子节点空间中是否有距离查询点 Q 更近的数据点. 以(2,4.5) 为圆心, 以为 3.202 为半径画圆, 如图 7 所示. 发现该圆和超平面 y = 4 交割, 即这里:|Q(k) - m|=|4.5 - 4|=0.5 <3.202, 因此进入 (5,4) 节点右子空间中去搜索. 所以, 将 (2,3) 加入到搜索路径中, 现在搜索路径节点有 <(7,2), (2, 3)>. 同时, 注意: 点 Q(2,4.5) 与父节点 (5,4) 的距离也要考虑, 由于这两点间的距离 3.04 <3.202, 所以将 (5,4) 赋给 nearest, 并且 dist=3.04.
接下来, 回溯至 (2,3) 叶子节点, 点 Q(2,4.5)和 (2,3) 的距离为 1.5, 比距离 (5,4) 要近, 所以最近邻点 nearest 更新为 (2,3), 最近距离 dis 更新为 1.5. 回溯至(7,2), 如图 8 所示, 以(2,4.5) 为圆心 1.5 为半径作圆, 并不和 x = 7 分割超平面交割, 即这里:|Q(k) - m|=|2 - 7|=5> 1.5. 至此, 搜索路径回溯完. 返回最近邻点(2,3), 最近距离 1.5.
四, 总结
Kd 树在维度较小时(比如 20,30), 算法的查找效率很高, 然而当数据维度增大(例如: K≥100), 查找效率会随着维度的增加而迅速下降. 假设数据集的维数为 D, 一般来说要求数据的规模 N 满足 N>>2 的 D 次方, 才能达到高效的搜索.
为了能够让 Kd 树满足对高维数据的索引, Jeffrey S. Beis 和 David G. Lowe 提出了一种改进算法 --Kd-tree with BBF(Best Bin First), 该算法能够实现近似 K 近邻的快速搜索, 在保证一定查找精度的前提下使得查找速度较快.
来源: https://www.cnblogs.com/PythonLearner/p/12952929.html