（模式识别与智能系统专业论文）函数s粗集与系统规律识别研究.pdf

山东大学硕士学位论文 摘要 1 9 8 2 年，波兰数学家z p a w l a k 教授提出粗集理论( r o u g hs e t st h e o r y ) ，粗集 就是用上，下近似两个集合来定义一个不可定义的集合工石是一个静态的集 合2 0 0 2 年史开泉教授将z p a w l a k 粗集进行推广，提出奇异粗集( s i n g u l a rr o u g h s e t s ) ，简称s - 粗集，它包括两种形式：单向s 粗集，双向s 粗集s 粗集将z p a w l a k 粗集的固定边界线变为浮动边界线，因此在s 粗集中，对象集合x 是动态的 z p a w l a k 粗集是s 粗集的特例，s 租集是z p a w l a k 粗集的一般形式在s 粗集的 基础上，史开泉教授将元素等价类推广为函数等价类，提出以函数等价类定义的 函数s 粗集本文将s 粗集理论与生物遗传理论、信息传递理论相嫁接，研究 s 粗集的特性和应用将函数s 粗集与灰色系统理论相结合，建立规律挖掘模型 本文理论和应用相结合，在研究s 粗集，函数s 一粗集的性质的基础上，给出了典型 应用本文具体的成果如下：在介绍粗集的基本理论和应用之后，进入本文的主体 部分，引入s 粗集，单向s 一粗集，双向s 粗集的定义和结构，提出了s 粗集的遗传 特性和遗传定理，将s 粗集与信息传递理论相结合，提出基于s 一粗集遗传特性的 单向s - 信息传递模型和双向s 信息传递模型；引入函数s 粗集，函数单向s 一粗集， 函数双向s 粗集以及函数单向s 一粗集对偶的概念和结构，讨论了函数s 粗集与s 粗集的关系，提出函数s 粗集的遗传特性和遗传定理，将函数s 粗集的遗传特性与 灰色系统理论相结合，建立规律生成和规律挖掘模型，用于发现和挖掘系统隐藏 的规律，并给出实际应用例子s 粗集，函数s 一粗集是粗集理论，租系统的理论研究 与应用研究的新的研究方向 关键词s 粗集，遗传，函数s 一粗集，信息传递，规律挖掘 山东大学硕士学位论文 a b s t r a c t r o u g hs e t st h e o r yi sp u tf o r w a r db yp o l a n dm a t h e m a t i c i a nz p a w l a ki n 1 9 8 2 ，i nu h i c ha nu n d e f i n e ds e t x c a nb ed e f i n e db yt h el o w e ra p p r o x i m a t i o na n d t h eu p p e ra p p r o x i m a t i o n i nr o u g hs e t s t h eo b j e c ts e txi sas t a t i cs e t p r o f e s s o r s h ik a i q u a ne x t e n d e dz p a w l a kr o u g hs e t si n t os i n g u l a rr o u g hs e t s ，c a l l e d s - r o u g hf 沱1 s f o rs h o r t , w h i c hh a st w of o r m s ：o n ed i r e c t i o ns - r o u g hs e t s ，t w o d i r e c t i o ns - r o u g hs e t s t h eb o u n d a r yo f xi ns - r o u g hs e t si sd y n a m i c z p a w l a k r o u g hs e t si st h es p e c i a lc a s eo fs - r o u g hs e t sa n ds - r o u g hs e t si st h eg e n e r a lf o r m o fz p a w l a kr o u g hs e t s o nt h eb a s i so fs - r o u g hs e t s ，p r o f e s s o rs h id e v e l o p e d t h ee l e m e n te q u i v a l e n c ec l a s si n t of u n c t i o ne q u i v a l e n c ec l a s s ，a n da d v a n c e d f u n c t i o ns - r o u g hs e t s i nt h i sp a p e r , w ec o m b i n e s - r o u g hs e t st h e o r y w i t h b i o l o g i c a lh e r e d i t yt h e o r ya n dm e s s a g et r a n s f f rt h e o r y , a n dc o m b i n ef u n c t i o n s - r o u g hs e t sw i t hg r a ys y s t e mt h e o r ya n dg i v ed i s c u s s i o na n dr e s e a r c h ，t h ep a p e r e m p h a s i z e sb o t ht h e o r e ma n da p p l i c a t i o n s t h ec o n c r e t er e s u l t so ft h i sp a p e r ：w e i n t r o d u c et h ec o n c e p t so fs - r o u g hs e t sa n di t st w of o r m s ：o n ed i r e c t i o ns - r o u g h s e t sa n dm od i r e c t i o ns - r o u 曲s e t s ，a n dg i v e st h e i rm a t h e m a t i c a ls t r u c t u r e s ，p u t f o r w a r dt h eh e r e d i t yc h a r a c t e r i s t i c sa n dh e r e d i t yt h e o r e mo fs - r o u g hs e t ，w h i c hi s a p p l i e di n t ot h em e s s a g et r a n s f e rt h e o r e ma n de s t a b l i s ho n ed i r e c t i o ns - m a s s a g e t r a n s f e rm o d e la n dt w od i r e c t i o ns - m a s s a g et r a n s f e rm o d e l ；i n t r o d u c et h e c o n c e p t so ff u n c t i o ns - r o u g hs e t sa n di t st h r e ef o r m s ：f u n c t i o no n ed i r e c t i o n s - r o u 曲s e t 5 f u n c t i o nt w od i r e c t i o ns - r o u g hs e t sa n dd u a lf u n c t i o no n ed i r e c t i o n s - r o u g hs e t s ，g i v e st h e i rm a t h e m a t i c a ls t r u c t u r e s ，p u tf o r w a r dt h eh e r e d i t y 山东大学硕士学位论文 c h a r a c t e r i s t i c sa n dh e r e d i t yt h e o r e mo ff u n c t i o ns - r o u g hs e t , w h i c hi sc o m b i n e d w i t hg r a ys y s t e mt h e o r e m ，a n de s t a b l i s ht h el a wm i n i n gm o d e l ，w h i c hi su s e dt o d i s c o v e ra n dm i n et h el a w sh i d d e ni nt h es y s t e m ，a nl a w m i n i n ge x a m p l ei sg i v e n a tl a s t f u n c t i o ns - r o u g hs e t si san e wt h e o r ya n dm e t h o di nr e c o g n i z i n gt h e t u r b u l e n tl a we x i s t i n gi nt h es y s t e ma n dr e c o g n i z i n gt h es y s t e ml a w k e y w o r d s ：s - r o u g hs e t s ，h e r e d i t y , f u n c t i o ns - r o u g hs e t s , m e s 鼢g et r a n s f e r ，l a w m i m n g 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：啦 日期：塑：墨 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：弘肇 导师签名：期：删z 山东大学硕士学位论文 第一章前言 1 1 粗集理论提出的背景 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真和假二值之 间，因此，长期以来许多逻辑学家和哲学家就致力于研究含糊概念早在1 9 0 4 年， 谓词逻辑的创始人f r e g e g 就提出了含糊( 德文v a g u e ) 一词，并把它归结到边界线 区域，也就是说在全体论域上存在一些个体既不能在某个子集上被分类，也不能 在该子集的补集上被分类1 9 6 5 年，z a d e h l a 创立了模糊f 用英文i 一3 f u z z y 翻译德 文v a g u e ) 集合论，不少理论计算机科学家和逻辑学家，都试图通过这一理论解决 f r e g e g 的含糊概念，但模糊集是不可计算的，没有给出数学公式描述这一模糊 概念，故无法计算出它在边界线上的具体的含糊元素数且1 9 8 2 年，p a w l a k z 针对 f r e g e g 的边界线思想提出了粗集，他把那些无法确认的个体都归属于边界线区 域，而这种边界线被定义为上近似集与下近似集之间的差集，由于上近似集和下 近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被 计算出来，即在真假二值之间的含糊程度可以计算，从而实t 觅t f r e g e g 的边界 线思想粗糙集理论主要兴趣在于它恰好反映了人们用粗糙集方法处理不分明问 题的常规性，即以不完全信息或知识去处理一些不分明现象的能力粗糙集自提 出以来就一直得至u z a d e h 的重视，并给予很高评价。将粑糙集与模糊逻辑、概率 推理、信度网络、神经网络、混沌理论、遗传算法及其他进化优化算法等一起列 为他所提倡的软计算的各种基础理论 1 2 粗集理论的发展与研究概况 粗集理论作为一种处理不精确、不确定与不完全数掘的新的数学理论，最初 i 山东大学硕士学位论文 是由波兰数学家z p a w l a k 于1 9 8 2 年提出来的由于最初关于粗集理论的研究大部 分是用波兰语发表的，因此当时并未引起国际计算机界和数学界的重视，研究地 域也仅限于东欧一些国家，直到2 0 世纪8 0 年代末才逐渐引起各国学者的关注。特 别是近十年来，由于它在机器学习与知识发现、数据挖掘、决策支持与分析等方 面的广泛、成功的应用而成为当前计算机人工智能、信息科学等领域的研究热点 之一。在国际上，1 9 9 1 年，z p a w l a k 出版了第一本粗集学术专著( t h e o r e t i c a l a s p e c t so f r e a s o n i n ga b o u td a t a ) ；1 9 9 2 年，第一届关于粗集理论的国际学术研讨 会在波兰召开；1 9 9 5 年，a c mc o m m u n i c a t i o n 将它列为新浮现的计算机科学的研 究课题：1 9 9 8 年，国际信息科学杂志( i n t e r n a t i o n a lj o u r n a lo f i n f o r m a t i o ns c i e n c e s ) 为粗集理论的研究出了一期专辑；2 0 0 4 年，国际粗集协会主办的第一本粗集国际 期刊( a d v a n c e si nr o u g hs e t s ) 出版发行：波兰华沙大学、工业大学、信息技术 与管理大学和加拿大r e g i n a 大学和圣、玛丽大学、英i 雪e d i n b u r g h 大学、u l s t e r 大 学和c a r d i f f 大学、意大： l j c a t a n i a 大学、印度统计研究院、美国s a nj o s e ) ， i 立大学 等对粗集理论有着深入研究。在国内，第一届粗集与软计算学术研讨会于2 0 0 1 年在重庆邮电学院召开：2 0 0 3 年1 0 月，重庆邮电学院成功承办了第九届国际粗集、 模糊集，数据挖掘与粒度计算学术研讨会；中国人工智能学会于2 0 0 3 年正式成立 粗糙集与软计算专业委员会；第四届中国粗集与软计算学术研讨会2 0 0 4 年1 0 月在 浙江海洋学院成功召开。曾黄麟、王国胤、刘清、张文修、史开泉等先后出了关 于粗集理论的多本专著：该理论的主要研究人员大多来自计算机科学领域，也有 来自信息科学、数学、系统科学、管理科学、控制科学等领域的学者即使随便 翻阅一本近年国内的计算机类学术期刊，都很可能看到和粗集有关的理论或应用 论文从研究地域来看，欧洲国家比较注重理论研究，北美学者比较注重应用， 日本在粗集和概率论相结合方面以及在医学的应用比较突出，我国在知识约简、 与信息论的结合、粗逻辑、粒计算、知识的不确定性研究方面取得了较大成功 2 山东大学硕士学位论文 粗集理论是建立在分类机制的基础之上的，它将分类理解为在特定空间上的等价 关系而等价关系构成了对该空间的划分粗集理论将知识理解为对数据划分的 结果，每一被划分的集合称为概念它的主要思想是利用已知的知识库，将不精 确或不确定的知识用已知的知识库中的知识来近似刻画 1 3 粗集理论及其应用研究现状 目前对粗集的研究主要集中在以下几个方面： ( 1 ) 粗集的数学性质研究方面包括粗集的代数结构和拓扑结构等，与数学理论的 结合使得一些新的概念己经出现，如“粗糙理想”和“粗糙半群”等 ( 2 ) 粗集理论拓展的研究，包括： 关系的推广，如基于相似关系的粗集模型，基于一般二元关系的粗集模型，另 外将对象所在的等价类看作该对象的一个邻域，从而推广导出基于邻域算子的粗 集模型：结合模糊集理论将粗集理论进行拓展，如将普通关系推广成模糊关系或 模糊划分而获得模糊粗集模型 变精度粗集和概率粗集模型等 ( 3 ) 粗集与其它软计算方法的联系与融合方面，包括与模糊集、证据理论等的关 系，与人工神经网络和遗传算法等的融合等 ( 4 ) 属性约简研究 1 4 论文的研究背景及意义 本文主要研究s 一粗集的特性和应用，函数s 一粗集的特性和应用s 一粗集 ( s i n g u l a rr o u g hs e t s ) 是本人导师史开泉教授于2 0 0 2 年提出的具有动态特性的粗集， 是z p a w l a k 粗集的拓展和延伸，因为在z p a w l a k 定义的粗集( r 一( z ) ，r 一( x ) ) 中：1 研究的对象集合xcu 是静态的，没有元素迁移的现象存在；2 给定集合xcu 。 山东大学硕士学位论文 则肖的上近似和下近似足( z ) ，r 一( x ) 确定，粗集( r 一( x ) ，r 一( x ) ) 也确定这里：x 是元素论域u 上的元素集合，x c u ，r 一( x ) ，r 一( x ) 分别是x 的上近似，下近似，r 是元素等价关系可以看出，z p a w l a k 粗集是具有静态特性的粗集，对于目前大多 数具有动态特性的系统如动态数据挖掘，动态知识发现，动态目标识别等方向的研 究有困难，为了解决z p a w l a k 粗集在研究具有动态性对象的不足，史开泉教授提出 了s 租集和它的两类形式：单向s - 粗集( ( 尺，) ( 工) ，( r ，f ) + ( x ) ) ，双向s 粗集 ( ( 足，莎) ( z ) ，( r ，莎) ( x + ) ) ，这里：f 和莎是元素迁移，f = i f , ， ，厶) ， f = 孺，五，五 ，莎= p u p z 的意义：3 u u ，舀j ， ) - - - - x e x ，z 的意 义：孤x 户( 功= i x f 使得集合x 向外扩张，x 具有单向动态特性；莎 使得x 既向外扩张，又向内收缩，彳具有双向动态特性s 粗集具有动态特性，从s 粗集( 单向s - 粗集，双向s 粗集) 的结构可以看出：s 粗集是z p a w l a k 粗集的的一般 形式，z p a w l a k 粗集是s 粗集的特例s 粗集是粗集的一个研究分支，从静态动态 的角度上，可以说s 粗集是z p a w l a k 粗集的发展 z p a w l a k 粗集和s 一粗集都是以元素等价类【x 】。定义的，它们在研究以离散的， 单个对象为元素的集合( 等价类) 时充分发挥了它们的特性进一步思考，如果我们 将等价类中的元素扩展到具有时间连续的函数中，即元素等价类【x 】。变成了函数 等价类【“( x ) 】。，那么我们的研究对象是否由个体延伸为系统? 答案是肯定的按照 这个思路，史开泉教授于2 0 0 5 年又提出了函数s 粗集( f u n c t i o ns - r o u g hs e t s ) 和它 的两类形式：函数单向s - 粗集( f u n c t i o no n ed i r e c t i o ns - r o u g hs e t s ) ，函数双向s - 粗集 ( f u n c t i o nt w od i r e c t i o ns - r o u g hs e t s ) 一个函数就是一个规律，因此，函数s 一粗集的提 出及对其特性的研究为我们寻找系统的运行规律挖掘潜藏规律提供了理论支持 利用粗集对系统规律的研究是粗集理论和应用的一个重大突破。对于变化多端的 金融系统，风险投资系统，状态识别系统，故障诊断系统等诸多系统中的规律识别， 系统状态规律生成及规律挖掘，规律发现的研究具有重要的开创性的意义 4 山东大学硕士学位论文 1 5 论文结构和内容 本文理论和应用相结合，在研究s 一粗集，函数s 粗集的性质的基础上，给出了 典型应用。具体的章节安排如下： 第一章介绍了粗集的研究背景和重要意义，s 粗集，函数s 一粗集提出的背景， 结构和意义 第二章用一个例子引入粗集的概念，并介绍了粗集的特性和应用 第三章引入s 粗集的概念，给出单向s 粗集，双向s 罐l 集的定义和结构，研究 了s 粗集的遗传特性和遗传定理，并将s 粗集与信息传递理论相结合，给出基于 s 粗集遗传特性的s 信息传递模型 第四章引入函数s 粗集的概念，给出函数单向s 粗集，函数双向s 粗集以及 函数单向s 租集对偶的概念和结构，讨论了函数s 粗集与s 粗集的关系，提出函数 s 粗集的遗传特性和遗传定理，将函数s 粗集的遗传特性与灰色系统理论相结合， 建立规律挖掘模型，用于发现和挖掘系统隐藏的规律，并给出实际应用 第五章论文总结及展望 山东大学硕士学位论文 第二章z p a w l a k 粗集 通常我们周围的信息都是不精确，不完整或者不确定的，要处理这些信息必须 要有相应的理论支持粗集和模糊集是处理不精确，不确定( 模糊) 信息的两大主要 工具 本章主要介绍粗集的基本概念和理论，并用简单的例子阐述粗集的应用粗 集自1 9 8 2 年波兰数学家z p a w l a k 教授提出以来，作为一个处理不确定性和不精确 性问题的理论工具，其理论和应用取得了很大的进步与发展近年来，粗集与神经 网络，遗传算法，模糊控制等智能工具结合起来，在机器学习，数据挖掘，知识发现，模 式识别，故障诊断，决策分析，过程控制等领域获得了成功运用 2 1z p a w l a k 粗集的引入背景 我们从一个通俗的例子引出粗集的概念 薯 毛 x 毛 图i 形状规则的牛皮 图l 是一块规则的牛皮，如果每个小方块可以做一双皮鞋，图中粗线包围的部 分可以做6 双皮鞋，分别用x l , x 2 ，x 3 ，_ ，毛表示，如图l 中所示做成的皮鞋用集 合可以用集合x 描述，这里：x = 五，屯，x 3 ，毛，x j 这里的集合x 是经典数学里 6 山东大学硕士学位论文 集合，是一个精确集这是一个精确的概念也就是说，粗线包围的牛皮正好能做6 双皮鞋，不多不少然而实际生活中的牛皮是否都是方方正正的? 答案是否定的我 们经常会碰到这种情况，如果给定的牛皮不是图1 所示的规则的，而是如图2 所示 图2 中曲线包围的牛皮能做多少双鞋子? 很显然，中间6 个小方块可以正好做六双， 阴影部分是做完6 双皮鞋后剩下的的牛皮，俗称下脚料，不是完整的小方块，但是 通过拼接大约可以拼成3 5 个方块，也就是说大约还能做3 5 双皮鞋 p l h ， 1 h k f 哆 - 3 l - o 图2 形状不规则的牛皮 比较图l 和图2 ，容易得到这样的事实：图1 中每个小方块都是完整的，是一个 精确的概念，能用普通集合表示，即x = “，毪，b ，毛，k ) ；而图2 中存在不精确 的边界部分，很显然不能用经典集合表示，如何描述这个集合呢? 这就给经典集 合理论提出了挑战如何用集合的概念来描述图2 中的元素? 针对这个问题，波兰 数学家z p a w l a k 提出了粗集的概念，所有边界非完整的带阴影的方块用集合 x ； 工i ，善；，j ：。 ，那么图中曲线内的部分可以用集合x 和集合x u x 来逼 近，即用y = ( ，u x ) 来表示现实中这类情况经常出现粗集的提出使这类不 精确问题得到了很好的解决 7 山东大学硕士学位论文 2 2z p a w l a k 粗集的基本理论与应用 首先介绍粗集的几个基本概念 定义2 2 1 设r 是定义在集合x 上的一个关系，若r 满足自反性，对称性和传递性， 则胄称为等价关系( 不可分辨关系) 定义2 2 2 设置是集合z 上的等价关系，或者不可分辨关系，对任意的j x ， 【x k = y l y x ，皿) 称为x 关于胄的等价类 定义2 2 3 设u 是非空有限论域，矗是u 上的等价关系，则称 s = ( u ，尺)( 2 2 1 ) 是一个信息系统，或称作近似空间 定义2 2 4 给定集合xc u ，r 是定义在x 上的等价关 系，r = 蜀，r ，r 。 ， x 】。是r 一等价类，r 一( x ) ，r 一( z ) 分别被称作x c u 的 下近似，上近似，如果 r 一( x ) = u 【x 】r = x l x u ，【x 】月互x )( 2 2 2 ) r 一( ) = u m 。 = x i x u ，【x 】月n x ( 2 2 3 ) 集合对( r 一( x ) ，r 一( x ) ) 称作x 亡u 的r 一粗集，简称粗集 很显然，r 一( x ) x r 一( x ) ，如图3 所示 ，一 么勿孰 么缓疬砀 戮k 么级 彩 黝 锄 黝 图3x 的下近似，上近似表示 山东大学硕士学位论文 这罩：r 一( 1 由所有完全属于x 的等价类组成，r 一( 爿) 由所有可能属于彳的等价 类组成 在z p a w l a k 粗集( 月一( x ) ，r 一( z ) ) 中，r 一( 肖) 是最小可定义集，r 一( ) 是最大可 定义集，b n r ( x ) 是r 一边界，而且 b n r ( x ) 2r 一( x ) 一! 一( y ) ( 2 ，2 5 ) 若b n r ( x ) = r 一( 工) 一疋( x ) = ，则z 是一个精确集 例：给定论域u = “，工：，x ，。) 和属性集r = “，r 2 ，r d ，将论域u 按属性集r 分 类，得到初等集： u r = “x l ，x ，b ， x 2 ，x 7 ，x l o ) ， x 4 ) ， x 5 ，工s ， x 6 ) 考虑对象集合x = _ ，x 3 ，_ ，毛，南 ，z 的下近似 月一( x ) = u 【工】r = x x u ，【x 】月x ) = 工i ，x 3 ，x 4 ，x 9 ) 上近似 r 一( x ) = u 【x 】r = x l x u ， x 】r n x 矿) = 工i ，石3 ，工4 ，x s ，x s ，x 9 ) 边界 b r n ( x ) = r 一( x ) 一r 一( j ) = 黾，x s u 上的粗集有四种类型： 1 若r 一( x ) 且r 一( x ) u ，则z 是( ，上的粗可定义集 2 若r ( x ) 且r 一( 肖) = u ，则j 是u 上的外不可定义集 3 若月一( x ) = 且月一( 彳) u ，则x 是u 上的内不可定义集 9 山东大学硕士学位论文 4 若r 一( ) = 且r 一( x ) = u ，则x 是u 上的完全不可定义集 定义2 2 5p o s r ( x ) ，n e g r ( x ) 分别被称作x c u 的r 一正域，r 一负域，而且 p o s 口( x ) = r 一( ) n e g 。( 工) = u r 一( )( 2 2 6 ) p o s 。( x ) 是由所有肯定属于x 的元素组成的集合，n e g 。( x ) 是所有肯定不属于 x 的元素组成的集合 定义2 2 6 给定【，上的等价关系r ，r 一( 爿) ，月一( x ) 分别是z 的下近似和上近似， 则称 d 月( x ) = c a r d ( r 一( x ) ) c a r d ( r 一( x ) ) ( 2 2 7 ) 是x 由等价关系r 定义的近似精度，其中c a r d ( * ) 表示该集合元素的数 目，x 精度d 。( x ) 反映我们了解集合x 的知识的完全程度显然，对于每一个等价关 系r 和对象集合x u ，有0 d r ( x ) l ；当d r ( x ) = 1 时，x 的尺边界域为空，集 合x 是尺可定义的：当d r ( 工) 1 时，x 有非空边界域，集合x 是r 不可定义的 定义2 2 7 给定属性集pr - - r ，若存在属性集q = p r ，q p ，使得 i n d ( q ) = i n d ( p ) ( 2 2 8 ) 而且q 是j p 最小子集，则称o 是p 的简化，记作r e d ( p ) ：r 是可省略的否则，r 是 尸中不可省略的 属性集合j p 可能有多种简化，p 的所有简化的交集称作p 的核，记作c o r e ( p ) ， 而且 c o r e ( p ) = n r e d ( p ) ( 2 2 9 ) 简而言之约减就是对属性集合的简化，去掉冗余属性，不影响对象的表达：核是 非常重要的决策属性，是表达知识必不可少的重要属性集，不能消去属性约简是 利用粗集理论进行决策，识别的第一步在信息系统x = ( 己，r ) 中，c ，dcr 是两 0 山东大学硕士学位论文 个属性子集，即条件属性和决策属性具有条件属性和决策属性的信息系统可表 达为决策表记做t = ( u ，r ，c ，d ) 简化决策表通常就是要化简决策表中的条件 属性，简化后的决策表具有与简化前的决策表相同的功能。 利用粗集方法处理数据，不需要获得所处理问题的数据集之外的任何先验信 息，只依赖数据内部的知识，用数据之间的近似来表示知识的不确定性粗集可以 对不完整数据进行分析，推理。从而发现数掘问的关系；提取有用特征，简化信息 处理，研究不精确，不确定知识的表达，从中发现隐含的规则所以粗集理论在模 式识别，人工智能，数据挖掘，控制决策等方面得到广泛的应用下面给出一个利 用粗集理论进行目标识别的简单例子 由目标样本集构成的原始关系表如表l ，为了简化问题，表中只给出3 个条件 属性，分别为高度，头发。眼睛决策属性为人的类别目标对象8 个，分别为a ，b 类 中的一种 表i 原始数据表 对象高度头发眼睛分类 1 矮 黑蓝a 2高黑蓝a 3 高黑棕a 4 高 红蓝b 5矮黄蓝b 6 高黄棕a 7 高黄蓝 b 8 矮黄棕 a ( 1 ) 对原始数据进行预处理，既数据的拆分与赋值，条件属性c = 口，b ，c ) ，口，b ，f 分 别对应身高，头发颜色，眼睛颜色属性，决策属性d = d ，既人的类别条件属性 值域口= f l ，2 ) 分别代表高，矮；值域b = l ，2 ，3 ) 分别代表黑，红，黄；值域 c = 1 , 2 分别代表蓝棕；决策属性值域d = a ，b 分别代表a ，b 两类人将表1 数值化得到满足粗集处理需要的关系表，表中的赋值并不影响识别的结果 1 1 山东大学硕士学位论文 表2 预处理后的关系表 对象 abcd l llla 22lla 32l2a 4221b 5l3lb 62 3 2a 723lb 8l32a ( 2 ) 对预处理后的关系表进行属性约减，消除冗余属性属性约减原则：每次去掉 一个条件属性s ，检查d 在c - s ) 中的正域是否等于d 在c 中的正域，以属性4 为 例，计算属性a 是否冗余 论域【，关于条件属性集c 的商集：u c = “l ，1 2 1 ， 3 ) ， 4 ) ， 5 ) ， 6 ， 7 t ， 8 ) ， 论域u 关于决策属性集d 的商集：u i d = ( 1 ，2 ，3 ，6 ，8 ) ， 4 ，5 ，7 ) ) ，( d ) = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) u l c 一 口) ) = 1 1 ，2 ) ， 3 ) ，1 4 ， 5 ，7 ) ， 6 ，8 ) ) p o s i c - 。：) ( d ) = i ，2 ，3 ，4 ，5 ，6 ，7 ，8 = p o s f ( d ) p o s ( 叫) ( d ) p o s c ( d ) 属性a 冗余，是关于d 的可约简的，删去a 不会破坏原始数据的分类信息按同样的 计算方法：p o s ( ( - l i i ( d ) p o s ( ( d ) ，j p 呱c - f 圳( d ) j p d & ( d ) ，所以属性6 ，c 是关 于d 不可约简的所以c o r e ，( d ) = 6 ，c 删去属性口后合并重复对象整理得表3 表3 属性约简历的大系表 1 2 对象 bcd l11a 3l2a 421b 531b 632a 山东大学硕士学位论文 化简决策规则中的条件属性的冗余值，对于规则1 ，集合 f = i f 。，【l 】。 = “l ，3 ， 1 ，4 ，5 ) ) 这罩：b o ) = 1 ，c ( 1 ) = l 故 【1 】l 州= 1 1 1 。ne l l ，= 1 ，3 f l i ，4 ，5 = 1 ) 为了求出可省略范畴，我们必须每次去掉一个范畴，并检查其余范畴的交是否还包 含在决策范畴【1 k = l ，3 ，6 ) 中 【l 】= 【1 1 。= 1 , 4 ，5 叫l k ，否 【l 】，一。= 【1 l = 1 ，3 ) c 【l l ， 是 规则1 的核值为b ( 1 ) = 1 类似的，我们可以计算其它决策规则的核值，得到条件属性核值表和生成识别 规则表 表4 核值表 对象 bcd l1 a 42 b 5 1b 6 2 a 表5 识别规则简化表 对象 b cd ll + a 2 2a 32 b 4 lb 用表5 中的识别规则，可以对给定的8 个人进行识别 根掘表5 ，不仅可以将所给的对象分类，还可以作为一个分类器，对任意同 性质的对象进行分类，在模式识别，机器学习中具有重要应用 山东大学硕士学位论文 第三章s 粗集结构与应用 3 1 单向s 粗集 约定：在3 1 - 3 2 的讨论中，设( ，是一个有限论域，r 是u 上的等价关系族，【x 】。 是r 等价类 定义3 1 1 给定集合x c u ，称f = z ， ，l ) 是定义在u 上的元素迁移 族，f 称作元素迁移，如果，f 满足 3 u u ，”i x j ，( “) = 工x( 3 1 1 ) ( 3 1 1 ) 的直观意义是：不在x 内的元素”，元素甜在z f 的作用下，“变成 ，( 甜) = z ，x 进入x 内；元素“是u 上的风险因素，元素“具有“突然特性”，“攻击 特性”；元素“常常在风险决策中遇到 定义3 1 2 称x 。是z c u 的单向s 集合，如果 x = x u j l “u ，“i x ，厂( “) = 工x ( 3 1 2 ) x 7 称作x c u 的，扩张，而且 x 7 = x l u ，“百x ，f ( u ) = x x )( 3 1 3 ) 定义3 1 3 称( 胄，f ) ( 。) 是x c u 的下近似，而且 ( 尼f ) 。( x 。) = u 【x 】r = x i 工u ，【工】r x 。) ( 3 1 4 ) 称( r ，f ) ( x 。) 是x 。c u 的上近似，而且 ( r ，) ( x ) = u 【x 】。 = x i x u ，i x r n x 庐 ( 3 1 5 ) 定义3 1 4 由( r ，) ( x 。) ，( 见f ) ) 构成的集合，称作x c u 的双向s - 粗集， 而目 山东大学硕士学位论文 “r ，f ) ( x ) ，( r ，) 。( j ) )( 3 1 6 ) 定义3 1 5 称a s ( x ) 是单向s - 粗集( ( 月，f ) ( x ) ，( r ，) 。( j ) ) 生成的副集合 ( a s s i s t a n ts e t s ) 而且 a s ( x ) = 工1 1 1 u ，i x ，f ( u ) = j 琶z ( 3 1 7 ) 这里：“茗”的直观意义：元素甜不完全被，f 迁移到x 内 这里应该给出特别的说明：( 3 1 3 ) 表示元素“u ，- f f x ，甜在厂f 的作用下变 成厂( “) ；x ，厂 ) 被完全迁入到x 内；( 甜) 关于集合x 的特征函数z ；町满足 以”= 1 ( 3 1 7 ) 表示元素“u ，u i x ，在厂f 的作用下变成厂( “) = x ，厂( ) 不被完全迁入到x 内，八) 关于集合x 的特征函数z 少满足o z 。 1 图3 1 给出单向s 粗集直观表示 i rr 痧勃物 ， 。 名缴笏历缓缓红 崩 一 ，(，)狻 f - a 绂缀 锄缓缢缈 图3 1 ，单向s 一集合爿= x u o i “u ，“毛x ，( “) = 工e j ，x 具有单向动态特性，存在单向s - 8 t 集 “尼，) ( xx ( r ，) i 爿) ) 命题1 ( ( 足，) ( 肖) ，( 尺，f ) 。( x ) ) 是具有单向动态特性的粗集 3 2 双向s 粗集 定义3 2 1 给定集合x 亡u ，称f = ；，正，厶) ，i = - l ，7 ：，7 。 是定义在 u 上的元素迁移族，e ，一f i 称作元素迁移，如果，f , 一f ，万分别满足： 3 u u ，j i x j ，( “) = x x( 3 2 1 ) 孤x j 7 j ( x ) = 亨x( 3 2 2 ) 山东大学硕士学。位论文 ( 3 2 2 ) 的直观意义是：在x 内的元素x ，元素x 在7 ，f 的作用下变成_ ( 工) = 站，l f 离开x 定义3 2 2 称x 。是集合z c u 的双向s 集合如果 = x u x l 甜u ，“i x ，厂 ) = x x ) ( 3 2 3 ) 称x 称作x c u 的亏集( 1 0 s ss e t s ) ，而且 x = x 一 工i x x ，f ( x ) = i x ) ( 3 2 4 ) z 7 称作xc u 的7 萎缩，而且 r 7 = x lx x ，7 ( z ) = ”i )( 3 2 5 ) 定义3 2 3 称( 足莎) ( ) 是x cu 的下近似，而且 ( 足莎) ( x ) = u 叫r = x l 工u ，i x r z + )( 3 2 6 ) 称( r ，莎) ( x 。) 是x c u 的上近似，而且 ( r ，莎) 。( x ) = u 瞳】r = z z u ，i x 。n x )( 3 2 7 ) 这里：莎= f u ? ，f ，万 定义3 2 4 由( 尺，莎) ( x ) ，( 足莎) ( x ) 构成的集合称作z c u 的双向s 粗集，而 且 ( ( r ，莎) 。( x ) ，( r ，莎) ( x + ) )( 3 2 8 ) 定义3 2 5 称a s ( x + ) 是双向s - 粗集( ( r ，莎) ) ，( r ，莎) ( x ) ) 生成的副集合 ( a s s i s t a n ts e t s ) 。而且 a s ( x ) = x i ”u ，“西，( “) = x 苔xa n d x x ，7 ( x ) 辱工) ( 3 2 9 ) 这里：“鲁”是一个特别的记号，“辱”的直观意义是：元素工不被7 完全迁出 到x 外 6 山东大学硕士学位论文 图3 2 给出双向s - 粗集直观表示 图3 2 双向s 集合x + = ( x u 和k c ，“毛x ，( “) = ，e x - 圳j e x ，7 ( j ) = 甜善x x 具有双向动态特性，存在双向s 瓤集“r ，矿) ，( x k ( 尼矿) ( x ) ) 图3 3 给出双向s 粗集的特征函数表示 图3 3 ( r ，。矿) ( x ) 是x + c u 的下近似，a ( x ) = 扣p e u ，毛爿，( “) = 工e 爿， ( x ) = x l x x ，7 ( d = “辱x ；a , c x ) ac x ) 分别是a ( x 。) 的一个部分 命题2 “r ，莎) 。( x ) ，( r ，莎) ( x ) ) 是具有双向动态特性的粗集 3 3s 粗集的f 遗传特性与遗传定理 下面先看一个例子，设u ：x i , 工2 ，而，h ，x s , x 6 ，x ，x l ，x 9 ，工l o ) 是一些苹果组 成的论域，口： ，口2 ，吒，c r 4 是定义在u 上的属性：q = 红色，口2 i 甜味，2 直径 5 c m ，：重量1 5 0 克，依据q 得到【x 】( 口i ) = “，而，x 4 , x 7 ，x l ，x l 。) ；显然【工】i m ) 是关 ， 山东大学硕士学位论文 于的等价类；一，屯，x 4 ，而，而，一。关于不可分辨，存在i n d ( x ( 。) ) ；与此类似， 依据0 l i , 2 得到【x 】i q ) _ “，屯，x 4 ，x s ，_ o ，存在i n d