算法基础 - 最小二乘法（线性拟合）
算法基础 - 最小二乘法（线性拟合）
最小二乘法（又称最小平方法）是一种数学优化技术，主要用于解决数据拟合问题。它通过最小化误差的平方和来寻找数据的最佳函数匹配，广泛应用于数据科学、机器学习等领域。本文将详细介绍最小二乘法的历史、原理及其在线性拟合中的应用，并通过两个C++示例代码帮助读者更好地理解这一算法。
1. 最小二乘法的历史
最小二乘法最早由德国数学家卡尔·弗里德里希·高斯在1809年提出，用于计算天体轨道。当时，意大利天文学家朱赛普·皮亚齐发现了第一颗小行星谷神星，但由于观测数据有限，大多数科学家都无法准确预测其位置。时年24岁的高斯利用最小二乘法成功计算出谷神星的轨道，奥地利天文学家海因里希·奥尔伯斯据此重新发现了谷神星。法国科学家勒让德于1806年独立发明了最小二乘法，但因不为世人所知而默默无闻。1829年，高斯提供了最小二乘法的优化效果强于其他方法的证明，这一理论被称为高斯-马尔可夫定理。
2. 最小二乘法的原理
最小二乘法的核心思想是通过最小化误差的平方和来寻找数据的最佳函数匹配。具体来说，假设有一组观测数据（X1，Y1），（X2，Y2），…，（Xn，Yn），我们希望找到一条直线y = kx + b，使得这条直线与所有观测数据点的误差平方和最小。这里的误差指的是观测值与实际值之间的差量。
最小二乘法通过求解以下优化问题来确定直线的参数k和b：
其中，Q表示残差平方和，n表示观测数据的数量。通过求解上述优化问题，可以得到k和b的具体值。
3. 典型应用场景 - 线性拟合
线性拟合是应用最小二乘法的一个典型场景。假设我们有一组观测数据点（X1，Y1），（X2，Y2），…，（Xn，Yn），我们希望找到一条直线y = kx + b来拟合这些数据点。最小二乘法通过最小化残差平方和来确定这条直线的参数k和b。
具体来说，我们可以通过求解以下方程组来得到k和b的值：
其中，sumX表示所有X值的和，sumY表示所有Y值的和，sumX2表示所有X值的平方和，sumXY表示所有X值与Y值的乘积和。
4. 线性拟合 C++ 示例1
下面是一个使用C++实现最小二乘法进行线性拟合的示例代码：
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
class LeastSquare
{
private:
double k, b;
public:
LeastSquare(const vector<double>& x, const vector<double>& y)
{
double sumX = 0, sumY = 0, sumX2 = 0, sumXY = 0;
for(int i=0; i< x.size(); ++i)
{
sumX += x[i];
sumY += y[i];
sumX2 += x[i] * x[i];
sumXY += x[i] * y[i];
}
//依据推导公式: (n * sumXY - sumX * sumY) / (n * sumX2 - sumX * sumX)
k = (sumXY * x.size() - sumX * sumY) / (sumX2 * x.size() - sumX * sumX);
//依据推导公式: (sumX2 * sumY - sumX * sumXY) / (n * sumX2 - sumX * sumX)
b = (sumX2 * sumY - sumX * sumXY) / (sumX2 * x.size() - sumX * sumX);
}
double getY(const double x) const
{
return k * x + b;
}
void print() const
{
std::cout << "y = " << k << "x + " <<b << "\n";
}
};
int LeastSquare002()
{
std::vector<double> x = {10, 15, 20, 25, 30, 35, 40, 45};
std::vector<double> y = {2000.36, 2000.50, 2000.72, 2000.80, 2001.07, 2001.25, 2001.48, 2001.60};
int sz = x.size();
x.resize(sz / 2);
LeastSquare ls(x, y);
ls.print();
cout<<"Input x:\n";
double x0;
while(cin>>x0)
{
cout<<"y = "<<ls.getY(x0)<<endl;
cout<<"Input x:\n";
}
}
return 0;
}
5. 线性拟合 C++ 示例2
这是一个使用C++实现最小二乘法进行线性拟合的另一个示例代码：
#include <iostream>
#include <vector>
#include <numeric>
using Parameter = struct {
double k; // 斜率
double b; // 截距
};
// 最小二乘法计算过程
bool LeastSquares(std::vector<double>& X, std::vector<double>& Y, Parameter& param)
{
if (X.empty() || Y.empty())
return false;
int n = X.size();
double sumX = std::accumulate(X.begin(), X.end(), 0.0);
double sumY = std::accumulate(Y.begin(), Y.end(), 0.0);
std::cout << "sumX = " << sumX << ", sumY = " << sumY << std::endl;
double meanX = sumX / n;
double meanY = sumY / n;
std::cout << "meanX = " << meanX << ", meanY = " << meanY << std::endl;
double sumXY = 0.0;
double sumX2 = 0.0;
for (int i = 0; i < n; i++)
{
sumXY += X[i] * Y[i]; //对x与y的乘积求和
sumX2 += X[i] * X[i]; //对x的平方求和
}
std::cout << "sumXY = " << sumXY << ", sumX2 = " << sumX2 << std::endl;
//依据推导公式: (n * sumXY - sumX * sumY) / (n * sumX2 - sumX * sumX)
param.k = (sumXY - n * meanX * meanY) / (sumX2 - n * meanX * meanX);
//依据推导公式: y = kx + b ---> b = y - kx
param.b = meanY - param.k * meanX;
return true;
}
int Test001LeastSquares()
{
std::vector<double> X = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<double> Y = {3, 5, 7, 9, 11, 13, 15, 17, 19};
Parameter param;
std::cout << " =============================== " << std::endl;
if (LeastSquares(X, Y, param))
{
std::cout << "拟合直线的方程为: y = " << param.k << "x + " << param.b << std::endl;
}
else
{
std::cout << "拟合失败" << std::endl;
}
std::cout << " =============================== \n\n\n " << std::endl;
return 0;
}
这两个示例代码展示了如何使用C++实现最小二乘法进行线性拟合。第一个示例使用了一个类来封装最小二乘法的计算过程，第二个示例则使用了一个函数来实现相同的功能。通过这两个示例，读者可以更好地理解最小二乘法的实现细节。