（控制理论与控制工程专业论文）概念格同构生成方法研究及isofca系统实现.pdf

上海大学博士学位论文 摘要 形式概念分析( f o r m a lc o n c e p t a n a l y s i s ，f c a ) 是应用数学的一个领域，其主要 内容是研究“概念”和“概念分层”的数学化描述，从而引发了数学思想在概念数据 分析和知识处理方面的研究和应用。f c a 的主要思想是从表示为形式背景( f o r m a l c o n t e x t ) 的数据中获取形式概念( f o r m a lc o n c e p t ) 以及形式概念之间的联系，形成一 种以形式概念为元素的格结构概念格( c o n c e p tl a t t i c e ) 。概念格是知识系统的良 好抽象，其意义主要有两方面：一、从数据中获取概念。与其它基于统计的传统数据 分析方法不同，f c a 用概念表示数据分析的结果，概念格是数据的高级表示形式 知识视图；二、概念格为知识处理提供了很好的基础，比如知识表示、关联规则发现、 智能搜索引擎、语义w e b 和自然语言理解等。 f c a 的一个重要问题是构造概念格。概念格的构造算法分为批处理算法和渐进式 算法两大类，目前已经有许多文献致力于概念格构造算法研究和设计。然而，这些研 究都集中在如何从形式背景直接构造概念格以及概念格的代数性质本身。而如何利用 形式背景之间的关系生成概念格方面，除了少数文献给出简单的原理性叙述之外，尚 未见有深入的研究成果发表。 本文在知识相似性的表示问题的研究中，结合形式背景同构和概念格同构等基本 原理，实现了以下创新点： 1 提出基于形式背景核的概念格同构生成方法。核心思想是：对于任意的形式 背景足，都可将其分解为阶数较小子背景。对每一个子背景墨的简化形式，在同阶形 式背景核中必存在与之同构的元素蜀，然后根据目的概念格导出墨的全部概念，从 而得到的墨概念格堡) 。最后合并所有的堡( k ) 得到壁( 固。 2 提出形式背景同构判定算法等价类算法。形式背景同构判定是判定一个 形式背景经过行、列交换能否变换成另一个形式背景，旨在寻找形式背景变换的快速 算法，本文提出的等价类法能够较好的解决这个问题。 3 提出r 阶形式背景核的概念及其构造算法。, 阶形式背景核是具有 个属性的 形式背景的集合，满足：每个元素都是简化的且任两个元素互不同构。在n 阶形式背 v 上海大学博士学位论文 景核的构造算法研究中，提出限定性定理，避免对b ( ”) 中数量接近一半而规模相对较 大的背景进行穷举，从而提高构造形式背景核的效率和阶数。形式背景核也是利用有 限知识表示新知识的基本模型。 4 提出并实现了概念格三维可视化互操作模型。根据概念格的空间伸展特性， 此项研究完成了概念格在三维空间的自动布局、动态显示和互操作用户界面。 5 设计并实现了一个基于概念格同构生成的软件工具i s o f c a ( i s o m o r p h i s m f c a ) 。基于创新点l 的思想，在系统的开发中，具体实现了n 阶形式背景核的构造、 形式背景的自动分解、形式背景的同构判定、概念格的同构生成和格的并行合并等。 概念格的同构生成具有多方面的理论意义和实用价值。首先，为概念格的获取提 供了一条新的途径。其次，建立一种知识处理的分布式语义模型。第三，支持学习过 程中的知识相似性的形式表示，即用一个知识系统相似地表示另一个知识系统。这一 点在i s o f c a 中得到了实践验证。 关键词：形式背景、概念格、同构、形式背景核、重构 v 上海大学博士学位论文 a b s t r a c t f o r m a lc o n c e p ta n a l y s i s ( f c a ) i saf i e l do fa p p l i e dm a t h e m a t i c sb a s e do nt h e m a t h e m a t i z a t i o no fc o n c e p ta n dc o n c e p t u a lh i e a r a c h y t h e r e b yi ta c t i v a t e sm a t h e m a t i c a l t h i n k i n gf o rc o n c e p t u a ld a t aa n a l y s i sa n dk n o w l e d g ep r o c e s s i n g t h em a j o rc o n t e n ti nf c a i st oe x t r a c tf o r m a lc o n c e p t sa n dc o n n e c t i o n sb e t w e e nt h e mf r o md a t ai nf o t i no ff o r m a l c o n t e x ts o a st of o r mal a t t i c es t r u c t u r eo ff o r m a lc o n e e d t s c o n c e p tl a t t i c e sh a v eb e e n r e g a r d e da sp e r f e c ta b s t r a c t i o no fk n o w l e d g es y s t e m t h e r ea r et w os i g n i f i c a n ta s p e c t s f i r s t ，t h er e s u l t so fd a t aa n a l y s i sa r ec o n e p t si n s t e a do fd a t at h e m s e l v e s d i f f e r i n gt o t r a d i t i o n a ld a t aa n a l y s i sm e t h o d sb a s e do ns t a t i s t i c s ，f c ao b t a i n sk n o w l e d g ev i e ww h i c hi s h i 曲e rl e v e lo f r e p r e s e n t a t i o no f d a t a s e c o n d ，c o n c e p tl a t t i c e sp r o v i d eb e t t e rf o u n d a t i o nf o r k n o w l e d g ep r o c e s s i n g ，s u c h a sa s s o c i a t i o nr u l e d i s c o v e r y , i n t e l l i g e n ts e a r c he n g i n e ， s e n m a t i cw e ba n dn a t u r a ll a n g u a g ep r o c e s s i n g o n eo fi m p o r t a n ti s s u e si nf c ai sc o n s t r u c t i o no fc o n c e p tl a t t i c e s s of a r , t h e r ea r et w o k i n d so fa l g o r i t h m sf o rc o n c e p tl a t t i c e s c o n s t r u c t i n g ，b a t c ha l g o r i t h m sa n di n c r e m e n t a l a l g o r i t h m s h o w e v e r , m o s to ft h er e s e a r c h e sd e d i c a t e dt ob u i l dc o n c e p tl a t t i c e sd i r e c t l y f r o mc o n t e x t s r a r er e s e a r c hp a p e r sw e r ep u b l i s h e di na d d i t i o nt o 5 w h i c h g i v e so u ts o m e b r i e fd e s c r i p t i o n so ne x p l o i t i n gt h er e l a t i o n sb e w t e e nc o n t e x t st og e n e r a t ec o n c e p tl a t t i c e s i nt h i sd i s s e r t a t i o n ，f i v ee m p h a s e sa r ep l a c e do nt h ed e v e l o p m e n to ft h em e t h o d s i n c l u d i n g ， 1 an o v e lm e t h o do fi s o m o r p h i cg e n e r a t i n go fc o n c e p tl a t t i c e sb a s e do nn t h - o r d e rc o n t e x t k e r n e l s ，o fw h i c ht h ec e n t r a li d e ai st h a ta na r b i t r a r yc o n t e x tkc a nb es p l i to n t o s u b c o n t e x t si ns m a l l e rs i z eo f o r d e r , t h e n ，f o re v e r ys u b c o n t e x tk i ，t h e r ee x i s t sai s o m o r p h i c c o n t e x tqi nt h ek e r n e lw i t ht h es a m eo r d e ra sk i ，a n dc o n c e p tl a t t i c e 堡( 墨) c a nb ey i e l d e d i nt e r m so f 墅( h o ，a n df i n a l l y , t h er e s u l t 受( 固c a nb er e c o n s t r u c t e df r o m 堡( k 0 2 e q u i v a l e n tc l a s sa l g o r i t h m ，ar a p i da l g o r i t h mf o rc o n t e x ti s o m o r p h i s md e t e c t i n g ，w h i c h i st od e t e r m i n ew h e t h e rac o n t e x tc a nb et r a n s f o m r e di n t oa n o t h e ro n eb ye x c h a n g i n gr o w s o rc o l u m n s ，a n df o c u s e so nf i n d i n go u tr a p i da l g o r i t h mo fc o n t e x tt r a n s f o r m 3 n o t i o no fn h - o r d e rc o n t e x tk e r n e la n da na l g o r i t h mf o rk e r n e lc a l c u l a t i n g a nn o r d e r c o n t e x tk e r n e li sas e to fc o n t e x t sw i t hna t t r i b u t e s a n da 1 1e l e m e n t si ni t l , r er e d u c i b l ea n d 上海大学博一l 学位论文 a r en o ti s o m o r p h i ct oe a c ho t h e ra sw e l l t h ek e r n e li su s e dt oe n s u r et h a te v e r ys u b c o n t e x t o fac o n t e x ti si s o m o r p h i ct oo n ei nt h ek e m e ls ot h a tt h el a t t i c e so fs u b c o n t e x tc a nb e g e n e r a t e df r o mc o r r e s p o n d i n gl a t t i c e so f k e r n e le l e m e n t s t h et h e o r e mp r o p o s e di nc h a p t e r 4g u a r a n t e e st h a ta l m o s th a l f o f a m o u n to f l a r g ec o n t e x ti n n n 、n e e dn o tb es c a n n e di n t h e p r o c e s sf o rk e r n e lc a l c u l a t i n g c o n t e x tk e r n e l c a nb er e g a r d e da saf o u n d a t i o nm o d e lt o e x p r e s s i n gn e wk n o w l e d g e 。b yu s i n gl i m i t e dm e t ak n o w l e d g e 4 a ni n t e r a c t i v em o d e lb a s e do nc o n c e p tl a t t i c e sv i s u a l i z i n gi nt h r e e d i m e n s i o n a ls p a c e t h ec o n c e p tl a t i c e sv i s u a l i z i n gi n c l u d e sn o to n l yt h ed e v e l o p m e n to ft h r e e 。d i m e n s i o n a l l a t t i c e sd i s p l a y , w h i c ha l l o w su s e r st or o t a t e ，f o l d u n f o l dl a t t i c e ，t oa n dd e t a i li n f o r m a t i o n c h e c k i n g ，b u ta l s oi n t e r a c t i v eu s e ri n t e r f a c e s 5 as o f t w a r et o o l k i ts y s t e m ，i s o f c a ( i s o m o r p h i s mf c a ) ，b a s e do nc o n c e p tl a t t i c e s i s o m o r p h i cg e n e r a t i n g f u n c t i o n si m p l e m e n t e d i n c l u d en t h - o r d e rc o n t e x tk e r n e l c o n s t r u c t i o n ，c o n t e x tr e d u c t i o n ，c o n t e x td e c o m p o s i t i o n ，c o n t e x ti s o m o r p h i s md e t e r m i n a t i o n ， g o d i na l g o r i t h mi m p r o v e m e n t ，c o n c e p tl a t t i c ei s o m o r p h i cg e n e r a t i o na n dl a t t i c ep a r a l l e l r e c o n s t r u c t i o n i s o m o r p h i cg e n e r a t i n go fc o n c e p tl a t t i c e si sas i g n i f i c a n tm e t h o dt oy i e l dl a t t i c e sw i t hg r e a t p r a c t i c a lv a l u e f i r s to fa l l ，t h em e t h o dp r o v i d e sa d i f f e r e n tw a yt oo b t a i nc o n c e p tl a t t i c e s f r o mc o n v e n t i o n a la l g o r i t h m s s e c o n d t h ec o n t e x tk e m e li sad i s t r i b u t e ds e m a n t i cm o d e l i n k n o w l e d g ep r o c e s s i n g l a s t ，k n o w l e d g es i m i l a r i t yc a nb ed i s c r i b e dw i t ht h em o d e li n k n o w l e d g el e a r n i n g ，a n dak n o w l e d g es y s t e mc a nb em u c hm o r ee a s i l ye x p r e s s e db yt h e s i m i l a r i t yo fa n o t h e rk n o w l e d g es y s t e m t h ep r o c e d u r e i sp e r f o r m a n c e di ni s o f c a k e y w o r d s f o r m a lc o n t e x t ，c o n c e p tl a t t i c e s ，i s o m o r p h i s m ，c o n t e x t k e r n e l ， r e c o n s t r u c t i o n v l 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过 的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 签名：日期：秒暖让吗 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论 文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 物笙吼型! ! ：竖厶 上海大学博j j 学位论文 第1 章绪论 本论文工作属于国家自然科学基金项目“基于r o u g h 集合理论的概念格结 构模型研究( 6 9 9 8 5 0 0 4 ) ”、“分布式概念格数学模型与算法研究( 6 0 275 0 2 2 ) ”和 “面向本体的形式概念分析扩展模型与算法( 6 0 5 7 50 3 5 ) ”中的内容，并得到上海 市高等学校青年发展基金( 0 3 a q 9 9 ) 以及河南省自然科学基金( 0 3 1 l0 1 170 0 ) 的资助。 学习的过程是获取新知识的过程。按照美国著名认知教育学家d a v i d a u s u b e l 的学习理论：人的学习应该是意义学习，影响学习的最主要因素是学习 者已掌握的知识，当学习者有意义学习的意向，并把所要学的新知识同原有的知 识联系起来时，意义学习便发生了 1 ，影响学习的最重要的因素是学生已知的 内容 2 】。人们认为新知识的学习取决于新、旧知识能否达到意义的同化，其中 最常见的一种现象是通过旧知识的相似性来理解新的知识。例如，如果个人对 “图书馆”、“书库”和“管理部门”的作用以及这三者之间的关系有所了解，那 么他便能较容易地理解“数据库系统”、“数据库”和“数据库管理系统”等新概 念以及它们之i n 的关系。注意，通过相似的知识，人们不仅仅学到孤立的新概念， 更重要的是掌握了众多概念之间的联系，这种联系反映了知识的结构。人们在交 流过程中经常使用例子和比方，正是基于相似知识结构上的这种相似性。本文旨 在从计算的角度揭示知识相似性的本质，并且建立利用已知知识获取新知识的计 算模型。那么，什么是知识的相似性? 1 1 知识的相似性 我们认为，知识的相似性是指不同的知识领域之间存在着对应的概念，并且 这些概念之间存在着相同的联系。概念是知识的基础，它是人类对客观世界的认 知过程中所产生的理性结果。每一个概念都具有外延和内涵两个逻辑特征，外延 是概念对思维对象分子范围的反映，即表示概念适用的范围：而内涵则是概念对 思维对象本质属性的反映，即代表外延中的思维对象所具有的共同性质。人们在 实践活动中不断形成概念，实质上就是对自然界的各种事物按照它们的共性不断 分类的过程。所谓遍尝野果，归纳特性，才能总结出什么是苹果、什么是桃子。 关于概念的形成过程，直到现在，从词典到心理学，从早期的逻辑经验主义 到现在的人工智能研究，对于概念形成的理解仍然是概括论的思想，即从对象到 概念：把给定对象的共同特点抽出来，加以概括，就成为概念。黑格尔恰恰反对 这种理解。他说：“我们以为构成我们表象内容的那些对象首先存在，然后我们 主观的活动方随之而起，通过前面所提及的抽象手续，并概括各种对象的共同之 l 海大学博士学位论文 点而形成概念一一这种想法是颠倒了的。反之，宁可说概念才是真正在先的”【3 】。 我们认为，无论是以认知主体为主的概括论思想，还是以认知客体为主的黑格尔 的概念先在思想，其反映的实质有一点是相同的：概念反映的是类对象，这些 对象都具有按照人类主观意识确定的某些属性，并且它们既可以是客观存在的实 物，也可以是抽象的现象。 概念以及概念之间的联系是构成知识的重要基础。在人工智能领域，为了使 得计算机便于进行知识处理，必须对概念进行抽象。康乃尔大学的j o s e p hd n o v a k 博士根据d a v i da u s u b e l 的学习理论，于上世纪六十年代提出了概念图技 术。概念图( c o n c e p tm a p ) 是一种用节点代表概念、用连线表示概念间关系的图 示法 4 ，它可以很直观地表示一个领域的知识。然而，概念图是建立在已经获 取了概念的基础上，并且概念之间的联系也是依赖于人为的理解。换言之，人们 对概念的外延和内涵的理解并不很精确，只能依靠常识确定概念之间的联系。因 此，尽管概念图能够表示概念及其之间的联系，却不能反映这种联系的实质，也 不能反映概念的内部特征。与概念图类似的还有概念语义网络，都是从直观理解 出发，在非限定性的范围内，用常识性的、非严格的元素去构造概念及其关系。 这种方法对概念进行了一定的抽象，结合某种具体方法也具有一定的意义，但是 它不能从根本上揭示概念的形成，也不能从根本上揭示概念之间的关系。 1 2 用概念格的同构表示知识的相似性 形式概念分析理论 5 做照哲学的观点，利用数学手段将哲学中的“概念” 抽象成了“形式概念”，并按照形式概念外延的“大小”定义它们之间的关系， 形成概念格。概念格由德国的r u d o l fw i l l e 教授于1 9 8 0 年在领导达姆施塔特 ( d a r m s t a d t ) 大学的研究小组试图让系统自动通过应用格论来生成一个结构框 架时发现的。形式概念( 在不引起混淆的情况下，简称为概念) 来自于形式背景， 而形式背景表是二维表，表示人们所关注的某个领域的数据集合。概念格形式化 地描述了知识系统，成为日益受关注的知识建模方法。f 3 9 研究了概念格的代数 性质。同时，形式概念分析作为一种能获得数据知识视图的分析方法也被越来越 广泛地应用到各个领域，如软件工程 6 、知识发现 7 、人工智能 8 、机器学习 【9 和w e b 知识发现 1 0 等各种涉及数据语义分析的领域。 表1 - 1 关于图书馆主要组成部分的形式背景 能存放书籍具有借还图书和管理功能 l 书库是 l 管理部门 是 很多知识系统，往往可用概念格来描述其基本结构，即概念及其关系。如果 j 二海大学博：卜学位论文 两个来自不同知识领域的概念格具有相同的结构，则意味着这两个知识系统具有 内在的一致性或者相似性。比如，图书馆和数据库系统两个知识系统，如果忽略 各自专业的某些细节，那么它们具有相似性。表l 一1 是关于图书馆组成部分的一 个形式背景，由此得到的概念格由图1 1 左部所示。为了用旧知识( 图书馆) 比 喻新知识( 数据库系统) ，一是需要知道旧知识的结构，二是需要指出新旧知识 结构上的对应关系。一种表述是“图书馆主要包括书库和管理部门，数据库好比 书库，数据库管理系统好比图书馆的管理部门，数据库系统则好比图书馆，它由 数据库和数据库管理系统构成”。新知识系统如图1 1 右部所示，我们容易发现， 新、旧知识在结构上有很好的对应性。 图1 1 数据库系统和图书馆两个知识系统的同构 至此，我们可以用形式概念分析的观点更确切地定义知识的相似性：知识的 相似性是两个结构相同的概念格。虽然有些复杂的知识系统并不容易用概念格表 示，但是其相似性也是明显的。比如在学习t c p i p 协议的工作原理时，往往用 邮寄信件的种种活动来比喻t c p i p 协议各层次的功能，如图1 , 2 所示。 为了利用概念格建立知识内在一致的描述模型和处理模型，必须要解决一些 列问题，包括规模控制、背景简化、元知识( 元数据) 管理、同构知识的判定、 新知识的生成以及知识的表达，等等。但归根结底，学习的过程是产生新知识的 过程，那么对应地，建立知识相似性模型的目标是有效地获取概念格。因此，在 深入展开讨论之前，有必要首先对概念格构造的主要问题和相关领域的研究现状 作一概要性介绍，研究现状的具体或者深入内容，参见后面各章。 j ：海人学博士学位论文 图1 2 邮局信件服务系统和t c p i p 通信协议的同构 1 3 本文研究的内容、意义和创新点 概念格的构造是f c a 的中心任务之一。到目前为止，国内外研究人员提出 了多种概念格构造算法，主要包括批处理算法和渐进式算法两大类。批处理算法 的思想是首先生成所有概念，然后根据它们之间的直接前驱一后继关系生成边， 完成概念格的构造。这类算法包括b o r d a t 算法 1 1 、o s h a m 算法、c h e i n 算法、 g a n t e r 算法、n o u f i n e 算法和并行造格算法p a r a l l e l n e x t c l o s u r e 1 2 等。渐进式算 法的思想首先初始化概念格为空，将当前要插入的对象的内涵集和现有格中所有 形式概念的内涵集作交运算，根据结果采取相应的处理。典型的算法有 g o d i n 1 3 1 、c a p i n e t o 和t b h o 的算法。国内研究人员对上述有些算法也做了一 些改进，例如改进了的b o r d a t 算法用于挖掘关联规则【1 6 、扩展概念格的渐进式 构造算法 1 5 】、基于索引树的概念格渐进式构造算法【1 4 】和概念格构造算法的改 进 1 7 1 等。 然而，以上各种算法都存在一个共同的问题，即它们都是研究如何根据形式 背景构造概念格，而没有研究形式背景之间、概念格之间的关系，更没有深入研 究如何利用这种关系有效地获取概念格。 本文的主要贡献是提出以n 阶背景核为基础的，以背景的分解、简化、同构 生成与合并为手段的概念格生成的思想，包括提出了一系列相关的概念和方法， 实现了一个以同构生成为特点的形式概念分析工具。具体主要解决的问题有：形 上海大学博士学位论文 式背景的约简( 包括清晰化和标准化) 、形式背景的同构判定( 主要成果为基于 等价类的同构判定算法) 、形式背景有限性问题( 主要成果为n 阶形式背景核的 生成) 、形式背景的分解、概念格构造算法的改进、概念格的同构生成算法、概 念格的重构和知识可视化，以及相关并行算法研究。 其中，本文的核心内容，即本文的创新点有： 1 提出基于形式背景核的概念格同构生成方法。核心思想是：对于任意的 形式背景k ，都可将其分解为阶数较小子背景。对每一个子背景匿，在同阶形式 背景核中必存在与之同构的元素h ，然后根据鼠的概念格导出蜀的全部概念， 从而得到的墨概念格里( 蜀) 。最后合并所有的堡( 墨) 得到堡( 固。 2 提出形式背景同构判定算法等价类算法。形式背景同构判定是判定 一个形式背景经过行、列交换能否变换成另一个形式背景，旨在寻找形式背景变 换的快速算法，本文提出的等价类法能够较好的解决这个问题。 3 提出n 阶形式背景核的概念及其构造算法。h 阶形式背景核是具有n 个 属性的形式背景的集合，满足：每个元素都是简化的且任两个元素互不同构。在 n 阶形式背景核的构造算法研究中，提出限定性定理，避免对皿f n ) 中数量接近一 半而规模相对较大的背景进行穷举，从而提高构造形式背景核的效率和阶数。形 式背景核也是利用有限知识表示新知识的基本模型。 4 提出并实现了概念格三维可视化互操作模型。根据概念格的空间伸展特 性，此项研究完成了概念格在三维空间的自动布局、动态显示和互操作用户界面。 5 设计并实现了一个基于概念格同构生成的软件工具i s o f c a 。基于创新点 1 的思想，在系统的开发中，具体实现了h 阶形式背景核的构造、形式背景的自 动分解、形式背景的同构判定、概念格的同构生成和格的并行合并等。 基于背景核的概念格同构生成方法具有理论意义和应用价值。首先，理论上 对图同构判定问题有借鉴意义。形式背景同构判定问题与采用邻接矩阵表示的无 向图的同构判定问题非常相似，但又不完全相同。区别之一是形式背景可看作任 意阶数的二值矩阵，而无向图的邻接矩阵是一个对称的二值方阵。所以在某种程 度上形式背景同构判定的问题更具有一般性。因此，本文提出的基于等价类的形 式背景同构判定算法不仅对概念格的生成具有实际意义，而且对于图同构判定问 题也具有理论意义。 其次，本文提出的基于背景核的概念格同构生成方法，是一种从根本上描述 知识相似性的模型，很好地抽象了学习中的关键因素用旧知识表示新知识。 在机器学习领域，系统能够利用背景核及其概念格作为元知识，从而表示新的知 识系统。如果系统有能力识别这些相近的领域知识，就有可能避免重复地构造概 念格。这样，不仅会大大降低概念格的空间和时间复杂性，并且增强了系统的智 卜海大学博士学位论文 能处理能力。 第三实际应用上，i s o f c a 系统能够作为一个原型系统，促进了f c a 的技 术化，支持更广泛的( 不仅仅是机器学习) 知识处理应用。概念格不仅支持各种 数据分析和知识发现 2 8 【3 9 】，还可用于智能信息处 n 4 0 - 4 4 】和基于概念搜索技 术 4 5 4 6 1 。随着w e b 资源的快速积累，人们对计算机系统处理能力的期望也逐 步提高，仅仅进行一般的数据处理已经不能满足社会发展的需求。尤其对于基于 w e b 平台的计算机系统，人们对其处理能力的期望正在从一般的网页浏览、关键 词检索和信息过滤等数据处理层次，转移到更高的智能化知识处理层次上来。系 统能够对w e b 资源进行语义理解，这已经成为非常迫切的要求。形式概念分析 是基于概念的信息处理方法之一，也是非常重要的一个研究领域。 1 4 本文的结构 本文共十一章，第二章介绍形式概念分析理论的相关基本知识。从第三章开 始，按照渐进的顺序逐步论述本课题的工作。 第三章探讨本课题工作最基本的内容：形式背景同构判定问题和基于等价类 的判定方法，这是本文的核心内容之一。 第四章首先简要介绍形式背景的简化、分解，以及形式背景简化的两个基本 方法：清晰化和标准化。然后重点讨论形式背景核的有关概念和计算方法，这是 本文的核心内容之一。 第五章介绍概念格构造的基本算法，重点介绍对g o d i n 算法的改进。g o d i n 算法也是形式背景核构造的基本算法。 第六章在上述内容的基础上，论述概念同构生成这一具体环节的算法。 第七章介绍概念格的重构，内容是如何把多个同域概念格合并为一个大的概 念格。重点论述基于同义概念的合并算法。 第八章是知识的可视化，主要介绍概念格的三维互操作模型的设计与实现， 是本文的核心内容之一。 第九章给出整个系统的设计与实现，并通过实验分析系统的整体性能。这一 章实际上是对论文全部工作的集成和验证，其实验结论是整体性的结论。 第十章通过个实例展示系统的1 作原理和应用价值。 最后一章概括本文的研究结论。 上海大学博士学位论文 第2 章形式概念分析基础 本章主要介绍相关的基础知识，内容涉及序论、格论和形式概念分析理论。 2 1 序论中的基本定义 定义2 ，1 设a 是一个集合，如果a 上的一个二元关系r ，对于v x ，n z a ， 满足如下条件： x r x ( 自反性1 x r y ，y r x ；x = y ( 反对称性) x r y ，y r zj x r z ( 传递性) 则称r 是a 上的一个偏序关系，把它记为“”。序偶，) 称为偏序集。 定义2 2 设，蔓) 为偏序集，对于b 一，如有n ，b e a ，且对任意z t t ， 都满足x d ，则称口为子集占的上界。同理，若对任意x e b ，都满足b x ， 则称b 为子集占的下界。 定义2 3 设臼，) 为偏序集，b g a ，a 为b 的任一上界，若对口的所有上 界y 均有a j ，则称a 为b 的最小上界( 上确界s u p r e m u m ) ，记为s u p ( 1 1 ) 。同 样，若b 为口的任一下界，若对曰的所有下界2 均有z b ，则称b 为b 的最大 下界( 下确界i n f i m u m ) ，记为i n f ( 1 1 ) 。 定义2 4 若( m ) 是一个偏序集，a ，b ，c ，d 是m 中的元素且b c 。则集合 陋，c 】：= x m 1 6 xs c ) 称为间隔( i n t e r v a l ) ，集合( d 】：= x e m ix - a ) 称为 主理想( p r i n e i p a li d e a l ) ，集合矽) ：= 朋jj d ) 称为主滤子( p r i n c i p a lf i l t e r ) 。 并且，日 b 被称为是一个完全并半格，类似地，如果对于任意非空的集合s _ c a 都存 在有 s ，则似，s ) 被称为是一个完全交半格。如果以，) 既是完全并半格，也是完 全交半格，则它是一个完全格。 定义2 8 对于完全格v 的任意一个元素v ，定义v ：= v z v l x v 和 v + ：= 八 x v v x 。如果v v ，则称v 是v 不可约简的( 读做“上确界不可 约简的”) ，如果v v + ，则称v 是 一刁；可约简的( 读做“下确界不可约简的”) 。 用以”表示所有v 不可约简的元索的集合，用 取”表示所有 一不可约简的元 素的集合。 定义2 9 偏序集( ) 和( ，) 之间的映射妒：m 一被称为单调的 ( m o n o t o n o u s ) ，如果对于所有x ，y e m 下面命题为真 】sy 等妒xs 妒y o 进一步，如果p 又是单射( i n j e c t i v e ) 且满足 则称p 为嵌序的( o r d e r - e m b e d d i n g ) 。 定义2 1 0 如果偏序集( m ) 和( ，) 之间的映射p ：m 一是个双射 函数且是嵌序的，则称之为一个序同构( o r d e r - i s o m o r p h i s m ) 。 上海大学博士学位论文 2 3 形式概念分析的理论基础 这里介绍的部分相关概念引自 5 。 定义2 1 1 形式背景( f o r m a lc o n t e x t ) 通常被定义为一个三元组：k ：= ( g ，m ， r ) ，其中g 和m 是集合，而r 则是g 和m 之间的二元关系。即r g x m ，其 中g 和m 的元素分别被称为对象和属性，而g r m ( 即b ，t ? 1 ) r ) 被读作：对象 g 具有属性m 。若基数0 埘i = h ，则称k 为n 阶形式背景。在不混淆的前提下， 形式背景简称为背景( c o n t e x t ) 。 定义2 1 2 给定背景k ：= ( g ，m ，r ) ，对于对象子集a g ，定义 a ：= 伽m v g 爿g 矗m 表示“a 中全体对象所共有的属性集”。相应地，对于属性子集b c - m ，定义 b ：= g g i v m b g r m 表示“同时具有b 中所有属性的对象的集合”。 表2 l 表示了一个背景。其中g = f l ，2 ，3 ，4 ，吖= ，b ，c ，d ) ，r 描 述了g 中元素拥有的m 中的属性值集，符号表示交叉与此的对象一属性对偶属 于关系月，因此这样的表格有时被称为交叉表。在表中通常使用l 代替。对象 3 的属性集为， 3 ) 7 = 昌自。 ，而f a ，c ) 7 = f 2 ) 。注意，因为集合 3 ) 只有 一个元素，所以往往把f 3 7 简单表示为37 ；对于属性也如此。 表2 _ 1 一个4 阶背景 口bcd 定义2 1 3 背景( g ，m 尺) 中的一个形苛榴j 含混一个序偶对a ，b ) ，其中a g ， b m ，且满足：a = b 且b = a 。其中a 、b 分别称为形式概念口，b ) 的办筵 ( e x t e n t ) 和力炳( i n t e n t ) 。毋( g ，托r ) 表示背景( g ，旭r ) 所有形式概念的集合。 在不引起混淆的情况下，本文以下部分将形式概念简称为概念。 命题2 1 如果( g ，尬r ) 是一个形式背景，a ，a l ，a 2 g 是对象集合，曰，b l 岛c m 是属性集合，则 本文中用双竖线括住个集合表示它的基数，即元素的个数。 9 上海太学博二j 学位论文 1 ) a l 互a 2j a i a ：1 ) 曰l b 2j b ；b j 2 ) a a ” 27 ) 曰b ” 3 ) a = a ” 3 1 日= b ” 4 ) a b 铮b a7 铮a b r 证明略。 对于每个对象子集a g ，由于( a ”，爿7 ) 总是一个概念，所以a 是这个形式概 念的内涵。a ”包含a 的最小外延。因此，任意一个集合a c g 是一个外延当且 仅当a = a 。对于内涵也同理。外延的并集一般不是一个外延，然而，任意个外 延( 内涵) 的交集总是一个外延( 内涵) 。例如在表2 1 中设爿= 4 ，由于a ”= 栅t 3 ，4 1 9 = a ，所以 4 ) 不是一个外延；而 3 ，4 、 1 ，3 ) 都是外延。 定义2 1 4 设( a l ，b 1 ) 和( 爿2 ，b 2 ) 是一个背景的两个概念，如果a j c a 2 ( 等同于b 2 c b i ) ，那么( 一l ，b 1 ) 被称为( 4 2 ，曰2 ) 的于掀( 爿2 ，b 2 ) 被称 为( a t ，b 1 ) 的危掀并且记为( 一1 ，b 1 ) ( 4 2 ，b 2 ) 。关系被称为概念的 德序，且( g ，m 尺) 的按此方式有序的所有概念的集合表示为 亟g ，m 月) ， 并且被称为背景( g mr ) 的砌：岔磐。 定义2 15 对于两个背景k i = ( g l ，m 1 r 1 ) 和尬= (