机器学习决策树(2)

剪枝处理

剪枝是决策树学习算法对付过拟合的主要手段。剪枝的基本策略有预剪枝和后剪枝。

预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

如何判断泛化性能的提升？采用留出法，预留一部分数据作为验证集以进行性能评估。

对于上图训练集，采用信息增益准则来进行划分属性选择，会训练出下图所示决策树。

---

预剪枝

基于信息增益准则，我们会选取属性“脐部”对训练集进行划分，产生三个分支。预剪枝要对划分前后的泛化性能进行评估来决定是否进行这个划分。

划分之前，所有样例都在根节点，若不进行划分，将该节点标记为叶节点，其类别标记为训练样例数最多的类别（训练样例数最多不唯一可任选其中一类），假设标记为好瓜，用验证集进行评估，验证集精度为37×100%=42.9%$\frac{3}{7}\times 100\mathrm{\%}=42.9\mathrm{\%}$

划分之后，节点2包含样例{1，2，3，14}，标记为好瓜；节点3包含样例{6，7，15，17}，标记为好瓜；节点4包含{10，16}，标记为坏瓜。用验证集进行评估，验证集精度为57×100%=71.4%$\frac{5}{7}\times 100\mathrm{\%}=71.4\mathrm{\%}$ 。泛化性能得到提升，所以用“脐部”划分得以确定。

接着对节点2进行划分，基于信息增益准则挑选出“色泽”属性。如图所示，划分后泛化能力下降，所以禁止划分。

对节点3进行划分，基于信息增益准则挑选出“根蒂”属性。如图所示，划分后泛化能力没有提高，所以禁止划分。

对于节点4，其所包含的样例已经都属于一类，不再进行划分。

预剪枝不仅降低了过拟合的风险，还减少了决策树的训练时间开销和测试时间开销。但另一方面预剪枝基于“贪心”的本质可能带来欠拟合的风险。

---

后剪枝

后剪枝先从训练集生成一颗完整决策树，如图4.5所示，该决策树的验证精度是42.9%。

首先考虑节点6，将节点6替换为叶节点后，包含训练集样例{7，15}，标记为好瓜，此时决策树的验证集精度为57.1%，于是后剪枝策略决定剪枝。

考察节点5，将节点5替换为叶节点后，包含训练集样例{6，7，15}，标记为好瓜，此时决策树的验证集精度为仍57.1%，于是可以不剪枝。（这里也可以剪枝）

考虑节点2，将节点2替换为叶节点后，包含训练集样例{1，2，3，14}，标记为好瓜，此时决策树的验证集精度为71.4%，于是后剪枝策略决定剪枝。

考虑节点3和1，将节点替换为叶节点后，所得决策树的验证集精度分别为71.4%和42.9%，于是不剪枝。

过程如下图所示：

后剪枝决策树通常比预剪枝保留更多的分支，欠拟合风险很小，泛化能力往往优于预剪枝决策树，但是训练时间开销比未剪枝决策树和预剪枝决策树都要大。

---

连续值处理

现实任务中常会遇到连续属性，我们要将连续属性离散化，最简单策略是采用二分法对连续属性进行处理。

给定样本集D和连续属性a，将a在D上的值从小到大排序，记为a1,a2,…,an$a^1,a^2,\dots ,a^n$，基于划分点t可以将D分为子集D−t$D_t^{-}$和D+t$D_t^{+}$。显然，对相邻属性取值ai$a_i$和ai+1$a_{i+1}$来说，t在区间[ai,ai+1)$[a_i,a_{i+1})$中取任意值所产生的划分结果相同，所以对连续属性a，我们可考察包含n-1个元素的候选划分点集合（属性a有n个值）。

Ta={ai+ai+12|1≤i≤n−1}$$T_a=\{\frac{a_i+a_{i+1}}{2}|1\le i\le n-1\}$$

然后就可以像离散属性值一样考察这些划分点，选取最优划分点进行样本集合的划分。

离散值的属性a对样本集D进行划分获得的信息增益：

Gain(D,a)=Ent(D)−∑v=1V|Dv|DEnt(Dv)$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{D}Ent(D^v)$$

连续值的属性a对样本集D进行划分获得的信息增益：

Gain(D,a)=maxt∈TaGain(D,a,t)=maxt∈Ta{Ent(D)−∑λ∈{−,+}|Dv|DEnt(Dλt)}$$Gain(D,a)=\underset{t\in T_a}{max}Gain(D,a,t)=\underset{t\in T_a}{max}\{Ent(D)-\sum _{\lambda \in \{-,+\}}\frac{|D^v|}{D}Ent(D_t^{\lambda })\}$$

我们选择使Gain(D,a,t)最大化的划分点。

举个栗子：

对属性“密度”，该属性的候选划分点集合包含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\}$
由上式计算出信息增益为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\}$
由上式计算出信息增益为0.349，对应于划分点0.126。

于是各属性增益为：

Gain(D,色泽)=0.109；Gain(D,根蒂)=0.143；Gain(D,敲声)=0.141；$$Gain(D,色泽)=0.109；Gain(D,根蒂)=0.143；Gain(D,敲声)=0.141；$$

Gain(D,纹理)=0.381；Gain(D,脐部)=0.289；Gain(D,触感)=0.061；$$Gain(D,纹理)=0.381；Gain(D,脐部)=0.289；Gain(D,触感)=0.061；$$

Gain(D,密度)=0.262；Gain(D,含糖率)=0.349$$Gain(D,密度)=0.262；Gain(D,含糖率)=0.349$$

于是，纹理被选为根节点划分属性，此后节点划分过程递归进行，最终生成决策树如下。

若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性。例如在父节点上使用“密度≤0.381$\le 0.381$”,不会禁止在子节点上使用“密度≤0.294$\le 0.294$”

---

缺失值处理
我们需要解决两个问题，

1. 如何在属性值缺失情况下进行划分属性选择
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分。

---

对于问题1：我们仅根据D中在属性a上没有缺失的样本子集来判断a的优劣。

之前信息增益的计算式为：

Gain(D,a)=Ent(D)−∑v=1V|Dv|DEnt(Dv)$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{D}Ent(D^v)$$

推广后：

Gain(D,a)=ρ×Gain(D˜,a)=ρ×(Ent(D˜)−∑v=1Vr˜vEnt(D˜v))$$Gain(D,a)=\rho \times Gain(\tilde{D},a)=\rho \times (Ent(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v))$$

Ent(D˜)=−∑k=1|Y|p˜klog2p˜k$$Ent(\tilde{D})=-\sum _{k=1}^{|\mathcal{Y}|}{\tilde{p}}_{k}lo{g}_2{\tilde{p}}_k$$

其中，D˜$\tilde{D}$表示D中在属性a上没有缺失的样本子集。
假如为每个样本x赋予一个权重wx$w_x$
ρ=∑x∈D˜wx∑x∈Dwx$\rho =\frac{\sum _{x\in \tilde{D}}{w}_x}{\sum _{x\in D}{w}_x}$表示无缺失值样本所占的比例。
r˜v=∑x∈D˜vwx∑x∈D˜wx${\tilde{r}}_v=\frac{\sum _{x\in {\tilde{D}}_v}{w}_x}{\sum _{x\in \tilde{D}}{w}_x}$表示无缺失值样本中在属性a上取值为av$a^v$的样本所占比例。
p˜k=∑x∈D˜kwx∑x∈D˜wx${\tilde{p}}_k=\frac{\sum _{x\in {\tilde{D}}_k}{w}_x}{\sum _{x\in \tilde{D}}{w}_x}$表示无缺失值样本中第k类所占的比例。

---

对于问题2：

若样本x在划分属性a上取值已知，则将x划入与其对应的子节点，且样本权重保持为wx$w_x$
若样本x在划分属性a上取值未知，将x同时划入所有的子节点，且样本权值在属性值av$a^v$对应的子节点中调节为r˜vwx${\tilde{r}}_v{w}_x$（就是让同一样本以不同的概率划入到不同的子节点去）。

举个栗子，

开始时，根节点包含样本集D中全部17个样例，各样例权值都为1。

以属性色泽为例，D˜$\tilde{D}$ 为{2，3，4，6，7，8，9，10，11，12，14，15，16，17}

Ent(D˜)=−∑k=12p˜klog2p˜k=−(614log2614+814log2814)=0.985$$Ent(\tilde{D})=-\sum _{k=1}^2{\tilde{p}}_{k}lo{g}_2{\tilde{p}}_k=-(\frac{6}{14}lo{g}_2\frac{6}{14}+\frac{8}{14}lo{g}_2\frac{8}{14})=0.985$$

令D˜1,D˜2,D˜3${\tilde{D}}^1,{\tilde{D}}^2,{\tilde{D}}^3$分别表示属性色泽上取值为青绿、乌黑、浅白的样本子集，有：

Ent(D˜1)=−(24log224+24log224)=1.000$$Ent({\tilde{D}}^1)=-(\frac{2}{4}lo{g}_2\frac{2}{4}+\frac{2}{4}lo{g}_2\frac{2}{4})=1.000$$

Ent(D˜2)=−(46log246+26log226)=0.918$$Ent({\tilde{D}}^2)=-(\frac{4}{6}lo{g}_2\frac{4}{6}+\frac{2}{6}lo{g}_2\frac{2}{6})=0.918$$

Ent(D˜1)=−(04log204+44log244)=0.000$$Ent({\tilde{D}}^1)=-(\frac{0}{4}lo{g}_2\frac{0}{4}+\frac{4}{4}lo{g}_2\frac{4}{4})=0.000$$

Gain(D,色泽)=ρ×Gain(D˜,a)=ρ×(Ent(D˜)−∑v=1Vr˜vEnt(D˜v))=1417×0.306=0.252$$Gain(D,色泽)=\rho \times Gain(\tilde{D},a)=\rho \times (Ent(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v))=\frac{14}{17}\times 0.306=0.252$$

于是各属性增益为：

Gain(D,色泽)=0.252；Gain(D,根蒂)=0.171；Gain(D,敲声)=0.145；$$Gain(D,色泽)=0.252；Gain(D,根蒂)=0.171；Gain(D,敲声)=0.145；$$

Gain(D,纹理)=0.424；Gain(D,脐部)=0.289；Gain(D,触感)=0.006；$$Gain(D,纹理)=0.424；Gain(D,脐部)=0.289；Gain(D,触感)=0.006；$$

选择纹理对根节点进行划分。编号8和10的样本在纹理上缺失值，因此它同时进入三个分支，但权重在三个分支清晰、稍糊、模糊中分别调整为715,515,315$\frac{7}{15},\frac{5}{15},\frac{3}{15}$

最终生成的决策树如下图: