基于本體的Web服務(wù)分類的實現(xiàn)

陸雄斌，郭朝珍

(福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建福州350108)

Web服務(wù)(Web Service)是基于XML和HTTPS的一種服務(wù)，其通信協(xié)議主要基于SOAP，服務(wù)的描述通過WSDL，通過UDDI來發(fā)現(xiàn)和獲得服務(wù)的元數(shù)據(jù)．傳統(tǒng)的SOA有其局限性［1］，單靠WSDL描述其服務(wù)信息，不能存儲語義級別的服務(wù)信息，極大地限制了服務(wù)發(fā)現(xiàn)的效率．由于WSDL只對Web服務(wù)的技術(shù)和語法進行描述，因此在服務(wù)檢索的時候，只能通過關(guān)鍵詞進行查找．

本文從WSDL出發(fā)，介紹網(wǎng)絡(luò)本體語言O(shè)WL的特點，利用OWL的結(jié)構(gòu)存儲服務(wù)信息．再根據(jù)目前對服務(wù)檢索效率的要求，提出了服務(wù)分類的想法，對眾多不同的服務(wù)在一定規(guī)則下進行分類，使具有相同功能的服務(wù)被歸為一類，把不同的服務(wù)用本體區(qū)分開．

1 Web服務(wù)分類算法的設(shè)計

1．1 本體概念

本體(Ontology)的概念最初起源于哲學(xué)領(lǐng)域，經(jīng)過多年的演進，人們對“本體”這一概念的重新理解和定位，本體的理論與方法早已被信息領(lǐng)域采用，用于知識的組織、表示、共享和重用．

OWL(Web Ontology Language)是W3C開發(fā)的一種網(wǎng)絡(luò)本體語言，用于對本體進行語義描述．它擁有比RDF和RDF Schema更強的表達能力，是基于XML擴展的語言．

本體語言是用于對領(lǐng)域知識的顯示的形式化描述，具有良定義語法［2］:高效率的推理支持、形式語義、充分的表達能力和表達的方便性．

OWL本體的結(jié)構(gòu)如下:

1)OWL頭部:OWL文檔通常稱為OWL本體或RDF文檔．一個OWL本體的根元素是一個rdf:RDF元素，用來指定一系列命名空間．

一個OWL本體開始于一個owl:Ontology元素中，包括了注釋、版本及其他本體的導(dǎo)入等．

2)OWL類元素:OWL類的定義使用了owl:Class元素，它是rdfs:Class的子類．

3)OWL屬性元素:(1)對象屬性，將對象相互關(guān)聯(lián)．(2)數(shù)據(jù)類型屬性，將對象與數(shù)據(jù)類型值相關(guān)聯(lián)．

因此，引入本體論的思想，并采用OWL DL這種基于XML的信息呈現(xiàn)方式，能更好地表現(xiàn)領(lǐng)域知識，作為推理的事實基礎(chǔ)．并且采用基于XML的方式表達知識，可以方便知識的共享［3］．

1．2 分類思想

算法的基本思想，就是在本體中構(gòu)建一個根節(jié)點類，在根節(jié)點之下建立m個分類節(jié)點(m根據(jù)具體分類數(shù)而定)，每一個分類節(jié)點下有若干個服務(wù)，這些服務(wù)之間具有較高的相似度，它們被歸為一類．

現(xiàn)在，我們所擁有的，即是已經(jīng)發(fā)布到服務(wù)器上的眾多Web服務(wù)的服務(wù)URL，即WSDL文檔所在的地址．要對Web服務(wù)進行分類，首先就必須提取服務(wù)的特征．

服務(wù)的特征有:服務(wù)名(Service Name)，輸入列表(Input List)，輸出類型(Output Type)，以及服務(wù)描述(Service Description)等．這些特征在WSDL中都有相應(yīng)的描述，因此首先要對服務(wù)的WSDL進行解析，提取服務(wù)特征，分類系統(tǒng)將利用OWLSAPI進行這一處理．

1．3 方法的選取

常見的分類方法有:決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡(luò)、k-近鄰、支持向量機、基于關(guān)聯(lián)規(guī)則的分類和集成學(xué)習(xí)等，這些方法都是建立在有訓(xùn)練集的前提下，而Web服務(wù)分類研究的是在沒有訓(xùn)練集的前提下，根據(jù)一定的規(guī)則將相似的服務(wù)聚合以達到分類的效果．這種無指導(dǎo)的學(xué)習(xí)方法稱為聚類方法，常見的聚類方法有:K-means算法、PAM算法(也稱k-中心點算法)、層次聚類算法、AGNES算法、密度聚類方法和DBSCAN算法等．

由于分類思想是Web服務(wù)迭代比較相似度來聚合相似的服務(wù)，因此適合用劃分聚類法．其中最典型的是K-均值算法(K-means)和K-中心點(K-modoid)方法．

由于K-中心點方法在迭代前需給定簇的個數(shù)K，而Web服務(wù)在分類前不知道具體的分類數(shù)，而是在迭代比較中產(chǎn)生新的分類或加入已有的分類，因此引入了聚合度閾值，根據(jù)聚合度同閾值的比較決定是否產(chǎn)生新的分類．

1．4 相似度計算方法

本文計算字符串相似度是基于編輯距離的，在編輯距離的基礎(chǔ)上加以改進之后，再計算字符串相似度的．

編輯距離［4］，又稱Levenshtein距離(也叫做Edit Distance)，是指2個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)．許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符．

例如將kitten一字轉(zhuǎn)成sitting:

(1)sitten(k→s)，

(2)sittin(e→i)，

(3)sitting(→g)，

則字符串“kitten”和“sitting”的編輯距離為3．

設(shè)2個字符串分別為 S1和 S2，編輯距離為d(S1，S2)，字符串長度分別為L1和L2，則字符串S1和字符串S2的相似度:

根據(jù)式(1)字符串“kitten”和“sitting”的相似度Sim 等于 0．571．

一個 Web服務(wù)的特征為:服務(wù)名稱(Service Name)，輸入列表(Input List)，輸出類型(Output Type)和服務(wù)描述(Service Description)，設(shè)對應(yīng)的相似度為 Simn，Simi，Simo和 Simd．則服務(wù) WSi和 WSj的聚合度其中，α、β、γ和θ分別表示服務(wù)名稱相似度、輸入列表相似度、輸出類型相似度和服務(wù)描述相似度的權(quán)重(本文默認 α =0．3，β =0．6，γ =0．1，θ=0．1，α +β + γ =1．0，θ是輔助權(quán)重)．

該方案對于計算服務(wù)之間的相似度是有效的，因為編輯距離是基于計算2個字符串的差異值，而相似度計算與差異值有關(guān)，差異值越小相似度越大．相似度的公式實際上表示2個字符串間匹配字符所占的平均比例，這用來描述2個字符串的相似度是合適的．因此，利用這種計算相似度的方法可計算服務(wù)的相似度．又由于服務(wù)是由服務(wù)名稱、輸入列表、輸出類型和服務(wù)描述等組成，就需要對各組成部分進行加權(quán)計算．

1．5 服務(wù)名稱相似度計算

服務(wù)名稱是Web服務(wù)的一大特征，具有相似功能的Web服務(wù)通常服務(wù)名稱相似，由于服務(wù)名稱屬于字符串，因此服務(wù)名稱相似度的計算直接調(diào)用式(1)．

設(shè)服務(wù)WSi和WSj的服務(wù)名稱分別為Ni和Nj，則服務(wù)名稱相似度:

1．6 輸入列表相似度計算

輸入列表包含一組輸入?yún)?shù)(也可以不包含)，輸入?yún)?shù)由輸入?yún)?shù)類型和輸入?yún)?shù)名稱組成，設(shè)輸入?yún)?shù)類型名為T，輸入?yún)?shù)名稱為M，則二元組(T，M)構(gòu)成一個參數(shù)．設(shè)服務(wù)WSi和WSj的輸入列表分別為INi和INj．

INi={(T1i，M1i)，(T2i，M2i)，…，(Tpi，Mpi)}，INj={(T1j，M1j)，(T2j，M2j)，…，(Tqj，Mqj)}，其中p和q分別代表WSi和WSj輸入?yún)?shù)的個數(shù)．將INi和INj進行笛卡爾積，得到配對集:

D(INi，INj)={〈(T1i，M1i)，(T1j，M1j)〉，〈(T1i，M1i)，(T2j，M2j)〉，…，〈(Tpi，Mpi)，(Tqj，Mqj)〉}．

對于配對集的每一個元素，按類型名(T)與類型名(T)計算相似度，參數(shù)名稱(M)與參數(shù)名稱(M)計算相似度，然后加權(quán)求和得出元素的相似度，最后將配對集中所有元素的相似度累加，得出2個輸入列表的累加相似度:

其中，υ和ν分別表示輸入?yún)?shù)的類型和名稱的權(quán)重(本文默認 υ =0．35，ν =0．65，υ + ν=1．0);F(Mki，Mlj)的計算參見式(1);G(Tki，Tlj)為類型名相似度計算公式，由于類型名比較特殊，例如float和double這2個類型名，按式(1)計算得到相似度為0，但從常識來看，單精度浮點型和雙精度浮點型在參數(shù)中沒有太大的區(qū)別，因此必須為給定的類型名對預(yù)設(shè)一個相似度，也就是經(jīng)驗值．本文設(shè)置的類型名預(yù)設(shè)值表見表1．

表1 類型名預(yù)設(shè)值表Table 1 Table of preset value of type name

因此，G(Ti，Tj)結(jié)合表1和式(1)得出:

Web服務(wù)輸入列表的相似度等于它們輸入列表的累加相似度與自身輸入列表累加相似度最大值之比:

1．7 輸出類型相似度計算

Web服務(wù)都有輸出類型(當(dāng)無返回值時，輸出類型名為null)，計算輸出類型相似度只要應(yīng)用式(5)即可．設(shè)服務(wù)WSi和WSj的輸出類型名分別為Oi和Oj，則輸出類型相似度為

1．8 服務(wù)描述相似度計算

服務(wù)描述是描述服務(wù)功能和服務(wù)信息的一串字符串，不像服務(wù)名稱、輸入列表和輸出參數(shù)是必須事先定義好，服務(wù)發(fā)布者根據(jù)需要定義服務(wù)描述或不添加服務(wù)描述．因此，計算服務(wù)聚合度時，僅將服務(wù)描述相似度作為輔助值來計算．本文對服務(wù)描述相似度的計算只用了簡單的字符串相似度公式，設(shè)服務(wù)WSi和WSj的服務(wù)描述分別為Di和Dj，則服務(wù)描述相似度為

2 實驗結(jié)果及分析

Web服務(wù)分類系統(tǒng)和Web服務(wù)調(diào)用客戶端運行的計算機配置如下:

·操作系統(tǒng):Windows XP(SP3);

· CPU:AMD Athlon(tm)64 X2 Dual 2．41 GHz;

·內(nèi)存:1 GB．

系統(tǒng)包含2組測試任務(wù):一組固定10個分類數(shù)，服務(wù)數(shù)分別是 10、20、30、50、100;另一組固定 60個服務(wù)數(shù)，分類數(shù)分別是 6、7、8、9、10．每組測試 6次，然后取平均值．

測試結(jié)果采用執(zhí)行時間、平均簇內(nèi)聚合度、平均簇間聚合度作為本系統(tǒng)的性能指標，執(zhí)行時間指系統(tǒng)的分類時間，即完成分類所需的毫秒數(shù)，平均簇內(nèi)聚合度和平均簇間聚合度指分類的質(zhì)量．

2．1 實驗效果

本文測試使用的數(shù)據(jù)以手工發(fā)布的100個服務(wù)為基礎(chǔ)，分為固定分類組和固定服務(wù)組，由此分析分類數(shù)和服務(wù)數(shù)對于分類時間的決定作用，測試結(jié)果見表2、表3．

表2 固定分類組Table 2 Group of fixed classification

表3 固定服務(wù)組Table 3 Group of fixed service

2．2 結(jié)果統(tǒng)計分析

從表2和表3的結(jié)果，發(fā)現(xiàn)服務(wù)數(shù)n對執(zhí)行時間影響較大，分類數(shù)c影響不大．分類數(shù)固定組的平均簇內(nèi)聚合度和平均簇間聚合度上下波動，而服務(wù)數(shù)固定組的平均簇內(nèi)聚合度隨著分類數(shù)c的增加而上升，平均簇間聚合度有微小的上升趨勢，這說明分類數(shù)越多，相同類別服務(wù)的相似度越高．由于迭代時，每個服務(wù)先與每個分類的中心服務(wù)比較，再與該分類的所有服務(wù)比較，因此Web服務(wù)分類的時間復(fù)雜度為O(n(c+n/c))．

如圖1，當(dāng)服務(wù)數(shù)n增加時，分類時間呈拋物線的趨勢增加．

圖1 時間隨服務(wù)數(shù)變化圖(分類數(shù)=10)Figure 1 Diagram of time-varying caused by the amount of service

如圖2，當(dāng)分類數(shù)變化時，分類時間呈雙曲線的趨勢變化．

3 結(jié)語

本文研究了Web服務(wù)的分類問題，采用聚類方法中的K-中心點的思想，結(jié)合了聚合度閾值對Web服務(wù)進行迭代聚類．利用本體的結(jié)構(gòu)存儲分類模型，動態(tài)生成分類結(jié)果，即服務(wù)本體文件．服務(wù)請求者讀取本體的分類模型，利用相似度比較的查找規(guī)則檢索服務(wù)，為服務(wù)請求者提供了一個更快更準確發(fā)現(xiàn)服務(wù)的方法．

圖2 時間隨分類數(shù)變化圖(服務(wù)數(shù)=60)Figure 2 Diagram of time-varying caused by the amount of classification

該系統(tǒng)提供了服務(wù)信息的可視化界面，功能區(qū)塊劃分清晰，另外支持用戶自定義系統(tǒng)參數(shù)值，以滿足不同的分類需求．

［1］曹剛，余凡，程慧平．基于語義Web服務(wù)的系統(tǒng)集成研究［J］．現(xiàn)代商貿(mào)工業(yè)，2009(1):357-358．

［2］ANTONIOU Grigoris，HARMELEN Frank van．語義網(wǎng)基礎(chǔ)教程［M］．陳小平，譯．北京．機械工業(yè)出版社，2008．

［3］朱創(chuàng)錄．OWL DL的知識表示與推理研究［J］．甘肅科技，2010(4):42-44．

［4］LEVENSHTEIN V L．Binary codes capable of correcting deletions，insertions and reversals［J］．Doklady Akadem iiNauk SSSR，1966，163(4):707-710．