李 坤，蔣莉莉

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

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

李 坤1，蔣莉莉2

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

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

語義Web；Web服務(wù)發(fā)現(xiàn)；準(zhǔn)確率；約束提??；結(jié)構(gòu)分析

1 引言

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

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

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

2 相關(guān)研究

基于 服 務(wù)IO 語 義 匹 配 的 有 OWLSM［5］、OWLS－UDDI［9］，在進(jìn)行語義 Web服務(wù)發(fā)現(xiàn)時(shí)主要是使用服務(wù)的IO概念語義包含關(guān)系來確定兩個(gè)服務(wù)之間的語義匹配程度。OWLSM中定義了三種語義匹配度：Equivalent、Subsume、Fail。在OWLS－UDDI中使用DAML－S作為 Web服務(wù)描述語言，并且提出了在語義Web服務(wù)發(fā)現(xiàn)中語義匹配的定義，其中定義的語義匹配度有精確匹配（Exact）、插 入 匹 配 （Plug－in）、包 含 匹 配 （Subsume）、匹配失?。‵ail）等。

OWLS－MX［6］中使用基于邏輯的語義匹配和信息檢索（Information Retrieval）相結(jié)合的方法，Web服務(wù)使用OWL－S進(jìn)行描述，語義推理使用OWLS－DL；先進(jìn)行基于IO邏輯的語義匹配，當(dāng)語義匹配失敗時(shí)再使用信息檢索的方法。在IO語義匹配過程中定義了七個(gè)語義匹配級(jí)別。信息檢索使用了cosine相似度度量、extended Jacquard相似度度量和Jensen－Shannon相似度度量。owls－mx取得了不錯(cuò)的效果。

Amorim R等人［10］提出使用基于邏輯的語義匹配和結(jié)構(gòu)分析相結(jié)合的方法，在進(jìn)行Web服務(wù)發(fā)現(xiàn)時(shí)先進(jìn)行服務(wù)的IO語義匹配，當(dāng)語義匹配失敗時(shí)再執(zhí)行結(jié)構(gòu)分析算法來提高服務(wù)發(fā)現(xiàn)準(zhǔn)確率。Wei D等人［11］提出使用基于邏輯的語義匹配，在進(jìn)行服務(wù)的IO語義匹配時(shí)先提取概念的語義約束，并且把Web服務(wù)表述為三元組形式，然后在主體、操作、客體上分別進(jìn)行匹配，最終返回匹配結(jié)果。

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

3.1 Web服務(wù)的語義匹配

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

（1）完全匹配（Exact）：服務(wù)service的概念s和請(qǐng)求服務(wù)request的概念r是完全匹配當(dāng)且僅當(dāng)r＝s，即請(qǐng)求服務(wù)request的概念與服務(wù)service的概念完全邏輯等價(jià)。如果服務(wù)service的I在圖1中的概念樹為aircraft，那么請(qǐng)求服務(wù)request的I是aircraft。

（2）插入匹配（Plug－in）：服務(wù)service的概念s和請(qǐng)求服務(wù)request的概念r是插入匹配當(dāng)且僅當(dāng)r∈parents（s）∨s∈Children（r），即概念r是概念s的父節(jié)點(diǎn)或者概念s是概念r的父節(jié)點(diǎn)。如果服務(wù)service的I在圖1中的概念樹為aircraft，那么請(qǐng)求服務(wù)request的I是Transportation。

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

（4）匹配失?。‵ail）：服務(wù)service和服務(wù)request進(jìn)行語義匹配時(shí)上面三種情況都不滿足就認(rèn)為是語義匹配失敗。

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

Figure 1 A concept tree of transportation domain圖1 一個(gè)交通工具域的等級(jí)概念樹

3.2 Web服務(wù)的概念語義約束

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

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

（2）沒有指定屬性的概念。在本體中一個(gè)概念可能和多個(gè)屬性相關(guān)聯(lián)，概念的語義通常受屬性約束，同一個(gè)概念可以根據(jù)不同屬性約束而分成不同部分。在特定環(huán)境中，Web服務(wù)IO所表示的語義不僅和概念有關(guān)，還與這些概念的相關(guān)屬性有關(guān)。

（3）沒有指定概念之間的關(guān)系。兩個(gè)具有不同語義的服務(wù)可能具有相同IO，這種情況下使用服務(wù)語義匹配就會(huì)誤判為相似。

因此，本文將概念約束表示為三種類型：

（1）約束isPropertyObjectOf：三元組〈A，is－PropertyObjectOf，B〉表示概念A(yù)是概念B 的一個(gè)屬性。它指明概念所屬類別，即概念A(yù)的實(shí)例是概念B的實(shí)例屬性值。

（2）約束hasPropertyObject：該約束關(guān)系是isPropertyObjectOf約束的逆關(guān)系。三元組〈A，hasPropertyObject，B〉表示概念A(yù)具有一個(gè)對(duì)象屬性，且該屬性的客體是概念B。

（3）約束Operation：三元組〈A，Operation，B〉表示兩個(gè)概念實(shí)體A和B具有某種關(guān)聯(lián)關(guān)系。單詞“Operation”是一個(gè)抽象詞，表示所有類型屬性。

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

3.3 Web服務(wù)的結(jié)構(gòu)分析

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

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

Figure 2 Case representation of service constraint圖2 服務(wù)約束圖實(shí)例表示

其中，M 是｜ancestor（c1）｜行｜ancestor（c2）｜列矩陣，式（2）是用來計(jì)算概念c1和c2父節(jié)點(diǎn)的均值，式（3）是用來計(jì)算概念c1和c2父節(jié)點(diǎn)的標(biāo)準(zhǔn)差。在計(jì)算過程中，當(dāng)vc的值小于本文設(shè)定閾值時(shí)將M清空。

3.4 算法描述

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

（1）使用3.1節(jié)中的服務(wù)語義匹配算法計(jì)算概念sa和ra語義匹配度（完全匹配、插入匹配、包含匹配、匹配失?。祷刂祊a。

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

（3）使用3.1節(jié)中的服務(wù)語義匹配算法計(jì)算概念sb和rb的語義匹配度（完全匹配、插入匹配、包含匹配、匹配失?。?，返回值pb。

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

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

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

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)使用OWL－S和pallet（Maryland大學(xué)開發(fā) 的 API，http：／／www.mindswap.org／2004／owl－s）對(duì)本體進(jìn)行解析和推理，使用xampp作為本地服務(wù)器進(jìn)行測(cè)試；使用OWLS－TC2.0作為測(cè)試集合，該測(cè)試集合有570多個(gè)服務(wù)，分別來自七個(gè)不同的領(lǐng)域 （education、medical care、food、travel、communication、economy和 weaponry）。實(shí)驗(yàn)的查詢性能采用準(zhǔn)確度和召回率［12］；召回率是衡量某一檢索系統(tǒng)從文獻(xiàn)集合中檢出相關(guān)文獻(xiàn)成功度的一項(xiàng)指標(biāo)，即檢出相關(guān)文獻(xiàn)與全部相關(guān)文獻(xiàn)的百分比。準(zhǔn)確率是檢索出相關(guān)文檔數(shù)與檢索出文檔總數(shù)的比率。檢索出的相關(guān)文檔數(shù)為Relevant Document，記為RelDoc，檢索出的文檔數(shù)為Retrieved Document，記RetDoc，準(zhǔn)確率（Precision）和召回率（Recall）定義如下：

實(shí)驗(yàn)結(jié)果如圖3所示，其中Algorithm proposed是本文提出的方法，分別與 owls－m4［6］和M4＋I(xiàn)nOutConstraint［11］進(jìn)行了對(duì)比。

Figure 3 Result of experiments圖3 實(shí)驗(yàn)結(jié)果圖

從圖3中可以看出，M4＋I(xiàn)nOutConstraint方法通過使用提取概念約束來增加IO概念語義的關(guān)系描述，可以減少語義Web服務(wù)的語義偏差和歧義，從而提高語義 Web服務(wù)語義匹配準(zhǔn)確率。對(duì)于評(píng)估Web服務(wù)發(fā)現(xiàn)算法，用戶滿意度是重要指標(biāo)。本文提出的方法重點(diǎn)在于服務(wù)語義匹配失敗后，通過服務(wù)結(jié)構(gòu)分析查找相關(guān)服務(wù)，實(shí)現(xiàn)Web服務(wù)發(fā)現(xiàn)準(zhǔn)確率更高，能夠返回更多潛在滿足服務(wù)請(qǐng)求者需求的服務(wù)，從而發(fā)現(xiàn)最優(yōu)服務(wù)，提升了用戶滿意度。

5 結(jié)束語

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

［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山東省青島市中國(guó)石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院

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

李坤（1980－），男，河南沈丘人，碩士生，實(shí)驗(yàn)師，研究方向 Web服務(wù)集成和語義 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－），女，山東廣饒人，碩士生，講師，研究方向?yàn)榉?wù)計(jì)算和計(jì)算機(jī)網(wǎng)絡(luò)。E－mail：lklk7189＠126.com

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