来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

前面提到，要构建决策树，最关键的问题是如何找到最优的划分属性，常见的划分方法有三种：

  • 信息增益（information gain），代表算法为 ID3
  • 增益率（gain ratio），代表算法为 C4.5
  • 基尼指数（Gini index），代表算法为 CART

信息熵

划分的原则是希望决策树的分支节点包含的样本尽可能属于同一类别，也就是节点的 纯度（purity）越高越好，而 信息熵（information entropy）是度量样本集合纯度最常用的一种指标之一：

Ent(D)=−∑k=1∣Y∣pklog2pk Ent(D) = - \sum_{k=1}^{\left| \mathcal{Y} \right|} p_k log_2p_k

其中，pkp_k 表示第 k 类样本所占的比例。熵越小，数据就越接近于同一个类别，纯度越高；熵越大，数据的纯度越低，也可以说不确定性越低。

举一个例子，假设数据集 D 有 3 个类别，所占比例为 {13,13,13}\{\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\}，根据公式计算出该数据集的信息熵为：

Ent(D)=−13log(13)−13log(13)−13log(13)=1.0986 Ent(D) = -\frac 1 3 log(\frac 1 3)-\frac 1 3log(\frac 1 3)-\frac 1 3log(\frac 1 3)=1.0986

再假设 3 个类别所占比例为 {110,210,710}\{\frac 1 {10},\frac 2 {10},\frac 7 {10}\}，那么信息熵为：

Ent(D)=−110log(110)−210log(210)−710log(710)=0.8018 Ent(D) = -\frac 1 {10} log(\frac 1 {10})-\frac 2 {10}log(\frac 2 {10})-\frac 7 {10}log(\frac 7 {10})=0.8018

再假设 3 个类别所占的比例为 {1,0,0}\{1,0,0\}，得到的信息熵为：

Ent(D)=0 Ent(D) = 0

可以看出，当数据属于同一个类别时，信息熵达到最小值 0，当数据均匀分布时，信息熵的值最大。

信息熵曲线

当数据集只有两个类别时，假设一个类别所占的比例为 x，则另一个类别所占的比例为 1-x，信息熵为：

Ent(D)=−xlog(x)−(1−x)log(1−x) Ent(D) = -xlog(x)-(1-x)log(1-x)

我们画出这个曲线如下：

import numpy as np
import matplotlib.pyplot as plt

def entropy(p):
    return -p * np.log(p) - (1-p) * np.log(1-p)

x = np.linspace(0.01, 0.99, 200)

plt.plot(x, entropy(x))
plt.show()

运行结果

Notebook 运行结果

从图中可以看出，当数据所占比例为 0.5 时，信息熵的值达到最大。

信息增益

有了信息熵了概念之后，我们再来看看 信息增益（information gain），信息增益表示根据某个属性对数据进行划分后，数据的信息熵得到了多大的提升。比如属性 a 有 V 个可能的取值，如果用属性 a 对数据集进行划分，则可以得到 V 个分支节点（注意，我们在这里只考虑该属性是离散值），也就是 V 个子集，我们记为 \(D^v（v = 1,2,...,V）\)，我们可以计算出每个子集的信息熵 Ent(Dv)Ent(D^v)，然后将所有子集的信息熵累加起来作为子集的信息熵，考虑到每个子集所含样本数不一样，我们再根据各自的比例乘上相应的系数：

Ent(Da)=∑v=1V∣Dv∣∣D∣Ent(Dv) Ent(D_a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)

其中，∣Dv∣|D^v| 表示第 v 个子集所含样本的数量，∣D∣|D| 表示数据集 DD 的样本总数。

这样，我们就可以得到根据属性 a 对数据进行划分的信息增益：

Gain(D,a)=Ent(D)−Ent(Da)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv) Gain(D, a) = Ent(D) - Ent(D_a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)

信息增益越大，表示使用属性 a 进行划分所得到的纯度提升越大，所以只要对每一个属性进行计算，找到信息增益最大的属性进行划分即可。

增益率

使用信息增益对样本进行划分存在一个问题：信息增益对取值较多的属性有所偏好。我们设想一个极端的情形，比如样本集共有 N 个类别，而其中某一个属性的取值也有 N 个，如果使用这个属性对样本进行划分，将得到 N 个分支节点，每个分支仅包含一个样本，很显然分支无法再继续划分了，但是这样的决策树绝大多情况下没有任何作用，其不具有泛化能力。

通常使用 增益率（gain ratio）来解决这个问题：

Gain_ratio(D,a)=Gain(D,a)IV(a) Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}

其中，IV 被称为属性 a 的 固有值（intrinsic value），IV(a)IV(a) 的定义如下：

IV(a)=−∑v=1V∣Dv∣∣D∣log2∣Dv∣∣D∣ IV(a) = - \sum_{v=1}^{V} \frac{\left| D^v \right|}{\left| D \right|} log_2 \frac{\left| D^v \right|}{\left| D \right|}

属性 a 的可能取值越多，它的固有值 IV 通常越大。

值得注意的是，增益率对取值较少的属性有所偏好，在实际使用中，通常使用启发式算法来综合使用增益率和信息增益。譬如在 C4.5 算法中，首先找出信息增益高于平均水平的属性，然后再从中选择增益率最高的。

基尼指数

信息熵是度量样本集合纯度最常用的一种指标之一，除此之外，还有其他指标来度量样本集合纯度，比如 基尼值：

Gini(D)=∑k=1∣Y∣∑k′≠kpkpk′=1−∑k=1∣Y∣pk2 Gini(D) = \sum_{k=1}^{\left| \mathcal{Y} \right|} \sum_{k' \ne k} p_k p_{k'} = 1 - \sum_{k=1}^{\left| \mathcal{Y} \right|} p_k^2

可以看出，基尼值反映了从数据集中随机抽取两个样本，其类别不一致的概率。因此基尼值越小，数据集的纯度越高。

根据基尼值就可以定义出属性 a 的 基尼指数（Gini index）:

Gini_index(D,a)=∑v=1V∣Dv∣∣D∣Gini(Dv) Gini\_index(D, a) = \sum_{v=1}^{V} \frac{\left| D^v \right|}{\left| D \right|} Gini(D^v)

和信息增益的做法一样，使用基尼指数作为构建决策树的划分方法，首先计算出所有属性的基尼指数，然后选择基尼指数最小的属性即可。