面向Web服務QoS預測的非負矩陣分解模型

蘇 凱,馬良荔,孫煜飛,郭曉明

（1.海軍工程大學裝備經濟管理系,湖北武漢430033；2.海軍工程大學計算機工程系,湖北武漢430033）

面向Web服務QoS預測的非負矩陣分解模型

蘇 凱1,2,馬良荔2,孫煜飛2,郭曉明2

（1.海軍工程大學裝備經濟管理系,湖北武漢430033；2.海軍工程大學計算機工程系,湖北武漢430033）

針對目前QoS預測算法準確度不高的問題,提出通過挖掘已有QoS觀測數據中的近鄰信息和隱含特征信息而實現服務QoS預測的方法.建立QoS預測的矩陣分解因子模型,將QoS預測問題轉化為稀疏QoS矩陣下的模型參數期望最大化（EM）估計問題,提出結合近鄰信息的非負矩陣分解算法NCNMF＋EM對該問題進行求解.算法綜合利用了QoS矩陣中的近鄰信息和隱含特征信息,可以實現對不同類型QoS屬性值的準確預測.實驗結果表明,采用該方法可以顯著地提高服務QoS的預測準確度,且算法的運行時間隨著矩陣規模的增大呈線性增長,可以應用于大規模的QoS預測問題中.

Web服務；服務選擇；QoS預測；矩陣因子模型；非負矩陣分解；期望最大化估計

隨著Web服務技術的發展,網絡上出現大量滿足相同功能、但服務質量（quality of service,QoS）不同的候選服務,QoS逐漸成為用戶評價Web服務,進而選擇服務的重要依據［1-3］.在實際應用中,由于不同用戶在調用服務時,網絡環境、地理位置和服務運行環境等存在差異,導致他們體驗到的服務QoS不同［4］.用戶需要對候選服務的QoS進行準確的預測,從而為Web服務的選擇提供可靠的QoS數據支撐.

目前,許多QoS驅動的服務選擇算法［5-7］均采用統計平均法預測服務的QoS,該方法將服務的QoS歷史平均值作為預測值統一提供給用戶,未考慮用戶的個性化差異,導致預測準確率較低.Shao等［8］認為“對某些服務擁有相似QoS經驗的用戶,對其他服務的QoS體驗也會比較接近”,進而采用協同過濾推薦方法為用戶個性化地預測服務的QoS.Zheng等［9］提出一種混合協同過濾QoS預測方法WSRec,通過綜合基于用戶和基于服務的協同過濾預測結果,使得QoS信息矩陣中的近鄰信息得到更充分利用.協同過濾方法對于用戶評分等主觀型數據的預測較準確,但服務的QoS是一種受環境因素影響較大的客觀型數據,僅通過挖掘QoS數據中的近鄰信息難以保證QoS預測的準確度.

文獻［10,11］假設“當外界環境特征和輸入特征相似時,服務的QoS相對穩定”,進而在為目標用戶預測服務的QoS時,首先探測用戶的環境特征和輸入特征等,然后在特征庫中搜索特征相似的QoS使用信息,并以此為基礎進行協同過濾預測.和傳統的協同過濾方法相比,該方法的預測效率和準確率都有一定的提升,但是該方法在預測QoS前大多假設特征庫已經建立好,且特征庫中已存在大量的特征QoS信息,否則難以保證QoS的預測準確度.在實際中影響服務QoS的環境特征因素很多,很難建立完備的特征QoS信息庫,因此該類方法面臨較大的應用困難.

Zheng等［12-14］認為用戶對服務的QoS體驗由少量隱含因子決定,提出建立合理的矩陣因子分解模型對已有的QoS觀測數據進行擬合,從而挖掘出影響用戶QoS體驗的隱含特征,進而為用戶提供個性化的QoS預測.與文獻［10,11］中建立顯式的特征模式不同,矩陣分解模型技術從已有的QoS觀測數據出發,挖掘觀測數據中包含的隱含特征,算法實現簡單,有效性高,更適用于現實中的大規模服務QoS預測問題.Zheng等［12-14］將矩陣因子分解問題轉化為損失函數的最優化問題,采用梯度下降法進行求解,不足之處在于算法收斂速度較緩慢,且收斂結果對于迭代步長的選擇較靈敏.

本文提出一種通過挖掘已有QoS觀測數據中的近鄰信息和隱含特征信息而實現服務QoS預測的方法.首先假設QoS觀測數據產生于一個低維線性模型和高斯噪聲的疊加,進而將稀疏QoS矩陣下的QoS預測問題轉化為模型參數的EM估計問題,然后提出一種結合近鄰信息的非負矩陣分解算法NCNMF＋EM對該問題進行求解.由于算法綜合利用了QoS矩陣中的近鄰信息和隱含特征信息,可以實現對不同類型QoS屬性值的準確預測.

1 QoS預測模型

QoS是描述Web服務質量的一系列非功能屬性的集合,通常包括價格、響應時間、吞吐量、可靠性和可用性等.假如QoS預測系統包含n個服務和m個用戶,則服務的QoS使用信息可以采用n×m的用戶-服務QoS矩陣R表示,矩陣R中的任意項Rij表示用戶j調用服務i時的QoS值.在現實中,大部分用戶只調用過少量的服務,因此QoS矩陣R包含許多缺失項,預測系統的目標是利用R中的已知QoS信息對這些缺失項進行準確的預測.例如,當用戶j未調用服務i時,則QoS矩陣中的Rij為缺失項,需要對這些缺失項進行預測.

筆者希望通過矩陣因子分解模型技術找到一個低維線性模型X＝UV對QoS矩陣R進行逼近,則缺失項Rij的預測值可以通過U的第i行與V的第j列取向量內積得到.其中U為n×k矩陣,V為k×m矩陣,k為特征因子的個數.

QoS矩陣因子分解模型具有一定的物理意義.假設服務的QoS可以由隱含的k個特征因子決定,這些特征因子可以是網絡環境特征、服務器環境特征和用戶輸入特征等.具體來說,網絡環境特征可以包含網絡帶寬、網絡吞吐量等,服務器環境特征可以包含服務器的CPU利用率、內存利用率、進程占有率、并發訪問率等,用戶特征可以包含用戶輸入大小、任務類型、地理位置等.假如對于每個特征因子,都對服務的QoS值有固定的影響基準值,比如對于某個信用卡號驗證服務,QoS（如響應時間）受輸入的信用卡號數量影響較大,而受所處的地理位置和網絡吞吐量影響較小,因此可以認為對于該服務,用戶輸入特征的QoS影響基準值較高；對于某個視頻傳輸服務,用戶位置離服務器越遠、網絡吞吐量越低,則用戶體驗到的服務響應時間越長,因此對于該類服務,用戶位置和網絡吞吐量的QoS影響基準值較高.將模型中的U稱為QoS基矩陣,并將U寫成列向量形式U＝［U1,U2,…,Uk］,則Ud（d＝1,2,…,k）表示第d個特征因子對各個服務的QoS影響基準值；V稱為權重矩陣,每一列對應為某個用戶對這k個特征因子賦予的權重,反映了該用戶對這些特征因子的敏感程度.用戶j對服務i的QoS體驗值可以表示為服務i在這k個特征因子上的QoS基準值的某個線性組合,系數為用戶j對相應特征因子賦予的權重值,如下所示：

式中：Xij為用戶j對服務i的QoS估計值,Uid為第d個特征因子對服務i的QoS基準值,Vdj為用戶j對第d個特征因子賦予的權重.

QoS屬性值（如響應時間、吞吐量、可靠性、可用性等）通常是非負的,所以U中的元素應滿足非負性約束.根據前面假設可知,用戶對服務的QoS體驗值為一系列對特征因子的QoS基準值的線性組合,即用戶對服務的整體QoS感知,由對各個特征因子的局部感知組合而成.為了更好地表征整體是由局部組成的這一直觀認識,V中的元素也應滿足非負性約束.與文獻［12,15,16］類似,假設用戶對服務的QoS體驗值可以由一個低維線性模型和高斯噪聲的疊加得到,即R＝X＋Z,Z為噪聲矩陣, Zij滿足期望為0、標準差為σij的高斯分布.QoS預測的矩陣因子分解模型由下式表示.

為了簡化問題,假設高斯噪聲的標準差σij均取統一常量σ,則Rij滿足期望為Xij、標準差為σ的高斯分布,記為Rij～N（Xij,σ2）.由以上定義可知, Xij是未知的參數,須對其進行估計.

2 QoS預測模型的參數估計

假設用戶調用不同服務體驗到的QoS值是獨立的,即QoS矩陣R的每個元素是統計獨立的,則對于QoS觀測矩陣R,變量X的似然函數為

由1章可知,Rij～N（Xij,σ2）,則Rij的概率密度函數為

等式兩邊取對數,可得對數似然函數：

假如R中的觀測數據是完整的,即不含缺失項時,則可以采用極大似然估計法估計模型參數X.

在現實應用中,絕大部分用戶只對其中少量服務有過調用經歷,因此用戶-服務QoS矩陣R是包含大量缺失項的稀疏QoS矩陣.鑒于此,采用EM算法最大化QoS矩陣中已知觀測數據的似然函數,以獲取模型參數X的估計.EM算法通常用于在不完整數據條件下的參數最大似然估計［17-18］.EM算法在每次迭代時包含2個步驟：E步,利用對隱含變量的現有估計值,計算完整數據的對數似然函數的期望；M步,通過最大化在E步求得的期望得到當前的參數估計值,將該估計值用于下一次迭代中的E步.通過交替執行這2個步驟,使模型參數收斂.

將QoS矩陣R中的已知觀測數據和未觀測數據分別定義為Ro和Ru,假設EM算法在第t次迭代后獲得的X的估計值為Xt,則在第t＋1次迭代時,包含以下2個步驟.

1）E步：計算完整QoS矩陣數據的對數似然函數的期望,記為

對于?Rij∈Ru,Rij～N（,σ2）,可得

將式（9）代入式（8）,并令Ru中的元素個數為C,可得

2）M步：通過最大化Q（X Xt）來獲得當前X的估計值.

m、n、σ和C均為常量,因此

令矩陣Rt＋1表示第t＋1次EM迭代時的完整矩陣,其中缺失項Rij∈Ru采用第t次迭代時的模型估計值X填充,將式（1）代入式（12）,可得

式中：·F表示矩陣的Frobenius范數.

由式（13）可知,可以通過尋找非負QoS基矩陣U和權重矩陣V使得 Rt＋1－UV2F最小,得到當前M步X的估計值.假如將 Rt＋1－UV2F作為目標函數,則可以通過對Rt＋1進行非負矩陣因子分解（NMF,non-negative matrix factorization）求解U和V.NMF最早由Lee等［19］提出用于提取人臉圖像的局部特征和文本中的語義特征,通過將非負矩陣分解為2個低維非負矩陣的乘積,挖掘原始矩陣的局部特征,實現對高維原始矩陣的降維擬合.對Rt＋1的NMF操作步驟如下.首先產生非負隨機數作為U和V的初始值,然后采用Lee等［20］提出的乘性更新法則,迭代求解U和V：

Lee在文獻［20］中證明了在該迭代規則下,目標函數 Rt＋1－UV單調不增,并在若干次迭代后趨于收斂,且矩陣U和V的非負性可以得到保證.

通過對Rt＋1的NMF操作,可得Rt＋1的逼近矩陣UV,從而得到當前M步X的估計值X＝UV.該估計值將被用于下一次EM迭代中的E步計算中.

綜上可知,采用EM算法估計參數X包含如下步驟：首先對X賦初始值,然后在每次迭代的E步中使用X對稀疏QoS矩陣R中的缺失項進行填充,在M步中對填充后的完整矩陣R進行非負矩陣分解,得到R的逼近矩陣UV,以此更新X并用于下一次迭代中的E步.該過程不斷重復,直到X收斂于某個局部最優值.

3 QoS預測算法NCNMF＋EM

矩陣分解模型難以檢測到相似用戶或者相似服務之間的關聯關系［12］.實際上,充分挖掘出這種近鄰關系,并用于NMF的求解過程,可以有效提高對QoS的預測準確度.尤其當QoS矩陣非常稀疏時,單獨采用NMF方法或近鄰法都難以保證較優的預測準確度.本節提出一種結合近鄰信息的非負矩陣分解算法NCNMF＋EM（neighbor information combined non-negative matrix factorization with EM procedures）,以實現稀疏QoS矩陣下的模型參數EM估計.算法首先采用基于服務的最近鄰協同過濾法預測原始QoS矩陣R中的缺失QoS,得到完整的QoS矩陣,并將該完整矩陣作為2章所述的EM算法中模型參數X的初始估計值；然后采用NMF算法更新X,通過交叉執行E步和M步,使X趨于收斂,則R中缺失項的預測值即為X中的對應項.算法由于在模型參數的EM估計中引入了近鄰先驗信息,可以有效地提高EM算法的收斂速度和最終收斂值,從而保證了算法的QoS預測準確度和預測效率.NCNMF＋EM算法的具體描述如下.

算法1 NCNMF＋EM.

輸入：稀疏QoS矩陣R,R中的未觀測數據集Ru,特征因子個數k,最近鄰數N,EM最大迭代次數tmax,NMF的最大迭代次數qmax.

輸出：缺失項得到預測的完整QoS矩陣R.

NCNMF＋EM算法的第1步表示產生滿足［0, 1］均勻分布的隨機矩陣,以初始化QoS基矩陣U和權重矩陣V.第2～7步表示采用最近鄰協同過濾方法預測R中的缺失值,然后以預測值填充后的完整矩陣作為X的初始值,詳見3.1和3.2節.第10步判斷目標函數是否滿足收斂條件,假如滿足收斂條件則算法結束,其中ε為某個足夠小的正數.第13～19步表示采用式（14）所述的乘性法則對因子矩陣U和V進行迭代更新,以實現對R的非負矩陣因子分解,從而得到R的低維逼近矩陣UV,其中16～18步通過對U中的每個元素除以其所在列的所有元素之和,實現對U的規范化操作,以保證矩陣因子分解的唯一性,?和⊙分別代表Hardmard乘和除.第21步表示將當前的逼近矩陣UV賦給X,作為下一次EM迭代中的輸入參數.經過若干次迭代后, X將趨于收斂,用X中元素取代R中的未觀測項將得到包含最終QoS預測值的完整QoS矩陣.

3.1 近鄰信息挖掘

假設QoS矩陣R中的Ria＝0,即不存在用戶a調用服務i的QoS記錄,則可以采用基于服務的最近鄰協同過濾法預測Ria.首先采用改進的皮爾遜相關系數計算服務i與其他服務的相似度.皮爾遜相關系數主要用于度量2個變量之間的相關性,因具有易于實現和精度高等特點,被廣泛應用于各類推薦系統.服務i和服務r的相似度sim（i,r）可由式（15）所示的改進的皮爾遜相關系數計算得到：

式中：

sim（i,r）的取值為［－1,1］,sim（i,r）越大說明兩服務越相似.令Ui和Ur分別表示調用過服務i和服務r的用戶集,則Uir＝Ui∩Ur表示調用過服務i和服務r的共同用戶集.Rij表示用戶j觀測到的服務i的QoS值,表示Ui中用戶觀測到的服務i的QoS算術平均值.式（15）與傳統的皮爾遜相關系數公式的區別在于考慮了以下2種極端情況.

1）當兩服務的共同用戶集為?時,無法采用傳統的皮爾遜相關系數得到有效值.

2）H＝0的情況,采用傳統的方法得到的相似度為無窮大,為無效取值.H＝0的情況是可能存在的,比如令服務i和服務r的共同用戶為a和b,假如a和b調用服務i時的QoS值相等,并且a和b調用服務r的QoS值相等,此時H＝0.

由于QoS矩陣極度稀疏的,上述2種極端情況很可能出現,式（15）在上述2種極端情況下,令相似度sim（i,r）＝0,以防止出現非法的相似度計算結果.完成服務i與其他所有服務的相似度計算步驟后,令與服務i相似度最高的N個服務組成的集合T（i）稱為服務i的Top-N近鄰服務集.

3.2 基于服務的最近鄰協同過濾

得到服務i的Top-N近鄰服務集T（i）后,則可以利用Top-N近鄰服務集中的QoS信息對Ria進行協同過濾預測,如下所示：

式中：r為服務i的近鄰服務,Rra表示用戶a對服務r的QoS體驗值.由于QoS矩陣較稀疏,Rra以高概率等于零,在該情況下計算得到的預測值不準確.為了解決該問題,可以在協同過濾預測前采用服務的算術平均值填充近鄰集中的缺失值.由于相似度可取負值,采用式（16）計算得到的QoS預測值也可能為負值,而現實中的服務QoS值是非負的,本文采用服務的算術平均值取代這部分負值.

通過以上所述的基于服務的最近鄰協同過濾法,原始QoS矩陣中的缺失項將得到較準確的預測值.采用該預測值對原始QoS矩陣進行填充可得完整的QoS矩陣,該完整矩陣將作為NCNMF-EM算法中模型參數X的初始估計值.

4 算法復雜度分析

NCNMF＋EM算法的時間復雜度主要包括近鄰信息挖掘、Top-N最近鄰協同過濾計算和QoS預測模型參數EM估計3個部分.在實際系統中,通?？梢圆捎秒x線方式計算服務之間的相似度,并存儲Top-N近鄰集信息,因此服務近鄰信息可以采用定期更新的方式,無需在線計算.本文只考慮Top-N最近鄰協同過濾計算和模型參數EM估計2個部分的在線計算時間復雜度.假設QoS矩陣R是n×m矩陣,且共有W個待預測項,EM迭代次數為tmax, NMF算法的最大迭代次數為qmax,特征因子個數為k.Top-N最近鄰協同過濾計算的時間復雜度為O（NW）；對R進行一次NMF操作的時間復雜度為O（qmaxkmn）,由于模型參數的EM估計共包含tmax次NMF,復雜度為O（tmaxqmaxkmn）.綜上可知, NCNMF＋EM算法的總時間復雜度為O（NW＋tmaxqmaxkmn））.由于W≤mn且N、tmax、qmax和k均為常量,隨著QoS矩陣規模mn的增大,NCNMF＋EM算法的運行時間呈線性增長,具有較高的有效性,可以適用于大規模的QoS預測問題.

5 實驗分析

采用網絡上真實的QoS數據集 WSDREAM［4］對NCNMF＋EM算法的預測準確度和時間性能進行實驗評估,研究算法中的Top-N、EM迭代次數tmax、NMF算法迭代次數qmax和特征因子個數k等參數對預測準確度的影響.WS-DREAM數據集記錄了30多個不同國家的339個用戶調用73個國家的5 825個Web服務的QoS信息.由于該數據集目前只包含響應時間和吞吐量2個QoS屬性的信息,實驗僅采用響應時間和吞吐量QoS數據對算法進行評估.為了便于分析,從數據集中分別獲取了300×3000的響應時間QoS矩陣和300× 3000的吞吐量QoS矩陣.實驗環境如下：Intel Core2 Quad 2.50 GHz CPU,4 GB RAM,操作系統為Windows XP,算法實現工具為Matlab 7.1.

5.1 準確度評估

平均絕對誤差（MAE）是推薦系統中評價預測精度最常用的度量標準,反映了系統預測值與實際值的平均絕對偏差［21］.MAE的定義如下：

式中：W為QoS矩陣中的待預測項數,Rij為用戶j體驗到的服務i的QoS實際值,為算法的QoS預測值.在實際應用中,不同QoS屬性的取值范圍不同,如Web服務的響應時間通常取0～20 s,吞吐量通常取0～1 000 kbit／s［12］,因此采用歸一化平均絕對誤差（NMAE）對算法的QoS預測準確度進行度量,NMAE越小表示算法的預測準確度越高.NMAE的定義如下：

為了驗證NCNMF＋EM算法的QoS預測準確度,與Zheng等［9,19］提出的其他算法進行對比.在該實驗中,將QoS數據集分為5個不相交的300× 600矩陣,采用5折交叉驗證的思想,分別對這5個 QoS矩陣進行預測.最后取5次實驗的NAME均值作為實驗結果,以降低數據集誤差對算法的影響.在實際應用中,QoS矩陣通常是極度稀疏的,因此在每次實驗中,都通過隨機移除QoS矩陣中的若干項,得到不同矩陣密度的稀疏QoS矩陣.算法的目標是對這些移除項的QoS進行預測,利用這些移除項的原有值對預測結果的準確度進行評估.在該實驗中,QoS矩陣的矩陣密度以0.01為步長從0.04遞增到0.13,研究算法在不同矩陣密度下的預測準確度.

圖1 不同矩陣密度下的響應時間預測結果對比Fig.1 Prediction performance comparison on response time w.r.t.density of matrix

圖2 不同矩陣密度下的吞吐量預測結果對比Fig.2 Prediction performance comparison on throughput w.r.t.the density of matrix

圖1、2分別給出不同算法在不同矩陣密度D下的響應時間預測結果和吞吐量預測結果.圖中, IPCC表示傳統的基于服務的協同過濾算法,參數Top-N取10.IPCC＋AF表示采用3.1、3.2節所述的改進的基于服務協同過濾算法,參數Top-N取10.WSRec為文獻［9］提出的混合協同過濾算法,參數Top-N和λ分別取文獻所述的最優值10和0.2.BNMF（Basic NMF）表示文獻［19］提出的基本NMF算法,BNMF直接采用式（14）對稀疏QoS矩陣進行因子分解擬合,未考慮QoS矩陣的稀疏性,也未引入QoS矩陣中的近鄰信息,BNMF中的參數特征因子個數取10,迭代次數取100.NCNMF＋EM表示本文提出的結合近鄰信息的NMF算法,算法的參數Top-N取10,NMF算法迭代次數qmax取100,特征因子個數k取10.圖中,NCNMF＋1EM表示EM迭代次數tmax為1,NCNMF＋5EM表示EM迭代次數tmax為5,以此類推.

由圖1、2表明,隨著QoS矩陣密度的增大,所有算法的NMAE值都呈下降趨勢,即算法的預測準確度呈上升趨勢.這是由于QoS信息越豐富,越有利于近鄰關系和隱含特征的挖掘,從而提升算法的預測準確度.從圖1、2可以發現,NCNMF＋EM只需1次EM迭代,對響應時間和吞吐量的預測準確度普遍優于其他幾種算法；當EM迭代次數增大時,算法的預測準確度得到大幅提升.從圖1、2可以發現,隨著EM迭代次數的增加,NCNMF＋EM算法對響應時間和吞吐量的預測準確度的提升幅度逐漸縮小,并分別于20次和25次左右迭代后收斂到最優值.從圖1、2的對比可以發現,WSRec對響應時間的預測準確度較高,且隨著矩陣密度的增大準確度提升明顯,但是對吞吐量的預測準確度不理想,并且準確度沒有隨矩陣密度的增大而呈現明顯的增長趨勢.這可能是由于不同用戶體驗到的Web服務的響應時間相較于吞吐量而言更穩定,因此近鄰信息對于響應時間的預測貢獻率較大,對于吞吐量的預測貢獻率較小.NCNMF＋EM算法對于2種QoS的預測準確率都較高,表明本文提出的結合近鄰信息和隱含特征信息的方法可以更好地通用于不同類型的QoS屬性值預測.

5.2 有效性實驗

通過對比NCNMF＋EM與其他算法的運行時間t,以評估NCNMF＋EM的時間性能.在本實驗中,用戶數固定為300,服務數n以100為步長從100遞增到1 000,以獲取不同規模的用戶-服務QoS矩陣,研究算法在不同矩陣規模下的時間性能.所有算法的參數設置與5.1節相同,由于響應時間和吞吐量的預測時間相當,采用響應時間QoS矩陣作為本次實驗數據集,矩陣密度取0.1.從圖3可以發現,隨著矩陣規模的增大,所有算法的運行時間都相應增長,其中BNMF算法的增長幅度最小,效率最高；WSRec的增長幅度最大,效率最低；NCNMF＋EM與IPCC和IPCC＋AF的運行時間相當,均隨著矩陣規模的增大呈線性增長,有效性較高,因此可以應用于大規模的QoS預測問題.從圖3可以發現,NCNMF＋EM隨著EM迭代次數的增加,運行時間沒有大幅增加,而是線性增長.結合圖1、2可知,NCNMF＋EM通過犧牲部分時間性能,可以顯著提升QoS預測的準確度,在實際應用中須在算法效率和算法預測準確度之間進行權衡.

圖3 不同矩陣規模下的算法時間性能對比Fig.3 Time performance comparison w.r.t.matrix scale

5.3 收斂性實驗

圖4 NCNMF＋EM和BNMF的響應時間預測收斂結果對比Fig.4 Convergence comparison between NCNMF＋EM and BNMF for response time prediction

圖5 NCNMF＋EM和BNMF的吞吐量預測收斂結果對比Fig.5 Convergence comparison between NCNMF＋EM and BNMF for throughput prediction

該實驗對NCNMF＋EM與BNMF的收斂性能進行對比.實驗數據分別采用300×600的響應時間和吞吐量QoS矩陣.EM迭代次數取1,特征因子數均取10,QoS矩陣密度為0.05.圖4、5表明,NCNMF＋EM的收斂速度和最終收斂值都明顯優于BNMF,這主要是由于前者在NMF算法中引入了近鄰信息,指導了NMF算法的優化方向,因此可以較快地收斂到最優值.從圖4、5可以發現,NCNMF＋EM算法在響應時間和吞吐量的預測中,均在迭代100次左右后收斂,因此在其他實驗中,NCNMF＋EM算法中的NMF迭代次數qmax均設為100.

5.4 Top-N對算法準確度的影響

本實驗中,將Top-N以3為步長從3遞增到30,研究Top-N對NCNMF＋EM預測準確度的影響.算法參數tmax取1,qmax取100,k取10,結果取10次獨立運行的平均值.圖6、7表明,當Top-N小于某個閾值時,增大Top-N可以提高算法的預測準確度,但超過該閾值時,增加Top-N會降低算法的預測準確度.原因是當Top-N較小時,增大Top-N有利于挖掘出更多的近鄰信息,從而提高算法的預測準確度；另一方面,由于QoS矩陣的稀疏度較高造成服務的共同用戶數較少,因此與目標服務相似的近鄰服務數是有限的,此時若Top-N較高,則將在協同過濾預測中引入大量不相似服務的QoS信息,因此導致預測準確度下降.在實際應用中,可以通過設定相似度閾值,使得超過該閾值的服務被認定為近鄰服務,以此動態地確定合理的Top-N.從圖6、7可以發現,響應時間和吞吐量的最佳Top-N分別為18和12,表明在預測響應時間時,近鄰服務數相對較多.該結果進一步驗證了5.1節的猜測,即不同用戶體驗到的Web服務的響應時間相較于吞吐量而言更穩定.

圖6 Top-N對響應時間預測準確度的影響Fig.6 Impact of Top-N on response time prediction

圖7 Top-N對吞吐量預測準確度的影響Fig.7 Impact of Top-N on throughput prediction

5.5 特征因子數對算法準確度的影響

在該實驗中,特征因子數k以3為步長從3遞增到30,研究NCNMF＋EM在取不同k時的預測準確度.算法的參數EM迭代次數tmax取1,Top-N取10, NMF迭代次數qmax取100,QoS矩陣密度為0.05.

如圖8、9所示分別為NCNMF＋EM在取不同特征因子數時的響應時間和吞吐量預測結果,結果為運行10次的平均值.由圖8、9表明,當k較小時,隨著k的增加,算法的預測準確度明顯上升；當k超過某個閾值時,隨著k的增加會導致預測準確度下降.原因是當k過小時,從QoS矩陣中挖掘的隱含特征過少,此時的因子模型難以較好地擬合原始QoS矩陣,導致預測準確度較低；當k過大時,會造成模型的過擬合問題,從而導致算法準確度下降.一般k取滿足k?mn／（m＋n）的正整數,在實際應用中,可以根據實際問題選擇若干個k值進行實驗驗證,以確定最優的k值.

圖8 特征因子數k對響應時間預測準確度的影響Fig.8 Impact of k on response time prediction

圖9 特征因子數k對吞吐量預測準確度的影響Fig.9 Impact of k on throughput prediction

6 結 語

本文提出采用低維線性模型對QoS觀測數據進行擬合,將QoS預測問題轉化為稀疏QoS矩陣下的模型參數EM估計問題,提出一種結合近鄰信息的非負矩陣分解算法NCNMF＋EM對該問題進行求解.該算法通過挖掘QoS矩陣中的近鄰信息和隱含特征信息,可以實現對服務QoS的準確預測.理論分析和實驗結果表明,NCNMF＋EM算法的準確度和效率較高,實現簡單,可以適用于大規模的不同類型QoS的預測問題.

本文采用的QoS數據集來源于對網絡上真實服務的運行監控,因此是客觀可信的.在實際應用中,通常還存在來源于服務供應商和用戶反饋的不可信QoS數據.下一步將研究不可信QoS數據的濾除方法,以提高在不可信QoS數據條件下對服務QoS的預測準確度.

［1］SU K,MA L,GUO X,et al.An efficient discrete invasive weed optimization algorithm for web services selection［J］.Journal of Software,2014,9（3）：709- 715.

［2］MOSER O,ROSENBERG F,DUSTDAR S.Domain-specific service selection for composite services［J］.IEEE Trans.on Software Engineering,2012,38（4）：828- 842.

［3］SU K,MA L,GUO X,et al.An efficient parameter adaptive genetic algorithm for service selection with endto-end QoS constraints［J］.Journal of Computational Information Systems,2014,10（2）：581- 588.

［4］ZHENG Z,ZHANG Y,LYU R M.Distributed QoS evaluation for real-world web services［C］//IEEE International Conference on Web Services.Miami：IEEE, 2010：83- 90.

［5］YU T,ZHANG Y,LIN K.Efficient algorithms for web services selection with end-to-end QoS constraints［J］.ACM Transactions on the Web,2007,1（1）：1- 26.

［6］XIAO R.Constructing a novel QoS aggregated model based on KBPP［J］.Communications in Computer and Information Science,2010,107（3）：117- 126.

［7］ALRIFAI M,RISSE T.Combining global optimization with local selection for efficient QoS-aware service composition［C］//Proceeding of the 18th International Conference on World Wide Web.New York：［s.n.］,2009：881- 882.

［8］SHAO L,ZHANG J,WEI Y,et al.Personalized QoS prediction for web service via collaborative filtering［C］//IEEE International Conference on Web Services.Salt Lake City：IEEE,2007：439- 446.

［9］ZHENG Z,MA H,LYU R M,et al.WSRec：a collaborative filtering based web service recommender system［C］//IEEE International Conference on Web Services.Los Angeles：IEEE,2009：437- 444.

［10］劉志中,王志堅,周曉峰,等.基于事例推理的Web服務QoS動態預測研究［J］.計算機科學,2011, 38（2）：119- 121.

LIU Zhi-zhong,WANG Zhi-jian,ZHOU Xiao-feng,et al.Dynamic prediction method for web service QoS based on case-based reasoning［J］.Computer Science, 2011,38（2）：119- 121.

［11］張莉,張斌,黃利萍,等.基于服務調用特征模式的個性化Web服務QoS預測方法［J］.計算機研究與發展, 2013,50（5）：1070- 1071.

ZHANG Li,ZHANG Bin,HUANG Li-ping,et al.A personalized web service quality prediction approach based on invoked feature model［J］.Journal of Computer Research and Development,2013,50（5）：1070- 1071.

［12］ZHENG Z,MA H,LYU R M,et al.Collaborative web service QoS prediction via neighborhood integrated Matrix factorization［J］.IEEE Transactions on Services Computing,2013,6（3）：289- 299.

［13］ZHANG Y,ZHENG Z,LYU R M.WSPred：a timeaware personalized QoS prediction framework for web services［C］//IEEE International Symposium on Software Reliability Engineering.Hiroshima：IEEE,2011：210- 219.

［14］彭飛,鄧浩江,劉磊.面向個性化服務推薦的QoS動態預測模型［J］.西安電子科技大學學報：自然科學版, 2013,40（4）：207- 213.

PENG Fei,DENG Hao-jiang,LIU Lei.QoS-aware temporal prediction model for personalized service recommendation［J］.Journal of Xidian University,2013, 40（4）：207- 213.

［15］ZHANG S,WANG W,FORD J,et al.Learning from incomplete ratings using non-negative matrix factorization［C］//6th SIAM Conference on Data Mining.Seoul：［s.n.］,2006：548- 552.

［16］SALAKHUTDINOV R,MNIH A.Probabilistic matrix factorization［C］//Proceeding of Advances in Neural Information Processing Systems.Denver：［s.n.］, 2007：1257- 1264.

［17］ZHANG S,WANG W,FORD J,et al.Using singular value decomposition approximation for collaborative filtering［C］//Proceeding of the 7th IEEE International Conference on E-Commerce Technology.Munich：IEEE,2005：1- 8.

［18］SREBRO N,JAAKKOLA T.Weighted low rank approximation［C］//Proceeding of the 20th International Conference on Machine Learning.Washington：［s.n.］,2003.

［19］LEE D D,SEUNG H S.Learning the parts of objects by non-negative matrix factorization［J］.Nature, 1999,401（6755）：788- 791.

［20］LEE D D,SEUNG H S.Algorithms for non-negative matrix factorization［C］//Proceeding of Advances in Neural Information Processing Systems.Denver：［s.n.］,2000：556- 562.

［21］HU R,PU P.Enhancing collaborative filtering systems with personality information［C］//Proceeding of The 5th ACM Conference on Recommender Systems.New York：［s.n.］,2011：197- 204.

Non-negative matrix factorization model for Web service QoS prediction

SU Kai1,2,MA Liang-li2,SUN Yu-fei2,GUO Xiao-ming2
（1.Department of Equipment Economics and Management,Naval University of Engineering,Wuhan 430033,China）（2.Department of Computer Engineering,Naval University of Engineering,Wuhan 430033,China）

An effective Web service QoS prediction approach was presented by utilizing the neighbor information and latent feature information of the observed QoS data.A matrix factor model for service QoS prediction was presented.Then an expectation-maximization（EM）estimation scenario was designed to learn the model based on the available QoS data.A neighbor information combined non-negative matrix factorization algorithm NCNMF＋EM was proposed to implement the scenario.The approach fully utilizes the information of the observed data,and can achieve high prediction accuracy.Experimental results demonstrate that the approach achieves better prediction accuracy than other state-of-the-art approaches.The computational time of the algorithm is linear with the scale of QoS matrix,which indicates that the approach is applicable to large scale QoS prediction problem.

Web service；service selection；QoS prediction；matrix factor model；non-negative matrix factorization；expectation-maximization estimation

10.3785／j.issn.1008-973X.2015.07.022

TP 393

A

1008- 973X（2015）07- 1358- 09

2014- 05- 22. 浙江大學學報(工學版)網址：www.journals.zju.edu.cn／eng

總裝預研基金資助項目（9140A27040413JB11407）；國家自然科學基金資助項目（61170217）.

蘇凱（1987－）,男,博士,助理研究員,從事服務計算的研究.ORCID：E-mail：keppelsue＠163.com