统计学习方法(二):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)}\) 最小,因此其等驾驭经验风险最小化。