kd树基本描述

1,705次阅读
没有评论

kd 树的结构

kd树是一个二叉树结构,它的每一个节点记载了【特征坐标,切分轴,指向左枝的指针,指向右枝的指针】。

其中,特征坐标是线性空间\(R^n\)中的一个点\(x_1,x_2,…,x_n\)。

切分轴由一个整数\(r\)表示,这里\(1 \le r \le n \),是我们在 n 维空间中沿第 r 维进行一次分割。

节点的左枝和右枝分别都是 kd 树,并且满足:如果 y 是左枝的一个特征坐标,那么\(y_r \le x_r \)并且如果 z 是右枝的一个特征坐标,那么\(z_r \ge x_r \)。

给定一个数据样本集 \(S \subseteq R^n\)和切分轴 r , 以下递归算法将构建一个基于该数据集的 kd 树,每一次循环制作一个节点:

−− 如果 \(|S|=1\),记录 S 中唯一的一个点为当前节点的特征数据,并且不设左枝和右枝.\(|S|\) 指集合 S 中元素的数量) −− 如果\(|S| >1\): ∙∙ 将 S 内所有点按照第 r 个坐标的大小进行排序; ∙∙ 选出该排列后的中位元素(如果一共有偶数个元素,则选择中位左边或右边的元素,左或右并无影响),作为当前节点的特征坐标,并且记录切分轴 r; ∙∙ 将 \(S_L\) 设为在 S 中所有排列在中位元素之前的元素; \(S_R\) 设为在 S 中所有排列在中位元素后的元素; ∙∙ 当前节点的左枝设为以 \(S_L\) 为数据集并且 r 为切分轴制作出的 kd 树;当前节点的右枝设为以 \(S_R\) 为数据集并且 r 为切分轴制作出的 kd 树。再设\(r\leftarrow(r+1)\ mod\ n \)。(这里,我们想轮流沿着每一个维度进行分割;\(mod\ n \) 是因为一共有 n 个维度,在沿着最后一个维度进行分割之后再重新回到第一个维度。)

构造 kd 树的例子

上面抽象的定义和算法确实是很不好理解,举一个例子会清楚很多。首先随机在 \(\mathbb{R}^2 \) 中随机生成 13 个点作为我们的数据集。起始的切分轴\(r=0\);这里 \(r=0\)对应 xx 轴,而\( r=1\) 对应 y 轴。

kd树基本描述
首先先沿 x 坐标进行切分,我们选出 x 坐标的中位点,获取最根部节点的坐标

kd树基本描述
并且按照该点的x坐标将空间进行切分,所有 x 坐标小于 6.27 的数据用于构建左枝,x坐标大于 6.27 的点用于构建右枝。

kd树基本描述
在下一步中 kd树基本描述 对应 y 轴,左右两边再按照 y 轴的排序进行切分,中位点记载于左右枝的节点。得到下面的树,左边的 x 是指这该层的节点都是沿 x 轴进行分割的。

kd树基本描述
空间的切分如下

kd树基本描述
下一步中 r≡1+1≡0 mod 2,对应 x 轴,所以下面再按照 x 坐标进行排序和切分,有

kd树基本描述
kd树基本描述
最后每一部分都只剩一个点,将他们记在最底部的节点中。因为不再有未被记录的点,所以不再进行切分。

kd树基本描述
kd树基本描述
就此完成了 kd 树的构造。

转载https://zhuanlan.zhihu.com/p/23966698

admin
版权声明:本站原创文章,由admin2018-03-14发表,共计1138字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)