基于约束提取与结构分析的语义Web服务发现算法研究＊

李 坤，蒋莉莉

（1.中国石油大学（华东）计算机与通信工程学院，山东 青岛266580；2.东营职业学院，山东 东营257091）

基于约束提取与结构分析的语义Web服务发现算法研究＊

李 坤1，蒋莉莉2

（1.中国石油大学（华东）计算机与通信工程学院，山东 青岛266580；2.东营职业学院，山东 东营257091）

随着互联网上Web服务数量的增多，如何快速准确地发现满足用户需求的Web服务已经成为一个亟待解决的问题。现在很多基于语义的Web服务发现方法都是基于IO匹配，当语义匹配失败时再采取其他措施来弥补。然而只是单纯的基于IO匹配语义Web服务发现的准确率并不高，提出了基于约束提取与结构分析的语义Web服务发现算法。算法分为两部分，首先进行基于约束提取的概念语义匹配，当匹配失败时再采取基于结构分析的算法。使用OWLS－TC 2.0作为测试集合对该方法进行测试。结果表明，所提出的方法有效地提高了服务发现准确率。

语义Web；Web服务发现；准确率；约束提取；结构分析

1 引言

随着网络上Web服务数量的迅速增加，如何快速、准确地发现满足用户需要的服务已经成为服务计算中的一个关键问题。为此，Web服务发现成为了近年来的一个研究热点。传统的Web服务发现的准确率低，原因在于：一方面，由于传统的Web服务描述缺少必要的语义信息，无法准确地描述Web服务的功能，严重影响Web服务发现的准确率；另一方面，传统Web服务发现技术是通过语法层面的服务描述语言和基于关键字的匹配算法来实现的。

语义Web服务研究是在语义层面对Web服务各个组件进行描述，采用的描述语言有：OWLS［1］、WSMO［2］、WSDLS［3］、SAWSDL［4］等。语义Web服务发现方法通常定义一个服务匹配器（Matchmaker），服务提供者和服务请求者使用同一服务描述语言，根据服务匹配器来度量请求服务和Web服务的语义匹配程度。目前，基于逻辑语义匹配Web服务发现技术大致分为两类：一是基于IO 的 Web服 务 发 现［5，6］；二 是 基 于IOPE 的Web服务发现［7，8］。这些方法的共同点是根据两个概念之间的包含关系来度量语义匹配程度，然而Web服务的匹配程度却是由服务IO概念语义匹配程度决定的。也就是说，IO语义参数质量决定了基于Web服务IO语义匹配的Web服务发现算法的性能。

为了弥补服务IO概念语义描述存在的不足，本文通过对Web服务提取IO语义约束，同时使用OWL－S描述 Web服务，从而提出新的算法；该算法分为两部分，首先进行基于语义约束提取的语义Web服务发现，当语义匹配失败时再进行基于结构分析的语义Web服务发现算法。

2 相关研究

基于 服 务IO 语 义 匹 配 的 有 OWLSM［5］、OWLS－UDDI［9］，在进行语义 Web服务发现时主要是使用服务的IO概念语义包含关系来确定两个服务之间的语义匹配程度。OWLSM中定义了三种语义匹配度：Equivalent、Subsume、Fail。在OWLS－UDDI中使用DAML－S作为 Web服务描述语言，并且提出了在语义Web服务发现中语义匹配的定义，其中定义的语义匹配度有精确匹配（Exact）、插 入 匹 配 （Plug－in）、包 含 匹 配 （Subsume）、匹配失败（Fail）等。

OWLS－MX［6］中使用基于逻辑的语义匹配和信息检索（Information Retrieval）相结合的方法，Web服务使用OWL－S进行描述，语义推理使用OWLS－DL；先进行基于IO逻辑的语义匹配，当语义匹配失败时再使用信息检索的方法。在IO语义匹配过程中定义了七个语义匹配级别。信息检索使用了cosine相似度度量、extended Jacquard相似度度量和Jensen－Shannon相似度度量。owls－mx取得了不错的效果。

Amorim R等人［10］提出使用基于逻辑的语义匹配和结构分析相结合的方法，在进行Web服务发现时先进行服务的IO语义匹配，当语义匹配失败时再执行结构分析算法来提高服务发现准确率。Wei D等人［11］提出使用基于逻辑的语义匹配，在进行服务的IO语义匹配时先提取概念的语义约束，并且把Web服务表述为三元组形式，然后在主体、操作、客体上分别进行匹配，最终返回匹配结果。

3 基于约束提取与结构分析的语义Web服务发现算法

3.1 Web服务的语义匹配

语义匹配算法是对服务IO进行语义匹配，即服务匹配程度由服务输入输出参数的逻辑匹配程度来决定，通过解析服务的语义描述文件，分别得到服务在IO上的概念，然后通过具有逻辑推理能力的pallet来对树形关系本体中的概念进行推理，语义匹配级别为 Exact、Plug－in、Subsume、Fail。假定c是一个领域概念，parents（c）返回概念c的父节点，Children（c）返回概念c的子节点。简单等级概念树定义如下：

（1）完全匹配（Exact）：服务service的概念s和请求服务request的概念r是完全匹配当且仅当r＝s，即请求服务request的概念与服务service的概念完全逻辑等价。如果服务service的I在图1中的概念树为aircraft，那么请求服务request的I是aircraft。

（2）插入匹配（Plug－in）：服务service的概念s和请求服务request的概念r是插入匹配当且仅当r∈parents（s）∨s∈Children（r），即概念r是概念s的父节点或者概念s是概念r的父节点。如果服务service的I在图1中的概念树为aircraft，那么请求服务request的I是Transportation。

（3）包含匹配（Subsumed－by）：服务service的概念s和请求服务request的概念r是包含匹配当且仅当s∈parents（r）∨r∈Children（s），即概念s是概念r的父节点或者概念r是概念s的父节点。如果服务service的I在图1中的概念树为automobile，那么请求服务request的I是Bus。

（4）匹配失败（Fail）：服务service和服务request进行语义匹配时上面三种情况都不满足就认为是语义匹配失败。

上述定义的插入匹配和包含匹配中两个析取子句语义看似相同，但是在实际本体推理过程中，语义关系推理结果往往取决其所在知识库。如果推理知识库不同，则可能会得到不同结果。在语义匹配过程中本文先进行完全匹配，然后进行插入匹配，再进行包含匹配，最终返回基于语义的匹配结果集。

Figure 1 A concept tree of transportation domain图1 一个交通工具域的等级概念树

3.2 Web服务的概念语义约束

服务概念语义约束提取的目的是尽量弥补服务IO概念语义描述存在的不足，即增加IO概念语义关系描述，并减少语义Web服务语义偏差和歧义，从而提高语义 Web服务语义匹配准确率。目前Web服务语义本体描述信息存在以下问题：

（1）没有指定概念的论域。通常情况下，概念在本体库中是描述一些比较抽象的事物，例如价格Price。然而抽象的概念往往与上下文有关，只有把他们放在特定语义中才有真正的意义。

（2）没有指定属性的概念。在本体中一个概念可能和多个属性相关联，概念的语义通常受属性约束，同一个概念可以根据不同属性约束而分成不同部分。在特定环境中，Web服务IO所表示的语义不仅和概念有关，还与这些概念的相关属性有关。

（3）没有指定概念之间的关系。两个具有不同语义的服务可能具有相同IO，这种情况下使用服务语义匹配就会误判为相似。

因此，本文将概念约束表示为三种类型：

（1）约束isPropertyObjectOf：三元组〈A，is－PropertyObjectOf，B〉表示概念A是概念B 的一个属性。它指明概念所属类别，即概念A的实例是概念B的实例属性值。

（2）约束hasPropertyObject：该约束关系是isPropertyObjectOf约束的逆关系。三元组〈A，hasPropertyObject，B〉表示概念A具有一个对象属性，且该属性的客体是概念B。

（3）约束Operation：三元组〈A，Operation，B〉表示两个概念实体A和B具有某种关联关系。单词“Operation”是一个抽象词，表示所有类型属性。

通过服务概念语义约束提取可以在一定程度上提高语义匹配的准确率，但是在现实世界中，存在这种情况，两个是同义词或者在语义上非常接近，但在本体中的定义却不是包含关系的概念，使用基于语义匹配方法就会失败。结合这种情况，本文允许出现语义匹配失败，当语义匹配失败时进行基于结构分析的Web服务发现。

3.3 Web服务的结构分析

这部分使用基于同义词字典的结构分析。同义词字典是针对测试集合owls－tc中的概念进行分类。在计算c1和c2两类概念之间相似度时，如果c1和c2是同一个概念，则M［i］［j］＝1；如果c1和c2是同义词，则 M［i］［j］＝0.5；否则，M［i］［j］＝0。进行基于同义词字典的结构分析的函数定义［11］如下：

其中，p1、p2、p3、p4分别是在0到1之间可以调整的参数，且p1＋p2＋p3＋p4＝1；可以根据用户需要进行调整，用于改变式（1）中各个项在两个概念相似度计算求解中所占比例，从而使算法达到最佳性能。ancestor（c1，c2）、descendent（c1，c2）、sibling（c1，c2）、leaf（c1，c2）分别用来计算概念c1和c2的父节点、子节点、兄弟节点、叶子节点的相似度，其计算方式相同，如下所示。

Figure 2 Case representation of service constraint图2 服务约束图实例表示

其中，M 是｜ancestor（c1）｜行｜ancestor（c2）｜列矩阵，式（2）是用来计算概念c1和c2父节点的均值，式（3）是用来计算概念c1和c2父节点的标准差。在计算过程中，当vc的值小于本文设定阈值时将M清空。

3.4 算法描述

本文算法先进行服务概念语义约束提取，然后进行服务语义匹配，当匹配失败时再进行服务结构分析，计算两个概念的相似度sim（c1，c2），当sim（c1，c2）大于设定阈值时认为二者是相关服务。本文将服务表示成三元组〈A，Operation，B〉形式，已经发布服务表示为三元组〈sa，so，sb〉，请求服务表示为三元组〈ra，ro，rb〉。算法具体描述如下：

（1）使用3.1节中的服务语义匹配算法计算概念sa和ra语义匹配度（完全匹配、插入匹配、包含匹配、匹配失败），返回值pa。

（2）计算约束操作so和ro的约束类型（is－PropertyObjectOf、hasPropertyObject、Operation），返回值po。

（3）使用3.1节中的服务语义匹配算法计算概念sb和rb的语义匹配度（完全匹配、插入匹配、包含匹配、匹配失败），返回值pb。

（4）根据式（1）～式（3）计算sum＝n1＊pa＋n2＊po＋n3＊pb，如果sum大于定义阈值认为匹配成功，否则转（5）。其中，n1、n2、n3的值都在0到1之间，且n1＋n2＋n3＝1。

（5）使用3.3节中服务结构分析算法计算概念sa和ra、sb和rb的语义匹相似度，如果sim（sa，ra）和sim（sb，rb）都大于定义的阈值，则认为是相关服务。

（6）重复上面的步骤，直至发现满足用户需求的最优服务。

4 实验结果

实验使用OWL－S和pallet（Maryland大学开发 的 API，http：／／www.mindswap.org／2004／owl－s）对本体进行解析和推理，使用xampp作为本地服务器进行测试；使用OWLS－TC2.0作为测试集合，该测试集合有570多个服务，分别来自七个不同的领域 （education、medical care、food、travel、communication、economy和 weaponry）。实验的查询性能采用准确度和召回率［12］；召回率是衡量某一检索系统从文献集合中检出相关文献成功度的一项指标，即检出相关文献与全部相关文献的百分比。准确率是检索出相关文档数与检索出文档总数的比率。检索出的相关文档数为Relevant Document，记为RelDoc，检索出的文档数为Retrieved Document，记RetDoc，准确率（Precision）和召回率（Recall）定义如下：

实验结果如图3所示，其中Algorithm proposed是本文提出的方法，分别与 owls－m4［6］和M4＋InOutConstraint［11］进行了对比。

Figure 3 Result of experiments图3 实验结果图

从图3中可以看出，M4＋InOutConstraint方法通过使用提取概念约束来增加IO概念语义的关系描述，可以减少语义Web服务的语义偏差和歧义，从而提高语义 Web服务语义匹配准确率。对于评估Web服务发现算法，用户满意度是重要指标。本文提出的方法重点在于服务语义匹配失败后，通过服务结构分析查找相关服务，实现Web服务发现准确率更高，能够返回更多潜在满足服务请求者需求的服务，从而发现最优服务，提升了用户满意度。

5 结束语

本文使用基于约束提取与结构分析的语义Web服务发现方法来进行Web服务发现，首先进行基于约束提取的IO语义匹配，当匹配失败时再进行基于结构分析的算法。实验结果证明了所提算法的有效性。在下一步的研究中，将重点改善算法性能，进一步完善 Web服务发现工具，为 Web服务发现提供支撑平台。

［1］ Martin D，Burstein M，Hobbs J，et al.OWL－S：Semantic markup for web services（2004）［EB／OL］.［2004－11－22］.http：／／www.w3.org／Submission／OWL－S／.

［2］ de Bruijn J，Bussler C，John D，et al.D2v1.3.Web service modeling ontology（wsmo）（2006）［EB／OL］.［2006－10－09］.http：／／www.wsmo.org／TR／d2／v1.3／.

［3］ Akkiraju R，Farrell J，Miller J，et al.Web service semantics－WSDL－S（2005）［EB／OL］.［2005－11－07］.http：／／www.w3.org／Submission／WSDL－S／.

［4］ Farrell J，Lausen H.Semantic annotations for WSDL and XML schema（2007）［EB／OL］.［2005－11－07］.http：／／www.w3.org／TR／sawsdl／.

［5］ Jaeger M C，Rojec－Goldmann G，Liebetruth C，et al.Rankedmatching for service descriptions using OWL－S［C］∥Proc of KiVS’05，Informatik Aktuell，2005：91－102.

［6］ Klusch M，Fries B，Sycara K.Automated semantic web service discovery with OWLS－MX［C］∥Proc of the 5th International Joint Conference on Autonomous Agents and Multi－A－gent Systems（AAMAS），2006：915－922.

［7］ Kaufer F，Klusch M.Wsmo－mx：A logic programming based hybrid service matchmaker［C］∥Proc of the 4th European Conference on Web Service，2006：161－170.

［8］ Stollberg M，Keller U，Lausen H，et al.Two－phase web service discovery based on rich functional descriptions［C］∥Proc of ESWC’07，2007：99－113.［9］ Paolucci M，Kawamura T，Payne T R，et al.Semantic matching of web services capabilities［C］∥Proc of International Semantic Web Conference，2002：333－347.

［10］ Amorim R，Claro D B，Lopes D，et al.Improving web service discovery by a functional and structural approach［C］∥Proc of 2011IEEE International Conference on Web Services DOI 10.1109／ICWS，2011：14

［11］ Wei D，Wang T，Wang J，et al.Extracting semantic constraint from description text for semantic web service discovery［C］∥Proc of ISWC’08，2008：146－161.

［12］ van Rijsbergen C J.Information retrieval［M］.London：

Butterworths，1979.

Research of semantic web service discovery algorithm based on constraint extraction and structure analysis

With the increase of the number of Web services on the Internet，how to find a web service that can meet users’requirements quickly and accurately has become a problem to be solved.Currently，many semantic web service methods are based on IO matching .They use other ways if semantic matching is failed.However，the accuracy of semantic web service discovery based on IO matching purely is not high enough.Semantic web service discovery algorithm is proposed，which is based on constraint extraction and structure analysis.It consists of two parts.Firstly，the conceptual semantic matching based on constraint extraction is carried out.Secondly，it uses the algorithm based on structure analysis while matching is failed.owls－tc2.0is used as test set to validate this method .Experimental results show that this method can improve the accuracy of service discovery effectively.

semantic web；semantic web discovery；accuracy；constraint extraction；structure analysis?

TP391

A

10.3969／j.issn.1007－130X.2013.08.023

1007－130X（2013）08－0144－05

2012－04－24；

2012－08－27

通讯地址：266580山东省青岛市中国石油大学（华东）计算机与通信工程学院

Address：College of Computer and Communication Engineering，China University of Petroleum，Qingdao 266580，Shandong，P.R.China

李坤（1980－），男，河南沈丘人，硕士生，实验师，研究方向 Web服务集成和语义 Web。E－mail：likun＠upc.edu.cn

LI Kun，born in 1980，MS candidate，experimentalist，his research interests include web services integration，and semantic web.

蒋莉莉（1980－），女，山东广饶人，硕士生，讲师，研究方向为服务计算和计算机网络。E－mail：lklk7189＠126.com

JIANG Li－li，born in 1980，MS candidate，lecturer，her research interests include service computing，and computer network.