（计算机软件与理论专业论文）基于概念格模型的粗糙集约简方法研究.pdf

基于概念格模型的粗糙集约简方法研究 摘要 约简和核是粗糙集理论中的重要研究课题，受到广泛关注。现有的约简算 法存在着以下一些问题：无法保证结果的完备性；不能保证得到最小约简；空 间开销大：时间复杂度高等。 概念格描述了概念间的泛化一例化关系以及内涵和外延之间的关系，是一 种完备的知识表现形式。概念格与粗糙集都是以等价类作为基本构件，因而存 在紧密的内在联系。 本文在讨论概念格与粗糙集关系的基础上，研究并提出了基于概念格模型 的求解约简与核的方法，主要工作如下： 概述了概念格和粗糙集合模型的相关研究。 研究了基于概念格的粗糙集表示方法，提出了相关的性质定理。 提出了基于概念格的信息系统和决策表约简算法a r b l ，实现了属性及属 性值约简，并能得到所有约简。 将简化概念格模型引入约简的求解过程，提出构造算法s i m p g 。简化概念 格通过省略与约简求解无关的结点，缩减了概念格的规模，提高了建格的时间 和空间性能。 在简化概念格的基础上，提出了基于简化概念格的约简求解算法r b s l ， 该算法可以得到核所有的约简，并判断决策表的一致性。 在上述研究基础上，实现了基于概念格求解约简的原型系统。 关键词：数据挖掘，决策表，粗糙集，概念格，核，约简 t h er e s e a r c ho fr o u g hs e t sr e d u e tb a s e do n c o n c e p tl a t t i c e a b s t r a c t r e d u c ta n dc o r ea r et h eh o t s p o t si nr o u g hs e t st h e o r y t h ee x i s t e dr e d u c t a l g o r i t h m sh a v ef o l l o w i n gp r o b l e m s ：t h e yc a n tm a k es u r eo ft h ec o m p l e t e n e s so f r e s u l ta n dc a n ta s s u r et oo b t a i nt h es m a l l e s tr e d u c t ；t h e yo f t e nn e e dl a r g es p a c e ， a n dh a v eb a dp e r f o r m a n c e c o n c e p tl a t t i c ed e s c r i b e st h er e l a t i o no fg e n e r a l i z a t i o n s p e c i a l i z a t i o nb e t w e e n c o n c e p t sa n dt h er e l a t i o n s h i pb e t w e e ni n t e n s i o na n de x t e n s i o n i t i sac o m p l e t e f o r mo fk n o w l e d g er e p r e s e n t a t i o n b o t hc o n c e p tl a t t i c ea n dr o u g hs e t sa r eb a s e do n e q u i v a l e n c ec a l s s ，s ot h ec o m p a c tr e l a t i o ne x s i t sb e t w e e nt h e m t h i sd i s s e r t a t i o nd i s c u s s e sa n dr e s e a r c h e st h er e l a t i o n s h i pb e t w e e nc o n c e p t l a t t i c ea n dr o u g hs e t s ，t h e np r e s e n t st h er e s o l u t i o no fr e d u c ta n dc o r eb a s e do nt h e c o n c e p tl a t t i c e t h ec o n t e n to ft h ed i s s e r t a t i o ni s a sf o l l o w s ： r e l a t e dw o r k so nc o n c e p tl a t t i c ea n dr o u g hs e t st h e o r ya r es t a t e dg e n e r a l l y t h er e p r e s e n t a t i o no fr o u g hs e t sb a s e do nc o n c e p tl a t t i c ei sd i s c u s s e di nd e t a i l ， a n dr e l e v a n tp r o p e r t i e sa r ep r e s e n t e d t h er e d u c t a l g o r i t h mo fi n f o r m a t i o ns y s t e ma n dd e c i s i o nt a b l eb a s e do n c o n c e p tl a t t i c ei sp r e s e n t e da sa r b l t h i sa l g o r i t h mc a np r o c e s sa t t r i b u t er e d u c t a n dv a l u er e d u c t ，a n di tc a ng e ta l lt h er e d u c t s s i m p l i f i e dc o n c e p tl a t t i c ei si n t r o d u c e dt ot h ep r o c e s so fr e d u c tr e s o l u t i o n ，a n d t h ec o n s t r u c t i o na l g o r i t h ms i m p gi sp r e s e n t e d s i m p l i f i e dc o n c e p tl a t t i c er e d u c e t h es c a l eo fo r i g i n a lc o n c e p tl a t t i c et h r o u g hc u t t i n gt h en o d e si r r e l e v a n tt ot h e r e d u e ta n dc o r e ，a sar e s u l t ，t h ee f f i c i e n c yo fc o n s t r u c t i n gc o n c e p tl a t t i c ei sg r e a t l y i m p r o v e d b a s e do ns i m p l i f i e dc o n c e p tl a t t i c e ，t h ea l g o r i t h mo fr e d u c tr e s o l u t i o nb a s e d o ns i m p l i f i e dc o n c e p tl a t t i c ei sp r e s e n t e da sr b s l ，t h i sa l g o r i t h mc a ng e tt h ec o r e ， a l lt h er e d u c t s ，a n dt h ec o n s i s t e n c yo fd e c i s i o nt a b l ea tt h es a m et i m e b a s e do nt h er e s e a r c h e ss t a t e da b o v e ，t h ep r o t o t y p es y s t e mo fr e d u c t r e s o l u t i o nb a s e do nc o n c e p tl a t t i c ei si m p l e m e n t e d k e y w o r d s ：d a t am i n i n g ，d e c i s i o nt a b l e ，r o u g hs e t s ，c o n c e p tl a t t i c e ，r e d u c t ，c o r e 表2 1 表2 2 表3 1 表4 1 表4 2 表4 3 表5 1 表5 2 表5 3 一个决策表 区分矩阵 上下文示例 决策表例1 例1 的属性值约简结果 a r b l 算法实验结果 表格清单 决策表例2 s i m p g 算法与g o d i n 算法性能比较 r b s l 算法实验结果 1 4 1 4 2 1 3 1 3 3 3 4 3 8 4 0 4 1 插图清单 粗糙集合示意图 上下文对应的h a s s e 图 例1 对应的概念格 去掉可缺属性c 后的概念格 完备概念格 s i m p g 算法构建的简化概念格 系统功能 实验系统主界面 模块1 一一基于概念格的约简求解 输入数据集文件及相关信息 结果输出一一所有约简 结果输出一一属性值约简 模块2 一一基于简化概念格的约简求解 结果输出一一所有约简，核属性及一致性 9 2 1 3 l 3 3 3 9 3 9 4 3 4 4 4 4 4 5 4 5 4 6 4 6 4 7 1 1 1 2 1 2 l 2 3 4 5 6 7 8 2 3 4 4 5 5 6 6 6 6 6 6 6 6图图图图图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金世工些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明井表示谢意。 学位论文作者签字：川如签字日期：炒占年占月7 日 学位论文版权使用授权书 本学位论文作者完全了解 金胆些友堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 盒世王些盘堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权f s ) = 麓i = 曩签字日期：喝年b 月7 日签字日期：形1 年 竿簇誓意作者毕业后去向：离歉也j 言至移网犯分芎 t 作单位： 。 o 叫 ) 雨b 毛：碲) 嘲 m ( 7 | 致谢 值此论文完成之际，首先要衷心感谢我的导师胡学钢教授在我的研究生就 读阶段给予的悉心指导和帮助。胡老师以他在数据挖掘领域深厚的理论基础和 严谨治学，实事求是的学术风范为我们的学习研究树立了优秀的榜样。三年来， 胡老师诚恳、宽容和强烈的责任心和谆谆教导给我留下了深刻的印象，终身难 忘。 同时，感谢计算机学院人工智能与数据挖掘实验室的所有老师给予的建议 和帮助。 另外还要感谢我的同学们以及师兄师姐给予的关心，支持和启发。 感谢合肥工业大学研究生部及计算机与信息学院的王新生老师、徐静老师 和各位院系领导对我的帮助与支持。 最后感谢家人对我一如既往的支持与关爱，是他们为我提供了良好的学习 环境，并给予在我遇到困难的时候给予我最多信一t l , 、勇气和力量。 作者：王听娅 2 0 0 6 年5 月 1 1 数据挖掘概述 1 1 1k d d 与数据挖掘 第一章绪论 随着信息技术的发展，指数级激增的数据量迫切地需要转化成有用的知识， 而且数据库和数据仓库技术的迅速发展，使得从潜在、隐性的数据中发现有用 的知识和模式成为可能。在这样的技术和经济背景下产生了k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ，数据库中的知识发现) 1 , 2 1 和d m ( d a t am i n i n g ，数据 挖掘) 3 1 ，它们已经被广泛地应用到科学研究、金融、保险、医疗保健、司法 和制造等各个行业。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第1 1 届国际人工智能联合会 议上首次提出的，这届学术会议上举行了以k d d 为主题的学术讨论，随后相 继在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年举行了k d d 的专题讨论会。随着对k d d 的深 入研究以及k d d 在许多领域的广泛成功的应用，k d d 已经成为当今计算机科 学与技术领域研究、应用的热点领域之一。 k d d 定义为从数据中识别有效的、新颖的并且可能是有价值的可理解的模 式的非平儿过程【29 1 ；它是知识信息处理的关键问题之一，还有很多和这一术语 相近似的术语，如数据挖掘( o m ) 、数据分析( d a t a a n a l y s i s ) 、数据融合( d a t a f u s i o n ) 以及决策支持( d e c i s i o ns u p p o r t i n g ) 等。数据挖掘是k d d 过程中的一 个特定步骤【3 “，运用具体的算法从数据里提取模式 3 2 1 ，它是k d d 过程中最核心 的部分，数据挖掘算法的好坏直接影响到所发现知识的好坏，目前大多数研究 都集中在数据挖掘算法上。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程p ”， 提取的知识表示为概念、规则、规律、模式等形式。一般来说，一个典型的数 据挖掘过程可以分成四个阶段，即数据预处理，建模，模型评估及模型应用。数 据预处理阶段主要包括数据的理解，属性选择，连续属性离散化，数据中的噪 声及丢失值处理，实例选择等。建模包括学习算法的选择，算法参数的确定等。 模型评估进行模型的训练和测试，对得到的模型进行评价。这三个阶段是循环 往复的过程，直到得到用户满意的模型为止。在得到满意的模型后，就可以运 用此模型对新数据进行解释。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理 和空间数据分析。通过数据挖掘，可以从数据库中提取有趣的知识、规律或高 层信息，并可以从不同角度观察或浏览。发现的知识可以用于决策、过程控制、 信息管理、查询处理，等等。因此，数据挖掘被信息产业界认为是数据库系统 最重要的前沿之一，是信息产业最有前途的交叉学科。 1 1 2 数据挖掘的主要任务 数据挖掘旨在从大型数据库中提取隐藏的预测性信息，以便于理解和观察 的形式反映给用户，并给出基于知识的决策分析意见和结论。下面介绍数据挖 掘的几种重要任务： 1 数据约简 目的是对数据进行浓缩，给出它的紧凑描述。其中属性选择一直是数据约 简的一个重要研究方向。属性选择的目的是找到满足特定标准的最小属性子集。 当前的属性选择算法主要各种搜索算法，贪婪算法，粗糙集模型以及神经网络， 遗传算法等。其中粗糙集理论是属性选择的有力武器之一，它提出了能够保持 分类能力不变的最小属性子集一一约简的概念，并给出了约筒计算的一般方法， 从而为属性选择问题提供了一种极具针对性的理论模型。 2 分类 分类在数据挖掘中是一项非常重要的任务，分类的目的是找到一个分类函 数或分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个，从 而实现对数据的分类。分类问题被广泛应用于疾病诊断，银行信贷等领域。当 前研究的分类模型主要有贝叶斯( b a y e s ) 络，决策树( d e c i s i o nt r e e ) ，神经网 络( n e u r a ln e t w o r k ) ，粗糙集合( r o u g hs e t s ) ，统计方法( s t a t i s t i c s ) ，遗传算 法( g e n e t i ca l g o r i t h m s ) 等。其中决策树由于其准确率高和计算量相对小，成 为应用最广泛的方法。神经网络方法主要是b p 算法，b p 算法本质上是一种非 线形判别函数。粗糙集理论是一种新的分类方法，其主要原理是在对数据库泛 化的基础上，根据对象的属性值的不同将对象分成不同的等价类，然后找出具 有相同分类能力，而且简化的属性集合，进而将获得的知识以规则的形式表示 出来。 3 聚类 聚类是根据客体属性集对一系列末分类客体进行类别的识别，按照相似性 分成若干类别，即“物以类聚”。聚类的目的是使属于同一类别的个体之间的距 离尽可能的小而不同类别的个体问的距离尽可能的大，即聚类应该使类内个体 洲的相似性最大，而类别间的相似性最小。 4 关联规则发现 2 所谓关联规则，是指数据对象之间的相互依赖关系，而发现关联规则的任 务就是从数据库中发现那些确信度( c o n f i d e n c e ) 和支持度( s u p p o r o 都大于给定 值的强规则( s t r o n gr u l e ) 。关联规则的经典算法是a p r i o r i 算法。a p r i o r i 算法 通过多次迭代来找出所有的频繁项目集，在第k 次迭代过程中找出所有的频繁 k 项目集l k 。常见的关联规则发现算法还有a i s ，s e t m ，d h p 等。 5 序列模式 序列模式是指在多个数据序列中发现共同的行为模式。序列模式发现算法 的框架与发现关联规则相同，也是一个逐步迭代的过程，在每次迭代中，包括 了候选频繁项集的生成和在事件序列中识别候选项集两个过程。迭代直到不能 再产生频繁项集为止。例如，对序列数据库d 中的某顾客，序列模式发现问题 就是在该数据库中寻找所有的频繁序列或所有的最长频繁序列。r a g r a w a l 称 最长频繁序列为序列模式( s e q u e n t i a lp a t t e r n ) 。 1 1 3 数据挖掘方法 数据挖掘的方法多种多样，而且每年都会出现新的数据挖掘模型。在实际 应用中，为了发现某类知识，常常要综合运用多种方法。目前，常用的数据挖 掘方法主要有以下几种： 1 粗糙集方法。粗糙集理论是近年来才兴起的用于研究不精确、不确定性 知识的学习、表达归纳的方法。粗糙集理论对知识作了一整套的形式化描述， 通过引入不可分辨关系、等价类、上近似、下近似等概念考察知识表达中不同 属性的重要性，通过分类找出属性间的关联规则。 2 决策树方法。即根据不同的特征，以树型结构表示分类或决策集合，进 而产生规则和发现规律的方法。决策树是分类研究最常用的模型之一，利用树 中从根到叶子结点的路径表示分类规则。决策树方法的最大优点是可理解性， 比较直观，缺点是处理复杂的数据时，受噪音数据等因素导致出现过多碎片。 决策树最早起源于概念学习系统c l s ，后来发展到i d 3 方法，在i d 3 算法的基 础上，又演化出处理连续属性的c 4 5 算法，能处理数据空缺值的c a r t 和 c h a i d 等方法，目前出现的两种新算法s l i q 和s p r i n t ，能在非常大的训练 集中进行决策树归纳，并可以处理符号属性和连续性属性 3 6 , 3 7 。 3 统计分析法。统计分析法利用对象的有限信息和不确定性信息进行统计 分析，进而评估、预测空间对象属性的特征、统计规律等知识，包括回归分析、 相关分析及主成分分析法等。该方法比较容易理解，对结果描述精确。然而， 当利用大规模训练集学习时，统计分析的评估代价变得很敏感。随着训练集规 模的增长，代价增长更快。 4 神经网络。神经网络法主要通过大量神经元构成的网络来实现自适应 非线性动态系统，并使其具有分布存储、联想记忆、大规模并行处理、自学习、 自组织、自适应等功能。常用于进行分类和聚类知识以及特征的挖掘。神经网 络方法的缺点是“黑箱”性，人们难以理解网络的学习和决策过程。 5 遗传算法。遗传算法是一种模拟生物进化过程的算法，可对问题的解空 间进行高效并行的全局搜索，能在搜索过程中自动获取和积累有关搜索空间的 知识，并可通过自适应机制控制搜索过程以求得最优解。 6 聚类分析法。聚类分析法根据实体的特征对其进行聚类或分类，进而发 现数据集的整个空间分布规律和典型模式的方法。常用的聚类方法有k m e a n ， k m e d o i d s 方法、e s t e r 等提出的基于r 一树的数据聚焦法。 数据挖掘的方法和技术有很多，粗糙集方法是其中比较有影响的方法之一， 它在k d d 中得到了成功的应用，引起了广泛的关注。本文将对粗糙集理论进 行深入的研究，着重探讨粗糙集中的约简求解方法。 1 2 粗糙集合理论概述 1 2 1 粗糙集合的研究背景 随着信息系统的规模以空前的速度不断增长，从大量的数据中高效地挖掘 出有用的信息，已经越来越成为一种挑战。由于实际的数据中常常包含着噪声， 不够精确甚至不完整，采用传统的数据统计方法对其分析处理需要预先对数据 之间的关系进行估计和假设，数据处理的效果往往不理想。而粗糙集合理论是 一种研究不确定、不完整知识的有效方法，它不需要任何先验信息，即可对数 据进行分析处理，从中发现隐含的知识，揭示潜在的规律。 粗糙集合理论是由波兰数学家p a w l a k z 于1 9 8 2 年首先提出。八十年代， 许多波兰学者对粗糙集合理论及其应用进行了坚持不懈的研究，其中主要对粗 糙集合理论的数学性质及逻辑系统进行了广泛的研究 2 1 , 2 2 , 2 3 , 2 4 , 2 5 1 。同时他们 也开发了一些应用系统。但由于最初的研究成果大多是以波兰文字发表在 “b u l l e t i no ft h ep o l i s ha c a d e m yo fs c i e n c e s ：m a m e m a r i e s ”或“b u l l e t i no ft h e p o l i s ha c a d e m yo fs c i e n c e s ：t e c h n i c a ls c i e n c e s ”上，该项研究局限于东欧各国， 当时并未引起国际计算机学界的重视。直到八十年代末，粗糙集合理论才逐渐 引起世界各国学者的注意。1 9 9 1 年p a w l a k 发表了专著“r o u g hs e t s t h e o r e t i c a l a s p e c t so fr e a s o n i n ga b o u td a t a ” 2 0 l ，奠定了粗糙集合的理论基础。同时，随着 1 9 9 2 年s l o w i n s k ir 主编的关于粗糙集合应用及其与相关方法比较研究的论文 集的出版，推动了国际上对粗糙集合理论与应用的深入研究，掀起了粗糙集合 理论的研究高潮。近几年来，粗糙集合理论已广泛地应用于机器学习、数据库 知识发现、决策支持与分析、专家系统、智能控制、模式识别等领域。 目前，在许多关于人工智能、模糊理论、信息管理与知识发现等国际学术 4 会议上经常可以看到涉及粗糙集合的论文。 粗糙集与k d d 关系密切，为k d d 提供了一种新的方法和工具。粗糙集可 以支持k d d 的多个步骤，如数据预处理、数据约简、规则生成等。 1 2 2 粗糙集合的研究现状及应用发展 粗糙集主要用于研究不完整、不精确知识的表达、学习与归纳。在分类的 意义下，它定义了模糊性和不确定性的概念。作为一种数学理论，它使用等价 类来形式化的表示分类。为了对知识的确定程度进行描述，粗糙集理论引入了 上近似和下近似的概念，并以这些概念来定义粗糙度。 粗糙集合理论从新的视角对知识进行了定义，把知识看作是关于论域的划 分，从而认为知识是具有粒度( g r a n u l a r i t y ) 的。认为知识的不精确性是由知识 粒度太大引起的。为处理数据( 特别是带噪声、不精确或不完全数据) 分类问 题提供了一套严密的数学工具，使得对知识能够进行严密的分析和操作。又由 于数据挖掘的深入研究和一些成功的商业运作，使得粗糙集理论和数据挖掘有 了天然的联系，粗糙集在知识上的定义、属性约简、规则提取等理论，使得数 据库上的数据挖掘有了深刻理论基础，从而为数据挖掘提供了一种崭新的工具。 粗糙集不仅自己可以独特的挖掘知识，而且可以和其他的数据挖掘算法结合起 来，从而产生了学多混合数据挖掘算法，大大开拓了数据挖掘的算法和技术， 丰富了数据挖掘的工具。 除了理论研究，人们也在积极寻找粗糙集在数据挖掘中的应用，如r s e s 系统，政系统是基于粗糙集理论上研制的数据挖掘系统，提供了粗糙集的属性 约简算法和规则提取，可以找到最佳约简集和近似约简集，并可以提出规则。 另外，还有，r e g i n a 大学开发的k d d r 系统，被广泛用于医疗诊断、电信业 等领域。还有美国k a n s a s 大学开发的l e r s ( l e a r n i n g f r o me x a m p l e sb a s e do n r s ) 系统，在医疗诊断、社区规划、全球气象研究等方面都有应用。 粗糙集是种软计算方法，它的简单实用性是令人惊奇的，粗糙集合能在 创立后的不长时间内得到迅速应用是因为它能处理各种数据以及数据的不精确 性和模棱两可的情况；它能求得知识的最小表达和知识的各种不同颗粒层次； 它能从数据中揭示出概念简单，易于操作的模式；它能产生精确而又易于检查 和证实的规则，特别适于智能控制中规则的自动生成。 粗糙集合能有效处理以下问题：不确定或不精确知识的表达；经验学习并 从经验中获取知识；不一致信息的分析；根据不确定，不完整的知识进行推理； 在保留信息的前提下进行数据化简；近似模式分类：识别并评估数据之间的依 赖关系。 粗糙集合目前的研究得到了很大的发展，主要方向如下： 1 粗糙集的数学性质。主要讨论粗糙集代数与拓扑结构以及粗糙集的收敛 性i j 刮等问题。 2 粗糙模型的扩展。粗糙集理论用于数据挖掘时会碰到噪音数据、数据缺 失、大数据量的一系列经典模型处理不理想的情况，于是出现了扩展的模型。 如：可变精度模型1 3 9 】一一有一定的容错能力，在一定情况下退化为经典模型； 相似模型【4 0 】一一可以处理数据库中的缺失值。 3 粗糙逻辑。在粗糙集的基础上建立的r o u g h 逻辑。 4 有效算法的研究。包括决策规则的提取算法，属性约筒算法，粗糙集基 本并行算法，以及与粗糙集有关的神经网络和遗传算法等。而约简是粗糙集用 于数据分析上的重要方面，属性约简算法一直以来是粗糙集理论及其应用研究 的重要内容，也是本文研究的主要内容。 5 多方法的融合。主要有：粗糙集台与神经网络的结合，加快神经网络的 速度；与遗传算法的结合来处理大数据集。 总之，粗糙集理论的应用前景很广阔，不但可以用于构造新型的系统，而 且关键在于它能够优化现有的许多算法。大数据集、高效约简算法、并行计算 以及混合算法研究等问题仍是粗糙集在数据挖掘中需要探讨的问题。 1 3 本文组织结构 本文在研究粗糙集合理论的基础上，分析并讨论了概念格与粗糙集的关系， 并提出了基于概念格模型的求解约简与核的方法。 本文由七个部分组成： 第一章简述了数据库中的知识发现以及数据挖掘的产生背景和研究现况， 并概述了粗糙集的产生发展和研究应用的基本情况。 第二章阐述了粗糙集合理论的基本思想，引入粗糙集中的基本定义，并对 粗糙集合理论中知识约简的定义、方法作了详细介绍。 第三章主要介绍概念格的基本知识，探索了概念格的发展过程，简要说明 了几种构建概念格的算法，并分析了概念格和粗糙集的内在联系。 第四章论述基于概念格的约简表示及求解。首先提出使用概念格来解决粗 糙集中的约简问题，并建立基于概念格的粗糙集合模型。在此基础上提出了基 于概念格的约简算法。 第五章讨论基于简化概念格模型的约简求解算法。通过构建简化概念格缩 减完备概念格的规模，并在此基础上进行约简与核的求解。 第六章中介绍本文的实验系统。 最后在第七章中对本文工作进行了总结并展望未来的研究。 第二章粗糙集合理论 半日糙集理论( r o u g hs e t s ，也称为r s 理论) 是由p a w l a k 于1 9 8 2 年提出的， 段理论从保持信息系统分类能力不变的角度出发，提出了“约简”和“核”两 个重要的概念，据此来描述海量信息系统中的最关键属性，并建立了相应的理 论基础。粗糙集合作为一种新的处理不确定性的有效数学工具，在计算机科学 与技术领域发挥了越来越重要的作用，已引起了研究人员的广泛注意i ”，1 8 ，1 9 】。 目前已经在人工智能，知识与数据发现，模式识别与分类，故障检浏等方面得 到了较为成功的应用。 由于k d d 中所涉及到的数据库大多是有噪音的、不完全的，这使得采用 传统的机器学习方法进行发现和描述存在较大的困难。而粗糙集合理论提供了 一套严格处理k d d 中最基本的分类问题的数学方法，通过对数据的分析，生 成确定与可能形式的规则。另外，半日糙集合理论包括了知识的一种形式模型， 这种模型可将知识定义为不可区分关系的一个族，使知识具有了一种清晰的数 学意义，并且可使用数学方法来分析处理。这些因素使得粗糙集合理论有助于 k d d 的研究。 本章阐述了粗糙集合中的基本概念和定义，重点讨论了粗糙集合中的知识 约简，介绍了知识约简的一些经典算法，最后介绍了一些粗糙集合的扩展模型。 2 1 粗糙集合的基本知识 2 1 1 近似空间的概念 基本粗糙集合理论认为知识是人类和其他物种所固有的分类能力。分类是 人类的最基本的智能行为，是推理、学习与决策中的关键问题。因此，粗糙集 合理论重点讨论对对象进行分类的能力。这里的“对象”指我们所能言及的任 何具体或抽象的事物，比如实物、状态、抽象概念、过程和时刻等，即知识必 须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部 分称之为所讨论的全域或论域( u n i v e r s e ) 。对于全域及知识的特性并没有任何特 别假设。事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集 ( f a m i l y ) ，这个族集提供了关于现实的显式事实，以及能够从这些显式事实中推 导出隐含事实的推理能力。为数学处理方便起见，在下面的定义中用等价关系 来代替分类【1 ”。 定义2 1 ：一个近似空间( a p p r o x i m a t es p a c e ) ( 或知识库) 定义为一个关系 7 系统( 或二元组) 弘( u ，r ) ，其中u g 是一个称为全域或论域( u n i v e r s e ) 的有 限集合，r 是u 上的等价关系的一个族集。 定义2 2 ：设p r 且p 0 ，p 中的所有等价关系的交集称为p 之上的一种 不可区分关系( i n d i s e r n i b i l i t yr e l a t i o n ) ，记作i n d ( p ) ，即：【x i n d ( p ) = n 【x r a k e r 定义2 3 ：给定近似空间弘( u ，r ) ，子集x g u 称为u 上的一个概念 ( c o n c e p t ) 。形式上，空集g 也视为一个概念；非空子族集p c _ r 所产生的不可区 分关系i n d ( p ) 的所有等价类的集合即u i n d ( p ) ，称为基本知识( b a s i c k n o w l e d g e 】，相应的等价类称为基本概念( b a s i cc o n c e p t ) ；特别地，若关系q e r ， 则关系q 就称为初等知识( e l e m e n t a r yk n o w l e d g e ) ，相应的等价类就称为初等概 念( e l e m e n t a r yc o n c e p t ) 。 本文中用大写字母p q ，r 等表示一个关系，用大写黑体字母p ，q ，r 等表 示关系的族集；m r 或r ) 表示关系r 中包含元素x u 的概念或等价类。为简 便起见，有时用p 代替i n d ( p ) 。 由定义可知，概念即对象的集合，概念的族集( 分类) 就是u 上的知识， u 上分类的族集可以认为是u 上的一个知识库，或说知识库即是分类方法的集 合。 2 1 2 粗糙集合中的基本概念 传统集合论认为，一个集合完全是由其元素所决定，一个元素要么属于这 个集合，要么不属于这个集合，即它的成员函数x ( x ) o ，1 。然而，现实中的 许多概念难以用传统集合来描述。为此，模糊集合对集合理论作了拓广，它通 过给成员赋予一个隶属度，即似( x ) e 0 ，l 】，使模糊集台能够处理一定的模糊和 不确定数据。但是其模糊隶属度的确定往往具有人为因素，这给其应用带来了 定的不便。传统集合论和模糊集合论都是把成员关系作为原始概念来处理， 集合的并和交就建立在其元素的隶属度的m a x 和m i t t 操作上，因此其隶属度必 须事先给定( 传统集合默认隶属度为l 或o ) 。 粗糙集合理论与传统集合理论有着相似之处，但是它们的出发点完全不 同。在粗糙集合中，成员关系不再是一个原始概念，认为不确定性与成员关系 有关，模糊性则表现在集合本身。下面先给出粗糙集合的基本定义，然后再定 义成员关系。 定义2 4 ：设集合x c u ，我们称r ( x ) = u yl ( y e u i n d ( r ) ) a ( y gx ) ) 为x 的下近似( 1 0 w e ra p p r o x i m a t i o n ) ，r ( x ) = u yi ( y u i n d ( r ) ) a ( y n x o ) 为x 的上近似( u p p e ra p p r o x i m a t i o n ) ，b n r ( x ) = r 。( x ) 一r ( x ) 为x 的边界或边界区域 ( b o u n d a r y ) 。 下近似包含了所有使用知识r 可确切分类到x 的元素，上近似则包括了所 8 有可能分类到x 的元素。显然，若b n r ( 刈o 或r ( x ) n ( x ) ，则集合x 就是 一个粗糙概念。边界区域是由不能肯定分类到这个概念或其补集中的所有元素 组成的。在粗糙集合中也采用了这样的概念，称p o s r ( x ) = r ( x ) 为集合x 的r 正区域( r p o s i t i v er e g i o n ) ，n e g r ( x ) = u - r ( x ) 称为集合x 的r - 负域( r n e g a t i v e r e g i o n ) 。 上述概念可用图2 1 表示如下： 鳓黼蕊黼黼黼 瀚黼 豳潮麓 l 豳 豳燃戮 ji x 戳酬 产三量； 牿 7 虬心 【边界) 厂k 芹、u 图2 1 粗糙集合示意图 在图中，整个区域为论域u ，每一小方格代表u i n d ( r ) 的一个元素，即等价类， 包含在概念x 中的、由若干个空表方格组成的区域为x 的下近似，由阴影方格 组成的区域为x 的边界，由边界及下近似组成x 的上近似。 可以看到，粗糙概念可以通过两个精确概念( 上近似和下近似) 来粗糙地 定义，这就使我们可以精确地表示不精确的概念。 定义2 5 ：设x c u 且x u ，集合x 的成员函数( m e m b e r s h i pf u n c t i o n ) ( 或 称粗糙成员函数( r o u g hm e m b e r s h i pf u n c t i o n ) ) 定义为 r ，、 c a r d ( x n r ( x ) ) 肛i 3 磊瓜鬲广 其中r 是不可区分关系，r ( x ) = m r = 秒：o u ) ( y r x ) ) ，c a r d 表示集合的基 数。 显然有p ! ( x ) e 0 ，1 。可以看到，这里的成员关系是根据已有的分类知识客 观计算出来的，而不是主观给定的。 另外，用上近似与下近似还可定义粗糙集合的包含关系与相等关系等。 定义2 6 ：设( u ，r ) 是一个近似空问，x ，y u ，则有如下概念： ( 1 ) 称集合x 为底线r - 包含于集合y ( x c _ r y ) 当且仅当r 。x r 。y 。 ( 2 ) 称集合x 为上线r 一包含于集合y ( x r y ) 当且仅当r x 心y 。 ( 3 ) 称集合x 为r 一等于集合y ( x c _ + r y ) 当且仅当r 。x r y 及r x c r + y 。 9 2 1 3 知识的约筒和相对约简 知识约简在信息系统分析与知识发现等领域具有重要的应用意义。知识之 间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往 往是知识约简的重要启发式信息。 在粗糙集合理论应用中，约简与核是两个最重要的基本概念。知识的约简 是指该知识的本质部分，它足以定义所考虑的知识中遇到的所有基本概念，而 核是其最重要的部分。 定义2 7 ：设r 是等价关系的一个族集，关系p r 。若i n d ( r ) = i n d ( r 一 p ) ，则称关系p 在族集r 中是可缺的( d i s p e n s a b l e ) ，否则就是不可缺的；若 族集r 中的每个关系都是不可缺的，则称族集r 是独立的( i n d e p e n d e n t ) ，否则 就是依赖的或非独立的。 定义2 8 ：若q _ c p 是独立的，并且i n d ( q ) = i n d ( p ) ，则称q 是族集p 的一 个约简( r e d u c t ) 。在族集p 中，所有不可缺的关系集合称为族集p 的核( c o r e ) ， 表示为c o r e ( p ) 。 下面的定理是建立核与约简之间联系的重要性质。 定理2 1 ：族集p 的核等于p 的所有约简的交集。 即c o r e ( p ) = l r e d ( p ) ，其中r e d ( p ) 是p 的所有约简的族集。 从定理2 1 可看出，核的概念具有两方面的意义。首先，可作为计算所有 约简的基础，因为核包含于每一个约简之中，并且其计算是直接的。其次，核 可以解释为知识的最重要部分的集合，进行知识约简时不能够删除它。 前面所定义的约简和核的概念在应用时有一定的限制。因此，下面将引入 其更泛化的概念。为此，首先需要定义一个分类关于另一个分类的正区域概念。 定义2 9 ：设p 和q 是全域u 上的等价关系的族集，族集q 的p 正区域 ( p - p o s i t i v er e g i o no fq ) ，记作p o s p ( q ) ，定义为 p o s p ( q ) = ljp ( x ) e x e u q 族集q 的p 正区域是全域u 中使用分类u p 能够正确地分类于u q 的等 价类之中的所有对象的集合。个集合x 相对于一个等价关系p 的正区域就是 这个集合的下近似p ( x ) ；而一个等价关系q 相对于另一个等价关系p 的正区 域的概念是解决分类q 的等价类( 一般视为决策类) 之中的那些对象可由分类 p 的等价类( 一般视为条件类) 来分类的问题。 定义2 1 0 ：设p 和q 是全域u 之上等价关系的族集，r e p 。若 p o s m o ( r ) ( i n d ( q ) ) = p o s i n d ( i , r ) ( z r d ( q ) ) ， 则称关系r 在族集p 中是q - 可缺的，否则称为q - 不可缺的；如果在族集p 中 的每一个关系r 都是q 不可缺的，则称族集p 关于族集q 独立的。 1 0 定义2 1 1 ：族集s g p 称为族集p 的q 一约简( q r e d u c t ) ，当且仅当s 是p 的 q 独立的予族集，且p o s s ( q ) = p o s p ( q ) ：族集p 中所有q 不可缺的初等关系 的集合，称为族集p 的q 一核( q g o r e ) ，记作c o r e o ( p ) 。 类似定理2 1 ，我们得到定理2 2 如下： 定理2 2 ：族集p 的q 核等于旗集p 的所有q 一约简的交集。 即c o r e o ( p ) = n r e d o ( p ) ，其中r e d o ( p ) 是族集p 的所有q - 约简的族集。 2 1 4 种类的约简与相对约简 基本种类( b a s i cc a t e g o r y ) 是知识的基本块，类似于概念的积木。知识库中 的每个概念都可由这些基本种类精确或严格地表示。另一方面，每一基本种类 是一些初等种类( e l e m e n t a r yc a t e g o r y ) 的交集。因此，现在的问题是，是否是 所有的初等种类对定义问题中的基本种类都是必要的。 从数学的观点看，这一问题类似于知识的约简，即删除知识p 中对定义所 有基本种类来说是多余的等价关系。 定义2