基于中位數(shù)的用戶信譽度排名算法

鮑 琳，牛軍鈺，莊 芳

?

基于中位數(shù)的用戶信譽度排名算法

鮑 琳，牛軍鈺，莊 芳

(復旦大學軟件學院，上海 201203)

針對推薦系統(tǒng)易受Spammer攻擊的影響，從而導致對象的實際得分不準確的問題，提出基于中位數(shù)的用戶信譽度排名算法。通過衡量用戶信譽度調(diào)整用戶打分權重，根據(jù)中位數(shù)具有不易受極端打分影響的特性，選取用戶打分與對象得分差距的中位數(shù)作為降低用戶信譽度的標準，不斷迭代調(diào)整用戶信譽度以及最終得分直至收斂。在多個真實數(shù)據(jù)集上的運行結果證明，相比現(xiàn)有排名算法，該算法具有更合理的信譽度分布和更高的排名結果準確度，通過該算法預處理后的數(shù)據(jù)集在SVD++上運行可以得到更低的均方根誤差。

推薦系統(tǒng)；用戶信譽度；Spammer攻擊；協(xié)同過濾；中位數(shù)；均方根誤差

1 概述

基于Web的打分排名系統(tǒng)在電子商務與消費點評網(wǎng)站中有著廣泛的應用，各類商品的評價排名結果影響著用戶的選擇，因此，排名系統(tǒng)成為了Spammer的重點攻擊對象。如何提高排名系統(tǒng)的準確度，是近年來數(shù)據(jù)挖掘領域的研究熱點。一個優(yōu)秀的排名算法應足夠健壯，以抵擋Spammer的攻擊，并且具有可收斂等特性[1-2]。為此，現(xiàn)有較多研究引入用戶信譽度[3]的概念，對用戶的打分重新評估，減少Spammer對最終排名的影響。目前基于用戶信譽度的推薦系統(tǒng)主要分為2種類型：內(nèi)容驅動型[4-5]和用戶驅動型。其中，用戶驅動型主要是根據(jù)用戶給對象的評分來評估該用戶的信譽度。

本文在對文獻[6]算法進行實驗、分析的基礎上，利用中位數(shù)不易受極端打分影響的特性，提出基于中位數(shù)的用戶信譽度排名算法：L1MED和L2MED，以提高打分系統(tǒng)排名結果的準確度。

2 簡單的打分系統(tǒng)

基于用戶信譽度的排名算法的主要思想為：打分結果總是與用戶群體打分差距較大的用戶，其信譽度較低，應減少其打分在計算總分時的權重。

圖1 簡單的打分系統(tǒng)

3 基于用戶信譽度的排名算法及其存在問題

實際上，在實現(xiàn)文獻[6]提出的算法過程中發(fā)現(xiàn)，在L1MIN、L2MIN算法中，用戶的信譽度基本沒有減少，當?shù)梅质諗繒r，用戶的信譽度幾乎始終保持在1的位置，即L1MIN和L2MIN有退化為算術平均算法的趨勢；而對于L1MAX、L2MAX與L1MIN、L2MIN則相反，用戶的信譽度將會集中在區(qū)域的最左端，只在一個很小的范圍內(nèi)有值，相當于為所有的用戶打分乘上了一個小于1的常數(shù)。這樣的結果并不理想，本文希望得到一個較平均的信譽度分布。

為了檢驗L1AVG、L2AVG、L1MAX、L2MAX、L1MIN和L2MIN算法的效率性和強壯性，文獻[6]分別計算這6種算法與算術平均算法(Mizz、YZLM、dKVD)之間的Kendall Tau距離，得出這6種算法與算術平均算法的Kendall Tau距離比Mizz、YZLM、dKVD算法的距離更小。由于L1MIN和L2MIN對用戶信譽度的懲罰過少，根據(jù)L1MIN和L2MIN算法計算出的最終打分結果與算術平均算法的計算結果相差無幾，因此，相近的距離無法證明這2種算法的有效性。

隨機選取一些用戶，并將其打分取反，例如，若滿分為5，用戶原本對某對象的打分為4，則將其打分改為1，然后觀察這個改變對于用戶信譽度的影響。

經(jīng)過上述處理后運行文獻[6]中的算法，得到表1的結果?？梢园l(fā)現(xiàn)，MIN算法的結果沒有受到任何影響，這種情形是不合理的；MAX的2個算法受影響相對較小，AVG和MED表現(xiàn)較為正常，用戶的信譽度有較明顯的變化。L1MED和L2MED是本文提出算法，與其他6種算法相比，它們采用了用戶評分與對象得分差距的中位數(shù)作為降低用戶信譽度的標準。

表1 打亂用戶打分對不同算法信譽度的影響

4 基于中位數(shù)的改進用戶信譽度排名算法

根據(jù)上述分析和簡單實驗的結果，希望得到的算法應有2個基本特性：(1)用戶的信譽度不應聚集在一起，而應更接近于正態(tài)分布；(2)其結果應與一個標準排序序列相似。

本文將中位數(shù)作為懲罰用戶信譽度的標準。中位數(shù)的作用與算術平均數(shù)相近，在一個等差數(shù)列或一個正態(tài)分布數(shù)列中，中位數(shù)與算數(shù)平均數(shù)相等。在數(shù)列中出現(xiàn)了極端變量值的情況下，因中位數(shù)不受極端變量值的影響，使用中位數(shù)比使用算數(shù)平均更合理。對于打分偏極端的Spammer來說，或許中位數(shù)更能反映其打分的真實情況。由此，本文提出L1MED算法和L2MED算法。

一次迭代過程的偽代碼具體如下：

Begin

for i←0 to 對象數(shù)

sum←0

count←0

for j←0 to 為對象objects[i]評過分的用戶數(shù)

sum←sum + rating[i, userId] ×該用戶的信譽度

count←count + 1

grades[i]←sum / count

for j←0 to 用戶數(shù)

mid ← getMid(users[j])

reputations[j] ← 1 – λ * mid

End

表2是L1MED算法在數(shù)據(jù)集MovieLen上迭代的部分得分結果，取0.2，本文只選取其中一個片段。

表2 λ=0.2時MovieLen上迭代的部分得分結果

另外，添加系數(shù)1/2保證收斂，對應L2MED算法的信譽度相關公式如下：

5 實驗與結果分析

在介紹所采用的數(shù)據(jù)集、評估指標和實驗參數(shù)設置的基礎上，對本文算法與現(xiàn)有算法進行比較，并對實驗結果進行分析。

5.1 數(shù)據(jù)集

在實驗過程中，本文使用以下數(shù)據(jù)集：(1)MovieLens 1M：該數(shù)據(jù)集是從MovieLens網(wǎng)站上收集而來的電影評分數(shù)據(jù)，包涵6 000個用戶、4 000部電影的1百萬條評分信息；(2)Epinions：該數(shù)據(jù)集是從Epinions(www.epinions.com)(一個產(chǎn)品評論網(wǎng)站)上收集而來，包括40 163個用戶對139 738個產(chǎn)品的1 149 766條評分記錄。

5.2 對比標準

在文獻[6]中，使用算術平均算法作為與其他算法對比的基準線。算術平均是大多數(shù)信息檢索(Information Retrieval, IR)社區(qū)使用計算得分的算法，它選擇相信所有用戶的打分真實性，不考慮用戶的信譽度，但因為該算法的簡易性及普及性，在此把它作為算法準確度的評價基準，并計算算術平均算法和各種排名算法兩者之間得分向量的L1距離。

SVD++[10]是在Netflix比賽中獲獎的一個協(xié)同過濾算法[11-12]模型，利用隱式反饋信息找到用戶的偏好，依此將用戶對電影的評分重新調(diào)整，從而向用戶推薦適合他們的電影。

5.3 參數(shù)設定

在SVD++的實驗部分，取迭代次數(shù)為20，學習率(learning rate)設定為0.001。

5.4 結果分析

圖2、圖3分別展示了算數(shù)平均算法和各種排名算法得分之間的相關性。圖2展示了MovieLen數(shù)據(jù)集上8種算法與算數(shù)平均算法之間得分的L1距離，L1MIN、L2MIN與算術平均算法之間的差距極小，因懲罰過小，對對象得分的影響微乎其微；在距離計算方式下，MED比AVG結果更加接近算術平均算法；MAX因懲罰過大，與算術平均算法之間的差距為所有算法中差距最大的。圖3說明了Epinions數(shù)據(jù)集上的運行結果，和MovieLen上得出的結論相近。

圖2 MovieLen數(shù)據(jù)集上各算法與算術平均算法之間的L1距離

圖3 Epinions數(shù)據(jù)集上各算法與算術平均算法之間的L1距離

圖4顯示了L1AVG、L1MED、L2AVG、L2MED算法計算出的用戶信譽度的分布(由于L1MIN、L2MIN、L1MAX、L2MAX算法的信譽度分布過于集中，如放到同一張圖中，無法看清其他算法的分布)。從圖4可以看出，L1AVG和L1MED有比較平均且相似的分布；在曲線的中間段，L1AVG比L1MIN更加平滑；相對地，L2AVG和L2MIN也有比較相似的分布，但是兩者用戶信譽度都相對比較集中，只在一個很小的分數(shù)段內(nèi)才有數(shù)值。

圖4 λ=0.2時MovieLen上用戶信譽度分布

經(jīng)上述分析得出，L1MED和L2MED算法有相對平均的用戶信譽度分布，并與算術平均算法的距離更接近。

表3列出了SVD++上運行MovieLen數(shù)據(jù)集后所得RMSE值，以及用L1AVG、L1MED、L2AVG、L2MED算法預處理MovieLen數(shù)據(jù)集后，運行所得RMSE值。

表3 原MovieLen和4種算法處理后的數(shù)據(jù)集RMSE

從表3可看出，預處理后的數(shù)據(jù)集對RMSE的值有所提升，符合期望。其中，L1MID的提升量最大，L1AVG次之，L2AVG和L2MIN相對MovieLen的原始數(shù)據(jù)集也有少量提升。在計算效率上，L1MED和L2MED由于需要尋找中位數(shù)，相對其他算法效率降低，但仍在可接受范圍之內(nèi)。

6 結束語

根據(jù)中位數(shù)不易受極端打分影響的特性，在已有基于用戶打分的推薦系統(tǒng)基礎上，提出2種新算法：L1MED和L2MED，這2種算法在2個不同的公開數(shù)據(jù)集上運行，將運行結果與已有算法做了比較，證明本文提出算法的準確性。同時，將算法預處理后的數(shù)據(jù)應用于SVD++上，結果比無處理的原始數(shù)據(jù)更優(yōu)秀，證明了算法的有效性。下一步將考慮用戶打分的時間順序屬性，分析用戶打分受已有打分影響的可能性，并試圖減少羊群效應所造成的影響，從而將本文算法推廣到更廣泛的應用場景中。

[1] J?sang A, Golbeck J. Challenges for Robust Trust and Repu- tation Systems[C]//Proceedings of the 5th International Workshop on Security and Trust Management. Saint Malo, France: [s. n.], 2009.

[2] 許海玲, 吳 瀟, 李曉東, 等. 互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]. 軟件學報, 2009, 20(2): 350-362.

[3] Resnick P, Kuwabara K, Zeckhauser R, et al. Reputation Systems[J]. Communications of the ACM, 2000, 43(12): 45-48.

[4] Adler B, de Alfaro L. A Content-driven Reputation System for the Wikipedia[C]//Proceedings of the 16th International Conference on World Wide Web. New York, USA: ACM Press, 2007: 261-270.

[5] Adler B, de Alfaro L, Kulshreshtha A, et al. Reputation Systems for Open Collaboration[J]. Communications of the ACM, 2011, 54(8): 81-87.

[6] Li Ronghua, Jerry Yuxu, Huang Xin, et al. Robust Reputation- based Ranking on Bipartite Rating Networks[C]//Proceedings of the 2012 SIAM International Conference on Data Mining. [S. l.]: SDM Press, 2012: 612-623.

[7] Mizzaro S. Quality Control in Scholarly Publishing: A New Proposal[J]. Journal of the American Society for Information Science and Technology, 2003, 54(11): 989-1005.

[8] Yu Yikuo, Zhang Yicheng, Laureti P. Decoding Information from Noisy, Redundant, and Intentionally Distorted Sources[J]. Physica A: Statistical Mechanics and Its Applications, 2006, 371(2): 732-744.

[9] de Kerchove C, van Dooren P. Iterative Filtering in Reputation Systems[J]. SIAM Journal on Matrix Analysis and Applications, 2010, 31(4): 1812-1834.

[10]Koren Y, Bell R. Advances in Collaborative Filtering[M]//Ricci F, Rokach L, Shapira B, et al. Recommender Systems Handbook. [S. l.]: Springer, 2011: 145-186.

[11] 鄧愛林, 朱揚勇, 施伯樂. 基于項目評分預測的協(xié)同過濾推薦算法[J]. 軟件學報, 2003, 14(9): 1621-1628.

[12] Goldberg D, Nichols D, Oki B M, et al. Using Collaborative Filtering to Weave an Information Tapestry[J]. Communi- cations of the ACM, 1992, 35(12): 61-70.

編輯 陸燕菲

User Reputation Ranking Algorithm Based on Median

BAO Lin, NIU Jun-yu, ZHUANG Fang

(Software School, Fudan University, Shanghai 201203, China)

For the problem that the recommendation system is vulnerable to the impact of Spammer attack, which leads to the inaccuracy of the final item rating, this paper proposes a user reputation ranking algorithm based on median. The algorithm readjusts the weight of user’s rating by measuring user’s reputation. On the other hand, according to the median, it has the property of less susceptible to the effects of extreme rating, the algorithm selects the median from the distances between user rank and object rank as the criterion to decrease user reputation, then iterates until convergence to adjust the user reputation and final rating. Operation result of multiple real data sets shows that the algorithm obtains a more reasonable reputation distribution and a higher accuracy, and after preprocessing by this algorithm, the rating data can get a better Root Mean Square Error(RMSE) value on SVD++.

recommendation system; user reputation; Spammer attack; collaborative filtering; median; Root Mean Square Error(RMSE)

1000-3428(2014)03-0063-04

A

TP399

鮑 琳(1988－)，女，碩士研究生，主研方向：推薦系統(tǒng)，社會網(wǎng)絡，網(wǎng)絡聚類；牛軍鈺，副教授；莊 芳，助理研究員、碩士研究生。

2013-02-04

2013-03-28 E-mail：by.mariana.trench@gmail.com

10.3969/j.issn.1000-3428.2014.03.013