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

（1.海軍工程大學(xué)裝備經(jīng)濟(jì)管理系,湖北武漢430033；2.海軍工程大學(xué)計(jì)算機(jī)工程系,湖北武漢430033）

面向Web服務(wù)QoS預(yù)測(cè)的非負(fù)矩陣分解模型

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

（1.海軍工程大學(xué)裝備經(jīng)濟(jì)管理系,湖北武漢430033；2.海軍工程大學(xué)計(jì)算機(jī)工程系,湖北武漢430033）

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

Web服務(wù)；服務(wù)選擇；QoS預(yù)測(cè)；矩陣因子模型；非負(fù)矩陣分解；期望最大化估計(jì)

隨著Web服務(wù)技術(shù)的發(fā)展,網(wǎng)絡(luò)上出現(xiàn)大量滿足相同功能、但服務(wù)質(zhì)量（quality of service,QoS）不同的候選服務(wù),QoS逐漸成為用戶評(píng)價(jià)Web服務(wù),進(jìn)而選擇服務(wù)的重要依據(jù)［1-3］.在實(shí)際應(yīng)用中,由于不同用戶在調(diào)用服務(wù)時(shí),網(wǎng)絡(luò)環(huán)境、地理位置和服務(wù)運(yùn)行環(huán)境等存在差異,導(dǎo)致他們體驗(yàn)到的服務(wù)QoS不同［4］.用戶需要對(duì)候選服務(wù)的QoS進(jìn)行準(zhǔn)確的預(yù)測(cè),從而為Web服務(wù)的選擇提供可靠的QoS數(shù)據(jù)支撐.

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

文獻(xiàn)［10,11］假設(shè)“當(dāng)外界環(huán)境特征和輸入特征相似時(shí),服務(wù)的QoS相對(duì)穩(wěn)定”,進(jìn)而在為目標(biāo)用戶預(yù)測(cè)服務(wù)的QoS時(shí),首先探測(cè)用戶的環(huán)境特征和輸入特征等,然后在特征庫(kù)中搜索特征相似的QoS使用信息,并以此為基礎(chǔ)進(jìn)行協(xié)同過(guò)濾預(yù)測(cè).和傳統(tǒng)的協(xié)同過(guò)濾方法相比,該方法的預(yù)測(cè)效率和準(zhǔn)確率都有一定的提升,但是該方法在預(yù)測(cè)QoS前大多假設(shè)特征庫(kù)已經(jīng)建立好,且特征庫(kù)中已存在大量的特征QoS信息,否則難以保證QoS的預(yù)測(cè)準(zhǔn)確度.在實(shí)際中影響服務(wù)QoS的環(huán)境特征因素很多,很難建立完備的特征QoS信息庫(kù),因此該類(lèi)方法面臨較大的應(yīng)用困難.

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

本文提出一種通過(guò)挖掘已有QoS觀測(cè)數(shù)據(jù)中的近鄰信息和隱含特征信息而實(shí)現(xiàn)服務(wù)QoS預(yù)測(cè)的方法.首先假設(shè)QoS觀測(cè)數(shù)據(jù)產(chǎn)生于一個(gè)低維線性模型和高斯噪聲的疊加,進(jìn)而將稀疏QoS矩陣下的QoS預(yù)測(cè)問(wèn)題轉(zhuǎn)化為模型參數(shù)的EM估計(jì)問(wèn)題,然后提出一種結(jié)合近鄰信息的非負(fù)矩陣分解算法NCNMF＋EM對(duì)該問(wèn)題進(jìn)行求解.由于算法綜合利用了QoS矩陣中的近鄰信息和隱含特征信息,可以實(shí)現(xiàn)對(duì)不同類(lèi)型QoS屬性值的準(zhǔn)確預(yù)測(cè).

1 QoS預(yù)測(cè)模型

QoS是描述Web服務(wù)質(zhì)量的一系列非功能屬性的集合,通常包括價(jià)格、響應(yīng)時(shí)間、吞吐量、可靠性和可用性等.假如QoS預(yù)測(cè)系統(tǒng)包含n個(gè)服務(wù)和m個(gè)用戶,則服務(wù)的QoS使用信息可以采用n×m的用戶-服務(wù)QoS矩陣R表示,矩陣R中的任意項(xiàng)Rij表示用戶j調(diào)用服務(wù)i時(shí)的QoS值.在現(xiàn)實(shí)中,大部分用戶只調(diào)用過(guò)少量的服務(wù),因此QoS矩陣R包含許多缺失項(xiàng),預(yù)測(cè)系統(tǒng)的目標(biāo)是利用R中的已知QoS信息對(duì)這些缺失項(xiàng)進(jìn)行準(zhǔn)確的預(yù)測(cè).例如,當(dāng)用戶j未調(diào)用服務(wù)i時(shí),則QoS矩陣中的Rij為缺失項(xiàng),需要對(duì)這些缺失項(xiàng)進(jìn)行預(yù)測(cè).

筆者希望通過(guò)矩陣因子分解模型技術(shù)找到一個(gè)低維線性模型X＝UV對(duì)QoS矩陣R進(jìn)行逼近,則缺失項(xiàng)Rij的預(yù)測(cè)值可以通過(guò)U的第i行與V的第j列取向量?jī)?nèi)積得到.其中U為n×k矩陣,V為k×m矩陣,k為特征因子的個(gè)數(shù).

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

式中：Xij為用戶j對(duì)服務(wù)i的QoS估計(jì)值,Uid為第d個(gè)特征因子對(duì)服務(wù)i的QoS基準(zhǔn)值,Vdj為用戶j對(duì)第d個(gè)特征因子賦予的權(quán)重.

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

為了簡(jiǎn)化問(wèn)題,假設(shè)高斯噪聲的標(biāo)準(zhǔn)差σij均取統(tǒng)一常量σ,則Rij滿足期望為Xij、標(biāo)準(zhǔn)差為σ的高斯分布,記為Rij～N（Xij,σ2）.由以上定義可知, Xij是未知的參數(shù),須對(duì)其進(jìn)行估計(jì).

2 QoS預(yù)測(cè)模型的參數(shù)估計(jì)

假設(shè)用戶調(diào)用不同服務(wù)體驗(yàn)到的QoS值是獨(dú)立的,即QoS矩陣R的每個(gè)元素是統(tǒng)計(jì)獨(dú)立的,則對(duì)于QoS觀測(cè)矩陣R,變量X的似然函數(shù)為

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

等式兩邊取對(duì)數(shù),可得對(duì)數(shù)似然函數(shù)：

假如R中的觀測(cè)數(shù)據(jù)是完整的,即不含缺失項(xiàng)時(shí),則可以采用極大似然估計(jì)法估計(jì)模型參數(shù)X.

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

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

1）E步：計(jì)算完整QoS矩陣數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的期望,記為

對(duì)于?Rij∈Ru,Rij～N（,σ2）,可得

將式（9）代入式（8）,并令Ru中的元素個(gè)數(shù)為C,可得

2）M步：通過(guò)最大化Q（X Xt）來(lái)獲得當(dāng)前X的估計(jì)值.

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

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

式中：·F表示矩陣的Frobenius范數(shù).

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

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

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

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

3 QoS預(yù)測(cè)算法NCNMF＋EM

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

算法1 NCNMF＋EM.

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

輸出：缺失項(xiàng)得到預(yù)測(cè)的完整QoS矩陣R.

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

3.1 近鄰信息挖掘

假設(shè)QoS矩陣R中的Ria＝0,即不存在用戶a調(diào)用服務(wù)i的QoS記錄,則可以采用基于服務(wù)的最近鄰協(xié)同過(guò)濾法預(yù)測(cè)Ria.首先采用改進(jìn)的皮爾遜相關(guān)系數(shù)計(jì)算服務(wù)i與其他服務(wù)的相似度.皮爾遜相關(guān)系數(shù)主要用于度量2個(gè)變量之間的相關(guān)性,因具有易于實(shí)現(xiàn)和精度高等特點(diǎn),被廣泛應(yīng)用于各類(lèi)推薦系統(tǒng).服務(wù)i和服務(wù)r的相似度sim（i,r）可由式（15）所示的改進(jìn)的皮爾遜相關(guān)系數(shù)計(jì)算得到：

式中：

sim（i,r）的取值為［－1,1］,sim（i,r）越大說(shuō)明兩服務(wù)越相似.令Ui和Ur分別表示調(diào)用過(guò)服務(wù)i和服務(wù)r的用戶集,則Uir＝Ui∩Ur表示調(diào)用過(guò)服務(wù)i和服務(wù)r的共同用戶集.Rij表示用戶j觀測(cè)到的服務(wù)i的QoS值,表示Ui中用戶觀測(cè)到的服務(wù)i的QoS算術(shù)平均值.式（15）與傳統(tǒng)的皮爾遜相關(guān)系數(shù)公式的區(qū)別在于考慮了以下2種極端情況.

1）當(dāng)兩服務(wù)的共同用戶集為?時(shí),無(wú)法采用傳統(tǒng)的皮爾遜相關(guān)系數(shù)得到有效值.

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

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

3.2 基于服務(wù)的最近鄰協(xié)同過(guò)濾

得到服務(wù)i的Top-N近鄰服務(wù)集T（i）后,則可以利用Top-N近鄰服務(wù)集中的QoS信息對(duì)Ria進(jìn)行協(xié)同過(guò)濾預(yù)測(cè),如下所示：

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

通過(guò)以上所述的基于服務(wù)的最近鄰協(xié)同過(guò)濾法,原始QoS矩陣中的缺失項(xiàng)將得到較準(zhǔn)確的預(yù)測(cè)值.采用該預(yù)測(cè)值對(duì)原始QoS矩陣進(jìn)行填充可得完整的QoS矩陣,該完整矩陣將作為NCNMF-EM算法中模型參數(shù)X的初始估計(jì)值.

4 算法復(fù)雜度分析

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

5 實(shí)驗(yàn)分析

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

5.1 準(zhǔn)確度評(píng)估

平均絕對(duì)誤差（MAE）是推薦系統(tǒng)中評(píng)價(jià)預(yù)測(cè)精度最常用的度量標(biāo)準(zhǔn),反映了系統(tǒng)預(yù)測(cè)值與實(shí)際值的平均絕對(duì)偏差［21］.MAE的定義如下：

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

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

圖1 不同矩陣密度下的響應(yīng)時(shí)間預(yù)測(cè)結(jié)果對(duì)比Fig.1 Prediction performance comparison on response time w.r.t.density of matrix

圖2 不同矩陣密度下的吞吐量預(yù)測(cè)結(jié)果對(duì)比Fig.2 Prediction performance comparison on throughput w.r.t.the density of matrix

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

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

5.2 有效性實(shí)驗(yàn)

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

圖3 不同矩陣規(guī)模下的算法時(shí)間性能對(duì)比Fig.3 Time performance comparison w.r.t.matrix scale

5.3 收斂性實(shí)驗(yàn)

圖4 NCNMF＋EM和BNMF的響應(yīng)時(shí)間預(yù)測(cè)收斂結(jié)果對(duì)比Fig.4 Convergence comparison between NCNMF＋EM and BNMF for response time prediction

圖5 NCNMF＋EM和BNMF的吞吐量預(yù)測(cè)收斂結(jié)果對(duì)比Fig.5 Convergence comparison between NCNMF＋EM and BNMF for throughput prediction

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

5.4 Top-N對(duì)算法準(zhǔn)確度的影響

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

圖6 Top-N對(duì)響應(yīng)時(shí)間預(yù)測(cè)準(zhǔn)確度的影響Fig.6 Impact of Top-N on response time prediction

圖7 Top-N對(duì)吞吐量預(yù)測(cè)準(zhǔn)確度的影響Fig.7 Impact of Top-N on throughput prediction

5.5 特征因子數(shù)對(duì)算法準(zhǔn)確度的影響

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

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

圖8 特征因子數(shù)k對(duì)響應(yīng)時(shí)間預(yù)測(cè)準(zhǔn)確度的影響Fig.8 Impact of k on response time prediction

圖9 特征因子數(shù)k對(duì)吞吐量預(yù)測(cè)準(zhǔn)確度的影響Fig.9 Impact of k on throughput prediction

6 結(jié) 語(yǔ)

本文提出采用低維線性模型對(duì)QoS觀測(cè)數(shù)據(jù)進(jìn)行擬合,將QoS預(yù)測(cè)問(wèn)題轉(zhuǎn)化為稀疏QoS矩陣下的模型參數(shù)EM估計(jì)問(wèn)題,提出一種結(jié)合近鄰信息的非負(fù)矩陣分解算法NCNMF＋EM對(duì)該問(wèn)題進(jìn)行求解.該算法通過(guò)挖掘QoS矩陣中的近鄰信息和隱含特征信息,可以實(shí)現(xiàn)對(duì)服務(wù)QoS的準(zhǔn)確預(yù)測(cè).理論分析和實(shí)驗(yàn)結(jié)果表明,NCNMF＋EM算法的準(zhǔn)確度和效率較高,實(shí)現(xiàn)簡(jiǎn)單,可以適用于大規(guī)模的不同類(lèi)型QoS的預(yù)測(cè)問(wèn)題.

本文采用的QoS數(shù)據(jù)集來(lái)源于對(duì)網(wǎng)絡(luò)上真實(shí)服務(wù)的運(yùn)行監(jiān)控,因此是客觀可信的.在實(shí)際應(yīng)用中,通常還存在來(lái)源于服務(wù)供應(yīng)商和用戶反饋的不可信QoS數(shù)據(jù).下一步將研究不可信QoS數(shù)據(jù)的濾除方法,以提高在不可信QoS數(shù)據(jù)條件下對(duì)服務(wù)QoS的預(yù)測(cè)準(zhǔn)確度.

［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］劉志中,王志堅(jiān),周曉峰,等.基于事例推理的Web服務(wù)QoS動(dòng)態(tài)預(yù)測(cè)研究［J］.計(jì)算機(jī)科學(xué),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］張莉,張斌,黃利萍,等.基于服務(wù)調(diào)用特征模式的個(gè)性化Web服務(wù)QoS預(yù)測(cè)方法［J］.計(jì)算機(jī)研究與發(fā)展, 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］彭飛,鄧浩江,劉磊.面向個(gè)性化服務(wù)推薦的QoS動(dòng)態(tài)預(yù)測(cè)模型［J］.西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 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. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址：www.journals.zju.edu.cn／eng

總裝預(yù)研基金資助項(xiàng)目（9140A27040413JB11407）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61170217）.

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