决策树基于树结构进行决策，叶结点对应于决策结果，其他每个结点对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中。最终目的是产生一个泛化能力强，能够处理未知样本的决策树。基本流程遵循简单而直观的分而治之。
决策树基本算法如下：
因为树的生成是递归的，递归算法中很重要的一点就是终止条件，即什么时候达到了叶结点（无法再更细分）就停止递归。
递归的停止条件有如下三种：
1.当前结点包含的样本全属于同一类别，无需划分。
2.当前的属性集为空，或者是当前的样本在属性集合上的值完全相同，无需划分。–标记为叶结点，并将其类别设定为结点所含样本最多的类别。
3.当前结点包含的样本集合为空，不能划分。–标记为叶结点，并将其类别设定为父结点所含样本最多的类别 情况23处理的实质不同：情形二利用当前结点的后验分布，情形三则是把父结点的样本分布作为当前结点的先验分布。
该算法的关键实际上是，每次该如何选择最优属性。书上后续章节则是对该问题的介绍。
一般而言，随着划分过程的不断进行，决策树的分支结点所包含的样本尽量属于同一类别，即结点的“纯度”越高越好。
“信息熵”是度量样本集合纯度最常用的指标。
假定当前样本集合D中第k类样本所占的比例为
p
k
（
k
=
1
,
2
,
.
.
.
,
∣
Y
∣
)
p_k（k=1,2,...,|\mathcal{Y}|)
pk（k=1,2,...,∣Y∣)，则D的信息熵定义为
E
n
t
(
D
)
=
−
∑
k
=
1
∣
Y
∣
p
k
log
2
p
k
Ent(D) = -\sum_{k=1}^{\\|\mathcal{Y}\\|}p_k\log_2p_k
Ent(D)=−k=1∑∣Y∣pklog2pk
该值越小，表示D的纯度越高，极限情况，假如当前集合D中所有样本都属于同一类，则该值为0，在信息论中我们用熵来衡量信息的不确定性。
假定离散属性a有V个可能的取值
{
a
1
,
a
2
,
.
.
.
,
a
V
}
\{a^1,a^2,...,a^V\}
{a1,a2,...,aV},若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为
a
v
a^v
av的样本集合，记为
D
v
D^v
Dv
G
a
i
n
(
D
,
a
)
=
E
n
t
(
D
)
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
E
n
t
(
D
v
)
Gain(D,a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
因此我们可以通过计算划分前后的信息熵，选择信息增益大的那些属性进行决策选择。
例如著名的ID3（iterative Dichotomiser）决策树学习算法就是以信息增益为准则来选择划分属性。
信息增益准则的缺点：对可取值数目较多的属性有所偏好。
改进：使用增益率。
G
a
i
n
_
r
a
t
i
o
=
G
a
i
n
(
D
,
a
)
I
V
(
a
)
Gain\_ratio = \frac{Gain(D,a)}{IV(a)}
Gain_ratio=IV(a)Gain(D,a)
其中IV（a）是属性a的固有值。通常来说，取值数目越大的属性，IV值越大。
I
V
(
a
)
=
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
l
o
g
2
∣
D
v
∣
∣
D
∣
IV(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}
IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣
增益率准则对可取值数目较少的属性有所偏好。C4.5因此没有直接采用增益率，而是采用了一个启发式，先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。
CART（Classifacation and regression tree，分类和回归树），一种著名的决策树学习算法，分类和回归任务都可用。使用基尼指数来选择划分属性，数据集D的纯度可以用基尼值来衡量。
直观含义：从数据集D中随机抽取两个样本，其类别标记不一致的概率。基尼指数越小，表示数据集D的纯度越高。
G
i
n
i
(
D
)
=
∑
k
=
1
Y
∑
k
′
≠
k
p
k
p
k
′
=
1
−
∑
k
=
1
Y
p
k
2
Gini(D) = \sum_{k=1}^{\mathcal{Y}}\sum_{k^{'}\neq k}p_k p_k^{'} \\ = 1 - \sum_{k=1}^{\mathcal{Y}}p_k^2
Gini(D)=k=1∑Yk′=k∑pkpk′=1−k=1∑Ypk2
属性a的基尼指数定义为：
G
i
n
i
_
i
n
d
e
x
(
D
,
a
)
=
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
G
i
n
i
(
D
v
)
Gini\_index(D, a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)
Gini_index(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv)
选择划分后基尼指数最小的属性作为最优划分属性。
首先要对数据集划分成训练集和验证集。
预剪枝：在生成树的过程中，在根据属性分支之前，先对该结点进行判断，如果当前结点的划分不能带来决策树泛化性能（验证集准确度）的提升，则将当前结点划分成叶结点。
后剪枝：自底向上地对非叶结点进行考察，如果该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。优点：欠拟合风险小，保留更多的分支，时间开销增加。
仅有一层的决策树，也被称为决策树桩。
西瓜的属性诸如：颜色、根蒂等都是离散值，而重量、密度等是连续值。在决策树中如何处理连续值？
连续属性离散化技术
C4.5：采用二分法对连续属性进行处理
需要解决的问题：
（1）如何在属性值缺失的情况下，进行划分属性选择？
（2）进行划分属性选择以后，若在该属性上的值缺失，如何对样本进行划分？
在属性值缺失的情况下，为每个样本赋予一个权重。
决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。
多变量决策树，就是能实现“斜划分”甚至更复杂划分的决策树。非叶结点是对属性的线性组合进行测试。
