（计算机软件与理论专业论文）基于扩展粗糙集的属性约简的研究.pdf

基于扩展粗糙集的属性约简的研究 摘要 粗糙集是一种处理模糊和不确定数据的数学工具，已在人工智能和数据挖 掘，模式识别与分类，故障监测等方面得到了良好的应用。属性约简是粗糙集理 论研究的一个重要内容，是在保持分类精度不变的前提下，删除冗余的属性的过 程。而寻求如何有效和快速地从那些尺寸庞大和复杂多样的数据集合中提取特征 子集已经成为属性约简研究的一个重要问题。 本文对基于扩展粗糙集的属性约简进行了研究，主要工作有： 1 提出了一种属性约筒的快速算法删冠，利用等价类的包含性质和分 支定界思想，将该算法中计算等价类的时间复杂度降为o ( 口1 1 m ) ：利用正区域和 属性个数的单调关系，减少论域的搜索空间，将约简算法的时间复杂度降为 o ( 阻1 2 i 卅) 。 2 针对以属性依赖度为度量的算法在处理某些数据应用时找不到任何特征 子集的问题，构造了前向贪婪搜索约简算法g a r b c 。该算法以一致性取代依赖 性作为属性重要性的度量，由于一致性是对正区域的扩展，使得多余属性和相对 约简的概念扩展了。 3 经典粗糙集理论是以严格的不可区分关系为基础的，在处理连续型属性 时往往要经过离散化处理。本文引入实数空间上的邻域系统，给出了一个混合属 性粗糙集模型，扩展了经典粗糙集理论的不可区分关系，构造了基于混合一致性 度量的约简算法a r b m c 。 4 在u 凹数据集合上将算法f f g a r 与现存算法进行比较，结果验证了算 法在计算效率上的有效性；将算法g a r b c 与传统算法进行比较，结果验证了算 法能够有效处理不一致信息系统；将算法a r b m c 与离散化方法进行比较，结果 表明了该算法在获得较少特征属性的同时能够保持或提高系统的分类能力。在大 坝安全监测系统中进行应用上述算法，能够有效地简化系统对测量数据进行的复 杂计算，提高系统的运行效率和预报监测精度，是可行和有效的。 关键词：粗糙集，快速算法，一致性，邻域，混合属性，安全监测系统 r e s e a r c h0 1 1d a t ar e d u c t i o nb a s e do n e x t e n d i n go fr o u g hs e t a b s t r a c t r o u g hs e tt h e o r yi s an e wm a t h e m a t i c a lt o o ld e a l i n g 、析t hv a g u e n e s sa n d u n c e r t a i n t y , h a sf o u n di t sa p p l i c a t i o n si nm a n ya r e a ss u c ha sa i ，k d d ，p a g e m r e c o g n i t i o na n dc l a s s i f i c a t i o na n df a u l td i a g n o s t i c a t i o n a t t r i b u t er e d u c t i o ni sa n i m p o r t a n tp a r to f t h er s t h e o r y , w h i c hd e l e t e st h er e d u n d a n ta t t r i b u t e so nt h ep r e m i s e o fu n c h a n g e do fc l a s s i f i c a t i o np r e c i s i o n a n dh o wt of m dt h er e d u c t i o nf r o mt h eh u g e a n dc o m p l e x i t yd a t as e tq u i c k l ya n de f f i c i e n t l yi sa k e ys t e po fr st h e o r y a t t r i b u t er e d u c t i o ni sf o c u s e do ni nt h i sd i s s e r t a t i o n m a i nt o p i c si n c l u d e 1 an e wa l g o r i t h mf f g a ri s p r e s e n t e db a s e do nb r a n c ha n db o u n dt o c o m p u t eu a u s i n g t h e i n c l u d i n gr e l a t i o n s h i p ，t h ea l g o r i t h mc u t sd o w nt h e c o m p l e x i t yt oo ( i a i i u i ) a n dm a k i n gu s eo ft h ep r o p e r t yt h a tp o s i t i v er e g i o n i n c r e a s e sw i t ht h ea m o u n to fa t t r i b u t e s ，af a s ta l g o r i t h mw h o s ec o m p u t a t i o n c o m p l e x i t yi so ( i a i 二i u i ) i sp r o p o s e d 2 i nm o s to ft h ee x i s ta l g o r i t h m s ，t h ed e p e n d e n c yf u n c t i o ni s e m p l o y e dt o e v a l u a t et h eq u a l i 够o faf e a t u r es u b s e t 。t h ed i s a d v a n t a g e so fu s i n gd e p e n d e n c y f u n c t i o na r ed i s c u s s e di nt h i sp a p e r , a n dt h ep r o b l e mo ft h ef o r w a r dg r e e d ys e a r c h a l g o r i t h mb a s e do nd e p e n d e n c yf u n c t i o ni sp r e s e n t e d an e wc o n s i s t e n c ym e a s u r ei s i n t r o d u c e dt od e a lw i t ht h i sp r o b l e m b a s e do nt h ec o n s i s t e n c y , af o r w a r dg r e e d y s e a r c ha l g o r i t h mg a r b ci sd e s i g n e dt of i n dr e d u c t s 3 c l a s s i c a lr sm o d e lj u s tw o r ki nd i s c r e t e s p a c e s ，s ow en e e dt r a n s f o r m n u m e r i c a la t t r i b u t et od i s c r e t eo n e s t h ep r o c e s sm a yl o s ss o m ei n f o r m a t i o no ft h e d a t as e t t od e a l 、析mt h i s p r o b l e m n e i g h b o r h o o dr o u g hs e tm o d e lb a s e do n n e i g h b o r h o o ds y s t e mi s i n t r o d u c e da n dan e wr o u g hs e tm o d e lw i t ht h em i x e d a t t r i b u t e sd a t as e ti sc o n s t r u c t e d b a s e do nt h em i x e dc o n s i s t e n c y , af o r w a r dg r e e d y s e a r c ha l g o r i t h ma r b m ci sd e s i g n e d 4 e x p e r i m e n tr e s u l t sw i t hu c id a t as e t ss h o wt h a tt h ep r o p o s e da l g o r i t h m sa t e e f f i c i e n ta n de f f e c t i v e i nd a m ss a f e t ym o n i t o r i n gs y s t e m ，w ea p p l yt h em e t h o db a s e d o nr st h e o r yt oa n a l y z et h ed a t ao fd a m t h ep r a c t i c er e s u l t ss h o wt h a ti tc a l ls i m p l i f y t h ee v a l u a t i n go ft h en e wd a t a , a n df i n d i n gu s e f u li n f o r m a t i o nf r o me x i s t i n gd a t a t h e r e s u l t se x p r e s st h a tt h em e t h o dc a nr e m a i nt h ec l a s s i f i c a t i o np o w e ra n dr e d u c et h e c o m p u t a t i o nt i m e v k e y w o r d s ：r o u g hs e t s ，f a s ta l g o r i t h m ，c o n s i s t e n c y ，n e i g h b o r h o o d ，m i x e da t t r i b u t e s ， s a f e t ym o n i t o r i n gs y s t e m 插图清单 图3 1i n d ( p ) 算法流程图1 7 图3 2 加政p ) 算法计算演示18 图3 3m u s h r o o m 集合上算法f f g a r 计算效率比较2 1 图3 44 个不同数据集合上算法f f g a r 计算效率比较2 l 图3 5 二元分类问题2 3 图3 - 6 数据集合s o n a r 和i o n o s p h e r e 上算法a r b m c 变距离测试3 l 图4 1 大坝安全监测基本逻辑框图。3 4 图4 1 大坝某测点的部分采集数据3 5 表格清单 表2 1 信息系统的一般表示8 表2 2 实例1 决策信息系统10 表2 - 3 表2 2 实例1 的区分矩阵1 0 表3 - 1 实例2 的决策信息系统18 表3 - 2 算法f f g a r 测试用u c i 数据集合2 0 表3 - 3 算法f f g a r 约简前后精度比较2 2 表3 - 4 算法g a r b c 测试用u c i 数据集合。2 5 表3 - 5 不同离散化方法下算法g a r b c 的特征选择2 5 表3 - 6 不同离散化方法下算法g a r b c 的精度比较。2 6 表3 - 7 算法a r b m c 测试用u c i 数据集合3 0 表3 8 算法a r b m c 在最优距离阀值下的特征选择和分类精度。3 0 表4 - l 大坝安全监测系统中算法f f g a r 测试。3 5 表4 - 2 系统中算法g a r b c 测试。3 5 表4 - 3 系统中算法a r b m c 测试。3 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金起王些态堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 酶童 签字日期： 学位论文版权使用授权书 沙p f 、f 7 | 本学位论文作者完全了解 金胆王些盔堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金日巴王些盔堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字e l 期： 口 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期： 电话： 邮编： 碧。 乒对女 忑r弘 致谢 值此论文完成之际，我谨向我的导师李心科老师表示由衷的谢意! 在我的硕 士研究生学习过程中，一直都得到了李老师悉心的指导，所取得的进步，无不浸 透着李老师的心血。李老师治学态度严谨，工作作风踏实，都是我学习的榜样， 不仅在学术上，在为人处事的原则上，李老师更是给我指明了方向。李老师知识 渊博，治学严谨，对问题有敏锐的洞察力，在我的硕士论文中也倾注了力老师大 量的心血，没有他的指导和帮助，没有他对我论文反复修改和提炼，我是不可能 完成我的毕业论文的。 感谢软件工程实验室的教授们对我的关心和帮助，感谢计算机与信息学院的 老师们，感谢他们给我提供的学习条件和机会。 感谢合肥工业大学软件工程研究室的所有师兄弟们，和他们的交流帮助我完 成了学业。 最后我要感谢我的家人，是他们几十年来一直默默地给予我关怀和帮助，是 我能够顺利的完成学业，也将激励着我在今后的工作中不断的前进。 作者：陈垫 2 0 0 8 4 u 1 1 粗糙集理论研究的背景和目的 第一章绪论 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及， 人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类 服务，业已成为广大信息技术工作者的所重点关注的焦点之一。与日趋成熟的数 据管理技术与软件工具相比，人们所依赖的数据分析工具功能，却无法有效地为 决策者提供其决策支持所需要的相关知识，从而形成了一种独特的现象“丰富的 数据，贫乏的知识 。 而随着数据库技术、人工智能、统计等技术的发展和融合，为有效解决上述 问题，自二十世纪九十年代开始，数据库知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d 逐步发展起来。在数据挖掘技术日益发展的同时，粗糙集理论 作为一种数据处理工具是诸多数据挖掘技术中较为有效的方法。粗糙集概念最早 是由波兰数学家z p a w l a k d l 于1 9 8 2 年在计算机与信息科学国际杂志上发表 的论文“r o u g hs e t ( 粗糙集) 中提出的。由于最初关于粗糙集理论的研究大多 是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视，研究仅 限于东欧的一些国家。直到1 9 9 1 年，p a w l a k 发表了专著粗糙集关于数据 推理的理论，奠定了粗糙集理论的基础，从此粗糙集理论及其应用的研究进入 了一个新的阶段。 1 2 国内外的研究状况 随着粗糙集关于数据推理的理论的发表，粗糙集理论的研究热潮逐 渐掀起。1 9 9 2 年，在波兰召开了第一届国际粗糙集理论研究会，这次会议着重 地讨论了集合近似的基本思想和应用，其中粗糙集环境下的机器学习的基础研究 是这次会议的专题之一。1 9 9 3 年在加拿大召开了第二届国际粗糙集与知识发现 研究会，这次会议积极推动了国际上对粗糙集应用的研究。一些著名的知识发现 学者参加了这次会议，并且介绍了许多应用扩展粗糙集理论的数据挖掘的方法与 系统。1 9 9 6 年在日本东京召开了第五次国际粗糙集研讨会。1 9 9 8 年在波兰华沙 召开了“第一届粗糙集和计算的当前趋势学术会议。1 9 9 9 年在日本召开了第 七届“粗糙集，模糊集，数据挖掘和粒度软计算的国际学术研讨会，阐明 了当前粗糙集、模糊集的研究趋势和现状，着重研究了其在软计算、数据库、 a i 和近似推理定理论和应用方面的发展。现在美国、加拿大、波兰、日本都有 粗糙集研究的专门机构。 粗糙集研究在我国的起步虽然较晚，但发展较快。2 0 0 1 年“第一届中国粗 糙集和软计算学术研讨会”在重庆邮电大学举办。大会邀请了粗糙集理论的创始 人z p a w l a k 教授做大会报告，研讨会推动了亚洲地区和我国对粗糙集理论与应 用的研究。2 0 0 3 年中国人工智能学会粗糙集与软计算专业委员会成立。2 0 0 6 年 7 月首届粗糙集与知识技术国际会议在重庆举行。目前，国内学者从事粗糙集研 究的人员越来越多，已经形成一支较为稳定的学术队伍，中国学者在这一领域中 的影响也越来越大。 1 3 粗糙集理论的研究内容和应用 1 3 1 粗糙集理论的研究内容 粗糙集理论提供了一种新的处理模糊和不确定数据的数学工具，其主要思想 是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则【4 j 。 粗糙集理论首先从新的角度对知识进行了定义。把知识看作是关于论域的划 分，从而认为知识是具有粒度( g r a n u l a r i t y ) 的。认为知识的不确定性是由知识粒度 太大而引起的，为处理数据( 特别是带有噪音、不精确或不完全数据) 分类问题提 供了一套严密的数学工具，使得对知识能够进行严密的分析和操作。而粗糙集理 论的研究主要有下面几个方面： 1 粗糙集模型的扩展和推广。粗糙集模型的推广一直是粗糙集理论研究的 主流方向，目前主要有两种方法：( 1 ) 构造性方法；( 2 ) 代数性( 公理化) 方法。构造 性方法是对经典粗糙集模型的一般推广，其主要思路是从给定的近似空间出发去 研究粗糙集和近似算子。它是以论域上的二元关系或布尔子代数作为基本要素 的，然后导出租糙集代数系统。这种方法所研究的问题往往来源于实际所建立 的模型有很强的应用价值，其主要缺点是不易深刻了解近似算子的代数结构。代 数方法也称为公理化方法有时也称为算子方法，这种方法不是以二元关系为基本 要素，它的基本要素是一对满足某些公理的一元( 集合) 近似算子，即粗糙代数系 统中近似算子是事先给定的。这种方法研究的明显优点是能够深刻地了解近似算 子的代数结构，其缺点是应用性不够强。 2 不确定性问题的理论研究。粗糙集理论中知识的不确定性主要由两个原 因产生的：一个原因是直接来自于论域上的二元关系及其产生的知识模块，即近 似空间本身，如果二元等价关系产生的每一个等价类中只有一个元素，那么等价 关系产生的划分不含有任何信息。划分越粗，每一个知识模块越大，知识库中的 知识越粗糙，相对于近似空间的概念和知识就越不确定，这时处理知识的不确定 性的方法往往用信息熵来刻画，知识的粗糙性与信息熵的关系比较密切，知识的 粗糙性实质上是其所含信息多少的更深层次的刻画。单从这个角度来看，粗糙集 理论与信息论的关系就比较密切，不少学者在这方面做了研究工作。 3 算法研究。粗糙集理论中有效算法研究是粗糙集在人工智能方向上研究 2 的一个主要方向。目前，粗糙集理论中有效算法研究主要集中在导出规则的增量 式算法，约简的启发式算法，粗糙集基本并行算法，以及与粗糙集有关的神经网 络与遗传算法等。这些研究的成功应用有的已经获得了商业价值。 1 3 2 粗糙集理论的应用 由于粗糙集理论在数据挖掘方面的应用备受关注，最近几年，粗糙集理论的 应用研究得到了长足的发展。下面从几个方面简述粗糙集理论的应用。 1 数据缩减和规则生成。k o h a v ia n ds a h a m i 3 1 用实验证明了数据库中最有 用的子集不一定是粗糙集中的相对核，甚至可能不包括完整的核属性。文献在讨 论了基于r s 的从数据中发现规则的增量自适应算法。g r z y m a l a 4 , w j j 比较了同时 使用可能规则及确定规则和只使用确定规则的性能，发现前者出现较少的错误 率。 2 大数据集。由于粗糙集在数据挖掘中具有较大的计算复杂度，受关联规 则算法的启发，有些学者提出将关联规则挖掘技巧应用于粗糙集的确定和可能规 则生成中来，以减少粗糙集方法的计算复杂度。而文献则使用遗传算法在决策表 中寻找代表性的模板，然后递归生成决策规则。 3 多方法融合。d u c h 7 】研究了将粗糙集方法应用于神经网络训练数据的预 处理。上述处理有利于提高学习效率，并且保持了较低的稳定的近似分类误分类 差错率。首先使用面向属性的概念树爬升技术对属性进行泛化，然后使用r s 方 法计算缩减并生成规则。由于在泛化过程中消除了不必要的属性值和在缩减过程 中去掉了不相关的属性，最后的规则是很一般的形式并且可用高层次抽象概念表 达。h u 8 】提出了一种将基于属性的归纳概念方法和r s 结合的方法。l i n g r a s 9 1 研究了粗糙集和遗传算法的集合，提出了一种粗糙遗传算法，在该算法中，基因 用粗糙数表示。 4 信息检索。k w a k 1 0 l 等在r s 理论基础上提出了一种r o u g h 关系数据库 模型，并定义了各种r o u g h 关系算子。该模型将r s 的重要性质引入到基本关系 模型中，从而使之具有更好的检索能力和适应性。在此模型中，查询结果返回的 是基于属性的r o u g h 关系，它不仅包含一个查询的确定应答，还包含可能的应 答，例如上近似所包含的元组等。 1 4 本文的研究内容和内容组织 1 4 1 本文的研究内容 粗糙集理论是应用决策信息系统来描述论域中的对象。决策信息系统是一种 重要而特殊的知识表达系统，通过对决策信息系统进行属性约简，使得化简后的 系统保留功能的同时具有更少的条件属性。决策信息系统的化简在工程应用中相 3 当重要，所以高效的属性约简算法是粗糙集理论应用于数据挖掘与知识发现领域 的重要方面，同样粗糙集模型的扩展推广也是主要研究课题之一。本文主要研究 基于扩展粗糙集模型的属性约简算法，主要内容如下： 概述了粗糙集理论的相关知识，系统地分析了经典粗糙集理论的属性约简算 法。 提出了一种基于属性依赖度的快速约简算法f f g a r ，采用分支定界思想改 进计算等价类的方法：并利用正域和属性个数的单调关系减少样本搜索空间，从 而减少计算次数，达到提高计算效率的目的。针对基于属性依赖度的约简算法在 处理不一致信息系统时可以出现不能发现任何约简集合的问题，基于一种新的一 致性度量提出了算法g a r b c ，有利于合理地处理不一致信息系统。 经典粗糙集理论能够良好对离散型数据进行处理，而对于连续型属性则需要 先进行离散化处理。在现实应用中连续型数值数据往往是普遍存在的。针对离散 化带来的信息丢失问题，基于邻域系统，提出了一种混合属性粗糙集模型，并构 造了该模型下的约简算法a r b m c 。直接对混合属性信息系统进行处理，能够减 少信息丢失，提高分类精度。 将文中的粗糙集约简算法应用于大坝安全监测系统，测试结果表明了算法在 系统中应用的可行性和有效性。 1 4 2 文本的内容组织 本文的内容组织如下： 第一章简述了数据库中的知识发现和数据挖掘的产生以及发展前景，阐述 了其处理过程。简述了粗糙集理论的产生背景和发展现状，以及研究内容。最后 阐述了本文的研究重点，和文章的组织结构。 第二章介绍经典粗糙集理论的主要概念，对典型的属性约简算法进行了分 析和研究，并对一些粗糙集扩展模型进行了介绍。 第三章基于对基本约简算法的研究，提出基于属性依赖度的快速约简算法 f f g a r 和基于一致性度量的约简算法g a r b c ，最后提出了一种改进的混合属 性粗糙集模型及其约简算法a r b m c 。 第四章简述大坝安全监测系统的内容、目的和工作原理，将粗糙集理论在 系统中的应用给出了相应的理论分析和实验说明。 第五章本文的总结，对全文的主要研究工作进行简要的阐述和说明，并对 下一步的工作进行了展望。 4 第二章粗糙集理论及约简算法 2 0 世纪8 0 年代，波兰的p a w l a k 教授提出了粗糙集理论，这是一种新型的 处理模糊性和不确定性知识的数学工具。经过t - 十多年的研究和发展，粗糙集 理论已经在信息系统分析、人工智能、决策分析支持、知识发现、模式识别与分 类、故障监测等方面取得了较为成功的应用。 粗糙集理论具有一些独特的观点。这些观点使得粗糙集特别适合于进行数据 分析，如： 知识的粒度性。 粗糙集理论认为知识的粒度性是造成使用已有知识不能精 确地表示某些概念的原因。通过引入不可区分关系作为粗糙集理论的基础，并在 此基础上定义了上下近似等概念，粗糙集理论能够有效的逼近这些概念。 新型成员关系。和模糊集合需要指定成员隶属度不同，粗糙集的成员是客 观计算的，只和已知数据有关，从而避免了主观因素的影响。 采用粗糙集理论作为研究知识发现的工具具有许多优点。粗糙集理论将知识 定义为不可区分关系的一个族集，这使得知识具有了一种清晰的数学意义，并可 使用数学方法进行处理。粗糙集理论能够分析隐藏在数据中的事实而不需要关于 数据的任何附加信息。 但是，在粗糙集合应用于实际系统时，仍然存在一些实际问题。例如在大数 据集下约简的有效计算问题，如何处理数据中的噪音和丢失值问题。为解决上述 问题，有许多工作集中在寻求有效的约简算法和对经典粗糙集理论的扩展上。 本章首先介绍了粗糙集理论的研究现状，接着对基本的约简算法和经典的粗 糙集扩展模型进行介绍。 2 1 粗糙集理论的基本概念 本节我们引入粗糙集理论主要概念的形式化定义。 定义2 1 信息系统可以表示为s = ( v , a u d ，助。其中u 为对象的非空有限集 合，称为论域；彳是非空有限的条件属性集合，d 是决策属性，彳n 刃- - i 乃；属性 集彳的值域肛u 口彳v o ，圪是属性口的值域，u 彳一v 是一个信息函数。 表2 1 给出一个信息系统的例子，其中泸 1 ，2 ，9 ) ，么= a i , a 2 ，a 3 ，a 4 ，决策 属性为d 。 5 表2 1 一个信息系统的例子 u a i a 2a 3a 4 d 定义2 2 设s = ( u 彳u 田，啪是信息系统，在任意子集b _ c a 上，且召。，则 b 中所有等价关系的交集称为b 上的不可区分关系( i n d i s c e r n i l i t yr e l a t i o n ) ，记为 i n d ( b ) 如故功= ( 葛力泸u ，反触力钡m ，) 不可区分关系也是等价关系，它把u 划分成为有限个集合，称为等价类， 记做m 删例，简记为b b 。 定义2 3 给定信息系统s = ( u , a u 4 ，啪，x c _ u 是一组对象，b c _ a 是一组属 性，x 相对于b 的下近似集定义为： b 一= f x u l 嘲占_ c x ) 定义2 4 给定信息系统s = ( u 彳u 田，场，x c _ u 是一组对象，b c _ a 是一组属 性，x 相对于b 的上近似集定义为： b 一= x ui x b n x o 定义2 5x 的b 边界则定义为集合： b n r ( x ) = b 一一b 一 我们也把n e g r x ) = u - - b 一为x 的b 的负域( n a g e t i v e ) ，把b n r x ) 称为边界 域( b o u n d a r y ) 。 定义2 6 给定信息系统s = ( u 彳u 刃，啪，x c _ u 是一组对象，b 至彳是一组属 性，决策属性d 相对于b 的正区域( p o s i t i v e ) 定义为： e o s d a ) = u 召一( x ) l x eu i n d ( d ) 图2 1 给出了经典粗糙集模型的几何解释。 6 i 2 3 4 s 6 7 8 图2 1 离散空间的经典粗糙集 由图2 1 可知，正域的大小反映了分类问题在给定属性空间中的可分离程度。 正域越大，表明各类的重叠区域，即边界越小。那么根据此属性集，可以更加精 细的描述此类分类问题。因此定义决策属性d 对条件属性b 的依赖性来进行描述。 定义2 7 给定信息系统s = ( u 么u 奶，v j ) ，b c _ a ，决策属性d 对条件属性集a 的子集b 依赖度y p d 定义为： 7 # l = c a r d ( p o s b ( d ) ) l c a r d ( p o s a ( d ) ) 其中c a r d ( ) 表示集合的基数。 定义2 8 给定信息系统s = ( u 彳u m ，啪，b 爿，a a - b ，则属性a 相对于b 的属性重要性定义为： s i g ( a , b c o = 1 b ul 。id 一 1 8 d 决策属性d 相对于b 的正区域代表了b c _ a 对于决策属性的近似质量。对于 原始数据集的决策来说，并不是4 中的所有的属性都是需要的，可能有些是冗余 的。约简就是在保持近似质量不变情况下的最小条件属性子集。 定义2 9 给定信息系统s = ( u 彳u 奶，助，vd b 4 ，如果帕一纠妁，则 称a 相对于b 是必不可少的，否则拈一向，州，称a 为b 中多余的。如果对于 v a b 都是必不可少的，我们称b 是独立的。 如果7 e - 加f 竹，则表明从系统中去掉属性a ，系统的正域没有发生改变， 因此各类的可区分性不变，此时属性a 没有给分类带来任何贡献，因此说a 是多 余的。相反，如果删除a ，系统的决策正域变小了，则表明各类的可区分性变差 了。此时口不能被删除。 定义2 1 0 给定信息系统s = ( u 彳u d ) ，珊，b s 彳，若满足 ( 1 ) v a b ，怕一t o j d o 。 定义2 1 7 任意属性a e a 哪的重要性定义为： s i g ( a , b , d ) = h ( d l 功一h ( 4 bu 口) ) 基于互信息和条件熵的约简算法有m i b a r i d 2 2 】算法和c e b a r k c 0 2 3 1 算法， 其分别以互信息和条件熵作为启发信息来衡量属性重要度。m i b a r k 算法和 c e b a r k c c 算法都是先计算信息系统的核，然后再对非核属性进行约简。 m i b a r k 算法式建立在条件属性与决策属性的互信息的基础上，以互信息的变化 量作为属性对于决策的相对重要度，以此为启发信息，以互信息相等作为终止条 件。c e b a r k c c 鼻讼是以信息系统的核属性为起点，逐次选择h ( a r e d u a ) ) 最 小的非核条件属性添加到核属性集合中，直到满足h ( a l a ) = h ( d l r e d ) ，得到约简 集合。其中m i b a r k 算搓韵基本描述入下： 算法2 3m i b a r k 输入：s = ( u , au d ) 力 输出：约简r e d 1 计算条件属性a 于决策属性d 的互信息耻；d ) ； 2 计算信息系统的核c o r e ；初始化r e d 为c o r e ，i m a x = o 3 h l ei m a x i ( a ；d ) f o re a c ha 包含于c 瑚p d ，计算使l ( a , a l r ) 最大的属性； r e d = r e d ua i m a x = i ( r e d ；d ) e n dw h i l e 4 r e t u r nr e d 若信息系统的核用基于区分矩阵算法来计算，那么m i b a r k 算法和 c e b a r k c c 算法的时间复杂度都为o ( 阻i l 刎2 ) + o ( 1 0 3 3 ) 。 2 3 扩展模型 经典粗糙集理论是建立在严格的不可区分关系基础上的，在处理现实世界中 的应用时会面临一些实际的问题，例如数据集合中含有噪音数据、数据有缺失、 连续型数值数据的离散化等问题。许多研究人员就这些问题都提出了自己的一些 想法，其中典型的有可变精度模型、相似模型等。 2 3 1 可变精度模型 在数据集中存在噪音等干扰情况下，经典粗糙集理论会由于其不可区分关系 的局限造成对数据的过拟合而使其对新对象的预测能力大为降低。而在实际应用 中，噪音的存在是在所难免的。为增强粗糙集模型的抗干扰能力，z i a r k o 3 0 1 提出 了一种可变精度粗糙集模型。该模型通过引入一个可变精度，从而具有一定的容 错性。 可变精度模型对经典粗糙集理论的扩展主要体现在它允许一定的误分类率。 为此引进一个精度b ( 0 b o 5 ) 。定义b 多数包含关系为：若把集合x 中的元 素分类到集合】，中，则会犯分类错误的可能性小于1 3 。显然，若1 3 ：0 ，则b - 多数 包含关系就退化成标准的包含关系。这样也就可以用p 多数包含关系来解释粗糙 1 2 集中的上下近似。 集合x 的下近似可解释为那些【，中的元素分类到x 中分类错误率不大于b 的等价类集合。x 的b 上近似跚包含所有u 中不可能在误分类率小于6 之下 分类到x 中的所有元素。 依据经典粗糙集理论中同样的方式，利用集合的下近似，可以定义属性的b 近似依赖度。经典粗糙集的属性依赖度是精确分类，即对对象的无错误分类的综 合能力的评价，而近似依赖度则是度量分类错误率在预先给定的可容忍极限b 之 内的分类能力。近似分类与粗糙分类相反，不能解释为属性的函数或部分函数依 赖。近似依赖的性质弱于函数依赖的性质，例如传递性就不再成立。 根据扩展的近似依赖的定义，b 约简或称近似约简可以定义为在近似依赖 度不变的前提下的最小子集。可变精度模型是和经典粗糙集相兼容的。因为只要 令b = o ，那么就和经典模型一致了。因此可变精度模型能够保留绝大多数经典模 型的良好性质，这为它的广泛应用打下了基础。 2 3 2 相似模型 在数据中存在缺失的属性值的时候，经典粗糙集理论下的不可区分关系或者 说是等价关系无法应付这种情形。为扩展粗糙集的能力，许多研究人员提出了用 相似关系来代替不可区分关系作为粗糙集的基础。 使用相似关系代替粗糙集合中的不可区分关系，最主要的变化就是相似类不 再形成对原集合的划分了，它们之间是相互重叠的。类似于等价类，可以定义相 似集，即所有和某个元素x 在属性集合b 上相似的集合s i m b ( x ) 。值得注意的是 s i m b ( x ) 中的元素不一定属于同一决策类。因此还需定义相似决策类，即相似集对 应的决策类集合。 由于相似集的元素并不一定属于同一个决策类，为此定义相对吸收集。子集 y c _ u 称为相对吸收集如果对于每个xe u ，存在ye y 与之相似，并且具有同样 的决策值。显然相对吸收集可以用来进行数据削减。利用相似集可以很容易的定 义正区域的概念，它就是所有包含在决策类中的相似集的并。依赖度和约简的概 念都能以类似经典理论的方式定义。 2 4 本章小结 粗糙集理论从集合论的角度出发，以观测数据进行分类的能力为基础，用求 核和约简的方法，仅仅利用数据本身的知识，来获得隐含的、内在的规律。通过 粗糙集方法能够挖掘出高质量和清晰的决策规则集，具有广泛的适应性。本章主 要介绍了粗糙集理论的主要概念，对经典的粗糙集属性约简算法进行了较为详细 的介绍和分析。此外还对典型的粗糙集扩展模型进行了介绍。 1 3 第三章基于扩展粗糙集的属性约简 属性约简是粗糙集理论中的一个重要内容，其目的就是求出最优约简，人们 通过引入区分矩阵、信息熵等技术和方法来达到求解最优约简的目的，但由于这 些算法受本身适用度的限制，都存在着一些不足。 本章针对基本算法的不足，进行了针对性不同的改进。首先，给出了一个基 于属性依赖度的快速约简算法e r 阴足；其次，针对以属性依赖性为度量的约简 算法在处理不一致决策信息系统时存在的问题，提出了一种基于一致性度量的约 简算法g a r b c ；最后，针对基于不可区分关系的经典粗糙集不能直接处理连续 型数值数据的问题，给出了一种混合属性粗糙集模型。 3 1 基于属性依赖度的快速约简算法 3 1 1 问题分析和相关原