统计学习方法 k近邻法

k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法，下面只讨论分类问题中的k近邻法，k近邻法的输入为实例的特征向量，对应于特征空间的点;输出为实例的类别，可以取多类. k近邻法假设给定一个训练数据集，其中的实例类别已定.分类时，对新的实例,根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测.因此，k近邻法不具有显式的学习过程，k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素.

k近邻算法

k近邻算法简单、直观:给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类.

k近邻法没有显式的学习过程.

k近邻模型

模型

特征空间中，对每个训练实例点，距离该点比其他点更近的所有点组成一个区域，叫作单元(cell). 每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分.最近邻法将实例xi的类yi作为其单元中所有点的类标记(class label). 这样，每个单元的实例点的类别是确定的。

距离度量

欧式距离，曼哈顿距离等。

k值的选择

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差(approximation error)会减小，只有与输入实例较近的(相似的)训练实例才会对预测结果起作用.但缺点是“学习”的估计误差(estimation error)会增大，预测结果会对近邻的实例点非常敏感.如果邻近的实例点恰巧是噪声,预测就会出错.换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合.

如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测.其优点是可以减少学习的估计误差.但缺点是学习的近似误差会增大.这时与输入实例较远的(不相似的)训练实例也会对预测起作用，使预测发生错误. k值的增大就意味着整体的模型变得简单.

在应用中，k值一般取一个比较小的数值.通常采用交叉验证法来选取最优的k值.

分类决策规则

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

k近邻法的实现：kd树

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

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

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

构造kd树

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

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

搜索kd树

利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。以最近邻为例，给定一个目标点，搜索其最近邻.首先找到包含目标点的叶结点;然后从该叶结点出发,依次回退到父结点;不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止.这样搜索就被限制在空间的局部区域上，效率大为提高.

如果实例点是随机分布的, kd树搜索的平均计算复杂度是O(logN),这里N是训练实例数. kd树更适用于训练实例数远大于空间维数时的k近邻搜索.当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描.