Bagging

算法流程如下：

1. 从原始样本中使用Bootstraping方法有放回地随机抽取nnn个训练样本，共进行kkk轮抽取，得到kkk个训练集；
2. 对于kkk个训练集，分别训练出kkk个模型；
3. 在对预测输出进行结合时：
   • 分类：简单投票法
   • 回归：简单平均法

RF

RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择。

传统决策树在选择划分特征时是在当前结点的特征集合（假设有ddd个特征）中选择一个最优特征；而在RF中，对基决策树的每个结点，先从该结点的特征集合中随机选择一个包含kkk个特征的子集，然后再从这个子集中选择一个最优特征用于划分。kkk控制了随机性的引入程度：

• k=dk=dk=d：基决策树的构建与传统决策树相同；
• k=1k=1k=1：随机选择一个特征进行划分；

RF简单、容易实现、计算开销小，但是性能却非常强大。

结合策略

对于输出值连续型，最常用的结合策略是使用平均法：

平均法

• 简单平均法：

H(x)=1T∑i=1Thi(x) H(x) = \frac{1}{T} \sum_{i=1}^T h_i(x)H(x)=T1​i=1∑T​hi​(x)

• 加权平均法：

H(x)=∑i=1Twihi(x),∑i=1Twi=1 H(x) = \sum_{i=1}^T w_i h_i(x), \quad \sum_{i=1}^T w_i = 1H(x)=i=1∑T​wi​hi​(x),i=1∑T​wi​=1

wiw_iwi​一般是从训练数据中学习而得。

在个体学习器性能相差较大时使用加权平均法，反之使用简单平均法。

投票法

对于分类任务来说，假设有{c1,c2,…,cN}\{ c_1, c_2, \dots, c_N \}{c1​,c2​,…,cN​}个类别。最常用的结合策略是使用投票法：

• 绝对多数投票法：

H(x)={cj,if ∑i=1Thij(x)>0.5∑k=1N∑i=1Thik(x)；reject,otherwise H(x) = \begin{cases} c_j,& if \ \sum_{i=1}^T h_i^j(x) > 0.5\sum_{k=1}^N \sum_{i=1}^T h_i^k(x)；\\ reject, & otherwise \end{cases}H(x)={cj​,reject,​if∑i=1T​hij​(x)>0.5∑k=1N​∑i=1T​hik​(x)；otherwise​

即某类别得票过半数，则预测为该类别；否则拒绝预测。

• 相对多数投票法：

H(x)=cargmaxj∑i=1Thij(x) H(x) = c_{argmax_j} \sum_{i=1}^T h_i^j(x)H(x)=cargmaxj​​i=1∑T​hij​(x)

即预测为得票最多的类别，若同时有多个类别获得最高票，则从中随机选择一个类别。

• 加权投票法：

H(x)=cargmaxj∑i=1Twihij(x),∑i=1Twi=1 H(x) = c_{argmax_j} \sum_{i=1}^T w_i h_i^j(x), \quad \sum_{i=1}^T w_i = 1H(x)=cargmaxj​​i=1∑T​wi​hij​(x),i=1∑T​wi​=1

学习法

当训练数据很多时，一种更为强大的结合策略是使用”学习法“，即通过另一个学习来结合，典型代表就是Stacking。这里把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。

Stacking先从初始数据集训练出初级学习器，然后”生成“一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。算法流程如下：