李蓉+葉俊民+楊艷

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

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

中圖分類號：TP3-0 文獻標(biāo)志碼：A 文章編號：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）是一個著名的網(wǎng)絡(luò)服務(wù)發(fā)布網(wǎng)站，在2012年其上發(fā)布的Web服務(wù)有6400多個[1]，而在2017年初，服務(wù)數(shù)量已經(jīng)達(dá)到15700多個，不到五年時間服務(wù)數(shù)量增加超過一倍。大量增長的服務(wù)給使用者提供了更多更好的選擇，但是也對服務(wù)選擇和推薦造成了更大困難，特別是對服務(wù)選擇和推薦的速度提出了更高的要求。

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

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

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

⑵ 多數(shù)服務(wù)聚類方法服務(wù)聚類后只能屬于某一個服務(wù)類別，沒有考慮概念的模糊性問題。很多服務(wù)可能屬于多個類型，比如天氣預(yù)報服務(wù)，因為旅游出行需要了解天氣信息，因此該服務(wù)可以屬于“出行”類別，同時因為社會生活中人們經(jīng)常關(guān)注天氣情況，該服務(wù)也可以分類在“社會生活”類別。在PWeb中的很多服務(wù)都有多個標(biāo)簽，可以把服務(wù)歸為不同的類別。因此只把服務(wù)歸為某種類別的硬聚類的方式有所欠缺。

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

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

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

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

⑴

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

⑵

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

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

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

⑶

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

定義1 SName相似度。

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

⑷

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

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

定義2 SGoal相似度。

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

⑸

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

⑹

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

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

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

⑺

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

3 聚類中心的計算方法

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

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

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

⑻

定義5 模糊元素可替。

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

⑼

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

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

⑽

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

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

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

4.1 計算聚類中心

算法1 FCM聚類中心計算算法

FCMCenter（S， U， p， th）

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

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

p表示聚類中心；

th表示閾值。

輸出：p表示計算后的聚類中心。

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

4.2 使用FCM算法對SName聚類

算法2 SName聚類算法endprint

SNAMEC（S， k， n， th）

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

k表示k個聚類中心；

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

th表示用戶定義的閾值；

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

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

1. m=0；

2. 隨機選取k×n個在[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時停止，th一般設(shè)置成0.01。算法中uij代表隸屬度矩陣U中的每一個元素，代表第m次迭代得到的k×n的隸屬度矩陣。

4.3 使用相似度計算的方法對SGoal聚類

算法3 SGoal聚類算法

SGoalC（S， P， k， n）

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

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

k表示k個聚類中心；

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ǔ)，比較每個服務(wù)和每個聚類中心的相似度，把結(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個聚類中心；

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和對結(jié)果的貢獻由權(quán)重標(biāo)記，具體權(quán)值可以根據(jù)實驗確定。

5 實驗

5.1 實驗準(zhǔn)備

為了檢驗本文提出的服務(wù)聚類方法SGCom，我們做了模擬實驗。實驗環(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虛擬機。

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

5.2 實驗分析

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

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

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

實驗1 SGCom算法參數(shù)討論

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

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

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

實驗2 聚類效果分析

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

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

6 結(jié)束語

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

參考文獻（References）：

[1] 李征，王健，張能等.一種面向主題的領(lǐng)域服務(wù)聚類方法[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ū)動的個性化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