基于動態(tài)時間的個性化推薦模型

譚黎立， 聶瑞華*， 梁 軍， 王進(jìn)宏

(1.華南師范大學(xué)計算機(jī)學(xué)院，廣州 510631；2. 華南師范大學(xué)網(wǎng)絡(luò)中心，廣州 510631；3. 北明軟件有限公司，廣州 510663)

基于動態(tài)時間的個性化推薦模型

譚黎立1， 聶瑞華1*， 梁 軍2， 王進(jìn)宏3

(1.華南師范大學(xué)計算機(jī)學(xué)院，廣州 510631；2. 華南師范大學(xué)網(wǎng)絡(luò)中心，廣州 510631；3. 北明軟件有限公司，廣州 510663)

在推薦系統(tǒng)中，往往會存在數(shù)據(jù)的非實(shí)時性、稀疏性和冷啟動性等問題，文中通過引入遺忘曲線來跟蹤用戶對資源偏好程度隨時間變化情況，提出一種改進(jìn)的K-Means聚類算法對用戶集進(jìn)行聚類，根據(jù)改進(jìn)的個性化推薦算法對用戶進(jìn)行推薦，建立了一種基于動態(tài)時間的個性化推薦模型. 通過實(shí)驗驗證，該個性化推薦模型能夠獲取準(zhǔn)確的用戶偏好信息，并緩解冷啟動問題，降低算法計算的時間空間復(fù)雜度，提高個性化推薦算法的推薦質(zhì)量.

個性化； 遺忘曲線；K-Means； 物質(zhì)擴(kuò)散； 熱傳導(dǎo)

個性化推薦技術(shù)是在20世紀(jì)90年代提出的，一直保持著較高的研究熱度[1]. 如人工智能、數(shù)據(jù)挖掘和大數(shù)據(jù)等各個研究領(lǐng)域相關(guān)技術(shù)為其提供相關(guān)服務(wù)與支持[2]. 個性化推薦技術(shù)是為了解決信息過載問題而發(fā)展出來的一門科學(xué)技術(shù)[3]，而基于協(xié)同過濾推薦技術(shù)(Collaborative Filtering Recommendations, 簡稱CF)是運(yùn)用最廣的個性化推薦技術(shù)[4]. 面對“大數(shù)據(jù)”時代，個性化推薦系統(tǒng)可以在海量的信息中，準(zhǔn)確預(yù)測出用戶的個性化潛在偏好，但也面臨著數(shù)據(jù)的稀疏性[5]、冷啟動性[6]和推薦效果不佳等問題.

學(xué)者們就這些問題紛紛提出了相應(yīng)的改進(jìn)算法，如：概率擴(kuò)展和熱力傳導(dǎo)的混合推薦算法，解決了在推薦效果上的準(zhǔn)確性和多樣性[7]；基于順序的推薦模型，分析用戶訪問項目的順序，以發(fā)現(xiàn)用戶的潛在感興趣的產(chǎn)品[8]；構(gòu)建特征層次模型，不僅可以通過時間序列分析來預(yù)測用戶偏好，而且可以很好解決數(shù)據(jù)冷啟動問題[9]；根據(jù)用戶的偏好記錄信息構(gòu)造社會關(guān)系網(wǎng)絡(luò)圖，猜想與新用戶之間的社會關(guān)系信息，并通過計算相似度，預(yù)測新用戶可能感興趣的項目，解決偏好矩陣的稀疏性問題[10]；利用數(shù)據(jù)挖掘相關(guān)算法來分析用戶行為信息，并分類處理，預(yù)測用戶的行為特征，為用戶推薦相關(guān)資源[11].

本文就構(gòu)建動態(tài)用戶偏好模型、降低數(shù)據(jù)復(fù)雜度和提高推薦算法的推薦效率等方面進(jìn)行深入研究，提出了一種基于動態(tài)時間的個性化推薦模型，旨在應(yīng)對個性化推薦系統(tǒng)面臨的挑戰(zhàn).

1 一種基于動態(tài)時間的推薦模型

本文提出了一種基于動態(tài)時間的個性化推薦模型(HH-CF)，能夠有效地提高其推薦質(zhì)量，降低計算的時間復(fù)雜度(圖1). 主要改進(jìn)點(diǎn)為引入遺忘曲線對用戶偏好進(jìn)行處理、對用戶集進(jìn)行聚類處理和對預(yù)測評分值進(jìn)行優(yōu)化調(diào)整.

圖1 基于動態(tài)時間的個性化推薦模型

Figure 1 The personalized recommendation model based on dynamic time

1.1 基于遺忘規(guī)律的改進(jìn)

用戶在不同時間段有不同需求，在傳統(tǒng)推薦系統(tǒng)中，很難獲取用戶當(dāng)前準(zhǔn)確的潛在偏好信息，因此，本文引入遺忘曲線調(diào)整用戶偏好信息. 人的記憶變化情況是：記憶量隨時間呈非均勻的減少，下降速率逐漸減少[12]. 通過大量實(shí)驗對遺忘曲線進(jìn)行擬合計算，得到如下公式：

ri,j=r0+r1e(t-t0

(1)

其中，t表示當(dāng)前時間，ri，j表示在t時第i用戶ui對第i資源resj的偏好值(當(dāng)由式(1)計算ri,j>5時，我們默認(rèn)ri,j5)，r0表示ui在t的最小偏好值，r1表示在t0時ui對resj的偏好值，表示ui對resj的遺忘因子，T表示該計算公式的有效時間.

最小偏好r0用于調(diào)整用戶對資源的偏好. 例如，當(dāng)該資源剛上線，或當(dāng)前為熱銷時期，系統(tǒng)把其設(shè)置為更大值. 動態(tài)調(diào)整r0，可以解決資源的冷啟動性問題. 本文采用一維向量的方式來表示：r0=[r1,r2,r3,…,rn].

1.2 基于聚類算法的改進(jìn)

本文提出了一種改進(jìn)的K-Means算法來緩解數(shù)據(jù)稀疏性和高維度問題. 通過減少干擾用戶量，降低數(shù)據(jù)維度和緩解數(shù)據(jù)稀疏性.

用戶集合U={u1,u2,…,um}，其中ui=(ri1,ri2,…,rin)，K-Means主要把數(shù)據(jù)集分解為k個相似用戶簇(k

K-Means計算流程：

步驟1：在U中選出k個用戶作為簇中心，表示為C={C1,C2,…,Ck}，其中Cj=(cj1,cj2,…,cjn).

步驟2：遍歷U，利用歐式距離計算用戶與簇中心的距離：

將每個用戶劃分到最近簇內(nèi).

步驟3：計算簇的均值點(diǎn)，把其替換成新的簇中心. 例如，簇Si={u1,u2,…,ua}，ui=(ri1,ri2,…,rin)，求取簇新中心Cj：

步驟4：重復(fù)步驟2、3，直到聚類結(jié)果不再變化.

判定目標(biāo)函數(shù)是否不再變化作為結(jié)束標(biāo)志. 目標(biāo)函數(shù)定義為：

由K-Means算法計算可以得到k個用戶簇，每個簇表示具有相似偏好的用戶集合.

改進(jìn)的K-Means算法的具體計算流程如下：

(1)對U={u1,u2,…,um}，隨機(jī)選取一個用戶作為初始簇中心C1，加入C={C1};

(2)以C1為起點(diǎn)，分別計算得出離C1距離最大的用戶，得到C2，加入C={C1,C2};

(3)以C1、C2為目標(biāo)點(diǎn)，計算得到C3距離兩點(diǎn)最大，C={C1,C2,C3};

(4)循環(huán)K次，以C={C1,C2,…,Cj}為目標(biāo)點(diǎn)，計算得到Cj+1距離C集合最大，加入C={C1,C2,…,Cj+1}.

計算距離最大值公式為：

(2)

其中，

式(2)使用了乘積計算方式，可以有效解決中心點(diǎn)集和其他簇中心相鄰近的干擾問題. 如使用加法方式計算，特殊情況時則不能保證簇中心是分離的狀態(tài). 1.3 基于推薦算法的改進(jìn)

考慮到推薦算法推薦效率不佳與多樣性等問題，提出了改進(jìn)的推薦模型，如圖2所示.

圖2 HH-CF模型Figure 2 HH-CF model

1.3.1 引入算法 基于用戶協(xié)同推薦算法User-CF的計算流程[13-15]如下：

(1)根據(jù)系統(tǒng)中已有的用戶信息、資源信息和用戶歷史偏好信息等數(shù)據(jù)，生成用戶偏好矩陣;

(2)根據(jù)用戶偏好矩陣計算用戶間的相似度，查找出與目標(biāo)用戶相似的用戶集;

(3)根據(jù)相似用戶的偏好，利用推薦算法計算用戶對未評分資源進(jìn)行預(yù)測評分，向用戶推送top-N個資源.

物質(zhì)擴(kuò)散算法、熱傳導(dǎo)算法分別根據(jù)下式計算得出：

(3)

(4)

其中，k(resc)為網(wǎng)絡(luò)拓?fù)鋱D中resc的度，k(ui)為網(wǎng)絡(luò)拓?fù)鋱D中ui的度，eijE，r(resc)表示resc的初始值，W(resi)表示resi的權(quán)重值，R(resi)表示resi的權(quán)重值，通過排名對資源進(jìn)行推送.

由式(3)可知，資源節(jié)點(diǎn)度越大，其值越大,因此，物質(zhì)擴(kuò)散算法更偏向推薦熱門的資源對象；由式(4)可知資源節(jié)點(diǎn)度越小，其值越大，因此，熱傳導(dǎo)算法更偏向推薦冷門資源對象.

1.3.2 改進(jìn)的推薦模型 改進(jìn)的推薦模型(圖3)加入MD算法和HS算法，可以增加用戶推薦流行和冷門資源對象的概率，提高推薦效率和多樣性. 具體流程如下：

步驟1：根據(jù)數(shù)據(jù)集構(gòu)造網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，用二分圖來表示，并設(shè)置初始的資源評分集合R向量.

步驟2：根據(jù)物質(zhì)擴(kuò)散和熱傳導(dǎo)算法計算對應(yīng)的權(quán)重值W(i)和R(i)，計算資源的調(diào)優(yōu)權(quán)重值S(i).

S(i)=,

(5)

步驟3：根據(jù)步驟2得到的調(diào)優(yōu)權(quán)重值來優(yōu)化調(diào)整推薦算法得到的預(yù)測值：

(6)

其中，KMCF(u,i)表示引入K-Means算法改進(jìn)的User-CF算法進(jìn)行計算得到的用戶評分預(yù)測值，δ為權(quán)重因子，實(shí)驗不斷擬合計算，找到使算法推薦效果最優(yōu)的δ.

步驟4：對預(yù)測值R(u,i)進(jìn)行排序，為用戶推送top-N個資源集合.

2 算法驗證與結(jié)果分析

本節(jié)主要介紹實(shí)驗數(shù)據(jù)集、實(shí)驗評價標(biāo)準(zhǔn)和實(shí)驗設(shè)計過程，最后給出對比實(shí)驗、分析實(shí)驗結(jié)果、得出實(shí)驗結(jié)論.

2.1 數(shù)據(jù)集與評價標(biāo)準(zhǔn)

2.1.1 實(shí)驗數(shù)據(jù)集 本實(shí)驗采用標(biāo)準(zhǔn)的電影評分?jǐn)?shù)據(jù)集MovieLens和豆瓣電影評分大規(guī)模數(shù)據(jù)集，數(shù)據(jù)集劃分70%為訓(xùn)練集、30%為測試集，衡量推薦精度的指標(biāo)采用F評價指標(biāo). 數(shù)據(jù)集詳細(xì)介紹見表1.

表1 數(shù)據(jù)集Table1 Data sets

2.1.2 評價標(biāo)準(zhǔn) 本實(shí)驗采用F值為評價標(biāo)準(zhǔn). 評價標(biāo)準(zhǔn)精準(zhǔn)率(precision)、召回率(recall)和F值計算公式如下：

其中，A表示有效的推薦結(jié)果，B表示未被推薦的相關(guān)文檔，C表示無效的推薦結(jié)果.

2.2 算法推薦效果比較

該實(shí)驗數(shù)據(jù)集采用0.1 K規(guī)模大小的MovieLens數(shù)據(jù)集. 通過借助基于用戶的協(xié)同過濾推薦算法(User-CF)進(jìn)行以下4組有效實(shí)驗，分別驗證本文提出的改進(jìn)模型的有效性，算法模型中的其他參數(shù)值均設(shè)置為使算法模型達(dá)到效果最優(yōu)時的相應(yīng)值.

圖3 遺忘因子比較Figure 3 Comparison of forgetting factor

實(shí)驗2：分別設(shè)置聚類簇個數(shù)k=5、k=8和k=10，比較通過K-Means聚類后進(jìn)行User-CF算法的推薦效果，實(shí)驗結(jié)果見圖4.

圖4 聚類簇數(shù)比較Figure 4 Comparison of cluster number

實(shí)驗3：分別設(shè)置權(quán)重因子δ=0.7、δ=0.8和δ=0.9，比較HH-CF算法推薦效果，實(shí)驗結(jié)果見圖5.

圖5 權(quán)重因子比較Figure 5 Comparison of weight factor

實(shí)驗4：實(shí)驗參數(shù)設(shè)置最優(yōu)時，比較HH-CF與User-CF算法的推薦效果，實(shí)驗結(jié)果見圖6.

圖6 算法效果比較Figure 6 Comparison of algorithm performance

從實(shí)驗結(jié)果可以得到以下結(jié)論：

(1)最近鄰用戶越多，算法的推薦效率越好.

(3)在設(shè)置參數(shù)使算法效果最佳時，該模型得到的推薦效率優(yōu)于傳統(tǒng)推薦算法.

通過上述實(shí)驗結(jié)果驗證，在本文實(shí)驗環(huán)境下，基于動態(tài)時間的個性化推薦模型(HH-CF)優(yōu)于傳統(tǒng)推薦算法.

2.3 算法性能比較

該實(shí)驗主要用于比較本文提出的算法模型計算時間性能的大小. 利用2組大小規(guī)模不同的數(shù)據(jù)集，比較HH-CF和User-CF算法為用戶進(jìn)行推薦需要的平均時間.

由圖7可知基于動態(tài)時間的個性化推薦模型(HH-CF)比傳統(tǒng)User-CF算法時間性能更好，極大地降低計算復(fù)雜度，進(jìn)行推薦計算時，可以減少計算花費(fèi)的時間. 在大規(guī)模的數(shù)據(jù)集中，能夠更加明顯地減少推薦算法計算的時間，極大地解決用戶個性化體驗問題.

圖7 不同數(shù)據(jù)集的時間效率比較Figure 7 Comparison of time efficiency of different data sets

2.4 實(shí)驗總結(jié)

本文實(shí)驗對HH-CF算法模型進(jìn)行有效地驗證，分別比較參數(shù)為何值時，HH-CF算法的推薦質(zhì)量最好. 并在不同數(shù)據(jù)集下比較算法的時間性能，驗證了HH-CF算法的有效性. 因此，本文提出的基于動態(tài)時間的個性化推薦模型能夠有效地減少計算的復(fù)雜度、降低數(shù)據(jù)維度和提高推薦算法的質(zhì)量.

3 總結(jié)

本文深入研究了個性化推薦算法，提出一種基于動態(tài)時間的個性化推薦模型，并通過實(shí)驗證明其推薦效果明顯優(yōu)于傳統(tǒng)推薦算法. 該模型是通過引入遺忘曲線來獲取準(zhǔn)確的用戶偏好信息，然后利用改進(jìn)的K-Means對用戶聚類，降低推薦算法計算的空間維度，最后根據(jù)改進(jìn)的推薦算法來實(shí)現(xiàn)個性化推薦.

但是，面對當(dāng)前時代的要求，其個性化推薦系統(tǒng)還有一些需要亟待解決的問題：

(1)實(shí)時有效推薦. 在大數(shù)據(jù)時代，需要處理海量化的數(shù)據(jù)，需要準(zhǔn)確快捷地為用戶提供服務(wù).

(2)多樣化推薦. 由于用戶的潛在需求越來越大，推薦系統(tǒng)需要提供更多用戶可能感興趣的資源集合，才能滿足用戶的需求.

[1] CHEN L. Personality in recommender systems[C]∥Proceedings of the 3rd Workshop on Emotions and Personality in Personalized Systems. New Yord:ACM,2015:16-20.

[2] NUNES M A S N,HU R. Personality-based recommender systems:an overview[C]∥Proceedings of the Sixth ACM Conference on Recommender Systems. New York:ACM,2012:5-6.

[3] 于洪,李俊華. 一種解決新項目冷啟動問題的推薦算法[J]. 軟件學(xué)報,2015,26(6):1395-1408.

YU H,LI J H. Algorithm to solve the cold-start problem in new item recommendations[J]. Journal of Software,2015,26(6):1395-1408.

[4] KOREN Y. Collaborative filtering with temporal dynamics[C]∥Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New Yord:ACM,2009:447-456.

[5] JONNALAGEDDA N,GAUCH S. Personalized news re-commendation using twitter[C]∥Proceedings of the 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence. Washington,DC:IEEE,2013:21-25.

[6] KRESTEL R. Recommendation on the social web:diversification and personalization[C]∥Proceedings of the 2011 International Workshop on DETecting and Exploiting Cultural DiversiTy on the Social Web. New York:ACM,2011:1-2. [7] GUAN Y,ZHAO D,ZENG A,et al. Preference of online users and personalized recommendations[J]. Physica A: Statistical Mechanics & Its Applications,2013,392(16):3417-3423.

[8] SALEHI M,KAMALABADI I N. Hybrid recommendation approach for learning material based on sequential pattern of the accessed material and the learner’s preference tree[J]. Knowledge-Based Systems,2013,48:57-69.

[9] ZHANG Y F. Daily-aware personalized recommendation based on feature-level time series analysis[C]∥Proceedings of the 24th International Conference on World Wide Web. Florence,Italy:[s.n.],2015:1373-1383.

[10]NAYAK R,ZHANG M,CHEN L. A social matching system for an online dating network:a preliminary study[C]∥Proceedings of the 2010 IEEE International Conference on Data Mining Workshops. Washington,DC:IEEE,2010:352-357.

[11]WANG T,LIU H,HE J,et al. Predicting new user’s behavior in online dating systems[M]∥Advanced Data Mi-ning and Applications. Berlin:Springer,2011:266-277.

[12]AVERELL L,HEATHCOTE A. The form of the forgetting curve and the fate of memories[J]. Journal of Mathematical Psychology,2011,55(1):25-35.

[13]GARCIN F,ZHOU K,FALTINGS B,et al. Personalized news recommendation based on collaborative filtering[C]∥Proceedings of the 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology. Washington,DC:IEEE,2012:164-173.

[14] 丁浩,戴牡紅. 基于用戶評分和遺傳算法的協(xié)同過濾推薦算法[J/OL]. 計算機(jī)工程與應(yīng)用,2015:6pp. (2015-08-31)[2016-02-25]. http:∥d.g.wanfangdata.com.cn/Periodical_pre_c6cf658e-83f1-498f-8bd3-230dbb8cb6e8.aspx.

DING H,DAI M H. Collaborative filtering recommendation algorithm based on user ratings and genetic algorithm[J]. Computer Engineering and Applications,2015:6pp. (2015-08-31)[2016-02-25]. http:∥d.g.wanfangdata.com.cn/Periodical_pre_c6cf658e-83f1-498f-8bd3-230dbb8cb6e8.aspx.

[15]CACHEDA F,CARNEIRO V,FERNNDEZ D,et al. Comparison of collaborative filtering algorithms:limitations of current techniques and proposals for scalable,high-performance recommender systems[J]. ACM Transactions on the Web,2011,5(1):161-171.

[16] ZHANG Y C,MEDO M,REN J,et al. Recommendation model based on opinion diffusion[J]. Europhysics Letters,2007,80(6):417-429.

[17] ZHANG Y C,BLATTNER M,YU Y K. Heat conduction process on community networks as a recommendation model[J]. Physical Review Letters,2008,99(15):12505-12508.

【中文責(zé)編：莊曉瓊 英文編校：肖菁】

PersonalizedRecommendationModelBasedonDynamicTime

TAN Lili1， NIE Ruihua1*， LIANG Jun2， WANG Jinhong3

(1. School of Computer Science, South China Normal University, Guangzhou 510631, China;2. Network Center, South China Normal University, Guangzhou 510631, China; 3. Bei Ming Software Co., Ltd., Guangzhou 510663, China)

In the recommendation systems, it often exists some problems of non-real-time data, sparse data and cold start. First, the forgetting curve is used to track the changed of user’s interests with time, and then an improved K-Means clustering algorithm is put forward to cluster users, and finally uses the improved personalized re-commendation algorithm. A model of personalized recommendation based on dynamic time is built. The experimental results show that the proposed personalized recommendation model can get more accurate recommendation perfor-mance and alleviate the cold start problem. It also can reduce the computing time and space complexity, and improve the quality of the recommendation of personalized recommendation algorithm.

personalization; forgetting curve; K-Means; material diffusion; heat conduction

2016-03-15 《華南師范大學(xué)學(xué)報(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

教育部-中移動基金項目(MCM20130651)；廣州市科技和信息化局基金項目(2014Y2-00006)

TP

A

1000-5463(2017)03-0123-06

*通訊作者:聶瑞華，教授，Email:nrh@scnu.edu.cn.