黃 媛

(長(zhǎng)江工程職業(yè)技術(shù)學(xué)院，武漢 430212)

一種改進(jìn)K-Means算法的服務(wù)聚類方法

黃 媛

(長(zhǎng)江工程職業(yè)技術(shù)學(xué)院，武漢 430212)

聚類方法能夠提高Web服務(wù)檢索的能力，針對(duì)傳統(tǒng)的K-Means聚類算法聚類時(shí)間長(zhǎng)的缺陷，文中提出了一種改進(jìn)的K-Means服務(wù)聚類方法，并進(jìn)行了有效性驗(yàn)證，在利用API服務(wù)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn) ，其結(jié)果表明：改進(jìn)的K-Means服務(wù)聚類的方法降低了服務(wù)聚類的時(shí)間復(fù)雜度。

改進(jìn)的K-Means;服務(wù)；聚類；時(shí)間復(fù)雜度

隨著Web2.0技術(shù)的飛速發(fā)展，Mashup和API服務(wù)在Web開發(fā)者社區(qū)中廣為流行，并且應(yīng)用在許多開放的Web網(wǎng)站中。大量的API服務(wù)每天都在涌現(xiàn)，所以我們需要一個(gè)平臺(tái)來(lái)瀏覽這些API服務(wù)。一些在線的平臺(tái)，例如雅虎，ProgrammableWeb.com等都允許用戶發(fā)布各種API服務(wù)。即使一些非專業(yè)人士也能通過(guò)組合Web API服務(wù)或其他的Web資源創(chuàng)建一些新的Web頁(yè)面，當(dāng)前ProgrammableWeb是一個(gè)很流行的社區(qū)，它吸引了大批研究者對(duì)社區(qū)用戶行為進(jìn)行研究。

1 Web服務(wù)聚類的相關(guān)研究文獻(xiàn)

近年來(lái)，Web服務(wù)聚類作為一種服務(wù)發(fā)現(xiàn)方法是一種新穎的服務(wù)發(fā)現(xiàn)方法。Khalid等人從Web服務(wù)的WSDL文檔中提取特征，如內(nèi)容，服務(wù)名，主機(jī)名，進(jìn)行Web服務(wù)聚類[1]，把聚類過(guò)程看作是發(fā)現(xiàn)的預(yù)處理階段，希望幫助建立一個(gè)搜索引擎來(lái)爬取和聚類非語(yǔ)義的Web服務(wù)。一種個(gè)性化的交互式的標(biāo)簽推薦算法在文獻(xiàn)[2]中提出，提供了一種特殊的依賴標(biāo)簽共享的數(shù)據(jù)標(biāo)注方式。標(biāo)簽可以用圖的方式來(lái)呈現(xiàn)，其中每個(gè)節(jié)點(diǎn)是標(biāo)簽，而節(jié)點(diǎn)之間的邊反映的是同一個(gè)文檔的共享情況。Harald等人[3]提出一種利用用戶和其查詢的Web頁(yè)之間對(duì)應(yīng)的主題的相似性進(jìn)行排序的方法。一些文章也討論過(guò)Web服務(wù)的標(biāo)注。使用標(biāo)簽語(yǔ)義的方式來(lái)注釋W(xué)eb服務(wù)[4],使用結(jié)構(gòu)化協(xié)同標(biāo)簽匹配Web服務(wù)。Liu等人[5]從WSDL文檔中提取參數(shù)名，并將它們以概念來(lái)聚類，聚類結(jié)果能用來(lái)改進(jìn)Web服務(wù)搜索結(jié)果的質(zhì)量。

2 改進(jìn)的K-Means聚類算法

K-Means是數(shù)據(jù)挖掘中一個(gè)經(jīng)典的聚類算法，在大型數(shù)據(jù)集的聚類中該算法非常普及。由于標(biāo)準(zhǔn)的K-Means算法在每次迭代時(shí)需要計(jì)算每個(gè)數(shù)據(jù)對(duì)象到K個(gè)聚類中心的距離，所以在大型數(shù)據(jù)集上執(zhí)行算法時(shí)會(huì)消耗大量執(zhí)行時(shí)間。這是K-Means算法的缺點(diǎn)，下面提出一種改進(jìn)的K-Means算法。

該算法主要思想是:首先設(shè)置兩個(gè)數(shù)據(jù)集，分開保存聚類中心的標(biāo)記以及在每次迭代中所有數(shù)據(jù)對(duì)象到最近聚類的距離，這些距離還能在下次迭代中繼續(xù)使用，然后繼續(xù)計(jì)算當(dāng)前數(shù)據(jù)對(duì)象和新的聚類中心的距離，如果計(jì)算的距離小于或等于到之前聚類的距離，那么數(shù)據(jù)對(duì)象就被放到上一次迭代中的聚類中。因此無(wú)需計(jì)算該數(shù)據(jù)對(duì)象到其他k-1個(gè)聚類中心的距離，節(jié)省了計(jì)算到其余k-1個(gè)聚類中心的距離的時(shí)間。

改進(jìn)的K-Means算法描述如下：

步驟1.從數(shù)據(jù)集D中隨機(jī)選取k個(gè)數(shù)據(jù)作為初始聚類中心；

步驟2.計(jì)算每個(gè)數(shù)據(jù)di(1≤i≤n)和所有k個(gè)聚類中心cj(1≤j≤k)的歐式距離d(di,cj)，并將數(shù)據(jù)di放到最近的聚類中。

步驟3.對(duì)每個(gè)數(shù)據(jù)di，找到最近的聚類中心cj，同時(shí)將di的值賦給聚類中心j；

步驟4.將數(shù)據(jù)對(duì)象di所在的聚類中心標(biāo)記以及存儲(chǔ)數(shù)據(jù)對(duì)象di和最近的聚類之間的距離分別存儲(chǔ)在數(shù)組Cluster[ ]和Dist[ ]中，設(shè)Cluster[i] =j, j是最近聚類的標(biāo)記，又設(shè)Dist[i]=d(di,cj)，d(di,cj)是和最近的聚類中心的距離。

步驟5.對(duì)每個(gè)聚類j(1≤j≤k)，重新計(jì)算聚類中心；

步驟6.重復(fù)操作

步驟7.對(duì)每一個(gè)數(shù)據(jù)di，計(jì)算它和當(dāng)前最近的聚類之間的距離；

步驟7.1.如果它的距離小于或等于Dist[i]，數(shù)據(jù)對(duì)象就存在初始的聚類中；

步驟7.2.否則對(duì)每個(gè)聚類中心cj(1≤j≤k)來(lái)說(shuō)，計(jì)算每個(gè)數(shù)據(jù)對(duì)象和所有聚類中心的距離d(di,cj)，將數(shù)據(jù)對(duì)象di的值賦給最近的聚類中心cj，設(shè)Cluster[i]=j;Dist[i]=d(di,cj);

步驟8. 對(duì)每個(gè)聚類j(1≤j≤k)，重新計(jì)算聚類中心；

步驟9.直到滿足收斂條件；

步驟10.輸出聚類結(jié)果；

這個(gè)改進(jìn)的K-Means算法需要兩個(gè)數(shù)組Cluster [ ]和Dist [ ]存儲(chǔ)每次迭代過(guò)程產(chǎn)生的信息，以便用于下一次迭代當(dāng)中。數(shù)組Cluster[ ]存儲(chǔ)最近聚類中心的標(biāo)記，數(shù)組Dist [ ]存儲(chǔ)數(shù)據(jù)對(duì)象和最近聚類中心的距離。這些數(shù)組中的信息減少了重復(fù)計(jì)算數(shù)據(jù)對(duì)象和最近聚類中心的距離(利用公式(1))的次數(shù)，這就使得改進(jìn)的K-Means算法比標(biāo)準(zhǔn)的K-Means算法執(zhí)行速度更快，數(shù)據(jù)集越大時(shí)，算法效果愈明顯。

3 改進(jìn)K-Means算法的實(shí)證

3.1 文檔預(yù)處理

為了評(píng)價(jià)API服務(wù)聚類的性能，我們利用爬蟲軟件從ProgrammableWeb網(wǎng)站上爬取200個(gè)API服務(wù)作為實(shí)驗(yàn)的數(shù)據(jù)集，并獲得每個(gè)API服務(wù)的名稱，描述，標(biāo)簽等信息。在這個(gè)步驟中，我們對(duì)API服務(wù)做一些預(yù)處理操作，例如移除停用詞、使用詞干分析器等。

(1)提取詞語(yǔ)。將句子拆分成詞，然后提取名詞作為詞語(yǔ)特征詞。

(2)移除停用詞。使用到包括要排除的詞的停用詞列表。這個(gè)列表作用是移除不能區(qū)分主題的普通詞，如“的，地，得”等。

(3)處理詞干。使用已有的詞干算法將一個(gè)詞轉(zhuǎn)化為它的詞干或詞根的形式。

(4)選擇關(guān)鍵詞。應(yīng)用TF-IDF閾值方法來(lái)選擇文檔集的關(guān)鍵詞。

TF-IDF(term frequency-inverse document frequency)是一種用于檢索中常用的加權(quán)技術(shù)。TF-IDF是一種統(tǒng)計(jì)方法，用以評(píng)估某一個(gè)字或詞對(duì)于語(yǔ)料庫(kù)中的某個(gè)文件的重要程度。相應(yīng)的字或詞在文中出現(xiàn)得越多其重要性越高，但與其在語(yǔ)料庫(kù)中出現(xiàn)越多重要性越低。搜索引擎常應(yīng)用TF-IDF加權(quán)的各類形式度量文件與用戶查詢之間相關(guān)程度。

3.2 API服務(wù)相似性

(1)

3.3 評(píng)價(jià)指標(biāo)

選擇精度(precision)為度量指標(biāo)，在信息檢索中廣泛使用精度作為評(píng)價(jià)聚類性能的一個(gè)主要指標(biāo)。

(2)

式中，succ(ci)是正確聚類到類ci中正確的服務(wù)的數(shù)目，mispl(ci)是劃分到聚類ci中錯(cuò)誤的服務(wù)的數(shù)目。

3.4 結(jié) 果

為了評(píng)價(jià)改進(jìn)后算法的聚類性能，在3.1中的API數(shù)據(jù)集上進(jìn)行試驗(yàn)，結(jié)果如圖1、圖2所示，從圖1中看到改進(jìn)的K-Means聚類算法和標(biāo)準(zhǔn)K-Means聚類算法都將API服務(wù)被分成了5類，分別是關(guān)于藝術(shù)，交通，地圖，通信，網(wǎng)站的服務(wù)。但是每個(gè)類中的服務(wù)數(shù)目有所不同，兩算法的執(zhí)行時(shí)間也不同，前者聚類時(shí)間不到10 s，后者執(zhí)行時(shí)間超過(guò)60 s。

為了驗(yàn)證本方法的有效性，我們選擇人工分類的方法，手動(dòng)對(duì)這200個(gè)服務(wù)進(jìn)行分類，將分類結(jié)果作為聚類結(jié)果的基線，聚類結(jié)果精度如圖2所示，從圖中可以看到改進(jìn)的K-Means聚類算法聚類平均精度為53.8%，標(biāo)準(zhǔn)K-Means聚類算法聚類平均精度為41.8%，這表明改進(jìn)的K-Means聚類算法比標(biāo)準(zhǔn)的K-Means聚類算法更好地改進(jìn)了聚類的性能。

圖1 改進(jìn)和標(biāo)準(zhǔn)的K-Means聚類算法聚類結(jié)果比較

圖2 改進(jìn)和標(biāo)準(zhǔn)的K-Means聚類算法聚類精度比較

4 小 結(jié)

為了提高Web服務(wù)聚類的性能，文中提出了一種改進(jìn)的K-Means聚類算法，改進(jìn)服務(wù)聚類的性能。為了評(píng)價(jià)API服務(wù)的聚類性能，從ProgrammableWeb網(wǎng)站上爬取了200個(gè)真實(shí)的API服務(wù)進(jìn)行試驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)的K-Means聚類算法聚類精度較高，聚類時(shí)間較短，聚類效果較好。

[1] Khalid Elgazzar, Ahmed E. Hassan, Patrick Martin. Clustering WSDL documents to bootstrap the discovery of web services[A]. In Proceeding of Conference on Web Services[C]. 2009:147-154.

[2] Shengliang Xu, Shenghua Bao, Ben Fei, Zhong Su, Yong Yu. Exploring folksonomy for personalized search[A]. In Proceeding of 31st Annual International ACM SIGIR Conference on research and development in information retrieval[C]. 2008:155-162.

[3] Harald Meyer, Mathias Weske. Light-Weight Semantic Service Annotations through Tagging[A]. In Proceeding of 4thinternational conference on service-oriented computing-ICSOC[C]. 2006:465-470.

[4] Shengliang Xu, Shenghua Bao, Ben Fei, Zhong Su, Yong Yu. Exploring folksonomy for personalized search[A]. In Proceeding of 31st Annual International ACM SIGIR Conference on research and development in information retrieval[C]. 2008:155-162.

[5] Fangfang Liu, Lei Wang, Jie Yu. Context-aware similarity search of web service[A]. In Proceedings of 2012 IEEE International Conference on Information Science and Technology[C].2012:596-602.

Service Clustering Method to Improve K-Means Algorithm

HUANG Yuan

(Changjiang Institute of Technology, Wuhan 430212, China)

The clustering method can improve the retrieval ability of Web service. To the defects of long clustering time of the traditional K-Means clustering algorithm, an improved method has been introduced and verified. The experiments based on the date sets of API services show that the improved K-Means method can reduce the time complexity of the clustering service.

improved K-Means method; service; clustering; time complexity

2017-01-11

黃 媛(1983-)，女，武漢人，講師，博士，研究方向：數(shù)據(jù)挖掘、服務(wù)計(jì)算。

TP39

A

1673-0496(2017)02-0035-03

10.14079/j.cnki.cn42-1745/tv.2017.02.012