下载掌阅APP，畅读海量书库
立即打开
决策树算法利用特殊的决策树模型来进行辅助决策，是模式识别中进行分类的一种有效的算法。它利用树状分类把一个复杂的多类问题转换为若干个简单分类问题来解决。
决策树模型代表了样本属性值与样本类别之间的一种映射关系。它采用“分而治之”的方法将问题的搜索空间分为若干子集，其形式类似于流程图。其中，每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个决策节点存放一个类标号。决策树的最顶层节点是根节点。决策树也可解释为一种特殊形式的规则集，其特征是规则的层次组织关系。决策树可以由分析训练数据的算法创建，或者由领域专家创建。大多数决策树因创建过程不同而不同。
决策树算法是主要针对“以离散型作为属性类型进行分类”的算法。对于连续型变量，必须被离散化后才能进行学习和分类。
决策树算法具有以下优点：决策树的构造不需要任何领域知识或参数设置，因此适用于探究式知识的发现；可以处理高维数据；获取的知识树的表示形式是直观的，并且容易被人理解；决策树学习的归纳和分类步骤简单、快速；一般情况下决策树具有很高的准确率。但也存在以下缺点：决策树算法不易处理连续型数据；数据的属性域必须被划分为不同的类别才能处理，有时这样的划分比较困难；决策过程忽略了数据库属性之间的相关性；在处理较大数据库时算法的额外开销较大，降低了分类的准确性；数据复杂性提高，会导致分支数增加，管理的难度会越来越大。
决策树算法是一种单分类器的分类技术，也是机器学习中的一种经典算法。决策树的内部节点是属性或者属性的集合，而叶节点是学习划分的类别或结论，内部节点的属性称为测试属性或分裂属性。
决策树模型一般包含3类节点：根节点、决策节点、叶节点。决策树节点构成示意如图2.2所示。决策树从根节点即决策树的起始节点开始，所有的待分类数据都存储在其中，即根节点中包含所有样本的数据。决策节点中包含所有属性的集合，并在某种规则下对其属性进行划分，最终当每个节点中仅含有某一类样本的时候，分裂完成，形成叶节点。从根节点至叶节点所形成的路径表示相应的分类规则。
图2.2 决策树节点构成示意
决策树的建立是一个从上至下、分而治之的过程。决策树的构建过程主要分为两个阶段：构造和剪枝。在构造阶段，从根节点开始在每个决策节点上选择测试属性，然后在建立的决策树的分支上进行样本的划分，直到达到规定的终止条件为止。一般终止条件有两种：一种是当每个叶节点中只含有同一类型的样本时停止继续分裂；另一种是设置节点中的迭代次数达到某个定值，同时样本数量小于某个阈值时停止分裂，而上述过程对于未知测试集的分类能力并不能保证，尤其在噪声数据或者孤立点数据较多时，分类精度会大打折扣。所以决策树采用剪枝来弥补决策树构造过程中的缺陷。决策树剪枝过程示意如图2.3所示。剪枝的过程实际上就是去除过于细分的叶节点，即噪声点和孤立点，将其回退到其父节点或更高的节点，使其父节点或更高的节点变为叶节点。这样就可以大大降低决策树的复杂度，减小决策树出现过拟合的概率，并对未知的数据有着较好的分类效果。
图2.3 决策树剪枝过程示意
决策树的整个构建过程如图2.4所示。当通过一组训练样本数据集的学习产生决策树后，就可以对一组新的未知数据进行分类。使用决策树对数据进行分类的时候，采用自顶向下的递归，对决策树内部节点进行属性值的判断，根据不同的属性值决定走哪一条分支，在叶节点处就能得到新数据的类别或结论。
图2.4 决策树的整个构建过程
根据决策树内部节点的不同属性，决策树有以下几种分类。
（1）当决策树的每一个内部节点都只包含一个属性时，称为单变量决策树；当决策树存在包含多个属性的内部节点时，称为多变量决策树。
（2）根据测试属性的不同属性值的个数，每一个内部节点可能有两个或者多个分支。如果决策树的每一个内部节点只有两个分支则称为二叉决策树。
分类结果可能有两类，也可能有多类。二叉决策树的分类结果只能有两类，故也称为布尔决策树。
在决策树构造过程中，分支指标（Splitting Index，SI）是关键。不同的决策树算法采用不同的分支指标。算法ID3、C4.5使用的分支指标是信息增益（Information Gain），而算法CART、SLIQ和SPRINT使用gini指标。这些指标决定了决策树在哪个属性处发生分类。
由于训练集中的噪声产生的起伏使决策树产生不必要的分支，因此在对实测样本分类时可能会产生错误的结果，为了降低错误率，需要进行决策树剪枝。
大多数决策树算法面临下列问题。
① 选择分类属性。在构建决策树的过程中，选择哪个属性作为分类属性会影响算法性能。属性的选择不仅涉及检验训练集中的数据，而且需要参考领域专家的建议。
② 分类属性的次序。选择分类属性的次序也是很重要的。较好的分类次序可以减少算法计算量。
③ 分类的数量。与选择分类属性的次序相对应的是确定分类的数量。分类的数量根据属性的定义域来确定。
④ 决策树的结构。为了改进应用决策树进行分类的性能，总是希望得到具有最少层次的平衡树。
⑤ 当训练数据被正确分类时，决策树的构造过程就应停止。为了防止产生过大的决策树或产生过拟合，有时也希望提前停止构造过程。提前停止构造过程需综合考虑分类精度和性能等多个因素。
⑥ 训练数据。构造的决策树的结构取决于训练数据。如果训练集太小，则构造的决策树由于没有足够的特殊性，不能很好地应用于更加通用的数据；如果训练集太大，则构造的决策树可能产生过拟合。
⑦ 剪枝。决策树被构造后，还需要对决策树进行剪枝，以提高分类阶段决策树的性能。剪枝阶段可能会删除过多的分类属性或者删除一些叶节点，以获得更好的性能。
在设计构建决策树算法时，总是希望得到可以对数据集进行正确分类的最佳形状的决策树。决策树的归纳算法和训练数据共同决定决策树的形状。
决策树算法的时间和空间复杂度取决于训练数据的规模、属性数量以及最终构建的决策树的形状。在最坏的情况下，构建的决策树可能很深而不茂密。
ID3算法是各种决策树算法中最有影响力、使用最广泛的一种，其基本策略是选择具有最高信息增益的属性作为分类属性。
设样本数据集为
X
，类别数为
n
，并设属于第
i
类的样本数据个数是
C
i
，
X
中总的样本数为|
X
|，则一个样本属于第
i
类的概率
。此时决策树对划分
C
的不确定程度（即信息熵）为
若选择属性 a （设属性 a 有 m 个不同的取值）进行测试，其不确定程度（即条件熵）为
则属性 a 对于分类提供的信息量为
式中 I ( X , a )表示属性作为分类属性之后信息熵的下降程度，亦称为信息增益。我们应该选择使 I ( X , a )最大的属性作为分类属性，这样得到的决策树的确定性最大。
ID3算法的步骤如下。
（1）在整个样本数据集 X 中选出规律为 W 的随机子集 X 1 ， W 称为窗口规模，子集称为窗口。
（2）以 I ( X , a )= H ( X )- H ( X | a )的值最大，即 H ( X | a )的值最小为标准，选取每次的测试属性，形成当前窗口的决策树。
（3）按顺序扫描所有样本数据，找出当前的决策树的例外，如果没有例外，则结束算法。
（4）组合当前窗口的一些样本数据与某些在步骤（3）中找到的例外形成新的窗口，转到步骤（2）。
基本的ID3算法采用信息增益作为单一的属性的度量，试图减少树的平均深度，而忽略对叶节点数量的研究，这导致了许多问题：信息增益的计算依赖于属性取值较多的特征，但属性取值较多的属性不一定是最优属性；抗噪性差，训练集中正例（符合决策属性）和反例（不符合决策属性）较难控制。因此，针对ID3算法的不足，提出以下改进策略。
① 离散化。在处理连续型属性时，可以将其离散化。最简单的方法是将属性值分成两段。对任何一个属性，其所有的取值在一个数据集中是有限的。假设该属性取值为{
a
1
,
a
2
,…,
a
n
}，首先将其值按递增顺序排列，然后将每对相邻值的中点看作可能的分裂点，一共存在
n
−1个分段值（即均值，如
）。ID3算法采用计算信息量的方法计算最佳的分段值，然后进一步构建决策树。
② 空缺值处理。训练集中的数据可能会出现某一训练样本中某一属性值空缺的情况，此时必须进行空缺值处理。我们可以用属性值的最常见值、平均值、样本平均值等代替空缺值。
③ 属性选择度量。在决策树的构建过程中，有许多的属性选择度量，我们也可以通过改造属性得到新的属性选择度量来提高算法的性能。
④ 可伸缩性。ID3算法对于规模相对较小的训练集是有效的，但对于现实世界中数以百万计的训练集，其需要频繁地将训练数据在主存和高速缓存中换进换出，会使算法的性能降低。因此，我们可以将训练集分成几个子集（每个子集能够放入内存），然后由每个子集构造一棵决策树，最后，将每个子集得到的分类规则组合起来，得出输出的分类规则。
⑤ 碎片、重复和复制处理。碎片是指给定的分支中的样本数太少，从而失去统计意义。碎片的解决方法：一种是将分类属性分组，决策树节点可以测试一个属性值是否属于给定的集合；另一种是创建二叉决策树，在决策树的节点上进行属性的布尔测试，从而减少碎片。
当一个属性沿决策树的一个给定的分支重复测试时，将出现重复。复制是指复制决策树中已经存在的子树。重复和复制问题可以由给定的属性构造新的属性（即属性构造）来解决。
C4.5算法是ID3算法的改进，它在ID3基础上增加了对连续属性、属性值空缺情况的处理，对剪枝也有较为成熟的方法。
与ID3算法不同，C4.5算法选取具有最高信息增益率的属性作为测试属性。对样本集 X ，假设变量 a 有 k 个属性，属性取值为 a 1 , a 2 ,…, a k ，对应 a 取值 a i 出现的样本数为 n i ，若 n 是样本的总数，则应有 n 1 + n 2 +… n k = n 。C4.5算法利用属性的熵值来定义为了获取样本关于属性的信息所需要付出的代价，即
信息增益率定义为平均互信息与获取信息所付出代价的比值，即（2.4）
即信息增益率是单位代价所取得的信息量，是一种相对的信息量不确定性度量。以信息增益率作为测试属性的选择标准，是选择 E ( X , a )最大的属性 a 作为测试属性。
C4.5算法在如下几个方面有所改进。
（1）解决了一些样本的某些属性值可能为空的情况。一种解决方法是在构建决策树时，将这些缺失值用常见值代替，或者用该属性所有取值的平均值代替，从而处理缺少属性值的训练样本。另一种解决方法是采用概率的方法，为属性的每一个取值赋予一个概率，在划分样本集时，将未知属性值的样本按照属性值的概率分配到子节点中，这些概率的获取依赖于已知的属性值的分布。
（2）不仅可以处理离散属性，还可以处理连续属性。其基本思想是对属性的取值进行排序，两个属性取值之间的中点作为可能分裂点，将数值集分成两部分，从而将ID3算法的处理扩充到数值属性上。
（3）增加了剪枝方法。在C4.5算法中，有以下两种基本的剪枝方法。
① 子树替代法，即用叶节点替代子树，且仅当替代后的误差率与原始树的误差率接近时才替代。子树替代是从“树枝”向“树根”方向进行的。
② 子树上升法，即用一棵子树中最常用的子树来代替这棵子树，子树从当前位置上升到树中较高的节点处。这种替代也需要根据误差率的增加量确定。
（4）分类时ID3算法会“偏袒”具有较多值的属性，因而可能导致过拟合。而C4.5算法的信息增益率函数可以弥补这个缺陷。
（5）使用 k 次迭代交叉验证，评估模型的优劣程度。交叉验证是一种模型评估方法，它将学习样本产生的决策树模型应用于独立的测试样本，从而对学习的结果进行验证。首先将所有的训练样本随机平均分成 n 份，每次使用其中的一份作为测试样本，使用其余的 n −1份作为学习样本，然后选择平均分类精度最高的决策树作为最后结果。上述的学习-验证过程重复 k 次，就称为 k 次迭代交叉验证。通常平均分类精度最高的决策树并不是节点最多的树。
但是C4.5算法同样存在缺点，它偏向于选择属性值比较集中的属性（即熵值最小的属性），而并不一定是对分类贡献最大、最重要的属性。
在ID3与C4.5算法中，当确定作为某层决策树节点的变量属性值较多时，按每一属性值引出一个分支进行递归，就会引出较多的分支，对应算法次数也增多，决策树算法速度缓慢。解决这个问题的方法是建立二叉决策树，即使每个树节点只产生两个分支（二叉）。CART算法就是这样一种算法。CART算法确定决策树节点（即测试属性）的方法与ID3算法一样，以平均互信息作为分类属性的度量，对于取定的测试属性 a ，若它有 n 个属性值 s 1 , s 2 ,…, s n ，应选取“最佳”分类属性值 s i 作为分裂点引出两个分支，以使分类结果尽可能合理、正确。
“最佳”分类属性值应满足条件
其中
Φ ( s / a )主要度量在属性 a 的属性值引出两个分支时，两分支出现的可能性以及两分支每个分类结果出现的可能性差异大小。当 Φ ( s / a )较大时，表示两分支分类结果出现的可能性差异大，即分类不均匀。特别地，当一分支完全含有同一类别结果的样本而另一分支不含有时，差异最大，这种情况越早出现表示利用越小的节点，可以越快获得分类结果。下标L和R分别指决策树中当前节点的左子树和右子树。 P L 和 P R 分别指训练集（样本集）中的样本在左子树和右子树的概率，其计算公式如下
P ( C i | a L )与 P ( C i | a R )分别指在左子树和右子树中的样本属于 C i 的概率，其计算公式为
CART算法的一大优点是它将模型的验证和最优通用树的发现嵌在了算法中，最优通用树即各边的代价之和最小。它先生成一棵非常复杂的决策树，再根据交叉验证和测试集验证的结果对决策树进行剪枝，从而得到最优通用树。
对于决策树，可以用以下性能指标进行评价。
评价决策树最首要、最基本的指标就是分类准确率。只有保证较高的分类准确率，才能评价决策树的其他性能。
在决策树的学习过程中，可能会得到若干与训练实例集相匹配的决策树，必须在它们当中选择应用于实测样本时出错率最低的决策树。如果有过多的决策树与训练实例集相匹配，那么模型的泛化能力（预测准确度）很差，这种情况称为过学习。
估计决策树在测试实例集上的性能一般是通过比较它在测试实例集上实际测试结果来完成的。这种方法等价于在测试实例集上训练决策树，这在大多数情况下都是不现实的。所以一般不采用这种方法，而是采取用训练实例集本身来估计训练算法的有效性。一种最简便的方法是用训练实例集的一部分（例如2/3的训练实例）对决策树进行训练，而用另外一部分（1/3的训练实例）检测决策树的有效性。但是这样将减少训练实例的数量而增大过学习的可能性，特别是当训练实例的数量较少时更会如此。所以一般利用交叉有效性和余一有效性来评价决策树的有效性。
（1）交叉有效性。在度量交叉有效性时，将训练实例集
T
分为互不相交并且大小相等的
k
个子集
T
1
,
T
2
,…,
T
k
，对于任意子集
T
i
，用
T
−
T
i
训练决策树，之后用
T
i
对生成的决策树进行测试，得到错误率
e
i
，然后估计整个算法的平均错误率
。因为随着
k
的增加，生成的树的数量会增加，算法的复杂度也会变大，所以应选择合适的
k
值。
（2）余一有效性。这种有效性的度量方法与交叉有效性类似，不同之处在于将每一个
T
i
的大小定为1。假设|
T
|=
n
，则整个算法的错误率
。很明显这种有效性度量算法的复杂度很高，但是它的准确度也是很高的。
决策树的复杂度也是度量决策树学习效果的一个很重要的指标，一般有以下3种评价指标。
（1）最优覆盖问题（MCV），即生成叶节点数量最少的决策树。
（2）最简公式问题（MCOMP），即生成每个叶节点深度最小的决策树。
（3）最优学习问题（OPL），即生成叶节点数量最少并且每个叶节点深度最小的决策树。
其中，叶节点深度是指叶节点距离根节点的层数。
在创建决策树时，由于数据中噪声和离群点的影响，许多分支反映的是训练数据中的异常。对于这种代表异常的分支可以通过剪枝的方法去除。
一般来说，如果决策树构造过于复杂，那么决策树是难以理解的，对应决策树的知识规则会出现冗余，将导致其难以应用；另外，决策树越小，存储决策树所需要的代价也越小。因此建立有效的决策树，不仅需要考虑分类的正确性，而且需要考虑决策树的复杂度，即建立的决策树在保证具有一定的分类准确率的条件下，越小越好。
常用的决策树简化方法就是剪枝。剪枝时要遵循奥卡姆剃刀原则，即“如无必要，勿增实体”，也就是在与观察相容的情况下，应当选择最简单的模型或方法。决策树越小就越容易理解，其存储与传输的代价就越小；决策树越复杂，节点越多，每个节点包含的训练样本越少，则支持每个节点的假设的样本个数就越小，可能导致决策树在测试集上的分类错误率增大；但决策树过小也会导致错误率增大。因此需要在决策树的大小与准确率之间寻找平衡点。剪枝方法主要包括预剪枝和后剪枝。
预剪枝就是预先指定某一相关阈值，决策树模型有关参数在达到该阈值后停止决策树的生长。预剪枝方法不必生成整棵决策树模型，且算法相对简单，效率很高，适合解决大规模问题，但预先指定的阈值不易确定。较高的阈值可能导致过分简化决策树，而较低的阈值可能使决策树的简化太少。一般地，以样本集应达到的分类准确率作为阈值进行预剪枝控制，此时决策树的复杂度随阈值变化而变化。更普遍的方法是采用统计意义下的 χ 2 检验、信息增益等度量，评估每次节点分类对系统性能的增益。如果节点分类的增益小于预先给定的阈值，则不对该节点进行扩展。如果在最好的情况下的扩展增益都小于阈值，即使有些节点的样本不属于同一类，算法也可以终止。
决策树后剪枝方法，就是针对未经剪枝的决策树，应用算法将决策树的某一棵或几棵子树删除，得到简化的决策树，并对得到的简化决策树进行评价，找出最好的剪枝策略以确定最终的决策树。其中，剪枝过程删除的子树可用叶节点代替，这个叶节点所属的类用这棵子树中大多数训练样本所属的类来代替。
后剪枝方法有自上而下的和自下而上两种剪枝策略。自下而上的策略从底层的节点开始剪枝，剪去满足一定条件的节点，在生成的新决策树上递归调用这个策略，直到没有可以剪枝的节点为止。自上而下的策略从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就进行剪枝。
一般的后剪枝方法的步骤如下。
设 T 0 为原始决策树， T i +1 是由 T i 中一棵或多棵子树被叶节点所代替得到的剪枝树。
① 第 i 次剪枝评价：若第 i 次的原始决策树是 T i ， T i 1 , T i 2 ,…, T ik 是分别对应 T i 的各种可能的剪枝决策树，可用以下评价标准选出一种最好的剪枝策略 a ik ，即
式中， M 是剪枝决策树分类错误率增加值， N 是样本总数， L ( S )是剪枝决策树被去掉的叶节点数。
② 对各次得到的剪枝决策树 T i 1 , T i 2 ,…, T ik ，用相同的样本测试其分类的错误率，错误率最小的为最优的剪枝决策树。
预剪枝和后剪枝可以交叉使用。后剪枝所需的计算要比预剪枝多，但通常可产生更可靠的决策树。