吳崢　陳俊　李靈芳

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

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

DOIDOI：10.11907/rjdk.171066

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）005002403

0引言

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

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

1改進(jìn)算法描述

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

1.1改進(jìn)的項(xiàng)目占比因子

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

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

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

其中，I（u）表示用戶(hù)u評(píng)分的項(xiàng)目，I（u）∩I（v）表示用戶(hù)u和用戶(hù)v共同評(píng)分的項(xiàng)目交集，num（I（u））表示用戶(hù)u評(píng)分項(xiàng)目個(gè)數(shù)，num（I（u）∩I（v））表示共同評(píng)分項(xiàng)目交集的個(gè)數(shù)。

1.2改進(jìn)的時(shí)間衰減函數(shù)

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

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

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

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

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

2實(shí)驗(yàn)過(guò)程及結(jié)果分析

2.1實(shí)驗(yàn)數(shù)據(jù)集介紹

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

2.2實(shí)驗(yàn)結(jié)果度量的標(biāo)準(zhǔn)

實(shí)驗(yàn)結(jié)果的準(zhǔn)確性采用平均絕對(duì)誤差（MAE）來(lái)度量。MAE通過(guò)比較用戶(hù)預(yù)測(cè)評(píng)分和用戶(hù)實(shí)際評(píng)分間的偏差來(lái)度量預(yù)測(cè)評(píng)分的準(zhǔn)確度，其值越小說(shuō)明推薦質(zhì)量越好。度量標(biāo)準(zhǔn)如式（7）。

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

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

2.3實(shí)驗(yàn)流程

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

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

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

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

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

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

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

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

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

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

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

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

3結(jié)語(yǔ)

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

參考文獻(xiàn)參考文獻(xiàn)：

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

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

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

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

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

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

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

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

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）