一種結合評分時間特性的協(xié)同過濾推薦算法

李圣秋，吳偉明，谷勇浩

（北京郵電大學 計算機學院，北京市 100876）

一種結合評分時間特性的協(xié)同過濾推薦算法

李圣秋，吳偉明，谷勇浩

（北京郵電大學 計算機學院，北京市 100876）

用戶評分是協(xié)同推薦算法實現(xiàn)未知評分預測的主要依據(jù)，傳統(tǒng)協(xié)同推薦算法一般只利用評分的數(shù)值，而忽視評分產(chǎn)生時間對推薦的作用，但是評分時間特性對推薦系統(tǒng)準確性的影響不容小覷。本文針對這個問題，以傳統(tǒng)協(xié)同過濾推薦算法為基礎，從評分時間角度對推薦算法的相似度計算和評分預測過程進行改進，提出了一種結合評分時間特性的協(xié)同過濾推薦算法。算法依據(jù)用戶對項目的評分及時間計算出一個時間因子，并將時間因子融入到相似度的計算中, 使推薦給目標用戶的項目更加合理。通過實驗進行該算法與現(xiàn)有協(xié)同推薦算法的對比，驗證了該算法在提高推薦準確性方面的有效性。

推薦系統(tǒng)；協(xié)同過濾；時間權重；評分預測

本文著錄格式：李圣秋，吳偉明，谷勇浩. 一種結合評分時間特性的協(xié)同過濾推薦算法[J]. 軟件，2016，37（11）：142-145

0 引言

互聯(lián)網(wǎng)的迅速發(fā)展將人們帶入了一個嶄新的信息時代，網(wǎng)絡中的信息資源越來越豐富，當用戶面對海量的數(shù)據(jù)信息時，如何在茫茫的信息海洋中快速、準確地找到需要的信息成為用迫切需要解決的問題。搜索引擎的出現(xiàn)在一定程度上緩解了用戶的信息負擔，但搜索引擎往往呈現(xiàn)給用戶同樣的搜索結果，無法針對用戶的興趣愛好主動提供個性化服務。在此背景下，推薦系統(tǒng)應運而生。概括來說，推薦系統(tǒng)以用戶為中心，通過研究用戶的行為、偏好和環(huán)境等因素，過濾與用戶偏好不相關的內容，為用戶推薦更具針對性、滿足其個性化需求的信息。常用的推薦方法有基于內容的推薦、基于知識的推薦、協(xié)同過濾推薦以及組合推薦等，其中協(xié)同過濾推薦是迄今為止應用最成功的個性化推薦技術之一[1]，

其基本思想是：通過計算用戶對項目評分之間的相似性，搜索目標用戶的最近鄰居，然后根據(jù)最近鄰居的評分向目標用戶產(chǎn)生推薦。

然而用戶的興趣偏好是隨著時間動態(tài)變化的，這就需要推薦系統(tǒng)能實時地向用戶推薦新穎的資源[2]。但傳統(tǒng)的協(xié)同過濾推薦算法并沒有考慮用戶的興趣隨時間的推移而發(fā)生變化，導致推薦的信息可能是過時的或不是用戶當前最感興趣的信息，影響了算法的準確性。因此，本文在傳統(tǒng)協(xié)同過濾算法的基礎上，提出了一個改進的結合了評分時間特性的協(xié)同過濾推薦算法，并利用實驗對傳統(tǒng)算法和本文提出的改進算法的準確度進行了比較。實驗結果表明，結合了評分時間特性的推薦算法提高了推薦的準確度。

1 基于項目的協(xié)同過濾推薦算法

協(xié)同過濾算法根據(jù)用戶的歷史評分數(shù)據(jù)進行推薦，一般來說分為基于用戶的協(xié)同過濾（User Based Collaborative Filtering，UserCF）和基于項目的協(xié)同過濾（Item Based Collaborative Filtering，ItemCF）。

UserCF從用戶角度出發(fā)，按照“相似用戶共享興趣”的思想；為了確定相似用戶，UserCF需要根據(jù)用戶對不同信息項目的歷史評分，計算不同用戶之間的相似度，但用戶相似性較不穩(wěn)定，用戶相似度一般需要在線計算和更新，這導致UserCF的在線性能難以保證，限制了UserCF在大型信息服務系統(tǒng)中應用。ItemCF從項目角度出發(fā)，服從“用戶未來興趣與歷史興趣相似”的假設，為確定與目標用戶已訪問項目的相似項目，ItemCF需要計算項目間相似度，較之于用戶相似度，項目相似性更為穩(wěn)定，ItemCF的相似度計算可離線計算，ItemCF可提供比UserCF更高的響應速度[3]。相似度模型是決定算法推薦效果好壞的關鍵，傳統(tǒng)的相似度度量方法有余弦相似度（Cosinimilarity，Cosin）、Jaccard 相似度（Jaccard Similarity，Jaccard）和皮爾遜相關系數(shù)[4]等。

鑒于ItemCF的性能優(yōu)勢，其在學術和實際應用中得到了大量研究和實踐，本文的研究內容將以ItemCF作為基準協(xié)同過濾推薦算法。

基于物品的協(xié)同過濾推薦算法主要分為兩步[5]：

1）計算物品之間的相似度；

2）根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表。

具體的過程是首選需要獲取用戶代理捕獲并記錄用戶對已訪問項目的評分數(shù)據(jù)，并以用戶描述向量形式表示用戶興趣，所有用戶描述向量按行構造為用戶-項目評分矩陣；根據(jù)用戶-項目評分矩陣，采用特定的相似性度量標準，計算不同項目之間的相似度；參考項目間相似度計算的結果，確定與目標項目相似的鄰居項目；針對目標用戶的每一未評分目標項目，根據(jù)其鄰居項目的評分，以鄰居項目與目標項目的相似度為權重，對鄰居項目評分進行加權求和預測用戶對目標項目的評分；依據(jù)對目標項目所預測的評分值大小，對目標用戶的所有未評分項目進行降序排序，進而選擇Top-N項目構成推薦列表，并主動推薦給目標用戶。

一個m*n的用戶－項目評分矩陣Rm*n，見表1。

表1 用戶-項目評分矩陣示例Tab.1 An Example of User-Item Rating Matrix

其中，Useri表示第i個用戶，Itemj表示第j個項目，Rateij表示第i個用戶對第j個項目的評分，總共有m個用戶n個項目。

為了確定目標項目的鄰居項目，ItemCF通過一定的相似度來度量項目間的相似性，常用的相似度計算方法有夾角余弦相似度和皮爾遜相關系數(shù)，鑒于皮爾遜相關系數(shù)不受評分分布的影響，其在實際應用中使用更為廣泛[6]，故本文采用皮爾遜相關系數(shù)計算項目間的相似度。

對于兩個項目Itemi與Itemj，其皮爾遜相關系數(shù)sim(i,j)可表示為：

其中Uij指的是Itemi與Itemj的公共評分用戶集，和分別表示Itemi與Itemj的平均評分值。在得到項目之間的相似度后，ItemCF通過如下公式計算用戶ui對一個項目sj的興趣：

其中sim(k,j)即是Itemk和Itemj的相似度，Sj是用戶喜歡的項目的集合，rik是用戶ui對項目Itemk

的興趣度。使用公式（2）這樣處理的結果是和用戶歷史上感興趣的物品越相似的物品，越有可能在用戶的推薦列表中獲得比較高的排名。

2 改進算法

2.1 時間效應

傳統(tǒng)協(xié)同過濾算法在尋找用戶的最近鄰居時，將用戶不同時間的項目評分同等對待，沒有考慮用戶對各個項目的評分不是在同一時間段進行的實際情況[7]。一般來說，用戶近期訪問過的項目對推薦該用戶未來可能感興趣的項目起比較重要的作用，而早期的訪問記錄對生成推薦結果影響相對較小，這是因為用戶的興趣偏好隨時間發(fā)生改變，而在較短的一段時間間隔內用戶的興趣相對穩(wěn)定。因此一個用戶感興趣的項目最可能和他近期訪問過的項目相似。也就是說，雖然所有評價都對推薦結果有影響，但最新評價貢獻更大，舊數(shù)據(jù)反映用戶以前的喜好，它在推薦的預測上應占較小的權值。

2.2 評分時間因子

根據(jù)前面的討論，傳統(tǒng)ItemCF算法在實現(xiàn)相似度計算和評分預測過程中只參考了評分的數(shù)值信息，對于可從時間角度反映用戶興趣變化的評分時間信息并未充分利用，過期的歷史評分數(shù)據(jù)不僅不能反映用戶的當前興趣，還干擾了當前的相似度計算和評分預測，導致ItemCF無法產(chǎn)生滿足用戶當前信息需求的推薦[8]。針對上述問題，應對傳統(tǒng)ItemCF算法的關鍵計算過程進行改進和修正，引入對評分時間特性的應用，針對用戶ui對項目Itemj產(chǎn)生的評分rij，可采用公式（3）形式的評分時間因子wij對該評分在時間方面的重要性加以區(qū)分。

公式（3）中用戶ui產(chǎn)生的所有評分構成其評分集合Ri={rik|rik≠0∧k∈n}，dij為評分rij對應的產(chǎn)生時間，為了克服不同用戶評分在絕對物理時間上存在的差異，公式（3）采用rank函數(shù)將評分絕對物理時間映射為評分在評分時間序列上的相對位置編號，公式（3）按照歷史評分產(chǎn)生的時間對評分的重要性進行了線性衰減，其取值為（0…1）之間的小數(shù)。

2.3 ItemCF算法集成評分時間因子

通過在傳統(tǒng)ItemCF算法中引入評分時間因子，可以更全面地利用用戶評分信息改善相似度的計算和評分預測過程。改進后的皮爾遜相關系數(shù)和評分預測方法如公式（4）和公式（5）所示。

改進后算法的流程如下：

輸入：

用戶集合U={ui|1≤i≤m}

項目集合S={sj|1≤j≤n}

用戶-項目評分矩陣Rm*n

輸出：

目標用戶u的Top-N項目推薦列表

Step1：根據(jù)用戶-項目評分矩陣R利用公式（3）計算評分rij對應的評分時間因子wij；

Step2：根據(jù)項目集合S，利用公式（4）計算項目si與sj的相似度sim(i,j)；

Step3：統(tǒng)計項目si所獲得的非0評分數(shù)量ci，根據(jù)與項目si的相似度，對所有其他項目進行降序排序，并選擇前K個項目作為項目si的鄰居項目集合Si；

Step4：根據(jù)公式（5）預測用戶ui對項目sj的評分pij

Step5：將步驟4中項目的預測評分按照降序從大到小的排列，最后選擇排在最前面評分最高的前n個項目推薦給用戶u。

3 實驗與結果分析

3.1 實驗數(shù)據(jù)及實驗環(huán)境

本文采用由 Minnesota大學的GroupLens研究小組創(chuàng)建的MovieLens數(shù)據(jù)集中的100K的數(shù)據(jù)集進行實驗。該數(shù)據(jù)集記錄共943個用戶對1 682部電影的10萬條評分[9]。評分的分值在[0-5]之間不等，用戶對電影的喜愛程度隨著分值的增加而遞增[10]。從數(shù)據(jù)集中隨機抽取80%作為訓練集，剩余20%作為測試集。

實驗軟硬件環(huán)境是Intel(R) Pentium(TM) CPU G2030 3 GHz，4 GB內存，Microsoft Windows10操作系統(tǒng)，算法使用Matlab實現(xiàn)。

3.2 檢驗指標

本文采用平均絕對誤差（MAE）評價該系統(tǒng)的推

薦質量[11]。MAE 通過計算實際評分與預測評分之間的差值來衡量算法的好壞。MAE值越小說明該算法就越好。MAE值的計算如公式（6）所示。

其中，Pu,i表示用戶u對項目i的預測評分，Ru,i表示用戶u對項目i的真實評分，n表示Pu,i或者Ru,i的數(shù)量。

3.3 結果與分析

為了驗證本文提出的基于用戶評分時間改進的協(xié)同過濾推薦算法的有效性，進行實驗對比。在MovieLens數(shù)據(jù)集上對改進的算法與傳統(tǒng)的基于項目的協(xié)同過濾推薦算法的推薦準確性進行了比較。MAE值隨不同的最近鄰數(shù)目的變化情況如圖1所示。

圖1 不同鄰居數(shù)目下ItemCF和改進算法的MAE對比Fig.1 MAE comparison of ItemCF and improved algorithm with different number of neighbors

從圖1中可以看出，結合評分時間特性改進的協(xié)同過濾推薦算法在最近鄰項目個數(shù)分別為10、20、30、40、50的MAE值均小于傳統(tǒng)的基于項目的協(xié)同過濾推薦算法。MAE值平均降低2%。由此可見，在相似度的計算中結合用戶的評分時間特性后推薦效果的準確性得到了提高。

4 結束語

本文針對傳統(tǒng)ItemCF算法沒有對評分的時間信息加以利用的不足，提出了結合評分時間特性的協(xié)同過濾推薦算法。該算法通過在相似度計算和評分預測中引入評分時間因子，從時間特性角度對用戶歷史評分的重要性加以區(qū)分，充分體現(xiàn)了評分時間特性對協(xié)同過濾推薦的重要影響。本文也通過實驗驗證了改進后的算法在提高推薦準確性方面的有效性。

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

[2] 曹一鳴. 協(xié)同過濾推薦瓶頸問題綜述[J]. 軟件, 2012, 12: 315-321.

[3] 蔡雄峰, 艾麗華, 丁丁. 一種緩解協(xié)同過濾算法數(shù)據(jù)稀疏性的方法[J]. 軟件, 2015, 03: 41-47.

[4] 劉青文. 基于協(xié)同過濾的推薦算法研究[D]. 北京: 中國科學技術大學, 2013.

[5] 顏龍杰. 基于近鄰評分預測的協(xié)同過濾推薦算法[J]. 軟件, 2013, 34(8): 63-66.

[6] 郭清菊, 周讓明, 馬俊濤. 基于學習興趣的個性化推薦算法研究[J]. 軟件, 2013, 34(9): 51-53.

[7] 李源鑫, 肖如良, 陳洪濤, 等. 時間衰減制導的協(xié)同過濾相似性計算[J]. 計算機應用系統(tǒng), 2013, 22 (11): 129-133.

[8] Zhu Min, Yao Shuzhen. A Collaborative Filtering Recommender Algorithm Based on the User Interest Model. Computational Science and Engineering(CSE), 2014 IEEE 17th International Conference on 19-21 Dec. 2014.

[9] 嚴冬梅, 魯城華. 基于用戶興趣度和特征的優(yōu)化協(xié)同過濾推薦[J]. 計算機應用研究, 2012, 29(2): 497-500.

[10] 吳月萍, 鄭建國. 改進相似性度量方法的協(xié)同過濾推薦算法[J]. 計算機應用與軟件, 2011, 28( 10) : 7-8, 42.

[11] 文俊浩, 舒珊. 一種改進相似性度量的協(xié)同過濾推薦算法[J]. 計算機科學, 2014, 41(5): 68-71.

A Collaborative Filtering Recommendation Algorithm in Combination with Rating Time Characteristic

LI Sheng-qiu, WU Wei-ming, GU Yong-hao
(School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China)

User rating is the main basis for cooperative recommendation algorithm to achieve the unknown score prediction. Traditional collaborative recommendation algorithm usually only use the score value while ignoring the effect of score generation time on recommendation. However the impact of scoring time characteristics on the accuracy of recommendation system can not be underestimated. In this paper, we propose a new collaborative filtering recommendation algorithm based on the traditional collaborative filtering recommendation algorithm, which improves the similarity calculation and the score forecasting process of the recommendation algorithm from the scoring time angle. The algorithm calculates a time factor based on the user’s score and time of the project, and integrates the time factor into the calculation of the similarity, which makes the recommendation to the target user more reasonable. The experiment is compared with the existing collaborative recommendation algorithm to verify the effectiveness of the algorithm in improving the recommendation accuracy.

Recommendation system; Collaborative filtering; Time weight; Rating prediction

TP391

A

10.3969/j.issn.1003-6970.2016.11.031

李圣秋(1993-)，男，碩士研究生，主要研究方向：現(xiàn)代網(wǎng)絡管理、移動互聯(lián)網(wǎng)；吳偉明，女，教授，主要研究方向：現(xiàn)代網(wǎng)絡管理、移動互聯(lián)網(wǎng)；谷勇浩，男，講師，主要研究方向：移動互聯(lián)網(wǎng)、網(wǎng)絡安全。

吳偉明，教授，主要研究方向：現(xiàn)代網(wǎng)絡管理、移動互聯(lián)網(wǎng)。