3分钟懂线性回归预测算法瞅一眼，懂个概念也值得

线性回归（linear-regression）预测算法C++实现

上一期，和大家分享了K-means聚类算法的基本概念和实现要点（漏了的同学欢迎加公众号回顾），本期和大家介绍线性回归预测算法的基本概念和实现要点，它一般用以解决“使用已知样本对未知公式参数的估计”类问题。估计出公式参数后，进一步的，可以对未知的样本进行计算以预测（或者推荐）。

本文主要参照 http://hi.baidu.com/hehehehello/item/40025c33d7d9b7b9633aff87 进行的浓缩，原文的作者是：苏冉旭。 再次感谢原作者写出了如此通俗易懂的文章。

首先，来看看机器学习领域，几个相关的基本概念： 回归(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）第二部分：算法实现 2）第三部分：测试用例 2）第四部分：输出结果