[关闭]
@markheng 2017-01-17T08:10:19.000000Z 字数 2280 阅读 2338

k-d树,k-d tree

数据结构


k-d树是查找相邻点很重要的一种数据结构。

索引结构中相似性查询有两种基本的方式:一种是范围查询(range searches),另一种是K近邻查询(K-neighbor searches)。
范围查询就是给定查询点和查询距离的阈值,从数据集中找出所有与查询点距离小于阈值的数据;
K近邻查询是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,就是最近邻查询(nearest neighbor searches)。

特征匹配算子可以风风能为两类,一类是线性扫描法(穷举),一类是建立数据索引,然后进行快速匹配。

k-d树是索引树的一种。划分的空间没有混叠(clipping)的,另一种划分空间是有混叠(overlapping)的。

k-d树的算法分为两类,一类是有关k-d树的构建算法,一类是在k-d树上进行邻近查找的算法。

k-d树的构建算法

k-d是k-dimension的缩写,是对数据点在k维空间中划分的一种数据结构。k-d树实际上是一种二叉树。
它结点内容包括:

数据名 类型 解释
dom_elt k维的向量 k维空间中的一个点,k-d树在某个维度以这个点为界进行划分
split 正数 表示进行划分的维数的序号
left kd-tree 左子树
right kd-tree 右子树

注意split是当前结点进行划分的维数的序号,序号只是为了在算法中表示方便,其实就是维度的标识。

算法描述

split选取
选取split时,为了得到较好的划分效果(较高的分辨率),通常做法是,计算每个维度的方差σi,如果σpσi中最大的,那么取维度p作为split。

dom_elt选取
将所有元素按照split维的数值大小进行排序,取最中间的那个元素作为dom_elt。

建立子树
假设ele为k维空间中的任意,对dom_elt一侧的数据(ele[split]dom_elt[split])建立左子树,树根为当前结点的左子结点。另一侧的数据(ele[split]>dom_elt[split])建立右子树,树根为当前结点的右子节点。

伪代码
算法:构建k-d树(build_kd_tree)
输入:k维点集ele_set
输出:k-d树 kd_t

  1. 如果ele_set 为空,则返回空
  2. 调用选择分裂点的子程序,得到分裂点dom_elt和分裂的维度split
  3. ele_set_left = {e|eele_set,e[split]dom_elt[split]}
    ele_set_right = {e|eele_set,e[split]>dom_elt[split]}
  4. build_kd_tree(ele_set_left)
    build_kd_tree(ele_set_right)

分裂点指的是结点中的dom_elt值,标识了当前分裂的界线。

k-d树的邻近查找

  1. 算法:k-d树查找target点的最近邻点(find_kd_tree)
  2. 输入:k-dkd_tree, 目标点 target
  3. 输出:目标的最近邻点nearest, 最近距离dist
  4. 1. 如果kd_tree为空,则设dist为无穷大,返回
  5. 2. 搜索k-d树直到叶子结点,记录搜索过的路径
  6. pSearch 指向 kd_tree的根节点
  7. while(pSearch指向的结点p不是叶子结点)
  8. {
  9. p加入到search_path
  10. if(target[p.split] <= p.dom_elt[p.split]){
  11. pSearch指向当前结点的左子树
  12. }else{
  13. pSearch指向当前结点的右子树
  14. }
  15. }
  16. 取出search_path中最后一个赋值给nearest
  17. dist = Distance(nearest, target)
  18. 3. 回溯搜索路径
  19. while(search_path 不为空)
  20. {
  21. pBack = search_path最后一个元素
  22. if(pBack 为叶子结点)
  23. {
  24. if(Distance(nearset, target) >
  25. Distance(pBack->dom_elt, target) )
  26. {
  27. nearset = pBack->dom_elt
  28. dist = Distance(pBack->dom_elt, target)
  29. }
  30. }
  31. else
  32. {
  33. s = pBack->split
  34. if(abs(pBack->dom_elt[s] - target[s]) < dist)
  35. {
  36. if( Distance(nearest, target) >
  37. Distance(pBack->dom_elt, target) )
  38. {
  39. nearest = pBack->dom_elt;
  40. dist = Distance(pBack->dom_elt, target);
  41. }
  42. if(target[s] <= pBack->dom_elt[s])
  43. pSearch = pBack->right;
  44. else
  45. pSearch = pBack->left;
  46. if(pSearch != NULL)
  47. pSearch加入到search_path
  48. }
  49. }
  50. }
  51. }

参考:
http://underthehood.blog.51cto.com/2531780/687160
k-d tree wikipedia
http://www.cnblogs.com/eyeszjwang/articles/2429382.html

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注