（农业机械化工程专业论文）一种启发式属性约简算法的研究与应用.pdf

摘要 一种启发式属性约简算法的研究与应用 农业机械化工程专业硕士研究生赖凡 指导教师余建桥教授 摘要 随着现代信息技术和计算机网络技术的不断壮大，人们可以非常容易地通过各种途径获 得数据，大量的数据已经充斥在我们的工作以及生活之中。面对如此纷繁的数据，如果我们 仍然采用传统的人工方式来进行处理会显得不切实际。如何能够快速而又准确地从这些海量 的数据中提取出有价值的知识来帮助我们进行决策和管理成了大家关注的问题。于是我们很 容易就会想到处理这些数据可以借助运算速度最快的计算机来实现。因此需要研究者对机器 学习特别是数据库知识发现做更加深入和广泛的研究，而数据库中往往存在冗余数据、缺失 数据、不确定的数据甚至不一致的数据等诸多情况，这些数据成了知识发现过程中的一大障 碍。 波兰数学家z p a w l a l ( 在1 9 8 2 年提出租糙集理论，粗糙集理论能够处理模糊和不确定性数 据，并且它具有的模型简单直观，无需数据先验信息。根据粗糙集理论提取出的规则易于理 解，自此理论提出之后已被成功地运用于商业等领域。本文针对粗糙集理论在知识发现过程 中几个关键问题：数据预处理、约简、规则提取等迸行了深入的研究。重点对粗糙集理论在 知识发现过程中约简算法进行了分析和总结，到目前为止还没有一个公认的、高效的约简算 法。在此基础上，作者提出了基于差别矩阵和启发式约简的改进算法，以减少时间复杂度， 提高算法效率并获取最优约简。 本文首先对粗糙集理论的发展、国内外研究现状及研究意义、粗糙集理论基础进行了研 究，并对知识发现过程中各环节运用粗糙集理论的方法进行了分析；其次论文分析了数据预 处理阶段常用的几种属性离散化方法，重点对连续属性离散化的n s 离散算法进行了研究。再 次对决策表的约简问题进行了分析，重点讨论了属性的约简和属性值的约简问题。在属性约 简方面，对目前常见的粗糙集属性约简算法进行研究总结，指出了存在的问题，并在此基础 上，针对差别矩阵以及启发式约简算法提出了改进算法，减少算法在计算时所需的时间和空 间复杂度，求取最小约简。在属性值约简方面，提出了基于启发式值约简算法的改进算法， 西南大学硕士学位论文 实现了有效地获取规则。最后通过u c i 数据库的实验对比分析，验证了改进算法具有更高的 效率，并能够得到较优的约简结果。本文还将改进后的约简算法系统地应用到学生考试成绩 分析中，对得到的规则进行科学地评价，找出影响学生成绩的潜在因素，并提出学习建议。 通过实际的应用，再次验证了改进算法的有效性和可行性。 关键词：属性约简启发式算法差别矩阵粗糙集 a b s n a c t a l bs t r a c t a 1 0 n gw i t ht l l eg r e a td e v e l o p m e n to fm o d e m 协f o 删i o nt e c h n o l o g y 勰dc o m p u t e rn e 细耐k ，i t w 舔c o n v e n i e n tf o ru st og e ta c c e s st oa l lk i n d so fd a t a ，w l l i c hh a da h a d yc o n g e s t e do u rd a i l yl i f e a n dw o r k s h o u l di tb eu i l p m c t i c a lt op r o c e s ss u c h 硼m e r o 砸锄dc o r 印l i c a t e d 纰，i fm et r a d i t i 帆a l m a n u a lm o d ew 嬲u s e d t h e ( 1 u e s t i o na f b r e s a i dh a dd l 删0 u ra n 饥t i o na sh o wt of e t c h 廿l eu s e f h l i i l 】 o m 眦i o ne x p e d i t i o u s l y 她dv e r a c i o u s l yf r o mm 硒s i v ed a t at oh e l po u rd e c i s i o n n 试【i i l g 孤d m 黝g e m e n t u n d o u b t e d l y c o m p u t e t i l em o s ts p e e d yo p e r a l t i o nm a c h i i l e ，c o u l db en l es o l u t i t o p r o c e s sm ei 1 1 f o m l a t i o n ，w l l i c hr e q u 疵dm o r et h o r o u g h 锄dc 唧r e k m s i v er e s e a r c h 叩n l ed a t ab a u s e k n o w l e d g ed i s c o v e r yw h e r et h er e d u n d 锄t ，d e f a u l t 强dn e 咖li n f o n n a t i o nc o u l db eam 句o f o b s t a c l e i i l1 9 8 2z p a w l a l 【，p o l 觚dm a 圮m a t i c i a i l ，p u tf o r w a r d sr o u 曲s e t l e o 够nc o u l dp r o c e s sv a g i l e a n d 咖d e f m e dd a t a ，o fw l l i c hm em i m e lw 勰嘶e f 锄di n t l l i t i o n i s t i cw i t l l o u tv a l i d a t e d i l l gi i l = f o n i l a t i o n i na d 啪c e a s 圮d e c i s i o nm l e sd e d l l c e df r r o mr o u g hs e tt l l e o 巧w 淞s 衄i g h t f 0 刑a r d ，i tt 扭db e 饥 觚1 1 1 i p u l a t e di i lb u s i m s s 证l l l 】叩h 卸t l y 1 1 1 i sp a p e rf o c u s e do n l ec d t i c a l i s s u e so fr o u g l ls e t l e o 拶 d u r i n gk n o w l e d g ed i s c o v e 巧，s u c h 弱讹p 1 1 e p r o e e s s i i l g ，r e d u c t i o n 孤dr u l e sr e d u c t i o n ，a m o n g w l l i c hm 如c t i o nw a ss 1 ) e c i f i c a l l ya i l a l y z e d 锄dc o n c l u d e d ，a i l di tw 舔d i s c o v e 此dm a tl u l t i in o wt h e r e w 弱n o ta na c k n o w l e d g e d 觚de 伍c i e n tr e d u c t i o na l g o d m m u n d e rt l l i sc i r c u m s t a i l c e ，t l l e 肌l o r b r o u g h tf o r w a r da 1 】h o r a t e da i i n l m e t i cb 舔e do nd i s c e m i ：b i l i t ym a t r i x 舭dn l eh e 耐s t i ca l g 嘶t h mf o r 砌b u t e 托d i l c t i o n ，i no r d e rt or e d u c et i i i l ec o m p l e x i t y ，i m p r o v ea r i t h m e t i ce 伍c i e r l c y 锄do b t a i nn l e b e s ti i e d u c 缸o n i i lm ef i r s tp l a c e ，廿l ep a p c rs t u d i e dt l l ed e v e l o p m e m 柚dr e s e n tr e s e a r c ha c l l i e v e m e n to fr o u g h s e t sa th o 蜘【ea n da ：b m a d ，a i l d l e s e a r c hs i g n i f i c a n c e 瓤l dt l l e o r e t i c so fr 0 i u g hs e t s ，a n di ta l l a l y s e d t l l er o u 曲s e tm e a n s 惋c hw e r ea p p l i e dt 0e v e d rp 1 1 a s e so fl ( 1 l o w l e d g ed i s c o v e h lm en e x tp l a c e ，i t a i l a l y s e ds e v e m lm e t h o d so fd i s c r e t i 刎o no fn i l r r i ca t 缸伯u t ei nd a 协p r 印r o e e s s i n gp h a s e ，w i mm e e m p h a s i sa 钍a c h e dt ot h en a ：v es c a l e fa l g o r i t h mf o ft h ed i s c r e “z a t i o no fc o n t i l l u o u s 砌b u t e s a b 0 幢 d e c i s i o nt a b l er e d u c t i o n ，e s p e c i a l l y l ea 缸i b u t er e d u c t i o na n dt l l ev a l u er e d u c t i o nw e r ea l s o e x p l o r e d h lm et e m 塔o fa 蜘b u t e sr e d u c t i o n ，t h ea u m o ra n a l ) ，z e d l ef a m i l i a ra l g o d 吐m l so fm e 砌b u t e sr e d u c t i 衄b a s e d0 nr o u g hs e t ，锄dp o i n t e do u tm ee x i s t e n tp r o b l 锄b 觞e d0 nn l i sr e s e a r c h ， a i l i l l l p r 0 v e da l g o d t l l mw 鹊p u tf o r w 矾sa c c o r d i l l g t 0t i l e d i s c e m i b i i i t ) rm 撕xa i l dh e 谢s t i c a l g o r i t l l i l lf o ra t t r i b u t e sr e d u c t i o n ，w h i c hr e s u l t e di n t 1 1 er e d u c t i o no fs p a c et i i i l ec 伽叩l e x i t y ，a n d o b t a m i n gt l l eb e s tr e 血l c t i o n w i lr e s p e c tt oa 蜘b u t ev a l u er e d u c t i o n ，a ni m p r 0 v e da l g 砥t l l mw a s a d v a i l c e dg r 0 1 m d e do n也eh e l l r i s t i ca 1 9 0 r i t h mf o rv a l u er e d u c t i o n ， a c t t i a l i z i n g e 街c i e n t m l e s - o b t a i n i n g l 勰tb u tn o tl e 舔t ，b yc o r n p 锄t i v ea n a l y s i so fu c id a 眦a s e ，t l l ea f o r e m e n t i o n e d i i i 西南大学硕士学位论文 i 棚p r 0 v e da l g o r i n u _ i l sw e r eo f1 1 i g h c re m c i e i l c y 孤do b “nb e t t e rr e d u c t i o nr e s u l t s a m dt h ep a p e r a p p l i e dm ei h 甲r o v e dr e d u c t i o na l g o r i t l l l l n st om ea n a l y s i so fs t t l d e n t s e x 舭l i i l a t i o n 碍s u l t s ，m a i 【i n g s c i e n t i f i ce v a l 啦血o no ft 1 1 eg a i n e dr u l e sb yw l l i c hn l ep o t e m i a lf a c t o ra f i e c 吐n gt l l es t u d 钮t s p e r f b m 龇l c ew 硒d i s c o v e r e d ，h e n c e ，l e 锄i n gs u g g e s t i o nc o u l db em a d e t h ee 伍c i e n c ya i l d f e a s i b i l i t yo fi n 】p r o v e da l g o r i t l l n l sw e r et 1 1 e r c f o r ev a l i d a t e db yp r a c t i c a la p p l i c a t i o n k e y w o r d s ：a 埘b u t e sr e d u c t i o n h e 嘶s t i ca 1 9 0 r i t l n d i s c e n l i b i l i t ym 赫x i v r o u 曲s e t s 独创性声明 学位论文题目：二盘廛塞盛属性约筒簋洼鲅盟窒曼应用 本人提交的学位论文是在导师指导下进行的研究工作及取得的研 究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了 标注。 学位论文作者：糨凡， 签字日期：冽眸j 月召日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生部可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 学位论文作者签名：牡 签字日期：劢眸r 月g 日 导师签名：乍x 吻 签字日期：7 6 年厂月夕日 绪论 第1 章绪论 当今社会己进入信息社会时代，通信技术、计算机技术以及网络技术高速发展，为各界 带来了新的机遇和挑战。如何快速有效地从这些海量数据中提取隐含的知识成为智能决策领 域的研究热点。知识发现及数据挖掘等新型智能数据处理技术在此基础上应运而生。 1 1 研究背景 粗糙集理论出现在1 9 8 2 年，由波兰数学家z p a w l a l c 首先提出，基于研究不完整和不确定 知识表达的一种数学工具【1 1 。最初的研究大多用波兰语言发表，所以当时研究仅局限于东欧国 家。直到1 9 9 1 年，z p a w l a l 【发表了专著r 0 u g l ls e t s ：1 1 1 e o r e t i c a la s p a c t so f r e 雏o n i n ga l 舢t d a t a ，对粗糙集理论作了系统的阐述，奠定了粗糙集理论基础。 1 9 9 2 年，在波兰召开了第1 届国际粗糙集研讨会，主要讨论了集合近似定义的基本思想 及其应用，随后每年召开一次以粗糙集理论为主题的国际研讨会。 1 9 9 3 年，在加拿大召开了第2 届国际粗糙集与知识发现研讨会，此时知识发现正值热门 话题，一些著名的知识发现学者在此次会议中介绍了许多应用扩展粗糙集理论的数据挖掘的 方法与系统。 1 9 9 4 年，在美国召开了第3 届国际粗糙集与软计算研讨会，主要讨论了粗糙集与模糊逻 辑、神经网络、进化理论等融合问题。 1 9 9 5 年，在第4 届模糊理论与技术国际研讨会中，主要针对粗糙集和模糊集指尖关系进 行了讨论。 1 9 9 6 年在日本东京召开的第5 届国际粗糙集研讨会以及2 0 0 1 年在中国召开的研讨会推动 了亚洲地区和我国对粗糙集理论与应用的研究。 粗糙集研究在中国虽然起步晚，但发展很快。2 0 0 1 年“第一届中国粗糙集与软计算学术 研讨会”在重庆邮电大学举办。2 0 0 3 年中国人工智能学会粗糙集与软计算专业委员会成立。 这个专业委员会在不到一年的时间就吸引了中国6 0 多家高校和院所的科研人员。在2 0 0 5 年9 月在加拿大举办的粗糙集研究国际会议上，中国学者的论文甚至超过了会议采用论文总数的 四分之一。 目前粗糙集理论已成为信息科学最为活跃的研究领域之一，它已经被应用于机器学习、 知识发现、决策支持与分析、专家系统、智能控制、图像处理等领域。其中以粗糙集理论为 基础的知识发现过程的研究更是成为研究的热点。目前国内外对于粗糙集的理论研究主要集 中在以下几个方面： ( 1 粗糙集的数学理论方面的研究 主要有粗糙集代数、粗糙集拓扑及其性质、粗糙逻辑等方面的研究。在数学理论方面的 研究是粗糙集理论形成和发展的基础。在粗糙集理论研究中构造性方法和公理化方法是两种 l 西南大学硕士学位论文 最基本的方法。在构造性方法方面，y a o 系统研究了各种特殊类型的粗糙集代数及其相应近似 算子所具备的特征。基于普通的领域关系，y a o 引入了邻域系统的概念并系统地研究了邻域系 统与粗糙近似之间的关系，证明了在邻域系统表示的近似算子意义下p a w l a l c 近似算子和模态 逻辑的可能性和必然性算子是一致的，为建立近似模型提供了强有力的工具2 1 。在公理化方法 方面，“u 等从拓扑的观点提出了由6 个公理组成粗糙集公理组，并证明了公理组的可靠性p j 。 祝峰等简化了该公理组，也证明了简化公理组的可靠性【4 1 。在此基础上，孙辉等进一步研究了 粗糙集公理组的极小化问题，得到了两个简化的粗糙集公理组，且讨论了它们的可靠性和极 小性【5 1 。上述这些工作丰富了粗糙集理论的内涵，同时也从不同角度体现了构造性方法和公理 化方法各自的优势和局限性。 ( 2 ) 数据预处理的研究 粗糙集理论中数据预处理阶段，连续属性离散化是当前的预处理问题之一。目前粗糙集 理论中的离散方法基于两类：一类基本上很少或不考虑粗糙集理论的特殊性，只是把机器学 习等其他学科中的离散化问题借用到粗糙集理论上来，离散化效果并不突出；另一类注意到 了粗糙集理论对决策表的特殊要求，采取结合方法来解决离散化问题。连续属性的离散化使 得粗糙集理论对离散和连续的属性都能处理，扩大了粗糙集理论的应用范围。 数据预处理另外一个重要内容是对不完备信息表的完备化。对于信息表中的某些属性值 是被遗漏的或是空缺问题，目前主要通过以下途径来对信息表中的遗漏数据进行补齐： 一种 途径是简单地将存在空缺( 遗漏) 属性值的实例记录删除，从而得到一个完备的信息表。该 方法只适合处理海量数据，并且遗漏属性值的记录数量远小于信息表所有记录数量的信息表。 第二种途径是将空缺( 遗漏) 属性值作为一种特殊的属性值来处理，它不同于其他任何属性 值，这样就能实现不完备信息表的完备化。第三种途径是采用统计学原理，根据信息表中其 余实例在该属性上的取值的分布情况来对一个遗漏属性值进行估计补充，这样不会影响信息 表中包含的信息量。第四种途径是根据粗糙集理论中数据不可分辨关系来对不完备的数据进 行补齐处理。 ( 3 ) 属性约简算法的研究 在粗糙集理论的各种应用中，属性约简算法一直是粗糙集理论研究中的核心作用问题之 一，对属性约简算法的研究具有重要意义，是知识发现的重要课题。根据粗糙集中的定义寻 找属性的最小约简，会导致组合爆炸问题，已被证明是一个n p - h ：d 问题，因此需要研究更 为有效的约简算法来寻求最优属性约简。目前该方面的研究主要采用启发式算法【6 】、并行算法 f 7 】、导出规则的增量式算法【8 ，9 1 、抽取最优决策规则算法【1 0 1 等来简化或者优化约简算法。和其 他寻优算法结合也逐渐成为人们研究的热点。 ( 4 ) 粗糙集模型的扩展 迄今为止，人们提出了许多粗糙集模型的扩展模型，其中研究主要有可变精度粗糙集模 型【l l 】、基于相似关系的粗糙集模型【1 2 】等。 2 绪论 ( 5 ) 与其他处理不确定性问题的理论或方法的研究 目前关于粗糙集理论与其他处理不确定性问题的理论或方法之间的关系的研究，主要集 中在与模糊数学”】、d s 证据理论、概率统计理论和信息论、神经网络等的相互渗透与补充。 这些研究表明粗糙集理论和它们都有交叉的部分，不能够互相取代，需要相互补充融合，揭 示它们之间内在的联系和本质的区别是非常有意义的研究课题。 除了大量的文献，也出现了许多基于粗糙集理论的分析系统和工具，其中有代表性的研 究系统有：美国l ( a n s a s 大学开发的基于粗糙集的l e r s 实例学习系统；波兰p o z n a n 科技大学 开发的r o s e 系统，用于决策分析；加拿大的r e 西m 大学开发的基于可变精度粗糙集模型的 知识发现系统k d d r ，该系统被用于对医学数据分析，以产生症状与疾病之间的新联系， 同时也支持电信业的市场研究；挪威科技大学计算机与信息科学系知识系统教研组和波兰华 沙大学数学所逻辑教研组的r d s s e t a 等。 1 2 研究意义 粗糙集理论与知识发现关系密切，它支持知识发现的多个步骤，包括建模和具体知识发 现过程。对粗糙集的研究主要基于分类，通过粗糙集理论可以解决的基本问题有：根据属性 值描述对象集：分析属性之间( 全部和部分的) 相关性；属性约简：确定属性重要性；决策 规则生成等。粗糙集运用于知识发现具有如下特点： ( 1 ) 能够处理各种数据，包括不完备的数据以及拥有众多变量的数据； ( 2 ) 能够处理数据的不精确性和部分真实性，包括确定性和不确定性的情况； ( 3 ) 能够在保留关键信息的前提下求取知识的最小表达和知识的各种不同颗粒层次； ( 4 ) 能够从数据中揭示出概念简单、易于操作的模式； ( 5 ) 能够从数据中获取精确且易于检查和证实的规则，特别适于智能控制中规则自动生 成。 与此同时，粗糙集理论运用于知识发现还具有一定优势：粗糙集理论进行数据分析时仅 利用数据本身提供的信息，无需任何先验知识；目前知识发现研究的对象多数是关系型数据 库，关系表可被看作是粗糙集理论中的决策表；知识发现中采用的其他技术不能自动地选择 合适的属性集，而利用粗糙集方法进行预处理以后，能够除掉多余属性，提高发现效率，降 低错误率。粗糙集理论比模糊集方法或神经网络方法在得到的决策规则和推理过程方面易于 被证实和检测。 在整个粗糙集理论体系中，属性约简是粗糙集理论的核心内容，也是知识发现过程中非 常重要的一个环节。一般情况下，信息系统中的条件属性对于决策类的作片j 并不是同等重要 的，有些条件属性可能是多余的，如果把这些多余的条件属性删除掉并不影响原来的系统分 类。属性约简就是指在不影响原来的信息系统分类的情况下，删除不相关或不重要的条件属 3 西南大学硕士学位论文 性，使原有的系统得到简化的一个过程。在不同的信息系统中，或者是在不同的条件下，人 们对属性约简的要求和期望是不一致的。如果在某个系统中存在一些属性，它们的属性值难 以获得，这种情况下我们所需要的就是获取代价较小的属性约简。而通常情况下，我们希望 最后得到的约简包含条件属性的数目越少越好。 因此，求取最小最优约简和提高约简速度是目前以及今后的主要研究目标，本文即针对 此方面研究展开。 1 3 主要内容 本文在深入研究粗糙集理论的基础之上，分析了基于差别矩阵以及基于启发式信息的属 性约简算法，指出其中存在的问题。在差别矩阵和启发式约简算法的基础上提出一种改进算 法，以减少算法在计算时所需的时间和空回复杂度，并获取最小约简。属性约简的值约简方 面，针对目前典型的启发式值约简算法提出改进，以实现更有效地获取规则。最后将改进后 的约简算法系统地应用到学生考试成绩分析中，对成绩表中的数据进行约简处理，对提取的 规则进行科学地评价，找出影响学生成绩潜在的因素，提出学习建议。通过具体的应用，验 证了改进算法的有效性和可行性。 1 4 组织结构 论文主体部分分为6 个章节，各章的内容安排如下： 第l 章绪论 本章研究了粗糙集理论的发展及国内外研究现状、论文研究意义、主要内容和组织结构。 第2 章粗糙集理论 本章主要研究了粗糙集理论的基本概念，包括知识和信息系统的表示、不可分辨关系的 概念、集合的上下近似、属性的依赖性重要性、约简与核、决策表概念及决策规则、决策表 的约简等基本概念，为后续章节奠定基础。 第3 章属性的离散化研究 属性的离散化处理是决策表约简( 属性约简和值约简) 的前提，本章重点分析了目前比 较有影响的几种连续属性离散化方法，重点对连续属性离散化的n s 离散算法进行了研究。 第4 章启发式属性约简算法研究 决策表的约简是粗糙集理论研究的核心部分，决策表约简分为属性约简和属性值约简两 个步骤。本章重点通过对各种属性约简算法的分析和总结，指出目前约简算法存在的问题。 在此基础上，作者针对差别矩阵和启发式约简算法提出了一种改进算法，以减少算法在计算 时所需的时间和空间复杂度，求取最小约简；同时本文还研究了基于启发式值约简算法的改 进算法，以获取更有效的规则。 4 绪论 第5 章验证与应用 将改进后的属性约简算法和值约简算法进行了验证并系统地把算法应用到学生考试成绩 分析中，对得到的规则进行科学地评价，找出影响学生成绩的潜在因素，并提出学习建议。 第6 章总结和展望 总结本文所做的主要工作并展望以后的研究方向。 5 西南大学硕士学位论文 第2 章粗糙集理论 本章主要研究粗糙集理论的基本原理【1 4 】、属性约简及规则生成的方法，作为后续章节的 基础。 2 1 粗糙集基本概念 在传统的数学集合理论中，一个对象与集合的关系只有两种：存在和不存在。而在粗糙 集理论中，对象和集合之间的关系变为三种1 5 】：在集合中；不在集合中；可能在集合中。 租糙集理论假定知识是一种对对象进行分类的能力，也就是说，知识必须与具有或抽象 世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为论域，简称为域。对 于论域及知识的特性并没有任何特别假设，事实上，知识构成了某一感兴趣领域中各种分类 模式的一个族集，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事 实的推理能力1 ，1 6 1 。 2 1 1 知识和信息系统 定义2 1 给定一定有限的非空对象集合玑称为论域。拟u ，称为u 中的一个概念 ( c o n c 印t ) 或范畴( c a t e j ；o r y ) 。灭u u 表示上的一个等价关系。等价关系月将所有集 合【厂划分为不相交的子集，记为凇= ，焉上表示只的等价类的族，关于u 的一个 知识。b r 】= ui 刘妙) 表示关系r 下包含元素x 的等价类。( u r ) 称为近似空间。 定义2 2 一个信息表知识表达系统s 可以表示为： s = ( u ，彳，矿，厂) 其中，u = x l 抛，x n ) 为对象的非空有限集合，即论域；a _ a l ，a 2 ，a i l l ) 为属性的非空集 合；v 为属性值域，y = u 圪；厂：u 彳专y 为一信息函数，表示对每一个口么，工u ， 厂( x ，口) 圪。当信息系统中属性a = cud 是属性集合，c 和d 分别称为条件属性集和决策 属性集，信息系统也称为决策系统，故s 也叫决策表。 2 1 2 不可分辨关系 定义2 3 不可分辨关系斟d ( p ) ：对于每个属性子集p r 且p 矽，则p 中的全部等价关 系的交集称为p 上的一个不可分辨二元关系，也叫不分明关系，记为n d ( p ) 。 刃、【d ( 尸1 ) = ( x ，y ) l ( x ，j ，) u u ，v 口p ，厂( x ，口) = 厂( y ，d ) ) ( 2 一1 ) 如果o ，y ) d 仍( 聊，则称x 和y 是p 不可区分的，且有v p 4 。从上可以看出不可 分辨关系优d ( 尸) 也是u 上的一个等价关系。它把u 划分为有限个集合，称为等价类。在每 一个等价集合中，对象间是不可分辨的。由不可分辨关系导出的等价类构成了知识的粒度， 6 粗糙集理论 从而产生了不确定性。这种不确定性和模糊集所产生的不确定性不同，是由于知识的不完备 性产生的，而模糊集的不确定性是由于自身概念的不确定性产生的。 粗糙集之所以能够描述知识的不确定性，正是基于知识表达中的不可分辨关系。通过一 个不可分辨关系，可以得到决策系统的一个划分，我们称划分后的等价类为不可分辨类。基 于某个属性集a 的所有等价记录的集合，被定义为等价类。b 】p 表示包含元素的p 等价类， 对于协u ，它的p 等价类定义为： b j p = y ui ( x ，y ，肋( 尸) ) ( 2 2 ) 即表示与记录x 具有等价关系p 的记录归为一类，此分类成为p 基于属性集a 的划分， 表示为u 饿d ( p ) = 只，最，只) 。 在粗糙集理论中，我们所要表达的某个子集是完全确定的。但是由于知识粒度的存在， 完全确定的子集不能被表达成由这些粒度产生的基本模块的并集。这样的子集，我们就称为 粗糙集。而对于能够由这些粒度产生的基本模块的并集所表达成的子集，则称为精确集。 粗糙集不能被表示成基本模块的并集，只能包含这些基本模块中的一部分。即对于粗糙 集x ，一个基本模块要么属于集合x ，要么不属于集合x 。下面涉及到的粗糙集的上近似和下 近似就是定义粗糙集的方法。 2 1 3 上近似和下近似 定义2 4 粗糙集对不确定概念的描述是通过下近似( 记为星( x ) ) 和上近似( 记为r ( 彳) ) 这两个精确概念来表示的。上近似和下近似构成了粗糙集研究中的两个基本运算。 对于每个集合x u 和不分明关系r ，x 的上近似和下近似可以用下列式子来表示： 包含在x 中的最大可定义集称为x 的r 下近似： 星( x ) = 扛ui 石】置x ) ( 2 3 ) 即所有包含在集合x 中的等价类的并集。 包含x 的最小可定义集称为x 的r 上近似： 尺( x ) = x ul x 足nx)(24) 即所有与x 的交集不为空且不包含在集合x 中的等价类的并集。 上面给出的粗糙集定义可以通过上下近似来解释： x 为r 的精确集，当且仅当墨( x ) = 尺( x ) ； x 为r 的粗糙集，当且仅当墨( x ) r ( x ) 。 通过粗糙集的上下近似可以将一个论域u 划分为三个不同的区域，分别是：正区域、负 区域和边界区域。正区域中的元素完全属于集合x ；负区域中的元素完全不属于集合x ；边界 7 西南大学硕士学位论文 区域中的元素可能属于、也可能不属于集合x 。下面是三个区域的定义： 定义2 5 一个集合x u 和不可分辨关系r ，x 的r 的正域( p o s i t i v er e g i o n ) 、负域 ( n e g a t i v er c 西0 n ) 和边界域( b o u n d a 叮r e 垂o n 定义： 正域：p o s r ( x ) = 曼( x ) 负域：n e g r ( x ) = u r ( 彳) 边界域：b n r ( x ) = r ( x ) 一( x ) ( 2 - 5 ) 上近似 下近 边界 域u 租糙集x 图2 1 粗糙集概念关系图示 在实际应用中，人们通常要考虑的一个重要问题是：信息系统中的各个属性之间是否具 有某种依赖关系，即从一给定的知识中能否导出另一知识? 这就是所谓的属性依赖性问题。 定义2 6 设集合x 是论域u 上的一个关于r 的粗糙集，定义x 关于r 的近似精度为 味耻翻 ( 2 - 6 ) 其中x 矽；1 | 表示集合中所含元素的数目，称集合的基数或势( c a r d i l l a l 时) 。 显然，o 口r 似) 1 。当口月似) = 1 时，表示不存在边界域，则称集合x 相对于r 时 清晰的；当口r 伍) o ，则集合x 关于r 是 粗糙集合。 x 的r 粗糙度与精确度恰恰相反，表示的是集合x 的知识不完全程度。 定义2 8 信息系统论域中元素x 对集合x 的粗糙隶属函数定义为 以力= 锴 弘8 ， 粗糙隶属函数表示在关系r 下元素x 对集合x 的隶属程度。显然，x ( x ) 【o ，l 】 粗糙集理论 2 2 属性的约简和依赖性 在信息系统中，判断属性及属性值在信息系统中是否必需；在保持原有信息系统分类能 力不变的情况下，如何尽可能地消去冗余知识的问题即是粗糙集属性的约简问题。 2 2 1 属性的依赖性 定义2 9 属性的依赖性：设有决策系统s ：( u ，cud ，v d ，其中c ，d 分别表示条件属性和 决策属性，则决策属性在条件属性下的正区域可定义为： p ( 塔c ( d ) = u 堡( x ) ( 2 9 ) j e u ，d 尸傩c ( d ) 表明根据c 的知识所进行的划分u 圮，能够确切地划入u 仍类的对象集合。 集合的上下近似紧密地与属性的依赖性相联系。如果属性集合d 中的所有属性值都唯一 地由属性集合c 中的属性值确定，则说d 完全依赖于c ，表示为cjd 。如果d 中的部分 属性值由c 中的属性值决定的话，则说d 局部依赖于c 。 决策属性d 对条件属性c 的依赖度定义为： 啼c ( d ) _ 竖掣 依赖度7 c ( d ) 表示在条件属性c 下能够确切划入决策u d 的对象占论域中总对象数的比 率，表达了决策属性对条件属性的依赖程度。 2 2 2 属性的重要性 针对某一具体问题，各属性的重要性是不同的。利用属性的依赖度可以定义属性的重要 程度。通常的做法是将某一属性口从c 中除去，看看它对由c 所产生的正区域的影响程度。 从定义2 9 可知，7 c ( d ) 表示决策属性d 和条件属性c 之间的依赖程度，即用c 来描述 u 烈d ( d ) 的近似程度。因此可以通过当a 从c 中除去时，7 c ( d ) 的改变来衡量属性口的重要 性。 定义2 。1 0 在决策系统s = ( u ，c u d m d 中，口c 的属性重要性定义为： m = 丝焉半小篙 像 可以将盯( c ，d ) g ) 理解为当属性口被除去时，所发生的分类错误率。属性的重要性也可以 扩展到属性集p c 的重要性度量。 定义2 1 1在决策系统s = ( u ，cud ，v f ) 中，p c 的属性重要性定义为 9 西南大学硕士学位论文 嘶= 丝嘉半小锗 2 2 3 约简与核 属性约简包括两个概念：约简和核。属性约简是指关系的最小不可省略子集，而属性的 核则是指最重要的关系集。 定义2 1 2 对于一给定的决策系统s = ( u ，cud m f ) ，条件属性集合c 的约简是c 的一个 非空子集p 。它满足： ( 1 ) v 口尸，口都是d 不可省略的 ( 2 ) p g 哪( d ) = p a 惯c ( d ) 则称p 是c 的一个约简，c 中所有约简的集合记作尼陇) ( c ) 。 可以这样理解，r 为论域中对象的属性集合，在近似表达中有一些属性的特征作用不大， 可以去掉它们而不影响对对象的表达。去除冗余属性后，剩余的属性集仍然保持其等价关系。 定义2 1 3c 中所有不可省略属性的集合称为c 的核，记为a p 见e ( c ) ，则 c d 足e ( o = n r e d ( c ) ( 2 1 3 ) 2 3 决策表及决策规则 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用决策表达形式来表达， 这一工具在决策应用中起着重要的作用。 2 3 1 决策表概念 定义2 1 4 决策表可以定义如下： 一个决策表是一个信息表知识表达系统s = ( u ，彳= c u e y ，厂) ，c 和d 分别称为条 件属性集和决策属性集，cnd = g ，d g 。条件属性和决策属性的等价关系斟d ( c ) 和 等价类i n d ( d ) 分别称为条件类和决策类。 一个决策表的结果属性有时是唯一的，称为单一决策；有时是不唯一的，称为多决策。 对于具有多个决策属性的决策表，可以通过一些方法转变为单一决策。 例2 2 设论域【，= ( x i ，工2 ，x 3 ，x 4 ，墨，石6 ，x 7 ) ，属性集彳= cud ，条件属性集 c = 口，6 ，c ，d ，决策属性集d = 日，决策表如表2 3 所示。 l o 粗糙集理论 表2 3 决策表 uab 由决策表可知： u c = 扛。) ，扛：x 扛，x 扛。) ，扛，k 扛。l & ， u d = k 。，x ：，x ，) 扛。) ，扛，x ，) ) p o s c ( d ) = ( x l ，工2 ，屯，x 4 ，x 5 ，x 6 ，x 7 ) 通过求知识的相对约简的方法，可以得到两个c 的d 约简为 b ，d ) 和 b ，c ) ，c 的d 核为 b ) 。 2 3 2 决策规则 从给定的决策表中生成决策规则是粗糙集的主要应用之一。决策规则用于对已知对象的 分类，或对新对象的分类进行预测。 设s = ( u ，彳，y ，厂) 是决策表，彳= c u d ，c 和d 分别称为条件属性集和决策属性集， 令置和l 分别表示条件类和决策类。 d e s ( 置) 表示条件类五的描述，定义为： d e s ( j 1 ) = ( 口，圪) i 厂( x ，口) = 圪，v 口c ) d e s ( ) 表示条件类的描述，定义为： d e s ( l ) = ( 口，圪) i ( x ，口) = 圪，v 口d 决策规则定义为： 乃：d e s ( t ) 一d 嚣( 艺)置n 巧9 决策表中所有决策规则的集合称为决策算法。 在从决策表中提取决策规则时，如果多个对象的信息( 属性值) 完全相同，则只保留其 中之一( 因为他们反映相同的决策规则) ，然后求条件属性的相对约简，得到约简的决策表。 约简后的决策表具有更少的条件属性，但具有和原决策表相同的知识。重复的行表达同一决 策规则，可以将其移去，这里的行不表示任何实际对象的描述。最后对每条规则进行约简， 并利用决策规则方法求出极小化的决策算法。 i l l o o l 0 o 2 2 o 2 o l 舢 慰 彤 舢 船 1 ：乏 西南大学硕士学位论文 例2 3 继例2 2 中的决策表，表2 4 为它的一个约简。 表2 4 约简的决策表 ub ce x l o2l x 2 o 2 l x 3 202 k 22o x 5 l o 2 】【6 l l2 由此约简决策表生成的决策规则为： ( b ，0 ) 八( c ，2 卜 ( e ，1 ) ( b ，2 ) 八( c ，o 卜+ ( e ，2 ) ( b ，2 ) 八( c ，2 卜+ ( e ，o ) ( b ，1 ) 八( c ，0 卜( e ，2 ) ( b ，1 ) 八( c ，1 ) - ( e ，2 ) ( b ，1 ) 八( c ，2 ) - _ ( e ，1 ) 2 3 3 决策表的简化 决策表的简化就是化简决策表中的条件属性，化简后的决策表具有与化简前的决策表相 同的功能，但是化简后的决策表具有更少的条件属性。因此，决策表的简化在工程应用中相 当重要，同样的决策可以基于更少量的条件，通过一些简单的手段就能获得同样要求的结果。 决策表简化的步骤如下： ( 1 ) 计算条件属性的简式，这等价于从决策表中删除某些列。 ( 2 ) 消除重复行。 ( 3 ) 对每条决策规则求值的简式，这等价于消除属性的多余值。 ( 4 ) 消除重复行。 通过上面的步骤，我们应该了解到：粗糙集对决策表的横向化简是通过求条件属性相对 于决策属性的简式与求每条规则的值简式完成的；纵向化简是通过步骤( 2 ) 和( 4 ) 中将重复行合 并完成的。 化简后的决策表示一个不完全的决策表，它仅包含那些在决策时所必需的条件属性值， 但它具有原始知识系统的所有知识。 经过属性约简得到了推理所要用到的规则知识。然而这些规则并不是最终的决策规则， 其表现在规则的冗余、矛盾、从属等方面，所以就要对规则知识进行检测和处理。 1 2 粗糙集理论 规则的检测方法有以下几个方面： ( 1 ) 等价规则的检测：两条规则在相同的条件下有相同的结论时，称它们为等价规则。 例如，设有如下规则： r 1 l l e l ：i fc 1 = la n dc 2 = 0 t h e nr r u l e 2 ：i fc 2 = oa n dc l = lt h e n r 则它们是等价的。因为系统中采用了生产式规则表示的，所以只要对两条规则部分和结论部 分分别检查其等价性就可得知这两条规则是否等价。此时两条规则中有一条是多余的，可以 从规则库中删去。 ( 2 ) 冗余条