（计算机应用技术专业论文）粗糙集及其在数据挖掘中的应用研究.pdf

摘要波兰数学家z ，p a w l a k 于1 9 8 2 年提出的粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前，粗糙集理论己成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域。粗糙集在数据挖掘的过程中，可用于数据挖掘的数据预处理部分。本文正是以此为出发点，以粗糙集理论应用于数据挖掘数据预处理的相关步骤为线索，对粗糙集理论中的几个关键问题进行了深入地研究。全文重点论述的内容如下：( 1 ) 连续属性的离散化问题粗糙集能出色地处理离散属性，但不能直接处理连续属性，在数据挖掘应用中，往往需要进行连续属性离散化处理。本文提出了基于遗传算法的连续属性离散化方法h c g a 。该算法克服了基于支持度和基于重要性等离散化算法容易得到局部最优解的缺点，实验证明文中的算法兼顾了属性离散化的全局性和准确性。( 2 ) 属性约简算法到目前为止还没有一个公认的、高效的约简算法。本文通过分析胡可云博士提出的h o r a f a 算法，指出了其不能获得最优约简的缺点，提出了改进的属性约简算法b f a 和a b f a 。通过对比实验分析，b f a 算法和a b f a 算法都能得到较优约简，但比较这两种算法的时间复杂度，a b f a 算法具有更高的效率，是一种较优的约简算法。( 3 ) 决策规则提取算法基于粗糙集理论实现数据挖掘的目的就是为了得到有用的知识以指导决策，属性约简的最终目的也是为了得到有用的规则，一个好的规则提取算法可以对决策更加有利。而提取的规则必须符合实际应用，本文通过对决策树规则提取算法的研究，提出了改进的基于决策树的规则提取算法，在原i d 3 算法的基础上加入了风险控制条件，同时考虑了父代规则对子代规则关联信息的影响。实验证明，可以将这种算法应用到现实生活中去。关键词：粗糙集，数据挖掘，h c g a 算法，b f a 算法，a b f a 算法。a b s t r a c tt h et h e o r yo fr o u g hs e t st h a tw a sp u tf o r w a r db yap o l i s hm a t h e m a t i c i a nn a m e dz p a w l a ki n1 9 8 2i san e wt o o lf o rp r o c e s s i n gv a g u ea n du n d e f i n e dk n o w l e d g e u n d e rt h ep r e m i s eo fk e e p i n gt h ec o n s t a n ta b i l i t yo fc a t e g o r i z e ，t h em a i ni d e ao ft h et h e o r yi st oo u t p u tt h ed e c i s i o no ft h ep r o b l e mo rt h ec a t e g o r i z e dr u l et h r o u g ht h er e d u c t i o no f k n o w l e d g e c u r r e n t l y , t h et h e o r yo f r o u g hs e t sh a sa l r e a d yb e e na p p l i e ds u c c e s s f u l l yi nt h ea r e ao fm a c h i n el e a m i n g ，d e c i s i o na n a l y z i n g ，p r o c e d u r ec o n t r o l l i n g ，p a t t e r nr e c o g n i t i o na n dd a t am i n i n ge t c i nt h ew h o l ep r o c e s so f d a t am i n i n g ，r o u g hs e t si sm a i n l ya p p l i e di nt h ea s p e c to fp r e p r o c e s s i n go fd a t am i n i n g f r o mt h i sp o i n ta n dw i t ht h er o u g hs e t si nd a t am i n i n gt op r e p a r et h ep r o c e s so fs t e pf o rc l u e s ，t h i st h e s i st h o r o u g h l ys t u d i e saf e wk e yp r o b l e m so f t h et h e o r y t h ef o l l o w i n ga r es o m em a i np o i n t sd i s c u s s e db yt h et h e s i s ：( 1 ) t h ep r o b l e mo f c o n t i n u o u sa t t r i b u t e sd i s c r e t i z a t i o n r o u g hs e t sc a nd e a lw i t ht h ed i s c r e t ea t t r i b u t e so u t s t a n d i n g l y ；h o w e v e r , i tc a n tp r o c e s st h ec o n t i n u o u sa t t r i b u t e s t h u sw en e e dt oc h a n g et h ec o n t i n u i t yi n t ot h ed i s c r e t i z a t i o ni nt h ep r a c t i c a la p p l i c a t i o ni nd a t am i n i n g t h i st h e s i sa p p r o a c h e sad i s c r e t i z a t i o nm e t h o do fc o n t i n u o u sa t t r i b u t e sb a s e do ng a a n dt h i sm e t h o dc a na v o i do b t a i n i n gl o c a l l yo p t i m i z e dr e s u l t sw h e nu s i n gd i s c r e t i z a t i o nm e t h o db a s e do ns u p p o r ta n di m p o r t t h ee x p e r i m e n tp r o v e st h a tt h i sa l g o r i t h m sl o o k sa f t e rb o t ht h eo v e r a l ls i t u a t i o na n da c c u r a c yi nd i s c r e t i z a t i o na t t r i b u t e s ( 2 ) a t t r i b u t e sr e d u c t i o na l g o r i t h m sb yf a r , t h e r ei sn or e d u c t i v em e t h o dt h a tw a sa c c e p t e dg e n e r a l l ya n dt h o u g h te f f i c i e n t l y t h et h e s i sp o i n t so u tt h es h o r t a g et h a th o r a f ac a n tg e ts u p e r i o rr e d u c t i o na c c o r d i n gt oa n a l y s i so fh o r a f aa p p r o a c h e db yd o c t o rk e y u nh u ，a n dp u tf o r w a r das p e c i e si m p r o v e m e n to f a t t r i b u t e sr e d u c t i o na l g o r i t h m sb f aa n da b f a h o w e v e r , b o t ho ft h et w oa l g o r i t h m sc a ng i v et h eo p t i m a ls o l u t i o n b ya n a l y z i n gt i m ec o m p l e x i t yo ft h ee x p e r i m e n t ，i tc a l lb ec e r t i f i c a t e dt h a ta b f ac a rg e ts u p e r i o rr e d u c t i o n ( 3 ) e x t r a c t i n gd e c i s i o nr u l e sa l g o r i t h m st h ep u r p o s eo fr e s e a r c h i n gd a t am i n i n gb a s e do nr o u g hs e t si st og e tt h eu s e f u lk n o w l e d g ef o rm a k i n gd e c i s i o n t h ea t t r i b u t e sr e d u c t i o ni sa l s of o ri t ag o o de x t r a c t i n gd e c i s i o nr u l e sa l g o r i t h mc a l lm a k eo u rd e c i s i o nm o r eb e n e f i c i a l t h er o l eo ft h ee x t r a c t i o nm u s tm a t c ht h ea p p l i c a t i o no fa c t u a lc i r c u m s t a n c e ，t h e r e f o r e ，t h et h e s i sp u t sf o r w a r dt h ei m p r o v e dr u l ee x t r a c t i o na l g o r i t h m sb a s e do nd e c i s i o nt r e e ，a n dj o i n e dt h er i s kc o n t r o lc o n d i t i o no nt h eb a s a lo ft h eo r i g i n a l1 1 9 3a l g o r i t h m s ，c o n s i d e r e dt h ec o u p l e to fc m l i g r a p h yar o l eo far u l eo ff a t h e rc o n n e c t i o nm e s s a g ea tt h es a m et i m e ，a c c o r d i n gt or e s e a r c h i n gt h ea l g o r i t h m se x t r a c t i n gf r o mt h er u l eo fd e c i s i o nt r e e i th a sb e e np r o v e dt h a tt h ea l g o r i t h m sc a nb ea p p l i e di np r a c t i c e k e y w o r d s ：r o u g hs e t s ，d a t am i n i n g , h c g aa l g o r i t h m s ，b f aa l g o r i t h m s ，a b f aa l g o r i t h m s西北大学学位论文知识产权声明粥y 、8 9 3 7 1 2本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期闻论文工作的知识产权攀位f | i 嚣于秀j 艺大学。学校有权傈鼙荠向豳家有关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据瘴进行检索，可以袋建影印、缩印或掇接等复刳手段僚存秘汇绽本学饿论文。同时，本入保证，毕业后结合学位论文研究课题再撰写的文章律注明作者单俄为西北大学。保密论文待勰密后适用本声明。学位论文 乍者签名：丕i 二蓝：指导教 摹签名：肋占年占月切日细g 年g 月曰嚣曩乏大学学位论文独创性声鞠本人声明：所黧交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方矫，本论文不雹含粪缝人已羟发表或撰写过的蕊究成采，也不毫含为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我一间工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：匆、苗、k ，= d 占年g 月如日1 1 概述第一章绪论信息产业是现代社会的三大支柱产业之一，信息是现代社会的基础，丽数据库技术则又是信息处理技术的基石。随着人类活动范围扩展、生活节奏加快以及技术的进步，人们能以更快和更廉价的方式获取和存储数据，使得数据和信息的数量以指数形式增长。仅用查询和检索，已不能提取数据中有利于用户实现目标的、带有知识性的信息，也无法提取数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，从而导致了“数据爆炸但知识贫乏”【i 的现象。因此，迫切需要新的知识发现工具对数据进行分析、推理，发现数据间的联系、提取有用特征、简化信息处理、减少信息的浪费。目前研究不精确、不确定知识的表达、学习、归纳等方法己成为智能信息处理中的重要研究课题。粗糙集理论【”1 是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的分类规则。目前，粗糙集理论已成功地用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域。在d m 和k d d 诸多方法中，粗糙集理论与方法对于处理复杂系统，不失为一种有效的方法。因为它与概率方法、模糊集方法和证据理论方法等其他处理不确定性问题理论的最显著的区别是，它无需提供问题所需处理的数据集合之外的任何先验信息。所以，与其他处理不确定性问题的理论有很强的互补性。粗糙集理论与数据挖掘密切相关 ”。粗糙集理论是数据挖掘领域中的又一个有效的方法与数学工具。第一，数据挖掘研究的对象多为关系型数据库，而关系型数据库的关系表可以被看作是粗糙集理论中的决策表；第二，现实世界中的规则有确定性也有不确定性的，数据库中也同样包含确定的规则和不确定的潜在规则。从数据库中发现不确定性的知识，就为粗糙集方法提供了用武之地。第三，数据库中的数据可能含有噪声，而剔除数据中的噪声也是粗糙集理论的特长之一。第四，数据挖掘领域，有诸多处理工具各有优缺点。其中，神经网络方法不能自动地选择合适的属性集，若币旷甩粗糙集方法进行数据预处理，去掉多余的属性，就可提高数据处理的效率；又如模糊集理论或者统计学方法需要数据库中数据的先验知识，而粗糙集方法却无需先验知识，较之能更好地表达数据库中的数据。第五，由于粗糙集理论自身的优点，经粗糙集方法处理得到的决策规则和推理过程较神经网络等工具更易证实和检测。粗糙集理论自提出后就一直是各国科学家研究的热点。1 2 论文的研究背景1 2 1 数据挖掘的特点和研究状况数据挖掘1 1 1 ( d a t am i n i n g ) 是一个提取有用信息的过程。与数据挖掘意义相近的术语有数据开采、知识抽取、信息收集和信息发现等。现在普遍采用的主要有数据挖掘和数据库中的知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ，k d d ) o k d d一词最早出现在1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了k d d 专题讨论会，集中讨论了数据统计、海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议发展成为年会。1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上不仅讨论了学术问题，还有3 0 多家软件公司展示了他们的数据挖掘软件产品，不少软件己在北美、欧洲等地得到应用。其它内容的专题会议也把数据挖掘和知识发现列为专题之一，成为当前计算机科学界的一大热点。事实上，数据挖掘是数据库中知识发现过程的一个基本步骤【l j 。知识发现过程如图1 1 所示，由以下步骤组成：展开文件图1 1( 1 ) 数据清理：消除噪声或不一致数据。( 2 ) 数据集成：多种数据源可以组合在一起。( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。( 5 ) 数据挖掘：使用智能方法提取数据模式或模型。( 6 ) 模式评估：根据某种兴趣度度量，识别真正有趣的知识模式。( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。9 0 年代初期，i n m o nw h 在其著作( b u i l d i n gt h ed a t aw a r e h o u s e ) )中第一次提出“数据仓库”的概念。从此，数据仓库的研究和应用得到了广泛的关注。数据仓库是在企业管理和决策中面向主题的、集成的、时变的以及非易失的数据集合 1 3 , 1 4 。与其他数据库应用不同的是，数据仓库更像一种过程对分布在企业内部各处的业务数据进行整合、加工和分析的过程。传统的数据库管理系统( d a t a b a s em a n a g e m e n ts y s t e m ，d b m s ) 的主要任务是联机事务处理( o n - l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) ；而数据仓库则是为数据分析和决策提供服务，这种系统被称为联机分析处j 里( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 。o l a p 的概念最早是由关系数据库之父e ec o d d 于1 9 9 3 年提出的。当时，c o d d 认为o l t p已不能满足终端用户对数据库查询分析的需要，结构化查询语言( s t r u c t u r e dq u e r yl a n g u a g e ，s q l ) 对数据库进行的简单查询也不能满足用户分析的需求。用户的决策分析需要对关系数据库进行大量计算才能得到结果，因此c o d d 提出了多维数据库和多维分析的概念。与国际上数据挖掘的研究和应用相比，我国在数据挖掘方面的研究尚处于起步阶段。计算机世界报技术专题版于1 9 9 6 年7 月发表了由中国人民大学信息学院王珊教授组织的“从数据库到数据仓库”的技术专题【1 5 】，1 9 9 8 年中国科学院数学研究所组织了“数据挖掘技术”的专题【16 1 ，同期还有国防科技大学的“决策支持系统”专题”】，这些专题对我国开展数据挖掘的研究起到了很大的推动作用。总之，数据挖掘与知识发现作为一门新兴的具有很大发展潜力的多学科融合的研究分支，目前已得到了各国学者和软件公司的重视和关注。1 2 2 粗糙集的特点和研究状况粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论。由于最初关于粗糙集理论的研究主要集中在波兰，因此，当时并没有引起国际计算机界和数学界的重视，研究地域仅限于东欧的一些国家。直到1 9 9 0 年前后，由于该理论在决策与分析、模式识别、机器学习与知识发现等方面的成功应用，才逐渐引起了世界各国学者的广泛关注。1 9 9 1 年z p a w l a k 的专著粗糙集一关于数据推理的理论( r o u 曲s e t s _ 一t h e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a ) 的问世，标志着粗糙集理论及其应用的研究进入了活跃时期。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集讨论会。这次会议主要讨论了集合近似定义的基本思想及其应用。但参加这次会议的研究者较少，范围也不太广泛。这次会议选出了15 篇论文刊登在“f o u n d a t i o no fc o m p u t i n ga n dd e c i s i o ns c i e n c e s ”1 9 9 3 年第1 8 卷上。从此，每年召开一次以粗糙集理论为主题的国际研讨会。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗糙集与知识发现研讨会。这次大会极大地推动了国际上对粗糙集理论与应用的研究，其主题是粗糙集，f u z z y 集与知识发现。由于此时正值k d d 成为研究的热门话题，一些著名的k d d 专家参加了这次会议，并且介绍了许多基于扩展的粗糙集理论的知识发现方法与系统。1 9 9 4 年在美国的s a nj o s e 召开了第三届国际粗糙集与软计算研讨会，这次会议广泛的探讨了粗糙集与模糊集、神经网络、进化理论等的融合问题。1 9 9 5 年召开的第四届模糊理论与国际技术研讨会，在这次会议上，针对粗糙集与模糊集合的基本观点与相互关系展开了激烈地讨论，较大地促进了粗糙集的研究。1 9 9 6 年底在日本东京召开了第五届国际粗糙集研讨会，这是第一次在亚洲召开的范围广泛的研讨会。1 9 9 8 年6 月在波兰华沙召开了“第一届粗糙集和计算的当前趋势”学术会议。1 9 9 9 年9 1 1 月在日本召开了“第七届粗糙集，f u z z y集、数据挖掘和粒度软计算的国际学术研讨会”( t h es e v e n t hi n t e r n a t i o n a lw o r k s h o po nr o u g hs e t s ，f u z z ys e t s ，d a t am i n i n ga n dg r a n u l a r - s o f tc o m p u t i n g( r s f d g r c 9 9 ) ) ，阐述了当前粗糙集、模糊集的研究现状和发展趋势，指出将着重在软计算、数据库、人工智能和近似推理等方面开展理论和应用。2 0 0 0 年1 0月在加拿大又召开了“第二届粗糙集和计算的当前趋势”学术会议。目前，许多关于人工智能、模糊理论、信息管理与知识发现等国际学术会议上经常可以看到粗糙集方面的论文。总之，粗糙集理论已成为信息科学最为活跃的研究领域之一。同时，该理论还在医学、化学、材料学、地理学、管理科学和金融学等其他学科得到了成功地应用。近年来，粗糙集理论的研究成果主要在于，粗糙集理论用确定的方法处理不完备和不确定的信息和数据，不需要先验知识，可从数据中得到知识，生成决策规则；围绕粗糙集理论与应用研究，开发出了相应的软件支撑系统，在实际应用中涌现出了很多成功的范例。1 3 论文背景及研究内容由上面的论述可知，目前，数据挖掘研究越来越受到学者的重视，而粗糙集理论作为一种数据挖掘工具有着它不可替代的优点，受到研究学者的广泛关注。因此研究粗糙集理论有着极其重要的理论意义和现实意义。粗糙集只能处理离散数据，所以在利用粗糙集进行研究之前必须将连续数据离散化，连续数据离散化的准确性直接影响到粗糙集的属性约简和规则提取，所以是一个关键的步骤。本文提出的种连续数据离散化算法( h c g a ) ，该算法可以有效的得到准确的离散化数据，为以后的操作提供了方便。属性约简一直就是一个研究的热点问题，国内外研究学者都对此方面特别关注。到目前为止，已经提出了一些约简算法，然而却没有找到一个公认的、高效的约简算法。因此，粗糙集理论高效、最优的约简算法仍然需要研究。本文对胡可云博士提出的h o r a f a 算法进行了改进，提出了b f a 算法和a b f a 算法，都可以得到较优约简，通过对比实验又进一步得到结论，a b f a 算法的时间效率较b f a 算法更高，a b f a 算法是一个高效的、较优的属性约简算法。属性约简的目的是为了得到决策规则，对于不同的应用应有不同的处理方法，本文利用改进的决策树方法提取决策规则，通过加入风险因子控制最终决策规则，同时考虑了父代规则对予代规则关联信息的影响，真正的得到了可应用于实际中的决策规则。本文的研究受到了陕西省教育厅重点科研计划项目( 0 0 j k 0 1 5 ) 及西北大学引进人才基金的资助。1 4 论文的组织与结构本文围绕粗糙集在数据挖掘中的应用展开研究。从数据的离散化开始，经过属性约简，最后完成规则提取任务。本文的组织如下：第一章：绪论。主要介绍了数据挖掘、粗糙集的研究现状和各自的特点，以其论文的研究背景及工作内容。第二章：粗糙集理论概述。综述了粗糙集理论的基本概念以及一些重要的性质。第三章：连续属性的离散化。本章着重研究了连续属性的离散化问题，提出了一种连续属性离散化算法，仿真实验证明了该算法是有效的。第四章：粗糙集属性约简算法。本章针对胡可云博士提出的h o r a f a 算法，分析了其中不能得到较优约简的不足，提出了一种改进的属性约简算法( b f a ) ，实现了较优约简，但考虑到b f a 算法时间复杂度较高。又提出了一种改进的属性约简算法( a b f a ) ，实验证明，后一种算法具有较高的效率，同时也可以得到较优约简。第五章：粗糙集的决策规则提取算法。本章通过对决策树规则提取算法的研究，提出改进的基于决策树的规则提取算法，在原i d 3 算法的基础上加入了风险控制条件，同时考虑到了父代规则对子代规则关联信息的影响，实验证明，该算法是一种较好的规则提取算法，可以将该算法应用到现实生活中去。第二章粗糙集理论概述粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。2 1 知识与知识库定义2 1 设u a 是感兴趣的对象组成的有限集合，称为论域。任何子集x u ，称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。一个划分定义为 互，置鼍) ：誓u ，置a ，薯n = a ，对于i j , i ，= 1 ，2 行；u 五= u 。u上的一族划分称为关于u 的一个知识库( k n o w l e d g e b a s e ) 。定义2 2 设r 是u 上的一个等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成的集合，【工k 表示包含元素x e u 的r 等价类。一个知识库就是一个等价关系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的族等价关系。若p r ，且p o ，则n p ( p 中所有等价关系的交集) 也是一个等价关系，称为p 上的不可区分( i n d i s c e m i b i l i t y ) 关系，记为i n d ( p ) ，且有 j k ( 一= r i x 月，r e p这样u i n d ( 尸) ( 即等价关系i n d ( p ) 的所有等价类或基本范畴) 表示与等价关系族p 相关的知识，称为k 中关于u 的p 基本知识( p 基本集) 。也可以定义，当k = ( u ，r ) 为一个知识库，i n d ( k ) 定义为k 中所有等价关系的族，记作i n d ( k ) = i n d ( p ) l o p r 。2 2 不精确范畴，近似与粗糙集定义2 3 令j u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范畴的并时，称x 是r 可定义的；否则称x 为r 不可定义的。r 可定义集是论域的子集，它可在知识库k 中精确的定义，而r 不可定义集不能在这个知识库中定义。r 可定义集也称作r 精确集，而r 不可定义集也称为r 非精确集或r粗糙集。当存在等价关系r i n d ( k ) 且x 为r 精确集时，集合x u 称为k 中的精确集；当对于任何r i n d ( k ) ，x 都是r 粗糙集，则x 称为k 中粗糙集。对于粗糙集可以近似的定义，使用两个精确集，即粗糙集的上近似( u p p e ra p p r o x i m a t i o n ) 和下：i 刚( 1 0 w e ra p p r o x i m a t i o n ) 来描述。定义2 4 给定知识库k = ( u ，r ) ，对于每个子集x 互u 和一个等价关系r i n d ( k 1 ，定义两个子集：_ e o c = u ( y e u r i y x ) ，r x = u y u r i yn x a 集合b n r ( ) ( ) = r x 一些称为x 的r 边界域：p o s r 伍) = 趔称为x 的r 正域：n e g r ( x ) = u - - 瓦x 称为x 的r 负域。星或p o s r ( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；足z 是那些根据知识r 判断可能属于x 的u 中元素组成的集合；b n r ( 均是那些根据知识r 既不能判断肯定属于x 又不能判断肯定属于x ( 即u - x ) 的u 中元素组成的集合；n e g r ( x ) 是那些根据知识p 判断肯定不属于x 的u 中元素组成的集合。如图2 1 所示图2 12 3 知识约简知识约简是粗糙集理论的核心内容之一。众所周知，知识库中知识( 属性)并不是同等重要的，甚至其中某些知识是冗余的。所谓知识约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的知识。知识约简中有两个基本概念：约简( r e d u c t ) 年l ：l 核( c o r e ) 。定义2 5 令r 是一族等价关系，r ，如果i n d ( r ) = i n d ( r 一 r ) ，则称r为r 中不必要的；否则称r 为r 中必要的。如果每一个r r 都为必要的，则称r 为独立的；否则称r 为依赖的。定理2 1c o r e ( p ) = f q r e d ( p ) ，其中r e d ( p ) 表示p 的所有约简。令p 和q 为u 中的等价关系，q 的p 正域记为p o s ，( q ) ，即p o s ，( q ) = up _ x 。q 的p 正域是u 中所有根据分类u p 的信息可以准确地x e u q划分到关系q 的等价类中去的对象集合。定义2 6令p 和q 为等价关系族，r p ，如果p o s m d 尸) ( f ”d ( q ) ) = p o s i n 邶一 ) 沏d ( q ) ) ，则称r 为p 中q 不必要的；否则r 为p中q 必要的。p o s ，( q ) 可以代替p o 舢) ( i h d ( q ) ) 。如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或p 相对于q 独立) 。设s p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p o s 。( q ) = p o s ，( q ) 。p 的q 约简简称为相对约简。p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核，记为c o r e q ( p ) 。定理2 2c o r e e ( p ) = n r e d 口( p ) ，其中r e d o ( p ) ：p r 蛆j r y f g p 的q 约简构成的集合。2 4 知识的依赖性定义2 7 令k = ( u ，r ) 为一个知识库，且令p ，q r 。( 1 ) 知识q 依赖于知识p ( 记作p j q ) 当且仅当i n d ( p ) i n d ( o ) 。( 2 ) 知识p 与知识q 等价( 记作p s q ) 当且仅当p j q j l q = p 。( 3 ) 知识p 与知识q 独立( 记作p q ) 当且仅当p j q 与q j p 均不成立。显然，p s q 当且仅当i n d ( p 1 = i n d ( q ) 。当知识q 依赖于知识p 时，也说知识q 是由知识p 导出的。有时候知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识p 导出的，部分可导出可由知识的正域来定义。定义2 8令k = ，r ) 为一个知识库，且令尸，q 曼r ，当k = 0 ( q ) = c a r d ( p o s ，( q ) ) c a r d ( u ) 时，称知识q 是k ( 0 k 1 ) 依赖于知识p 的，记作p ；。q ，其中，c a r d ( p o s ，( q ) ) 表示了根据p ，u 中所有一定能归入q 的元素的数目。当k = l 时，称q 完全依赖于p ，即论域的全部元素都可通过知识p 划入u q的初等范畴；当0 k l 时，称q 粗糙( 部分) 依赖于p ，即只有属于正域的元素可以通过p划入知识q 的范畴：当k = 0 时，称q 完全独立于p ，即论域中没有元素能通过p 划入q 的初等范畴。如果p j q ，也记为p j q 系数r a o ) 可以看作q 和p 间的依赖度。2 5 知识表达系统知识表达是智能信息系统的关键，所谓知识获取，就是要从大量的原始数据信息中分析发现有用的规律信息，即是将知识从一种原来的表达形式( 原始数据表达形式) 转换为一种新的目标表达形式。基于粗糙集理论的知识发现，主要是借助于信息表这样一种有效的数据表知识表达方式，这是粗糙集理论中对知识进行表达和处理的基本工具，其基本成分是研究对象的集合。定义2 9 四元组s = ( u ，a ，矿，厂) 是一个知识表达系统，其中u ：对象的非空有限集合，称为论域；a ：属性的非空有限集合；v = u 地，v 。是属性a 的值口e a域；f ：u x a v 是一个信息函数，它为每个对象的每个属性值赋予一个信息值，即v a a ，x u ，f ( x ，a ) 虼。2 6 决策表决策表是一类特殊而重要的知识表达系统。多数决策问题都可以用决策表形式来表达，这一工具在决策应用中起着重要的作用。定义2 1 0 设s = ( u ，a ，v ，f ) 为一知识表达系统，a = c u d ，c n d = o ，c称为条件属性集，d 称为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。一个决策表中结果属性有时是唯一的，称为单一决策：有时是不唯一的，称为多决策，对于具有多个结果属性的决策表总是可以转换成单一决策表。这有利于问题的简化和求解。定义2 1 1 设决策系统s = ( u ，c u d ) ，如果任意x j u i n d ( c ) ，一定存在i u i n d ( d ) ，使得五，那么决策表是协调的，否则是不协调的。也就是说当决策表是协调时，条件属性和决策属性间的依赖度p o s 。( d ) 等于1 ，否则等于0 。每个决策表都可以难一分解成两个决策表，其中一个表完全不协调，依赖度为0 ；另一个表则完全扔调，依赖度为1 ，当然只有依赖度大于0 且不等于1时，这一分解才能进行。定义2 1 2 设s = ( u ，a ，v ，f ) 是一个决策表，a = c u d ，c f i d = o ，其中c为条件属性集，d 为决策属性集。令z 和f 分别代表u c 与u d 中的各个等价类，d e s ( x 。) 表示对等价类置的描述，即等价类x i 对于各条件属性值的特定取值；d e s ( y ) 表示对等价类巧的描述，即等价类对于各决策属性值的特定取值。定义2 1 3 决策规则定义：0 ：缸( 五) 寸概( 巧) ，r n 五o ，规则的确定性因予( 互，誓) = | 巧n 五| | 五| ，o ( 五，弓) s 1 当f ( 五，艺) 一l 时，鼍是确定静；警0 4 五，) 1 时，咯是不确定的。在实际应用中，许多决策问题都可以用决策表来表达，这个工具在决策应用中超羞提当重要懿l 乍廷，倒懿，躅决策表来蘧述家医陵，浃策表的每个实铡霹能就是病人，聚伟潺性是症状和检溯，丽决策是病症。每个病人都由裣溅的绪果和症状来表征，而且由医生( 专家) 根据瘸症的严重程度_ 辩乏分类。2 7 可辫识矩阵和可辨识函数定义2 。1 4 可辫识矩阵：给定一个信息系统s = ( u ，a ，v ，) ，a = c u d 怒属性集合，c ，d 分别是条件属性和决策属性。可辨识矩降m ；( m 。) 定义为：f 垃芒c ：口( 薯) 目0 ，) ，d ( x i ) 毋d ( x ，)毪。 。，其它。其中a ( x ) 是元组x 在属性a 上的取值，d ( x ) 是x 在决策属性d 上的取值。由上面可辨识矩阵的定义可知，当两个对象的决策属性取值相同时，它们所对应的可辨识矩眸元素的取值为o ；当两个对象的决策属性不同且可以通过菜魑条传属性懿取擅不阕龆鼓区分霹，它们濒对应静可辨识缒黪瓣元素的取篷隽这薅个对象属经僮不瓣豹条件属性集合，鄯可渡区分这两个瓣象豹条件属性集合。警两个对象发生冲突时，即所有的条件麟性取值相同而决策桶性的取值不同时，则它们所对应的可辨识矩阵中的元素的取值为空集。根据可辨识矩孵的定义，可瞄得到霹辨识矩阵如下戆髓质：f 1 ) 可瓣谖蹩臻楚一个黯蠡篷终。溺忿计算露只计算上睾矩薄或下半矩辫。( 2 ) 根据可辨识矩阵的定义，可以发现可辨识矩阵中的元素是由能够区分两个对象的黼性构成。如果某元索只有一个属性，则说明这两个对象只有靠这个属性来唯一区分，因此这个属性是不可删除的，是核属性。一令售惠系统夔震往绞麓可 盖遴过俊楚交可瓣识蹩黪宝藏兹可藜鼍鏊滋数露得到，这个函数的极小祈取范式中的所裔合取式就是信息系统所有的属桎约简。定义2 1 5 可辨识函数的定义：a = i - i m f 。其中州，= a 1v a 2 ：v 。- v d 月，棚口2 口l ，口2 ，n 可辨识函数a 有如下性质：函数a 的极小析取范式中的所有合取式是系统的所有约简。2 8 决策属性的支持度定义2 1 6 设y d 是决策表( u ，a ) 中的一个决策属性a = c u d ，c n d = 0 。现在考虑决策属性y d 的整体决策而不是对于“决策子集”w u y 的一个局部决策。决策属性y d 关于条件属性a c 的支持子集是子集s a ( y )2u 。帅“盯2 u 。，( u ，。：，r )s p t a ( y ) 一u m ，彤一i iu称为y 关于a 的支持度。如果u y = u 8 ，其中艿是“全体”划分u a = u ，则对于d c ，有只( y ) = u ，s p t 。( y ) = 1 。2 9 属性重要性定义2 1 7 如果t ( y ) = u w 。u y ( u ，。；，矿) a ，则x 在x 中是重要的( 对于y 而言) 。如果疋( 】，) = u w e u i y ( u ，。，y ) = 。，则x 在x 中是不重要的( 对于y 而言) 。令o c x c ，o c y d ，u y u 6 = ) 。给定x e ，定义x在x 中的重要性( 对于y 而言) 为s 辔；咄 = ( i s x ( r ) l i s x 七 ( y ) i ) i u i 。第三章连续属性的离散化z p a w l a k 提出的粗糙集理论认为知识是论域在等价关系下形成的划分，所以它适于处理具有离散属性值的信息系统，而不能直接处理具有连续属性值的系统。所以在数据挖掘的实际应用中，需要把连续属性进行离散化 2 0 , 2 1 1 ，然后再用粗糙集理论进行处理。本文提出一种离散化算法( h c g a ) ，本算法在离散化的过程中充分考虑到了离散后的条件属性对决策属性的支持度方面的因素，既提高了数据离散化的准确率，又提高了数据离散化的效率。连续属性的离散化是知识获取的数据预处理步骤，它不仅可以缩减运算量还能在一定程度上抑制噪声。本章首先分别介绍了数据离散化、分层聚类、遗传算法的基本概念和基本特点，为改进的算法提供理论基础。然后介绍了离散化算法h c g a ，最后通过实验证明了算法的可行性和有效性。3 1 离散化问题的描述决策表s = u ，r ，v ，p ，u = 。l ，x 2 ，x n ) 为有限的对象集合即论域，r = c u d 是属性集合，c = c i ，c 2 ，c k ) 为条件属性集合， d 为决策属性集。对于任意的a e r ，有信息映射u v a ，u 是属性a 上的值域，在值域v a _ 1 。，q上的一个断点可记为( a ，c ) ，其中a r ，c 为实数值。在v 。= 1 a ，r a 】上的任意一个断点集合d a = ( a ，c l a ) ，( a ，c 2 8 ) ，( a ，c k 干l a ) ) 其中，k a n ，且l 。= c o a c i a ( c 2 a ， c k + 1 8 = r a ，定义了v 。上的一个分类p 。，p a = c o a , c 1 8 u c l a ，c 2 8 u u c k a , c k + 1 8 。因此，任意的p = u p 。，a e r 定义了一个新的决策表s p = t ，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。3 4 基于遗传算法的连续属性离散化方法本节提出了一种基于遗传算法的连续属性离散化方法( h i e r a r c h i c a lc l u s t e r i n gg e n e t i ca l g o r i t h m s ，h c g a ) ，将最小断点集作为优化目标，并构造一个新的算子来保证所选断点能保持原决策系统的不可分辩关系。3 4 1 算法的基本思想在离散化过程中，如果划分较细，可以提高对决策属性的支持，但是往往会使决策表含有很多的冗余信息，降低了约简效率；如果划分较粗，则可能增加决策表中不相容信息。因此，必须在决策属性支持度不变的条件下，寻找能提高约简效率的划分。在本算法中充分考虑到这些因素的影响，使用遗传算法进行属性离散化之前