基于中位數的用戶信譽度排名算法

鮑 琳，牛軍鈺，莊 芳

?

基于中位數的用戶信譽度排名算法

鮑 琳，牛軍鈺，莊 芳

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

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

推薦系統；用戶信譽度；Spammer攻擊；協同過濾；中位數；均方根誤差

1 概述

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

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

2 簡單的打分系統

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

圖1 簡單的打分系統

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

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

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

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

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

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

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

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

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

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

Begin

for i←0 to 對象數

sum←0

count←0

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

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

count←count + 1

grades[i]←sum / count

for j←0 to 用戶數

mid ← getMid(users[j])

reputations[j] ← 1 – λ * mid

End

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

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

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

5 實驗與結果分析

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

5.1 數據集

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

5.2 對比標準

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

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

5.3 參數設定

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

5.4 結果分析

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

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

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

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

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

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

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

表3 原MovieLen和4種算法處理后的數據集RMSE

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

6 結束語

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

[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] 許海玲, 吳 瀟, 李曉東, 等. 互聯網推薦系統比較研究[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] 鄧愛林, 朱揚勇, 施伯樂. 基于項目評分預測的協同過濾推薦算法[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－)，女，碩士研究生，主研方向：推薦系統，社會網絡，網絡聚類；牛軍鈺，副教授；莊 芳，助理研究員、碩士研究生。

2013-02-04

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

10.3969/j.issn.1000-3428.2014.03.013