胡偉健 滕飛 李靈芳 王歡

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

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

中圖分類號：TP391.4；TP311

文獻(xiàn)標(biāo)志碼：A

0引言

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

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

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

1相關(guān)研究

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

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

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

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

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

2適應(yīng)用戶興趣變化的改進(jìn)型協(xié)同過濾算法

2.1算法的提出

2.1.1改進(jìn)的歐氏距離相似度方法

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

改進(jìn)的歐氏距離算法中在信息建模時不僅建立了用戶物品評分矩陣，而且建立了一個對應(yīng)的評分時間矩陣T（U，I），記錄了用戶對物品產(chǎn)生評分的時間，矩陣T與矩陣R一一對應(yīng)，若用戶未對該物品評分（以“—”表示），則矩陣中對應(yīng)項為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ù)學(xué)計算，已經(jīng)將時間信息轉(zhuǎn)化為時間戳格式）：

2.1.3適應(yīng)用戶興趣變化的改進(jìn)型協(xié)同過濾算法

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

2.2算法過程描述

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

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

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

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

3.2實驗結(jié)果度量標(biāo)準(zhǔn)

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

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

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

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

3.4實驗結(jié)果分析

實驗1預(yù)測評分準(zhǔn)確度比較。

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

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

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

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

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

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

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

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

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

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

4結(jié)語

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

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

參考文獻(xiàn)：

[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].計算機應(yīng)用與軟件，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].計算機應(yīng)用與軟件，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].軟件學(xué)報，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].軟件導(dǎo)刊，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]孫光輝.基于時間效應(yīng)和用戶興趣變化的改進(jìn)推薦算法研究[D].北京：北京郵電大學(xué)，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]. 計算機應(yīng)用，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]. 計算機應(yīng)用，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.）