一種改進(jìn)的混合推薦算法

宋文君， 郭 強(qiáng)， 劉建國

（上海理工大學(xué) 管理學(xué)院 復(fù)雜科學(xué)研究中心，上海 200093）

互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展使得信息超載問題日益嚴(yán)重［1］.個性化推薦系統(tǒng)利用用戶的歷史行為來預(yù)測其潛在的需求，能夠有效地解決信息超載問題［2－3］.現(xiàn) 有 的 推 薦 算 法 包 括 協(xié) 同 過 濾 算 法（collaborative filtering）［4－5］、基于內(nèi)容的推薦算法（content－based algorithm）［6］、基于網(wǎng)絡(luò)結(jié) 構(gòu)的推 薦算法（network－based algorithm）等［7－13］.其中，基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法就是將熱傳導(dǎo)（heat conduction）［7－9］、物質(zhì)擴(kuò)散（mass diffusion）［10－12］等原理應(yīng)用到個性化推薦算法的研究中，已經(jīng)取得了很好的研究成果.Zhang等［7］利用用戶對產(chǎn)品的打分信息，實(shí)現(xiàn)了熱傳導(dǎo)的推薦算法.Zhou等［10］利用用戶－產(chǎn)品二部分網(wǎng)絡(luò)提出了一種基于物質(zhì)擴(kuò)散的推薦算法.進(jìn)一步，Zhou等［13］基于物質(zhì)擴(kuò)散與熱傳導(dǎo)原理提出了一種混合推薦算法（HHM）.

HHM 算法雖然能夠同時提高算法的準(zhǔn)確性與多樣性，但是，必須采用全部的用戶信息［14］.然而用戶的早期行為不能很好地反映其目前的興趣偏好，也就是說應(yīng)該考慮時間信息對于推薦效果的影響.近幾年來，許多學(xué)者嘗試將時間因素融入到算法中來提升推薦效果.例如，Liu等［15］提出了一種基于時間因素的推薦算法.另外，Zhang等［16］將基于時間和拓?fù)浣Y(jié)構(gòu)這兩種方法混合起來，提出了一種用來抽取信息骨架的方法.雖然這一方法只需要處理部分信息，但是，卻缺乏時間窗口對推薦效果影響的研究，這對于降低計算復(fù)雜性至關(guān)重要.本文提出了一種基于有限時間窗口的改進(jìn)混合推薦算法.首先采用標(biāo)準(zhǔn)數(shù)據(jù)集Netflix，通過逐漸增大時間窗口的方式生成一系列訓(xùn)練集，然后將每一個訓(xùn)練集作為已知的數(shù)據(jù)來預(yù)測用戶的興趣偏好，最后利用測試集來檢驗推薦算法的效果.實(shí)驗結(jié)果表明，采用部分用戶近期數(shù)據(jù)能夠同時提升推薦的準(zhǔn)確性和多樣性，而且新改進(jìn)的算法適用于不同活躍程度的用戶.表明本文的方法可以極大地降低計算復(fù)雜性，非常具有實(shí)踐價值.

1 模型與方法

1.1 基于二部分網(wǎng)絡(luò)的混合推薦算法

用戶－產(chǎn)品二部分網(wǎng)絡(luò)包括一組由集合U＝｛u1，u2，…，un｝表示的用戶節(jié)點(diǎn)，一組由集合O＝｛o1，o2，…，om｝表示的產(chǎn)品節(jié)點(diǎn)，以及連接這兩組節(jié)點(diǎn)的連邊，由集合E＝｛e1，e2，…，ep｝表示.其中，如果用戶uj選擇過產(chǎn)品oi，那么就在uj和oi之間連接一條邊aij＝1；否則，aij＝0.

標(biāo)準(zhǔn)的熱傳導(dǎo)算法最初由Zhang等［7］提出來.假設(shè)每個產(chǎn)品都具有一個初始資源，并且它可以在用戶－產(chǎn)品二部分網(wǎng)絡(luò)上傳遞，使得所有產(chǎn)品都會獲得一個最終的資源.這一資源傳遞的過程可以表示為

式中，W 代表資源轉(zhuǎn)移矩陣；f 表示產(chǎn)品的初始資源；f ′則表示最終資源.

熱傳導(dǎo)算法［7］在推薦列表多樣性上具有優(yōu)勢，但是，因為對冷門產(chǎn)品分配過多的資源而導(dǎo)致準(zhǔn)確性很差.物質(zhì)擴(kuò)散算法［10］卻因為更加關(guān)注流行產(chǎn)品，可以表現(xiàn)出很高的推薦準(zhǔn)確性.為了綜合上述兩種方法的優(yōu)勢，Zhou等［13］提出了一種混合推薦算法（HHM）可以同時提高推薦結(jié)果的準(zhǔn)確性和多樣性.資源轉(zhuǎn)移矩陣可以表示為

式中，koα，koβ和kuj分別代表產(chǎn)品oα，oβ以及用戶uj的度；aαj，aβj分別代表用戶uj與產(chǎn)品oα，oβ的連邊；λ 為混合參數(shù)，λ＝0，代表標(biāo)準(zhǔn)的熱傳導(dǎo)算法，而λ＝1，則表示物質(zhì)擴(kuò)散算法.

當(dāng)混合參數(shù)λ 調(diào)節(jié)到一個最優(yōu)值時，該算法在準(zhǔn)確性和多樣性兩方面都可以得到一個更好的推薦結(jié)果.

1.2 改進(jìn)的混合推薦算法

本文基于用戶的近期行為能夠更好地反映其潛在的興趣偏好的思想，提出了一種基于有限時間窗口的改進(jìn)混合推薦算法.首先，通過采用標(biāo)準(zhǔn)的HHM 算法，可以得到一個最優(yōu)的混合參數(shù)使得推薦結(jié)果的準(zhǔn)確率最高，記為λopt.然后，將最近發(fā)生的前10%的記錄作為測試集，另外按照下面不斷地擴(kuò)大時間窗口的方法，劃分出一系列訓(xùn)練集.在剩下的用戶記錄中最大的時間信息記為t0，假設(shè)在時間標(biāo)T∈［t0－ηΔt，t0］這一范圍內(nèi)的記錄就構(gòu)成了第η個訓(xùn)練集，其中，Δt 代表時間間隔，η 則表示訓(xùn)練集的編號.η 的最小值為1，代表第一個訓(xùn)練集，它包含從時間標(biāo)t0向前倒推了一個單位時間間隔內(nèi)的全部記錄.η 的上界是原始訓(xùn)練集的生命周期與Δt的比值.需要注意的是，隨著η 值的不斷增大，訓(xùn)練集中所包含的數(shù)據(jù)量也在不斷增大，但是，測試集卻保持不變.另外，將每一組訓(xùn)練集作為已知的數(shù)據(jù)，來預(yù)測用戶對沒有選擇過的產(chǎn)品的喜好程度.這里采用改進(jìn)的混合推薦算法，其資源轉(zhuǎn)移矩陣表示為

最后，采用準(zhǔn)確率（precision）、召回率（recall）和平均漢明距離（average Hamming distance）這3種指標(biāo)來衡量新算法的推薦效果.

1.3 衡量指標(biāo)

準(zhǔn)確率P［17］：表示用戶對系統(tǒng)所推薦的產(chǎn)品喜歡的概率，也就是系統(tǒng)推薦的產(chǎn)品中用戶喜歡的產(chǎn)品所占的比例，即

式中，L 代表推薦列表的長度；hi代表同時出現(xiàn)在用戶ui的測試集和其推薦列表中的產(chǎn)品數(shù)目.

通常來說，當(dāng)推薦列表長度L 給定的時候，準(zhǔn)確率越高，表明推薦結(jié)果越準(zhǔn)確.

召回率R［17］：表示用戶喜歡的產(chǎn)品被推薦的概率，即

式中，nip則代表測試集中用戶ui喜歡的產(chǎn)品數(shù)目.

同樣地，召回率越高，說明推薦效果越好.

平均漢明距離S［17］：推薦結(jié)果的多樣性可以采用平均漢明距離來衡量，具體表示為

式中，Qij（L）則代表用戶ui和uj的推薦列表中相同產(chǎn)品的數(shù)目.

最大值S＝1，表明兩個用戶的推薦列表沒有重復(fù)的產(chǎn)品，也就說明推薦系統(tǒng)的多樣性最高；反之，如果S＝0，則表示兩個用戶的推薦列表完全一致.

2 實(shí)證結(jié)果分析

2.1 實(shí)驗數(shù)據(jù)

采用標(biāo)準(zhǔn)數(shù)據(jù)集Netflix來檢驗新算法的推薦效果.Netflix的數(shù)據(jù)包括8 609個用戶對5 081部電影的打分情況，是netflix.com 網(wǎng)站從2001年2月至5月期間收集得到的.根據(jù)本文提出的方法，最近發(fā)生的41 924條記錄就構(gòu)成了測試集.假設(shè)劃分訓(xùn)練集的時間間隔Δt 為2天，那么，就可以得到45個訓(xùn)練集.經(jīng)過實(shí)驗，可以得到最優(yōu)的混合參數(shù)λopt＝0.51，如圖1所示.

2.2 實(shí)驗結(jié)果

圖1 混合參數(shù)與準(zhǔn)確率的關(guān)系Fig.1 Relation between hybridization parameter and precision

圖2 推薦效果隨訓(xùn)練集編號增大的變化情況Fig.2 Relation between algorithmic performance and number of training set

利用準(zhǔn)確率和召回率這兩個指標(biāo)來衡量推薦算法的準(zhǔn)確性，而平均漢明距離則用于衡量推薦列表的多樣性.圖2表示這3種指標(biāo)隨著η 增大的變化情況.可以看出準(zhǔn)確率和召回率基本上都呈現(xiàn)出一種先上升后下降的趨勢，而多樣性基本上呈下降趨勢，也就是說，只采用部分近期數(shù)據(jù)就可以得到一個更準(zhǔn)確且多樣的推薦結(jié)果.從圖2中可以看出，只需要考慮14／45≈31.11%的用戶近期記錄，所得到的推薦準(zhǔn)確度可以平均提升4.22%，而多樣性可以提升13.74%.由此可見，為了生成一個更好的推薦結(jié)果而采用用戶－產(chǎn)品二部分網(wǎng)絡(luò)中的全部數(shù)據(jù)是沒有必要的.這一現(xiàn)象產(chǎn)生的原因可能在于用戶的興趣偏好是隨時間動態(tài)變化的，考慮用戶的早期行為會影響推薦結(jié)果的表現(xiàn)性.由于最初訓(xùn)練集中的數(shù)據(jù)量太少，不能準(zhǔn)確地反映出用戶的興趣偏好.然而，當(dāng)時間窗口不斷增大的時候，已知的數(shù)據(jù)量越多，反而會干擾推薦的效果，也就是說，只考慮部分用戶近期數(shù)據(jù)反而能夠得到一個更好的推薦結(jié)果.

2.3 不同活躍程度的用戶準(zhǔn)確性

用戶的活躍程度可以用他們的度來衡量.數(shù)據(jù)集Netflix 中用戶的度分布情況近似呈現(xiàn)冪率形式［2］，也就是說，非?；钴S的用戶數(shù)量很少，而絕大部分都是度小的用戶.為了研究本文提出的算法對不同活躍程度的用戶是否都適用，按照用戶的度ku將他們分為5 類，分別為1～10，11～20，21～50，51～100和超過100.圖3（見下頁）表示上述這5類用戶的準(zhǔn)確率隨著η 增大的變化情況.從實(shí)驗結(jié)果可以看出，對于不同活躍程度的用戶來說，他們的準(zhǔn)確率隨著η 的增大基本上呈現(xiàn)出一種先上升后下降的趨勢，也就是說，對于不同活躍程度的用戶來說，本文提出的改進(jìn)混合推薦算法都能夠提高算法的準(zhǔn)確性.特別是對于新用戶來說，這里假設(shè)度不超過10的用戶為新用戶，只需要考慮31.11%的用戶近期記錄，準(zhǔn)確率就可以提高11%.因此，從提高推薦準(zhǔn)確性的角度來看，改進(jìn)的混合推薦算法能夠適用于不同活躍程度的用戶.

圖3 不同活躍程度用戶準(zhǔn)確率的變化情況Fig.3 Precision on users with different activeness

3 總結(jié)與展望

基于熱傳導(dǎo)和物質(zhì)擴(kuò)散原理的混合推薦算法［13］能夠同時提高推薦列表的準(zhǔn)確性和多樣性.經(jīng)典的方法是采用用戶－產(chǎn)品二部分網(wǎng)絡(luò)中的全部數(shù)據(jù)，卻忽略了時間窗口對于推薦算法效果的影響.因此，本文著重研究了時間窗口對于混合推薦算法的影響，并且提出了一種基于有限時間窗口的改進(jìn)混合推薦算法，能夠同時提高推薦結(jié)果的準(zhǔn)確性和多樣性.首先采用標(biāo)準(zhǔn)數(shù)據(jù)集Netflix，通過逐漸擴(kuò)大時間窗口的方法生成一系列訓(xùn)練集，然后將每個訓(xùn)練集作為已知的數(shù)據(jù)來預(yù)測用戶的興趣偏好，最后利用測試集來檢驗推薦算法的效果.在Netflix數(shù)據(jù)集上的實(shí)驗結(jié)果表明，只采用31.11%的近期數(shù)據(jù)，所得到的推薦結(jié)果準(zhǔn)確性可以平均提升4.22%，而多樣性可以提升13.74%.另外還發(fā)現(xiàn)新提出的算法適用于不同活躍程度的用戶.本文的工作在理論和實(shí)踐上都具有一定的價值.在理論上，本文的方法對于深入理解時間窗口對混合推薦算法的影響很有幫助；在實(shí)踐中，能夠降低大規(guī)模數(shù)據(jù)所引發(fā)的計算復(fù)雜性問題，并且減少數(shù)據(jù)存儲空間.然而，對于不同的數(shù)據(jù)集如何找到合適的時間窗口，以及如何建立一個理論模型來解釋為何采用部分近期數(shù)據(jù)所得到的推薦效果更好，是作者未來的研究方向.

［1］劉建國，周濤，汪秉宏.個性化推薦系統(tǒng)的研究進(jìn)展［J］.自然科學(xué)進(jìn)展，2009，19（1）：1－15.

［2］Lv L Y，Medo M，Yeung C H，et al.Recommender systems［J］.Physics Reports，2012，519（1）：1－49.

［3］陳華，李仁發(fā)，劉鈺峰，等.個性化搜索引擎推薦算法研究［J］.計算機(jī)應(yīng)用研究，2010，27（1）：48－50.

［4］石珂瑞，劉建國.二階有向相似性對協(xié)同過濾算法的影響［J］.上海理工大學(xué)學(xué)報，2014，36（1）：31－33.

［5］李霞，李守偉.面向個性化推薦系統(tǒng)的二分網(wǎng)絡(luò)協(xié)同過濾算法研究［J］.計算機(jī)應(yīng)用研究，2013，30（7）：1946－1949.

［6］Ricci F，Nguyen Q N.Acquiring and revising preferences in a critique－based mobile recommender system［J］.IEEE，Intelligent Systems，2007，22（3）：22－29.

［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］Guo Q，Leng R，Shi K，et al.Heat conduction information filtering via local information of bipartite networks［J］.The European Physical Journal B，2012，85（8）：1－8.

［9］Liu J G，Zhou T，Guo Q.Information filtering via biased heat conduction［J］.Physical Review E，2011，84（3）：037101.

［10］Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation［J］.Physical Review E，2007，76（4）：046115.

［11］Liu J G，Zhou T，Wang B H，et al.Effects of user’s tastes on personalized recommendation ［J］.International Journal of Modern Physics C，2009，20（12）：1925－1932.

［12］張子柯.社會化標(biāo)簽系統(tǒng)的結(jié)構(gòu)、演化和功能［J］.上海理工大學(xué)學(xué)報，2011，33（5）：444－451.

［13］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.

［14］Zeng A，Yeung C H，Shang M S，et al.The reinforcing influence of recommendations on global diversification［J］.Europhysics Letters，2012，97（1）：18005.

［15］Liu J，Deng G S.Link prediction in a user－object network based on time－weighted resource allocation［J］.Physica A：Statistical Mechanics and its Applications，2009，388（17）：3643－3650.

［16］Zhang Q M，Zeng A，Shang M S.Extracting the information backbone in online system［J］.PloS One，2013，8（5）：e62624.

［17］朱郁筱，呂琳媛.推薦系統(tǒng)評價指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報，2012，41（2）：163－175.