利用關聯規則挖掘的Web API組合模式發現

夏艷敏,唐 兵,唐明董,2,曹步清,喬 帥

1(湖南科技大學 計算機科學與工程學院,湖南 湘潭 411201) 2(廣東外語外貿大學 信息科學與技術學院,廣州 510006)E-mail:btang@hnust.edu.cn

1 引 言

在API經濟模式[1]的推動下,越來越多的企業紛紛以Web API的形式在互聯網上發布數據或服務以實現商業增值.通過有效組合不同功能的Web API,可以開發出功能強大、有創意的Web應用,這成為了一種非常流行的軟件開發方式[2].然而,盡管現實中通過組合Web API開發軟件的方式越來越普遍,但是對于API組合中所蘊含的規律和模式仍然缺乏認識.如何根據API組合模式和API之間的關聯關系幫助開發者快速地從眾多的Web API中挑選合適的API去構建新的應用成為了一種重要的研究問題.目前,盡管有些工作已經調研了Web API之間的關系,但對于Web API 組合模式的研究還很少見.

近年來,標簽在對網絡資源進行管理和檢索方面取得了巨大的發展,互聯網上的各種內容都被標注了標簽[3,4].這些標簽體現了對標注資源的功能概括和描述,能夠方便用戶更好地理解、分類和檢索相關資源.由于Web API的標簽代表著它自身的功能、用途等屬性,因此,可以將Web API的標簽類比成關聯規則挖掘技術[5]的“購物籃分析”中的商品并結合Mashup中的Web API組合關系來發現API之間的關聯關系即API的標簽關聯規則.這些標簽關聯規則可以體現出哪些功能屬性的Web API經常被組合在一起構成Web應用,能夠在一定程度上反映出Web API的組合模式.

挖掘標簽關聯規則能夠更好地發現標簽之間的潛在關系[6-8].Fernandez等人[9]基于標簽云之間的相似性來建立Web服務之間的關聯規則.Wang等人[10]結合Web API和標簽發現了Mashup用戶的行為模式.Goarany等人[11]得到了Web API的二項集標簽關聯規則,并用這些規則來預測有趣的Mashup模式.聶規劃等人[12]運用Apriori算法挖掘出了基于用戶行為的Web服務組合關聯規則.Ni等人[13]使用RuleTree算法得到Web API之間的正負標簽關聯規則為Mashup推薦Web API.Tang等人[14]基于Web服務的關聯關系和它們的標簽共現關系構建了一個三層的Web服務網絡視圖模型.但是上述工作都沒有考慮標簽用詞的不規范,形式不統一和同義詞問題帶來的影響,部分工作只考慮了標簽的二項集,并且缺少對挖掘結果的真實評估.

本文提出了一種基于關聯規則挖掘的WACP方法來發現Web API的組合模式.該方法利用了Web API上代表功能屬性的標簽以及歷史的Web API組合關系,先將Web API的標簽結合Stanford CoreNLP(1)Stanford CoreNLP, https://stanfordnlp.github.io/CoreNLP/進行詞形還原,再結合WordNet(2)WordNet, https://wordnet.princeton.edu/對標簽進行了同義詞統一等處理,然后使用基于FP-growth[15]的Web API標簽關聯規則挖掘算法對Web API之間的標簽進行挖掘得到了具有強關聯性的Web API標簽關聯規則.這些具有強關聯性的Web API標簽關聯規則在一定程度上反映了Web API的組合模式.這些API組合模式可以幫助開發者快速、準確地從眾多的Web API中選擇合適的Web API組合構成新的Web應用以滿足多樣化的功能需求.WACP方法不僅可以挖掘頻繁二項集,并且能夠得到所有項集的Web API組合模式.通過使用ProgrammableWeb(3)ProgrammableWeb, https://www.programmableweb.com/的真實數據集進行實驗比較與分析,結果表明WACP方法相比于其它方法在查準率、查全率和F值等指標上都有所提高.

本文的組織結構如下:第1節介紹Web API組合模式的背景和相關工作;第2節詳細講述Web API組合模式挖掘過程及相關算法;第3節為實驗結果與分析;第4節對全文內容進行總結,并展望了下一步的工作.

2 Web API組合模式挖掘

本文提出了一種WACP方法來挖掘Web API組合模式,WACP的功能結構如圖1所示,它主要包括4個功能模塊:

1)數據提取:從ProgrammableWeb上爬取數據集,從數據集中提取實驗所需要的Web API名稱、標簽和Mashup名稱、Web API組合記錄等信息.

2)Web API標簽處理:將Web API標簽進行去除無意義詞、詞形還原、同義詞統一等處理,提高標簽的無異義性和準確性.結合API標簽以及Mashup中的API組合記錄生成Web API組合標簽集.

3)Web API標簽關聯規則挖掘:根據Web API組合的標簽集,結合基于FP-growth的Web API標簽關聯規則挖掘算法來挖掘具有強關聯性的Web API標簽關聯規則.

圖1 WACP的功能結構Fig.1 Framework of WACP

4)獲取Web API組合模式:將具有強關聯性的Web API標簽關聯規則中的無意義規則進行過濾得到Web API組合模式,這些模式能夠準確反映出Web API之間的功能關聯關系.

2.1 數據提取

該過程主要是從ProgrammableWeb中提取實驗所需要的Web API的標簽、歷史Web API組合記錄等信息.Web API、Mashup和tag的關聯關系如圖2所示.

2.2 數據預處理

為了獲得高質量的數據,減少實驗誤差,提高Web API組合模式的準確性,本文將Web API的標簽進行了以下處理:

1)去除無意義詞.在數據處理過程中發現Web API的標簽中存在一些無實際意義的單詞,例如不規則長字符串(如 referencemusicmusicbrainz).因此,本文定義了一個動態無意義詞表,用于去掉數據集中無實際意義的詞.

圖2 Mashup,Web API,Tag元素關聯圖Fig.2 Relationships among web APIs,mashups and tags

2)詞形還原.Web API的標簽單詞存在許多不同的形態,如ing、ed等.這些單詞的不同形態會造成挖掘出現僅詞性不同的、具有完全相同意義的標簽關聯規則,如“blog→media”和“blogging→media”.為了使挖掘所得的標簽關聯規則結果更為準確,需要將標簽單詞還原成一般形式并去重.本文結合Stanford CoreNLP工具實現對標簽的詞形還原.

3)同義詞統一.在數據分析過程中發現Web API標簽中存在許多意思相同或相近的標簽,如bike和bicycle、phone和telephone等.由于不同開發者有不同的描述習慣,對同一事物的描述也有可能采用不同的單詞,從而會導致開發者在定義Web API時可能使用不同標簽來表達同一含義.而這種同義詞情況會產生許多功能類似的標簽關聯規則,如“telephone→webhook”和“phone→webhook”、“place→bicycle”和“place→bike”.Web API標簽中的同義詞會影響Web API組合模式的準確度和可靠性.本文結合WordNet對數據集中的標簽進行了同義詞統一處理,更能提升Web API組合模式的可靠性.

將處理后的Web API標簽以及歷史API組合信息相結合,得到所有Web API組合的標簽集,以進行接下來的Web API標簽關聯規則的挖掘.

2.3 Web API標簽關聯規則挖掘

關聯規則挖掘技術[5]通常用于描述兩個或多個事物之間存在的某種潛在的關聯關系,下面是它的相關定義:

定義1.設L={l1,l2,…,lm}是項的集合,I是數據庫事務的集合,每個事務T是一個非空項集,T?L.設X是一個項集,事務T包含X,X?L,Y?L,X≠?,Y≠?,X∩Y=?.關聯規則是在I中成立的形如X→Y的蘊涵式.

定義2.令num(I)表示數據庫事務I的總數,num(X∪Y)表示I中包含X∪Y事務的個數,關聯規則X→Y的支持度的計算公式為:

(1)

定義3.關聯規則X→Y的置信度指事務集中包含X事務中包含Y事務所占的百分比,計算公式為:

(2)

判斷一個關聯規則是否有用和準確,即看它的支持度、置信度是否滿足最小支持度、最小置信度閾值,如果大于閾值則為有用的、正確的規則,否則為無用的規則.

本文提出一種“基于FP-growth的Web API標簽關聯規則挖掘算法”用于挖掘形如“[tagi1,tagi2,…,tagin]→tagx”且具有強關聯性的Web API標簽關聯規則,其中{tagi1,tagi2,…,tagin,tagx}?Tapi,Tapi為Web API組合的標簽集合.該算法一共分為3個步驟:1、構建FP-tree;2、挖掘FP-tree得到標簽頻繁項集;3、挖掘Web API標簽強關聯規則.

1)構建FP-tree.根據Web API組合標簽事務集,構建Web API組合標簽的FP-tree.該過程算法如下:

步驟1.構建FP-tree

Imput:Web API 組合標簽事務集W.

Output:FP-tree.

1)掃描W一次,收集標簽頻繁項的集合B,將B按照支持度計數降序排序得到頻繁項列表Lfreq.

2)創建FP-tree的根節點“Null”,將W中的每個事務Trans執行以下2個步驟:

a)得到Trans中的所有標簽頻繁項,并按照Lfreq進行排序.

b)設排序后Trans的頻繁項列表為[t|T],其中,t是頻繁項中的第一個標簽,T是頻繁項中剩余的標簽.如果存在結點F有子結點M,使得結點M的標簽等于t標簽,那么結點M的數目加1;否則創建一個新結點N并計數為1,鏈接到它的父結點F.

3)遞歸操作第2步,直到將W中的所有事務都添加到FP-tree中.

2)挖掘FP-tree得到標簽頻繁項集.根據構建的FP-tree,調用FP-growth函數得到Web API標簽頻繁項集.該過程算法如下:

步驟2.挖掘FP-tree得到標簽頻繁項集

Imput:FP-tree,最小支持度計數min_sup.

Output:Web API標簽頻繁項集.

1)挖掘FP-tree通過調用FP-growth(FP-tree,Null)實現.

1.ProcedureFP-growth(Tree,α):

2.ifTree包含路徑Pthen

3.for路徑P中結點的每個組合(記作β)do

4. 產生項集β∪α,支持度計數等于β中結點的min_sup

5.endfor

6.else

7.forFP-tree的頭表中的每個標簽aido

8. 產生項集β=ai∪α,支持度計數等于ai的支持度計數

9. 構造β的條件FP-treeTreeβ

10. ifTreeβ≠?then

11. 調用FP-growth(Treeβ,β)

12.endif

13.endfor

14.endif

2)根據FP-tree得到所有的Web API標簽頻繁項集以及這些項集對應的支持度計數.

3)挖掘Web API標簽強關聯規則.由Web API標簽頻繁項集生成Web API標簽強關聯規則.該過程算法如下:

步驟3.挖掘Web API標簽強關聯規則

Imput:Web API標簽頻繁項集,最小置信度min_sup.

Output:Web API標簽關聯規則.

1)定義標簽關聯規則組成元素,關聯規則前項用“condition”表示,后項用“result”表示,關聯規則的形式為“condition→result”.

2)對于每個滿足min_sup的標簽頻繁項集Item生成對應的標簽關聯規則,過程如下:

1.FunctionListTagRuleMining(Item):

2.tagrules←?,i←0

3.ifItem≠?then

4.whilei

5.result←Item.get(i)

6.condition←condition∪Item.subList(0,i)

7.condition←condition∪Item.subList(i+1,Item.size)

8. 產生規則 “condition→result”并將該規則放入tagrules中

9.i++

10.endwhile

11.endif

12.返回的tagrules即為由標簽頻繁項集Item生成的標簽關聯規則.

3)得到所有形如“condition→result”的Web API標簽關聯規則.

通過設置min_conf閾值,得到滿足min_conf即具有強關聯性的所有Web API標簽關聯規則.

2.4 獲取Web API組合模式

在得到的形如[tagi1,tagi2,…,tagin]→tagx的所有Web API標簽強關聯規則中,如果tagi1,tagi2,…,tagin和tagx是屬于同一個Web API中的標簽,則需要過濾掉這類規則.因為這樣的規則并不能反映Web API之間的功能關聯關系,這些來自于同一個Web API的標簽僅僅只是一種相同或相似概念來描述相同的API資源.獲取Web API組合模式的過程如下所示:

1.得到所有Web API的自身標簽集,并新建Web API標簽關聯規則過濾列表filterRule.

2.將Web API的自身標簽集結合FP-growth算法生成需要過濾掉的Web API標簽關聯規則并放入filterRule中,這些規則的前項和后項都來自于相同的Web API.

3.將2.3中得到的所有Web API標簽關聯規則與filterRule中的規則進行匹配,如果規則存在于filterRule中,那么刪除該規則,如果不存在則保留該規則.

4.最終保留的Web API標簽關聯規則即為得到的Web API組合模式.

經過上述步驟得到的Web API組合模式正確反映了Web API之間的功能關聯關系,能夠體現什么功能屬性的Web API常被組合在一起開發新應用.

3 實驗結果及分析

3.1 數據集

本實驗使用的數據集是從ProgrammableWeb上爬取的9135條Web API記錄以及6875條Mashup記錄.其中,Web API記錄包括API名稱、標簽、類別、網址、描述文檔等信息.Mashup記錄包括Mashup名稱、標簽、使用的Web API組合等信息.

3.2 實驗結果

3.2.1 Web API標簽處理

將Web API的標簽進行詞形還原、同義詞統一等處理,表1展示了部分處理后的Web API標簽數據.

表1 Web API標簽處理結果舉例Table 1 Examples of Web API tag processing

3.2.2 Web API標簽頻繁項集

將處理后的Web API標簽集作為基于FP-growth的Web API標簽關聯規則挖掘算法的輸入,得到了Web API標簽的頻繁項集.表2展示了部分Web API標簽頻繁項集以及它們的頻數.

表2 Web API標簽頻繁項集結果舉例Table 2 Examples of tag frequent itemsets

3.2.3 Web API標簽關聯規則挖掘

通過訓練Web API之間的標簽頻繁項集得到了Web API之間的標簽關聯規則,通過設置最小支持度、最小置信度閾值來獲得具有強關聯性的規則.其中,最小支持度閾值設置為0.007(50/6875),即在6875條Mashup記錄中,規則出現的個數不少于50;最小置信度閾值設置為0.6.表3為2項集Web API標簽關聯規則前10個最優規則.

3.2.4 獲取Web API組合模式

去除Web API標簽強關聯規則中不能反映出API之間的組合關系的規則得到Web API組合模式,這些Web API組合模式能夠準確反映出API之間的功能組合關系.表4展示了2、3、4項集的前5個最優的Web API組合模式.

這15條記錄是從Web API組合模式中選擇的二項集、三項集、四項集支持度、置信度最高的前5條組合模式以及它們的支持度、置信度.這些Web API組合模式是由代表功能屬性的API的標簽訓練得到的標簽關聯規則,并且通過了規則的篩選過濾,它們能夠準確反映出API之間在功能上的關聯關系以及API之間的組合模式.當然,Web API最優組合模式也可以根據其他指標來選擇,如設置不同的模式長度、支持度閾值、置信度閾值等.

表3 2項集Web API標簽關聯規則前10個最優規則Table 3 Top 10 Web API tag association rules for 2-itemsets

表4 多項集Web API組合模式中前5個最優模式Table 4 Top 5 Web API tag association rules for multi-itemsets

以表4的第6條組合模式為例,“[display,video]→map”表示“display”、“video”標簽通常與“map”標簽存在于不同API中,并且這些不同的API能夠通過組合形成Web應用.從“bigsity”Mashup的API組合關系中發現,該mashup中的“yahoo local search”API包含“display”標簽,“youtube”API包含“video”標簽,“google maps”API包含“map”標簽,這三個標簽同時存在于Web API組合中并且“display,video”和“map”來自于不同的API,說明“[display,video]→map”反映出了API在功能上的關聯關系且為正確的Web API的組合模式.

結合Web API的組合模式,開發者可以更加準確、快捷地構建最合理的Web 服務.例如,當開發者已擁有包含“geolocation”標簽屬性的Web API并需要結合新的API組成Mashup時,這時可以根據“[geolocation]→display”組合模式推薦包含“display”標簽的Web API組成新的Mashup.

3.3 方法比較

1)WACP:該方法首先去除Web API標簽中的無意義詞,再對標簽進行詞形還原和同義詞統一等處理得到Web API組合標簽事務集,通過使用基于FP-growth的Web API標簽關聯規則挖掘算法得到所有項集的Web API標簽強關聯規則,過濾掉不能準確反映Web API之間功能關聯關系的規則得到Web API組合模式.

2)Goarany等方法[11]:該方法直接使用Web API的標簽以及API之間的歷史組合關系得到形如“(tagm,tagn)”的二項集Web API標簽對,將每個標簽對中的兩個標簽共同歷史調用次數進行統計得到支持度和置信度,過濾掉兩個標簽同時存在于相同Web API的標簽對,每個標簽對可以生成兩條形如“tagm→tagn”和“tagn→tagm”的規則,對所有標簽對進行該操作得到所有Web API二項集標簽關聯規則.

3.4 評價指標

由于Web API組合模式個數較多,本文選取Web API的所有二項集組合模式進行實驗評價.實驗采用了數據挖掘中常用的評估指標:查準率(Precision)、查全率(Recall)和二者綜合評價的F值(F-measure).

Mashup的標簽描述了Web API組合和Mashup兩者的功能情況,它能從一定程度上反映出Web API之間的關系[11].在本實驗中,假定根據Mashup自身標簽挖掘出的標簽關聯規則為正確規則,若Web API組合模式存在于Mashup標簽關聯規則中,那么認為這條Web API組合模式為正確模式,反之則為不正確模式.以下為查準率、查全率、F值的公式:

查準率公式:

(3)

查全率公式:

(4)

F值公式:

(5)

其中,findtrue為檢索到的Web API組合模式中的正確模式數目,findfalse為檢索到的Web API組合模式中的不正確模式數目,unfindtrue為未檢索到但卻是正確的Web API組合模式數目.

3.5 評價結果

圖3為本文所提出的WACP方法與Goarany等提出的方法在支持度閾值下的Web API組合模式的查準率、查全率、F值性能對比圖.圖4為本文所提出的WACP方法與Goarany等提出的方法在置信度閾值下的Web API組合模式的查準率、查全率、F值性能對比圖.

從圖中可以看出,對于本實驗使用的3種評估標準,不管是從支持度閾值還是置信度閾值的角度去評估,WACP方法都要優于Goarany等提出的方法.當支持度閾值從0.0002到0.0012時,WACP方法的F值分別高于對比方法 1.6%、1.7%、1.5%、1.3%、1.4%、1%,當置信度閾值從0.005到0.03時,WACP方法的F值分別高于對比方法 1.6%、1.6%、1.7%、1.6%、1.5%、1.6%.

由于Web API的標簽存在無意義詞、詞性不統一和同義詞等現象,Web API標簽質量并不是特別高,在這些情況下容易產生不正確的Web API組合模式和能夠表達相同API功能關聯關系的許多重復模式,使得Web API組合模式的準確性并不高.另外,Web API標簽關聯規則中存在許多不能反映出API之間功能關聯關系的規則,這也會影響到Web API組合模式的準確性.

本文提出的WACP方法考慮到了對Web API標簽進行詞形還原、同義詞統一等處理,提高了標簽的質量.另外,將Web API標簽關聯規則中的不合理規則的進行了過濾,使得每個Web API組合模式都能夠準確地反映API之間的功能關聯關系.相比于Goarany等提出的方法只得到了API之間的二項集關聯規則,本文使用的基于FP-growth的Web API標簽關聯規則挖掘算法挖掘得到了所有項集的Web API組合模式,另外,該算法在性能上也優于Goarany等提出的方法和Apriori等.因此,使用WACP方法得到的Web API組合模式更加準確,Precision、recall和F-measure值也有明顯提高.

圖3 不同支持度閾值下的實驗結果Fig.3 Experiment results in different support threshold

圖4 不同置信度閾值下的實驗結果Fig.4 Experiment results in different confidence threshold

4 總結與討論

本文為發現Web API生態系統中的API組合模式,提出了一種基于關聯規則挖掘的方法—WACP.該方法通過結合Web API的標簽以及歷史的API組合關系,先將API標簽進行了詞形還原、同義詞統一等處理,再使用基于FP-growth的標簽關聯規則挖掘算法得到了Web API之間的標簽強關聯規則,最后對規則進行過濾得到了Web API組合模式.Web API組合模式的發現可以為開發者從眾多的Web API中挑選合適的Web API組合提供支持.實驗結果表明了WACP方法的有效性.

許多Web API上標注的標簽數很少甚至沒有,這種數據稀疏性可能會影響Web API組合模式發現的效果.未來工作將考慮Web API的標簽擴展,如從Web API的描述文檔中提取關鍵字推薦新的標簽,以進一步提高標簽關聯挖掘和Web API組合模式發現的性能.