基于組合歷史的交互式服務推薦方法

2018-03-28 05:01:44潘偉豐宋貝貝

計算機研究與發(fā)展 2018年3期

潘偉豐姜波李兵胡博宋貝貝

1(浙江工商大學計算機與信息工程學院杭州 310018) 2(武漢大學計算機學院武漢 430072) 3 (金蝶國際軟件集團金蝶研究院廣東深圳 518057) (wfpan1982@163.com)

面向服務的計算(service-oriented computing, SOC)[1-3]已成為工業(yè)界和學術(shù)界關(guān)注的熱點.它倡導以服務及其組合為基礎構(gòu)造應用的開發(fā)模式,導致軟件的形態(tài)、生產(chǎn)方式、運行方式和使用方式都發(fā)生了巨大變化[3].軟件正處在一個由服務構(gòu)成的開放、協(xié)同的環(huán)境中[4].隨著由服務構(gòu)成的應用的普及,服務的種類和數(shù)量(截止2013年1月PWeb(ProgrammableWeb)*http://www.programmableweb.com上發(fā)布的開放API超過6 400個)急劇增加,以服務為中心的互聯(lián)網(wǎng)正在形成[5].面對數(shù)量龐大的服務群,如何發(fā)現(xiàn)滿足用戶需求的服務已成為影響服務計算進一步發(fā)展的瓶頸[6].

推薦技術(shù)被認為是解決信息資源過載問題的有效方法之一[7].近年來,國內(nèi)外學者將推薦技術(shù)引入服務計算領(lǐng)域,力圖提高服務發(fā)現(xiàn)和選擇的性能,主要包括[8]:基于語義的服務推薦方法[9]、基于情境的服務推薦方法[10]、基于語法的服務推薦方法[11]和基于協(xié)同過濾的服務推薦方法[12-21]等.現(xiàn)有的工作取得了一定的成果,但是仍有2點不足之處:

1) 數(shù)據(jù)難以獲取.現(xiàn)有的方法基本都依賴事先收集的用戶注冊信息(興趣、國籍、年齡等)、歷史的服務調(diào)用信息、用戶偏好信息、服務的QoS信息等數(shù)據(jù),然而這些數(shù)據(jù)對于普通用戶收集不易.

2) 未考慮所推薦服務的可用性及與已有服務的可組合性.現(xiàn)有的方法基本都是針對用戶需求不明確時的服務推薦,針對復合服務開發(fā)(服務組合)時的服務推薦較少,基本都忽略了服務的可用性(推薦的服務是否可以訪問)及推薦的服務與已有服務的可組合問題.

因此,如何在復合服務開發(fā)階段(服務組合)時,在缺少用戶注冊信息、歷史的服務調(diào)用信息、用戶偏好信息、服務QoS信息等的情況下,為開發(fā)者推薦可用的、可組合的服務成為服務推薦領(lǐng)域的一個新問題.

針對這一新問題,我們提出了一種基于組合歷史的交互式服務推薦方法(interactive service reco-mmendation based on composition history, iSee).1)該方法依據(jù)服務注冊庫中(復合)服務元信息構(gòu)建服務網(wǎng)絡模型;2)使用復雜網(wǎng)絡中的方法(如單模投影[22]、骨干網(wǎng)挖掘等[23])挖掘服務組合關(guān)系及使用模式;3)基于服務網(wǎng)絡,并在服務使用模式及服務失效數(shù)據(jù)的支持下,針對服務的3種使用場景,提出了相應的服務推薦算法.我們以PWeb上mashup應用和開放API的真實數(shù)據(jù)為例進行驗證,并與相關(guān)方法進行對比研究.結(jié)果表明:本文的方法在實現(xiàn)服務推薦方面是正確和有效的.

1 問題定義

在給出iSee方法的詳細過程之前,首先通過一個實際場景說明本文擬解決的主要問題,并引出問題的定義.

Unmeshm是一家社交網(wǎng)絡公司的程序員,他曾通過組合Facebook,Flickr,Google Maps這3個開放API開發(fā)了一個Blog on a Map應用,使用戶可以在地圖上發(fā)布博客.后來,Unmeshm將該應用發(fā)布在網(wǎng)絡上,并提供了該應用的元信息(如名稱、描述、標簽、使用的開放API等).Mrowe是另一家公司的程序員,正在利用開放API開發(fā)新的應用,為用戶定位其Facebook上好友的位置.Mrowe通過搜索已找到了一個開放API Facebook,那么接下來他應該選擇哪個API與Facebook組合呢？網(wǎng)絡上的開放API數(shù)量龐大,通過人工查看API文檔尋找可以與Facebook組合的API是極其困難的.但是,Mrowe預開發(fā)的應用與Unmeshm已開發(fā)的Blog on a Map應用在功能上有類似之處.Mrowe可否利用Unmeshm的成功經(jīng)驗來尋找下一個可以與Facebook可組合的API呢?

Mrowe可以利用的信息主要包括開放API的元信息(如名稱、描述、標簽等),應用(復合服務)的元信息(如名稱、描述、標簽、使用的開放API等).他無法得到用戶的注冊信息、偏好信息、服務的QoS信息等數(shù)據(jù).因此,現(xiàn)有的很多服務推薦方法[8-18]都將無能為力.

因此,我們將本文擬解決的問題定義為:在復合服務開發(fā)階段,僅給定復合服務及原子服務的一些元信息,如何利用歷史的服務組合信息為開發(fā)者推薦滿足需求的可用、可組合的服務.

為了解決這一問題,有2個關(guān)鍵點:

1) 如何抽象和表達蘊含在復合服務和原子服務元信息中的知識,并通過分析服務組合歷史信息,挖掘服務的使用模式.

2) 如何針對復合服務開發(fā)的不同場景為用戶推薦服務.

2 iSee方法

服務的組合歷史包含了服務使用的隱含知識[3].iSee方法使用這種經(jīng)過檢驗的知識為用戶推薦服務,從而提高應用開發(fā)的效率.圖1是iSee方法的框架圖.

Fig. 1 Framework of iSee圖1 iSee方法框架

2.1 數(shù)據(jù)收集

互聯(lián)網(wǎng)上分布著大量的服務,為了有效利用這些服務,必須使它們能夠動態(tài)地找到彼此.服務注冊中心為服務提供了一個宣傳自己并了解其他服務的地方.為了使自己開發(fā)的(復合)服務盡可能地被找到,服務提供者一般會按特定的注冊模型詳細地描述其提供的服務,如原子服務的名稱、描述、標簽等(復合服務可能還包含其使用的原子服務集).iSee方法主要使用這些易于獲取的數(shù)據(jù)來為開發(fā)者推薦服務.因此,我們將爬取(復合)服務的這些元信息.同時,為了保證數(shù)據(jù)的準確性,我們還將對數(shù)據(jù)做降噪處理,如修正拼錯的單詞、去除重復的(復合)服務等[3].

2.2 服務網(wǎng)絡模型

抽象和表達蘊含在復合服務和原子服務元信息中的知識是利用這些知識的前提[3].復合服務通常由>0個原子服務輔以一定的編程組合而成.iSee方法將復合服務和原子服務間的宏觀組合關(guān)系用服務網(wǎng)絡模型抽象.下文首先給出相關(guān)服務網(wǎng)絡的定義.

定義1. 服務隸屬網(wǎng)(service affiliation network,SAN).復合服務可由原子服務組合而成.復合服務使用原子服務的關(guān)系與社交網(wǎng)絡中多個人員參與一個社會組織的隸屬關(guān)系[22]類似.因此,iSee使用服務隸屬網(wǎng)SAN抽象復合服務對原子服務的使用關(guān)系.SAN本質(zhì)上是一個二部圖,即SAN=(Ncs,Ns,Duse).其中:Ncs和Ns分別為復合服務和原子服務的節(jié)點集;無向邊集Duse={{csi,sj}},csi∈Ncs,sj∈Ns抽象復合服務csi對原子服務sj的使用.SAN中復合服務和原子服務2類節(jié)點間的連接關(guān)系可由關(guān)聯(lián)矩陣ψ描述,其元素:

(1)

其中,ψ是一個|Ncs|×|Ns|的二值矩陣.若ψi j=1,則{csi,sj}∈Duse,否則{csi,sj}?Duse.

通過對SAN在原子服務方向上做單模投影[22],可得到原子服務間的可組合關(guān)系.

定義2. 服務組合網(wǎng)(service composition network,SECON).SECON=(Ns,Dc)可用于抽象原子服務間的可組合關(guān)系.其中:Ns同SAN中Ns的定義;Dc是一個無向邊的集合,表示原子服務間的共現(xiàn)關(guān)系[3].SECON的關(guān)聯(lián)矩陣ψs可由ψ得到,其元素:

(2)

SECON包含了原子服務間是否可以組合的知識.但是,SECON是由SAN單模投影得到的,單模投影會引入很多無效的組合關(guān)系.如圖2所示,假設復合服務CS由原子服務S1,S2,S3構(gòu)成,可以構(gòu)建相應的SAN,如圖2所示.同時,通過對SAN在原子服務方向作投影可得到相應的SECON,如圖2右邊圖所示.在投影時,因S1,S2,S3在CS中共現(xiàn),所以SECON中原子服務兩兩間都存在連邊,表明它們之間可能可以組合.但是,若S1,S2,S3間的真實組合關(guān)系如圖2左ωs所示,則SECON中S1和S3間的邊是無效的.因此,原子服務間真實的組合網(wǎng)絡ωs=(Ns,Es)和SECON滿足Es∈Dc.隨著復合服務數(shù)的增加,通過投影得到的SECON往往會比較稠密,大量的無效邊使我們很難準確把握原子服務間真實的組合關(guān)系.因此,有必要盡量去除SECON中的無效邊.

Fig. 2 Illustration of invalid compositions by one-modeprojection圖2 單模投影產(chǎn)生無效組合關(guān)系的例子

復雜系統(tǒng)和復雜性科學被認為是“21世紀的科學”,它的基本觀點是結(jié)構(gòu)決定功能[24].iSee用網(wǎng)絡模型抽象原子服務間的組合關(guān)系,啟發(fā)我們用復雜網(wǎng)絡研究中較成熟的理論及方法過濾SECON的無效邊.

iSee引入復雜網(wǎng)絡研究中的骨干網(wǎng)(backbone network)挖掘方法[23]過濾SECON中的無效邊,挖掘服務組合骨干網(wǎng).骨干網(wǎng)挖掘在很多領(lǐng)域獲得了成功的應用,如食譜分析[23]、航空網(wǎng)分析[25]、議會大選[26]、Internet網(wǎng)分析[26]等,它主要基于各節(jié)點的權(quán)重及其分布特征,挖掘具有統(tǒng)計顯著意義的邊.我們使用Barabási研究組在文獻[23]中提出的骨干網(wǎng)挖掘算法挖掘服務組合骨干網(wǎng)(service composition backbone network,SCBN).下文首先給出概念的定義.

定義3. 節(jié)點權(quán).節(jié)點i的節(jié)點權(quán)si定義為與該節(jié)點相連的所有邊的權(quán)重和,即:

(3)

其中,vi是節(jié)點i的鄰居節(jié)點集(網(wǎng)絡中與節(jié)點i存在連邊的節(jié)點集),wi j是節(jié)點i和j間邊(i,j)的權(quán)值.如圖2中右圖所示,sS1=wS1S2+wS1S3=2.

定義4. 歸一化邊權(quán).邊權(quán)wi j相對于si的歸一化邊權(quán)pi j定義為

pi j=wi j/si.

(4)

文獻[23]僅將網(wǎng)絡中滿足(1-pi j)ki-1<α的邊(i,j)保留下來(ki是節(jié)點i的度,α是給定的一個過濾值).若節(jié)點i不存在這樣的邊,則保留邊權(quán)最大的一條邊.求解服務組合骨干網(wǎng)的過程詳見算法1.其中,Network是加權(quán)無向網(wǎng)絡類(類型同SECON),Node是節(jié)點類,nodes是SECON的節(jié)點集,getDegree(i)返回節(jié)點i的度,getWeight(i)返回節(jié)點i的節(jié)點權(quán),getNeighbors(i)返回節(jié)點i的鄰居節(jié)點集,w[i][j]存儲邊(i,j)的邊權(quán),pow(x,y)等價于xy,alpha對應α.

算法1.SCBN挖掘算法bne.

輸入:SECON、過濾值alpha;

輸出:SCBN.

Networkbne(NetworkSECON,floatalpha){

① 構(gòu)建一個與SECON同節(jié)點,但沒有邊的網(wǎng)絡NewNetwork;

② for (Nodei:nodes) {

③ intk=getDegree(i);

④ intkBak=k;

⑤ floatmaxWeight=-1.0;

⑥ if (k>1) {

⑦ floats=getWeight(i);

⑧ for (Nodej:getNeighbors(i)) {

⑨ doublep=1.0×w[i][j]/s;

⑩ if (pow(1-p,k-1)

服務推薦時,若所推薦的原子服務是不可用的,就得尋找與該原子服務功能相似的可用原子服務進行替代.為此,iSee引入服務相似網(wǎng)表征原子服務及原子服務間的相似關(guān)系.

定義5. 服務相似網(wǎng)(service similarity network,SANE).SANE可以表示為SANE=(Ns,Dsim).其中:Ns為原子服務節(jié)點集,Dsim是無向邊集,表示邊2端原子服務間存在相似性,邊上權(quán)值表示相似性大小.

原子服務的元信息包含了對其功能的描述.通過元信息各個部分(如描述、標簽等)相似度的計算可以得到原子服務間功能的相似度.原子服務元信息的各部分本質(zhì)是長短不一的文檔,相似度的計算可以使用向量空間模型[27].

我們以原子服務元信息中描述的相似性計算過程為例說明向量空間模型的實施步驟.首先,使用詞向量為每個原子服務的描述信息建立N維空間向量:

dj=(w1,j,w2,j,…,wN,j),

(5)

其中,dj為原子服務j的描述信息所對應的空間向量,N是描述信息中的不同詞語(短語)數(shù),wi,j表示第i個詞語(短語)的權(quán)重.

然后,使用2個原子服務描述向量的余弦系數(shù)表示原子服務間由于描述而產(chǎn)生的相似性:

(6)

其中,Sim(di,dj)是di和dj間的相似性,Cos(di,dj)是di和dj間的余弦系數(shù),T是詞(或短語)的集合,|T|返回T中元素個數(shù).

原子服務間的相似性為其元信息各部分(描述、標簽等)相似性的線性加權(quán)和:

(7)

同時,原子服務的元信息各部分是長短不一的文本.短文本包含的詞語較少且重復率低,長文本包含的詞語較多且重復率高.我們分別使用布爾向量空間模型和TF-IDF模型[27]為其中的短文本(標簽等)和長文本(描述等)設置詞語權(quán)重wi,j.為了客觀地設置式(7)中的權(quán)值αk,我們引入統(tǒng)計實踐中常用的變異系數(shù)法(coefficient of variation method,CV)[28].

需要指出的是,本文主要以離線的方式構(gòu)建各類服務網(wǎng)絡,即首先從服務注冊中心爬取服務的元信息,并存于本地數(shù)據(jù)庫;然后從本地數(shù)據(jù)庫讀取信息構(gòu)建各類網(wǎng)絡.我們并未考慮在構(gòu)建服務網(wǎng)絡的過程中又有新服務加入的情況,因為我們是定期爬取服務信息的.當然,我們構(gòu)建的服務網(wǎng)絡也極易動態(tài)擴展.一旦有新的復合服務進來,只需對新的復合服務構(gòu)建SAN和SECON,然后將新構(gòu)建的SECON并入原來的SECON中(增加新的節(jié)點、新的邊或改變已有邊的邊權(quán));骨干網(wǎng)更新的時候也只需重新考慮是否將受影響的邊(新加入的邊和邊權(quán)改變的邊)及節(jié)點加入到骨干網(wǎng)中;服務相似網(wǎng)更新的時候,只需依次計算新加入的原子服務與網(wǎng)絡中原有原子服務間的相似度,并將新原子服務及相應的邊加入相似網(wǎng)絡.

2.3 服務使用模式

SAN抽象了復合服務對原子服務的使用歷史,從SAN投影得到的SECON和SCBN自然包含了原子服務間的可組合關(guān)系.實際上,SECON和SCBN的任意路徑都是一個潛在的復合服務.但是原子服務間是如何組合在一起的呢？為了回答這個問題,我們有必要對服務的使用模式進行分析.

我們主要圍繞2個問題對服務使用模式進行分析：

問題1. 一個復合服務通常由多少個原子服務構(gòu)成.

問題2. 原子服務是否更傾向于和流行的原子服務連接.

iSee使用網(wǎng)絡模型抽象復合服務對原子服務的使用關(guān)系及原子服務間的組合關(guān)系.我們可以借鑒復雜網(wǎng)絡中的結(jié)構(gòu)分析方法揭示服務的使用模式.為此,我們將首先引入復雜網(wǎng)絡研究中的2個統(tǒng)計指標.

定義6[29]. 度數(shù)中心度(degree centrality,DC).復雜網(wǎng)絡研究中,節(jié)點的度數(shù)中心度描述了網(wǎng)絡中與該節(jié)點相連的節(jié)點數(shù).

在SAN中,復合服務的DC描述了其使用的原子服務數(shù).因此,我們可以通過分析復合服務DC的分布規(guī)律得到構(gòu)成一個復合服務所需原子服務數(shù)的范圍[A,B].例如,若95%的復合服務使用的原子服務數(shù)均在[1,5]內(nèi),便可將上述[A,B]定為[1,5].

定義7[30]. 度分布.度分布P(k)表示一個隨機選擇的節(jié)點度恰好是k的概率,常用累積度分布來定義,即Pcum(k)=P(K>k)～k-β.

當網(wǎng)絡的度分布符合冪律分布時,那么這個網(wǎng)絡就是“無標度”網(wǎng)絡[30].在無標度網(wǎng)絡中,大部分節(jié)點只與少數(shù)節(jié)點相連,而極少的節(jié)點與大量節(jié)點相連.因此,若原子服務的度分布是無標度的,則表明開發(fā)者“擇優(yōu)”[30]選擇原子服務構(gòu)造復合服務.換言之,開發(fā)者傾向于選擇流行的原子服務構(gòu)建復合服務.

2.4 服務推薦算法

復合服務開發(fā)過程中,原子服務的使用場景大致可分為3種[3]:1)開發(fā)者還未選擇原子服務;2)開發(fā)者已選擇了1個原子服務;3)開發(fā)者已選擇了multi(multi>1)個原子服務.對于情況1,一旦開發(fā)者選定了一個原子服務,就自動轉(zhuǎn)化為情況2.iSee將服務的推薦問題轉(zhuǎn)化為在SCBN中搜索包含給定節(jié)點的路徑的過程.路徑中開發(fā)者已選節(jié)點外的節(jié)點代表的原子服務即為推薦的原子服務.然而,若SCBN規(guī)模大且稠密,則其包含指定節(jié)點且長度任意的路徑數(shù)會很龐大,難以推薦開發(fā)者真正需要的組合方案.因此,本文主要關(guān)注下一個可組合服務的推薦,而完整的復合服務則通過不斷地交互進行構(gòu)造.

但是,原子服務處在一個開放、動態(tài)的環(huán)境中,服務的可用性不能持續(xù)保證.若用戶選擇的原子服務失效,我們必須為其推薦功能相似的可替換服務,而原子服務間的功能相似性蘊含在SANE中.因此,iSee方法將SCBN,SANE,服務的使用模式、服務失效數(shù)據(jù)等作為服務推薦的基礎設施,為開發(fā)者推薦服務.

通過SANE可以找到與失效服務相似的服務集.但是這僅僅利用的是服務間的相似性,忽略了服務流行性上的差異,即在相似服務集中,有些服務可能已經(jīng)被廣泛使用(在SAN中DC值大),有些很少使用(在SAN中DC值小),有些甚至從未被使用過.因此,在計算可替換服務集時,為了綜合考慮服務間的相似度及服務的流行性,我們提出了相似服務的排序指標sRank:

(8)

其中,sRankj表示節(jié)點j的sRank值,wi j是節(jié)點i與j間的相似度,kj是節(jié)點j在SAN中的度,maxDeg是SAN中原子服務節(jié)點的最大DC值,α1和α2是相應分量的權(quán)值,且α1+α2=1,代表相應分量對sRank的貢獻程度.若sRank與服務的流行性無關(guān)(網(wǎng)絡非無標度),則可設置α1=1,α2=0.

iSee按如下步驟計算可替換服務集:1)在SANE中尋找與失效服務相鄰的所有鄰居節(jié)點;2)依據(jù)sRank值降序排列這些鄰居節(jié)點;3)返回sRank值最大的若干鄰居節(jié)點作為可替換服務集.算法2所示的是單個失效服務的可替換服務推薦算法resReal(replaceable service recommendation algorithm).其中,Network是加權(quán)無向網(wǎng)絡類,Node是節(jié)點類,nodes是SANE的節(jié)點數(shù)組,j.sRank表示節(jié)點j的sRank成員值,j.k是節(jié)點j的度,α1和α2是通過2.2節(jié)所述CV求得的加權(quán)系數(shù),w[ss][j]是邊(ss,j)上的權(quán)值.

算法2. 可替換服務推薦算法resReal.

輸入:SANE、存儲失效服務數(shù)據(jù)的數(shù)組fs、單個失效服務ss、待推薦的服務數(shù)resNum;

輸出:推薦的服務數(shù)組.

Node[]resReal(NetworkSANE,Node[]fs,Nodess,intresNum) {

① Node[]nodeBak=new Node[nodes.length];

② intmaxDeg=0;

③ for (Nodei:nodes) {/*nodes為SAN節(jié)點集*/

④ intdeg=getDegree(i);

⑤ if (deg≥maxDeg) /*求節(jié)點最大度*/

⑥maxDeg=deg;

⑦ if (ss與i在SANE中有邊相連)

⑧ if (i不在fs中)

⑨ 將節(jié)點i加入nodeBak數(shù)組;

⑩ }

j.k/maxDeg;

算法2的關(guān)鍵步驟是for循環(huán)(步驟③～步驟⑩)的步驟④,故其時間復雜度是O(n2)(n是SANE網(wǎng)絡節(jié)點數(shù)).

iSee為上述3種原子服務的不同使用場景都提供了相應的推薦方法.

場景1. 開發(fā)者還未選擇原子服務.

開發(fā)者還未選擇原子服務時的服務推薦類似于推薦系統(tǒng)中的“冷啟動”問題,這時我們將向開發(fā)者推薦“平臺”原子服務[3].“平臺”原子服務流行度很高,參與了大部分復合服務的構(gòu)建.因此,新構(gòu)建的復合服務也很可能選擇這些“平臺”原子服務.為此,iSee將SAN中的服務按照DC值降序排列,并將Top-psNum個服務推薦給用戶(psNum是待推薦的服務數(shù)).

算法3. 平臺服務推薦算法psReal.

輸入:SAN、待推薦的服務數(shù)psNum;

輸出:度Top-psNum的服務數(shù)組.

Node[]psReal(NetworkSAN,intpsNum) {

① for (Nodei:nodes1) /*nodes1為SAN原子服務節(jié)點數(shù)組*/

② for (Nodej:nodes2) /*nodes2為SAN復合服務節(jié)點數(shù)組*/

③ if (i與j相連)

④i.degee++;

⑤BubbleSort(nodes); /*按度值冒泡排序(降序)*/

⑥ 返回度值Top-psNum的服務集進行推薦;

⑦ }

算法3的關(guān)鍵步驟是for循環(huán)(步驟①～步驟④)內(nèi)的步驟③,故其時間復雜度是O(nm)(n,m分別是SAN的原子服務節(jié)點數(shù)和復合服務節(jié)點數(shù)).

場景2. 開發(fā)者已選擇了1個原子服務.

iSee主要是基于SCBN為用戶推薦服務,而原子服務只有與其他原子服務在復合服務中共現(xiàn)才能出現(xiàn)在SCBN中.對于一些僅參與一個復合服務構(gòu)建(該復合服務僅由一個原子服務構(gòu)成)或未參與任何復合服務構(gòu)建的原子服務是不可能出現(xiàn)在SCBN中的.因此,對于選擇了1個原子服務的服務推薦問題,iSee將分2種情況:1)已選服務不屬于無效服務集fs,并且存在于SCBN中;2)情況1之外的情況.對于情況1,我們可以直接在SCBN中搜索與該服務直接相連的服務來推薦.對于情況2,iSee將首先為用戶推薦可替換的Top-resNum服務,一旦用戶選擇了某個服務,再按照情況1為用戶推薦服務.iSee將不在SCBN中的服務也看成失效服務,因為它們沒有歷史使用記錄可以利用.

那么,如何對待推薦的服務按某種優(yōu)先級排序呢？如2.3節(jié)所述,服務的排序應融入服務使用模式的知識.因此,若服務的度分布是冪律分布,則服務更傾向于和流行的服務連接.為了綜合考慮SCBN中服務連接強度和度分布對服務優(yōu)先級的影響,我們引入曾在文獻[31]中提出的加權(quán)k-核分解方法(weightedk-core decompostition method,Wk-core)分析服務節(jié)點的優(yōu)先級.

Wk-core基于節(jié)點的加權(quán)度從整體角度分析節(jié)點重要性.加權(quán)度指標綜合考慮了節(jié)點的度和邊權(quán)對節(jié)點重要性的影響,符合本文對服務優(yōu)先級的定義.節(jié)點i的加權(quán)度wDeg(i)定義為

(9)

假設網(wǎng)絡G=(V,E)是由|V|個節(jié)點和|E|條邊組成的一個加權(quán)無向網(wǎng)絡,則與Wk-core相關(guān)的概念定義如下:

定義8. 網(wǎng)絡的加權(quán)k-核(weightedk-core).是指反復去掉加權(quán)度值小于或等于k的節(jié)點及其連邊后剩余的子圖,并且該子圖是具有這一性質(zhì)的最大子圖.

定義9. 節(jié)點的加權(quán)核數(shù)(weighted coreness)k.表示該節(jié)點存在于加權(quán)k-核中,但是在加權(quán)(k+1)-核中被刪除,則該節(jié)點的加權(quán)核數(shù)為k.節(jié)點加權(quán)核數(shù)的最大值kmax稱為網(wǎng)絡的加權(quán)核數(shù).

本文將節(jié)點的加權(quán)核數(shù)作為節(jié)點排序的優(yōu)先級,值越大排名越靠前.對于無效的服務其加權(quán)核數(shù)值為0.已選1個原子服務的推薦過程如算法4所示.

算法4. 已選1個原子服務的推薦算法sigReal.

輸入:SCBN,SANE、存儲失效服務數(shù)據(jù)的數(shù)組fs、用戶已選服務selS、待推薦的方案數(shù)sigNum、算法2參數(shù)resNum;

輸出:推薦的服務集合.

Node[]sigReal(NetworkSCBN,NetworkSANE,Node[]fs,Node[]selS,intsigNum,intresNum) {

① booleanflag;inti=0;

② Node[]resNodes;/*存儲替換服務集*/

③ if (selS[0]屬于fs‖selS[0]不在SANE)

④flag=true;

⑤ if (flag=true) {

⑥r(nóng)esNodes=resReal(SANE,fs,selS[0],resNum); /*調(diào)用算法2*/

⑦ 輸出resNodes中Top-resNum的可替換服務,等待用戶選擇;

⑧selS[0]=resNodes[s]; /*若用戶選擇了第s個服務s∈[0,resNum]*/

⑨ }

⑩ for (Nodei:nodes)

/*nodes為SCBN的節(jié)點集*/

場景3. 開發(fā)者已經(jīng)選擇了multi(multi>1)個原子服務.

對于選擇了multi(multi>1)個原子服務的服務推薦問題,iSee將分2種情況:1)已選原子服務不屬于無效服務集fs,并且存在于SCBN中;2)情況1之外的情況.對于情況1,我們可以直接在SCBN中搜索包含已選服務的路徑來推薦服務.對于情況2,我們必須按照算法2為失效的服務推薦可替換服務.同時,如2.3節(jié)所述,復合服務一般由[A,B]個以內(nèi)的原子服務構(gòu)成,所以iSee限定推薦的簡單路徑節(jié)點數(shù)在B以內(nèi).推薦算法如算法5所示.

算法5. 已選multi個服務的推薦算法mulReal.

輸入:SCBN,SANE,存儲失效服務數(shù)據(jù)的數(shù)組fs、存儲用戶已選服務的數(shù)組selS、待推薦的方案數(shù)mulNum、算法2參數(shù)resNum及路徑最大節(jié)點數(shù)B;

輸出:推薦的服務集合.

Node[]mulReal(NetworkSCBN,NetworkSANE,Node[]fs,Node[]selS,intB,intresNum) {

① booleanflag[]=new boolean[selS.length];

② intcnt=0;Node[]resNodes;

③ for (inti=0;i

④ if (selS[i]不屬于fs‖selS[i]不在SANE)

⑤flag[cnt++]=i;

⑥ }

⑦ for (inti=0;i

⑧resNodes=resReal(SANE,fs,selS[flag[i]],resNum);

⑨ 輸出resNodes中Top-resNum的可替換服務,等待用戶選擇;

⑩selS[flag[i]]=resNodes[s]; /*若用戶選擇第s個服務s∈[0,resNum]*/

因此,總的服務推薦算法IsReal如算法6所示.

算法6. 服務推薦算法IsReal.

輸入:SANE，fs，ss，resNum，SAN，psNum，SCBN，selS，sigNum，mulNum，B;

輸出:推薦的服務集合.

① while (true) {

② 接受用戶輸入的服務,存于selS數(shù)組;

③ if (selS元素個數(shù)=0) {

④ 按照算法3的psReal推薦服務;

⑤ }

⑥ else if (selS元素個數(shù)=1) {

⑦ 按照算法4的sigReal推薦服務;

⑧ }

⑨ else if (selS元素個數(shù)≤B){

⑩ 按照算法5的mulReal推薦服務;

算法6的時間復雜性分析詳見各種場景相應的算法部分,此處不再贅述.

3 實例分析

為了說明iSee的具體實施過程,同時驗證其正確性和有效性,本文將結(jié)合PWeb上mashup應用和開放API的真實數(shù)據(jù),進行實證分析.

3.1 數(shù)據(jù)來源

PWeb是目前最大和最活躍的mashup應用和開放API注冊庫,提供了mashup和API的一些注冊元信息,如圖3所示.mashup是由API組合而成的,包含了對API的使用歷史.因此,可以將API看成原子服務,mashup看成復合服務.同時,若某一API失效了,在其名字旁和描述中都會出現(xiàn)“Deprecated”.因此,失效API服務集也容易獲得.PWeb數(shù)據(jù)集符合iSee方法對數(shù)據(jù)的要求.

我們使用的數(shù)據(jù)集是PWeb上截止2011年12月14日的所有mashup應用和開放API的元信息(圖3中矩形框內(nèi)信息),并按文獻[3]中的方法對數(shù)據(jù)降噪.最終,實驗數(shù)據(jù)集含復合服務6 362個(mashup應用)、原子服務4 506個(開放API).

3.2 實驗過程及結(jié)果

如圖3(b)所示,每個mashup應用都有一個構(gòu)成該mashup的開放API列表.我們據(jù)此構(gòu)建了所有mashup應用和其所用API間的SAN,共包含6 362個mashup節(jié)點和982個API節(jié)點.如前所述,爬取的數(shù)據(jù)集中API共有4 506個,但最終SAN中的API只有982.可見,PWeb上API的使用率比較低,被使用過的API僅占總API數(shù)的21.8%.

Fig. 3 Meta-information of open API and mashup圖3 開放API及mashup應用的元信息頁

① http://www.programmableweb.com/api/google-maps ② http://www.programmableweb.com/mashup/ski-bonk

一旦構(gòu)建了SAN,就可以根據(jù)SAN分析開放API的使用模式.圖4所示的是mashup的DC分布.從圖4可見,95.8%的mashup應用其使用的開放API數(shù)≤5,僅有4.2%的mashup應用使用的開放API數(shù)≥10.這說明大部分mashup應用僅由少量的開放API構(gòu)成.因此,我們將2.3節(jié)中提到的范圍[A,B]確定為[1,5].同時,將DC排名Top-10的API,如表1所示,作為“平臺”API[3].

Fig. 4 DC distribution of mashup圖4 mashup應用的DC分布

NamesofOpenAPIsDCGoogleMaps2303Twitter661Flickr590YouTube589AmazoneCommerce403Twilio333Facebook320eBay214Last．fm206GoogleSearch178

圖5所示的是開放API在雙對數(shù)軸上的Pcum(k).從圖5可見,Pcum(k)接近直線,評價擬合精度的指標R2達到了0.98以上,滿足冪律分布.冪律分布表明,開發(fā)者傾向于選擇流行的開放API構(gòu)建mashup.因此,式(8)中a2≠0.本文不區(qū)分服務的相似性與流行性對sRank的影響,設置a1=a2=0.5.

Fig. 5 Cumulative degree distributuion of open API (log-log scale)圖5 開放API的累積度分布(雙對數(shù)軸)

通過對SAN在API方向作投影操作,可以得到SAN相應的SECON,包含865個節(jié)點和10 966條邊.投影產(chǎn)生了117個孤立節(jié)點,它們沒有與其他API在同一個mashup中共現(xiàn).SECON排除了這類孤立節(jié)點.SECON的平均DC達到了25,網(wǎng)絡比較稠密,包含了很多無效邊.為此,我們使用骨干網(wǎng)挖掘算法(算法1)過濾SECON中的無效邊.最終,我們得到的SCBN包含865個節(jié)點、7 702條邊.

同時,我們根據(jù)開放API的描述和標簽計算了API間的相似度(其中:描述用TF-IDF模型計算、標簽用布爾向量空間模型計算),構(gòu)造了SANE(包含4 506個節(jié)點和8 629 141條邊).

3.3 實驗結(jié)果分析

在本節(jié)中,我們將重點圍繞4個問題對實驗結(jié)果進行深入分析.

3.3.1 骨干網(wǎng)挖掘算法過濾無效邊的能力檢驗

要檢驗骨干網(wǎng)挖掘算法在過濾無效邊上的有效性,必須有服務間真實連接關(guān)系的數(shù)據(jù).PWeb上mashup內(nèi)部API間真實的連接關(guān)系是無法直接獲取的.為此,我們使用在文獻[32]中構(gòu)建的數(shù)據(jù)集.通過解析工作流源文件獲取工作流與Web服務間的關(guān)系,我們構(gòu)建了SAN(包含261個工作流和358個Web服務).通過對SAN在Web服務方向作投影獲得了相應的SECON(包含358個Web服務和4 252條邊).

Fig. 6 The curve of valid and invalid edg ratio versus alpha圖6 有效邊與無效邊比例隨alpha的變化情況

從圖6可見,當alpha∈[0.60,1.00],SECON的邊并沒有明顯的減少;當alpha∈[0.50,0.60),無效邊的比例顯著降低,而有效邊的比例沒有減少;當alpha∈[0.40,0.50),無效邊的比例顯著下降,有效邊的比例緩慢下降;當alpha∈[0.00,0.40)無效邊的減少基本穩(wěn)定,有效邊的比例顯著減少.由此可見,骨干網(wǎng)挖掘算法對于過濾無效邊確實可以起到一定作用.

文中若沒有特別說明,取alpha=0.45.在這種設置下,整個網(wǎng)絡的邊數(shù)沒有太明顯的減少,可以盡量去除無效邊,保留有效邊.alpha的最優(yōu)設置方法此處不做討論,因為在去掉部分無效邊的SECON上做推薦始終優(yōu)于在最原始的SECON上做推薦.

3.3.2 iSee方法推薦有意義API的能力檢驗

我們設計了人工實驗以檢驗本文方法的有效性.我們邀請了10人參與本次實驗,包括3名同事、3名博士研究生和4名碩士研究生.3名同事從事服務計算相關(guān)研究已有4年之久,3名博士研究生也在服務計算領(lǐng)域從事了3年的研究,3名碩士研究生在服務計算領(lǐng)域也從事了2年的研究.他們對于mashup應用的開發(fā)及PWeb平臺都比較熟悉,但是他們事先并不了解iSee方法.

在實驗中,他們將各自獨立開發(fā)一個與旅游相關(guān)的mashup應用,但是只能使用我們的平臺(該平臺實現(xiàn)了iSee)及平臺提供的API資源.他們可以根據(jù)自己的經(jīng)驗,從選擇0個、1個或多個API開始,增量式的開發(fā)mashup應用.根據(jù)開發(fā)者的開發(fā)情境,我們將給用戶提供Top-10的API推薦意見,同時將檢測用戶是否選擇我們推薦的服務,并記錄選擇了哪幾個服務、在推薦列表中的排名、推薦的時間(實施推薦到用戶選擇該推薦的總時間)等信息.若用戶對我們推薦的結(jié)果不滿意也可以通過關(guān)鍵詞檢索的方式查找相應的服務.

為了客觀地量度iSee在服務推薦方面的準確度,我們計算了平均排序分(average rank score)[33].對于某一開發(fā)者u而言,服務s的排序分RSus定義為

(10)

其中,Lu表示可為開發(fā)者u推薦的服務總數(shù),lus是開發(fā)者u選擇的服務s在Lu中的排名.將所有的開發(fā)者的排序分求算數(shù)平均便能得到系統(tǒng)的排序分RS.排序分值越小,說明系統(tǒng)越趨于把滿足用戶需求的服務排在前面;反之,說明系統(tǒng)把用戶需要的服務排在了越后面.

在實驗中,10個參與人共進行了28次選擇,我們發(fā)現(xiàn)他們選擇的服務都排在推薦的服務列表的前6,平均RS為0.3255.這說明iSee方法在輔助開發(fā)復合服務方面還是可以起到一定作用的,其推薦的服務能滿足開發(fā)者的需求.

3.3.3 iSee方法與同類方法的對比

目前服務推薦方面的工作很多,但是從結(jié)構(gòu)角度(服務網(wǎng)絡)出發(fā)的工作并不多.在本節(jié)中,iSee將僅與從結(jié)構(gòu)角度出發(fā)的LFH方法[3]及BIGSIR方法[32]進行比較.

為了比較各個方法推薦效果上的差異,我們需要分別為這10個參與者的每次選擇構(gòu)造最優(yōu)服務推薦列表.為此,我們又請這10位參與者不使用iSee的推薦功能,僅通過PWeb的搜索功能來尋找API,構(gòu)建滿足其需求的mashup應用,以檢驗是否存在比iSee方法推薦的Top-10服務更好的服務.若存在這樣的服務,我們便將其與iSee的推薦結(jié)果合并,然后由他們?nèi)斯@些服務進行打分排序,構(gòu)建新的Top-10服務推薦列表.我們將由這10個參與者各自給出的Top-10服務推薦列表看成是最優(yōu)的服務推薦列表.

在實驗中,僅2個參與者各自發(fā)現(xiàn)了一個比iSee方法Top-10中更好的服務,而且這2個方案在最終人工構(gòu)造的Top-10推薦列表中排名都比較靠后,分列8,9位.我們請這10個參與者人工對iSee方法的Top-10結(jié)果進行排序,以構(gòu)造最優(yōu)排序結(jié)果.對于其中2位發(fā)現(xiàn)了新服務的參與者,我們將新發(fā)現(xiàn)的服務與iSee方法為其推薦的Top-10服務一起參與排序.我們發(fā)現(xiàn),iSee方法排名1～6位的推薦服務集和排名7～10位的推薦服務集與最優(yōu)排序1～6位的服務集和7～10位的服務集(新增2個除外)基本是一致的,只是服務的相對排名有差異.

為了得到LFH方法和BIGSIR方法的推薦結(jié)果,我們重復了3.3.2節(jié)中的實驗,僅服務推薦分別使用LFH和BIGSIR方法.在實驗中,我們發(fā)現(xiàn):對于LFH方法,僅17個采納了推薦的Top-10服務列表中的服務,而且選擇的服務都排在6～10位間,其余11個通過人工搜索查找;對于BIGSIR方法,僅10個采納其服務推薦意見,而且選擇的服務都排在6～10位間,其余18個通過人工搜索查找.

服務推薦實質(zhì)是對服務的排序.因此,比較iSee,LFH,BIGSIR之間的優(yōu)劣,可以通過計算每種方法的排序結(jié)果與最優(yōu)排序的相似度來衡量.Kendall等級相關(guān)系數(shù)τB[34]常用于量度2種排序結(jié)果的相似性及其強弱.本文將使用τB量度各種推薦方法排序結(jié)果與最優(yōu)排序結(jié)果的相似關(guān)系.τB定義為

(11)

使用τB計算2個排序的相似性有一個前提條件,即2個排序是對相同的元素集合進行排序.iSee的Top-10服務集與最優(yōu)服務集元素基本一致.LFH和BIGSIR的推薦服務集與最優(yōu)服務集之間元素差別比較大.LFH的結(jié)果集與最優(yōu)服務集平均只有2.4個元素相同;BIGSIR的結(jié)果集與最優(yōu)服務集平均只有1.2個元素相同.因此,我們無法用τB量度LFH和BIGSIR的排序結(jié)果與最優(yōu)排序的相似性.因此,我們使用τB僅量度iSee推薦服務集與最優(yōu)排序集的相似關(guān)系(結(jié)果如表2所示).因每個參與者多次選擇的τB存在顯著度不一致的問題,無法求其均值.表2中顯示的是參與者在多次選擇中τB的最低值.在計算2個排名的相關(guān)性系數(shù)時,對于新增了2個推薦意見的參與者,我們將新增加的推薦意見放在第11位,而最優(yōu)排序?qū)⑵浞謩e排在了第8和第9位.

Table 2 τB Between Results of iSee and Optimum表2 iSee方法排序結(jié)果與最優(yōu)排序的τB

Note:*Correlation is significant at the 0.05 level (two-tailed).

從表2可見,iSee方法給10位參與者的推薦結(jié)果在多數(shù)情況下都與其相應的最優(yōu)推薦至少存在顯著性水平0.05的正相關(guān)性,相關(guān)系數(shù)在0.4以上,僅在某幾次選擇中不存在明顯的相關(guān)性.但是至少它們的元素基本是一致的.可見,iSee方法在推薦效果上比LFH和BIGSIR均要好.

在實驗中,一位參與者選擇了一個無效的開放API—alexa Web search,一個參與者選擇了一個沒有被任何復合服務使用過的服務——500px.iSee均可以為這2位參與者提供可替換的服務,從而順利的完成推薦.而這2種情況,LFH和BIGSIR都是無能為力的.因此,從為失效服務及無歷史使用歷史的服務實施推薦來看,iSee要優(yōu)于LFH和BIGSIR.

3.3.4 iSee方法的擴展性如何

作為一個實際的服務推薦方法,iSee將被運用于不同規(guī)模的數(shù)據(jù)集.若一個服務推薦方法時間開銷很大,用戶往往是無法忍受的.因此,我們將檢驗iSee在不同規(guī)模數(shù)據(jù)集上實現(xiàn)服務推薦的時間開銷.

我們設計了2個實驗以檢驗iSee的擴展性.iSee涉及很多與用戶的交互操作,如失效服務的選擇、推薦服務的選擇等.為了能高效地獲取算法運行的時間開銷,我們假設:若服務失效,默認選擇排名第一的可替換服務;用戶每次都選排名第一的推薦服務;推薦的服務數(shù)為10.

實驗1. 數(shù)據(jù)規(guī)模對算法運行時間的影響.

SAN,SECON,SANE等網(wǎng)絡都是根據(jù)mashup和構(gòu)成mashup的API列表定義的.網(wǎng)絡的規(guī)模往往以網(wǎng)絡中的節(jié)點數(shù)來描述.為了分析數(shù)據(jù)規(guī)模對算法性能的影響,我們以600的倍數(shù)隨機采樣得到的原始數(shù)據(jù)集,構(gòu)建各種規(guī)模的網(wǎng)絡(SCBN是在alpha=0.45時構(gòu)建的),并考慮用戶的不同輸入情況,測試算法的運行時間,結(jié)果如圖7所示:

Fig. 7 The curve of running time versus data scale圖7 運行時間與數(shù)據(jù)規(guī)模的變化曲線

為了提高結(jié)果的穩(wěn)定性,圖7中的每個數(shù)據(jù)點是100次獨立實驗得到結(jié)果的平均值.圖7中不同顏色的曲線代表不同的用戶輸入情況(selS是算法4和算法5中的參數(shù),代表用戶已選擇的服務數(shù)).算法的運行時間包含了各種網(wǎng)絡的構(gòu)建時間,這2部分的時間與selS=0時的情況基本一致.然而網(wǎng)絡并不需要每次都動態(tài)構(gòu)建,一般通過離線方式定期更新即可(隨著大量的新mashup的加入才需要更新各網(wǎng)絡).因此,若除去網(wǎng)絡構(gòu)建的時間,推薦算法還是比較高效的.從圖7我們可以發(fā)現(xiàn),算法運行時間隨著mashup數(shù)量和selS值的增加呈現(xiàn)線性增長的趨勢.但是,即使mashup規(guī)模增長了5倍,selS增長到5,算法運行時間仍然低于2.5 min.在大部分情況下,用戶選擇的服務數(shù)都不大于3,算法基本都可以在20 s內(nèi)完成推薦,這么短的時間完全可以給用戶以實時推薦.iSee適用于大規(guī)模服務的情況.

實驗2. 已選服務數(shù)對算法運行時間的影響.

用戶已選服務數(shù)會影響算法的搜索策略.為了分析用戶已選服務數(shù)對算法性能的影響,我們以3.2節(jié)構(gòu)造的數(shù)據(jù)集為實驗對象(SCBN是在alpha=0.45時構(gòu)建的),并考慮用戶的不同輸入情況,測試算法的運行時間,結(jié)果如圖8所示.

Fig. 8 The curve of running time versus selS圖8 運行時間與用戶已選服務數(shù)(selS)的變化曲線

圖8中的每個數(shù)據(jù)點都是100次獨立實驗所得結(jié)果的平均值.selS代表用戶已選服務數(shù).算法的運行時間同樣也包含了各種網(wǎng)絡的構(gòu)建時間.從圖8可見,算法運行時間隨著selS值的增加呈現(xiàn)不斷增長的趨勢.當selS≤3時,時間增長緩慢.當selS>3時,時間增長快速.因為隨著selS的增大,API間組合的可能性成倍增加.

4 相關(guān)研究

服務推薦技術(shù)是解決服務資源過載問題的有效方法之一,近年來已涌現(xiàn)了大量的研究工作.

Blake和Nowlan[11]通過對用戶操作會話的監(jiān)控獲取文本信息,并量度該文本信息與Web服務描述文檔的相似性,從而定位用戶感興趣的服務集,實現(xiàn)推薦.

Shao等人[12]通過用戶對相同Web服務的體驗評價用戶間的相似性,并使用基于用戶的協(xié)同過濾算法預測其未使用Web服務的QoS信息,從而向用戶推薦具有較高QoS的服務.

Zheng等人[13]將基于用戶的推薦算法和基于商品的推薦算法系統(tǒng)的融合起來預測Web服務的QoS信息,并實現(xiàn)了推薦系統(tǒng)WSRec.

Zhao等人[35]通過語義技術(shù)發(fā)現(xiàn)服務間隱含的關(guān)聯(lián),并使用網(wǎng)絡模型抽象服務及它們之間的關(guān)聯(lián),提出了一種通過服務間關(guān)聯(lián)發(fā)現(xiàn)用戶所需服務的方法.用戶通過關(guān)鍵字搜索便可獲得相關(guān)的服務集.

Chen等人[14]發(fā)現(xiàn)用戶的地理位置與Web服務的QoS間存在高相關(guān)性.因此,他們構(gòu)建了一種融入用戶地理位置信息的RegionKNN算法來預測服務的缺失QoS信息,進而指導服務推薦.相比于以往的方法,該方法預測的QoS信息更加準確,推薦效果更好.

Deng等人[18]基于網(wǎng)絡建模和分析技術(shù)研究了用戶和服務之間的信任關(guān)系,提出了基于信任協(xié)同過濾的服務推薦算法提供個性化的服務推薦.

Jiang等人[32]構(gòu)建復合服務與原子服務的二部圖,并引入物質(zhì)流動算法實現(xiàn)服務推薦.

Su等人[19]認為,現(xiàn)有的基于協(xié)同過濾的方法在預測服務QoS時忽略了服務歷史QoS信息的可靠性.因此,他們提出了一種信任感知的服務QoS預測方法,進而向用戶推薦具有較高QoS的服務.

Kang等人[20]提出了一種融入用戶潛在QoS偏好及用戶對服務興趣多樣性特征的Web服務推薦方法.

Xu等人[21]綜合考慮用戶端和服務端的情境信息,提出了一種情境感知的Web服務QoS預測方法,并應用于服務推薦和選擇.

我們曾在文獻[3]中將“軟件網(wǎng)絡觀”引入服務分類及推薦中,提出服務分類及推薦的LFH方法.但是該工作主要關(guān)注服務的分類,并未對推薦工作展開深入的探討,只是給出在服務推薦方面可能的應用方向.本文的工作是文獻[3]及文獻[32]的深入研究,是復雜網(wǎng)絡思想在服務推薦領(lǐng)域的進一步實踐,與其他的服務推薦工作存在很大差異.本文提出的系統(tǒng)方法以及算法和評估策略,均可以應用在其他服務推薦研究.

5 結(jié)論與展望

針對現(xiàn)有服務推薦方法中存在的數(shù)據(jù)難以獲取和未考慮所推薦服務的可用性及與已有服務的可組合性等問題,提出了一種基于服務組合歷史的交互式服務推薦方法,給出了服務隸屬關(guān)系、服務組合關(guān)系和服務相似關(guān)系的服務網(wǎng)絡模型,并引入學科交叉思想,用復雜網(wǎng)絡相關(guān)原理及方法分析服務使用模式、去除無效服務關(guān)系等,并進而指導服務推薦,為從網(wǎng)絡科學角度解決服務計算相關(guān)問題提供了一種思路.本文的主要工作有3個方面:

1) 將復合服務、原子服務及它們間的使用關(guān)系用隸屬網(wǎng)抽象,并通過單模投影得到原子服務間的可組合關(guān)系,進而借助復雜網(wǎng)絡中的骨干網(wǎng)挖掘技術(shù)挖掘原子服務間真實的組合關(guān)系,并通過度和度分布挖掘原子服務使用模式,指導服務推薦算法的設計.

2) 依據(jù)服務的3種使用場景設計了相應的推薦方法.方法考慮了服務的失效問題.

3) 以PWeb上真實的服務數(shù)據(jù)驗證所提方法的正確性和有效性.

下一步的研究工作主要包括:提供自適應的參數(shù)設置方法,同時與基于語義、語法、協(xié)同過濾等的推薦方法融合起來,進一步提高服務推薦的效率和精準度.

[1] Papazoglou M P. Service-oriented computing: Concepts, characteristics and directions[C] // Proc of the 4th Int Conf on Web Information Systems Engineering (WISE 2003). Piscataway, NJ: IEEE, 2003: 3-12

[2] Li Gang, Ma Xiujun, Han Yanbo, et al. Transparent service composition in dynamic network environments[J]. Chinese Journal of Computers, 2007, 30(4): 579-587 (in Chinese)

(李剛, 馬修軍, 韓燕波, 等. 動態(tài)網(wǎng)絡環(huán)境下的透明服務組合[J]. 計算機學報, 2007, 30(4): 579-587)

[3] Pan Weifeng, Li Bing, Shao Bo, et al. Service classification and recommendation based on software networks[J]. Chinese Journal of Computers, 2011, 34(12): 2355-2369 (in Chinese)

(潘偉豐, 李兵, 邵波, 等. 基于軟件網(wǎng)絡的服務自動分類和推薦方法研究[J]. 計算機學報, 2011, 34(12): 2355-2369)

[4] Cardoso J. Quality of service and semantic composition workflows[D]. Athens, GA: University of Georgia, 2002

[5] Li Zeng, Wang Jian, Zhang Neng, et al. A topic-oriented clustering approach for domain services[J]. Journal of Computer Research and Development, 2014, 51(2): 408-419 (in Chinese)

(李征, 王健, 張能, 等. 一種面向主題的領(lǐng)域服務聚類方法[J]. 計算機研究與發(fā)展, 2014, 51(2): 408-419)

[6] Zhang Liangjie, Zhang Jia, Cai Hong. Service Computing[M]. Berlin: Springer, 2007

[7] Jannach D, Zanker M, Felfernig A, et al. Recommender Systems: An Introduction[M]. Cambridge: Cambridge University Press, 2010

[8] Sun Huifeng, Zheng Zibin, Chen Junliang, et al. Personalized Web service recommendation via normal recovery collaborative filtering[J]. IEEE Trans on Services Computing, 2013, 6(4): 573-579

[9] Klusch M, Kapahnke P. iSeM: Approximated reasoning for adaptive hybrid selection of semantic services[C] // Proc of the 4th IEEE Int Conf on Semantic Computing (ICSC 2010). Piscataway, NJ: IEEE, 2010: 184-191

[10] Liu Liwei, Lecue F, Mehandjiev N, et al. Using context similarity for service recommendation[C] // Proc of the 4th IEEE Int Conf on Semantic Computing (ICSC 2010). Piscataway, NJ: IEEE, 2010: 277-284

[11] Blake M B, Nowlan M F. A Web service recommender system using enhanced syntactical matching[C] // Proc of the 5th IEEE Int Conf on Web Services (ICWS 2007). Piscataway, NJ: IEEE, 2007: 575-582

[12] Shao Lingshuang, Zhang Jing, Wei Yong, et al. Personalized QoS prediction for Web services via collaborative filtering[C] // Proc of the 5th IEEE Int Conf on Web Services (ICWS 2007). Piscataway, NJ: IEEE, 2007: 439-446

[13] Zheng Zibin, Ma Hao, Lyu M R, et al. WSRec: A collaborative filtering based Web service recommender system[C] //Proc of the 7th IEEE Int Conf on Web Services (ICWS 2009). Piscataway, NJ: IEEE, 2009: 437-444

[14] Chen Xi, Liu Xudong, Huang Zicheng, et al. RegionKNN: A scalable hybrid collaborative filtering algorithm for personalized Web service recommendation[C] //Proc of the 8th IEEE Int Conf on Web Services (ICWS 2010). Piscataway, NJ: IEEE, 2010: 9-16

[15] Zheng Zibin, Ma Hao, Lyu M R, et al. QoS-aware Web service recommendation by collaborative filtering[J]. IEEE Trans on Services Computing, 2011, 4(2): 140-152

[16] Zhang Qiong, Ding Chen, Chi Chihung. Collaborative filtering based service ranking using invocation histories[C] //Proc of the 9th IEEE Int Conf on Web Services (ICWS 2011). Piscataway, NJ: IEEE, 2011: 195-202

[17] Chen Xi, Zheng Zibin, Liu Xudong, et al. Personalized QoS-aware Web service recommendation and visualization[J]. IEEE Trans on Services Computing, 2013, 6(1): 35-47

[18] Deng Shuiguang, Huang Longtao, Wu Jian, et al. Trust-based personalized service recommendation: A network perspective[J]. Journal of Computer Science and Technology, 2014, 29(1): 69-80

[19] Su Kai, Xiao Bin, Liu Baoping, et al. TAP: A personalized trust-aware QoS prediction approach for Web service recommendation[J]. Knowledge-Based Systems, 2017, 115(1): 55-65

[20] Kang Guosheng, Tang Mingdong, Liu Jianxun, et al. Diversifying Web service recommendation results via exploring service usage history[J]. IEEE Trans on Services Computing, 2016, 9(4): 566-579

[21] Xu Yueshen, Yin Jianwei, Deng Shuiguang, et al. Context-aware QoS prediction for Web service recommendation and selection[J]. Expert Systems with Applications, 2016, 53: 75-86

[22] Newman M E J. The structure of scientific collaboration networks[J]. Proceedings of the National Academy of Sciences, 2001, 98(2): 404-409

[23] Strogatz S H. Exploring complex networks[J]. Nature, 2001, 410(6825): 268-276

[24] Ahn Y Y, Ahnert S, Bagrow J P, et al. Flavor network and the principles of food pairing[OL]. [2016-07-01]. https://www.nature.com/articles/srep00196

[25] Serrano M A, Boguna M, Vespignani A. Extracting the multiscale backbone of complex weighted networks[J]. Proc of the National Academy of Sciences, 2009, 106(16): 6483-6488

[26] Lee S H, Kim P J, Ahn Y Y, et al. Googling social interactions: Web search engine based social network construction[J]. Plos One, 2010, 5(7): e11233

[27] Salton G, Wong A, Yang Chungshu. A vector space model for automatic indexing[J]. Communications of ACM, 1975, 18(11): 613-620

[28] McClave J T, Benson P G, Sincich T. Statistics for Business and Economics[M]. 10th ed. Upper Saddle River, NJ: Prentice Hall, 2008

[29] Wikipedia. Centrality definition[EB/OL]. [2016-05-05]. http://en.wikipedia.org/wiki/Centrality

[30] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512

[31] Pan Weifeng, Hu Bo, Jiang Bo, et al. Identifying important packages of object-oriented software using weightedk-core decomposition[J]. Journal of Intelligent Systems, 2014, 23(4): 461-476

[32] Jiang Bo, Zhang Xiaoxiao, Pan Weifeng, et al. BIGSIR: A bipartite graph based service recommendation method[C] // Proc of the 9th IEEE World Congresss on Services (SERVICES 2013). Piscataway, NJ: IEEE, 2013: 363-369

[33] Zhou Tao, Ren Jie, Medo M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E, 2007, 76(4): 046115

[34] Pan Weifeng, Li Bing, Ma Yutao, et al. Identifying the key packages using weighted PageRank algorithm[J]. Acta Electronica Sinica, 2014, 42(11): 2174-2183 (in Chinese)

(潘偉豐, 李兵, 馬于濤, 等. 基于加權(quán)PageRank算法的關(guān)鍵包識別方法[J]. 電子學報, 2014, 42(11): 2174-2183)

[35] Zhao Chenting, Ma Chun’e, Zhang Jing. HyperService：Linking and exploring services on the Web[C] // Proc of the 8th IEEE Int Conf on Web Services (ICWS 2010). Piscataway, NJ: IEEE, 2010: 17-24