一種基于群體智慧的智能服務(wù)聚類方法

陳彥萍， 高宇坤， 張恒山， 夏 虹， 王忠民，王 鑫， 高 慧

(1. 西安郵電大學(xué) 計算機學(xué)院 陜西 西安 710121； 2. 陜西省網(wǎng)絡(luò)數(shù)據(jù)分析與智能處理重點實驗室 陜西 西安 710121)

0 引言

近年來，面向個人、家庭、集團(tuán)用戶的各種創(chuàng)新應(yīng)用急速增長，各行各業(yè)的“智能服務(wù)”應(yīng)運而生[1-3].智能服務(wù)以用戶需求為中心，進(jìn)行服務(wù)模式和商業(yè)模式的創(chuàng)新[1]，能夠自動辨識用戶的顯性和隱性需求，并且主動、高效地滿足其需求的服務(wù)[3].智能服務(wù)種類繁多，數(shù)量龐大，因此海量智能服務(wù)的供需匹配是一個復(fù)雜的過程，需要通過智能服務(wù)的聚類、選擇與評價等幾個階段來解決.因此，在實現(xiàn)智能服務(wù)供需匹配的初始階段，如何對海量的智能服務(wù)進(jìn)行聚類處理，快速、準(zhǔn)確和高效地選出能夠滿足用戶請求所需的智能服務(wù)集合成為一個亟待解決的問題.

聚類目前已經(jīng)被大量地應(yīng)用在服務(wù)的研究當(dāng)中，服務(wù)聚類是指按照服務(wù)與服務(wù)之間的相似程度，把性質(zhì)類似的服務(wù)劃分到同一個簇中，相同簇的服務(wù)具有相似特性.為了解決不同的問題，滿足不同的需求，很多學(xué)者研究并實現(xiàn)了各種各樣的聚類算法.文獻(xiàn)[4-7]將機器學(xué)習(xí)算法運用到服務(wù)發(fā)現(xiàn)中，可以降低服務(wù)的搜索范圍,進(jìn)而提高服務(wù)發(fā)現(xiàn)的效率.文獻(xiàn)[5]基于功能相似性進(jìn)行服務(wù)的聚類，可以提高服務(wù)的檢索效率.文獻(xiàn)[6]在服務(wù)描述文檔中運用特征選擇工程，選擇相關(guān)的能體現(xiàn)服務(wù)功能的關(guān)鍵特征，量化關(guān)鍵特征，計算服務(wù)相似度，最后聚類成簇.文獻(xiàn)[7]統(tǒng)計每個詞在每個服務(wù)文本中出現(xiàn)的次數(shù)，構(gòu)建詞與文檔的矩陣，將每個詞轉(zhuǎn)化成數(shù)字，然后通過生成的數(shù)字化矩陣計算服務(wù)間相似度，從而聚類成簇.文獻(xiàn)[8]基于貓群優(yōu)化算法提出一種按照功能相似性進(jìn)行服務(wù)聚類的方法.文獻(xiàn)[9]在確定聚類數(shù)的前提下，實現(xiàn)對服務(wù)的聚類預(yù)處理.文獻(xiàn)[10]通過不同的相似度閾值，獲得不同的聚類結(jié)果.文獻(xiàn)[11]提出基于屬性的網(wǎng)格資源動態(tài)聚類法.文獻(xiàn)[12]為確定最佳分類，通過構(gòu)造F-統(tǒng)計量的方法進(jìn)行評價選取.文獻(xiàn)[13]提出了一種面向主題的領(lǐng)域服務(wù)聚類方法，該方法在對服務(wù)進(jìn)行領(lǐng)域分類的基礎(chǔ)上，結(jié)合概率、融合領(lǐng)域特性的領(lǐng)域服務(wù)聚類模型DSCM，并基于該模型提出了一種面向主題的聚類方法.文獻(xiàn)[14]提出了面向領(lǐng)域的標(biāo)簽輔助的服務(wù)聚類方法，該方法在建立DT-WSC服務(wù)聚類模型的基礎(chǔ)上提高了聚類效果.文獻(xiàn)[15]從服務(wù)描述文檔中提取內(nèi)容、上下文、主機名和服務(wù)名稱4個特征，以便使用樹遍歷算法對服務(wù)進(jìn)行聚類，通過歸一化Google距離來測量內(nèi)容和上下文之間的相似性.上述文獻(xiàn)所述的服務(wù)聚類大多都只使用了一種聚類方法(如k-means聚類)，這存在很大的局限性，因為沒有一種聚類算法能準(zhǔn)確揭示各種數(shù)據(jù)集所呈現(xiàn)出來的多種多樣的簇結(jié)構(gòu).

為了解決這一問題，本文提出了一種基于群體智慧的智能服務(wù)聚類方法(service cluster based on wisdom of crowds，SCWoC).該方法將基于群體智慧的聚類集成方法應(yīng)用到智能服務(wù)中，使其滿足智能服務(wù)的特點.先將服務(wù)數(shù)據(jù)集進(jìn)行轉(zhuǎn)化，得到一個滿足群體智慧準(zhǔn)則的可使用數(shù)據(jù)集，然后利用不同聚類算法進(jìn)行集成.該方法利用滿足智能服務(wù)特征的群體智慧理論，使基聚類結(jié)果互相學(xué)習(xí)，實現(xiàn)了基聚類算法的集成，提高了服務(wù)聚類結(jié)果的準(zhǔn)確性.

1 相關(guān)概念

1.1 群體智慧與聚類集成

文獻(xiàn)[16]首先提出了群體智慧的概念. 群體智慧又稱作集體智慧，可以理解為共享的或者群體的智能，它可以在細(xì)菌、動物群體、人類社會、計算機網(wǎng)絡(luò)中出現(xiàn)，表現(xiàn)為集體協(xié)作的創(chuàng)作方式、協(xié)商一致的決策方式等群體合作形式.文獻(xiàn)[17]提出一種基于群體智慧優(yōu)化決策框架.文獻(xiàn)[18-19]提出“聚類集成”的概念：聚類集成是指將關(guān)于一個對象集合的多個劃分組合成一個統(tǒng)一聚類結(jié)果的方法.文獻(xiàn)[20]提出聚類集成(cluster ensembles)的目標(biāo)就是要尋找一個聚類，相對于所有的輸入聚類結(jié)果來說，盡可能多的符合(或一致).

聚類集成的過程為：假設(shè)數(shù)據(jù)集X有n個數(shù)據(jù)對象X={x1,x2,…,xn}，首先對數(shù)據(jù)集使用N次聚類算法，得到N個聚類結(jié)果，其中pi(i=1,2,…,N)為第i個聚類算法得到的聚類結(jié)果；然后利用一致性函數(shù)T對P中的聚類結(jié)果進(jìn)行集成，得到一個新的數(shù)據(jù)劃分P′，將此作為最終的聚類結(jié)果.

1.2 基于群體智慧的聚類集成

文獻(xiàn)[21]最先將群體智慧概念應(yīng)用到聚類問題上，給出了一種基于群體智慧框架的聚類模型，將群體智慧框架在聚類集成問題中轉(zhuǎn)化為如下內(nèi)容：

1) 獨立性. 即數(shù)據(jù)間的特征必須滿足最小關(guān)聯(lián)性.

2) 分散性. 基聚類算法生成的基聚類結(jié)果必須只使用自己的方法.

3) 多樣性. 每一個聚類算法都有聚類結(jié)果，即使與事實相差很多.

4) 聚集性. 將各自的聚類結(jié)果轉(zhuǎn)化成為集成結(jié)果的機制.

圖1 基于群體智慧框架的聚類模型Fig.1 Clustering model based on wisdom of crowds framework

文獻(xiàn)[22]將這種模型進(jìn)行了詳細(xì)的說明和論證，通過大量實驗驗證了基于群體智慧框架的聚類模型的可行性與優(yōu)越性.模型如圖1所示，數(shù)據(jù)集通過映射函數(shù)得到映射集，此時，實現(xiàn)了群體智慧的獨立性標(biāo)準(zhǔn)；映射集通過轉(zhuǎn)換函數(shù)得到轉(zhuǎn)換集，此時，實現(xiàn)了群體智慧的分散性標(biāo)準(zhǔn)；轉(zhuǎn)換集通過不同的聚類算法得到參考集，此時，實現(xiàn)了群體智慧的多樣性標(biāo)準(zhǔn)；參考集通過學(xué)習(xí)算法得到結(jié)果集，此時，實現(xiàn)了群體智慧的聚集性標(biāo)準(zhǔn).

2 基于群體智慧的服務(wù)聚類方法

智能服務(wù)的供需匹配是一個復(fù)雜的問題，需要分為智能服務(wù)的聚類、選擇與評價等多個階段.首先使用服務(wù)聚類算法對數(shù)據(jù)進(jìn)行預(yù)處理，為服務(wù)匹配做準(zhǔn)備，把類似的服務(wù)聚成類簇.其次，通過服務(wù)發(fā)現(xiàn)機制，將用戶的搜索請求定位到相應(yīng)的服務(wù)類簇，從而降低服務(wù)的搜索數(shù)量和匹配計算量，提高服務(wù)發(fā)現(xiàn)效率.本文提出一種包含群體智慧理論的聚類集成方法(SCWoC)，在群體智慧的框架下有效地提高了基聚類結(jié)果的準(zhǔn)確性、聚類集成結(jié)果的穩(wěn)定性及準(zhǔn)確性.

圖2 SCWoC算法流程圖Fig.2 SCWoC algorithm flow chart

2.1 SCWoC方法

SCWoC方法的整體框架如圖2所示，該框架包含用戶和服務(wù)搜索引擎2個查詢角色；5個組間，分別是特征提取器、相似度計算器、相似度集成器、基聚類器、聚類集成器.

具體實現(xiàn)過程為：首先用R語言工具從programmableWeb上爬取相應(yīng)的服務(wù)數(shù)據(jù)，包括服務(wù)名稱、服務(wù)類別、服務(wù)描述文本、以及tag標(biāo)注信息；然后，通過特征提取器提取每個服務(wù)描述文本和tag標(biāo)注信息，并將其作為服務(wù)聚類的輸入文本，采用相似度計算器分別計算出服務(wù)描述文本和tag標(biāo)注信息相似度，通過相似度集成器將服務(wù)描述文本相似度和tag標(biāo)注相似度進(jìn)行融合，得到服務(wù)之間的相似度，并將其作為基聚類器的輸入矩陣；接下來，由基聚類器進(jìn)行聚類，得到基聚類結(jié)果，利用聚類集成器對聚類結(jié)果進(jìn)行集成，得到最終的聚類結(jié)果后，用戶通過服務(wù)搜索引擎進(jìn)行服務(wù)搜索與查詢，系統(tǒng)返回搜索結(jié)果給用戶.

2.2 服務(wù)相似性計算

本文主要是在聚類方法上進(jìn)行了優(yōu)化，由于Web服務(wù)數(shù)據(jù)集一般都是文本數(shù)據(jù)集，不能直接使用，所以服務(wù)相似度計算是用來處理這些不能直接使用的文本數(shù)據(jù)，將其轉(zhuǎn)化為數(shù)值數(shù)據(jù)，這樣就可以進(jìn)行聚類操作.

2.2.1文本相似性計算 服務(wù)描述文本描述了服務(wù)的功能，由一段文本組成，先對服務(wù)描述文本進(jìn)行預(yù)處理，提取有意義的內(nèi)容詞匯形成一個服務(wù)描述文本的權(quán)值向量，然后，再根據(jù)權(quán)值向量進(jìn)行相似度計算，主要由以下4個步驟完成[23].

1) 提取詞語.將句子劃分成詞語，提取名詞作為詞語特征詞.

2) 移除停用詞.去掉一些無意義的符號和不能區(qū)分主題的詞匯，例如：+、*、&、the、and、of等.

3) 處理詞干. 將一個詞處理為它的詞干或者詞根的形式，例如 gived、gives，全部處理成give.

4) 選擇關(guān)鍵詞. 運用tf-idf閾值算法選擇文檔集的關(guān)鍵詞.

其中tf-idf閾值算法主要包括兩個步驟.首先計算詞頻，詞頻tfij計算公式為

(1)

其中：分子表示詞條i在文檔j中出現(xiàn)的次數(shù)；分母是文檔j中所有詞條之和.其次計算逆向文件頻率idfi，其公式為

idfi=log(N/ni)，

(2)

其中：N是文檔集總數(shù)；ni是包含詞條i的文檔數(shù)目.

標(biāo)準(zhǔn)配送式變電站采用模塊化、標(biāo)準(zhǔn)化、工廠化生產(chǎn)，是未來變電站發(fā)展的新方向。預(yù)制光纜作為實現(xiàn)二次設(shè)備間模塊化、標(biāo)準(zhǔn)化連接的重要手段，有效提高了標(biāo)準(zhǔn)配送式變電站現(xiàn)場光纜接線的質(zhì)量與效率，在標(biāo)準(zhǔn)配送式變電站內(nèi)得以廣泛應(yīng)用，但同時存在工程應(yīng)用方案眾多、工程實施問題較多等情況。本論文結(jié)合標(biāo)準(zhǔn)配送式變電站預(yù)制光纜的工程應(yīng)用現(xiàn)狀及需求，結(jié)合預(yù)制光纜的結(jié)構(gòu)型式、光纜類型、預(yù)制方式等因素對預(yù)制光纜的工程應(yīng)用方案進(jìn)行研究并給出標(biāo)準(zhǔn)化應(yīng)用方案，同時對工程實施中的常見問題進(jìn)行分析研究并提出解決方案，有助于實現(xiàn)預(yù)制光纜的標(biāo)準(zhǔn)化應(yīng)用與工程推廣。

詞條i在文檔j的tf-idf權(quán)值計算公式為

ωij=tfij×idfi.

(3)

權(quán)值越大，說明詞條越重要，選出權(quán)值超出閾值的詞匯作為文檔的關(guān)鍵詞.

(4)

其中：θ是文檔i,j的特征向量的夾角.

2.2.2tag標(biāo)注相似性計算 tag信息也屬于服務(wù)功能性描述，使用tag信息能夠有效地提高服務(wù)聚類精度和查詢效率，tag相似性根據(jù)Jaccard系數(shù)方法進(jìn)行計算，

(5)

其中：分子表示同時標(biāo)注兩個服務(wù)的標(biāo)簽數(shù)；分母表示兩個服務(wù)的標(biāo)簽集并集.

2.2.3相似性集成 結(jié)合服務(wù)描述文本相似性和tag標(biāo)準(zhǔn)相似性，獲得兩個服務(wù)之間的集成相似度公式為

sim(si,sj)=simD(si,sj)+simtag(si,sj).

(6)

2.3 基聚類結(jié)果的生成

基聚類結(jié)果的生成方法主要有3種：1) 使用不同的數(shù)據(jù)子集；2) 對算法賦予不同的參數(shù)；3) 使用不同的聚類算法等.

本文使用均勻性來表示分區(qū)P與參考集E中所有分區(qū)的多樣性為

Uniformity(P,E)=1-(2η2(P))/(3η1(P)+Θ(P,E))，

其中：E是參考集；P是來自參考集E的分區(qū)，當(dāng)lim(Uniformity(P,E))=0，代表區(qū)域P的多樣性較低；當(dāng)lim(Uniformity(P,E))=1，代表區(qū)域P的多樣性較高；0≤Uniformity(P,E)≤1.本文將單個算法的均勻性與所有算法的均勻性的占比作為相似度矩陣WCS權(quán)重系數(shù).

(7)

其中：T代表個體聚類結(jié)果的數(shù)目；Uniformity(Pi,E)代表第i個區(qū)域P與參考集E的均勻性.

2.4 基于權(quán)重的聚類集成方法

聚類集成的核心問題之一是如何根據(jù)這些由聚類成員得到的聚類結(jié)果，構(gòu)造數(shù)據(jù)點之間的相似度矩陣.數(shù)據(jù)點xi，xj之間的相似度為

(8)

其中：xi,xj代表不同的數(shù)據(jù)點；M代表個體聚類結(jié)果的個數(shù)；Nij代表數(shù)據(jù)點xi,xj在M種基聚類算法劃分中是否屬于同一簇，若屬于同一簇，Nij=1，否則，Nij=0；C(xi)代表來自簇C中xi數(shù)據(jù)點；C(xj)代表來自簇C中xj的數(shù)據(jù)點.

添加權(quán)重的相似度矩陣WCS的計算公式為

(9)

其中：xi、xj、M、Nij、C(xi)、C(xj)與公式(8)定義一樣；ρi代表權(quán)重系數(shù).

綜上所述，SCWoC算法如下.

輸入：服務(wù)特征數(shù)據(jù)集Z.

輸出：最終服務(wù)聚類結(jié)果T.

1) 使用公式(1)～(4)生成文本相似性矩陣.

2) 使用公式(5)生成tag標(biāo)注相似性矩陣.

3) 使用公式(6)集成服務(wù)文本相似性矩陣和tag標(biāo)注信息相似性矩陣，得到服務(wù)相似矩陣Z.

4) 用不同的聚類算法對數(shù)據(jù)集Z進(jìn)行聚類，聚類的結(jié)果放入一個參考集E中.

5) 使用公式(7)計算權(quán)重.

6) 使用式(8)、(9)計算加權(quán)相似度矩陣WCS.

7) 對WCS矩陣使用k-means算法進(jìn)行聚類，得到服務(wù)聚類結(jié)果T.

3 實驗

3.1 數(shù)據(jù)集

本文從ProgrammableWeb上爬取了4 800個API服務(wù)，每一個API服務(wù)包括服務(wù)名稱、描述文本、tag標(biāo)簽、以及分類等信息.由于電腦條件的限制，數(shù)據(jù)量過大，本文從爬取的API服務(wù)中選取3個API類別，分別為Email(173個)、Video(172個)、Tools(255個)，API數(shù)量總共為600個.同時，把聚類結(jié)果與原有分類作比較，驗證試驗的有效性.

表1為API服務(wù)數(shù)據(jù)的樣式.其中desc中文本描述語句太長，文中不予描述,用符號…表示.

表1 API服務(wù)數(shù)據(jù)Tab.1 API service data

3.2 評價標(biāo)準(zhǔn)

本文采用純度指標(biāo)[24]和查全率來評價聚類的有效性.

令D為服務(wù)集合，C表示D上的聚類結(jié)果，ck∈C指的是一個聚類結(jié)果中的第k個簇，T為D上原有的標(biāo)準(zhǔn)聚類結(jié)果，tk∈T指的是標(biāo)準(zhǔn)聚類結(jié)果中的第k個簇，則ck的聚類純度CP(ck)定義為

查全率=(succ(ck))/(succ(ck)+missed(ck))，其中：succ(ck)是成功聚類到ck中服務(wù)的數(shù)目；missed(ck)是本應(yīng)該劃分到ck中但是卻劃分到其他類中服務(wù)的數(shù)目.

3.3 實驗過程及結(jié)果分析

使用表1中tags和desc數(shù)據(jù)分別生成tags相似度矩陣和desc相似度矩陣，然后通過這兩個矩陣構(gòu)建API服務(wù)間的相似度矩陣，之后對服務(wù)間相似度矩陣使用基聚類算法生成基聚類結(jié)果，通過權(quán)重集成得到最后的服務(wù)分類.在試驗中，將本文所提的SCWoC方法與FCluster方法[25](基于服務(wù)相似性的k-means方法)和MSCA方法[23](融合k-means與Agnes的服務(wù)聚類方法)進(jìn)行實驗比較.本文SCWoC方法服務(wù)聚類結(jié)果及構(gòu)成如表2所示.SCWoC方法、FCluster方法和MSCA方法在各類中的純度和查全率對比如表3所示.

表2 聚類結(jié)果及結(jié)構(gòu)構(gòu)成Tab.2 Clustering results and structure

由表3可知SCWoC方法在各類中的純度：類1、類2、類3的純度分別為67.7%、65.9%、63.8%.SCWoC方法與FCluster方法和MSCA方法的平均純度分別為65.8%、61.8%、63.1%.SCWoC方法相比與其他兩種方法在聚類純度上分別提升了4%和2.7%.

表3 三種方法的對比Tab.3 Comparison of three methods

表3還展示了3種方法查全率的比較，SCWoC方法、MSCA方法、FCluster方法的平均查全率分別為66.6%、62.8%、60.8%，可以得出SCWoC方法的平均查全率最高.

綜上所述，SCWoC方法有效地提高了服務(wù)聚類的純度和查全率.

4 結(jié)論

本文提出了一種基于群體智慧的服務(wù)聚類方法，從服務(wù)特征數(shù)據(jù)集入手利用群體智慧理論的獨立性、分散性、多樣性引導(dǎo)基聚類結(jié)果的生成，利用群體智慧的聚集性，采取基于權(quán)重的基聚類集成方法，對基聚類結(jié)果進(jìn)行聚合，實現(xiàn)服務(wù)聚類.使用Web服務(wù)數(shù)據(jù)集驗證了本文方法的有效性.實驗結(jié)果表明，相較于傳統(tǒng)的k-means服務(wù)聚類方法，提高了服務(wù)聚類的純度和查全率.