基于復雜網絡社團劃分的Ｗｅｂ ｓｅｒｖｉｃｅｓ聚類

摘 要：以單詞為網絡節點，由自然語言描述中單詞的同現頻率確定單詞間的相關度并作為邊的權值，構建自然語言描述集合的加權單詞網絡模型。利用Newman快速算法對加權單詞網絡模型進行社團劃分，得到單詞聚類結果；根據單詞聚類結果與服務之間的映射關系實現服務聚類。實驗結果與手工分類結果的對比表明，平均查準率達74.7%以上。

關鍵詞：Web服務； 聚類； 復雜網絡； 社團劃分； 文本聚類

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2299-04

doi:10.3969/j.issn.1001-3695.2009.06.091

Web services clustering based ondetecting community structurein complex network

OU You-yuan1， ZHANG Hai-su1，2， MENG Hui1， LI De-yi3

(1. Institute of Commanding Automation， PLA University of Science Technology， Nanjing 210007， China; 2. Commanding Communication Academy， Wuhan 430010， China; 3. Institute of Electronic System Engineering， Beijing 100141， China)

Abstract:

This paper described an algorithm which created WWN of service descriptions. The nodes was words， and WWN got the edge-weight through the words co-appearance. Newman fast algorithm could detect community structure in WWN and return the clusters of words. Using the relationship between words and services， achieved service-clustering. At last， an experiment on a collection of 1 007 Web services shows the high precision of 74.7%.

Key words：Web services; clustering; complex networks; community structure detecting; documents clustering

0 引言

Web services作為一種新興的Web應用模式，在整個網絡中被廣泛地發布與調用。OWL-S^[1]是W3C發布的標準，定義了描述Web services的本體。OWL-S通過ServiceCategory屬性來指向服務分類體系中的某一條目，條目值是ServiceCategory類的一個實例。目前大多數OWL-S文件均由WSDL文件轉換而來，而WSDL文件缺少分類信息，導致OWL-S文件也缺少分類信息（ServiceCategory屬性值空缺），給服務發現、檢索以及服務資源的管理帶來不便。如果手工對OWL-S服務進行分類，將面臨大量繁雜的工作。如何實現服務的自動聚類，構成了Web services研究的挑戰。

聚類技術可以實現對服務的無指導分類。對網絡中的大量服務進行聚類，能夠在沒有訓練樣本的條件下，自動產生聚類模型。在服務發現的結果呈現中，通過服務聚類，可以使大量不強相關的匹配結果按照類別分開呈列，有利于用戶快速定位其感興趣的檢索結果。聚類結果也可作為分類的基礎，便于服務資源的管理以及新服務的添加。

本文根據同類服務的自然語言描述中單詞同現頻率的高低作為服務聚類的依據，構建了自然語言描述集的加權單詞網絡（weighted words network，WWN）模型。選取復雜網絡社團劃分的Newman快速算法對WWN進行劃分，得到單詞聚類結果；最后通過單詞類別與服務類別的映射關系完成服務聚類過程。使用德國人工智能中心開發的OWL-S Test Collection進行聚類實驗，結果與手工分類結果比較，平均查準率達74.7%以上，與目前所見相關的服務/短文本聚類方法相比具有一定優勢。

1 相關工作

聚類按照事物的某些屬性將事物聚集成若干類，使得類間相似性盡量小，類內相似性盡量大^[2]。對應地，每個Web service都由自然語言描述(text description)，即一段對功能的描述文本。從一個Web service的自然語言描述來看，它所包含的詞匯提供了分類的直接信息。同類服務的自然語言描述擁有大量相同的詞匯，對這些詞匯進行相關性聚類，就可以指導服務聚類。由于Web服務的自然語言描述是單詞數量較少的文本，服務聚類部分轉換為對短文本的聚類。

目前，在大多數文本聚類方法中都使用VSM（vector space model，向量空間模型）來描述整個聚類對象^[3]。考慮對象集合D={D1，D2，…，Dk}，每一對象Di對應一個向量Vi，Vi定義為

Vi＝｛f(tf1，idf1)， f(tf2，idf2)，…， f(tfn，idfn)｝

其中：tfj是單詞j在對象Dj中出現的頻率；idfj表示單詞j在對象集合D中出現的對象總數； f表示tfj和idfj的函數。在使用VSM的方法中，需要計算每對向量之間的距離(可選歐氏距離、明氏距離等數種常用的距離度量)，然后使用不同算法進行聚類?；赩SM的主要聚類算法包括劃分方法、層次聚類和SOM神經網絡等。文獻[4~7]的實驗結果證明，基于VSM的聚類方法效果一般在60%左右，對小文本聚類效果則更差。

Noam Slonim等人^[8]提出通過信息瓶頸方法的單詞聚類來指導文本聚類的思想。此方法首先提取文本中的單詞，計算各單詞屬于一篇文本的概率；然后用貝葉斯方法計算兩個單詞屬于一個類的概率，進而通過此概率對單詞進行聚類；最后通過文本和單詞類的映射關系對文本分類，平均查準率約為67%。

Ferrer Cancho等人^[9]構造了一個語言網絡，將單詞或短語作為節點，單詞或短語在句子中的同現構成節點之間的邊。Matsuo等人^[10]發現，人類的語言網絡既不是完全隨機的，也不是完全規則的，而是具備小世界特性的復雜網絡。語言網絡在全局上高度連接，且局部高度聚集。復雜網絡理論的研究結果進一步揭示了網絡的抱團特性。網絡的社團劃分實質上是對節點的聚類。每個社團內部節點之間的連接相對緊密，而各個社團之間的連接相對比較稀疏^[11]。

基于語言網絡和復雜網絡的研究基礎，本文將聚類對象的各屬性值均看做節點，每個對象將成為一個節點集，在同現的屬性值（即節點）之間添上加權邊，形成復雜網絡。兩個對象對應的節點集之間的相同屬性值越多，它們之間的邊權值越大。網絡進行社團劃分后，由對象與節點之間的映射關系及節點在對象中的不同權值，節點類可以映射為對象類，實現了高維度的對象聚類。具體針對Web services，本文用自然語言描述中的單詞作為節點，單詞之間的聯系作為復雜網絡中的邊構建WWN。利用復雜網絡社團劃分算法，將劃分后的單詞集作為聚類，利用單詞集與文本的映射關系，指導自然語言描述集聚類。

2 加權單詞網絡模型

數學上在研究復雜網絡時，只關心節點之間有沒有邊相連，至于節點在什么位置、邊是什么形狀等是無須關心的^[12]。設網絡拓撲圖G(V，E)由節點集V和邊集E組成，需要從自然語言描述中抽象出網絡中的點、邊對應關系。本章設計了一套節點、邊的映射機制，并量化節點間的相關度，構建了自然語言描述的加權單詞網絡模型。

1）節點映射方法

將文本中的每個單詞映射為節點vi，所有節點構成節點集V；如果兩個單詞出現在自然語言描述的同一句中，就認為這兩個單詞之間直接關聯，在對應的節點間連邊，自然語言描述集將映射為一個單詞網絡。根據文本聚類的處理規則，只有名詞、動詞在文本中的作用最顯著。針對自然語言描述的短文本（單詞數量級僅為數十個）聚類，動詞數量相對較少，因此算法實驗中僅需要考慮相對數量較多的名詞。例如，OWL-S Test Collection中服務T-car price service的自然語言描述為：“This service analyzed car market value and deduced that color is one of the main issue in its popularity， so this service provides list of price of car with its color.”其包含的名詞為service、car、market、value、color、issue、popularity、list、price。構成的網絡如圖1所示。

獲取所抽取單詞的詞根，將同一單詞的不同形式（如單復數等）規范為同一形式。此外，算法需處理停用詞，主要包括同時出現在多個類別中的極高頻率詞以及頻率極低的單詞。原因為：a）這類單詞會影響聚類效果；b)通常聚類結果中的類名選自于單詞集，這類單詞也會對確定類名造成干擾。比如，在自然語言描述中，“service”就是高頻率詞，在初始的預處理中進行檢測時舍去。

2）邊映射方法

邊的映射體現為單詞之間的相關度，在同一句中，不同單詞所出現位置的距離越大，其相關度就越小。在WWN中將單詞間的相關度定義為節點之間邊的權值。WWN使用鄰接矩陣A存儲，矩陣元素aij為節點i與節點j之間邊的權值。

單詞之間的距離d影響單詞之間的相關度。若兩個單詞在同一個句子中相隔d個詞，則認為這兩個單詞的相關度為1/d；若兩個單詞分別在兩個句子里出現，則認為這兩個單詞出現同現現象。設兩個單詞在兩個句子中的相關度分別為1/d1和1/d2，則總相關度為

ε=(1/d1)×2+1/d2

例如，在上述T-car price service的自然語言描述中，“car”與“service”兩個詞在前句中相關度為1/2，在后句中相關度為1/6，因此總相關度為

ε=(1/d1)×2+1/d2=1/2×2+1/6=7/6

通過對節點及邊映射的定義，可以得到服務“T-car price service”的WWN，如圖2所示是帶有權值的WWN。



總結上述構建WWN的流程為：選定Web services測試集→抽取自然語言描述→詞性標注→抽取名詞→獲取詞根→去除停用詞→節點映射→邊權值計算等。

3 單詞聚類與服務聚類

3.1 單詞聚類

根據復雜網絡社團劃分算法，對WWN進行社團劃分，可以對大量單詞進行聚類，進而對服務進行聚類。為了說明這種聚類的合理性，首先介紹復雜網絡模塊度的概念。

模塊度是衡量網絡社團劃分質量的標準^[11]?？紤]某種劃分形式，它將網絡劃分為k個社團。定義一個k×k維的對稱矩陣E=(eij)，其中元素eij表示網絡中連接社團i和j的邊在所有邊中所占的比例。設矩陣中對角線各元素之和為Tre=∑ieii，它給出了網絡中所有社團內部的邊在所有邊中所占的比例。定義矩陣中每行的元素之和為ai=∑jeij，它表示與第i個社團中節點相連的邊在所有邊中的比例。任選一條邊連接社團i和j的概率為aiaj，連接社團內部節點的概率為∑ki=1a2i=‖e2‖。其中：‖e2‖表示矩陣 e2的所有元素之和。

定義 Q=∑i(eii-a2i)=Tre-‖e2‖

其中：Q是衡量社團劃分質量的指標，其上限為1，Q越接近1，說明社團結構越明顯，劃分質量越好。獲取最大模塊度，意味著社團內部節點之間的連接相對緊密，對應于聚類后同類相似性最大；各個社團之間的連接相對比較稀疏，對應于聚類后類間相似性最小。

復雜網絡社團劃分有多種典型算法，如GN算法 [13]、譜平分法 [14]和Kernighan-Lin算法 [15]等。從復雜性角度考慮，本方法選擇Newman快速算法對WWN進行聚類 [16]，時間復雜度為O(n#8226;log n)。在Newman算法中，設節點i和j間的邊權值為k，表示i和j之間有k條邊，k必須是正整數。從聚類的角度考慮，因為節點間邊的權值代表單詞間的相關度，意味著單詞之間聯系的大小，所以邊的權值為非整數是有意義的。在算法中將邊的權值由正整數擴展至正有理數。Newman算法對WWN劃分后，得到最大的模塊度值，說明網絡社團劃分即聚類的效果為最優。在單詞聚類中，算法的輸入為WWN的鄰接矩陣，輸出為單詞類。算法如下：

/*network[i][j]記錄節點i和j之間的權值；節點數目為N；節點i和j屬于不同社團，e[i][j]表示連接節點i和j的邊在所有邊中所占的比例；a[i][0]表示與第i個社團相連的邊在所有邊中的比例（包括社團內部的邊）；a[i][1]表示第i個社團內部的邊*/

輸入：WWN鄰接矩陣network[i][j]；

輸出：單詞及其類別形成的二維數組。

算法步驟：

a）初始化WWN為N個社團（每個節點為一個社團）；e[i][j]=network[i][j]/2*m（m指總邊數）；a[i][0]=k[i]/2*m（k指社團度數）。

b）依次計算有邊相連的社團合并的模塊度增量deltaQ（deltaQ=2*（e[i][j]-a[i][0]*a[j][0]））。

取max(deltaQ)時最大的兩個社團合并形成新社團，更新e[i][j]和a[i][1]分別為新社團形成后的值；

重復步驟b)，直到max(deltaQ)為負值。

c)劃分完畢后，選擇Q最大時斷開網絡（即max(deltaQ)為負值時），輸出a[i][1]及對應的單詞，得到單詞聚類結果。

3.2 服務聚類

單詞聚類完畢后，單詞類別用來指導服務的聚類，將每個服務向量與所有的單詞類別比較，加入到合適的服務類別中。定義單詞的權值為：在WWN中，與單詞所對應節點相連的所有邊的權值之和。每個單詞類別對應一個服務類別，在分類好的單詞類中取權值最大的一個或幾個單詞作為該服務類的類名。

設服務Di的自然語言描述中有n個單詞{W1，W2，…，Wn}，定義Di對應的向量Vi={tf1，tf2，…，tfn}。其中：tfn表示的是單詞Wn的權值。服務Di隸屬于某一單詞類別A（即相應的服務類別）的程度由M確定：

M=∑Wn∈AC(Wn)tfn

其中：C(Wn)代表單詞Wn在Di的自然語言描述中出現的次數。比較服務針對不同的單詞類別的M值，選取其中最大的M值，將服務歸入對應的服務類別。也可以進行軟聚類，選擇兩個或幾個M值，把服務分到多個類中。算法如下：

/*word[n]記錄單詞；wordWeight[n]記錄單詞的權值;CW表示單詞word[w]在服務D的自然語言描述中出現的次數；tfw表示的是單詞word[w]的權值wordWeight[w] */

輸入：各社團a[i][1]及對應的單詞；

輸出：類名及服務類別。

a)依次計算每個單詞i的權值wordWeight[i]=∑njnetwork[i][j]。

b)在每個單詞類別內，取max(wordWeight[i])對應的單詞word[k]作為這個單詞類對應的服務類類名。

c)對每個服務Di，依次計算M值：M=∑Wn∈AC(Wn)tfn。

d)Di的類ID =max（M[i]），類別為對應的單詞類別名。

單詞聚類中Newman快速算法的時間復雜度為O(n#8226;log n)，n為單詞數量。服務聚類時，算法使用稀疏矩陣存儲network[i][j]，矩陣的每一行都存為一個平衡二叉樹，可以降低算法復雜性，復雜度為O(n#8226;log n)。因此使用WWN的社團劃分算法進行服務聚類總的時間復雜度為O(n#8226;log n)。

4 實驗結果及評估

本算法選取德國人工智能中心（DFKI）開發的OWL-S Test Collection（OWL-S TC）作為測試集進行了實驗。目前還沒有OWL-S服務的標準測試集，OWL-S TC可以看做標準測試集的雛形。OWL-S TC至今共有五個版本，本文使用2007年11月發布的OWL-S TC version 2.2。

OWL-S TC依據OWL-S 1.1標準提供了1 007個語義Web services，絕大部分是從公共的IBM UDDI注冊中心獲取，且從WSDL轉換為OWL-S^[17]。OWL-S TC將這1 007個語義Web services手工分為七類：education、medical、food、travel、communication、economy、weapon。個別服務被手工分為兩個類，因此手工分類結果中Web services總數為1 013。本文將對這些服務進行自動聚類，并對自動聚類的結果和手工分類的結果進行比較以評價性能。

通過對OWL-S TC中1 013個Web services的自然語言描述的名詞抽取及相關處理，共有680個單詞，所形成的WWN社團劃分前后如圖3所示。聚類后，單詞共分為15個類，具體統計如表1所示。

因為3、10、12、13、14和15類單詞數過少，統計中可以忽略。采用查準率和純凈度（purity）作為聚類結果的質量指標。對于數據集D，設P表示D聚類后的一個類別中的服務集合；設L表示P所對應手工分類類別中的服務集合。P相對于L的查準率定義為

precision(p，l)=|P∩L|/P;p∈P，l∈L

在此基礎上，純凈度^[18]定義為

purity(P，L)=∑p∈P|P|/|D| maxl∈L(precision(p，l));p∈P，l∈L

純凈度是各個類查準率的加權平均值，而各類的查準率是相對于手工分類各類別的最大查準率，這兩個指標能較全面地反映聚類效果。為了測試本文基于復雜網絡社團劃分進行聚類的方法（WWNC）的有效性，用K-means算法作了比較實驗。由于K-means對輸入屬性的順序敏感，交換輸入的順序將得到不同的聚類結果，用K-means進行了多次實驗，取結果較好的兩次，分別記為K-means和K-means-2。與OWL-S TC分類的結果比較如圖4和表2所示。

WWNC聚類平均查準率為74.7%，如圖5所示，每類的查準率均比K-means的查準率高。從純凈度角度考慮，如表2所示，WWNC的純凈度為69.6%，與兩次K-means算法的結果比較也有明顯優勢。K-means兩次聚類均沒有區分開education、medical、travel三個類，基于向量空間的聚類算法如K-means等孤立考慮各屬性，處理高維度屬性的能力不足。WWNC較好地利用了屬性節點之間的相關性，利用了單詞之間的內在聯系。可以推論：服務的數量越多、單詞的數量越大，節點之間的相關性將更強，WWNC聚類算法的性能越好。

WWNC聚類結果中Education、medical兩個類別查準率相對較低，其中大部分服務被劃分到了第四類。分析這兩個類別的自然語言描述：a）Education類中手工分類的結果有瑕疵，類中服務相似性不高，如其中“beverage maxPrice physical-Quantity service”的自然語言描述為“This service informs the physical-quantity and maximum price of a given beverage item”，這個服務被聚類算法分在經濟類，從直觀上看是正確的；b）Medical類中服務數量比較少，但自然語言描述中某些單詞的相關性較高，如drug、treatment、patient、hospital、biopsy、syndrome、duration、health、physician、clinic等，盡管這些單詞強相關，但未發現同現，在單詞網絡中沒有邊互連。

WWN能夠相對完整和準確地表達單詞節點之間的聯系，突出了同類服務的相似性。由單詞節點之間的相關度計算所得的邊權值，較好地體現了單詞之間的內在聯系，提高了聚類質量。傳統的聚類算法時間復雜性大部分是O(n2)級（n為對象數目）。本文聚類方法的時間復雜度為O(n#8226;log n)（n為單詞的數目）。一種語言中單詞的數目是有限的，而服務的數量可以遠遠大于單詞的數量，因此本算法在針對大量服務的聚類中要比傳統算法快很多。

5 結束語

基于復雜網絡社團劃分的Web services聚類基本實現了對服務的自動聚類，這給WSDL至OWL-S的文件轉換節省了大量時間。同時，對大量凌亂無序的服務進行聚類，能夠將服務依內在分布劃歸不同的類別，對服務集數據的組織和管理提供了便利。利用復雜網絡社團劃分的方法進行聚類，解決了聚類對象多屬性、高維度的問題。本文以OWL-S TC為例構建了一個具體的加權單詞網絡，并基于此網絡進行社團劃分，實現了服務的聚類，其時間復雜性為O(n#8226;log n)。由于服務與單詞的內在強關聯性，聚類結果中同類服務體現了較好的相似性。算法在Web services的發現、檢索、添加以及服務發現后的結果呈現上均可直接應用。

今后的工作主要集中在三個方面：a)建立強相關單詞的示例本體，對單詞網絡模型進行優化；b)利用服務的輸入、輸出進行二次匹配，并與前面聚類算法的結果加權綜合考慮；c)建立服務與多個單詞之間的一對多映射，將一個服務分到多個類中，實現軟聚類，進一步提高聚類質量。

參考文獻:

[1]DAML services home [EB/OL]. （2006-03）. http://www. daml. org/services/owl-s/.

[2]HAN Jia-wei， KAMBER M. Data mining concepts and techniques[M]. Beijing:China Machine Press， 2001:335-336.

[3]RAGHAVAN V V，WONG S K M. A critical analysis of vector space model for information retrieval[J]. Journal of the American Society for Information Science， 1986，37(5):279-287.

[4]MacQUEEN J B.Some methods for classification and analysis of multivariate observations[C]//Proc of the 5th Berkeley Symposium on Math Statist Prob. Berkley:university of California Press，1967:281-297.

[5]HNNEBURG A， KEIM D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proc of the 4th International Conference on Knowledge Discovery and Data Mining. New York:AAAI Press， 1998:58-65.

[6]HINNEBURG A. Density-based clustering in large databases using projections and visualizations [D]. Konstanz: University of Konstanz， 2002

[7]GEORGE K， HAN E H， KUMAR V. CHAMELEON: a hierarchical clustering algorithm using dynamic modeling [J]. IEEE Computer， 1999，27(3):329-341.

[8]SLONIM N， TISHIBY N. Document clustering using word clusters via the information bottleneck method[C]//Proc of the 23rd Conference on Research and Development in Information Retrieval. New York:ACM Press， 2000:208-215.

[9]CANCHO F I， SOLE R V. The small world of human language[J]. Proc of the Roy Society of London:Biological Science， 2001，268(1482):2261-2265.

[10]MATSUO Y， OHSAWA Y， ISHIZUKA M. A document as a small world[M]. Berlin:Springer， 2001:444-448.

[11]汪小帆，李翔. 復雜網絡理論及其應用[M]. 北京：清華大學出版社，2006.

[12]李德毅， 杜鹢. 不確定性人工智能[M]. 北京：國防工業出版社，2005.

[13]GRIVAN M， NEWMAN M E J. Community structure insocial and biological networks[J].Proc of National Academy of Science， 2002，99(12):7821-7826.

[14]FIEDLER M. Algebraic connectivity of graphs [J].Czech Math J， 1973，23(28):298-305.

[15]KERNIGHAN B W， LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal， 1970，49(2):291-307.

[16]NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E Rev， 2004， 38(2):321-330.

[17]OWL-S service retrieval test collection [EB/OL].[2008-05-22].http://projects.semwebcentral.org/projects/owls-tc/.

[18]趙鵬.復雜網絡與互聯網個性化信息服務的研究[D].合肥：中國科學技術大學，2006.