《统计学习方法》学习笔记3：k近邻法

k 近邻法（k-nearest neighbor, k-NN）是一种基本分类与回归方法。这里只讨论分类问题的 kNN。
k 近邻法的算法
1. 输入：
  
  训练集
  $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}$
  其中， $x_i \in \mathcal{X} \subseteq \mathbb{R}^n$ 为实例的特征向量， $y_i \in \mathcal{Y} = \{c_1, c_2, \ldots, c_K\}$ 为实例的类别， $i = 1, 2, \ldots, N$ ；实例特征向量 $x$ 。
2. 输出实例 $x$ 所属的类 $y$ 。
3. 过程：
  1. 根据给定的距离度量，找出与 $x$ 最邻近的 $k$ 个点，这个邻域记作 $N_k(x)$ 。
  2. 在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$ ：
    $y = \arg\max_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_j), \quad i = 1, 2, \ldots, N;\; j = 1, 2, \ldots, K$
    其中， $I$ 为指示函数，即当 $y_i = c_j$ 时 $I$ 为 1，否则 $I$ 为 0。
$k = 1$ 是一种特殊情况，称为最邻近算法。
k 近邻法的模型三要素是距离度量、k 值与分类决策规则。
1. 基本概念
  1. 单元（cell）：距离该点比其他点更近的所有点组成的一个区域。每个训练实例拥有一个单元。
  2. 类标记（class label）：每个单元的类别。最邻近法将实例 $x_i$ 的类 $y_i$ 作为其单元中所有点的类标记。
2. 距离度量
  1. $L_p$ 距离定义为：
    $L_p(x_i, x_j) = \left( \sum_{l=1}^{n} \left| x_i^{(l)} - x_j^{(l)} \right|^p \right)^{\frac{1}{p}}$
  2. 当 $L_p$ 距离中 $p$ 取 2 时，称为欧氏距离（Euclidean distance）。
  3. 当 $L_p$ 距离中 $p$ 取 1 时，称为曼哈顿距离（Manhattan distance）。
  4. 当 $L_p$ 距离中 $p$ 取 $\infty$ 时，它是各个坐标距离的最大值，即：
    $L_\infty(x_i, x_j) = \max_l \left| x_i^{(l)} - x_j^{(l)} \right|$
  5. 此外还有 Minkowski 距离。
  6. 距离度量不同，最邻近点不同。
3. $k$ 值越小意味着模型越复杂，更容易过拟合。通常 $k$ 取一个较小的值。通常采用交叉验证法确定 $k$ 值。
4. 分类决策规则：k 近邻法的分类决策往往是多数表决。分类函数为：
  $f: \mathbb{R}^n \to \{c_1, c_2, \ldots, c_K\}$
  误分类的概率是：
  $P(Y \neq f(X)) = 1 - P(Y = f(X))$
  对给定的实例 $x \in \mathcal{X}$ ，其最邻近的 $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)$ 最大，所以多数表决规则等价于经验风险最小化。
计算 kNN 的算法是 kd 树。kd 树是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。注意这里的 $k$ 与 k 近邻的 $k$ 并不是一个含义，它等于特征向量的维数。