梯度下降法解多元线性回归(C++) - CodeFight compute

提供测试

题意 ：

已知有数据集包含多个工程师的信息，而对于每个工程师有engineer -> [y,x1,x2] 表示当其XP的值为x1，解决的题目为x2个时，可以开出y的薪水。请用多元线性回归，给出所查询工程师的薪水。

题解：

题目比较恶心的是最终参数要保留两位小数，所以并不是最拟合的就是结果。小心精度就好，不是本次题解的重点。

说道解线性回归，之前CodeFight也有个题，是一元的，直接每个方程求导后用高斯消元解决的。当时尝试用梯度下降法，但总是不找不到合适的rate而不收敛，十分的费解。

首先，要确定的是以L2为cost function的线性回归是一定可以通过设置合适的步长(这里就称作rate)，一步步迭代到最有点的。证明很简单，因为L2是光滑的，所以其最小值一定在某个极小值点，而当我们把L2对每个自变量求二阶导，得到的都是一个一元方程，可知对于任意方向都只存在一个驻点，因此用合适步长梯度下降法一定会收敛并且必然可以取到cost function的全局最小值。

而梯度下降法如何做呢，网上也有很多资料了，包括吴恩达在Coursera上的公开课都说得很详细。对于每次迭代，算出当前cost function在各个自变量维度上的斜率(对该 变量求偏导)，然后让参数往负斜率方向迭代，因为全局只有一个极小值点，所以必然会让cost function的各个维度偏导从一个大于0的点通过不断的迭代到一个逼近0的点。

但问题的关键是在开始实现的时候，我发现总是不收敛，cost function随着每次迭代变化却越来越大(有种每次都是矫枉过正的感觉)。在想是不是步长rate设置得不够好，但尝试了很多不同的步长，都无法得到想要的结果。最终发现是自己漏了一个很重要的步骤，一定要做归一化！！如果数据集中每个变量差别很大，或者一个数据的每个特征取值相差很大，会很难找到合适的步长的。归一化有很多种方法，我的处理是取测试集的平均值。

double rd(double x){
    char buff[100];
    double a;
    sprintf(buff,"%.2lf",x);
    sscanf(buff,"%lf",&a);
    return a;
}
int compute(vector<vector<int>> engineers, vector<int> candidate) {
    int n=engineers.size();
    double v[3][5],sum[3],E[n][3];
    for (int j=0;j<3;j++){
        sum[j]=1;
        for (int i=0;i<n;i++)
            sum[j]+=engineers[i][j];
        sum[j]/=n; 
    } 
    sum[0]=1;
    for (int i=0;i<n;i++)
        for (int j=0;j<3;j++)
            E[i][j]=engineers[i][j]/sum[j];
    memset(v,0,sizeof(v));
    double h[3],p[3],rate=0.01,pre=1e+50,now;
    for (int i=0;i<3;i++)
        h[i]=0;
    for (int times=0;times<2000000;times++){
        for (int i=0;i<3;i++)
            p[i]=h[i]; 
        for (int i=0;i<n;i++){
            double d = E[i][0] - (p[0] + p[1]*E[i][1] + p[2]* E[i][2]);   
            h[0]+=rate*d;
            for (int j=1;j<3;j++)
                h[j]+=rate*E[i][j]*d;
        }  
    }
    h[1]/=sum[1];
    h[2]/=sum[2]; 
    for (int i=0;i<3;i++)
        h[i]=rd(h[i]); 
    return (int)(h[0] + candidate[0]*h[1] + candidate[1]*h[2]);
}