一、决策树的基本框架
决策树是一类基本的机器学习算法。它是基于树状结构来进行决策，从上到下依次进行判断，最终得到模型的决策。一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶子节点；叶子节点对应决策结果，其他每个节点则对应一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶子节点的路径对应了一个判断测试序列。决策树的生成是一个递归过程。在决策树的算法中，如果出现下述三种情形之一，会终止继续划分，返回递归结果：1、当前节点包含的样本都是同一类别；2、当前节点能够划分的属性集合为空，或者节点中的样本在属性上的取值相同；3、当前节点不包含任何样本。决策算法的关键或不同在于：如何选择最优的划分属性。一般来说，随着决策树划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能是同一类别。
二、基于信息增益的划分
“熵”（Entropy）是度量样本集合纯度（purity）最常用的一种指标。假定当前样本集合
D
D
D中第
k
k
k类样本所占的比例为
p
k
(
k
=
1
,
2
,
.
.
.
.
∣
Y
∣
)
p_k(k = 1,2,....|Y|)
pk(k=1,2,....∣Y∣)，则样本集D的熵可以定义为：
E
n
t
r
o
p
y
(
D
)
=
−
∑
k
=
1
∣
Y
∣
p
k
l
o
g
2
p
k
Entropy(D) =- \displaystyle\sum_{k=1}^{|Y|}p_k{log_2}p_k
Entropy(D)=−k=1∑∣Y∣pklog2pk；
E
n
t
r
o
p
y
(
D
)
Entropy(D)
Entropy(D)的值越小，表示D的纯度越高。假定离散属性
a
a
a有
V
V
V个可能的取值
a
1
,
a
2
,
.
.
.
,
a
V
{a^1,a^2,...,a^V}
a1,a2,...,aV，若使用
a
a
a来对样本集
D
D
D进行划分，则会产生
V
V
V个分支节点，其中第
v
v
v个分支节点包含了
D
D
D中所有在属性
a
a
a上取值为
a
v
a^v
av的样本，即为
D
v
D^v
Dv。首先计算出
D
v
D^v
Dv的熵
E
n
t
r
o
p
y
(
D
v
)
Entropy(D^v)
Entropy(Dv)，再考虑到不同的分子节点所包含的样本数不同，给分支节点赋予权重
∣
D
v
∣
/
∣
D
∣
|D^v|/|D|
∣Dv∣/∣D∣，也就是样本数越多的分支节点的影响越大，基于此，可以计算出用属性
a
a
a对样本集
D
D
D进行划分所获得的“信息增益”（information gain）。
G
a
i
n
(
D
,
a
)
=
E
n
t
r
o
p
y
(
D
)
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
E
n
t
r
o
p
y
(
D
v
)
Gain(D, a) = Entropy(D) - \displaystyle\sum_{v=1}^{V}\dfrac{|D^v|}{|D|}{Entropy(D^v)}
Gain(D,a)=Entropy(D)−v=1∑V∣D∣∣Dv∣Entropy(Dv)。一般而言，信息增益越大，则意味着使用属性
a
a
a来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。ID3决策树学习算法就是以信息增益为准则来选择划分属性。
三、基于信息增益率的划分
由于信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优划分属性。增益率定义为：
G
a
i
n
R
a
t
i
o
(
D
,
a
)
=
G
a
i
n
(
D
,
a
)
I
V
(
a
)
GainRatio(D, a) = \dfrac{Gain(D,a)}{IV(a)}
GainRatio(D,a)=IV(a)Gain(D,a)。其中
I
V
(
a
)
=
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
l
o
g
2
∣
D
v
∣
∣
D
∣
IV(a) = - \displaystyle\sum_{v=1}^{V}\dfrac{|D^v|}{|D|}{log_2{\dfrac{|D^v|}{|D|}}}
IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣。
I
V
(
a
)
IV(a)
IV(a)称为属性
a
a
a的“固有值”(intrinsic value)。属性
a
a
a的可能取值数目越多（即
V
V
V越大），则
I
V
(
a
)
IV(a)
IV(a)的值通常会很大。增益率准则对可取数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用一个启发式的方法：先从候选划分属性中找出增益率高于平均水平的属性，再从中选择增益率最高的。
四、基于基尼系数的划分
CART决策树使用“基尼系数”（Gini index）来选择划分属性。
G
i
n
i
(
D
)
=
∑
k
=
1
∣
y
∣
∑
k
′
=
/
k
p
k
p
k
′
Gini(D) = \displaystyle\sum_{k=1}^{|y|}\displaystyle\sum_{{k'}{=}\llap{/\,}k}{p_k}{p_k'}
Gini(D)=k=1∑∣y∣k′=/k∑pkpk′ = 1 -
∑
k
=
1
∣
y
∣
p
k
2
\displaystyle\sum_{k=1}^{|y|}{p_k^2}
k=1∑∣y∣pk2。直观来说
G
i
n
i
(
D
)
Gini(D)
Gini(D)反映了从数据集
D
D
D中随机抽取两个样本，其类别标记不一致的概率。因此，
G
i
n
i
(
D
)
Gini(D)
Gini(D)越小，则数据集D的纯度越高。属性
a
a
a的基尼指数定义为：
G
i
n
i
I
n
d
e
x
(
D
,
a
)
=
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
G
i
n
i
(
D
v
)
GiniIndex(D,a) = \displaystyle\sum_{v=1}^{V}\dfrac{|D^v|}{|D|}{Gini(D^v)}
GiniIndex(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv)，在候选集合
A
A
A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
五、sklearn实践决策树
接下来，python的sklearn包来实践上述几种决策树
from sklearn
import tree
from sklearn
import datasets
, model_selection
iris
= datasets
.load_iris
()
X
= iris
.data
Y
= iris
.target
x_train
,x_test
, y_train
, y_text
= model_selection
.train_test_split
(X
, Y
, test_size
=0.2, random_state
=0)
classification_tree
= tree
.DecisionTreeClassifier
()
classification_tree
.fit
(x_train
, y_train
)
print(classification_tree
.feature_importances_
)
print(classification_tree
.predict
(x_test
))
总结
使用决策树也是可以做特征重要性分析的：按照划分决策树的过程中选择特征的先后顺序来判断特征的重要性。在sklearn中有一个feature_importances_属性可以输出特征的重要性。
参考资料
周志华《机器学习》http://www.siyuanblog.com/?p=821
