（应用数学专业论文）变精度模糊粗糙集理论与应用研究.pdf

哈尔滨t 稗大学硕十学何论文 摘要 粗糙集理论作为一种新的数据分析理论，是处理具有不确定性的问题 的数学工具。粗糙集理论已广泛应用于数据挖掘、机器学习、人工智能和 模式识别等领域。但其自身尚存在一些局限，p a w l a k 粗糙集与变精度粗 糙集模型都是建立在等价关系基础之上。然而很多实际问题中所处理对象 本身可能就具有模糊性，对象之间也不存在分明的关系，而只存在模糊关 系。 属性约简问题是n p 问题，用传统的优化方法不能很好解决。本文把 蚁群算法应用到属性约简中，基于属性约简的特点修正了基本蚁群算法的 状态转移概率计算公式和信息素更新公式，以使得修正的蚁群算法更合适 于解决属性约简问题。 本文吸收了z i a r k o 的变精度思想，基于模糊相似关系提出了变精度模 糊粗糙集模型，研究了模糊集的变精度粗近似问题，并详细讨论了变精度 模糊粗糙集模型的性质。p a w l a k 粗糙集和z i a r k o 变精度粗糙集都是本文 提出的模型的一个特例。 在实际模糊聚类分析中，样本的属性重要性不同，甚至有的属性干扰 了聚类分析的结果。本文把变精度模糊粗糙集模型应用于模糊聚类分析中 的样本属性权值的确定问题。我们利用本文提出的模型和属性重要程度的 概念分析了聚类样本属性重要性权值。然后把分析的结果应用于模糊c 均值聚类算法。通过实验验证了基于变精度模糊粗糙集模型的属性重要性 分析方法可以有效的提高聚类质量。 关键词：粗糙集；变精度模糊粗糙集；属性约简；蚁群算法；模糊聚类 哈尔滨t 程大学硕十学何论文 a bs t r a c t a san e wt h e o r yo fd a t aa n a l y s i st h er o u g hs e t sa r ea l li m p o r t a n t m a t h e m a t i c a lm e t h o dt od e a lw i t hu n c e r t a i n t yp r o b l e m s i ti sw i d e l ya p p l i e di n v a r i o u sf i e l d ss u c ha sd a t am i n i n g ，m a c h i n el e a r n i n g ，a r t i f i c i a li n t e l l i g e n c ea n d p a t t e r nr e c o g n i t i o n b u tt h e r ea r es o m es h o r t c o m i n g sa b o u tc l a s s i c a lr o u g hs e t s t h e o r y p a w l a k sr o u g hs e t sm o d e la n dt h ev a r i a b l ep r e c i s i o nr o u g hs e t sm o d e l a r eb u i l to ne q u i v a l e n c er e l a t i o n s b u ti np r a c t i c a la p p l i c a t i o n s ，m a n yo b j e c t s w eh a n d l ea r ef u z z y ，a n dt h e r ea r en oc r i s pr e l a t i o n sb e t w e e no n eo b j e c ta n d a n o t h e rb u to n l y f u z z yr e l a t i o n s a t t r i b u t e sr e d u c t i o ni san pp r o b l e m ，a n dt h ec o n v e n t i o n a lo p t i m i z a t i o n c a n tb eu s e ds u c c e s s f u l l y i nt h i st h e s i st h ea c o a l g o r i t h mi su s e dt os o l v e t h i sp r o b l e m o nt h eb a s i so ft h ef e a t u r eo fa t t r i b u t e sr e d u c t i o n ，t h es t a t e t r a n s i t i o np r o b a b i l i t yf o r m u l aa n dt h ep h e r o m o n e u p d a t af o r m u l aa r em o d i f i e d t om a k ei tm o r ea d a p t i v et oa t t r i b u t e sr e d u c t i o n t h i st h e s i sp r o p o s e st h ev a r i a b l ep r e c i s i o nf u z z yr o u g hs e t sm o d e lo nt h e b a s i so ff u z z ys i m i l a r i t yr e l a t i o n s ，w h i c ha s s i m i l a t e st h ei d e ao fz i a r k o s v a r i a b l ep r e c i s i o nr o u g hs e t s t h e nt h er o u g ha p p r o x i m a t i o n so ff u z z ys e t sa r e s t u d i e d ，a n dp a r t i c u l a r l yt h ep r o p e r t i e so fv a r i a b l ep r e c i s i o nf u z z yr o u g hs e t s a r ei n v e s t i g a t e d p a w l a k sr o u g hs e t sa n dt h ez i a r k o sv a r i a b l ep r e c i s i o nr o u g h s e t sa r et w oi n s t a n c e so ft h em o d e lp r o p o s e d i nc l u s t e r i n ga n a l y s i s ，d i f f e r e n ta t t r i b u t e sh a v ed i f f e r e n ti m p o r t a n c ei n c l u s t e r i n g ，a n de v e ns o m ea t t r i b u t e sd i s t u r bt h ec l u s t e r i n gr e s u l t s i nt h i st h e s i s ， t h ev a r i a b l ep r e c i s i o nf u z z yr o u g hs e t sm o d e li sa p p l i e di n c a l c u l a t i n gt h e w e i g h t so fa t t r i b u t e s t h ew e i g h t so fa t t r i b u t e sa l ea n a l y z e db yv a r i a b l e p r e c i s i o nf u z z yr o u g hs e t sm o d e la n dt h en o t i o ni m p o r t a n c eo fa t t r i b u t e s t h e n t h er e s u l ti sa p p l i e dt of c ma l g o r i t h m 。e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e 哈尔滨t 程大学硕十学何论文 a t t r i b u t e s 、i t l ld i f f e r e n tw e i g h t sw h i c ha r ea n a l y z e db yv a r i a b l ep r e c i s i o n f u z z yr o u g hs e t sg r e a t l yi m p r o v et h eq u a l i t yo fc l u s t e r i n g k e y w o r d ：r o u g hs e t ；v a r i a b l ep r e c i s i o nf u z z yr o u g hs e t s ；a t t r i b u t e sr e d u c t i o n ； a c oa l g o r i t h m ；f u z z yc l u s t e r i n g 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文献 的引用已在文中指出，并与参考文献相对应。除文中己注明 引用的内容外，本论文不包含任何其他个人或集体己经公开 发表的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 作者( 签字) 张月毳 e lg q ： 沙口孵6 月厂日 哈尔滨t 程人学硕十学何论文 _ _ i 一r i i i i i i i i i i i i i 萱i i i i i 宣葺i i 宣i i | | 宣 第1 章绪论 1 1 粗糙集概述 1 9 8 2 年，以波兰数学家p a w l a kz 为代表的学者在研究不精确、不确定 性及不完全知识表示和分类问题的基础上，首次提出了粗糙集理论n 1 。粗 糙集理论是一种刻画不完整性和不确定性信息的数学工具，能有效地分析 和处理不精确、不致和不完整等各种不完备信息，并从中发现隐含的知 识，揭示潜在的规律。由于最初关于粗糙集理论的研究主要集中在波兰， 因此当时并没有引起国际计算机界和数学界的重视，研究地域仅限于东欧 一些国家。直到1 9 9 0 年前后，该理论在数据的决策与分析、模式识别、机 器学习等方面得到了成功的应用，才逐渐引起了世界各国学者的广泛关 注。1 9 9 1 年p a w l a k 教授出版的第一本关于粗糙集的专著乜1 和1 9 9 2 年 s l o w i n s k i 主编论文集的出版口1 ，推动了国际上对粗糙集理论与应用的深入 研究。1 9 9 2 年在波兰召开了第一届国际粗糙集合研讨会，这次会议着重讨 论了集合近似定义的基本思想及其应用和粗糙集合环境下的机器学习等 基础研究。从此每年都会召开一次以粗糙集理论为主题的国际研讨会，进 而推动了粗糙集理论的拓展和应用。另外，国际上还成立了粗糙集学术研 究会，参加的成员来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克 兰和印度等国家。目前粗糙集理论已成为人工智能领域中一个较新的学术 热点，引起了越来越多科研人员的关注。 粗糙集的研究对象是由一个多值属性集合描述的对象集合，对于每个 对象及其属性都有一个值作为其描述符号，对象、属性和描述符是表达决 策问题的三个基本要素。这种表达形式也可以看成一个二维表格，表格的 行与对象相对应，列对应于对象的属性；各行包含了表示相应对象信息的 描述符，还有关于各个对象的类别成员的信息。粗糙集理论建立在分类机 制的基础上，并将等价关系对空间的划分与知识等同。粗糙集理论的主要 思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的 l 哈尔滨t 程大学硕十学位论文 知识来近似刻画。在粗糙集理论中，“知识”被认为是一种分类能力，也就 是将知识理解为对数据的划分。在保持分类能力不变的前提下，通过知识 约简，导出问题的决策或分类规则。 1 2 粗糙集研究的进展 1 2 1粗糙集理论拓广方面的研究 由p a w l a k 教授提出的经典粗糙集理论虽然是一种比较有效的软计算 工具，但是它也存在一定的局限性。如它处理的分类必须是完全正确或肯 定的、所处理的对象是已知的，且从模型中得到的结论仅适用于这些对象 等，这些局限性都限制了它的应用。许多学者从多方面推广了这一模型， 其中最主要的是z i a r k ow 教授于1 9 9 3 年提出的变精度粗糙集模型h 1 。在这 个模型中，给定一个阈值，当对象所在的等价类在某种程度上包含于集合 肿时，就认为这个对象属于丘这一推广在应用中非常重要，因为实际 问题中绝对的包含有时是不必要的。目前，很多学者开始对变精度粗糙集 进行研究，并取得了一定的成绩。米据生1 等提出了基于变精度粗糙集模 型的知识约简方法，并给出了基于可变精度粗糙集模型的下分布约简及 上分布约简的概念及其等价定义，从而拓展了传统粗糙集理论的模型。 它是不协调目标信息系统知识约简的新方法。而菅利荣1 等根据可变精度 粗糙集理论提出了利用嵌套的等价关系集构造基于不同置信阈值不同 级别分类质量，的分层知识粒度及其相应的算法。该算法可根据不同置信 阈值、不同级别分类质量给出适宜的知识粒度，是一种比较灵活的应用算 法。 随着对粗糙集理论研究的深入，其内涵和外延都有了迸一步的拓宽和 延伸。如奇异粗糙集口1 ，基于相异关系的粗糙集理论1 ，基于相似关系的 粗糙集理论瞪1 ，基于相容关系的粗糙集理论n 等，这些都是对传统粗糙集 理论在一定程度上的扩展和补充。奇异粗糙集理论是山东大学史开泉教授 于2 0 0 2 年提出的，简写为啪集，包括单向奇异粗集与双向奇异粗集。而 2 哈尔滨下程大学硕十学何论文 相异粗糙集理论则利用相异关系代替p a w l a k 粗糙集理论中的不可分辨关 系，建立了基于相异关系的粗糙集理论，从而使粗糙集理论在完备信息系 统和不完备信息系统中的应用统一起来。基于相似关系的粗糙集理论针对 相似类中的元素无法区分正相似或负相似的问题，在相似关系粗糙集的基 础上，引入支配关系对相似类进行进一步分类，从而提出了基于相似关系 粗糙集的分解。基于相容关系的粗糙集模型则用相容核代替等价类来构造 上下近似算子，从而得到推广的粗糙集模型。该方法得到的上下近似算子 分别是闭包算子和内部算子，从而对未知知识的粗刻画更为精确。 1 2 2 粗糙集理论有效算法的研究 目前有关粗糙集有效算法的研究主要集中于规则提取。1 刀、属性约简 m 啦! 和数据挖掘嘲吨3 等方面。 1 2 3 连续属性的离散化 连续属性的离散化问题是粗糙集理论中一个重要的问题，对特征空间 进行离散化是一种有效的预处理手段。迄今为止，文献中已出现了大量的 离散化算法及其应用。根据不同的准则，离散化方法可以分为不同种类： 等间隔和等频率区间法、单规则离散器法伍町、基于统计检验的离散化方法 嘲、基于熵的离散化方法旺6 。删、自适应离散算法引口”、布尔量推理离散算 法口2 1 等。离散过程定义为由一个从给定决策表的属性的所有可能断点中选 出合适的断点。所有可能的断点是无限多的，但是它们可以被分成有限的 等价类，这样同一等价类中的断点是不可区分的。因此断点集可以由代表 等价类的断点子集所代替，而且在离散过程中代表断点的选择方法是确定 的。可以发现在离散化过程的开始时刻很难适当的选择代表断点集合，但 是在离散化过程结束后可以调整它们。 1 2 4 与模糊集的结合研究 粗糙集理论和模糊集理论都是研究信息系统中知识不完善、不精确问 哈尔滨丁稃大学硕十学何论文 题的方法，但粗糙集理论解决问题的出发点是信息系统中知识的不可分辨 性，而模糊集理论则关注信息系统中知识的模糊性，两者在处理方法上各 有特色。两者的结合可以更好地解决信息系统中不完善、不精确性知识的 问题。目前有关这方面的研究主要集中于粗糙集的模糊度概念口朝、模糊集 的近似算子以及粗糙集和模糊集的结合建立新模型脚箱1 等。z h a n g h u a g u a n g 等口阳研究了在粗糙集理论中引入两种算子，把粗糙集中著名的两 个不等式修正为等式，从而可以保证在新的表达式中不会再有信息丢失， 并利用新的算子分析了模糊集的粗糙度问题；米据生等阳刀的研究通过使用 三角模的概念，拓展了近似的概念从而产生了模糊集的上下近似算子，并 研究了两个近似空间的组成；j e n s e nr 等们则在模糊粗糙集模型的基础上 提出了基于蚁群最优化特征选择机制解决寻找最小特征集的问题；王健鹏 等口钔提出了基于覆盖的模糊粗糙集模型，讨论了该模型的一些相关性质， 并证明了论域上的任意子集相对于覆盖近似空间及其约简后的覆盖近似 空问的上下近似是分别相等的，从而简化了运算。另外，还有一些对比分 析模糊集与粗糙集各自优缺点的文献。模糊集理论是发展相对较成熟的 理论，在许多领域已有不小的成就，它与粗糙集的特点相互补充，将成为 新的研究热点。 1 2 5 其他方面的研究 随着粗糙集理论的发展，与之相关联的研究也越来越多“卜例。这些研 究都不约而同的用到了粗糙集理论，不论是在决策方面，评价方面，以及 与其他方法的相互关系上面，也都得出了一些有用的结论。另外，还有很 多应用粗糙集理论解决实际问题的相关文献。 1 3 粗糙集的应用 粗糙集具有较强的实用性，从诞生到现在虽然只有二十多年，但已经 在许多领域取得了令人鼓舞的成果。 ( 1 ) 粗糙集应用于智能控制。粗糙集根据观测数据获得控制策略的方 4 哈尔滨t 程大学硕十学何论文 法称为从范例中学习，属于智能控制的范畴。基本步骤是：把控制过程中 的一些有代表性的状态以及操作人员在这些状态下所采取的控制策略都 记录下来，形成决策表，然后对其分析化简，总结出控制规则。形式为： i fc o n d i t i o n = n 满足t h e n 采取d e c i s i o n = m 。粗糙集方法是一类符号化分 析方法，需要将连续的控制变量离散化，为此p a w l a k 提出了粗糙函数的概 念，为粗糙控制打下了理论基础。 ( 2 ) 粗糙集应用于神经专家系统。在专家系统中，知识获取是一个非 常关键的阶段，定义又很困难。由苏丹卡同大学、马来西亚大学和普恰大 学的m e 。y a h i a 、r m a h m o d 等研制的粗糙神经专家系统中提出将神 经网络作为专家知识库。而运用粗糙集作为数学工具来处理不确定与不精 确数据，将两者结合形成称之为粗糙神经专家系统的混合结构。前者作为 结构中神经网络的预处理器，为预处理粗糙引擎，而将后者加入该结构形 成粗糙神经推理引擎的推理引擎新结构，随之设计为一种新知识库结构， 其结构基于神经网络与粗糙分析约简的结合上。该系统已应用于医学诊 断，并通过了肝炎病例的检测。 ( 3 ) 粗糙集应用于决策分析。在决策分析方面，粗糙集理论的决策规 则是在分析以往经验数据的基础上得到的，它允许决策对象存在一些不太 明确的属性。希腊发展银行e t e v a 应用粗糙集理论协助制订信贷政策， 是粗糙集理论多准则决策方法的一个成功范例。另外，由意大利卡塔亚大 学学者g r e c o 和波兰波兹纳特大学的s l o w i n s h i 提出可以将粗糙集应用于多 标准决策分析。 ( 4 ) 粗糙集和模糊集在词汇挖掘中的应用。美国l o w au n i v e r s i t y 的 s f i m v 跏和l o u i s i a n as t a t eu n i v e r s i t y 的r u i z 等人指出，信息检索中的词汇 挖掘的意义是利用领域词汇提高用户的查询效率。通常用户的查询对检索 主题并不是优化的，词汇挖掘允许概括、细化或执行其他基于词汇查询的 转换，以提高查询性能。该文研究了一种新的词汇挖掘机制，它采用了粗 糙集与模糊集的结合。文本查询既可以使用权重即模糊表示，也允许使用 哈尔滨丁稗大学硕十学何论文 基于粗糙集的近似表示。该文探索和概括了粗糙集和可变精度模型，还解 决了多词汇视图的问题。最后分析了应用该词汇挖掘结构的联合医疗语言 系统。该机制支持语义和信息检索在不同的词汇视图中的应用。 ( 5 ) 粗糙集应用于股票数据分析。g o l a n 和z i a r k o 应用粗糙集理论分析 了1 0 年股票的历史数据，研究了股票价格与经济指数之间的依赖关系，获 得的预测规则得到了华尔街证券交易专家的认可。 ( 6 ) 粗糙集应用于医疗诊断。在医疗诊断方面，用粗糙集方法根据以 往病例归纳出诊断规则，用来指导新的病例。人工预测早产准确率只有 1 7 - 3 8 ，应用粗糙集理论可提高至f 1 6 8 - 9 0 。 r o u g hs e t s 理论的应用领域还包括：地震预报、冲突分析、近似推理、 软件工程数据分析、图像处理、材料科学中的晶体结构分析、预测建模、 结构建模、投资分析、电力系统等。 1 4 粗糙集研究的展望 1 4 1 粗糙集理论研究展望 目前，对粗糙集理论的研究集中在其数学性质，粗糙集拓广，与其它 不确定方法的关系和互补等方面。 ( 1 ) 粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构、 拓扑结构，以及粗糙集的收敛性问题。 ( 2 ) 粗糙集拓广方面的研究主要涉及广义粗糙集模型与对连续属性的 离散化等。 ( 3 ) 粗糙集理论与其他不确定性方法之间的关系的研究中，目前主要 讨论它与模糊集理论和证据理论的关系。 ( 4 ) 粗糙逻辑与近似推理的研究 1 4 2 粗糙集应用研究展望 粗糙集理论尽管已经取得了很多很好的应用结果，但仍然存在许多 6 哈尔滨t 稃大学硕十学何论文 问题。尽管人们已经对其中的某些问题进行了研究，但还没有取得令人满 意的结果。应用中存在的问题主要集中在以下几个方面 ( 1 ) 大数据集问题的解决 现实中的数据库已经越来越大，如何降低算法的执行效率和复杂度， 从众多数据中寻找最有用的数据，是粗糙集理论需要应对的一个挑战。虽 然目前这方面已有了一些研究成果，但是还不完善，仍需要进一步研究。 ( 2 ) 缺失值处理方法研究 在对样本数据进行处理时，往往会遇到数据丢失的问题。即不完备的 信息系统。造成数据丢失的原因很多，如对数据测量的误差、数据处理和 数据获取的限制等。由于经典粗糙集理论是基于完备信息系统的，为了使 这一理沦适合于不完备信息系统的处理，需要采用特定的方法对缺失值进 行处理，建立处理不完备信息系统的扩展粗糙集模型。 ( 3 ) 高效约简算法探索 属性约简的求解是一个n p 困难问题，导致该问题的主要原因是属性 的组合爆炸。高效的约简算法是粗糙集理论应用于知识发现的基础，要在 令人可接受的时间内获得约简的通常做法是基于启发式知识的约简方法。 国内外学者在这方面做了大量的研究，但是目前还不存在一种非常有效的 方法，因此寻找快速的约简算法及其增量版本这一问题仍是粗糙集理论的 研究热点之一。 ( 4 ) 连续属性的离散化处理 因为粗糙集只能处理离散化的属性，而现实中存在的数据一般具有连 续型的属性，因此，连续属性的离散化变得极为重要，已成为制约粗糙集 实际应用的一个很大障碍。目前已经有了一些这方面的相关研究，但是这 些方法或多或少的都存在一定的缺陷，还没有一种比较公理化的方法，因 此该问题的研究仍是今后的热点。 由于粗糙集在实际应用中取得了很好的结果，所以越来越多的学者开 始关注粗糙集理论，它已经成为人工智能领域的一个学术热点，而这又将 7 哈尔滨丁稗大学硕十学何论文 推动人们更深入的研究与应用它。 1 5 本文的主要工作 由于属性约简问题是n p 难问题，用传统的优化方法在多项式时间复 杂度内是解决不了的。本文把修正了的蚁群算法应用到属性约简问题。本 文在理论上对变精度粗糙集进行了拓广，基于模糊相似关系建立了变精度 模糊粗糙集模型。并证明p a w l a k 粗糙集和变精度粗糙集是本文所建立的 模型的特殊情况。然后详细讨论了所建立的模型的性质。最后把变精度模 糊粗糙集模型应用于模糊聚类分析中属性权值的确定问题，提高了聚类质 量。 1 6 本章小结 本章首先介绍了粗糙集的的产生，然后总结了粗糙集的发展历程以及 应用情况，展望了粗糙集理论的应用前景。最后阐述了本文的主要工作。 8 哈尔滨t 稃大学硕十学何论文 第2 章粗糙集基础理论 粗糙集理论是一种新的处理不确定性知识的数学工具，其主要思想就 是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类 规则。目前，粗糙集理论已被成功地应用于机器学习、决策分析、过程控 制、模式识别与数据挖掘等领域。本章介绍经典粗糙集理论( p a w l a k 粗糙 集模型) 的基本概念，作为后面各章节的基础m 1 。 2 1 知识与知识库 设u s 矽是我们感兴趣的对象组成的有限集合，称为论域。任何子集 x u ，称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是 一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。经典 粗集主要是对在u 上能形成划分的那些知识感兴趣。一个划分粤定义为： z = ，局，) ；su ，x ，对于i * j ，n 萄= 矽，f ，产l ，2 ， 3 ，刀；u 五= u 。 1 = 1 u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 设r 是u 上的一个等价关系，蚴表示r 的所有等价类( 或者u 上的 分类) 构成的集合。b 】。表示包含元素x u 的等价类。一个知识库就是一 个关系系统k = ( u ，a ) ，其中u 为非空有限集，称为论域，彳是u 上的 一族等价关系。 若p c _ a 且尸矽，则n p ( p 中所有等价关系的交集) 也是一个等价关 系，称为尸上的不可区分关系( i n d i s c e r n i b i l i t yr e l a t i o n ) ，记为i n d ( p ) ， 且有 x k 尸) = n 脚a 这样，跏，z d ( p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关系 族尸相关的知识，称为k 中关于u 的尸基本知识p 基本集) 。为简单起 见，我们用u p 代替劬锄d ( p ) ，i n d ( p ) 的等价类称为知识尸的基本概念 或基本范畴。特别地，如果q u r ，则称q 为k 中关于u 的q 初等知 9 哈尔滨下稃大学硕+ 学何论文 一i i i i 一 识，q 的等价类为知识尺的q 初等概念或q 初等范畴。 事实上，尸基本范畴是拥有知识尸的论域的基本特性，换句话说，它 们是知识的基本模块。 我们也可以定义：当胙( u ，a ) 为一个知识库，i n d ( k ) 定义为k 中所 有等价关系的族，记作i n d ( k ) = i n d ( p ) f p c _ a ) 。 例2 1 给定一玩具积木的集合泸 x l ，砣，x 8 ，并且假设这些 积木有不同的颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 小，大) 。 因此，这些积木都可以用颜色、形状、体积这些知识来描述。例如一块积 木可以是红色、小而圆的，或黄色、大而方的等。如果我们根据某一属性 描述这些积木的情况，就可以按颜色、形状、体积分类。 按颜色分类： x l ，x3 ，x7 红； x 2 x 4 蓝； x 5 ，x 6 ，x 厂黄； 按形状分类： 同 x l ，x5 倒； x 2 ，x6 方； x 3 ，x 4 ，x 7 ，x 8 三角； 按体积分类： x2 ，x 7 ，x f 一大； x l x 3 x 4 x 5 x 6 叫、。 换言之，我们定义三个等价关系( 即属性) ：颜色r 。，形状r ，和体积 r ，通过这些等价关系，可以得到下面三个等价类： u r l2 x l ，石3 ，x7 ， x2 ，x 4 ， x 5 ，x 6 ，x 8 ) ； u r 22 x l ，x5 ) ， x2 ，x 6 ) ， x 3 ，x 4 ，x7 ，x 8 ) ： u r3 = x 2 ，x7 ，x 8 ) ， x l ，x 3 ，x 4 ，x 5 ，x 6 ) ) 。 这些等价类是由知识库肛( 配 r 。，r ：，r ，) ) 中的初等概念( 初 1 0 哈尔滨t 程大学硕十学1 市论文 等范畴) 构成的。 基本范畴是初等范畴的交集构成的，例如下列集合： x l ，x 3 ，x7 ) n x 3 ，x 4 ，x7 ，x 8 ) = x3 ，x 7 ； x2 ，x 4 n x2 ，x 6 ) 5 x2 ； x 5 ，x 6 ，x 8 ) n x3 ，x 4 ，x7 ，x 8 2 x 8 ) ； 它们分别为 r 。，r ：) 的基本范畴，即：红色三角形，蓝色方形，黄色三 角形。 下列集合： x l ，x 3 ，x7 ) n x 3 ，石4 ，x 7 ，x8 ) n x2 ，x 7 ，x 8 ) = x7 ； x2 ，x4 ) n x2 ，x6 ) n x2 ，x7 ，x 8 2 x2 ) ； x5 ，x 6 ，x 8 ) n x 3 ，x 4 ，x7 ，x 3 ) n x2 ，x7 ，x 8 ) 2 x 8 ； 它们分别为 尺。，尺：，r ， 的基本范畴，即：红色大三角形，蓝色大 方形，黄色大三角形。 下列集合： x l ，x3 ，x7 u x 2 ，x4 ) 2 x l ，x3 ，x7 ，x 2 ，x4 ； x2 ，x 4 ) u x 5 ，x 6 ，x 8 ) 2 x2 ，x 4 ，x 5 ，x 6 ，x 8 ； x 1 ，x3 ，x7 ) u x 5 ，z 6 ，x s ) 2 x l ，x 3 ，x7 芦5 ，x 6 ，x 8 ) ； 它们分别为 r 的范畴，即：红或蓝( 非黄) ，蓝或黄( 非红) ，红或黄( 非 蓝) 。 有些范畴在这个知识库中是无法得到的，例如： x2 ，x 4 ) n x l ，x5 ) 2 矽； x l ，x 3 ，x7 ) n x2 ，x 6 ) 2 。 也就是说，在我们的知识库中不存在蓝色圆形和红色方形的范畴，即为空 范畴。 下面讨论两个知识库之间的关系。 令k 。- - ( u ，p ) 和k 2 = ( u ，q ) 为两个知识库，若i n d ( p ) = i n a ( q ) ，即 u q = u p ，则称k l 和k 2 是等价的，记作k l k 2 。因此，当k 1 和k 2 有 哈尔滨t 稗大学硕十学位论文 i 同样的基本范畴集时，知识库k ，和k ：中的知识都能使我们确切地表达关 于论域的完全相同的事实。 2 2 粗近似与粗糙集 令x c _ u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范畴 的并时，称x 是尺可定义的，否则称x 为r 不可定义的。 r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可 定义集不能在这个知识库中定义。尺可定义集也称作r 精确集。而灭不可 定义集也称为尺非精确集或r 粗糙集( r o u g hs e t s ) 。 当存在等价关系r e i n d ( k ) 且x 为r 精确集时，集合x c _ u 称为k 中 的精确集；当对于任何r e i n d ( k ) ，x 都为尺粗糙集，则称x 为k 中的粗 糙集。 对于粗糙集可以使用两个精确集来描述，即粗糙集的上近似和下近似 来描述。 定义2 1 给定知识库弘( u ，彳) ，对于每个子集x c _ u 和一个等价关 系r i n d ( k ) ，定义两个子集： 星胙u y eu r i y x ， 月弘u y eu r i y n x 矽 。 分别称它们为x 的r 下近似集和尺上近似集。下近似、上近似也可用下 面的等式表达： g x = x e 卅防】r 田， 尺_ ，- x ui x r n x * 矽 。 集合b n “x ) = r x - 星x 称为x 的尺边界域；p o s r = 宣x 称为x 的r 正域；n e g r = u - r x 称为x 的r 负域。显然：r x = p o s r u b n r 。 墨x 或p o s r 是由那些根据知识r 判断肯定属于x 的u 中元素组成 的集合：r x 是那些根据知识尺判断可能属于x 的u 中元素组成的集合； 6 力r 是那些根据知识，既不能判断肯定属于x 又不能判断定属于搿即 1 2 哈尔滨下程大学硕十学何论文 泸彳的u 中元素组成的集合；n e g r 是那些根据知识可判断肯定不属于 x 的u 中元素组成的集合。 下列性质是显而易见的。 ( 1 ) x 为r 可定义集当且仅当堡弘r x ； ( 2 ) x 为r 粗糙集当且仅当丛r x 。 定理2 1 卅 ( 1 ) 一r x c x c r 魁 ( 2 ) 星矿= r = 痧； ( 3 ) r 伍uy ) = r x ur 匕 ( 4 ) r n 功= r x n 尺k ( 5 ) x c 】，j r x c 一墨l r x c _ ry ( 6 ) 墨o 刈功2 墨x u 星y ( 7 ) 尺n 功r x nrh ( 8 ) r ( 埘尺凰 ( 9 ) 一r ( 埘= - r x ； ( 1 0 ) r ( r 脚= 页( 尺劢= 尺凰 ( 1 1 ) r ( r 劢= r ( 尺为= r 丘 集合( 范畴) 的不精确性是由于边界域的存在而引起的，集合的边界域 越大，其精确性则越低。为了更准确地表达这一点，我们引入精度的概念。 由等价关系尺定义的集合x 的近似精度为 口。：幽， “ ir xl 其中x ，i x j 表示集合x 的基数。 精度口。用来刻画我们对于了解集合x 的知识的完全程度。显然， 对每一个r 和x c _ u 有0 1 。当口r = 1 时，x 的r 边界域为 空集，集合x 为r 可定义的；当口ro | f ) ， x2，x 4 ，x 7 ，x 8 ) ， u r3 = ( x l ，x 5 ) ， x 6 ) ， x2，石7 ，x 8 ) ， x 3 ，x 4 ) ) 。 关系i n d 0 ) 有下列等价类： u i n d 0 ) = x 1 ，x5 ) ， x2 ，x 8 ) ， x3 ) ， x 4 ) ， x6 ) ， x7 ) 。 关系尺，为a 中必要的，因为 u i n d 0 一 r l ) = x i ，z 5 ) ， z 2 ，z 7 ，x 8 ) ， z 3 ) ， 石4 ) ， 缸6 ) ) u i n d 0 ) o 对于关系r ，有 u i n d 0 一 r2 ) ) = x l ，x5 ， x 2 ，x 8 ， x 3 ， x 4 ) ， z 6 ， x 7 ) = u a ， 故关系r ，是a 中不必要的。 同样，对于关系r3 有u i n d 一 r ，) ) = u a ，因此，r 。也是彳不必要 的。 为了得到么= 尺。，r2 ，r3 ) 的约简，我们检验 r i ，r2 ) ， r l ，尺，) 是否为独立的，因为u i n d ( r l ，r2 ) u i n d ( r 1 ) ) 且u i n d ( r l ， 尺2 ) ) u i n d ( r2 ) ) ，因此 尺l ，r2 ) 为独立的且 r 。，r ：) 为彳的一个 约简。同理， 尺。，r ，) 也是么的一个约简。 。 在应用中，一个分类相对于另一个分类的关系十分重要，因此我们将 介绍知识的相对约简和相对核的概念。首先我们定义一个分类相对于另一 1 6 哈尔滨t 程大学硕十学何论文 。 个分类的正域。 令尸和q 为u 中的等价关系。q 的尸正域记为p o s e ( q ) ，即 p o s e ( q ) 2 u 削，q 丛，q 的p 正域是u 中所有根据分类u p 的信息可以 准确地划分到关系q 的等价类中去的对象集合。 令p 和q 为等价关系族，尺p ，如果p o s i n a ( p ) ( i n d ( q ) ) ：p o s i d ( p - r ) ( i n d ( q ) ) ，则称尺为p 中q 不必要的；否则r 为尸中q 必要的。 为简单起见，我们也用p o s e ( q ) 代替p o s i d ( p ) ( i n d ( q ) ) 。如果p 中的 每个尺都为q 必要的，则称尸为q 独立的( 或称p 相对于q 独立) 。 设s c p ，s 为尸的q 约简当且仅当s 是尸的q 独立子族且p 蛳( q ) = p o s e ( q ) 。p 的q 约简简称为相对约简。尸中所有q 必要的原始关系构成 的集合称为p 的q 核，记为c o r e q ( p ) 。 相对核与相对约简的关系见下述命题：c o r e q ( p ) = ，p 如p ) 。其中 ，p 而( 尸) 为所有尸的q 约简。 2 4 知识表达系统与决策表 知识表达在智能数据处理中占有十分重要的地位。 形式上，四元组s = ( u ，a ，儿力是一个知识表达系统，其中 玑对象的非空有限集合，称为论域； 么：属性的非空有限集合； v = uv 。，v 。是属性a 的值域； u x a v 是一个信息函数，它为每个对象的每个属性赋予一个信 息值，即v 口4 ，i eu ，f ( x ，a ) v 。 知识表达系统的数据以关系表的形式表示。关系表的行对应要研究的 对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。 容易看出，一个属性对应一个等价关系，一个表可以看作是定义的一 族等价关系，即知识库。前几节讨论的问题都可以用属性及属性值引入的 分类来表示，知识约简可转化为属性约简。 1 7 哈尔滨丁稗大学硕十学位论文 例2 4 表2 1 给出了一个关于某些病人的知识表达系统。其中泸 e 。， e2 ，e ，e 。，e ，es ) ，彳= 头痛，肌肉痛，体温) 。属性头痛与肌肉痛中1 表示是，0 表示否；属性体温1 表示正常，2 表示高，3 表示很高。 表2 1 病人数据 病人头痛肌肉痛体温 p l lll e 2 ll2 e 3 ll3 e 4 o1l e 5 0o2 e 6 o13 在例2 4 中，若取属性集尸= 头痛，肌肉痛 ，弘 e ：，e 。，e 。) ，则 u p = e l ，e2 ，e3 ) ， p4 ，e6 ) ， e5 ) ) ，g 唧o sj p 2 e4 ，e 6 ， p x = e l ，e2 ，e3，e4 ，e 6 ) ，n e g p 2 u - p x 2 e5 ) ， 锄尸= 两一p x = e 。，e2 ，e ， 。属性集 头痛，肌肉痛，体温 有一个 约简 头痛，体温) ，而 头痛，体温) 也是核。 决策表是一类特殊而且重要的知识表达系统。多数决策问题都可以用 决策表形式来表达，这一工具在决策应用中起着重要的作用。 决策表可以根据知识表达系统定义如下： 设p ( u ，彳，n 力为一知识表达系统，a = c u d ，c n 胪，c 称为 条件属性集，d 称为决策属性集。具有条件属性和决策属性的知识表达系 统称为决策表。 在决策表中不同的属性可能具有不同的重要性。为了找出某些属性集 的重要性，可以从表中去掉一些属性，再来考察没有该属性后分类会怎样 变化。若去掉该属性相应分类变化较大，则说明该属性重要性高，反之说 哈尔滨t 程大学硕十学1 _ 7 ：论文 一i 一 明该属性重要性低。 属性子集c c 关于d 的重要性定义为 仃( c ) = y c ( d ) 一，( d ) ( 2 1 ) 其中y c ( d ) = l p o s c ( d ) u i 。 在决策表中，最重要的是决策规则的产生。 设p ( u ，么，儿力为一决策表，令x ，和】，分别代表u c 与u d 中 的各个等价类，d e s ，) 表示对等价类x ，的描述。即等价类x ，对于各条 件属性值的特定取值。d e s ( y ，) 表示对等价类】，的描述，即等价类y ，对 于各决策属性值的特定取值。 决策规则定义如下：，f ：d e s ( x f ) - - - d e s ( y ，) ，x fny 矽； 规则的确定性因子为，y ，) = ix ，n 】，i ix ，l ，o ( x 。，】，) l 。当( x j ，y ) = 1 时， 是确定的；当o ( x f ，y ) 1 时， ， 是不确定的。 注在产生决策规则之前，可先对决策表中的属性进行约简。 2 5区分矩阵与区分函数 利用区分矩阵( d i s c e r n i b i l i t ym a t r i x ) 来表达知识有许多优点，特别是 它能容易地计算约简和核。 令乒( u ，a ，以，) 是一个知识表达系统，lu | = 疗。s 的区分矩阵是 一个? x r 矩阵，其任一元素为 口& ，力= a e a1 研，口) 酝，口) ) 因此，口g ，y ) 是区别对象x 和y 的所有属性的集合。 下面我们