机器学习-正则化（岭回归、lasso）和前向逐步回归

本文代码均来自于《机器学习实战》

这三种要处理的是同样的问题，也就是数据的特征数量大于样本数量的情况。这个时候会出现矩阵不可逆的情况，为什么呢？

矩阵可逆的条件是：1. 方阵 2. 满秩

X.t*X必然是方阵（nxmxmxn=nxn,最终行列数是原来的X矩阵的列数，也就是特征数),但是要满秩的话，由于线性代数的一个结论，X.t*X的秩不会比X大，而X的秩是样本数和特征数中较小的那一个，所以，如果样本数小于特征数的话，X.t*X就不会是可逆的。

遇到这种情况，我们可以采用正则化的方式或者剔除多余特征，这里我们介绍一些正则化的方式，例如岭回归、lasso，以及另外的一种方法：前向逐步回归

正则化

先解释一下这个词吧，毕竟这个词，每次听都感觉很玄妙的样子，但是也说不清到底哪里玄妙了。

唔，这里知乎有个答主写的很靠谱，把正则化的概念从头到尾撸了一遍。这里搬运一下：

所以从定义上来看，原本用来进行正则化的是0范数，但是由于计算困难，大家才转而使用2范数的。

岭回归

先贴一张《机器学习实战》的图哈

加入偏差：牺牲无偏性

加一点百度百科的数学性解释（感觉又回到了那个被数值分析支配的学期。。。）

知乎上有位答主说的很透，这里转一下:

所以具体实施其实挺简单的。但是注意，“为了使用岭回归和缩减技术，首先要对特征做标准化处理，使得每个维度的特征具有相同的重要性”,注意这里的“标准化”指的其实是Standardization，是改变了原有分布、变成均值为0方差为1的。具体可以看这篇博文：https://www.cnblogs.com/jiading/p/11575038.html

为什么要标准化，因为很明显，由文章最上面的议论我们可以看出来，在损失函数中加入二范数惩罚项是为了能将一些不必要的w设置为0，这才是岭回归的真正目的，而不仅仅是为X.t/*X“撑场子”保证其可逆。所以，我们可以想象，如果不标准化的话，一些y_i会变的非常大，那么通过公式，我们就很难将这些项对应的w设置为0，而它们却是有可能是不相关的。所以，我们必须让每一项都有一样的“重要性”。使用Standardization之后，连每个特征的样本分布都给你整一样的了，这才是真正的“泯然众人矣”。

特征的值的大小不重要，我们看的关键是它是否和我们要回归的量相关

岭回归的代码其实比较简单：

#岭回归
def ridgeRegres(xMat,yMat,lam=0.2):
    xTx = xMat.T*xMat
    denom = xTx + eye(shape(xMat)[1])*lam
    if linalg.det(denom) == 0.0:
        print ("This matrix is singular, cannot do inverse")
        return
    ws = denom.I * (xMat.T*yMat)
    return ws
#岭回归的测试函数
def ridgeTest(xArr,yArr):
    xMat = mat(xArr); yMat=mat(yArr).T
    yMean = mean(yMat,0)
    #数据必须先标准化，才能进行正则化
    yMat = yMat - yMean     #to eliminate X0 take mean off of Y
    #regularize X's
    xMeans = mean(xMat,0)   #calc mean then subtract it off
    xVar = var(xMat,0)      #calc variance of Xi then divide by it
    xMat = (xMat - xMeans)/xVar
    numTestPts = 30
    wMat = zeros((numTestPts,shape(xMat)[1]))
    for i in range(numTestPts):
        #让λ以指数级变换，只是为了看λ很小和很大的时候对结果的影响
        ws = ridgeRegres(xMat,yMat,exp(i-10))
        wMat[i,:]=ws.T
    return wMat 

这张图非常好！它直观地体现了上面说的正则化对w的惩罚作用：当λ设置较大的时候，几乎所有的参数都被惩罚到了接近0的地步，注意是接近0但不是0！

为什么不是0，这一点留到下面讲lasso的时候对比着说比较清楚

lasso

lasso和岭回归的唯一区别就是将使用的二范数换成了一范数。但是再引出lasso的公式之前，我们需要先把岭回归的公式修改一下：

这里借用了知乎少整酱的回答中的公式（https://zhuanlan.zhihu.com/p/30535220）

同学们，这里用到的是什么啊？用到的就是拉格朗日乘子法和KKT条件啊，下面的就是不等式约束，把t往左边一挪，就是熟悉的不等式约束的形式了。只不过那个t我们没有在代价函数里面体现，但是这也没什么影响，因为代价函数一求偏导数这些常数就都没有了。

那么类似的，lasso方法只是将上面的公式修改为了：

也就是用了一范数，但就是这一个范数的差别就造成了很大的不同：

而对于lasso方法，则是会让一些系数真的为0.这一点从几何上比较好解释，这里再借用一下知乎少整酱的回答：

是不是说的特别清楚！

看到这里，同学可能有疑问了：那不能用梯度下降法，为什么不用正规方程法呢？因为正规方程法也是基于求导的呀，忘了的同学看下图（来源：https://blog.csdn.net/qq_36523839/article/details/82931559）

所以只能用坐标下降法。

https://zhuanlan.zhihu.com/p/30535220上有具体的坐标下降法的方法和python实现，我就不转了，主要是我也懒得学了2333，（据说）比它更方便的前向逐步回归可以得到和它类似的效果，那这个就不看了。

前向逐步回归

这个算法听着挺玄乎，其实看代码就知道，是属于比较无脑和暴力的方法，效率不会太高。当然实现起来是真的简单。

代码：

'''
Created on Jan 8, 2011

@author: Peter
'''
from numpy import *
#加载数据
def loadDataSet(fileName):      #general function to parse tab -delimited floats
    #attribute的个数
    numFeat = len(open(fileName).readline().split('\t')) - 1 #get number of fields
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr =[]
        curLine = line.strip().split('\t')
        for i in range(numFeat):
            lineArr.append(float(curLine[i]))
        #dataMat是一个二维矩阵，labelMat是一维的
        dataMat.append(lineArr)
        labelMat.append(float(curLine[-1]))
    return dataMat,labelMat
def rssError(yArr,yHatArr): #yArr and yHatArr both need to be arrays
    return ((yArr-yHatArr)**2).sum()
def regularize(xMat):#regularize by columns
    inMat = xMat.copy()
    inMeans = mean(inMat,0)   #calc mean then subtract it off
    inVar = var(inMat,0)      #calc variance of Xi then divide by it
    inMat = (inMat - inMeans)/inVar
    return inMat
#前向逐步线性回归，目的是输出线性回归的weight
def stageWise(xArr,yArr,eps=0.01,numIt=100):
    #eps是每次迭代的步长，numIt是迭代的次数
    xMat = mat(xArr); yMat=mat(yArr).T
    yMean = mean(yMat,0)
    #标准化,x的标准化使用的是Z-score Normalization，其实是Standardization，改变了原有分布的
    yMat = yMat - yMean     #can also regularize ys but will get smaller coef
    xMat = regularize(xMat)
    #m是样本个数，n是特征数
    m,n=shape(xMat)
    #保存每次迭代之后的结果，测试时候显示迭代过程用的，真正使用的时候只要最后一次就好了
    returnMat = zeros((numIt,n)) #testing code remove
    #初始的时候所有的weights置为0
    ws = zeros((n,1)); wsTest = ws.copy(); wsMax = ws.copy()
    for i in range(numIt):
        print (ws.T)#输出现在的weight
        lowestError = inf;
        #对每个变量的系数进行尝试
        for j in range(n):
            #注意这里不是在-1到1的范围内遍历，而是遍历数组，这个数组中有-1和1两个元素
            for sign in [-1,1]:
                wsTest = ws.copy()
                #改变一个变量的值，或者加上一个步长，或者减去一个步长
                wsTest[j] += eps*sign
                yTest = xMat*wsTest
                #计算误差
                rssE = rssError(yMat.A,yTest.A)
                if rssE < lowestError:
                    #如果误差比最小误差小，这个weight的“配方”就留下了
                    lowestError = rssE
                    wsMax = wsTest
        #最后留下那个最大的weight的配方
        ws = wsMax.copy()
        returnMat[i,:]=ws.T
    return returnMat