（应用数学专业论文）粗糙集理论及其在多目标优化中的应用.pdf

摘要 粗糙集( r o u g hs e t s ) 理论是二十世纪八十年代初由波兰数学家z p a w l a k 首先 提出的一种新的处理含糊和不精确数据的数学工具该理论被视为当代信息科学 中重要的软计算方法近年来，粗糙集成为人工智能和信息科学最活跃的研究领域 之一，并且在模式识别、冲突分析、数据挖掘、智能控制、机器学习、知识获取、 医疗诊断、专家系统、人工神经网络、决策分析、数据库知识发现、机械故障诊 断、材料科学、金融和市场分析等领域得到成功应用 本文研究粗糙集理论及其在多目标优化中的应用，旨在开拓粗糙集理论的应用 领域、寻求解决多目标优化问题的新途径主要工作如下： 1 讨论了粗糙集与分配b z 一格上的区间结构的关系研究了分配b z 一格上的 区间结构和性质，建立了分配b z 一格上的租糙集代数，利用分配b z 一格上的反直 觉算子，构造了一对对偶算予，这对算子不仅具有良好的代数性质，而且可以生成 一个粗糙集代数证明了分配b z 一格上的任一元素口的粗糙近似( y ( 口) ，芦( 口) ) 可由 必然性测度y 和可能性测度得到对于任意给定的一个分配b z 一格，可由“v 和 “”这一对近似算子诱导一个粗糙集代数 2 研究了基于粗糙近似算予的模式“二分法”的性质描述了把给定的模式 空间划分成两类的可能性和必然性，设计了有边界区域的模式分类的可能性和必然 性的粗糙神经网络算法，并用仿真实验验证了算法的有效性利用h l e e ，h t a n a k a 的区间回归分析的上、下近似模型，解决了个“选址”优化问题基于 j s t e f a n o w s k i 的赋值容差关系处理不完备信息表的数据推理算法，解决了一个“房 地产评价”问题 3 在区间可能性规划中构造了一个等价关系，定义了最优解集的上、下近似 解集，给出了判定可能最优解和必然最优解的一个充要条件用实例说明了最优解 的判定方法及可能度和必然度的计算方法 4 。研究了多目标规划问题的冗余约束条件的约简方法和有效解的粗糙近似方 法提出了多目标规划问题的约束条件关于某目标函数的约束度的定义，根据约束 度大小和各个目标函数对约束度阀值的要求，删除不重要约束建立了原问题的核 心约束条件组和相应的核心有效解的概念，刻画了原问题的有效解和核心有效解 的关系设计了一种剔除冗余约束和求各个目标函数都能接受的有效解的粗糙近 似算法框图用实例验证了所提的概念和方法的有效性 5 提出了多目标优化问题的目标函数对参考解的满意度、支持解集、中立解 集、冲突解集等概念通过计算各个目标函数支持解集、中立解集、冲突解集，不 仅可以确定目标函数之间的相互关系，而且可以对参考解进行排序利用属性约简 可以确定多目标优化问题中的核心目标函数，为决策者提供更为可靠的决策信息 关键词：粗糙集上、下近似算子分配b z 一格模式分类可能性测度必然 性测度约束度多目标规划冲突分析 a b s t r a c t r o u g hs e t t h e o r y , i n t r o d u c e db y z p a w l a k1 9 8 0 s ( p a w l a k ，1 9 9 1 ；p a w l a ke ta 1 ，1 9 9 5 ) ， i san e wm a t h e m a t i c a lt o o lt od e a lw i t h v a g u e n e s sa n d u n c e r t a i n t y m o r er e c e n t l v ，a sa n i m p o r t a n tm e t h o df o rt l l es o f tc o m p u t i n gi ni n f o r m a t i o ns c i e n c e r o l l 【g hs e tt h e o r yh a s b e c o m eo n eo ft h em o s ta c t i v er e s e a r c hf i e l do fa r t i f i c i a li n t e l l i g e n c ea n di n f o r m a t i o n s c i e n c e ，a n di th a sb e e ns u c c e s s f u l l ya p p l i e dt om a n ya r e a ss u c ha sp a t t e mr e c o g n i t i o n ， c o n f l i c t a n a l y s i s ，d a t am i n i n g ，i n t e l l i g e n tc o n t r o l ，m a c h i n e l e a r n i n g ，k n o w l e d g e a c q u i s i t i o n ，m e d i c i n ed i a g n o s i s ，e x p e r ts y s t e m s ，a r t i f i c i a ln e u r a ln e t w o r k s ，d e c i s i o n a n a l y s i s ，k n o w l e d g ed i s c o y e r yf r o md a t a b a s e s ，m a c h i n ed i a g n o s i s ，m a t e r i a ls c i e n c e ， f i n a n c i a la n dm a r k e t a n a l y s i s ，a n ds o o n r o u g h s e tt h e o r ya n di t sa p p l i c a t i o n si nm u l t i p l eo b j e c t i v eo p t i m i z a t i o n sa r es t u d i e d i nt h i s p a p e r i ti s o u ra i m st of i n dn e wa p p r o a c h e st os o l v e m u l t i p l eo b j e c t i v e o p t i m i z a t i o np r o b l e m a n dt oi n i t i a t en e wa r e a so f r o u g hs e t d e t a i la sf o l l o w s ： 1 t h e r e l a t i o n s h i pb e t w e e nr o u g hs e t sa n di n t e r v a ls t r u c t u r eo f t h ed i s t r i b u t i v e b z l a t t i c e si sd i s c u s s e d ，w es t u d yt h ei n t e r v a ls t r u c t u r ea n dp r o p e r t i e so ft h e d i s t r i b u t i v eb z - l a t t i e e sa n dc o n s t r u c tar o u g hs e t a l g e b r ao v e rt h e m i n a d d i t i o n ，ap a i ro fd u a lo p e r a t o r s i sc o n s t r u c t e d b yu s i n g a n t i - i n t u i t i o n o p e r a t o r s o v e rt l l ed i s t r i b u t i v eb z l a t t i c e s w h i c hn o t o n l yh a s e x c e l l e n t p r o p e r t i e sb u t a l s og e n e r a t e sar o u g hs e ta l g e b r ai ti sp r o v e dt h a tt h er o u g hs e t a p p r o x i m a t i o n ( v ( 口) ，“( 口) ) o fa n y ai nd i s t r i b u t i v eb z - l a t t i c e sc a nb e i n d u c e df r o mt w om o d a l - l i k eu n a r y o p e r a t o r s ( vf o rn e c e s s i t y a n d”f o r p o s s i b i l i t y ) ，s oc a n a r o u g h s e ta l g e b r af o ra n yg i v e nd i s t r i b u t i v eb z - l a t t i c e 2 t h ep r o p e r t i e so fr o u g ha p p r o x i m a t i o no p e r a t o r sb a s e do nt h eb i s e c t i o n m e t h o do fp a t t e ma r es t u d i e d ，w ed e s c r i b et h ep o s s i b i l i t ya n dn e c e s s i t yo f p a t t e r nc l a s s i f i c a t i o nb yd i v i d i n gap a t t e r ns p a c e i n t ot w od e c i s i o na r e a s ，t h e n an e wr o u g hn e u r a ln e t w o r k sa l g o r i t h mo fp o s s i b i l i t ya n dn e c e s s i t yo ft h e c l a s s i f i c a t i o np r o b l e mw i t hb o u n d a r ya r e a si sd e s i g n e d a ne x a m p l es h o w s t h a tt h ea l g o r i t h mi se f f e c t i v e t h e “l o c a t i o n ”p r o b l e mi ss o l v e db yu s i n g u p p e ra n dl o w e ra p p r o x i m a t i o nm o d e l si n i n t e r v a lr e g r e s s i o np r o p o s e db y h l e ea n dh t a n a k a t h e “r e a le s t a t ee v a l u a t i n g p r o b l e mi ss o l v e db y m e a n so ft h e a l g o r i t h m f o rd a t a r e a s o n i n gd e a l i n g w i t l l i n c o m p l e t e i n f o r m a t i o n s y s t e m s b a s e do nv a l u e dt o l e r a n c et e l a t i o n p r o p o s e db y j s t e f a n o w s k i 3 t h e u p p e ra n dl o w e ra p p r o x i m a t i o no fo p t i m a ls o l u t i o n ss e ti sd e f i n e dw i t h a l le q u i v a l e n c er e l a t i o nc o n s t r u c t e di ni n t e r v a lp o s s i b i l i t yp r o g r a m m i n g t h e n as u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rd e t e r m i n i n gp o s s i b l ea n d n e c e s s a r y o p t i m a l s o l u t i o n si s p r e s e n t e d a ne x a m p l es h o w st h e d e t a i l c o m p u t i n g m e t h o d 4 ar e d u c t i o n a l g o r i t h m f o rc o n s t r a i n tc o n d i t i o na n dan e wa p p r o a c ht o a p p r o x i m a t e e f f e c t i v es o l u t i o n si n m u l t i p l eo b j e c t i v ep r o g r a m m i n g a r e s t u d i e d t h ed e f i n i t i o no ft h ec o n s t r a i n td e g r e eo fc o n s t r a i n tc o n d i t i o n sf o r g i v e ns o m eo b j e c t i v ef u n c t i o ni nm u l t i p l eo b j e c t i v eo p t i m i z a t i o n s i sp r o p o s e d ， a c c o r d i n gt ow h i c hl e s si m p o r t a n tc o n s t r a i n t sa r er e m o v e d i na d d i t i o n ，t h e s y s t e mo f c o r ec o n s t r a i n t sa n dt h ec o r r e s p o n d i n gc o n c e p to f t h ec o r ee f f e c t i v e s o l u t i o no ft h eo r i g i n a lm o d e la r cb u i l t ，w h i c hc h a r a c t e r i z et h er e l a t i o n s h i p b e t w e e ne f f e c t i v es o l u t i o na n dc o r ee f f e c t i v es o l u t i o no f t h eo r i g i n a lm o d e l f i n a l l y , e x p e r i m e n t ss h o w t h a tt h em e t h o di se f f e c t i v e 5 m a n yd e f i n i t i o n sa r ep r o p o s e d ，s u c ha ss a t i s f a c t o r yd e g r e eg i v e nr e f e r e n c e s o l u t i o n s ，s u p p o r t i n g s o l u t i o ns e t ，n e u t r a ls o l u t i o ns e t ，c o n f l i c ts o l u t i o ns e te t c ， o nw h i c ht h ei n t e r r e l a t i o na m o n gt h eo b j e c t i v ef u n c t i o n sa n dt h eo r d e r i n g r e l a t i o na m o n gt h er e f e r e n c es o l u t i o n s c a nb ef i x e d a t t r i b u t er e d u c t i o nb a s e d a p p r o a c h t od e t e r m i n ec o i o b j e c t i v e f u n c t i o n si n m u l t i p l eo b j e c t i v e 0 d t i m i z a t i o n sp r o v i d e sd e c i s i o nm a k e r w i t hr e l i a b l ed e c i s i o ni n f o r m a t i o n - k e y w o r d s ：r o u g hs e t ，l o w e ra n du p p e ra p p r o x i m a t eo p e r a t o r , d i s t r i b u t i v e b z l a t t i c e ， p a r e mc l a s s i f i c a t i o n 。p o s s i b l em e a s u r e ，n e c e s s a r y m e a s u r e ，c o n s t r a i n td e f e e ， m u l t i o b j e c t i v eo p f i m i z a t m i l c o n f l i c ta n a l y s i s 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均己在论文中做了明确的说明并表示了谢意 本人签名：堑q 查丝 日期：童翌兰：竺：! ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部 分内容，可以允许采用影印、缩印或其他复制手段保存论文( 保密的论文在解密 本人签名：塑! 堑 导师签名：耋：l 至! ! 日期：翌兰! 三：兰! 日期：缈三：! ：! 笙。 一璺二里! ! 重量堡鱼塑望 ! 第一章引言与预备知识 粗糙集 o u 曲s e t s ，简称r s ) 理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的处理 不精确、不确定数据的一种新的数据分析理论，已被广泛应用于人工智能、模式识 别与智能信息处理等计算机领域近年来，粗糙集理论已成为信息科学最为活跃的 研究领域之一粗糙集的理论和方法与其他数据分析方法，诸如。统计学，聚类分析，模 糊集，证据理论等有某些重叠的部分，但它也是一门独立的学科粗糙集方法对于人 工智能、认知科学、机器学习、知识获取、决策分析、模式识别，以及从数据库、 专家系统和归纳推理申发现知识都是重要的方法，尤其对于研究开发决策支持系统 和数据挖掘特别有用本章前两节将阐述粗糙集理论产生的背景和研究现状以及有 关粗糙集的基本概念，最后一节概述了本文的主要工作 1 1 粗糙集理论的背景及研究现状 1 1 1 粗糙集概念提出的背景 早在1 9 0 4 年，谓词逻辑的创始人g f r e g e 就提出了含糊( 德文v a g u e ) - - 词，并把 它归结到边界线区域，即在论域上存在这样的个体对象，它既属于某个子集，也不 属于该子集的补集不少理论计算机科学家和逻辑学家以l a z a d e h 提出的模糊集 概念为工具，试图解决g f r e g e 提出的含糊概念，但由于模糊集并没有给出描述含 糊概念的数学公式，因而无法计算边界区域上的具体含糊元素的数目二十世纪 八十年代初，z p a w l a k 针对g f r e g e 提出的边界区域思想提出了r o u g h 集概念，他建 立了上、下近似集的概念，而把上近似集与下近似集之差定义为边界区域，把无法 确认的个体都归属于边界区域由于上、下近似集可以通过等价关系( 或二元关系) 给出清晰的数学公式表示，因此，边界区域的元素的含糊程度可以计算从而实现了 g f r e g e 的边界区域思想 t 1 2 粗糙集理论及应用的研究现状 自z p a w l a k 提出租糙集概念以来，一些理论工作者相继发表了粗糙集代数、 粗糙集拓扑及其性质、粗糙逻辑及处理近似推理的逻辑工具等方面的论文关于粗 糙集与模糊集、证据理论、概率逻辑、模态逻辑之间的关系的论文也有不少近年 来人们把粗糙集理论应用于多准则决策分析，s o r e c o b m a t a r a z z o ，r s l o w i n s k i 系 统地综述了基于各种关系的粗糖集理论及其在多准则决策方面的应用 1 - 3 i ，取得了 西安电子科技大学博士学位论文：租糙集理论及其在多目标优化中的应用 理想的决策效果， 知识的表示与管理一直是当今人工智能领域的热点研究课题，而人工智能最 早的表示模式大都采用逻辑形式来表示，特别是模态逻辑倍受人们的关注由于 模态逻辑中添加了“必然”和“可能”两种算子，这给命题演算提供了恰当的非 真值系统，使得模态逻辑从纯粹逻辑走向了应用领域尽管用模态逻辑表示知识模 式有很多优点，如证明过程的推理规则有效，具有很好的理解形式语义的能力，但 它的一个致命弱点是表示和处理功能的分离，因此，如何用可操作的方法来处理 以逻辑形式表示的数据一直是人们探讨的热点近年来研究者们利用粗糙集的近 似计算和模态算子的相似性，对粗糙集进行了研究如，商琳和陈世福证明了近似 算子、模态算子与关系运算的等价性，并从关系运算角度给出了模态算子与近似集 计算的方法【4 】为了解决g f r e g e 提出的边界区域上的元素计算问题，p a w l a k 提出 了一种粗糙逻辑和基于决策表的决策逻辑，前者建立了五个真值：真、假、粗糙 真、粗糙假和粗糙不一致；后者是基于决策表定义的逻辑，它实质上是经典二值 逻辑的特殊情况此后，许多研究者提出了各种粗糙逻辑系统，它们的工作极大地 促进了人们对逻辑学的应用研究值得一提的是：刘清对模态逻辑中的文与粗糙 逻辑作了比较，揭示了s ；与由等价关系引出的粗糙逻辑的等价性，这个结果为经 典逻辑在近似推理中的应用提供了基础( 或依据) 1 2 ”后来，刘清又以邻域拓扑内点 和邻域拓扑闭包为逻辑算子，定义了一种基于邻域信息表的邻域逻辑系统1 5 l ，这种 逻辑系统可用于专家系统中的近似推理，也有助于开发新的决策系统 关于粗糙集的测度问题也受到人们的重视2 0 0 0 年，于剑和程乾生研究了粗糙 集与不可测集的关系，指出粗糙集就是测度论中的不可测集，一个集合的可测程 度就是粗糙集的精度 6 1 2 0 0 1 年，张仕念和刘文奇研究了可测空间与p a w l a k 代数的 关系进一步推广了于剑和程乾生的结果1 7 j 1 9 8 5 年p a w l a k 考虑到不精确性和不确定性环境中总伴随着粗糙性与模糊性， 研究了模糊集与粗糙集的关系1 9 9 0 年，d u b o i s d 和p r a d e ，h 提出了模糊粗糙集和 粗糙模糊集的概念【8 】1 9 9 8 年，d o g a n c o k e r 证明了模糊粗糙集就是直觉l - 模糊集【9 j 1 9 9 8 年。n e h a d n m o r s i 和m m y a k o u t 给出了模糊粗糙集公理【f o j ，模糊集与粗糙集 的有机结合进一步扩展了粗糙集的应用前景 在粗糙集理论中，属性的约简是一个非常重要的课题，z i a r k o 已经证明求解决 策表的所有属性约简是n p h a r d 问题，最小属性约简也是n p - h a r d 问题i l l j 对于大 系统而言，如果能删除冗余属性，则可以大大提高系统潜在知识的清晰度，计算属 性约简有助于提取信息系统的规则，实现数据挖掘的目的根据有无决策属性，把 属性约简分为绝对约简和相对约简对于相对约简已有许多方法，但对于绝对约简 的研究还不多见维锦、叶东毅等利用概念格的h a s s e 图与粗糙集中属性导出的不 可分辨关系之间存在的对应关系，给出了基于概念格的计算信息表中所有绝对约 第一章引言与预各知识 简的算法，并通过理论分析和实例计算验证了算法的正确性和有效性f 1 2 】 粗糙集理论的生命力在于它有较强的实用性，从1 9 9 3 年得到国际承认至今虽 然只有短短十来年时间，但它在许多领域得到了成功的应用，如，模式识别、灾害 预报、冲突分析、数据发掘、工业控制、医疗诊断、专家系统、人工神经网络、决 策分析、机械故障诊断、材料科学、财政预算、股市分析等领域近年来，又出现 了粗糙集的新的应用领域，如：粗糙控制、信号和图像处理、粗糙数据库、粗糙信 息查询、粗糙神经网络等 1 1 3 褪糙集与其他软计算方法相结合的应用前景广阔 粗糙集是数据发掘的有效工具，具有坚实的理论基础和广泛的应用背景近 年来，粗糙集与其他软计算方法的结合，使得粗糙集的数据发掘能力得到进一步提 高目前，由挪威科技大学计算机与信息科学系和波兰华沙大学数学研究所合作开 发的一个基于粗糙集理论的r o s e t t a 表列数据( t a b u l a rd a t a ) 分析工具包已经成功地 用于空间数据挖掘，它能较好地处理决策表属性值遗漏的问题 1 3 1 粗糙集与神经网络、遗传算法、模糊数学的结合越来越得到重视其中粗糙集 与神经网络的结合已经成为研究的热点粗糙集的优势在于： 1 ) 能够搜索数据的最小集合； 2 ) 评价数据的重要性； 3 ) 允许同时使用定性和定量的数据； 4 ) 从数据中产生决策规则集合 神经网络的最大特点之一就是无需实现函数表达而完成并行处理，且有容错和 抗干扰能力人们用并行算法成功实现了粗糙集理论的知识约简，取得了良好的效 果1 9 9 8 年，l i n g r a s 用一个粗糙神经元来代替传统神经网络中的一个神经元，提出了 粗糙神经网络理论 1 4 , 1 5 1 2 0 0 1 年，张兆礼、孙圣和提出了粗糙神经网络结构的概念， 并给出了基于粗糙神经网络的数据融合模型 1 6 1 同年，梅晓丹、孙圣和又给出了其性 能明显优于遗传算法的粗糙神经网络禁止搜索算法【1 7 】郝丽娜博士研究了粗糙集 一神经网络智能混合系统及其工程应用，并把粗糙神经网络系统用于故障诊断中i l ”， 这些工作是粗糙集与神经网络成功结合的初步结果，它必将为软计算提供更为有效 的算法 神经网络、专家系统和粗糙集不仅各具特色，而且又有许多共同之处，三者的有 机结合必将给智能信息处理带来新的生机 粗分析和信息论的结合也是一个研究热点有的学者利用信息论的熵原理构造 所谓的t 粗熵”，用来度量知识的粒度或评价属性的重要性跚苗夺谦等1 唧证明了 知识约简在信息和代数两种表示下是等价的在信息表示下不仅知识比较容易理 解，而且粗分析比较容易实现高效的约简算法根据粗糙集理论可知：知识是有粒度 的由知识粗糙性定义的偏序“较细”是单调下降的【们 西安电子科技大学博士学位论文：粗糙集理论及其在多目标优化中的应用 综上所述，粗糙集理论是处理不确定和不精确数据的一种新方法，是计算机 科学和信息科学研究的新领域 本文将研究分配b z 格上的粗糙集代数以及粗糙集理论在多目标优化中的应 用后面两节分别概述与本文有关的基础知识和本文的主要工作 1 2 与本文有关的粗糙集理论的基础知识 1 2 1 有关粗糙集的基本概念 设u 是我们感兴趣的对象组成的有限集合，称为论域任意一个子集 x u ，称为u 中的一个概念或范畴u 中的任何概念族称为关于u 的知识利用对 u 能形成划分的那些知识定义u 的一个划分3 = ( x l ，x 2 ，以) ，z u ，z ， 对于i ，一i ，= 1 , 2 ，”；u = u u 中的一族划分称为关于u 的知识库 i i l 设月是u 上的一个等价关系，由等价关系r 把论域u 划分为不相交子集，对u 的这种划分称为由r 所诱导的商集，记为u r ，表示由r 的所有等价类构成的集 合 z 】。表示u 中根据关系r 确定的与x 能划分在一类的对象的集合，称为工的等价 类如果u 中的两个元素x , y 属于相同的等价类，则称x , y 是不可分辨的元素由于任 意一个集合譬u ，可以不必是某些等价类之并，因此，利用r 的等价类不一定可以 精确地描述在这种情况下，人们用r 的一对下近似集和上近似集来刻画z 1 2 1 1 粗糙近似空间 定义1 2 1 i a g 设u 是一个非空有限论域，对u 的任意一个非空子集x u 和 u 上的任意等价关系矗，定义x ( 目标集合) 关于r 的下近似集和上近似集分别为 r ( j ) = 缸u j 【x 】月x ) = u f x kj 【加月x ) r ( z ) = x u | 【x 】r n y 妒 = u 【x 】月f x x ) ( 1 - 1 ) ( 1 - 2 ) 称p o s 。( x ) = r ( x ) 为z 的r 正域，它包含根据r 的知识判定肯定属于的 u 中元素组成的集合；称月e g 。( ) = u r ( z ) 为x 关于r 的负域，它包含根据r 知 识判定肯定不属于x 的u 中元素组成的集合r ( x ) 是包含根据r 的知识判定可 能属于x 的u 中元素组成的集合定义砌。( x ) = r ( x ) 一r 。( x ) 为x 关于r 的边 界域 二元组( u ，只) 构成一个近似空间，称r ( 石) = ( 见( x ) ，月( ) ) 为x 在近似空间 ( u ，r ) 中的粗糙集r 为u 上的不分明关系，用【z 】。表示u 中根据关系r 确定的与 x 不可分辩的对象的集合，称为x 的不可分辩类，其中x u 为u 中的一个对象 在粗糙集理论中，每一个不精确概念都可由一对称之为下近似集与上近似集的 第一章引言与预备知识 精确概念来描述这里的集合以概率推断为定量依据，并与d e m p s t e r - s c h a f e r 理论中 的似然函数相等价下近似集与d e m p s t e r - s c h a f e r 理论中的证据函数相等价从语义 角度讲，上近似集的范围比目标集合的定义范围要大，而下近似集的范围比目标集 合的定义范围要小，在此空间中的集合族均属于粗糙集在这个意义下，上、下近似 集合分别是该空间的两个极限情形 1 2 1 2 粗糙近似算子的基本性质 下列是粗糙集近似算子的基本性质： 1 ) r 。( x ) 工尺( x ) ；r ( ) = u r ( u x ) ，【1 - 3 ) 2 ) r ( 矿) = r ( 妒) = ，r 。( u ) = r ( u ) = u ，( 1 - 4 ) 3 ) y j r ( x ) r 。( 】，) ，r ( x ) r ( y ) ，( i - 5 ) 4 ) 见( 爿u 1 0 2 r ( z ) i j r 。( ，) ，r ( x u y ) = r ( z ) t 3 r ( r ) ，( 1 6 ) 5 ) 见( n 1 0 = r 。( x ) n r ( n ，r ( x ny ) r ( x ) i - 1 r ( y ) ， ( 1 - 7 ) 6 ) r ( x ) = r + ( x ) ，r ( x ) = r 。( x ) ( 1 8 ) 1 2 2 有关粗糙集理论的几个基本问题 1 2 2 1 信息系统 信息系统也称为数据表，下面我们介绍相关概念 定义1 2 2 f 1 1 一个信息系统可用s = ( u ，a ，v ，力来表示，其中u 是被描述的对 象的有限非空集，爿是属性的有限非空集矿= u 圪为属性值的集合一个信息 函数厂：u a v ，它将属性的值分配到信息表中各行相应的属性中如果 垤，u ，都有确定的属性值厂，q ) 与之对应( j qe a ) ，则称s 是一个完全信 息表，否则称为不完全信息表 粗糙集理论中，知识是对数据表中数据间关系的描述，人们通常定义知识为对 事物的分类能力这种能力由上近似集、下近似集、等价关系等概念来体现因为粗 糙集处理的对象是类似= 维关系的信息表( 决策表) ，目前成熟的关系数据库管理系 统和新发展起来的数据仓库管理系统，为粗糙集的数据开采奠定了坚实的基础 1 2 2 2 粗糙近似的精度和质量 1 ) 近似精度对于一个粗糙集z u ，我们可以利用属性爿定义 x 的近似精度为： 州耻嚣揣 ( 1 - ，) 堕安电子科技大学博士学位论文：魍糙集理论及其在多目标优化中的应用 显然0 口( x ) l ；如果口( x ) = 1 ，则关于一是一个普通集：如果 a 一( x ) o ( 1 r ( f ，) 0 ) ：f ，j 是互补的， i m s ( i , j ) ( 0 ( 如( f ，_ ，) _ ，则称在区别 c 。类与其他类时属性f 比属性_ ，重要； 耍安电子科技大学博士学位论文：粗糙集理论及其在多目标优化中的应用 若，m ( f ，力 o ，则称在区分q 类与其他类时属性f 和属性，是互补的： 若，。( f ，) = o ，则称在区分c 。类与其他类时属性f 和属性，是独立的 由上述描述可知：反映重要性的指标s h a p l e y 值和反映相互作用指标l 。( f ，) 可以作为评价属性的两个度量指数这两个度量指标提供了有关单个属性对于某 个分类的重要性和属性之间两两相互依赖的信息，也能反映两个属性在一起时对 于分类是否是相互补充的，还是多余的基于对这两个度量指标的上述解释，从给 定的属性集合中选择最为合适的属性子集是能够实现的如何完成属性的选取， 人们提出了属性约简的方法 1 2 2 ，4 二元决策表的矩阵表示 给定一个决策表d t = ，如表( 1 3 ) 所示a 是属性集，假定对 “中的属性已按某种方式作了排序在表( 1 3 ) 中，q ，42 一，口。a ，m = c a r d ( a ) 于 是每个对象一的属性值可用一个向量( v 。v 。，v 。) ，( i = 1 , 2 ，n ) 来表示，可记为 x ov 1 a 1 + v i 2 a 2 + + 口。( 1 - 2 2 ) 称( ，v ，v 。) 为对象x i 关于属性( a l ，a 2 ，a 。) 的坐标向量 表 ( 1 3 ) 条件属性( 4 ) 决策属性 对象( x ) d 口2 d “ d 而 v l i v 1 2v l ”d l 工21 2 1v 2 2 。v 2 md 2 ： ： x nv mv n2v md 。 ( 这里( a ，啦，d 。) 表示属性向量组) 于是，对上述信息表( u ，a ，v ，力可以形式地表示为 工l 工2 ： x ” e f 1 2 v 2 1v 2 2 l v n 2 v n h q d 2 ： 口” 其决策表d t = 也可以形式地表示为 ( 1 2 3 ) 一一一苎= 妻! ! 童兰堡鱼垫塑 ! ! 睡引 口1 日2 ： d m 在给定论域u 中对象的属性集爿= ( 口。，口： 巧 v 1 2 v 2 2 v 1 月 v 2 月 d 1 1 d ，| ：。( 1 - 2 4 ) d ，3 ，a m ) 7 时，称矩阵 为信息系统s = ( u ，a ，v ，厂) 的属性值矩阵，称 r 】一2 5 ) d = ( d l ，d 2 ，d 。) 。( 1 - 2 6 ) 为s 的决策矩阵 上述信息表的矩阵形式与向量空间中的向量表示相似给定一个子空间的一组 基向量，则该空间中的每一个向量都可以有惟一的线性表示，一个子空间可以存在 不同的等价的基向量在信息表中给定一组属性( 特征) 就相当于确定了一组基向量 对于决策表的属性约简就相当于求组基向量 显然，当对象x ，变更时，即当我们更新数据表中记录时。其属性值矩阵和决 策矩阵都将改变事实上，用( 1 2 4 ) 表示的信息系统决策表也可以视为一个信息的 “输入输出”关系，这种关系蕴涵着决策规则当我们输入对象的属性值矩阵 时，一定会得到相应的对象的有关决策信息的输出，这个处理过程就是决策过程 因此，决策系统的决策规则也可以用逻辑系统中的产生式规则来表示： 如果n = a 。，则d = d 里塑匕三生： ：f 1 - 2 7 ) 求d = 7 1 2 2 5 属性约简与核 粗糙集是一种刻画不完整性和不确定性的数学工具，能有效地分析和处埋小 精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规 律粗糙集方法模拟人类的抽象逻辑思维它基于不可分辨性的思想和知识约简的 方法，从数据中推导逻辑规则作为知识系统模型，可以输入定性、定量或混合性信 息：定义条件属性和决策属性间的依赖关系，即输入空间与输出空间的映射关系是 通过简单的决策表约简而得到的人们通过去掉冗余属性可以大大简化知识的表 达空间维数，可以描绘知识表达中不同属性的重要性进行知识表达空间约简，从 样本数据中获得推理规则 下面我们先叙述属性约简和核的概念，再提供属性约简的计算方法 1 ) 属性约简与核的概念1 1 ，1 9 】 在信息系统s = ( u ，a ，矿，) 中，每一个属性子集p a 都可以决定一个二元不 可分辩关系i n d ( p ) ： i n d ( p ) = ( x ，y ) u x u fv a a ，f ( x ，a ) = 厂( j ，口) ( 1 2 8 ) 显然1 n d ( p ) 是论域u 上的等价关系，且有 ( 1 ) i n d ( p ) = n 肌d ( 口) ) ； 口e ， ( 2 ) 若p ，g a ，p 9 ，月j j n d ( q ) 1 n d ( p ) 定义1 2 3 i , 1 9 设s = ( u ，a ，v ，厂) 是一个信息系统，口a ，如果i n d ( a 一 口) ) = i n d ( a ) ，则称属性a 在彳中是不必要的( 多余的) ，否则，称口在彳是必要的如 果每一个属性a a 在a 中都是必要的，则称a 是独立的，否则，称a 是相依的 定义1 2 4 i , 1 9 1 k s = ( 【，a ，v ，力是一个信息系统，p a ，称尸是a 的一个 约简，如果尸满足： ( 1 ) i n d ( p ) = i n d ( a ) ；( 2 ) p 是独立的 一般地，一个信息系统可能存在多个相对属性约简，我们称所有属性约简的 交集为爿的核。记作c o r e ( a ) 一个信息系统属性约简的核是惟一的对于相依的属 性集，可以通过约简来去掉多余的属性核的用处有两方面：首先它可作为所有约 简的计算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次可解释 为在属性约简时它是不能消去的属性特征的集合 2 ) 属性约简的计算 设s = ( u ，a ，v ，f ) 是一个信息系统，a = a ，0 2 c d 。) 是有序的月个属性，所谓 属性约简，就是在保持对系统分辨能力不变的条件下，去除不必要的冗余属性， 这有助于决策者从系统中提取有关对象的本质特征 根据属性约简的概念，可设计下列属性约简算法： 假定集合e 是存放系统必要属性的则 第一步：置e = 矿； 第二步：从a 去掉属性q ，计算r ( a 一 a i ) ) ，并判断r ( a 一 a t ) = r ( a ) 是否成 立? ，若成立，则置e = a ) ； 第三步：继续从爿去掉属性口：，求r ( a 一溉，口2 ) ) ，并判断y ( 爿一“，a ： ) = ，( 爿) 是 否成立? ，若不成立，则将属性a 2 放回4 中； 连续重复上述第二步和第三步，则最后得到的集合a e 就是最小属性约简 1 2 2 6 极大必要属性组与最小属性约简 第一章引言与预备知识 对于给定的信息决策表，为了迅速、准确地将对象进行分类，首先应进行属 性的约简下面先提出信息表中极大必要属性组的概念： 定义1 2 5 设d t = 是一个决策信息系统，假定通过属性约 简得到的最小属性集为a 5 = 口( 1 ) ，口( 2 ) ，口( 曲) ，称( 口( 1 ) ，口( 2 ) ，o ) 为信息系统 s = 的一个极大必要属性组 粗糙集中的属性约简相当于线性空间中寻求一组向量的基向量组显然信息表 s 中每个对象x 都可由s 的一个极大属性组表示，相应地，称u 的对象的属性值矩 阵为s 的最小属性约简矩阵在这个意义下，属性的最小约简过程就相当于属性值 矩阵约简为最小属性约简矩阵 “约简”和“核”是粗糙集中很重要的两个概念由于决策表中每一个对象都 蕴涵着一条分类规则，因此决策表又可以看