集成算法
发表评论
1199 views

1 集成学习概述

核心思想：三个臭皮匠顶个诸葛亮

集成学习三步走

  1. 特征抽取
  2. 反复建模（弱学习器）
  3. 模型集成（强学习器）

1.1 模型集成的策略

1.1.1 平均法

最终的预测输出 = 若干个弱学习器的预测输出的平均

1.1.2 投票法

最终的预测输出 = 若干个弱学习器的预测输出的投票结果

  • 常见的几种投票法
  • 相对多数投票法：少数服从多数
  • 绝对多数投票法：票数过半才算数
  • 加权投票法：厉害的“弱”学习器一票更比六票强
1.1.3 学习法

代表方法是stacking：把若干个弱学习器的预测结果作为输入再训练一个模型（套娃）

#集成学习 #平均法 #投票法 #学习法 #stacking

2 boosting

boosting算法流程：

  • 从训练集用初始权重训练出一个弱学习器1
  • 根据弱学习器的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。
  • 然后基于调整权重后的训练集来训练弱学习器2，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

2.1 Adaboost

Adaboost的算法流程和boosting是基本一致的，不过相比于boosting，Adaboost对于学习误差率的计算、样本权重的更新和弱学习器的集合策略进行了更为清晰细致的描述：

设训练集样本为$T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$

设第K个弱学习器的样本权重为$\left(w_{k1},w_{k2},...,w_{kn}\right)$

初始化样本权重：$w_{1i}=\frac{1}{n},i=1,2,...,n$

2.1.1 分类问题的算法细节

第k个弱分类器$G_k(x)$在训练集上的分类误差率： $$e_k=P(G_k(x_i)\neq y_i)=\Sigma_{i=1}^nw_{ki}I(G_k(x_i)\neq y_i)$$

第k个弱分类器$G_k(x)$的权重： $$\alpha_k=\frac{1}{2}log(\frac{1-e_k}{e_k})$$

  • 分类误差率越大，弱分类器越不可靠，相应权重也就越低

第K个弱学习器的样本权重的更新： $$w_{k+1,i}=\frac{w_{ki}}{Z_k}exp(-\alpha_ky_iG_k(x_i))$$

  • 其中$Z_k$为规范化因子，$Z_k=\Sigma_{i=1}^nexp(-\alpha_ky_iG_k(x_i))$
  • 当第$i$个样本分类错误时，$y_iG_k(x_i)<0$，此样本的权重增大，反之则减少

弱学习器通过加权的方式进行策略的集合： $$final\model(x)=sign(\Sigma\{i=1}^n\alpha_kG_k(x))$$

2.1.2 回归问题的算法细节

第k个弱分类器$G_k(x)$在训练集上的最大误差： $$E_k=max|y_i-G_k(x_i)|,i=1,2,...,n$$

第k个弱分类器$G_k(x)$每个样本的相对误差：

  • 如果是线性误差，则$e_{ki}=\frac{|y_i-G_k(x_i)|}{E_k}$
  • 如果是平方误差，则$e_{ki}=\frac{|y_i-G_k(x_i)|^2}{E_k^2}$
  • 如果是指数误差，则$e_{ki}=1-exp(\frac{-|y_i-G_k(x_i)|}{E_k})$

第k个弱分类器$G_k(x)$在训练集上的分类误差率： $$e_k=\Sigma_{i=1}^nw_{ki}e_{ki}$$

第k个弱分类器$G_k(x)$的权重： $$\alpha_k=\frac{1-e_k}{e_k}$$

第K个弱学习器的样本权重的更新： $$w_{k+1,i}=\frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}$$

  • 其中$Z_k$为规范化因子，$Z_k=\Sigma_{i=1}^nw_{ki}\alpha_k^{1-e_{ki}}$

弱学习器通过加权的方式进行策略的集合： $$final\model(x)=\Sigma\{k=1}^Kln(\frac{1}{\alpha_k})g(x)$$

  • 取$k=1,2,...,K\text{时, }ln(\frac{1}{\alpha_k})$的中位数所对应的$k^{\ast}$值，$g(x)=G_{k^{\ast}}(x)$
2.1.3 损失函数优化

Adaboost的特性

  • 加法模型，最终的强分类器是若干个弱分类器加权平均而得到的
  • 前向分步学习算法，通过一轮轮的弱学习器学习，利用前一个强学习器的结果和当前弱学习器来更新当前的强学习器的模型，实现更强的模型性能。
  • 如果说第k-1轮的强学习器为$f_{k-1}(x)=\Sigma_{i=1}^{k-1}\alpha_iG_i(x)$，则第k轮的强学习器为$f_{k}(x)=f_{k-1}(x)+\alpha_kG_k(x)$
  • 损失函数为指数函数：$argmin{\alpha,G}\Sigma_{i=1}^nexp(-y_if_k(x))$
  • 值得一提的是，损失函数对$\alpha$进行求导并化简后，就可以推导出弱分类器$G_k(x)$的权重公式和样本权重的更新公式

加入正则项：

  • $f_{k}(x)=f_{k-1}(x)+\alpha_kG_k(x)$将转变为$f_{k}(x)=f_{k-1}(x)+v\alpha_kG_k(x)$
  • 其中$v$表示学习速率，取值范围在$[0,1]$之间，较小的取值对应着更多的迭代次数
  • 学习速率和迭代最大次数将共同决定算法的拟合效果
2.1.4 Adboost 总结

理论上任何学习器都可以作为弱学习器用于Adboost

最常见的弱学习器是决策树，对于分类问题，Adaboost使用CART分类树作为弱学习器，而对于回归问题Adaboost使用CART回归树作为弱学习器

Adboost优点

  • Adaboost作为分类器时，分类精度很高
  • 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活
  • 作为简单的二元分类器时，构造简单，结果可理解
  • 不容易发生过拟合
  • 权重更新时候的加速计算技巧

Adboost缺点

  • 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的预测准确性

2.2 提升树（Boosting Decision Tree）

残差 = 真实值 - 预测值

提升树的核心思想是在迭代中不断地拟合残差，形成新的弱学习器（决策树）

提升树即是整个迭代过程生成的决策树（分类树或回归树）的累加

而GBDT与提升树最大的区别就在于GBDT采用损失函数的负梯度来作为残差的近似值

提升树算法流程：

  • 根据数据集$(X,y)$拟合决策树得到模型$f_0(x)$
  • 计算残差$r_0=y-f_0(x)$，并根据数据集$(X,r_0)$拟合得到模型$f_1(x)$
  • 计算残差$r_1=y-f_1(x)$，并根据数据集$(X,r_1)$拟合得到模型$f_2(x)$
  • 重复以上过程，直到残差无明显变化或达到指定的最大迭代次数
  • 迭代最终得到$M$个弱学习器，而提升树模型$final_model(x)=\Sigma_{m=1}^Mf_m(x)$

注：关于提升树的一些计算细节，可参考GBDT中的内容

2.3 GBDT

GBDT全称为Gradient Boosting Decison Tree。

GBDT有很多简称，有GBT（Gradient Boosting Tree）, GTB（Gradient Tree Boosting ）， GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其实都是指的同一种算法，本文统一简称GBDT。

GBDT使用了类似于Adboost的前向分步算法进行算法的迭代，但是GBDT的弱学习器限定为CART回归树模型，同时迭代思路和Adaboost也有所不同。

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是$f_{t−1}(x)$, 损失函数是$L(y,f_{t−1}(x))$, 每次迭代的目标是找到一个CART回归树模型的弱学习器h\_t(x)，让本轮的损失函数$L(y,f_t(x))=L(y,f_{t−1}(x)+h_t(x))$最小。也就是说，每次拟合得到的CART树都是为了让最终模型的损失尽量变得更小。

2.3.1 GBDT的负梯度拟合

GBDT的核心问题在于如何拟合损失函数

Freidman提出了用损失函数的负梯度来作为本轮残差的近似值，进而拟合一个CART回归树

第$t$轮的第$i$个样本的损失函数的负梯度 $$r_{ti}=[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{t-1}(x)}$$

把负梯度作为残差的估计值拟合新的CART回归树

新的CART回归树所对应的叶子节点区域为$R_{tj},j=1,2,...,J$（叶子节点总数为$J$）

然后以损失函数最小为原则，使用线性搜索的方法确定每个叶子节点的输出值$c_{tj}$ $$c_{tj}=argmin(c)\Sigma_{x_i\in R_{tj}}L(y_i,f_{t-1}(x_i)+c)$$

GBDT的弱学习器结合策略是一个加法过程

新强学习器的预测值=旧强学习器的预测值+新CART回归树的输出值（修正值）

本轮最终得到的强学习器表达式如下： $$f_t(x)=f_{t-1}(x)+h_t(x)=f_{t-1}(x)+\Sigma_{j=1}^Jc_{tj}I(x\in R_{tj})$$

2.3.2 GBDT回归算法

GBDT算法流程

  • 初始化强学习器$f_0(x)=argmin(c)\Sigma_{i=1}^nL(y_i,c)$，其中$n$表示样本数
  • 计算 $f_0(x)$ 负梯度并拟合新的 CART 回归树，并计算每个叶子节点的最佳输出值 $c_{1j}$
  • 更新强学习器$f_1(x)=f_{0}(x)+\Sigma_{j=1}^Jc_{1j}I(x\in R_{tj})$
  • 计算 $f_1(x)$ 负梯度并拟合新的 CART 回归树，并计算每个叶子节点的最佳输出值 $c_{2j}$
  • 更新强学习器 $f_2(x)=f_{1}(x)+\Sigma_{j=1}^Jc_{2j}I(x\in R_{tj})$
  • 重复以上过程，直到迭代次数达到最大值 $T$
  • 最终强学习器$f(x)=f_T(x)=f_{0}(x)+\Sigma_{t=1}^T\Sigma_{j=1}^Jc_{tj}I(x\in R_{tj})$
2.3.3 GBDT分类算法

由于GBDT的弱学习器限定为CART回归树模型

所以GBDT的输出值为连续值，需要转换为离散值

GBDT从回归到分类，主要有两个方法

  • 一个是用指数损失函数，此时GBDT退化为Adaboost算法
  • 另一种方法是用类似于逻辑回归的对数似然损失函数的方法

对数似然损失函数

  • 对于二分类问题，可以采用logistic函数的对数化作为损失函数
  • 对于多分类问题，可以采用softmax函数的对数化作为损失函数
  • 使用对数似然损失函数时，$c_{tj}$的计算较为复杂，需要用近似值代替（具体推导详见梯度提升树(GBDT)原理小结
2.3.4 GBDT的正则化

3 种常见的 GBDT 的正则化方法

  • 方法一：添加学习速率的正则项，详见损失函数优化
  • 方法二：在进行拟合CART回归树时进行样本采样（不放回），使用子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)
  • 方法三：对树进行正则化剪枝，详见CART的剪枝
2.3.5 GBDT总结

GBDT优点：

  • 可以灵活处理各种类型的数据，包括连续值和离散值
  • 相对于SVM模型调参较少，且预测的准确率也比较高
  • 特定的损失函数对异常值的鲁棒性非常强，如Huber损失函数和Quantile损失函数

GBDT缺点：

  • 弱学习器之间存在依赖关系，难以并行训练数据（SGBT可以实现部分并行）

#boosting #Adboost #提升树 #GBDT

3 bagging

bagging算法流程：

  • 通过T次的随机采样（多为自助法），得到T个采样数据集
  • 对于这T个采样数据集，分别独立的训练出T个弱学习器
  • 如果是分类算法预测，则T个弱学习器投票选择得票数最多的类别作为最终类别
  • 如果是回归算法预测，将T个弱学习器得到的回归结果的平均值作为最终的模型输出

3.1 随机森林

随机森林是bagging的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。

3.1.1 随机森林的思路

随机森林算法流程：

  • 对数据集进行随机采样(一般为自助法)，得到采样训练集$D_1$
  • 基于$D_1$训练CART决策树模型$G_1(x)$，在训练树的节点时，对特征进行采样，并从中选择最优的特征作为左右子树的划分依据
  • 重复以上过程，直到训练出 $T$ 个弱学习器（CART 决策树）
  • 如果是分类算法预测，将投票选择得票数最多的类别作为随机森林的预测类别
  • 如果是回归算法预测，将多个弱学习器结果的平均值作为随机森林的模型输出
3.1.2 袋外误差

随机森林训练时对样本的采样都是随机且有放回的（自助法），因此在训练某棵树时，会出现没有被采样到的样本，这些样本称为该棵树的袋外数据(Out Of Bag，OOB)。

袋外错误率（oob err）的计算过程：

  • 对于每个样本，计算它作为某棵树的袋外数据时该树对它的预测结果
  • 对于多次作为袋外数据的样本，通过投票法或简单平均法得出该样本的袋外预测结果
  • 根据所有样本的袋外预测结果及其真实结果，计算出预测错误率

袋外错误率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证

3.1.3 特征重要性

随机森林主要有两种方法用于评估特征的重要性

  1. Mean decrease impurity 不纯度降低

    • 以GINI系数为例，遍历所有树中特征A出现过的节点
    • 计算节点处的GINI系数变化$\Delta Gini$（即特征A对于不纯度的降低能力）
    • 每个特征都进行GINI系数变化的汇总求和$\Sigma \Delta Gini$
    • 对所有特征的$\Sigma \Delta Gini$进行归一化处理，得到每个特征的重要性

  2. Mean decrease accuracy 准确度降低

    • 对每棵树通过OOB样本计算预测误差$Error1$
    • 随机扰动OOB样本中的特征A，再计算每棵树的预测误差$Error2$
    • $Error1-Error2$就刻画了特征A的重要性

随机扰动的两种方法

  • 使用平均分布或高斯分布得到的随机值替代
  • 对特征所在列进行随机打乱（更科学，因为扰动）
3.1.4 随机森林的推广
3.1.4.1 ExtraTrees

ExtraTrees VS 随机森林：

  • ExtraTrees是RF的一个变种，原理基本是一致的
  • ExtraTrees不对训练集进行采样，每次训练CART决策树都用完整的数据集
  • ExtraTrees在训练树的过程中，不进行最优特征的选择，而是随机选择一个特征
  • 相比于随机森林，ExtraTrees一般规模更大，泛化性更好
3.1.4.2 Totally Random Trees Embedding

Totally Random Trees Embedding(以下简称 TRTE)是一种非监督学习的数据转化方法。它将低维的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。

TRTE在数据转化的过程也使用了类似于RF的方法，建立T个决策树来拟合数据。当决策树建立完毕以后，数据集里的每个数据在T个决策树中叶子节点的位置也定下来了。

比如我们有3颗决策树，每个决策树有5个叶子节点，某个数据特征x划分到第一个决策树的第2个叶子节点，第二个决策树的第3个叶子节点，第三个决策树的第5个叶子节点。则x映射后的特征编码为(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15维的高维特征。（这里特征维度之间加上空格是为了强调三颗决策树各自的子编码）

映射到高维特征后，可以继续使用监督学习的各种分类回归算法了。

3.1.4.3 Isolation Forest

Isolation Forest（以下简称IForest）是一种异常点检测的方法。

IForest VS 随机森林

  • IForest会对训练集进行随机采样，但是采样个数相比于RF要少很多，因为异常点检测只需要部分的样本就可以将异常点区别出来了。
  • IForest在训练树的过程中会随机选择一个划分特征，然后对划分特征随机选择一个划分阈值。这点也和RF不同。
  • IForest一般会选择一个比较小的最大决策树深度max_depth，原因同样本采集。

IForest 异常点检测过程：

  • IForest将测试样本点$x$带入训练好的$T$颗决策树
  • 计算该样本在每颗决策树上的叶子节点的深度$h_t(x)$，然后得出平均高度$h(x)$
  • 然后用下面的公式计算样本点$x$的异常概率：

$$s(x,n)=2^{-\frac{h(x)}{c(n)}}$$

  • $n$表示样本数，$c(n)=2ln(n-1)+\xi -2\frac{n-1}{n}$，$\xi$表示欧拉常数
  • $s(x,n)$的取值范围是$[0,1]$,取值越接近于$1$，则是异常点的概率也越大
3.1.5 随机森林总结

随机森林优点：

  • 可以高度并行化训练，大量样本的训练有速度优势
  • 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型
  • 在训练后，可以给出各个特征对于输出的重要性
  • 由于采用了随机采样，训练出的模型的方差小，泛化能力强
  • 相对于 Boosting 系列的 Adaboost 和 GBDT， RF 实现比较简单
  • 对部分特征缺失不敏感。

随机森林缺点：

  • 在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
  • 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

#bagging #随机森林

4 参考

集成学习原理小结
Bagging与随机森林算法原理小结
集成学习之Adaboost算法原理小结
梯度提升树(GBDT)GBDT原理小结

往年同期文章