一句话解释：在大样本中，找距离目标点最近的k个点。

什么是K近邻算法

对两个实例点之间的距离进行度量

1. 其实就是使用了范数，不同范数对应的距离度量下的最近邻点不同
2. 可以简单理解为计算两个点之间的距离

K值是什么

1. 在训练集T中找到与目标点 x 最邻近的 k 个点

   1. k越小，模型复杂度越高，容易过拟合（因为一个点很有可能是噪声）

2. k越大，可以减少学习的估计误差，但是也会导致学习的近似误差增大，本来不相似的东西也会被认为属于比较邻近的集合

3. 一般来说，k值是一个比较小的数值

4. 采用交叉验证法来选择最优的k值

分类决策规则

1. 多数表决规则
   1. 由k个最邻近的点中的多数来决定该点所属的类
2. 衡量分的对不对？
   1. 误分类概念，要使误分类概率最小

怎么实现这个算法呢？

1. 老老实实计算每一个点与目标点之间的距离？
   那要是训练集非常大，岂不是非常耗时费力？
2. 所以要使用kd树方法——对k维空间中的点进行存储以便对其进行快速检索的树形数据结构。

kd树方法

关键两点，一个是构造，另一个是搜索

1. 树方法实质
   1. 管他什么树方法，说白了就是不断分割；
   2. 刚开始整个区域，包含全部点，分一下，各区域点就少了很多，分啊分，最后的小区域点就非常少了，这样搜索效率会提高很多；
   3. 实施起来可能和这个简单的说法略有不同，用到了坐标的中位数，形成的树中存储的是点的坐标。
2. 如何理解这个树形结构
   1. 要注意，这个树不是说每个实例点是一个树枝，而是数据集划分空间才是树枝；
   2. 也就是说刚才是整个数据集——这就是根结点，然后这个数据集分了两部分，就是两个子区域，分别是一个节点……分啊分，某个小区域里面没有实例点了，这个小区域就是树的末端了（叶结点）。
3. 搜索方法
   1. 先从叶结点开始检查，然后回退检查父结点和父结点的其他子结点；
   2. 我们假设一下，有个叶结点比较近，那这个叶结点肯定是目标结点的一个近邻了，然后看一下父结点，结果发现比它还近，然后再回退父结点和父结点的其他子结点，找啊找，直到检索到根结点，就找到了最近的点。要是父结点并不近，那么肯定，这个点就算是最近的了。