本节介绍了两个线性模型的拟合方法：
- 最小二乘法
由于假设模型是线性的，预测的结果稳定但是可能会不准确。 -
最近邻法
对模型没有假设，预测结果准确但是不稳定（根据
线性模型和最小二乘
线性模型指形如 的模型，是超平面上的直线。
某个线性模型输入具有 个特征，输出是一个标量。预测模型可以表示为：
为了表示方便，我们常常把常数项加入 ，从而变成一个
维的向量：
其中：
最小二乘法是最流行的线性模型拟合方法。它的目的是找出系数 使
（residual sum of squares, RSS）最小：
其中 代表训练数据的序号。一共有
组训练数据。
用矩阵形式表示为：
其中 每一行都是一组训练数据输入：
用 对
求导，并令导数为 0 ：
得出二次函数最值点：
关于矩阵求导，可以看我另一篇文章：向量和矩阵求导。
最近邻法
最近邻法挑选 个与给定输入最相似的训练数据输入，并将其结果取平均得到预测结果。
其中 指输入
的
个最近的 Neighbor。
这里有一个可调节的参数 ，当选取的 k 越大时，误差越大。
方法对比
我们用两个不同的二元高斯分布各产生100个数据，并分别使用最小二乘法和最近邻法分类：
由于最小二乘法假设了模型是线性的，因此在二维平面上，分界线就是一条直线（三维时，是一个平面）。对于我们的数据集，这样的分类存在一些误差。
最近邻法结果根据 的选择不同而不同。当
增大时，由于考虑的点越来越多，边界也会越来越“模糊”。
维度诅咒：高维中的局部方法
看起来最近邻法似乎效果不错，理论上，只要我们训练数据足够多，总能找到距离 足够近的
个邻居。然而，在高维情况下，这种思路是不可行的。这也称作”维度诅咒“。维度诅咒主要体现在三个方面：
- 数据量膨胀
- 样本靠近边界
数据量膨胀
设想一个 维的超立方体，它的每个维度边长都是 1，体积为 1。假设我们要预测的是这个立方体中体积为
的一部分。那么被选取的立方体的边长就是
。
例如对于 10 维的输入，我们为了准确预测其中 1% 的数据，需要在每个维度选取 作为训练数据。如果需要预测 10%，则需要选取
。这显然太多了。
样本靠近边界
仍以这个 维的单位超立方体为例，假设我们对每个维度均匀采样。样本落在边长为
的立方体中的概率为
。可以看出，这个概率随着维度增加而减少（因为
）。也就是说，维度越大，越高比例的采样点靠近采样边界。
如果这个采样进行 次，那么所有样本都 不在 边长为
的小立方体中的概率为：
随着维度越来越大，“空心”现象会越来越严重。当我们尝试用最近邻法寻找邻居时，总会被“拉”到边界，导致有偏差的结果。
下面的图用简单的 1 维、2维情形直观显示了为什么维度扩大时，最近的邻居会越来越远(蓝色表示最近邻居)。
其根本原因是，我们定义的距离是欧氏距离，即：
在额外增加维度时， 肯定是增加的。
预测误差衡量标准
已知输入 X 与输出 Y 之间的真实关系为：
假设训练数据集为 ，我们希望用k-最近邻法预测
的输出。可以定义误差指标为平均方差（mean squared error，MSE）：
我们把预测误差分成了两个分量：
- Variance：表示预测值的离散程度
- Bias：表示预测值均值的偏差程度
我们用以下例子来说明 Var 和 Bias：
当我们选取 时，有
，这是最大值。
由于 ，无论如何选取邻居，都会导致预测结果往小了偏差（Bias）。
当维度增大时，由于 基本维持不变，Bias 也基本一致：
当维度增大时，即使 基本维持不变，由于
离中心越来越远，必然有 Var 越来越大：
绘制成图形如下：
