C4.5决策树及CART决策树

学习目标

1. 了解信息增益率的计算公式
2. 知道ID3 和 C4.5决策树的优缺点
3. 了解基尼指数的计算公式
4. 了解基尼指数对于不同特征的计算方式
5. 了解回归决策树的构建原理

1. 信息增益率计算公式¶

1. Gain_Ratio 表示信息增益率
2. IV 表示分裂信息、内在信息
3. 特征的信息增益 ➗ 内在信息
4. 如果某个特征的特征值种类较多，则其内在信息值就越大。即：特征值种类越多，除以的系数就越大。
5. 如果某个特征的特征值种类较小，则其内在信息值就越小。即：特征值种类越小，除以的系数就越小。

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。惩罚参数：数据集D以特征A作为随机变量的熵的倒数。

1.1信息增益率计算举例

特征1的信息增益率：

1. 信息增益：0.5408520829727552
2. 分裂信息：-4/6*math.log(4/6, 2) -2/6*math.log(2/6, 2)=0.9182958340544896
3. 信息增益率：信息增益/分裂信息=0.5408520829727552/0.9182958340544896=0.5889736868180786

特征2的信息增益率：

1. 信息增益：1
2. 分裂信息：-1/6*math.log(1/6, 2) * 6=2.584962500721156
3. 信息增益率：信息增益/信息熵=1/2.584962500721156=0.38685280723454163

由计算结果可见，特征1的信息增益率大于特征2的信息增益率，根据信息增益率，我们应该选择特征1作为分裂特征

1.2. ID3和C4.5对比

• ID3算法缺点
• ID3算法不能处理具有连续值的属性
• ID3算法不能处理属性具有缺失值的样本
• 算法会生成很深的树，容易产生过拟合现象
• 算法一般会优先选择有较多属性值的特征，因为属性值多的特征会有相对较大的信息增益，但这里的属性并不一定是最优的
• C4.5算法的核心思想是ID3算法，对ID3算法进行了相应的改进。
• C4.5使用的是信息增益比来选择特征，克服了ID3的不足。
• 可以处理离散型描述属性，也可以处理连续数值型属性
• 能处理不完整数据
• C4.5算法优缺点
• 优点：分类规则利于理解，准确率高
• 缺点
  • 在构造过程中，需要对数据集进行多次的顺序扫描和排序，导致算法的低效
  • C4.5只适合于能够驻留内存的数据集，当数据集非常大时，程序无法运行
• 无论是ID3还是C4.5最好在小数据集上使用，当特征取值很多时最好使用C4.5算法

4. Cart树简介

Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归，其学习算法分为下面两步：

（1）决策树生成：用训练数据生成决策树，生成树尽可能大

（2）决策树剪枝：基于损失函数最小化的剪枝，用验证数据对生成的数据进行剪枝。

分类和回归树模型采用不同的最优化策略。Cart回归树使用平方误差最小化策略，Cart分类生成树采用的基尼指数最小化策略。

Scikit-learn中有两类决策树，他们均采用优化的Cart决策树算法。一个是DecisionTreeClassifier一个是DecisionTreeRegressor回归。

5. 基尼指数计算公式

1. 信息增益（ID3）、信息增益率值越大（C4.5），则说明优先选择该特征。
2. 基尼指数值越小（cart），则说明优先选择该特征。

6. Cart分类树原理¶

如果目标变量是离散变量，则是classfication Tree分类树。

分类树是使用树结构算法将数据分成离散类的方法。

（1）分类树两个关键点：

将训练样本进行递归地划分自变量空间进行建树‚用验证数据进行剪枝。

（2）对于离散变量X（x1…xn）处理：

分别取X变量各值的不同组合，将其分到树的左枝或右枝，并对不同组合而产生的树，进行评判，找出最佳组合。如果只有两个取值，直接根据这两个值就可以划分树。取值多于两个的情况就复杂一些了，如变量年纪，其值有“少年”、“中年”、“老年”，则分别生产{少年，中年}和{老年}，{少年、老年}和{中年}，{中年，老年}和{少年}，这三种组合，最后评判对目标区分最佳的组合。因为CART二分的特性，当训练数据具有两个以上的类别，CART需考虑将目标类别合并成两个超类别，这个过程称为双化。这里可以说一个公式,n个属性，可以分出(2^n-2)/2种情况。

💡💡我们知道，决策树算法对训练集很容易过拟合，导致泛化能力很差，为解决此问题，需要对CART树进行剪枝。CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小，从而能够对未知数据有更准确的预测，也就是说CART使用的是后剪枝法。一般分为两步：先生成决策树，产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，最后选择泛化能力好的剪枝策略

7. 回归决策树构建原理¶

CART 回归树和 CART 分类树的不同之处在于:

1. CART 分类树预测输出的是一个离散值，CART 回归树预测输出的是一个连续值。
2. CART 分类树使用基尼指数作为划分、构建树的依据，CART 回归树使用平方损失。
3. 分类树使用叶子节点里出现更多次数的类别作为预测类别，回归树则采用叶子节点里均值作为预测输出

CART 回归树构建:

\operatorname{Loss}(y, f(x))=(f(x)-y)^{2}

例子：

假设：数据集只有 1 个特征 x, 目标值值为 y，如下图所示：

由于只有 1 个特征，所以只需要选择该特征的最优划分点，并不需要计算其他特征。

1. 先将特征 x 的值排序，并取相邻元素均值作为待划分点
2. 计算每一个划分点的平方损失，例如：1.5 的平方损失计算过程为：
3. R1 为 小于 1.5 的样本个数，样本数量为：1，其输出值为：5.56

$R_1 =5.56$

R2 为 大于 1.5 的样本个数，样本数量为：9 ，其输出值为：

$R_2=(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05) / 9=7.50$

该划分点的平方损失： 以此方式计算 2.5、3.5... 等划分点的平方损失，结果如下所示：

4. 当划分点 s=6.5 时，m(s) 最小。因此，第一个划分变量：特征为 X, 切分点为 6.5，即：j=x, s=6.5

依此类推，分别对每一个节点进行上面的几个步骤

CART 回归树构建过程如下：

1. 选择第一个特征，将该特征的值进行排序，取相邻点计算均值作为待划分点
2. 根据所有划分点，将数据集分成两部分：R1、R2
3. R1 和 R2 两部分的平方损失相加作为该切分点平方损失
4. 取最小的平方损失的划分点，作为当前特征的划分点
5. 以此计算其他特征的最优划分点、以及该划分点对应的损失值
6. 在所有的特征的划分点中，选择出最小平方损失的划分点，作为当前树的分裂点
7. 回归决策树使用平方损失作为分裂增益计算指标
8. 回归决策树是二叉树

下章我们具体学习剪枝以及带入案例帮大家更好的理解