高维检索树

K-dimentional Tree

Kd树:循环遍历各维度,按该维度取值二分数据

  • 对高维数据进行快速搜索二叉树

    • 超平面都垂直于轴的BSPTree
  • Kd树对样本点的组织表示对k维空间的划分

    • 每个节点对应k维空间中超矩形区域
    • 构造kd树相当于用垂直于坐标轴超平面不断划分k维空间, 得到一系列超矩形区域
  • Kd树构建目标

    • 树应该尽量平衡,即分割应尽量均匀
    • 最大化邻域搜索的剪枝

建树

  • 输入:数据点$X_i, i=1,2,\cdots,N$
  • 确定划分维度(轴)
    • 选择方差最大的轴,使得数据尽量分散
    • 按次序循环遍历所有轴:方便查找时定位轴
  • 选择该维度上数值中位数作为划分点
    • 中位数查找方法
      • 各维度统一全体排序、记录
      • 抽样,使用样本中位数
    • 小于中位数的数据点划分至左子树,否则划分至右子树
  • 递归建立左、右子树直至无法继续划分
    • 节点中包含数据项数量小于阈值

查找K近邻

  • 输入:Kd树、目标点x
  • 在Kd树中找出包含目标点x的叶节点,以之为近邻点

    • 从根节点出发,与节点比较对应坐标值,递归访问至叶节点 为止
    • 目标点在训练样本中不存在,必然能够访问到叶节点
  • 沿树回溯,检查节点是否距离目标点更近,尝试更新

  • 检查该节点另一子区域是否可能具有更近距离的点

    • 即考察以目标点为圆心、当前近邻距离为半径圆,同划分轴 是否相交
    • 则只需比较目标点同相应切分平面距离、近邻距离
  • 若目标点同该对应切分平面距离小于近邻距离

    • 则将目标节点视为属于该子区域中的点
    • 从节点未访问子树开始重复以上步骤,进行近邻搜索
  • 否则继续回退

  • 退回到根节点时,搜索结束,近邻点

  • 回溯过程中需要盘对子域是否访问过,可以通过标记、比较相应 轴坐标等方式判断
  • k>1的情况类似,不过检测时使用最远近邻,新近邻需要和所有 原近邻依次比较

其他操作

插入新节点

  • 从根节点出发,根据待插入节点、当前节点在对应维度取值确定 插入左、右子树
  • 遍历直至叶子节点,插入

删除节点

  • 简单方法:将待删除节点子节点组成新集合,对其重新构建, 将新子树挂载在原被删节点位置

  • 分类讨论:设删除节点T对应划分维度为D

    • 节点无子树:直接删除
    • 节点有右子树
      • 在右子树寻找维度D取值最小节点P,替换被删除节点T
      • 在右子树递归处理删除节点P
    • 节点无右子树有左子树
      • 在左子树寻找维度D取值最小节点P,替换被删除节点T
      • 将T的左子树作为P的右子树
      • 在右子树递归处理删除节点P

查找维度D最小点

  • 若当前结点切分维度为D:只需查找左子树
  • 否则需要对左、右子树分别递归搜索

Vantage Point Tree

VP树:任选样本点,按照数据点与该点距离二分数据

  • 对高维数据进行快速搜索二叉树

  • VP树对样本点的组织表示对k维空间的划分

    • 每个节点对应k维空间中一个球形划分
    • 构造kd树相当于用以给定样本点为球心不断划分k维空间, 得到一系列球内、球外区域

建树

  • 输入:数据$X_i, i=1,2,\cdots,n$
  • 选择某数据点$X_v$作为划分球心
  • 计算其他数据点距离$D_i = d(X_i, X_v)$
  • 求出$D_i$中位数$M$
    • 与$X_v$距离$D_i \leq M$的数据点$D_i$划分至左子树
    • 与$X_v$距离$D_i \gt M$的数据点$D_i$划分至右子树

Rectangle Tree

R树:将空间划分为有重叠的

  • B树高维推广
    • 类似B树将一维区间划分为多个不重叠的子区间
    • 同样是平衡树,所有叶子位于同一层上
  • R树退化至1维有分割区间重叠问题,效果不如B树

性质

  • $M$:节点中最大键数量
  • $m \leq \frac M 2$:节点中条目最小数量
  • 非根叶节点包含$m-M$索引记录:$I$表示可在空间中完全覆盖 节点中条目点的MBR

  • 非根、非叶节点包含$m-m$个子节点:$I$表示可在空间中完全 覆盖节点中条目矩形的MBR

  • 根节点条目数$[2, m]$,除非为叶子节点

  • minimal bounding rectangleMBR,最小边界矩形

节点结构

  • 叶子节点结构:$(I, tuple-ids)$

    tree_hd_rtree_node_structure

    • $I((s_1, e_1), (s_2, e_2), \cdots, (s_n, e_n))$: n维空间中矩形
    • $tuple-ids$:节点包含的记录
  • 非叶节点:$(I, child-pointer)$

操作

建树

矩形搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SearchRect(T, S, ret):
// 利用R树搜索矩形范围中包含的记录点
// 输入:R树根节点T、待搜索矩形S
// 输出:矩形S覆盖的条目

if T.I join S == NULL:
return

// 若T不是叶子节点,检查其每个条目E
if not T.is_leaf():
for E in T.entries:
// 对与S相交E.I对应条目E,递归调用搜索
if T.I join S != NULL:
SearchRect(E, S, ret)

// 若T是叶子节点且T.I与S相交,检查其每个记录点
elif T.I join S != NULL:
for E in T.entries:
if E in S:
ret.add(E)

选择所属叶子

1
2
3
4
5
6
7
8
9
10
11
12
13
ChooseLeaf(T, E):
// 在R树中寻找新索引条目所属叶子节点
// 输入:R树根节点T、索引条目E
// 输出:E所属R树中叶子节点

if T.is_leaf():
Assert(E.is_subset(T))
return T

else:
for T_E in T.entries:
if E.is_subset(T_E)
return ChooseLeaf(T_E, E) or T_E

插入新条目

1
2
3
4
5
6
7
8
9
10
11
12
Insert(T, E):
// 向R树中插入新条目
// 输出:R树根T、新条目E

L = ChooseLeaf(T, E)
if L.has_slot():
L.add(E)
else:
LL = L.split()
L.add(E)
P = L.get_parent()

调整树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
AdjustTree(T, L):
// 从不满足节点开始调整R树至满足要求
// 输入:R树根T、不满足要求节点L
// 输出:

if L.is_root():
return

P = L.get_parent_node()
if L.splitted():
NN = L.get_split_node()
if P.
// 调整节点L在父节点中矩形框I大小
addjust_I(P.L.I)

R*-tree

X-tree

SS-tree

SR-Tree

Metric-tree

Author

UBeaRLy

Posted on

2019-06-04

Updated on

2019-06-04

Licensed under

Comments