基于WordNet和二分圖的語義Web服務(wù)發(fā)現(xiàn)算法

1、技術(shù)創(chuàng)新微計(jì)算機(jī)信息(管控一體化2010年第26卷第8-3期360元/年郵局訂閱號(hào):82-946現(xiàn)場總線技術(shù)應(yīng)用200例軟件時(shí)空基于WordNet 和二分圖的語義Web 服務(wù)發(fā)現(xiàn)算法Semantic Web service discovery Algorithm based on WordNet and bipartite graph(長沙理工大學(xué)華建新曹敦HUA Jian-xin CAO Dun摘要:由于Web 服務(wù)的描述參數(shù)都是有順序的,而服務(wù)提供者和用戶之間缺少對(duì)服務(wù)的共同語義描述約束,服務(wù)請(qǐng)求的描述參數(shù)都是無序的,它們之間不能直接進(jìn)行匹配調(diào)用。本文在OWL-S 的基礎(chǔ)上利用WordNe

2、t 計(jì)算參數(shù)的相似度,最后引入二分圖來解決這一不對(duì)稱匹配問題。實(shí)驗(yàn)結(jié)果表明本文算法有較好查準(zhǔn)率和查全率,同時(shí)本文算法易于實(shí)現(xiàn)。關(guān)鍵詞:Web 服務(wù);服務(wù)發(fā)現(xiàn);WordNet;二分圖中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:AAbstract:Because the parameters which described of web services are in order,there exists the lack of a common semantic describ -ing constraints between providers and users of web services,Par

3、ameters which described of the request is disorderly,they can not be used directly matching others.This paper adopts WordNet to calculate the similarity of the parameters based on OWL-S and quotes bipartite graph to solve the problem of asymmetric matching in the end.The experimental results show th

4、at the precision ratio and re -call ratio of this algorithm is better than others and it is easy to implement this algorithm at the same time.Key words:Web Service;service discovery;WordNet;bipartite graph文章編號(hào):1008-0570(201008-3-0198-03引言由于面向服務(wù)的體系結(jié)構(gòu)(SOA能夠提供更有效性和動(dòng)態(tài)的應(yīng)用,越來越多的分布、異構(gòu)信息系統(tǒng)的開發(fā)和集成都采用了SOA 技術(shù),而

5、Web 服務(wù)發(fā)現(xiàn)是SOA 非常重要的組成部分。隨著Internet 上可用的Web 服務(wù)數(shù)量的增加,尋找一個(gè)適合的Web服務(wù)來滿足服務(wù)請(qǐng)求者的要求變得越來越困難。如何方便有效地實(shí)現(xiàn)服務(wù)發(fā)現(xiàn),成為SOA 所要解決的關(guān)鍵問題之一。當(dāng)前Web 服務(wù)發(fā)現(xiàn)的主要是采用WSDL 和UDDI 技術(shù),利用基于關(guān)鍵字的匹配方法,該方法在查全率和查準(zhǔn)率上都不能夠滿足用戶的需求。為了提高服務(wù)發(fā)現(xiàn)的查全率和查準(zhǔn)率,研究人員在Web 服務(wù)的基礎(chǔ)上結(jié)合語義Web 技術(shù)提出了基于語義的Web 服務(wù)發(fā)現(xiàn)。關(guān)于語義Web 服務(wù)發(fā)現(xiàn)已有不少研究成果,主要是利用Ontology 來描述Web 服務(wù),然后通過這些帶有語義信息的描述實(shí)

6、現(xiàn)Web 服務(wù)來實(shí)現(xiàn)服務(wù)的自動(dòng)發(fā)現(xiàn),調(diào)用和組裝。雖然它們可以獲得比較理想的查全率和查準(zhǔn)率,但是這些方法實(shí)現(xiàn)難度高,對(duì)服務(wù)語義進(jìn)行建模的代價(jià)大,同時(shí)由于服務(wù)提供者和用戶之間缺少對(duì)服務(wù)的共同語義描述約束,Web 服務(wù)的描述參數(shù)都是有順序的,而服務(wù)請(qǐng)求的描述參數(shù)都是無序的,它們之間的不對(duì)稱性不能直接進(jìn)行匹配調(diào)用。本文提出的不對(duì)稱的語義Web 服務(wù)匹配算法是在OWL-S 的基礎(chǔ)上利用WordNet 來計(jì)算本體之間的相似度,然后利用二分圖來解決用戶的請(qǐng)求服務(wù)與服務(wù)操作的不對(duì)稱匹配問題,最后得到一組滿足要求且按照與用戶的請(qǐng)求服務(wù)的相似度降序排列的Web 服務(wù),每個(gè)Web 服務(wù)的描述參數(shù)都與用戶的請(qǐng)求參數(shù)一

7、一對(duì)應(yīng),為實(shí)現(xiàn)動(dòng)態(tài)調(diào)用打下基礎(chǔ)。1理論基礎(chǔ)1.1OWL-S 簡介OWL-S 是DARPA 組織在OWL 的基礎(chǔ)上,構(gòu)建出來的為Web 服務(wù)的發(fā)布者和請(qǐng)求者提供了統(tǒng)一的語義基礎(chǔ)。在OWL-S 中對(duì)Web 服務(wù)描述的基本信息主要有三種本體:Service Pro -file 用來發(fā)布和發(fā)現(xiàn)服務(wù);Service Model 用來對(duì)服務(wù)操作提供一個(gè)詳細(xì)描述;Service Grounding 描述了服務(wù)間如何交互。Service Profile 本體主要描述服務(wù)和服務(wù)提供者的信息,包括服務(wù)提供者的信息、服務(wù)的功能信息、服務(wù)屬性三個(gè)方面,其中服務(wù)的功能信息主要包括輸入、輸出、前置條件和效果(簡稱IOPE

8、。通過Service Profile 本體,服務(wù)提供者可以提供自己的服務(wù)說明,而服務(wù)查詢代理可以通過服務(wù)提供的Service Profile 信息來判斷是否滿足服務(wù)請(qǐng)求者的需求。1.2二分圖簡介無向圖G=(V,E,其中V 是頂點(diǎn)集,E 是邊集,如果該圖滿足V=V 0V 1,V 0V 1=,且e=(x,yE,均有x V 0,y V 1,則稱圖G 為二分圖。給定一個(gè)二分圖G,M 為G 邊集的一個(gè)子集,如果M 滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn),則稱M 是一個(gè)匹配。如果一個(gè)匹配中,圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián),則稱此匹配為完全匹配,也稱作完備匹配。如果G 為加權(quán)二分圖,則權(quán)值和最大的完備

9、匹配稱為最優(yōu)匹配。2語義Web 服務(wù)發(fā)現(xiàn)相關(guān)定義本文利用OWL-S 對(duì)Web 服務(wù)集和服務(wù)請(qǐng)求進(jìn)行預(yù)處理,得到一個(gè)Profiles 文檔,然后基于這些文檔實(shí)現(xiàn)Web 服務(wù)匹配。本文主要是利用Service Profile 中的輸入、輸出、前置條件和效果(簡稱IOPE來進(jìn)行匹配。定義1Web 服務(wù)ws 為一個(gè)四元組ws=I,O,P,E,其中I=i 1,i 2i n 是該服務(wù)的輸入消息集合;O=o 1,o 2o n 是該服務(wù)的輸出華建新:碩士基金項(xiàng)目:湖南省科技計(jì)劃項(xiàng)目(2009SK4006198-郵局訂閱號(hào):82-946360元/年技術(shù)創(chuàng)新 軟件時(shí)空PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)

10、注消息集合;P=p 1,p 2p n 是該服務(wù)的前置條件集合;E=e 1,e 2e n 該服務(wù)的效果集合。定義2服務(wù)請(qǐng)求r 為一個(gè)五元組來表示r=I r ,O r ,P r ,E r ,其中Ir =i r 1,i r 2i r m 是該服務(wù)請(qǐng)求的輸入消息集合;Or =o r 1,o r2o r m是該服務(wù)請(qǐng)求的輸出消息集合;Pr =p r 1,p r 2p r m是該服務(wù)請(qǐng)求的前置條件集合;Er =e r 1,e r 2e r m 該服務(wù)請(qǐng)求的效果集合;01是用戶設(shè)定的閾值,即一個(gè)服務(wù)與服務(wù)請(qǐng)求的相似度大于等于閾值該服務(wù)才是匹配的。定義3Web 服務(wù)匹配。Web 服務(wù)IOPE 分為兩類:前提(

11、IP和結(jié)果(OE。進(jìn)行匹配時(shí),用戶請(qǐng)求的前提(I r P r 的參數(shù)包含Web 服務(wù)所需的前提(IP的參數(shù),且Web 服務(wù)的結(jié)果(OE的參數(shù)包含了用戶請(qǐng)求的結(jié)果(O r E r 的參數(shù),且它們之間的相似度大于等于用戶提供的閾值,則匹配成功。由定義3可知,用戶請(qǐng)求的前提分量參數(shù)必須包含Web 服務(wù)的前提分量參數(shù),用戶請(qǐng)求的結(jié)果分量參數(shù)必須被包含于Web 服務(wù)的結(jié)果分量參數(shù)?，F(xiàn)有的二分圖不能很好解決這一問題,本文對(duì)二分圖進(jìn)行擴(kuò)展,提出一個(gè)擴(kuò)展最優(yōu)匹配,定義如下:定義4擴(kuò)展最優(yōu)匹配。對(duì)于一個(gè)二分圖G 和G 的一個(gè)匹配M,G 滿足條件|V0|V1|,M 是G 的一個(gè)擴(kuò)展最優(yōu)匹配,當(dāng)且僅當(dāng):1M 是覆蓋

12、V0中所有節(jié)點(diǎn);2M 是所有邊的權(quán)值加和最大的匹配。3語義Web 服務(wù)匹配算法本文提出的匹配算法基本思想是:根據(jù)服務(wù)請(qǐng)求信息預(yù)處理服務(wù)請(qǐng)求信息,利用二分圖來計(jì)算服務(wù)集每一個(gè)服務(wù)與服務(wù)請(qǐng)求之間的相似度,將相似度大于等于用戶給定閾值的服務(wù)添加到結(jié)果列表,直到服務(wù)集全部匹配完畢,返回按相似度降序排列的結(jié)果列表。其流程見圖1:圖1服務(wù)匹配流程3.1概念相似度的計(jì)算WordNet 是一個(gè)英語字典。由于它包含了語義信息,所以有別于通常意義上的字典。WordNet 根據(jù)詞條的意義將它們分組,每一個(gè)具有相同意義的字條組稱為一個(gè)synset (同義詞集合。WordNet 為每一個(gè)synset 提供了簡短,概要的

13、定義,并記錄不同synset 之間的語義關(guān)系。利用WordNet 計(jì)算兩個(gè)元素的語義距離,進(jìn)而得到它們的相似度。具體計(jì)算方法如下:Sim(w1,w2=1/(1+len(w1,w2(1其中l(wèi)en (w1,w2是詞w1到w2的路徑長度。Sim(w1,w20,1。3.2基于二分圖的不對(duì)稱匹配算法由定義1,對(duì)于Web 服務(wù)每一個(gè)分量,它都是由一組參數(shù)表示。由于用戶無法感知Web 服務(wù)集中服務(wù)的每一個(gè)分量的參數(shù)構(gòu)成次序,所以無法直接匹配,本文采用二分圖技術(shù)來解決這種不對(duì)稱本體之間的匹配。具體算法如下:(1如果|I|>|I r |、|P|>|P r |、|O r |>|O |、|E r

14、|>|E|中有一個(gè)成立,由定義3可知匹配不成功,返回;(2利用公式(1計(jì)算I=i 1,i 2i n 與Ir =i r 1,i r 2i r m 每個(gè)參數(shù)之間的相似度;(3初始化二分圖G,其中V 0=I,V 1=I r ,邊集E 就是I 與I r 的連線,邊的權(quán)值就是它們之間的相似度;(4根據(jù)邊的權(quán)值,求出G 的擴(kuò)展最優(yōu)匹配M 。(5求出M 中所有邊的權(quán)值的平均值作為I 與Ir 的相似度。(6重復(fù)(2到(5求出P 與P r 的相似度。(7利用公式(1計(jì)算O=o 1,o 2o n 與Or =o r 1,o r 2o r m 每個(gè)參數(shù)之間的相似度;(8初始化二分圖G,V 0=O r ,V 1=

15、O,邊集E 就是O 與O r 的連線,邊的權(quán)值就是它們之間的相似度;(9根據(jù)邊的權(quán)值,求出G 的擴(kuò)展最優(yōu)匹配M 。(10求出M 中所有邊的權(quán)值的平均值作為O 與O r 的相似度。(11重復(fù)(7到(10求出E 與E r 相似度。(12對(duì)4個(gè)分量相似度求平均,得到兩個(gè)服務(wù)之間的相似度,如果相似度大于用戶給的,該服務(wù)加入結(jié)果集。其中步驟4和9,求二分圖最優(yōu)匹配的經(jīng)典算法是由Kuhn 和Munkres 獨(dú)立提出的KM 算法,本文對(duì)二分圖最優(yōu)匹配進(jìn)行了擴(kuò)展,所以KM 也要做相應(yīng)改進(jìn),算法步驟如下:(1如果|V 0|=|V 1|,則按照KM 算法來求解。(2如果|V 0|<|V 1|,則在V0增加|

16、V 1|-|V 0|個(gè)虛擬節(jié)點(diǎn),V 0每增加一節(jié)點(diǎn)同時(shí)增加V 1中每一節(jié)點(diǎn)到該節(jié)點(diǎn)的邊,邊的權(quán)值為0。這樣G 就轉(zhuǎn)化為。(3按照KM 算法來求解的最優(yōu)匹配。(4最后去掉剛剛增加的節(jié)點(diǎn)和邊,把的最優(yōu)匹配轉(zhuǎn)化為G 的最優(yōu)匹配。圖2基于二分圖的不對(duì)稱匹配算法示意圖a 初始建立的二分圖b 最后得到的擴(kuò)展最優(yōu)匹配4實(shí)驗(yàn)結(jié)果為了驗(yàn)證文中提出的Web 服務(wù)匹配發(fā)現(xiàn)方法的有效性,我們用召回率和準(zhǔn)確率作為度量Web 服務(wù)發(fā)現(xiàn)的指標(biāo),以評(píng)價(jià)其性能。召回率是指查詢返回符合查詢條件的Web 服務(wù)與測試樣本集中符合查詢條件的Web 服務(wù)的比率,準(zhǔn)確率是指查詢返回符合查詢條件的Web 服務(wù)與查詢返回Web 服務(wù)總數(shù)量的比

17、率。召回率和準(zhǔn)確率越高,服務(wù)匹配算法越好。本文使用了以下4種開發(fā)工具來構(gòu)建原型系統(tǒng):Eclipse,199-技術(shù)創(chuàng)新微計(jì)算機(jī)信息(管控一體化2010年第26卷第8-3期360元/年郵局訂閱號(hào):82-946現(xiàn)場總線技術(shù)應(yīng)用200例軟件時(shí)空500個(gè),與經(jīng)典的argument UDDI Registry 系統(tǒng)進(jìn)行仿真性能對(duì)比。實(shí)驗(yàn)結(jié)果見表1(表中AUDDIR 代表argument UDDI Reg -istry,Rec 代表召回率,Pre 代表準(zhǔn)確率。結(jié)果表明本文的算法有比較好的召回率和準(zhǔn)確率。表1實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)5結(jié)論傳統(tǒng)的基于XML 的服務(wù)描述語言缺乏對(duì)服務(wù)的語義描述,文中引入OWL-S 描述服務(wù)來

18、解決該問題,并提出一個(gè)不對(duì)稱的語義Web 服務(wù)匹配算法。對(duì)服務(wù)的文本描述、功能描述和參數(shù)進(jìn)行了匹配,最后對(duì)候選的服務(wù)發(fā)布進(jìn)行排序,得到一組Web 服務(wù)描述參數(shù)都與用戶的請(qǐng)求參數(shù)一一對(duì)應(yīng)的Web 服務(wù)集,找出相似度最高的服務(wù),從而實(shí)現(xiàn)服務(wù)的自動(dòng)發(fā)現(xiàn)調(diào)用機(jī)制。文為Web 服務(wù)的動(dòng)態(tài)調(diào)用打下基礎(chǔ);而且由于沒用使用復(fù)雜的邏輯推理,易于編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明本文算法查準(zhǔn)率和查全率要優(yōu)于argument UDDI Registry,具有更大的應(yīng)用范圍。本文的下一步工作主要集中于如何在Web 服務(wù)發(fā)現(xiàn)過程中支持用戶的非功能性需求(如QoS。本文創(chuàng)新點(diǎn):提出了語義Web 服務(wù)匹配定義,利用擴(kuò)展二分圖來解決We

19、b 服務(wù)與服務(wù)請(qǐng)求的IOPE 描述參數(shù)不對(duì)稱性,同時(shí)利用WordNet 來降低語義Web 服務(wù)建模復(fù)雜性。參考文獻(xiàn)1岳昆,王曉玲,周傲英.Web 服務(wù)核心支撐技術(shù):研究綜述J.軟件學(xué)報(bào),2004,15(3:428-442.3PAOLUCCI M,KAWAMURA T,PAYNE T R,et a1.Importing the semantic Web in UDDIM.London:Springer-Verlag,2002:225-236.5Vaculin,R.;Sycara,K.Semantic Web Services Monitoring:An OWL -S Based Approach

20、 C.Hawaii International Conference on System Sciences,Proceedings of the 41st Annual 7-10Jan.2008Page(s:313313.6Ayse B.Bener,Volkan Ozadali,Erdem Savas Ilhan.Semantic matchmaker with precondition and effect matching using SWRLJ.Expert Systems with Applications,Volume 36,Issue 5,July 2009,Pages 9371-

21、9377.7Matthias Klusch,Benedikt Fries,Katia Sycara.OWLS -MX:A hybrid Semantic Web service matchmaker for OWL-S services.JWeb Semantics:Science,Services and Agents on the World Wide Web,Volume 7,Issue 2,April 2009,Pages 121-133.8錢雪忠,王創(chuàng)偉等.一種擴(kuò)展Web 服務(wù)體系構(gòu)架下的服務(wù)發(fā)現(xiàn)技術(shù)J.微計(jì)算機(jī)信息.2008,4-3:p170-172作者簡介:華建新(1981-,男

22、,漢,湖南衡南人,碩士,主要研究方向?yàn)閃eb 服務(wù);曹敦(1979-女,漢,湖南衡陽人,助教,主要研究方向:無線信道建模。Biography:HUA Jian -xin (1981-,Male (Han,Hunan Heng -nan,Maste,Special:Web Service.(410076湖南長沙長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院華建新曹敦(Institute of Computer and Communication Engineering;Changsha University of Science and Technology,Changsha 410076,ChinaHUA

23、Jian-xin CAO Dun通訊地址:(410076湖南長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院華建新(上接第171頁連接強(qiáng)度和概念內(nèi)涵的連接強(qiáng)度使得用戶可以進(jìn)行多條路徑的選擇,且當(dāng)一條路徑出現(xiàn)臨時(shí)狀況不可用時(shí),可以選擇其他路徑來進(jìn)行導(dǎo)航。利用本體對(duì)室內(nèi)環(huán)境位置和用戶需求的語義描述,以及本體描述的無二義性與邏輯推理的準(zhǔn)確性,保證了室內(nèi)導(dǎo)航的準(zhǔn)確率和用戶導(dǎo)航的滿意度。參考文獻(xiàn)1林敏,鮑煦等.改進(jìn)Monte Carlo 算法用于RFID 標(biāo)簽的室內(nèi)定位J.微計(jì)算機(jī)信息.2008,5-2:p203-2042Wille,R.Reconstructing lattice theory:an approach based on hi -erarchies of concepts.In:Rival,Ivan ed.Ordered Sets.Dordrecht -Boston:Reidel,1982:P445-4703Gander B,Wille R.Formal Concept Analysis M.Mathematical Foundations.Berlin:Springer,19994Antoniou,G.,&Harmelen,F.v.“A Semantic Web Primer ”.Massa-chusetts:The MIT Press,20045Gomez-Perez