（计算机应用技术专业论文）基于泛系方法论的rough集理论研究.pdf

薅一点尊 硕士学位论文 摘要 当今，社会进入了网络信息时代，计算机与网络信息技术的飞速发展使得信 息量急剧增加，并伴随着数据的不确定性更加显著。如何从大量的、杂乱无章的、 强干扰的海量数据中挖掘潜在的有利用价值的信息呢? 人们提出了智能信息处 理，希望计算机能自动从大量的数据中获取其潜在的模型。如何处理不精确、不 确定知识和数据的方法等已成为智能信息处理中的重要研究课题。r o u g h 集 ( r o u g hs e t s ，也称粗集或粗糙集) 理论是一种研究不完整、不确定知识的表达、 学习、归纳的理论方法，是一种新的处理模糊和不确定性知识的数学工具a 近年 来r o u g h 集已成为信息科学中最为活跃的研究领域之一。特别是在医学、商业、 金融、工程设计、气象学及其它一些领域都有重要应用。 本文所做的工作是在泛系方法论的指导下，将r o u g h 集理论与集合论、非 线性问题等分析结合研究，在探索上述理论模型在某些方面存在泛系共性的基础 上，在约简算法和理论两个方面得到改进和扩充。 本文首先给出了r o u g h 集理论的一些基本概念，并对概念进行了简要说明。 介绍了粗糙集的基本原理与方法以及这一理论的研究发展状况。 接着本文从泛系观的角度，分析决策表的化筒。把决策表显化为广义系统， 在此基础上发现决策表的化筒过程其实是一种系统内硬件的变化，是系统的转化 过程，又存在泛对称和泛极端的显化过程。而且这种变化中的关系是一种偏序关 系，又可以构成布尔代数系统。为进一步研究决策表的化筒提供了一种新思路。 然后本文基于粗集等价关系的补，从泛混沌、泛引子和泛怪引子的角度作 釉击摹 硕士学位论文 分析，从研究非线性问题入手，为进一步研究决策表的特性提供了新的思路。 接着讨论了当传递性不能满足时使得等价关系弱化为相容关系的粗糙集模 型，可看作是基于关系的泛化，进一步对属性核的计算进行探讨，使得对于特征 提取过程中难以离散化、归一化的问题能够用粗集方法处理成为可能。 最后用泛系的概念重新表示了r o u g h 集理论的一些基本概念，用泛系形影关 系与泛模拟分析了粗集决策表，并且重新表示了相容决策表属性约简算法。在弓 入了隐模拟之后可以不通过集合之间的包含关系来确定规则的相容性。同时，在 进行属性约简的时候不用计算下近似而确定某属性是否可约简。使属性约简更为 直观、简洁。 本文对粗糙集的研究重点集中在理论层次，同时用泛系观研究了其中的一些 问题，论述了多种理论研究的结合点。通过不同学科的交缘，使得粗集理论结合 其它学科的特性，使其适合于解决某类具体应用问题。如何将粗糙集理论用统一 的泛系理论来解释和深化，并迸一步用其指导粗糙集理论的研究，这项工作很值 得今后去做。 关键词粗糙集理论泛系理论广义系统形影关系模拟非 线性问题核化简 魂_ 击j 硕士学位论文 a b s t r a c t n o w a d a y s ，t h ew o r l dh a sg o ti n t ot h et i m e so fn e t w o r ka n di n f o r m a t i o n t h e r a p i dd e v e l o p m e n to f t h ec o m p u t e ra n dt h ei n f o r m a t i o nt e c h n o l o g yo fn e t w o r kh a s m a d el a r g ed a t ai n e a s es u d d e n l y ，w h i c hb e c a m em o r ee v i d e n tw i t ht h eu n c e r t a i n t y o fd a t a h o wc a nw ef i n do u tt h e p o t e n t i a lu s e f u lp a r ta m o n g t h eg r e a ta m o u n to fd a t a w h i c hi si m m e t h o d i c a la n d n o i s y ? t h e i n t e l l e c t u a li n f o r m a t i o nh a n d l i n gh a sb e e n p u t f o r w a r d ，b yw h i c hp e o p l eh o p et h ec o m p u t e r t og e ti t sp o t e n t i a lm o d e lf r o mag r e a t a m o u n to fi n f o r m a t i o na u t o m a t i c a l l y i th a sb e c o m ea ni m p o r t a n tr e s e a r c hs u b j e c t h o wt oh a n d l ei n a c c u r a t ea n du n c e r t a i nk n o w l e d g ea n dd a t a r o u g hs e t st h e o r yi sa k i n do ft h e o r yt o s t u d yt h er e p r e s e n t a t i o n , l e a r n i n ga n di n d u c t i o no fi n c o m p l e t e ， u n d e t e r m i n e dk n o w l e d g ea n dd a t a i ti sn e wm a t h e m a t i c a lm e a n s ，w h i c hh a n d l e s f u z z ya n du n d e t e r m i n e dk n o w l e d g e u pt on o wr o u g h s e t st h e o r yh a sb e e no n eo ft h e m o s ta c t i v er e s e a r c ha s p e c t si nt h ef i e l do fi n f o r m a t i o ns c i e n c e e s p e c i a l l y , i th a sb e e n a p p l i e dt om e s c a l ，c o m m e r c e ，f i n a n c i a l ，e n g i n e e r i n gp r o j e c t ，a e r o g r a p h ya n da n y o t h e rf i e l d s i nt h i s p a p e rw ec o m b i n er o u g hs e t st h e o r yw i mc l a s s i c a l s e t st h e o r y , s o m e c h a r a c t e r si nn o n l i n e a r a n a l y s i s a n ds oo nw i t ht h e d i r e c t i o no fp a n s y s t e m s m e t h o d o l o g y , o i lt h eb a s i so fs e a r c h i n gf o rt h ep a n s y s t e m sc o m l n o n n e s si ns o m e a s p e c t sa m o n g t h ea b o v e t h e o r ym o d e l s ，w ee x p e n d t h et h e o r ym o d e la n d i m p r o v e t h e a l g o r i t h m f i r s t ，w ep r e s e n tt h e b a s i c c o n c e p t i o n s a b o u tr o u g hs e t sa n d e x p l a i nt h e m u i 蔫一z 荨 硕士学位论文 b r i e f l y w ei n t r o d u c et h er a t i o n a l e ，t h em e t h o da n d t h ed e v e l o p m e n to fr e s e a r c ha b o u t r o u g h s e t s n e x t ，f r o mt h ev i e wo fp a n s y s t e m s ，w ea n a l y z et h ed e c i s i o nt a b l e sr e d u c e - t i o n w el r a n s f o r mt h ed e c i s i o nt a b l e si n t ot h eg e n e r a l i z e ds y s t e m s ，b a s e do ni tt h e p r o c e s so fd e c i s i o nt a b l e sr e d u c t i o ni sac h a n g ei nt h eh a r d w a r eo ft h es y s t e m , i ti s p r o c e s so fs y e t e mt r a n s f o r mt o o , h i d e dp a n s y m m e t r ya n dp a n e x t r e m e t h er e l a t i o n s o ft h es y s t e m st r a n s f o r mi st h er e l a t i o no f p a r t i a lo r d e ra n ds t r u c t u r et h eb o o l e a n a l g e b r ai n t h ed e c i s i o nt a b l e sr e d u c t i o n t h i sc h a p t e rp r e s e n tan e w t h i n k i n gf o r r e s e a r c h i n gt h ed e c i s i o nt a b l e sr e d u c t i o n f u r t h e r a n d t h e n ，b a s e do nu 2 _ r ，f r o mt h ev i e w so f p a n c h a o s ，p a n a t t r a c t o ra n ds t r a n g e p a n a t t r a c t o r , w ea n a l y z e d t h er e l a t i o n sw ew i l lr e s e a r c ht h er e d u c t i o n o f d i c i s i o nt a b l e b a s e do nn o n - l i n e a r r e l a t i o na n a l y s i sf u r t h e r f o l l o w i n g ，i nt h ef i e l do f s e t st h e o r y , w ew e a k e nt h ei n d i s c d m i n a b l er e l a t i o nt o c o n s i s t e n tr e l m i o n ，t h i si sa p a n t r a n s f o r mb a s e do nr e l a t i o n , w ed i s c u s st h ec a l c u l a t i o n o fc o r eo fa t t r i b u t e f u r t h e r l y t h i s m a k e si t p o s s i b l e t od e a lt h e p r o b l e m o f n o n - u n i f o r m l yd i s c r e t ew i t hr o u g h s e t s a tl a s t ，w e e x p r e s s s o m eb a s i c c o n c e p t s o fr o u g hs e t s t h e o r yw i t hp a n - s y s t e m s ，a n dw ed i s c u s st h ed e c i s i o nt a b l e s o fr o u g hs e t sf r o mt h e 们e w so f p a n s y s t e m sb o d y s h a d o wr e l a t i o na n dp a n s t i m u l a t i o n ，w eg i v ean e w a l g o r i t h ma b o u t a t t r i b u t er e d u c t i o n w ec a na s c e r t a i nt h ec o n s i s t e n c yo fr u l e sn o tb yt h ec o n t a i n a b l e r e l a t i o no f s e t s ，a tt h es a n et i m e ，a t t r i b u t er e d u c t i o nd o n tu s el o w e r a p p r o x i m a t es e t s , 1 v 惩一土曹 硕士学位论文 w h i c hm a k e sa t t r i b u t er e d u c t i o nm o r e s t r a i g h t f o r w a r da n dc o n c i s i o n i nt h ep a p e r ，w ep u tt h em a i np o i n t so ft h er e s e a r c ho nt h e o r yl e v e lo fr o u g h s e t s a tt h es a m et i m ew ea l s or e s e a r c hs o m ep r o b l e m sb a s e do nt h ev i e w so f p a n s y s t e m s ，w ed i c u s s t h ec r o s s e so f e a c hr e s e a r c hr e s u l ta n d a p p l i c a t i o n t h r o u g ht h e i n t e r s e c t i o no fd i f f e r e n ts u b j e c t s ，r o u g hs e t st h e o r yh a sa c h i e v e ds o m ec h a r a c t e r so f o t h e rs u b j e c t s , w h i c hm a k e si ta d a p tt os o l v es o m ek i n d so f c o n c r e t e sa p p l i c a t i o n h o w c a nw e e x p l a i nr o u g hs e t st h e o r yi nu n i f o r mp a n s y s t e m st h e o r y , a n df a r t h e rc o n d u c t t h er e s e a r c ho f r o u g hs e t st h e o r y , w h i c hi sw o r t ht od oi nt h ef u t u r e k e y w o r d s ：r o u g h s e t s t h e o r yp a n s y s t e m st h e o r yg e n e r a l i z e ds y s t e m b o d p s h a d o wr e l a t i o np a n s t i m u l a t i o n n o n - l i n e a rr e l a t i o n a n a l y s i s c o r e d e c i s i o nt a b l e sr e d u c t i o n v 硕士学位论文 原创性声明 y 7 3 2 2 1 4 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所 取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等， 均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体 已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 狴盘亟 日期_ 丝翌三： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大 学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向 国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人 授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用任何复制手段保存和 l 编本学位论文。本人离校后发表、使用学位论文或 与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文储躲弛捅导师躲参以日期：z 嘴r a 蔼- t 击尊 硕士学位论文 第一章绪论 1 1 r o u g h 集提出的背景 在经典逻辑中，只有真假之分，但在现实生活中许多含糊现象并不能简单地用 真假来表示，如何表示和处理这些现象就成为一个研究领域。长期以来许多逻辑学 家和哲学家就致力于研究含糊概念t 早在1 9 0 4 年为此逻辑的创始人g f r e g e 就提出 了含糊( v a g u e ) 词，他把它归结到边界线上，也就是说全域上存在一些个体既不 能在其某个子集上分类，也不能再该子集的补集上分类。 1 9 6 5 年，z a d c h 提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这 一理论解决g f r e g e 的含糊概念，但遗憾的是模糊集是不可计算的，即没有给出数 学公式描述这一含糊概念，故无法计算出它的具体的含糊元素数目，如模糊集中的 隶度函数u 和模糊逻辑中的算子九都是如此。时隔2 0 年后的8 0 年代初，波兰的p a w l a k 针对g f r e g e 的边界线区域思想提出了粗糙集( r o u g hs e t s ) 【ij ，他把那些无法确定 的个体都归属于边界线区域，而这些边界线区域被定义为上近似集和下近似集之差 集。由于它有确定的数学公式描述，所以含糊元素的数目是可以计算的，即在真假 二值之间含糊度是可以计算的。r o u g h 集理论主要特点在于它恰好反映了人们用 r o u g h 集方法处理不分明问题的常规性，即以不完全信息或知识些不分明现象的 能力，或依据观察、量度到的某些不精确的结果而分类数据的能力。8 0 年代以来经 过许多计算机科学家和数学家的不懈研究，r o u 吐集已经从理论上日趋完善，特别 是由于8 0 年代末9 0 年代初在知识发现等领域得到了成功的应用而越来越受到国际 上的广泛关注。相对于其他处理不确定性和模糊性的理论工具而言，r o u g h 集理论 有着许多不可替代的优越性。经过近几年的研究和发展，它已经在信息系统分析、 人工智能及应用、决策支持系统、知识与数据发现、模式识别与分类、故障检测等 方面取得了较为成功的应用。 r o u g h 集概念在某种程度上与许多其它为处理含糊和不精确性问题而研制的 数学工具有相似之处，特别是d e m p s t e r s h a r e r 证据理论【21 。两者之间主要区别在于 d e m p s t e r - s h a f e r 理论利用信度函数作为主要工具，而r o u g h 集理论利用集合下近似 集和上近似集。另一种关系存在于模糊集理论和r o u g h 集理论中间。r o u g h 集理 论与模糊集理论多方面对照，不是和模糊集竞争，而是在补充它。总之，r o u g h 集 理论和模糊集理论对于不完全的知识来说它们是各自独立的方法。此外，r o u g h 集 理论与b o o l e a n 推理方法，与决策分析方法也在作相互补充。 r o u g h 集理论的主要优势之一是它不需要任何预备的或有关数据信息，比如统 a 扣蔓尊硕士学位论文 计学中的概率分布，d e m p s t e r - s h a f e r 理论基本橛率赋值，或者模糊集理论中的隶属 度或概率值。 必须指出，r o u g h 集理论也不是万能的，对建模而言，尽管r o u g h 集理论对 知识不完全的处理是有效的，但是，由于这个理论未包含处理不精确或不确定原始 数据的机制，因此，单纯地使用这一理论不一定有效描述不精确或不确定地实际问 题，这意味着，需要其它方法补充。一般地说，由于证据理论与模糊集理论等具有 处理不精确和不确定数据的方法( 尽管在描述上不一定方便) ，因此，将它们与粗糙 集理论构成互补是自然的考虑【3 l 。 1 2 r o u g h 集研究的动态 2 0 世纪7 0 年代初，波兰学者p a w l a kz 和波兰科学院、华沙大学的逻辑家们 组成的研究小组，开始了对r o u g h 集理论的数学性质与逻辑系统的基础研究。同时 也开发了一些应用系统。1 9 9 1 年p a w l a kz 教授的第一本关于r o u g h 集的专著和 1 9 9 2 年r s l o w i n s k i 主要主编的关于r o u g h 集应用及其相关方法比较研究的论文集 的出版，推动了国际上对r o u g h 集理论与应用的深入研究。1 9 9 2 年在波兰召开了 第l 届国际r o u g h 集讨论会。这次会议着重讨论了集合近似定义的基本思想及其应 用，其中r o u g h 集环境下机器学习的基础研究是这次会议的四个专题之一。从此每 年召开一次与r o u g h 集理论为主题的国际研讨会。 近年来r o u g h 集理论已成为信息科学最为活跃的研究领域之一，同时该理论还 在医学、化学、管理科学、商业和金融等领域得到了成功的应用。我国也在国家自 然科学基金，国家8 6 3 计划和一些省市基金的支持下开展了一定的研究工作，逐渐 的得到一些研究成果。国内已经连续召开了两届r o u g h 集会议，以及关于粗糙集、 模糊集以及粒度计算的国际会议。 目前，r o u g h 集理论已发展到较高水平。对于r o u g h 集理论的研究，大致集中 在以下几个方面： ( 1 ) r o u g h 集逻辑从逻辑角度进行不精确推理，决策。 o l 【1 4 l ( 2 ) r o u g h 集代数讨论粗糙集的代数结构和拓扑结构以及收敛性问题。致 力于构造或生成约简空间。【8 】【1 1 】 ( 3 ) r o u g h 集约简包括各种约简算法的研究，求解尽可能小的约简以 并行实现。【2 】【1 3 】 ( 4 ) 知识粒度在不同的层次下解释知识。【4 】 5 】 9 1 2 ：j 鼋一文尊 硕士学位论文 ( 5 ) 与其它处理模糊理论或不确定性理论之间关系的研究将r o u g h 集理 论进行推广。【6 】【7 1 本文着重于对r o u g h 集属性的约简的研究。 1 3 论文组织及创新点 本文所做的工作是在泛系方法论的指导下，将r o u g h 集理论与集合论、非线性 问题等分析结合研究，在探索上述理论模型在某些方面存在泛系共性的基础上，在 算法和理论两个方面得到改进和扩充。 本文第二章介绍了知识表达系统和r o u g h 集的一些基本概念，如：上近似、下 近似、不可分辨关系、正域、负域、边界域、相对正域、信息系统的核、协调决策 规则、不协调决策规则，讨论了决策表的属性约简及r o u g h 集的一些基本性质。 第三章至第六章为本文中心内容，也是创新点。 第三章从泛系观的角度，分析决策表的化简。把决策表显化为广义系统，在此 基础上发现决策表的化简过程其实是一种系统内硬件的变化，诱导出系统的转化过 程，是泛对称和泛极端的显化过程。而且这种变化中的关系是一种偏序关系，又可 以构成布尔代数系统。为进一步研究决策表的化简提供了一种新思路。 第四章基于粗集等价关系的补，从泛混沌、泛引子和泛怪引子的角度作了分析， 从研究非线性问题入手，为进一步研究决策表的特性提供了新的思路。 第五章讨论了当传递性不能满足时使得等价关系弱化为相容关系的粗糙集模 型。可看作是基于关系的泛化，进一步对属性核的计算进行探讨，使得对于特征提 取过程中难以离散化、归一化的问题能够用粗集方法处理成为可能。 第六章用泛系的概念重新表示了r o u g h 集理论的一些基本概念，用泛系形影关 系与泛模拟分析了租集决策表，并且重新表示了相容决策表属性约简算法。传统的 约简算法是通过关系简化族的交运算求得核，而本文提出的算法是通过形影关系和 隐模拟先求得核，再依次加其它属性求决策表的一种属性约简，使属性约简更为直 观、简洁。 第七章是工作总结与未来的工作。本文对粗糙集的研究重点集中在理论层次， 同时用泛系观研究了其中的一些问题。根据现阶段r o u g h 集理论发展的现状，认为 将来还可以将泛系模拟观和相应定理结合讨论属性化简；还有相容核替代等价关系， 这种泛化下的粗集模型的属性约简、关联规则的提取等有关问题。继续讨论粗集理 论中的非线性问题，研究抽象集合上的渐变突变机理和稳定性。 狮虫萼 硕士学位论文 第二章r o u g h 集基础知识 2 1 r o u g h 集基本概念 2 1 1 知识表达系统 粗糙集理论认为知识是一种对对象进行分类的能力。这里的对象是指我们所能 言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具 体或抽象世界的特定部分相关的分类模式联系在一起，这种特定的部分称为所讨论 的全域或论域。现实世界中的知识有很多种组织形式，通常r o u g h 集理论讨论信息 表的表示形式。信息表是一个二维表格，信息表中的列表示属性，行表示对象，并 且每行表示该对象的一条信息。数据可以通过观察测量得到。信息表中有一类特殊 的表，叫决策表【l5 1 。决策表将信息表的属性分成两类：条件属性和决策属性。 定义2 1一个决策表知识表达系统s 可以表示为： s = 这里，u 是论域( 对象的集合) ，a jc u d 是属性集合，c 是条件属性集，d 是 决策属性集，v = u v a 是属性值的集合，v a 表示属性a e a 的属性值范围，即属性a 的值域，f ：u a 斗v 是一个函数，它指定u 中的每一个对象的属性值。 具有条件属性和决策属性的知识表达系统可表达为决策表。记作t = ( u ，a ，c ，d ) 或简称为c d 决策表。 令x i 和y j 分别代表u c 与u d 中的各个等价类，d e s ( x i ) 表示对等价类x i 的描 述，即等价类x 。对于各条件属性值的特定取值：d e s ( y i ) 表示对等价类y i 的描述， 即等价类y i 对于各决策属性值的特定取值。决策规则定义为：r i j ：d e s ( x i ) - - - d e s ( y i ) ， y i nx i o 。 从上述定义可看出：决策表的条件属性c 和决策属性d 对应论域的两个划分。 决策规则反映了这两个划分之间的关系。如果一个条件属性划分的等价类被一个决 策属性划分的等价类包含，那么该决策规则是相容的：反之，如果一个条件属性的 等价类不被任何个决策属性的等价类包含，那么，该决策规则是不相容的。若表 中所有的决策规则都是相容，则该决策表为相容决策表。 表t = ( u ，a ，c ，d ) 中，a e c ，若t ，- ( u ，a ，c - a ) ，d ) 为相容的，我们称t = ( u ，a ，c ，d ) 决策表中属性a 是可省略的，否则a 是不可省略的。当所有a e p 是不可省略的，则 称p c c 是c 的一个简化。从c 得到p 的过程就是条件属性的化简。 4 萄一文蕈 硕士学位论文 决策表知识表达系统中，容易看出一个属性对应一个等价关系，一个表可以看 作定义了一族等价关系，即知识库。下面将给出一般的知识表达系统的定义： 定义2 2 知识表达系统可以形式化的定义为： s = ( u ，a ) 其中u 是一个非空、有限论域，a 是非空的属性有限集合。 对于属性a a 有a ：u 呻v a ，其中v a 表示属性a r 的属性值范围，即属性a 的值域。 每个子集b c a 称为一个属性，当b 是单元素集时，b 称为原始的，否则b 被 称为复合的。属性b 可以看作是用等价关系( 在该属性上的取值相同) 表示的知识 的一个名称，可以称为标识属性。 对于每一个x e u ，对于每一个a cc u d ，我们定义一个函数 d x ：a 哼v ，d x ( a ) = a ( x ) 函数d 。成为c d 决策表中的决策规则，对于c 的约束记作d x i c ，对于d 的约束 记作d d d ，d x l c 和d x l d 分别称为d x 的条件和决策。如果对于每一个y x ，a 。l c = d y l c 意味着d x l d = d ，i d ，则称决策规则d x 是相容的，否则称为不相容的。只有当所有决策 规则都是相容的时，决策表才是相容的，否则，决策表是不相容的。 2 1 2 r o u g h 集的基本概念酣 对于每个属性子集b c ，x e u ，令函数i n f b ( x ) = ( a ，a ( x ) ) l a e b a ( x ) v 1 。 定义2 3 对x ，y e u ，当i n f b ( x ) = i n f b ( y ) 时，称x ，y 是在b 下不可分辨 的，即x 和y 在b 属性集下的属性值都相同，因此在b 下无法分辨x 和y 。定义不 可分辨关系i n d ( b ) 如下： 、 i n d ( b ) = ( x ，y ) ii n f 。( x ) = i n f b ( y ) ) 显然i n d ( b ) 是一个等价关系，且 i n d ( b 户n i m d ( b ) ) ，其中b e b 不可分辨关系是对象由属性集合表达时所表现在论域中的等价关系。它预示出 知识的颗粒状结构。而知识的粒度正是造成已有知识无法精确地表示概念的原因。 当决策表所包含的数据足够多的时候，通过属性所对应的等价关系就可以反映出论 域的过程性知识( 概念之间的逻辑关系) ，即等价类之间的关系。从决策表的描述性 j i 9 - r 土荸 硕士学位论文 知识中发现有用的过程性知识( 规则知识) 是知识发现的重要内容。 设u 是非空论域，c 是非空条件属性集，x _ u ，b c ， x 。为包含x 的b 等价类。 定义2 4x 关于r 的下近似集定义为： r - ( x ) = x e u | x _ c x x 关于r 的下近似集是u i n d ( r ) 商系统中所有被x 包含的元素的并集。 x 关于r 的下近似集表示了在现有的知识系统( 商系统) 中用现有的知识( 等 价类) 去表示x ，所能得到的可以确定地归入集合x 的对象的集合。也可以说是在 现有的知识系统下面可以用现有知识准确表示的属于x 的部分。 定义2 5x 关于r 的上近似集定义为： r 一( x ) = x e t ji x n x a x 关于r 的上近似集是u i n d ( r ) 商系统中所有跟x 有交榘的元素的并集。 x 关于r 的上近似集表示了所有的在现有知识系统( 商系统) 中用现有的知识 ( 等价类) 去表示x ，所有跟x 有关系的知识的并集。就是整个论域中在现有的知 识下和x 有关系的所有元素的集合。 定义2 6x 的边界域： b n 。( x ) = r - ( x ) 一耻( x ) x 的边界域是u i n d ( r ) 商系统中所有跟x 有交集但是不被x 所包含的元素的 并集。 x 的边界域表示了在现有的知识系统( 商系统) 中用现有的知识( 等价类) 去 表示x ，对于知识r 所能得到的不能准确的知道是否属于x 的那部分元素。也可以 说是在现有的知识系统下面用现有知识不能准确分辨是否属于x 的那一部分元素。 有时候也把x 关于b 的下近似集称为x 的b 芷域，记作p o s 。 x ) 。把n e g 。( x ) = u r 一( x ) 称为x 的b 负域，表示在现有的知识系统( 商系统) 中用现有的知识( 等价 类) 可以精确表示的不属于x 的元素的并集。 根据上近似集、下近似集的定义，不难得到如下命题： 命题2 1( 1 ) 当且仅当r _ ( x ) e = r - ( x ) e ，称集合x 是r 可定义集； ( 2 ) 当且仅当r - ( x ) s r - ( x ) n ，称对于r 集合x 是粗集； 6 黉一矗薯 硕士学位论文 命题2 2( 1 ) r - ( x ) x r - ( x ) ； ( 2 ) r ( g ) = r 一( a ) = a ，r 一( u ) = r 一( u ) = u ； ( 3 ) r 一( x u y ) = r 一( x ) u r 一( y ) ； ( 4 ) r 一( x n y ) = r 一( x ) n r 一( y ) ； ( 5 ) x c y ：辛i l ( x ) g r 一( y ) ； ( 6 ) x y ：r - ( x ) r 一( y ) ： ( 7 ) ( r 一( x ) u r ( y ”c _ r 一( x u v ) ； ( 8 ) r - ( x n y ) 耋( r 一( x ) n r 一( y ) ) ； ( 9 ) r 一( 一x ) = 一r 一( x ) ； ( 1 0 ) r 一( 一x ) ：一r - ( x ) ( 1 1 ) r ( r - ( x ) ) = r - ( r - ( x ) ) = r - ( x ) ； ( 1 2 ) r 一( r 一( x ) ) = r 一( r 一( x ) ) = r - ( x ) ； 2 1 3 近似与成员关系 与集合近似概念相关的新概念一一成员关系。 当且仅当x r _ ( x ) 称为x 的r 下成员关系；当且仅当x er 一( x ) 称为x 的r 上成员关系；这里x r 一( x ) 表示对于r ，x 确切地属于x ；x e r 弋x ) 表示对于r ， x 可能属于x 。成员关系将r o u g h 集区别于传统集合论。传统集合论认为：集合完 全由元素决定，对于给定元素要么属于某个集合，要么不属于某个集合。而在r o u g h 集中存在不确定性，不确定性与成员关系有关。成员关系并不是该元素的绝对特性， 依赖于我们的知识，即一个对象是否属于一个集合依赖于我们对它的了解程度。 2 2 决策表的约简 决策表的化简包括两部分，一部分是算法的约简，在整个决策表中去掉所有可 省略的条件属性，另一部分是决策规则的约简，对每一个决策规则进行冗余属性值 简化。这两部分的顺序没有特别的要求，先进行哪部分都可以。 2 2 1 算法的约简 决策表算法的简化过程就是从决策表信息系统的条件属性中去掉不必要的 7 蕊一击善 硕士学位论文 条件属性( 对决策没有帮助) 的条件属性，从而得到表示更简单、对决策更有效的 决策规则。决策表属性约简的算法有很多，如基于可辨别矩阵和逻辑运算的属性约 简算法，归纳属性约简算法，基于信息的属性约简算法，基于特征选择的属性约简 算法，等等。 下面介绍完备系统一般的属性约简算法。 设原始决策表的条件属性集合为c = ( a ii = l ，r l ，决策属性集合为d ， d c d 。对于决策表中的每一个条件属性a ，进行如下过程，直至条件属性不再发生 变化为止。 ， t 如果删除条件属性a 。使得相容的决策表仍然相容，则说明条件属性a ，相 对于决策属性c l 是冗余的，从决策表中删除条件属性a ，所在的列，并将 重复的行进行合并； 如果删除条件属性a ，使得相容的决策表变得不相容说明条件属性a 是 相对于决策属性d 必要的，不能删除。 2 2 2 决策规则的约简 决策规则的化简是利用决策逻辑分别消去决策表中的每一个决策规则的不必要 条件，它不是整体上的化简属性，而是在针对每一个决策规则，去掉表达该规则的 冗余属性值，以便进一步简化决策表。 可以利用如下算法来进行简化： ( 对于规则集合中的每条规则一 f 对于该规则中的任意条件属性 如果去掉该条件属性，该规则不和规则集合中的其他规则冲突， 则可以从该规则中去掉该条件属性。) 经过这样的两次约简处理得到化简后的的决策表，继而得到最后的决策规则简 化形式。 8 越一击尊 硕士学位论文 3 1 引言 第三章粗集与系统观 广义系统、转化和泛对称是泛系范畴的概念基砖之一。本章利用泛系理论分 析了决策表及其化简，反映出决策表的一些系统关系。进步发现决策表的化简过 程其实是一种系统内硬件的变化，这种变化中的关系是种偏序关系，并且可以构 成格和布尔代数系统。 3 2 相关的知识介绍 3 2 i 泛系关系 3 2 1 1 广义系统转化 广义系统的数学形式表示为广义硬件a 与广义软件b 的形式结合弘( a ，b ) 。 广义硬件a 为任何给定的事物集，也包括为其它已定义的广义系统，而广义软件b 则为a 上的某砦关系或关系的泛权复合。】 广义系统可表示为s = ( a ，b ) ，b c p ( a + 个w ) ，这里a 名ua t i 。， i 矗为某给定 的集族，w 为泛权集。 由两个系统硬件之间的关系( 变化) 诱导出系统软件的关系( 变化) ，称为系统的 转化。 3 2 1 2 泛导 f 是a 到b 的关系，f c a x b ，泛导f ( 0 ) = f - 1 r o o f ，它将a 上的关系变到b 上 的关系。 3 2 i 3 泛对称泛极端 泛系对称观把对称理解为多变与少变的联系与转化，并泛化为泛对称的概念， 使之在形式上更为灵活多样，可表现为事物变中有所不变，不变中又有所变的规律 性范畴。 系统在某种条件决定的泛序关系下的最大、最小值称为系统的泛极端。 从泛系观来看下述问题，这个过程就是“广义系统”、“转化”和“泛对称”的 显化。 9 蔼_ 文尊硕士学位论文 3 2 2 格与布尔代数妇订 定义3 2 2 1如果集合a 上的二元关系r 是自反的，反对称的和传递的，那 么称r 为a 上的偏序，记为 。 定义3 2 2 2设 是一偏序集合，b 是a 的子集。 ( a ) 元素b e b 是b 的最大元素，如果对每一元素x e b ，x 如 ( b ) 元素b e b 是b 的最小元素，如果对每一元素x b ，b x 定义3 2 2 3设 是一偏序集合，b 是a 的子集。 ( a )如果对于每一b b ，b a ，那么元素a e a 叫做b 的上界；如果对于每 一b b ，a b ，那么元素a e a 叫做b 的下界。 ( b ) 如果a 是上界并且对每- _ b 的上界a 有醚a ，那么元素a e a 叫 做b 的最小上界，记作1 ；如果a 是一下界并且对每一b 的下界a 有 a - a ，那么元素a e a 叫做b 的最大下界 记作o 。 定义3 2 2 4设 是一偏序集合，如果l 中每一对元素a 、b ，都有最大 下界和最小上界，则称此 为格。 通常用a * b 表示( a ，b ) 的最大下界，用a o b 表示( a ，b ) 的最小上界，即 a * b = d l b a ，b ) a ( g b = l u b a ，b 并称它们为a 。b 的保交和保联。 定义3 。2 ，2 5如果一个格b ，既是有补格，又是分配格，则称此格为布尔格。 3 3 从系统观看粗集中的几个问题 3 3 1 决策表中的广义系统 在决策表分析中，张原始的决策表隐含四个系统：条件等价类系统、决策等 价类系统和两个逻辑系统。条件等价类系统：s i = ，其中硬件a l 是条件 等价类的集合；软件u 、一是条件等价类上的并和补的运算。决策等价类系统：s 2 = ，其中硬件a 2 是决策等价类的集合；软件u 、一是决策等价类上的并和补的运 算。由于条件等价类系统中等价类之间的交是空集，所以这里没有集合的交运算 ( n ) ；决策等价类系统亦然。逻辑系统：s 3 = 和s 4 = 其中硬件 1 0 蔫一文尊 硕士学位论文 a 3 = d e s ( x ) l x e a l ) ，a 4 ； d e s ( x ) j x a 2 ) 是等价类的描述或称作它们的名字，事实 上，一个名字是一个命题，如颜色是红，形状是方等：软件v ，是命题连接词。 3 3 2 决策表中广义系统的转化 由s l 和s 2 构成的关系是条件等价类和决策等价类之间的关系是包含关系：由 s 3 和s 4 构成的关系是条件名称和决策名称之间的关系，其结果是决策规则。 这四