王宇琛

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

基于標(biāo)簽的Web服務(wù)聚類

王宇琛

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

Web服務(wù)數(shù)量的不斷增加使得服務(wù)發(fā)現(xiàn)逐漸成為研究熱點(diǎn)，同時(shí)，也為Web服務(wù)發(fā)現(xiàn)帶來了巨大的挑戰(zhàn)。傳統(tǒng)的Web服務(wù)發(fā)現(xiàn)或是通過對(duì)UDDI上的服務(wù)注冊(cè)信息進(jìn)行關(guān)鍵詞匹配，或是基于WSDL文檔的Web服務(wù)聚類來實(shí)現(xiàn)的，然而這兩種服務(wù)發(fā)現(xiàn)方法都不能滿足用戶的需求。目前，由于標(biāo)簽?zāi)軌蝮w現(xiàn)信息及信息之間的關(guān)聯(lián)性而在Web服務(wù)上得以廣泛的利用，基于現(xiàn)有的聚類技術(shù)，提出基于標(biāo)簽的Web服務(wù)聚類方法。對(duì)于標(biāo)簽數(shù)較少的服務(wù)，通過推薦算法為其推薦標(biāo)簽并與WSDL文檔中的特征相合進(jìn)行聚類。在實(shí)驗(yàn)中，該算法與現(xiàn)有Web聚類算法進(jìn)行比較并得到更好的結(jié)果，證明該算法的有效性。

Web服務(wù)；標(biāo)簽；Web服務(wù)聚類

0 引言

Web服務(wù)發(fā)現(xiàn)是Web服務(wù)系統(tǒng)架構(gòu)中的重要部分[1～2]。目前Web服務(wù)聚類的研究與應(yīng)用越來越廣泛。最為流行的Web服務(wù)聚類方法是使用WSDL文檔中的特征以及UDDI中的服務(wù)ID或名稱，或是服務(wù)的有限屬性值等[3]，按照指定的聚類方法對(duì)Web服務(wù)進(jìn)行聚類,得到的結(jié)果中除了關(guān)鍵詞匹配的結(jié)果外,還包括與目標(biāo)Web服務(wù)功能相似的其他Web服務(wù)，極大地提高了Web服務(wù)發(fā)現(xiàn)的能力[4]。

然而，目前在Web服務(wù)發(fā)現(xiàn)中，查準(zhǔn)率和查全率并不高，主要可以歸因于：（1）UDDI上注冊(cè)的部分Web服務(wù)已失效；（2）不同的Web服務(wù)，WSDL文檔的組織結(jié)構(gòu)不同，相同信息的表述方式也存在差異；（3）用戶對(duì)所需查詢的目標(biāo)不能準(zhǔn)確描述。

傳統(tǒng)的Web服務(wù)聚類研究注重利用WSDL文檔及UDDI上的注冊(cè)信息，而忽視了Tag的作用。Tag是對(duì)Web服務(wù)內(nèi)容的概括性說明，與Web服務(wù)內(nèi)容的相關(guān)性較強(qiáng)，可用于描述Web服務(wù)的功能。同時(shí)，Tag具有較強(qiáng)的主觀性，用戶可以基于自身評(píng)價(jià)為服務(wù)添加Tag，因此Tag與用戶也有較好的交互性。

本文利用相關(guān)的算法，在Web服務(wù)已有的Tag基礎(chǔ)上進(jìn)行Tag推薦，結(jié)合WSDL文檔中的4個(gè)特征向量，在Web服務(wù)聚類實(shí)驗(yàn)中，本文算法得到了更為準(zhǔn)確的聚類結(jié)果。

1 基于Tag的Web服務(wù)聚類算法

1.1 算法設(shè)計(jì)

輸入Web服務(wù)數(shù)據(jù)后，首先對(duì)Web服務(wù)數(shù)據(jù)進(jìn)行處理，主要是從中提取Tag以及WSDL文檔，分析并存儲(chǔ)WSDL文檔中的Type、Message、Port、Name四個(gè)特征向量。同時(shí)，判斷提取到的Tag數(shù)量是否適當(dāng)，當(dāng)Tag數(shù)量較少時(shí)，為Web服務(wù)推薦Tag。最終將推薦后的Tag集與WSDL文檔向量相結(jié)合，運(yùn)用本文提出的聚類算法對(duì)Web服務(wù)進(jìn)行聚類，輸出聚類結(jié)果。

圖1給出了算法的流程圖。

Web服務(wù)聚類算法框架如下：

輸入部分：Web服務(wù)輸入

處理部分：Tag提取：從Web服務(wù)中提取Tag

WSDL特征提?。簭腤eb服務(wù)中提取WSDL文檔，提取WSDL文檔中的Type、Message、Port、Name四個(gè)特征向量

Tag推薦：用sum算法對(duì)Tag數(shù)量較少的服務(wù)進(jìn)行Tag推薦

輸出部分：將最終Tag集與WSDL文檔中提取的4個(gè)特征向量相結(jié)合，運(yùn)用Tag+WSDL聚類算法對(duì)Web服務(wù)進(jìn)行聚類。

圖1 Web服務(wù)聚類的設(shè)計(jì)方案

1.2 Tag相似度計(jì)算

算法的核心步驟為兩個(gè)Tag的相似度計(jì)算，兩個(gè)Tag之間的相似程度稱為Tag相似度，相似度計(jì)算公式如下：

其中，Sab指兩個(gè)Tag之間的相似度，Tn指Tagn，Wn指所有存在Tn的WSDL文檔的集合。

Sab的取值范圍為[0,1]，當(dāng)Sab越趨向于1時(shí)，這兩個(gè)服務(wù)越相似，當(dāng)Sab越趨向于0時(shí)，這兩個(gè)服務(wù)越不相似，當(dāng)兩個(gè)Tag完全不相同時(shí)，Sab=0，當(dāng)兩個(gè)Tag完全相同時(shí)，Sab=1。

1.3 Tag與WSDL組成的特征向量聚類

本小節(jié)提出了結(jié)合Tag與WSDL特征進(jìn)行聚類的方法。算法如下：

①?gòu)膎個(gè)數(shù)據(jù)中任意選擇k個(gè)作為初始聚類中心。

②計(jì)算余下的n-k個(gè)數(shù)據(jù)與k個(gè)聚類中心的相似度：

其中S1、S2、S3、S4為WSDL文檔中的Type、Message、Port、Name特征向量的值，Stag為Tag的相似度值。

③將這n-k個(gè)數(shù)據(jù)按照與k個(gè)聚類中心的相似度高低進(jìn)行分配。

④分配完畢，重新計(jì)算每個(gè)聚類中每個(gè)點(diǎn)到其他點(diǎn)的相似度之和，取值最小的點(diǎn)作為新的中心點(diǎn)。

⑤重復(fù)②～④步驟，直到選出的中心點(diǎn)不再改變。經(jīng)過以上幾個(gè)步驟，最終得到全部n個(gè)服務(wù)的k個(gè)聚類。

1.4 Tag推薦算法

由于部分Web服務(wù)只有1～2個(gè)Tag，對(duì)這部分Web服務(wù)需要進(jìn)行預(yù)處理，為Web服務(wù)進(jìn)行Tag推薦。在本文中，我們主要采用sum方法進(jìn)行Tag推薦，算法如下：

①對(duì)服務(wù)A中的每一個(gè)Tn，計(jì)算出Tn與訓(xùn)練集中除Tn外的每一個(gè)Tm的相似度Smn。

②為每一個(gè)Tn選擇相似度最高的前五個(gè)Tag，并將其推薦給服務(wù)A，組成n個(gè)Tag推薦集。

③當(dāng)Tm在n個(gè)Tag推薦集中出現(xiàn)k（k＞1）次時(shí)，將這k次的相似度相加，即去重時(shí)疊加相似度，最終Smn= Smn1+Smn2+…+Smnk。

④選擇最終Smn最高的五個(gè)Tag作為服務(wù)A的目標(biāo)Tag。

經(jīng)過以上幾個(gè)步驟，最終得到所需Tag，并將此Tag集推薦給Web服務(wù)。

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

2.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)共分為4個(gè)部分：?jiǎn)渭兊腡ag聚類實(shí)驗(yàn)、單純的WSDL聚類實(shí)驗(yàn)、單純的Tag與WSDL組成的特征向量聚類實(shí)驗(yàn)以及處理后的Tag與WSDL組成的特征向量聚類實(shí)驗(yàn)。實(shí)驗(yàn)中用到近兩萬個(gè)Web服務(wù)信息，并從中提取出380個(gè)有Tag描述的Web服務(wù)信息，主要為以下四類：movie、ce1ebrity、astronomy、tourism。在Tag推薦過程中則用到2000個(gè)帶Tag的Web服務(wù)描述信息，其中1900個(gè)數(shù)據(jù)作為測(cè)試集，剩下的100個(gè)數(shù)據(jù)為目標(biāo)集。

2.2 聚類算法性能評(píng)價(jià)指標(biāo)

我們采用精度（precision）和召回（reca11）來評(píng)估聚類方法的性能。其中精度是對(duì)正確度的測(cè)量，召回則是對(duì)完整性的測(cè)量。

ci指聚類i，Pci為聚類i的精度，succ（ci）和misp1（ci）分別是完全成功地和錯(cuò)誤地聚類到ci中的服務(wù)數(shù)，1ength（ci）是聚類i的數(shù)量，精度計(jì)算方法如下：

Rci為聚類i的召回，missed（ci）則是本該聚類到ci卻被放置到其他聚類中的服務(wù)數(shù)，召回計(jì)算方法如下：

2.3 實(shí)驗(yàn)結(jié)果及分析

表1 各聚類的Precision結(jié)果

表2 各聚類的Recall結(jié)果

從實(shí)驗(yàn)結(jié)果中可以看出，單純的Tag聚類得到了較好的結(jié)果。然而，由于movie和ce1ebrity這兩類的Tag可能會(huì)存在一定的交集，導(dǎo)致包含交集Tag的服務(wù)聚類出現(xiàn)誤差，因此這兩類的Precision和Reca11相對(duì)較低；而astronomy和tourism這兩個(gè)類的Tag基本上沒有任何交集，很容易就能被聚成兩個(gè)類，因此其Precision和Reca11都是100%。

單純WSDL聚類的精度和召回較低，通過對(duì)WSDL文檔進(jìn)行分析可以發(fā)現(xiàn)，相似服務(wù)之間的文檔描述方式上可能存在較大的差別，因此聚類會(huì)有一定的誤差。

Tag+WSDL的聚類效果明顯好于單純的WSDL或Tag的聚類。單純的Tag聚類會(huì)將具有相同Tag的Web服務(wù)聚集在一起，而這些Tag可能適用于不同功能的Web服務(wù)，通過WSDL的特征向量可以修正Tag聚類中出現(xiàn)的部分偏差，因此Tag+WSDL的聚類效果較好。

當(dāng)Tag數(shù)量較少時(shí)，聚類會(huì)出現(xiàn)錯(cuò)誤，因此單純的Tag聚類的效果較差。然而使用本文提出的方法對(duì)Tag進(jìn)行推薦后，再用WSDL特征向量進(jìn)行修正，極大地提升了聚類效果，聚類正確性明顯增加，整體效果要好于單純的Tag+WSDL聚類。

2.4 實(shí)驗(yàn)結(jié)論

對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析可以發(fā)現(xiàn)，Tag和WSDL組成的特征向量聚類效果要明顯好于單純的Tag和單純的WSDL聚類，而在四種聚類中，對(duì)Tag進(jìn)行推薦后再與WSDL組成特征向量聚類效果是最好的。

因此，基于Tag的Web服務(wù)聚類是一種能夠有效地對(duì)Web服務(wù)進(jìn)行聚類的方法。

3 結(jié)語(yǔ)

Web服務(wù)發(fā)現(xiàn)是Web服務(wù)研究中一項(xiàng)重要的研究，目前較多使用單純的WSDL文檔聚類和基于UDDI上的注冊(cè)信息的關(guān)鍵詞匹配兩種方式，這兩種方式都存在一定的缺陷，使得聚類結(jié)果不能較好地滿足用戶的需求。本文從Web服務(wù)的Tag出發(fā)，提出了Tag與WSDL特征向量組合起來加以聚類的方法，同時(shí)為Tag較少的Web服務(wù)進(jìn)行Tag推薦，極大地提高了聚類結(jié)果的準(zhǔn)確性。經(jīng)過以上改進(jìn)，使得Web聚類的準(zhǔn)確性得到顯著提高。在本文中計(jì)算Web相似度時(shí)，用到的是WSDL文檔的四個(gè)特征向量的平均值，WSDL的相似度與Tag相似度也是各取0.5。在下一步的工作中我們應(yīng)當(dāng)通過訓(xùn)練集的方法得到各特征以及WSDL相似度、Tag相似度對(duì)應(yīng)的權(quán)值來取代目前的平均值，以得到更為精確的聚類結(jié)果。

參考文獻(xiàn)：

[1] 岳昆，王曉玲，周傲英.Web服務(wù)核心支撐技術(shù)：研究綜述.軟件學(xué)報(bào)，2004，15（3）:428～442

[2] Pao1ucci M.,Kawamura T.,Payne T.R.,Sycara K..Semantic Matching of Web Services Capabi1ities.In:Proceedings of the 1st Internationa1 Semantic Web Conference（ISWC）,Sar-dinia,Ita1ia,2002：34～43

[3] Wei Liu,Wi1son Wong.Web Service C1ustering Using Text Mining Techniques.Internationa1 Journa1 of Agent-Oriented Software Engineering,2009，3（1）：6～26

[4] Kha1id E1gazzar,Ahmed E.Hassan,Patrick Martin.C1ustering WSDL Documents to Bootstrap the Discovery of Web Services to Appear in the 8th Internationa1 Conference on Web Services（ICWS'10）,Miami,F1orida,USA,Ju1y 2010.

[5] Richi Nayak.Data Mining in Web Services Discovery and Monitoring.Internationa1 Journa1 of Web Services Research，2008，5（1）：63～81

[6] 寧玉輝，楊棟，杜玉越.基于服務(wù)簇的Web服務(wù)綁定方法[J].山東科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2014（04）

[7] 李敏，唐春玲.基于語(yǔ)義的Web服務(wù)發(fā)展現(xiàn)狀[J].科技信息，2014（09）

[8] 魏登萍，王挺，王戟.融合描述文檔結(jié)構(gòu)和參引特征的Web服務(wù)發(fā)現(xiàn)[J].軟件學(xué)報(bào)，2011，22（（9）:2006～2019

Web Services Cluster Based on Tags

WANG Yu-chen
（Co11ege of Computer Science,Sichuan University,Chengdu610065）

With the increasing number of Web service,Web service discovery becomes a hotspot.Current infrastructures of Web services discovery, such as keywords-based matching with UDDI registration information and WSDL-based Web service c1uster becomes inefficient.Now tags are wide1y app1ied in Web service.Proposes Web services c1uster based on tags combing with WSDL document information.For those Web services which have fewer tags,we recommend tags by tag recommend a1gorithm.In the experiment,we compare this method with other Web services c1uster a1gorithms and demonstrate the effectiveness of this method.

Web Service;Tag;Web Service C1uster

1007-1423（2015）05-0020-04

10.3969/j.issn.1007-1423.2015.05.004

王宇?。?992-），女，湖北黃岡人，碩士，研究方向?yàn)樾畔z索

2014-12-25

2015-01-25