莊 崟，郭志川，黃逍穎

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

0 引 言

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

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

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

1 算法描述

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

圖1 基于協(xié)同過濾的自適應Web服務QoS預測方法的流程

具體的算法描述如下：

(1)用戶端向服務端提出基于QoS的Web服務請求。

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

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

Sim(ui,uj)=

(1)

Sim(ui,uj)=

(2)

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

(4)根據(jù)相似性找到對于目標用戶的K個最接近用戶，或者找到對于目標服務的K個最接近服務。記錄下它們對應的相似度值。

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

(3)

(4)

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

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

(5)

(6)

從而得到預測值B。

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

(7)把預測值A(chǔ)和B以一定的權(quán)值相結(jié)合，得到目標用戶(或項目)的QoS值：

(7)

α+β=1

(8)

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

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

2 實驗結(jié)果

基于WSDream(339*5 825)數(shù)據(jù)集來進行相應的實驗，WSDream是一個公開的QoS方面的數(shù)據(jù)集。將數(shù)據(jù)集文件分別以8∶2的比例，劃分為訓練數(shù)據(jù)集和測試數(shù)據(jù)集。然后以訓練數(shù)據(jù)集為輸入，輸出測試數(shù)據(jù)集中各用戶-項目的預測評分。最后對預測評分進行協(xié)同過濾的評價指標評估：

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

(9)

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

(10)

這兩個指標主要是通過計算預測值與實際值之間的偏差來評估目標方法的預測精度。

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

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

表1 改進方法與WSRec方法的比較

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

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

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

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

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

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

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

3 結(jié)束語

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