劉曉光，謝曉堯

(1.貴州大學 計算機科學與技術學院，貴州 貴陽550000；2.貴州師范大學 信息與計算科學重點實驗室，貴州 貴陽 550000)

?

一種結合遺忘機制與加權二部圖的推薦算法

劉曉光1，2，謝曉堯2

(1.貴州大學 計算機科學與技術學院，貴州 貴陽550000；2.貴州師范大學 信息與計算科學重點實驗室，貴州 貴陽 550000)

為了解決因用戶興趣漂移而導致推薦質量下降的問題，本文引入了用戶對產品的遺忘因子。通過分析用戶的瀏覽記錄和打分情況，建立用戶的動態(tài)興趣模型；并計算用戶對產品的遺忘因子，利用遺忘因子作為加權二部圖的權值，通過二部圖的資源分配方法產生用戶的推薦列表。在數(shù)據(jù)集MovieLens上的實驗表明：該算法能有效地處理用戶興趣漂移的問題，提高推薦列表的推薦質量。

興趣漂移；遺忘機制；加權二部圖；資源分配；推薦算法

0 引言

隨著現(xiàn)代電子商務和網(wǎng)絡技術的快速發(fā)展，互聯(lián)網(wǎng)的規(guī)模不斷擴大，信息不斷膨脹，世界上的信息處于大爆炸的狀態(tài)，用戶所面對的信息數(shù)量大、質量差、信息價值低，給用戶帶來了信息超載的問題。為了解決信息超載問題，推薦系統(tǒng)應運而生[1]。

隨著Web2.0技術趨于成熟，推薦系統(tǒng)在網(wǎng)絡上的應用也迅速發(fā)展，如TaoBao、Amazon、Youtube等網(wǎng)站，它們都擁有自己的推薦系統(tǒng)。在實際的應用中，用戶的數(shù)量龐大，產品資源的數(shù)量巨大，用戶很少能一次就找到自己想要的信息。設計一個準確高效的推薦系統(tǒng)不僅可以發(fā)現(xiàn)用戶潛在的興趣對象，還可以針對不同用戶提供個性化的服務[2]，以幫助用戶更好地獲取想要的信息。

2012年，文獻[3]提出了加權網(wǎng)絡推斷算法(WNBI)，即加權二部圖推薦算法，該推薦算法解決了高評分值的產品不能優(yōu)先推薦的問題，提高了推薦質量。但是在現(xiàn)實生活中，隨著新的產品(選擇)的出現(xiàn)，產品的感知和受歡迎程度不斷發(fā)生變化，同樣，用戶的傾向也是不斷變化的，這種用戶偏好隨著時間變化的情況，稱為用戶“興趣漂移”問題[4]。為了降低“興趣漂移”問題對推薦質量的影響，研究人員做了大量的工作，如：文獻[5]提出的時間加權不確定近鄰協(xié)同過濾算法，文獻[6]提出的融合時間綜合影響的輪盤賭游走個性化推薦算法等。本文通過遺忘機制引入了遺忘因子，利用遺忘因子作為加權二部圖的權值，提出了一種改進的加權網(wǎng)絡推斷算法(FWNBI)，即結合遺忘機制與加權二部圖的推薦算法。

1 遺忘機制

對于用戶的“興趣漂移”問題，目前有各種不同的遺忘機制來處理。2008年，文獻[7]提出了一種遺忘機制，引入了一種指數(shù)的遺忘函數(shù)F(t)來量化用戶興趣的衰減程度，函數(shù)定義為：

(1)

其中：遺忘函數(shù)F(t)為當前時間用戶的興趣衰減到的程度，即當前時間用戶興趣的保留程度；t為用戶產生推薦列表時的當前時間；est為用戶選擇某產品的時間；hl為用戶遺忘的速率，hl越大表示遺忘的速度越慢，hl越小表示遺忘的速度越快[7]。

1885年，德國心理學家艾賓浩斯研究發(fā)現(xiàn)：人們在學習之后立即開始遺忘，而且遺忘的速度并不是均勻的，最初遺忘速度很快，以后逐漸緩慢[8]。遺忘速度曲線如圖1所示。

圖1 艾賓浩斯遺忘曲線

根據(jù)艾賓浩斯理論，將遺忘速率hl定義為：用戶初次選擇產品的時間距離系統(tǒng)為用戶產生推薦列表時的時間間隔。對于某一用戶，假設初次選擇產品的時間為t1，選擇某一產品P的時間為t2，系統(tǒng)為該用戶產生推薦列表的時間為t，那么該用戶對于產品P的興趣保留程度為F(t)=e-ln 2*(t-t2)/(t-t1);隨著t的推移，hl=t-t1的值越大，即用戶對于產品P的遺忘速度越慢。

2 加權二部圖推薦算法

近年來復雜網(wǎng)絡的研究方興未艾，越來越多關于網(wǎng)絡的研究成果被發(fā)掘并應用。二部圖是一種特殊的網(wǎng)絡，它僅包含兩類節(jié)點：一類節(jié)點是活動的用戶節(jié)點，例如需要獲得推薦的用戶等；另一類節(jié)點是項目節(jié)點，例如要為用戶推薦的產品等[3]，它僅允許不同類的節(jié)點間相連。

2007年，文獻[9]提出了二部圖推薦算法，該推薦算法把用戶和產品分別抽象為不同的節(jié)點，作為二部圖的節(jié)點，把用戶與產品之間的選擇關系抽象為兩類節(jié)點之間的邊(如果用戶i選擇了產品j，那么用戶i節(jié)點與產品j節(jié)點之間連接一條邊aji=1，否則aji=0，其中i=1,2,…，m;j=1,2,…，n)。該算法僅考慮用戶節(jié)點與產品節(jié)點之間的連接關系，而不考慮用戶和產品的內容特征，所有算法利用的信息都藏在用戶節(jié)點和產品節(jié)點及它們之間的邊所構成的二部圖中。

該算法假設所有的產品節(jié)點上都具有某種可再分配的資源，該資源可以通過用戶節(jié)點與產品節(jié)點之間的邊轉移到其他的產品節(jié)點上，擁有資源的產品會把更多的資源轉移給其更加青睞的產品上[10]。通過這種資源分配的方法，把用戶沒有選擇過的產品并且擁有更多資源的產品按照擁有資源的數(shù)量從大到小排序，將排名靠前的產品推薦給該用戶，形成推薦列表。

但是二部圖推薦算法中的二部圖是無權值的，產品的資源平均分配給選擇過該產品的用戶，用戶所得到的資源再平均分配給該用戶所選擇過的產品。在這個資源分配過程中所有產品的重要性相同，對用戶的推薦貢獻是相同的；但在實際應用中，用戶喜歡的產品對用戶的推薦貢獻要高于用戶不太喜歡的產品對于用戶的推薦貢獻。顯然，平均分配資源的方式并不合理。文獻[3]提出了加權二部圖推薦算法，該推薦算法考慮用戶與產品之間的邊的權重，根據(jù)邊的權重來進行資源的分配，如產品j將資源按邊aji的權值與該產品邊權之和的比分配給用戶i，同樣，用戶i再將所獲得的資源按邊aki的權值與該用戶邊權之和的比例分配給產品。

3 FWNBI推薦算法

無論是二部圖推薦算法還是加權二部圖推薦算法，它們只是單純的考慮用戶喜歡與不喜歡或用戶的喜歡程度，并沒有考慮用戶“興趣漂移”的問題。二部圖推薦算法把用戶選擇過的產品看做是同等重要，并沒有區(qū)分用戶對產品的喜歡程度(打分值wij)；而加權二部圖推薦算法雖然區(qū)分了用戶對產品的喜歡程度(打分值wij)，不同喜歡程度的產品的重要性不同，但并沒有考慮用戶的“興趣漂移”問題，這在一定程度上降低了推薦算法的推薦質量。

基于遺忘機制和加權二部圖的推薦算法(FWNBI)，在給用戶推薦時考慮了時間對用戶興趣的影響，通過遺忘機制引入了遺忘因子fij，用來量化當前時間t時用戶j對于產品i的興趣的保留程度，見式(2)。

(2)

其中：estij表示用戶j選擇產品i的時間；hlj=t-tj,t表示系統(tǒng)為用戶j產生推薦列表的當前時間，tj表示用戶j初次選擇產品的時間。

利用遺忘因子fij與當時用戶j對產品的打分值wij的乘積，kij來估計當前用戶j對于該產品i的喜歡程度，見式(3)。

kij=wijfij。

(3)

圖2 改進推薦算法資源轉移過程

將kij作為二部圖邊的權值，資源分配的過程如圖2所示。在圖2a中，3個產品的起始資源分別為x、y、z，邊的權值為kij。首先，資源從產品節(jié)點轉移到用戶節(jié)點，產品節(jié)點將擁有的資源按照用戶-產品邊權與該產品邊權之和的權重比，分配給每個與該產品節(jié)點相連的用戶節(jié)點上，分配結果見圖2b；其次，資源從用戶節(jié)點返回到產品節(jié)點上，用戶節(jié)點將所分得資源按照用戶-產品邊權與該用戶邊權之和的權重比，分配給與其相連的產品節(jié)點上，結果見圖2c。

由資源分配過程可知，任意產品j分配給產品i的資源權重Wij計算公式為：

(4)

(5)

其中：k(xj)表示與產品xj連接的所有用戶邊權之和；k(yl)表示與用戶yl連接的所有產品邊權之和；amn表示用戶n是否選擇過產品m；kmn表示用戶n對產品m的喜歡程度的估計值。

通過式(4)和式(5)可以得到系統(tǒng)的資源分配矩陣W。對于給定的一個目標用戶，將他選擇過的且打分值大于等于3分的產品上的初始資源設為1，沒有選擇過或打分值小于3分的產品上的初始資源設為 0。這樣得到一個n維的 0/1 矢量，代表針對該用戶的初始資源分配構型，顯然，這個初始構型表達了個性化信息，對于不同用戶是不一樣的。記這個矢量為f，通過上述過程得到的最終的資源分配矢量可以表示為：

f′=Wf，

(6)

其中：W為系統(tǒng)的資源分配矩陣；f為目標用戶的初始資源分配構型；f′為系統(tǒng)給目標用戶推薦的產品的矢量原始列表。

把矢量f′中用戶已經選擇過的產品所對應的值置為0，然后將矢量f′中的元素按值的大小進行排序，值越大就說明該用戶越喜歡其所對應的產品。排序靠前的值所對應的產品，可以推薦給目標用戶。

假設(U,P,W,T)表示用戶的行為，其中U表示用戶集合，P表示用戶U選擇過的產品集合，W表示用戶U給產品集合P的打分集合(1～5分)，T表示用戶U選擇產品P并給產品打分時的時間集合。用戶ui在時間tij時選擇產品pj并且給該產品的打分值為wij的一次行為可以表示為(ui，pj，wij，tij)。

FWNBI算法描述：

第1步：估算現(xiàn)在用戶對已選產品的打分情況。

輸入：用戶的瀏覽記錄和打分情況T；

輸出：輸出格式為(ui，pj，kij，0)的數(shù)組initial[ui][pj]，用戶ui選擇過的產品的邊的權值之和記為Ku[ui]，選擇過產品pj的用戶的邊的權值之和記為Km[pj]。

Foreach t in T

生成格式為(ui，pj，wij，tij)的數(shù)據(jù)集合A；

Endfor

Foreach a in A

根據(jù)式(2)生成格式為(ui，pj，wij，fij)的數(shù)據(jù)b；

根據(jù)式(3)將數(shù)據(jù)b轉換為格式為(ui，pj，kij，0)的數(shù)組initial[ui][pj]；

計算與用戶ui相連的邊的權值之和，記為Ku(ui)；

計算與產品pj相連的邊的權值之和，記為Km(pj)；

Endfor

第2步：計算資源轉移矩陣。

輸入：格式為(ui，pj，kij，0)的數(shù)據(jù)集H，集合Ku，集合Km；

輸出：資源轉移矩陣W。

Foreach h in H

根據(jù)式(4)和式(5)計算得到資源轉移矩陣W；

Endfor

第3步：為某個用戶計算得到推薦列表。

輸入：用戶的初始資源分配構型f，資源轉移矩陣W；

輸出：某個用戶的推薦列表R。

Begin

根據(jù)式(6)得到系統(tǒng)給用戶推薦的產品的推薦值矢量f1；

得到初始推薦列表R=f1-f，取值較大的所對應的產品形成最終推薦列表。

End

4 算法評價

4.1 數(shù)據(jù)集

采用開源的MovieLens數(shù)據(jù)集，數(shù)據(jù)集的規(guī)模如表1所示。

表1 數(shù)據(jù)集規(guī)模

從數(shù)據(jù)集中隨機抽取70%的數(shù)據(jù)并對該數(shù)據(jù)集按時間的先后進行劃分，其中，用戶較早選擇的80%的數(shù)據(jù)作為訓練集，較晚選擇的20%的數(shù)據(jù)作為測試集。重復上述過程10次，取10次評價結果的平均值作為該推薦算法的最終評價結果。

4.2 評價指標

在該推薦算法中，用戶具有明確的二分喜好(用戶對電影的打分值大于等于3表示喜歡，否則表示不喜歡)，本文采用特別適合于具有二分喜好的評價指標：分類準確度[10]。目前，最常用的分類準確度指標有準確率、召回率、綜合評價指標(F1指標)和曲線下面積(AUC)。該推薦算法對于推薦排序有一定的要求，本文還采用排序準確度評價指標，文獻[9]提出了用平均排序分度量推薦算法的排序準確度。本文采用準確率、召回率、F1指標和平均排序分對該推薦算法進行評價。

4.2.1 基于準確率、召回率的評價

準確率和召回率是推薦系統(tǒng)中常用的兩個評價指標。準確率也叫查準率，表示用戶喜歡的產品在系統(tǒng)推薦列表中所占的比例；召回率也叫查全率，表示一個用戶喜歡的商品被推薦的概率[11]。

表2 待預測的產品4種可能的狀態(tài)

對于用戶未選擇和打分的產品，往往有4種可能的狀態(tài)，如表2所示，其中K表示系統(tǒng)中產品的個數(shù)。

由表2可知系統(tǒng)整體的推薦準確率為：

(7)

系統(tǒng)整體的召回率為：

(8)

其中：U表示測試用戶的集合；M表示測試用戶的數(shù)量。

圖3為基于加權二部圖的推薦算法(WNBI)、基于遺忘機制和加權二部圖的推薦算法(FWNBI)在推薦長度分別為5個、10個、20個、30個、…、100個下的準確率和召回率折線圖。

圖3 算法的準確率和召回率折線

由圖3可知：FWNBI和WNBI在準確率和召回率上的差別不是很大，隨著推薦長度的增大，兩者的準確率和召回率曲線幾乎重合，在推薦長度為10～50個時，F(xiàn)WNBI的準確率優(yōu)于WNBI；并且在推薦長度為30個時，F(xiàn)WNBI的準確率達到最大；但在推薦長度大于70個時，兩者的準確率和召回率幾乎相等，F(xiàn)WNBI相對于WNBI并無明顯的優(yōu)勢。

4.2.2 基于F1指標的評價

由于受到推薦列表長度、評分稀疏性以及喜好閥值等多方面因素的影響，很多學者不提倡利用準確率和召回率來評價推薦系統(tǒng)，特別是只單獨考慮一種指標的時候誤差極大[11]。

一種常用的方法是同時考慮準確率和召回率從而比較全面地評價算法的優(yōu)劣，文獻[12-13]提出了F1指標，定義為：

(9)

圖4 F1指標曲線

其中：R(L)為系統(tǒng)整體的召回率；P(L)為系統(tǒng)整體的準確率。

圖4為FWNBI和WNBI分別在推薦長度分別為5個、10個、20個、30個、…、100個下的F1指標的折線圖。由圖4可知：在推薦長度為20～60個時，F(xiàn)WNBI推薦算法明顯優(yōu)于WNBI推薦算法，并且在推薦長度為30個時達到最優(yōu)。隨著推薦長度的增加，F(xiàn)WNBI推薦算法的優(yōu)勢逐漸變小。

4.2.3 基于平均排序分的評價

無論是FBWN推薦算法還是WNBI推薦算法，他們對于推薦的排序都有一定的要求，如果僅僅用分類準確度來評價推薦算法，顯然是不太全面的。假設現(xiàn)在有兩種推薦算法A和B，它們給某一用戶推薦的產品列表a和b中均有一個產品c是該用戶所喜歡的，但是c在a列表中排在第一個，而在b列表中排在最后一個；根據(jù)式(8)可知：它們的推薦準確率相同，但給用戶的體驗上顯然是A要優(yōu)于B。文獻[9]提出了用平均排序來度量推薦系統(tǒng)的排序準確度。對于某一用戶u來說，商品α的排序分定義如下：

圖5 平均排序分RS曲線

(10)

其中：Lu表示用戶u未選擇過的商品數(shù)目；luα為待預測商品α在用戶u的推薦列表中的排名。將所有用戶的排序分求平均即得到系統(tǒng)的排序分RS。排序分值越小，說明系統(tǒng)越趨向于把用戶喜歡的商品排在前面；反之，則說明系統(tǒng)把用戶喜歡的商品排在了后面[11-16]。圖5為FWNBI和WNBI分別在推薦長度為5個、10個、20個、30個、40個、50個的情況下的平均排序分。由圖5可知：FWNBI推薦算法更趨向于將用戶喜歡的產品排在推薦列表的前面。較WNBI有更好的推薦質量。

5 結束語

本文針對用戶“興趣漂移”問題，提出了一種改進的加權二部圖推薦算法：基于遺忘機制與加權二部圖的推薦算法FWNBI。實驗結果表明：F1指標在推薦長度為30個時，推薦質量達到最優(yōu)，明顯優(yōu)于WNBI推薦算法;推薦長度在10～60個時，F(xiàn)WNBI的推薦質量要優(yōu)于WNBI，并且FWNBI推薦算法更趨向于將用戶喜歡的產品排在推薦列表的前面。

雖然FWNBI推薦算法的推薦質量要優(yōu)于WNBI推薦算法，但FWNBI推薦算法的計算復雜度要大于WNBI推薦算法，當產品的數(shù)量達到一定的程度，計算復雜度將制約著該推薦算法的效率。

[1] 許海玲,吳瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報,2009,20(2):350-362.

[2] 陳敏.個性化推薦系統(tǒng)研究[D].南京:南京郵電大學,2012.

[3] 張新猛,蔣盛益.基于加權二部圖的個性化推薦算法[J].計算機應用,2012,32(3):654-657.

[4] Koren Y.Collaborative Filtering with Temporal Dynamics[J].Communications of the ACM,2010,53(4):89-97.

[5] 鄭志高,劉京.時間加權不確定近鄰協(xié)同過濾算法[J].計算機科學,2014,41(8):7-12.

[6] 趙婷,肖如良.融合時間綜合影響的輪盤賭游走個性化推薦算法[J].計算機應用,2014,34(4):1114-1117,1129.

[7] Cheng Y,Qiu G,Bu J,et al.Model Bloggers′ Interests Based on Forgetting Mechanism[C]//Proceedings of the 17th international Conference on World Wide Web.ACM,2008:1129-1130.

[8] 于洪,李轉運.基于遺忘曲線的協(xié)同過濾推薦算法[J].南京大學學報,2010,46(5):520-527.

[9] Zhou T,Ren J,Matú? M,et al.Bipartite Network Projection and Personal Recommendation[J].Physical Review E,2007,76(4):6116-6123.

[10] 劉建國,周濤,汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學進展,2009,19(1):1-15.

[11] 朱郁筱,呂琳媛.推薦系統(tǒng)評價指標綜述[J].電子科技大學學報,2012,42(2):163-175.

[12] Van R C J.Information Retrieval[M].MA,USA:Butterworth-Heinemann Newton,1979.

[13] Pazzani M J,Billsus D.Learning and Revising User Profiles:the Identification of Interesting Web Sites[J].Machine Learning,1997,27(3):313-331.

[14] 項亮.推薦系統(tǒng)實踐[M].北京:人民郵電出版社,2012.

[15] 黃威,尚有林,王琪鳳.二部圖匹配的一個判別條件[J].河南科技大學學報:自然科學版,2013,34(4):85-87.

[16] Soboroff I,Nichloas C.Combining Content and Collaboration in Text Filtering[C]//Proceedings of the IJCAI’99 Workshop on Machine Learning for Information Filtering.1999:86-91.

貴州省科學技術基金項目(200917);貴州省教育廳重點基金項目(20090034);貴陽市科技局重點基金項目(2010183)

劉曉光(1990-),男,河南許昌人,碩士生;謝曉堯(1952-),男,貴州貴陽人,教授,博士,博士生導師,主要研究方向為網(wǎng)絡信息安全、工程計算應用.

2014-07-03

1672-6871(2015)03-0048-06

TP3

A