夏 會,高 旻,鄒 淑

(1.重慶理工大學(xué) 會計學(xué)院,重慶400054;2.重慶大學(xué) 大數(shù)據(jù)與軟件學(xué)院,重慶400044)

Web服務(wù)是一種平臺獨立、低耦合、可編程的Web應(yīng)用程序,具有良好的互操作性,廣泛用于開發(fā)大規(guī)模的分布式應(yīng)用程序。隨著信息技術(shù)的迅猛發(fā)展,特別是云計算等新型服務(wù)計算的興起,軟件應(yīng)用、計算能力、數(shù)據(jù)等許多資源都被打包成服務(wù),Web服務(wù)的數(shù)量呈指數(shù)級增長,大量功能相同或相似的Web服務(wù)不斷涌現(xiàn)[1]。用戶因為缺乏相應(yīng)的專業(yè)知識而無法作出選擇,及時準確地為用戶發(fā)現(xiàn)和選擇高質(zhì)量的服務(wù)成為服務(wù)計算領(lǐng)域亟待解決的問題[2]。

個性化推薦技術(shù)作為緩解信息過量產(chǎn)生和有效信息發(fā)現(xiàn)不平衡的有效方法之一[3],被引入到Web服務(wù)領(lǐng)域,可以及時高效地為用戶提供滿足需求的Web服務(wù),提高用戶的滿意度[4]。個性化服務(wù)推薦技術(shù)的一個重要問題是如何獲得Web服務(wù)的質(zhì)量(Quality of Service,QoS)。QoS作為描述Web服務(wù)的主要非功能性特征,包括Web服務(wù)的響應(yīng)時間、吞吐量、價格和可靠性等[5]。精確的QoS可以有效地提高Web服務(wù)推薦的性能[6]。盡管用戶可以通過親自調(diào)用Web服務(wù)來評估QoS,但是要在短時間對大量候選服務(wù)的QoS進行準確評估是不太可能的[7]。與此同時,網(wǎng)絡(luò)環(huán)境的不確定性以及惡意的用戶反饋可能導(dǎo)致用戶調(diào)用Web服務(wù)時的QoS是虛假的,包含噪聲的[8]。實際應(yīng)用中,用戶對Web服務(wù)的QoS矩陣通常是稀疏的,包含噪聲的,對Web服務(wù)推薦影響較大。由于Web服務(wù)的QoS屬性受到用戶和Web服務(wù)所在的位置、訪問時間以及網(wǎng)絡(luò)環(huán)境等因素的影響,當前的研究多在已有的基于用戶或服務(wù)協(xié)同過濾推薦[5,9-10]的基礎(chǔ)上,利用時間和位置的特征[2,11-14],對QoS的預(yù)測結(jié)果進行優(yōu)化,以更好地進行協(xié)同過濾推薦。

筆者在上述工作的基礎(chǔ)上,總結(jié)Web服務(wù)的時空特征為:短時間內(nèi),相似用戶通常具有相似的網(wǎng)絡(luò)環(huán)境和網(wǎng)絡(luò)性能,進而有較大可能在相同的Web服務(wù)上觀察到相似的性能。因此,得出用戶 服務(wù)的QoS矩陣具有結(jié)構(gòu)相似性。

1)全局結(jié)構(gòu)相似性?？紤]到用戶的網(wǎng)絡(luò)行為在短時間(如s、min、h)內(nèi)通常變化不明顯(在2 h內(nèi)用戶一直使用視頻類軟件看電影),即存在用戶在較短時間內(nèi)使用相同的或者類似的Web服務(wù)的現(xiàn)象,相鄰兩個時間段(s、min、h)內(nèi)的用戶 服務(wù)QoS矩陣的全局結(jié)構(gòu)是相似的[14]。這種全局結(jié)構(gòu)相似性是時間相似性的一種體現(xiàn)。

2)局部結(jié)構(gòu)相似性。相鄰用戶通常處于同一自治系統(tǒng),或者處于相鄰自治系統(tǒng)內(nèi),其在相鄰時間段內(nèi)具有相同或相似網(wǎng)絡(luò)環(huán)境的可能性較大,有可能對相同服務(wù)的QoS反饋是相似的[15]。QoS矩陣在相鄰用戶上具有局部的結(jié)構(gòu)相似性,這種局部結(jié)構(gòu)相似性本質(zhì)上反映了用戶位置的相似性。

文中將上述特征融入到對QoS的預(yù)測上,提出了基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解模型(Global and Local Structure Similarity based Sparse Matrix Factorization Machine,GLMF),以達到提升QoS預(yù)測精度的目標。①將QoS矩陣的時空特征與矩陣分解相結(jié)合,提出了一種基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解模型。在矩陣分解時,通過保留其與前一時刻QoS值的全局相似性信息,以及當前時刻用戶的局部相似性信息,可以顯著提高QoS的預(yù)測性能。②使用真實的Web服務(wù)QoS數(shù)據(jù)集對提出的方法進行了實驗評估。結(jié)果驗證了所提方法具有較高的預(yù)測性能,表明了該方法可以很好地處理數(shù)據(jù)稀疏和噪聲的問題。

基于協(xié)同過濾方法的Web服務(wù)推薦得到廣泛的研究和應(yīng)用,并取得較好的效果。協(xié)同過濾推薦技術(shù)主要分為基于記憶的協(xié)同過濾推薦[16]、基于模型的協(xié)同過濾推薦?；谟洃浀姆椒ㄓ挚煞譃榛谟脩舻腫17]和基于物品的[18]兩種方法。基于記憶的協(xié)同過濾推薦需要根據(jù)歷史數(shù)據(jù)得到相似用戶或服務(wù),基于相似用戶或服務(wù),實現(xiàn)對Web服務(wù)的QoS值的預(yù)測?；谀Ｐ偷姆椒╗19]通過歷史數(shù)據(jù)的學(xué)習(xí),建立一個全局模型,確定用戶 物品間的隱含關(guān)系,實現(xiàn)對QoS值的預(yù)測。Zheng等[20]將基于用戶和基于物品的方法進行混合,實現(xiàn)Web服務(wù)的可靠性預(yù)測。Wang等[10]基于用戶相似性和基站相似度實現(xiàn)移動網(wǎng)絡(luò)環(huán)境下Web服務(wù)的個性化推薦,并在此基礎(chǔ)上對QoS值進行預(yù)測。盧鳳等[9]基于用戶和服務(wù)的時空相似性特征,對相似性計算方法進行了改進,構(gòu)建了Web服務(wù)推薦系統(tǒng)的框架,提高了對QoS協(xié)同預(yù)測的精確度。王磊等[5]為避免協(xié)同過濾推薦精度受數(shù)據(jù)稀疏的影響,提出基于K-means聚類的Slope One算法,能夠有效地提升QoS預(yù)測的精度?；谀Ｐ偷姆椒馨l(fā)現(xiàn)用戶 服務(wù)之間隱含的關(guān)系,具有更高的預(yù)測精度[21]。為進一步提高QoS的預(yù)測精度,Zhang等[14]基于Web服務(wù)的時間感知屬性對用戶 服務(wù) 時間矩陣進行分解,有效地填充了未知的QoS值。Chen等[14]將用戶或服務(wù)聚為一類,認為同類的用戶或服務(wù)共享某種隱含特征,并基于此實現(xiàn)對QoS值的預(yù)測。Yang等[11]基于用戶和服務(wù)的位置信息對用戶 服務(wù)矩陣進行分解,有效地解決數(shù)據(jù)稀疏和冷啟動的問題,Liu等[13]也利用位置屬性對協(xié)同過濾推薦的結(jié)果進行優(yōu)化。Ryu等[15]則在位置信息的基礎(chǔ)上,基于偏好可傳播性對用戶 服務(wù)矩陣進行分解,有效地解決了冷啟動的問題。唐明董等[12]在位置信息的基礎(chǔ)上,采用因子分解方法進行矩陣分解,有效地解決了數(shù)據(jù)稀疏和冷啟動的問題。

目前,解決數(shù)據(jù)稀疏等問題取得了較多成果,然而其主要工作均建立在用戶和服務(wù)的地理位置相似性上,對其時間屬性的應(yīng)用并不充分。文中將充分應(yīng)用用戶或服務(wù)的時間空間屬性,挖掘用戶、服務(wù)之間的隱含關(guān)系,提升QoS的預(yù)測性能。

1 基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解模型(GLMF)

先介紹GLMF方法的總體流程,然后對GLMF的實現(xiàn)細節(jié)進行描述,包括模型和算法步驟。GLMF方法的總體流程,如圖1所示,GLMF通過記錄t+1時刻用戶 服務(wù)QoS矩陣的位置相似性和相鄰時間QoS矩陣的時間相似性,采用稀疏矩陣分解的方法對t+1時刻未知的QoS值進行預(yù)測。

圖1 GLMF的總體流程Fig.1 The general flow of GLMF

1.1 QoS矩陣的構(gòu)建

對未知QoS值的預(yù)測需要獲得歷史Web服務(wù)調(diào)用所產(chǎn)生的QoS數(shù)據(jù),主要通過服務(wù)用戶的反饋以及QoS的監(jiān)測系統(tǒng)產(chǎn)生。前者收集用戶對Web服務(wù)的反饋,如響應(yīng)時間、可用性及信譽等;后者通過部署在服務(wù)器上的監(jiān)測系統(tǒng)收集Web服務(wù)的QoS屬性。所有服務(wù)調(diào)用產(chǎn)生的QoS記錄可以用一個矩陣來表示,即用戶 服務(wù)的QoS矩陣,每個QoS記錄可能包含多個QoS參數(shù)。下面給出各個時刻t下的用戶 服務(wù)QoS矩陣的形式化表示。

1)S代表Web服務(wù)集合,S={s1,s2,…,s p};U用于代表調(diào)用Web服務(wù)的所有用戶的集合,U={u1,u2,…,u n}。這里假設(shè)所有時刻的用戶和服務(wù)不變。

2)R t代表t時刻用戶調(diào)用服務(wù)產(chǎn)生QoS記錄的矩陣,即用戶 服務(wù)QoS矩陣其中代表t時刻用戶u i調(diào)用服務(wù)s j產(chǎn)生的QoS記錄,該記錄可以是響應(yīng)時間、吞吐量、反饋等。若用戶未調(diào)用過該服務(wù),則QoS記錄為空。真實場景中,每個時刻用戶通常僅使用部分Web服務(wù),產(chǎn)生的用戶 服務(wù)QoS矩陣應(yīng)當十分稀疏。文中要解決的問題可以形式化表示為基于稀疏矩陣R t和R t+1,實現(xiàn)對矩陣R t+1的低秩填充。

1.2 模型簡介

對t+1時刻的矩陣R t+1進行典型的低秩矩陣分解,其損失函數(shù)為

由于相鄰時刻網(wǎng)絡(luò)環(huán)境相差不大,相似用戶調(diào)用服務(wù)的QoS屬性可能具有相似性,且相鄰時刻的QoS矩陣也具有相似性。上述特征反映在QoS矩陣上分別是局部結(jié)構(gòu)相似性(位置相似性)和全局結(jié)構(gòu)相似性(時間相似性)。將其融入到式(1)中得到修正后的損失函數(shù)為

其中,第3項通過最小化t+1時刻與t時刻QoS矩陣差異性的方式保留t時刻QoS矩陣的全局結(jié)構(gòu)特征;第4項通過拉普拉斯矩陣L保留t+1時刻的局部結(jié)構(gòu)特征,L=D-W。W是R t+1的相似度矩陣(采用歐氏距離進行表示,距離越大,相似度越小),D是對角矩陣(其對角線上的元素來自于對W各行的求和)。

基于式(2)計算梯度為

采用乘性迭代法則對A t+1和B t+1進行尋優(yōu):

1.3 基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解算法

算法1.基于時空感知的稀疏矩陣分解算法。

輸入:用戶 服務(wù)QoS矩陣R t+1和R t;隱式特征數(shù)M;誤差標準ε和δ;迭代次數(shù)count。

①隨機初始化分解因子A t+1(N×M)和B t+1(P×M);

②cnt=0;

③按照式(5)和式(6)計算誤差度量指標MAE和RMSE;

④while cnt

⑤按照式(3)和式(4)對A t+1和B t+1更新;

⑥按照式(5)和式(6)計算誤差度量指標MAE和RMSE;

⑦end while

2 實驗驗證與分析

為了驗證方法的有效性,采用真實的Web服務(wù)QoS數(shù)據(jù)進行實驗評估[14]。該數(shù)據(jù)集采集自wsdream.com網(wǎng)站,包含4 532個Web服務(wù)在64個相鄰時間段內(nèi)被142個用戶調(diào)用的QoS記錄,主要是吞吐量(throughput)和響應(yīng)時間(response time,或round trip time,RTT)兩方面。值得注意的是,QoS有多種屬性,包括響應(yīng)時間、吞吐量等客觀屬性,也包括用戶對服務(wù)質(zhì)量的反饋等主觀屬性。對于客觀屬性數(shù)據(jù),需要對其歸一化以消除不同量綱的影響;對于主觀屬性數(shù)據(jù),可以利用用戶平均值與整體平均值進行糾偏(這里假定整體均值是中立的)。

文中使用服務(wù)的RTT數(shù)據(jù)來評估所提出的方法。實驗采用的數(shù)據(jù)集是用戶端的輕量級中間件自動收集用戶調(diào)用服務(wù)時產(chǎn)生的真實QoS記錄,由于所處網(wǎng)絡(luò)環(huán)境、設(shè)備的不同,其QoS記錄必然是包含噪聲的。此外,真實環(huán)境下的RTT矩陣是稀疏的,在實驗時為了模擬實際的Web服務(wù)應(yīng)用場景,通過隨機移除RTT矩陣的一部分數(shù)據(jù)實現(xiàn)對矩陣的稀疏化。采用稀疏度(移除數(shù)據(jù)的大小/總矩陣的大小)來衡量矩陣的稀疏程度。稀疏化后的矩陣是可看做訓(xùn)練數(shù)據(jù),而被移除的數(shù)據(jù)可看做測試數(shù)據(jù)。

2.1 評估指標

通過計算預(yù)測的RTT值與實際RTT值之間的偏差來評估文中方法在預(yù)測Web服務(wù)RTT的準確性。常用的誤差度量指標:平均絕對誤差MAE(mean absolute error)和均方根誤差RMSE(root mean squared error)。二者的計算公式如下:

其中,SP是被移除的數(shù)據(jù),即用于測試的數(shù)據(jù)集,|SP|是數(shù)據(jù)集的大小。MAE和RMSE的值越小,代表預(yù)測的精度越高。

2.2 對比方法的選擇

為了比較GLMF方法與其他方法在預(yù)測性能上的優(yōu)劣,實驗中將其與以下2個經(jīng)典的預(yù)測方法進行了對比:

1)非負矩陣分解(non-negative matrix factorization,NMF)。NMF約束分解后的矩陣分量為非負的。在QoS預(yù)測中,這種假設(shè)是合理的。

2)奇異值分解(single value decomposition,SVD)。SVD是實現(xiàn)矩陣低秩近似的典型方式之一?；跉v史數(shù)據(jù)的潛在信息尋找一個屬性空間,用戶調(diào)用服務(wù)的QoS值由用戶和服務(wù)在此屬性空間的點集求得。

3)Kmeans+Slope One算法?；陧椖?服務(wù))的協(xié)同過濾推薦中,Slope One算法可以有效地實現(xiàn)缺值預(yù)測。然而,Slope One算法在實現(xiàn)時未考慮到項目與項目之間的相似性。因此,在空缺值預(yù)測之前,使用K-means算法對項目進行聚類以提高QoS預(yù)測精度。

2.3 參數(shù)λ1、λ2、λ3對預(yù)測性能的影響

參數(shù)λ1所在項是為了防止過擬合而設(shè)置的,參數(shù)λ2和λ3分別用于保留QoS矩陣的全局結(jié)構(gòu)相似性和局部結(jié)構(gòu)相似性。文中矩陣的稀疏度均設(shè)置為0.9,隱式特征數(shù)目設(shè)置為30。從圖2、圖3和圖4可以發(fā)現(xiàn),參數(shù)λ1、λ2、λ3的取值在一定程度上會影響到預(yù)測的精度。圖2中MAE和RMSE起初隨著參數(shù)λ1的增加快速下降,當λ1大于0.000 5時,整體反而上升。圖3中MAE和RMSE起初隨著參數(shù)λ2的增加快速下降,當λ2大于0.5時,基本保持平穩(wěn)或者緩慢下降。圖4中MAE和RMSE起初隨著λ3的增加基本保持不變,當λ3大于0.000 5時,反而快速上升。由此,參數(shù)λ1的值可固定為0.000 5;參數(shù)λ2和λ3可分別設(shè)置為0.5,0.000 5。

圖2 參數(shù)λ1對預(yù)測性能的影響Fig.2 The effect of parameterλ1 on prediction performance

圖3 參數(shù)λ2對預(yù)測性能的影響Fig.3 The effect of parameterλ2 on prediction performance

圖4 參數(shù)λ3對預(yù)測性能的影響Fig.4 The effect of parameterλ3 on prediction performance

2.4 QoS矩陣的稀疏度對預(yù)測性能的影響

在真實場景中,各個時刻的QoS矩陣均是稀疏的,其稀疏程度不同,預(yù)測性能是不同的。文中模型對時刻t和t+1的QoS矩陣(R t和R t+1)進行處理,矩陣R t和R t+1的稀疏度均會對預(yù)測性能有影響。具體結(jié)果如圖5和圖6所示。圖5中固定矩陣R t的稀疏度為0.9,矩陣R t+1的稀疏度范圍為[0.55,0.95],每步增長0.05。由圖5可知,MAE和RMSE的值隨著稀疏度的增加整體上不斷增加,且整體增加幅度不大。這意味著適當?shù)氖占疩oS記錄,減小數(shù)據(jù)稀疏度可以提高預(yù)測的精度。圖6中固定矩陣R t+1的稀疏度為0.9,矩陣R t的稀疏度范圍為[0.55,0.95],每步增長為0.05。由圖6可知,隨著稀疏度的增加,MAE值出現(xiàn)緩慢的增長,RMSE值基本保持不變。這意味著前一時刻矩陣的稀疏度對預(yù)測的性能有影響,但影響效果十分有限,表明文中方法具有良好的可擴展性,少量的全局結(jié)構(gòu)信息可以達到較好的預(yù)測性能。

圖5 QoS矩陣R t+1稀疏度對預(yù)測性能的影響Fig.5 The effect of the sparseness of QoS matrix R t+1 on prediction performance

圖6 QoS矩陣R t稀疏度對預(yù)測性能的影響Fig.6 The effect of the sparseness of QoS matrix R t on prediction performance

2.5 隱特征數(shù)目對預(yù)測性能的影響

隱特征個數(shù)體現(xiàn)了對QoS矩陣認知的程度。隱特征個數(shù)越高意味著對QoS矩陣的認知越高,增加了計算的復(fù)雜度;隱特征個數(shù)越少,雖然降低了計算的復(fù)雜度,但是減少了對QoS矩陣的認知。圖7展示了隱特征數(shù)目對預(yù)測性能的影響,其中QoS矩陣R t和R t+1的稀疏度均設(shè)置為0.9,隱特征數(shù)目的范圍為[5,100],每步增長5。隨著隱特征數(shù)目的增加,RMSE整體上呈現(xiàn)顯著的降低,MAE整體上變化不大。這表明隱特征數(shù)目的增加,一定程度上加強了對QoS矩陣的認知,導(dǎo)致預(yù)測性能總體變好。然而,在[20,40]范圍內(nèi),MAE和RMSE值均出現(xiàn)一定的波動。因為并不是所有增加的隱特征都能有效加強對QoS矩陣的認知。文中均衡計算性能和預(yù)測性能,最終在實驗中設(shè)置隱特征數(shù)目為30。

圖7 隱特征個數(shù)對預(yù)測性能的影響Fig.7 The effect of the number of underlying features on prediction performance

2.6 不同方法預(yù)測性能的對比

表1顯示了GLMF與各種對比方法的預(yù)測結(jié)果。其中,Kmeans+Slope One算法是基于記憶的協(xié)同過濾方法,這種方法在數(shù)據(jù)稠密時能取得較好的效果,卻并不適用于數(shù)據(jù)稀疏的環(huán)境,因此預(yù)測性能最低。NMF、SVD和GLMF均利用矩陣分解理論對用戶 服務(wù)QoS矩陣進行建模,發(fā)現(xiàn)用戶 服務(wù)的隱含特征,提高了預(yù)測的性能。由表1可知,隨著矩陣稀疏度的增加,無論何種方法,其MAE和RMSE值均增加,預(yù)測性能均下降。值得一提的是,GLMF方法在高稀疏度情境下,其MAE和RMSE值均小于其他方法,具有更優(yōu)的預(yù)測性能。相比于NMF,GLMF的MAE值最大下降了3.25%,RMSE值最大下降了6.65%;相比于SVD,GLMF的MAE值最大下降了3.67%,RMSE值最大下降了7.01%。與NMF和SVD相比,GLMF充分利用了用戶 服務(wù)QoS矩陣的全局和局部結(jié)構(gòu)特征,進一步提高了預(yù)測精度。

表1 GLMF、NMF、SVD和Kmeans+Slope One算法的預(yù)測性能Table 2 The prediction performance of GLMF、NMF、SVD and Kmeans+Slope One algorithms

3 結(jié) 論

文中針對用戶 服務(wù)間的QoS預(yù)測問題,充分利用時空特征,即相鄰時間段內(nèi),相似用戶具有相似的網(wǎng)絡(luò)環(huán)境,更大可能具有相似的QoS屬性,提出了一種基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解算法。該算法將QoS預(yù)測問題歸結(jié)為矩陣的低秩近似問題,通過乘性迭代的方式尋找矩陣的因子,最終實現(xiàn)對QoS矩陣的低秩填充。實驗結(jié)果表明,基于全局和局部結(jié)構(gòu)相似性的稀疏矩陣分解模型(GLMF)與經(jīng)典的矩陣分解方法、基于記憶的協(xié)同過濾方法相比,QoS預(yù)測性能有一定的提高,能有效解決數(shù)據(jù)稀疏、噪聲等問題。未來擬將文中方法進一步應(yīng)用于更多場景下,如為基于情景的Web服務(wù)推薦(主要包括基于QoS的服務(wù)聚集、服務(wù)組合優(yōu)化和服務(wù)的異常檢測等)提供支撐。