k近邻法

k近邻法

k 近邻法（k-nearest neighbor，k-NN）是一种基本的分类与回归方法。

主要思想：假定给定一个训练数据集，其中实例标签已定，当输入新的实例时，可以根据其最近的 k 个训练实例的标签，预测新实例对应的标注信息。

• 分类问题：对新的实例，根据与之相邻的 k 个训练实例的类别，通过多数表决等方式进行预测。
• 回归问题：对新的实例，根据与之相邻的 k 个训练实例的标签，通过均值计算进行预测。

下面主要讨论分类问题

算法

输入：训练集：

$$T = \{(x_1,y_1),(x_2,y_2)\cdots,(x_N,y_N)\}$$

其中，$x_i \in \mathcal{X} \subseteq \mathbf{R}^n$，$y \in \mathcal{Y} = \{c_1,c_2,\cdots,c_K\}$，实例 $x$；

输出：实例 $x$ 所属类别 $y$

1. 根据给定的距离度量，计算 $x$ 与 $T$ 中点的距离；

2. 在 $T$ 中找到与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域记作 $N_k(x)$；

3. 在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$。

$$y = \mathop{\arg\max}_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_j), \quad i = 1,2,\cdots,N;\ j = 1,2,\cdots,K$$

k近邻法的三要素

距离

$L_p$ 距离：

特征空间 $\mathcal{X}$ 假设为 $\mathbf{R}^n$，$\forall x_i,x_j \in \mathcal{X}$，$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$，则有

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

• 欧氏距离（Euclidean distance）

$$L_2(x_i, x_j) = \left( \sum_{l=1}^{n} \left| x_i^{(l)} - x_j^{(l)} \right|^2 \right)^{\frac{1}{2}}$$

• 曼哈顿距离（Manhattan distance）

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

• 切比雪夫距离（Chebyshev distance）

$$L_\infty(x_i, x_j) = \max_{l} \left| x_i^{(l)} - x_j^{(l)} \right|$$

k值的选取

• 较小的 $k$ 值，学习的近似误差减小，但估计误差增大，敏感性增强，而且模型复杂，容易过拟合
• 较大的 $k$ 值，减少学习的估计误差，但近似误差增大，而且模型简单

注：$k$ 的取值可通过交叉验证来选择，一般低于训练集样本量的平方根。

分类决策规则

多数表决规则：由输入实例的 $k$ 个邻近的训练实例中的多数类决定输入实例的类。

• 分类函数

$$f: \mathbf{R}^n \to \{c_1,c_2,\cdots,c_K\}$$

• 0-1 损失函数

$$L(Y,f(X))=
\begin{cases}
1, & Y \neq f(X) \\
0, & Y = f(X)
\end{cases}$$

• 误分类概率

$$P(Y \neq f(X)) = 1 - P(Y = f(X))$$

给定实例 $x \in \mathcal{X}$，相应的 $k$ 邻域 $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)$$

最小化误分类率，等价于

$$\arg\max_{c_j}\sum_{x_i\in N_k(x)} I(y_i = c_j)$$