（计算机软件与理论专业论文）动态约简关键技术研究.pdf

摘要 针对大型复杂决策信息系统，如何进行决策信息系统约简并获取 知识一直是粗糙集理论中一个重要的研究课题。动态约简方法作为一 种有效的约简方法提出，其实质是对大型决策信息系统进行多次抽 样，把复杂决策信息系统的约简问题转化为若干子决策信息系统约简 的交集，以寻求最优、最稳定约简的问题。本文基于粗糙集理论与方 法，从动态约简的提出背景以及包含的各个层面详细阐述了其理论体 系，深入研究了动态约简方法中子决策信息系统的抽样策略、动态约 简结果的稳定性度量方法，并与静态约简方法进行了比较。 文章对动态约简的抽样问题进行了描述，分析了动态约简方法中 样本族的计算方法，指出了存在的不足。针对抽取出的子决策信息系 统，基于相对正域方法，度量了予决策系统与初始决策信息系统之间 的相似性，并以此对整个样本族的特征进行了评判，提出了新的样本 族确定方法。 对动态约简中的稳定性度量方法进行了分析，结合动态约简方法 的抽样策略，基于代数论观点，从相对正域和边界区域角度，对样本 族的稳定性进行了评判。根据动态约简计算方法，给出了度量函数， 通过样本族稳定性评判标准对动态约简的稳定性进行了度量。 评述了目前国内外主要静态属性约简方法，分析了动态约简与静 态约简两种方法的各自特点，进而针对同一决策信息系统，从算法结 果的角度对动态约简与静态约简两种方法进行了比较，说明了动态约 简更为稳定、有效。 论文最后对全文进行了总结，并对粗糙集理论及动态约简的发展 方向进行了展望。 关键词粗糙集，决策信息系统，动态约简，抽样，稳定性 a b s t r a c t f o rt h el a r g ec o m p l e xd e c i s i o ns y s t e m ，h o wt or e d u c ef r o md e c i s i o n s y s t e ma n dg a i nk n o w l e d g ei so n eo ft h em o s ti m p o r t a n tt a s k si nr o u g h s e tt h e o r y d y n a m i cr e d u c tm e t h o d o l o g y , w h i c hs u p p o s e da sa ne f f e c t i v e r e d u c tm e t h o d ，i st os a m p l ef r o mal a r g ed e c i s i o ns y s t e mm a n yt i m e s ， w h i c hc h a n g et h ep r o b l e mo fc a l c u l a t i n gr e d u c t sf r o mo r i g i n a lc o m p l e x d e c i s i o ns y s t e mi n t ot h a to fm a n ys i m p l es u b d e c i s i o ns y s t e m s b a s e do n t h er o u g hs e tt h e o r y , f r o mt h eb a c k g r o u n da n ds e v e r a lh i e r a r c h i e so f d y n a m i cr e d u c t ，t h i s t h e s i sd e s c r i b e st h ei d e ao fd y n a m i cr e d u c t m e t h o d o l o g y i nd e t a i l i t d e e p l yr e s e a r c h st h ep r o b l e m so fd y n a m i c r e d u c t ，s u c ha sh o wt os a m p l es u b d e c i s i o ns y s t e m si nd y n a m i cr e d u c t m e t h o d o l o g y , h o wt om e a s u r e t h es t a b i l i t yo fr e d u c t ss e t ，a n dc o m p a r e si t w i t hs t a t i cr e d u c t i o na l g o r i t h m s t h et h e s i sa n a l y z e st h ep r o b l e mo fh o wt oc o m p u t et h eq u a n t i t yo f s u b - d e c i s i o ns y s t e m sf a m i l yfi nd y n a m i cr e d u c t ，t h es h o r t a g eo ft h i s m e t h o di sa l s oi n d i c a t e d f o rt h es u b - d e c i s i o ns y s t e me x t r a c t e df r o mt h e o r i g i n a ll a r g ed e c i s i o ns y s t e m ，b a s e do nt h ev i e wo fr e l a t e dp o s i t i v e r e g i o n ，t h em e t h o do fm e a s u r i n gt h es i m i l a r i t yd e g r e eb e t w e e nt w o d e c i s i o ns y s t e m si sp r e s e n t e d ，a n dt h en e wm e t h o df o rs u b d e c i s i o n s y s t e m sf a m i l yfc o m p u t a t i o ni sp r e s e n t e d t h em e a s u r e m e n tm e t h o df o rs t a b i l i t yo fd y n a m i cr e d u c tm e t h o d o l o g yh a sb e e na n a l y z e d t h ea n a l y s i so fs a m p l i n gp r o b l e mh a sb e e n t a k e n f r o mt h ec o n c e p t so fr e l a t e dp o s i t i v er e g i o na n db o u n d a r yr e g i o n ， i t p r e s e n t s t h em e a s u r e m e n tm e t h o df o rt h e s t a b i l i t yd e g r e e o f s u b d e c i s i o ns y s t e m sf a m i l yf t h e n ，t h em e a s u r e m e n tf u n c t i o no f d y n a m i cr e d u c t sa n di t sp r o p e r t ya r ep r e s e n t e d t h ec h a r a c t e r i s t i c so fs o m es t a t i cr e d u c t i o na l g o r i t h m si nt h ep r e s e n t d o m e s t i ca n df o r e i g nl i t e r a t u r e sa r ea n a l y z e d b yt h er e d u c ta n dt h ec o r e o fd e c i s i o ns y s t e m ，i tc o m p a r e st h et w om e t h o d sf o rt h es a m ed e c i s i o n s y s t e m t h ev a l i d i t ya n ds t a b i l i t yo fd y n a m i cr e d u c th a v eb e e np r o v e d k e yw o r d s r o u g hs e t ，d e c i s i o ns y s t e m ，d y n a m i cr e d u c t ，s a m p l e ， s t a b i l i t y i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学 位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在在论 文中作了明确的说明。 作者签名：兰隘塑日期：堕年三月上日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：地导师签名：垄立嘲 日期：2 盟生年上月血日 硕士学位论文 第一章绪论 第一章绪论 粗糙集( r o u g hs e o 理论自波兰科学家z p a w l a k 提出以来，其理论与方法不断 发展，已在多个领域得到了广泛的应用。作为一种软计算方法，粗糙集理论基于 等价关系，目的是得到问题的决策或分类规则。其只根据给定决策信息系统进行 数据分析无需依靠先验知识的特点，克服了传统数据分析理论中存在的不足，引 起了国内外理论界的关注。本章介绍了粗糙集理论与方法及有关背景，评述了国 内外相关研究现状，最后简单介绍了本文的研究内容和全文结构。 1 1 引言 当今社会已经进入网络信息时代，计算机与网络信息技术飞速发展，使得社 会各行各业信息量的不断增长。由于人类的参与使数据与信息系统中的不确定性 更加显著，如何分析、理解这些大量的、无序的、强干扰的海量数据，并从其中 挖掘、发现潜在知识，帮助人类做出决策已越来越重要。虽然，人们在分析现有 的信息方面已经提出了一些用于数据挖掘的简单统计分析技术，但实用的智能数 据分析理论与技术仍不成熟。因此，寻求一种快速、高效、智能的数据分析方法 一直是数据挖掘研究者重点研究的目标之一。 2 0 世纪6 0 年代l a z a d e h 提出了模糊集理论，使得研究者能够用数学表示 含糊的概念，但对这一概念并没有给出数学公式来描述，模糊集理论因此是不可 计算的。其无法计算出它的边界线上的具体的含糊元素数目，且应用基础很大程 度上依赖于人们的某些先验知识，限制了该理论应用的客观实际性。 2 0 世纪8 0 年代z p a w l a k 提出了粗糙集理论i l 2 】，以模糊集理论、证据理论 及布尔推理方法为基础，是一种刻划不完整性和不确定性的数学工具。该理论能 有效地分析和处理不精确、不一致、不完整等各种不确定性信息，并从中发现隐 含的知识，揭示潜在的规律【3 l 。粗糙集理论自提出以来，以其广阔的适用性迅速 引起各行业的重视。以它为基础研究数据分析技术的热潮方兴未艾，近年来已形 成了较为完整的理论体系。 粗糙集理论用决策信息系统这一二维表来表示近似知识空间，表中所有对象 的集合称为论域，用属性集合描述论域中对象的特征，知识即被认为是对对象的 分类能力1 4 j 。粗糙集理论以消除冗余属性为基础，在保持分类或决策能力不变的 情况下，导出对问题的决策或分类规则集( 一个与初始决策信息系统具有相同或 相似分类能力的决策信息系统) 。其最大优点在于只使用己给数据集所提供的信 硕士学位论文 第一章绪论 息进行挖掘，不依赖于其他的模型假设。 1 2 国内外研究现状评述 粗糙集理论是一种新型的处理模糊和不完备知识软计算方法，能有效地分析 和处理不精确、不一致、不完整等各种不确定信息，该理论近年来日益受到国际 学术届的重视。软计算的概念是由模糊集创始人z a d e h 提出的，传统的计算方法 即所谓的硬计算，使用精确、固定和不变的算法来表达和解决问题，而软计算的 指导原则是利用允许的不精确性、不确定性和部分真实性以得到易于处理，鲁棒 性强和成本较低的解决方案，以便更好地与现实系统相协调。软计算中的主要工 具包括粗糙集，模糊逻辑，神经网络，概率推理，可信网络，遗传算法与其它进 化优化算法，混沌理论等。 波兰学者p a w l a kz 于1 9 8 2 年提出r s 理论，并在1 9 9 1 年出版了专著1 5 1 系 统全面地阐述了r s 理论，奠定了严密的数学基础，该书与1 9 9 2 年出版的r s 理 论应用专集1 6 1 较好地总结了这一时期r s 理论与实践的研究成果，促进了它的进 一步发展，现已成为学习和应用r s 理论的重要文献。1 9 9 2 年在波兰k i e k r z 召 开了第一届国际r s 研讨会，着重讨论了集合近似定义的基本思想及应用，其中 r s 环境下的机器学习基础研究是这次会议的四个专题之一；1 9 9 3 年在加拿大 b a n f f 召开第二届国际r s 理论与知识发现研讨会，积极推动了国际上对r s 理论 与应用的研究；1 9 9 4 年第三届国际粗糙集与软计算研讨会在美国s a nj o s e 召开， 广泛讨论了粗糙集与模糊逻辑、神经网络、进化理论等的融合问题；1 9 9 5 年， a c m c o m m u n i c a t i o n 将其列为新浮现的计算机科学的研究课题；1 9 9 5 年召开的 第四届模糊理论与技术国际会议上对模糊集和粗糙集的相互关系展开了讨论，极 大地促进了粗糙集的发展；1 9 9 6 年在日本东京召开了第五届国际r s 研讨会，推 动了亚洲地区对r s 理论与应用的研究；1 9 9 7 年3 月在美国n o r t h c a r o l i n a 召开 了第五届国际研讨会；1 9 9 8 年，国际信息科学杂志为r s 理论的研究出了期专 辑；2 0 0 0 年1 0 月，在加拿大b a n f f 召开了第二届粗糙集与计算趋势国际会议， 这次会议极大地推动了粗糙集理论在软计算、数据库、人工智能和近似推理等方 面的发展；2 0 0 4 年6 月在瑞典召开第四届在计算方面粗糙集及当前趋势的国际 会议；目前r s 理论已成为人工智能领域中一个较新的学术热点，引起了越来越 多的科研人员的关注。 从1 9 9 2 年至今，每年都召开以r s 为主题的国际会议，推动了r s 理论的拓 展和应用。国际上成立了粗糙集学术研究会，参加的成员来自波兰、美国、加拿 大、日本、挪威、俄罗斯、乌克兰和印度等国家。至今已有大约2 0 0 0 篇有关粗 糙集的论文在世界各地的学术杂志上发表，也有不少专著阐述粗糙集理论的各个 2 硕士学位论文第一章绪论 方面。目前，粗糙集理论与神经网络、演化计算、模糊系统及混沌系统已被公认 为人工智能的五大新兴技术p j 。我国学者也从9 0 年代也开展了对粗糙集合理论 与方法的深入研究，主要集中在对它的数学性质、有效算法的研究，如粗糙集理 论的知识表示、知识约简算法、粗糙逻辑等方面，取得了许多研究成果和令人瞩 目的成绩，与国际学术界之间的交流也日趋广泛。2 0 0 1 年5 月在重庆举行第一 届中国r s 理论与软计算学术研讨会( c r s s c 2 0 0 1 ) 忙l ；2 0 0 2 年1 0 月在苏州大学 举办了第二届中国r o u g hs e t 和软计算学术研讨会( c r s s c 2 0 0 2 ) ；2 0 0 3 年5 月将 在重庆邮电学院同时举办第三届中国r o u g hs e t 和软计算学术研讨会 ( c r s s c 2 0 0 3 ) 和第九届r o u g hs e t 、模糊集、数据挖掘与粒度计算国际学术会议 ( r s f d g r c 2 0 0 3 ) ；2 0 0 4 年1 0 月在浙江舟山、2 0 0 5 年8 月在辽宁鞍山和2 0 0 6 年 1 0 月在浙江金华分别已经召开或即将召开第四、五、六届中国r o u g h 集与软计 算学术研讨会，这些会议的举办表明我国r o u g hs e t 理论研究的队伍正在不断壮 大，已经得到国际同行的重视和认可。我国于2 0 0 3 年成立了中国人工智能学会 粗糙集与软计算专业委员会，粗糙集的研究队伍也更加壮大，研究成果在深度和 广度上有了更大的发展。 粗糙集理论作为一种新型的数据分析理论与方法提出以来，克服了传统知识 处理和模糊逻辑的缺陷与不足，以集合逼近的方法来描述知识，实现不确定性和 不完整性知识的处理。该理论中提出的核、约简以及上下近似集等概念，不仅为 信息科学和认知科学提供了新的科学逻辑和研究方法，而且为智能信息处理提供 了有效的处理技术。粗糙集的基本思想是以不可分辨关系为基础，通过对决策信 息系统的知识约简，达到简约知识，得到分类规则的目的。可见，知识约简是粗 糙集理论研究中的核心内容之一。所谓知识约简，即通过对决策信息系统中冗余 属性的去除，使得新得到的决策信息系统与初始决策信息系统保持相同或相似的 分类或决策能力。根据决策信息系统的结构特征，知识约简方法包括以范畴，或 属性，或规则为出发点的三种【9 】，通常所说的知识约简是针对属性而言，本文研 究的动态约简即为其中一种约简方法，在这里我们对属性约简算法进一步分析阐 述。 ( 1 ) 静态约简。 静态属性约简算法( 相对于动态约简而言) 对初始决策信息系统进行一次或 多次扫描，只针对初始系统进行操作，如直接求约简、求核等，大部分现有的基 于粗糙集理论的约简算法研究基本上都是静态的，具体采用方法基本上是启发式 约简算法。启发式算法最先由h uxh 【1 0 ，其基本思想是认为核为一个约简， 并将其作为所有约简的基础和起点，使用属性重要性为启发信息，按属性重要性 的大小逐个添加属性并入集合，直到该集合是一个约简。目前，国内外对于静态 3 硕士学位论文 第一章绪论 属性约简进行了大量深入的研究，也取得了一些成果。已经产生了很多约简算法， 其中包括基于分辨矩阵的方法【1 2 】、基于代数论观点中相对正域的方法f 1 3 】、基于 分布约简的方法1 1 4 】以及基于信息熵观点的方法【1 5 】1 5 。 上述约简算法均局限于启发式算法的比较上，虽然对决策信息系统的较优约 简的求取上取得了很好的效果( 最优约简的求取已经被w o n g s k m 和z i a r k o w 证明是n p j a r d 问题1 1 6 , 1 7 1 ) ，但是也存在的突出问题。这些算法主要针对小容量、 完全、没有增量的相容决策信息系统而言，相关的粗糙集分析软件对决策信息系 统的规模都有限制。实际决策信息系统往往数据量非常大且包含各种很多噪声， 由小样本组成的决策信息系统难以代表全体数据集的性质，从而导致决策信息系 统的约简带有局部色彩，最终得到的规则泛化能力也非常有限【l8 1 。另有几种约 简算法不在本文的研究范围内，我们将在2 3 节进行简单介绍。 ( 2 ) 动态约简。 在面对海量决策信息系统和变化决策信息系统的约简时，静态约简算法根据 初始决策信息系统求得的约简非常不稳定，带有很大的局部色彩，而且计算量极 大。针对动态建立数据库的要求以及静态约简算法的存在的问题，在面临海量数 据时，j a n g b a z a n 提出的动态约简算法【1 9 , 2 0 , 2 1 提供了一种新的约简方法，希望能 很好的解决在静态约简解决海量数据时得出的约简或决策规则不够稳定的问题。 该算法的实质是对复杂大型决策信息系统进行多次抽样，把复杂决策信息系统的 约简问题转化为若干子决策信息系统约简的交集【”1 ，以寻求最优、最稳定的约 简的问题。 动态约简方法的思想是为了寻求稳定存在决策信息系统中的、绝对不能够去 除的属性集合( 这可以认为是约简) ，其采用的方法是对初始决策信息系统进行大 量的随机的子决策信息系统的抽取，进而对所有子决策信息系统求取约简并求交 集，得到的约简从某种意义上说是初始决策信息系统中最稳定的约简。这也正是 动态约简方法所追求的目标。文 1 9 2 1 提出动态约简算法是一套较为完整的理论 体系，包括f 族一动态约简和f 族一广义动态约简两种方法，在理论上为决策信息 系统寻求稳定约简奠定了初步基础。 目前关于动态约简方法的研究还很不充分，b a z a n 的算法在子决策信息系统 的抽样策略和动态约简的稳定性分析等关键问题的描述上显得过于简单，缺乏充 分性，国内外有关动态约简方法方面的文献屈指可数，很多问题可以继续深化和 完善。现有的大多数文献多是将动态约简作为种方法应用到不同的学科或领域 中，对该学科或领域中某些问题的解决提供参考或方法帮助，更多只是将其作为 一种约简方法在有关属性约简的学位论文中引用。如文1 2 2 将动态约简方法应用 到故障诊断专家系统中，希望通过引入该方法建立故障规则自动获取系统，并增 4 硕士学位论文 第一章绪论 强系统处理不完备信息和自动获取规则知识的能力。 本文对动态约简方法进行了深入细致地分析，在子决策信息系统的抽样策略 和动态约简的稳定性分析等问题上进行了详细的探讨和研究，并将其与静态约简 方法进行了比较。文章做了大量的基础性和前瞻性工作，如在对动态约简的抽样 分析和稳定性分析的过程中，提出了子决策信息系统与初始决策信息系统相似度 的比较方法，以及通过对样本族的稳定性度量达到对动态约简稳定性度量目的的 方法等等，为动态约简理论体系的进一步完善做了一定的工作。 1 3 本文主要研究内容及全文结构 针对静态约简算法在面对海量数据和增量变化数据的处理时，所表现出的求 得的约简非常不稳定，带有很大的局部色彩，而且计算量巨大等问题，b a z a n 提 出了动态约简算法。动态约简从某种意义上说被认为是存在于决策信息系统中的 最稳定的约简，在面对海量数据和增量数据时所表现出的，比静态约简算法更高 效、更稳定的特点，使得其受到了广泛的重视，因而，动态约简的深入研究有助 于对粗糙集理论的深刻理解，对面对海量数据集的寻求高效约简理论与方法的研 究也具有指导性意义。 本文以动态约简方法的研究为核心内容，在详细分析动态约简理论体系之 后，针对b a z a n 算法在子决策信息系统的抽样策略和动态约简的稳定性分析等关 键问题上描述过于简单，缺乏充分性，亟待完善的问题，分别就动态约简的抽样 策略和稳定性问题作了深入研究，从代数论观点，提出了一种子决策信息系统与 初始决策信息系统相似性比较方法，进而提出了改进的抽样策略，并在此基础上 很好的解决了动态约简样本族，的稳定性度量问题，达到了度量动态约简结果 稳定性的目的。之后，引用动态核的概念，对静态属性约简算法与动态约简进行 了比较研究，并从理论上证明了动态约简方法更为稳定、有效。 根据以上研究内容，论文各个章节安排如下： 第一章，绪论。本章简单介绍了粗糙集合理论的发展，分析了国内外研究现 状，描述了本文的主要内容及结构安排。 第二章，粗糙集理论及静态约简方法。本章详细描述了粗糙集理论的产生背 景、研究内容、发展过程及特点，对粗糙集中的一些基本概念，如决策信息系统、 不可分辨关系、上下近似集等进行了介绍，紧接着重点介绍了分辨矩阵的构造方 法和分辨函数的运算，以及如何利用分辨矩阵和分辨求得决策信息系统的约简与 核，这也是动态约简方法实现的基础。在之后的小节中，对目前国内外存在的静 态约简方法进行了综述，分析了各自的特点，为第三章引出动态约简方法打下基 础。 5 硕士学位论文 第一章绪论 第三章，动态约简方法概述。本章分析了动态约简方法的提出背景，借鉴了 b a z a n 提出的动态约简方法的基本思想，并对其进行了详细分析和描述。在经过 作者整理之后，进行了调整改进，突出了动态约简的本质，将其概括为，族动 态约简、( f 的动态约简和广义动态约简三个部分，在理论上更加完善，使之成为 更为完备的理论体系，为本文后半部分动态约简的抽样分析和结果集的稳定性问 题的探讨奠定了基础。 第四章，动态约简方法的抽样策略。动态约简结果有效与否的关键在于动态 约简样本族大小的如何确定。该章分析了b a z a n 方法中子决策信息系统样本族f 的抽取方法，指出了其中存在的不足：之后，基于代数论中相对正域的观点，给 出了一种度量子决策信息系统与初始决策信息系统之间相似度( 或代表度) 的方 法，进而确定了动态约简f 族大小计算的新方法；最后给出了几个评估动态约 简f 族质量的参数。 第五章，动态约简集的稳定性分析。该章结合动态约简方法中f 族样本的 抽取问题，对动态约简结果的稳定性问题进行了探讨，详细分析了b a z a n 方法的 不足之处，阐述了动态约简结果的稳定性和随机抽取出来的f 族之间的关系，在 此基础上，根据第四章中f 族的确定方法，给出了一种基于粗糙集理论的动态 约简稳定性度量方法，及其度量函数，为动态约简稳定性的进一步研究提供了一 个理论依据。 第六章，动态约简和静态约简方法比较。决策信息系统的属性约简一直是粗 糙集理论研究中的核心内容之一，通常认为得到的约简较静态约简方法更为稳 定。该章对近年来的出现的有代表性的静态属性约简方法进行了评述，之后针对 同一决策信息系统，从算法结果的角度，对动态约简与静态约简方法进行了比较， 并说明了动态约简更为稳定、有效。 第七章，总结与展望。该章对论文的研究工作进行总结，指出进一步研究工 作的重点和方向。 6 硕士学位论文第二章粗糙集理论及静态约简方法 第二章粗糙集理论及约简方法 粗糙集理论是一种刻划不完整性和不确定性的数学工具。其主要思想就是在 保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前， 粗糙集理论已经在许多学科与工程领域得到成功的应用。本章介绍标准粗糙集的 基本理论，以及粗糙集理论中国内外现有的一些静态约简方法的基本概念和各自 特点，作为下一章引出动态约简概念的理论基础。 2 1 粗糙集理论的产生、研究的基本内容及发展 2 1 1 粗糙集理论的产生背景及基本研究内容 自1 8 世纪德国数学家gw tl e i b n i z 倡导用通用符号语言和逻辑演算改革形 式逻辑学，到19 世纪德国数学家gf r e g e 等人建立命题演算和一阶谓词演算系 统以来，形成了数理逻辑学体系【2 3 1 。这种经典逻辑中只有真、假二值之分，但 实际上有大量含糊现象存在于真与假之间。因此，长期以来许多逻辑学家和哲学 家就致力于研究含糊概念。在1 9 0 4 年，谓词逻辑的创始人g f r e g e 就提出了含糊 一词，并把它归结到边界线，也就是说在全域上存在一些个体既不能在其某个子 集上被分类，也不能在该子集的补集上被分类。 2 0 世纪6 0 年代初，l a z a d e h 提出了模糊集，不少理论计算机科学家和逻 辑学家，试图通过这一理论解决gf r e g e 的含糊概念，但遗憾的是，模糊集是不 可计算的，没有给出数学公式描述这一含糊概念，故无法计算出它的边界线上的 具体的含糊元素数目。8 0 年代初，z p a w l a k 针对g f r e g e 的边界线区域思想提出 了粗糙集【2 ，他把那些无法确认的个体都归于边界线区域，而这种边界线区域 被定义为上近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价 关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，即在真假二 值之间的含糊程度可以计算，从而实现了g f r e g e 的边界线思想。粗糙集理论主 要兴趣在于它恰好反映了人们用粗糙集方法处理不分明问题的常规性，即以不完 全信息或知识去处理一些不分明现象的能力，或依据观察、度量到的某些不精确 的结果而进行分类数据的能力。 目前来看，粗糙集理论研究的内容主要包括以下几个方面： ( 1 ) 决策信息系统的约简 粗糙集理论采用决策信息系统这一二维表作为研究的样本空间，用属性集来 描述表中对象的特征，通常属性集分为条件属性集和决策属性集。粗糙集理论从 7 硕士学位论文 第二章粗糙集理论及静态约简方法 决策信息系统推导得出分类或决策规则集，其数据分析过程1 2 5 】如下 目依 标对赖重属规知 信 象 关要属性值值则识 息 + 分 + 系 + 性 + 性 - i t , 约 + 核 - i p 约 - i i ,a_ 表口 系类 分分核简简并不 统析析 图2 - 1 粗糙集数据分析过程 过程中关键步骤为属性约简和值约简的求取。决策信息系统属性约简的目的 是去除条件属性集中冗余的属性，提取出相对稳定条件属性集合，以此达到降低 存储空间、加快数据处理时间和提高规则泛化能力。通常属性约简过程希望寻求 得到决策信息系统的最小或最优约简( 即可认为是约简中条件属性最少1 ，但这已 经被w o n g s k m 和z i a r k o w 证明是n ph a r d 问题1 1 6 , 1 7 1 ，通常运用启发式算法 得到较优约简。 决策信息系统的值约简对已求得的约简集进行操作，其目的是使某一决策的 条件达到最小化，从而用最少的信息做出最正确的判断。为了得到适应能力更强， 对新对象具有最大匹配能力的规则，必须对求得的约简进行泛化，去掉其中存在 的不必要条件属性信息，进行属性值约简。在对约简求所有规则( 即一个完备的 规则集) 过程中，需要考虑单属性规则、二属性规则依次到所有属性规则，那么 对某一条规则而言，需考虑其所有的条件属性组合，属性值约简问题即成为一 n p - h a r d 问题( 主要原因是属性的组合爆炸问题) ，这个问题在目前仍然还没有得 到很好的解决。目前广泛应用的基于粗糙集理论的属性值约简的方法是分辨矩阵 法【2 6 i 和标记法旧，但这两种方法都不是针对某个决策信息系统求出一个完备性 的规则集。 ( 2 ) 不完全决策信息系统的处理 从不完全决策信息系统( 含有空值暂时无法得到的值，称这种决策信息 系统为不完全决策信息系统) 产生决策树已被人工智能界注意。处理空值的简单 方法是删除带有空值的对象或用最常用值( 由取值概率确定) 代替空值。空值的概 率分布可用贝叶斯范式估计。也有用其他条件属性和决策属性的取值关系来估计 空值的做法。文【2 8 】利用模糊集理论处理空值引起的不确定。 在粗糙集商业软件l e r s 中，还提到一种处理空值的方法：即用可能的取值 代替空值，根据不同的组合把不完全决策信息系统转化为若干完全决策信息系 统。但这种方法的复杂性高，在空值属性较多或空值可能取值较多的情况下，效 率很低。 8 硕士学位论文第二章粗糙集理论及静态约简方法 在文【2 9 中，s l o w i n s k i 比较了几种不完全决策系统的分析方法，得出了以下 结论：第一，如果一个规则在原不完全系统的每个完全( 组合) 拓展中是确定的， 那么这个规则是确定的；第二，从不完全决策信息系统中删除包含空值的对象后， 获取的知识可能为伪规则( 对原不完全系统不一定成立) 。文 3 0 应用分辨矩阵， 推广了等价关系( 相似关系) 、集合近似等概念，研究了不完全决策信息系统的决 策信息系统约简和规则发现问题，从而为粗糙集理论的实用化迈出了可喜的一 步。文 3 0 提出的约简方法的特点是不需改变原不完全决策信息系统。 有关不完全决策信息系统的处理，文 3 l 】还提出了一种基于粗糙集的数据开 采模型。该模型先建立一系列不同简化层次的子系统，然后推导出各子系统的规 则集。在应用模型决策时，用给定对象的信息与模型相应层次节点的规则匹配， 根据某种算法做出决策。目前有关不完全信息的处理，仍是粗糙集应用的难点。 ( 3 ) 连续属性的离散化 粗糙集理论的数学基础是集合论，因而难以直接处理连续的属性。但现实决 策信息系统中连续属性是普遍存在的，因此连续属性的离散化是制约粗糙集约简 实用化的难点之一。连续属性的离散化的根本出发点是在尽量减少决策信息系统 信息损失的前提下( 保持决策信息系统不同类对象的可分辨关系) ，得到简化的和 浓缩的决策信息系统，以便用粗糙集理论分析，获得决策所需要的知识。离散化 的根本任务是把连续属性的取值范围或取值空间划分为若干个数目不太多的小 区间，其中每个小区间对应着一个离散的符号。 离散化结果应满足下列两点：第一，连续属性离散化后的空间维数尽量小， 也就是每一个离散化后的属性值的种类尽量少：第二，属性值被离散化后的信息 丢失尽量少。现有实验已经证明最优离散化问题( 离散的切点数最少) 是一种 n p h a r d 问题i j “，利用一些启发式算法可以得到较满意的结果。目前对连续属性 离散化的方法主要分为两类：一类是仅对每一个属性的属性值进行划分的局部离 散方法( l o c a ld i s c r e t i z a t i o nm e t h o d ) ，包括等宽区间法( e q u a l w i d t h i n t e r v a l s ) 、等 频区间法( e q u a l - f r e q u e n c y i n t e r v a l s ) 以及利用分类熵准则( 如e f 和m c e ) 划分；一 类是考虑全部条件属性的属性值进行划分的全局离散方法( g l o b a ld i s c r e t i z a t i o n m e t h o d ) ，包括归并方法、划分方法及串分析方法口”。 ( 4 ) 粗糙集与其他研究方向的集成 粗糙集约简和其他计算方法的结合，能够提高数据开采能力，这是由现实世 界的复杂性和处理方法有限能力的矛盾决定的。其中粗糙集与神经网络的结合是 研究的热点。通常，粗糙集约简对噪声敏感且泛化能力弱，可以用神经网络的优 点( 自组织、容错和推广能力) 来弥补；神经网络不能确定重要性的属性组合、结 构构造缺乏通用的房法且推理过程不透明等不足，可以用粗分析辅助。粗分析和 9 硕士学位论文 第二章粗糙集理论及静态约简方法 神经网络的结合实质上是人类两种思维方式_ j 翌辑思维和形象思维的结合。寻 找新的结合方法是一个值得讨论的问题。 有关粗糙集理论与遗传算法、模糊集理论等软计算方法的结合也屡见不鲜。 文 3 4 1 在并行虚拟机环境下结合遗传算法和粗糙集理论结合实现了种数据开 采模型，即利用遗传算法设计一种自适应粗糙集模型。这种模型能够获得比传统 粗糙集模型更好的结果。 此外，模糊集与粗糙集的约简思想结合用于模糊一粗糙控制器，用来获取和 表达知识。约简思想与统计方法结合，粗糙集与p e t r i 网、主分量分析( p c a ) 、支 撑向量机( s v m ) 、b a y e s i a n 方法也有报道。粗糙集与其它软计算方法的集成是数 据开采的一种趋势。 粗糙集理论与模糊集理论同为刻画不完整性和不确定性的数学工具，较模糊 集理论而言，其可以用数学方法定义不确定性信息的特征决定了理论本身的优越 性。其特点主要在于： ( 1 ) 粗糙集无需先验知识。通常采用模糊集和概率统计方法来处理不确定信 息，但都需要一些数据的附加信息或先验信息，如模糊隶属函数和概率分布等， 并且这些信息有并不容易获取。而粗糙集理论方法只根据给定数据本身提供的信 息进行分析，无须任何先验知识。 ( 2 ) 粗糙集可以通过数学公式表达和处理不完备信息。粗糙集理论能在保留 关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估数据 之间的依赖关系，揭示出概念简单的模式；能从经验数据中获取易于证实的规则 知识，特别适于智能控制。 ( 3 ) 粗糙集与模糊集刻划的是不完备信息的两个方面【3 5 1 ：粗糙集理论以不 可分辨关系为基础，侧重分类；模糊集基于元素对集合隶属程度的不同，强调集 合本身的含混性。从粗糙集的观点看，粗糙集合不能清晰定义的原因是缺乏足够 的论域知识，但可以用一对清晰集合逼近。有关粗糙集和模糊集内在联系的阐述 及模糊粗糙集的概念可以参看文 3 6 。另外，粗糙集理论和证据理论也有一些相 互交叠之处【3 7 】，在实际应用中可以相互补充。 2 1 2 粗糙集理论的应用现状 粗糙集理论的影响已经渗透到信息科学的几乎所有分支，自粗糙集理论诞生 以来，几十年间已经形成比较完善的理论体系。目前，该理论己成为信息科学最 为活跃的研究领域之一，在医学、化学、材料学、地理学、管理科学和金融等学 科，以及模式识别、机器学习、决策支持、过程控制、预测建模等工程领域得到 1 0 硕士学位论文第二章粗糙集理论及静态约简方法 了成功的应用。其强大的生命力表现为该理论具有很强的实用性，大概可以分为 以下几个方面： 1 大数据集分析。其中包括股票数据分析、医疗诊断分析、地震预报等方面。 文 3 8 应用粗糙集方法分析了十年间股票的历史数据，研究了股票价格与经济指 数之间的依赖关系，获得的预测规则得到了华尔街证券交易专家的认可。文【3 9 应用粗糙集方法根据以往的病例归纳出诊断规则，用来指导新的病例。现有的人 工预测早产的准确率只有1 7 一3 8 ，应用粗糙集理论则可提高到6 8 一9 0 。文 4 0 研究了地震前的地质和气象数据与里氏地震级别的依赖关系。 2 人工智能。如模式识别、专家系统( e s ) 及人工神经网络( a n n ) 等。文 4 1 应用r s 方法研究了手写字符识别问题，提取出了特征属性。文 4 2 r s 抽取规则 的特点，为构造e s 知识库提供了一条崭新的途径。训练时间过于漫长的固有缺 点是制约a n n 实用化的因素之一。文【4 3 】应用粗糙集化简神经网络训练样本数 据集，在保留重要信息的前提下消除了多余的数据，使训练速度提高了4 7 2 倍， 获得了较好的效果。文【4 4 】将r s 与a n n 结合起来，充分利用r s 处理不确定性 的特长以增强a n n 的信息处理能力。 3 知识发现。k d d 又称数据发掘，是当前人工智能和数据库技术交叉学科 的研究热点之一。r s 方法现已成为k d d 的一种重要方法，其导出的知识精炼 且更便于存储和使用。 己经开发的基于粗糙集理论的知识发现系统主要有【4 5 】：l e r s 系统是美国 k a n s a s 大学开发的基于粗糙集的实例学习系统主要用于环境保护、气候研究和 医疗研究等。r o s e 系统是波兰p a z n a n 工业大学计算科学研究所智能决策支持 系统实验室研制的。该系统实现了p a w l a k 的基本粗糙集模型和可变精度粗糙集 模型，并成功应用于医学、药剂学、技术诊断、金融和管理科学、图像与信号处 理、软件工程评估等。 k d d r 系统是由加拿大r e g i n a 大学研制的，它基于可变精度粗糙集模型， 采用知识发现的决策矩阵方法。用于医学数据分析和电信市场的决策分析等。 r o u g he n o u g h 是挪威t r o l ld a t ai n c 公司开发的，包括数据输入、预处理、 编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析。 除以上系统外，还有一些其他系统，如加拿大r e d u c ts y s t e mi n c 公司开发 的d a t a l o g i c r ，中国科学院计算技术研究所开发的k d t 和南京大学研制的 k n i g h t 等。 4 粗糙控$ 1 1 4 6 , 4 7 , 4 8 1 。粗糙集理论根据观测数据获得控制策略的方法被称为从 范例中学习，属于智能控制范畴。基本步骤是：把控制过程中的一些有代表性的 状态以及操作人员在这些状态下所采取的控制策略都记录下来，形成决策信息系 硕士学位论文 第二章粗糙集理论及静态约简方法 统，然后对其分析化简，总结出控制规则，形成为：i fc o n d i t i o n = n 满足t h e n 采取d e c i s i o n = m 。粗糙集方法是一类符号化分析方法，需要将连续的控制变量 离散化，为此z p a w l a k 提出了粗糙函数的概念，为粗糙控制打下了理论基础。 文 4 6 ，4 7 应用粗糙控制研究了“小车一倒立摆系统”这一经典控制问题，取得了 较好的结果。在过程控制领域，文 4 8 应用粗糙集方法成功地提取出了水泥窑炉 的控制规则。粗糙控制的优点是简单迅速、实现容易、不需要象模糊控制那样进 行模糊化和去模糊化。因此在特别要求控制器结构与算法简单的场合，采取粗糙 控制较为合适。另外，由于控制算法完全来自观测数据本身，其决策和推理过程 可以很容易被检验和证实。一种新的有吸引力的控制策略“模糊一粗糙控制”正 悄然兴起，其主要思路是利用粗糙集理论获取模糊控制规则。 5 人文社科及管理科学。比如在冲突分析方面，文 4 9 应用r s 方法建立了 反映以色列、巴勒斯坦、约旦、叙利亚和沙特阿拉伯等六国关于中东和平问题各 自立场的谈判模型；在决策分析方面，粗糙集的决策规则是在分析以往经验数据 的基础上得到的1 5 0 “。粗糙集允许决策对象中存在一些不太明确、不太完整的属 性，弥补了常规决策方法的不足。希腊工业发展银行e t e v a 应用r s 理论协助 制定信贷政策，是粗糙集多准则决策方法的一个成功范例。 r s 理论的应用领域还包括：近似推理、软件工程数据分析、图象处理、材 料科学中的晶体结构分析、预测建模、结构建模、投票分析、电力系统等。粗糙 集自提出以来直得到模糊数学的创始人l a z a d e h 的重视，并给予很高的评价， 把它列入他新提倡的软计算的基础理论之一。由此可见，粗糙集理论及其广泛应 用将越来越受到重视。 2 2 粗糙集理论的基本概念 2 2 1 决策信息系统、不可分辨关系 面对现实世界中纷繁复杂的问题，粗糙集理论用决策信息系统这一二维表来 表示现实世界，作为研究的样本空问。表中所有对象的集合称为论域，用属性集 合描述论域中对象的特征，决策信息系统可以根据知识表达系统定义如下： 定义2 - l 对于决策信