ESL 2.3：最小二乘法和最近邻法

作者: 找不到工作 | 来源:发表于2021-07-25 13:46 被阅读0次

ESL 2.3：最小二乘法和最近邻法
模式识别——6 其他分类方法
统计学习方法之kNN算法
k 近邻法
数据科学 6 机器学习：k-近邻算法
数据科学（机器学习:k-近邻算法）
k-近邻算法
机器学习笔记-k近邻算法
算法图解 (十)
PyTorch基础知识

本节介绍了两个线性模型的拟合方法：

最小二乘法
由于假设模型是线性的，预测的结果稳定但是可能会不准确。
$k$ 最近邻法
对模型没有假设，预测结果准确但是不稳定（根据 $k$ 设定值会不同）

线性模型和最小二乘

线性模型指形如 $y=ax+b$ 的模型，是超平面上的直线。

某个线性模型输入具有 $p$ 个特征，输出是一个标量。预测模型可以表示为：

$\hat y = \beta_0 + \sum_{i=1}^p x_i \beta_i$

为了表示方便，我们常常把常数项加入 $\beta$ ，从而变成一个 $p+1$ 维的向量：

$\hat y = X^T \boldsymbol{\beta}$

其中：
$X^T = [1, x_1, x_2, ..., x_p]$
$\boldsymbol{\beta} = [\beta_0, \beta_1, \beta_2, ..., \beta_p]^T$

最小二乘法是最流行的线性模型拟合方法。它的目的是找出系数 $\boldsymbol{\beta}$ 使 $||Y-\hat Y||_2$ （residual sum of squares, RSS）最小：

$\text{RSS}(\boldsymbol{\beta} ) = \sum_{j=1}^N (y_j - X_j^T\boldsymbol{\beta} )^2$

其中 $j$ 代表训练数据的序号。一共有 $N$ 组训练数据。

用矩阵形式表示为：

$\text{RSS}(\boldsymbol{\beta}) = (\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta} )^T(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta} )$

其中 $\boldsymbol{ X }$ 每一行都是一组训练数据输入：

$\boldsymbol{ X } = \begin{bmatrix} 1 & x_{11} & x_{12} & \cdots & x_{1p} \\ 1 & x_{21} & x_{22} & \cdots & x_{2p} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{N1} & x_{N2} & \cdots & x_{Np} \\ \end{bmatrix}_{ N \times ( p+1 ) }$

用 $\text{RSS}(\boldsymbol{\beta})$ 对 $\boldsymbol{\beta}$ 求导，并令导数为 0 ：
$\boldsymbol{X}^T(\boldsymbol{y} - \boldsymbol{X} \boldsymbol{\beta}) = 0$
得出二次函数最值点：

$\hat{\boldsymbol{\beta}} = (\boldsymbol{X}^T \boldsymbol{X})^{-1} \boldsymbol{X}^T \boldsymbol{y}$

关于矩阵求导，可以看我另一篇文章：向量和矩阵求导。

方法对比

我们用两个不同的二元高斯分布各产生100个数据，并分别使用最小二乘法和最近邻法分类：

最小二乘法分类结果

由于最小二乘法假设了模型是线性的，因此在二维平面上，分界线就是一条直线（三维时，是一个平面）。对于我们的数据集，这样的分类存在一些误差。

最近邻法分类结果（k = 15）

最近邻法分类结果（k = 1）

最近邻法结果根据 $k$ 的选择不同而不同。当 $k$ 增大时，由于考虑的点越来越多，边界也会越来越“模糊”。

维度诅咒：高维中的局部方法

看起来最近邻法似乎效果不错，理论上，只要我们训练数据足够多，总能找到距离 $x$ 足够近的 $k$ 个邻居。然而，在高维情况下，这种思路是不可行的。这也称作”维度诅咒“。维度诅咒主要体现在三个方面：

数据量膨胀
样本靠近边界

数据量膨胀

设想一个 $p$ 维的超立方体，它的每个维度边长都是 1，体积为 1。假设我们要预测的是这个立方体中体积为 $v$ 的一部分。那么被选取的立方体的边长就是 $e_p(r) = v^{1/p}$ 。

例如对于 10 维的输入，我们为了准确预测其中 1% 的数据，需要在每个维度选取 $0.01^{0.1} = 63.09\%$ 作为训练数据。如果需要预测 10%，则需要选取 $0.1^{0.1} = 79.43\%$ 。这显然太多了。

每个维度需要的训练数据与总维度的关系

样本靠近边界

仍以这个 $p$ 维的单位超立方体为例，假设我们对每个维度均匀采样。样本落在边长为 $r$ 的立方体中的概率为 $r^p$ 。可以看出，这个概率随着维度增加而减少（因为 $r \leq 1$ ）。也就是说，维度越大，越高比例的采样点靠近采样边界。

如果这个采样进行 $N$ 次，那么所有样本都不在边长为 $r$ 的小立方体中的概率为：

$\text{P}(x >= r) = (1-r^p)^N$

随着维度越来越大，“空心”现象会越来越严重。当我们尝试用最近邻法寻找邻居时，总会被“拉”到边界，导致有偏差的结果。

下面的图用简单的 1 维、2维情形直观显示了为什么维度扩大时，最近的邻居会越来越远(蓝色表示最近邻居)。

k-最近邻法（k=1）时的邻居

其根本原因是，我们定义的距离是欧氏距离，即：

$d = \sqrt{\sum_{i=1}^p (x_i - a_i)^2}$

在额外增加维度时， $d$ 肯定是增加的。

预测误差衡量标准

已知输入 X 与输出 Y 之间的真实关系为：

$Y = f(X)$

假设训练数据集为 $\tau$ ，我们希望用k-最近邻法预测 $x_0$ 的输出。可以定义误差指标为平均方差（mean squared error，MSE）：

$\begin{align*} \text{MSE}(x_0) &= E_{\tau} [f(x_0) - \hat{y}_0]^2 \\ &= E_{\tau}[\hat{y}_0 - E_{\tau}(\hat{y}_0)]^2 + [E_\tau(\hat{y}_0) - f(x_0)]^2 \\ &= \text{Var}_{\tau}(\hat{y}_0) + \text{Bias}^2(\hat{y}_0) \end{align*}$