基于約束提取與結構分析的語義Web服務發(fā)現(xiàn)算法研究＊

李 坤，蔣莉莉

（1.中國石油大學（華東）計算機與通信工程學院，山東 青島266580；2.東營職業(yè)學院，山東 東營257091）

基于約束提取與結構分析的語義Web服務發(fā)現(xiàn)算法研究＊

李 坤1，蔣莉莉2

（1.中國石油大學（華東）計算機與通信工程學院，山東 青島266580；2.東營職業(yè)學院，山東 東營257091）

隨著互聯(lián)網(wǎng)上Web服務數(shù)量的增多，如何快速準確地發(fā)現(xiàn)滿足用戶需求的Web服務已經成為一個亟待解決的問題。現(xiàn)在很多基于語義的Web服務發(fā)現(xiàn)方法都是基于IO匹配，當語義匹配失敗時再采取其他措施來彌補。然而只是單純的基于IO匹配語義Web服務發(fā)現(xiàn)的準確率并不高，提出了基于約束提取與結構分析的語義Web服務發(fā)現(xiàn)算法。算法分為兩部分，首先進行基于約束提取的概念語義匹配，當匹配失敗時再采取基于結構分析的算法。使用OWLS－TC 2.0作為測試集合對該方法進行測試。結果表明，所提出的方法有效地提高了服務發(fā)現(xiàn)準確率。

語義Web；Web服務發(fā)現(xiàn)；準確率；約束提?。唤Y構分析

1 引言

隨著網(wǎng)絡上Web服務數(shù)量的迅速增加，如何快速、準確地發(fā)現(xiàn)滿足用戶需要的服務已經成為服務計算中的一個關鍵問題。為此，Web服務發(fā)現(xiàn)成為了近年來的一個研究熱點。傳統(tǒng)的Web服務發(fā)現(xiàn)的準確率低，原因在于：一方面，由于傳統(tǒng)的Web服務描述缺少必要的語義信息，無法準確地描述Web服務的功能，嚴重影響Web服務發(fā)現(xiàn)的準確率；另一方面，傳統(tǒng)Web服務發(fā)現(xiàn)技術是通過語法層面的服務描述語言和基于關鍵字的匹配算法來實現(xiàn)的。

語義Web服務研究是在語義層面對Web服務各個組件進行描述，采用的描述語言有：OWLS［1］、WSMO［2］、WSDLS［3］、SAWSDL［4］等。語義Web服務發(fā)現(xiàn)方法通常定義一個服務匹配器（Matchmaker），服務提供者和服務請求者使用同一服務描述語言，根據(jù)服務匹配器來度量請求服務和Web服務的語義匹配程度。目前，基于邏輯語義匹配Web服務發(fā)現(xiàn)技術大致分為兩類：一是基于IO 的 Web服 務 發(fā) 現(xiàn)［5，6］；二 是 基 于IOPE 的Web服務發(fā)現(xiàn)［7，8］。這些方法的共同點是根據(jù)兩個概念之間的包含關系來度量語義匹配程度，然而Web服務的匹配程度卻是由服務IO概念語義匹配程度決定的。也就是說，IO語義參數(shù)質量決定了基于Web服務IO語義匹配的Web服務發(fā)現(xiàn)算法的性能。

為了彌補服務IO概念語義描述存在的不足，本文通過對Web服務提取IO語義約束，同時使用OWL－S描述 Web服務，從而提出新的算法；該算法分為兩部分，首先進行基于語義約束提取的語義Web服務發(fā)現(xiàn)，當語義匹配失敗時再進行基于結構分析的語義Web服務發(fā)現(xiàn)算法。

2 相關研究

基于 服 務IO 語 義 匹 配 的 有 OWLSM［5］、OWLS－UDDI［9］，在進行語義 Web服務發(fā)現(xiàn)時主要是使用服務的IO概念語義包含關系來確定兩個服務之間的語義匹配程度。OWLSM中定義了三種語義匹配度：Equivalent、Subsume、Fail。在OWLS－UDDI中使用DAML－S作為 Web服務描述語言，并且提出了在語義Web服務發(fā)現(xiàn)中語義匹配的定義，其中定義的語義匹配度有精確匹配（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服務發(fā)現(xiàn)時先進行服務的IO語義匹配，當語義匹配失敗時再執(zhí)行結構分析算法來提高服務發(fā)現(xiàn)準確率。Wei D等人［11］提出使用基于邏輯的語義匹配，在進行服務的IO語義匹配時先提取概念的語義約束，并且把Web服務表述為三元組形式，然后在主體、操作、客體上分別進行匹配，最終返回匹配結果。

3 基于約束提取與結構分析的語義Web服務發(fā)現(xiàn)算法

3.1 Web服務的語義匹配

語義匹配算法是對服務IO進行語義匹配，即服務匹配程度由服務輸入輸出參數(shù)的邏輯匹配程度來決定，通過解析服務的語義描述文件，分別得到服務在IO上的概念，然后通過具有邏輯推理能力的pallet來對樹形關系本體中的概念進行推理，語義匹配級別為 Exact、Plug－in、Subsume、Fail。假定c是一個領域概念，parents（c）返回概念c的父節(jié)點，Children（c）返回概念c的子節(jié)點。簡單等級概念樹定義如下：

（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的父節(jié)點或者概念s是概念r的父節(jié)點。如果服務service的I在圖1中的概念樹為aircraft，那么請求服務request的I是Transportation。

（3）包含匹配（Subsumed－by）：服務service的概念s和請求服務request的概念r是包含匹配當且僅當s∈parents（r）∨r∈Children（s），即概念s是概念r的父節(jié)點或者概念r是概念s的父節(jié)點。如果服務service的I在圖1中的概念樹為automobile，那么請求服務request的I是Bus。

（4）匹配失?。‵ail）：服務service和服務request進行語義匹配時上面三種情況都不滿足就認為是語義匹配失敗。

上述定義的插入匹配和包含匹配中兩個析取子句語義看似相同，但是在實際本體推理過程中，語義關系推理結果往往取決其所在知識庫。如果推理知識庫不同，則可能會得到不同結果。在語義匹配過程中本文先進行完全匹配，然后進行插入匹配，再進行包含匹配，最終返回基于語義的匹配結果集。

Figure 1 A concept tree of transportation domain圖1 一個交通工具域的等級概念樹

3.2 Web服務的概念語義約束

服務概念語義約束提取的目的是盡量彌補服務IO概念語義描述存在的不足，即增加IO概念語義關系描述，并減少語義Web服務語義偏差和歧義，從而提高語義 Web服務語義匹配準確率。目前Web服務語義本體描述信息存在以下問題：

（1）沒有指定概念的論域。通常情況下，概念在本體庫中是描述一些比較抽象的事物，例如價格Price。然而抽象的概念往往與上下文有關，只有把他們放在特定語義中才有真正的意義。

（2）沒有指定屬性的概念。在本體中一個概念可能和多個屬性相關聯(lián)，概念的語義通常受屬性約束，同一個概念可以根據(jù)不同屬性約束而分成不同部分。在特定環(huán)境中，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具有某種關聯(lián)關系。單詞“Operation”是一個抽象詞，表示所有類型屬性。

通過服務概念語義約束提取可以在一定程度上提高語義匹配的準確率，但是在現(xiàn)實世界中，存在這種情況，兩個是同義詞或者在語義上非常接近，但在本體中的定義卻不是包含關系的概念，使用基于語義匹配方法就會失敗。結合這種情況，本文允許出現(xiàn)語義匹配失敗，當語義匹配失敗時進行基于結構分析的Web服務發(fā)現(xiàn)。

3.3 Web服務的結構分析

這部分使用基于同義詞字典的結構分析。同義詞字典是針對測試集合owls－tc中的概念進行分類。在計算c1和c2兩類概念之間相似度時，如果c1和c2是同一個概念，則M［i］［j］＝1；如果c1和c2是同義詞，則 M［i］［j］＝0.5；否則，M［i］［j］＝0。進行基于同義詞字典的結構分析的函數(shù)定義［11］如下：

其中，p1、p2、p3、p4分別是在0到1之間可以調整的參數(shù)，且p1＋p2＋p3＋p4＝1；可以根據(jù)用戶需要進行調整，用于改變式（1）中各個項在兩個概念相似度計算求解中所占比例，從而使算法達到最佳性能。ancestor（c1，c2）、descendent（c1，c2）、sibling（c1，c2）、leaf（c1，c2）分別用來計算概念c1和c2的父節(jié)點、子節(jié)點、兄弟節(jié)點、葉子節(jié)點的相似度，其計算方式相同，如下所示。

Figure 2 Case representation of service constraint圖2 服務約束圖實例表示

其中，M 是｜ancestor（c1）｜行｜ancestor（c2）｜列矩陣，式（2）是用來計算概念c1和c2父節(jié)點的均值，式（3）是用來計算概念c1和c2父節(jié)點的標準差。在計算過程中，當vc的值小于本文設定閾值時將M清空。

3.4 算法描述

本文算法先進行服務概念語義約束提取，然后進行服務語義匹配，當匹配失敗時再進行服務結構分析，計算兩個概念的相似度sim（c1，c2），當sim（c1，c2）大于設定閾值時認為二者是相關服務。本文將服務表示成三元組〈A，Operation，B〉形式，已經發(fā)布服務表示為三元組〈sa，so，sb〉，請求服務表示為三元組〈ra，ro，rb〉。算法具體描述如下：

（1）使用3.1節(jié)中的服務語義匹配算法計算概念sa和ra語義匹配度（完全匹配、插入匹配、包含匹配、匹配失敗），返回值pa。

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

（3）使用3.1節(jié)中的服務語義匹配算法計算概念sb和rb的語義匹配度（完全匹配、插入匹配、包含匹配、匹配失?。祷刂祊b。

（4）根據(jù)式（1）～式（3）計算sum＝n1＊pa＋n2＊po＋n3＊pb，如果sum大于定義閾值認為匹配成功，否則轉（5）。其中，n1、n2、n3的值都在0到1之間，且n1＋n2＋n3＝1。

（5）使用3.3節(jié)中服務結構分析算法計算概念sa和ra、sb和rb的語義匹相似度，如果sim（sa，ra）和sim（sb，rb）都大于定義的閾值，則認為是相關服務。

（6）重復上面的步驟，直至發(fā)現(xiàn)滿足用戶需求的最優(yōu)服務。

4 實驗結果

實驗使用OWL－S和pallet（Maryland大學開發(fā) 的 API，http：／／www.mindswap.org／2004／owl－s）對本體進行解析和推理，使用xampp作為本地服務器進行測試；使用OWLS－TC2.0作為測試集合，該測試集合有570多個服務，分別來自七個不同的領域 （education、medical care、food、travel、communication、economy和 weaponry）。實驗的查詢性能采用準確度和召回率［12］；召回率是衡量某一檢索系統(tǒng)從文獻集合中檢出相關文獻成功度的一項指標，即檢出相關文獻與全部相關文獻的百分比。準確率是檢索出相關文檔數(shù)與檢索出文檔總數(shù)的比率。檢索出的相關文檔數(shù)為Relevant Document，記為RelDoc，檢索出的文檔數(shù)為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服務發(fā)現(xiàn)算法，用戶滿意度是重要指標。本文提出的方法重點在于服務語義匹配失敗后，通過服務結構分析查找相關服務，實現(xiàn)Web服務發(fā)現(xiàn)準確率更高，能夠返回更多潛在滿足服務請求者需求的服務，從而發(fā)現(xiàn)最優(yōu)服務，提升了用戶滿意度。

5 結束語

本文使用基于約束提取與結構分析的語義Web服務發(fā)現(xiàn)方法來進行Web服務發(fā)現(xiàn)，首先進行基于約束提取的IO語義匹配，當匹配失敗時再進行基于結構分析的算法。實驗結果證明了所提算法的有效性。在下一步的研究中，將重點改善算法性能，進一步完善 Web服務發(fā)現(xiàn)工具，為 Web服務發(fā)現(xiàn)提供支撐平臺。

［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，F(xiàn)arrell 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，F(xiàn)ries 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－），女，山東廣饒人，碩士生，講師，研究方向為服務計算和計算機網(wǎng)絡。E－mail：lklk7189＠126.com

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