基于隨機游走增強型矩陣分解的混合服務預測

林堅 李俊

摘要：隨著Web服務數(shù)量的急劇增長，如何在大量功能相似但非功能屬性各異的服務中選擇滿足用戶個性化需求的服務是亟需解決的問題?；赒oS（Quality of Service）預測的服務推薦方法成為研究熱點。然而，QoS數(shù)據(jù)的稀疏性和“冷啟動”問題阻礙其發(fā)展。針對當前主流的QoS預測模型預測精度不高和收斂速度較慢等問題，提出一種基于隨機游走模型和矩陣分解技術的混合QoS預測方法。該方法首先基于矩陣分解獲得用戶及服務的潛因子矩陣，并將用戶潛因子矩陣轉(zhuǎn)化為用戶相似度矩陣;然后基于用戶相似度矩陣并結(jié)合Web服務的網(wǎng)絡位置信息，使用隨機游走模型提高用戶相似度矩陣的準確性;最終結(jié)合協(xié)同過濾方法與矩陣分解模型進行QoS預測。在真實數(shù)據(jù)集上實驗，結(jié)果表明，與當前主流的QoS預測方法相比，該方法具有更高的預測精度和效率。

關鍵詞：QoS預測;隨機游走;矩陣分解;混合預測;服務推薦

DOI：10.11907/rjd k.191205

中圖分類號：TP301 文獻標識碼：A 文章編號：1672-7800（2019）012-0082-07

0引言

近年來，基于協(xié)同過濾（cF）和矩陣分解（MF）的推薦模型在傳統(tǒng)推薦領域如商品、音樂和電影的推薦中應用廣泛。然而，由于Web服務環(huán)境下QoS數(shù)據(jù)難于收集，并且數(shù)據(jù)存在稀疏性及收集數(shù)據(jù)中存在大量無法用于預測的無效信息等原因，阻礙了服務個性化推薦領域的發(fā)展。此外，Web服務分布在不同異構(gòu)網(wǎng)絡中，這些網(wǎng)絡性能各異且獨立的自治系統(tǒng)所收集的數(shù)據(jù)，通常受網(wǎng)絡位置影響而出現(xiàn)偏差甚至無效，從而無法進行有效的QoS預測。因此，亟需一種能針對上述問題的、高效準確的Web服務推薦方法，以滿足用戶的個性化需求。盡管目前已經(jīng)存在許多基于QoS預測的服務推薦模型，但普遍存在預測精度不高、模型復雜等問題。

近年來，基于QoS預測的Web服務推薦技術得到了迅猛發(fā)展。傳統(tǒng)的QoS預測方法包括基于歷史記錄的QoS預測方法、基于位置感知的QoS預測方法、基于時間感知的QoS預測方法以及基于服務外部信息（IP或GPS）的QoS預測方法。雖然這些方法所使用的服務領域信息對QoS預測至關重要，但是由于QoS數(shù)據(jù)集的稀疏性所導致的領域信息不平衡，使得這些方法在提高QoS預測精度上作用十分有限?；诰仃嚪纸獾腝oS預測模型能在一定程度上緩解數(shù)據(jù)稀疏性帶來的問題。文獻[8]提出一種基于矩陣分解的協(xié)同過濾方法預測缺失的QoS值，但該方法存在局部預測精度難以提升問題;文獻[9-10]提出了基于隨機游走的QoS預測模型，并驗證了模型在真實QoS數(shù)據(jù)集上能相對有效地提高預測精度。模型的主要思想是利用轉(zhuǎn)移概率矩陣和馬爾可夫隨機過程原理，把無直接關系的用戶之間相似度考慮在內(nèi)，以在稀疏數(shù)據(jù)集上獲得更加準確的相似性，但該方法存在全局預測精度難以提升的問題。

針對當前預測模型存在的問題，本文結(jié)合現(xiàn)有預測算法優(yōu)點，并且針對QoS數(shù)據(jù)集特點，提出一種混合型預測算法以提高QoS預測精度。

1相關工作

1.1問題描述

基于QoS預測的Web服務推薦主要思想是預測用戶未曾調(diào)用過服務的QoS值，并基于所預測的QoS值推薦能滿足用戶個性化需求的服務。實際Web服務QoS預測場景中包括用戶、服務、用戶調(diào)用服務的實際QoS值3個角色，可用G=（US，SS，Q）三元組表示，其中US={u1，u2，...，，um}表示所有用戶的集合，SS={S1，S2…Sn}表示所有服務的集合，qij，∈ Q表示用戶i調(diào)用服務j產(chǎn)生的QoS值（如響應時間、吞吐量等）。如果服務i未曾被用戶i調(diào)用過，則qij為空，否則非空。一般qij，=-1表示無效值，QoS預測問題是對所有qij為空或無效值進行預測并填充。

1.2冷啟動與稀疏性

傳統(tǒng)的基于協(xié)同過濾（cF）的QoS預測方法會面臨“冷啟動”和稀疏性問題。其中“冷啟動”問題表現(xiàn)為新的服務或用戶沒有歷史調(diào)用的數(shù)據(jù)可利用，從而無法對此類用戶或服務進行推薦。數(shù)據(jù)稀疏問題表現(xiàn)為當用戶和服務數(shù)量急劇增長時，某個用戶只調(diào)用過其中少部分服務，或某個服務只被其中少部分用戶調(diào)用過，導致被觀測和記錄的QoS值qij只占整個二維矩陣Q很小部分，從而無法進行有效預測。

1.3矩陣分解方法

基于矩陣分解（MF）的QoS預測方法是當前解決“冷啟動”和數(shù)據(jù)稀疏性問題的主要途徑。矩陣分解方法主要思想是基于機器學習方法，將表示原始數(shù)據(jù)集的二維矩陣Q分解為用戶和服務的潛因子矩陣u和s，其中所有Uij和Sij都不為空。然后根據(jù)潛因子矩陣中行列之間的線性相關信息恢復原矩陣Q中缺失的值。

盡管矩陣分解方法能夠挖掘出用戶服務間的潛在信息，但僅依靠行列之間線性關系得到的QoS預測會較粗糙，且會引入大量噪聲。另外，全局性好的矩陣分解方法對局部數(shù)據(jù)不夠敏感，會遇到局部預測精度難以提升問題。

1.4隨機游走方法

基于隨機游走模型的QoS預測方法能夠增強用戶之間的相似性，從而在一定程度上提高服務預測的準確性。該方法是傳統(tǒng)CF模型的一種重要改進，其主要思想是利用轉(zhuǎn)移概率矩陣和馬爾可夫隨機過程原理，把無直接關系的用戶之間的相似度考慮在內(nèi)，以在稀疏數(shù)據(jù)集上獲得更加準確的相似性。但傳統(tǒng)的隨機游走模型簡單地在原始用戶相似度矩陣上進行隨機游走，并沒有把Web服務的領域信息考慮在內(nèi)，且沒有利用QoS全局范圍內(nèi)的信息進行預測，因此預測精度提高有限。

1.5Web服務領域信息

在動態(tài)開放的服務環(huán)境中，QoS通常會受到用戶和服務領域信息如網(wǎng)絡位置等影響。因此，在QoS預測時還需將服務的領域信息考慮進來?？梢岳迷糛oS數(shù)據(jù)集中存在的AS1={asi1，asi2...asik}屬性表示用戶或服務的位置系統(tǒng)編號，例如asi;表示用戶i的位置在系統(tǒng)j中。CAS（ui，uj）∈A表示User，和User，的公共位置系統(tǒng)。附加的CAS數(shù)據(jù)集會給稀疏的QoS數(shù)據(jù)集帶來更多的領域附加信息，能夠提高QoS預測算法的準確率。然而，在用戶和服務位置分布比較稀疏的情況下，傳統(tǒng)的基于位置的服務推薦方法在服務QoS預測精度方面會受到限制。

2QoS預測方法

為提高服務預測算法的精確度和效率，在充分分析上述模型的優(yōu)缺點以及QoS數(shù)據(jù)特點基礎上，首先利用矩陣分解模型得到全局范圍內(nèi)準確性較高的QoS預測值;然后基于矩陣分解得到用戶隱特征矩陣，結(jié)合Web服務的網(wǎng)絡位置信息進行隨機游走以增強用戶之間的相似度，進而在局部范圍內(nèi)增加QoS的預測精度;最終混合上述步驟得到兩種不同的結(jié)果作為最終的QoS預測值。

3RWEMF模型

針對QoS預測中存在的稀疏性問題和“冷啟動”問題，本文提出一種結(jié)合矩陣分解方法和基于Web服務領域信息的隨機游走模型混和的QoS預測方法（RWEMF）。該方法首先通過矩陣分解得到用戶潛因子矩陣，然后基于用戶潛因子矩陣進行相似度計算得到用戶相似度矩陣，在此基礎上結(jié)合Web服務的領域信息基于隨機游走模型增強用戶間的相似關聯(lián)度，最后混合協(xié)同過濾和矩陣分解得到最終QoS預測值。

3.1矩陣分解求隱含矩陣

矩陣分解是一種基于低秩矩陣恢復的方法，在服務推薦領域已經(jīng)得到廣泛應用。它通過將用戶和服務投射到更能體現(xiàn)其最顯著特征的具有更低維度的隱含空間，解決有限覆蓋和稀疏性問題。

顯然，矩陣分解能解決大量QoS值為空的稀疏問題，并且能在短時間內(nèi)有效處理大量的服務數(shù)據(jù)。然而，基于矩陣分解的模型是在全局范圍內(nèi)對缺失Qos值進行填充，并沒有考慮用戶的個性化程度及不同偏好。因此對于稀疏數(shù)據(jù)集上的用戶，預測值將接近區(qū)域服務的平均值，并且對數(shù)據(jù)集中波動較大的用戶和服務的預測準確性會降低。因此考慮在矩陣分解的基礎上結(jié)合協(xié)同過濾方法進行個性化的Qos預測，以增強預測結(jié)果的準確性。

3.2相似度計算

傳統(tǒng)的CF方法基于原始數(shù)據(jù)集并采用Pearson相關系數(shù)（PCC）計算用戶之間相似性，如公式（5）所示。PCC反映了不同用戶的QoS值記錄的線性相關性，這種相關性反映了用戶之間偏好的相似性，假設用戶偏好長時間保持不變。

盡管構(gòu)建用于推薦的相似性矩陣較容易，但是存在這樣的問題：當兩個用戶沒有共同調(diào)用的服務時，距離將為零。因為較低距離值意味著算法中的用戶之間有更多相似性，所以零距離用戶被視為最相似的用戶，并且將選擇作為最終預測的鄰居。另外，基于CF的方法中的相似度計算并不總是有效。當服務數(shù)量很大且QoS值為空時，大量的計算資源被浪費。因此，與傳統(tǒng)CF方法不同，使用上一步驟矩陣分解方法后得到的用戶潛因子矩陣u計算用戶的相似度，由于u比原數(shù)據(jù)維度較小并且不存在缺失數(shù)據(jù)，因此大大節(jié)省了大規(guī)模數(shù)據(jù)集運算時間，提高了相似度計算的有效性。相似度矩陣Sim計算如下：

其中，參數(shù)0<λ<1用于調(diào)整各部分預測結(jié)果的權重，使得模型適應不同場景。該算法考慮用戶在QoS值中的均值偏向Q，結(jié)合MF具有較好的全局預測能力，兩個模型在過擬合或欠擬合預測過程中由混合算法的參數(shù)協(xié)調(diào)以取得更高精度。

3.5算法復雜度

RWEMF模型的預測算法時間復雜度由CF和MF各自的計算過程組成。其中，CF的時間復雜度從O（m×n×n）降低到O（m×n×K），其中K是矩陣u的隱含維度。當n很大并且K很小時，計算時間將在數(shù)據(jù)量大的數(shù)據(jù)集中得到有效節(jié)省。從整體過程看，RWEMF算法在這些Web服務數(shù)據(jù)集中不會增加額外的時間復雜度。盡管其時間復雜度大于RWE和MF的總和，但其運行時間即使在數(shù)據(jù)量大的Web服務數(shù)據(jù)集上仍在可接受范圍內(nèi)。

4仿真實驗

4.1實驗設置

本實驗采用真實數(shù)據(jù)集WS-DREAM對模型有效性進行驗證。整個數(shù)據(jù)集包括兩個子數(shù)據(jù)集：響應時間（RT）和吞吐量（TP）。其中響應時間單位為秒（s），吞吐量單位為千比特每秒（kbps），數(shù)據(jù)集詳細的統(tǒng)計特征見表1。從表l可以看到數(shù)據(jù)集的基本情況，參加統(tǒng)計的數(shù)據(jù)包括339個用戶和5825個服務，其中統(tǒng)計參數(shù)包括最小值（min）、最大值（max）、平均值（mean）、標準差（std）?？梢钥吹絉T較TP數(shù)據(jù)集具有更小的數(shù)據(jù)跨度和較小的方差。在兩種分布各異的數(shù)據(jù)集上進行實驗能充分反映預測方法在一般情況下的性能。

表2顯示有關用戶和服務位置信息。user_as行表示數(shù)據(jù)集中有339個用戶，分布在136個領域中，每個領域至少有1個用戶，不超過31個用戶。一個領域內(nèi)平均用戶數(shù)為2.4745，標準差為2.8338。service_as行表示數(shù)據(jù)集中有5825個服務，分布在992個領域中。每個領域至少有1個服務，不超過1212個服務。一個領域內(nèi)的平均服務數(shù)為5.8660個，標準差為40.6090。其中，后綴“as”和“ct”分別表示領域為as（自治系統(tǒng)）和ct（國家）。

本實驗算法采用python2.7和c++混合實現(xiàn)，在一臺CPU為Intel Core i585002.8GHz、內(nèi)存為8G的PC上運行，操作系統(tǒng)為Ubuntu 16。

MAE反映預測的絕對誤差，NMAE反映預測的相對誤差。通過MAE與NMAE兩個參數(shù)的比較可以反映出預測算法的預測精度和性能。

4.3預測準確性

與幾種當前主流預測模型進行對比驗證RWEMF模型的有效性。

（1）UPCC是一種基于用戶的協(xié)同過濾算法，通過Pearson相關系數(shù)計算用戶之間的相似度，以用戶間協(xié)同關系為基礎提供其他用戶QoS值的預測。

（2）IPCC是一種基于服務的協(xié)同過濾算法，通過Pear-SOIl相關系數(shù)計算服務之間的相似度，以服務之間的協(xié)同關系為基礎提供其它服務的QoS預測。

（3）UIPCC是一種混合方法，將UPCC和IPCC的預測結(jié)果組合在一起提供更高精度的預測結(jié)果，其準確性一般有更高的準確度。

（4）PMF是一種基于概率模型的矩陣分解算法。通過聯(lián)合用戶和服務的概率分布建立模型。通過矩陣分解，獲取用戶和服務隱矩陣提供其它QoS預測。

（5）RWE是一種基于用戶的隨機游走模型。主要通過矩陣分解的中間結(jié)果計算用戶之間相似度，在基于協(xié)同過濾的基礎上提供預測。

（6）XEMF是一種基于矩陣分解的算法。主要通過矩陣分解產(chǎn)生用戶和服務隱含矩陣，結(jié)合用戶和服務初始條件提供矩陣缺失值預測，是本文提出的參照算法。

表3和表4顯示了7種方法分別在RT和TP數(shù)據(jù)集上的預測精度的實驗結(jié)果。其中每一行是每種預測方法MAE和NMAE指標，每一列表示不同采樣率，分別在5%、10%、15%、20%采樣率下進行實驗。

當采樣密度為5%時，基于MF算法（PMF）比基于PCC（UPCC，IPCC和UIPCC）具有更小的MAE和NAME，所以預測精度更高。同時，RWE算法的MAE值為0.5255，相對于UPCC、IPCC和UIPCC等基于相似性的協(xié)同過濾算法，預測準確度更高。同樣，基于矩陣分解的方法XEMF的預測精度較PMF有提升。RWEMF算法有0.5068的MAE值和0.5591的NMAE，較其它幾種預測算法有很大提升。在不同采樣率10%、15%、20%下，RWEMF同樣有著最小的MAE和NMAE值，因而RWEMF適用于不同的采樣率情況。最后RWEMF在TP的數(shù)據(jù)集上也有著相同優(yōu)越的表現(xiàn)，較其它算法有更低的MAE和NMAE值。因此可以驗證RWEMF能適用不同數(shù)據(jù)集合。實驗表明使用了隨機游走方法的RWEMF提高了用戶間相似度計算結(jié)果，利用矩陣分解方法的優(yōu)勢有效提高了預測的準確性。

4.4實驗參數(shù)分析

RWEMF中TOPK、MF的隱含維度ldmf（矩陣分解的隱含維度）以及RW和MF混合系數(shù)λrumf是直接影響QoS預測精度的重要參數(shù)，下面分別對這3個參數(shù)進行討論。

圖l和圖2表示調(diào)整參數(shù)topK后，RWEMF分別在RT和TP數(shù)據(jù)集上的性能表現(xiàn)。其中x軸表示5%、10%、15%、20%的采樣密度，丫軸表示RWEMF方法的預測精度MAE。從圖中可以看出，當topK=3時，RWEMF在不同采樣密度下較topK為其它值時有更小的MAE值，這同樣適用于RT和TP。因此，選擇合適的近鄰數(shù)量能使算法得到更好的預測效果。

圖3、圖4表示RWEMF在不同MF分解維度下運行時間和預測精度性能。其中x軸為矩陣分解時的維度，1d-mf包括5、10、15、20、25等幾個分解維度。左邊的丫軸表示算法的運行時間對應圖中條形統(tǒng)計部分，右邊的丫軸表示算法的MAE精度對應圖中折線部分。算法比較試驗在5%、10%、15%、20%采樣密度下進行。首先分析圖中條形統(tǒng)計部分，在采樣密度增加時，算法運行時間也在增加;其次在ldmf算法的矩陣分解維度增加時，算法運行時間也在增加;再分析折線統(tǒng)計部分，折線統(tǒng)計結(jié)果是在同一采樣密度5%下得到的。隨著1dmf變化，預測算法的精度也在變化。當ldmf=15時，在RT和TP數(shù)據(jù)集上，RWEMF算法的MAE相對較小，預測精度較高。隨著ldmf的變化，MAE值反而增加，說明更高的分解維度不會提高算法的預測精度，表明更高維度的分解會引入數(shù)據(jù)噪聲從而影響精度。綜合運行時間和預測精度，當1dmf=15時，算法相對運行更快，可實現(xiàn)更高的預測精度。因此，選擇合適的1dmf參數(shù)是RWEMF算法高效運行的基礎，需要平衡運算和預測精度之間的關系。

圖5、圖6表示λrumf，參數(shù)在混合RWE和MF預測中提高精度的作用。其中x軸表示λrumf，參數(shù)，其值在[0，1]之間，y軸表示預測精度MAE值。實驗中選擇具有代表性的低5%和高20%的采樣密度進行實驗。每種密度都有3種線型（RWE、XEMF和RWEMF）。很明顯，XEMF的MAE是三者中最大的，RWE的MAE低于MF。使用λrumf，為0.7時RWEMF達到了MAE的最小值，此即為算法的最優(yōu)預測狀態(tài)。RT和TP數(shù)據(jù)集具有同樣的實驗效果。因此，選擇合適的λrumf對RWEMF提高預測精度有重要作用。

圖7、圖8表示在RT和TP上3種算法（RWEMF、RWE和XEMF）預測值的分布情況，其中的每個點表示此算法的預測值和實際值誤差的相對位置。其中x和y軸分別代表用戶和服務編號，z軸表示算法的相對誤差值。圖中的點經(jīng)過簡化處理，表示數(shù)據(jù)集上的預測相對位置。這兩個圖可以形象反映出3種算法的預測能力，也解釋了為什么RWEMF可以有效提高預測精度的原因。RWE算法預測的點分布較為分散，在Error為-15，0，20的平面上都有聚集。分析后發(fā)現(xiàn)由于RWE對局部信息更加敏感，在某些位置具有較高的準確度，但在有些位置上又存在較大誤差，因此它在整個數(shù)據(jù)集上具有較大的方差，表現(xiàn)為紅色點離散度更大。XEMF預測的點聚集在靠近Error為0的平面附近，XEMF無法實現(xiàn)局部更高的準確性，但它的預測整體差異很小。RWEMF的點通常位于RWE和XEMF之間，且點聚集在靠近Error為0的平面附近。因此，混合算法的預測有效融合了RWE和XEMF的預測結(jié)果，在RT和TP數(shù)據(jù)集上都有良好表現(xiàn)。

5結(jié)語

本文針對Web服務QoS數(shù)據(jù)集在稀疏采樣條件下的特點，結(jié)合現(xiàn)有的基于隨機游走的CF和MF優(yōu)點，提出了混合型預測算法RWEMF。在WS-Dream數(shù)據(jù)集上對RWEMF算法進行了驗證，實驗結(jié)果表明該預測方法較傳統(tǒng)預測方法有效地提高了預測精度。通過對實驗參數(shù)的進一步分析發(fā)現(xiàn)，相似度計算和附近鄰域選擇對RWEMF預測精度提高很重要?；陔S機游走的CF和MF算法的融合在RT數(shù)據(jù)集上5%采樣密度下的MAE為0.5068，足以體現(xiàn)RWEMF能有效提高Web服務QoS值預測效果。

今后將研究通過對更高精度模型的融合使Web QoS的預測準確度進一步提高。結(jié)合Web QoS數(shù)據(jù)特點，從算法角度設計運行時間少和預測精度高的Web服務預測方法，在Web服務環(huán)境中提高系統(tǒng)預測推薦效率。