聚類技術在Web服務中的應用研究

黃媛

摘 要：通過對ProgrammableWeb在線社區進行研究，發現網站上的API服務數量龐大且含有豐富的數據信息。討論了網頁采集、數據預處理等相關技術，利用K-Means和凝聚層次聚類技術在API服務數據集上進行實驗，實驗結果表明，K-Means算法具有更好的聚類效果。

關鍵詞：聚類；Web服務；K-Means；API服務數據

DOIDOI：10.11907/rjdk.171075

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）007-0149-03

0 引言

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

1 API服務聚類

1.1 描述相似性

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

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

1.2 標簽相似性

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

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

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

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

2 聚類算法

2.1 K-Means聚類算法

K-Means是數據挖掘中的經典聚類算法[4]，在做大型數據集聚類時廣泛使用。基本的K-Means算法中，每一次迭代計算每個數據集合對象到K個聚類中心的距離。

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

2.2 凝聚層次聚類算法

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

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

3 實驗

3.1 文檔預處理

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

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

（2）移除停用詞。根據已經構建好的停用詞列表移除停用詞。列表作用是移除不能區分主題的普通詞，如的、地、得等。

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

（4）選擇關鍵詞。根據TF-IDF閾值方法獲取能表示文檔集的關鍵詞。

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

3.2 評價指標

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

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

3.3 結果

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

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

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

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

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

4 結語

本文提出一種利用標注數據改進服務聚類性能的方法。在DAT方法中，計算了API服務間描述層和標簽層相似性，然后利用描述層和標簽層的組合相似性對API服務進行聚類。為了評價API服務的聚類性能，從ProgrammableWeb網站抓取了200個真實的API服務數據，采用K-Means和hierarchical算法進行聚類，實驗結果表明DAT方法更好地改進了聚類性能。

參考文獻：

[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]黃媛，李兵. 基于標簽推薦的Mashup服務聚類[J].計算機科學，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