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

  1. k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法。这里只讨论分类问题的kNN。
  2. k近邻法的算法
    1. 输入
      训练集 $$ T = \lbrace(x_1, y_1), (x_2, y_2), \cdots , (x_N, y_N)\rbrace $$
      其中,$ x_i \in \mathcal{X} \subseteq \mathbf{R}^n $为实例的特征向量,$ y_i \in \mathcal{Y} = {c_1, c_2, \cdots ,c_K} $ 为实例的类别,$ i=1,2, \cdots , N $;实例特征向量 $ x $;
    2. 输出实例$ x $所属的类 $ y $。
    3. 过程
      1. 根据给定的距离度量,找出与$x$最邻近的$k$个点,这个邻域记作$N_k(x)$
      2. 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$:
        $$ \arg\max_{c_j}\sum_{x_i \in N_k(x)}I(y_i=c_j), i=1,2,\cdots,N;\ j=1,2,\cdots,K $$
        其中,$I$为指示函数,即当$y_i=c_i$时$I$为1,否则$I$为0
  3. $k=1$是一种特殊情况,称为最邻近算法。
  4. 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|x_i^{(l)}| - x_j^{(l)}|^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, y_i) = \max_l|x_i^{(l)}-x_j^{(l)}| $$
      5. 此外还有Minkowski距离
      6. 距离度量不同,最邻近点不同
    3. $k$值越小意味着模型越复杂,更容易过拟合。通常$k$取一个较小的值。通常采用交叉验证法确定$k$值。
    4. 分类决策规则:$k$近邻法的分类决策往往是多数表决。分类函数为
      $$ f: \mathbf{R}^n \rightarrow \lbrace c_1, c_2, \cdots , c_K \rbrace $$
      误分类的概率是
      $$ 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(k)}I(y_i = c_j) $最大,所以多数表决规则等价于经验风险最小化。
  5. 计算kNN的算法是kd树。kd树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。注意这里的$k$与$k$近邻的$k$并不是一个含义。它等于特征向量的维数。

标签: none

添加新评论