摘要
【学习笔记】
常见的决策树算法有 ID3, C4.5, CART
该篇主要介绍三种决策树算法的基本原理及样例示范
决策树 Decision Tree
递归学习
离散型样例数据
以下为部分离散化处理后的“水稻经济性状数据”，我们以组合、试点、株高、穗长、每穗总粒数、每穗实粒数为特征属性，根据成穗率将样本划分为高、中、低三类
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| 紫两优10号 | 芜湖 | 较高 | 较低 | 高 | 较高 | 高 |
| 辐优886 | 凤阳 | 较低 | 较高 | 高 | 高 | 高 |
| C两优111 | 凤阳 | 低 | 低 | 较低 | 较低 | 高 |
| 紫两优10号 | 省院 | 较低 | 高 | 低 | 低 | 高 |
| 西农优5号 | 凤阳 | 较低 | 较低 | 较低 | 中 | 高 |
| C两优111 | 芜湖 | 较低 | 较低 | 中 | 中 | 高 |
| 辐优886 | 六安 | 中 | 较低 | 中 | 低 | 中 |
| C两优111 | 全椒 | 较低 | 中 | 中 | 较低 | 中 |
| 西农优5号 | 芜湖 | 中 | 中 | 较高 | 较高 | 中 |
| 紫两优10号 | 六安 | 较高 | 中 | 高 | 高 | 中 |
| C两优111 | 省院 | 低 | 低 | 较低 | 中 | 中 |
| 紫两优10号 | 凤阳 | 中 | 低 | 中 | 较高 | 中 |
| 西农优5号 | 省院 | 中 | 高 | 中 | 较高 | 中 |
| 辐优886 | 芜湖 | 中 | 较高 | 较低 | 较低 | 中 |
| C两优111 | 六安 | 低 | 较低 | 低 | 低 | 中 |
| 辐优886 | 省院 | 高 | 较低 | 较高 | 低 | 低 |
| 辐优886 | 全椒 | 高 | 低 | 中 | 低 | 低 |
| 西农优5号 | 全椒 | 高 | 较低 | 较低 | 较低 | 低 |
| 紫两优10号 | 全椒 | 较高 | 较高 | 较高 | 中 | 低 |
| 西农优5号 | 六安 | 较高 | 较低 | 中 | 较高 | 低 |
重要公式
信息熵(Information Entropy)
$Ent(D) = - \sum_{k=1}^{K} p_{k} log_{2}p_{k}$
设当前样本集 D 中第 K 类样本所占比例为 $p_k$ (k = 1, 2, 3, …, |K|)，K 为类别的总数（对于二元分类来说 K=2）。
Ent(D) 的值越小，则 D 的纯度越高。
该公式规定：若$p=0$，则$plogp=0$
- 这个公式也决定了信息增益的一个缺点：即信息增益对可取值数目多的特征有偏好，因为特征可取的值越多，会导致“纯度”越大，即 Ent(D) 会很小，如果一个特征的离散个数与样本数相等，那么 Ent(D)值会为0
ID3算法 信息增益(Information Gain)
$Gain(D,a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)$
假定离散属性 a 有 V 个可能的取值{$a^1$, $a^2$, …, $a^v$}，如果使用特征 a 来对数据集 D 进行划分，则会产生 V 个分支结点，其中第 v 个结点包含了数据集 D 中所有在特征 a 上取值为 $a^v$ 的样本总数，记为 $D^v$。因此可以根据上面信息熵的公式计算出信息熵，再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予权重 $\frac{|D^v|}{|D|}$ ，即样本数越多的分支节点的影响越大，因此，能够计算出特征 a 对样本集 D 进行划分所获得的“信息增益”
样本示例
若以“株高”作为划分特征，则会产生 5 个分支结点，即 $V = 5$；样本分为 3 类，即 $K = 3$
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| 西农优5号 | 全椒 | 高 | 较低 | 较低 | 较低 | 低 |
| 辐优886 | 省院 | 高 | 较低 | 较高 | 低 | 低 |
| 辐优886 | 全椒 | 高 | 低 | 中 | 低 | 低 |
仅有成穗率低一个类别，可以计算出该样本子集的信息熵为
$Ent(D^1) = -\sum_{k=1}^{3}p_{k}log_{2}p_{k} = -(1\times log_{2}1 + 0\times 0 + 0\times 0) = 0$
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| 紫两优10号 | 六安 | 较高 | 中 | 高 | 高 | 中 |
| 紫两优10号 | 芜湖 | 较高 | 较低 | 高 | 较高 | 高 |
| 紫两优10号 | 全椒 | 较高 | 较高 | 较高 | 中 | 低 |
| 西农优5号 | 六安 | 较高 | 较低 | 中 | 较高 | 低 |
同理，对于株高为较高的样本子集，信息熵为
$Ent(D^2) = 1.5$
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| 辐优886 | 六安 | 中 | 较低 | 中 | 低 | 中 |
| 辐优886 | 芜湖 | 中 | 较高 | 较低 | 较低 | 中 |
| 西农优5号 | 省院 | 中 | 高 | 中 | 较高 | 中 |
| 西农优5号 | 芜湖 | 中 | 中 | 较高 | 较高 | 中 |
| 紫两优10号 | 凤阳 | 中 | 低 | 中 | 较高 | 中 |
$Ent(D^3) = 0$
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| C两优111 | 全椒 | 较低 | 中 | 中 | 较低 | 中 |
| C两优111 | 芜湖 | 较低 | 较低 | 中 | 中 | 高 |
| 紫两优10号 | 省院 | 较低 | 高 | 低 | 低 | 高 |
| 西农优5号 | 凤阳 | 较低 | 较低 | 较低 | 中 | 高 |
| 辐优886 | 凤阳 | 较低 | 较高 | 高 | 高 | 高 |
$Ent(D^4) = 0.722$
| 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|
| C两优111 | 省院 | 低 | 低 | 较低 | 中 | 中 |
| C两优111 | 六安 | 低 | 较低 | 低 | 低 | 中 |
| C两优111 | 凤阳 | 低 | 低 | 较低 | 较低 | 高 |
$Ent(D^5) = 0.918$
$Ent(D) = 1.539$
因此信息增益为
$Gain(D,株高) = Ent(D) - \sum_{v=1}^{5} \frac{|D^v|}{|D|}Ent(D^v) = 1.539 - 0.618 = 0.921$
同理可得
$Gain(D, 组合) = 0.155$
$Gain(D, 试点) = 0.553$
$Gain(D, 穗长) = 0.277$
$Gain(D, 每穗总粒数) = 0.301$
$Gain(D, 每穗实粒数) = 0.116$
因此应选择信息增益最大的“株高”作为划分属性
C4.5算法 增益率(Gain ratio)
$Gain \_ ratio(D,a) = \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 的固有值（intrinsic value）
样本示例
| 编号 | 组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
|---|---|---|---|---|---|---|---|
| 0 | 紫两优10号 | 芜湖 | 较高 | 较低 | 高 | 较高 | 高 |
| 1 | 辐优886 | 凤阳 | 较低 | 较高 | 高 | 高 | 高 |
| 2 | C两优111 | 凤阳 | 低 | 低 | 较低 | 较低 | 高 |
| … | … | … | … | … | … | … | … |
若示例数据添加属性“编号”，那么它的信息增益 $Gain(D, 编号) = Ent(D) = 1.539$
比任何其他属性的增益值都要大，该结点将按“编号”进行划分，决策树的性能会受到很大影响。因此，我们引入固有值（IV）来消除这种不良的影响。
如对于属性“编号”，$IV(编号) = - \sum_{v=1}^{20} \frac{1}{20} log_{2} \frac{1}{20} = 2.996$
$Gain \_ ratio(D, 编号) = \frac{Gain(D, 编号)}{IV(编号)} = \frac{1.539}{2.996} = 0.514$
同理计算出其他属性的增益率为
$Gain \_ ratio ( D, 组合 ) = 0.078$
$Gain \_ ratio ( D, 试点 ) = 0.238$
$Gain \_ ratio ( D, 株高 ) = 0.403$
$Gain \_ ratio ( D, 穗长 ) = 0.129$
$Gain \_ ratio ( D, 每穗总粒数 ) = 0.138$
$Gain \_ ratio ( D, 每穗实粒数 ) = 0.051$
此处由于数据量过小，且截取范围不太合适，导致仍然是按“编号”划分的表现最好…
在更大数据量的实际处理中，增益率能够很好地消除“编号”这种看似表现很好，实则与类别无关的属性的影响
CART算法 基尼指数(Gini index)
$Gini(D) = \sum_{k=1}^{|K|}\sum_{k’ \ne k} p_{k} p_{k’} \\ = 1-\sum_{k=1}^{|K|} p^{2}_{k}$
$Gini \_ index(D,a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} Gini(D^v)$
CART决策树使用基尼指数来选择划分属性。基尼值 Gini(D) 表示数据集 D 的纯度
选择使得划分后基尼指数最小的属性作为最优划分属性，即
$a_{*} = arg_{a\in A} min $ $ Gini \_ index(D,a)$
样本示例
CART算法使用基尼值(Gini)而非信息熵来量化表示数据集D的纯度
我们仍然以“株高”作为示例
$Gini \_ index(D, 株高) = \sum_{v=1}^{5} \frac{|D^v|}{|D|} Gini(D^{v})
\\= \frac{3}{20}0.444 + \frac{5}{20}0.320 + \frac{5}{20}0 + \frac{4}{20}0.625 + \frac{3}{20}0 = 0.272$
同理可得
$Gini \_ index ( D, 组合 ) = 0.600$
$Gini \_ index ( D, 试点 ) = 0.450$
$Gini \_ index ( D, 穗长 ) = 0.537$
$Gini \_ index ( D, 每穗总粒数 ) = 0.543$
$Gini \_ index ( D, 每穗实粒数 ) = 0.600$
可见以株高作为划分属性的基尼指数最小