linear-regression预测算法C++实现
机器学习领域，几个常见的概念：
回归(regression)：用已知样本对未知公式参数的估计。
线性回归(linear regression)：回归的一种，回归函数是一次函数，例如：
result=f(X,Y,Z,…)=aX+bY+cZ+…+…
其中X，Y，Z是训练样本集中样本的各个维度(feature)，a，b，c是模型的未知参数。
逻辑回归(logistic regression)：将result归一化到[0, 1]区间，即使用一个逻辑方程将线性回归归一化。
总而言之，逻辑回归是线性回归的一种，线性回归是回归的一种。
线性回归模型是有效的
既然逻辑回归是线性回归的一种，那么我们重点就线性回归展开讨论，线性回归的预测模型虽然是一元方程，但现实中很多应用场景符合这个模型，例如商品的价格与商品的销量之间的关系。一般来说价格越贵则销量越低，价格越便宜则销量越高，于是我们就能够用
“销量=a*价格+b”这个模型来最大化商家的收益。
如何确定a和b的值呢，我们可以根据历史“价格-销售”数据，来计算最优一元模型的a和b的值。
当然，很多应用场景不能够使用线性回归模型来进行预测，例如，月份和平均气温，平均气温并不随着月份的增长呈线性增长或下降的趋势。那么，什么时候可以使用线性回归模型呢？
线性回归模型的适用场景
1）可以用于预测，也可以用于分类，用于分类问题时，需要设定阈值区间，并提前知晓阈值区间与类别的对应关系
2）只适用于线性问题，可以有多个维度(feature)
如何求解线性回归中的维度参数
在已知样本集set的时候，如果根据样本集得到result=f(X,Y,Z,…)=aX+bY+cZ+…+…中的未知参数a，b，c呢？
最小二乘法
最小二乘法适用于任意多维度的线性回归参数求解，它可求解出一组最优a，b，c解，使得对于样本集set中的每一个样本data，用result=f(X,Y,Z,…)来预测样本，预测值与实际值的方差最小。方差是我们常见的估值函数(cost function)。
梯度下降法
最小二乘法实际上只定义了估值函数是方差，真正求解a，b，c的方法是梯度下降法，这是一个枚举型的求解算法，其算法步骤如下：
1）使用随机的a0, b0, c0作为初始值
2）分别求解最优a, b, c…，对于每个维度参数的求解，步骤为（以a为例）：
2.1）设定a范围的最大值与最小值
2.2）设定a计算的梯度步长（这就是它叫梯度下降法的原因）
2.3）固定其他维度参数
2.4）计算a的所有取值中，使得估值函数最小的那个a即为所求
数学上可以证明：
1）上述算法是可以收敛的（显而易见）
2）分别求出a，b，c的最优值，组合起来就是整体的最优值（没这么明显了），这个结论是很重要的，假设样本个数为n，计算a，b，c的算法复杂度都是线性的O(m)，这个结论让算法的整体复杂度是n*O(m) + n*O(m) + n*O(m)，而不是[n*O(m) ]*[n*O(m)]*[n*O(m)]的关系。
为了清晰直白的用程序表达算法的整个过程，未经过任何优化的C++实现源码如下，为了简化计算，不妨设特征只有一个，预测方程为Y=aX+b
第一部分：一维样本，已抽象成二维平面上的点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | //pointclass CPoint{ public: CPoint() { m_x = 0.0; m_y = 0.0; } CPoint(double x, double y) { m_x = x; m_y = y; } double GetX() const { return m_x; } double GetY() const { return m_y; } private: double m_x; double m_y;}; |
第二部分：算法的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | // one-dimensional// Y=f(X)=aX+bclass CLinearRegression{public: // 第一步骤：初始化 int Init(const vector< CPoint>& points) { if(points.size() == 0) { return -1; } m_points = points; } // 第二步骤：计算a和b int Run() { // 先将a和b取个随机的初值，此处取了0 m_a = 0; m_b = 0; double minCost = CaculateCost(m_a,m_b); double curCost = 0.0; // 先计算最优的a for(double a=MIN_a; a< =MAX_a; a+=INC) { curCost = CaculateCost(a,m_b); if(curCost< minCost) { m_a = a; minCost = curCost; } } // 再计算最优的b for(double b=MIN_b; b< =MAX_b; b+=INC) { curCost = CaculateCost(m_a,b); if(curCost< minCost) { m_b = b; minCost = curCost; } } } // 第三步骤：输出结果 int PrintResult() { printf("Y=f(X)=%lfX+(%lf)\n",m_a,m_b); printf("minCost=%lf\n",CaculateCost(m_a,m_b)); }private: // 内部函数：给定a,b，输出当前所有样本的预计与实际值的方差 double CaculateCost(double a, double b) { double cost = 0.0; double xReal = 0.0; double yReal = 0.0; double yPredict = 0.0; double yDef = 0.0; for(uint32_t i=0;i< m_points.size();++i) { // x实际值 xReal = m_points[i].GetX(); // y实际值 yReal = m_points[i].GetY(); // y预测值 yPredict = a*xReal + b; yDef = yPredict - yReal; // 累加方差 cost += (yDef*yDef); } return cost; } public: CLinearRegression() { }private: // a，b的取值范围 const static double MIN_a = -2768.0; const static double MAX_a = 2768.0; const static double MIN_b = -2768.0; const static double MAX_b = 2768.0; // 梯度递增值 const static double INC = 0.5; // a，b，样本的保存 double m_a; double m_b; vector< CPoint> m_points;}; |
第三部分：测试用例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include< stdio.h>#include< vector>int main(){ // 构造三个点，放在y=x+1左右 vector< CPoint> points; points.push_back(CPoint(-1,0)); points.push_back(CPoint(0,1)); points.push_back(CPoint(1,2.1)); // 使用线性回归方法计算a和b CLinearRegression lr; lr.Init(points); lr.Run(); lr.PrintResult(); return 0;} |
第四部分：结果输出
[shenjian@dev02 linear-regression]$ ./a.out
Y=f(X)=1.000000X+(1.000000)
minCost=0.010000
末了，本文主要参照 http://hi.baidu.com/hehehehello/item/40025c33d7d9b7b9633aff87 原文的作者是：苏冉旭。
再次感谢原作者写出了如此通俗易懂的文章。
http://www.habadog.com/2014/06/27/linear-regression-cpp/#rd