（应用数学专业论文）概念格上的粗糙集与拓扑空间的关系.pdf

概念格上的粗糙集与拓扑宅间的关系 摘要 在经典粗糙集中，基于上、下近似算子，我们可以单独由上、下近似算子构造 拓扑空间，本文研究了概念格上两种上、下近似算子的性质，得到了由上、下近似 算子可以构造拓扑空间的条件 首先在第二章中，简单介绍了格和拓扑空间的基础知识，并研究了在序集合中， 一个集合的上集、下集与上界、下界的关系，以及在格和完备格中的具体表示形式 其次，在第三章中我们简单介绍了经典粗糙集的基本知识，并研究了在概念格 上基于上、下近似算子构造拓扑空问的条件 再次，研究了概念格上基于上、下近似算子构造的拓扑空间的性质： ( 1 ) 如果( 以t ) 为一拓扑空间，则b = e x t ( j ( l ) ) u d 为( 以t ) 的一个基，其 中j ( l ) 是概念格l 的并不可约元组成的集合 ( 2 ) 如果( t ) 为一拓扑空间，则b = e x t ( l ) 为u 8 9 - - 个覆盖，并j t e x t ( j ( l ) ) 是覆盖b 的一个约简 ( 3 ) 如果( 玑t ) 为一拓扑空间，其中u 为有限对象集合，那么此拓扑空间具有可 数基，并且拓扑空间的子集的每一个覆盖都有可数子覆盖 ( 4 ) 如果( 阢t ) 为一拓扑空间，则对于任意z 以存在( a ，b ) l ，使得a = z ) 成 立的充分必要条件是( 以t ) 是一个h a u s d o r 任空间 关键词：格；概念格；上、下近似算子；粗糙集；形式概念背景 i i 硕士学化论文 a b s t r a c t i nt h ec l a s s i c a lr o u g hs e t ，b a s e do nt h eu p p e ro rl o w e ra p p r o x i m a t i o n o p e r a t o r s ， w ec a nc o n s t r u c t et o p o l o g i c a ls p a c e ，i nt h i sp a p e r ，w ed i s c u s st h ep r o p e r t i e so f ak i n do fu p p e ra n dl o w e ra p p r o x i m a t i o no p e r a t o r si n c o n c e p tl a t t i c e w ea l s o o b t a i nt h ec o n d i t i o n sf o rc o n s t r u c t i n gt o p o l o g i c a ls p a c ew i t ht h eu p p e ra n dl o w e r a p p r o x i m a t i o no p e r a t o r s f i r s t l y , i ns e c t i o n2 ，w eg i v eab r i e fi n t r o d u c t i o nt ot h ec o n c e p tl a t t i c ea n d t o p o l o g i c a ls p a c e ，a f t e rt h a t ，w es t u d yt h er e l a t i o nb e t w e e nl o w e rs e t ，u p p e rs e ta n d u p p e rb o u n d ，l o w e rb o u n di no r d e r8 e t w ea l s og i v et h es p e c i f i cr e p r e s e n t a t i o no f t h e i rr e l a t i o ni nl a t t i c ea n dt h ec o m p l e t el a t t i c e s e c o n d l y , i ns e c t i o n3 ，w eg i v eab r i e fi n t r o d u c t i o nt ot h ec l a s s i c a lr o u g hs e t s w eo b t a i ns o m et h ec o n d i t i o n so fc o n s t r u c t i n gt o p o l o g i c a ls p a c eb a s e do nt h eu p p e r a n dl o w e ra p p r o x i m a t i o no p e r a t o r si nc o n c e p tl a t t i c e t h i r d l y , w eo b t a i ns o m ep r o p e r t i e so ft o p o l o g i c a ls p a c eb a s e do nt h eu p p e r a n dl o w e ra p p r o x i m a t i o no p e r a t o r si nc o n c e p tl a t t i c e ： ( 1 ) i f ( 配t ) i sat o p o l o g i c a ls p a c e ，t h e nb = e x t ( j ( l ) ) udi sab a s eo f ( 以t ) ，w h e r ej ( l ) i st h es e to fi r r e d u c i b l ee l e m e n t so ft h ec o n c e p tl a t t i c el ( 2 ) i f ( 配t ) i sat o p o l o g i c a ls p a c e ，t h e nb = e x t ( l ) i sac o v e ro fu ，a n d e x t ( j ( l ) ) i sar e d u c t i o no ft h ec o v e rb ( 3 ) i f ( 阢t ) i sat o p o l o g i c a ls p a c e w h e r eu i saf i n i t es e t ，t h e nt h i st o p o l o g i c a l s p a c eh a sc o u n t a b l eb a s e ，a n dt h ec o v e ro fe v e r ys u b s e to fuh a sac o u n t a b l es u b - c o v e r a g e ( 4 ) i f ( 以t ) i sat o p o l o g i c a ls p a c e ，t h e nf o ra n yz us u c ht h a ta = z ) i f a n do n l yi f ( t ) i sah a u s d o r f fs p a c e k e yw o r d s ：l a t t i c e ；c o n c e p tl a t t i c e ；t h eu p p e ra n dl o w e ra p p r o x i m a t i o n o p e r a t o r s ；r o u g hs e t ；t h ef o r m a lc o n c e p tc o n t e x t i i i 硕士学位论文 1 1 研究背景 第1 章绪论 形式概念分析f 1 ( f o r m a lc o n c e p ta n a l y s i s ，f c a ) ，又称为概念格，由德国的 r u d o l fw i l l e 教授于1 9 8 2 年提出【2 】形式概念分析中的概念来源于哲学，在哲学中， 概念被理解为由外延和内涵两个部分所组成的思想单元基于概念的这一哲学理 解，w i l l e 教授对概念进行了形式化描述，提出的形式概念分析可以用于概念的发 现、排序和显示在形式概念分析中，概念的外延被理解为属于这个概念的所有对 象的集合，而内涵则被认为是所有这些对象所共有的特征( 或属性) 集所有的概念 连同它们之间的泛化与例化关系可以构成一个概念格概念格结构模犁是形式概 念分析理论中的核心数据结构它本质上描述了对象和特征之间的联系，表明了 概念之间的泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视化概念格 是一种可被用于数据分析、知识发现和信息检索，软件工程1 3 1 ，信息提取和数据挖 掘【4 ，5 】的方法，目前已在信息科学中取得了很多成功的应用【6 1 ，并仍然具有很大的潜 在应用价值 1 2 概念格研究的主要内容 ( 1 ) 基础理论的研究这方面主要包括对概念格的代数性质的研究、对概念格 之间的同态及同构的研究、对概念格的子格及商格的研究等，是形式概念分析的理 论基础 ( 2 ) 概念格的构建构建概念格的算法大致可分为两大类：批处理算法和增量算 法概念格的构建在形式概念分析中占有十分重要的地位，是形式概念分析应用的 基础 ( 3 ) 概念格的修剪在一般情况下，概念格的节点数会随着形式背景的增大成 指数级增长，因此在数据集比较大的情况下，就需要对概念格节点的增长进行控制， 即对概念格进行修剪 ( 4 ) 规则提取不少学者讨论了从概念格上提取规则的问题，概念格和其他分 类器相比，其提取的规则具有相当或更好的分类效果 ( 5 ) 形式概念分析与粗糙集的关系形式概念分析与粗糙集理论都是进行数据 挖掘的工具，建立讨论它们之m 的联系是为了更好地进行知识获取，从而粗糙概念 分析应运而生 概念格上的粗糙集与拓扑空间的关系 ( 6 ) 模糊概念格主要研究模糊环境下概念格的牛成与规则获取 ( 7 ) 概念格的可视化主要研究如何有效地显示概念格的结构 ( 8 ) 概念格的应用目前形式概念分析已经广泛应用于信息检索、数字图书馆、 软件工程和知识发现等领域 1 3概念格研究的历史、现状及其成果 在概念格理论刚提出时，只有德国国内少数学者对形式概念分析进行研究，并 且主要其中在理论研究，采用数学的、抽象的方法对问题进行描述、分析和论证在 概念格的应用方面，这个时期的主要成果是在德国的几个项目中的应用取得成功 此后几年，由于信息科学的迅速发展，而形式概念分析理论中的某些数据结构为信 息科学的研究提供了一些基本而有效的信息表示方法，因此在国际上迅速而广泛地 开展起对形式概念分析理论及其应用的研究，形式概念分析近期的研究成果如下： ( 1 ) 基于概念格的分类系统：由s a h a l r d 开发的r u l e a r n e r 系统【7 8 1 ，其根据 属性构造出概念格，然后从构建的概念格中提取出分类规则用于支持对象的分类， 此外还有其它一些分类系统 ( 2 ) g o d i n 等描述了基于概念格模型的概念形成方法【9 1 ，主要提出了从概念格 中提取出蕴涵规则的算法，并使用了关系数据库中函数依赖的理论结果来处理规 则的蕴含问题，为了提高抗噪音能力，其提出了从概念格中提取近似规则的算法， p a s q l l i e r 等研究了关联规则的提取问题【圳 ( 3 ) h otb 研究了基于概念格的概念聚类方法【l l 】，实现了一些学习系统，包 括o s h a m 和i n c o s h a m ，允许系统改进它自身的推理性能，从而提高了系统预测 未知实例的灵活性 ( 4 ) w i l l e 教授引入背景网络1 1 2 l 的形式方法，提出了不同形式背景之间的四种 不同的操作：并置，下置，融合以及级连 ( 5 ) 胡可云等人提出了利用概念格进行分类和无冗余规则的提取1 1 3 l ，谢志鹏等 人提出利用概念格的层次关系提取关联规则1 1 4 - 1 6 】，刘宗田等人提出的利用容差关 系建立广义概念格提取近似规n i l e ，胡学钢【1 8 - 2 2 】等人在一般概念格的基础上提出 了扩展概念格、约简概念格、相对约简格和量化概念格的定义，并利用这些非经典 概念格进行高效的规则提取张国强等人提出逼近概念格【2 3 1 2 3 ，李庆国，陈学友提出 逼近概念格的生成方法赵奕【2 5 , 2 6 等人针对概念格与r o u g h 集之间的联系，把二 者有机的结合在一起提出t r o u g h 概念格，并在此基础上提取蕴含规则侯锦1 2 7 】等 人提出了利用概念格进行r o u g h 集理论中重要的组成部分一属性约简此外还包括 一2 一 硕士学位论文 一些概念格构造和维护算法 2 8 , 2 9 的研究等等 1 4 本文研究的工作及成果 本文系统地介绍了形式概念分析、粗糙集和拓扑空间的相关理论，并在认真学 习前人成果的基础上： ( 1 ) 研究基于粗糙集上、下近似算子构造的概念格的上、下近似算子的性质 ( 2 ) 研究了一般概念格单独基于某些上、下近似算子可以构造拓扑空间的条件 ( 3 ) 研究了一般概念格基于某些上近似算子所构造拓扑空间的性质 1 5本文的组织结构 全文共分为三章，其组织结构如下： 第一章绪论介绍了形式概念分析的研究背景，研究的主要内容，以及目前国 内外的研究现状和本文的组织结构 第二章形式概念分析和拓扑空间相关的基础知识及其相关性质的推广 第三章首先简单介绍了粗糙集的基础知识，然后由粗糙集的上、下近似算子引 出概念格的上、下近似算子，近而讨论了算子的相关性质以及上、下近似算子与拓 扑空间的关系 一3 一 概念格上的粗糙集与拓扑窄问的关系 第2 章格和拓扑空间的基础知识 2 1 格的定义及相关性质的推广 本节主要介绍了格的有关定义和性质，作为后面章节的预备知识 定义2 1 1 3 0 lp 是一个集合，定义p 上的序关系是其上的一个二元关系，对于比， y ，z p 满足如下条件： ( 1 ) z z ； ( 2 ) z 可和可z ：= z = 可； ( 3 ) z y f l 铂y z = 争x 名 定义2 1 2 3 0 】p 是一个序集合，并且q 尸， ( 1 ) q 是一个下集，如果x q ，y 只y x ，我们有y q ； ( 2 ) q 是一个上集，如果z q ，y p y z ，我们有y q 定义2 1 3 1 3 0 】p 是一个序集合，并且s 尸， ( 1 ) 元素z p 是s 的一个上界，如果对于所有的z s ，8 z ，所有上界组成的 集合记为： s 钍= 【z p i ( v s s ) s s ( 2 ) 元素x p 是s 的一个下界，如果对于所有的z s ，8 z ，所有下界组成的 集合记为： 伊= z p l ( v s s ) s s 推论2 1 4 p 是一个序集合，并且s p ， ( 1 如果q 是s 的上界集合，那么q 是一个上集； ( 2 ) 如果q 是s 的下界的集合，那么q 是一个下集 证明：由序集合的定义和上集、下集、上界、下界的定义显然可得 令xv 可代表s u p x ，) ，zay , f 4 ：表i n f x ，可) 定义2 1 5 1 3 0 p 是一个非空的序集合： ( 1 ) 如果对于所有的z ，y p ，zvy ，za 秒都存在，则称p 是一个格； ( 2 ) 如果对于所有的s p ，v s ，a s 都存在，则称p 是一一个完备格 推论2 1 6p 是一个序集合，且尸是一个格： ( 1 ) 如果s 是个有限集合，则s “= nt8 = 下vs ； ( 2 ) 如果s 是个有限集合，s 。= n 上8 = j ，八s 一4 一 硕二l 二学位论文 推论2 1 7 尸是一个序集合，且p 是一个完备格： ( 1 ) 如果s 是p 的任意子集合( 包括有限子集和无限子集) ，则酽= nts = t vs ； ( 2 ) 如果s 是p 的任意子集合( 包括有限子集和无限子集) ，则= nj ，s = j ， s s 八8 o s 证明：由相关定义易得，证明略 定义2 1 8 【3 0 l 设p q 是两个序集合，映射垆：p _ q 是保序的，如果满足条件： 在p 中z y 兮在q 中妒( z ) 妒( 可) 定义2 1 9 【3 0 lp q 是两个格，映射f ：l _ k 称为同态或格同态，如果，是保交和 保并的，即满足如下条件：对于任意z ，簦l ( 1 ) f ( x v y ) = f ( x ) v ，( 可) ； ( 2 ) f ( x 八y ) = f ( x ) 八，( ) 引理2 1 1 0 a o l l ，k 是两个格，映射厂：l k ，如果，是同态映射，那么，是一个 保序映射 推论2 1 1 1 a o l ，k 是两个格，映射f ：l _ k ，是保序映射，但不一定为同态映 射 由保序映射和同态映射的定义容易得同态映射一定是保序映射但保序映射不 一定是同态映射，如例2 1 所示：f ：l _ k 侈1 1 2 1 ： 表2 1 形式概念背景( uk 冗) 表2 2 形式概念背景( u 7 ，y 7 ，兄7 ) 一5 一 概念格上的粗糙集与拓扑空间的关系 口一 ( a )( b ) 图2 1 图o ，b 是以表2 1 ，2 2 为形式概念背景形成的概念格 表2 1 和表2 2 分别是两个概念格的形式概念背景，在表2 1 中对象集合u = 1 ，2 】， 属性集合v = o ，6 ) ，在表2 2 中对象集合u 7 = 1 7 ，2 7 ) ，属性集合v 7 = 0 7 ，6 ，c ，) 由表2 1 我们可以构造2 个概念( 1 ) ， n ，6 ) ) ，( ( 1 ，2 ， n ) ，由表2 2 我们可以构造4 个概 念( 2 7 ， 0 7 ，c ，) ) ，( 1 7 ) ， 口7 ，6 ，) ) ，( _ 1 7 ，2 7 ) ， 0 7 ) ) ，( 0 ， o ，6 ，c ，) ) ，因此我们利用相关软件 画出其构成的概念格的图像图2 1 ，其中图2 1 ( a ) 是以表2 1 为背景形成的概念格的图 像，图2 1 ( b ) 是以表2 2 为背景形成的概念格的图像，如上：我们定义以表2 1 和表2 2 为 背景形成的概念格之间的映射如下：，( ( 2 7 ) ， 0 7 ，c ，) ) ) = ( 1 ) ， a ，6 ) ，厂( ( 1 7 ) ， 0 7 ，6 ，】) ) = ( 1 ， o ，6 ) ) ，l 厂( ( 0 ， 0 7 ，6 ，c ，) ) ) = ( 1 ) ， n ，6 ) ) ，厂( ( 1 7 ，2 1 ) ， ) ) ) = ( 1 ，2 ) ， o ) ) 由上面的例子易得，保序映射不一定是同态映射 推论2 1 1 2 3 0 】lk 是两个链，映射f ：l _ k ： ( 1 ) 若l 厂是保序映射，则为f h 态映射； ( 2 ) 若。厂是同态映射，则厂为保序映射 引理2 1 1 3 3 0 】有限格一定是完备格 引理2 1 1 4 1 3 0 1 p 是一个序集： ( 1 ) p n 果c = c o ，c 1 ，c 2 ，c 3 ，c 4 ) 是p 中的一个i c i = 佗+ 1 有限链，那么我们 就说c 的长度是n ： 暑 _ 一一一u 硕士学位论文 ( 2 ) p 是有限长度的，如果p 存在一个长度为扎的链，礼n o ； ( 3 ) 如果p e p 的每个链都是有限的，则p 没有无限的链 定义2 1 1 5 3 0 】l 是一个格，z l 是交并不可约的，如果z 满足条件： ( 1 ) x 0 ； ( 2 ) 对于 c a ，b l ，z = avb 辛z = a 或者z = b 其中条件( 2 ) 等价于a z ，b 其中磊为定理3 1 1 3 中所定义的选择函数 3 2概念格与不可构造拓扑空间的上、下近似算子 在概念格l 中，对于一个概念( a ，b ) l ，因为一个概念的外延和它的内涵是唯 一相互决定的，所以我们只需研究概念的外延的性质就可知道内涵的性质，或只研 究内涵的性质就可以知道外延的性质，本节我们主要研究概念外延的性质 定义3 2 1 1 4 6 l 对于一个概念格l ，它的所有外延的集糊e x t ( l ) ，即： e x t ( l ) = e x t e n t ( x ，y ) i ( x ，y ) 三) f i t e x t ( l ) 的定义可知，e x t ( l ) 包含全集u ，其中为所有对象组成的集合，并 且在有限交下是封闭的，即a e x t ( l ) ，b e x t ( l ) ，a n b e x t ( l ) 定义3 2 2 4 6 5 1 】假设( 阢v 兄) 是一个形式背景，对于一个对象集合a u , 我t l j 定义a 的上近似和下近似如下： 丽万( a ) = f t x l x e x t ( l ) ，a x ； s a p r ( a ) = ( x l x e x t ( l ) ，x a ，v x + e x t ( l ) ( x x 辛x + ga ) ) 推论3 2 3 概念格l 以( 以ur ) 为形式背景，对于任意集合a 以由定义3 2 2 所定义的上、下近似算子的定义可知： ( 1 ) 若a e x t ( l ) ，则丽万( a ) = a ； ( 2 ) 若a 芒e x t ( l ) ，则ac ：丽万( 4 ) 且a s - - d - - w w ( a ) 推论3 2 4 设( 以v 兄) 是一个形式概念背景，r 是u 上的一个二元关系，对于任 意x ，y u ，由定义3 2 2 定义的上、下近似算了具有如下性质： 一1 8 硕士学位论文 ( 1 ) x y 令s a p r ( x ) s a p r ( y ) ； ( 2 ) x y 丽万( x ) s - - c - 万( y ) ； ( 3 ) s a p r ( xny ) = s a p r ( x ) ns a p r ( y ) ； ( 4 ) 丽歹( xny ) = 丽万( x ) ns - a - - 万w ( y ) ； ( 5 ) u 曼型( x ) x 丽万( x ) ； ( 6 ) s - - d - - w 矽( o ) = 仍，而万( u ) = u ； ( 7 ) 丽万( xuy ) 丽万( x ) u 丽万( y ) 证明：对于( 1 ) ( 2 ) ( 5 ) ( 6 ) 我们很容易由s a p r ( x ) ，百万( x ) 的定义可得 在经典粗糙集中，上近似算子是闭包算子，而对于概念格我们有以下结论j 注记：s a p r ：x _ 丽万( x ) 不一定是闭包算子 例3 1 ，表3 1 给出了一个形式概念背景( 以vr ) ，其中对象集u = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) ， 其中1 代表水蛭，2 代表鳊鱼，3 代表青蛙，5 代表杂草，6 代表芦苇，7 代表大豆，8 代表玉米属 性集v = a ，b ，c ，d ，e ，g ，h ，i ) ，a 代表生存需要水，6 生活在水中，c 居住在陆地上，d t 产食物需要叶绿素，e 双子叶植物，单子叶植物，9 能够移动，h 有脚，i 哺乳幼崽，其h a s s e 图 如图3 1 表3 1 形式概念背景( 以vr ) a bcde g hi 我们取对象集合己，的子集a = 1 ，2 ，3 ) ，b = 4 ，6 ) ，由定义3 2 2 中所定义的上 一1 9 一 1 2 3 4 5 6 7 8 概念格上的粗糙集与拓扑空间的关系 图3 1 以表3 1 为形式概念背景形成的概念格 2 0 硕士学位论文 近似算子的定义可得： s a 万( a ) = n z i z e x t ( l ) ，a x = 1 ，2 ，3 ) n 1 ，2 ，3 ，4 ) n 1 ，2 ，3 ，5 ，6 ) n 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) = 1 ，2 ，3 ) ， s a - 万( b ) = n x l x e x t ( l ) ，b x = 3 ，4 ，6 ，7 ，8 ) n 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) = 3 ，4 ，6 ，7 ，8 ) ， s a p r ( aub ) = s a p r ( 1 ，2 ，3 ，4 ，6 ) ) = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ， 丽( a ) u 丽( b ) = 1 ，2 ，3 ，4 ，6 ，7 ，8 ) 显然丽( a ) u 丽( b ) 否砀矛( a u b ) 由闭包算子的定义和上面的反例可知，在概念格上丽万：x 一丽万( x ) 不一定 是闭包算子 有上面的注记可知，在经典粗糙集中上近似算子是闭包算子，而在概念格中上近 似算子却不一定是闭包算子，在经典粗糙集中下近似算子是内部算子，在概念格中 下近似算子是否是内部算子昵? 定理3 2 5u s a p r ：x _ u 曼型( x ) 是内部算子 证明：( 1 ) 因为概念格是完备格，所以下近似算子满足：u s a p r ( x ) = x ，u 兰塑( 仍) = o ( 2 ) 对于任意x ，y 由塑丝的定义我们令： s a p r ( x ) = a 1 ，a 2 a m ) ， s a p r ( y ) = b 1 ，岛玩) ， 一s a p r ( x ) n s a p r ( y ) = a 1 nb 1 ，a 1nb 2 a 1n 鼠，a 2nb 1 ，n 玩) = b 1 ，b 2 ，b r ) ， 令 一s a 矿( x n y ) = c ，c 2 ，一a ， 一9 1 概念格上的粗糙集与拓扑窄间的关系 v 鼠s a p r ( x ) n s a w ( y ) ，由下近似算子的定义可得：鼠x ，鼠y 所 以鼠xny ，从而 塑( x ) n 翌( y ) 型( x n y ) v g s a p r ( xny ) ，g xnk g x ，g y 因此 g 塑( x ) n s a p r ( y ) ， 所以 一s a p r ( x n y ) 塑( x ) n 型( y ) ， 从而 一s a p r ( x n y ) = 型( x ) n 型( 矿) ( 3 ) 对于任意x 以由下近似算子的定义，我们令 s a p r = a 1 ，a 2 a n ) ， 其中a x ，1 i n , a lua 2u u 如x ，耳p us