（应用数学专业论文）形式背景同构判定算法研究及其应用.pdf

河南大学硕士研究生学位论文第l 页 摘要 构造概念格是f c a ( f o m a lc o n c e p ta n a l y s i s ) 理论中的一个重要问题。传统 的构造算法均是对于一个给定的形式背景从头构造概念格，而不能利用已有的概 念格。针对该问题，课题组提出了概念格的同构生成方法，所涉及到的一个基本 问题是如何判定两个形式背景是否同构。这也是本文工作的中心任务。 形式背景同构判定与图同构判定属于同一类问题，但不尽相同，因为在造格过 程中不仅需要得出形式背景是否同构的结论，而且如果存在同构还需要求出具体 的映射关系。由于形式背景用矩阵表示，所以我们只关心是用矩阵表示图的一类 同构判定算法。这些算法大致分为两类，一类使用行列交换进行判定，一类利用 图的一些不变量及其它特性进行判定。形式背景同构判定可以通过行列交换进行 判定，本文中实现的“直观算法”就是使用这种思路。但这种方法时间复杂度高， 效率很低。根据图同构的第二类算法，我们也可以利用形式背景的一些不变量进 行初步判断，同时结合行列变换的方法进行判定，基于这个思路，本文提出了“等 价类法”。 等价类同构判定算法的基本思想为：对于形式背景局和局分别按照等重 ( w e i g h t ) 关系进行等重划分，此过程包括两部分对象划分和属性划分。对象 划分在计算每一对象( 行) 的重的基础上，按照等重关系将对象集划分为等价类， 并使得对象等价类按其重的大小排序。为确定形式背景形态上的唯一性，在变换 过程中，始终要保持等价类的有序性。属性划分类似。于是，等重划分后的形式 背景被对象等价类和属性等价类分解为多个子形式背景，这样只须对k l 和岛对应 的子形式背景运用直观算法进行判定。 经过实验证明，等价类算法在时间复杂性和空间复杂性上都优于直观算法，有 效地提高了同构判定的效率，尤其是当形式背景的对象数和属性数增加时，等价 类算法的优越性更加明显。再结合形式背景的分解和约简等手段，为概念格的构 造提供了一种有实用价值的方法，我们将这种方法称为是基于格同构的生成方法。 基于格同构的生成方法的实用价值和性能在i s o f c a ( i s o m o r p h i s mf o m a lc o n c e p t a n a l y s i s ) 系统中得到了验证。 本文的主要贡献如下： ( 1 ) 提出了等价类算法，并通过实验验证了等价类算法的高效性和正确性。 ( 2 ) 提出了基于对象和属性权重不变量的等价关系，实现对形式背景对象集 和属性集的划分。 第1 i 页河南大学硕士研究生学位论文 ( 3 ) 根据图同构行列交换判定思想，实现了形式背景同构判定的直观算法。 ( 4 ) 将等价类算法运用于i s o f c a 原型系统中对盯阶形式背景核的构造和子形 式背景同构判定。该系统的成功运行验证了概念格同构生成方法的可行性，也验 证了等价类算法的实用性。 关键词：形式概念分析，概念格，形式背景，同构 河南大学硕士研究生学位论文 第1 il 页 a b s t r l c t c o n c 印tl a m c ec o 璐缸1 l c t i n gi sac m c i a ip r o b l e mi nt l l et l l e o r yo ff c a ( f o 咖a l c o n c e p ta n a l y s i s ) 1 1 l et m d i t i o i i a la l g o r i 血m su s u a l l yb u i l d al a n i c ed i r e c t l yi nt e n n so f ac o n t c x tw h i l e 吐他yc a n n o tu s ee x i s t i n gi a 仕i c et og e r a t ca wo n e p l l r 试n g 廿l i s p r o b l e m ，也ew o r kt e 枷a r o l l i l do u rs u p e r v i s o rp r o p o s e sam e 山o d o fi s o m o r p h j c g 锄e 删n g ，o fw h i c h e l e m e n t a r yp r o b l e mi sh o w t od e t e 皿i 雎w h e m e rt w 0c o n t e x t s a r ei s o m o r p l l i co rn o t a n dm i si sa l s ot h ec e n h 对m i s s i o no f m i sp a p e l c o i l t e x ti s o m o r p l l i s md e t e c t i o ni sq u i t es i l i l i l 缸t om ew e l l - k n o w np r o b l e mo f 鲫h i s o m o r p h i s m 。t h ed i f f e r e n c eb e t w e e nt h e mi st h 她f o rc o n t e x ti s o r r 旧r p h i s md e t e c t i n g ， t h er e s u l t s 证c l u d en o to n l yt l l ea n s w e ry b so rn o ，b u ta i s ot l l ep a i ro fm 叩si f ac o n t e x t i si s o m o r p h i ct 0a i l o t l l e r o w i n gt ou s i n gm 枷xt oe x p r e s sac o n t e x t ，w ea r eo n l y c o n c e m e dw i mt l l ei s o m o r p h i s md e t e c t i n g 盯m m 地6 c so fg r a p hw 1 1 i c h “p 佗s s c db y m 枷x 1 r t 圮s ea r i m m e t i c sa r em a i n l yd i v i d e di n t ot 、釉k i n d s ：o n ei sd e t e c t i i l gb ym r l k “c h 锄g e ，t h co t l l e rb yi n v a r i 锄t s 锄ds o m eo t i l e r 衄bo ft h eg r a p h t h e d i i ；e c t a r i m m e t i c ，i nt l l i sp a p e ri s 岫i n gt h e 瑚1 l 【e x c l l a n g e y e t ，i t sah i 曲t i m e c o m p l e x i 坝 l a we 伍c i e n c ym e t h o d a c c o r d i n gt o 也el a t t e ri d e a w eu s es o m ei r l v a r i 觚t so fc o n t c x t t oi n a 玉，eap r i m a r y 如t c c t i o n 锄dc o m b i n ew “ht h er a n ke x c h a n g e ，w h i c hw en 黜d “e q 试v a l e md 懿sa r i t l l m e t i c t h ei d e ao ft l l ee q u i v a l e n tc l 船sa l g o r i m m s ，i st 0d i v i d ec o n t e x t s 厨弛dk j a c c o r d i n g t 0 e q u i v a l e mw e i g h t ，w h i c h i n c l u d e st w op a r t s ：o b j e c t sp 删t i o na n d a 船i b u t e sp a r t m o n o b je c _ t sp a r t i t i o ni st od i v i d em eo b j e c t ss c ti n t oe q u i v 缸e mc i 蠲s m e nt 0o r d e rb y 、c i g h to nb 髂i so fa c c o u n t i n gt l l ew e i g h to fe a c ho b j e c t ( r o w ) t o e n s u r ct l l em o d a lu n i q u c n e s so fm ec o n 把x t ，w es l o u l da l w a y sp r e s e r v em eo r d e ro ft l 忙 e q u i v a l e n tc l 船s e s n es 锄et o 啪i b u t c sp 删j t i o n s o ，t 1 1 ec o n t e x ti sd i v i d e di n t om u l t i s u b c o n t e x t s b yo b j e c te q u i v a l e n tc l 孙s a i l da n 曲u t ee q u i v a l e mc l 硒s t h eo n l y s u b s e q u e r l c es t e pi st 0a p p l yd i r c c ta r m 圮t i ct o 也ec o r r e s p o n d i n gs u b c o n t e x t s0 f 局 锄d 尬 t h et e s t sp r o v e dt l l a te q l l i v a l e mc l 船sa r i t l l m e t i co u t g od i r e c ta r i m m e t i ci nb o i l l t 访1 e c 唧l e x i t y a n ds p a c e - c o m p l e x i t ya i l dc n h a n c et h ee m c i e n c yo fi s o m o r p l l i s m d e t e c t i n 舀e s p e c i a l l yw h e i im ec o n t e x th a sl a r g ea t t 曲u t e s 锄do b j e c t s 也ea d v 卸协g e b e c o m e sm o r eo b v b u s c o 血b i n e dw i md e c o m p o s i t i o na n d 砒i o no fc o n t e 融，“i sa 第1 v 页河南大学硕士研究生学位论文 m c t i c a lm 最m so fj a m c cc s 蜘c t i 曲a tj sw 量1 砒w ec a l l e dt 1 1 eb u i j dm c t h o db a d i 枷c ei m o r p h j s m ，t 量l ep e r l b n l l a l l c e 如dp r a 甜c a l i t yv a l u eo fw l l i c hi st c s t i f i c di nt h e i - f c a ( i m r p l l i 锄f o 肌a lc o n c e p ta n a l y s i s ) s y 吼e m t h ei n a i nc o 嘣b 们o n sa r ea sf b l l o 、v s ： ( 1 ) p m p o s i n ga n dc a n y i n go u tt l l ee q u i v a l e n tc l 鼬s 撕t l l m e t i c 锄dp m v e i t sh i g i l 甜- c i e n c y 趴dv a l i d 时b y t e s t s ( 2 ) p u t i n gf o r w a r de q u i v a i e n t 她l a t i o no f w e i g h t i n v 撕a n 乜o f o b j t so r 砌b u t e s 砒l di m p l e m e n tt h ep a n i t i o no f o b j e c t ss e ta r i da t t r i b u t 船s e t ( 3 ) a “删旧i l l gt o 也em o u g h to f m n ke x c h a n g e ，剃i z i n g 也ed i r e c ta l 9 0 1 噎t h mo f c 0 呲e x ti s o m o r p m s md d 删o n ( 4 ) a p p l y i n gm ee q i l i v a l e n tc l 鹊s 撕m m e t i c 抽t ot h ei s o f c as y m - m t oc o 璐t r u c t n 捌呔c o n t e x tc o 坞a n dd c t e c tt 1 1 es u b - c o n t e x t si r n c 卵量l i s m t h es u c c e s s 柚埘m l i l l go f t l l es y g 胁v a i i d a 土e st i l e f 色船i b i l i t y o ft h ci s o m o r p l l i cc 0 咖c t i o no fi a m 粕d p m g t i c a b i l 时o f m ec q u i v 柚e n td 髂sa 1 9 0 r i t h m k e yw o r d s ：f o m l a lc c e p t 锄a l y s i s ；c o n c 印tl a 土t i c e ；f b n l l a lc o n t t m ；i s 啪0 r p ： i i s l l l 关于学位论文独立完成和内容创新的声明 y 9 1 1 1 2 葛 本人向河南大学提出硕士学住酣士学住口申请。本人郑重 声明：所呈交的学住论文是本人独立完成的，对所研究的课题有 新酌见解口角4 造性的见解口。据我所知，除文中加以说明、标注 和致谢的地方外，论文中不包括其他人已经发表或撰写过的研究 成果，也不包括其他人为获得任何教育：科研机构的学位或证书 而使用过的材料。辱我一同工作的同事对本研究所做的任何贡献 均已在论文中作了明确酌说明并表示了谢意。 。 、爹拳轻每菇瑟( 每溪藉交濉耆i 签漕= | t 甏塔鞭u、学德申赫必( 拳镁论文雅考i 墨漕= | 0 黧哆。7 鼍兰j ? 。 毫。：，：一警jj 。7 | 沙蠡牟j j 1 ，月7 峰日 。j 关于学位撼文著作椒馕甩授权书j 本人鲣河南大学审糠等比浪撩案! 礤畿学桎阶士学住口。作为 学位的作者魏本人完全了解并筒意背离大学有关保留、使用学位 论文的要求，即河南大学有衩商周寡时书馆、科研信息机构、数 据收集机构和本校图书馆等提供学位论文( 纸质文本和电子文 本) 以供公众检索、查阅o 、本刈囊权河南大学出于宣扬、展览学 校学术发展和进行学术交流等目的，可以采取影印、缩印、扫描 和拷贝等复制手段保存、汇编学位论文( 氟质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名：噬谚格 y 年6 月f 中日 洼壹：请在相应的口，内划“”。 河南大学硕士研究生学位论文第1 页 第1 章绪论 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学理解，德国的w i l l e r 教授【l 】提出了形式概念分析，用于概念的发现、 排序和显示。在形式概念分析中，概念的外延被理解为属于这个概念的所有对象 的集合，而内涵则被认为是所有这些对象所共有的特征( 或属性) 集，这实现了 对概念的哲学理解的形式化。而概念格作为形式概念分析脚中核心的数据结构，本 质上描述了对象和特征之间的联系，表明了概念之间的泛化与例化关系，其相应 的h 篮图则实现了对数据的可视化。作为序论和格论与实际应用结合的产物，概 念格一直以来被认为是进行数据分析的有力工具。对概念格模型的研究具有很重 要的理论意义删1 4 j 。概念格已成为近年来获得飞速发展的数据分析的有力工具。 1 1 形式概念分析的主要内容及应用 1 1 1 形式概念分析的来源 概念是人类进行思维的最基本的单位是用来组织成为诸如判断、结论等更 为复杂的思想的基础，是人类进行知识表述的一种有效手段，是一个哲学的范畴。 对概念的这种理解源于古希腊哲学，发展于十七世纪的近代学院派，进一步发展 成德国标准，最终成为了世界标准1 5 】。在知识表示、知识管理、机器学习、专家系 统等不同的领域，研究者们从不同的角度和观点来分析概念，形成了对概念的不 同形式化描述方法 形式概念分析大约诞生于二十世纪八十年代，是一种对数据进行分析的工具 或者方法，特别是可以对给定的信息进行调查和处理。而数据应该是从人类有意 义的可以理解的思维单位概念中抽取而形成的形式化的单元。形式化表明的 是所处理的数据是形式化的数学实体，不必和人类思维中的概念完全相同，它同 时也指出形式概念分析处理的基本数据形式是形式背景，形式背景是人类背景知 识中的一小部分。 许多应用数学需要直接借助于格理论来实现其最终的应用。而从一个二维表 中来构造完全的格结构已经在b i m l o 蹦格理论( 1 a c t i c e t 地o r y ) 的第一版中加以解 释和说明。但是由于新的应用目的和发展的需要，b m d l o f 哟格理论需要进一步的 扩展和更深入的研究。即使不考虑实际的应用，形式概念分析的提出也引起了研 第2 页河南大学硕士研究生学位论文 究者的很大兴趣，由此形式概念分析从应用的角度开始走向理论的形式化研究 1 1 2 形式概念分析主要内容 基于b r i l c l l o 耐格理论的贡献，德国的w i l l l e l 5 】教授在1 9 8 2 年作为一种数学理论 首先引入了概念格( c o n c 印ti 枷c e ) ，奠定了形式概念分析的理论基础，将哲学的概 念进行数学化的描述实现了概念的一种形式化描述方法。概念格理论是形式概 念分析理论的核心数据结构，被认为是知识发现和数据分析的有力数学工具。 形式概念分析的研究主要包括以下几个方面的内容： 一、基础理论的研究。研究概念的形式化描述和定义、定理、特征等，是形 式概念分析的理论基础，目前仍有研究者从事这方面的工作。 二、概念格的形成方法研究。主要关注概念格快速且有效的构造，目前国内 外已经提供了多种概念格的快速构造算法，概念格的构造在形式概念分析中占有 十分重要的地位，是概念格理论实践和概念格应用的基础。 三、概念格的应用研究主要研究基于概念格的知识表示、规则发现等各种 问题，将概念格应用于知识发现和软件工程领域。 。 四、概念格的显示。主要研究如何有效地显示概念格的结构，概念格通过h a 滩 图生动和简洁地体现了这些概念之间的泛化和特化关系，但终归不太直观和生动。 概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法目前 国外已经有不少相关方面的研究，但国内相关的研究还很少。概念格及其可视化研 究嘲通过对各种自动布局方式特点的分析，提出了概念格的三维自动布局策略， 对三维空间中的层次布局与层内节点自动布局问题进行探讨并加以实现，较好地 解决了二维布局中格节点横向过度扩张和线段交叉的问题 形式概念分析作为一种形式化的数学方法和人工智能、数据库技术、软件工 程等其它领域的计算机科学有着紧密的联系，但同时又相对独立 1 1 3 概念格模型的应用 概念格作为一种形式化的描述和分析工具，由于其所具有的优良特性，目前 在软件工程、数据挖掘、信息检索等多个领域获得成功应用，以下做简单介绍。 一、应用于软件工程 在软件工程领域，形势概念分析为再工程、软件重用、面向对象程序设计等 领域中某些问题的解决提供了理论支持并已经取得了一系列的应用成果。 g o d i n 和m i n c 踟等在文献【7 】中描述了使用概念格方法从现存软件系统中生成 河南大学硕士研究生学位论文第3 页 和检索摘要的方法，并通过两个软件的重用过程演示了该方法。在文献 8 】中研究 者们还将概念格应用于类层次( c l 骶sh i e r 砌y ) 的设计上。s n e l t i n g g 等在文献【9 】中 采用概念分析技术来根据现有的源代码推断出配置结构，通过对生成的概念格进 行可视化显示，清晰的显示出可能存在的配置结构和性质。s c h m m 等在文献 1 0 】 中设计了一个有效的算法，合并具有相互重叠类型的类继承层次，来导出集成的 继承层次，它是以概念格作为类继承层次的形式化机制。 二、应用于知识发现 概念格的节点体现了概念格内涵和外延的统一，概念格的层次结构是节点间 的一种偏序关系，表明概念的泛化和例化。目前有不少研究工作探讨了从格节点 和概念格的层次结构中提取规则的问题。试验研究表明，基于概念格的各种规则 提取系统是有效的，形式概念分析非常适合发现规则型知识。在知识发现方面， 有不少作者探讨过从格上提取规则的问题，也有作者直接用格节点实例匹配而进 行分类。已知的一些基于概念格的分类学习系统主要有：s a l l 锄i 开发的 r u l e a r n e r 系统【1 1 l ，n j i 、o u a 等设计的l e g a l f 【l2 j 系统等。 三、应用于信息检索 在信息检索方面，概念格可以作为检索的支撑结构： 、 u k r o l l l l 和n j d a “e s 在文献【1 3 】中提出了一种基于概念格结构的网上智能查询 机制，企图去分析和揭示各类文档间的内在关联，将其应用于知识管理和信息检 索，实现新知识的获取和己有知识的共享。g o d i n 等在文献【1 4 】中建立了一个概念 格结构的信息检索系统，并将其和其他两种较传统的信息检索系统相比较，得出 结论：基于概念格结构的检索是非常有吸引力的，因为它将主题搜索的良好特性 和浏览器的潜力结合在一起。n e l l s s 和k - c m 【1 5 】使用概念格进行i m 啪e t 上文档元信息 的自动分类和分析。 1 2 概念格构造方法及存在的问题 在应用概念格的过程中，首先需要解决的是格的构造问题。由于概念格的完 备性，即使对于适当大小的数据，也将会产生庞大的格结构，它的构造过程无疑 是非常耗时的。因此研究概念格生成的高效算法就显得更加迫切。从构造方法的 角度来看，概念格的构造算法按可分为三类：批处理算法、渐进式构造算法和并 行算法。 第4 页河南大学硕士研究生学位论文 1 2 1 批处理算法( b a t c ha i g o r i t h m ) 批处理生成概念格，主要任务是生成所有的格节点( 即形式概念的集合) 以 及建立这些格节点间直接前驱直接后继关系。如果按照步骤完成次序的不同， 算法可以分为两种：一种是任务分割生成模型，首先生成全部的概念集合，然后 再找出这些概念之间的直接前驱，直接后继关系，如g a l i t e r 算法【2 j 、c l 地i n 算法1 1 6 j ： 另一种是任务交叉生成模型，每次生成少量的概念，并将这些概念链接到节点集 合中，如b o r d a t 算法1 1 7 1 。如果根据其构造格的不同方式，算法可以分为三类，即自 顶向下算法、自底向上算法和枚举算法。自顶向下算法首先构造格的最上层节点， 再逐渐往下，例如b o r d a t 算法。自底向上算法则相反，首先构造底部的节点，再向 上扩展。如c h e 洫算法。枚举算法则是按照一定顺序枚举格的所有节点，然后再生 成h 船s e 图。即各节点之间的关系。此类算法如g 她t e r 算法，n o 嘶n e 算法【l q 等。 1 2 2 渐进式构造算法 渐进式构造算法基本思想是：假设形式背景中的前f 个对象已经生成了概念节 点的子集和概念格的子格，当第f + 1 号对象加入时，去更新原有的概念节点子集和 概念格的子格重复这一步骤，直到生成最终的格机构。典型的算法有g 0 d i n 【1 6 】 算法和c a r d i n e t 【1 9 】算法。当然很容易将此策略应用于属性上，可以依据属性而不是 对象来渐进式生成概念格。 另外还有一些改进算法，例如基于索引树的概念格渐进式构造算法【2 0 l ，扩展 概念格的渐进式构造算法【2 “，改进了的b o r d a t 算法挖掘关联规则啕。 在渐进式生成概念格的求解过程中。将当前要插入的对象插入概念格图表中 时，通常需要考虑三个问题： ( 1 ) 所有薪节点的生成； ( 2 ) 避免已有概念节点的重复生成： ( 3 ) h a s 图表的更新。 1 2 3 并行算法 对b o r d a t 。g 锄t c r ( n 取t c l o s u ) ，c h e m ，n o r r i s ，g o d i n 和n o i | r i n e 等这些算法 的实验比较表明：n e x t a o s u 陀算法对大量、密集的数据而言是一个较好的构造算 法但是，问题是在处理海量数据时仍然花费了很多时间。为避免这个问题的一 河南大学硕士研究生学位论文第5 页 种方法是设计并行造格算法。目前有关概念格生成的并行算法0 a r a l l e la 1 8 p 枷姗) 研究不是很多，并行算法通常是以其他算法原理为基础的，在文献【1 9 】中作者根据 b o r d a t 算法的原理，设计了一个并行化的版本，文献【2 3 】介绍了一个新的基于分解 搜索区间的并行造格算法p 缸a l l c l n e x t c l o s u r e ，该算法表现出很好的可扩展性，并 且很容易用于并行和分布式计算。可以预测对于海量数据的概念格的生成和应用 研究，并行算法必然是一个大的趋势。 1 2 4 存在问题 目前的绝大部分概念格构造算法均是对于一个给定的形式背景从头构造概念 格，而由形式背景构造格，理论上说，最坏情况下形式背景对象个数或属性个数 的增长将会导致概念的节点个数的指数倍增长，形式背景规模的大小对造格效率 的影响是巨大的。随着概念格理论在数据挖掘等领域的应用逐渐广泛，需要处理 的数据也几乎呈爆炸式增长，如何从海量数据快速的构造概念格，己经成为一个 亟待解决的问题。如何降低从一个大规模、超大规模的形式背景中构造概念格的 时间复杂度成为目前形式概念分析领域研究的一个重点和难点。 我们希望能跳出传统概念格构造算法的思维模式，提出一个新的概念格构造 方法，通过研究形式背景之间的关系并且利用这些关系快速地生成概念格。 1 3 课题来源及内容组织 1 3 1 本文的课题来源 在形式概念分析系统中，随着数据的累积，形式背景的规模迅速增大，构造 格的工作量将很繁重。为解决此问题并支持大数据量和分布数据源的数据分析应 用，开发一个以概念格为知识视图的数据分析系统具有非常重要的意义。 本文的课题来源于河南省自然科学基金项目“分布式概念格模型和知识发现” ( 0 3 1 1 0 1 1 7 0 0 ) 。该项目的目的是建立并实现分布式的知识模型和计算模型，开发 一个原型系统，支持用户从各种常见的数据源中获取知识视图，并进行浏览和数 据分析。 在本模型中，每一个对象以及它所拥有的属性集被视为一个数据实体。其中多 种数据源被组织成数据实体域( d a t ae n t 时u i v e r s e ，简称实体域) 和数据实体空间 ( d a t ae n t i t ys p e ，简称实体空间) 。实体域包含所有的数据实体，即每个具有属性 第6 页河南大学硕士研究生学位论文 集合的对象都被包含其中。一个实体空间是数据实体的聚类，同一聚类中的数据 实体具有相似的属性，即它们具有至少一个共同的属性。因此，实体域可以被分 成若干实体空间。 模型的工作原理是：首先，系统从数据源建立实体域，通过系统自动提取或 者用户交互的手段，实体域或若干实体空间都可被表示为形式背景。如果必要， 形式背景可被分解成若干适当规模的子形式背景；其次，对于获得的任意一个形 式背景局，系统在形式背景库中检查是否存在与之同构的形式背景，如果存在， 设为恐，则将两者之间的映射存入映射库，将硒添入形式背景库、构造其概念格b ( 蜀) 并存入概念格库，而不必再重新花费时间去构造格；然后，根据用户需求形成 知识视图，这一步主要是利用库中映射和同构格b ( 局) ，同构生成b ( 局) ，然后经过 必要的重构或合并生成完整的知识视图；最后，用户在交互式界面上可以对知识 视图进行浏览或者进行后续处理( 比如规则提取) 。分布式知识模型中的数据库都 是分布的，最终要求模型运行在并行分布计算平台上，以支持各种并行算法。 使用该模型构造概念格快捷，但是要求系统中必须存在同构的形式背景，因 而形式背景的同构判定成为这一方法的核心问题，而对于该问题，国内外相关研 究少，人们关注更多的是它的同类问题图同构判定问题的研究。形式背景的 同构判定是本文所要解决的主要问题。 l - 3 2 本文的内容组织 本文的主要研究内容是试图提出一种形式背景同构判定的高效算法。本文内 容组织如下： 第二章介绍了形式概念分析的部分理论基础，包括形式背景、形式概念、多 值形式背景及其向单值形式背景的转换以及形式背景与概念格的关系等内容。一 第三章介绍了形式背景同构判定的同类问题图同构相关理论和几种判定 方法，以及对形式背景同构判定的理论支持及借鉴意义。 第四章实现了形式背景的直接判定方法，并提出了形式背景同构判定的等价 类算法，阐述了这两种算法的相关理论及实现思路，并通过实验比较、分析这两 种算法。 第五章介绍了基于概念格同构生成的系统i s o f c a 的设计、实现及同构判定在 系统i s o f c a 中的应用。 第六章是全文的总结。对本文的主要研究工作进行简要的阐述，并探讨和展 望了在未来时间内应当完善的问题。 河南大学硕士研究生学位论文第7 页 2 1 引言 第2 章形式背景基础 形式概念分析是对哲学中概念的一种数学处理，是人们组织和分析数据的一 种方法，是将数据及其结构、本质以及依赖关系进行形象化的一种描述。 形式概念分析中形式化表明的是所处理的数据是形式化的数学实体，不必和 人类思维中的概念完全相同，它同时也指出形式概念分析处理的基本数据形式是 形式背景，形式背景是人类背景知识中的一小部分。形式概念分析通常由形式背 景这一基本定义开始。所以了解形式背景相关性质是我们开展下一步工作的基础。 形式概念分析的基本观点与形式背景( f o m a ic o n t e x t ) 和形式概念( f i m l a l c o n c e d t ) 有关。形容词“形式的”( f o n n a l ) 意欲强调这里着重介绍数学概念，这 些数学概念只反映了背景和概念含义的某些方面。然而为了方便，在下面的论述 中我们仅在定义中使用“形式的”一词，其它地方有时省略。如果某处出现c o n t e x t 和c o n c e p t ，则分别代表形式背景和形式概念。 2 2 形式背景与形式概念 概念的含义要依赖于一定范围的背景知识，而背景就是对象及其具有的属性 的集合。任何一个概念都是从背景中提取出来的一个子集，这个子集的全体对象 具有某些共同属性。或者说，对任何对象、属性以及其中的本质性的东西等进行 的分析，实际上就是对背景( c o m e x t ) 进行的分析。 形式背景是对背景的形式化描述，它重点体现对象集、属性集以及它们之间 的关系，如果用g 表示对象集、肘表示属性集，表示对象集和属性集之间的关系， 则g 、从，构成的三元组称作一个形式背景。 定义2 1 1 2 l 形式背景被定义为一个三元组足= ( g ，md ，其中g 和肘分别是 对象集合和属性集合，g 的元素称为对象( o b i e c t s ) ，肘的元素称为属性( 砌b u l e s ) ( 严格地讲是形式对象和形式属性) ，而j 是g 和m 之间的二元关系，即j g x m ， 为了表示一个对象g 和一个属性棚在关系，中，可以写成g 砌或b m ) ，并且读 成“对象g 具有属性肌”。 关系川丝被称为形式背景的映射，对于伍肌) 仨，有时写成咖。形式背景 可以用一个交叉表来表示。表中各行用对象名标识，各列用属性名标识。g 行与肌 第8 页河南大学硕士研究生学位论文 列的交叉点表示对象“g 具有属性珊”。交叉点的表示可以任选，只要交待清楚含 义。形式背景描述了对象及其特征之间的自然分组和关系的有序集。 表2 _ l 二元关系表示形式背景 例2 1 表2 - 2 所示的形式背景用于表示积木。这里对象表示各种积木，属性表 示积木的属性。 表2 - 2 积木形式背景竭 属性集 f 对象集o 红蓝黄固方三角大小 * l0 0 l oo0 l 五o l 00 l o10 五 lo00ol0i 兄0 1 oo0 l o 1 魁 oo110001 0010lo0l 而 l 00o0ll0 咒 00100ll0 形式背景x = ( g ，m d 可被表示为以对象为行、以属性为列的二值矩阵，其每 一元素u 为行序，七为列序，o ，4 g l i ，o 七8 m 0 ) 可定义为： fi如果对象，拥有属性i 啄5 1 0 否则 将表2 2 的形式背景用二值矩阵表示，即可得到图2 1 。 河南大学硕士研究生学位论文第9 页 l0 olo o ol 0lo ol0l0 l0o0olol olo o 01ol o o1lo o o1 o ol010 o1 1o o o o1 10 o ol0 oll0 图2 1 形式背景的矩阵表示 定义2 2 1 2 1 给定对象集合g ，对于对象子集一g ，定义 彳i 珊m i v g 4 - g h n 表示“一中全体对象所共有的属性集”。相应地，对于属性子集曰 以定义 f ：= g g i v m 曰g i m ) 表示“同时具有口中所有属性的对象的集合”。 如在表2 2 所示的形式背景蜀中，墨= 红，三角，小) ，红+ = 五，局，西) ， 表示码是红色的小三角，在对象集中，红色的有三个对象墨，局，局。 定义2 3 1 2 i 形式背景足= ( g ，md 中的一个形式概念是个对u ，功，其中 爿量g ，b m 满足：4 = 占且四= 一。4 、b 分别称为形式概念似，研的外延( e x 锄t ) 和内涵( i n t e m ) 。b ( g ，m d 表示形式背景( g ，m d 所有形式概念的集合。 显然，概念的内涵是概念外延中所有对象的共同属性的集合，而概念的外延是 概念内涵可以确定的最大的对象集合，一个概念是一个完备的二元组。特别定义 两个特殊的概念，分别是包含所有对象的概念为全概念，包含所有属性的概念为 空概念。 形式概念似，的外延彳和内涵b 被关系，紧密地联系在一起。因为47 = b 且 b 号一，那么外延决定内涵，同时内涵也决定外延，进而决定了形式概念。下面的 命题2 1 进一步陈述了这种相互作用的简单规则。 命题2 1 1 2 l 如果是一个形式背景，4 、一卜2 g 是对象集合，丑、丑l 、历是 属性集合，则 1 ) l 4 2 = ，爿；4 2 ) 一4 3 、4 = 一。 l ) e b 2 ：e 耳 2 ) 曰b 。 3 1 b = b ” 4 ) 一曰曰e 一爿b ， 第1 0 页河南大学硕士研究生学位论文 证明： 1 ) 如果m 4 ，那么对于所有的g 爿：，有g ，m ，也就是说，对于所有的g 彳。，特别地有g ，m ，如果4 一2 ，那么小爿；。 2 ) 如果g 月，那么对于所有的m e 彳有占m ，这蕴含着g 。 3 ) 根据2 ) 立即得到爿，再根据彳5 。和1 ) 得到。所以a = 彳。 4 ) 有定义直接得到。 由命题2 1 得出，对于每个集合g ，由于( 一。，一) 总是一个形式概念，所以彳 是这个形式概念的内涵。爿。包含a 的最小外延。因此，任意一个集合4 g 是一 个外延当且仅当4 = 一。对于内涵也同理。外延的并集一般不是一个外延，然而， 任意个外延( 内涵) 的交集总是一个外延( 内涵) 。 由此得出从形式背景得到形式概念的方法： 1 ) 选择对象4 2 ) 得到一对象具有的所有属性集一 3 ) 得到具有属性集的所有对象集，似7 4 ) 则口”，彳) 就是一个形式概念。 例如对于表2 2 中的形式背景背景蜀，求形式概念 1 、任选一个对象a ，比如= 恐 。 2 、得到属性集彳= 蓝，方，大) 。 3 、得到叫) = 蓝，方，大) k 施 。 4 、那么得到的口”，爿产( 恐 ， 蓝，方，大) ) 就是一个形式概念。当然由于形式 背景的特殊性，得出) = 彳。形式概念可以命名名称，也可以不命名名称。 形式概念中的对象集是形式概念的外延，形式概念中的属性集是形式概念的 内涵。例如对于形式概念：叫”彳产( 托) ， 蓝，方，大) ) ，则( ，一) 的外延为 恐) ，似”，4 ) 的内涵为 蓝，方，大) 。 如果用c 表示一个给定的形式概念，其内涵和外延也可以分别用i “t e m ( c ) 和 e x t e n t ( c ) 来表示。 定义2 4 脚如果( 彳l ，甄) 和( 4 2 ，晚) 是一个形式背景的两个形式概念，如果 彳l 彳2 ( 等同于历e 两) ，那么( i 蜀) 被称为( j 4 2 ，晚) 的子概念，( t 2 ，历) 被 河南大学硕士研究生学位论文第”页 称为“i ，历) 的父概念，并且我们记为( l ，b 1 ) ( 4 2 ，历) 。关系是形式概念 之间的序。按此方式有序的b ( g ，md 所有形式概念的集合被表示为默g ，md ， 即互g ，m d = ( b ( g ，m d ， ) ，并且被称为形式背景极g m d 的概念格。 子概念父概念关系是b ( g ，m d 上的偏序关系，因为它满足自反性、反对称性 和传递性。通过这个关系，我们得到一个偏序集垦( g ，m d = ( b ( g ，m d ，9 ，因为 对于b ( g ，尬d 任意非空子集s ，s 中的任意两个形式概念都有最小上界和最大下 界，所以偏序集联g ，md 是一个完全格。 定理2 1 【2 】设置= ( g ，m d 为一形式背景，甄目= ( b ( g ，m d ， ) 是形式背景k 的概念格，那么垦( 回为一完全格，对于b ( g ，md 的任意非空子集，其最小上界 s u p a 卧目) 和最大下界i n 妲( 叼) 分别为： v ( x 。，g ( z ) ) = ( g ( 厂( 置) ) ，n g ( 置) ) t i l 旧 i 甜 ( z 。，g ( 置) ) = ( n z ，( g ( y g ( x ，) ) ) ) - e ，j 酣 陀。 概念格可以图形化表示为有标号的线图( 1 a b e l l e dl i n ed i a 群眦) 。生成图的方法 如下：如果c i c 2 ，且格中没有元素c 3 使得c 1 c 3 c 2 ，那么就存在一条从c l 到c 2 的边。在线图中，我们使用黑色的圆圈表示形式概念，使用向上的线段表示 子概念父概念关系。对于一个对象，如果c 是包含该对象的最小概念，则对象的 名称被附在c 所对应的圆圈上。对于一个特征，如果c 是包含该特征的最大概念， 则特征的名称被附在c 所对应的圆圈上。概念格的有标号线图通常被用作通信模 式，这使得给定数据背景的概念结构变得清晰和易于理解，从而实现了概念格的 可视化的显示。 例2 _ 2 对于表2 3 中的形式背景， 表2 - 3 形式背景足 abcd l100o 20l00 300lo 4 000l 5lllo 61l0l 对应的格为图2 2 所示。 图2 2 由k 得出的概念格墅( 叼 第12 页河南大学硕士研究生学位论文 2 3 多值形式背景 在标准语言中，单词“属性( 砷晡b u t e ) ”不仅仅用于一个对象要么有要么无的 性质( p m p e n i e s ) ，诸如“颜色”、“重量”、“性别”、“年级”等属性都具有很多的 值，它们被称为多值属性( m 锄y - v a l 啪da n m m t e s ) ，与我们至今为止所考虑的单值 属性截然不同。 对象属性值关系是对现实世界问题进行编码的一种常用的数据结构，在统计 学中它被表示为数据矩阵。而在计算机科学中则被表示为关系数据库。在形式概 念分析中，它被阐述为多值背景1 2 4 l ，而形式背景则通常又被称作单值背景。 在经典形式概念分析中，形式背景是单值的。即通常对每个属性用l 表示该 属性在该对象中出现，用0 表示不出现。实际上多值形式背景和单值形式背景是 完全等价的，我们可以通过一定的方法将多值形式背景转换成单值形式背景。本 文中算法实现所使用的形式背景都是单值的。 定义2 5 一个多值形式背景( g 必矾d 由集合g ，m 和矽以及这三者之间 的一个三元关系，组成，g m 矿且下式成立 k ，m ，w ) 堪( g ，埘，v ) 聪蕴含辄= v 。 g 的元素称为对象，肼的元素称为( 多值) 属性，的元素称为属性值。b m ，w ) ，读为“对象g 的属性肼有值w ”。称( g ，m 暇，) 为行值形式背景，如果矿 有订个元素。多值属性可以被认为是从g 到w 的偏射。所以