（计算机应用技术专业论文）基于模糊粗糙集的降维算法研究.pdf

摘要 近年来，信息技术的广泛应用使企业采集到的数据以前所未有的 速度增长。但是海量数据采集后并未得到充分的应用和开发，信息含 量高、内容丰富的数据库成为无人问津的数据坟墓，造成资源的极大 浪费。知识处理技术的兴起与迅速发展。使海量数据的实际应用成为 可能。然而，数据维数过大严重地影响了规则和案例的提取以及基于 知识推理系统的响应速度和并发用户数。 模糊粗糙集理论是解决数据集维数问题的有效工具，但基于模糊 粗糙集的降维算法还不多。本篇论文首先系统地总结了模糊粗糙集的 研究成果及发展趋势，根据模糊粗糙近似推演方式的不同，主要形成 了三种从不同角度研究的模糊粗糙集。论文对属性模糊化的方法进行 了研究，给出了单个属性和复合属性模糊化的般方法。通过比较国 内外在粗糙集和模糊粗糙降维思想与算法，提出了三种模糊粗糙降维 算法：属性递减约简算法，基于遗传算法的约简算法以及约简树算法。 属性递减约简算法计算复杂性较低，基于遗传算法的约简性能出色， 而约简树算法能够找到最小约简，并且不需要对解空间进行完全搜 索。 铁路货票中包含大量客户及铁路运输相关信息，通过分析研究， 结合铁路货运营销专家的经验，综合利用提出的算法对广铁集团的货 票数据库进行了降维处理，显著地降低了数据的维数，提取出了影响 客户选择铁路运输的因素，从而为广铁集团货运营销分析系统的开发 提供了良好基础。 关键词模糊粗糙集，铁路货票，属性递减约简，遗传算法约简，约简 树算法 a b s t r a c t i nr e c e n t y e a r s ， d a t a g a t h e r e db ye n t e r p “s e s i n c r e a s e r a p i d l y b e c a u s eo fw i d eu s eo fi n f o f m a t i o nt e c h n o l o g y ，b u tl a r g ev o l u m e so f d a t aa r en o tf h n yu s e da n de x p l o i t e da f t e rb e i n gc o l l e c t e d ，a n dd a t a b a s e s w h i c ha r ef h uo fu s e f h li n f o m a t i o nb e c o m ed a t at o m b st h a tn ob o d y c a nm a k eu s eo f w h i c hi sa ne n o m o u sw a s t eo fr e s o u r c e ，t h er j s ea n d r a p i dd e v e l o p m e n t o ft e c h n o l o g yo fl ( n o w l e d g e e n g i n e e r i n g m a k e s d r a w i n g u s e f u li n f o 啪a t i o n 疗d ml a r g ev 0 1 u m ed a t a p o s s i b i e b u tt h eh i g h d i m e n s i o no fd a t as t i l lr e m a i n sa sab i go b s t a c l ef o rd e d u c i n gm l e sa i l d g e n e r a t i n gc a s e s ，a n d u s e r sm u s tw a i t1 0 n gf o rao u t p u ta i l dt h en u m b e ro f u s e r 小a tc a nw o r kc o n c u r r e m l yi sl i l n i t e d f u z z yr o u g hs e t 也e o r yi s a ne 丑1 e c t i v et o o lf o rr e d u c t i o no fd a t a d i m e n s i o n ，b u tt h e r e a r ef e wd i m e n s i o nr e d u c t i o na l g o “t l l m st h a ta r e b a s e do n f h z z ym u g hs e tt h e o r y s of a r h lt h i s a r t i c l e ，t l i e a u t h o r s y s t e m a t i c a i l ys u m m a r i z e sc u 盯e n tr e s e a r c ha n dt e n d e n c yo ff i l z z yr o u g h s e h e o 哆b e c a u s e 硪f 轴e n m e t h o 出a r eu s e d od e d u c em 冱ym u 曲 a p p r o x i m a t i o n s ，血e r ea r em a i n l yt h r e ek i n d so ff u z z yr o u g hs e t s t h e a u t h o ra l s oe x a m i n et h em e t h o dt o 向z z 匆a t t 抽u t e si n 如z z yr o u 曲s e t a n dp r e s e n tg e n e r a lm e t h o dt o m z z 匆s i n g l ea t t r i b u t e 锄dc o m p o s i t e a t t r i b u t e s 触e ra i l a l y z i n gm a n yd i m e n s i o nr e d u c t i o na l g o r i t h mb a s e do n r o u g h s e t a n d 向z z yr o u g h s e t t h e o r y ，t h e a u t h o rp u t sf o n v a r dt 1 1 r e e e a e c t i v e a l g o r i t h m b a s e do n f l l z 珂r o u g h s e t m e o r y ： d e c r e a s e r ，g u 己e d u c t o ra n dt r e e j 己e “c t o r t h ed e c r e a s e ra l g o r i t h m h a sag o o dc o m p u t i n gc o m l e x i t yt h eg a 上e d u c t o rp e r f o 咖a n c ew e l l ， a i l dt h et r e e r e d u c t o rg u a r a n t e et 1 1 a tm em i n i m a lr e d u c tw i l lb ef i n d w i t h o u te x a m i n n ga l l p o s s i b l e s l l b s e to ft h es e to fa l lc o n d i t i o n a l i i a 嘶b u t e s r a i l w a yi n v o i c e sc o n t a i n sl o t so fi n f o m a t i o na b o u tc u s t o m e r s 蛐d r a 订w a yt r a n s p o r t a t i o n a f t e rc a r e f u la n a l y s i sa n dc o n f i e 州n gw i t he x p e r t s o nr a i l w a yt r a n s p o r t a t i o n ，t h ea u t h o rc o m b i n e sa b o v e a i g o r i m m s t or e d u c e t h ed i m e n s i o no fd a t ai ni n v o i c ed a t a b a s eo fg u a n g z h o u r a i l w a v g r o u p t h ee a e c ti sc o n s i d e r a b l e a n d t h ea t 仃i b u t e st l l a ta f f b c tc u s t o m e r s c h o i c eo f t r a n s p o n a t i o na r ef b l u l ds oas o l i df b u n d a t i o nf o rd e v e l o p m e n t o f g u a n g z h o ur a i l w a yg r o 叩i n v o i c ea j l a l y s i ss y s t e mi sb u 讹 k e y w o r d s 他z yr o u 曲s e t ，r a i l w a yi n v o i c e ，a 删b u t e sd e s c e n d i n g r e d u c t i o n ，g e n e t i ca l g o r i t h m - b a s e dr e d u c t i o n ，r e d u c t i o n 打e ea l g o r i t l l i i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名- 磊5 生羔日期：羔竺红妇暨日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅：学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 储签毖车髅名型幽吼型年上月互日 硕上学位论文第一章绪论 1 1 问题的提出 第一章绪论 粗糙集( r 叫g hs e t ) 理论1 8 l 是波兰数学家z p a w l a k 于1 9 8 2 年提出的，它 具有很强的定性分析能力，可以直接从给定问题的描述集合出发，通过不可分辨 关系和不可分辨类确定给定问题的近似域，从而得到该问题的内在规律。目前， 粗糙集理论与神经网络、模糊理论、专家系统、证据理论等理论相结合，已被应 用于知识获取、数据挖掘、信息融合、决策分析和决策支持、模式识别、机器学 习、故障诊断和控制算法获取等各种领域。 粗糙集的一个重要应用是对信息系统进行降维处理( 习惯上称为约简) 。信 息系统降维包括值约简和属性约简( 也称特征选择) 。信息系统中，重复的记录( 两 条或两条以上的记录除记录编号以外的属性取值都相等) 不但不能为推理提供新 的规刚和经验，记录的大量重复反而影晌系统运行效率，值约简就是在保证信息 系统的总规则数( 互不相同的记录数) 不变的条件下删除这些重复记录的过程。 所谓属性约简，就是在保持信息系统分类能力不变的前提下，利用一系列变换过 程，得到信息系统的条件属性集合的一个最小子集。一般认为，获取的数据越充 分，对事物的性质或状态的判断就越准确。然而，获取充分的数据往往需要更多 的b 寸阐或者更多的金钱，面且有时是不可能的，这就需要从属性全集中找出具有 与其相同的确定事物性质或状态的能力且属性数目尽可能少的属性子集。这一过 程就是信息系统属性约简过程，得到的属性子集称为原属性集的约简。 粗糙集理论对离散的数据集合的降维处理十分适用，国内外学者在这方面做 出了大量的研究，并取得了一定成果。然而，利用粗糙集理论进行降维处理之前， 必须对连续属性进行离散化，这一过程将造成某种程度的信息损失，因为离散化 后的属性值没有保留属性值在实数值上存在的差异。 法国学者d d u b o i s 和 lp r a d e 于1 9 9 2 年提出的模糊粗糙集就是为了解决 粗糙集的离散化过程的信息损失问题。他们将模糊集理论引入粗糙集中，对信息 系统中的对象不蒋进行离散化，而讨论对象间的关系时也用对象的相似关系而非 粗糙集中的等价关系。正是由于模糊粗糙集理论引入的模糊概念易于保留连续属 性值的信息，因此使用该理论处理数据集更能保留原始数据集所包含的信息。已 有学者研究表明3 6 1 ，应用模糊粗糙集得到的模糊规则或基于案例的推理系统以 及原始数据集的约简比粗糙集具有更高的准确度。 近十年来，国内外学者对模糊粗糙集的基本特征和基本理论进行了有益的研 硕 ：学位论文第一章绪论 究，并且取得了一定的应用成果。然而，当前的研究主要集中于从不同的角度考 察模糊粗糙集的性质，至于基于模糊粗糙集的降维算法，由于与粗糙集降维相比 的特殊性和引入模糊集后导致的计算复杂性，现在的研究成果还不多。 幕于模糊粗糙集的降维算法研究对于更完整地保留原始数据的知识和信息 以提高在知识获取、数据挖掘、决策分析和决策支持、模式识别、机器学习等领 域中数据约简的准确性具有重要的意义。 1 2 国内外研究现状 121 国内研究现状【”4 j 在粗糙集和模糊粗糙集的研究方面，国内起步较晚，但经过近十年的努力， 也取得了一定的理论和应用成果。在连续属性离散化方面，苗夺谦利用决策表榴 容性的反馈信息，提出了一种领域独立的基于动态层次聚类的连续属性离散化方 法：权光曰、刘文远等将信息熵与无穷范数的概念应用到连续属性离散化问题， 提出了基于信息熵的属性空间极小化算法；另外，张飞弓和叶东毅也对此问题进 行了研究。在粗糙集的基本性质与基本定义的研究方面，刘健勤通过把粗糙集和 进化计算理论相结合，构造出了进化粗糙集。梁吉业、徐宗本等通过将包含度概 念引入到粗糙集理论中，建立了包含度与粗糙集数据分析中的度量之间的关系， 证实了粗糙集数据分析中的有关度量均可归结为包含度。范世栋、支天云给出了 粗糙集的粗糙并、交、补的定义，并从多方面研究了粗糙集的代数性质。浙江海 洋学院的徐优红在定义了基于随机集的粗糙近似算子的基础上讨论了随机集、粗 糙近似算子与可能性测度的关系。在粗糙集知识表示方面，苗夺谦证明了知识约 简的信息熵表示和代数表示的等价关系，为寻找高效的知识约简算法奠定了基 础。 国内当前对模糊粗糙集的研究还不多。吴伟志和张文修给出了模糊粗糙集的 些性质并进行了证明；程日失给出了模糊粗糙集的分解定理及表现定理以及粗 糙模糊数的概念；王玲芝对模糊粗糙集的距离贴近度、最小最大贴近度进行了研 究。 国内在属性约简研究方面虽然起步较晚，但也提出了一些有新意的方法。王 文辉提出了一个粗糙集知识约简算法，它从系统的信息表出发，根据可辨别关系 的下三角矩阵，利用遗传算法搜索基于粗糙集的最小约简，但作者未能对该算法 的正确性给出严格的验证。叶东毅提出了一个j e l o n e k 属性约简算法的改进版 本，它利用单属性的近似精度和h u 的差别矩阵方法，求解出一个较优的属性约 简，使得计算复杂性下降到o ( n 2 m 2 ) ，其中n 为数据集中对象数，m 为属性数。潘 丹结合属陛约简判定的完备算法和属性约简算法，设计了一个能以较大概率找到 硕士学位论文第一章绪论 最小约简的算法，该算法也是基于差别矩阵的。刘宗田提出了一个在增加数据库 记录后，能够在已有最小属性约简的基础上求解新的最小属性约简的算法，该算 法同样基于记录问的不可区分关系。 l 2 2 国外研究现状i j ”1 国外当前对属性约简的研究主要集中在粗糙集属性约简方面，研究的两个主 要思路是枚举搜索和利用启发式信息。枚举搜索计算量大，但能保证找到最小约 简；启发式搜索能显著降低计算量，但却不能保证找到最小约简，通常找到的是 一个次优解。关于属性约简的算法很多，这里仅介绍其中有代表性的几种。 在枚举搜索算法中。p 0 1 k o w s k i 和s k o w r o n 提出了一个很有启发意义的基于 可辨识矩阵和逻辑运算的属性约简算法，它将对属性组合情况的搜索演变成了逻 辑公式的化简，思路巧妙，步骤简单，可以得到决策表中所有可能的约简结果， 但得到的逻辑表达式过多，计算量大。另外，m m o d r z e j e w s k i 提出了寻找最小 约简的宽度优先搜索算法，它首先从原始决策表中删除一个属性，得到所有可能 的包含n 1 个条件属性的子决策表，然后再反复地再这些子决策表上进行上述操 作，最终就可以得到所有可能的属性约简结果。同时，他对深度优先算法也进行 了探讨。但不幸的是，由于这是一个组合爆炸问题，穷尽的搜索所需要的时间和 空间代价很高，实际计算约简的时候，往往采用某种启发式的算法。 启发式算法中有代表性的是t y l i n 和r c h e n 的归纳属性约简算法，它首 先求得决策表的属性核，试图以属性核为基础来求决策表的最小属性约简。实质 上。这种算法还是一种对属性组合的搜索，只是采用了启发式知识减小搜索空间。 因为属性核是肯定在约简结果中的，所以首先得到属性核，这样就避免了对核属 性之间的组合情况的搜索。r b a t t i t i 提出了一种基于互信息的属性约简算法 m i b a r k 算法，它也是从属性核出发，每次从剩余的条件属性集合中选择一个 对决策属性的互信息最大的属性添加进来，直到所得属性集合对决策属性的互信 息与条件属性全集对决策属性的互信息相同，则此属性集合即为所求。这一种方 法也不能保证得到最小约简。x i a o h u ah u 在研究决策表约简问题时，对决策表 中的属性进行度量，并提出了特征( 属性) 选择算法。该算法利用可变精度粗糙 集模型，计算所有特征的特征价值，并对特征进行排序，删除特征价值最小的特 征，重复上述过程，直至特征集合与决策类的依赖关系达到期望的程度。这种算 法能够得到一个和决策属性有很强依赖性的条件属性子集，但会有一定的信息损 失。但算法中也可以通过适当设置得到一个没有信息损失的属性子集。由于引入 模糊集后导致的算法构造与计算复杂性，以及约简思想与粗糙集约简思想的差 异，基于模糊粗糙集的属性约简的算法目前还很少。r i c h a r dj e n s e n 和q i a n g s h e n 硕： 学位论文第一章绪沦 提出了一个称为q u i c k r e d u c t 的模糊粗糙降维算法，它是基于启发式信息的，计 算复杂度不高。但它的约简性能不稳定，算法执行效果随决策表系统的具体性质 不同而差异很大。 在模糊粗糙集的研究方面国外学者主要集中在从不同的角度考察模糊粗糙 集的性质。根据模糊粗糙近似推演方式的不同，主要形成了三种从不同角度研究 的模糊粗糙集：基于形式逻辑的模糊粗糙集，基于三角模的模糊粗糙集，基于盘一 截集的模糊粗糙集。 基于形式逻辑的模糊粗糙集盼”) 9 ，4 0 1 从粗糙集概念出发，把经典( p a w l a k ) 的粗糙上下近似变换成等价的表示形式，然后分别把等价关系扩展成模糊相似关 系，把普通集合扩展成模糊集合，得到模糊粗糙近似的一般表示。 一个模糊集可以用两种方法来表示：特征函数或者分解定理。基于口一截集 的模糊粗糙集1 4 l ，4 2 ，4 3 1 就是利用模糊集的分解定理把一个模糊集或者模糊相似关 系( 也是一个模糊集) 加以分解，分解后的模糊集被表示成一族口一截集的数乘 集的并集，而模糊相似关系则表示成了一族等价关系的并集。可以利用原有的粗 糙集研究方法研究模糊集和模糊相似关系的分解表示，并在此基础上推导出粗糙 模糊集和模糊粗糙集。 基于三角模的模糊粗糙集采用的是面向算符( o p e r a t o r o r i e n t e d ) 的研究 方法，它把粗糙集和模糊粗糙集的上、下近似看作是对参考集施以某个相应的运 算而得到“l 。这种方法首先要定义一系列可以用来表示模糊集之间的交、并、 补、取反和蕴涵的模糊逻辑算符。对于模糊粗糙上、下近似，分别用一个这些算 符组合而成的运算( 一个映射) 来表示，即，对某个集合( 普通的或模糊的) 施 以相应的运算就可以得到该集合的一个上或下近似。由于定义的模糊逻辑算符 的方式不同，将产生不同类型的模糊粗糙上、下近似。 1 3 研究的实际意义 本论文的选题与完成都得益于实际应用的需要。 近年来，我国国民经济保持持续快速发展，国家继续采取拉动内需的积极财 政t ，同时外贸行业出现高速增长局面，在上述多重积极因素的带动下，交通 运；训j 业实现了良好的运行态势p 3 ”】。在三种主要运输方式中，水路货运量增长 强劲( 2 0 0 0 年增长7 。5 ，2 0 0 1 年增长8 1 ) ，公路货运增幅较快( 2 0 0 0 年增长 5 4 ，2 0 0 1 年增长5 9 ) ，铁路货运量也出现了一定的增长( 2 0 0 0 年增长4 3 6 ，2 0 0 1 年增长4 9 l ) 。然而，铁路货运量的增长落后于其他运输方式，总 体来说，铁路货运在竞争中处于不利地位。 广州铁路集团是规模较大的铁路公司，下辖羊城、海南、广深、广梅汕以及 4 硕：上学位论文第一章绪论 长沙、怀化等多家铁路公司，其一年的货运量占全国铁路货运量的十分之一强。 广铁集团所辖范围经济较为发达，然而其铁路货运形势却不容乐观。据内部统计 集团货运量1 9 9 9 年增长4 8 7 ，2 0 0 0 年增长5 4 3 ，2 0 0 1 年增长5 3 2 。虽然 集团的这一增长速度高于全国平均水平，但是却不能令人满意。这一增长速度仍 然低于其他运输方式的平均增长速度；它明显落后于国民经济7 8 的增长率， 而集团所辖地区的经济增长率更高出此水平：经过四次提速，铁路货运能力有较 大的增强，已完全改变了过去的供不应求的局面，货运量增长缓慢导致了大量的 运力过剩。 为了充分利用集团货运能力，提高集团经济效益，同时更好地为国民经济服 务，广铁集团委托中南大学组织铁路运输、管理、经济和计算机等多个学科的力 量开发货运营销分析与决策系统。 项目目标是从货票信息中发现影响客户选择铁路运输的因素以及各因素影 响大小，以辅助营销人员制订营销策略以及为铁路货运相关制度及政策的制定提 供决策支持，此外，系统还应实现货运业务统计分析、客户管理的自动化以代替 当前的人工处理。 为了达到上述目标，该系统应具有的主要功能如下： ( 1 ) 分析影响客户的因素及其重要性； ( 2 ) 及时分析、发现客户、特别是大客户的货运量的异常变化： ( 3 ) 预测某项制度、政策的改变对货运量的影响； ( 4 ) 客户管理，包括客户增加、查询、修改及统计分析； ( 5 ) 货票统计功能。 完整的货票数据库包含1 5 4 个数据表，其中1 2 个表保存货票信息，习惯上 称为货票主库，其他的1 4 2 个表为数据字典表和辅助信息表，负责为货票制票提 供数据支持，如整车车号库b 胛w z c 帐，集装箱号库b h p w z x h k 篷布号子库 b h p w z p s k ，分局字典b h p f j z d o 等。货票主库包含的1 2 个数据表具有相同的结构， 表名形如b h $ 睨z k o ，其中幸是数字l 1 2 的1 6 迸制表示，即l c ，每个表存放对 应的月份的货票。每条货票记录字段多达1 3 8 个，其中包含了大量客户信息，货 物信息，以及铁路货运相关信息。 货票记录包含的1 3 8 个字段中，并不是每个字段都对客户选择运输工具典省 影响，同时，对客户具有影响的所有字段中，可能有部分字段能够完全决定用户 的选择，找出这部分字段有利于营销人员排除冗余属性的干扰、有针对性地改进 营销策略。另外，广州铁路集团全集团平均每月入库的货票多达3 0 万批，约占 2 0 0 m 的存储空间，货票分析系统需要用到过去五年的货票数据，共约1 8 0 0 万批 货票，容量达1 2 g 。在货票分析及货运量预测中，需要扫描大量的货票记录，货 硕士学位论文第一章绪论 票数据容量越大则扫描所需花费时间越多。因此，从提高系统效率来看，电需要 对货票数据进行约简。 本课题研究的实际意义在于： ( 1 ) 系统地总结模糊粗糙集及模糊粗糙集降维基本思想，为其它科研人员或 技术人员研究模糊粗糙集、开发新的模糊粗糙集降维算法提供重要参考； 2 ) 论文研究的模糊粗糙降维算法，可以提高降维后的决策表的信息完整性， 为知识获取、信息融合、决策分析和决策支持等应用提供更好的数据预处理： ( 3 ) 在广铁集团货运营销分析决策系统的开发中，对模糊粗糙集降维算法的 研究，有利于发现影响客户选择铁路运输的因素，降低系统的存储需求，提高系 统响应速度，减少数据备份、恢复时间。 1 4 主要研究内容 广铁集团货运营销分析决策系统的很多功能都需要对大量记录甚至整个货 票库进行扫描，数据维数过大，将导致系统存储需求大、响应速度慢、多用户并 发操作效率低、数据备份恢复时问长等缺点。同时，货票属性过多还不利于营销 人员发现影响客户选择铁路运输的因素，从而有针对性地制定营销策略。 本文的主要研究内容如下： ( 1 ) 系统地总结了模糊粗糙集基本理论与最新研究成果。 ( 2 ) 分析了粗糙集造成信息损失的原因以及模糊粗糙集降维处理中克服此缺 陷所采取的方法，研究了模糊粗糙集的属性模糊化方法，特别是复合属性模糊化 方法。 ( 3 ) 分析现有算法的优势与不足，提出了三种模糊粗糙降维算法：属性递减 约r ! 法，基于遗传算法的约简算法以及约简树算法。属性递减约简算法计算复 杂0 氐，基于遗传算法的约简性能出色，而约筒树算法能够找到最小约简，并 且不需要对解空间进行完全搜索。 ( 4 ) 分析了现有货票信息系统运行效率低下的原因并提出了改进方法。 ( 5 ) 分析了货票数据的特征，研究了货票数据约简预处理问题，包括不一致 性删除、冗余属性识别与删除、货票表补齐的方法。利用研究出的模糊粗糙降 维算法对货票数据进行了约简，并对结果进行了分析。 6 硕士学位论文第二：章粗糙集及模糊粗糙集 第二章粗糙集及模糊粗糙集 经典的粗糙集理论( p a w l a k 粗糙集) 要求处理的属性值是离散的，对于连 续的属性值，需要首先施以一离散化过程，该过程在保持数据集分类能力不变的 前提下，将连续属性区间上的值映射到有限个语言变量1 2 ，3 】。在随后的处理中， 只对这些语言变量加以考虑，不再涉及其代表的原始数据值。然而，映射到同一 语言变量的不同属性值之间是有差异的，而且不同语言变量所表示的属性值之间 电具有某种过渡性质，忽视这两种情况是粗糙集离散化过程造成信息损失的主要 原因。 为了避免粗糙集理论进行数据处理所必需的离散化过程，d u b o i s 和p r a d e 于1 9 9 2 年把模糊集引入了粗糙集，提出了模糊粗糙集理论p ”。 模糊粗糙集理论最重要的问题是在给定的论域和模糊相似关系下推演出概 念( 清晰的和模糊的) 的模糊粗糙近似。根据模糊粗糙近似推演方式的不同，主 要形成了三种从不同角度研究的模糊粗糙集：基于形式逻辑( m o d a ll o g i c ) 的 模糊粗糙集，基于三角模的模糊粗糙集，基于a 一截集的模糊粗糙集。 本章首先系统地总结了粗糙集和模糊集理论，然后通过定义一系列模糊逻辑 算符，导出模糊粗糙集的基于三角模的表示。 2 1 粗糙集合论【1 7 1 8 】 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论。由 于最初关于粗糙集理论的研究主要集中在波兰，因此当时并没有引起国际计算机 界和数学界的重视，研究地域仅局限在东欧一些国家。直到1 9 9 0 年前后，该理 论在数据的决策与分析、模式识别、机器学习与知识发现等方面的成功应用，才 逐渐引起了世界各国学者的广泛关注。1 9 9 1 年z p a w l a k 的专著r o u g hs e t s t h e r o e t i c a la s p e c t so fr 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 咖u n i c t i o n 将粗糙集列为新浮现的计算机科学 的研究课题。目前，粗糙集理论己成为信息科学最为活跃的研究领域之一。同时， 该理论还在医学、化学、材料学、地理学、管理科学、金融、故障诊断等方面得 到了成功的应用。 7 硕二l 学位论文第二章粗糙集及模糊粗糙集 2 1 1 粗糙集基本思想 设，西是感兴趣的对象组成的有限非空集合，称为论域。任何子集x u 称为u 中的一个概念。特别的，空集也是一个概念。u 中的任何概念族称为关于 u 的抽象知识，简称知识。粗糙集理论感兴趣的是那些能在u 上形成划分的知识。 对于货票集合来说，其任意子集称为一个概念。 根据运输距离对货票进行分类，可以形成不同的概念： 概念l ：运距在5 0 0 公里( 含5 0 0 公里) 以下的货票。 概念2 ：运距在5 0 0 公里一1 5 0 0 公里( 含1 5 0 0 公里) 间的货票。 概念3 ：运距在1 5 0 0 公里以上的货票。 、 显然，上述3 个概念组成的概念族是货票集合u 上的形成划分的知识。u 上 的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 粗糙集理论建立在这样一个前提上：即所考虑的论域中的每一个对象都包含 某种信息( 数据和知识) 。例如，每个货票记录的包含了客户信息、货物信息以 及其它运输细节相关信息，。就可用的信息来说，如果对象在这些信息上相等， 则称对象在这些信息上是不开区分的。以这种方式生成的不可区分关系是粗糙集 理论的数学基础。 所有不可区分的对象形成的集合称为一个基本集( 也称基本集或基本概念) ， 它形成了全集中知识的一个基本粒度。一个集合若恰好等于基本集的任意并集称 为一个清晰( c r i s p ) 集( 精确集) ，否则称为粗糙( r o u g h ) 集( 不精确的) 。 于是，每个粗糙集都有了一个边界区域，处于边界区域的对象，仅根据其所 具z i 。的信息无法确定它是属于该集合还是其补集。显然，清晰集没有边界区域。 这意味着边界区域的样本无法利用现有知识正确分类。 因此，假设对象可以仅仅通过它们所具有的信息来观察导致了知识的粒度 性。由于知识的粒度性导致一些对象无法被区分并且表现为相同。以此，模糊的 概念不能用其元素的特征来刻划。粗糙集中提出用两个精确的概念一下近似和上 近似来刻划模糊的概念。下近似包含所有确定属于该概念的对象，上近似包含所 有可能属于该概念的对象。显然，上下近似之问的区别组成了模糊概念豹边界区 域。近似是粗糙集理论的两个基本运算。 前面已经提到，粗糙集的出发点是所感兴趣的对象的相关信息产生的不可区 分关系。不可区分关系的存在表明，由于知识的不完整和缺乏而无法区分某些对 象。这意味着无法处理单个对象，但可以把不可区分的对象组成的集合作为的基 本概念( 也就是知识的基本粒度) 来处理。 假设u 和a 是两个有限非空集合，其中u 是对象全集，也就是论域，a 是属 性的集合。t = ( u a ) 称为一个信息表。每个属性a a 都有一个取值范围v i ，称 硕士学位论文第二章粗糙集及模糊粗糙集 为a 的值域。a 的任何子集b 确定了u 上的一个二元关系i ( b ) ，称为不可区分关 系，其定义如下： ，( b ) = ( x ，y ) iv n 曰，a ( z ) = 口( y ) ) 公式( 2 一1 ) 其中a ( x ) 表示对象x 在属性a 上的取值。显然i ( b ) 是一个等价关系。 在论文的其余部分，i ( b ) 的等价类族，即b 所确定的划分将被表示为u i ( b ) ， 或者简记为u b ：1 ( b ) 的一个等价类，即u b 划分中的一块，若它包含对象x 则 被记为b ( x ) 。 如果( x ，y ) i ( b ) ，则我们将说x 和y 是b 一不可区分的。关系i ( b ) 的等 价类被称为b 基本集。b 基本集的任意并集称为b 可定义集。 不可区分关系可以用来定义粗糙集的基本概念。 假设x u 是对象的任意集合，则下面两个集合： b 。( x ) = 扛u ：占( x ) )公式( 2 - 2 ) 曰( x ) = ( x u ：日( x ) n x 妒)公式( 2 3 ) 风( x ) 和b8 ( ) 分别称为集合x 的b 一下近似和b 一上近似，而集合x 称为 参考集。集合 州。( x ) = 口+ ( x ) 一b + ( x ) 公式( 2 4 ) 称为集合x 的b 一边界区域。 若边界区域是空集，即研( ) = ，则集合x 关于b 是可定义( 准确、清 晰) 的。相反，若删。( x ) ，则集合x 关于b 是不可定义( 不准确、粗糙) 的。 粗糙集同样可以用下面的系数进行描述： 州，= 蹦 公式( 2 5 ) 该系数称为近似的准确性，其中l x i 表示集合爿庐的势( 或者基数) 。显 然o ( z ) l 。如果( x ) = 1 那么集合x 关于b 是清晰( 准确、可定义) 的。 相反，若盯。( x ) l ，则集合x 关于b 是粗糙( 不准确、不可定义) 的。 粗糙集同样可以用粗糙成员函数来描述，粗糙成员函数定义如下： 公式( 2 - 6 ) 显然，o ：( x ) s 1 。成员函数的值：( x ) 可以解释成x 属于x 的确定程度。 粗糙成员函数可以被用来定义集合的上下近似和边界区域，如下所示： b + ( j ) = r u ：( x ) = 1 ) 公式( 2 _ 7 ) 9 锴 f i ) r ( b f 硕士学位论文第二章粗糙集及模糊粗糙集 公式( 2 8 ) 公式( 2 9 ) 2 。1 2 决策表和决策规雯i l 决策表是粗糙集理论的知识表达形式，是一类特殊而重要的知识表达系统， 它表示当满足某些条件时，决策( 行为、操作、控制) 应该如何进行。 一个决策表是一一个知识表达系统 ，其中u 是对象集合，r = c u d 是属性集合，子集c 和d 分别称为条件属性集合和决策属性集合，d 庐，v 是属 性取值范围的集合，f ：( ，尺斗矿是一个信息函数，它指定u 中每个对象x 的 属性值。 条件属性c 和决策属性d 的等价关系i ( c ) 和i ( d ) 的等价类分别称为条件类和 决策类。 在推理、运算时，决策表通常只考虑决策属性为单一属性的情况，当现实中 遇到决策属性集合包含多个属性的时候，可以通过一些方法。将该决策表进行变 换，得到等价的单一决策属性决策表。 表2 1 是一个决策表的例子： 表2 1 流感诊断决蓑表 条件属性决策属性 病人头痛肌肉痛体温流感 e 1是是正常否 e 2是是高是 e3是 是很高是 e 4否是正常否 e 5否 否高 否 e 6否是很高 是 e 7否否 高是 e g否是很高否 设a = 是一个决策表，其中v = u 形i 口c ) u 屹tr = c u d ) 是属性 集合，b c u d ，v 上的原子公式a = v 称为b 和v 上的描述子，其中掰占且v 圪。 f ( b ，v ) 是b 和v 上的公式的集合。用m l 表示u 中所有满足性质妒f ( e 矿) 的对 象的集合。 这些集合及其运算定义如下： 忙= 吼= r u i 盯( r ) = p ) ， l 眵 妒虬= | | 妒虬n i 扫忆 i 忉v 妒。= l p 虬u l p t l l 。 0 - 1 妒虬= u l 眵虬 0 ， 川 砷 4 - 。“ k 硕。 ：学位论文第二章粗糙集及模糊粗糙集 i ? ( c v ) 和f ( d ，v ) 中的公式分别称为条件公式和决策公式。 是然任何对象j u 都属于决策表a 的个决策类队。；o 口= 口( x ) 0 。 a 的一个决策规则是形如妒；l f ，的一个表达式，其中妒f ( c ，矿) ，p ，( d ，矿) 。 决策规则常常可以用i f t h e n 形式来描述，以此常被称为i f t h e n 规则。 决策规则妒y 真当且仅当剜i 。陟儿。否则可以用酬l 包含在陟扎中的程度来 表示规则的可信度。 决策表中的每个对象x 代表了一个决策规则 八。sc 以= 口( x ) 八。e 。口= a ( x ) 。 对应于某些对象的决策规则可能有着相同的条件部分却有着不同的决策部 分。这样的规则被称为不一致的( 不可决定的，冲突的，可能的) 规则；否则规 则被称为一致的( 确定的，非冲突的) 规则。包含不一致规则的决策表称为不一 致的决策表，否则称为一致的决策表。 2 1 3 决策表离散化 运用粗糙集理论处理决策表时，要求决策表中的值用离散( 如整型、字符串 型、枚举型) 数据表达。如果某些条件属性或决策属性的值域为连续值( 如浮点 型数表达) ，则在处理前必须进行离散化处理，而且，即使对于离散数据，有时 也需要通过将离散值进行合并( 抽象) 得到更高层次的离散值，这是粗糙集理论 中的一类重要研究课题。由于决策表的离散化问题是在粗糙集理论分析的其他环 节( 如属性约简、值约简) 之前进行，故它属于粗糙集理论中的预处理部分。 设决策表t = ，r = c u d ) 是属性集合，子集c 和 d 分别称为条件 属性集和决策属性集，u = ( x ，x 。，x ) 是论域。设决策类的个数为r ( d ) 。属性a 的值域v 。上的一个断点可以记为( a ，c ) ，其中口尺，c 为实数集。在值域屹= 【乞，】 上的任意一个断点集合( ( 口，c 1 4 ) ， ，c ：4 ) ，0 ，q 。) ) 定义了圪上的一个分类只 只= 【c 0 4 ，c i 。】，【c l 。，c 2 4 】，h4 ，c k + 1 4 】) 乞 。气f 气 圪= 。，c l 。) u 【q 4 ，c 2 。) u u 【气。，气“。】 因此，任意的p = u 只定义了一个新的决策表s ，= ， 艇r ，( ) = ，铮，( ) 【e 。，q + 。) ，对于x ，f o ，k 。) ，即经过离散化后，原来 硕士学位论文第二章粗糙集及模糊褪糙集 的信息系统被一个新的信息系统所代替。 某个属性离散化后，它的属性区问被划分成多个子区问。每个子区问上的值 被统_ 地用一个符号来表示它可以是整型、字符串型、枚举型，但只有符号意 义，不能进行运算。因此习惯上称它为语言变量。 离散化本质上可以归结为利用选取的断点来对条件属性构成的空间进行划分 的州题，把这个n ( n 为条件属性的个数) 维空间划分为有限个区域，使得每个区 域中的对象的决策值相同。假没某个属性有m 个属性值，则在此属性域上就有m 1 个断点可取( 每两个相邻的属性值之间存在一个断点) ，随着属性个数的增加， 可取的断点数将随着属性值的个数呈几何增长。选取断点的过程也是合并属性值 的过程，通过合并属性值，减少属性值的个数，减小问题的复杂度，这也有利于 提高知识获取过程中所得到的知识的适应度。 2 1 ，4 属性约简 现实生活生产中，影响一件事物或一个过程的因素是多方面的，这些因素有 些是重簧的，有些是冗余的，去掉其中一些因素，不会影响人们对事物或过程的 状态的判断。这种在不影响人们对事物的判断的前提下去掉部分原因属性的操作 在粗糙集理论里称为属性约简。属性约简在现实系统中具有重大意义。例如，在 一些生产过程中，确保某些大型复杂的系统的工作状态十分重要，需要实时检测 并判断其工作状况以及时进行调节、控制。然而，可检测的影响其状态的参数也 许有几十甚至几百种之多，对这些参数都进行检测并判断不但可能影响实时性， 也是弓贵的，因此需要挑选出部分足以判断系统工作状态的参数加以检测，这一 过i 。、是属性约简过程。当然，在属性约简的过程中还可以给每个参数加上代表 检溉，戈本的权值，以得到检测成本最低的参数集合。当然，此时的约简集合不一 定是参数数目最少的约简。 由上可知，属性约简的目标就是从条件属性集合中发现部分必要的子集，使 得根据此子集形成的分类结果与条件属性全集的分类结果一致，即和条件属性全 集具有相同的分类能力。 条件属性集合的分类能力就是根据对象在该属性集上的取值确定对象的决策 属性取值的能力，它可以用决策属性对条件属性集合的依赖性来衡量。如果属性 集c 中的值唯一地决定了属性集d 中的值，则称d 完全依赖于c ，表示为c j d 。 换句话说，如果c 和d 值存在一个函数依赖关系，则称d 完全依赖于c 。 设c 和d 是a 的子集，则d 对c 的依赖性程度k ( o 詹1 ) 定义如下： 公式( 2 一l o ) 守， 硕 ：学位论文第二章粗糙集及模糊粗糙集 j 中 j i ) d 跖( d ) = uc + ( 并)公式( 2 1 1 ) x e t i i d 称为划分u d 关于c 的正域，它表示u 中所有能通过属陛集c 确定地分类到 u d 的分区中的对象的集合，其中c ( ) 是x 的c 一下近似。 如果k l 则d 完全依赖于c ，如果k 1 ，则称d ( 以程度k ) 部分依赖于c 。 系数k 表达了利用属性c ，u 中的所有对象能被正确的分类到划分u d 中的比 例它称为依赖性程度。 容易看出，如果d 完全依赖于c ，则有，( c ) ，( j d ) 。意味着c 生成的划分比d 生 成的划分更细，并且u d 中的任意一个等价类x 可以用u c 中的等价类的并集表 不n 属性约简就