|
转自：http://blog.csdn.net/pipisorry/article/details/52186307 海量数据最近邻查找的kd-tree简介利用Octree，為封閉的3D空間建立一個資料結構來管理空間中的每個元素。如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。 3D空間可以用Octree，2D空間可以用Quadtree(四元樹，概念跟Octree一樣)。那麼4D空間呢？5D空間呢？ .... 遇到多維度的空間時，要怎麼去建立一個資料結構來有效管理呢？K-d tree 可以解決這個問題，這是由 Bentley [1] 在 1975年所提出的概念並發表在ACM (Association for Computing Machinery)上。 本文的主要目的是讲一下如何创建k-d tree对特征点集合进行数据组织和使用k-d tree来进行最近邻搜索。 k-d树（k-dimensional），是一种分割k维数据空间的数据结构（对数据点在k维空间中划分的一种数据结构），是一种高维索引树形数据结构。K-D树是二进制空间分割树的特殊的情况。其实，Kd-树是一种平衡二叉树。 主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。常用于在大规模的高维数据空间进行最近邻查找(Nearest Neighbor)和近似最近邻查找(Approximate Nearest Neighbor)，例如图像检索和识别中的高维图像特征向量的K近邻查找与匹配。 Kd-Tree与一维二叉查找树之间的区别二叉查找树：数据存放在树中的每个结点（根结点、中间结点、叶子结点）中； 应用背景SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻，现在提出了很多高维空间索引结构和近似查询的算法，k-d树就是其中一种。 为了更好的引出k-d tree，先讲一讲最近邻搜索。 最近邻搜索最近邻的数学形式的定义给定一个多维空间 None-nearer如下定义：
上面的公式中距离度量是欧式距离，当然也可以是任何其他Lp-norm。
其中di是向量d的第i个分量。 朴素最近邻搜索现在再来说最近邻搜索，如何找到一个这样的d’，它离d的距离在E中是最近的。 很容易想到的一个方法就是线性扫描，也称为穷举搜索，依次计算样本集E中每个样本点到d的距离，然后取最小距离的那个点。这个方法又称为朴素最近邻搜索。当样本集E较大时（在物体识别的问题中，可能有数千个甚至数万个SIFT特征点），显然这种策略是非常耗时的。 k-d tree的简介及表示 表示因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。k-d tree是索引树中的一种典型的方法。 k-d tree是英文K-dimension tree的缩写，是对数据点在k维空间中划分的一种数据结构。k-d tree实际上是一种二叉树。每个结点的内容如下：
样本集E由k-d tree的结点的集合表示，每个结点表示一个样本点，dom_elt就是表示该样本点的向量。该样本点根据结点的分割超平面将样本空间分为两个子空间。左子空间中的样本点集合由左子树left表示，右子空间中的样本点集合由右子树right表示。分割超平面是一个通过点dom_elt并且垂直于split所指示的方向轴的平面。 举个简单的例子，在二维的情况下，一个样本点可以由二维向量(x,y)表示，其中令x维的序号为0，y维的序号为1。假设一个结点的dom_elt为(7,2) ，split的取值为0，那么分割超面就是x=dom_elt(0)=7，它垂直与x轴且过点(7,2)，如下图所示：
（红线代表分割超平面） 于是其他数据点的x维（第split=0维）如果小于7，则被分配到左子空间；若大于7，则被分配到右子空间。例如，（5,4）被分配到左子空间，（9，6）被分配到右子空间。如下图所示:
从上面的表也可以看出k-d tree本质上是一种二叉树，因此k-d tree的构建是一个逐级展开的递归过程。 并且从这个过程中可知，内部节点都在分割面上，而叶子节点都在某个分割区域中。 kdtree的构建 过程怎样构造一棵Kd-tree？对于Kd-tree这样一棵二叉树，我们首先需要确定怎样划分左子树和右子树，即一个K维数据是依据什么被划分到左子树或右子树的。 Kd-Tree的构建算法（1） 在K维数据集合中选择具有最大方差的维度k，然后在该维度上选择中值m为pivot对该数据集合进行划分，得到两个子集合；同时创建一个树结点node，用于存储<k, m>； 给定二维数据集合：(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)，利用上述算法构建一棵Kd-tree。左图是Kd-tree对应二维数据集合的一个空间划分，右图是构建的一棵Kd-tree。 1）k-d tree[5] 把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。 (1)选择特征的方法 计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。 （2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。 第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。 替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。 （3）达到什么条件算法结束 实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。
图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。 分裂结点选择程序分裂结点的选择通常有多种方法，最常用的是一种方法是：对于所有的样本点，统计它们在每个维上的方差，挑选出方差中的最大值，对应的维就是split域的值。数据方差最大表明沿该维度数据点分散得比较开，这个方向上进行数据分割可以获得最好的分辨率；然后再将所有样本点按其第split维的值进行排序，位于正中间的那个数据点选为分裂结点的dom_elt域。 每次对子空间的划分时，怎样确定在哪个维度上进行划分？ 最简单的方法就是轮着来，即如果这次选择了在第i维上进行数据划分，那下一次就在第j(j≠i)维上进行划分，例如：j = (i mod k) + 1。想象一下我们切豆腐时，先是竖着切一刀，切成两半后，再横着来一刀，就得到了很小的方块豆腐。可是“轮着来”的方法是否可以很好地解决问题呢？再次想象一下，我们现在要切的是一根木条，按照“轮着来”的方法先是竖着切一刀，木条一分为二，干净利落，接下来就是再横着切一刀，这个时候就有点考验刀法了，如果木条的直径（横截面）较大，还可以下手，如果直径较小，就没法往下切了。因此，如果K维数据的分布像上面的豆腐一样，“轮着来”的切分方法是可以奏效，但是如果K维度上数据的分布像木条一样，“轮着来”就不好用了。因此，还需要想想其他的切法。 如果一个K维数据集合的分布像木条一样，那就是说明这K维数据在木条较长方向代表的维度上，这些数据的分布散得比较开，数学上来说，就是这些数据在该维度上的方差（invariance）比较大，换句话说，正因为这些数据在该维度上分散的比较开，我们就更容易在这个维度上将它们划分开，因此，这就引出了我们选择维度的另一种方法：最大方差法（max invarince），即每次我们选择维度进行划分时，都选择具有最大方差维度。 在某个维度上进行划分时，怎样确保在这一维度上的划分得到的两个子集合的数量尽量相等，即左子树和右子树中的结点个数尽量相等？假设当前我们按照最大方差法选择了在维度i上进行K维数据集S的划分，此时我们需要在维度i上将K维数据集合S划分为两个子集合A和B，子集合A中的数据在维度i上的值都小于子集合B中。首先考虑最简单的划分法，即选择第一个数作为比较对象（即划分轴，pivot），S中剩余的其他所有K维数据都跟该pivot在维度i上进行比较，如果小于pivot则划A集合，大于则划入B集合。把A集合和B集合分别看做是左子树和右子树，那么我们在构造一个二叉树的时候，当然是希望它是一棵尽量平衡的树，即左右子树中的结点个数相差不大。而A集合和B集合中数据的个数显然跟pivot值有关，因为它们是跟pivot比较后才被划分到相应的集合中去的。好了，现在的问题就是确定pivot了。给定一个数组，怎样才能得到两个子数组，这两个数组包含的元素个数差不多且其中一个子数组中的元素值都小于另一个子数组呢？方法很简单，找到数组中的中值（即中位数，median），然后将数组中所有元素与中值进行比较，就可以得到上述两个子数组。同样，在维度i上进行划分时，pivot就选择该维度i上所有数据的中值，这样得到的两个子集合数据个数就基本相同了。 kdtree最近邻查找的算法过程构建好一棵Kd-Tree后，下面给出利用Kd-Tree进行最近邻查找的算法： （1）将查询数据Q从根结点开始，按照Q与各个结点的比较结果向下访问Kd-Tree，直至达到叶子结点。 怎样判断未被访问过的树分支Branch里是否还有离Q更近的点？从几何空间上来看，就是判断以Q为中心center和以Dcur为半径Radius的超球面（Hypersphere）与树分支Branch代表的超矩形（Hyperrectangle）之间是否相交。 kdtree算法实现构建kd-tree算法的伪代码1 构建k-d树的伪码
算法：createKDTree 构建一棵k-d tree k-d tree的最近邻搜索算法如前所述，在k-d tree树中进行数据的k近邻搜索是特征匹配的重要环节，其目的是检索在k-d tree中与待查询点距离最近的k个数据点。 最近邻搜索是k近邻的特例，也就是1近邻。将1近邻改扩展到k近邻非常容易。下面介绍最简单的k-d tree最近邻搜索算法。 基本的思路很简单：首先通过二叉树搜索（比较待查询节点和分裂节点的分裂维的值，小于等于就进入左子树分支，等于就进入右子树分支直到叶子结点），顺着“搜索路径”很快能找到最近邻的近似点，也就是与待查询点处于同一个子空间的叶子结点；然后再回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径）。重复这个过程直到搜索路径为空。下面给出k-d tree最近邻搜索的伪代码： 算法：kdtreeFindNearest /* k-d tree的最近邻搜索 */ k-d tree的构建过程及搜索实例示例1 假设样本集为：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。构建过程如下： （1）确定split域，6个数据点在x,y维度上的数据方差分别为39, 28.63。在x轴上方差最大，所以split域值为0（x维的序号为0） （2）确定分裂节点，根据x维上的值将数据排序，则6个数据点再排序后位于中间的那个数据点为(7,2)，该结点就是分割超平面就是通过(7,2)并垂直于split=0(x)轴的直线x=7 （3）左子空间和右子空间，分割超面x=7将整个空间氛围两部分，x<=7的部分为左子空间，包含3个数据点{(2,3), (5,4), (4,7)}；另一部分为右子空间，包含2个数据点{(9,6), (8,1)}。如下图所示 （4）分别对左子空间中的数据点和右子空间中的数据点重复上面的步骤构建左子树和右子树直到经过划分的子样本集为空。下面的图从左至右从上至下显示了构建这棵二叉树的所有步骤：
示例2 假设有六个二维数据点 = {（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间中。为了能有效的找到最近邻，Kd-树采用分而治之的思想，即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为：
示例3 假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。将上面的图转化为树形图的样子如下：
我们来查找点(2.1,3.1)，在(7,2)点测试到达(5,4)，在(5,4)点测试到达(2,3)，然后search_path中的结点为<(7,2), (5,4), (2,3)>，从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141； 然后回溯至(5,4)，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆，并不和超平面y=4相交，如下图，所以不必跳到结点(5,4)的右子空间去搜索，因为右子空间中不可能有更近样本点了。
于是在回溯至(7,2)，同理，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆并不和超平面x=7相交，所以也不用跳到结点(7,2)的右子空间去搜索。 至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2.1,3.1)的最近邻点，最近距离为0.141。 示例4 再举一个稍微复杂的例子，我们来查找点(2,4.5)，在(7,2)处测试到达(5,4)，在(5,4)处测试到达(4,7)，然后search_path中的结点为<(7,2), (5,4), (4,7)>，从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202； 然后回溯至(5,4)，以(2,4.5)为圆心，以dist=3.202为半径画一个圆与超平面y=4相交，如下图，所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中，现在search_path中的结点为<(7,2), (2, 3)>；另外，(5,4)与(2,4.5)的距离为3.04 < dist = 3.202，所以将(5,4)赋给nearest，并且dist=3.04。
回溯至(2,3)，(2,3)是叶子节点，直接平判断(2,3)是否离(2,4.5)更近，计算得到距离为1.5，所以nearest更新为(2,3)，dist更新为(1.5) 回溯至(7,2)，同理，以(2,4.5)为圆心，以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。 至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2,4.5)的最近邻点，最近距离为1.5。 两次搜索的返回的最近邻点虽然是一样的，但是搜索(2, 4.5)的过程要复杂一些，因为(2, 4.5)更接近超平面。研究表明，当查询点的邻域与分割超平面两侧的空间都产生交集时，回溯的次数大大增加。最坏的情况下搜索N个结点的k维kd-tree所花费的时间为：
复杂度分析对于拥有n个已知点的kD-Tree，其复杂度如下： 把最邻近点算法扩展成K-最邻近点算法... k-d tree的扩展Kd-tree with BBF由于大量回溯会导致kd-tree最近邻搜索的性能大大下降，因此研究人员也提出了改进的k-d tree近邻搜索。 其中一个比较著名的就是 Best-Bin-First，它通过设置优先级队列和运行超时限定来获取近似的最近邻，有效地减少回溯的次数。 [KD Tree] [从K近邻算法、距离度量谈到KD树、SIFT+BBF算法]* K值的选择 除了上述1.2节如何定义邻居的问题之外，还有一个选择多少个邻居，即K值定义为多大的问题。不要小看了这个K值选择问题，因为它对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说： k-d tree的实现库伪代码： [scipy.spatial.KDTree][scipy.spatial] [KD-tree的原理以及构建与查询操作的python实现]c/c++: [kdtree A simple C library for working with KD-Trees] [http://code.google.com/p/kdtree/] [https://github.com/sdeming/kdtree] Java: [KD-Tree Implementation in Java and C#] from: http://blog.csdn.net/pipisorry/article/details/52186307 ref: [wiki: Paper |
|
|
，把
中的一个向量成为一个样本点或数据点。
中样本点的有限集合称为样本集。给定样本集E，和一个样本点d，d的最近邻就是任何样本点d’∈E满足None-nearer(E,d,d’)。
