统计学习方法笔记04

李航. 统计学习方法[M]. 清华大学出版社, 2012.

第5章决策树

5.1 决策树模型与学习

决策树模型的优点：模型具有可读性，分类速度快。
通常包括三个步骤：特征选择、决策树生成和决策树修剪。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。

5.2 特征选择

特征选择的准则是信息增益或信息增益比。

信息增益

熵的定义：

在信息论与概率统计中，熵(entropy)是表示随机变量不确定性的度量，定义为

$H(X) = - \sum_{i=1}^n p_i \log p_i$

其中 $p_i = P(X=x_i)$ 表示取有限值的随机变量X的概率分布。熵越大，随机变量的不确定性就越大。且由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记为H(p)。

条件熵、经验熵、经验条件熵的定义：

条件熵 $H(Y|X)$ 表示在已知随机变量X的条件下随机变量 $Y$ 的不确定性，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对X的数学期望

$H(Y|X) = \sum_{i=1}^n \left[ P(X=x_i) H(Y|X=x_i) \right]$

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。

信息增益的定义：

信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

$g(D,A) = H(D) - H(D|A)$

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益的算法

设训练数据集为D，|D|表示其样本容量，即样本个数。设有K个类Ck，k=1,2,...,K，|Ck|为属于类Ck的样本个数， $\sum |C_k| = |D|$ 。设特征A有n个不同的取值{a1, a2, ..., an}，根据特征A的取值将D划分为n个子集D1, D2, ..., Dn，|Di|为Di的样本个数， $\sum |D_i| = |D|$ 。记子集Di中属于类Ck的样本的集合为Dik，即 $D_{ik}=D_i\cap C_k$ ，|Dik|为Dik的样本个数。于是信息增益的算法如下：

输入：训练数据集D和特征A

输出：特征A对训练数据集D的特征增益g(D,A)

(1) 计算数据集D的经验熵H(D)

$H(D) = - \sum_{k=1}^K \left( \dfrac{|C_k|}{|D|} \log_2 \dfrac{|C_k|}{|D|} \right)$

(2) 计算特征A对数据集D的经验条件熵H(D|A)

$H(D|A) = \sum_{i=1}^n \left( \dfrac{|D_i|}{|D|} H(D_i) \right)= - \sum_{i=1}^n \left[ \dfrac{|D_i|}{|D|} \sum_{k=1}^K \left( \dfrac{|D_{ik}|}{|D_i|} \log_2 \dfrac{|D_{ik}|}{|D_i|} \right)\right]$

(3) 计算信息增益

$g(D,A) = H(D) - H(D|A)$

信息增益比的定义：

以信息增益为划分数据集的特征的依据，存在偏向于选择取值较多的特征的问题。故需要使用信息增益比(information gain ratio)来进行校正。

特征A对训练数据集D的信息增益比 $g_R(D,A)$ 定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵H_A(D)之比，即

$g_R(D,A)=\dfrac{g(D,A)}{H_A(D)} = \dfrac{g(D,A)}{-\sum_{i=1}^n \left( \dfrac{|D_i|}{|D|} \log_2 \dfrac{|D_i|}{|D|} \right)}$

5.3 决策树的生成

ID3算法：利用信息增益准则选择特征。

C4.5算法：使用信息增益比来选择特征。