摘要
【学习笔记】
常见的决策树算法有 ID3, C4.5, CART
该篇主要介绍三种决策树算法的基本原理及样例示范
决策树 Decision Tree
递归学习
/algorithm.png)
离散型样例数据
以下为部分离散化处理后的“水稻经济性状数据”,我们以组合、试点、株高、穗长、每穗总粒数、每穗实粒数为特征属性,根据成穗率将样本划分为高、中、低三类
组合 | 试点 | 株高 | 穗长 | 每穗总粒数 | 每穗实粒数 | 成穗率 |
---|---|---|---|---|---|---|
紫两优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$
可见以株高作为划分属性的基尼指数最小