0 引言

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

　　1 相關(guān)工作

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

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

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

　　2 基于BTM的語義稀疏服務(wù)聚類方法

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

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

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

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

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

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

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

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

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

　　2.2.1 BTM模型

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

　　使用式(1)計(jì)算每個(gè)詞對(duì)的概率。

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

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

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

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

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

　　2.2.2 參數(shù)估算

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

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

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

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

　　2.3 基于服務(wù)的潛在特征聚類

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

　　將服務(wù)表示成潛在特征后，使用Kmeans方法對(duì)服務(wù)進(jìn)行聚類，聚類具體過程見算法1。

　　算法1 語義稀疏的服務(wù)聚類算法

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

　　輸出：服務(wù)類簇。

　　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)，建立主題—服務(wù)分布，使用式(9)建立服務(wù)潛在特征表征。

　　9 基于服務(wù)潛在特征，使用K-means算法對(duì)服務(wù)進(jìn)行聚類，最終返回服務(wù)類簇。

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

　　3 實(shí)驗(yàn)評(píng)價(jià)

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

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

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

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

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

　　3.2 結(jié)果與分析

　　3.2.1 方法性能

　　為了評(píng)測(cè)本文所提出S3C方法的聚類性能，將其與3種常用的服務(wù)聚類方法進(jìn)行性能對(duì)比。

　　(1)K-means：該方法是基于劃分的聚類算法，實(shí)驗(yàn)過程中，直接使用K-means對(duì)服務(wù)進(jìn)行聚類。

　　(2)Agglomerative：該方法是基于自底向上的層次聚類算法，實(shí)驗(yàn)過程中，直接使用Agglomerative方法對(duì)服務(wù)進(jìn)行聚類。

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

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

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

　　3.2.2 參數(shù)影響

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

　　4 結(jié)語

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

　　參考文獻(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.

　　推薦閱讀：有機(jī)化學(xué)sci期刊