（计算机软件与理论专业论文）粗糙集的不确定度量理论及启发式属性约简算法研究.pdf

摘要 粗糙集理论是近年来发展起来的一种处理不确定、不精确、不完整数据的新的数学 工具【l 】。粗糙集理论自波兰科学家p a w l a k 于1 9 8 2 年提出以来，已经被成功的应用于机 器学习、数据挖掘、决策支持与分析、软计算等领域【2 8 】。 粗糙集理论中根据等价关系对论域进行划分，不同的等价关系对论域进行划分会得 到不同的划分模块，划分越粗，得到的划分模块越大，信息含量越少，不确定性越大； 划分越细，得到的划分模块越小，分类越精确，信息含量越大，不确定性越小。如何度 量不同等价关系对论域划分的粗细及分类的精确程度，如何度量划分的不确定性，即不 确定度量理论的研究是粗糙集理论研究的一个重要方面。 高效的属性约简算法是粗糙集应用于知识发现的基础，寻求快速的属性约简算法是 粗糙集理论的研究热点之一。如何基于粗糙集的不确定度量理论，运用启发信息来简化 计算以找出属性集的最小约简是粗糙集理论研究的一个重要方向。这就需要提出合适的 度量理论，并基于该度量理论设计有效的启发式属性约简算法，因此需要对粗糙集理论 中的不确定度量理论进行研究。 本文对粗糙集理论中的度量理论进行了研究，给出了一个统一的度量集合问贴近度 的方法，根据该方法，提出了度量信息系统、决策系统、不完备信息系统、不完备决策 系统中划分之间贴近度的方法，并对这些系统中的划分贴近度分别进行了系统研究，给 出各系统中划分贴近度的一些性质及相应的理论证明，根据划分贴近度设计了对以上各 系统进行属性约简的启发式算法。 一 针对信息系统，由于知识中属性的逐渐增加或减少的变化，导致知识对论域产生不 同粗细的划分，并得到不同大小的信息粒，给出了两个新的度量方法一粒度熵和粗糙 熵，用于度量知识随着属性的增加或减少对论域产生不同划分时的分辨能力，并基于粒 度熵设计了对信息系统进行属性约简的启发式算法。 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用决策表形式来表 达【9 】。本文根据决策系统的特点，对决策系统中决策属性集相对条件属性集的正域和依 赖度进行了研究，给出了一个新的计算决策系统中正域和依赖度的方法，提出了一个基 于依赖度的决策系统启发式属性约简算法。 关键词：粗糙集理论，划分贴近度，属性约简，粒度熵，依赖度 a b s t r a c t r o u g hs e tt h e o r yi san e wd e v e l o p e dm a t h e m a t i ct o o lw h i c hc a nd e a lw i t hu n c e r t a i n 、i m p r e c i s ea n d i n c o m p l e t ed a t a t l l r o u g hs e tt h e o r yw h i c hw 硒p r 0 南s e db yp a w l a ki n1 9 8 2h 琴b e e ns u c c e s s 如l l yu s e di n m a c h i n el e a r n i n g , d a t am i n i n g ，d e c i s i o ns u p p o r ta n da n a l y s i s ，s o f tc o m p u t i n g ，a n do t h e rf i e l d s l 2 - 8 1 i nr o u g hs e tt h e o r yw ec a nd i v i d et h ed o m a i ni n t od i f f e r e n te q u i v a l e n c em o d u l e sa c c o r d i n gt od i f f e r e n t e q u i v a l e n c er e l a t i o n s t h em o r er o u g ht h ep a r t i t i o ni s ，t h eg r e a t e rt h em o d u l ei s ，a n dw ew i l lg e tm o r e r o u g hc l a s s i f i c a t i o n ；t h ef r e e rt h ep a r t i t i o ni s ，t h es m a l l e rt h em o d u l ei s ，a n dw ew i l lg e tm o r ea c c u r a t e c l a s s i f i c a t i o n h o wt om e a s u r ew h e t h e rt h ep a r t i t i o no ft h eu n i v e r s ei sr o u g ho rf r e e ra c c o r d i n gt od i f f e r e n t e q u i v a l e n c e sa n dt h ea c c u r a c yo fd i f f e r e n tc l a s s i f i c a t i o ni sa ni m p o r t a n ta s p e c ti nt h et h e o r e t i c a ls t u d yo f r o u g hs e tt h e o r y a t t r i b u t er e d u c t i o ni so n eo ft h em o s ti m p o r t a n ta s p e c ti nt h i st h e o r y e f f i c i e n ta t t r i b u t er e d u c t i o n a l g o r i t h mi st h ef o u n d a t i o nf o rr o u g hs e tt h e o r yt ob ea p p l i e dt ok n o w l e d g ed i s c o v e r y r a p i da t t r i b u t e r e d u c t i o na l g o r i t h mi so n eo f t h ef o c u s e so f t h es t u d yi nr o u g hs e tt h e o r y h o wt ou s et h ei n f o r m a t i o nb a s e d o nu n c e r t a i n t ym e a s u r e m e n tt h e o r yt os i m p l i f yt h ec a l c u l a t i o no fa t t r i b u t er e d u c t i o na n dg e tt h em i n i m u m r e d u c t i o no fa t t r i b u t es e ti sa ni m p o r t a n td i r e c t i o no fr e s e a r c h i tr e q u i r e sa l la p p r o p r i a t eu n c e r t a i n t y m e a s u r e m e n tt h e o r y ，a n db a s e do nw h i c hw ec a nd e s i g ne f f e c t i v eh 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 m , s o w en e e dt os t u d yt h eu n c e r t a i n t ym e a s u r e m e n tt h e o r yi nr o u g hs e tt h e o r y i nt h i sp a p e r , w ed e f i n ean e wm e a s u r e m e n to fu n c e r t a i n t y - - c l o s e d e g r e e ，w h i c hc a nb eu s e dt o m g a s u r et h ec l o s ed e g r e eb e t w e e nt w os e t s b a s e do nt h ec l o s e - d e g r e eo ft w os e t s , w eg i v et h ed e f i n i t i o n s o fp a r t i t i o nc l o s e - d e g r e eo fi n f o r m a t i o ns y s t e m ，d e c i s i o n - m a k i n gs y s t e m , i n c o m p l e t ei n f o r m a t i o ns y s t e m a n di n c o m p l e t ed e c i s i o n - m a k i n gs y s t e mw h i c hc a nb eu s e dt om e a s u r et h ec l o s ed e g r e eo fp a r t i t i o ni ne a c h s y s t e m w eg i v e s o m en a t u r e sa n dc o r r e s p o n d i n gt h e o r e t i c a lp r o o fo fp a r t i t i o nc l o s e - d e g r e e ，a n dr e d e f i n e a t t r i b u t ei m p o r t a n t n e s sa c c o r d i n gt ot h ep a r t i t i o nc l o s e - d e g r e ei ni n f o r m a t i o ns y s t e m , d e c i s i o n - m a k i n g s y s t e m , i n c o m p l e t ei n f o r m a t i o ns y s t e ma n di n c o m p l e t ed e c i s i o n - m a k i n gs y s t e ma n dd e s i g nh e u r i s t i c a t t r i b u t er e d u c t i o na l g o r i t h m so ft h ea b o v es y s t e mb a s e do np a r t i t i o nc l o s e - d e g r e eo f e a c hs y s t e m b e c a u s et h ei n c r e a s e m e n to rd e c r e a s e m e n to fa t t r i b u t e si ne q u i v a l e n c er e l a t i o n sw i l ll e a dt ot h e p a r t i t i o n so f t h eu n i v e r s ec h a n g e d , s ow ep r o p o s et w om e a s u r e m e n t st om e a s u r et h ei d e n t i f yc a p a c i t yo f e q u i v a l e n c er e l a t i o n sa n dg i v eah 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 eg r a n u l a re n t r o p y ! i i d e c i s i o nt a b l ei s a s p e c i a la n di m p o r t a n tk n o w l e d g er e p r e s e n t a t i o ns y s t e m , t h em a j o r i t y o f d e c i s i o n - m a k i n gq u e s t i o n sc a l lb ee x p r e s s e di nt h ef o r mo fd e c i s i o nt a b l e w eg i v ean e wm e t h o dt o c o m p u t et h ed e g r e eo fd e p e n d e n c yb e t w e e nd e c i s i o na t t r i b u t e sa n dc o n d i t i o na t t r i b u t e s p r o p o s ea l l 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 ed e g r e eo fd e p e n d e n c yw i t hg o o dp e r f o r m a n c e k e yw o r d s ：r o u g hs e tt h e o r y , p a r t i t i o nc l o s e d e g r e e ，a t t r i b u t er e d u c t i o n ，g r a n u l a re n t r o p y , t h e d e g r e eo fd e p e n d e n c y i v 独创性声明与论文使用授权说明 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写的研究成果，也不包含为获得河南师范大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示了谢意。 签名：盘銎受日期：型星：笸：2 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河南师 范大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 签名：盘蕊函导师签名：垒乏么! 妾日期： y 口? - 舌形 6 7 第一章绪论 第一章绪论 1 1 研究的目的与意义 当今社会，由于计算机与网络信息技术的飞速发展，各个领域的数据和信息急剧增 加，如何在大量杂乱无章的强干扰数据中挖掘潜在的、有利用价值的信息，给人类的智 能信息处理能力提出了前所未有的挑战 9 1 。由此产生了人工智能研究的一个新领域数 据挖掘和数据库知识发现，而粗糙集理论是一种新的处理数据挖掘和知识发现的方法， 可以有效处理不确定、不精确、不完整的数据。 粗糙集理论由波兰科学家p a w l a k 于1 9 8 2 年提出，已经被成功的应用于机器学习、 数据挖掘、决策支持与分析、软计算等领域【2 埘。粗糙集理论正在赢得越来越多的研究 者关注。 粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关 系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一 被划分的集合称为概念【l o l 。粗糙集理论的主要思想是利用已知的知识库，将不精确或不 确定的知识用己知的知识库中的知识来( 近似) n l 画t l o l ；在保持信息系统分类能力不变的 前提下，通过知识约简，导出问题的决策或分类规则。 粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问 题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以 说是比较客观的，由于这个理论未能包含处理不精确或不确定原始数据的机制，所以这 个理论与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的 互补性【i o 】。 粗糙集理论中不确定性主要有两个原因产生，一个原因是直接来自于论域上的等价 关系及其产生的知识模块【1 0 】。粗糙集中根据等价关系对论域进行划分，不同的等价关系 对论域进行划分会得到不同的划分模块，划分越粗，得到的划分模块越大，信息含量越 少，不确定性就越大；划分越细，得到的划分模块越小，分类越精确，信息含量就越大， 不确定性就越小。粗糙集理论中不确定性的另一个原因来自于给定论域里粗糙近似的边 界，边界为空集时知识是完全确定的，边界越大知识就越粗糙或越模糊【l o 】。如何度量不 同等价关系对论域划分的粗细、分类的精确程度及划分的不确定性，即不确定度量理论 本研究得到河南省自然科学基金项目( 0 5 1 1 0 1 1 5 0 0 ) 和河南省高校新世纪优秀人才支持计划( 2 0 0 6 h a n c e t 一1 9 ) 资助 粗糙集的不确定度量理论及启发式属性约简算法研究 的研究是粗糙集理论研究的一个重要方面。 属性约简是粗糙集的核心内容之一【，它是在保持信息系统的分类能力不变的前提 下，删除其中的冗余属性。一个信息系统的知识约简可能不是唯一的，但要找到一个信 息系统的所有约简是一个n p h a r d 问题【l l 】。 高效的属性约简算法是粗糙集应用于知识发现的基础，寻求快速的属性约简算法是 粗糙集理论的研究热点之一。如何基于粗糙集的不确定度量理论，运用启发信息来简化 计算以找出属性集的最小约简是粗糙集理论研究的一个重要方向。这就需要提出一个合 适的度量理论，并基于该度量理论设计有效的启发式属性约简算法，因此需要对粗糙集 理论中的不确定度量理论及启发式属性约简算法进行研究。 作为一种新的智能计算方法，粗糙集理论已在许多工程与科学领域取得了广泛的应 用，受到了越来越多的研究者的关注。粗糙集不确定性的度量理论及属性约简算法是粗 糙集理论研究的重要内容，也是河南省自然科学基金项目研究的一部分内容。 1 2 粗糙集理论研究的历史与现状 粗糙集理论是近年来发展起来的一种处理不确定、不精确、不完整数据的数学工具 【l 】。粗糙集的概念最早是由波兰数学家z p a w l a k 于1 9 8 2 年在计算机与信息科学国 际杂志上发表的论文“r o u g hs e t s ( 粗糙集) 中提出来的。由于最初关于粗糙集理论的研 究大都是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视，研究仅 限于东欧的一些国家，直到2 0 世纪8 0 年代末才逐渐引起各国学者的注意【1 0 1 。1 9 9 1 年， 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 ) ) ，奠定了粗 糙集理论的基础，从此粗糙集理论及其应用的研究进入了一个新的阶段，在国际上掀起 了研究粗糙集的热潮，召开了多次以粗糙集为主题的国际会议，引起了越来越多的科研 人员的关注，极大的推动了对粗糙集理论的研究。美国、加拿大、波兰、日本都有粗糙 集研究的专门机构，粗糙集理论已成为人工智能领域中一个研究热点。 1 9 9 2 年，在波兰召开了第一届国际粗糙集研讨会，着重讨论了集合近似定义的基本 思想及应用。 1 9 9 3 年，在加拿大b a n f f 召开了第二届国际粗糙集与知识发现研讨会，会议的主题 是粗糙集、模糊集与知识发现，这次会议极大地推动了国际上对粗糙集理论与应用的研 究。 2 第一章绪论 1 9 9 4 年，在美国s a nj o s e 召开了第三届国际粗糙集与软计算研讨会，广泛探讨了粗 糙集与模糊逻辑、神经网络、进化论的融合问题。 1 9 9 5 年，在美国w i l m i n g t o n 召开了第四届国际粗糙集研讨会，对粗糙集与软计算 方法的基本观点与关系展开了激烈的探讨。 一 1 9 9 6 年底，在日本东京召开了第五届国际粗糙集研讨会，是第一次在亚洲地区召开 的范围广泛的粗糙集研讨会，推动了亚洲地区对粗糙集理论与应用的研究。 1 9 9 8 年6 月，在波兰召开了第一届国际粗糙集与计算的当前趋势学术会议。 1 9 9 8 年1 0 月，在美国n o r t hc a r o l i n a 召开了第六届粗糙集、数据挖掘及粒度计算国 际研讨会。 1 9 9 9 年，在日本召开了第七届国际粗糙集、模糊集、数据挖掘和粒度一一软计算会 议，研讨会的重点是促进人工智能、软计算和数据库等技术的高度融合，以便解决实际 中具有不确定性与模糊性的大而复杂的问题，主要阐述了当前粗糙集、模糊集的研究现 状与发展趋势。 2 0 0 0 年，在加拿大召开了第二届国际粗糙集与计算的当前趋势学术会议。 2 0 0 3 年，在重庆邮电大学召开了第九届国际粗糙集、模糊集、数据挖掘与粒计算学 术会议。 2 0 0 4 年，在瑞典召开了第四届国际粗糙集与计算的当前趋势学术会议。 2 0 0 5 年，在加拿大召开了第十届国际粗糙集、模糊集、数据挖掘和粒计算学术会议。 2 0 0 6 年，在日本召开了第五届国际粗糙集与计算的当前趋势学术会议。 在国内，对粗糙集理论的研究始于9 0 年代中期，起步相对较晚，但进展迅速，从 2 0 0 1 年起国内召开了七届粗糙集学术研讨会，推动了粗糙集理论在国内的研究与发展， 许多高校和科研院所的专家、学者对粗糙集的理论和应用进行了一系列的研究，主要集 中在对它的模型拓展、数学性质、属性约简算法等研究方面，已取得了令人鼓舞的成果， 每年的粗糙集学术研讨会在规模和质量上均呈良好的增长趋势。 2 0 0 1 年，在重庆邮电大学召开了第一届中国r o u g h 集与软计算学术研讨会。 2 0 0 2 年，在苏州大学召开了第二届中国r o u g h 集与软计算学术研讨会。 2 0 0 3 年，在重庆邮电大学召开了第三届中国r o u g h 集与软计算学术研讨会。 2 0 0 4 年，在浙江海洋学院召开了第四届中国r o u g h 集与软计算学术研讨会。 2 0 0 5 年，在鞍山科技大学召开了第五届中国r o u g h 集与软计算学术研讨会。 粗糙集的不确定度量理论及启发式属性约简算法研究 2 0 0 6 年，在浙江师范大学召开了第六届中国r o u g h 集与软计算学术研讨会。 2 0 0 7 年，在山西大学召开了第七届中国r o u g h 集与软计算学术会议，第一届中国 w e b 智能学术研讨会和第一届中国粒计算学术研讨会。 。 2 0 0 8 年，拟定在河南师范大学召开第八届中国r o u g h 集与软计算学术会议，第二 届中国w e b 智能学术研讨会和第二届中国粒计算学术研讨会。 目前，国内学者从事粗糙集研究的人员越来越多，形成了一支较为稳定的学术队伍， 中国学者在这一领域的影响也越来越大，正成为这一领域的重要科研力量。 1 3 粗糙集理论的研究方向 1 3 1 粗糙集理论的理论研究 目前，粗糙集理论的理论研究主要集中在以下一些方面f i o l ： 一 ( 1 ) 粗糙集模型的拓广。粗糙集模型的拓广，一直是粗糙集理论研究的一个重要 方向，人们已经将粗糙集理论成功拓广到模糊粗糙集模型f 1 2 - 1 6 1 ，变精度粗糙集模型1 7 舶1 j 不完备粗糙集模型【1 研等，并进行了大量研究。对粗糙集模型拓广的研究，扩展了粗糙集 理论及其应用领域。 ， ( 2 ) 不确定性问题的理论研究。由于二元关系中属性的变化会导致对论域划分的 改变，产生不同的知识模块，划分越粗，知识模块越大，分类越粗；划分越细，知识模 块越小，分类越细。在使用上下近似表示一个给定的集合时，边界越大知识就越粗糙或 越模糊。目前，研究者对粗糙集理论及其拓展模型中不确定度量理论进行了大量研究 2 0 - 4 6 1 ，其中度量等价关系对论域划分的粗细的理论主要有信息熵理论【2 2 之3 j ，知识粒度理 论 h i 等；另外研究者还提出了多种粗糙熵2 3 。1 】和粒度度量【3 2 刁7 l ，文献 3 9 - 4 6 1 主要研究粗 糙集拓展模型中的不确定度量理论。 ( 3 ) 与其他处理不确定性方法的理论的研究。在粗糙集理论与其他处理模糊性或 不确定性方法的理论研究中，主要集中在它与概率统计、模糊数学、d s 证据理论和信 息论的相互渗透与补充。 ( 4 ) 高效的约简算法研究。约简的求解是一个n p h a r d 困难问题，导致n p h a r d 问题的主要原因是属性的组合爆炸。高效的约简算法是粗糙集应用于知识发现的基础， 因此寻求快速的约简算法及其增量算法仍是粗糙集理论的研究热点之一。研究者对粗糙 集的属性约简算法及属性值约简算法进行了大量的研究，提出了大量属性约简算法，主 4 第一章绪论 要有基于区分矩阵的属性约简算法【4 7 彤j 、基于信息熵、知识粒度等度量理论的启发式属 性约简算法瞰- 6 2 1 、粗糙集的增量式属性约简算法1 6 3 l 、与粗糙集有关的神经网络算法睁】、 粗糙集拓展模型的属性约简算法【6 5 勰】等。随着研究的进展，属性约简的效率不断提高， 算法的时间复杂度不断降低。粗糙集理论中有效算法研究是粗糙集在人工智能方向上研 究的一个主要方向，这些研究的成功应用有的已经获得了商业价值。 ( 5 ) 与其他数学理论的联系。对粗糙集理论的研究的不断深入，与其他数学分支 的联系也更加紧密。从算子的观点看粗糙集理论，与之关系较紧的有拓扑空间、数理逻 辑、模态逻辑、格与布尔代数、算子代数等；从构造性和集合的观点来看，它与概率论、 模糊数学、证据理论、图论、信息论等联系较为密切。粗糙集理论研究不但需要以这些 理论作为基础，同时也相应地带动这些理论的发展。 ( 6 ) 粒计算。粒计算( g - r a n u l a r c o m p u t i n g ，g r c ) 是信息处理的一种新的概念，覆盖 了所有有关粒度的理论、方法、技术和工具的研究，已成为模糊的、不完整的、不精确 的及海量的信息处理的重要工具和智能研究领域的热点之一，基于粗糙集的粒计算是目 前粗糙集理论研究的一个热点。 1 3 2 粗糙集理论的应用研究 近年来，粗糙集理论的实际应用发展很快，涉及的领域也很广，主要有以下一些应 用领域哪7 0 】： ( 1 ) 决策分析【7 1 。7 3 】：粗糙集分析方法利用数据本身提供的信息即可进行规则提取， 允许决策对象存在一些不太明确、不太完整的属性，给决策者在决策分析时提供正确的 意见。 一( 2 ) 粗糙控制 7 4 - 7 9 1 ：粗糙集根据观测数据获得控制策略的方法称为从范例中学习， 属于智能控制的范畴。基本步骡是：把控制过程中的一些有代表性的状态以及操作人员 在这些状态下所采取的控制策略都记录下来，形成决策表，然后对其分析化简，总结出 控制规则。 ( 、3 ) 专家系统【8 0 l ：在专家系统中，知识获取是一个非常关键的阶段，定义又很困 难。粗糙集理论为构造专家系统中的知识库提供了一条新的途径。 ( 4 ) 客户行为分析【8 1 】：电子商务在国内外已经逐渐开展起来，分析客户的特点是 最大限度提高商业活动的效率和成功机会、实现最大商业价值、降低商业成本的重要因 粗糙集的不确定度量理论及启发式属性约简算法研究 素，而粗糙集在这方面的应用使得商家可以更好的分析市场的潜在客户。 ( 5 ) 文本分类【8 2 1 ：随着电子信息量的急剧增长，信息过滤和信息检索越发重要。 而对于目前大量的高位数据进行分类却是一个很困难的事情，当把这些高位数据运用粗 糙集属性约简技术处理之后，消除了数据集中的冗余知识，从而可以得到一个包含少量 前提条件的规则组成的规则库。这种方法既可以降低关键词集合的维数又可以保持关键 词集合中的信息。 ( 6 ) 股票数据分析【8 3 】：g o l a nr 和z i a r k o 应用粗糙集理论分析了l o 年股票的历史 数据，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街证券 交易专家的认可。 ( 7 ) 医疗诊断【州：在医疗诊断方面，用粗糙集方法根据以往病例归纳出诊断规则， 用来指导新的病例。 ( 8 ) 图像处理【8 5 8 7 l ：粗糙集理论应用于图像处理，+ 主要是将图像包含的像素信息 作为一个知识系统，利用粗糙集中的不可分辨概念、近似集合和知识约简的思想，对图 像进行相关的操作。粗糙集理论应用于图像增强、图像分隔、图像滤波等方面产生了很 好的效果。 ( 9 ) 故障诊断【8 8 】：利用粗糙集理论可以更好的进行故障特征的提取，有利于快速 识别并排除故障。 、 ( 1 0 ) 模式识别【8 2 培3 l ：模式识别是粗糙集理论的一个主要应用方面，在模式识别中 可以利用粗糙集方法进行特征选择、特征表示、分类和聚类，并取得了良好的效果。 1 3 3 粗糙集理论研究的发展趋势 粗糙集理论以其独特的优势正在赢得越来越多研究者的关注，但粗糙集理论仍然有 很多不完善的地方，粗糙集理论今后的研究热点主要包括以下几个方面 7 0 l 。 ( 1 ) 大数据集问题。现实中的数据库已经越来越大，如何降低算法的执行效率和 复杂度，从众多数据中寻找最有用的数据，是粗糙集理论需要应对的一个挑战。虽然目 前这方面已有了一些研究成果，但是还不完善，仍需要进一步研究。 ( 2 ) 缺失值处理方法。在对样本数据进行处理时，往往会遇到数据丢失的问题， 一般把含有丢失数据的信息系统称为不完备的信息系统。造成数据丢失的原因很多，如 对数据测量的误差、数据处理和数据获取的限制等等。如何对缺失值进行更好的处理， 是粗糙集今后的一个研究方向。 6 第一章绪论 ( 3 ) 多方法融合。由于粗糙集在处理数据时存在一定的缺点，因此有必要把粗糙 集和其他不确定方法结合起来。目前比较常用的作法是粗糙集和神经网络及模糊集的结 合应用。虽然在这方面已经取得了一定的成绩，但是还有很多难点并没有解决，仍需进 一步的研究。 一 ( 4 ) 连续数据的离散化。因为粗糙集只能处理离散化的数据，而现实中存在的一 般是连续型的数据，因此，连续数据的离散化变得极为重要。目前已经有了一些这方面 的相关研究，但是这些方法或多或少的都存在一定的缺陷，还没有一种比较公理化的方 法。因此该方面的研究仍是今后研究的热点。 1 4 论文研究内容与结构安排 1 4 1 论文主要研究内容 本文针对粗糙集理论中根据不同等价关系得到论域的不同划分进行了研究，提出了 信息系统、决策系统、不完备信息系统、不完备决策系统中的划分贴近度理论，并根据 划分贴近度理论设计了对以上各系统进行属性约简的启发式算法。针对信息系统中随着 知识中属性的逐渐增加或减少，导致知识对论域产生不同粗细的划分，并得到不同大小 的信息粒进行研究，提出了信息系统中的两个新的度量粒度熵和粗糙熵，并基于粒 度熵设计了对信息系统进行属性约简的启发式算法。根据决策系统的特点，对决策系统 中依赖度进行了研究，给出了一个新的计算决策系统中决策属性相对条件属性集的正域 和依赖度的方法，提出了一个基于依赖度的决策系统启发式属性约简算法。 1 4 2 论文结构安排 第一章主要是绪论。包括以下四部分内容：首先阐述了本文研究的目的与意义：接 着介绍了粗糙集理论研究的历史与现状，粗糙集理论的研究方向；最后介绍了论文研究 内容与结构安排。 第二章主要是粗糙集理论基础知识。首先介绍粗糙集理论基本概念及属性约简，然 后介绍了不完备信息系统和决策系统的基本概念和属性约简；最后对现有粗糙集度量理 论、信息熵理论和知识粒度理论进行了介绍，并分析了信息熵理论和知识粒度理论之间 的关系。 第三章主要提出了粗糙集的划分贴近度理论及基于划分贴近度理论的启发式属性 粗糙集的不确定度量理论及启发式属性约简算法研究 约简算法。首先介绍和分析了现有的粗糙集属性约简算法；然后，提出了粗糙集的划分 贴近度理论及启发式属性约简算法，主要包括：a ) 信息系统中粗糙集的划分贴近度理 论及属性约简算法；b ) 决策系统中粗糙集的划分贴近度理论及属性约简算法；c ) 不 完备信息系统中粗糙集的划分贴近度理论及属性约简算法；d ) 不完备决策系统中粗糙 集的划分贴近度理论及属性约简算法。并分别对所提出的各个算法进行了实例分析和比 较。 第四章主要研究信息系统的粒度熵及基于粒度熵的属性约简算法。首先定义了信息 系统中粒度熵的概念；然后基于粒度熵设计了信息系统的启发式属性约简算法并进行了 实例分析。 第五章主要研究基于依赖度的决策系统属性约简算法。首先介绍了决策系统中依赖 度的概念；然后根据决策系统的特点给出了一种新的计算决策表中依赖度的方法：接着 提出了基于依赖度的决策系统启发式属性约简算法，最后进行了实例分析。 第六章对全文所做的工作进行了总结，然后指出本文的不足之处，最后对下一步的 研究工作给出迸一步的探讨与设想。 8 第二章粗糙集理论基础知识 第二章粗糙集理论基础知识 2 1 粗糙集理论基本概念 本节我们主要介绍粗糙集理论的一些基本概念，关于其具体概念的详细定义，可参 阅有关文献【1 ，9 】。 定义2 1 形式上，四元组萨( 叫，嘲称为信息系统，其中u 表示对象的非空有限集 合，称为论域；么表示属性的非空有限集合；肛u 圪，圪表示属性口的值域；厂表示 a e a u x a _ y 的一个信息函数，它为每个对象在每个属性上赋予一个信息值，即v a e a ，x e 仉 如，口) 圪。通常信息系统可以简记为s - - - ( u a ) 。 若a = c u d ，c 、d 分别为条件属性集和决策属性集，且c n d = g ，则具有条件属 性和决策属性的信息系统称为决策系统。若d = 矽，则称信息系统为数据表，否则称信 息系统为决策表。 。 信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象 的属性，对象的信息是通过指定对象的各属性值来表达。 定义2 2 设双叫，嘲为信息系统，v p c a ，定义属性集p 的不可区分关系1 n d ( p ) 为： 刷：d = ( ( x u x 矶v a e p ，他，a ) ：j q y ，口) ， ( 2 一1 ) 如果( x 力刷明，则称z 和y 是p 不可区分的，对v p c a ，不可区分关系i n d ( p ) 是u 上的等价关系，u i n d ( p ) = x i , x 2 , - - 疋 ( 简记为聊d 表示不可区分关系n o ( p ) 在u 上导出的划分，石u ，五，石n 再= ，对于i c j ( i j = l ，2 ，朋) ，称为泖中的等 价类。对于v z u 吲j p 表示包含元素置的尸等价类。 定义2 3 设萨( u a ，m 为信息系统，v p g a ，埏u 为论域u 的一个子集，若u p = u i n d ( p ) = y l ，圪，) ，定义两个子集： 一p x = u ( 】1 儿u p ，r c _ x ， ( 2 2 ) 腑= u y i y e u p ，巾脖) ， ( 2 3 ) 分别称它们为x 的尸下近似集和尸上近似集。定义x 的p 边界域，x 的p 正域和x 的 p 负域分别为： bnp(x)=xpx(2-4) 9 粗糙集的不确定度量理论及启发式属性约简算法研究 e o s p ( x ) = g x ， ( 2 5 ) n e g p ( x ) = u - p x ， ( 2 6 ) 丛或p o s p ( x ) 是根据知识p 判断肯定属于x 的u 中元素组成的集合，蹦是根据知识p 判断可能属于x 的u 中元素组成的集合，b n p ( x ) 是根据知识尸既不能判断肯定属于x 又不能判断肯定属于u - x 的u 中元素组成的集合，8 n e ( x ) 是根据知识p 判断肯定不属 于x 的u 中元素组成的集合。 t。， 定理2 1( 1 ) x 为p 可定义集当且仅当跗= 蹦。 ( 2 ) x 为p 粗糙集当且仅当p x p x 。 根据x 的上近似集和下近似集，可定义四种不同的重要粗糙集：，。 ( 1 ) 如果丛矽且尸x 以则称x 为p 粗糙可定义。 ( 2 ) 如果丛= 矽且麒阢则称x 为p 内不可定义。 ( 3 ) 如果丛矽且砑= u ，则称j 为p 外不可定义。 ( 4 ) 如果蹦= 矽且砑= u ，则称x 为p 全不可定义。 如果集合x 为p 粗糙可定义的，则意味着我们可以确定u 中某些元素属于x 或也 如果集合彳为p 内不可定义的，则意味着我们可以确定u 中某些元素是否属于磁 但不能确定u 中的任一元素是否属于兄 如果集合石为p 外不可定义的，则意味着我们可以确定u 中某些元素属于工但 不能确定u 中任一元素是否属于- x 如果集合x 为p 全不可定义的，则意味着我们不能确定u 中任一元素是否属于x 或- x 定义2 4 设s = - ( u , a ，嘲为信息系统，p g a ，令乒泖= 坦，鼎 ，则根据p ，f 的近似分类精度定义为： 近似分类质量定义为： 1 0 l 甄l 邮旷卜丽1 l 丛f l y e ( f ) - 矿 ( 2 7 ) ( 2 8 ) 第二章粗糙集理论基础知识 近似分类精度描述的是当使用知识p 对对象分类时，可能的决策中正确决策的百分比； 近似分类质量表示的是应用知识p 能确切的划入f 类的对象的百分比。 2 2 知识约简 知识约简是粗糙集理论的核心内容之一。我们知道，知识库中的知识( 属性) 并不是 同等重要的，对于特定的应用( 决策) ，可能用到的属性并不相同，有些属性可能是冗余 的。所谓知识约简，就是在保持知识库分类能力不变条件下，删除其中不相关或不重要 的知识( 属性) 。 “ 定义2 5 设尸为一个属性集合，a e p ，若优d 硼严 口) ) ，则称a 为p 中不必 要的，否则称a 为尸中必要的。如果每一个口p 都为p 中必要的，则称尸为独立的， 否则称p 为依赖的。 定义2 6 设s = - ( u a ，哪为信息系统，q c p = _ a ，如果q 是独立的，p l n d ( q ) = i n d ( p ) ， 则称q 为尸的一个约简。 由上面的定义可知，约简有两个方面的性质：首先，约简所表达的对系统的划分与 原来的知识库所形成的划分是一致的，即约简所表达的知识和原来的知识具有相同的表 达能力；其次，就是独立性与最小性，约简是能够表达原来知识库的最小集合，约简里 边一般不可再进行约简【3 9 】。 定义2 7 设弘( 叫，z j ) 为信息系统，p c a ，p 中所有必要属性组成的集合称为尸的 核，记作c o r e ( p ) ，c o r e ( p ) = i q r e d ( p ) ，r e d ( p ) 表示p 的所有约简。 在决策系统中，一个分类相对于另一个分类的关系十分重要，下面我们给出知识的 相对约简和相对核。首先，我们定义一个分类相对于另一个分类的正域。 定义2 8 设s = ( u , c ud ，蚴为决策系统，p c c ，决策属性d 的尸正域记为p o s e d ) ， p o s k d ) = u 矽l y eu d ， ( 2 9 ) d 的尸正域是u 中所有根据分类u p 的信息可以准确地划分到关系d 的等价类中去的 对象集合。 定义2 9 设s = ( u , c u d ，z j ) y g 决策系统，r e p c _ c ，若p o s t , 一( ， ( d ) = p o s p ( d ) ，则称， 为p 中d 不必要的，否则称，为p 中d 必要的。若p 中每个，都为p 中d 必要的， 则称尸为d 独立的。 定义2 1 0 设s = ( u , c u d ，m 为决策系统，若q c p c c ，p o s e d ) = p o s t , ( d ) j tq 是d 粗糙集的不确定度量理论及启发式属性约简算法研究 独立的，则q 是p 相对d 的相对约简。 定义2 1 1 设s 气u , c u d ，v j ) 为决策系统，若p c _ c ，则p 中所有d 必要的属性组成 的集合称为p 的d 核，简称为相对核，记为c o r e o ( p ) ： 。 c o r e d ( p ) = n r e a o ( p ) ， ( 2 1 0 ) 其中r e d o ( p ) 表示所有尸的d 约简构成的集合。 定义2 1 2 设蹦叫，蚴为一个信息系统，p 、q 为u 上的等价关系，令一 k = l p o s p ( a ) l i 刎， ( 2 1 1 ) 这里i i 表示集合的基数。我们称知识q 是| ( 0 七1 ) 度依赖于知识尸的，记作p - 七q ，七 可以看作q 和p 间的依赖度。当k = - i 时，我们称q 完全依赖于尸；当0 0 。 定理2 5 设u 是一个论域，p 是汐的一个条件属性集合，d 为决策属性，且论域u 是在p 上相对于d 一致的，则尸中的一个属性a 是p 相对于决策属性d 不必要的，其 充分必要条件为域 田l d = 坝 田i e - a ) 。 2