决策树 - ID3和C4.5

决策树学习通常包含三个步骤:特征选择、决策树的生成、决策树的修剪。

决策树学习的思想主要来源于:

  • 由Quinlan提出的ID3算法和C4.5算法
  • 由Breiman等人提出的CART算法

决策树模型与学习

决策树模型

决策树由节点(node)和有向边(directed edge)组成。

节点分为内部节点(表示特征/属性)和叶子节点(表示分类)。

> 决策树与if-then规则

从根节点到叶子节点对应一条路径,亦即一条规则,不同规则间互斥,所有规则组成全体,即互斥完备性

> 决策树与条件概率分布

给定特征条件下类的条件概率分布。

决策树分类时强行将样本分到条件概率最大的那一类中去。

决策树学习

给定训练数据集
$$
D = { (x_1, y_1),(x_2,y_2), \cdots, (x_N,y_N) }
$$
其中

  • $x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$为输入向量(特征向量),$n$为样本的特征维度
  • $y_i \in { 1,2,\cdots,K }$为每个样本的标记,$K$为总类数
  • $i=1,2,\cdots,N$,$N$为样本容量

与训练数据集不矛盾的决策树可能有多个,也可能没有;我们需要求矛盾最小、对测试集泛化能力较高的那个决策树。

特征选择

经典的特征选择准则有两个:信息增益信息增益比

信息增益

熵&经验熵

在信息论和概率统计中,(Entropy)是随机变量不确定性的度量。

设$X$是有限取值的离散型随机变量,其概率分布为
$$
P(X=x_i)=p_i \text{, $i=1,2,\cdots,n$}
$$
随机变量$X$的
$$
H(X)=-\sum_{i=1}^N p_i \log p_i \text{, 特别的 $0 \log 0 = 0$}
$$
的定义可知,随机变量的(不确定性)与随机变量的取值无关。这其实不难理解:确定性变量是随机性变量的一种特例,对于确定性变量取值1还是1000它们的不确定性应该是一样的,都为0。

的单位:bit(当对数底为2时)或者nat(当对数底为$e$时)。

当随机变量$X$完全确定($P(X=x_k)=1$且$P(X=x_{\text{else}})=0$)或者完全不确定($P(X=x_{\text{any}})=1/n$)时,$H(X)$取得最小值(0)或者最大值($\log n$)。

当随机变量只取0、1时
$$
H(p) = -p \log_2 p - (1-p) \log_2 (1-p)
$$

如果此随机变量的熵值通过极大似然估计得到,称之为经验熵

条件熵&经验条件熵

条件熵(Conditional Entropy)

设随机变量$X$和$Y$的联合分布为
$$
P(X=x_i, Y=y_j) = p_{ij}, i=1,2,\cdots,n;j=1,2,\cdots,m
$$
条件熵$H(Y|X)$表示已知随机变量$X$的条件下随机变量$Y$的不确定性
$$
H(Y|X) = \sum_{i=1}^n [ P(X=x_i) \cdot H(Y|X=x_i) ]
$$
如果随机变量$X$和$Y$独立,则$H(Y|X=x_i)=H(Y)$,此时条件熵
$$
H(Y|X) = \sum_{i=1}^n [ P(X=x_i) \cdot H(Y) ] = H(Y)
$$
如果随机变量$Y$的条件熵通过极大似然估计得到,称之为经验条件熵

经验之意,即从观察数据中进行推断。

我们将随机变量Y的熵与已知X条件下Y的条件熵的差称之为互信息(Mutual Information)。

信息增益

信息增益(Information Gain)指,当得知特征$X$的信息时,$Y$不确定性减少的程度。

特征A对训练数据集D的信息增益
$$
g(D,A) = H(D) - H(D|A)
$$
决策树中信息增益的概念就相当于训练数据集中特征互信息

训练数据集中不同的特征具有不同的信息增益,信息增益较大的特征具有更强的分类能力。

计算信息增益举例:

类别的先验分布:$P(Y=是)=9/15=3/5$, $P(Y=否)=9/15=2/5$

类别的熵:$H(Y)=-3/5\log3/5-2/5\log2/5 = 0.971$

该训练数据集有4个特征:年龄、有工作、有自己的房子、信贷情况,分别用A、B、C、D表示。

以年龄为例计算其对训练数据集的信息增益

  1. 随机变量取值数值化(有序分类):青年 $\to$ 1, 中年 $\to$ 2,老年 $\to$ 3

  2. 年龄的先验分布: $P(A=1)=P(A=2)=P(A=3)=1/3$

  3. 训练数据集D在年龄A已知时的条件概率分布:
    $$
    \begin{split}
    P(Y=0|A=1)=3/5, P(Y=1|A=1)=2/5 \\
    P(Y=0|A=2)=2/5, P(Y=1|A=2)=3/5 \\
    P(Y=0|A=3)=1/5, P(Y=1|A=3)=4/5
    \end{split}
    $$
    此时
    $$
    \begin{split}
    H(Y|A=1) &= - 3/5 \log_2 3/5 - 2/5 \log_2 2/5 = 0.9709506 \\
    H(Y|A=2) &= - 2/5 \log_2 2/5 - 3/5 \log_2 3/5 = 0.9709506 \\
    H(Y|A=3) &= - 1/5 \log_2 1/5 - 4/5 \log_2 4/5 = 0.7219281
    \end{split}
    $$

  1. 训练数据集D在年龄A已知时的条件熵:
    $$
    \begin{split}
    H(Y|A) &= P(A=1)H(Y|A=1) + P(A=2)H(Y|A=2) + P(A=3)H(Y|A=3) \\
    &= 1/3 \times 0.9709506 + 1/3 \times 0.9709506 + 1/3 \times 0.7219281 \\
    &= 0.8879431 \\
    \end{split}
    $$

  2. 信息增益
    $$
    \begin{split}
    g(Y,A) &= H(Y) - H(Y|A) \\
    &= 0.971 - 0.8879431 \\
    &= 0.083
    \end{split}
    $$
    同理得
    $$
    \begin{split}
    g(Y,B) &= 0.324 \\
    g(Y,C) &= 0.420 \\
    g(Y,D) &= 0.363
    \end{split}
    $$
    经过比较,特征C(有自己的房子)对训练数据集的信息增益最大,所以选择特征C作为最优的分类特征。

信息增益比

信息增益的偏向性

根据信息增益的定义$H(D,A)=H(D)-H(D|A)$,如果数据集D中某个特征A的采样值为恒定常数,那么$H(D|A)=0$,即$H(D,A)=H(D)$,此时特征A对数据集D的信息增益达到最大值——D的熵值。那么我们应该选择特征A作为最优划分特征吗?显然不。这是信息增益在描述采样值为常数的特征时的弊端。除此之外,信息增益在计算连续型随机变量时也会遇到不小的问题。

所以信息增益适合于计算离散特征,并且该随机变量取值的采样数不宜过少。

信息增益的相对性

所谓的信息增益,字面意思就是确定性的增加量,这个确定性的增加是相对数据集D的熵的,这意味着,D的熵越大,信息增益就可能越大;反之越小。

信息增益比的定义

于是,我们将信息增益除以数据集的熵,用相对的确定性增量来描述最优分类特征:
$$
g_R(D,A) = \frac{g(D,A)}{H(D)} = \frac{H(D)-H(D|A)}{H(D)} = 1 - \frac{H(D|A)}{H(D)}
$$

决策树的生成

决策树学习的两个经典算法:ID3算法、C4.5算法。

生成算法只能用来生成树,十分容易过拟合。

生成的树需要进行剪枝,去拟合。

ID3算法

算法核心是在决策树的各个节点应用信息增益的准则选择特征。

根据信息增益选择特征的方法还是属于极大似然。

> ID3算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CONST 信息增益阈值
DEF ID3算法(数据集D, 特征集合A):
IF D中所有样本属于同一类C:
T为单节点树,将C作为该节点的类标记,返回T
ELSE IF A为空:
T为单节点树,将D中样本数最多的那个类作为该节点的类标记,返回T
ELSE:
计算特征集合A中各个特征对数据集D的信息增益,确定信息增益最大的特征Ag
IF Ag < 信息增益阈值:
T为单节点树,将D中样本数最多的那个类作为该节点的类标记,返回T
ELSE:
FOR 采样值v IN 特征Ag中的所有采样值的集合:
从数据集D中划分出特征Ag值为v的子集Dv
T的一个子节点 = 递归调用 ID3算法(数据集Dv, 特征集合{A-Ag})
返回T

C4.5算法

将ID3算法中的 信息增益 替换为 信息增益比 即可。

为什么叫做C4.5算法而不叫ID4算法呢?据说作者发表完ID3算法后此领域过于火爆导致ID4、ID5等名字有人用了。

决策树的剪枝

前面提到,决策树的生成算法倾向于拟合训练数据,极易出现过拟合。

剪枝(Pruning) 即考虑模型的复杂度,对生成的树进行简化。

剪枝 通过极小化 损失函数 实现。

> 剪枝原理

假设:树$T$的叶子节点的个数为$|T|$,$t$是树$T$的一个叶子节点,该叶子节点有$N_t$个样本点,其中属于第$k$类的样本点有$N_{tk}$个。

则,叶子节点$t$的经验熵为
$$
H_t(T) = - \sum_{k=1}^K \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}
$$
决策树学习的损失函数为
$$
L_\alpha(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T|
$$
每个叶子节点的样本数越少、经验熵越小,同时总叶子节点数越少,损失越小。

这里损失函数由两部分组成:

  1. 决策树模型对数据集的预测误差

$$
L(T) = \sum_{t=1}^{|T|} N_t H_t(T) = - \sum_{t=1}^{|T|} \sum_{k=1}^K N_{tk} \log \frac{N_{tk}}{N_t}
$$

  1. 决策树模型的模型复杂度

$$
C(T) = |T|
$$

剪枝的具体实现如下:

剪枝前的叶子节点集合为{A,B,C,D},计算其损失函数$L_1$

剪枝后的叶子节点集合为{E,C,D},计算其损失函数$L_2$

因为$L_2 < L_1$,所以我们剪掉以E为根节点的子树,E的 类别 标记为样本数最多的那一个。

参考文献

CART算法见< http://localhost:4002/ml/20191122-edcd.html >

----- For reprint please indicate the source -----
0%