??? 在語義Web服務中，服務需求和發(fā)布雙方一般采用共同的領域本體準確表示服務的輸入、輸出、前提和結(jié)果中的信息。通過對本體中概念關系的推理和分析，可知服務需求和發(fā)布方的匹配程度。本體中最主要的關系是概念之間的子類關系(subClassOf)，也稱繼承關系[4]。由子類關系可以定義概念之間的包含關系。如果概念A是概念B的子類(subClass)，概念B包含(Subsume)概念A，包含關系是可傳遞的?？紤]概念之間的單繼承關系，本體可以表示成1棵分類樹。
1.2 經(jīng)典匹配算法及其結(jié)果分析
??? 經(jīng)典匹配算法利用描述邏輯和本體語言OWL來實現(xiàn)對Web服務的匹配，匹配對象主要是ServiceProfile中的IOPEs參數(shù)。對兩個服務之間的匹配程度分成了Exact，Plug-In，Subsume，F(xiàn)ail 4個級別：
??? (1)Exact：當發(fā)布服務的輸出與請求的輸出描述完全等價或當請求服務的輸出是發(fā)布服務輸出的直接子類時，稱為Exact精確匹配。
??? (2)Plug-In：當發(fā)布服務的輸出包含請求服務的輸出時，稱為Plug-In插入匹配。
??? (3)Subsume：當請求服務的輸出包含發(fā)布服務的輸出時，稱為Subsume包含匹配。
??? (4)其他情況，稱為Fail，匹配失敗。
??? 設請求服務的某個輸出為outR，發(fā)布服務的某個輸出為outA，則每一對輸出的匹配算法可描述為如下[4]：
??? Match(outR，outA)
??? { if outA=outA return Exact；
????? if outR subclassOf outA return Exact；
????? if outA subsume outR return Plug-In；
????? if outA subsume outA return Subsume；
????? else return Fail；
??? }
??? 每一對輸入匹配結(jié)果與輸出匹配結(jié)果的包含關系是相反的，即Match(outR，outA)應用到每一對輸入的匹配為Match(inA，inR)。
??? 在匹配算法中，不存在包含關系的概念之間認為其沒有語義聯(lián)系，返回結(jié)果為“匹配失敗(Fail)”。這一點符合Web服務的匹配要求。比如在圖1中如果請求服務查詢的是“Car”，而發(fā)布的服務是“Truck”，雖然2個概念都是“Vehicle”的子類，但因為發(fā)布的服務不能滿足請求，則認為兩者之間是不匹配的。
??? 對于插入匹配由于發(fā)布的服務輸出包含了請求服務的輸出(或請求服務的輸入包含了發(fā)布服務的輸入)，而包含匹配是請求服務的輸出包含了發(fā)布服務的輸出(或發(fā)布服務的輸入包含了請求服務的輸入)，因此插入匹配的匹配程度高于包含匹配。在圖1中，如果請求查詢的服務是“Ford”汽車，發(fā)布的服務是“Vehicle”，查詢的服務通常情況下是可以滿足請求的，這時返回結(jié)果為“插入”匹配。如請求查詢?nèi)我獾摹癡ehicle”，發(fā)布“Mazda”汽車服務，只有少數(shù)情況能滿足請求，這時返回結(jié)果為“包含”匹配。所以，4類匹配的匹配程度由高到低的排序是：精確匹配、插入匹配、包含匹配和不匹配。
??? 該經(jīng)典匹配算法通過對本體中類的包含關系的推理，給出服務發(fā)布方和請求方之間的匹配等級，通過返回不同匹配等級的服務提高服務的查準率和查全率，但它最大的缺點在于不能給出服務之間的精確匹配，影響了服務匹配質(zhì)量。如圖1所示，如果請求方的輸出是Ford汽車，提供方的輸出不管是Car，Vehicle還是Machine，返回結(jié)果都是插入匹配，但事實三者的匹配程度相差很大，這不利于在大量的服務中準確地查找所需的服務。而概念深度對匹配精度也有一定的影響，高層不同概念之間比底層概念之間的語義差別要大，因為越高層次的概念越概括，其區(qū)分度越大，越底層的概括越具體，越趨近屬于同一個分支。如“機動車”和“非機動車”的相似度顯然要比同屬于“機動車”概念的“汽車”和“卡車”的語義差別要大。為了解決以上問題，本文提出一種用本體概念間相似度算法來進行服務的精確匹配，同時提出兩種語義權重分配方法用于計算本體概念間的語義距離和相似度。新算法既保持了原算法的匹配等級的合理性，又能提供精確的匹配。
2 概念相似度算法
2.1 權重分配與語義距離計算算法
??? 目前大多數(shù)基于語義距離的相似度計算方法中，用到的語義距離都是取2個本體概念之間的最短路徑，即從概念C1到概念C2所經(jīng)過的最少邊的數(shù)目。本文將權重分配在2個概念C1和C2之間的關系上，也即本體圖中的“邊”上。權重分配原則滿足概念之間的語義距離隨著本體分類樹的深度的增加而減小。
??? 本文提出兩種權重分配方法：一種為按層等分，首先給定權重a，然后按層等分a(根節(jié)點為第1層)，假設該本體分類樹層次數(shù)為n，則第n層節(jié)點所在的每條分支的權重計算公式為式(1)(因為n層的本體分類樹，深度為n-1，關系sub(c₁，c₂)為繼承關系)。
　　
??? 另一種稱為歸一法，給定整個本體分類樹的權值為1，假如該樹根節(jié)點有n個分支，則每個分支總權重為1/n，如果該分支節(jié)點又有m個子分支，那么該分支節(jié)點所在分支的權重為該分支總權重的1/t(t的值在系統(tǒng)設計時指定，一般取2或3)，而該分支節(jié)點的所有子分支的總權重為該分支節(jié)點所在分支權重的1/t，每條分支計算公式如式(2)所示(關系sub(c₁，c₂)為繼承關系)：
　　
??? 例如，對于圖1根據(jù)本文提出的權重分配方法按式(1)有：W[sub(Machine，Computer)]=a/2=0.5a；W[sub(Vehicle，Truck)]=a/4=0.25a；W[sub(Machine，Toyota)]=0.125a。
??? 對于圖1根據(jù)本文提出的權重分配方法按式(2)有(t=2)：W[sub(Machine，Computer)]=1/2=0.5；W[sub(Machine，Vehicle)]=1/4=0.25；W[sub(Car，Toyota)]=1/48。
??? 定義1：定義概念c1和c2之間的語義距離為distance(c₁，c₂)。
??? 定義2：定義概念節(jié)點c1和c2之間的路徑長度為Lengthc₁，c₂)。

??? 定義3：定義概念節(jié)點c1和c2之間的語義距離為負值，即distance(c₁，c₂)。<0。
??? 對于表示本體的分類樹，可以用2個不同概念節(jié)點之間的距離來衡量概念之間的相似度。為了滿足服務匹配的要求與計算方便，在計算任意兩點之間的語義距離時選取公式(1)來計算(a=1)，可以通過如下算法得到：
??? (1)查看c₁和c₂是否是同一個概念。
??? 如果是，則distance(c₁，c₂)=0；如果否，轉(zhuǎn)入(2)。
??? (2)查看c₁和c₂之間是否存在直接繼承關系。
??? 如果是，則distance(c₁，c₂)=W[sub(c₁，c₂)]×1，而distance(c₂，c₁)=-[W[sub(c₁，c₂)]×1]；如果否，轉(zhuǎn)入(3)。
??? (3)查看c₁和c₂之間是否存在間接的繼承關系。
??? 如果是，則distance(c₁，c₂)=Length(c₁，c₂)×∑[W[sub(c₁，c₂)]，其中∑[W[sub(c₁，c₂)]為該路徑上的權重之和；distance(c₂，c₁)=-Length(c1，c2)×∑[W[sub(c₁，c₂)]，如果否，轉(zhuǎn)入(4)。
??? (4)c₁和c₂之間無繼承關系，語義距離distance(c₁，c₂)=∞。
??? 根據(jù)以上算法對于圖1，Machine與Machine滿足算法的第1種情況，所以distance(Machine，Machine)=0，Truck到Vehicle滿足算法的第2種情況，所以distance(Vehicle，Truck)=0.125，Machine到Car滿足算法的第3種情況，此時語義距離為負數(shù)，所以distance(Machine，Car)=-0.75，Computer到Truck滿足算法的第4種情況，所以distance(Computer，Truck)=∞；
2.2 相似度計算
??? 得到2個概念c₁和c₂之間的語義距離distance(c₁，c₂)之后，需要構造合理的相似度函數(shù)，將語義距離轉(zhuǎn)化成相似度。相似度函數(shù)需要滿足以下幾個主要特性[5]：
??? (1)當語義距離為0時，相似度為l。即當2個概念相同時，相似度為1。
??? (2)此函數(shù)隨語義距離的增加而減小。即語義距離大的概念間的相似度小于語義距離小的概念間的相似度。
??? (3)函數(shù)的輸出必須保證在[0，1]區(qū)間內(nèi)。?
??? 根據(jù)以上3個特性，得到2個概念c₁、c₂之間的相似度函數(shù)SimF(c₁，c₂)定義如下：
???
??? 通過以上定義，分類樹中2個概念的匹配程度就是[0，1]中的1個具體實數(shù)，數(shù)值越大，節(jié)點之間的距離越短，節(jié)點所對應的概念的相似度越高。按以上定義，傳統(tǒng)算法中的“精確匹配”的相似度為1，“匹配失敗”的相似度為0，“插入匹配”的相似度為1個(0.5，1)的實數(shù)，“包含匹配”的相似度為1個(0，0.5)之間的實數(shù)。
??? α，β分別為影響因子，α，β的取值決定了語義距離影響相似度取值的大小，α，β的取值越大，同樣距離下得出的相似度就越小。直觀看來，合理的α，β取值需要保證在語義距離為l時(即非常相近的2個概念如具有父子關系的概念)，相似度在0.5以上。根據(jù)上面提出的計算相似度算法公式(3)(α=0.9，β=0.8)得到圖1中個本體概念之間的相似度，如表1所示。

??? 通過上表分析可以看出，根據(jù)本文提出的算法，既提高了服務的匹配精度，還保持了傳統(tǒng)算法的匹配等級的合理性。例如，如果按照經(jīng)典的匹配算法，如果請求服務的輸出為Mazda，則服務輸出為Machine，Vehicle和Car的服務都能滿足要求(相似度都≥0.5)，而利用本文提出的算法(相似度≥0.5)，則只有輸出為Mazda的服務滿足要求。如果發(fā)布的服務與請求的服務中有多個輸入?yún)?shù)和輸出參數(shù)，則可以取匹配度最高的參數(shù)來匹配某一個請求的輸入或輸出，最終的匹配結(jié)果可以是請求服務所有輸入輸出參數(shù)的加權平均值。
3 實驗結(jié)果與分析
??? 在服務匹配中，通常用查準率和查全率來衡量一個Web服務匹配算法的好壞。查準率是指查詢返回符合查詢條件的Web服務數(shù)量與查詢返回Web服務總數(shù)量的比率；查全率是指查詢返回符合查詢條件的Web服務與測試樣本集中符合查詢條件的Web服務的比率。查準率和查全率越高，服務匹配算法越好。為了驗證本文匹配算法的有效性，開發(fā)了1個原型系統(tǒng)WSMS(Web服務匹配系統(tǒng)，本文精確匹配算法實現(xiàn))，參考OWLS-TC V2服務測試數(shù)據(jù)集[6]，制定了測試數(shù)據(jù)集WSMS-TC(該測試集來自3個知識領域，每個領域抽取50個服務描述，共150個)，對WSMS和經(jīng)典的OWL-S/UDDI匹配算法進行了仿真性能測試，對于要求返回精確度為0.2以上或0.4以上的服務，OWL-S/U DDI匹配取包含匹配的結(jié)果；對于要求返回精確度為0.5以上、0.6以上或0.8以上的服務，OWL-S/ＵDDI匹配取插入匹配的結(jié)果，統(tǒng)計結(jié)果如表2所示(圖中用OUDDIS代替OWL-S/UDDI算法實現(xiàn)的系統(tǒng))。