（计算机应用技术专业论文）基于决策树的数据挖掘算法研究与应用.pdf

摘要 数据挖掘是信息处理领域的一项重要课题，它融合了数据库、人工智能、机器学习、 统计学等多个领域的理论和技术。分类是数据挖掘的重要功能之一，基于决策树的分类 算法在数据挖掘中的应用是非常广泛的。与其他分类算法相比，决策树具有计算量相对 较小、易于提取显式规则、可以显示重要的决策属性和分类准确率较高等优点。 然而在实际应用过程中，现存的决策树算法也存在着很多不足之处，如计算效率低 下、生成树的规模较大等。因此，进一步改进决策树算法，提高决策树的性能，使其更 加适合数据挖掘技术的应用要求具有重要的理论和实际意义。 针对上述不足，本文进行了深入的研究，将粗糙集理论引入决策树分类当中，对如 何优化决策树分类算法进行了探索。本文主要研究工作如下： 首先，论文介绍了数据挖掘的相关技术和理论基础，并重点对决策树生成及后剪枝 算法进行了分析和比较。 其次，从属性约简和剪枝两方面对决策树算法进行优化，提出了基于属性依赖度的 属性约简算法e r 和基于粗糙集理论的决策树后剪枝算法p r u n e 。 最后，将优化的决策树算法应用于供应商评价系统当中，并将该算法与c 4 5 算法 作了比较，验证了该算法的有效性。 关键词：数据挖掘，分类，决策树，粗糙集理论 r e s e a r c ho nd a t am i n i n g a l g o r i t h ma n da p p l i c a t i o nb a s e do n d e c i s i o nt r e e l im i n g z h u a n g ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y ：s e n i o re n g i n e e rz h a n g w e n - d o n g a b s t r a c t d a t am i n i n gi st h e f a i r l ys i g n i f i c a n tt h e s i si nt h ef i e l do fi n f o r m a t i o n - p r o c e s s i n g t e c h n o l o g y , w h i c hc o n s i s t so fm a n yt h e o r i e sa n dt e c h n o l o g ys u c ha s b a s e a r t i f i c i a l i n t e l l i g e n c e ，m a c h i n el e a r n i n ga n ds t a t i s t i c s c l a s s i f i c a t i o ni so n eo ft h ei m p o r t a n tf u n c t i o n so f d a t am i n i n g ，c l a s s i f i c a t i o na l g o r i t h mb a s e do nd e c i s i o nt r e e i sw i d e l yu s e di nd a t am i n i n g c o m p a r e dw i t ho t h e rc l a s s i f i c a t i o nm e t h o d s ，d e c i s i o nt r e eh a st h ef o l l o w i n ga d v a n t a g e s ： r e l a t i v e l ys m a l l e rc a l c u l a t i o nw o r k l o a d ，t h ee a s eo fg e t t i n ga p p a r e n tr u l e s ，t h ec a b a b i l i t yo f s h o w i n gi m p o r t a n td e c i s i o nc h a r a c t e r i s t i c sa n dh i g h e rc o r r e c t n e s so fc l a s s i f i c a t i o n ，e t c h o w e v e r , t h ee x i s t i n gd e c i s i o nt r e ea l g o r i t h ma l s oe x i s t sal o to fs h o r t a g ew h e nb e i n g a p p l i e di np r a c t i c e ，s u c ha si t sl o w e rc o m p u t a t i o ne f f i c i e n c ya n d b i g g e rs c a l eo fd e c i s i o nt r e e ， e t c t h e r e f o r e ，i tp o s s e s s e ss i g n i f i c a n c eb o t ht h e o r e t i c l ya n d f a c t u a l l yt om a k ef u r t h e r l m p r o v e m e n ti nd e c i s i o nt r e ea l g o r i t h ms oa st oe n h a n c ei t sc a p a c i b i l i t ya n dm a k ei tm o r e s u i t a b l ef o rp r a c t i c a la p p l i c a t i o n i no r d e rt ot r yt os o l v et h ea b o v ep r o b l e m s ，t h ea u t h o ro ft h i sp a p e rm a k e s d e e pr e s e a r e h o nt h o s ep o i n t s t h er o u g hs e tt h e o r yi si n t r o d u c e di n t od e c i s i o nt r e ec l a s s i f i c a t i o n a n dt h e m e t h o do fo p t i m i z i n gt h ed 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 mi si n v e s t i g a t e d t h em a i nw o r k d o n ei nt h i sp a p e ri sa sf o l l o w s ： f i r s t l y , t h i sp a p e ri n t r o d u c e st h er e l a t e dt e c h o n o l o g ya n dt h et h e o r e t i cb a s i so fd a t a m i n i n ga n dc l a s s i f i c a t i o nt e c h n o l o g y , a n dt h ee m p h a s i si sa t t a c h e dt ot h e a n a l y s i sa n d c o m p a r i s o no fd e c i s i o nt r e ea n dp o s t p r u n i n ga l g o r i t h m s s e c o n d l y , t h ed e c i s i o nt r e ea l g o r i t h mi so p t i m i z e di nt h i sp a p e ri nt w oa s p e c t s ：a t t r i b u t e r e d u c t i o na n dp r u n i n g a t t r i b u t er e d u c t i o na l g o r i t h me rb a s e do nt h ed e g r e eo fd e p e n d e n c yo f a t t r i b u t ea n dp o s t p r u n i n ga l g o r i t h mp r u n eb a s e qo nr o u g hs e tt h e o r ya r ep r o p o s e d f i n a l l y ，t h eo p t i m i z e dd e c i s i o nt r e ea l g o r i t h mi su s e di n s u p p l i e r m e a s u r e m e n t s y s t e m ，a n di t sv a l i d i t yi sv e r i f i e dw h e nc o m p a r i n gw i t hc 4 5a l g o r i t h m k e yw o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o nt r e e ，r o u g hs e tt h e o r y 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：壅璺旦：睦日期： 啼厂月“日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：查塑：巨 指导教师签名： 日期：羽年r 月“r 日期：2 0 p f 年箩月z 乡日 中国油人学( 华东) 硕士学位论文 第一章前言 1 1 研究背景及意义 近年来，随着计算机技术的不断发展，我们存储的信息数据越来越多，如何发现信 息数据背后隐藏的知识，进一步指导我们的行业行为是我们面临的一个重要问题。数据 挖掘技术1 。2 1 正是为解决上述问题而产生的，它能找出数据之间的潜在联系，进行更高 层次的分析，以便更好的作出理想的决策，预测未来的发展趋势。经过近几年的发展， 数据挖掘已越来越显示出其强大的生命力。 数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法构造数据模 型的方式也不相同，在进行数据挖掘时可采用许多不同的方法，如神经网络、决策树、 遗传算法和可视化技术等。数据分类是数据挖掘中的一项重要功能。用于数据分类的方 法有很多【3 4 1 ，如决策树方法，贝叶斯网络，遗传算法，基于关联的分类方法，粗糙集， k 最临近方法等。其中，决策树方法是数据分类常用的方法之一，与其他分类方法相比 决策树方法具有如下显著优点： ( 1 ) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直 走到叶，沿途的分裂条件就能够唯一确定一条分类的规则。 ( 2 ) 准确性高：跟其他分类方法相比，利用决策树挖掘出的分类规则准确性更高， 能更好地指导人们的决策。 ( 3 ) 易被人理解：决策树不需要使用者了解很多背景知识，且生成规则简单，还 可以清晰的显示哪些字段比较重要。 ( 4 ) 可伸缩性强：既可用于小数据集，也可用于海量数据集。 目前，基于决策树的数据挖掘技术已被广泛应用于各个领域：在零售业，其应用主 要涉及客户细分和交叉销售等方面；在金融业，其应用突出表现在信用评估和防止欺诈 等方面；在电信业，其最突出表现是其在客户保持方面的应用：在电子商务领域，其在 在线销售、数字销售、网络广告、客户关系管理等诸多方面有着广泛地应用；在气象领 域，其在预测严重暴风雨方面有重要应用；在安全反恐领域，数据挖掘可以解决视频图 像序列中的动作识别问题，能给专家提供重要的技术支持。 基于决策树的数据挖掘技术目前还存在以下问题： ( 1 ) 信息增益方法偏向于选择取值较多的属性，即内偏置问题。该问题造成了决 策树容易过分拟合、规模过大、产生的规则长度过长等缺点。 ( 2 ) 计算效率较低。目前的决策树算法在进行属性选择时多数都采用基于信息熵 1 第一章前苦 的理论，由于计算信息熵的时间复杂度较高，并且决策树的构造是一个循环递归的过程， 多次计算将导致复杂的计算费用。 ( 3 ) 测试属性约简问题。目前的测试属性约简算法还不够成熟，现有的决策树算 法大多都针对原始的训练集进行构建，没有经过测试属性的约简，从而导致算法增加了 大量的多余计算。 ( 4 ) 决策树剪枝问题。随机噪声和某些决策仅取决于少量的训练数据，都会导致 决策树的分类精度下降，并且过度拟合训练数据集。解决这些问题主要是通过对决策树 进行剪枝来实现的。目前的剪枝算法在精度和复杂度方面还不够理想，有待进一步改进。 本文主要对测试属性约简和决策树剪枝问题进行探讨。 1 2 国内外研究现状 1 2 1 国外研究现状 目前，决策树技术已经在许多数据挖掘系统中得到研究者的关注，国内外很多公司 均已推出自己的数据挖掘系统，其中大多都采用决策树方法。文献 5 】对s a s 公司的s a s e n t e r p r i s em i n e r 进行了介绍，指出该系统是一种通用的数据挖掘工具，能够通过收集分 析各种统计资料和客户购买模式，来帮助用户发现业务的趋势，解释已知事实，预测未 来结果，并识别完成任务所需的关键因素。文献【6 】中介绍的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 提供了一个可视化的快速建模环境，由数据获取、挖掘、整理、 建模和报告等部分组成。a n g o s s 公司的k n o w l e d g es e e k e r 是一个基于决策树的数据分 析程序，具有相当完整的分类树分析功能。文献 7 】中介绍的r i g h t p o i n t 公司的 d a t a c r u n c h e r 是一种客户服务器方式的数据挖掘引擎，具有分析数据仓库中海量数据的 能力，能与当今的许多主流关系数据库和数据挖掘辅助工具直接进行连接，辅助建立面 向营销的数据挖掘研究的模型。此外，还有美i 虱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 n g r a p h i c 公司的m i n e s e t ，v a n g u a r ds o f t w a r e 公司的d e c i s i o np r 0 3 0 ，l i t i g a t i o nr i s ka n a l y s i s 公司的l i t i g a t i o nr i s ka n a l y s i s 等。 比较成熟的决策树算法有i d 3 1 8 1 ，c 4 5 t 9 1 ，c h a i d i 7 1 ，c a r t t l 们，p u b l i c t l l l ，s l i q 1 2 1 ， s p r i n t t l 3 1 等。c 4 5 算法是q u i n l a n 本人针对i d 3 算法提出的一种改进算法，1 9 9 3 年， q u i n l a n 出版了专著机器学习规划对c 4 5 算法进行详细描述。c h a i d ( 即c h i s q u a r e a u t o m a t i ci n t e r a c i o nd e t e c t o r 的缩写，卡方自动互动侦测器) 算法是g o r d o nb k a s s 博士在 2 中国石油大学( 华东) 硕_ f ：学位论文 1 9 7 6 年提出的，可用来对分类性数据( 如患者属于哪个州或患者的性别) 进行挖掘。 c a r t ( b o 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 的缩写，分类回归树) 算法从1 9 8 4 年丌始得到 普及推广，可对连续型因变量进行处理。p u b l i c 算法是r a j e e v ，r a s t o g i 等人在2 0 0 0 年 提出的，它不但继承了c a r t 算法建树的基本原理，而且还使用了更加高效的剪枝策略。 s l i q 算法可以处理大规模的训练样本集，具有较好的伸缩性，但对主存容量要求较高。 j o h ns h a l e r 等人提出s p r i n t 算法的目的就是要彻底解决主存容量的限制，与s l i q 相比， s p r i n t 算法完全摆脱了主存容量的限制，同时也具有并行性。 针对现有决策树算法的不足，很多研究人员尝试在控制决策树的规模和提高决策树 的精度等方面做出努力，通过研究各种预剪枝算法和后剪枝算法来控制树的规模，同时 在修改测试属性空间、改进测试属性选择方法、限制数据集、改变数据结构等方面提出 了许多新的算法和标准。 1 2 2 国内研究现状 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量【1 4 。15 1 。1 9 9 3 年国家自 然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相 开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究 所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究， 华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则开采算法的优化和改造，南京大学、四川联合大学和上海交通大 学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。文献【6 】中介绍了中 科院计算技术研究所智能信息处理重点实验室开发的m sm i n e r 。该系统是一种多策略知 识发现平台，能够提供快捷有效的数据挖掘解决方案和多种知识发现方法。 国内许多研究人员都在i d 3 算法基础上提出了自己的改进思想。文献 1 6 】中洪家荣 等从事例学习最优化的角度分析了决策树归纳学习的优化原则，提出了一种新的基于概 率的决策树构造算法p i d 。p i d 在决策树的规模和精度方面优于i d 3 ，但是在训练速度 和测试速度上比i d 3 慢，并且p i d 决策树上的某些属性可能重复使用。针对i d 3 算法偏 向于选择取值较多属性的这一缺点，文献 1 7 q p 支t j d , 虎等提出了i d 3 算法的优化算法一 一m i d 3 算法。该算法在选择一个新的属性时，不是仅仅考虑该属性带来的信息增益， 而是考虑到选择该属性后继续选择的属性带来的信息增益，即同时考虑树的两层结点， 取得了比i d 3 更好的分类效果。较之传统的i d 3 算法，徐凌宇等提出的l b e t 方法的最 3 第一章前言 大优点在于接受和记忆数据的信息量增加。文献【1 8 】中曲开社等人就q u i n l a n 的i d 3 算 法中信息熵标准有倾向于取值较多属性的缺陷，在计算信息熵时引入了用户兴趣度，改 进了i d 3 算法，使决策树减少了对取值较多属性的依赖性。文献 1 9 】中赵卫东等人将粗 糙集理论应用于决策树的构造过程，提出了一种利用粗糙集理论对决策树进行优化的算 法，取得了较好的优化效果。文献 2 0 1 q b 苗夺谦等人用相对泛化的概念构造多变量检验， 提出一种评价多变量检验的准则。文献【2 1 中吴艳艳提出了将决策树的基本建树思想 i d 3 算法与粗糙集理论相结合的一种新型的决策树建树方法，该方法的提出使数据挖掘 的结果更简单、更容易理解。 1 3 主要研究内容 论文主要研究了两项内容：决策树测试属性约简和后剪枝算法。 ( 1 ) 决策树测试属性约简。通过对粗糙集理论和现有属性约简算法的研究，提出 了一种改进的基于粗糙集理论属性依赖度的属性约简算法，该算法主要从时问复杂度上 来进行改进，在保持分类能力不变的情况下，不必经过大量计算就能找出较优的属性约 简集。 ( 2 ) 决策树后剪枝算法。在研究基于粗糙集理论的现有后剪枝算法的基础上，针 对现有算法执行效率不高的问题进行改进，提出了一种改进的基于粗糙集理论的决策树 后剪枝算法。算法首先确定重要结点，剪枝时只需计算子树根结点和子树所含重要结点 的分类错误率而不必计算非重要结点的错误率，这在很大程度上降低了时间复杂度。 1 4 本文的组织结构 论文共分为五章，安排如下： 第一章介绍了本课题的研究背景和意义，详细介绍了决策树分类技术的国内外研究 现状。 第二章介绍了决策树分类技术的相关知识，详细介绍了常用的决策树分类算法以及 决策树后剪枝方法，并对决策树的主要研究内容进行了探讨。 第三章对粗糙集理论进行了研究，提出了基于属性重要性的测试属性约简算法和基 于粗糙集理论的决策树后剪枝算法，并对算法性能进行了比较分析，通过实验对两算法 进行了验证。 第四章应用第三章提出的测试属性约简和后剪枝算法对决策树进行优化，并将优化 算法应用于供应商评价系统当中，最后将优化算法与c 4 5 算法作了比较。 4 中国石油大学( 华东) 硕士学位论文 第五章结论部分总结了论文的主要工作和创新点，并对下一步工作进行了展望。 5 第一二章数据挖掘相关技术研究 第二章数据挖掘相关技术研究 2 1 数据挖掘技术 2 1 1 数据挖掘概念 数据挖掘( d a t am i n i n g ，d m ) ，就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的，人们事先不知的，但又是潜在有用的信息和知识的过 程 2 2 - 2 3 】。 数据挖掘是一门来自各种不同领域的研究者共同关注的交叉性学科，受到多个学科 的影响，最主要的学科包括：数据库技术、统计学、人工智能、机器学习、模式识别、 高性能计算、可视化技术、信息科学等。 2 1 2 数据挖掘步骤 数据挖掘的全过程描述如图2 1 所示： 清理与 选择与 数据 触- 品娥- 日三7 u7 u 数据库数据仓库特定数据集模式 知识 图2 1 数据挖掘步骤示意图 f i 9 2 - 1 d a t am i n i n gs t e p ss k e t c h 整个数据挖掘过程是由若干挖掘步骤组成的，主要步骤有2 4 】： ( 1 ) 数据清洗( d a t ac l e a m i n g ) ，其作用就是清除数据噪声和与挖掘主题明显无关的 数据。 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) ，其作用就是将来自多数据源中的相关数据组合到 一起。 ( 3 ) 数据转换( d a t at r a n s f o r m a t i o n ) ，其作用就是将数据转换为易于进行数据挖 掘的数据存储形式。 ( 4 ) 数据挖掘( d a t am i n i n g ) ，它是知识挖掘的一个基本步骤，其作用就是利用智 能方法挖掘数据模式或规律知识。 ( 5 ) 模式评估( p a t t e r ne v a l u a t i o n ) ，其作用就是根据一定评估标准从挖掘结果筛 选出有意义的模式知识。 ( 6 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，其作用就是利用可视化和知识表达技术， 6 中国石油大学( 华东) 硕_ j 学位论文 向用户展示所挖掘出的相关知识。 2 1 3 数据挖掘功能 利用数据挖掘技术可以帮助用户获得决策所需的多种知识。在许多情况下，用户并 不知道数据存在哪些有价值的信息知识，因此对于一个数据挖掘系统而言，它应该能够 同时搜索发现多种模式的知识，以满足用户的期望和实际需要。此外数据挖掘系统还应 能够挖掘出多种层次( 抽象水平) 的模式知识。数据挖掘功能以及所能够挖掘的知识类 型如下所述【2 5 2 6 】： ( 1 ) 分类和回归 分类是在已有数据集的基础上学会一个分类函数或构造一个分类模型，该函数或模 型能够把训练集中的数据记录映射到给定类别中的某一个，从而可以应用于数据预测。 回归则是通过具有已知值的变量来预测其他变量的值。和分类方法不同的是，分类输出 的是离散的类别值，而回归输出的则是连续数值。 ( 2 ) 关联分析 关联分析用于发现大量数据中项集之间有意义的关联或相互关系，寻找给定数据集 中项之间的有趣联系。关联规则的支持度和置信度是两个规则兴趣度度量，他们分别反 映发现规则的有用性和确定性。数据库中的数据一般都存在着关联关系。关联分析模型 的一个典型例子是购物篮分析，通过对顾客购买偏好的分析，确定商品促销的目标客户， 以此来设计各种商品促销的方案，并通过商品购买关联分析的结果，采用交叉销售和向 上销售的方法，挖掘客户的购买力，实现准确的商品促销。 ( 3 ) 聚类 聚类就是将数据对象分组成为多个类或簇，划分的原则是在同一个簇中的对象之间 具有较高的相似度，而不同簇中的对象差别较大。聚类增强了人们对客观现实的认识， 是概念描述和偏差分析的先决条件。与分类不同，聚类操作中要划分的类是事先未知的， 类的形成完全是数据驱动的，属于一种无指导的学习方法。 ( 4 ) 孤立点分析 数据库中可能包含一些数据对象与大部分的一般行为或模式不一致，我们称之为孤 立点。大部分数据挖掘方法将孤立点视为噪声或例外丢掉，然而在一些应用如欺诈检测 中，罕见的事件可能比正常出现的事件更有趣，针对孤立点的数据分析称为孤立点挖掘。 ( 5 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述 7 第二章数据挖掘相关技术研究 分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之 间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描 述的方法很多，如决策树方法、遗传算法等。 2 1 4 数据挖掘常用技术 数据挖掘有如下常用技术【2 7 】： ( 1 ) 决策树 所谓决策树就是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属 性( 取值) 的测试，其分支就代表测试的每个结果，而树的每个叶结点就代表一个类别， 树的最高层结点就是根结点。如图2 2 所示，就是一个决策树示意描述，该决策树描述 了一个购买电脑的分类模型，利用它可以对一个学生是否会在本商场购买电脑进行分类 预测。决策树的中间结点通常用矩形表示，而叶子结点常用椭圆表示。常用的决策树方 法有i d 3 、c 4 5 、c a r t 、c h i a d 和p u b l i c 。 图2 - 2 决策树示意描述 f i 9 2 - 2 d e c i s i o nt r e ei n d i c a t ed e s c r i p t i o n ( 2 ) 神经网络 神经网络是一种新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建 立的一种计算模型。其特点是利用大量简单的计算单元连成网络，来实现大规模并行计 算。 神经网络建立在自学习的数学模型基础之上，它可以对大量复杂的数据进行分析， 并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络系统由 一系列类似于人脑神经元一样的处理单元组成，我们称之为节点( n o d e ) 。这些节点通过 网络彼此互连，如果有数据输入，它们便可以进行确定数据模式的工作。神经网络有相 8 中国石油大学( 华东) 硕士学位论文 互连接的输入层、中间层( 或隐藏层) 、输出层组成。其中中间层由多个节点组成，完 成大部分网络工作。输出层输出数据分析的执行结果。例如我们可以指定输入层为代表 过去的销售情况、价格及季节等因素，输出层便可输出判断本季度的销售情况的数据。 神经网络近来越来越受到人们的关注，因为它为解决复杂度较大的问题提供了一种 相对有效的简单方法。神经网络可以很容易的解决具有上百个参数的问题。神经网络常 用于两类问题：分类和回归。 输入层隐含层输出层 图2 _ 3 神经网络示例图 f i 9 2 - 3 n e u r a ln e t w o r k se x a m p l e sm a p 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层，如图2 3 所示。 输入层的每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在 输入层和输出层之间是隐含层，隐含层的层数和每层节点的个数决定了神经网络的复杂 度。 ( 3 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) ，是近几年发展起来的一种崭新的全局优化算 法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个 体适应性的提高，这一点体现了自然界中“物竞天择、适者生存”的进化过程。1 9 6 2 年h o l l a n d 教授首次提出了g a 算法的思想，从而吸引了大批的研究者，并迅速推广到 优化、搜索、机器学习等方面，从而奠定了坚实的理论基础。 由于遗传算法是一种基于生物进化论和分子遗传学的搜索优化算法，在用遗传算法 解决问题时，首先要将问题可能的解按某种形式进行编码，一般用字符串来表示，这个 过程就将问题符号化、离散化了。 编码后的解称为染色体，随机选取n 个染色体作为初始种群，再根据预定的评价函 9 第一二章数据挖掘相关技术研究 数对每个染色体计算适应值，性能较好的染色体有较高的适应值。选择适应值较高的染 色体进行复制，并通过遗传算子，产生一群新的更适应环境的染色体，形成新的种群， 直至最后收敛到一个最适应环境的个体，得到问题的最优化解。 ( 4 ) 近邻算法 将数据集合中每一个记录进行分类的方法。依据“d oa sy o u rn e i g h b o r sd o 的原则， 相邻数据必然有相同的属性或行为。k n e a r e s t 邻居方法的含义为：k 表示某个特定数据 的k 个邻居，可以通过k 个邻居的平均数据来预测该特定数据的某个属性或行为。 ( 5 ) 粗糙集方法 粗糙集方法是一种处理模糊和不确定问题的新的数学工具。利用粗糙集可以处理的 问题包括数据约简、数据相关性的发现、数据意义的评估、由数据产生决策算法、数据 中范式的发现及因果关系的发现等。粗糙集理论作为数据挖掘的一种方法，近年来得到 了计算机研究领域的广泛关注和青睐。这不仅是因为它具有良好的数学基础和性质，而 且还因为它恰好反映了人们用粗糙集方法处理不分明问题的常规性，即以不完全信息或 知识去处理一些不分明现象的能力，或依据观察、度量到的某些不精确的结果而进行数 据分类的能力。粗糙集理论也不是万能的，对建模而言，尽管粗糙集理论对知识不完全 的处理是有效的，但是，由于这个理论未包含处理不精确或不确定原始数据的机制，因 此，单纯地使用这个理论不一定能有效地描述不确定或不精确的实际问题。同时，由于 粗糙集理论只能作用于具有离散值的系统，其应用领域也受到了限制，这意味着需要其 他方法的补充。 目前，决策树与粗糙集理论相结合的分类技术得到了快速的发展，把粗糙集理论与 决策树理论相联系，取长补短，充分发挥决策树和粗糙集理论的优点，为分类的实际应 用寻找新方法、开辟新途径，是我们面临的一个新课题。 2 2 决策树技术 2 2 1 决策树简介 决策树是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性的 测试，即形式为( a i - - v i ) 的逻辑判断，其中a i 是属性，v i 是该属性的某个属性值，其分 支就代表测试的每个结果，也就是每一种可能的值和一条边一一对应，叶子结点指定一 个类别。决策树构造的输入是一组带有类别标记的数据，构造的结果是一棵二叉或多叉 树。树中结点可分为两类：决策结点和叶子结点。 决策树是一种有指导学习的常用方法。首先，从训练集中选取实例的一个子集，然 1 0 中国石油大学( 华东) 硕l 学位论文 后使用这些子集构建一个决策树，剩下的训练集实例用于检验所建决策树的准确度。如 果决策树能正确地对实例进行分类，该过程结束。如果某实例分类有误，那么，该实例 就被添加到所选训练实例子集中，并构建一棵新树，直到创建了一个能j 下确分类所有未 选训练实例的树为止。 决策树生成基本算法如下所述： g e n e r a t e _ d e c i s i o n _ t r e e 根据给定数据集产生一个决策树 输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为a t t r i b u t el i s t 。 输出：决策树。 处理流程： ( 1 ) 创建一个结点n ； ( 2 ) 若该结点中的所有样本均为同一类别c ，则开始根结点对应所有的训练样本 ( 3 ) 返回n 作为一个叶结点并标志为类别c ； ( 4 ) 若a t t r i b u t el i s t 为空，则 ( 5 ) 返回n 作为一个叶结点并标记为该结点所含样本中类别个数最多的类别； ( 6 ) 从a t t r i b u t el i s t 选择一个信息增益最大的属- i 生t e s ta t t r i b u t e ； ( 7 )并将结点n 标记为t e s ta t t r i b u t e ； ( 8 ) 对于t e s ta t t r i b u t e 中的每一个己知取值a i ，准备划分结点n 所包含的样本集； ( 9 ) 根据t e s ta t t r i b u t e = a i 条件，从结点n 产生相应的一个分支，以表示该测试条件： ( 1 0 ) 设s i 为t e s t ( 1 1 ) 若s i 为空，则将相应叶结点标记为该结点所含样本中类别个数最多的类别； ( 1 2 ) 否则将相应叶结点标志为g e n e r a t e _ d e c i s i o n _ t r e e ( s i ，a t t r i b u t e _ l i s t - t e s t _ a t t r i b u t e ) 返回值； 算法递归操作的终止条件是： ( 1 ) 给定结点的所有样本属于同一类( 步骤2 和3 ) 。 ( 2 ) 没有剩余属性可以用来进一步划分样本( 步骤4 ) 。 ( 3 ) 没有样本满足t e s ta t t r i b u t e = a ( 步骤1 1 ) 。 基本决策树算法是一种贪心算法。它采用白上而下、分而制之的递归方式来构造一 个决策树。g e n e r a t ed e c i s i o nt r e e 算法就是著名决策树算法i d 3 的一个基本版本。 2 2 2 常见的决策树分类算法 ( 1 ) i d 3 算法 第二章数据挖掘相关技术研究 i d 3 算法运用信息熵理论，选择当前样本集中具有最大信息增益值的属性作为测试 属性。样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集 划分为多少子样本集，同时，决策树上相应于该样本集的结点长出新的叶子结点。由于 决策树的结构越简单越能从本质上概括事物的规律，于是我们期望非叶子结点到达后代 结点的平均路径总是最短，即生成的决策树的平均深度最小，这就要求在每个结点选择 较好的划分。香农的信息论表明系统的不确定性越小，信息的传递就越充分。i d 3 算法 根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值 来度量：信息增益值越大，不确定性越小。因此，算法在每个非叶子结点选择信息增益 最大的属性作为测试属性。信息增益值的计算方法如下： 设s 为一个包含s 个数据样本的集合。又类别属性可以取m 个不同的值，对应于m 个 不同的类别c f ，f l ，2 ，3 ，m ) 。假设s 。为类别c f 中的样本个数，那么要对一个给 定数据对象进行分类所需要的信息量为： ，( j 1 ，s 2 ，s 聊) = 一p 。l o g ( p ，) ( 2 - 1 ) 其中p ，就是任意一个数据对象属于类别c f 的概率；可以按s s 计算。而其中的l o g i 垂l 数 是以2 为底，因为在信息论中信息都是按位进行编码的。 设属性彳具有v 个不同值 a l ，0 2 ，a v 。可以用属性么将成0 分为v 个子集 s ，& ，s ) ， 其中，s 包含蹀合中属性彳取口，值的数据样本。如果爿被选做测试属性( 即最好的分裂属 性) ，设町为子集s 中属于c ：类别的样本数。根据由么划分成子集的熵( e n t r o p y ) 或期望信 息由下式给出： e ( 彳) ：窆华( ，) 2 圳 其中垒二二鱼项被当作匆个子集的权值，它是由所有子集中属幽取吩的样本数 s 之和除以躁合中的样本总数。e 例计算结果越小，就表示其子集划分结果越“纯”( 好) 。 而对于一个给定子集s ，它的信息为： ，( s 1 j ，s 2 j ，s 。v ) = = p l o g ( p p ) ( 2 3 ) ，- 1 其中，p 产l ，蚓，即为子集s 中任一个数据样本属于类别g 的概率。 这样利用属性么对当前分支结点进行样本集合划分所获得的信息增益为： gai n ( 4 ) = ，( s l ，s2 ，s 册) e ( 彳) ( 2 4 ) 1 2 中国石油人学( 华东) 钡_ ：学位论文 i d 3 算法将待挖掘样本集分为训练样本集和测试样本集，决策树的构建是在对训练 样本集的学习基础上产生的，决策树生成之后，再运用测试样本集对树进行后剪枝，将 分类预测准确率不符合条件的叶子结点剪去。i d 3 算法以信息增益作为测试属性选择标 准存在一个弊端：由于信息增益度量倾向于有许多值的属性，但取值较多的属性不一定 是最佳的属性。 ( 2 ) c 4 5 算法 c 4 5 算法是从i d 3 算法演变而来的，除了拥有i d 3 算法的功能外，c 4 5 算法还引 入了新的方法和增加了新的功能。例如：用信息增益率的概念；合并具有连续属性的值； 可以处理具有缺少属性值的训练样本；通过使用不同的修剪技术以避免树的过度拟合； k 交叉验证；规则的产生方式等。 c 4 5 在本质上和我们前面给出的决策树推导方法相同：在选择测试属性时，通过信 息熵公式计算出各属性的信息增益。c 4 5 采用启发式搜索来选择导致最大信息增益率 g a i n r a t i o ( a ) 的属性a 作为扩展属性进行分枝，整个算法是个递归过程，直到无法分裂 出新的结点为止。 信息增益率( g a i n r a t i o ) 方法认为应当选择信息增益好的属性，一个属性的信息增 益率用下面的公式给出： g a i n r a t i o ( 舻踹 ( 2 - 5 ) 其中，属性的信息增益g a i n ( a ) 用前面给出的公式计算，分裂信息s p l i t ( a ) 计算如下： s p l i t ( a ) = 一列i = 1 。掣， p 6 ， l ) l ) 可见，c 4 5 采用的信息增益率表示了由分枝产生的有用信息的比率，这个值越大， 分枝包含的有用信息越多。 i d 3 算法最初假定属性为离散值，但在实际环境中，很多属性值是连续的。对于连 续属性，c 4 5 处理过程如下： 根据属性的值，对数据集排序； 用不同的阈值将数据集动态的进行划分； 当输出改变时确定一个阈值； 取两个实际值中的中点作为一个阈值； 取两个划分，所有样本都在这两个划分中； 1 3 第二章数据挖掘相关技术研究 得到所有可能的阈值、增益及增益率； 在每一个属性会变为两个取值，即小于阈值或大于等于阈值。 c 4 5 处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将 最常用的值分在同一类中。具体采用概率的方法，依据属性已知的值，对属性的每一个 值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。 c 4 5 算法在选择测试属性，分割样本集上所采用的技术仍然没有脱离信息熵原理， 因此生成的决策树仍然是多叉树。如果想生成更为简洁和高效的决策树，必须对算法进 行改进。 ( 3 ) 其它算法 除了i d 3 算法和c 4 5 算法外，还有以下常用决策树分类算法： c a r t 算法。与c 4 5 算法类似，c a r t 算法也是先建树，后剪枝，但在具体实 现上二者有所不同。c a r t 算法采用一种二分递归分割技术，总是将当前样本集分割为 两个子样本集，使得生成决策树的每个非叶结点都有两个分枝，因此该算法生成的决策 树是结构简洁的二叉树。 p u b l i c 算法。该算法将剪枝融入到建树过程中，在建树阶段不生成会被剪枝 的子树，生成的决策树与对同一样本集使用后剪枝策略生成的决策树完全相同，而效率 却比后者有大幅度提高。 s l i q 算法。该算法首先将训练样本集划分成若干子集，使得每一个子集都能完 全放入主存，然后对每个子集分别构造一棵决策树，再将这些树综合，得到最终决策树 模型。 s p r i n t 算法。该算法彻底解决了主存容量的限制，能够处理其它任何算法都不 适用的超大规模训练样本集，并能有效地生成决策树。 2 2 3 决策树后剪枝方法 在一个决策树刚刚建立起来的时候，树中的许多分支都是根据训练样本集合中的异 常数据( 由于噪声