（计算机软件与理论专业论文）决策树算法在银行风险监控中的应用研究.pdf

摘要 近年来，银行业不断曝出内部人员偷蛀银行资金的丑闻。由于银行的业务流 程趋于自动化，系统趋于复杂化，对信息技术的依赖性更强，国内银行的风险监 控也变得更为复杂。如何随时监控风险的发生，如何将风险控制在一定范围内， 我们迫切需要探寻一种快速、简捷、实用的风险监控方法。 本文首先讨论了数据挖掘相关技术，分析了国内外数据挖掘在金融领域的应 用状况。在此基础上，结合企业调研以及相关数据，对银行风险监控业务进行详 细的分析，着重研究了数据挖掘中的决策树分类算法，将其应用到银行风险监控 模型的建立过程中，并建立了银行风险监控系统。系统通过风险提示、预警、监 测等手段，对银行一旦有风险的苗头出现，即可进行防堵，把风险消灭在萌芽状 态，以避免或减弱对银行的破坏程度。从技术角度，系统使用了j 2 e e ( j s f - t - s p r i n g + h i b e r n a t e ) 框架技术，并利用构件技术构建出可扩展的应用解决方案，具有 易于实施、松散耦合、高度可扩展等技术特点。最后通过实验结果表明该系统有 良好的分类效果，能较好地满足实际需求。 关键宇：风险监控；决策树；分类 a b s t r a c t t h e s ey e a r s ，t h es c a n d a lo fs t e a l i n gt h ef u n dt h ew i t h i nt h eb a n k i n gh a p p e n e d c o n t i n u o u s l y f o rt h er e a s o no ft h ea u t o m a t i o no ft h eb a n k i n gb u s i n e s sa n dt h e c o m p l i c a t eo ft h es y s t e m ，t h es y s t e mi sm o r ed e p e n d e n tt oi tt e c h n i q u e ；t h er i s k m o n i t o ri sm o r ec o m p l i c a t e h o wt om o n i t o rt h er i s ki nt i m e ，h o wt oc o n t r o lt h er i s k i nc e r t a i ns c a l e ，w en e e dt ol o o kf o ras w i f t ，e f f e c t i v em e t h o dt oa p p r o a c ht h er i s k m o n i t o r t h i sd i s s e r t a t i o nf i r s t l yd i s c u s s e st h ed e f i n i t i o no ft h ec l a s s i f i c a t i o no fd a t a m i n i n g ，a n a l y s i st h ea p p l i c a t i o no f d a t am i n i n gi nf i n a n c i a la r e ai na n da b r o a d o nt h e b a s eo fa b o v e ，u s i n gr e l a t e dd a t a , a n a l y s i st h er i s km o n i t o rb u s i n e s so fb a n k i n g ， m a k e sas t u d yo fd e c i s i o nt r e ea l g o r i t h mo fd a t am i n i n ga n da p p l i e st h ed e c i s i o nt r e e a l g o r i t h mt ot h em o d e lb u i l d i n gp r o c e s so fb a n k i n gr i s km o n i t o r s e c o n d l y , t h e d i s s e r t a t i o ns e t su pb a n k i n gr i s km o n i t o rs y s t e m t h es y s t e mw i l lc a n c e lt h er i s ki n t h ei n i t i a ls t a g eb ym e a n so fr i s kp r o m o t i o n ，e a r l yw a r n i n ga n dm o n i t o r , s oa st o w e a k e nt h ee x t e n to fd e s t r u c t i o nt ob a n k t h es y s t e mu s e st h ef r a m e w o r ko fj 2 e e ( j s f + s p r i n g + h i b e m a t e ) ，s e t su pae x t e n d a b l ea p p l i c a t i o np l a n 谢t hc o m p o n e n t t e c h n i q u e ，t h es y s t e mi se a s yt oe s t a b l i s h ，h i g he x t e n d a b l e ，l o o s ec o u p l i n g f i n a l l y , t h e e x p e r i m e n tr e s u l td e c l a r e st h a tt h es y s t e mp e r f o r m sw e l l ，a n dm e e t st h er e q u i r e m e n t t oag r e a te x t e n t k e yw o r d s ：r i s km o n i t o r ；d e c i s i o nt r e e ；c l a s s i f i c a t i o n 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：渗毖 沙，7 年厂月z 7 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： ( ) 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 ( v ) 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人：劳多亏 矽夕歹年厂月z t h 第一章绪论 1 1 课题的研究背景 第一章绪论 法国兴业银行成立于1 8 6 4 年，距今已有1 4 4 年历史。该行是法国第二大银 行，在欧元区排名第四的金融集团，也是欧洲盈利最丰厚的银行之一。这样的具 有悠久历史的老牌银行，却在2 0 0 8 年1 月2 3 日宣布，由于交易人员违规操作致 使该行4 9 亿欧元损失。从该行的巨额损失中，人们似乎再次目睹了1 9 9 5 年2 月，具有2 3 0 年历史的英国老牌银行巴林银行倒闭的一幕。两家银行有如此 相似的地方，例如都是由于操作人员的违规运作，都是从事股指期货买卖，都是 越权在短期内( 1 - 2 年) 进行衍生品的交易，同时造成规模巨大的经济损失。所不 同的是巴林银行破产，而法国兴业却采取快速融资5 5 亿欧元补充资本金的方式 i l l 。法国兴业的事件给我国金融业敲响了警钟，体现了风险监控必要性及重要性。 随着金融市场不断扩大，商业银行问竞争不断加剧，银行为了吸引客户增加 客户数，经常主动或者被动地减低监控门槛，从而给某些人以可乘之机。伴随而 来是金融业中的欺诈现象日趋严重，例如恶意拖欠贷款、伪造信用卡、信用卡被 盗刷、伪造客户信用度等欺诈手段应有尽有【2 1 。目前，由于金融监管层对银行业 的风险监控存在缺失，给银行带来了极大的损失，严重影响了银行业务的进一步 发展。 普尔斯马特、格林柯尔系、泰跃系等企业授信风险的集中暴露，不仅给银行 带来巨额的信贷资金损失，对银行声誉也造成了消极影响。虽然银行已采取重大 风险事件报告、案件专项治理、现场检查等积极措施并取得一定成效，但针对授 信业务流程的实时监测、风险提示、快速处理、持续反馈机制仍未建立，对授信 业务风险隐患的“早发现、早控制、早改进”能力亟待加强【3 】。2 0 0 6 年1 1 月1 日，银行高层“加强风险和案件控制 专题会议明确要求：“风险监控平台部、 风险管理部、信贷审批部、营运管理部要做好对授信流程的实时监控，加强对信 贷管理和审批环节的实时风险控制，实现对异常贷款的快速调查和处理的机制”。 现阶段，银行面临的风险越来越多，银行应该采取什么样的措施来防范这些风险 呢? 就目前业界人士认为，风险监控的手段有两条：一是政策调控，采用行政手 决策树算法在银行风险监控中的应用研究 段，依靠法律和行业互助来控制风险；二是利用技术手段，防患于未然。两者相 比，利用技术手段是目前银行最佳的风险监控利器【3 11 4 1 。 由于银行业务量巨大，形式多样，那些有风险的数据往往比较隐蔽，难以发 现。其中一个比较好的思路就是从分析海量历史数据入手，建立规则库，从中发 现风险，从而提前采取措施，进行风险监控，减少风险带来的损失。从技术角度 来讲，目前比较有效的风险监控的方法就是利用数据挖掘的分类技术进行银行风 险监控。数据挖掘技术是目前国际上数据库和信息决策领域的最前沿方向之一， 是应用一系列技术从大型数据库或数据仓库中提取人们感兴趣的信息和知识，这 些知识或信息是隐含的，事先未知而潜在有用的，提取的知识表示为概念、规则、 规律、模式等形式1 2 1 【5 11 6 1 。也可以说，数据挖掘是一类深层次的数据分析。数据 挖掘在一些领域内已有成功的应用，如零售业、银行、医疗等行业，但数据挖掘 技术在金融业中成熟的应用尚不多见。分类是数据挖掘的主要技术之一，目前在 商业上有较多应用，其方法是构造一个分类函数或分类模型( 也称作分类器) ， 通过分类函数，把数据库中的元组映射到给定类别中的某一个，即要发现一些指 定的商品或事件是否属于某一特定数据子集的规则f 4 1 7 1 。决策树分类算法可以用 于大型数据库，具有较高准确率和较快的速度。而且，目前决策树算法在一些实 际应用中取得了成功，比如在保险业中的应用【8 l 、金融预测模型1 9 1 等。 综上所述，数据挖掘分类技术的决策树算法能很好的应用于银行风险监控 中，本文将提出一个基于决策树分类的风险监控模型。 1 2 国内外研究动态 数据挖掘技术应用到金融领域，可以用来对金融市场进行分析、建模和预测， 并进行风险评估和客户关系管理，为金融企业运营提供决策支持【l 们。数据挖掘 在整个金融领域的应用已经比较成熟。目前，有许多关于数据挖掘技术在金融领 域应用的文献，为数据挖掘在金融领域的应用奠定了理论基础。 w i l s o n 和s h a r d a 】通过基于神经网络系统以高达9 7 的准确率对公司的破 产进行有效的预测，并有效的论证了在预测公司破产时使用基于神经网络的系统 进行分析比判别分析方法更具有优势。b a r r 和m a n i t l 2 】通过使用数据挖掘中的神 经网络和归纳规则法建立的模型预测s & p5 0 0 指数。他们使用具有2 1 个变量的 2 第一章绪论 时间序列作为输入变量，在基于神经网络的模型上进行实验，以达到9 2 的正确 率预测出变化的指数。m y o u n g j o n gk i m 和i n g o oh a n l l 3 l 在2 0 0 3 年比较分析了在 破产预测中运用遗传算法所带来的优势。g h j o h n ，e m i l l e r 和r k e 舭r 【1 4 】阐述了 通过使用归纳规则法方法在基于风险和回报率条件下来评估股票，并让用户去建 立基于自己的风险承受度之上的股票组合的思想。n a n c h e nh s i e h ，b e c k e r 等 都在金融领域如何使用数据挖掘技术提出了自己的看法【1 5 一2 4 1 。 国外的许多公司也都推出了自己的数据挖掘系统，其中很多都采用了决策树 方法，而在m i c r o s o f t 、s g i 、s a s 2 5 1 【2 6 】在已推出的数据采掘系统中，首选的方法 就是决策树方法。s a s 公司的s a se n t e r p r i s em i n e r 2 6 1 ，是一种通用的数据挖掘 工具，通过收集分析各种统计资料和客户购买模式，帮助用户发现业务的趋势， 解释己知事实，预测未来结果，并识别完成任务所需关键因素，最终实现增加收 入并降低成本的目的。i b m 公司的i n t e l l i g e n tm i n e r ，具有典型数据集自动生成、 关联发现、序列规律发现、概念性分类和可视化显示等功能，可以自动实现数据 选择、数据转换、数据发掘和结果显示，必要时重复这一过程。s o l u t i o n 公司的 c l e m e n t i n e 2 7 1 提供了一个可视化的快速建模环境，由数据获取、挖掘、整理、建 模和报告等部分组成。r i g h t p o i n t 公司的d a t ac r u n c h e r 是一种客户朋艮务器方式 的数据挖掘引擎，具有分析数据仓库中海量数据的能力，能与当今的许多主流关 系数据库和数据挖掘辅助工具直接进行连接，辅助建立面向营销的数据挖掘研究 的模型。还有a n g o s s 公司的k n o w l e d g es e e k e r ，t h i n k i n gm a c h i n e 公司的 d a r w i n ，s i l i c o ng r a p h i c 公司的m i n es e t 等1 2 8 】。 与国外相比，国内的数据挖掘研究稍晚，还没形成规模。1 9 9 3 年国家自然 科学基金首次支持对该领域的研究项目，1 9 9 9 年，第三届p a k d d ( p a c i f i c a s i a c o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 会议在北京召开更是加快了 国内在该领域的研究步伐。目前有部分学者把数据挖掘技术应用到金融领域，如： 杨淑娥，黄礼通过基于b p 的神经网络对上市公司的财务危机进行预测【2 9 】；刘曼， 罗慧分析了数据挖掘技术在上市公司财务危机预警体系中的运用1 3 0 1 等。在实践 应用方面，中科院计算技术研究所智能信息处理重点实验室开发出了m s m i n e r ， 它一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种 3 决策树算法在银行风险监控中的应用研究 知识发现方法。但是，国内的研究大部分还处于起步阶段，有待进一步的探索与 实践。 1 3 本文研究的主要内容 本文采用理论联系实践的研究方法，结合企业调研以及相关数据的分析，对 银行风险监控进行详细的分析，着重研究了数据挖掘中的决策树分类算法，并将 决策树分类算法应用到银行风险监控模型的建立过程中。 首先，本文阐述了课题的背景及其研究意义，分析了国内外数据挖掘在金融 领域的应用状况，对银行风险监控业务进行粗略描述。 其次，对数据挖掘决策树经典算法i d 3 做深入研究，根据此算法的缺陷提出 一种改进方法，根据对同一结果集的验证得出改进后的决策树算法有更高的准确 率及更好的分类效率。 第三，用改进的决策树算法取得风险监控规则，并用实例说明决策树方法在 银行风险监控应用中的处理过程。 最后，根据银行业务的实际需求，结合当今先进的i t 技术，实现基于决策 树算法的银行风险监控系统，并用测试数据进行验证。实践证明此系统可对银行 业务进行风险监控，可以有效地支持管理层进行决策。 4 第二章决策树分类技术 2 1 概述 第二章决策树分类技术 分类即根据数据的不同特征将其划分为不同的类别5 】 6 1 3 1 1 。在数据挖掘中， 对银行业务做出预测被看作是一个分类问题，即确定业务为正常业务还是具有风 险的业务。具体做法是将分类方法用于预先选定的包含银行业务类标示属性的训 练样本集中，从而挖掘归纳出规则集( 即建立分类模型) ，然后利用所获取的规 则对未知类别属性的用户进行预测分类，判定这些未知类别属性的银行业务是正 常业务还是具有风险的业务。对于判定为具有风险趋向的业务，银行部门可以采 取一些必要措施，从而达到风险监控的目的。 构造分类模型过程中，可以使用很多不同的方法，如决策树、贝叶斯分类法、 神经网络分类法等【5 】 3 2 】。尽管存在如此多的分类方法，但不同的问题需要不同的 方法去解决。即使对于同一个问题，可能有许多分类算法适用，而分类的效果又 和数据的特点有关：有些数据中有噪声数据，有缺值，分布稀疏，有些属性是离 散的，而有些属性是连续的。目前普遍认为不存在某种方法能适合于所有特点的 数据。通过对分类算法的比较研究发现，决策树算法是一种简洁而又高效的方法。 与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代 来训练模型，除了训练数据中的信息外，不再需要其他额外信息，并且表现了很 好的分类精确度。同时以其规则易于提取和容易理解的优点得到了广泛应用。目 前决策树算法在一些实际应用中也取得了成功，比如在保险业中的应用 s l 、金融 预测模型 9 1 等。 2 2 分类 2 2 1 分类的含义 数据挖掘中的分类方法是将数据集按某个指定的属性划分，并给出分类规 则。分类的目的是构造一个分类函数或分类模型( 也称作分类器) ，通过分类函 数，把数据库中的元组映射到给定类别中的某一个，即要发现一些指定的商品或 5 决策树算法在银行风险监控中的应用研究 事件是否属于某一特定数据子集的规则。分类问题可以用数据库术语表示如下： 对于一个给定的数据集，该数据样本集具有i n + 1 个属性( 字段) 4 ，彳：，4 。， c 。将此数据样本集按c 的属性值分类，形成一个分类模型。再用该模型对新的 数据集进行分类预测，既在己知新数据集马，b ：，b 。的值的情况下预测出 属性c 的值p 3 1 。分类模型可以用下面的数学表达式来定义： f ( a l ，a 2 ，a 。) 一c ( 2 1 ) 2 2 2 分类的过程 分类的过程主要分为分类模型的建立及分类模型的应用两个步骤。 l 、创建分类模型 如图2 1 所示，这是一个机器学习过程，用分类算法和一个类别己经确定的 数据集创建分类模型。用于创建模型的数据集叫训练集。训练集用其分类属性的 属性值表示类别，训练集中每一条记录都属于一个确定的类别。分类模型中的预 测模式可以用分类规则、决策树、或者数学方程的形式来表达。 受呈 n a m er a n ky e a r st e n u r e d m i k ea s s i s t a n tp r o f3n o m a r y a s s i s t a n tp r o f7y e s b i l lp r o f e s s o r2 y r e s j i ma s s o c i a t ep r o f7y e s d a v ea s s i s t a n tp r o f6n o a n n e a s s o c i a t ep r o f3 n 0 图2 1 创建分类模型 2 、使用模型预测 如图2 2 所示，使用分类模型前必须用一定的方法估计分类模型的准确率。 这可使用创建的模型对一个类别己知的数据集测试集进行预测，并将预测结 6 甲 第一二章决策树分类技术 果和实际值进行比较。测试集和训练集必须是相互独立的。再用达到一定准确率 的分类模型预测类别未知的数据集。 o 圈吣 l 测试集 i l lj 、 n a m f er a n ky e a r st e n l i r e d t b ma s s i s t a n tp r o f2n 0 m e l i s aa s s o c i a t ep r o f 7n 0 g e o r g e p r o f e s s o r5y e s j o s e p h a s s i s t a n tp r o f7y e s 图2 2 使用模型预测 d 一? 分类在机器学习中被称之为有监督的学习，这是因为训练集的类别是确定 的，而类别未知的数据集是基于训练集进行分类的。近年来，国内外的研究人员 在分类知识发现领域进行了大量的研究工作和实际应用的推广，分类技术已被广 泛、有效地应用于科学实验、医疗诊断、气象预报、信贷审核、商业预测、案件 侦破等领域，引起了企业界和学术界的广泛关注。 2 2 3 分类的评估 2 2 3 1 分类的评估标准 在数据挖掘中，选择合适的算法、建立有效的挖掘模型是非常关键的。对于 大型数据库来说，这种选择很困难，因为不可能试验每一种算法，也不可能对每 一个建立的模型进行验证。同时，对于模型进行评估的过程中，会存在很多种评 价标准，用不同的评价标准对算法进行评估，结果差距很大，而且不同数据集的 特性也会直接影响算法的运行性能。因此算法选择及模型评估必须在了解数据 集、模型及算法的相关知识以后，结合决策人员的实际需求再进行。目前国际上 流行根据下列标准对分类方法进行比较和评估1 5 j ： 预测准确率：由算法生成的分类模型对新数据的预测能力。 决策树算法在银行风险监控中的应用研究 速度：创建分类模型的速度和使用分类模型的速度。 健壮性：处理噪音和空缺值的能力。 伸缩性：对大量磁盘驻留数据的处理能力。 可解释性：用户对算法产生的分类模式可理解程度。对于描述型的分类任务， 模型描述越简洁越受欢迎。例如，采用规则表示的分类模式就更有用，而神经网 络方法产生的结果就难以理解。 2 2 3 2 分类的评估方法 分类模型的准确性是分类成功的关键。运用分类算法建立分类模型后，可用 下面几种方法评估分类模型的准确性【6 】。 l 、保持法( h o l d o u tm e t h o d ) 运用保持法时，将数据集随机地划分成两个独立的数据集：训练集和测试集。 用训练集建立模型，再用测试集评估模型。通常，取三分之二的数据用于训练集， 其余的用于测试集( 图2 3 ) 。保持法的评估是保守的，因为只有数据集的一部分 用于建立模型。为保证评估的准确性，可将保持法重复k 次，数据集每次随机地 划分成不同的训练集和测试集。总体准确率取k 次评估准确率的平均值。这种方 法被称为重复保持法。重复保持法遇到的最大问题是不同测试集间有重叠的数 据。 图2 3 保持法 2 、k 一折交叉确认法( k f o l dc r o s s v a l i d a t i o nm e t h o d ) 交叉确认法能避免出现重叠问题，k - 折交叉确认法，将初始数据分成大小相 等的k 个部分，而且这k 个部分互不相交，例如将数据s 分成k 个部分 s ，s 2 ， 瓯 。使用这种方法，训练和测试都要进行k 次。在第i 次迭代，墨作为测试集， 8 第二章决策树分类技术 其余的子集都用于训练决策树，然后用测试集验证训练出来的决策树的正确率， 如图2 4 所示。进行k 次后，再将k 次的正确率求出平均值，得出最终的平均正 确率。通常取k = l o 。 图2 4k 一折交叉确认法 3 、留一法( l e a v eo n e o u tm e t h o d ) 留一法是k 一折交叉确认法的变形。若数据集有n 条记录，将数据集划分为n 个子集。进行1 1 次迭代，每次留一条记录用作测试，其余n 1 条记录用作训练集。 留一法适合于较小的数据集，否则计算量太大。 4 、引导法( b o o t s t r a pm e t h o d ) 从数据集的1 1 条记录中均匀地、有放回地取样形成训练集。由于取样是有放 回的，任意一条记录在1 1 次选样后未被选入训练集的几率是( 1 1 n ) n l e = o 3 6 8 ， 因此被选入训练集的几率是0 6 3 2 。建立模型后，用训练集测试模型的误差。这 种误差称之为重新替代误差，误差数值记为e t r a i n 。再用测试集测试模型的误差， 误差数值记为e t e s t 。模型的总体误差估计为： e s t i m a t e d e r r o r = 0 6 3 2 书e 肭+ 0 3 6 8 木p 矧 ( 2 2 ) 对同一个模型引导法可以重复多次，重复k 次总体误差为： 量 e s t i m a t e d p 舢，= 1 ( o 6 3 2 乞肭+ o 3 6 8 色枷) ( 2 3 ) 9 决策树算法在银行风险监控中的应用研究 2 3 分类算法概述 分类一直都是机器学习、模式识别和数理统计的研究对象。因此有多种分类 方法，常见的分类方法有：决策树归纳方法、贝叶斯方法、神经网络方法、k - 最临近分类法、基于事例的推理方法、遗传方法、粗糙集方法、模糊集方法。每 种方法可由几种代表性的算法实现。对不同的数据类型和应用领域，每种方法都 有其长处和短处。但许多实验比较表明，没有一种分类算法对所有的数据类型和 应用领域都优于其他分类算法。 2 3 1 决策树 决策树方法自2 0 世纪6 0 年代以来，在分类、预测、规则提取等领域有着广 泛应用。决策树算法是数据挖掘领域研究分类问题最常采用的方法，其原因有三： 一是决策树构造的分类器易于理解；二是采用决策树分类，其速度快于其它分类 方法；三是采用决策树的分类方法得到的分类准确性优于其它方法。利用决策树 分类通常分为两步生成树和剪枝。树的生成采用自上而下的递归分治法，而 剪枝则是剪去那些可能增大树的错误预测率的分枝。生成最优决策树的问题是 n p 难的。决策树方法中最为著名的算法是q u i n l a n 提出的i d 3 算法【3 4 1 ，该算法 以信息熵的增益进行属性选择，增益率能克服增益偏向于多值属性的特点。c a r t 算法则采用基于最小距离的g i n ii n d e x 标准和为了克服g i n i 在处理多类问题上的 困难而进行的改进【3 5 l 。i d 3 及后续版本c 4 5 【3 6 】、c 5 o 是使用广泛的决策树算法， 还有许多其它选择属性的方法，如c s e p 、m d l 3 7 j 等。决策树分类的其它算法还 有f a c t 、q u e s t 、c h a i d 等【3 8 4 2 】。 2 3 2 贝叶斯方法 贝叶斯分类是基于贝叶斯原理进行的分类，该算法可以预测类成员的可能 性，例如某个给定样本属于一个特定类的概率。常用的贝叶斯分类方法有朴素贝 叶斯分类和贝叶斯网络两种。朴素贝叶斯分类假定一个属性值对给定的影响独立 于其他属性的值。这一假定称作类条件独立。做此假定是为了简化所需计算，并 在此意义下称为“朴素的 。这种假设降低了计算的复杂度，且具有较高的精确 度【4 3 】m 。贝叶斯网络是一个带有注释的有向无环图，以有效表示大变量集的联 1 0 第二章决策树分类技术 合概率分布。适用于分析大量变量之间的相互关系，利用贝叶斯公式的学习和推 理能力，实现预测、分类等数据挖掘任务。事实上，贝叶斯网络也是一种适合表 示不确定性知识的方法。贝叶斯网络的构造涉及网络结构和网络参数两部分的学 习。但是获得最优结构和参数都是n p 难的，因此出现了许多启发式的方法。 贝叶斯分类具有如下特点： ( 1 ) 贝叶斯分类并不把一个对象绝对地指派给某一类，而是通过计算得出属于 某一类的概率，具有最大概率的类便是该对象所属的类； ( 2 ) 一般情况下在贝叶斯分类中所有的属性都潜在地起作用，即并不是一个或 几个属性决定分类，而是所有的属性都参与分类； ( 3 ) 贝叶斯分类对象的属性可以是离散的，也可以连续的。 2 3 3 神经网络 神经网络的研究己经取得了许多方面的进展和成果，提出了大量的网络模 型，发现了许多学习算法，人工神经网络在模式分类、机器视觉、机器听觉、智 能计算、机器人控制、信号处理、组合优化求解、医学诊断、数据挖掘等领域具 有很好的应用。 神经网络可分为四种类型，即前向型、反馈型、随机型和自组织型。前向神 经网络是数据挖掘中广为应用的一类网络，其原理和算法也是其它一些网络的基 础。神经网络具有对噪声数据的承受能力，尤其是它对未经训练的数据的分类能 力。实验表明，神经网络在某些分类问题上具有比符号方法更好的表现，但是神 经网络没有很好地用于数据挖掘的原因在于无法获得显式的规则。近来已经出现 了一些由训练过的神经网络提取规则的一些算法，如k b a n n 等。 近年来，神经网络用于数据挖掘一分类的研究逐渐增多，l a m 和l e e 讨论了 利用人工神经网络构造文本分类器及维数削减的方法【4 5 1 ，g u p t a 等人分析了现有 神经网络算法用于分类等问题的现状，认为尽管神经网络在预测精度、鲁棒性、 无需数据分布的假设等方面具有优势，但是在决定合适的网络结构、训练参数、 结果解释及训练时间长等方面仍有许多困难，从而提出了一种规则抽取框架，以 解决神经网络提取的规则缺乏可解释性的问题。h a t a n o 等人提出了一种应用于 超文本数据的分类视图机制，通过自组织映射( s o m ) 和搜索引擎交互式的进行 决策树算法在银行风险监控中的应用研究 w e b 文档的分类 4 6 1 。目前，神经网络作为一种自适应、自学习的算法模型在数 据挖掘中已经有一些成功的应用。 2 3 4 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是v a p n i k 根据统计学理论提出的 一种新的非常有潜力的分类技术。支持向量机实现是通过某种事先选择的非线性 映射( 核函数) 将输入向量映射到一个高维特征空间，在这个空间中构造最优分 类超平面。鉴于支持向量机扎实的理论基础，并且和传统的学习算法想比较( 比 如人工神经网络) ，s v m 通过提高数据的维度把非线性分类问题转换成线性分类 问题，较好解决了传统算法中训练集误差最小而测试集误差仍较大的问题，算法 的效率和精度都比较高。所以近年来该方法成为构造数据挖掘分类器的一项新型 技术，在分类和回归模型中得到了很好的应用。由于s v m 可以选择和保存有用 的训练数据即支持矢量，取自大型数据库中的小样本的训练数据可使计算的复杂 度降低。所以，s v m 方法可用于数据预处理、样本化等知识发现的过程，也可 用于其它的数据挖掘应用。研究表明：对同一数据库，使用不同核函数训练的 s v m ，在测试数据上均具有较高的预测准确率。 2 3 5 其他方法 除了上述方法外，分类还可以使用基于案例的推理( c a r ) 、遗传算法、粗糙 集和模糊集方法。一般地，商品化的数据挖掘软件中很少使用这些方法。因为基 于案例的推理、粗糙集方法和遗传算法尚处于成长阶段，还有许多值得研究的问 题。 基于案例的推理( c b r ) 是基于要求的方法，其存放的样本或案例是复杂的符 号描述。给定一个待分类的新案例时，基于案例的推理首先检查是否存在一个同 样的训练案例。如果有，则返回附在该案例上的解。如果没有，则基于案例推理 将搜索具有类似于新案例成分的训练案例，即视为新案例的邻近者。基于案例的 推理的研究方向是寻找一种好的相似性度量，探索训练案例索引的有效技术和组 合解的方法。 1 2 第二章决策树分类技术 遗传算法和进化计算是基于生物学优胜劣汰、自然进化机理的研究领域，适 合于并行优化问题和数据分类，将免疫机制与遗传算法和进化计算集成用于数据 挖掘问题是一个新的挑战。 粗糙集方法也可以用于分类问题，尤其适合于发现不准确数据或噪声数据内 在的结构和联系。它主要用于离散值属性的数据，一般地，对于连续型属性应在 处理前离散化。模糊逻辑也是进行数据挖掘的理论和工具之一，模糊逻辑主要用 于处理不精确的知识，进行不精确的推理。 2 4 决策树分类算法 2 4 1 决策树算法简介 决策树算法是一种归纳分类算法。在过去十几年里，决策树算法在机器学习 和数据挖掘领域一直受到广泛的重视【4 7 1 。决策树算法可设计成具有良好可伸缩 性的算法，能很好地与超大型数据库结合，并能处理相关的多种数据类型( 连续、 离散、布尔) 。决策树算法的另一个优点是其结果容易被人理解，其分类模式容 易转化成分类规则。决策树算法着眼于从一组无次序、无规则的实例中推理出决 策树表示形式的分类规则。它是一种逼近离散值函数的方法，对噪声数据有很好 的健壮性且能够学习析取表达式，这种方法将从一组训练数据中学习到的函数表 示为一棵决策树。它采用自顶向下的递归方式，在决策树的内部节点进行属性值 的比较，并根据不同的属性值判断从该节点向下的分枝，在决策树的叶结点得到 结论。所以从根到叶结点的一条路径就对应这一条合取规则，整棵决策树就对应 着一组析取表达式规则。 2 4 1 1 决策树的结构 决策树通过把实例从根节点排列到某个叶结点来分类实例，叶节点即为实例 所属的分类。树上的每一个节点指定了对实例的某个属性的测试，并且该节点的 每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节 点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向 下移动，最后这个过程在以新节点为根的子树上重复【4 8 1 。如图2 5 所示，每个非 1 3 决策树算法在银行风险监控中的应用研究 叶节点代表数据集的输入属性，每一个后继分支代表属性的对应值，叶节点代表 该属性所属的分类。 图2 5 决策树的结构 2 4 1 2 决策树算法的原理 决策树算法是以信息论原理为基础的。信息论是c e s h a n n o n 为解决信息传 递( 通信) 过程问题建立的一系列理论，也称为通信理论。一个传递信息的系统 是由发送端( 信源) 和接受端( 信宿) 以及连接两者的通道( 信道) 三部分组成。 熵是信息论中的定义：任何系统存在一个状态函数，可把它定义为熵( e n t r o p y ) ， 用符号s 表示【2 引。熵是一个物理名词，数值为用气温除热量所得的商，它标志 着热量转化为功的程度，泛指某些物质系统状态的一种量度。根据玻尔兹曼熵公 式 4 9 1 ，熵是无序性、不确定性的量度。而在信息论中，信息是最重要的元素， 是有序性、确定性的量度，即它是具有新内容的消息，能够消除某一时间的不确 定性。因此，信息是熵的对立面，信息量称为负熵，信息熵的概念相应地被提出。 信息熵在信息论中称为平均信息量，是对被传送的信息进行度量所采用的一种平 均值。信源中被传送的信息包括有限数目的互斥并联合完备的事件，它们都以一 定的概率出现，用数学式子来表示就是：一组事件墨，x ，以既定概率 p ( 五) ，p ( x ，) 出现，其平均值h ( x ) 就是信息熵，它的值等于每个事件的自信息 量，( x ) 的数学期望，即： ， 日( x ) = 一尸( 置) ，( 置) = p ( x t ) l o g p ( x ，) ( 2 4 ) f 篁lj 暑l 在信息论中，c e s h a n n o n 提出了一系列的概念： 1 4 第_ 二章决策树分类技术 1 、自信息量：设x 。，x ：，x 。为信源发出的信号，在收到x 。之前，收信 者对信源发出信号的不确定性定义为信息符号的自信息量j ( 置) ，即 l ( x ，) = 一l 0 9 2p ( x ，) ，其中p ( x ，) 是信源发出鼍的概率。 2 、信息熵( e n t r o p y ) ：自信息量只能反映符号的不确定性，而信息熵可以用 来度量整个信源x 整体的不确定性，定义如下： 打 e n t r o p y ( x ) = 一p ( x j ) l 0 9 2p c x , ) ( 2 5 ) 其中n 为信源x 所有可能的符号数，即用信源每发一个符号所提供的平均 自信息量来定义信息熵( 平均信息量) 。 3 、条件熵：如果信源x 与随机变量y 不是互相独立的，收信者收到信息y ， 那么用信息熵e n t r o p y ( xi 聊来度量收信者在接受到随机变量y 之后，对随机变 量x 仍然存在的不确定性。设置对应信源符号x ，z 对应信源符号y ，p ( 五iz ) 为当y 为z 时x 为x ，的概率，则有： e n t r o p y ( xid = 一尸( ziy ，) l 0 9 2 尸( 置iz ) ( 2 6 ) 4 、平均互信息量：用它来表示信号y 所能提供的关于x 的信息量的大小， 可用下式表示： i ( x ，即= e n t r o p y ( x ) 一e n t o p y ( xi 即 ( 2 7 ) 信息熵刻画了任意样本集的纯度。例如：某个信息源总是发送同样的信息， 那么接收者就不需要更多的信息，此时信息源的熵就为0 ，也就是没有任何不确 定性。相反，如果某个信息发送了n 个不同的信息并且每个信息是相互独立的， 此时熵的值就是l o g ：n 。 信息熵用在决策树中是作为训练集纯度的标准，在决策树形成过程中，最重 要的部分是对分裂属性的选择【5 1 。比较常用的一种方法是计算信息增益 ( i n f o r m a t i o ng a i n ) 。信息增益的原理来自信息论，它是使某个属性用来分类训练 集而导致的期望熵降低。因此，信息增益越大的属性分类数据集的可能性越大。 1 5 决策树算法在银行风险监控中的应用研究 决策树的形成就是递归地对数据集中的每个节点进行分类，直到节点的所有类别 都属于同一类或没有多余的属性来划分训练样本集。 2 4 1 3 决策树算法的工作过程 使用决策树算法解决分类问题有两个步骤，它的工作过程可以用图2 6 描述。 1 创建分类模型 2 使用模型测试 图2 6 决策树算法解决分类问题的两个步骤 第一步是利用训练集建立一棵决策树，建立决策树模型。 第二步是利用生成完毕的决策树对输入数据进行分类。对输入的纪录，从根 节点依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所在的类。 2 4 1 4 决策树的生成过程 决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比 较，并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。 所以从根到叶结点的一条路径就对应一条规则，整个决策树就对应着一组规则。 决策树生成算法如下： 第二章决策树分类技术 由算法可知，分割方法c l 是决策树的关键。根据算法不同，目前决策树算 法可分为两类：基于信息论的方法和最小g i n i 指标方法，对应前者的算法有 i d 3 3 4 1 ，c 4 5 1 3 6 1 ，后者有c a r t 、s l i o 、s p r i n t 、p u b l i c 等。 2 4 1 5 决策树的评价指标 决策树算法中，决策树的复杂度和分类精度是需要考虑的重要内容，决策树 的评价指标一般有如下几个方面g l 、预测准确性 该指标描述分类模型准确预测新的或未知类别数据的能力。预测准确性是决 策人员最关心的问题，对于他们来说，之所以采用分类发现模型的原因在于分类 发现模型可以在巨量数据中按照用户的使用要求处理数据，对数据进行分类，从 中找寻有用信息。经分类发现的模型处理后，从原始数据中得到的信息的准确性 在很大程度上将会影响决策人员制定的决策的准确性。 2 、描述的简洁性 这是针对分类发现模型对问题的描述方式以及该描述方式的可理解水平提 出的。分类发现模型的最终目的是方便决策人员的使用，所以，对于决策人员来 说，模型描述越简洁，也就越易于理解，同时也就越受欢迎。例如：采用规则表 示的分类器构造法所提供的分类模型的描述方式就比较简洁、易于理解而采用神 经网络等方法产生的描述结果相对来说就难以理解，从而使其更进一步的广泛应 用受到了一定的限制。 3 、计算复杂性 1 7 决策树算法在银行风险监控中的应用研究 计算复杂性依赖于具体的实现细节，在数据挖掘中，由于某种操作对象是海 量的数据库，因此空间和时间的复杂性问题将是非常重要的一个环节，将直接影 响生成与使用模型的计算成本。 4 、模型鲁棒性 鲁棒性是对模型预测准确性的一个补充，是在存在噪声及数据缺损的情况 下，准确对未知类别的数据进行分类的能力。正如前面所提到的，数据挖掘处理 的对象是大量的数据，而这些数据又常常存在不完整的情况，数据缺损、噪声数 据以及冗余数据等情况是普遍存在的，在这种情况下，就要求所建立的模型对这 些情况有充分的适应能力。 5 、处理规模 处理规模是指在巨量数据的情况下构造模型的能力以及构造分类模型的精 确度。数据挖掘所处理的对象数量是巨大的，那么就要求所构建的挖掘模型可以 适用于各种不同规模的数据量情况。 2 4 2 几种常见的决策树算法 2 4 2 1c l $ 算法 c l s ( 概念学习系统) 5 0 l 【5 l 】算法是1 9 6 6 年由h u n t 、m a r t i n