统计学习方法（二）：k 近邻法

\(k\) 近邻法

模型

\(k\) 近邻法是一种基本的分类和回归方法。对于分类问题，模型将输入对应于特征空间后输出对应的类别。\(k\) 近邻法假定给定一个训练数据集，其中的实例类别已定。分类时，对于新的实例，根据其 \(k\) 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，\(k\) 近邻法不具有显式的学习过程。\(k\) 值的选择、距离度量和分类决策规则是 \(k\) 近邻法的三个基本要素。

\(k=1\) 的特殊情况被称为最近邻算法。

距离度量

要选择 \(k\) 近邻就要首先确定度量距离的方法，通常特称空间是 \(n\) 维实数向量空间 \(\mathbb{R}^n\)。使用的距离是欧式距离或更一般的 \(L_p\) 距离，也可以是其他距离。

设特征空间是 \(\chi\) 是 \(n\) 维实数向量空间 \(\mathbb{R}^n\)，\(x_i,x_j\in \chi\)，\(x_i = (x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T\)， \(x_j = (x_j^{(1)},x_j^{(2)},\cdots,x_j^{(n)})^T\)，\(x_i,x_j\) 的 \(L_p\) 距离定义为 \[ L_p(x_i,x_j)=(\sum_{l=1}^n{|x_i^{(l)} - x_j^{(l)}|^p})^{\frac{1}{p}} \] 其中 \(p\geqslant 1\)。

当 \(p=2\) 时，称为欧式距离 (Euclidean distance)，即 \[ L_2(x_i,x_j)=(\sum_{l=1}^n{|x_i^{(l)} - x_j^{(l)}|^2})^{\frac{1}{2}} \] 当 \(p=1\)时，称为曼哈顿距离 (Manhattan distance)，即 \[ L_1(x_i,x_j)=\sum_{l=1}^n{|x_i^{(l)} - x_j^{(l)}|} \] 当 \(p=\infty\) 时，它是各个坐标距离中的最大值，即 \[ L_\infty(x_i,x_j)=\underset{l}{max}{|x_i^{(l)} - x_j^{(l)}|} \]

\(k\) 值的选择

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

如果 \(k\) 值较小，就相当于用较小的邻域中的训练实例进行预测，造成的结果就是近似误差减小，估计误差增大，即 \(k\) 值的减小意味着模型整体变复杂，容易发生过拟合。

如果 \(k\) 值较大，模型的估计误差减小，近似误差增大，使模型整体变简单。

近似误差 (approximation error) ：度量与最优误差之间的相近程度

估计误差 (estimate error) ：度量预测结果与最优结果的相近程度

个人直观理解为近似误差度量了预测值与实际值的差距，而估计误差则度量了当前参数与最优解的参数的距离。对与 \(k\) 值的选择，使用较小的 \(k\) 值可以有效避免大量无关数据带来的影响，但如果近邻实例恰巧是噪声，预测就会出错，这和过拟合对参数的变化极度敏感的特性是一致的，过拟合时，训练数据的预测效果很好，即近似误差小，但泛化能力极低，模型的参数与实际情况相差较远，即估计误差大。

如果 \(k=N\)，则模型直接预测训练数据中最多的类，无使用意义。

实际使用中，\(k\) 通常取一个较小的值。对于 \(k\) 的选择，可以使用交叉验证法。

分类决策规则

通常使用多数表决决定输出的结果，下面证明多数表决规则等价于经验风险最小化。

如果用0-1​损失函数作为分类的损失函数，对于分类函数 \[ f:\mathbb{R}^n = \{c_1, c_2, \cdots, c_K\} \] 误分类的概率为 \[ P(Y\neq f(X)) = 1 - p(Y = f(X)) \] 对于给定的实例 \(x\in \chi\)，其 \(k\) 个最近邻的训练实例点构成 \(N_k(x)\)。如果 \(N_k(x)\) 对应的是类别 \(c_j\)，则误分类率为 \[ \frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i \neq c_j)} = 1 - \frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i = c_j)} \] 由于多数表决的目标是使 \(\sum_{x_i\in N_k(x)}{I(y_i = c_j)}\) 最大，即 \(\sum_{x_i\in N_k(x)}{I(y_i \neq c_j)}\) 最小，因此其等驾驭经验风险最小化。