利用貓群優(yōu)化算法增強Web服務(wù)發(fā)現(xiàn)的研究

王繼魁

(吉林師范大學 計算機學院，吉林 四平 136000)

Web服務(wù)是一種基于客戶端和服務(wù)器端的使用標準的網(wǎng)絡(luò)通信協(xié)議HTTP或HTTPS進行通信的應用程序.Web服務(wù)架構(gòu)的組件有服務(wù)提供者、服務(wù)消費者和服務(wù)代理規(guī)范標準(如通用描述、發(fā)現(xiàn)與集成UDDI[1](Universal Description Discovery and Integration).在UDDI機制的規(guī)范下，特定行為的Web服務(wù)可用Web服務(wù)描述語言(WSDL)描述其功能和用途.傳統(tǒng)的針對需求查找相關(guān)Web服務(wù)的方法都是基于服務(wù)名稱或自然語言描述的，可遺憾的是絕大多數(shù)的Web服務(wù)不能夠被自然語言清晰準確的表述.為了克服上述限制，在WSDL語言中應用文本挖掘技術(shù)可以識別出描述所需Web服務(wù)功能的組件.使用這些功能獲取相關(guān)信息后，可以對WSDL進行聚類，以便在服務(wù)發(fā)現(xiàn)和選擇過程中縮小搜索空間，提高搜索效率.

對于文檔的聚類，聚類算法的選擇是至關(guān)重要的.傳統(tǒng)的算法是K-means、Hierarchical Agglomerative、Suffix Tree等.目前流行的基于群體智能的聚類算法：蟻群優(yōu)化算法(ACO)，粒子群優(yōu)化算法(PSO)、遺傳算法(GA)等.本文采用一種新穎的貓群優(yōu)化算法[2]來進行Web服務(wù)的聚類.貓群優(yōu)化算法是模擬自然界中貓的社會習性和覓食形為的一種算法.本文采用自適應的貓群優(yōu)化算法來對Web服務(wù)集合進行聚類分組，然后將此算法的聚類精度與傳統(tǒng)的K-means[3]聚類算法的精度做比較，給出實驗結(jié)果.

1 自然語言處理

解決本文問題的關(guān)鍵在于如何提取Web服務(wù)的功能性信息，并使用這些信息對指定的需求的Web服務(wù)進行分類.首先，使用自然語言處理NLP技術(shù)對WSDL文檔進行預處理，比如去除stop-word等，用來獲取自然語言中的主干作為分析的屬性.然后，使用NLP中的TF-IDF[4](Term Frequency-Inverse Document Frequency)技術(shù)，使用歐幾里德距離計算出WSDL文檔之間相近性和差異度.

本文使用的WSDL文檔數(shù)據(jù)集來自于OWLS-TC4[5]，選取其中的虹膜、眼鏡、大豆、紅酒數(shù)據(jù)作為測試對象.對文檔內(nèi)容聚類計算出相似度的值后，為分別應用K-means算法和貓群優(yōu)化算法，對得出的結(jié)果進行比較.

2 K-means聚類

K-means算法[6,7]中，要形成的簇的數(shù)量由k值給出.隨機選擇k個文檔作為聚類中心，通過計算中心和文檔之間的歐幾里德距離[8]，將所有文檔分配到最近的中心.找到每個簇中所有文檔的均值，將值最小的文檔作為新簇的中心.最終，根據(jù)公式(1)計算的歐幾里德距離重新分配文檔，并且繼續(xù)該過程直到不再能重新分配，即已經(jīng)達到穩(wěn)定的聚類.

(1)

3 貓群聚類

雖然貓的大多數(shù)時間在休息，但它對所在環(huán)境和移動的物體有著高度的警覺性和好奇心.這樣的形行特征能幫助貓發(fā)現(xiàn)獵物并捕捉獵物.相對于休息時間，貓花費較少的時間去追逐獵物以節(jié)省體能.受這種狩獵模式的啟發(fā)，貓群優(yōu)化算法(CSO)可分為兩種模式：貓在休息時的“搜索模式”和在追逐獵物時的“追蹤模式”.在CSO中，創(chuàng)建一群貓并另它們隨機分布于M維度的解空間中，每只貓代表一個解決方案.貓群根據(jù)狀態(tài)自然的被分為兩組，第一組的貓正在休息并密切關(guān)注周圍環(huán)境，即搜索模式；第二組的貓?zhí)幱谝苿訝顟B(tài)并追逐獵物，即追蹤模式.這兩種模式的融合有助于CSO算法在M維度的解空間中得出最佳的解決方案.由于貓在追蹤模式中花費的時間較少，在追蹤模式組中的貓的數(shù)量應該較少.在把貓分類為兩種模式后，將提供新的位置和適應度函數(shù)，將最佳解決方案的貓篩選出來，重復以上步驟直到滿足終止條件.

CSO算法過程可分為以下5步：

1．創(chuàng)建群體中貓的總數(shù)并把它們分散到M維的解空間Xi,d中，同時為每只貓隨機分配一個在最大速度區(qū)間內(nèi)的一個初速度vi,d.

2．根據(jù)兩種模式的混合比MR，為每只貓設(shè)置一個標志，將它們分類為搜索模式或跟蹤模式.

3．使用最佳適應度函數(shù)保存每只貓的適應度的值，并對其進行評估.位置最好的貓(Xbest)代表目前最佳的解決方案.

4．根據(jù)貓的標志，讓貓在搜索模式和跟蹤模式間切換.

5．若終止條件被滿足，則算法結(jié)束，否則重復2至5步.

3.1 搜索模式

要描述貓的搜索行為，需要使用4個參數(shù)：搜索存儲池(SMP)、相應維度搜索范圍(SRD)、可變維度總數(shù)(CDC)、自身位置考量(SPC).SMP表示進入搜索模式的貓的總數(shù)；SDR記錄了貓所在維度的舊值與新值的變化范圍；CDC表示有多少個維度發(fā)生了變化；SPC是布爾變量，它表示貓的當前位置是否可作為移動的候選位置.SPC的值不能影響SMP的值.

搜索過挰如下：

1．遍歷每一只貓確定SMP數(shù)量.如果當前貓的SPC值為true，則SMP值減1，并記錄當前貓的位置信息.

2．針對上一步記錄的貓，根據(jù)CDC的值使用以下公式(2)計算其新位置.

xcn=(1±SRD×R)×XC

(2)

其中XC為貓的當前位置，XCN為貓的新位置，R為0-1間的隨機數(shù)

3．計算貓的新位置適應度值FS.若所有適應度值FS都相等，將所有侯選點的備選概率設(shè)置為1，否則使用公式(3)來計算每一個侯選點的備選概率.

(3)

其中，Pi是第i只侯選貓的概率，F(xiàn)Si第i只侯選貓的適應度值，F(xiàn)Smax和FSmin適應度的最大值和最小值.

3.2 跟蹤模式

跟蹤模式激發(fā)貓去捕捉獵物.當貓在搜索模式中發(fā)現(xiàn)獵物后，貓可以根據(jù)獵物的位置及其速度決定自身的移動速度和方向.在CSO中，貓k在維度d上的速度由公式(4)計算：

Vk,d=Vk,d+r1×c1(Xbest,d-Xk,d)

(4)

其中，vk,d為貓在維度d上的速度，Xbest,d為最優(yōu)解的貓的位置，Xk,d為貓k的位置，c1為常量，r1為0～1間的隨機數(shù).

貓k的最新位置可由公式(5)計算：

Xk,d,new=Xk,d,old+Vk,d

(5)

其中，Xk,d,new為貓k在維度d上的新位置，Xk,d,old為貓k在維度d上的當前位置.

4 實驗結(jié)果分析

本文實驗使用一些常用標準數(shù)據(jù)集，同時也采了WSDL數(shù)據(jù)集，WSDL文檔數(shù)據(jù)集源自于OWLS-TC4.聚類的精確度使用公式(6)來計算：

(6)

其中，k表示聚類的個數(shù)，j表示分類的個數(shù).在WSDL數(shù)據(jù)集中，為提高運算精度，采用了一些特定的領(lǐng)域，如通信、經(jīng)濟、教育、食品、地理、醫(yī)藥、模擬、旅行及武器.實驗結(jié)果及對比分析如表1.可以看到相對于K-means算法，CSO算法在各個數(shù)據(jù)集上的計算精度都有所提高.

表1 k-means算法和CSO算法在各數(shù)據(jù)集的聚類精度

5 結(jié) 論

本文提出一種分類Web服務(wù)以增強服務(wù)發(fā)現(xiàn)的方法.為對Web服務(wù)進行聚類，應用了K-means算法和貓群優(yōu)化算法CSO，并比較了兩種算法在標準數(shù)據(jù)集和WSDL數(shù)據(jù)集上性能.結(jié)果表明，CSO明顯優(yōu)于K-means，在CSO的跟蹤模式下，聚類中心隨機變化可以檢測出更好的聚類中心.我們將進一步擴展所提出的聚類算法，優(yōu)化Web服務(wù)的實時搜索精度，增強Web服務(wù)發(fā)現(xiàn)的時間和精度等性能.