决策树的定义、构成及应用原理

决策树方法是一种较为通用的分类方法，决策树模型简单易于理解，且决策树转变为SQL语句很容易，能有效地访问数据库，特别地，很多情况下，决策树分类器的准确度与其他分类方法相似甚至更好。 目前已形成了多种决策树算法，如ID3、 CART、 C4.5、 SLIQ、SPRINT等。本节主要介绍决策树定义及算法原理。

1）决策树结构

决策树是一种树性结构，基本组成部分包括根节点、叶节点、分割点（split point）、分支（split）。树的最顶层节点是根节点，是整个决策树的开始；叶节点代表类或类的分布，对应一个类别属性C的值；非叶节点对应一个分割点，表示对一个或多个属性的测试，用于决定数据样本的分支，每个分割点都有一个分支判断规则（splitting predicate）：对连续属性A，分支判断规则形式是value（A）＜x（x是属性A值域中的一个值）；而对离散属性A，分支判断规则形式则为value（A） ∈x［xdomain（A）］。每个分支代表一个测试输出，要么是一个新的分割点，要么是树的结尾（叶节点）。

例5.1：图5-1a是一个不同年龄客户购买车的风险评估的数据样本集，图5-1b是图5-1a中训练样本的一个决策树。其中，（年龄＜25）和（车类型in ｛sports｝）是两个分割点，它们把数据样本分成高风险和低风险两类。利用这个决策树，可以鉴别未来保险申请人的类别：高风险类或低风险类。

图5-1　数据集及对应的构造树

定义5.4（决策树，decision tree）：给定一个数据样本集D= ｛X1， X2， …， Xn｝，数据集中的属性有｛A1，A2， …， Ah｝，其中Xi = ＜ xi1 ， xi2 ，…，xih＞ （1≤i≤n），类集合C=｛C1，C2，…，Cm｝，与数据样本集D相关的决策树具有如下性质：

（1）每个非叶节点选用一个属性Ak（1 ≤k ≤h）进行分割。

（2）每个分支是一个测试输出。

（3）每个叶节点表示一个类分布，由一个类Cj（1≤j≤m）标记。

根据决策树的各种不同属性，决策树主要有以下几种：

（1）决策树的非叶节点的测试属性是单变量的，即每个非叶结点只包含一个属性；或是多变量的，即存在包含多个属性的节点。

（2）根据测试属性的不同属性值的个数，使得每个非叶节点有两个或多个分支。如果每个非叶节点只有两个分支称为二叉决策树；允许节点含有多于两个子节点的树称为多叉树。

（3）每个属性值的类型可能是数值类型，也可能是离散类型的。

（4）分类结果既可能是两类又可能是多类，如果二叉树的结果只能有两类，则称为布尔决策树。

2）决策树分类算法原理

使用决策树解决分类问题包括两个主要步骤：

（1）使用训练数据集构造决策树。

（2）对数据集中的每个待预测数据利用决策树决定其所属类别。

决策树模型构造快且简单易于理解，但在决策树构造过程中将面临如下一些主要问题：

（1）训练数据集的大小。生成的决策树的结构取决于训练数据集的大小。如果训练数据集太小，那么生成的决策树可能不够详细，导致难以适应更一般的数据；而如果训练数据集太大，可能导致生成的树过适应（或过学习）。

定义5.5（过学习）：推出过多的假设与训练数据集相一致而导致所做出的假设泛化能力过差称为过学习（或过适应）。

因此，过学习造成所建立的决策树对历史数据样本可能非常准确，但一旦应用到新的数据样本时准确性却急剧下降。后面会给出尽可能避免过学习的剪枝策略。

（2）属性选择度量（最佳分支属性、分支属性顺序及分支数量的选择）。如何找到节点测试的分割点、找到分割点后如何划分数据是决策树构造算法的关键，目前几种常用的属性选择方法，如信息增益标准Gain、最小Gini指标（lowest Gini index）方法等，对应前者的算法有ID3、 C4.5等，后者有CART、 SLIQ和SPRINT等。这些算法要求计算每个属性的信息增益，然后选择具有最高信息增益的属性作为当前节点的测试属性，对该属性的每个值创建分支，据此划分样本，这个属性使得对结果划分中的样本分类所需的信息量小，且对一个对象分类所需的期望测试数目最小。

分支数量：属性的值域越小则分支的数量相对较小，如性别属性；然而如果值域是连续值或具有大量的离散值，则分支的数量会难以决定。

（3）树的结构。一些算法仅建立二叉树、层次少的平衡树，但常常需要复杂的具有多路分支的决策树。这要求根据具体问题的需求进行选择权衡。

（4）停止的标准。为防止树的过大生长（如树的大小、高度、叶节点个数等），需要在决策树构造过程中设定一定的停止标准以较早停止树的增长，防止过适应。

（5）剪枝。为避免过学习，需要通过删除部分节点和子树，对决策树进行剪枝。

3）决策树分类的详细过程

（1）建立决策树，利用训练样本以自顶向下递归的方式构造决策树。初始情况下，数据都在根节点，然后递归的进行数据切分，每次切分对应一个节点以及一个测试判断，对每个切分都要求分成的组之间的“差异”最大。

具体步骤如下：创建节点，若样本都在同一个类，则该节点为叶节点，并用该类类标号标记；否则选择具有最高信息增益的属性作为当前节点的测试属性，对测试属性的每个已知的值，创建一个分支，并据此划分样本。以此递归形成每个划分上的样本决策树，直到以下情况之一出现，则停止划分：给定节点的所有样本属于同一类（这样的节点有时被称为纯节点）；没有剩余属性可以用来进一步划分样本（则以样本中的多数所在的类标记它）；分支属性没有样本（则以样本中的多数类创建一个叶节点）。

为使读者更加清楚这个过程，下面给出决策树生成算法的伪代码（图5-2）：

图5-2　决策树生成算法

（2）简化决策树。(www.xing528.com)

①简化决策树的原因。由于决策树是利用训练数据集创建的，其创建过程涉及训练数据集的大部分样本，在构造时，许多分支可能反映的是训练数据集中的噪声或孤立点，需要检测并剪去这种分支，以提高在未知类别数据（待预测数据）上分类的准确性。

对最终的决策树来说，在建立过程中生长太大的决策树将降低树的可理解性和可用性。决策树过于复杂，节点个数过多，则每个叶节点所包含的训练样本个数就越少（即支持每个叶节点假设的样本个数越少），这可能导致决策树在未知测试集上的分类错误率的增加，因此需要修剪决策树，以剪去包含样本过少的叶节点；另外生长过大的决策树也可能导致决策树本身对历史数据的依赖性增大，即出现过学习情况，为了使得到的决策树所蕴含的规则具有普遍意义，防止树的过大生长，需要提早停止树的增长，以防止过学习，同时减少训练的时间。

但需要注意的是，并不是节点越小错误率就越低，并不能使得决策树过小，因为决策树过小也会导致错误率上升。

因此要在树的大小与正确率之间寻找平衡，应在保证正确率的前提下尽量构造简单的决策树。

②决策树过大的原因。

a.表示不当。决策树的大小与描述语言有关，选择正确的描述语言可以大大减少决策树的复杂程度。

b.数据有噪声。数据的噪声包括属性噪声（不恰当的属性）和属性值噪声（数据的属性值有错误）。决策树无法区分正确的数据与错误的数据，既对正确的数据建模又对错误的数据建模，而正确数据本身的规律性被噪声所覆盖，导致决策树随噪声的存在而变大。

c.重复的子树。产生过大的决策树可能是因为有完全相同的子树。

③控制树的大小。常采用剪枝的方法控制树的大小，包括：预剪枝法、后剪枝法和组合式剪枝法。

a.预剪枝法：提前使节点成为叶节点停止树的构造，对树剪枝。

在树生成的过程中设定一定的准则来决定是否继续生长树，例如设定决策树的最大高度（层数）来限制树的生长，或设定每个节点必须包含的最少样本数，当节点中样本的个数小于某个数值时就停止分割；也可在构造树时，用如统计意义下的X2、信息增益等度量评估分割的优良性，如果在一个节点划分样本将导致低于预定阈值的分支，则停止进一步划分给定的子集。然而适当的阈值的选取是困难的，较高的阈值可能导致过分简化树，较低的阈值可能使得树的化简太少，需要根据专门应用领域的知识或经过多次测试评估得到。

b.后剪枝法：与设置停止增长条件相对应，是待决策树完全生成以后再进行剪枝。

先允许树尽量生长，然后通过删除节点的分支剪除树的节点，把树修剪到较小的尺寸。当然在修剪的同时要求尽量保持决策树的准确度不要下降太多。后剪枝方法所需的计算比预剪枝方法多，但通常产生更可靠的树。

c.组合式剪枝法：可以交叉使用预剪枝和后剪枝，形成组合方法。

具体的剪枝算法有：基于代价复杂度修剪（cost-complexity pruning， CCP）、悲观修剪（pessimstic pruning）和最小描述长度修剪（minimum description length pruning， MDL）等。

基于代价复杂度修剪方法是根据计算各个节点的期望错误率进行评估是否剪去子树（如果剪去该节点将导致较高的错误期望率，则保留该子树，否则剪去该子树）； MDL修剪方法是根据编码所需的二进位位数，评估是否对树进行修剪（最佳剪枝树是使得编码所需的二进位位数最少的）。后面将会详细介绍MDL修剪方法，其余的不做详细描述。

剪枝数据集的选择要考虑以下两个方面：

a.选择与构造决策树数据集不同的数据进行剪枝。基于代价复杂度修剪方法使用独立的样本集用于决策树的修剪，即与用于树的构造过程中使用的样本集不同。例如使用训练集2/3的数据生成树，另外1/3的数据用于剪枝。但是当训练数据集比较小时，容易导致过学习。

b.选择与生成决策树数据集相同的数据进行剪枝。悲观修剪将所有的训练样本都用于树的构建与修剪，虽然计算复杂性不高，但容易导致生成过大的树，并且有时精确度不高，而错误率较高。

（3）评估生成的决策树模型。决策树之所以重要，并非因为它归纳了已经知道的信息（训练集），而是因为它能把新的案例进行正确的分类，因此当构造分类模型时，应该既有训练数据构造模型，又有测试数据检验这个模型的工作准确性。

由于过学习问题产生的可能性，因此在由训练数据样本集导出决策树后，需要评估所得决策树对未来的数据（即未经决策树处理的数据）正确标号的准确率。 目前常用的评估方法有：

①保持方法：这种评估方法只有一部分初始数据用于导出的分类模型。该方法将给定数据随机地划分成两个独立的集合：训练集和测试集。通常，三分之二的数据分配到训练集，其余三分之一分配到测试集，使用训练集导出决策树模型，其准确率用测试集评估。

②交叉有效性方法：将训练数据集S分为互不相交且大小相等的k个子集S1，S2 ，… ， Sk，对于任意子集Si，用S—Si训练决策树，用Si对生成的决策树进行测试，得到错误率ei，然后估计整个算法的错误率e：

随着k的增加，所生成的树的数目也随之增加，算法的复杂度也会变大。

（4）使用模型分类。如果认为决策树的准确率是可以接受的，则用构造的决策树对类标号未知的数据样本进行分类。

（5）由决策树提取分类规则。决策树所表示的知识可以IF-THEN形式的分类规则表示。由决策树提取分类规则的过程是对从根到树叶的每条路径创建一个规则，沿着给定路径上的每个“属性-值”对形成规则前件（“IF”）部分的一个合取项，叶节点包含类预测，形成规则（“THEN”）部分。

例5.2（如图5-lb的决策树）：沿着由根节点到叶节点的路径，可转换IF-THEN分类规则，提取的规则如下：

IF age＜25 THEN Risk=“High”

IF age＞25 AND CarType in ｛ sports｝ THEN Risk=“High”

IF age＞25 AND CarType not in ｛ sports｝ THEN Risk=“low”

4）决策树归纳分类小结

决策树具有生成的规则易于理解、计算量相对不大、可处理连续和离散属性且明确显示哪些属性更为重要等多方面优点。但决策树也存在不足，主要表现在对连续性的属性比较难预测；对有时间顺序的数据，需要很多预处理的工作；当类别太多时，错误可能增加较快。

需要引起读者注意的是，在实际中应用的决策树可能非常复杂，例如，利用历史数据建立一个包含几百个属性、+几种输出类的决策树，这样的一棵树可能太复杂，但每一条从根结点到叶节点的路径所描述的含义仍然是可以理解的。决策树的这种易理解性对数据挖掘的使用者来说是一个显著的优点。然而决策树的这种明确性可能带来误导，如决策树每个节点对应分割的定义都是非常明确毫不含糊的，但在实际应用中这种明确可能带来麻烦，例如，可能出现这样的情况：年收入40001元的人具有较小的信用风险而40000元的人却不具有。这些特殊情况都需要使用者在实际应用中注意权衡。