（管理科学与工程专业论文）基于S粗集理论上的属性约简与算法研究.pdf

l i ：东师范人学硕十学位论文 基于s 一粗集理论上的属性约简与算法研究 摘要 粗糙集理论是1 9 8 2 年由波兰数学家z p a w l a k 教授提出来的，它是一种处 理不完整、不确定信息的新型数学工具。由于粗糙集理论是利用数据集上的等 价关系对知识的不确定程度进行度量，而无需提供所需处理的数据集合之外的 任何先验信息，这样就避免了对知识的主观评价所带来的误差。目前，该理论 在数据决策与分析、模式识别、信息科学、管理科学、金融、医学、化学等其 他学科领域已得到了较为成功的应用。 z p a w l a l ( 粗集理论应用到信息系统知识发现中存在着一些局限性：知识 发现是在封闭的信息系统中进行的，它所处理对象的属性集是已知的( 静态的) ， 且从信息系统中得到的结论仅适用于这些对象。而在现实诸多领域的应用中， 所遇到的大多都是动态的属性集，即开放系统，针对具有动态特征的信息系统， 史开泉教授提出了s ； r 集( s i n g u l a rr o u 曲s e t s ) ，它为解决动态系统识别、动 态系统决策、动态系统推理等问题提供理论依据。 属性约简是粗糙集理论研究的核心问题之一，通过属性约简，删除决策表 中不必要的属性，在不丢失决策表基本信息的前提下，简化知识的表示，这正 是人们所期望的。现有的知识发现方法，大都是“静态 的发现，即从已有数 据中挖掘出潜在的规则，由规则做出相关判断，但事实上，人们在认识某一客 观事物的过程中，一方面由于人们的认识能力及所运用工具的局限性，或者出 于某种考虑，对所认识的结果要求不高，从而导致认识的结果总是局部的、片 面的；另一方面由于客观对象本身在不断发展，有些对形式规则没有影响的属 性被约简，但并不能说明它们就不重要。因此，在经过一段时期后，当有新的 数据加入时，最初得到的关于对象的认识可能无法j 下确地描述对象的特征。如 果运用一般的知识发现方法，对全部数据重新进行知识发现，不仅耗时耗力， 降低知识发现的效率，而且有时是不可行的。对此本文从s k o w r o n 提出的分辨 矩阵的角度出发，给出了s 粗集中的分辨矩阵，并在此基础上提出了基于s 一粗 集理论上的属性约简算法，找出有效约简。 本文主要做了以下工作： ( 1 ) 介绍了粗糙集理论的基本知识，以及粗糙集理论中的核心概念，为以 后的属性约简算法的提出奠定了基础。 ( 2 ) 探讨了s 一粗集理论的基本知识，定义了单向属性迁移和双向属性迁移 集合，研究了单向动态信息系统和双向动态信息系统的模型。 l i j 东师范人学硕i 学位论文 ( 3 ) 基于s k o 、啪n 的分辨矩阵，设计了s 一粗集中的分辨矩阵模型，和单向 属性迁移上的动态信息系统的分辨矩阵模型以及双向属性迁移上的动态信息系 统的分辨矩阵模型。 ( 4 ) 研究s 粗集中的分辨矩阵模型，研究了该模型的一些性质，并利用这 些性质给出了s 粗集理论上的属性约简算法，根据该算法可以得到决策信息系 统的核属性和全部约简集。 ( 5 ) 应用s 粗集理论的属性约简算法到化学药品的合成及医疗诊治中，证 明了该算法的有效性。 本文的创新点如下： ( 1 ) 设计了s 粗集中的分辨矩阵模型，和单向属性迁移上的动态信息系统 的分辨矩阵模型以及双向属性迁移上的动态信息系统的分辨矩阵模型。 ( 2 ) 提出s 粗集理论上的属性约简算法，根据该算法可以得到决策信息系 统的核属性和全部约简集。 利用s 粗集理论进行决策分析还有许多问题值得探讨，相关工作还有待进 一步研究。 关键词：粗糙集；s 粗集；属性幻简；分辨矩阵；属性迁移 分类号：t p l 8 山东师范大学硕l ：学位论史 t h er e s e a r c ho f a t t r i b u t er e d u c t i o nw i t ha l g o r i t h mb a s e do n s r o u g hs e tt h e o r y a b s t r a c t r o u g l ls e tt h e o wi sam a t h e m a t i ct o o lt od e a lw i m 如z z va n du n c e n i a nk n o w l e d g e ， 州c hi sp u tf o n a r db yp l a i l dm a t h e m a t i c i a nz p a w l a ki nl9 8 2 nm a l ( e su s eo ft h e e q u i v a l e n c er e l a t i o n st om e a s u r et h ei n d e t e r n l i n a t i o nd e f 丁e eo fl ( 1 l o w l e d g ea n di t d o e s n tn e e d 觚yk n o w l e d g eb e s i d et h ed a t aw h i c hn e e d st ob ep r o c e s s e d t h e r e f o r e t h ee 盯0 fc a u s e db ys u b j e c t i v e 印p r a i s a lc a l lb ea v 0 i d e d a tp r e s e n t ，t h e r o u g l ls e t t h e o 巧h a v eb e e nm u c hs u c c e s s m l 印p l i c a t i o n si nd a t a a n a l y s i s ，p a t t e n lr e c o 朗i t i o n ， i n r 加a t i o ns c i e n c e m a n a g 锄e n ts c i e n c e f i n a n c e m e d i c i n e c h 锄i s t r ye c t a p p l i c a t i o no fz p a w l a k sr o l u 曲s e t t h e o r yt ok n o w l e d g ed i s c o v e r y i n i n f o m a t i o ns y s t e ma r es o m el i m i t a t i o n s ：k n o w l e d 聆 d i s c o v e r yi sac l o s e d i n f o 肌a t i o ns y s t 锄，a n di td e a l sw i t ht h eo b j e c tw h i c hp r o p e n ya r ek n o w n ( s t a t i c ) ， a n dt h ec o n c l u s i o nd 嘶v e d6 o mi n f o 肌a t i o ns y s t e n lo n l yu s e dt ot h eo b i e c t w h i l e i nm a n yr e a la p p l i c a t i o n s ，i to r e ne n c o u n t e r e dw i t hd y n a m i cs e t ，t h a ti so p e n s y s t e m s ，f o rd y n 锄i ci n f o 舯a t i o ns y s t 锄s ，p r o f e s s o rs h ik a i q u a np r o p o s e ds - r o u 曲 s e t s ( s i n g u l a rr o u 曲s e t s ) ，i tp r o v i d e sm et h e o 拶b a s i s 南rs o l v i n gd ”a m i cs y s t e m i d e n t i f i c a t i o n ，d y n a m i cs v s t 锄d e c i s i o n ，d v n a m i cs y s t e mi n f b r e n c ea n ds oo n a t t r i b u t er e d u c t i o no fr o u 曲s e tt h e o r yi so n eo fm ec o r ei s s u e s ，t h r o u 小t h e a t t 抽u t er e d u c t i o n ，硼i n e c e s s a 巧p r o p 耐ya r ed e l e t e d 敞胍d e c i s i o n - m a k i n gt a b l e ， u n d e rm ep r 锄i s eo fw i t h o u tl o s so fb a s i ci n f o m a t i o n t h e s ea r ei u s tp e o p l e s e x p e c t a t i o n k n o w l e d g ed i s c o v e r ym e t h o d sa r em o s t l y ”s t a t i c ”，m a ti sm i n i n gd a t a 丘o mp o t e n t i a ln l l e sw h i c hm a d eb yt h er e l e v a n tj u d g e i nf a c t ，t h e r e 印p e a r st 、) l ，0 i s s u e si nt h ep r o c e s so fr e c o g n i z i n gac e r t a i no b i e c t 。0 no n eh a n d ，i ta l w a y sl e a dt o p e o p l e sr e c o 印i z a t i o np a r t i a la n do n e s i d e df o rt h el i m i t a t i o n so fp e o p l e sa b i l i t yt o r e c o g n i z ea 1 1 dt h eu s e dt o o l sa n dm ed 锄a n do fm er e c o 印i z a t i o n sr e s u l ti sn o th i 曲 f o rs o m ec o n s i d e r a t i o n ：o nt h eo t h e rh a n d ，t h o u g l ls o m ea t t r i b u t ew h i c hh a v en o t i m p a c to nt h er u l em a yb er e d u c e db e c a u s eo ft h eu n c e a s i n gd e v e l o p m e n to fm e o b j e c ti t s e l et h ea t t r i b u t ed o n tm e a nu n i m p o r t a n t t h e r e f o r e ，a r e rs o m et i m e ，i fa n e wd a t aa d d e d ，t h ei n i t i a lr e s u l to nt h eo b i e c tm a yn o tb ea b l et ob er e c o g n i z e dm e c h a r a c t 甜s t i c sc o l l r e c t l y b yt h eg e l l e r a lk n o w l e d g ed i s c o v e 哆m e t h o d s ，i ti sn o to n l y d i s s i p a t ee 矗o r t sa n dr e d u c et h ee 行i c i e n c y b u ta l s on o tf e a s i b l ef o ra l ld a t a k n o w l e d g et ob er e f o 明d b yt h ev i e wo fs k o w r o n sd i s t i n g u i s hm a t 打xi nt h i sp a p e r ， ad i s t i n g u i s hm a 倒xo fs r o u 曲s e ti sp r o p o s e d ，a n daa t t n b u t er e d u c t i o na l g o r i t h m f o rf i n d i n ge f 话c t i v er e d u c t i o ni sg i v e n 1 1 1t h i sp a p e r ，t h ef o l l o w i n gw o r kh a sb e e nd o n e ： ( 1 ) t h eb a s i ck n o w l e d g eo ft h ef o u 曲s e tt h e o 巧a n ds o m e r ec o n c 印t sa r e i n n o d u c e di nt h ef i r s ts e c t i o n t h a th a sl a i dt h ef 0 u n d a t i o nf o rl a t e ra t t r i b u t e r e d u c t i o na l g o 打t l l l n 山东师范人学硕 学位论文 ( 2 ) t h eb a s i ck n o w l e d g eo fs r o u 幽s e tt l l e o r yi sd i s c u s s e d o n ed i r e c t i o n a t t r i b u t et r a n s f hs e ta n dt w od i r e c t i o n 砌b u t e 仃甜l s f 醯s e ta r ed e 6 n e d o n e d i r e c t i o n i y n a m i ci n f o m a t i o ns y s t e l nm o d e la 1 1 dt w od i r e c t i o ne i y n 锄i ci n f o r m a t i o n s y s t e i nm o d e l 孤es t u d i e d ( 3 ) b y 血ev i e wo fs k o 、啪n ，ad i s t i n 鲥s hm 删xm o d e lo fs - r o u g l ls e ti s 西v e i l d i s t i n g u i s hb e t 、v e e nm 删xm o d e lo no n ed i r e c t i o nm i 露a t i o na n dt w od i r e c t i o n m i g r a t i o n f o r t h e d y n a m i c s o fp r o p e r t yi n f o 姗a t i o ns y s t 锄sa r e d e s i g n e d r e s p e c t i v e l y ( 4 ) d i s t i n g u i s hm a t r i xm o d e lo ns - r o u 曲s e ta n di t sn a n j r ea r es t l l d i e d a t t d b u t e r e d u ( ：t i o nw i ma 1 9 0 r i t b a s e do ns r o u g hs e tm e o r yi sp r o p o s e db yu s i n gm e s e n a t u r e ，d e c i s i o ni n f o h n a t i o ns y s t 锄sc o r ea t t r i b u t ea n da l lt h ea 饱怕u t er e d u c t i o n s e tc a nb eo b t a i n e db yt h ea l g o r i n l m ( 5 ) b a s e do ns - r o u 曲s e tm e o q ，a t t 抽u t er e d u c t i o na l g o 订t h mi sa p p l i e dt om e s y n t h e s i so fc h e m i c a l sa n dm e d i c a lt r e a t n l e n tw h i c hp r o v et h ee f f e c t i v e n e s so ft h e a l g o r i m m t h i sa r t i c l ei i l l l o v a t i o ni sa sf o l l o w s ： ( 1 ) d i s t i n g u i s hm a t xm o d e lo fs r o u 曲s e ti s 百v e n ，d i s t i n g u i s hb e t w e e nm a t r i x m o d e lo no n ed i r e c t i o nm i 掣a t i o na n dt w od i r e c t i o nm i 掣a t i o nf o rt h ed m l a i n i c so f p r o p e n yi n f o 肌a t i o ns y s t e m si sd e s i g n e dr e s p e c t i v e l y ( 2 ) a t t r i b u t er e d u c t i o nw i t ha l g o r i t h mb a s e do ns - r o u g hs e tm e o r yi sp r o p o s e d ， d e c i s i o ni n f o 彻a t i o ns y s t e m sc o r ea t t r i b u t ea n da l “h ea t t b u t er e d u c t i o ns e tc a nb e o b t a i n e db yt h ea l g o n t h m m 觚yo t h e rp r o b l 锄si nt h ed e c i s i o na n a l y s i sf o rs - r o u g hs e tt h e o wn e e dt o d i s c u s s 1 1 1 ea c c o r d i n gw o r kw i l lb ed o n ei nt h e 如t u r e k e yw o r d s ：r o u g hs e t ；s r o u 曲s e t ；a t t b u t er e d u c t i o n ；d i s t i n g u i s hm a t r i x ； a t t d b u t et r a n s f e r c l a s s i f i c a t i o n ：t p18 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者繇搽毛 导师签 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位做储躲撇 签字日期：2 。尸年6 月汐日 导师擀s 奉叭 签翱舭吖年月庙 3 山东师范大学硕卜学位论文 1 1 本文研究背景 第1 章引言 当今社会是个信息高速发展的时代，信息量不断增长，对信息分析工具的 要求也越来越高，人们希望自动地从数据中获取其潜在的依赖模型。这样，大 量的数据就无须人的处理，甚至无须人的观察。虽然已经有很多对数据进行分 析的简单统计技术，但高级的智能数据分析技术还远没有成熟。高智能数据分 析的一个支撑点就是首先要对纷繁复杂的数据进行分析，约简和去除一些冗余 信息。 粗糙集理论是一种处理不精确和模糊知识的数学工具【l 】。自1 9 8 2 年来由波 兰华沙理工大z p a w l a k 教授首次提出以来，经过2 0 余年的研究与发展，已经在 理论上和实际应用上取得长足的进展。目前，它在人工智能、模式识别与分类、 故障诊断，特别是在知识与数据发现领域得到了成功的应用【，z 州。r o u 曲s e t 研究 的对象是由一个多值属性集合描述的一个对象集合，对于每个对象及其属性都 有一个值作为其描述符号，对象、属性、描述符是表达决策问题的3 个要素。 这种表达形式也可以看成为一个二维表格，表格的行与对象相对应，列对应于对 象的属性。通常，关于对象的可得到的信息不一定足以划分其成员类别，换句 话说，这种不精确性导致了对象的不可分辩性。给定对象间的一个等价关系， 即由等价类构成的近似空间的不分明关系，r o u g l ls e t 就用不分明对象类形成的 上近似和下近似来描述。这些近似分别对应了确定属于给定类的最大的对象集 合和可能属于给定类的最小的对象集合【5 】。下近似和上近似的差是一个边界集 合，它包含了所有不能确切判定是否属于给定类的对象。这种处理可以定义近 似的精度和质量。r o u 曲s e t 理论可以解决重要的分类问题，去除冗余对象和对 属性进行约简，从而得到决策规则的数量尽可能少【6 】。 r o u 曲s e t 理论的相关知识【7 】更多的是运用到决策表的属性约简算法的研究 当中。决策表中的属性并不是同等重要的，而且某些属性是冗余的。冗余属性的 存在，一方面是对资源的浪费；另一方面，干扰人们做出正确而简洁的决策。 所谓属性约简【j m 】，就是在保持决策表的分类或决策能力不变的条件下，删除其 中不相关或不重要的属性。属性约简的目的是导出决策表的决策规则，约简中 的属性直接影响着决策规则的繁简和性能。在z p a w l a k 粗集理论中通过信息系 统的知识发现存在着局限性：知识发现是在封闭的信息系统中进行的，它所处 理对象的属性集是已知的( 静态的) ，且从信息系统中得到的结论仅适用于这些 对象。而在现实诸多领域的应用中，所遇到的大多都是动态的属性集，即开放 系统，针对具有动态特征的信息系统，史开泉教授提出了s 一粗集u l l 】( s i n g u l a r 山东师范人学硕+ ：学位论文 r o u 曲s e t s ) 。本文从s k o w r o n 提出的分辨矩阵的角度出发，给出了s 一粗集中的 分辨矩阵，并在此基础上提出了基于s 粗集理论上的属性约简算法，找出有效 约简。 1 2s 一粗糙集理论研究现状 粗糙集理论是波兰数学家z p a w l a k 于19 8 2 年首先提出的，该理论刚刚被 提出时并未受到国际智能研究领域的广泛重视，当时的研究也仅限于波兰等几 个东欧国家。到了9 0 年代，数据仓库和数据挖掘逐渐引起了广大学者的重视， 在这种情况下，粗糙集理论被广泛认识并迅速发展起烈1 2 】。 2 0 0 2 年史开泉对z p a w l a k 粗集提出改进【1 3 】，给出动态r 元素等价类【x 】的 概念；提出了s 粗集( s i n g g u l a rr o u 曲s e t s ) ，s 粗集是以具有动态特征的r 一元 素等价类【x 】定义的。s 粗集具有两种基本形式：单向s 粗集( o n ed i r e c t i o n s i n g u l a rr o u 曲s e t s ) ，单向s 粗集对偶( d u a lo f o n ed i r c t i o ns i n g u l a rr o u 幽s e t s ) ，双 向s 粗集( t w od i r e c t i o ns i n g u l a rr o u 曲s e t s ) 。s 粗集为动态数据挖掘。动态知识 发现研究提供了理论支持。在系统中，利用s 粗集进行规律挖掘规律发现研究 也遇到了困难。这是因为：s 粗集( 或r 一元素等价类 x 】) 不具有规律( 函数) 特征。2 0 0 5 年史开泉把函数这一分析工具，引入到s 粗集中并改进s 粗集，给 出具有动念特性的r - 函数等价类 u 】的概念，提出函数s 一粗集( m n c t i o ns i n g u l a r r o u 曲s e t s ) 函数s 粗集是以具有动态特征( 单向动态，双向动态) 的r 函数 等价类 u 】定义的，u ，陋 是一个函数，函数u ，是一个规律。函数s 一粗集具有 两类基本形式：函数单向s 一粗集( m n c t i o no n ed i r e c t i o ns i n g u l a rr o u 曲s e t s ) ，函 数单向s 粗集对偶( d u a lo f 如c t i o no n ed i r e c t i o ns i n g u l a rr o u 曲s e t s ) ，函数双向 s 一粗集( c t i o n 觚od i r e c t i o ns i n g u l a rm o g l ls e t s ) ；函数s 一粗集具有动态特征( 单 向动态，双向动态) 。2 0 0 5 年史开泉把函数这一分析工具，引入到z p a w l a k 粗 集中，给出具有静态特性的r 一函数等价类 u 】的概念，并对z p a w l a k 粗集给出 改进，提出函数粗集( 劬c t i o ns i n g u l a rr o u 曲s e t s ) ，函数粗集是以具有静态特 征的r 函数等价类 u 定义的。从z p a w l a k 粗集与s 粗集的结构，函数s 粗集 的结构，容易得到这样一个事实：z p a w l a k 粗集是s 粗集的特例，s 一粗集是函 数s 粗集的特例；函数s 粗集是s 粗集的一般形式，s 粗集是z p a w l a k 粗集的 一般形式。 2 山东师范大学硕十学位论文 粗糙集的研究在我国虽然起步晚，但发展较快。其研究主要集中于理论方 面，成功开发及应用的实例几乎没有。而关于s 粗集属性约简算法的研究目前 在国内还几乎是一片空白。 1 3 粗糙集理论应用于属性约简 通常来说，大多数的机构建立数据库的目的是为了有效地管理信息资源。 换句话说，在大多数数据库中收集的数据很少是专门用于挖掘知识。所以，知 识库中的知识( 属性) 并不是同等重要的，数据库中总会包含很多冗余属性( 特 征) ，特别是数据如果是随机采集的，则冗余性更普遍，这些属性对于规则的发 现是不必要的。如果这些冗余的属性不被移走的话，不仅规则发现过程的时间 复杂度会增加，而且被发现的规则的质量也会降低。冗余知识的存在，一方面 是对资源的浪费，它需要存储空间；另一方面，干扰人们作出准确而简洁的决 策。所谓属性约简，就是在保持分类和决策能力不变的条件上，删除决策表中 不相关或是不重要的属性。约简反映了一个决策表的本质信息。 、决策表的属性约简是粗糙集理论的核心问题之一【1 4 l 引。粗糙集理论的主要 思想就是在保持分类能力不变的前提下，通过属性约简，导出问题的决策或分 类规则。国内外很多学者对这一问题进行了大量的研究，给出多种不同的属性 约简方法。 1 基本算法。基本算法首先构造差别矩阵。在差别矩阵的基础上得出差别 函数。然后应用吸收律对差别函数进行化简，使之成为析取范式。值得注意的是 这种基于差别矩阵和数学逻辑运算的属性约简所得到的条件属性是保证原信息 系统不损失潜在知识的前提下，进行最佳属性约简的充分但不必要条件。这种 算法适合比较小的数据集。虽然差别函数不是寻找最优化简的最佳方法，但差 别函数有效的提供了核的求解方法。文献 1 6 1 7 给出了基于差别矩阵和逻辑运 算的属性约简方法；文献 1 8 】对基于差别矩阵的约简算法进行了探讨。 2 基于属性重要性的算法。由h u 提出。该算法使用核作为计算约简的出发 点来计算个最好的或者用户指定的最小约简。该算法将属性的重要性作为启 发规则。首先按照属性的重要程度，从大到小逐个加入，直至找到一个最小约简为 止。通过对算法中加入启发性知识，缩小问题求解的搜索空间，因此该种算法 得到了极大地应用和发展。q i a n g 等利用属性依赖度作为启发式信息建立了属 性约简的启发式算法，成功地应用于水处理厂的系统监控中i l9 】；王珏等利用某 属性在决策矩阵中出现的概率作为启发式信息构造启发式算法【2 0 】；w o n g 等 提出利用属性的信息熵作为衡量属性重要性的标准【2 1 1 。文献【2 2 】是苗夺谦等人 提出的基于互信息的属性约简算法；文献 2 3 是王国j 乱等人提出的基于信息熵 山东师范大学硕 ! 学位论文 的属性约简算法。 3 遗传算法。遗传算法实际上是寻优技术，它考虑多输入单输出的全局最 优问题，其基础是以集合的字符串为染色体。字符串中的字符为基因，按生物 进化和遗传规律，利用复制、交换、突变等操作，优胜劣汰，最终找出最优解。 一些学者提出遗传算法非常适合于进行属性约简。l i n 掣a s 和da v i s 研究了粗糙 集和遗传算法的结合，提出了一种粗糙遗传算法。 4 扩展法则和动态约简算法。这两种算法较前面的算法更复杂，然而在大数 据集情况下，采用这两种算法却是非常好的算法。求解一个决策表的全部约简 或计算出最佳约简都是n p h 砌问题【2 4 1 。导致属性约简问题是n p 问题的主要 原因是属性组合爆炸问题，尤其是当数据库规模较大时问题尤为突出。高效的 约简算法是粗糙集应用于数据挖掘的基础，目前还没有一种公认的非常有效的 方法。因此，寻求高效率的属性约简算法始终是一个不容回避的问题。 1 4 本文研究内容与组织结构 本文着重对粗糙集理论研究的核心问题属性约简进行了研究。提出了 基于s 粗集理论上的属性约简算法。本文的研究内容，概况起来主要包括三个 方面的内容： 1 学习粗糙集理论，包括简介粗糙集理论的基本概念，基本理论，产生、 发展和应用。 2 介绍了几种典型的基于粗糙集理论的属性约简算法及应用。 3 本文对粗糙集理论上的属性约简算法及s 粗集理论进行了研究，提出 了基于s 一粗糙集的属性约简算法，并给出了s 粗集理论中的单向动态信息系统 和双向动态信息系统的模型，在s k o w r o n 【2 5 】提出的分辨矩阵的基础上，提出了 s 一粗集理论中的分辨矩阵模型及性质。本文的具体结构如下： 第1 章：引言。 介绍本论文的研究背景，s 粗糙集理论的研究现状及粗糙集理论中的一些 属性约简算法。 第2 章：粗糙集理论的基本知识。 介绍粗糙集理论的基本概念和知识，并对本论文的一些概念和符号进行了 统一和描述。 第3 章：s 粗糙集理论的基本知识。 介绍s 粗糙集理论的基本概念和知识，并对本论文的一些概念和符号进行 了统一和描述。 第4 章：属性约简算法。 4 l l | 东师范人学硕卜学位论文 首先介绍几种典型的属性约简算法及其应用，然后有介绍基于s 粗集理论 上的属性约简算法。 第5 章：基于s 一粗糙集属性约简算法的应用。把s 粗糙集属性约简算法应 用到化学药品的合成和医学诊断方面，并证明了该算法的有效性。 第6 章：总结与展望。 对本论文的主要工作进行了总结，并对未来的工作进行了展望。 5 山东师范人学硕十学位论文 第2 章粗糙集理论的基本知识 粗糙集理论是一种新的处理模糊和不确定知识的数学工具。其主要思想就 是在保持决策表分类能力不变的前提下，从决策表中挖掘出最小决策规则，并 且能够利用这些决策规则的集合进行决策分析和预测。本章将介绍粗糙集理论 的基本知识，作为以后各章的基础。 2 1 知识与分类 一般认为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特性， 是属于认识论范畴的概念。任何知识，都是对其事物运动状态及变化规律的概 括性描述。这对知识的定义不能算是一个完全的、精确的表达，因为知识是具 有多种意义的。 粗糙集理论从认知科学的一些观点柬理解知识，j 下是由于这一点使得粗糙 集理论在数据推理、经济决策等领域有了新的突破，彳稍 到广泛应用。知识是 源于人类及其他物种的分类能力。关于环境的知识，从生存的观点看，就是感 觉信号的复杂分类，它是动物的基本功能对不同情况的分类能力而来的。更为 抽象层次的分类是推理、学习、决策的关键，是一种基础知识【2 引。 定义2 1 【i 】设【，是我们感兴趣的对象组成的非空有限集合，称为论域( 全 域) 。任何子集u ，称为u 中的一个概念或范畴。的一组概念称为u 上 的抽象知识，简称为知识。 本文主要是对在u 上能形成划分的那些知识感兴趣。u 中的对象按照某一 个或几个属性进行分类，从而得到一个划分，在此一个划分，定义为： ，= x l ，x 2 ，兄) ，其中，石u ，石a ，石n 西= a ( f 歹，f = l ，2 ，? ) ， u 石= u 。 f = l 定义2 2 【1 】u 上的一个划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。一 个知识库就是一个关系系统k = ( u ，r ) ，其中u 是非空有限集，r 为u 上等价 关系的一个族集。 叫r 表示尺的所有等价类( 或者u 上的分类) 构成的集合， x 异表示的是 包含元素x u 的r 等价类。 下面举例说明： 6 山东师范大学顾i ：学位论文 玩具积木的集合u = 缸- ，x z ，x ，x ，工s ，z s ，石，船) 。现在假设这些积木有不同的 颜色( 红、黄、蓝) 、形状( 方、圆、三角) 、体积( 大，小) 。因此，这些积木 都可以用颜色、形状、体积这些知识来描述。如果我们根据某一属性描述这些 积木的情况，就可以按颜色、形状、体积分类： 按颜色分类： 红： 工i ，工3 ，x 7 ) ；黄： x 5 ，工6 ，x 8 ) ；蓝： x 2 ，石4 ) ； 按形状分类： 方： 工2 ，z 6 ) ；圆： x l ，肋) ；三角： 船，z 4 ，石7 ，船) ； 按体积分类： 大： z 2 ，工7 ，x 8 ) ； d 、： x l ，x 3 ，工4 ，工5 ，工6 ) 。 换言之，我们定义了三个属性：颜色尺- 、形状r z 、体积j r ，通过这些属 性，就可以得到下面三个分类： u r i = 篱l ，x 3 ，x 7 ) ， x 5 ，舶，x 8 ) ， x 2 ，x 4 ) ) ， 己，尺2 = 石i ，x 5 ) ， x 2 ，x 6 ) ， 工3 ，x 4 ，x 7 ，工8 ) ) ， 乙r 尺3 = 石i ，了3 ，x 4 ，石5 ，z 6 ) ， x 2 ，x 7 ，x 8 ) ) 。 2 2 不可分辨关系和上、下近似集 粗糙集理论拓展了经典的集合论，把用于分类的知识嵌入集合内，作为集 合组成的一部分。一个对象口是否属于集合x ，需要根据现有的知识来判断， 可以分为三种情况f 2 7 】： ( 1 ) 对象口肯定属于集合x ； ( 2 ) 对象口肯定不属于集合x ； ( 3 ) 对象口可能属于也可能不属于集合x 。 集合的划分密切依赖于我们所掌握的关于论域的知识，是相对的而不是绝 对的。二元对k = ( u ，尺) 成为一个近似空间( a p p r o x i m a t i o ns p a c e ) ，设z 为论域u 中的一个对象，x 为u 的一个子集，则【x 】足表示所有与x 不可分辨的对象所组 成的集合，换句话说，是由x 决定的等价类，即【x 】r 中的每个对象都与x 有着 相同的特征属性( a t t r i b u t e ) 。 7 山东师范人学顾 j 学位论文 定义2 3 【1 】若尸r ，且尸9 ，则尸中所有等价关系的交集也是一个等 价关系，称为p 上的不可辨识关系( i n d i s c 锄i b l er e l a t i o n ) ，记为剧d ( p ) ，且有 【x 肋( p ) = n 【k 。 矗e ， 这样，圳扒移( p ) ( 即等价关系胁移( p ) 的所有等价类) 表示与等价关系p 相关的知识，称为k 中关于u 的尸基本知识( p 基本集) 。为简单起见，我们 用叫p 代替u z 彻( p ) ，z d ( p ) 的等价类称为知识p 的基本概念或基本范畴。 特别地，如果q 尺，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等概念或q 初等范畴。 同样，当k = ，尺) 为一个知识库，- d ( k ) 定义为k 中所有等价关系的族。 不可分辨关系是粗糙集理论的核心概念，根据不可分辨关系，论域被划分为一 个类族，而每个类内部的对象都是不可区分的。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 集和下近似( 1 0 w e ra p p r o x i m a t i o n ) 集来描述。 定义2 4 【1 】设集合u ，r d ) ，定义两个子集： 星x = u y 叫尺iy 冬x ) ， 瓦x = u 】，叫尺il 厂n x o ) 分别称它们为x 的r 下近似集和r 上近似集。 集合曰r ( x ) = 融一丛称为x 的r 边界域；加& ( x ) = 丛称为x 的尺正 域；船g ( x ) = u 一融称为x 的尺负域。 显然，融= p d 品( x ) u 剧( x ) 。丛或p d ( x ) 是由那些知识r 判断肯 定属于x 的u 中元素所组成的集合；劢是由那些知识尺判断可能属于x 的u 中元素所组成的集合；蹴( x ) 是由那些知识r 既不能判断可能属于x 又不能 判断肯定属于一x 的【，中元素所组成的集合；砸瓯( ) 是由那些知识r 判断肯 定不属于x 的u 中元素所组成的集合。 下面的性质是显而易见的： 8 山东师范火学硕 学位论文 定理2 1 【1 】 ( 1 ) x 为尺可定义的当且仅当心= 肷； ( 2 ) x 为r 粗糙的当且仅当砑斟； 我们也可以将肘描述为x 中的最大可定义集，将砝描述为含有x 的最 小可定义集。根据集合x 的上近似和下近似的不同情况，可以定义四种不同的 重要的粗糙集【2 8 】： ( 1 ) 如果心o 且砑u ，则称x 为尺粗糙可定义； ( 2 ) 如果心= 囝且劢u ，则称x 为尺内不可定义； ( 3 ) 如果心a 且取= u ，则称x 为尺外不可定义； ( 4 ) 如果胱= a 且融= u ，则称x 为r 全不可定义。 这种划分的直观意义是这样的： 如果集合x 为尺粗糙可定义，则意味着我们可以确定u 中的某些元素属于 x 或一x 。 如果集合x 为尺内不可定义，则意味着我们可以确定u 中的某些元素是否 属于一x ，但不能确定u 中的任一元素是否属于x 。 如果集合x 为r 外不可定义，则意味着我们可以确定u 中的某些元素是否 属于x ，但不能确定u 中的任一元素是否属于一x 。 如果集合x 为r 完全不可定义，则意味着我们不能确定u 中的任一元素是 否属于x 或一x 。 粗糙集理论与传统的集合论有着相似之处，但是它们的出发点完全不同。 传统集合论认为，一个集合完全由其元素决定，一个元素要么属于这个集合， 要么不属于这个集合，即它的隶属函数肚( x ) o ，1 ) 。模糊集合对此做了拓广， 它给成员赋予一个隶属度，即肚( x ) o ，l 】，使得模糊集合能够处理一定的模糊 和不确定数据，但其隶属度往往具有人为的因素在里面，这为它的应用带来一 定的不便【2 9 1 。在粗糙集理论中，隶属关系不再是一个原始概念，因此无需人为 给元素指定一个隶属度，从而避免了主观因素的影响。粗糙集理论认为不确定 与隶属关系有关，而模糊性则表现在集合本身。 集合的不精确主要是由于边界域的存在，集合的边界域越大，那么该集合 就越不精确。粗糙集通过近似精度这一概念来衡量集合的精确程度。 定义2 5 【3 0 1 由等价关系尺确定的集合x 的近似精度为 9 山东师范人学硕 j 学位论文 州耻陶， 其中，x a ，i x i 表示集合x 的势，也就是x 所包含的对象的个数。 精度口足( x ) 用来反映我们对于了解集合x 知识的完全程度。显然，对每一 个r 和x 互u 有o 口足( x ) l 。当口詹( x ) = 1 时，说明x 的尺边界域为空集，集 合x 为r 可定义的；当口r ( x ) ， 口矗( x 4 ) = 2 1 1 。 2 3 知识约简 知识约简中有两个基本概念：约简( 陀如甜) 和核( c d 旭) 。 定义2 6 【1 1 令尸为一族等价关系，尺p ，如果删d ( p 一体) ) = 刷d ( 尸) ，则 称关系r 在p 中是不必要的；否则称关系r 在p 中是必要的。 不必要的关系在知识库中是多余的，如果