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

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

（1.南京工業大學 經濟與管理學院，南京 211816；2.南京中醫藥大學 經貿管理學院，南京 210046）

0 引言

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

1 基于二分圖的SimRank算法

SimRank算法是一個基于二分圖模型的隨機游走算法，定義兩個節點相似的基本思想是：如果指向節點a和指向節點b的節點相似，那么a和b也認為是相似的。給定有向圖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）是一個阻尼系數，通常取值0.6～0.8。

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

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

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

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

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

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

2 算法的改進

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

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

2.2 引入衰減函數將時間影響量化

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

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

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

當得到時間上下文信息時，通過將式(7)引入到式(2)得到式(8)改進的SimRank相似度計算算法即TSR算法：

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

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

3 實驗結果分析

3.1 數據集與評測指標

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

召回率定義為：

準確率定義為：

覆蓋率定義為：

3.2 實驗結果與分析

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

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

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

表2顯示了在數據集上使用基于二分圖模型的協同過濾算法（SimRank-CF）的推薦結果（N=5）。當K=10時，推薦效果最佳，準確率為12.58。

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

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

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

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

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

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

表6 各種算法的對比結果

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

圖1 三種算法準確率對比圖（N=5）

4 結束語

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