基于融合時間信息影響的SimRank算法的個性化推薦

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

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

0 引言

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

1 基于二分圖的SimRank算法

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

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

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

對于用戶A和用戶B，且A≠B：

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

對于物品a與物品b，且a≠b：

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

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

2 算法的改進(jìn)

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

3.1 數(shù)據(jù)集與評測指標(biāo)

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

召回率定義為：

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

覆蓋率定義為：

3.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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