基于交集占比與時間衰減的協(xié)同過濾推薦算法研究

吳崢　陳俊　李靈芳

摘要摘要：針對傳統(tǒng)協(xié)同過濾算法中存在的數(shù)據(jù)稀疏和用戶興趣變化問題，提出一種改進的協(xié)同過濾推薦算法（IPTDCF）。在用戶相似度計算中融入評分交集項目占比因子，針對用戶興趣變化問題在評分預(yù)測計算中融入時間衰減函數(shù)，提高推薦算法的準確性。仿真實驗表明，改進后的算法在推薦準確度上優(yōu)于傳統(tǒng)算法。

關(guān)鍵詞關(guān)鍵詞：協(xié)同過濾；IPTDCF；交集占比；時間衰減

DOIDOI：10.11907/rjdk.171066

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）005002403

0引言

推薦系統(tǒng)近年來得到了廣泛應(yīng)用，但也面臨很多問題，如用戶興趣變化、數(shù)據(jù)稀疏性問題等。傳統(tǒng)推薦算法在計算用戶相似度中時的參考集合由于只選用兩用戶共同評分的項目，而忽略了兩用戶均未評分和單一用戶評分的項目，這樣求得的用戶相似度只能片面反映用戶興趣，且沒有考慮用戶興趣變化問題。早期研究在用戶興趣變化方面有所涉及，比如張磊[1]提出了基于遺忘曲線規(guī)律進行時間衰減，得到有效評分矩陣再進行推薦算法；孫智聰[2]提出了一種基于記憶激活理論的協(xié)同過濾算法，給出重復(fù)學習后的興趣最大值計算方法；胡偉健等[3]提出了一種改進的歐式距離相似度度量方法和時間信息模擬用戶興趣變化的方法等。雖然上述算法考慮了用戶興趣變化，但在推薦準確性上仍有優(yōu)化空間。

本文引入評分交集項目占比因子優(yōu)化用戶相似度計算方法，引入時間衰減函數(shù)解決用戶興趣變化問題，提出改進算法，提高推薦算法的準確性。

1改進算法描述

UBCF算法首先計算用戶間相似度，主要方法有皮爾遜相關(guān)系數(shù)相似度計算方法、歐氏距離相似度計算方法、余弦相似度計算方法等。其中，皮爾遜相關(guān)系數(shù)相似度計算方法如下：

1.1改進的項目占比因子

項目評分是用戶興趣的直接反映，用戶可以有多種興趣。實際中，兩位用戶可能僅在個別興趣愛好上是相同的，反映在評分上為兩位用戶的評分項目交集遠小于各自評分項目數(shù)。如圖1所示，圖中項目交集I是傳統(tǒng)用戶相似度計算方法的取值范圍，項目交集中可能是當前熱門項目，也可能是兩用戶共同的興趣愛好。以MovieLens中數(shù)據(jù)量為100k大小的數(shù)據(jù)集為例，用戶181對435個項目進行了評分，用戶600對89個項目進行了評分，而兩用戶共同評分的項目僅有1個；用戶181對435個項目進行了評分，用戶766對175個項目進行了評分，而兩用戶共同評分的項目僅有1個。另外，也有可能評分項目較多的用戶覆蓋了評分較少用戶的幾乎所有項目，如圖2所示。同樣以上述數(shù)據(jù)集為例，用戶13對636個項目進行了評分，用戶814對35個項目進行了評分，并且這35個項目恰好也被用戶13評價過；用戶655對685個項目進行了評分，用戶111對24個項目進行了評分，并且這24個項目恰好也被用戶655評價過。顯然，這兩種情況下僅考慮用戶評分項目交集而忽略大部分非交集評分項目，在衡量用戶興趣時是片面的，不能準確得出用戶興趣。因此，在用戶相似度計算時考慮引入交集項目在用戶所有評分項目中的占比，對皮爾遜相關(guān)系數(shù)計算公式進行改進，改進如公式（3）所示。

其中，a表示一個很小的常量，其作用是避免出現(xiàn)分母為0的情況。prop（u，v）為項目占比因子，表示用戶u和用戶v共同評分項目數(shù)在各自評分項目數(shù)之和中所占的比例，如公式（4）所示，取值范圍[0，1]，兩用戶項目交集數(shù)越多，其值越大，對相似度的削減力度越小，相應(yīng)的sim值越大，表示兩者越相似。當兩用戶評分項目完全相同時prop（u，v）值為1，表示兩用戶所有已評分項目均參與到用戶相似度計算中，當兩用戶評分項目沒有交集時prop（u，v）值為0。

prop（u，v）=2×num（I（u）∩I（v））num（I（u））+num（I（v））（4）

其中，I（u）表示用戶u評分的項目，I（u）∩I（v）表示用戶u和用戶v共同評分的項目交集，num（I（u））表示用戶u評分項目個數(shù)，num（I（u）∩I（v））表示共同評分項目交集的個數(shù)。

1.2改進的時間衰減函數(shù)

項目評分是用戶對項目在當前時間喜好程度的直觀體現(xiàn)，而人腦對事物的記憶符合艾賓浩斯遺忘規(guī)律，即新生事物在大腦中的遺忘速度遵循先快后慢，最終趨于穩(wěn)定的變化規(guī)律。用戶對項目的喜好程度也會隨著這樣的記憶規(guī)律而發(fā)生變化，在傳統(tǒng)預(yù)測評分中并沒有體現(xiàn)出這一變化，由此在預(yù)測評分方法中增加時間衰減函數(shù)，當預(yù)測評分和近鄰用戶對該項目評分時間差越小，近鄰用戶實際評分對預(yù)測評分的影響越大，衰減越弱，改進如公式（5）所示。

pred（u，i）=ru+∑v∈Psim（u，v）×（rvi-rv）×f（tui，tvi）∑v∈Psim（u，v）（5）

其中，集合P表示用戶u的近鄰用戶集合中對項目i進行評分的用戶集合，tui表示用戶u對項目i的評分時間，在這里為時間戳形式。f為遺忘記憶保留率函數(shù)，其公式如下（6）所示，為單調(diào)遞減函數(shù)，分子為常量，評分時間間隔越大時，（t1-t2）越大，分母越大，記憶保持率越小，懲罰力度越大，評分的有效性越低，在預(yù)測評分中的貢獻度就要越低，模擬了用戶興趣變化的過程。計算如下：

f（t1，t2）=ec|t0+t1-t2|b（6）

其中，e為自然對數(shù)，c、b、t0為常量系數(shù)，實驗發(fā)現(xiàn)，t0取1e-6、c取0.4且b取0.04時效果最佳。

2實驗過程及結(jié)果分析

2.1實驗數(shù)據(jù)集介紹

本實驗所采用的數(shù)據(jù)集來自Movielens網(wǎng)站，包括6 040位用戶、3 900部電影、以及用戶對電影評分的1 000 209條數(shù)據(jù)記錄。其中，每位用戶至少對其中20部電影進行過評分，評分采用五分整數(shù)制，評分越高代表用戶越喜歡該部電影。

2.2實驗結(jié)果度量的標準

實驗結(jié)果的準確性采用平均絕對誤差（MAE）來度量。MAE通過比較用戶預(yù)測評分和用戶實際評分間的偏差來度量預(yù)測評分的準確度，其值越小說明推薦質(zhì)量越好。度量標準如式（7）。

MAE=∑ni=1|Δpi|n（7）

其中|Δpi|表示用戶對項目i的預(yù)測評分和實際評分的差值的絕對值，R（u）為用戶u的推薦列表，T（u）位測試集中用戶u的真實行為記錄集。

2.3實驗流程

為更好說明結(jié)果，選取UBCF算法、文獻[1]ForgetBCF算法和本文提出的IPTDCF算法，對比MAE值的大小及變化趨勢。UBCF和IPTDCF的實驗流程（見圖3）如下：

Input：用戶集合U，項目集合I，用戶評分記錄集合Info，最近鄰居數(shù)k；

Output： 預(yù)測評分矩陣Pred（U，I）以及MAE值。

Step 1： 將Info按照80%-20%的數(shù)量比，隨機分成兩部分，80%部分記錄作為訓(xùn)練集Base，20%部分作為測試集Test。

Step 2 ： 提取出數(shù)據(jù)集Base和Test中的用戶、項目評分、評分時間信息，組成用戶-項目評分矩陣R（U，I）、R（U，I）和相應(yīng)的用戶-項目評分時間矩陣T（U，I）、T（U，I）。

Step 3： 分別根據(jù)公式（1）和（3）進行對比實驗，對訓(xùn)練集中每個用戶uU，在改進公式（3）中求出用戶單獨評分項目數(shù)和兩用戶共同評分項目數(shù)，并根據(jù)公式（5）計算出項目占比因子，求出用戶間相似度similarity（u，v），并保存在相似度矩陣Sim（U，U）中。

Step 4： 在Sim（U，U）中，對每個用戶uU，選取出與u相似度最高的k位用戶，組成最近鄰集合neighborhood（u，k），并保存在最近鄰矩陣Neighbor（U，k）中。

Step 5： 根據(jù)訓(xùn)練集中得到的最近鄰矩陣Neighbor（U，k），對測試集中用戶項目評分進行預(yù)測，分別根據(jù)公式（2）和（5）進行對比實驗，在改進公式（6）中根據(jù)評分時間間隔進行時間衰減，根據(jù)公式（7）求出記憶保留率，再計算出R′（U，I）中每個用戶已評分項目的預(yù)測評分，并保存到預(yù)測評分矩陣Pred（U，I）中。

Step 6：根據(jù)公式（7），分別求出對比實驗中兩組MAE值，比較推薦算法的準確性，返回Pred（U，I），實驗完成。

2.4實驗結(jié)果分析

實驗均采用皮爾遜相關(guān)系數(shù)來計算相似度，觀察不同鄰居數(shù)時MAE值的變化，結(jié)果如表1和圖4所示。

結(jié)果顯示，不同算法和不同近鄰數(shù)得到的MAE值不同，相同近鄰數(shù)時，UBCF的MAE值最大，IPTDCF的MAE值最小，表明IPTDCF的推薦準確性更高。UBCF和ForgetBCF呈遞減變化，IPTDCF先遞減后遞增，UBCF接近線性變化，F(xiàn)orget和IPTDCF遞減速度先快后慢，最終趨于平穩(wěn)，這是由于時間衰減函數(shù)使得MAE值變化符合遺忘曲線規(guī)律；IPTDCF在近鄰數(shù)為80時達到最小值，后期有微弱遞增趨勢，這是由于項目占比因子的削弱作用使得原本較高的用戶相似度依然高，而原本較低的用戶相似度變得更低，增加近鄰相當于增加了更過低相似度的近鄰，因而鄰居數(shù)的增多反而削弱了改進效果。綜上所述，由IPTDCF計算出的MAE值要小于UBCF算法和ForgetBCF算法，可以發(fā)現(xiàn)IPTDCF在推薦的準確性上明顯優(yōu)于傳統(tǒng)UBCF算法和ForgetBCF算法。

3結(jié)語

本文針對評分數(shù)據(jù)稀疏或用戶評分時間不同的應(yīng)用場景提出了一種改進型協(xié)同過濾推薦算法IPTDCF。IPTDCF算法首先在計算用戶相似度時加入共同評分項目交集占各自所有評分項目的比例因子，考慮兩用戶評分項目的非交集部分；其次在預(yù)測項目評分時引入時間衰減函數(shù)，結(jié)合遺忘曲線規(guī)律，對評分預(yù)測方法進行修正。兩組實驗通過MAE值的比較，得出IPTDCF算法在推薦準確性方面明顯優(yōu)于傳統(tǒng)推薦算法的結(jié)論。在評分數(shù)據(jù)稀疏或用戶評分時間不同的情況下，更適合采用改進算法IPTDCF。

參考文獻參考文獻：

[1]張磊. 基于遺忘曲線的推薦算法研究[D].合肥：安徽理工大學，2014.

[2]孫智聰.基于時間上下文和屬性的個性化推薦研究[D].重慶：重慶大學，2015.

[3]胡偉健，滕飛，李靈芳，王歡.適應(yīng)用戶興趣變化的改進型協(xié)同過濾算法[J].計算機應(yīng)用.2016，36（8）：20872091.

[4]孫光輝.基于時間效應(yīng)和用戶興趣變化的改進推薦算法研究[D].北京：北京郵電大學，2014.

[5]孫光福，吳樂，劉淇，朱琛，陳恩紅.基于時序行為的協(xié)同過濾推薦算法[J].軟件學報，2013（11）： 27212733.

[6]黃創(chuàng)光，印鑒，汪靜，劉玉葆，王甲海.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學報，2010，33（8）：13691377.

[7]孟祥武，劉樹棟，張玉潔，胡勛.社會化推薦系統(tǒng)研究[J].軟件學報，2015（6）：13561372.

[8]RICCI F，ROKACH L， SHAPIRA B，et al.Recommender systems handbook[M].Springer，2011.

責任編輯（責任編輯：陳福時）