基于觀點(diǎn)傳播的改進(jìn)相似性計(jì)算評(píng)分預(yù)測(cè)方法

艾 均, 李林志, 蘇 湛, 鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

基于觀點(diǎn)傳播的改進(jìn)相似性計(jì)算評(píng)分預(yù)測(cè)方法

艾 均, 李林志, 蘇 湛, 鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

通過研究網(wǎng)絡(luò)結(jié)構(gòu)上的觀點(diǎn)傳播與協(xié)同過濾算法,基于對(duì)觀點(diǎn)傳播算法的優(yōu)化,提出了基于用戶相似和物品相似推薦系統(tǒng)評(píng)分預(yù)測(cè)算法.設(shè)計(jì)的算法修正了現(xiàn)有相似研究中在目標(biāo)比較相似時(shí),相似性結(jié)果為零的問題,將用戶(或物品)的相似度定義為用戶(或物品)間的觀點(diǎn)數(shù)目和差異在相應(yīng)復(fù)雜網(wǎng)絡(luò)中的傳播結(jié)果,并提出了相應(yīng)的推薦算法.在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明,提出的算法與幾種典型的現(xiàn)有方法相比較,具有更高的準(zhǔn)確性,并且優(yōu)于觀點(diǎn)傳播算法.

復(fù)雜網(wǎng)絡(luò); 推薦系統(tǒng); 評(píng)分預(yù)測(cè); 觀點(diǎn)傳播; 相似度

隨著互聯(lián)網(wǎng)信息技術(shù)的高速發(fā)展,人們已經(jīng)進(jìn)入到信息過載[1-2]的時(shí)代.面對(duì)海量的信息,對(duì)信息消費(fèi)者而言,能找到自己喜歡的信息是一個(gè)巨大挑戰(zhàn),同時(shí)對(duì)信息生產(chǎn)者來說,產(chǎn)生用戶感興趣的信息并推送給用戶也是一個(gè)挑戰(zhàn).在此情況下,推薦系統(tǒng)顯得尤為重要,它聯(lián)系用戶和物品,發(fā)現(xiàn)用戶興趣點(diǎn)并推薦其感興趣的信息,解決信息過載問題.

推薦系統(tǒng)中研究和應(yīng)用最廣泛的是協(xié)同過濾算法[3-4],此外,基于隱語義模型[5]的算法自Netflix比賽以來也得到研究者的青睞.最近,基于網(wǎng)絡(luò)結(jié)構(gòu)[6]的推薦算法由于其更高的計(jì)算效率和準(zhǔn)確率,逐漸引起學(xué)者的廣泛關(guān)注.它是將用戶和物品看成抽象的網(wǎng)絡(luò)節(jié)點(diǎn),通過構(gòu)造一個(gè)用戶-物品網(wǎng)絡(luò),利用物理學(xué)的方法研究個(gè)性化推薦.如Zhang等[7-8]加入用戶對(duì)物品的打分信息,實(shí)現(xiàn)了基于熱傳導(dǎo)和物質(zhì)擴(kuò)散的推薦算法;Zhou等[9]通過結(jié)合物質(zhì)擴(kuò)散和熱傳導(dǎo),提高了推薦算法的準(zhǔn)確性和多樣性;Huang等[10]在協(xié)同過濾算法中加入擴(kuò)散動(dòng)力學(xué)方法,部分解決了數(shù)據(jù)稀疏性問題.最近很多研究者用網(wǎng)絡(luò)的方法[11-13]研究個(gè)性化推薦算法也取得了不錯(cuò)的成就.文獻(xiàn)[11]將對(duì)象-用戶網(wǎng)絡(luò)模型中節(jié)點(diǎn)之間的關(guān)系作為研究的重點(diǎn),研究了對(duì)象與對(duì)象的關(guān)系,用戶與用戶的關(guān)系,以及對(duì)象與用戶之間的關(guān)系,從異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系出發(fā)設(shè)計(jì)了新的方法.文獻(xiàn)[12]應(yīng)用網(wǎng)絡(luò)模型,混合了質(zhì)量擴(kuò)散(mass diffusion,MD)和熱傳導(dǎo)(heat conduction,HC)方法,研究了不同權(quán)重對(duì)混合算法效果的影響.文獻(xiàn)[13]設(shè)計(jì)了一個(gè)參數(shù)來調(diào)節(jié)擴(kuò)散的傾向性.上面的算法主要研究了推薦列表,在評(píng)分預(yù)測(cè)方面的研究較少.

本文基于網(wǎng)絡(luò)結(jié)構(gòu)的觀點(diǎn)傳播理論[8]和觀點(diǎn)傳播過程的用戶相似算法[12],發(fā)現(xiàn)在進(jìn)行相似性計(jì)算時(shí),現(xiàn)有的一些算法會(huì)在2個(gè)對(duì)象比較相似的情況下,出現(xiàn)相似性為零的計(jì)算結(jié)果.為了解決這一問題,本文改進(jìn)了算法相似性的計(jì)算方法,避免了這一問題的出現(xiàn),提出了基于觀點(diǎn)傳播的物品相似算法,并與協(xié)同過濾結(jié)合,預(yù)測(cè)用戶對(duì)物品的評(píng)分.實(shí)驗(yàn)結(jié)果證明,與改進(jìn)前的算法和傳統(tǒng)的協(xié)同過濾算法比較,本文所用算法的準(zhǔn)確率均有提高,并且算法的時(shí)間復(fù)雜度較低.

1 研究方法

本文研究觀點(diǎn)的傳播過程與協(xié)同過濾結(jié)合的推薦算法,基于傳播的用戶相似評(píng)分預(yù)測(cè)方法[12],在此基礎(chǔ)上修改了缺陷,降低了算法的誤差率,并提出了基于傳播的物品相似推薦算法.

首先討論基于用戶觀點(diǎn)傳播(user opinion spreading,UOS)的推薦算法.假設(shè)一個(gè)推薦系統(tǒng)中有m個(gè)用戶和n個(gè)物品,記用戶和物品的集合分別為U={u1,u2,…,um}和O={o1,o2,…,on},則用戶對(duì)物品的評(píng)分矩陣記為R={riα}∈Rm,n,其中,riα表示用戶i對(duì)物品α的評(píng)分值,值為整數(shù),范圍屬于[1,5].另外,設(shè)置一個(gè)與評(píng)分矩陣對(duì)應(yīng)的矩陣A={aiα}∈Rm,n,若用戶i對(duì)物品α評(píng)過分,則aiα為1;否則,為0.將用戶集合和物品集合放到一個(gè)網(wǎng)絡(luò)中,則ki和kα分別表示用戶和物品的度值.

在利用用戶對(duì)物品的評(píng)分信息時(shí),需要考慮每個(gè)用戶對(duì)物品的觀點(diǎn)是不同的.例如,有些用戶比較苛刻,屬于完美主義者,對(duì)物品的評(píng)分普遍偏低;而有些用戶沒有那么苛刻,經(jīng)常會(huì)給出較高的分值.所以,客觀地評(píng)分實(shí)際受個(gè)人主觀的影響.為了消除這種不利影響,可通過公式將評(píng)分歸一化

(1)

式中:ri,max和ri,min代表用戶i評(píng)分記錄中的最高分和最低分;eiα為用戶評(píng)分歸一化之后的結(jié)果,若最高分與最低分相等,可將歸一化值賦為0,eiα∈[-1,1].

通過歸一化公式,用戶的評(píng)分值范圍變?yōu)?1～1之間,此時(shí)的值代表了用戶的客觀評(píng)價(jià).例如,用戶i評(píng)過的最高分和最低分為5和3,而用戶j評(píng)過的最高分和最低分為3和1,他們對(duì)于同一物品α的真實(shí)評(píng)分都是3,此時(shí),對(duì)用戶i而言,3分是其評(píng)分記錄的最低分,說明他不喜歡該物品;用戶j的3分卻是其評(píng)分記錄的最高分,代表他比較喜歡該物品.通過歸一化后,eiα=-1和ejα=1,可以表示他們之間的差異.

文獻(xiàn)[12]使用資源分配和評(píng)分結(jié)合方法計(jì)算用戶間的相似性.

(2)

式中:sij表示用戶i對(duì)用戶j的影響,可看作是用戶i與用戶j的相似度.

歸一化后,用戶評(píng)分乘積越大,共同評(píng)過分的物品越多,表示用戶越相似.但用戶間的影響是有向的,即sij≠sji.為了消除相似度為負(fù)值對(duì)預(yù)測(cè)值的影響,定義相似矩陣為Smm={sij},sij為負(fù)數(shù)時(shí),則賦值為0,且將用戶自身的相似度也變?yōu)?.

用戶對(duì)物品的的評(píng)分預(yù)測(cè)為

(3)

這與協(xié)同過濾算法很相似,都是利用與用戶最相似的鄰居的評(píng)分預(yù)測(cè)用戶對(duì)物品的評(píng)分值.

1.1 基于觀點(diǎn)傳播的用戶相似算法

(4)表1 MovieLens訓(xùn)練集上歸一化值為0占總評(píng)分?jǐn)?shù)目的比例Tab.1 Proportion of normalized-value zero in the total user-item ratings of MovieLens training set

用1-|eiα-ejα|代替eiαejα,取值范圍不變,但更精確地表達(dá)了用戶間的相似程度.例如,用戶i、用戶j和用戶k的最高、最低評(píng)分均為5和1,但對(duì)物品α的評(píng)分分別為3,3,5,故歸一化后的值分別為eiα=0,ejα=0,ekα=1.計(jì)算改進(jìn)前,用戶j和用戶k對(duì)用戶i的影響則均為0,無法區(qū)分評(píng)分值不同用戶間的相似程度;而改進(jìn)后用戶j對(duì)用戶i的影響為1,用戶k對(duì)用戶i的影響為0,這與直觀用戶評(píng)分值表達(dá)的含義一樣,提高了用戶相似度的準(zhǔn)確率.基于觀點(diǎn)傳播的用戶相似(US-OS)算法是用戶觀點(diǎn)傳播(UOS)算法的改進(jìn),并且取得了更好的效果.

1.2 基于觀點(diǎn)傳播的物品相似算法

基于鄰域的協(xié)同過濾算法有2種:基于用戶相似的協(xié)同過濾和基于物品相似的協(xié)同過濾.并且通過分析基于皮爾遜相關(guān)系數(shù)的協(xié)同過濾算法,發(fā)現(xiàn)基于物品相似的協(xié)同過濾的評(píng)分預(yù)測(cè)效果更好;另外,在真實(shí)的電影網(wǎng)站或圖書網(wǎng)站中,用戶的數(shù)目要遠(yuǎn)遠(yuǎn)多于物品數(shù)目,利用物品相似進(jìn)行推薦,在時(shí)間復(fù)雜度上要小很多.因此,本文通過基于傳播過程的用戶相似算法,提出基于傳播過程的物品相似算法.

基于物品相似的推薦算法,本質(zhì)上是利用用戶對(duì)物品的歷史評(píng)分記錄,建立一個(gè)物品的相似矩陣,在給用戶推薦某個(gè)物品時(shí),利用用戶的歷史評(píng)分記錄,找到與該物品最相似的n個(gè)物品,通過用戶對(duì)該物品鄰居的評(píng)分,預(yù)測(cè)用戶對(duì)該物品的評(píng)分值.在計(jì)算2個(gè)物品相似度時(shí),必須是一個(gè)用戶同時(shí)對(duì)這2個(gè)物品評(píng)過分,因此,在評(píng)分的歸一化公式上,仍然可以使用式(1).

基于觀點(diǎn)傳播的物品相似IS-OS算法的相似度公式為

(5)

式中:sαβ表示物品α對(duì)物品β的影響,可看作是物品α與物品β的相似度.

但物品相似度是有向的,即2個(gè)物品間的影響是不同的.為了消除相似度為負(fù)值對(duì)預(yù)測(cè)值的影響,定義相似矩陣為Snn={sαβ},將sαβ為負(fù)數(shù)的值全部賦值為0.用戶對(duì)物品的評(píng)分預(yù)測(cè)式與式(3)類似.

(6)

為了比較本文所用算法的優(yōu)劣,分別與基于Pearson[14]相關(guān)系數(shù)的用戶相似算法和物品相似算法比較,實(shí)驗(yàn)結(jié)果證明,本文所用算法降低了評(píng)分預(yù)測(cè)誤差.基于Pearson相關(guān)系數(shù)的用戶相似度和基于Pearson相關(guān)系數(shù)的物品相似度分別為

(7)

(8)

Pearson相關(guān)系數(shù)的取值范圍為[-1,1].

2 實(shí)驗(yàn)結(jié)果與討論

使用MovieLens 100k數(shù)據(jù)集驗(yàn)證所用算法的準(zhǔn)確性,該數(shù)據(jù)集包括943個(gè)用戶對(duì)1 682部電影進(jìn)行的100 000條評(píng)分記錄,評(píng)分值是1～5的整數(shù),并且保證每個(gè)用戶至少對(duì)20部電影評(píng)過分,數(shù)據(jù)集的數(shù)據(jù)稀疏度為93.70%.為了驗(yàn)證算法,使用折5交叉驗(yàn)證方法[15],將用戶-物品評(píng)分記錄隨機(jī)地平均分成5組,使用其中的4組作為訓(xùn)練集,1組作為測(cè)試集,依次將每組作為測(cè)試集,并取5次結(jié)果的平均值作為最終的結(jié)果.

(9)

(10)

雖然MAE計(jì)算和理解簡(jiǎn)單,但存在一定的局限性,MAE低的推薦系統(tǒng),只能說明該系統(tǒng)更擅長預(yù)測(cè)低分商品的評(píng)分[16].RMSE指標(biāo)加重了對(duì)預(yù)測(cè)不準(zhǔn)評(píng)分的懲罰,對(duì)系統(tǒng)的要求更苛刻.

將相似度為負(fù)數(shù)賦值成0的優(yōu)化[17],更能提高算法的準(zhǔn)確度.本文中所有的推薦算法均采用該方法,因此,將改進(jìn)的皮爾遜用戶協(xié)同過濾(UCF)算法簡(jiǎn)記為UCF-Pearson-Opt,將改進(jìn)的皮爾遜物品協(xié)同過濾(ICF)算法簡(jiǎn)記為ICF-Pearson-Opt.將用戶觀點(diǎn)傳播記為UOS,而基于UOS改進(jìn)的觀點(diǎn)傳播的用戶相似算法記為US-OS,并將本文新提出的基于觀點(diǎn)傳播的物品相似算法記為IS-OS.

為了比較不同算法的預(yù)測(cè)效果,本文計(jì)算了5種算法在不同鄰居數(shù)目的平均絕對(duì)誤差和均方根誤差,結(jié)果如圖1和圖2所示.

在基于用戶相似的推薦算法中,本文所用的基于UOS算法改進(jìn)的US-OS算法的效果最好,在用戶相似鄰居個(gè)數(shù)n=40時(shí)得到最低的誤差,MAE=0.734 3,RMSE=0.936 1,并且隨著用戶相似鄰居個(gè)數(shù)的增加,曲線接近水平增長,說明US-OS算法的穩(wěn)定性較好.US-OS算法的誤差比UOS算法的更低,MAE和RMSE分別提高了0.88%和0.8%,說明本文所用改進(jìn)方法的有效性.而傳統(tǒng)的基于優(yōu)化的皮爾遜用戶協(xié)同過濾算法的效果最差,US-OS算法的MAE比其提高了1%,RMSE比其提高了1.5%,并且算法的時(shí)間復(fù)雜度并不高.

圖1 5種算法在不同鄰居個(gè)數(shù)下的平均絕對(duì)誤差Fig.1 Mean average error results of five algorithms with different number of neighbors

圖2 5種算法在不同鄰居個(gè)數(shù)下的均方根誤差Fig.2 Root mean square error of five algorithms with different number of neighbors

在基于物品相似的推薦算法中,本文所提出的基于觀點(diǎn)傳播的物品相似(IS-OS)推薦算法的效果最好.在物品相似鄰居個(gè)數(shù)n=20時(shí)得到最低的MAE=0.713,而當(dāng)n=30時(shí)得到最低的RMSE=0.910 9,并且隨著物品相似鄰居個(gè)數(shù)的增加,曲線接近水平增長,說明IS-OS算法的穩(wěn)定性較好.比較傳統(tǒng)的基于優(yōu)化的皮爾遜物品協(xié)同過濾算法,IS-OS算法的MAE比其提高了1%,RMSE比其提高了1.15%.

3 結(jié) 論

綜合5種算法的結(jié)果可知,IS-OS算法的效果最好,比US-OS算法的MAE提高了2.1%,RMSE提高了2.5%.綜上可得結(jié)論:在MoiveLens 100k數(shù)據(jù)集上,基于物品相似的推薦算法要優(yōu)于基于用戶相似的推薦算法;基于物理學(xué)理論中的傳播過程相似度計(jì)算方法要優(yōu)于傳統(tǒng)的皮爾遜相關(guān)系數(shù)相似度計(jì)算方法;采用評(píng)分?jǐn)?shù)值歸一化方法和相似度有向方法能有效提高算法的準(zhǔn)確度.

研究了基于用戶觀點(diǎn)傳播的推薦算法,針對(duì)其中的部分缺陷,提出改進(jìn)的方法,命名為基于傳播過程的用戶相似(US-OS)推薦算法,并提出基于傳播過程的物品相似(IS-OS)推薦算法.在MoiveLens數(shù)據(jù)集上的實(shí)驗(yàn)證明,US-OS算法在n=40時(shí),得到最好的效果,MAE和RMSE分別為0.734 3和0.936 1,相比傳統(tǒng)的皮爾遜用戶協(xié)同過濾算法的MAE和RMSE分別提高了1%和1.5%.IS-OS算法在以上5種算法中效果最好,在n=20時(shí),最低的MAE=0.713,n=30時(shí),最低的RMSE=0.910 9,相比傳統(tǒng)的皮爾遜物品協(xié)同過濾算法的MAE和RMSE分別提高了1%和1.15%.且比US-OS算法的MAE和RMSE分別提高了2.1%和2.5%.由此證明了本文所提算法的有效性,并且證明了在MoiveLens數(shù)據(jù)集上,基于物品相似的推薦算法要優(yōu)于基于用戶相似的推薦算法.

[1] JONES Q,RAVID G,RAFAELI S.Information overload and the message dynamics of online interaction spaces:a theoretical model and empirical exploration[J].Information Systems Research,2004,15(2):194-210.

[2] FENG L,HU Y Q,LI B W,et al.Competing for attention in social media under information overload conditions[J].PLoS One,2015,10(7):e0126090.

[3] LINDEN G,SMITH B,YORK J.Amazon.com recommendation:item-to-item collaborative filtering[J].IEEE Internet Computing,2003,7(1):76-80.

[4] HUANG Z,ZENG D,CHEN H.A comparison of collaborative-filtering recommendation algorithms for E-commerce[J].IEEE Intelligent Systems,2007,22(5):68-78.

[5] ZHANG L,LI C R,XU Y F,et al.An efficient solution to factor drifting problem in the pLSA model[C]∥Proceedings of 5th International Conference on Computer and Information Technology.Shanghai:IEEE,2005:175-181.

[6] GHARIBSHAH J,JALILI M.Connectedness of users-items networks and recommender systems[J].Applied Mathematics and Computation,2014,243:578-584.

[7] ZHANG Y C,BLATTNER M,YU Y K.Heat conduction process on community networks as a recommendation model[J].Physical Review Letters,2007,99(15):154301.

[8] ZHANG Y C,MEDO M,REN J,et al.Recommendation model based on opinion diffusion[J].Europhysics Letters,2007,80(6):68003.

[9] ZHOU T,KUSCSIK Z,LIU J G,et al.Solving the apparent diversity-accuracy dilemma of recommender systems[J].Proceedings of the National Academy of Sciences of the United States of America,2010,107(10):4511-4515.

[10] HUANG Z,CHEN H,ZENG D.Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering[J].ACM Transactions on Information Systems,2004,22(1):116-142.

[11] NIE D C,AN Y H,DONG Q,et al.Information filtering via balanced diffusion on bipartite networks[J].Physica A:Statistical Mechanics and its Applications,2015,421:44-53.

[12] HE X S,ZHOU M Y,ZHUO Z,et al.Predicting online ratings based on the opinion spreading process[J].Physica A:Statistical Mechanics and its Applications,2015,436:658-664.

[13] GAN M X,JIANG R.ROUND:walking on an object-user heterogeneous network for personalized recommendations[J].Expert Systems with Applications,2015,42(22):8791-8804.

[14] HERLOCKER J L,KONSTAN J A,TERVEEN L G,et al.Evaluating collaborative filtering recommender systems[J].ACM Transactions on Information Systems,2004,22(1):5-53.

[15] GARDY J L,SPENCER C,WANG K,et al.PSORT-B:improving protein subcellular localization prediction for Gram-negative bacteria[J].Nucleic Acids Research,2003,31(13):3613-3617.

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

[17] HERLOCKER J,KONSTAN J A,RIEDL J.An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms[J].Information Retrieval,2002,5(4):287-310.

(編輯:石 瑛)

Online-Rating Prediction Based on Opinion Spreading and an Improved Similarity Calculation Method

AI Jun, LI Linzhi, SU Zhan, WU Chunxue

(SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

The relation between users and items in the recommendation system was considered as a complex network structure, and the binary relation between users and items was used to construct a graph model,based on which a diffusion dynamics method was introduced to study the recommendation algorithm.Through studying the ideas spreading in the network structure and collaborative filtering algorithms,two optimized algorithms were presented based on user similarity and item similarity,respectively.The proposed approach provides a correction method for zero value problems of similarity calculation,ignored in most existing publications.The similarity of users (or items) was defined as the number of corresponding views which a user (or items) owns and differences between those viewpoints spreading in the complex network.Using MovieLens data set,the experiments show that the presented algorithm has better performance than the collaborative filtering algorithm based on Pearson correlation coefficient and some other existing methods.

complexnetwork;recommendationsystem;ratingprediction;opinionspreading;similarity

1007-6735(2017)03-0236-05

10.13255/j.cnki.jusst.2017.03.006

2016-09-29

上海市自然科學(xué)基金資助項(xiàng)目(14ZR1428800;15ZR1428600)

艾均(1980-),男,講師.研究方向:復(fù)雜網(wǎng)絡(luò).E-mail:aijun@outlook.com

TP 393

A