二谈决策树算法

在昨天的文章中，企鹅介绍了决策树算法中的两种划分选择——信息熵与信息增益，以及利用这两种划分选择如何构建决策树模型。那么，在决策树算法建模的过程中，我们还有哪些广泛应用的划分选择呢？今天，企鹅就为你继续讲讲增益率和基尼系数这两种指标。

增

益

率

在很多应用场景中，每行数据（示例）都对应一个特定的编号，导致在编号这一列数据中，有多少数据就有多少类结果。回顾之前的信息熵公式，这一属性的信息增益将远大于其他候选属性，以这一属性作为分支节点虽然分支节点的纯度达到最高，但建立的决策树模型不具有泛化能力，无法对新样本进行有效的预测。

上述现象表明了信息增益在使用上的一大缺陷——其对取值类别较多的属性有一定的偏好，这一偏好可能对模型的泛化能力产生负面影响。因而，为解决这一问题，就需要引入一个新的划分选择——增益率。

增益率的定义如下：

对于属性的固有值IV，属性对应的值的种类越多，IV的值就越大，增益率也就越小，一定程度上解决了类似于“编号”这类属性对建模过程的影响。但，这也会造成增益率对可驱逐数目类别较少的属性有所偏好的情况。因而，在应用增益率构建决策树模型的C4.5算法中，并没有直接选择增益率最大的候选划分属性，而是采用了一种启发式算法：

（1）从候选划分属性中找出信息增益高于平均水平的属性

（2）从（1）中选出的属性中挑选增益率最高的属性完成决策树的节点选择。

可以说，C4.5算法是在以信息增益为节点划分选择上的ID3基础上的改进，但除了节点划分，C4.5算法还在以下几方面进行了改进：

（1）能够处理离散型和连续型的属性类型；

（2）构造决策树之后进行剪枝操作；

（3）能够处理具有缺失属性值的训练数据。

在之后的文章中，我们还将对剪枝以及缺失数据等方面进行具体介绍。在基本了解了C4.5算法原理后，那么在实践中应该如何利用R软件进行操作呢？

基

尼

系

数

CART决策树使用基尼系数来选择划分属性。

除了使用基尼系数作为划分节点选择的指标，CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。

CART算法构建决策树模型主要分为两个步骤：（1）将样本递归划分进行建树过程；（2）用验证数据进行剪枝。由于剪枝将在后文中进行重点介绍，那么下面我们将对如何在R语言中实践CART算法进行介绍。