李圣秋，吳偉明，谷勇浩

（北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京市 100876）

一種結(jié)合評(píng)分時(shí)間特性的協(xié)同過(guò)濾推薦算法

李圣秋，吳偉明，谷勇浩

（北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京市 100876）

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

推薦系統(tǒng)；協(xié)同過(guò)濾；時(shí)間權(quán)重；評(píng)分預(yù)測(cè)

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

0 引言

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

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

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

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

協(xié)同過(guò)濾算法根據(jù)用戶的歷史評(píng)分?jǐn)?shù)據(jù)進(jìn)行推薦，一般來(lái)說(shuō)分為基于用戶的協(xié)同過(guò)濾（User Based Collaborative Filtering，UserCF）和基于項(xiàng)目的協(xié)同過(guò)濾（Item Based Collaborative Filtering，ItemCF）。

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

鑒于ItemCF的性能優(yōu)勢(shì)，其在學(xué)術(shù)和實(shí)際應(yīng)用中得到了大量研究和實(shí)踐，本文的研究?jī)?nèi)容將以ItemCF作為基準(zhǔn)協(xié)同過(guò)濾推薦算法。

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

1）計(jì)算物品之間的相似度；

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

具體的過(guò)程是首選需要獲取用戶代理捕獲并記錄用戶對(duì)已訪問(wèn)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)，并以用戶描述向量形式表示用戶興趣，所有用戶描述向量按行構(gòu)造為用戶-項(xiàng)目評(píng)分矩陣；根據(jù)用戶-項(xiàng)目評(píng)分矩陣，采用特定的相似性度量標(biāo)準(zhǔn)，計(jì)算不同項(xiàng)目之間的相似度；參考項(xiàng)目間相似度計(jì)算的結(jié)果，確定與目標(biāo)項(xiàng)目相似的鄰居項(xiàng)目；針對(duì)目標(biāo)用戶的每一未評(píng)分目標(biāo)項(xiàng)目，根據(jù)其鄰居項(xiàng)目的評(píng)分，以鄰居項(xiàng)目與目標(biāo)項(xiàng)目的相似度為權(quán)重，對(duì)鄰居項(xiàng)目評(píng)分進(jìn)行加權(quán)求和預(yù)測(cè)用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分；依據(jù)對(duì)目標(biāo)項(xiàng)目所預(yù)測(cè)的評(píng)分值大小，對(duì)目標(biāo)用戶的所有未評(píng)分項(xiàng)目進(jìn)行降序排序，進(jìn)而選擇Top-N項(xiàng)目構(gòu)成推薦列表，并主動(dòng)推薦給目標(biāo)用戶。

一個(gè)m*n的用戶－項(xiàng)目評(píng)分矩陣Rm*n，見(jiàn)表1。

表1 用戶-項(xiàng)目評(píng)分矩陣示例Tab.1 An Example of User-Item Rating Matrix

其中，Useri表示第i個(gè)用戶，Itemj表示第j個(gè)項(xiàng)目，Rateij表示第i個(gè)用戶對(duì)第j個(gè)項(xiàng)目的評(píng)分，總共有m個(gè)用戶n個(gè)項(xiàng)目。

為了確定目標(biāo)項(xiàng)目的鄰居項(xiàng)目，ItemCF通過(guò)一定的相似度來(lái)度量項(xiàng)目間的相似性，常用的相似度計(jì)算方法有夾角余弦相似度和皮爾遜相關(guān)系數(shù)，鑒于皮爾遜相關(guān)系數(shù)不受評(píng)分分布的影響，其在實(shí)際應(yīng)用中使用更為廣泛[6]，故本文采用皮爾遜相關(guān)系數(shù)計(jì)算項(xiàng)目間的相似度。

對(duì)于兩個(gè)項(xiàng)目Itemi與Itemj，其皮爾遜相關(guān)系數(shù)sim(i,j)可表示為：

其中Uij指的是Itemi與Itemj的公共評(píng)分用戶集，和分別表示Itemi與Itemj的平均評(píng)分值。在得到項(xiàng)目之間的相似度后，ItemCF通過(guò)如下公式計(jì)算用戶ui對(duì)一個(gè)項(xiàng)目sj的興趣：

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

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

2 改進(jìn)算法

2.1 時(shí)間效應(yīng)

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

2.2 評(píng)分時(shí)間因子

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

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

2.3 ItemCF算法集成評(píng)分時(shí)間因子

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

改進(jìn)后算法的流程如下：

輸入：

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

項(xiàng)目集合S={sj|1≤j≤n}

用戶-項(xiàng)目評(píng)分矩陣Rm*n

輸出：

目標(biāo)用戶u的Top-N項(xiàng)目推薦列表

Step1：根據(jù)用戶-項(xiàng)目評(píng)分矩陣R利用公式（3）計(jì)算評(píng)分rij對(duì)應(yīng)的評(píng)分時(shí)間因子wij；

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

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

Step4：根據(jù)公式（5）預(yù)測(cè)用戶ui對(duì)項(xiàng)目sj的評(píng)分pij

Step5：將步驟4中項(xiàng)目的預(yù)測(cè)評(píng)分按照降序從大到小的排列，最后選擇排在最前面評(píng)分最高的前n個(gè)項(xiàng)目推薦給用戶u。

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

3.2 檢驗(yàn)指標(biāo)

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

薦質(zhì)量[11]。MAE 通過(guò)計(jì)算實(shí)際評(píng)分與預(yù)測(cè)評(píng)分之間的差值來(lái)衡量算法的好壞。MAE值越小說(shuō)明該算法就越好。MAE值的計(jì)算如公式（6）所示。

其中，Pu,i表示用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，Ru,i表示用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分，n表示Pu,i或者Ru,i的數(shù)量。

3.3 結(jié)果與分析

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

[7] 李源鑫, 肖如良, 陳洪濤, 等. 時(shí)間衰減制導(dǎo)的協(xié)同過(guò)濾相似性計(jì)算[J]. 計(jì)算機(jī)應(yīng)用系統(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án)冬梅, 魯城華. 基于用戶興趣度和特征的優(yōu)化協(xié)同過(guò)濾推薦[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(2): 497-500.

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

[11] 文俊浩, 舒珊. 一種改進(jìn)相似性度量的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)科學(xué), 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)絡(luò)管理、移動(dòng)互聯(lián)網(wǎng)；吳偉明，女，教授，主要研究方向：現(xiàn)代網(wǎng)絡(luò)管理、移動(dòng)互聯(lián)網(wǎng)；谷勇浩，男，講師，主要研究方向：移動(dòng)互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全。

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