精华内容
下载资源
问答
  • kd树最近邻搜索算法
    2022-05-14 17:47:59

    欢迎关注更多精彩
    关注我,学习常用算法与数据结构,一题多解,降维打击。

    参考资料
    https://blog.csdn.net/qq_34107425/article/details/106321837 查询最近点
    https://blog.csdn.net/qq_38019633/article/details/89555909 查询最近k个点

    代码实现

    
    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    
    
    enum  dimension {
        X=0, Y=1
    };
    
    class P {
    public:
        double first, second;
        int i;
    };
    
    
    bool cmp0(const P a,const  P b) {
        return a.first< b.first;
    }
    
    bool cmp1(const P a, const P b) {
        return a.second< b.second;
    }
    
    class KDNode {
    public:
        dimension d; // 按哪一维划分
        P center; // 分割点
        int i;
        KDNode *left, *right;
    };
    
    const int N =200100;
    
    KDNode nodePool[N];
    int used = 0;
    
    int getNode() {
        nodePool[used].left=NULL;
        nodePool[used].right=NULL;
        used++;
        return used-1;
    }
    
    P points[N];
    
    // 获取方差
    double getVariance(int l, int r, dimension D) {
        double average=0;
        for(int i=l;i<=r;++i) {
            if(D==X) average+=points[i].first;
            if(D==Y) average+=points[i].second;
        }
    
        average /= r-l+1;
    
        double variance=0;
    
        for(int i=l;i<=r;++i) {
            if(D==X) variance+=pow(points[i].first-average, 2);
            if(D==Y) variance+=pow(points[i].second-average, 2);
        }
    
        variance /= r-l+1;
        return variance;
    }
    
    int buildTree(int l, int r) {
        if(l>r)return -1;
        int root =  getNode();
        if (l == r) {
            nodePool[root].d=X;
            nodePool[root].center = points[l];
            nodePool[root].i = points[l].i;
            return root;
        }
    
        // 计算方差
        double varianceX = getVariance(l, r, X);
        double varianceY = getVariance(l, r, Y);
    
        if(varianceY>varianceX) {
            sort(points+l, points+r+1, cmp1);
            nodePool[root].d=Y;
        }
        else {
            sort(points+l, points+r+1, cmp0);
            nodePool[root].d=X;
        }
    
        int mid = (l+r)>>1;
        nodePool[root].center = points[mid];
        nodePool[root].i = points[mid].i;
    
        int left =  buildTree(l, mid-1);
        if(left>=0)nodePool[root].left = &nodePool[left];
    
        int right =  buildTree(mid+1, r);
        if(right>=0)nodePool[root].right = &nodePool[right];
    
        return root;
    }
    
    bool isToLeft(KDNode * root, P target) {
        if(root->d == X) return target.first < root->center.first;
        return target.second < root->center.second;
    }
    
    
    bool isCross(KDNode * root, P target, double r) {
        if(root->d == X) {
            return fabs(target.first - root->center.first)>r;
        }
        return fabs(target.second < root->center.second)>r;
    }
    
    double dis( P a, P b) {
        a.first-=b.first;
        a.second -= b.second;
    
        return sqrt(a.first*a.first + a.second*a.second);
    }
    
    void query(KDNode * root, P target, double &ans) {
        if(root==NULL)return;
    
        bool toLeft;
        // 查询某个分支
        if(root->left && isToLeft(root, target)) {
            query(root->left, target, ans);
            toLeft=true;
        } else if(root->right && !isToLeft(root, target)) {
            query(root->right, target, ans);
            toLeft=false;
        }
    
        // 是否查询另一边
        if(isCross(root, target, ans)) {
            if(toLeft && root->right) query(root->right, target, ans);
            if(!toLeft && root->left) query(root->left, target, ans);
        }
    
        // 计算自身
        if(root->i != target.i)ans = min(ans, dis(root->center, target));
    }
    
    
    void solve() {
        int n=0;
        while(scanf("%d", &n)!=EOF &&n) {
            used = 0;
            for(int i=0;i<n;i++) {
                scanf("%lf%lf",&points[i].first, &points[i].second);
                points[i].i=i;
            }
    
            int root = buildTree(0, n-1);
    
            for(int i=0;i<n;i++) {
                double m = dis(points[i], points[1]);
                if(i)m = dis(points[i], points[0]);
                query(&nodePool[root], points[i], m);
    
                printf("%.2lf\n", m/2);
            }
    
        }
    }
    
    
    
    int main() {
        solve();
    
        return 0;
    }
    /*
    
     */
    

    本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

    更多相关内容
  • 李航统计学习方法(第二版)(六):k近邻算法实现(kd tree方法)中,对kd树进行了介绍,包括,kd树的简介、kd树的建立以及kd树搜索。在看到李航老师书中对kd树搜索算法的描述后,其中对于递归回退的操作描述不是...

    李航统计学习方法(第二版)(六):k近邻算法实现(kd tree方法)中,对kd树进行了介绍,包括,kd树的简介、kd树的建立以及kd树的搜索。在看到李航老师书中对kd树搜索算法的描述后,其中对于递归回退的操作描述不是很理解,觉得太抽象了(很可能是我自己的理解能力的问题)。对比多个源码(各个源码都还有我觉得有问题的地方,有时间我会在各博主博客下面留言,主要有:1.c++实现kdTree创建以及最近邻点查找,2. KDTree的C++实现),最后靠蛮力弄明白kdtree最近邻搜索的算法,特此记录一下。

    文章目录

    一、kd树最近邻搜索算法

    李航老师《统计学习方法(第二版)》中的kdtree最近邻搜索算法引出如下:
    在这里插入图片描述
    在这里插入图片描述

    其中,算法最核心的部分是(3.a)与(3.b)这两句。我比较难以想象的是(3.b)中:

    如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点。接着,递归地进行最近邻搜索;

    如何移动到另一个子结点?然后又如何递归地进行最近邻搜索?

    网上找了很多博客,大部分都是学舌似的话,根本没有提供比书中这段话更多的信息。很多博客中给的例子,点到为止,一个简单的例子根本不会触发什么[移动到另一个子结点。接着,递归地进行最近邻搜索]好么!

    于是寄希望于看别人实现的源码来弄清楚整个算法,因为源码必定是细节的。CSDN博主nnzzll的实现就很简洁清晰,github|nnzzll/NaiveKDTree。我借着他的代码一步一步在脑中虚拟的运行着一棵kdtree,终于知道[移动到另一个子结点。接着,递归地进行最近邻搜索]的意思了。虽然,nnzzll的代码也存在问题,我在他那篇博客下也留言了,希望之后与之有更多的交流。

    不废话,下面开始用图与例子对这个过程进行说明。

    二、一个二维kdtree的例子

    假定我们有一个二维数据集 [ ( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) ] [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)] [(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)], 我们按照如下所示的kdtree构建算法,可以得到一棵kdtree。(注:如何构建kdtree不是本文的重点,所以不多赘述
    在这里插入图片描述
    由二维数据集 [ ( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) ] [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)] [(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)]构建的kdtree如下图:
    在这里插入图片描述

    该kdtree表示成空间形式如下图所示:
    在这里插入图片描述

    三、kdtree最近邻搜索步骤图示

    假定给定目标数据点 ( 6 , 6 ) (6, 6) (6,6),我们基于上面构建的kdtree树,来说明如何搜索得到离 ( 6 , 6 ) (6, 6) (6,6)最近的数据点。
    在这里插入图片描述

    step 1:李航书中最近邻搜索算法第一步:

    在这里插入图片描述
    按以上步骤,从kdtree根节点 ( 7 , 2 ) (7,2) (7,2)开始向下搜索,路径为 ( 7 , 2 ) , ( 5 , 4 ) , ( 4 , 7 ) (7,2),(5,4),(4,7) (7,2),(5,4),(4,7),其中, ( 4 , 7 ) (4,7) (4,7)为叶子节点。我们将该步骤中经过的节点压入待比较节点队列(该队列为先进后出队列)。下图左边显示的是经过step1后的待比较节点队列,根节点 ( 7 , 2 ) (7,2) (7,2)在栈底部,叶子节点 ( 4 , 7 ) (4,7) (4,7)在栈顶部;下图右边显示的经过step1经过的节点(红色显示)。
    在这里插入图片描述

    step 2:初始化当前最近距离与最近节点

    李航书中最近邻搜索算法第二步:以此叶结点为“当前最近点”
    在这里插入图片描述
    以step 1中的,也即待比较节点队列的栈顶节点 ( 4 , 7 ) (4,7) (4,7)来初始化与目标点 ( 6 , 6 ) (6,6) (6,6)当前最近节点当前最近距离

    通过计算 ( 6 , 6 ) (6, 6) (6,6) ( 4 , 7 ) (4,7) (4,7)的距离,可得当前最近距离 d m i n = 2.23 d_{min}=2.23 dmin=2.23当前最近节点 ( 4 , 7 ) (4,7) (4,7)

    在这里插入图片描述

    step 3:持续地从待比较节点队列中压出栈顶节点,执行李航老师书上的第三步中的(a)与(b):

    在这里插入图片描述

    3.1: 取出栈顶节点为 ( 4 , 7 ) (4,7) (4,7),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    执行算法(3.a):如果该节点保存的实例点比当前最近点距离目标点更近,则以该实例点为当前最近节点

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 4 , 7 ) (4,7) (4,7)的欧式距离为2.23,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    执行算法(3.b):检测该节点的兄弟节点(更一般的说法是兄弟子kdtree)(该节点父节点的另一个子树)有没有可能包含最近节点。具体地,检查兄弟结点对应的区域是否以目标点为球心、以目标点与当前最近节点间的距离为半径的超球体相交。如果相交,可能在另一个子节点对应的区域内存在距目标点更近的点,移动到另一个子节点。接着,递归地进行最近邻搜索

    我们得出如下图的圆与父节点 ( 5 , 4 ) (5,4) (5,4)用来划分左子树与右子树的维度为 y y y,也即 y = 4 y=4 y=4有相交,说明节点 ( 5 , 4 ) (5,4) (5,4)的另一子树区域(左子树)可能存在离目标点 ( 6 , 6 ) (6, 6) (6,6)更近的节点。当前访问节点为 ( 4 , 7 ) (4,7) (4,7),在其父节点的右边,所以递归地对其父节点 ( 5 , 4 ) (5,4) (5,4)的左子树区域进行最近邻搜索。
    在这里插入图片描述

    移动到另一个子节点。接着,递归地进行最近邻搜索

    经过kd树搜索算法(3.b),我们知道节点 ( 5 , 4 ) (5,4) (5,4)左子树可能存在最近节点,因此要对该子树进行最近邻搜索。在程序实现上有两种方式:

    1)将整个最近邻搜索写成可递归的函数findNearestPoint(kdtree, pt);
    2) 用堆栈队列实现。

    用第一种方式,我们只需要在findNearestPoint(kdtree, pt)中从叶子节点循着父节点往上,一直到根节点进行访问,中途若出现某个访问节点的兄弟子树可能存在最近节点(根据kd树搜索算法(3.b)可判断),则用兄弟子kdtree(假定为brother_kdtree)调用findNearestPoint(brother_kdtree, pt),构成一个嵌套调用。代码比较美观。

    用第二种方式的优点是比较直观。用一个先入先出的队列来存储待比较节点队列,在原理上是和第一种嵌套调用方式是一样的。本文为了更直观,所以采用第二种方式。

    按照step 1中的,最近邻搜索算法中如下所示的第一步,对子树进行遍历,至到叶子节点。
    在这里插入图片描述
    由于,节点 ( 4 , 7 ) (4, 7) (4,7)的兄弟子树只有一个节点 ( 2 , 3 ) (2,3) (2,3),它的根节点也是叶子节点。因此,访问节点路径中只有一个节点 ( 2 , 3 ) (2,3) (2,3),将其加入待比较节点队列

    在这里插入图片描述

    3.2: 取出栈顶节点为 ( 2 , 3 ) (2,3) (2,3),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 2 , 3 ) (2,3) (2,3)的欧式距离为5.0,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    由于节点 ( 2 , 3 ) (2,3) (2,3)的兄弟节点 ( 4 , 7 ) (4,7) (4,7)(或者说是以 ( 4 , 7 ) (4,7) (4,7)为根结点的子kd树)已经被访问,所以跳过该步骤。

    3.3: 取出栈顶节点为 ( 5 , 4 ) (5,4) (5,4),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 5 , 4 ) (5,4) (5,4)的欧式距离为2.23,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    节点 ( 5 , 4 ) (5,4) (5,4)的父节点 ( 7 , 2 ) (7,2) (7,2)的右子树(以节点 ( 9 , 6 ) (9,6) (9,6)为根节点)是其兄弟子树,如下图可知,以 ( 6 , 6 ) (6,6) (6,6)为圆心,以2.23为半径的圆与 x = 7 x=7 x=7 ( 7 , 2 ) (7,2) (7,2)的划分维度为 x x x)相交,可知节点 ( 5 , 4 ) (5,4) (5,4)的兄弟子树(以节点 ( 9 , 6 ) (9,6) (9,6)为根节点)可能存在最近节点。

    在这里插入图片描述

    移动到另一个子节点。接着,递归地进行最近邻搜索

    节点 ( 5 , 4 ) (5, 4) (5,4)的兄弟子树是以节点 ( 9 , 6 ) (9, 6) (9,6)为根节点,并且根节点只有一个左叶子节点 ( 8 , 1 ) (8,1) (8,1)

    以目标点 ( 6 , 6 ) (6,6) (6,6)为输入,对该子树进行正向搜索,找到叶子节点。由于目标点的 y = 6 y=6 y=6不小于用于划分的分界线 y = 6 y=6 y=6,按理应该归到节点 ( 9 , 6 ) (9,6) (9,6)的右叶子节点,可是 ( 9 , 6 ) (9, 6) (9,6)不存在右叶子节点。为了在代码上实现统一,遇到这种只有一个子节点的情况,不用按分界线来划分左和右,直接往下走到它的这个唯一子节点即可。
    在这里插入图片描述

    3.4: 取出栈顶节点为 ( 8 , 1 ) (8,1) (8,1),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 8 , 1 ) (8,1) (8,1)的欧式距离为5.3,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    节点 ( 8 , 1 ) (8,1) (8,1)无兄弟子树,故此步骤跳过。

    3.5: 取出栈顶节点为 ( 9 , 6 ) (9,6) (9,6),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 9 , 6 ) (9,6) (9,6)的欧式距离为3.0,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    节点 ( 9 , 6 ) (9,6) (9,6)的兄弟子树已被访问,跳过此步骤。

    3.5: 取出栈顶节点为 ( 7 , 2 ) (7,2) (7,2),并执行下列操作:

    在这里插入图片描述

    --------------------kd树搜索算法(3.a)--------------------------

    计算目标点 ( 6 , 6 ) (6,6) (6,6) ( 7 , 2 ) (7,2) (7,2)的欧式距离为4.12,不比当前最近距离2.23要小,所以不会导致当前最近节点当前最近距离的更新。

    --------------------kd树搜索算法(3.b)--------------------------

    节点 ( 7 , 2 ) (7,2) (7,2)无兄弟子树,跳过此步骤。

    3.6: 取出栈顶节点为NULL,也即待比较节点队列为空,结束搜索。

    备注:结束搜索条件有两种:1)回退到根结点;2)栈顶节点为空。

    第一种结束搜索条件是李航老师《统计学习方法(第二版)》书中的,这个结束条件需要在递归回退之前,也即李书中步骤(2)与步骤(3)之间,加一个判断根节点是否为当前最近节点的步骤,不然会漏掉可能是最近节点的根节点。此方式则将本文中的step 3.5与step 3.6合并为step 3.5:取出栈顶节点为根节点,结束搜索。

    第二种则不用,更加直观,这也是本文采用的方式。

    结尾

    本文以二维数据集[ ( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) ] 构建的kdtree为例,用(6,6)作为目标点,事实上证明 ( 6 , 6 ) (6,6) (6,6)作为目标点使这个例子非常复杂,最终把所有的节点都访问了一遍。本文也正是想采用这样一个复杂的例子,把这个kdtree最近邻搜索算法说透。

    如果你愿意的话,用同样的例子去走一遍c++实现kdTree创建以及最近邻点查找KDTree的C++实现中给出的代码。你会发现,博主们手撸的代码能覆盖我们在网上看到的那些简单情况,但是对于本文中给出的情况却cover不了。这也说明,他们代码并没有完全复现算法的思想。

    如果这篇博客有幸被两位博主看到,我先借这个机会向你们道声感谢。你们的博客的确给了我很多思考的方式,包括采用堆栈的方式来实现最近邻搜索。如对文中观点持不同意见,请狠狠踩我吧!欢迎一起交流,然后一起成长。

    展开全文
  • 主要介绍了python K近邻算法kd树实现,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • python实现kd树以及最近邻查找算法

    千次阅读 2022-04-26 21:59:44
    python实现kd树以及最近邻查找算法一、kd树简介二、kd树生成1.确定切分域2.确定数据域3.理解递归4.python实现递归代码三、kd树上的最近邻查找算法 一、kd树简介 kd树是一种形结构,的每个节点存放一个k维...

    一、kd树简介

    kd树是一种树形结构,树的每个节点存放一个k维数据,某一节点的子节点可以看作是由过该节点一个平面切割后产生的(想象一下切蛋糕的过程),如此反复产生切割平面,就能为每个数据在空间中建立索引,如下图所示:
    在这里插入图片描述
    由于采用这种特殊的分割方式,使得在利用kd树做最近邻查找时,可以避开一些距离很远的点,查找速度得到了较大的提升,对于空间中Nk维数据,穷举法的算法复杂度为O(Nk),而使用kd树查找的算法复杂度只有O(klog(N))。kd树是一种典型的空间换时间的方式,即花费存储空间为数据建立索引,这样使得后续查找时速度更快,花费时间更少。

    二、kd树生成

    具体的算法实现主要参考的是这篇文章:https://www.cnblogs.com/eyeszjwang/articles/2429382.html,实现时有少量改动。生成kd树有两个关键的中间过程,即:

    1.确定切分域

    (1)确定split域:对于所有描述子数据(特征矢量),统计它们在每个维上的数据方差。以SURF特征为例,描述子为64维,可计算64个方差。挑选出最大值,对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开,在这个方向上进行数据分割有较好的分辨率;

    这段文字用通俗一点的语言来说就是:对于二维的情况,每一次做数据切分的时候,沿着x轴还是y轴做切分是一个问题,那么我们要怎么确定呢?我们可以统计这些二维数据的x值和y值的方差,方差越大说明数据在这一方向上越离散,而数据越离散说明沿着这一方向上数据之间的距离区分度越大,简单点来说就是相互之间隔得更远,我们就用这个方向做切分。
    确定了切分域之后,我们就需要来对数据做切分了。

    2.确定数据域

    (2)确定Node-data域:数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set’ = Data-set\Node-data(除去其中Node-data这一点)。

    简单来说,这句话的意思是:现在我们已经确定了沿着x轴做切分,那么我们要怎么决定在x轴哪里做切分呢?我们可以将所有数据根据x值的大小做一个排序,然后选取正中间那个数据的x值作为切分的位置。注意,这里有一个关键的问题是:如果我们有偶数个数据,怎么确定中间那个数据?难道我们选取中间两个数做一下平均???如果没有记错的话这应该是中位数的定义。。。如果这样完全就是自找麻烦!因为我们要确保至少有一个数据的x值落在切分点上,但是取平均之后并不能保证!!!所以更好的办法是,在有两个中间数据的情况下,随便选取一个数据的x值就行了。
    决定了在x轴哪里做切分之后,我们就需要把数据做切分了,这里根据数据的x值相对于切分位置的大小,可以归为左节点和右节点,同时不要忘了:当前主节点也要保存一个数据,选取一个x值大小和切分位置相等的数据保存就行(如果有多个随便选一个就行,关键之处在于这个数据的x值落在切割线上。)

    3.理解递归树

    前面提到过,kd树是一种树形结构,因此可以递归生成,这是树形结构的共性,用程序语言来说,递归就是函数自己调用自己,在理解上也是很自然的。对于一组数据,我们通过找到的一个切分线把数据一分为二,而这个切分线的确定只和这组数据有关,左边的数据归为左节点,右边的数据归为右节点,更进一步,对于左边或者右边的这组数据,我们又可以将其看作一个整体,找到一个切分线把它一分为二,这样将一组数据一分为二的过程反复进行,相当于这个过程函数不断地调用自身,最终生成二叉树,将所有的数据分开。

    4.python实现递归树代码

    ###建立kd树和实现查询功能
    import numpy as np
    import matplotlib.pyplot as plt
    
    class kdTree:
        def __init__(self, parent_node):
            '''
            节点初始化
            '''
            self.nodedata = None   ###当前节点的数据值,二维数据
            self.split = None ###分割平面的方向轴序号,0代表沿着x轴分割,1代表沿着y轴分割
            self.range = None  ###分割临界值
            self.left = None    ###左子树节点
            self.right = None   ###右子树节点
            self.parent = parent_node  ###父节点
            self.leftdata = None  ###保留左边节点的所有数据
            self.rightdata = None ###保留右边节点的所有数据
            self.isinvted = False ###记录当前节点是否被访问过
    
        def print(self):
            '''
            打印当前节点信息
            '''
            print(self.nodedata, self.split, self.range)
    
        def getSplitAxis(self, all_data):
            '''
            根据方差决定分割轴
            '''
            var_all_data = np.var(all_data, axis=0)
            if var_all_data[0] > var_all_data[1]:
                return 0
            else:
                return 1
        
    
        def getRange(self, split_axis, all_data):
            '''
            获取对应分割轴上的中位数据值大小
            '''
            split_all_data = all_data[:, split_axis]
            data_count = split_all_data.shape[0]
            med_index = int(data_count/2)
            sort_split_all_data = np.sort(split_all_data)
            range_data = sort_split_all_data[med_index]
            return range_data
    
    
        def getNodeLeftRigthData(self, all_data):
            '''
            将数据划分到左子树,右子树以及得到当前节点
            '''
            data_count = all_data.shape[0]
            ls_leftdata = []
            ls_rightdata = []
            for i in range(data_count):
                now_data = all_data[i]
                if now_data[self.split] < self.range:
                    ls_leftdata.append(now_data)
                elif now_data[self.split] == self.range and self.nodedata == None:
                    self.nodedata = now_data
                else:
                    ls_rightdata.append(now_data)
            self.leftdata = np.array(ls_leftdata)
            self.rightdata = np.array(ls_rightdata)
    
    
        def createNextNode(self,all_data):
            '''
            迭代创建节点,生成kd树
            '''
            if all_data.shape[0] == 0:
                print("create kd tree finished!")
                return None
            self.split = self.getSplitAxis(all_data)
            self.range = self.getRange(self.split, all_data)
            self.getNodeLeftRigthData(all_data)
            if self.leftdata.shape[0] != 0:
                self.left = kdTree(self)
                self.left.createNextNode(self.leftdata)
            if self.rightdata.shape[0] != 0:
                self.right = kdTree(self)
                self.right.createNextNode(self.rightdata)
    
        def plotKdTree(self):
            '''
            在图上画出来树形结构的递归迭代过程
            '''
            if self.parent == None:
                plt.figure(dpi=300)
                plt.xlim([0.0, 10.0])
                plt.ylim([0.0, 10.0])
            color = np.random.random(3)
            if self.left != None:
                plt.plot([self.nodedata[0], self.left.nodedata[0]],[self.nodedata[1], self.left.nodedata[1]], '-o', color=color)
                plt.arrow(x=self.nodedata[0], y=self.nodedata[1], dx=(self.left.nodedata[0]-self.nodedata[0])/2.0, dy=(self.left.nodedata[1]-self.nodedata[1])/2.0, color=color, head_width=0.2)
                self.left.plotKdTree()
            if self.right != None:
                plt.plot([self.nodedata[0], self.right.nodedata[0]],[self.nodedata[1], self.right.nodedata[1]], '-o', color=color)
                plt.arrow(x=self.nodedata[0], y=self.nodedata[1], dx=(self.right.nodedata[0]-self.nodedata[0])/2.0, dy=(self.right.nodedata[1]-self.nodedata[1])/2.0, color=color, head_width=0.2)
                self.right.plotKdTree()
            # if self.split == 0:
            #     x = self.range
            #     plt.vlines(x, 0, 10, color=color, linestyles='--')
            # else:
            #     y = self.range
            #     plt.hlines(y, 0, 10, color=color, linestyles='--')
    
    
    test_array = 10.0*np.random.random([30,2])
    my_kd_tree = kdTree(None)
    my_kd_tree.createNextNode(test_array)
    my_kd_tree.plotKdTree()
    

    这里代码中使用了Python面向对象技术,kdTree类的重要参数和前面给出的参考文章中的参数大致相同,具体代码细节不再说明,这里随机生成了30个范围在0-10之内的2维数据作为测试数据,下图是一次运行得到的结果:
    在这里插入图片描述
    可以很容易看到中间橙色的点就是根节点,以及每个节点的迭代过程,运行过程无误。

    三、kd树上的最近邻查找算法

    加快对目标数据的最近邻数据的搜索过程,是kd树这种特殊存储结构的最主要功能,尤其是在数据量非常大时,其速度优势更加明显。kd树上的最近邻查找算法主要涉及两个过程,即:

    1.生成搜索路径

    这一过程相对容易,也很好理解。由于我们之前已经根据不同的切分线,生成了包含所有数据点的kd树,那么现在给我们一个新的数据,我们首先当然是根据这些切分线来判断待查找的数据是属于哪个分区的,我们当然有理由相信与这个数据同属一个分区的数据点(即某个叶节点)是其最近邻点的概率比不同分区的点的概率要大。因此,我们通过对目标数据的二叉查找,可以确定出一条搜索路径以及初始的最近邻点,但是要注意的是,通过二叉查找找到的叶节点是目标点的最近邻点的可能性较大,但不是一定的,如下图:
    在这里插入图片描述
    目标点落在了y=4的上半平面,但是其最近邻点却在y=4的下半平面,所以这里我们初步搜索出来的一个叶节点并不一定是目标点的最近邻点,我们还需要不断地沿着搜索路径回溯,确定同一主节点的其它子节点中是否存在与目标点距离更近的点。

    2.搜索路径回溯

    为了实现路径回溯的功能,这里需要使用来存储搜索路径,具体说来,当回溯到某一节点的父节点时,需要判断目标点到该父节点对应切分线的距离是否小于当前的最小距离,如果比最短距离还小,说明在该父节点对应的另一分支中有可能存在与目标点距离更小的点,因此就需要搜索该分支中的节点。
    为了更加形象地说明,还是以上图为例。首先通过二分查找我们确定目标点与(4,7)点落在同一域内,因此将(4,7)作为初始最近邻点,然后向上回溯到(5,4)点,而(5,4)点对应的切分线是y=4,通过计算发现目标点到直线y=4的距离小于当前最短距离,因此在目标点的对侧即(5,4)节点的另一分支可能存在与目标点距离更近的点,因此我们需要跳到另一分支中重新检索,这里由于另一分支的深度不一定和前一分支相同,因此在跳到另一分支的头节点之后,我们还需要在此基础之上重复第1步中的路径搜索过程,到达该分支的叶节点,然后重复向上回溯查找直到将搜索路径全部回溯完成,我们就可以得到目标点的最近邻点。
    这其中还有一个值得注意的地方,就是向上回溯时为了避免路径在两个分支之间来回跳跃导致死循环,需要将整个回溯过程中访问过的节点从路径中去掉,用一个标签来指示就可以,上述代码中使用的是
    isinvted
    来标记当前节点是否被访问过。

    3.最近邻查找算法代码

    具体代码实现是在以上kdTree类的基础上在添加几个内部函数就可以了,具体添加的函数为:

    	def divDataToLeftOrRight(self, find_data):
            '''
            根据传入的数据将其分给左节点(0)或右节点(1)
            '''
            data_value = find_data[self.split]
            if data_value < self.range:
                return 0
            else:
                return 1
    
        def getSearchPath(self, ls_path, find_data):
            '''
            二叉查找到叶节点上
            '''
            now_node = ls_path[-1]
            if now_node == None:
                return ls_path
            now_split = now_node.divDataToLeftOrRight(find_data)
            if now_split == 0:
                next_node = now_node.left
            else:
                next_node = now_node.right
            while(next_node!=None):
                ls_path.append(next_node)
                next_split = next_node.divDataToLeftOrRight(find_data)
                if next_split == 0:
                    next_node = next_node.left
                else:
                    next_node = next_node.right
            return ls_path
                
        def getNestNode(self, find_data, min_dist, min_data):
            '''
            回溯查找目标点的最近邻距离
            '''
            ls_path = []
            ls_path.append(self)
            self.getSearchPath(ls_path, find_data)
            now_node = ls_path.pop()
            now_node.isinvted = True
            min_data = now_node.nodedata
            min_dist = np.linalg.norm(find_data-min_data)
            while(len(ls_path)!=0):
                back_node = ls_path.pop()   ### 向上回溯一个节点
                if back_node.isinvted == True:
                    continue
                else:
                    back_node.isinvted = True
                back_dist = np.linalg.norm(find_data-back_node.nodedata)
                if back_dist < min_dist:
                    min_data = back_node.nodedata
                    min_dist = back_dist
                if np.abs(find_data[back_node.split]-back_node.range) < min_dist:
                    ls_path.append(back_node)
                    if back_node.left.isinvted == True:
                        if back_node.right == None:
                            continue
                        ls_path.append(back_node.right)
                    else:
                        if back_node.left == None:
                            continue
                        ls_path.append(back_node.left)
                    ls_path = back_node.getSearchPath(ls_path, find_data)
                    now_node = ls_path.pop()
                    now_node.isinvted = True
                    now_dist = np.linalg.norm(find_data-now_node.nodedata)
                    if now_dist < min_dist:
                        min_data = now_node.nodedata
                        min_dist = now_dist
            print("min distance:{}  min data:{}".format(min_dist, min_data))
            return min_dist
    
        def getNestDistByEx(self, test_array, find_data, min_dist, min_data):
            '''
            穷举法得到目标点的最近邻距离
            '''
            data_count = test_array.shape[0]
            min_data = test_array[0]
            min_dist = np.linalg.norm(find_data-min_data)
            for i in range(data_count):
                now_data = test_array[i]
                now_dist = np.linalg.norm(find_data-now_data)
                if now_dist < min_dist:
                    min_dist = now_dist
                    min_data = now_data
            print("min distance:{}  min data:{}".format(min_dist, min_data))
            return min_dist
    

    代码的对齐格式是一致的,直接加入以上类中就可以,当然为了对比以及验证结果的正确性,在类中还实现了穷举查找算法。首先用50个点测试了一下回溯查找结果的正确性,绘制的结果如下:
    在这里插入图片描述
    查找的目标点是(5.0, 5.0),查找到的最近邻点在目标点左下角,从图上来看结果是正确的。为了对比穷举法和利用kd树回溯查找的速度,数据点设置为10000个,代码为:

    test_array = 10.0*np.random.random([10000,2])   ### 随机生成n个2维0-10以内的数据点
    my_kd_tree = kdTree(None)                    ### kd树实例化
    my_kd_tree.createNextNode(test_array)        ### 生成kd树
    # my_kd_tree.plotKdTree()   
    find_data = np.array([5.0, 5.0])             ### 待查找目标点
    min_dist = 0                                 ### 临时变量,存储最短距离
    min_data = np.array([0.0, 0.0])              ### 临时变量,存储取到最短距离时对应的数据点
    
    %time min_dist = my_kd_tree.getNestNode(find_data, min_dist, min_data)        ### 利用kd树回溯查找
    %time min_dist = my_kd_tree.getNestDistByEx(test_array, find_data, min_dist, min_data)    ### 穷举法查找
    

    用%time命令来显示单步运行查找算法所需的时间,运行结果如下:
    在这里插入图片描述
    可以看到两种算法最终查找到的最短距离以及最近邻数据点都是一样的,证明了算法的正确性。同时kd树查找过程只用了1ms左右,而穷举法查找用了70ms左右,二者相差了70倍,当然随着数据量增大这个差距还会继续增加的,最终应该会趋于某个极限值。

    展开全文
  • 1.5KD树最近邻搜索算法 1.5.1举例:查询点(2.1,3.1) 1.5.2 举例:查询点(2,4.5) 2 kd树近邻搜索算法的改进:BBF算法 3 球、M、VP、MVP 3.1球 3.2VP与MVP简介 特征点匹配和数据库查、...

    目录

    1 KD树

    1.1 什么是KD树

    1.2 KD树的构建

    1.3 KD树的插入

    1.4 KD树的删除

    1.5 KD树的最近邻搜索算法

    1.5.1 举例:查询点(2.1,3.1)

    1.5.2 举例:查询点(2,4.5)

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

    3 球树、M树、VP树、MVP树

    3.1 球树

    3.2 VP树与MVP树简介


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

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

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

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

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

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

    1 KD树

    1.1 什么是KD树

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

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

    1.2 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树的数据结构:

            

    /** 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树的插入、删除、查找操作。

    1.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也按照一分为二的规则继续划分。

    1.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结点,请看一系列删除步骤:

         

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

         

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

          

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

          

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

             

            (4)在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)

    1.5 KD树的最近邻搜索算法

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

           

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

    1.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。

    1.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)。

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

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

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

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

    复杂度分析:

     

    操作

    平均复杂度

    最坏复杂度

    新增节点

    O(logn)

    O(n)

    删除节点

    O(logn)

    O(n)

    最近邻搜索

    O(logn)

    O(n)

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

     

        也正因为上述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,直到优先队列为空。

        如你在下图所见到的那样:

                 

    3 球树、M树、VP树、MVP树

    3.1 球树

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

            

        现要找它的最近邻。

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

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

             

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

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

           

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

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

            

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

          

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

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

               

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

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

    3.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)。
     

    KD树详解:https://blog.csdn.net/Galaxy_yr/article/details/89285069?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_utm_term-1&spm=1001.2101.3001.4242

    KD树:https://www.cnblogs.com/kexinxin/p/11795447.html

    从K近邻算法、距离度量谈到KD树、SIFT+BBF算法:https://blog.csdn.net/v_july_v/article/details/8203674

     

     

    展开全文
  • Kd树实现K近邻算法

    2022-02-05 18:57:13
    第三章:K近邻算法,基于kd树
  • 由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据。但是,最近邻算法明显是存在缺陷的,...
  • 这次我们就先来总结下 最近邻算法(NN)中的KD树的相关知识点。 问题的产生 最近邻搜索(Nearest Neighbor Search)是指在一个确定的距离度量和一个搜索空间内寻找与给定查询项距离最小的元素。暴力搜索的解法时间...
  • KD树详解及KD树最近邻算法

    千次阅读 2019-12-24 14:37:27
    Kd-是K-dimension tree的缩写,是对数据点在k维空间(如二维(x,y),三维(x,y,z),k维(x,y,z..)中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索最近邻搜索)。 k-d是一种空间...
  • 算法思想来自于李航的《统计学习方法》本文主要实现其kd树最近邻搜索 构造代码已经发表过了,现在也还是写一下, //为了方便储存数据 public class Data { public double x1; public double x2; } //kd树的...
  • 一篇博客断断续续写了几天,太难了) 5.3.2、kd树搜索 向下遍历kd树搜索包含分类节点的叶子节点: 向上遍历搜索与待分类节点最近的节点: 5.4、结果展示 用于算法验证数据集为机器学习中常用的鸢尾花数据集,该数据集...
  • k-d最近邻搜索算法

    千次阅读 2021-01-14 15:40:03
    下面介绍最简单的k-d tree最近邻搜索算法。基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,大于就进入右子分支直到叶子结点),顺着“搜索路径...
  • 李航KD树最近邻搜索

    2019-12-04 21:13:02
    李航老师书上的的算法说明没怎么看懂,看了网上的博客,悟出一套循环(建立好KD树以后的最近邻搜索),我想应该是这样的(例子是李航《统计学习算法》第三章56页;例3.3):   步骤 结点查询标记 栈内...
  • K-近邻算法kd树

    2021-03-06 23:18:59
    K-近邻算法kd树 问题导入: 实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索。 这在特征空间的维数大及训练数据容量大时尤其必要。 k近邻法最简单的实现是线性扫描(穷举搜索),即要计算...
  • 最近邻查找算法kd-tree

    万次阅读 多人点赞 2016-08-12 10:12:01
    海量数据最近邻查找的kd-tree简介  利用Octree,為封閉的3D空間建立一個資料結構來管理空間中的每個元素。如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。  3D空間可以用Octree,2D空間可以用Quadtree(四...
  • KNN(K-Nearest Neighbor即K近邻),监督学习算法。 当预测一个新的值x的时候,根据它距离最近的K个点是什么类别来判断属于哪个类别。做分类也可以做回归。
  • 最快搜索kd树

    2014-12-25 12:29:41
    一种最快的搜索kds的实现,时间搜索的效率更高
  • 当k等于1时,k近邻则为最近邻。k值一般选择比较小的值,通常采用交叉验证的方法来选取最优的k值。 距离一般使用欧氏距离,曼哈顿距离,minkowski距离。 分类的决策规则,多数表决,当分类的损失函数是0-1损失函数...
  • 特征匹配--KD树
  • 基于kdtree 的点云邻近点的匹配与搜索。点的深度搜索
  • K近邻 kd树 搜索算法 python实现

    千次阅读 2019-02-27 16:08:18
    文章目录K近邻 k维kd树搜索算法 python实现python数据结构之二叉树kd树算法介绍构造平衡kd树kd树最近邻搜索kd树算法python实现参考文献 K近邻 k维kd树搜索算法 python实现 在KNN算法中,当样本数据量非常大时...
  • 范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据另一种是K近邻查询,就是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。...
  • 从K近邻算法、距离度量谈到KD树

    千次阅读 2016-07-18 19:49:10
    1.本文首先讲述了K近邻算法,然后讲述了相关的距离度量表示法 2.讲K近邻算法的实现–KD树,和KD树的插入,删除,最近邻查找等操作第一部分、K近邻算法
  • k-d树最近邻搜索算法伪代码: ''' 输入:k-d树根节点root,要查询的结点target 输出:k-d中距离target最近的结点nearest_node ''' search(root, target): ## 1. 进行二叉查找,建立搜索路径,直到找到一个叶结点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,447
精华内容 1,778
热门标签
关键字:

kd树最近邻搜索算法

友情链接: crc.rar