当前位置： 首页 > ai >正文

【k近邻】Kd树的构造与最近邻搜索算法

ai 2025/8/12 12:21:08

【k近邻】 K-Nearest Neighbors算法原理及流程

【k近邻】 K-Nearest Neighbors算法距离度量选择与数据维度归一化

【k近邻】 K-Nearest Neighbors算法k值的选择

【k近邻】 Kd树的构造与最近邻搜索算法

【k近邻】 Kd树构造与最近邻搜索示例

Kd树是一种对K（与k近邻的k意义不同）维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

Kd树是一种二叉树，表示对K维空间的一个划分(partition)。

构造Kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分，构成一 系列的K维超矩形区域。Kd树的每个结点对应于一个k维超矩形区域。

算法:构造kd树

输入：$k$维空间数据集$T=\{x_1,x_2,\cdots,x_N\}$,其中$x_i=(x_i^{(1)},x_i^{(2)}\cdots,x_i^{(k)})^T$$i=1,2,\cdots,N\colon$

输出：$kd$树。

(1)开始：构造根结点，根结点对应于包含T 的$k$维空间的超矩形区域。

 选择$x^{(1)}$为坐标轴，以$T$中所有实例的$x^{(1)}$ 终标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。

由的根结点生成深度为1的左,右子结点：左子结点对应坐标$x^{(1)}$小于切分点的子区域，右子结点对应于坐标$x^{(1)}$大于切分点的子区域。

将落在切分超平面上的实例点保存在根结点。

(2)重复：对深度为$j$的结点，选择$x^{(l)}$为切分的坐标轴，$l=j({\mathrm{mod}}k)+1$,以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现。

由该结点生成深度为$j+1$的左、右子结点：左子结点对应坐标$x^{(l)}$小于切分点的子区域，右子结点对应坐标$x^{(l)}$大于切分点的子区域。

 将落在切分超平面上的实例点保存在该结点。

(3)直到两个子区域没有实例存在时停止,从而形成$kd$树的区域划分。

例:沿x轴开始的kd树构造

算法:使用kd树的最近邻搜索

输入：已构造的$kd$ 树，目标点$x;$

输出：$x$的最近邻。

 (1)在$kd$树中找出包含目标点$x$的叶结点：从根结点出发，递归地向下访问$kd$树。若目标点$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。

(2)以此叶结点为“当前最近点”。

(3)递归地向上回退，在每个结点进行以下操作：

        (a)如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。

        (b)当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。

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

        如果不相交，向上回退。

(4)当回退到根结点时，搜索结束。最后的“当前最近点”即为$x$的最近邻点。

http://www.xdnf.cn/news/17521.html

相关文章：

  • 用户虚拟地址空间布局
  • JVM管理数据的方式
  • 剧本杀小程序系统开发：推动行业数字化转型新动力
  • Linux中DNS系统搭建与配置指南（配实验步骤与注释）
  • 在 .NET Core 5.0 中启用 Gzip 压缩 Response
  • Tricentis Tosca：现代软件测试的自动化利器
  • 企业级 IT 运维服务平台数据备份方案：基于 rsync 的自动化实现
  • AI生成代码时代的商业模式重构：从“软件即产品”到“价值即服务”
  • 云原生环境Prometheus企业级监控
  • Notepad++ 插件开发实战：从理念到落地的探索
  • 嵌入式第二十五天(基于Linux操作系统的编程-文件操作)
  • 大模型提示词工程实践：大语言模型文本转换实践
  • 【读代码】微软开源Agentic-RAG深度解析
  • execjs执行js报错， subprocess.py编码问题
  • Ignite端口管理组件GridPortProcessor全解析
  • Linux系统编程——基础IO
  • 《录井管理与工程》书籍第一章要点及相应思考
  • 虚幻GAS底层原理解剖十 （网络）
  • 深度剖析 Linux 信号：从基础概念到高级应用，全面解析其在进程管理与系统交互中的核心作用与底层运行机制
  • Orange的运维学习日记--39.Nginx详解与服务部署
  • 【liunx】web高可用---nginx
  • GSON 框架下百度天气 JSON 数据转 JavaBean 的实战攻略
  • ZooKeeper和Reids做分布式锁的区别？
  • Notepad--：国产跨平台文本编辑器，Notepad++ 的理想替代方案
  • 车载软件架构 --- 车辆量产后怎么刷写Flash Bootloader
  • 【数据结构入门】二叉树（1）
  • Redis7 GEO功能介绍与电商场景案例解析
  • Android模块化架构深度解析：从设计到实践
  • HTML5中华美食网站源码
  • (Arxiv-2025)Phantom-Data：迈向通用的主体一致性视频生成数据集