（计算机科学与技术专业论文）基于变精度粗糙集的决策树分类算法研究.pdf

r e s e a r c ho nc l a s s i f i c a t i o na l g o r i t h mo fd e c i s i o nt r e e b a s e do nv a r i a b l ep r e c i s i o nr o u g hs e t at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fd e g r e e b y y a n w e n j u a n ( c o m p u t e r s c i e n c ea n dt e c h n o l o g y ) t h e s i ss u pf e s s o rl i uzhillesls s u p e r v l s o r ： r o t e s s o r l ul l l lr j u l y 2 0 11 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文：基王变糙廑狃蕉篡数迭筮挝筮耋篡法婴塞： 。除论 文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经 公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 一 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于： 保密口在年解密后适用本授权书。 不保密口( 请在以上方框内打“ ) 导师签名2 叼场 加i ( 年7 月 中文摘要 摘要 数据挖掘自上世纪8 0 年代后期出现以来，经过二十多年的发展，现在已成为 机器学习和人工智能这两大热门领域的重要研究内容。特征属性提取、冗余属性 约简、分类精度和算法效率的提高以及相关算法针对某特定领域或背景的改进和 应用都是目前数据挖掘的研究重点。在数据挖掘的所有方法中，决策树分类算法 以其计算量小、容易理解、运行结果直观易懂等优点，受到众多学者关注。所以， 本文通过对相关领域现有算法的深入研究，针对属性约简和决策树分类存在的不 足，做出相应的改进，并选择多个u c i 数据集做对比实验，取得不错的效果。具 体来说，主要研究内容包括以下三个方面： ( 1 ) 在进行属性约简时，现有算法所采用的重要属性选择标准倾向于选择取 值个数较多的属性，而没有考虑属性取值的有效性。因此，本文提出了一种新的 重要属性选择标准，该标准使用了支持度对属性的有效取值进行统计，并将有效 取值个数和1 3 逼近精度综合作为衡量属性重要性的标准。 ( 2 ) 本文针对现有决策树分类算法存在的对噪声数据敏感和分裂属性选择困 难等不足，结合变精度粗糙集能够容忍噪声数据的优点，提出了一种新的分裂属 性选择标准，该标准从变精度明确区和信息论的角度进行综合考虑，使得改进算 法构造的决策树既能有效抵抗噪声数据又具有较高的正确分类率。另外，通过引 入置信度和支持度的概念实现在决策树构建过程中的预剪枝，可以有效降低树的 规模；将匹配度应用到对测试数据的类标号预测中，提高分类精度。 ( 3 ) 将经过属性提取、数据预处理等步骤的冠心病中医诊疗病例作为实验数 据。首先进行属性约简，挖掘出对冠心病有影响的因素；然后使用约简后的数据 构建决策树，提取决策规则，实现对冠心病病例样本的中医症型分类。 关键词：变精度粗糙集；属性约简；决策树；冠心病 英文摘要 a b s t r a c t a f t e r 觚呻y e a r so fd e v d o p m e n t ，d a t am i n i n gh a sb e c o m e ak e yr e s e a r c ht o p i ci n a r e a so fm a c h i n el e a r n i n ga n da r t i f i c i a li n t e l l i g e n c es i n c ei tf i r s ta p p e a r e di nt h el a t e8 0 s a tp r e s e n t ，f e a t u r ee x t r a c t i o n ，a t t r i b u t er e d u c t i o n ，i m p r o v e m e n to fa l g o r i t h me f f i c i e n c y a n dc l a s s i f i c a t i o na c c u r a c ya n da p p l i c a t i o no fr e l e v a n tm e t h o d si nt h es p e c i f i ca r e a sa r e t h ef o c u so fd a t am i n i n g i nm a n yd a t am i n i n gm e t h o d s ，d e c i s i o nt r e ec l a s s i f i c a t i o n m e t h o d sh a sa d v a n t a g e so f l i g h tc o m p u t a t i o n , e a s i l yu n d e r s t a n d a b l ea n di n t u i t i v er e s u l t s ， s ot h i sm e t h o dh a sb e e np a i dg r e a ta t t e n t i o n sb ym a n ys c h o l a r s t h e r e f o r e ，b a s e do n t h r o u g h d e p t hs t u d yo nt h ee x i t i n ga l g o r i t h m s ，t h i sp a p e rm a k e sc o r r e s p o n d i n g i m p r o v e m e n t sf o rd e f i c i e n c i e si na l g o r i t h m so fa t t r i b u t er e d u c t i o na n dd e c i s i o nt r e e c l a s s i f i c a t i o n a n dt h ec o m p a r i n ge x p e r i m e n t su s et h eu c id a t a s e t s ，a n dt h ei m p r o v e d a l g o r i t h m sa c h i e v eg o o dr e s u l t s s p e c i f i c a l l y , t h em a i nc o n t e n t si n c l u d et h ef o l l o w i n g t h r e ea s p e c t s ： ( 1 ) d u r i n gt h ea t t r i b u t er e d u c t i o n , c r i t e r i ao fs i g n i f i c a n t a t t r i b u t es e l e c t i o ni n e x i s t i n ga l g o r i t h m so f t e nt e n dt oc h o o s ea t t r i b u t ew h i c hh a sm o r ev a l u e s ，w i t h o u t c o n s i d e r i n gt h ev a l i d i t yo fi t t h e r e f o r e ，t h i sp a p e rp r o p o s e s an e wc r i t e r i o no f s i g n i f i c a n ta t t r i b u t es e l e c t i o n ，w h i c hi n t e g r a t e st h en u m b e ro f v a l i dv a l u e sa n d 1 3 - a p p r o x i m a t i o na c c u r a c ya sam e a s u r eo fi m p o r t a n c e ，u s i n gs u p p o r tt o c o u n tt h e n u m b e ro fv a l i dv a l u e s ( 2 ) a se x i s t i n gd e c i s i o nt r e ea l g o r i t h mh a sd i s a d v a n t a g e so fb e i n gs e n s i t i v et o n o i s ed a t aa n dd i f f i c u l tt os e l e c ts p l i t t i n gp r o p e r t y , t h i sp a p e rp r o p o s e san e wa t t r i b u t e s e l e c t i o nc r i t e r i o nw h i c hc o m b i n e sw i t hv a r i a b l ep r e c i s i o n sa d v a n t a g eo ft o l e r a t i n g n o i s ed a t a t h i sc r i t e r i o nc o n s i d e r sc o m p r e h e n s i v e l yb o t hf r o mt h ep e r s p e c t i v e so f v a r i a b l ep r e c i s i o ne x p l i c i tr e g i o na n di n f o r m a t i o nt h e o r y i tm a k e st h ei m p r o v e d a l g o r i t h mh a v eah i 曲r e s i s t a n c et on o i s ed a t aa n dc l a s s i f i c a t i o na c c u r a c y i na d d i t i o n , t h r o u g ht h ei n t r o d u c t i o no fc o n f i d e n c ea n ds u p p o r t ，t h ea l g o r i t h ma c h i e v e sp r e - p r u n i n g i n t h ep r o c e s so fd e c i s i o nt r e eb u i l d i n g , w h i c hc a nr e d u c et h es i z eo fd e c i s i o nt r e e ( 3 ) u s e st h ec o r o n a r yh e a r td i s e a s ed a t ai nt r a d i t i o n a lc h i n e s em e d i c i n et r e a t m e n t ， w h i c hg ot h r o u g ha t t r i b u t ee x t r a c t i o na n dd a t ap r e p r o c e s s i n gs t e p s ，a se x p e r i m e n t a ld a t a f i r s t ，b ym e a n so fa t t r i b u t er e d u c t i o n ，t h ef a c t o r st h a ta f f e c tc o r o n a r yh e a r td i s e a s ea le a l ld u go u t ；t h e n ，u s e st h er e d u c e dd a t at oc o n s t r u c td e c i s i o nt r c ca n de x t r a c td e c i s i o n r u l e s k e yw o r d s ：v a r i a b l ep r e c i s i o nr o u g h s e t ；a t t r i b u t er e d u c t i o n ：d e c i s i o nt r e e ： c o r o n a r yh e a r td i s e a s e 目录 目录 第1 章绪论l 1 1 论文研究背景1 1 2 国内外研究现状2 1 3 论文组织结构5 第2 章属性约简和决策树方法概述7 2 1 数据挖掘相关介绍7 2 1 1 数据挖掘的定义7 2 1 2 数据挖掘的过程8 2 1 3 数据挖掘的方法1o 2 1 4 数据挖掘的应用1 1 2 2 属性约简理论。1 3 2 2 1 属性约简概述1 3 2 2 1 核的求解1 4 2 2 2 属性选择标准15 2 3 决策树分类16 2 3 1 分裂属性选择标准1 6 2 3 2 决策树的剪枝方法1 7 2 4 本章小结。l8 第3 章基于变精度粗糙集的属性约简算法1 9 3 1 粗糙集理论一1 9 3 2 变精度粗糙集2 1 3 3 基于变精度粗糙集的属性约简改进算法。2 3 3 3 1 基于变精度粗糙集的属性选择方法2 3 3 3 2 基于变精度粗糙集的属性约简改进算法描述2 4 3 3 3 示例说明2 5 3 4 实验结果与分析2 8 3 5 本章小结。2 9 第4 章基于变精度粗糙集的决策树算法研究3 0 4 1 决策树的定义及分类过程3 0 4 2 决策树分类相关理论基础3l 4 2 1 信息论知识3 1 4 2 2 基于变精度粗糙集的分类知识3 2 4 3 基于变精度粗糙集的决策树分类改进算法3 3 4 3 1 基于v p r s 的分裂属性选择标准3 3 4 3 2 结点停止分裂条件和类别预测方法3 5 4 3 2 算法描述3 6 4 4 实验结果及分析3 8 4 5 本章小结4 3 第5 章基于变精度粗糙集的属性约简及决策树改进算法在冠心病中医临床诊疗中 的应用4 4 5 1 冠心病相关介绍。4 4 5 1 1 冠心病的危害4 4 5 1 2 中医药防治冠心病的独特优势4 4 5 1 3 智能技术应用于中医药防治冠心病临床研究的现状4 5 5 2 冠心病数据预处理4 5 5 2 1 常用数据离散方法4 6 5 2 2 冠心病数据4 7 5 3 实验结果与分析4 9 5 4 本章小结5 2 第6 章结论与展望5 3 6 1 结论5 3 6 2 展望5 3 参考文献。5 5 致谢6 0 基于变精度粗糙集的决策树分类算法研究 第1 章绪论 1 1 论文研究背景 人类进入二十一世纪，随着计算机和网络技术的深入发展、商务贸易电子化 和企事业单位办公自动化的迅速普及以及数据库技术和数据库管理系统的广泛应 用，人们从自然科学、社会活动和工程技术的各个领域生产和获取信息的能力大 大提高，从而使得当今社会面临“信息爆炸和“数据过剩”的巨大压力。对于 我们所积累的海量数据，目前的数据库管理系统仅仅可以高效的实现数据的录入、 查询、统计等基本功能，无法实现通过对数据的高层次分析后发现数据背后隐藏 的关系和规则，并进一步根据数据库中现有数据预测未来发展趋势的功能。这就 是我们通常所说的“数据爆炸但知识贫乏 的现象。在这种情况下，如何将爆炸 的信息和过剩的数据综合利用，从中提取出有用的知识和信息，成为国内外学者 广泛关注的话题，因此知识发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 和数 据挖掘( d m ，d a t am i n i n g ) 这一新型数据分析技术应运而生。知识发现这一概念 的最早提出是在1 9 8 9 年8 月召开的第1 1 届国际人工智能联合会议的专题研讨会 上，数据挖掘概念则是在晚6 年的美国计算机年会上提出。 知识发现是指通过自动处理数据库中的大量原始数据，识别出有效地、可用 的、必然的、易于理解的、富有意义的模式的过程。数据挖掘是指从数据库的大 量数据中提取隐含的、先前未知的并有潜在价值的信息和知识的过程【l 】。数据挖掘 是一个多学科交叉的研究领域，其融合了统计学、数据仓库、信息检索、机器学 习、人工智能、高性能计算以及数据可视化等最新研究成果【2 3 】。数据挖掘采用的 技术主要有神经网络、模糊集、决策树、粗糙集以及统计方法等。 粗糙集理论( r o u g hs e t s ) 在数据挖掘领域有很好的表现，已经成为数据挖掘 的常用方法之一，它为处理模糊和不确定知识提供了一种比较系统的工具，被广 泛应用于机器学习、智能控制、知识发现、辅助决策等人工智能和认知领域。变 精度粗糙集是上世纪九十年代初在p a w l a k 4 1 经典粗糙集理论的基础上通过引入阈 值( 正确分类率) 而扩展出来的，它允许一定程度的分类错误，从而提高了原 第1 章绪论 算法的抗噪声能力。知识约简和决策树分类是数据挖掘技术中的主要研究领域， 同时也是变精度粗糙集的重要研究内容。 在我们所积累的信息中，并不是所有的信息都是有用信息，我们将对决策或 分类不必要的信息称作冗余信息。冗余信息的存在，一方面会浪费大量的资源， 如处理该部分信息所用的时间、存储空间等；另一方面还会在决策过程中造成干 扰，妨碍人们做出正确的决策。所以，为节约资源和提高决策效率就需要对信息 系统进行约简，找到足以作出正确决策的最小信息系统。现有属性约简算法充分 考虑了各条件属性的分类能力以及对决策系统的影响大小，但是普遍存在倾向于 选择取值个数较多的属性的问题。 决策树算法首先需要根据训练数据集得到决策树分类器，然后用得到的分类 器预测测试数据集中的记录属于哪一类。与其他数据挖掘方法相比，决策树在构 造过程中不需要任何参数设置和领域知识，分类过程简单快速，生成的结果用树 的形式表示，直观易懂，且具有较高的分类正确率。国内外学者对决策树的研究 重点一般都集中在得到一棵节点数目尽可能少、树的深度尽可能小且分类正确率 尽可能高的决策树，尽管构造一棵最优决策树被证明是n ph a r d 问题。 鉴于属性约简和决策树分类算法的优点和实用性，本文跟踪变精度粗糙集理 论的前沿知识，通过阅读大量文献，针对信息系统属性约简和决策树构造问题， 进行了广泛、深入的研究，并在此基础上作出改进。 1 2 国内外研究现状 1 2 1 属性约简研究现状 属性约简是粗糙集理论中重要的研究内容【5 1 。一般情况下，我们数据库中所存 储的数据并不是最精简的，里面总是包含一些对决策和分类无用的冗余数据。在 信息系统中冗余数据是以冗余属性为表现形式的，所有的条件属性并不是同等重 要的，有些条件属性从信息系统中删除之后，并不影响原信息系统的分类预测能 力。属性约简就是把那些与原信息系统不相关或对其不重要的属性从中删除，这 样既使原有信息系统得到了简化，又不会对其分类能力造成影响。在对信息系统 2 基于变精度粗糙集的决策树分类算法研究 进行属性约简时，人们总是想要得出其最小约简或信息系统的所有约简，但是由 于信息系统的属性个数是不确定的，同时属性可以任意组合，所以以上两个问题 已经被证实为n p h a r d 的。对信息系统计算约简属性是进行数据挖掘和知识发现的 第一步，约简算法的效率将会直接影响后续工作的准确性，所以寻求快速高效的 约简算法仍是相关领域的重要研究课题之一。 到目前为止，国内外相关学者已经提出了许多属性约简的算法。具体来说， 如文献 6 】使用了基于区别矩阵的算法，这种算法的优点是能够求得信息系统的核 和所有的约简，且计算过程直观，易于理解。但是由于需要对逻辑公式进行化简， 所以具有计算量大、属性约简效率低的缺点。文献【7 9 所提算法首先计算出信息 系统的核属性，并以其为出发点使用属性的重要性作为启发式规则依次添加属性， 这种方法能够按照用户要求计算出最好的约简。文献 1 0 提出了一种与遗传算法相 结合的约简方法，由于遗传算法具有鲁棒性、隐含并行性和全局搜索等优点，是 一种高效的优化和搜索技术，目前已经被应用很多重要领域。文献 1 1 】介绍了基于 复合系统的约简，即利用现有较小子系统的约简结果快速求取复合系统的约简。 其中心思想是将以布尔函数为基础的化简问题转化为在集合空间中进行边界搜索 的问题，而如果子系统的约简情况已知，就会大大简化对复合系统的空间搜索。 文献 1 2 ，1 3 定义了强等价的概念，并在此基础上提出了基于扩展法则的约简。文 献 1 4 1 6 介绍了动态约简，其主要步骤是对决策表进行多次采样构建多个子表， 然后分别对每个子表计算所有约简。在所有的子表中均保持不变或近似保持不变 的约简就是最终求得的动态约简。文献 1 7 1 介绍了基于数据库操作的约简。 1 2 2 决策树分类研究现状 分类是数据挖掘领域的一个重要研究问题，它通过分析输入数据( 或称训练 数据) ，对数据所具有的特性进行总结，并归纳出每个决策类的准确描述。然后 用归纳出的类描述对所属类未知的新数据即测试数据进行分类，来预测它们分别 属于哪个类，同时得到分类正确率作为对分类算法的性能评价。由于决策树算法 构造的分类器结构简单且易于理解、分类准确率高和速度快等优点，决策树是众 3 第1 章绪论 多处理分类问题的技术中最常采用的一种。一般情况下，决策树分类算法具有很 高的分类准确率【1 8 】。 最早的决策树学习系统要追述到h u n t ，m a r t i n 和s t o n e 于1 9 6 6 年研制的一个 概念学习系统c l s t l 9 1 ( c o n c e p tl e a m i n gs y s t e m ) ，自上世纪九十年代以来，受到 众多学者追捧，被广泛应用于机器学习、知识发现等领域。在分类过程中，决策 树的构建是一个从上到下、从整体到部分的过程。这种方法在对数据进行处理时， 结果用类似于流程图的树结构进行表示，将数据按照某种特性分到树的不同的分 支，属于一个分支的数据具有某种类别归属共性。在构建的决策树中，每一个内 部结点代表的是在一个条件属性上的测试，由内部结点划分出的每一个分支代表 在条件属性上的测试输出，每个叶子结点代表数据最终归属的类。用构造好的决 策树对所属类未知的数据样本分类时，分别将样本的属性值按照从上到下的顺序 在判定树上进行测试；直到叶子结点。决策树中的每一条从根结点到叶子结点的 路径都可以提取出分类规则，如何构造分类精度高、规模( 树的结点和叶子结点) 小的决策树是国内外学者对决策树算法研究的核心内容。 所有的决策树算法中，早期的比较经典的算法包括i d 3 算法【2 0 】、c 4 5 算法【2 1 】 和c a r t 算法【2 2 】等。此后，国内外许多学者对经典算法存在的不足进行了改进或 是提出了新的决策树分类算法，大体分为以下几类。 ( 1 ) 在经典算法基础上所提出的改进算法 洪家荣等学者采用基于信息增益率的标准选择分支属性，但在构建决策树时， 一边按照选定算法往下生长，同时又将聚类引入决策树构建，将其与条件概率相 结合对树的符合条件的分支自动进行合并【2 3 】。刘小虎、李生等人在对当前结点选 择分裂属性时，并不仅限于计算该层结点中某个属性所具有的信息量，而是要从 树的两层结点进行考察【2 4 1 。钟鸣、陈文伟等针对训练数据中的样本特点，如正样 本和反样本之间的比率对选择分裂属性时造成的影响，提出了一个新的算法：i b l e 算法，每次从当前结点向下分支时都不再选择单个属性而是按照某种规则选取一 组属性，最后的预测效果要比i d 3 算法优 2 5 1 。 ( 2 ) 基于粗糙集理论或变精度粗糙集理论的决策树分类算法 4 基于变精度粗糙集的决策树分类算法研究 卫金茂在分裂属性的选择上，首次提出了将粗糙集理论引用其中【2 6 】。而后由 于变精度粗糙集理论的独特优点，如能有效提高算法的分类正确率、抵抗噪声数 据和增强泛化能力等，许多学者基于变精度粗糙集提出了构建决策树的改进算法 2 7 - 3 1 o ( 3 ) 基于多变量的决策树构造方法 构造多变量决策树的方法有：对条件属性构造线性组合，然后通过一系列的 演绎得到当前结点所需属性【3 2 】；将多变量决策树与粗糙集相结合的构造算法【3 3 】； 使用成本约束标准进行限制的多变量决策树算法【蚓等。 ( 4 ) 可动态扩展的决策树算法 这类算法适合针对较大规模数据进行决策树构建，现有的具体分类算法有 s l i q 算法【3 5 1 、s p r i n t 算法【3 6 1 、p u b l i c 算法【3 7 1 、雨林算法和b o a t 算法。 ( 5 ) 多值属性多类标决策树构造算法 前边介绍的算法都是针对单值属性单类标数据构建决策树的算法，c h e ny 等 于2 0 0 3 首次提出了针对多值属性和多类标数据的决策树分类算法m m c 3 引。但是 m m c 算法并不完美，所以后来相关学者又提出了一些改进算法如：m m d t 算法【捌、 s s c 算法 4 0 l 和s c cs p 算法【4 l 】。 ( 6 ) 其他决策树分类算法 除了上面介绍的决策树分类算法之外，还有一些其他的决策树算法如：基于 模糊集的决策树构建算法【4 2 4 ”、基于样本主成分数据的决策树分类算法1 4 4 、从多 层结点综合考虑的决策树分类算法 4 5 】、针对数据类标分层的决策树构建算法 h c l 蚓、基于特定标准对决策树符合条件的分支进行合并的算法【4 7 1 ，基于关联规 则的决策树算法【4 8 1 。 1 3 论文组织结构 全文的具体结构组织如下： 第一章论文研究背景，介绍国内外相关知识的研究现状及课题意义，明确论 文的研究内容和篇章结构。 5 第1 章绪论 第二章介绍数据挖掘的基本概念、过程和相关理论。重点是对属性约简和决 策树理论做详细的介绍。 第三章在现有属性约简理论的基础上，针对存在的一些不足做出相应改进， 该算法提出了新的评价属性重要性的标准，并选取2 0 个u c i 公用数据集进行实验， 测试该算法的约简效果。 第四章针对决策树构建过程中对噪声数据敏感和倾向于选择取值个数多的 属性作为分裂结点的不足，提出了新的决策树构造算法，该算法采用新的分裂属 性选择标准，并引入了置信度阈值和最小记录个数阈值等参数实现对决策树的预 剪枝。最后也是选取2 0 个u c i 公用数据集采用十次十倍交叉验证方法进行试验， 并将实验结果与其他四种基于变精度粗糙集的决策树分类方法进行比较，最后分 析每个参数对试验结果的影响。 第五章将本文基于属性约简和决策树分类的改进算法应用于国家自然科学 基金“分析挖掘冠心病中医诊疗临床规律的智能技术研究 中的数据。 6 基于变精度粗糙集的决策树分类算法研究 第2 章属性约简和决策树方法概述 2 1 数据挖掘相关介绍 2 1 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ，d m ) 是从大量的、不完全的、有噪声的、模糊的、随 机的、实际应用的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程【2 】。 以上定义介绍了数据挖掘的几个特征：第一，进行挖掘的数据对象必须是现 实生活中真实存在、拥有一定数量且含噪声的；第二，挖掘出的知识不是显而易 见的；第三，根据用户的兴趣度进行挖掘，挖掘出的知识可以为用户接受、理解 和运用；第四，并不需要挖掘发现十分细致准确的信息，只要可以用于支持某个 决策或业务问题。 数据挖掘是通过从数据中挖掘知识的方式，将有趣的知识、规律或高级别的 信息从数据库的相关数据集中提取出来，并从不同角度进行分析研究【3 1 。以前，数 据挖掘的对象仅限于结构化的数据，如数据库和数据仓库。但是近年来随着网络 和多媒体技术的发展，数据挖掘的对象已经逐步扩大到半结构化或非结构化的数 据，于是产生了文本挖掘、图像和视频挖掘、w e b 数据挖掘和空间数据挖掘等。 数据挖掘的飞速发展离不开三大技术的支撑：数据库技术、人工智能技术和 数理统计。图2 1 系统描述了数据挖掘技术的整个形成过程 4 9 1 ：随着近期大热的 数据库理论的深入发展，用于灵活处理大型数据的数据仓库技术应运而生；而机 器学习技术伴随着人工智能的发展取得长足进步，当这些不断发展的新兴技术结 合上传统的数理统计理论时就碰撞出了新的火花，产生了- i l 新的研究学科 数据挖掘。 7 第2 章属性约简和决策树方法概述 2 1 2 数据挖掘的过程 图2 1 数据挖掘形成过程 f i 9 2 1f o r m a t i o no fd a t am i n i n g 图2 2 数据挖掘过程示意图 f i 9 2 2d i a g r a mo ft h ed a t am i n i n gp r o c e s s 8 基于变精度粗糙集的决策树分类算法研究 数据挖掘是一套系统的工作，包括若干步骤，且每一个步骤的工作都直接影 响后续步骤的效果，无论哪个步骤达不到预期的目标，都需要再次回到前面的步 骤，重新进行调整和执行。数据挖掘过程可粗略的理解为三部曲：数据准备、数 据挖掘和结果的表达与解释( 如图2 2 ) 【剐。 下面详细说明一下数据挖掘的主要步骤： 1 明确挖掘对象 数据挖掘的第一步也是最重要的一步就是要清楚地知道挖掘目的。虽然我们 无法提前预测挖掘结果，但是我们一定要对要分析的问题和预期达到的目标有明 确的认识，不能盲目的为了挖掘而挖掘，这样往往会由于太过随意而不会成功。 从哪些数据中进行挖掘? 那么多的数据中有多少数据是对我们有用的? 数据挖掘 的终止条件是什么? 这些问题在真正进行数据挖掘前都要妥善解决。 2 准备数据 数据是挖掘的基础，数据挖掘对数据的选择有着严格的要求，因为好的数据 是保证数据挖掘取得成功的先决条件。具体来说，数据挖掘包括以下三个方面： ( 1 ) 数据选择( d a t as e l e c t i o n ) ：根据挖掘的目标和用户的需求，从众多数据 源中提取适于挖掘的数据。 ( 2 ) 数据预处理( d a t ap r o c e s s i n g ) ：选取完数据后，为提高数据的质量和保证 挖掘结果的可靠，还需要对选取好的数据进行预处理。数据预处理的目的是为了 检查数据的一致性和完整性、消除噪声、填补缺失数据和删除重复记录等，采用的 方法有数据清理、数据集成和数据规约等。 ( 3 ) 数据转换( d a t at r a n s f o r m a t i o n ) ：因为数据选择时是从不同的数据源中选 择适合数据挖掘的数据，所以挖掘之前需要将这些数据转换成统一的格式并建立 一个反映数据特征的分析模型。 3 数据挖掘 在准备好数据之后，就要根据数据的特点选择一个适合的挖掘方法对其进行 数据挖掘，得到隐含的影响决策的信息。数据挖掘的方法将在后面具体介绍。 4 结果表达和解释 9 第2 章属性约简和决策g t - ) 亨法概述 由于数据挖掘最终需要面向用户，所以数据挖掘完成后，需要对挖掘结果进 行合理表达，使人们能清楚地理解挖掘出的结果，最后将挖掘出的结果运用到决 策中。 2 1 3 数据挖掘的方法 目前，研究界普遍使用的数据挖掘方法主要包括聚类分析、演变分析、分类、 关联规则分析、偏差检测和预测【2 3 】。 ( 1 ) 关联规则分析 关联是指存在于两个或两个以上变量所取的值之间的某些规律。我们使用关 联分析的作用是为了找寻出存在于事务之间的某些依赖关系。其中，最受推崇的 关联规则挖掘算法是a g r a w a l 提出的a p r i o r ig t 去t 5 1 1 。 ( 2 ) 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模【2 1 。演变 分析可应用到股票交易中，帮助预测股票市场价格的未来走向，方便对投资做出 决策。演变分析主要分为基于时间序列的数据分析、基于相似性的数据分析和基 于序列或周期的模式匹配。 ( 3 ) 聚类分析 聚类是将类标号未知的物理或抽象对象的集合进行分组的过程，每一组中的 成员都是相似的对象组成的类。聚类分析将数据划分成若干类或簇，同一类或簇 中的对象之间的相似度都很高，而不同类或簇中的对象之间的相似度较小。聚类 技术可以分为以下几类：划分方法、层次方法、基于密度的方法、基于网格的方 法、基于模型的方法、高维数据的方法和基于约束的聚类等【2 1 。 ( 4 ) 分类 分类的过程是一个构建分类模型的过程，通过构建的分类模型可以将数据库 中的任一实例映射到某个给定的类别。数据分类的过程包括两个步骤：第一步， 学习步，或称训练阶段，该阶段主要是通过分析或从给定训练集数据中学习进行 构造分类器；第二步，测试步，使用上一阶段构造的分类器对测试数据进行分类， 1 0 基于变精度粗糙集的决策树分类算法研究 并统计该分类器的准确率。其中，测试数据是随机选取的一组独立于训练集的数 据。 常用的分类方法主要有决策树分类器、贝叶斯分类器、贝叶斯信念网络、基 于规则的分类器、神经网络、遗传算法、k 最近邻分类器、基于案例的推理、粗 糙集和模糊逻辑技术等。 ( 5 ) 预测 通过分析历史数据发现隐藏其中的数据变化规律和趋势，然后建立某种模型 用来预测未来数据的特征，这就是预测的过程。常用的预测方法包括线性回归、 非线性回归和其他一些基于回归的模型。 ( 6 ) 偏差检测 偏差是指数据集中一些潜在的特例数据，如分类问题中的反常噪声实例、进 行预测时存在于观测实际结果和模型预测值之间的偏差、与提取的规则相违背的 特例等。偏差检测所要做的工作是统计观测的实际值与参照值之间存在的偏差， 其中可以选取模型的预测值、专家提供的标准或者其他的观测值作为参照标准。 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、 机器学习、可视化和信息科学【2 1 。 2 1 4 数据挖掘的应用 近年来，数据收集和存储技术都取得了很大的进步，这使得我们现在可以以 比以往更高的速度和更低的代价来收集科学数据，最后导致在各个领域都积累了 海量的数据，这些数据中有包含了丰富时间和空间信息的高维数据、流数据和异 构数据。新形势下，数据挖掘在新兴的科技领域中将会发挥更大的作用和潜力。 下面介绍一下数据挖掘在各个领域中的应用： ( 1 ) 在金融领域的应用 基于金融领域的数据挖掘是指通过从银行和金融机构积累的大量数据信息中 进行分析挖掘，得到用户感兴趣的信息，从而帮助金融企业和金融监管部门对整 个金融市场进行监管和在需要做出决策时为其提供决策依据。由于银行和金融机 构提供业务的特殊性，其收集的数据通常都比较完整、可靠、连续，并且具有很 第2 章属性约简和决策树方法概述 高的质量，这样在对数据进行预处理时就大大节省了工作量，进一步优化了挖掘 过程。下面介绍几种数据挖掘在金融领域的典型应用： a ) 为多维数据分析和数据挖掘设计和构造数据仓库：根据用户的需求，使用 多维数据分析方法分析数据的一般性质，为银行和金融机构积累的大量数据构造数 据仓库，并提供与用户需求相符的功能模块。 b ) 分析客户的贷款偿还能力和评估客户的信用等级：这个应用对银行等金融 机构的业务开展非常重要。在实际生活中，影响客户贷款偿还履行和顾客信用等 级评定的因素有很多，且这些因素对其影响程度各不相同。我们可以选择数据挖 掘中的属性选择或者属性相关评定方法，来对影响因素的重要性进行量化，从而 识别出重要因素，剔除不重要或不相关因素，简化信息系统，使决策变得简单明 了。 c ) 洗黑钱和其他一些金融犯罪案件的侦破：每个人在银行和金融机构进行的 交易都有一个数据库中的数据与之对应，如果我们把银行等金融机构的数据库中 的数据和一些犯罪历史数据库中的信息集成起来，通过使用链接分析工具、分类 工具、聚类工具、离群点分析工具等一系列数据分析工具检测异常就有可能发现 一些和侦破工作有关的信息。 除了以上详细介绍的，数据挖掘在金融领域还有其他一些应用，如针对定向 销售的客户进行分类和聚类、应用到股票交易中预测股票交易规律等。 ( 2 ) 在零售行业的应用 现在每个商店都是商品零售网点，顾客在任何一个网点都可以联机的购买任 意商品，这样商品的销售记录、顾客的购买记录、消费和服务等记录都被一一保 存在数据库中。再加上基于w e b 或电子商务的商业活动日益方便，网络购物已成 为一种流行，使得零售行业堆积的数据记录进一步膨胀。 这种形势下急需数据挖掘技术应用在零售行业中，从零售行业积累的数据中 进行分析挖掘，发现顾客购买行为、识别顾客购买需求和趋势、分析促销活动效 果以及挖掘顾客购买物品之间的关联信息，以方便更准确的进行产品推荐和定向 1 2 基于变精度粗糙集的决策树分类算法研究 营销，维护更高的顾客忠诚度和满意度，增加商品的销售额，同时尽可能的减少 成本，提高商业利润。 ( 3 ) 在电信领域的应用 近年来，随着电信与计算机网络、因特网、其他一些通信与计算工具的融合， 电信提供的服务已经从单纯的通话服务扩展为涵盖传真、图像传输、电子邮件和 网络数据传输等的一系列综合服务。此外，加上政府对电信业的扶持和技术的更 新换代，电信市场将会蓬勃发展。 有发展就会有竞争，有竞争就会有新的要求，才会有更高层次的发展，蓬勃 发展的电信市场迫切呼唤数据挖掘技术的应用，以便帮助企业更好的理解商业行 为、制定更合理的收费标准、提高服务标准和服务质量、减少客户资源流失、识 别欺诈消费并提前防范、为客户提供分层服务和优化电信网络，进一步节约成本 和资源，增加企业利润。 ( 4 ) 在其他一些领域的应用：技术的不断发展催生了很多新的产业，也带来了 许多新的问题，于是数据挖掘技术又被应用到这些新的领域来解决特定问题。比 如过去十年基因组学、蛋白质学、功能基因组学和生物医学的研究取得迅猛发展， 促使生物学数据挖掘成为新兴生物信息学研究领域中不可或缺的组成部分；随着 互联网应用的广泛普及，各种对网络的入侵和攻击严重侵害人们隐私，危害民众 财产安全，妨碍公众正常生活，所以入侵检测被视为网络管理的关键组成部分， 以识别入侵检测为目的的数据挖掘算法也得到人们的相应重视。 2 2 属性约简理论 2 2 1 属性约简概述 人们在进