（计算机应用技术专业论文）基于改进启发式遗传算法的属性约简方法.pdf

摘要 摘要 粗糙集理论是在上世纪八十年代由波兰数学家p a w l a k 提出的一种处理模糊和不确定 问题的数学理论。它能够分析出隐藏在数据中的事实，而且不需要提供任何关于数据的 附加信息。粗糙集理论已经在许多领域获得了成功的应用，例如知识发现、模式识别、 决策分析、机器学习等领域。 信息系统的属性约简是粗糙集理论的核心内容之一。寻找信息系统的最优约简或全 部约简是n p h a r d 问题，而基于属性重要性的启发式算法能够相对快速地计算出信息系 统的约简。 为了获得决策系统中属性的极小相对约简，本文将决策表中相对于每个条件属性的 集合和划分的粗糙逼近精度作为衡量属性重要程度的准则，并以此作为启发式信息引入 遗传算法，提出了一种在优化初始种群的基础上提高算法性能的启发式遗传算法。通过 构造一个修正算子并将其引入启发式信息，以保证被选择的属性子集的分类能力不变。 该算子利用启发式信息的局部搜索技术，使得算法既保持了整体的优化特性，又具有较 快的收敛速度。最后的实例证明，该算法能有效地对决策系统进行约简。 关键词：粗糙集逼近精度属性约简遗传算法 大连交通大学工学硕士学位论文 a b s t r a c t r o u g hs e tt h e o r y ，p r o p o s e db yp a w l a ki nt h ee a r l y19 8 0 s ，i sam a t h e m a t i c a lt h e o r yt o d e a l 诵t hv a g u ea n du n c e r t a i nk n o w l e d g e ，w h i c hc a na n a l y z et h er u l eh i d d e ni nt h ed a t a w i t h o u ta n ya d d i t i o n a li n f o r m a t i o n r o u g hs e tt h e o r yi su s e di nm a n yf i e l d ss u c ha s k n o w l e d g ed i s c o v e r y ，p a t t e r ni d e n t i f y i n g ，d e c i s i o na n a l y s i sa n dm a c h i n el e a r n i n g 1 1 l 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 o ns y s t e mi so n eo ft h em a i nt o p i c si nr o u g hs e t t h e o r y g e t t i n gt h eb e s tr e d u c t i o no ra l lr e d u c t i o ni st h en p - h a r dp r o b l e m h e u r i s t i ca l g o r i t h m b a s e do nt h ea t t r i b u t ei m p o r t a n c eh a db e e nm a d et og e tb e t t e rr e d u c t i o nq u i c k l y i nt h i sp a p e r ，w er e g a r dt h es i g n i f i c a n c eo fa t t r i b u t e sd e f i n e df r o mt h ea p p r o x i m a t i o n q u a l i t yw i t hr e s p e c tt ot h ep a r t i t i o na n dc o n d i t i o na t t r i b u t e ss e ta sh e u r i s t i ci n f o r m a t i o n ，a n d i n t r o d u c et h eh e u r i s t i ci n f o r m a t i o ni n t o g e n e t i ca l g o r i t h mb a s e do no p t i m i z i n g i n i t i a l p o p u l a t i o n an e wm o d i f yo p e r a t o ri su s e df o ri n t r o d u c i n gt h eh e u r i s t i ci n f o r m a t i o ns oa st o m a i n t a i nt h ea b i l i t yo fc l a s s i f i c a t i o no ft h ea t t r i b u t e ss e t t h eo p e r a t o ri sa ne m b o d i m e n to f l o c a lr e s e a r c hm e t h o du s i n gh e u r i s t i ci n f o r m a t i o n s ot h ea l g o r i t h mc o n v e r g e sq u i c k l ya n d h a sg l o b a lo p t i m i z i n ga b i l i t y t h ea l g o r i t h mi sa l s oa n a l y z e dt h e o r e t i c a l l ya n dt h ec o r r e c t n e s s a n de f f e c t i v e n e s so ft h ea l g o d t h ma r es h o w ni nt h ee x p e r i m e n t s k e yw o r d s ：r o u g hs e t ；a p p r o x i m a t i o nq u a l i t y ；a t t r i b u t er e d u c t i o n ；g e n e t i ca l g o d t h m ； 绪论 绪论 粗糙集理论的发展与特点 粗糙集( r o u g hs e t ，r s ) 理论是由波兰数学家p a w l a k 于1 9 8 2 年提出的分析不精确、不 确定数据的数学理论。该理论是经典集合论的又一推广形式，其主要思想是利用已知的 不完全信息或知识去近似刻画不精确或不确定的概念。或者依据观察、度量到的结果去 处理不分明的现象和问题。实践证明，这一理论对于处理不精确，不确定与不完全数据 是一种非常有效的方法，因此越来越受到国际学术界的广泛关注。 1 9 8 2 年，波兰华沙理工大学的数学家z p a w l a k 教授以关系理论为基本工具，推广传 统的集合理论，提出了粗糙集( r o u g hs e t ) 这一处理不精确、不确定与不完全数据的新 的数学理论n 1 。1 9 9 1 年，z p a w l a k 教授的第一本关于粗糙集专著和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用与相关方法比较研究的论文集的出版，推动了对粗糙集理论的深 入研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集学术讨论会，主要讨论了集合近 似定义的基本思想及其应用，其中粗糙集环境下的机器学习的基础研究是这次会议的四 个专题之一。1 9 9 3 年在加拿大b a f f 召开了第二届粗糙集和知识发现研讨会。这次会议的 主题是粗糙集、模糊集与知识发现。这次会议积极推动了国际上对粗糙集理论与应用的 研究。1 9 9 4 年在美国s a n j o s e 召开了第三届国际粗糙集与软计算研讨会，这次会议主要 探讨了粗糙集与模糊逻辑、神经网络、进化理论等的融合问题。1 9 9 5 年在美国w i l m i n g t o n 召开了粗糙集研讨会。粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯 上撰文，概况性地介绍了作为目前人工智能应用新技术之一的粗糙集理论的基本概念， 及其在知识获取、机器学习、决策分析和知识发现等领域的具体研究项目和进展。在1 9 9 5 年召开的第四届模糊理论与技术国际研讨会，主要针对粗糙集与模糊集之间的关系进行 了讨论，促进了粗糙集的发展。1 9 9 9 年在日本召开第七届粗糙集、模糊集、数据挖掘和 粒度一软计算国际会议庄要阐述了当前粗糙集、模糊集的研究现状和发展趋势。2 0 0 0 年 在加拿大召开了第二届粗糙集和计算的当前趋势学术会议。中国r o u g h 集与软计算研讨 会也成为公认的高水平学术交流会议。2 0 0 3 年5 月在重庆召开“第3 届中国r o u g h 集与软 计算学术研讨会 。当前许多重要的国际学术会议都把粗糙集理论的研究列入主要内容 专一跚 一一 o 与其它处理不确定性问题的数学理论相比，粗糙集理论具有以下主要特点口1 ： ( 1 ) 在分析数据过程中，由用户提供的数据是唯一的信息源。数据以外的任何额外的 参数假设是不需要的，即无需提供除所需处理的数据集合之外的任何先验信息。比如统 计学中的概率分布，模糊集理论中的隶属度，d e m p s t e r s h a f e 证据理论中的基本概率赋 大连交通大学工学硕士学位论文 值等，这些信息在很多情况下并不容易得到。 ( 2 ) 粗糙集理论将知识的粒度性作为己有知识不能确定表示某些概念的原因。它可以 表达和处理不确定的信息，在保留关键信息的前提下对数据进行化简并求得知识的最小 表达；能识别并评估数据之间的依赖关系；能从经验数据中获取易于证实的规则知识， 特别适用于智能控制。 ( 3 ) 基于粗糙集的数据分析的主要工具是存在于直接信息源数据项中的关系。这些关 系是一种隐含的信息，它们在数据分析过程中被揭示出来。粗糙集理论的这些特点决定 了它在不确定性数据分析方面有着不可替代的优越性。但是，由于这个理论不包含处理 不精确或不确定原始数据的机制，单纯地使用这个理论不一定能有效地描述和处理不精 确或不确定的实际问题，这意味着需要其它方法的补充。一般地说，由于证据理论h 3 和 模糊集理论砸3 具有处理不精确和不确定数据的方法，将它们与粗糙集理论构成互补是非 常自然的考虑。 粗糙集理论的研究现状 目前，对粗糙集理论的研究主要集中在：粗糙集模型的推广，问题的不确定性研究， 与其他处理不确定性、模糊性问题的数学理论的关系与互补，纯粹的数学理论方面的研 究，粗糙集的算法研究和人工智能及其他方向关系的研究等。这些研究有的是纯理论方 面的探索，有的是受应用推动而产生砸1 。p m v l a k 粗糙集模型的推广一直是粗糙集理论研 究的主要方向，目前主要有构造性方法和( 代数) 公理化方法；粗糙集理论中有效算法 的研究主要集中在：导出规则的增量式算法、约简的启发式算法、粗糙集基本并行算法 以及与粗糙集有关的神经网络与遗传算法等。 信息系统的约简是粗糙集理论的核心内容之一口，是粗糙集理论研究的重要方向。 信息系统的约简包括属性约简和属性值约简两种。 信息系统中的属性并不是同等重要的，有些属性是绝对不必要的，去掉这种属性并不 影响信息系统的分类能力，而有些属性是绝对必要的，去掉这种属性必然会影响系统的 分类能力，有些属性是相对必要的，这种属性同其它属性联合起来，可以保持信息系统 的分类能力，但是也存在着不需要这种属性而保持信息系统分类能力的属性子集。属性 约简就是要寻找保持信息系统分类能力的最小属性子集。属性约简可以使信息系统的知 识表示更加简洁，使隐藏在数据表中的知识更加清晰，使决策表的规则集的推广能力更 强，适应性更好。属性约简去掉了决策表的冗余属性，但是还没有充分去掉决策表的冗 余信息，也就是说经过属性约简得到一个规则集，这个规则集中的规则不一定都是最优 的规则，通过属性值约简后可以使规则集中的每个规则是最优的。经过属性约简和属性 值约简后，可以得到决策表的一个规则集，这个规则集中的规则仍有可能是多余的，应 2 绪论 该进一步约去这些多余的规则，得到一个极小规则集。 粗糙集理论的应用 粗糙集理论是- - f - 实用性很强的学科，由于其在数据挖掘方面的应用而受到广泛的 关注，最近几年，粗糙集理论的应用研究得到了广泛的发展，在不少领域取得了丰硕的 成果。下面简单介绍粗糙集应用的几个主要领域嘎m j ： 数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 幻。知识发现就是从 大量数据中发现潜在规律、提取有用知识的方法和技术。知识发现不但能够学习已有的 知识，还能够发现未知的知识，得到的知识是“显式 的，既能为人所理解，又便于存 储和应用，因此一出现就得到广泛的重视。粗糙集和k d d 关系密切，为k d d 提供了一种新 的方法和工具。粗糙集可支持k d d 的多个步骤，如数据预处理、数据约简、规则生成等。 k d d 研究的实施对象多为关系型数据库，关系表可被看作粗糙集理论中的决策表，这给 粗糙集方法的应用带来极大的方便。现实世界中的规则有确定性的，也有不确定性的。 从数据库中发现不确定性的知识，为粗糙集方法提供了用武之地。从数据中发现异常， 排除知识发现过程中的噪声干扰也是粗糙集方法的特长。运用粗糙集方法得到的知识发 现算法有利于并行执行，这可极大地提高发现效率。 决策支持。决策支持系统是一组协作指定决策的工具，其重要特征就是能够执行规 则并进行判断分析。粗糙集理论能够在大量经验数据的基础上找到这些规则，而且基于 粗糙集理论的决策支持系统弥补了常规决策方法的不足：它允许决策对象存在一些不太 明确、不太完整的属性，并经过推理得到基本肯定的结论。 人工神经网络训练的样本约简。利用粗糙集理论对神经网络训练的样本进行预处理， 可以删除训练样本中的冗余和无用信息，使训练样本得以简化，提高神经网络的训练数 据效率。特别是，通过粗糙集理论的属性约简，可以删除训练样本中多余的属性，减少 神经网络输入层节点的个数，使神经网络的拓扑结构得以简化。 本文的主要内容与章节安排 本文主要研究粗糙集理论的核心问题之一属性约简方法。前人工作的基础上，将粗 糙逼近精度作为启发式信息引入了启发式遗传算法，在初始种群设置中添加了属性核设 置，提高了算法的收敛速度，提出了一种基于改进启发式遗传算法的属性约简方法，并 在实例中验证了该算法的有效性。 本文的组织结构安排如下： 绪论：介绍了粗糙集理论的基本特点方法，粗糙集理论的发展和研究现状以及粗糙集 理论的应用领域等。 第一章：介绍了粗糙集理论中的基本概念与基本理论，粗糙集理论模型的扩展，以及 3 大连交通大学工学硕士学位论文 粗糙集与其他处理不确定性问题方法的联系，是本文的理论基础。 第二章：介绍了知识与知识库，信息系统和决策表及属性约简的概念，着重研究了目 前流行的各种属性约简的算法。 第三章：介绍了遗传算法的基本理论及基本遗传算法的思想。 第四章：在前人研究的基础上提出一种基于改进启发式遗传算法的属性约简方法， 并给出算法的理论分析及实例应用。 结论：本文的总结，概要介绍了本文的主要内容和创新点，指出了本文的一些不足之 处与一些应该值得继续研究的方向。 4 第一章粗糙集理论 第一章粗糙集理论 粗糙集理论为人们提供了一种描述不确定事物的数学语言，使人们可以采用不同的 精度来分析数据。本章介绍粗糙集理论的一些基本概念。粗糙集理论是建立在分类机制 的基础上的，它将分类理解为特定空间上的等价关系，而等价关系构成了该空间的划分。 粗糙集理论将知识理解为对数据的划分，每一个被划分的集合称为概念。 1 1 集合与等价关系 集合是数学中的一个原始概念。例如，某学校图书馆中的书构成一个集合，一个教 室里的学生构成一个集合，全体自然数构成一个集合等等。所谓集合( 或简称集) 是指 具有某种特定性质的事物的总体。 集合可以用一个大写字母表示。组成这个集合的事物称为集合的元素。集合中的元 素可以用小写字母表示。元素a 是集合a 的元素表示为a e a ，元素口不是集合彳的元素 表示为口彳。 集合可以用将组成集合的所有元素用大括号括起来的方法表示。例如： a = 岛6 ，c ，b = 红，绿，兰 。当集合的元素可以有序安排时，在大括号内也可以把所有元 素都罗列出来，例如：a = l ，2 ，1 0 0 。 集合也可以用其元素的性质加以描述，或者定义一个变量，表示集合的任一元素， 并对其性质加以描述。例如：a = 大连交通大学的所有学生) ，b = x l 工= 2 k n + l ，k 为任意整数) 。 集合的元素可以是集合，此时称为集和族，常用黑体大写字母表示。例 如：a = l ，2 ，3 ，b = 4 ，5 ，c = 6 ) ，p = 彳，b ，c ，p 是集合族，a ，b , c 是集合，也是p 的元素。 根据集合中元素的情况，没有元素的集合称为空集，空集可以用f 2 j 表示，例如： a = 大于1 且小于2 的整数 。包括了在给定问题中所有要考虑的全部可能元素的集合称为全 集，也称论域，记为u 。 定义1 1 1 若把一个集合a 分成若干个叫做分块的非空子集，使得a 中每个元素至 少属于一个分块，那么这些分块的全体构成的集合叫做a 的一个覆盖。如果a 中每个元 素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做a 的一个划分( 或分划) 。 例如：a - l , 2 ，3 ，4 ，5 ，6 ) ，s i = 1 ) ，岛= 2 ，3 ，4 ，s ，= 5 ，6 ，因s lu s 2u s 3 = a 且s i n s 2ns 3 = f 2 j ， 故s 。，s ：，s 3 是a 的一个划分。 定义1 1 2 两个具有固定次序的元素组成一个序偶，用以表达两个元素之间的关 系。记为 。 5 大连交通大学工学硕士学位论文 序偶可以看作是具有两个元素的集合。它与一般集合不同的是序偶具有确定的次序。 在集合中 a ，b = b ，a ) ，但对于序偶 。两个序偶相等， 。 下近似、上近似也可以用下面的等式来表示： 星( x ) = x u i 【x 】r x ) ， ( 1 2 ) r ( x ) = x ul 【x 】rn x 9 ) 。 p a w l a k 在提出粗糙集理论时，同时给出了上近似集、下近似集之间的1 2 条代数性质 【1 3 】 ( 1 )凰x ) 互x s 烈x ) ( 2 )凰回= _ ( 回= a ，星( = - ( u ) = u ( 3 )r ( x u d = r ( x ) u 页( y ) ( 4 )g ( x n n = r ( x ) n 凰y ) ( 5 ) x y = ，星( x ) 星( 1 ，) ( 6 ) x 互y j - ( x ) - ( j ，) ( 7 )熨x u y ) 星( 幻u 烈y ) ( 8 )葡x n d - ( x ) n 页( y ) ( 9 ) 星( ) = - ( x ) ( 1 0 )_ ( _ ) = 豆两 ( 1 1 ) 凰星( x ) ) = 尺哩( x ) ) = 型x ) ( 1 2 )凰- ( x ) ) = 页( - ( x ) ) = j i ( x ) 7 大连交通大学工学硕士学位论文 同时，定义p o s r ( x ) = 垦( x ) 为x 的r 正域；e 嗥( x ) = u r ( x ) 为x 的r 负域； 刷( x ) = r ( x ) 一墨( x ) 为x 的灭边界域。直观的讲：x 的r 正域是根据知识r 判断肯 定属于x 的那些对象构成的集合；x 的尺上近似集是根据知识r 有可能属于x 的对象 构成的集合；x 的r 边界域是根据知识r 不能确定是否属于x 的对象构成的集合；x 的r 负域是根据知识尺判断肯定不属于x 的那些对象构成的集合。集合的不确定性是由 于边界域的存在而引起的，集合的边界域越大其精确性越低，为更准确地表达这一点， 引入了精度的概念。对于由等价关系r 定义的近似精度为： 靠( x ) ：c a r d ( r _ ( x ) ) ( 1 3 ) c a r a ( r ( x ) ) 式中，c a r d ( x ) 表示集合的元素的数目，称为集合的基数或势，c a r d ( r _ ( 彳”也可以表达 为i 戡x ) i 。显然0 靠( x ) 1 ，如果d r ( x ) = 1 ，则称集合x 相对于r 是清晰的； 哝( x ) 1 ，则称集合x 相对于尺是粗糙的。畋( x ) 可以认为是在等价关系r 下逼近集合 x 的精度。 根据集合x 的上、下近似集的特征，对集合x 的不确定程度可以作如下定义： 定义1 2 2 星( ，- ( x ) 是集合x s u 关于等价关系r 的下近似集和上近似集，若 星( x ) - ( x ) ，即x 是不可定义集，则： 如果烈x ) f 2 j 且- ( x ) u ，称x 为r 粗糙可定义的； 如果烈x ) = f 2 j 且- ( x ) u ，称x 为r 内不可定义的； 如果凰x ) f 2 j 且- ( x ) = 【，称x 为r 外不可定义的； 如果亘x ) = a 且( x ) = u ，称x 为r 全不可定义的； 对于上述定义，可以作如下的直观理解： 当集合虽x ) = - ( x ) 时，集合x 的边界为空，根据r 可以完全肯定地判定任意元素是 否属于集合x ，即集合彳是确定的；若集合x 的边界不为空，根据r 则有部分元素不能 被确定地判定是否属于x 。如果x 是r 粗糙可定义的，则可以确定u 中的部分元素是否 属于x 或口彳；如果x 是r 内不可定义的，则可以确定u 中的部分元素是否属于口x ， 但不能确定u 中任何元素是否属于x ；如果x 是r 外不可定义的，则可以确定u 中的部 分元素是否属于工，但不能确定u 中任何元素是否属于口x ；如果x 是r 全不可定义的， 则不能确定u 中任何元素是否属于x 或口z 。 1 3 粗糙集模型的扩展 经典粗糙集理论是建立在严格的等价关系之上的，然而经典粗糙集理论依然存在以 8 第一章粗糙集理论 下几个主要的不足，使其在实际应用中并不能处理所有的不精确及不确定性问题。 ( 1 ) 对原始数据本身的模糊性缺乏相应的处理能力。 ( 2 ) 对于粗糙集的边界区的刻画过于简单。 ( 3 ) 粗糙集理论的方法在可用信息不完全的情况下将对象归类于某一具体的类，通 常分类是确定的，但并未提供数理统计中所常用的在一个给定错误率的条件下 尽可能将多的对象进行分类的方法。 因此，许多学者对经典粗糙集的理论模型进行了更深入的研究和扩充，提出了一些 扩展的粗糙集模型来处理不同的实际问题。其中具有代表性及应用广泛的有可变精度模 型、相容关系模型、概率粗糙集模型和模糊粗糙集模型等。下面对各扩展的粗糙集模型 做一个简略的介绍。 1 3 1 可变精度模型 在p a w l a k 提出的经典粗糙集理论中，是用精确集包含来定义上近似集和下近似集的， 在实际应用中，这种方式缺乏对噪音数据的适应能力。然而，现实处理的数据中含有噪 音是在所难免的。基于这个考虑，z i a r k o 提出了一种称之为可变精度粗糙集( v a r i a b l e p r e c i s i o nr o u g hs e t ，v p r s ) 模型n 们。该模型通过引入一个精度，因而具有一定的容错 性，给出了错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界区域和 负区域，讨论了此定义下的有关性质。 v p r s 中定义了集合x 归类于集合】，的误分类度c ( x ，y ) ： c ( x ，n = f 帮愀 ( 1 4 ) ，d = t o ，眯r。高= o ( 1 4 ) 显然当c ( x ，y ) = o 时有x y ，当c ( x ，y ) 0 时，即有c ( x ， ，) x 1 0 0 的元素归类错误。 可提前定义一个错误分类率p ( os 卢 o 5 ) 。 设u 为论域，r 为u 上的等价关系，u r = x ，k ，匕 。给定u 上的集合x ，定义其一 下近似及一上近似为： 星口( x ) = i y e u r ，c ( l x ) ) ( 1 5 ) r p ( x ) = y i y u r ，c ( x ，y ) l - p 集合x 的卢一边界区域定义为： b n r b ( x ) = y i y e u r ，f l c ( x ，功 l - f l ( 1 6 ) 当p = o 时，v p r s 模型就蜕化为经典粗糙集模型，即经典粗糙集是v p r s 的一个特例。 可变精度粗糙集模型是经典粗糙集模型的直接扩展，它完全继承了经典粗糙集的性质， 9 大连交通大学工学硕士学位论文 拥有经典粗糙集的所有优点，并且它还拓广了经典粗糙集理论的应用范围 1 3 2 相容关系模型 在通过实际测量得到的数据库中，某个对象的个别或部分属性缺失现象十分普遍， 而经典粗糙集是处理不了这种情况的。因此许多学者基于容差关系对经典粗糙集进行了 扩充，即用容差关系代替等价关系作为粗糙集的划分基础。 给定信息系统s = 缈，a ，v ，力，对于具有缺失属性值的属性子集b c _ a ，记缺失属性为 “，i c ，引入容差关系丁： 定义1 3 1 容差关系丁定义为： 丁= ( x ，y ) i x u a y u ( v 口b ，口( x ) = 口( y ) v 口( 功= 木r a c y ) = 幸) ) ( 1 7 ) 从定义中可以直观的看出丁满足自反和对称关系，但不一定满足传递关系。对应经 典粗糙集中等价类概念定义容差类为： 定义1 3 2 元素j 的容差类厶( 工) 表示在属性集合b 上满足关系t ( x ，y ) 的元素y 的集 合： 厶o ) = y i y e u ，( x ，少) n ( 1 8 ) 根据容差类的定义，可以定义不完备信息系统中集合x 关于属性集合b 的上、下近 似集。 定义1 3 3 对于不完备信息系统s = 缈，a ，力，集合x 关于属性集b 在容差关系r 上的上近似集荒、下近似集定义为： 笸；= 缸w l ，日( 功x ( 1 9 ) 弼= 缸u i ，曰( x ) c t x 0 1 3 3 概率粗糙集模型 设u 为有限元素构成的论域，r 是u 上的等价关系，其构成的等价类为 u r - - - - x i ，五，以 。记工所在的等价类为【x 】，令p 为定义在u 的子集类构成的盯代数上 的概率测度，三元组彳，= ，r ，p ) 称为概率近似空间。u 中的每个子集称为概念，它代表 了一个随机事件。p ( xy ) 表示事件】，发生下x 出现的条件概率，也可解释为随机选择的 对象在概念y 的描述下属于的x 概率。 设o p a f l x 关于彳。= ( 【，r ，户) 依参数口，的概率正域，边界域和负域分别为 p o s ( x ，口，f 1 ) = p _ l x ( x ) = 红u i p ( x l b 】) 口) b n ( x ，口，f 1 ) = x u i ，c = q ，a 2 。a 3 。a 4 ，d = d ，。 1 4 第二章信息系统及其属性约简 表2 1 一个决策表的实例 t a b l e2 1a ne x a m p l eo fd e c is i o nt a b l e u q 口2口3口4 d 五 11321 而 21211 黾 1l3 2 l 黾 12212 屯 l2212 毛 121l3 而 12212 黾 12113 2 3 信息系统的属性约简概念 目前数据库和信息系统中信息膨胀主要有两个方向：横向和纵向。横向指的是属性字 段的不断增加，纵向指的是记录数的增加。在粗糙集中对于信息系统横向的约简可以称 之为属性约简，纵向的约简可以认为是值约简。随着数据库系统中数据的不断增加，属 性的约简相对于值的约简变得更加有效。如果在知识获取之前能减少大量包含较少或几 乎不包含什么信息的冗余属性，将大大简化数据库结构的复杂度，提高人们对隐含在数 据库庞大数据量下的各种信息的认识程度，因此属性约简也就成为了目前粗糙集的研究 热点之一。 2 3 1 约简与核 约简和核是粗糙集理论中的两个基本概念。约简是一个决策系统的基本部分，核是 所有约简的公共部分，完成知识约简的基本工作是利用这两个基本概念来进行。 定义2 3 1 设r 是定义在论域u 上的一个等价关系族，如果存在，r 且 1 n d ( r 一 r ) ) = 肋( 固，则称关系，在r 中是绝对不必要的：否则称，在r 中是绝对必要的。 绝对不必要的关系在知识库中是多余的，如果将它们从知识库中去掉，不会改变该 知识库的分类能力。相反，若知识库中去掉一个绝对必要的关系，则一定会改变知识库 的分类能力。 定义2 3 2 设r 为定义在论域u 上的一个等价关系族，如果每个关系，r 在r 中都 1 5 大连交通大学工学硕士学位论文 是绝对必要的，则称关系族r 是独立的；否则，称r 是相互依赖的。 对于相互依赖的关系族来说，其中包含有冗余关系，可以对其约简：而对于独立的 关系族，去掉其中任何一个关系都将破坏知识库的分类能力。 定义2 3 3 设r 为定义在论域u 上的一个等价关系族，r 中所有绝对必要关系组成 的集合称为关系族r 的绝对核，记作c 锨e ( r ) 。 定义2 3 4 设u 是一个论域，尸和q 是定义在u 上的两个等价关系族，且q c _ p ， 如果： ( 1 ) i n d ( q ) = i n d ( p ) ( 2 ) q 是独立的 则称q 是尸的一个绝对约简。 如果知识q 是知识p 的绝对约简，那么，u 中通过知识p 可区分的对象，同样可以 用知识q 来区分。 “约简 和“核 这两个概念很重要，是粗糙集方法的精华。粗糙集理论提供了搜 索约简和核的方法。计算约简的复杂性随着决策表的增大呈指数增长，这是一个典型的 n p 完全问题，当然实际中没有必要求出所有的约简。因此引入启发式的搜索方法既有助 于找到较优的约简又可以大大减少时间复杂度。 2 3 2 相对约简与相对核 在应用中，一个分类相对于另一个分类的关系十分重要，因此介绍知识的相对简化 和相对核的概念。 定义2 3 5 设p 和q 为定义在论域u 上的两个等价关系族，q 的p 正域记为 p o s a q ) ，定义为p o s e ( q ) = u2 似) 。 x g u i q 定义2 3 6 设p 和q 为定义在论域u 上的两个等价关系族，若存在r e p 使得 p o s , ( q ) = p o s _ ( 叫，j ) ( q ) ，则称，为p 中相对于q 可省略的( 不必要的) ，简称尸中q 可省略的； 否则，称，为p 中相对于q 不可省略的( 必要的) 。 定义2 3 7 设尸和q 为定义在论域u 上的两个等价关系族，若尸中的每一个，都是 尸中q 不可省略的，则称p 为( 相对于) q 独立的。 定义2 3 8 设p 和q 为定义在论域u 上的两个等价关系族，若p 的q 独立子集 s c p 有p o s s ( q ) = p o s e ( q ) 则称s 为p 的q 约简。 可以记p 的所有q 约简关系族为r e d a ( p ) 。 1 6 第二章信息系统及其属性约简 定义2