随机森林的算法思想

作者: PrivateEye_zzy | 来源:发表于2019-06-28 11:30 被阅读0次

本章涉及到的知识点清单：

1、集成学习

2、bagging模式

3、随机森林的思想

4、CART算法

5、分类树

6、回归树

7、数据样本和feature的随机采样

8、决策树节点的完全二分裂

9、随机森林的构造步骤

10、案例一：随机森林处理分类

11、案例二：随机森林处理回归

12、随机森林的优点和缺点

一、集成学习

集成学习通过训练若干个弱学习器，然后将各个若学习器结果汇总，通过一定的结合策略计算最终结果，从而形成一个强学习器，即

集成学习

每个单体学习器集成的算法是一个弱分类器，通常这些弱学习器集成的算法分为两类：

（1）同质：所有弱学习器集成的算法属于同种类型，比如决策树集成

（2）异质：不同弱学习器集成的算法属于不同类型

用的比较多的是同质学习器，而同质学习器按照单体学习器之间是否存在依赖关系可以分为两类：

（1）如果单体学习器之间存在强依赖关系，则单体学习器需要串行生成，代表算法是boosting系列算法

（2）如果单体学习器之间不存在强依赖关系，则单体学习器可以并行生成，代表算法是bagging和随机森林系列算法

目前，有三种常见的集成学习框架：bagging，boosting和stacking，随机森林属于bagging

二、bagging方法

bagging：从训练集进行子抽样，构成每个单体学习器需要的子数据集，最后对所有单体学习器预测的结果进行汇总决策，即

bagging模式

bagging有如下特点：

（1）从原始样本集采取有放回式抽样，抽样的规模等于原始样本集，则一些样本可能会被多次重复抽到，而一些样本可能不会被抽到

（2）采用均匀抽样，即每个样本的被抽取的权重相等

（3）一个子训练集得到一个弱学习器，则K个子训练集对应K个弱学习器

（4）所有弱学习器的预测结果一样重要(权重相等)

（5）各个弱学习器之间互相独立，即可并行生成若干弱学习器

（6）对于分类问题，将K个弱学习器的预测结果采取投票策略；对于回归问题，将K个弱学习器的预测结果采取均值策略

三、随机森林的思想

随机森林是基于集成学习的思想，将多颗树集成在一起的算法，它的基本单元是决策树，且这些决策树之间彼此独立没有关联

随机森林包含如下思想：

（1）数据样本的随机选取

（2）决策树的构造

（3）待选feature的随机选取

（4）森林的预测策略

四、CART算法

随机森林的单元弱学习器是决策树，决策树分类两类：分类树和回归树

分类树输出的是预测样本的类别，回归树输出的是预测样本的数值，而CART分裂算法可以构建分类树，也可构建回归树

CART算法的流程为：

（1）先用不同的feature和分割值尝试分裂出不同节点

（2）对于非叶子节点，采取二分策略分割当前数据，

（3）采用不同的评分函数来量化当前分裂的效果，选取分数最高的feature来完成节点的真分裂

（4）直到分裂出叶子节点

CART算法有如下特点：

（1）CART算法对每个非叶子节点的判断条件为：单feature的单个分割值

（2）CART算法对每个非叶子节点的判断逻辑为：只判断当前feature是否满足当前的是非条件，答案只能为“是”或者“否”，则即时一个feature有多个取值，也只能把当前数据划分为两部分

（3）CART算法对每个非叶子节点的切割逻辑为：二分递归切割策略，把当前样本划分为两个子样本，使得生成的非叶子节点都有两个分支，因此CART算法构成的是一个结构简洁的二叉树

（4）CART算法的评分函数为：

a、回归问题：总方差评分

b、分类问题：基尼系数评分

CART分裂算法对比ID3和C4.5算法如下

不同分裂算法的比较

五、分类树

对于分类树，我们使用基尼系数来为节点的分裂效果评分

设：样本集D总共有K个类别， $C_{k}$ 表示属于第k类的样本子集，则D的基尼系数表达为：

$Gini(D) = 1 - \sum_{k=1}^K (\frac{|C_{k}|}{|D|})^{2}$

从基尼系数的表达式可知，其反映了样本中类别不一致的概率，即样本的不纯度。显然基尼系数越小，样本的不纯度就越低

设集合A表示D中的所有feature，任意feature为： $a\epsilon A$ ，a的特征值为： $a=\{ a_{1}...a_{v} \}$

定义a的切割点集合S为： $S=\{ s_{1}...s_{v-1} \}=\{ \frac{a_{1} + a_{2}}{2} ... \frac{a_{v-1} + a_{v}}{2} \}$

则根据特征a的某个切割点s，由CART算法将D二分为两部分子集D1和D2，该逻辑的基尼系数评分表达为：

$Gini(D,a) = \frac{|D1|}{|D|} Gini(D1) + \frac{|D2|}{|D|} Gini(D2)$

其中 $\frac{|D1|}{|D|}$ 和 $\frac{|D2|}{|D|}$ 分别表示D1和D2的权重

则分类树分裂的目标为：

用基尼系数评分，找出使得当前节点分裂效果最好的特征a*和分割点s*

翻译为数学语言即： $a^{*}, s^{*} = \min_{a\varepsilon A,s\varepsilon S} \{ Gini(D,a) \}$

六、回归树

对于分类树，我们使用总方差R2来为节点的分裂效果评分

与上述分类树同理，根据特征a的某个切割点s，由CART算法将D二分为两部分子集D1和D2，该逻辑的R2评分表达为：

$R^{2} = var(D1)|D1| + var(D2)|D2|$

其中var表示样本的方差

则回归树分裂的目标为：

用R2总方差评分，找出使得当前节点分裂效果最好的特征a*和分割点s*

翻译为数学语言即： $a^{*}, s^{*} = \min_{a\varepsilon A,s\varepsilon S} \{ R2(D,a) \}$

七、数据样本和feature的随机采样(bootstrap)

随机森林对输入的样本集分别进行行、列的随机采样

行采样：构造随机子样本，对数量为N的样本，进行有放回式抽样，得到可能会随机重复的数量为N的子样本

列采样：构造随机feature，对数量为M的特征，进行无放回式抽样，得到m<M个随机feature，一般取 $m=\sqrt{M}$

有放回式抽样样本

无放回式抽样特征

数据(行)采样和feature(列)采样的使用场景为：

（1）数据采样：构造决策树之前

（2）feature采样：构造决策树的递归过程中，即每次非叶子节点的分裂

八、决策树节点的完全二分裂

在递归构造决策树的过程中，每个树分支(非叶子节点)都要按照单个feature的分割点完成二分裂，直到该节点无法继续分裂为止

停止继续分裂的条件：在递归构造决策树的过程中，当前样本的类别均一致

九、随机森林的构造步骤

通过以上知识点，我们可以归纳出随机森林的构造步骤：

（1）采用有放回式随机抽样，抽选出K组训练子集

（2）由每组训练子集递归构造K颗决策树

（3）对于决策树的每一个节点，采用无放回式随机抽样feature全集，抽选出m个待选feature

（4）尝试用所有待选feature来分裂节点，根据Gini或者R2评分函数给每次分裂效果量化评分，选择出最佳的feature和切割点值

（5）决策树根据发现的最佳feature和切割点值分裂节点，直到停止分裂

（6）每颗决策树都都不用采用剪枝技术，每棵树都能完整生长

（7）交叉验证模型的预测能力，对于分类问题，采用投票策略对K颗决策树的预测结果统计；对于回归任务，采用K颗决策树的预测结果求均值

十、案例一：随机森林处理分类问题

我们采用bagging算法和Gini系数来构建随机森林处理分类问题：

基尼系数

随机采样样本和特征

寻找节点的最佳分裂方式

递归建立决策树

交叉验证分类模型

模型预测分类结果

十一、案例二：随机森林处理回归问题

同理，我们用bagging算法和R2来构建随机森林处理回归问题：

计算总方差R2

叶子节点取均值

寻找节点的最佳分裂方式

递归建立决策树

交叉验证回归模型

模型预测回归结果

十二、随机森林的优点和缺点

最后我们总结一下随机森林模型的优缺点

随机森林模型的优点有：

（1）随机森林模型能解决分类与回归两种类型的问题，并在这两个方面都有相当好的估计表现

（2）子数据集的构造采用有放回式抽样，使得抽样数据集有大约1/3的数据没有被抽中去参加决策树的构造，所以相对不容易出现over-fitting

（3）使树节点每次分裂选择的最佳feature和分割值，都由无放回式抽样提供随机feature候选列表，则训练出的模型方差较小，泛化能力强

（4）模型训练速度快，各弱学习器容易做成并行化方法

PS：简单证明上述第(2)点

设任意一个样本集采用有放回式抽样n次，每次抽取互相独立，即每个样本被抽中的概率都为 $\frac{1}{n}$ ，则某个样本在这n次都没有被抽中的概率为P，翻译为数学语言，即：