机器学习-组合方法

时间：2022-03-31 05:32:55

Ensemble methods（集成方法）

机器学习中的集成方法指结合若干个简单的基模型，最后得到一个相对复杂的预测模型。具体为对不同算法得到的结果通过某种方式集成在一起，或者对相同算法的参数组合在一起得到最后结果。常见的集成方法可分为平均方法（Average methods）和提升方法（Boost methods），本文对这两种方法做些简单介绍，主要对提升方法中的若干问题进行一些总结。

1. Average methods（平均方法）

这里主要以比赛中用到比较多的随机森林（Random Forests）进行介绍。随机森林在python中的sklearn.ensemble目录下，而在R中包名为randomForest。

主要思想是：首先对训练数据集有放回地行采样，再列采样即对特征采样，建立若干决策树。当有新的输入样本时，由这些决策树投票得到最后结果。因为其行列采样都是随机的，因此，一般情况下就算不剪枝也不会出现过拟合。

随机森林分类回归具体算法：
1. for （b = 1：B）：
(a) 通过自举法(bootstrap)在训练数据集中获得大小为N的样本Z。
(b) 根据自举法得到的数据建立树 Tb 。对树的每个节点递归地重复下面的步骤，直到到达最小节点数量 nmin ：
i. 在p个特征中随机选择m个特征。
ii. 在m个特征中选择最佳分裂特征。
iii. 把该节点分裂为两个子节点。
2. 输出组合树 [Tb]B1 .
预测：对一个新的输入点x
回归： f^Brf(x)=1/B∑Bb=1Tb(x) 。
分类：令 C^b(x) 为第b棵树的分类结果，则 C^rf(x)=多数表决[C^b(x)]B1

2. Boost methods（提升方法）

2.1 Adaboost算法

用于处理二分类问题。基本思想是：通过一系列的迭代，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值；加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

2.1.1 具体算法：

  1. 初始化训练数据的权值分布：
    D1=(w11,...,w1i,...,w1N),w1i=1/N,i=1,2,...,N
  2. for (m = 1:M):
    (a) 根据具有权值分布的训练数据 Dm 训练数据，得到基本分类器：
    Gm(x):x→{−1,+1}

    (b) 计算 Gm(x) 在训练数据集上的分类误差率：
    errm=∑i=1NwmiI(Gm(xi)≠yi)

    (c)计算 Gm(x) 的系数：
    αm=12log1−errmerrm

    (d) 更新训练数据集的权值分布：
    Dm+1=(wm+1,1,...wm+1,i,...,wm+1,N)

    wm+1,i=wmiexp(−αmyiGm(xi))∑Ni=1wmiexp(−αmyiGm(xi))
  3. 得到最终分类器：
    G(x)=sign(∑m=1MαmGm(x))

2.1.2 说明：

[1] 2(c)步表示该弱分类器在最终分类器中的重要性，误差越大， αm 越小；
[2] 2(d)步更新训练数据权重，增加正确分类样本的权重，降低误分类的权重；
[3] 3(c)弱分类器加权表决；
[4] 当2(a)中的基分类器为决策树时，即为提升树分类问题，可以看成损失函数为指数函数 L(y,f(x))=exp(−yf(x)) ，因此也可以用梯度提升解决。

2.1.3 Adaboost前向分布算法表示

Adaboost最终分类器可由加法模型表示：

f(x)=∑m=1MαmGm(x)

损失函数为指数损失函数：
L(y,f(x))=exp[−yf(x)]

求解目标函数，得到：
(αm,Gm(x))=argminα,G∑i=1Nexp[−yi(fm−1(xi)+αG(xi))]=argminα,G∑i=1Nw¯¯¯miexp[−yiαG(xi)]w¯¯¯mi=exp[−yifm−1(xi)]

求解 G∗m(x) :
L=∑i=1Nw¯¯¯miexp[−yiαG(xi)]=∑yi=Gm(xi)w¯¯¯mie−α+∑yi≠Gm(xi)w¯¯¯mieα=(eα−e−α)∑i=1Nw¯¯¯miI(yi≠G(xi))+e−α∑i=1Nw¯¯¯mi

所以，
G∗m(x)=argminG∑i=1Nw¯¯¯miI(yi≠G(xi))

对L中的 α 求偏导，得到：
α∗m=12log1−emem

em=∑Ni=1w¯¯¯miI(yi≠G(xi))∑Ni=1w¯¯¯mi

根据
fm(x)=fm−1(x)+αmGm(x)

w¯¯¯m+1,i=exp(−yifm(xi))

得到：
w¯¯¯m+1,i=w¯¯¯miexp[−yiαmGm(x)]

只是样本权值与Adaboost中只相差规范化因子，因此，两种表示方法等价。
即Adaboost模型可以看成是采用加法模型（基函数线性组合），损失函数为指数函数，学习算法为前向分布算法的二分类学习算法。

2.2 提升树

采用加法模型与前向分布算法，以决策树为基函数的提升方法称为提升树。最后输出表示为：

fM(x)=∑m=1MT(x;Θm)

Θm={Rjm,γjm)Jm1 为决策树的参数。
根据前向分布算法，第m步模型为：
fm(x)=fm−1(x)+T(x;Θm)

Θ^m=argminΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm))

γ^jm=argminγjm∑xi∈RjmL(yi,fm−1(xi)+γjm)

本文主要简单介绍指数损失函数的分类问题和平方损失的回归问题，后续工作介绍一般情况下的梯度提升。

2.2.1 分类

根据提升树的定义，若处理二分类问题，且损失函数是指数损失，则提升树是Adaboost算法的一种特殊情况，其基函数取的是分类树。

因此，根据Adaboost，若每次迭代生成的分类树输出 Tm∈{−1,+1} ，则每颗分类树优化目标：

最小化:  ∑i=1Nw¯¯¯miI(yi≠T(xi))

w¯¯¯mi=exp(−yifm−1(xi))

2.2.2 回归

当采用平方损失函数时，

L(y,f(x))=(y−f(x))2

即
L(y,fm−1(x)+T(x;Θm))=[y−fm−1(x)−T(x;Θm)]2=[r−T(x;Θm)]2

r表示当前模型拟合数据的残差，所以每迭代一次拟合当前的残差学习得到一个回归树 T(x;Θm) ，此时 γ^jm 即是对应在 Rjm 中样本点的残差的平均值。
更新：
fm(x)=fm−1(x)+T(X;Θm)

3. 总结

本文主要简单介绍了机器学习中的两种ensemble methods：average methods、 boost methods，代表性算法：随机森林，adaboost和提升树。其中利用提升树处理更一般的分类回归问题即GBDT算法将在后续工作中进行。

标签：

相关文章