k-d 树

  k-d 树(k-维树的缩写)是一种对k维空间中的实例点进行存储以方便对齐进行快速检索的树形数据结构,k-d 树可以用于于多维空间关键数据的搜索,例如范围搜索和最近邻搜索。

  k-d 树是每个节点都为k维点的二叉树,表示对 k 维空间的一个划分。构造k-d树相当于不断地用垂直于坐标轴的超平面将k维空间进行无重叠切分(Clipping,对应的一种切分方式是 Overlapping,代表结构 R 树),构成一系列的k维超矩形区域。k-d 树的每个结点对应于一个k维超矩形区域。所有非叶子节点可以视作用一个超平面把空间分区成两部分。在超平面左边的点代表节点的左子树,在超平面右边的点代表节点的右子树。超平面的方向可以用下述方法来选择:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照 x 轴划分,所有 x 值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法矢为 x 轴的单位矢量。

  构造 k-d 树的方法如下:构造根节点,使根节点对应于k维空间中包含所有实例点的超矩形区域;通过下面的递归方法,不断地对k维空间进行划分,生成子节点。在超矩形区域上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域且分为左右两个子区域;这时,实例点被分到两个子区域。这个过程知道子区域内没有实例时终止,终止时的结点即为叶子结点。在此过程中,将实例保存到相应的结点上。

  在构造 k-d 树的过程中,选择一个“好”的根节点很重要,根节点的选择虽然不会影响构造正确的 k-d 树,但是会影响树的最大深度以及超平面空间的形状是否均衡。分裂结点的选择通常有多种方法,最常用的是一种方法是:对于所有的样本点,统计它们在每个维上的方差,挑选出方差中的最大值,对应的维就是 split 域的值。数据方差最大表明沿该维度数据点分散得比较开,这个方向上进行数据分割可以获得最好的分辨率,然后再将所有实例点按其第 split 维的值进行排序,位于正中间的那个实例点选为分裂结点。通常,依次选择坐标轴对空间切分,选择训练实例点在选定的坐标轴上的中位数为切分点,这样得到的 k-d 树是平衡的,但是平衡的 k-d 树搜索时未必是效率最优的结构。

  表1给出的是 k-d 树每个节点中主要包含的数据结构。

数据名称

数据类型

描述

node

矢量

样本中某个 k 维实例点

range

矢量

该节点所代表的空间范围

split

整数

分裂维的序号,垂直于分割超平面的方向轴序号

left

k-d树

由位于该节点分割超平面左子空间内所有数据点所构成的k-d树

right

k-d树

由位于该节点分割超平面右子空间内所有数据点所构成的k-d树

  举个简单的例子,在二维的情况下,一个样本点可以由二维向量(x,y)表示,其中令 x 维的序号为0,y 维的序号为1。假设一个样本点为(7,2),split 的取值为0,那么分割超面就是 x=7,它垂直与 x 轴且过点(7,2)。

  采用中位数选择切分的方法,下面的 Python 代码描述的具体的构造 k-d 树的过程

01 class Node: pass

02

03 def kdtree(point_list, depth=0):

04

05    if not point_list:

06        return None

07

08    # Select axis based on depth so that axis cycles through all valid values

09    k = len(point_list[0]) # assumes all points have the same dimension

10    axis = depth % k

11

12    # Sort point list and choose median as pivot element

13    point_list.sort(key=lambda point: point[axis])

14    median = len(point_list) // 2 # choose median

15

16    # Create node and construct subtrees

17    node = Node()

18    node.location = point_list[median]

19    node.left_child = kdtree(point_list[:median], depth + 1)

20    node.right_child = kdtree(point_list[median + 1:], depth + 1)

21    return node

  以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图中黑点所示。k-d 树算法就是要确定下图中这些分割空间的分割线(多维空间即为分割平面,一般为超平面)。利用上面的构造算法可以对二维空间进行划分。

300px-Kdtree_2d.svg

图1

  最后生成的k-d树如下图所示

300px-Tree_0001.svg[4]

图2

最邻近查找算法(Nearest Search)

  现在再来说最近邻搜索,如何在样本集中找到一个实例点,使其离目标点的距离在样本中是最近的。很容易想到的一个方法就是线性扫描,也称为穷举搜索,依次计算样本集中每个实例点到目标点的距离,然后取最小距离的那个点。这个方法又称为朴素最近邻搜索。当样本集较大时,显然这种策略是非常耗时的。

  因为实际数据一般都会呈现簇状的聚类形态,因此我们想到建立数据索引,然后再进行快速匹配。索引树是一种树结构索引方法,其基本思想是对搜索空间进行层次划分。k-d tree是索引树中的一种典型的方法。利用 k-d 树可以省去对大部分数据点的搜索,从而减少搜索的计算量。

  下面以最近邻为例讲述搜索过程。

  给定一个目标点,搜索其最近邻,首先通过二分搜索,顺着“搜索路径”很快能找到最近邻的近似点,也就是与目标点处于同一个子空间的叶子结点;然后从该叶子结点回溯,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索,并将其他子结点加入到搜索路径。重复这个过程直到搜索路径为空。这样搜索就被限制在空间的局部区域上了,提高了搜索效率。

  包含目标点的叶节点对应包含目标点的最小超矩形区域。以此叶节点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最临近点的超球体的内部,然后返回当前结点的父节点,如果父节点的另一子节点的超矩形区域与超球体相交,那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点,将此点作为新的当前最近点。算法转到更上一级的父节点,继续上述过程。如果父节点的另一子节点的超矩形区域与超球体不相交,或不存在比当前最近点更近的点,则停止搜索。 

  下面给出 k-d 树最近邻搜索的伪代码:

01 算法:kdtreeFindNearest /* k-d tree的最近邻搜索 */

02 输入:kd /* k-d tree类型*/

03 输出 : nearest /* 最近邻实例点 */

04 target /* 目标点 */ 

05 dist /* 最近邻和目标点的距离 */

06

07 1. 如果kd是空的,则设dist为无穷大返回

08

09 2. 向下搜索直到叶子结点

10

11 pSearch = &kd

12 while(pSearch != NULL)

13 { 

14     pSearch加入到search_path;

15     if(target[pSearch->split] <= pSearch->node[pSearch->split]) /* 如果小于就进入左子树 */ 

16     { 

17         pSearch = pSearch->left;

18     } 

19     else 

20     { 

21         pSearch = pSearch->right;

22     } 

23 } 

24 取出search_path最后一个赋给nearest 

25 dist = Distance(nearest, target);

26

27 3. 回溯搜索路径

28

29 while(search_path不为空)

30 { 

31     取出search_path最后一个结点赋给pBack

32

33     if(pBack->left为空 && pBack->right为空) /* 如果pBack为叶子结点 */

34     {

35         if( Distance(nearest->node, target) > Distance(pBack->node, target) )

36         {

37             nearest = pBack;

38             dist = Distance(pBack->node, target);

39         }

40     }

41     else

42     {

43         split = pBack->split;

44         if(abs(pBack->node[split] target[split]) < dist) /* 如果以target为中心的圆(球或超球),半径为dist的圆与分割超平面相交, 那么就要跳到另一边的子空间去搜索 */ 

45         { 

46             if( Distance(nearest->node, target) > Distance(pBack->node, target) )

47             { 

48                 nearest = pBack;

49                 dist = Distance(pBack->dom_elt, target);

50             } 

51             if(target[s] <= pBack->node[s]) /* 如果target位于pBack的左子空间,那么就要跳到右子空间去搜索 */ 

52                 pSearch = pBack->right;

53             else 

54                 pSearch = pBack->left;      /* 如果target位于pBack的右子空间,那么就要跳到左子空间去搜索 */ 

55             if(pSearch != NULL)

56                 pSearch加入到search_path 

57         }

58     }

59 }

  这里先以一个简单的实例来描述最邻近查找的基本思路。

  星号表示要查询的目标点(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为半径画圆,如图3所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)结点的右子空间中去搜索,因为右子空间中不可能有更近的实例点了。

下载[4]

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

  于是,再回溯到结点(7,2),以目标点(2.1,3.1)为圆心,以0.1414为半径的圆更不会与超平面 x = 7 相交,因此不用进入(7,2)的右子空间进行搜索。至此,整个搜索路径为空,结束整个搜索,返回结点(2,3)作为目标点(2.1,3.1)的最近邻点,最近距离为0.141。

  一个复杂点的例子如目标点为(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为半径作圆,如图4所示。可见该圆与超平面 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 相交,如图5所示。至此,搜索路径回溯完毕。返回最近邻点(2,3),最近距离1.5。

下载 (1)[4]

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

下载 (2)[4]

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

  两次搜索的返回的最近邻点虽然是一样的,但是搜索(2, 4.5)的过程要复杂一些,因为(2, 4.5)更接近超平面。研究表明,当目标点的邻域与分割超平面两侧的空间都产生交集时,需要查找另一侧子空间,回溯的次数大大增加。导致检索过程复杂,效率下降。

  一般来讲,最临近搜索只需要检测几个叶子结点即可,如下图所示:

general

  但是,如果当实例点的分布比较糟糕时,几乎要遍历所有的结点,如下所示:

bad_distribution

  研究表明 N 个节点的 k-d 树搜索过程时间复杂度最坏的情况下是 110e6db9ffaedb472bf923da6236b00d[4]。如果实例点是随机分布的,k-d 树搜索的平均计算复杂度是 O(logN)。k-d 树更适用于训练实例 N >> 2k 的情况,因此空间维数不能太高,一般不大于20维,当空间维数接近实例数时,它的效率会迅速下降,几乎接近贪婪线性扫描。由于大量回溯会导致 k-d 树最近邻搜索的性能大大下降,因此研究人员也提出了改进的 k-d 树近邻搜索算法,其中一个比较著名的就是 Best-Bin-First,它通过设置优先级队列和运行超时限定来获取近似的最近邻,有效地减少回溯的次数。

  最后,可以用这个 k-d tree applet 去体会一下。

  该方法可以修改后用于 K 近邻搜索,即通过维护一个包含 k 个最近邻结点的队列来实现。

  参考资料:

  1. http://en.wikipedia.org/wiki/K-d_tree

  2. http://goo.gl/XJC7Y

  3. 统计机器学习,李航

  4. An intoductory tutorial on kd-trees, Andrew W.Moore

k-d 树》上有4条评论

  1. 在搜索KD-tree的第一步“利用二分查找”搜索最近的叶子节点的过程,是不是和建立KD-tree的策略一样呢?(比如如果插入的时候,按照第一层比较x坐标,第二层比较y坐标……等进行插入,那么搜索的时候也是按照这个顺序进行比较是么?)

  2. (5, 4)结点的右子空间中不可能有更近的实例点了,我认为就没有必要再回溯到(7, 2)了吧?这与你之前说的是不是矛盾啊?

  3. 楼主,要参考http://en.wikipedia.org/wiki/K-d_tree,把你那个复杂例子的回溯过程在修正一下,你的顺序貌似写错了

发表评论

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