统计学习方法第三章 k 近邻法

$k$ 近邻法（$k$-nearest neighbor，$k$-NN）是一种基本分类与回归方法。$k$ 近邻法的输入为实例的特征向量，输出为实例的类别，可以取多类。$k$ 近邻法假设给定一个训练集数据，其中的实例类别已定。分类时，对新的实例，根据其 $k$ 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，$k$ 近邻法不具有显式的学习过程。

$k$ 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的模型。

$k$ 值得选择、距离度量以及分类决策规则是 $k$ 近邻法的三个基本要素。

3.1 $k$ 近邻算法

算法 3.1 （$k$ 近邻法）
输入：训练数据集

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

其中
$$x_i\in{\cal X}\subseteq\mathbb{R}^n$$
为实例的特征空间，
$$y_i\in{\cal Y}=\{c_1,c_2,\cdots,c_K\}$$
为实例的类别；实例特征向量 $x$
输出：实例 $x$ 所属的类 $y$
(1) 根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域记作 $N_k(x)$
(2) 在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$
$$y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}\mathbb{I}(y_i=c_j),i=1,2,\cdots,N; j=1,2,\cdots,K$$
式中，$\mathbb{I}$ 为指示函数

$k$ 近邻法的特殊情况是 $k=1$ 的情形，称为最近邻算法。对于输入的实例点（特征向量）$x$，最邻近法将数据集中与 $x$ 最邻近点的类作为 $x$ 的类。

3.2 $k$ 近邻模型

$k$ 近邻法使用的模型实际上对应于特征空间的划分。模型由三个基本要素——距离度量，$k$ 值得选取和分类决策规则决定。

3.2.1 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反应。$k$ 近邻模型的特征空间一般是 $n$ 维实数向量空间 $\mathbb{R}^n$。使用的距离是欧氏距离，也可以使用其他距离，例如更一般的 $L_p$ 距离或 Minkowski 距离。

设特征空间 ${\cal X}$ 是 $n$ 维实数向量空间 $\mathbb{R}^n$，$x_i,x_j\in{\cal X}$，$x_i=\left(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)}\right)^\text{T}$，$x_j=\left(x_j^{(1)},x_j^{(2)},\cdots,x_j^{(n)}\right)^\text{T}$，$x_i,x_j$ 的 $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}$$

3.2.2 $k$ 值的选择

$k$ 值得选择会对 $k$ 近邻法的结果产生重大影响。

如果选择较小的 $k$ 值，就相当于用较小的邻域中的训练实例进行预测。“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声点，预测就会出错。换句话说，$k$ 值得减小就意味着整体模型变的复杂，容易发生过拟合。

如果 $k$ 值选择过大，就相当于用较大邻域中的训练实例进行预测。其优点是可以减小学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。$k$ 值的增大意味着整体的模型变得简单。

如果 $k=N$，那么无论输入的实例是什么，都将简单的预测它属于在训练实例中最多的类，这时，模型过于简单，是不可取的。

在应用中，$k$ 值一般取一个比较小的数值，通常采用交叉验证法来选取最优的 $k$ 值。

3.2.3 分类决策规则

$k$ 近邻法中的分类决策规则往往是多数表决，即由输入实例的 $k$ 个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则（majority voting rule）有如下解释：如果分类的损失函数是 0-1 损失函数，分类函数为

$$f:\mathbb{R}^n\longrightarrow\{c_1,c_2,\cdots,c_K\}$$

那么误分类的概率是

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

对于给定的实例 $x\in{\cal X}$，其最邻近的 $k$ 个训练实例点构成集合 $N_k(x)$。如果涵盖 $N_k(x)$ 的区域类别是 $c_j$，那么误分类率是

$$\frac{1}{k}\sum_{x_i\in N_k(x)}\mathbb{I}(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_k(x)}\mathbb{I}(y_i= c_j)$$

要使误分类率最小即经验风险最小，就要使 $\sum_{x_i\in N_k(x)}\mathbb{I}(y_i= c_j)$ 最大，所以多数表决规则等价于经验风险最小化。

3.3 $k$ 近邻法的实现：$kd$ 树

为了对训练数据进行快速 $k$ 近邻搜索，我可以采取 $kd$ 树方法（此 $k$ 是计算机科学中的叫法）。

$kd$ 树是每个节点都为 $k$ 维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。选择超平面的方法如下：每个节点都与k维中垂直于超平面的那一维有关。因此，如果选择按照x轴划分，所有 $x$ 值小于指定值的节点都会出现在左子树，所有 $x$ 值大于指定值的节点都会出现在右子树。这样，超平面可以用该x值来确定，其法线为 $x$ 轴的单位向量。

3.3.1 构造 $kd$ 树

有很多种方法可以选择轴垂直分割面（axis-aligned splitting planes），所以有很多种创建 $kd$ 树的方法。最典型的方法如下：

随着树的深度轮流选择轴当作分割面。（例如：在三维空间中根节点是 $x$ 轴垂直分割面，其子节点皆为 $y$ 轴垂直分割面，其孙节点皆为 $z$ 轴垂直分割面，其曾孙节点则皆为 $x$ 轴垂直分割面，依此类推）
点由垂直分割面之轴座标的中位数区分并放入子树

这个方法产生一个平衡的 $kd$ 树。每个叶节点的高度都十分接近。然而，平衡的树不一定对每个应用都是最佳的。

3.3.2 搜索 $kd$ 树

最邻近搜索用来找出在树中与输入点最接近的点。

$kd$ 树最邻近搜索的过程如下：

从根节点开始，递归的往下移。往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点)
一旦移动到叶节点，将该节点当作"目前最佳点"

解开递归，并对每个经过的节点运行下列步骤：

如果目前所在点比目前最佳点更靠近输入点，则将其变为目前最佳点
检查另一边子树有没有更近的点，如果有则从该节点往下找
当根节点搜索完毕后完成最邻近搜索

如果实例点是随机分布的，$kd$ 树搜索的平均计算复杂度是 $O(\log N)$，这里 $N$ 是训练实例数。$kd$ 树更适用于训练实例数远大于空间维度时的 $k$ 近邻搜索。当空间维度接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

统计学习方法第三章 k 近邻法

3.1 \(k\) 近邻算法

3.2 \(k\) 近邻模型

3.2.1 距离度量

3.2.2 \(k\) 值的选择

3.2.3 分类决策规则

3.3 \(k\) 近邻法的实现：\(kd\) 树

3.3.1 构造 \(kd\) 树

3.3.2 搜索 \(kd\) 树

发布日期

最后更新

分类

标签