文章目录
前言
本章的决策树旨在了解最基础的决策树知识以及常见的几个决策树算法，至于更近阶的集成学习则不加以介绍。
1、决策树思想
决策树是机器学习一个非常重要的分支，作为最重要的机器学习算法之一，掌握决策树成为学习机器学习的重要目标。
首先需要明确的是，决策树可以解决回归和分类问题，但是这里主要讨论的是分类问题。决策树的学习的基本形式是一种树型结构，和svm、感知机这类的机器学习算法不同，决策树不能学习出来具体的表达式，但能学习出一系列if-then规则。所以我们也认为决策树是定义在特征空间与类空间上的条件概率分布。并且决策树的主要优点有可读性强，分类速度快。而一般的决策树学习过程主要分为三步：特征选择、决策树的生成、决策树的剪枝。下面我们就一般决策树的三种步骤进行详细的介绍。
2、特征选择
要想生成一棵决策树，第一步就是特征选择，那么什么是特征选择呢？
假设给定的训练数据集为：
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
⋯
,
(
x
N
,
y
N
)
}
D={\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)}\}
D={(x1,y1),(x2,y2),⋯,(xN,yN)}
其中
x
i
=
(
x
i
(
1
)
,
x
i
(
2
)
,
⋯
,
x
i
(
n
)
)
T
x_i=(x^{(1)}_i,x^{(2)}_i,\cdots,x^{(n)}_i)^T
xi=(xi(1),xi(2),⋯,xi(n))T为输入实例（特征向量）,
n
n
n为特征的个数，
y
i
∈
{
1
,
2
,
⋯
,
K
}
y_i\in\{1,2,\cdots,K\}
yi∈{1,2,⋯,K}为类标记，
i
=
1
,
2
,
⋯
,
N
i=1,2,\cdots,N
i=1,2,⋯,N，
N
N
N为样本容量。其中
x
x
x叫做输入的特征向量,
x
(
1
)
x^{(1)}
x(1)称为特征，我们在进行生成决策树时，总要选择先从那个特征进行分类，后从那个特征进行分类，这就叫特征选择，我们首先应该选择最具有分类能力的特征作为我们的特征，因为这样能提高学习的效率。到底怎么看出哪个特征是最具分类能力的呢？
这就需要引入一个评判标准叫做信息增益和信息增益比，而信息增益是建立在什么是信息的基础上的，于是又需要引入一个能反映信息多少的概念：熵。
熵表示随机变量不确定性的度量。设
X
X
X是一个取有限个值得离散随机变量，其概率分布为：
P
(
X
=
x
i
)
=
p
i
,
i
=
1
,
2
,
⋯
,
n
P(X=x_i)=p_i,\,\,\,\,\,i=1,2,\cdots,n
P(X=xi)=pi,i=1,2,⋯,n
则随机变量
X
X
X的熵定义为：
H
(
X
)
=
−
∑
i
=
1
n
p
i
log
p
i
H(X)=-\sum\limits_{i=1}^n{p_i\log p_i}
H(X)=−i=1∑npilogpi
在上述式子中，如果
p
i
p_i
pi等于0，那么定义
H
(
X
)
H(X)
H(X)也等于0，说明熵的值为0，不携带任何信息，且
log
\log
log一般取值为
l
o
g
2
log_2
log2。
假设随机变量只取两个值时，例如抛硬币问题，结果只会出现正面和反面，则此时
X
X
X的分布为：
P
(
X
=
正
面
)
=
p
,
P
(
X
=
反
面
)
=
1
−
p
,
0
≤
p
≤
1
P(X=正面)=p,\,\,\,\,P(X=反面)=1-p,\,\,\,\,\,0\le p\le1
P(X=正面)=p,P(X=反面)=1−p,0≤p≤1
此时的熵为
H
(
p
)
=
−
p
log
2
p
−
(
1
−
p
)
l
o
g
2
(
1
−
p
)
H(p)=-p\log_2p-(1-p)log_2(1-p)
H(p)=−plog2p−(1−p)log2(1−p)
而条件熵
H
(
Y
∣
X
)
H(Y|X)
H(Y∣X)表示在已知随机变量
X
X
X的条件下随机变量
Y
Y
Y的不确定性。且有：
H
(
Y
∣
X
)
=
∑
i
=
1
n
p
i
H
(
Y
∣
X
=
x
i
)
H(Y|X)=\sum\limits_{i=1}^n{p_iH(Y|X=x_i)}
H(Y∣X)=i=1∑npiH(Y∣X=xi)
这里的，
p
i
=
P
(
X
=
x
i
)
,
i
=
1
,
2
⋯
,
n
p_i=P(X=x_i),i=1,2\cdots,n
pi=P(X=xi),i=1,2⋯,n。
信息增益的含义就是得知特征
X
X
X的信息而使得类
Y
Y
Y的信息的不确定性减少的程度。计算方式如下：
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
D
D，
∣
D
∣
|D|
∣D∣表示样本容量(样本个数)。设有
K
K
K个类别
C
k
,
k
=
1
,
2
,
⋯
,
K
C_k,\,\,\,\,\,\,\,k=1,2,\cdots,K
Ck,k=1,2,⋯,K，
∣
C
k
∣
|C_k|
∣Ck∣表示属于
C
k
C_k
Ck的样本个数，含义与
D
D
D类似。于是我们有
∑
k
=
1
K
∣
C
k
∣
=
∣
D
∣
\sum\limits_{k=1}^K{|C_k|}=|D|
k=1∑K∣Ck∣=∣D∣。设特征
A
A
A有
n
n
n个不同的取值
{
a
1
,
a
2
,
⋯
,
a
n
}
\{a_1,a_2,\cdots,a_n\}
{a1,a2,⋯,an},根据特征
A
A
A的取值将训练集
D
D
D划分为
n
n
n个子集
D
1
,
D
2
,
⋯
,
D
n
D_1,D_2,\cdots,D_n
D1,D2,⋯,Dn,
∣
D
i
∣
|D_i|
∣Di∣表示子集
D
i
D_i
Di所含样本个数，同样有：
∑
i
=
1
n
∣
D
I
∣
=
∣
D
∣
\sum\limits_{i=1}^n{|D_I|}=|D|
i=1∑n∣DI∣=∣D∣。记子集
D
i
D_i
Di中属于类
C
k
C_k
Ck的样本的集合为
D
i
k
D_{ik}
Dik，
∣
D
i
k
∣
|D_{ik}|
∣Dik∣为
D
i
k
D_{ik}
Dik的样本个数。这一系列定义就是为了后续方便表示信息增益的算法公式。于是便有了信息增益的计算方法如下：
（1）先计算数据集
D
D
D的经验熵
H
(
D
)
H(D)
H(D)
H
(
D
)
=
−
∑
k
=
1
K
∣
C
k
∣
∣
D
∣
log
2
∣
C
k
∣
∣
D
∣
H(D)=-\sum\limits_{k=1}^K{\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}}
H(D)=−k=1∑K∣D∣∣Ck∣log2∣D∣∣Ck∣
（2）计算特征
A
A
A对数据集
D
D
D的经验条件熵
H
(
D
∣
A
)
H(D|A)
H(D∣A)
H
(
D
∣
A
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
∑
i
=
1
n
∣
D
i
k
∣
∣
D
i
∣
log
2
∣
D
i
k
∣
∣
D
i
∣
H(D|A)=\sum\limits_{i=1}^n{\frac{|D_i|}{|D|}}H(D_i)=-\sum\limits_{i=1}^n{\frac{|D_i|}{|D|}\sum\limits_{i=1}^n{\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}}}
H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)=−i=1∑n∣D∣∣Di∣i=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
)
H
A
(
D
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
log
2
∣
D
i
∣
∣
D
∣
g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum\limits_{i=1}^n{\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}}
gR(D,A)=HA(D)g(D,A)HA(D)=−i=1∑n∣D∣∣Di∣log2∣D∣∣Di∣
由此可知
g
R
(
D
,
A
)
g_R(D,A)
gR(D,A)和
g
(
D
,
A
)
g(D,A)
g(D,A)均可以作为选择特征的标准，至于二者有什么区别呢？
g
R
(
D
,
A
)
g_R(D,A)
gR(D,A)可以认为是
g
(
D
,
A
)
g(D,A)
g(D,A)的改进，在《统计学习方法》中是这么介绍的，如果使用信息增益
g
(
D
,
A
)
g(D,A)
g(D,A)来选择特征时，结果会偏向取值类别多的类。例如假设出现一个取值很多的离散变量，此时计算得到的信息增益就会很大，显然这是不符合要求的，于是我们就可以引入了信息增益比这一概念，在信息增益的基础上除以
H
A
(
D
)
H_A(D)
HA(D)，而
H
A
(
D
)
H_A(D)
HA(D)是随着取值种类越多值越大，这样可以平衡分子过大的情况。
另外还有一种选择特征的标准是基尼指数，基尼指数的定义为：
G
i
n
i
(
p
)
=
∑
k
=
1
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
K
p
k
2
Gini(p)=\sum\limits_{k=1}^K{p_k(1-p_k)}=1-\sum\limits_{k=1}^Kp^2_k
Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
其中
K
K
K表示K个类，
p
k
p_k
pk表示样本点属于第
k
k
k个类的概率，也可以表示为
p
k
=
∣
C
k
∣
∣
D
∣
p_k=\frac{|C_k|}{|D|}
pk=∣D∣∣Ck∣。
所以对于一个给定的数据集
D
D
D，其基尼指数为：
G
i
n
i
(
D
)
=
1
−
∑
k
=
1
K
(
∣
C
k
∣
∣
D
∣
)
2
Gini(D)=1-\sum\limits_{k=1}^K(\frac{|C_k|}{|D|})^2
Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2
则在特征A的条件下，集合
D
D
D的基尼指数定义为
G
i
n
i
(
D
,
A
)
=
∣
D
1
∣
∣
D
∣
G
i
n
i
(
D
1
)
+
∣
D
2
∣
∣
D
∣
G
i
n
i
(
D
2
)
Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)
Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
而基尼指数和信息增益与信息增益相比，基尼指数没有对数计算，在信息增益特征选择中，我们选择信息增益大的特征作为分类特征，而基尼指数则选择数值较小的特征作为分类特征。
3 常见的几种决策树生成算法
3.1、ID3算法
ID3算法是采用信息增益作为选择标准的生成算法，对于给定的训练数据集，我们可以通过ID3算法生成一棵决策树。
输入：训练数据集
D
D
D,特征集
A
A
A阈值
ε
\varepsilon
ε
输出：决策树
T
T
T
- 若 D D D中所有的实例属于同一类 C k C_k Ck，则 T T T为单结点树，并将类 C k C_k Ck作为该节点的类标记，返回树 T T T;
- 若 A A A中无特征，则返回 T T T为单结点树，并将 D D D中实例最大的类 C k C_k Ck作为该结点的类标记；
- 当1，2均不满足时，计算 A A A中各特征对 D D D的信息增益，选择信息增益最大的特征 A g A_g Ag；
- 如果选择的特征 A g A_g Ag的信息增益小于阈值 ε \varepsilon ε，则置 T T T为单结点树，并将 D D D中实例数最大的类 C k C_k Ck做为该结点的类标记，返回 T T T；
- 否则对于 A g A_g Ag的每一个可能值 a i a_i ai，使 A g = a i A_g=a_i Ag=ai将 D D D分割为若干非空子集 D i D_i Di，将 D i D_i Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成数 T T T，返回 T T T。
- 对第 i i i个子结点，以 D i D_i Di为训练集，以 A − A g A-{A_g} A−Ag为特征集，递归地调用 1 − 5 1-5 1−5，得到子树 T i T_i Ti，返回 T i T_i Ti。
这里的决策树算法是通用的算法步骤，在后面的其它决策树算法种类中也可以看见这些步骤，我们只需要记住一个决策树是如何产生的即可。在决策树的生成算法中，前几步介绍的都是特例情况，例如在步骤1中，当数据集中所有的y值均为一个类别时，这时树就是单结点，这个结点返回的就是单个类别的值；在2中，若 A A A中无特征，此时只剩下预测值标签一列，返回的树也是单结点树，并且此结点的类标记就是标签值y中类别数最多的类；在3中，排除1、2的特殊情况（存在特征、标签不是单单一种），此时是学习一个棵决策树的开始，而在训练一棵决策树我们知道可以分为三步：选择特征、决策树的生成、决策树的剪枝，此时就是选择特征阶段，而在ID3算法中，选择特征所用的标准为信息增益；在4中，假设我们找到了最大的信息增益特征，但是此时特征的信息增益实在是过小，则算法不会再使用此特征进行分类，直接返回当前树，而当前树的当前结点，则是归为当前结点中实例数最大的类（其实这一步相当于在学习决策树中的跳出循环步骤）；在5中，如果4的条件不满足，从3直接跳转到5，进行决策树的分支，这也是学习决策树的最主要的步骤；在6中，这也是不断学习决策树的步骤保证；
3.2、C4.5算法
C4.5算法和ID3算法从学习步骤上是没有太大差别的，我们可以理解C4.5算法为ID3算法的改进，在ID3算法中用到的是信息增益作为选择新特征的标准，而C4.5算法中使用的是信息增益比作为选择新特征的标准，这可以算是一种改进，而其它所有的算法步骤和ID3中步骤一样。
3.3、CART算法
在CART算法中，需要学习的知识又和前面不一样了，C4.5和ID3是最简单的决策树算法，这两种算法应用于分类树的比较多，但是CART算法是可以完全适应回归树的。
CART的全称就是：classification and regression tree 含义就是分类与回归树，说明CART在处理分类问题和回归问题时均有办法。
在学习CART决策树之前，我们需要知道CART决策树的几个特点，首先CART决策树是一个完全二叉树，内部结点特征的取值为连续值或者离散值中的“是”或“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间划分为有限个单元。当我们面临特征为多类别时，即特征
A
A
A存在类别输入
A
1
、
A
2
、
A
3
A1、A2、A3
A1、A2、A3时，不能使用CART算法将特征
A
A
A一次性分完，只能找到最优的组合例如
A
1
、
A
2
A1、A2
A1、A2和
A
3
A3
A3这种组合形式来进行二分，而后续再对
A
1
、
A
2
A1、A2
A1、A2进行二分，总之CART的树为完全二叉树。
先看比较熟悉的处理分类问题，CART在处理分类问题时和C4.5与ID3唯一的不同点就是选择新特征的标准不一样，CART使用的是基尼指数，在前面介绍特征选择时我们详细介绍了基尼指数，基尼指数和信息熵、信息增益比类似，都能作为决策树选择特征时的标准，当决策树选择使用基尼指数作为标准时，可以不需要进行对数运算，其它的几乎没什么改变，而且在很多实验中表明，其实选择基尼指数和信息增益比学习的树模型带来的误差不大。算法步骤在ID3那一节中已经介绍过了。
CART最主要的还是回归部分，这一部分是ID3和C4.5没有的。下面就来详细介绍CART的回归部分。首先我们要知道，在分类算法中，决策树用来选择特征方法是基于各个特征的基尼指数的大小，基尼指数小的特征说明样本集合不确定性小，也即分类效果好。但是在回归树中，由于预测值是连续的数值，此时不能再使用基尼指数、信息增益比、信息增益来作为选择特征的标准了。此时我们使用的标准就是平方误差最小。
假设
X
X
X与
Y
Y
Y分别未输入和输出变量，并且
Y
Y
Y是连续变量，给定训练数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
⋯
,
(
x
N
,
y
N
)
}
D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}
D={(x1,y1),(x2,y2),⋯,(xN,yN)}
下面考虑如何生成一个回归树。
一棵回归树对应着一个输入空间的一个划分以及划分的单元上的输出值。假设输入空间已经被划分为
M
M
M个单元
R
1
,
R
2
,
⋯
,
R
M
R_1,R_2,\cdots,R_M
R1,R2,⋯,RM，并且在每个单元上
R
m
R_m
Rm上有一个固定的输出值
c
m
c_m
cm，于是回归树模型可以表示为：
f
(
x
)
=
∑
m
=
1
M
c
m
I
(
x
∈
R
m
)
f(x)=\sum\limits_{m=1}^M{c_mI(x\in R_m)}
f(x)=m=1∑McmI(x∈Rm)
当输入空间的划分确定时，可以用平方误差
∑
x
i
∈
R
m
(
y
i
−
f
(
x
i
)
)
2
\sum\limits_{x_i\in R_m}{(y_i-f(x_i))^2}
xi∈Rm∑(yi−f(xi))2来表示回归树对于训练数据的预测误差，用平方误差最小准则来求解每个单元上的最优输出值。设单元
R
m
R_m
Rm上的
c
m
c_m
cm的最优值
c
^
m
{\hat c_m}
c^m就是
R
m
R_m
Rm上所有输入实例
x
i
x_i
xi对应的输出
y
i
y_i
yi的均值，即：
c
^
m
=
a
v
e
(
y
i
∣
x
i
∈
R
m
)
\hat c_m=ave(y_i|x_i\in R_m)
c^m=ave(yi∣xi∈Rm)
我们这里的划分其实是给定的，但是在学习过程中，需要我们找到最优的划分点，假设我们选择第
j
j
j个变量
x
(
j
)
x^{(j)}
x(j)和它的取值
s
s
s，作为切分变量和切分点，并定义切分点
s
s
s将数据切分为两个区域：
R
1
(
j
,
s
)
=
x
∣
x
(
j
)
≤
s
和
R
2
(
j
,
s
)
=
x
∣
x
(
j
)
>
s
R_1(j,s)={x|x^(j)\le s}\,\,\,\,\,\,\,\,和\,\,\,\,\,\,\,\,R_2(j,s)={x|x^(j) >s}
R1(j,s)=x∣x(j)≤s和R2(j,s)=x∣x(j)>s
然后寻找最优的切分变量
j
j
j和最优的切分点
s
s
s，具体的有：
min
j
,
s
[
min
c
1
∑
x
i
∈
R
1
(
j
,
s
)
(
y
i
−
c
1
)
2
+
min
c
2
∑
x
i
∈
R
2
(
j
,
s
)
(
y
i
−
c
2
)
2
]
\mathop {\min }\limits_{j,s} \left[ {\mathop {\min }\limits_{{c_1}} \sum\limits_{{x_i} \in {R_1}(j,s)} {{{({y_i} - {c_1})}^2} + } \mathop {\min }\limits_{{c_2}} \sum\limits_{{x_i} \in {R_2}(j,s)} {{{({y_i} - {c_2})}^2}} } \right]
j,smin⎣⎡c1minxi∈R1(j,s)∑(yi−c1)2+c2minxi∈R2(j,s)∑(yi−c2)2⎦⎤
对固定输入变量
j
j
j可以找到最优切分点
s
s
s。
c
^
1
=
a
v
e
(
y
i
∣
x
i
∈
R
1
(
j
,
s
)
)
和
c
^
2
=
a
v
e
(
y
i
∣
x
i
∈
R
2
(
j
,
s
)
)
{\hat c_1} = ave({y_i}|{x_i} \in {R_1}(j,s))\,\,\,\,\,\,\,\,和\,\,\,\,\,\,\,\,{\hat c_2} = ave({y_i}|{x_i} \in {R_2}(j,s))
c^1=ave(yi∣xi∈R1(j,s))和c^2=ave(yi∣xi∈R2(j,s))
变量所有的变量，找到最优的切分变量
j
j
j和最优的切分点
s
s
s，构成一对
(
j
,
s
)
(j,s)
(j,s)。以此将输入空间划分为两个区域，接着，对每个区域重复上述步骤，直到算法满足条件停止。我们将着整个流程称为最小二乘回归。
下面是生成最小二乘回归树的步骤：
输入：训练数据集 D D D；
输出：回归树 f ( x ) f(x) f(x)。
- 遍历所有的变量 j j j，对固定的切分变量扫描切分点 s s s，选择使得下式达到最小值的 ( j , s ) (j,s) (j,s)； min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \mathop {\min }\limits_{j,s} \left[ {\mathop {\min }\limits_{{c_1}} \sum\limits_{{x_i} \in {R_1}(j,s)} {{{({y_i} - {c_1})}^2} + } \mathop {\min }\limits_{{c_2}} \sum\limits_{{x_i} \in {R_2}(j,s)} {{{({y_i} - {c_2})}^2}} } \right] j,smin⎣⎡c1minxi∈R1(j,s)∑(yi−c1)2+c2minxi∈R2(j,s)∑(yi−c2)2⎦⎤
- 用选定的对 ( j , s ) (j,s) (j,s)划分区域并决定相应的输出值： R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R 2 ( j , s ) = { x ∣ x ( j ) > s } c ^ m = 1 N m ∑ x i ∈ R m y i , x ∈ R m , m = 1 , 2 {R_1}(j,s) = \{ x|{x^{(j)}} \le s\}\,\,\,\,\,\,\,\,{R_2}(j,s) = \{ x|{x^{(j)}} > s\}\\ {\hat c_m} = \frac{1}{{{N_m}}}\sum\limits_{{x_i} \in {R_m}} {{y_i}},\,\,\,\,\,\,\,\,x\in R_m,\,\,\,\,\,\,\,\,m=1,2 R1(j,s)={x∣x(j)≤s}R2(j,s)={x∣x(j)>s}c^m=Nm1xi∈Rm∑yi,x∈Rm,m=1,2
- 继续对两个子区域调用步骤1、2，直到满足条件为止。
- 将输入空间划分为 M M M个区域 R 1 , R 2 , ⋯ , R M R_1,R_2,\cdots,R_M R1,R2,⋯,RM，生成决策树； f ( x ) = ∑ m = 1 M c ^ m I ( x ∈ R m ) f(x)=\sum\limits_{m=1}^M{\hat c_mI(x\in R_m)} f(x)=m=1∑Mc^mI(x∈Rm)
这里算法步骤是引用李航老师的《统计学习方法》。其实在了解算法一步步在干什么，编程实现起来就会很简单。上面的步骤要理解需要注意几个点：
1、在找最优的 ( j , s ) (j,s) (j,s)时，回归树其实是两次遍历，即找 j j j和找 s s s。找 j j j是找最属性，找 s s s是找对应 j j j属性下的最优切分点，最后最优的组合 ( j , s ) (j,s) (j,s)应该是全局最优的；
2、在找到 ( j , s ) (j,s) (j,s)后，CART回归树会把输入空间一分为二，此时划分后的空间会有两个输出值，我们记为 c 1 c_1 c1和 c 2 c_2 c2，求解这两个值的方法就是求所属空间类样本值的平均。再一次二分之后，重复1、2步骤再次二分，这样无限循环下去，还有个重要的点就是这样二分下去，计算的误差是越来越小的，这个误差就是使用 c 1 c_1 c1和 c 2 c_2 c2在所属的空间内计算均方误差，直到最后的误差为0；
3、在进行二分时，我们每一次二分过后产生了一个新的结点，此时仍然需要重新进行遍历找到最优的$(j,s)。
到这里，CART算法的生成我们就介绍完了，后面还有一部分就是CART的剪枝。
4、决策树的剪枝
4.1、ID3和C4.5算法的剪枝
决策树最重要的三大步骤最后一步：剪枝。这一步是保证决策树拥有强泛化能力的保证，在线性模型中存在过拟合情况，决策树是非线性模型，也存在过拟合情况，如果决策树不进行剪枝，那么一棵训练完的决策树很有可能会出现过拟合情况。用一句话来解释决策树的过拟合是：决策树在学习样本点时学习的“太好了”，以至于把一些样本点的特点当作所有样本点的共性而导致过拟合。
先来了解一下决策树的过拟合情况。前面学习了决策树的生成方法，从生成方法中可以看到，一棵决策树在生成过程中是不断迭代生成的，直到不能再生成下去为止，这种情况生成的决策树一般来说都是非常“深”的，这种“深”是基于训练数据学习出来的，在训练集数据中拟合的非常好，但是如果在验证集上进行预测，那么得到的效果就不一定会很好，当在训练集上预测的效果非常好，但是在验证集上的效果非常差时，此时决策树就很有可能存在过拟合现象。解决过拟合的思路也很简单，就是减小决策树的“深度”。一般来说决策树防止过拟合的方法不止剪枝一个，还有一种可靠的方法就是在每次决策树生成新结点的同时，计算此时生成结点后的决策树在验证集上的误差和未生成结点前的决策树在验证集上的误差，将两误差进行比较，如果后者误差大，我们就继续生成新结点，反之则不生成新结点，这种防止过拟合的方法是每一次生成树支时均需要进行一次判断，而且还需要预留一部分数据作为验证集。另一种防止过拟合的方法就是剪枝。前者叫做预剪枝，后者称为后剪枝，预剪枝基于贪心算法来决定是否生成新支点的，这种思想最大的坏处就是容易产生欠拟合。
决策树的剪枝其实思想非常简单，就是对于以生成的一棵完整的决策树，我们从树的最底端往上进行剪枝，剪枝依据的准则由损失函数决定。
假设一棵训练完整的树为
T
T
T，其中叶子结点的个数为
∣
T
∣
|T|
∣T∣，
t
t
t是树
T
T
T的叶结点，该叶结点有
N
i
N_i
Ni个样本点，其中
k
k
k类的样本点有
N
t
k
N_{tk}
Ntk个，
k
=
1
,
2
,
⋯
,
K
k=1,2,\cdots,K
k=1,2,⋯,K，
H
t
(
T
)
H_t(T)
Ht(T)为叶结点
t
t
t上的经验熵，
α
≥
0
\alpha\ge0
α≥0为参数，则决策树学习的损失函数可以定义为：
C
α
(
T
)
=
∑
t
=
1
∣
T
∣
N
t
H
t
(
T
)
+
α
∣
T
∣
C_{\alpha}(T)=\sum\limits_{t=1}^{|T|}{N_tH_t(T)+\alpha|T|}
Cα(T)=t=1∑∣T∣NtHt(T)+α∣T∣
其中经验熵：
H
t
(
T
)
=
−
∑
k
N
t
k
N
t
log
N
t
k
N
t
H_t(T)=-\sum\limits_{k}{\frac{N_{tk}}{N_t}\log{\frac{N_{tk}}{N_t}}}
Ht(T)=−k∑NtNtklogNtNtk
在损失函数中如果我们记：
C
(
T
)
=
∑
t
=
1
∣
T
∣
N
t
H
t
(
T
)
=
−
∑
t
=
1
∣
T
∣
∑
k
=
1
K
N
t
k
log
N
t
k
N
t
C(T)=\sum\limits_{t=1}^{|T|}{N_tH_t(T)=-\sum\limits_{t=1}^{|T|}\sum\limits_{k=1}^K{N_{tk}\log{\frac{N_{tk}}{N_t}}}}
C(T)=t=1∑∣T∣NtHt(T)=−t=1∑∣T∣k=1∑KNtklogNtNtk
这时有：
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
C_{\alpha}(T)=C(T)+\alpha|T|
Cα(T)=C(T)+α∣T∣
这时的损失函数被我们变成两个部分，分为
C
(
T
)
C(T)
C(T)和
α
∣
T
∣
\alpha|T|
α∣T∣这两个部分，第一部分表示的含义表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，至于为什么这个公式可以理解为模型的预测误差，我们可以从公式中找到答案，在公式中，
T
T
T表示叶子结点的个数，叶子结点就是没有子结点的结点，通俗来说，就是分类到底无法再进行生长的那个结点，而
H
t
(
T
)
H_t(T)
Ht(T)的含义是某个叶子结点的经验熵，在前面我们学习经验熵时知道，经验熵反映的是对数据集进行分类的不确定性，所以当经验熵越大时，可以认为分类的效果越差，那么经验熵就能理解为误差了，所以公式
∑
t
=
1
∣
T
∣
N
t
H
t
(
T
)
\sum\limits_{t=1}^{|T|}{N_tH_t(T)}
t=1∑∣T∣NtHt(T)表示的含义就是整棵树的总误差。而对于右边的式子
α
∣
T
∣
\alpha|T|
α∣T∣，这个式子的理解非常简单，
α
\alpha
α就是一个常数，
∣
T
∣
|T|
∣T∣的含义是叶子结点的个数，同时也反映出这棵树的复杂程度，即若
∣
T
∣
|T|
∣T∣越大，说明树越复杂，其与叶子结点个数的乘积，反映的就是整个树模型的结构误差。当
α
\alpha
α的值为0时，说明我们的损失函数只需要考虑预测误差，此时的树应该拟合的越深越好，但是此时树模型的复杂度也就很高。随着
α
\alpha
α的值在不断变大，模型的复杂度在不断下降，模型的拟合程度也在下降，我们在给定
α
\alpha
α的情况下，总能找到一个最好的树。此时这个最好的树就是我们需要的生成树，剪枝的过程就是让树模型不仅仅考虑拟合程度，还需要考虑整个树的复杂度。
注意：ID3和C4.5算法的剪枝思路是一样的
决策树剪枝算法步骤简介：
输入：一棵未剪枝的决策树 T T T和参数 α \alpha α
输出：修剪后的决策树 T α T_{\alpha} Tα
计算每个结点的经验熵；
递归地从树的叶结点向上搜索； 设叶结点回到父结点之前与之后的树分别为: T b T_b Tb与 T a T_a Ta，其对应的损失函数分别为： C α ( T b ) C_\alpha(T_b) Cα(Tb)与 C α ( T a ) C_\alpha(T_a) Cα(Ta)，如果：
C α ( T a ) ≤ C α ( T b ) C_\alpha(T_a)\le C_\alpha(T_b) Cα(Ta)≤Cα(Tb) 则进行剪枝，即将父结点变为新的叶结点；返回第2步，直到不能继续剪枝为止，此时对应的树 T α T_\alpha Tα就是最优的决策树。
上面的决策树剪枝算法有几个需要注意的点：1、计算每个结点的经验熵，而不是计算叶结点的经验熵，这里计算所有结点的经验熵是因为剪枝前我们不知道需要剪枝到哪一个叶结点，所以需要计算所有的叶结点的经验熵。2、这里的误差进行比较其实就是比较父结点和子结点两个结点之间的损失函数大小。3、这就是不断迭代过程，不断迭代最终找到的树就是最优的树，最优的树对应的损失函数就是最小的，且此时不会出现剪枝情况。
4.2、CART算法的剪枝
前面介绍了CART的生成，这一部分要介绍CART的剪枝，关于CART的剪枝部分，又于ID3和C4.5不一样。
在前面介绍剪枝操作时，我们说剪枝操作就是控制树模型的复杂度和预测精度之间关系，在CART剪枝方法中也是如此，CART剪枝其实还是一个比较复杂的事情，我在第一次学习CATR剪枝时也是搞不明白，下面就一起来看看CART的剪枝。
先提供网上几篇有助于我理解CART剪枝的
博客园-CART剪枝实例
知乎-理解CART剪枝
其它的我就是对着李航老师的《统计学习方法》这本书进行学习。
在学习CART剪枝前，我们回顾一下上文树模型的损失函数的形式：
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
C_\alpha(T)=C(T) + \alpha |T|
Cα(T)=C(T)+α∣T∣
其中
C
α
(
T
)
C_\alpha(T)
Cα(T)表示损失函数，
C
(
T
)
C(T)
C(T)表示模型对训练集的预测误差。
∣
T
∣
|T|
∣T∣表示模型的复杂度，
α
\alpha
α是参数，用来权衡训练数据的拟合程度与模型的复杂度。
我们下面学习CART时需要用到上述损失函数，总的来说CART的剪枝分为两步：剪枝形成一个子树序列、在得到的子树序列中选择一个最优的子树。
先来看剪枝形成一个子树序列。
在一棵完整的决策树中，决定我们是否对某一结点进行剪枝的依据就是剪枝完损失函数是否会下降，如果剪枝完损失函数的值下降了，那么就说明我们剪枝是有必要的。假设完整的决策树为
T
0
T_0
T0，对
T
0
T_0
T0的任意内部结点
t
t
t，以
t
t
t为单结点树的损失函数是：
C
α
(
t
)
=
C
(
t
)
+
α
C_\alpha(t)=C(t)+\alpha
Cα(t)=C(t)+α
这个公式其实就可以看出是决策树剪枝完之后的损失函数。
而未对
t
t
t结点进行剪枝，也就是剪枝前的损失函数为：
C
α
(
T
t
)
=
C
(
T
t
)
+
α
∣
T
t
∣
C_\alpha(T_t)=C(T_t)+\alpha |T_t|
Cα(Tt)=C(Tt)+α∣Tt∣
这个式子是以
t
t
t结点为根结点，
T
t
T_t
Tt表示子树的意思。
当
α
=
0
\alpha=0
α=0或者
α
\alpha
α充分小时，有不等式：
C
α
(
T
t
)
<
C
α
(
t
)
C_\alpha(T_t)<C_\alpha(t)
Cα(Tt)<Cα(t)
因为当
α
\alpha
α在增大时，在某一点
α
\alpha
α有：
C
α
(
T
t
)
=
C
α
(
t
)
C_\alpha(T_t)=C_\alpha(t)
Cα(Tt)=Cα(t)
当
α
\alpha
α再增大时，不等式就会反向，这个时候肯定会存在一个临界值
α
=
C
(
t
)
−
C
(
T
t
)
∣
T
t
−
1
∣
\alpha=\frac{C(t)-C(T_t)}{|T_t-1|}
α=∣Tt−1∣C(t)−C(Tt)，
T
t
T_t
Tt与
t
t
t有相同俄损失函数值，其实也指剪枝前和剪枝后有相同的损失函数值，但是此时
t
t
t
的结点少，因此
t
t
t要比
T
t
T_t
Tt更可取，则对
T
−
t
T-t
T−t进行剪枝。
如果记
T
0
T_0
T0中的每个内部结点，均有：
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)
在李航老师的《统计学习方法》中写到，上述的含义是剪枝后整体损失函数减少的程度。所以应该减去
α
\alpha
α最大的支点，但是书中让我们剪去
g
(
t
)
g(t)
g(t)最小的
T
t
T_t
Tt，这一点困扰了我很久。
实际上，在一棵树
T
0
T_0
T0上，
α
\alpha
α的含义是权衡训练数据预测误差和模型复杂度的函数，最开始时
α
\alpha
α的值是0，那么此时是不剪枝是最好的，当
α
\alpha
α的值在不断增大，当增大到某一值时，此时总会出现某个支点，剪枝要比不剪枝要好，但是当
α
\alpha
α的值还在不断增大，这时肯定就会出现第二个结点满足剪枝的情况，但是此时存在两个满足剪枝的结点，CART在选择的时候，选择了剪掉
α
\alpha
α最小的结点，也就是剪掉最先出现被剪情况的结点，这样就得到了
α
1
\alpha_1
α1，并且此时的树
T
0
T_0
T0是被剪枝一部分的，我们将此时的
T
0
T_0
T0赋给
T
1
T_1
T1，并且后续的操作是针对
T
1
T_1
T1这棵树进行的。不断循环上述步骤，就可以得到一系列的子树
T
0
,
T
1
,
⋯
,
T
n
T_0,T_1,\cdots,T_n
T0,T1,⋯,Tn。还有个需要注意的点，就是
T
1
T_1
T1应该是
[
α
1
,
α
2
)
[\alpha_1,\alpha_2)
[α1,α2)区间内的最优子树，在
T
0
T_0
T0树阶段，我们遍历了所有的结点，找到了最小
α
\alpha
α的结点，但是在
T
1
T_1
T1开始剪枝时，我们也遍历了所有的结点，找到最小的
α
\alpha
α。而此时的
α
2
\alpha_2
α2并不是第一次遍历中第二大的
α
\alpha
α值。
另外还需要注意在剪枝时，整个过程是由下往上的，这也和树的结构有关系，我们总是想找到当前最优的树。
在子树序列 T 0 , T 1 , ⋯ , T n T_0,T_1,\cdots,T_n T0,T1,⋯,Tn中通过交叉验证找到最优子树，这里的验证方法就很简单，就是利用独立的测试集来对所有子树进行测试，选择误差最小的子树为我们剪枝算法的结果。回归问题用平方误差，分类问题用基尼指数。
CART剪枝算法
输入：CART算法生成的决策树 T 0 T_0 T0;
输出：最优决策树 T α T_\alpha Tα。
- 设 k = 0 , T = T 0 k=0,T=T_0 k=0,T=T0.
- 设 α = + ∞ \alpha=+\infty α=+∞.
- 自下而上地对各内部结点 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 α = min ( α , g ( t ) ) g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\\ \alpha=\min(\alpha,g(t)) g(t)=∣Tt∣−1C(t)−C(Tt)α=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的叶结点个数。- 对 g ( t ) = α g(t)=\alpha g(t)=α的内部结点 t t t进行剪枝，并对叶结点 t t t以多数表决法决定其类，得到树 T T T.
- 设 k = k + 1 , α k = α , T k = T k=k+1,\alpha_k=\alpha,T_k=T k=k+1,αk=α,Tk=T.
- 如果 T k T_k Tk不是由根结点及两个叶结点构成的树，则回到步骤2，否则令 T k = T n T_k=T_n Tk=Tn.
- 采用交叉验证法在子树序列 T 0 , T 1 , ⋯ , T n T_0,T_1,\cdots,T_n T0,T1,⋯,Tn中选取最优的子树 T α T_\alpha Tα。
上面给出的就是CART剪枝算法的全部流程，其实里面的每一步骤都详细分析过了，第6步应该是跳出算法训练的步骤。
5、总结
决策树的一些基础知识，到这里就已经完结了，其实也只是《统计学习方法》中介绍的内容完结了，这篇文章入门决策树的一个整理，后续还会有更多进阶的学习内容，会放在下面的链接中，由于Matlab编程没有树型结构，那么如果想用matlab编程实现就需要用嵌套结构。