李蓉+葉俊民+楊艷

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

關鍵詞： FCM算法； Web服務； 服務聚類； 服務相似度

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

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

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

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

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

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

1 數(shù)據(jù)準備

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

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

⑴

其中，SName表示服務的名稱，SRole表示服務針對的對象，SGoal表示該服務的功能目標。

⑵

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

2 服務的相似度計算方法

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

⑶

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

定義1 SName相似度。

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

⑷

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

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

定義2 SGoal相似度。

SGoal相似度表示服務的目標模型中的功能性目標屬性的相似程度，可表示為：

⑸

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

⑹

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

定義3 服務相似度。

服務相似度表示兩個服務的相似程度，可表示為：

⑺

其中α和β是調整系數(shù)，調整SNameSim和SGoalSim在計算結果中所占的權重，α+β=1。

3 聚類中心的計算方法

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

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

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

⑻

定義5 模糊元素可替。

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

⑼

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

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

⑽

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

4 Web服務聚類方法

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

4.1 計算聚類中心

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

FCMCenter（S， U， p， th）

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

U={u1，u2，…，un}，表示所有服務對應的隸屬度的集合；

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

4.2 使用FCM算法對SName聚類

算法2 SName聚類算法endprint

SNAMEC（S， k， n， th）

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

k表示k個聚類中心；

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

th表示用戶定義的閾值；

輸出：U表示服務隸屬度矩陣；

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一般設置成0.01。算法中uij代表隸屬度矩陣U中的每一個元素，代表第m次迭代得到的k×n的隸屬度矩陣。

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

算法3 SGoal聚類算法

SGoalC（S， P， k， n）

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

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

k表示k個聚類中心；

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

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

1. for i=1 to k

2. for j=1 to n

3. uij=SGoalSim（sj，pi）；

4. 更新隸屬度矩陣U；

5. Return U；

算法以前面得到的聚類中心為基礎，比較每個服務和每個聚類中心的相似度，把結果寫到新的隸屬度矩陣U中。

4.4 整合聚類結果

算法4 聚類組合算法

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

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

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

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

k表示k個聚類中心；

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

α和β分別表示U和U'的權重；

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

1. for i=1 to k

2. for j=1 to n

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

4. 更新隸屬度矩陣UNew；

5. Return UNew；

算法綜合SNAMEC和SGoalC算法得到的服務隸屬度矩陣，得到隸屬度矩陣UNew。U和對結果的貢獻由權重標記，具體權值可以根據(jù)實驗確定。

5 實驗

5.1 實驗準備

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

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

5.2 實驗分析

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

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

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

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

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

分別選取α的值為0.2到0.8，對應的β取值從0.8到0.2，針對我們準備的6個不同領域共600個服務，得到聚類的F值、純度和熵，如表2所示。

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

實驗2 聚類效果分析

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

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

6 結束語

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

參考文獻（References）：

[1] 李征，王健，張能等.一種面向主題的領域服務聚類方法[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驅動的個性化Web服務推薦方法研究[D].武

漢大學碩士學位論文，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