在線用戶聲譽(yù)評價算法的魯棒性分析

李圣楠,　楊　凱,　劉曉露,　劉建國,2,　郭　強(qiáng)

(1.上海理工大學(xué) 復(fù)雜系統(tǒng)科學(xué)研究中心,上?！?00093; 2.上海財經(jīng)大學(xué) 科研實(shí)驗(yàn)中心,上?！?00433)

?

在線用戶聲譽(yù)評價算法的魯棒性分析

李圣楠1,楊凱1,劉曉露1,劉建國1,2,郭強(qiáng)1

(1.上海理工大學(xué) 復(fù)雜系統(tǒng)科學(xué)研究中心,上海200093; 2.上海財經(jīng)大學(xué) 科研實(shí)驗(yàn)中心,上海200433)

在線評分系統(tǒng)中的惡意或隨機(jī)打分為準(zhǔn)確評價在線用戶聲譽(yù)帶來了極大的挑戰(zhàn).對3種基于迭代的經(jīng)典在線用戶聲譽(yù)評價算法的魯棒性進(jìn)行了細(xì)致研究.實(shí)驗(yàn)先將不同數(shù)量用戶打分隨機(jī)化,再以均方根誤差為指標(biāo)衡量其余用戶聲譽(yù)值受影響程度.實(shí)驗(yàn)共在3個數(shù)據(jù)集中進(jìn)行,在MovieLens和Netflix兩個經(jīng)典實(shí)證數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明:系統(tǒng)中1%～60%的用戶進(jìn)行隨機(jī)打分時,基于關(guān)聯(lián)分析的CR算法始終保持很好的魯棒性;基于打分迭代的IARR算法的均方根誤差略有增大,最大值達(dá)到0.22,但整體波動較小;而改進(jìn)的基于打分迭代的IARR2算法的均方根誤差最大值達(dá)到0.695,其魯棒性的較大波動是因算法受高聲譽(yù)用戶的影響較大.在Douban數(shù)據(jù)集上的結(jié)果表明:在打分?jǐn)?shù)據(jù)稀疏情況下,CR算法也能保持很好的魯棒性.

在線打分系統(tǒng); 用戶聲譽(yù); 魯棒性

在互聯(lián)網(wǎng)大數(shù)據(jù)的背景下,電子商務(wù)、互聯(lián)網(wǎng)金融、在線產(chǎn)品打分等諸多用戶行為越來越多地融入網(wǎng)絡(luò)數(shù)據(jù)中[1].一方面,在線系統(tǒng)向用戶提供大量商品以供選擇,包括電影、書籍、網(wǎng)頁等[2];另一方面,用戶可以在系統(tǒng)中對商品進(jìn)行在線打分.近年來,在線用戶聲譽(yù)評價算法引起人們越來越多的關(guān)注[3],Zhou等[4]提出了基于皮爾森相關(guān)系數(shù)的迭代算法(簡稱CR算法).該算法引入量化評價兩變量相關(guān)程度的皮爾森相關(guān)系數(shù),使打分和產(chǎn)品質(zhì)量相似度越高的用戶得到的聲譽(yù)值也越高.在此基礎(chǔ)上,考慮到系統(tǒng)中亂打分用戶的存在,Liao等[5]提出了聲譽(yù)值再分配迭代算法(簡稱 IARR算法)和引入懲罰因子的聲譽(yù)值再分配迭代算法(簡稱IARR2算法).兩種算法增強(qiáng)了系統(tǒng)中高聲譽(yù)或打分產(chǎn)品多的用戶的影響力,因?yàn)檫@部分用戶常被認(rèn)為是系統(tǒng)中的可信用戶.

如今,各種在線評價系統(tǒng)中不乏隨意打分、惡意打分的用戶[6],因此建立準(zhǔn)確的用戶聲譽(yù)評定體系,可以提高產(chǎn)品綜合評分的準(zhǔn)確性[7].然而,網(wǎng)絡(luò)中普遍存在的亂打分現(xiàn)象[8],對聲譽(yù)系統(tǒng)的度量造成了一定干擾.因此,對聲譽(yù)評價模型效果的全面分析就顯得尤為重要.傳統(tǒng)對模型的評價,多從結(jié)果準(zhǔn)確性角度展開[4-5].然而,在準(zhǔn)確性的評價中,一方面,真實(shí)網(wǎng)絡(luò)中,產(chǎn)品的實(shí)際質(zhì)量一般未知,同時標(biāo)準(zhǔn)產(chǎn)品的界定也存在一定困難;另一方面,已有指標(biāo)很難準(zhǔn)確反映模型對系統(tǒng)中普遍存在亂打分用戶這一現(xiàn)象的抗干擾能力.不同真實(shí)網(wǎng)絡(luò)中,算法應(yīng)對亂打分干擾的魯棒性,對系統(tǒng)能否準(zhǔn)確評價用戶聲譽(yù)具有重要意義.基于以上思想,本文以均方根誤差為指標(biāo),分析了系統(tǒng)中不同數(shù)量用戶的隨機(jī)打分行為對其余用戶(以下簡稱誠實(shí)用戶)聲譽(yù)度量的影響,從而研究經(jīng)典聲譽(yù)評價算法的魯棒性.

本文對基于皮爾森相關(guān)系數(shù)的迭代算法、聲譽(yù)值再分配迭代算法及引入懲罰因子的改進(jìn)迭代算法的魯棒性進(jìn)行了實(shí)證分析.在MovieLens和Netflix兩個經(jīng)典數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果一致表明,在亂打分用戶數(shù)量不斷增加過程中,CR算法始終保持較好的魯棒性,IARR算法也相對穩(wěn)定,而IARR2算法受干擾較大.對IARR2算法魯棒性影響因素的分析結(jié)果表明,IARR2算法的魯棒性受聲譽(yù)值極大用戶的影響較大.在Douban數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,即便在打分?jǐn)?shù)據(jù)稀疏情況下,CR算法也能保持很好的魯棒性.

1　在線用戶聲譽(yù)評價算法

(1)

1.1CR算法

在CR算法中[4],根據(jù)式(1)得到產(chǎn)品α的質(zhì)量Qα,然后計算用戶i的打分和其對應(yīng)產(chǎn)品質(zhì)量間的皮爾森相關(guān)系數(shù).其公式表示為

(2)

用戶i的聲譽(yù)值Ri為

(3)

根據(jù)更新的用戶聲譽(yù)值,按式(1)重新計算所有產(chǎn)品質(zhì)量[10].模型迭代過程停止于所有產(chǎn)品前后兩次質(zhì)量值的均方差(見式(4))小于設(shè)定的閾值Δ(本文MovieLens數(shù)據(jù)集中Δ=10-5;Netflix中Δ=6×10-3;Douban中Δ=0.1).

(4)

1.2IARR算法

IARR算法[5]是基于CR算法建立的,將每次迭代中式(3)得到的用戶i的聲譽(yù)值記為TRi,然后按照式(5)對用戶i聲譽(yù)值進(jìn)行再分配.最后根據(jù)得到的新聲譽(yù)值,重新計算產(chǎn)品質(zhì)量,進(jìn)而循環(huán)迭代.

(5)

式中,θ為算法參數(shù),當(dāng)θ=1 時算法退化為經(jīng)典的用戶聲譽(yù)度量方法.IARR算法加入用戶聲譽(yù)再分配過程,目的在于放大高聲譽(yù)用戶的聲譽(yù)值.因?yàn)楦呗曌u(yù)的用戶常被認(rèn)為是系統(tǒng)中不存在亂打分行為的可信用戶,增加這部分用戶的影響力,可以在一定程度上削減迭代過程中噪聲數(shù)據(jù)的干擾,提高產(chǎn)品質(zhì)量評分和用戶聲譽(yù)評定的準(zhǔn)確性.

1.3IARR2算法

通常,只給很少量產(chǎn)品打分的用戶,不應(yīng)獲得很高的聲譽(yù)值.因?yàn)橛脩襞既徊聦Ξa(chǎn)品在大眾評分下的質(zhì)量很容易,但大量打分都能吻合就相對困難.因此,只有用戶打分?jǐn)?shù)據(jù)較充足時,其高聲譽(yù)才可信.同樣地,從產(chǎn)品角度,通過很少數(shù)用戶打分就獲得高質(zhì)量的評定,這一評價結(jié)果是很武斷的.

IARR2算法基于上述對用戶度和產(chǎn)品度的考慮[5],除了沿用前兩種算法的迭代過程,以及IARR算法的用戶聲譽(yù)再分配過程外,引入了兩個懲罰因子分別改進(jìn)式(1)和式(2).修改后的公式為

(6)

2　聲譽(yù)評價算法的魯棒性分析

以往對聲譽(yù)評價算法結(jié)果的分析多從準(zhǔn)確性角度展開,并且常采用肯德爾系數(shù)(簡稱τ值)[11]和AUC算法[12].本文則從魯棒性角度,以均方根誤差值(簡稱RMSE值)為指標(biāo),分析聲譽(yù)評價算法對網(wǎng)絡(luò)中隨機(jī)打分用戶情況的抗干擾能力,算法的參數(shù)θ設(shè)定為3.

2.1魯棒性分析方法

2.2實(shí)證分析數(shù)據(jù)集

本文的研究選擇了MovieLens和Netflix兩個包含用戶對電影在線打分記錄的經(jīng)典數(shù)據(jù)集,以及包括用戶對圖書在線打分記錄的Douban數(shù)據(jù)集.實(shí)驗(yàn)選用的MovieLens數(shù)據(jù)集包含943個用戶對1 682個電影的100 000條打分記錄.Netflix數(shù)據(jù)集規(guī)模相對很大,實(shí)驗(yàn)中選出其中打分電影不少于20個的5 000名用戶的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集.Douban數(shù)據(jù)集稀疏性很大,因此本文也選取打分不少于20個的40 038個用戶的所有記錄作為實(shí)驗(yàn)數(shù)據(jù)集.同時,用戶的打分都是1～5的整數(shù).表1描述了數(shù)據(jù)集的一些基本特性.

表1實(shí)驗(yàn)數(shù)據(jù)集的基本特性

Tab.1Propertiesoftheapplieddatasets

數(shù)據(jù)集用戶數(shù)產(chǎn)品數(shù)打分?jǐn)?shù)量用戶平均度產(chǎn)品平均度MovieLens 9431682100000106 59Netflix500017770894482179 50Douban4003878094178494345 23

2.3聲譽(yù)評價算法的魯棒性分析

將3種在線用戶聲譽(yù)評價算法分別在3個數(shù)據(jù)集上按上述分析方法進(jìn)行實(shí)驗(yàn).在不同數(shù)據(jù)集中逐次設(shè)定隨機(jī)化用戶數(shù)n從1%～60%為隨機(jī)打分用戶.進(jìn)而,對比隨機(jī)打分前后算法得到的均方根誤差RMSE的值.在MovieLens數(shù)據(jù)集中,共實(shí)驗(yàn)50次(n=10,20,30,…,500);在Netflix數(shù)據(jù)集中,共實(shí)驗(yàn)31次(n=50,100,200,300,…,3 000);在Douban數(shù)據(jù)集中,共實(shí)驗(yàn)11次(n=4 000,6 000,8 000,…,24 000).實(shí)驗(yàn)結(jié)果如圖1所示.

圖1中橫坐標(biāo)n為每次實(shí)驗(yàn)假定的亂打分用戶數(shù)量,縱坐標(biāo)RMSE為網(wǎng)絡(luò)中n個用戶亂打分狀態(tài)下其余誠實(shí)用戶聲譽(yù)值與各自原始聲譽(yù)值兩組變量的均方根誤差.圖中結(jié)果均為5次獨(dú)立實(shí)驗(yàn)的平均值.

從圖1(a)和(b)可見,在MovieLens和Netflix兩個經(jīng)典數(shù)據(jù)集中,隨著系統(tǒng)中亂打分用戶的數(shù)量不斷增加,CR和IARR算法的RMSE整體上呈現(xiàn)緩慢上升趨勢,即隨著亂打分用戶數(shù)量的增加,算法對誠實(shí)用戶聲譽(yù)計算結(jié)果的變化略微增大.CR算法的RMSE值在MovieLens數(shù)據(jù)集中最大值為0.048 6,在Netflix中最大值也僅為0.064 3.因此,在CR算法中,亂打分用戶的出現(xiàn)對系統(tǒng)中誠實(shí)用戶聲譽(yù)評價的干擾較小,即CR算法在應(yīng)對網(wǎng)絡(luò)中不確定數(shù)量用戶亂打分情況時,聲譽(yù)評價結(jié)果相對穩(wěn)定.與CR算法相比結(jié)果變化較大的IARR算法,在兩個不同數(shù)據(jù)集下的RMSE最大值也只在0.2左右,并且波動較小.所以,IARR算法的魯棒性也相對較好.然而,對于實(shí)驗(yàn)結(jié)果顯著波動的IARR2算法,其RMSE最大值在Netflix數(shù)據(jù)集上接近0.35,在MovieLens數(shù)據(jù)集上更是超過0.6.同時,隨著亂打分用戶數(shù)量的變化,IARR2算法結(jié)果也出現(xiàn)不同程度的較大波動.因此,IARR2算法在網(wǎng)絡(luò)中存在不確定數(shù)量用戶亂打分現(xiàn)象時,算法魯棒性波動較大.

圖1　MovieLens,Netflix和Douban數(shù)據(jù)集中CR,IARR,IARR2算法的魯棒性分析結(jié)果

對算法原理進(jìn)行分析,CR和IARR模型的聲譽(yù)值結(jié)果是基于用戶打分和其相應(yīng)打分產(chǎn)品平均質(zhì)量間的皮爾森相關(guān)系數(shù)產(chǎn)生的.在線打分系統(tǒng)中,對同一產(chǎn)品進(jìn)行打分的用戶分布廣泛,因此部分隨機(jī)用戶的亂打分行為使產(chǎn)品平均質(zhì)量產(chǎn)生較大變化的可能性較小,個體行為也就不會對系統(tǒng)整體評價產(chǎn)生較大影響.然而,在產(chǎn)品質(zhì)量計算中引入最大聲譽(yù)值作為懲罰因子的IARR2算法,使得高聲譽(yù)用戶在產(chǎn)品質(zhì)量評價中起關(guān)鍵性作用.因此,部分聲譽(yù)極高用戶的行為變動就可能對整個評價系統(tǒng)產(chǎn)生較大干擾.

從圖1(c)可見,在Douban數(shù)據(jù)集中,隨著亂打分用戶數(shù)量的增加,3種算法整體都呈現(xiàn)平緩上升趨勢,其中CR算法RMSE值始終最小,IARR2算法存在小幅波動.Douban數(shù)據(jù)集中打分記錄稀疏,產(chǎn)品平均度相對較小,因此用戶間基于共同打分產(chǎn)品產(chǎn)生的關(guān)聯(lián)性也較小,所以,部分用戶隨機(jī)打分行為導(dǎo)致誠實(shí)用戶聲譽(yù)值的變化就相對平緩,波動小.Douban數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,CR算法在稀疏性網(wǎng)絡(luò)中也能保持很好的魯棒性.

3　IARR2算法魯棒性影響因素的分析

本節(jié)對圖1(a)和(b)實(shí)驗(yàn)結(jié)果中IARR2算法出現(xiàn)的突變和不規(guī)律現(xiàn)象展開進(jìn)一步研究分析.在MovieLens和Netflix兩個經(jīng)典數(shù)據(jù)集中,用戶打分彼此關(guān)聯(lián)性較大,通過分析算法原理發(fā)現(xiàn),IARR2算法中懲罰因子的引入,使度大、原始聲譽(yù)高的這部分特定用戶的打分?jǐn)?shù)據(jù)對算法評價結(jié)果起決定性作用,所以當(dāng)這部分特定用戶的數(shù)據(jù)出現(xiàn)變化,或者其他用戶數(shù)據(jù)的變化對這小部分用戶產(chǎn)生較大影響時,算法對其他用戶的聲譽(yù)評價就可能產(chǎn)生較大幅度變化.

3.1特定用戶的選取和分析方法

為了進(jìn)一步研究IARR2算法受特定用戶影響較大這一特性,本文通過對IARR2算法的魯棒性分析結(jié)果和用戶度及原始聲譽(yù)值進(jìn)行綜合分析,選取算法中原始聲譽(yù)值極高的用戶,研究其單獨(dú)的隨機(jī)打分行為在兩個經(jīng)典數(shù)據(jù)集中對系統(tǒng)中其余用戶聲譽(yù)評價的影響.

在MovieLens數(shù)據(jù)集中,將其中唯一一個原始聲譽(yù)值極高用戶的打分隨機(jī)化,分析系統(tǒng)中其余用戶聲譽(yù)值的變化程度.該用戶具體信息見表2(見下頁),同時IARR2算法在MovieLens數(shù)據(jù)集中得到的第二大原始聲譽(yù)值僅為1.77;在Netflix數(shù)據(jù)集中,研究原始聲譽(yù)值極大的前兩位用戶同時進(jìn)行隨機(jī)打分,對系統(tǒng)其余用戶聲譽(yù)值評價的影響.這兩位用戶具體信息見表2,同時位列第三位的原始聲譽(yù)值僅為4.82.

3.2特定用戶對IARR2算法魯棒性影響的分析結(jié)果

按上述實(shí)驗(yàn)方法,在MovieLens和Netflix兩個數(shù)據(jù)集中,分別選定IARR2算法中得到極大聲譽(yù)值的用戶為系統(tǒng)中的亂打分用戶,然后通過IARR2算法重新計算用戶聲譽(yù)值,最后統(tǒng)計除選定用戶外的其余所有用戶的新聲譽(yù)值和對應(yīng)原始聲譽(yù)值兩組變量的RMSE值.10次獨(dú)立實(shí)驗(yàn)的平均結(jié)果見表2.

表2聲譽(yù)值極大用戶對IARR2算法魯棒性影響的分析結(jié)果

Tab.2Effect of users with high reputation on the robustness of IARR2

數(shù)據(jù)集用戶編號原始聲譽(yù)值RMSEMovieLens27614.279960.4805Netflix1546 18.424813506 17.906750.5315

兩個數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,IARR2算法的魯棒性受算法中聲譽(yù)值極大用戶的影響較大.因此,如果這小部分特定用戶自身打分行為發(fā)生變化,或者系統(tǒng)中其他用戶亂打分的行為對這部分特定用戶聲譽(yù)值產(chǎn)生較大影響時,都可能導(dǎo)致系統(tǒng)對其余用戶的聲譽(yù)評價產(chǎn)生較大改變.

4　結(jié)束語

本文分析了在線用戶聲譽(yù)評價中3種常用算法在不同數(shù)據(jù)集下的魯棒性.實(shí)驗(yàn)通過設(shè)定不同數(shù)量用戶隨機(jī)打分,以RMSE值反映算法對其余用戶聲譽(yù)評價的變化,從而分析不同算法對用戶隨機(jī)打分行為的魯棒性.3種算法在兩個經(jīng)典數(shù)據(jù)集下的RMSE值表明,CR算法魯棒性相對最好,IARR算法也相對穩(wěn)定,而IARR2算法的RMSE值波動幅度較大.對IARR2算法魯棒性影響因素的分析結(jié)果表明,IARR2算法的評價結(jié)果受其中聲譽(yù)值極大用戶的影響較大,從而導(dǎo)致算法魯棒性波動較大.在較稀疏的Douban數(shù)據(jù)集中的結(jié)果表明,在打分?jǐn)?shù)據(jù)稀疏情況下,CR算法也能保持很好的魯棒性.因此,對于網(wǎng)絡(luò)中普遍存在的用戶亂打分現(xiàn)象,就魯棒性而言,應(yīng)優(yōu)先選擇CR算法.該工作對于進(jìn)一步分析在線社交網(wǎng)絡(luò)的結(jié)構(gòu)特征對于動力學(xué)的影響具有一定參考意義[13-15].

[1]郭強(qiáng),劉建國.在線社會系統(tǒng)的用戶行為分析研究進(jìn)展[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2015,12(2):97-102.

[2]Lü L Y,MEDO M,YEUNG C H,et al.Recommender systems[J].Physics Reports,2012,519(1):1-49.

[3]盧志剛.電子商務(wù)聲譽(yù)——結(jié)構(gòu)與評價研究[M].北京:清華大學(xué)出版社,2014.

[4]ZHOU Y B,LEI T,ZHOU T.A robust ranking algorithm to spamming[J].EPL (Europhysics Letters),2011,94(4):48002.

[5]LIAO H,ZENG A,XIAO R,et al.Ranking reputation and quality in online rating systems[J].PLoS One,2014,9(5):e97146.

[6]MASUM H,ZHANG Y C.Manifesto for the reputation society[EB/OL].(2014-07-05)[2015-08-22].http:∥firstmonday.org/ojs/index.php/fm/article/view/1158/1078.

[7]LIM E P,NGUYEN V A,JINDAL N,et al.Detecting product review spammers using rating behaviors[C]∥Proceedings of the 19thACM International Conference on Information and Knowledge Management.New York:ACM,2010:939-948.

[8]ZENG A,CIMINI G.Removing spurious interactions in complex networks[J].Physical Review E,2012,85(3):036101.

[9]ZENG A,YEUNG C H,SHANG M S,et al.The reinforcing influence of recommendations on global diversification[J].EPL (Europhysics Letters),2012,97(1):18005.

[10]LIAO H,CIMINI G,MEDO M.Measuring quality,reputation and trust in online communities[M]∥CHEN L,FELFERNIG A,LIU J M,et al.Foundations of Intelligent Systems.Heidelberg:Springer,2012:405-414.

[11]KENDALL M G.A new measure of rank correlation[J].Biometrika,1938,30(1/2):81-93.

[12]HANLEY J A,MCNEIL B J.The meaning and use of the area under a receiver operating characteristic (ROC) curve[J].Radiology,1982,143(1):29-36.

[13]李旭東,劉建國.軌道交通網(wǎng)絡(luò)的可達(dá)性及其網(wǎng)絡(luò)結(jié)構(gòu)分析[J].上海理工大學(xué)學(xué)報,2015,37(3):279-283.

[14]周萍,張子柯,章恬,等.一種基于社會化媒體和社會網(wǎng)絡(luò)結(jié)構(gòu)的混合推薦模型[J].上海理工大學(xué)學(xué)報,2014,36(3):267-276.

[15]石珂瑞,劉建國.二階有向相似性對協(xié)同過濾算法的影響[J].上海理工大學(xué)學(xué)報,2014,36(1):31-33.

(編輯:丁紅藝)

Robustness Analysis of Online User Reputation Measurements

LI Shengnan1,YANG Kai1,LIU Xiaolu1,LIU Jianguo1,2,GUO Qiang1

(1.Research Center for Complex Systems Science,University for Shanghai for Science and Technology,Shanghai 200093,China; 2.Laboratory Centre,Shanghai University of Finance and Economics,Shanghai 200433,China)

Malicious and spam actions in online rating systems affect the user reputation measurements greatly.By setting different number of spammers and evaluating its effect by the root-mean-square error (RMSE),the robustness of three typical iterative-oriented online user reputation measurements was investigated.The results for MovieLens and Netflix data sets show that when facing with 1%～60% of spammers in the network,the CR algorithm has the best performance of robustness.The largest RMSE value of the iterative algorithm of reputation IARR reaches 0.22,with slight fluctuation of the RMSE.And the RMSE value of the improved iterative algorithm of reputation IARR2 reaches 0.695.The result for Douban data set shows that the CR algorithm still maintains great robustness even when the users rate few common items.

online rating system; user reputation; robustness

1007-6735(2016)04-0362-05

10.13255/j.cnki.jusst.2016.04.010

2015-08-22

國家自然科學(xué)基金資助項目(71271126,71374177,61361125);教育部博士點(diǎn)基金資助項目(20120078110002);上海市東方學(xué)者特聘教授,上海市曙光學(xué)者(14SG42)

李圣楠(1995-),女,碩士研究生.研究方向:社會網(wǎng)絡(luò)分析.E-mail:lishengnan318@163.com

劉建國(1979-),男,教授.研究方向:網(wǎng)絡(luò)科學(xué).E-mail:liujg004@ustc.edu.cn

N 949

A