查看原文
其他

大话系列 | k近邻(中)—有一棵树叫KD树

小一 小一的学习笔记 2023-01-01

关注+星标,听说他有点东西

全文共2139字,阅读全文需11分钟




写在前面的话

大家好,我是小一

k近邻分类本是分类算法中第二简单的,第一是决策树,但是写下来之后总感觉似乎哪里写的复杂了。

所以稍微复杂的内容就单独放在了这节,就当是k近邻算法的一个拓展好了。

上一节末尾我们提到了在样本量大的时候,k近邻进行预测分类会需要很长的时间。 所以这节是对上节最后提出问题的一个解释吧。

贴上上节链接,大家不妨再回忆一下当时是怎么思考这个问题的:大话系列 | k近邻(上)—理论



1. KD树

kd树:k-dimensional树,中文意思为k-维树。

在上节的k近邻分类过程中,每出现一个新的待分类点,我们都需要将它与全量的数据进行计算,选出其中距离最近的k个邻居,所以这就导致计算非常耗时。

为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数,例如kd树方法。

需要注意的是:kd树是存储k维空间数据的树结构,与k近邻中的k不是一回事


3.1. KD树原理

在看kd树的构建之前,需要先了解一个概念:平衡二叉树

好熟悉,数据结构里面的内容!

平衡二叉指的是左子树上的所有节点的值都小于(包括等于)根节点的值,而右子树上的所有节点的值都比根节点的值大,且左子树与右子树的高度差最大为1。

看一张图,你应该瞬间就懂了

平衡二叉树

例如节点49左边的值都不大于49,右边的值都大于49,左边子树的深度为4,右边子树的深度也为4,所以上面的数就是一颗平衡二叉树。


因为平衡二叉树的性质,我们在搜索树的时候,根据叶子节点可以很快速的查找到想要的结果。

你应该不否认上面那棵树可以让你很快速的找到你要的数据吧

这个是一维数据查找的二叉树,那如果我们的数据是二维的呢?

比如说,现在我们有一批学生的语文和数学成绩,如何建立一棵树可以方便快速的找到我们要的学生数据?

根据一维平衡二叉树的思想,我们可以这样做:

  • 先根据语文成绩,将所有人的成绩分为S1和S2,其中S1的语文成绩>c1,S2的语文成绩<=c1
  • 针对S1部分,根据数学成绩继续分为S3和S4,其中S3的数学成绩>m1,S4的数学成绩<=m1
  • 针对S2部分,根据数学成绩继续分为S5和S6,其中S5的数学成绩>m2,S6的数学成绩<=m2
  • 再根据语文针对,将S3和S4、S5和S6划分为更小的集合
  • 继续使用数学成绩进行划分
  • ...

最终,我们划分后形成的KD树是这样的:

最终的KD树以及对应的二叉树就是这样的:

ok,原理我们已经知道了,一起来看下如何创建KD树


3.2. KD树构建
输入:k维空间数据集T(多维想象不出来就用墙角代替三维)
输出:kd树
步骤:

① 开始:

构造根节点,根节点对应于包含T的k维空间的超矩形区域,并将超矩形区域切分为两个子区域

② 重复:

对深度为j的节点,选择对应的x维切分轴,以该节点的区域中所有实例的x维坐标的中位数为切分点,将该节点对应的超矩形区域切分为两个子区域

③停止:

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


总结来说,在kd树的创建过程中,每次取一个维度的中位数为划分点, 将其作为树的节点,将数据集分成左右两部分递归的进行划分。

需要注意的是,下一层划分的维度和上一层不同,一般直接选择k的下一个维度。


3.3. KD树查找

目前我们已经创建了一颗kd树,接下来的任务是通过kd树查找最近的k个邻居。

在kd树的查找过程中,首先找到包含目标点的叶节点;然后从该叶节点出发,依次回退到叶节点;不断查找于目标点最近邻的节点,当确定不可能存在更近的节点时终止。

上面的搜索过程是被直接限制在空间的局部区域上, 比起最开始的knn搜索效率大大提高。


仔细看一下kd树的搜索过程:

输入: 已构造的kd树,目标点x
输出: x的最近邻
步骤:

①在kd树中找出包含目标点x的叶节点:从根节点出发,递归的向下访问kd树

②以此叶节点为当前最近点

③递归的向上回退,并对每个节点进行以下操作:

  • 如果该节点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”
  • 检查当前子节点的父节点的另一子结点对应的区域是否有更近的点
  • 如果有,则更新当前最近点,并继续向上回退

④当回退到根节点时,搜索结束。最后的当前最近点即为x的最近邻点


想必又到了你开始犯迷糊(而我开始举例子)的时间了

有一颗kd树,根节点时A,子节点为BCDEF等,有一个目标实例点S,求S的最近邻

举个栗子

  • 首先在kd树中找到包含点S的叶节点D,以点D作为最近邻

  • 其次返回点D的父节点B,在B的另一子结点F的区域内搜索最近邻,节点F的区域与圆不相交,不可能有最近邻点

  • 继续返回上一级父节点A,在节点A的另一子结点C的区域内搜索最近邻,发现存在实例点E比D更近,更新最近邻点

  • A为根节点,递归结束,点E为点S的最近邻点



2. KNN做回归

还有最后一个问题:通过k近邻算法进行回归预测

这个应该不用多说了吧,k近邻的回归和决策树的回归都挺类似,直接看决策树怎么处理回归问题,类比到k近邻上即可:

基于CART算法的决策树回归



写在后面的话

填上了上节最后留下的坑,如果没有这个坑想必你会非常容易理解k近邻算法

这是我们学到的第三个机器学习分类算法,大家可以类比一下前两个,分析分析

按照惯例,贴上k近邻分类算法的思维导图

k近邻算法思维导图


大家可以在后台回复knn获取,原图会被系统二次压缩,需要原图的同学可以加小一微信领取

我是小一,第一步的一,我们下节见






往期推荐

大话系列 | 决策树(上篇)—理论

大话系列 | 决策树(中篇)—理论

大话系列 | 决策树(下篇)—实战

大话系列 | 贝叶斯(上篇)—理论

大话系列 | 贝叶斯(下篇)—实战



您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存