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

（西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710121）

一種有效的W eb服務(wù)聚類方法

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

（西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710121）

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

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

語義Web；Web服務(wù)；本體學(xué)習(xí)；Web服務(wù)發(fā)現(xiàn)

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

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

1　相關(guān)研究工作

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

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

2　方法描述

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

圖1　聚類方法架構(gòu)圖

2.1特征提取

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

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

2.2相似度計(jì)算

2.2.1本體學(xué)習(xí)

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

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

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

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

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

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

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

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

定義2.2（對(duì)象屬性關(guān)系）:若?（Ci∈PROP（Cj））∩（Cj∈PROP（Ci）），則概念Ci與概念 Cj存在對(duì)象屬性關(guān)系。

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

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

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

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

2.2.2基于術(shù)語相似度的信息抽取

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

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

其中，WebPMI作為SEB的計(jì)算方法。

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

2.2.3相似度計(jì)算

文中采用過濾器計(jì)算服務(wù)相似度。

精確匹配：若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在異構(gòu)的本體中，則SiF與SjF失敗匹配。

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

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

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

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

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

2.3特征整合與聚類

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

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

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

1）設(shè)定目標(biāo)簇類數(shù)n；

2）每一個(gè)服務(wù)樣本作為一個(gè)簇類；

3）計(jì)算鄰接矩陣；

4）repeat

5）找到分屬兩個(gè)不同類簇，且距離最近的服務(wù)樣本對(duì)，將其合并；

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

7）計(jì)算各個(gè)簇類中所有服務(wù)的中心值；

8）選擇各個(gè)簇類中最大值的服務(wù)作為簇類中心；

9）until CN=n。

3　實(shí)驗(yàn)結(jié)果與分析

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

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

3.1本體樣本

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

圖2　本體樣本

圖3為圖2中本體相關(guān)的部分OWL文件。

圖3　圖2本體相關(guān)owl文件

3.2結(jié)果分析

為了評(píng)估聚類的效果，本實(shí)驗(yàn)從5個(gè)領(lǐng)域中獲取了350個(gè)WSDL文檔，對(duì)比了包含復(fù)雜數(shù)據(jù)類型的本體和信息檢索方法HTS（C）與未包含復(fù)雜數(shù)據(jù)類型的HTS方法，根據(jù)文獻(xiàn)［13-15］采用準(zhǔn)確率（P）、召回率（R）和F-Measure作為評(píng)測(cè)指標(biāo)。

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

F-measure是對(duì)上述兩種指標(biāo)的平均。

圖4　HTS與HTS（C）對(duì)比圖

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

4　結(jié)束語

文中在Web服務(wù)中考慮了復(fù)雜數(shù)據(jù)類型，介紹了若干個(gè)能夠應(yīng)用于本體學(xué)習(xí)的規(guī)則，獲得了更多的數(shù)據(jù)屬性和對(duì)象屬性，豐富擴(kuò)展了本體，最終提高Web服務(wù)聚類的性能。下一步工作是考慮通過引入本體映射提高相似度的計(jì)算，以及通過服務(wù)聚類提高服務(wù)發(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中組合服務(wù)自動(dòng)部署的研究和實(shí)現(xiàn)［J］.西安郵電學(xué)院學(xué)報(bào)，2010（5）:107-110.

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

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

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

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

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

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

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

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

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

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

［15］嚴(yán)桂奪.基于主題聚類的網(wǎng)頁目錄結(jié)構(gòu)構(gòu)建方法研究［D］.廣州：華南理工大學(xué)，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稿件編號(hào)：201601282

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

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