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

鮑 琳，牛軍鈺，莊 芳

?

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

鮑 琳，牛軍鈺，莊 芳

(復(fù)旦大學(xué)軟件學(xué)院，上海 201203)

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

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

1 概述

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

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

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

基于用戶信譽(yù)度的排名算法的主要思想為：打分結(jié)果總是與用戶群體打分差距較大的用戶，其信譽(yù)度較低，應(yīng)減少其打分在計(jì)算總分時(shí)的權(quán)重。

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

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

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

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

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

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

表1 打亂用戶打分對(duì)不同算法信譽(yù)度的影響

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

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

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

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

Begin

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

sum←0

count←0

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

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

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上迭代的部分得分結(jié)果，取0.2，本文只選取其中一個(gè)片段。

表2 λ=0.2時(shí)MovieLen上迭代的部分得分結(jié)果

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

5 實(shí)驗(yàn)與結(jié)果分析

在介紹所采用的數(shù)據(jù)集、評(píng)估指標(biāo)和實(shí)驗(yàn)參數(shù)設(shè)置的基礎(chǔ)上，對(duì)本文算法與現(xiàn)有算法進(jìn)行比較，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

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

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

5.2 對(duì)比標(biāo)準(zhǔn)

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

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

5.3 參數(shù)設(shè)定

在SVD++的實(shí)驗(yàn)部分，取迭代次數(shù)為20，學(xué)習(xí)率(learning rate)設(shè)定為0.001。

5.4 結(jié)果分析

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

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

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

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

圖4 λ=0.2時(shí)MovieLen上用戶信譽(yù)度分布

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

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

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

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

6 結(jié)束語

根據(jù)中位數(shù)不易受極端打分影響的特性，在已有基于用戶打分的推薦系統(tǒng)基礎(chǔ)上，提出2種新算法：L1MED和L2MED，這2種算法在2個(gè)不同的公開數(shù)據(jù)集上運(yùn)行，將運(yùn)行結(jié)果與已有算法做了比較，證明本文提出算法的準(zhǔn)確性。同時(shí)，將算法預(yù)處理后的數(shù)據(jù)應(yīng)用于SVD++上，結(jié)果比無處理的原始數(shù)據(jù)更優(yōu)秀，證明了算法的有效性。下一步將考慮用戶打分的時(shí)間順序?qū)傩裕治鲇脩舸蚍质芤延写蚍钟绊懙目赡苄裕⒃噲D減少羊群效應(yīng)所造成的影響，從而將本文算法推廣到更廣泛的應(yīng)用場(chǎng)景中。

[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]. 軟件學(xué)報(bào), 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] 鄧愛林, 朱揚(yáng)勇, 施伯樂. 基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法[J]. 軟件學(xué)報(bào), 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)，社會(huì)網(wǎng)絡(luò)，網(wǎng)絡(luò)聚類；牛軍鈺，副教授；莊 芳，助理研究員、碩士研究生。

2013-02-04

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

10.3969/j.issn.1000-3428.2014.03.013