决策树是树模型的基础模型，随机森林、提升树、梯度提升树等都是基于决策树演化而来。
决策树以及其演化（CART, GBDT,XGBoost）在数据挖掘竞赛中有广泛的应用，是机器学习的基础模型。
熵表示随机变量不确定性的度量。设X是一个取有限个离散值的随机变量，其概率分布为
p
(
X
=
x
i
)
=
p
i
,
i
=
1
,
2
,
…
,
n
p(X = x_i) = p_i, i = 1, 2,ldots, n
p(X=xi)=pi,i=1,2,…,n
则随机变量X的熵定义为
H
(
X
)
=
−
∑
i
=
1
n
p
i
l
o
g
p
i
H(X) = -sum_{i = 1}^np_ilogp_i
H(X)=−∑i=1npilogpi
熵越大表示随机变量的不确定性越大
信息增益表示在一个条件下信息复杂度（不确定性）减小的程度。
信息增益公式如下：
G
a
i
n
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
Gain(D, A) = H(D) - H(D|A)
Gain(D,A)=H(D)−H(D∣A)
H
(
D
)
H(D)
H(D)：熵（D的不确定性）
H
(
D
∣
A
)
H(D|A)
H(D∣A)：条件熵（在A的条件下D的不确定性）
信息增益比，就是信息增益率。公式如下：
G
a
i
n
R
a
t
i
o
(
D
,
A
)
=
G
a
i
n
(
D
,
A
)
H
A
(
D
)
Gain_{Ratio}(D, A) = frac{Gain(D, A)}{H_A(D)}
GainRatio(D,A)=HA(D)Gain(D,A)
其中
H
A
(
D
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
l
o
g
2
∣
D
i
∣
∣
D
∣
H_A(D) = -sum_{i = 1}^nfrac{|D_i|}{|D|}log_2frac{|D_i|}{|D|}
HA(D)=−∑i=1n∣D∣∣Di∣log2∣D∣∣Di∣
表示随机取样的两个样本不一致的概率。即从数据集D随机抽取两个样本，类别标记不同的概率。
在分类问题中，假设有M个类别，第k个类别的概率为
p
k
p_k
pk，则基尼系数的公式为：
G
i
n
i
(
p
)
=
∑
k
=
1
M
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
M
p
k
2
Gini(p)=sum_{k=1}^Mp_k(1-p_k)=1-sum_{k=1}^Mp_k^2
Gini(p)=∑k=1Mpk(1−pk)=1−∑k=1Mpk2
回归和分类是机器学习中两个基本任务，其中决策树算法是分类任务的典型代表。
回归输出的是连续值，分类输出的是离散值
决策树是自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分成内部结点和叶子结点。内部结点表示一个属性或特征，叶子结点表示类别。根据根结点的划分，样本被分到不同的子节点中，再根据子节点的特征进一步划分，直到所有样本都划分到某一个类别（叶子结点）中。
决策树的本质：分支语句
决策树种类：
按任务分：分类树和回归树
按特征选择分：ID3决策树算法（任务：分类；树：多叉树；特征选择：信息增益）、C4.5决策树算法（任务：分类；树：多叉树；特征选择：信息增益比）、CART决策树算法（任务：回归、分类；树：二叉树；特征选择：基尼系数、平方误差）
ID3决策树的特征选择标准是信息增益，但偏向于取值较多的特征
ID3缺点：1、偏向于取值较多的特征；2、对训练样本的质量的依赖性强
C4.5决策树的特征选择标准是信息增益比，但偏向于取值较少的特征
ID3缺点：1、偏向于取值较少的特征；2、分治的策略，局部最优
输出的是离散值，特征选择标准是基尼系数
输入：训练数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
)
}
D = {{(x_1, y_1),(x_2,y_2),ldots,(x_n,y_n)}}
D={(x1,y1),(x2,y2),…,(xn,yn)}
输出：提升树
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∈R1(j,s)}(y_i-c_1)^2 +min_{c_2}sum_{x_i∈R2(j,s)}(y_i-c_2)^2 ]
minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2]
遍历变量
j
j
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
∣
x
(
j
)
<
=
s
,
R
2
(
j
,
s
)
=
x
∣
x
(
j
)
>
s
R_1(j,s)={x|x^{(j)}<=s},R_2(j,s)={x|x^{(j)}>s}
R1(j,s)=x∣x(j)<=s,R2(j,s)=x∣x(j)>s
c
m
=
1
N
m
∑
x
i
∈
R
m
(
j
,
s
)
y
i
,
x
∈
R
m
,
m
=
1
,
2
c_{m}=frac{1}{N_m}sum_{x_i∈R_m(j,s)}y_i,x∈R_m,m=1,2
cm=Nm1∑xi∈Rm(j,s)yi,x∈Rm,m=1,2
（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件
（4）将输入空间划分为M个区域
R
1
,
R
2
,
…
,
R
m
R_1,R_2,ldots,Rm
R1,R2,…,Rm,生成决策树
f
(
x
)
=
∑
m
=
1
M
c
m
I
(
x
∈
R
m
)
f(x)=sum_{m=1}^Mc_mI(x∈R_m)
f(x)=∑m=1McmI(x∈Rm)
输出的是连续值，特征选择标准是平方误差
决策树总结 决策树优点简单、可解释性好；
效率高
不适用于数据量小
减枝代价大
