2.3 两个简单的预测方法：最小二乘和最近邻

本节介绍两个简单而有效的预测模型：最小二乘法（least squares） 拟合的线性模型，和 k-近邻（k-nearest-neighbor） 预测算法。线性模型对真实的数据关系做了很大简化，其结果通常比较稳定但不够准确。k-最近邻方法没有对真实数据的关系做很强的假设，其结果通常准确但不够稳定。

2.3.1 线性模型和最小二乘法

在过去的 30 年，线性模型一直是统计学中的基础支柱，到现在也是最重要的预测方法。已知一个输入变量向量 $X^T=(X_1,X_2,\dots,X_p)$，预测输出变量 $Y$ 的线性模型如下：

$$\hat{Y} = \hat{\beta}_0 + \sum_{j=1}^p X_j \hat{\beta}_j \tag{2.1}$$

式中 $\hat{\beta}_0$ 为线性模型的截距项，机器学习领域称之为“偏差（bias）”项。为了等式好看，通常在输入变量中加入一个常数变量 1，之后便可以将 $\hat{\beta}_0$ 纳入到参数向量 $\hat{\beta}$ 中，于是线性模型可以写为两个向量的内积（innter product）。

$$\hat{Y} = X^T \hat{\beta} \tag{2.2}$$

上式中 $X^T$ 表示向量或矩阵的转置（$X$ 为列向量）。上式是对单个输出变量的模型，$\hat{Y}$ 为一个数值；也可以推广到 $\hat{Y}$ 为 $K$ 维向量，此时 $\beta$ 成为 $p\times K$ 的参数矩阵。对于单个数值输出变量，符合上式的点 $(X,\hat{Y})$ 可以被视为 $(p+1)$ 维空间上的超平面（hyperplane）。¹若 $X$ 包含了常数项，则这个超平面包含 $(p+1)$ 维空间的原点，并且是一个子空间。若 $X$ 不包含常数项，则为一个仿射（affine）集合²，其与 $Y$ 轴交于 $(\mathbb{0},\hat{\beta}_0)$。

若将等式看成一个 $p$ 维输入变量的方程，即 $f(X)=X^T\beta$。这是一个对输入参数线性的方程，其梯度 $f’(X)=\beta$ 向量在输入变量的空间中指向 $Y$ 值增加最快的方向。

那么如何从训练数据集中拟合线性模型？方法有很多，其中目前最流行的方法为最小二乘法（least squares），即寻找使得残差平方和（residual sum of squares, RSS）最小的参数 $\beta$：

$$\operatorname{RSS}(\beta) = \sum_{i=1}^N (y_i - x_i^T \beta)^2 \tag{2.3}$$

$\operatorname{RSS}(\beta)$ 是对与其输入参数的二次方程，因此一定存在最小值，但最小值有可能不唯一。从矩阵的表达式可以很方便地推导出这个最优问题的解。上式可以写成：

$$\operatorname{RSS}(\beta) = (\mathbf{y} - \mathbf{X}\beta)^T (\mathbf{y} - \mathbf{X}\beta) \tag{2.4}$$

这里的 $\mathbf{X}$ 为 $N\times p$ 的矩阵，$\mathbf{y}$ 为训练数据集 $N$ 维的输出变量向量。上式对 $\beta$ 做微分后得到 正则方程（normal equations）：

$$\mathbf{X}^T(\mathbf{y} - \mathbf{X}\beta) = 0 \tag{2.5}$$

当 $X^TX$ 为满秩矩阵（non-singular）时，存在唯一解：

$$\hat{\beta} = (\mathbf{X}^T \mathbf{X})^T \mathbf{X}^T\mathbf{y} \tag{2.6}$$

训练样本中第 i 个输入变量样本 $x_i$ 对应的输出变量拟合值为 $\hat{y}_i=\hat{y}(x_i)=x_i^T\hat{\beta}$。给定一个新的输入变量观测样本 $x_0$，对应的输出变量预测值为 $\hat{y}(x_0)= x_0^T\hat{\beta}$。$p$ 维的参数估计 $\hat{\beta}$ 决定了输入变量与对应的拟合输出变量组成的空间。从直观上讲这种方法并不需要一个非常大的数据集。³

**图 2.1**：二维空间上的分类问题。输出变量为二分类变量，编码 0 代表“蓝色”，1 代表“橙色”，用线性回归拟合。实线为决策边界，$x^T \hat{\beta}= 0.5$。模型判定输入变量空间上橙色阴影区域中的点为“橙色”，蓝色阴影区域中的点为“蓝色”。

下面是一个用线性模型解决分类问题的例子。图 2.1 展示了一对输入变量 $X_1$ 和 $X_2$ 的训练数据集的散点图。所用的是模拟数据，其生成方法并不重要因此不做解释。输出变量 $G$ 为分类变量，取值为“蓝色”或“橙色”，在图中分别以相应的颜色标记。样本中两种颜色的点各有 100 个。根据 $G$ 将输出变量 $Y$ 定义为 0 和 1，分别对应“蓝色”和“橙色”，然后用线性回归模型拟合训练数据。然后根据下面的规则，将拟合的数值变量 $\hat{Y}$ 转换成分类变量 $\hat{G}$：

$$\hat{G} = \begin{cases} \text{橙色} & \text{if } \hat{Y} > 0.5\\ \text{蓝色} & \text{if } \hat{Y} \leq 0.5 \end{cases}\tag{2.7}$$

如图 2.1 所示，模型将 $\mathbb{R}^2$ 空间上的集合 ${x:x^T\hat{\beta}>0.5}$ 分类为“橙色”，模型的预测分类被线性的 决策边界（decision boundary） 分隔开。显而易见在决策边界的两侧均有被误分类的样本点。线性模型对边界的形态假设过于严格（必须为一条直线），不然有些分类错误是可以避免的。需要指出的是这些是训练数据集上的拟合错误，我们并没有明确样本的生成机制。考虑以下两种可能：

场景一：训练数据集的输入变量由二维的高斯（正态）分布产生，其相互之间不相关，且有不同的均值。

场景二：训练数据集的输入变量均为 10 个小方差高斯分布的混合，其中每个分布的均值本身又服从高斯分布。

高斯分布的混合可以从随机数生成模型的角度来理解。首先生成一个离散的随机数，来选择使用哪一个高斯分布，然后再根据选定的高斯分布生成随机数。⁴当每类样本中只有一个高斯分布时（场景一），在第四章我们会证明线性决策边界是最好的方法，而且线性边界的估计也近乎达到最优。数据的生成机制导致了存在两个类别重叠的区域，是无法避免的，这也同样会影响到模型对新数据集的预测。

相反地，当数据由对一些相对聚簇（即小方差）的高斯分布的混合产生时（场景二），线性决策边界不是最优的。最优的决策边界是非线性且不相连，这也导致很难得到这个边界。

接下来我们考虑另一种分类和回归的解决方法，从某种角度来说它与线性模型截然不同，且更适合“场景二”描述的生成模型。

2.3.2 最近邻方法

最近邻方法利用训练集中在输入变量空间上距离 $x$ 最近的样本点集合 $\mathcal{T}$ 来生成预测 $\hat{Y}$。具体来说，k-最近邻方法（k-nearest neighbor, KNN）的输出变量拟合 $\hat{Y}$ 定义为：

$$\hat{Y}(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i \tag{2.8}$$

其中 $N_k(x)$ 为 $x$ 的邻域，即在训练集中距离 $x$ 最近的 $k$ 的样本点。谈及远近，就涉及到距离的定义，在这里我们先默认采用欧式距离。综上，k-最近邻方法寻找训练集中与 $x$ 在输入变量空间中距离最近的 $k$ 的个点，然后用它们的输出变量平局值作为预测结果。

**图 2.2**：与图 2.1 同样的分类样本数据，输出变量为二分类“蓝色”和“橙色”，分别编码为 0 和 1，使用等式 2.8 所示的 15-近邻方法获得拟合值，每个点的 15 个样本中最近邻点的投票决定了预测分类。

我们用每个样本的 15 个近邻（$k=15$）的输出变量（0/1 编码）的平均值来做拟合，应用在图 2.1 同样的训练集上，结果展示在图 2.2 中。因此 $\hat{Y}$ 实际上是邻域中“橙色”（编码为 1）的样本比例，而“当 $\hat{Y}>0.5$ 时 $\hat{G}$ 为‘橙色’”的判定方法，实际可以理解为在邻域上的“少数服从多数”的投票。输入变量空间被分为蓝色和橙色阴影的区域，分辨代表了模型判定为“蓝色”和“橙色”的点的集合。线性决策边界可以估计出直线的表达式，而最近邻只能靠对输入变量空间上密集的网格上做预测来获得决策边界。可见区分蓝色和橙色区域的决策边界是十分不规则的，而且会照顾到同一类的点聚集的局部区域。

**图 2.3**：与图 2.1 同样的分类样本数据，输出变量为二分类“蓝色”和“橙色”，分别编码为 0 和 1，使用 1-邻域方法得到输入空间上的点的预测分类。

图 2.3 展示了单邻域分类模型的结果，即 $\hat{Y}$ 完全与训练样本中距离 $x$ 最近的 $x_l$ 相对应的 $y_l$ 一致。此时的分类区域相对更容易计算，实际上等同于训练集的 沃罗诺伊图（Voronoi tessellation）⁵。训练集中的每个点 $x_i$ 都在输入空间中对应着以它为最近一个点的区域，而对于这个区域上的所有点 $x$，其分类为 $\hat{G}(x)=g_i$。这种分类的决策边界比 15-邻域方法更加不规则。

对于量化的输出变量 $Y$ 的回归问题，k-最近邻方法也一样定位为在邻域上取平均。当然很少会有人选择 $k=1$。

与图 2.1 相比较，图 2.2 中的被误分类的训练样本要少得多。在图 2.3 中，训练集中的样本甚至都被正确分类。从直观上考虑，对于 k-近邻方法的样本集的拟合错误会随着 k 的增加而增加，而且当 $k=1$ 时样本集的拟合值为其本身，不产生任何错误。只有利用一个独立的测试集我们才能更客观地评价不同方法的预测能力的好坏。

从表面上看能，k-最近邻方法只有近邻个数 $k$ 一个参数，而最小二乘法有 $p$ 个参数。但实际上，在稍后的章节中我们可以看到其实际的参数个数为 $N/k$，通常要大于 $p$，随 $k$ 的增大而变小。简单地从直观上理解，k-最近邻实际上产生了 $N/k$ 个不重叠的区域，而在每个区域中都对应一个参数（即均值）。

另外，很明显我们无法用训练集上的误差平方和作为筛选 $k$ 的标准，因为那样会总是选择 $k=1$。k-最近邻方法更适合上述的“场景二”中描述的混合生成模型，相反在“场景一”的生成模型中会比线性决策边界误差更多。

2.3.3 最小二乘法与最近邻

最小二乘法的线性决策边界非常平滑，而且拟合稳定⁶。然而其有效性很大程度取决于线性假设的合理性。这个方法的方差小而有可能偏差大，我们会在稍后章节详细讨论。

另一方面，k 最近邻方法貌似对隐含的样本生成机制没有任何的假设，可以应用于各种场景。但其决策边界的每一个区域都由一部分训练集的输入变量所决定，因此十分不规则不稳定。这个方法的偏差小而方差大。

这两种方法都有各自最适用的场景。在本节中，线性回归更适用于上述的“场景一”，而最近邻更适合“场景二”。接下来就将从上帝视角揭秘：模拟数据的生成模型实际上介于场景一和场景二之间，可能更接近于后者。以下为“蓝色”类别 100 个样本的生成方法：首先生成服从二元高斯分布 $\mathcal{N}((1,0)^T,\mathbf{I})$ 的 10 个均值 $m_k$，$k=1,\dots,10$；其次以均匀的 $1/10$ 的概率随机选取 $m_k$，然后生成服从 $\mathcal{N}(m_k,\mathbf{I}/5)$ 的二维随机向量，重复这个过程 100 次。“橙色”类别的样本的生成方法与上述一致，只是将 10 个均值服从的二元高斯分布改为 $\mathcal{N}((0,1)^T,\mathbf{I})$。产生的结果为高斯混合分布。

训练集包含了“蓝色”和“橙色”各 100 个样本，测试集包含了同样生成模型产生的 10,000 个样本。图 2.4 展示了最小二乘法和不同 $k$ 值的 k-邻域方法在 10,000 个新样本上的分类测试结果。

**图 2.4**：模拟数据中的误分类比例曲线。不同模型面对同样的训练样本，大小为 200；测试集大小为 10,000。橙色曲线为 k-近邻在测试集上的误分类比例，蓝色曲线为其在训练集上的误分类比例。线性回归的结果为两个橙色和蓝色的正方形点（对应着自由度$N/k=3$），分别为其在测试集和训练集的误分类比例。紫色水平线为最优贝叶斯错误率。

目前最流行的统计学习方法中，大部分都为这两种简单的方法的变体。实际上，最简单的 1-近邻方法可以满足现实中很大比例的低维度问题。以下列举了一些对这两种简单方法的改进：

核方法（Kernel methods）在取平均时使用随着距离平滑地衰减至 0 的权重值，而 k-邻域使用非 0 即 1 的权重。
在高维空间，可以使用距离核函数（distance kernels），从而赋予一些输入变量更大的影响力。
局部回归方法使用局部加权最小二乘法拟合线性模型，而不仅是局部取均值。
使用原输入变量的基函数拓展模型来拟合线性模型，可以逼近任意复杂的模型关系。
复杂的投影寻踪和神经网络模型，是由非线性转换后的线性模型加和组成的。

hyperplane ↩︎
affine ↩︎
N > p ↩︎
mixture gaussian, 先用高斯分布生成均值，再根据该均值的高斯分布生成随机数。 ↩︎
Voronoi diagram ↩︎
原文为“stable to fit”。这里以及下一段中的的“稳定”，译者理解为模型对样本集的稳定性，即加入或去除某几个训练样本点会对模型产生多大的影响，以及样本中的离群值会对模型产生多大的影响。 ↩︎