决策树、bagging、boosting算法思想

本文内容主要以算法思想为主，介绍决策树原理，从决策树迁移到集成学习主要是由于随机森林比较好使，引出了bagging和它的亲戚boosting。有趣的思想包括：决策树的信息熵、随机森林的泛化性能、boosting的改变样本分布与前向分步思想

1.决策树

人类判断的机制：由上及下逐级决策，将大问题化为多个子问题。

决策树机制：选择不同的划分属性，将问题逐步划分建成一棵树状图。

由根结点（原始问题）、内结点（子问题）、叶节点（最终决策）组成，具有处理未见实例的能力，泛化能力强。

1.1 算法步骤

决策树利用递归生成，生成过程包含三种递归返回：

1）当前结点所含样本属于同一类别

2）当前属性集为空或者当前样本在所有属性上相等

3）当前结点所含样本为空

具体的算法实现过程这篇文章讲的很好：决策树分类算法原理分析及代码实现

决策树类算法有GBDT(Gradient Boosting DT）、XGBDT、随机森林

1.2 信息熵与基尼指数

信息熵：通过样本集合的不确定性度量样本集合的纯度（信息熵是什么）

Ent(D)越大，不确定性越高，纯度越低。

信息增益：就决策树来说，对公式的理解可以是划分前后不确定性的差值，也就是使用a划分属性带来的纯度提升

决策树学习算法ID3（1986）用信息增益来选择划分属性，C4.5（1993）用信息增益率来选择划分属性

基尼指数：随机从D中抽取两个样本，其类别标记不一致的概率作为纯度的判定，不一致的概率越大，纯度越低。

CART（1984）采用基尼指数来选择划分属性

2. bagging与随即森林

bagging：主要是通过样本的扰动引入基学习器的多样性。利用bootstrap从原始数据集中采样得到不同的数据集，分别训练不同的及学习器模型，再根据结合策略结合

随机森林：基于决策树的bagging，主要是通过样本扰动和属性扰动引入多样性。除了样本集的抽取，还在属性划分过程中引入随机性，不对所有样本进行最优选择，而是先随机选择某些属性，再从随机的属性中选择最优属性。

3. boosting

前向分步训练：基学习器的学习不是并行的，下一个基学习器的学习会用到上一个基学习器的先验知识。

更新样本分布：样本集的抽取不是随机的，而是根据本次基学习器的结果改变本次所使用的训练样本集的分布，用于下一个基学习器的学习。

此外，基学习器的结合策略也可以根据每步训练结果进行改进，如AdaBoost使用的加权平均法中的基学习器分配权重就是根据每一步基学习器的训练结果得到。