大话系列 | k近邻（中）—有一棵树叫KD树
↑关注+星标，听说他有点东西
全文共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树构建
① 开始：
构造根节点，根节点对应于包含T的k维空间的超矩形区域，并将超矩形区域切分为两个子区域
对深度为j的节点，选择对应的x维切分轴，以该节点的区域中所有实例的x维坐标的中位数为切分点，将该节点对应的超矩形区域切分为两个子区域
直到两个子区域没有实例存在时停止，从而形成kd树的区域划分
总结来说，在kd树的创建过程中，每次取一个维度的中位数为划分点， 将其作为树的节点，将数据集分成左右两部分递归的进行划分。
需要注意的是，下一层划分的维度和上一层不同，一般直接选择k的下一个维度。
3.3. KD树查找
目前我们已经创建了一颗kd树，接下来的任务是通过kd树查找最近的k个邻居。
在kd树的查找过程中，首先找到包含目标点的叶节点；然后从该叶节点出发，依次回退到叶节点；不断查找于目标点最近邻的节点，当确定不可能存在更近的节点时终止。
上面的搜索过程是被直接限制在空间的局部区域上， 比起最开始的knn搜索效率大大提高。
仔细看一下kd树的搜索过程：
①在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近邻上即可：
写在后面的话
填上了上节最后留下的坑，如果没有这个坑想必你会非常容易理解k近邻算法
这是我们学到的第三个机器学习分类算法，大家可以类比一下前两个，分析分析
按照惯例，贴上k近邻分类算法的思维导图
大家可以在后台回复knn获取，原图会被系统二次压缩，需要原图的同学可以加小一微信领取
我是小一，第一步的一，我们下节见