黑马程序员技术交流社区

标题: 【上海校区】决策树之ID3, C4.5与CART区别与联系 [打印本页]

---

作者: 不二晨    时间: 2018-10-19 09:30
标题: 【上海校区】决策树之ID3, C4.5与CART区别与联系
决策树之ID3, C4.5与CART区别



ID3决策树

著名的ID3决策树以信息增益为准则来选择划分属性；

区别于C4.5决策树算法，C4.5决策树算法是以增益率(gain ratio)来选择最优划分属性
ID3名字中的ID是Iterative Dichotomser(迭代二分类器)的简称
“信息熵(information entropy)是度量样本集合纯度最常用的一种指标。
假设当前样本集合D中第k类样本所占的比例为pk(k=1,2,…,∣Y∣) p_k (k=1,2,\dots, |Y|)p
k
​       
(k=1,2,…,∣Y∣)，则D的信息熵定义为：
Ent(D)=−∑∣Y∣k=1pklog2pk Ent(D) = - \sum_{k=1}^{|Y|}p_k log_2 p_k
Ent(D)=−
k=1
∑
∣Y∣
​       
p
k
​       
log
2
​       
p
k
​       


Ent(D)的值越小，则D的纯度越高。

假定离散属性α \alphaα有V VV个可能的取值α1,α2,…,αV \alpha^1, \alpha^2, \dots, \alpha^Vα
1
,α
2
,…,α
V
，若使用α \alphaα来对样本集D DD进行划分，则会产生V VV个分支节点，其中第v vv个分支节点包含了D DD中所有在属性α \alphaα上取值为αv \alpha^vα
v
的样本，记为Dv D^vD
v
.
我们可以根据上式计算出Dv D^vD
v
的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重∣Dv∣∣D∣ \frac{|D^v|}{|D|}
∣D∣
∣D
v
∣
​       
，即样本数越多的分支节点的影响越大，于是可计算出用属性α \alphaα对样本集D DD进行划分所获得的“信息增益”(information gain)

Gain(D,α)=Ent(D)−∑Vv=1∣Dv∣∣D∣Ent(Dv) Gain(D,\alpha) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
Gain(D,α)=Ent(D)−
v=1
∑
V
​       

∣D∣
∣D
v
∣
​       
Ent(D
v
)

一般而言，信息增益越大，则意味着使用属性α \alphaα来进行划分所获得的“纯度提升”越大。因此，我们可使用信息增益来进行决策树的划分属性选择，即选择属性α∗=arg maxα∈A Gain(D,α) \alpha_* = arg \ max_{\alpha \in A} \ Gain(D, \alpha)α
∗
​       
=arg max
α∈A
​       
  Gain(D,α)

注：使用信息增益与使用信息增益率作为属性选择的差别：从信息增益的定义式不难发现，若以信息增益作为属性选择依据，则该决策树生成时更倾向于选择可取值数目较多的属性（西瓜书中也有**“实际上，信息增益准则对可取值数目较多的属性有所偏好”）.因此C4.5决策树算法作为ID3决策树算法的改进版，引入增益率，来消除这种不利影响，但“增益率准则对可取数目较少的属性有所偏好**”，
因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找到信息增益高于平均水平的属性，在从中选择增益率最高的。“
C4.5决策树

ID3决策树使用信息增益准则划分属性，但信息增益准则对可取值数目较多的属性有所偏好。为了解决这个问题，Quinlan于1993提出C4.5决策树作为ID3决策树算法的改进版，不再直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优划分属性，采用与上式相同的符号表示，增益率定义为：

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


其中

IV(a)=−∑Vv=1∣Dv∣∣D∣log2DvD IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2 \frac{D^v}{D}
IV(a)=−
v=1
∑
V
​       

∣D∣
∣D
v
∣
​       
log
2
​       

D
D
v

​       


成为属性α \alphaα的“固有值”(intrinsic value)。属性α \alphaα的可能取值数目越多（即V越大），则IV(α) IV(\alpha)IV(α)的值通常会越大。

可参考西瓜书P78 P_78P
7
​       
8示例
需要注意的是，引入增益率是为了消除“信息增益准则对可取值数目较多的属性有所偏好”，，但“增益率准则对可取数目较少的属性有所偏好”，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找到信息增益高于平均水平的属性，在从中选择增益率最高的。

CART决策树

CART决策树使用“基尼指数”(Gini index)来选择划分属性，
假设当前样本集合D中第k类样本所占的比例为pk(k=1,2,…,∣Y∣) p_k (k=1,2,\dots, |Y|)p
k
​       
(k=1,2,…,∣Y∣)，数据集D的纯度可用基尼值来度量：
Gini(D)=∑∣y∣k=1∑k′≠kpkpk′=1−∑∣y∣k=1p2k Gini(D) = \sum_{k=1}^{|y|} \sum_{k^{'}\neq k}p_k p_{k^{'}}= 1 - \sum_{k=1}^{|y|} p_{k}^{2}
Gini(D)=
k=1
∑
∣y∣
​       

k
′


̸
​       
=k
∑
​       
p
k
​       
p
k
′


​       
=1−
k=1
∑
∣y∣
​       
p
k
2
​       


直观来说，Gini(D) Gini(D)Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini GiniGini越小，则数据集D DD的纯度越高。

采用与上式相同的符号表示，属性α \alphaα的基尼指数定义为：

Giniindex(D,α)=∑Vv=1∣Dv∣∣D∣Gini(Dv) Gini_index(D,\alpha) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)
Gini
i
​       
ndex(D,α)=
v=1
∑
V
​       

∣D∣
∣D
v
∣
​       
Gini(D
v
)

于是，我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即a∗=arg minα∈A Gini_index(D,α)​ a_* ={arg \ min}_{\alpha \in A} \ Gini\_index(D, \alpha)​a
∗
​       
=arg min
α∈A
​       
  Gini_index(D,α)​
---------------------
【转载】
作者：dby_freedom
原文：https://blog.csdn.net/Dby_freedom/article/details/82051751

---

作者: 不二晨    时间: 2018-10-25 10:47

---

作者: 魔都黑马少年梦    时间: 2018-11-1 16:22

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2