（计算机软件与理论专业论文）基于本体的web信息集成若干关键技术研究.pdf

摘要 摘要 w e b 提供了一个极其丰富而有价值的信息资源库。如何从w e b 信息源中获 取并提供给用户符合需要的w e b 信息这是一个具有重要意义的理论和实际应用 课题。w e b 上的数据具有半结构性、异构性和分布性等特点，这些特点决定了 w e b 信息集成是一项十分具有挑战性的工作。 本文在分析w e b 信息特点和当前w e b 信息集成方法的基础上，以基于中间 层本体的混合方法( m b h 方法) 为线索，就基于本体的w e b 信息集成若干关键 技术进行了研究。这些研究包括了从对象集合中自动提取本体概念、面向w e b 表格的信息抽取、m b h 方法中中间层本体的构造、本体上的柔性查询及m b h 方法中的查询重写等内容，所做的工作和取得的创新成果主要体现在下面五个方 面： 1 提出了一个基于互关联后继树模型的概念格构造算法以提高从对象集合 中提取概念的效率。该算法将我们在全文检索研究中的成果互关联 后继树模型应用于概念格构造当中，利用形式背景的互关联后继树模型， 结合数据挖掘中对频繁项集的挖掘技术实现概念内涵的提取，在概念提 取过程中避免了大量候选属性集的生成。与其它概念格构造算法相比， 理论分析和实验都证明该算法具有一定的优越性。 2 针对中文信息，提出了一个基于正则表达式、面向w e b 表格的信息抽取 方法。该方法在分析表达概念的中文短语特点基础上，将表达同一本体 概念的中文短语自动概括为一类正则表达式表示的方言模式，通过正则 表达式的匹配实现从w e b 信息到本体概念的映射，并同时针对w e b 表 格特点，制定相应的策略解决匹配冲突。该方法重点解决了信息抽取中 同一概念不同表达带来概念不易识别的问题，实验证明该方法具有一定 实用性。 3 借鉴需求工程中的多视点理论，基于一些限定和假设，提出了一个基于 多视点的中间层本体构建方法，将各局部本体视为中间层本体的一个视 点，根据构建过程中应遵循的三条原则，通过检查和处理各局部本体间 的不一致性，使用启发式规则推理不同局部本体概念之间的关系等手段 获取中间层本体。该方法在获取中间层本体的同时，也保证了中间层本 体与局部本体间的语义一致性。 4 将柔性查询和半柔性查询概念引入到本体查询当中，同时针对本体图为 树的情况，提出了一个本体上半柔性查询的有效求解方法。该方法通过 复亘大学博士学位论文第i 页 摘要 建立索引和使用叶序区间判断s f - c o n d i t i o n ( 半柔性条件1 是否满足实现 本体上的半柔性查询求解。同传统的深度优先遍历方法相比，理论分析 和实验都证明该求解方法具有一定优越性。 5 根据所研究的关键技术和实际项目中的应用需求，提出了一个使用m b h 方法的w e b 信息集成体系结构，并基于该体系结构开发了一个基于本体 的w e b 信息集成原型系统，该原型系统具有本体管理、w e b 信息抽取、 查询重写等功能，具有一定的实用价值。 关键词：本体，m b h 方法，中间层本体，概念格，多视点，柔性查询， 查询重写 复旦大学博士学位论文第i i 页 a b s t 队c t a b s t r a c t w e bo f f e r sa na b u n d a n ta n dv a l u a b l ei n f o r m a t i o nr e p o s i t o r y s oi ti sa l li m p o r t a n ta n d m e a n i n gs u b j e c tt or e s e a r c hh o wd i s c o v e r ya n do b t a i nv a l u a b l ei n f o r m a t i o ni n 6 r e p o s i t o r y n ed a t ao f w 曲h a sc h a r a c t e r i s t i c ss u c ha ss e m i s t r u c t u r e d ，h e t e r o g e n e o u s ， d i s t r i b u t e de t c t h e s ec h a r a c t e r i s t i c sm a k et h ei n f o r m a t i o ni n t e g r a t i o no nw 曲a c h a l l e n g i n g w o r k a i ma tm e d i a t o rb a s e dh y b r i d ( m b 哟a p p r o a c h sm a i n l y , t h et h e s i sa d d r e s s e ss e v e r a l k e y t e c h n i c a lp r o b l e m so fo n t o l o g y - b a s e d 骺6i n f o r m a t i o ni n t e g r a t i o n w h i c hc o v e r s o n t o l o g yc o n c e p t se x t r a c t i n gf r o mo b j e c t ss e tb a s e do nf c a , i n f o r m a t i o ne x t r a c t i n g f r o mw 曲t a b l e ，m e d i a t o ro n t o l o g yc o n s t r u c t i n gi n m b h ，f l e x i b l eq u e r i e so v e r o n t o l o g y , q u e r yr e w r i t i n g i nm b h m a j o rc o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： 1 a ni r s t - b a s e da l g o r i t h mi sp r o p o s e df o rc o n s t r u c t i o no fc o n c e p tl a t t i c e st o e l e v a t et h e p e r f o r m a n c e o f c o n c e p t se x t r a c t i n g f r o m o b j e c t s s c t t h e a l g o r i t h mf i r s tu s e st h ei n t e r - r e l e v a n ts u c c e s s i v et r e e sm o d e l t ot r a n s f o r m f o r m a lc o n t e x t , t h e ne x t r a c tc o n c e p t sf r o mf o r m a lc o n t e x t b yt e c h n o l o g i e so f f i n d i n gf r e q u e n ti t e m s e t si n d a t am i n i n g i nt h ee x t r a c t i n gp r o c e d u r e ，t h e a l g o d t t m aa v o i d sg e n e r a t i o no fl o t so fc a n d i d a t ea t t r i b u t e ss e t s c o m p a r e d w i t hs o m eo t h e ra l g o r i t h mf o rc 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 c o m p l e x i t y a n a l y s i sa n de x p e r i m e n ti l l u s t r a t et h a tt h ea l g o r i t h mw g ：p r o p o s e di sm o r e e f f i c i e n t 2 a i ma tc h i n e s ei n f o r m a t i o n ，ar e g u l a re x p r e s s i o n sb a s e d ，w e bt a b l bo r i e n t e d i n f o r m a t i o n e x t r a c t i n g m e t h o di s p r o p o s e d i n o r d e rt oe x t r a c tc h i n e s e i n f o r m a t i o nf r o mw e bt a b l e s ，w e a n a l y s e t h ec h a r a c t e r i s t i c so fc h i n e s e p h r a s ew h i c he x p r e s s e sc o n c e p ti no n t o l o g y , g e n e r a l i z eak i n do fd i a l e c t p a t t e r nu s i n gr e g u l a re x p r e s s i o n sf r o mp h r a s es e tw h i c he x p r e s s e st h es a m e c o n c e p t w eu s e t h ed i a l e c tp a t t e r nm a t c h i n gt oc o m p l e t e m a p p i n g f r o mw e b i n f o r m a t i o nt oc o n c e p ti no n t o l o g ya n dd e s i g ns t r a t e g yt or e s o l v em a t c h i n g c o n f l i c ta tt h es a m e t i m e e x p e r i m e n t i l l u s t r a t et h a tt h i si n f o r m a t i o n e x t r a c t i n g m e t h o df o rw e bt a b l e si sa p p l i e d 3 i l l u m i n e d b ym u l t i p l ev i e w p o i n t st h e o r y i n r e q u i r e m e n te n g i n e e r i n g , a m u l t i p l e - v i e w p o i n t s b a s e d m e d i a t o r o n t o l o g yc o n s t r u c t i n ga p p r o a c h i s p l o p o s e d w ev i e we a c hl o c a lo n t o l o g ya so n ev i e w p o i n to ft h em e d i a t o r 复旦大学博士学位论文第i i i 页 o n t o l o g y , u s ei n c o n s i s t e n c yc h e c k i n ga m o n g e a c hl o c a l o n t o l o g y a n d h e u r i s t i cr u l e sw h i c hr e a s o nr e l a t i o n sb e t w e e nc o n c e p t si nd i f f e r e n tl o c a l o n t o l o g y i oo b t a i nm e d i a t o r o n t o l o g y t h em u l t i p l e - v i e w p o i n t s - b a s e d m e d i a t o r o n t o l o g yc o n s t r u c t i n ga p p r o a c hk e e p s s e m a n t i ca m o n gl o c a l o n t o l o g i e sa n d m e d i a t o r o n t o l o g y 4 w ci n d u c tt h ec o n c e p t so ff l e x i b l ea n ds e m i f l e x i b l eq u e r i e si no n t o l o g y q u e r i e s w h e n t h e o n t o l o g yg r a p h i sa t r e e ，w ep r o p o s e d a l le f f i c i e n t a p p r o a c ht oe v a l u a t es e m i f l e x i b l eq u e r i e s t h i sa p p r o a c h u s et r e ei n d e xa n d t h e o r e ma b o u tl e a f o r d e r r e g i o n t oe v a l u a t es e m i f l e x i b l e q u e r i e s o v e r o n t o l o g yt r e e c o m p a r e d w i t ht h ec u s t o me v a l u a t i o na p p r o a c h , t h ea p p r o a c h w e p r o p o s e d i sm o r ee f f i c i e n ti u u s t r a t e db ye x p e r i m e n t 5 aw e bi n f o r m a t i o ni n t e g r a t i o na r c h i t e c t u r ei s p r o p o s e d b a s e do n t h i s a r c h i t e c t u r ea n dr e q u i r e m e n ti np r o j e c t ，w ee x p l o i tap r o t o t y p ef o rw e b i n f o r m a t i o n i n t e g r a t i o n t h i sp r o t o t y p e h a sf u n c t i o n ss u c h a s o n t o l o g y m a n a g e m e n t ，w e b i n f o r m a t i o ne x t r a c t i o n ，q u e r y r e w r i t i n g e t c k e y w o r d s ：o n t o l o g y ，m b h ，m e d i a t o ro n t o l o g y ，c o n c e p tl a t t i c e s ，m u l t i p l e v i e w p o i n t s ，f l e x i b l eq u e r i e s ，q u e r yr e w r i t i n g 复量大学博士学位论文第i v 页 第一章绪论 第一章绪论弟一早三；百下匕 本章首先阐述了本文的研究背景，重点讨论了基于本体的w e b 信息集成中的 一些基本问题。然后回顾了这方面的相关研究工作。最后介绍了本文的研究内容 与本文的结构安排。 1 1 研究背景 w e b 自出现以来，已经发展成为上亿个用户，数以百万个站点，存储了数亿 个页面的巨大的全球化分布式信息空间。它的超文本形式包含了各种新闻报道、 商业信息、技术资料、科研文献与文化娱乐等多种类与形式的信息集，为人们提 供了一个极其丰富而有价值的信息资源库。对网络环境下的w e b 海量信息进行 集成、分析处理并提供决策服务成为当前研究的新热点。 w e b 上的数据具有半结构性、异构性和分布性等特点，屏蔽这些特性，为用 户提供统一的模式，是目前w e b 信息集成的关键问题。目前分布式异构信息集 成的方式主要有两种，结构化方法和面向语义的方法。结构化方法提供给用户供 查询使用的统一结构模式，其主要特定是实现比较简单、信息源相对比较固定。 结构化方法的一个代表性项目是s t a n d f o r d 大学开发的t s i m m i s 系统 【t s i m m i s 9 8 1 。 因特网上数据所固有的异构性、分布性、增长性和变化性决定了结构方法不 适应w e b 信息集成，并且随着w 3 c 对s e m a n t i c w e b s w 0 1 的大力推广，面向语 义的w e b 信息集成方法已成为w e b 信息集成技术的研究重点。 每个w e b 站点中的信息处于某特定语义背景当中，这个背景中的特定知识 蕴涵在w e b 信息当中，与w e b 信息一起构成了w e b 信息的语义。由于w e b 信 息的分布性，w e b 信息的语义可能存在异构问题，造成语义异构主要由于下面几 个问题： 1 不同的信息源使用多种术语( 词汇) 表示同一概念。 2 同一概念在不同的信息源中表达不同的含义。 3 各信息源使用不同的结构来表示相同( 或相似) 的信息。 4 各信息源中的概念之间存在着各种联系，但因为各信息源的分布自治性 这种隐含的联系不能体现出来。 在面向语义的w e b 信息集成中必须提供一个通用语义模型以解决语义异构 问题。这个通用语义模型是一个平台无关模型( t h e p l a t f o r m i n d e p e n d e n tm o d e l ， 复旦大学博士学位论文第1 页 第一章绪论 p n v 0 ，屏蔽了w e b 信息之间的语义异构。本体( o n t o l o g y ) 作为“特定领域内概念 以及概念之间关系的集合”n f 0 9 1 ，能够有效地表达特定领域内的通用知识， 非常适合作为面向语义的w e b 信息集成中的通用语义模型，因而目前面向语义 的w e b 信息集成方法一般都基于本体。 本体工程作为人工智能研究领域中一个新兴的分支，正被越来越多的知识工 程研究者所关注。目前在本体工程研究领域已经出现了不少研究成果，这些研究 成果正在逐步形成一个完整的体系。 原则上，信息集成根据集成的数据分为两种方式：数据仓库方式和查询驱动 的集成( o n d e m a n dr e t r i e v a l ) 方式。在数据仓库方式中，所有需要的数据被收集 在一个中心数据库中，等待用户的查询。数据仓库最大的问题在于无法满足用户 对于数据的时变性，但优点在于实现和维护简单。若采用查询驱动的集成方式， 则当查询执行时，查询执行引擎才从各分布信息源动态提取数据。查询驱动的集 成方式优点在于能够总是提供给用户最新的数据，对于具有时变性的w e b 信息 而言，实际应用中查询驱动的集成方式更适合于w 曲信息集成。 基于本体的w e b 信息集成方法远远要比使用结构化的方法复杂。造成这种 复杂性的主要原因在于：基于本体的w e b 信息集成涉及到本体工程中的多个研 究领域，如本体构建、本体集成、本体查询等。由于本体工程作为人工智能中一 个新兴的领域，在许多研究领域还未形成成熟、完整的体系。这种不成熟性和不 完整性给基于本体的应用带来了许多困难。 毫无疑问，构建一个实用、有效的基于本体的w e b 信息集成系统是一项具 有挑战性的工作，在构建过程中需要考虑下面的问题： - 如何获取w e b 信息集成系统需要的本体。 - 如何基于本体对w e b 信息源中的信息进行抽取。 如何提供灵活的查询机制以满足用户查询本体的要求。 _ 如何基于本体获取用户需要的信息。 【w v v 0 1 】中将目前基于本体的信息集成方法主要分为三种：单本体方法 ( s i n g l eo n t o l o g y 印p r o a c h e s ) 、多本体方法( m u l t i p l eo n t o l o g ya p p r o a c h e s ) 和混合方 法( h y b r i d a p p r o a c h e s ) 。这三种方法的体系结构如图1 - 1 所示： 单本体方法采用一个全局本体( g l o b a lo n t o l o g y ) 对应于各分布、异构信息源， 作为所有信息源的通用语义模型。当各信息源具有基本相同的领域视角时，采用 此法比较适合，但如果各信息源的领域视角不同，则创建统一的全局本体十分困 难，并且当各信息源发生改变时，全局本体也必须相应修改。在多本体方法中， 每一个信息源对应于一个局部本体( 1 0 c a lo n t o l o g y ) ，不同局部本体间建立映射关 系( 如不同局部本体中的概念哪些相等或相似) ，当每个局部本体更改时，只需修 复旦大学博士学位论文第2 页 第一章绪论 改受影响的关联部分，但多本体方法不利于本体之间的互操作。为了弥补单本体 方法和多本体方法的缺点，混合方法被提出。混合方法使用一个共享的词汇集合 f s h a r e dv o c a b u l a r y ，有时共享词汇集合也是一个本体，被称为公共本体( g e n e r a l o m o t o g y ) ) 雠- t 领域中的原语 在不同本体之间基于语义层应用不一致性检查和处理策略，消除了不同 本体之间的语义不一致性。 使用启发式规则在语义层获取不同本体概念之间的关系，并使用p r o l o g 子句推理解决语义蕴涵问题。 使用同态概念改写本体图，消除了中间层本体中的冗余。 本体上的柔性查询 在基于本体的应用当中，用户常常要查询本体以获取感兴趣的概念与关系。 目前面向本体 羽( o n t o l o g yg r a p h ) 的查询多使用严格匹配的机制。为了扩展查询的 语义，以提供给用户更灵活的查询机制，我们将y k a n z a 提出的针对半结构化数 据( 0 e 蛐的柔性查询和半柔性查询概念 k s 0 1 应用于本体查询之中。 柔性查询和半柔性查询基于“一条路径上的节点是语义相关的”这一假设， 使用柔性匹配和半柔性匹配进行查询的求解。 目前对于柔性查询和半柔性查询，多使用图遍历的方法，其缺点是效率不高。 针对本体图为树的情况，我们提出了一个本体上半柔性查询的有效求解方法。方 法中使用全文检索中的索引技术为本体树建立索引，并使用叶序区间来判定两个 节点是否在同一条路径上以检查映射是否满足s f - c o n d i t i o n ( 半柔性条件) 。该方 法中的相关技术同时也可应用于柔性查询的求解。与传统的深度优先遍历求解方 法相比，该方法从理论上和实验上都证明具有一定优越性。 _ m b h 方法中的查询重写 在m b h 方法中，用户的查询基于中间层本体，而w e b 信息却直接映射到局 部本体，当用户提交了一个查询之后，系统需要将这个基于中间层本体的查询改 写为基于局部本体的查询，这个过程称之为查询重写。 在本文的研究中，我们参考关系数据库中的查询重写技术 【l e v y 0 0 r s u 9 5 p l 0 0 ，将本体中的概念( 主要指类) 表达为谓词形式，使用 d a t a l o g 规则表示查询，并根据中间层本体中概念与局部本体中概念之间的关系， 分为g a v ( g l o b a l a sv i e w ) 和l a v ( l o e a l8 8v i e w ) l e v y 0 0 两种方式来讨论查询重 写算法。 原型系统 基于所研究的技术和我们所承担项目的具体需求，我们讨论了一个使用 m b h 方法的w e b 信息集成体系结构，并基于这一体系结构开发了一个具有一定 使用价值的原型系统。 复旦大学博士学位论文第1 4 页 第一章绪论 1 3 2 本文的组织安排 本文以m b h 方法为线索，围绕对基于本体的w e b 信息集成关键技术的研究 展开，总共分七章，具体安排如下： 第一章绪论 该章首先阐述了本文的研究背景，重点讨论了基于本体的w e b 信息集成 中的一些基本问题。然后回顾了这方面的相关研究工作。最后介绍了本 文的研究内容与本文的结构安排。 第二章基于f c a 的概念提取 该章主要介绍了如何基于f c a 从对象集合中提取概念，并将重点集中 在概念格的构造算法上，提出了一个基于互关联后继树的概念格构造算 法。并在理论与实验上进行了与其它算法的比较。 第三章面向w e b 表格的信息抽取 针对中文信息，该章提出了一个面向w e b 表格，使用正则表达式表达概 念并通过正则表达式匹配实现信息抽取的方法。详细讨论了通过样本集 合获取正则表达式的算法以及匹配冲突解决策略，并展示了应用该方法 的实验结果。 第四章基于多视点的中间层本体构造 该章首先提出了在m b h 方法中构造中间层本体应遵循的三条原则，然 后借鉴需求工程中的多视点理论，提出了一个基于多视点的中间层本体 构造方法。方法中将各局部本体视为中间层本体的一个视点。通过检测 和处理各局部本体间的不一致性，使用启发式规则推理不同局部本体概 念之间关系等来获取中间层本体。 - 第五章本体驱动的查询处理 w e b 信息集成系统的一个主要功能是回答用户的查询。用户的查询被分 为两类：对于本体的查询和基于本体对w e b 信息源中数据的查询，该章 对这两类查询问题进行了研究。针对本体查询，该章提出了本体上柔性 查询和半柔性查询概念，并提出了一个本体图为树时的半柔性查询有效 求解方法。针对m b h 方法中的查询重写问题，该章应用关系数据查询 重写的研究成果来解决这一问题。 第六章原型系统 该章首先讨论了一个应用m b h 方法的w e b 信息集成体系结构，然后介 绍了一个基于该体系结构和实际项目应用需求，并结合本文所研究技术 所开发的一个基于本体的w e b 信息集成原型系统。 复旦大学博士学位论文第1 5 页 第一章绪论 _ 第七章总结与展望 该章对全文的工作进行了总结，并对今后的工作提出了新的研究方向。 图1 - 4 显示了本文的研究内容与结构。 图1 - 4 本文的研究内容与结构 复旦大学博士学位论文第1 6 页 第二章基于f c a 的概念提取 第二章基于f c a 的概念提取 构建一个完整且准确概括领域知识的本体是基于本体的应用项目顺利实施 的必要前提，从数据集中提取领域本体中的概念是目前辅助本体构建所使用的主 要方法。概念在哲学中被理解为由外延和内涵两个部分所组成的思想单元，基于 概念的这一哲学理解，本章中主要研究了如何基于形式概念分析( f o r m a l c o n c e p t a n a l y s i sf c a l 理论从对象集合中提取概念，并重点介绍了一个基于互关联后继树 ( i m e r - r e l e v a n t s u c c e s s i v et r e e s r e s t ) * 引模型的概念格( c o n c e p tl a t t i c e s ) 构造算 法。理论与实验都证明该算法与其它一些概念格构造算法相比具有一定的优越 性。 2 1 引言 构建一个完整且准确概括领域知识的本体是基于本体的应用项目顺利实旌 的必要前提。在本体构建研究领域，尽管已经出现了一系列的本体构建方法学和 开发工具，但本体构建自动化仍然一直是本体研究领域中的技术难题。虽然构建 本体依然离不开人类专家的干预，但许多使用模式识别、人工智能和数理统计技 术的方法已被用于辅助本体构建，这些方法能够大大减少本体开发者的工作量， 辅助本体开发者构建语义完整的本体。 概念是构造本体的基本元素，因而辅助构建本体的工作也主要集中于概念的 自动提取，提取的来源主要来自领域内的数据集：如文本文档集合、w e b 页面集 合和关系数据库等。目前的研究主要集中在从文档集合中提取概念 s g o l l y t i d l f s 0 1 ，这些方法主要使用数理统计和自然语言处理技术，具有 较高的自动化程度，但不足之处在于提取的精确度不高，并且结果的完备性无法 度量。 在许多对本体的定义中f n f g 9 1 g r u b e r 9 3 ，概念并无明确的结构，可以 指代现实世界中任何东西。但若要使用机器提取概念，则必须首先给出能够被机 器识别的概念形式。 概念在哲学中被理解为由外延和内涵两个部分所组成的思想单元。基于概念 的这一哲学理解，德国的w i l l e 教授提出了形式概念分析o 。o r m a l c o n c e p t a n a l v s i s f c a ) 【s w 9 5 f l s 9 5 】【w 1e 9 2 】理论，用于概念的发现、排序和显示。在f c a 中， 概念的外延被表示为属于这个概念的所有对象的集合，而内涵则被表示为所有这 些对象所共有的特征( 或属性) 集合，从而实现了对概念哲学理解的形式化。 复旦大学博士学位论文第1 7 页 第二章基于f c a 的概念提取 领域内的数据集中常常包含了许多属于某概念的对象( 如数据库中的记录) ， 基于f c a 中对概念的形式化定义，可以从这些对象集合中提取概念，并且这样 的提取过程能够提取出对象集合中的所有概念。 对象集合中所有概念构成了一个概念格( c o n c e p tl a t t i c e s ) 。作为f c a 中核心 的数据结构，概念格本质上描述了对象和属性之间的联系，表明了概念之间的泛 化与例化关系，而提取概念的过程实质上也成为一个概念格构造过程。概念提取 的效率直接取决于概念格的构造效率。 构造概念格的主要困难在于概念格中概念数目是形式背景( f o r m a lc o n t e x t l 大小的指数级函数，并且概念数目的确定是一个n i 完全问题。所有的概念格构 造算法都需要解决两个问题：( 1 ) 如何产生所有的概念。 0 ，s ( y ) 0 ，则s ( x ) = s 0 0 。 根据形式概念内涵和属性集的势可得到定义2 4 、2 5 。 定义2 4 项概念内涵和k 项属性集) 对于形式概念口声) ，若阻i 曲，我们称 曰为一个k 项概念内涵。对于任意x t z _ m 且闳曲，我们称x 为k 项属性集。 定义2 - 5 ( 概念等价类) 对于形式概念口卫) ，眶i l f ，若丑”；8 ，则称z 与 概念u 声) 存在概念等价关系矗，概念“柳的等价类被定义为陋】，。= v w - _ mi x r b 。 对于概念等价类，根据性质2 1 和2 - 3 ，有性质2 4 。 性质2 - 4 对于a r - _ m 和形式概念口力。如果s ( 的 o 且艇吲，。，则一定有 艇蛰，即因s 1 日i 且s 僻) = s ( 的。 定理2 - 1 、2 - 2 被用来判定一个七( 七 0 ) 项属性集与k 项概念内涵之间的关系。 定理2 1 在一个形式背景中，对于颤t o o ) 项属性集工有s o ，若在所有 支持度大于。的“1 项属性集的集合中存在y ，有x c y 且s c 的= s f 聊，则z 一定 不是一个k 项概念内涵。 证明；由性质2 - 2 可知，x 和y 属于同一概念等价类，且因阳。由性质2 4 复旦大学博士学位论文第2 0 页 第二章基于f c a 的概念提取 可知，一定不是该概念等价类中概念的内涵。 定理2 - 2 在一个形式背景中，对于七( 七 0 ) 项属性集x 有s e 砷 0 ，若在所有 支持度大于。的k + l 项属性集的集合中不存在y j 使得x c y 且s ( 的= s ( y ) ，则z 一定是一个k 项概念内涵。 证明：使用反证法：若x 不是一个k ( b o ) 项概念的内涵，则在x 所属的概念 等价类降】，。中，一定存在概念的内涵曰使得x c b 。则对于y = x u m 圆- 2 0 ) ， 有s = s ( 因为s s s 鹤，而s = s ) 。与假设矛盾，定理得证。 2 4 基于互关联后继树的概念格构造算法 2 4 1 互关联后继树与形式背景 互关联后继树是我们根据序列字符的有序性和冗余性而提出的一种新型的 海量全文存储、索引模型。它的一些基本概念如下。 定义2 6 ( 后继) 对任意文本符号4 6 口2 ，在字符串a l a 2 中，a j 称为4 2 的前驱； a 2 称为口j 的后继。 在一个全文a l a 2 - 一如中( 为了处理方便，我们在全文的最后字符后砸添加了 结束标记符) ，若出现了m 个相同的字符，不妨记为b ，那么b 的后继共有m 个 瓴的后继为) ，记为6 【】( 1 司墨m ) ，6 阴表示b 的第j 个后继。 定义2 - 7 ( 一元后继表达式和后继树) 在一个全文a l d 扣叫，若有m 个字 符口i l ，a b ，a k 相同，不妨记为b b 的所有后继记为4 i 1 + 1 ，a i a + 1 ，a k + 1a 令 口自+ 1 ，口i 2 + 1 ，口+ 1 的所有后继表示为4 自+ 1 t a 9 1 ，口i 2 + 1 【t a 9 2 ，口i m + l 【t a g ，则 b 和它的后继构成一个一元后继表达式o ( o 1 + 1 ，t a g , ) ，( 口”l ，t a 9 2 ) , ， q l r + 1 ，缸踟) ) ，可用一棵后继树来表达此表达式，如图2 - 1 所示。 b 个 ( a i t + 1 ，t a g j ) ( a i 2 “。q ) ( 口+ 1 t a g ) 图2 - 1 后继树 其中b 为树根，分支叶节点由0 。“，缸毋) ( 1 匈绷) 组成。表示4 i ，+ - 是b 的一个 后继。标记姐毋表示4o + 1 的后继将出现在以ai t + l 为根的后继树中的第t a g j + 翁； 支叶节点上。 复旦大学博士学位论文第2 1 页 第二章基于f c a 的概念提取 根据以上定义，我们可定义互关联后继树模型。 定义2 8 ( 互关联后继树模型) 若全文a l a 弘中共有f 个不同的字符，这 f 个字符对应于f 棵不同的后继树，而这些后继树中的每个叶节点都对应于另外 一棵后继树的根节点。换而言之，一个全文所对应的所有后继树是相互关联的， 这种关联关系反映了字符在全文字符串中出现的位置前后关系。我们称一个全文 对应的所有后继树为全文的互关联后继树，记为i r s t 。 例2 1 展示了一个全文字符串的互关联后继树模型。 例2 - 1 设全文“a b c a b a a b c ”，取奉”为串的结束标志符。其中共有3 个不 同的字符；a 、b 和c ，它们对应的一元后继表达式分别为：a ( ( 6 ，1 ) ，p ，2 ) ，0 ，4 ) ，p ，3 ) ) 、 b ( ( c ，1 ) ，0 ，3 ) ( c ，2 ) ) 和c ( 0 ，砧) ，相应的后继树如图2 - 2 所示。这三棵后继树构成 全文“a b c a b a a b c ”的互关联后继树。 进一步，从图2 2 中的第一棵树的第一个分支口一p ，1 ) 开始，按照叶节点的 后继符b 及其后继标记t a g = l 遍历后继树b 的第1 个分支，如此下去将遍历整个 i r s t ，那么遍历路径上的根项所组成的有序字符便还原初始的全文序列。由此 我们可以得到取s t 的等价描述性定理。 定理2 3 i r s t 是全文的一种等价描述模型，即对任意一全文都能构造其 珉s t ，同时对于i r s t 也能还原其对应的原文。 证明：略。 3 ) (2 ) ( 图2 - 2 。a b c a b a a b c ”的互关联后继树模型 c 可以扩展互关联后继树模型来表示形式背景。为此我们称形式背景的互关联 后继树模型为f c i r s t ( f o r m a l c o n t e x tn l s t ) 。 在构建f c i r s t 之前需要对形式背景进行符号化。例2 2 表示了一个形式背 景的符号化过程。 例2 - 2 图2 - 3 表示了一个形式背景的符号化过程。 图2 3 中，我们将一个形式背景r - - ( 6 i l f ) 的交叉表中的每一行( 每个对象) 表示为一个由属性组成的字符串，并在每个字符串的尾部加上“表示一个字 符串的结束。这里，我们预先分配给形式背景中的属性和对象一个序号，对象使 用g i ( 1 出n ，n = l g i ) 表示，属性使用，l t ( 1 巫s m ，肌= m ) 表示。在k 的符号化结果j f 每个对象的属性集字符串中，属性之间按序号升序排列。很明显，足与j ( c 是等 价的。f c i r s t 中的后继树结构如图2 4 所示。 复旦大学博士学位论文第2 2 页 八一 第二章基于f c a 的概念提取 m lm 2m ， 扭t m 5 g l 9 2 印 9 4 9 5 0 l l ，g i d ( a ) 一个形式背景置 对象属性集 量jr t l l 脚2 m 4 0 勘m l 席2 m ，。 g ji n 2 1 7 1 3 m e i n s , 9 4 r t l l 册j m 4 * g s m 2 m 3 m j f o ) r 的符号化结果j ( c 图2 - 3 一个形式背景的符号化过程 图2 - 4f c i r s t 中的后继树 图2 - 4 中，m i 表示j f 中任一属性。暑瞄( 1 母鳓表示，l f 依次出现在j f 中对象 的序号，4f 1 ，口f 2 ，4 f ，表示出现在对象gg i d f 的属性集字符串中m f 后面的所 有属性字符( 共有0 个) ，a 。为该属性集字符串中i , n i 的后继，口枷+ 1 j ( 1 蜊6 ) 是 4 柚的后继，这里我们不妨称4 ，。j 为m i 的间接后继。若椭出现在对象g 列f 的 属性集字符串中最末位，则将”作为m i 的后继。招g 加( 1 s m s 劲表示a 舯在对 象g 州，的属性集字符串中的后继将出现在以口加为根的后继树中的第略加 个分支叶节点上。将图2 4 和图2 1 进行比较，可发现f c i r s t 是i r s t 的扩展， 在f c i r s t 后继树的叶节点中包含了根节点的间接后继。例2 3 展示了例2 2 中 形式背景的f c 瓜s t 。 例2 - 3 图2 5 展示了由例2 2 中j 【c 构建的f c i r s t 。 在形式背景k 的符号化结果f 中，我们将每个对象表示为g i = m m b mk ， 则k 的f c i r s t 可用一个元素为队列的数组f c 表示，其中f c i 中的f 与属性 m ；中的序号下标i 对应。 每一队列f c i 有一个指针c o u n t ，记录当前队列存放后继节点的个数，队 列中的元素为一个三元组帆趣试，t a g ) ，此三元组与图2 4 中叶节点结构相同。置的 f c i r s t 构造算法如算法2 ，1 所示。 算法2 _ 1 ：形式背景k 的f c i r s t 构造算法 输入：形式背景k 的符号化结果k c ，其中有n 个对象g ，, 9 2 , - - - 岛，m 个属性 m l , m 2 ，朋a 每个对象毋= m m t m k + ( 七绷) 。 复旦大学博士学位论文第2 3 页 第二章基于f c a 的概念提取 输出：形式背景k 的f a r s t - 一数组f c 。 过程： f o r o = 1 ；f s m ；f + + ) f c 【f 】，c o u n t = o ；)，扔始纪月q v 手超嚣 f o rq = k t s 玳“q 开始处理每个g i 七= b i ( 不包含+ ) ； 强x = 踯c o n t i n u e ；| l 对象中一个羁性都投南跳幽此次循环 f o r ( f = 1 ；f ( 七；“+ ) f o ro = f + 1 ；! 龟，+ + ) a d d ( ( mi j ，i ，f c f a c o u n t + 1 ) ，f c m ) ；疟f c 觑 张中规a 元素 f c h 】c o u n t + + ； ) a d d ( 孓啡越； 1 1 2 缸a 对象羁性集字符串帕结束捋” f c m c o u n t + + ； ) 。，纛沁正习灸。弋 图2 - 5 例2 - 2 中f 的f c i r s t 模型 算法2 - 1 依次对j f 中每个对象g j 处理，得到队列数组f c 中的每个元素。 f c i 包含了以m i 为根节点的后继树中所有的叶节点( 队列f c i q u 的所有元素) 。 从算法2 - 1 所构造的f c i r s t 中同样可还原出对应的j f 。为此我们可得到类似定 理2 3 的等价描述性定理。 定理2 - 4 f c i r s t 是形式背景置的一种等价描述模型：对于任一形式背景都 能构造其f c i r s t ，同时对于f c 瓜s t 也能还原出其对应的形式背景。 证明：略。 复里大学博士学位论文第2 4 页 、l ， )、l，、， d刁q$q乃 坩屹n 第二章基于f c a 的概念提取 由定理2 4 可知，从