（应用数学专业论文）概念格的生成算法.pdf

摘要 摘要 本文分三部分给出了三种概念格的生成算法第一部分在对象集内引入两个偏序 关系和7 及一种新的交运算n ，来建立改进的对象格，然后通过此对象格产生概念 格第二部分利用矩阵行秩的层次思想提出了一种基于矩阵行秩的概念格生成算法，并 用实例描述了对象和属性之间的概念关系第三部分将有限集上的概念信息粒的定义加 以拓展，并在概念信息粒组成的集合上给出了两个概念信息粒之间的偏序关系，并证明 了概念信息粒组成的集合关于这个偏序关系是完备格 关键词格概念概念格概念信息粒概念信息粒格 a b s 仃a c t a b s t r a c t t h r e ea l g o r i t h m sa r ep r e s e n t e di nd i f f e r e n tt h r e ep a r t si nt h i sd i s s e r t a t i o n t h ef i r s tp a r t b u i l d su pm o d i f i e do b j e c tl a t t i c eb yi n t r o d u c i n gt w op a r t i a lo r d e r i n gr e l a t i o n s ，a n d a n dan e wi n t e r s e c t i o n | l ，f o l l o w e db yg e n e r a t i n gac o n c e p tl a t t i c ew i t ht h em o d i f i e do b je c t l a t t i c e t h es e c o n dp a r tp r e s e n t sa na l g o r i t h mo fg e n e r a t i n gc o n c e p tl a t t i c eu t i l i z i n gl a y e r t h i n k i n go fr o wr a n ko fm a t r i x a tt h es a m et i m e ，i td e s c r i b e st h ec o n c e p tr e l a t i o nb e t w e e n o b j e c t sa n da t t r i b u t e sb ya l le x a m p l e t h ef i n a lp a r te x p a n d st h ed e f i n i t i o no ft h ec o n c e p t i n f o r m a t i o ng r a n u l ei nt h el i m i t e ds e t ，a n df o l l o w e db yp r e s e n t i n gap a r t i a lr e l a t i o nb e t w e e n t w oc o n c e p ti n f o r m a t i o ng r a n u l e si nt h es e to ft h ec o n c e p ti n f o r m a t i o ng r a n u l e s t h e nw e p r o v et h a tt h es e to ft h ec o n c e p ti n f o r m a t i o ng r a n u l e si sac o m p l e t el a t t i c ea b o u tt h ep a r t i a l r e l a t i o n k e yw o r d sl a t t i c e c o n c e p tc o n c e p tl a t t i c e c o n c e p ti n f o r m a t i o ng r a n u l ec o n c e p t i n f o r m a t i o ng r a n u l a rl a t t i c e i l 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢i 作者签名： 扬荔 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密留。 ( 请在以上相应方格内打“4 ) 保护知识产权声明 本人为申请河北大学学位所提挛的题目为( 彘移鲁修物苌成写；毒 ) 的学位论文，是我个人在? 师移午 ) 指导并与导磐合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定： 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：坳 日期：丝! ! 年上月上乙日 作者签名：塑盏日期：盟年l 月卫日 导师签名： 日期： 丘月上之日 第1 章概述 第1 章概述 1 1 课题的发展现状 在计算机与网络信息技术飞速发展的今天，各个领域的信息与数据急剧增加，并且 由于人类的参与使数据与信息中的不确定性更加显著，信息与数据中的关系更加复 杂如何从大量杂乱无章和强干扰的数据中挖掘潜在的、新颖的、正确的、有利的价值 知识，这给智能信息处理提出了严峻的挑战，而这些应用数学问题需要借助于格论来实 现其最重的应用其中，从一个二维表中来构造完全的格结构在b i r k h o f f 的格论中已加 以解释和说明，但是，由于新的目的和发展需要，格论需要进一步的扩展和更深入的研 究，而形式概念分析( f c a ) 1 1j 正是在这种情况下诞生的其首次描述是在1 9 8 1 年关于有 序集合的b a n f f 会议的专题演讲上，而形式概念分析( f c a ) 作为一种数学理论是由德国 的w i l l e 教授【2 】于1 9 8 2 年正式提出来的，它的提出满足了许多应用数学问题要借助于格 论来解决的需要它作为一种强有力的数据挖掘工具，其诞生引起了人工智能工作者的 广范关注，并被用于数据分析、数据挖掘、机器学习以及知识发现【3 钏、信息检索【5 】、信 息过滤【6 1 、软件工程【7 1 等领域在形式概念分析( f c a ) 中，概念和概念格的生成是最基 本的任务前人对概念格的生成主要形成了两类算法：批处理生成算法和渐进式生成算 法批处理算法主要用于在数据量较小或给定的数据集上的概念格的建造批处理生成 概念格的经典算法是l i n d i n g 的l a t t i c e 算法【8 】研究人员经过研究得到了改进的批处理 概念格生成算法1 9 。1 1 1 渐进式算法除了能实现批处理算法的功能外，对一已建成的概念 格，但是概念格的形式背景是动态的数据，当数据变动时需要重新建格，此时渐进式算 法是更有利的算法渐进式生成概念格的经典算法是g o d i n 算法【12 1 研究人员将其改进 生成了改进的渐进式概念格生成算法【1 3 16 1 另外n g u i f o t l 7 1 等提出了创能够建概念格的并 行算法，并且给出了算法的正确性证明 1 2 本文的主要工作 本文给出了三种生成概念格的新方法这三种方法各有特点，对于不同的问题，可 以采用最为适宜的三种方法之一得到所需问题的最佳答案第一种方法是：通过在对象 集内引入两个偏序关系7 和互及一种新的交运算n ，来建立改进的对象格，然后通过此 河北大学理学硕十学位论文 对象格产生概念格此概念格与由通常对象集合的交运算n 产生的概念格相比，其产生 的概念节点不仅包括由通常对象集合的交运算n 产生的概念格的子节点的对象，还包括 产生的新对象适用于形式概念背景较多的情况，且更符合实际建立概念格的需要第 二种方法是：利用矩阵行秩的层次思想提出了一种基于矩阵行秩生成概念格的算法，并 用实例证明了其有效性第三种方法是：将有限集上的概念信息粒的定义加以拓展，并 在概念信息粒组成的集合上给出了两个概念信息粒之间的偏序关系，证明了概念信息粒 组成的集合关于这个偏序关系是完备格，即：概念信息粒格 1 3 本文的组织方式 第2 章为预备知识，主要给出本文涉及的基本知识 第3 章给出了生成概念格的第一种算法，即由对象格产生概念格 第4 章给出了生成概念格的第二种算法，即利用矩阵行秩生成概念格的算法 第5 章将概念信息粒格由有限推广到无限，探索由概念信息粒格产生概念格 第2 章预备知识 第2 章预备知识 为了完成第2 至第4 章定理的证明，本章给出有关格以及概念格的基本知识 定义2 1 【1 ，1 8 】一个形式背景就是一个- - 元n ( g ，m ，) ，这里g 和m 是集合，i 互 g xm 为g 和m 之间的二元关系，g 和m 的元素相应的被称为对象和属性对于g g ， m m ，( g ，删) i “表示对象g 具有属性m ” 定义2 2 i 1 8 】设( g ，m ，) 为一形式背景，对于彳g ，b m ，令 a = ，z mv g a ，( g ，聊) ，) ；b = g gv m m ，( g ，”) i ) 如果a = b ，且b 7 = a ，则称( 么，b ) 为( g ，m ，) 的一个概念此时称彳为( a ，b ) 的外 延，丑为( 彳，b ) 的内涵用p ( a ，m ，i ) 表示( g ，m ，) 的所有概念组成的集合 定义2 3 1 1 , 1 8 】设( g ，m ，) 为一形式背景，( 彳l ，b 1 ) ，( a 2 ，b 2 ) p ( g ，m ，) ，规定( a 1 ，b 1 ) ( a 2 ，b 2 ) a 1 a 2 此时称( a 2 ，b z ) 为( a 1 ，b i ) 的母概念，似t ，b ，) 为( 么2 ，召2 ) 的子概念 定义2 4 【1 9 】每个概念格都可以由一个h a s s e 示图来表示h a s s e 示图的节点表示概 念，边表示两个概念是相邻的对于c ，c 2 p ( o ，m ，歹) ，c i c 2 ，如果不存在 c 3 d ( g ，m ，i ) 使得c 1 c 3 c 2 ，我们称c - ，c 2 是相邻概念c - 称为c 2 的低层相邻概念， c z 称为c 的高层相邻概念 定义2 5 【2 0 】若一个关系满足下边几条性质： ( p 1 )自反性：口日 ( p 2 )反对称性：若口b 且b 口，有口= b ( p 3 ) 传递性：若口b 且b c ，有口c 则称关系为一个偏序关系 定义2 6 刚若一个集合的所有元素都满足定义2 5 中( p 1 ) 一( p 3 ) 称此集合为一个 偏序集 定义2 7 1 2 0 若一个偏序集( 三；) 满足，v a ，b l ，口和b 都有上确# a v b 及下确 界口 6 ，则称( 三；) 为一个格 定义2 8 【2 0 】称格( 三；) 是一个完备格，若对三的任意非空子集么，a 元素的上确界 和下确界都存在 1 河北大学理学硕士学伊论文 定义2 9 2 2 】设( g ，m ，) 为形式背景，若彳b 且b a ，则称( 么，b ) 为概念信息粒， 其中g ，m 为有限集 定理2 1 【1 1o i 发( g ，m ，) 为形式背景，对于4 g ，局m ( j ，) ，则下列关系成立 ( u4 ) = n 彳i ；( u 易) = f 7b j j e dj e j e dj e , i 设( g ，m ，) 为一形式背景，则( p ( g ，m ，n ) 是完备格，其中上下确界由下式给 出 v ，( 4 ，马) = ( ( u4 ) ”，n 马) ，a ，( 4 ，马) = ( n4 ，( u 马) ”) j j j f d | 毛j j e j l e jj e j 定理2 2 【2 0 1 设( p ；) 为一偏序集，x - y h p ，i n f 日存在，那么( 尸；) 为一个格 定理2 3 2 1 1 在定义2 3 中，关系“”可诱导出p ( g ，m ，d 的一个完备格结构，格 中元素满足： ( 彳1 ，b 1 ) v ( 彳2 ，b 2 ) = ( ( b 1r 、b 2 ) ，b 1 n b 2 ) ； ( 彳l ，b 1 ) ( a 2 ，b 2 ) = ( 彳1 厂、a 2 ，( 彳l r 、彳2 ) ) ； 其中( 么，b - ) ，( a 2 ，b 2 ) 为( g ，m ，) 的两个概念称此完备格为( g ，m ，) 的概念格其 中g ，m 为有限集 定理2 4 【1 1 设( g ，m ，) 是一个关系，令么，4 g ，b ，局m ，则 ( i ) a a ，( i ) b b 。， ( i i ) 么l a 2j a 12a 2 ， ( i i ) 7b l b 2j ( b 1 ) 三( b 2 ) ， ( i i i ) a ，_ a ”，( i i i ) b = b ”， ( i v ) ( u4 ) 7 = n 彳j ，( i v ) ( u 马) = 1 7b j j e jj e jj e j乍j 第3 章对象格产生概念格 第3 章对象格产生概念格 根据定理2 1 和定理2 2 ，并采用文献 1 ，1 8 中有关概念格的定义，在对象集内引 入两个偏序关系和及一种新的交运算n 来建立改进的对象格，然后通过此对象格 产生概念格此处只讨论有限的形式背景为了与运算n 7 区分，这里将通常集合的n 运 算称为集合的交运算 3 1 对象格产生概念格 这一节我们首先定义对象集上的偏序关系来建立对象格，然后由对象格建立概念 格 下面通过例子说明由定理2 1 中对象集交运算不适合于某些实际需要 例3 1 设g 为对象集有下列集合组成a 1 = 小麦，蝗虫) ，a 2 = 小麦，蟋蟀) ，a 3 = 玉 米，蟋蟀) ，a 4 = 花生，蝈蝈) ，对应的性质集合分别为s t ，s z ，s ；，s 按照通常 集合的交运算n 对象集的交集只产生两部分，如图3 1 所示 图3 1 但我们看到玉米和小麦同属于单子叶植物，蝗虫和蝈蝈同属于昆虫但上图中 小 麦，蝗虫) 和 花生，蛔蝈) 两个集合没有公共元素为了提高概念格的实用性，在本节 中提出一种改进的概念格生成算法 为了建立对象格，我们作如下定义 定义3 1 设g 为对象集，对于g ，9 2 g ，定义g - ，9 2 间的关系如下： g l 9 2 g l 是9 2 的泛化，或者g - 和9 2 是同一个对象 例如g l = 单子叶植物，9 2 = 小麦，那么单子叶植物是小麦的泛化由定义3 1 可 知g lg9 2 河北大学理学硕+ 学位论文 通过定义3 1 给出的 ，关系，将集合 gg 型g l ，gg9 2 ，且不存在g ，使得g ，g l ，9 7 ，g z ，且g 9 7 ) ，记作g e n ( g l ，9 2 ) 当g ，和9 2 不是同一个对象时，定义g e n ( g l ，9 2 ) 是g ，9 2 低层邻居 当9 1 和9 2 是同一个对象时，g e n ( g l ，9 2 ) = g l = 9 2 = g 当g - 和g z 没有共同的泛化时，g e n ( g l ，9 2 ) = a 根据“关系的定义， ，显然满足：自反性，反对称性，传递性，所以下面定理 成立 定理3 1 定义的g ，g ：间的 ，关系为偏序关系 例3 1 中的对象通过7 关系产生的偏序结构如图3 2 所示 图3 2 定义了两个对象间的偏序关系，接下来我们定义两个对象集之间的关系c ，如下 定义3 2 对于么l ，a 2 g ，a i 7a 2 存在函数：爿1 专彳2 ，对v x a j ，都有 x a 的函数f ：x 哼x 满足x x ，所以彳彳成立所以自 反性成立 如果彳，冬7 彳z 且彳2 7 彳- ，由定义的集合间的关系，只有彳f4 z 所以反对称性 成立 由函数的性质知，如果么，三彳：且彳：彳，则有彳，彳，所以传递性成立 所以7 关系是一个偏序关系 根据彳- n 7 么：的定义知4 l n 彳z 就是彳，与4 z 的下确界，即a 1 a 2 = a n a ： 因为对象集是有限的，由定理2 2 知，由对象集间的7 关系产生的集合构成一个格， 称之为对象格 图3 3 下面我们按照索引顺序将例3 1 中的对象集形成对象格，如图3 3 所示 彳n a 2 = a 。= ( 小麦，昆虫) 彳tn 7a 3 = a b = ( 单子叶植物，昆虫) 彳：n 7a 3 = a 庐 单子叶植物，蟋蟀) 么an a 3 = a b = 单子叶植物，昆虫) 彳n ，a 4 = a d = 被子植物，昆虫) 彳：n a 4 = a e = 被子植物，昆虫) 彳sn a 4 = a d = 被子植物，昆虫) 河北大学理学硕十学位论文 么。n 彳= a d = ( 被子植物，昆虫) 彳an 彳。= 彳d = ( 被子植物，昆虫) 彳。n 7a 4 = a a = ( 被子植物，昆虫) 因为概念格可由对象格唯一确定，所以我们由对象格可以得到概念格按照定义2 1 中的a7 = 聊mv g a ，( g ，所) i ) ，我们可以得到每个对象集合所对应的属性集合，设 例3 1 中的对象集对应的属性集合分别为s ，s 2 ，s s ，s t ，& ，& ，则根据 定义2 4 定义的概念间的相邻关系，其对象格对应的概念格结构如图3 4 所示 图3 4 在概念格的生成过程中，我们用上面定义的n 运算来代替通常集合的交运算，形成 的概念格更具有实用性 3 2 总结 我们看到按照通常集合的交运算n 产生的概念格和由新定义的n 运算产生的概念 格既有区别又有联系利用n 运算产生的概念节点不仅包括按照通常集合的交运算n 产 生的概念格的子节点的对象，还包括新产生的对象在格同构意义下，由通常集合交运 算n 产生的概念格是利用n 运算产生的概念格的子格通常集合交运算n 产生的概念格 中对象集有公共对象的两个概念的交产生的子概念与利用n 运算产生的概念格中对象 集和上述对象集分别相同的两个概念的交产生的子概念对应两个概念格的的最小概念 对应本文由对象格产生概念格的方法与文献 2 3 产生的概念格的方法不同之处在于本 文的方法对对象更多的形式背景更有效，更符合一些实际需要 第4 章利用矩阵行秩生成概念格的一种算法 第4 章利用矩阵行秩生成概念格的一种算法 根据定理2 1 和定理2 3 ，并采用文献 1 ，1 8 中有关概念格的定义，本章利用矩阵行 秩的层次思想提出了一种基于矩阵行秩的概念格生成算法，并用实例描述了对象和属性 之间的概念关系 4 。1 预备知识 在形式背景( g ，m ，) 中，对象g g 和性质删m 的关系要么是( g ，所) i ，要么是 ( g ，m ) 仨i 那么一个有限的形式背景都可以用一个矩阵来表示，如果( g ，聊) i ，在矩 阵中用数字1 表示；如果( g ，t r l ) 萑i ，在矩阵中用数字0 表示 例4 1 表4 1 给出一个形式背景，它可以表示为0 、1 矩阵，如表4 2 所示 。属侔 abcdef g 对囊 110 1101o 2111101o 31ol 0o01 4 l1oo001 5110 0001 6111o0ol 711o101 0 81ol110o 表4 1 11 1 1 1 o oo oo 1o o1 11 表4 2 定义4 1 设( g ，m ，) 为一形式背景，显然它可以看作是一个由0 、1 表示的矩阵， 对于某个属性聊m ，在( g ，m ，) 的矩阵中，如果聊对应的列有，个1 时，则称该属性 的秩为，记为r ( m ) = r 玎= m a x r ( m ) i 聊m ) 称为形式背景的秩 为了第二节定理叙述方便，给出如下定义 定义4 2 设( g ，m ，) 为一形式背景，似l ，b 1 ) ，( 彳2 ，b 2 ) 1 3 ( g ，m ，i ) ，( a i ，b i ) ( 么2 ，b 2 ) 彳，ca 2 此时称( 彳2 ，b 2 ) 为( 么，b 1 ) 的真母概念，( 彳1 ，b t ) 为( 彳2 ，b 2 ) 的真子概念 o o 1 1 1 1 o o 1 1 o 0 o 0 1 o o 0 o o o o 0 1 o 1 o 1 1 1 1 o ，l 1 1 1 l 1 l ，l 1 l 1 l ，工 河北大学理学硕七学何论文 4 2 主要定理及算法 定理4 1 设( g ，m ，) 为一形式背景，对于m m ，r ( m ) = f ，则d ( g ，m ，i ) 中存在一 个概念( 彳，曰) ，使得f a l - f 证明当r ( m ) = t 时恰有f 个g 使得( g ，m ) ，令a = gl ( g ，m ) ，) 由定义2 1 得 a = 朋) 由定理2 4 得 聊) ”= 历) ，从而( 聊) ， m ) ，) 为( g ，m ，) 的概念，其中 l 聊州= i a | - f ，召= 聊 定理4 2 设( g ，m ，) 为一形式背景，p ( g ，m ，) 为( g ，m ，) 的概念格令似，b ) p ( g ，m ，i ) ，则o ，b ) 或者是存在m b ，使得r ( m ) = iai ，且( 么，b ) = ( 聊) ， 聊) ”) ， 或者为( 彳，b ) 的两个真母概念的交集 证明分两种情况完成证明令iai = f 情况1 如果有m b 使得r ( m ) = f ，由定理l 有( 肌) ， 聊) ，) 为概念 由聊b 知v g a ，都有( g ，聊) i ，故有g 聊) 7 ，从而a c _ 聊) 再由 聊) i = iai = ， 知a = 朋 ，故( a ，b ) = ( 脚) 7 ， 朋) ”) 情况2 假设对vm b ，r ( m ) iai 因为( 彳，b ) 为一个概念，v 聊b ，g a 都有( g ，m ) i ，所以彳 聊) ，由情况1 的证明知lah ( 所) i ，所以ac 所) 7 由于n g ，m ，) 为一个完备格，所以口，b ) 必然可 以表示成它的两个真母概念的交集即存在( 么- ，b ) ，( 么：，b z ) 为( 么，b ) 的两个真超概念， ( 彳，b ) = ( a 1 ，召1 ) ( a 2 ，b 2 ) = ( a 1 n 彳2 ，( 彳l n 么2 ) ) 设( g ，m ，) 为一形式背景，由定理4 2 知( g ，吖，) 上的任何概念似，b ) 或者为m 上 的元素生成，或者由n g ，m ，i ) 上的( 彳，b ) 的两个真母概念的交生成由此可以给出概念 格的一个生成算法 4 3 利用矩阵行秩生成概念格的算法 本节主要是利用矩阵行秩的层次思想来构造概念格的生成算法 步骤1 第一层概念：( g ，g7 ) 步骤2 第二层概念：求形式背景( g ，m ，) 的秩力= m a x r ( m ) lm m ) ，并求秩为 刀的概念即找到所有列中有刀个1 的列所对应的属性m ，然后写出概念( 聊) ， 聊) ”) 第4 章利用矩阵行秩生成概念格的一种算法 步骤3按定理4 2 第二种情况计算所有上层概念的交运算，把生成概念按外延包 含元素个数多少进行归类存储；计算小于力的秩最大的概念设其秩为，秩为，的概 念和存储中外延元素个数为，的概念组成概念集合，得到新层概念 步骤4 令z = ，1 ，若，0 ，重复过程否则，执行步骤5 步骤5 最后层次概念( m 7 ，m ) 4 1 节中的例子中，通过表示形式背景的矩阵计算其概念层次如下： 第一层概念：( g ，口) 第二层概念：( 1 2 3 6 8 ，a c ) ，( 2 4 5 6 7 ，a b ) 第三层概念：( 1 2 7 8 ，a d ) ，( 3 4 5 6 ，a g ) 第四层概念：( 1 2 7 ，a d z ) ，( 1 2 8 ，a c d ) ，( 4 5 6 ，a b g ) 第五层概念：( 1 2 ，a c d z ) ，( 2 6 ，a b c ) ，( 2 7 ，a b d z ) ，( 3 6 ，a c g ) 第六层概念：( 2 ，a b c d f ) ，( 6 ，a b c g ) ，( 8 ，a c d e ) 最后一层概念：( 囝，m ) 4 4 结束语 本文是从矩阵的角度出发，利用矩阵行秩和概念对交封闭的特点，提出的一种基于 矩阵行秩的概念格生成算法实例证明该算法是正确的和有效的 河北大学理学硕十学位论文 第5 章概念信息粒格 本章将定义2 9 有限集上的概念信息粒的定义加以拓展，并在概念信息粒组成的集 合上给出了两个概念信息粒之间的偏序关系，并利用定理2 4 证明了概念信息粒组成的 集合关于这个偏序关系是完备格这是对概念信息粒格理论的发展与完善，同时扩充了 概念格理论的研究内容 5 1 预备知识 由概念格的定义，对象集g 和属性集m 不一定必为有限，本节把文献 2 2 中的概 念信息粒的定义从有限推广到无限下面给出相关的定义 定义5 1 对于一个形式背景( g ，m ，) ，且a g ，b m ，若满足彳且b 彳， 则称元素对( 彳，b ) 为一个概念信息粒 定义5 2 形式背景( g ，m ，) 的所有概念信息粒的集合用孵( g ，m ，i ) 表示对于 孵( g ，m ，i ) 中的两个概念信息粒( 彳，b ，) 和( 彳：，b ：) ，如果彳么：( 等价于b ：b - ) ，则 ( 彳，曰) 和( 彳z ，b 2 ) 的关系写成( 彳，b 1 ) ( a z ，b 2 ) 则称( 彳，召- ) 为( 么2 ，b 2 ) 的子概念信息粒， 或者说( 彳z ，b z ) 为( 彳- ，b ) 的母概念信息粒 有了这些准备工作，我们将在下一节完成本章的最主要的定理 5 2 主要定理 由定理2 4 ，得到本节的主要定理 定理5 1 设( g ，m ，i ) 是一关系，则( 孵( g ，m ，n ) 是完备格，其中上下确界由下式给 出： v ，( a j ，局) = ( ( u4 ) 。，n 另) ，a ，( 4 ，另) = ( n4 ，( u 局) ”) j “ j 刮t e a j “ j 刮j e j 证明易证，关系是吸( g ，m ，) 上的偏序由定理2 4 及概念信息粒的定义得： ( ( u 历) 。) 7 = ( u 马) = nb j2na j ，即n4 ( ( u 马) 。) t e dj e jl 1 钏) e lj e ( na j ) 2 ( nb j ) = ( u 易) 。，即( u 马) 。( n4 ) t e jl e dl e dj t ij e j 故( n4 ，( u 历) 。) 孵( g ，m ，i ) 第5 苹概念信息粒格 ( ( u4 ，) ”) = ( u4 ) 7 = n 彳? 2n 局，即n 巧三( ( u4 ) ”) j e jj jj e jj e j j e jj e j ( n 巧) 7 ( na 3 k ( u4 ) ”，即( u4 ) 。( n 巧) j e jj e jj e jj e jj e j 所以( ( u4 ) 。，n 易) 孵( g ，m ，) j e j j e j 显然，( n4 ，( u 岛) ”) 是 ( 4 ，局) i ，j ) 在婀( g ，m ，i ) 中下界下面我们将看到它还 j e jj e j 是 ( 4 ，易) i j j 在孵( g ，m ，) 中的下确界 设( 彳，b ) 是这个集合的任一下界，对所有j j 都有彳西因此，彳n4 ，这得 e j 出( 彳，b ) ( n4 ，( u 马) 。) ，e jj e j 故人( 4 ，马) = ( n4 ，( u 局) ”) j 5 0 j jj $ j 在贸( g ，m ，i ) 中，由于( 彳- ，b i ) ( a 2 ，b 2 ) b 2 b 1 ，在上面的证明中由b 代替彳便 得v ( 4 ，j 5 i ) = ( ( u4 ) ”，n 局) j u j jj e j 故( 孵( g ，m ，) ，) 是完备格，称此格为概念信息粒格 由此定理我们不难得到以下推论 推论5 1 当g 和m 都为有限集合时，( 孵( g ，m ，) ，) 为完备格 推论5 2 将定理中的彳b 且b 么7 特殊化，a7 = b 且b7 = 彳则可以得到 ( 吼( g ，m ，n ) 为概念格 注( 1 ) 推论5 1 的结论与文献 2 2 】在有限集上定义的概念信息粒格一致，所以此定 理是对有限的推广 ( 2 ) 推论5 2 的结论与文献 1 ，1 8 中定义的概念及概念格的相关性质一致所以说此 定理扩展了概念格理论的研究内容，是对概念格理论理论研究的拓展 5 3 总结 我们注意到无限理论是对有限理论的补充和发展，而有限理论是无限理论的基 础然而很多在有限情况下难以完成的证明在无限情况下却很容易证明( 女i 2 4 ，定理 3 1 ) 从而本节的结论即使对概念格理论的研究，也起着一定的不可忽视的作用在 河北大学理学硕十学位论文 文献 2 2 中给出了在有限的情况下，如何由概念信息粒格得到概念格以后的工作就是 在无限情况下，如何由概念信息粒格得到概念格 第6 章参考文献 第6 章结论和展望 本文第2 章在对象集内引入两个偏序关系夕和c ，及一种新的交运算n 7 来建立改进 的对象格，然后通过此对象格产生概念格我们看到按照通常集合的交运算n 产生的概 念格和由新定义的n 7 运算产生的概念格既有区别又有联系利用n 运算产生的概念节 点不仅包括按照通常集合的交运算n 产生的概念格的子节点的对象，还包括新产生的对 象在格同构意义下，由通常集合交运算n 产生的概念格是利用n ，运算产生的概念格的 子格通常集合交运算n 产生的概念格中对象集有公共对象的两个概念的交产生的子概 念与利用n 运算产生的概念格中对象集和上述对象集分别相同的两个概念的交产生的 子概念对应两个概念格的的最小概念对应这种对象格产生概念格的方法，对多对象 的形式背景更有效，更符合一些实际需要 第3 章利用矩阵行秩的层次思想提出了一种基于矩阵行秩的概念格生成算法，并用 实例描述了该算法的有效性 第4 章将有限集上的概念信息粒的定义加以拓展，并在概念信息粒组成的集合上给 出了两个概念信息粒之间的偏序关系，并证明了概念信息粒组成的集合关于这个偏序关 系是完备格这是对概念信息粒格理论的发展与完善，同时扩充了概念格理论的研究内 容且这种将有限推广到无限的方法对很多问题的解决将会起到关键的作用 关于概念格的生成算法很多情况下是在形式背景为有限时成立，以后的工作是研究 在有限的形式背景下如何更有效的生成概念格，以及形式背景为无限时的概念格的生成 方法 河北大学理学硕十学位论文 参考文献 【1 】b g a n t e ra n dr w i l l e f o r m a lc o n c e p ta n a l y s i s ：m a t h e m a t i c a lf o u n d a t i o n s m b e r l i n ：s p r i n g e r - v e r l a g ，19 9 9 【2 】r w i l l e r e s t r u c t u r i n gl a t t i c et h e o r y ：a na p p r o a c hb a s e do nh i e r a r c h i e so fc o n c e p t s 【m 】，i n ：r i v a l ie d s e t s ，d o r d r e c h t b o s t o n ：r e i d e a l ，19 8 2 ：4 4 5 - 4 7 0 【3 】r g o d i na n dr m i s s a o u j a ni n c r e m e n t a lc o n c e p tf o r m a t i o na p p r o a c hf o rl e a r n i n gf r o md a t a b a s e s j t h e o r e t i c a lc o m p u t e rs c i e n c e ，1 9 9 4 ，3 8 7 - 4 1 9 【4 】4g s t u m m e ，r w i l l ea n du w i l l e c o n c e p t u a lk n o w l e d g ed i s c o v e r yi nd a t a b a s e su s i n gf o r m a lc o n c e p t a n a l y s i sm e t h o d s ：p r i n c i p l e so f d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y m b e r l i n ：s p r i n g e r - v e r l a g ， 2 0 0 6 【5 】r j c o l ea n de w e k l u n d a p p l i c a t i o no ff o r m a lc o n c e p ta n a l y s i st oi n f o r m a t i o nr e t r i e v a lu s i n ga h i e r a r c h i c a l l ys t r u c t u r e dt h e s a u r u s h t t p ：c i t e s e e r i s tp s u e d u c o l e 9 6 a p p l i c a t i o nh t m l 6 】p e k l u n da n dr c o l e ak n o w l e d g er e p r e s e n t a t i o nf o ri n f o r m a t i o nf i l t e r i n gu s i n gf o r m a lc o n c e p t a n a l y s i s h t t p ：c i t e s e e r i s tp s u e d u 3 9 6 3 6 4h t m l 7 】g s n e l t i n g s o f t w a r er e e n g i n e e r i n gb a s e do nc o n c e p tl a t t i c e s h t t p ：c i t e s e e r i s tp s u e d u s m e l t i n 9 0 0 s o f f w a r eh t m l 【8 】cl i n d i g f a s tc o n c e p ta n a l y s i s ，a p r i l21 ，2 0 0 2 h t t p ：w w w s t c s u n i - s a a r l a n d d e f l i n d i g p a p e r s l i n d i g f c a - 2 0 0 0 p d f 【9 】j - e b o d a t c a l c u lp r a t i q u e d er e c h e r c dd e ss o u s m a t r i c e s p r e m i e r e s d u n e c o r r e s p o n d e n c e m a t s c i h u m ，19 8 6 2 4 e m ea n n e e ，9 6 ：31 - 4 7 1 0 】b g a n t e r t w ob a s i ca l g o r i t h m si nc o n c e p ta n a l y s i s j 】t e c h n i c a lr e p o r t8 31 ，t e c h n i s c h eh o c h s c h u l e ， d a r m s t d t , g e r m a n y , 19 8 4 【1 1 m c h e i n a l g o r i t h md er e c h e r c h dd e ss o u s - m a t r i c e sp r e m i e r e sd u n em a t r i c e ，b u l l m a t h s o c s c i r s r o u m a n i e1 3 ( 6 1 ) ( 1 9 6 9 ) n o 1 ，2 1 - 2 5 【12 】r g o d i n ，r m i s s a o u ia n dh a l a o u i i n c r e m e n t a lc o n c e p tf o r m a t i o na l g o r i t h m sb a s e do ng a l o i sl a t t i c e j 】c o m p u t a t i o ni n t e l l i g e n c e ，1 9 9 5 ，l1 ( 2 ) ：1 1 7 - 1 3 4 1 3 】l n o u r i n ea n do r a y n a u d af a s ta l g o r i t h mf o rb u i l d i n gl a t t i c e s j i n f o r m a t i o np r o c e s s i n gl e t t e r s ， 1 9 9 9 ，7 1 ( 5 - 6 ) ：1 9 9 2 0 4 1 4 l n o u r i n ea n do r a y n a u d af a s ti n c r e m e n t a la l g o r i t h m f o rb u i l d i n gl a t t i c e s j j o u r n a lo f e x p e r i m e n t a l t h e o r i t i c a la r t i f i c i a li n t e l l i g e n c e ，2 0 0 2 ，1 4 ( 2 - 3 ) ：2 1 7 - 2 2 7 【1 5 】谢志鹏，刘宗田概念格的快速渐进式构造算法 j 计算机学报，2 0 0 2 ，2 5 ( 5 ) ：4 9 0 4 9 6 【1 6 】t b