00-决策树算法

2023-06-15

一、基本流程#

【定义】基于树状结构进行判定的决策流程。决策过程的最终结论对应了我们所希望的判定结果。每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内。

【目标】决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”策略。

【过程】决策树的生成是一个递归过程。当符合条件以下之一时，递归返回：（1）当前结点包含的样本全属于同一类别；（2）当前属性集未空，或所有样本在所有属性上取值相同；（3）当前结点包含的样本集合为空。(2)为后验，（3）为先验。

二、划分选择#

【目标】希望决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。一般三种方法：信息增益、增益率、基尼指数。

2.1 信息增益#

如果我们把抛出一枚硬币产生两种等概率的情况的不确定性，定义为1bit，那么对于一种面临n个相等可能情况的事件，就相当于抛了 $log_2n$ 次硬币，不确定性就是 $log_2n$ bit.反过来，如果告知了发生某件事的概率为p，那么它就有可能产生1/p的相等可能结果，就相当于抛了 $log_2\frac{1}{p}$ 次硬币。对于某一个事件，其有n种可能的结果，每种可能的结果发生的概率记为pi。通过上述的分析，我们不难想到，只要对每种可能的结果分别求出其不确定性，再乘以其发生的概率，我们就可以得到整个事件“不确定性”的期望值。这个值就是信息熵。

假设集合D中，第i类样本的所占比例为pi(i=1,2,…,|y|)，那么D的信息熵可以用公式可以表示为：

Ent(D)=-\sum_{i=1}^{|y|}p_ilog_2p_i

信息熵表示的是事件“不确定性”的期望值。而在决策树中，如果一个分类使得每个类别中的“纯度”提高了，那么信息熵的“不确定性”自然就降低了。

根据这一点，我们可以设计这样的流程：

确定待分类的样本集合D和离散属性集合X；
对于离散属性集合X中的每一个元素a，假设其有v个可能的取值（a1,a2,…,av)；
计算初始分类情况下，D的信息熵；
使用a对D进行划分，假设第i个节点ai划出了Di个元素组为一类；
我们对新划分的结果再次计算信息熵；
c减去e。对所有的ai都进行此操作，并从结果中选取使得差值最大的a*，以a*为标准进行划分；
不断重复以上步骤，直到无法划分为止。

步骤f处的公式便可以写为：

Gain(D,a)=Ent(D)-\sum_{i=1}^{|v|}\frac{|Di|}{|D|}Ent(Di)

这个差值我们就称之为“信息增益”，即信息不确定性减少了多少。

2.2 增益率#

信息增益的概念是很直接的，但是，“信息纯度”的增加，并不一定能够带来我们想要的学习模型。

例如，如果我们直接以“编号”或者“ID”来划分，那么一开始就可以直接划分出样例数量的分支，纯度最高。但这样的模型显然无法满足我们的需求，根本提供不了任何信息。

信息增益表示了经过a*属性的分类后，整体信息不确定性减少了多少。但在这个过程中，信息不确定的减少，不一定来自“把相同类别的信息整合到一起”，还有可能来自“把信息拆散开来的程度”。即，我们想要的是纯度高而且每个类别里面样例数量也尽可能多的分类结果，并非只是每个类别的纯度都尽可能高的结果。

基于这点，C4.5决策树算法提供了一种新的思路：使用增益率来表示，其公式如下所示：

\begin{aligned}{}Gain\_ratio(D,a)&=\frac{Gain(D,a)}{IV(a)}\\and\quad IV(a)&=-\sum_{i=1}^{|v|}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}\end{aligned}

这个方法实质上做了一个这样的假设：用信息增益除以分类方式带来的固有增益，得到增益率。而增益率可以表示真实的“纯度高而且每个类别里面样例数量也尽可能多”的情况。

实际操作时，会先从候选划分中选出信息增益超过平均值的属性，再从中选出增益率最高的那一个来。

2.3 基尼指数#

CART决策树另辟蹊径，它首先定义了一个“基尼值”：从数据集D中随机抽取两个样本，其类别标记不一致的概率：

Gini(D)=1-\sum_{i=1}^{|y|}p_i^2

Gini值越小，数据集D的纯度越高。

然后再对根据属性a*进行的划分，取期望值，便可以得到基尼指数：

Gini\_index(D,a)=\sum_{i=1}^{|v|}\frac{|D_i|}{|D|}Gini(D_i)

在候选集合A中，选择使得划分后基尼指数最小的属性作为最优划分，这样就可以得到一组划分序列了。

当然，基尼指数只考虑了“纯度”，仍然具备和“信息增益”一样的问题：如果按照编号来划分，那么每个类别里的Gini值都是0，所得到的基尼系数自然是最小的。

对于这个问题，采用基尼指数来划分决策树时，应该提前对候选属性进行适当的筛选，或者如同“增益率”一样，对结果进行适当修正。

三、剪枝处理#

【目标】处理“过拟合”问题。当分支过多时，学习算法很有可能会把训练集自身的特点当作所有数据都具有的一般性质而进行过拟合。因此，需要主动剪去一些分支来降低过拟合的风险。

个人理解，像2.2中提到的“信息增益”和“基尼指数”就包含了类似过拟合的问题，可以通过剪枝来处理相关的问题。

3.1 预剪枝#

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

这里的关键在于判断“决策树泛化性能是否提升”。这里可以采用第二章的“留出法”，预留一部分数据用作“验证集”。

预剪枝的整体流程为：

首先基于信息增益原则，选取某个属性X对训练集进行划分，产生k个分支
讨论是否要进行这样划分。考虑不进行划分，那么该结点标记为叶结点，根据训练样例数最多的类别将该结点标记（例如正例大于反例，那么算法就默认给所有样例判正）。用验证集对这个单结点决策树进行评估，计算出验证集精度P1。
考虑进行划分，属性X具备V个值，对每个值划分出一个类别，然后每个类别都根据训练样例数最多的进行标记。用验证集对目前的结果进行判别，计算出验证集精度P2。
比较P1和P2，如果P1大于P2，那么不进行划分。如果P2大于P1，那么就采用这种划分方式。
不断迭代循环步骤1-4，直到产出的结点无法继续划分为止。

不难发现，“预剪枝”采用的是 “贪心法”，每次都先选取使得验证集精确度最高的那种方式，将有可能导致验证集精度下降的划分都剪去。

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

但是，决策树中往往会存在这样一种情况：先前的划分会导致验证集的精确度下降，但是这种划分带来的后续流程又会把验证集精确度提高。

因此，“预剪枝”会给决策树带来 “欠拟合” 的风险。

3.2 后剪枝#

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

其过程如下所示：

首先基于某种原则（信息增益、增益率、基尼指数）从训练集中生成一棵完整的决策树。基于这棵决策树，计算出训练集的精度为P1。
考察最底层的任一分支结点。将该结点替换为叶结点，然后根据训练样例最多的结果标记该结点。此时，基于替换后的决策树，计算出训练集的精度为P2。
如果P1>P2，那么这个叶结点将保留。反之，如果P2>P1，那么进行剪枝，得到剪枝后的决策树。
重复流程1-3，直到所有分支结点都考虑到了。

可以发现，“后剪枝”是在决策树生成之后再进行剪枝的，而且要自底向上对所有非叶结点逐一考察，因此时间开销会比较大。但后剪枝决策树避免了预剪枝的问题，欠拟合风险小，泛化性能会更高。

四、连续与缺失值#

4.1 连续值处理#

如果对于某个样例的某种属性，其值为连续值的话，应该如何对结点进行划分呢？

一种可行的方式是，采用二分法，将连续属性“离散化”。

在给定的样本集合D中，假设连续属性a出现了n个不同的取值。我们将这些值从小到大进行排序，得到一个集合 $\{a^1,a^2,...,a^n\}$ 。

又有，基于一个划分点t，我们可以把D分为子集Dt-和Dt+，前者表示在属性a上取值不大于t的样本，后者表示在属性a上取值小于t的样本。

我们依次从ai和ai+1中，选取中位点 $T_i=\frac{a^i+a^{i+1}}{2}$ ，把中位点作为候选的划分点，这样我们就得到了一个候选划分点集合：

T_a=\{\frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1\}

我们得到了n-1种划分方式，而我们要选取的是“信息增益”最大的那种划分方式。改写信息增益公式如下：

\begin{aligned}Gain(D,a)&=\underset{t\in T_a}{max}\quad Gain(D,a,t)\\&=\underset{t\in T_a}{max}\quad Ent(D)-\sum_{\lambda \in \{+,-\}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda)\end{aligned}

我们选择使得信息增益值最大的划分点，作为该属性的划分点。

4.2 缺失值处理#

由于隐私保护、检测成本……现实情况下，在属性数目较多的情况下，往往会有大量样本出现缺失值。为此，我们需要解决两个问题：

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

问题a表示：“在样本的属性值缺失的情况下，如何计算信息熵和信息增益？”

问题b表示：“根据信息增益确定划分属性后，如何将属性值缺失的样本划分到分类中？”

给定训练集D和属性a，令D~表示D在属性a上没有缺失值的样本子集。我们分别针对问题a和问题b进行考虑：

【问题a】显然，我们只能根据D~~来判断属性a的优劣。假定属性a有V个可取值 $\{a^1,a^2,...,a^V\}$ ，令 $\widetilde{D^v}$ 表示D~~在属性a上取值为a^{v}的样本子集， $\widetilde{D_k}$ 表示D~中属于第k类（k=1,2,…,|y|）的样本子集。假定我们为每个样本x赋予一个权重wx，并做如下定义：

\begin{aligned}\rho =\frac{\sum_{x\in \widetilde{D}}w_x}{\sum_{x\in D}w_x},\quad\widetilde{p_k}=\frac{\sum_{x\in \widetilde{D_k}}w_x}{\sum_{x\in \widetilde{D}}w_x},\quad\widetilde{r_v}=\frac{\sum_{x\in \widetilde{D^v}}w_x}{\sum_{x\in \widetilde{D}}w_x}\end{aligned}

这里面，ρ代表了无缺失值样本所占总样本的比例，p_k表示无缺失值样本中第k类所占的比例，r_v表示无缺失值样本在属性a上取值为a^v的样本所占的比例。

这样我们就可以把信息增益公式改写为：

\begin{aligned}Gain(D,a)&=\rho×Gain(\widetilde{D},a)\\&=\rho×(Ent(\widetilde{D})-\sum_{v=1}^{|V|}\widetilde{r_v}Ent(\widetilde{D^v}))\\Ent(\widetilde{D})&=-\sum_{k=1}^{|y|}\widetilde{p_k}log_2\widetilde{p_k})\end{aligned}

【问题b】若样本在划分属性a上的取值已知，则将x划入与取值对应的子节点，且样本权值在子节点中保持为w_x 。若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，且样本权值在与属性值a^v对应的子结点中调整为r_v*wx。

【总结】对于缺失值的处理，整个过程如下所示：

假设样本集D含有n0个样例，各个样例的权值均为1。
对于属性a，无缺失的样例子集D~~里包含了t1个正例，|D~~|-t1个反例。计算得到D~的信息熵：

\begin{aligned}     Ent(\widetilde{D})&=-\sum_{k=1}^{|2|}\widetilde{p_k}log_2\widetilde{p_k}\\     &=-(\frac{t1}{|\widetilde{D}|}log_2\frac{t1}{|\widetilde{D}|}+\frac{|\widetilde{D}|-t1}{|\widetilde{D}|}log_2\frac{|\widetilde{D}|-t1}{|\widetilde{D}|})     \end{aligned}

D~使用属性a进行划分，可以划分出m个类别。对于每个类别 $\widetilde{D^i}$ ，假设有正例ti个，反例个，计算其信息熵：

for \quad i\in\{1,2,...,m\},\\Ent(\widetilde{D^i})=-(\frac{ti}{|\widetilde{D^i}|}log_2\frac{ti}{|\widetilde{D^i}|}+\frac{|\widetilde{D^i}|-ti}{|\widetilde{D^i}|}log_2\frac{|\widetilde{D^i}|-ti}{|\widetilde{D^i}|})

计算样本子集D~在属性a上的信息增益：

Gain(\widetilde{D},a)=Ent(\widetilde{D})-\sum_{v=1}^{m}\frac{|\widetilde{D^v}|}{|\widetilde{D}|}Ent(\widetilde{D^v})

计算样本子集D在属性a上的信息增益：

Gain(D,a)=\frac{|\widetilde{D}|}{|D|}×Gain(\widetilde{D},a)

以此类推，计算出所有属性在D上的信息增益，选取使得信息增益呈现最大值的属性值ai，根据其属性对结点进行划分。
对于属性ai缺失的样例，将其同时分入ai的所有划分类中，并且权重分别调整为：当前分类内无缺失属性样本的个数/分类前无缺失属性样本的个数。
流程1-7递归执行。

五、多变量决策树#

一句话总结：多变量决策树试图建立一个合适的线性分类器，该分类器中，非叶结点不再是仅针对某个属性，而是属性的线性组合。