聚類技術(shù)在Web服務(wù)中的應(yīng)用研究

黃媛

摘 要：通過(guò)對(duì)ProgrammableWeb在線社區(qū)進(jìn)行研究，發(fā)現(xiàn)網(wǎng)站上的API服務(wù)數(shù)量龐大且含有豐富的數(shù)據(jù)信息。討論了網(wǎng)頁(yè)采集、數(shù)據(jù)預(yù)處理等相關(guān)技術(shù)，利用K-Means和凝聚層次聚類技術(shù)在API服務(wù)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，K-Means算法具有更好的聚類效果。

關(guān)鍵詞：聚類；Web服務(wù)；K-Means；API服務(wù)數(shù)據(jù)

DOIDOI：10.11907/rjdk.171075

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）007-0149-03

0 引言

隨著Web2.0技術(shù)的飛速發(fā)展，Mashup和API服務(wù)在Web開(kāi)發(fā)者社區(qū)廣為流行，并應(yīng)用在許多開(kāi)放的Web網(wǎng)站中。企業(yè)Web應(yīng)用中Mashup與其它應(yīng)用區(qū)別很大，常常不能重復(fù)使用或者沒(méi)有Web API，人們不得不為這些應(yīng)用去創(chuàng)建大量Web API。每天涌現(xiàn)的大量API服務(wù)需要一個(gè)平臺(tái)來(lái)瀏覽 [1]。一些在線平臺(tái)，例如雅虎、ProgrammableWeb.com等都允許用戶發(fā)布各種API服務(wù)，一些非專業(yè)人士也能通過(guò)組合Web API服務(wù)或其它Web資源創(chuàng)建新的Web頁(yè)面。ProgrammableWeb現(xiàn)在很流行，吸引了研究者的關(guān)注，推動(dòng)了社區(qū)用戶行為的研究[2]。目前網(wǎng)站已經(jīng)有6 730個(gè)Mashup和6 783個(gè)開(kāi)放的API服務(wù)，開(kāi)發(fā)者不用測(cè)試就能將API服務(wù)結(jié)合起來(lái)。和傳統(tǒng)的Web開(kāi)發(fā)相比，Mashup越來(lái)越簡(jiǎn)單和流行，因?yàn)殚_(kāi)發(fā)者不用測(cè)試和移植內(nèi)部的Web應(yīng)用就能使用這些數(shù)據(jù)，非技術(shù)人員也能通過(guò)在線社區(qū)快速集成已有的應(yīng)用。

1 API服務(wù)聚類

1.1 描述相似性

API服務(wù)經(jīng)過(guò)文檔預(yù)處理[3]后，使用詞語(yǔ)向量集表示。向量之間的相似性表示兩個(gè)文本之間的相似性，可用向量之間的夾角余弦值表示，也叫作余弦相似性，這是目前在信息檢索和聚類方法中度量文本相似性的最常用方法。設(shè)定文檔ta→和tb→，文檔間的余弦相似性計(jì)算公式如下：

ta→和tb→是詞集T={t1，...，tm}上的m維向量，每一維都代表一個(gè)詞在文檔中的權(quán)重，且為非負(fù)，余弦相似度非負(fù)并且屬于[0，1]。

1.2 標(biāo)簽相似性

API服務(wù)的標(biāo)注數(shù)據(jù)能起到描述API服務(wù)或是提供文本或語(yǔ)義信息的作用。本文根據(jù)標(biāo)注數(shù)據(jù)的相似性，提出了改進(jìn)API服務(wù)聚類性能的方法。給定一個(gè)包含3個(gè)標(biāo)簽t1，t2，t3的API服務(wù)，si的標(biāo)簽集Ti={t1，t2，t3}。通過(guò)Jaccard系數(shù)方法計(jì)算標(biāo)簽之間的相似性：

Simtag（si，sj）=|Ti∩Tj||Ti∪Tj|（2）其中|Ti∩Tj|是同時(shí)標(biāo)注和標(biāo)簽數(shù)目，|Ti∪Tj|是Ti和Tj的并集。

根據(jù)以上公式，API服務(wù)si和sj的相似性sim（si，sj）計(jì)算如下：

sim（si，sj）=βsimdes（si，sj）+（1-β）simtag（si，sj）（3）其中，β是描述層相似性權(quán)值，1-β是標(biāo)簽層相似性權(quán)值，simdes（si，sj）是描述層相似性，simtag（si，sj）是標(biāo)簽層相似性，β取值范圍是[0，1]，如果兩個(gè)服務(wù)的描述和標(biāo)簽相同即是1，如果兩個(gè)服務(wù)的描述和標(biāo)簽完全不同則是0。

2 聚類算法

2.1 K-Means聚類算法

K-Means是數(shù)據(jù)挖掘中的經(jīng)典聚類算法[4]，在做大型數(shù)據(jù)集聚類時(shí)廣泛使用。基本的K-Means算法中，每一次迭代計(jì)算每個(gè)數(shù)據(jù)集合對(duì)象到K個(gè)聚類中心的距離。

K-Means算法步驟如下：①?gòu)臄?shù)據(jù)集D中，隨機(jī)抽取其中的k個(gè)對(duì)象作為初始聚類中心；②計(jì)算每個(gè)數(shù)據(jù)對(duì)象di（1≤i≤n）和所有k個(gè)聚類中心cj（1≤j≤k）的歐式距離d（di，cj），并將數(shù)據(jù)對(duì)象di放到最近的聚類中；③對(duì)每個(gè)數(shù)據(jù)對(duì)象di找到最近的聚類中心cj，同時(shí)將di的值賦給聚類中心j；④將數(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）是最近的聚類中心距離；⑤對(duì)每個(gè)聚類j（1≤j≤k），重新計(jì)算聚類中心；⑥重復(fù)操作；⑦對(duì)每個(gè)數(shù)據(jù)對(duì)象di計(jì)算它和當(dāng)前最近的聚類之間的距離。如果距離小于或等于Dist[i]，數(shù)據(jù)對(duì)象就存在初始的聚類中，否則對(duì)每個(gè)聚類中心cj（1≤j≤k）計(jì)算每個(gè)數(shù)據(jù)對(duì)象和所有聚類中心的距離d（di，cj），將數(shù)據(jù)對(duì)象di值賦給最近的聚類中心cj，設(shè)Cluster[i]=j，Dist[i]=d（di，cj）；⑧對(duì)每個(gè)聚類j（1≤j≤k）重新計(jì)算聚類中心；⑨直到滿足收斂條件；B10輸出聚類結(jié)果。

2.2 凝聚層次聚類算法

本文采用凝聚層次聚類算法[5] （以下簡(jiǎn)稱Hierarchical算法）和基本的K-Means算法相比較。API服務(wù)用權(quán)值向量用R表示，相似性閾值初始值設(shè)為1，經(jīng)過(guò)多次迭代后閾值慢慢減小直到為0。如果相似性指標(biāo)滿足閾值，標(biāo)簽就聚合在一起。在Hierarchical算法中，劃分系數(shù)起著至關(guān)重要的作用，它定義了層次結(jié)構(gòu)被劃分成單個(gè)簇的層次數(shù)目。算法輸出為API服務(wù)聚類的集合。

算法步驟：①將每個(gè)API服務(wù)單獨(dú)作為一個(gè)聚類，將這些API服務(wù)作為聚類的種子；②將所有API服務(wù)放在一個(gè)層次簇中?；诜?wù)之間的相似性，見(jiàn)公式（3），API服務(wù)簇集聚在一起，首先是相似度最高的API服務(wù)聚集在一起，然后是相似度略低的聚集在一起，結(jié)果是一個(gè)包含所有API服務(wù)的樹(shù)形結(jié)構(gòu)。聚合簇：滿足當(dāng)前相似性閾值的簇放在一起，有許多方式?jīng)Q定簇之間的距離：?jiǎn)芜B接、最大連接、平均連接等。文中采用簇的質(zhì)心計(jì)算簇之間的距離。降低相似性：相似性閾值逐漸降低，重復(fù)上個(gè)步驟直到所有簇聚合在一起。將樹(shù)剪成簇：層次樹(shù)通過(guò)剪枝分割為多個(gè)簇；③調(diào)整參數(shù)，控制層次聚類的粒度，決定層次樹(shù)的層次數(shù)目，參數(shù)最優(yōu)時(shí)能將API服務(wù)慢慢聚合，同時(shí)捕捉到單個(gè)簇之間的概念關(guān)系。聚合速度太快會(huì)失去重要的API服務(wù)依賴性。endprint

3 實(shí)驗(yàn)

3.1 文檔預(yù)處理

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

（1）提取詞語(yǔ)。將語(yǔ)句拆分成詞語(yǔ)，構(gòu)建詞語(yǔ)集合，然后從中提取名詞作為詞語(yǔ)的特征詞。

（2）移除停用詞。根據(jù)已經(jīng)構(gòu)建好的停用詞列表移除停用詞。列表作用是移除不能區(qū)分主題的普通詞，如的、地、得等。

（3）處理詞干。使用詞干算法將一個(gè)詞以詞干或詞根的形式表現(xiàn)。

（4）選擇關(guān)鍵詞。根據(jù)TF-IDF閾值方法獲取能表示文檔集的關(guān)鍵詞。

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

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

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

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

3.3 結(jié)果

本文對(duì)照兩種計(jì)算API相似性方法：

（1）D（description）：API服務(wù)的相似性根據(jù)API服務(wù)的描述文本相似性來(lái)計(jì)算。

（2）DAT（description and tag）：根據(jù)API服務(wù)描述文本的相似性和標(biāo)簽之間的相似性，組合計(jì)算API 服務(wù)的相似性（利用公式（3））。

本文分別用K-Means聚類方法和Hierarchical方法，比較兩種計(jì)算API服務(wù)相似性的方法。從圖1、圖2可以看出，利用K-Means和Hierarchical方法聚類結(jié)果為5類，分別是關(guān)于藝術(shù)、交通、地圖、通信、網(wǎng)站的服務(wù)，但是每個(gè)類中的服務(wù)數(shù)目有所不同。實(shí)驗(yàn)中K-Means算法的聚類時(shí)間較短，約為10秒，而Hierarchical方法聚類時(shí)間約為1分鐘，使用K-Means算法的聚類時(shí)間較短。

從圖3可以看出，K-Means算法利用D方法的聚類平均精度為59%，而利用DAT方法的聚類平均精度為79%，高于D方法的聚類平均精度。Hierarchical算法中利用D方法的聚類平均精度為52%，而利用DAT方法的聚類平均精度為73%，同樣高于D方法的聚類平均精度。結(jié)果表明K-Means算法的聚類精度高于Hierarchical算法的聚類精度，利用DAT方法對(duì)API服務(wù)聚類效果更好。

4 結(jié)語(yǔ)

本文提出一種利用標(biāo)注數(shù)據(jù)改進(jìn)服務(wù)聚類性能的方法。在DAT方法中，計(jì)算了API服務(wù)間描述層和標(biāo)簽層相似性，然后利用描述層和標(biāo)簽層的組合相似性對(duì)API服務(wù)進(jìn)行聚類。為了評(píng)價(jià)API服務(wù)的聚類性能，從ProgrammableWeb網(wǎng)站抓取了200個(gè)真實(shí)的API服務(wù)數(shù)據(jù)，采用K-Means和hierarchical算法進(jìn)行聚類，實(shí)驗(yàn)結(jié)果表明DAT方法更好地改進(jìn)了聚類性能。

參考文獻(xiàn)：

[1]MALIHE DANESH， HOSSEIN SHIRGAHI. Text document clustering using semantic neighbors[J]. Journal of software Engineering， 2011， 5（4）：136-144.

[2]G ZHENG， A BOUGUETTAYA.Service mining on the web[J]. IEEE Transactions on Services Computing，2009， 2（1）：65-78.

[3]黃媛，李兵. 基于標(biāo)簽推薦的Mashup服務(wù)聚類[J].計(jì)算機(jī)科學(xué)，2013，40（2）：167-171.

[4]SU TING， DY J. A deterministic method for initializing K-means clustering[C].Tools with Artificial Intelligence， ICTAI，2004.

[5]HELENA AIDOS ， ANA FRED. Hierarchical clustering with high order dissimilarities[J]. Machine Learning and Data Mining in Pattern Recognition，2001.endprint