（计算机软件与理论专业论文）基于粗糙集理论的数据挖掘算法的研究.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho nr o u g hs e tt h e o r yb a s e d d a t am i n i n g a l g o r i t h m c a n d i d a t e ：f e n gw e i j u n s u p e r v i s o r ：a s s o c i a t ep r o f iq ul i p i n g a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e rs o f t w a r ea n dt h e o r y d a t eo fs u b m i s s i o n ：d e c e m b e r ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。一 作者( 签字) ：沟列干 日期： 2 0 o 年弓月侈日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可切在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：马为军导师( 签字) ：、功钟 日期： 2 。o 年弓月岁日劲f 口年弓月d 日 哈尔滨工程大学硕十学位论文 摘要 随着网络技术和信息技术的不断进步，数据挖掘引起了人们的广泛关注， 传统的信息处理技术越来越不能很好地满足实际应用的需要。因此，人们迫 切需要具有更高效率和更强能力的信息处理技术。 p a w l a k 提出的粗糙集理论是一种全新的处理模糊性、不确定性问题的数 学工具，它无需提供数据集合之外的任何先验信息，而是利用集合上的等价 关系对知识的不确定程度进行度量，这使得粗糙集理论在数据挖掘中具有更 加明显的优越性。将粗糙集理论应用到数据挖掘中，需要经过数据预处理、 求核属性、属性约简、规则生成等几个步骤。本文以粗糙集理论在数据挖掘 过程中的步骤为线索，主要对连续属性离散化、求取决策表的核值属性、决 策表的属性约简等问题进行了深入的研究。本文的主要创新工作包括： 提出一种基于粗糙集理论和o p t i c s 算法相结合的连续属性离散化算 法。运用粗糙集理论处理决策表时，要求决策表中的值用离散数据表示。因 此，在深入分析和研究几种离散化算法优缺点的基础上，提出一种基于粗糙 集理论和o p t i c s 算法相结合的连续属性离散化算法。该算法是以粗糙集理 论中的依赖度作为评价机制，更好的保持了条件属性和决策属性的不可分辨 关系，该算法也是一种全局的离散化算法，离散化后的信息系统更具有整体 性。通过实验验证，该算法能够得到理想的离散化结果。 提出一种改进的基于属性重要性的启发式约简算法。通过研究发现，基 于属性重要性和基于信息熵作为启发信息的属性约简算法都是不完备的。综 合考虑这两种启发信息，以粗糙集理论为依据，以属性重要性为主要标准， 信息熵为辅助标准，提出一种改进的基于属性重要性的启发式约简算法。通 过实验验证，该算法是个更加完备、更加合理的算法。 关键词：粗糙集；数据挖掘；连续属性离散化；属性约简 哈尔滨t 程大学硕士学何论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h en e t w o r kt e c h n o l o g ya n di n f o r m a t i o nt e c h n o l o g y , w i d e s p r e a da t t e n t i o nh a sb e e np a i dt od a t am i n i n g t h et r a d i t i o n a li n f o r m a t i o n p r o c e s s i n gt e c h n o l o g yi si n c r e a s i n g l yu n a b l et op r o p e r l ym e e tt h en e e d s o f p r a c t i c a la p p l i c a t i o n s t h e r e f o r e ，i t i sa n u r g e n tn e e d t ou s ei n f o r m a t i o n p r o c e s s i n gt e c h n o l o g yw i t hm o r ee f f i c i e n c ya n da b i l i t y p a w l a kp r o p o s e dr o u g hs e tt h e o r ya san e wm a t h e m a t i c a lt o o lt op r o c e s s v a g u ea n du n c e r t a i nk n o w l e d g e t h e r ei sn on e e dt op r o v i d ea n yp r i o ri n f o r m a t i o n w h i c hi sn o ti nt h ed a t as e t t h ee q u i v a l e n tr e l a t i o no nt h es e ti su s e dt om e a s u r e t h ek n o w l e d g eu n c e r t a i n t ya n db yt h i sw a yt h er o u g hs e tt h e o r yh a sm o r eo b v i o u s a d v a n t a g e s i nd a t a m i n i n g t h er o u g hs e tt h e o r yi sa p p l i e d t od a t am i n i n g i n c l u d i n gd a t ap r e p r o c e s s i n g , f m d i n gc o r ea t t r i b u t e s ，a t t r i b u t er e d u c t i o n ，r u l e g e n e r a t i o na n ds oo n i nt h i sp a p e r , b a s e do nr o u g hs e tt h e o r yi nd a t am i n i n g p r o c e s ss t e p s ，d i s p e r s i n gc o n t i n u o u sa t t r i b u t e s ，f m d i n gc o r ea t t r i b u t e so fd e c i s i o n t a b l ea n dd e c i s i o nt a b l ea t t r i b u t er e d u c t i o na r em a i n l ya n a l y z e da n dr e s e a r c h e d m a j o r i n i t i a t i v e sa n di n n o v a t i o n si n c l u d e ： t h ea l g o r i t h mc o m b i n i n gr o u g hs e tt h e o r ya n dt h eo p t i c sa l g o r i t h mi s p r o p o s e db yd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e s w h e nr o u g hs e tt h e o r yd e a l s w i t hd e c i s i o nt a b l e ，d a t ai sr e p r e s e n t e db yd i s c r e t ev a l u e s t h e r e f o r e ，w i t hd e e p l y r e s e a r c ha n da n a l y s i so ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fs e v e r a ld i s c r e t e a l g o r i t h m s ，t h ea l g o r i t h mc o m b i n i n gr o u g hs e tt h e o r ya n dt h eo p t i c sa l g o r i t h m i sp r o p o s e db yd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e s t h ee v a l u a t i o nm e c h a n i s m i sb a s e do nd e p e n d e n c eo fr o u g hs e t ，w h i c hm a i n t a i n sc o n d i t i o na t t r i b u t e sa n d d e c i s i o na t t r i b u t eo fi n d i s c e m i b i l i t yr e l a t i o n t h ea l g o r i t h mi sa l s oag l o b a l d i s c r e t i z a t i o na l g o r i t h ma n dt h ei n f o r m a t i o ns y s t e mh a st h em o r eg e n e r a l i z a t i o n a f t e rd i s c r e t i z a t i o n e x p e r i m e n ts h o w st h a tt h ea l g o r i t h mc a na c h i e v eb e t t e r r e s u l t so fd i s c r e t i z a t i o n h e u r i s t i ca t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nt h ei m p o r t a n c eo fa t t r i b u t ei s q l d e v e l o p e d t h r o u g h t h es t u d y , t h ea t t r i b u t e r e d u c t i o na l g o r i t h m sb a s e d o n a t t r i b u t ei m p o r t a n c ea n di n f o r m a t i o ne n t r o p ya st h eh e u r i s t i ci n f o r m a t i o n a l en o t c o m d l e t e c o m p r e h e n s i v ec o n s i d e r a t i o no ft h e s e t w oe r d i g h t e r r i n gi n f o r m a t i o n ， h e u r i s t i c 砌b u t er e d u c t i o na l g o r i t h mb a s e d o nt h ei m p o r t a n c eo fa t t r i b u t el s d e v e l o d e d t h ea l g o r i t h mu s er o u g hs e tt h e o r ya s t h eb a s i s ，t h ei m p o r t a n t eo f a t t r i b u t ea st h em a i nc r i t e r i o na n dt h ei n f o r m a t i o ne n t r o p y o ft h es e c o n d a r y s t a n d a r d s e x p e r i m e n t s s h o wt h a tt h e a l g o r i t h m i sm o r ec o m p l e t e ，m o r e r e a s o n a b l em e t h o d k e yw o r d s ：r o u g hs e t ；d a t am i n i n g ；d i s c r e t i z a t i o n o fc o n t i n u o u s 撒i b u t e s ； a t t r i b u t er e d u c t i o n 缸l ， h 哈尔滨工程大学硕十学位论文 目录 第l 章绪论1 1 1课题研究的目的和意义1 1 2国内外研究现状2 1 3 数据挖掘的应用3 1 3 1 数据挖掘的典型应用3 1 3 2 粗糙集理论在数据挖掘中的应用4 1 4 数据挖掘过程”5 1 4 1 数据挖掘的一般过程5 1 4 2 基于粗糙集理论的数据挖掘过程7 1 5 论文背景及研究内容7 1 6 论文的组织结构9 第2 章粗糙集理论及相关技术1 0 2 1 知识与知识库：1 0 2 2 粗糙集的近似1 1 2 3知识约简15 2 4 知识的依赖性1 7 2 5 信息系统与决策表1 9 2 6 可辨识矩阵2 1 2 7 粗糙集理论的信息论观点描述2 2 2 8相关技术2 4 2 8 1o p t i c s 算法的相关定义”2 5 2 8 2o p t i c s 算法描述”2 6 2 8 3 可达图2 6 2 9 本章小结2 7 第3 章连续属性离散化2 9 3 1离散化问题的分类及原则：”2 9 3 2 离散化问题的描述3 0 3 3 离散化算法介绍与分析3 1 _ i 哈尔滨丁程大学硕士学位论文 3 3 1 等距离划分方法。3 2 3 3 2 等频率划分方法3 2 3 3 3n a i v es c a l e r 离散化算法3 2 3 3 4 布尔逻辑和粗糙集理论相结合的离散化算法3 3 3 4 基于o p t i c s 聚类算法的连续属性离散化算法3 3 3 4 1算法思想3 4 3 4 2 基于粗糙集理论和o p t i c s 算法的连续属性离散化算法3 5 3 4 3 算法分析3 6 3 4 4 实验分析3 7 3 5本章小结3 9 第4 章属性约简4 0 4 1几种典型的属性约简算法4 0 4 2 属性约简的启发式算法4 l 4 2 1基于属性频率函数的启发式约简算法4 1 4 2 2 基于互信息的启发式约简算法m i b a r k 算法4 l 4 2 3 基于属性重要性的启发式属性约简算法4 2 4 3改进的基于属性重要性的启发式属性约简算法4 4 4 3 1决策表核属性集合的计算方法4 4 4 3 2 改进的基于属性重要性的启发式属性约简算法4 6 4 3 3 算法分析4 8 4 3 4 实验分析4 9 4 4 本章小结51 结论”5 2 参考文献5 4 攻读硕士位期间发表的论文和取得的科研成果5 8 致谢5 9 哈尔滨工程大学硕士学位论文 第l 章绪论 1 1 课题研究的目的和意义 如今，随着信息技术、网络技术和其它相关技术的高速发展，越来越多 的数据集合在企业、科研部门、政府机构的计算机上逐渐累积起来。很多企 业和机构开始着手进行信息化项目建设，在扩大生产经营和提高生产效率的 同时，也积累了大量有关顾客、生产模式、营销、管理等方面的宝贵资料； 在广泛实施电子政务和电子商务的今天，政府机构的数据也需要进行信息化 改造；科研部门更是收集了大量有实用价值的科学研究数据，试图从它们当 中发现自然界和社会各界的规则。可是，大量数据集合的迅猛积累，很快就 超出了只靠手工就能够进行分析和处理的规模。在如此庞大的数据量面前， 很多机构和企业陷入了“资源丰富而知识匮乏”的境地。 面对“资源丰富而知识匮乏”的局面，人们渴望得到一种全新的、更加 符合人们需要的数据分析和处理工具，应用这种工具来完成分析和处理现有 数据集的任务。在这种迫切要求的情况下，产生了“数据挖掘”这门技术。 有关这方面的工作已经取得了很多研究成果，各类相关软件的应用极大地推 动了人们分析数据和处理数据的能力，并在数据分析和决策领域提供了有效 的手段，极大提高了工作效率，许多学者认为数据挖掘还不是一个完善的学 科，数据可扩展性、与数据库系统的兼容性，以及可用性和准确性都有待改 进【2 】。 数据挖掘是多种技术的集成，统计学、决策支持系统、数据库管理和数 据仓库、机器学习、可视化和并行处理技术都是相互影响和支持数据挖掘工 具的工具。行之有效的数据挖掘方法对于人们分析数据、处理数据具有相当 重要的意义。目前，数据挖掘中常用到的挖掘方法有：聚类分析方法、规则 归纳法、模糊集方法、支持向量机、决策树方法、粗糙集方法等【3 】。 哈尔滨t 程大学硕+ 学位论文 1 2 国内外研究现状 著名数学家z p a w l a k t 1 在1 9 8 2 年的时候提出了粗糙集这门经典理论，该 理论刚被提出的时候，并没有引起国际计算机学界和数学界的广泛重视，由 于受到语言的限制，当时的研究也只有波兰等几个东欧国家。到了9 0 年代， 数据仓库技术和数据挖掘技术引起了广大学者和专家们的重视，在这种前提 下，粗糙集理论及其方法才被人们认识并迅速发展起来。 9 0 年代初，z p a w l a k 发表的( ( r o u g hs e t ：t h e o r e t i c a la s p e c t so fr e a s o n i n g a b o u td a t a ) ) 是粗糙集理论发展进程中的一个里程碑【5 】，它代表了对粗糙集理 论的研究已经进入新的阶段。越来越多的学者和专家开始从事粗糙集的理论 研究和具体应用的工作。开发的研究成果也受到人们的广泛关注。1 9 9 2 年和 1 9 9 3 年分别在波兰和加拿大召开了两届国际粗糙集理论交流会，因为当时正 值知识发现成为热门研究方向，许多国际著名学者和专家参加了会议，重点 讨论了粗糙集理论的研究与应用工作，他们提出了许多有实用价值的数据挖 掘方法与应用系统。从那时候开始，粗糙集理论与方法就广泛的应用到数据 挖掘领域中。9 0 年代末，亚洲地区和我国对粗糙集理论及其应用的研究也有 了较快的进展【6 】。 近些年来，粗糙集理论已经广泛地应用于医疗诊断、粗糙控制、软件工 程、图像处理、数据分析、模式识别、化学材料等领域。国际上已经研究开 发了一些基于粗糙集理论的数据挖掘系统，这些系统已经应用到各个领域， 并且取得了较好的效果。例如，r e g i n a 大学利用粗糙集理论研制的k d d r 系统，该系统已经被广泛应用于城市规划、卫生等行业，该系统成功的提供 了辅助决策方法【7 1 。 就目前国际研究状况而言，理论研究主要有粗糙集与概率论和模糊集结 合、粗糙集理论同遗传算法等其它人工智能技术的结合、粗糙控制等方面。 另外，粗糙集理论模型的扩展也是一个研究的热门课题。在实际运用方面， 学者和专家们非常关注将粗糙集理论应用于信息与通信、医疗卫生、模式识 2 k 鱼 哈尔滨丁程大学硕十学位论文 别等领域。 国内关于粗糙集理论与方法的研究落后于欧美一些国家，直到9 0 年代后 期，一些高校和科研所才开始进行研究，可是，进展速度却很明显。例如， 南京大学、清华大学、中科院等高校或者研究所都进行了全面的研究并取得 了一定的研究成果。 1 3 数据挖掘的应用 1 3 1 数据挖掘的典型应用 数据挖掘的迅速发展是由不断更新的实际应用所推动的，这些应用需要 新的技术支持。下面简要介绍一些数据挖掘的典型应用【1 】。 ( 1 ) 顾客分群。顾客细分或顾客分群是现代经营的基础。通过聚类分析 的方法，对顾客进行分类，获得各个顾客群体不同的习惯和特点，从而达到 提高产品销量的目的。 、 ( 2 ) 贡献价值分析。不同的顾客对企业的贡献差别较大，少数顾客的贡 献要比多数的顾客要高出许多。根据其贡献价值的不同进行分类，进而发现 贡献价值高的顾客，把有限的资源投入到这样的顾客身上。 ( 3 ) 有针对性服务。通过对每个人的资料进行分析和比较，从中发现他 们与众不同的方面，就可以有针对性地为他们提供服务。 ( 4 ) 构建模式。通过分析商品和顾客的模式，能够发现他们之间的搭配 销售模式。利用这些模型，能够设计出更好的营销模型，不断提高产品销售 数量。 ( 5 ) 孤立点发现。对大量的数据集合进行分析，找出其中的孤立点。 ( 6 ) 提高效率和改进流程。通过对业务资料的分析处理，能够发现更加 完备的方法，进而达到提高工作效率或改善业务流程的目的。 ( 7 ) 预报。通过对数据集中未来趋势的分析和预测，对可能将要发生的 事件如地震、火山喷发等提前进行预报，以便减少人们的经济损失。 3 哈尔滨工程大学硕士学位论文 ( 8 ) 科学知识发现。通过对大量科学数据和企业信息进行分析处和理， 可以发现自然界或社会各界的规律。 1 3 2 粗糙集理论在数据挖掘中的应用 粗糙集理论正从理论研究阶段逐步转向实际应用阶段转变，目前，在很 多行业和领域取得了丰硕的研究成果。 ( 1 ) 证券预测。g o l a n 等结合粗糙集的方法总结了历史资料，从中发现 了经济规律与证券价格波动的关系，为人们能够准确的投资证券市场提供了 帮助嗍。 ( 2 ) 模式识别。应用粗糙集理论和方法可以解决手写字符识别的难题， 有效地提高了识别的准确率【9 】。 ( 3 ) 灾难预报。t e g h e m 等采用粗糙集方法分析了地壳活动与是否有地 震发生的相互关系，这也是预报地震的一种新方法【o 】。 ( 4 ) 辅助谈判。d e j a 根据粗糙集理论构建了可以反映巴勒斯坦、叙利 亚等六国关于中东和平问题各自立场的谈判模式，为谈判的成功举行提供了 辅助决策方法】。 ( 5 ) 知识发现。粗糙集理论和方法是一种有实用价值的数据挖掘方法， 应用粗糙集理论可以从数据库中发现对人们有用的知识【1 2 】。 ( 6 ) 简化控制方法。在整个控制过程当中，把具有代表性的实例以及它 所采取的控制方法都保存下来，然后应用粗糙集理论和方法对其进行约简。 粗糙控制的优点是简洁方便、易于实现。因此，在要求不高的情况下，可以 采取这种控制方法【1 3 】。 ( 7 ) 医疗诊断预测。人们根据粗糙集理论和方法，在分析历史病例的基 础上总结出诊断规则，应用这些诊断规则来辅助医生对新的病例进行诊断。 应用这些规则之后，诊断的准确率则有了明显的提古【】。 ( 8 ) 构造专家系统。应用粗糙集理论和方法在数据库中提取规则，为人 们创建知识库提供了一种全新的手段【1 5 】。 4 哈尔滨t 程大学硕士学位论文 i i 暑i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 苗i i i - i i ( 9 ) 简化神经网络数据集。神经网络的缺陷是训练时间过长，它是制约 神经网络向实际应用转变的主要原因。j e l o n e k 等应用粗糙集方法化简神经网 络训练样本数据集，删除了冗余的数据，这样，在提高训练速度的同时，也 取得了更好的结果t 6 1 。 ( 1 0 ) 获取决策规则。采用粗糙集方法获取的决策规则是在分析历史数 据的基础上得出来的【1 7 l 。 粗糙集理论的应用还涉及到很多领域，例如，近似推理方法、结构预测 建模、软件工程测试、数据分析处理、图象压缩处理、选票结果分析、化学 材料结构分析等1 1 5 , 1 9 , z 0 。 1 4 数据挖掘过程 1 4 1 数据挖掘的一般过程 图1 1 数据挖掘过程图 5 哈尔滨丁稃大学硕士学位论文 i i i i i i i i i i i 宣i i 宣i i 宣i i 萱i i i i i i i i i i i i i i i i i i i i i i i i i i i _ i i i _ _ _ _ _ _ _ - - 一 数据挖掘过程并不仅仅是一个数据一模型一结果的套用公式的过程，而 是一个不断循环、逐渐完善的过程。一般的数据挖掘过程需要经过业务理解、 数据理解、数据预处理、建模、评估、部署等几个步骤【l 】。 在图1 1 中，最外层的循环反映了数据挖掘本质上是一个循环往复的过 程。数据挖掘并不是循环一次，就结束了数据挖掘过程。随着时间、数据的 变化，原有的挖掘模型可能不适应这种变化，而需要不断更新数据挖掘过程。 因此，数据挖掘过程本质上是一个循环往复、逐步求精的过程【1 】。 图1 1 的内部反映了在一个数据挖掘过程中各个步骤之间的关系。我们 可以发现，各个步骤之间不存在严格意义上的次序关系，需要根据一个步骤 结果的好坏决定回溯上一步骤或者继续下一步骤。下面简要的介绍一下数据 挖掘过程的各个步骤【。 ( 1 ) 业务理解。业务理解就是熟悉将要进行数据挖掘的业务，确定业务 所要达到的标准，最后将业务上的问题转化为数据挖掘的问题。 ( 2 ) 数据理解。数据理解就要收集相关的数据资料，并且对数据进行核 实，以保证数据的质量。假如在这一步骤中遇到有关数据的问题，则应回溯 到开始步骤重新对业务进行理解。 ( 3 ) 数据预处理。这一步骤是提供用于建模的数据集。它包括对实验数 据的选择、对缺失数据进行补充、对连续型的数据进行离散化处理等子任务。 ( 4 ) 建模。选择合适的算法及算法参数。一般来讲，对于某一种数据挖 掘任务而言，可以采用多种不同的数据挖掘算法。算法选定之后进行建模， 在建模的过程中，要不断地调整算法的参数，之后，还要对模型进行测试。 ( 5 ) 评估。评估的方法有很多种，因应用类型的差别而不同，我们可以 根据实际应用进行验证评估。如果结果没有达到预期目的，则应回溯到以前 的步骤，否则继续进行下一个步骤。 ( 6 ) 部署。完成了建模、评估，并不等于已经完成了任务。在实际业务 工作中，需要将生成的结果应用到一个业务工作中，并将应用的结果与生成 的结果进行对比，以便对模型进行改进。 6 1 5 论文背景及研究内容 z p a w l a k 提出的粗糙集理论是一种具有实用价值的数学工具，它能较好 的处理不完整性、不精确性问题，它具有很多自己的特色和优点。粗糙集理 论和方法的基础是属性之间的不可分辨关系。它不同于模糊集、概率论、统 计学等其它的传统数学分析工具，粗糙集理论和方法在处理具有不完备性、 不确定性的数据时，具有非常明显的优越性，它通过上近似集合、下近似集 合、约简等概念来描述和表达信息系统的不完备性和不准确性，它的表示方 7 哈尔滨工程大学硕十学位论文 法更加符合人们实际需要。处理不确定信息常用的数学分析工具，如模糊集 和概率论都需要先验知识，并且这些信息都存在人工参与的因素，而且都不 容易通过计算得到。然而，粗糙集理论对数据集合的分析和处理不需要附加 任何外界信息和先验知识，所有的分析和处理工作都是完全基于数据对象本 身独立完成的。因此，消除了主观人为因素的影响。正是因为粗糙集理论的 这一独特优点，使其在数据挖掘领域中发展更加迅速。但是作为一种崭新的 事物，粗糙集理论在实际应用中还有很多地方值得深入研究讨论【2 l 】。 粗糙集理论和方法是一种执行效率较高的的数据挖掘方法，当前，就其 理论研究而言，主要有三个方面需要进一步深化和研究： 第一，粗糙集理论同其它数据挖掘方法进行结合的问题。例如，粗糙集 理论和聚类分析方法、遗传算法等方法进行结合，在降低算法复杂度的同时， 可以提高算法的效率。 第二，至今还没有高效、准确的属性约简算法，这是制约粗糙集理论向 实际应用转换的主要方面。因此，属性约简算法迫切需要人们进行深入的研 究。 第三，粗糙集理论的缺点是只能处理离散型的数据，而不能处理连续型 的数据，为了保持原有信息系统的分辨能力不变，需要采用满足粗糙集理论 这一特殊要求的离散化算法1 2 2 】。 根据以上三方面需要研究的问题，本文主要应用粗糙集理论，针对连续 属性离散化和属性约简两个方面的问题进行了深入的分析和研究。 本文提出一种基于粗糙集理论和o p t i c s 算法相结合的连续属性离散化 算法，这个算法兼顾决策表的整体性质，因此，它是一种全局性的离散化方 法，对决策表进行离散化后，能够得到更加理想的结果；本文对约简的启发 式算法也进行了深入研究，经过研究发现，这些算法都是不完备的。综合考 虑属性重要度和信息熵这两种标准，我们以粗糙集理论为依据，以属性重要 度为主要标准，信息熵为辅助标准，提出一种改进的启发式约简算法。改进 后的算法在处理大量的，甚至海量的科学数据时，更能充分显示其优越性， 哈尔滨工程大学硕士学位论文 它不会使大量的有用的数据丢失掉，并且可以更准确的求取属性的最小约简。 改进后的约简算法与原来的算法进行比较，它是一种更加有效的属性约简算 法。 1 6 论文的组织结构 本文是以粗糙集理论为基础，以它在数据挖掘中的应用而进行研究的， 阐述了数据挖掘的基本知识和粗糙集理论的基本概念，提出两种有关粗糙集 理论的数据挖掘算法，下面是本文的结构安排： 第一章：绪论。分析了论文研究的背景、目的及意义；阐述了数据挖掘 的一般过程和基于粗糙集理论的数据挖掘过程。 第二章：粗糙集理论及相关技术。介绍了粗糙集的上近似集合、下近似 集合、核等重要概念；接着分析了信息系统和决策表及可辨识矩阵；然后， 阐述了粗糙集理论的信息论观点描述；最后分析了一种聚类分析算法 一o p t i c s 算法。 第三章：连续属性离散化。本章是论文的主体部分，介绍了离散化问题 的分类和原则以及离散化问题的描述，接着深入分析和研究了几种离散化算 法的优缺点，最后提出一种粗糙集和o p t i c s 算法相结合的离散化算法，通 过对决策表进行离散化处理，该算法能够得到理想的离散化结果。 第四章：属性约简。本章同样是论文的主体部分，经过研究发现，有些 约简算法是不完备的。综合考虑属性重要度和信息熵这两种标准，以粗糙集 理论为依据，以属性重要度为主要标准，信息熵为辅助标准，提出一种改进 的启发式约简算法。通过复杂度分析和实验验证，该算法是个更加完备、更 加合理的算法。 结论：对提出的两种算法进行了总结，对今后的主要研究工作进行了规 划。 9 f ，j = l ，2 ，以；u x , = u 。 i = 1 定义2 2 t z ，l 令r 是u 上的一个等价关系，叫尺表示月的所有等价类构成 的集合，【x 1 月表示为包含元素x u 的r 等价类。因此，一个知识库就是一个 等价关系系统k = ( u ，r ) ，u 不是空集，是由对象组成的论域，尺是u 上的 一个等价关系族。 如果p r ，并且p 垂，那么n p 也是一个等价关系，称为p 上的不可 分辨关系，记为i n d ( p 】，下列公式成立： m 椰1 = n ( 2 1 ) 艇p u i n d ( p 1 是与等价类关系族p 有关联的知识，称为k 中关于u 的p 基本 知识1 2 3 。 换言之，如果k = ( u ，r ) 是一个知识库，那么i n d ( k ) 就是k 中所有等价 关系的族，即 加d ( k ) = i d ( 尸) l 西p 只) 瞄】。 为了更好的理解这些定义，我们通过下面的例子进行说明： 现有由8 个工具模型组成的集合u = ，x 2 ，x 8 ) ，并且这些模型有绿、 黑、褐三种颜色；按形状分，有矩形、椭圆形、菱形；按重量分，有较轻的， 1 0 哈尔滨工程大学硕士学位论文 有较重的。因此，这些工具模型都可以用颜色、形状、重量这些知识来进行 区分。如果根据某一属性辨别这些工具模型，就可以按照颜色、形状、重量 分类。 按颜色分类，绿色： 五，j c 3 ，x 7 ) ；褐色： x 2 ，_ ) ；黑色： 毛，魄) ； 按形状分类，椭圆形： 五，墨) ；矩形： 恐，) ；菱形： x 3 ，x 4 。而，x s ) ； 按重量分类，较重： x 2 ，为，黾】；较轻： 五，恐，_ ，x 5 ，x 6 ) a 换种说法，我们定义三个等价关系：颜色置，形状r 、重量足，通过上 面这些分类，就能够产生下面三个等价类： u r , - - - x , ，恐，而) ， 恐，五) ， 恐，黾) ) ； 叫恐= 五，恐) ， 而，讫) ， 屯，x 4 ，x - ，) ) ； 叫b - x 2 ，而，黾) ， 五，恐，_ ，恐，x 。) ) 。 这些等价类是由知识库k = ( u ， 蜀，r ，咫) ) 中的初等概念，也称为初等范 畴组成的。 初等范畴的交集就是基本范畴，例如： 西，恐，x - ) n 而，x 4 ，而，黾) = 毛，而) ， 恐，五】n 屯，旄) = 恐) ， 墨，黾) n 而，_ ，而，黾) = 黾) 。 它们分别表示 置，是) 的基本范畴，即：绿色菱形，褐色矩形，黑色菱形。 下列集合： 五，x s ，而) n 而，x 4 ，x 7 ，黾) n 恐，而，黾) - x 7 ) ， 恐，_ ) n 屯，x 。) n j c 2 ，x 7 ，黾) = 恐) ， ，x 6 ，黾) n 恐，x 4 ，为，) n 恐，x - ，黾) = 黾) 。 它们分别表示 尺，是，r 3 ) 的基本范畴，即：较重的绿色菱形，较重的褐 色矩形，较重的黑色。菱形。 2 2 粗糙集的近似 令xsu ，r 是u 上的一个等价关系。如果x 能表示成r 基本范畴的并集 哈尔滨t 程大学硕十学位论文 时，就认为x 是r 可定义的；如果x 不能表示成等价关系r 基本范畴的并集 时，那么就认为x 是r 不可定义的。 如图2 1 所示，就粗糙集理论本身而言，我们可以运用两个集合来逼近 粗糙集合，就是采用粗糙集的上近似集合和下近似集合这两个精确集合来表 示。 雾一， “j 女 l ，。一；7 ：z 毪! ”向锈 爹 一 八 ， 习 荔， l 。 乒 ；。 哩： 甜 4 i n ， 心 爹 “ ， ， 一 、 五 l 一： ； l 磐 缴 ? 彰拶 t 雾+ 一 j 、 多 。 钐5 ：r k移，。l l龟 、 蓁，zi | 、， 辔 缓 弘，j 。， ， ，。，：- ? ，缓”。 x 的下近似 集合x 的边界 国 x 的上、下近似之差 下面的定理是非常明显的： 定理2 1 2 3 ( 1 ) x 为r 可定义集，当且仅当丛= r x 。 ( 2 ) x 为r 的非精确集，也称为粗糙集，当且仅当丛r x 。 可以使用胱表示为x 中的最大可定义集，使用r x 表示为含有x 的最 小可定义集。 我们可以从x 的上近似集合和下近似集合定义出发，就可以得到以下四 种定义1 2 3 】： ( 1 ) 假如r x 且r x u ，就表示x 为r 粗糙可定义。 ( 2 ) 假如r x = 且r x u ，就表示x 为r 内不可定义。 ( 3 ) 假如r x 西且r x = u ，就表示x 为r 外不可定义。 ( 4 ) 假如r x = 且r x = u ，就表示x 为r 全不可定义。 模糊集理论给集合中的每个元素确定一个隶属函数，即从( x ) e o ，1 】， 隶属函数的使用给人们带来了许多麻烦。然而在粗糙集理论中，隶属关系已 经显得无关紧要，由于它不需要人工参与或给定一个隶属函数，克服了主观 因素带来的不准确性。 定义2 4 【】令x u ，一个等价关系为r ，x 的精度可以表示为 ( 2 - 4 ) 幽刚b = 、l， x 哈尔滨工程大学硕士学位论文 i 1 i ii i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 葺 其中x ，i x i 是x 中含有x 的个数。 ( x ) 用来描述我们对于集合x 认识的完整情况。对每一个等价关系 r 、x u 有0 - a ：r ( x ) 1 。 当( x ) = 1 时，反映了x 的r 边界域是空集，x 是可以定义的； 当( x ) 1 时，反映了x 的r 边界域不是空集，x 是不可以定义的例。 为了更好的理解粗糙集和精度的定义，我们举例进行说明1 2 ，】： 设k = ( u ，r ) ，r ei n d ( k ) ，其中u = 工o ，x ，x2 ，x3 ，工4 ，x5 ，x 6 ，工? ， x 。，x 。，x l o ，且有r 的下列等价类： e l = xo ，x 。) ， e 2 = x2 ，工6 ，x9 ) ， e 3 = x3 ，工5 ) ， e 。= x 。， x8 ) ， e 5 = x7 ，x l o ， 集合x ，毒 工。，工，工。，工。) 为r 可定义集，因为 墨x i = r x 。= e ，u e t 集合x 2 = x 。，工。，x 。，x ；，x 。，工1 0 为r 粗糙可定义集，因为 x ：的近似集，边界和精度为 墨x 2 = e 3 ue 4 = x3 ，x 4 ，x5 ， x8 ) ， r x 2 = e 1 u e 3 u e 4 u e s = xo ，x l ， x3 ，x4 ，工5 ，工7 ，x8 ，x l o ， b n r ( x 2 ) = e l u e 5 = xo ，x l ，工7 ，x l o ， (