【计算方法】正交区域查询---KD-Tree概念

   

一、说明

        kd 树是一种二叉树数据结构,可以用来进行高效的 kNN 计算。kd 树算法偏于复杂,本篇将先介绍以二叉树的形式来记录和索引空间的思路,以便读者更轻松地理解 kd 树。

二、正交区域查找

2.1 定义

        对于k维空间的张量数据表格,如果需要找出超立方体的区域内部数据的查找方法。之所以称之为正交区域查找,是因为在k维张量中,属性维度的空间相互无关。
        而许多信息的查询是可以转化为正交区域查找的,例如问一堆员工中,年龄在[a,b],工资在[l,r]中的有几个,家庭人数为【n,m】。这个有很多做法,什么树套树之类的。而一种思路是,把员工的年龄x、工资y、家庭成员z,映射到三维平面上的点(x,y,z)上,这样就可以进行正交区域查找了,即查找一个矩形中点的个数。


        对于更高维查询,我们需要一个数据结构,该结构可以在任何维数下使用 。* 注意:如果用树嵌套查询不足以构成各维度对等模型,因此,二叉树的迭代查询是不可取的。

 2.2 引进KD树

        先解释一下名字,K是维数,D是Dimension,即维。“树”表明他是树的结构。基本地,KD树中一个节点储存了:

  • K维空间域,(例如三维中的一个长方体),
  • 一个K维点的坐标
  • 两个儿子下标

        在平衡树中,我们知道:可以维护以每个节点为根的子树权值的min和max。
        如法泡制,K维空间域与此很类似,维护的是子树点的坐标范围。

const int K=3;
struct KD_Tree
{
    int d[K],son[2];
    int x[2],y[2],z[2]     ;//Range[K][2];
} tr[N];

        如上代码,P为节点储存的原图的点坐标,son为儿子,第二行储存了K维空间域。

2.3 构造Kd树

基本思想:

  • KD树是一颗平衡二叉树,其中每个非叶节点,可以想象一个超平面,用来分割其储存的空间域,其中超平面垂直于坐标轴。
  • 树尽量平衡,超平面划分的两个空间内的点尽量一样多。
  • 为了有扩展性,树的每一层的超平面垂直的坐标轴,要轮流来取。即第一层垂直x轴,第二层垂直y轴,第三层垂直z轴····

        垂直某个轴,意味着以这个轴的坐标为关键字来操作。
        例如这次要垂直x轴,我们取当前点集的x坐标的中位数,然后把它作为切分点,切分点作为父节点,即KD树中新节点储存的点;切开的两边的点分别属于左右子树的点集。

2.4 二维的例子说明原理

1)有二维点如下图:

 2)建立2d的平衡树x轴节点

        在x轴上找二分线l1

3)建立2d的平衡树y轴节点

深度优先算法:

  • 在x的l1线的左侧找到y轴上的二分线l2

  • 在l1和l2包含区域找x的二分线l4

 

 

 

 

完成图:

 

三、三维度示例研究

3.1 假如下面例子

这是一个例子:血型、血小板数、血压三个指标。就按照x,y,z交替选中进行二叉树构建。

3.2 构建示例代码(python)

下面给出构造代码

class KDTree(object):
    
    """
    A super short KD-Tree for points...
    so concise that you can copypasta into your homework 
    without arousing suspicion.
    This implementation only supports Euclidean distance. 
    The points can be any array-like type, e.g: 
        lists, tuples, numpy arrays.
    Usage:
    1. Make the KD-Tree:
        `kd_tree = KDTree(points, dim)`
    2. You can then use `get_knn` for k nearest neighbors or 
       `get_nearest` for the nearest neighbor
    points are be a list of points: [[0, 1, 2], [12.3, 4.5, 2.3], ...]
    """
    def __init__(self, points, dim, dist_sq_func=None):
        """Makes the KD-Tree for fast lookup.
        Parameters
        ----------
        points : list<point>
            A list of points.
        dim : int 
            The dimension of the points. 
        dist_sq_func : function(point, point), optional
            A function that returns the squared Euclidean distance
            between the two points. 
            If omitted, it uses the default implementation.
        """

        if dist_sq_func is None:
            dist_sq_func = lambda a, b: sum((x - b[i]) ** 2 
                for i, x in enumerate(a))
                
        def make(points, i=0):
            if len(points) > 1:
                points.sort(key=lambda x: x[i])
                i = (i + 1) % dim
                m = len(points) >> 1
                return [make(points[:m], i), make(points[m + 1:], i), 
                    points[m]]
            if len(points) == 1:
                return [None, None, points[0]]
        
        def add_point(node, point, i=0):
            if node is not None:
                dx = node[2][i] - point[i]
                for j, c in ((0, dx >= 0), (1, dx < 0)):
                    if c and node[j] is None:
                        node[j] = [None, None, point]
                    elif c:
                        add_point(node[j], point, (i + 1) % dim)

        import heapq
        def get_knn(node, point, k, return_dist_sq, heap, i=0, tiebreaker=1):
            if node is not None:
                dist_sq = dist_sq_func(point, node[2])
                dx = node[2][i] - point[i]
                if len(heap) < k:
                    heapq.heappush(heap, (-dist_sq, tiebreaker, node[2]))
                elif dist_sq < -heap[0][0]:
                    heapq.heappushpop(heap, (-dist_sq, tiebreaker, node[2]))
                i = (i + 1) % dim
                # Goes into the left branch, then the right branch if needed
                for b in (dx < 0, dx >= 0)[:1 + (dx * dx < -heap[0][0])]:
                    get_knn(node[b], point, k, return_dist_sq, 
                        heap, i, (tiebreaker << 1) | b)
            if tiebreaker == 1:
                return [(-h[0], h[2]) if return_dist_sq else h[2] 
                    for h in sorted(heap)][::-1]

        def walk(node):
            if node is not None:
                for j in 0, 1:
                    for x in walk(node[j]):
                        yield x
                yield node[2]

        self._add_point = add_point
        self._get_knn = get_knn 
        self._root = make(points)
        self._walk = walk

    def __iter__(self):
        return self._walk(self._root)
        
    def add_point(self, point):
        """Adds a point to the kd-tree.
        
        Parameters
        ----------
        point : array-like
            The point.
        """
        if self._root is None:
            self._root = [None, None, point]
        else:
            self._add_point(self._root, point)

    def get_knn(self, point, k, return_dist_sq=True):
        """Returns k nearest neighbors.
        Parameters
        ----------
        point : array-like
            The point.
        k: int 
            The number of nearest neighbors.
        return_dist_sq : boolean
            Whether to return the squared Euclidean distances.
        Returns
        -------
        list<array-like>
            The nearest neighbors. 
            If `return_dist_sq` is true, the return will be:
                [(dist_sq, point), ...]
            else:
                [point, ...]
        """
        return self._get_knn(self._root, point, k, return_dist_sq, [])

    def get_nearest(self, point, return_dist_sq=True):
        """Returns the nearest neighbor.
        Parameters
        ----------
        point : array-like
            The point.
        return_dist_sq : boolean
            Whether to return the squared Euclidean distance.
        Returns
        -------
        array-like
            The nearest neighbor. 
            If the tree is empty, returns `None`.
            If `return_dist_sq` is true, the return will be:
                (dist_sq, point)
            else:
                point
        """
        l = self._get_knn(self._root, point, 1, return_dist_sq, [])
        return l[0] if len(l) else None

下面给出测试代码 

import unittest
import random
import cProfile
from kd_tree import *

class KDTreeUnitTest(unittest.TestCase):

    def test_all(self):

        dim = 3

        def dist_sq_func(a, b):
            return sum((x - b[i]) ** 2 for i, x in enumerate(a))

        def get_knn_naive(points, point, k, return_dist_sq=True):
            neighbors = []
            for i, pp in enumerate(points):
                dist_sq = dist_sq_func(point, pp)
                neighbors.append((dist_sq, pp))
            neighbors = sorted(neighbors)[:k]
            return neighbors if return_dist_sq else [n[1] for n in neighbors]

        def get_nearest_naive(points, point, return_dist_sq=True):
            nearest = min(points, key=lambda p:dist_sq_func(p, point))
            if return_dist_sq:
                return (dist_sq_func(nearest, point), nearest) 
            return nearest

        def rand_point(dim):
            return [random.uniform(-1, 1) for d in range(dim)]

        points = [rand_point(dim) for x in range(10000)]
        additional_points = [rand_point(dim) for x in range(100)]
        query_points = [rand_point(dim) for x in range(100)]

        kd_tree_results = []
        naive_results = []
        
        global test_and_bench_kd_tree
        global test_and_bench_naive

        def test_and_bench_kd_tree():
            global kd_tree
            kd_tree = KDTree(points, dim)
            for point in additional_points:
                kd_tree.add_point(point)
            kd_tree_results.append(tuple(kd_tree.get_knn([0] * dim, 8)))
            for t in query_points:
                kd_tree_results.append(tuple(kd_tree.get_knn(t, 8)))
            for t in query_points:
                kd_tree_results.append(tuple(kd_tree.get_nearest(t)))

        def test_and_bench_naive():
            all_points = points + additional_points
            naive_results.append(tuple(get_knn_naive(all_points, [0] * dim, 8)))
            for t in query_points:
                naive_results.append(tuple(get_knn_naive(all_points, t, 8)))
            for t in query_points:
                naive_results.append(tuple(get_nearest_naive(all_points, t)))

        print("Running KDTree...")
        cProfile.run("test_and_bench_kd_tree()")
        
        print("Running naive version...")
        cProfile.run("test_and_bench_naive()")

        print("Query results same as naive version?: {}"
            .format(kd_tree_results == naive_results))
        
        self.assertEqual(kd_tree_results, naive_results, 
            "Query results mismatch")
        
        self.assertEqual(len(list(kd_tree)), len(points) + len(additional_points), 
            "Number of points from iterator mismatch")

if __name__ == '__main__':
    unittest.main()

参考文章:

GitHub - Vectorized/Python-KD-Tree: A simple and fast KD-tree for points in Python for kNN or nearest points. (damm short at just ~60 lines) No libraries needed.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/12467.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一键生成元宇宙 AI又杀疯了

人类十几年的进步水平&#xff0c;AI用几个月就能轻易实现。在展示了超强的文本对话能力和一键生图功能后&#xff0c;AI大模型不打算停下&#xff0c;开始挑战搭建3D空间这一更高难度的动作。 这次&#xff0c;Facebook母公司Meta想当一把主导者。几天前&#xff0c;它的首席…

信号生成和可视化——周期性/非周期性波形

信号生成和可视化 此示例说明如何使用 Signal Processing Toolbox™ 中提供的函数生成广泛使用的周期和非周期性波形、扫频正弦波和脉冲序列。尝试此示例Copy Command Copy Code 周期性波形 除了 MATLAB 中的 sin 和 cos 函数外&#xff0c;Signal Processing Toolbox™ 还…

redis主从复制详解

文章目录 主从复制概述主从复制的作用主要包括&#xff1a;数据冗余故障恢复负载均衡高可用基石 主从库之间采用的是读写分离的方式读操作写操作 主从复制原理全量复制确立主从关系全量复制的三个阶段第一阶段是主从库间建立连接、协商同步的过程&#xff0c;主要是为全量复制做…

MobileNetV3详细原理(含torch源码)

作者&#xff1a;爱笑的男孩。 个人简介&#xff1a;打工人。 持续分享&#xff1a;机器学习、深度学习、python相关内容、日常BUG解决方法及Windows&Linux实践小技巧。 如发现文章有误&#xff0c;麻烦请指出&#xff0c;我会及时去纠正。有其他需要可以私信我或者发我邮箱…

Linux系统上如何禁用 USB 存储

Linux系统上如何禁用 USB 存储 为了保护数据不被泄漏&#xff0c;我们使用软件和硬件防火墙来限制外部未经授权的访问&#xff0c;但是数据泄露也可能发生在内部。 为了消除这种可能性&#xff0c;机构会限制和监测访问互联网&#xff0c;同时禁用 USB 存储设备。 我是艾西&…

uni-app常用配置

保存自动格式化 工具》设置》编辑器设置》保存时自动格式化 JS语法检查 安装eslint-js插件eslint-js - DCloud 插件市场用于校验js和html中的js代码https://ext.dcloud.net.cn/plugin?id2037工具》设置》插件配置》eslint-js 启用实时校检 Vue语法检查 安装eslint-vue插件…

如何突破LinkedIn领英限制,导出非好友邮箱等社交方式

相信做外贸的朋友都有使用过Linkedin&#xff0c;如果还没有使用过的话&#xff0c;我只能说您错过一个很好的平台。只要是厉害的外贸人都特别擅长用Linkedin找客户。 那为什么说Linkedin是外贸业务员开发客户最有效的途径呢&#xff1f;主要基于以下几点&#xff1a; 第一&a…

强训之【井字棋和密码强度等级】

目录 1.井字棋1.1题目1.2思路讲解1.3代码展示 2.密码强度判断2.1题目2.2思路讲解2.3代码 3.选择题 1.井字棋 1.1题目 链接: link 描述 给定一个二维数组board&#xff0c;代表棋盘&#xff0c;其中元素为1的代表是当前玩家的棋子&#xff0c;0表示没有棋子&#xff0c;-1代表…

禅道OpenAI更新至1.2版本,超多实用功能惊喜上线!

广受欢迎的禅道OpenAI插件近日成功发布&#xff0c;截至目前已更新至1.2版本。 截至本版本发布&#xff0c;禅道OpenAI已经拥有了神奇海螺&#xff08;ChatGPT聊天&#xff09;、需求润色、任务润色、Bug润色及本次的需求一键生成用例功能&#xff0c;仍有更多实用的新功能正在…

计算机视觉__基本图像操作(显示、读取、保存)

计算机视觉__基本图像操作&#xff08;显示、读取、保存&#xff09; 本文目录&#xff1a; ✨ 一、前言 ✨ 二、图像显示&#xff08;使用OpenCV和Matplotlib显示图像&#xff09; &#xff08;1&#xff09;、使用OpenCV显示图像 &#xff08;2&#xff09;、使用Matplotl…

电磁兼容(EMC)的标准与测试内容

在国际范围上&#xff0c;电磁兼容标准的制定已经有了70多年的发展历程&#xff0c;最早为了保护无线电通信和广播&#xff0c;国际无线电干扰特别委员会&#xff08;CISPR&#xff09;对各种用电设备和系统提出了相关的电磁干扰发射限值和测量方法。到了20世纪60&#xff5e;7…

被裁了,39 岁阿里 P9,攒下 1.5 亿....

今天刷知乎&#xff0c;在问题 “40 岁因为财务自由决定不上班的人&#xff0c;个人资产总和到底有多少” 下看到一位阿里 P9 的匿名回答让我狠狠的酸了一把~ 这刚刚失业的四十岁高级码农自曝了自己的人生经历&#xff0c;作为一名“阿里 P9”的程序员&#xff0c;他讲述了自己…

聚观早报|阿里云正式推出通义千问;京东零售开启5年最大组织变革

今日要闻&#xff1a;国家网信办规范生成式人工智能服务&#xff1b;阿里云正式推出通义千问&#xff1b;京东零售开启5年来最大组织变革&#xff1b;飞书将推出智能AI助手「My AI」&#xff1b;乐高将继续扩大在华零售布局 国家网信办规范生成式人工智能服务 4 月 11 日&…

redis——使用

session缓存缓存更新方式删除缓存vs更新缓存缓存和数据库操作原子性缓存和数据库操作顺序结论 缓存问题缓存穿透缓存雪崩缓存击穿 全局唯一ID数据并发线程安全单体分布式redis分布式锁的问题 redis消息队列listpubsubstream 消息推送 session 问题&#xff1a;session存在tomca…

nginx简单使用与配置

nginx简单使用与配置 Nginx 是一个高性能的HTTP和反向代理web服务器、一个邮件代理服务器&#xff0c;一个通用的 TCP/UDP 代理服务器。支持FastCGI、SSL、Virtual Host、URL Rewrite、Gzip等功能。并且支持很多第三方的模块扩展。 前端可以通过nginx实现以下功能&#xff1a…

DAY 34 正则表达式

正则表达式 REGEXP&#xff1a; Regular Expressions&#xff0c;由一类特殊字符及文本字符所编写的模式&#xff0c; 其中有些字符&#xff08;元字符&#xff09;不表示字符字面意义&#xff0c;而表示控制或通配的功能&#xff0c; 类似于增强版的通配符功能&#xff0c;但…

Linux--tty

Linux 终端(TTY) TTY 是 Teletype 或 Teletypewriter 的缩写&#xff0c;原来是指电传打字机&#xff0c;后来这种设备逐渐键盘和显示器取代。不管是电传打字机还是键盘显示器&#xff0c;都是作为计算机的终端设备存在的&#xff0c;所以 TTY 也泛指计算机的终端(terminal)设…

【面试】你在项目中遇到过慢查询问题吗?你是怎么做SQL优化的?

文章目录 前言一、找出有问题的SQL1、系统层面2、SQL语句层面 二、查看SQL执行计划三、SQL优化案例慢查询优化步骤 SQL优化小结 前言 我在面试的时候很喜欢问候选人这样一个问题&#xff1a;“你在项目中遇到过慢查询问题吗&#xff1f;你是怎么做SQL优化的&#xff1f;” 很多…

基于DSP+FPGA的多轴运动控制平台(一)硬件设计

2 实验平台总体方案与硬件设计 2.1.1 实验平台的功能需求分析 针对便于多轴运动控制技术的研究&#xff0c;培养此方面技术的人才&#xff0c;实验平台应能 对多轴运动实现高速高精度的控制效果&#xff0c;同时保证系统开放性和兼容多种算法及 参数的运行。 实验过程契合…

TCP/IP协议及配置

文章目录 一、TCP/IP概述1. TCP/IP协议族2. 主机与主机之间通信的三个要素 二、什么是IP地址1. 用来标识一个网络节点的互联网地址&#xff08;如同电话的号码&#xff09;2. IPv4地址组成 三、IP地址分类1. 常用的IP地址2. 组播及科研专用 四、IP地址分类&#xff08;续&#…