一種基于本體相似度的Web服務(wù)匹配算法

殷華英，劉訓(xùn)沛，耿碩陽

(1.承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系，河北承德 067000;2.遼寧大學(xué) 信息學(xué)院 ，遼寧 沈陽 110036)

一種基于本體相似度的Web服務(wù)匹配算法

殷華英1，2，劉訓(xùn)沛2，耿碩陽2

(1.承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系，河北承德 067000;2.遼寧大學(xué) 信息學(xué)院 ，遼寧 沈陽 110036)

服務(wù)匹配也被認(rèn)為是基于本體概念的相似度計(jì)算。針對(duì)本體結(jié)構(gòu)中概念之間的IS-A關(guān)系，通過對(duì)語義相似度相關(guān)算法的研究，提出了一種結(jié)合信息論模型和語義距離模型的相似度算法，并在此基礎(chǔ)上上構(gòu)建了二層服務(wù)匹配模型，從而實(shí)現(xiàn)了對(duì)服務(wù)的有效區(qū)分和匹配。

本體;概念;相似度;語義距離;服務(wù)匹配

Web服務(wù)是架構(gòu)在XML和Internet技術(shù)之上的分布式計(jì)算技術(shù)，作為一種基于網(wǎng)絡(luò)環(huán)境的自適應(yīng)、自描述、模塊化的應(yīng)用程序，因其具有良好的互操作性和可重用性，在電子商務(wù)、應(yīng)用集成、流程管理等領(lǐng)域中得到了越來越廣泛的應(yīng)用［1］。隨著互聯(lián)網(wǎng)應(yīng)用技術(shù)的發(fā)展和應(yīng)用需求的需要，互聯(lián)網(wǎng)上出現(xiàn)了越來越多的Web服務(wù)，這樣如何從這些服務(wù)當(dāng)中快速有效的發(fā)現(xiàn)自己需要的服務(wù)就成為一個(gè)急需解決的問題。

作為一個(gè)提供發(fā)布和查找的基礎(chǔ)架構(gòu)規(guī)范，UDDI提供了對(duì)服務(wù)注冊(cè)信息進(jìn)行關(guān)鍵字精確匹配的服務(wù)查詢，但因?yàn)槿狈Ψ?wù)的語義信息，在服務(wù)的查準(zhǔn)率和查全率上都不是很令人滿意。目前，基于語義的Web服務(wù)匹配己經(jīng)引起了國內(nèi)外學(xué)者越來越多的重視，成為Web服務(wù)研究的熱點(diǎn)之一。這類方法也被認(rèn)為是應(yīng)用前景最廣闊的服務(wù)匹配方法。在這類方法中，通過語義Web技術(shù)，將基于本體的知識(shí)標(biāo)注為Web服務(wù)增加語義信息，從而增強(qiáng)了Web服務(wù)的語義描述能力，為Web服務(wù)的匹配提供了語義層上的支持。目前，服務(wù)匹配過程大多是以Web服務(wù)模型OWL-S為基礎(chǔ)，根據(jù)本體中概念之間的關(guān)系，結(jié)合語義邏輯推理、語義相似度計(jì)算等方法實(shí)現(xiàn)的。和傳統(tǒng)的基于關(guān)鍵字的服務(wù)匹配方法相比，在服務(wù)的查全率和查準(zhǔn)率上，效果會(huì)有顯著改善。

1 本體相似度的混合算法

1.1 算法思想

［2］中給出的方法，本文在此基礎(chǔ)上提出了一種本體語義相似度的混合計(jì)算方法。針對(duì)本體中概念之間只存在IS-A類型的關(guān)系，對(duì)關(guān)系權(quán)值的計(jì)算進(jìn)行了簡(jiǎn)化。通過對(duì)基于網(wǎng)絡(luò)距離模型和基于信息論模型的兩種方法進(jìn)行綜合，提出了一種簡(jiǎn)單高效的計(jì)算相似度的方法。先利用信息論模型計(jì)算概念出現(xiàn)的概率和包含的信息量，再根據(jù)概念的信息量計(jì)算連接邊的權(quán)值，最后利用網(wǎng)絡(luò)距離的方法求出概念間的最短語義距離，由此求出概念之間的相似性。

1.2 相關(guān)公式

該公式用來計(jì)算概念層次結(jié)構(gòu)樹中概念c出現(xiàn)的概率。其中r為根概念，p為概念c的父概念，n為概念p的直接子概念個(gè)數(shù)，p(c)為概念c的出現(xiàn)概率。

對(duì)于概念出現(xiàn)概率的計(jì)算，本文未采用文本集統(tǒng)計(jì)的方法，而是將整個(gè)本體看成是一個(gè)大樣本空間。在只存在IS-A關(guān)系的本體中，在計(jì)算概念出現(xiàn)的次數(shù)時(shí)，如果某個(gè)概念出現(xiàn)一次，則認(rèn)為它的所有父概念都出現(xiàn)一次，反過來，也即計(jì)算某概念的出現(xiàn)次數(shù)時(shí)應(yīng)將其所有后代概念的出現(xiàn)次數(shù)累加起來。對(duì)于根概念，它包含其它所有概念，認(rèn)為它的出現(xiàn)概率為1，其它的節(jié)點(diǎn)出現(xiàn)概率可按照此公式遞歸求出。

該公式用來計(jì)算領(lǐng)域本體中概念c包含的信息量。p(c)為概念c的任一實(shí)例出現(xiàn)的概率，Ires(c)為概念c的信息量。可知，隨著概念概率的增加，它所包含的信息量是逐漸減小的。

該公式用來計(jì)算概念c1和概念c2最短語義距離，由概念c1、c2連接路徑上的邊的權(quán)值累加求和得出。其中:parent(c)為概念c的直接父節(jié)點(diǎn)。path(c1，c2)為概念c1、c2連接路徑中的所有概念節(jié)點(diǎn)，包括c1和c2概念節(jié)點(diǎn)。LCA(c1，c2)為c1、c2的最近共同祖先，在計(jì)算時(shí)，應(yīng)將LCA(c1，c2)排除在外。

1.3 算法過程

計(jì)算概念間的語義距離，就是計(jì)算它們連接路徑上的邊的權(quán)值之和，而邊的權(quán)值確定，需要從根概念開始計(jì)算每個(gè)概念所包含的信息量，然后再根據(jù)信息量確定相鄰概念間連接邊的權(quán)值。

定義1 概念c1，c2的生成子樹:從根節(jié)點(diǎn)到概念c1、c2連接路徑上的所有節(jié)點(diǎn)構(gòu)成的樹。

定義2 概念c1，c2的最小生成子樹:從概念的最近共同祖先到概念c1、c2連接路徑上所有節(jié)點(diǎn)構(gòu)成的樹。

具體過程分為以下3步:

step1:從概念節(jié)點(diǎn)c1、c2回溯到根節(jié)點(diǎn)，確定概念的生成子樹、最小生成子樹。

step2:從根節(jié)點(diǎn)往概念節(jié)點(diǎn)c1、c2掃描，計(jì)算概念c1、c2的生成子樹上每條邊的權(quán)值。

step3:對(duì)概念c1、c2的最小生成子樹中的每條邊的權(quán)值累加，并進(jìn)行相似度轉(zhuǎn)化，即為所求結(jié)果。

下面以圖1的Vehicile本體中概念BMW和Car為例說明計(jì)算相似度的計(jì)算過程。

計(jì)算生成樹上的各個(gè)概念的出現(xiàn)概率和包含的信息量:

計(jì)算連接邊的權(quán)值:

最終的計(jì)算結(jié)果如圖2所示。

則概念BMW和Car的語義距離dist(BMW，Car)=0.068。

2 兩層服務(wù)匹配模型

給出本體概念相似度計(jì)算方法之后，就可以把它應(yīng)用于語義Web服務(wù)的匹配。一般來講，對(duì)服務(wù)的匹配主要是通過對(duì)服務(wù)的IOPE進(jìn)行匹配來實(shí)現(xiàn)的，根據(jù)本文的算法，本文關(guān)注的是對(duì)服務(wù)IO的匹配。服務(wù)W的描述如下:

W={WName，WIn，WOut}，其中:

Wname為服務(wù)的名字;

WIn=＜in1，in2，...inn＞為服務(wù)的輸入?yún)?shù)集，是實(shí)際輸入?yún)?shù)在領(lǐng)域本體庫中對(duì)應(yīng)的概念表示;

WOut=＜o(jì)ut1，out2，...outn＞為服務(wù)的輸出參數(shù)集，是實(shí)際輸出參數(shù)在領(lǐng)域本體庫中對(duì)應(yīng)的概念表示。

為減少服務(wù)匹配的規(guī)模，降低問題的復(fù)雜度，在對(duì)服務(wù)的IO進(jìn)行語義相似度計(jì)算之前，先進(jìn)行語義推理，排除那些不符合條件的服務(wù)。首先對(duì)比較的兩個(gè)服務(wù)利用OWL-S解析，獲取服務(wù)IO的相關(guān)概念，再利用Paolucci［3］提出的方法進(jìn)行語義推理，進(jìn)行第一層語義匹配。然后根據(jù)匹配結(jié)果，來決定下一步是否進(jìn)行語義距離的計(jì)算。當(dāng)結(jié)果為Exact服務(wù)匹配成功時(shí)，或者Fail，服務(wù)完全不匹配時(shí)，這時(shí)就不再進(jìn)行后面的語義距離計(jì)算，只有在語義推理結(jié)果為PlugIn或Subsume，提供的服務(wù)能部分滿足請(qǐng)求服務(wù)時(shí)，才使用本章提出的算法進(jìn)行概念的語義距離計(jì)算，對(duì)請(qǐng)求服務(wù)和提供服務(wù)的輸入、輸出進(jìn)行語義距離計(jì)算。最后將對(duì)輸入、輸出語義距離計(jì)算的結(jié)果進(jìn)行綜合和排序，返回給服務(wù)請(qǐng)求者。這是第二層的匹配。兩層的語義匹配模型結(jié)構(gòu)圖如圖3所示。

3 結(jié)束語

在服務(wù)匹配和發(fā)現(xiàn)中，傳統(tǒng)的UDDI基于關(guān)鍵字和簡(jiǎn)單分類的發(fā)現(xiàn)機(jī)制已經(jīng)不能很好的滿足要求，存在查全率和查準(zhǔn)率較低的情形。本文通過對(duì)兩種相似度算法—基于網(wǎng)絡(luò)距離模型和基于信息論模型的有效融合，提出了一種基于IS－A關(guān)系的概念相似度混合算法，該方法計(jì)算過程簡(jiǎn)單，復(fù)雜度低，并和語義推理方法結(jié)合起來，搭建了一個(gè)兩層語義匹配模型。通過該模型，可以有效地、準(zhǔn)確地對(duì)Web服務(wù)進(jìn)行區(qū)分和匹配。

參考文獻(xiàn):

［1］ 俞堅(jiān)，韓燕波.面向服務(wù)的計(jì)算—原理和應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

［2］ Conrath D.，Jiang J.Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy.In Proceedings of International Conference on Reaseareh in Computational Linguistics，Taiwan，1997.

［3］ Massimo Paolucci，Takahiro Kawamura，Terry R.Payne，et al.“Semantic Matching of Web Services Capabilities，”I In Computer Science，2002，Vol.2342:333 －347.

［4］ Lin Dekang.An information － theoretic definition of similarity.in proceedings of the 15th international Conference on Machine Learning，Madison，Wisconsin，1998.

A Web Service Matching Algorithm Based on Similarity of Ontology

YIN Hua-ying1，2，LIU Xun-pei2，GENG Shuo-yang2
(1.Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China;2.Information School，Liaoning University，Shenyang 110036，Liaoning，China)

Service matching is also considered to be the concept of ontology-based similarity calculations.For the IS-A relationship between the concepts of ontology structure，the paper puts forward a kind of similarity algorithm that combines information theory model with semantic distance model through the research to semantic similarity algorithm.Based on this，it also builds up a second service matching model to fulfill the effective distinguishing and matching service.

ontology;concept;similarity;semantic distance;service matchmaking

TP393

B

1008-9446(2011)03-0050-04

2011-05-31

殷華英(1976－)，男，河北承德人，承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系講師，主要從事計(jì)算機(jī)軟件教學(xué)工作。