决策树 | Swift's Blog

决策树的定义和示例见西瓜书P73~P74，下面主要介绍决策树的构造算法：

信息熵

信息熵是衡量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k(k=1,2,\cdots,|\gamma|)$ ，那么 $D$ 的信息熵为：

$Ent(D) = - \sum_{k=1}^{|\gamma|} p_k log_2 p_k$

$Ent(D)$ 越小，则 $D$ 纯度越高。

$Gain(D, a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)$

$V$ 表示属性 $a$ 的取值范围。信息增益越大，表示使用属性 $a$ 进行划分所获得的“纯度提升”越大。

根据 ID3 算法的核心思想，只要在每次决策树非叶子节点划分之前，计算出每一个属性所带来的信息增益，选择最大信息增益的属性来划分，就可以让本次划分更优，因此整个 ID3 实际上是一个贪心算法。

以西瓜数据集2.0来说，“纹理”的信息增益最大，于是它被选为划分属性。后续对其它属性进行特征选择。

C4.5 对 ID3 算法最大的改进就是在获取最优分类特征的时候，将 ID3 所使用的信息增益换成了信息增益比。

如果我们将每个西瓜样本的“编号”作为候选划分属性，那么它的信息增益最大。因为“编号”将产生17个分支，每个分支仅包含一个样本，这些分支结点的纯度达到最大。但这样的决策树不具有泛化能力，无法对新样本有效预测。

实际上，信息增益准则对取值较多的属性有所偏好，为了减少这种偏好带来的不利影响，C4.5采用“增益率”来选择最优划分属性：

$Gain\_ratio = \frac{Gain(D,a)}{IV(a)} \\ IV(a) = -\sum_{v=1}^V \frac{D^v}{D} log_2 \frac{D^v}{D}$

$IV(a)$ 称为属性 $a$ 的“固有值”。$V$ 越大，$IV(a)$ 越大。

需注意的是，增益率对 $V$ 较小的属性 $a$ 有所偏好。因此，C4.5算法并不直接选择增益率最大的候选划分属性，而使用了一个启发式策略：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART决策树使用“基尼指数”来选择划分属性。数据集 $D$ 的纯度可用基尼值来度量：

$Gini(D) = \sum_{k=1}^{|\gamma|} \sum_{k' \ne k} p_k p_{k'} = 1 - \sum_{k=1}^{|\gamma|} p_k^2$

直观来说，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数定义为：

$Gini\_index(D,a) = \sum_{v=1}^V \frac{|D^v|}{|D|} Gini(D^v)$

在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即：

$a_{*} = argmax_{a \in A} Gini\_ index(D,a)$