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

哈尔滨t 程大学硕士学位论文 摘要 粗糙集理论是2 0 世纪7 0 年代发展起来的一种新的处理含糊性和不确定 性问题的数学工具，它是智能信息处理的一种重要方法，基于不可区分性思 想和知识简化方法。目前，获得高效、快捷的属性约简算法是该理论研究的 主要课题之一，高效的约简算法在信息系统分析与数据挖掘等领域具有重要 的应用意义。 本文在研究粗糙集理论的基础上发现由于信息系统中的决策规则存在相 容的和不相容的，导致决策表的相容性和不可相容性。而大多数决策表属性 约简算法在进行属性约简之前需要判断决策表的相容性。针对决策表的可相 容性和不可相容性，分别研究了相应代表的属性约简算法。相容决策表约筒 算法包括基于依赖度和重要度的属性约简算法和基于广义信息表的属性约简 算法；在不相容约简算法中，介绍了基于包含度的属性约简算法。通过分析 表明以上算法只能对相容和不相容决策表分别约简，浪费了时间，不具一般 性。为了解决这一问题，本文提出了基于决策熵的决策表属性约简算法，通 过实验分析，其实验结果与前三个算法结果一致。表明基于决策熵的属性约 简算法对决策表进行属性约简之前，不需要预先判断决策表是相容的或不相 容的，并且解决了经典粗糙集理论中属性约简的两种定义对不相容决策表约 简时结果不一致的问题，提高了效率，具有广泛性，达到了预期效果。 关键词：数据挖掘；粗糙集；属性约简；决策熵 哈尔滨工程大学硕士学位论文 a b s t r a c t r o u g hs e tt l l e o r yi san e wm a m e m a d e a lt o o lw l l i c hc a nt a e “ea m b i 嘶a n d 瑚c 刚础时d e v e l o p e d 觚mt h e1 9 7 0 s ni s 瓤嘶r t a mm e t h o do fi n t e l l e c t i v c i n f o r m a d o nl r a n s a e t i o n 、】v _ l l i c hb a s c do f 枷- d i s 吐n g i i i s ha n dt e c h n o l e d g e r e d u c t i o n a tp l 礤嘲嵋i t so n eo ft h e 岫r t a n tp r o b l e m so fe a l e u l a t i n gh i g l l e m c t i v e ，s h o n c ma t t r i b u t er e d d o na l g o f i t h m s , a n dt l 圮h i 曲e f f i c t i v er e d u e t i o n a l g o f i t h m sh a v e 嘶r t a n ta p p l i c a t i o ns i g n i f i c a n c ei ni n f o r m a t i o ns y s t e ma n a l y s i s a n dd a t al n i n i n g t h i sp a p e ri sb a s e d u g hs e t 也e 0 彤d u et 0t h e r ei s 碰；i s 蛐a n d i n c o n s i s k 帕c ei nd e c i s i o nr o l eo fi 嘶o r m a d o ns y s t e m , w l l i c hr c s u l 乜i n n s i s t e n e e a n di l l c o n s i s t e n o fd e c i s i o nt a b l e h o w e v e rm o s to fa t t r i b u t er e d u e t i o n 蛔f i t h m so fd e c i s i o nt a ：b l en e e dt oj u d g ew h e t h c rd e e i s i o nt a b l ei sc o n s i s t e mo r m c o m i s t e n tb e f b r ep i o g r e 鹞i n ga t t r i b u t er 洳f i o n a i i n i i l g 砒黜i s t e n to r m c o m i s t e n to fd e c i s i o nt a 【b l e 把s e a r c h e sr e p r e s c n 诅f i v ea t t r i b u t er e d u c t i o n a l g o f i t h m s 他s p e e f i v e l y c o n s i s t e n td e e i 妇t a b l ei n c l u d e s 蛆a l g o f i t h mo f a t t r i b u t er e d u c t i o nb a s e do nd e p e 】 1 d 吼a n di n l p o r t a l 肼a n d 缸蛔n t h mo f a t t r i b u t er e d u c t i o nb a s e do ng e r a l i z e di n f o 删i o nt a b l e ；w 蝴e 缸a l g o f i t h mo f a t t r i b u t e 佗d u e t i o nb a s e d 帆i n c l u s i o nd e g r e ei l lt h em c o m i s t e n to f d e c i s i o nt a b l e hl e a r n c dt h a ta b o v ea t t r i b u t er e d u c t i o na l g o f i t h m sm a yo n l yr e a u e ec 删妣n to r m c o m i s t e n td e c i s i o nt a b l er e ! 辨c t i v e l y w a s t i n go fm o 吼t i m e , a n d 血e yh a dn o t u n i v e r s a l i t y i no r d e r 协t a k l et h a t , ap r o p o s e da l g o f i t h mo fa t t r i b u t er e d u c t i o nf o r d c c i s i o nt a b l eb a s e d 钮咖p ) ，i sp o i n t 甜t h ee ) 【p e r i m e n tr e s e ta n da b o v eo n 髂 a r ea c c o r d a n tt l a r o u g ha n a l y z i n g t h en e wa l g o f i t h mn e e dn o tj l | d g ew h e t h e r d e c i s i o nt a b l ei sc o n s i s t e n to ri n c o n s i s t e mb e t o r ep r o g r e s s i n ga t l x i b u t er e d u c t i o n f o rd e e i s i o nt a b l 舔w h e nt l l e s ed e f i n i d o ma 弛u s e dt or e d u m 础i s t e n t d e e i s i o nt a b l e r e d u r 部u l 协c o i l l db ei n e o m i s t e n t ，“s o l v e st h i sp r o b l e ma n d a d v a n c e se f f i c i e n e y nh a su n i v e r s a l i t ya n d 佗a c h e s 锄t i e i p a t i v ee f f e c t 哈尔滨t 程大学硕士学位论文 k e ”o r d s ：d a t am i n i n g ；r o u g hs e t ；a t t r i b u t er e d u c e ；d e c i s i o ni n f o r m a t i o ne n t r o p y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：功年月夕日 啥尔滨工程大学硕士学位论文 1 1 数据挖掘概述 第1 章绪论 由于社会进入网络信息时代，计算机与网络技术迅猛发展起来，数据库 技术和数据库管理系统( d b m s ) 也开始广泛使用，商业、政府、科技等数 据库中存储的数据量急剧增大并且趋于分散，出现了“丰富的数据与贫乏的 知识”的现象。在这样的背景下，人们迫切需要新一代的技术和工具来开采 数据库中蕴藏的宝藏，使数据成为有用的知识，指导企业的技术决策和经营 决策，使企业在竞争中立于不败之地。另外，近十余年来，计算机和信息技 术也有了长足的进展，产生了许多新概念和新技术，如更高性能的计算机和 操作系统、数据仓库( d a t aw a r e h o u s e ) 、因特网( i n t e r a c t ) 、神经网络等。 在市场需求和技术基础这两个因素都具备的环境下，数据挖掘技术或称k d d ( 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 ) 的技术就应运而生了。随着数据挖掘研 究领域的不断拓展，传统的关系数据挖掘和事务数据挖掘已经发展到对空间 数据的挖掘。空间数据正在逐步成为各种信息系统的主体和基础，空间数据 是一类重要的、特殊的数据，有着比一般关系数据库和事务数据库更加丰富 和复杂的语义信息，包含着更丰富的知识。这样，尽管数据挖掘最初产生于 关系数据库和事务数据库，但是因为空间数据的特殊性，从空间数据库中挖 掘知识便很快引起了数据挖掘研究者的关注 1 1 1 什么是数据挖掘 数据挖掘( d a t am i n i n g ) ，也可以称为数据库中的知识发现，是指从大 量的原始数据中，提取用户感兴趣的知识的过程，这些知识是有价值的、隐 含的、事先未知的、潜在有用的。 数据挖掘的对象可以是数据库或数据仓库内容，也可以是其它数据源的 哈尔滨工程大学硕士学位论文 内容。数据挖掘是一种决策支持过程，它主要是基于人工智能、机器学习、 统计学技术，高度自动化地分析企业原有的数据，并做出归纳性的推理，从 中挖掘出潜在模式，预测客户的行为，帮助企业的决策者调整市场策略以便 减少风险，做出正确的决策”。 1 1 2 数据挖掘的基本任务 数据挖掘的任务主要是关联分析、分类分析、聚类分析、偏差分析、时 序模式分析和预测分析等。 ( 1 ) 关联分析( a s s o c i a t i o n a n a l y s i s ) 关联规则挖掘是r a k c s h a p w a l 等人首先提出的。两个或两个以上变量取 值之间存在的规律性称为关联。数据关联是数据库中存在的一类重要的、可 被发现的知识。关联可以分为简单关联、时序关联和因果关联。关联分析的 目的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阙值来度量 关联规则的相关性，并不断引入兴趣度、相关性等参数，使得所挖掘的规则 更符合需求。 ( 2 ) 分类分析( c l a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即 该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。 分类是利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则 描述和预测。 。 ( 3 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，使同一类中的数据彼此相似， 不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式， 以及可能的数据属性之间的相互关系。 ( 4 ) 偏差分析( d e v i a t i o n ) 数据库中的数据往往存在很多异常情况，而偏差中会包括很多有用的知 识，因此，发现数据库中数据存在的异常情况是非常重要的。偏差检验的基 本方法是寻找观察结果和它的参照之间的差别。 ( 5 ) 时序模式分析( t i m e - s e r i e sp a t t e r n ) 2 哈尔滨工程大学硕士学位论文 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归 一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时 间的不同。 ( 6 ) 预测分析( p r e d i c a t i o n ) 预测则是利用历史数据找出变化规律，建立模型，并由建立盼模型对未 来数据的种类及特征进行预测。预测关心的是精度和不确定性，通常使用预 测方差来度量n 一。 1 1 3 数据挖掘的方法 数据挖掘的方法主要有遗传算法、神经网络方法、统计分析方法、模糊 集方法、决策树方法、粗糙集方法等。 ( 1 ) 遗传算法 遗传算法是一种仿生全局优化方法，它是一种基于生物自然选择和遗传 机理的随机搜索算法。遗传算法具有的隐含并行性、易于和其它模型结合等 性质使得它在数据挖掘中加以应用 s u n i l 已经成功地开发了一个基于遗传算法的数据挖掘工具，利用此工具 对两个飞机失事的真实数据库进行了数据挖掘实验，实验结果表明遗传算法 是进行数据挖掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗 糙集等技术的结合方面上利用遗传算法优化神经网络结构，在不增加错误 率的前提下，删除多余的连接和隐层单元：用遗传算法和b p 算法结合训练 神经网络，再从网络提取规则等。但是遗传算法本身算法比较复杂，收敛于 局部极小的较早收敛问题还尚未解决。 ( 2 ) 神经网络方法 神经网络由于自身良好的组织适应性、并行处理、分布存储和高度容错 等特性非常适合解决数据挖掘之类的问题，因此近年来越来越受到人们的关 注。典型的神经网络模型主要分为三大类：以感知机、b p 反向传播模型、函 数型网络为代表的，其用于分类、预测和模式识别的前馈式神经网络模型； 以h o p f i e l d 的离散模型和连续模型为代表的，其分别用于联想记忆和优化计 算的反馈式神经网络模型：以a r t 模型、k o h o l o n 模型为代表的，其用于聚 3 哈尔滨工程大学硕士学位论文 类的自组织映射方法。神经网络方法的缺点是它的“黑箱”性，这使得人们 很难理解网络的学习和决策过程。 ( 3 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确 定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对 它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分 析。可进行常用统计( 求大量数据中的最大值、最小值、总和、平均值等) 、 回归分析( 用回归方程来表示变量问的数量关系) 、相关分析( 用相关系数来 度量变量间的相关程度) 、差异分析( 从样本统计量的值得出差异来确定总体 参数之间是否存在差异) 等。 ( 4 ) 模糊集方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别 和模糊聚类分析。系统的复杂性越高，其模糊性越强，一般模糊集合理论是 用隶属度来刻画模糊事物的亦此亦彼性。李德毅等人在传统模糊理论和概率 统计的基础上，提出了定性定量不确定性转换模型云模型，并形成了云 理论。 ( 5 ) 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的的分类 后，从中找到一些有价值的、潜在的信息。决策树的主要优点是描述简单， 分类速度快，尤其适合大规模的数据处理。最有影响和最早的决策树方法是 由q u i n l a n 提出的著名的基于信息熵的i d 3 算法。此方法存在的主要问题是： i d 3 是非递增学习算法；i d 3 决策树是单变量决策树，复杂概念的表达困难： 同性间的相互关系强调不够；抗噪性差。针对此类问题，曾出现了许多较好 的改进算法，如s c h l i m m e r 和f i s h e r 设计的i d 4 递增式学习算法；钟鸣、陈 文伟等提出的m l e 算法等。 ( 6 ) 粗糙集方法 粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集方法有 几个优点：不需要给出额外信息：简化输入信息的表达空间；算法简单，易 于操作。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数 据库管理系统和新发展起来的数据仓库管理系统，为粗糙集的数据挖掘奠定 4 哈尔滨工程大学硕士学位论文 了坚实的基础。但粗糙集的数学基础是集合论，难以直接处理连续的属性。 而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗糙 集理论实用化的难点。现在国际上已经研制出来了一些基于粗糙集的工具应 用软件，如加拿大r e g i n a 大学开发的k d d - r ：美国k a n s a s 大学开发的l e r s 等”l 。 1 2 粗糙集国内外研究现状 粗糙集理论是波兰数学家z p a w l a k m 于1 9 8 2 年最先提出的一个分析数据 的数学理论。在分类的意义下，租糙集理论定义了模糊性和不确定性的概念。 在此理论刚刚问世的几年里，由于理论还不成熟，因此没有受到国际计算机 学界的重视，当时主要在波兰等几个东欧国家进行了研究直至2 0 世纪8 0 年代末，粗糙集理论才引起了世界各国学者的关注。自1 9 9 2 年在波兰举行了 粗糙集理论的第一届国际研讨会以来，每年一度的国际粗糙集理论研讨会定 期在世界各国召开。可以说，目前粗糙集理论已经成为国际上数据挖掘研究 的热点。 目前，国外对粗糙集理论的研究和应用发展的都比较快，特别是1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其相关方法比较研究的论文集的出 版，推动了国际上对粗糙集理论和方法的深入研究1 9 9 2 年，在波兰召开的 第一届国际粗糙集研讨会，此次会议着重讨论了集合近似定义的基本思想及 其应用，其中租糙集环境下机器学习的基础研究是此次会议的四个专题之一 但是，参加这次会议的研究者较少，范围也不太广泛。于1 9 9 3 年在加拿大召 开的第二届国际粗糙集与知识发现研讨会上，其主题是粗糙集、f u z z y 集与 知识发现，极大地推动了国际上对粗糙集理论与应用的研究。于1 9 9 4 年在美 国召开的第三届国际粗糙集与软件研讨会上，广泛探讨了粗糙集与模糊逻辑、 神经网络、进化论等融合问题。 粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年第l l 期a c m w 通讯上 撰文，概括性地介绍了目前人工智能应用新技术之一的粗糙集理论的基本概 念，及其在知识获取和机器学习，决策分析、知识发现等领域的具体研究项 目和进展。尤其是1 9 9 5 年召开的第四届模糊理论与技术国际研讨会，在这次 5 哈尔滨工程大学硕士学位论文 会议上，针对粗糙集与模糊集合的基本观点与相互关系展开了激烈的讨论， 极大地促进了粗糙集的研究。1 9 9 6 年在日本东京召开了第五届国际粗糙集研 讨会，这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。1 9 9 9 年1 1 月在日本、2 0 0 0 年l o 月在加拿大又召开了第一届和第二届“粗糙集和计算 的当前趋势”学术会议，来自波兰、美国、加拿大、日本、挪威、俄罗斯、 乌克兰和印度等国家的研究人员参加了会议，会议阐述了当前粗糙集、模糊 集的研究现状和发展趋势，会议指出将着重在软计算、数据库、人工智能和 近似推理等理论和应用方面发展。目前，许多关于人工智能、模糊理论、信 息管理与知识发现等国际会议上经常可以看到涉及粗糙集的论文。 在国内，对粗糙集理论的研究和应用仍处在起步阶段。1 9 9 6 年王珏，苗 夺谦等在 模式识别与人工智能发表了关于粗糙集理论与应用的论述，介 绍了粗糙集理论的主要原理、基本算法和在知识发现、决策分析等方面的应 用，开始了国内粗糙集理论的研究和应用；1 9 9 8 年曾黄麟编写的粗集理论 与应用是国内第一本关于粗糙集理论的专著；常犁云等对属性的值约简算 法做出了改进，提高了样本分类的正确率；韩祯祥、张琦等将粗糙集方法应 用于电力系统故障诊断( 警报处理) ，效果良好。对粗糙集理论研究比较深入 和透彻的是苗夺谦、王珏等，他们不仅提出了基于粗糙集的多变量决策树的 构造方法，而且还把粗糙集中的概念和运算从代数角度提升到信息角度，为 人们深刻理解粗糙集理论的本质以及寻找高效的知识约简算法奠定了基础。 国外目前在粗糙集领域的研究主要集中在约简的优化算法、粗糙集理论 和模糊理论、粗糙集理论同神经网络理论等其它人工智能技术的结合、粗糙 逻辑等课题上“”。本文中，对于粗糙集的约简算法的研究正是当前粗糙集领 域中一个非常重要的课题。 1 3 本文的研究意义及其主要内容 现实世界中存在大量的不确定性，任何将世界中某些方面模型化的方法 都应该包括处理不确定性的机制。在理解实体或数据的意义或性质时可能存 在不确定性。空间数据挖掘中需要不确定性处理的一个基本方面是空间对象 之间的拓扑关系。空间对象之间的拓扑关系包含的是各种不同的空间实体之 6 哈尔滨工程大学硕士学位论文 问的关系，空间关系，例如相交、邻近、重叠等，都已经得到应用，用来发 现空间数据中的关联规则和属性泛化“”。 本文对粗糙集模型处理空间关系的空间数据属性约简算法进行改进，此 算法可以处理空问数据中的不确定性关系，在保持信息分类能力不变的前提 下进行数据属性约简。与已有的粗糙集分类算法相比，算法提高了分类准确 性，同时改进了空间属性约简方法，该算法对决策表进行属性约简之前，不 需要预先判断决策表是相容的或不相容的，并且解决了经典粗糙集理论中属 性约简的两种定义对不相容决策表约简时结果不一致的问题，具有广泛性。 1 4 本文的组织结构 本文共分五章，主要内容如下： 第l 章，对数据挖掘理论进行了系统论述；阐述了粗糙集理论在国内外 的研究现状；介绍了本文的研究意义及其主要内容：介绍了本文的组织结构。 第2 章，在租糙集基本理论中系统介绍了知识和不可区分关系；信息系 统；粗糙集的定义及表示知识的简化，包括约简知识的绝对简化和知识的相 对简化；知识的依赖；粗糙集的应用前景。 第3 章，主要介绍了具有代表性的属性约简算法，包括基于相容决策表 和不相容决策表的属性约简算法。 第4 章，提出的基于决策熵的属性约简算法是本文的重点首先阐述了 决策熵基本理论并对其分析，然后提出了一种基于决策熵的属性约简算法， 此算法解决了要预先知道约简的决策表是相容的还是不相容的问题。最后对 此算法进行性能分析。 第5 章，通过使用相容决策表、不相容决策表的实例对第3 章的属性约 简算法和基于决策熵的属性约简算法进行分析，最后对实验结果进行比较。 7 哈尔滨工程大学硕士学位论文 第2 章粗糙集理论基础 2 0 世纪7 0 年代初，波兰学者z p a w l a k 和波兰科学院、华沙大学的逻辑 家们组成了研究小组，对信息系统的逻辑特性进行了长期基础性的研究他 们针对从实验中得到的以数据形式表述的不精确性、不确定性和不完整性的 信息和知识，进行了分类分析，为粗糙集理论的产生奠定了基础。z p a w h a k 教授针对c x f r e g e 的边界线区域思想提出粗糙集概念，发表了经典论文，宣 告了粗糙集理论的诞生。到了2 0 世纪8 0 年代末，粗糙集理论引起了各国学 术界的重视，许多数学家、逻辑学家和计算机研究人员等对粗糙集理论和应 用产生了极大兴趣并且进行了大量的研究工作“”。 2 1 粗糙集的基本理论 2 1 1 知识和不可区分关系 假设研究的对象组成的是一个非空有限集合，称此集合为论域，记作阢 即【，o 是要讨论的论域。 知识是u _ k 的任何子集称为u 中的一个概念，知识则是u 中的任何概念 族。 对于论域阢如果存在吐的子集的集合d f 幻，x 2 ，蜀 ，使得v x t ， 髯e d ，对于f ，石n 竭= o ；x _ ，u x 2 0 u x 阢则称d 是论域u 上的一个划 分。其中石m ，i = - 1 ，2 ，撑。划分构成了u 中的一个概念族，也就形成 了一个知识。租糙集理论就是对那些能形成划分的知识感兴趣。 令剐黾论域趾的一个关系，如果r 同时满足如下性质： ( 1 ) ( 自反性) v x e 仉( z ，x ) r ； ( 2 ) ( 对称性) v x ，y e 玑若q ，y ) r ，则，工) 足； ( 3 ) ( 传递性) v x ，y ，z 阢若( 工，y ) ( 弘：) 置，则( 工，z ) 矗 哈尔滨t 程大学硕士学位论文 胄。 则称关系r 是吐的等价关系。 等价关系和划分的关系由划分的定义可知，由u 上的等价关系胄所生成的 等价类作为元素所构成的集合，就是u _ k 的一个划分，即由等价关系可以得 到一个划分。 同样，一个划分中的任意集合都当作一个等价类，就形成了一个等价关 系。也可以说，等价关系与划分的概念是一一对应的：一个等价关系可以导 出一个划分，一个划分也可以导出一个等价关系。 一个由等价关系r 的所有等价类u r 构成的集合是u j = 的一个划分，形成 了一个知识，称为且初等知识。刷均等价类为知识的r 初等范畴。 知识库就是一个关系系统k 三( 阢足) 。其中剐黾u j = 的一族等价关系。 ，震，且p = = o o ，则n p ( ，中所有等价关系的交集) 也是一个等价关系，称 为p 上的不可区分关系，记为i n d ( p ) 。 由这个定义可知，不可区分关系也是等价关系，它是由等价关系族的交 集构成的一个等价关系。论域u 在等价关系n 和您下的划分记为u r ，和u r 2 ， 不可区分关系i n d ( r j ，r 2 ) 对u 划分的结果为c 所n d ( r j ，r 2 ) ，它由u r l 和 u r 2 叠加而成，如图2 1 所示。 n ( 1 ) u i r ，( 2 ) u i r 2( 3 ) u i n d ( ，力) 图2 i 不可区分关系划分结果的构成 如果x l e 嘲砌， ，并且x 2 e x 砌，) ，则对于p 中任何的等价关系来r 说，工j 和却都是位于同一个等价类中。也就是说，只根据p 中的等价关系， 是不能区分出x ，和x 2 的。因此由u i n d ( 尸) 构成的集合是u 上的一个划分。 用u i p 来代替u i n d ( p ) 。同单个的等价关系一样，这个等价关系族p 也形 成了一个知识，称为p 的基本知识。尸的等价类为知识p 的p 基本范畴。不 9 哈尔滨工程大学硕士学位论文 可区分关系的等价类形成了知识的基本模块，处于等价类中的任何对象，都 无法区分。也可以说，等价类构成了知识的粒度，而这种知识的粒度正是租 糙集理论中产生不确定性的原因“”。 2 1 2 信息系统 知识表达系统也称为信息系统，是用关系表的形式表达的。 给定一个信息系统s 可表示为p 矾a ，i t , 户，其中，u 是对象的集 合，即论域；a 是属性的有限集合；净_ 。i r a ，阮表示属性口的值域；办u a - - - , v 是一个信息函数，它给属于u 的对象附属性值，即对于任意a e a 和x u 有 ，( 工，口) 砌 2 1 3 粗糙集的定义 设u 是非空的论域，震是一个不可区分关系或称等价关系；4 = ( 玑置) 称为一个近似空间；u i r 表示胄中所有等价类的集合，或称u 的分类；【硼。 表示r 中包含x 的等价类；r 中的等价类称为基本集；基本集的有限并集称 为可定义集。 定义2 1 设x 是( ，的子集，x c _ u ，则z 可用可定义集的术语从中定 义：4 中包含在x 中的最小可定义集称为中工的下近似，表达式为星黔伽u i 【圈r j f ) 。a 中包含z 的最大可定义集称为彳中j 的上近似，表达式为 足y = 投ui 【羽n 脬m 。( 星匕p , x ) 称为粗糙集， 定义2 2 定义b n d ( j ) = 兄r 毽工称为j 的边界域：p o s ( j d 嗵墨 称为x 的正区域；n e g ( j d = u - r x ，称为x 的负区域。 ， 若把r 看成分类的知识。x 的正区域中的目标可以确定地分类为j 的成 员；负区域中的目标可以确定地判断不属于五即属于x 的补集j 鼠边界区 中的目标无法确定地判断属于x 或。刀一。 下近似和上近似以及边界域的定义可以用图2 2 来清楚的表示。 图2 2 中，由曲线围起来的部分就是我们需要表达的某个子集五由里 边粗黑线围起来的就是这个子集的下近似，外边租黑线围起来的就是这个子 1 0 哈尔滨工程大学硕士学位论文 。 集的上近似，位于两者之间的就是边界域。小方格就是由知识r 所产生的等 价类。它也就表示了知识置的粒度性。集合x 无法用小方格准确地表示出来， 但是，它可以由两个集合：下近似和上近似粗略地表示m ，。 i 、l i | hll l- i (。r _ _ _ _ i i1 7 1ii昃字 iv 一 r 厂 _ 图2 2 粗糙集近似定义示意图 粗糙集的表示只是由两个精确集近似地表示。这种近似的大小是可以刻 画的。由上图可以看出粗糙集的不精确性是由于边界域的存在而引起的。边 界域越大，其精确性越低。如果边界域为空集，则粗糙集就成为精确集。 租糙集理论中，不精确的数值不是预先假定的，而是通过表达知识不精 确性的概念近似计算得到的，这种不精确性的数值表示的是有限知识( 知识 的粒度性) 的结果。粗糙集理论不需要预先指定一个精确数值去表达不精确 的知识。 图2 3 形象的说明粗糙集的基本概念工是置可定义的，当且仅当 量转瓦r ，简称可定义的。z 对于r 是粗略的，当且仅当瓦z _ r x o nn ) 、 p n l x 【 p p pn 、- p ， n n 图2 3 粗糙集基本概念示意图 l l 哈尔滨工程大学硕士学位论文 2 1 4 约简 2 1 4 绝对约简 给定的一个知识库，是否可以用较少的知识表达同样的概念。也就是说， 删除知识库中的一些知识是否又使它能够与原来的知识库具有相同的表达能 力，这就是知识的简化，约简n ”。 令r 为一族等价关系，r e r ，如果h a d ( 月) = m d ( 且一 r ) ) ，则称足为 r 中不必要的；否则称屁为r 中必要的。 如果置为r 中不必要的，则胄和( j 卜似 ) 能够表达相同的知识，表明 置在r 中的作用不大，删除它不影响对原来系统的表达。 如果每一个r e r 都为r 中必要的，则称r 为独立的；否则称r 为依赖 的。如果r 为独立的，则说明r 中的每个等价关系足都是必要的，都不可省 略，即胄具有最小性。 设q p ，如果q 是独立的，并且i n d ( q ) i l l d ( p ) ，则称q 为p 的 一个约简。 一 根据这个定义可以知道，约简有两个方面的性质：首先，约简所表达的 对系统的划分与原来的知识库所形成的划分是完全一致的，即约简所表达的 知识和原来的知识具有相同的表达能力；其次，就是独立性，即最小性，约 简是能够表达原来的知识库的最小集合，约简里不可再进行约简。 p 中所有必要关系组成的集合，称为p 的核，记为c o r e ( p ) w 核与约简的关系是c o 陀( p ) = nr e d ( p ) ，其中r e d ( p ) 表示p 的所有 约简。 核这个概念的作用是作为所有约简计算的基础，因为核包含在所有的约 简之中，并且计算可以直接进行；可解释为在知识约简时它是不能消去的知 识特征集合。 例2 1 ；设 ，- ( ur ) 是一个知识库，其中u x ，x 2 ，妇 ，r = r ， 彤，r 3 ，等价关系且，彤，飓有下列等价类： u r = 聊，斯，巧 ， 勋，x s ， 句) ， 拓，x 7 ， 1 2 哈尔滨工程大学硕士学位论文 u r 2 = 茸，匀，奶， ， 砌，和，却，耘 ， ( j ) r 产“却，鄹) ， x d ， x 2 ，x 7 ，x s ， x 3 ，斯，。 关系i n d ( r ) 有下列等价类：u i n d ( r ) = 铆，x j ， x 2 ，劫 ， x 3 ) ， ， 孙) ， x 7 ”。 因为u i n d ( 震一 g l ) = “习。x 5 ， x 2 ，x 7 ，x s ， 幻) ，b 4 ) ， ，i n d ( r ) ，关系置，为丑中必要的。 因为u i n d ( 胄一 9 2 ) ) = 轴研，x s ，胁 ，伽 ，) ， x t = u i n d ( 盖) ，关系岛为震中不必要的。+ 因为u i n d ( 五- 飓) ) = “柳，x s ， 却，x s ) ， 幻) ，伽 ，( 砧) ，缸7 = v i n d ( r ) ，关系如为r 中不必要的。 这表明通过等价关系 凡，岛，飓 的集合定义的分类与根据 r j ，彤) 或 r 1 ，r s 定义的分类相同，即表明该系统的知识可以通过u i n d ( r j ，飓) ) 或u i n d ( 飓，r 3 ) 来表达。 为了得到r = r ，彤，飓 的约简，检验 r ，飓) 和 r ，岛) 是否为独立 的。因为硎n d ( ( r l ，彤 ) = = u i n d ( 而) ，且酾n d ( 局。岛 ) = u i n d ( 硒) ， 所以 尺，五2 是独立的，即 r i ，r 2 为置的一个约简：又因为c 历n d ( 皿， 奶) ) ：= u i n d ( r d 且u i n d ( 局，硒 ) = u i n dc r y ) ，所 r t ，如 是独 立的，即 g t ，岛 也是胄的一个约简。 这样，r 有两个约简 r i ，r 2 和 r ，彤 ，一个核c o 陀( r ) = r ，r 2 ) u r ， 岛) _ r ，) i “。 2 1 4 ，2 相对约简 在应用时，个分类( 不可区分关系) 相对于另一个分类的关系十分重 要，上面的概念只是一个分类中所表达的知识的粒度性。下面来看看以下概 念。 q 的尸正域是p o s p ( q ) = u ( 层研x v q 。 q 的p 正域是【，中根据分类，p 的信息可以准确地划分到知识q 的等 价类中的对象集合。即q 的，正域是由知识p 所产生的等价类所组成的集合， 这些等价类能够完全地属于知识q 。 哈尔滨工程大学硕士学位论文 若p o s p ( q ) = p o s p - ( r ) ( q ) ，称r 为p 中q 不必要的；否则r 为 户中q 必要的。 如果p 中的每个矗都为q 必要的，则p 为q 独立的。 相对约简是设s o _ p ，称s 为p 的q 相对约简，当且仅当s 为p 的q 独 立子族，且p o s s ( q ) - p o s p ( q ) 。由这个定义可以知道相对约简一方面 可以表示原来的知识，即和原来的系统的分类能力一样；另一方面它又不包 含重复的知识，每个知识都是必要的。也就是说，相对约简是能表示原有知 识的最小集。显然相对约简有多个。 相对核是p 中所有q 必要的原始关系所组成的集合，称为尸的q 核。 记为c o r e q ( p ) 。 相对核与相对约简的关系是c o r e q ( ，) = n r e d q ( p ) ，其中r e d q ( p ) 是所有尸的q 相对约简构成的集合。即相对核是所有相对约简的交集。 相对核这个概念的作用是作为所有相对约简计算的基础，因为相对核包 含在所有的相对约简之中，并且计算可以直接进行；也可解释为它在知识约 简时是不能消去的知识特征集合。 例2 2 ：设j p ( u ，p ) 是一个知识库，其中泸伽，x 2 ，x s ，p = 五， 恐，如) ，等价关系震，飓和岛有下列等价类： u r i = 伽，劫，斯，幻，x 7 ， 勋，靳 ， u r 尸t 讧| ，x 3 ，x px s ，讧2 ，x ，x 7 ，x 心、， 础户 体，扔，拓) ， x 2 ，x 7 ，x s ， x 3 ，x 4 ) 等价关系q 有下列等价类：v q = x l ，扔，x 6 ， 却，x 4 ， 却，x 7 ， 却 。 于是，由，导出的分类为u p = - 忸j ，x 5 ， 幻，和 ， x 2 ，拗 ， x 6 ， x z 。 可以得到：p o s p ( q ) = i x l ，砧，和，奶，勘，x l 现在，从p 中去掉胄j ，得到硎( p - r i ) - - x l ，嘲， 幻，柳) ，f 功，x 7 ， x a ， x 6 。 于是有p o s ( p - r d ( q ) = 工，勋，却，x a ，) = # p o s p ( q ) ，所以， 且，是p 中必要的。 从p 中去掉飓，得到凹( 只 彤 ) = 缸，奶，粕， 幻，却) ， 勋，x 8 ， 缸7 ) ) 。 1 4 哈尔滨丁程大学硕士学位论文 于是有p o s ( p - r 2 ) ( q ) = x ，幻，x 4 ，幻，砧，x 7 f p o s p ( q ) ，所以， 彤是p 中不必要的。 从尸中去掉毋，得到u ，( p - 飓 ) = “柳，幻，x 4 ，x s ， x 2 ，x a ， 耜， x 7 于是有p o s ( p 岛) ( q ) = 彬= p o s p ( q ) ，所以，飓是p 中必要的。 这样，p 的q 核就是 r i ，奶) ，它也是p 的q 约简“一。 2 1 5 知识的依赖性 知识的依赖性可以形式化地定义如下：令j 净( 玑r ) 是一个知识库， p c _ r ，q c r 。则： 知识q 依赖于知识p ( 记作p q ) ，当且仅当i n d ( p ) i n d ( q ) 知识尸与知识q 等价( 记作p m q ) ，当且仅当p j q 且q j ，。 知识p 与知识q 独立( 记作尸9 ) ，当且仅当p j q 且q = p 均不成 立。 显然，p f q ，当且仅当i n d ( p ) - - i n d ( q ) 。 当知识q 依赖于知识p 时，也说知识q 是由知识p 导出来的。 有时候知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识 p 导出的，部分可导出，可由知识的正域来定义。 令肛( 矾矗) 为一知识库，且p ，q c _ r 。当扣i p ( q ) 4 p o s p ( q ) i i u i 时， 称知识q 是k ( o | | 1 ) 度依赖于知识p 的，记作p j q 。 当k = l 时，称q 完全依赖于p ；当0 k l 时，称q 粗糙( 部分) 依赖于 p ： 当k - - 0 时，称q 完全独立于户。 由依赖性的定义可知，当p j q 时，则由q 导出的分类u q 的正域覆 盖了知识库的k x l 0 0 个元素；另一方面，只有属于分类正域的元素能被唯 一的分类，即对象的k x l 0 0 可以通过知识p 划入分类u q 的模块中m ，。 2 2 粗糙集的应用及展望 粗糙集不仅自己可以独特的挖掘知识，而且可以和其它的数据挖掘算法 1 5 哈尔滨丁= 程大学硕士学位论文 结合起来，从而产生了学多混合数据挖掘算法，大大开拓了数据挖掘的算法 和技术，丰富了数据挖掘的工具。除了研究，人们也在积极寻找粗糙集在数 据挖掘中的应用，如r s e s 系统，该系统是基于粗糙集理论上研制的数据挖 掘系统，里面提供了粗糙集的属性约简算法和规则提取，可以找到最佳约简 集和近似约简集，并可以提出规则。粗糙集目前研究得到了很大的发展，主 要方向如下： ( 1 ) 粗糙集的属性约简。约简是粗糙集用于数据分析上的重要方面，但 是求最小约简是n p 问题，大都采用启发式算法； 夺重要性方法：根据重要性来对属性进行约简； 根据布尔运算：此方法可以求出所有最小约简，但是只适合小数据集； 夺遗传算法：b j o r v a n d 和k o r m o r a s k i 用遗传算法来求最小约简。 ( 2 ) 粗糙模型的扩展。粗糙集理论用于数据挖掘时会碰到噪音数据、数 据缺失、大数据量的一系列经典模型处理不理想的情况，于是出现了扩展的 模型： 可变精度模型：有一定容错能力，在一定情况下退化为经典模型； 相似模型：可以处理数据库中的缺失值： 粗糙逻辑：在粗糙集的基础上建立粗糙逻辑。 ( 3 ) 多方法的融合。 粗糙集和神经网络的结合，加快神经网络的速度； 和遗传算法的结合来处理大数据集。 总之，粗糙集理论采用概念的上、下近似来处理模糊性，并通过相应的 数学公式来计算，它是完全由数据决定的，具有很强的客观性。粗糙集理论 以其独特的优势逐渐赢得越来越多的关注，在理论研究方面也日趋成熟，并 在很多领域都取得了较为