kd-tree算法简介

k近邻问题是一种常见的问题,它是给定训练数据集,对输入实例而在训练数据集中找到与该实例中最近的k个实例。如果k=1,那么就是最近邻问题。对于k近邻问题,如果用线性扫描(暴力)的方法会比较慢,我们可以用kd-tree这种数据结构来进行高效地解决。

kd树是一种分割k维空间的数据结构。我们将一个空间进行不断地划分,选择一个坐标轴然后在此坐标轴的一个切分点,垂直做一条先,进行拆分成左右两个区域。直至子区域内没有点为止。然后对于查询的点,我们就按照树的遍历顺序进行查询。但是这个过程可能并不完全包括了正确的点,所以我们需要在回溯的时候对于需要的另一个分支进行查询。是哪些点需要在回溯的时候继续遍历呢?简单来说,就是按照查询的点和选择的点进行画圆,如果其覆盖的区域包括了另一个分支,那么就需要执行另一个分支。

下面通过展示一个建树和查询的实例,来对于kd树有一个更清晰的认识。其中Node-data代表的数据集中某个数据点。split数组则是垂直于分割超平面的方向轴序号。

例子比较简单,只有两维,即x轴和y轴。所以可以简单地给x,y两个方向轴编号为0,1,也即split={0,1}。

建立kd树

(1)确定split域的首先该取的值。分别计算x,y方向上数据的方差得知x方向上的方差最大,所以split域值首先取0,也就是x轴方向;

(2)确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7,所以Node-data = (7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于split = 0(x轴)的直线x = 7;

(3)确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分,如图2所示。x < = 7的部分为左子空间,包含3个节点{(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点{(9,6),(8,1)}。

《kd-tree算法简介》

图1 x=7将整个空间分为两部分

  如算法所述,k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点(5,4)和(9,6)(也就是左右子空间的’根’节点),同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点,如图1所示。最后生成的k-d树如图3所示。

《kd-tree算法简介》

图2 上述实例生成的k-d树

kd树上的查询

在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。

  星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻,还需要进行’回溯’操作:算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,然后回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如图4所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中去搜索。

《kd-tree算法简介》

图3 查找(2.1,3.1)点的两次回溯判断

  再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。

  一个复杂点了例子如查找点为(2,4.5)。同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,取(4,7)为当前最近邻点,计算其与目标查找点的距离为3.202。然后回溯到(5,4),计算其与查找点之间的距离为3.041。以(2,4.5)为圆心,以3.041为半径作圆,如图5所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找。此时需将(2,3)节点加入搜索路径中得<(7,2),(2,3)>。回溯至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5。回溯至(7,2),以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如图6所示。至此,搜索路径回溯完。返回最近邻点(2,3),最近距离1.5。k-d树查询算法的伪代码如表3所示。

《kd-tree算法简介》

图4 查找(2,4.5)点的第一次回溯判断

《kd-tree算法简介》

图6 查找(2,4.5)点的第二次回溯判断

时间复杂度

最后关于时间复杂度上,根据科学研究(我并不会算)其时间复杂度为O(kn^(1-1/k)。需要注意的是,一般来说要求数据的规模N满足N»2D,才能达到高效的搜索。所以我们举的例子k=2,是非常好的应用场景。

然后贴一下我的代码,是hdu5992的代码 。这个代码必须要G++下交,c++下TLE(我觉得应该是对于nth_element的支持不同)
注释掉的是hdu4347,这两个题的维度分别是5和3,n>>2^k,因此kd树非常合适。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注