一種基于標(biāo)簽的層次Web服務(wù)聚類方法

李蓉+葉俊民+楊艷

摘 要： 提出一種基于Fuzzy c-means聚類方法的模糊服務(wù)聚類方法SGCom，該方法首先標(biāo)注服務(wù)的名稱、功能和使用對(duì)象，再用改進(jìn)的FCM算法對(duì)服務(wù)的名稱聚類，用比較相似度的方法對(duì)服務(wù)的其他元素聚類，并綜合得出聚類結(jié)果。由于該方法基于服務(wù)的注冊(cè)信息，不局限于單一的服務(wù)描述語言，得到的結(jié)果是服務(wù)屬于某個(gè)類別的比率，在服務(wù)發(fā)現(xiàn)時(shí)可以根據(jù)用戶設(shè)定的閾值推薦服務(wù)類別，避免了靠近類簇邊界上的服務(wù)難以被準(zhǔn)確分類的問題。

關(guān)鍵詞： FCM算法； Web服務(wù)； 服務(wù)聚類； 服務(wù)相似度

中圖分類號(hào)：TP3-0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2017）11-30-05

A tag based hierarchical Web service clustering method

Li Rong， Ye Junmin， Yang Yan

（Computer Science Department， Central China Normal University， Wuhan， Hubei 430079， China）

Abstract： In this paper， a Fuzzy c-means based fuzzy service clustering method SGCom is proposed. When using this method， the names， functions， and goals of the Web services are tagged， the improved FCM algorithm is used to cluster the names of services， and similarity of other Web service elements is calculated to cluster them. Comprehensive cluster results can be obtained through these steps. The SGCom method is bases on service registration information and is not limited to a single service description language， so the result obtained is the membership degree of service that belongs to a category， and the category of a service can be recommended according to the threshold set by the user when the service is found， which solves the problem that the services close to the cluster boundaries are difficult to be classified accurately by the hard clustering methods.

Key words： FCM algorithm； Web service； service clustering； service similarity

0 引言

隨著網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)服務(wù)資源的數(shù)量飛速增長。ProgrammableWeb （PWeb）是一個(gè)著名的網(wǎng)絡(luò)服務(wù)發(fā)布網(wǎng)站，在2012年其上發(fā)布的Web服務(wù)有6400多個(gè)[1]，而在2017年初，服務(wù)數(shù)量已經(jīng)達(dá)到15700多個(gè)，不到五年時(shí)間服務(wù)數(shù)量增加超過一倍。大量增長的服務(wù)給使用者提供了更多更好的選擇，但是也對(duì)服務(wù)選擇和推薦造成了更大困難，特別是對(duì)服務(wù)選擇和推薦的速度提出了更高的要求。

服務(wù)聚類是服務(wù)選擇和推薦的一種有效的支持手段[2]，按照一定的規(guī)則對(duì)大量的服務(wù)聚類，服務(wù)選擇時(shí)在相關(guān)的服務(wù)類別中選擇合適的服務(wù)，這樣縮小了服務(wù)查找的范圍，加快了查找速度，提高了查找的正確率?，F(xiàn)在已經(jīng)有很多服務(wù)聚類方法。文獻(xiàn)[3]提出了一種基于網(wǎng)絡(luò)圖的服務(wù)聚類算法SNTClus。文獻(xiàn)[4]提出一種根據(jù)服務(wù)描述的詞語相似度聚類服務(wù)的辦法CAS。文獻(xiàn)[5]提出一種使用加權(quán)的模糊c-means （FCM）方法WFCM聚類服務(wù)的方法。

這些聚類方法都從服務(wù)的特點(diǎn)出發(fā)，應(yīng)用基本的數(shù)據(jù)聚類的方法，并做了一定改進(jìn)，提高了聚類效果，但仍然存在以下問題。

⑴ 多數(shù)服務(wù)聚類的方法只能支持某一種服務(wù)文檔。文獻(xiàn)[6-7]等支持用WSDL描述的服務(wù)聚類，文獻(xiàn)[8-9]等支持用OWL-S描述的服務(wù)聚類，現(xiàn)在有很多RESTful服務(wù)用自然語言描述，對(duì)這類服務(wù)的聚類方法研究的不多。

⑵ 多數(shù)服務(wù)聚類方法服務(wù)聚類后只能屬于某一個(gè)服務(wù)類別，沒有考慮概念的模糊性問題。很多服務(wù)可能屬于多個(gè)類型，比如天氣預(yù)報(bào)服務(wù)，因?yàn)槁糜纬鲂行枰私馓鞖庑畔?，因此該服?wù)可以屬于“出行”類別，同時(shí)因?yàn)樯鐣?huì)生活中人們經(jīng)常關(guān)注天氣情況，該服務(wù)也可以分類在“社會(huì)生活”類別。在PWeb中的很多服務(wù)都有多個(gè)標(biāo)簽，可以把服務(wù)歸為不同的類別。因此只把服務(wù)歸為某種類別的硬聚類的方式有所欠缺。

本文提出了一種基于Fuzzy c-means聚類方法的模糊服務(wù)聚類方法SGCom，該方法首先標(biāo)注服務(wù)的名稱、功能和使用對(duì)象，再用改進(jìn)的FCM算法對(duì)服務(wù)標(biāo)簽聚類。該方法基于服務(wù)的注冊(cè)信息，不局限于單一的服務(wù)描述語言，得到的結(jié)果是服務(wù)屬于某個(gè)類別的比率，在服務(wù)發(fā)現(xiàn)時(shí)可以根據(jù)用戶設(shè)定的閾值推薦服務(wù)類別。

1 數(shù)據(jù)準(zhǔn)備

數(shù)據(jù)準(zhǔn)備的結(jié)果如圖1所示。在進(jìn)行服務(wù)聚類之前首先要獲得服務(wù)的名稱、功能等信息，在PWeb中注冊(cè)的服務(wù)使用短文本標(biāo)注的方式提供服務(wù)的描述信息，也有部分用戶標(biāo)簽信息。endprint

由于服務(wù)標(biāo)注使用自然語言，需要對(duì)其內(nèi)容進(jìn)行一定的約束和處理，本文用自然語言處理工具包NLTK實(shí)現(xiàn)這些功能。NLTK是主流的自然語言處理工具包，能非常方便地在Python中調(diào)用，能方便地使用包括WordNet在內(nèi)的多種詞典。最后得到服務(wù)的定義如下。

⑴

其中，SName表示服務(wù)的名稱，SRole表示服務(wù)針對(duì)的對(duì)象，SGoal表示該服務(wù)的功能目標(biāo)。

⑵

其中GOperation說明完成功能目標(biāo)需要的操作，GObject說明操作的對(duì)象，GManner說明操作的方式。每個(gè)功能性目標(biāo)定義的操作必須要有一個(gè)操作對(duì)象，但可以不定義操作的方式。

2 服務(wù)的相似度計(jì)算方法

本文對(duì)服務(wù)的聚類關(guān)注于對(duì)服務(wù)的名稱SName的聚類和對(duì)服務(wù)的功能性目標(biāo)SGoal的聚類。SName說明服務(wù)的主要功能，用動(dòng)賓短語表示，因此在計(jì)算相似度前需要先分詞，得到單獨(dú)的動(dòng)詞和名詞，見公式⑶，再根據(jù)公式⑷計(jì)算其相似度。

⑶

簡單的用英文表示的名詞和動(dòng)詞的語義相似度可以用WordNet來計(jì)算。WordNet是常用的英語檢索詞典[10]，其中的名詞和動(dòng)詞具有層次關(guān)系，可以方便地計(jì)算詞語間的相似度。本文使用常用的基于WordNet的詞語相似度的計(jì)算方法Resnik算法計(jì)算相似度[11]。

定義1 SName相似度。

SName相似度表示服務(wù)的名稱的相似程度，可表示為：

⑷

其中s1和s2為需要比較的服務(wù)，表示使用Resnik算法計(jì)算的動(dòng)詞之間和的相似度值，ωsp和ωso為用戶定義的權(quán)重，以區(qū)別操作和操作對(duì)象對(duì)服務(wù)相似度的貢獻(xiàn)程度，ωsp和ωso在0到1之間，即ωsp，ωso∈[0，1]。

每個(gè)服務(wù)s有一組功能性目標(biāo)描述的集合SGoal={sg1，sg2，…，sgn}，求取兩個(gè)服務(wù)的相似度需要比較兩個(gè)服務(wù)的所有sgi的相似度，再求其最大值，見公式⑸。

定義2 SGoal相似度。

SGoal相似度表示服務(wù)的目標(biāo)模型中的功能性目標(biāo)屬性的相似程度，可表示為：

⑸

其中n和m分別代表服務(wù)s1和s2中功能性目標(biāo)描述的個(gè)數(shù)，由公式⑹給出。

⑹

公式⑹求出sg中三個(gè)分量的相似度的平均值。

定義3 服務(wù)相似度。

服務(wù)相似度表示兩個(gè)服務(wù)的相似程度，可表示為：

⑺

其中α和β是調(diào)整系數(shù)，調(diào)整SNameSim和SGoalSim在計(jì)算結(jié)果中所占的權(quán)重，α+β=1。

3 聚類中心的計(jì)算方法

在FCM算法中，每次迭代時(shí)都需要調(diào)整k個(gè)類簇的聚類中心，在基本FCM定義中考慮參與聚類的樣本點(diǎn)是數(shù)字，因此采用求取歸入同一類簇的所有樣本點(diǎn)的平均數(shù)來計(jì)算新的聚類中心[12]。但是在本文的應(yīng)用中參與聚類的是詞語，很難求取詞語的平均數(shù)，因此本文考慮求取同一類簇的所有樣本點(diǎn)的到老聚類中心的平均距離，再找到在本類中和老聚類中心的距離接近平均距離的那個(gè)樣本點(diǎn)，即可得到新的聚類中心。

定義4 模糊平均語義距離。

模糊平均語義距離表示在一定范圍內(nèi)，所有其他元素到某一個(gè)元素的平均的模糊語義距離。給定樣本點(diǎn)的集合和隸屬度的集合，給定一個(gè)聚類中心xi，xi∈S，集合中的所有元素到的模糊平均距離可以定義為：

⑻

定義5 模糊元素可替。

模糊元素可替表示一個(gè)樣本點(diǎn)可以被另一個(gè)樣本點(diǎn)替換。給定樣本點(diǎn)的集合和隸屬度的集合，給定一個(gè)樣本點(diǎn)xi，xi∈S，有樣本點(diǎn)xj，xi≠xj，滿足公式⑻，則xi和xj模糊元素可替，記為。

⑼

其中ε為一個(gè)給定的閾值，在0到1之間，可以根據(jù)集合S中服務(wù)的粒度設(shè)定。

由以上定義，傳統(tǒng)FCM算法中聚類中心pi的計(jì)算公式可以變換成：

⑽

公式⑽表示當(dāng)原來的聚類中心p和服務(wù)xj滿足模糊元素可替時(shí)，xj可以作為新的模糊聚類中心。

4 Web服務(wù)聚類方法

本文的層次聚類方法先用FCM算法對(duì)服務(wù)的SName屬性聚類，得到初始的k個(gè)聚類中心和服務(wù)的隸屬度矩陣。因?yàn)镾Goal信息是對(duì)服務(wù)功能的細(xì)化描述，為了提高聚類準(zhǔn)確度，以上面算出的k個(gè)聚類中心為中心，比較服務(wù)的SGoal相似度，重新聚類服務(wù)，然后綜合以上兩種聚類方法的結(jié)果，得到所需服務(wù)聚類中心和隸屬度矩陣。

4.1 計(jì)算聚類中心

算法1 FCM聚類中心計(jì)算算法

FCMCenter（S， U， p， th）

輸入：S={s1，s2，…，sn}，表示所有服務(wù)的集合；

U={u1，u2，…，un}，表示所有服務(wù)對(duì)應(yīng)的隸屬度的集合；

p表示聚類中心；

th表示閾值。

輸出：p表示計(jì)算后的聚類中心。

1. for i=1 to n

2. d=SNameSim（u1*si，p）；

3. fdist=d/（n-1）；

4. for i=1 to n

5. if （SNameSim（u1*si，p）-fdist）6. p=si；

7. return p；

FCMCenter算法計(jì)算服務(wù)集合S的新的聚類中心，新的聚類中心要求變化距離小于th，可以取th為0.01，如果找不到新的使變化距離小于th的服務(wù)，則現(xiàn)在的聚類中心是最優(yōu)的。

4.2 使用FCM算法對(duì)SName聚類

算法2 SName聚類算法endprint

SNAMEC（S， k， n， th）

輸入：S={s1，s2，…，sn}，表示所有服務(wù)的集合；

k表示k個(gè)聚類中心；

n表示服務(wù)的數(shù)量；

th表示用戶定義的閾值；

輸出：U表示服務(wù)隸屬度矩陣；

p={p1，p2，…，pk}，表示最后得到的聚類中心；

1. m=0；

2. 隨機(jī)選取k×n個(gè)在[0，1]之間的數(shù)，初始化隸屬矩陣。

3. Do

4. z=0；

5. for i=1 to k

6. uk=U中的第k列；

7. pi=FCMCenter（S，uk，pi，0.01）；

8. for i=1 to k

9. for j=1 to n

10. for t=1 to n

11. z=；

12. uij=1/z；

13. 更新隸屬度矩陣；

14. m=m+1；

15. Until （<=th）

16. Return ；

17. Return {p1，p2，…，pk}；

算法迭代更新隸屬度矩陣U和聚類中心，直到聚類中心的變化小于th時(shí)停止，th一般設(shè)置成0.01。算法中uij代表隸屬度矩陣U中的每一個(gè)元素，代表第m次迭代得到的k×n的隸屬度矩陣。

4.3 使用相似度計(jì)算的方法對(duì)SGoal聚類

算法3 SGoal聚類算法

SGoalC（S， P， k， n）

輸入：S={s1，s2，…，sn}，表示所有服務(wù)的集合

p={p1，p2，…，pk}，表示SNAMEC算法得到的聚類中心；

k表示k個(gè)聚類中心；

n表示服務(wù)的數(shù)量；

輸出：U表示最后得到的服務(wù)隸屬度矩陣。

1. for i=1 to k

2. for j=1 to n

3. uij=SGoalSim（sj，pi）；

4. 更新隸屬度矩陣U；

5. Return U；

算法以前面得到的聚類中心為基礎(chǔ)，比較每個(gè)服務(wù)和每個(gè)聚類中心的相似度，把結(jié)果寫到新的隸屬度矩陣U中。

4.4 整合聚類結(jié)果

算法4 聚類組合算法

SGCom（U， U'， P， k， n， α， β）

輸入：U表示SNAMEC算法得到的服務(wù)隸屬度矩陣；

U'表示SGoalC算法得到的服務(wù)隸屬度矩陣；

P={p1，p2，…，pk}，表示SNAMEC算法得到的聚類中心；

k表示k個(gè)聚類中心；

n表示服務(wù)的數(shù)量；

α和β分別表示U和U'的權(quán)重；

輸出：UNew表示最后得到的服務(wù)隸屬度矩陣。

1. for i=1 to k

2. for j=1 to n

3. unewij=α*uij+β*u'ij；

4. 更新隸屬度矩陣UNew；

5. Return UNew；

算法綜合SNAMEC和SGoalC算法得到的服務(wù)隸屬度矩陣，得到隸屬度矩陣UNew。U和對(duì)結(jié)果的貢獻(xiàn)由權(quán)重標(biāo)記，具體權(quán)值可以根據(jù)實(shí)驗(yàn)確定。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)準(zhǔn)備

為了檢驗(yàn)本文提出的服務(wù)聚類方法SGCom，我們做了模擬實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境包括Intel Core I5 1.7GHz CPU，4GB內(nèi)存，Windows 7操作系統(tǒng)，MySQL 5.5數(shù)據(jù)庫服務(wù)器，Apache 2.4應(yīng)用服務(wù)器，開發(fā)語言采用Java，使用JDK 6.0 Java虛擬機(jī)。

服務(wù)資源網(wǎng)站PWeb上提供了15000多個(gè)服務(wù)，已經(jīng)有132000多個(gè)注冊(cè)會(huì)員。我們利用網(wǎng)站提供的API，使用爬蟲軟件爬取了大量的服務(wù)，通過數(shù)據(jù)分析，選取服務(wù)數(shù)量最多的前6個(gè)應(yīng)用領(lǐng)域作為測(cè)試的基礎(chǔ)，這6個(gè)服務(wù)類別和它們中的服務(wù)數(shù)量如表1所示。我們從每類服務(wù)中選取功能比較復(fù)雜、描述信息比較詳細(xì)的100個(gè)服務(wù)，人工建立服務(wù)的標(biāo)簽。

5.2 實(shí)驗(yàn)分析

本文先通過人工判斷對(duì)300個(gè)服務(wù)分類，再把通過算法得到的聚類結(jié)果與人工聚類結(jié)果比較。評(píng)價(jià)標(biāo)準(zhǔn)采用常用的熵、F值和聚類純度，這些都是信息檢索領(lǐng)域的常用評(píng)價(jià)指標(biāo)[13]。通常用幾個(gè)指標(biāo)綜合評(píng)價(jià)聚類效果，一個(gè)聚類的F值越高、純度越高、熵越低，則聚類效果越好。

我們使用上面提出的聚類組合算法SGCom與其他算法比較。參與比較的算法包括第一節(jié)中提到的SNTClus算法、CAS算法和WFCM算法。

因?yàn)镾GCom算法中有兩個(gè)參數(shù)，分別表示用SNAMEC算法聚類的結(jié)果和用SGoalC算法聚類的結(jié)果的權(quán)重。本文也設(shè)計(jì)了實(shí)驗(yàn)討論的選取對(duì)聚類效果的影響。

實(shí)驗(yàn)1 SGCom算法參數(shù)討論

參數(shù)α和β滿足：α，β∈（0，1）且α+β=1。

分別選取α的值為0.2到0.8，對(duì)應(yīng)的β取值從0.8到0.2，針對(duì)我們準(zhǔn)備的6個(gè)不同領(lǐng)域共600個(gè)服務(wù)，得到聚類的F值、純度和熵，如表2所示。

從實(shí)驗(yàn)結(jié)果可知α=0.4，β=0.6時(shí)，針對(duì)我們的數(shù)據(jù)集，聚類效果比較好。這是因?yàn)閿?shù)據(jù)集中的服務(wù)都經(jīng)過人工標(biāo)注，服務(wù)的功能性目標(biāo)描述非常完整，能很好地補(bǔ)充服務(wù)信息。如果是服務(wù)功能性目標(biāo)描述不完整的服務(wù)，可能SGoalC算法的聚類結(jié)果對(duì)服務(wù)聚類的貢獻(xiàn)不大，應(yīng)該增大α的取值。endprint

實(shí)驗(yàn)2 聚類效果分析

SGCom算法與其他算法的聚類性能比較如圖2所示。

從實(shí)驗(yàn)結(jié)果可知SGCom算法的F值和純度最高，熵最低。SGCom算法和同樣使用模糊聚類的WFCM算法比較，F(xiàn)值和純度分別提升了0.66和0.61，熵降低了0.55，說明增加服務(wù)的描述信息，并引入RGPS模型有效地組織這些信息，可以提高服務(wù)聚類的效果。

6 結(jié)束語

本文提出了一種基于標(biāo)簽的服務(wù)聚類方法，首先通過對(duì)服務(wù)描述分析，將Web服務(wù)按照名稱、角色和目標(biāo)標(biāo)注，然后使用混合的FCM方法對(duì)服務(wù)聚類，為以后的服務(wù)選擇和推薦提供基礎(chǔ)。在下一步工作中，將繼續(xù)深入研究服務(wù)的半自動(dòng)建模方式及服務(wù)聚類結(jié)果和給定的初始類簇?cái)?shù)k之間的關(guān)系。由于文中現(xiàn)在使用的服務(wù)來自PWeb中的一些類別，已經(jīng)分好了類，因此本文沒有考慮k值設(shè)定的問題，但是對(duì)于不知道分類的服務(wù)，k值是否合理決定著服務(wù)聚類的效果尚不清楚。k值的選擇對(duì)本文提出的聚類算法的影響值得深入研究。

參考文獻(xiàn)（References）：

[1] 李征，王健，張能等.一種面向主題的領(lǐng)域服務(wù)聚類方法[J].計(jì)

算機(jī)研究與發(fā)展，2014.51（2）：408-419

[2] Elgazzar K， Hassan A E， Martin P. Clustering WSDL

Documents to Bootstrap the Discovery of Web Services[C]. 2010 IEEE International Conference on Web Services. IEEE Computer Society，2010：147-154

[3] Li P， Wen J， Li X. SNTClus： A Novel Service Clustering

Algorithm based on Network Analysis and Service Tags[J]. Wydawnictwo SIGMA-NOT， 2013.

[4] 大橋宏輝. Calculating Word Similarity for Context Aware

Web Service Clustering[J]. Ieice Technical Report Sc Services Computing，2013.112：29-31

[5] Dorn C， Dustdar S. Weighted fuzzy clustering for

capability-driven service aggregation[C].Service-Oriented Computing and Applications （SOCA）， 2010 IEEE International Conference on. IEEE，2010：1-8

[6] 張秀偉.RGPS驅(qū)動(dòng)的個(gè)性化Web服務(wù)推薦方法研究[D].武

漢大學(xué)碩士學(xué)位論文，2014.

[7] Q. Yu and M. Rege. On service community learning： A

co-clustering approach[C]. In Proc of Web Services （ICWS）， 2015 IEEE International Conference on Web Services，2015：283-290

[8] C.B. Pop， V.R. Chifu， I. Salomie， M. Dins Q. Yu and M.

Rege. On service community learning： A co-clustering approach[C]. In Proc of Web Services （ICWS）， 2016 IEEE International Conference on，2016：283-290

[9] Pop C B， Chifu V R， Salomie I， et al. Semantic Web

Service Clustering for Efficient Discovery Using an Ant-Based Method[C]. Intelligent Distributed Computing IV-Proceedings of the International Symposium on Intelligent Distributed Computing-IDC 2010， Tangier， Morocco， September，2010：23-33

[10] Fellbaum C， Miller G. WordNet： an electronic lexical

database[J]. Cognition Brain & Behavior，1998.

[11] Ahsaee M G， Naghibzadeh M， Naeini S E Y. Semantic

similarity assessment of words using weighted WordNet[J]. International Journal of Machine Learning & Cybernetics，2014.5（3）：479-490

[12] Bezdek J C， Ehrlich R， Full W. FCM： The fuzzy c-means

clustering algorithm[J]. Computers & Geosciences，1984.10（2-3）：191-203

[13] Wang B B， Mckay R I B， Abbass H A， et al.

AComparative Study for Domain Ontology Guided Feature[C]. Proceedings of the 26th Australasian computer science conference-Volume 16. Australian Computer Society，Inc.，2003：69-78endprint