linear-regression预测算法C++实现

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

第一部分:一维样本,已抽象成二维平面上的点

//point
class 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;
};

第二部分:算法的实现

// one-dimensional
// Y=f(X)=aX+b
class 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;
};

第三部分:测试用例

#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 原文的作者是:苏冉旭。
再次感谢原作者写出了如此通俗易懂的文章。

评论关闭。