基于協(xié)同過(guò)濾的自適應(yīng)Web服務(wù)QoS預(yù)測(cè)方法

莊 崟，郭志川，黃逍穎

(1.江蘇有線技術(shù)研究院有限公司，江蘇 南京 210001；2.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190；3.中國(guó)科學(xué)院大學(xué)，北京 100049)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，Web服務(wù)的便捷性導(dǎo)致用戶對(duì)它的需求逐漸增大。如今大量的Web服務(wù)充斥互聯(lián)網(wǎng)，在增加用戶選擇的同時(shí)，也提出了更高的要求：面對(duì)相同種類和條件下的服務(wù)，除了滿足功能性需求之外，用戶希望得到更高的服務(wù)質(zhì)量(QoS)。目前，服務(wù)QoS預(yù)測(cè)已經(jīng)成為Web服務(wù)領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題[1-6]。這需要根據(jù)一些指標(biāo)來(lái)對(duì)已有的服務(wù)進(jìn)行衡量，在這些指標(biāo)的對(duì)比之下，根據(jù)每一個(gè)用戶的具體需求來(lái)對(duì)用戶進(jìn)行個(gè)性化的服務(wù)推薦，縮小用戶的選擇范圍，從而更高效地享受相關(guān)服務(wù)。

QoS度量有多種方法[7-12]，服務(wù)器端度量的QoS值(價(jià)格、流行度等等)，服務(wù)提供商通常會(huì)在廣告中展示內(nèi)容，這些對(duì)于不同的用戶來(lái)說(shuō)都是相同的，但是在客戶端度量的QoS值(響應(yīng)時(shí)間、吞吐量、服務(wù)可用性等)在不同的用戶之間卻會(huì)因受到不可預(yù)測(cè)的網(wǎng)絡(luò)連接和完全不同的用戶環(huán)境的影響而大相徑庭。需要對(duì)不同的用戶獲得精確的個(gè)人用戶端Web服務(wù)的QoS值，而QoS值的準(zhǔn)確測(cè)量需要對(duì)用戶端得到的Web服務(wù)進(jìn)行評(píng)估，因此選擇一種合適的評(píng)估方法是非常必要的。但是在實(shí)際操作中，從用戶角度去評(píng)測(cè)Web服務(wù)是很困難的。它具有如下缺點(diǎn)：(1)為了得到QoS信息，用戶需要執(zhí)行相關(guān)的服務(wù)調(diào)用，服務(wù)提供者可能會(huì)收取調(diào)用費(fèi)用，同時(shí)會(huì)增加資源消耗；(2)隨著網(wǎng)絡(luò)上的Web服務(wù)數(shù)量的日益增多，測(cè)評(píng)所有的Web服務(wù)將很耗時(shí)；(3)為了連續(xù)監(jiān)視Web服務(wù)的QoS性能，服務(wù)用戶需要定期調(diào)用評(píng)估服務(wù)；(4)為了深度評(píng)測(cè)Web服務(wù)，服務(wù)用戶還需要做更多的工作。因此，為了更好地對(duì)用戶端QoS進(jìn)行評(píng)價(jià)從而做到推薦，目前最流行的做法是對(duì)用戶端的QoS以預(yù)測(cè)的方式進(jìn)行，從而使用戶不需要再對(duì)每個(gè)Web服務(wù)進(jìn)行測(cè)評(píng)，并且可節(jié)約時(shí)間。

采用協(xié)同過(guò)濾的手段已被證明是當(dāng)前預(yù)測(cè)精度最高的方法[13-16]。WSRec算法具有很好的效果[16]，但是目前單一采用協(xié)同過(guò)濾的預(yù)測(cè)精度不高，尤其是在矩陣較為稀疏的情形下。基于此，文中將多種協(xié)同過(guò)濾方法進(jìn)行動(dòng)態(tài)組合，給出了一種基于協(xié)同過(guò)濾的自適應(yīng)QoS服務(wù)預(yù)測(cè)方法，以提升用戶體驗(yàn)。

1 算法描述

提出一種基于協(xié)同過(guò)濾的自適應(yīng)QoS服務(wù)預(yù)測(cè)方法，解決現(xiàn)有的Web服務(wù)QoS預(yù)測(cè)方法當(dāng)中精度較低的問(wèn)題。方法流程如圖1所示。

圖1 基于協(xié)同過(guò)濾的自適應(yīng)Web服務(wù)QoS預(yù)測(cè)方法的流程

具體的算法描述如下：

(1)用戶端向服務(wù)端提出基于QoS的Web服務(wù)請(qǐng)求。

(2)服務(wù)端根據(jù)用戶端提出的Web服務(wù)請(qǐng)求，以及已有的用戶端的其他Web服務(wù)QoS數(shù)據(jù)，以及與該用戶端相類似的其他客戶端的Web服務(wù)QoS數(shù)據(jù)，生成用戶-服務(wù)矩陣，其中每一列代表一種Web服務(wù)，每一行對(duì)應(yīng)一個(gè)用戶。

(3)在該用戶-服務(wù)矩陣中，計(jì)算兩兩用戶以及兩兩服務(wù)之間的相似度，然后對(duì)相似結(jié)果進(jìn)行聚類分析；相似度的計(jì)算采用的是皮爾遜相關(guān)系數(shù)：

Sim(ui,uj)=

(1)

Sim(ui,uj)=

(2)

其中，u表示用戶，i表示服務(wù)，ui表示第i個(gè)用戶，si表示第i個(gè)服務(wù)。Sim(ui,uj)表示用戶ui和uj的相似度，Sim(si,sj)表示服務(wù)si和sj的相似度。r(ui,s)表示用戶ui對(duì)每個(gè)服務(wù)的QoS值，r(si,u)表示每個(gè)用戶對(duì)服務(wù)si的QoS值。

(4)根據(jù)相似性找到對(duì)于目標(biāo)用戶的K個(gè)最接近用戶，或者找到對(duì)于目標(biāo)服務(wù)的K個(gè)最接近服務(wù)。記錄下它們對(duì)應(yīng)的相似度值。

(5)把步驟4記錄的相似度值與K個(gè)用戶(或者K個(gè)服務(wù))的均值相結(jié)合，利用如下公式得到對(duì)該QoS值所做出的預(yù)測(cè)值A(chǔ)：

(3)

(4)

基于混合協(xié)同過(guò)濾的QoS服務(wù)預(yù)測(cè)方法，特征在于首先計(jì)算兩兩用戶以及兩兩服務(wù)之間的相似度，然后對(duì)相似結(jié)果進(jìn)行聚類分析，找到對(duì)于目標(biāo)用戶的K個(gè)最接近用戶以及對(duì)于所需Web服務(wù)最接近的K個(gè)項(xiàng)目，并把計(jì)算出的相似度與K個(gè)用戶(或者K個(gè)服務(wù))的均值相結(jié)合，形成對(duì)該QoS值所做出的預(yù)測(cè)值A(chǔ)。

(6)同步驟1～步驟5，不同之處是在計(jì)算兩兩之間的相似性的時(shí)候，使用一種改進(jìn)的UPCC和IPCC相關(guān)系數(shù)：

(5)

(6)

從而得到預(yù)測(cè)值B。

其中，|Ia∩Iu|是用戶a和用戶u共同調(diào)用的服務(wù)，Ia是用戶a調(diào)用的服務(wù)，Iu是用戶u調(diào)用的服務(wù)。|Ua∩Uu|是共同調(diào)用服務(wù)i和j的用戶，Ui是調(diào)用服務(wù)i的用戶，Uj是調(diào)用服務(wù)j的用戶。

(7)把預(yù)測(cè)值A(chǔ)和B以一定的權(quán)值相結(jié)合，得到目標(biāo)用戶(或項(xiàng)目)的QoS值：

(7)

α+β=1

(8)

通過(guò)自適應(yīng)調(diào)整權(quán)值α與β的大小，得到較好的QoS預(yù)測(cè)值。

以上所述的基于混合協(xié)同過(guò)濾的QoS服務(wù)預(yù)測(cè)方法，通過(guò)預(yù)測(cè)值A(chǔ)和B以一定的權(quán)值相結(jié)合得到目標(biāo)用戶(或服務(wù))的QoS值。在不同的數(shù)據(jù)集里，通過(guò)調(diào)整權(quán)值系數(shù)的值，得到該條件下最優(yōu)的QoS預(yù)測(cè)方案。

2 實(shí)驗(yàn)結(jié)果

基于WSDream(339*5 825)數(shù)據(jù)集來(lái)進(jìn)行相應(yīng)的實(shí)驗(yàn)，WSDream是一個(gè)公開(kāi)的QoS方面的數(shù)據(jù)集。將數(shù)據(jù)集文件分別以8∶2的比例，劃分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集。然后以訓(xùn)練數(shù)據(jù)集為輸入，輸出測(cè)試數(shù)據(jù)集中各用戶-項(xiàng)目的預(yù)測(cè)評(píng)分。最后對(duì)預(yù)測(cè)評(píng)分進(jìn)行協(xié)同過(guò)濾的評(píng)價(jià)指標(biāo)評(píng)估：

平均絕對(duì)偏差(MAE)計(jì)算公式如下：

(9)

均方根誤差(RMSE)計(jì)算公式如下：

(10)

這兩個(gè)指標(biāo)主要是通過(guò)計(jì)算預(yù)測(cè)值與實(shí)際值之間的偏差來(lái)評(píng)估目標(biāo)方法的預(yù)測(cè)精度。

表2～表4分別是采樣10%、20%、30%作為測(cè)試集之后得到的結(jié)果。結(jié)合3張表發(fā)現(xiàn)，文中方法在MAE、RMSE指標(biāo)上優(yōu)于單獨(dú)使用WSRec(一種改進(jìn)的協(xié)同過(guò)濾)方法，如表1所示。結(jié)合每張表上α的取值，在α=0.65附近時(shí)，MAE和RMSE可以達(dá)到最低值。

表2～表4顯示了文中方法中α的取值對(duì)于預(yù)測(cè)精度(MAE/RMSE)的影響(分別為抽取10%/20%/30%的數(shù)據(jù)集作為測(cè)試集)。結(jié)合每張表上α的取值，在α=0.65時(shí)，MAE和RMSE可以達(dá)到最優(yōu)值。

表1 改進(jìn)方法與WSRec方法的比較

表2 α取值與預(yù)測(cè)精度的關(guān)系(抽取10%作為測(cè)試集，α的最優(yōu)值：α=0.65)

表3 α取值與預(yù)測(cè)精度的關(guān)系(抽取20%作為測(cè)試集，α的最優(yōu)取值范圍：0.4<α<1)

表4 α取值與預(yù)測(cè)精度的關(guān)系(抽取30%作為測(cè)試集，α的最優(yōu)取值范圍：0.5<α<1)

針對(duì)不同的抽樣率，MAE與α取值的曲線關(guān)系如圖2～圖4所示。

圖2 10%抽樣關(guān)系

圖3 20%抽樣關(guān)系

圖4 30%抽樣關(guān)系

3 結(jié)束語(yǔ)

采用協(xié)同過(guò)濾的手段是當(dāng)前預(yù)測(cè)精度較好的方法，但是目前單一采用協(xié)同過(guò)濾的預(yù)測(cè)精度不高，尤其是在矩陣較為稀疏的情形下。該文有效改進(jìn)了這一問(wèn)題，使得QoS預(yù)測(cè)精度得到提高。提出的采用兩種協(xié)同過(guò)濾進(jìn)行混合的算法，可以通過(guò)自適應(yīng)調(diào)整權(quán)值的大小，提高協(xié)同過(guò)濾算法的精度。該算法改進(jìn)了皮爾遜相關(guān)系數(shù)法可能在數(shù)據(jù)稀疏的情況下對(duì)相似性給予過(guò)高估計(jì)的不足，從而提高了最終的QoS預(yù)測(cè)值的精度，同時(shí)指標(biāo)上也優(yōu)于WSRec方法。