（运筹学与控制论专业论文）概念格的属性约简及建格算法的研究.pdf

at h e s i si no p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s r e s e a r c ho na t t r i b u t er e d u c t i o na n d c o n s t r u c t i n ga l g o r i t h mo fc o n c e p tl a t t i c e b y l ix i a o x i a s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz h a n gx u e f e n g n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 l， j 1 】 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 ：巴 总。 学位论文作者签名：杏晚霞 日 期：彻& j 、1 3 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 摘要 概念格的属性约简及建格算法的研究 摘要 概念格是根据二元关系建立的一种概念层次结构，它在本质上描述了对象与属性 之间的联系，体现了概念内涵和外延的统一，是数据分析与规则提取的一种有效的工 具。粗糙集理论是一种处理不精确、不确定和模糊数据的新型数学工具，它已能有效 地从数据本身提供的信息中发现有效的、潜在的知识。而概念格与粗糙集之间的关系 也是近年来许多学者关注的焦点，它们的有效结合使得一些算法得到了简化与改进。 本文共分五部分内容，第一部分介绍了研究问题的背景、发展现状，本文的相关 工作及组织结构。第二部分给出了概念格和粗糙集的基本理论以及它们之间的关系， 为概念格的属性约简方法和建格算法的研究奠定了基础。第三部分对基于可辨识矩阵 的概念格属性约简方法进行了分析，给出相应的算法，并提出了一种只依赖于形式背 景本身的属性约简的方法及算法。此算法可以作为建格前的预处理算法。第四部分提 出了基于粗糙集中等价关系的理论来构造概念格的算法，共有三个算法：基于等价类 求概念节点的算法；求概念格中其它节点的算法；构造概念格的算法。在这种算法中 由于等价类的引入节省了寻找概念节点的时间，提高了算法的效率。第五部分对本文 的研究进行总结，并指出了概念格进一步的研究方向。 本文对提出的算法进行了实验测试，并与其它相关算法进行了比较，多次实验表 明本文提出的算法是可行，有效的。 关键词：概念格；粗糙集；等价类；属性约简；算法 i i 串 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho na t t r i b u t er e d u c t i o na n dc o n s t r u c t i n g a l g o r i t h mo fc o n c e p tl a t t i c e a bs t r a c t c o n c e p tl a t t i c ei sac o n c e p th i e r a r c h i c a ls 仃1 l c t u r eb a s e do nb i n a r yr e l a t i o n s i te s s e n t i a l l y d e s c r i b e st h er e l a t i o n sb e t w e e no b j e c t sa n da t t r i b u t e s ，e m b o d i e st h eu n i f i c a t i o no fi n t e n s i o n a n de x t e n s i o no fc o n c e p t s ，a n di sa ne f f e c t i v et o o lo fd a t aa n a l y s i sa n dr u l e e x t r a c t i o n r o u g hs e ti san e wv a l i dm a t h e m a t i c a lt h e o r yd e v e l o p e di nr e c e n ty e a r s ，w h i c hh a st h e a b i l i t yt od e a lw i t hi m p r e c i s e ，u n c e r t a i n ，a n dv a g u ei n f o r m a t i o n i tc a nf i n dv a l i da n d p o t e n t i a l l yu s e f u lk n o w l e d g ei nd a t a t h er e l a t i o nb e t w e e nc o n c e p tl a t t i c ea n dr o u g hs e th a s b e e nf o c u s e db ym a n ys c h o l a r sa n ds o m ea l g o r i t h m sb e c o m ep r e d i g e s t e da n di m p r o v e d o w i n g t ot h e i re f f i c i e n tc o m b i n a t i o n t h et h e s i si s c o m p o s e do ff i v ep a r t s t h ef i r s tp a r ti n t r o d u c e st h eb a c k g r o u n da n d d e v e l o p m e n to ft h er e s e a r c hi s s u ei nt h ep a p e r t h e nt h es e c o n dp a r tp r e s e n t st h et h e s i so f c o n c e p tl a t t i c ea n dr o u g hs e ta n dt h er e l a t i o no ft h e m t h o s ee s t a b l i s ht h ef o u n d a t i o nf o r s t u d y i n go nt h ea t t r i b u t er e d u c t i o na n dc o n s t r u c t i n ga l g o r i t h mo f c o n c e p tl a t t i c e t h et h i r d p a r ta n a l y s e st h ea p p r o a c ho fa t t r i b u t er e d u c t i o no fc o n c e p tl a t t i c eb a s eo nd i s c e m i b l e m a t r i x e sa n dp r e s e n t si t sa l g o r i t h m a n da n o t h e ra p p r o a c hi sp r o p o s e do nt h eb a s i so ff o r m a l c o n t e x t i nt h ef o u r t hp a r t ，ac o n s t r u c t i n gc o n c e p tl a t t i c ea l g o r i t h mb a s e de q u i v a l e n c ec l a s s mt h er o u g hs e ti sp u tf o r w a r d c o m p a r e dw i t ht h ei n c r e m e n t a ls t r u c t u r i n ga l g o r i t h m ，t h i s a l g o r i t h ms a v e sm u c ht i m ea b o u tf i n d i n gc o n c e p tn o d e sa n di sm o r ee f f i c i e n td u et ot h e e q u i v a l e n c ec l a s s t h ef i f t hp a r ts u m m a r i z e st h et h e s i s ，a n dp o i n t so u tt h ed i r e c t i o no f r e s e a r c ho nc o n c e p tl a t t i c ef u r t h e r t h ea l g o r i t h m sw ep r o p o s e da r et e s t e du n d e rd i f f e r e n t e x p e r i m e n ta n dc o m p a r e dw i t h a s s o c i a t e da l g o r i t h m s ag r e a td e a lo fs i m u l a t i o nr e s u l t ss h o w st h a tt h e a l g o r i t h m sa r e f e a s i b l ea n de 仟e c t i v e k e yw o r d s ：c o n c e p tl a t t i c e ；r o u g hs e t ；e q u i v a l e n c ec l a s s ；a t t r i b u t er e d u c t i o n ；a l g o r i t h m j ， -， ， 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i l l 第1 章绪论1 1 1 研究问题的背景及现状l 1 2 本文研究的主要工作3 1 3 本文的组织结构4 第2 章预备知识5 2 1 概念格的基本理论5 2 1 1 概念格的基本定义5 2 1 2 概念格的基本性质7 2 1 3 概念格的几种类型7 2 2 粗糙集的基本概念l l 2 3 概念格与粗糙集的关系1 4 2 4 小结14 第3 章概念格的属性约简1 8 3 1 概念格属性约简的基本概念1 8 3 2 概念格属性约简的方法2 0 3 2 1 基于可辨识矩阵的属性约简方法2 1 3 2 2 基于形式背景的属性约简的方法2 3 3 3 小结2 7 第4 章概念格的构造算法2 8 4 1 经典构造算法的简单描述2 8 4 1 1 批处理算法2 8 4 1 2 渐进式算法2 9 东北大学硕士学位论文 目录 4 1 3 领域知识的添加算法3 0 4 2 基于等价类的概念格构造算法31 4 2 1 基于等价类的概念格构造算法3 5 4 2 2 应用实例3 5 4 2 3 算法的空间复杂度分析3 5 4 3 实验测试_ 。3 7 4 4 小结3 7 第5 章结论与展望4 0 参考文献4 1 致谢4 5 作者攻读硕士学位期间主要成果4 6 v 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究问题的背景及现状 形式概念分析理论，是由德国数学家w i l l e e l 】根据哲学中的概念理论提出的，其中 哲学中的概念被理解为由外延和内涵两部分组成的思想单元，基于此在形式概念分析 中概念的外延被理解为属于这个概念的所有对象的集合，而内涵被认为是所有这些对 象所共同拥有的属性集，这实现了对概念的哲学理解的形式化。概念格，又称g a l o i s 格，是形式概念分析理论中的核心数据结构，它是根据数据集中对象与属性之间的二 元关系建立起来的概念层次结构，这种结构生动而简洁的体现了概念间的泛化和特化 关系。格中的每个节点是一个概念，它由两部分组成：一部分是对象集，另一部分是 属性集，前者表示具有属性集中所有属性的对象，称为概念的外延；后者表示对象集 中的对象具有的所有属性，称为概念的内涵。因此，概念格在本质上描述了对象与属 性之间的关系。概念格是数据分析和规则提取的一种有效工具，从数据集中生成概念 格的过程实际上是一种概念聚类的过程，h a s s e 图实现了对这种数据结构的可视化。作 为数据分析和知识处理的形式化工具，概念格理论已被广泛地应用于软件工程，知识 工程，数据挖掘，信息检索【2 5 】等领域。 作为与概念格理论联系密切的粗糙集理论，是八十年代初由波兰学者z p a w l a k 6 】 首次提出的一种分析数据的数学理论。粗糙集理论是一种新的处理模糊和不确定知识 的软计算工具，是一种重要的数据库知识发现方法。粗糙集的主要优势之一是它不需 要任何预备的或额外的有关数据信息，比如统计学中的概率分布d e i 】叩s t 昏s h a f e r 理论 中的基本概率赋值，或者模糊集理论中的隶属度1 7 。粗糙集理论研究的一个重要内容是 知识约简，即在保持分辨能力不变的条件下通过求取最简属性集，挖掘出信息系统中 潜在的简洁的知识，从而为知识获取提供了一套全新的方法。粗糙集理论具有一些独 特的观点，如知识的粒度性，粗糙集理论认为知识的粒度性是造成使用已有的知识不 能精确地表示某些概念的原因。粗糙集理论的出发点是根据问题的描述对论域进行划 分，通过引入不可分辨关系定义了上、下近似等概念，再有就是新型成员关系，和模 糊集合需要指定成员隶属度不同。在粗糙集中无需人为给元素指定一个隶属度，从而 避免了主观因素的影响，因而成为知识发现、知识获取、机器学习等领域的一种重要 东北大学硕士学位论文 第1 章绪论 研究方法瞵j 。 随着数据库技术和数据库管理系统的广泛应用，全球范围内数据库中的数据量急 剧增大，电子化数据越来越多，信息高速公路的发展和广泛应用使得整个社会变成了 信息化的网络世界，数据量的增长更为迅猛。在用概念格理论处理这些数据时的工作 量是相当大的，并且在这些海量的数据中，很多对于我们是没有用的，因此可以先对 信息系统进行一下预处理，在不改变概念格层次的前提下，对形式背景进行属性约简。 有关形式概念分析中的属性约简的研究工作并不多，文献【7 】通过概念格来研究形式背 景的属性约简，即寻找一个可以决定所有概念格并保持概念格层次结构不变的最小属 性集；本文从形式背景本身出发提出了概念格属性约简的另种方法，这种方法既不 依赖于某种运算，也不依赖于h a s s e 图，从而提高运算效率。 w i l l e 教授在1 9 8 2 年发表的有( 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 n h i e r a r c h i e so f c o n c e p t s ) ) 【1 1 标志着概念格理论的建立，f o r m a lc o n c e p ta n a l y s i s ) ) 1 0 】使概 念格理论进一步成熟，其中讨论了它的完备性等若干性质。随后，又有学者研究了它 的同构性【1 1 】；近几年，又有人提出邻域【1 3 】、闭包【1 4 】、极大和随机概念格网等概念。总 的来说，关于概念格的构造算法做的研究比较多。构造概念格的过程实际上是概念聚 类的过程，对同一批数据，所生成的格也是唯一的。概念格构造算法可以分为两类： 批处理算法和增量算法。批处理算法的思想是首先生成所有概念，然后根据它们之间 的直接前驱后继关系，生成边，完成概念格的构造。根据其构造格的不同方式，批处 理算法又可以分为3 类：从顶向下算法，自底向上算法，枚举算法。从顶向下算法首 先构造格的最上层节点，再逐渐向下，如b o r d a t 算法 1 5 】；o s h a m 算法【1 6 1 ；自底向上 算法首先构造底部的节点，再向上扩展，如c h e i n 算法【1 7 】。枚举算法则是按照一定顺 序枚举格的所有节点，然后再生成格的h a s s e 图，如g a n t e 一1 引，n o u r i n e 算法【1 9 】。增 量算法是把当前要插入的对象和概念格中所有的概念相交，由交的结果把格中节点分 为不变节点、更新节点和新增节点，根据交的结果然后采取不同的方法，如g o d i n 算 法【2 0 1 、c a p i n e t o 算法【2 l 】、t b h o 算法和渐进式生成算法【2 3 2 5 1 。其中，概念格的维 护算法【2 6 2 刀( 主要涉及到对象的插入、删除、修改和属性的增加、删除) 也属于概念格的 增量算法。在概念格理论发展的基础上，吴刚、胡学钢等人对概念格进行了扩展，通 过引入等价内涵定义了扩展概念格( e x t e n d e dc o n c e p tl a t t i c e s ) t 2 8 1 ，并证明扩展概念格和 其对应的一般概念格是同构的；随后又定义了约简概念格( r e d u c e dc o n c e p tl a t t i c e s ) 1 2 9 1 ， 简化了扩展概念格，使其更利于大规模数据库知识发现的应用；约简格中生成的概念 东北大学硕士学位论文 笫1 章绪论 内涵可以从其父概念内涵中获得，对约简概念格进一步简化又提出了相对约简概念格 ( r e l a t i v er e d u c e dc o n c e p tl a t t i c e s ) 蚓；在概念格的内涵中引入等价关系并将其外延量化， 得到了量化概念格( q u a n t i t a t i v ec o n c e p tl a t t i c e ) 3 1 】，利用量化概念格可以更清晰的表示知 识，从而便于挖掘包括关联规则在内的多种规则，并且用户可根据自己的兴趣交互的 挖掘关联规则，不需要计算频繁项目集，因而提高了挖掘规则的效率。本文在提出这 些新概念格的基础上，并对这些概念格的性质、构造做了一定的研究。 以上都是针对单个概念格进行的，随着网络技术尤其是互联网的飞速发展，数据 的分布式存储和并行处理的需求越来越迫切，对多概念格的合并算法也有了一些研究。 其中，李云【3 4 】通过定义概念的横向加运算，提出了一种多概念格的横向合并算法，该 算法适用于对概念格进行分布并行处理。 概念格的研究并不仅仅限于理论方面，在应用上也有一定的发展，如在软件工程、 信息检索、知识发现、数据挖掘、规则提取、聚类分析【3 2 - 3 6 1 等领域。尤其在规则提取 方面的研究较多，如提取关联规则、蕴涵规则、分类规则等。在知识发现领域，概念 格可以从关系数据中提取各种类型的知识，如关联规则、蕴涵规则、分类规则等；在 软件工程领域，概念格可以从类库以及类库的规范说明上构造，从而对类库的可视化 以及类库的重构和优化提供支持；在知识工程领域，概念格可以用于知识库的重新结 构化；在信息检索方面，概念格可以实现对信息的有机组织并过滤掉无用的信息( 如 和粗糙集理论吲相结合对信息系统进行属性约简) 来简化信息表。目前，也有人在 应用概念格进行搜索引擎方面的研究。而且，有人指出概念格将会在生物和生命科学 领域有重大应用。 1 2 本文研究的主要工作 本文所做的工作主要有以下几个方面： 第一，全面地分析了概念格与粗糙集的基础理论，两种非经典的概念格：扩展概 念格与量化概念格的相关概念和性质，以及概念格的几种构造算法：批处理算法，增 量算法，以及利用领域知识的添加算法。 第二，分析了概念格属性约简的理论知识，及其两种方法：基于c t t ”运算法和基于 辨识矩阵法，在此基础上提出了一种基于形式背景本身的属性约简方法。此算法可以 作为建格前的预处理算法。 第三，仔细研究了概念格与粗糙集之间的关系，并基于等价类理论提出了一种寻 3 东北大学硕士学位论文第1 章绪论 找概念节点并构造概念格的算法，并对此算法进行了分析比较。 1 3 本文的组织结构 本文共分为五章，具体结构如下： 第1 章绪论，介绍了研究问题的背景、发展现状、本文的相关研究工作及组织结 构。 第2 章预备知识，给出了概念格和粗糙集的基本理论，以及它们之间的关系，为 概念格的属性约简方法和建格算法的研究奠定了基础。 第3 章概念格的属性约简，深入研究了基于可辨识矩阵的属性约简方法，并提出 了基于形式背景本身的概念格属性约简方法。 第4 章概念格的构造算法，概括了构造概念格的几种经典算法，并提出了基于粗 糙集理论的概念格构造算法。 第5 章结论与展望，对本文的研究进行总结，并提出了进一步的研究内容与方向。 东北大学硕士学位论文第2 章预备知识 第2 章预备知识 2 1 概念格的基本理论 2 1 1 概念格的基本定义 定义2 1 i t l 】龇为一集合，z z ，l 上的一个偏序是一二元关系，满足： ( 1 ) x x ( 自反性) ： ( 2 )x y y z j 咧( 反对称性) ； ( 3 ) x y a y z ：e x z ( 传递性) 。 具有偏序关系的集合三称为偏序集，记为犯，) 。 定义2 1 2 1 1 偏序集犯，) 被称为一个格，若对于任意z ，) ，三，下确：瓢 y 和上确 揪v y 均存在。若对于三的任意子靴，下确界 x 和上确界v x 均存在，则犯，) 称为一个完备格。 定义2 1 3 t 1 1 形式背景k 是一个三元组尽= ( g 必d ，其中庐搪l 瘦，勘) 是对象集， m = m l ，m 2 ，m 一) 是属性集，是g 和m 之间的一个二元关系，即( g ，m ) 1 。 概念格中的形式背景一般是二值的，如表2 1 所示的形式背景，它由4 个对象和6 个属性组成，表中的1 表示相应的对象和属性之间具有二元关系，记坛，m ) = l ，0 表示 相应的对象和属性之间没有二元关系，记地朋) = o 。 表2 1 形式背景 t a b l e2 1f o c a lc o n t e x t 定义2 1 4 f 7 i 设( g 必d 为形式背景，对于对象集么g ，记 a = m miv g a ：g l m ， 5 东北大学硕士学位论文 第2 章预备知识 相应地，对于属性集b m ，记 b = g gv m m ：g l m 。 也就是说彳指对象集彳所具有的所有属性集合，b 指具有属性b 的所有对象的集 合。为了方便起见，我们记德) 髫， m ) - 珑。 规定当矽g 时，矿= m ；当痧m 时，= g 。 定理2 1 1 1 7 1 对于形式背景( g 必d ，v a l 4 2 , a _ mg ，v b l 声2 , b c m , 以下性质成立： ( 1 ) a i 么2 ja 2 a l ，b i c b 2 j8 2 t sb l ； ( 2 ) a a ，b b ； ( 3 ) a = a ，b = b ； ( 4 ) 么b bs a ； ( 5 ) ( 彳lu a 2 ) - 2 彳l n 彳2 ，( 曰lu b 2 ) f 。召l n 岛； ( 6 ) ( 彳ln a 2 ) f2 4 u 彳2 ，( b 1n b 2 ) 2b , u b 2 ； ( 7 ) ( a ”，a ) 和( b ，b ) 都是概念。 定义2 1 5 7 二元组c 主似声) 是形式背景( g m d 的一个概念，如果a = 艿且b t = 爿， 其中a s g ，b 互m 。此时称彳为概念的外延，记为e x t e n t ( c ) ，b 为概念的内涵，记 为i n t e n t ( o 。 定义2 1 6 1 7 1 蜀= 口l 声1 ) ，恐= 似2 声2 ) 是形式背景( g 必d 的两个概念，规定： 五蔓4 4 蜀盈 j i 一 l + 一 此时称噩为蜀的超概念，五称为噩的子概念，“”称为子概念超概念关系( 又称为 泛化- 例化关系，或前驱- 后继关系) 。若不存在不同于恐和蜀的概念x s = ( a 3 声3 ) ，使得 蜀 x s x 2 则称局盖住蜀。 由形式背景2 1 生成的所有概念为( g 1 9 2 9 3 9 4 ，) ，( g i 9 3 ，m 3 ) ，( g 1 9 2 9 4 ，m i ) ，( g l , m l m 3 驰) ， ( 9 2 9 4 ，m l m 2 ) ，( 矽，m l m 2 m s m 4 ) 。 若用l ( g 川) 表示形式背景( g ，m d 的全体概念，则“”是l ( g 朋d 上的偏序关系， 三为偏序集记( l ，) ，它可诱导出l ( g m d 上的一个格结构，可以证明，它是一个完备 6 东北大学硕士学位论文 第2 章预备知识 格，相应的上确界和f 确界定义如卜： 似r 声f ) = ( na ，( ub i ) ”) ， i e t i e ti e t 拒v r ( a b i ) 2 ( ( 望彳；) ”，g ， 其中似f 鳓三( g 彤d ，t 是指标集，此完备格称为形式背景( g 旧的概念格记为 三( g 川d 。由表2 1 的形式背景所得到的概念格的h a s s e 如图2 1 。 ( g ，矽) 幽，疗石、撩川 国l ，m l m 3 m 4 )幽，m l m 2 ) ( 矽，膨) 图2 1 由表2 1 的形式背景生成的概念格的h a s s e 图 f i g2 1t h eh a s s eg r a p ho f c o n c e p t l a t t i c eg e n e r a t e db yt a b l e2 1 2 1 2 概念格的基本性质 设l ( g 彤d 为一个概念格，由定理2 1 1 显然有： 定理2 1 2 【1 0 i 若c ：f ( g 以d ，f 乃则 i n t e n t ( q = ni n t e n t ( g ) ； 拒l i e r e x t e n t ( ac i ) 2ue x t e n t ( c i ) 。 i e l f e ， 注2 1 1 ：概念格的多个概念的上确界的外延并不是简单的对这些概念的外延取并， 下确界的内涵也不是对这些概念的内涵取交。 定理2 1 3 t 1 0 1 设( g 删) 为一形式背景，如果口f 声f ) 三( g 删) ，则 ( 1 ) ( n4 f ) ”= n4 ； f e ，i e r ( 2 ) ( ue ) = n4 。 i e ti e r 证明对( 1 ) ，由定理2 1 1 ( 2 ) ，显然有n4 三( n4 ) ”：对v t t ，有n4 么r ，由定 leti e ri e t 理2 1 1 ( 1 ) 知( 9 4 ) ”g ( 4 ) ”= a r ，所以( 9 4 ) ”( 4 ) ”= 么r ，则( 9 4 ) ”2 9 4 。 7 东北大学硕士学位论文 第2 章预备知识 对( 2 ) ，由定理2 1 l ( 3 ) 和( 5 ) 知( 甚e ) 2 ( 望e ) = n e = n 4 。证毕。 定理2 1 4 设概念格l ( g , m j ) ，则其中的任意概念c l ，c 2 ，c 3 满足 ( 1 ) 交换律q v q = c 2 v c l ，c l a q = c 2 c n ； ( 2 ) 幂等律c 1vc l ，= c l ，c lac l = c l ； ( 3 ) 结合律( c l v q ) v q = c l v ( q vc 3 ) ( c l ac 2 ) a c 3 = q a ( c 2 a g ) ； ( 4 ) 吸收律q v ( c l a c 2 ) = c l ，c 1 a ( q v c 2 ) = c l 。 证明由定理2 1 3 ，( 1 ) ，( 2 ) ，( 4 ) 显然成立，现只证明( 3 ) 。设q = ( a l 声1 ) ，c 2 = 似2 , 8 2 ， c 3 = ( a 3 声3 ) 为任意三个概念，则 ( c i v c 2 ) v c 3 ：( ( b ln b 2 ) , b l n b 2 ) v ( a 3 声3 ) = ( ( ( b ln b 2 ) u 彳3 ) , b l n 历n 召3 ) = ( ( ( 曰in b 2 ) ”u a 3 ) 声l n 晚n b 3 ) = ( ( b 。n b 2n 岛) 乒l n 眈n 曰3 ) c a v ( q vc 3 ) = 似1 月1 ) v ( ( b 2n b 3 ) t , b 2 n b 3 ) = ( ( 4u ( b 2n b 3 ) ) ”, b l n b 2 n b 3 ) = ( ( 彳l u ( b 2nb 3 ) ) 猡ln 岛n b 3 ) = ( ( b 。n 岛n b ) 乒l n 历n 曰3 ) 由概念内涵的唯一性，所以 ( e l vc 2 ) v c 3 - - c l v ( c 2 vc 3 ) 。 同理( c 1 ac 2 ) 人c 3 = c , ( c 2 ag ) 。 注2 1 2 概念格未必满足分配律和模律，并且，很显然概念格任意一个元素( 即一 个概念) 不一定存在补元。 定理2 1 5 1 1 0 1 若概念格的一个节点c 存在两个或两个以上的直接子节点，设其中 的任意两个直接子节点为c l ，c 2 ，则c i ，c 2 之间不存在父子关系。 证明由格的知识可知，这两个直接子节点c l ，c 2 的上确界为该节点c 。若两个 直接子节点c l ，c 2 之间存在父子关系，则这两个直接子节点的上确界必为其中一个子 节点，与上确界的唯一性相矛盾。 r 东北大学硕士学位论文第2 章预备知识 2 1 3 概念格的几种类型 ( 1 ) 扩展概念格 本节我们介绍扩展概念格的定义及其基本性质。 定义2 1 7 【2 8 】如果b ica 且e 利，则称曰l 为彳的一个等价特征组，简称为等价 组，用e g u ( a ) 表示由a 的所有的等价组组成的等价簇，e q u ( a ) = b i i b l ca 1 5 1 b ! 利) 。 定义2 1 8 【2 8 】称从形式背景( g m d 得到的二元组似固为一个基本概念，其中， 彳p ( d ) ( d 回，曰尸p ) ( d 蚴，并且b e q u ( a ) 。彳和b 分别称为概念的外延和一组 内涵。每一个基本概念描述了一组对象及其所共有的一组特征。称形式背景中的基本 概念c l = ( m ，b 1 ) 和c 2 = 0 , b 2 ) 为两个等价的基本概念，简称等价概念，b l 和曰2 为等价内 涵。等价概念反映了同一概念的不同描述形式。 若一个概念的内涵不存在等价内涵，则称该概念为单一概念。若一个概念的内涵 b l 存在多个等价的内涵历少3 ，, b k ，则称这一概念为多重概念将单一概念和多重概念 统称为扩展概念，简称概念，表示为口， b l , b 2 , - - - 鲰) ) 。特别地，称包含所有对象的概 念为全概念，而空集所对应的概念为空概念。 形式背景睁( d p ，尺) 中有这种等价关系的概念集也构成一个完全格结构，称为扩展 概念格( 简记为e c l ) 。 为了方便，以后在文中使用g c l ( c ) 表示由形式背景k 所产生的概念格，而用 e c l ( c ) 表示由k 所产生的扩展概念格。 性质2 1 1 【2 8 1c 奢l = 似i 岁l = b i l 声1 2 ，l j 1 ) ) ，q 2 = 似2 , b z = b 2 lb z 2 , - , b e 殷) ) 是e c l ( c ) 的两个概念，则q 1 c m 当且仅当g c l ( c ) 中的两个概念c g l = 似i ，ub l f ) 和= ( a 2 ，u 蚴，满足c 6 a _ c m ( i = l ，2 ，尼l ；j = 1 ，2 ，如) 。 性质2 1 2 【2 8 】由形式背景j o ( d p 皿) 所得到的g c l ( c ) 与e c l ( c ) 的概念数相同，并 且两者的概念相对应，即e c l ( c ) 中存在扩展概念似，徊l 声2 ，a ) ) g c l ( c ) 中存在概 念口，u b ) ，其中每个口声i ) ( i _ l ，2 ，助为一个基本概念。 根据性质2 1 和性质2 2 可知，尽管e c l 格与g c l 格表示形式上有所不同，但两 者是同构的，即它们所产生的概念集合及所建立的格结构相一致。 定义2 1 9 f 2 8 1 在概念c - 似步) 中，如果存在b f b ，满足旧f i = 1 ，则称c 为召的初始 0 东北大学硕士学位论文第2 章预备知识 概念，晟为c 的一个初始特征( 或初始内涵) 。如果对c 的两个直接超概念c l = ( a l , b i ) 和q = 似2 ) ，存在磅b ，满足毋钮l u b 2 k ，则称c 为c l 和c 2 的生成概念( 其中b i j b i ， b 2 k b 2 ) ，相应地称局为c 的生成特征( 或生成内涵) 。 定义2 1 1 0 2 8 1 设c 剐i 声l = 徊l l $ 1 2 ，声l 七1