（计算机应用技术专业论文）基于粗糙集的数据挖掘属性约简算法的研究.pdf

哈尔滨t 程大学硕士学位论文 摘要 数据挖掘是近年来数据库领域中出现的一个新兴研究热点，它是从数据 库的大量数据中提取隐含的、未知的、具有潜在价值的信息和知识的过程。 进行数据挖掘的方法有很多，基于粗糙集的数据挖掘方法便是其中之一。属 性约简是基于粗糙集的数据挖掘过程中的关键步骤，获得高效、快捷的属性 约简算法对基于粗糙集的数据挖掘领域具有重要的现实意义。 基于可辨识矩阵的属性约简算法是目前众多属性约简算法中应用最为广 泛的一种。本文在粗糙集理论的基础上，针对传统的基于s k o w r o n 可辨识矩 阵属性约简算法中存在的不足，提出了一种新的基于浓缩布尔矩阵的属性约 简算法，该算法主要在以下几个方面作出了改进：提出了浓缩布尔矩阵的概 念。该浓缩布尔矩阵以布尔代数的形式有效解决了现有可辨识矩阵存储空间 大、生成效率低等缺点：提出了一种新的分辨函数最小析取范式生成算法。 该算法不仅能获得分辨函数所有最小析取范式项，并有效节省了存储空间， 降低算法的时间复杂度。最后，通过实验对比验证了基于浓缩布尔矩阵的属 性约简算法的正确性和高效性。 针对实际问题中数据库中的数据是不断变化的这一情况，提出了基于浓 缩布尔矩阵的增量式属性约简算法。该算法避免了每次从庞大的原始决策表 进行约简的动作，实现了对决策表约简结果的动态更新与维护，从而提高了 属性约简效率。最后，通过实例验证了当决策表动态更新时，该算法能够在 已有属性约简的基础上正确获得更新后决策表的所有属性约简，有效减少了 计算量，提高了算法执行效率。 关键词：数据挖掘；粗糙集；属性约简；浓缩布尔矩阵；增量式算法 哈尔滨工程大学硕士学位论文 一i i ；j 薯一_ i i i i i i i 宣i 宣声i i i 宣冒| 皇宣i j 暑萱i _ a b s t r a c t d a t am i n i n gi san e wh o tr e s e a r c hs p o ti nd a t a b a s ea r e a i ti su s e dt od i s c o v e r t h ei m p l i c i t ，p r e v i o u s l yu n k n o w n ，a n dp o t e n t i a l l yu s e f u li n f o r m a t i o nf r o mt h e l a r g eq u a n t i t yo fd a t a r o u g hs e tm e t h o d o l o g yi sa k i n do fm o r ev a l i dm e t h o dt o d e a lw 池i t a t t r i b u t e sr e d u c t i o ni st h em o s ti m p o r t a n ts t e pi nt h ec o u r s eo fd a t a m i n i n gb a s e do nr o u g hs e tt h e o r y h o wt oa c q u i r eas i m p l ea n de f f e c t i v e a t t r i b u t e sr e d u c t i o nm e t h o dh a sag r e a tm e a n i n gf o rd a t am i n i n gd o m a i n c u r r e n t l y , t h e r ea r el o t so fa l g o r i t h m sf o ra t t r i b u t e sr e d u c t i o n , i nw h i c ht h e a l g o r i t h mb a s e do nd i s c e r n i b i l i t ym a t r i xi so n eo fe f f i c i e n t l ya l g o r i t h m s a i m i n g a tt h ed r a w b a c k se x i s ti nt h et r a d i t i o n a la t t r i b u t e sr e d u c t i o na l g o r i t h mb a s e do n s k o w r o nd i s c e r n i b i l i t ym a t r i x ，an o v e ia l g o r i t h mb a s e do ne n r i c h i n gb o o l e a n m a t r i xi sp r e s e n t e dw h i c hi n c l u d et w oi n n o v a t i o n a lp o i n t sa sb e l o w ：f i r s t l y , t h e c o n c e p to fe n r i c h i n gb o o l e a nm a t r i xi sp r o p o s e d ，w h i c h c a l le f f e c t i v e l yc u td o w n t h ec o m p u t i n ga n ds t o r i n g c a p a c i t y s e c o n d l y , t h eg e n e r a t i o na l g o r i t h m o f m i n i m a ld i s j t m c t i v en o r m a lf o r m ( d n f ) f o rd i s c e r n i b i l i t yf u n c t i o ni sp r e s e n t e d ， w h i c hc a nd i r e c t l yg e n e r a t et h em i n i m a ld n fo fd i s c e m i b i l i t yf u n c t i o n sa n ds a v e s m e m o r ys p a c ea n dc p uo c c u p a t i o nt i m e f i n a l l y , t h ev a l i d i t ya n de f f i e c t i v e n e s s o ft h ea t t r i b u t e sr e d u c t i o na l g o r i t h mb a s e de n r i c h i n gb o o l e a nm a t r i xi sp r o v e d a i m i n ga tt h es i t u a t i o ni nr e a la p p l i c a t i o nw h i c hd a t aa r ea l w a y sc h a n g i n gi n d a t a b a s e ，a l li n c r e m e n t a la l g o r i t h mo fa t t r i b u t e sr e d u c t i o n i s p r o p o s e d t h i s a l g o r i t h mc a l la v o i dr e d u c t i o nf r o mt h el a r g eo r i g i n a l d e c i s i o nt a b l ew h e nn e w o b j e c t sa r ea d d e d i tc a r lu p d a t ea n dv i n d i c a t et h er e s u l t so f r e d u c t i o nf o ro r i g i n a l t a b l e ，a n di m p r o v et h ee f f i c i e n c yo fa t t r i b u t e sr e d u c t i o nf o rd a t a b a s e t h e a l g o r i t h mi sd e m o n s t r a t e dt ob e e f f e c t i v ew i t ht h es p e c i f i ce x a m p l eu l t i m a t e l y k e y w o r d s ：d a t am i n i n g ；r o u g hs e t ；a t t r i b u t e sr e d u c t i o n ；e n r i c h i n gb o o l e a nm a t r i x ； i n c r e m e n t a la l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：煎盎 日期：如窖年，月i o 日 哈尔滨工程大学硕士学位论文 1 1 数据挖掘概述 1 1 1 什么是数据挖掘 第1 章绪论 由于科学技术的迅猛发展，使得数据库的规模日益扩大，数据存储量急 剧增加。面对大量信息在给人们带来方便的同时，也不可避免的带来了一些 问题，比如无法发现信息间隐藏的内在关系、无法辨别信息的真假j 无法根 据现有的信息对未来数据发展趋势进行预测等。那么，如何才能不被大量信 息所淹没，并从中及时发现潜藏的、有价值的知识? 这一问题的提出，迫切 需要一种新的技术与工具来帮助人们从大量数据中搜寻有用的信息。为适应 这种需求，数据挖掘应运而生，它是信息处理技术自然演化的结果。 数据挖掘i l 】，也可以称为数据库中的知识发现，就是从大量的、不完全 的、有噪声的、模糊的、随机的原始数据中提取出隐含其中的、事先未知的、 但又是潜在有用的信息和知识的过程。 1 1 2 数据挖掘的方法 数据挖掘是一门交叉性学科，它只有在其它多种技术的支持下，才能挖 掘出令用户满意的结果。具体来说，数据挖掘的方法与技术主要分为以下几 类： ( 1 ) 机器学习方法 机器学习方法就是通过观察和实验来发现并获取经验规律，可细分为： 归纳学习方法、基于范例学习、遗传算法等f 2 j 。 ( 2 ) 统计分析方法 统计分析方法是利用统计学原理，对总体中的样本数据进行分析，得出 哈尔滨工程大学硕士学位论文 葺置暑墨| 宣一i i i 一 i 皇重皇暑；葺 描述、推断总体信息和知识的方法，这些信息和知识揭示了总体中的内部规 律。目前主要的统计方法有：回归分析( 多元回归、自回归等) 、判别分析 ( 贝叶斯判别、费歇尔判别、非参数判别) 、聚类分析( 系统聚类、动态聚类 等) 、探索性分析( 主元分析法、相关分析法等) 、模糊集、粗糙集等方法。 ( 3 ) 神经网络方法 神经网络方法建立在可以自学习的数学模型基础上，是一种通过训练来 学习的非线性预测模型1 4 1 。该方法通过模拟人脑神经元的结构，将每一个连 接看作一个处理单元，来完成分类、聚类、特征挖掘等多种数据挖掘任务。 目前的神经网络方法主要有：前向神经网络、自组织神经网络( 自组织特征 映射、竞争学习) 等。 ( 4 ) 遗传算法 遗传算法是根据d a r w i n 进化论和m e n d e l 的遗传学说生物进化思想而启发 得出的一种全局优化算法i s 。它通过自然选择、遗传、变异等作用机制，利 用适者生存的概念，来提高个体的自适应性，从而得到最优解。 ( 5 ) 可视化技术 可视化技术就是把数据信息转换并表达成可视化形式，如图象或图形。 使用户能通过可视化的方法，交互地分析数据间的关系，便于发现数据间的 模式、异常等情况变化，极大地提高数据挖掘的速度和深度i 酣。 1 1 3 数据挖掘的研究现状及发展趋势 1 9 8 9 年举行的第十一届国际联合人工智能学术会议首次提出了数据库 知识发现的概念，并于1 9 9 5 年第一次召开了知识发现与数据挖掘国际学术会 议。1 9 9 8 年建立了专门研究数据库知识发现的学术组织 a c m s i g k d d ( s p e c i a l i n t e r e s t e d g r o u p o i l k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ) ，1 9 9 9 年，由其组织了第五届知识发现与数据挖掘国际会议。迄 今为止，关于数据库知识发现的国际研讨会已经召开了8 次，规模由原来的 专题讨论发展到现今的国际学术大会，研究重点也逐渐从发现方法转向到系 统应用，且注重多种发现策略和技术的合成，以及多种学科之间的相互渗透。 有关数据挖掘的研究还发表在书籍、会议、以及有关数据库、统计学、 2 哈尔滨工程大学硕士学位论文 机器学习和数据可视化的杂志上，这些成果都促进了数据挖掘技术的研究与 发展。 未来数据挖掘的研究热点及发展趋势主要集中在以下几个方面： ( 1 ) 数据挖掘语言的形式化：发展了专门用于有用信息发现的数据挖掘 语言。标准的数据挖掘语言将有助于数据挖掘的系统化开发，改进数据挖掘 系统间功能的互操作性，促进数据挖掘系统在企业和社会中的教育与使用。 ( 2 ) 数据挖掘过程的可视化：通过数据挖掘的可视化，可以使用户更容 易理解数据挖掘的过程，便于进行人机交互，有助于推动数据挖掘作为数据 分析的基本工具。 ( 3 ) 数据挖掘中的隐私保护与信息安全：当人们可以从不同角度和不同 层次上看到数据库中的数据时，将可能威胁到数据的安全性，甚至泄露受保 护的私人数据信息。所以，如何做到数据挖掘中的隐私保护与信息安全至关 重要。 ( 4 ) 加强对各种非结构化数据的挖掘：如对文本数据、图形数据、视频 图像数据等的挖掘。 1 2 粗糙集国内外研究现状 粗糙集作为一种新的用于处理不精确、不确定与不完全数据的数学理论， 最初是由波兰数学家z p a w l a k ( 参见文献 7 ) 于1 9 8 2 年首次提出的。其主 要思想就是在保持分类能力不变的前提下，通过知识约简导出概念的分类规 则。1 9 9 1 年，p a w l a k 出版的第一本有关粗糙集理论的专著( r o u g hs e t s ) ) s l ， 极大地推动了国际上对租糙集理论与其应用的深入研究。1 9 9 2 年在波兰召开 了第一届国际粗糙集研讨会，会议着重讨论了集合近似定义的基本思想及其 应用和粗糙集环境下的机器学习研究，在此之后，每年都定期在世界各国召 开一次以粗糙集理论为主题的国际研讨会。目前，国外在粗糙集领域的研究 主要集中在约简的优化算法、粗糙集理论和模糊理论、粗糙集理论与神经网 络理论等其它人工智能技术的结合、粗糙逻辑等课题上，并取得了显着成果。 国内对粗糙集理论的研究始于9 0 年代中期，王珏、苗夺谦、王国胤、曾 黄麟等人于1 9 9 4 年首次将粗糙集理论引入我国，为我国对粗糙集理论的研究 3 哈尔滨工程大学硕士学位论文 打下了坚实的基础；在此之后，张文修等人提出了基于随即集的粗糙集模型， 并研究了粗糙集与包含度之间的关系：刘清等人对粗糙集在近似推理、智能 代理等方面进行了深入研究。自2 0 0 1 年起，在重庆邮电学院、苏州大学、浙 江海洋学院和同济大学、鞍山科技大学等地组织承办了多次r o u g hs e t s 和软 计算学术研讨会，这些会议的举办表明我国r o u g hs e t s 理论的研究队伍正在 不断壮大，并已得到国际同行的重视和认可。 1 3 论文的研究意义及其主要研究内容 综上所述，数据挖掘的研究越来越受到国内外学者的重视，而粗糙集作 为一种数据挖掘工具有着它不可替代的优势。其中，如何获得高效、快捷的 属性约简算法是粗糙集理论研究的重要课题之一，本文以高效获取决策表所 有属性约简为目的，着重在以下几个方面进行了研究： ( 1 ) 浓缩布尔矩阵的提出 本文提出了一种新型的可辨识矩阵浓缩布尔矩阵，它通过布尔代数 的形式有效解决了现有可辨识矩阵存储空间大、生成效率低的问题。由决策 表直接生成的浓缩布尔矩阵是分辨函数的合取矩阵形式，可由其直接生成分 辨函数的析取范式，省略传统基于可辨识矩阵属性约简中需要生成分辨函数 的中间过程，有效提高约简效率。 ( 2 ) 改进的分辨函数最小析取范式生成算法的提出 分辨函数析取范式的生成方式是影响基于可辨识矩阵属性约简效率的重 要因素。本文针对基于数学模型的直接搜索转换方法【9 l 存在的不足：不能得 到最小析取范式，并由此造成了时间及空间的浪费，提出一种新的用于直接 生成分辨函数最小析取范式的算法，该算法采用简单的矩阵运算替代复杂的 分辨函数析取范式生成过程，不仅直接获得分辨函数的最小析取范式，并有 效改善算法的时间和空间复杂度，提高了属性约简的生成效率。 ( 3 ) 基于浓缩布尔矩阵的属性约简算法的提出 属性约简是粗糙集理论研究的核心内容之一。在实际应用中，特别是在 数据不精确、不确定的情况下，很难确定需要用哪个约简导出的规则，因 此，求出决策表的所有约简是有必要的。本文在浓缩布尔矩阵的基础上，针 4 哈尔滨工程大学硕士学位论文 对静态数据库和动态数据库两种情况，分别提出了以下能够获取决策表所有 约简的属性约简算法： 芦基于浓缩布尔矩阵的非增量属性约简算法 针对基于s k o w r o n 可辨识矩阵属性约简算法中存在的效率低、空间复杂 度高等不足，提出了一种新的基于浓缩布尔矩阵的属性约简算法，并通过实 验验证该算法的有效性。 芦基于浓缩布尔矩阵的增量式属性约简算法 针对如何高效率实现动态数据库的属性约简问题，本文在基于浓缩布尔 矩阵的非增量属性约简算法的基础上，提出了一种基于浓缩布尔矩阵的增量 式属性约简算法，实现了对原决策表约简结果的增量式更新、维护和管理， 提高了动态数据库属性约简效率。 1 4 论文的组织结构 本文共有五章，其组织结构如下。 第1 章：绪论。对数据挖掘理论进行了系统论述：阐述了粗糙集理论的 国内外研究现状；简要介绍了本文的主要研究内容以及论文的组织结构。 第2 章：粗糙集基础理论。简要介绍了粗糙集的基础理论知识及其主要 应用与发展前景。 第3 章：可辨识矩阵。文中对现有几种可辨识矩阵进行了研究，并针对 其在属性约简中存在的不足，提出了浓缩布尔矩阵的概念及其生成算法，最 后通过实例对比验证了浓缩布尔矩阵具有存储空间小、生成效率高的优点。 第4 章：分辨函数最小析取范式的生成算法。首先介绍析取矩阵、合取 矩阵的相关理论及运算规则；其次在分析基于数学模型的直接搜索转换方法 存在不足的基础上，提出了改进的分辨函数最小析取范式的生成算法，有效 提高属性约简效率；最后通过实例验证该算法的有效性。 第5 章：基于浓缩布尔矩阵的属性约简算法。为获得决策表所有最小属 性约简，本章在浓缩布尔矩阵的基础上，针对静态数据库和动态数据库，分 别提出了基于浓缩布尔矩阵的非增量属性约简算法和增量式属性约简算法， 并用实例加以论证说明。 5 哈尔滨工程大学硕士学位论文 第2 章粗糙集基础理论 粗糙集理论是一种用于刻画不完整和不确定性的数学工具，它能有效分 析和处理各种不精确、不一致和不完整的信息，并从中发现隐含的知识，揭 示潜在的规律。自1 9 8 2 年波兰数学家z p a w l a k 首次提出r o u g hs e t s 理论后， 2 0 年来世界各国学者的研究与探讨，使得粗糙集无论是在理论上还是在相关 领域的应用上都取得了令人瞩目的研究成果。 2 1 粗糙集的基础理论 2 1 1 知识与知识库 粗糙集理论建立在分类机制的基础上，并将等价关系对空间的划分与知 识等同。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的 知识用已知知识库中的知识进行近似刻画。 在粗糙集理论中，“知识 被认为是一种分类能力，也可理解为对数据 的划分能力。用集合的概念表示，知识可定义为：定义一组数据集合u 和等 价关系集合r ，在等价关系集合尺下对数据集合u 的划分，称为知识，记为 u r 。由此，在u 和r 的意义下，知识库可以定义为：属于r 中的所有可能 的关系对u 的划分，记为k = ( ，r ) ，其中u 是论域，r 是u 上的一个等价 关系簇l 。 2 1 2 信息系统 信息系统的基本组成是研究对象的集合，关于这些对象的知识是通过指 定对象的基本特征( 属性) 和它们的特征值( 属性值) 来描述的。一般地， 一个信息系统【1 2 j s 可以表示为四元组s = ，其中，u 是对象的集 6 哈尔滨工程大学硕士学位论文 合，即论域；a 是属性的有限集合；v = u 矿。，圪表示属性a 的值域； a e a f ：u a v 是一个信息函数，它给属于u 的对象赋属性值，即对于任意 a a 和x u 有f ( x ，a ) 圪。通常信息系统s = 也可简化表示为 s = ( u ，彳) 。 信息系统的行对应要研究的对象，列对应对象的属性。容易看出，一个 属性对应一个等价关系，一个信息系统可以看作是一簇等价关系，即知识库。 对于每个属性子集p a ，定义属性p 的不可区分关系1 1 3 i n d ( p ) 为 i n d ( p ) = ( x ，y ) u 2v r p ，f ( x ，- ) = f ( y ，) ( 2 1 ) 如果( x ，j ，) r n d ( p ) ，则称x 与y 是尸不可区分的。容易证明v 尸a ， 不可区分关系i n d ( p ) 是u 上的等价关系，符号u i n d ( p ) 表示不可区分关系 i n d ( p ) 在u 上导出的划分，i n d ( p ) 中的等价类称为尸的基本集，符号【x 】p 表示包含x u 的p 等价类。 下面讨论两个信息系统的关系。 令s = ( u ，4 ) 和= ( u ，4 ) 为两个信息系统，若i n d ( 4 ) = i n d ( a ：) ，则 称s 和& 是等价的。这表示可以用不同的属性集对对象进行描述，以表达关 于论域u 的完全相同的事实。 令s i = ( u ，4 ) 和& = ( u ，4 ) 为两个信息系统，当i n d ( 4 ) i n d ( a 2 ) 时， 称信息系统s ( 或属性集4 ) 比信息系统( 或属性集4 ) 更精细，或者称是比 s 更粗糙。 信息系统s = ( u ，彳) 也可称为知识表达系统。 例2 1 表2 1 给出一个天气情况的信息系统。 表2 1 有关天气情况的信息系统 【， o u t l o o k ( a t )t e m p e r a t u r e ( a 2 )h u m i d i t y ( a s ) 毛s u n n y h 0 t h i 曲 屯s u n n y h 0 t h i g h 毛 o v e r c a s th 0 t h i 曲 面 r a i n m i l d h j 曲 黾 r a i nc 0 0 ln o r m a l 哈尔滨工程大学硕士学位论文 表中论域u = x t ，而，x 3 ，心，x 5 ，属性集合a = a t ，a 2 ，a 3 ) ，根据这个信息系 统，可以得到其相关的概念描述，如将天气按气象、温度、湿度可以分别进 行如下分类，得到有关天气情况的知识如下： u a t = “x l ，屯 ， x d ， ，x 5 ) ； u a 2 = 五，x 2 ，而 ， 而 ， ； u a 3 = x l ，j c 2 ，x 3 ，毛 ， 黾 。 2 1 3 决策表 决策表是一类特殊而重要的信息系统，多数决策问题都可以用决策表形 式来表示。决策表可以根据信息系统定义如下： 设信息系统s u ，a ，v ，f ，a = c u d ，且c nd a ，c 和d 分别称 为条件属性集和决策属性集，y 是属性的值域，厂是对象属性到值域的映射。 称具有条件属性和决策属性的信息系统s 为决策表1 1 4 】。 例2 2 表2 2 给出一个身体状况决策表( 参见文献 1 5 ) 。条件属性 c = 溉，a 2 ，a d ，决策属性为d 。 表2 2 身体状况决策表 条件属性c决策属性d 对象u 头疼( 口1 )乏力( 口2 )发烧( 口3 ) 流感 一 是是正常 否 吃 是是偏高 是 而 是是 很高是 否是正常否 2 1 4 粗糙集 设u 是非空的论域，r 是一个不可分辨关系或称等价关系；a = ( u ，r ) 称 为一个近似空间；u r 表示r 中所有等价类的集合，或称u 的分类；h 】。表 示尺中包含x 的等价类；r 中的等价类称为基本集；基本集的有限并集称为 8 哈尔滨工程大学硕士学位论文 i | 暑| | i 皇皇| i 可定义集。 定义2 1 设石是u 的子集，x u ，则x 可用可定义集的术语从4 中 定义：a 中包含在x 中的最小可定义集称为彳中x 的下近似，表达式为 r x = x ui 【叫r x ) 。彳中包含x 的最大可定义集称为a 中x 的上近似， 表达式为放= x u l f x k n 义彩 。( 戥，r x ) 称为粗糙集f 1 6 l 。 定义2 2b n d ( x ) = 肷一丛，称为x 的边界域；p o s ( x ) = _ r x ，称为 x 的正域；n e g ( x ) = u r x ，称为x 的负域。 边界域b n d ( x ) 是根据知识r ，u 中既不能肯定归入集合工又不能肯 定归入集合贾的元素构成的集合。正域p o s ( x ) 是根据知识足，u 中所有一 定能归入集合x 的元素构成的集合。负域n e g c x ) 是根据知识尼中所有 不能确定一定归入集合x 的元素的集合。 下近似和上近似以及边界域的定义可如图2 1 所示 ，7 i 。 i 、if _ 厂烈 、- h 、i 1 】 (r li1l ( 一i 昃 l ， l 恹 i - f 一 厂 i i 图2 1 租糙集近似定义示意图 图2 1 中，由曲线围起来的部分就是需要表达的某个子集置由里边粗 黑线围起来的就是这个子集的下近似，外边粗黑线围起来的就是这个子集的 上近似，位于两者之间的区域就是边界域。小方格就是由知识尺所产生的等 价类。集合x 无法用小方格准确地表示出来，但是，它可以由两个集合：下 近似和上近似粗略地表示。 由图2 1 可以看出，粗糙集的不精确性是由于边界域的存在而引起的。 边界域越大，其精确性越低。如果边界域为空集，则粗糙集为精确集。 9 哈尔滨工程大学硕士学位论文 粗糙集理论中，不精确的数值不是预先假定的，而是通过表达知识不精 确性的概念近似计算得到的，这种不精确的数值表示的是有限知识( 知识的 粒度性) 的结果。粗糙集理论不需要预先指定一个精确数值去表达不精确的 知识。 命题2 1 ( 1 ) 当且仅当丛= 劢，称集合x 是尺可定义集； ( 2 ) 当且仅当丛殿，称集合z 是r 的粗略集。 图2 2 形象的说明命题2 1 【1 3 】。 nn 1 v 。 广、 、 p 7 n x ppp | 、 厂 ， nn 图2 2 命题2 1 示意图 例2 3 在表2 2 所示的决策表中，对于属性子集庐 乏力，发烧 ，集合 x = x 2 ，x 3 ，x 4 是一个粗集，下面分别计算集合x 的上近似集，下近似集，正 域，负域，边界域。 首先计算论域u 的所有b 基本集，u i n d ( b ) = “而，昀 ， 秘) ， x d ) 令骂= 而，x 4 ，马= x 2 ) ，忍= x 3 ) ，集合x 与基本集有如下关系： x n 蜀= x 4 g ， x n 垦= x 2 囝， x n 岛= x 3 ) a 。 由此可得到集合x 的上近似集、下近似集、正域、边界域、负域： b ( x ) = 蜀u 岛u 马= 五，_ j c 2 ，x 3 ，x 4 ) ， 星( x ) = 垦u 色= x 2 ，x 3 ) ， p o s b ( x ) = 鸯( x ) = 而，x 3 ) ， b n d 厅( x ) = 五，x 4 ， n e g 疗( x ) = u b ( x ) = g 。 1 0 哈尔滨工程大学硕士学位论文 2 1 5 属性约简 属性约简是粗糙集理论的核心内容之一。众所周知，信息系统中的属性 并不是同等重要的，甚至其中某些属性是冗余的。所谓属性约衙1 9 1 ，就是在 保持信息系统的分类或决策能力不变的条件下，删除其中的冗余属性，获取 最小属性集。 2 1 5 1 知识的绝对约简及核属性 定义2 3 设u 是一个论域，足是定义在u 上的一个等价关系簇，p r ， 如果i n d ( r p ) = i n d ( r ) ，则称关系p 在r 中是不必要的；否则，称p 在 r 中是必要的。 定义2 4 设u 为一个论域，r 为定义在u 上的一个等价关系簇，p r ， 如果每个关系p r 在r 中都是必要的，则称关系簇足是独立的。 定义2 5 设u 是一个论域，尺是定义在u 上的一个等价关系簇，r 中所 有必要的关系组成的集合称为关系簇尺的核，记作c o r e ( r ) 。 核的作用可理解为以下两点1 ：o i ： ( 1 ) 由于核包含于所有约简中，所以可将核属性作为计算属性约简的基 础： ( 2 ) 核属性可解释为在知识约简过程中不能消除的知识特征集合。 定义2 6 设u 是一个论域，r 和q 是定义在u 上的两个等价关系簇，且 q r ，如果i n d ( q ) = i n d ( r ) ，且q 是独立的，则称q 是r 的一个绝对约 简。 根据这个定义可知，约简有以下两点性质： ( 1 ) 约简所表达的对系统的划分与原来的知识库所形成的划分是完全一 致的，即约简所表达的知识和原来的知识具有相同的表达能力； ( 2 ) 约简具有最小性，即约简是能够表达原来的知识库的最小集合，约 简后不可再进行约简。 核与约简有如下关系： c o r e ( r ) = f q r e d ( r ) ，其中r e d ( r ) 表示r 的所有约简。 l l 哈尔滨工程大学硕士学位论文 薯i _ 暑盲暑薯葺i i | 皇_ 置_ 暑宣i ；墨i 暑薯皇宣宣j l j 嗣i i _ 嗣_ | _ _ _ _ i _ _ 宣皇置_ 宣暑宣_ _ _ 定理2 1 对于任何信息系统s = ( u ，a ) ，约简总是存在的【2 1 l 。 证明：若对于任意口a ，都有u ( a 一 口 ) u 彳，则4 本身就是约简。 若存在a a ，且有u ( a 一 口) ) = u a ，则研究尽利- a 。若对于任意岛蜀， 都有u a 彳( 墨一 6 1 ) ) ，则4 就是约简。若存在6 l 骂，且有 u i a = a i ( 8 , 一 6 1 ) ) ，则再研究岛= 尽一 6 l ，重复以上过程。由于a 是有限 集，所以总能找到一个口a ，使u b = u r ，且u ( b - b ) u a ( v b b ) 。 这时，曰即为信息系统的一个约简。 例2 4 设k = ( u ，r ) 是一个知识库，其中u = 而，x 2 ，黾) ， r = 蜀，砭，恐 ，等价关系曷、恐、恐有下列等价类。 u r i = “耳， ， x 2 ，黾) ， j c 3 ) ， 讫，而 ， 【，r 2 = “j c l ，j c 3 ，黾 ， ， 吃，x 4 ，而，黾) ) ， u 垦= “x i ，屯) ， ， x 2 ，j c 7 ， ， 屯，x 4 ) ) 。 关系i n d ( r ) 有下列等价类： u i n d ( r ) = 五，黾) ， 而，黾 ， 屯 ， ， ， 而) 。 因为u i n d ( r - r t ) = 毛，黾) ， 而，j c 7 ，黾) ， 毛) ， 黾) ， ) ) u i n d ( r ) ， 关系冠为足中必要的。 因为u i n d ( r 一 恐) ) = j c l ，黾 ，( 而，毛 ， 而) ， ) ， ) ， 为) ) = u i n d ( r ) ， 关系尼为尺中不必要的。 因为u u , , r d ( r - & ) = “，黾) ， 而，黾 ， 而) ， ) ， 蚝) ， ) ) = u i n d ( r ) ， 关系足为尺中不必要的。 这表明通过等价关系 墨，r ，马 定义的分类与根据 r i ，r 2 或 r 。，马 定 义的分类相同，即表明该系统的知识可以通过u i n d ( r , ，r 2 ) 或 u i n d ( r , ，r ， ) 来表达。 为了得到r = r i ，局，恐 的约简，检验 r i ，心) 和 r i ，恐 是否独立。 因为u i n d ( & ，垦 ) # u i n d ( & ) ，且u i n d ( & ，r 2 ) ) u 1 n d ( r 2 ) ， 所以 置，r ) 是独立的，即 墨，r ) 为r 的一个约简；又因为 u i n d ( & ，马) ) u i i n d ( r 1 ) 且u i n d ( r i ，玛) ) u i n d ( & ) ，所以 r i ，b ) 是独立的，即 蜀，恐) 也是r 的一个约简。 这样，r 有两个约简 r i ，坞 和 r i ，恐 ， 一个核 c o r e ( r ) = r 。，r 2 ) n r i ，恐) = r i 。 1 2 哈尔滨工程大学硕士学位论文 2 1 5 2 知识的相对约简及核属性 在讨论决策表属性约简时，一个条件属性对应的一个等价关系将对论域 u 形成一个划分，所有的条件属性形成条件属性集合c 对论域u 的划分，记 为u c ；同时，决策属性d 也对论域【厂形成一个划分，记为u d 。这两个划 分形成了对论域样本分类的知识。属性约简的目的就是要从条件属性集合中 发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性 的分类和所有条件属性形成的相对于决策属性的分类一致，即和所有条件属 性相对于决策属性有相同的分类能力。这就是决策表的相对约简。以下为决 策表相对属性约简的有关定义。 定义2 7 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇，q 的p 正域记为 p o s p ( q ) = u ( x ) ( 2 - 2 ) x e u q 定义2 8 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，若 p o s p ( q ) = p o s e t , ( q ) ，则称，为p 中相对于q 可省略的( 不必要的) ，简称p 中q 可省略的；否则，称，为j p 中相对于q 不可省略的( 必要的) 。 定义2 9 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇，若 p 中的任意，都是尸中不可省略的，称尸为( 相对于) q 独立的。 定义2 1 0 设【，是一个论域，p 和q 是定义在【，上的两个等价关系簇， 若p 的q 独立子集s p ，有p o s s ( q ) = p o s p ( 9 ，则称s 为p 的q 约简。 记尸的所有q 约简关系簇为r e d d ( p ) 。 定义2 1 1 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇， 尸的所有q 不可省略原始关系簇称为尸的q 核，记为c o r ( 尸) 。 一般情况下，核属性未必构成信息系统的约简，属性约简不一定非要从 核属性开始，但找出核属性有以下两个用处圜： ( 1 ) 以核属性作为计算约简的起点，简化属性约简的计算量； ( 2 ) 核属性是约简中的必要属性，是在约简中不能消去的。 定义2 1 2 设u 是一个论域，p 和q 是定义在【，上的两个等价关系簇， 如果p o s p ( q ) = u ，则称论域彤是p 上相对于q 一致。 哈尔滨工程大学硕士学位论文 定义2 1 3 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇， r e d o ( 尸) 为尸的所有q 约简关系簇，c o r e o ( 尸) 为p 的q 核，则 c o r e ( ，( 尸) = nr e d ( ) ( p ) 。 一般地，一个决策表的条件属性对于决策属性的相对约简并不是唯一的， 即同一个决策表可能存在多个相对约简。由于属性约简的目的是导出关于决 策表的决策规则，约简中属性的多少将直接影响着决策规则的繁简和性能。 因此，人们往往期望找到具有最少条件属性的约简，即最小约简。然而，sk m w o n g 和w z i a r k o 已经证明了找出一个决策表的最小约简是n p ，h a r d 问题， 导致n p h a r d 问题的主要原因是属性的组合爆炸问题】。 例2 5 设k = ( u ，尸) 是一个知识库，其中u = x l ，娩，黾 ， p = r i ，坞，马) ，等价关系墨，是和吗有下列等价类。 【，墨= 五，而，黾，而) ， 屯，黾 ，u 恐= 葺，j c 3 ，黾) ， x 2 ，x 6 ，而，黾 ， u 恐= “而，而， x 2 ，j c 7 ，黾) ， 毛，) 。 等价关系q 有下列等价类：u q = “而，而，民) ， x 3 ，x 4 1 ， x 2 ，而) ， ) 。于 是，由p 导出的分类为：u p = 五，而 ， 屯，x 4 1 ， 而，黾) ， x j ，k ，可以得到： p o s ，( q ) = 葺，屯，x 4 ，黾，x 6 ，而 。 现在，从p 中去掉曷，得n u ( ? 一 蜀 ) = “五，黾) ， j c 3 ，) ， 而，而，j c 8 ) ， 民 。 于是有p o s p 憾l ( q ) = “，x s ，x 4 ，毛，屹 p o s | p ( 9 ，所以，置是p 中必要的。 从p 中去掉坞，得到：u ( e - 恐) ) = 葺，毛， ，如，黾) ， x 2 ，黾) ， 而 。于是 有p o s p ， 如i ( q ) = 而，而，x 4 ，j c 5 ，j f 6 ，j c 7 ) = p o s p ( q ) ，所以，马是p 中不必要的。 从p 中去掉玛，得到u ( e 一 尼) ) = “x 。，x 3 ，而，黾 ， 而，而) ， 民，而) 。于是有 p o s 州岛 ( q ) = a p o s p ( q ) ，所以，玛是p 中必要的。这样，p 的q 核为 蜀，玛) ，它也是p 的q 约简。 2 2 粗糙集的应用及展望 2 2 1 粗糙集理论的应用现状 由于r o u g hs e t s 理论具有较强的实用性，已在许多领域中取得了显著成 果。尤其在股票数据分析、模式识别、地震预报、冲突分析、知识发现、粗 1 4 哈尔滨工程大学硕士学位论文 r 糙控制、医疗诊断、专家系统、人工神经元网络、决策分析以及其它各个方 面的应用中，粗糙集理论都提供了行之有效的数学方法。目前有关粗糙集的 应用主要包括以下几个方面： ( 1 ) 在数据挖掘中的应用 数据挖掘与规则生成是粗糙集理论在实际应用中最重要的一部分。由于 利用粗糙集可搜索数据的最小集合，可以使用定性与定量的数据，并从数据 中产生决策规则，所以在应用数据挖掘技术对大规模数据集进行数据挖掘之 前，可以利用粗糙集理论先对数据集进行约简，达到精炼数据集的目的，以 便于数据存储。粗糙集应用于数据挖掘的最大优点是可从数据本身直接获取 信息而不需要额外的外部信息，得出的属性子集能够较好地代表原属性集。 ( 2 ) 决策评价 利用粗糙集理论进行决策评价，以便给决策者提供正确的决策意见。 ( 3 ) 故障诊断 故障诊断是一个涉及到有效决策制定的复杂而困难的问题。根据随时监 测到的故障症状进行及时的系统诊断，可以帮助降低系统停机时间以提高总 的生产力，具有重要的现实意义。 ( 4 ) 模式识别 粗糙集理论的另一个重要应用就是模式识别。在模式识别的过程中可以 利用粗糙集理论进行特征选取，以选择那些确实能表征该模式的特征项。 2 2 2 粗糙集理论的发展趋势 粗糙集理论以其独特的优势得到许多专家学者的关注，但由于它是一门 新兴科学，仍然有许多需要完善的地方。研究热点主要有以下几个方面【2 s l ： ( 1 ) 大数据集问题 由于科学世界的发展，数据库规模越来越大，如何降低算法的时空复杂 度，以较高的效率获取最有价值的信息是粗糙集理论的一个挑战。 ( 2 ) 缺失值处理方法 在对样本数据进行处理时，常常由于对数据测量的误差以及数据处理受 到限制等原因而造成样本数据的丢失，一般把含有丢失数据的信息系统称为 1 5 哈尔滨工程大学硕士学位论文 不完备的信息系统。由于经典的粗糙集理论是基于完备信息系统