一種有效的W eb服務聚類方法

馬傳賓，翟社平，馬蒙雨，郭 琳

（西安郵電大學 計算機學院，陜西 西安710121）

一種有效的W eb服務聚類方法

馬傳賓，翟社平，馬蒙雨，郭 琳

（西安郵電大學 計算機學院，陜西 西安710121）

將功能相似的Web服務聚類是一種有效的服務發(fā)現(xiàn)方法，而聚類的關鍵在于服務之間語義相似度的計算。目前國內(nèi)外主流使用

、信息檢索和基于本體的方法計算相似度，這些方法存在語義信息缺失等問題，并且聚類方法只考慮到簡單數(shù)據(jù)類型的處理。本文提出一種同時包含處理簡單數(shù)據(jù)類型和復雜數(shù)據(jù)類型的本體學習方法，利用本體學習和信息檢索相結合的方式（Hybrid term similarity，HTS）進行Web服務聚類。實驗結果表明，該方法能夠有效地提高Web服務的聚類效果。

語義Web；Web服務；本體學習；Web服務發(fā)現(xiàn)

隨著Internet中Web服務數(shù)量的增加，服務的自動發(fā)現(xiàn)面臨著很大的挑戰(zhàn)。Web服務聚類能夠根據(jù)輸入、輸出、前提和效果即IOPEs（inputs，outputs，pre-conditions and effects），將功能相似的服務進行聚類，從而能夠有效地進行服務發(fā)現(xiàn)。采用相似度計算方法來計算服務特征的相似度SoFs（Similarity of features），服務特征相似度的總和，即為服務相似度。目前聚類算法使用了一些相似度計算方法，例如基于關鍵字的方法、信息檢索和基于本體的方法等，然而由于服務資源的異質性和獨立性，基于關鍵字的方法并不能準確地計算出術語的語義相似度，另外，信息檢索方法主要針對純文本格式內(nèi)容，但Web服務通常包含了較多復雜的結構，基于本體的方法，雖然本體有助于提取語義相似度，但如何定義多個高質量的本體依然存在問題。

為了解決這些問題，本文將簡單數(shù)據(jù)類型和復雜數(shù)據(jù)類型相結合，通過分析二者的語義模式豐富本體學習的內(nèi)容，從而有效地進行Web服務聚類。

1　相關研究工作

Rajendran等［1］提出一種采用動態(tài)代理框架來自動進行Web服務發(fā)現(xiàn)方法。Wen等［2］提出一種采用WordNet和本體來計算服務相似度的方法。Schmidt等［3］提出一種采用P2P方式進行 Web服務發(fā)現(xiàn)的方法。楊楠等［4］提出一種由 SCML（Service Composition Management Language）出發(fā)自動轉化BPEL（Business Process Execution Language）并在引擎中自動部署、發(fā)布、執(zhí)行的方法，并證明該方法對流程自動發(fā)布具有一定的可用性。劉建曉等［5］設計了一種基于關系數(shù)據(jù)庫中自身連接的快速準確實施Web服務聚類的方法.該方法可以提高計算服務間相似度的效率。翟社平等［6］提出了一種基于概念理解的規(guī)劃方法，解決了語用Web服務中私有本體概念之間的協(xié)商和理解問題。陳彥萍［7］提出一種基于調(diào)節(jié)熵和社會認知算法的Web服務組合算法，用于解決Web服務組合最優(yōu)問題。徐小良等［8］利用領域本體將Web服務形式化為領域概念的集合，提出一種基于圖論聚類的服務發(fā)現(xiàn)方法，提高了服務發(fā)現(xiàn)效率。朱志良等［9］提出一種特殊的考慮到編程風格和命名規(guī)范的預處理方法，然后結合SCAN算法，能夠有效的提高Web服務的聚類效果。

在WSDL中，服務特征的描述通常包含復合術語，目前大多數(shù)方法中只對其進行簡單分詞并直接進行句子分析，導致術語只做了簡單的分析處理，影響了服務相似度計算的準確性。復合術語包含的本體關系應該充分被利用，但是所提及的大多數(shù)方法并沒有在Web服務聚類時考慮到復雜數(shù)據(jù)類型。文中提出了一種考慮復合術語和復雜數(shù)據(jù)類型的方式進行語義相似度計算的方法。

2　方法描述

文中使用WSDL文檔進行Web服務聚類。首先，抽取描述服務功能的特征；其次，通過本體學習構建本體；然后，采用基于術語相似度的本體學習和信息檢索的方法計算特征相似度。通過特征整合，計算服務相似度值并通過凝聚層次聚類算法進行Web服務聚類。聚類方法的體系結構，如圖1所示。

圖1　聚類方法架構圖

2.1特征提取

由于Web服務中通常有多個復雜數(shù)據(jù)類型，因此采用式（1）計算復雜數(shù)據(jù)類型的平均相似度。

其中，sx和ry表示服務Si和服務Sj的復雜數(shù)據(jù)類型，m表示服務Si中sx的個數(shù)，n表示服務Sj中ry個數(shù)。

2.2相似度計算

2.2.1本體學習

本體學習目的是精確地識別服務文檔中的語義。本文通過在服務特征中挖掘復合術語隱含的語義來自動構建本體。首先，若該特征為復合術語，則將它切分成簡單術語，如切分AuthorOfNovel成為3個元素（Author，of，Novel）；然后過濾并移除停用詞，得到（Author，Novel）；計算其TF-IDF，TF-IDF值代表了本體概念的重要程度，對其升序排列后，獲取大于預先設定閾值T的術語，通過模式分析方法找出術語的隱含關系。

本體是共享概念模型的明確規(guī)范化說明。本體關系描述了概念之間以及概念屬性之間的相互作用。本文僅考慮兩種類型關系，即概念層次（上下位關系）和3元組關系（主體-謂詞-客體）。C為概念｛C1，C2，…Cn｝的集合，其中Ci代表SiF（服務Si中的特征F）。LSC（Ci）表示概念Ci的下位概念Cx的集合；LGC（Cx）表示Cx的上位概念Ci的集合，PROP（Ci）表示概念Ci的屬性集合。

定義1（上下位關系）：若?Ci∈LSC（Cj）∩LGC（Ci），則概念Ci和Cj存在上下位關系。其中概念Ci可以是簡單術語（如Employee）也可以是復合術語（OrganizationEmployee）。如果一個概念是復合術語，則右半部分術語是概念（Employee）的首部，左半部分術語是概念（Organization）的修飾術語。

規(guī)則1:（首部-修飾關系規(guī)則）：首部和修飾表示詞項的上下位關系［10］。

屬性包括數(shù)據(jù)屬性和對象屬性，其中數(shù)據(jù)屬性指概念中的數(shù)據(jù)，對象屬性指概念間的關系。

定義2（屬性關系）：若?Cj∈PROP（Ci），則Cj和Ci存在屬性關系。該屬性關系可以是對象屬性或者數(shù)據(jù)屬性。

定義2.1（數(shù)據(jù)屬性關系）:若?Pi∈PROP（Cj），則Pi和概念Cj存在數(shù)據(jù)屬性關系。其中Pi是概念Cj中的數(shù)據(jù)。

規(guī)則2：（復合名詞規(guī)則）:若復合術語t中簡單術語均是名詞，則概念Mt和數(shù)據(jù)t存在數(shù)據(jù)屬性關系。

定義2.2（對象屬性關系）:若?（Ci∈PROP（Cj））∩（Cj∈PROP（Ci）），則概念Ci與概念 Cj存在對象屬性關系。

規(guī)則3（概念與修飾規(guī)則）:若概念Ci與概念Cj的修飾術語相同，則概念Ci與Cj存在對象屬性關系。

規(guī)則4（修飾規(guī)則）:若概念Ci的修飾部分與概念Cj的修飾部分相同，且不存在與該修飾術語相同的概念，則Ci與Cj存在對象屬性關系。

規(guī)則5（復雜數(shù)據(jù)類型-簡單數(shù)據(jù)類型規(guī)則）:本體概念Ci表示在WSDL文檔d中的復雜數(shù)據(jù)類型，Cj與Ci為不同的概念，Cj表示在d中簡單類型或者其他復雜數(shù)據(jù)類型，若復雜數(shù)據(jù)類型Ci包含名稱為p，且數(shù)據(jù)類型為Cj的概念，則Ci和Cj存在對象屬性關系（Ci-p-Cj）。

根據(jù)規(guī)則1構建上下位關系，根據(jù)規(guī)則2產(chǎn)生數(shù)據(jù)屬性關系，根據(jù)規(guī)則3和規(guī)則4產(chǎn)生對象屬性關系。若服務的特征為復雜數(shù)據(jù)類型，則規(guī)則5產(chǎn)生更多的對象屬性，從而豐富本體。

2.2.2基于術語相似度的信息抽取

通過信息抽取方法計算相似度，采用式（2）計算簡單術語的相似度，然后采用式（1）計算平均相似度。

其中，其中TBsim（T1，T2）表示基于詞庫的術語相似度值，SE sin（T1，T2）是SEB相似度值，α和β的取值范圍為［0，1］，且α+β=1。

其中，WebPMI作為SEB的計算方法。

其中，H（P）和H（Q）各自代表查詢P和Q的頁數(shù)。H（P∩Q）代表P和Q聯(lián)合查詢。若H（P∩Q）低于閾值c，則該項系數(shù)為0，因為兩個術語可能出現(xiàn)在同一頁。N表示搜索引擎索引的文檔數(shù)。

2.2.3相似度計算

文中采用過濾器計算服務相似度。

精確匹配：若Ci≡Cj，則SiF完全匹配SjF；

屬性-概念匹配:若Ci∈PROP（Cj），則 SiF和SjF屬性-概念匹配；

屬性-屬性匹配:若 Ci∈PROP（Ck）∩Cj∈PROP（Ck），則SiF和SjF屬性-屬性匹配；

嵌入匹配:若Ci∈LSE（Cj），則SiF和 SjF嵌入匹配；

兄弟匹配：若 Ci∈LSC（Ck）∩Cj∈LES（Ck），則 SiF和 SjF兄弟匹配；

包含匹配：若Cj>Ci，則SiF和SjF包含匹配。

邏輯失敗匹配和失敗匹配：若Ci和Cj在相同的本體中，但不能匹配以上6種模式，則SiF與SjF邏輯失敗匹配。若Ci和Cj在異構的本體中，則SiF與SjF失敗匹配。

根據(jù)基于邏輯匹配的程度應用過濾器，精確匹配>屬性-概念匹配>屬性-屬性匹配>嵌入匹配>兄弟匹配>包含匹配>邏輯失敗匹配>失敗匹配。

若兩個概念是精確匹配，則相似值為最大值1，。若是其他匹配（不包含失敗匹配），則采用式（4）計算相似度。

其中Wm和We的取值范圍為［0，1］，具體由匹配的過濾器決定；ESim（Ci，Cj）表示邊緣相似度，采用式（5）計算。

其中d（Ci，Cj）表示概念Ci和Cj最短的距離，D表示本體最大深度。

如果兩個概念位于異構的本體中（即兩種服務為失敗匹配），則采用信息檢索術語相似度的方法來計算特征相似度。

2.3特征整合與聚類

式（6）為通過整合特征計算服務Si和Sj最終的相似度值SSc（Si，Sj），用于進行Web服務聚類。

其中WN，WON，WCT，WOP和WI取值范圍均為［0，1］。

文中采用自下而上的凝聚層次聚類算法［11-12］，算法流程為：

1）設定目標簇類數(shù)n；

2）每一個服務樣本作為一個簇類；

3）計算鄰接矩陣；

4）repeat

5）找到分屬兩個不同類簇，且距離最近的服務樣本對，將其合并；

6）CN=當前簇類數(shù)目；

7）計算各個簇類中所有服務的中心值；

8）選擇各個簇類中最大值的服務作為簇類中心；

9）until CN=n。

3　實驗結果與分析

實驗的系統(tǒng)環(huán)境配置如表1所示。測試數(shù)據(jù)是從Web服務庫中抽取的Educational、Film、Vehicle、Medical和Food 5個領域相關的WSDL文檔。

表1　系統(tǒng)環(huán)境配置

3.1本體樣本

圖2為經(jīng)過本體學習之后得到的本體片段，展示了由復雜數(shù)據(jù)類型得到的對象屬性關系。如概念 University和educational_employee存在對象屬性關系（University-hasvice-chancellor-educational_employee）。

圖2　本體樣本

圖3為圖2中本體相關的部分OWL文件。

圖3　圖2本體相關owl文件

3.2結果分析

為了評估聚類的效果，本實驗從5個領域中獲取了350個WSDL文檔，對比了包含復雜數(shù)據(jù)類型的本體和信息檢索方法HTS（C）與未包含復雜數(shù)據(jù)類型的HTS方法，根據(jù)文獻［13-15］采用準確率（P）、召回率（R）和F-Measure作為評測指標。

其中，NMij表示在簇j中類i的元素個數(shù)。NMj表示簇j中元素的個數(shù)，NMi表示類i中元素個數(shù)。

F-measure是對上述兩種指標的平均。

圖4　HTS與HTS（C）對比圖

從圖4（a）、圖4（b）、圖4（c）可以看出，在考慮復雜數(shù)據(jù)類型之后采用HTS方法，即HTS（C），比未考慮復雜數(shù)據(jù)類型的HTS方法有更高的準確率、召回率、F-measure，意味著屬于這些組的Web服務更多地、更準確地放到對應的簇中。

4　結束語

文中在Web服務中考慮了復雜數(shù)據(jù)類型，介紹了若干個能夠應用于本體學習的規(guī)則，獲得了更多的數(shù)據(jù)屬性和對象屬性，豐富擴展了本體，最終提高Web服務聚類的性能。下一步工作是考慮通過引入本體映射提高相似度的計算，以及通過服務聚類提高服務發(fā)現(xiàn)的性能。

［1］Rajendran T，Balasubramanie P.An optimal agent-based architecture for dynamic Web service discovery with QoS［C］//International Conference on Computing Communication& Network Technologies，2010:1-7.

［2］Wen T，Sheng G，Li Y，et al.“Research on Web service discoverywith semanticsand clustering，”in proc［C］.6th IEEE Joint International Information Technology andArtificial IntelligenceConference，China，August，2011：62-67.

［3］Schmidt C，Parashar M.A Peer-to-Peer approach to web servicediscoveryworldwideweb-internet&Web information systems［J］.2004，7（2）:211-229.

［4］楊楠，馬力，陳彥萍.ActiveBPEL中組合服務自動部署的研究和實現(xiàn)［J］.西安郵電學院學報，2010（5）:107-110.

［5］劉建曉，王健，張秀偉等.一種基于RDB中自身連接的Web服務聚類方法［J］.計算機研究與發(fā)展，2013，50：205-210.

［6］翟社平，魏娟麗，李增智.一種服務本體規(guī)劃理解的語用Web服務發(fā)現(xiàn)算法［J］.解放軍理工大學學報，2008，9（5）：440-444.

［7］陳彥萍，田改玲，張建科.基于調(diào)節(jié)熵函數(shù)的Web服務組合算法［J］.西安郵電大學學報，2013，4:64-70.

［8］徐小良，陳金奎，吳優(yōu).基于聚類優(yōu)化的Web服務發(fā)現(xiàn)方法［J］.計算機工程，2011（9）:68-70.

［9］朱志良，苑海濤，宋杰，等.Web服務聚類方法的研究和改進［J］.小型微型計算機系統(tǒng)，2012，33（1）:96-101.

［10］王盛，樊興華，陳現(xiàn)麟.利用上下位關系的中文短文本分類［J］.計算機應用，2010（3）:603-606，611.

［11］郭景峰，趙玉艷，邊偉峰，等.基于改進的凝聚性和分離性的層次聚類算法［J］.計算機研究與發(fā)展，2008，S1:202-206.

［12］Christopher D，Manning，Prabhakar Raghavan，Hinrich Schutze，Introduction to Information Retrieval［M］.Cambridge University Press，2008.

［13］夏紅科，鄭雪峰，胡祥.多策略概念相似度計算方法LMS［J］.計算機工程與應用，2010，46（20）:32-39.

［14］楊文忠.基于近似網(wǎng)頁聚類算法的Web文本數(shù)據(jù)挖掘技術的研究與應用［D］.長沙：湖南大學，2005.

［15］嚴桂奪.基于主題聚類的網(wǎng)頁目錄結構構建方法研究［D］.廣州：華南理工大學，2010.

An effective clustering approach for W eb services

MA Chuan-bin，ZHAIShe-ping，MA Meng-yu，GUO Lin
（School of Computer Science and Technology，Xi'an University of Posts and Telecommunications，Xi'an 710121，China）

EstablishingWeb services into function similarity cluster is an efficientmethod of service discovery.The key of the clustering is the calculation of the semantic similarity between Web services.Mainstream use keywords，information retrieval or ontology-basedmethod to compute the similarity in home and abroad.Furthermore，Thesemethods exist such problems as lack of semantic information.Further，current clusteringmethods only take into account the processing of simple data type. The approach is proposed to calculate the service similarity not only contains simple data types but contains complex data types.Thus，use ontology learning and information retrievalmethod toWeb service clustering.This approach used in project willsignificantly improveWeb services discovery.

semantic Web；Web service；ontology learning；Web service discovery

TP391

A

1674-6236（2016）19-0011-04

2016-01-29稿件編號：201601282

陜西省教育廳科研項目（12JK0733）；陜西省自然基金項目（2012JM8044）；西安郵電大學研究生創(chuàng)新基金項目（114-602080049）

馬傳賓（1989—）,男，山東菏澤人，碩士研究生。研究方向：語義Web。