分类算法之决策树（Decision Tree）_决策树 gini系数

一、决策树简介

决策树，顾名思义，就是帮我们做出决策的树，生活中我们遇到各种各样的抉择，我们的决策过程就是一个树的模型，通过对一系列问题进行if/else的推导，最终实现相关决策

例如：在选择瓜的时候

我们认为色泽、根蒂、敲声是一个西瓜的三个特征，每次我们做出抉择都是基于这三个特征来把一个节点分成好几个新的节点，在我们的问题中，决策的内容是将结果分成两类， 即是（1）否（0）好瓜，这一智类决策问题被称为分类问题，决策树是一种简单的处理分类问题的算法

二、决策树原理

一个完整的决策树包含以下部分

1）根节点：就是数最顶端的节点，比如上图中的“色泽”

2）叶子节点：树最底部的那些节点，也就是决策结果，好瓜还是坏瓜

3）内部节点：除了叶子节点都是内部节点

4）分支：连接内部节点的路径，表示特征划分的结果

三、决策树常见算法

（构建决策树时，首先要选择一个根节点，选择谁来当根节点的准则，有以下三种。）

• ID3：基于信息增益（Information Gain）进行特征选择。（下文）
• C4.5：基于信息增益比（Gain Ratio）进行特征选择，并引入剪枝技术避免过拟合。信息增益率=信息增益/特征本身的熵 Gain（B）/H（B）  
• CART（Classification and Regression Trees）：分类树采用基尼系数（Gini Impurity）进行特征选择，同时可以处理分类和回归任务。

1、Gini系数（CART决策树）

决策树模型的建树依据主要用到的是基尼系数的概念

采用基尼系数进行运算的决策树也被称为CART决策树

基尼系数用于计算一个系统中的失序现象，即系统的混乱程度（纯度），基尼系数越高，系统的混乱程度就越高（不纯），建立决策树模型的目的就是降低系统的混乱程度（提高纯度），从而得到合适的数据分类结果

计算公式如下

               （衡量了集合T的不纯度）

其中pi为类别i在样本T中出现的概率，即类别为i的样本占样本总数的概率

Σ表示后面的项进行求和，对pi进行平方可以放大概率之间的差异，并保证计算结果始终是非负的

例如，一个全部都是离职员工的样本中只有一个类别——离职员工，其出现的频率是100%，所以该系统的基尼系数为1-1^2＝0，表示该系统没有混乱，或者说该系统的“纯度”很高。而如果样本中一半是离职员工，另一半是未离职员工，那么类别个数为2，每个类别出现的频率都为50%，所以其基尼系数为1-（0.5^2＋0.5^2）＝0.5，即其混乱程度很高。

当引入某个用于分类的变量 （如“满意度＜5”）时，分类后的基尼系数公式如下

S1、S2为划分后各自的样本量，gini（T1）、gini（T2）为两类各自的基尼系数

例如，一个初始样本中有1000个员工，其中已知有400人离职，600人不离职。划分前该系统的基尼系数为1-（0.42＋0.62）＝0.48，下面采用两种方式决定根节点：一是根据“满意度＜5”进行分类；二是根据“收入＜10000元”进行分类。

T1的基尼系数：gini(T1)=1-（1^2+0^2）=0

T2的基尼系数：gini(T2)=1-（0.25^2+0.75^2）=0.375

划分后的基尼系数：

划分方式2：以“收入＜10000元”为根节点进行划分，如下图所示，计算过程如下。

T1的基尼系数：gini（T1）＝1-（0.25^2＋0.75^2）＝0.375

T2的基尼系数：gini（T2）＝1-（0.5^2＋0.5^2）＝0.5

划分后的基尼系数：

可以看到，划分前的基尼系数为0.48，以“满意度＜5”为根节点进行划分后的基尼系数为0.3，而以“收入＜10000元”为根节点进行划分后的基尼系数为0.45。

基尼系数越低表示系统的混乱程度越低（纯度越高），区分度越高，越适合用于分类预测，因此这里选择“满意度＜5”作为根节点。

 2、信息熵、信息增益（ID3）

除了基尼系数，还有另一种衡量系统混乱程度的经典手段-信息熵

在搭建决策树模型时，信息熵的作用和基尼系数是基本一致的，都可以帮助合理地划分节点。信息熵H(X)的计算公式如下  (i=1,2,…,n)

其中X表示随机变量，随机变量的取值为X1，X2，X3……，在n分类问题中便有n个取值，pi表示随机变量Xi的发生频率，且有Σpi＝1。

举例来说，一个全部都是离职员工的样本中只有一个类别——离职员工，其出现的频率是100%，所以该系统的信息熵为-1×log1＝0，表示该系统没有混乱。而如果样本中一半是离职员工，另一半是未离职员工，那么类别个数为2，每个类别出现的频率都为50%，所以该系统的信息熵为-（0.5×log0.5＋0.5×log0.5）＝1，表示该系统混乱程度很高。

当引入某个用于进行分类的变量A（如“满意度＜5”），根据该变量划分的信息熵又称为条件熵

其中S1、S2为划分后两类各自的样本量，H（X1）、H（X2）为两类各自的信息熵

为了衡量不同划分方式降低信息熵的效果，还需计算分类后信息上的减少值（原系统的信息熵与分类后系统的信息熵之差），该减少值称为熵增益或信息增益，其值越大，说明分类后的系统混乱程度越低，即分类越准确。

信息增益的计算公式如下

      

同理，使用之前的例子，初始样本有1000个员工，其中已知有400人离职，600人不离职。划分前该系统的信息熵为-（0.4×log0.4＋0.6×log0.6）＝0.97，混乱程度较高。下面采用两种方式决定根节点：一是根据“满意度＜5”进行分类；二是根据“收入＜10000元”进行分类。

划分方式1：以“满意度＜5”为根节点进行划分，如下图所示，计算过程如下。

初始信息熵：H（X）＝-（0.4×log0.4＋0.6×log0.6）＝0.97

X1的信息熵：H（X1）＝-（1×log1＋0×log0）＝0

X2的信息熵：H（X2）＝-（0.25×log0.25＋0.75×log0.75）＝0.81

划分后的信息熵：

信息增益：Gain（A）＝H（X）-HA（X）＝0.97-0.65＝0.32

划分方式2：以“收入＜10000元”为根节点进行划分，如下图所示，计算过程如下。

初始信息熵：H（X）＝-（0.4×log0.4＋0.6×log0.6）＝0.97

X1的信息熵：H（X1）＝-（0.25×log0.25＋0.75×log0.75）＝0.81

X2的信息熵：H（X2）＝-（0.5×log0.5＋0.5×log0.5）＝1

划分后的信息熵:

信息增益：Gain（B）＝H（X）-HB（X）＝0.97-0.924＝0.046

根据方式1划分后的信息增益为0.32，大于根据方式2划分后的信息增益0.046，因此选择根据方式1进行决策树的划分，这样能更好地降低系统的混乱程度。这个结论和之前用基尼系数计算得到的结论是一样的。

3、三种算法的比较

适用范围：

ID3算法只能处理离散特征的分类问题，C4.5能够处理离散特征和连续特征的分类问题，CART算法可以处理离散和连续特征的分类与回归问题。

四、决策树构建过程

决策树的构建过程通常采用递归分割（Recursive Partitioning）方法：

1. 从数据集的特征空间选择最佳特征作为根节点，基于某种度量方法（如信息增益、信息增益比或基尼系数）找到最优划分条件。
2. 根据选定特征的划分条件，将数据集分为两个或多个子集。
3. 对每个子集，重复步骤1和2，直至满足某种停止条件（如最大树深度、最小节点数据量或纯度达到阈值）。
4. 如果需要的话，可以进行剪枝操作，以降低过拟合风险。

五、剪枝处理

决策树算法很容易过拟合，剪枝算法就是用来防止决策树过拟合，提高泛华性能的方法。剪枝分为预剪枝与后剪枝。

1、预剪枝：

预剪枝技术是在决策树生成过程中，提前停止树的生长，从而防止过拟合。预剪枝实施的方法有：

• 最大树深度：设定树的最大深度，当达到最大深度时停止分裂。
• 最小节点数据量：设定节点上的最小数据量，若数据量小于该阈值则不再进行分裂。
• 最小信息增益或其他指标：如果分裂后的某个指标（如信息增益、基尼指数等）没有显著改善，则停止分裂。

预剪枝的优点是计算速度快，因为剪枝发生在树生长期间。然而，预剪枝的缺点是可能过早停止分裂，导致欠拟合现象。

2、后剪枝：

后剪枝技术是在决策树生成完成后，通过剪除部分子树来简化决策树。后剪枝方法通常采用自底向上的策略，从叶节点开始合并，直至满足某种停止条件。后剪枝实施的方法有：

• 代价复杂度剪枝（Cost-Complexity Pruning）：通过定义复杂度损失函数，量化模型的拟合精度与复杂度之间的关系。当模型复杂度损失大于简化模型后的误差损失时，进行剪枝操作。
• 错误率剪枝：使用验证集计算误差率，当剪枝操作后验证集的误差率降低（或至多增加一定容忍度），则剪掉子树。

后剪枝通常能取得较好的泛化性能，因为它在生成完整决策树后再进行剪枝。然而，其缺点是计算复杂度较高，因为需要在完整决策树生成之后再进行剪枝操作。

六、优点和缺点

优点：

   1、易于理解和解释：决策树通过树形结构直观地表示特征与目标之间的关系。

   2、无需预处理和特征缩放：决策树不需要对数据进行预处理，如标准化、归一化（过将输入特征的数值范围缩放到一个预定的区间（通常为[0, 1]））等。

   3、能处理混合类型特征：可以同时处理分类和数值特征。

   4、高效且可扩展：决策树的构建和预测过程相对快速，可以用于大规模数据集。

缺点：

   1、高效且可扩展：决策树的构建和预测过程相对快速，可以用于大规模数据集。

   2、对噪声（无法解释的变异数据）敏感：数据中的噪声可能导致树结构发生剧变。

   3、稳定性较差：数据集的小变动可能导致完全不同的树结构。