机器学习金典算法系列旨在归纳总结常用经典机器学习算法，其中内容来自自己学习理解、博文参考等，目的在于再次深入学习这类算法，并加以总结，提升自我，方便文档查阅；如有不足，请方家指点
最小二乘法
0 前言
首先从字面上理解，最小二乘法，就是
最小化平方和的优化方法
；这里的平方和指的是误差（真实目标对象与拟合目标对象的差）的平方；其目的/核心思想就是通过最小化这个误差的平方和，使得拟合对象最大限度逼近目标对象。
值得一提的是最小二乘是一种优化思想，当结合具体应用对象，它才被具体化为某类最小二乘法，如常用的有
最小二乘法直线拟合
，
最小二乘法多项式（曲线）拟合
，它们的公式、推导、证明都不相同，但它们背后的思想是统一的。最小二乘法处理的一般模型表达式如下：
y
=
θ
1
x
1
+
θ
2
x
2
+
θ
3
x
3
+
⋯
+
θ
n
x
n
y=\theta _1 x_1+ \theta _2 x_2 + \theta _3 x_3 + \cdots + \theta _n x_n
y
=
θ
1
x
1
+
θ
2
x
2
+
θ
3
x
3
+
⋯
+
θ
n
x
n
若是直线拟合，则：
y
=
θ
1
+
θ
2
x
y=\theta _1 + \theta _2 x
y
=
θ
1
+
θ
2
x
若是曲线拟合，则：
y
=
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
y=\theta _1 + \theta _2 x + \theta _3 x^2 + \cdots + \theta _n x^n
y
=
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
视问题复杂度而定
x
x
x
取几次方。这里可能有人有疑问，最小二乘不是处理线性问题吗？怎么
x
n
x^n
x
n
都出来了？
注意，我们的目的是求取一个非线性方程，但当我们用最小二乘求解时，我们针对的是
θ
\theta
θ
变量，而不是
x
x
x
，也就是说，机器学习中，这里的
x
x
x
是输入，是已知量，
y
y
y
是输出，是预测量，
θ
\theta
θ
才是我们要学习的变量；所以这还是一个线性问题。
1 最小二乘解析
想要搞清楚最小二乘法，我们从下面三个问题来分析
1.1 怎样定义误差
误差，当然是真实值与拟合值的差
e
i
=
y
^
i
−
y
i
e_i=\hat y_i – y_i
e
i
=
y
^
i
−
y
i
其中，
e
i
e_i
e
i
表示第
i
i
i
个样本的误差，
y
i
y_i
y
i
表示该样本的预测值，
y
^
i
\hat y_i
y
^
i
表示真实值，也即：
e
i
=
y
^
i
−
（
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
）
e_i=\hat y_i -（\theta _1 + \theta _2 x + \theta _3 x^2 + \cdots + \theta _n x^n）
e
i
=
y
^
i
−
（
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
）
而误差平方和
Q
=
∑
i
=
1
n
e
i
2
=
∑
i
=
1
n
(
y
^
i
−
y
i
)
2
=
∑
i
=
1
n
[
y
^
i
−
（
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
）
]
2
\begin{aligned}{} Q=& \displaystyle \sum _{i=1}^n e_i^2 \\ =& \displaystyle \sum _{i=1}^n(\hat y_i – y_i)^2 \\ =& \displaystyle \sum _{i=1}^n [ \hat y_i -（\theta _1 + \theta _2 x + \theta _3 x^2 + \cdots + \theta _n x^n）] ^2 \end{aligned}
Q
=
=
=
i
=
1
∑
n
e
i
2
i
=
1
∑
n
(
y
^
i
−
y
i
)
2
i
=
1
∑
n
[
y
^
i
−
（
θ
1
+
θ
2
x
+
θ
3
x
2
+
⋯
+
θ
n
x
n
）
]
2
但为啥要平方（2范数）呢？绝对值（1范数）不可以吗？
我们从几何角度来解释这个问题，以直线拟合模型为例，我们在直线上寻找一个点到点
(
x
0
,
y
0
)
(x_0,y_0)
(
x
0
,
y
0
)
距离最短，若采用绝对值方式的话，则
m
i
n
(
∣
x
−
x
0
∣
+
∣
y
−
y
0
∣
)
min(|x-x_0|+|y-y_0|)
m
i
n
(
∣
x
−
x
0
∣
+
∣
y
−
y
0
∣
)
所以最小情况就是
x
=
x
0
x=x_0
x
=
x
0
或者
y
=
y
0
y=y_0
y
=
y
0
处，如下图
而采用平方方式的话，则可以视为两点间距离（这里只是没有开方），最小化就是点到直线间距离最短，当然就是垂线
m
i
n
[
(
x
−
x
0
)
2
+
(
y
−
y
0
)
2
]
min[(x-x_0)^2+(y-y_0)^2]
m
i
n
[
(
x
−
x
0
)
2
+
(
y
−
y
0
)
2
]
所以最小情况就是垂足处，如下图
可以看出，平方要比绝对值更能得到最短距离，即使得误差最小化，也就是更能使得拟合函数逼近真实函数。
1.2 怎样最小化误差
我们假设有
m
m
m
个样本，则对于
m
m
m
个样本来说，可用如下方程组来表示：
{
θ
1
+
θ
2
x
1
+
θ
3
x
1
2
+
⋯
+
θ
n
x
1
n
=
y
1
θ
1
+
θ
2
x
2
+
θ
3
x
2
2
+
⋯
+
θ
n
x
2
n
=
y
2
⋮
θ
1
+
θ
2
x
i
+
θ
3
x
i
2
+
⋯
+
θ
n
x
i
n
=
y
i
⋮
θ
1
+
θ
2
x
m
+
θ
3
x
m
2
+
⋯
+
θ
n
x
m
n
=
y
m
\left \{ \begin{array}{c} \theta _1 + \theta _2 x_1 + \theta _3 x_1^2 + \cdots + \theta _n x_1^n&=&y_1 \\ \theta _1 + \theta _2 x_2 + \theta _3 x_2^2 + \cdots + \theta _n x_2^n&=&y_2 \\ \vdots \\ \theta _1 + \theta _2 x_i + \theta _3 x_i^2 + \cdots + \theta _n x_i^n&=&y_i \\ \vdots \\ \theta _1 + \theta _2 x_m + \theta _3 x_m^2 + \cdots + \theta _n x_m^n&=&y_m \end{array} \right.
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎧
θ
1
+
θ
2
x
1
+
θ
3
x
1
2
+
⋯
+
θ
n
x
1
n
θ
1
+
θ
2
x
2
+
θ
3
x
2
2
+
⋯
+
θ
n
x
2
n
⋮
θ
1
+
θ
2
x
i
+
θ
3
x
i
2
+
⋯
+
θ
n
x
i
n
⋮
θ
1
+
θ
2
x
m
+
θ
3
x
m
2
+
⋯
+
θ
n
x
m
n
=
=
=
=
y
1
y
2
y
i
y
m
转换为矩阵形式
[
1
x
1
x
1
2
⋯
x
1
n
1
x
2
x
2
2
⋯
x
2
n
⋯
⋯
⋯
⋮
⋯
1
x
m
x
m
2
⋯
x
m
n
]
[
θ
1
θ
2
⋮
θ
n
]
=
[
y
1
y
2
⋮
y
m
]
\begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \cdots & \cdots & \cdots & \vdots & \cdots \\ 1 & x_m & x_m^2 & \cdots & x_m^n \\ \end{bmatrix} \begin{bmatrix} \theta _1 \\ \theta _2 \\ \vdots \\ \theta _n \\ \end{bmatrix}= \begin{bmatrix} y_1\\ y_2\\ \vdots \\ y_m \end{bmatrix}
⎣
⎢
⎢
⎢
⎡
1
1
⋯
1
x
1
x
2
⋯
x
m
x
1
2
x
2
2
⋯
x
m
2
⋯
⋯
⋮
⋯
x
1
n
x
2
n
⋯
x
m
n
⎦
⎥
⎥
⎥
⎤
⎣
⎢
⎢
⎢
⎡
θ
1
θ
2
⋮
θ
n
⎦
⎥
⎥
⎥
⎤
=
⎣
⎢
⎢
⎢
⎡
y
1
y
2
⋮
y
m
⎦
⎥
⎥
⎥
⎤
简化为
X
⋅
θ
=
Y
X \cdot \theta = Y
X
⋅
θ
=
Y
所以，最小二乘法表达式为
m
i
n
∣
∣
Y
^
−
X
⋅
θ
∣
∣
2
min||\hat Y-X\cdot \theta||_2
m
i
n
∣
∣
Y
^
−
X
⋅
θ
∣
∣
2
显然，该误差函数是关于
θ
i
\theta_i
θ
i
的多元二次函数方程组，要求取最小值，则是求取一阶导数并设其为0，即求取
极小值
。这里不展开求偏导，后面以直线模型为例展示求导过程。
将上式对
θ
\theta
θ
求导，并令其为0
2
(
Y
^
−
X
⋅
θ
)
⋅
X
=
0
2(\hat Y-X\cdot \theta)\cdot X = 0
2
(
Y
^
−
X
⋅
θ
)
⋅
X
=
0
X
X
X
不为0，也即
Y
^
−
X
⋅
θ
=
0
\hat Y-X\cdot \theta = 0
Y
^
−
X
⋅
θ
=
0
两边同时乘
X
T
X^T
X
T
，变形为
X
T
X
⋅
θ
=
X
T
Y
^
X^TX\cdot \theta = X^T\hat Y
X
T
X
⋅
θ
=
X
T
Y
^
在变形为
θ
=
(
X
T
X
)
−
1
X
T
Y
^
\theta = (X^TX)^{-1}X^T\hat Y
θ
=
(
X
T
X
)
−
1
X
T
Y
^
##1.3 什么情况下能用这矩阵形式求解
从上面的最后一个式子可以看出，只有当
矩阵
X
T
X
X^TX
X
T
X
可逆
时，该式才成立；而相反，最小二乘法则不可用，也就是说无法用直接求一阶导数方式，计算出最优解，这时就需要用
梯度下降法
来迭代逼近最优解。
3 直线拟合最小二乘法
3.1 理论推导
首先直线模型为：
y
=
θ
1
+
θ
2
x
y=\theta _1 + \theta _2 x
y
=
θ
1
+
θ
2
x
其平均损失函数形式为：
Q
=
∑
i
=
1
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
2
Q = \displaystyle \sum _{i=1}^n ( \hat y_i -\theta _1 – \theta _2 x_i)^2
Q
=
i
=
1
∑
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
2
其中
x
i
x_i
x
i
表示样本输入，
y
^
i
\hat y_i
y
^
i
表示样本真实输出。
在这里，最小二乘法就是求解
Q
Q
Q
的最小值，因为误差
Q
Q
Q
最小，对应
θ
\theta
θ
值最优；所有我们将上式看成一个
Q
Q
Q
关于
θ
\theta
θ
变量的函数，问题转成一个求极小值问题：
{
∂
Q
∂
θ
1
=
2
∑
i
=
1
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
∗
(
−
1
)
=
0
∂
Q
∂
θ
2
=
2
∑
i
=
1
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
∗
(
−
x
i
)
=
0
\left \{ \begin{array}{c} \frac{\partial Q}{\partial \theta_1} = 2 \displaystyle \sum _{i=1}^n ( \hat y_i -\theta _1 – \theta _2 x_i)*(-1) = 0\\ \frac{\partial Q}{\partial \theta_2} = 2 \displaystyle \sum _{i=1}^n ( \hat y_i -\theta _1 – \theta _2 x_i)*(-x_i) = 0 \\ \end{array} \right.
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
∂
θ
1
∂
Q
=
2
i
=
1
∑
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
∗
(
−
1
)
=
0
∂
θ
2
∂
Q
=
2
i
=
1
∑
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
∗
(
−
x
i
)
=
0
两式化简为：
{
∑
i
=
1
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
=
0
∑
i
=
1
n
(
x
i
∗
y
^
i
−
θ
1
∗
x
i
−
θ
2
x
i
2
)
=
0
\left \{ \begin{array}{c} \displaystyle \sum _{i=1}^n ( \hat y_i -\theta _1 – \theta _2 x_i)= 0\\ \displaystyle \sum _{i=1}^n ( x_i * \hat y_i -\theta _1* x_i – \theta _2 x_i^2)= 0 \\ \end{array} \right.
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
i
=
1
∑
n
(
y
^
i
−
θ
1
−
θ
2
x
i
)
=
0
i
=
1
∑
n
(
x
i
∗
y
^
i
−
θ
1
∗
x
i
−
θ
2
x
i
2
)
=
0
两式再化简为：
{
n
θ
1
=
∑
i
=
1
n
y
^
i
−
θ
2
∑
i
=
1
n
x
i
∑
i
=
1
n
(
x
i
∗
y
^
i
)
−
θ
1
∑
i
=
1
n
x
i
−
θ
2
∑
i
=
1
n
x
i
2
=
0
\left \{ \begin{array}{c} n\theta _1 = \displaystyle \sum _{i=1}^n \hat y_i – \theta _2 \displaystyle \sum _{i=1}^nx_i\\ \displaystyle \sum _{i=1}^n ( x_i * \hat y_i) -\theta _1\displaystyle \sum _{i=1}^n x_i – \theta _2 \displaystyle \sum _{i=1}^nx_i^2= 0 \\ \end{array} \right.
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
n
θ
1
=
i
=
1
∑
n
y
^
i
−
θ
2
i
=
1
∑
n
x
i
i
=
1
∑
n
(
x
i
∗
y
^
i
)
−
θ
1
i
=
1
∑
n
x
i
−
θ
2
i
=
1
∑
n
x
i
2
=
0
将
θ
1
\theta_1
θ
1
消掉，计算出
θ
2
\theta_2
θ
2
，再计算
θ
1
\theta_1
θ
1
，得：
{
θ
1
=
∑
i
=
1
n
x
i
2
∑
i
=
1
n
y
^
i
−
∑
i
=
1
n
x
i
∑
i
=
1
n
x
i
y
^
i
n
∑
i
=
1
n
x
i
2
−
(
∑
i
=
1
n
x
i
)
2
θ
2
=
n
∑
i
=
1
n
x
i
y
^
i
−
∑
i
=
1
n
x
i
∑
i
=
1
n
y
^
i
n
∑
i
=
1
n
x
i
2
−
(
∑
i
=
1
n
x
i
)
2
\left \{ \begin{array}{c} \theta _1 = \dfrac{\displaystyle \sum _{i=1}^nx_i^2 \displaystyle \sum _{i=1}^n \hat y_i – \displaystyle \sum _{i=1}^nx_i \displaystyle \sum _{i=1}^n x_i\hat y_i}{n\displaystyle \sum _{i=1}^nx_i^2 – (\displaystyle \sum _{i=1}^nx_i)^2} \\ \theta _2 = \dfrac{n\displaystyle \sum _{i=1}^n x_i\hat y_i – \displaystyle \sum _{i=1}^nx_i \displaystyle \sum _{i=1}^n\hat y_i}{n\displaystyle \sum _{i=1}^nx_i^2 – (\displaystyle \sum _{i=1}^nx_i)^2}\\ \end{array} \right.
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎧
θ
1
=
n
i
=
1
∑
n
x
i
2
−
(
i
=
1
∑
n
x
i
)
2
i
=
1
∑
n
x
i
2
i
=
1
∑
n
y
^
i
−
i
=
1
∑
n
x
i
i
=
1
∑
n
x
i
y
^
i
θ
2
=
n
i
=
1
∑
n
x
i
2
−
(
i
=
1
∑
n
x
i
)
2
n
i
=
1
∑
n
x
i
y
^
i
−
i
=
1
∑
n
x
i
i
=
1
∑
n
y
^
i
3.2 代码实现
原理简单，我的代码实现也较粗糙，能表达就行
#include<iostream>
#include<vector>
using namespace std;
//y = ax+b
void LeastSquare(double& a, double& b, vector<double> x, vector<double> y)
{
if (x.size()<2 || y.size()<2 || x.size() != y.size())
{
return;
}
double sum_x = 0;
double sum_y = 0;
double sum_xy = 0;
double sum_xx = 0;
for (size_t i = 0; i < x.size(); i++)
{
sum_x += x[i];
sum_y += y[i];
sum_xy += x[i] * y[i];
sum_xx += x[i] * x[i];
}
b = (sum_xx*sum_y - sum_x*sum_xy)*1.0 / (x.size()*sum_xx - sum_x*sum_x);
a = (x.size()*sum_xy - sum_x*sum_y)*1.0 / (x.size()*sum_xx - sum_x*sum_x);
}
int main()
{
vector<double> x;
vector<double> y;
//y = -2.5x+1.7 模拟数据
for (size_t i = 0; i < 10; i++)
{
x.push_back(i);
y.push_back(-2.5 * i + 1.7);
}
double a = 0;
double b = 0;
LeastSquare(a, b, x, y); //调用最小二乘法计算a b值
cout << a << " " << b << endl;
return 0;
}
4 最小二乘法与梯度下降法
首先它们都是机器学习中，计算
问题最优解的优化方法
，但它们采用的方式不同，前者采用暴力的解方程组方式，直接，简单，粗暴，在条件允许下，求得最优解；而后者采用步进迭代的方式，一步一步的逼近最优解。实际应用中，大多问题是不能直接解方程求得最优解的，所以梯度下降法应用广泛，关于
梯度下降法
，可参见我的博文或其他博文。
5 参考文献
【1】到底什么是最小二乘法：
https://blog.csdn.net/yuxiaoxi21/article/details/71469311
【2】最小二乘法及算法实现：
https://blog.csdn.net/zkw12312/article/details/78783939