结论速递
本文索引
0 决策树概述
0.1 决策树
决策树实际上就是一种if-then规则的集合。同时，李航在《统计机器学习》中指出，决策树还表示给定特征条件下类的条件概率分布。
这一条件概率分布定义在特征空间的一个划分（partition）上，将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布，决策树的一条路径对应于划分中的一个单元。
决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
0.2 决策树的学习
决策树的学习本质上是从训练数据集中归纳出一组分类规则，事实上，和训练数据集不矛盾的决策树可能有很多个，也可能一个也没有。学习决策树的目标是，获得一个与训练数据矛盾较小的决策树，同时这个决策树具有很好的泛化能力。
决策树的学习算法通常是贪心算法，递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这一过程对应着对特征空间的划分，也对应着决策树的构建。
决策树的学习算法包含特征选择、决策树生成与决策树的剪枝过程，由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择，决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
Hunt算法是许多决策树算法的基础。
设 D t D_t Dt是与节点 t t t相关联的训练记录集，而 y = y 1 , y 2 , . . . , y c y={y_1,y_2,...,y_c} y=y1,y2,...,yc是类标号，Hunt算法的递归定义如下：
- 如果 D t D_t Dt中所有记录都属于同一个类 y y y，则 t t t是叶节点，用 y t y_t yt标记。
- 如果 D t D_t Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将 D t D_t Dt中的记录分布到子女结点中。然后，对于每个子女节点，递归地调用该算法。
决策树的学习算法必须解决下面两个问题：
- 如何分裂训练记录？需要确定属性测试条件（即选择最佳划分的度量），和分类方法。
选择最佳划分的度量通常是根据划分后子女节点不纯性的程度，这里引入了信息论中信息熵等概念。 - 如何停止分裂过程？需要有结束条件，以终止决策树的生长过程。
1 信息论基础
1.1 信息熵、条件熵、信息增益
前面提到了，选择决策树每个节点最佳划分的度量，通常是根据划分后子女节点不纯性的程度。
信息熵是用于度量不确定性的函数，在论文《A Mathematical Theory of Communication》中有具体定义，离散信息熵形式如下：
H
(
Y
)
=
E
Y
[
−
log
2
p
(
Y
)
]
=
−
∑
k
=
1
K
p
(
y
k
)
log
2
p
(
y
k
)
H(Y)=\Epsilon_Y[-\log_2p(Y)]=-\sum_{k=1}^{K}p(y_k)\log_2p(y_k)
H(Y)=EY[−log2p(Y)]=−k=1∑Kp(yk)log2p(yk)
离散信息熵的最小值为0并且在单点分布时取到，离散熵最大值为 log K \log K logK且在离散均匀分布时取到。
在决策树的分裂过程中，我们不但需要考察节点的不确定性或纯度，还要考察子节点的平均不确定性或平均纯度来决定是否进行分裂。
子节点的产生来源于决策树分支的条件，因此我们要研究在给定条件下随机变量的平均信息熵或条件熵（即条件分布的不确定性）。
H ( Y ∣ X ) = E X [ E Y ∣ X [ − log 2 p ( Y ∣ X ) ] ] H(Y|X)=\Epsilon_X[\Epsilon_{Y|X}[-\log_2 p(Y|X)]] H(Y∣X)=EX[EY∣X[−log2p(Y∣X)]]
有了信息熵和条件熵的概念定义后，可以定义信息增益（Information Gain），即节点分裂之后带来的不确定性的降低或者纯度的提高。
具体定义为，在得到了随机变量 X X X的取值信息后，随机变量 Y Y Y不确定性的平均减小量为
G ( Y , X ) = H ( Y ) − H ( Y ∣ X ) G(Y,X)=H(Y)-H(Y|X) G(Y,X)=H(Y)−H(Y∣X)
信息增益必定非负，而且如果随机变量Y和X相互独立，无论我们是否知道X的信息，都不会对Y的不确定性产生影响，此时的信息增益为0。
信息增益G(Y,X)在本质上就是p(y,x)关于p(y)p(x)的KL散度
1.2 思考题
- 证明如下关系：
G ( Y , X ) = H ( X ) − H ( X ∣ Y ) G(Y,X) = H(X)-H(X|Y) G(Y,X)=H(X)−H(X∣Y) G ( Y , X ) = H ( X ) + H ( Y ) − H ( Y , X ) G(Y,X) = H(X)+H(Y)-H(Y,X) G(Y,X)=H(X)+H(Y)−H(Y,X) G ( Y , X ) = H ( Y , X ) − H ( X ∣ Y ) − H ( Y ∣ X ) G(Y,X) = H(Y,X)-H(X|Y)-H(Y|X) G(Y,X)=H(Y,X)−H(X∣Y)−H(Y∣X)
上述均有
左式=
−
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
p
(
y
k
)
p
(
x
m
)
p
(
y
k
,
x
m
)
-\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2{\dfrac{p(y_k)p(x_m)}{p(y_k,x_m)}}
−∑k=1K∑m=1Mp(yk,xm)log2p(yk,xm)p(yk)p(xm)
对式一：
右式=
H
(
X
)
−
H
(
X
∣
Y
)
H(X)-H(X|Y)
H(X)−H(X∣Y)
=
E
X
[
−
log
2
p
(
X
)
]
−
E
Y
[
E
X
∣
Y
[
−
log
2
p
(
X
∣
Y
)
]
]
\Epsilon_X[-\log_2p(X)]-\Epsilon_Y[\Epsilon_{X|Y}[-\log_2 p(X|Y)]]
EX[−log2p(X)]−EY[EX∣Y[−log2p(X∣Y)]]
=
−
∑
m
=
1
M
p
(
x
m
)
log
2
p
(
x
m
)
−
∑
k
=
1
K
p
(
y
k
)
∑
m
=
1
M
p
(
x
m
∣
y
k
)
log
2
p
(
x
m
∣
y
k
)
-\sum_{m=1}^{M}p(x_m)\log_2p(x_m)-\sum_{k=1}^{K}p(y_k)\sum_{m=1}^{M}p(x_m|y_k)\log_2p(x_m|y_k)
−∑m=1Mp(xm)log2p(xm)−∑k=1Kp(yk)∑m=1Mp(xm∣yk)log2p(xm∣yk)
=
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
[
log
2
p
(
y
k
,
x
m
)
p
(
y
k
)
−
log
2
p
(
x
m
)
]
\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)[\log_2{\dfrac {p(y_k,x_m)}{p(y_k)}}-\log_2{p(x_m)}]
∑k=1K∑m=1Mp(yk,xm)[log2p(yk)p(yk,xm)−log2p(xm)]
=
−
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
p
(
y
k
)
p
(
x
m
)
p
(
y
k
,
x
m
)
-\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2{\dfrac{p(y_k)p(x_m)}{p(y_k,x_m)}}
−∑k=1K∑m=1Mp(yk,xm)log2p(yk,xm)p(yk)p(xm)
=左式
得证。
对式二：
右式=
H
(
X
)
+
H
(
Y
)
−
H
(
Y
,
X
)
H(X)+H(Y)-H(Y,X)
H(X)+H(Y)−H(Y,X)
=
E
X
[
−
log
2
p
(
X
)
]
+
E
Y
[
−
log
2
p
(
Y
)
]
−
E
(
Y
,
X
)
p
(
y
,
x
)
[
−
log
2
p
(
Y
,
X
)
]
]
\Epsilon_X[-\log_2p(X)]+\Epsilon_Y[-\log_2p(Y)]-\Epsilon_{(Y,X)~p(y,x)}[-\log_2 p(Y,X)]]
EX[−log2p(X)]+EY[−log2p(Y)]−E(Y,X) p(y,x)[−log2p(Y,X)]]
=
−
∑
m
=
1
M
p
(
x
m
)
log
2
p
(
x
m
)
−
∑
k
=
1
K
p
(
y
k
)
log
2
p
(
y
k
)
+
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
(
y
k
,
x
m
)
-\sum_{m=1}^{M}p(x_m)\log_2p(x_m)-\sum_{k=1}^{K}p(y_k)\log_2p(y_k)+\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2(y_k,x_m)
−∑m=1Mp(xm)log2p(xm)−∑k=1Kp(yk)log2p(yk)+∑k=1K∑m=1Mp(yk,xm)log2(yk,xm)
=
−
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
(
x
m
)
−
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
(
y
k
,
)
+
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
(
y
k
,
x
m
)
-\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2(x_m)-\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2(y_k,)+\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2(y_k,x_m)
−∑k=1K∑m=1Mp(yk,xm)log2(xm)−∑k=1K∑m=1Mp(yk,xm)log2(yk,)+∑k=1K∑m=1Mp(yk,xm)log2(yk,xm)
=
−
∑
k
=
1
K
∑
m
=
1
M
p
(
y
k
,
x
m
)
log
2
p
(
y
k
)
p
(
x
m
)
p
(
y
k
,
x
m
)
-\sum_{k=1}^{K} \sum_{m=1}^{M}p(y_k,x_m)\log_2{\dfrac{p(y_k)p(x_m)}{p(y_k,x_m)}}
−∑k=1K∑m=1Mp(yk,xm)log2p(yk,xm)p(yk)p(xm)
=左式
得证。