今天以周志华老师的西瓜为例，复盘一下三种决策树算法。
文章目录
数据：
信息增益（ID3算法）
信息熵表示信息的混乱程度，熵越大数据越混乱。分类的目的是为了使同一类别的数据尽可能“纯净”，因此追求尽量小的信息熵。
信息增益表示分类前后信息熵的差值。分类前信息熵是定值，分类后信息熵越小，信息增益越大。因此我们追求尽量大的信息增益值。
entropy(D)表示未分类时数据D的信息熵:
e
n
t
r
o
p
y
(
D
)
=
−
∑
i
=
1
k
p
(
c
i
)
l
o
g
2
p
(
c
i
)
entropy(D)=-\sum_{i=1}^k p(c_i)log_2p(c_i)
entropy(D)=−i=1∑kp(ci)log2p(ci)
其中，
c
i
c_i
ci表示样本的分类变量取i的概率。
entropy(D,A)表示按照属性A分类后数据D的信息熵：
e
n
t
r
o
p
y
(
D
,
A
)
=
∑
i
=
1
m
∣
D
i
∣
∣
D
∣
e
n
t
r
o
p
y
(
D
i
)
entropy(D,A)=\sum_{i=1}^m\frac{|D_i|}{|D|}entropy(D_i)
entropy(D,A)=i=1∑m∣D∣∣Di∣entropy(Di)
其中，
∣
D
i
∣
D
∣
\frac{|D_i}{|D|}
∣D∣∣Di表示样本的描述变量A取
D
i
D_i
Di的概率。
信息增益即信息熵的差值:
g
a
i
n
(
D
,
A
)
=
e
n
t
r
o
p
y
(
D
)
−
e
n
t
r
o
p
y
(
D
,
A
)
gain(D,A)=entropy(D)-entropy(D,A)
gain(D,A)=entropy(D)−entropy(D,A)
以西瓜为例，分类变量为是否为好瓜，描述变量为前面6个属性。
e n t r o p y ( D ) = − 8 17 l o g 2 8 17 − 9 17 l o g 2 9 17 = 0.998 entropy(D)=-\frac{8}{17}log_2\frac{8}{17}-\frac{9}{17}log_2\frac{9}{17}=0.998 entropy(D)=−178log2178−179log2179=0.998
e
n
t
r
o
p
y
(
D
,
色
泽
)
=
−
6
17
e
n
t
r
o
p
y
(
青
绿
)
−
6
17
e
n
t
r
o
p
y
(
乌
黑
)
−
5
17
e
n
t
r
o
p
y
(
浅
白
)
=
−
6
17
[
−
3
6
l
o
g
2
3
6
−
3
6
l
o
g
2
3
6
]
−
6
17
[
−
4
6
l
o
g
2
4
6
−
2
6
l
o
g
2
2
6
]
−
5
17
[
−
1
5
l
o
g
2
1
5
−
4
5
l
o
g
2
45
]
=
0.889
\begin{aligned} entropy(D,色泽)&=-\frac{6}{17}entropy(青绿)-\frac{6}{17}entropy(乌黑)-\frac{5}{17}entropy(浅白)\\[2ex] &=-\frac{6}{17}[-\frac{3}{6}log_2\frac{3}{6}-\frac{3}{6}log_2\frac{3}{6}]-\frac{6}{17}[-\frac{4}{6}log_2\frac{4}{6}-\frac{2}{6}log_2\frac{2}{6}]-\frac{5}{17}[-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2{4}{5}]\\[2ex] &=0.889 \end{aligned}
entropy(D,色泽)=−176entropy(青绿)−176entropy(乌黑)−175entropy(浅白)=−176[−63log263−63log263]−176[−64log264−62log262]−175[−51log251−54log245]=0.889
g
a
i
n
(
D
,
色
泽
)
=
e
n
t
r
o
p
y
(
D
)
−
e
n
t
r
o
p
y
(
D
,
色
泽
)
=
0.109
gain(D,色泽)=entropy(D)-entropy(D,色泽)=0.109
gain(D,色泽)=entropy(D)−entropy(D,色泽)=0.109
同理，计算其他属性的信息增益，最终得出“纹理”的信息增益最大，因此选择它作为分裂属性。
信息增益比率（C4.5算法）
由信息熵的计算公式可以看出，信息增益有一个先天缺陷：更倾向于选取分类个数多的属性。若有一个分类变量，对每一个样本都取不同值，那么每个样本为一个类别，每个类别的信息熵都是0，信息熵最小，但显然是不合理的。因此，提出信息增益比率进行调整。
g
a
i
n
_
r
a
t
i
o
(
D
,
A
)
=
g
a
i
n
(
D
,
A
)
s
p
l
i
t
I
n
f
o
(
D
,
A
)
gain\_ratio(D,A)=\frac{gain(D,A)}{splitInfo(D,A)}
gain_ratio(D,A)=splitInfo(D,A)gain(D,A)
s
p
l
i
I
n
f
o
(
D
,
A
)
=
−
∑
i
=
1
m
∣
D
i
∣
∣
D
∣
l
o
g
2
(
∣
D
i
∣
∣
D
∣
)
spliInfo(D,A)=-\sum_{i=1}^m\frac{|D_i|}{|D|}log_2(\frac{|D_i|}{|D|})
spliInfo(D,A)=−i=1∑m∣D∣∣Di∣log2(∣D∣∣Di∣)
信息增益比率即信息增益除以一个“分类信息熵”，这个分母其实就是把描述变量A当做分类变量时计算得出的信息熵值。可以看出，类别越多，分类信息熵越大。
还是以西瓜为例：
s p l i I n f o ( D , 色 泽 ) = − 6 17 l o g 2 6 17 − 6 17 l o g 2 6 17 − 5 17 l o g 2 5 17 = 0.613 spliInfo(D,色泽)=-\frac{6}{17}log_2\frac{6}{17}-\frac{6}{17}log_2\frac{6}{17}-\frac{5}{17}log_2\frac{5}{17}=0.613 spliInfo(D,色泽)=−176log2176−176log2176−175log2175=0.613
g a i n _ r a t i o = 0.109 0.613 = 0.178 gain\_ratio=\frac{0.109}{0.613}=0.178 gain_ratio=0.6130.109=0.178
类似的可以计算出其他属性的信息增益比率。
需要注意的是，增益率对类别数量少的属性有所偏好，因此，C4.5算法并不直接选择增益率最大的属性进行分裂，而是先选出信息增益高于平均水平的属性，在从这些属性中选择信息增益率最高的，其实就是对两种方法的缺点进行了一下权衡。
基尼指数（CART算法）
值得一提的是，CART算法要求决策树为二叉树，当分类变量大于2个的时候，将一个类别视为一类，其余类别视为另一类，计算基尼指数选取最优的划分方法。
基尼指数表示随机抽取两个样本，分类变量值不一致的概率，概率越大表示纯度越低。因此，追求的基尼指数越小越好。
G
i
n
i
(
D
)
=
∑
i
=
1
k
p
k
(
1
−
p
k
)
=
1
−
∑
i
−
1
k
p
k
2
Gini(D)=\sum_{i=1}^kp_k(1-p_k)=1-\sum_{i-1}^kp_k^2
Gini(D)=i=1∑kpk(1−pk)=1−i−1∑kpk2
按照描述变量A进行分类后，基尼指数为：
G
i
n
i
(
D
,
A
)
=
∑
i
=
1
m
∣
D
i
∣
∣
D
∣
G
i
n
i
(
D
i
)
Gini(D,A)=\sum_{i=1}^m\frac{|D_i|}{|D|}Gini(D_i)
Gini(D,A)=i=1∑m∣D∣∣Di∣Gini(Di)
再看西瓜的例子：
以色泽分类后，基尼指数
G
i
n
i
(
D
,
色
泽
)
=
6
17
G
i
n
i
(
青
绿
)
+
6
17
G
i
n
i
(
乌
黑
)
+
5
17
(
浅
白
)
=
6
17
[
1
−
(
3
6
)
2
−
(
3
6
)
2
]
+
6
17
[
1
−
(
4
6
)
2
−
(
4
6
)
2
]
+
5
17
[
1
−
(
1
5
)
2
−
(
4
5
)
2
]
\begin{aligned} Gini(D,色泽)&=\frac{6}{17}Gini(青绿)+\frac{6}{17}Gini(乌黑)+\frac{5}{17}(浅白)\\[2ex] &=\frac{6}{17}[1-(\frac{3}{6})^2-(\frac{3}{6})^2]+\frac{6}{17}[1-(\frac{4}{6})^2-(\frac{4}{6})^2]+\frac{5}{17}[1-(\frac{1}{5})^2-(\frac{4}{5})^2] \end{aligned}
Gini(D,色泽)=176Gini(青绿)+176Gini(乌黑)+175(浅白)=176[1−(63)2−(63)2]+176[1−(64)2−(64)2]+175[1−(51)2−(54)2]
同理算出其他属性的GIni指数，选取最小的作为分类属性即可。
手动复盘，如有错误，敬请指正。