Bagging & RF

相对于 boosting ，bagging 更好理解一点。

Bagging

算法流程如下：

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

RF

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

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

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

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

结合策略

平均法

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

• 简单平均法：

$$H(x) = \frac{1}{T} \sum_{i=1}^T h_i(x)$$

• 加权平均法：

$$H(x) = \sum_{i=1}^T w_i h_i(x), \quad \sum_{i=1}^T w_i = 1$$

$w_i$ 一般是从训练数据中学习而得。

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

投票法

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

• 绝对多数投票法：

$$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) = c_{argmax_j} \sum_{i=1}^T h_i^j(x)$$

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

• 加权投票法：

$$H(x) = c_{argmax_j} \sum_{i=1}^T w_i h_i^j(x), \quad \sum_{i=1}^T w_i = 1$$

学习法

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

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