k邻近法

一种基本的分类回归方法，其并没有显示的学习过程。对于一个测试实例，通过训练集中距离最近的k个实例来进行表决，得到该实例的分类结果。

模型

k邻近法的核心就是通过对于特征空间的划分，实现决策。其中重点要考虑的是距离度量、k值、表决方式

距离度量可以取p范数（常用2范数）

k的取值

k如果过小，那么k值就会更加明显的受到最临近点的影响，倘若最邻近点就是噪声，那么分类结果就会出现较大的偏差。k过小会是模型变得复杂，过拟合的概率增加

k如果过大，考虑极限情况 $k = N$ ，此时无论测试实例为什么，结果都是固定的。此时的模型过于简单

k一般还是去一个较小的值，通过交叉验证法来确定最佳的k值

决策方式

通常使用多数最优的方式，考虑 $0-1$ 损失函数，那么多数最优就是经验风险最小化的情况

kd树

我们往往通过构造一个二叉树来实现对于k维特征空间的划分，称之为kd树，构造kd树的方法非常简单。

实际上我们就是在用垂直于坐标轴的超平面不断地去划分特征空间，步骤如下

1. 取 $x^{(1)}$ 为坐标轴，取N个实例中 $x^{(1)}$ 为中位数的为根节点，其中小于该中位数的为左子树，其余为右子树
2. 对于深度为 $j$ 的节点，取 $x^{(l)}$ 为坐标轴（ $l = j (\mod k) + 1$ ），重复的进行划分直到子区域中没有实例点

搜索

1. 首先找到测试点所属的叶子节点：从根结点出发，按照对应坐标轴进行分类就得到此时的最邻近点

2. 回溯：递归回退

   1. 若该节点到测试点的距离更近，则更新最邻近点的值
   2. 检查另一子树内是否有更邻近的点，即检查以测试点为球心，最近距离为半径的超球体是否与该区域相交，若不相交，向上回退

3. 直到回退到根节点，此时最邻近的点就是结果

对于最邻近的k个点，那么在回溯的过程中就要维护一个大顶堆，通过比较大顶堆堆顶的值来进行更新。

总结

kNN适合小样本的训练，其可解释性较弱。适合一些简单的问题，应用范围不广。