（计算机应用技术专业论文）基于linked+open+data的语义关联发现及其应用.pdf

浙江大学硕上学位论文摘要 摘要 语义网( s e m a n t i cw e b ) 的目标是通过在网页内容上附加形式化的语义信息， 让机器也能够理解网页的内容。随着语义网技术逐渐成熟，人们根据互联数据 ( l i n k e dd a t a ) 的原则在语义网上发布、连接结构化数据，最终产生互联数据。 开放互联数据社区的成立极大地促进了互联数据的发布。已经发布的互联数据集 覆盖领域广泛，有地理信息、人口资料信息、在线社区、科学出版物、音乐等。 互联数据为从分布式数据源中发现事物之间潜在的关系提供了巨大的可能。随着 越来越多的互联数据的发布，如何在互联数据上进行语义关联发现成为研究的关 键问题。 语义关联是语义数据模型中实体之间二维关系的知识表示形式。语义关联发 现基于现有的语义关联，使用算法推导出更深层次的语义关系。然而现有的语义 关联发现方法都是基于集中式的知识库的，这不符合互联数据的分布式特点，也 使得现有的方法可扩展性较差。因此，研究设计一种符合互联数据分布式特点， 可扩展性较好的语义关联发现方法是非常必要的。 针对上述问题，论文提出并设计实现了一个多代理协作的分布式语义关联发 现框架。具体内容包括：提出一种新的知识表示模型，介绍了假设、证据、证 据图等知识元素的表示方法，该知识表示模型有助于多个代理之间进行知识交 换。提出了一种新的多代理协作式语义关联发现机制。设计实现了两类代理： 目录代理和挖掘代理，并对代理提供的服务给出了详细的规范定义。设计实现 了语义关联发现的核心算法，并研究分析了算法可以采用的不同策略。对该语 义关联发现框架进行模拟实验，并做性能分析。并将它应用于d b l p 和d b p e d ia 数据集，结果表明多代理之间协作进行语义关联发现是可行的。 关键词：语义关联发现，多代理，挖掘，协作，互联数据 a b s t r a c t s e m a n t i cw 色ba i m sa ta t t a c h i n gw e bp a g e sw i t hf o r m a ls e m a n t i ci n f o r m a t i o nt om a k e t h e mm a c h i n eu n d e r s t a n d a b l e w i t ht h er a p i dd e v e l o p m e n t o fs e m a n t i cw e b t e c h n o l o g i e s t h e e f f o r to fp u b l i s h i n g ，c o n n e c t i n gs t r u c t u r ed a t aa c c o r d i n gt o t h e p r i n c i p l eo fl i n k e dd a t aw i l l r e s u l t i nw e bo fd a t a t h ee s t a b l i s h m e n to fl i n k e d l i n k i n go p e nd a t ac o m m u n i t yh a sg r e a t l yf a c i l i t a t e dt h er e l e a s e o ft h el i n k e dd a t a t h e s ep u b l i s h e dd a t as e t sc o v e raw i d er a n g eo fa r e a ss u c ha sg e o g r a p h i ci n t o n n a t l o n - d e m o g r a p h i cd a t aa n di n f o r m a t i o n ，o n l i n ec o m m u n i t i e s ，s c i e n t i f i cp u b l i c a t i o n s ，a n d m u s i c t h ee f f o r to fp u b l i s h i n gl i n k e dd a t ap r o v i d e sp o t e n t i a lf o rt h ed i s c o v e r yo f h i d d e ns e m a n t i ca s s o c i a t i o nf r o md a t as o u r c e s a sm o r ea n dm o r el i n k e d d a t a p u b l i s h e d h o wt od i s c o v e rt h es e m a n t i ca s s o c i a t i o nf r o mi tb e c o m eo n e o fk e yi s s u e s i ns e m a n t i cw e br e s e a r c hf i e l d s e m a n t i ca s s o c i a t i o ni sd e f i n e da st h er e p r e s e n t a t i o no fr i c hk n o w l e d g ea b o u tb i n a r y r e l a t i o ni ns e m a n t i cd a t am o d e l s e m a n t i ca s s o c i a t i o nd i s c o v e r yi st oi n f e ro u tf u r t h e r a s s o c i a t i o n sb a s e do ne x i s t i n gs e m a n t i ca s s o c i a t i o n sb yi n v e n t i n ga l g o r i t h m h o w e v e r , e x i s t i n gm e t h o d sa r ea l lb a s e do nac e n t r a l i z e dd a t am o d e l ，w h i c hi s n o tc o n s i s t e n t w i t ht h ed i s t r i b u t e df e a t u r e so ft h el i n k e dd a t a ，b u ta l s om a k e st h es c a l a b i l i t yo ft h e e x i s t i n g m e t h o dp o o r i t sn e c e s s a r yt od e s i g nas c a l a b l e s e m a n t i ca s s o c l a t i o n d i s c o v e r yf r a m e w o r k t h a ti ss u i t a b l ef o rl i n k e dd a t a 1 nr e s p o n s et ot h e s ei s s u e s ，w ep r o p o s ea n di m p l e m e n tad e c e n t r a l i z e dm u l t i _ a g e n t c o i l a b o r a t i v ef r a m e w o r kf o rs e m a n t i ca s s o c i a t i o nd i s c o v e r y t h em a i nc o n t r i b u t i o ni s d e s c r i b e da sf o l l o w ( i ) p r e s e n tan e wm o d e lo fk n o w l e d g er e p r e s e n t a t i o n ，i n t r o d u c e d t h eh y p o t h e s i s ，e v i d e n c e ，e v i d e n t i a r yg r a p ha n do t h e rk n o w l e d g ee l e m e n t s t h e k n o w l e d g er e p r e s e n t a t i o nm o d e lw i l lh e l pt h ee x c h a n g eo fk n o w l e d g ea m o n gt h e a g e n t s ( g ) p r o p o s ean e wm u l t i a g e n t c o l l a b o r a t i v es e m a n t i ca s s o c i a t i o nd i s c o v e r y m e c h a n i s m d e s i g na n di m p l e m e n t e dt w ot y p e so fa g e n t s ：d i r e c t o r ya g e n t sa n d 浙江大学硕士学位论文a b s t r a c t w o r k e ra g e n t ，a n dp r o v i d ed e t a i l e ds p e c i f i c a t i o n sf o rt h es e r v i c e sp r o v i d e db yt h e a g e n t s d e s i g na n di m p l e m e n t e dt h ec o r e o fs e m a n t i ca s s o c i a t i o nd i s c o v e r y a l g o r i t h m s ，r e s e a r c ha n da n a l y z ed i f f e r e n ts t r a t e g i e st h a tc o u l db ee m p l o y i n gi nt h e a l g o r i t h m s d os i m u l a t i o ne x p e r i m e n t st ov e r i f yt h ef e a s i b i l i t yo f t h ef r a m e w o r ka n d a n a l y z et h ep e r f o r m a n c e w ea l s oa p p l yt h ef r a m e w o r kt od b l pa n dd b p e d i ad a t a s e t s ，t h er e s u l t ss h o wt h a ti t sf e a s i b l et ou s et h ef r a m e w o r kt od i s c o v e r yt h eh i d d e n s e m a n t i ca s s o c i a t i o n k e y w o r d s ： s e m a n t i ca s s o c i a t i o nd i s c o v e r y , m u l t i a g e n t ，m i n i n g ，c o l l a b o r a t i o n ， l i n k e dd a t a 浙江大学硕j ：学何论文 图门录 图目录 图1 1 共同链接3 图1 2 互联数据链接图【l o 】5 图2 1 假设1 1 图2 2 证据12 图2 3 系统架构图15 图2 4 目录代理结构图16 图2 5 挖掘代理结构图18 图2 6 代理协作交互图2 0 图2 7 案例说明2 1 图2 8 协议流程图2 3 图2 9 资源查洵服务请求格式2 4 图2 1 0 资源查询服务返回格式2 4 图2 1 1 假设分配服务请求格式2 5 图2 1 2 证据发布服务请求格式2 6 图2 1 3 获取注册代理目录服务请求格式2 6 图2 1 4 获取注册代理目录服务返回格式2 7 图2 15 目录代理解答服务请求格式2 7 图3 1 搜索方向示意图31 图3 2 结果组合算法示意图。3 6 图4 1r o u t e r 算法- 4 0 图4 2 实验样例图4 2 图4 3 实验结果分析图。4 4 图5 1n o d e 数据结构4 7 图5 2 数据结构4 7 图5 3 搜索过程代码4 8 图5 4 标题相似度计算方法4 9 图5 5 记录数据结构51 图5 6 数据结构5l 图5 7 搜索算法实现5 2 图5 8 测试用例结果一5 4 图6 1 系统架构图5 8 图6 2 配置文件图5 9 图6 3 人员帐号关系图6l 图6 4 管理员建立映射关系图6 2 图6 5 注册时建立映射关系图6 2 图6 6 排序模型设计图6 5 i i i 浙江大学硕十学位论文图门录 图6 7 单点登录协议流程图。6 7 图6 8 成功登录效果图6 8 图6 9 成功登录加工系统截图6 9 图6 18 安全传输过程7 0 图6 1 9 消息安全策略配置7 l 图6 2 0 密钥库配置7 l 图6 2 1 事务管理配置7 2 图6 2 2 事务定义7 2 图6 2 3 事务状态判断7 2 图6 2 4 事务提交。7 3 i v 浙江大学硕 ：学位论文表门录 表目录 表2 1 服务列表2 2 表2 2 资源查询服务请求参数说明表2 4 表2 3 假设分配服务请求参数说明表一2 5 表2 4 目录代理解答服务请求参数说明表2 7 表6 1 权限说明表6 0 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝望盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月e t 浙江大学硕i ：学位论文第1 章绪论 第1 章绪论 1 1 语义网 随着互联网的爆炸性增长，网络上包含了越来越多的信息，这些信息为用户 提供了丰富的信息源。搜索引擎技术帮助人们从海量的信息中提取出用户感兴趣 的内容，极大地减少了用户筛选信息的时间，给用户带来了便捷。然而，这些搜 索引擎通常采取自然语言处理、数据挖掘及统计分析等技术对网络文档进行处 理，搜索结果精确度不高。其根本原因在于，网络文档描述了现实世界中对象、 概念和它们之问的关系，这些信息虽然能够让人们理解，但是机器却没有办法理 解文档中所包含的语义。 1 9 9 8 年，t b e m e r s l e e 首次提出了语义网( s e m a n t i cw e b ) 的概念。语义网 的目标是通过在网页内容上附加形式化的语义信息，让机器也能够理解网页的内 容【1 1 。2 0 0 0 年，t b e m e r s l e e 在x m l 2 0 0 0 会议上首次给出了语义网的体系结构 图【2 1 。该结构图展示了一系列已经标准化的语义技术及语义网在传统超文本网络 上的扩展。下面介绍几个语义网体系结构图中的重要技术和概念： 统一资源标识符( u r i ) ：用于唯一标识任何资源，如文档、具体对象或抽 象概念等。u r i 有多种形式如u r l ( 统一资源定位符) 、i r i ( 国际化资源 标识符) 等。例如：可以使用h t t p ：w w w w 3 o r g p e o p l e b e r n e r s l e e 来唯一 标识t b e m e r s l e e 。 资源描述框架( r d f ) 和r d fs c h e m a ( r d f s ) ：它是用于描述资源之间 关系的规范，同时规定了如何用图的形式来表示资源的关系。r d f 是一个 数据模型，它使用 的三元组形式，称作r d f 陈述 ( s t a t e m e n t ) 来描述资源之间的二元关系。把主语和宾语看作结点，谓语 看作一条由主语指向宾语的有向边，一条r d f 陈述就可以表示成一个r d f 图。r d f s 提供了r d f 可以使用的词汇表描述资源之间的属性和类关系。 浙江大学硕i ：学位论文第1 章绪论 本体( o n t o l o g y ) ：本体用于描述事物的本质 3 】。它是一个规范化的词汇 表，它定义了领域内的专业词汇及其关系。本体语言o w l ( w e b o n t o l o g y l a n g u a g e ) 扩展了r d f s ，增加了一些约束，如属性特征、值的约 束等。o w l 语言基于描述逻辑，增强了语义网的推理能力。 s p q r a l ：一种语义数据的查询语言。 架构图中还包括了r i f ( 规则交换语言) 、统一逻辑、证明、信任模块等还没有完 全实现的技术【4 】。 目前，不少人学和研究机构都在从事语义研究。如，斯坦福大学主要研究知 识表示和推理，他t f 仓j 建了一种本体描述语言d a m l ；卡而斯鲁厄大学主要从事 对本体知识的管理；多伦多大学和马里兰大学主要通过语义规则对知识库进行挖 掘等。而惠普研究院、雅虎、i b m 等公司也都投入了许多研究力量从事语义网研 究。 1 2 互联数据 随着语义技术的逐渐发展，有很多数据按照语义规范发布在互联网上。但足 在2 0 0 6 年以前，已发布的语义数据中，有大量数据并没有相互链接【5 1 。语义网不 仅仅是发布语义数据，更重要的是创建语义数据之间的链接，让机器可以浏览数 据。 2 0 0 6 年，t b e m e r s l e e 提出了互联数据( l i n k e dd a t a ) 的原则【5 】： 1 使用u r i 来标识资源； 2 使用h t t pu r i s ，以便人和机器都可以查找( d e r e f e r e n c e ) 资源； 3 查找u r i 时，提供有用的信息( 如元数据等) ； 4 包含同已发布数据的链接，相关u r i 可以提高互联网上相关信息的发现。 从互联数据的原则可以看出互联数据同之前发布的语义数据不同的是： ( 1 ) 使用可查找的u r i 可查找( d e r e f e r e n c e ) 指可以通过u r i 来获得实体的描述。u r i 有着很多 种变种，如：u u i d ( u n i v e r s a l l yu n i q u ei d e n t i f i e r ) 、s s n ( s o c i a ls e c u r i t yn u m b e r ) 2 浙江大学硕1 ：学位论文第l 章绪论 等。u r i 还有子集如：u r l 和u r n 。其中u r l 包含了获取网络文档的机制， 如：h t t p ：w w w w 3 o r g 。u r n 如u m ：i s b n ：0 1 2 3 4 5 6 7 8 9 ，并没有提供查找该标识 符的地点和方法。u r i 中得到最广泛支持的是以h t t p ：模式表示的u r i 。其他形 式的u r i 虽然能够唯一标识资源，但是不能够保证资源的描述可以在查找的过 程中获得。 当资源使用可查找的u r i 来标识时，不但保证资源可以被广泛使用，而且 提供了查找资源详细信息，同相关资源链接的方法。 ( 2 ) 强调数据源之间的链接 一个实体可能在不同的数据集中有不同的唯一标识。例如：t b e m e r s l e e 在d b p e d i a 的数据集中用h t t p ：d b p e d i a o r g r e s o u r c e t i m _ b e m e r s - l e e 来标识； 在d b l p 数据中用h t t p ：w w w 4 w i w i s s f u - b e r l i n d e d b l p r e s o u r c e p e r s o n l0 0 0 0 7 米 标识。实际上两个不同的u r i 标识的都是同一个人，“万维网之父”t b e m e r s l e e 。 为了让机器能够在这两个数据集间自由的浏览。我们把两个u r i 通过 属性链接起来，表示两个u r i 标识的实际上是通过一个实体。 如图1 1 所示： 图1 1 共同链接 创建数据源链接可以手工设置或者自动产生。自动产生链接的方法有：基于 子图的算法和基于属性的算法等【6 】o 互联数据使用资源描述框架( r d f ) 来描述任意资源之间的二维关系；利用 超文本协议( h t t p ) 发布结构化的数据，链接不同数据源中的数据盯1 。简单地说， 互联数据是一种通过可查找u r i 来发布、共享、链接语义数据的方法。 互联数据是语义网技术的子领域，随着语义技术的成熟，越来越多按照互联 数据原则发布的数据的增加，将会形成全球数据库或数据资源网3 ( w e bo fd a t a ) 。 3 浙江大学硕十学位论文第1 章绪论 2 0 0 7 年2 月，由w 3 c 的语义网教育及扩展工作组( s e m a n t i cw e be d u c a t i o n a n do u t r e a c h ) 支持的开放互联数据社区项目成立。该项目的目标足将开放的数 据集用r d f 格式重新发布在互联网j 二，并创建数据间的相互链接。 这些开放的数据集称为开放互联数据( l i n k e do p e nd a t a ) ，它覆盖领域广泛， 有地理信息、人口资料信息、在线社区、科学出版物、音乐等呻1 。其中一些比较 著名的数据集有阳1 ：d b p e d i a ，包含了从维基百科中抽取的数据，共2 1 8 万个概念， 发布了2 亿1 8 0 0 万个三元组；d b l pb i b i l i o g r a p h y ，包含了计算机科学领域的 发表论文信息，有8 0 万篇文章，4 0 万个作者信息，发布了1 5 0 0 万个三元组； g e o n a m e s 包含了6 5 0 万的全世界地理特征信息；f o a f ，包含了人与人之间的关系 的信息，是语义网中非常有名的社交应用等。 开放互联数据社区项目的成立，极大地促进了互联数据的发展。2 0 0 7 年，发 布了2 0 亿多个的r d f 三元组，2 0 0 多万个数据链接晴1 。截止2 0 0 9 年1 1 月，已经 发布了1 3 1 亿个r d f 三元组，1 亿4 2 0 0 万个数据链接阳1 。互联数据的爆发式增长， 使得数据资源网的形成不再只是愿景。 如图1 2 展示了截至2 0 0 9 年6 月已经发布的互联数据情况。其中每个结点表 示一个开放的数据源，结点之间的弧表示数据源之间相互链接。 4 衙# j 学倚论文第1 日论 图】2 互联数据链接图【l 哪 相比于传统的网络只是文档之间的相互链接；互联数据实现的是数据与数据 之间的互联。互联数据是结构化的数据并包含了机器可以理解的语义信息；使 得机器可以直接对互联数据进行处理。互联数据使用h t t pu r i 方便了机器对数 据的查找：数据之间的链接，方便机器从一个数据源测览到另一个数据源，并查 找资源相关的信息。互联数据的这种特性为从分布式数据源中发现事物之间潜在 的关系提供了巨大的可能。 1 3 语义关联发现 语义关联( s e m a n t i ca s s o c i a t i o n ) 是语义数据模型中实体之间二维关系的知 识表示形式，即实体之间的复杂关系。语义关联可以表示为实体之间的语义连通 性或语义相似性”“1 。语义关联可以是直接的，也可以是间接的。 语义关联发现( s e m a n t i ca s s o c i a t i o nd i s c o v e r y ) 基于现有的语义关联， 5 浙江大学硕士学位论文第l 章绪论 使用算法推导出更深层次的关系。语义关联发现使用领域本体来描述和推理领域 相关的关系。 语义关联发现有广泛的应用领域，如： 生物医学知识发现 文献n 4 1 将语义关联发现应用于生物医学领域，通过整合医学概念与生物医学 本体，构造语义网，使用语义关联发现指导专利检索。 社会网络分析 文献n 司将语义关联发现应用于社会关系分析，通过计算审稿人与作者在语义 图上的联通性的强弱，来判断他们之间的利益冲突。 国家安全领域 文献n 6 1 将语义关联发现应用于国家安全领域，通过乘客与危险分子名单的关 联来计算乘客的危险值，指导登机检查，以保证国家安全。 随着越来越多的互联数据的发布，如何在互联数据上进行语义关联发现成为 研究的关键问题。文献【1 6 】提出了语义关联的概念，一套符合r d f 数据模型规范 的语义关联表示模型。语义关联发现最著名的用例是推断统一资源标识符之问的 等价关系，例如推导两个帐号实际上表示同一个用户。而且，可以使用统计方法 根据实体之间的属性推导出实体间的语义相似性 1 6 】。另外，一些相关工作，主要 集中在在语义图上进行实体之间的路径发现和路径排序【1 l - 1 4 】。基于互联数据进行 语义关联发现的重要性，文献【1 1 】还提出了p q u e r y 查询机制发现复杂有意义的 关系。文酬1 4 】【1 5 】等探讨了在互联数据上进行语义关联发现的可行性，进一步提出 一些具有参考性的查询处理机制，用于在语义图上进行语义关联发现。文献【1 2 】【1 7 】 等提出一些可行的排序算法和策略，对语义关联发现结果进行排序。最后，实体 间的语义关联也可以从它们在同一事件中的共同出现情况推导得出【1 8 】。 语义关联发现作为关系发现的一种方法，其重要特征是领域本体驱动的。领 域奉体提供了标准词表来表述领域特定的关系，并允许从无结构或半结构化的文 档中自动或半自动的抽取关系。提高了关系发现的精确度和应用相关性。 然而上述的工作都是基于一个集中式的知识库，通过获取不同数据源的开放 6 浙江大学顾士学位论文第l 章绪论 互联数据集，将这些数据集合并、融合，生成一个集中的r d f 数据模型，在这个 模型的基础上进行语义关联发现。互联数据的高速动态增长，使得现有方法存在 以下不足： 可扩展性较差； 不符合互联数据分布式的特点； 数据存储的困难。， 1 4 本文的工作 针对现有语义关联发现方法的不足，本文提出并实现了一种多代理协作的分 布式语义关联发现框架。该框架具有较好可扩展性，更符合开放互联数据的分布 式特点。本文的创新性贡献有以下几点： ( 1 ) 提出了一种新的知识表示模型。用该模型表示假设、证据、证据图等知 识元素。新的知识表示模型有助于代理之间进行直接通信，相互协作。 ( 2 ) 提出并设计实现一种新的协作式语义关联发现机制。设计实现了目录代 理和挖掘代理两种类型代理。在协作的过程中，两类代理相互通信发布假设 和证据。这些相互依赖的假设和证据最后形成了证据图。通过对证据图的分 析，最后生成解答假设的完整语义路径。 ( 3 ) 实现了语义关联发现框架的核心算法：挖掘算法、调度算法、结果组合 算法，并研究了挖掘算法和调度算法可以采用的不同的策略。这些不同的策 略可以在代理协作挖掘过程中指导图搜索的方向和挖掘代理的选择。 ( 4 ) 对该多代理协作的分布式语义关联发现框架进行了模拟实验，并对它的 性能进行分析。 ( 5 1 将该框架应用于d b l p 和d b p e d i a 这两个开放互联数据集，挖掘人与人 之问潜在的语义关联。 1 5 论文结构 本文的第二章首先介绍了知识表示模型的相关概念，然后介绍了多代理协作 7 浙江大学硕l j 学位论文第1 章绪论 框架的体系架构。重点介绍了框架中的目录代理和挖掘代理，及代理之间的协作 交互过程。介绍了代理提供的服务，给出服务协议的具体规范。 第三章介绍了多代理协作框架的核心算法：挖掘算法、调度算法、结果组合 算法。 第p l q 章介绍了多代理协作框架在算法生成数据上的模拟实验结果。介绍了模 拟环境的设置，实验的流程，并给出结果分析。 第五章介绍了多代理协作框架在开放互联数据中的应用。以d b p e d i a 、d b l p 两个开放互联数据集为数据源，展示代理之间的协作发现的过程及结果。 第六章介绍了硕士期间所完成的项目。 第七章对多代理协作模型进行总结，分析可以进行改进的方向。 1 6 本章小结 本章中，介绍了语义网和互联数据的发展和在互联数据上进行语义关联发现 的可能性。介绍了语义关联发现的广泛应用领域及前人在语义关联发现方向所取 得的研究成果。针对现有方法的局限性提出了多代理协作的分布式挖掘框架。 8 浙江大学硕j j 学位论文第2 章系统体系架构没 第2 章系统体系架构设计 2 1 系统设计目标 多代理协作分布式语义关联发现框架将解决以下问题： 1 语义关联发现的目标 在多代理协作语义关联发现框架中，我们采用了假设驱动的方法，有效地缩 小进行语义关联发现所要分析的数据范围，提高了效率。在框架中，用户只需输 入关心的任意两个实体，系统据此自动生成假设，输出支持假设的解答，即找出 用户关心的两个实体之间的语义关联路径。系统根据核心算法通过找寻这两个实 体之间的语义路径试图发现两个实体之间潜在的语义关联。这种假设驱动的方法 可以做到只关心用户所提出的假设，可以减少无目标地对数据进行全部分析；并 具有通用性，用户只须输入两个实体，而不必关心实体涉及哪个领域。 2 代理之间的有效通信和协作 在多代理协作分布式语义关联发现框架中，我们提出一种新的知识表示模型 并设计了代理服务协议，该知识表示模型和服务协议是代理之间进行通信和协作 的必要条件。在框架中，多个代理进行通信和协作，涉及到知识的共享和交换。 系统中我们详细设计了代理服务协议，给出服务的规范定义，很好地解决了信息 的传递和解析问题。采用一致的知识表示，使得代理可以理解来自其他代理的信 息。这样的设计，使得代理不但在物理层上能够收发信息、在语法层上能够正确 的解析信息而且在语义层上能够理解信息，真正保证了代理之间的有效通信和协 作。 3 框架的可扩展性 在多代理协作分布式语义关联发现框架中，设计了目录代理和挖掘代理两种 类型的代理，使得系统可以通过增加挖掘代理的数量来处理日益增长的互联数 据，保证了框架的可扩展性。 系统包含1 个目录代理和多个挖掘代理。目录代理负责对注册的挖据代理进 9 浙江大学硕士学位论文第2 章系统体系架构设i 行管理。挖掘代理拥有局部知识库，能够处理自身拥有的局部丐= 联数据集，并在 该数据集上进行局部挖掘，发现潜在的语义关联。 一个挖掘代理的局部知识库只涉及单个特定的领域，有利于及时更新该领域 的知识，提高对该领域的知识发现能力。挖掘代理具有独立性和自主性，对于同 一个领域，可以通过增加挖掘代理来处理该领域新发布的互联数据集；对于新的 领域，可以通过增加挖掘代理，设定新代理的知识库，拓展框架町以处理的领域 范围。 在下文中，将详细介绍基于多代理协作分布式语义关联发现框架的架构设 计。首先，介绍知识表示模型，对框架中涉及的概念提出形式化的定义。然后介 绍多代理协作框架的架构，介绍框架中的两类重要代理：目录代理和挖掘代理； 目录代理和挖掘代理之问的交互过程。最后，介绍代理所提供的服务，并给出服 务规范定义和服务协议。 2 2 知识表示模型 知识表示模型是多代理协作分布式语义关联发现框架的基础。它定义了假 设、证据等知识元素；定义了这些知识元素之间的关系；定义了代理之间的关系。 这种新的知识表示模型更有利于协作式的语义关联发现，更适合多代理之间进行 知识交换和共享。 下面对知识表示模型中的知识元素和关系给出详细的定义。 r d f 陈述是一个三元组 ，其中，s 表示主体，p 表示谓词，0 表示客体。 语义关联( s a ) 是一个r d f 陈述，它表示主体s 与客体0 之间的存在类型p 的关 系。在r d f 图中，语义关联表示为j 山d 。 假设是可靠性不确定的语义关联，它所宣称的主体与客体之问的关系有待进 一步的验证。下面是假设的形式化定义。 定义l 假设( h y p o t h e s i s ) 假设h 是一个六元组 ，其中u 表示h 的u r i 引用标识；s 表示h 的主体，p 表示h 的谓词，0 表示h 的客体；a 表示h 的作者，l 表示解答h 的路 1 0 浙江大学硕1 ：学位论文第2 带系统体系架构设i f 径长度。假设图形化表示如图2 1 所示。 a s p o 图2 1 假设 一个假设h 可以由它的u r i 引用唯一标识或者由它的问题 及解答路径 长度限制l 来标识。因此h 可以表示为办( 甜) 或h ：s 屿0 。当，不设置时，表 示不限制路径长度，可以表示为 ；当p 不设置时表示不限定谓词关系。 根据假设是否被完全证明，假设分为两种状态： ( 1 ) 封闭( c l o s e d ) 的假设：假设被封闭的证据所证明。 ( 2 ) 开放( o p e n ) 的假设：假设未被证明或证明假设的证据是开放的。 根据假设的提出者的类型，假设分为两类： ( 1 ) 原生假设：由用户提出的假设，即系统要解决的初始假设，代理协作解 答的目标。 ( 2 ) 衍生假设：挖掘代理在解答过程中产生的新的假设。新的假设的产生是 代理之间协作的前提。 证据可以是有助于代理验证假设可靠性的任何资源在本文中仅讨论符合语 义规范的形式化的证据。 定义2 证据( e v i d e n c e l 证据e 是一个三元组 ，其中u 表示e 的u r i 标识；g 表示e 的内容，是 语义关联的集合，a 表示e 的作者。证据图形化表示如图2 2 所示。 浙江大学硕上学位论文第2 审系统体系架构设计 图2 2 证据 s a l s a n 一个证据e 可以由它的u r i 引用唯一标识e ( u ) 或者表示为一条语义路径。 如 证明 假设h ：s 屿o的 证 据可以表示为 s j o ：s 上山q 上山乞。q 血o d 。 根据证据是否完全支持验证假设，可以分为两类： ( 1 ) 开放的证据：证据的语义路径中包含假设。对于给定的假设s 玛d ， 开放的证据形如s 2 屿c 卫! l 专d 。 ( 2 ) 封闭的证据：封闭的证据是一条不包含假设的语义路径或它的语义路径 中所包含的假设已经被证明。例如，对于给定的假设s 玛d ，有证据 e l ：s 世_ c 卫盟一d ，其中e 1 所包含的假设c 卫b d 已经被证据p 2 ： c 且b 4 ”办：丘屿d 所证明，我们说q 是封闭的。 定义3 依赖关系 证据和假设之间的这利一验证和包含的关系，可以形式化的表示为证据与假设 之间的依赖关系。 ( 1 ) 当证据e 验证假设h ，我们就宣称h 依赖e ，表示为 ，在r d f 图中表示为厅业2 旦! 屿p ；或宣称e 支持h ，表示为 ，在r d f 图 中表示为p 业哟办。 ( 2 ) 当开放的证据e 中包含假设h 时，我们就宣称e 依赖h ，表示为 ，在r d f 图中表示为p 鲤立2 屿厅；或宣称h 支持e ，因为当h 被 1 2 一一 浙江大学硕i ：学位论文第2 章系统体系架构设计 解答时，e 就转化成封闭的证据，表示f o ，在r d f 图中表示为 厅翌2 1 与p ( 3 ) 在( 1 ) ( 2 ) 中属性d e p e n d s 和s u p p o r t s 互为逆属性， 即 办生型屿p ，p 磐e 臣q 办。 ( 4 ) 在本文中我们不讨论由属性d e p e n d s 和s u p p o r t s 的传递性所产生的证据和 证据、假设和假设的间接依赖关系。 证据和假设的直接依赖关系，形成了证据图。 定义4 证据图和逆证据图 证据图是一个有向图e g = ( v ，d ) 其中v 是点集，矿= 日ue 且日n e = 彩， h 是假设的点集，e 是证据的点集；d 是边的集合，表示d e p e n d s 关系。 根据属性d e p e n d s 的逆属性s u p p o r t s ，我们只要反转每条边的方向，就得到逆 证据图。 逆证据图e g = ( 矿，s ) ，其中v 是点集，y = 日ue 且日ne = 囝，h 是假设 的点集，e 是证据的点集；s 是边的集合，表示s u p p o r t s 关系。 定义5 接受关系 代理接受( a c c e p t s ) 假设和证据，则表示代理相信这些假设和证据是真实的。 属性a c c e p t s 的逆属性为a c c e p t s b y ，表示假设和证据被谁接受。 代理接受假设和证据的条件为： ( 1 ) 证据是封闭的证据 ( 2 ) 开放的证据，但证据所依赖的假设是封闭的。 ( 3 ) 封闭的假设，即该假设依赖的证据是封闭的。 当两个实体之间的关系是 关系时，我们称两个实体是相等的。本 系统只考虑显示的相等关系，不考虑通过算法的方式推导得出的实体相等关系。 定义6 邻居关系 当挖掘代理拥有的知识库中的数据与另一代理的知识库中的数据有部分实 体是相等的，即在互联数据中，一个数据集中有数据通过 链接到另 浙江大学硕上学位论文第2 章系统体系架构设计 一数据集中的数据，称两个挖掘代理为邻居。挖掘代理的邻居关系代表了挖掘代 理进行协作的可能性。 2 3 系统架构 在多代理协作分布式语义关联发现框架中，我们设计并实现了两类知识发现 代理：目录代理和挖掘代理，确定了每种类型代理在框架中的角色和作用，详细 定义了各类型代理所提供的服务协议，代理之间的通信流程。 目录代理接收用户提出的假设，并将假设解答任务根据全局调度算法按照相 应的策略分配给挖掘代理进行解答。最后将挖掘代理产生的解答组合起来，提供 给用户完整的解答结果。挖掘代理接受分派的假设任务，根据局部挖掘算法，在 代理所拥有的局部知识庠巾产生部分或完整的解答，其中不完整的解答则产生衍 生的假设，并将衍生的假设根据局部调度算法分派给系统中的其他挖掘代理进行 解答。语义关联发现的过程即是目录代理和挖掘代理相互协作，共同解答用户提 交的假设的过程。 如图2 3 为系统的架构图，最下层为知识库，可以存储在数据库中，也可以 以文件形式存在。中间一层为挖掘代理，每个挖掘代理拥有自己的知识库。挖掘 代理之间也可以相互通信。最上层为目录代理，目录代理负责调度下层的挖掘代 理，协同工作。 1 4 囤23 系统架构图 2 31 目录代理 目录代理在多代理协作分布式语义关聩发现框架中负责整个语义关联发现 过程的协调和调度，它的主要功能包括： r 1 ) 挖掘代理注册管理。目录代理维护了一个目录，日录中的条目包含了挖 掘代理求解问题能力的描述信息和目录代理自身的描述信息。目录中还包含 r 代理所提供的服务的信息。 r 2 ) 挖掘代理调度。h 录代理将假设分派给有可能解答假设的挖掘代理。 r 3 1 证据生成。目录代理在证据图e 搜索与假设相关的证据