| kd树 | 您所在的位置：网站首页 › 2点9-1点3 › kd树 |
kd树
|
1.实例
假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图2中黑点所示）。k-d树算法就是要确定图2中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。下面就要通过一步步展示k-d树是如何确定这些分割线的。
k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。 2.构造kd树kd树是一种对k维空间中的实例点进行存储以便对其进行快速搜索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行切分，构成一系列的k维超矩形区域。kd树的每一个节点对应于一个k维超矩形区域。k-d树是一个二叉树，每个节点表示一个空间范围。下表给出的是k-d树每个节点中主要包含的数据结构。 从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。下面给出的是构建k-d树的伪码。 [cpp] view plain copy 算法：构建k-d树（createKDTree） 输入：数据点集Data-set和其所在的空间Range 输出：Kd，类型为k-d tree 1.If Data-set为空，则返回空的k-d tree 2.调用节点生成程序： （1）确定split域：对于所有描述子数据（特征矢量），统计它们在每个维上的数据方差。假设每条数据记录为64维，可计算64个方差。挑选出最大值，对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开，在这个方向上进行数据分割有较好的分辨率； （2）确定Node-data域：数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set' = Data-set \ Node-data（除去其中Node-data这一点）。 3.dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]} Left_Range = {Range && dataleft} dataright = {d属于Data-set' && d[split] > Node-data[split]} Right_Range = {Range && dataright} 4.left = 由（dataleft，Left_Range）建立的k-d tree，即递归调用createKDTree（dataleft，Left_Range）。并设置left的parent域为Kd； right = 由（dataright，Right_Range）建立的k-d tree，即调用createKDTree（dataleft，Left_Range）。并设置right的parent域为Kd。
以上述举的实例来看，过程如下： 由于此例简单，数据维度只有2维，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。 （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将整个空间分为两部分，如下图所示。x Node-data； //初始化最近邻点 while（Kd_point） push（Kd_point）到search_path中； //search_path是一个堆栈结构，存储着搜索路径节点指针 /*** If Dist（nearest，target） > Dist（Kd_point -> Node-data，target） nearest = Kd_point -> Node-data； //更新最近邻点 Max_dist = Dist(Kd_point，target）； //更新最近邻点与查询点间的距离 ***/ s = Kd_point -> split； //确定待分割的方向 If target[s] Node-data[s] //进行二叉查找 Kd_point = Kd_point -> left； else Kd_point = Kd_point ->right； nearest = search_path中最后一个叶子节点； //注意：二叉搜索时不比计算选择搜索路径中的最邻近点，这部分已被注释 Max_dist = Dist（nearest，target）； //直接取最后叶子节点作为回溯前的初始最近邻点 3. //回溯查找 while（search_path != NULL） back_point = 从search_path取出一个节点指针； //从search_path堆栈弹栈 s = back_point -> split； //确定分割方向 If Dist（target[s]，back_point -> Node-data[s]） right； //如果target位于左子空间，就应进入右子空间 else Kd_point = back_point -> left; //如果target位于右子空间，就应进入左子空间 将Kd_point压入search_path堆栈； If Dist（nearest，target） > Dist（Kd_Point -> Node-data，target） nearest = Kd_point -> Node-data； //更新最近邻点 Min_dist = Dist（Kd_point -> Node-data,target）； //更新最近邻点与查询点间的距离
当维数较大时，直接利用k-d树快速检索的性能急剧下降。假设数据集的维数为D，一般来说要求数据的规模N满足条件：N远大于2的D次方，才能达到高效的搜索。 |
【本文地址】