基于改進協同過濾的個性化Web服務推薦方法研究

徐 堃，朱小柯，荊曉遠

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.武漢大學 計算機學院，湖北 武漢 430072；3.南京郵電大學 自動化學院，江蘇 南京 210003)

0 引 言

互聯網中快速增加的Web服務給用戶提供了很多選擇，這些服務所提供的內容卻有很多相似之處[1]。為了減少用戶選擇Web服務時的難度，Web服務推薦成為一種有效的方式。推薦系統現在受到了越來越多的重視，因為在大量的服務中，推薦系統能有效挖掘候選服務的功能性及非功能性屬性，進行擇優篩選，并向用戶推薦最合適的服務。亞馬遜網站已經在用推薦技術進行書籍推薦和CD推薦[2]。

協同過濾(collaborative filtering,CF)是一種廣泛使用的服務推薦技術。該類方法假設，如果用戶1和用戶2訪問一部分服務的質量相似，那么對于用戶2已經訪問過的新服務而言，用戶1在使用該服務時會有相似的服務質量[3]。已有的基于訪問歷史的CF算法使用Web服務的服務質量(quality of services,QoS)計算用戶之間或服務之間的相似度，但是直接使用所有的QoS數據并不能做出準確的相似性判斷。因為在用戶訪問服務的過程中，用戶的個性化偏好并不能直接體現在QoS數據中。直接使用QoS數據進行相似性計算，會得到不真實的相似度結果。為了準確地推薦服務，需要聯合用戶偏好和QoS數據進行相似度判斷及QoS預測。

文中提出了一種基于用戶偏好的改進協同過濾算法(UPCF)，同時使用用戶偏好和QoS做出準確的服務推薦。該方法改進了廣泛使用的皮爾遜相關系數(Pearson correlation coefficient，PCC)，首先從QoS數據中提取出個性化偏好，計算出準確的用戶間或服務間相似度；然后使用top-k算法選擇相似鄰居；最后使用QoS值對目標用戶的缺失數據進行預測。

1 相關工作

1.1 基于協同過濾的Web服務推薦

協同過濾是一種廣泛使用的服務推薦技術，CF基于系統中其他用戶的訪問歷史進行推薦。目前基于協同過濾的Web服務推薦的研究主要集中于基于訪問歷史的服務推薦和基于模型的服務推薦。文中提出的算法屬于前者。

Web服務推薦領域傳統的基于訪問歷史的推薦算法有UMEAN、IMEAN、UPCC、IPCC、WSREC[4-7]。UMEAN使用系統中所有用戶對Web服務的已知QoS平均值來預測目標用戶的缺失QoS值。同理，IMEAN使用系統中所有服務的已知QoS平均值來預測目標服務的缺失QoS值。

UPCC是基于用戶的皮爾遜相關性預測算法，該算法致力于找尋與目標用戶皮爾遜相關系數較大的鄰居，并使用鄰居用戶的QoS數據來預測目標用戶的QoS值。用戶間的相似度取值范圍為[-1,1]，相似度值越大表示用戶間越相似。該算法的計算過程如下：

(1)

(2)

其中，N(u)為根據top-k算法選擇的用戶u的優先相似鄰居集合；P(u,i)表示預測出的用戶u訪問服務i的QoS值。

與UPCC類似，IPCC是基于服務的皮爾遜相關性預測算法，該算法致力于找尋與目標服務皮爾遜相關系數較大的鄰居，并使用鄰居服務的QoS數據來預測目標服務的QoS值。服務間的相似度取值范圍也是[-1,1]，相似度值越大表示服務之間越相似。該算法的計算過程如下：

(3)

(4)

為了提高Web服務推薦的準確性，很多研究工作在此基礎上進行了一些改進。WSREC方法使用聯合基于用戶和基于服務的協同過濾推薦算法以提高Web服務的推薦準確性;文獻[8-10]使用矩陣分解的方法代替協同過濾算法。但是，以上方法都沒有考慮用戶偏好對QoS預測的影響，預測結果的準確性因此受到影響。

1.2 個性化服務推薦

基于協同過濾[11-14]的個性化Web推薦算法已經有不少學者研究過。文獻[2]中認為，兩個用戶訪問過相同的Web服務這一行為并不能保證這兩個用戶就是相似的，該文提出使用被訪問服務的標準差大小來判定該服務對用戶相似度評價的影響。文獻[6]中認為，如果兩個用戶在訪問一些服務時有相似的QoS值，那么在訪問其他服務時，也會有相似的QoS值。文獻[15]中認為，在地理位置上近鄰的用戶比相隔較遠的用戶有更大的可能性具有相似的訪問服務質量，并以此作為預測準則。

以上個性化推薦方法考慮了用戶的地理位置、服務的變化性、用戶的相似訪問歷史等因素，但都未考慮用戶偏好，預測準確率受到影響。因此，文中提出基于用戶偏好的改進協同過濾Web服務推薦算法。

2 改進協同過濾的Web服務推薦

2.1 用戶偏好定義

定義1:給定用戶集合U={u1,u2,…,um}和服務集合S={s1,s2,…,sn}，定義變量Sati,j為用戶ui對服務sj的偏好，并構建一個m×n的用戶偏好矩陣SATm×n；構建一個m×n的QoS矩陣Qm×n，變量qi,j表示用戶ui訪問服務sj的QoS值。

用戶偏好從QoS數據中提取并提供兩種評價準則。準則1:QoS值(可靠性等)越高用戶越滿意；準則2:QoS值(響應時間等)越低用戶越滿意。式(5)～(7)描述了Sati,j的細節：

(5)

α=

(6)

β=

(7)

其中，min(ui)和max(ui)分別表示用戶ui訪問的最小和最大的QoS值。真實世界中，Qm×n是一個稀疏矩陣，SATm×n也同樣是一個稀疏矩陣。

2.2 基于用戶偏好的相似度計算

在基于訪問歷史的協同過濾推薦工作中，找到目標用戶或服務的優先相似鄰居是整個算法中最重要的部分，因為推薦算法的預測準確率依賴于準確的相似鄰居。

現有的相似度計算方法有余弦相似度、皮爾遜相關系數等，皮爾遜相關系數具有更好的相似度計算結果。文中采用皮爾遜相關系數計算用戶間或服務間的相似度，并以此找出目標用戶或服務的優先相似鄰居。具體的相似度計算如下所示：

simsat(u,v)=

(8)

simsat(i,j)=

(9)

2.3 改進協同過濾的Web服務推薦算法步驟

輸入：QoS數據的訓練集TrainData，QoS數據的測試集TestData，近似鄰居數top-k，調和參數λ

輸出：QoS預測值P(u,i)

(1)對訓練集TrainData中的QoS數據，用式(5)計算出用戶偏好矩陣SAT；

(2)對用戶偏好矩陣SAT中的每個用戶，用式(8)計算出用戶之間的偏好相似性，存于用戶相似性矩陣中；

(3)根據相似用戶鄰居數top-k選擇用戶的優先相似鄰居集合N(u)；

(4)對測試集TestData中缺失的QoS值，用式(2)計算出缺失QoS預測值Pu(u,i)；

(5)對SAT中的每個服務，用式(9)計算出服務之間的用戶偏好相似性，存于服務相似性矩陣中；

(6)根據相似服務鄰居數top-k選擇服務的優先相似鄰居集合N(i)；

(7)對測試集TestData中缺失的QoS值，用式(4)計算出缺失QoS預測值Pi(u,i)；

(8)用調和參數λ調節Pu(u,i)、Pi(u,i)的比例，得到UPCF算法最佳預測值P(u,i)。

P(u,i)=λPu(u,i)+(1-λ)Pi(u,i),λ∈[0,1]

(10)

3 實 驗

3.1 數據庫

實驗使用香港中文大學發布的WSDREAM[16]數據集，該數據集收集了全球30個國家的339個用戶和70多個國家的5 825個Web服務，包含197萬條真實Web服務QoS訪問記錄，分為響應時間和吞吐量兩個部分。響應時間的取值范圍是0～20 s，吞吐量的取值范圍是0～1 000 kbps。

3.2 評價指標

平均絕對誤差(MAE)是聯合過濾方法中經常使用的評價指標,定義如下：

(11)

從式(11)可以看出，MAE值越小表明算法預測的準確性越高。

平均標準差誤差(RMSE)也是度量指標，定義如下:

(12)

和MAE相比，RMSE加大了對預測差異較大的QoS值的懲罰，對于預測結果穩定性的要求更高，同樣，RMSE值越小表明算法預測的準確性越高。

3.3 實驗對比與分析

為了證明文中算法的有效性，與傳統的基于CF推薦算法UPCC[5]、IPCC[7]、WSREC[4]和最新的基于CF推薦算法PHCF[2]作對比實驗。實驗中使用的QoS屬性為Web服務的響應時間(response time)。

矩陣的稀疏度定義為訓練集的稀疏度(density)，算法運行在6個不同的稀疏度上，分別是5%，10%，15%，20%，25%，30%。如果矩陣的稀疏度是10%，那么矩陣中10%的數據組成訓練集，剩下90%的數據組成測試集。每種算法做20次隨機實驗，取MAE和RMSE的平均值作為實驗結果。文中算法的用戶鄰居top-k為20，服務鄰居top-k為130，調和參數λ為0.7，實驗結果如表1和表2所示。

表1 不同稀疏度下MAE對比結果

表2 不同稀疏度下RMSE對比結果

從表1可以看出，各推薦算法的MAE值隨著稀疏程度的減弱在降低；在各稀疏度下UPCF算法的MAE與最新的PHCF相比至少下降0.8%，與其他算法相比下降更多；結果表明UPCF具有更高的預測準確率。

表2的實驗結果證明UPCF與對比算法相比在具有更好的預測準確率的同時，預測結果的穩定性也更好。

3.4 top-k的影響

參數top-k控制相似鄰居集合的大小。top-k過小，鄰居的QoS值會出現個性化偏置；top-k過大，鄰居的近似作用就會減弱。圖1是10%稀疏度條件下用戶鄰居數變化對MAE的影響。

圖1 參數Topk of Users的影響

從圖1可以看出，用戶鄰居數為20時，QoS預測準確率最高。對服務鄰居數也進行了測試實驗，結果表明服務鄰居數為130時預測準確率最高。

3.5 λ的影響

參數λ調節相似用戶預測部分和相似服務預測部分在UPCF訓練模型中的比重，這種協同預測方法在文獻[4]證明是一種有效提升預測準確率的辦法。圖2是10%稀疏度條件下參數λ變化對MAE影響。

圖2 參數λ的影響

從圖2可以看出，當λ為0.7時，MAE值最低；此時相似用戶預測部分占比70%，相似服務預測部分占比30%。

4 結束語

文中提出一種基于用戶偏好的改進協同過濾Web服務推薦算法。該算法從QoS數據中提取用戶偏好，并將其作為相似用戶的選擇標準，然后使用top-k算法確定目標用戶及服務的相似鄰居，最后使用皮爾遜相關系數預測目標用戶的QoS值。實驗結果證明了該算法具有很好的預測準確率。

[1] EKSTRAND M D,RIEDL J T,KONSTAN J A.Collaborative filtering recommender systems[J].Foundations and Trends in Human-Computer Interaction,2010,4(2):81-173.

[2] JIANG Yechun,LIU Jianxun,TANG Mingdong,et al.An effective Web service recommendation method based on personalized collaborative filtering[C]//9th international conference on Web services.United States:IEEE Computer Society,2011:211-218.

[3] CHEN Xi, ZHENG Zibin,LIU Xudong,et al.Personalized QoS-aware Web service recommendation and visualization[J].IEEE Transactions on Services Computing,2013,6(1):35-47.

[4] ZHENG Zibin,MA Hao,LYU M R,et al.WSRec:a collaborative filtering based Web service recommender system[C]//International conference on Web services.United States:IEEE Computer Society,2009:437-444.

[5] BREESE J S,HECKERMAN D,KADIE C.Empirical analysis of predictive algorithms for collaborative filtering[C]//2013 conference on uncertainty in artificial intelligence.United States:IEEE Computer Society,2013:43-52.

[6] SHAO Lingshuang,ZHANG Jing,WEI Yong,et al.Personalized QoS prediction for Web services via collaborative filtering[C]//2007 IEEE international conference on Web services.United States:IEEE Computer Society,2007:439-446.

[7] RESNICK P,IACOVOU N,SUCHAK M,et al.Grouplens:an open architecture for collaborative filtering of Netnews[C]//1994 conference on computer supported cooperative work.United States:ACM,1994:175-186.

[8] KOREN Y,BELL R, VOLINSKY C. Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.

[9] HE P,ZHU J,ZHENG Z,et al.Location-based hierarchical matrix factorization for Web service recommendation[C]//IEEE international conference on Web services.United States:IEEE Computer Society,2014:297-304.

[10] YU Q,ZHENG Z,WANG H.Trace norm regularized matrix factorization for service recommendation[C]//2013 IEEE international conference on Web services.United States:IEEE Computer Society,2013:34-41.

[11] FLETCHER K K,LIU X F,TANG M.Elastic personalized nonfunctional attribute preference and trade-off based service selection[J].ACM Transactions on the Web,2015,9(1):1-26.

[12] LIU X,FLETCHER K K,TANG M.Service selection based on personalized preference and trade-offs among QoS factors and price[C]//IEEE first international conference on services economics.United States:IEEE Computer Society,2012:32-39.

[13] RONG W,LIU K,LIANG L.Personalized Web service ranking via user group combining association rule[C]//IEEE international conference on Web services.United States:IEEE Computer Society,2009:445-452.

[14] LIU R,JIA C X,ZHOU T,et al.Personal recommendation via modified collaborative filtering[J].Physica A:Statistical Mechanics and Its Applications,2009,388(4):462-468.

[15] CHEN X,ZHENG Z,YU Q,et al.Web service recommendation via exploiting location and QoS information[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1913-1924.

[16] ZHENG Z,ZHANG Y,LYU M R.Investigating Qos of real-world Web services[J].IEEE Transactions on Services Computing,2014,7(1):32-39.