（计算机科学与技术专业论文）决策树模型在银行风险预警系统中的应用.pdf

摘要 随着中国加入w t o ，我国金融银行业的竞争也日趋激烈，银行风 险预警系统作为银行风险系统的重要分支。在目前的银行风险系统 中，尤其是银行同业业务中，关于客户，下级机构以及同业新业务预 警的分类还停留在以人工手动完成的阶段，为了降低人为因素的影 响，更加科学准确的得到分类结果，本文在分析了决策树技术在银行 风险预警系统中应用的可行性之后，提出了一种以提高预警质量为根 本目标的应用决策树分类技术在银行风险预警系统的实施方案。 分类是数据挖掘的重要组成部分，它根据类标号己知的数据建立 模型，进而使用该模型来预测类标号未知的数据所属的类。常用的分 类方法有决策树分类、贝叶斯分类、神经网络分类等，其中决策树方 法在可理解度、易训练性、易实施性和通用性等方面优于其他的分类 方法。本文选择将决策树分类法应用到银行风险预警系统中。 根据所提出的实施方案，本文以同业客户分析为例，完整地实现 了决策树分类的全过程，包括：确定对象及目标；采集数据；采用数 据集成、数据清理、数据转换、数据消减等数据预处理技术；使用 i d 3 算法生成决策树，并利用事后修剪法对决策树进行修剪；然后由 决策树产生分类规则，完成决策树模型的建立；最后，利用构筑的决 策树模型成功应用到风险预警系统中，并取得了良好的效果。 关键词：风险预警系统；决策树；分类；i d 3 算法； a b s t r a c t w i t hc h i 蚰s e a m i n go ft h em e m b e r s h i po fm e 、呵0 ，t h e c o m p e t i t i o nw i t h i nb a l l l 【si si n c r e a s i n g l ys c v e r e l y t h eb a r l l ( e a r l y w 啪i n g s y s t e m i so n ei m p o r t a n tb 啪c ho ft h eb a l l ：kr i s k s y s t e m i n c u r r e n t s y s t e m ，t h ec l 舔s i f i c a t i o no fc u s t o m e r s ，s u b s i d i a r yb a n ka 1 1 dn e wb u s i n e s s s t i l ls 协婚i nt h ep l l m s eo fm 加u a lw o d d n g t or 。d u c em eb a di n f l u n c co f h u m a nf a c t o r s ，拙da c q u i r em o r ca c c l ，r a t ec l a s s f i c a t i o nr c s u l t s ，t h i s d i s s c r a t i o nw i l la 1 1 a l y z et h ef e a s i b i l 时o f 印p l y i n gd c c i s i o nn 优i nt h e b a f 出e a r l y w 锄i n gs y s t e m ，t h e ni t w i l lp m p o s ean e we ) 【。c u t i v ep l 她， w h i c ha i m sa ti n c r c 鹊i n gt h eq u a l i 哆o fe a d y w 锄i n g ，a n dt h i sp l a nw i l l 印p l y t h ei nt h eb 甜止e a r l y w 锄i n gs y s t e m c l a s s i f i c a t i o ni s 锄i m p o r t a n tp a r to f 纰m i n i n g ，w h i c he s t a _ b l i s h e sa m o d e lr e l y i n go nd a t ao fk n o 咖c l a s sa n dt h e nf o r s c e st l l ec l a s so ft 1 1 e u 1 1 ：k o w n c l a s sd a 妇w i t ht h em o d e l c o m m o nm e t h o ( 1 sf b rc l a s s i f i c a t i o n a r ed c c i s i o n 仃优、b a y e s i a n 、n e u r a ln e ta 1 1 ds oo n ；锄o n gt 1 1 e s em e t h o d s t h em e t h o do u t p e r f o r n 晦o m e rm e t h o d si i le 嬲yt ou n d e r s t a n d 、f a c i l i t yf o r t r a i n i n g 、i m p l 锄e n t a t i o na n du t i l i t y t h i s d i s s e r t a t i o nt l c l pm ec h o o s e d e c i s i o nt r c c 舔m yc l a s s i f i c a t i o nm e t h o d a c c o r d i n gt h ee x e c u t i v ep l a i l ，t h i sd i s s e r a t i o nw i l le 】【a m p l i 矽t or l i z c t h ew h o l ep r o c c s so fd e c i s i o n 仃i e ec o m p l e t e l y ，“c o n t a i n s ：c 1 1 s u r et h e o b j e c t ；g e tn e e d e dd a t a ；u s et h ed a t ap r e t r e a t n l e n tm e t h o ds u c h 舔d a t a d a t ai n t e g f a t i o n ，d a t ac l e 矾d a t at r a n s f o 衄a t i o n 锄ds oo n ；u i d 3a l g o r i t h t 0m a k et h ed e c i s i o nt r e ；g e tt h ec l a s s i f i c a t i o nm l ea c c o r d i n gt ot h e 协e e t oc o m p l e t et h ed e c i s i o n 仃e em o d e l ：f i n a l l y t h ed e c i s i o n 仃e cm o d e la r i s s u c c e s s 如l l y 印p l i e di n t ot h eb a n ke a r l y w a m i n gs y s t e m 锄dg a i n s 柚 u p s t a i l d i n ge f f e c t k e yw o r d s ：d e c i s i o nn e e ；c l a s s i f i c a t i o n ；i d 3a l g o d t h ； 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丝日期：本人签名： 二盔幺垒 日期： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本 学位论文不属于保密范围，适用本授权书。 本人签名：缝日期：2 q 坌2 ：丝堕 导师签名：烨 第一章绪论 尽管数据挖掘技术己经有了很大的发展，并且应用于社会生产的各个方面， 但由于目前各行各业的数据都存在数据爆炸的现象，应用数据挖掘的方法提供科 学的决策支持仍具有广阔的前景。本文针对银行风险预警系统同业业务部分研制 开发了适用于预警挖掘的决策树分类方法并将其应用于银行风险预警系统中，得 出了丰富的决策信息，用于指导快捷准确的预警。下面就论文的研究背景、研究 意义以及论文的整体结构作一介绍。 1 研究背景 1 1 决策树分类方法 决策树分类方法是一种以实例为基础的归纳学习方法，是数据挖掘众多分类 技术中的重要组成部分。它着眼于从一组无次序、无规则的实例中推出决策树表 示形式的分类规则。它采用自项向下的递归方式在决策树的内部结点进行属性的 比较，并根据不同属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。 所以从根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组 析取表达式规则。决策树分类法实现简单，层次结构清晰，能够产生易于理解和 分析的规则，因此是目前应用较为广泛的分类方法。该方法己被有效地应用于科 学实践、医疗诊断、气象预报、商业预测、案件侦破等领域，引起了工业界和学 术界的极大关注。 1 2 银行风险预警系统 银行风险预警系统是商业银行风险系统的重要组成部分。旨在利用银行现有 的业务数据，通过查询，分析。计算，统计等手段，根据已定的指标和预警规则， 对违规的业务和机构进行预警。以达到降低银行业务风险，从而提高银行核心竞 争力的目的。目前，随着中国进入w t o ，外资银行开始进军国内市场，银行业的 竞争愈演愈烈。如 可有效地降低运营风险，提高企业的核心竞争力业已成为各大 商业银行竟相追逐的目标。因而，银行风险预警系统在各大商业银行中得到了广 泛的关注和应用。 1 3 在风险预警中应用决策树模型的必要性 本文作者在某商业银行风险预警系统的实际开发过程中，主要遇到了以下三 个问题： 1 银行同业客户的授信额度配给工作不完善，主要是稽核员根据经验手动 完成的，缺乏科学性和准确性。 2 原数据中没有针对银行下级机构的授权额度配给，使很多预警工作无法 进行。 3 预警的结果不够及时，没有对于新业务预警等级的预测性划分。 通过分析研究，发现这些问题都是因为没能对同业客户，下级机构，以及新 同业业务的预警等级进行科学的预测性的分类造成的。 为了解决这些问题，我们引入了决策树分类方法，同银行风险预警系统相结 合，建立风险预警决策树模型，对银行同业客户，银行下级机构，以及每笔银行 同业业务预警等级进行分类。 这样，就可以根据得到的分类结果，对于不同的客户，下级机构科学的配给 不同的授信授权额度，对于新业务也可以及时准确的进行其预警等级的判定，上 面的问题也就迎刃而解了。 目前，应用数据挖掘技术以及决策树方法为商业银行提供决策支持的研究很 多。大部分集中在利用数据挖掘技术对商业银行的客户进行细分，以便于银行对 不同的客户采用不同的策略和服务，达到银行利益的最大化。本文利用决策树的 分类方法也对银行的客户进行了划分，主要以下有两点不同之处： ( 1 ) 目的不同。本文客户分类原则从银行风险预警系统的实际情况出发，以 给予不同的客户不同的授信为目标。主要目的是判断客户应配给的授信额度值。 ( 2 ) 客户含义不同。本文进行分类的客户均为商业银行同业业务客户，大部 分是金融业投资类企业，与一般的客户在客户属性上也有本质的区别。 另外，国内外也有利用决策树来进行风险预警的研究。这些研究主要是通过 建立预警指标体系进行的。所谓预警指标体系就根据国际惯例以及行内经验制定 出衡量客户以及银行内部情况的指标。再通过分析这些指标值，进行预警分类。 本文的预警分类则是针对每一笔同业业务进行的。即不是判断其指标值是否在预 警范围进行预警，而是分析每笔同业业务的业务信息来预测此笔业务的预警等 级。这种针对业务进行的预警方式是通过实际操作过程中该商业银行稽核部的稽 核专员提出的，具有一定的现实意义，也是本文的一种尝试。 2 2 本文结构 本文共五章，第一章描述问题的背景和国内外的研究现状；第二章介绍数据 挖掘的发展历程，以及国内外研究方向；第三章较为详细地论述了银行风险预警 系统中运用决策树建模的过程；第四章展示了决策树建模在风险预警系统中的应 用：第五章对本论文的工作做了总结和展望。 第二章综述 1决策树分类技术 1 1 决策树概述 决策树算法是一种以决策树这种数据结构为基础的分类算法【l8 。决策树 ( d e c i s i 骶c ) 又称判定树，是一个类似于流程图的树结构，其中每个内部结点表 示一个属性上的测试( 称测试属性或决策属性) ，每个分枝代表一个测试输出，而 每个树叶结点代表一个类或类分布。为了给未知的样本分类，由树根开始对该对 象的属性逐个测试其值，并且顺着分枝向下走，直至到达某个叶结点，此时结 点代表的类则为该对象所属的类。 图2 1 一颗决策树的例子 上图是一棵决策树，给出了某小学学生学习状况的例子。这个例子假定要按 学生学习成绩的好坏这个概念对一个集合进行分类，该集合中用来描述学生的属 性为性格、家庭背景和性别【1 9 1 。这棵决策树对“小学生成绩好坏”进行分类， 指出一个小学生的成绩是好还是坏。每个内部结点( 矩形框) 代表对某个属性的一 次测试，每片叶子( 椭圆框) 代表一个类( 学习成绩好为p ，差为加，输入新的对 象记录，可以预测该对象属于哪一个类。这棵决策树将整个实例空间分为三类， 当家庭背景为中，性格为外向并且是男生时，这个学生的学习成绩为好。 决策树包含许多不同的算法，主要分为3 类： ( 1 ) 基于统计论的方法，以c a r t 【2 0 】为代表，在这类算法中，对于非终端结点 来说，有两个分枝。 ( 2 ) 基于信息论的方法，以i d 3 算法 2 1 捌为代表，此类算法中，非终端结点的 分枝数由样本类别个数决定。 ( 3 ) 以a i d ，c h a i 2 o 刁为代表的算法，在此类算法中，非终端结点的分枝数 在两个样本类别个数范围内分布。 1 2 决策树算法的基本思想 决策树算法构造决策树来发现数据中蕴涵的分类规则，如何构造精度高、规 模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步， 决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集 是根据实际需要由历史的、有一定综合程度的、用于数据分析处理的数据集。第 二步，决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正 和修正的过程。主要是用新的样本数据集( 称为测试数据集) 中的数据校验决策树 生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。 1 2 。l 决策树的生成 决策树生成的过程中，输入为训练样本数据集，决策树为最终输出结果。决 策树的每一个决策结点对应元组进行分类的一个决策属性( 测试属性) ，分枝对应 着元组按该属性迸一步划分的取值特征，叶子代表类或类的分布。首先，根据用 户的实际需要选择类别标识属性和决策树的决策属性集，决策属性集是指在候选 属性( 除了类别标识属性之外的所有属性) 中选择的属性集，然后开始构造决策 树。决策树归纳的基本算法是贪心算法，是以自顶向下递归的各个击破的方式决 策树。算法的基本步骤如下： ( i ) 树以代表训练样本的单个结点开始。 ( 2 ) 如果样本都在同一个类，则该结点成为树叶，并用该类标记。 ( 3 ) 否则，算法选择最有分类能力的属性作为决策树的当前结点。 ( 4 ) 根据当前决策结点属性取值的不同，将训练样本数据集划分为若干子集。 每个取值形成一个分枝，有几个取值形成几个分枝。 ( 5 ) 针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本 上的决策树。一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑 4 它。 ( 6 ) 递归划分步骤仅当下列条件之一成立时停止： 给定结点的所有样本属于同一类。 没有剩余属性可以用来进一步划分样本。在这种情况下，使用多数表决， 将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时 也可以存放该结点样本的类别分布。 如果某一分枝t e s t 锄晡h u t f a + 没有样本，则以样本的多数类创建一个树叶。 1 2 2 决策属性的选择方法 构造决策树的关键是要选择一个好的划分标准，以决定按哪一个属性进行节 点的划分。一般用统计度量的方法来选择属性对结点进行划分，主要有： l 信息增益( i n f o 舢廿o ng a i n ) 分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。 1 9 4 8 年，香农( c e s h 锄o n ) 提出了信息论【2 3 1 ，定义熵( e n 缸d p y ) 作为衡量系统混 乱程度的统计量，熵越大，系统越混乱。由此可见，最佳的方案是使熵减少量最 大的划分方案，划分后嫡的减少就是信息增益。因此，选择属性对结点进行划分 的标准应该是选择信息增益最大的属性。算法i d 3 ，c 4 5 就是使用信息增益作为 选择属性对结点进行划分的指标。信息论中对信息量( h f o r m a t i o n ) 和熵( e n 的p y ) 的定义为【圳： h f 咖t i 口n - l o i 肌 b 口”叩y i en i o l “p ) 数据集划分前的熵： 设数据集s 有彳i ，一2 4 n ，共玎+ ，个属性。其中分类属性c 有m 个不同的离 散取值c l ，c 2 ，c 。即数据集s 中分成m 个类别。设数据集中全部样本数为s ， 分类属性值为旬，句，c 的样本数分别旬，兜，砘。那么划分之前，样本集s 的总 熵( 期望信息) 为： ，魄屯。气 ；a 蛔，办 ( 目 其中，p i 是s 集中任意一个样本属于类别c i 的概率，并用s 出估计。注意，对 数函数以2 为底，因为信息用二进制编码。容易看出，数据集s 的总熵在划分前 是属于不同类别的样本的信息量的加权平均。 数据集划分后的熵： 5 设属性a 有v 个不同的离散属性值，可使用属性彳将数据集s 划分为v 个子 集( 函，最，s 0 。设子集中的全部样本数为焉，其中分类属性值为c j ，q ，c m 的样本数为s l j ，岛，s 面，则子集与的熵为： ，( j i ，一。) 。 n i o | i 埘 其中j 口：! i = ：s ；匈。是焉中任一样本属于类别g 的概率。 使用属性a 把数据集s 划分成y 个子集后，s 的总熵为v 个子集的熵的加权 平均： 尉 ，杰当_ = ! 二；三马( ，j - ) = 至j “，) 月 h 岣l 华：为墨子集的权重，表示j ，子集在数据集s 中的比重。 信息增益 信息增益表示系统由于分类获得的信息量，由系统熵的减少量度，定义数据 集s 按属性么划分后的信息增益为s 划分前后的熵差： g 口i n ( a ) = l ( s 1 s 2 ，s 0 一e ( a ) 算法计算每个属性的信息增益。具有最高信息增益的属性选作给定数据集s 的决策属性，创建一个结点，并以该属性标记，对属性的每个值创建分枝，并据 此划分样本。 2 基尼指数( g i n d e x ) 如果决策树是二叉树，常用基尼指数作为选择决策属性的标准。数据样本集 s 的分类属性有辨个不同的离散值个类别，那么基尼指数就是 删毋a 1 艺一 其中竹是类别c 出现的概率。如果用属性彳将s 划分成两部分j b 却。即这 个划分的基尼指数就是： g t n i s ) = sh s ) g i n t ( s1 ) + ( s 2 s ) g i n i ( s 0 执行划分时，选择基尼指数最小的属性对结点数据样本进行划分。决策树是 二叉树时，设属性有v 个离散型取值，则属性彳可有种划分s 集的方法，其 中一个划分方法的基尼指数最小，称之为属性一的最佳划分。在选择结点最佳 划分时，首先找出每个属性的最佳划分方法，再比较所有属性的最佳划分方法， 最后确定结点的最佳划分。 6 1 2 3 数值型属性的离散化 在用决策树方法进行分类时，数值型属性要离散化。 设彳为数值型属性，那么彳的最大可能取值数为n ( 数据集s 的全部样本数) 。 要利用4 把数据集s 分为两组，对应的条件为爿 ，。关键的问题如何选 择分割阀值y 。通常做法是先对数据集s 按爿的属性值按升序排序，设排序后4 的属性序列为，从小到大依次取不同的分裂点，取信息增益最大( 基尼 指数最小) 的就是a 的最佳划分。若v j 为最佳分裂点，通常取v = m + v j + 2 。建树 时，在每个结点上都要对数值型属性捧序以便计算信息增益或基尼指数。 1 2 4 决策树的修剪 在决策树分类算法中，除了分类的正确性是要首先考虑的因素外，决策树的 简洁程度也是一个需要考虑的重要因素。因此要使用剪枝策略来简化决策树，并 提高所提取的规则的可靠性。主要的剪枝方法有预剪枝q 静p 邝n i n g ) 和后剪枝 s t 巾r u r i i i l g ) ，以及其他的后处理( p o s t 倒腻猕s i n g ) 方法。 l 预剪枝 在预剪枝算法中，并不把每个叶子结点均为同一类时作为算法停止的条件， 而是在建树的过程中终止树的建立以达到对树进行剪枝的目的。在这里，终止只 是将该结点变成叶子结点，该结点可能包含训练子集中经常出现的类或这些样本 的可能分布。 2 后前枝 后剪枝是在决策树建立之后，对形成的决策树的分枝进行清理的过程。后剪 枝算法有两种可能的剪枝策略，一种是自上而下的，一种是自下而上的。自下而 上的算法是首先在最底层的内部结点( 即所有子结点都是叶子结点的内结点) 开 始剪枝，剪去那些满足一定剪枝标准的内结点，生成新的决策树，之后在新的决 策树递归调用这个算法，直至没有新的结点满足剪枝的标准为止。自上而下的算 法则是从根结点开始向下逐个考虑每个结点是否应被剪枝。 预剪枝和后剪枝可以交叉使用，后剪枝算法比预剪枝算法需要更多的计算时 间，但可以产生更可靠的决策树。 3 增量树学习 在样本数据集较大时，为了解决内存空间的问题，利用增量树( i n c r 衄l “ 仃优) 学习的方法。即通过逐步增加训练实例增量式地构造剪枝决策树。在递归调 用剪枝算法的过程中，对剪枝来说大的实例集有好处。所以如果增加训练实例时 重新考虑剪枝有一定好处。 7 另一种增量式学习方法是动态剪枝( d y n 锄i c 肿g ) ，或者叫做虚剪枝 ( v i 巾皿ip n l l l i n 曲。在这种方法中，也是根据前面的方法以统计的方法建立决策树。 不同的是并不是整棵树的所有节点都进行分类，而是有一部分叶节点作为所谓虚 节点，不对虚节点的实例进行分类，只对实节点的实例进行分类。虚节点可以被 看成是已经被修剪的节点。叶节点在虚节点与实节点之间的转换是在决策树积累 实例的过程中动态地决定的，所以在建树过程中当一个叶节点剪枝时只是将它变 为虚节点而不是真的就剪掉，避免带来不可修复的变化。 可以看出，增量式学习在保持决策树学习的其他优点的同时，还可以使决策 树的大小较为理想。在对决策树进行剪枝后，锝到一组决策树，我们可以选用 一套独立的测试数据集去评估每一棵生成的决策树的精确度，出错率最低的决策 树是人们希望得到的最优决策树。在剪枝算法中，评估树的分枝好坏的有基于分 类错误估计、信息增益、代价复杂度，最小编码代价等，具体将在有关算法中 给予介绍。 1 3 几种典型的决策树算法 1 3 1m 3 算法 1 9 8 6 年q u i l 觚提出了d 3 算法阻】。假设用t 代表当前样本集，当前候选属 性集用ta 嘶b u t e i i s t 表示，候选属性集中所有属性皆为离散型，或数值属性事 先经过预处理转化成离散型。则i d 3 算法由描述如下： ( i ) 创建根节点n ； ( 2 ) t 都属于同一类c ，则返回n 为叶节点，标记为类c ； ( 3 ) t a t 岫b u c e l i s t 为空 则返回n 为叶节点，标记n 为t 中出现最多在类； ( 4 ) f o re a c ht a t 晡b u t e l i s t 中的属性 计算信息增益髓i n ： ( 5 ) n 的测试属性t c s t a t 缸b u t e - t a 州b u t c l i s t 具有晟高g a i l l 值的属性； ( 6 ) f o re a c ht e s t a t 啊b u t e l i s t 的取值f 由节点n 一个新的叶子节点 新叶子节点对应的样本子集t 为空 则不分裂此叶子节点，将其标记为t 中出现最多在类 e l s e 在该叶子节点上执行i d 3 f 0 彻n 吲t ，t a 晡b u t e i i s t ) ，继续对它分裂； i d 3 算法是基于信息嫡的决策树分类算法，根据属性集的取值选择实例的类 别。它采用自项向下不可返回的策略，搜出全部空间的一部分，它确保决策树建 立最简单，分类速度快，是国际上最早、影响力最大的决策树算法。但它也有其 不足之处：d 3 算法采用基于信息嫡的属性选择标准，因此偏向于选择属性取值 较多的属性，而属性取值较多的属性却不一定是最佳的分类属性，其次，d 3 算 法学习简单的逻辑表达能力较差。 1 3 2c 4 5 算法 1 9 9 6 年，q u i l 髓对i d3 算法进行了改进和补充，提出了后来非常流行的c 4 5 算法。c 4 5 算法在d 3 算法的基础上加进了对连续型属性、属性值空缺情况的 处理，对剪枝也有了较成熟的算法。假设用t 代表当前样本集，当前候选属性 集用t a t 晡b u c e l i s t 表示，则c 4 5 算法c 4 5f o 咖h e e nta t 啊b u t d i s t ) 的伪代码如 下： ( 1 ) 创建根节点n ； ( 2 ) i f t 都属于同一类c ，则返回n 为叶节点，标记为类c ； ( 3 ) t a t 晡b u t e l i s t 为空o rt 中所剩的样本数少于某给定值 则返回n 为叶节点，标记n 为t 中出现最多的类； ( 4 ) f o r 队c ht a t 啊b u t e l i s t 中的属性 计算信息增益率i i l f b i m a t i o ng a i l lm t i o ； ( 5 ) n 的测试属性t e s t a t 砸b u t e = t a t 砸b u t e i i s t 具有最高信息增益率的属性； ( 6 ) 测试属性为连续型 则找到该属性的分割阀值； ( 7 ) f o re a c h 由节点n 一个新的叶子节点 i f 该叶子节点对应的样本子集t 为空 则分裂此叶子节点生成新叶节点，将其标记为t 中出现最多的类 e l s e 在该叶子节点上执行“5 f 0 皿骶e ( t ，t a t 啊b u t e l i s t ) ，继续对它 分裂； ) ( 8 ) 计算每个节点的分类错误，进行树剪枝。 与i d 3 算法不同，c 4 5 采用信息增益率( i 1 1 f o 册a t i o ng a i l lm t i o ) 作为选择测试 属性的标准。信息增益率等于信息增益对分割信息量( s p l i t i n f o 肌a t i o n ) 的比值。 对样本集t ，假设a 是有s 个不同取值的离散属性，用a 分割样本集所得的信息 增益的算法d 3 相同，分割信息量由以下公式给出： 9 一一 斜x 慨( p 黜 假设a 是在连续区间取值的连续属性，则先将样本集t 按属性a 的取值从 小到大排序，一般用快速排序法。假定排好后属性的取值序列为v i ，v 2 ，v ，则 对i 【l ，m 1 】，有值= ( v i + v i + 1 ) ，2 ，和按值v 划分的两个样本子集： 吖= l h 墨y 巧= h h y ， 这样划分所得信息增益记为g a 吣。线性地扫描序列v l ，v 2 ，v m 找出n 使得 鐾a i l l ，最大，t 被划分为两个子集t i 。和t 2 0 在此划分上求出信息增益率为连续属 性a 的最终信息增益率。而序列v 2 ，v m 中找到的又不超过局部闭值v 的取值v ； 成为当前节点在a 上的分割闭值( 1 r e s h o l d ) 。按照上述方法求出当前候选属性集 中所有属性的信息增益率，比较它们找出信息增益率最高的属性，若为离散属性， 则按照该属性的不同取值分割当前样本集：若为连续属性，则依据它的分割闭值， 将当前样本集分为两个子样本集对每个子样本集用同样的方法分割直到不可分 割或达到停止条件为止。 为了处理某些样本在某些属性上取值空缺的情况，c 4 5 为每个样本设立一 个权值。一开始，所有样本的权值均为】o 。当从样本集t 选择了测试属性a 将 t 划分成s 个子集死乃，乃，对每个子样本集正，它包含的样本中a = a i 和 a 值空缺的样本。界中含空缺值的样本的权值正比于不中a 值空缺的样本数对t 中a 值不空缺的样本数的比值。 生成决策树后“5 算法计算每个节点的分类错误( c l a 孵i f i c a l i e 玳蝴进行剪 枝。对每个叶子节点，分类错误为该节点中不属于该节点所表示的样本的权值之 和：对于非叶子节点，分类错误为它的各个孩子节点的分类错误之和。如果计算 出某个节点n 的分类错误超过了节点n 所代表的样本集t 中的所有样本分配为 t 中出现最多的类别所得的分类错误，则将节点n 的所有子枝剪去，使n 成为 叶子节点，以t 中出现最多的类别标记它。 由于c 4 5 算法采用训练样本集来估计分类错误，因此会使得到的决策树融 进了训练集中的某些异常，而这些异常通常不在总体样本中出现，从而导致决策 树倾向于所谓过度拟合( o v 盯f i t ) ，这个缺陷可以通过选择一组独立于训练样本集 的测试集优化决策树来弥补“5 的另一个不足是在计算连续属性的信息增益 时，需要对所有取值线性扫描以找出局部闭值，这使它的效率受到了限制。为 了解决这个问题，2 0 0 2 年，s a l v a t o r er u g 西甜提出了后来称之为e c 4 5 【2 6 1 的改进 1 0 算法，通过采用二分查找代替线性扫描和采用计数排序法来确定局部闭值，并通 过维护一个称为a v c 的数组取代c 4 5 对连续属性排序的做法，提高了效率。 1 3 3c a r t 算法 c a r t 算法采用二分递归的分割技术，使得生成的树是结构简单的二叉树 【2 0 2 7 1 。设t 代表当前样本集，ta 州b u t e l i s t 代表候选属性集，则c a r t 算法 c a m 0 咖仃e t ) 描述如下： ( 1 ) 创建根节点n ； ( 2 ) 为n 分配类别： ( 3 ) mt 都属于同一类0 r t 中所剩样本为空 则返回n 为叶节点，为其分配类别； ( 4 ) f o re a c hta t t m u t c l i s t 中的属性 执行该属性一个划分，计算此划分的g i n l 系数； ( 5 ) n 的测试属性t e s ta t 仃j b u t e = - t a t 岫b u t e l i s t 具有最小g i n i 系数的属性； ( 6 ) 划分t 得t i ，t 2 两个子集： 则找到该属性的分割闭值： ( 7 ) 调用c a r t f o 瑚饥喊1 1 ) ； ( 8 ) 调用c a n f 0 衄虮；o f r 2 ) ； 与3 ，c 4 5 不同，c a r t 算法采用基于基尼系数选择最佳决策属性。对候选 属性集中的每一个属性，c a r t 算法计算该属性上每种可能划分的g i n i 系数， 找到g 烈i 系数最小的划分作为该属性上的最佳划分，然后比较所有候选属性上 最佳划分的g i 系数，拥有最小划分g i n i 系数的属性成为最终决策属性。 c a r t 算法对每个节点都分配类别，节点的类别可以是当前节点出现最多的 类别，或者参考当前节点的分类错误等考虑类别标记。 c a r t 算法采用后剪枝，剪技算法采用代价一复杂度算法。决策树复杂度与 分类精确度之间的关系如图2 2 所示嗍。图2 2 说明当决策树复杂度超过一定程 度后，随着复杂度的提高，测试集的分类精确度反而会降低。因此，建立的决策 树不宜太复杂，需进行剪枝该剪枝算法依赖于复杂性参数a ，a 随树复杂度的 增加而减小，当增加一个节点引起的分类精确度变化量小于树复杂度变化的q 倍时，则须剪去该节点。故建立一棵既能精确分类，又不过度适合的决策树的关 键是求解一个合适的a 值。 图2 2 决策树的复杂度与分类精确度之间的关系 对于样本数太少不能分出独立的测试样本集的情况，采用一种称为交叉确定 ( c r 0 姆v a l i d a t i o n ) 的剪枝方法，将训练样本集分成n 份，每份的数据分布近似相 等。n 份中取出其中1 份作为测试集，其余n 1 份作为训练集，每建立一棵树后， 再交换训练集和测试集，这样共进行n 次，得到n 棵局部决策树，综合n 棵局 部决策树形成全局决策树。这样形成的全局决策树在性能上非常接近由包含所有 样本的原始训练样本集得到的决策树。这个方法解决了在小样本集上挖掘决策树 没有独立的测试集造成的过度拟合问题。 1 3 4 s l i q 算法 i d 3 c 4 5 等算法对规模较小，可以全部放入主存的训练样本集很有效，但当 训练样本集太大无法全部放入主存时，这些算法的效率明显降低，不适宜处理大 规模数据。为此，m m 研究人员在1 9 9 6 年提出了s l i q 算法( s 删s c d 【脚m i n g i nq u e s t ) 1 2 8 】。实践证明，对于前面算法可以处理的小规模训练集，s l i q 的运行 速度更快，生成的决策树更小，分类精度更高；对于前面算法无法处理的大规模 训练集，s l l q 精度更高，优势更明显。 s u o 算法采用3 种数据结构来构造决策树，分别是属性表、类表和类直方 图( c l 娜h i s t o 鲫n ) 。属性表含有两个字段：属性值和样本号。类表也含有两个字 段：样本类别和样本所属叶节点。类表的第k 条记录对应于训练集中第k 个样本 ( 样本号为k ) ，所以属性表和类表之间可以建立关联。类表可以随时指示样本所 属的划分，所以必须长驻内存。每个属性有一张属性表，属性表可以驻留磁盘 类直方图附在叶节点上，用来描述节点的类别分布，它由一组二元组 组成；描述离散属性分布时，它由一组三元组 组成。随着算法的执行，类直方图不断更新。 1 2 八 1 - 类直方图实例说明：当扫描到属性表的第一行，测试条件为a 1 5 h 2 立方图 中，满足条件的样本记录在l 行，不满足条件的记录在r 行。h 2 ，h 3 为扫描到 属性表第一项时，当前各个叶节点的直方图，h 2 t ，h 3 为扫描到属性表第二项时 的当前各个叶节点的直方图。s l l o 算法在建树阶段对连续属性采用预排序技术， 并用广度优先策略生成决策树，对离散属性采用快速求子集算法确定划分条件。 具体算法描述如下： ( 1 ) 建立类表和各属性表，并且进行预排序，即对每个连续属性的属性表进行 单独捧序，以避免在每个节点都要给连续属性值重新排序； ( 2 ) 如果每个叶节点中的样本都能归为一类，则算法停止，否则转( 3 ) ； ( 3 ) 利用属性表寻找拥有最小g i n i 指数的划分作为最佳划分方案。算法一次 只处理一张属性表( 假设对应属性a ) ，从上到下每读一条记录，就根据样本号关 联到类表的相关记录，找到样本所在的叶节点，从而更新叶节点上的类直方图， 若a 是连续的，则还要根据a 的当前取值v 计算对应于判断a v 的g 小i 值。 若a 是离散的，则在扫描完a 属性表后，用贪心算法或穷举法计算最佳的s 。 当扫描结束时，就可确定在各叶节点上依据属性a 进行划分的最佳方案，各叶 节点上的划分方案不一定相同。同理，当扫描完所有属性表后，可确定当前树中 所有节点的最佳划分； ( 4 ) 根据( 3 ) 得到的最佳划分节点，判断为真的样本划归左孩子节点，否则划归 右孩子节点。这样( 3 ) ( 4 ) 步就构成了广度优先的建树策略。 ( 5 ) 更新类表中的第二项，使之指向样本划分后所在的节点； ( 6 ) 转( 2 ) 。 s u q 算法采用基于最小描述长度( m d l ) 的原则进行剪枝，即根据决策树的 编码代价的大小进行剪枝，以寻找最小的决策树。决策树编码代价的定义为： 决策树的编码代价= 树结构的编码代价+ 在内部节点上进行浏试的编码代价 + 训练集的编码代价。 由于使用了新的数据结构，s l i q 可并行化。在多处理器的并行环境下，假 设每个处理器都各自拥有独立的主存和辅存，s l i q 算法可将属性表平均分配给 曲 各个处理器，使决策树的生成实现并行。对于类表，可以让每个处理器有一份， 或将它分割后分给各处理器。 由于在算法执行过程中要随时修改类表，s l i q 算法的类表要常驻内存，而 类表会随着训练样本集的增大而增大，因此s l i q 算法仍然不能摆脱主存容量的 限制。 1 3 5s p r i n t 算法 为解决主存限制的问题，m m 研究人员又提出了可伸缩并行的决策树算法 s p r 酣t 1 2 9 1 ( s c a l a b l ep a r a l l e l i z a b l ei i l d l n i o no f d c c i s i o nt r ) 。s p r i n t 对s l i q 的 数据结构进行改迸，把原来的属性表和类表归并为一个属性表，属性表由属性值、 类别属性和样本号3 个字段组成，它随着节点的扩展而划分，并附属于相应的子 节点。直方图附属在节点上，用来插述某个属性的类别分布。当描述连续属性的 类分布时，节点上关联两个直方图c b c i o 。，和c 曲。，前者描述已处理样本的类别 分布，后者描述未处理样本的类别分布，两者的值皆随算法的进行而更新：当描 述离散属性的类分布时，节点只关联一个直方图0 0 岫tma _ 岍x ，记录不同取值的 样本在各个类别的的个数。 与s l i q 算法不同，s p r 盯采用深度优先的建树策略，具体步骤如下： ( 1 ) 生成根节点，并为所有属性建立属性表，同时预排序连续属性的属性表： ( 2 ) 如果每个叶节点中的样本都能归为一类，则算法停止，否则转( 3 ) ( 3 ) 利用属性表寻找拥有最小g i n i 指数的划分作为最佳划分方案。算法依次 扫描该节点上的每张属性表。由于计算g i n i 值需要该节点上直方图的信息，因 此每处理一张属性表前均要清空并初始化直方图。对于连续属性a 要求初始化 c b 由，为o 而c 曲0 v e 为该节点上的样本关于a 的总体分布。每扫描a 属性表的一 条记录( 设属性值为v ) ，都要更新一次c b d o ，和c i 姗。，且计算对应于划分a y 的g i n i 值。这样，一次扫描完a 属性表，就可得到该节点关于a 属性的最佳划 分，并记录下来。对于离散属性b ，先清空c o m t m a 仃i x ，在扫描b 属性表的同时 c o u n tm a 仃讧，扫描完后，根据构造好的c o u n tm a n 讧求解最佳划分中的s ，并把 它记录下来当扫描完该节点的所有属性表时，就可得到该节点的最佳划分。 ( 4 ) 根据划分方案，生成该节点的两个子节点n 1 ，n 2 。 ( 5 ) 划分该节点上的各属性表，使之关联到n l 或n 2 上。首先划分测试属性的 属性表：依次扫描记录 ，判别x 属于哪个孩子，然 后将该条记录移到该孩子节点的新属性表中，同时将i d 值写入h a s h 表，以保存 划分后样本所在孩子节点的信息。然后其余属性表：依次扫描，依据样本号查找 h a s h 表中该样本划分后所在的孩子节点，然后至该孩子节点的新属性表中。 1 4 ( 6 ) 分别转( 2 ) n 1 ，n 2 。 s p i m q t 算法采用基于m d l 的标准进行剪枝。通过以下方法，可将算法改 成可并行的：将训练集平均分布到n 个处理器上，而后每个处理器生成自己的数 据分片。由于连续属性值要求全局排序，因此要将n 个处理器上的连续属性的 属性表综合重排序，再平均分布到各个处理器上。在建立h a s h 表时，需要处理 器上收集所有样本号信息。 1 4决策树分类算法的比较 基于决策树的分类算法白提出以来，除了上面所述的几种比较典型的以外。 还有基于人机交互、p u b l i c 算法等等，各种算法各有所长。按出现的先后来看， 后面出现的算法总是希望解决之前的算法在执行速度、可伸缩性、输出结果的可 理解性、分类预测的准确性等方面所存在的不足。例如“5 系列算法与之前的 d 3 算法相比，具备了直接处理连续属性和属性有空缺值的样本；c a r t 采用基 尼指数来选择测试属性，使得生成的决策树是结构简单、易于理解的二叉树；为 了提高算法的可伸缩性和并行性，提出了s u q 和s p r 盯算法；基于人机交互 的决策树算法则是将人工智能和人为干预加进了决策树生成的过程，打破由计算