C++实现KDTree 附完整代码

目录
  • 简介
  • 举例
  • 分割的作用
    • 一维
    • 二维
    • n维
  • 关于kdtree的重要问题
    • 一.树的建立
  • 关键代码

简介

  k-d树(k-dimensional),是一种分割k维数据空间的数据结构(对数据点在k维空间中划分的一种数据结构),主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。

kdTree概念

kd-tree或者k维树是计算机科学中使用的一种数据结构,用来组织表示k维空间中点的集合。它是一种带有其他约束条件的二分查找树。Kd-tree对于区间和近邻搜索十分有用。一般位于三维空间中的邻域搜索常用kd-tree,因此本文中所有的kd-tree都是三维的kd-tree。

举例

  上图就是一颗kdtree,可以看出kdtree是二叉搜索树的变种。
  kdtree的性质:

  1. kdtree具有平衡的特质,两树叶的高度差不超过1。(树越平衡代表着分割得越平均,搜索的时间越少)
  2. 数据只存放在叶子结点,而根结点和中间结点存放一些空间划分信息(例如划分维度、划分值)。
  3. 将每一个元组按0排序(第一项序号为0,第二项序号为1,第三项序号为2),在树的第n层,第 n%3 项被用粗体显示,而这些被粗体显示的树就是作为二叉搜索树的key值,比如,根节点的左子树中的每一个节点的第一个项均小于根节点的的第一项,右子树的节点中第一项均大于根节点的第一项,子树依次类推。

分割的作用

一维

  对于一个标准的BSTree,每个节点只有一个key值。

  将key值对应到一维的坐标轴上。

  根节点对应的就是2,左子树都在2的左边,右子树都在2的右边,整个一维空间就被根节点分割成了两个部分,当要查找结点0的时候,由于是在2的左边,所以可以放心的只搜索左子树的部分。整个搜索的过程可以看成不断分割搜索区间的过程,直到找到目标节点。

二维

这样的分割可以扩展到二维甚至更多维的情况。

但是问题来了,二维的节点怎么比较大小?

在BSTree中,节点分割的是一维数轴,那么在二维中,就应当是分割平面了,就像这样:

黄色的点作为根节点,上面的点归左子树,下面的点归右子树,接下来再不断地划分,最后得到一棵树就是赫赫有名的BSPTree(binary space partitioning tree). 分割的那条线叫做分割超平面(splitting hyperplane),在一维中是一个点,二维中是线,三维的是面。

n维

KDTree就是超平面都垂直于轴的BSPTree。同样的数据集,用KDTree划分之后就是这样:

黄色节点就是Root节点,下一层是红色,再下一层是绿色,再下一层是蓝色。为了更好的理解KDTree的分割,我们在图形中来看一下搜索的过程,假设现在需要搜寻右下角的一个点,首先要做的就是比较这个点的x坐标和root点的x坐标值,由于x坐标值大于root节点的x坐标,所以只需要在右边搜寻,接下来,要比较该节点和右边红色节点y值得大小...后面依此类推。整个过程如下图:
1.

2.

3.

关于kdtree的重要问题

一.树的建立

1.节点的数据结构

定义:
Node-data - 数据矢量, 数据集中某个数据点,是n维矢量(这里也就是k维)
Range - 空间矢量, 该节点所代表的空间范围
split - 整数, 垂直于分割超平面的方向轴序号
Left - k-d树, 由位于该节点分割超平面左子空间内所有数据点所构成的k-d树
Right - k-d树, 由位于该节点分割超平面右子空间内所有数据点所构成的k-d树
parent - k-d树, 父节点

2. 优化

1.切分维度优化

构建开始前,对比数据点在各维度的分布情况,数据点在某一维度坐标值的方差越大分布越分散,方差越小分布越集中。从方差大的维度开始切分可以取得很好的切分效果及平衡性。

2.中值选择优化

第一种,算法开始前,对原始数据点在所有维度进行一次排序,存储下来,然后在后续的中值选择中,无须每次都对其子集进行排序,提升了性能。

第二种,从原始数据点中随机选择固定数目的点,然后对其进行排序,每次从这些样本点中取中值,来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。

2.最近邻域搜索(Nearest-Neighbor Lookup)

给定一个KDTree和一个节点,求KDTree中离这个节点最近的节点.(这个节点就是最临近点)

这里距离的求法用的是欧式距离。

基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。

这里还有几个细节需要注意一下,如下图,假设标记为星星的点是 test point, 绿色的点是找到的近似点,在回溯过程中,需要用到一个队列,存储需要回溯的点,在判断其他子节点空间中是否有可能有距离查询点更近的数据点时,做法是以查询点为圆心,以当前的最近距离为半径画圆,这个圆称为候选超球(candidate hypersphere),如果圆与回溯点的轴相交,则需要将轴另一边的节点都放到回溯队列里面来。

判断轴是否与候选超球相交的方法可以参考下图:

关键代码

构建KDTree

void KDTree::buildKdTree(KDTree *tree, vector<vector<double>> data, unsigned int depth)
{
    //样本的数量
    unsigned long samplesNum = data.size();
    //终止条件
    if (samplesNum == 0)
    {
        return;
    }
    if (samplesNum == 1)
    {
        tree->root = data[0];
        return;
    }
    //样本的维度
    unsigned long 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->left_child = new KDTree;
    tree->left_child->parent = tree;
    tree->right_child = new KDTree;
    tree->right_child->parent = tree;
    buildKdTree(tree->left_child, subset1, depth + 1);
    buildKdTree(tree->right_child, subset2, depth + 1);
}

查询目标点的最近邻点

vector<double> KDTree::searchNearestNeighbor(vector<double> goal, KDTree *tree)
{
    /*第一步:在kd树中找出包含目标点的叶子结点:从根结点出发,
    递归的向下访问kd树,若目标点的当前维的坐标小于切分点的
    坐标,则移动到左子结点,否则移动到右子结点,直到子结点为
    叶结点为止,以此叶子结点为“当前最近点”
    */
    unsigned long k = tree->root.size();//计算出数据的维数
    unsigned d = 0;//维度初始化为0,即从第1维开始
    KDTree* currentTree = tree;
    vector<double> currentNearest = currentTree->root;
    while(!currentTree->is_leaf())
    {
        unsigned index = d % k;//计算当前维
        if (currentTree->right_child->is_empty() || goal[index] < currentNearest[index])
        {
            currentTree = currentTree->left_child;
        }
        else
        {
            currentTree = currentTree->right_child;
        }
        ++d;
    }
    currentNearest = currentTree->root;

    /*第二步:递归地向上回退, 在每个结点进行如下操作:
    (a)如果该结点保存的实例比当前最近点距离目标点更近,则以该例点为“当前最近点”
    (b)当前最近点一定存在于某结点一个子结点对应的区域,检查该子结点的父结点的另
    一子结点对应区域是否有更近的点(即检查另一子结点对应的区域是否与以目标点为球
    心、以目标点与“当前最近点”间的距离为半径的球体相交);如果相交,可能在另一
    个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点,接着递归进行最
    近邻搜索;如果不相交,向上回退*/

    //当前最近邻与目标点的距离
    double currentDistance = measureDistance(goal, currentNearest, 0);

    //如果当前子kd树的根结点是其父结点的左孩子,则搜索其父结点的右孩子结点所代表
    //的区域,反之亦反
    KDTree* searchDistrict;
    if (currentTree->is_left())
    {
        if (currentTree->parent->right_child == nullptr)
            searchDistrict = currentTree;
        else
            searchDistrict = currentTree->parent->right_child;
    }
    else
    {
        searchDistrict = currentTree->parent->left_child;
    }

    //如果搜索区域对应的子kd树的根结点不是整个kd树的根结点,继续回退搜索
    while (searchDistrict->parent != nullptr)
    {
        //搜索区域与目标点的最近距离
        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->is_empty())
            {
                double rootDistance = measureDistance(goal, searchDistrict->root, 0);
                if (rootDistance < currentDistance)
                {
                    currentDistance = rootDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->left_child != nullptr)
            {
                double leftDistance = measureDistance(goal, searchDistrict->left_child->root, 0);
                if (leftDistance < currentDistance)
                {
                    currentDistance = leftDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->right_child != nullptr)
            {
                double rightDistance = measureDistance(goal, searchDistrict->right_child->root, 0);
                if (rightDistance < currentDistance)
                {
                    currentDistance = rightDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
        }//end if

        if (searchDistrict->parent->parent != nullptr)
        {
            searchDistrict = searchDistrict->parent->is_left()?
                            searchDistrict->parent->parent->right_child:
                            searchDistrict->parent->parent->left_child;
        }
        else
        {
            searchDistrict = searchDistrict->parent;
        }
        ++d;
    }//end while
    return currentNearest;
}

完整代码下载地址:KDTreeC++实现
参考:
https://blog.csdn.net/silangquan/article/details/41483689

https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html

到此这篇关于C++实现KDTree的文章就介绍到这了,更多相关C++实现KDTree内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

到此这篇关于C++实现KDTree 附完整代码的文章就介绍到这了,更多相关C++实现KDTree内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现KDTree 附完整代码

    目录 简介 举例 分割的作用 一维 二维 n维 关于kdtree的重要问题 一.树的建立 关键代码 简介   k-d树(k-dimensional),是一种分割k维数据空间的数据结构(对数据点在k维空间中划分的一种数据结构),主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索). kdTree概念 kd-tree或者k维树是计算机科学中使用的一种数据结构,用来组织表示k维空间中点的集合.它是一种带有其他约束条件的二分查找树.Kd-tree对于区间和近邻搜索十分有用.一般位于三维空间中的邻

  • JAVA实现用户抽奖功能(附完整代码)

    需求分析 1)实现三个基本功能:登录.注册.抽奖. 2)登录:用户输入账号密码进行登录,输入账号后会匹配已注册的用户,若输入用户不存在则退出,密码有三次输入机会,登录成功后主界面会显示已登录用户的账号信息. 3)注册:用户首先输入账号名称,系统查询此名称是否存在,如存在则请求用户换一个名称,否则进入密码输入,密码要求6位数字字符串,注册成功后,系统随机分配一个与已有用户不重复的四位数字id编号. 4)抽奖:功能实现前提:需有用户处于登录状态.该前提满足时,系统从已存在用户中随机抽取5位不同的用户

  • Python统计词频并绘制图片(附完整代码)

    效果 1 实现代码 读取txt文件: def readText(text_file_path): with open(text_file_path, encoding='gbk') as f: # content = f.read() return content 得到文章的词频: def getRecommondArticleKeyword(text_content, key_word_need_num = 10, custom_words = [], stop_words =[], quer

  • c语言实现简易版三子棋(附完整代码)

    目录 一.菜单栏 二.初始化棋盘 三.打印棋盘 四.玩家下棋 五.电脑下棋 六.判断输赢 七.调用玩家.电脑下棋函数和判断输赢函数 八.全部代码 总结 一.菜单栏 1.制作一个简易版的菜单,并附上选项提示 2.因为该程序想至少运行一次,所有选择用do while循环,而选择玩与不玩游戏时,则采用switch case语句比较合适,然后调用相应的函数即可 二.初始化棋盘 1.先创建一个棋盘 为了便于更改棋盘大小,所有采用宏定义的方式来定义其行与列 2.对棋盘进行初始化 起初未下棋时,棋盘应该是空白

  • 用python画个奥运五环(附完整代码)

    完整代码 #绘制奥运五环 import turtle #导入turtle包 turtle.width(15) #定义线条宽度为15 turtle.color("red") turtle.circle(50) turtle.penup() #定义颜色,园半径,抬笔 turtle.goto(120,0) turtle.pendown() #定义线条走向,落笔 turtle.color("green") turtle.circle(50) turtle.penup() t

  • 用c语言实现一个电话薄(附完整代码)

    先看一下这个小程序的效果 这里我为了演示方便,把人数固定为3个: 人数都是可以自定义的: 下面是这个简单的代码: #include<stdio.h> typedef struct con { int num; char name[11]; char tel[10]; }contact; int main() { contact con[3]; int i; for(i=0;i<3;i++) { printf("请输入编号:"); scanf("%d"

  • python政策网字体反爬实例(附完整代码)

    目录 1 字体反爬案例 2 使用环境 3 安装python第三方库 4 查看woff文件 5 woff文件解决字体反爬全过程 5.1 调用第三方库 5.2 请求woff链接下载woff文件到本地 5.3 查看woff文件内容,可以通过以下两种方式 5.5 建立字体反爬后与圆字体间对应关系 5.6 得到结果 6 完整代码如下 总结 字体反爬,也是一种常见的反爬技术,这些网站采用了自定义的字体文件,在浏览器上正常显示,但是爬虫抓取下来的数据要么就是乱码,要么就是变成其他字符.下面我们通过其中一种方式

  • 用python写一个福字(附完整代码)

    目录 前言: 一,扫五福活动如此火爆,为何不自己利用编程来生成福字! 二,完整代码 三,总结 前言: 支付宝 2022 集五福活动正式开启 数据显示,过去六年累计参与支付宝集五福的人数已经超过了 7 亿,每 2 个中国人里就有 1 个曾扫福.集福.送福. 一,扫五福活动如此火爆,为何不自己利用编程来生成福字! 首先作品奉上: ①,导入python库 import io from PIL import Image import requests ②,利用爬虫,获取单个汉字 def get_word

  • c语言实现简易版三子棋(附完整代码)

    目录 一.菜单栏 二.初始化棋盘 三.打印棋盘 四.玩家下棋 五.电脑下棋 六.判断输赢 七.调用玩家.电脑下棋函数和判断输赢函数 八.全部代码 总结 一.菜单栏 1.制作一个简易版的菜单,并附上选项提示 2.因为该程序想至少运行一次,所有选择用do while循环,而选择玩与不玩游戏时,则采用switch case语句比较合适,然后调用相应的函数即可 二.初始化棋盘 1.先创建一个棋盘 为了便于更改棋盘大小,所有采用宏定义的方式来定义其行与列 2.对棋盘进行初始化 起初未下棋时,棋盘应该是空白

  • 用c语言实现一个电话薄(附完整代码)

    先看一下这个小程序的效果 这里我为了演示方便,把人数固定为3个: 人数都是可以自定义的: 下面是这个简单的代码: #include<stdio.h> typedef struct con { int num; char name[11]; char tel[10]; }contact; int main() { contact con[3]; int i; for(i=0;i<3;i++) { printf("请输入编号:"); scanf("%d"

随机推荐