黃媛
摘 要:通過(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