（计算机应用技术专业论文）基于粗糙集理论属性约简的研究与应用.pdf

摘要 基于粗糙集理论属性约简的研究与应用 专业：计算机应用技术 硕士生：王翔飞 导师：须文波 摘要 属性约简是粗糙集理论研究的重要内容之一。它是在保持信息系统分类能 力不变的情况下，删除其中不重要的和冗余的那些属性，同时提取出信息系统 的重要信息。 论文在经典粗糙集理论基础上，定义了一个相容样本集的概念，并证明相 对正域和相容样本集之间的等价关系，以此给出了约简过程中属性集和原信息 表是否具有相同分类能力的判定定理；同时根据边界域定义了条件属性的重要 性，进而给出了一种属性约简的计算方法。该方法包括相容样本集的计算，属 性核的求取和属性的约简。在属性核的计算中，给出了判断属性是否为核属性 的判定定理；在属性约简中给出了判定属性约简的定理。分析表明该方法在属 性核的计算上获得了较低的时间复杂度；由于引入了相容样本集的概念，使得 该约简方法不仅适用于相容的信息系统，还可用于不相容的信息系统。通过仿 真实验和应用表明，该方法取得了较为满意的约简结果，能有效应用于决策判 断。 最后为了粗糙集理论能更好的适用于不完备系统，对目前粗糙集理论模型 进行了扩充。建立了一种k 等价度容差关系下的粗糙集模型。通过性能分析说 明该模型具有很好的灵活性，得到的结果也更加符合实际情况。为下一步在不 完备系统上的属性约简及规则提取打下了基础。 关键字：粗糙集，属性约简，属性核，相容样本集，不完备信息系统 江南大学硕士学位论文 r e s e a r c ha n d a p p l i c a t i o no f a t t r i b u t er e d u c t i o nb a s e d o n r o u g h s e tt h e o r y m a j o r ：c o m p u t e ra p p l i e dt e c h n i q u e g r a d u a t es t u d e n t ：w a n gx i a n g f e i t u t o r ：x uw e n b o a b s t r a c t a t t r i b u t er e d u c t i o ni so n eo fi m p o r t a n tq u e s t i o ni nr o u g hs e t i tc a ne l i m i n a t e u n i m p o r t a n ta n dr e d u n d a n c i e sa t t r i b u t eo fi n f o r m a t i o ns y s t e m s i nt h ep a p e r , t h ec o n s i s t e n t s a m p l es e tw a sd e f i n e d ，t h ee q u i v a l e n c er e l a t i o n b e t w e e nt h ec o n s i s t e n ts a m p l es e ta n dr e l a t i v ep o s i t i v er e g i o i li sp r o v e n ，a n dt h e a t t r i b u t es i g n i f i c a n c ew a sd e f i n e db a s e do nb o u n d a r yn g i o n m o r e o v e r , ae f f e e t i v e m e t h o do fa t t r i b u t er e d u c t i o ni sp r e s e n t e d t h em a i np r o c e s si st oc a l c u l a t ec o n s i s t e n t s a m p l es e t e x t r a c tc o n d i t i o nr e l a t i r e a t t r i b u t ec o r e c a l c u l a t er e l a t i v ea t t r i b u t e r e d u c t i o ns e t i nt h ea t t r i b u t ec o r ec a l c u l a t i o np a r t ，at h e o r e mo fe s t i m a t ec o r e a t t r i b u t ei sg i y e n 。i nt h ea t t r i b u t er e d u c t i o np a r t at h e o r e mo fe q u i v a l e n c eb e t w e e n r e d u c t i o ns e ta n dc o n s i s t e n ts a m p l es e ti sg i v e n 7 矗c a n a l y s i si n d i c a t e dt h a tt h e a l g o r i t h mo fc a l c u l a t ea t t r i b u t ec o l eh a sl o wt i m ec o m p l e x i t i e s ；t h em e t h o do f a t t r i b u t er e d u c t i o na p p l e st oc o n s i s t e n ti n f o r m a t i o ns v s t e ma n di n c o n s i a t e n t i n f o r m a t i o ns y s t e m t 1 1 ee m l u a t o rr e s u l ts h o wt h a tt h ev a l i d i t yo ft h ea l g o r i t h mw e r e d e m o n s t r a t e d l a s t l y , i no r d e rt or o u g hs e tt h e o r yc 姐a p p l i e st oi n c o m p l e t es y s t e m an e w m o d e lb a s eo nk e q u i v a l e n tt o l e r a n c er e l a t i o ni sp r e s e n t e d t h em o d e lh a sg o o d f l e x i b l e n e s sb yp e r f o r m a n c ea n a l y s i s k e y w o r d s l ：r o u g hs e t ，a t t r i b u t i o nr e d u c t i o n ，a t t r i b u t i o nc o r e ，c o n s i s t e n t s a m p l es e t ，i n c o m p l e t ei n f o r m a t i o ns y s t e m s n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：赵。塑! 蔓导师签名：f 至兰! 坠 日期：砌7 年弓月，j 咱 第一章绪论 第一章绪论 1 1 粗糙集理论的发展和现状 粗糙集( r o u g hs e t s ) 理论是一种研究不精确，不确定性知识的数学工具【1 1 。由 波兰华沙理工大学教授z p a w l a k ：e 1 9 8 2 年首先提出的，借鉴了逻辑学和哲学中不 精确、模糊的各种定义，针对知识库，提出不精确范畴等概念，并在此基础上逐渐形 成了完整的粗糙集理论体系。 粗糙集理论在1 9 8 2 年被提出，当时关于这方面的研究主要集中在波兰。直到 1 9 9 0 年，该理论在决策与分析、模式识别、机器学习与知识发现等方面得到成功 应用，才逐步引起世界各国学术研究者的关注。之后很多学者都积极关注和热心 研究，使其理论发展和应用方面都取得了很大进步。1 9 9 1 年z p a w l a k 出版了l b u g h 集理论的专著( r o u g hs e t 铲1 【1 l e o r e t i c a la s p e c t s o fr e a s o n i n ga b o u td a t a ) ，这 为以后的进一步研究奠定了理论基础；1 9 9 2 年在波兰召开了第一届粗糙集理论国 际学术会议；1 9 9 5 年z p a w l a k 又进一步介绍了r o u 曲集理论和研究进展；同年 a c mc o m m u n i c a t i o n 将粗糙集列为计算机科学研究课题。我国对于粗糙集理论的 研究虽然较晚，但发展迅速，取得了丰富的成果。2 0 0 1 年“第一届中国粗糙集与 软计算学术研讨会”在重庆邮电大学举办；2 0 0 3 年中国人工智能学会粗糙集与软 计算专业委员会成立，其中吸引了国内很多高校和科研机构的科研人员；目前国 内学者从事粗糙集研究的人员越来越多，已形成了一支较为稳定的学术队伍，中 国学者在这一领域的影响也越来越大，正在逐步成为在这一领域的重要科研力量 i t 6 。 粗糙集作为一种处理信息的数学方法，无需任何先验信息，只通过发现数据 间隐藏的关系，揭示潜在的规律，从而提取有用信息。粗糙集理论的有效性在数 据挖掘、机器学习、智能控制、模式识别、故障诊断等方面得到大量应用和证实 i 硎。粗糙集理论已成为信息科学最为活跃的研究领域之一。 在粗糙集中，属性核的计算，属性的约简，决策规则的产生，和不完备信 息系统的理论模型扩充都是目前研究的热点。对于属性核的计算目前主要是通 过区分矩阵( d i s c c m i b i l i t ym a t r i x ) 【冽来求出的。区分矩阵是s k o w r o n 教授提出的 一种知识表达形式。使用区分矩阵容易计算出属性核。但区分矩阵计算属性核 的方法只适合于相容的信息系统【剐，利用信息熵可以解决不相容系统属性核的 求解1 9 】。然而这些算法普遍存在计算复杂度高的问题，当论域的对象规模较大 时，利用区分矩阵需要占用大量的存储空间。对于属性约简主要是在求出属性 江南大学硕士学位论文 核的基础上，逐步加入重要性强的属性而扩展得到约简结果的。由于属性的重 要程度不同，如何选取合适的属性就成为研究问题。主要有利用属性依赖度定 义重要性i x 0 作为启发式信息建立的约简方法；利用信息熵【1 1 】【1 2 】定义重要性建立 的约简方法；利用属性在决策矩阵出现的概率1 1 3 】作为启发式信息建立的约简方 法；利用近似精度定义属性重要性而建立的约简方法【1 4 1 。这些方法仍存在一些 不完善的地方，采用属性重要性的算法并不能一定能找到信息表的最优解，因 此对于属性重要性的定义也有待研究改进。在对于不完备系统的模型扩充方面， 目前已有r o u g h 集模型主要有：k r y s z k i e wi c z l 硼提出的基于容差关系的r o u g h 集模型，s t e f a n o ws k i 2 1 】提出的基于非对称相似关系下的r o u g h 集模型，王国 胤1 2 2 提出的基于限制容差关系下的r o u g h 集模型。容差关系模型的条件太过宽 松，会导致没有确定已知属性值相等的两个对象分在同一个类中；相似关系模 型的条件太过苛刻，存在一些有很多已知属性相等的两对象被划分在不同类中； 限制容差关系模型虽然对以上模型做了改进，但也存在某些问题，对于只存在 一个相同的属性值的两个对象会被分在同一个类中，这与实际是不相符的，所 以进一步完善不完备系统下的理论模型也是今后研究的方向。 1 2 主要工作内容 论文主要工作有两个，一是属性约简算法的改进；二是粗糙集在不完备信 息系统中的理论模型扩充。 在目前粗糙集理论的基础上，给出一些新的概念和定理。首先定义了一个 概念一相容样本集，然后证明了属性约简的相关判定定理，即相对正域和相容 样本集间存在等价的关系，并以此给出一种新的属性约简方法。 经典粗糙集理论只能用于完备的信息系统，并不适合不完备信息系统( 即系 统中存在空值1 。为此，本文进行了粗糙集理论模型扩充。给出一种新的模型一 七等价度容差关系下的粗糙集模型。 2 第二章粗糙集理论基本概念 第二章粗糙集理论基本概念 2 1 知识与不可区分关系 经典逻辑中，只有真假之分，但在现实生活中有许多含糊现象并不能简单 地用真、假来表示。粗糙集是一种新的处理模糊和不确定知识的数学工具，它 把无法确认的个体都归于边界区域，而这种边界区域被定义为上近似集和下近 似集。其主要思想就是在保持分类能力不变的情况下，通过知识约简，导出问 题的决策或分类规则。 粗糙集认为知识就是人类和其他物种所固有的分类能力，知识的粒度性是 造成使用已有知识不能精确地表示某些概念的原因。粗糙集通过引入不可区分 关系作为其理论基础，并以此基础上定义上近似集，下近似集概念。下近似集 中的每一个成员都是该集合的确定成员，而上近似集中的每个成员可能是该集 合的成员。 设u = ( x l 渤函) 为非空有限集为论域，对于每个子集x c _ u 称为论域u 中的一个概念或范畴。u 中的任何概念族称为关于论域u 的知识( 或属性) 。 设r 是u 上的等价关系，u r 表示r 的所有等价类构成的集合，【x 】r 表示 包含元素x e u 的r 等价类。若p 量r 且毋，那么n p ( p 中所有等价关系的 交集) 也是一个等价关系，称为p 上的不可区分( i n d i s c e m i b i l i t y ) 关系，记为i n d ( p ) 。 等价关系i n d ( p ) 的所有等价类u i n d ( p ) 表示与等价关系p 相关的知识( 属性) 。 i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。为简便使用，我们用p 来代 替i n d ( p ) ，u p 代替u i n d ( p ) 1 6 1 。 一个知识系统描述为：s = ( u ，v f r ) ，其中，论域u = ( x l ，x 2 函) 为非空有 限集，v 是属性项r e r 的值域，f 是u r 到v 的一个映射，即：f ：u r v r 为u 上的等价关系。i n d ( s ) 定义为s 中所有等价关系的族，记作i n d c s ) - - r o d ( p ) i 妒；e p c r 。知识系统也称为信息系统。为了方便知识系统可简记为s = ( u ，r ) 。 对于一个知识系统s = ( u ，、f ，r ) ，p _ r ，不可区分关系可用如下表示： i n d ( p ) = ( x ，y ) e u uivp e p , f ( x ，a ) = f ( y ，a ) ) 如果( x ，y ) e i n d ( p ) ，则称x 和y 是不可区分的。符号u i n d ( p ) 表示不可区分 关系i n d ( p ) 在u 上导出的分类，可简记为u p 。【x 】p 表示包含x 的p 等价类。 通常知识系统的数据以关系表的形式表示。关系表的行对应研究对象，表 3 江南大学硕士学位论文 的列对应对象的属性，对象的信息通过指定对象的各属性值来表达。 对于两个知识系统s = ( u ，p ) 和g = ( u ，q ) ，若砌( p ) c i n d ( o ) ，称知识p 比知 识q 更精细，或者说q 比p 更租糙。 2 2 上、下近似集 r o u g h 集理论中的不确定性是一种基于边界的概念，即一个集合在某特定 的知识下有不确定的边界，相对于某一个特定的知识而言，每一个集合由上近 似和下近似的精确概念来表示。 设x _ u 是任一子集，r 为u 上的等价关系。当x 能表达成某些r 基本范 畴的并时，称x 是可定义的；否则称x 为r 不可定义的。r 可定义集是u 的 子集，称为可定义集；而r 不可定义集称为非精确集或r 粗糙集。 为了可以定义粗糙集，这里使用两个精确集，即上近似集( u p p e r a p p r o x i m a t i o n ) 、下近似集( 1 0 w e fa p p m x i m a t i o n ) 来描述粗糙集【1 6 1 。 s = ( u ，v f ，r ) 为一个信息系统，对于子集x _ c u 定义上、下近似集： r x = x e u i 【x r nx 妒 r x = x e ui 【x xc x ) 上、下近似集也可用下面的等式来表示： r x = u y u riy n x 妒 星x = u y e u r iy x 集合b n r ( ) 0 = r x 一墨x 称为x 的r 边界域；p o s r g 日= 星x 称为x 的r 正域； n e 甑( x ) = u - - rx 称为x 的r 负域。显然：rx = p o s r ( x ) o b n r ( x ) 。 p o s x ( x ) 或墨x 是根据知识r 判断肯定属于子集x 的元素组成的集合；r x 是根据知识r 判断可能属于x 的u 中元素组成的集合；b n x ( x ) 是根据知识r 无法判断是否属于x 的元素组成的集合；n e g x ( x ) 是根据知识r 判断肯定不属 于x 的u 中元素组成的集合。 若x 是可定义的当且仅当r x ：i x ；x 是不可定义的当且仅当r x i x ， 这时x 是r o u g h 集。 由r 上近似集和下近似集可得到下面的性质1 1 6 1 ： 4 第二章粗糙集理论基本概念 ( 1 ) 垦x x r x ( 2 ) 尽u = r u = u ( 3 ) r ( x uy ) = r xu r y ( 4 ) 星( x n y ) = 星x n 墨y ( 5 ) x y 4 r x c _ r y ( 6 ) x g r x c _ r y 国r ( ) ( ny ) c _ r x n r y ( 8 ) 尽( x uy ) 星x u 墨y ( 9 ) 墨( 劢= r x ( 注：x - u 一均 ( 1 0 ) r ( 玛= 星x 0 1 ) r _ ( 星均= r ( 尽玛= 星x ( 1 2 ) r ( r 均= 星( r ) p = r x 下面介绍刻画粗糙集特征的一些方法。 由于集合边界域的存在使得存在不确定性。集合的边界域越大，其精确性 越低；反之越高。为了更精确地表示这种r o u g h 近似精度的思想，这里引入精 度的概念。由等价关系r 定义的集合x 的近似精度为： 口r ( ) p = l 墨xi ir xi 其中x 妒，ixi 表示x 的基数。若x o 可定义口趵= 1 。 由于墨x c r x ，显然；0 s 口r ( 均s 1 。当口r ( ) ( ) = 1 时，即星x = r x ，集合 x 的r 边界域为空集，x 为r 可定义；当口r 1 时，即星x c r x ，集合x 有非空r 边界域，x 为r 不可定义。 我们可以利用近似精度来定义x 的r 粗糙度： p x ( x ) = - l - 口r 这里我们可以看到，x 的r 粗糙度与近似精度正好相反，它表示的是集合x 的 知识的不完全程度。 5 江南大学硕士学位论文 r o u g h 集的近似精度口r 和粗糙度pr a p 这两种数字特征说明了边界域 的大小，但没有说明边界域的结构，因此可以由上、下近似集来定义粗糙集的 四种拓扑特征： ( 1 ) 若墨x 妒r r x # u ，则称x 为r 粗糙可定义。 ( 2 ) 若星x = o 且r x u ，则称x 为r 内不可定义。 ( 3 ) 若星x 妒且r x = u ，则称x 为r 外不可定义。 ( 4 ) 若星x = 妒r r x = u ，则称x 为r 全不可定义。 这四种拓扑特征有着直观的意义。如果x 为r 粗糙可定义，我们可确定u 中某 些元素属于x 或x ；如果x 为r 内不可定义，我们可确定u 中某些元素是否 属于x ，但不能确定u 中的任一元素是否属于x ；如果x 为r 外不可定义， 我们可确定u 中某些元素是否属于x ，但不能确定u 中任一元素是否属于x ； 如果x 为r 全不可定义，我们不能确定u 中任一元素是否属于x 或x 。 粗糙集的精度数字特征和拓扑结构之间存在一种关系。当集合x 为r 内 不可定义或全不可定义，则其精度为0 ：当集合x 为外不可定义或全不可定义 时，则集合x 的补集的精度为0 ；所以即使知道了集合的精度，也不能确定它 的拓扑结构；反过来，集合的拓扑结构也不具备精度的信息。 2 3 知识约简与核 ( i ) 属性约简与核 知识( 属性) 约简( a t t r i b u t er e d u c t ) 是粗糙集理论的重要研究内容之一。一般来 说，信息系统中属性的重要程度是不同的，且常常存在冗余的属性，因此有必 要进行属性约简p 1 1 。所谓属性约简就是在保持信息系统分类能力不变的情况下， 删除其中不重要的和冗余的那些属性【3 0 l 。 下面定义属性约简的相关的一些概念： 令r 为一族等价关系，p e r ，若 i n d ( r ) = i n d ( r 一 p ) ， 则称p 为r 中不必要的；否则称p 为r 中必要的。若对于每一个p e r 都是r 中必要的，则称r 为独立的；否则称r 为依赖的。 设p c _ r ，如果p 是独立的，且i n d ( p ) = i n d ( r ) ，则称p 为r 的一个约简。 6 第二章粗籀集理论基本概念 显然可知道r 有多种约简。r 中所有必要属性关系组成的集合称为r 的核( c o r e ) ， 记作c o r e ( r ) 。 定理2 1 c o r e ( r ) = nr e d ( r ) ，其中r e d ( r ) 表示p 的所有约简。 这里要说明的是，一般属性约简不唯一，其中包含关系最小的约简为最小 约简【矧。而属性核是唯一的。 属性核在知识信息系统中为最重要的特征集合，它包含在所有约简之中， 因此可以作为属性约简的基础，在属性核之上通过一定的方法选取属性增加到 核中，从而得到约简集合【4 】。 例2 1 设一个信息系统s = ( u ，r ) ，其中u = x l 】【2 ，x s ，r = r t ，r 2 ，s 3 ，如 表2 1 【1 6 l 所示： 表2 1 等价关系r l ，r 2 ，r 3 有下列等价类： u r l = x l ，x 4 ，x 5 ， x 2 ，x s ， x 3 ， x 6 , x 7 ) u r l = x i ，x 3 ，x s ， 】【6 ) ， x 2 , x 4 ，x 7 , x 8 u r l = x 1 ，x s ) ， x 6 ， x 2 ，x 7 , x 8 ， x 3 ，x 4 关系u i n d ( r ) 有下列等价类： u i n d ( r ) = x l ，x s ， x 2 ，x s ， x 3 ， 】【4 ) ， x 6 ) ， x 7 ) 对于r 1 有 u 五n d ( r - - r 1 ) ) _ x 1 ，x s ) ， x 2 ，x 7 ，x 8 ) ， x 3 ， x 4 ， x 6 u f l n d ( r ) 所以r 1 为r 中必要的。 对于r 2 有 w n d ( r 一 r 2 ) ) = “x l ，x s ， x 2 ，x s ， x 3 ， 】【4 ) ， x 6 ， x 7 ) = 啪d ( r ) 所以r 2 为r 中不必要的。 对于r 3 有 u 五n d ( r 一 r 3 ) = x i ，x 5 ， x 2 , x s ， x 3 ， 】【4 ) ， x 6 ， x 7 = u h i d ( r ) 所以r 3 为r 中不必要的。 这表明r 的分类同r 一 r 2 ) 和r 一 r 3 的分类相同，即该信息系统的知识 7 江南大学硕士学位论文 分类可以用u 五n d ( r 1 ，r 2 ) f 阳u 五n d c r l ，1 3 ) 来表达。为了得到r 的约简，需要检验 r 1 ，r 2 和 r 1 ，r 3 是否为独立的。 因为u i n d ( r 一 r 2 刖r 1 即：u i n d ( r 1 , r 3 ) # u r 1 所以r 3 为必要的 因为u i n d ( r - - r 2 ) 为哪r 3 即：u l n d 假1 ，r 3 ) u r 3 所以r i 为必要的 故 r 1 ，r 3 为独立的，也就是说 r t ，r 3 是r 的一个约简。 因为u t n d ( r 一 r 3 为叫r 1 即：u f m d f 9 1 ，r 2 d m r i 所以r 2 为必要的 因为u i n d ( r 一 r 3 ) m r 2 即：u m d ( r l ，r 2 籼r 2 所以r 1 为必要的 故 r 1 ，r 2 为独立的，也就是说 r 1 ，r 2 也是r 的一个约简。 这样r 有两个约简 r 1 ，r 2 ) 和 r 1 ，r 3 ，那么r 的属性核为c o r e ( r ) = r 1 ，r 2 n r 1 ，i t 3 = r 1 。 在实际应用中，一个分类相对于另一个分类的关系很重要，这里需要引入 相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念，首先定义一个分类相对 于另一个分类的相对正域。 一个信息系统s = ( u ，r ) ，p c _ r 、q c - r 为两个等价关系，q 的p 相对正域 记为p o s k q ) ，即 p 0 s 枷( i n d ( q ) ) = u x e u i n d ( o ) p x q 的p 相对正域是u 中所有根据分类u p 的信息可以准确地划分到关系 q 的等价类中去的对象集合1 2 3 1 。 如果存在p p ，使得 p o s i n d ( e ) ( i n d ( q ) ) = p o s i n d t p ( p ) ( i n d ( q ) ) 则称p 为p 中q 不必要的；否则称为必要的1 1 9 】。 为简便起见，用p o s e ( q ) 代替p o s i n d 0 p x i n d ( q ) ) 。 若p 中的每个p 都为q 必要的，则称p 为q 独立的( 或p 相对于q 独立) 。 设s 口，s 为p 的q 约简当且仅当s 是q 独立的，且p o s s ( q ) = p o s p ( q ) 。 此时p 的q 约简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称相对核，记为 r e 0 ( p ) ( i i ) 决策信息系统 决策信息系统( 决策表) 是一种特殊而重要的信息系统。 设s = ( u ，v , l a o d ) ) 为决策信息系统( 决策表) ，其中，u = ( x t x 2 函) 是 非空有限样本集，称为论域；a 有限条件属性集；d 是决策属性；v 是条件属 性a a 的值域；f ：u x ( a u d ) 一v 的映射函数i 埘。 8 第二章粗糙集理论基本概念 属性集合p a 对决策属性d 的相对正域是：p o s k d ) = ux e u d _ px 。 下面讨论知识的依赖性重要性。 对于信息系统s = ( u ，r ) ，p c _ r 、q c _ r ： ( 1 ) 知识q 依赖于知识p ( 记作p q ) 当且仅当i n d ( p ) c i n d ( q ) ( 2 ) 知识p 与知识q 等价当且仅当p ；q 且q j p ，即i n d ( p ) = i n d ( q ) ( 3 ) 知识p 与知识q 独立当且仅当p q 和q p 都不成立 当知识q 依赖于p 时，也称知识q 是由p 导出的。 有时候知识的依赖性可能是部分的，并不是完全依赖的，也就是说知识o 仅有部分是由p 导出的，可以用相对正域来描述 信息系统s = ( u ，r ) ，p r 、q _ cr ，定义依赖度 七= y “q ) = ip o s k q ) i iu i 这时可称知识q 是k 度依赖于知识p 的，记作p q 。显然0 k 1 。当k = 1 时，称q 完全依赖于p ；当0 七 1 时，称q 粗糙( 部分) 依赖于p ；当k = o 时，称q 完全独立于p 。 在信息系统中不同的知识可能具有不同的重要性。为了找出这种重要性， 可以采用从属性集r 巾去掉一些属性后分类的变化程度。若去掉该属性后相应 得分类变化较大，则说明该属性重要性高；反之，说明该属性的重要性低。 信息系统s = ( u ，r ) ，p c ：r 、q c _ r ，属性子集s 口关于q 的重要性定义为 盯“s ) - r k q ) - yps ( q ) 对于决策表s = ( u ，v , f , a o d ) ) ，a a 关于 d 的重要性定义为 o r i 】( a ) = r “d ) 一y a - a ( d ) 例2 2 决策表s = ( u ，v , f , a o d ) ) ，其中u = x l ，x 2 ，x s ，条件属性集 a - a l ，a 2 ，a 3 ，决策属性 d ) 如表1 1 7 1 2 2 表2 2 a 2a 3 0o 9 一一一一一一一一一 江南大学硕士学位论文 x 8 1021 属性a l ，a 2 , a 3 ，分别有下列等价类 u a l - - x l ，x 2 , x 3 ， x 4 ，x 5 ，x 6 x t , x 8 u a 2 ) = x l ，x 2 ，x 3 ，x 4 ，x 6 】【8 ， x 5 ，x 7 ) u a 3 ) = “x 1 ，】【4 ) ， x 2 ，x s , x t ， x 3 ，x 6 ，x 8 ) ) 属性 a l a 2 a l ，a 3 a 2 , a 3 分别有下列等价类 u a l ，a 2 ) = x l ，x 2 , x 3 ， x 4 ，】【6 】【8 ) ， x 5 , x 7 u a l ，a 3 ) = x d x 2 ， ， x 3 ， 】【4 ) ， x 5 , x t ， x 6 , x s u a 2 ，a 3 = x l ，x 4 ) ， x 2 ， x 5 ，x 7 ， x 3 ，x 6 , x s 条件属性a 和决策属性 叮分别有下列等价类 u a x l ， x 2 “x 3 ， 】【4 ， x 5 ，x 7 ， x 6 ，】【8 ) u 町= “x 2 ，x 3 ，x 6 , x 7 ， x l ，x 4 ，x 5 ，x 8 ) 所以： p o s a ( d ) = x 1 ，x 2 ，x 3 ，】【4 七一r a ( d ) = ip o s a ( d ) i iu | = 4 8 = 0 5 这说明a 是k = 0 5 度依赖于 d ) 对于属性a - a 1 ) 有 p o s a - a 1 ( d ) = x l ，x 2 ，x 4 = p o s a ( d ) 故 a 1 是a 中d 必要的； 对于属性a - a 2 有 p o s a - a 2 ( d ) = x 1 ，x 2 ，x 3 ，】【4 ) = p o s a ( d ) 故 a 2 是a 中d 不必要的； 对于属性p 卜 a 3 有 p o s a a 3 ( d ) = 妒：p o s a ( d ) 故 a 3 是a 中d 必要的 a 2 是a 中d 不必要的，现在分析a - a 2 是否为独立的， 因为 p o s a a 1 ，a 2 ( d ) = p o s | 3 ( d ) = x l , x 4 ：p o s a ( d ) p o s a a 2 ，a 3 ( d ) = p o s 一l ( d ) = ：p o s a ( d ) 所以a - a 2 ) 是独立的，即a 的 d 的约简为a - a 2 ) = a l ，a 3 ，只有这一个约简， 故a 的 d ) 的核c o r c a ( d ) = a l ，a 3 。 下面分别来计算属性的 a 1 ) a 2 和 a 3 重要度 盯u ( a 0 = y “d ) 一y a - - l ( d ) = 4 8 3 8 = 1 8 l o 第二章粗糙集理论基本概念 盯u ( a 2 ) = r “d ) 一ra a 2 ( d ) = 4 8 4 8 = 0 o r u ( a 3 ) = y “d ) 一ya a 3 ，( d ) - - 4 8 一o = 4 8 所以可知属性 a 3 ) 最重要，其次是 a 1 ) ， a 2 是最不重要的。 在决策表中。最重要的就是要导出决策规则，在产生决策规则之前，可首 先对决策表中的属性进行约简，从而可以减少属性的数量，这就降低了规则产 生的复杂性【6 l 。 设s = ( u ，v , f , a u d ) ) 为决策信息系统( 决策表) ，令x i 和y j 分别为u a 与 u d q a 的等价类，d e s ( x i ) 表示对等价类x i 的描述，即等价类x i 对于各条件 属性值的特征取值；d e s ( y j ) 表示对等价类y j 的描述，即等价类y i 对于各条件属 性值的特征取值；决策规则的定义如下： 码：d e s ( x i ) 一d e s ( y j ) ，k n y j 妒 规则的确定性因子p p ( i ，y j ) = ix i ny ji ix ii ，o ( x i ，y j ) 1 当o ，y j ) = 1 时，r i j 表示确定性规则； 当0 p ( x j ，y j ) 一( d ，o ) n 江南大学硕士学位论文 1 4 2 ：( a 1 ，1 ) 人( a 3 ，o 卜 1 ) 因为 z ( x 5 ，y 1 ) = i x s n y li lx 5i = o 5 z ( x 5 ，y 2 ) = ix s n y 2i i ) 【5l = 0 5 ( ) ( 6 ，y 1 ) = ix 6 n y li i ) 【6i = o 5 z c r 塥y 2 ) = lx 6 n y 2i ix 6i = 0 5 所以不确定性规则有 1 5 1 ：( a l ，1 ) a ( a 3 ，l 卜( d ，o ) ，确定性因子为0 5 r 5 2 ： ( a 1 ，1 ) a ( a 3 ，1 卜+ ( d ，1 ) ，确定性因子为0 5 r 6 l ： ( a l ，1 ) 八( a 3 ，2 ) 吖d ，0 ) ，确定性因子为0 5 r 6 2 ：( a l ，1 ) a ( a 3 ，2 卜+ ( d ，1 ) ，确定性因子为0 5 第三章属性约简算法的研究 第三章属性约简算法的研究 本章主要在目前粗糙集理论的基础上， 容样本集的概念，并证明了相关判定定理， 算方法。 3 1 目前属性约简存在的问题 给出了一些定义和定理。定义了相 最后给出了属性核和属性约简的计 属性约简是粗糙集理论的核心内容之一，它反映了一个信息系统的本质信 息。所谓属性约简，就是在保持系统分类或决策能力不变得条件下，删除其中 不重要和冗余的属性。从而减少下一步计算要处理的数据量和排除一些无用信 息的干扰。属性约简就是求得原始集合的一个子集，而这个子集和原始集有着 相同的分类能力 由属性约简的定义可知： 对于一个决策信息表s = ( u ，v ；罅u d ) ) ，属性集合p c _ a ，f 为a 的约简当且 仅当 ( 1 ) p 是a 的独立子族，且 ( 2 ) p o s t ( d ) = p o s a ( d ) a 的d 约简称为相对约简。a 的所有d 约简的交集称为a 的d 核，称为相对属性核， 记为：c o r e d ( a ) 。 a 的约简是不唯一的，存在多种约简，而属性核是唯一的。 目前的属性约简的主要思想是先计算出决策表的属性核( c o r e ) ，然后在核的 基础上逐步扩展求出属性约简。也就是说求出属性约简需要先后两部分，一是 计算出属性核，二是在核的基础上如何扩展求出约简。 对于属性核的计算目前主要是通过区分矩阵( d i s c e r n i b i l i t ym a t r i x ) ! 】来求出 的。区分矩阵是s k o w r o n 教授提出的一种知识表达形式。使用区分矩阵可以很 容易计算出决策表的属性核。 定义3 1 l 冽设一个信息系统s = ( u ，、f ，r ) ，其中论域u = ( x l , x 2 ，j 。) 为非 空有限集，v 是属性项r e r 的值域，f 是u r 到v 的一个映射，即：f ：u r v r 为u 上的等价关系。iui - - n s 的区分矩阵是一个n n 矩阵，其任一元 素定义为 a ( x ，y ) = a aif ( x ，a ) f ( y ，a ) ) 在其他情况下定义为空集，因此，口( x ，y ) 是区别对象x 和y 的所有属性的 江南大学硕士学位论文 集合。 当且仅当区分矩阵中某个元素a ( x ，y ) 为单元素时，该属性属于核 7 1 。该结 论后来被大量文献所引用。随后这个结论又被发现一些问题，最终指出问题的 根本原因是由于信息系统的不相容性导致的1 8 】【9 】。也就是说通过区分矩阵计算核 的方法只能适合于相容的信息系统，即如果信息系统为相容的，当且仅当区分 矩阵中某个元素口( x ，y ) 为单元素时，该属性属于核。也就是说区分矩阵中所有 单元素组成的集合为属性核。 定义3 2 【1 2 】信息系统的相容性定义为：对于一个信息系统s = 邮，v f r ) ，其 中r = a u 田，其中a 为条件属性，t d 为决策属性。当且仅当： v x i , x j u ( i _ j ) ( d ( x i ) - d ( x j ) ) a ：l a e a ( a ( x i ) , j a ( x j ) ) 此时信息系统为相容的。反之为不相容的。 例3 1 决策表s = 一，v , f , a u d ) ) ，其中u = x 1 ，x 2 ，x 5 ，条件属性集 a = a ，b ，c ) ，决策属性 d ) ，如下表3 1 【1 6 1 ，表3 2 为相应的区分矩阵 表3 1 区分矩阵是对成矩阵，如下表3 2 表3 2 通过区分矩阵表3 2 很容易看出其中只有一个单元素口( x 2 ，x 5 ) = b ，所以属性 核是 b ) 。 对于不相容的信息系统，可以利用信息熵解决核属性的计算。 定义3 3 i 【9 】一个信息系统s = c o ，v r ) ，p g t ，p 导出的等价类u p = x 1 ， x 2 ，x 。 ，则p 在u 上的概率分布为 1 4 第三章属性约简算法的研究 i x ：p 】；五，以，五1 【p l ，n ，p j 其中p i - - p ( x , ) = l x , i i u i ，i = l ，2 ，n 定义3 4 【9 】一个信息系统s = ( u ，、f r ) ，p g t ，定义p 的信息熵【明h p ) 为 日一一p 隅) l o 妇) ) 口 定义3 5 1 9 ) - - 个信息系统s = ( u ，、f ，r ) ，p g t ，q g l ，p 导出的等价类u p = x l ，x 2 ，x j ，q 导出的等价类u q = y 1 ，y 2 ，y a ，q 相对于p 的条件熵 【9 】为 日( q i 竹- 一善p ( 置) 善p 嘶i 五) 1 0 9 ( p 辑i 五) ) 其中p 嘶i 五) 一kn x , l