机器学习--02算法--03Lasso回归算法（Lasso Regression Algorithm）_lasso algorithm

Lasso回归是线性回归的变种，在代价函数后添加L1范数。

一、引言

LASSO的完整名称叫最小绝对值收敛和选择算子算法（least absolute shrinkage and selection operator）。

二、模型介绍

先来回顾一下岭回归的代价函数，在原来标准线性回归代价函数上加上了一个带惩罚系数 λ 的 w 向量的 L2-范数的平方：
$$\mathrm{Cost}(w)=\sum _{i=1}^N{\left(y_i-w^T{x}_i\right)}^2+\lambda \Vert w{\Vert }_2^2$$
Lasso回归算法也同岭回归一样加上了正则项，只是改成加上了一个带惩罚系数 λ 的 w 向量的 L1-范数作为惩罚项（L1-范数的含义为向量 w 每个元素绝对值的和），所以这种正则化方式也被称为L1正则化。
$$\mathrm{Cost}(w)=\sum _{i=1}^N{\left(y_i-w^T{x}_i\right)}^2+\lambda \Vert w{\Vert }_1$$
同样是求使得代价函数最小时 w 的大小：
$$w=\underset{w}{\mathrm{argmin}}\left(\sum _{i=1}^N{\left(y_i-w^T{x}_i\right)}^2+\lambda \Vert w{\Vert }_1\right)$$
由于加入的是向量的 L1-范数，其中存在绝对值，导致其代价函数不是处处可导的，所以就没办法通过直接求导的方式来直接得到 w 的解析解。下面介绍两种求解权重系数 w 的方法：坐标下降法（coordinate descent）、最小角回归法（Least Angle Regression，LARS）

三、算法步骤

坐标下降法：
  坐标下降法的核心与它的名称一样，就是沿着某一个坐标轴方向，通过一次一次的迭代更新权重系数的值，来渐渐逼近最优解。

具体步骤：
（1）初始化权重系数 w，例如初始化为零向量。
（2）遍历所有权重系数，依次将其中一个权重系数当作变量，其他权重系数固定为上一次计算的结果当作常量，求出当前条件下只有一个权重系数变量的情况下的最优解。

（3）步骤（2）为一次完整迭代，当所有权重系数的变化不大或者到达最大迭代次数时，结束迭代。

如上图所示，每次迭代固定其他的权重系数，只朝着其中一个坐标轴的方向更新，最后到达最优解。
**最小角回归法（Least Angle Regression，LARS）**解释略，详见机器学习算法系列（五）- Lasso回归算法（Lasso Regression Algorithm）

四、代码实现

1. 使用 Python 实现Lasso回归算法（坐标下降法）：

注：本实现未考虑偏移量 b ，需要对特征进行归一化处理

def lassoUseCd(X, y, lambdas=0.1, max_iter=1000, tol=1e-4):
    """
    Lasso回归，使用坐标下降法（coordinate descent）
    args:
        X - 训练数据集
        y - 目标标签值
        lambdas - 惩罚项系数
        max_iter - 最大迭代次数
        tol - 变化量容忍值
    return:
        w - 权重系数
    """
    # 初始化 w 为零向量
    w = np.zeros(X.shape[1])
    for it in range(max_iter):
        done = True
        # 遍历所有自变量
        for i in range(0, len(w)):
            # 记录上一轮系数
            weight = w[i]
            # 求出当前条件下的最佳系数
            w[i] = down(X, y, w, i, lambdas)
            # 当其中一个系数变化量未到达其容忍值，继续循环
            if (np.abs(weight - w[i]) > tol):
                done = False
        # 所有系数都变化不大时，结束循环
        if (done):
            break
    return w

def down(X, y, w, index, lambdas=0.1):
    """
    cost(w) = (x1 * w1 + x2 * w2 + ... - y)^2 + ... + λ(|w1| + |w2| + ...)
    假设 w1 是变量，这时其他的值均为常数，带入上式后，其代价函数是关于 w1 的一元二次函数，可以写成下式：
    cost(w1) = (a * w1 + b)^2 + ... + λ|w1| + c (a,b,c,λ 均为常数)
    => 展开后
    cost(w1) = aa * w1^2 + 2ab * w1 + λ|w1| + c (aa,ab,c,λ 均为常数)
    """
    # 展开后的二次项的系数之和
    aa = 0
    # 展开后的一次项的系数之和
    ab = 0
    for i in range(X.shape[0]):
        # 括号内一次项的系数
        a = X[i][index]
        # 括号内常数项的系数
        b = X[i][:].dot(w) - a * w[index] - y[i]
        # 可以很容易的得到展开后的二次项的系数为括号内一次项的系数平方的和
        aa = aa + a * a
        # 可以很容易的得到展开后的一次项的系数为括号内一次项的系数乘以括号内常数项的和
        ab = ab + a * b
    # 由于是一元二次函数，当导数为零时，函数值最小值，只需要关注二次项系数、一次项系数和 λ
    return det(aa, ab, lambdas)

def det(aa, ab, lambdas=0.1):
    """
    通过代价函数的导数求 w，当 w = 0 时，不可导
    det(w) = 2aa * w + 2ab + λ = 0 (w > 0)
    => w = - (2 * ab + λ) / (2 * aa)

    det(w) = 2aa * w + 2ab - λ = 0 (w < 0)
    => w = - (2 * ab - λ) / (2 * aa)

    det(w) = NaN (w = 0)
    => w = 0
    """
    w = - (2 * ab + lambdas) / (2 * aa)
    if w < 0:
        w = - (2 * ab - lambdas) / (2 * aa)
        if w > 0:
            w = 0
    return w
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

2. sklearn实现

from sklearn.linear_model import Lasso

# 初始化Lasso回归器，默认使用坐标下降法
reg = Lasso(alpha=0.1, fit_intercept=False)
# 拟合线性模型
reg.fit(X, y)
# 权重系数
w = reg.coef_
1
2
3
4
5
6
7
8

五、代码解释

————————————————————————————————————————————

六、选择

那么，到底如何选用线性回归、岭回归、 Lasso回归和弹性网络
呢？通常来说，有正则化——哪怕是很小，总是比没有更可取一些。
所以大多数情况下，你应该避免使用纯线性回归。岭回归是个不错的
默认选择，但是如果你觉得实际用到的特征只有少数几个，那就应该
更倾向于Lasso回归或是弹性网络，因为它们会将无用特征的权重降
为零。一般而言，弹性网络优于Lasso回归，因为当特征数量超过训
练实例数量，又或者是几个特征强相关时， Lasso回归的表现可能非
常不稳定。