重修决策树：信息增益与Gini系数

重修系列的 第二篇文章

最近被Random Forest，Adaboost，ID3，C4.5，CART一系列决策森林包围了，正巧在复习 数据仓库 ，把这一系列的内容再串联一遍。

我是决策树

决策树本质上是一个 贪心方法 ，虽然从理论上说我们能够构造一棵最优决策树，但是时间与算力开销实在很大，所以实际上我们使用的是 Hunt's 算法来执行贪心的选择过程。简单来说就是：假设我手上有一个评估分裂后的节点集好坏的一个 标准 （这个标准就是下面要说的信息增益与Gini系数），我每次只考察使当前节点达到最优分裂的属性，而不从全局角度来考虑。

根据标准的不同，决策树又分为 ID3, C4.5, CART 三大类，分别使用的考察标准是 信息增益、信息增益率、Gini系数 。

信息增益

信息增益建立在 信息熵 这个概念之上，我只从我粗浅的理解来阐述这些概念。

信息熵提出的目的是为了 量化信息 ，而量化的目的是 便于比较 。比如小明知道小红很开心，而小张知道小红开心的原因是因为小明裤子的拉链没拉，在这个情境下，小张知道的信息是比小明要多的，因为小张不仅知道小红开心，还知道小红开心的原因，我们有理由认为在小红开心这件事情上，小张知道的信息比小明要多。但是这与主题关系不大，根据我看博客多年的经验，怼上太多公式反而会给人造成混淆，所以我不放信息熵的公式了。总得来说只有一点：信息熵存在的目的是为了便于进行信息量的比较，考虑到熵表征的是物质的混乱程度，所以 信息量越大，信息熵的值越趋于0 。

现在给定一个数据集合$D$，我们要做的是一个$k$分类问题，即把里面的数据分成$y_1,…,y_k$共$k$类。 这里提出一个很简单但是对于计算后面的信息增益与Gini系数都很重要的概念：$p_i,i\in[1,k]$。$p_i$表征 从数据集合D中随机取一个元素出来，这个元素类别是y_i的概率 ，所以很好理解的是，$p_i=\frac{|y_i|}{|D|}$，也就是类别为$y_i$元素在$D$中所占的比例。

现在来讲 信息增益 ，ID3算法的本质就是使用划分前后的信息增益来考察划分属性的好坏。我们可以从以下几个步骤考虑：

1. 我们计算当前数据集合的经验熵：$H(D)=-\sum_{i=1}^kp_i\mathrm{log}_2p_i$。
   简单理解就是，当前数据集合$D$的经验熵就是当前 每一类出现概率的对数在D中的加权和 。
2. 假设我们使用属性$A$来划分当前的数据集合$D$，而$A$有$n$个取值，也就是说我们使用$A$将数据集$D$划分成为了$n$类，分别是$D_1,…,D_n$。我们可以用同样的方式算出$D_1,…,D_n$的经验熵$H(D_1),H(D_2),…,H(D_n)$。
3. 信息增益就是分裂前后的经验熵之差，也就是$g(D,A)=H(D)-\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$。
   前面那个变量就是 分裂前数据的经验熵 ，而减号后面的变量就是 分裂后每一个子节点的经验熵的加权和 。权重就是这个子节点中的数据数量占原数据集合$D$的比例。

在执行ID3算法时，我们遍历每一个能考察的节点， 选择让g达到最大的节点 。因为减号前面的数值是不会变化的，而后面的数值表征了分裂后节点提供的信息量。如果后面的数值贼拉小，说明提供的信息量很大，那整个$g(D,A)$就会很大。而我们要选择最大的那个属性来进行分裂。

信息增益率

信息增益率 在搞懂信息增益以后很好理解，几句话就能说完：

从上面计算条件经验熵的公式可以看出， 信息增益更倾向于选择属性取值n数量更多，每个取值的数据量越均匀的那个属性 。

所以我们需要在信息增益中增加一个 惩罚系数 ，也就是说，这个惩罚系数的值应该 随着属性取值的增加而增大 。惩罚系数的具体计算公式是：$-\sum_{i=1}^n\frac{|D_i|}{|D|}$（其实也就是分类的经验熵$H(A)$）。

最后的信息增益率就是原信息增益与这个惩罚系数之比，即$g’=g(D|A)\div H(A)$。

Gini系数

Gini系数的思想要更好理解一点。它考察了 数据的纯度 ，即分裂后的每一个子类的数据越纯，这个分类属性就越好。同理，我们要 计算分裂前的Gini系数，与分裂后的Gini系数的加权和，并将两者相减 ，相减之差越大，说明这个分类属性越好。

Gini系数的计算公式为：

同样，也就是当前数据集合中每一类的概率平方和的补。

假设我们使用了属性$A$对数据$D$进行分裂为$n$类，求这些分裂后的子类的Gini系数的加权和，权重就是上面提到的$|D_i|/|D|$，再将结果相减即可。

最终的Gini系数增益公式为：