（计算机应用技术专业论文）基于程序演化的rs高效求核算法的研究.pdf

摘要 目前，数据挖掘( d a t am i n g ，d m ) 采用的较新技术是粗糙集( r o u g hs e t ，r s ) 。 它在分析和处理不完整、不一致和不精确的数据并进行知识的约简时不需要先验经验。 粗糙集主要的研究内容是属性约简，而求核属性是属性约简的关键步骤。现在很多约简 算法是从核属性开始，然后通过启发式搜索找到最小约简。差别矩阵求核方法是常用的 求核方法，许多学者在此基础上进行了改进，但是其效率都不是很理想。程序演化作为 提高算法效率的新的方向和途径，在国内外已经引起了广泛的关注，将其用于提高差别 矩阵求核算法是一个新的方向。 本文围绕提高算法效率的程序演化策略，探索应用演化策略来改进差别矩阵求核算 法。本文的主要工作如下： ( 1 ) 阐述差别矩阵求核原理，对最新基于差别矩阵求核改进算法进行了研究分析， 总结差别矩阵求核算法效率不高的一些原因，为降低算法复杂度提供思路。 ( 2 ) 依据程序演化的应用方式特点，实现使用h a s k e l l 函数式语言规范描述差别矩 阵求核算法。先不考虑其算法的效率，但保证其正确性，为以后的演化提供基础。 ( 3 ) 分析研究规范描述的差别矩阵求核算法，结合算法低效率的原因，使用程序 演化中t u p l i n g 与a c c u m u l a t i o n 演化策略对程序进行优化，提高算法的效率。 ( 4 ) 研究分析演化后的算法，引入数据集合划分方法以提高生成差别矩阵的效率， 再结合使用a c c u m u l a t i o n 演化策略对以上算法进行优化。演化后的求核算法比原差别矩 阵求核算法效率高，使用仿真试验证明本文算法的正确性和高效性。 关键词：粗糙集；核属性；程序演化；t u p l i n g 演化策略；a c c u m u l a t i o n 演化策略 a b s t r a c t r o u g hs e ti san e wt e c h n o l o g yf o rd a t am i n i n g , w h i c ha n a l y z i n ga n dp r o c e s s i n gt h e i n c o m p l e t e ，i n c o n s i s t e n t a n di n a c c u r a t ed a t aa n dr e d u c i n gk n o w l e d g ew i t h o u t p r i o r e x p e r i e n c e a t t r i b u t er e d u c t i o n , t h ek e ys t e po fw h i c hi ss e e k i n ga t t r i b u t ec o r e s ，i sm a j o r r e s e a r c hc o n t e n t so fr o u g hs e t t h em o s to fr e d u c i n ga l g o r i t h m sb e g i nw i t ha t t r i b u t ec o r e s t h o u g hh e u r i s t i cs e a r c ht ot h em i n i n l u nr e d u c t i o n s e e k i n g a t t r i b u t ec o r e sb a s e do n d i f f e r e n t i a lm a t r i xi st h ec o m m o nm e t h o d ，w h i c hi si m p r o v e db ym a n ys c h o l a r sb u th a d l o w e f f i c i e n c y p r o g r a mt r a n s f o r m a t i o n , a san e w d i r e c t i o na n dw a yo fi m p r o v i n gt h ee f f i c i e n c yo f a l g o r i t h m sh a sa l r e a d yc a u s e dt h ee x t e n s i v ec o n c e r na th o m ea n da b r o a d u s i n gp r o g r a m t r a n s f o r m a t i o nt oi m p r o v et h ee f f i c i e n c yo fs e e k i n ga t t r i b u t ec o r e sa l g o r i t h mb a s e do n d i f f e r e n t i a lm a t r i xi san e wd i r e c t i o n c e n t e r i n go ns t r a t e g i e so fp r o g r a mt r a n s f o r m a t i o nt oi m p r o v et h ee f f i c i e n c yo fa l g o r i t h m i nt h i sp a p e r , u s i n gt h a tt oi m p r o v et h ee f f i c i e n c yo fs e e k i n ga t t r i b u t ec o r e sa l g o r i t h mb a s e d o nd i f f e r e n t i a lm a t r i x t h em a i nw o r ki nt h i sp a p e ri sa sf o l l o w s ： ( 1 ) p r i n c i p l eo fs e e k i n ga t t r i b u t ec o r e sa l g o r i t h mb a s e d o nd i f f e r e n t i a lm a t r i xi sd e s c r i b e d ， a n da n a l y z e dt h el a t e s tr e s e a r c ho ns e e k i n ga t t r i b u t ec o r e si m p r o v e da l g o r i t h m sb a s e do n d i f f e r e n t i a lm a t r i x t h er e a s o n so fl o we f f i c i e n c yo f a l g o r i t h m sa r es u m m a r i z e d ，w h i c ho f f e r i d e a sf o rr e d u c i n gt h ec o m p l e x i t yo fa l g o r i t h m ( 2 ) a c c o r d i n gt oc h a r a c t e r i s t i c so fa p p l i c a t i o nm e t h o d so fp r o g r a mt r a n s f o r m a t i o n , s p e c i f i l yd e s c r i b e ss e e k i n ga t t r i b u t ec o r e sa l g o r i t h m sb a s e do nd i f f e r e n t i a lm a t r i xb yh a s k e l l f u n c t i o n a ll a n g u a g e t h ee f f i c i e n c yo fa l g o r i t h mc o u l dn o tc o n s i d e r e da tf i r s t , b u tt h e c o r r e c t n e s so fw h i c hi sg u a r a n t e e d ，t h a ti st h eb a s i co ft r a n s f o r m a t i o n ( 3 ) a f t e ra n a l y z i n ga n dp r o c e s s i n gt h es p e c i f i l yd e s c r i b e ss e e k i n ga t t r i b u t ec o r e s a l g o r i t h m sb a s e do nd i f f e r e n t i a lm a t r i x ，c o m b i n e dw i t ht h er e a s o n so ft h el o we f f i c i e n t a l g o r i t h m ，u s i n gt u p l i n ga n da c c u m u l a t i o ns t r a t e g i e so fp r o g r a mt r a n s f o r m a t i o nt oi m p r o v e t h ee f f i c i e n c yo fa l g o r i t h m ( 4 ) a r e ra n a l y z i n gt h ei m p r o v e da l g o r i t h mb ys t r a t e g i e so fp r o g r a mt r a n s f o r m a t i o n ，u s m g am e t h o dt od i v i d ed a t as e ti n t os u b s e t st oi m p r o v et h ee f f i c i e n c yo fc r e a t i n gd i f f e r e n t i a l m a t r i x ，t h e nc o m b i n e s 丽ma c c u m u l a t i o ns t r a t e g i e st oo p t i m i z et h ea l g o r i t h m t h ei m p r o v e d a l g o r i t h ma f t e rp r o g r a mt r a n s f o r m a t i o nc o m p a r e sw i t ht h eo r i g i n a ls e e k i n ga t t r i b u t ec o r e s a l g o r i t h m sb a s e do nd i f f e r e n t i a lm a t r i x ，t h ef o r m e rh a sh i g h e re f f i c i e n c y c o m p u t e r s i m u l a t i o ns h o wt h a tt h ec o r r e c t n e s sa n dh i g he f f i c i e n c yo fa l g o r i t h mp r o p o s e di nt h i sp a p e r i i k e yw o r d s ：r o u g hs e t ；c o r ea t t r i b u t e ；p r o g r a mt r a n s f o r m a t i o n ；t u p f i n gs t r a t e g y ； a c c u m u l a t i o ns t r a t e g y n i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：犹缎 日期：，年 占月弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 甏缎 彳瓠 日期：i ) 年6 月3 日 日期：f 啤6 月 1 1 引言 第一章绪论 随着计算机网络的发展，人们积累的数据越来越多，仅靠专业经验及传统工具分析 数据，已不能从日益增多的数据中提出隐藏的重要信息，这就给人类的智能信息处理能 力提出了前所未有的挑战，于是产生了人工智能研究的一个崭新领域数据库知识发现 ( k n o w l e d g ed i s e o v e r y i nd a t a b a s e ，k d d ) 和数据挖掘( d a t am i n i n g ，d m ) 用于从海 量数据中挖掘有用知识。目前，d m 所采用的技术主要有神经网络、遗传算法、决策树、 粗糙集、统计方法等。 粗糙集理论是d m 中相对较新的一种技术。它的诞生是为了分析处理大量现实世界 的不是和经典逻辑一样，不是真就是假，而是含糊在真假之间的现象所导致的含糊、不 确定性问题。其特点是在处理问题所需的数据集合时不需要任何的先验经验。粗糙集理 论的重要研究内容一属性约简，其目的在于在保持知识库分类能力不变的条件下，通过 知识约简，删除其中不必要( 不相关或不重要) 的属性，使知识简化，又不失去人们需 要的基本信息。这样一方面可大大提高系统知识的清晰度，另一方面有助于从复杂的决 策系统中获取简洁的决策规则。 现有的很多属性约简算法都是从信息系统的核属性开始，然后再由核属性通过启发 式知识扩展到最小约简。粗糙集理论并没有提供直接从信息系统中求核的方法。根据核 属性的定义来求核，需先求出该信息系统的所有约简，再通过求交集得到核属性集。根 据粗糙集理论定义，寻找属性的最小简化是一个n p h a r d ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 问题馏，因此需要研究更为有效的求核算法成为本文研究的目标。程序演化作为一种新 的提高算法效率的理论方法，其研究与应用已逐渐引起学者们的高度关注。 1 2 国内外研究现状 1 2 1 程序演化 r b i r d 在1 9 8 7 年首先提出了程序演化的概念船1 。随后r b i r d 等人将范畴理论引入程 序演化中“s 1 ，从程序代数的角度建立了程序演化的理论基础，完善了b i r d m e e r t e n s 形 式体系，并应用于程序优化。 程序演化不使用经典程序变换的f o l d u n f o l d 形式，而是应用结构算法理论来进行程 序的规范化描述。在结构算法理论的基础上建立演化规则( r u l e s ) ，在结构算法理论中 演化建立在程序代数的基础之上，将程序的数据结构看作为代数中的项，控制结构看作 代数的同构映射，应用范畴函数描述程序的变换，由于具有严谨的数学理论基础，因此 应用程序演化方法更容易建立严格、简明的程序规范描述和演化的规则。 程序演化方法把程序的数学结构作为程序开发的基础。将程序看成数学对象，程序 设计看成数学活动，在程序设计中基于演化规则的数学推理扮演核心角色。从这样的观 点出发，编程原则可以被严格地形式化描述，程序设计者能遵循和应用这些原则，而不 仅仅是依靠经验积累进行程序设计。这方向的研究对程序设计方法学的发展有重要影 响。 程序演化方法的理论研究与应用已引起软件理论研究者的高度关注：余金山m 1 引入 p r o l o g 语义定义给出语义保持变化规则；z h e n j i a n gh u h l 应用程序演化方法到优化数据挖 掘关联规则中寻找频繁项集中；张红等给出了函数式语言到过程式语言转换的关键技术 阳1 ，并被成功地应用于高效程序开发曲、并行程序设计“等领域；a l c i n oc u n h a n 2 1 等把程 序演化应用于软件演变的资料处理程序中；j o h nr e g e h r n 3 1 等用程序演化工具把中断驱动 程序传感器应用软件代码转换为多线程代码，用来提高程序的并行性，提高程序效率。 1 2 2 粗糙集理论及其求核算法 粗糙集理论是由z p a w l a k 于十九世纪八十年代首先提出，它是作为处理含糊性和 不精确性问题的数学理论，是一门实用性很强的学科。从上世纪九十年代起，粗糙集理 论及其学习与知识发现、数据挖掘、决策支持与分析、模式识别等方面的广泛应用n “， 使得该理论受到了国内外学者的关注而得到快速发展。 1 9 9 1 年粗糙集的创始人发表专著 r o u g h s 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 ga b o u t d a t a ) ) ，奠定了粗糙集理论的基础，意味着粗糙集理论的成熟，推动了粗糙集的研究。 1 9 9 2 年r s l o w i n s k i 主编出版论文集关于粗糙集应用及其与相关方法的比较研究，对这 一段时间理论和实践工作的成果作了较好的总结，推动了国际上对粗糙集理论及其应用 的深入研究。同年第一届国际粗糙集讨论会在p o l a n d 召开，并以此为标志粗糙集理论开 2 始了国际化研讨，从此以后，每年召开一次以粗糙集理论为主题的国际研讨会，召开的 与粗糙集相关的会议进一步推动了粗糙集的发展，如2 0 0 7 年在c a n a d a 召开了r s f d g r c 0 7 与r s k t 0 7 联合会议，使得越来越多的学者开始了解并且准备从事该领域的研究。 2 0 0 1 年5 月我国在重庆召开了“第1 届中国r o u g h 集与软计算学术研讨会”，邀请 了z p a w l a k 教授做大会报告。此后，国内也每年举行一次粗糙集与软计算的学术讨论， 如2 0 0 6 年1 0 月在浙江召开第6 届中国粗糙集会议。2 0 0 3 年中国成立了人工智能学会粗 糙集与软计算专业委员会( c r s s c a a i ) ，以加强高校间合作与交流，促进国内外学术交 流，推动中国人工智能、粗糙集与软计算理论研究及其应用发展。高水平的国内学术会 议，如2 0 0 7 年8 月c r s s c 2 0 0 7 在山西大学的召开，推动了粗糙集理论与应用在亚洲地 区和我国的研究。国内各研究机构和高校在开始了粗糙集理论及应用的研究后，涌现了 苗夺谦n “、王国胤“町等一批研究粗糙集理论的著名学者，并取得了一定的成果。 粗糙集理论能够研究和解决实际问题，短短二十多年的时间，其应用研究已经在很 多领域取得一定的成果。例如，交通运输n7 埔1 、图像处理n 轴1 、决策分析乜、医学诊断唿矧、 农业乜衢1 、房地产哺1 等。 属性约简作为粗糙集理论的重要研究内容，约简算法的效率成为人们所关注的重 点，求核运算是属性约简的关键，直接影响着知识约简的效率，因此许多学者围绕如何 提高求核运算效率展开了研究。 黄丽萍【2 钊以协调信息系统中条件属性的划分相对于决策属性划分的概率分布为单点 分布的性质，提出一种新的求核算法。由于采用概率分布的计算方法相对于条件信息熵 的计算方法更简单，所以能减少不必要的计算。算法时间复杂度为o ( i a l 2 i u i l o g l u i ) 。 蒋开平、胡彩萍、段志锋啪等在深入分析粗糙集中核心概念的基础上，从广义映射 的观点对相关的概念进行另一种形式的定义，给出了基于这种定义形式的相关性质，并 给出了关于正区域及属性重要度的改进计算方法。但是只是从理论上证明了提出的概念 与原定义的等价性及算法的有效性。 a s k o w r o n t s l 提出的基于差别矩阵的方法易于理解和计算核属性，也便于约简，但求 差别矩阵的时间复杂度为o ( n 2 ( 1 c i + l d l ) ) ，其中n 是样本的个数，l c l 和| d 1 分别为条件 属性和决策属性的个数。当数据量很大时，算法的可行性就面临巨大的挑战，通过差别 矩阵求属性核的时间较大。由于差别矩阵求核方法存在效率低问题，所以许多学者在差 别矩阵的基础上对求核属性进行了研究，得到了许多改进的算法。 h u t 驯在a s k o w r o n 理论的基础上提出改进的差别矩阵求核方法，该方法有效地减 少了计算量，提高了求核属性的效率，但其时间复杂度仍较高为o ( i c i i o l ) 。后来h u 1 分析了基于正区域的属性约简概念的不足后，提出了一个基于数据库系统的属性约简概 念，并用数据库的一些操作设计了一个基于数据库的属性约简的求核属性算法，但该算 法的复杂度受u b ( b c ud ) 操作的复杂度影响很大。 李茹、张丽芳、褚诚缘| 3 “在结合粗糙集理论和层次聚类方法的基础上，运用模糊概 念层方法对原始数据进行模糊化处理，排除边缘数据的干扰作用的同时减少噪声数据的 干扰作用，以进一步简化差别矩阵得出核属性集。但是时间和空间的复杂度还是不理想。 徐章艳、杨炳儒、宋威2 1 在深入研究基于h u 的基础上，给出了一个基于h u 的差 别矩阵的简化差别矩阵和相应核的定义，并证明了该核与差别矩阵的核是等价的。并在 此基础上设计了一个新的求核算法，其时间复杂度为m a ) 【 d ( i c i i 叫c 1 2 ，o o c l l u i ) 。 以上基于差别矩阵的改进求核算法从提高效率程度上都不是很理想。程序演化是现 在广泛采用的优化算法、显著提高算法效率的新方法。因此程序演化为优化差别矩阵求 核算法，提高算法效率提供了新的思路与方向。 1 3 本文主要工作 综上所述，分析研究以上r s 差别矩阵的改进求核算法，本人认为存在如下几个问 题： ( 1 ) 现有许多基于差别矩阵的改进求核算法的效率，普遍存在时间复杂度较高的问 题。因此提高算法效率是关键。 ( 2 ) 在国外，程序演化的理论作为提高算法效率新的方向，应用比较普遍，但在国 内程序演化理论的研究和应用不多，只有少数人对此进行深入研究。 ( 3 ) 目前将程序演化思想应用到优化粗糙集的差别矩阵求核算法上的研究还没有。 针对差别矩阵求核算法所面临的一些问题，考虑到时间的局限性，本文探索应用程 序演化方法来优化差别矩阵求核算法，为提高差别矩阵求核算法效率提供了新的方向。 本文主要工作内容包括以下几个方面： ( 1 ) 分析程序演化的特点、应用前景及发展趋势；分析差别矩阵求核算法的思路及 特点：分析这种算法低效的原因，为提高算法效率提供思路。 ( 2 ) 为解决差别矩阵求核算法普遍存在时间复杂度高的问题，应用程序演化的方法， 4 首先用函数式语言h a s k e l l 实现基于差别矩阵求核算法的规范描述。先不考虑算法的效 率，但保证其正确性，为以后的算法优化提供基础。 ( 3 ) 为了提高算法的效率，应用程序演化的t u p l i n g 和a c c u m u l a t i o n 演化策略对规 范描述的求核算法进行演化，降低算法的复杂度。 ( 4 ) 为进一步提高算法的效率，将数据集划分方法应用到提高算法效率上，再使用 a c c u m u l a t i o n 演化策略，演化后的新算法比原差别矩阵求核算法效率高，仿真试验证明 本文算法的正确性和高效性。 1 4 论文的组织结构 本文结构及内容安排如下： 第一章绪论。概述研究粗糙集的目的和意义以及程序演化、粗糙集求核算法的国 内外研究状况。 第二章粗糙集求核与程序演化。介绍r s 求核的基本知识和相关概念。简单讲述基 于差别矩阵的求核算法，为后续章节规范化描述的算法提供理论基础。同时阐述了程序 演化的相关概念，介绍了函数式语言h a s k e u 的特点及基础知识。 第三章差别矩阵求核算法规范描述的实现。用新的数据结构存储数据，然后用 h a s k e l l 语言实现规范描述差别矩阵求核算法，同时对算法中的重要基本函数，如构建矩 阵函数，扫描矩阵函数，比较样本函数等函数的作用进行举例说明。 第四章基于程序演化的r s 高效求核算法的研究。通过应用程序演化中的t u p l i n g 和a c c u m u l a t i o n 演化策略对规范描述的求核算法进行演化，以达到提高算法效率的目 的。应用数据划分方法减少生成差别矩阵的时间，然后应用a c c u m u l a t i o n 演化策略进一 步提高算法的效率。利用u c i 中的标准算例为测试对象，对演化后的求核算法在y i c h o 系统进行仿真实验，证明算法的正确性和有效性。 第五章总论与展望。总结概括本文的研究工作，提出进一步研究的方向。 5 第二章粗糙集求核与程序演化 2 1 粗糙集理论的基本概念 2 1 1 知识与分类 知识是人类改造客观世界的实践中所获得的认识和经验的总和，具有抽象性、普遍 性和规律性。粗糙集理论的观点是“知识就是一种对对象进行分类的能力 。这里的“对 象”是指例如实物、状态、抽象概念、过程和时间等任何事物。知识直接与真实或抽象 世界的特定语境不同分类模式联系在一起，这种特定语境称为论域，其通常是一个非空 有限的集合。通过知识对任何客观事物不同属性或特征的描述来对其进行分类。 定义2 1 ( 知识和概念) n 司设u 是对象组成的非空有限集合，称为论域。论域u 的 任何一个子集x u ，称为论域u 的一个概念或范畴。为了规范化，认为空集也是一个 概念，称为空概念。 在粗糙集理论中，主要讨论的是那些能够在论域u 上形成划分或覆盖的知识。划分 与等价关系可以视为等同，所以通常用等价关系或关系表示分类及知识。 定义2 2 ( 知识库) n 引给定一个论域u 和u 上的一簇等价关系s ，称为二元组 k = 缈，s ) 是关于论域【厂的一个知识库或近似空间。 定义2 3 ( 不可分辨关系) n 钉给定一个论域u 和u 上的一簇等价关系s ，若p 互s ， 且p ，则np ( p 中所有等价关系的交集) 仍然是论域u 上的一个等价关系，称为p 上的不可分辨关系，记为i n d ( p ) ，简记为p 。且比u ， z 】肋( p ) = 叫p = n x 】足，这 样u i i n d ( p ) = x 肋( p ) i 坛u ) 表示与等价关系i n d ( p ) 关系的知识，称为知识库 k = ( u ，s ) 中关于论域【厂的p 基本知识。为了简便，用p 代替i n d ( p ) ，用u p 代替 u i i n d ( p ) 。下举例说明： 表2 1 医疗诊断决策表“5 1 条件属性决策属性 病例编号 头疼( r )肌肉疼( r )体温( 玛)流感( 冠) 而 是是正常否 6 续表2 1 屯 是是 高是 毛 是是很高是 毛 否是正常否 黾 否否高否 否是 很高 是 根据表2 1 ，知识库为k = ( u ， 焉，r 2 ，墨，兄) ) ，其中论域为案例u = “，x 2 ，) 。 四个属性定义了四个等价关系：头疼、肌肉痛、体温、流感。可以用集合表示论域的不 同划分。 u 头疼母= ，x 2 ，屯) ， 以，屯，) ) ： u 肌肉疼恐= ，屯，屯，五，) ， 屯) ) ； u 体温r = “，) ，如，墨) ，“，气 ) ： u 流感心= “五，x 4 ，黾) ， 屯，毛，) ) 。 可以利用不可分辨关系来获取知识的概念，关于( 头疼墨，肌肉疼恐) 、( 头疼墨， 体温咫) 、( 肌肉疼r ，体温咫) 的划分为： u 头疼尺。，肌肉疼足) = “，x 2 ，而) ， ，毛) ， 而) ) ； u ( 头疼r 。，体龇) = “) ， 工：) ，如) ， ) ， 黾) ， ) ) ； u 月a n 疼尺：，体龇) = “，而) ，k ) ， 屯，魄) ， 鼍) ) 。 2 1 2 粗糙集理论的基本定义 定义2 4 ( 集合的上近似和下近似) n 5 1 给定知识库k = ( u ，s ) ，其中u 为论域，s 表 示论域u 上的等价关系簇，则 互u 和论域u 上的一个等价关系r i n d ( k ) ，定义子 集x 关于知识r 的上近似和下近似分别为： g ( x ) = 卅( 坛u ) 人( x 】rn x ) ) = u r l v r u i r ) ( y nx 矽) ( 2 1 ) 星( x ) = 卅( 觇u ) a ( 工】置x ) ) = u r i v r u 尺) ( y 量x ) ( 2 2 ) 上近似r ( x ) 表示那些根据知识尺判断肯定属于或可能属于工的论域u 中元素的集合； 下近似r ( x ) 表示那些根据知识r 判断肯定属于x 的论域u 中元素的集合。集合 7 b n 足= 页( 彳) 一星( x ) 称为x 的r 边界，即表示那些根据知识尺即不能判断肯定属于x 又 不能判断肯定不属于x 的论域u 中元素组成的集合：集合p o s 足= 叁( x ) 称为x 的尺正 域；集合刀昭矗= u 一天( x ) ，称为x 的尺负域，即表示那些根据知识尺判断肯定不属于x 的论域u 中元素的集合。对于粗糙集而言，它的下近似基( ) 描述了包含x 中的最大可 定义集，上近似描述了包含x 的最小可定义集。这些集合可用图2 1 表示： 论域u ：表示整个区 论域的商集u 瓜：表示图中给所有方格组成的集 域包含的元素 合，即论域在等价关系r 下的分类模式 j ( ， 一 一，。1， ， 一，一， f0；， 。， ， ，、， 一 一 、， ，。 翟 ， _ ，j， 7；霜- ，、，i ， ， ，一 ，一 ，一- ，一 。， - ，、，、，f ， ， | x ， ，： ：亡， ，一 ，一?， 。， ，i 或 ， 一- ，一 一 ， ，r j， ，- 、 】 ， ，：，：， ，-，： ，一i _ 。一 ， 、 1 ， ，、7 y ) 7 ， ；e ， ， ， ，? l ，! 。 ，j j ， 7 ， j ，1 ，p l 。 ， ， 叮 ，一 ， 。l ， - ，i x ， 。， 、 - ，- ， ， ， ， 。 ，j 界 7 7 r7 7 ， = = ： 一，- ，7 一， ” 7 一i7 7r 7 1x ， -_- ，一 ， ，一 - ， ， ll 一 一- ) ，p，_ ， ，：，划五- j 誓，上一l 一 f 等价关系r ：表不划分整个 区域的横竖线 图2 1 集合x 的上近似、下近似、边界域的示意图“司 根据表2 1 ，若对于等价关系尺= ( 头疼，肌肉疼) ，论域的一个子集合x = k ，毛，屯) ， 则根据定义2 4 ，x 的r 一下近似、上近似、正域、边界域和负域分别为： 肭r 一下近似墨( x ) = 玩) ： 确r 一上近似 r ( x ) = “，而，屯，黾) ； x 的r - 正域p o s 月( x ) = r ( x ) = 玩) ； 肭尺一边界域 6 ( x ) = 尺( x ) 一星( x ) = “，屯，毛) ； 姗勺尺一负域 n e g 凡( x ) = u r ( 彳) = x 4 ，) 。 8 2 2 知识的相对核及求核算法 知识约简是粗糙集理论的核心内容之一。一般来说，知识库中的知识( 如属性) 并 不是同等重要的，甚至其中某些知识是不必要的，或者说是冗余的。所谓的知识约简是 指在保持知识库分类能力不变的条件下，删除不必要的知识。直观上讲，知识的核是最 能体现知识特征的部分。核属性具有唯一性，并且核属性是所有约简的交集。在知识约 简时核属性不能被删除，否则将减弱知识的分类能力。故核属性是属性约简计算的基础。 2 2 1 知识相对约简的相关概念与定义 处于计算的考虑，利用列联表来表示知识，视为用来表示划分的特殊的形式化语 言。知识表达系统被看出为一个关系数据表，关系表的行对应要研究的对象( 或状态、 过程等) ，关系表的列对应对象的属性，对象信息通过制定对象的各个属性值来表达。 一般地，一个知识表达系统可以表示为： 定义2 5 ( 知识表达系统) n 5 。称四元组k r s = ( u ，a ，v ，f ) 是一个知识表达系统，其 中，u 是对象的非空有限集合，也称为论域；a 为属性的非空有限集合；v = u k 是 属性值的集合，v 口表示属性口a 的属性值范围，即属性，的值域，f ：u aj v 是一 个信息函数。 定义2 6 ( 决策表d t ) n 引称四元组d t = ( u ，c u d ，矿，f ) 是一个决策表，其中u 、y 、 厂与知识系统的定义一样；c 和d 分别为条件属性集和决策属性集。实际上，表2 1 为 一个含有决策属性的知识表达系统，其中“头疼、“肌肉痛”和“体温”为条件属性， “流感”为决策属性。 在许多实际应用中，一个分类相对与另一个分类的关系非常重要，例如表2 1 中依 照属性“体温 的分类对依照属性“流感 的分类提供了最多的有用信息。下面介绍知 识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念。 知识q 相对于知识p 的正域为p o s p ( q ) = u e ( x ) ，记为p o s p ( q ) 。它是论域u 中 所有根据分类u p 的信息可以准确地划分到关系q 的等价类中去的对象的集合。 定义2 7 n 5 1 给定一个知识库k = ( u ，s ) 和知识库中的两个等价关系簇p ，q s ， v r p ，若p 肋( p ) ( n d ( q ) ) = p o s m 烈p 一 露1 ) ( z 物( q ) ) 成立，则称知识r 为p 中q 不必要 的，否则称r 为p 中q 必要的。 9 常用p o s 尸( q ) 代替p ，d ( p ) ( i n d ( q ) ，如果对于每一个尺p ，r 都为p 中q 必要的， 则称p 为q 独立的，否则尸是q 依赖的或q 不独立的。 定义2 8 ( 知识的相对约简) n 5 给定个知识库k = ( u ，s ) 和知识库中的两个等价关 系簇p ，qgs ，对于任意的ggp ，若g 满足：( 1 ) g 是q 独立的；( 2 ) p o s g ( q ) = p o s | p ( q ) 。则称g 是尸的一个q 约简，记为g r e d o ( p ) ，其中r e d q ( p ) 表 示p 的全体q 约简组成的集合。 定义2 9 ( 知识的相对核) n 5 3 给定一个知识库k = ( u ，s ) 和知识库中的两个等价关系 簇p ，q s ，对任意的r p ，若p 傩肋( p ) ( n 厂d ( q ) ) p 彻( p 一 置 ) ( z d ( q ) ) 成立，则称r 为p 中q 必要的，p 中所有q 必要的知识组成的集合称为尸的q 核，记为c o r e o ( p ) 定理2 1 n 5 1c o r e q ( p ) = i r e d q ( p ) 相对核及其相对约简与知识的核与约简的性质相似。举表2 1 例子说明，考虑决策 属性“流感”，求出条件属性相对于决策属性的核及其约简。 首先同样是分别求出条件属性、决策属性的等价类。然后根据定义2 9 算的条件属 性相对于决策属性的相对核，如下： p o s ( 头疼，( 流感) = p o s ( 肌肉疼，( 流感) = 也) p o s t 体温，( 流感) = “，屯，x 4 ，x 6 ) p d & 头疼，肌肉疼，体温 ) ( 流感) = 而，x 2 ，毛，x 4 ，x 5 ，x 6 ， p o s t 头疼，肌肉疼 ) ( 流感) = p o s q 头疼觑肉疼，体温卜 体温) ) ( 移蓖感) = 墨) p o s ( 头疼，体温j ) ( 流感) = p o s ( 头疼肌肉疼体温卜 肌肉疼) ) ( 流感) 五，x 2 ，毛，x 4 ，x 5 ，) p o s l 【 肌肉疼体温”( 流感) = p o s 头疼，肌肉疼，体温卜 头疼) ) ( 流感) 五，恐，x 3 ，x 4 ，b ，) 因为p o s ( 头疼 肌肉疼，体温j ( 流感) = p o s 肌肉疼。体温 ( 流感) = p 琊 头疼，体温 ( 流感) ，同时根据定义2 9 ， p o s ( 头疼疼 一 头疼) ) ( 流感) = p 啦 肌肉疼) ) ( 流感) p o s ( f 头疼肌肉疼”( 流感) ，说明 头疼) 在 头疼， 体温) 中为必要的，同理可得， 体温) 在 头疼，体温) 中为必要的，所以 头疼，体温) 为独立的，又根据定义2 8 ，故得到 头疼，体温) 是约简，同理可得 肌肉疼，体温) 也 是约简。所以c o r e = 肌肉疼，体温) n 头疼，体温) = 体温) 。 2 2 2 差别矩阵求核算法 知识表达系统的属性约简算法是表达系统中信息智能化处理的核心内容之一。由以 上定义可知，知识表达系统中的属性并不是同等重要，甚至某些属性是冗余的。如何在 保持知识库分类能力不变的条件下，删除其中不必要、不重要或不相关的属性，就是约 简算法所要解决的问题。而求出核属性是约简算法的关键。下面介绍基于粗糙集理论的 l o 经典求核属性算法。 1 9 9 1 年，斯科龙( s k o w r o n ) 教授提出差别矩阵n 5 1 。这种方法对于知识表达系统中 核( 或相对核) 、约简( 或相对约简) 以及其他概念的表示和计算具有很多优点。h u 根 据差别矩阵得出确定属性核的方法。其定义如下： 定义2 1 0 ( 差别矩阵求核) n 5 1 在决策表系统d t = ( u ，c u d ，v ，f ) 中，r = c u d 属 性集合，子集c = 娩l i = 1 ，m ) 和d = d ) 分别称为条件属性集和决策属性集， u = “，x 2 ，讫) 是论域，a i ，) 是样本x ，在属性口j 上的取值。c d ( f ，) 表示差别矩阵中 第i 行第j 列的元素，则差别矩阵c d 定义为： 蚴斗旧苫他“净吼好絮糍， 眨3 ， i矿，d 【而j 2 d t 工，j 其中i j - l ，2 ，n 。 显然，差别矩阵是一个依主对角线对称的矩阵。规定当d ( 而) = d ( x j ) 时，c d ( i ，j ) = 。 当c d ( i ，) = 吼k c ) 为单个属性，a ol c o ( i ，州= 1 时，去掉它一定会改变知识表达系统 的分类能力，即属性a i 为绝对必要的，否则为不必要的。因此所有必要的属性组成集合 即为知识表达系统的核，在差别矩阵表示法中转化为所有简单属性元素组成的集合。 利用差别矩阵能够容易计算出知识表达系统的核，但在生成差别矩阵的时候所用的 时间是o ( n 2 ) ，同时在差别矩阵中查找核属性最好的时间复杂度和最差的时间复杂度分 别为o ( n 2 ) 和o ( n 2 lc | ) ，运行时间较长。因为在这一过程中有很多不必要的矩阵项( 项 中属性个数多于1 的项中的属性不是核属性，因而是不必要的) 在生成差别矩阵时消耗 时间，在查找核属性时也消耗时间。 在现实中，样本的数量是庞大的，这样的时间复杂度是我们不能接受的，故如何降 低算法的时间复杂度，减少求核属性时间是本文所要研究的主要问题。本文所讨论的信 息系统是相容的。 现以表2 1 决策系统举例说明差别矩阵是如何求出核属性。根据差别矩阵的定义， 其中条件属性c = 头疼( 墨) ，肌肉疼( 恐) ，体温( 墨) ) ，决策属性d = 流感( 蜀) ) ， 论域u = “，x 2 ，) 。样本_ 在条件属性c = q ( 而) i 是，是，正常) ，在决策属性上的 取值d ( 五) = 否) 。其余五个样本的条件属性值与决策属性值的采集与第一个样本的做法 相同。 当算法开始时，取第一个样本而进行比较。根据差别矩阵定义，样本与本身相比 c d ( f ，f ) = 矽，因此差别矩阵第一行第一项为空。接着样本x 。与剩下五个样本比较，因样 本毛与而的决策属性值不同，故对比它们的条件属性值。由于它们只有在条件属性马上 的取值不同，故在差别矩阵c d ( 1 ，2 ) = 恐。差别矩阵其余项也由此方法而得。 故差别矩阵表示为： c o = 矽咫马 矽墨b 矽矽蜀b墨r妒 矽墨恐墨恐r矽 矽 恐 r 马 矽 扫描矩阵后，因l c o ( 1 ，2 ) l = l c o ( 1 ，3 ) 1 = 1 c o ( 4 ，6 ) 1 - - 1 ，又由于c o ( 1 ，2 ) = c o ( 1 ，3 ) = c d ( 4 ，6 ) = r 3 ，故核属性集为取， 。 2 3 程序演化