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

内蒙古大学硕十学位论文 基于粗糙集的属性约简算法研究 摘要 粗糙集理论是由波兰数学家z p a w l a k 在1 9 8 2 年提出的，是继概率论、模糊 数学、证据理论之后又一种处理不确定性的有效数学工具。该理论的特点是不 需要任何先验知识，或任何附加信息，就能有效地分析和处理不精确、不完整 和不一致的信息。并从中发现隐含的知识，揭示潜在的规律。数据挖掘和知识 发现是从现存的数据库、数据仓库或其它信息库中挖掘有价值的知识的过程。 粗糙集理论是一种新的数据挖掘技术。 属性约简是利用粗糙集理论作为工具来进行数据挖掘的关键技术之一。本 文对粗糙集理论进行了研究，提出了一种基于区分矩阵和属性重要性的改进算 法。针对决策表中存在的不相容问题，本文在对前人算法讨论的基础上，提出 一种基于u i n d ( c ) 等价类划分的约简算法。最后，本文在总结了上述各个算法的 特点后，提出一种基于树的约简算法，该算法的特点是能够得到决策表的所有 约简，并且适合相容决策表和不相容决策表。 关键词：数据挖掘，粗糙集，属性约简，区分矩阵，树 基丁租糙集的属性约简算法研究 r e s e a r c h e df o ra t t r l b u t 嚣r e d u c t 薹o na l g o r l t h m b a s e do nr o u g hs e tt h e o r y a b s t r a c t r o u g hs e tt h e o r yi sp r o v i d e db yz 。p a w l a ki n19 8 2 。i ti sam 弛t h e o r yt h a t p r o c e s st h en o n - a c c u r a t ea f t e rp r o b a b i l i t yt h e o r y , f u z z yt h e o r ya n dd e m p s t e r - s h a f e r n o tn e e d i n go t h e ri n f o r m a t i o no rp r e v i o u sk n o w l e d g et h i st h e o r yc a na n a l y z ea n d p r o c e s st h en o n a c c u r a t e ，n o n i n t e g r i t yd a t aa n dt h e nm i n el a t e n tk n o w l e d g e d a t a m i n i n ga n dk n o w l e d g ed i s c o v e r yi nd a t a b a s e si sd r a w i n gk n o w l e d g ef r o mt h e d a t a b a s e ，d a t aw a r e h o u s eo ro t h e rd a t a b a s e s r o u g hs e tt h e o r yi san e wd a t am i n i n g t e c h n o l o g y t h ea t t r i b u t er e d u c t i o ni sak e y t e c h n o l o g yi nr o u g hs e t sf o rd a t am i n i n g 。i nt h i s p a p e r ，ih a v es t u d i e dt h er o u g hs e tt h e o r ya n dm a d ead i s t i n c t i o nb a s e do nt h em a t r i x a n da t t r i b u t ei m p o r t a n c eo f i m p r o v i n gt h ea l g o r i t h m i nt h ed e c i s i o n m a k i n gt a b l ef o r t h ei n c o m p a t i b i l i t yp r o b l e m ，im a d ean e wa t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nt h e u i n d ( c ) e q u i v a l e n c ec l a s so ft h er e d u c t i o na l g o r i t h mf i n a l l y , i ns u m m i n gu pt h e c h a r a c t e r i s t i c so fe a c ho ft h e s ea l g o r i t h m s ，t h i sp a p e rm a d e an e wa l g o r i t h mb a s e do n at r e eb yt h er e d u c t i o na l g o r i t h m 。t h ea l g o r i t h mi sc h a r a c t e r i z e d b yt h ed e c i s i o nt a b l e ，c a n b ea l lf o rc o m p a t i b l ea n d i n c o m p a t i b l ed e c i s i o nt a b l e k e y w o r d ：d a t a m i n i n g ，r o u g hs e t s ，r e d u c t i o nd i s c e r n i b i l i t ym a t r i x ，t r e e i i 内蒙古大学硕+ 学位论文 图表目录 图1 1 数据挖掘和其它学科的关系。1 图1 2 数据挖掘的基本过程和主要步骤2 图2 1 粗糙近似1 1 表3 1 某一知识表达系统1 5 表3 2 表3 1 对应的区分矩阵1 5 表3 3 决策表1 6 表3 4 表3 3 对应的区分矩阵1 7 表3 5 决策表。2 1 表3 6 汽车数据库2 3 表3 7i ( p ；d i r ) 值2 3 表3 8 区分矩阵m 2 7 表3 9 区分矩阵m 母2 7 表4 1 决策表31 表4 2 决策表3 2 表4 3 决策表。3 3 表4 4 决策表。3 5 表4 5i ( 1 9 l ) 值3 5 表4 5 表4 1 的转换决策表3 9 表4 6 表4 4 的转换决策表3 9 表4 7 表4 5 的区分矩阵3 9 表4 8 表4 6 的区分矩阵3 9 表5 1 决策表4 2 图5 1 约简树第一层4 3 图5 2 最后约简树4 3 图5 3 约简树第一层4 3 v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 己经发表或撰写过的研究成果，也不包含为获得内蒙古大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示了谢意。 在学期间研究成果使用说明书 学位论文作者完全了解内蒙古大学有关保留和使用学位论文的规定，即：内 蒙古大学研究生在校攻读学位期问论文工作的知识产权单位属内蒙古大学。学校 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查 阅和借阅；学校可以公靠学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。作者今后使用涉及在学期间主要研究内容 或研究成果，须征得内蒙古大学就读期f 日j 导师的同意：若用于发表论文，版权单 位必须署名为内蒙古大学方可投稿或公丌发表。 学位论文作者签名： 日期： 玄鏖 务一五j 7 一墟 f r 矿_ 尹鉴銎 内蒙古大学硕士学位论文 1 1 数据挖掘 第一章绪论 当今，随着计算机网络和通讯的发展，产生了大量的数据，并且，伴随着计算机硬件的 飞速、稳定的进步，对这些数据的存储也成为了可能。庞大的数据集带来了海量的信息，但 是如何从这些浩如烟海的数据和信息中获得自己感兴趣的有用的信息已经远远超出人的处理 和理解能力。结果大量数据被收集在大型数据库中常年得不到访问，成为“数据坟墓 。【1 】 1 1 1 什么是数据挖掘 数据挖掘，英文为d a t am i n i n g ，对于它的描述有许多不同的说法，其中最普遍的定义为： 数据挖掘是指从大量数据中抽取隐含的、不为人知的、有用的信息。数据挖掘也被描述为试 图创建一个数据库中描述的复杂世界的简单模型，因而我们也可以说数据挖掘是处理大量信 息的方法，并且它有助于以比任何人都快的速度发现有用的信息。与数据挖掘的意义非常相 近的另一些术语有数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简称k d d ) 、数 据分析、知识提取等。 数据挖掘是- i j 广义的交叉学科，对数据挖掘技术的研究涉及数据库、人工智能、统计 学、可视化、并行计算等多门学科，也吸引了大批各领域学者和工程技术人员的关注。 i i 2 数据挖掘的过程 图i i 数据挖掘和其它学科的关系 f i g u r e 1 1r e l a t i o n s h i po fd a t am i n i n ga n do t h e rs u b j e c t 广义的数据挖掘过程包括从数据选择开始到把最终结果提供给用户的整个过程，可以用 下面的五个步骤来说明数据挖掘的过程： 1 ) 确定业务对象： 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结果 l 基于粗糙集的属性约简算法研究 是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性，是 不会成功的。 2 ) 数据准备： 数据准备包括以下三个内容：数据的选择；搜索所有与业务对象有关的内部和外部数据 信息，并从中选择适用于数据挖掘应用的数据。数据的预处理；研究数据的质量，为进一步 的分析做准备，并确定将要进行的挖掘操作的类型。数据的转换；将数据转换成一个分析模 型。这个分析模型是针对挖掘算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖 掘成功的关键。 3 ) 数据挖掘： 对所得到的经过转换的数据进行挖掘。除了完善选择合适的挖掘算法外，其余一切工作 都能自动地完成。 4 ) 结果分析： 解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定，通常会用到可视化技 术。 5 ) 知识的同化： 将分析所得到的知识集成到业务信息系统的组织结构中去。 1 1 3 数据挖掘的方法 图1 2 数据挖掘的基本过程和主要步骤 f i g u r e l 2t h eb a s i cd a t am i n i n gp r o c e s sa n dm 句o rs t e p s 数据挖掘可以从很多不同的角度进行分类，如根据所发现知识的种类不同分为：分类规 则挖掘、聚类规则挖掘、关联规则挖掘、序列模式分析。根据挖掘技术的不同可分为以下几 种【2 】： 1 ) 决策树： 2 内蒙古大学硕士学位论文 决策树是在信息论基础上对数据进行分类的一种方法。首先，通过一批已知的训练数据 建立一棵决策树；然后，利用建好的决策树，对数据进行预测。决策树的建立过程可以看成 是数据规则的生成过程。典型的算法有i d 3 算法等。 2 ) 神经网络： 神经网络建立在自学习的数学模型之上，它可以对大量的、复杂的数据进行分析，并可 以完成对人脑来说极为复杂的模式抽取及趋势分析。神经网络系统由一系列我们称之为节点 的类似于人脑神经元一样的处理单元组成。典型模型有b p 网络等。 3 ) 相关规则： 相关规则是一种简单却很实用的关联分析规则，它描述了一个事物中某些属性同时出现 的规律和模式。相关规则分析就是依据一定的可信度、支持度、期望可信度、作用度建立相 关规则。典型算法有a p r i o r i 算法等。 4 ) k 均值聚类： l 卜均值聚类是一种无指导的聚类方法，通过适当选取k 个初始聚类中心，将每个点分 派到与自己距离最近的聚类中心所代表的类中，然后由每个类中所包含的点计算出新的聚类 中心，重复这个聚类过程，直到中心不再移动。 5 ) 遗传算法： 遗传算法是借鉴生物界的自然选择和遗传机制而产生的搜索算法，由定长的字符串组成 的种群借助于复制、交叉、变异等遗传操作不断进化，从而找到问题的最优解或次优解，当 求解问题的规模很大时，遗传算法有突出的优势。 6 ) k n e a r e s t 邻近： 邻近就是彼此距离很近的数据。依据“d oa sy o u rn e i g h b o r sd o 的原则，k - n e a r e s t 邻近 方法认为：邻近数据必然有相近的属性或行为，可以通过某特定数据的k 个邻居的平均来预 测它的某个属性或行为。 7 ) 联机分析处理： 联机分析处理主要通过多维的方式来对数据进行分析。它不同于传统的联机事务处理应 用。联机事务处理应用主要是用来完成用户的事务处理，如民航订票系统、银行储蓄系统等 等，通常要进行大量的更新操作，同时对响应时间要求比较高。而联机分析处理主要是对用 户当f j 及历史数据进行分析。典型的应用如银行信用卡风险的分析与预测、公司市场营销策 略的制定等，主要是进行大量的查询操作，对实时性要求不高。 3 基于粗糙集的属性约简算法研究 1 2 粗糙集 粗糙集理论是波兰数学家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 l t h e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a ) 的问世，标志着粗糙集理论及其应用的研究进入了活跃时则3 1 。 粗糙集理论在信息科学的应用主要有两大类【4 】：一类是无决策的分析，内容主要包括数 据压缩、约简、聚类与机器发现等；另一类是有决策的分析，内容主要包括决策分析、规则 提取等，当然也可用于对原始数据的预处理，如数据压缩与约简等。作为处理不确定性和不 精确性问题的一种数学工具，粗糙集理论近年日益受到国际学术界的重视。 1 2 1 粗糙集理论研究对象 粗糙集的研究对象是由一个多值属性集合描述的一个对象集合，每个对象都有一个值作 为其描述符号，对象、属性和描述符是表达决策问题的三个基本要素。这种表达形式也可以 看成一个二维表格，表格的行与对象相对应，列对应于对象的属性；各行包含了表示相应对 象信息的描述符，还有关于各个对象的类别成员的信息。通常，关于对象的可得到的信息不 一定足以划分其成员类别。换句话说，这种不精确性导致了对象的不可分辨性。给定对象间 的一个等价关系，即导致由等价关系构成的近似空间的不分明关系，粗糙集就用不分明对象 类形成的上近似和下近似来描述。这些近似分别对应了确定属于给定类的最大的对象集合和 可能属于给定类的最小的对象集合。下近似和上近似的差是一个边界集合，它包含了所有不 能确切判定是否属于给定类的对象。 1 2 2 粗糙集理论的特点 粗糙集具有以下一些特点： 首先，粗糙集不需要先验知识，模糊集和概率统计方法是处理不确定信息的常用方法， 但这些方法需要一些数据的附加信息或先验知识，如模糊隶属函数和概率分布等，这些信息 有时并不容易得到，粗糙集分析方法仅利用数据本身提供的信息，无须任何先验知识。 其次，粗糙集是一个强大的数据分析工具，粗糙集能表达和处理不完备信息；能在保留 关键信息的前提下对数据进行化简并求得知识的最小表达；能识别并评估数据之间的依赖关 4 内蒙古大学硕士学位论文 系，揭示出概念简单的模式；能从经验数据中获取易于证实的规则知识，特别适用于智能控 制。 最后，粗糙集理论有很强的生命力，粗糙集理论的生命力在于它具有较强的实用性，从 诞生到现在虽然只有二十几年的时间，但已经在许多领域取得了令人鼓舞的成果，例如数据 挖掘、人工智能、专家系统、决策支持系统、模式识别与分类、故障检测等。 1 2 3 粗糙集理论的研究现状 由于粗糙集理论自诞生之日起就有着鲜明的认知学特征和应用背景，且其依赖的模型 信息系统是计算机科学，特别是人工智能领域众多研究方向中问题的描述框架，所以到 上个世纪八十年代末，该理论受到国际上许多计算机科学家和人工智能专家的重视。1 9 9 5 年 a c mc o m m u n i c a t i o n 将粗糙集理论列为计算机学科的新研究课题，并在i n t e m e t 上定期发布 电子公告。这些举措加速了粗糙集理论在世界范围内的发展与交流。经过二十余年的发展， 粗糙集理论及其应用受到世界范围内的广泛关注，许多国际会议将其列为专题。至今已有大 量有关粗糙集的论文在世界各地的学术杂志上发表，也有不少专著阐述粗糙集理论的各个方 面。国内2 0 0 3 年5 月2 6 日2 9 日在重庆邮电学院举办了中国第三届粗糙集与软计算暨第九 届粗糙集、模糊集、数据挖掘与粒度计算国际学术会议( r s f d g r c 2 0 0 3 ) 。 自粗糙集理论提出以来，对粗糙集理论的研究，主要集中在粗糙代数【5 】【6 】【7 】【8 】、粗糙集拓 扑及其性质吲【10 1 、粗糙逻辑及近似推理的逻辑工具【l l 】【1 2 】等方面。这些研究结果充分论述了 粗糙集与模糊集【1 4 】、证据理论与粗糙集理论之间的关系【1 5 】，也建立了粗糙集与概率逻辑、粗 糙集与模态逻辑之间的关系。 知识约简是粗糙集理论的核心内容之一，其主要思想是在保持分类能力不变的前提下， 消除信息系统( 决策表) 中不必要的知识，导出最终的决策或分类规则。目前，静态的属性 约简算法主要有两类：一类是基于信息熵即s h a n n o n 熵的启发式算法【1 6 】【1 7 1 ，该算法的基本思 路是：先计算出核，而后根据其它属性的重要程度依次在核的基础上添加属性或者根据决策 属性对条件属性的依赖程度依次剔除掉那些对分类不产生影响的属性，直到使所得的属性集 与原信息系统( 或决策表) 的分类能力相同为止，但启发式算法往往不能得到系统的所有约 简。另一类是基于区分矩阵和区分函数构造的属性约简算法【1 8 】【1 9 】，这种算法的基本思路是：利 用区分矩阵导出区分函数，然后求解区分函数的析取范式，该范式中的每一个析取项即为系 统的一个约简。这种算法直观，易于理解，能够计算出核与所有约简。不足之处是区分矩阵 中会出现大量的重复元素，降低了属性约简算法的效率。 5 基于粗糙集的属性约简算法研究 1 2 4 研究内容的提出 众所周知，粗糙集理论是一种处理含糊和不精确问题的新型数学工具【2 0 1 。它从新的角度 认识知识，认为知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。通过引 入不可区分关系作为粗糙集理论的基础，并在此基础上定义了上、下近似等概念，使得粗糙 集理论能够有效地逼近这些概念。在粗糙集理论的计算问题中，知识约简是核心内容之一， 其目的是在保持分类能力不变的前提下，去掉数据表中冗余的属性和属性值，以便提高系统 潜在知识的清晰度。这在处理大规模数据尤其是海量数据时是非常必要的。否则冗余信息所 带来的时间和空间上的代价将是巨大的。另外，由于数据规模的增大，因而时间效率就显得尤 为重要，本课题正是从提高属性约简效率入手，对基于区分矩阵的属性约简算法和基于互信 息的属性约简算法进行研究。大数据量带来的另一个问题就是决策表往往是不相容的，这给 属性约简带来了新的挑战，本课题针对这个问题，在深入研究现有不相容决策表算法【2 i 】的基 础上，提出了一种适合普遍决策表的算法。 1 3 本文研究内容及结构安排 1 3 1 本文研究内容 本文就1 2 4 提出的问题进行了研究，主要包括以下内容： 1 对经典的粗糙集理论进行了系统的学习和研究 2 分析传统区分矩阵属性约简算法的不足，提出一种基于属性重要性和区分矩阵的改进 算法。 3 面对不相容决策表，本文在讨论了前人的方法后，指出他们的局限性，并在此基础上 提出一种新的基于等价划分的改进算法。 4 决策表的最终目的是生成决策规则，为作出合理正确的决策做准备。因此，得到决策 表的所有约简就是必要的了，本文在总结了约简的特点和经典约简算法的基础上，提出一种 基于树的约简算法，该方法的优点主要是能够得到决策表的所有约简，并且利用树的特点， 可以使用计算机来实现。 1 3 2 本文的结构安排 除本章绪论外，本文的结构安排如下： 第二章介绍粗糙集的基本理论，主要介绍一些属性约简过程中用到的基本概念。 第三章介绍了常用的基于区分矩阵的约简算法和基于属性重要性的约简算法，利用这两 6 内蒙古大学硕士学位论文 个算法的优点，提出一种改进的基于属性重要性和区分矩阵的约简算法。 第四章针对不相容决策表，本章首先讨论了前人算法的局限性，并指出产生这种局限性 的原因是：没有从整体上去考虑决策表，而只是从单个对象上去考虑。基于这种原因，本文 提出一种基于u i n d ( c ) 的等价划分的约简算法。并将该方法与其他针对不相容决策表的方法 进行了比较。 第五章本文最后，提出一种基于树的约简算法，该算法的提出，主要是为了找到决策表 的所有约简，并且能够适用于各种决策表( 相容与不相容的) 。 第六章对前面各章的总结，并提出了未来研究的方向。 7 基于粗糙集的属性约简算法研究 第二章粗糙集理论 粗糙集理论是一种处理含糊和不精确问题的新型数学工具。其主要思想是在保持分类能 力不变的前提下，通过知识约简，导出问题的决策或分类规则。本章主要介绍属性约简理论 中经常用到的一些基本概念【3 1 ，作为以后各章节的基础。 2 1 经典粗糙集理论 2 1 1 知识、分类与知识库 一般认为，知识是人类通过实践认识到的客观世界的规律性的东西，是人类实践经验的 总结和提炼，具有抽象和普遍的特性。知识是信息经过加工处理、解释、选择和改造而形成 的。粗糙集理论认为，知识是对对象进行分类的能力。 定义l 设非空集u 是我们感兴趣的对象组成的有限集合，称为论域。 定义2 任何子集x c u ，称为u 中的一个概念或范畴。为规范化起见，我们认为空集也 是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识；u 上的一族划分称为关 于u 的一个知识库。 定义3 设r 是u 上的一个等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成的 集合，【x 】r 表示包含元素x e u 的r 等价类。 定义4 一个知识库就是一个关系系统h u ，r ) ，其中u 为非空有限集，称为论域，r 是 u 上的一族等价关系。 定义5 设尸r ，且p ，则n p ( p 中所有等价关系的交集) 也是一个等价关系，称为p 上的不可区分关系，记为i n d ( p ) ，r 有 x i n d ( p ) = n 阢】r ，这样u i 1 1 d ( p ) ( 即等价关系i n d ( p ) l 拘 腊 所有等价类) 表示与等价关系族p 相关的知识，称为k 中关于u 的p 基本知识( p 基本集) 。 为简单起见，我们用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。 特别地，如果q r ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等概 念或q 初等范畴。事实上，p 基本范畴是拥有知识p 的论域的基本特性。换句话说，它们是 知识的基本模块。 下面我们讨论两个知识库之间的关系 定义6 令k = ，p ) 和k = ，q ) 为两个知识库。若i n d ( p ) = i n d ( q ) ，即u p = u q ，则称k 和 8 内蒙古大学硕士学位论文 k ( p 和q ) 是等价的。因此，当k 和k 有同样的基本范畴集时，知识库k 和k 中的知识都是 使我们确切地表达关于论域的完全相同的事实。 这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事 实。对于k = ，p ) 和k = ( u ，q ) 两个知识库，当i n d ( p ) c i n d ( q ) 时，我们称知识p ( 知识库k ) 比 知识q ( 知识库k ) 更精细，或者说q 比p 更粗糙。当p 比q 更精细时，我们也称p 为q 的 特化，q 为p 的推广。这意味着，推广是将某些范畴组合在一起，而特化则是将范畴分割成 更小的单元。 2 1 2 粗糙集 粗糙集是建立在分类的机制上的，它将分类理解为在特定空间上的等价关系，而等价关 系构成了该空间的划分。所以粗糙集的定义依赖于等价关系和等价类，这里我们先介绍等价 关系和等价类的概念 1 2 】。 七 定义7 若x i ( i k ) 为u 的子集，且x i ( i k ) ，x i n 玛= ( i j ) ，i = u ，则称 x i i i k ) j 筒 为u 的划分f 2 2 1 。 划分即是分类，即将研究对象分成不同类，这些类之间互不相交，且任何对象均包含于 某一类中。比如对于小轿车可以用不同颜色来分类，也可以用不同性能来分类，可以用价格 来分类，也可以用生产地区分类。有了不同的分类才可能有针对性的决策。 定义8 设r uo u ，称r 为u 上的关系。当( x ，y ) r 时，称x , y 有关系r ，当( x ，y ) 仨r 时，称x , y 无关系r 。 定义9u 上的关系r 称为等价关系，若满足以下性质： 自反性：( x i ，x i ) r ( x iu ) ； 对称性：( x i , x j ) er 时，( x j ，x i ) er ( x i ，x j eu ) ； 传递性：( x b x j ) r ，( x j ，x k ) e r ，贝, l j ( x i ，x k ) r ( x i ，x j ，x k eu ) ； 有了等价关系，我们就可以定义粗糙集了。等价关系可以将对象集分类，从认知的角度 来看，人们需要通过分类去认识那些不能用分类精确表示的对象集，这种集合称为粗糙集。 定义1 0 设x c u ，r 为u 上的一个等价关系，当x 能表达成某些r 基本范畴的并时， 称x 是r 可定义的；否则称x 为r 不可定义的。r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可定义集不能在这个知识库中定义，r 可定义集也称为r 精确集，而 r 不可定义集也称为r 非精确集或r 粗糙集( r o u g hs e 0 。 9 基于粗糙集的属性约简算法研究 为将粗糙集精确的表达出来，我们引入上近似( u p p e ra p p r o x i m a t i o n ) 和下近化a ( 1 0 w e r a p p r o x i m a t i o n ) 。 定义l l 设u 是对象集，r 是u 上的等价关系。称，r ) 为近似空间，由，r ) 产生的等 价类为： u r = x i r l x i e u ) ，其中 x j 】r _ ( x i ，均) r 。 _ 。：? 一 对于任意x c u ，记r ( x ) - - x i l x d r c _ x ，r ( x ) = ( x i l x i r ax ；e ， 称尺( 均为x 的下近似集，r ( ) ( ) 为x 的上近似集。x 的下近似集也称为x 的r 正域， 记作p o s r ( x ) ，它是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；r ( x ) 是那些 根据知识r 判断可能属于x 的u 中元素组成的集合；n e g r ( x ) = u 一尺( x ) ，称为x 的r - 负域， 它是由那些根据知识r 判断肯定不属于x 的u 中元素组成的集合；b n r ( x ) = r ( x ) 尺( x ) 称为 x 的r 边界域，它是那些根据知识r 既不能判断肯定属于x 又不能判断肯定属于x ( 即u x ) 的u 中元素组成的集合。 由定义可以看出，x 的下近似集r ( ) ( ) 是u 中包含在x 中的最大可定义集，x 的上近似 集r 是u 中包含x 的最小可定义集，因此，若尺( x ) = r ( x ) ，称x 为可定义的集合，否则 称x 为粗糙集。 因为粗糙集只是近似地在u 上用r 等价类进行了定义，为此引入粗糙近似精度来量化粗 糙集的不精确性。 定义1 2 设x c u ，x ，则称o r ( x ) = c a r d ( r ( x ) ) c a r d ( r ( x ) ) 为x c u 的近似精度。其 中，c a r d ( p ) 表示集合p 中的元素个数。 精度昧( x ) 用来反应我们对于了解集合x 的知识的完全程度。显然，对每一个r 和x c u 有o o r ( x ) - l 。当( x ) - l 时，x 的r 边界域为空集，集合x 为r 可定义的；当o r ( x ) i 时， 集合x 有非空r 边界域，集合x 为r 不可定义的。 用图2 1 描述上述定义更直观。 1 0 2 1 3 知识约筒与知识的依赖性 图2 1 粗糙近似 f i g u r e 21r o u g ha p p r o x i m a t i o n 本节着重介绍糨糙集理论中的两个基本问题：知识约简与知识依赖性噬i 。知识约简是研 究近似空间中每个等价关系是否都是必要的，以及如何删去不必要的知识。知识约简在信息 系统分析与数据挖掘等领域都有重要的应用意义。知识之间的依赖性决定知识是否可以进行 约简，根据依赖性所定义的知识的重要性往往是知识约简的重要启发式信息。 令r 为一族等价关系，p r ，如果i n d ( r ) = i n d ( r f p ) ，则称p 为r 中不必要的；否则称 p 为r 中必要的。如果每一个p r 都为r 中必要的，则称r 为独立的；否则称r 为依赖的。 定义1 3 设q c p 如果q 是独立的，且i n d ( q ) = i n d ( p ) 则称q 为p 的一个约简。显然p 可以有多种约简。p 中所有必要关系组成的集合称为p 的核，记作c o 州p ) 。 核与约简有如下关系： c o r e ( p ) = n r e d ( p ) 其中r e d ( p ) 表示p 的所有约菏。可以看出，核这个概念有两方面的用处：首先，它可以 作为所有约简的汁算基础因为核包含在所有的简式之中，并且计算可以直接进行；其次， 可解释为在知识约简时它是不能消去的知识特征集合。 在实际的应用中，一个分类相对于另一个分类的关系十分重要，因此我们将介绍知识的 相对约简( r e 砒i v er e d u e t ) 和相对核( r e l 乱i v ec o r e ) 酏j 概念。 令p 和q 为u 中的等价关系，q 的p 正域记为p o s “q ) ，e p p o s f f q ) = u f 彩，q 的p 正 x m i q 一 域是u 中所有根据分类u ，p 的信息可以准确地划分到关系q 的等价类中的对象集合。 令p 和q 为等价关系族，r e p ，如果 1 1 基于粗糙集的属性约简算法研究 p o s i n d ( p ) ( i n d ( q ) ) = p o s i n d ( p ( r ) ( i n d ( q ) ) ， 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。为简单起见，我们也用p o s p ( q ) 代 替p o s i 。d ( p ) ( i n d ( q ) ) 。如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或p 相对q 独立) 。 定义1 4 设s c _ p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p o s s ( q ) = p o s p ( q ) 。p 的q 约简简称为相对约简。p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相 对核，记为c o r e q ( p ) 。 相对核和相对约简的关系见下述事实： c o r e q ( p ) = l lr e d q ( p ) ，其中r e d q ( p ) 是所有p 的q 约简构成的集合。 定义1 5 知识的依赖性可形式化地定义如下：令k - ( u ，r ) 是一个知识库，p , q c r 。 ( 1 ) 知识q 依赖于知识p ( 记作p j q ) 当且仅当i n d ( p ) i n d ( q ) 。 ( 2 ) 知识p 与知识q 等价( 记作p 暑q ) 当且仅当p = q 且q j p 。 ( 3 ) 知识p 与知识q 独立( 记作p q ) 当且仅当p = q 与q p 均不成立。 有时候知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识p 导出的，部分 可导出可由知识的正域来定义。 定义1 6 令k = f d ，r ) 为一个知识库，且p , q _ c r 。当 k _ 所( q ) = i p o s p ( q ) l i u i 时，我们称知识q 是k ( o k 1 ) 度依赖于知识p 的，记作p j k q 。 当k = l 时，我们称q 完全依赖于p ；当o 。这与第一个过程得到的结果一致。 利用区分矩阵法的算法时间复杂度为o ( m x n 2 ) ，其中，1 1 为属性集合，m 为对象集合。 在面对大数据量的时候，算法的复杂度会成倍增长，因此该算法只适合小的数据集。但该算 法的优点是得到约简结果是完备的，决策表的所有约简都可以得到，这样为决策带来了方便。 3 2 基于属性重要性的约简算法 3 2 1 属性重要性的计算方法 一般来讲，一个决策表的知识约简不是唯一的，即对同一个决策表可能存在多个相对约 简。因为知识约简的目的是导出关于决策表的决策规则，约简中属性的多少直接影响着决策 规则的繁简，因此，人们期望找到具有最少属性的约简，l i p i d 、约简【17 1 。w o n g s k m 和 z i a r k o w 已经证明求信息系统的所有约简或最佳约简都是n p 难题【2 4 1 ，其原因是属性的组合 会产生爆炸，在人工智能领域，解决这一类问题的一般方法是采用启发式搜索2 5 1 ，通过运用 启发式信息来简化计算以找出最佳约简或次佳约简。 启发式的属性约简方法一般都是从系统的核属性出发，根据各属性的属性重要度从大到 小加入到被选择的属性集中，直到该集合是一个约简为止。常用的属性重要性的计算有下面 两种： ( 1 ) 根据依赖度的变化来定义： 定义2 3 设t 为一决策表，c ，d 分别为条件属性集和决策属性。对于任意属性a ec 的重 要性定义如下： s g f ( a , c ，d ) 一k ( c ，d ) - k ( c 一 a ) ，d ) ； 其中，k ( c ，d ) = c a r d ( p o s c ( d ) ) c a r d ( u ) ( 2 ) 根据信息熵来定义： 1 9 4 8 年s h a n n o n 提出并发展了信息论，研究以数学的方法度量并研究信息。通过通信后 。 1 8 内蒙古大学硕士学位论文 对信源中各种符号出现的不确定程度来度量信息量的大小【2 引。上面关于属性重要性的衡量， 是通过代数学的等价关系和集合运算来定义的，我们称之为粗糙集理论的代数表示。在代数 表示下，粗糙集理论的很多概念与运算的直观性差，人们不容易理解其本质。另外，在此表 示下，目前还没有关于知识约简的高效算法，同一问题在不同知识表示下的算法难度是不同 的。在这种情况下，苗夺谦，d u n t s c h 和g e d i g a 等从信息论的角度出发，建立起来知识与信 息熵的关系，引入了信息熵和条件熵来衡量属性的重要性。 定义2 4 知识p ( u p = x l ，x 2 x n ) ) 的信息熵h ( p ) 定义为： h ( p ) ：p ( x i ) 1 。g p ( x i ) ； i = l 其中p ( x i ) 为p 在论域u 上的划分x = ( x l ，x 2 x n ) 上的x i 的概率，i = l ，2 ，n 。 知识q ( u i n d ( q ) = y i ，y 2 y n ) ) 相对知识p ( u i n d ( p ) = x l ，x 2 x n ) ) 的条件熵h ( q p ) 定义 为： h ( q p ) ：p ( x i ) p ( y j x i ) l o g p ( y j x i ) ； i = l _ ，= l 其中p ( v x i ) 是条件概率，p ( y j x i ) = j y j f x d i x d ，i - - 1 ，2 ，n ，j = l ，2 ，m 。知识p 与q 的 互信息i ( p ；q ) 为：i ( p ；q ) = h ( q ) - h ( q p ) 。 运用信息熵研究知识约简可以得到以下结