（应用数学专业论文）基于形式背景合成与分解的面向对象与面向属性概念格生成.pdf

摘要 概念格理论，亦称形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) ，是由德国数学家 w i l l er 于1 9 8 2 年提出的它以格理论为基础，用于概念的发现、排序和显示“概 念”的基本观点是从哲学中的概念发展而来的在哲学中，概念被理解为由外延 和内涵所组成的思想单元 g e d i g a , g 、d u n t s h , i 、 y a o ，yy 把形式概念分析 与粗糙集理论相结合，把粗糙集理论中的近似算子引入到概念格中，给出了不同 于经典概念格的两种新的概念格：面向对象概念格与面向属性概念格本论文就 是在这个基础上完成的 本文主要研究了形式背景合成与分解时面向对象与面向属性概念格生成问 题主要研究成果如下： 1 经典形式背景合成与分解的面向对象概念格生成问题首先研究了两个 小形式背景合成新形式背景时面向对象概念格生成方法，并给出了相应定理；然 后研究了形式背景分解成两个子形式背景时面向对象概念格生成方法及定理；最 后，将所得到的结论推广到多个小背景合成以及大背景分解为多个小背景的情 况 2 经典形式背景合成与分解的面向属性概念格生成问题首先研究了两个 小形式背景合成新形式背景时面向属性概念格生成方法，并给出了相应定理；然 后研究了形式背景分解成两个子形式背景时面向属性概念格生成方法及定理；最 后，将所得到的结论推广到多个小背景合成以及大背景分解为多个小背景的情 况 关键词 形式背景，形式概念，合成，面向对象概念格，面向属性概念格 a b s t r a c t ( 英文摘要) c o n c e p tl a t t i c et h e o r y ( a l s oc a l l e df o r m a lc o n c e p ta n a l y s i s ) ，p r o p o s e db yr w i l l ei n19 8 2 ，i sam e t h o df o rd a t aa n a l y s i su s e di nf i n d i n g , o r d e r i n ga n dd i s p l a y i n g o f c o n c e p t s t h eb a s i ct e r mo f ”c o n c e p t ”i sd e v e l o p e df r o mt h ec o n c e p to fp h i l o s o p h y i np h i l o s o p h y , c o n c e p ti su n d e r s t o o da sat h o u g h tu n i tw h i c hi sc o m p o s e db y e x t e n s i o na n di n t e n t i o n g e d i g a , g ，d u n t s h , i a n dy a o ，yyi n t r o d u c e d a p p r o x i m a t i o no p e r a t o ro fr o u g hs e tt h e o r yi n t ot h et h e o r yo fc o n c e p tl a t t i c e s ，a n d p r e s e n t e do b j e c to r i e n t e dc o n c e p tl a t t i c e sa n dp r o p e r t yo r i e n t e dc o n c e p tl a t t i c e s r e s p e c t i v e l y t h et h e s i sw a sa c c o m p l i s h e do nt h eb a s i so f t h a t t h i sp a p e rm a i n l ys t u d i e st h ec o n s t r u c t i o nm e t h o d so fo b j e c to r i e n t e dc o n c e p t l a t t i c e sa n dp r o p e r t yo r i e n t e dc o n c e p tl a t t i c e sw h e nc o m b i n i n ga n dd e c o m p o s i n g f o r m a lc o n t e x t s t h em a j o rr e s u l t sa r e 1 c o n s t r u c t i o no fo b j e c to r i e n t e dc o n c e p tl a t t i c e st h r o u g ht h ec o m b i n a t i o na n d d e c o m p o s i t i o no fc l a s s i cf o r m a lc o n t e x t s f i r s t l y , c o n s t r u c t i o no fo b je c tc o n c e p t l a t t i c et h e o r yf r o mc o m b i n a t i o no ff o r m a lc o n t e x t s ，a n dt h e n ，c o n s t r u c t i o no fo b j e c t c o n c e p tl a t t i c et h e o r yf r o ms u b - f o r m a lc o n t e x t s f i n a l l y , t h eg e n e r a l i z a t i o ni sg i v e n 2 c o n s t r u c t i o no fp r o p e r t yo r i e n t e dc o n c e p tl a t t i c e st h r o u g ht h ec o m b i n a t i o na n d d e c o m p o s i t i o no fc l a s s i cf o r m a lc o n t e x t s f i r s t l y , c o n s t r u c t i o no fp r o p e r t yc o n c e p t l a t t i c et h e o r yf r o mc o m b i n a t i o no ff o r m a lc o n t e x t s ，a n dt h e n , c o n s t r u c t i o no fp r o p e r t y c o n c e p tl a t t i c et h e o r yf r o ms u b f o r m a lc o n t e x t s f i n a l l y , t h eg e n e r a l i z a t i o ni sg i v e n k e y w o r d s f o r m a lc o n t e x t s ，f o r m a lc o n c e p t ，c o m b i n a t i o n ，o b j e c to r i e n t e dc o n c e p tl a t t i c e s ， p r o p e r t yo r i e n t e dc o n c e p tl a t t i c e s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子 版。本人允许论文被查阅和借阅。本人授权西北大学司以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编奉学位论文。l 司时授权中国科学 技术信息研究所等机构将本学位论文收录到中国学位论文全文数 据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 丝f指导教师签名：燮 p 卜年6 只s 加| 拜6b 皇日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特另, j j j h 以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的! 学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作j 7 明确的说i j 月i ：农乃鲥意。 学位论文作者签名：拯于 弘d 年5 月歹日 西北大学硕士学位论文 第一章绪论 1 1 选题的背景 形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 是由德国数学家w i l l er 于19 8 2 年提 出的，用于概念的发现、排序和显示【l 】“概念”的基本观点是从哲学中的概念抽 象出来的在哲学中，概念被理解为由外延和内涵所组成的思想单元形式概念 分析，又称概念格理论，是以数学的序理论特别是格理论为基础的形式背景 ( u 附) 是形式概念分析的基础，它是一个由对象集阢属性集矿以及u 与v 之 间的二元关系月所构成的三元组在形式背景的基础上，获得形式概念( 别) ， 其中，x u 称为概念的外延，是属于这个概念的所有对象的集合；a y 称为 概念的内涵，是x 中所有这些对象共同具有的属性集合概念是外延与内涵的统 一体所有的概念连同它们之间的泛化和例化关系构成一个概念格概念格结构 模型是形式概念分析的核心数据结构它本质上描述了对象和属性之间的联系， 表明了概念之间的泛化和例化关系，其相应的h a s s e 图则实现了对数据的可视 化因此，概念格被认为是进行数据分析的有力工具 概念格在它提出之后的最初十年里，从事研究的工作人员主要是德国达姆施 达特( d a r m s t a d t ) 技术大学的一个研究小组和w i l l e 的学生随着一些有关概念格 方面的文章【2 ，3 ，4 ，5 6 1 的发表和出版，概念格理论引起了越来越多不同学科领域的学 者关注特别是自1 9 9 3 年和2 0 0 3 年开始，召开的两个国际性会议：t h ei n t e r n a t i o n a l c o n f e r e n c eo nc o n c e p t u a ls t r u c t u r e s ( i c c s ) 和t h ei n t e r n a t i o n a lc o n f e r e n c eo n f c a ( i c f c a ) ，更扩大了它的影响在后来的十多年里，它的研究人员逐渐壮大， 形成了许多研究团队，涉及的学科领域有：语言学、软件工程、心理学、人工智 能以及信息检索等另外，在国内也有不少学者对概念格理论进行研究，并在该 领域取得了一定的成绩例如：已出版的专著【7 ，8 】，已完成的博士论文、硕士论 寸1 9 ，1 0 , 1l ，1 2 ，1 3 ，1 4 ，1 5 】箜 寸 概念格不仅反映了概念外延与内涵的统一，而且揭示了概念之间的泛化与例 化关系这种特殊的分类机制使概念格与其它分类方法相比较效果更佳，更具有 实际应用价值目前，概念格研究主要集中在概念格的构造、模型的推广、概念 格的化简、概念格上的分类规则和关联规则的提取、概念格的应用以及与其它理 论的结合等 第一章绪论 概念格是以数学化的概念和概念层次为基础的应用数学领域的一个分支，它 激发了人们对概念数据分析和知识处理的数学思考然而，经过多年的发展，概 念格发生了重大变化，已经从最初提出时的数学定位转移到计算机科学上被认 为是“概念化知识处理( c o n c e p t u a lk n o w l e d g ep r o c e s s i n gc r d ) ”在数学方面的重 要支柱概念格理论的基础是形式概念，由于每个概念的形成需要不止一次的分 类，所以它比单一分类具有更好的概括性此外，概念格清晰的概念层次结构可 以使对象与属性之间存在的联系简洁、生动、直观的表达出来 概念格被认为是进行数据分析的有力工具概念格的建造是概念格应用的基 础概念格的建造就是从数据库中提取所有概念及概念层次结构关系的过程由 于概念格中概念( 节点) 的个数通常随数据库中数据的增加呈指数级增长，因此， 概念格的构造是人们关注的一个课题一般地，构造概念格有两种形式，一种是 先找出概念格的所有概念，然后确定其结构这种形式的关键是概念的生成目 前，用于生成概念的主要方法有：自然算法【16 1 、基于闭包的有序子集法【”】；另 一种则是同时考虑概念和结构这种方式通常是根据已知概念寻找它的临近概念 或者找出它的边，主要算法有：g o d i n 算法、c a p i n e r o 算法、a d d a t o m 算法、增 量算法和批处理算法 1 8 , 1 9 , 2 0 1 等 由于形式概念分析以概念格的形式把数据有机的组织起来，概念格节点反映 了概念内涵与外延的统一，节点问的关系体系体现了概念之间的泛化和例化关 系，因此，非常适合用来发现规则型知识g o d i nr 【2 1 】等在其提出的增量式建格 算法基础上给出了由概念格来提取蕴含规则的算法其基本思想是系统生成当前 节点的所在幂集，并检查其是否包含在其父节点中若没有，则生成以该集合为 前件的规则m i s s a o u i t 2 2 1 等提出了近似蕴含规则的提取算法；h u 2 3 】提出了一种在 概念格上提取分类和关联规则的集成算法p a s q u i e r t 2 4 1 等研究了关联规则的提取 问题 g e d i g a , g 、d u n t s h 。i 、y a o ，yy 把形式概念分析与粗糙集理论相结合，把 粗糙集中的近似算子引入到概念格中【2 5 娜2 2 7 1 ，给出了基于粗糙集的概念格构造方 法粗糙集是研究划分的，而概念格是在划分的基础上产生的，因此，可以利用 粗糙集方法研究概念格的构造对于一个形式背景( u 咄) ，引入一对近似算子分 别叫必要算子( n e c e s s i t yo p e r a t o r ) 和可能算子( p o s s i b i l i t yo p e r a t o r ) ，分别用记号口和 表示【2 7 】，v x c _ u ，a c _ y ，若满足x = ，a = f ，称元素组职4 ) 是一个面向对 2 西北大学硕士学位论文 象概念其中，x o q 面向对象概念g 础) 的外延，么叫面向对象概念p 叫) 的内涵若 满足x = a d ，a = x o ，称元素组伍4 ) 是一个面向属性概念其中，x n q 面向属性 概念a 卅) 的外延，a 叫面向属性概念( x c t ) 的内涵由这些面向对象概念和面向 属性概念同它们之间的泛化和例化关系所构成的格分别叫面向对象概念格和面 向属性概念格【2 7 ，2 引从而丰富了概念格理论，为数据分析提供了新的理论依据 1 2 研究内容 论文基于粗糙集的概念格构造方法研究了形式背景合成与分解的概念格生 成基于化复杂为简单化整为零的思想，把一个复杂的形式背景分解成几个或多 个简单的形式背景合成，在寻找这些简单形式背景的概念时不需要处理复杂的数 据过程通过这些简单形式背景的概念来获得合成形式背景的所有概念，再把合 成形式背景的所有概念连同它们之间的泛化和例化关系相结合就可以构建出合 成形式背景的概念格算法【2 9 】表明该方法在经典形式背景下可以节省建格时间， 本文也是在经典形式背景下研究的，因此，该算法也适用于本文 为了便于理论的证明，论文中主要以两个形式背景合成以及原形式背景分解 为两个子形式背景为研究对象，即把形式背景( 以幽) 看成是由形式背景( 明，巧, r i ) 和( u 2 ，圪如) 合成的或是形式背景( u z ，巧皿1 ) 和( 奶，圪如) 是由形式背景( 以耻) 分解 的，若满足u = u = 址，y = 巧u 匕，r = 墨u 足，这种形式背景的合成称为横向合成 ( 横向分解) ；若满足u = u iu ，v = k = 匕，r = 蜀u 足，该合成称为纵向合成( 纵向 分解) 通过研究形式背景( 奶，所皿1 ) 和( 醍，玛悬) 与合成形式背景( 以耻) 中的面向 对象( 面向属性) 概念的外延( 内涵) 之间的关系，可知道合成形式背景( u k r ) 面向 对象( 面向属性) 概念的外延( 内涵) 是由形式背景( u ，v z , rz ) 和( u 2 ，v 2 , r 2 ) 中面向对象 ( 面向属性) 概念的外延集( 内涵集) 中的元素做交运算或做并运算获得的，由此就 可以获得合成形式背景的外延集( 内涵集) 在获得合成形式背景外延集( 内涵集) 的基础上，根据面向对象( 面向属性) 概念的定义，利用近似算子( u 或) 做相应的 运算就可以获得与外延集( 内涵集) 相对应的内涵集( 外延集) ，从而就可以获得合 成形式背景的所有面向对象( 面向属性) 概念，至此也就完成了形式背景合成的面 向对象与面向属性概念格生成然后再把这一方法推广到有限多个形式背景的合 成，若再遇到复杂的形式背景时就可以利用该方法来处理形式背景的分解与合 成相类似，可将其看成形式背景合成的逆过程，其研究方法相类似，将在第三章 3 第一章绪论 和第四章再进行研究现实生活中根据具体的需要进行相应的合成与分解，然后 再进行相应的信息提取和知识发现 1 3 本文的组织框架 论文主要研究了形式背景合成与分解时面向对象与面向属性概念格生成问 题首先研究了形式背景合成与分解时面向对象概念格生成问题，最后研究了形 式背景合成与分解时面向属性概念格生成问题，获得了一些结论，并把结论进行 推广论文总体上分为四章，从第二章开始具体布局如下： 第二章是基础知识概述这章主要介绍了一些基本概念，包括形式概念、近 似算子、面向对象概念格与面向属性概念格 第三章给出了形式背景合成与分解的面向对象概念格生成首先给出两个形 式背景合成时面向对象念格生成，以及原形式背景分解成两个子形式背景时面向 对象概念格生成，并把相应的结论进行推广 第四章给出了形式背景合成与分解的面向属性概念格生成这章也是先给出 两个形式背景合成时面向属性念格生成，以及原形式背景分解成两个子形式背景 时面向属性概念格生成，并把相应的结论进行推广 最后一章给出总结与展望 4 西北大学硕士学位论文 第二章背景知识 2 1 形式背景与近似算子 形式背景( u 啪) 是形式概念分析的基础 定义2 1 【1 】称( u 咄) 为个形式背景，其中u = “，恐，屯) 为对象集，每个 五o 以) 称为一个对象；y = “，口：，a 。) 为属性集，每个巳( _ ，z ) 称为一个属性： 尺为【，和y 之间的二元关系，r u x v 在形式背景( 以哪) 中，vx e u ，y e v ，若( x ，j ，) r ，我们就称对象工拥有属性 y ，或属性y 被对象x 所拥有，记为x r y 给定了二元关系r 就可以获得以下两 个集合： 坛u ，x r = y e v i x r y v ， v yev ，r y = x ux r y cu 并且x r y y e x r x r y 由上述定义，对于集合x c _ u 和y cv ，则有： x r - - u 斌，r y = u 缈 x e x y e y 由此可见，躲中的任一属性必被x 中的至少一个对象所拥有，r y 中的任一个对 象至少含有】，中的一个属性 对于形式背景( u 咄) ，引入一对近似算子：必要算子( n e c e s s i t yo p e r a t o r ) 和 f 撕( p o s s i b i l i t yo p e r a t o r ) ，分别用记号口和表示【2 7 1 口：2 u 专2 7 与：2 u _ 2 y 定义如下：x x u ， f = 秒v i v x e u ( x r y j x e x ) = d v i r y 册 ( 2 1 ) 彳。= 秒v i 孤u ( x r y a x x ) = 抄v i 缈n x 囝) = u x r = 艘 ( 2 2 ) m 石 对偶的，口：2 7 专2 u 与0 ：2 y 一2 u 定义如下：v y c v ， y 0 = x e u l v y v ( x r y ：，y e 功 = 缸u i x r g n ( 2 3 ) 5 第二章背景知识 p = x u 1 3 y v ( x r y y 功 = x u i x 尺n y g = = u r y y e l = r y ( 2 4 ) 对于形式背景( 以咄) ，这两对算子有如下性质：v x ，五，置cu ， v 】，x ，kg 矿， i )墨五研霹，舛g 墨， x kj 砰砖，砰s 譬 i i )f o 石石0 0 ，妒。y cy 0 口 i i i )掣。口= p ，x 。d 。= x o ，y o 。口= p ，y o 口o = y o i v ) ( 五n x 2 ) o = 矸n 避，( 五u 五) 。= 矸u 霹， ( x n 砭) 口= 砰n 砖，( u 砭) 。= 誓o u 瑶 2 2 面向对象概念格与面向属性概念格 面向对象概念格是由y y y a o 在【2 7 】中引入的，面向属性概念概念格是由 d u n t s c h 和g e d i g a 在2 8 1 中引入的 定义2 2 1 2 7 】设( u 哪) 是一个形式背景，如果一个二元组仪d ，其中 x c u ，y c _ v ，若满足f = y ，y 。= x ，称( x ，y ) 为一个面向对象概念其中，x 称 为面向对象概念的外延，】，称为面向对象概念的内涵 用l ( u ，v ，r ) 表示形式背景( 以咄) 的全体面向对象概念，记 ( 五，) ( 砭，e ) 五量五( 写艺) ( 2 5 ) 则”是l ( u ，y ，r ) 上的偏序关系其中，( 五，x ) 叫作( 五，k ) 的亚概念，( 墨，k ) 叫 作( 五，x ) 的超概念 若( 五，x ) ，( 置，e ) 都是形式背景( u 咄) 中的面向对象概念，则 ( 墨，x ) ( 五，艺) = ( ( 誓n e ) o ，xn r o = ( ( 五n x o o 。，zn k ) ( 2 6 ) ( 五，r o v ( & ，砭) = ( 墨u 五，( 五u 置) 口) = ( 墨u 五，( ku 砭) 。0 )( 2 7 ) 从定义2 2 和性质i i i ) 、i v ) 可证( 墨n 五，( xnr o o o ) 和( ( 五u ) 0 1 3xur ot 包都是 面向对象概念，从而知z ( u ，y ，r ) 是格，且是完备格，称为面向对象概念格 定义2 3 1 2 8 1 设( 以咄) 是一个形式背景，如果一个二元组y ) ，其中 6 两北大学硕士学位论文 x u ，y v ，若满足x = y o ，y = x o ，称功为一个面向属性概念其中，x 称 为面向属性概念的外延，】，称为面向属性概念的内涵 e h ( 2 5 ) 式可知”也是l ( u ，v ，尺) 上的偏序关系， 若( 五，i ) ，( 置，k ) 都是形式背景( u , v , r y g 惭属性概念，则 ( x l ，x ) a ( 置，匕) = ( 五n 五，( 五o 五) o ) = ( 五o 五，( ko 匕) ) ( 2 8 ) ( 五，墨) v ( 五，五) = “u 艺) o ，x u 艺) = ( ( 五u 五) 如，誓u s ) ( 2 9 ) 从定义2 3 和性质i i i ) 、i v ) n - i t 正( x io 五，( xa y e ) o o ) 和( ( 五u 五) 。0 ，xu y 0 也都是 面向属性概念，从而知l ( u ，v ，r ) 是格，且是完备格，称为面向属性概念格 例题2 1 针对表1 给出形式背景缈，y ，r ) ，其中u = l ，2 ，3 ，4 ， y = a , b ，c ，d ，e 为了表述方便用1 2 3 表示对象集 1 2 3 ，用曲表示属性集 口6 ) 给 出其面向对象与面向属性概念格如图1 和图2 所示 表1 形式背景( 【厂，y ，r ) ( 1 2 4 ，a b c e )( 13 ，d e ) r 、l ( 24 ，c )( 1 ，p ) ( d ，1 2 i ) 夕弋 0 3 讲l i 弋夕 ( f 2 j ，g ) 图1 形式背景( u ，y ，尺) 的面向对象概念格图2 形式背景( u ，l r ) 的面向属性概念格 7 1 2 3 第三章形式背景合成与分解的面向对象概念格生成 第三章形式背景合成与分解的面向对象概念格生成 本章主要研究了形式背景合成与分解的面向对象概念格生成方法，给出两个 形式背景合成时面向对象概念格生成方法，以及原形式背景分解时子形式背景的 面向对象概念格生成情况，并给出相应的理论证明 3 1 横向合成形式背景的面向对象概念格生成 本节主要解决了在对象集相同属性集不同时，形式背景横向合成的面向对象 概念格生成 定义3 1 设( u 乃皿1 ) 和( u 圪鼻2 ) 是两个形式背景，称形式背景( u 咄) 是由形 式背景( 以k 皿1 ) 和( u 圪皿2 ) 合成的，若满足v = 巧u k ，r = 墨u 恐当kn 匕时， 砂kn 匕，墨y = 足y 为了简化表述，本文分别用三、三l 、三2 表示形式背景( 以啪) 、( 以n 水1 ) 和 ( u , v 2 , r 2 ) 的面向对象概念格，其中的近似算子分别用口，0 、口l ，0 1 、f 1 2 ，0 2 来标 记则有如下的引理： 引理3 1 设形式背景( 以础) 是由形式背景( u 巧皿1 ) 和( u 圪皿2 ) 合成的，则 v x u ，y v ， 1 ) f = u 舻2 ，其中，f 1 = fnf , ，f 2 = fn 匕 2 )y o = ( y f l o 。u ( y n v 2 ) 。，并且v l ，sk ，p = ，i = 1 ，2 证明：1 ) 由( 2 1 ) 式可得 x o = y v i r y c _ r = y v l ( & y o 疋y ) x ) = y v l & y x u y v l p 、2 y c _ x ) = y k i 墨y s x ) u y 匕i r 2 y c _ x ) = f 1u , f f 2 2 )y o = nk ) ou ( r n 圪) o ，显然，只需证明v y ck ，p = p ，i = l ，2 v 1 _ cv , ，由( 2 4 ) 式可得p = u 砂= u 皑y u r y ) = u 墨y 1 同理可证 y e yy e y y e y p = y 0 2 定理3 1 设形式背景( 以唧) 是由形式背景( u 巧皿1 ) 和( 配圪愚) 合成的， 锻u ，若( x ，p ) el ( u ，v ，r ) 当且仅当x = f 1 们u f 2 眈 证明：j ：拟u ，若( x ，x 口) el ( u ，v ，r ) 则x = f o ，由引理1 可得 8 西北大学硕士学位论文 x = f 。= ( f 1 u f 2 ) o = p u p 2 0 = p ”u p 2 蛇 仁：若x = p u p 2 眈，由引理1 可得x = p m lu x 0 2 们= ( p 1u f 2 ) o = 掣。又因为( f 。，p ) 是个面向对象概念，所以( x ，f ) z ( u ，v ，r ) 定理3 2 设形式背景( u 啪) 是由形式背景( v ，v i , r i ) 和( u , v 2 , r 2 ) 合成的， v x cu ，若( x ，f ) 三，则毯厶，五厶，使得x = x iu 五其中用l l u 和 三2 u 分别表示面向对象概念格厶和三2 的所有面向对象概念外延的集合 证明：若( x ，f ) l ，由定理3 1 可知x = f ”1u p 2 眈，因为 ( f 1 0 1f 1 ) 厶，( x 0 2 0 2 2 ) 乞，所以p 1 厶【，f 2 0 2 令五= f 1 0 1 ， 墨= p 2 铊，则可证x = 墨u 墨 定理3 3 设形式背景( u 咄) 是由形式背景( u , v b r l ) 和( u y 2 , r 2 ) 合成的，若 v x i 厶u ，x 2l 2 【，则正u x 2 岛 证明：设五厶u ，x 2l 2 u ，则由定理3 1 和性质i i ) 可知墨= 研1 0 1 矸2 镗s 五， 所以五= 研”1u 矸2 蛇毛，同理可证五毛，因此墨u 五毛得证 由定理3 2 、3 3 可得，合成形式背景( 以哪) 中的所有面向对象概念的外延集， 可由形式背景( 以“皿1 ) 和( 以圪皿2 ) 的面向对象概念的外延集中的元素作并运算获 得 获得合成背景( 以啪) 的所有面向对象概念的外延集后，就可获得相应面向对 象概念的内涵集，即获得了合成形式背景的所有面向对象概念，进而可以构建出 合成背景的面向对象概念格 定理3 4 设形式背景( 以耻) 是由形式背景( u , v l 皿o 和( u , v 2 , r 2 ) 合成的，用 厶，厶分别表示形式背景( 以巧皿1 ) 和( 配圪皿2 ) 的面向对象概念格，则三= ( 五u 五， ( 五u 五) 口) l v ( 墨，誓) 厶，( 五，e ) 厶) 把定理3 4 的结论推广到多个形式背景的合成，则有如下结论： 定理3 5 设形式背景( 以嘲) 是由形式背景缈，k ，r ) ( f = 1 ，2 ，胛) 合成的，记 上l ，三2 ，厶分别是形式背景( u n 皿1 ) ，( u , v 2 , r 2 ) ，( 以尺疗) 的面向对象 概念格，则三= ( 五u u 以，( 五u u 以) 口) lv ( 五，) 厶，( 以，k ) 厶) 3 2 纵向合成形式背景的面向对象概念格生成 上一节研究了对象集相同属性集不同时形式背景合成的面向对象概念格生 成下面研究属性集相同对象集不同时形式背景合成的面向对象概念格生成 9 第三章形式背景合成与分解的面向对象概念格生成 定义3 2 设( 矾，鼬1 ) 和( u 2 ，v , r 2 ) 是两个形式背景，则称形式背景( u 嘲) 是由 形式背景( 矾，v , r 1 ) 和( u 2 ，v , r 2 ) 合成的，若满足u = uu ，r = 墨u 恐当 己n f 2 j 时，坛un 巩，皿= 以 为了简化表述，还分别用、厶、2 表示形式背景( 以懈) 、( 阴，v , r o 和( 矾，耻2 ) 的面向对象概念格，其近似算子也分别用口，、口l ，1 、口2 ，2 来标记 引理3 2 设形式背景( 以鼬) 是由形式背景( 明，v , r 0 和( u 2 ，f , r 9 合成的，则 v x 冬u ，y v ， 3 ) y 。= y o lu r 他，其中y 0 1 = y on u ，r 0 2 = y on ， 4 ) x o = f 1n p 2 证明：3 ) 由定义可证 4 ) r y e x o ，则r y e _ x ( r y u r 2 y ) c _ x j 墨少量x ，r 2 y c _ x ，从而可知 少1 ，y p 2 ，则少1 n f 2 ，即证p 一1 n p 2 ， 同理可证酽一1nx 0 2 ，所以= x 0 1n x 0 2 定理3 6 设形式背景( u 哪) 是由形式背景( 矾，v , r i ) 和( 踢，v , r 2 ) 合成的，则 v y c _ v ，若( p ，y ) l ( u ，v ，r ) 当且仅当y = y 矧n y o 口2 证明：j ：若( y o ，聊l ( u ，v ，r ) ，可得y = 】，。，由引理3 2 可知y = 】，矧n 严2 ， 仨：若】，：y 伽1n 】，纰，又由引理3 2 得】，锄ny 如2 = y o d ，因为( 】，o ，y o 口) 是 面向对象概念，所以可得( p ，聊l ( u ，v ，r ) ，从而定理得证 定理3 7 设形式背景( u 哪) 是由形式背景( 矾，v , r 1 ) 和( 觇，哪2 ) 合成的， v y c _ v ，若( p ，y ) ，v ，尺) ，则j xe l i ，五厶，使得】，= zn 艺其中厶y ，厶矿分 别表示面向对象概念格厶，厶的所有面向对象概念的内涵集 证明：若( p ，y ) el ( u ，v ，尺) ，由定理3 6 可得y = y 如1n 】，如2 ，又因为 ( y 0 1 ，y 0 1 口1 ) 厶，( 】，0 2 ) y o 加2 ) 厶，由弓i 理3 2 可知】，o 妇1 = ( y 。n u ) d 1 = 】，0 0 1n u 尸1 = 】，o d l ， 同理可证p 2 0 2 = p 2 ，令k = y o 妇1 ，艺= 】，佃2 ，即可证】，= in 艺 定理3 8 设形式背景( u 咄) 是由形式背景( 矾，v , r o 和( 沈，v , r 9 合成的， v r , 厶r ，e 2 r ，贝0kn r , 句( u ，y ，r ) 证明：v 写厶p ，则( x 们，x ) 厶，所以】j ：= 彳皿，由性质i i ) 可得】j i 】_ ；蜘2 ，再 由定理3 6 和定理3 7 的证明可得i = 誓如nr , 伽2 句，同理可证得艺，所以 1 0 西北人学硕士学位论文 可证xn e 句( u ，v ，r ) 由定理3 7 、3 8 可得纵向合成形式背景( 以哪) 中的所有面向对象概念的内涵 集，都可由形式背景( 矾，v , r 0 和( u 2 ，v , 8 2 ) 的面向对象概念的内涵集中的元素作交 运算获得 获得纵向合成形式背景( 以咄) 的所有面向对象概念的内涵集后，再借助可能 近似算子作运算即可获得相应面向对象概念的外延集，从而就可获得纵向合 成形式背景的所有面向对象概念，进而构建出纵向合成形式背景的面向对象概念 格 定理3 9 设形式背景( u 哪) 是由形式背景( 矾，v 3 2 1 ) 和( u 2 ，v , r 2 ) 合成的，用 厶，厶分别表示形式背景( 矾，v , r 0 和( u 2 ，幽2 ) 的面向对象概念格，则l ( u ，v ，r ) = ( ( xn e ) 。，zn 艺) i v ( 五，z ) 厶，( x 2 ，艺) l 2 定理3 9 的结论阐述了两个形式背景纵向合成时面向对象概念格生成，这一 结论还可以推广到有限个形式背景纵向合成时面向对象概念格生成 定理3 1 0 设形式背景( u 咄) 是由形式背景( ，矿，r ) 0 = 1 ，2 ，厅) 合成的，记 厶，厶，厶分别是形式背景( u ，v ，r i ) ( i = 1 ，2 ，以) 的面向对象概念格，则 z ( u ，v ，r ) = ( ( xn 艺n n ) 4 ，kn 艺n n ) iv ( 五，k ) 厶，( 以，k ) 厶) 3 3 横向分解形式背景的面向对象概念格生成 这一节主要研究形式背景横向分解时子形式背景的面向对象概念格生成情 况 定义3 3设( u 哪) 是形式背景，则称形式背景( u n 皿1 ) 和( 以圪凡) 是由形 式背景( u 啪) 分解的，若满足y = ku r , ，r = 墨u 足当knv 2 0 时，易验证 砂kn 屹，蜀y = 恐y 定理3 1 l 设形式背景( 以n 皿1 ) 和( u 圪皿2 ) 是由形式背景( u k r ) 分解的，则 v ( x ，曰) l ，j ( ( b n k ) 甜，b n k ) 厶，其中f = 1 ，2 f f n ： 只需证明( b n 形) 们即可，不妨令i = l ，则由引理3 1 可得 s n v , = fn v , = ( p 1u p 2 ) n k = ( f 1n k ) u ( 一2n 巧) = 1 ，可知( b n k ) 们= 怕1 厶c ，即( f 1 ，妒1 ) 厶，定理 | 导证 定理3 1 2 设形式背景( u n 皿1 ) 和( u , v 2 r 9 是由形式背景( 以哪) 分解的，则 第三章形式背景合成与分解的面向对象概念格生成 v ( 五，且) 厶，3 ( x ，b ) l ，使得蜀= b n v , ，且五= n 巧) 乱 证明： 事实上3 ( x ，b ) 三，使得，b ) = ( 墨u b l 0 2e ) ，因此只需证明 ( 五ub 1 0 2 蜀) 三即可，由引理1 可得五u b , 眈= e 们u 垦铊= 群，可知( 邵，且) l ， 即( 墨u b l 0 2 旦) 定理得证 从定理3 1 1 、3 1 2 可知子形式背景的所有面向对象概念都可从原形式背景中 获得，进而可构建出子形式背景的面向对象概念格，正如下面定理所叙述的： 定理3 1 3 设形式背景( 以v l , r i ) 和( u , v 2 , r 2 ) 是由形式背景( 以啾) 分解的，则 厶= ( ( 曰n 巧) 钟，b n 巧) l v ( z ，曰) ，o = l ，2 ) 定理3 1 3 给出分解成两个子形式背景时面向对象概念格生成，这一结论还 可以推广到分解成有限个子形式背景的情况，正如定理3 1 4 所叙述的： 定理3 1 4 设形式背景( 【厂，巧，墨) ，( u ，匕，足) ，k ，r ) 是由形式背景( 以咄) 分解的，则厶= ( ( b n 形) “，8 n r , ) l v ( x ，b ) 三 ，( f = 1 ，2 ，刀) 3 4 纵向分解形式背景的面向对象概念格生成 这一节研究了形式背景纵向分解时子形式背景的面向对象概念格生成 定义3 4 设( 以啪) 是形式背景，称形式背景( 明，v , r 1 ) 和( u 2 ，v , r 2 ) 是由形式背 景( u , v , r ) 分解的，若满足u = uu v 2 ，r = 蜀u 是当un u 2 g 时，易验证 v x un u 2 ，碣= 啦 定理3 1 5 设形式背景( 矾，v r 1 ) 和( 巩，v , r 2 ) 是由形式背景( u 耻) 分解的，则 v ( x ，b ) l ，3 ( x n u ，( x n ) 口。) 厶，i = 1 , 2 证明： 只需证明( 石n 配) 口厶，即可不妨设i = l ，则由引理3 2 得 x n ( s , = 矿n u = ( b 。1u 矿2 ) f l u , = b 。1 ，所以( x n u ) 口1 = 占佃1 厶y 定理得证 定理3 1 6 设形式背景( 阴，v , r i ) 和( 醍，y r 9 是由形式背景( u 础) 分解的，则 v ( 五，e ) 厶，3 ( x ，b ) l ，使得五= x n u , ，骂= ( x n u ) 证明：事实上，3 ( x ，b ) 工使得( x ，b ) = ( 五，矸2n 且) ，由引理3 2 可知 x , 0 2n 且= 矸2n 矸1 = 矸，又因为( 五，矸) ，所以定理3 1 5 得证 综合定理3 1 4 、3 1 5 可知子形式背景的所有面向对象概念都可从原形式背景 中获得，进而就可构建出子形式背景的面向对象概念格，正如下面定理所述： 定理3 1 7 设形式背景( u i ，v , r 1 ) 和( 醍，v , r 2 ) 是由形式背景( 以咄) 分解的，则 1 2 西北大学硕士学位论文 厶= ( x n g ，( n ) 口) i v ( x ，b ) 三) ，i = 1 ，2 定理3 1 7 给出了原形式背景分解成两个子形式背景时的面向对象概念格生 成情况，这一结果还可以推广到分解成有限个子形式背景的情况，可得如下面定 理： 定理3 1 8 设形式背景( u ，v ，墨) ，( 址，v ，足) ，( u ，v ，咒) 是由形式背景( u 啪) 分 解的，则厶= ( x n g ，( x n 以) 口训v ( x ，b ) 三 ，i = 1 ，2 ，1 例题3 1 表2 给出一个形式背景，y ，月) 是由形式背景，v l l ，墨) 和( u ，v 2 ，r ) 合成的，其中u = 1 ，2 ，3 ，4 ，5 ，6 ) ，v = a , b ，c ，d ，p ，f ，g ，k = a , b ，c ，d ，匕= e , f ，g ， r = 足u 足，为了表述方便，用1 2 3 表示对象集 1 2 3 ，用曲表示属性集 口6 ) 表2 形式背景( 【厂，v ，r ) n b c d e f g 。2，3，蕊翁,ac)(12345,bcd， (123最4