《统计学习方法》算法学习笔记（二）之 K近邻法

K 近邻法

总述

k-近邻法（k-nearest neighbor, k-NN）是一种以分类与回归为基础的方法，在本节中我们仅讨论分类问题中的k-近邻法。其输入是实例的特征向量，在特征空间中对应特定的位置；输出则是实例的类别，在多类别场景下可灵活选择。该方法假设给定一个训练数据集，并且其中各类别已知确定。在分类新样本时，依据其与训练集中距离最近的k个邻居实例类别信息及决策规则（如多数投票等方法），进行预测判断。由此可见，在k-近邻法中并不存在显式的训练过程阶段；相反地，则是在利用训练数据集对特征空间进行划分并建立模型结构的基础上完成分类任务。选择合适的k值、采用何种距离度量以及确定何种分类决策规则是该算法实现过程中最为关键的三个基本要素。

1.1 k 近邻算法

基于一个训练集，在测试阶段对一个新的输入实例进行分类时，在测试集中确定与该测试样本最近邻的k个具体数据点。这些k个具体数据点中的大多数属于同一类别，则将这一具体特征向量归类到类别 y中（通过投票决策）。

基于给定的距离测度，在训练集T内寻找与样本x最接近的k个样本点；从这些k个样本点构成的邻域N_k(x)上应用多数投票机制来确定样本x所属的类别y。

其中，I为指示函数，即当y_i=c_j时I为1，否则I为0。

k近邻法的一个特例是当k=1时的情形，在这种情况下被称为最近邻算法。对于输入实例x（即特征向量），在应用最近邻法时会将与x最接近的类别作为x所属的类别。

1.2 k 近邻模型

1.2.1 模型

在特征空间中，在针对每一个特定的数据样本x_i的情况下，在这个特定数据样本周围并使其与其他数据样本的距离相对最小的一个区域内所包含的所有数据样本共同构成的一个区域被称为"单元"（cell）。每一个具体的数据样本都有自己的独特区域作为其对应的"细胞"（cell），而所有的数据样本对应的"细胞"（cell）共同构成了整个特征空间的一种划分方式。在最近邻分类方法中，默认情况下会将属于同一个"细胞"（cell）的所有样本归为同一类别。

1.2.2 距离度量

在特征空间中，两个实例点之间的距离度量反映了它们相似程度的大小。设特征空间为x，它是一个n维实数向量空间R^n。对于属于该空间的任意两点x_i, x_j∈x（其中i,j=1,2,...,N)），它们的形式分别为x_i=(x_i^1, x_i^2, ..., x_i^n)^T, x_j=(x_j^1, x_j^2, ..., x_j^n)^T,则定义了x_i与x_j之间多种距离计算方式：

1. L_p距离：

2. 欧式距离（Euclidean distance）：

3. 曼哈顿距离（Manhattan distance）：

4. 当p=∞，它是各个坐标距离的最大值，即

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

1.2.3 k 值的选择

（1）类似于仅考虑邻近训练实例的小规模区域进行预测，“学习”的近似误差会降低；
（2）缺点在于“学习”的估计误差会增大；预测结果对邻近实例点过于敏感；如果这些邻近点恰好包含噪声数据，“学习”效果就会受到显著影响；
（3）当k值减小时，“模型的整体复杂度显著提升”，从而可能导致过拟合现象出现。

2. 选择较大的k值
   （1）利用较大的邻域范围内的训练样本进行预测，并能有效降低估计误差的影响；
   （2）然而，在这种情况下近似区域扩大可能导致较大的近似误差，并且与输入实例距离较远且不相似的训练样本仍会对分类结果产生影响；
   （3）随着k值增加，模型的整体复杂性显著降低；
   （4）当k=N时，在所有测试样本上都采用多数投票法来进行分类判断。

在应用环境中（如工程优化、机器学习等），k 值通常取一个较小的值，并通过交叉验证法来选择最佳k值。

1.2.4 分类决策规则

多数类投票：即通过输入实例x的k个近邻的训练实例中的大多数类别来决定输入实例x的类。解释：当损失函数采用0-1损失时，分类规则定义为f: R^n \rightarrow \{c_1, c_2, \dots, c_k\}。误分类概率则计算为：

P(Y≠f(x)) = 1 - P(Y=f(x))

对于给定的一个实例x ∈ X, 其最近邻中的k个训练样本点构成了集合N^x_k. 如果涵盖N^x_k区域的是类别c_j$, 那么其误分类率即为：

要使误分类率最小，即经验风险最小，就要值

最大，所以多数表决规则等价于经验风险最小化。

1.3 k 近邻算法的实现：kd 树

在实现k近邻算法的过程中

1.3.1 构造 kd 树

kd树是一种对k维空间中的实例点进行组织以便提高搜索效率的树形结构。kd树作为一种二叉树，在划分k维空间时采用垂直于坐标轴的方式形成超平面，并将空间划分为一系列k维超矩形区域。每个节点对应一个特定范围内的k维超矩形区域，并通过不断选择合适的坐标轴及其对应的中位数作为切分点来构建 kd 树结构。在构建平衡 kd 树时通常会按照一定顺序依次选取坐标轴并选择训练实例点在选定坐标轴上的中位数值作为分割点从而实现较高的均衡性；然而需要注意的是即使构建出平衡 kd 树其搜索效率也未必达到理论上的最优值

开始：建立根节点（Node Root），其对应于包含数据集T的 k 维空间中的一个超矩形区域。
以特征变量x^1作为坐标轴，并基于T中所有实例在该特征变量上的中位数值确定一个切分点（split point）。通过一个与x^1轴垂直的超平面（hyperplane）将该区域分割为两个子区域。
生成深度为1的左子节点（Left Node）用于表示所有实例在特征变量x^1上的取值小于该切分点的情况；右子节点（Right Node）则用于表示大于该情况。

考虑深度为j的那个节点，并选择其上的一个坐标轴作为分割依据，在计算出该特征维度下的数据中位数值后，在这一特征维度上建立一个与选定坐标轴垂直的空间超平面进行分割操作。随后根据这一切割位置生成左右两个新节点：左侧新节点适用于其所在空间满足x^{l值小于切割位置的所有样本；右侧新节点则适用于x}l值大于切割位置的所有样本情况；同时位于切割超平面上的数据样本则被保留在当前节点中而不进入任何子树结构

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

1.3.2 搜索kd树

给定一个目标数据集X，在k d树中寻找其最邻近的数据实例。具体来说，在k d树中找到包含该目标数据集的所有叶子节点之后，在这些叶子节点的基础上逐步向上回溯至根节点，在此过程中持续比较当前节点是否为最接近的目标实例。一旦确定不可能存在比当前记录更为接近的目标实例时就停止搜索过程。这种通过限定局部区域来完成搜索的方法大大提高了计算效率。

为了找到包含目标点x的叶子节点，在k d树中从根节点出发进行深度优先搜索。对于每个节点而言，在当前维度下比较目标点x与切分坐标的位置关系：若$x_i < split_i，则进入左子树；否则进入右子树；这一过程持续直到到达叶子节点为止。
将该叶子节点设为当前最近邻候选。
沿着路径向上回退检查，在每个父节点执行以下操作：
（a）如果父节点保存的数据实例比当前候选更接近目标，则更新候选；
（b）判断是否存在另一个分支可能存在更近数据实例的情况：具体而言，检查另一子树对应的区域是否与以目标为中心、半径等于当前最近距离的超球体相交；如果存在，则进入该子树继续搜索；否则返回上一层父节点。

4. 当退回到根结点，搜索结束。最后的“当前最近点”即为x的最近邻点。

假设实例点呈随机分布，则基于 kd 树实现的搜索算法具有平均时间复杂度为 O(\log N) ，其中 N 代表训练样本的数量 。该方法特别适合于处理那些训练样本数量远超空间维度数量的情况下的 k 近邻搜索问题 。当空间维度的数量接近于训练样本数量时 ，则该方法的搜索效率显著降低 ，并几乎相当于进行了全范围的一次扫描