適應用戶興趣變化的改進型協(xié)同過濾算法

胡偉健 滕飛 李靈芳 王歡

摘要：協(xié)同過濾算法可以根據(jù)用戶的歷史行為記錄去預測其可能喜歡的物品，是現(xiàn)在業(yè)界應用極為廣泛的推薦算法。但傳統(tǒng)的協(xié)同過濾算法并沒有考慮到用戶興趣的概念漂移，在一些基于時間的協(xié)同過濾算法中對推薦時效性的考慮也有所欠缺。針對這些問題，結(jié)合用戶興趣隨時間轉(zhuǎn)移的特點，改進了相似度的度量方法，同時引入一種增強的時間衰減模型來度量預測值，并將這兩種方式有機地結(jié)合起來，解決了用戶興趣的概念漂移問題并考慮了推薦算法的時效性。仿真實驗中，分別在不同的數(shù)據(jù)集中對比了該算法與UserCF、TCNCF、PTCF以及TimeSVD++算法的預測評分準確度和TopN推薦準確度。實驗結(jié)果表明，改進算法能夠降低預測評分的均方根誤差（RMSE），并在TopN推薦準確度上均優(yōu)于對比算法。

關鍵詞：協(xié)同過濾；個性化推薦；用戶興趣；歐氏距離；時效性

中圖分類號：TP391.4；TP311

文獻標志碼：A

0引言

隨著大數(shù)據(jù)時代的來臨，我們已經(jīng)由原來的信息匱乏時代邁向了信息過載的時代。人們每天需要面臨海量的信息，面對這些海量信息，用戶需要根據(jù)其信息需求投入大量時間進行信息的過濾和選擇，產(chǎn)生信息過載問題[1]。為了解決信息過載給用戶帶來的困擾，學術(shù)界和業(yè)界進行了大量信息技術(shù)的創(chuàng)新和實踐，推薦系統(tǒng)正逐漸成為解決信息過載的主要發(fā)展方向[1]。推薦系統(tǒng)可以根據(jù)用戶的個體信息需求，為其提供個性化信息推薦，在海量信息空間中，以個性化的方式引導用戶獲得有用的信息對象[2]。如今，推薦系統(tǒng)已經(jīng)成功應用在諸如電子商務[3]、數(shù)字圖書館[4]、新聞[5]等諸多領域，并且取得了不錯的成果。

協(xié)同過濾（collaborative filtering）算法是應用最廣泛，同時也是發(fā)展比較成熟的一種推薦算法。協(xié)同過濾推薦算法由于其與推薦內(nèi)容的無關性，并可發(fā)現(xiàn)用戶的潛在信息需求等優(yōu)勢，已經(jīng)成為了推薦算法中最具發(fā)展前途的方向[6]。著名電子商務網(wǎng)站亞馬遜的個性化推薦系統(tǒng)有著"推薦系統(tǒng)之王"的美譽，其核心算法就是協(xié)同過濾算法。據(jù)悉，亞馬遜通過推薦系統(tǒng)，將其銷售額提升了30%[3]。傳統(tǒng)協(xié)同過濾算法沒有考慮用戶興趣的變化，造成了推薦準確性的下降。早期的協(xié)同過濾算法研究中，通常使用將時間作為加權(quán)項與相似度或者預測評分進行結(jié)合的方法解決用戶興趣變化的問題。任磊[7]提出了一種將評分時間因子與皮爾遜相關系數(shù)相結(jié)合的相似度計算方法來模擬用戶興趣變化；叢曉琪等[8]將一種時間加權(quán)函數(shù)融合到預測值的計算中，提高了推薦的準確度。上述算法沒有考慮產(chǎn)生推薦的當前時間，不能夠反映推薦產(chǎn)生時用戶的興趣變化，降低了推薦的時效性。

本文旨在解決用戶興趣變化問題，并提高推薦算法時效性，提出了一種適應用戶興趣變化的改進型協(xié)同過濾算法（Improved Collaborative Filtering recommendation algorithm incorporated with User Interest Change， ICFUIC）。主要從以下兩個方面對傳統(tǒng)協(xié)同過濾算法進行了改進：首先，提出了一種改進的歐氏距離相似度度量方法，在歐氏距離的計算中引入時間信息來模擬用戶的興趣變化；其次，在預測值計算時引入了一種增強的時間衰減模型，加入了推薦的當前時間，提高了推薦時效性。

1相關研究

1.1傳統(tǒng)協(xié)同過濾算法

協(xié)同過濾技術(shù)是推薦系統(tǒng)中應用最為成功的一種信息過濾技術(shù)[9]，主要利用與目標用戶相似的用戶行為（評分、點擊次數(shù)等）推斷目標用戶對特定產(chǎn)品的喜好程度，然后根據(jù)這種喜好進行相應的推薦[10]。算法輸入一般為用戶項目評分矩陣，輸出可以為用戶對項目的預測評分或推薦的項目列表。傳統(tǒng)的協(xié)同過濾算法又可以分為基于用戶的協(xié)同過濾（UserCF）算法和基于項目的協(xié)同過濾（ItemCF）算法。本文將以UserCF算法作為研究的基礎協(xié)同過濾算法。UserCF算法首先利用已有的用戶行為記錄計算出各用戶之間的相似程度，常用的計算用戶相似度的方法有皮爾遜相關系數(shù)方法（式（1））、歐氏距離相似度方法（式（2））、余弦相似度方法等；然后選取最相似的若干用戶組成最近鄰集合，并通過最近鄰集合中用戶行為記錄來對目標用戶可能的行為進行預測，預測函數(shù)如式（3）所示；最后根據(jù)預測產(chǎn)生推薦結(jié)果。

1.2基于時間的協(xié)同過濾算法

為了解決用戶興趣的概念漂移問題，文獻[11]中提出了一種時間加權(quán)協(xié)同過濾算法，即引入時間加權(quán)函數(shù)來改進相似度的計算，通過時間加權(quán)函數(shù)對用戶的相似度進行加權(quán)處理，評分時間較近的兩個物品權(quán)重更高；反之，權(quán)重越低。文獻[12]中通過引入了艾賓浩斯記憶曲線來模擬用戶興趣的變化，并將遺忘曲線進行擬合后的擬合函數(shù)作為時間加權(quán)函數(shù)引入到相似度度量中。文獻[13]中了將時間信息引入到奇異值分解（Singular Value Decomposition， SVD）方法中，提出了一種TimeSVD++算法，從而將時間信息加入到了用戶的特征向量中。文獻[14]中將時間作為第三個維度引入到算法中，并使用張量分解的方式模擬動態(tài)變化。以上文獻中的這些方法通過不同的形式將時間信息考慮進了推薦算法的計算過程中，從實驗結(jié)果來看，都在一定程度上提高了推薦的準確性。

與上述方法不同，本文通過將評分的相對時間信息引入歐氏距離中來計算相似度，并引入了一種增強型的時間衰減函數(shù)用來計算預測值，提出了一種適應用戶興趣變化的改進型協(xié)同過濾算法。

2適應用戶興趣變化的改進型協(xié)同過濾算法

2.1算法的提出

2.1.1改進的歐氏距離相似度方法

傳統(tǒng)的推薦算法中用歐氏距離度量相似度時采用了如式（2）中的方法。在信息建模的過程中，根據(jù)用戶對物品的評分建立一個用戶物品評分矩陣，即R（U，I），然后對矩陣通過式（2）中的方法計算用戶與用戶或者物品與物品之間的相似度。

改進的歐氏距離算法中在信息建模時不僅建立了用戶物品評分矩陣，而且建立了一個對應的評分時間矩陣T（U，I），記錄了用戶對物品產(chǎn)生評分的時間，矩陣T與矩陣R一一對應，若用戶未對該物品評分（以“—”表示），則矩陣中對應項為0即可。如用戶1對物品1的評分為3.0，評分時間為2015年11月1日；用戶2對物品1無評分；用戶2對物品2的評分為5.0，評分時間為2015年12月15日；用戶1對物品2的評分為4.0，評分時間為2015年10月3日。信息建模后可得出如下兩個矩陣（為方便數(shù)學計算，已經(jīng)將時間信息轉(zhuǎn)化為時間戳格式）：

2.1.3適應用戶興趣變化的改進型協(xié)同過濾算法

改進的歐氏距離算法不僅能夠解決皮爾遜相關系數(shù)在度量相似度上的不足，而且通過引入時間信息到歐氏距離的計算中，考慮了歷史行為記錄的相對時間，從而能夠得到用戶之間更加真實、準確的相似度；將增強的衰減函數(shù)加入到預測值的計算中，引入了推薦的當前時間，使得推薦的結(jié)果更接近于用戶的當前興趣，提高了推薦時效性。因此，改進算法ICFUIC將兩種方式有機結(jié)合起來，利用改進的歐氏距離算法來度量相似度，利用引入了增強的時間衰減函數(shù)的預測值計算方法來度量預測值，形成了一種更加全面的、能夠更好適應用戶興趣變化的改進型協(xié)同過濾算法。

2.2算法過程描述

根據(jù)協(xié)同過濾算法的基本原則與式（4）～（10），可以總結(jié)出適應用戶興趣變化的改進型協(xié)同過濾算法（ICFUIC）過程如下：

3實驗數(shù)據(jù)與結(jié)果分析

3.1實驗數(shù)據(jù)集

為了比較時間因素對推薦結(jié)果產(chǎn)生的影響，實驗數(shù)據(jù)集中應該包含有評分信息以及產(chǎn)生評分的時間信息，因此，實驗中選擇了以下兩個數(shù)據(jù)集對算法進行驗證：1）美國Minnesota大學提供的最新電影數(shù)據(jù)集MovieLens Latest Datasets；2）HP/Compad的DEC（Digital Equipment Corporation）研究中心提供的EachMovie數(shù)據(jù)集（由于實驗機器硬件資源有限，采用隨機抽樣的方法從中抽取了部分數(shù)據(jù)）。

3.2實驗結(jié)果度量標準

本文主要從評分預測和TopN推薦這兩個方面來度量推薦算法的準確度。對于評分預測采用了均方根誤差（Root Mean Square Error， RMSE）。RMSE通過計算預測值與實際值之間的偏差來衡量推薦質(zhì)量，其得到的值越小，說明推薦算法的準確性越高，反之亦然。對于TopN推薦采用了F1-Measure指標，F(xiàn)1-Measure是由準確率（precision）和召回率（recall）共同計算得出，其得到的值越大，說明推薦算法的準確性越高，反之亦然。

3.3比較算法及參數(shù)設定

本文選擇了改進算法ICFUIC與前文介紹的傳統(tǒng)UserCF算法[9]、TCNCF算法[11]、PTCF算法[8]和TimeSVD++算法[13]進行對比。

在實驗中，為了保證實驗的準確性與可行性，將數(shù)據(jù)集隨機劃分為訓練集與測試集，其中訓練集為原數(shù)據(jù)集的80%，測試集為原數(shù)據(jù)集的20%。同時設置了兩組對比實驗：實驗1主要驗證算法的預測評分準確度；實驗2主要驗證TopN準確度。實驗1中，為了驗證各個算法在不同鄰居數(shù)下的表現(xiàn)，鄰居數(shù)設置為10～35，步長為5；由于TimeSVD++算法與鄰居數(shù)無關，因此實驗1中選擇了特征數(shù)為10時，TimeSVD++算法的RMSE值。實驗2選取用戶的鄰居數(shù)為20，觀察了推薦數(shù)目K從10～35每次增加5時，各個推薦算法的性能。

3.4實驗結(jié)果分析

實驗1預測評分準確度比較。

圖1中給出了D1、D2數(shù)據(jù)集下不同鄰居數(shù)時五個對比算法對應的RMSE值比較結(jié)果，從中可以看出：

1）隨著鄰居數(shù)的不斷增加，各個算法的預測評分準確度整體上在不斷地提高并趨于穩(wěn)定。

2）TCNCF與PTCF在數(shù)據(jù)集D1上比UserCF預測評分準確度都有了提高，主要是因為考慮了時間問題，可見用戶興趣變化對推薦準確性的影響；但在數(shù)據(jù)集D2上其準確度并不優(yōu)于UserCF，說明改進算法的通用性上還存在不足。

3）ICFUIC在數(shù)據(jù)集D1和D2上，其預測評分的準確度均明顯優(yōu)于傳統(tǒng)UserCF算法、TCNCF和PTCF，說明本文提出的改進方法能夠更好地模擬用戶興趣變化，有效提高推薦的預測評分準確度。

4）TimeSVD++在D1、D2數(shù)據(jù)集下預測評分準確度均高于其他四種協(xié)同過濾算法，這主要是由于TimeSVD++采用了奇異值分解的方法進行推薦，該方法通過將評分矩陣進行分解提煉出潛在維度數(shù)（特征值），從而簡化了數(shù)據(jù)，去除了噪聲，可以更準確地計算用戶間相似度；但特征值的選取具有不確定性，且分解后的向量具有不可解釋性，同時在大規(guī)模稠密矩陣上進行分解時，算法的時間開銷巨大，這些問題也限制了該方法在實際中的應用。

從表2的實驗結(jié)果可以得出：

1）隨著推薦數(shù)目不斷增加，各個算法的TopN準確度都在不斷提高。

2）結(jié)合實驗1，TCNCF和PTCF雖然在數(shù)據(jù)集D1上的預測評分準確度比UserCF有了提高，但在TopN準確度的度量上，其F1-Measure低于UserCF，說明其改進方法仍然存在一定的缺陷與不足。

3）ICFUIC的F1-Measure值均明顯高于UserCF、TCNCF和PTCF，說明ICFUIC在TopN準確度上較UserCF、TCNCF、PTCF也有了明顯的提高；同時雖然TimeSVD++在預測評分準確度上優(yōu)于ICFUIC，但是ICFUIC具有更高的TopN推薦準確度。

實驗1與實驗2中通過將五種算法的預測評分準確度和TopN準確度進行對比，可以發(fā)現(xiàn)本文提出的ICFUIC在預測評分準確度均優(yōu)于同類型的傳統(tǒng)算法與改進算法；同時在TopN準確度上均優(yōu)于其他四種算法。因此，可以說ICFUIC在推薦準確度上有了明顯的提高。

4結(jié)語

通過對協(xié)同過濾算法的研究與分析，傳統(tǒng)算法中未考慮用戶興趣的概念漂移問題，在推薦準確度與時效性方面表現(xiàn)不佳。本文針對此不足之處，提出了一種適應用戶興趣變化的改進型協(xié)同過濾算法。算法在度量相似度時為了避免皮爾遜相關系數(shù)方法在數(shù)據(jù)稀疏時無法計算相似度的問題從而采用了歐氏距離來計算相似度，并且將時間因素引入到傳統(tǒng)的歐氏距離的計算中，在一定程度上解決了用戶興趣的概念漂移問題。同時，又通過將增強的時間衰減模型引入到預測值的計算中來更好地解決推薦的時效性問題。最后將對相似度的改進計算方法與預測值的改進計算方法有機地結(jié)合起來。實驗結(jié)果表明改進后的算法在推薦算法的準確度上有了明顯的提高。

本文算法仍存在以下兩個不足之處：1）對用戶的相似度進行計算時，由于又新構(gòu)建了評分時間矩陣，因此加大了對內(nèi)存的開銷，增加了計算的時間；2）實驗中數(shù)據(jù)集來自于電影領域，因此在算法的應用場合上有一定的局限性。在接下來的工作中，主要針對上面提到的兩點不足進行改進，嘗試將相似度模型進行優(yōu)化，以減少內(nèi)存開銷與計算時間；將算法運用到其他的應用場合中，來驗證算法的有效性。

參考文獻：

[1]RESNICK P， IACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// CSCW94： Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work. New York： ACM， 1994： 175-186.

[2]ADOMAVICIUS G， TUZHILIN A. Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge & Data Engineering， 2005， 17（6）：734-749.

[3]SCHAFER J B， KONSTAN J， RIEDL J. Recommender systems in E-commerce [C]// EC99： Proceedings of the 1st ACM Conference on Electronic Commerce. New York： ACM， 1999： 158-166.

[4]JAYAWARDANA C， HEWAGAMAGE K P， HIRAKAWA M. A personalized information environment for digital libraries [J]. Information Technology & Libraries， 2001， 20（4）：185-196.

[5]KONSTAN J A， MILLER B N， MALTZ D， et al. GroupLens： applying collaborative filtering to Usenet news [J]. Communications of the ACM， 2000， 40（3）： 77-87.

[6]鄭先榮，曹先彬. 線性逐步遺忘協(xié)同過濾算法的研究[J].計算機工程，2007，33（6）：72-73. （ZHENG X R， CAO X B. Research on lineal gradual forgetting collaborative filtering algorithm [J]. Computer Engineering， 2007， 33（6）： 72-74.）

[7]任磊.一種結(jié)合評分時間特性的協(xié)同推薦算法[J].計算機應用與軟件，2015，32（5）：112-115. （REN L. A collaborative recommendation algorithm in combination with rating time characteristic[J]. Computer Applications and Software， 2015， 32（5）： 112-115.）

[8]叢曉琪，楊懷珍，劉枚蓮.基于時間加權(quán)的協(xié)同過濾算法研究[J].計算機應用與軟件，2009，26（8）：120-121. （CONG X Q， YANG H Z， LIU M L. On collaborative filtering algorithm based on time weight [J]. Computer Applications and Software， 2009， 26（8）： 120-121.）

[9]OWEN S， ANIL R， DUNNING T， et al. Mahout in Action [M]. Greenwich， CT： Manning Publications， 2011： 34-47.

[10]許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報，2009，20（2）：350-362. （XU H L， WU X， LI X D， et al. Comparison study of Internet recommendation system [J]. Journal of Software， 2009， 20（2）： 350-362.）

[11]李佳，陳亞軍.基于時間和共同評分項目數(shù)的協(xié)同過濾算法研究[J].軟件導刊，2015，14（7）：61-63. （LI J，CHEN Y J. A filtering algorithm research based on time and the number of common grading[J]. Software Guide， 2015， 14（7）： 61-63.）

[12]孫光輝.基于時間效應和用戶興趣變化的改進推薦算法研究[D].北京：北京郵電大學，2014：10-19. （SUN G H. Research of improved recommendation algorithm based on time effect and changes in users interest [D]. Beijing： Beijing University of Posts and Telecommunications， 2014： 10-19.）

[13]KOREN Y. Collaborative filtering with temporal dynamics [J]. Communications of the ACM， 2010， 53（4）： 89-97.

KDD 09： Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009： 447-456.【

[14]XIONG L， CHEN X， HUANG T K， et al. Temporal collaborative filtering with bayesian probabilistic tensor factorization [C]// SDM 2000： Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2010： 211-222.

[15]FAN X， HU Y， ZHANG R， et al. Modeling temporal effectiveness for context-aware Web services recommendation [C]// ICWS 2015： Proceedings of the 2015 IEEE International Conference on Web Services. Washington， DC： IEEE Computer Society， 2015： 225-232.

[16]范家兵，王鵬，周渭博，等.在推薦系統(tǒng)中利用時間因素的方法[J]. 計算機應用，2015，35（5）：1324-1327. （FAN J B， WANG P， ZHOU W B， et al. Method by using time factors in recommender system[J]. Journal of Computer Applications， 2015， 35（5）： 1324-1327.）

[17]項亮. 推薦系統(tǒng)實踐[M].北京：人民郵電出版社，2012：35-77. （XIANG L. Recommended System Practice [M]. Beijing： Posts and Telecom Press， 2012： 35-77.）

[18]王嵐，翟正軍.基于時間加權(quán)的協(xié)同過濾算法[J]. 計算機應用，2007，27（9）：2302-2303. （WANG L， ZHAI Z J. Collaborative filtering algorithm based on time weight [J]. Journal of Computer Applications， 2007， 27（9）： 2302-2303.）