kd树方法

优质

小牛编辑

125浏览

2023-12-01

kd树方法

$$kd$$树是一种对$$k$$维空间中的实例点进行存储以便对其进行快速检索的树形结构。它是二叉树，表示对$$k$$维空间的一个划分（partition）。构造$$kd$$树相当于不断地用垂直于坐标轴的超平面将$$k$$维空间划分，构成一列的$$k$$维超矩形区域。$$kd$$树的每个节点对应于一个$$k$$维超矩形区域。

pic source: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/moretrees.php

1. 构造平衡$$kd$$树算法

输入：$$k$$维空间数据集$$T={x{(1)},x{(2)},...,x{(m)}}$$，其中$$x{(i)}=(x_1, x_2, ..., x_k)^T$$，$$i=1,2,...,m$$

**输出：**kd树

1）开始：构造根节点，根节点对应于包含$$T$$的$$k$$维空间的超矩形区域。

选择$$x_1$$为坐标轴，以$$T$$中所有实例的$$x_1$$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$$x_1$$垂直的超平面实现。

由根节点生成深度为1的左右子树：左子树对应于坐标$$x_1$$的值小于切分点的子区域，右子树对应于坐标$$x_1$$的值大于切分点的子区域。

将落在切分超平面上的实例点保存在根节点。

2）重复：对于深度为$$l$$的节点，选择$$x_j$$为切分的坐标轴，$$j=l\pmod k+1$$，举例来讲就是第一次切分选择坐标$$x_1$$，第二次选择坐标$$x_2$$，第三次选择坐标$$x_3$$，当$$k$$维后，返回到$$x_1$$继续作为切分坐标。切分由通过切分点并与轴$$x_j$$垂直的超平面实现。

对于左右子树，以$$x_j$$坐标的中位数为切分点，并保存为子树的根节点，然后同样分成两个子树。

3）直到两个子区域没有实例存在时停止，从而形成$$kd$$树的区域划分。