（计算机应用技术专业论文）基于进化算法的属性约简方法研究.pdf

摘要 数据挖掘是指从含有大量数据的数据库中提取有效的、有潜在价值的、新颖 的信息和知识的非平凡过程。在许多的数据挖掘方法中，粗糙集方法是其中的一 种很好的数据挖掘工具。在上个世纪八十年代粗糙集理论是由著名的波兰数学家 z p a w l a k 提出的处理模糊和不确定性问题的一种数学方法，它可以分析出隐含 在数据中的事实，并且基本上不需要提供任何相关数据附加信息，粗糙集理论已 经在社会许多领域中获得了比较成功的应用，比如模式识别、知识发现、机器学 习、决策分析等领域。 信息系统的属性约简是粗糙集理论的重要内容之一。但寻找信息系统的最优 约简或全部约简是一个n p 问题。遗传算法是一种模拟生物进化过程的最优解的 方法，具有全局搜索、鲁棒性强、可扩展性、隐含并行性等特点，已经被广泛应 用到粗糙集属性约简中。为了能够快速有效地获取信息系统中属性的最小约简， 在分析遗传算法与属性约简的方法的基础上，将属性重要性度量作为启发式信息 引入遗传算法，构造出了一种基于启发式变异算子的属性约简算法。该算法通过 构造新的变异算子来引入启发式信息，这样体现了启发式信息的局部搜索技术， 并使得该算法不仅保持整体优化特性，而且还具有较快的收敛速度。差分进化算 法是基于一种变异、交叉、选择的全局进化优化算法，将差分进化算法应用到多 个个体组成的群体，这样得到的群体中的个体可以一代接一代地得到优化，并逐 步逼近算法的最优解。该文将差分进化算法引入粗糙集属性约简中，构造出基于 差分进化算法的粗糙集属性约简算法。实验结果表明，这两种方法都能快速有效 地求出决策表的最小约简。 关键词：粗糙集；属性约简；遗传算法；核；差分进化算法 a b s t r a c t d a t am 1 n l n g1 sa o r d i n a r yp r o c e d u c et h a tt a k i n ge f f e c t i v ea n d p o t e n t i a lv a l u eo f n e wi n t o 加a t l o na n dk n o w l e d g ef r o m q u a n t i t i e so fd a t a i nm a n yo ft h em i n i n g m e t h o d s ，r 。u g h s e tm e t h 。d si s 。n e 。f t h eu s e f u it 。i s 。fd a t am i n i n g r 。u g hs e t t h e o r y1 sam a t h e m a t i c a lm e t h 。dt od e a 】w i t hv a g u ea n du n c e r t a i n q u e s t i o nw h i c h p r o p o s e d b yp a w l a ki nt h ee a r l y19 8 0 sa n dc a nm a k e aa n a l y s i so ft h er u l ec o n t a i n e d m t h e d a t a w l t h 。u ta n ya d d i t i 。n a li n f o m a t i o l l r o u g h s e tt h e 。r yg e t s s u c c e s si n m a n yt ，e l d s ，s u c ha sp a t t e r ni d e n t i f y i n g ，k n 。w l e d g ed i s c o v e r y ，m a c h i n el e a r n i n ga n d d e c i s i o n a n a l y s i s t h ea t t r i b u t er e d u c t i o no fi n f o r m a t i 。n s y s t e m si s 。n e 。ft h e ：r e p o r t a n t 小姐“0 u g h s e tt h e o r y t of i n dt h eb e s tr e d u c t i o no ra i i r e d u c t i o no f i n t o m a t l o ns y s t e m si s t h en p - h a r dp r o b l e m g e n e t i ca l g o r i t h mi s a 。p t i m i z a t i o n m e t h o dw h l c hs i 砌l a e s t h ep r 。c e s s 。f b i 。1 0 9 i c a l e v 。l u t i 。n ，w i t hg l o b a ls e a r c h r o b u s t n e s s , s c a l a b i i m p l i c i tp a r a l l e l i s m ，e t c ，a n dh a sb e e nw i d e l yu s e dt o t h e a t t r i b u t er e d u c t i o no fr o u g hs e t t og e tt h em i n i m a l r e d u c t i 。no ft h ei n f o r m a t i 。n s y s t e m sq u l c k l ya n d e f f e c t i v e l y , b a s e do ng e n e t i ca l g o r i t h ma n d a n a l y s i s 。fa t t r i b u t e r e d u c t l 。n ，t h l s p a p e r1 0 0 k s 。nt h es i g n i f i c a n c eo fa t t r i b u t e sa sh e u r i s t i ci n f o n n a t i o n ：n t r o d u c e s t h e h e u r i s i c i n f o r m a t i o ni n t o g e n e t i ca l g 。r i t h m ，a n d p r 。p o s e sa n ? p ? d h e u r i s i t 沁g e n e t i ca l g o r i t h m t h i s p a p e rp r o p o s e san e wm u t a t e0 p e r a t o r 士o r i n t m d u c l n gt h eh e u r i s i t i ci n f o r m a t i o na n dt h e t e c h n 0 1 0 9 yi sal o c a ls e a r c h m e t h o du s l n gh e u r i s i t i ci n f o r m a t i o l l t h e r e f o r e ，t h e a l g 。r i t | l m h a sg l o b a l0 p t i m i z i n g a b i l i t y a n d c o n v e r g e sq u i c k l y d i f f e r e n t i a l e v 。l u t i 。n a l g o r i t h mi s a g l o b a 。l ? 1 u ：o n a r y o p t 油i z e da 1 9 0 r i t h m ，w h i c hb a s e do nm u t a t i o n 、c r o s s o v e r 、s e l e c t i o n 1n l sa j g 训h mc a na p p l i e dt o an u m b e ro fi n d i v i d u a l ss o t h a tm o s to ft h e mc a n 。p t i m i z e df r o mg e n e r a t i o n t o g e n e r a t i o n ，a n df i n a l l yi t g r a d u a l l ya p p r o a c ht h e o p t i m a ls o l u t i o n t h i s p a p e rw i l li n t r 。d u c e d i f f e r e n t i a l e v 0 1 u t i 。n a l g 。r i t h mi n a t t r i b u t e r e d u c t i o no fr o u g hs e t ，a n d c o n s t r u c tad i f f e r e n t i a l e v o l u t i o na 1 9 0 r i t h m w h l c hb a s e do na t t r i b u t e r e d u c t i o no fr o u g hs e t t h e r e s u l t ss h o wt h a tt h et w o m e t n o d sc a nc a l c u l a t em i n i m a l r e d u c t i o no fd e c i s i o nc h a r t sq u i c k l y a n de f f e c t i v e l v k e yw 。r d s ：r 。u g hs e t ； a t t r i b u t er e d u c t i 。n ； g e n e t i ca i g o r i t h m ； c 。r e ； d i f f e r e n t i a le v o l u t i o na l g o r i t h m i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律后果由本人承担。 作者签名：常磋 日期：2 01 0 年月了日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：殇彳寥 日期2 0 1 。年名月了日 新虢臀武眺2 年占月弓日 第一章绪论 1 1 课题研究目的与意义 粗糙集理论是在概率论、证据理论、模糊集理论之后的另一个解决不确定性 和含糊性的数学方法。该理论的基本思想是指保持其分类能力没有变的情况下， 通过属性约简，得出问题的分类规则与决策。该方法不需要先验知识或者任何额 外的信息，就可以有效地分析并处理不一致、不完整和不精确的数据，并可以从 数据中发现隐藏的知识，揭示隐含的方法规律。粗糙集理论的重要特点主要是它 并不需要和数据相关的任何准备的和额外的附加信息。粗糙集理论方法已经在许 多方面取得了很成功的应用，例如数据挖掘、模糊识别、机器学习、过程控制和 决策分析等。 粗糙集理论的关键点是将知识和分类结合在一起，利用等价关系概念化地表 达知识的分类，知识被看作是对研究对象的一种分类能力。知识并不是所有的都 是必要的，这样就导致了知识的约简问题。知识约简( 属性值约简与属性约简) 就是 指保持决策信息系统在分类能力没有变的情况下，删除可以忽略或者冗余的知识。 这些存在的冗余知识不仅是对资源的重要浪费( 需要大量的处理时间与存储空间) ， 而且会影响人们做出简洁而正确的决策，从而影响了人们认识和使用信息系统的 准确性。 粗糙集理论的重要内容是属性约简算法。启发式属性约简算法有许多类，传 统的基于遗传算法的约简方法是其中的一类。因为遗传算法自身具有隐含并行性 和全局优化等特点，因此采用遗传算法求知识约简的解，一般会降低计算的复杂 度且可以得到属性最小约简或属性最小相对约简。可以采用多种启发式方法求一 般遗传算法的属性约简算法的解，利用分析国内国外许多种基于遗传算法的粗糙 集属性约简算法差异的地方，在编码方法、适应度函数确定和遗传操作的选择存 在差异，但由于遗传算法理论本身存在的不足和局限性以及粗糙集属性约简的 n p h a r d 缺点，使得启发式遗传算法有很多需要改进、优化的地方，比如编码方式 和初始化种群的选取，启发式信息的设计，修正算子的如何修正以及三种遗传算 子方法的选择问题都是制约遗传算法约简效率的关键问题，是需要深入研究探讨 的方向。研究改进更加快速、更加有效的粗糙集属性约简算法是该篇文章的主要 研究目的。 探索研究粗糙集属性约简在实际生活中的应用有着非常深刻的意义，化简多 余的数据，保留最佳的规则，可以极大地提高处理数据的效果。将粗糙集理论和 属性约简算法结合能够进行知识获取、图像处理、机器学习、模型建立、决策制 定等应用。效率高的属性约简算法是粗糙集理论运用在知识发现与数据挖掘领域 的基础。但是，1 9 8 5 年著名学者z i a r k o 和w r o n gs k m 已经证明找出一个决策表 或者信息系统的最小约简是一个n p h a r d 问题，产生这个问题的原因主要是数据 的组合爆炸导致的，且不存在规范统一的高效率方法，事实上对于大型数据库来 说，属性最小约简是并不存在的，学者们通常所得到的只是属性的相似约简。所 以，研究探讨更为高效的属性约简算法，减小算法的时间复杂度，寻找快速的属 性约简算法，有效地得到属性最小约简仍将是粗糙集方法今后研究的重要课题内 容。作者采用两种约简方法求解粗糙集理论中的属性约简问题，一种是基于启发 式变异算子的属性约简算法，另外一种是基于差分进化算法的属性约简算法，实 验结果表明，这两种算法都是求解知识约简问题的快速有效的方法。 1 2 粗糙集国内外研究现状 波兰华沙大学著名的数学家z p a w l a k 教授在2 0 世纪8 0 年代就关于集合论和 模糊集的理论提出了粗糙集理论，并且在其数学性质和逻辑系统的根本上进行深 入分析。最初此理论是建立在商集的基础上，由于数学问题比较复杂，该理论并 没有引起人工智能学者的关注，其研究的范围也仅仅局限在波兰等一些东欧国家。 尽管许多波兰学者在当时对粗糙集理论以及应用做了不断地学习研究，但真正开 始引起世界各地研究者关注的时候，则是2 0 世纪8 0 年代末的事情了。 z p a w l a k 教授在1 9 9 1 年出版了 专著，该书 系统地概括了粗糙集理论的相关概念心1 。r s l o w i n s k i 在1 9 9 2 年发表的关于粗糙集 理论的应用论文集更好的分析了这时期该理论及其实践的主要贡献，进一步加速 了粗糙集理论在多个领域的运用和发展1 。从那时候开始，该理论得到了各国学者 的注意，粗糙集开始了新的发展热潮，。 第一届国际粗糙集研讨会1 9 9 2 年在波兰举行，该会议重点研究了关于集合近 似的基本思路与应用【s ，。从那以后关于粗糙集理论为内容的国际研讨会每年都要举 行一次。1 9 9 3 年第二届国际粗糙集与知识发现研讨会在加拿大隆重召开m - 。该会 议重点是积极发展世界各国对粗糙集与应用的研究，特别是提出了很多关于粗糙 集理论的知识发现系统和方法。1 9 9 4 年，第三界国际粗糙集与软计算研讨会在 美国举行，该会议主要探讨粗糙集与模糊逻辑、进化理论、神经网络等内容的相 关问题。1 9 9 5 年几位主要倡导粗糙集理论及其应用的研究者在第1 l 期a c m 通 讯上发表文章，系统地概括了粗糙集理论的基本概念，它是当前人工智能应用方 面的新技术之一，该文章还介绍了粗糙集理论在知识获取、决策分析、机器学习、 知识发现等方面的具体研究内容以及发展速度阳1 。当年举行的第四届模糊理论与技 术国际研讨会也对模糊集和粗糙集的之间关系和基本观点进行了激烈的讨论，在 一定程度上加深了对粗糙集的理解。而1 9 9 6 年又在f 1 本举行了第一次在亚洲地区 召开的关于粗糙集的研讨会一一第五届国际粗糙集研讨会。1 9 9 9 年日本又举行了 第七届关于粗糙集的相关会议，此次会议重点阐述当前模糊集、粗糙集的发展趋 势与研究现状，并且做出要将研究的重点放在软计算、人工智能、数据库以及近 似推理等理论应用上。 中国研究者也踊跃参加粗糙集理论及其应用的研究，起步虽晚但发展很快。 2 0 0 1 年“第一届中国粗糙集和软计算学术研讨会”在重庆邮电大学成功召开。粗 糙集理论的创造者z p a w l a k 教授被大会邀请作报告，该研讨会提高了我国及亚洲 地区关于粗糙集理论及其应用的研究速度。粗糙集与软计算专业委员会以及中国 人工智能学会在2 0 0 3 年成立。而首届粗糙集与知识技术国际会议也于2 0 0 6 年7 月在重庆召开。现在越来越多的国内专家研究粗糙集理论，且已经形成一支比较 大的学术研究队伍，中国学者开始在这方面发挥越来越大的作用。 在粗糙集理论中研究有效算法是其在人工智能研究方向中的一个重要方向。 目前，粗糙集理论中研究有效算法主要体现在属性约简算法、规则提取、遗传算 法研究和神经网络等。属性约简在粗糙集理论中是很重要的一个问题“。属性约 简的关键就是指在保持决策表或信息系统中分类能力没有改变的状况下，删除其 中不重要或者不相关的属性【t “。但现在已经证明了求解最小约简或者所有约简是 n p h a r d 问题。求解核和属性约简一直以来都是粗糙集理论研究的热点与难点。现 在的属性约简算法主要分为三个方面： ( 1 ) p a w l a k 属性约简算法。该算法根据属性约简的定义进行求问题解，并且需 要考察关于条件属性集的幂集中的所有元素，故具有指数型时间复杂性，该方法 具有非常强的理论指导意义，但由于计算速度比较慢，且在计算机上实现比较困 难，因此，在实际应用中局限性非常大。 ( 2 ) 区分矩阵属性约简算法1 。由著名的波兰华沙大学数学家s k o w r o n 提出来 的区分矩阵是求解最小约简的非常有用的工具。利用区分矩阵求得核属性，依据 核属性来求解区分函数的最小吸取范式，最后求得的每个析取分量表示对应的一 个属性约简，因此就可以得到所求最小约简。方法的时间复杂度为 0 ( 2 旧木l 彳u i * l o g i 【，i ) ，其中a 表示属性集合，x 表示条件属性c 的子集，l u l 表示对象集合，对比p a w l a w 属性约简算法的时间复杂度，该算法会减少一半，且 可以很快求出决策表的所有约简，并且能够正确找到最小约简，但该方法在解决 含有大量数据的决策表属性约简的问题上，效率并不是很高，。 ( 3 ) 启发式属性约简算法n “。现如今研究这类约简算法的方法比较多。主要有 通过属性重要度、区分矩阵中属性频度以及基于遗传算法等启发信息来求解决策 表的约简。处理大规模数据集都可以采用这类算法。现有关于属性约简算法的文 章绝大部分都是在基于区分矩阵与基于属性重要度的两种方法基础上提出，例如 比较有影响的有x h u 提出的基于属性依赖度的属性约简方法n “，基于属性重要度 的属性约简算法，胡桂荣等人也提出了基于属性互信息的属性约简方法“，基于 关联矩阵的属性约简算法与基于区分矩阵属性频率l - ”等算法都有各自的特点“。王 学峰等人提出的基于遗传算法求解属性的最小约简方法取得了不错的结果n ”。文 献 2 0 1 提出的启发式遗传算法，是在优化初始种群的基础上以属性重要度作为启发 式信息来提高算法的性能；李金海等人提出的方法是以基于信息论中的互信息定 义属性重要度作为启发式信息进行属性约简，实验表明该算法具有不错的收敛速 度和约简效果心“。 1 3本文研究内容和结构安排 作者详细地介绍了粗糙集多种属性约简方法。通过分析对比多种属性约简算 法的情况下，对基于进化算法的属性约简算法进行了研究。通过将基于启发式信 息的遗传算法与粗糙集理论结合，将其应用到解决信息系统的属性约简问题，通 4 过改进传统的遗传约简算法，运用信息论和启发式的理论，构造出基于启发式变 异算子的属性约简算法，提高了信息系统约简的效率。此外，将差分进化算法与 粗糙集属性约简结合，构造出基于差分进化算法的属性约简算法，该算法也提高 了约简效率。 该文主要研究内容及结构安排如下： 第一章主要介绍粗糙集研究目的及其意义，并且还介绍了粗糙集的国内外研 究现状。 第二章是粗糙集理论的一些相关基础知识。在该章中详细地介绍粗糙集理论 的基础概念，包括粗糙集的研究对象、粗糙集的特点、知识与知识库、上下近似 集、属性核及其约简，知识依赖性等内容。 第三章构造了一种基于启发式变异算子的属性约简算法，通过分析该算法的 主要思想，确定了三种算子的设计以及实现方法；该章通过引入属性核限制初始 群体，这样避免盲目的随机产生种群，从而极大地减少算法的搜索空间，并保证 了算法结果的正确性。同时该算法提出了启发式变异算子与修正算子的局部优化 策略，用这两种算子对种群进行局部优化，使得可行解总在搜索的范围内，从而 提高算法局部搜索能力。实验结果表明该算法能够快速有效地得到最小约简，即 该算法效率高于其它一般基于遗传算法的约简算法。 第四章根据差分进化算法是一种基于种群新的进化方法，并且它优化实值参 数具有非常强的优化性能，且其原理比较简单，受控的参数少等优点，将该算法 与粗糙集属性约简结合，构造出基于差分进化算法的属性约简算法，实验表明该 算法能够快速有效地求得属性的最小约简。 最后的结论是对全文的研究工作做了分析与总结，并提出下一步需要做的工 作。 第二章粗糙集基本理论 粗糙集理论是处理不相容、不完备、不精确数据的理论方法，是传统集合论 的延续发展，为现实生活数据的知识学习、挖掘、表示和归纳等内容的学习提供 了一类有效的处理方法与技术【z 2 2 3 1 。目前，粗糙集在决策分析、过程控制、机器学 习、知识获取等各个领域取得了大范围的应用，并且已经是人工智能领域中比较 新的一个学术研究点， 2 1 粗糙集理论概况 2 1 1粗糙集研究对象 粗糙集的研究对象是用多值属性( 症状、特性、特征等) 集合表示对象( 观 察、病历等) 集合，每一个属性与对象都用描述符号表示对应值，属性、对象与 描述符是描述决策问题的三个重要要素。可以用这种描述方式作为一个二维表格， 表格的行表示对象，表格的列表示对象的属性；每一行不仅可以表示相关对象信 息的描述符，而且还可以表示相关对象的成员类别信息。通常情况不一定能够将 对象所求得的信息划分成其类别成员。换句话说，对象的不可分辨性就是由上述 不确定性所产生的。在对象它们之间确定一个等价关系，然后利用这种等价关系 组成近似空间，称这种近似空间是不可分辨关系，从而粗糙集就能够利用这种关 系类产生的下近似与上近似表示。它们各自描述了可能属于确定类的最小对象集 合和属于确定类的最大对象集合。上近似与下近似之间的差是一个边界集合，该 集合表达了那些所有不可以肯定属于具体类的对象。 2 1 2 粗糙集理论特点 粗糙集理论比较简单、且实用性比较强，可以在建立后很快的时间内就能够 快速的得到运用是由于其含有如下的优点： ( 1 ) 可以处理数据的模棱两可与不精确性，包括非确定性和确定性两种情况。 ( 2 ) 可以得出知识多种不同层次颗粒以及它的最小表达。 ( 3 ) 可以从数据中得出容易操作且概念容易理解的方式。 ( 4 ) 可以得到准确且容易证实和检查的决策，尤其在智能控制中生成的决策比 6 较适用。 ( 5 ) 可以解决多种数据，包括含有许多变量的数据和结构不完整的数据。 2 2 粗糙集理论的基础知识 2 2 1知识和知识库 粗糙集理论主张“知识是对对象进行分类的一种能力”，此处的“对象”是 指任何实物、抽象概念、状态、时间和过程等，也就是说，知识需要相关的各种 分类模式以及抽象或具体的特定语境结合一起，将这个特定语境叫做论域。知识 又指人类在进行现实生活的实践中所得到经验和认知，并具有规律性、普遍性和 抽象性，而且又可以作为指导人们行为的原则。知识是规则、命题等方面的集合， 通常可以将它分为控制性知识、说明性知识和过程性知识。粗糙集理论表示知识 是直接与抽象或真实生活中的不同分类模式结合在一起，所以知识可以描述任何 客观存在的事物。可以理解知识为对事物的一种分类能力，也可以用知识系统的 集合表达形式描述它的这种分类能力。 定义2 1设u 表示对象构成的j e 空有限集合，称这个集合为论域。论域u 上的范畴或者概念指的是论域u 中任何一个子集xgu 。同时认为空集也是概念， 简称空概念。论域u 中任何概念簇或子集簇表示关于论域的抽象知识，称为知识。 其中每一个子集或者概念都可以描述知识的一个信息粒。 一般求解问题的过程中，研究者需要解决的是论域u 上的一簇划分并不是论 域u 上的单一划分( 分类或知识) ，知识库的概念由此产生。 定义2 2 对于给定的论域u 及其上的等价关系s ，一般称二元组k = ( u ，s ) ， 是与论域u 相关的近似空间或者知识库。 定义2 3对于给定的论域u 及其上的等价关系s ，如果p s ，且p o ， 则n p ( 表示p 中所有等价关系的交集) 依然是关于论域u 上的等价关系，则简称其 为p 上的不可分辨关系，将该不可分辨关系描述为i n d ( p ) ，经常将其简单标为p 。 并且有v x u ，【工 ，d ( p ) = x 】j p = ，n 工】r 。 v 口# p 通常将u i n d ( p ) = 【x 】，。( p ) iv x u 描述为和等价关系i n d ( p ) 相关的知识， 简称为知识库k = ( u ，s ) 中和论域u 相关的p 基本集或p 基本知识。平时为了方便， 7 采用【厂尸替代u i n d ( p ) ，u i n d ( p ) 的等价类表示知识p 的基本范畴或基本概 念。尤其当q s 时，则认为q 是表达论域u 上的q 初等知识，q 的等价类也可 以表示为知识s 的q 初等范畴或初等概念。 现介绍一个例子说明相关知识，对于给定的玩具积木论域u = x 1x 2 ，x s ，可 以设这些积木有几种不同的颜色( 红色、黄色、蓝色) ，形状有( 方、圆、三角) ， 体积有( 大、小) ，如下表2 1 所示。所以能够利用颜色、形状、体积三种知识来 表示积木，比如一块积木能够用蓝色、大而方的，或红色、小而圆的等。若依据 其中一个属性表示积木的状况，可以采用按颜色、体积、形状进行分类。 表2 1 积木信息表 积木( u )颜色( r 1 )形状( r 2 )体积( r 3 ) x i 红 圆小 x e 蓝 方 大 x 3 红 三角小 x 4蓝三角小 x 5 黄圆小 x 6黄方小 x 7红 三角大 x 8 黄三角大 采用颜色分类：红色= “，x 3 ，x 7 ；蓝色= x 2 ，x 4 ) ；黄色= x 5 ，x 6 ，x 8 ) 。 采用形状分类：圆形= 五，x 5 ) ；方形= x 2 ，x 6 ) ；三角形= 屯，x 4 ，x 7 ，x s ) 。 采用体积分类：大= 恐，x 7 ，x 8 ) ；小= 五，x 3 ，x 4 ，x 5 ，x 6 ) 。 也就是说，3 个不同属性表示3 个不同等价关系：颜色r l ，形状恐，体积r ， 利用上面3 种不同等价关系，将论域划为下面几种不同集合描述。 u u u 墨= 五，x 3 ，而) ， 恐，_ ) ， 墨，x 6 ，黾) ) 。 足= 五，墨 ， 屯，氏 ， 恐，x 4 ，x 7 ，黾) 。 是- - i x , ，x 7 ，黾) ， 五，x 3 ，x 4 ，x 5 ，讫) 。 上述等价类组成了知识库k = ( 【， 属，恐，玛) ) 中的初等范畴或初等概念。初等范 畴的交集组成了基本范畴，比如： x 5 ，气，x s ) f i x 3 ，x 4 ，x 7 ，x s ) = 黾) ， x 2 ，_ ) n 恐，讫) = 屯) ， 五，恐，x ， n x 3 ，i ，_ ，黾) = 屯，为) 。 上述各自表示 尺。，是) 的基本概念：黄色三角形，蓝色方形，红色三角形。同 理能够得到知识 墨，忍) 或者 足，b ) 的基本概念。 x 2 ，x 4 n x 2 ，x 6 ) i 1 x 2 ，x 7 ，x s ) = x 2 ) ， x 5 ，x 6 ，x s n x 3 ，墨，_ ，x s n x 2 ，_ ，黾) = 黾) ， 玉，恐，而) n 五，屯，_ ，黾) n 恐，为，黾 = _ ) 。 上述各自表示了 墨，足，r 的基本概念：蓝色大方形，黄色大三角形，红色大 三角形。 2 2 2 近似与粗糙集 该小节是以传统集合论为根本，介绍粗糙集理论的相关概念，例如上近似、下 近似、正域、边界域、负域、不分辨关系、粗糙度以及近似精度的定义及其性质。 定义2 4对于知识库k = ( u ，s ) ，其中u 表示论域，s 是关于论域u 上的一 个等价关系簇，则栅u ，论域u 上有一个等价关系r i n d ( k ) ，那么可以确定 论域u 上子集x 关于知识r 的上近似和下近似依次表示 豆( x ) = xa ( v x u ) a ( r x l 足n x ) ) = u yi ( y u r ) a ( ynx ) ) ， 星( x ) = xi ( 觇u ) 人( x 】只x ) ) = u 】，i ( v 】厂u r ) 人( y x ) ) 。 集合p o s 矗( x ) = 尽( x ) 简称x 的r 正域：b n 冗( x ) = 豆( x ) 一叁( x ) 简称x 的r 边界域；将n e g 月( x ) = u - k ( x ) 称为x 的r 负域。很明显豆( x ) = p 月( x ) u 6 ( x ) 。 上近似k ( x 1 指在论域u 中通过知识r 决定肯定属于或者可能属于子集x 中 元素构成的集合；正域p o s 矗( 彳) 或下近似叁( x ) 指在论域u 中通过知识r 决定肯定 属于子集x 中元素构成的集合；r 负域n e g r ( x ) 指在论域u 中通过知识r 决定不 属于子集x 元素构成的集合。r 边界域6 n r ( x ) 指在论域u 中通过知识r 决定既不 能肯定属于子集x 又不能肯定不属于子集x 中元素构成的集合； 定义2 5对于论域u 及u 上的一个等价关系r ，v xs u ，如果豆( x ) = 尽( x ) ， 则称子集x 关于论域u 相对知识r 的r 一可定义集或r - 精确集；如果豆( x ) 尽( x ) ， 则称子集x 关于论域u 相对知识r 的r 不可定义集或r 粗糙集。 在粗糙集理论中任意有限个r 基本概念的并，都可以简称r 可定义集或者 r 精确集，如果论域u 及r 得到肯定时，称之为可定义集或精确集。 给一个例子说明上述概念，如对于论域u = 五，恐，而 及u 上的等价关系r ， 如果u 尺= 巨，巨，岛 ，其中巨= 恐，x 4 ，屯，毛 ，易= 五，屯) ，历= 讫，而，而 。求集 9 合k = 五，x 3 ，鼍 的r - 上近似、r - 下近似、r 一正域、r 一边界域和r 一负域。 r 上近似豆( k ) = xr ( v 艇v ) a ( t x 尺nr l g ) ) = e lu 最， r - 下近似_ r ( r 1 ) = x i ( v x u ) 人( x r k ) ) = 最， r 一正域p o s r ( x ) = r _ ( r 1 ) = 乞， r 边界域b n r ( r 1 ) = 豆( x ) 一r ( x ) = 巨， r 负域n e g r ( 】= i ) = u 一豆( x ) = 与。 通过上面的结果可以得出集合巨的元素利用知识r 既不能确定属于范畴i ， 也不能确定不属于范畴x ；集合最的元素必然属于范畴巧；集合岛的元素确定不 属于范畴x 。 范畴或集合的不精确性是因为存在边界域而产生的，如果它的边界域越大的 话，则它的精确性就会越低。为了进一步更精确地从量化角度描述这一点，可以 用集合的粗糙度概念和近似精度来表述这一点。 定义2 6对于论域u 及u 上的等价关系r ，栅u ，用等价关系r 表示的 论域u 子集x 的粗糙度和近似精度分别表示为 以x ) = l - o r r ( 跏州吩罱端。 精度( x ) 是指在知识r 下对子集x 表示的范畴程度了解。从上面公式可以 得出，对于知识r 和x u ，有o c r r ( x ) 1 。当( x ) = 1 时，子集x 的r - 边界 域是空集，因此子集x 是r 一精确集或r - 可定义的；当( x ) 1 时，该集合表示 含有非空的r 边界域，因此子集x 是r 精确集或r 不可定义的；当子集x 表示 空集时，则定义( x ) = ( o ) = 1 。而子集x 的r - 粗糙度与精度表示的意思相反， 它表示在知识r 下对子集x 表示的范畴不完全程度的了解。 现通过举例理解粗糙度和近似精度的概念，对于知识库k = ( u ，s ) 及知识库中 的等价关系r i n d ( k ) ，其得出的等价类如下所示：x = 五，j c 4 ，黾 ，k - - x ：，毛，x 7 ) ， e = 黾) ，k - - x 。) 。且论域u = 五，吻，毛) 。计算集合五= 五，_ ，毛 的r 一粗糙度 和近似精度。 按2 4 定义的上、下近似理论可得： 尽( 工) = a ，豆( x ) = xu e - - x , ，而，_ ，屯，而，黾 。 按定义2 6 能够得到： 集合五的r 一粗糙度风( x 。) = 1 一口。( x 。) = 1 0 = 1 ； 始五的r 酬精( 引= 粼= 詈一o o 由上面可以得出：集合咒是r 粗糙集且是不可定义的。 2 3知识约简 2 3 1知识约简 知识约简在处理数据和智能信息中有着非常显著的作用，同时是粗糙集理论 的重点内容。知识约简是指保持知识库分类能力没有变的情况下，删除冗余的知 识。 知识约简中有两个重要概念：核( c o r e ) 和约简( r e d u c t i o n ) 。 定义2 7 对于知识库k = ( u ，s ) 及其上的一个等价关系族pc _ s ，p ，如 果i n d ( p ) = i n d ( p - r ) ，那么称知识r 在p 中不重要，否则称r 在p 中是必需的。 若对于每一个r p ，r 都是p 中必需的，那么称p 是独立的，否则称p 为不独立的或 者依赖的。 定理2 1若知识p 为独立的，v g p ，那么g 必定同样是独立的。 定义2 8 对于知识库k = ( u ，s ) 及其上的一类等价关系p c _ s ，如果对于任意 的g p ，g 达到下面两点： ( 1 ) g 为独立的， ( 2 ) i n d ( p ) = i n d ( g ) 。 那么g 为p 中的一个约简，可以记作g r e d ( p ) ，而且尼仞( p ) 是指p 的所有约 简构成的集合。 从上面的概念可以得出，知识中一个任意的约简和关于知识的知识库中的任 何一个表达的范畴都是相同的，换句话说它们之间关于论域的分类能力一样。通 常情况下，知识的约简并不能够说只有一个，它是能够含有许多个约简。 定义2 9 对于知识库k = ( u ，s ) 及其上的一类等价关系p c _ s ，如果对于任意 的re p ，r 符合i n d ( p - r ) i n d ( p ) ，那么称r 在p 中是必要的，且p 的核表示为 p 中全体必要的知识构成的集合，简称c o r e ( p ) 。 注意：核是唯一性的。 约简和核的关系可以表示如下： 定理2 2 c o r e ( p ) = o r e d ( p ) 。 从上述定理可以看出，知识的核是由知识的全体约简的交集组成的，说明在 知识的每一个约简中都包括核，并且核是知识约简中必不可少的重要部分。 从定理2 2 还可以得出，核是知识约简最重要的部分，也就是说最能够表示知 识特点的那部分。核的范畴还有其它两方面的影响：一方面核是表示知识特性的 最关键部位，如果在知识约简求解的过程中被删除了，将会大大影响知识的分类 能力；另一方面核能够成为全体约简计算的基础，这是由于每一个约简都存在核 属性，因此能够进行直接的运算。 现在通过例子详细介绍核与知识约简求解的过程如下所示： 给定知识库k = ( u ，s ) 以及其上的论域u = x o ，x i ，x 2 ，x 8 ，并且s = r i ，r ，忍 ， i n d ( i r ) 对应的等价类以及等价关系r l r 2 ，r 3 如下所示： u 足= 五，x 4 ，) ， 恐，黾) ， 而 ， 讫，x 7 u le = 五，x 3 ，屯 ， 讫 ， 而，x 4 ，x 7 ，黾) u & = 五，屯) ， 吒) ， 恐，x 7 ，而 ， 屯，_ ) ) u i i n d ( s ) = x l ，屯) ， 屯，气 ， 屯) ， _ ， 氏 ， 为) ) 判断r l ，r 2 ，r 3 x q 圳i n d ( s ) 是否是必要的，且解i n d ( s ) 的所有约简与核。 由于 u 1 n d ( s 一 r t ) ) 2 最。 r li 【工】足 = x i , x 5 ) ，x ，x ， x ：石，x 。 ， z 。) ) u i n d ( s ) ， 因此，r l 在s 中是必要的。 由于 u i n d ( s 一 r z ) 2 州队 r = _ ，屯) ， x 。) ， ) ， 毛，黾 ， _ ， x ， ) = u i n d ( s ) ， 因此，r 2 在s 中是不必要的。 由于 u i n d ( s 一) 2 州 x 】r = u i n d ( s ) ， 因此，r 3 在s 中是小必要的。 下面求解s 的约简与核： 通过上面可以知道：c o r e ( s ) = r i ) 。 由于 u 州d ( 尺，r ：) 5 州) x 】再 = z 。，x ， ， x ： ， x 。 ， x ：，x 。 ， 工。 ， x ， = u i n d ( s ) 。 因此，u i n d ( r , ，r 2 ) ：z t & u r i ，表示墨在u i n d ( r , ，足 ) 中是必要的， u i n d ( r , ，r ) ) u 心，表示足在i n d ( r i ，r ) ) 中是必要的。显然，知识 r l ，r ) r l ，足，r 已经达到定义2 8 的条件，因此它是知识 r i ，r ，r ) 中的一个属 性约简。 由于 【，i n d ( r ，r ，) ) 2 置。q r , i x 】r = h x ，) ， x ， ， x 。) ， 黾) ，k ， x ，) = u i n d ( s ) ， 所以，u i n d ( r , ，b ) ) u r ，表示r 在z d ( r ，r ) 中是必要的， u i n d ( r 。，恐) ) u r ，表示r 在z d ( r ，r ) 中是必要的。所以可以得知知识 置，b 是独立的。显然，知识 墨，r s r l ，r ，恐 也达到了定义2 8 的条件，因此 它也是知识 r ，r ，r ) 中的一个属性约简。 通过上述可以知道，知识s = 蜀，r ，r 3 ) 分别有两个约简为 r i ，r 和 r 。，r ) ， 目3 个知识关于论域u 具有一样的分类能力，但通过知识约简表示的知识适用性很 强，比较简便，更容易让人理解。且可以通过验证： r lr ) n 墨，r 3 ) = r 。) ，即定 理2 2 成立。 2 3 2知识的依赖性 可以定义知识的依赖性如下： 定义2 1 0 给定一个知识库k = ( u ，s ) ，且v p ，q i n d ( k ) ，定义 7p ( q ) = 尼= 【，l u 表示知识o 依赖于知识p 的程度，将其记为p jt qo 上式中，p o s e ( q ) 2 z 酬uq ( x ) 表示知识o 的p 正域，它表示关于论域u 中所有依据分类信息u 尸能够正确的划 分到知识o 等价类中的相关对象集合。 由上面定义的知识依赖度程度可以知道，如果p j 。q ，那么通过q 导出的分 类信息u q 的正域包括了知识库中关于论域u 的kx 1 0 0 个元素。也就是说，论 域u 中k x l 0 0 个元素能够利用知识p 正确地划分到分类信息u q 的等价类中去。 知识依赖度的特性： ( 1 ) 0 斥( q ) = k 1 。 ( 2 ) 当厂p ( q ) = k = l 时，表示知识q 完全依赖于知识p ，或者表示知识q 是通过知 识p 导出的，可以记为尸j 。q 或p jq 。 ( 3 ) 当yp ( q ) = k = o 时，表示