kd树_kd树搜索 - CSDN
精华内容
参与话题
  • KD树详解及KD树最近邻算法

    千次阅读 2018-06-08 16:43:29
        一般说来,索引结构中相似性查询有两种基本的方式: 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据另一种是K近邻查询,就是...

        一般说来,索引结构中相似性查询有两种基本的方式:

    1. 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据
    2. 另一种是K近邻查询,就是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。

    2.1、什么是KD树

        Kd-树是K-dimension tree的缩写,是对数据点在k维空间(如二维(x,y),三维(x,y,z),k维(x1,y,z..)中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。本质上说,Kd-树就是一种平衡二叉树。

        首先必须搞清楚的是,k-d树是一种空间划分树,说白了,就是把整个空间划分为特定的几个部分,然后在特定空间的部分内进行相关搜索操作。想像一个三维(多维有点为难你的想象力了)空间,kd树按照一定的划分规则把这个三维空间划分了多个空间,如下图所示:

    2.2、KD树的构建

        kd树构建的伪代码如下图所示:

        再举一个简单直观的实例来介绍k-d树构建算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图所示。为了能有效的找到最近邻,k-d树采用分而治之的思想,即将整个空间划分为几个小部分,首先,粗黑线将空间一分为二,然后在两个子空间中,细黑直线又将整个空间划分为四部分,最后虚黑直线将这四部分进一步划分。

        6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}构建kd树的具体步骤为:

    1. 确定:split域=x。具体是:6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故split域值为x;
    2. 确定:Node-data = (7,2)。具体是:根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以Node-data域位数据点(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:split=x轴的直线x=7;
    3. 确定:左子空间和右子空间。具体是:分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)};
        如上算法所述,kd树的构建是一个递归过程,我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点(5,4)和(9,6),同时将空间和数据集进一步细分,如此往复直到空间中只包含一个数据点。

        与此同时,经过对上面所示的空间划分之后,我们可以看出,点(7,2)可以为根结点,从根结点出发的两条红粗斜线指向的(5,4)和(9,6)则为根结点的左右子结点,而(2,3),(4,7)则为(5,4)的左右孩子(通过两条细红斜线相连),最后,(8,1)为(9,6)的左孩子(通过细红斜线相连)。如此,便形成了下面这样一棵k-d树:

     

        k-d树的数据结构

        针对上表给出的kd树的数据结构,转化成具体代码如下所示(注,本文以下代码分析基于Rob Hess维护的sift库)

    1. /** a node in a k-d tree */  
    2. struct kd_node  
    3. {  
    4.     int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置  
    5.     double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值  
    6.     int leaf;                    /**< 1 if node is a leaf, 0 otherwise */  
    7.     struct feature* features;    /**< features at this node */  
    8.     int n;                       /**< number of features */  
    9.     struct kd_node* kd_left;     /**< left child */  
    10.     struct kd_node* kd_right;    /**< right child */  
    11. };  
    1. /** a node in a k-d tree */  
    2. struct kd_node  
    3. {  
    4.     int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置  
    5.     double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值  
    6.     int leaf;                    /**< 1 if node is a leaf, 0 otherwise */  
    7.     struct feature* features;    /**< features at this node */  
    8.     int n;                       /**< number of features */  
    9.     struct kd_node* kd_left;     /**< left child */  
    10.     struct kd_node* kd_right;    /**< right child */  
    11. };  
    /** a node in a k-d tree */
    struct kd_node
    {
        int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置
        double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值
        int leaf;                    /**< 1 if node is a leaf, 0 otherwise */
        struct feature* features;    /**< features at this node */
        int n;                       /**< number of features */
        struct kd_node* kd_left;     /**< left child */
        struct kd_node* kd_right;    /**< right child */
    };

        也就是说,如之前所述,kd树中,kd代表k-dimension,每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面,用垂直于坐标轴的超平面将空间分为两个部分,这样递归的从根节点不停的划分,直到没有实例为止。经典的构造k-d tree的规则如下:

    1. 随着树的深度增加,循环的选取坐标轴,作为分割超平面的法向量。对于3-d tree来说,根节点选取x轴,根节点的孩子选取y轴,根节点的孙子选取z轴,根节点的曾孙子选取x轴,这样循环下去。
    2. 每次均为所有对应实例的中位数的实例作为切分点,切分点作为父节点,左右两侧为划分的作为左右两子树。

        对于n个实例的k维数据来说,建立kd-tree的时间复杂度为O(k*n*logn)。

        构建完kd树之后,如今进行最近邻搜索呢?从下面的动态gif图中,你是否能看出些许端倪呢?


        k-d树算法可以分为两大部分,除了上部分有关k-d树本身这种数据结构建立的算法,另一部分是在建立的k-d树上各种诸如插入,删除,查找(最邻近查找)等操作涉及的算法。下面,咱们依次来看kd树的插入、删除、查找操作。

    2.3、KD树的插入

        元素插入到一个K-D树的方法和二叉检索树类似。本质上,在偶数层比较x坐标值,而在奇数层比较y坐标值。当我们到达了树的底部,(也就是当一个空指针出现),我们也就找到了结点将要插入的位置。生成的K-D树的形状依赖于结点插入时的顺序。给定N个点,其中一个结点插入和检索的平均代价是O(log2N)。

        下面4副图(来源:中国地质大学电子课件)说明了插入顺序为(a) Chicago, (b) Mobile, (c) Toronto, and (d) Buffalo,建立空间K-D树的示例:


        应该清楚,这里描述的插入过程中,每个结点将其所在的平面分割成两部分。因比,Chicago 将平面上所有结点分成两部分,一部分所有的结点x坐标值小于35,另一部分结点的x坐标值大于或等于35。同样Mobile将所有x坐标值大于35的结点以分成两部分,一部分结点的Y坐标值是小于10,另一部分结点的Y坐标值大于或等于10。后面的Toronto、Buffalo也按照一分为二的规则继续划分。

    2.4、KD树的删除

        KD树的删除可以用递归程序来实现。我们假设希望从K-D树中删除结点(a,b)。如果(a,b)的两个子树都为空,则用空树来代替(a,b)。否则,在(a,b)的子树中寻找一个合适的结点来代替它,譬如(c,d),则递归地从K-D树中删除(c,d)。一旦(c,d)已经被删除,则用(c,d)代替(a,b)。假设(a,b)是一个X识别器,那么,它得替代节点要么是(a,b)左子树中的X坐标最大值的结点,要么是(a,b)右子树中x坐标最小值的结点
        也就是说,跟普通二叉树(包括如下图所示的红黑树)结点的删除是同样的思想:用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点(比如,下图红黑树中,若要删除根结点26,第一步便是用23或28取代根结点26)。
       当(a,b)的右子树为空时,找到(a,b)左子树中具有x坐标最大的结点,譬如(c,d),将(a,b)的左子树放到(c,d)的右子树中,且在树中从它的上一层递归地应用删除过程(也就是(a,b)的左子树) 。
        下面来举一个实际的例子(来源:中国地质大学电子课件,原课件错误已经在下文中订正),如下图所示,原始图像及对应的kd树,现在要删除图中的A结点,请看一系列删除步骤:
        要删除上图中结点A,选择结点A的右子树中X坐标值最小的结点,这里是C,C成为根,如下图:
         从C的右子树中找出一个结点代替先前C的位置,
        这里是D,并将D的左子树转为它的右子树,D代替先前C的位置,如下图:
        在D的新右子树中,找X坐标最小的结点,这里为H,H代替D的位置,
        在D的右子树中找到一个Y坐标最小的值,这里是I,将I代替原先H的位置,从而A结点从图中顺利删除,如下图所示:
        从一个K-D树中删除结点(a,b)的问题变成了在(a,b)的子树中寻找x坐标为最小的结点。不幸的是寻找最小x坐标值的结点比二叉检索树中解决类似的问题要复杂得多。特别是虽然最小x坐标值的结点一定在x识别器的左子树中,但它同样可在y识别器的两个子树中。因此关系到检索,且必须注意检索坐标,以使在每个奇数层仅检索2个子树中的一个。
        从K-D树中删除一个结点是代价很高的,很清楚删除子树的根受到子树中结点个数的限制。用TPL(T)表示树T总的路径长度。可看出树中子树大小的总和为TPL(T)+N。 以随机方式插入N个点形成树的TPL是O(N*log2N),这就意味着从一个随机形成的K-D树中删除一个随机选取的结点平均代价的上界是O(log2N) 。

    2.5、KD树的最近邻搜索算法

        现实生活中有许多问题需要在多维数据的快速分析和快速搜索,对于这个问题最常用的方法是所谓的kd树。在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。在一个N维的笛卡儿空间在两个点之间的距离是由下述公式确定:

    1. void innerGetClosest(NODE* pNode, PT point, PT& res, int& nMinDis)  
    2. {  
    3.     if (NULL == pNode)  
    4.         return;  
    5.     int nCurDis = abs(point.x - pNode->pt.x) + abs(point.y - pNode->pt.y);  
    6.     if (nMinDis < 0 || nCurDis < nMinDis)  
    7.     {  
    8.         nMinDis = nCurDis;  
    9.         res = pNode->pt;  
    10.     }  
    11.     if (pNode->splitX && point.x <= pNode->pt.x || !pNode->splitX && point.y <= pNode->pt.y)  
    12.         innerGetClosest(pNode->pLft, point, res, nMinDis);  
    13.     else  
    14.         innerGetClosest(pNode->pRgt, point, res, nMinDis);  
    15.     int rang = pNode->splitX ? abs(point.x - pNode->pt.x) : abs(point.y - pNode->pt.y);  
    16.     if (rang > nMinDis)  
    17.         return;  
    18.     NODE* pGoInto = pNode->pLft;  
    19.     if (pNode->splitX && point.x > pNode->pt.x || !pNode->splitX && point.y > pNode->pt.y)  
    20.         pGoInto = pNode->pRgt;  
    21.     innerGetClosest(pGoInto, point, res, nMinDis);  
    22. }  
    void innerGetClosest(NODE* pNode, PT point, PT& res, int& nMinDis)
    {
        if (NULL == pNode)
            return;
        int nCurDis = abs(point.x - pNode->pt.x) + abs(point.y - pNode->pt.y);
        if (nMinDis < 0 || nCurDis < nMinDis)
        {
            nMinDis = nCurDis;
            res = pNode->pt;
        }
        if (pNode->splitX && point.x <= pNode->pt.x || !pNode->splitX && point.y <= pNode->pt.y)
            innerGetClosest(pNode->pLft, point, res, nMinDis);
        else
            innerGetClosest(pNode->pRgt, point, res, nMinDis);
        int rang = pNode->splitX ? abs(point.x - pNode->pt.x) : abs(point.y - pNode->pt.y);
        if (rang > nMinDis)
            return;
        NODE* pGoInto = pNode->pLft;
        if (pNode->splitX && point.x > pNode->pt.x || !pNode->splitX && point.y > pNode->pt.y)
            pGoInto = pNode->pRgt;
        innerGetClosest(pGoInto, point, res, nMinDis);
    }

    下面,以两个简单的实例(例子来自图像局部不变特性特征与描述一书)来描述最邻近查找的基本思路。

    2.5.1、举例:查询点(2.1,3.1)

        星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻,还需要进行相关的‘回溯’操作。也就是说,算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。

        以查询(2.1,3.1)为例:

    1. 二叉树搜索:先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,
    2. 回溯查找:在得到(2,3)为查询点的最近点之后,回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如下图所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中(图中灰色区域)去搜索;
    3. 最后,再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。


    2.5.2、举例:查询点2,4.5

        一个复杂点了例子如查找点为(2,4.5),具体步骤依次如下:

    1. 同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,但(4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点;
    2. 以(2,4.5)为圆心,以3.041为半径作圆,如下图所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找,也就是将(2,3)节点加入搜索路径中得<(7,2),(2,3)>;于是接着搜索至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5;
    3. 回溯查找至(5,4),直到最后回溯到根结点(7,2)的时候,以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图所示。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.5。

        上述两次实例表明,当查询点的邻域与分割超平面两侧空间交割时,需要查找另一侧子空间,导致检索过程复杂,效率下降。

        一般来讲,最临近搜索只需要检测几个叶子结点即可,如下图所示:  

        但是,如果当实例点的分布比较糟糕时,几乎要遍历所有的结点,如下所示:

        研究表明N个节点的K维k-d树搜索过程时间复杂度为:tworst=O(kN1-1/k)。

        同时,以上为了介绍方便,讨论的是二维或三维情形。但在实际的应用中,如SIFT特征矢量128维,SURF特征矢量64维,维度都比较大,直接利用k-d树快速检索(维数不超过20)的性能急剧下降,几乎接近贪婪线性扫描。假设数据集的维数为D,一般来说要求数据的规模N满足N»2D,才能达到高效的搜索。所以这就引出了一系列对k-d树算法的改进:BBF算法,和一系列M树、VP树、MVP树等高维空间索引树(下文2.6节kd树近邻搜索算法的改进:BBF算法,与2.7节球树、M树、VP树、MVP树)。

    2.6、kd树近邻搜索算法的改进:BBF算法

        咱们顺着上一节的思路,参考统计学习方法一书上的内容,再来总结下kd树的最近邻搜索算法:

    输入:以构造的kd树,目标点x;
    输出:x 的最近邻
    算法步骤如下:
    1. 在kd树种找出包含目标点x的叶结点:从根结点出发,递归地向下搜索kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点,直到子结点为叶结点为止。
    2. 以此叶结点为“当前最近点”。
    3. 递归的向上回溯,在每个结点进行以下操作:
      (a)如果该结点保存的实例点比当前最近点距离目标点更近,则更新“当前最近点”,也就是说以该实例点为“当前最近点”。
      (b)当前最近点一定存在于该结点一个子结点对应的区域,检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体做法是,检查另一子结点对应的区域是否以目标点位球心,以目标点与“当前最近点”间的距离为半径的圆或超球体相交:
      如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点,接着,继续递归地进行最近邻搜索;
      如果不相交,向上回溯。
    4. 回退到根结点时,搜索结束,最后的“当前最近点”即为x 的最近邻点。

        如果实例点是随机分布的,那么kd树搜索的平均计算复杂度是O(NlogN),这里的N是训练实例树。所以说,kd树更适用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,一降降到“解放前”:线性扫描的速度。

        也正因为上述k最近邻搜索算法的第4个步骤中的所述:“回退到根结点时,搜索结束”,每个最近邻点的查询比较完成过程最终都要回退到根结点而结束,而导致了许多不必要回溯访问和比较到的结点,这些多余的损耗在高维度数据查找的时候,搜索效率将变得相当之地下,那有什么办法可以改进这个原始的kd树最近邻搜索算法呢?

        从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。

        针对此BBF机制,读者Feng&书童点评道:

    1. 在某一层,分割面是第ki维,分割值是kv,那么 abs(q[ki]-kv) 就是没有选择的那个分支的优先级,也就是计算的是那一维上的距离;
    2. 同时,从优先队列里面取节点只在某次搜索到叶节点后才发生,计算过距离的节点不会出现在队列的,比如1~10这10个节点,你第一次搜索到叶节点的路径是1-5-7,那么1,5,7是不会出现在优先队列的。换句话说,优先队列里面存的都是查询路径上节点对应的相反子节点,比如:搜索左子树,就把对应这一层的右节点存进队列。

        如此,就引出了本节要讨论的kd树最近邻搜索算法的改进:BBF(Best-Bin-First)查询算法,它是由发明sift算法的David Lowe在1997的一篇文章中针对高维数据提出的一种近似算法,此算法能确保优先检索包含最近邻点可能性较高的空间,此外,BBF机制还设置了一个运行超时限定。采用了BBF查询机制后,kd树便可以有效的扩展到高维数据集上。

        伪代码如下图所示(图取自图像局部不变特性特征与描述一书):

        还是以上面的查询(2,4.5)为例,搜索的算法流程为:

    1. 将(7,2)压人优先队列中;
    2. 提取优先队列中的(7,2),由于(2,4.5)位于(7,2)分割超平面的左侧,所以检索其左子结点(5,4)。同时,根据BBF机制”搜索左/右子树,就把对应这一层的兄弟结点即右/左结点存进队列”,将其(5,4)对应的兄弟结点即右子结点(9,6)压人优先队列中,此时优先队列为{(9,6)},最佳点为(7,2);然后一直检索到叶子结点(4,7),此时优先队列为{(2,3),(9,6)},“最佳点”则为(5,4);
    3. 提取优先级最高的结点(2,3),重复步骤2,直到优先队列为空。

        如你在下图所见到的那样(话说,用鼠标在图片上写字着实不好写):

    2.7、球树、M树、VP树、MVP树

    2.7.1、球树

        咱们来针对上文内容总结回顾下,针对下面这样一棵kd树:

        现要找它的最近邻。

        通过上文2.5节,总结来说,我们已经知道:

    1、为了找到一个给定目标点的最近邻,需要从树的根结点开始向下沿树找出目标点所在的区域,如下图所示,给定目标点,用星号标示,我们似乎一眼看出,有一个点离目标点最近,因为它落在以目标点为圆心以较小长度为半径的虚线圆内,但为了确定是否可能还村庄一个最近的近邻,我们会先检查叶节点的同胞结点,然叶节点的同胞结点在图中所示的阴影部分,虚线圆并不与之相交,所以确定同胞叶结点不可能包含更近的近邻。


    2、于是我们回溯到父节点,并检查父节点的同胞结点,父节点的同胞结点覆盖了图中所有横线X轴上的区域。因为虚线圆与右上方的矩形(KD树把二维平面划分成一个一个矩形)相交…

        如上,我们看到,KD树是可用于有效寻找最近邻的一个树结构,但这个树结构其实并不完美,当处理不均匀分布的数据集时便会呈现出一个基本冲突:既邀请树有完美的平衡结构,又要求待查找的区域近似方形,但不管是近似方形,还是矩形,甚至正方形,都不是最好的使用形状,因为他们都有角。

            


        什么意思呢?就是说,在上图中,如果黑色的实例点离目标点星点再远一点,那么势必那个虚线圆会如红线所示那样扩大,以致与左上方矩形的右下角相交,既然相交了,那么势必又必须检查这个左上方矩形,而实际上,最近的点离星点的距离很近,检查左上方矩形区域已是多余。于此我们看见,KD树把二维平面划分成一个一个矩形,但矩形区域的角却是个难以处理的问题。

        解决的方案就是使用如下图所示的球树:

    先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加。


        使用球树找出给定目标点的最近邻方法是,首先自上而下贯穿整棵树找出包含目标点所在的叶子,并在这个球里找出与目标点最靠近的点,这将确定出目标点距离它的最近邻点的一个上限值,然后跟KD树查找一样,检查同胞结点,如果目标点到同胞结点中心的距离超过同胞结点的半径与当前的上限值之和,那么同胞结点里不可能存在一个更近的点;否则的话,必须进一步检查位于同胞结点以下的子树。

        如下图,目标点还是用一个星表示,黑色点是当前已知的的目标点的最近邻,灰色球里的所有内容将被排除,因为灰色球的中心点离的太远,所以它不可能包含一个更近的点,像这样,递归的向树的根结点进行回溯处理,检查所有可能包含一个更近于当前上限值的点的球。


        球树是自上而下的建立,和KD树一样,根本问题就是要找到一个好的方法将包含数据点集的球分裂成两个,在实践中,不必等到叶子结点只有两个胡数据点时才停止,可以采用和KD树一样的方法,一旦结点上的数据点打到预先设置的最小数量时,便可提前停止建树过程。

        也就是上面所述,先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加(注:本小节内容主要来自参考条目19:数据挖掘实用机器学习技术,[新西兰]Ian H.Witten 著,第4章4.7节)。

    2.7.2、VP树与MVP树简介

        高维特征向量的距离索引问题是基于内容的图像检索的一项关键技术,目前经常采用的解决办法是首先对高维特征空间做降维处理,然后采用包括四叉树、kd树、R树族等在内的主流多维索引结构,这种方法的出发点是:目前的主流多维索引结构在处理维数较低的情况时具有比较好的效率,但对于维数很高的情况则显得力不从心(即所谓的维数危机) 。

        实验结果表明当特征空间的维数超过20 的时候,效率明显降低,而可视化特征往往采用高维向量描述,一般情况下可以达到10^2的量级,甚至更高。在表示图像可视化特征的高维向量中各维信息的重要程度是不同的,通过降维技术去除属于次要信息的特征向量以及相关性较强的特征向量,从而降低特征空间的维数,这种方法已经得到了一些实际应用。

        然而这种方法存在不足之处采用降维技术可能会导致有效信息的损失,尤其不适合于处理特征空间中的特征向量相关性很小的情况。另外主流的多维索引结构大都针对欧氏空间,设计需要利用到欧氏空间的几何性质,而图像的相似性计算很可能不限于基于欧氏距离。这种情况下人们越来越关注基于距离的度量空间高维索引结构可以直接应用于高维向量相似性查询问题。

        度量空间中对象之间的距离度量只能利用三角不等式性质,而不能利用其他几何性质。向量空间可以看作由实数坐标串组成的特殊度量空间,目前针对度量空间的高维索引问题提出的索引结构有很多种大致可以作如下分类,如下图所示:

        

        其中,VP树和MVP树中特征向量的举例表示为:

         读者点评:

    1. UESTC_HN_AY_GUOBO:现在主要是在kdtree的基础上有了mtree或者mvptree,其实关键还是pivot的选择,以及度量空间中算法怎么减少距离计算;
    2. mandycool:mvp-tree,是利用三角形不等式来缩小搜索区域的,不过mvp-tree的目标稍有不同,查询的是到query点的距离小于某个值r的点;另外作者test的数据集只有20维,不知道上百维以后效果如何,而减少距离计算的一个思路是做embedding,通过不等式排除掉一部分点。

        更多内容请参见论文1:DIST ANCE-BASED INDEXING FOR HIGH-DIMENSIONAL METRIC SP ACES,作者:Tolga Bozkaya & Meral Ozsoyoglu,及论文2:基于度量空间高维索引结构VP-tree及MVP-tree的图像检索王志强,甘国辉,程起敏

        当然,如果你觉得上述论文还不够满足你胃口的话,这里有一大堆nearest neighbor algorithms相关的论文可供你看:http://scholar.google.com.hk/scholar?q=nearest+neighbor+algorithms&btnG=&hl=zh-CN&as_sdt=0&as_vis=1(其中,这篇可以看下Spill-Trees,An investigation of practical approximate nearest neighbor algorithms。

    转载于: https://blog.csdn.net/app_12062011/article/details/51986805
    谢谢原博主~~~

    展开全文
  • 15分钟理解KD树

    万次阅读 2018-05-20 21:25:00
    1. 概述KD树是一种查询索引结构,广泛应用于数据库索引中。从概念的角度讲,它是一种高纬数据的快速查询结构,本文首先介绍1维数据的索引查询,然后介绍2维KD树的创建和查询,相关定理和推论也简单列出,本文争取用...

    1. 概述

    KD树是一种查询索引结构,广泛应用于数据库索引中。从概念的角度讲,它是一种高纬数据的快速查询结构,本文首先介绍1维数据的索引查询,然后介绍2维KD树的创建和查询,相关定理和推论也简单列出,本文争取用15分钟的时间,让大家快速理解KD树。

    2. 1维数据的查询

    假设在数据库的表格T中存储了学生的语文成绩chinese、数学成绩math、英语成绩english,如果要查询语文成绩介于30~93分的学生,如何处理?假设学生数量为N,如果顺序查询,则其时间复杂度为O(N),当学生规模很大时,其效率显然很低,如果使用平衡二叉树,则其时间复杂度为O(logN),能极大地提高查询效率。平衡二叉树示意图为:

    图1:平衡二叉树示意图

    对于1维数据的查询,使用平衡二叉树建立索引即可。如果现在将查询条件变为:语文成绩介于30~93,数学成绩结余30~90,又该如何处理呢?

    如果分别使用平衡二叉树对语文成绩和数学成绩建立索引,则需要先在语文成绩中查询得到集合S1,再在数学成绩中查询得到集合S2,然后计算S1和S2的交集,若|S1|=m,|S2|=n,则其时间复杂度为O(m*n),有没有更好的办法呢?

    3. KD树

    针对多维数据索引,是否也存在类似的一维的索引方法呢?先看2维数据的集合示意图:

    图2: 2维数据示意图

    如果先根据语文成绩,将所有人的成绩分成两半,其中一半的语文成绩<=c1,另一半的语文成绩>c1,分别得到集合S1,S2;然后针对S1,根据数学成绩分为两半,其中一半的数学成绩<=m1,另一半的数学成绩>m1,分别得到S3,S4,针对S2,根据数学成绩分为两半,其中一半的数学成绩<=m2,另一半的数学成绩>m2,分别得到S5,S6;再根据语文成绩分别对S3,S4,S5,S6继续执行类似划分得到更小的集合,然后再在更小的集合上根据数学成绩继续,...

    上面描述的就是构建KD树的基本思路,其构建后的KD树如下图所示:

    图3: KD树示意图

    如图所示,l1左边都是语文成绩低于45分,l1右边都是语文成绩高于45分的;l2下方都是语文成绩低于45分且数学成绩低于50分的,l2上方都是语文成绩低于45分且数学成绩高于50分的,后面以此类推。下面的图示,更清晰地表示了KD树的结构及其对应的二叉树:

    图4: KD树及对应的二叉树

    在了解了KD树的基本原理后,剩下的工作就是如何构建KD树以及如何在KD树上查询了。

    3.1 KD树构建算法

    相对而言,构建KD树是针对高维数据,需要针对每一维都进行二分,针对二维数据的KD树构建算法如下图5所示:

    图5:KD树构建算法

    其中的P表示待构建的元素集合,depth表示当前是KD树的第几层,如果depth是偶数,通过纵向线对集合进行划分;如果depth是奇数,通过横向线进行划分(3~5行);第6、7行递归进行KD树中子树的构建。

    图5中的算法时间复杂度为:O(nlogn),感兴趣的同学可以写出递推公式公式进行推到,算法导论中专门讲了这个递推公式。

    3.2 KD树查询算法

    在构建了KD树的基础上,如何进行查询其实是一个相对简单的问题了,在这里需要注意的是,在KD树中每一层划分所依据的是哪一维的数据,其它的根二叉树其实没有差别。KD树查询算法如下图所示:

    图6: 查询算法

    图6中算法的v表示KD树中当前搜索的子树,R表示是一个高维数据的区域,区域的概念如图7所示:

    图7: 区域示意图

    如果v是叶子结点且属于区域R,则直接返回(第1行);如果v是非叶子结点,则比较R与v的左子树lc(v)是否有交集,如果有且lc(v)完全被R覆盖,则lc(v)是所查询结果的一部分,如果不是完全覆盖,则递归查询lc(v)(36行);对右子树也是类似的操作(710)。算法的时间复杂度为:O(sqrt(n) + k),其中k是最后的结果中元素的个数,其递推公式公式为:

    图8: KD树查询递推公式

    上述算法中的二维也可升级为3维,其思维方式与从1维升级到2维一致,相应的构建算法和查询算法也与2维的一致,感兴趣的童鞋可以分析相应算法的时间复杂度。

    4. 小结

    本文以从1维数据索引跳变到2维数据索引的方式,引出了KD树,并介绍了KD树的构建与索引查询算法。KD树主要应用在高维数据索引,特别是空间数据库的索引,x和y分别表示经度和纬度,能较好的处理空间上的查询效率问题,如果在x和y再加一个时间维度,也能较好地处理时空数据索引查询。



    作者:CodingTech
    链接:https://www.jianshu.com/p/ffe52db3e12b

    展开全文
  • 统计学习笔记(3)——k近邻法与kd树    在使用k近邻法进行分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决的方式进行预测。由于k近邻模型的特征空间一般是n维实数向量,所以距离的计算...
    
        

    k近邻法与kd树

               

            在使用k近邻法进行分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决的方式进行预测。由于k近邻模型的特征空间一般是n维实数向量,所以距离的计算通常采用的是欧式距离。关键的是k值的选取,如果k值太小就意味着整体模型变得复杂,容易发生过拟合,即如果邻近的实例点恰巧是噪声,预测就会出错,极端的情况是k=1,称为最近邻算法,对于待预测点x,与x最近的点决定了x的类别。k值得增大意味着整体的模型变得简单,极端的情况是k=N,那么无论输入实例是什么,都简单地预测它属于训练集中最多的类,这样的模型过于简单。经验是,k值一般去一个比较小的值,通常采取交叉验证的方法来选取最优的k值。

           实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索,这点在特征空间的维数大以及训练数据容量大时尤其重要。k近邻法的最简单实现是线性扫描,这时要计算输入实例与每一个训练实例的距离,当训练集很大时,计算非常耗时,这种方法是不可行的。为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数。具体方法有很多,这里介绍kd树方法。

    1.实例

           先以一个简单直观的实例来介绍k-d树算法。假设有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树的伪码。

    1. 算法:构建k-d树(createKDTree)  
    2. 输入:数据点集Data-set和其所在的空间Range  
    3. 输出:Kd,类型为k-d tree  
    4. 1.If Data-set为空,则返回空的k-d tree  
    5. 2.调用节点生成程序:  
    6.   (1)确定split域:对于所有描述子数据(特征矢量),统计它们在每个维上的数据方差。假设每条数据记录为64维,可计算64个方差。挑选出最大值,对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开,在这个方向上进行数据分割有较好的分辨率;  
    7.   (2)确定Node-data域:数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set' = Data-set \ Node-data(除去其中Node-data这一点)。  
    8. 3.dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]}  
    9.    Left_Range = {Range && dataleft}  
    10.   dataright = {d属于Data-set' && d[split] > Node-data[split]}  
    11.    Right_Range = {Range && dataright}  
    12. 4.left = 由(dataleft,Left_Range)建立的k-d tree,即递归调用createKDTree(dataleft,Left_Range)。并设置left的parent域为Kd;  
    13.    right = 由(dataright,Right_Range)建立的k-d tree,即调用createKDTree(dataleft,Left_Range)。并设置right的parent域为Kd。  
    算法:构建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 <= 7的部分为左子空间,包含3个节点{(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点{(9,6),(8,1)}。


             如算法所述,k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点(5,4)和(9,6)(也就是左右子空间的'根'节点),同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点,如下图所示。最后生成的k-d树如下图所示。

    3.搜索kd树

            在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。

            星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻,还需要进行'回溯'操作:算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为小于(7,2)和(5,4),大于(2,3),首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,然后回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如下图所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中去搜索。


             再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。

              一个复杂点了例子如查找点为(2,4.5)。同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,取(4,7)为当前最近邻点,计算其与目标查找点的距离为3.202。然后回溯到(5,4),计算其与查找点之间的距离为3.041。以(2,4.5)为圆心,以3.041为半径作圆,如下图左所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找。此时需将(2,3)节点加入搜索路径中得<(7,2),(2,3)>。回溯至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5。回溯至(7,2),以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图右所示。至此,搜索路径回溯完。返回最近邻点(2,3),最近距离1.5。

           k-d树查询算法的伪代码如下所示。

    1. 算法:k-d树最邻近查找  
    2. 输入:Kd,    //k-d tree类型  
    3.      target  //查询数据点  
    4. 输出:nearest, //最邻近数据点  
    5.      dist      //最邻近数据点和查询点间的距离  
    6. 1. If Kd为NULL,则设dist为infinite并返回  
    7. 2. //进行二叉查找,生成搜索路径  
    8.    Kd_point = &Kd;                   //Kd-point中保存k-d tree根节点地址  
    9.    nearest = Kd_point -> Node-data;  //初始化最近邻点  
    10.    while(Kd_point)  
    11.      push(Kd_point)到search_path中; //search_path是一个堆栈结构,存储着搜索路径节点指针  
    12.  /*** If Dist(nearest,target) > Dist(Kd_point -> Node-data,target) 
    13.        nearest  = Kd_point -> Node-data;    //更新最近邻点 
    14.        Max_dist = Dist(Kd_point,target);  //更新最近邻点与查询点间的距离  ***/  
    15.      s = Kd_point -> split;                       //确定待分割的方向  
    16.      If target[s] <= Kd_point -> Node-data[s]     //进行二叉查找  
    17.        Kd_point = Kd_point -> left;  
    18.      else  
    19.        Kd_point = Kd_point ->right;  
    20.    nearest = search_path中最后一个叶子节点; //注意:二叉搜索时不比计算选择搜索路径中的最邻近点,这部分已被注释  
    21.    Max_dist = Dist(nearest,target);    //直接取最后叶子节点作为回溯前的初始最近邻点  
    22.   
    23. 3. //回溯查找  
    24.    while(search_path != NULL)  
    25.      back_point = 从search_path取出一个节点指针;   //从search_path堆栈弹栈  
    26.      s = back_point -> split;                   //确定分割方向  
    27.      If Dist(target[s],back_point -> Node-data[s]) < Max_dist   //判断还需进入的子空间  
    28.        If target[s] <= back_point -> Node-data[s]  
    29.          Kd_point = back_point -> right;  //如果target位于左子空间,就应进入右子空间  
    30.        else  
    31.          Kd_point = back_point -> left;    //如果target位于右子空间,就应进入左子空间  
    32.        将Kd_point压入search_path堆栈;  
    33.      If Dist(nearest,target) > Dist(Kd_Point -> Node-data,target)  
    34.        nearest  = Kd_point -> Node-data;                 //更新最近邻点  
    35.        Min_dist = Dist(Kd_point -> Node-data,target);  //更新最近邻点与查询点间的距离  
    算法:k-d树最邻近查找
    输入:Kd,    //k-d tree类型
         target  //查询数据点
    输出:nearest, //最邻近数据点
         dist      //最邻近数据点和查询点间的距离
    1. If Kd为NULL,则设dist为infinite并返回
    2. //进行二叉查找,生成搜索路径
       Kd_point = &Kd;                   //Kd-point中保存k-d tree根节点地址
       nearest = Kd_point -> 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] <= Kd_point -> 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]) < Max_dist   //判断还需进入的子空间
           If target[s] <= back_point -> Node-data[s]
             Kd_point = back_point -> 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次方,才能达到高效的搜索。


    参考:

    http://www.cnblogs.com/eyeszjwang/articles/2429382.html
    展开全文
  • KNN(三)--KD树详解及KD树最近邻算法

    万次阅读 多人点赞 2019-02-12 19:44:53
    之前blog内曾经介绍过SIFT特征匹配算法,特征点匹配和数据库查、图像检索本质上是同一个问题,都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题,如何快速而准确地找到查询点的近邻,不少人提出了很...

    之前blog内曾经介绍过SIFT特征匹配算法,特征点匹配和数据库查、图像检索本质上是同一个问题,都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题,如何快速而准确地找到查询点的近邻,不少人提出了很多高维空间索引结构和近似查询的算法。

        一般说来,索引结构中相似性查询有两种基本的方式:

    1. 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据
    2. 另一种是K近邻查询,就是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。

        同样,针对特征点匹配也有两种方法:

    • 最容易的办法就是线性扫描,也就是我们常说的穷举搜索,依次计算样本集E中每个样本到输入实例点的距离,然后抽取出计算出来的最小距离的点即为最近邻点。此种办法简单直白,但当样本集或训练集很大时,它的缺点就立马暴露出来了,举个例子,在物体识别的问题中,可能有数千个甚至数万个SIFT特征点,而去计算这成千上万的特征点与输入实例点的距离,明显是不足取的。
    • 另外一种,就是构建数据索引,因为实际数据一般都会呈现簇状的聚类形态,因此我们想到建立数据索引,然后再进行快速匹配。索引树是一种树结构索引方法,其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠,其代表就是k-d树;后者划分空间相互有交叠,其代表为R树。

        1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了如下图形式的把空间划分为多个部分的k-d树。

     

     

    2.1、什么是KD树

        Kd-树是K-dimension tree的缩写,是对数据点在k维空间(如二维(x,y),三维(x,y,z),k维(x1,y,z..))中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。本质上说,Kd-树就是一种平衡二叉树。

        首先必须搞清楚的是,k-d树是一种空间划分树,说白了,就是把整个空间划分为特定的几个部分,然后在特定空间的部分内进行相关搜索操作。想像一个三维(多维有点为难你的想象力了)空间,kd树按照一定的划分规则把这个三维空间划分了多个空间,如下图所示:

     

    2.2、KD树的构建

        kd树构建的伪代码如下图所示:

     

     

        再举一个简单直观的实例来介绍k-d树构建算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图所示。为了能有效的找到最近邻,k-d树采用分而治之的思想,即将整个空间划分为几个小部分,首先,粗黑线将空间一分为二,然后在两个子空间中,细黑直线又将整个空间划分为四部分,最后虚黑直线将这四部分进一步划分。

     

        6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}构建kd树的具体步骤为:

    1. 确定:split域=x。具体是:6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故split域值为x;
    2. 确定:Node-data = (7,2)。具体是:根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以Node-data域位数据点(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:split=x轴的直线x=7;
    3. 确定:左子空间和右子空间。具体是:分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)};

        如上算法所述,kd树的构建是一个递归过程,我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点(5,4)和(9,6),同时将空间和数据集进一步细分,如此往复直到空间中只包含一个数据点。

        与此同时,经过对上面所示的空间划分之后,我们可以看出,点(7,2)可以为根结点,从根结点出发的两条红粗斜线指向的(5,4)和(9,6)则为根结点的左右子结点,而(2,3),(4,7)则为(5,4)的左右孩子(通过两条细红斜线相连),最后,(8,1)为(9,6)的左孩子(通过细红斜线相连)。如此,便形成了下面这样一棵k-d树:

     

     

     

     

        k-d树的数据结构

     

        针对上表给出的kd树的数据结构,转化成具体代码如下所示(注,本文以下代码分析基于Rob Hess维护的sift库)

    [cpp] view plaincopyprint?

    1. /** a node in a k-d tree */  
    2. struct kd_node  
    3. {  
    4.     int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置  
    5.     double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值  
    6.     int leaf;                    /**< 1 if node is a leaf, 0 otherwise */  
    7.     struct feature* features;    /**< features at this node */  
    8.     int n;                       /**< number of features */  
    9.     struct kd_node* kd_left;     /**< left child */  
    10.     struct kd_node* kd_right;    /**< right child */  
    11. };  
    /** a node in a k-d tree */
    struct kd_node
    {
    	int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置
    	double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值
    	int leaf;                    /**< 1 if node is a leaf, 0 otherwise */
    	struct feature* features;    /**< features at this node */
    	int n;                       /**< number of features */
    	struct kd_node* kd_left;     /**< left child */
    	struct kd_node* kd_right;    /**< right child */
    };

        也就是说,如之前所述,kd树中,kd代表k-dimension,每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面,用垂直于坐标轴的超平面将空间分为两个部分,这样递归的从根节点不停的划分,直到没有实例为止。经典的构造k-d tree的规则如下:

    1. 随着树的深度增加,循环的选取坐标轴,作为分割超平面的法向量。对于3-d tree来说,根节点选取x轴,根节点的孩子选取y轴,根节点的孙子选取z轴,根节点的曾孙子选取x轴,这样循环下去。
    2. 每次均为所有对应实例的中位数的实例作为切分点,切分点作为父节点,左右两侧为划分的作为左右两子树。

        对于n个实例的k维数据来说,建立kd-tree的时间复杂度为O(k*n*logn)。

     

        构建完kd树之后,如今进行最近邻搜索呢?从下面的动态gif图中,你是否能看出些许端倪呢?

        k-d树算法可以分为两大部分,除了上部分有关k-d树本身这种数据结构建立的算法,另一部分是在建立的k-d树上各种诸如插入,删除,查找(最邻近查找)等操作涉及的算法。下面,咱们依次来看kd树的插入、删除、查找操作。

     

    2.3、KD树的插入

     

        元素插入到一个K-D树的方法和二叉检索树类似。本质上,在偶数层比较x坐标值,而在奇数层比较y坐标值。当我们到达了树的底部,(也就是当一个空指针出现),我们也就找到了结点将要插入的位置。生成的K-D树的形状依赖于结点插入时的顺序。给定N个点,其中一个结点插入和检索的平均代价是O(log2N)。

        下面4副图(来源:中国地质大学电子课件)说明了插入顺序为(a) Chicago, (b) Mobile, (c) Toronto, and (d) Buffalo,建立空间K-D树的示例:

     

     

        应该清楚,这里描述的插入过程中,每个结点将其所在的平面分割成两部分。因比,Chicago 将平面上所有结点分成两部分,一部分所有的结点x坐标值小于35,另一部分结点的x坐标值大于或等于35。同样Mobile将所有x坐标值大于35的结点以分成两部分,一部分结点的Y坐标值是小于10,另一部分结点的Y坐标值大于或等于10。后面的Toronto、Buffalo也按照一分为二的规则继续划分。

    2.4、KD树的删除

        KD树的删除可以用递归程序来实现。我们假设希望从K-D树中删除结点(a,b)。如果(a,b)的两个子树都为空,则用空树来代替(a,b)。否则,在(a,b)的子树中寻找一个合适的结点来代替它,譬如(c,d),则递归地从K-D树中删除(c,d)。一旦(c,d)已经被删除,则用(c,d)代替(a,b)。假设(a,b)是一个X识别器,那么,它得替代节点要么是(a,b)左子树中的X坐标最大值的结点,要么是(a,b)右子树中x坐标最小值的结点。

        也就是说,跟普通二叉树(包括如下图所示的红黑树)结点的删除是同样的思想:用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点(比如,下图红黑树中,若要删除根结点26,第一步便是用23或28取代根结点26)。

       当(a,b)的右子树为空时,找到(a,b)左子树中具有x坐标最大的结点,譬如(c,d),将(a,b)的左子树放到(c,d)的右子树中,且在树中从它的上一层递归地应用删除过程(也就是(a,b)的左子树) 。

        下面来举一个实际的例子(来源:中国地质大学电子课件,原课件错误已经在下文中订正),如下图所示,原始图像及对应的kd树,现在要删除图中的A结点,请看一系列删除步骤:

        要删除上图中结点A,选择结点A的右子树中X坐标值最小的结点,这里是C,C成为根,如下图:

         从C的右子树中找出一个结点代替先前C的位置,

        这里是D,并将D的左子树转为它的右子树,D代替先前C的位置,如下图:

        在D的新右子树中,找X坐标最小的结点,这里为H,H代替D的位置,

        在D的右子树中找到一个Y坐标最小的值,这里是I,将I代替原先H的位置,从而A结点从图中顺利删除,如下图所示:

        从一个K-D树中删除结点(a,b)的问题变成了在(a,b)的子树中寻找x坐标为最小的结点。不幸的是寻找最小x坐标值的结点比二叉检索树中解决类似的问题要复杂得多。特别是虽然最小x坐标值的结点一定在x识别器的左子树中,但它同样可在y识别器的两个子树中。因此关系到检索,且必须注意检索坐标,以使在每个奇数层仅检索2个子树中的一个。
        从K-D树中删除一个结点是代价很高的,很清楚删除子树的根受到子树中结点个数的限制。用TPL(T)表示树T总的路径长度。可看出树中子树大小的总和为TPL(T)+N。 以随机方式插入N个点形成树的TPL是O(N*log2N),这就意味着从一个随机形成的K-D树中删除一个随机选取的结点平均代价的上界是O(log2N) 。

    2.5、KD树的最近邻搜索算法

        现实生活中有许多问题需要在多维数据的快速分析和快速搜索,对于这个问题最常用的方法是所谓的kd树。在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。在一个N维的笛卡儿空间在两个点之间的距离是由下述公式确定:

    void innerGetClosest(NODE* pNode, PT point, PT& res, int& nMinDis)
    {
    	if (NULL == pNode)
    		return;
    	int nCurDis = abs(point.x - pNode->pt.x) + abs(point.y - pNode->pt.y);
    	if (nMinDis < 0 || nCurDis < nMinDis)
    	{
    		nMinDis = nCurDis;
    		res = pNode->pt;
    	}
    	if (pNode->splitX && point.x <= pNode->pt.x || !pNode->splitX && point.y <= pNode->pt.y)
    		innerGetClosest(pNode->pLft, point, res, nMinDis);
    	else
    		innerGetClosest(pNode->pRgt, point, res, nMinDis);
    	int rang = pNode->splitX ? abs(point.x - pNode->pt.x) : abs(point.y - pNode->pt.y);
    	if (rang > nMinDis)
    		return;
    	NODE* pGoInto = pNode->pLft;
    	if (pNode->splitX && point.x > pNode->pt.x || !pNode->splitX && point.y > pNode->pt.y)
    		pGoInto = pNode->pRgt;
    	innerGetClosest(pGoInto, point, res, nMinDis);
    }

    下面,以两个简单的实例(例子来自图像局部不变特性特征与描述一书)来描述最邻近查找的基本思路。

    2.5.1、举例:查询点(2.1,3.1)

        星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻,还需要进行相关的‘回溯'操作。也就是说,算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。

        以查询(2.1,3.1)为例:

     

    1. 二叉树搜索:先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,
    2. 回溯查找:在得到(2,3)为查询点的最近点之后,回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如下图所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中(图中灰色区域)去搜索;
    3. 最后,再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。

    2.5.2、举例:查询点2,4.5

        一个复杂点了例子如查找点为(2,4.5),具体步骤依次如下:

     

    1. 同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,但(4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点;
    2. 以(2,4.5)为圆心,以3.041为半径作圆,如下图所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找,也就是将(2,3)节点加入搜索路径中得<(7,2),(2,3)>;于是接着搜索至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5;
    3. 回溯查找至(5,4),直到最后回溯到根结点(7,2)的时候,以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图所示。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.5。

        上述两次实例表明,当查询点的邻域与分割超平面两侧空间交割时,需要查找另一侧子空间,导致检索过程复杂,效率下降。

     

        一般来讲,最临近搜索只需要检测几个叶子结点即可,如下图所示:  

     

     

     

     

        但是,如果当实例点的分布比较糟糕时,几乎要遍历所有的结点,如下所示:

     

        研究表明N个节点的K维k-d树搜索过程时间复杂度为:tworst=O(kN1-1/k)。

        同时,以上为了介绍方便,讨论的是二维或三维情形。但在实际的应用中,如SIFT特征矢量128维,SURF特征矢量64维,维度都比较大,直接利用k-d树快速检索(维数不超过20)的性能急剧下降,几乎接近贪婪线性扫描。假设数据集的维数为D,一般来说要求数据的规模N满足N»2D,才能达到高效的搜索。所以这就引出了一系列对k-d树算法的改进:BBF算法,和一系列M树、VP树、MVP树等高维空间索引树(下文2.6节kd树近邻搜索算法的改进:BBF算法,与2.7节球树、M树、VP树、MVP树)。

    2.6、kd树近邻搜索算法的改进:BBF算法

        咱们顺着上一节的思路,参考统计学习方法一书上的内容,再来总结下kd树的最近邻搜索算法:

    输入:以构造的kd树,目标点x;
    输出:x 的最近邻
    算法步骤如下:

    1. 在kd树种找出包含目标点x的叶结点:从根结点出发,递归地向下搜索kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点,直到子结点为叶结点为止。
    2. 以此叶结点为“当前最近点”。
    3. 递归的向上回溯,在每个结点进行以下操作:
      (a)如果该结点保存的实例点比当前最近点距离目标点更近,则更新“当前最近点”,也就是说以该实例点为“当前最近点”。
      (b)当前最近点一定存在于该结点一个子结点对应的区域,检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体做法是,检查另一子结点对应的区域是否以目标点位球心,以目标点与“当前最近点”间的距离为半径的圆或超球体相交:
      如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点,接着,继续递归地进行最近邻搜索;
      如果不相交,向上回溯。
    4. 回退到根结点时,搜索结束,最后的“当前最近点”即为x 的最近邻点。

        如果实例点是随机分布的,那么kd树搜索的平均计算复杂度是O(NlogN),这里的N是训练实例树。所以说,kd树更适用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,一降降到“解放前”:线性扫描的速度。

        也正因为上述k最近邻搜索算法的第4个步骤中的所述:“回退到根结点时,搜索结束”,每个最近邻点的查询比较完成过程最终都要回退到根结点而结束,而导致了许多不必要回溯访问和比较到的结点,这些多余的损耗在高维度数据查找的时候,搜索效率将变得相当之地下,那有什么办法可以改进这个原始的kd树最近邻搜索算法呢?

        从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。

        针对此BBF机制,读者Feng&书童点评道:

    1. 在某一层,分割面是第ki维,分割值是kv,那么 abs(q[ki]-kv) 就是没有选择的那个分支的优先级,也就是计算的是那一维上的距离;
    2. 同时,从优先队列里面取节点只在某次搜索到叶节点后才发生,计算过距离的节点不会出现在队列的,比如1~10这10个节点,你第一次搜索到叶节点的路径是1-5-7,那么1,5,7是不会出现在优先队列的。换句话说,优先队列里面存的都是查询路径上节点对应的相反子节点,比如:搜索左子树,就把对应这一层的右节点存进队列。

        如此,就引出了本节要讨论的kd树最近邻搜索算法的改进:BBF(Best-Bin-First)查询算法,它是由发明sift算法的David Lowe在1997的一篇文章中针对高维数据提出的一种近似算法,此算法能确保优先检索包含最近邻点可能性较高的空间,此外,BBF机制还设置了一个运行超时限定。采用了BBF查询机制后,kd树便可以有效的扩展到高维数据集上。

        伪代码如下图所示(图取自图像局部不变特性特征与描述一书):

     

        还是以上面的查询(2,4.5)为例,搜索的算法流程为:

    1. 将(7,2)压人优先队列中;
    2. 提取优先队列中的(7,2),由于(2,4.5)位于(7,2)分割超平面的左侧,所以检索其左子结点(5,4)。同时,根据BBF机制”搜索左/右子树,就把对应这一层的兄弟结点即右/左结点存进队列”,将其(5,4)对应的兄弟结点即右子结点(9,6)压人优先队列中,此时优先队列为{(9,6)},最佳点为(7,2);然后一直检索到叶子结点(4,7),此时优先队列为{(2,3),(9,6)},“最佳点”则为(5,4);
    3. 提取优先级最高的结点(2,3),重复步骤2,直到优先队列为空。

        如你在下图所见到的那样(话说,用鼠标在图片上写字着实不好写):

     

     

    2.7、球树、M树、VP树、MVP树

    2.7.1、球树

     

        咱们来针对上文内容总结回顾下,针对下面这样一棵kd树:

     

     

        现要找它的最近邻。

        通过上文2.5节,总结来说,我们已经知道:

    1、为了找到一个给定目标点的最近邻,需要从树的根结点开始向下沿树找出目标点所在的区域,如下图所示,给定目标点,用星号标示,我们似乎一眼看出,有一个点离目标点最近,因为它落在以目标点为圆心以较小长度为半径的虚线圆内,但为了确定是否可能还村庄一个最近的近邻,我们会先检查叶节点的同胞结点,然叶节点的同胞结点在图中所示的阴影部分,虚线圆并不与之相交,所以确定同胞叶结点不可能包含更近的近邻。

     

     

    2、于是我们回溯到父节点,并检查父节点的同胞结点,父节点的同胞结点覆盖了图中所有横线X轴上的区域。因为虚线圆与右上方的矩形(KD树把二维平面划分成一个一个矩形)相交...

        如上,我们看到,KD树是可用于有效寻找最近邻的一个树结构,但这个树结构其实并不完美,当处理不均匀分布的数据集时便会呈现出一个基本冲突:既邀请树有完美的平衡结构,又要求待查找的区域近似方形,但不管是近似方形,还是矩形,甚至正方形,都不是最好的使用形状,因为他们都有角。

     

            

        什么意思呢?就是说,在上图中,如果黑色的实例点离目标点星点再远一点,那么势必那个虚线圆会如红线所示那样扩大,以致与左上方矩形的右下角相交,既然相交了,那么势必又必须检查这个左上方矩形,而实际上,最近的点离星点的距离很近,检查左上方矩形区域已是多余。于此我们看见,KD树把二维平面划分成一个一个矩形,但矩形区域的角却是个难以处理的问题。

        解决的方案就是使用如下图所示的球树:

     

    先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加。

     

     

        使用球树找出给定目标点的最近邻方法是,首先自上而下贯穿整棵树找出包含目标点所在的叶子,并在这个球里找出与目标点最靠近的点,这将确定出目标点距离它的最近邻点的一个上限值,然后跟KD树查找一样,检查同胞结点,如果目标点到同胞结点中心的距离超过同胞结点的半径与当前的上限值之和,那么同胞结点里不可能存在一个更近的点;否则的话,必须进一步检查位于同胞结点以下的子树。

        如下图,目标点还是用一个星表示,黑色点是当前已知的的目标点的最近邻,灰色球里的所有内容将被排除,因为灰色球的中心点离的太远,所以它不可能包含一个更近的点,像这样,递归的向树的根结点进行回溯处理,检查所有可能包含一个更近于当前上限值的点的球。

     

     

        球树是自上而下的建立,和KD树一样,根本问题就是要找到一个好的方法将包含数据点集的球分裂成两个,在实践中,不必等到叶子结点只有两个胡数据点时才停止,可以采用和KD树一样的方法,一旦结点上的数据点打到预先设置的最小数量时,便可提前停止建树过程。

        也就是上面所述,先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加(注:本小节内容主要来自参考条目19:数据挖掘实用机器学习技术,[新西兰]Ian H.Witten 著,第4章4.7节)。

    2.7.2、VP树与MVP树简介

        高维特征向量的距离索引问题是基于内容的图像检索的一项关键技术,目前经常采用的解决办法是首先对高维特征空间做降维处理,然后采用包括四叉树、kd树、R树族等在内的主流多维索引结构,这种方法的出发点是:目前的主流多维索引结构在处理维数较低的情况时具有比较好的效率,但对于维数很高的情况则显得力不从心(即所谓的维数危机) 。

        实验结果表明当特征空间的维数超过20 的时候,效率明显降低,而可视化特征往往采用高维向量描述,一般情况下可以达到10^2的量级,甚至更高。在表示图像可视化特征的高维向量中各维信息的重要程度是不同的,通过降维技术去除属于次要信息的特征向量以及相关性较强的特征向量,从而降低特征空间的维数,这种方法已经得到了一些实际应用。

        然而这种方法存在不足之处采用降维技术可能会导致有效信息的损失,尤其不适合于处理特征空间中的特征向量相关性很小的情况。另外主流的多维索引结构大都针对欧氏空间,设计需要利用到欧氏空间的几何性质,而图像的相似性计算很可能不限于基于欧氏距离。这种情况下人们越来越关注基于距离的度量空间高维索引结构可以直接应用于高维向量相似性查询问题。

        度量空间中对象之间的距离度量只能利用三角不等式性质,而不能利用其他几何性质。向量空间可以看作由实数坐标串组成的特殊度量空间,目前针对度量空间的高维索引问题提出的索引结构有很多种大致可以作如下分类,如下图所示:

     

        

     

     

        其中,VP树和MVP树中特征向量的举例表示为:

     

     

         读者点评:

     

    1. UESTC_HN_AY_GUOBO:现在主要是在kdtree的基础上有了mtree或者mvptree,其实关键还是pivot的选择,以及度量空间中算法怎么减少距离计算;
    2. mandycool:mvp-tree,是利用三角形不等式来缩小搜索区域的,不过mvp-tree的目标稍有不同,查询的是到query点的距离小于某个值r的点;另外作者test的数据集只有20维,不知道上百维以后效果如何,而减少距离计算的一个思路是做embedding,通过不等式排除掉一部分点。

        更多内容请参见论文1:DIST ANCE-BASED INDEXING FOR HIGH-DIMENSIONAL METRIC SP ACES,作者:Tolga Bozkaya & Meral Ozsoyoglu,及论文2:基于度量空间高维索引结构VP-tree及MVP-tree的图像检索,王志强,甘国辉,程起敏。

        当然,如果你觉得上述论文还不够满足你胃口的话,这里有一大堆nearest neighbor algorithms相关的论文可供你看:http://scholar.google.com.hk/scholar?q=nearest+neighbor+algorithms&btnG=&hl=zh-CN&as_sdt=0&as_vis=1(其中,这篇可以看下:Spill-Trees,An investigation of practical approximate nearest neighbor algorithms)。

     

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <cmath>
    using namespace std;
    
    
    
    
    struct KdTree{
        vector<double> root;
        KdTree* parent;
        KdTree* leftChild;
        KdTree* rightChild;
        //默认构造函数
        KdTree(){parent = leftChild = rightChild = NULL;}
        //判断kd树是否为空
        bool isEmpty()
        {
            return root.empty();
        }
        //判断kd树是否只是一个叶子结点
        bool isLeaf()
        {
            return (!root.empty()) && 
                rightChild == NULL && leftChild == NULL;
        }
        //判断是否是树的根结点
        bool isRoot()
        {
            return (!isEmpty()) && parent == NULL;
        }
        //判断该子kd树的根结点是否是其父kd树的左结点
        bool isLeft()
        {
            return parent->leftChild->root == root;
        }
        //判断该子kd树的根结点是否是其父kd树的右结点
        bool isRight()
        {
            return parent->rightChild->root == root;
        }
    };
    
    int data[6][2] = {{2,3},{5,4},{9,6},{4,7},{8,1},{7,2}};
    
    template<typename T>
    vector<vector<T> > Transpose(vector<vector<T> > Matrix)
    {
        unsigned row = Matrix.size();
        unsigned col = Matrix[0].size();
        vector<vector<T> > Trans(col,vector<T>(row,0));
        for (unsigned i = 0; i < col; ++i)
        {
            for (unsigned j = 0; j < row; ++j)
            {
                Trans[i][j] = Matrix[j][i];
            }
        }
        return Trans;
    }
    
    template <typename T>
    T findMiddleValue(vector<T> vec)
    {
        sort(vec.begin(),vec.end());
        auto pos = vec.size() / 2;
        return vec[pos];
    }
    
    
    //构建kd树
    void buildKdTree(KdTree* tree, vector<vector<double> > data, unsigned depth)
    {
    
        //样本的数量
        unsigned samplesNum = data.size();
        //终止条件
        if (samplesNum == 0)
        {
            return;
        }
        if (samplesNum == 1)
        {
            tree->root = data[0];
            return;
        }
        //样本的维度
        unsigned k = data[0].size();
        vector<vector<double> > transData = Transpose(data);
        //选择切分属性
        unsigned splitAttribute = depth % k;
        vector<double> splitAttributeValues = transData[splitAttribute];
        //选择切分值
        double splitValue = findMiddleValue(splitAttributeValues);
        //cout << "splitValue" << splitValue  << endl;
    
        // 根据选定的切分属性和切分值,将数据集分为两个子集
        vector<vector<double> > subset1;
        vector<vector<double> > subset2;
        for (unsigned i = 0; i < samplesNum; ++i)
        {
            if (splitAttributeValues[i] == splitValue && tree->root.empty())
                tree->root = data[i];
            else
            {
                if (splitAttributeValues[i] < splitValue)
                    subset1.push_back(data[i]);
                else
                    subset2.push_back(data[i]);
            }
        }
    
        //子集递归调用buildKdTree函数
    
        tree->leftChild = new KdTree;
        tree->leftChild->parent = tree;
        tree->rightChild = new KdTree;
        tree->rightChild->parent = tree;
        buildKdTree(tree->leftChild, subset1, depth + 1);
        buildKdTree(tree->rightChild, subset2, depth + 1);
    }
    
    //逐层打印kd树
    void printKdTree(KdTree *tree, unsigned depth)
    {
        for (unsigned i = 0; i < depth; ++i)
            cout << "\t";
                
        for (vector<double>::size_type j = 0; j < tree->root.size(); ++j)
            cout << tree->root[j] << ",";
        cout << endl;
        if (tree->leftChild == NULL && tree->rightChild == NULL )//叶子节点
            return;
        else //非叶子节点
        {
            if (tree->leftChild != NULL)
            {
                for (unsigned i = 0; i < depth + 1; ++i)
                    cout << "\t";
                cout << " left:";
                printKdTree(tree->leftChild, depth + 1);
            }
                
            cout << endl;
            if (tree->rightChild != NULL)
            {
                for (unsigned i = 0; i < depth + 1; ++i)
                    cout << "\t";
                cout << "right:";
                printKdTree(tree->rightChild, depth + 1);
            }
            cout << endl;
        }
    }
    
    
    //计算空间中两个点的距离
    double measureDistance(vector<double> point1, vector<double> point2, unsigned method)
    {
        if (point1.size() != point2.size())
        {
            cerr << "Dimensions don't match!!" ;
            exit(1);
        }
        switch (method)
        {
            case 0://欧氏距离
                {
                    double res = 0;
                    for (vector<double>::size_type i = 0; i < point1.size(); ++i)
                    {
                        res += pow((point1[i] - point2[i]), 2);
                    }
                    return sqrt(res);
                }
            case 1://曼哈顿距离
                {
                    double res = 0;
                    for (vector<double>::size_type i = 0; i < point1.size(); ++i)
                    {
                        res += abs(point1[i] - point2[i]);
                    }
                    return res;
                }
            default:
                {
                    cerr << "Invalid method!!" << endl;
                    return -1;
                }
        }
    }
    //在kd树tree中搜索目标点goal的最近邻
    //输入:目标点;已构造的kd树
    //输出:目标点的最近邻
    vector<double> searchNearestNeighbor(vector<double> goal, KdTree *tree)
    {
        /*第一步:在kd树中找出包含目标点的叶子结点:从根结点出发,
        递归的向下访问kd树,若目标点的当前维的坐标小于切分点的
        坐标,则移动到左子结点,否则移动到右子结点,直到子结点为
        叶结点为止,以此叶子结点为“当前最近点”
        */
        unsigned k = tree->root.size();//计算出数据的维数
        unsigned d = 0;//维度初始化为0,即从第1维开始
        KdTree* currentTree = tree;
        vector<double> currentNearest = currentTree->root;
        while(!currentTree->isLeaf())
        {
            unsigned index = d % k;//计算当前维
            if (currentTree->rightChild->isEmpty() || goal[index] < currentNearest[index])
            {
                currentTree = currentTree->leftChild;
            }
            else
            {
                currentTree = currentTree->rightChild;
            }
            ++d;
        }
        currentNearest = currentTree->root;
    
        /*第二步:递归地向上回退, 在每个结点进行如下操作:
        (a)如果该结点保存的实例比当前最近点距离目标点更近,则以该例点为“当前最近点”
        (b)当前最近点一定存在于某结点一个子结点对应的区域,检查该子结点的父结点的另
        一子结点对应区域是否有更近的点(即检查另一子结点对应的区域是否与以目标点为球
        心、以目标点与“当前最近点”间的距离为半径的球体相交);如果相交,可能在另一
        个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点,接着递归进行最
        近邻搜索;如果不相交,向上回退*/
    
        //当前最近邻与目标点的距离
        double currentDistance = measureDistance(goal, currentNearest, 0);
    
        //如果当前子kd树的根结点是其父结点的左孩子,则搜索其父结点的右孩子结点所代表
        //的区域,反之亦反
        KdTree* searchDistrict;
        if (currentTree->isLeft())
        {
            if (currentTree->parent->rightChild == NULL)
                searchDistrict = currentTree;
            else
                searchDistrict = currentTree->parent->rightChild;
        }
        else
        {
            searchDistrict = currentTree->parent->leftChild;
        }
    
        //如果搜索区域对应的子kd树的根结点不是整个kd树的根结点,继续回退搜索
        while (searchDistrict->parent != NULL)
        {
            //搜索区域与目标点的最近距离
            double districtDistance = abs(goal[(d+1)%k] - searchDistrict->parent->root[(d+1)%k]);
    
            //如果“搜索区域与目标点的最近距离”比“当前最近邻与目标点的距离”短,表明搜索
            //区域内可能存在距离目标点更近的点
            if (districtDistance < currentDistance )//&& !searchDistrict->isEmpty()
            {
    
                double parentDistance = measureDistance(goal, searchDistrict->parent->root, 0);
    
                if (parentDistance < currentDistance)
                {
                    currentDistance = parentDistance;
                    currentTree = searchDistrict->parent;
                    currentNearest = currentTree->root;
                }
                if (!searchDistrict->isEmpty())
                {
                    double rootDistance = measureDistance(goal, searchDistrict->root, 0);
                    if (rootDistance < currentDistance)
                    {
                        currentDistance = rootDistance;
                        currentTree = searchDistrict;
                        currentNearest = currentTree->root;
                    }
                }
                if (searchDistrict->leftChild != NULL)
                {
                    double leftDistance = measureDistance(goal, searchDistrict->leftChild->root, 0);
                    if (leftDistance < currentDistance)
                    {
                        currentDistance = leftDistance;
                        currentTree = searchDistrict;
                        currentNearest = currentTree->root;
                    }
                }
                if (searchDistrict->rightChild != NULL)
                {
                    double rightDistance = measureDistance(goal, searchDistrict->rightChild->root, 0);
                    if (rightDistance < currentDistance)
                    {
                        currentDistance = rightDistance;
                        currentTree = searchDistrict;
                        currentNearest = currentTree->root;
                    }
                }
            }//end if
    
            if (searchDistrict->parent->parent != NULL)
            {
                searchDistrict = searchDistrict->parent->isLeft()? 
                                searchDistrict->parent->parent->rightChild:
                                searchDistrict->parent->parent->leftChild;
            }
            else
            {
                searchDistrict = searchDistrict->parent;
            }
            ++d;
        }//end while
        return currentNearest;
    }
    
    int main()
    {
        vector<vector<double> > train(6, vector<double>(2, 0));
        for (unsigned i = 0; i < 6; ++i)
            for (unsigned j = 0; j < 2; ++j)
                train[i][j] = data[i][j];
    
        KdTree* kdTree = new KdTree;
        buildKdTree(kdTree, train, 0);
    
        printKdTree(kdTree, 0);
    
        vector<double> goal;
        goal.push_back(3);
        goal.push_back(4.5);
        vector<double> nearestNeighbor = searchNearestNeighbor(goal, kdTree);
        vector<double>::iterator beg = nearestNeighbor.begin();
        cout << "The nearest neighbor is: ";
        while(beg != nearestNeighbor.end()) cout << *beg++ << ",";
        cout << endl;
        return 0;
    }

     

     

     

     

     

     

     

     

    

    展开全文
  • KD树详解

    千次阅读 2019-05-17 10:05:45
    2.1、什么是KD树 Kd-树是K-dimension tree的缩写,是对数据点在k维空间(如二维(x,y),三维(x,y,z),k维(x1,y,z..))中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。...
  • KD树

    万次阅读 多人点赞 2019-03-05 21:43:27
    1.的建立; 2.最近邻域搜索(Nearest-Neighbor Search)。 本文讲解旨在讲解Kd-Tree(K-demension tree)的一些粗浅的原理,以及其在计算机视觉的一些应用,既是总结了自己,也是分享给大家,希望...
  • KD树(K-Dimension Tree)

    2020-10-18 15:57:47
    当训练集很大时,计算输入...本质上说,KD树就是一种平衡二叉树。 范围查询 就是给定查询点和查询距离的阈值,从数据集中找出所有和查询点距离小于阈值的数。 K近邻查询 是给定查询点和正整数 KKK,从数据集中找到距离
  • KD树(网易游戏笔试)

    万次阅读 多人点赞 2014-09-27 22:20:33
    从K近邻算法、距离度量谈到KD树、SIFT+BBF算法 前言  前两日,在微博上说:“到今天为止,我至少亏欠了3篇文章待写:1、KD树;2、神经网络;3、编程艺术第28章。你看到,blog内的文章与你于别处所见的...
  • KNN算法和kd树详解(例子+图示)

    千次阅读 多人点赞 2019-03-15 11:29:40
    一、KNN算法 KNN(K-NearestNeighbor)算法既可以用于分类,也可用于回归。这里介绍他的分类用法。 训练集:一堆拥有标签的m维数据,可以表示为: 其中,是标签,即所属类别。...目标:一个测试数据x,预测其所属...
  • 先简要介绍knn——K近邻算法和kd-tree——kd树,然后介绍matlab环境中有关使用kd树的函数。k-d树(k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和...
  • KDTree复杂度

    千次阅读 2013-02-04 13:45:38
    KD Tree Kd-其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-是一种平衡二叉树。 举一示例: 假设有六个二维数据点 = {(2,3),(5,4),(9,6),(4,7),(8,1),(7...
  • Kd-Tree算法原理简析

    万次阅读 2018-05-07 23:31:09
     Kd-Tree是从BST(Binary search tree)发展而来,是一种高维索引形数据结构,常用于大规模高维数据密集的查找比对的使用场景中,主要是最近邻查找(Nearest Neighbor)以及近似最近邻查找(App...
  • 使用KD树进行最近邻查找的例子

    千次阅读 2015-05-04 17:53:36
    使用KD树进行最近邻查找的例子 例1: 查询点(2.1,3.1) 星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最...
  • 统计学习笔记(3)——k近邻法与kd树

    万次阅读 多人点赞 2014-04-17 11:36:58
    在使用k近邻法进行分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决的方式进行预测。由于k近邻模型的特征空间一般是n维实数向量,所以距离的计算通常采用的是欧式距离。关键的是k值的选取,如果k...
  • kd树搜索(k邻近法)

    千次阅读 2018-07-06 16:08:01
    使用KD树进行最近邻查找的例子例1:查询点(2.1,3.1)星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最...
  • PBRT学习笔记: KD树的一点优化技巧

    千次阅读 2011-02-02 16:00:00
    KD树作为光线跟踪的加速结构,一直以来是光线跟踪中的一个研究热点。一个高效的KD树对于光线跟踪算法具有非常重要的意义。本文简单总结下PBRT中的KD树的一些有价值相关内容。首先,我们看一下PBRT中的KD树的一些重要...
  • 数据结构和算法——kd树

    万次阅读 2017-02-03 09:39:05
    一、K-近邻算法K-近邻算法是一种典型的无参监督学习算法,对于一个监督学习任务来说,其mm个训练样本为:{(X(1),y(1)),(X(2),y(2)),⋯,(X(m),y(m))}\left \{ \left ( X^{\left ( 1 \right )},y^{\left ( 1 \right )}...
  • 在使用k近邻法进行分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决的方式进行预测。由于k近邻模型的特征空间一般是n维实数向量,所以距离的计算通常采用的是欧式距离。关键的是k值的选取,如果k...
  • KD-Tree点云去噪

    千次阅读 2018-03-09 13:42:20
    使用KD树进行点云去噪,大致思路: 构建KD树 随机取点求解平均距离 将所有距离超出平均距离两倍的点删掉 实验代码: https://github.com/Yannnnnnnnnnnn/kd_filter.git 实验截图: ...
  •   前言 通过雷达、激光扫描、立体摄像机等三维测量设备获取的点云数据,具有数据量大、分布不均匀等特点。作为三维领域中一个重要的数据来源,点云数据主要是表征目标表面的海量点集合,并不具备传统网格...
1 2 3 4 5 ... 20
收藏数 10,601
精华内容 4,240
关键字:

kd树