决策树是一种基本的分类与回归方法。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。
1 决策树模型与学习 分类决策树模型是一种描述对实例进行分类的树形结构。决策树是由节点和有向边组成，结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。
通常特征选择的准则是信息增益或信息增益比。
2.1 信息增益
在信息论和概率统计中，熵表示随机变量不确定性的度量，则熵的定义为：
H
(
p
)
=
−
∑
i
=
1
n
p
i
l
o
g
p
i
H(p)=-sum_{i=1}^n p_i logp_i
H(p)=−i=1∑npilogpi
对应地，熵越大，随机变量的不确定性越大。
0
≤
H
(
p
)
≤
l
o
g
n
0leq H(p) leq logn
0≤H(p)≤logn
条件熵
p
(
Y
∣
X
)
p(Y|X)
p(Y∣X) 表示在已知随机变量X的条件下随机变量Y的不确定性。
H
(
Y
∣
X
)
=
−
∑
i
=
1
n
p
i
H
(
Y
∣
X
=
x
i
)
H(Y|X)=-sum_{i=1}^n p_i H(Y|X=x_i)
H(Y∣X)=−i=1∑npiH(Y∣X=xi)
信息增益表示得知特征X的信息而使得类Y的信息的不准确性减少的程度。
特征A对于数码据集D的信息增益
g
(
D
,
A
)
g(D,A)
g(D,A),定义为经验熵
H
(
D
)
H(D)
H(D)和条件经验熵
H
(
D
∣
A
)
H(D|A)
H(D∣A)之差。
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
g(D,A)=H(D)-H(D|A)
g(D,A)=H(D)−H(D∣A)
熵
H
(
Y
)
H(Y)
H(Y)与条件熵
H
(
Y
∣
X
)
H(Y|X)
H(Y∣X)之差成为互信息。决策树中的信息增益等价于训练数据集中类与特征的互信息。
信息增益算法：
输入：训练数据集D和特征A
输出：信息增益
g
(
D
,
A
)
g(D,A)
g(D,A)
(1）计算经验熵
H
(
D
)
H(D)
H(D)
H
(
D
)
=
−
∑
k
=
1
K
∣
D
k
∣
∣
D
∣
l
o
g
2
∣
D
k
∣
∣
D
∣
H(D)=-sum_{k=1}^K frac{|D_k|}{|D|} log_2frac{|D_k|}{|D|}
H(D)=−k=1∑K∣D∣∣Dk∣log2∣D∣∣Dk∣
(2)计算经验条件熵
H
(
D
∣
A
)
H(D|A)
H(D∣A)
H
(
D
∣
A
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
=
−
∑
k
=
1
n
∣
D
i
k
∣
∣
D
i
∣
l
o
g
2
∣
D
i
k
∣
∣
D
i
∣
H(D|A)=-sum_{i=1}^n frac{|D_i|}{|D|}H(D_i)=-sum_{k=1}^nfrac{|D_{ik}|}{|D_i|}log_2frac{|D_{ik}|}{|D_i|}
H(D∣A)=−i=1∑n∣D∣∣Di∣H(Di)=−k=1∑n∣Di∣∣Dik∣log2∣Di∣∣Dik∣
(3)计算信息增益
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
g(D,A)=H(D)-H(D|A)
g(D,A)=H(D)−H(D∣A)
信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。
g
R
(
D
,
A
)
=
g
(
D
,
A
)
H
A
(
D
)
g_R(D,A)=frac{g(D,A)}{H_A(D)}
gR(D,A)=HA(D)g(D,A)
ID3算法和核心决策各个结点上应用信息增益准则选择特征。
C4.5对ID3算法做了改进，通过信息增益比特征选择准则。
在决策树学习中将已生成的树进行简化的过程称为剪枝。用以防止过拟合。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个数为
∣
T
∣
|T|
∣T∣，t是树T的叶结点，该结点有
N
t
N_t
Nt个样本点，其中k类的样本点有
N
t
k
N_{tk}
Ntk个，k=1,2…k.
H
t
(
T
)
H_t(T)
Ht(T)为叶结点t上的经验熵，
α
≥
0
alpha geq 0
α≥0为参数，则决策树学习的损失函数可以定义为：
C
α
(
T
)
=
∑
t
=
1
∣
T
∣
N
N
t
H
t
(
T
)
+
α
∣
T
∣
C_alpha(T)=sum_{t=1}^{|T|N}N_tH_t(T)+alpha|T|
Cα(T)=t=1∑∣T∣NNtHt(T)+α∣T∣
其中经验熵为：
H
t
(
T
)
=
−
∑
k
N
t
k
N
t
l
o
g
N
t
k
N
t
H_t(T)=-sum_k frac{N_{tk}}{N_t}log frac{N_{tk}}{N_t}
Ht(T)=−k∑NtNtklogNtNtk
那么损失函数可以写为:
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
C_alpha(T)=C(T)+alpha|T|
Cα(T)=C(T)+α∣T∣
C
(
T
)
C(T)
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度。
∣
T
∣
|T|
∣T∣表示模型复杂度，参数
α
≥
0
alpha geq0
α≥0控制两者之间的影响。其中，
α
=
0
alpha =0
α=0表示只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
分类与回归树（classification and regression tree,CART）既可以用于回归，也可以用于分类。
5.1 回归树的生成 决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树。
最小二乘回归树生成算法
输入：训练数据集D；
输出：回归树
f
(
x
)
f(x)
f(x)。
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
（1）选择最优切分变量
j
j
j与切分点
s
s
s，求解
m
i
n
j
,
s
[
m
i
n
c
1
∑
x
i
∈
R
1
(
j
,
s
)
(
y
i
−
c
1
)
2
+
m
i
n
c
2
∑
x
i
∈
R
2
(
j
,
s
)
(
y
i
−
c
2
)
2
]
min_{j,s}[min_{c_1}sum_{x_i in R_1(j,s)}(y_i-c_1)^2+min_{c_2}sum_{x_i in R_2(j,s)}(y_i-c_2)^2]
minj,s[minc1xi∈R1(j,s)∑(yi−c1)2+minc2xi∈R2(j,s)∑(yi−c2)2]
遍历变量j，对固定的切分量
j
j
j扫描切分点
s
s
s，选择使得上式达到最小值的
(
j
,
s
)
(j,s)
(j,s)。
（2）用选定的对
(
j
,
s
)
(j,s)
(j,s)划分区域并决定相应的输出值：
R
1
(
j
,
s
)
=
{
x
j
≤
s
}
R_1(j,s)=left{x^j leq sright}
R1(j,s)={xj≤s},
R
2
(
j
,
s
)
=
{
x
j
>
s
}
R_2(j,s)=left{x^j > sright}
R2(j,s)={xj>s}
c
^
m
=
1
N
m
∑
x
i
∈
R
m
(
j
,
s
)
y
i
hat c_m=frac{1}{N_m}sum_{x_iin R_m(j,s)}y_i
c^m=Nm1xi∈Rm(j,s)∑yi
其中
x
∈
R
m
,
m
=
1
,
2
xin R_m,m =1,2
x∈Rm,m=1,2。
（3）继续对两个子区域调用步骤（1）（2），直至满足停止条件。
（4）将输入空间划分为M个区域
R
1
,
R
2
,
.
.
,
R
M
R_1,R_2,..,R_M
R1,R2,..,RM，生成决策树：
f
(
x
)
=
∑
m
=
1
M
c
^
m
I
(
x
∈
R
m
)
f(x)=sum_{m=1}^Mhat c_mI(x in R_m)
f(x)=m=1∑Mc^mI(x∈Rm)
基尼指数—分类问题中，假设有K个类，样本点属于第k类的概率为
p
k
p_k
pk，则概率分布的基尼指数定义为
G
i
n
i
(
p
)
=
∑
k
=
1
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
K
p
k
2
Gini(p)=sum_{k=1}^Kp_k(1-p_k)=1-sum_{k=1}^Kp_k^2
Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
对于二分类，则基尼指数为：
G
i
n
i
(
p
)
=
2
p
(
1
−
p
)
Gini(p)=2p(1-p)
Gini(p)=2p(1−p)
对于给定样本集合D，其基尼指数为
G
i
n
i
(
D
)
=
1
−
∑
k
=
1
K
(
∣
C
k
∣
∣
D
∣
)
2
Gini(D)=1-sum_{k=1}^K(frac{|C_k|}{|D|})^2
Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2
基尼指数越大，不确定性越大。
CART剪枝算法
输入：CART算法生成的决策树
T
0
T_0
T0;
输出：最优决策树
T
α
T_alpha
Tα。
（1）设
k
=
0
,
T
=
T
0
k=0,T=T_0
k=0,T=T0。
（2） 设
α
=
+
∞
alpha=+infin
α=+∞
（3）自下而上地对各内部结点
t
t
t计算
C
(
T
t
)
,
∣
T
t
∣
C(T_t),|T_t|
C(Tt),∣Tt∣以及
g
(
t
)
=
C
(
t
)
−
c
(
T
t
)
∣
T
t
∣
−
1
g(t)=frac{C(t)-c(T_t)}{|T_t|-1}
g(t)=∣Tt∣−1C(t)−c(Tt)
α
=
m
i
n
(
α
,
g
(
t
)
)
alpha=min(alpha,g(t))
α=min(α,g(t))
这里，
T
t
T_t
Tt表示
t
t
t为根结点的子树，
C
(
T
t
)
C(T_t)
C(Tt)是对训练数据的预测误差，
∣
T
t
∣
|T_t|
∣Tt∣ 是
T
t
T_t
Tt的叶结点个数。
（4）对
g
(
t
)
=
α
g(t)=alpha
g(t)=α的内部结点
t
t
t进行剪枝，并对叶结点
t
t
t以多数表决法决定其类，得到树
T
T
T。
（5）设
k
=
k
+
1
,
α
k
=
α
,
T
k
=
T
k=k+1,alpha_k=alpha,T_k=T
k=k+1,αk=α,Tk=T。
（6）如果
T
k
T_k
Tk不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则
T
k
=
T
n
T_k=T_n
Tk=Tn。
（7）采用交叉验证法在子树序列
T
0
,
T
1
,
.
.
.
,
T
n
T_0,T_1,...,T_n
T0,T1,...,Tn中选取最优子树
T
α
T_alpha
Tα。
