王繼魁

(吉林師范大學(xué) 計(jì)算機(jī)學(xué)院，吉林 四平 136000)

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

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

1 自然語言處理

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

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

2 K-means聚類

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

(1)

3 貓群聚類

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

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

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

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

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

4．根據(jù)貓的標(biāo)志，讓貓?jiān)谒阉髂Ｊ胶透櫮Ｊ介g切換.

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

3.1 搜索模式

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

搜索過挰如下：

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

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

xcn=(1±SRD×R)×XC

(2)

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

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

(3)

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

3.2 跟蹤模式

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

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

(4)

其中，vk,d為貓?jiān)诰S度d上的速度，Xbest,d為最優(yōu)解的貓的位置，Xk,d為貓k的位置，c1為常量，r1為0～1間的隨機(jī)數(shù).

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

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

(5)

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

4 實(shí)驗(yàn)結(jié)果分析

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

(6)

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

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

5 結(jié) 論

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