机器学习k近邻算法kd树实现优化查询

简介: 机器学习k近邻算法kd树实现优化查询

1 kd树简介

1.1 什么是kd树

问题导入:

实现k近邻算法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索。

这在特征空间的维数大及训练数据容量大时尤其必要。

**k近邻法最简单的实现是线性扫描(穷举搜索),即要计算输入实例与每一个训练实例的距离。计算并存储好以后,再查找K近邻。**当训练集很大时,计算非常耗时。

为了提高kNN搜索的效率,可以考虑使用特殊的结构存储训练数据,以减小计算距离的次数。

根据KNN每次需要预测一个点时,我们都需要计算训练数据集里每个点到这个点的距离,然后选出距离最近的k个点进行投票。当数据集很大时,这个计算成本非常高,针对N个样本,D个特征的数据集,其算法复杂度为O(DN2)

kd树:为了避免每次都重新计算一遍距离,算法会把距离信息保存在一棵树里,这样在计算之前从树里查询距离信息,尽量避免重新计算。其基本原理是,如果A和B距离很远,B和C距离很近,那么A和C的距离也很远。有了这个信息,就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到O(DNlog(N))。感兴趣的读者可参阅论文:Bentley,J.L.,Communications of the ACM(1975)。

1989年,另外一种称为Ball Tree的算法,在kd Tree的基础上对性能进一步进行了优化。感兴趣的读者可以搜索Five balltree construction algorithms来了解详细的算法信息。

1.2 原理

黄色的点作为根节点,上面的点归左子树,下面的点归右子树,接下来再不断地划分,分割的那条线叫做分割超平面(splitting hyperplane),在一维中是一个点,二维中是线,三维的是面。

黄色节点就是Root节点,下一层是红色,再下一层是绿色,再下一层是蓝色。

1.树的建立;

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

kd树(K-dimension tree)是**一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。**kd树是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量。

类比“二分查找”:给出一组数据:[9 1 4 7 2 5 0 3 8],要查找8。如果挨个查找(线性扫描),那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了:[0 1 2 3 4 5 6 7 8 9],按前一种方式我们进行了很多没有必要的查找,现在如果我们以5为分界点,那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。

因此,根本就没有必要进入第一个簇,可以直接进入第二个簇进行查找。把二分查找中的数据点换成k维数据点,这样的划分就变成了用超平面对k维空间的划分。空间划分就是对数据点进行分类,“挨得近”的数据点就在一个空间里面。

2 构造方法

(1)构造根结点,使根结点对应于K维空间中包含所有实例点的超矩形区域;

(2)**通过递归的方法,不断地对k维空间进行切分,生成子结点。**在超矩形区域上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域(子结点);这时,实例被分到两个子区域。

(3)上述过程直到子区域内没有实例时终止(终止时的结点为叶结点)。在此过程中,将实例保存在相应的结点上。

(4)通常,循环的选择坐标轴对空间切分,选择训练实例点在坐标轴上的中位数为切分点,这样得到的kd树是平衡的(平衡二叉树:它是一棵空树,或其左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是平衡二叉树)。

KD树中每个节点是一个向量,和二叉树按照数的大小划分不同的是,KD树每层需要选定向量中的某一维,然后根据这一维按左小右大的方式划分数据。在构建KD树时,关键需要解决2个问题:

(1)选择向量的哪一维进行划分;

(2)如何划分数据;

第一个问题简单的解决方法可以是随机选择某一维或按顺序选择,但是更好的方法应该是在数据比较分散的那一维进行划分(分散的程度可以根据方差来衡量)

第二个问题中,好的划分方法可以使构建的树比较平衡,可以每次选择中位数来进行划分。

3 案例分析

3.1 树的建立

给定一个二维空间数据集:T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},构造一个平衡kd树。

(1)思路引导:

根结点对应包含数据集T的矩形,选择x(1)轴,6个数据点的x(1)坐标中位数是6,这里选最接近的(7,2)点,以平面x(1)=7将空间分为左、右两个子矩形(子结点);接着左矩形以x(2)=4分为两个子矩形(左矩形中{(2,3),(5,4),(4,7)}点的x(2)坐标中位数正好为4),右矩形以x(2)=6分为两个子矩形,如此递归,最后得到如下图所示的特征空间划分和kd树。

3.2 最近领域的搜索

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

样本集{(2,3),(5,4), (9,6), (4,7), (8,1), (7,2)}

3.2.1 查找点(2.1,3.1)

在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2),(5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;


然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如上图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。

于是再回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索。


至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。


3.2.2 查找点(2,4.5)

在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7)【优先选择在本域搜索】,然后search_path中的结点为<(7,2),(5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;

然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2),(2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。


回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)


回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。


至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。

4 总结

  • kd树的构建过程
  • 1.构造根节点
  • 2.通过递归的方法,不断地对k维空间进行切分,生成子节点
  • 3.重复第二步骤,直到子区域中没有实例时终止
  • 需要关注细节:a.选择向量的哪一维进行划分;b.如何划分数据
  • kd树的搜索过程【知道】
  • 1**.二叉树搜索比较待查询节点和分裂节点的分裂维的值**,(小于等于就进入左子树分支,大于就进入右子树分支直到叶子结点)
  • 2.顺着“搜索路径”找到最近邻的近似点
  • 3.回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索
  • 4.重复这个过程直到搜索路径为空
目录
相关文章
|
17天前
|
机器学习/深度学习 并行计算 PyTorch
优化技巧与策略:提高 PyTorch 模型训练效率
【8月更文第29天】在深度学习领域中,PyTorch 是一个非常流行的框架,被广泛应用于各种机器学习任务中。然而,随着模型复杂度的增加以及数据集规模的增长,如何有效地训练这些模型成为了一个重要的问题。本文将介绍一系列优化技巧和策略,帮助提高 PyTorch 模型训练的效率。
28 0
|
9天前
|
机器学习/深度学习 数据采集 算法
数据挖掘和机器学习算法
数据挖掘和机器学习算法
|
12天前
|
机器学习/深度学习 数据采集 存储
一文读懂蒙特卡洛算法:从概率模拟到机器学习模型优化的全方位解析
蒙特卡洛方法起源于1945年科学家斯坦尼斯劳·乌拉姆对纸牌游戏中概率问题的思考,与约翰·冯·诺依曼共同奠定了该方法的理论基础。该方法通过模拟大量随机场景来近似复杂问题的解,因命名灵感源自蒙特卡洛赌场。如今,蒙特卡洛方法广泛应用于机器学习领域,尤其在超参数调优、贝叶斯滤波等方面表现出色。通过随机采样超参数空间,蒙特卡洛方法能够高效地找到优质组合,适用于处理高维度、非线性问题。本文通过实例展示了蒙特卡洛方法在估算圆周率π和优化机器学习模型中的应用,并对比了其与网格搜索方法的性能。
88 1
|
14天前
|
机器学习/深度学习 存储 前端开发
实战揭秘:如何借助TensorFlow.js的强大力量,轻松将高效能的机器学习模型无缝集成到Web浏览器中,从而打造智能化的前端应用并优化用户体验
【8月更文挑战第31天】将机器学习模型集成到Web应用中,可让用户在浏览器内体验智能化功能。TensorFlow.js作为在客户端浏览器中运行的库,提供了强大支持。本文通过问答形式详细介绍如何使用TensorFlow.js将机器学习模型带入Web浏览器,并通过具体示例代码展示最佳实践。首先,需在HTML文件中引入TensorFlow.js库;接着,可通过加载预训练模型如MobileNet实现图像分类;然后,编写代码处理图像识别并显示结果;此外,还介绍了如何训练自定义模型及优化模型性能的方法,包括模型量化、剪枝和压缩等。
25 1
|
15天前
|
机器学习/深度学习 安全 算法
利用机器学习优化网络安全防御策略
【8月更文挑战第30天】在信息技术迅猛发展的今天,网络安全问题日益突显,传统的安全防御手段逐渐显得力不从心。本文提出一种基于机器学习的网络安全防御策略优化方法。首先,通过分析现有网络攻击模式和特征,构建适用于网络安全的机器学习模型;然后,利用该模型对网络流量进行实时监控和异常检测,从而有效识别潜在的安全威胁;最后,根据检测结果自动调整防御策略,以提升整体网络的安全性能。本研究的创新点在于将机器学习技术与网络安全防御相结合,实现了智能化、自动化的安全防御体系。
|
14天前
|
缓存 开发者 测试技术
跨平台应用开发必备秘籍:运用 Uno Platform 打造高性能与优雅设计兼备的多平台应用,全面解析从代码共享到最佳实践的每一个细节
【8月更文挑战第31天】Uno Platform 是一种强大的工具,允许开发者使用 C# 和 XAML 构建跨平台应用。本文探讨了 Uno Platform 中实现跨平台应用的最佳实践,包括代码共享、平台特定功能、性能优化及测试等方面。通过共享代码、采用 MVVM 模式、使用条件编译指令以及优化性能,开发者可以高效构建高质量应用。Uno Platform 支持多种测试方法,确保应用在各平台上的稳定性和可靠性。这使得 Uno Platform 成为个人项目和企业应用的理想选择。
25 0
|
14天前
|
API UED 开发者
如何在Uno Platform中轻松实现流畅动画效果——从基础到优化,全方位打造用户友好的动态交互体验!
【8月更文挑战第31天】在开发跨平台应用时,确保用户界面流畅且具吸引力至关重要。Uno Platform 作为多端统一的开发框架,不仅支持跨系统应用开发,还能通过优化实现流畅动画,增强用户体验。本文探讨了Uno Platform中实现流畅动画的多个方面,包括动画基础、性能优化、实践技巧及问题排查,帮助开发者掌握具体优化策略,提升应用质量与用户满意度。通过合理利用故事板、减少布局复杂性、使用硬件加速等技术,结合异步方法与预设缓存技巧,开发者能够创建美观且流畅的动画效果。
38 0
|
15天前
|
机器学习/深度学习 存储 算法
利用机器学习优化数据中心的能源效率
【8月更文挑战第30天】 在信息技术不断进步的今天,数据中心作为支撑云计算、大数据分析和人工智能等技术的核心基础设施,其能源效率已成为衡量运营成本和环境可持续性的关键指标。本文旨在探讨如何通过机器学习技术对数据中心进行能源效率优化。首先,文中介绍了数据中心能耗的主要组成部分及其影响因素。其次,详细阐述了机器学习模型在预测和管理数据中心能源消耗方面的应用,并通过案例分析展示了机器学习算法在实际环境中的效果。最后,文章讨论了机器学习优化策略实施的潜在挑战与未来发展方向。
|
16天前
|
机器学习/深度学习 存储 算法
图解最常用的 10 个机器学习算法!
图解最常用的 10 个机器学习算法!
|
17天前
|
机器学习/深度学习 算法 数据挖掘
8个常见的机器学习算法的计算复杂度总结
8个常见的机器学习算法的计算复杂度总结
8个常见的机器学习算法的计算复杂度总结