徐 堃，朱小柯，荊曉遠(yuǎn)

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

0 引 言

互聯(lián)網(wǎng)中快速增加的Web服務(wù)給用戶提供了很多選擇，這些服務(wù)所提供的內(nèi)容卻有很多相似之處[1]。為了減少用戶選擇Web服務(wù)時(shí)的難度，Web服務(wù)推薦成為一種有效的方式。推薦系統(tǒng)現(xiàn)在受到了越來越多的重視，因?yàn)樵诖罅康姆?wù)中，推薦系統(tǒng)能有效挖掘候選服務(wù)的功能性及非功能性屬性，進(jìn)行擇優(yōu)篩選，并向用戶推薦最合適的服務(wù)。亞馬遜網(wǎng)站已經(jīng)在用推薦技術(shù)進(jìn)行書籍推薦和CD推薦[2]。

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

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

1 相關(guān)工作

1.1 基于協(xié)同過濾的Web服務(wù)推薦

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

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

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

(1)

(2)

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

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

(3)

(4)

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

1.2 個(gè)性化服務(wù)推薦

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

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

2 改進(jìn)協(xié)同過濾的Web服務(wù)推薦

2.1 用戶偏好定義

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

用戶偏好從QoS數(shù)據(jù)中提取并提供兩種評價(jià)準(zhǔn)則。準(zhǔn)則1:QoS值(可靠性等)越高用戶越滿意；準(zhǔn)則2:QoS值(響應(yīng)時(shí)間等)越低用戶越滿意。式(5)～(7)描述了Sati,j的細(xì)節(jié)：

(5)

α=

(6)

β=

(7)

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

2.2 基于用戶偏好的相似度計(jì)算

在基于訪問歷史的協(xié)同過濾推薦工作中，找到目標(biāo)用戶或服務(wù)的優(yōu)先相似鄰居是整個(gè)算法中最重要的部分，因?yàn)橥扑]算法的預(yù)測準(zhǔn)確率依賴于準(zhǔn)確的相似鄰居。

現(xiàn)有的相似度計(jì)算方法有余弦相似度、皮爾遜相關(guān)系數(shù)等，皮爾遜相關(guān)系數(shù)具有更好的相似度計(jì)算結(jié)果。文中采用皮爾遜相關(guān)系數(shù)計(jì)算用戶間或服務(wù)間的相似度，并以此找出目標(biāo)用戶或服務(wù)的優(yōu)先相似鄰居。具體的相似度計(jì)算如下所示：

simsat(u,v)=

(8)

simsat(i,j)=

(9)

2.3 改進(jìn)協(xié)同過濾的Web服務(wù)推薦算法步驟

輸入：QoS數(shù)據(jù)的訓(xùn)練集TrainData，QoS數(shù)據(jù)的測試集TestData，近似鄰居數(shù)top-k，調(diào)和參數(shù)λ

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

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

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

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

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

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

(6)根據(jù)相似服務(wù)鄰居數(shù)top-k選擇服務(wù)的優(yōu)先相似鄰居集合N(i)；

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

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

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

(10)

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)庫

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

3.2 評價(jià)指標(biāo)

平均絕對誤差(MAE)是聯(lián)合過濾方法中經(jīng)常使用的評價(jià)指標(biāo),定義如下：

(11)

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

平均標(biāo)準(zhǔn)差誤差(RMSE)也是度量指標(biāo)，定義如下:

(12)

和MAE相比，RMSE加大了對預(yù)測差異較大的QoS值的懲罰，對于預(yù)測結(jié)果穩(wěn)定性的要求更高，同樣，RMSE值越小表明算法預(yù)測的準(zhǔn)確性越高。

3.3 實(shí)驗(yàn)對比與分析

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

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

表1 不同稀疏度下MAE對比結(jié)果

表2 不同稀疏度下RMSE對比結(jié)果

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

表2的實(shí)驗(yàn)結(jié)果證明UPCF與對比算法相比在具有更好的預(yù)測準(zhǔn)確率的同時(shí)，預(yù)測結(jié)果的穩(wěn)定性也更好。

3.4 top-k的影響

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

圖1 參數(shù)Topk of Users的影響

從圖1可以看出，用戶鄰居數(shù)為20時(shí)，QoS預(yù)測準(zhǔn)確率最高。對服務(wù)鄰居數(shù)也進(jìn)行了測試實(shí)驗(yàn)，結(jié)果表明服務(wù)鄰居數(shù)為130時(shí)預(yù)測準(zhǔn)確率最高。

3.5 λ的影響

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

圖2 參數(shù)λ的影響

從圖2可以看出，當(dāng)λ為0.7時(shí)，MAE值最低；此時(shí)相似用戶預(yù)測部分占比70%，相似服務(wù)預(yù)測部分占比30%。

4 結(jié)束語

文中提出一種基于用戶偏好的改進(jìn)協(xié)同過濾Web服務(wù)推薦算法。該算法從QoS數(shù)據(jù)中提取用戶偏好，并將其作為相似用戶的選擇標(biāo)準(zhǔn)，然后使用top-k算法確定目標(biāo)用戶及服務(wù)的相似鄰居，最后使用皮爾遜相關(guān)系數(shù)預(yù)測目標(biāo)用戶的QoS值。實(shí)驗(yàn)結(jié)果證明了該算法具有很好的預(yù)測準(zhǔn)確率。

[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.