- 简介
kd-tree也叫k维树，是k维二叉树，是一种空间划分的数据结构，常备用于高维空间搜索 。
- kd-tree的构建
输入：无序化的点云，维度为k。
输出：数据对应的kd-tree。
步骤：
① 初始化分割轴：对每个维度的数据进行方差的计算，取最大方差的维度作为分割轴，标记为r；
② 确定节点：对当前数据按分割轴维度进行检索，找到中位数数据，将其放入到当前节点上；
③ 划分双支：划分左支：在当前分割轴维度，所有小于中位数的值划分到左支中；
划分右支：在当前分割轴维度，所有大于等于中位数的值划分到左支中；
④ 更新分割轴：r = （r+1）% k，首先r从0开始，0表示x轴；然后r = （0+1）%2=1；然后r = （1+1）%2 = 0，表示在沿着最后一个维度进行分割之后再重新回到第一个维度。
⑤ 确定子节点：确定左节点：在左支的数据中进行步骤2；
确定右节点：在右支的数据中进行步骤2；
这样就构成了一个完整的kd-tree。
- 举例
有一组二维数：{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}
构建步骤：
① 初始化分割轴：
发现X轴的方差较大，所以最开始的分割轴为x轴。
② 确定当前的节点：
对x轴的数{2, 5, 9, 4, 8, 7}找中位数，发现5和7 都可以（选择左右都无影响），这里选择7，也就是（7，2）作为节点。
③ 划分双支数据
在x轴维度上，比较和7的大小，进行划分：
左支：{（2,3），（5,4），（4,7）}
右支：{（9,6），（8,1）}
④ 更新分割轴
例子中只有两个维度，所以下一个轴是y轴
⑤ 确定子节点
左节点：在左支中找到y轴的中位数4，即（5,4），所以左支数据更新为{（2,3）}，右支数据更新为：{（4,7）}
右节点：在右支中找到y轴的中位数6，即（9,6），所以左支数据更新为{（8,1）}，右支数据为null
⑥ 更新分割轴：
下一个维度为x轴
⑦ 确定（5,4）的子节点
左节点：由于只有一个数据，所以左节点为（2,3）
右节点：由于只有一个数据，所以右节点为（4,7）
⑧ 确定（9,6）的子节点
左节点：由于只有一个数据，所以左节点为（8,1）
右节点：空
最终得到了整个kd-tree
image.png
- 最近邻
① 举例：查找（2.1,3.1）的最近邻
② 首先计算当前节点的距离，scipy库中的距离默认使用欧式距离计算的，即p=2，也可以修改。
image.png
③ 首先计算（2.1,3.1）和（7，2）的距离（下面都用欧式距离）：5.022，并且暂定为（7，2），根据当前分割轴的维度（2.1<7），所以选择左支。
④ 计算当前节点（5,4）的距离：3.036，3.036<5.022,暂定为（5,4），根据当前的分割维度（3.1<4），选左支。
⑤ 计算当前节点（2,3）的距离：0.1414，暂定为(2,3)，根据当前分割轴维度（2.1 > 2），选取右支，而右支为空，回溯上一个节点。
⑥ 计算(2.1,3.1)与(5,4)的分割轴{y = 4}的距离，如果0.14小于距离值，说明就是最近值。如果大于距离值，说明，还有可能存在值与(2.1,3.1)最近，需要往右支检索。
⑦ 由于0.14 < 0.9，我们找到了最近邻的值为(2,3)，最近距离为0.14。
网友评论