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

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

0 引言

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

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

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

1 相關概念

1.1 群體智慧與聚類集成

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

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

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

文獻[21]最先將群體智慧概念應用到聚類問題上，給出了一種基于群體智慧框架的聚類模型，將群體智慧框架在聚類集成問題中轉化為如下內容：

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

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

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

4) 聚集性. 將各自的聚類結果轉化成為集成結果的機制.

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

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

2 基于群體智慧的服務聚類方法

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

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

2.1 SCWoC方法

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

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

2.2 服務相似性計算

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

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

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

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

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

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

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

(1)

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

idfi=log(N/ni)，

(2)

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

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

詞條i在文檔j的tf-idf權值計算公式為

ωij=tfij×idfi.

(3)

權值越大，說明詞條越重要，選出權值超出閾值的詞匯作為文檔的關鍵詞.

(4)

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

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

(5)

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

2.2.3相似性集成 結合服務描述文本相似性和tag標準相似性，獲得兩個服務之間的集成相似度公式為

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

(6)

2.3 基聚類結果的生成

基聚類結果的生成方法主要有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ū)，當lim(Uniformity(P,E))=0，代表區(qū)域P的多樣性較低；當lim(Uniformity(P,E))=1，代表區(qū)域P的多樣性較高；0≤Uniformity(P,E)≤1.本文將單個算法的均勻性與所有算法的均勻性的占比作為相似度矩陣WCS權重系數(shù).

(7)

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

2.4 基于權重的聚類集成方法

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

(8)

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

添加權重的相似度矩陣WCS的計算公式為

(9)

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

綜上所述，SCWoC算法如下.

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

輸出：最終服務聚類結果T.

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

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

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

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

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

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

7) 對WCS矩陣使用k-means算法進行聚類，得到服務聚類結果T.

3 實驗

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

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

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

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

3.2 評價標準

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

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

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

3.3 實驗過程及結果分析

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

表2 聚類結果及結構構成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方法有效地提高了服務聚類的純度和查全率.

4 結論

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