（运筹学与控制论专业论文）基于粗糙集的数据挖掘属性约简算法研究.pdf

摘要 摘要 粗糙集理论是由波兰数学家z p a w i a k 在1 9 s 2 年提出的，是继概率论、模糊数 学、证据理论之后又一种处理不确定性的有效数学工具。该理论的特点是不需要 任何先验知识，或任何附加信息，就能有效地分析和处理不精确、不完整和不一 致的信息。并从中发现隐含的知识，揭示潜在的规律。数据挖掘和知识发现是从 现存的数据库、数据仓库或其它信息库中挖掘有价值的知识的过程。粗糙集理论 是一种新的数据挖掘技术。 本文就粗糙集理论及其在数据挖掘中的应用方法进行了较为深入系统地研 究。重点研究了扩展粗糙集模型：基于连续属性的粗糙集模型及其约简算法；不 完备信息系统下粗糙集模型及其约简算法；以及更一般的集值信息系统及其约简 算法。主要研究工作包括： 1 对近年来粗糙集理论及其相关的数据挖掘方法进行了综述。 2 深入研究了各种常见的粗糙集模型及其性质；针对信息系统的多样性，给 出了基于粗糙集的刻画方式。 3 属性约简是粗糙集理论研究的核心问题之一，现已证明，寻找信息系统的 最小约简是n p _ h a r d 问题。目前已经提出了一些有效的算法，然而其算法复杂度都 比较高，因此还需要进一步研究属性约简的有效算法，本文就常见粗糙集模型， 给出了一般形式的基于代数或信息论下的改进属性约简算法。 4 研究了不完备信息系统粗糙集模型，并提出了基于限制容差关系的属性约 简算法；提出了集值信息系统及基于其上的属性约简算法；研究了连续属性的信 息系统及属性约简算法。并且针对以上提出的模型及算法，给出了完整的实例， 进一步验证了其应用于实际系统的有效性和实用性。 关键词：粗糙集，属性约简，数据挖掘，不完备信息系统，集值信息系统 电子科技大学硕士学位论文 a b s t r a c t r o u g h s e tt h e o r yi sp r o v i d e db yz p a w i a ki n19 8 2 i ti sam a t l lt h e o r yt h a tp r o c e s s t 1 1 en o n a c c u r a t ea f t e rp r o b a b i l i t yt h e o r y ，f i l z 巧t l l e o r ) ra 工1 dd e m p s t e r - s l l a f e ln o t n e e d i n go t h e ri n f b m a t i o no rp r c v i o u sk n o w l e d g et 1 1 i sm e o r yc a l la n a l y z ea 1 1 dp r o c e s s t l en o n a c c u r a t e ，n o n - i n t e g r i t yd a t aa n dt l l e nm i n el a t e n tk n o w i e d g e d a t am i n i n ga i l d h l o w l e d g ed i s c o v e r yi n d a t a b a s e si sd r a w i i l gk n o w l e 如ef b mm ed a t a b a s e ，d a t a w a r e h o u s eo ro t h e rd a t a b a s e s r o u g hs e tt 1 1 e o r yi san e wd a t am i n i n gt e c l l l l 0 1 0 9 y a f t e rt 1 1 0 r o u 曲r e s e a r c ho fr o u g hs e ta n di t sa p p l i c a t i o ni nd a t am i n i n g t h ep 印e r m a “yr c s e 删le x p a n s i o nm o d e lo fr o u g hs e t ：r o u 曲s e tm o d e lb a s e do nc o n t i l l u o u s a t t r i b u t ea n da l g o r i t l l m0 fr e d u c t i o n ；m o d e la n da l g o r i t h mf o rr e d u c t i o no fk n o w l e d g e u n d c ri n c o m p l e t e 证f o 皿a t i o n s y s t e m s ；r o u g hs e t m o d e la n dr e d u c t i o nb a s e d m u l t i v a l u e di n f o r m a t i o ns y s t e m t h cm a i nr e s e 盯c hi n c l u d e ： 1 a ns u r v e yo nr o u g hs e ta n dr e l a t i v et e c h n 0 1 0 9 y0 f d a t am i n i n g 2 t h o r o u g hr e s e a r c ha l lk i n d so fr o u g hs e tm o d e l p m v i d e dt h em c m o d t os h o w d i v e r s ei n f o r n l a t i o ns y s t e m 3 t h ea t t r i b u t er e d u c t i o no fi n f 0 珊a t i o ns y s t e mi st h em a mt o p i ci nr o u 曲s e t t h e o r y b u t ，j ti sp r o v e d 也a tg e t t i n gt h eb e s t 棼e d u c t i o no ra 1 1r e d u c t i o nj san pp r o b l e m t h e r ei sp 嘣i n gf o n v a r ds o m ev a l i da l g o r j t h mc l l r r e n t l y h o w e v e rc o m p l e x i t yi sa l l h i g h e r t h ep 印c rg i v ei m p r o v e dg e n e r a lf o ma i g o r i t l l mo fa t t r i b u t er e d u c t i o nb a s e do n a l g e b r aa 1 1 dt h ei n f b m a t i o nt l l e o r i e s 4 r e s e a r c h i n gt h em u g hs e tm o d e li ni c o m p l e t ei n f o n n a t i o ns y s t e m a n d p r o v i d i n g 也er e d u c t i o na l g o r i 也mb a s e do n1 i m i t e dt o l e m c er e l a t i o n p u t d n gf b 刑8 r d m u l t i v a l u e di n f o r m a t i o ns y s t e ma n da 嘶b u t er e d u c t i o nb a s e do ni t g i v ea l g o r i t h mo f a t t r i b u t er e d u c t i o nb a s e do ni n f o m l a t i o na b o u tc o m i n u o u sa t t r i b u t e t h el a s t l y ，t h e p a p e rg i v ec o m p l e t es o l i de x 锄p l et op r o v et h a t a 1 1m o d e la n da l g o r i t l l m g i v e n p r e v i o u s l yi su s e m l n e s sa 1 1 dv a l i d 姆i na p p l i c a t i o n k e ) w o r d ：r o u 曲s e tt h e o a t t r i b u t er e d u c t i o n ，d a t am i l l i n g ，i n c o m p l e t ei n f b r n l a t i o n s y s t e m ，m u l t i v a l u e di n f o 珊a t i o ns y s t e m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：二象粤闲驴 日期：为眵年1 7 月7 口曰 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲卑弛聊虢盟兰 日期：为艿年1 7 月日 第一章绪论 1 1 课题的研究意义与背景 第一章绪论 当今全球信息大爆炸，每个人都面临着海量数据，如何从中获取有价值的信 息成为一个首要问题。由此，数据挖掘于2 0 世纪8 0 年代中后期出现了，并在9 0 年代得到了飞速的发展。数据挖掘【1 2 ，”( d a t a m i n i n g ) ，就是从大量数据中提取或 “挖掘”隐含的、事先未知的潜在有用信息。数据挖掘涉及到多学科技术的集成。在 数据挖掘中，所存储的数据往往含有大量冗余或者不完整的属性，严重降低了数 据挖掘算法的时间效率和算法质量。如何删除冗余的属性，却是一个极其具有挑 战性的工作。这就是特征选择所需要完成的工作。近来，粗糙集理论在数据挖掘 与知识发现方面得到了广泛的发展。粗糙集理论的特点是不需要预先给定某些特 征的数量描述，而是直接从给定问题的描述集合出发，通过不可分辨关系和不可 分辨类确定给定问题的近似域，从而找出该问题的内在规律。这种思想和方法给 数据挖掘注入了新的生命力，大大促进了数据挖掘的发展。 1 2 粗糙集及其数据挖掘当前的发展情况 1 2 1 粗糙集提出的背景 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真与假二值之间。 长期以来许多逻辑学家和哲学家就致力于研究含糊概念，1 9 0 4 年，谓词逻辑创始 人g f r e g e 就提出了含糊( v a g u e ) 一词，并把它归结到边界线区域，即在全域上存 在一些个体既不能在其某个子集上被分类，也不能在该子集的补集上被分类。2 0 世纪6 0 年代，l a z a d e h 提出了模糊集1 4 】( f u z 巧s e t s ) ，不少科学家试图通过该理 论解决现实中含糊的概念，然而遗憾的是，模糊集是不可计算的，无法给出数学 公式描述这一含糊概念，因此也无法计算出它的边界线上的具体含糊元素数目。 1 9 8 2 年，z p a w l a l ( 针对g f r e g e 的边界线区域思想提出了粗糙集 5 1 u 曲s e t s ) ，他 把那些无法确认的个体都归属于边界线区域，而这些边界线区域被定义为上近似 和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数 皇王型堇盔堂堡主堂焦兰奎 学公式描述，所以含糊元素数目可以被计算出来，即在真假二值之间含糊程度是 可以计算，从而实现了g f r e g e 的边界线思想。粗糙集理论主要思想在于它恰好反 映了人们用粗糙集方法处理不分明问题的常规性，即以不完全信息或知识去处理 一些不分明现象的能力，或依据观察、度量到的某些不精确的结果而进行分类数 据的能力。 1 2 2 粗糙集理论及其发展 粗糙集理论是继概率论，模糊集，证据理论之后的又一个处理不确定性的数学 工具。该理论是一种刻画不完整性和不确定性的工具，能有效地分析和处理不精 确、不一致、不完整等各种不完备信息，并从中发现隐含的信息。粗糙集是一个强 大的数据分析工具它能表达和处理不完备信息；能在保留关键信息的前提下对 数据进行化简并求得知识的最小表达式；能识别并评估数据之间的依赖关系，揭 示出概念简单的模式；能从经验数据中获取易于证实的规则知识，特别适于智能 控制。粗糙集自问世以来，无论在理论或应用上都是一种新的、最重要的并且是 迅速发展的一门既有理论又有应用的研究领域。 粗糙集是一种软计算方法。软计算( s o rc o m p u t i n g ) 的概念是由模糊集创始 人z a d e h 提出的传统的计算方法即所谓硬计算，使用精确、固定和不变的算法来 表达和解决问题；而软计算的指导原则是利用所允许的不精确、不确定性和部分 真实性得到易于处理、鲁棒性强和成本较低的解决方案，以便更好地与现实系统 相协调。软计算旧的主要工具包括粗糙集、模糊逻辑、神经网络、概率推理、信 度网络、遗传算法与其他进化优化算法、混沌理论等。 粗糙集理论与其它一些软计算理论有相似之处，特别适合证据理论 ( d e m p s t e r - s h a f e r ( d s ) ) ，两者之间的主要区别在于d s 理论利用置信和似然函数作 为主要工具，而粗糙集理论利用上、下近似集。至于模糊集和粗糙集，它们之间 并不互相冲突，而是互相补充的，它们有处理问题各自的方法。 粗糙集理论作为一种处理含糊性和不确定性信息的新的数学方法，自提出之 后许多学者对该理论及其应用进行了坚持不懈的研究。1 9 9 1 年，z p a w l a l 出版了 第一本关于粗糙集的专著i ”，它奠定了粗糙集理论的基础：1 9 9 2 年rs 1 0 州n s k i 出版 了关于粗糙集应用研究的论文集i ，推动了国际上对粗糙集理论与应用的深入研 究。1 9 9 2 年，在波兰k i e k r z 召开了第一届国际粗糙集学术讨论会，主要讨论了集合 近似定义的基本思想及其应用。z p a w l a k 于1 9 9 5 年概括性地介绍了粗糙集理论的 2 第一章绪论 基本概念及其具体研究进展。1 9 9 9 年，在日本召开第七届关于粗糙集、模糊集、 数据挖掘和粒度的软计算国际会议，主要阐述了当前粗糙集、模糊集的研究现状 和发展趋势。2 0 0 0 年，在加拿大召开了第二届粗糙集和软计算的当前趋势学术会 议。当今许多重要的国际学术会议都把粗糙集理论的研究列入主要内容之一。 1 2 3 粗糙集理论的研究现状 从粗糙集理论出现到发展这短短的二十多年时间，粗糙集理论得到了迅猛的 发展，目前已经成为人工智能领域一个研究的学术热点。无论是在理论还是实际 应用的很多都取得了惊人的成果。目前粗糙集的研究主要体现在以下几个方面， 见文献f 9 ，1 0 】。 ( 】) 粗糙集理论方面的研究 粗糙集理论的研究历史较短，粗糙集概念的定义尚未完全统一，定义观点的 不同往往带来研究的侧重点不同。当前，对粗糙集理论的研究工作主要集中在以 下几个方面： 粗糙集数学性质方面的研究：基于粗糙集的代数系统、粗糙拓扑结构等方面。 粗糙集模型的推广：一直是粗糙集理论研究的主流方向，主要有两种方法： 构造性方法、公理化方法。 与其他处理不确定性方法的理论的研究：主要集中在与概率统计、模糊数学、 神经网络n ”、d s 证据理论和信息论的相互渗透和互补。 粗糙集高效算法的研究：找出信息系统的所有约简或最优约简是一个n p 完全 问题，目前研究主要集中在约简的启发式算法f 1 2 】、并行算法、导出规则的增量式 算法方面以及与粗糙集有关的神经网络、遗传算法等。 粗糙逻辑与粗糙推理：研究粗糙逻辑【1 3 l 的五个逻辑值，即真、假、粗糙真、 粗糙假和粗糙不相容，以及建立在其上的粗糙推理。 以上这些研究有的受应用推动而产生，有的则是纯理论方面的。 ( 2 ) 粗糙集理论应用方面的研究 粗糙集理论可以解决的主要问题包括：数据约简、数据依赖的发现、数据重要 性的评估、决策产生算法、数据的近似分类、数据异同的发现、数据中模式的发 现和因果关系的发现等。粗糙集方法在很多方面中都有应用： 数据挖掘：粗糙集方法可以有效的获取知识、已成为数据挖掘中的一个重要 方法。 电子科技大学硕士学位论文 模式识别：用粗糙集方法进行特征提取，选取能表征该模式的特征项。 医疗诊断：粗糙集方法根据以往的病例归纳出是否得病的决策规则，并用这 些决策规则来诊断新的病例。 决策分析：利用信息系统( 决策表) ，粗糙集理论可以获得决策规则。 粗糙集w 曲知识发现：随着i n t e n l e t 的迅速扩展，w 曲页面的增加，利用粗 糙集进行w 曲知识发现。 与其它软计算方法结合：粗糙集如何与其他方法结合，将是提高知识发现效 率的一种重要途径。 1 3 论文结构及内容介绍 本论文的组织结构是这样的：第一章绪论，介绍研究背景、意义及相关知识。 第二章粗糙集理论相关知识，介绍信息系统及粗糙集的基础知识。第三章基于 粗糙集的属性约简，主要研究了基于几种常见粗糙集模型的属性约简算法及当前 的研究进展。第四章粗糙集与数据挖掘，本章主要探讨了当前数据挖掘的发展情 况；研究了粗糙集理论在数据挖掘领域的应用。第五章扩展粗糙集模型及其约简， 主要研究了不完各信息信息系统下、连续属性信息系统、集值信息系统下的粗糙 集模型及其约简算法，以及与其他软计算方法相结合的应用研究给出实际的应用 背景。第六章对全文进行总结，对仍然需要解决的问题提出解决方案，提出今后 的可行的研究方向。 本论文所完成的工作如下： ( 1 ) 常见粗糙集模型下属性约简算法的推广和改进 针对经典粗糙集关系下的各种模型提出或改进属性约简算法。 ( 2 ) 粗糙集理论的完善和推广 研究连续属性信息系统的粗糙集模型及其约简算法。 将粗糙集推广到不完各信息系统中。 集值信息系统下的粗糙集模型及其约简算法。 ( 3 ) 应用粗糙集理论推进数据挖掘的发展 基于更一般信息系统的粗糙集模型，进行数据约简，提取决策规则。 第二章粗糙集理论相关知识 第二章粗糙集理论相关知识 2 1 粗糙集理论的基本概念 2 1 1 粗糙集的基本概念 粗糙集是一种新的处理模糊和不确定性知识的数学工具。其主要思想是在保 持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。粗糙集 理论是建立在分类机制基础上的，它将分类理解为在特定空间上的等价关系，而 等价关系构成了对该空间的划分。其主要思想是利用已知的知识库，将不精确或 不确定的知识用已知的知识库中的知识来( 近似) 刻画。该理论与其它处理不确 定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外 的任何先验信息。并且与概率论、模糊数学、证据理论等其它处理不确定或不精 确问题的理论有很强的互补性。 设u 是非空有限论域，r 是u 上的二元等价关系，r 称为不可分辨关系，序 对一= ( u ，r ) 称为近似空间。v ( x ，y ) u u ，若( x ，y ) 月，则称对象x 与y 在近似空 间4 中是不可分辨的。u 五是v 上由r 生成的等价类的全体，它构成了u 的一个 划分。可以证明，u 上的划分可以与u 上的二元等价关系之间建立一一对应。u r 中的集合成为基本集或原子集。若将u 中的集合称为概念或表示知识，则 一= ( u ，五) 称为知识库，原子集表示基本概念或知识模块。任意有限的基本机的并 和空间都称为可定义集。否则称为不可定义的。可定义集也称为精确集，它可以 在知识库中精确的描述或定义，可表示已知知识，可以验证所有可定义集全体可 构成u 上的一个拓扑。 对于论域u 上任意一个子集工，z 不一定能用知识库的知识来精确地描述， 即彳可能为不可定义集，这时就用关于一的一对下近似心和上近似五x 来近似 地描述。其定义如下： 型= u 【叫l 【x 】z = 协u j 【叫l ) r r = u x 】l 【石】n x o ) = x u i 【x 】n x a ) 其中 z 是x 所在的尺等价类或定义为： 电子科技大学硕士学位论文 蚪= u y u 矗f y 田 冗y = u 】，仨u r f 】，n z a 下近似墨x 也称为x 关于a 的正域，记做p 0 s ( x ) ，它可以解释为由那些根据现 有知识判断出肯定属于z 的对象所组成的最大集合，上近似五可以解释为由那些 根据现有知识判断出可能属于肖的对象所组成的最小集合。u j 讶称为z 的负域， 记做 田( x ) ，它可以解释为由那些根据现有知识判断出肯定不属于x 的对象所组 成的集合。星z 豆r 称为边界域，它可以理解为由那些根据现有知识判断出可能属 于x 但不能完全肯定是否一定属于互的对象所组成的集合，记做丑是( 卫) 。并且以 下等式成立： 豆r = p 傩( x ) u 引矿( z ) = 堡u 删( x ) = u 星( x ) ( 其中表示补) 。 由定义，以下性质成立； ( 1 ) x 为r 可定义集当且仅当心= 科 ( 2 ) 为r 可粗糙集当且仅当肘冠 ( 3 ) 肛z 职，基a 豆g = o ，星u 豆u = u ( 4 ) 豆( x u y ) 夏r u 豆l ，基( x n y ) 墨x u 基y ( 5 ) z 】r 等星r 至堡】，r 】，j r x r 】， ( 6 ) 星( r uj ，) 等星z u 堡r ，承x n 】，) j 豆r u 豆y ( 7 ) 星( 工) 一承j ，) ，豆( x ) = 基( z ) ( 其中表示集合补) ( 8 ) 星( 星( x ) ) = 夏( 星( z ) ) = 星( r ) ，豆( 豆( 盖) ) = 星( 豆( 。r ”= 夏( y ) 称( 2 u ，n ，u ，一，曼两为粗糙代数系统， 由等价关系r 定义的x 关于u 的近似精度为 珞( z ) = f f i 心 其中i z i 表示集合工的基数，x g 。近似精度反映了知识x 中肯定在知识库 中的部分在现有知识的百分比。显然对于每一个r 和x u 有0 璇( x ) 1 。当 强( x ) = 1 时，z 的边界域为空集，即集合x 为r 可定义的；当啦) 1 时，集合 z 有非空月边界域，集合z 为月不可定义的。 由等价关系r 定义的工关于近似空间u 粗糙集性测度定义为； 6 第二章粗糙集理论相关知识 所( z ) = 1 一j 丛l i 删i 显然，o m ( 工) s 1 ，x 是可定义的当且仅当所) = 0 ，x 是粗糙的当且仅当 口。( ) o 。粗糙性测度反映了知识的不完全程度。 粗糙集理论中还对集合类关于近似空间定义了下近似和上近似。设 f ： 茧，托， ，以) 是由u 的子集所构成的集类，则f 关于近似空间u 的下近似基f 和上近似豆，定义为 星f = 瞄，执，瞄) 面= 豇，脱，甄) 根据r ，的近似分类精度和近似分类质量分别定义为： 强( f ) = i 星( x ) j i 豆( * ) l f - lf = i 肪( f ) = 1 8 ( ) i i u i l = 1 近似分类精度描述的是当使用r 对对象分类时，可能的决策中正确决策的百分 比；而近似分类质量表示用r 能确切地划分，类的对象的百分比。 2 。1 2 其它常见粗糙集模型 1 变精度粗糙集模型( v a r i a b l ep r e c i s i o nr o u g hs e tm o d e l ) 经典粗糙集模型的一个局限性是它所处理的类别归属必须是完全肯定的，因 为分类的最小单元是等价类，严格按照等价类缺乏柔性；只有“包含”或“不包含”， 而没有某种程度上的“包含”或“属于”。这样将某个与集合有相当大的重叠的等价类 和另一个与集合重叠很小的等价类都同等对待地归入边界域，就很不合理；另外， 原始模型对数据过分拟合，当出现噪声数据时，抗干扰能力差，对新对象的预测 能力降低。 变精度粗糙集模型是对p a w l a k 粗糙集模型的扩充，该模型允许一定程度的错 误分类率存在，这样不仅进一步完善了近似空间的概念，而且有利于用粗糙集理 论从认为不相关的数据中发现相关性。 设z 、y 表示有限论域u 的非空子集，令 c ( x ，y ) = 扩j z n y | i x if 妻罡： 则称c ( x ，j ，) 为集合关于集合y 的相对错误分类率。 电子科技大学硕士学位论文 令o 口 o 5 ，定义多包含关系为 口 c ( 盖，y ) 】，三石 多包含关系的直观意义是卫与】，中公共元素的数目大于z 中元素数目的 5 0 定义2 1 设( 矿，r ) 为近似空间，其中论域v 为非空有限集合，r 为u 上的等 价关系，u r = 蜀，易，e ) 为r 的等价关系或基本集构成的集合。对于z u ， z 的口下近似为： 一 出z = u 征u r l x e ) 或野x = u e v r ic ( e ，z ) 历 出x 也称x 的卢正区域，记为p o s 和( z ) 定义j 的的上近似为：昂z = u 征e u r lc ( e ，x ) 1 一卢) 定义x 的卢的边界域为：6 n 冶( z ) = u e u 则 c ( e ，z ) 1 一历 定义z 的口的负区域为： 铝即( = u 怛u 矗fc ( e ，1 一) x 的口正区域可理解为讲u 中的对象以不大于卢的分类误差分于石集合。z 的口负区域理解为将u 中的对象以不太子卢的分类误差分于x 的补集( x ) 随着分类误差口的增大，z 的下近似集扩大，上近似集缩小，边界域缩小； 变精度模型一定程度上补偿了原始定义的死板、生硬，柔化了边界，使分类更加 合理准确。 如果口= 0 ，则变精度粗糙集模型就退化为p a w l a l ( 粗糙集模型。 2 概率粗糙集模型 p a w l a k 粗糙集模型是基于可利用信息的确定性的，因而忽略了可利用信息的 不完全性和可能存在的统计信息，而概率粗糙集模型恰恰能很好地解决此问题。 定义2 2 设4 = ( u ，r ，尸) 称为概率近似空间，其中u 是有限论域集合，五是u 上的等价关系，_ p 为u 上子集类构成的盯代数上的概率测度。 设o 口 卫关于以依参数d ，卢的正域，边界域和负域分别为： 第二章粗糙集理论相关知识 p ( x ，口，) = 互( ) = 扛u l p ( x i 【卅) 口 ， 6 m ( ，口，) = x u i p ( zj 口 ) 口 ， 行踞( x ，货，) = u p 知= 缸u i p ( z l 肛 ) ) 显然，当甜= 1 ，= 0 时，若取p ( z i z 】) = | z n 【z 】l 苫】i ，则： 2 厶( x ) = 五( 工) = x u i x 】x ) ( x ) = ( x ) = 扛z l x 】n 囝) 这时概率粗糙集模型的下近似和上近似分别成为p a w l a l 【粗糙集模型的下近似 和上近似。因此概率粗糙集模型是p a w l a k 粗糙集模型的推广形式。 3 模糊粗糙集模型 模糊集和粗糙集在处理不确定性和不精确性问题方面推广了经典集合论，两 个理论的比较和融合一直是人们感兴趣的话题，模糊粗糙集理论的建立和发展， 成为粗糙集理论推广的方向之一。在文献【1 5 中d u b o i sa n d p r a d e 提出了模糊粗糙 集模型。 定义2 3 设( u ，r ) 是模糊近似空间，即r 是论域u 上的一个模糊等价关系， v f f ( u ) ，在空间( u ，r ) 上的下近似f 、上近似静是u 上的一对模糊集： 星f ( x ) = i 1 1 f ( i n a x 【胁( y ) ，1 一，如( x ，y ) 】ly u ) ， 胁( x ) = s u p r n i n 肚( y ) ，胁( 石，_ y ) 】i y u ) 对于p a w l a k 粗糙集模型，由于特征函数触( y ) ，若) ，j ，则触( 力= 1 ，否 则为o ，则可把p a w l a k 粗糙集模型改写为： 触( x ) = i n f 触( y ) 】l y u ，( 石，y ) r ) 脚( x ) = s u p ，啊( y ) 】y u ，( x ，力r ) 下近似的直观意义为只有任意与x 具有等价关系月的y 都在集合x 中 ( 触( 力= 1 ) 时，蹦( x ) = 1 ，即x 丛，上近似亦同。 2 2 信息系统知识的表示方式 信息系统在智能数据处理中占有非常重要的地位 定义2 4 形式上，四元组s = ( u ，爿，矿，) 表示一个信息系统，其中 电子科技大学硕士学位论文 u ：对象的非空有限集合，称为论域；爿：属性的非空有限集合； 矿= lj 圪，k 是属性口的值域 口e ，：u 矿呻y 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v 口爿，x 6 ，( x ，4 ) 5 通常，也用s = ( 玑4 ) 来代替s = ( u ，一，矿，) 信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过制定对象的各属性值来表达。一个属性对应着 一个等价关系，一个表可以看成是定义的一簇等价关系。 目标信息系统是一类特殊而重要的信息系统。 设s = ( u ，以，) 为一信息系统，彳= c u d ，c n d = a ，c 称为条件属性集，d 称为决策属性集。具有条件属性和决策属性的信息系统称为目标信息系统。 定义2 5 设s = ，爿，y ，力为目标信息系统，爿= c u d ，c n d = o ，若对于 v x ，y ，工y ，v 口e c ，当，( x ，8 ) = ，( y ，口) 日寸有，( z ，d ) = ，( y ，d ) 成立，( x ，口) 贝0 是一致( 协调) 的，否则是不致( 不协调) 的。 定义2 6 设s = ( 阢爿，y ，厂) 为目标信息系统，如果对所有的决策规则都是一致 的，则信息系统是一致的，否则是非一致的。 定义2 7 ”1 设s = ( u ，爿，矿，) 为目标信息系统，爿= c u d ，c n d ：o ，称决策属 性d 在s 中以程度 ( o t 1 ) 依赖于c ，其中 七= i p ( d ) l l u j ( 1 ) 当t = 1 时，意味着m d ( c ) 删d ( d ) ，即在已知条件c 下，可将u 上全部 个体划分到d 基本类中。 ( 2 ) 当o 女 1 ，则称d 粗糙依赖于c ，即在已知条件c 下，只能将u 上那些 属于正区域的个体划分到d 基本类。 ( 3 ) 当七= 0 ，则称d 全不依赖于c ，说明利用条件c 在u 上没有元素可划分到 d 基本类。 定理2 p6 】设s = ( u ，彳，y ，) 目标信息系统是一致的，当且仅当七：1 证明：由定义，显然成立。 定理2 2 每个目标信息系统s = ( u ，4 ，y ，) 都能唯一地分解成两个决策表 蜀= ( 矾，彳，矿，力和岛= ( 巩，“，以门，使得在& 中岛= i ，而在& 中岛= o ，其中： 第二章粗糙集理论相关知识 u = p o ( d ) = u j “( d ) p d ( x ) 以= 丑c ( d ) = u z d ，( d ) 肌0 ( x ) 2 3 信息系统的多样性 设s = ( u ，4 ，矿，) 是一个信息系统，其中f = u ：f m ) ，：u 斗珑( k 矿) 表示属 性研关于对象的取值函数。如果矸= 【o ，1 】，则此系统称为f u z 硝信息系统。如果 形= p ( 形) ，则此信息系统称为集值信息系统，其中k 为有限论域。如果 瑶= 珊o ，1 ) ，则称此信息系统为区间信息系统，其中o ，1 】) 表示 0 ，1 上闭区间全 体。如果矿= f ( 0 ，1 】) ，则称此信息系统为f 1 1 z z y 数信息系统，其中，( o ，1 】) 表示 o ，1 】 上的f u z 巧数全体( o ，1 】上的f i l z z ) r 数指【o ，1 】上的取值在【0 ，1 】的凸函数4 ，即对于 任意x ，_ y 【o ，1 】和o 2 0 ，则关于丑d 的 占下近似与占上近似具有以下性质： ( 1 ) 露( o ) = 盛( g ) = a ，霹( = 髫( u ) = u ， ( 2 ) 髫( x ) 盖瞄( z ) ， ( 3 ) 整皤n y ) = 髫( x ) n 髫( y ) ，霹( x uy ) = 霹( x ) u 露( y ) ， ( 4 ) 篮( ) 一喵( z ) ，群( j ) 一墨；) 对于目标信息系统( u ，彳，f ， 田， 岛) ) ，记恐= ( x ，y ) e u 【，：踟( 砷= 岛( ) ， 则玛为x 上的等价关系，即对于目标值，要求必须相等。记它的等价类为 u 局= d 1 ，d 2 ，q ) 我们记： d ( d ，【z 】；) 刊d ，n 肛 ；i x 蓝， ；( x ) = ( d ( 8 ，【x 】；) ，d ( d 2 【x ：) ，d ( p 【司；) ) ， 菇( 工) = d ，u 岛： x ；n d ，a ) ， 瑶= q o ：d ( 日o 吲；) = 1 弓磐d ( b m ；) ) ， 埔( 功= m 野d ( d ，0 ，【z 瞄) = d ( d o 【卅；) ， c ；( d ) = 缸u ：嵋( 曲= d ) ，d u 吃 例5 1 表5 1 给出了一个连续值域目标信息系统。 第五章扩展粗糙集模型及其约简 表5 1 连续值域目标信息系统 u 碍口， d 而 o o1 而 0 20l 恐 0 4l2 矗 0 6o 52 鼍 0 6 1 3 1 o3 取s = o _ 3 ，由前面的定义得： u = 五，恐，魄 ，4 = q ，吒) ，d = d l ，d 2 ，d 3 ) 成瓴) = ( 1 ，o ，o ) ，以“) = o ，o ，o ) ，成( 屯) = ( o ，2 3 ，1 3 ) ， 成( 矗) = ( o ，2 3 ，l 3 ) ，( ) = ( o ，2 3 ，1 3 ) ，联( ) = ( o ，o ，1 ) ， 疗“) = 假) ，成) = ) ，形( 砖) = ( d 2 ) ， 圬( ) = ( d 2 ) ，以( 而) = ( d 2 ) ，壕( 魄) = ( d 3 ) 5 1 2 连续值域信息系统属性约简 对于连续属性信息系统下的属性约简，这里采用分布约简与最大分布约简的思 想。 定义5 2 设( u ，爿，f ， d ) ， 岛 ) 为连续值域信息系统，对于给定的g o ，b 4 ： ( 1 ) 若帆u ，店( 曲= 成( x ) ，则称丑是g 分布协调集；若b 是s 分布协调集， 而占的任意真子集不是s 分布协调集，则称占为s 分布约简。 ( 2 ) 若觇u ，圬( x ) = 虻( x ) ，则称b 是s 最大分布协调集；若b 是s 最大分布 协调集，而b 的任意真子集不是占最大分布协调集，则称曰为譬最大分布约简。 分布协调集是保持对象在每个决策类的隶属程度不变的属性集，而最大分布协 调集保持每个对象的最大分布决策类不变；若占为连续值域信息系统 ( u ，爿，f ， d ) ， 岛) ) 的占分布约简，则在阀值占下由属性集b 产生的规则与由爿产生 的规则有相同的可信度。若b 为连续值域信息系统( u ，爿，f ， 田， ) ) 的占最大分布 约简，则在阀值占下由属性集b 产生的不确定性命题规则与由彳产生的规则相同， 但可信度可能不同。 定理5 - 2 【3 6 】设( u ，彳， 田， 幽 ) 为连续值域信息系统，则分布协调集必为最 大分布协调集。 电子科技大学硕士学位论文 对于例5 1 ，若令s = 0 3 ，b = “ ，则： 成( x 。) = ( 1 ，o ，o ) ，一( 屯) = ( 2 ，3 ，1 3 ，o ) ，成( 玛) = ( 1 4 ，2 ，4 ，1 ，4 ) ， ：( 而) = ( o ，2 3 ，1 3 ) ，正( ) = ( o ，2 3 ，1 3 ) ，成( ) = ( o ，o ，1 ) 显然，属性子集口= 弛) 不是s = o 3 的分布协调集，而是最大分布协调集。 接着我们来讨论一下占的取值问题，即当s 去何值时，能最大限度的挖掘有价值的 信息。研究表明，当取s r p 弘l 五( 蕾) 一五( x 川时，只能得到 一条规则，显然也达不到要求，所以s 最好取 砸ni 五 ) ( 耐) l ) 3 1 输出结果 l ( “。) ，厶( “：) 厶( ) 算法复杂度分析：该算法实现部分共三层循环，复杂度为 0 ( ：女) ( j ：c d 耐( 占) ) ，算法输入输出的时间复杂度都为d ( h ) ，所以该算法的整体 复杂度为d ( ，