《统计学习方法》 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)的类别,就可以判定新的豆子的类别。如果最近三颗全部为绿豆,自然新豆子为绿豆;如果最近三颗豆子有两颗为绿豆,一颗为红豆,则根据多数表决定理,新豆子为绿豆。
补充介绍:对于 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)}|)$,简单来说就是各维度坐标数值差的最大值
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)}$
构造根节点和根节点下的左右子树
以 $x^{(1)}$ 为坐标轴,以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点,切分为两个子区域
所有实例的 $x^{(1)}$ 坐标序列为 ${1,2,3,4,5}$,中位数为 3。因此 $(3,4)$ 为根节点,两个子区域分别为 ${(1,2),(2,3)}$ 和 ${(4,5),(5,6)}$
对于深度为 $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$。
直到两个子区域没有实例存在时停止。
4.2 kd 树的几何意义
同时,我们用上述这个二维的例子来讲述 kd 树的几何意义。每一次划分就是通过切分点做与坐标轴 $x^{(l)}$ 垂直的超平面。
- 第一次切分,切分点为 $(3,4)$,坐标轴为 $x^{(1)}$
- 第二次切分,切分点为 $(2,3)$ 和 $(5,6)$,坐标轴为 $x^{(2)}$
通过对比 4.1 中的 kd 树结构和 4.2 中的区域划分图,不难发现,所有的非叶节点都落在超平面上,所有叶子节点都落在超矩形区间内。
4.3 kd 搜索树
下面介绍如何通过 kd 树进行 k 近邻搜索。
找出包含目标点 $x$ 的叶节点
从根节点出发,若目标点 $x$ 当前维的坐标小于切分点的坐标,则移动到其左子节点;反之,移动到右子节点。直到子节点维叶子节点。(同二叉搜索树)
以此叶节点为“当前最近点”。创建一个大小为 k 的 List,用来存储 k 个距离目标点最近的点集。
递归地向上回退
检查当前遍历的子节点的兄弟节点对应的区域是否有更近的点。(检查兄弟节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交)
从上图中可见超球体(粉色区域)和其兄弟节点对应的区域(蓝色区域)没有交集。因此在当前循环中,无需计算距离并更新点集。
如有交集,计算距离、更新点集。
5. 总结
k 近邻算法
- 判定一个带标记集合中一个新实例的类别的算法
- 一般采用线性扫描的方式计算实例点之间的距离
kd 树是 k 近邻算法的一种实现方式
- 采用了特定的存储结构(二叉树)
- 相比 k 近邻法减少了计算距离的次数
- 但当空间维数接近训练样本数时,优势不明显。