基于語義的Ｗｅｂ服務匹配算法研究
2009-04-29 00:00:00彭勃
電腦知識與技術 2009年15期
摘要:針對基于推理的OWL-S/UDDI匹配算法在同一級結果間不能進一步區分匹配度導致查全率和查準率不高的問題，提出了一種基于本體概念相似度計算的服務匹配算法，該算法分別按服務的基本描述、功能和非功能(QoS)三個層次進行匹配，提高了服務匹配效率。
關鍵詞:語義;Web服務;OWL-S;服務匹配
中圖分類號:TP393 文獻標識碼:A 文章編號:1009-3044(2009)15-3989-04
Research on Web Service Matching Algorithm Based on Semantic
PENG Bo
(Computer Center，Anhui Medical University，Hefei 230032，China)
Abstract: The OWL-S/UDDI matching algorithm based on reasoning cannot differentiate the matching degree on the same results level，thus causing inaccuracy and incompleteness.According this shortcoming of reserch， this paper proposes a Web service matching algorithm based on similarity computing of ontology concept.The algorithm has three levels:the basic description matching，the function matching ，and the non-function matching(QoS).This algorithm can improves the efficiency of services matching.
Key words: semantic;Web service;OWL-S;service matching
1 引言
面向服務體系結構(SOA)是網絡環境下分布式應用系統的概念模型，在這個模型中松散耦合的系統組件在網絡上被描述、發布和調用。實現SOA的主要方式是基于WSDL/UDDI的Web服務技術，Web服務的關鍵是服務的發現，基于語法級的服務描述語言和基于關鍵字的服務匹配算法導致了服務查準率低。語義Web服務綜合了語義網技術和Web服務技術的優點，通過擴展UDDI，加入領域本體庫，為每個注冊服務添加語義信息等技術能夠為Web服務的自動發現、執行、解釋和自動組合提供有效支持。
本文首先介紹了基于推理的OWL-S/UDDI語義Web服務匹配算法，針對其同一級匹配結果間不能進一步區分的問題，提出了一種基于本體概念相似度計算的語義Web服務分級匹配算法。
2 相關技術概述
2.1 本體
目前較為公認的本體定義是Rudi Stuger于1998年提出的:“本體是共享概念的明確的、形式化的規范描述[1]”。通俗地講，本體是為了讓計算機對現實世界某一領域中的概念及概念間的關系有明確、一致的理解而進行的形式化、規范化的描述。本體的優點在于它能指導人們對某一領域的知識達到一致的認識和理解，并使用計算機進行描述和邏輯推理，從而達到語義Web的目標。
2.2 Web服務描述語言
實現語義Web服務的關鍵步驟是對Web服務進行語義描述。OWL-S是一種描述Web服務的本體語言，其前身是DAML-S，它為Web服務提供了核心的標記語言結構，用于精確描述Web服務的屬性和能力，這些描述能被計算機無二義性的解釋理解，從而實現服務的自動發現、執行和組合。這個描述至少包括三個方面語義:ServiceProfile提供服務的抽象描述，如服務實體、服務可以實現的功能，以及服務的性能參數等;ServiceModel描述Web服務如何執行，包括服務執行的先后順序、過程流程等;ServiceGrounding描述了如何調用Web服務，描述具體的綁定信息，例如服務地址、通信協議及消息格式等。
2.3 OWL-S ServiceProfile
OWL-S Profile描述服務的三個基本方面:服務提供者的信息、服務的功能和服務的其他特征。ServiceProfile第一組屬性描述Web服務提供實體，包括提供者名稱(ServiceName) 、描述文本(textDescription)和聯系信息(ContactInformation)。 ServiceProfile第二組屬性描述服務功能，這是最本質的部分，表達了服務性能的兩個方面:一是從信息流角度:輸入信息Inputs和輸出信息Outputs;二是從狀態流角度:服務所需的前置條件Precondition以及服務執行后的結果Effect。ServiceProfile第三組屬性描述服務的其他特征，包括服務分類ServiceCategory和服務等級QualityRating(提供服務質量信息)等。
本文將ServiceProfile作為廣告發布在服務注冊中心，并利用ServiceProfile的信息進行服務匹配。同時，服務請求也將ServiceProfile作為表達服務查詢條件的語言，從而使服務匹配能夠更加方便。
3 基于語義的Web服務匹配算法
3.1 基于推理的OWL-S/UDDI服務匹配算法
基于推理的服務匹配是利用本體概念間的包含關系來判斷服務的請求方和發布方的匹配程度。Massimo Paolucci等于2002年首先提出了一種基于DAML-S的服務匹配算法[2]，利用DAML-S的Service Profile對服務的輸入、輸出、前提、效果(IOPE)進行匹配。該方法定義了四種匹配程度(以輸出匹配為例，設outR為請求者的一個輸出，outA為服務發布者的一個輸出):
1) Exact: 當outR與outA相同或outR是outA的直接子類(subClassOf)時，結果為Exact。
2) Plug-In:如果outA包含outR，也就是說outA可能完全滿足outR。
3) Subsume:如果outR包含outA，即outA能部分滿足outR但不是完全滿足。
4) Fail:在outR和outA之間沒有任何包含關系，匹配失敗。
隨后，LeiLi等人對上述四種匹配類型進行了補充，在Subsume和Fail之間添加了Intersection，即outR與outA的交集是可滿足的(outR∩outA≠Φ，但outR不包含outA)，說明outA有可能滿足outR的部分功能。從上述介紹可以看出，基于推理的OWL-S/UDDI服務匹配方法將服務間的匹配程度分為5個等級:Exact Plug-In Subsume Intersection Fail，但在同一等級內部無法進一步區分匹配度。
3.2 Web服務描述模型
在介紹匹配算法之前，先創建服務描述模型，將服務描述為:WS=
3.3 Web服務匹配算法的分級匹配過程
算法的基本原理:服務請求者先提供一個OWL-S文檔，對其所需服務進行描述。在預處理階段，通過服務分類匹配(可通過屬性ServiceCategory來判斷)去掉不屬于請求服務分類的注冊服務，將分類符合的服務放入候選集中，首先進行基本描述匹配，經由基本描述匹配篩選的候選服務再參與功能匹配，合格的服務再進一步參與QoS非功能屬性的匹配。下面詳細介紹各部分的匹配過程。
3.3.1 基本描述的匹配
服務的名稱和文本描述是已經在Web服務本體中的概念實體、概念屬性以及概念間的關系，所以其計算的基礎是概念間語義相似度。對于本體庫中概念以及概念間上下位關系(subClassOf)形成的概念樹，可用2個不同節點之間的距離來衡量節點概念間的相似度。因服務匹配的要求，定義概念樹中節點的距離如下:
定義1概念樹定義為一棵有向樹，對于樹中的每一條有向邊
定義2對于概念樹中的任意2個節點Vi，Vj的距離distance(Vi，Vj)，定義為:
1) 如果Vi與Vj為樹中相同節點，則distance(Vi，Vj)=0
2) 如果從節點Vi沒有路徑到達Vj，且從節點Vi也沒有路徑到達Vj，則distance(Vi，Vj)=∞
3) 如果從節點Vi有路徑到達Vj，則distance(Vi，Vj)為從Vi到達Vj的路徑的長度。
4) 如果從節點Vj反方向有路徑到達Vi，則distance(Vi，Vj)為Vj從到達Vi的路徑長度的負數。
定義3概念樹中2個節點所表示的概念相似度函數定義如下，設結點Vi表示的概念為Cvi，結點Vj表示的概念為Cvj。
其中AS是廣告服務，RS是請求服務，Simsn(AS，RS)是服務名稱的相似度，Simtd(AS，RS)是文本描述的相似度。SimBasic(AS，RS)的結果是0到1之間的實數值。其中wi是用戶自定義的權值。
w1+ w2=1，0≤wi≤1，i=1，2
基本描述匹配算法描述:
BasicDescriptionMatch(RS，AS，Reasoner reasoner)
{
Int BasicMatch=0;
Ucandidates=Ф;//候選子集初始為空
BasicMatch=reasoner.SimBasic(RS，AS);//由推理機計算SimBasic
for (int i=0;AS<>Ф;i++){
if BasicMatch>Num1 //Num1是用戶設定的匹配閾值
ADD(Ucandidates，ASi);//將符合條件的AS加入候選集中
endif
}
}
3.3.2 服務功能的匹配
在這個階段，使用基于WordNet和HowNet通過語義相似度的計算方法來計算請求服務與廣告服務的匹配相似度。
WordNet是一個以同義詞集合為單位來組織信息的語義詞典，是基于英文的詞匯語義網絡系統。它為英語詞語相似度的計算提供了便利。目前基于WordNet的相似度計算方法很多，如res、lin和jcn等方法使用WordNet中的上下位關系計算相似度;hso、lesk和vector等方法使用WordNet中包括上下位關系的所有關系計算相似度[3]。
為了在使用WordNet中所有信息關系的同時充分使用上下位關系，本文在計算英文信息的相似度時選擇兩個典型的方法:lin和lesk，其中對方法lin進行改進，再分別計算得到概念相似度Slin和Slesk，然后取Slin和Slesk的加權和作為英文概念最終的相似度值。
方法Lin是利用概率的方法計算兩個概念的相似度。
在尋找詞義Cvi和Cvj的共同上位詞時，通過路徑的方法，設定了一個系數αl/2。其中α是一個介于0和1之間的常數，用來調整隨層次加深，相似度隨之遞減的程度， 表示在某個同義詞層次結構中，尋找詞義Cvi和Cvj的共同上位詞的最大路徑。由于Cvi和Cvj兩個詞義，故乘以1/2。
HowNet是一個用以揭示概念與概念之間以及概念所具有屬性之間的關系的常識知識庫，是目前最完善的漢語語義知識詞典。本文設漢語概念的語義相似度為Sch，使用劉群[4]等人提出的基于HowNet的語義相似度計算方法可得到漢語概念相似度值。最后對英文概念相似度值和漢語概念相似度值加權平均得到公式(4):
其中μi是用戶自定義的權值。μ1+μ2+μ3=1，0≤μi≤1，i=1，2，3
設Ains表示廣告服務輸入參數的集合，Rins表示請求服務輸入參數的集合，Aous表示廣告服務輸出參數的集合，Rous表示請求服務輸出參數的集合，Aprs表示廣告服務的前提條件參數的集合，Rprs表示請求服務前提條件參數的集合，Aes表示廣告服務影響參數的集合，Res表示請求服務結果影響參數的集合。在這里需注意的是這四個參數都是本體中的概念而不是原子數據類型。基于公式(4)，函數SimIOPE(AS，RS)可計算服務的功能性特征(IOPE)的匹配度，其參數是廣告服務(AS)和請求服務(RS)，其結果是0至1之間的實數值。
服務功能的相似度計算公式如下:
其中α1、α2、α3、α4分別是輸入集、輸出集、前提條件集、結果影響集的權值，
α1+α2+α3+α4=1，0≤αi≤1，i=1，2，3，4. 權值可由用戶決定，如果用戶沒有對權值的要求，則可采用默認的平均權值，即視這四個方面同等重要。
功能匹配算法描述:
由于PR和IO的匹配算法相似，在這里只對IO匹配加以說明。
ParametersMatch(RS，AS，Reasoner reasoner)
{
Ucandidates=Ф;//候選子集初始為空
//inputs匹配
int inMatch=0;
int inCount1=RS.getInputs().size;
int inCount2=AS.getInputs().size;
for(int i=0;i for(int j=0;inCount1;j++){ //由推理機根據公式(5)計算相似度 inMatch=reasoner.Parametermatch(RS.getinputs(i)，AS.getinputs(j)); ifinMatch>Num2 // Num2是用戶設定的匹配閾值 ADD(Ucandidates，ASi);//將符合條件的AS加入候選集中 Endif } } //outputs匹配 int outMatch=0; int outCount1=RS.getOutputs().size; int outCount2=AS.getOutputs().size; for(int i=0;i for(int j=0;outCount1;j++){ //由推理機根據公式(5)計算相似度 outMatch=reasoner.Parametermatch(RS.getoutputs(i)，AS.getoutputs(j)); ifoutMatch>Num2 // Num2是用戶設定的匹配閾值 ADD(Ucandidates，ASi);//將符合條件的AS加入候選集中 Endif } } 3.3.3 非功能屬性QoS的匹配 功能性的匹配只滿足了請求服務方靜態的常規要求，這些常規要求相對固定。而如果用戶想要獲得高質量的Web服務，還需要用一些非功能的屬性來量化其服務功能，這就是Web服務的QoS(Quality of Service)，文獻[5]中Joge Cardoso給出了服務質量評價模型中應包括的因素，具體包括費用(cost)、時間(time)、可靠性(reliability)。這里再增加信譽度(Credit)因素。 函數SimQoS(AS，RS)計算廣告服務AS和請求服務RS的QoS相似度。可通過分別計算AS和RS的QoS中各維相似度的幾何距離來計算。函數返回一個0至1之間的實數，返回值越接近1，說明AS和RS越相似。 服務質量匹配算法描述: QoSMatch(RS，AS，Reasoner reasoner) { IntQoSMatch=0; Ucandidates=Ф;//候選子集初始為空 QoSMatch=reasoner.SimQoS(RS，AS);//由推理機計算SimQoS for (int i=0;AS<>Ф;i++){ if BasicMatch>Num4 //Num4是用戶設定的匹配閾值 ADD(Ucandidates，ASi);//將符合條件的AS加入候選集中 endif } } 4 算法性能分析 在評價服務匹配算法效率方面，通常用查準率和查全率來衡量一個Web服務匹配算法的好壞。查準率是指查詢返回符合查詢條件的Web服務數量與查詢返回Web服務總數量的比率;查全率是指查詢返回符合查詢條件的Web服務數量與測試樣本集中符合查詢條件的Web服務數量的比率。查準率和查全率越高，服務匹配算法越好。為了驗證本文匹配算法的有效性，設計了一個原型系統WSMS(服務匹配系統)，本文選取醫學診斷專家系統本體文件及100個可用于查詢疾病診療方案的Web服務，對于本文算法和OWL-S/UDDI匹配算法進行仿真性能測試，測試結果如表1所示。 由此可見，本文算法綜合考慮了服務的基本描述、服務功能和服務質量三個方面的相似度，具有較高的服務發現效率。 5 結束語 本文分析了基于推理的服務匹配算法的局限性，提出了一種基于本體概念相似度計算的服務匹配算法。實驗結果表明該算法能過濾掉大多數不相關服務，縮小服務匹配范圍，提高了服務匹配效率。下一步將完善算法和原型系統，考慮在語義網中存在多個異構本體情況下進一步改進服務匹配算法。 參考文獻: [1] Rudi Stuger，Richard Benjam ins V. Knowledge Engineering:Principles and Methods[J]. .Data and Knowledge Engineering 1998，25(2):161. [2] Massimo Paolucci，Takahiro Kawamura，Terry R Payne. Semantic matching of Web services capabilities[C]. In Proceedings of the First International Semantic Web Conference(ISWC). [3] 余曉峰.面向譯文選擇的雙語語義詞典自動構建研究[D].哈爾濱:哈爾濱工業大學，2005:30-42. [4] 劉群，李素建.基于《知網》的詞匯語義相似度計算[J].Computational Linguistics and Chinese Language Processing， 2002， 7(2):59-76. [5] Cardoso J.Bussler C.Semantic Web Services and Processes:Semantic Composition and Quality of Service[C].On the Move to Meaningfull Internet Computer 2002.
