K近邻
约定：
- 红色：对名词进行解释的重点
- 黄色：各部分总结中的重点
- 绿色：算法基本假设与解释
摘要：
名词解释：kd树、R树
- kd树：根据特征将特征平面不断二分的方法，用于加速KNN的过程
- R树：一种类似B树和B+树的划分高维平面的方法，可以用于加速KNN的过程
原理实现： KNN的手写实现
一、一句话概括
基于距离的计算找到最像（距离最近）的k个，在这k个中通过投票进行决策得到结果
二、K近邻计算过程
按照定义拆分以下3个过程
2.1 K值选择
- 较小的K值会过于依赖数据，泛化能力可能会比较差。比如k选择1，正好有一个数据和训练数据的特征完全一致，那么就应该选择这个数据的标签吗，很有可能这个数据是有偏差的（数据误差），k=3或者5通过投票可以解决这个问题
- 一般选择较小的k值，3或5这种，通过交叉验证来优化（变换不同的训练数据）
2.2 距离计算
- 根据范数有曼哈顿距离（1范数），欧几里得距离（2范数）
- 欧几里得距离常用 注：其他关于距离的介绍在 番外-正则化、距离与范数 中有详细的讨论
2.3 决策过程
- 基于距离找到k个最像（距离最小）的样本之后，需要根据这些样本的标签估计待遇测数据的标签
- 通常来说就是少数服从多数，也有一种改进的算法：按照距离的权重投票（距离越近的点权重越高）
三、空间优化方法
因为KNN非常粗暴，上来直接开算，没有训练过程，导致时间复杂度很高，所以就有了一种基于树形结构提前划分特征空阿的思路
3.1 KD树
- KD树似乎是一个比较容易想到的划分特征空间的方法，其思想就是按照每一个特征进行二分（从这个角度看有点像CART树）
- 其算法就是，第一层按照第一个维度进行二分，第二层按照第二个维度进行二分，第m层按照第m个维度进行二分。共$2^m$个叶子节点
- 树构建完成后，将某个新的样本按照树的结构找到自己的位置，然后寻找邻居
- 寻找邻居的过程可能需要尽心回溯（兄弟节点不是，有可能叔节点满足要求，一般不会回溯很多次）
3.2 R树
- R树中的R指 Rectangle，其思想和B树以及B+树很像，可以理解成高维空间中的B树
- 其本质也是一颗平衡树，通过将子节点的外接矩形作为父节点的方法，可以提前判断这个样本是否在区域中（不在父节点的区域中，肯定也不在子节点的区域中）
- 因为是高维空间的平衡书，所以在构建的过程中非常困难，目前没有一个能兼容效率的构建方法
四、总结
- K近邻是基于距离的算法（通常需要归一化，将各个特征对距离的影响变得一样），找到最像的K个后，投票得到结果
- 没有什么训练过程，也几乎没有什么假设（只有一个特征相似的样本，标签也相似这样的看起来是废话的假设）拿到新数据直接开始算，所以模型比较准确，但是时间复杂度极高，存在将特征空间划分的基于树结构的方法，但是构建的结果要么十分庞大，要么很难构建