决策树分类在服刑人员再犯罪预测上的应用

决策树是通过一系列规则对数据进行分类的过程，它提供一种在什么条件下会得到什么值的类似规则方法，决策树分为分类树和回归树，分类树对离散变量做决策树，回归树对连续变量做决策树。下面以一个例子来进行说明：

一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？

母亲：26。

女儿：长得帅不帅？

母亲：挺帅的。

女儿：收入高不？

母亲：不算很高，中等情况。

女儿：是公务员不？

母亲：是，在税务局上班呢。

女儿：那好，我去见见。

则上述的决策树见图5-17所示。

图5-17　找对象的决策树

图5-17就是女孩的是否见对象的决策过程，这就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员将男人分为两个类别：见和不见。由此，我们可以说决策树是一种描述对样本实例（男人）进行分类（见或不见）的树形结构。决策树由节点和有向边组成。最上部是根节点，此时所有样本都在一起，经过该节点后样本被划分到各子节点中。每个子节点再用新的特征来进一步决策，直到最后的叶节点。叶节点上只包含单纯一类样本（见或不见），不需要再进行划分。决策树中节点包括两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个分类。

决策树是属于机器学习中监督学习分类算法中比较简单的一种，决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径（有向边）则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

如果不考虑效率，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树。决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。决策树的构造一般包含三个部分：

（1）特征选择：特征选择是指从训练数据众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。

（2）决策树生成：根据选择的特征评估，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长。对树结构来说，递归结构是最容易理解的方式。

（3）剪枝：决策树容易过拟合，一般需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

1.特征选择

决策树构造的核心问题在于：

①如何选择特征作为待分裂的节点；

②如何选择待分裂节点的特征分裂点。

要选择特征和特征分裂点，就需要先掌握相关不纯度的概念。所谓不纯度是指用来表示落在当前节点的样本的类别分布的均衡程度^[21]。决策树分裂节点的目标是使得节点分裂前后，样本的类别分布更加不均衡，也就是不纯度需要降低。因此，我们每次分裂节点时，选择使得节点分裂前后，不纯度下降最大的特征和分裂点。接下来我们以银行贷款为例进行说明，银行一般依据借贷人的收入、受教育程度、婚姻状况等对房贷进行决策，依据的规则如下：

①若借贷人收入高，则借贷人不会违约；

②若借贷人收入中等且学历为本科或研究生，则借贷人不会违约；

③若借贷人收入中等且为高中及以下学历，则借贷人会违约；

④若借贷人收入低，则借贷人会违约。

银行贷款数据见表5-13所示。

表5-13　银行贷款数据

假设分别选择收入、教育程度两个特征作为根节点进行分裂，收入按照低、中等、高，教育程度按照高中及以下、本科、研究生分别分为三个子节点，数据在分裂之前的数据集为D0＝{1，2，3，4，5，6，7，8，9，10}，用编号表示样本数据，则分裂见图5-18所示。

图5-18　根据不纯度的下降程度选择特征和对应的分裂节点

选择特征“收入”作为待分裂的节点，将数据集D0分为D1、D2和D3，对应的节点分别为t1，t2，t3；选择特征“教育程度”作为待分裂的节点，将数据集D0分为D4、D5和D6，对应的节点分别为t4，t5，t6。假设用Imp（.）表示节点的不纯度，那么按照特征“收入”分裂节点前后的不纯度下降值为Imp（t0）-Imp（t1 t2 t3）；按照特征“教育程度”分裂节点前后的不纯度下降值为Imp（t0）-Imp（t4 t5 t6）。对比不同特征不纯度下降值，选择不纯度下降值更大的作为分裂节点。对节点的不纯度进行度量可以采用：信息熵、Gini指数、误分率。

（1）信息熵。熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度，无序程度越高，不确定性越大，熵也就越大。在概率论中，信息熵给了我们一种度量信息不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值。在决策树场景下，用信息熵度量一个节点分布的不纯度。若待分类的事物可能划分在m类中，则节点t中第ci类样本的概率为：p（ci｜t），那么节点t的信息熵就定义为：

当节点中的样本均匀分布在每一个类别时，信息熵取得最大值log2m，说明此时节点的不纯度最大；当所有样本属于某一个类别时，信息熵取得最小值0，说明此时节点的不纯度最小。将各数据集也视作是分裂节点，则图5-18中的特征“收入”和“教育程度”节点中两个类别的样本数及表5-13中的样本总数分类见表5-14所示。

表5-14　收入和教育程度节点中两个类别的样本数

对于表5-14中的节点，信息熵的计算如下：

上述计算中，我们定义0log2 0＝0。基于节点信息熵的定义，计算节点分裂前后信息熵的下降值，称为信息增益：

其中，节点t0（等价于D0）含有n个样本数据，经过分裂生产K个子节点，每一个子节点中的样本数分别为{n1，n2，…，nk}。根据公式（5.48）可以计算出特征“收入”和“教育程度”的信息增益分别为：

在特征“收入”分裂节点后，三个子节点中的样本数分别为：n1＝2，n2＝5，n3＝3；在特征“教育程度”分裂节点后，三个子节点中的样本数分别为：n1＝4，n2＝3，n3＝3，而总样本数n＝10。

显然，特征“收入”的信息增益大，因此选择特征“收入”作为根节点，其他子节点的选择依次类推。

在实际应用中，利用信息增益通常选择的是节点分裂成很多子节点的分裂节点，然而，当节点的样本数较小时，容易造成过度拟合。一个克服上述缺点的方法是使用节点分裂的子节点的样本数信息对信息增益进行修正，称为信息增益率，如下：

(www.xing528.com)

其中SplitInfo为分裂信息，信息增益率通过分裂信息对信息增益进行调整，能避免节点分裂成很多数据量的叶子节点。

（2）Gini指数。用信息增益来构建决策树计算量较大，因此引入另外一种构建决策树的方法Gini指数。Gini指数是20世纪初意大利学者吉尼根据劳伦茨曲线所定义的判断收入分配公平程度的指标，是比例数值，在0和1之间。在决策树场景下，用Gini指数来度量决策树中落在某个节点的不同类别样本分布的不纯度。假设某个数据集D共有m个类，则节点t中第ci类样本的相对频率为：p（ci｜t），那么节点t的Gini指数就定义为：

当节点中属于每个类别的样本数均匀分布，Gini指数取得最大值（1-1/m），此时，该节点的不纯度最大；当样本节点中所有样本数据属于一个类别时，Gini指数取得最小值0，此时，该节点的不纯度最小。在表5-14银行贷款数据例子中，按照特征“收入”对根节点进行分裂，则三个叶子节点的Gini指数计算示例如下：

在表5-14银行贷款数据例子中，按照特征“教育程度”对根节点进行分裂，则三个叶子节点的Gini指数计算示例如下：

假设初始数据集为节点t，样本数为n，节点t经过某种方式分裂后生成了K个子节点，其中第k个子节点tk中的样本数为nk，则节点t分裂后的Gini指数可表示为：

不同的特征对于不同的分裂方式，需要选择使得Gini指数下降值最大的分裂方案，也即：（Gini（t0）-Gini（t0）split）为最大。其中，t0为根节点，由此，选择特征“收入”分裂后的Gini指数下降值为：

选择特征“教育程度”分裂后的Gini指数下降值为：

同理，可计算出特征“婚姻状况”和“性别”分裂根节点后Gini指数下降值分别为0.020和0，特征“收入”的Gini指数下降值最大，因此选择特征“收入”为分裂根节点。

在分裂根节点后，我们发现在特征“收入”的取值“中等”子节点中包含了违约和未违约样本，因此，还需要对子节点再次进行分裂，选择特征的依据与分裂根节点时类似，因此，得到完整的决策树，而最终的叶子节点只包含一类样本，见图5-19所示。

图5-19　根据Gini指数得到的完整决策树

（3）误分率。误分率是第三种度量节点不纯度的方法。假设数据集D中共有m类，则在节点t中第ci类数据的相对频率为p（ci｜t），由此可以得出节点t的误分率为：

其中，误分率代表的是：当按照多数类来预测当前节点样本的类别时，被错误分类的样本数据比例。当样本数据均匀地分布在每一个类别时，误分率取得最大值：（1-1/m），此时不纯度最大；当样本数据属于某一个类别时，误分率取得最小值：0，此时不纯度最小。对于表5-14中的6个节点，其误分率的计算如下：

由此，我们可以得出按照特征“收入”进行分裂后的误分率为：0＋0.400＋0＝0.400，按照特征“教育程度”进行分裂后的误分率为：0.250＋0.333＋0.333＝0.916，显然特征“收入”的误分率小，因此我们选择特征“收入”进行分裂根节点。

对于二分类问题，当正类样本的相对频率为p，则负类样本的相对频率就为1-p，此时，信息熵、Gini指数、误分率三种不纯度度量值分别为：

对于上述三种不纯度度量值，当相对频率为0或1时，分类效果都最好，不纯度都为0；当相对频率在0.5时，三种不纯度度量值的分类效果都最差；在相对频率在0～0.5或0.5～1不断变大的过程中，使用信息熵度量的不纯度最大，对不佳分裂行为的惩罚也最大，Gini指数次之，误分率不纯度最小，效果最好。

2.决策树的生成

决策树的生成一般是从根节点开始，根据某种规则（信息熵、Gini指数或误分率）选择最佳特征分裂根节点；然后选择子节点的特征继续分裂，直到节点中的样本只有一种类别。为了找到最佳的特征、划分出最好的结果，我们必须评估数据集中蕴含的每个特征，寻找分类数据集的最好特征。对于离散型特征，节点根据特征取值进行分裂，在图5-17中，节点特征“收入”，则根据其取值为“高”“中等”“低”分裂成三个子节点；对于连续型特征，则需要根据具体特征值（分裂点）来分裂子节点，在图5-17中，根节点特征“年龄”，分裂点选择30，分裂成≤30和＞30两个子节点。一般而言，当某个节点中数据只属于某一个类别（分类问题）或者方差较小（回归问题）时，节点不再进行进一步分裂。完成根节点分裂之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则该分支处理完成，称为一个叶子节点，即确定了分类。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内（叶子节点）。

3.剪枝

在决策树建立的过程中，若不加任何限制，可能产生过于复杂的树（例如树的层数太多、树的节点数过多等），从而使得最后生成的树可能完全拟合原始数据，导致数据训练过程的过拟合。另外，决策树产生过拟合，也可能是由于训练数据中的噪音或孤立点。因此，在决策树的构建过程中，还要进行树剪枝（Tree Pruning），来避免数据过拟合。通常，树剪枝使用信息增益等统计度量，减去最不可靠的分支，这将导致较快的分类，提高决策树独立于训练数据正确分类的能力。

树剪枝分为预剪枝（PrePruning）和后剪枝（PostPruning）两种。预剪枝指在决策树生长过程中，设置一个不纯度下降阈值（例如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、信息增益小于一定阀值等），在对节点分裂之前，如果不纯度下降值小于给定的阈值，则停止对节点进行分裂，并将该节点标记为叶子节点，使得在产生完全拟合的决策树之前就停止生长。预剪枝的检验技术也有很多，但如何确定一个合适的阀值也需要一定的依据，阀值太高导致模型拟合不足，阀值太低又导致模型过拟合。

后剪枝是在决策树生长完成之后，按照自底向上的方式修剪决策树。通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等。后剪枝操作是一个边修剪边检验的过程，一般规则标准是：在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树对测试数据的预测精度，并计算出相应的错误率，如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么就剪掉该子树。

预剪枝可能过早地终止决策树的生长，后剪枝一般能够产生更好的效果，实践中被证明更成功。但后剪枝在子树被剪掉后，决策树生长的一部分计算就被浪费了。决策树是否需要剪枝，需要通过某种度量来进行判定，判断决策树的优劣指标可以定义为：

其中，｜T｜表示某棵决策树T包含的节点数，nt表示节点t中的样本数，imp（t）表示节点t的某种不纯度度量，例如信息熵、Gini指数或误分率。公式（5.53）的第一项为决策树对训练集的拟合程度，第二项为决策树模型的复杂度。第一项减小，第二项就会增大，反之亦然。因此，可以权衡拟合度和复杂度，而a表示复杂度控制参数，代表了预先设置的一种权衡倾向，a越大意味着对复杂度的决策树模型有更高的惩罚。

两种剪枝法的优缺点：

预剪枝：降低过拟合风险，由于某些结点的后续分支在训练前就被剪掉，因此可以显著减少训练时间。但是也正是由于后续分支的预测精度未被比较就剪掉了，存在这种情况：虽然当前节点泛化性能差，但是后续分支的泛化性能却极好。预剪枝忽略了这些好的情况，所以存在欠拟合的风险。

后剪枝：欠拟合风险小，泛化能力往往优于预剪枝。但是训练时间开销比未剪枝和预剪枝大。

4.常见的决策树算法

基于不同的不纯度度量分裂评价标准、能够处理的特征类型和目标特征的类型，研究者提出了不同的决策树算法，常见的代表性的有ID3、C4.5、CART三种经典的决策树算法。

（1）ID3算法。ID3（Iterative Dichotomiser 3）是由澳大利亚计算机科学家Ross Quinlan在1986年提出的一种经典的决策树学习算法。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。ID3使用信息熵作为节点不纯度的度量，每次根据“最大信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来分裂节点，也就是说如果一个特征有4种取值，数据将被分裂为4个子节点，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用，所以有观点认为这种分裂方式过于迅速。ID3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵（混乱度）减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择信息熵减少程度最大的特征来分裂节点数据（贪心），也就是“最大信息熵增益”原则。ID3算法侧重于处理特征值较多的特征，但是不能处理特征值为连续的情况，这是因为ID3使用信息熵增益作为节点分裂的标准导致的。另外，ID3没有考虑每个叶子节点样本数的大小，可能导致叶子节点中的样本数量较少，从而造成过拟合问题。

（2）C4.5算法。ID3采用的信息熵增益度量存在一个缺点，它一般会优先选择有较多属性值的特征，因为属性值多的特征会有相对较大的信息增益，而C4.5是Ross Quinlan于1993年在改进ID3算法上述缺点的基础上而提出的。首先，对于连续型特征，不再通过枚举所有可能取值的方式来分裂节点，而是通过某一个分裂阈值来分裂节点。例如对于连续型特征“年龄”，假设选择特征阈值为45，那么将把节点分裂为小于等于45和大于45的两个子节点。其次，为了避免分裂成较多子节点，C4.5算法使用信息熵增益率[见公式（5.49）]来代替信息熵增益[见公式（5.48）]作为节点分裂的评价准则，信息增益率通过引入一个被称作分裂信息（Split information）的项来惩罚取值较多的特征，不再偏向于选择那些取值较多的离散型特征进行节点分裂。

（3）CART算法。ID3和C4.5算法主要用来预测分类问题，不能用来预测回归问题（目标值为连续值），而CART（Classification and Regression Tree）则能够同时处理分类问题和回归问题。CART算法是L.Breiman，J.Friedman，R.Olshen和C.Stone于1984年提出的。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子节点多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用Gini指数来选择最好的数据分割的特征，Gini指数描述的是节点的不纯度，使用Gini指数下降值作为节点分裂评价的准则。CART回归时，使用节点数据的目标特征的方差作为不纯度的度量，方差下降值作为节点分裂的评价准则。

CART算法和另外两个经典决策树算法的其他的不同点是：节点每次分裂只分裂成两个子节点。对于连续型特征，通过选择特征分裂阈值，按照特征分裂阈值把当前节点分裂成两个子节点；低于离散型特征，CART算法不再根据每一个特征取值进行分裂子节点，而是每次选择一个具体的特征值，根据样本数据是否满足该特征值来分裂成两个子节点。例如，对于离散型特征“教育程度”，进行节点分裂时不再选择特征取值范围{高中及以下，本科，研究生}，而是选择特征值“高中及以下”作为节点分裂的评价准则，则根据“教育程度是高中及以下”和“教育程度不是高中及以下”将当前节点分裂成两个子节点。

5.决策树的优点和缺点

决策树的优点主要有：

（1）决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解；

（2）决策树模型可以可视化，非常直观；

（3）应用范围广，可用于分类和回归，而且非常容易做多类别的分类；

（4）能够处理数值型和连续的样本特征。

决策树的缺点主要有：

（1）很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting）。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量；

（2）学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的，这种算法不能保证建立全局最优的决策树。Random Forest引入随机能缓解这个问题。