机器学习（第四章）4.决策树
1基本流程
决策树(decision tree) 是一类常见的机器学习方法.
以二分类任务为例，希望从给定训练数据集中学得一个模型用以对新示例进行分类，将样本分类的任务，可以看作是对于“当前样本是否为正类”这个问题的“决策”或“判定”过程。此决策过程如下图所示：
- 决策过程的最终结论对应了我们所希望的判定结果，例如"是"或"不是"好瓜;
- 决策过程中提出的每个判定问题都是对某个属性的"测试"，例如"色泽=?" "根蒂=?“
- 每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内，
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;
-
叶结点对应于决策结果，其他每个结点则对应于一个属性测试;
-
每个结点包含的样本集合根据属性测试的结果被划分到子结点中;
-
根结点包含样本全集
决策树的基本流程如下图所示
三种情形会导致递归返回:
(1) 当前结点包含的样本全属于同一类别，无需划分;
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
(3) 当前结点包含的样本集合为空，不能划分.
在第(2) 种情形下，我们把当前结点标记为叶结点，井将其类别设定为该结点所含样本最多的类别;
在第 (3) 种情形下，同样把当前结点标记为叶结点，将其类别设定为其父结点所含样本最多的类别.
注意这两种情形的处理实质不同:情形(2) 是在利用当前结点的后验分布，而情形(3) 则是把父结点的样本分布作为当前结点的先验分布.
2划分选择
? 由算法可看出决策树学习的关键是第8行，即如何选择最优划分属性一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的"纯度" (purity) 越来越高.
2.1 ID3决策树
2.1.1自信息
2.1.2信息熵
“信息熵” (information entropy) 是度量样本集合纯度最常用的一种指标.
假定当前样本集合D中第k类样本所占的比例为 Pk (k = 1, 2,. . . , IYI) ，则的信息熵定义为
Ent
?
(
D
)
=
?
∑
k
=
1
∣
Y
∣
p
k
log
?
2
p
k
\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k}
Ent(D)=?k=1∑∣Y∣?pk?log2?pk?
**Ent(D)**的值越小，D的纯度越高
2.1.3条件熵
2.1.4 ID3决策树
2.2 C4.5决策树
由于ID3决策树对可能取值较多的属性有所偏好，对分类中每一个分类样本中只有一个示例并不适用，例如编号，所以有了C4.5决策树
但是C4.5决策树并未完全使用“增益率”代替“信息增益”，而是采用一种启发式的方法：先选出信息增益高于平均水平的属性，然后再从中选择增益率最高的。
2.3CART决策树
**基尼值（针对样本总体属性）：**从样本集合D中随机抽取两个样本，其类别标记为不一致的概率。因此，基尼值越小，碰到异类的概率就越小，纯度对应就越高。
Gini
?
(
D
)
=
∑
k
=
1
∣
Y
∣
∑
k
′
≠
k
p
k
p
k
′
=
∑
k
=
1
∣
Y
∣
p
k
(
1
?
p
k
)
=
1
?
∑
k
=
1
∣
Y
∣
p
k
2
\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=\sum_{k=1}^{|\mathcal{Y}|} p_{k}\left(1-p_{k}\right) \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}
Gini(D)?=k=1∑∣Y∣?k′?=k∑?pk?pk′?=k=1∑∣Y∣?pk?(1?pk?)=1?k=1∑∣Y∣?pk2??
**属性a的基尼指数（针对某个属性）：**类比信息熵和条件熵。
Gini
?
?
index
?
(
D
,
a
)
=
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
Gini
?
(
D
v
)
\operatorname{Gini}_{-} \operatorname{index}(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)
Gini??index(D,a)=v=1∑V?∣D∣∣Dv∣?Gini(Dv)
CART决策树：选择基尼指数最小的属性作为最划化分属性
CART决策树的实际构造算法：
3.剪枝处理
剪枝(pruning) ：是决策树学习算法对付"过拟合"的主要手段.在决策树学习中把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合.因此，可通过主动去掉一些分支来降低过拟合的风险.
决策树剪枝的基本策略有：
预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将当前结点标记为叶结点；
后剪枝：先从训练集生成一颗完整的决策树，然后再自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。
是否剪枝的评判标准：剪枝前后的决策树泛化性能
方法：本节使用留出法，即预留一部分数据用于“验证集”以进行性能评估。
划分准则：信息增益准则来进行划分属性选择。
如表4.2 所示，编号为 {1 ,10 ,14,15 ,16, 17} 的样例组成训练集，编号为{4, 11, 12 ,13} 的样例组成验证集.
3.1预剪枝示意
基于表4.2生成的未剪枝决策树
基于表4.2 生成的预剪枝决策树
这是一棵仅有一层划分的决策树，亦称**“决策树桩” (decision stump)**
由上面两图对比可知，
特点：
1.预剪枝使得决策树的很多分支都没有"展开“，这不仅降低了过拟合的风险，还显著减少了训练时间开销和测试时间开销。
2.但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降?但在其基础上进行的后续划分却有可能导致性能显著提高;预剪枝基于"贪心"本质禁止这些分支展开给预剪枝决策树带来了欠拟含的风险
3.2后剪枝示意
特点：
1.后剪枝决策树通常比预剪枝决策树保留了更多的分支 ，一般情形下，后剪枝决策树的欠拟合风险很小，泛化能力往往优于预剪枝决策树.
2.但后剪枝过程是在生成完全决策树之后进行的 ，并且要自底向上，对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.
4.连续与缺失值
4.1连续值处理
? 目前学习了基于离散属性来生成决策树，现实学习任务中常遇到连续属性，由于连续属性的可取值数目不再有限， 因此，不能直接根据连续属性的取值来对结点进行划分.
? 常用的是采用 二分法(bi partition) 对连续属性进行处理。
方法：给定样本集D 和连续属性 a，假定a 上出现 n个不同的取值，将这些值从小到大进行排序，取两个相邻值的中位点作为候选划分点，可以得到n-1个候选划分点，就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分
Gain
?
(
D
,
a
)
=
max
?
t
∈
T
a
Gain
?
(
D
,
a
,
t
)
=
max
?
t
∈
T
a
Ent
?
(
D
)
?
∑
λ
∈
{
?
,
+
}
∣
D
t
λ
∣
∣
D
∣
Ent
?
(
D
t
λ
)
\begin{aligned} \operatorname{Gain}(D, a) &=\max _{t \in T_{a}} \operatorname{Gain}(D, a, t) \\ &=\max _{t \in T_{a}} \operatorname{Ent}(D)-\sum_{\lambda \in\{-,+\}} \frac{\left|D_{t}^{\lambda}\right|}{|D|} \operatorname{Ent}\left(D_{t}^{\lambda}\right) \end{aligned}
Gain(D,a)?=t∈Ta?max?Gain(D,a,t)=t∈Ta?max?Ent(D)?λ∈{?,+}∑?∣D∣∣∣?Dtλ?∣∣??Ent(Dtλ?)?
其中 Gain(D ,a, t) 是样本集D 基于划分点t二分后的信息增益.于是，可选择使 Gain(D,a, t) 最大化的划分点.
4.2缺失值处理
我们需解决两个问题:
(1) 如何在属性值缺失的情况下进行划分属性选择?
(2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?
问题(1)可以由上式回答
概率根据其划分的类别中样本所占的权重决定。
5.多变量决策树
决策树所形成的分类边界有一个明显的特点:轴平行(axis- parallel) ，即它的分类边界由若干个与坐标轴平行的分段组成.
但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时是对属性的线性组合进行测试;与传统的"单变量决策树" (univariate decision tree) 不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。
