集成学习

2018-03-26

个体与集成

“同质”：由类型相同的学习器组合而成的集成学习器，每个学习器可称为基学习器
“异质”：由类型不相同的学习器组合而成的集成学习器，每个学习器可称为“组件学习器”
集成学习通过将多个学习器进行结合，常常可以获得比单一学习器具有显著优越的泛化性能。这个对于弱学习器尤为明显。
如何获得一个好的集成学习器呢？每个个体学习器具有一定的准确性（每个学习器不能太坏）和多样性（每个学习器之间存在差异）
集成学习方法可以分为两大类：一是个体学习器间存在强依赖关系、必须串行生成序列化方法，代表有Boosting算法，二是个体学习器之间不存在强依赖关系、可同时生成的并行化方法，代表有Bagging和随机森林（Random Forest）

Bagging与随机森林

Bagging算法

Bagging算法基本流程：采用自助采样法，可以采用出个含个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。

随机森林（Random Forest）

随机森林是Bagging的一个扩展变体，随机森林是在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体的说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有个属性）中选择一个最优属性；而在随机森林（RF）中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含个属性的子集，然后再从这个子集中选择一个最优属性用于划分。
可以参阅：http://www.cnblogs.com/hrlnw/p/3850459.html

采样方式

随机森林的集成学习方法是Bagging， Bagging的采样方式为：
- Bootstraping：有放回的采样
随机森林即随机采样样本，也随机选择特征，因此防止过拟合能力更强，降低方差。

构建方法

构建多颗决策树，结果是所有的决策树共同决定的。对于分类任务可以取出现最多，回归操作可以取均值。

随机性的体现

数据选择随机性：n个样本中，采集60%的样本个数的集合作为数据，去除异常样本影响。
特征随机性：在d个特种中，随机选择其中一些特征。

随机森林的推广(Extra Trees)

extra trees是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：

1）对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。

2）在选定了划分特征后，RF的决策树会基于信息增益，基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。

从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是bias相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好

GBDT (Gradient Boosting Decision Tree)

gbdt的基本原理是boost 里面的 boosting tree（提升树），并使用 gradient boost。
GBDT中的树都是回归树，不是分类树，因为gradient boost 需要按照损失函数的梯度近似的拟合残差，这样拟合的是连续数值，因此只有回归树。

　GB算法中最典型的基学习器是决策树，尤其是CART，正如名字的含义，GBDT是GB和DT的结合。要注意的是这里的决策树是回归树，GBDT中的决策树是个弱模型，深度较小一般不会超过5，叶子节点的数量也不会超过10，对于生成的每棵决策树乘上比较小的缩减系数（学习率<0.1），有些GBDT的实现加入了随机抽样$（subsample 0.5<=f <=0.8）$提高模型的泛化能力。通过交叉验证的方法选择最优的参数。因此GBDT实际的核心问题变成怎么基于${(x_i, r_{im})}_{i=1}^n$使用CART回归树生成$! h_m(x)？$

CART分类树在很多书籍和资料中介绍比较多，但是再次强调GDBT中使用的是回归树。作为对比，先说分类树，我们知道CART是二叉树，CART分类树在每次分枝时，是穷举每一个feature的每一个阈值，根据GINI系数找到使不纯性降低最大的的feature以及其阀值，然后按照feature<=阈值，和feature>阈值分成的两个分枝，每个分支包含符合分支条件的样本。用同样方法继续分枝直到该分支下的所有样本都属于统一类别，或达到预设的终止条件，若最终叶子节点中的类别不唯一，则以多数人的类别作为该叶子节点的性别。回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是GINI系数，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

xgboost

XGBoost比GBDT好的地方：
二阶泰勒展开
节点分数惩罚正则
增益计算不同，GBDT是gini，xgb是优化推导公式
一步一步理解GB、GBDT、xgboost
upload successful

Boosting

Boosting算法是一族可以将弱学习器提升为强学习器的算法。
Boosting工作原理：先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的的训练样本在后续受到更多的关注，然后基于调整后的样本分布训练下一个基学习器，如此重复进行，知道基学习器数目达到事先指定的值，最终将这个基学习器进行加权结合。这种算法最具有代表的是AdaBoost算法。
AdaBoost算法可以理解是基于“加性模型”，即基学习器的线性组合。

Adaboost

（Adaptive Boosting自适应增强）适应性在于：前一个基本分类器的赝本会得到加强，加权后全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到每个预定的足够小的错误率或者达到预先设定的最大迭代次数。
upload successful
从图中可以看到，在训练过程中我们需要训练出多个弱分类器（图中为3个），每个弱分类器是由不同权重的样本（图中为5个训练样本）训练得到（其中第一个弱分类器对应输入样本的权值是一样的），而每个弱分类器对最终分类结果的作用也不同，是通过加权平均输出的，权值见上图中三角形里面的数值。那么这些弱分类器和其对应的权值是怎样训练出来的呢？
下面通过一个例子来简单说明。
书中（machine learning in action）假设的是5个训练样本，每个训练样本的维度为2，在训练第一个分类器时5个样本的权重各为0.2. 注意这里样本的权值和最终训练的弱分类器组对应的权值α是不同的，样本的权重只在训练过程中用到，而α在训练过程和测试过程都有用到。
现在假设弱分类器是带一个节点的简单决策树，该决策树会选择2个属性（假设只有2个属性）的一个，然后计算出这个属性中的最佳值用来分类。损失函数中正则化项为$Ω(f_t)=γT+\frac{λ}{2}\sum_{j=1}^Tω_i^2$，叶子的个数+w的L2模平方
Adaboost的简单版本训练过程如下：

训练第一个分类器，样本的权值D为相同的均值。通过一个弱分类器，得到这5个样本（请对应书中的例子来看，依旧是machine learning in action）的分类预测标签。与给出的样本真实标签对比，就可能出现误差(即错误)。如果某个样本预测错误，则它对应的错误值为该样本的权重，如果分类正确，则错误值为0. 最后累加5个样本的错误率之和，记为ε。
通过ε来计算该弱分类器的权重α，公式如下：
$α=\frac{1}{2}ln(\frac{1-ε}{ε})$
通过α来计算训练下一个弱分类器样本的权重D，如果对应样本分类正确，则减小该样本的权重，公式为：
$D_i^{t+1}=\frac{D_i^{(t)}e^{-α}}{Sum(D)}$
如果样本分类错误，则增加该样本的权重，公式为：
$D_i^{t+1}=\frac{D_i^{(t)}e^α}{Sum(D)}$
循环步骤1,2,3来继续训练多个分类器，只是其D值不同而已。
测试过程如下：
输入一个样本到训练好的每个弱分类中，则每个弱分类都对应一个输出标签，然后该标签乘以对应的α，最后求和得到值的符号即为预测标签值。

结合策略

如何使结合后的集成算法明显的优势呢？也就是说如何将训练出来的多个基学习器如何很好的结合在一起呢形成新的集成算法呢？主要有平均法、投票法、学习法三种结合策略。

Voting

投票制即为，投票多者为最终的结果。例如一个分类问题，多个模型投票（当然可以设置权重）。最终投票数最多的类为最终被预测的类。

Averaging

Averaging即所有预测器的结果平均。
回归问题，直接取平均值作为最终的预测值。（也可以使用加权平均）
分类问题，直接将模型的预测概率做平均。（or 加权）
加权平均，其公式如下：
$$\sum_{i=1}^n Weight_i∗P_i$$
其中nn表示模型的个数， $Weight_i$表示该模型权重，$P_i$表示模型i的预测概率值。
例如两个分类器，XGBoost（权重0.4）和LightGBM（权重0.6），其预测概率分别为：0.75、0.5，那么最终的预测概率，(0.4 0.75+0.6 0.5)/(0.4+0.6)=0.6
模型权重也可以通过机器学习模型学习得到

Ranking

Rank的思想其实和Averaging一致，但Rank是把排名做平均，对于AUC指标比较有效。
个人认为其实就是Learning to rank的思想，可以来优化搜索排名。具体公式如下：
$$\sum_{i=1}^n \frac{Weight_i}{Rank_i}$$
其中nn表示模型的个数， WeightiWeighti表示该模型权重，所有权重相同表示平均融合。RankiRanki表示样本在第i个模型中的升序排名。它可以较快的利用排名融合多个模型之间的差异，而不需要加权融合概率。

Binning

将单个模型的输出放到一个桶中。参考pdf paper

Bagging

使用训练数据的不同随机子集来训练每个 Base Model，最后每个 Base Model 权重相同，分类问题进行投票，回归问题平均。
随机森林就用到了Bagging，并且具有天然的并行性。

Boosting

Boosting是一种迭代的方法，每一次训练会更关心上一次被分错的样本，比如改变被错分的样本的权重的Adaboost方法。还有许多都是基于这种思想，比如Gradient Boosting等。

Stacking

upload successful
从上图可以看出，类似交叉验证。

将数据集分为K个部分，共有n个模型。
for i in xrange(n):
for i in xrange(k):
用第i个部分作为预测，剩余的部分来训练模型，获得其预测的输出作为第i部分的新特征。
对于测试集，直接用这k个模型的预测值均值作为新的特征。
这样k次下来，整个数据集都获得了这个模型构建的New Feature。n个模型训练下来，这个模型就有n个New Features。
把New Features和label作为新的分类器的输入进行训练。然后输入测试集的New Features输入模型获得最终的预测结果。

Blending

Blending直接用不相交的数据集用于不同层的训练。

以两层的Blending为例，训练集划分为两部分（d1，d2），测试集为test。

第一层：用d1训练多个模型，讲其对d2和test的预测结果作为第二层的New Features。
第二层：用d2的New Features和标签训练新的分类器，然后把test的New Features输入作为最终的预测值。

融合的条件

Base Model 之间的相关性要尽可能的小。这就是为什么非 Tree-based Model 往往表现不是最好但还是要将它们包括在 Ensemble 里面的原因。Ensemble 的 Diversity 越大，最终 Model 的 Bias 就越低。
Base Model 之间的性能表现不能差距太大。这其实是一个 Trade-off，在实际中很有可能表现相近的 Model 只有寥寥几个而且它们之间相关性还不低。但是实践告诉我们即使在这种情况下 Ensemble 还是能大幅提高成绩。

多样性

多样性，在前面已经提到过，一个好集成算法，需要训练出来的基学习器具有很强的多样性。

误差-分歧分解
多样性度量
多样性增强

在集成学习中需要有效地生成多样性大的个体学习器。如果增强多样性呢？一般思路是在学习过程中引入随机性，常见的做法是对数据样本、输入属性、输出表示、算法参数进行扰动。

优点

低泛化误差；
容易实现，分类准确率较高，没有太多参数可以调；

缺点

对outlier（离群值）比较敏感。