统计学习方法-k近邻法

简述

k近邻算法主要思想就是根据给定的距离度量方法，在训练集中找到与目标点最近邻的k个点，在这k个点中根据决策规则（通常是多数表决）决定目标点的类别。

距离度量

$L_p$距离（$L_p$ distance）

假设$x_i, x_j \in \textbf{R}^n$，$x_i = (x_i^{(1)},x_i^{(2)},\dots, x_i^{(n)})^T$，$x_j = (x_j^{(1)},x_j^{(2)},\dots, x_j^{(n)})^T$

则$L_p$距离的定义为

$$L_p(x_i, x_j) = (\sum_{l=1}^n|x_i^{(l)} - x_j^{(l)}|^p)^{\frac{1}{p}}, \space p \ge 1 \tag 1$$

当$p=1$时，称为曼哈顿距离(Manhattan distance)

$$L_1(x_i, x_j) = \sum_{l=1}^n|x_i^{(l)} - x_j^{(l)}| \tag 2$$

当$p=2$时，称为欧式距离(Euclidean distance)

$$L_2(x_i, x_j) = (\sum_{l=1}^n(x_i^{(l)} - x_j^{(l)})^2)^{\frac{1}{2}} \tag 3$$

当$p=\infty$时，是各个坐标距离的最大值

$$L_{\infty}(x_i, x_j) = \mathop{\text{max}}\limits_{l} |x_i^{(l)} - x_j^{(l)}| \tag 4$$

k值的选择

如果选择较小的k值，目标点会对周围的近邻点非常敏感，容易受到噪声的影响，发生过拟合。如果选择较大的k值，则离目标点较远的非相似点会对目标点产生影响，发生欠拟合。因此，通常对特定数据集采用多次交叉验证的方式来确定k值。

分类规则

最常用的就是多数表决，对于一个含有j类标签的数据集，目标点的标签确定是通过附近k邻域内最多的标签来决定。因此，对于$k$个训练实例点构成的集合$N_k(x)$，如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率为

$$\frac{1}{k} \sum_{x_i \in N_k(x)} I (y_i \ne c_j) = 1 - \frac{1}{k} \sum_{x_i \in N_k(x)} I (y_i = c_j) \tag 5$$

使$\sum_{x_i \in N_k(x)} I (y_i = c_j)$最大即误分类率最小