KD-Tree原理详解

phpmianshi6年前 (2015-11-11)算法125

这样就会出现很多长条的分割,对于KDTree来说是很不利的。


为了避免这种情况,需要修改一下算法,纬度的选择的依据为数据范围最大的那一维作为分割纬度,之后也是选中这个纬度的中间节点作为轴点,然后进行分割,分割出来的结果是:



这样的结果对于最邻近搜索是非常友好的。

但是这样做还是有一些不好,就是在树上很可能有一些空的节点,当要限制树的高度的时候,这种方法就不合适了。

构建示例

二维样例:{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}

构建步骤:

1、初始化分割轴:

发现x轴的方差较大,所以,最开始的分割轴为x轴。

2、确定当前节点:

对{2,5,9,4,8,7}找中位数,发现{5,7}都可以,这里我们选择7,也就是(7,2);

3、划分双支数据:

在x轴维度上,比较和7的大小,进行划分:

左支:{(2,3),(5,4),(4,7)}

右支:{(9,6),(8,1)}

4、更新分割轴:

一共就两个维度,所以,下一个维度是y轴。

5、确定子节点:

左节点:在左支中找到y轴的中位数(5,4),左支数据更新为{(2,3)},右支数据更新为{(4,7)}

右节点:在右支中找到y轴的中位数(9,6),左支数据更新为{(8,1)},右支数据为null。

6、更新分割轴:

下一个维度为x轴。

7、确定(5,4)的子节点:

左节点:由于只有一个数据,所以,左节点为(2,3)

右节点:由于只有一个数据,所以,右节点为(4,7)

8、确定(9,6)的子节点:

左节点:由于只有一个数据,所以,左节点为(8,1)

右节点:右节点为空。

最终,就可以构建整个的kd-tree了。

邻近搜索

给定一个KDTree和一个节点,求KDTree中离这个节点最近的节点.(这个节点就是最临近点)

这里距离的求法用的是欧式距离。



基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。

这里还有几个细节需要注意一下,如下图,假设标记为星星的点是 test point, 绿色的点是找到的近似点,在回溯过程中,需要用到一个队列,存储需要回溯的点,在判断其他子节点空间中是否有可能有距离查询点更近的数据点时,做法是以查询点为圆心,以当前的最近距离为半径画圆,这个圆称为候选超球(candidate hypersphere),如果圆与回溯点的轴相交,则需要将轴另一边的节点都放到回溯队列里面来。


判断轴是否与候选超球相交的方法可以参考下图:



下面再用一个例子来具体说一下查询的过程。

假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。
我们来查找点(2.1,3.1),在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2), (5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;
然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如下图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。
于是在回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索。
至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。



再举一个稍微复杂的例子,我们来查找点(2,4.5),在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7),然后search_path中的结点为<(7,2), (5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;
然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,如下图,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2), (2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。
回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)
回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。



所以在搜索中可能会出现不同的情况,比如下面的两张图就是比较极端的两个例子。



代码清单

以下是k-d树的c++代码实现,包括建树过程和搜索过程。算法main函数输入k-d树训练实例点,算法会完成建树操作,随后可以输入待查询的目标点,程序将会搜索K-d树找出与输入目标点最近邻的训练实例点。本程序只实现了1近邻搜索,如果要实现k近邻搜索,只需对程序稍作修改。比如可以对每个结点添加一个标记,如果已经输出该结点为最近邻结点,那么就继续查找次近邻的结点,直到输出k个结点后算法结束。

简介kd树(k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。一个KDTree的例子上图的树就是一棵KDTree,形...

加密算法的对比和总结

phpmianshi6年前 (2015-11-03)算法179
一、单向散列算法也称为Hash(哈希)算法。是一种将任意长度的消息压缩到某一固定长度(消息摘要)的函数(该过程不可逆)。Hash函数可用于数字签名、消息的完整性检测、消息起源的认证检测等。常见的散列算...

腾讯面试题:10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

phpmianshi6年前 (2015-04-14)算法329
题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。关...

归并排序,外排序,10G文件500M内存的排序

phpmianshi6年前 (2015-04-13)算法330
归并排序,外排序,10G文件500M内存的排序
归并排序可以是一种外排序, 外排序是指利用外存也就是磁盘进行排序的一种简称。典型的应用是hadoop 的 mapreduce 的merge 阶段归并排序的: 假设有n 个元素, 将n 个元素分程x 组...