前言

决策树属于经典的十大数据挖掘算法之一，是一种类似于流程图的树结构，其规则就是IF…THEN…的思想，可以用于数值型因变量的预测和离散型因变量的分类。该算法简单直观、通俗易懂，不需要研究者掌握任何领域知识或复杂的数学推理，而且算法的结果输出具有很强的解释性。

使用决策树过程中，有两个非常重要的核心问题需要解决，一个是决策树中节点字段的选择，另一个是决策树的剪枝（在实际应用中，我们是不期望决策树盲目生长的，因为这会导致模型的过拟合）。在本文中，我们重点讲解有关节点选择的问题，并通过小例子加以说明。

决策树

首先来看一下如下的表格以及对应的决策树图：

可能你会有疑问，根节点为什么选择年龄字段作为判断条件，而不是选择其他字段呢？同理，其他中间节点的选择是否都有理论依据作为支撑呢？我们再设想一下，如果选择合理的话，决策树的分类效果应该是非常好的，即叶节点中的输出会比较“纯净”（即叶节点只包含相同的分类）。

那问题来了，“纯净”度该如何度量？通常可以使用信息增益、信息增益率和基尼指数来衡量“纯净度”，接下来我们就介绍CART决策树所使用的基尼指数方法。

基尼指数

决策树中的C4.5算法使用信息增益率指标实现根节点或中间节点的字段选择，但该算法与ID3算法一致，都只能针对离散型因变量进行分类，而对于连续型的因变量就显得束手无策了。为了能够让决策树预测连续型的因变量，Breiman等人在1984年提出了CART算法，该算法也称为分类回归树，它所使用的字段选择指标是基尼指数。

基尼指数的计算公式可以表示为：

其中，pk表示某事件第k个可能值的发生概率，该概率可以使用经验概率表示，所以基尼指数可以重写为：

其中，|D|表示事件中的所有样本点，|Ck|表示事件的第k个可能值出现的次数，所以概率值pk就是

所表示的频率。下面以手工构造的虚拟数据为例，解释CART算法是如何借助于基尼指数实现节点字段的选择，数据如下：

假设上表中的Edu表示客户的受教育水平，Credit为客户在第三方的信用记录，Loan为因变量，表示银行是否对其发放贷款。根据基尼指数的公式，可以计算Loan变量的基尼指数值：

在选择根节点或中间节点的变量时，就需要计算条件基尼指数，条件基尼指数仍然是某变量各取值下条件基尼指数的期望，所不同的是，条件基尼指数采用的是二分法原理。对于Credit变量来说，其包含两种值，可以一分为二；但是对于Edu变量来说，它有三种不同的值，就无法一分为二了，但可以打包处理，如本科与非本科（硕士和大专为一组）、硕士与非硕士（本科和大专为一组）、大专与非大专（本科和硕士一组）。

对于三个及以上不同值的离散变量来说，在计算条件基尼指数时会稍微复杂一些，因为该变量在做二元划分时，会产生多对不同的组合。以表中的Edu变量为例，一共产生三对不同的组合，所以在计算条件基尼指数时就需要考虑三种组合的值，最终从三种值中挑选出最小的作为该变量的二元划分。条件基尼指数的计算公式可以表示为：

其中，

表示A变量在某个二元划分下，第i组的概率，其对应的经验概率为

，即A变量中第i组的样本量与总样本量的商；

表示在已知分组

的情况下，变量D取第k种值的条件基尼指数，其中

表示分组

内变量D取第k种值的频率。为了使读者理解条件基尼指数的计算过程，下面分别计算自变量Edu和Credit对因变量Loan的条件基尼指数：

如上结果所示，由于变量Edu含有三种不同的值，故需要计算三对不同的条件基尼指数值，其中本科与非本科的二元划分对应的条件基尼指数为0.444，硕士与非硕士的条件基尼指数为0.333，大专与非大专的条件基尼指数为0.267，由于最小值为0.267，故将大专与非大专作为变量Edu的二元划分；而变量Credit只有两种值，故只需计算一次条件基尼指数即可，并且值为0.167。

在如上的计算过程中，还需要考虑自变量对因变量的影响程度，即因变量的基尼指数下降速度的快慢，下降的越快，则自变量对因变量的影响就越强。下降速度的快慢可用下方式子衡量：

所以，Edu变量中大专与非大专组的基尼指数下降速度为

；Credit变量的基尼指数下降速度为

。根据节点变量的选择原理，会优先考虑Credit变量用于根节点的条件判断，因为相比于Edu变量来说，它的基尼指数下降速度最大。

假如数据集中包含数值型的自变量，计算该变量的条件基尼指数与数值型自变量信息增益的计算步骤完全一致，所不同的只是度量方法换成了基尼指数。同样，在选择变量的分割点时，需要从n-1个均值中挑选出使

下降速度最大的

作为连续型变量的分割点。

有关决策树中基尼指数的原理和解释就介绍到这里，除此，如何利用信息增益、信息增益率解决C4.5决策树的节点选择问题，可以在我的新书《从零开始学Python数据分析与挖掘》中得到详细的答案。

文章转载自：刘顺祥