《统计学习方法》 k 近邻算法部分的读书笔记

1. k 近邻算法简介

给定数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中，$x_i \in R^n$ 为实例的特征向量，$y_i \in {c_1, c_2,…, c_K}$ 为实例的类别。

k 近邻算法 认为“物以类聚”——“红豆附近是红豆”，因此当需要判定某一实例 $(x_i,y_i)$ 的类别时，可以通过在训练集 $T$ 中找到与实例 $(x_i,y_i)$ 距离最近的 $k$ 个点（将涵盖这 $k$ 个点的邻域记作 $N_k(x)$）。通过邻域 $N_k(x)$ 的类别特性来决定实例 $(x_i,y_i)$ 的类别。

简单来说，如果有两类实例群：绿豆和红豆，现在要判定某一个豆子的类别。利用 k 近邻的思想，只需要知道离这颗豆子最近的三颗豆子（取 k=3）的类别，就可以判定新的豆子的类别。如果最近三颗全部为绿豆，自然新豆子为绿豆；如果最近三颗豆子有两颗为绿豆，一颗为红豆，则根据多数表决定理，新豆子为绿豆。
image-20210429104033799

补充介绍：对于 k 近邻算法中 $k$ 值的选择会对算法结果产生重大影响

  • 如果选择了较小的 $k$

    学习的估计误差会增大。换句话说，预测结果对临近实例点非常敏感，如果临近的实例恰好是噪声，预测便容易出错。

  • 如果选择了较大的 $k$

    学习的近似误差会增大。换句话说，此时与输入实例较远的训练实例也会起到预测的作用，带来误差。


2. 距离度量

在第一章我们介绍 k 近邻算法中需要选取距离实例 “距离最近” 的 k 个实例，那如何来度量距离？

令 $x_i = (x_i^{(1)}, x_i^{(2)}, .. ,x_i^{(n)})$，$x_j = (x_j^{(1)}, x_j^{(2)}, .. ,x_j^{(n)})$

  • 欧氏距离（二范数）

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

  • 曼哈顿距离（一范数），也称街区距离

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

不难发现欧式距离和曼哈顿距离在格式上存在一些共性，其实他们都属于 P 范数下的一个特例

  • P 范数

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

另外，还有切比雪夫距离，也称棋盘距离

  • 切比雪夫距离

    $D_{chess} = max(|x_i^{(m)}-x_i^{(n)}|, |x_j^{(m)}-x_j^{(n)}|)$，简单来说就是各维度坐标数值差的最大值

image-20210429105847785

3. 分类决策规则（多项表决规则）

用通俗的语言来说，多项表决规则就是少数服从多数。如果在邻域内，属于某一类的实例数量更多，则输入实例就属于哪一类。

定义（多项表决规则）：如果分类的损失函数为 0-1 损失函数，分类函数为 $f:R^n \rightarrow {c_1,c_2, …,c_K}$
那么误分类的概率是 $P(Y \neq f(X))=1-P(Y=f(X))$
对于给定实例 $x \in \chi$，则其最邻近的 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)$
要使误分类率（经验风险）最小化，则 $\sum_{x_i \in N_k(x)}I(y_i=c_j)$ 应最大

上述定义中，$I(y_i \neq c_j)$ 为指示函数，$I(x)= \begin{cases} 1 &\text{x为真} \\0 &\text{x为假} \end{cases}$

$\sum_{x_i \in N_k(x)}I(y_i=c_j)$ 最大（经验风险最小），也就对应了多数表决。


4. kd 树（k 近邻方法的实现）

k 近邻方法中，采用线性扫描（逐个计算）的方式计算实例之间的距离。当特征空间的维数大或者训练数据容量大时，运算量极大。

因此，为了提高搜索效率，提出了 kd 树。**kd 树在结构上是二叉树，因此在搜索时的时间复杂度为 O(log n)**。

4.1 构造 kd 树

给定二维数据集 $T={x_1, x_2,…,x_N}$，其中 $x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T$

因为比较抽象，所以通过一个简单的例子来描述：给定二维数据集 $T={(1, 2), (2, 3), (3,4), (4,5), (5,6)}$

  1. 构造根节点和根节点下的左右子树

    以 $x^{(1)}$ 为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，切分为两个子区域

    所有实例的 $x^{(1)}$ 坐标序列为 ${1,2,3,4,5}$，中位数为 3。因此 $(3,4)$ 为根节点，两个子区域分别为 ${(1,2),(2,3)}$ 和 ${(4,5),(5,6)}$

    image-20210429143350270

  2. 对于深度为 $j$ 的节点，选择 $x^{(l)}$ 为切分坐标轴（$l=j(mod \ k) + 1$）继续划分

    对于区域 ${(1,2),(2,3)}$，$l=1(mod \ 2)+1=2$，因此以 $x^{(2)}$ 为坐标轴，列出序列 ${2,3}$，选取中位数 3（父节点${(2,3)}$），分为两个子区域 ${(1,2)}$ 和 $\emptyset$。

    对于区域 ${(4,5),(5,6)}$，$l=1(mod \ 2)+1=2$，因此以 $x^{(2)}$ 为坐标轴，列出序列 ${5,6}$，选取中位数 6（父节点${(5,6)}$），分为两个子区域 ${(4,5)}$ 和 $\emptyset$。

    image-20210429143407215

  3. 直到两个子区域没有实例存在时停止。

4.2 kd 树的几何意义

同时，我们用上述这个二维的例子来讲述 kd 树的几何意义。每一次划分就是通过切分点做与坐标轴 $x^{(l)}$ 垂直的超平面。

  1. 第一次切分，切分点为 $(3,4)$，坐标轴为 $x^{(1)}$
  2. 第二次切分，切分点为 $(2,3)$ 和 $(5,6)$，坐标轴为 $x^{(2)}$
    image-20210429144600175 image-20210429144615071image-20210429144630913

通过对比 4.1 中的 kd 树结构和 4.2 中的区域划分图，不难发现，所有的非叶节点都落在超平面上，所有叶子节点都落在超矩形区间内。

4.3 kd 搜索树

下面介绍如何通过 kd 树进行 k 近邻搜索。

  1. 找出包含目标点 $x$ 的叶节点

    从根节点出发，若目标点 $x$ 当前维的坐标小于切分点的坐标，则移动到其左子节点；反之，移动到右子节点。直到子节点维叶子节点。（同二叉搜索树）

  2. 以此叶节点为“当前最近点”。创建一个大小为 k 的 List，用来存储 k 个距离目标点最近的点集。

  3. 递归地向上回退

    • 检查当前遍历的子节点的兄弟节点对应的区域是否有更近的点。（检查兄弟节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交）

      image-20210429151237178

      从上图中可见超球体（粉色区域）和其兄弟节点对应的区域（蓝色区域）没有交集。因此在当前循环中，无需计算距离并更新点集。

    • 如有交集，计算距离、更新点集。


5. 总结

  • k 近邻算法

    • 判定一个带标记集合中一个新实例的类别的算法
    • 一般采用线性扫描的方式计算实例点之间的距离

  • kd 树是 k 近邻算法的一种实现方式

    • 采用了特定的存储结构（二叉树）
    • 相比 k 近邻法减少了计算距离的次数
    • 但当空间维数接近训练样本数时，优势不明显。