（管理科学与工程专业论文）粗集覆盖算法及其相关问题的研究.pdf

山东师范人学硕十学位论文 粗集覆盖算法及其相关问题的研究 摘要 从数据集中对对象进行归纳学习和分类是人工智能中很重要的领域，旨在发 现数据中隐藏的、未知的、潜在有用的知识，本质是在大的数据集合中寻找数据 问的规则及普遍模式。近几年来，已经研究了很多基于归纳学习的理论，发展了 许多技术来处理不精确的数据，其中最成功的是粗糙集理论。粗糙集理论是波兰 科学家z p a w l a l 【于1 9 8 2 年提出的一种数据分析理论，它是关于数据推理的一 个强大的工具，目前已发展成为一种处理模糊和不确定性信息的数学理论，成功 地应用于机器学习、模式识别、决策支持、数据挖掘、过程控制等领域。并且已 发展成为人工智能的一个重要研究方向，在数据挖掘( d a t am i n i n g ) 与知识发现 ( k d d ) 中具有非常广泛的潜在应用背景，并已获得许多成功的应用。 p a w l a k 粗糙集理论是以等价关系为基础建立的。但是在有些领域，等价关 系是不适合处理一些粒度数据。进而，为了推广粗糙集理论的应用范围，研究者 提出了多种的粗糙集模型。其中，z b o n i k o w s k i 利用沦域上的覆盖建立了覆盖 粗糙集模型。本文对z b o n i k o w s k i 定义的覆盖粗糙集模型中的一些概念进行了 完善。同时在新的定义下讨论了上、下近似的性质和覆盖的约简，并用公理化的 方法研究了它们。在粗集覆盖约简的基础上，本文对相对约简也进行了相关的讨 论。另外，本文在在诱导覆盖的基础上，提出了一种新的覆盖扩展覆盖( t h e e x t e n s i o nc o v 耐n 曲，并就同一论域上的两个扩展覆盖依赖程度的度量进行了说 明以及扩展覆盖上任意两个元素之问的三种基本关系进行了详细的讨论。 本文定义了知识论域和知识拓扑，组建了4 种拓扑空间，讨论了z p a w l a k 粗 糙集模型上映射的拓扑性质，指出了粗糙集模型与一个有限集之间的映射。在该 映射上可以诱导出基于此有限集上的等价关系，从而得到了两个粗集拓扑空问的 映射。这个映射是连续的，如果是双射则此映射是丌的且把粗集映成粗集，粗集 的原像还是粗集。对一个问题进行拓展研究，首先要找到该问题的相对性因子， 对与相对性因子泛化，然后再用泛系方法论中的泛导思想，构造该问题的新模型。 本问从泛系的角度对覆盖粗糙集的拓展研究就是基于这种思想。通过泛系理论对 覆盖粗糙集的研究，根据泛系拓扑与粗糙集近似的相似性即从内、外逼近某对象， 提出了覆盖粗集的模型 在基于对映射和z b o n i k o w s k i 定义的覆盖粗糙集模型的研究，本文由某泛 序系统下某元素的上、下逼近，联系到某线序系统下元素的插入排序和选择排序。 通过引入偏序宏观序而将线形序下的插入排序和选择排序，拓展到任何序下来实 现，并给出了任何序下插入排序和选择排序的一般算法。并且，通过插入排序还 可以构造拓扑结构，以便于对问题的研究。 关键词：粗糙集；覆盖；公理化；约简；插入排序；选择排序； 分类号：四18 t h er e s e a r c ho no f a l g o t h mo nr o u 曲s e t c o v 耐n g a n d r e l a t e dp r o b l e m s a b s t r a c t i n d u c t i v el e a m i n ga n dc l a s s i f i c a t i o no f o b j e c t 丘o md a t as e ta r ev e 眄i m p o r t a n t a r e a si n 积i 矗c i a li n t e l l i g e n c e ，i no r d e rt od i s c o v e r h i d d e n ，u n 玉m o w n ，p o t c n t i a l i yu s e 伽 h o w l e d g ei nm ed a t a ，a n dt os e a r c ht h er u l ea 1 1 dt h eg e n e r a lm o d e 舶mt h el 硼驴d a t a s e tme s s e n c e i i lr e c e n ty e a r s ，al o to f t h e o r i e sb a s e do ni n d u c t i v el e a m i n gh a v eb e e l l r e s e a r c h e d ，觚dan u m b e ro ft e c h n i q u e sa r ed e v e l o p e dt od e a lw i t hi m p r e c i s ed a t a t h em o s ts u c c e s s 如1 t e c l l i l i q u ei sr o u 曲s e tt h e o 彤r o u 曲s e tt h e o qi san e wd a t a a l l a l y s i s ，i tw a sf i r s tp u tf o n a r db yp o l a n ds c i e n t i s tz p a w l a k w h i c hi sa p o w e r 如l t o o la b o u td a t ar e a s o n i n g a tp r e s e n ti th a sb e e nd e v e 】o p e dt ob ean e wm a t h 锄a t i e a l t o o l t od e a lw i t h 妇g u e n e s sa n du n e e n a i n i y i th a sb e e na p p l i e ds u c e e s s m l l yt om a n v a i e a si n c l u d i n gm a c h i n el e a m i n g ，p a t t e mr e c o g n i t i o n ，d e c i s i o ns u p p o r t ，d a t am i n i n g a i l dp r o c e s sc o l l t r 0 1 p r e s e n t l yi th a sd e v e l o p e dt ob ea i li m p o n a n tr e s e a r c h i n g d i i e c t i o no fa r t i f i c i a ki n t e l i g e n t ，i th a sv e 拶e x t e n s i v el a t e n ta p p l y i n gb a c k g r o u n da t t h ef i e l do fd a t am i n i n g t h et h e o r yo fp a w l a kr o n 曲s e tw a se s t a b l i s h e d o nt h eb a s eo fe q u i v a l e n c e r a l a t i o n ，b u ti ns o m es i t u a t i o n s ，e q u i v a l e n c er e l a t i o n sa r en o ts u i t a b l ef o rc o p i n gw i n l 黟a 1 1 u l a n t y i n s t e a dt h e e s e a c h e r sp u tf o n ) l ，a r dm a n yk i n d so fg e n e r a l i z e dr o u 曲s e t m o d e l si 1 1o r d e rt o e x p a n d i t sa p p l i c a t i o n s a r e a s a m o n gt h e s er e s e a c ha r e a s ， z b o n i k o w s k ie s t a b l i s h e dc o v 硎n gr o u 曲s e tm o d e lu s i n gac o v 舐n go fu n i v e r s e i n t 量l i sp a p w e r e a s o n a b l ym o d i f i e dt h en e wd e 矗n i t i o no ft h ec o v 舒n g a tt h es 锄e t i m e ，d i s c u s e dt h ep r o p o s i t o n l lo fc o v i n gu p p e r a p p r o x i m a t i o no r e r a t i o na n dc o v 嘶n g l o w e ra p p r o x i m a t i o no p e r a t i o na n dt h e r e d u c t i o no fc o v 鲥n g su n d e rt h en e w d e f i n i t i o n f u t h e m l o r e ，t h el o w e ra n du p p e r 印p r o x i m a t i o n 叩e r a t i o n sh a v eb e e l l a ) 【i o m i z e d i i la d d i t i o n ，o nm eb a s i so fi n d u c e dc o v e r a g e ，w e p r o p o s ean e wc o v e r a g e 。e x t e l l s l o nc o v e r ，o na l l do nt h es 锄ed o m a i no nt h ee x p a n s i o n c o v e r i n go f t h et w o d e p e n d e n to nt h em e a s u r ea 1 1 dad e s c d p t i a l s ot h r e eb a s i cr e l a t i o n sb e 眦e e na n y 觚o e l 锄e n t sw i t l lr e s p e c tt ot h ee x t e n s i o nc o v e ra r ed i s c u s s e di nd e t a i l i i lm i sp a p e r k n o w l e d g eu n i v e r s ea 1 1 dl ( n o w l e d g et o p o l o g ) ra r ed e f i n e d f o u rk i n d o tt o p o l o g ys p a c ea r ec o n s t r a c t e d n ec o 肌e c t i o n s 锄o n ga i l dt h ep r o p 喇i e so fm 锄 a 粥s t u d i 谢t o p o i o 昏c a lp r o p e 棚e s簖m a p 鳓p a w l 酞r o u 曲s e c sm o d e la f e d i s c l l s s e d a n dam a pb e m e c nr o u 曲s e tm o d d 柏daf i n e t es e t c a i li n d u c ea 键u i 谢瓢礴蕊傩强龇曩砖钯s e 。主f 搬em a p 这婉卿i e da sam a pb 戎w 蝴柳o t o p 0 1 0 西c a ls p a c e ，m 蹴i ti sc o n t i n u o u s f o u r t h 矧胍o r e ，i ft h em a pi sb i j e c t i v e ，t h e i li t i gs 主n 斑l t 雏毽s 重yo p 镰跹d 瓶魏。强s ，佼e 主趣a 萨锺di 程v e 塔e 趣a g eo fa 融l 或蛾 a r er o u 曲b a s e do nt h j er e s e a r c ho f c o v e “n gr o u 曲s e ta n dp r o p e n i e so fm a p i nt h i s p a p b yt h eu p p e ra p p r o x i m a t i o na n dl o 、懈a p p r o x i m a t 主o no f p a n s y s t e m st i 叩o l o g y w oc o n t a c 专i 薹l s 锄a l l d 舵e 耋戤i so v 嚣】i n e a ro f d 嚣s y s t e m 8 yi n t r o d u c i n g p 删a lm a c r o o r d c re x p e n di n s e r ta n d 眈et a x i sw h i c hi s 订u eo v e rl i n e a ro r d e rt o 锄yo r d 瓯p u t f o 薹w a 砖ag 鼹e 嗣i n s 硪雒d 抵撕曩魏e 耄i c 。琢蠢d 斑。羔l ，黼c a n n s l 敝l l 。p o l o g y y i n s e r t i n g k e yw o r d s ：r o u 曲s 娃；c o v 硪n g ；雄p 羚x i 越a t 主o n ；辖曲兹o n ；i n s 鼬鑫矬dt f e e a x i s c l a s s i 6 c a t i o n ：t p18 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，木栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：01 涉文 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权趁可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) ， 学位论文作者签名：? 薹争五 导师签字： 签字日期：2 。o9 年6 月乜日 签字日期：2 0 0 文、。 夕年6 月钇日 山东师范大学颐十学位论文 1 1 粗集理论概述 第一章绪论 粗糙集理论是波兰科学家p a w l a l ( 【l 】在1 9 8 2 年提出的，借鉴了逻辑学和哲学 中对不精确、模糊的各种定义，针对知识库，提出不精确范畴等概念，并在此基 础上形成了完整的理论体系粗糙集理论。该理论是一种刻画不完整和不确定性 的数学工具，能有效地分析不精确( i m p r e c i s e ) 、不一致( i n e o n s i s t e n t ) 、不完整 ( i n c o m p l e t e ) 等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐 含的知识、揭示潜在的规律。 由于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时没有引 起国际计算机学界和数学界的重视，研究地域也仅局限在东欧一些国家，直到 2 0 世纪8 0 年代末才逐渐引起各国学者的注意。近几年来，由于它在机器学习与 知识发现、数据挖掘、决策支持与分析等方面的广泛应用，研究逐渐趋热。1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开；1 9 9 5 年， a c m c p n z c a t i o n 将其列为新浮现的计算机科学的研究课题；1 9 9 8 年，国际信息 科学杂志( i n f o 肌“o n s c i e n c e s ) 还为粗糙集理论的研究出了一期专辑。这些都表明 了粗糙集理论与其应用的研究有着广泛的发展前景。 粗糙集理论建立在分类机制的基础上，它将分类理解为特定空间上的等价关 系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分 每一被划分的集合称为概念。粗糙集理论的主要思想是利用己知的知识库，将不 精确或不确定的知识用己知的知识库中的知识来近似刻画。该理论与其他处理不 确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合 之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比较客观 的。由于这个理论未能包含处理不精确或不确定原始数据的机制，所以这个理论 与概率论，模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的 互补性。 p a w l a k 最初提出的粗糙集模型是以等价关系为基础的，它将分类理解为在 特定空问上的等价关系，而等价关系构成了对该空间的划分，将知识理解为对数 据的划分，每一被划分的集合称为概念。其主要思想是利用已知的知识库，将不 精确或不确定的知识用己知的知识库中的知识来( 近似) 刻画。在对于粗糙集理论 的研究中，为了使该理论能有更大的应用空间，研究者提出很多推广的粗糙集模 型，目前主要有两种方法：( 1 ) 构造性方法；( 2 ) 公理化方法。 ( 1 ) 构造性方法是对原始p a w l a k 粗糙集模型的般推广，其主要思路是从给 定的近似空间出发去研究粗糙集和近似算予。它是以论域上的二元关系或布尔子 代数作为基本要素的，然后导出粗糙集代数系统( 2 “，n ，u ，缈，缈) 。这种方法所 研究的问题往往来源予实际，所建立的模型有很强的应用价值，其主要缺点是不 易深刻了解近似算子的代数结构。在p a w l a k 粗糙集模型中有三个最基本的要素： 一个论域u ：u 上的一个二元等价关系r ( 或划分) ( 它们构成了近似空间) ；一个 被近似描述的( 经典) 集合x ，也称为专家概念。这样，推广的形式主要也有三个 方向，即从论域方向、从关系方向( 包括近似空间) 和从集合方向。 从论域方向推广的髓前只有一莘孛，就是把p a w l a l 【粗糙集模型中的一个论域 推广到双论域的情形 2 】，当然这时的二元关系就变成为两个论域笛卡尔乘积的一 个子集。 关系的推广：一种是将论域上的二元等价关系推广成为任意的二元关系得到 了一般关系下的粮糙集模型【3 】；另种是将对象x 所在的等价类看成是x 的一个 邻域从而推广导出了基于邻域算子的粗糙集模型，也有将由关系导出的划分推 广成为般的稚尔子代数的，以此出发去定义粗糙集和近似算子的【4 1 ；更一般的 是将普通关系推广成模糊关系或模糊划分丽获得模糊粗糙集模型翻嘲。 将集合和近似空问进行推广。这一类的推广是与其他处理不确定，不精确或 模糊的知识砖瑟概率论，模赣数学，信息论，证据理论等) 结合起来进行研究的。 当知识库中的知识是由于随机原因产生或经统计得到时，即知识库中的知识很可 能是不确定的，很多学者提爨了统计( 或概率) 粗糙集模型【7 】【s 】【9 】，交精度粗糙集。 模型实质上也可以归入这类模型，寻求具有最小风险的b a y e s 决策问题也可转化 为这类模型。 当知识库中的知识模块都是清晰的概念，而被描述的概念是一个模糊概念 时，人们建立了粗糙模糊集模型来解决此类问题的近似推理。当知识库中的知识 模块也是模糊的，有些学者就提出了模糊粗糙集模型。 代数方法又称为公理化方法或算子方法，这种方法不是以二元关系为基本要 素，它的基本要素是一对满足某些公理的一元( 集合 近似算子三，嚣：2 秽_ 2 即粗 糙代数系统( 2 “，门，u ，厶日) 中近似算子是事先给定的。这种方法研究的明显优点 是能够深刻地了解近似算子的代数结构，其缺点是应用性不够强。 近似算子的某些公理能保证有一些特殊类型的二元关系的存在，使这些芙系 能够通过构造性方法产生给定的算子，反过来，由二元关系通过构造性方法导出 的近似算子一定满足某蝗公理，使这些公理通过代数方法产生给定的二元关系。 2 山东师范，：学颀十学位论文 公理化方法的研究一开始只髑限于p a w l a l ( 粗糙集代数系统【1 蠲嘲，即公理与二元 等价关系相对应情形，后逐渐发展到一般关系下的粗糙集系统。m o r s inn 等用 公理化的方法对基于三角模豹粗糙集模型进行了研究，张文修等对一般模糊关系 下的模糊粗糙集模型的公理化方法进行了讨论。 1 2 本文的主要工作 在p a w l a k 粗糙集模型中，论域上的等价关系起着至关重要的作用，基于等价 关系形成的划分，构造了论域上的上、下近似算子，用于刻画不精确概念，并进 丽研究褶应的知识约篱与知识获取润题。但在很多实际阆题中，对象之间的等价 关系很难构造，或者对象之间本质上没有等价关系。为了推广粗糙集理论的应用 围，根据一些具体问题，研究者对p 纛w l 呔粗糙集模型进行了多种形式的推广， 相继出现了变精度粗糙集模型、程度粗糙集模型、模糊粗糙集模型、基于般二 元关系的粗糙集模型、基于覆盖理论的粗糙集模型等。 z b o n i k o w s k i 【垃】从实际应用出发，提出了覆盖粗糙集模型，讨论了相关的性 质。本文在覆盖粗糙集的基础上给出了约简的概念和方法，并证明了一个覆盖通 过约篙得到的最小覆盖是惟一的，并篮通过算法实现了一般情况下如何来求最小 覆盖。 在覆盖粗糙集模型的研究中，针对z b o 越l ( o w s 越定义的算子不其有对偶性， 特别是其上近似算子不满足单调性。许多学者对其定义的近似算子做了适当的修 改。其中，w 强撒z h u f l 3 】对覆盖近似算子做了适当修改，定义了几种耨的覆盖上 近似算子，并且讨论了它们的性质，公理化条件，约简及其相互之间的关系。借 助邻域，针对z 。b o n i k o w s k i 模型中上、下近似算子不对偶的特性，秦克云【1 4 】定 义了几对对偶的近似算子，并且讨论了它们的 生质及其相互关系。本文在以上两 位学者提出的近似算予的基础上完善了其概念和性质。 插入排序和堆选择排序要求在线形序下进行，但现实孛有各种各样的序，如 何在各种序下进行排序? 本文通过引入宏观序而将线形序下的插入和选择排序 推广到任俺序下来实现。 l 。3 章节安排 本文第二章介绍文中将要用到的粗糙集的基础知识，第三章讨论基于覆盖的 粗糙集概念及其公理化的方法，第四章讨论了覆盖糨集的约简以及楣关的性质， 第五章讨论覆盖的粗糙集模型插入和选择排序，最后是结论和参考文献等内容。 3 第二章粗糙集理论的基本知识 粗糙集理论是一种新的处理模糊和不确定知识的数学工具。其主要思想就是 在保持决策表分类能力不变的前提下，从决策表中挖掘出最小决策规则，并且能 够利用这些决策规则的集合进行决策分析和预测。本章将介绍粗糙集理论的基本 知识，作为以后各章的基础。 2 1 粗糙集理论的基本概念 2 1 1 知识与分类 般认为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特性， 是属于认识论范畴的概念。任何知识，都是对其事物运动状态及变化规律的概括 性描述。这对知识的定义不畿算是个完全的、精确的表达，因为知谈是具有多 种意义的。、 粗糙集理论从认知科学的一些观点束理解知识，讵是出于这一点使得粗糙集 理论程数据推理、经济决策等领域有了新的突破，才得到广泛应用。知识是源于 人类及其他物种的分类能力。关于环境的知识，从生存的观点看，就是感觉信号 的复杂分类，它是动物的基本功能对不丽情况的分类能力丽来的。更为抽象层次 的分类是推理、学习、决策的关键，是一种基础知谢15 1 。 例如，在某静强境下，规器入表现褥像是有知识、有智慧，实瘊上是它们将 外部环境和内部状态的传感信号分类，得出可能的情况并由此支配行动，知识直 接与真实或抽象世界有关的不同分类模式联系在起。 因此，任何一个物种都是由一些知识来描述的，根据这些知识可以把它们分 类，利用不同的属性知识描述，对物科，产生不同的分类。 定义2 重吲设u 是我们感兴趣的对象组成的非空有限集合，称为论域( 全 域) 。任何子集x u ，称为中的一个概念或范畴。u 的一组概念称为u 上的 抽象知识，简称为知识。 本文主要是对在u 上能形成划分的那些知识感兴趣。u 中的对象按照某一 个或几个属性进行分类，从而得到一个划分，在此一个划分z 定义为： z = 彤l ，x 2 ，嬲) ，其中，互u ，石g ，石n 菇= f 2 j ( f 喾歹，l ，歹= l ，2 ，+ ，箨) ， 船 u 石= u 。 f = - 1 4 山东师范大学顾十学位论文 定义2 2 【1 6 1u 上的一个划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。一 个知识库就是一个关系系统足= ( u ，尺) ，其中u 是非空有限集，尺为u 上等价关 系的一个族集。 啪表示r 的所有等价类( 或者u 上的分类) 构成的集合，【x k 表示的是 包含元素石u 的尺等价类。 下面举例说明： 玩具积木的集合u = 扛- ，石z ，肋，x ，x s ，z o ，石，工s ) 。现在假设这些积木有不同的颜 色( 红、黄、蓝) 、形状( 方、圆、三角) 、体积( 大，小) 。因此，这些积木都 可以用颜色、形状、体积这些知识来描述。如果我们根据某一属性描述这些积木 的情况，就可以按颜色、形状、体积分类： 按颜色分类： 红： x i ，x 3 ，x 7 ) ；黄： x 5 ，x 6 ，x 8 ) ；蓝： x 2 ，石4 ) ； 按形状分类： 方： 工2 ，x 6 ) ； 圆： x l ，x 5 ) ；三角： x 3 ，工4 ，z 7 ，z 8 ) ； 按体积分类： 大： x 2 ，x 7 ，x 8 ) ； j 、： 石i ，石3 ，x 4 ，x 5 ，x 6 ) 。 换言之，我们定义了三个属性：颜色r 一、形状r ：、体积r ，通过这些属性， 就可以得到下面三个分类： c ，尺l = x i ，石3 ，x 7 ) ， 石5 ，石6 ，石8 ) ， x 2 ，泓) ) ， 己，r2 = 石l ，x 5 ) ， x 2 ，石6 ) ， x 3 ，x 4 ，z 7 ，船) ) ， u r3 = z l ，石3 ，x 4 ，x 5 ，x 6 ) ， x 2 ，x 7 ，船) ) 。 2 1 2 不可分辨关系和上、下近似集 粗糙集理论拓展了经典的集合论，把用于分类的知识嵌入集合内，作为集合 组成的一部分。一个对象口是否属于集合x ，需要根据现有的知识来判断，可 以分为三种情况 1 7 】： ( 1 ) 对象口肯定属于集合x ； ( 2 ) 对象口肯定不属于集合x ； ( 3 ) 对象口可能属于也可能不属于集合x 。 5 集合的划分密切依赖于我们所掌握的关予论域的知识，是相对的而不是绝对 的。二元对足= ( u ，妁成为一个近似空闻( a p p 舱x i m a l i o ns p a c e ) ，设x 为论域矽中 的一个对象，z 为u 的一个子集，则 x 】矗表示所有与x 不可分辨的对象所组成 的集合，换句话说，是由善决定的等价类，帮【x 】暑中的每个对象都与x 有蓿褶丽 的特征属性( a t t r i b u t e ) 。 定义2 3 【翻若p 匹定，且p a ，则p 中所有等价关系的交集也是一个等价 关系，称为p 上的不可辨识关系攮d i s e e 氆谗l e 辖l 蕊。垮，记为删| d 妫，且有 嗍帅c ，2 腰x 这样，卅弘国( 妁( 即等价关系讯羽( 竹的所有等价类) 表示与等价关系p 相 关的知识，称为莨中关于u 的p 基本知识( p 基本集) 。炎简单起见，我们月醪妒 代替叫n ( p ) ，胁( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地， 如聚q 灭，刘称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等 概念或2 初等范畴。 同样，当足= ( u ，尺) 为一个知识库，趴移( 鬈) 定义为k 中所有等价关系的族。 不可分辨关系是粗糙集理论的核心概念，根据不可分辨关系，论域被划分为一个 类族，而每个类内部的对象都是不可区分的。 对于粮糙集可以近似地定义，我们使用两个精确集，群裰糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 集和下近似( 1 0 w e ra p p r o x i m a t i o n ) 集来描述。 定义2 4 f 囝设集合x 至，霆剧移暖) ，定义两个子集： 鐾x = u y w 足 y x ) ， 页x = u 】，芭叫尺ly n a ) 分别称它们为石的露下近似集帮霆上近似集。 集合删k ( ) = 积一垦x 称为x 的尺边界域；麟( ) = 斛称为戈的尺正 域；姗r ( ) = u 一融称为x 的灭负域。 显然，融= 只硝露( x ) u 雪峨( x ) 。鲋或嬲x ) 是渤那些知识爱判断肯定 山东师范大学颁j ：学位论文 属于x 的u 中元素所组成的集合；融是由那些知识效判断可能属于爿的u 中 元素所组成的集合；趟垓( x ) 是由那些知识霆既不能判断可能属于x 又不能判断 肯定属于“的【，中元素所组成的集会；旭吹( x ) 是由那些知识足判断肯定不 属于x 的u 中元素所缀成的集合。 下面的性质是显而易见的： 定理2 量【1 q ( 1 ) 为r 可定义的当且仅当麒= 型； ( 2 ) x 为露粗糙的当且仅当面礴丛； 我们也可以将型播述为x 中的最大可定义集，将融攒述为含有x 的最小 可定义集。根据集合并的上近似和下近似的不同情况，可以定义四种不同的重 要的凝糙集【5 】； ( 1 ) 如果墅囝且砝喾u ，则称x 为尺粗糙可定义； ( 2 ) 如果墼= 彩且斟雾，则称x 为赶内不可定义； ( 3 ) 如果墼雾彩且勋= 移，则称x 为焱外不可定义； ( 4 ) 如果丛= a 且戤嚣c 厂，则称x 为r 全不可定义。 这种划分的壹观意义是这样的： 如果集合x 为尺粗糙可定义，则意味着我们可以确定u 中的某些元素属于 x 戴一xo 如果集合为r 内不可定义，则意味着我们可以确定u 中的某些元素是否 属予一x ，僵不能确定秽中的任元素是否属于x 。 如果集合x 为冗外不可定义，则意味着我们可以确定u 中的某些元素是否 属予x ，但不能确定彩中的任一元素是否属于一x 。 如果集合x 为露完全不可定义，则意味着我们不能确定u 中的任一元素是 否属于x 或一鬣。 凝糙集理论与传统的集合论有着稿似之处，但是它们静崮发点完全不同。传 统集合论认为，一个集合完全由其元素决定，一个元素要么属于这个集合，要么 不属予这个集会，帮它的隶属飚数，( 并) 爷，1 ) 。模糊集合对魏徽了拓广，它给 成员赋予一个隶属度，郯舻( x ) 【o ，l 】，使得模糊集合能够处理一定的模糊和不 7 确定数据，程其隶属度往往具有人为的因素在举面，这为它的应用带来一定的不 便【1 6 】。在粗糙集理论中，隶属关系不褥是一个原始概念，因此无需人为给元素 指定一个隶属度，从两避免了主观因素的影响。粗糙集理论认涛不确定与隶属关 系有关，而模糊性则表现在集合本身。 集合的不精确主要是由于边界域的存在，集合的边界域越大，那么该集合就 越不精确。粗糙集通过近似精度这一概念来衡量集合的精确程度。 定义2 。s f l 8 l 由等价关系灭确定的集合x 的近戳精度隽 州耻陶 其中，x 彩，1 x f 表示集合x 的势，也就是x 所包含的对象的个数。 精度盛嚣( x ) 用来反映我钓对于了解集合x 知识麴完全程度。显然，对每一个 犬和xg 夥有o 搿霁肖) l 。当窿是( 爿 = l 时，浼璃x 的灾边界域为空集，集合x 为尺可定义的；当耐詹( x ) 、 为r 内不可定义，因为： 出，= f 2 j ， m 3 = e l u e 2 u e 3 = x o ，工l ，x 2 ，石3 ，石5 ，x 6 ，工9 ) u ， 集合x 4 = x o ，x l ，石2 ，x 3 ，x 4 ，x 7 ) 为尺外不可定义，因为： 豇_ 局= 石o ，x 1 ) 囝， 融= u ， x 一的边界和近似精度分别为： 丑( x 4 ) = e 2 u e 3 u e 4 u e 5 = x 2 ，x 3 ，z 4 ，x 5 ，z 6 ，x 7 ，溉，x 9 ，舶o ) ， 口露( x 4 ) = 2 1 1 。 2 2 知识约简和知识的依赖性 知识约简和知识的依赖性是粗糙集理沦中两个最基本的问题。知识约简是研 究知识库中每个等价关系是否都是必要的，以及如何删除不必要的知识。知识约 简在机器学习、信息系统分析与数据挖掘领域都具有重要的应用意义。知识之间 的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往往是 知识约简的重要的启发式信息。 2 2 1 知识约简 知识约简中有两个基本概念：约简( 旭如订) 和核( c d 旭) 。 定义2 6 【1 6 】令p 为一族等价关系，尺尸，如果z d ( 尸一体) ) = z d ( 竹，则 称关系尺在尸中是不必要的；否则称关系尺在p 中是必要的。 不必要的关系在知识库中是多余的，如果将它从知识库中删除掉，不会改变 知识库的分类能力；相反，如果从知识库中去掉一个必要的关系，则一定会破坏 这个知识库的分类能力。 定义2 7 【1 6 1 令p 为一族等价关系，r p ，如果每个关系r p 在p 中都是 必要的，则称族集尸是独立的；否则称p 是依赖的。 对于依赖的关系族，其中包含有多余的关系，可以对其约简；而对于独立的 关系族，是不可以对其进行约简的。 9 通过以上的定义以及简单的推导，我们得到如下的定理： 定理2 2 【6 】如果p 是独立的，q 尸，则称q 也是独立的。 证明：用反证法。 假设q 冬尸且q 是依赖的，则存在s c q ，使得n 移( s ) = z 彻( q ) ，这就意 味着 肋( s u ( p q ) ) = 肋( p ) ，s u ( p q ) c 尸 因此尸是依赖的，这与已知条件是矛盾的，故定理得到了证明。 定义2 8 1 6 】设u 是一个论域，j p 、q 为定义在u 上的两个等价关系族，且 q p ，如果满足： ( 1 ) 饥( 尸) = 删d ( q ) ； ( 2 ) q 是独立的。 则称q 是尸的一个约简( 旭d “) 。 定义2 9 【m 】设u 是一个论域，p 为定义在u 上的一个等价关系族，尸中所 有必要关系组成的集合，称为族集p 的核( c d 陀) ，记作c d ，g ( p ) 。 通过以上的定义以及简单的推导，我们得到如下的定理： 定理2 3 陀( p ) = n 俐( p ) ，其中的彤d ( 尸) 表示族集尸的所有约简。 从上面的定理可以看出，核的用处有两个方面：第一，它可以作为所有约简 的计算基础，因为由核的定义我们知道，核包含在所有的约简之中，并且计算可 以直接进行；第二，核可以被解释为知识最重要部分的集合，在进行知识约简时 是不能够去掉它的。 一般产生约简的方法是逐个向核中添加不必要的关系，并进行检查。注意， 不必要的关系集合的幂集的基数是多少，就有多少种添加的方式。最好的情况出 现在当所有的必要关系的集合本身就是约简，此时的约简是唯一的。所以，计算 一个最佳的约简( 比如定义为关系最少) 和计算所有的约简都是当前研究当中的 n p 难题。 现在举例说明寻求约简和核的过程如下： 设k = ( u ，r ) 是一个知识库，其中u = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ， r = 尺- ，尺2 ，r ，) ，等价关系r - ，尺z 和尺3 有下列等价类： l o 山东师范大学硕十学位论文 叫r t = x - ，x 一，x s ) ， x z ，z 8 ) ， x 3 ) ， x o ，x ，) ) 叫尺，= x - ，x s ) ， 工o ) ， x 2 ，x ，s ) ， x ，x 。 关系刷d ( r ) 有下列等价类： 叫尺= “x l ，x 5 ) ， x z ，x s ) ， x ，) ， x ) ， x s ) ， x ，) ) ， 关系尺- 为尺中必要的，因为： 叫z ( r 一尺1 ) = “x i ，x 5 ) ， x 2 ，x 7 ，x 8 ) ， x 3 ) ， x 4 ) ， x 6 ) ) 叫伽d ( r ) 。 对于关系r ：，我们有： 叫上加( r 一只z ) = “x - ，x 5 ) ， x 2 ，x s ) ， x ，) ， x 。) ， x s ) ， x ，) ) = 叫砌d ( r ) ， 故关系尺z 是r 中不必要的。 同样对于关系r ，我们有： 叫肋( r r 3 ) = “x i x 5 ， x 2 ，z 8 ， x 3 ， x 4 ， x 6 ， x 7 ”= 叫砌d ( 尺) ， 因此关系r 3 是r 中不必要的。 这表明通过等价关系尺，尺z 和j r ，的集合定义的分类与根据尺t 和尺2 或r i 和 尺，定义的分类相同，即表明该系统的知识可以通过叫z d ( 尺- ，r z ) ) 或 叫饥仍( 似- ，r ，) ) 来表达。 为了得到尺= 但t ，r z ，尺s ) 的约简，我们检验俾t ，r ：) 和但t ，r ，) 是否为独立的， 因为叫j ：仞( 尺l ，尺2 ) 叫n d ( 尺- ) ，且叫z 彻( 尺l ，尺2 ) 叫饿d ( 尺2 ) ，因此 r ，尺2 ) 为 独立的，且 r - ，r z ) 为r 的一个约简。同样，我们可以得到 尺- ，尼) 也是尺的一个 约简。所以，r 就有两个约简， 即 尺t ，r z ) 和 凰尺，) ，一个核 昭( 尺) = r i ，r z ) n 尺- ，尺3 ) = 尺i ) 。 在实际的应用中，一个分类对于另一个分类的关系十分重要，这就是知识的 相对约简( r e l a t i v er e d u c t i o n ) 和相对核( r e l a t i v ec o r e ) 的概念。 定义2 1 0 【1 q 设p 和q 是u 中的等价关系，q 的p 正域记为p d 昂( q ) ，即 尸0 昂( q ) = u x 艇u q q 的尸正域是【厂中所有根据分类叫p 的信息可以准确地划分到关系q 的等 l l 价类中去的对象集合。 定义2 1 1 设尸和q 是u 中的等价关系族， 尺p ，如果 p i 粥锄( p ) ( n ( 9 ) ) = 尸( p 一 露) ) ( j 凇( q ) ) 则称r 为p 中q 不必要的；否则r 为 p 中q 必要的。 为了简单起见，有时我们也会用p ( q ) 来代替p 优( p j ( 上d ( q ) ) 。 如果p 中的每个月都是q 必要的，则称p 为q 独立的，否则就称p 为q 依赖 的。 定义2 1 2 【1 6 1 设s j p ，s 为尸的q 约简当且仅当s 是尸的q 独立子集族， 且户弧( q ) = 膦( q ) ，p 的q 约简称为相对约简。 p 中所有q 必要的初等关系构成的集合我们称为户的q 核，简称相对核，记为 ，印( 尸) 。 2 2 2 知识的依赖性 知识的依赖性可以形式化的定义如下： 定义2 1 3 【1 6 】令k = 缈，r ) 是一个知识库，p ，q 尺， ( 1 ) 知识q 依赖于知识尸或知识尸可以推导知识q ，当且仅当 删d ( 竹肋( q ) ，记作尸jq ； ( 2 ) 知识p 和知识q 是等价的，当且仅当尸q 且qj 尸，即 肋( 尸) = 肋( q ) ，记作尸= q ； ( 3 ) 知识尸和知识q 是独立的，当且仅当尸q 且qjp 均不成立的时候， 记作p q ； 现举例说明知识的依赖性，如下： 假设知识p 和知识q 有如下分类： 叫p = x - ，x s ) ， x 2 ，x s ) ， x 3 ) ， x ) ， x 6 ) ， x ，) ) 1 2 山东师范大学硕- 卜学位论文 叫q = 石- ，彳s ) ， x z ，x ，x s ) ， x ，肖，x s ) ) ； 可见，上仞( 印j d ( q ) ，因此p jq 。 有时候知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识p 导 出的，部分可导出可由知识的正域来解释。 定义2 1 4 【16 】令k = ，r ) 是一个知识库，p ，q r ，当 后= 7 p ( q ) = i p d - 野( q ) i | 【厂i 时，我们称知识q 是尼( 0 七1 ) 度依赖于知识p 的，记作p jt q 。 ( 1 ) 当七= l 时，我们称知识q 完全依赖于知识尸； ( 2 ) 当0 七 l 时，则称知识q 部分( 粗糙) 依赖于知识尸； ( 3 ) 当七= o 时，则称知识q 完全独立于知识p 。 上述思想也可以解释为将对象分类的能力。确切地浼，若足= 1 ，则论域的 所有元素都能够用知识p 来分类于叫q 的概念之中。若后l ，则仅仅是论域中 属于正区域的那些元素能够用知识尸来分类于叫q 的概念之中。若七= o 时，则 论域中所有元素都不能用知识尸来分类于叫q 的概念之中。因此系数厂尸( q ) 可以 看作是q 与尸间的依赖程度。 2 3 区分矩阵 a s k o w r o n 教授和c r a u s z e r 教授的区分矩阵于2 0 世纪9 0 年代初提出后， 一直被认为是求解属性约简和求核的重要方法