（应用数学专业论文）粗糙集理论中的若干问题研究.pdf

国防科学技术大学研究生院学位论文 a b s t r a c t t h er o u g hs e tt h e o r y ( r s t ) ，w h i c hw a si n t r o d u c e db yz p a w l a ki n19 8 2 ，i sat o o lt od e a l w i t hv a g u e n e s sa n du n c e r t a i n t y i t sm a i ni d e ai si n d u c i n gd e c i s i o no rc l a s s i f i c a t i o nr u l et h r o u g h k n o w l e d g er e d u c t i o nb yk e e p i n g t h ec l a s s i f ya b i l i t y t h em a i nd i f f e r e n c eb e t w e e nt h er s ta n d o t h e rt h e o r i e si st h a tt h er s td o e sn o tn e e da n yp r e l i m i n a r yi n f o r m a t i o na b o u td a t a s oi t sm o r e o b j e c t i v ei nd e s c r i b i n g a n d d e a l i n g w i t h v a g u e n e s s a n d u n c e r t a i n t y i nt h i sp a p e r f i r s t l yw e c o m p a r er s t w i t hf u z z ys e t st h e o r ya n di n t r o d u c ef u z z ym e t h o d i n t ot h es t u d yo fr s t b yt h er o u g hm e m b e r s h i pf u n c t i o n t h ee x a c te x p r e s so ft h ei n t e r s e c t i o n a n du n i o no ft h ef u z z ys e t sd e f i n e db yt h er o u g hm e m b e r s h i pf u n c t i o ni s g i v e n t w oe x t e n s i o n m o d e lo fr s ta r ei n t r o d u c e da n dt h e i rc h a r a c t e r sa r ed i s c u s s e d w ea l s od i s c o v e rt h ec h a n g e so f t h eu p p e r ( 1 0 w e r ) a p p r o x i m a t i o na f t e rt h ea t t r i b u t e sw e r ea d d e dt oo rr e m o v e df r o mt h eo r i g i n a l a t t r i b u t i o ns e t s e c o n d l y , w eg e tt w on e w r e d u c t i o na l g o r i t h m s t h eh e u r i s t i cr e d u c t i o na l g o r i t h mb a s e do n t h er e l a t i v e s i g n i f i c a n c ei nj n f u r m a t i o ns y s t e r ni sm o r en a t u r a la n de a s i e ri nc o m p u t a t i o na n d i m p r o v e st h er e d u c t i o na l g o r i t h mi ns p e e d t h ec o n v e r s i o n a la l g o r i t h mo ft h ed e c i s i o nt a b l e b a s e do nt h el o w e ra p p r o x i m a t i o nr e d u c t i o n t h e o r yt r a n s l a t et h er e l a t i v er e d u c t i o no f t h ed e c i s i o n t a b l ei n t ot h er e d u c t i o no ft h ei n f o r m a t i o ns y s t e ma n do f f e ran e wm e t h o dt of i n dr e l a t i v e r e d u c t i o no f t h ed e c i s i o nt a b l e a tl a s t ，s e v e r a lm e a s u r e m e n t so f r o u g h n e s sa n d t h e i rr e l a t i o n sa r ed i s c u s s e d k e y w o r d s ：r o u g hs e tt h e o r y ；f u z z ys e tt h e o r y ；i n f o r m a t i o ns y s t e m ；d e c i s i o nt a b l e ； r e d u c t i o n ；r o u g h n e s s 第1 i 页 国防科学技术大学研究生院学位论文 第一章绪 论 1 1粗糙集理论介绍及发展现状 1 1 1 粗糙集理论的简单介绍 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得各个领域的 数据和信息量急剧增加，世界正处于一个“信息爆炸”的时代。同时由于人类的参与使数据 与信息系统中的不确定性更加显著，形成了不确定性复杂大系统。这些数据是一种宝贵的资 源，但我们从中发掘所需信息的能力却非常有限。如何从大量的、杂乱无章的、强干扰的海 量数据中挖掘潜在的、有利用价值的信息和知识，对人类的信息处理能力提出了前所未有的 挑战。因此当前迫切需要更好的智能化的方法和工具来处理和挖掘这些同益庞大的数掘库。 由此产生了一个新领域一数据库知识发现( k d d ) 和数据开采( d m ) 。 在k d d 和d m 诸多方法中，粗糙集理论与方法对于处理不确定性复杂系统是种较为 有效的方法，其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决 策或分类规则。它与概率方法、模糊集方法和证据理论等其它处理不确定性问题理论的最显 著区别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性 的描述或处理也是比较客观的。当然，由于该理论未能包含处理不精确或不确定原始数据的 机制，所以与其它处理不确定性问题的理论有很强的互补性。 粗糙集理论是波兰数学家z p a w l a k _ 【q 于1 9 8 2 年提出的一种数据分析理论。由于最初关 于粗糙集理论的研究主要集中在波兰，因此当时并没有引起国际计算机界和数学界的重视， 研究地域仅局限于东欧的一些国家。直到1 9 9 0 年前后，由于该理论在数据的决策与分析、 模式识别、数据挖掘、机器学习与知识发现等方面的成功应用，才逐渐引起了世界各国学者 的广泛关注。1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开。1 9 9 5 年，彳c m c o m m u n i c a t i o n 将其列为新浮现的计算机科学的研究课题。1 9 9 8 年，国际信息科学杂志还为 粗糙集理论的研究出了一期专辑。目前，粗糙集理论已成为信息科学最为活跃的研究领域之 一。近几年，这个理论已被广泛的应用于人工智能、机器学习、知识发现、数据挖掘、决策 支持与分析、模式识别、专家系统与智能控制、故障检测等研究分支：而在医学、生物学、 化学、材料学、管理学和金融学等其它学科也得到了成功应用。 1 1 2 粗糙集理论的研究现状 粗糙集理论的研究由于其历史较短，所以至今为止，对粗糙集的概念的定义还没有完全 统一，一种是原始的e a w l a l 吐l l 意义下的，也有由上，下近似构成的一对集合来命名的【2 l ，还 有以下近似和上近似构成的区间集( 集合类) 来定义的p 】，定义观点的不同往往带来研究的 侧重面的不同。目前，对粗糙集理论的研究主要集中在：粗糙集的模型的推广，问题的不确 定性研究，与其它处理不确定性、模糊性问题的数学理论的关系与互补，纯粹的数学理论方 面的研究，粗糙集的算法研究等。这些研究有的是受应用的推动而产生的，有的是纯理论的。 p a w 肠k 粗糙集模型的推广一直是粗糙集理论研究的主流方向，目前主要有两种方法：( 1 ) 第1 页 国防科学技术大学研究生院学位论文 第一章绪 论 1 1粗糙集理论介绍及发展现状 1 1 1 粗糙集理论的简单介绍 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得各个领域的 数据和信息量急剧增加，世界正处于一个“信息爆炸”的时代。同时由于人类的参与使数据 与信息系统中的不确定性更加显著，形成了不确定性复杂大系统。这些数据是一种宝贵的资 源，但我们从中发掘所需信息的能力却非常有限。如何从大量的、杂乱无章的、强干扰的海 量数据中挖掘潜在的、有利用价值的信息和知识，对人类的信息处理能力提出了前所未有的 挑战。因此当前迫切需要更好的智能化的方法和工具来处理和挖掘这些同益庞大的数掘库。 由此产生了一个新领域一数据库知识发现( k d d ) 和数据开采( d m ) 。 在k d d 和d m 诸多方法中，粗糙集理论与方法对于处理不确定性复杂系统是种较为 有效的方法，其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决 策或分类规则。它与概率方法、模糊集方法和证据理论等其它处理不确定性问题理论的最显 著区别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性 的描述或处理也是比较客观的。当然，由于该理论未能包含处理不精确或不确定原始数据的 机制，所以与其它处理不确定性问题的理论有很强的互补性。 粗糙集理论是波兰数学家z p a w l a k _ 【q 于1 9 8 2 年提出的一种数据分析理论。由于最初关 于粗糙集理论的研究主要集中在波兰，因此当时并没有引起国际计算机界和数学界的重视， 研究地域仅局限于东欧的一些国家。直到1 9 9 0 年前后，由于该理论在数据的决策与分析、 模式识别、数据挖掘、机器学习与知识发现等方面的成功应用，才逐渐引起了世界各国学者 的广泛关注。1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开。1 9 9 5 年，彳c m c o m m u n i c a t i o n 将其列为新浮现的计算机科学的研究课题。1 9 9 8 年，国际信息科学杂志还为 粗糙集理论的研究出了一期专辑。目前，粗糙集理论已成为信息科学最为活跃的研究领域之 一。近几年，这个理论已被广泛的应用于人工智能、机器学习、知识发现、数据挖掘、决策 支持与分析、模式识别、专家系统与智能控制、故障检测等研究分支：而在医学、生物学、 化学、材料学、管理学和金融学等其它学科也得到了成功应用。 1 1 2 粗糙集理论的研究现状 粗糙集理论的研究由于其历史较短，所以至今为止，对粗糙集的概念的定义还没有完全 统一，一种是原始的e a w l a l 吐l l 意义下的，也有由上，下近似构成的一对集合来命名的【2 l ，还 有以下近似和上近似构成的区间集( 集合类) 来定义的p 】，定义观点的不同往往带来研究的 侧重面的不同。目前，对粗糙集理论的研究主要集中在：粗糙集的模型的推广，问题的不确 定性研究，与其它处理不确定性、模糊性问题的数学理论的关系与互补，纯粹的数学理论方 面的研究，粗糙集的算法研究等。这些研究有的是受应用的推动而产生的，有的是纯理论的。 p a w 肠k 粗糙集模型的推广一直是粗糙集理论研究的主流方向，目前主要有两种方法：( 1 ) 第1 页 国防科学技术大学研究生院学位论文 构造性方法：( 2 ) 代数( 公理化) 方法。 ( 1 ) 构造性方法是对原始p a w l a k 粗糙集模型的一般推广，其主要思路是从给定的近似 空间出发去研究粗糙集和近似算子。它是以论域上的二元关系或布尔子代数作为基本要素 的，然后导出粗糙集代数系统1 2 “，c ，u ，n ，r ，r ) 。这种方法所研究的问题往往来源于实际，所 建立的模型有很强的应用价值，其主要缺点是不易深刻了解近似算子的代数结构。 在p a w l a k 粗糙集模型中有三个最基本的要素：一个论域u ，u 上的一个二元等价关系 月( 或划分) ( 它们构成了近似空间) ，一个被近似描述的集合。这样，推广的形式主要也有三个 方向，即从论域方向、从关系方向( 包括近似空间) 和从集合方向。 从论域方向推广的目前只有一种，就是双论域的情况【4 】，当然这时的二元关系就变成为 两个论域笛卡尔乘积的一个子集。对于将论域推广到多个的情形来研究粗糙集理论的文献目 前我们还未见到。 从关系方向的推广，一种是将论域上的二元等价关系推广成为任意的二元关系得到了一 般关系下的粗糙集模型1 5 j ；另一种是将对象x 所在的等价类看成是的一个邻域，从而推广导 出了基于邻域算子的粗糙集模型【3 】；也有将由关系导出的划分推广成为一般的布尔子代数， 以此出发去定义粗糙集和近似算子的1 6 j ：更一般的有将普通关系推广成模糊关系或模糊划分 1 7 s 9 j 而获得模糊粗糙集模型。 从集合和近似空间方向的推广，是与其它处理不确定、不精确或模糊的理论( 如概率论， 模糊数学，信息论，证据理论等) 结合起来进行研究的。当知识库中的知识是由于随机原因 或经统计得到的，即知识库中的知识很可能是不确定的，很多学者提出了统计( 或概率) 羊h 糙集模型”b 1 ，变精度粗糙集模型【1 4 】实质上也可以归入这类模型，寻求具有最小风险的 b a y e s 决策问题也可转化为这类模型【l ”。这一类模型在数据分析的增量式机器学习中有重要 应用【l ”。目前见到的此类模型中，近似空间中二元关系大都是等价关系，对于非等价关系给 出的情况文章的尚没见到，基于随机集的粗糙集模型1 1 6 1 既是对基于邻域算予的粗糙集模型的 推广，又适用于双论域情形，同时也是对统计粗糙集模型的推广。 当知识库中的知识模块都是清晰概念，而被描述的概念是模糊概念，人们建立了粗糙模 糊集模型【i7 】来解决此类问题的近似推理。当知识库中的知识模块也是模糊的，有些学者就提 出了模糊粗糙集模型 a , l g , 6 l 。对于知识库中的知识模块既是模糊知识又是随机得到的至今未见 论及，但现实问题肯定存在，因此也是值得研究的。 ( 2 ) 代数方法也称公理化方法( 有时也称为算子方法) ，这种方法不是以二元关系为基 本要素，它的基本要素是一对满足某些公理的一元近似算子厶h ：2 “j2 “，即粗糙代数系 统( 2 “，u ，n ，厶) 中近似算子是事先给定的。这种方法研究的明显优点是能够深刻了解近似 算子的代数结构，其缺点是应用性不够强。 近似算子的某些公理能保证有一些特殊类型的二元关系的存在，使这些关系能够通过构 造性方法产生给定的算子；反过来，由二元关系通过构造性方法导出的近似算子一定满足某 些公理，使这些公理通过代数方法产生给定的二元关系。 公理化方法的研究一开始只局限于p a w l a k 粗糙代数系统，即公理与二元等价关系相对 应情形，后逐渐发展到一般关系下的粗糙集系统1 1 9 , 2 0 。至今为止，关于公理化方法的粗糙集 理论研究大多局限于经典集情况，对于模糊集情况虽有讨论f l0 1 ，但比较少。 粗糙集理论中知识的不确定性主要有两个原因：一个原因是直接来源于论域上的二元关 系及其产生的知识模块，即近似空间本身，如果二元等价关系产生的每一个等价类中只有一 个元素，那么等价关系产生的划分不含有任何信息。划分越粗，每一个知识模块越大，知识 第2 页 国防科学技术大学研究生院学位论文 库中的知识越粗糙，相对于近似空间的概念和知识就越不确定，这时处理知识的不确定性的 方法往往用s h a n n o n 信息熵来刻划。知识的粗糙性与信息熵的关系比较密切，知识的粗糙性 实质上是其所含信息多少的更深层次的刻划【2 “。单从这个角度来看，粗糙集理论与信息论的 关系就比较密切，不少学者在这方面做了研究工作【2 l ”2 。 粗糙集理论中知识不确定性的另一个来源是给定论域里粗糙近似的边界，当边界为空集 时知识是完全确定的，边界越大知识就越粗糙或越模糊。粗糙集理论刻划概念x 的不确定性 用正则条件熵h 。( x ir + ) ( 其中x = 伍，x ) 是由x 产生的一个划分，r = x ，x ：，x 。 是由r 产生的一个划分) 】和粗糙性测度p 似) 来实现的。但是这两个度量并没有提供那些 完全属于x 的下近似的区域里面与不可分辨关系的知识粒度有关的不确定性。于是有人引进 了粗糙熵e r ( z ) 的概念来刻划概念x 的不确定性f 2 刭。 寻求一个合适的度量来刻划知识的不确定性也是粗糙集理论研究的一个重要方向。 在粗糙集理论与其它处理模糊性或不确定性方法的理论研究中，主要集中在它与概率统 计、模糊数学、d s 证据理论和信息论的相互渗透与补充。 在信息系统中，知识库的知识一般有两类：一类库中所有对象的描述是完全已知的， p a w l a k 粗糙集模型和一般二元关系下的粗糙集模型就是属于这一种；另一类库中的对象的 描述只有部分是已知的，即知识库中的知识是不确定的，它只能通过训练样本所提供的信息 来刻划概念，为了使从训练样本获得的规则符合整个论域的对象，在抽取样本时应符合统计 规律性，因此概率统计作为研究自然界，人类社会及技术过程中大量随机现象的规律性的一 门学科，它与粳糙集理论的结合就显得非常自然。 粗糙集理论用粗糙隶属函数来刻划知识的模糊性。对予只建立在一般二元关系r 下的近 似空问k = ( u ，r ) ，粗糙隶属函数定义为 斛钳 在概率近似空间下，粗糙隶属函数定义为 小) = 错 粗糙隶属函数一般不是z a d e h 意义下的隶属函数【l 9 “l 。 模糊集理论和粗糙集理论在处理不确定性和不精确性问题方面都推广了经典集合论。虽 然有一定的相容性和相似性，然而它们的侧重面不同。我们将在后面的章节中作详细介绍。 粗糙集理论与d s 证据理论在处理不确定性问题方面产生和研究的方法是不同的，但却 有某种相容性，粗糙集理论是为开发规则的机器自动生成而提出的，而d - s 证据理论主要用 于证据推理。粗糙集理论用概念的一对上，下近似对其进行描述，而d - s 证据理论是用一对 信任函数和似然函数在给定证据下对假设进行估计和评价。粗糙集理论中的下近似和上近似 的概率恰好分别是信任函数和似然函数【4 1 6 l ，然而生成信任函数和似然函数的基本概率分配 函数( 即m a s s 函数) 方法是不同的，前者来源于系统中数据本身，比较客观，而后者往往 来自于专家的经验，带有很强的主观性。粗糙集理论与d s 证据理论有很强的互补性。 粗糙集理论应用于数据分析时，会遇到噪音、数据缺失、数据量大等一系列经典理论解 决不够理想的问题。因此在近几年的研究中，出现了许多粗糙集的扩展模型。其中典型的有 变精度模型和相似模型。变精度模型使经典的粗糙集模型具有了一定的容错性，增强了经典 第3 页 国防科学技术大学研究生院学位论文 模型的抗干扰能力，并能够保持经典模型的绝大多数良好的性质；相似模型解决了存在数据 缺失的问题，在实践使用中具有比经典粗糙集模型更好的性能。 粗糙集理论中有效算法研究是粗糙集在知识发现、决策支持和人工智能方向上研究的一 个主要方向和重要课题。目前国际上的许多研究都集中在这个方面，并且这些研究成果都已 取得了重要的应用价值和商业价值。典型算法主要有： 1 基本算法； 2 导出规则的增量式算法； 3 约简的启发式算法； 4 动态约简的算法； 5 复合系统的约简算法： 6 粗糙集基本算法的并行算法； 7 扩展算法： 8 基于粗糙集理论的遗传算法和神经网络算法。 随着对粗糙集理论的研究的不断深入，它与其它数学分支的联系也更加紧密。例如，从 算子的观点看粗糙集理论，与之关系较紧的有拓扑空间、数理逻辑、模态逻辑、格与稚尔代 数、算子代数等；从构造性和集合的观点来看，它与概率论、模糊数学、证据理论、图论和 信息论等联系较为密切。粗糙集理论研究不但需要以这些理论为基础，同时也相应的带动这 些理论的发展。例如从算子的角度来看，粗糙集代数系统c 2 “，。，u ，n ，尺，r ) 是普通布尔代数系 统( 2 “，c ，u n ) 加上两个一元集合算子星和r 的推广。由于逻辑是计算机推理的基础，基于粗 糙集的逻辑的研究也是粗糙集理论研究的比较活跃的一个方向。例如粗糙集代数系统 2 “，c ，u ，n ，星，rj 中的五个集合算子恰好对应模态逻辑的五个算子，因此基于粗糙集的模态逻 辑的研究显得特别活跃，各种模型的粗糙集代数系统恰好对应于各种模态逻辑系统 2 4 , 1 9 , 5 】， 二者的结合有重要的应用，基于这种联系粗糙集理论能丰富模态逻辑理论，反之亦然。 至今为止，就我们所知粗糙集理论研究与应用只限于对数据给出的知识问题的处理，对 于由文本和连续图像问题的处理我们尚未见到，由于随机集理论在图像处理中已获得了成功 的应用，因此我们认为对粗糙集理论与随机集理论的结合的进一步研究有望使它在图像处理 上获得成功。 目前，纯粹的数学理论与粗糙集理论结合起来进行研究已有文章出现，并不断有新的概 念出现，如“粗糙逻辑” 2 5 , 2 6 】、“粗糙理想”、“粗糙半群”1 2 7 】等等。我们认为，随着粗糙结 构与代数结构，拓扑结构，序结构等各种结构的不断整合，必将不断涌现出新的富有生机的 数学分支。 1 2 1知识与知识库 1 2粗糙集基础理论 设u 矽是我们感兴趣的对象组成的有限集合，称为论域。z u 称为u 中的一个概 念或范畴。为规范化起见，我们认为空集也是一个概念。u 中的任何概念族称为关于u 的 抽象知识，简称知识。u 上的一族划分称为关于u 的一个知识库。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合，b k 表示包含元 第4 页 国防科学技术大学研究生院学位论文 模型的抗干扰能力，并能够保持经典模型的绝大多数良好的性质；相似模型解决了存在数据 缺失的问题，在实践使用中具有比经典粗糙集模型更好的性能。 粗糙集理论中有效算法研究是粗糙集在知识发现、决策支持和人工智能方向上研究的一 个主要方向和重要课题。目前国际上的许多研究都集中在这个方面，并且这些研究成果都已 取得了重要的应用价值和商业价值。典型算法主要有： 1 基本算法； 2 导出规则的增量式算法； 3 约简的启发式算法； 4 动态约简的算法； 5 复合系统的约简算法： 6 粗糙集基本算法的并行算法； 7 扩展算法： 8 基于粗糙集理论的遗传算法和神经网络算法。 随着对粗糙集理论的研究的不断深入，它与其它数学分支的联系也更加紧密。例如，从 算子的观点看粗糙集理论，与之关系较紧的有拓扑空间、数理逻辑、模态逻辑、格与稚尔代 数、算子代数等；从构造性和集合的观点来看，它与概率论、模糊数学、证据理论、图论和 信息论等联系较为密切。粗糙集理论研究不但需要以这些理论为基础，同时也相应的带动这 些理论的发展。例如从算子的角度来看，粗糙集代数系统c 2 “，。，u ，n ，尺，r ) 是普通布尔代数系 统( 2 “，c ，u n ) 加上两个一元集合算子星和r 的推广。由于逻辑是计算机推理的基础，基于粗 糙集的逻辑的研究也是粗糙集理论研究的比较活跃的一个方向。例如粗糙集代数系统 2 “，c ，u ，n ，星，rj 中的五个集合算子恰好对应模态逻辑的五个算子，因此基于粗糙集的模态逻 辑的研究显得特别活跃，各种模型的粗糙集代数系统恰好对应于各种模态逻辑系统 2 4 , 1 9 , 5 】， 二者的结合有重要的应用，基于这种联系粗糙集理论能丰富模态逻辑理论，反之亦然。 至今为止，就我们所知粗糙集理论研究与应用只限于对数据给出的知识问题的处理，对 于由文本和连续图像问题的处理我们尚未见到，由于随机集理论在图像处理中已获得了成功 的应用，因此我们认为对粗糙集理论与随机集理论的结合的进一步研究有望使它在图像处理 上获得成功。 目前，纯粹的数学理论与粗糙集理论结合起来进行研究已有文章出现，并不断有新的概 念出现，如“粗糙逻辑” 2 5 , 2 6 】、“粗糙理想”、“粗糙半群”1 2 7 】等等。我们认为，随着粗糙结 构与代数结构，拓扑结构，序结构等各种结构的不断整合，必将不断涌现出新的富有生机的 数学分支。 1 2 1 知识与知识库 1 2粗糙集基础理论 设u 矽是我们感兴趣的对象组成的有限集合，称为论域。z u 称为u 中的一个概 念或范畴。为规范化起见，我们认为空集也是一个概念。u 中的任何概念族称为关于u 的 抽象知识，简称知识。u 上的一族划分称为关于u 的一个知识库。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合，b k 表示包含元 第4 页 国防科学技术大学研究生院学位论文 素x u 的r 等价类。一个知识库就是一个关系系统k = ( u ，r ) ，其中r 是u 上的一族等价 关系。 若p c _ r ，且p ，则np ( p 中所有等价关系的交集) 也是一个等价关系，称为p 上的 不可区分( i n d i s c e r n i b i l i t y ) 关系，记为i n d ( p ) ，且有 乩邶，= n i x 。 r e p 这样，u i n d ( p ) 表示与等价关系族p 相关的知识，为简单起见，用l ，p 代替【，i n d ( p ) 。 对于两个知识库之间的关系，有以下结论： 令j o ( u ，p ) 和k = ( u ，q ) 为两个知识库，若i n d ( p ) = i n d ( q ) ，即u p = - u q ，则称k 和 k 是等价的，记作k 丝k7 ：当i n d ( p ) i n d ( q ) 时，称知识p ( 知识库固比知识q ( 知识库k ) 更精细，或者说q 比p 更粗糙。当p 比q 更精细时，也称p 为q 的特化，q 为p 的推 广。 1 2 2 粗糙集 设尺是u 上的二元等价关系，x u ，u i r 是u 上由r 生成的等价类全体，它构成 了u 的一个划分。u r 中的集合称为r 基本集或原子集。若将【，中的集合称为概念或表示 知识，则原子集表示基本概念或知识模块。若能表达成某些尺基本集的并或空集，则称 为尺可定义集，否则称x 为r 不可定义集。 r 可定义集是论域的子集，它可在知识库中精确地定义，而月不可定义集不能在这个 知识库中定义。r 可定义集也称为r 精确集，而r 不可定义集也称为r 非精确集或r 粗糙 集( r o u g hs e t ) 。 对于粗糙集可以使用两个精确集，即粗糙集的上近t 以( 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 ) 来描述。 给定知识库k = ( u ，胄) ，对于每个子集x u 和一个等价关系re i n d ( k ) ，定义两个子 集： r _ x = u x r | 【x 】r x ) = x t e u i 【工 r x j r x = u 【z r i 【x 】r n x ) = x u | 【z r n x j 分别称它们为的r 下近似集和r 上近似集。 下近似墨x 也称为x 的r 正域，记作p o s 。( x ) ，它可以解释为根据知识r 判断肯定属 于x 的对象所组成的最大集合，上近似r x 可以解释为根据知识r 判断可能属于x 的对象所 组成的最小集合。u 一死y 称作z 的r 负域，记作n e g 。( x ) ，它可以解释为由那些知识r 判 断出肯定不属于的对象所组成的集合。r x 一鱼z 称作肖的尺边界，记作b n d 。( x ) ，它可 以解释为由那些根据知识r 既不能判断肯定属于z 又不能判断肯定属于泸彳的对象所组 成的集合。 x 为r 可定义集当且仅当r x = r x ；z 为胄粗糙集当且仅当r x r x 。 尺的下近似集和上近似集有下列性质： ( 1 ) 丛x s r x ( 2 ) 墨妒= r = ，r u = r u = u ( 3 ) r ( x u y ) = r x u r y ；r ( n n = r x f 7 r y 第5 页 国防科学技术大学研究生院学位论文 ( 4 ) x y j 壁；x 至y 等尼r r y ( 5 ) 墨( x u 】，) 2 墨x u ；r ( x n y ) r x n r y ( 6 ) 墨( 一x ) = 一r x ；r ( 一x ) = 一1 6 ( 7 ) 星( 歹) = r ( ) = 星x ；r ( r x ) = 宣( 见r ) = r x 1 2 3 知识约简 图1 2 1粗糙集 知识约简是粗糙集理论的核心内容之一。知识库中知识并不是同等重要的，甚至其中某 些知i = 是冗余的，知识约简就是在保持知识库分类能力不变的条件下，删除其中不相关或不 重要的知识。 知识约简中有两个基本概念：约简( r e d u c t ) 和核( c o r e ) 。 在列约简和核进行讨论之前，先作如下定义： 令r 为一族等价关系，r r ，如果 i n d ( r ) 2 i n d ( r - r ) 则称r 为r 中不必要的：否则称r 为r 中必要的。 如果每一个r r 都为r 中必要的，则称胄为独立的；否则称胄为依赖的。 定理1 2 1 【2 8 】如果胄是独立的，p c r ，则p 也是独立的。 设p c _ r ，如果，是独立的，且i n d ( p ) = i n d ( r ) ，则称p 为矗的一个约简。显然，月可 以有多种约简。r 中所有必要关系组成的集合称为矗的核，记做c o r e 僻) 。 核与约简有如下关系： 定理1 2 2 【2 ”c o r e ( r ) = n r e d ( r ) ，其中r e d ( r ) 表示月的所有约简。 在应用中，一个分类相对于另一个分类的关系十分重要，因此我们将介绍知识的相对约 简( r e l a t i v er e d u c t ) 羊 1 $ 1 对核( r e l a t i v ec o r e ) 的概念。首先定义一个分类相对于另一个分类的正 域。 令p 和q 为u 中的等价关系，q 的p 正域记为p o s ，( q ) ，即p o s ，( q ) = u x e u q q 的p 正域是u 中所有根据分类u 尸的信息可以准确的划分到关系q 的等价类中去的 对象集合。 令p 和q 为等价关系族，r p ，如果 第6 页 里堕型堂堇垄盔堂丛塑竺堕堂焦适塞 p o s 。d ( p ) ( f n d ( q ) ) = p o s m d ( p 一( m d ( q ) ) 则称r 为p 中q 不必要的；否则称r 为p 中q 必要的。 为简单起见，也用p o s ，( q ) 代替p o s m p 、( i n d ( q ) ) 。 如果p 中的每个月都为q 必要的，则称，为q 独立的( 或尸相对于q 独立) 。 设s c p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p o s 。( q ) = p o s ，( q ) 。p 的 q 约简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核，记为c o r e 。( p ) 。 相对核与相对约简的关系见下述定理： 定理1 2 3 口” c o r e d ( 尸) = n r e d o ( p ) ，其中r e d o ( p ) 是所有p 的q 约简构成的集合。 1 2 4 知识的依赖性 知识的依赖性可形式化地定义如下：令o ( u ，月) 是个知识库，p ，q 月 ( 1 ) 知识q 依赖于知识p ( 记作p j q ) 当且仅当i n d ( p ) c i n d ( q ) 。 ( 2 ) 知识p 与q 知识等价( 记作e 一- q ) 当且仅当p j q 且q j 九 ( 3 ) 知识p 与q 知识独立( 记作p q ) 当且仅当p j q 与q j p 均不成立。 显然，尸；q 当且仅当i n d ( p ) = i n 坝q ) 。 当知识q 依赖于知识p 时，我们也说知识q 是由知识p 导出的。 定理1 2 4 1 2 8 】下列条件是等价的： ( 1 ) p j q ( 2 ) i n d ( p uq ) = i n d ( p ) ( 3 ) p o s ，( q ) = u ( 4 ) 对于所有x u q ，有丛= ，其中蹦表示i n d ( p 。 定理1 2 4 表明，如果知识q 依赖于知识p ，则在知识库中，知识q 是多余的。在这种 情况下，知识p u q 与知识p 提供同样的对象特征。 下面是依赖性的一些重要性质【2 8 】： ( 1 ) 如果p 等q 且q j 矗，则p ；月 ( 2 ) 如果且q 辛r ，则p u qj 矗 ( 3 ) 如果p ；月u q ，则p j r 且p j q ( 4 ) 如果p q 且矗u q j t ，则，u 露j 7 ( 5 ) 如果p q 且r j t ，则p u r j q u t ( 6 ) 如果p q 且p7 ) p ，则p 7 j q ( 7 ) 如果p j q 且q 7 c q ，则p q 7 有时候知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识p 导出的，部 分导出可由知识的正域来定义。 令o ( r ) 是一个知识库，p ，q g r ，当 k = 邝( q ) = l p o s ，( q ) l i u l 时，称知识q 是k ( o k 1 ) 度依赖于知识p 的，记作p j 。q 。 当k = l 时，称q 完全依赖于p ；当o k l 时，称q 粗糙( 部分) 依赖于p ；当k = o 时， 称q 完全独立于p 。如果p j q ，也记为p j q 。 第7 页 国防科学技术大学研究生院学位论文 由依赖性的定义可知，当p j 。e 时，则由q 导出的分类u e 的正域覆盖了知识库的 k 1 0 0 个元索；另一方面，只有属于分类正域的元素能被唯一的分类，即对象的k 1 0 0 可以通过知识p 划入分类u q 的模块中。 系数y ，( q ) 可以看作q 和p 间的依赖度。 当然，还可以使用粗糙依赖的另外度量，但这里的度量看来更适合于各种应用，并且也 易于计算和解释。 部分依赖p j 。q 的量度k 不能够完全反映u q 中类之间的分布情况。例如，一些决策 类可能完全由p 描述，但另一些可能仅仅由p 部分描述。因此，我们需要使用一个系数 ，( x ) = p x l i x l ，x u q 来表明通过知识p 能将v q 中每个类的多少个元素正确划分。 这样，两个值如( q ) 和y ，( x ) ，x u q 给出了知识尸的分类能力关于分类u q 的全 部信息。 1 2 5知识表达系统 知识表达在智能数据处理中占有十分重要的地位。 形式上，四元组s = ( u ，a ，v ，厂) 是一个知识表达系统，其中 队对象的非空有限集合，称为论域： a ：属性的非空有限集合； v = 【j 圪，圪是属性口的值域； 口e a 厂：u a v 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v a 4 ，x u ，f ( x ，口) 圪。 知识表达系统也称为信息系统，通常也用s = ( u ，a ) 来代替s = ( u ，a ，v ，f ) 。 知识表达系统的数据以关系表的形式表示。关系表的行对应要研究的对象，列对应对象 的属性，对象的信息是通过指定对象的各属性值来表达。容易看出，一个属性对应一个等价 关系，一个表可以看作是定义的一族等价关系，即知识库，从而知识约简可转化为属性约简。 如果( x ，y ) i n d ( p ) ，则称x 和y 是p 不可区分的。容易证明，v p a ，不可区分关系 i n 故尸) 是u 上的等价关系，符号u i n d ( p ) ( 简记为u p ) 表示不可区分关系i n d ( p ) 在u 上导 出的划分，i n d ( p ) 中的等价类称为p 基本集。符号b i ，表示包含x u 的尸等价类。 决策表是一类特殊而重要的知识表达系统，决策表可以根据知识表达系统定义如下： 设s = ( u ，a ，v ，f ) 为一知识表达系统，a = c u d ，c n d = ，c 称为条件属性集，d 称 为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。 在决策表中，不同的属性可能具有不同的重要性，为了找出某些属性的重要性 ( s i g n i f i c a n c e ) ，我们的方法是从表中去掉一些属性，再来考察没有该属性后分类会怎样变 化。若去掉该属性相应分类变化较大，则说明该属性的强度大，郎重要性高：反之，说明该 属性的强度小，即重要性低。 令c 和d 分别为条件属性集和决策属性集，属性子集c7 c 关于d 的重要性定义为 仃c d ( c ) = y c ( d ) 一y c - c , ( d ) 特别当c7 = f 口，时，属性日c 关于d 的重要性为 仃( 口) = r c ( d ) 一y c 一佃】( d ) 第8 页 国防科学技术大学研究生院学位论文 在决策表中，决策规则的产生也比较重要。设s = ( u ，a ，v ，f ) 是一个决策表， a = c u d ，c n d = ，其中为c 条件属性集，d 为决策属性集。令x ，和分别代表u c 与 u d 中的各个等价类，d e s ( x 。) 表示对等价类x ，的描述，即等价类x 对于各条件属性值的 特定取值；d e s ( y ，) 表示对等价类