参考网上 综合整理

决策树与随机森林

本篇博客将重新给出对决策树与随机森林的认识。主要分析决策树的学习算法：信息增益和ID3、C4.5、CART树，然后给出随机森林。
决策树中，最重要的问题有3个:
1. 特征选择。即选择哪个特征作为某个节点的分类特征；
2. 特征值的选择。即选择好特征后怎么划分子树；
3. 决策树出现过拟合怎么办？
下面分别就以上问题对决策树给出解释。决策树往往是递归的选择最优特征，并根据该特征对训练数据进行分割。

一. 信息熵

基本解释参考：https://blog.****.net/xbmatrix/article/details/56691137

关于信息熵以及最大熵模型的详细信息，请参看该博客。

信息：信息量；概率越小，信息量越大-------所以，通过使用负号来使概率 P越小和信息I 越大。

熵：期望

信息熵：信息的期望

条件熵：在某一特征下的信息熵的期望

信息增益：剩余信息量

通俗理解条件熵

二. 决策树

第一步：特征值的选择（信息增益，信息增益率，gini指数）

第二步：决策树的生成（ID3；ID4.5；Gini指数）

第三步：决策树的剪枝

三. 决策树生成

决策树生成算法

ID3和C4.5

输入：训练集D，特征集A，阀值μ

输出：决策树T

（1)如果D中的所有实例，都属于同一个类CkCk，那么置T为单节点树，返回T

（2)如果A=ØA=Ø，置T为单节点树，将D中实例数最大的类CkCk作为该节点的类，返回T

（3按照上面的三个判断标准，计算信息增益（信息增益比），选择信息增益最大（信息增益比最大）的特征AgAg。

（4)若Ag<μAg<μ，置T为单节点树，将D中实例数最大的类CkCk作为该节点的类，返回T

（5)否则使用特征A分割数据集D，建立树，返回T

（6)对节点i,以DiDi为训练集合，以A−{Ag}A−{Ag}为特征集，递归调用（1）~（5）

 

CART生成：

决策树的生成就是递归的构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

1.回归树生成：

参考：https://cethik.vip/2016/09/21/machineCAST/

2.分类树的生成：

（1)根据特征A，将数据集预分类为A=a和A！=a两类，计算基尼指数

（2)选择基尼指数最小的特征作为分类特征，将数据集切分。切分的两个子节点包含两个被分开的数据集。

（3)对两个子节点递归调用（1）（2），直到满足停止条件。

（4)生成CART决策树。

四. 决策树中避免过拟合的方法

1. 剪枝

参考：https://blog.****.net/bird_fly_i/article/details/72824639

：样本数加权熵求和

剪枝类型：预剪枝、后剪枝

• 预剪枝是在决策树生成过程中，对树进行剪枝，提前结束树的分支生长。
• 后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。

预剪枝依据：

• 作为叶结点或作为根结点需要含的最少样本个数
• 决策树的层数
• 结点的经验熵小于某个阈值才停止

后剪枝思路：

其中：T通俗表达复杂度

损失函数的通俗解释：

2. 随机森林

Bootstrap Aggregation

• 从训练集中有重复的选出n个样本；
• 在所有属性上，对这n个样本建立分类器；
• 重复上述步骤m次，获得m个分类器。最终的决策由这m个分类器进行投票决定。

随机森林

• 从训练集中用Bootstrap采样选出n个样本；
• 从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；
• 重复上述步骤，建立m棵CART树，然后进行投票表决。

详细参考：https://blog.****.net/gumpeng/article/details/51397737