• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

kd树基本描述

math admin 2年前 (2018-03-14) 796次浏览 0个评论 扫描二维码

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 轴。

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

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

在下一步中 r=0+1=1\ mod\ 2 对应 y 轴,左右两边再按照 y 轴的排序进行切分,中位点记载于左右枝的节点。得到下面的树,左边的 x 是指这该层的节点都是沿 x 轴进行分割的。

空间的切分如下

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

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

就此完成了 kd 树的构造。

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


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明kd 树基本描述
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!