（计算机应用技术专业论文）基于概念相似度的语义web服务发现方法.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 研究生签名：堑? 缁日期：! 删 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括干u 登) 授权东南大学研究生院办理。 研究生签名：鳖导师签名： 缘日 期：型! ：! ：! i 摘要 摘要 基于u d d i 的服务注册与发现机制无法准确刻画服务能力且服务发现过程仅依赖关 键字搜索，服务发现效果无法满足用户需求。语义w e b 服务基于传统w e b 服务，嵌入 语义信息以准确描述w e b 服务，具有高度的互操作、跨平台、松耦合和易部署等特性。 然而如何准确而有效地发现满足用户需求的w e b 服务是一个亟待解决的关键问题。 服务发现的核心是服务匹配，服务匹配的基础是概念间语义相似度的计算。本文充 分考虑本体树结构特点，分析概念间边类型、深度、密度对相似度的影响，提出一种改 进的概念相似度计算方法，比现有概念语义相似度更接近领域专家的判断，可提高服务 匹配的查准率和查全率；基于概念相似度表及概念服务索引表，提出有效的服务候选集 确定算法，通过降低服务查找空间，提高服务发现效率；将服务匹配问题转化为二分图 最佳匹配问题，提出相应的二分图服务匹配算法，寻找请求服务和广告服务输入输出间 的最佳匹配，准确而高效地实现服务匹配。 本文采用o w l s t c 测试实例进行仿真实验，将本文所提算法与当前两个最好算法 进行比较。实验结果表明所提算法在查全率和查准率上都优于其他两个算法，有效性得 到充分验证。 关键字：语义w e b 服务，服务发现，服务匹配，概念相似度 a b s t r a c t t h es e r v i c er e g i s t r ya n dd i s c o v e r yp o l i c yb a s e do nu d d ic a n n o ts a t i s f y c u s t o m e r r e q u i r e m e n t sf o rt h ew e a k n e s si n s e r v i c ec a p a b i l i t yd e s c r i p t i o na n dt h ek e y w o r d - b a s e d s e a r c h i n gm e t h o d b a s e do nt h et r a d i t i o n a l w e bs e r v i c e ，s e m a n t i cw e bs e r v i c e i s c h 剐a c t e r i z e dw i t hh i g hi n t e r o p e r a b i l i t y , g o o dc r o s s - p l a t f o r mc a p a b i l i t y , l o o s ec o u p l i n ga n d e a s yd e p l o y m e n t ，a n dc a np r e c i s e l yd e s c r i b e s e r v i c ec a p a b i l i t i e si nt e r m so fs e m a n t i c i n f 0 n n a t i o n h o w e v e gh o w t od i s c o v e rs e r v i c e se f f e c t i v e l yt om e e tc u s t o m e rr e q u i r e m e n t si s ak e yp r o b l e m t h es e n ，i c em a t c h i n gi st h ek e yt ot h es e r v i c ed i s c o v e r y , a n dt h ec o n c e p ts i m i l a r i t yi s c r i t i c a lt ot h es e r v i c es e m a n t i cs i m i l a r i t yc a l c u l a t i o ni nt h es e r v i c em a t c h i n g a ni m p r o v e d c o n c e p ts i m i l a r i t yc a l c u l a t i o nm e t h o di sp r o p o s e d a c c o r d i n gt ot h es t r u c t u r ec h a r a c t e r i s t i c s o ft h eo n t o l o g yt r e e ，e f f e c t so ft h ee d g et y p e ，d e p t ha n dd e n s i t ya m o n gc o n c e p t se x e r t i n go n s i m i l a r i t ya r ea n a l y z e d t h i sm e t h o do b t a i n sm o r ee x p e r tk n o w l e d g et h a nt r a d i t i o n a lw a y s ， w h i c hc a ni m p r o v et h er a t i oo fp r e c i s i o na n dr e c a l l b a s e do nt h ec o n c e p ts i m i l a r i t yt a b l e a n dc o n c e p t s e r v i c ei n d e xt a b l e ，a ne f f e c t i v ea l g o r i t h m i sp r e s e n t e dt oc o n s t r u c tt h e c a n d i d a l c es e t t h es e a r c hs p a c ei sr e d u c e da n d t h es e r v i c ed i s c o v e r ye f f i c i e n c yi si m p r o v e d b yt r a n s f o r m i n gt h es e r v i c em a t c h i n gt ot h eb i p a r t i t eg r a p hm a t c h i n g ，as e r v l c em a t c h i n g a l g o r i t h mi sp r o p o s e dt oe x p l o r et h eb e s t s e r v i c ea n dt h o s eo ft h ea d v e r t i s eo n e m a p p i n gb e t w e e ni n p u t s o u t p u t so ft h er e q u e s t k e y w o r d s ：s e m a n t i cw e bs e r v i c e ，s e r v i c ed i s c o v e r y , s e r v i c em a t c h i n g ，c o n c e p t s i m i l a r i t y 目录 目录 摘要i a b s t r a c t i i 目录i i i 第l 章绪论l 1 1 研究背景和意义l 1 2 国内外研究现状1 1 3 相关技术。2 1 3 1w e b 服务概述3 1 3 2 语义w e b 概述4 1 3 3 本体描述语言o w l 5 1 3 ，4 语义w e b 服务描述语言o w l s 6 1 4 论文主要内容8 1 5 论文结构8 第2 章概念语义相似度计算方法9 2 1 概念语义相似度计算方法的分析与比较9 2 2 改进的概念语义相似度计算方法l l 2 2 1 概念间边类型、深度、密度与权重的关系分析1 2 2 2 2 基于语义距离的改进概念相似度计算方法1 3 2 3 本章小结1 6 第3 章基于概念相似度的语义w e b 服务匹配算法1 7 3 1 服务语义相似度的定义1 7 3 2 服务候选集确定算法1 9 3 3 基于二分图的服务匹配算法2 0 3 4 本章小结2 4 第4 章算法实现与评价2 5 4 1 实验环境2 5 4 2 算法实现2 5 4 3 实验结果与分析2 7 4 3 1 测试实例2 7 4 3 2 实现结果2 7 4 3 3 实验结果比较与分析2 9 4 4 本章小结3l 第5 章总结与展望3 2 5 1 工作总结。3 2 i i i 目录 5 2 后续工作展望3 2 骛【谢3 4 参考文献3 5 攻读学位期间发表的学术论文3 7 i v 第1 章绪论 第1 章绪论 1 1 研究背景和意义 随着互联网的高速发展，异构环境下的互操作需求日益紧迫，w e b 服务应运而生。 w e b 服务基于x m l ，解决了异构分布式计算以及代码与数据重用等问题；高度的互操 作性、跨平台性、松耦合和易部署等特点较好的满足了当前业界的需求；开放的业务供 应方式，改变了互联网上数据相互孤立的格局。w e b 服务已经成为分布式计算和面向服 务计算的主流技术。语义w e b 由“互联网之父”t i mb e m e r s l e e 提出，将智能的、机器可 理解的信息融入现有w e b 技术以实现访问异构和分布式资源。语义w e b 技术核心是准 确描述网络资源语义，使应用程序得以理解并自动化处理网络资源。 语义w e b 服务结合了传统w e b 服务和语义w e b 的优点。利用语义w e b 丰富的语义 描述能力和强大的逻辑推理能力准确描述w e b 服务，使计算机得以理解，从而实现w e b 服务的自动发现、选择和组合。传统的基于u d d i ( u n i v e r s a ld e s c r i p t i o n d i s c o v e r y , a n d i n t e g r a t i o n ) 的服务注册与发现机制仅支持对服务语法层面的操作，一方面在服务注册阶 段无法准确刻画服务能力，另一方面在服务发现过程中仅提供基于关键字的服务匹配策 略，服务发现效果显然无法满足用户要求。特别是在服务数量剧增的情况下，用户面临 大量功能相似服务，因此，如何准确而有效发现满足用户需求的语义w e b 服务是一个 亟待解决的关键问题，其核心是语义w e b 服务匹配。提出高效语义w e b 服务发现方法 和匹配算法，对语义w e b 服务选择、组合、执行等具有重要意义。 1 2 国内外研究现状 国内学者针对语义w e b 服务发现问题进行了广泛而深入的研究，取得了丰富的研 究成果。中国科学院史忠植等i i 】将语义w e b 服务表示为( 概念：动作) ，运用描述逻辑对 本体概念进行分层推理，实现相似度匹配。国防科技大学胡建强等f 2 】提出了q w s d l 描 述语言和“三层次、五类型”的匹配模型，从基本描述、基调描述、服务质量等方面描述 语义w e b 服务，基于松弛匹配构造相似函数以度量服务相似度。吴健【3 】等提出了基于本 体论和词汇语义相似度的语义w e b 服务发现方法，通过构建语义w e b 服务本体，给出 一个语义w e b 服务发现的研究对象，提出几种相似度计算方法，详细讨论词汇语义相 似度的计算过程。刘振鹏等1 4 j 提出一种基于服务质量q o s 的语义w 曲服务选择算法， 先将含有语义信息的广告服务和请求服务进行相似度匹配，对达到相似度达到一定要求 的广告服务，进行q o s 评价，选择出一个q o s 值最大的服务。邝砾等1 5 】提出为服务库 中所有广告服务的输出建立倒排索引，基于倒排索引机制，设计面向组合的服务发现算 法，极大的减少了搜索空间，并通过挖掘服务组合提高服务发现的查全率。彭晖等【6 l 提 出一种基于动态描述逻辑的语义w e b 服务描述与匹配方法，利用动态描述逻辑发现与 目标服务匹配的原子服务组合。孙萍等1 7 l 提出利用服务聚类优化面向过程模型的语义 东南大学硕士学位论文 w e b 服务发现框架，利用聚类技术，从服务的功能相似和过程相似两个层面对服务进行 聚类预处理，降低了服务的查找空间。针对请求服务中可能潜在的行为约束，建立基于 p e t r i 网的过程需求模型，将其与候选服务的过程模型进行比较，对满足功能需求的服务 进一步筛选，从而提高查准率。 国外，m a r kk l e i n 等1 8 , 9 j 提出一种基于过程本体的语义w e b 服务发现方法，利用过 程本体描述请求服务与广告服务，匹配请求服务和广告服务的过程本体，从而得到所需 服务。该算法大大提高了服务匹配精度，但过分依赖过程模型，建模方式不同或过程模 型不准确，直接影响服务发现结果，且算法实现的复杂度较高。卡耐基梅隆大学软件 智能实验室的p a o l u c c i 等【lo 】开发了基于d a m l s 描述语言的a u g m e n tu d d i 语义w 曲 服务注册系统，利用本体概念间的包含关系匹配服务输入和输出，因为该匹配算法基于 p r o l o g 推理，返回结果均为精确匹配服务，所以具有很高的查准率。美国乔治亚大学 l s d i s 实验室的m e t e o r - s 系统1 1 1 , 1 2 】采用了语义本体论推理和q o s 策略相结合的服务 匹配和筛选方法，服务查准率高，但服务匹配效率不佳。由于使用的是简单的基于服务 模板的匹配算法，故而不能支持复杂的逻辑推理。德国人工智能研究中心的k l u s c h 等 毛1 4 j 开发了一种基于逻辑推理和语法相似度计算相结合的匹配器o w l s m x ，基于本体 概念间包含关系定义5 种匹配度( e x a c t 、p l u g i n 、s u b s u m e s 、s u b s u m e d b y 和 n e a r e s t n e i g h b o r ) 。其中前3 种基于逻辑推理，后两种属混合类型，需计算本体概念间 的语法相似度，分别基于4 种语法相似度计算方法：l o s s o f - i n f o r m a t i o n 、e x t e n d e d j a c q u a r d 、c o s i n es i m i l a r i t yv a l u e 和j e n s e n s h a n n o ni n f o r m a t i o nd i v e r g e n c e 。该算法查准率 高，较好地利用了语义w e b 中基于逻辑描述的推理技术，同时结合语法相似度的计算 提高了算法的查全率。f e n z e 等1 1 5 , 1 6 】提出一种基于模糊多重集与模糊聚类的混合匹配方 法，对服务输入和输出描述中的概念建立模糊多重集并进行模糊聚类，根据聚类中心找 出匹配服务候选集。该算法应用了模糊聚类策略，具有较高的查全率。 综上所述，现有服务匹配算法通常弱化概念间关系，仅考虑相等及包含与被包含两 种关系，无法覆盖概念间所有关系，影响服务匹配的查准率；确定服务候选集时，仅把 拥有与请求服务涉及概念相同的广告服务选入服务候选集，遗漏了具有与请求服务涉及 概念相似的广告服务，影响服务匹配的查全率；描述服务匹配结果较粗糙，只分等级而 不提供具体的相似度，难以区分同等级中的服务匹配情况。 1 3 相关技术 语义w e b 服务是w e b 服务和语义网技术的结合，它把语义网的研究成果引入w e b 服务中，可以实现自动化的服务发现、调用、组合、监视和恢复。语义网的研究将使得 访问w e b 资源不再仅仅依靠关键字来查找和访问，而是根据内容来访问。w e b 服务作 为w e b 上的一类越来越重要的资源，同样要求语义网对其提供广泛的语义支持，从而 实现语义w e b 服务。 2 第i 章绪论 1 3 1w e b 服务概述 w 曲服务是可以通过w e b 描述、发布、定位和调用的模块化应用。w 3 c 这样定义 w e b 服务：“w r e b 服务是一种软件系统，被设计用来支持网络上机器与机器之间的互操 作；它有一个以机器可以处理的格式( w s d l ) 描述的接口；其它系统通过s o a p 消息以 w e b 服务指定的方式与之交互，s o a p 消息通常以x m l 序列化的形式采用h t t p 协议 以及其它w e b 相关标准进行传输。”从上述定义可以看出，w e b 服务本质上是一种应用 程序之间的通信机制，它独立于硬件平台、操作系统和编程语言。w e b 服务有一个软件 接口，它描述了一组在网络上可以通过标准化的x m l 消息传递进行访问的操作。 w e b 服务的目的是要解决异构平台上数据和应用的整合与共享问题，以前的许多分 布式技术也试图解决这个问题，如c o r b a 、d c o m c o m + 和r m i 等，但是这些技术 要么过于复杂、难以使用，要么不能穿透防火墙，不能在i n t e m c t 上进行工作，并且不 同标准之间不易实现互操作。w e b 服务技术很好地解决了这些问题，它使用开放的标准 x m l 来描述与服务交互的所有必需细节，包括消息格式、传输协议和位置，它的接口 隐藏了实现的细节，使得它独立于编写它的语言和实现它的软硬件平台。这样基于w e b 服务技术实现的应用具有松耦合性，也能够被组合起来以完成更复杂的功能。 在w e b 服务体系结构中包括三种角色和三种操作，这三种角色是服务提供者、服 务务请求者和服务注册中心，这些角色完成的操作是发布、查找和绑定，操作的对象是 服务和服务描述。服务提供者创建w e b 服务，并用w s d l 来描述该服务，然后通过u d d i 在服务注册中心注册该服务；服务请求者通过u d d i 接口在注册中心查找所需的服务， 注册中心将会返回满足需求的服务的w s d l 描述以及指向服务本身的u r l ，借助于这 些信息，服务请求者就能够绑定并调用该服务。 在w e b 服务体系中，使用w s d l 来描述服务，u d d i 来发布、查找服务，s o a p 来执行服务调用，在w e b 服务之间进行消息传递，它们是w e b 服务最基本的三项技术： ( 1 ) s o a p s o a p 是一个基于x m l 的在分布式环境中交换信息的协议。它包括四个部分： s o a p 封装，它定义了一个描述消息中的内容是什么、是谁发送的、谁应当接受并 处理以及如何处理的框架；s o a p 编码规则，它用于表示应用程序需要使用的数据 类型的实例；s o a pr p c ，它表示远程过程调用和应答的协定；s o a p 绑定，使用 底层协议交换信息。任何传输协议都可以用来交换s o a p 消息，只要发送和接收消 息的应用程序理解该协议即可。 ( 2 ) w s d l w s d l 是一种基于x m l 的用来描述w e b 服务接口的标准，用以指明w e b 服 务中使用的方法、数据类型、使用的传输协议和w e b 服务宿主的终点u r l 。w s d l 将w e b 服务描述为能够对消息进行操作的服务访问点的集合。操作和消息都被抽 象地描述，然后绑定到一个具体的网络协议上，而消息格式定义了一个服务访问点， 相关的具体服务访问点被合成抽象的服务访问点。w s d l 是可扩展的，允许对服务 东南大学硕士学位论文 访问点和他们的消息进行描述而不考虑用于通讯的消息格式或者网络协议。 ( 3 ) u d d i u d d i 是o a s i s 发起的一个项目，它是一个基于x m l 的规范，可以使世界范 围内的企业在互联网上发布自己所提供的w e b 服务，并查找所需的w e b 服务。各 公司可以使用u d d i 描述其商业过程，描述信息包括三部分： 白页：有关企业的基本信息，如地址、联系方式以及已知的标识； 黄页：基于标准分类的类别信息； 绿页：与服务相关联的绑定信息，以及指向这些服务所实现的技术规范的引用。 这些描述信息可以被存储到注册中心。同时，u d d i 规范还提供了一种可以对这种 描述信息进行发布和查找的方法。u d d i 是最常用的w e b 服务发现标准，但还有 其它的技术也能用于w e b 服务的发现，如e b x m l 和w s i n s p e c t i o n ，它们都可以和 u d d i 结合起来使用。 1 3 2 语义w e b 概述 传统的h t m l 标记语言只对内容的显示格式做了标记，数据的表现格式和数据揉 合在一起，缺乏针对数据内容的标签，从而使得w e b 上的信息内容难以被机器所理解， 制约了需要对w e b 上的海量数据进行自动化处理应用的开发。近年来出现的w e b 新标 准x m l 可以根据用户需要制定能反映数据内容的标签，实现数据内容和数据表现形式 的分离。x m l 及其相关技术，使传统w e b 上的信息内容从面向人浏览转为同时面向计 算机自动处理迈出了重要的一步。面向计算机自动处理的前提是机器能够理解某个概 念，即能够执行一些和这个概念相关的查询或其他操作。语义w e b 就是一个由大量机 器可以理解的数据构成的体系结构，其中数据之间的关系通过一些术语表达，这些术语 之间又形成一种复杂的网络关系，计算机能通过术语得到数据的含义，并通过逻辑推理 完成一些原来机器不能直接完成的工作。 语义w e b 之父t i m b e r n e r s l e e 对语义w e b 做如下描述：语义w e b 是对当前w e b 的扩展，语义w e b 上的信息具有定义良好的含义，使得计算机之间以及人类能够更好 的彼此合作。从语义w e b 的起源发展看来，语义w e b 是人工智能领域和w e b 技术相互 结合的产物。语义w e b 建立的基础是知识的概念化和形式化以及相应的推理，与人工 智能有深厚的渊源，许多分析都需要从人工智能领域的角度考察。 b e m e r s l e e 在x m l 2 0 0 0 大会上描述了语义w e b 的体系结构。如图1 1 所示【1 7 】， 语义w e b 采用统一编码u n i c o d e 作为字符编码方案以便涵盖网络上各种语言和文字的 信息资源。u r i ( u n i f o r mr e s o u r c ei d e n t i f i e r s ) 是一个i n t e m e t 标准，泛指所有以字符串标 识的网络资源，包含了u r l ( u n i f o r mr e s o u r c el o c a t o r ) 和u r n ( u n i f o r mr e s o u r c en a m e ) 。 u n i c o d e 和u r i 是语义w e b 的基石，成功解决了w e b 上资源定位和跨地区字符编码的 标准格式的问题。在u n i c o d e 和u r i 之上，是x m l 及其相关技术层。x m l 允许用户 根据需要自定义标签对发布的内容进行标记，并使用文档类型定义d t d 或x m ls c h e m a 来约束标签结构。为了避免用户自定义标签重名的情况，w 3 c 采用了n a m e s p a c e 机制。 4 第1 章绪论 但x m l 只是解决了文档内容的结构、次序的问题并没有解决文档内容的语义问题。所 以标签的含义的定义和互操作要由上层解决。资源描述框架r d f ( r e s o u r c ed e s c r i p t i o n f r a m e w o r k ) 和r d fs c h e m a 是数据互操作层，r d f 是一个开发的元数据框架，定义了一 种机器可以理解的描述数据语义的数据模型，主要包括三个对象类型：资源、特性和声 明。资源可能是整个网页或网页的一部分或是不能通过网络直接访问的对象。特性是描 述某个资源特定的方面、特征、属性或关系。一个的资源和某特性名称加上该特性的值， 三者就构成了一个r d f 声明。r d fs c h e m a 可以定义类、子类、超类，并且可以定义特 性和子特性，以及它们的约束如：领域和范围等。r d f r d f s 层之上为o n t o l o g y 层。 入 l 3 信任 卜 规则 l 3 证明 i n 数据 _ 一 肄 八 隧磊貔磊i 磊自貔象蠹女蕴：缸& 缓自貂巍& 缢荔蠡荔磊貔缓渤* l 玉数据 踌 自述 本体词汇椅 文件 + ；? | 7 ? 1 + 。 。 ：，。j ，。， l r d f + r d f s c h e m a _ 黟。? 。7 。锄 x m l + n s ，+ x m l s c h e m al 匕二二二二照纛。：。二二鍪要至墨= ：i 图1 1 语义w e b 架构图 1 3 3 本体描述语言o w l 关于本体( o n t l o g o y ) ，g r u b e r 1 8 1 在1 9 9 3 年给出了一个最为流行的定义，即“本体是 概念模型的明确的规范说明”。s t u d e r 等【1 9 j 在对本体做了深入研究后，扩展了g r u b e r 的 定义，认为“本体是共享概念模型的明确的形式化规范说明”，该定义包含四层含义：概 念模型，即本体是通过抽象客观世界的概念而得到的模型，它表示的含义独立于具体的 环境状态；明确性，即本体所使用的概念及在这些概念之上的约束都有明确的定义，没 有二义性；形式化，即本体是计算机可处理的，而不是自然语言；共享，即本体体现的 是共同认可的知识，反映的是相关领域中公认的概念集合，它所针对的是团体而不是个 体。p e r e z 等【2 0 】采用分类法组织本体论，并归纳出五个基本的本体建模元语： 类或概念：指任何事务，如工作描述、功能、行为、策略和推理过程。从语义上讲， 它表示的是对象的集合，其定义包括概念的名称，与其它概念之间的关系的集合， 以及对概念的自然语言描述。 关系：在领域中概念之间的交互作用，形式上定义为n 维笛卡儿积的子集：r ： c 1x c 2 x x c n ，从语义上讲关系对应于对象元组的集合。 东南大学硕士学位论文 函数：是一类特殊的关系。即前n 1 个元素可以唯一决定第n 个元素。形式化的定 义为映射f ：c 1x c 2 x x c n 1 一c n 。 公理：代表永真断言。 实例：代表元素，从语义上讲实例表示的就是对象。 其中概念间的四种基本关系： p a r t o f ：表示概念之间部分与整体的关系。 k i n d o f ：表示概念之间的继承关系，类似于面向对象中父类和子类的关系。 i n s t a n c e o f ：表示概念的实体与概念之间的关系，等同于面向对象中对象和类的关 系。 a t t r i b u t e o f 表示某个概念是另一概念的属性。 在实际建模过程中，不一定要严格地按照上述五类基本建模元语来创建本体，概念 间的关系也不限于上述四种基本关系，可以根据领域的具体情况定义相应的关系，以满 足应用需要。 o w l 剐( o n t o l o g yw e bl a n g u a g e ) 是由w 3 c 组织推荐的用来表示w e b 上本体的标准 语言，它从d a m l + o i l 描述语言发展而来，基本思想是在表达能力和推理复杂度之 间取得平衡：既满足表达w e b 上信息的需求，又控制推理复杂度，方便应用的开发。 o w l 文档是一个标准的x m l 文档，它通过对r d f 进行扩展和施加约束来表达诸如子 类、等价类、特征属性、公理等丰富的语义信息。 o w l 采用面向对象的方式来描述领域知识，即通过类和属性的概念来描述对象， 并通过公理来描述类和属性的特征和关系： o w l 类( c l a s s ) ：类是组织具有相似特征的资源的一种抽象方式。每一个o w l 类联 系到一个个体( i n d i v i d u a l ) 的集合，这些类被称为对象类，这个集合则是它的外延， 集合中的个体叫做类的实例( i n s t a n c e ) 。元素o w l ：c l a s s 用来定义一个对象类，可通 过指定类的名字或者说明一个匿名的类的外延来描述这个类。此外，还可以通过 r d f s ：s u b c l a s s o f 来定义类的层次结构。 o w l 属性( p r o p e r t y ) ：是描述类之间关系的抽象机制，可看作是类之上的二元关系， 属性之间可通过s u b p r o p e r t y o f 形成层次化结构。o w l 属性分为两类：将对象与其 它对象关联起来的对象属性( o b j e c tp r o p e r t y ) s 1 将对象与数据类型关联起来的数据类 型属性( d a t a t y p ep r o p e r t y ) ，对象属性的值域是类的个体的集合，而数据类型属性的 值域是数值类型的值，如整数、字符串等( 由x m ls c h e m a 定义) 。 o w l 个体( i n d i v i d u a l ) ：是组成类的元素，被称为类的实例。个体通过使用r d f ：t y p e 来将自己绑定到某个类上。 1 3 4 语义w e b 服务描述语言o w l s o w l 。s 【2 2 ( o n t o l o g yw e bl a n g u a g ef o rs e r v i c e ) 就是一种用来描述w e b 服务属性和 功能的o w l 本体规范，它使用一系列基本的类和属性来描述服务，提供了一个可共享 6 第1 章绪论 的框架，使得w e b 服务成为计算机可理解的实体，从而便于实现服务的自动发现、选 择、调用、互操作、组合以及执行监控等。 o w l s 主要包括s e r v i c e p r o f i l e 、s e r v i c e m o d e l 和s e r v i c e g r o u n d i n g 三类上层本体， 它们分别描述了服务具备的功能、服务如何执行、服务如何访问等语义信息。具体如下： ( 1 ) s e r v i c e p r o f i l e s e r v i c e p r o f i l e 主要包含关于w e b 服务的三方面信息：服务的非功能性信息，服务 的功能信息和服务的一些附加特征信息。服务的非功能性信息提供了用户可读的信息， 这些信息一般不能进行自动化地处理，主要包含服务名称( s e r v i c e n a m e ) 、服务的文字描 述( t e x t d e s c r i p t i o n ) 和服务提供者的联系信息( c o n t a c t l n f o n n a t i o n ) 。服务的功能信息是 s e r v i c e p o r f i l e 中最本质的部分，它由输入、输出、前置条件和效果( i n p u t ，o u t p u t ， p r e c o n d i t i o n 和e f f e c t ，简称l o p e ) 组成。p r o f i l e 本体通过h a s l n p u t 、h a s o u t p u t 、 h a s p r e c o n d i t i o n 、h a s e f f e c t 等属性来描述l o p e ，但所有l o p e 的实例都在p r o c e s s 部分 创建，p r o f i l e 的实例只是简单地指向这些实例。服务的附加特征信息包括服务的分类信 息和服务的q o s 信息，如服务承诺的质量等级、服务所属的分类、服务的响应时间、 服务覆盖的地域范围等。 ( 2 ) s e r v i c e m o d e l s e r v i c e m o d e l 用来描述服务的内部流程，即服务如何工作，包括服务执行时发生的 操作、具体的逻辑执行顺序、服务间交互的协议，并说明了抽象消息和被传输信息的本 体类型。具体来说，过程分为三类：原子过程( a t o m i cp r o c e s s ) 、复合过程( c o m p o s i t e p r o c e s s ) 和简单过程( s i m p l ep r o c e s s ) 。原子过程是不可再分的过程，可以直接被调用。 复合过程定义了由若干个原子和复合过程构成的过程。复合过程详细说明了过程如何协 同工作以完成复杂的功能。同时，复合过程定义了控制流和数据流。控制流详细说明了 不同的子过程在执行上的时间关系，例如顺序( s e q u e n c e ) 、选择( c h o i c e ) 等。数据流详细 说明了一个过程产生的数据如何被另一个过程调用。简单过程提供了一个抽象的封装， 可被用做某些原子过程的视图或复合过程的简单表达，不能被直接调用，也不能与 g r o u n d i n g 绑定。 ( 3 ) s e r v i c e g r o u n d i n g s e r v i c e g r o u n d i n g 描述了如何来访问服务，涉及到访问服务所需要的具体信息，包 括服务访问的协议、消息格式、地址和端口等。o w l s 规范中没有定义语法成分来描 述这些信息，而是利用w s d l 来描述。s e r v i c e g r o u n d i n g 可看作是从抽象的概念描述到 具体服务的映射过程，在w s d l 和p r o c e e s 之间起桥梁作用。分别需要进行三方面的映 射：o w l s 中的a t o m i cp r o c e s s 映射到w s d l 的o p e r a t i o n ； o w l s 中的a t o m i c p r o c e s s 的输入和输出对应w s d l 操作中的m e s s a g e ； o w l s 中的i n p u t 和o u t p u t 的 类型对应w s d l 中的抽象类型。 东南大学硕士学位论文 1 4 论文主要内容 本文充分利用语义w e b 服务中语义信息，设计并实现一种语义w e b 服务的匹配方 法以提高语义w e b 服务发现的查全率和查准率。论文主要内容如下： ( 1 ) 提出一种改进概念语义相似度计算方法。该方法充分考虑本体树结构，综合影 响概念相似度的3 大主要因素，从而使概念相似度更接近领域专家的判断。 ( 2 ) 提出服务候选集的确定算法。对服务的输入、输出概念建立索引和相似度表， 扩展传统的基于概念相同原则的选择策略，拥有与请求服务涉及概念相似的广 告服务均可选入服务候选集，从而扩大了服务候选集的覆盖度，提高查全率。 ( 3 ) 提出基于二分图的服务匹配算法。将语义w e b 服务匹配问题转化为二分图最佳 匹配问题，扩展现有二分图匹配方法寻找广告服务与请求服务输入、输出概念 间的最佳单射，提高查准率。 ( 4 ) 算法实现与评价。实现了本文提出的基于概念相似度的语义w e b 服务发现方 法，并与现有著名的两个算法o w l s m o 、o w l s m 3 进行比较，分析匹配结 果并获得相应结论。 1 5 论文结构 论文的其余章节安排如下： 第2 章介绍并分析现有概念相似度算法，描述本文提出改进的概念语义相似度计算 方法。 第3 章介绍服务语义相似度的定义、服务候选集确定算法和基于二分图的服务匹配 算法。 第4 章实现与评估本文提出的基于概念相似度的语义w e b 服务发现方法，描述并 分析实验结果。 第5 章总结本文工作，指出有待完善之处及今后研究方向。 8 第2 章概念语义相似度计算方法 第2 章概念语义相似度计算方法 语义w e b 服务发现问题的核心是服务匹配，即匹配请求服务和广告服务，以找出 其中与请求服务一致的服务集合。服务匹配的核心是服务相似度，而服务相似度基于语 义w e b 服务所包含本体概念( 本文中简称概念) 间的相似度定义。因此，概念语义相 似度计算是服务匹配的关键。本章基于对现有概念相似度计算方法的分析和总结，提出 了改进概念语义相似度计算方法。 2 1 概念语义相似度计算方法的分析与比较 本体模型是包含一组概念集合和一组语义关系集合。如图2 1 为一个本体示例，可 以把本体模型看成是一颗分层树。节点表示概念，边表示概念间语义关系。自项向下， 概念分类由大到小，子节点是对父节点的细化。概念语义相似度是两个概念内涵的相似 程度，应用领域不同则含义不同。例如，基于实例的机器翻译中定义的相似度主要用于 衡量词语的可替换程度；而信息检索中定义的相似度反映文本与用户查询语义上的匹配 程度，相似度越大，表示该文本与用户请求越一致。概念语义相似度在基于本体的语义 w e b 服务发现中有重要作用。若两个概念具有某些共同特征，定义两者相似，用 s i m ( q ，乞) 表示概念q 和岛的相似度。相似度必须满足： 相似度的值为【o ，i i 区间中的一个实数，即s i m ( c ，c 2 ) o ，1 】。 若两个概念完全相同，定义相似度为l ，即s i m ( c i ，岛) = l 当且仅当q = c 2 。 若两个概念完全不同，定义相似度为0 ，即s i m ( c 。，g ) = 0 。 相似关系是对称的，即s i m ( q ，岛) = s i m ( c 2 ，q ) 。 图2 1 本体示例 概念语义相似度计算方法主要有基于几何距离、基于属性和基于信息容量的计算方 法，具体如下： 9 东南大学硕士学位论文 ( 1 ) 基于几何距离的概念语义相似度计算方法 基于几何距离的概念语义相似度计算方法1 2 3 的基本思想是以两个概念在本体树中 的最短几何距离定义相似度，距离越短则相似度越大。最短几何距离是两个概念的最短 路径长度。公式( 2 1 ) 定义了两个概念基于几何距离的相似度： sim(q，g)：2din,x-shortestpath(q,c2)( 2 1 ) 1 2 。 其中，k 是本体树的最大深度；s h o r t e s t p a t h ( c i ，c 2 ) 是q 和巳最短路径长度。 ( 2 ) 基于属性的概念语义相似度计算方法 在现实世界中，人们区别和联系不同事物的过程中通常会通过比较事物之间的属性 特点。如果两个事物有许多共同属性，则说明这两个事物比较相似，反之则相反。所以， 基于属性的概念语义相似度计算方法是通过对比两个概念的属性集，从而获得其相似程 度。概念间相同属性越多，相似度越大。t v e r s k y t 2 4 】提出了一个基于属性的概念语义相 似度计算方法，如公式( 2 2 )