基于融合時(shí)間信息影響的SimRank算法的個(gè)性化推薦

劉 曜，潘 芳，潘 郁，朱曉峰

（1.南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，南京 211816；2.南京中醫(yī)藥大學(xué) 經(jīng)貿(mào)管理學(xué)院，南京 210046）

0 引言

在當(dāng)今信息嚴(yán)重過載的環(huán)境下，個(gè)性化推薦是信息檢索和內(nèi)容發(fā)現(xiàn)的關(guān)鍵方法。目前應(yīng)用最為廣泛的個(gè)性化推薦算法是協(xié)同過濾算法，但是該算法已被證明存在許多問題。其中最為嚴(yán)重是如何對(duì)系統(tǒng)中的新用戶進(jìn)行推薦（冷啟動(dòng)問題）[1]。由于用戶-項(xiàng)目關(guān)系可以用二分圖模型來表示，因此許多基于圖的算法可以應(yīng)用在基于圖的個(gè)性化推薦上[2]。針對(duì)冷啟動(dòng)問題，用混合用戶模型對(duì)用戶首先進(jìn)行一個(gè)預(yù)處理生成一定數(shù)量的用戶集，然后構(gòu)成用戶集-項(xiàng)目的二分圖，進(jìn)而給新用戶進(jìn)行推薦[3]。目前二分圖模型在個(gè)性化推薦中的使用逐漸普遍，但是都缺乏對(duì)時(shí)間上下文信息的考慮。由于用戶的興趣是隨著時(shí)間值的改變而持續(xù)變化的，而且這些變化在用戶不斷增加的新行為中得到充分體現(xiàn)。一個(gè)實(shí)時(shí)的推薦系統(tǒng)需要能夠?qū)崟r(shí)響應(yīng)用戶新的行為，讓推薦列表不斷更新，從而滿足用戶不斷變化的興趣[4]。從實(shí)際需求和推薦的準(zhǔn)確度雙重角度考慮，在個(gè)性化推薦中應(yīng)用融合時(shí)間上下文信息的二分圖模型更合理，且更具實(shí)際意義。

1 基于二分圖的SimRank算法

SimRank算法是一個(gè)基于二分圖模型的隨機(jī)游走算法，定義兩個(gè)節(jié)點(diǎn)相似的基本思想是：如果指向節(jié)點(diǎn)a和指向節(jié)點(diǎn)b的節(jié)點(diǎn)相似，那么a和b也認(rèn)為是相似的。給定有向圖G=（V,E），V是圖的頂點(diǎn)集，E是圖的邊集，任取a,b,∈V,I(a)={c|(a,c)]E},I(b)={c|(b,c)∈E},S(a,b)表示a與b的相似度。SimRank算法計(jì)算公式如下

其中，C∈（0,1）是一個(gè)阻尼系數(shù)，通常取值0.6～0.8。

SimRank是一個(gè)基于圖的拓?fù)浣Y(jié)構(gòu)信息來衡量圖中任意兩個(gè)對(duì)象間相似度的模型，同樣可以應(yīng)用于計(jì)算項(xiàng)目推薦中的用戶間的相似性或項(xiàng)目間的相似性。給定用戶-物品二分圖G(V,E)，頂點(diǎn)集合V由用戶頂點(diǎn)Vu和物品頂點(diǎn)Vk兩部分構(gòu)成。即可以把SimRank算法展開為如下兩種形式：

對(duì)于用戶A和用戶B，且A≠B：

其中c1∈[0,1]表示衰減系數(shù)，O(A)表示用戶A的出鏈集合，表示A的出度。

對(duì)于物品a與物品b，且a≠b：

其中c2∈[0,1]表示衰減系數(shù)。

SimRank算法依據(jù)用戶-項(xiàng)目之間的評(píng)分給出推薦，緩解了冷啟動(dòng)和數(shù)據(jù)稀疏的問題，但是該算法沒有考慮時(shí)間信息對(duì)推薦質(zhì)量的影響，推薦效果并不是很理想。

2 算法的改進(jìn)

2.1 基于二分圖模型的個(gè)性化推薦算法

將二分圖模型與協(xié)同過濾算法相結(jié)合，首先將節(jié)點(diǎn)結(jié)構(gòu)轉(zhuǎn)化為二分圖，采用二分圖算法得到用戶節(jié)點(diǎn)與項(xiàng)目節(jié)點(diǎn)之間的全局相似度，再結(jié)合協(xié)同過濾算法，得到基于二分圖模型的協(xié)同過濾算法。使用公式(5)計(jì)算用戶u對(duì)項(xiàng)目i的興趣p(u,i)，進(jìn)一步得到用戶u的top-N列表。

2.2 引入衰減函數(shù)將時(shí)間影響量化

本文從時(shí)間信息與用戶興趣的相關(guān)性出發(fā)，設(shè)計(jì)一種融合時(shí)間影響的SimRank算法（TSR）。TSR基于以下方向考慮時(shí)間上下文信息對(duì)推薦結(jié)果的影響：隨著時(shí)間改變，用戶的興趣是在不斷變化的，即用戶興趣與時(shí)間信息的關(guān)聯(lián)性。通常在相對(duì)短的時(shí)間段內(nèi)用戶喜好的物品具有比較高的相似性，相較于用戶很久之前的行為，用戶近期的顯性及隱性行為能更好的體現(xiàn)用戶當(dāng)前的興趣喜好。通過分析時(shí)間信息對(duì)推薦結(jié)果的影響特點(diǎn)，引入數(shù)學(xué)衰減函數(shù)量化時(shí)間信息對(duì)推薦結(jié)果的影響，式(6)為引入的數(shù)學(xué)衰減函數(shù)原型：

式(6)度量了變量x與x0的相關(guān)性，的值越小，他們之間的距離就越短，同時(shí)意味著關(guān)聯(lián)性也就越大。k是相關(guān)性因子，用來調(diào)節(jié)x與x0的相關(guān)程度。從以上實(shí)際情況出發(fā)，根據(jù)數(shù)學(xué)衰減模型(6)，提出了考慮時(shí)間信息影響的前提下，用戶u在選擇了項(xiàng)目i后對(duì)項(xiàng)目j的興趣度fui(j)如式(7)：

α是時(shí)間衰減參數(shù)，它的取值隨著系統(tǒng)變化而改變。當(dāng)系統(tǒng)中某用戶的興趣變化相對(duì)比較頻繁時(shí)，就應(yīng)該取比較大的α，反之需要取比較小的α。其中tui與tuj分別是用戶u對(duì)項(xiàng)目i和項(xiàng)目j產(chǎn)生行為的時(shí)間。決定了用戶u對(duì)項(xiàng)目j的興趣度，值越小即用戶對(duì)項(xiàng)目i和項(xiàng)目j產(chǎn)生行為的時(shí)間越近，則fui(j)越大，用戶對(duì)項(xiàng)目j感興趣的概率就越高。反之當(dāng)值越大，則fui(j)越小，用戶對(duì)項(xiàng)目j感興趣的概率就越低。

當(dāng)?shù)玫綍r(shí)間上下文信息時(shí)，通過將式(7)引入到式(2)得到式(8)改進(jìn)的SimRank相似度計(jì)算算法即TSR算法：

除了考慮時(shí)間信息對(duì)相關(guān)表的影響，也考慮到時(shí)間信息對(duì)預(yù)測(cè)公式的影響。一般來說用戶近期的行為相似關(guān)系比較大，因此本文也借助數(shù)學(xué)衰減函數(shù)原型(6)設(shè)計(jì)了衰減函數(shù)式改進(jìn)了預(yù)測(cè)公式(9)：

其中N(i,k)包含了與項(xiàng)目i最接近的k個(gè)項(xiàng)目。t0是當(dāng)前時(shí)間，當(dāng)值越小即tuj與t0越靠近時(shí)，與項(xiàng)目j相似度高的項(xiàng)目在用戶u的推薦列表中的排名就會(huì)越靠前。β是時(shí)間衰減參數(shù)，根據(jù)不同的數(shù)據(jù)集選擇相應(yīng)的值。在改進(jìn)了SimRank算法后并將其與引入時(shí)間衰減函數(shù)的預(yù)測(cè)公式相結(jié)合得到了基于TSR的協(xié)同過濾模型（TSR-CF），即基于融合時(shí)間信息影響的SimRank算法的個(gè)性化推薦模型。

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

3.1 數(shù)據(jù)集與評(píng)測(cè)指標(biāo)

數(shù)據(jù)集：本文采用GroupLens提供的MovieLens數(shù)據(jù)集中的MovieLens 1M Dataset[5]，該數(shù)據(jù)集包含6000位用戶對(duì)4000部電影做出的1000000個(gè)評(píng)價(jià)。本文采用離線實(shí)驗(yàn)來評(píng)測(cè)及比較各種算法。要得到推薦算法的具體評(píng)測(cè)指標(biāo)值，首先將MovieLens數(shù)據(jù)集隨機(jī)分成獨(dú)立的M份（本文中M=10），從中隨機(jī)挑選出一份作為測(cè)試數(shù)據(jù)集，余下的M-1份是訓(xùn)練數(shù)據(jù)集。最后將M次實(shí)驗(yàn)得到的評(píng)測(cè)指標(biāo)結(jié)果求平均，作為最終的評(píng)測(cè)指標(biāo)值。評(píng)測(cè)指標(biāo)：

召回率定義為：

準(zhǔn)確率定義為：

覆蓋率定義為：

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

表1顯示了在數(shù)據(jù)集上直接使用基于二分圖模型的SimRank相似度算法的推薦結(jié)果，從實(shí)驗(yàn)結(jié)果來看，直接使用SimRank算法計(jì)算二分圖節(jié)點(diǎn)距離并產(chǎn)生推薦結(jié)果的做法，沒有獲得理想的測(cè)評(píng)指標(biāo)值。當(dāng)N=1時(shí)，其準(zhǔn)確率值為11.36，召回率與覆蓋率的值僅為0.77與0.35。當(dāng)N=5時(shí)，準(zhǔn)確率為7.57。

表1 基于SimRank算法直接推薦的效果

表2 基于二分圖模型的協(xié)同過濾算法的推薦結(jié)果（N=5）

表2顯示了在數(shù)據(jù)集上使用基于二分圖模型的協(xié)同過濾算法（SimRank-CF）的推薦結(jié)果（N=5）。當(dāng)K=10時(shí)，推薦效果最佳，準(zhǔn)確率為12.58。

表3 基于二分圖模型的協(xié)同過濾算法的推薦結(jié)果（N=10）

表3顯示了在該數(shù)據(jù)集上基于二分圖模型的協(xié)同過濾算法（SimRank—CF）的推薦情況（N=10）。在K=10時(shí)，取得最優(yōu)值，準(zhǔn)確率為10.43%。

表4 基于融合時(shí)間信息的SimRank算法的推薦結(jié)果（N=5）

表4顯示了基于融合時(shí)間信息的SimRank算法的推薦結(jié)果（TSR-CF）（N=5）。當(dāng)K=10時(shí)，推薦效果最佳，準(zhǔn)確率為16.93%，召回率為4.85%，覆蓋率為13.96%。

表5 基于融合時(shí)間信息的SimRank算法的推薦結(jié)果（N=10）

表5顯示了基于融合時(shí)間信息的SimRank算法的推薦結(jié)果（TSR-CF）（N=10），當(dāng)K=10時(shí)，推薦性能最佳，準(zhǔn)確率達(dá)到14.69%，召回率達(dá)到7.84%，覆蓋率達(dá)到22.68%。

表6 各種算法的對(duì)比結(jié)果

表6中列出了各種算法的對(duì)比結(jié)果，這里不再考慮參數(shù)K的影響，將K選為最優(yōu)準(zhǔn)確率和召回率的值10。可以看到，直接使用SimRank算法計(jì)算二分圖節(jié)點(diǎn)距離并產(chǎn)生推薦結(jié)果的做法效果最差，其次基于物品的協(xié)同過濾和基于SimRank算法的協(xié)同過濾，TSR算法取得效果最佳。從結(jié)果上看SimRank算法不適合直接用在稠密數(shù)據(jù)集上進(jìn)行推薦。圖1對(duì)三種基于二分圖模型的推薦在準(zhǔn)確率方面進(jìn)行比較，說明傳統(tǒng)的基于二分圖模型的協(xié)同過濾算法在稠密數(shù)據(jù)集上也并無優(yōu)勢(shì)，而TSR算法的推薦結(jié)果要優(yōu)于相比較的兩個(gè)算法。

圖1 三種算法準(zhǔn)確率對(duì)比圖（N=5）

4 結(jié)束語

本文根據(jù)當(dāng)前基于圖模型推薦算法的特點(diǎn)的前提下，結(jié)合實(shí)際應(yīng)用背景，提出了融合時(shí)間信息的simrank個(gè)性化推薦算法（TSR），并將其與傳統(tǒng)協(xié)同過濾算法相結(jié)合，得到了基于融合時(shí)間信息二分圖模型的個(gè)性化推薦（TSR-CF）。實(shí)驗(yàn)表明該算法在覆蓋率、召回率及準(zhǔn)確率三個(gè)指標(biāo)上比直接使用基于simrank算法的個(gè)性化推薦、基于SimRank的協(xié)同過濾和基于物品的協(xié)同過濾個(gè)性化推薦有明顯的改善，充分證明了時(shí)間綜合信息對(duì)推薦性能的提高有積極推動(dòng)作用。