（计算机应用技术专业论文）决策树分类算法及其应用.pdf

摘要 摘要 随着企业信息化建设，数据仓库和决策支持系统技术在企业中得到了空前的应用。 如何将决策支持系统中的数据挖掘方法应用到企业中成为了研究的重点。 论文主要是围绕数据挖掘分类算法中的决策树算法的关键技术展开研究的。 本文首先对决策树分类算法做了一个综述。对典型的决策树分类算法的主要特性， 优缺点，适用范围，目前的改进状况，决策树算法的应用和展望进行了简要的概述。 随着数据处理技术的飞速发展，需要处理的数据规模越来越大，已经从最初的小型 数据库发展到现在大型数据库，数据仓库等。这时有效性、正确性和空间性就成为了数 据挖掘中主要考虑的特性。在对典型决策树分类算法的研究后，将抽样技术引入到决策 树算法c 4 5 中，使得这种对小数据集有效的算法也能在给定大数据集的情况下挖掘出 有一定正确性的分类规则。选择u c i 机器学习库的标准数据库为数据源，使用改进的基 于抽样的决策树c 4 5 算法进行分类规则的挖掘。试验表明该方法能在获得满意的正确 性的情况下显著的提高数据挖掘的效率。 紧接着结合一个钢铁企业的应用背景，将改进的算法应用在了两个大的方面：钢铁 企业生产成本关键工序分析和钢铁企业亏损品种分析。第一个应用以工艺路线为切入 点，结合钢铁企业的成本分析项目，对生产成本关键工序进行数据仓库建模。采用改进 的基于抽样技术的决策树c 4 5 算法对海量数据进行挖掘，挖掘出工艺路线中的关键工 序，影响钢铁企业成本的分类规则。第二个应用结合钢铁企业的销售亏损品种分析项目， 对亏损品种分析进行数据仓库建模，挖掘出钢铁企业亏损品种分析的关键影响因素。两 个应用为钢铁企业的成本管理提供了科学依据，同时为数据挖掘系统的建立提供了很好 的经验。 关键词：决策树算法；抽样；钢铁企业；成本分析；数据仓库建模 大连交通大学t 学硕十学位论文 a b s t r a c t w i t ht h ec o n s t r u c t i o no fe n t e r p r i s ei n f o i r m a t i o n ，d a t aw a r e h o u s ea n dd e c i s i o ns u p p o r t s y s t e mt e c h n o l o g yi nt h ee n t e r p r i s eh a su n d e r g o n ea nu n p r e c e d e n t e da p p l i c a t i o n h o ww i l l t h ed e c i s i o ns u p p o r ts y s t e ma p p l i c a t i o no fd a t am i m n gm e t h o d st oe n t e r p r i s e sb e c o m et h e f o c u so ft h es t u d y ? t h em a i nt h e s i si so nt h ek e yt e c h n o l o g i e so ft h ed e c i s i o nt r e ea l g o r i t h mo ft h e c l a s s i f i c a t i o na l g o r i t h mo fd a t am i n i n g t h i sa r t i c l ef i r s td o e sar e v i e wo nd e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h m t h eb r i e f s u m m a r yi sa b o u tt h em a i nc h a r a c t e r i s t i c ，a d v a n t a g e sa n dd i s a d v a n t a g e s ，s c o p eo fa p p l i c a t i o n ， p r e s e n ti m p r o v e m e n ts t a t e ，a p p l i c a t i o na n de x p e c t i n go ft y p i c a lc a t e g o r i z e da l g o r i t h m so f d e c i s i o nt r e e a l o n gw i t ht h ed a t ap r o c e s s i n gt e c h n o l o g y sr a p i dd e v e l o p m e n t ，t h ed a t as c a l ew h i c h n e e d st ob ep r o c e s s e dh a sb e e nm u c hb i g g e rt h a nb e f o r e ，i ta l r e a d yh a sd e v e l o p e df r o mt h e i n i t i a ls m a l ld a t a b a s et ot h ep r e s e n tl a r g e - s c a l ed a t a b a s ea n dt h ed a t aw a r e h o u s e t h e n v a l i d i t y ，a c c u r a c ya n ds p a c eo ft h ed a t am i n i n gb e c a m eam a j o rc o n s i d e r a t i o ni nt h e c h a r a c t e r i s t i c s a f t e rt h ef o r m e rf a c eo ft h et y p i c a ld e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h m r e s e a r c h ，t h es a m p l i n gt e c h n o l o g yw i l lb ei n t r o d u c e di n t ot h ed e c i s i o n t r e ea l g o r i t h mc 4 5 ， m a k i n gs m a l ld a t as e t se f f e c t i v ea l g o r i t h mc a na l s og i v e nac e r t a i nc o r r e c tr u l e sf o rt h el a r g e d a t as e t s c h o o s es t a n d a r dd a t a b a s eo fu c im a c h i n el e a r n i n gl i b r a r ya sd a t as o u r c e ，u s e d e c i s i o nt r e ec 4 5a l g o r i t h mb a s e do ns a m p l i n gt od i go u tc l a s s i f i c a t i o nr u l e s t e s t i n gs h o w s t h a tt h em e t h o dc a ns i g n i f i c a n t l yi m p r o v et h ee f f i c i e n c yo fd a t am i n i n go nc o n d i t i o nt h a t o b t a i n ss a t i s f a c t o r yc o r r e c t n e s s i m m e d i a t e l yc o m b i n eo n ec o n c r e t ea p p l i c a t i o nb a c k g r o u n do nt h e i r o na n ds t e e l e n t e r p r i s e s ，t h ei m p r o v e da l g o r i t h m w i l lb eu s e di nt w om a j o ra s p e c t s ：i r o na n ds t e e l e n t e r p r i s e sk e yp r o c e s s e so fp r o d u c t i o nc o s t sa n dal o s so fi r o na n ds t e e le n t e r p r i s e s t h ef i r s t a p p l i c a t i o nr e g a r d sc r a f tr o u t ea st h eb r e a k t h r o u g hp o i n t ，c o m b i n et h e c o s ta n a l y s i sp r o j e c t so f e n t e r p r i s e s ，d od a t aw a r e h o u s em o d e l i n gf o rp r o d u c t i o nc o s tp r o c e s s e s a d o p ti m p r o v e d d e c i s i o nt r e ea l g o r i t h mc 4 5u s e df o rm a s s i v ed a t a , d i go u to ft h ek e yp r o c e s s e si np r o c e s s r o u t e s ，t h ec l a s s i f i c a t i o nr u l e su s e df o rc o s t sa f f e c to fi r o na n ds t e e le n t e r p r i s e s ，p r o c e s s e sa n d m a t c h i n gt h eb e s tt e a m s t h es e c o n da p p l i c a t i o nc o m b i n e st h ep r o j e c t so f t h el o s sa n a l y s i so f e n t e r p r i s es a l e ，d od a t aw a r e h o u s em o d e l i n gf o rl o s sa n a l y s i s ，a n dd i go u tk e yi n f l u e n c i n g f a c t o r sf o ri r o na n ds t e e le n t e r p r i s e sl o s s t w oa p p l i c a t i o n sp r o v i d eas c i e n t i f i cb a s i sf o rt h e c o s to fm a n a g e m e n tf o re n t e r p r i s e a tt h es a m et i m ep r o v i d eag o o de x p e r i e n c ef o rt h e e s t a b l i s h m e n to fd a t am i n i n gs y s t e m h 摘要 k e yw o r d s ：d e c i s i o nt r e ea l g o r i t h m ；s a m p l i n g ；i r o na n d s t e e le n t e r p r i s e s ；c o s ta n a l y s i s ； d a t aw a r e h o u s em o d e l i n g 绪论 1 1 课题的背景和意义 第一章绪论弟一早瑁 下匕 1 1 1 课题的背景及可行性分析 无论是商业企业、科研机构或者政府部门，在过去的若干年时间里都积累了海量的、 以不同形式存储的数据资料。由于这些资料十分繁杂，从中发现有用价值的信息或知识， 达到为决策服务的目的，成为非常艰巨的任务。目前的许多数据库应用系统对数据库中 的数据进行管理和事务处理，而对这些数据进行进一步分析、发现隐含在数据间的特定 关系、趋势等高层次信息或知识的能力相对不足。随着企业数据环境的不断规范与完善， 企业用户信息化应用水平的不断提高，企业领导已不在满足于简单的领导查询功能，一 些新的需求( 如决策分析与决策支持等功能) 正在逐渐被企业领导所重视。现代企业的 领导更希望能够及时掌握各种产品销售趋势，了解本企业哪些产品销售量大、利润高? 哪些客户采购的产品数量多? 竞争对手的哪些产品对本企业产品构成威胁? 哪些用户 是赢利客户? 影响产品质量的内在因素等等。而数据挖掘技术就能从大规模的数据库中 发现用户感兴趣的隐含的有价值的信息，使企业能够为客户提供有针对性的服务，做出 正确的商业决策，确保企业在瞬息万变的信息时代始终处于有利的竞争位置。 某集团是以废钢、铁合金为主要原料的电炉、模铸、轧制短流程生产线为特征的钢 铁企业，它结合现代化管理模式的建立和实施从2 0 0 0 年开始逐年加大科技投入，进行 集团的大规模信息化建设。几年来，该集团通过实施信息化一期和二期工程，即 e r p ( e n t e r p r i s er e s o u r c ep l a n n i n g ) 系统和m e s ( m a n u f a c t u r i n ge x e c u t i o ns y s t e m ) 部分功 能：经营决策、管理决策、生产调度、实时监控等。提高了企业整体管理水平和企业的 市场竞争能力，促进了企业向现代企业模式的转变，也为企业可持续发展提供了动力。 信息系统的应用使企业能准确及时掌握库存信息，制定合理的物资采购计划，加强了企 业成本控制能力，规范了销售、物资采购的业务流程；通过优化排产，粗细两级生产能 力平衡，提高了设备生产效率和订单交货率，缩短了交货时间，加强了企业对现场控制 能力，实现了从销售订货一生产排产一生产跟踪一成品入库一销售，整个物流信息闭环 完全通畅。目前已启动的基于数据仓库的成本销售决策支持系统正是在这样的环境下开 发的。 大连交通大学工学硕十学位论文 1 1 2 本课题的目的和意义 本文就是在这样的背景下开展研究的。企业的成本管理和销售管理是一个制造企业 经营管理的重要组成部分。 成本管理在企业管理中占据着重要位置。成本是影响效益水平的高低的重要因素， 是反映企业生产经营状况的综合指标，并在很大程度上反映着企业各项经营活动的经济 效果，它可以显示企业生产经营管理水平的高低。另外，成本也是衡量企业是否具有发 展前途的重要指标，是影响企业经营预测、决策和分析的重要因素。 销售管理系统在企业经营活动具有重要的作用。节约交易费用，降低销售成本。持 续扩大市场范围，有利于持续开发全球市场。全球市场同步传递信息，系统内部数据共 享，提高工作效率。提高交易的透明度，减少暗箱操作，有利于建立相互监督机制，减 少腐败。缩短货款回收期，加速企业资金周转，提高资金使用效率。员工之间职责分工 明确，有利于提高工作效率。提高企业对市场的快速反应能力，全面提高企业竞争力。 直接快速地发布企业的信息资料，对外广告宣传，有利于树立企业形象。提供客户信息 反馈和客户跟踪服务，保持与客户的紧密接触。一年3 6 5 天2 4 小时不问断服务，提供 和( 或) 获取商业信息。保持企业与销售人员和客户的紧密联系，充分发挥团队的协同作 战优势。 本课题的目的和意义就是利用该集团现有的数据仓库中积累的大量的成本和销售 业务数据，建立基于集团型数据仓库的成本和销售决策分析系统，进行多角度的信息分 析和深层次的信息挖掘，为决策层提供高度综合的、反映成本决定因素、销售库存趋势 的、适合于生产经营决策的信息，辅助企业各级决策者进行与成本分析、库存销售有关 的决策分析，以改善管理者的决策能力、降低决策风险，提高决策的科学性和信息化程 度。 1 2 论文研究的主要思路 本论文研究的是决策树分类算法及其应用。决策树算法因为具有速度快，容易转化 成简单而便于理解的分类规则，容易转化成数据库查询语言等优点，而成为进行数据挖 掘分析的工具。通过以上的分析，本论文的主要思路是以成本分析和销售分析为切入点， 结合企业现有的数据仓库，建立适合挖掘的星型或者雪花模型，用改进的基于抽样的决 策树分类算法c 4 5 进行数据挖掘分析，分析集团型企业中成本和销售的决定因素，以 人性化、可视化的结果展示，给企业的决策者提供科学的决策依据。 2 绪论 1 3 论文的结构 本论文研究的是决策树分类算法及其应用。论文的结构如下： 第一章，绪论。介绍了本课题的背景和意义，研究的主要思路。 第二章，决策树分类算法综述。对常用的决策树分类算法进行论述。分析比较各常 用分类算法主要特性，优缺点，适用范围，及目前的改进状况。用定量和定性的方法将 结果表示出来。 第三章，基于抽样的决策树c 4 5 算法的研究。从挖掘算法的有效性、正确性和空 间性出发，将抽样的技术引入到决策树算法c 4 5 中，使得这种对小数据集有效的算法 也能在给定大数据集的情况下挖掘出有一定正确性的分类规则。并给出了改进算法的伪 代码和实验结果，说明了该改进算法的可行性。 第四章，决策树分类算法的应用。将改进的算法在钢铁企业中做了两个应用。前一 个应用是决策树分类算法在钢铁企业生产成本关键工序分析中的应用。建立了生产成本 关键工序的雪花模型和面向数据挖掘任务的生产成本关键工序决策表。挖掘出了工艺路 线关键工序分类树。后一个应用是决策树算法在钢铁企业亏损品种分析中的应用。建立 了销售亏损品种分析的雪花模型和销售亏损品种分析决策表。挖掘出了钢铁企业亏损品 种分析的决策树。 最后是论文的结论与展望部分。 本章小结 本章提出了论文研究的目的和可行性，并列举了论文的主要思路和主要工作。 3 大连交通大学t 学硕十学位论文 第二章决策树分类算法综述 2 1 分类算法 数据挖掘自提出以来，有着各种定义，较新的定义是f a y y a d 提出的：数据挖掘是 从数据集中识别出有效的，新颖的，潜在有用的以及最终可理解的模式的非平凡过程。 分类是数据挖掘中的主要技术之一，指在数据库的各个对象中找出共同特性，并按照分 类模型进行分类。近年来，数据挖掘分类提出了许多算法，按大的方向分类主要有：决 策树，贝叶斯，粗糙集，人工神经网络，遗传算法，关联规则，k 最临近，模糊集等。 分类的目的是构造一个分类函数或分类模型，该模型能把数据库中的数据项映射到某一 个给定类别中i l j 。定义1 给出了分类问题的定义。 定义l ：给定一个由元组( 条目，记录) 组成的数据库d = t l , t 2 ，t n 和一个类别集 合c = c l ，c m ) ，分类问题定义为从数据库到类集合的映射f - d c ，即数据库中的元 组t i 分配到某个类c i 中，有c j = t i l f ( t i ) = c i ，l i n ，且t i d ) 。1 2 j 分类的过程一般分为两个步骤【3 j ：第一步是训练阶段，通过已知训练集建立概念描 述模型。训练集是指数据库中为建立模型而被分析的数据元组集。训练集中的单个元组 称为训练样本，每个训练样本有一个类别标记。一个具体样本的形式可为：( v 1 ，v 2 ，v n ； c ) ；其中v i 表示属性值，c 表示类别。训练数据样本在数据库中以表结构形式组织存放， 该表有两种类型属性：一种称为类标号属性，另一种称为判定对象属性，也称条件属性。 条件属性又因为类型不同，分为连续属性( 也称数值属性) 和离散属性( 也称种类属性) 两 种。由于提供了每个样本的类标号，这一步也称为有指导的学习；第二步是测试阶段， 利用已获得的模型进行分类操作。首先用测试集评估模型的分类准确度，如果模型准确 度可以接受，就可以用它来对未知类标记的对象进行分类。一般来说，测试阶段的代价 远远低于训练阶段。 2 1 1 决策树( d e c i s i o nt r e e ) 分类算法 决策树分类算法通常分为两个步骤：决策树生成和决策树修剪。决策树生成算法是 以实例为基础的归纳学习方法，采用自顶向下的递归方式，在决策树的内部结点进行属 性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论 1 3 4 】。决策树修剪算法是消除决策树的过分拟合( o v e r f i t t i n g ) i h 题，过分拟合指过多的假 设与训练数据相一致，导致我们所做出的假设泛化能力过差。有两种基本的剪枝策略： 预先剪枝和后剪枝。理论上讲后剪枝好于预先剪枝，但计算复杂度大。 4 第二章决策树分类算法综述 h u n t 等人于1 9 6 6 年提出的概念学习系统c l s 是最早的决策树算法。以后的许多决 策树算法都是c l s 算法的改进或由c l s 衍生出来的。q u i n l a n 于1 9 7 9 年提出了著名的 i d 3 算法。1 9 9 3 年提出的以i d 3 算法为蓝本的c 4 5 是一个能处理连续属性的算法。其 它决策树算法还有i d 3 的增量版本i d 4 和i d 5 ，h a r t i g a n 于1 9 7 5 年提出的c h a i d 算法 及b r e i m e n 等于19 8 4 年提出的c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 算法等。强调在 数据挖掘中有伸缩性的决策树算法有s l i q ( s u p e r v i s e dl e a r n i n g i n q u e s t ) ， s p r i n t ( s c a l a b l ep a r a l l e l i z a b l ei n d u c t i o no fd e c i s i o nt r e e s ) 并1 r a i n f o r e s t 等【l 】o 2 1 2 贝叶斯( b e y e s ) 分类算法 b a y e s 算法是一类利用概率统计知识进行分类的算法。这些算法主要利用b a y e s 定 理来预测一个未知类别的样本属于各个类的可能性，选择其中可能性最大的一个类别作 为该样本的最终类别。和其它分类方法比较，b a y e s 算法有以下优势l l 邡，5 j ：( 1 ) 可以综 合考虑先验信息与后验信息；( 2 ) 适合处理带噪声与干扰的数据集；( 3 ) 其结果易于被理 解并可解释为因果关系。( 4 ) 贝叶斯方法与其它模型相结合，有效地避免了数据的过分拟 合。( 5 ) 它仅需扫描一次数据库。b a y e s 算法的不足是：( 1 ) 先验信息的使用，先验信息来 源于经验或者以前的实验结论，没有确定的理论做支持，因此在一定程度上存在争议。 ( 2 ) 处理数据复杂性高，因此时间和空间的消耗也比较大，贝叶斯方法要进行后验概率的 计算，区间估计，假设检验等，大量的计算是不可避免的。贝叶斯分类包括朴素贝叶斯 分类( n a t i v eb a y e sn e t w o r k ，简称n b ) 1 6 j 和贝叶斯网络即贝叶斯信念网络( b a y e s i a nb e l i e f n e t w o r k ，简称b b n ) 17 1 。n b 算法的分类前提是属性值之间相互独立，即不存在依赖关 系。分类算法的研究表明，n b 算法可以与决策树和神经网络相媲美，用于大型数据库 时，n b 算法也表现出高准确率与高速度。其改进算法有树形增强朴素贝叶斯分类 t a n ( t r e ea u g m e n t e dn a t i v eb a y e s ) 算法，结合e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法的朴 素贝叶斯分类算法等。但在实践中，属性值之间可能存在依赖关系，b b n 算法解决了 这个问题。b b n 由网络拓扑结构g 和局部概率分布的集合p 两部分组成。因此b b n 的 学习可以分解为两个阶段【8 l ：( 1 ) 参数学习：给定b b n 的结构，利用给定的样本数据学 习网络的参数。( 2 ) 结构学习：网络的结构没有确定，利用给定样本数据学习网络的结构 和参数。其中后者更为复杂些。参数学习包括从完备数据中学习概率参数的m l e ( 最大 似然估计) 方法，及从不完备数据中学习概率参数的蒙特卡洛方法，高斯近似法，梯度 方法和e m 算法。结构学习中包括从不完备数据中学习结构的m s e m ( m o d e ls e l e c t i o n e m ) 算法，a m s e m ( a l t e m a t i v em o d e l s e l e c t i o ne m ) 算法，b a y e s i a n - s e m ( b a y e s i a n s t r u c t u r ee m ) 算法，e g a ( e x c e p t i o n & g e n e t i ca l g o r i t h m ) 算法，b n g s ( b a y e s i a nn e t w o r k & 大连交通大学丁学硕十学位论文 g i b b e ss a m p l i n g ) 算法及从完备数据中学习结构的有基于约束的方法( c o n s t r a i n tb a s e d ) 和 基于打分的方法( s c o r eb a s e d ) 。 2 1 3 粗糙集( r o u g hs e t ) 分类算法 粗糙集理论是一种研究不精确，不确定知识的工具，由波兰科学家z p a w l a k 在1 9 8 2 年首先提出。详见文献o 1 1 1 2 1 。粗糙集分类算法的优势是：( 1 ) 数据挖掘研究的对象多 为关系型数据库，关系表可被作为粗糙集理论中的信息表或决策表，这给粗糙集方法的 应用带来极大的方便；( 2 ) 粗糙集的约简理论可用于高维数据的预处理，以去除冗余属性 从而达到降维的目的。( 3 ) 现实世界中的规则有确定的，也有不确定的。从数据库中挖掘 不确定的知识，为数据挖掘提供了用武之地。( 4 ) 运用粗糙集方法得到的数据挖掘算法有 利于并行执行，这可以极大地提高大规模数据库中的数据挖掘效率。 一个信息系统经过粗糙集方法处理后，可以实现以下目标：( 1 ) 从信息系统中去除冗 余对象，即值约简( 2 ) 从信息系统中去除冗余属性，即属性约简( 3 ) 估计某一属性的重要 度( 4 ) 得到独立属性的最小子集，同时保证与原属性的分类质量相同，即约简的属性集( 5 ) 得到各约简集的交集核，这是最优约简集的必须元素( 6 ) 得到分类规则。 应用粗糙集方法，所要处理的属性值必须是离散化的数据。但在实际应用中，属性 取连续值的情况是经常出现的。目前有许多不同的连续属性离散化方法，如等宽离散化， 等频离散化，统计检验方法，信息熵方法，自适应量化法等i l 引。但对于一个给定的数据 集，还没有一个确定的评判准则去评判哪一种方法更好。属性约简算法主要有以下几种： ( 1 ) 基本算法：基于区分矩阵与分辨函数的算法，基于相对差异表的算法。( 2 ) 基于属性 的重要性( 3 ) 遗传算法( 4 ) 复合系统的约简( 5 ) 扩展法则和动态约简。实验表明基于扩展法 则的属性约简算法比基本算法快数十到数百倍，因此能处理更大的数据集。而基于动态 约简的属性算法计算过程较为简明，且能够有效地增强约简的抗噪能力。( 6 ) 基于关联矩 阵的算法。值约简算法中有：( 1 ) 基于可分辨矩阵的值约简算法，( 2 ) 面向规则的约简算法， ( 3 ) 基于决策间不可区分关系的值约简，( 4 ) 采用属性值重要性度量作为附加信息的启发 式算法等。 粗糙集是数据挖掘的有效工具，具有坚实的理论基础。但在使用中也遇到了许多困 难，目前的有效途径有两条：一是粗糙集理论的扩展，二是粗糙集与其它方法的结合。 基于粗糙集的数据挖掘在以下方面有待深化：( 1 ) 高效约简算法。( 2 ) 粗糙集和其它软计 算方法的进一步结合。( 3 ) 粗糙集知识挖掘的递增算法，即在过去已挖掘知识的基础上， 修正和补充不合理的部分，以适应新的数据，而不是重新开始。( 4 ) 粗糙集基本运算的并 6 第二章决策树分类算法综述 行算法及硬件实现，以大幅度改善数据挖掘的效率，解决分布异构问题。( 5 ) 扩大数据处 理的范围。 2 1 4 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k a n n ) 分类算法 所谓神经网络就是一组连续的输入输出单元，其中每个连接都与一个权相关。在 学习阶段，通过调整神经网络的权，使得能够预测样本的正确类标号来学习。人工神经 网络按网络性能分为连续型与离散型，确定型与随机型。按网络的拓扑结构可分为前向 神经网络与反馈神经网络【l 】。前向神经网络常用的算法有感知器( p e r e e p t r o n ) ，径向基函数 神经网络( r b f ) ，多层前向神经网络的b p 算法等。反馈神经网络常用的算法有h o p f i e l d 神经网络，b o l t z m a n n 机等。 神经网络的优点有【2 , 1 0 ：( 1 ) 能很好地处理包含大量噪声数据的数据集。( 2 ) 既能处理 数值型的又能处理分类型的属性。( 3 ) 能并行分布工作，各组成部分同时参与运算。( 4 ) 神经网络信息存储分布于全网络的各个权重中，某些单元障碍并不影响信息的完整， 具有鲁棒性。缺点是i l 8 ，- 0 1 ：( 1 ) 不能解释网络的行为。( 2 ) 不能保证是一个最佳的解。( 3 ) 对训练数据可以实现很好的分类，但对测试数据可能会失效。( 4 ) 不能利用神经网络直接 生成规则。但可用一定的算法采掘规则，常用算法有f u 的k t 算法，t o w e l l 的m o f 算 法，s c s t i t o 等人的相似权值法以及在此基础上的c s w 算法等。( 5 ) 神经网络法的学习时 间较长。 神经网络算法的使用范围为：刚( 1 ) 实例是由许多“属性一值”对表示的，输入值可以 是任意实数。( 2 ) 目标函数的输出可能是离散值，实数值或者由若干实数属性或离散属性 组成的向量。( 3 ) 训练数据可能包含错误。( 4 ) 可容忍长时间的训练。( 5 ) 可能需要快速求 出目标函数值。( 6 ) 人类能否理解学到的目标是不重要的。 2 2 决策树( d e c i s i o nt r e e ) 分类算法典型算法分析 前面提到决策树方法具有速度快，容易转化成简单而便于理解的分类规则，容易转 化成数据库查询语言等许多优点，是一种简单但广泛使用的分类技术。下面对典型的决 策树分类算法的主要特性，优缺点，适用范围，目前的改进状况，决策树的应用及将来 的展望进行论述。决策树分类算法有很多种，但是到目前为止，还没有一种被证明对任 何的数据集的分类质量优于其它所有算法。在具体的应用中，要根据数据特征和问题的 性质来选择合适的算法。 7 大连交通大学工学硕士学位论文 2 2 1i d 3 算法 采用信息论中的概念，用信息增益( i n f o r m a t i o ng a i n ) 作为决策属性分类判断能力的 度量，进行决策结点属性的选择。属性的信息增益是属性的无条件熵与条件熵的差。在 构造决策树的过程中总是选择信息增益值最大的属性作为当前的测试属性，这样就可以 保证找到的是一棵简单的判定树。 任意样本分类的期望信息：i ( s l ，s 2 ，s m ) = 一p il 0 9 2 ( p i ) ( i = 1 ，m ) s 是s 个 数据样本的集合。类别属性具有m 个不同值c i 。s i 是类c i 中的样本数。p i 是任意样本 属于c i 的概率，并用s i s 估计。 由非类别属性a 划分为子集的熵：e ( a ) = ( s l j + + s m j ) s i ( s l j ，s m j ) 非类别属性a 具有v 个不同值( a l ，a 2 ，a v ) 。利用a 将s 划分为v 个子集( s l ， s 2 ，s v ) ；其中s j 包含s 中在a 上具有值a j 的样本。s i j 是子集s j 中类c i 的样本 数。 信息增益：g a i n ( a ) = i ( s l ，s 2 ，s m ) 一e ( a ) i d 3 1 3 1 算法具有计算速度较快，准确率较高，容易实现等优点，但同时也存在许多 不足之处：( 1 ) i d 3 算法只能处理离散型属性，对于连续型属性在分类前需对训练样本数 据中的对应项进行离散化。( 2 ) i d 3 算法使用信息论中的信息增益进行决策属性的选择， 而信息增益的主要特点是趋于那些有很多值的属性，这样会直接影响i d 3 算法的运行效 率及计算结果。( 3 ) 数据质量的好坏( 体现在数据是否存在大量的冗余，数据属性之间的 相关性过强以及数据缺损，不完整等) 是影响数据挖掘效率及结果的重要原因。数据源 的数据庞杂性会导致生成的决策树过于庞大。( 4 ) 在构造树的过程中，需要对数据集进行 多次的扫描和排序。因而导致算法的低效。近年来有大量的学者围绕该算法做了十分广 泛的研究，并提出了各种各样的改进方法。如：k o n e n k o 等人建议限制决策树为二叉树， 使得取值多的属性与取值少的属性有同等机会，此算法已在a s s i s t a n t 6 j 系统中实现， 虽然该算法的确能克服i d 3 算法偏向于取值多的属性的缺点，但是这个改进并不是很理 想。n i b l e t ta n db r m o k o 于1 9 8 6 年提出m e p 算法，利用l a p l a c e 概率估计来提高i d 3 算法在噪声域中的性能。1 9 9 8 年刘晓虎等提出了m i d 3 算法是对i d 3 的优化算法，当选 择一个属性时，m i d 3 算法不仅考虑该属性带来的信息增益，而且考虑选择该属性后继 选择的属性带来的信息增益，同时考虑树的两层结点。 2 2 2c 4 5 算法 c 4 5 t 1 4 1 算法继承了i d 3 算法的优点，并在以下几个方面改进了i d 3 算法【2 , 3 , 1 5 1 ：( 1 ) 利用信息增益比率来选择属性。为了达到最佳分裂的目的，c 4 5 先计算每个属性的增益， 8 第二章决策树分类算法综述 然后仅对那些高于信息增益平均值的属性应用增益比率进行测试。( 2 ) 可以处理具有缺少 属性值的训练样本。为了对一个具有缺失属性值的记录进行分类，可以基于已知属性值 的其它记录来预测缺失的属性值。( 3 ) 可以完成对连续属性的离散化处理。( 4 ) 通过使用 不同的修剪技术以避免树的过度拟合。在c 4 5 中，有两种预剪枝技术：子树替代法和 子树上升法。( 5 ) 采用k 次迭代交叉验证法。 增益比率g a i nr a t i o 衡量属性分裂数据的广度和均匀性。 s p l i t l n f o r 加a t i o n c ，一毫斟o g ：斜 s 1 到s c 是c 个值的属性a 分割s 而形成的c 个样本子集。实际上，分裂信息是s 关于属性a 的各值的熵。 增益比率： g a r a 面( ，= 丽者兹等丽 c 4 5 的缺点是在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而 导致算法的低效。此外c 4 5 只适合于能够驻留于内存的数据集，当训练集大得无法在 内存容纳时程序无法运行。 2 2 - 3s l i q 算法与s p r i n t 算法 上面介绍的i d 3 和c 4 5 算法等对于相对小的数据集是很有效的，当这些算法用于大 型数据集时，有效性和收缩性就出现了问题。s l i q t l 6 】是一种快速可扩展的分类算法， s p r i n t i l 7 1 是一种可伸缩的并行分类器，两者能有效解决上述问题。s l i q 和s p r i n t 都 是采用基尼指数作为属性选择的度量，都能在非常大的训练样本集上进行决策树的归纳 学习，都能处理连续属性和离散属性，都使用了预排序技术，对非常大而不能一次放入 内存的驻留磁盘的数据集进行排序。两种算法都定义并使用了新的数据结构，以利于树 的构造。 数据集t 包含来自n 个类的样本，g i n i 指标定义为 鲫 r2 1 一 ：i p 2 t f i 。：类j 出现的频率 = 。 ：蒌i 卜h 螂的堋举 如果一个划分将数据集t 分成两个子集s l 和s 2 。则分割后的的g i n i s p l i t 是： g i n i 舢( 丁) 。争g i n i ( 刚+ 争g i n i ( s2 ) 提供最小g i n i s p l i t 就被选择作为分割的标准。 9 大连交通大学t 学硕十学位论文 s l i q 算法使用若干驻留磁盘的属性表和一个驻留内存的类表。在决策树生成时采 用广度优先增长策略和m d l ( 最短描述长度) 剪枝。其算法是分割时只需变换类表中结点 的指针，无需分割属性表。s l i q 算法的优点有【3 】：( 1 ) 运算速度快，对属性值只做一次 排序。( 2 ) 利用整个训练集的所有数据，不做取样处理，不丧失精确度。( 3 ) 轻松处理磁 盘常驻的大型数据集，适合处理数据库的海量数据。( 4 ) 更快的，更小的目标树。( 5 ) 低 代价的m d l 剪枝技术。s i l q 算法的缺点是类表必需常驻内存，且类表的大小随训练样 本中元组数目成比例增长，当类表太大不能放在主存时，s l i q 的性能下降。 s p r i n t 算法是分割属性列表，并用该列表的记录索引生成记录元组所在结点的哈 希表，用该哈希表分割其它属性列表。s p r i n t 算法的优点有：( 1 ) 训练样本数量不受内存 的限制。( 2 ) 具有很好的伸缩性、加速性和扩容性。( 3 ) 并行容易实现，效率较高。 s p r i n t 算法的缺点在于使用属性列表，为每个n o d e 都保存属性表，这个表的大小 有可能是数据库中原始数据大小的好几倍，导致存储代价比原来高，结点分割要创建哈 希表( 该表的大小与该n o d e 所具有的纪录成正比) ，维护每个n o d e 属性表的h a s h 表的开 销很大，加大了系统的负担，结点分割技术也相对复杂i 。 2 2 4c h a i d 算法 c h a i d 2 j 算法采用卡方统计量来确定树的分裂，它可用于类别值、卡方检验。c h a i d 算法的原理是用最大似然比或p e a r s o nx 2 检验针对某一设定的反应变量，对一系列的解 释变量加以比较，找出最佳解释变量和反应变量的分类结果。其过程是将解释变量分成 一系列的二维表，从中找出最有统计差异的解释变量，在此变量的基础上继续进行二维 分类，直到结果满意为止。 2 2 5c a r t 算法 分类与回归树c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 1 1 8 】算法先生成一棵非常 复杂的树，再根据交叉验证和测试集验证的结果对树进行剪枝。从而得到最优通用树。 c a r t 算法是对i d 3 算法的改进，是一种产生二叉决策树的技术，与i d 3 一样，采用信 息增益来作为选择最佳分裂属性的度量。但与i d 3 算法不同的是在每个子类产生子结点 的地方，只产生两个子结点【2 1 9 j ，即可处理连续属性又可以处理离散属性。c a r t 模型 最早由b r e m a n 等人提出并在统计学领域普遍应用。 c a r t 是一种有监督学习算法，即用户在使用c a r t 进行预测之前，必须首先提供 一个学习样本集( l e a r n i n gs a m p l e s ) 对c a r t 进行构建和评估，然后才能使用。修剪中 采取的是后剪枝( p o s t p r u n i n g ) 方法【l5 1 。在修剪中我们采用c a r t 系统的成本一复杂度 1 0 第二章决策树分类算法综述 最小( m i n i m a lc o s t c o m p l e x i t yp r u n i n g ) 原则。这里我们所采用的是测试样本评估。这 种方法使用独立的测试样本，它的机时效率较高，适用于学习样本包括大量事件的情况。 分类回归树是基于统计理论的非参数的识别技术，它具有非常强大的统计解析功能， 对输入数据和预测数据的要求可以是不完整的，或者是复杂的浮点数运算。它将模型的验 证和最优通用树的发现嵌入了算法中。而且，数据处理后的结果所包含的规则明白易懂。 因此，分类回归树已成为对特征数据进行建立统计解析模型的一个很好的方法。当然，与 其它统计分析方法一样，c a r t 自身也存在缺点。如ca rt 模型的稳定性较差，用类似 研究资料建立的树型模型往往存在差异。c a r t 本身是一种大样本的统计分析方法，样本 量较小时模型不稳定。对于内部同质性较好的数据，ca rt 分析的结果与其它分析方法 得到的结果基本一致。 2 2 6 雨林( r a i n f o r e s t ) 算法 过去的研究提出了多种决策树算法，但是到目前为止并没有一种算法在任何数据集 合下生成决策树的质量方面超过所有其他的算法。雨林算法【2 0 j 框架关注于提高决策树算 法的伸缩性，该框架可运用于大多数决策树算法( 例如s p r i n t 和s l i q ) ，使算法获得的 结果与将全部的数据放置于内存所得到的结果一致。雨林算法的核心思想是根据每一次 计算所能使用的内存空间，合