（计算机软件与理论专业论文）增量式属性约简更新算法研究.pdf

摘要 粗糙集理论由波兰科学家z p a w l a k 于1 9 8 2 年提出的一种处理模糊和不确定 知识的数学工具。粗糙集理论建立在论域中的不可分辨关系之上，用上、下近似 来描述概念，不依赖于所需处理的数据集合之外的任何先验信息，就能对不精确、 不确定、不完整的数据信息进行有效的处理。近年来，粗糙集理论在不少领域如 数据挖掘、人工智能、模式识别、决策分析取得了很多成功的应用。 属性约简是粗糙集理论的核心问题之一，化简冗余属性，可以大大提高数据 处理的效率。因此研究更为有效、时间复杂性更低的约简算法成为粗糙集理论研 究的重点。而很多属性约简都是从核开始的，求核成了属性约简求解的关键步骤， 因而探索有效的求核方法具有重要的实用价值。 已有的大多数属性约简算法主要考虑信息系统或决策表不变的情况，有关属 性约简的增量式更新算法报道不多。然而现实世界数据是动态产生的，信息系统 或决策表中的对象在不断变化，已得到的属性约简可能不再有效，这就需要对属 性约简进行动态修改。核求解算法也有同样的问题。 本文的主要工作如下： 1 分析发现杨明教授给出的改进的差别矩阵中存在不必要的计算，为此提 出了改进的差别矩阵定义及求核方法；在此基础上提出一种基于改进差别矩阵的 核增量式更新算法，主要考虑对象动态增加情况下核的更新问题。 2 在一种基于差别矩阵的属性核快速更新算法f u a c ( af a s tu p d a t i n g a l g o r i t h mf o rc o m p u t i n ga l la t t r i b u t e sc o r eb a s e do nd i s c e r n i b i l i t ym a t r i x ) 的基础上提 出了一种改进算法，主要考虑对象动态删除情况下核的更新问题。 3 分析已有的属性约简增量式更新算法，发现它具有较高的时间和空间复 杂度；在1 的基础上提出了一种近线性时间、空间复杂度的高效属性约简增量式 更新算法。 关键词：粗糙集；属性约简；核 a b s t r a c t r o u g hs e tt h e o r yi sam a t h e m a t i c st o o lf o rp r o c e s s i n gv a g u ea n di m p r e c i s i o n k n o w l e d g e ，w h i c hi sp r o p o s e db yp o l a n ds c i e n t i s tz p a w l a ki n19 8 2 r o u g hs e t t h e o r yi sb a s e do nt h ei n d i s c e m i b i l i t yr e l a t i o nt h a td e s c r i b e si n d i s t i n g u i s h a b l eo b j e c t s a n dc a l lb ea p p r o a c h e db yt w oa c c u r a t es e t s ，t h el o w e ra n du p p e r a p p r o x i m a t i o n n o t n e e d i n go t h e ri n f o r m a t i o nt h i st h e o r yc a na n a l y z ea n dp r o c e s st h ei m p r e c i s e ， u n c e r t a i na n di n c o m p l e t ed a t ap r o b l e m s i nr e c e n ty e a r s ，r o u g hs e t st h e o r yh a sb e e n s u c c e s s f u l l yi m p l e m e n t e di nd a t am i n i n g ，a r t i f i c i a li n t e l l i g e n c e ，p a t t e r nr e c o g n i t i o n ， d e c i s i o na n a l y s i s ，e t c a t t r i b u t er e d u c t i o ni so n eo fm a i nt o p i c si nr o u g hs e tt h e o r y t h er e d u c t i o no f a t t r i b u t e sc a nh i g h l ye n h a n c et h ee f f i c i e n c yo fd a t ap r o c e s s i n gb yr e m o v i n gr e d u n d a n t c o n d i t i o n a la t t r i b u t e s s ot os t u d ym o r ee f f e c t i v ea l g o r i t h m st og e tt h eb e t t e ra t t r i b u t e r e d u c t i o na n dt od e c r e a s et h et i m ec o m p l e x i t yb e c o m e sa ni m p o r t a n tp o i n ti nr o u g h s e tt h e o r y c o m p u t i n gc o r ei so n eo fi m p o r t a n tp a r t so fa t t r i b u t e sr e d u c t i o nb e c a u s e m a n ya t t r i b u t e sr e d u c t i o na l g o r i t h m sb e g i nc o r e ，s oe x p l o r i n ge f f e c t i v ec o m p u t i n g c o r ea l g o r i t h mh a sa ni m p o r t a n tp r a c t i c a lv a l u e m a n ye x i s t i n ga l g o r i t h m sm a i n l ya i ma tt h ec a s eo fs t a t i o n a r yi n f o r m a t i o n s y s t e mo rd e c i s i o nt a b l e ，v e r yl i t t l ew o r kh a sb e e n d o n ei nu p d a t i n go fa na t t r i b u t e r e d u c t i o n t h eg o ta t t r i b u t er e d u c t i o nc o u l db en ol o n g e rv a l i db e c a u s er e a l - w o r l d d a t aa r eg e n e r a t e dd y n a m i c a l l ya n dt h eo b j e c t st h a ti ni n f o r m a t i o ns y s t e mo rd e c i s i o n t a b l ec h a n g ec o n s t a n t l y ，s or e q u i r e sd y n a m i cm o d i f i c a t i o n sa t t r i b u t er e d u c t i o n t h e a l g o r i t h mo fc o m p u t i n gc o r eh a st h es a m ep r o b l e ma sa t t r i b u t e sr e d u c t i o n t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： 1 a n a l y s i sf o u n dt h a tt h ei m p r o v e dd i s c e r n i b i l i t ym a t r i xp r e s e n t e db yp r o f e s s o r y a n gm i n ge x i s tu n n e c e s s a r yc a l c u l a t i o n t h e r e f o r ea ni m p r o v e dd i s c e r n i b i l i t ym a t r i x d e f i n i t i o nt o g e t h e r 、析t l lam e t h o df o rc o m p u t i n gt h ec o r ei si n t r o d u c e d t h i sp a p e r i n t r o d u c e sa ni n c r e m e n t a lu p d a t i n ga l g o r i t h mo ft h ec o m p u t a t i o no fac o r eb a s e do n i m p r o v e dd i s c e r n i b i l i t ym a t r i xi nt h ec a s eo ft h ep r o b l e mo fc o r eu p d a t i n gw h e n d y n a m i cm c g e eo b j e c t s 2 i m p r o v e df a s tu p d m i n ga l g o r i t h mi sp r o p o s e db a s eaf a s tu p d a t i n ga l g o r i t h m f o rc o m p u t i n ga l la t t r i b u t e sc o r eb a s e do nd i s c e r n i b i l i t ym a t r i x ，w h i c hm a i n l yc o n s i d e r c o r eu p d a t i n gp r o b l e mw h e nd y n a m i cd e l e t eo b j e c t s 3 p r o p o s e dr ne f f e c t i v ei n c r e m e n t a lu p d a t i n ga t t r i b u t er e d u c t i o na l g o r i t h m w h i c hh a sn e a r l yl i n e a rt i m ea n dl i n e a rs p a c ec o m p l e x i t yb a s eo n1a f t e ra n a l y s i s f o u n dt h a tt h ee x i s t i n gi n c r e m e n t a lu p d a t i n ga l g o r i t h mf o ra t t r i b u t er e d u c t i o nh a sh i g h t i m ea n d s p a c ec o m p l e x i t y k e yw o r d s ：r o u g hs e t ；a t t r i b u t er e d u c t i o n ；c o r e 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：权协 1 年f 月、f 日 厦门大学学位论文著作权使用声明 本人同意厦 j 大学根据中华人民共和国学位条铡暂行实蘧办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阕。本人同意厦门大学将学位论文热入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘臻汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 ( v ) 2 。不保密，适用上述授权零 ( 请在以上相应括号内打“ 或填上相应内容尊保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：袈珈融 印7 钳刖f 日 第一章绪论 第一章绪论 1 1 引言 当今，社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得 各个领域的数据和信息急剧增加。数据的丰富带来了强有力的数据分析工具的需 求，大量的数据被描述成“数据丰富，但信息贫乏 。快速增长的海量数据被收 集、存放在大型和大量数据库中，没有强有力的工具，理解它们已经远远超出人 的能力，因此，有人称之为：“数据坟墓 。其结果是，收集在大型数据库中的数 据变成难得再访问的数据档案，这样，重要的决定常常不是基于数据库中信息丰 富的数据，而是基于决策者的直觉。 如何从大量的、杂乱无章的、强干扰的数据中挖掘潜在的、有利用价值的信 息，这给人类的智能信息处理能力提出了前所未有的挑战，人们需要采用自动化 程度更高、效率更高的数据分析工具来处理这些数据，并提供有用的知识。随着 数据挖掘d m ( d a t am i n i n g ) 和知识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的 概念在1 9 8 9 年被提出，随之出现了新一代的技术和工具用于d m 和k d d 领域。 k d d 是指从大量数据中提取有效的、新颖的、潜在有用的、最终可被理解的模 式的非平凡过程，本质上是在大的数据集合中寻找数据间的规则和普遍模式。 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、 机器学习、可视化和信息科学，以及可以使用的其他学科的技术。在d m 和k d d 的诸多方法中，粗糙集理论与方法是复杂系统一种较为有效的方法，因为它与概 率方法、模糊集方法和证据理论方法等其他处理不确定性问题理论的最显著的区 别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以它对数据的 不确定性的描述和处理可以来说是比较客观的。 粗糙集中约简冗余属性的算法较为简单，由粗糙集模型导出的决策规则集给 出了最小的知识表示；不修正不一致性，将生成的不一致规则划分为确定性规则 和可能性规则；由粗糙集方法导出的结果易于理解。当然，由于该理论未能包含 处理不精确或不确定原始数据的机制，所以与其他处理不确定性问题的理论有很 强的互补性。 增量式属性约简更新算法研究 1 2 国内外相关文献综述 1 2 1 粗糙集的研究历史 粗糙集理论是由波兰科学家z p a w l a k 在1 9 8 2 年提出的一种新型的处理模 糊和不确定的数学工具。1 9 9 1 年波兰p a w l a k 教授的第一本关于粗糙集的专著口1 和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其与相关方法比较研究论文集1 的出版，推动了国际上对粗糙集理论与应用的深入研究。 1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集讨论会，这次会议着重讨论 了集合近似定义的基本思想及其应用，其中粗糙集环境下机器学习的基础研究是 这次会议的四个专题之一。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗糙集与知 识发现( r s d 9 3 ) 研讨会。这次会议极大地推动了国际上对粗糙集理论与应用的研 究，其主题是粗糙集、模糊集与知识发现。1 9 9 4 年在美国的s a n s o s e 召开了第 三届国际粗糙集与软计算研讨会，这次会议广泛探讨了粗糙集与模糊逻辑、神经 网络、进化论等融合问题。粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年第 1 1 期a c m 通讯上撰文，概括性地介绍了目前人工智能应用新技术之一的粗糙集 理论的基本概念，及其在知识获取和机器学习、决策分析、知识发现等领域的具 体研究项目和进展。尤其是1 9 9 5 年召开的第4 届模糊理论与技术国际研讨会， 在这次会议上，针对粗糙集与模糊集合的基本观点与相互关系展开了激烈的讨 论，较大地促进了粗糙集的研究。1 9 9 6 年在日本东京召开了第5 届国际粗糙集 研讨会，这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。1 9 9 9 年1 1 月 在日本、2 0 0 0 年1 0 月在加拿大又分别召开了第1 届和第2 届“粗糙集和计算的 当前趋势”学术会议，来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰 和印度等国家的研究人员参加了会议，会议阐述了当前粗糙集、模糊集的研究现 状和发展趋势，指出将着重在软计算、数据库、a i ( a r t i f i c i a li n t e l l i g e n c e ) 和近似 推理等理论和应用方面发展。 国内学者也积极投身于粗糙集理论和应用的研究。自2 0 0 1 年在重庆成功召 开“第一届中国r o u g h 集与软计算学术研讨会( c r s s c 2 0 0 1 ) 以来，我国每年的 c r s s c 系列研讨会在规模和质量上均呈良好的增长趋势，在此领域的研究工作 发展很快。2 0 0 3 年成立了中国人工智能学会粗糙集与软计算专业委员，r o u g h 集的研究队伍也更加壮大，研究成果在深度和广度上有了更大的发展，2 0 0 6 在 2 第一章绪论 浙江金华召开完的“第六届中国r o u g h 集与软计算学术研讨会( c r s s c 2 0 0 6 ) ”进 一步丰富了我国学者在这一领域的研究。 我国对粗糙集理论的研究虽然起步较晚，但也取得了一系列的研究成果。西 安交大的张文修教授对粗糙集理论刚和概念格理论1 都有深入探讨、重庆邮电的 王国胤教授1 、南昌大学的刘清教授盯1 先后出版专著来介绍粗糙集，使得对粗糙 集的研究成为学者们普遍重视和高度关注的热点。山东大学的史开泉教授提出的 s 粗集阴3 和函数s 粗集m 的概念，对经典的p a w l a k 粗糙集的概念进行了扩展，将 对粗糙集的研究从静态过程延拓到动态过程，在国内外引起高度关注，也为将动 态粗糙集理论运用到多属性决策中提供了理论上的依据和支持。 粗糙集理论在信息科学的应用上主要有两大类：一类是无决策的分析，内容 主要包括数据压缩、约简、聚类与机器发现等；另一类是有决策的分析，内容主 要包括决策分析、规则提取等，当然也可用于对原始数据的预处理，如数据压缩 与约简等。作为处理不确定性和不精确性问题的一种数学工具，粗糙集理论近年 日益受到国际学术界的重视。 目前，其理论模型得到不断完善和发展，并渗透到很多学科，成为研究数据 挖掘、知识约简和粒计算的理论基础。r o u g h 集理论自身也已成为完整、独立的 科学领域。此外，r o u g h 集理论与其他一些软计算理论，诸如f u z z y 集、粒计算、 神经网络、遗传算法等均已经成为当前国内计算机及相关专业的研究热点。在许 多关于人工智能、模糊理论、知识发现和信息管理等国际学术会议上经常可以看 到涉及粗糙集的论文。 1 2 2 粗糙集的研究现状 对粗糙集理论的研究主要集中在：粗糙集的算法研究，粗糙集的模型推广， 问题的不确定性的研究，与其他处理不确定性、模糊性问题的数学理论的关系与 互补，纯粹的数学理论方面的研究，和人工智能其他方向关系的研究等。这些研 究有的是应用型的，有的是理论型的。 ( 1 ) 粗糙集模型的拓展 粗糙集理论在应用于数据分析时，会遇到噪声、数据不齐、海量数据等一系 列经典理论解决不够理想的问题，且粗糙集的运算是建立在等价关系的基础之 上，需要满足自反、对称和传递三种性质，但在实际过程中传递性的条件很难得 增鏖式属性约简更新算法研究 到满足，因此研究学者在传统粗糙集模型的基础上进行了扩充。拓展方法主要有 构造性方法和代数性方法n 们： 代数性方法是基予粗糙集代数系统的算子，利用拓扑学的观点研究近似算子 对某些公理的适应程度，研究的范围大多是经典的集合论、公理与二元等价关系 相对应，后来y y y a o 在总结p a w l a k 粗糙集代数系统理论的基础上将其拓展到 一般意义下的粗糙集系统，建立了粗糙集代数空间与拓扑空间的映射关系，完善 了近似算子的代数结构，其理论性较强，但实际应用还不多见。 构造性方法的研究较为普遍，主要以论域的二元关系和布尔代数为要素，导 出粗糙集代数系统，其拓展方向主要包括论域方向拓展、关系推广及近似空间的 延拓。 ( 2 ) 不确定性问题的理论研究雏蟠 粗糙集理论中知识的不确定性主要由两个原因产生的：一个原因是直接来自 于论域上的二元关系及其产生的知识模块，即近似空间本身，如果二元等价关系 产生的划分越粗，每一个知识模块越大，知识库中的知识越粗糙，相对于近似空 间的概念和知识就越不确定，这时知识的不确定性的方法往往用香农信息熵来刻 画。知识的粗糙性与信息熵的关系比较密切，知识的粗糙性实质上是其所含信息 多少的更深层次的刻域。 ( 3 ) 与其他处理不确定性方法的理论研究 粗糙集与概率统计、粗糙集与证据理论、粮糙集与模糊集、糯糙集与神经网 络、粗糙集和粒计算。 ( 算法研究 约简算法 约简包括属性约简和值约篱。然丽对于一个信息系统来说，找出其所有约简 或最小约简都已证明是n p h a r d 。故一般采用启发式信息找出最优或次优约简。 导出规则的增量式算法 原有的算法是在固定的数据集上进行的。当有新的数据增加到数据集时，若 用原有的算法导出规则是相当麻烦的。增量式算法是对原有规则进行修正，从丽 得出关于新数据集的规则的方法。 粗糙集基本运算的并行算法 粗糙集的基本性质决定，它的很多基本运算可以并行计算。文献n 霹采用基于 格形数组的s i m d 计算机的形式，提出并实现了粗糙集理论中诸如可定义性、不 4 第一章绪论 可区分性、及上、下近似这些基本运算的并行计算结构。 ( 5 ) 属性值的离散化 粗糙集只能处理离散化的属性，而现实中存在的数据一般具有连续型的属 性，因此，连续属性的离散化是制约粗糙集理论实用化的难点之一。这个问题一 直是人工智能界关注的焦点。连续属性离散化的根本出发点，是在尽量减少决策 表信息损失的前提下( 保持决策表不同类对象的可分辨关系) ，得到简化和浓缩 的决策表，以便用粗糙集理论分析，获得决策所需要的知识。 虽然目前在有关粗糙集理论及其相关的研究中取得了一些令人瞩目的成果， 但是仍然存在一些至今还没有很好解决的问题n 3 1 。 1 2 3 粗糙集理论的应用成果 粗糙集( r o u g hs e t s ) 理论的生命力在于它具有较强的实用性，从诞生到现在 虽然只有三十多年的时间，但已经在许多领域取得了令人鼓舞的成果。有很多有 趣实用的案例被做过报告，现在让我们来按行业回顾其中的一些代表性的应用： ( 1 ) 医学应用( m e d i c i n e ) ： 在医疗诊断方面，用粗糙集方法根据以往病例数据来归纳出诊断规则，用来指 导新的病例，如肺炎诊断n 制。 在医学护理方面，用基于粗糙集开发出来的l e r s 软件可以更好的构建专家 知识获取系统，指导护理n 射。 在医学图像方面，用基于粗糙集的神经网络方法对生理组织图像进行比较结 合，帮助我们更好的进行分类n 引。 ( 2 ) 金融商业应用( f i n a n c e a n db u s i n e s s ) ： 股票数据分析，g o l a n 和z i a r k o 应用粗糙集理论分析了l o 年股票的历史数据， 研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街证券 交易专家的认可n 7 1 。 银行风险评估，r s l o w i n s k i 和c z o p u n i d i s 应用粗糙集方法对多家银行进行 破产风险预测评估，建立了相应的粗糙集模型，获得了较好的应用效果n 8 1 。 商业数据分析，z p i a s t a 于19 9 8 年使用粗糙集方法对市场金融数据库进行分 析，提出了用粗糙分类的思想对金融数据进行数据挖掘和知识发现，效果很好n 引。 ( 3 ) 2 1 2 程应用( e n g i n e e r i n g ) ： 工业控制，粗糙集根据观测数据获得控制策略的方法称为从范例中学习，属于 5 增量式属性约简更新算法研究 智能控制的范畴。基本步骤是：把控制过程中的一些有代表性的状态以及操作入 员在这些状态下所采取的控制策略都记录下来，形成决策表，然后对其分析化简， 总结出控制规则嘲。 信号和图像处理，在这一领域粗糙集有极其广泛的应用，例如对数字语音信 号的嗜杂和无序处理滔，语音编码的过滤溯，图像处理，文本分析强霹等等。 ( 4 ) 信息科学( i n f o r m a t i o ns c i e n c e ) 信息检索，在信息检索过程中，由予文档中存在大量的多义积近义现象，导致 不确定性出现，这将影响检索的性能。为此采用基于互信息的粗糙集理论来处理 这类不确定性麓题踟。 软件工程，粗糙集用于帮助软件工程数据的定性分析，软件质量的评估和软 件的可配置性等溉蚓。 ( 5 ) 决策分析( d e c i s i o na n a l y s i s ) 在决策分析方面，裰糙集理论的决策规则是在分柝以往经验数据的基础上得 到的，它允许决策对象存在一些不太明确，不太完整的属性，弥补了常规方法的 不足。文献【2 7 】论述了基于粮糙集理论的知识表达和粗糙集决策规则的提取过 程，提出一种相应的行车指挥决策评价体系。证明列车运行次序决策属性，能完 全作为列车运行调整的决策条件。 ，2 4 基于粗糙集的相关软件 目前已经产生了许多基于糨糙集方法的知识发现系统，其中最具代表性的有 以下几种： ( 1 ) 基于粗糙集的l e r s ( l e a m i n gf r o me x a m p l e sb a s e do nr o u g hs e t ) 是美 国k a n s a s 大学开发的基于粮糙集的实例学习系统 2 8 1 。该系统作为一魏开发专家 系统的工具，已经被美国国家航空和航天管理局( n a s a ) 的j o h n s o n 空间中心所 采用。另外该系统还已经被用于医学研究、气候预测、环境保护等方面。l e r s 的输入采用特定的文件格式，该格式类似于信息表，但是用附加信息来表明条件 属性、决策属性、属性的优先级等信息。 ( 2 ) r o s e ( r o u g hs e td a t ae x p l o r e r ) 是由波兰p o z n a n 科技大学开发用于决策 分析的溯。它是运行在p c 兼容机w i n d o w sn t 上的交互式软件系统。 ( 3 ) r o u g h - - e n o u g h 是由挪威t r o l l d a t a 公司开发的。该系统根据信息系统计 6 第一章绪论 算得到分辨矩阵。系统提供很多工具进行集合近似，如等价类、决策类、上近似、 下近似、边界区域、粗糙成员值、泛化决策规则等，并且使用遗传算法生成约简 结果。可在网站h t t p ：w w w t r o l l d a t a n o r e n o u g h 下载该软件。 ( 4 ) d a t a l o g i c r 它是加拿大r e d u c t & l o b b e 有限公司现在的代表产品。 d a t a l o g i c r 可以对杂乱无章、不完整和模糊的数据进行知识约简并且把这些知 识表示成简单易懂的规则表，它能这样做的原因是通过结合数据中的逻辑属性和 概率模式来消除多余不相关的数据，从而找到最佳的知识表达方式。从 h t t p ：w w w r e d u c t c o r n 上面我们可以了解到更多的信息。 除了上述代表性的软件以外，还有一些在粗糙集领域很有名的软件：g r o b i a n 软件，它是用c + + 写成的基于粗糙集理论的数据分析软件；p r i m e r o s e 软件 ( 基于粗糙集的概率规则归纳方法) ；p r o b r o u g h 软件( 从数据中归纳除决策规 则的系统) ；r o u g hf a m i l y ( 基于粗糙集方法和规则挖掘技术基本功能的实现程 序组) 等等。 1 3 本文的主要工作和组织结构 1 3 1 课题的提出和意义 知识约简是粗糙集理论的核心内容之一。所谓知识约简，就是在保持知识库 分类能力不变的条件下，删除其中不相关或不重要的知识。在粗糙集理论中，知 识约简分为：属性约简和属性值约简，即在保持信息系统分类或决策能力不变的 前提下，删除冗余属性和冗余属性值，获得信息系统的分类或决策规则。随着数 据库系统中数据的不断增加，属性约简相对于属性值约简更加有效。它大大简化 了数据库结构的复杂度，提高了人们对隐含在数据库庞大数据量下的各种信息的 认识程度。因此，属性约简也就成为了目前粗糙集的研究热点之一。目前人们已 经做了许多工作，提出了许多算法。 现有的大多数属性约简算法主要考虑静态数据的处理，有关属性约简的增量 式算法不多。并且已有的为数不多的动态增量属性约简算法，它们的时间、空间 复杂度较高。很多属性约简是从求属性核开始的，所以求核也是粗糙集理论的一 个重要问题。求解屙i 生核也面临上述同样的问题。基于以上问题，本文围绕粗糙 集中的求属性核和属性约简问题，介绍了相关粗糙集理论知识，在分析各种求核 7 增量式属性约简更新算法研究 方法和属性约简算法的基础上，改进了已有的增量式求属性核及属性约简算法， 使它们有较低的时间、空间复杂度，进行了相关实验或实例验证。 1 3 2 本文的组织结构 第一章，讲述了粗糙集的由来，文献综述部分详细介绍了粗糙集理论的提出、 发展沿革和目前的研究现状，粗糙集理论在各个领域的应用，前人的研究成果， 最后介绍了本课题研究的主要内容。 第二章介绍了粗糙集理论中的相关概念：知识的定义、不可分辨关系、上下 近似、正域、负域、边界、约简、核、近似精度、知识的依赖性等。同时介绍了 知识表示的概念并给出实例分析。 第三章介绍了常用的求属性核方法，在分析前人提出的求核方法基础上，改 进了其中两种核增量式更新算法。 第四章讨论了代表性的属性约简算法，包括常见的属性约简算法、改进的基 于差别矩阵的属性约简算法、基于差别矩阵的增量式属性约简算法，最后提出了 属性约简增量式完备算法，并给出相应的实例验证。 第五章对本课题提出的研究方法的特点、结论和意义进行了总结和探讨。 8 第二二章粗糙集基础理论 第二章粗糙集基础理论 粗糙集以不可分辨关系为基础，给出知识表达系统这一模型，以分类的观点， 利用精确的上、下近似集逼近不精确对象，赋予知识清晰的数学意义，从而提供 了用数理逻辑方法来表达、约简、分析、推理不精确知识和分辨系统的某些特点、 过程、预测的结果等。本章主要介绍粗糙集的基本理论“棚。 2 1 知识与知识库 2 - 1 1 相关定义 知识理论的各个方面研究得到了逻辑学、信息工程、系统工程和人工智能工 作者的广泛重视。现有许多理解、表述和处理知识的方法。由于当涉及到不同领 域知识具有不同定义，与触相比，粗糙集理论中关于知识的理解可能更接近于 认识科学。 粗糙集理论认为知识是蕴藏在人类的分类能力之中的，知识以关于对象的分 类能力为基础。这里对象是指感兴趣的所有东西，如事物、状态、抽象概念和过 程等，称之为论域u 。因此，粗糙集理论中，知识被理解成关于论域的一组划分。 论域可以按照不同的属性分成不同的类，具有相同特征的知识构成基本集，其元 素具有不可分辨关系，基本集是构成知识的模块，使知识具有粒状结构与层次性。 假设给定一个感兴趣的对象论域阢对于任何子集x c _ u 称为u 中的一个概 念或范畴。知识库可表示为k = 似彤，其中尺为u 上的等价关系集合，则u r 表示r 将u 分成的所有等价类构成的等价类簇。可以根据不同的r 对u 进行不 同形式的分类。知识库也被称作近似空间。 设u 是一个论域，足是u 上的等价关系，u 肛表示u 上由尺导出的所有等 价类。 x 】r 表示包含元素x u 的r 等价类。一个知识库就是一个关系系统k = 厂配 彤，其中u 是论域，p 是u 上的一个等价类簇。如果qc _ p 且缪驴，n n q ( q 的所有等价类的交也是一个等价关系) ，记作i n d ( q ) 。 定义2 1k = 似矽和胙似纠是两个知识库，若1 n d ( p ) = i n d ( q ) ，则称k 和般或q 和力是等价的，记作k 兰坂或者p 兰9 。因此，当k 和m 是同样的 基本范畴集时，知识库k 和m 中的知识都能使我们确切地表达关于论域的完全 9 增量式属性约简更新算法研究 相同的事实。 对于两个知识库k = 似彤和胙以9 ，当1 n d ( p ) c i n d ( q ) 时，称知识库p 比知识库q 更精细，或者说q 比p 更粗糙。当尸比q 更精细时，我们称尸为q 的特化，q 为p 的推广。由以上可知，推广是将某些范畴组合在一起，而特化则 是将范畴分割成更小的单元。 2 1 2 知识表达系统决策表 知识表达系统的基本成分是被研究对象的集合，关于这些对象的知识是通过 指定对象的属性和他们的属性值来描述。因此，可用信息系统来表示知识。 定义2 2 形式上四元组s = 佛么，”j 9 是一个信息系统，其中u 是对象的 非空有限集合，称为论域泸扛j ，x 2 , ：列；彳是属性的非空有限集合，么= 扣j ，a 2 , ， a m ；v = u v o 是属性的值域集，圪是属性口酬的值域；厂是信息函数u 彳_ y a e a 是一个信息函数，它指定u 中每个对象x 的属性值。如果a = cu d ，c f i d = 妇p ， c 表示条件属性集，d 表示决策属性集，则该类信息系统又称为决策系统，决策 系统是一类最为常见的信息系统。 2 2 集合近似和粗糙集的基本概念 2 2 1 不可分辨关系与上、下近似集 近似空间构成论域u 的一个划分：若r 是u 上的一个等价关系，以 x 】r 表 示x 的r 等价类，u r 表示尺的所有等价类构成的集合，即商集；r 的所有等价 类构成u 的一个划分，划分块与等价类相对应。等价关系组成的集合为等价关 系族。 定义2 3 令r 为等价关系族，设尸c r ，且尸c p ，则p 中所有等价关系的 交集称为p 上的不可区分关系，记作1 n d ( p ) ，即有：缸】肋( ，) = n 【x 】只 r e p 不可区分关系是p a w l a k 粗糙集理论中最基本的概念。若似纠i n d ( p ) ，则 称对象x 与y 是不可区分的，即五y 存在于不可区分关系1 n d ( p ) 的同一个等价类 中。依据等价关系族尸形成的分类知识，五y 无法区分。我们称u i n d ( p ) 中的各 等价类称为p 基本集。 1 0 第二章粗糙集基础理论 表2 - 1 实例表( i ) 定义三个等价关系( a l j 属性) ：头疼r j 、肌肉疼r 2 和体温r 3 ，通过这些等价 关系，可以得到下面的三个等价类。 u r 1 2 1 ，2 ，3 ， 4 ，5 ，6 ) ) ， u r 2 2 l ，2 ，3 ，4 ，6 ) ， 5 ) ， u r 3 2 l ，4 ， 2 ，5 ) ， 3 ，6 ) ) 。 由此可以看出，我们可以按不同的等价关系对论域进行分类，得到不同的概 念和抽象。其中，有的概念是有用的，有的是无价值的，知识获取就是要用最小 的知识获得有用的概念，并得到概念之间的关系。 定义2 4 给定一个决策表信息系统s = 化cu d , v , , j 9 ，对于x c _ u 和r c _ c ，x 的下近似集与x 的上近似集分别定义为r = u 埘y e u r 且】，秘和 r 仞= 堋y e u r 且y f i x - ：西 。 在信息系统( 或决策表) 中，若一些数据具有相同的条件属性而具有不同的分 类，则称这类数据是不一致的；否则为一致的。 j 的斤下近似表示所有一定属于x 的对象的集合，x 的r 上近似表示所有可能 属于x 的对象的集合。 j 的月正域：p o s r ( x ) = r ( 2 - 1 ) z 的月负域：n e g r ( x ) = u - r + ( 2 - 2 ) j 的边界区定义为：s n r ( x ) = r + 一r ( 2 3 ) b n i ? 御表示既不能明确判断属于x ，也不能明确判断不属于x 的对象组成的 集合。 增量式属性约简更新算法研究 当r + ( 2 0 - 置时，称集合x 关于且是清晰的删s p ) ；当胄p 毋月时，称 集合j 关于亓是粗糙的，这时也称集合j 为关于芹的粗糙集( r o u g hs e t ) 。这可用 集合对俾p p ，胄。，来近似表示。 用图2 1 表示更加直观： 圈2 1 粗糙集中各集合之间关系的示意图 正域 边界域 负域 22 2 近似精度和粗糙度 集合的不确定性是由于边界域的存在而引起的，集合的边界域越大其精确性 越低，为更准确地表达遮一点，我们引入了精度的概念。对于由等价关系r 定 义的近似精度为： 铲篇 其中，1 表示集合的基数。对有限集合来说，集合基数就是集台中元素的 个数。即可将对等价关系集斤的粗糙程度用斤下近似集合成员个数与亓上近似 集合成员个数的比值来度量。显然0 。1 ，如果t z r - - 1 ，则称集合j 相对于拧是 清晰的，如果d 。 o ，则集合j 关于 口口。 第二章粗糙集基础理论 r 是粗糙集合。 不失一般性，假设仅有一个决策属性d ，其取值范围是1 ，2 ，k ，由d 导 出的等价类构成划分： 卿，贶) ，其中孵= xe ul f c x ，驯= i ，i = 1 ， 2 ，k 。 定义2 5 设p 对划分 即，蚴，觋 的严近似精度为y ，= 轳缈l 2 3 知识约简 给定的一个知识库，是否可以用较少的知识表达同样的概念。也就是说，删 除知识库中的一些知识是否又使它能够与原来的知识库具有相同的表达能力，这 就是知识约简。知识约简是粗糙集理论的核心内容之一，在数据挖掘领域具有重 要的应用意义。 定义2 6 如果属性a c 满足y 卜f b y 。，则称属性a 为不可缺少的，否 则，称属性为冗余的。若在信息系统中a 中的任意属性都是必要的，则称a 是独 立的；否则称a 是依赖的。 定义2 7 给定信息系统s = 似cu d , 形j 9 ，子集bc _ a 称为是彳的约简，若 i n d ( a ) = 1 n d ( b ) 且b 是独立的。记为：r e d ( a ) 。 根据这个定义可知，约简有两个方面的性质：首先，约简所表达的对系统的 划分能力与原来的知识库所形成的划分是完全一致的，即约简所表达的知识和原 来的知识具有相同的表达能力；其次，就是独立性，即最小性，约简是能够表达 原来的知识库的最小集合，约简集合中的属性不可再进行删除。 定义2 8 设p c _ c ，若y ，= y 。，且不存在r c p ，y 。= y 。，则称p 为c 的 一个( 相对于决策属性d 的) 属性约简。所有c 的属性约简的交称为c 的核，记为 c o r e ( c ) 。 约简是属性中最小的子集，这个子集导出的原子集数目与由整个属性集导出 的原子集数目相同，即对论域的划分不变，它可以通过初始信息系统识别出所有 可分辨的对象。核是属性中最重要的部分，是所有约简的公共部分，其中任何一 个元素都不可能在不影响属性分类能力的情况下被删除。核是唯一的，而约简不 1 3 增量式属性约简更新算法研究 唯一。约简与核是粗糙集理论的两个基本概念，也是信息系统知识约简的基础。 2 3 1 代数观约简 一般来说，信息系统分为有决策与无决策两种类型。对于无决策的信息系统 我们简称为信息表，带有决策属性的信息系统称为决策信息系统，简称决策表。 信息表的约简有时也称为绝对约简，它只需保证约简后的属性是独立的。而对于 决策表的约简一般称为相对约简，由于带有决策属性，相对约简较之绝对约简相 对复杂。代数观约简就是一种相对约简。 在决策信息系统s = 似cu d , v , j 9 中，决策属性集d 将论域u 中的对象分类， 产生划分u d ，因此可考虑属性分类相对另一属性分类的关系，即属性的相对约 简和相对核的概念。 定义2 9 令尸和q 是论域u 上的属性集，q 的p 正域记为p o s e ( q ) ，定义为： p o s e ( q ) 2u 只)( 2 - 6 ) x e 【，o 相对正域p o s e ( q ) 是论域u 的所有那些使用分类聊所表达的知识中能够 正确地分类到u q 的等价类之中的对象的集合。可以认为是一个集合类的下近 似的并集。决策信息系统的决策属性d 相对于条件属性c 的相对正域p o s c ( d ) 集合中的元素称为系统正域对象。 尸和q 为论域u 上的属性集，对v 口