黃媛

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

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

DOIDOI：10.11907/rjdk.171075

中圖分類號：TP319

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

0 引言

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

1 API服務(wù)聚類

1.1 描述相似性

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

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

1.2 標(biāo)簽相似性

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

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

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

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]，如果兩個服務(wù)的描述和標(biāo)簽相同即是1，如果兩個服務(wù)的描述和標(biāo)簽完全不同則是0。

2 聚類算法

2.1 K-Means聚類算法

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

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

2.2 凝聚層次聚類算法

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

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

3 實驗

3.1 文檔預(yù)處理

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

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

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

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

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

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

3.2 評價指標(biāo)

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

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

3.3 結(jié)果

本文對照兩種計算API相似性方法：

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

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

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

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

4 結(jié)語

本文提出一種利用標(biāo)注數(shù)據(jù)改進(jìn)服務(wù)聚類性能的方法。在DAT方法中，計算了API服務(wù)間描述層和標(biāo)簽層相似性，然后利用描述層和標(biāo)簽層的組合相似性對API服務(wù)進(jìn)行聚類。為了評價API服務(wù)的聚類性能，從ProgrammableWeb網(wǎng)站抓取了200個真實的API服務(wù)數(shù)據(jù)，采用K-Means和hierarchical算法進(jì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ī)科學(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