基于詞典的服務語義標注和匹配算法

錢海忠,蔡莉莉

(1.金陵科技學院軟件工程學院,江蘇 南京 211169;2.中國傳媒大學南廣學院,江蘇 南京 211172)

語義萬維網[1]與萬維網服務相結合,為實現(xiàn)語義萬維網服務[2]的服務發(fā)現(xiàn)、匹配、調用及組合等功能的自動化提供了一條可行的路徑,有關該方面的研究成果不斷涌現(xiàn)。大多數(shù)研究成果借助本體技術,但是依賴于本體的算法也存在一些不足: 1) 要實現(xiàn)對萬維網服務語義標注的前提條件是在因特網上有一個共同認知的領域本體庫,這個前提難以做到;2) 本體庫的構建需要知識工程領域專家的參與,是一件非常費時、費力的工程,不易于大規(guī)模自動化處理,同時隸屬于不同領域本體庫的概念,它們的語義相似性計算[3]還存在一定困難;3) 本體技術是面向專家級的而非普通級用戶,這就要求服務提供商必需在本體專家指導下才能精確的發(fā)布服務,使用服務的用戶也必需具有一定本體知識才能提交經過本體標注的服務請求文檔,這樣限制了服務的應用層面。

1 基于語義詞典的服務語義標注

1.1 算法思想及基本概念

根據(jù)Tversky的模型[4],概念的特征屬性是最能描述概念的本質,也是判別概念相似性最好依據(jù)。本文的算法依據(jù)該模型采用了描述概念特征的特征詞集來描述概念的方式,概念之間的相似性則通過在語義詞典上對特征詞集的語義相似計算來判別。詞對的語義相似性是一個主觀性比較強的概念,本文所涉及的語義相似性是指詞對能描述同一個概念的局部特征屬性,因此下面給出本文提出的算法中幾個相關定義。

定義1特征詞。用來描述概念特征屬性的詞。對原子概念可能對應于一個特征詞或一組同義的特征詞，而對于復雜的概念則需要多個特征詞分別描述其特征屬性。其中特征詞的作用相當于知網中的義原作用。

定義2特征詞對語義相似性。如果存在兩個特征詞可以描述同一概念屬性特征,則認為它們是在語義上相似。

本文算法依賴于具體的語義詞典,不同的語義詞典所采用的相似計算方法也會有所不同,如文獻[5]是基于知網,而文獻[6]是基于詞網。相似程度是一個較為模糊的概念,在一般算法中都定義為0到1之間的實數(shù),但是在本文提供的算法中,最終要轉換為判斷特征詞對的數(shù)量,因此本文定義相似度取值為0或1,同時假定一個詞與自身和空元素的語義相似度分別為1和0。為了敘述方便,表述為：

(1)

采用文獻[12]的方法,計算表1中的3個特征詞對,返回結果見表1。

表1 特征詞相似度

假定給定一個閥值T,如果大于或等于T的詞匯都是語義相似的,則公式(1)對表1中3個詞對的返回值分別為1、1、0。

定義3特征詞集。由兩個或多個能夠描述同一個概念或概念特征屬性的詞匯組成的集合,記為SpecialSet(SS)。

定義4特征詞集的相似性。如果兩個特征詞集中的詞兩兩構成詞對,判別詞對的語義相似性,當兩個特征詞集中語義相似的詞對個數(shù)與兩個集合所包含元素的個數(shù)之比值大于給定的閥值時,即認為兩個特征詞匯集在語義上是相似的。公式表述如下:

(2)

其中‖S‖表示集合S所含元素的個數(shù);F(SSi,SSj)判別兩個集合的相似性函數(shù),閥值T是可調節(jié)參數(shù),一般由統(tǒng)計經驗值給出。如果分別用這兩個特征詞匯集各自描述一個原子概念或概念的某個特征,則可以認為這兩個原子概念是等同的或是多個概念具有某個共同特征。

因為兩個特征詞匯集的元素個數(shù)可能各不相同,為了便于計算,參照文獻[5]先對兩個集合的元素構建好一一對應關系。兩個特征詞匯集相似度計算步驟如下:1) 計算兩個集合的所有元素兩兩之間的相似度;2) 從所有的相似度值中選擇最大的一個,將這個相似度值對應的兩個元素對應起來,如果該值大于給定閥值,則計數(shù)一次;3) 分別從兩個集合中刪去那些已經建立對應關系的元素;4) 重復步驟2)和3),直到所有的元素都一一對應;5) 沒有建立起對應關系的元素與空元素對應,不予計算；6) 利用公式(2)中分子項計算對應好的詞匯對并予以統(tǒng)計個數(shù),計算出兩個集合的相似性。

1.2 萬維網服務語義標注

本文主要是對萬維網服務的功能特征屬性采用特征詞集來描述，對原子概念(原子類型)采用一個特征詞匯集來描述;對于復雜概念(即復合類型)則首先對其進行分解成各個原子概念(原子類型),然后再逐一標注。在WSDL文件中,增加如下標簽。標簽① 。它的作用為:算法會根據(jù)給定的分類項,把服務歸類到相應的分類樹中,便于快速檢索;在進行相似性判斷時則根據(jù)language選項采用相應語言的語義詞匯本體庫,如英文可以采用詞網,中文可以采用中國知網;該標簽在一個WSDL文件中,只出現(xiàn)1次,一般放在文件頭部。標簽② 特征詞匯集。它的作用為:該標簽采用特征詞匯集來標注一個原子概念(原子類型)或是某個復雜概念(復雜類型)的原子屬性,多個特征詞之間用冒號隔開。在標注時,根據(jù)屬性特征相似性決定概念相似性原則,只標注復合型對象的基本元素。

例如有一個簡單的萬維網服務,它的功能是輸入城市郵政編號,返回對應城市名。下面代碼對于一個簡單概念進行語義標注的一個WSDL文件語義標注節(jié)選片段。

名稱:地名:城市

如下面代碼對于一個復雜概念進行語義標注的一個WSDL文件語義標注節(jié)選片段。

##

2 萬維網服務的匹配算法

2.1 萬維網服務匹配模型

匹配過程中如何判別兩個概念(或屬性)是否相等,一般通過語義計算服務描述信息。輸入/輸出參數(shù)通常采用本體中的概念(類)來標注,而前置約束和后置效應通常表示為邏輯公式,要滿足服務所屬的行業(yè)或面向的應用領域的規(guī)則(公理),但是通常情況下只判斷邏輯表達式真與假。不同的服務描述方式會有不同服務匹配算法,但從功能角度上來看本質上相同。參照文獻[7-8]的匹配標準,重新給出了以輸入/輸出參數(shù)這些功能屬性為參考目標的服務匹配的幾種標準,表示如下。

定義5精確匹配(exact)。

事業(yè)單位對于所有的活動都必須有預算機制，在活動執(zhí)行過程中，財務部門要對財務人員和固定資產進行全面的管理，財務人員應當具備預測資產使用情況的能力，在實際的操作過程中，預測的資產使用會隨著真實情況的不斷變化而發(fā)生變化，也就是說，工作人員要加強對于所有事件的觀察，防止因為管理上的疏忽而導致資產費用盲目的使用。為加強管理，事業(yè)單位可以增加一項機制：將財務人員對于事件的反應能力而做出的預算結果登記在冊，進行月末劃分等級，以此來鞭策財務人員。

請求服務的輸入?yún)?shù)完全符合通告服務的輸入請求,通告服務的輸出參數(shù)完全符合請求服務的輸出請求或通告服務的輸出參數(shù)包含請求服務的輸出參數(shù)。簡記為

定義6嵌入匹配(plug in)。

請求服務的輸入?yún)?shù)被包含于通告服務的輸入?yún)?shù),而通告服務的輸出參數(shù)完全符合請求服務的輸出請求或通告服務的輸出參數(shù)包含請求服務的輸出參數(shù)。簡記為

定義7包含匹配(subsume)。

請求服務的輸入?yún)?shù)包含于通告服務的輸入?yún)?shù),而通告服務的輸出參數(shù)完全符合請求服務的輸出請求或通告服務的輸出參數(shù)包含請求服務的輸出參數(shù)。簡記為

。

本章給出的匹配模型在(Oreq?Oadv)這個條件下,匹配結果都具有方向性,通告服務可作為請求服務的精確匹配,反之不成立。定義的3種匹配標準,從滿足請求用戶需求的角度來分析,精確匹配最強,包含匹配次之,最后是嵌入匹配。簡記為exact>subsume>plugin。

2.2 萬維網服務匹配方法

根據(jù)1.2節(jié)給出的輸入/輸出參數(shù)概念的語義標注方法和2.1節(jié)提出的萬維網服務匹配模型,本節(jié)首先給出判別兩個服務的輸入/輸出參數(shù)的語義相似性計算公式。

1) 判別服務輸入?yún)?shù)相似度公式如下:

(3)

因為每個參數(shù)都會對應于一個特征詞集,所以參照文獻[5]計算集合元素相似性的方式進行計算,步驟如下。前5步參照特征詞匯相似計算，步驟6):利用公式(3)中分子項計算對應好的參數(shù)對并予以統(tǒng)計個數(shù),并計算出兩個服務參數(shù)對相似個數(shù),并分別與兩個服務參數(shù)個數(shù)進行比較,比值為1,表明兩個服務的輸入?yún)?shù)一一對應;比值≤1,表明判別之后參數(shù)對個數(shù)少于給定的個數(shù),屬于包含或被包含關系;對于復合類型的參數(shù),本文算法只標注到它的原子類型,因此計算過程,對復合類型先展開成原子類型參數(shù),再做比較。

同理公式(3),下面分別給出判別兩個萬維網服務輸出參數(shù)之間的關系以及輸入與輸出之間的關系。

2) 判別服務輸出參數(shù)之間相似度公式如下:

(4)

3) 判斷兩個服務輸入與輸出之間的相似度公式，參照公式(4)對Iadv,Oreq計算。

3 實驗與結果

本文通過開發(fā)工具eclipse3.2、JDK1.6以及axis2.0,搭建了一個萬維網服務開發(fā)測試環(huán)境。實驗1:通過對本文算法與傳統(tǒng)基于關鍵詞算法在查詢精確方面的比較,說明該方法是否具備可行性。分別提交了多組查詢請求,每組請求的萬維網服務數(shù)量有所不同,分別計算每組的平均精確度,結果見圖1。從圖1中看出,本文算法的精確度明顯優(yōu)于傳統(tǒng)基于關鍵詞的查詢算法。雖然測試的樣本空間比較小,但是從中可以看出本文提出的方法具有一定的可行性,并且該方法在實際中簡化了語義標注的復雜度,易于被普通用戶所使用。

圖1 算法與傳統(tǒng)基于關鍵詞算法性能比較Fig.1 The performances of the algorithm and the traditional algorithm

實驗2:由于詞網的應用較早,并且現(xiàn)有基于該語義詞匯庫的研究成果較多，為此對本文算法和基于詞網的一些服務語義標注算法[9-10]進行了對比實驗。實驗中的詞匯相似性算法采用與對比文獻的相同算法。在不同規(guī)模注冊服務數(shù)量下,同樣提交了多組查詢請求,每組請求查詢的服務數(shù)量各不同,分別統(tǒng)計各算法的平均查詢精確度,結果見圖3。文獻[9-10]的方法都是采用單個單詞進行標注,準確度上要比本章提出的方法低,見圖3。在最后兩組實驗中服務查詢提交的請求文檔中,有些概念只用少量的特征詞來標注,此時它的精確度將會降低,這是該算法的一個不足之處。本章算法要分別計算特征詞匯對的語義相似,進而來判斷概念的相似性,因此算法花費的時間要比同類文獻的算法多,結果見圖3。

圖2 算法與文獻基于WordNet的算法精確度Fig.2 The accuracies of the three algorithms

圖3 算法與文獻算法查詢時間耗費Fig.3 The query times of the three algorithms

4 結 語

本算法利用已經構建好的語義詞典,以特征詞集的相似性來近似描述概念之間的相似性。該算法符合人們描述事物的客觀事實,容易被普通用戶所掌握。實驗結果也說明了算法具有一定有效性。

[1] Berners-Lee T,Hendler J,Lassila O.The Semantic Web[J].Scientific America,2001,284(5):34-43

[2] McIlraith S,Son T C,Zeng H.Semantic Web Services[J].IEEE Intelligent Systems & their Application,2001,16(2):46-53

[3] 楊梅.“化”綴詞的語法和語義研究[J].金陵科技學院學報:社會科學版,2006,20(1):71-75

[4] Tversky A.Features of Similarity [J].Psychological Review,1977,84(4):327-252

[5] Liu Q,Li S J.Word Similarity Computing Based on Hownet[J].Computational Linguistics and Chinese Language Processing,2002(7):59-76

[6] Jutla D N,Veerasekaran D,Ding R.Trade-Offs in a Google Distance and a WordNet Hybrid for QoS-Enabled Web Services Composition[C].2012 IEEE Ninth International Conference on Services Computing (SCC),2012:312-319

[7] Paolucci M,Kawamura T,et al.Semantic Matching of Web Services Capabilities[C].Proceedings of the First International Semantic Web Conference on the Semantic Web,Sardinia,Italy,2002:333-347

[8] Lecue F,Leger A.Semantic Web Service Composition Based on a Closed World Assumption[C].ECOWS06,2006:233-242

[9] Kaijun Ren,Nong Xiao,Jinjun Chen.Building Quick Service Query List Using WordNet and Multiple Heterogeneous Ontologies toward More Realistic Service Composition[J].IEEE Transactions on Services Computing,2011,4(3):216-229

[10] Maher M,Hamza H S,Mohamed R M.Service Composition Recovery Using Formal Concept Analyst& Wordnet Similarity[C].IRI 2011,2011:123-138