一種結(jié)合遺忘機(jī)制與加權(quán)二部圖的推薦算法

劉曉光，謝曉堯

(1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng)550000；2.貴州師范大學(xué) 信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550000)

?

一種結(jié)合遺忘機(jī)制與加權(quán)二部圖的推薦算法

劉曉光1，2，謝曉堯2

(1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng)550000；2.貴州師范大學(xué) 信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550000)

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

興趣漂移；遺忘機(jī)制；加權(quán)二部圖；資源分配；推薦算法

0 引言

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

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

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

1 遺忘機(jī)制

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

(1)

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

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

圖1 艾賓浩斯遺忘曲線(xiàn)

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

2 加權(quán)二部圖推薦算法

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

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

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

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

3 FWNBI推薦算法

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

基于遺忘機(jī)制和加權(quán)二部圖的推薦算法(FWNBI)，在給用戶(hù)推薦時(shí)考慮了時(shí)間對(duì)用戶(hù)興趣的影響，通過(guò)遺忘機(jī)制引入了遺忘因子fij，用來(lái)量化當(dāng)前時(shí)間t時(shí)用戶(hù)j對(duì)于產(chǎn)品i的興趣的保留程度，見(jiàn)式(2)。

(2)

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

利用遺忘因子fij與當(dāng)時(shí)用戶(hù)j對(duì)產(chǎn)品的打分值wij的乘積，kij來(lái)估計(jì)當(dāng)前用戶(hù)j對(duì)于該產(chǎn)品i的喜歡程度，見(jiàn)式(3)。

kij=wijfij。

(3)

圖2 改進(jìn)推薦算法資源轉(zhuǎn)移過(guò)程

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

由資源分配過(guò)程可知，任意產(chǎn)品j分配給產(chǎn)品i的資源權(quán)重Wij計(jì)算公式為：

(4)

(5)

其中：k(xj)表示與產(chǎn)品xj連接的所有用戶(hù)邊權(quán)之和；k(yl)表示與用戶(hù)yl連接的所有產(chǎn)品邊權(quán)之和；amn表示用戶(hù)n是否選擇過(guò)產(chǎn)品m；kmn表示用戶(hù)n對(duì)產(chǎn)品m的喜歡程度的估計(jì)值。

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

f′=Wf，

(6)

其中：W為系統(tǒng)的資源分配矩陣；f為目標(biāo)用戶(hù)的初始資源分配構(gòu)型；f′為系統(tǒng)給目標(biāo)用戶(hù)推薦的產(chǎn)品的矢量原始列表。

把矢量f′中用戶(hù)已經(jīng)選擇過(guò)的產(chǎn)品所對(duì)應(yīng)的值置為0，然后將矢量f′中的元素按值的大小進(jìn)行排序，值越大就說(shuō)明該用戶(hù)越喜歡其所對(duì)應(yīng)的產(chǎn)品。排序靠前的值所對(duì)應(yīng)的產(chǎn)品，可以推薦給目標(biāo)用戶(hù)。

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

FWNBI算法描述：

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

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

輸出：輸出格式為(ui，pj，kij，0)的數(shù)組initial[ui][pj]，用戶(hù)ui選擇過(guò)的產(chǎn)品的邊的權(quán)值之和記為Ku[ui]，選擇過(guò)產(chǎn)品pj的用戶(hù)的邊的權(quán)值之和記為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轉(zhuǎn)換為格式為(ui，pj，kij，0)的數(shù)組initial[ui][pj]；

計(jì)算與用戶(hù)ui相連的邊的權(quán)值之和，記為Ku(ui)；

計(jì)算與產(chǎn)品pj相連的邊的權(quán)值之和，記為Km(pj)；

Endfor

第2步：計(jì)算資源轉(zhuǎn)移矩陣。

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

輸出：資源轉(zhuǎn)移矩陣W。

Foreach h in H

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

Endfor

第3步：為某個(gè)用戶(hù)計(jì)算得到推薦列表。

輸入：用戶(hù)的初始資源分配構(gòu)型f，資源轉(zhuǎn)移矩陣W；

輸出：某個(gè)用戶(hù)的推薦列表R。

Begin

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

得到初始推薦列表R=f1-f，取值較大的所對(duì)應(yīng)的產(chǎn)品形成最終推薦列表。

End

4 算法評(píng)價(jià)

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

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

4.2.1 基于準(zhǔn)確率、召回率的評(píng)價(jià)

準(zhǔn)確率和召回率是推薦系統(tǒng)中常用的兩個(gè)評(píng)價(jià)指標(biāo)。準(zhǔn)確率也叫查準(zhǔn)率，表示用戶(hù)喜歡的產(chǎn)品在系統(tǒng)推薦列表中所占的比例；召回率也叫查全率，表示一個(gè)用戶(hù)喜歡的商品被推薦的概率[11]。

表2 待預(yù)測(cè)的產(chǎn)品4種可能的狀態(tài)

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

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

(7)

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

(8)

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

圖3為基于加權(quán)二部圖的推薦算法(WNBI)、基于遺忘機(jī)制和加權(quán)二部圖的推薦算法(FWNBI)在推薦長(zhǎng)度分別為5個(gè)、10個(gè)、20個(gè)、30個(gè)、…、100個(gè)下的準(zhǔn)確率和召回率折線(xiàn)圖。

圖3 算法的準(zhǔn)確率和召回率折線(xiàn)

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

4.2.2 基于F1指標(biāo)的評(píng)價(jià)

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

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

(9)

圖4 F1指標(biāo)曲線(xiàn)

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

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

4.2.3 基于平均排序分的評(píng)價(jià)

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

圖5 平均排序分RS曲線(xiàn)

(10)

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

5 結(jié)束語(yǔ)

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

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

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

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

[3] 張新猛,蔣盛益.基于加權(quán)二部圖的個(gè)性化推薦算法[J].計(jì)算機(jī)應(yīng)用,2012,32(3):654-657.

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

[5] 鄭志高,劉京.時(shí)間加權(quán)不確定近鄰協(xié)同過(guò)濾算法[J].計(jì)算機(jī)科學(xué),2014,41(8):7-12.

[6] 趙婷,肖如良.融合時(shí)間綜合影響的輪盤(pán)賭游走個(gè)性化推薦算法[J].計(jì)算機(jī)應(yīng)用,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] 于洪,李轉(zhuǎn)運(yùn).基于遺忘曲線(xiàn)的協(xié)同過(guò)濾推薦算法[J].南京大學(xué)學(xué)報(bào),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] 劉建國(guó),周濤,汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J].自然科學(xué)進(jìn)展,2009,19(1):1-15.

[11] 朱郁筱,呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述[J].電子科技大學(xué)學(xué)報(bào),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] 項(xiàng)亮.推薦系統(tǒng)實(shí)踐[M].北京:人民郵電出版社,2012.

[15] 黃威,尚有林,王琪鳳.二部圖匹配的一個(gè)判別條件[J].河南科技大學(xué)學(xué)報(bào):自然科學(xué)版,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.

貴州省科學(xué)技術(shù)基金項(xiàng)目(200917);貴州省教育廳重點(diǎn)基金項(xiàng)目(20090034);貴陽(yáng)市科技局重點(diǎn)基金項(xiàng)目(2010183)

劉曉光(1990-),男,河南許昌人,碩士生;謝曉堯(1952-),男,貴州貴陽(yáng)人,教授,博士,博士生導(dǎo)師,主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全、工程計(jì)算應(yīng)用.

2014-07-03

1672-6871(2015)03-0048-06

TP3

A