4.1基本流程
决策树，一类常见机器学习方法，希望从给定训练集学得一个模型用以对新示例进行分类。
一般，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。
从根结点到每个叶结点的路径对应了一个判定测试序列。
决策树学习目的是为产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单直观的“分而治之”策略。
决策树基本算法里，导致递归返回的三种情形：1、当前结点包含样本全属于同一类别，无需划分；2、当前属性集为空，或是所有样本在所有属性上取值相同，无法划分（该情况下，将当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别）3、当前结点包含的样本集合为空，不能划分。（该情况下，同样将当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别）
情形2是在利用当前结点的后验分布，而情形3则是把父结点的样本分布作为当前结点的先验分布。
4.2划分选择
决策树学习的关键-如何选择最优划分属性
4.2.1信息增益
“信息熵”常用于度量样本集合纯度。
样本集合D中第k类样本所占比例为
p
k
(
k
=
1
,
2
,
.
.
.
,
∣
y
∣
)
p_k(k=1,2,...,|y|)
pk(k=1,2,...,∣y∣)，则D的信息熵定义如下（注， 信息熵Ent(D)的值越小，则D的纯度越高。）
离散属性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，由上述计算信息熵式子可进而计算出
D
v
D^v
Dv的信息熵。考虑到不同分支结点所包含样本数不同，给分支结点赋予权重
∣
D
v
∣
∣
D
∣
\frac{|D^v|}{|D|}
∣D∣∣Dv∣，即样本数越多的分支结点影响越大，故可计算出用该属性a对样本D进行划分所获得的“信息增益”
一般而言，信息增益越大，意味着使用属性a进行划分所获得的“纯度提升”越大。故而可用信息增益进行决策树的划分属性的选择。
ID3算法即以信息增益为准则来选择划分属性。
（具体利用信息增益进行属性划分的例子见西瓜书P74-P75）
一个需要解决的问题：信息增益准则对可取值数目较多的属性有所偏好
理解：如若通过编号属性来划分各个样本，显然产生的每个分支只含有一个样本，这些分支的纯度达到最大。但是很显然，这样构建出来的决策树不具有泛化能力。
问题的解决改进：使用“增益率”来选择最优划分属性
增益率定义如下，其中IV(a)称为属性a的“固有值”
属性a的可能取值数目越多即V越大，IV(a)的值通常会越大。
问题：增益率准则对取值数目较少的属性有偏好
因此，C4.5算法并非直接选择增益率最大的候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
4.2.3基尼系数
CART决策树使用"基尼指数"来选择划分属性.
基尼值反映了从数据集D中随即抽取两个样本，其类别标记不一致的概率，因此可用于度量数据集D的纯度，基尼值越小，则数据集D的纯度越高。
计算属性a的基尼系数
在候选属性集合中，选择使得划分后基尼指数最小的属性作为最优划分属性，即
4.3剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”。
预剪枝：指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
注：
1、判断决策树泛化性能提升与否的性能评估方法-假定为留出法。
2、采用信息增益准则进行划分属性选择。
4.3.1预剪枝
例子见书上P80-P81
书中例子最终所得决策树为
“决策树桩”：仅有一层划分的决策树
预剪枝使得决策树的很多分支都没有"展开”，不仅降低过拟合风险，还显著减少决策树的训练时间开销和测试时间开销。
但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可
能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高;预剪枝基于"贪心"本质禁止这些分支展开 给预剪枝决策树带来了“欠拟合”的风险。
4.3.2后剪枝
例子见书上P82-P83
书中例子最终所得决策树为
后剪枝决策树通常比预剪枝决策树保留更多的分支，且后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
但是，由于后剪枝过程是在生成完全决策树之后进行的 并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
4.4连续与缺失值
4.4.1连续值处理
讨论如何在决策树学习中使用连续属性-连续属性离散化技术，如二分法
C4.5决策树算法中采用二分法对连续属性进行处理。
给定样本集D，连续属性a。
将属性a在数据集D上出现的n个不同取值进行从小到大排序，记
{
a
1
,
a
2
,
.
.
.
,
a
n
}
\{a^1,a^2,...,a^n\}
{a1,a2,...,an}.
基于划分t可将D分为子集
D
t
−
D_t^-
Dt−和
D
t
+
D_t^+
Dt+，其中
D
t
−
D_t^-
Dt−包含那些在属性a上取值不大于t的样本，而
D
t
+
D_t^+
Dt+则包含那些在属性a上取值大于t的样本。
由于对相邻属性
a
i
a^i
ai和
a
i
+
1
a^{i+1}
ai+1而言，t在二者区间之中取任意值多产生的划分结果相同，因此我们把二者区间的中位点
a
i
+
a
i
+
1
2
\frac{a^i+a^{i+1}}{2}
2ai+ai+1作为候选划分点。
对连续属性a，我们可考察包含n-1个元素的候选划分点集合
之后，便可以像离散属性值一样来考察这些划分点，选择最优划分点进行样本集合的划分。
G
a
i
n
(
D
,
a
,
t
)
Gain(D,a,t)
Gain(D,a,t)是样本集D基于划分点t二分后的信息增益，故可选择使得
G
a
i
n
(
D
,
a
,
t
)
Gain(D,a,t)
Gain(D,a,t)最大化的划分点即为最优划分点。
举例：
属性“密度”，17个训练样本取值各不相同，该属性的候选划分点集合包含16个候选值：
T
密度
=
{
0.244
,
0.294
,
0.351
,
0.381
,
0.420
,
0.459
,
0.518
,
0.574
,
0.600
,
0.621
,
0.636
,
0.648
,
0.661
,
0.681
,
0.708
,
0.746
}
T_{密度}=\{0.244,0.294, 0.351, 0.381, 0.420, 0.459, 0.518, 0.574, 0.600, 0.621, 0.636, 0.648, 0.661, 0.681, 0.708, 0.746\}
T密度={0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746}
计算属性“密度”信息增益为0.262，对应划分点0.381。
属性“含糖率”，其候选划分点集合也包含16个候选值
T
含糖率
=
{
0.049
,
0.074
,
0.095
,
0.101
,
0.126
,
0.155
,
0.179
,
0.204
,
0.213
,
0.226
,
0.250
,
0.265
,
0.292
,
0.344
,
0.373
,
0.418
}
T_{含糖率}=\{0.049, 0.074, 0.095, 0.101 , 0.126, 0.155, 0.179, 0.204, 0.213, 0.226, 0.250, 0.265, 0.292, 0.344,0.373,0.418\}
T含糖率={0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418}
计算属性“含糖率”信息增益为0.349，对应划分点0.126。
计算其余各属性的信息增益，得
故选择信息增益率最大的属性“纹理”做根节点进行属性划分
最终生成决策树如下：
注：与离散属性不同的是，若当前结点划分属性为连续属性，该属性仍可作为其后代结点的划分属性。
4.4.2缺失值处理
不完整样本，即样本的某些属性值缺失
如何利用有缺失属性的训练样例进行学习？
问题：（1）如何在属性值缺失的情况下进行划分属性选择?
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
解决方案：
对问题（1），根据无缺失的样本子集来判断属性优劣
对问题（2），若样本x在划分属性a上取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为
w
x
w_x
wx。若样本x在划分属性a上取值未知，则将x同时划入所有子结点，且样本权值在与属性
a
v
a^v
av对应的子结点中调整为
r
v
~
⋅
w
x
\tilde{r_v}\cdot w_x
rv~⋅wx
C4.5利用上述方法作为缺失值处理的解决方案
4.5多变量决策树
把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。
决策树所形成的分类边界的特点：轴平行，即分类边界由若干个与坐标轴平行的分段组成。
如例，一决策树及其所对应的分类边界
可见，分类边界每一段都与坐标轴平行。每段划分都直接对应某个属性取值，故有较好的可解释性。
实际情况下，真实分类边界比较复杂，需使用很多段划分才能获得较好的近似，若能使用斜的划分边界，决策树模型将大为简化。
“多变量决策树”即为能实现这样“斜划分”甚至更复杂划分的决策树。在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试。即将非叶结点视作形如
∑
i
=
1
d
w
i
a
i
=
t
\sum_{i = 1}^{d}w_ia_i=t
∑i=1dwiai=t的线性分类器，其中
w
i
w_i
wi是属性
a
i
a_i
ai的权重，
w
i
w_i
wi和t可在该结点所含的样本集合属性集上学得。
如
