（应用数学专业论文）基于覆盖关系的概念格构造模型.pdf

河南大学研究生硕士学位论文第1 页 摘要 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得 各个领域的数据和信息急剧增加( 信息爆炸) ，同时人类的参与使数据与信息系统 中的不确定性更加显著。如何有效地实现对数据的分析和处理，如何快速地从数 据中提取出隐含的知识，长期以来一直是人工智能领域的研究热点。 概念格( c o n c e p th t t i c e ) ，以其完备的结构和坚实的理论基础成为数据挖掘过 程中的主要模型之一。由于造格是一个繁杂的过程，如何构造概念格成了制约概 念格得到广泛应用的瓶颈。面对这个挑战，各种造格算法随这个难题而产生。目 前已经提出了构造概念格的多种算法，归纳一下可以分为两大类：渐进式造格算法 和批处理的造格算法。目前绝大多数的渐进式算法只适用于单个对象的逐个插入 更新的情况，然而在大多数的数据库中，更新操作往往是同时插入多个对象。为了适 应这种情况，根据概念的覆盖关系，提出了一种新的渐进式概念格构造算法，这种算 法可以一次性地加入一个对象集合，而且在生成概念的以后，能够构造出概念格的 h a s s e 图，从而加快了概念格的构造速度。 在概念格的构造过程中，首先对形式背景进行约简处理，同时记下删除的行 和列，然后把形式背景切分为属性集含有四阶或四阶以下形式背景基的形式，再 次约简形式背景，根据形式背景同构进行子概念格构造，子格构造完成以后，为 了概念格的完整性，重新添加第二次约简的信息，最后合并生成的子概念格，完 成概念格的构造。 实验表明，本文提出的算法模型是可行的，也是非常有效的，且不仅可以使 子概念格得到了重用，同时对于概念格多机处理和形式背景经常变动的情况，具 有很好的灵活性特点。其中，概念格的合并算法在该模型中处于关键的位置，其 性能的优劣直接影响概念格构造的速度。 第l i 页河南大学研究生硕士学位论文 本文的主要贡献如下： ( 1 ) 设计了一种基于覆盖关系的概念格构造算法。这种算法在子概念格合并的 过程中减少了比较的次数，从而提高了造格的工作效率。 ( 2 ) 定义了两个映射函数，并用相关定理证明了嵌套线图和概念格所对应的 h a s s e 图之间的映射关系。 ( 3 ) 设计了一种概念格构造模型，并与c l 【f a 算法和g o d i n 算法进行比较。 关键词：概念格；概念格合并；覆盖；子概念格 河南大学研究生硕士学位论文第1 ii 页 a b s t r a c t n o w a d a y s ，t h es o c i e t yh a l se n t e ：r e d 廿1 ei l l f o n l l a t i o ne r a 1 1 l ec o m p u t e ra n dn e t v 旧r k i 1 1 b m a t i o nt e c h n o l o g yh a v eb e e nd e v e l o p e ds or a p i d l yt l l a td a t aa 1 1 di n f o m l a t i o na r e i n c r e a s i l l gd r a m a t i c a l l y ( i n f o m l a t i o ne x p l o s i o n ) i n a l l f i e l d s ，m e a l l w m l ed a _ t a a 1 1 d i 1 1 】白加喊i o ns y s t e m sb e c o m em o r e 姗c e r t a i nd u et oh 啪觚sp a r t i c i p a t i o n h o wt o e f r e c t i v e l ya c m e v et h ed a t aa n a l y s i sa u l dp r o c e s s i n ga n dq u i c k l yg e ti 埘l p l i c i tk n o w l e d g e h a sl o n gb e e na ni m p o r t a n td i r e c t i o no f a r t i f i c i a li n t e l l i g e n c e c o n c 印tl a t t i c ew i 也c o m p l e t es t r u c t u r ea n ds o l i dt h e o 巧h a sb e e no n eo ft h em a i n m o d e l si nd m 。b e c a u s eb u i l d i n gl 吡i c ei sae x p e n s i v ep r o c e s s ，h o wt oc o n s 仃u c1 a t t i c e b e c o m e sa 伊e a t1 i m i tw i t ha p p l i c a t i o n d u et ot h ec h a l l e n g e ，a l lk i n d so fm e t h o d sb r i n g u p n o w a d a y s t h e r ea r et v 旧m e m o d sf o r b u i l d i n g l a _ t t i c e ：b a t c h a l g o r i m m s a 1 1 d i n c r e m e n t a l a l g o r i t i l n l s t h ee x i s t i n gi n c r e m e n t a la l g o r i t h m sa r eo n l ys u i t a b l ef o rt h e c a s eo fs i n 9 1 eo b j e c ti n s e n i o n so n eb yo n e ，h o w e v e r ，i nm o s td 撕b a l s e s ，t 1 1 eu p d a t e sa r e g r o u p 一埘s e ，i e ，as e to fo b j e c t si st ob ea d d e da tat i m e t os 0 1 v et h i sp r o b l e m ，t t l i sp 印e r p r e s e n t san e wi n c r e m e n t a la l g o r i t f o rb u i l d i n gc o n c e p t1 a t t i c eb a s e do nc o v e r r e l a t i o n ，t l l i sa l g o r i t h mi ss u i t a b l ef o rm e c a l s eo ft h ei n s e r t i o no fas e to fo b je c t si n t on l e c o n t e x t ，a n di tc a i lc o n s t r u c tt h eh a s s ed ia j f 锄o ft ：h ec o n c e p tl a 仕i c e w m l eg e n e 均t i n g t h ec o n c 印t f i n a l l y ，t 1 1 ee x p e r i m e l l t a lp r o v et h a tt h em o t h e di sc o l l r e c ta i l dq u i c k d u r i n gc o n 鲫m c t i n gl a n i c e s ，w ed e a lw i t ht h ef o m a lc o n t e x t w ef k s t l yr e d u c et h e f o m l a lc o n t e x ta n dd e l e t eu n w a m e dr o w sa 1 1 dc o l u m n s ，a t l es 锄et i m ew r i t ed o w nt h e i n f o 珊a t i o na b o u tw h a tw ed oj u s tn o w a r e rt h ec o n t e x ti sr e d u c e d ，i ti sp a r t i t i o n e d w i t ht h ef o u r mo r d e rc o n t e x tk e m e l ( o ru n d e ri t ) a l lt h i n gi sd o n e ，o n c em o r ed e a l 谢t h t h ep a n i t i o n e dc h i l d c o n t e x ta n dc o n s t n l c tc m l d 一1 a n i c e sa c c o r d i n gt 0i s o m o q 灿c r e l a t i o n gb e t w e e nt h e m i no r d e rt ot h ec 1 1 i l d l a n i c e sc o m p l e t e ，t h ed e l e t e di i l f o 肌a t i o n m u s t b ea d d e d a tl a s tt h ec l l i l d - l 眦i c e sa r e 砌t e da n d b u i l d 钍1 ec o m p l e t el 甜i c e a c c o r d i n gt ot h er e s u l t s o ft h ee x p e r i m e n t s ，t h i sa l g o r i t h mi s v e 巧c o r r e c ta i l d e f f i c a c i o u s b e c a u s ei tu s et h ee x i s t e di n f o m l a t i o na n da d o p tt om a i l yp r o c e s s e s ，也e m e t h o di ss m a r t t h ek e yo p e r a t i o no ft h em e m o di sa s s e b l y i n gm ec 1 1 i l d l a t t i c e s ，w l l i c h d e c i d et h ea l g o r i t l l mi sg o o do rn o t t h em a i nc o n t r i b u t i o n so fm i sp a p e ri 1 1 c l u d e ， ( 1 ) t h ep 印e rg i v eaa l g o r i t h mf o rc o n s t n j c t i o nl a t t i c eb a s e do nc o v e rr e l a t i o n 。n s 第1v 页河南大学研究生硕士学位论文 m e r i ti s 也a tm ea l g o r i m mr e d u c et h en 锄b e ro fc o m p a r e 锄0 n gb u i l d i n gj 戤i c e ，s ot h a t i ta d v a i l c e st h ee m c i e n c y ( 2 ) f r o mm ep o i n to fb u i l d i i l g1 a n i c e ，w og i v et 、) ，of h n c i o n sa i l ds o m ep r o p o s i t i o n s p r 0 v em en l d c a i lb et 嫩s l a t ei n t on l eh 瓠s ed i a g 捌阻 ( 3 ) t h ep 印e rg i v eam o d e lf o rc o n s t m c t i o nl a n i c eb a s e do nc o v e rr e l a t i o n ，a n d c o m p a r e w i t ht h ec l i f - aa l g o r i t h ma l l dg o d i na l g o r i t h m k e ) 僻o r d s ：c o n c e ml a ：t t i c e ；u 1 1 i o n ；c o v e r ；c h i l d - l a t t i c e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学住申请。本人郑重声明：所呈交的学住论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过酌研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 签名：二穿二二乳 ，2 移d g 卑月，目 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 甄质文 本和电子文本) 雕供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目舌匀，可以采取影印、缩即、扫描和拷贝等复制手 段保存、汇编学位论文( 氟质文本和电子文本) 。 ( 涉及保密内各妁学位论文在解密后适用本授权书) 1 1，e 学位获得者( 学位论文作者) 签名：娄二益 2 0d 学位论文指导教师釜名： 2 0 白年6 月f 厶日 河南大学研究生硕士学位论文第1 页 第1 章绪论 自德国的w i l l e r 教授提出了形式概念分析【l 】的概念以后，形式概念分析就成 了数学家研究的对象，成了他们分析问题的工具之一。在哲学中，概念被理解为 由外延和内涵两个部分所组成的思想单元。形式概念分析反映了概念的哲学理解， 并被用于概念的发现、排序和显示。而概念格作为其核心的数据结构，描述了对 象和特征之间的联系，表明了概念之间的泛化和例化关系，相应的h a s s e 图实现了 对数据的可视化。目前形式概念分析已经在知识发现【2 j 、机器学习、软件工程、信 息检索【3 】等诸多领域得到了广泛的应用。概念格作为形式概念分析中核心的数据结 构，它的构造速度的快慢成为制约其应用的瓶颈。 本章主要介绍了以下几方面，概念格产生的知识背景；概念格研究的内容及 其现状分析；本论文的课题来源及所要做的主要工作；最后简单介绍了本论文内 容的安排。 1 1 概念格产生的知识背景 概念是人们对事物的共同特点抽象、概括而形成的对某一事物的定义。在哲 学中，概念被定义为思维的基本形式之一，它反映了客观事物的一般的、本质的 特性，由外延和内涵两个部分所组成的思想单元。由于概念是思维的基本单位， 因此基于对概念的研究成为人工智能的一个重要组成部分。在知识表示、知识管 理、机器学习、专家系统等不同的领域，研究者们从不同的角度和观点来分析概 念，形成了对概念的不同形式化描述方法。 形式概念分析大约诞生于二十世纪八十年代，当时位于德国的d 鲫 i l 删t 【lj 的 研究小组开始系统的研究和发展一种基于格理论的应用软件。形式概念分析是一 种对数据进行分析的工具或者方法，特别是可以对给定的信息进行分析和处理。 而数据应该是从人类有意义的可以理解的思维单位概念中抽取而形成的形式 化的单元。形式化表明的是所处理的数据是形式化的数学实体，不必和人类思维 中的概念完全相同，它同时也指出形式概念分析处理的基本数据形式是形式背景， 形式背景是人类背景知识中的一小部分。d 撇渤d t 小组的研究显然在形式概念分 析的诞生及应用过程中起到了重大的作用。他们首先把种种可能性系统地详细阐 述为一种数据分析方法，并且进行试验，进一步开发许多应用。该工作成功的决 定性因素存在于背景的形式化和把“概念”作为外延和内涵实体的解释。 概念格来源于对形式概念的分析。概念格( c o n c 印tl a t t i c e ) ，也称为g a l o i s 第2 页河南大学研究生硕士学位论文 格f ，是由德国的w i i l e 教授于1 9 8 2 年作为一种数学理论首先提出的【4 】，用于概念 的发现、排序和显示【5 1 ，他将哲学的概念进行数学化的描述，实现了概念的一种形 式化描述方法。概念格理论是形式概念分析理论的核心数据结构，也是知识发现 和数据分析的有力数学工具。由于概念格有良好的数学性质和适合批处理【6 儿j 等特 点，概念格对于解决并行分布式数据挖掘中存在的数据的分布式存储与并行处理 问题，可以说是非常理想的工具。因此对概念格模型【8 j 的研究具有很重要的理论意 义。 1 2 概念格研究范围及现状分析 基于b i 舳o f f 对格理论的贡献，德国的晰1 l e 教授在1 9 8 2 年作为一种数学理论 首先引入了概念格( c o n c e p tl a n i c e ) o7 1 ，奠定了形式概念分析的理论基础，将哲学的 概念进行数学化的描述，实现了概念的一种形式化描述方法。概念格理论是形式 概念分析理论的核心数据结构，被认为是知识发现和数据分析的有力数学工具。 形式概念分析与概念格主要包括以下几个方面的内容： 一、基础理论，研究概念的形式化描述和定义、定理、特征等。是形式概念 分析的理论基础。 二、概念格的形成方法，主要关注概念格快速且有效的构造，目前国内外已 经提供了多种概念格的快速构造算法，概念格的构造在形式概念分析中占有十分 重要的地位，是概念格理论实践和概念格应用的基础。 三、概念格的可视化，主要研究如何有效地显示概念格的结构，目前国外已 经有不少相关方面的研究，但国内相关的研究还很少。在文献 4 2 设计了概念格的 三位表示形式。 四、概念格的应用，主要研究基于概念格的知识表示、规则发现等各种问题， 将概念格应用于知识发现和软件工程领域。 1 2 1 基础理论 研究概念的形式化描述和定义、定理、特征等，是形式概念分析的理论基础， 目前仍有研究者从事这方面的工作。 对形式概念分析做了全面阐述的第一部出版物是w i l l e 教授的r e s t r u c t u i _ i i l g l a t t i c et h e o r y 【4 1 。这部文献利用了b i r k h o f f 格理论的结论所提供的数学可能性进行 数据分析，并且已经包含了许多在本文中提及的思想，包括关于概念格基本定理 的证明。 河南大学研究生硕士学位论文第3 页 作为形式概念分析的重要理论基础，b m 【h 0 丘的格理论诞生的更早。1 9 4 0 年出 版的b i 拙。圩关于格理论的著作( l 稚i c et l l e o f y ) 第一版【9 】中明确提到了关联关系( 如 对象属性关系) 的解释，并解释和说明了如何从一个二维表中来构造完全的格结 构。由于新的应用和发展的需要，形式概念分析在b r 蛐。行的格理论上作了进一步 的扩展和更深入的研究。即使不考虑实际的应用，形式概念分析的提出也引起了 研究者的很大兴趣，由此形式概念分析从应用的角度开始走向理论的形式化研究。 b a r b “1 0 】中也有值得关注的研究，也可参见ba r _ b u t & m o n j a r d “1 0 】。 1 2 2 概念格的研究现状 概念格的构造是f c a 的中心任务之一。到目前为止，国内外研究人员提出了 多种概念格构造算法，主要包括批处理算法和渐进式算法两大类。批处理算法的 思想是首先生成所有概念，然后根据它们之间的直接前驱一后继关系生成边，完 成概念格的构造。这类算法包括b o r d a t 算法【1 1 】、o s h a m 算法【1 2 】、c h e i n 算法【1 2 】、 g a l l t e r 算、法【圯】、n o 埘n e 算法【6 】和并行造格算法p a r a l l e l n e x t c l o s u r e 【1 3 】等。渐进式 算法的思想首先初始化概念格为空，将当前要插入的对象的内涵集和现有格中所 有形式概念的内涵集作交运算，根据结果采取相应的处理。典型的算法有g o d i n 算法f 1 4 】、c a p i n e t o 算法f 1 5 】和t b h o 的算、法【m j 。国内研究人员对上述有些算法 也做了一些改进，例如改进了的b o r d a t 算法用于挖掘关联规则1 4 3 】【5 3 j 、扩展概念格 的渐进式构造算法j 、基于索引树的概念格渐进式构造算法【4 7 】和概念格构造算法 的改进1 4 纠、概念格的合并算法【1 7 】等。 然而，以上各种算法都存在一个共同的问题，即它们都是研究如何根据形式 背景构造概念格，而没有研究形式背景之间、概念格之间的关系，更没有深入研 究如何利用这种关系有效地获取概念格。本文就是结合形式背景之间的关系，在 导师及师兄师姐思路的基础上，利用四阶以下的形式背景同构造格，然后用本文 提出的算法合并这些子格。最后形成当前形式背景下对应的概念格。对于目前典 型概念格的构造算法，将在第二章阐述，并作简单分析。 1 2 3 概念格的可视化 概念格的可视化主要研究概念格空间结构的展示形式问题，通过格结构可视 化可以使人们更加直观的看到它的空间结构。目前国外已经有不少相关方面的研 究，但国内相关的研究还很少。 w i l l e 在1 9 9 3 年发表的论文 1 8 中这样解释：格是用于进行数据分析的，而不 第4 页河南大学研究生硕士学位论文 是仅限于一种数学描述，格中蕴含了很多意义。因此，将格用图形表示出来不仅 仅是反映一种数学结构，而且是给出了一种有多种意义的数据表示形式或表示方 法。由此可见概念格的可视化也是当前对概念格研究的重要内容。概念格的可视 化给人们提供了直观的分析与观察知识单元内在关系的方法，然而概念格的布局 却是相当困难的。在概念格的图形表示中，有两种主要的布局手段，一种是手工 布局，另一种是利用计算机自动布局。手工布局的优点是能够根据人们的审美观 去修改每个节点的位置，从而得到一种高质量的概念格图形。然而手工布局费时 费力，效率不高。因此如何利用计算机进行概念格的自动布局成了概念格展示形 式的重点。 充分利用计算机进行自动布局是目前一个主要的研究方向，但是在自动布局 中，最大的困难则是如何尽可能“美观”地显示任意给定的概念格。这方面的成功例 子有：使用n 维格结构i ls 】表示的基于布尔型的概念格，采用链分解得到的实际应 用中进行形式概念分析的可分配概念格等等。 1 2 4 概念格的成功应用 主要研究基于概念格的知识表示、规则发现等各种问题，概念格作为一种形 式化的描述和分析工具，由于其所具有的优良特性，目前在信息检索、软件工程、 知识发现、联机分析处理、数理逻辑等各个领域获得了成功应用，以下做简单介 绍。 ( 1 ) 信息检索： 在信息检索方面，概念格可以作为检索的支撑结构： u 融0 1 1 i l 和n j d a v i e s 在文献 1 8 】中提出了种基于概念格结构的网上智能查询 机制，企图去分析和揭示各类文档问的内在关联，将其应用于知识管理和信息检 索，实现新知识的获取和己有知识的共享。g o d i n 等在文献【1 9 】中建立了一个概念 格结构的信息检索系统，并将其和其他两种较传统的信息检索系统相比较，得出 结论：基于概念格结构的检索是非常有吸引力的，因为它将主题搜索的良好特性 和浏览器的潜力结合在起。n e u s s 和k e n t 【2 0 】使用概念格进行h l t e m e t 上文档元信息 的自动分类和分析。 ( 2 ) 知识发现 形式概念分析以概念格的形式使数据有机地组织起来，目前有不少研究工作 探讨了从格节点和概念格的层次结构中提取规则【4 3 j ( 铊j 的问题。试验研究表明，基 于概念格的各种规则提取系统是有效的，形式概念分析非常适合发现规则型知识。 以下简介有关文献中的基于格结构的规则提取及相关系统。 河南大学研究生硕士学位论文 第5 页 已知的一些基于概念格的分类学习系统主要有：s a l l a _ 喊开发的r u l e 剐5 心m r 系统【2 1 】和而n j i 、o u a 等设计的l e g a l e 系引2 2 】【2 3 1 。g o d m 等在文献【2 4 】中提出了 从概念格中提取出蕴涵规则的算法。m i s s a o u i 等【2 5 】对文献 2 4 】进行了扩展，提出 了从概念格中提取近似规则的算法。p a s q u i e r 等在文献f 2 6 1 中以已发现的所有频繁 项集作为基础，提出了用于提取确定性关联规则的d u q u e n n e g u i g u e 基，以及用 于近似关联规则的适当基( p r o p e r b a s i s ) 和结构基( s t m c t u r a lb a s i s ) 。 在文献 2 7 中，w i l l e 引入多背景( m u l t i c o m e x t ) 这个概念，并给出了不同形式背 景之间的四种不同的操作。以w i l l e 所提出的多背景为理论依据，文献【2 7 【2 8 研 究了在概念格框架结构下结构化( 复杂) 对象中的概念学习和规则提取。“q u i e r e 等在文献 3 0 中研究了概念格在由标号图( 1 a b e l e d 缪印h ) 描述的实例中的学习。文献 【3 1 】研究了由标号的、递归的树所描述的数据和数据类，定义了一种数据描述的方 法一通用项( g e n t e 衄) 、以及g e n t e r r i l 之间的泛化关系，并且说明了在对象集和通 用项之间存在一个g a l o i s 联接，从而可以应用g a l o i s 格的聚类方法。 ( 3 ) 软件工程： 形式概念分析在软件工程领域，形式概念分析为再工程、软件重用、面向对 象程序设计等领域中某些问题的解决提供了理论支持，并已经取得了一系列的应 用成果。 概念格与面向对象程序设计：g o d i nr 等在文献【1 9 】中还将概念格应用于类层 次( c l a u s s1 1 i e r a r c h y ) 的设计上。s n e i t i n g 等基于概念分析提出了一个用于检测和补救 设计问题的框架结构【3 引。 概念格与软件再工程：l i n d i g 等【3 3 】使用格结构中得到模块结构，以使用格结 构来评估模块候选项之间的内聚度和祸合度。针对配置的再工程问题，。s n e l t i n g 在 文献 3 4 采用概念分析的技术来根据现有的源代码推断出配置结构。 基于概念格的软件重用：文献 3 5 利用概念形成方法以两种方式来支持软件重 用：建立一个导航空间( 概念层次) 来对库中的产品进行组织和检索，以及通过建议 更好的抽象为重用打包活动( r e u s ep a c k a g i n ga c t i v i 够) 提供支持。 ( 4 ) 其他应用 概念格还获得了其它的一些应用，如文献 3 6 通过使用嵌套线图来对概念层次 的任意组合进行可视化，来替代在0 l a p ( 联机分析处理) 中被广泛使用的嵌套图。 w i l l e 在文献 3 7 】中将概念图和形式概念分析结合起来，从而得到了对初等逻辑的一 种形式化，用于对于知识的表示和处理。砌c h a r d sd e b b i e 【3 8 j 利用概念格对硒p p l e d o w nr m e 进行有机的组织；c u l e 的c e m 电子邮件管理系统1 3 川通过将e m a i l 存储 在概念格中，而不是常用的树状结构中，从而在检索电子邮件时获得了吏大的灵 活性；文献 4 0 则将概念格应用于智能帮助系统的领域建模等等，另外概念格在遗传 第6 页河南大学研究生硕士学位论文 学上也有广泛的应用【5 4 】。 1 3 课题的来源和内容的组织 1 3 1 课题的提出 在形式概念分析系统中，随着数据的累积，形式背景库和概念格库将迅速膨胀。 解决此问题并支持大数据量和分布数据源的数据分析应用，是目前面临的一个挑 战。尽管以前提出了各种类型的概念格的渐进式构造算法，但都是对单个对象的 操作。而随着人们研究事物的深入，对象成批出现，这时候对单个对象的添加就 显然满足不了需要，根据这一点，本文提出了基于覆盖的概念格的渐进式构造算 法。这种算法可以一次添加一个对象集。 1 3 2 本文研究的内容及意义 构造概念格的过程实际上是概念聚类的过程。因此，在概念格中，构造概念 格算法具有很重要的地位。概念格是建立在偏序集上的具有完备性的结构。其完 备性主要体现在概念格中不仅表达分类的信息，还表达其它有用的信息，几乎所 有的数据库中的联系都可以表达出来，这和其它的规则求解的方法有所不同。它 可以用来求解分类规则、关联规则和特征规则等。所谓概念格的完备性指的是不 受数据或属性排列次序的影响，不同的构造方法所生成的格形式是唯一的。 概念格所具有的完备性一方面是概念格的优点之一，另一方面即使对于适当 大小的数据，也将产生庞大的格结构。理论上说，概念的节点个数会以形式背景 对象个数和属性个数的指数倍增长。无疑概念格的构造过程十分耗时并且非常关 键。随着数据以空前的速度不断增长，从形式背景构造概念格成为制约概念格应 用的一个瓶颈。从数以万计的数据中快速的构造出概念格，己经越来越成为一种 挑战。从形式概念分析诞生以来截至到目前的二十多年中，国内外许多学者提出 了关于概念格构造的各种各样的模型。但是因为概念格的完备性原因，在时间复 杂度和空间复杂度方面，找出大大优于已有算法的概念格构造算法变得几乎不可 能。同时，随着概念格理论在数据挖掘等领域的应用逐渐广泛，需要处理的数据 也几乎呈爆炸式增长。问题规模的迅速庞大和高效算法研究进展的缓慢，成为概 念格研究应用领域的一个突出的矛盾。 基于以上原因，如何降低从一个大规模、超大规模的形式背景中构造概念格 河南大学研究生硕士学位论文第7 页 的时间复杂度成为目前形式概念分析领域研究的一个重点和难点。近年来随着人 们对概念格的研究提出了这样那样的算法，如国内概念格的横向合并算法【拍】、基 于属性的概念格的构造算法【4 5 l 等，都是用己知的概念于生成格结构中的所有概念 进行比较，从而更新概念格的结构。本文从已知的形式背景基出发，通过比较形 式背景同构来提高造格的速度，即用已知的格结构代替要求的概念格。在概念格 合并的过程中，基于概念的覆盖关系提出了一种概念格的合并算法，这种算法采 用求下级覆盖的形式限定搜索的范围，从而提高了构造概念格的速度。 本文的主要贡献如下： ( 1 ) 设计了一种基于覆盖关系的概念格合并算法。这种合并算法在子概念格合 并的过程中减少了概念之问的比较次数，从而提高了造格的工作效率。 ( 2 ) 定义了两个映射函数，并用相关定理证明了嵌套线图和概念格所对应的 h a s s e 图之间的映射关系。 ( 3 ) 设计了一种概念格构造模型，并与c l i f a 算法h 司和g o d i n 算法h 2 3 进行比 较。 1 3 3 本文内容的组织 本文内容的组织如下： 第l 章主要介绍了形式概念分析产生的背景，以及形式概念分析主要的研究 内容和面临的问题。最后给出了本文的课题来源及所要做的主要工作。 第2 章介绍了概念格的基础知识，给出了两类概念格的构造算法，即批处理 算法和渐进式构造算法，并对两种算法中的经典算法进行简单分析。 第3 章介绍了形式背景的清晰化和标准化以及对形式背景的拆分等信息，同 时给出相应的算法，为第四章的应用提供依据。 第4 章介绍了概念格合并算法的理论支持，提出了两个定义和相关的性质定 理等，做了简单的证明，最后给出了算法。 第5 章是在第4 章的基础上进行实验，验证算法的可行性和有效性，并 c u f a n 5 3 算法和g o d i n 算法n 2 3 进行对比，证明此算法的高效性。 最后是全文的总结，并展望了在未来时间内应当完善的问题。 第8 页河南大学研究生硕士学位论文 第2 章概念格基础知识及典型算法分析 本章首先介绍概念格( c o n c 印tl a t t i c e ) 的相关概念和数学基础；接着介绍已经出 现的两类概念格的建造算法，即批处理算法和渐进式构造算法，然后对这两种算法 里的经典算法进行详细的介绍和讨论。 2 1 概念格的基础知识 形式概念分析的数学基础【1 】是序论( o r d e rt h e o 巧) 及完全格( c o m p l e t ela t t i c e ) 理 论，概念格模型是两者与实际应用结合的产物，这里本文首先给出序论和格论中 的一些基本定义【4 1 1 。关于格和有序集的标准专论主要是b i 曲o f r 的格理论【9 】。某些 概念的表示采用了文献 4 5 中的说法。 2 1 1 序论中的基本定义 定义2 1 设4 是一个集合，如果彳上的一个关系，对于比，y ，z 彳，满足如 下条件： 炽( 自反性) 协，协jx = y ( 反对称性) 跏，皿j 北( 传递性) 则称灭是彳上的一个偏序关系，把它记为“”。序偶( 么，s ) 称为偏序集。 定义2 2设( 彳，) 为偏序集，对于b 剑，如有a 彳，且对曰的任意元素x ， 都满足x 勤，则称口为子集b 的上界。同理，且对召的任意元素x ，都满足日立， 则称口为子集b 的下界。 定义2 3设( 彳，) 为偏序集，b 剑，口为b 的任上界，若对b 的所有上界 y 均有口每，则称口为b 的最小上界( 上确界j 印阳聊删) ，记为s 印倒。同样，若 6 为b 的任一下界，若对b 的所有下界z 均有匹6 ，则称6 为b 的最大下界( 下确 界f ”，i ， “，竹) ，记为f 疗7 r 7 劲。 2 1 2 形式概念分析的理论基础 概念格理论非常丰富，这里主要介绍概念格的基本概念。形式概念分析通常 河南大学研究生硕士学位论文第9 页 由形式背景这一基本概念开始。 定义2 4 一个形式背景被定义为一个三元组织g ，必d ，其中g 是对象集合， m 是属性集合，而，是g 和m 间的二元关系，即延g m ，g 和m 的元素分别被 称为对象域和特征域( 属性域) 。设d g ，d m 则棚( 即( d ，田，) 被读作对象 d 具有特征吠属性回。例如下图2 1 中，g = 1 、2 、3 、4 、5 、6 、7 、8 ) ，肛 a 、b 、 c 、d 、e 、f 、g 、h 、i ) ，是g 与m 间二元关系，例如对象1 具有属性a 、b 、g 。 abcdef g hi 1lll 2l1 1 1 3 1 11l1 411 1 1 1 5l11l 61 111 1 7 1 1l1 8 1 111 图2 1 形式背景示例 定义2 5 在形式背景k 中，在g 的幂集和m 的幂集之间定义如下两个映射厂 和g ： g ：以d ) 2 m m iv d g ，曲 ) 彤材彳：甙m ) 2 o gfv d 必d 掰) 通常称函数厂和g 为g 的幂集尸倒和m 的幂集尸俐之间的g a l o i s 联接。分 别表示“g 中全体对象所共有的属性集”和“同时具有m 中所有属性的对象集” 定义2 6 如果尸f j 矽即印坳上的一个二元组( d ，所) ，满足条件d i 反掰) 及掰i 必d ) ， 则称该二元组为形式背景k 的一个形式概念( 在不引起混淆的情况下简称为概念) ， o 和聊分别为该形式概念的外延( ，酞把，2 f ) 和内涵以，z 纪掰) 。 本文中对于给定的概念c ，其内涵和外延也可以分别用加f g 所幻和腑p 班幻 来表示。k 的所有形式概念的集合被标记为四倒。 傩仞上最重要的结构是由亚概念一超概念关系( 又称为父概念一子概念关 系，或前驱一后继关系) 产生的，其定义如下： 定义2 7 给定形式概念( d l ，聊1 ) 和( d 2 ，聊2 ) ，如果d l d 2 ( 等价于聊2 聊1 ) j 则 形式概念( d 1 ，聊1 ) 是形式概念( d 2 ，垅2 ) 的亚概念( 也称为后继) ，形式概念( d 2 ，历2 ) 是形 式概念( d 】，朋1 ) 的超概念( 也称为前驱) ，记为( d l ，聊1 ) ( d 2 ，m 2 ) 。若概念( d 】，聊1 ) ( d 2 ， 第10 页河南大学研究生硕士学位论文 m 2 ) ，且不存在概念( d 3 ，聊3 ) 使得( d l ，磁1 ) ( d 3 ，磁3 ) ( 0 2 ，朋2 ) ，则称( d l ，聊1 ) 是( d 2 ，功2 ) 的直接子概念，( d 2 ，聊2 ) 是( d 1 ，聊1 ) 的直接超概念，记为( d 1 ，聊1 ) ( d 2 ，聊2 ) 。 父概念一子概念关系是c s 倒上的偏序关系，因为它满足自反性、反对称性和 传递性。通过这个关系，可以得到一个偏序集c s 仞= 作s 匈，g ，因为对于c s 内 任意非空子集s ，i s r 中的任意两个形式概念都有最小上界和最大下界，所以偏序集 倒是一个完全格。 定义2 8 称由集合上的偏序关系诱导的偏序集仰倒，匀为形式背景 k 的概念格，记为三( 目。 对概念格中的任一概念( d ，m ) p ( g