0 引言

　　隨著面向服務的體系架構(gòu)(Service Oriented Architecture，SOA)的迅猛發(fā)展，互聯(lián)網(wǎng)上Web服務數(shù)目呈持續(xù)增長趨勢。如何為用戶快速有效地推薦合適的服務成為一項極具挑戰(zhàn)性的研究任務。由于版權(quán)和資金等原因，大量UDDI服務注冊中心相繼關閉[1]，基于搜索引擎技術(shù)的服務發(fā)現(xiàn)方法成為主流方式。常用搜索技術(shù)基本采用基于關鍵字匹配的方式，導致服務發(fā)現(xiàn)的精準度受到服務描述中缺少關鍵字或同形異義等因素的影響[2]。長期以來，服務聚類被視為解決該問題的一種有效途徑，并得到了學術(shù)界的廣泛關注[2-5]，它將功能相似的服務聚類到一起從而減小搜索空間，提高服務發(fā)現(xiàn)效率[3]。例如文獻[2]從WSDL文檔中抽取服務特征建立特征向量，依照特征向量組織成不同的服務類簇。盡管上述服務聚類方法在不同情景下具有很好的效果，但是當面對服務描述語義稀疏時發(fā)現(xiàn)此過程中仍然會出現(xiàn)一些問題，造成這些問題的主要原因是諸多聚類算法在服務描述語義稀疏時，語義稀疏描述導致缺乏足夠的統(tǒng)計信息進而無法進行有效的相似度計算[6]。互聯(lián)網(wǎng)上最大的服務注冊中心ProgrammableWeb(http：//www.programmableweb.com，PWeb)提供了針對各類服務的注冊功能，同時提供了服務關于功能的自然語言描述信息，通過這些信息進行服務分類。存在的關鍵問題是，這些服務描述往往以短文本形式存在，語義稀疏程度非常高。據(jù)統(tǒng)計，PWeb中服務數(shù)量最多的前10個分類中，服務描述文本平均長度僅為72，其中包含大量的無意義詞語。面對互聯(lián)網(wǎng)上與日俱增的服務規(guī)模，在語義稀疏的情境下，傳統(tǒng)服務聚類方法精確度普遍不高，影響服務發(fā)現(xiàn)和推薦效率。

　　1 相關工作

　　文獻[7]建立基于統(tǒng)計的模型動態(tài)計算服務相似性，促進搜索引擎發(fā)現(xiàn)服務的能力;文獻[8]基于層次Agglomerative聚類算法，采用一種自下而上的方式將功能相似的服務組織成不同類簇，提高服務發(fā)現(xiàn)效率;文獻[9]提出一種WTCluster服務聚類方法，利用Kmeans算法聯(lián)合WSDL和標簽相似性進行服務聚類;文獻[10]利用Petri網(wǎng)技術(shù)針對服務功能和過程兩個側(cè)面的相似性進行服務聚類，提升服務發(fā)現(xiàn)效率;文獻[11]提出一種支配服務的概念，通過分析服務支配關系構(gòu)建服務與用戶請求之間的相關性;文獻[12]提出一種基于Info-Kmean與概要的增量學習方法，解決K-means算法中心點選取0值特征導致KL散度值無窮大的問題。

　　目前，基于主題模型的服務聚類研究有很多。文獻[13]使用PLSA(Probabilistic Latent Semantic Analysis)和LDA(Latent Dirichlet Allocation)從服務描述中發(fā)現(xiàn)服務的潛在主題，使用主題模型對OWL-S服務的Profile和功能描述進行聚類;文獻[9]利用LDA將WSDL中提取的特征描述構(gòu)建成為層次結(jié)構(gòu)，獲取關于服務的主題—特征分布，建立基于主題的服務發(fā)現(xiàn)技術(shù);文獻[14]將WSDL文檔預處理獲取特征向量表征且與服務功能標簽相融合，利用WT-LDA模型實現(xiàn)服務聚類。

　　上述方法在不同程度上提高了服務聚類效率，但仍然存在以下不足：①參與聚類的服務文檔大多數(shù)是基于某種特定格式的服務描述文檔，缺乏對自然語言描述的服務發(fā)現(xiàn)方法研究;②針對自然語言短文本描述的服務發(fā)現(xiàn)方法經(jīng)常會遭遇語義稀疏的情況，而服務發(fā)現(xiàn)過程中鮮有考慮此方面的問題。因此，本文提出一種基于BTM對服務描述進行特征構(gòu)建的方法，有效規(guī)避描述信息的語義稀疏問題，在此基礎上利用服務潛在特征進行服務聚類的方法以提高服務聚類質(zhì)量。

　　2 基于BTM的語義稀疏服務聚類方法

　　本文提出的基于BTM的語義稀疏服務聚類方法(Semantic Sparse Service Clustering，S3C)是一種基于主題模型進行服務聚類的方法，聚類過程主要分為3個階段：數(shù)據(jù)爬取與預處理、基于BTM的潛在特征構(gòu)造和基于服務的潛在特征聚類，具體流程如圖1所示。第一階段，主要從服務注冊中心爬取服務的描述文件進行數(shù)據(jù)清洗;第二階段，通過訓練BTM模型獲取文檔—主題分布，構(gòu)建服務的潛在特征;第三階段，依據(jù)上階段獲取的服務潛在特征，利用聚類算法進行聚類工作。

　　2.1 數(shù)據(jù)爬取與預處理

　　從PWeb中獲取服務的文本描述數(shù)據(jù)，獲得這些信息之后，創(chuàng)建表征服務內(nèi)容的初始特征向量。

　　(1)建立初始向量：基于自然語言處理包NLTK實現(xiàn)服務描述文檔的分詞。

　　(2)詞干還原：利用NLTK提供的PorterStemmer算法將特征向量中的特征詞匯進行詞干還原，例如，Learned和Learning具有相同詞干Learn。

　　(3)移除功能詞：功能詞匯指諸如“the”、“a”等對服務特征沒有實際意義的詞，需要從文檔中移除此類功能詞。

　　完成上述數(shù)據(jù)清理過程，為潛在特征構(gòu)造提供數(shù)據(jù)支持。

　　2.2 基于BTM的潛在特征構(gòu)造

　　BTM和LDA都是主題模型。BTM模型中，即使文本只有10個關鍵詞，也會構(gòu)造出45個Biterm，該方法極大程度地解決了LDA對短文本處理存在的弊端。同時，大量實驗發(fā)現(xiàn)，使用Biterm對文本建模要比用單一詞語建模能夠更好地挖掘文本的隱藏主題。

　　2.2.1 BTM模型

　　BTM概率圖模型如圖2所示，首先生成基于BTM模型的語料庫。從概率圖模型可以發(fā)現(xiàn)：對于一個短文本的服務描述文檔，不同詞對所對應的主題Z=1，2，…，z是獨立的，這是BTM與傳統(tǒng)主題建模方法的顯著區(qū)別。BTM針對整個語料集合[B]中每個詞對[b(wi，wj)]進行建模，未對文檔的生成過程進行建模，在學習過程中尚未獲得服務文檔的主題分布，得到的僅是詞對—主題與主題—詞的分布。為了獲取文檔—主題分布，本文采用貝葉斯公式推理得到服務文檔的主題分布。

　　使用式(1)計算每個詞對的概率。

　　使用式(2)計算整個語料庫[B]的概率。

　　首先，根據(jù)全概率公式，使用式(3)表示文檔主題—分布。

　　其中，利用貝葉斯公式計算詞對—主題分布，如式(4)所示。

　　式(3)中，[P(b|d)]可以將服務描述文檔中詞對的經(jīng)驗分布作為[P(b|d)]估算值，具體如式(5)所示。

　　其中，[nd(b)]表示文檔d中詞對b出現(xiàn)的次數(shù)。

　　2.2.2 參數(shù)估算

　　利用BTM獲得服務描述文檔的主題分布，必須要估算出BTM中參數(shù)[θ]和[φ]的設置。常用參數(shù)估算方法有期望傳播、變分推理和Gibbs抽樣等[15]，本文采用Gibbs抽樣方法作為BTM的參數(shù)估算方法，如式(6)所示。

　　對于語料集合[B]中的每一個詞對[b(wi，wj)]，計算詞對的條件概率分布，獲得其主題分布[zb]，其中[z-b]表示在集合[B]中除該詞對外的主題分配，[nz]表示主題z分配給詞對[b]的次數(shù)，[nwi|z]表示主題z分配給單詞[wi]的次數(shù)，[nwj|z]表示主題z分配給單詞[wj]的次數(shù)，M表示特征詞的個數(shù)。

　　根據(jù)詞對—主題分布情況，利用式(7)和式(8)計算出參數(shù)[θ]和[φ]。

　　其中，[φw|z]表示主題z中單詞w的概率，[θz]表示主題z的概率，[B]是詞對集合中詞對的總數(shù)。

　　2.3 基于服務的潛在特征聚類

　　根據(jù)上文分析，通過式(3)使用貝葉斯公式計算得到服務的文檔—主題分布[P(z|d)]。通過大量實驗對比，采用式(9)的方法對每個服務描述進行表示，將服務表示轉(zhuǎn)換成潛在特征。

　　將服務表示成潛在特征后，使用Kmeans方法對服務進行聚類，聚類具體過程見算法1。

　　算法1 語義稀疏的服務聚類算法

　　輸入：服務集合SS，超參數(shù)[α]、[β]，主題數(shù)目。

　　輸出：服務類簇。

　　1 初始化Z，并使得|Z|等于聚類數(shù)目。

　　2 WHILE 算法未收斂 DO

　　3 FOR iter = 1 TO Niter DO

　　4 FOR [b∈B]DO

　　5 基于[P(z|z-b，B，α，β)]，采樣[zb]

　　6 更新[nz]，[nwi|z]和[nwj|z]

　　ENDFOR

　　ENDFOR

　　ENDWHILE

　　7 得到參數(shù)Θ和Ф。

　　8 根據(jù)式(3)—式(5)，建立主題—服務分布，使用式(9)建立服務潛在特征表征。

　　9 基于服務潛在特征，使用K-means算法對服務進行聚類，最終返回服務類簇。

　　第1-7步使用Gibbs抽樣獲得BTM模型的模型參數(shù);第8步基于式(3)—式(5)計算獲得服務的文檔—主題分布，根據(jù)式(10)構(gòu)建服務的潛在特征表示;第9步實現(xiàn)服務聚類，并返回服務的類簇信息。

　　3 實驗評價

　　3.1 實驗準備

　　實驗數(shù)據(jù)來源于PWeb，該網(wǎng)站提供的服務具有詳細的Profile信息。實驗過程中爬取10 050個Web服務及其相關信息，篩選了包含服務最多的5個類別，總共包含2 761個Web服務，數(shù)據(jù)統(tǒng)計如表1所示。

　　使用純度(purity)和熵(entropy)作為評價指標，其中，純度越高，且熵越小，表明服務聚類的效果越好。設類簇[ci]包含個數(shù)為[ni]，使用式(10)和式(11)計算每個類簇的純度和所有類簇的平均純度。

　　其中，[ni]代表類簇[ci]中包含的服務數(shù)目，[nji]代表第j個分類中被成功分入[ci]中的服務數(shù)目。

　　使用式(12)和式(13)計算每個類簇的熵和所有類簇的熵。

　　3.2 結(jié)果與分析

　　3.2.1 方法性能

　　為了評測本文所提出S3C方法的聚類性能，將其與3種常用的服務聚類方法進行性能對比。

　　(1)K-means：該方法是基于劃分的聚類算法，實驗過程中，直接使用K-means對服務進行聚類。

　　(2)Agglomerative：該方法是基于自底向上的層次聚類算法，實驗過程中，直接使用Agglomerative方法對服務進行聚類。

　　(3)LDA：該模型是一種無監(jiān)督的主題聚類模型，實驗過程中，直接使用LDA模型對服務進行聚類。

　　在實驗過程中，使用BTM開源代碼(http：//code.google.com/p/btm)構(gòu)造潛在特征，超參數(shù)采用文獻[16]中設置的[α]=50/K，[β]=0.01。

　　從圖3得出如下結(jié)論：①S3C算法不論是在純度還是熵上的表現(xiàn)都優(yōu)于其它方法，特別是與直接使用LDA相比，算法性能得到明顯提升，說明S3C算法是有效的;②K-means算法、Agglomerative算法和LDA模型在基于語義稀疏服務聚類的時候性能并不好，說明傳統(tǒng)算法在語義稀疏的環(huán)境下容易遭受相似度計算困難的問題，進一步驗證了文獻[6]結(jié)論的正確性。實驗結(jié)果說明，基于BTM的方法在語義稀疏的情境下進行服務聚類的優(yōu)勢，也進一步說明在聚類中考慮語義稀疏的必要性。

　　3.2.2 參數(shù)影響

　　主題個數(shù)K的選取是影響主題模型性能的重要因素。本文采用基于貝葉斯模型[17]選擇方法，確定本文所用實驗數(shù)據(jù)的主題數(shù)目。在不同K值下運行Gibbs抽樣算法，觀測[log(P(w|K))]變化情況。具體實驗結(jié)果如圖4所示，當主題數(shù)目K=200時，后驗概率能夠得到最好性能，主題模型對于給定數(shù)據(jù)取得最佳擬合度。因此，S3C中主題個數(shù)K的取值選取為200。同時，S3C中對BTM超參數(shù)設定選擇文獻[16]中設置的[α]=50/K，[β]=0.01。

　　4 結(jié)語

　　本文基于BTM提出了一種面向語義稀疏的服務聚類方法S3C，使用公開服務注冊中心Pweb真實數(shù)據(jù)進行相關實驗，驗證基于BTM的語義稀疏服務聚類方法的可行性和有效性[18]。與經(jīng)典的服務聚類方法進行對比，S3C方法在聚類純度、熵等方面均具有更好的聚類效果，從平均純度看，該方法達到0.68，比其它方法提升30%左右;從平均熵看，該方法降低到0.41，性能提升50%左右。下一步研究重點：①在語義稀疏服務聚類的基礎上研究面向領域的服務發(fā)現(xiàn)技術(shù)[19-20];②研究推薦與發(fā)現(xiàn)相結(jié)合的服務發(fā)現(xiàn)方法[21-22]，提升服務發(fā)現(xiàn)過程中的個性化程度。

　　參考文獻：

　　[1] Al-MASRI E， MAHMOUD QH. Investigating web services on the World Wide Web[C]. Proceedings of the 17th International Conference on World Wide Web，2008：795-804.

　　[2] ELGAZZAE K， HASSAN A.E and MAERIN P. Clustering wsdl documents to bootstrap the discovery of web services[C]. Proceedings of 2010 IEEE International Conference on Web Services (ICWS)， 2010： 147-154.

　　推薦閱讀：有機化學sci期刊