西瓜书+南瓜书第四章决策树

4.1什么是决策树

决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值。

4.2划分选择

4.2.1 划分的思路

我们需要选择一个最优的划分属性，一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即节点的纯度越来越高。
那我们就需要一种衡量样本集合纯度的一种指标，我们这里选择的是一种常用于度量样本集合纯度的一种指标，即“信息熵”，假定当前样本集合中第$k$类样本所占的比例为$p_k(k=1,2,\cdots ,|\gamma |)$,则$D$的信息熵定义为
$$Ent(D)=-\sum _{k=1}^{|\gamma |}{p}_k{\log }_2{p}_k$$

4.2.2 ID3决策树

ID3决策数以信息增益为准则划分属性.
假定离散属性$a$有$v$个可能的取值{
$a^1,a^2,\cdots ,a^V$}，若使用$a$来对样本集合$D$进行划分，则会产生$v$个分支节点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$ 的样本，记为$D^v$,我们先算出$D^v$的信息熵，再考虑不同分支结点所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点的影响越大，于是可计算出属性$a$对样本集$D$进行划分所获得的“信息增益”
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
信息增益越大，则这次划分对纯度提升越高，故我们选择属性
$$a_{\ast }=\underset{a\in A}{\mathrm{argmax}}Gain(D,a)$$
作为划分属性.

4.2.3 C4.5决策树

ID3决策树有个缺点,信息增益准则对可取数目较多的属性有所偏好，为了减少这种影响，C4.5决策树算法选择用“增益率”来选择最优划分属性，增益率定义为
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},$$
其中$$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$
称为属性$a$的固有值，属性a的可能取值越多，$IV(a)$通常越大。
需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5决策树并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式:先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.2.4 CART决策树

CART决策树使用基尼系数来选择划分属性，数据集$D$的纯度可以用基尼值来度量:
$$\begin{gathered} Gini(D)=\sum _{k=1}^{|\gamma |}\sum _{k^{{}^{\prime }}\ne k}{p}_k{p}_{k^{{}^{\prime }}} \\ =1-\sum _{k-1}^{|\gamma |}{p}_k^2 \end{gathered}$$
直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率，因此$Gini(D)$越小，则数据集$D$的纯度越高.
属性a的基尼指数定义为·
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$
则
$$a_{\ast }=\mathrm{argmin}Gini\_index(D,a).$$

4.3 剪枝处理

4.3.1 基本问题

为什么要剪枝？
剪枝是决策树学习算法对付“过拟合”的主要手段。
那么过拟合是怎么出现的呢?
在决策树学习中，为了尽可以正确分类样本，结点划分将不断重复，有时会造成决策树分支过多，以致把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合，因此，可通过主动去掉一些分支来降低过拟合的风险。
处理方式?
通过剪枝，提高泛化性能。

4.3.2 预剪枝

在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分，并将当前结点标记为叶结点。
优点:使得很多分支没有展开，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
缺点:有些分支的当前划分虽然不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

4.3.3 后剪枝

先从训练集生成一棵完整的决策树，然后自下而上地对非叶结点进行考察，若将该点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
优点: 欠拟合风险小
缺点: 训练时间开销大

4.4 连续与缺失值

4.4.1 连续值处理

到目前为止我们仅讨论了基于离散属性来生成决策树，现实学习任务中常常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。
给定样本集合$D$和连续属性$a$，假定a在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序，记为 { a 1 , a 2 , … , a n } . \{a^1,a^2,\dots,a^n\}. {
a1,a2,…,an}.基于划分点$t$可将$D$分为子集$D_t^{-}$和$D_t^{+}$，其中$D_t^{-}$包含那些属性a上取值不大于$t$的样本，而$D_t^{+}$则包含那些在属性$a$上取值大于$t$的样本。显然，对相邻的属性取值$a^i$和$a^{i+1}$来说，$t$在区间$[a^i,a^{i+1})$中取任意值的划分结果相同，所以我们不妨选可能的$n-1$的划分点t的集合为
T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } T_a=\{\frac{a^i+a^{i+1}}{2}|1\le i\le n-1\} Ta​={
2ai+ai+1​∣1≤i≤n−1}
即把$a^i$和$a^{i+1}$的中位点作为候选划分点，然后我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本的划分。

G a i n ( D , a ) = max ⁡ t ∈ T a G a i n ( D , a , t ) = max ⁡ t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) Gain(D,a)=\max_{t\in T_a}Gain(D,a,t)\\ =\max_{t\in T_a}Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D_{t}^{\lambda}|}{|D|}Ent(D_{t}^{\lambda}) Gain(D,a)=t∈Ta​max​Gain(D,a,t)=t∈Ta​max​Ent(D)−λ∈{
−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)
其中$Gain(D,a,t)$是样本集基于划分点$t$二分后的信息增益，于是我们就可选择使$Gain(D,a,t)$最大化的划分点。
需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性。(例如在父节点上使用了“密度$\le$ 0.381”,不会禁止在子节点上使用“密度” $\le$ 0.294)

4.4.2缺失值处理

现实任务中常会遇到不完整的样本，即样本的某些属性值缺失；尤其是在属性数目较多的情况下，往往有大量样本出现缺失值。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。
那么我们需要解决两个问题
1,如何在属性值缺失的情况下进行划分属性的选择?
2,给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?
给定训练集$D$和属性$a$,令$\tilde{D}$表示$D$中属性在$a$上没有缺失值的样本子集。
对于问题1，显然我们仅可以根据$\tilde{D}$来判断属性$a$的优劣，假定属性$a$可取值{
$a^1,a^2,\cdots ,a^V$}，令$\widetilde{D^v}$表示$\tilde{D}$中在属性$a$上取值为$a^v$的样本子集，$\widetilde{D_k}$表示$\tilde{D}$中属于第$k$类($k=1,2,\dots ,|\gamma |$)样本子集，则显然有$\tilde{D}={\cup }_{k=1}^{|\gamma |}\widetilde{D_k}$，$\tilde{D}={\cup }_{v=1}^{|V|}\widetilde{D^v}$。假定我们为每个样本$\mathbf{x}$赋予一个权重$w_{\mathbf{x}}$并定义

• 这里的$w_x$是什么呢？
• 答: 初始化为1，会随着学习而调整

$$\rho =\frac{{\sum }_{x\in \tilde{D}}{w}_{\mathbf{x}}}{{\sum }_{x\in D}{w}_{\mathbf{x}}},$$
$$\widetilde{p_k}=\frac{{\sum }_{x\in \widetilde{D_k}}{w}_{\mathbf{x}}}{{\sum }_{x\in D}{w}_{\mathbf{x}}},$$
$$\widetilde{r_v}=\frac{{\sum }_{x\in \widetilde{D^v}}{w}_{\mathbf{x}}}{{\sum }_{x\in D}{w}_{\mathbf{x}}},$$
直观来看，对属性$a$,$\rho$表示无缺失值样本所占的比例，$\widetilde{p_k}$表示无缺失值样本中第$k$类所占的比例，$\widetilde{r_v}$表示无缺失值样本中在属性$a$上取值$a^v$的样本所占的比例。显然，${\sum }_{k=1}^{|\gamma |}\widetilde{p_k}=1$,${\sum }_{v=1}^{|V|}\widetilde{r_v}=1$.
基于以上定义我们可以将信息增益的计算式推广为
$$\begin{gathered} Gain(D,a)=\rho \times Gain(\tilde{D},a) \\ =\rho \times (Ent(\tilde{D})-\sum _{v=1}^V\widetilde{r_v}Ent(\widetilde{D^v})) \end{gathered}$$
其中
$$Ent(\tilde{D})=-\sum _{k=1}^{|\gamma |}\widetilde{p_k}{\log }_2\widetilde{p_k}$$
对问题2，若样本$\mathbf{x}$在划分属性$a$上的取值未知，则将$\mathbf{x}$同时划入所有子结点，且将样本权值在与属性值$a$对应的子结点中调整为$\widetilde{r_v}\cdot w_{\mathbf{x}}$；直观来看，就是让同一个样本以不同的概率划入不同的子结点中去。

4.5 多变量决策树

若把每个属性对应一条坐标轴，上述的单变量决策树，划分的边界是和该坐标轴垂直的，是“直”的，这样的划分可能需要很多次才能得到较好的近似，而多变量决策树可以直接生成“斜”的边界，决策判断条件变得多维，如下图。

• 如何实现呢？

以上内容源于周志华《机器学习》（西瓜书），笔者以自己的理解写了这篇笔记，如有错误欢迎指正