0%

决策树

Posted on Edited on In
Symbols count in article: 4.4k Reading time ≈ 15 mins.

构建决策树

决策树是一种常见的分类机器学习方法，顾名思义，决策树就是基于树形结构来进行决策，这恰是人类在面临决策问题时一种很自然的处理机制。

决策树例子

一棵判断西瓜是否是好瓜的决策树例子

在构建一棵决策树时，其决策的过程就是对某个属性的“测试”，每个测试的结果或是导出最终的分类结果，或是导出下一步的判定问题，每一次需要决策的样本是上次的决策结果之后划分出来的样本。

一般，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

构建一棵决策树的伪代码为：

输入：训练集$D={(xi, y_i)}{i=1}^{m}$

​ 属性集$A = {ai}{i=1}^{d}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void GenerateDTree(D, A) {
  	生成根结点 root;
	if (D中样本全属于同一类别C) {//当前结点包含的样本全属于同一类别，即yi都相同
 		将root标记为C类叶结点;
   		return;
  	}
	if (A == NULL || D中样本在属性A上取值相同) {//没有属性可以选择或者当前所有样本在剩下的属性上取值相同
    		将root标记为叶结点，其类别标记为D中样本最多的类;
    		return;
	}
  	从属性集A中选择最优划分属性a*;
  	for (对于属性a*每一个可能的属性取值v) {
      		为root生成一个分支；令D_v表示D中在属性a*上取值为v的样本子集;
        	if (D_v 为空集) {
           		将分支结点标记为叶结点，其类别标记为D中(注意是D)中样本最多的类;
           		return;
        	} else {
           		GenerateDTree(D_v, A - a*);
        	}
    	}
}

决策树生成的算法是一个递归算法，注意该递归算法的三个返回条件

疑问:
1、 如果在选择当前样本数量最多的类作为类别标记时，有多个样本数量最多的类别时怎么办？随便选一个？
2、for循环中，对于属性a*每一个可能的属性取值v，这里的可能取值是相对于最开始的数据集来说还是相对于当前结点中的数据集来说？因为当前结点中的数据集在属性a*上的取值可能比最开始的数据集要少一些

划分选择

在上面的生成决策树的伪代码中，我们要选择最优的划分属性，那么应该怎么选择最后的划分属性呢？一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。所以可以选择使得划分后结点纯度更高的属性作为划分属性，一般有以下几种度量某种属性这种能力的指标：信息增益、增益率、基尼指数。

信息增益

在查看定义信息增益之前，需要先查看信息熵的定义。信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合$D$中第$k$类样本所占的比例为$p_k \space (k = 1,2, \cdots, |Y|, |Y|表示当前样本中类别的总数)$，则信息熵的定义为：

$Ent(D)$越小，则数据集合$D$的纯度越高

有了信息熵的定义之后，再来看信息增益的定义。假设某个离散属性$a$有$V$个可能的取值${a_1, a_2, \cdots, a_V}$，若使用属性a来对样本集D来划分，则会产生$V$个分支结点。其中第$i$个分支结点包含了D中所有在属性$a$上取值为$a_i$的样本，记为$D_i$。这样可以计算出$D_i$的信息熵，在考虑在不同的分支结点包含的样本数不同，给分支结点赋予权重$|\frac{D_i}{D}|$，即样本数多的分支结点的影响越大。最后可以得到使用属性$a$对样本集D进行划分所获得的“信息增益”:

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提示”越大。若在一次划分中，有多个属性均取得了最大的信息增益，则任选其中之一作为划分属性。

增益率

信息增益准则的特点是对可取值数目较多的属性性有所偏好，例如某种属性有1000个取值，那么这个属性的信息增益率一般就会很大，但是选择这个属性作为划分属性后，每个划分出来的结点可能会因为已经没有多少剩余的样本而很快地被标记为叶结点。那么使用这个有1000个取值的属性划分得到的决策树泛化能力一般不会太好。而增益率则将每个属性的可能取值个数考虑了进去，其定义为：

$IV(a)$称为属性a的“固有值”，属性a的可能取值数目越多(即$V$越大)，则$IV(a)$的取值通常会越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，有些算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选择增益率最高的。

基尼指数

查看基尼指数的定义前，先看一下基尼值的定义。基尼值也是用来描述数据集D的纯度的指标。其具体定义为：

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

有了基尼值的定义，再来看属性a的基尼指数的定义：

我们在候选属性集合$A$中，选择那个使得划分后基尼指数最小(注意是最小，信息增益和增益率中是选最大的那个)的属性作为划分属性。

剪枝处理

剪枝处理是决策树学习算法处理过拟合的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会造成决策树分支过多，这时就可能因训练样本学习得“太好”了，以至于把训练集自身的一些特点也当做所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有预剪枝和后剪枝。

预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。那么如何判断泛化性能是否提升呢？可以使用验证集来判断，看剪枝后的决策树在验证集上的表现是否比未剪枝的决策树好。

预剪枝使得决策树的很多分支结点都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，这给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝则是先从训练集中生成一棵完整的决策树，然后自底向上地对每个非叶结点进行判断，若将该非叶结点对应的子树替换为叶结点能带来决策树泛化能力的提升(同样也可使用验证集来判定泛化性能是否提升)，则该非叶结点标记叶结点。

后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情况下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续值处理

在决策树中，对于某些取值为连续值的属性，不能直接根据连续属性的可取值来对结点进行划分，此时要将连续值转换为离散值，最简单的策略是采用二分法对连续属性进行处理。

给定样本集$D$和连续属性$a$，假设$a$在$D$上出现了n各不同的取值，将这些值从小到大进行排列，记为${a_1, a_2, \cdots, a_n}$。选定划分点$t$为某两个相邻取值的中点，则数据集可以被划分为两个子集。因此，对于n个不同

取值，共有$n-1$个候选划分点，这些划分点构成集合：

然后，可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集的划分。例如可用改造后的信息增益来判断划分点的优劣：

$Gain(D, a, t)$是样本集在连续属性$a$上基于划分点$t$二分后的信息增益。于是，我们就可选择使$G(D, a, t)$

最大化的划分点。

需要注意的是，与离散值属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。例如当前结点选择的划分属性为连续属性$a$，并且划分标准为$a \leq 0.5$和$a> 0.5$，则对于使用$a \leq 0.5$划分出来的结点，仍然可以使用属性a最后划分属性，这时可能选择划分标准为$a \leq 0.25$和$0.25 < a \leq 0.5$。

缺失值处理

现实任务中常会遇到不完整的样本，尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值，如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息的极大浪费。所以要想办法处理缺失值的情况。

如何在属性缺失的情况下进行划分属性选择

给定数据集$D$和属性$a$，令$\overline{D}$表示D中在属性a上没有缺失值的样本子集，显然我们可根据$\overline{D}$来判断属性a的优劣。假设属性a由$V$个可取值${a_1, a_2, \cdots, a_V}$，令$\overline{D_i}$表示$\overline{D}$中在属性a上取值为$a_i$的样本子集。$\overline{D_k}$表示$\overline{D}$中属于第$k$类$(k = {1, 2, \cdots, |Y|}, \space|Y|为\overline{D}中类别总数)$的样本子集。则有：

假定为$D$中的每个样本$x$赋予一个权值$w_x$，并定义：

直观上来看，对属性$a$，$\rho$表示无缺失值样本所占的比例，$\overline{pk}$表示无缺失值样本中第$k$类样本所占的比例，$\overline{r_i}$则表示无缺失值样本中在属性a上取值为$a_i$的样本占的比例。显然有：$\sum{k=1}^{|Y|} \overline{pk} = 1$，$\sum{i=1}^{V} \overline{r_i} = 1$。

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

同理也可得到增益率和基尼指数的推广。

给定划分属性，若样本在该属性上的值缺失，如果对样本进行划分

若确定了划分属性为$a$，若样本$x$在划分属性$a$上的取值未知，则将$x$同时划入所有子结点，且样本权值在与属性值$a_i$对应的子结点调整为$\overline{r_i} · w_x$。直观上来看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则$d$个属性描述的样本就对应了$d$维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点: 轴平行​，即它的分界边界由若干个和坐标轴平行的分段组成。

显然，分类边界与坐标轴平行时，这样的分类边界使得学习结果具有较好的可解释性。但在学习任务的真实边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，则决策树的模型将能得到很大的简化，多变量决策时就是能实现斜划分甚至更复杂划分的决策树。在此类决策树中，非叶结点不再仅对莫个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如$\sum_{i=1}^d w_i a_i = t$的线性分类器，其中$w_i$是属性$a_i$的权重。在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最有划分属性，而是试图建立一个合适的线性分类器。

其他

在决策时中，常使用信息增益、增益率、基尼指数作为划分属性选择的标准，除这些意外，人们还设计了许多其他的准则用于决策树划分选择。这些准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限。而使用剪枝的方法和程度对决策树泛化性能的影响相当显著，有实验研究表明，在数据带有噪声时通过剪枝甚至可将决策树的泛化性能提高25%。

有算法试图在决策树中的叶结点嵌入神经网络，例如感知机树在决策树的每个叶结点上训练一个感知机，有的直接在叶结点嵌入多层神经网络。

有一些决策树算法可进行增量学习，即在接收到新样本后对已学得的模型进行调整，而不完全重新学习。主要机制是通过调整分支路径上的划分次序来对树进行部分重构。增量学习可有效降低每次接受到新样本后的训练时间开销，但多步增量学习后的模型与基于全部数据训练而得的模型有较大差别。