决策树及其应用场景

决策树（DT，decision tree）被广泛应用于数据挖掘尤其是机器学习等领域，是一种简洁并且实用的监督学习算法。它的目的是通过对输入数据的学习建立一棵树结构的模型，对目标变量进行预测。由于模型建立以后进行预测的过程和人类进行决策的过程很相似，因而称为决策树。

比如，有人要给你推荐工作，如果你用如图4.2所示的图告诉他你的要求，那么他就会很容易提前帮你筛选出你会去参加面试的公司了。

图4.2　决策树

你不告诉他你的要求，只是他每次给你推荐工作的时候，告诉你工作内容、工资是否超过5000元和工作地点是否在武汉等信息，你告诉他你去还是不去参加面试。等他多推荐几次后，如果他自己能总结出你的工作要求，比如再遇到不是IT行业的工作，他就知道不用给你推荐了，他能够预测出来你应该是不会去的，就说明他通过之前这些数据和你的答案已经发现你对工作的要求了，也就是学习到了图4.2所示的那棵决策树，并能用它来预测出哪些工作再推荐给你你会去参加面试。

图4.2说明了决策树的基本构成，它包括内部节点、叶子节点和有向边，从根节点开始，到叶子节点结束。内部节点也称为分支，为测试内容或特征值；叶子节点为结论。按照任务的不同，决策树也相应地可以分为分类树和回归树两类。

决策树的特点就是能从给定的数据集中找规律，对新数据进行正确分类，或者说是能由训练数据集的特征空间来估计分类空间的条件概率模型。更通俗一点说，就是给定了你数据和分类，结果让你可以进行监督学习，通过决策树的方法进行学习，它能找出哪个节点做根节点更好。

决策树的主要优点如下：

（1）既可以用于回归问题，也可用于分类问题；

（2）算法相对比较简单，分类速度、效率相比其他一些分类算法更快、更高；

（3）能用于非线性空间数据的分类。

主要缺点是：可能会产生过度匹配（也叫过拟合（overfitting））。具体来说，就是得到的决策树对用于训练的已知数据，可以进行很好的分类和拟合，但是对于新的没有训练过的数据，分类或拟合的结果并不好。

出现过拟合，主要原因还是对业务逻辑的理解还不透彻，导致样本数据有问题或者决策树构建方法不合理。样本问题可能是由样本里噪声数据干扰过大、样本抽取错误、样本太少、建模时使用了样本中的太多无关输入变量等造成的。比如上面找工作的例子，给你推荐工作的人在你决定是否参加面试的数据中额外加上公司名字长度、面试官性别、面试日期是否是奇数等变量，就很有可能将某些纯属巧合的因素当成你是否参加面试的关键因素了。另外，在决策树模型构建中，如果不去控制决策树的生长，就可能导致每个叶子节点只包含单纯事件数据或非事件数据，这样对于训练数据会很好，可是对于新数据就会很糟。针对这一点，在决策树构造中还会加入剪枝（pruning）过程，提前停止决策树生长或者对已经生成的决策树按照一定规则进行修剪。

决策树的构造通常包括三个部分：特征选择、决策树生成和决策树修剪。具体的构造过程如下：

（1）递归地选择最优特征，并根据该特征将训练数据划分成不同的数据子集，使各数据子集有一个在当前条件下最好的分类；

（2）由根节点开始分割，一直到叶子节点；

（3）如果有数据子集不能被正确分类，则对其选择新的最优特征，继续分割，递归进行，直到所有数据子集被基本正确分类或没有合适特征为止；

（4）每个子集都被分到叶子节点，即有了明确分类，决策树形成；

（5）对决策树进行简化。

下面对决策树的这三个部分分别进行介绍。

1.特征选择

究竟选择用哪个特征来划分数据呢？基本原则就是将无序的数据变得更有序。所以首先要解决如何表示数据有序的程度这一问题，这样才能知道数据是否变得更有序了。如果学过信息论或者通信原理，就会知道可以采用熵（entropy）的概念对信息进行量化。熵的取值范围为0～1，它可以反映随机变量的不确定性程度，熵越大，就表示随机变量的不确定性越大。如果是一堆杂乱无章的数据，熵值就会很大，而一旦数据变得有序了，熵值就会变小。

先看一下信息的熵计算公式：

它反映的是所有可能发生的X事件带来的信息量的期望。熵计算公式中对概率取对数的底可以是2，也可以是e，由换底公式可知两者只是差了一个固定的倍数ln2而已。

如果Y也是随机变量，可以取不同的值，那么X在Y条件下的不确定性，也就是在Y条件下X的熵的数学期望就称为条件熵（conditional entropy），其计算公式为：

如果以上两个计算公式中的概率是由数据估计而来的，尤其是采用的是最大似然估计，那么这两个计算公式所表示的熵就可以分别称为经验熵和经验条件熵。假设数据集为D，分成了K类，Ck为第k类数据子集，重新改写这两个计算公式，数据集D的经验熵公式为：

针对某个特征A，它有n种取值，数据集D的经验条件熵公式为：

其中，Di表示D中特征A取第i个值得到的数据子集，Dik表示Di中属于第k类的数据子集。

进一步，引入信息增益（information gain）的概念，其定义为划分之前的熵减去划分之后的熵（划分之后的熵为条件熵）。信息增益计算公式如下：

也就是求划分之后熵的下降值。以某个特征进行划分，使得熵下降得越多，说明用这个特征划分得到的数据越有序。这样，就给选择特征提供了一种依据，即选取能使信息增益最大的分类特征对数据集进行划分。

下面，通过一个例子来看一下具体计算方法。

例4.1　假设有贷款申请数据如表4.1所示，计算该表“是否批准”项的经验熵以及在“是否有自己的住房”条件下的条件经验熵，并计算以“是否有住房”进行划分后的信息增益。

表4.1　贷款申请数据表

解　通过对表进行统计，发现总共有15条数据，“是否批准”项有两类，即9个是、6个否。代入式（4.3），

“是否有自己的住房”数据有两种，即有自己的住房6个和没有自己的住房9个。在这个条件下，有自己的住房的6条记录中获批贷款和未获批贷款的记录分别为6条和0条，经验熵为H（D|A=有住房）=0；没有自己的住房的9条记录中获批贷款和未获批贷款的记录分别为3条和6条，经验熵为由式（4.4）求出经验条件熵为

所以由式（4.5）计算得到信息增益为G（D，A）=0.971-0.551=0.42。

将信息增益作为划分依据就构成了决策树中的ID3（iterative dichotomiser 3，第三代迭代二分器）算法的核心。另外，还有其他一些常用的构造决策树的算法，比如C4.5算法和CART（classification and regression tree，分类与回归树），它们分别选择其他类似的参数——信息增益比（gain ratio）和基尼指数（gini index）作为数据划分依据。

将信息增益作为划分依据存在一个问题，即会比较偏好可取值数目较多的特征，这种特征的信息增益往往较大。信息增益比，也称为信息增益率，能克服这一缺点。它是信息增益与划分前熵的比值，其计算公式为：

然而信息增益比会偏向可取值数目较少的特征，因为这种特征H（D）容易偏小，也就是信息增益比公式（4.6）中的分母容易较小，导致信息增益比偏大，所以在C4.5算法中并未直接找信息增益比最大的特征进行划分，而是首先找信息增益高于平均值的特征，然后从中选择信息增益比最大的特征。

由于信息增益和信息增益比都需要计算对数，因此CART算法选用了基尼指数这一参数作为划分依据，其计算公式为：

其中，k代表类别。

特征A条件下集合D的基尼指数计算公式为：

因为CART为二叉树，所以是二分类，即只分为两类，于是式（4.8）可以写为：

基尼指数反映了从数据集中随机抽取样本，其类别标记不一致的概率，代表了数据的不纯度，取值范围也是介于0到1之间，越小代表数据的不纯度越低，数据越有序，特征越好，所以选取基尼指数最小的特征进行数据划分，相当于基尼指数增益最大。

针对例4.1，由式（4.6）不难算出以“是否有住房”划分的信息增益比为：

由式（4.7）、式（4.8）得到其由“是否有住房”划分的基尼指数为：

2.决策树生成

前面提到的ID3算法、C4.5算法和CART算法都是常用的决策树生成算法，决策树生成的过程基本都按照图4.3进行迭代。(www.xing528.com)

图4.3　决策树生成过程

下面具体来看一下ID3算法及其实现。

ID3于1975年由澳大利亚科学家Ross Quinlan提出。ID3算法中并未考虑剪枝的问题。该算法的输入是训练数据集D、特征集A、信息增益阈值ε；输出为决策树T。基本过程如下：

（1）若D中所有数据属于同一类Ck，则T为单节点树，将Ck作为该节点的类标记，返回T；

（2）若A为空，则T为单节点树，将D中数据最多的类Ck作为该节点的类标记，返回T；

（3）否则，计算A中各特征对D的信息增益，选择最大的特征Ag；

（4）如果Ag的信息增益小于信息增益阈值ε，则置T为单节点树，将D中数据最多的类Ck作为该节点的类标记，返回T；

（5）否则，对Ag的所有取值ai，依照Ag=ai将D分为若干子集Di，把Di中数据最多的类作为类标记，构造子节点，由节点及其子节点构成树T，返回T；

（6）对第i个子节点，以D=｛Di｝为训练数据集，以A=｛Ag｝为特征集，递归调用步骤（1）～（5），得到子树Ti，返回Ti。

针对表4.1中的数据，看一下Python实现方法，下面说明了主要代码，完整代码参考实验部分。

首先，需要选择合适的知识表示方法来表示数据集中的数据，为了简化，对数据内容做了简单映射：年龄段（0，青年；1，中年；2，老年），有工作（0，否；1，是），有自己的房子（0，否；1，是），信贷情况（0，一般；1，好；2，非常好），是否贷款（no，否；yes，是）。这部分并非必要。

Python中可以用列表来存储每个数据，用二维列表存储表格。

程序中需要反复进行经验熵的计算，这通过函数calcShannon Ent（dataSet）实现，且输入变量为数据集列表，输出经验熵的值。程序中还有其他一些功能，也都设计成函数的形式，这样不仅方便使用，而且代码更简洁和便于阅读。

决策树的生成过程也相当于是机器学习中的训练过程，主要由create Tree（dataset，labels，feat Labels，epsilon）函数实现，其中代码注释部分标注的Step1～Step6对应着前面介绍过的ID3算法基本过程中的6个步骤，且Step5包含在了Step6递归调用的函数参数中。

完整代码参考本书所附文件\ex4_1_DT\Decision Tree01_ID3.py，其输出如下：

它采用字典嵌套的方式表示树结构，对应的决策树如图4.4所示。

图4.4　表4.1数据对应的决策树示例

在应用决策树进行预测时，主要就是通过一系列的if…elif…else结构，根据输入数据的特征项进行选择。

ID3算法虽然比较简单，但应用还是很广泛的，比如Ross Quinlan用它预测国际象棋最后阶段白方一个王一个车，黑方一个王一个骑士，导致黑方3步以内输掉的棋局能，特征采用了23个不同的高层次棋局属性。

ID3算法的缺点也比较明显：一是使用信息增益进行特征选择会偏向可取值较多的特征，而且信息增益阈值ε不容易设定；二是如果样本特征很多，则产生的树容易过深，最终导致模型泛化能力较差，出现过拟合；三是无法处理连续值特征和没有剪枝过程。

C4.5算法和CART算法也是常见的决策树生成算法，算法流程和ID3算法类似。

其中，C4.5算法由Ross Quinlan在1993年提出，可以看作是对ID3算法的一个扩展。它在选择特征进行划分时，会综合考虑信息增益和信息增益比，在信息增益高于平均水平的特征中选取信息增益比最大的特征。另外，它考虑了将取值为连续值的特征进行离散化处理的方案。假设某个数据集中包含每天的平均气温这个特征和是否开空调的数据，气温对应的取值就是连续值25.3（N）、22.1（N）、35.1（Y）、33.6（Y）、23.7（N）、20.5（N）、31.0（Y），C4.5算法首先会对其进行升序排序，得到20.5（N）、22.1（N）、23.7（N）、25.3（N）、31.0（Y）、33.6（Y）、35.1（Y），然后选取相邻的两个值之间的中点作为切分数据集的备选点，这样，N个数据就会产生N-1个备选点，比如，20.5和22.1之间就可以产生备选点（≤21.3和＞21.3），然后计算这N-1种情况下的信息增益，选择信息增益最大的备选点作为最佳划分点，然后计算其信息增益比并作为该特征划分的信息增益比。为了避免算法倾向于选择连续值的特征作为最佳划分点，计算信息增益比时还需要对信息增益的值进行修正，即减去，其中N是连续值的特征的取值个数，D为训练数据数。为了减少运算量，对于N-1个备选点，只计算会使分类发生变化的备选点的信息增益，比如对于上面的气温数据，就可以只选择25.3和31.0之间的中点（≤28.15和＞28.15）计算信息增益。

在实际应用中，还可能会遇到一个问题，就是数据集中的数据不完整，出现缺失值。这个时候该怎么办呢？如果直接丢弃数据，就造成了浪费。要解决这个问题，就要考虑3种情况下的处理方案。

首先是特征选择问题，以对应特征下没有缺失的样本数据进行计算，比如计算该特征没有缺失情况下的信息增益；然后乘以没有缺失的样本占总样本的比例值进行修正，作为该特征的信息增益；最后还是和以前一样，选择信息增益最大的特征进行数据划分。

在进行数据划分时，又会遇到问题，就是对该特征下缺失的数据该如何划分？这时，可以引入权重的概念，将缺失该特征的数据按一定权重分配到该特征的不同取值分支中，权重则可以按该特征不同分支无缺失数据占总无缺失数据的比例给出。这样在该分支下，无缺失的数据权重为1，缺失的数据则按一定比例划拨了一份过来，也可以看作是不缺失了，只是权重不为1，接下来的计算就相同了，只是在统计计数时，要注意缺失项的权重值不是1。下面以表4.2为例，计算一下相关信息增益。

例4.2　计算表4.2中按照“是否有自己的住房”划分后的信息增益以及在该划分下，进一步计算将“无自己的住房”的数据按照“是否有工作”进行划分的信息增益。

表4.2　有缺失项贷款申请数据表

解　首先按照无缺失项计算按照“是否有自己的住房”划分的信息增益，表中统计信息为：总共15条信息，有13条无缺失记录（7获批，6否），7条没自己的住房（1获批，6否），6条有自己的住房（6获批，0否）。

按照“是否有自己的住房”划分之前，信息熵为

划分之后，有

假设此时选择该项进行划分后，计算按照“是否有工作”对没有住房的数据子集进行划分的信息增益。

首先确定权重，是否有住房项13条无缺失项有2个取值，7条没住房，6条有住房，所以将两条缺失数据分给没住房的权重为7/13，分给有住房的权重为6/13，接着计算在没有住房的情况下按工作进行划分的信息增益。

划分前，没有住房且工作项无缺失数据占没有住房总数据的比为

可简单理解为：将“是否有自己的住房”的两条缺失记录分配到这里，相当于每条只占7/13的可能是没有住房，或者是说每条记录分配了7/13的到这部分来了。

在决策树模型训练好以后，如果用于预测的样本数据有缺失项，又该怎么预测呢？这时，当分类进行到某个未知的节点时，就假设会出现所有可能的分类结果，这样就会存在多条路径，分类结果可能是类别分布而不是某一类别，选择概率最高的作为预测结果。

CART算法由Breiman于1984年提出。从名称也可以看出，它既能用于分类，也可以用于回归。当它作为分类树时，采用基尼指数作为特征划分的依据；当它作为回归树时，采用样本的最小方差作为特征划分的依据。在回归应用中预测结果输出的具体值，一般采用相应节点的中值、平均值等来获得。

CART算法同C4.5算法是非常相似的，但是它不像ID3算法和C4.5算法那样可以生成多叉树，它生成的是一棵二叉树。如果某个特征有多个取值，那么它就会对多个取值的不同组合方案进行划分，分别计算不同划分方案的子节点的基尼指数或样本的最小方差，从中选择最优的划分方案。比如，年龄段特征有青年、中年、老年三个取值，那么就可以将年龄特征分为［［青年］，［中年，老年］］、［［青年，中年］，［老年］］、［［中年］，［青年，老年］］三种组合去分别计算划分后的基尼指数值，按照值最小的方案进行划分。

3.决策树修剪

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类没有那么精确，也就是出现过拟合现象。其中一种解决方法是考虑决策树的复杂度，对已经生成的树进行简化，也就是剪枝。剪枝是对决策树进行优化，提高其泛化性能很重要的一个环节。

决策树的剪枝可以分为预剪枝和后剪枝两类。预剪枝是指在决策树生成过程中，在对节点进行划分之前，先估算其是否能带来泛化性能的提升，如果不能则停止划分，将其标记为叶子节点；后剪枝则是先训练生成一棵完整的决策树，然后对内部节点进行考察，若将该节点对应的子树替换为叶子节点能带来泛化性能的提升，则进行剪枝，将该节点用叶子节点替换。

那么，如何判断决策树泛化性能是否有所提升呢？一种方法是通过训练数据集上的错误分类数量来估算，还有一种方法是采用测试数据集上的错误分类来估算。

前面介绍的ID3算法用到了阈值，能提前停止树的生长，可以看作是预剪枝算法之一，只是阈值的大小难以确定，实用性不强。另外，采用节点划分前和划分后的准确率进行比较来确定是否划分，是基于贪心的策略，会带来欠拟合风险。后剪枝欠拟合的风险很小，泛化性能往往也优于预剪枝，但是训练时间会大很多。C4.5算法采用的策略就是后剪枝策略，称为悲观错误率剪枝（PEP，pessimistic error pruning）。它采用自上而下的方式评估每一个内部节点，预测剪枝后错误率是否保持或下降，如果是就剪枝。它不需要单独的测试数据集。

还有一种后剪枝算法，称为错误率降低剪枝（REP，reduced error pruning）算法。它采用自底向上的方式遍历所有子树，用叶子节点替换子树，看错误率是否有所降低。它需要一个测试数据集。

CART算法采用了基于代价复杂度剪枝（CCP，cost complexity pruning）的方法，会迭代生成一系列嵌套的剪枝树，需要使用测试数据集评估所有的树，从而选择最优树。

4.随机森林

随机森林（random forest）是一种叫作bagging的集成算法。bagging算法是将原始数据集随机抽样成N个新数据集，然后用同一个机器学习算法进行学习，得到N个模型，最后得到一个综合模型。随机森林由多个决策树组成，每一棵决策树都是一棵CART分类与回归树，所以随机森林既可以进行分类，也可以进行回归。当随机森林用于分类时，分类的结果由每一个子决策树的分类结果中的多数来决定；当随机森林用于回归时，最终结果取每棵子决策树回归结果的平均值。