本章涉及到的知识点清单：
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有如下特点：
（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个类别，表示属于第k类的样本子集，则D的基尼系数表达为：
从基尼系数的表达式可知，其反映了样本中类别不一致的概率，即样本的不纯度。显然基尼系数越小，样本的不纯度就越低
设集合A表示D中的所有feature，任意feature为：，a的特征值为：
定义a的切割点集合S为：
则根据特征a的某个切割点s，由CART算法将D二分为两部分子集D1和D2，该逻辑的基尼系数评分表达为：
其中和
分别表示D1和D2的权重
则分类树分裂的目标为：
用基尼系数评分，找出使得当前节点分裂效果最好的特征a*和分割点s*
翻译为数学语言即：
六、回归树
对于分类树，我们使用总方差R2来为节点的分裂效果评分
与上述分类树同理，根据特征a的某个切割点s，由CART算法将D二分为两部分子集D1和D2，该逻辑的R2评分表达为：
其中var表示样本的方差
则回归树分裂的目标为：
用R2总方差评分，找出使得当前节点分裂效果最好的特征a*和分割点s*
翻译为数学语言即：
七、数据样本和feature的随机采样(bootstrap)
随机森林对输入的样本集分别进行行、列的随机采样
行采样：构造随机子样本，对数量为N的样本，进行有放回式抽样，得到可能会随机重复的数量为N的子样本
列采样：构造随机feature，对数量为M的特征，进行无放回式抽样，得到m<M个随机feature，一般取
数据(行)采样和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来构建随机森林处理回归问题：
十二、随机森林的优点和缺点
最后我们总结一下随机森林模型的优缺点
随机森林模型的优点有：
（1）随机森林模型能解决分类与回归两种类型的问题，并在这两个方面都有相当好的估计表现
（2）子数据集的构造采用有放回式抽样，使得抽样数据集有大约1/3的数据没有被抽中去参加决策树的构造，所以相对不容易出现over-fitting
（3）使树节点每次分裂选择的最佳feature和分割值，都由无放回式抽样提供随机feature候选列表，则训练出的模型方差较小，泛化能力强
（4）模型训练速度快，各弱学习器容易做成并行化方法
PS：简单证明上述第(2)点
设任意一个样本集采用有放回式抽样n次，每次抽取互相独立，即每个样本被抽中的概率都为，则某个样本在这n次都没有被抽中的概率为P，翻译为数学语言，即：
上式两边取对数得：
令，则：
化简得：
上式e的幂部分取极限属于型，使用洛必达法则得：
带入解出P：
随机森林模型的缺点有：
（1）在某些噪音比较大的样本集上，模型容易陷入过拟合
（2）取值划分比较多的特征容易对模型的决策产生更大的影响，从而影响拟合的模型的效果
案例代码见：随机森林的算法思想
