k近邻法于1968年由Cover和Hart提出，是一种基本分类与回归方法。k近邻法的输入为实例的特征向量，对应特征空间的点；输出为实例的类别，可以取多类。k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻法不具有的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型"。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

1. k近邻算法

输入：训练数据集

输出：实例x所属的类y。

k近邻法的特殊情况是k=1的情形，称为最近邻算法。

2. k近邻模型

k近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

2.1. 模型

k近邻法中，当训练集、距离度量、k值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。

2.2. 距离度量

这里p<=1。当p=2时，称为欧氏距离，即

当p=1时，称为曼哈顿距离，即

不同的距离度量所确定的最近邻点是不同的。

2.3. k值的选择

k值的选择会对k近邻法的结果产生重大影响。

k值较小时，相当于用较小的领域中的训练实例进行预测，”学习“的近似误差会减小，但估计误差会增大，预测结果对近邻的实例点非常敏感，容易发生过拟合。

k值较大时则相反。

通常采用交叉验证法来选取最优的k值。

2.4. 分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数为

那么误分类的概率是

3. k近邻法的实现：kd树

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。

k近邻法最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。

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

3.1. 构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应一个k维超矩形区域。

构造kd树的方法如下：构造根结点，使根结点对应于k维空间中包含所有实例点的矩形区域；通过下面的，递归方法，不断地对k维空间进行切分，生成子结点。

在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过待定的切分点并垂直于待定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止。在此过程中，将实例保存在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。但平衡的kd树搜索时的效率未必是最优的。

平衡kd树构造算法

输出：kd树。

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

3.2. 搜索kd树

给定一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。

包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。然后返回当前结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法转到更上一级的父结点，继续上述过程。如果结点的另一子结点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。

kd树最近邻搜索算法

输入：已构造的kd树，目标点x；

输出：x的最近邻。

（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。

（2）以此叶结点为当前最近点。

（3）递归地向上回退，在每个结点进行以下操作：

（a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为当前最近点。

（b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与当前最近点间的距离为半径的超球体相交。

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个结点。接着，递归地进行最近邻搜索。

（4）当回退到根结点时，搜索结束。最后的当前最近点即为x的最近邻点。

参考文献

【1】统计学习方法（第2版），李航著，清华大学出版社