Chap04 决策树

第四章 决策树(decision tree)

文章目录

第四章 决策树(decision tree)4.1 基本流程4.2 划分选择4.2.1 信息增益 4.2.2 增益率4.2.3 基尼系数 4.3 剪枝处理4.3.1 预剪枝4.3.2 后剪枝 4.4 连续与缺失值4.4.1 连续值处理4.4.2 缺失值处理 4.5 多变量决策树

4.1 基本流程

决策树(Decison Tree)是一种基于树结构决策的机器学习算法。

决策树采用分而治之(Divide and Conquer)策略，以一系列的子决策决定分类结果。

一般的，一颗决策树包含一个根结点、若干个子结点和若干个叶结点。根结点包含样本全集；子结点对应属性划分，包含划分样本；叶结点对应决策结果，包含决策样本。从根结点到每个叶结点的路径对应一个判定测试序列。

学习目的：决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树。 显然，决策树的生成是一个递归过程。其核心是最优划分属性的选择，在决策树基本算法中，有以下三种情形导致递归返回：

当前结点包含的样本全属于同一类别，无需划分。

所有样本在所有属性值相同，或属性集为空，无法划分，该结点类别设定为所含样本最多的类别。

当前结点包含的样本集合为空，不能划分。该节点类别设置为其父节点所含样本最多的类别。

4.2 划分选择

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高

4.2.1 信息增益

“信息熵”（information entropy）：度量样本集合纯度最常用的一种最常用的指标(可以狭隘的理解为一种混乱程度的度量) 假定当前样本集合$D$中第$k$类样本所占的比例$p_k(k=1,2,\dots ,\mid Y\mid )$ ​则D的信息熵定义为:

$$Ent(D)=-\sum _{k=1}^{\mid Y\mid }{p}_{k}lo{g}_2{p}_k$$

$Ent(D)$值越小，则$D$的纯度越高 计算信息熵约定：若$p=0$，则$plo{g}_{2}p=0p{\log }_{2}p=0$ $Ent(D)$最小值为$0$，最大值为$log2\mid \mathcal{Y}\mid$

假定离散属性$a$有$V$个可能取值 $\{a1,a2,\dots ,aV\}$ 若使用$a$来对样本集$D$划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\frac{D^v}{D}$，即样本数越多的分支结点的影响越大，于是可计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”(information gain): $$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D_v\mid }{\mid D\mid }Ent(D^v)$$

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的的“纯度提升”越大

因此，我们可以根据信息增益来选择结点，一般选择信息增益最大的属性作为划分结点，即： $$a\ast =argma{x}_{aϵA}Gain(D,a)$$

著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

4.2.2 增益率

实际上，由于信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。增益率定义为： $$Gai{n}_{ratio}(D,a)=\frac{Gain(D,a)}{IV(a)}$$ 其中： $$IV(a)=-\sum _{v=1}^V\frac{\mid Dv\mid }{\mid D\mid }lo{g}_2\frac{\mid Dv\mid }{\mid D\mid }$$ 称为属性a的“固有值”($intrinsicvalue$).

须注意的是，由于增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法采用先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的方法来选择最优划分属性

4.2.3 基尼系数

CART(Classification and Regression)决策树使用基尼指数(Gini Index)来选择划分属性

数据集D的纯度可用基尼值来度量： $$Gini(D)=\sum _{k=1}^{|\mathcal{Y}|}\sum _{k\prime ̸=k}{p}_k{p}_{k\prime }$$

直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小,则数据集$D$的纯度越高。

属性$a$的基尼指数定义为： $$Gin{i}_{index}(D,a)=\sum _{v=1}^V\frac{\mid Dv\mid }{\mid D\mid }Gini(D^v)$$ 于是，我们在划分属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即： $$a\ast =argmi{n}_{aϵA}Gini\_index(D,a)$$

信息熵代表了混乱程度。信息熵越小，信息增益越大，纯度越大 基尼值表示了类别不一致的概率，基尼值越小，纯度越大

4.3 剪枝处理

“剪枝”(Pruning)是决策树学习算法用于防止模型过拟合(Overfitting)的主要手段。

决策树剪枝的基本策略有"预剪枝"(prepruning)和"后剪枝"(post-pruning)。

4.3.1 预剪枝

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

仅有一层划分的决策树，称为“决策树桩(decision stump)”

预剪枝基于贪心本质，预划分当前结点，减少了决策树的分支

优点：

显著降低了过拟合的风险显著减少了决策树的训练时间开销和测试时间开销

缺点：

数据集可能存在当前划分验证集精度低，但后续划分显著提高的情形，无法得到最优决策树；给预剪枝决策树带来了欠拟合的风险；

4.3.2 后剪枝

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

优点：

保留了更多分支，泛化性能增强降低了欠拟合的风险

缺点：

先从训练集生成一颗完整的决策树，训练时间开销和测试时间开销大

4.4 连续与缺失值

4.4.1 连续值处理

到目前为止我们仅讨论了基于离散属性来生成决策树。但是在现实学习任务中常会遇到连续属性， 由于连续属性的可取数目不再有限，因此不能根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术派上用场。最简单的策略是采用二分法(bi-partition)对连续属性进行处理，这正是C4.5算法中采用的机制 。

给定样本集D和属性a,假定在D上出现了n个不同的取值，将这些值从小到大进行排序，记为 $\{a1,a2,\dots ,an\}$，基于划分点$t$可将$D$分为子集$D_t^{-}$和$D_t^{+}$,其中,$D_t^{-}$包含那些在属性$a$取值上不大于$t$的样本，而$D_t^{+}$则包含那些在属性a上大于t的样本。

显然，对相邻的属性取值$a^i$和$a^{i+1}$来说，$t$在区间$[ai,ai+1]$中取任意值所产生的划分结果相同。因此，对于连续属性$a$，我们可考察包含$n-1$个元素的候选划分点集合： $$Ta=\{\frac{a^i+a^{i+1}}{2}\mid 1\le i\le n-1\}$$

计算纯度的方式跟之前一致，但是将中位点值替换为划分属性值

4.4.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失

考虑利用有缺失属性值的不完整样本来进行学习，需解决以下两个问题：

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

问题一 对于训练集$D$和属性$a$,令$\tilde{D}$表示$D$中在属性$a$上没有缺失值的样本子集，使用$\tilde{D}$来进行划分属性选择，假定属性$a$有$V$个可取值$\{a^1,a^2,\cdots ,a^V\}$，则：

${\tilde{D}}^v$表示$\tilde{D}$在属性a上取值为a^{v}的样本子集(共有V个值)${\tilde{D}}^v$表示$\tilde{D}$中属于第$K$类的样本子集(共$\mathcal{Y}$类) 显然有 $$\tilde{D}\bigcup _{k=1}^{\mathcal{Y}}{\tilde{D}}_k=\bigcup _{k=1}^{\mathcal{V}}{\tilde{D}}^v$$ 假定我们为每个样本$x$赋予一个权重$w_x$ ,并定义： $$\rho =\frac{{\sum }_{xϵ\tilde{D}}{w}_x}{{\sum }_{xϵD}{w}_x}$$

$${\tilde{p}}_k=\frac{{\sum }_{xϵ{\tilde{D}}_k}{w}_x}{{\sum }_{xϵ\tilde{D}}{w}_x}(1\le k\le |\mathcal{Y}|)$$

$${\tilde{r}}_v=\frac{{\sum }_{xϵ{\tilde{D}}^v}{w}_x}{{\sum }_{xϵ\tilde{D}}{w}_x}(1\le v\le V)$$

直观的看， 对属性$a,\rho$表示无缺失值样本所占的比例； $\widetilde{p_k}$表示无缺失值样本中第k类所占的比例； $\widetilde{r_v}$表示无缺失值样本中在属性$a$上取值$a^v$的样本所占的比例； ​ 为权重值，默认为1，在属性缺失的样本会同时进入所有分支，并将权重调整为各分支占的比重。

基于上述定义，我们可将信息增益的计算式推广为：

$$Gain(D,a)=\rho \times Gain(\tilde{D},a)$$ 其中： $$Ent(\tilde{D})=-\sum _{k=1}^{\mid Y\mid }{\tilde{p}}_{k}lo{g}_2{\tilde{p}}_k$$ 问题二

若样本$x$xx在划分属性$a$上的取值已知，则将$x$划入与其取值对应的子结点，且样本权值在子结点中保持为$w_x$。若样本$x$在划分属性$a$上的取值未知，则将$x$同时划入所有结点，且样本权值在与属性值$a^v$ 对应的子结点中调整为${\tilde{r}}_v\cdot w_x$ ;直观的看，这是让同一个样本以不同的概率划入到不同的子结点中去。

4.5 多变量决策树

将样本集合对应多维空间，每个属性对应一个维度，分类就是在不同类空间寻找边界。单变量决策树的分类边界是由若干个与坐标轴平行的分段组成。

若能使用斜的划分边界，则决策树模型将大为简化， “多变量决策树“(multivariate decision tree)就是能实现这样的“斜划分”，甚至更复杂划分的决策树 在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。