引入時間衰減項的興趣點推薦算法

常曉雨，余正生

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

?

引入時間衰減項的興趣點推薦算法

常曉雨，余正生

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

摘要：興趣點推薦已成為幫助人們發(fā)現(xiàn)感興趣點的重要手段，傳統(tǒng)推薦算法僅僅對固定時間段內(nèi)的興趣點做推薦，而沒有考慮興趣點推薦存在時間上的衰減現(xiàn)象.為了進(jìn)一步提高興趣點推薦算法的性能，總結(jié)了傳統(tǒng)基于興趣點相似度的協(xié)同過濾推薦算法，設(shè)計了表現(xiàn)更優(yōu)異的改進(jìn)算法——引入時間衰減項的興趣點推薦算法.實際數(shù)據(jù)集上的測試結(jié)果表明，改進(jìn)算法在精準(zhǔn)度、召回率和F指標(biāo)等方面比傳統(tǒng)基于興趣點相似度的協(xié)同過濾推薦算法有更好的表現(xiàn).

關(guān)鍵詞：興趣點推薦；協(xié)同過濾；時間衰減項；推薦算法

0引言

隨著智能手機(jī)的普及和定位技術(shù)的發(fā)展，人們更容易獲得自己位置的實時信息，從而促使了基于位置的社交網(wǎng)絡(luò)的出現(xiàn)，例如大眾點評，F(xiàn)oursquare，Jiepang等[1-3].基于位置的社交網(wǎng)絡(luò)中包含了用戶對興趣點訪問的時間信息，為人們在推薦算法中考慮時間衰減性提供了便利.例如，文獻(xiàn)[4]對固定時間段內(nèi)的興趣點做推薦，但沒有考慮興趣點推薦存在時間上的衰減現(xiàn)象，因此這種算法并不適用于對整個時間軸上的興趣點做推薦.在興趣點推薦中，用戶訪問時間間隔越短的興趣點之間的相似度越高，在推薦算法中的權(quán)重越大.為了進(jìn)一步挖掘興趣點推薦中的時間特性，本文提出了一種引入時間衰減項的興趣點推薦算法，它不僅適用于固定時間段內(nèi)的興趣點，還可以對整個時間軸上的興趣點做推薦.

1相似度求解公式

1)余弦相似度.在余弦相似度求解公式中，通過興趣點評分向量之間的夾角余弦來度量它們之間的相似度.興趣點i，j的余弦相似度如下：

(1)

2)修正余弦相似度.在余弦相似度基礎(chǔ)上進(jìn)行了改進(jìn)，通過減去用戶對興趣點的平均評分解決了余弦相似度沒有考慮用戶評分等級差異的問題.興趣點i，j的修正余弦相似度如下：

(2)

3)皮爾遜相關(guān)系數(shù)相似度.與修正余弦相似度一樣，它也解決了用戶評分等級差異的問題.興趣點i，j的皮爾遜相關(guān)系數(shù)相似度如下：

(3)

2引入時間衰減項的興趣點推薦算法

就統(tǒng)計意義上來說，用戶訪問時間相隔越短的興趣點之間相似度越高，在推薦算法中的權(quán)重越大.實驗中引入適合本文數(shù)據(jù)集應(yīng)用場景的時間衰減函數(shù)如下：

f(|tui-tuj|)=Qt+e-Nt|tui-tuj|,i,j∈G,t∈T.

(4)

式中，Qt，Nt(Qt，Nt>0)為時間衰減參數(shù)，取值與特定系統(tǒng)相關(guān)，G為興趣點的集合，T為用戶訪問興趣點的時間集合.分別在3.3節(jié)實驗1和實驗3中對Qt和Nt取值進(jìn)行了測試.

通過引入時間衰減函數(shù)式(4)得到改進(jìn)后的興趣點相似度求解公式如下：

wtime(i,j)=w(i,j)f(|tui-tuj|).

(5)

式中，w(i,j)表示通過傳統(tǒng)興趣點相似度求解公式得到的興趣點i和j之間的相似度.

用戶u對興趣點i的評分預(yù)測公式如下[7]:

(6)

3仿真實驗

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

本文抓取了大眾點評中杭州下沙地區(qū)用戶從2012-06-10到2015-06-10的簽到數(shù)據(jù)，如表1所示.

表1　杭州下沙地區(qū)用戶簽到數(shù)據(jù)集

表1中，u代表用戶的編號，1≤u≤m，m為收集的用戶總數(shù)；i代表興趣點的編號，1≤i≤n，n為興趣點總數(shù)；rui代表用戶u對興趣點i的最近一次評分值，tui代表用戶u對興趣點i的最近一次簽到時間.

本文共抓取到1 276 683條簽到數(shù)據(jù)，通過以下步驟給用戶u推薦預(yù)測評分值最大的N個興趣點：

1)隨機(jī)選取1/8的簽到興趣點作為測試集，剩余7/8的簽到興趣點作為訓(xùn)練集；

2)通過式(5)計算出各個興趣點之間的相似度，得到興趣點相似度矩陣；

3)將興趣點相似度矩陣中的數(shù)據(jù)按降序排列，得到排序好的興趣點相似度矩陣；

4)利用評分預(yù)測式(6)，預(yù)測出用戶u對測試集中各個興趣點的預(yù)測評分；

5)將預(yù)測評分值最大的N個興趣點推薦給用戶u.

3.2算法評價指標(biāo)

R(u)表示用戶u推薦的N個興趣點的集合，T(u)表示用戶u實際感興趣的興趣點集合，則召回率(Recall，記為PRecall)、精準(zhǔn)度(Precision，記為PPrecision)和F指標(biāo)(F-Measure，記為F)[8]分別如下所示：

(7)

(8)

(9)

召回率描述的是在用戶實際感興趣的興趣點當(dāng)中被推薦的比例，精準(zhǔn)度描述的是推薦列表當(dāng)中用戶實際感興趣的興趣點所占的比例，但這2個指標(biāo)經(jīng)常出現(xiàn)相互矛盾的情況，往往1個指標(biāo)增大的同時另1個指標(biāo)隨之減小，為了綜合考慮召回率和精準(zhǔn)度，實驗中還用到了綜合評價指標(biāo)F指標(biāo).

3.3仿真實驗與分析

實驗中的數(shù)據(jù)來源于大眾點評網(wǎng)，將這些數(shù)據(jù)運(yùn)用于興趣點推薦是本文的數(shù)據(jù)集應(yīng)用場景.

實驗1用戶對興趣點的平均回訪率與時間跨度的關(guān)系.

回訪率是用戶訪問了某個興趣點相隔一段時間后再次訪問這個興趣點的概率.平均回訪率是全體用戶回訪率的平均值.平均回訪率與時間跨度的關(guān)系如圖1所示，反映出隨著時間的增長用戶整體對興趣點的感興趣程度的變化規(guī)律.

圖1　平均回訪率與時間跨度關(guān)系圖

由圖1可知，在本文數(shù)據(jù)集應(yīng)用場景中，平均回訪率y與時間跨度x整體呈現(xiàn)出以e為底的指數(shù)函數(shù)關(guān)系，即y=m+e-qx(m,q>0)函數(shù)關(guān)系.時間跨度在0～420 h之間時，平均回訪率隨時間跨度變化較大，主要是非常住人口或旅游人員起到比較大的作用.時間跨度為420 h以后平均回訪率保持在0.13左右，這部分是常住人口經(jīng)常訪問的興趣點隨時間跨度變化不大.因此在本文數(shù)據(jù)集應(yīng)用場景中的引入的時間衰減函數(shù)為式(4)，并且Qt取值為0.13.

實驗2傳統(tǒng)基于興趣點相似度的協(xié)同過濾推薦算法中不同的相似度計算方法的性能表現(xiàn).

在推薦列表長度N取不同值情況下，對利用式(1)、式(2)、式(3)的3種方法對興趣點推薦算法的推薦性能進(jìn)行比較實驗，實驗結(jié)果如圖2和圖3所示.

圖2　不同N時，3種算法的精準(zhǔn)度和召回率

圖3　不同N時，3種算法的F指標(biāo)

由圖2和圖3可知，從精準(zhǔn)度、召回率和F指標(biāo)方面看，余弦算法優(yōu)于修正余弦算法，修正余弦算法又優(yōu)于皮爾遜相關(guān)系數(shù)算法；由圖2可知，余弦算法的精準(zhǔn)度和召回率相交在7～8之間，表明杭州下沙地區(qū)用戶每次最有可能訪問7～8個興趣點.

實驗3引入時間衰減項的興趣點推薦算法中時間衰減參數(shù)Nt對推薦性能的影響.

根據(jù)引入時間衰減項的興趣點推薦算法中時間衰減參數(shù)Nt對推薦性能的影響，取得Nt的最優(yōu)值如表2所示.

由實驗2結(jié)論可知，杭州下沙地區(qū)用戶每次最有可能訪問7～8個興趣點，這里推薦列表長度N值取為8.

表2　推薦列表長度N=8時，不同時間衰減參數(shù)Nt下的精準(zhǔn)度和召回率

由表2可知，當(dāng)時間衰減參數(shù)Nt逐步減小時精準(zhǔn)度和召回率都在逐步增大，當(dāng)Nt=0.005時精準(zhǔn)度和召回率達(dá)到最大，本實驗場景中時間衰減參數(shù)Nt取值為0.005.

實驗4對比引入時間衰減項的興趣點推薦算法與實驗2中性能最好的基于興趣點相似度的協(xié)同過濾推薦算法的性能表現(xiàn).

在推薦列表長度N取不同值情況下，對兩種推薦算法的推薦性能進(jìn)行比較實驗，實驗結(jié)果如圖4和圖5所示.

時間衰減參數(shù)Qt和Nt已經(jīng)分別在實驗1和實驗3中得到，這里取它們的最優(yōu)值.

圖4　不同N時，2種算法的精準(zhǔn)度和召回率

圖5　不同N時，2種算法的F指標(biāo)

由圖4和圖5可知，引入時間衰減項的興趣點推薦算法比傳統(tǒng)基于興趣點相似度的協(xié)同過濾推薦算法在精準(zhǔn)度、召回率和F指標(biāo)方面有更好的表現(xiàn).

4結(jié)束語

本文以杭州下沙地區(qū)用戶簽到數(shù)據(jù)集為實驗數(shù)據(jù)，研究并得到了興趣點相似度在整個時間段內(nèi)的時序特征，提出了引入時間衰減項的興趣點推薦算法.通過一系列測試實驗，驗證了引入時間衰減項的興趣點推薦算法比傳統(tǒng)基于興趣點相似度的協(xié)同過濾推薦算法有更好的性能表現(xiàn).但在不同數(shù)據(jù)集應(yīng)用場景中時間衰減函數(shù)的類型不一定相同，本文沒能給出時間衰減函數(shù)的一般公式，這將是下一步研究的方向.

參考文獻(xiàn)

[1]李敏，王曉聰，張軍，等.基于位置的社交網(wǎng)絡(luò)用戶簽到及相關(guān)行為研究[J].計算機(jī)科學(xué)，2013，40(10)：72-76.

[2]YANGD,ZHANGD,YUZ,etal.Asentiment-enhancedpersonalizedlocationrecommendationsystem[C]//Proceedingsofthe24thACMConferenceonHypertextandSocialMedia.ACM, 2013: 119-128.

[3]孟祥武，胡勛，王立才，等.移動推薦系統(tǒng)及其應(yīng)用[J].軟件學(xué)報，2013，24(1)：91-108.

[4]徐翔俊，聶任燦.基于位置的社會網(wǎng)絡(luò)中面向時序特征的興趣點推薦算法[J].計算機(jī)應(yīng)用研究，2015，32(7)：1959-1961.

[5]BOBADILLAJ,ORTEGAF,HERNANDOA,etal.Recommendersystemssurvey[J].Knowledge-BasedSystems, 2013, 46(1): 109-132.

[6]XIANGC,GUISHENGY,LONGZ,etal.Methodofcollaborativefilteringbasedonuncertainuserinterestscluster[J].Journalofcomputers, 2013, 8(1): 186-193.

[7]項亮.推薦系統(tǒng)實踐[M].北京：人民郵電出版社，2012：41-64．

[8]HERLOCKERJL,KONSTANJA,TERVEENLG,etal.Evaluatingcollaborativefilteringrecommendersystems[J].ACMTransactionsonInformationSystems(TOIS), 2004, 22(1): 5-53.

DOI：10.13954/j.cnki.hdu.2016.03.009

收稿日期：2015-09-15

基金項目：國家自然科學(xué)基金資助項目(61502131)

作者簡介：常曉雨(1987-)，男，河南許昌人，碩士研究生，機(jī)器學(xué)習(xí).通信作者：余正生教授，E-mail：yuzhengsheng@hdu.edu.cn.

中圖分類號：TP181

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

文章編號：1001-9146(2016)03-0042-05

Point-of-interest Recommendation Algorithm Introducing Time Attenuation Item

CHANG Xiaoyu, YU Zhengsheng

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：Point-of-interest(PoI) recommendation has become an important means to help people find interesting locations. Traditional recommendation algorithms just focus the recommendation on a fixed period of time, without taking account of the attenuation phenomena of time. In order to further improve the performance of the recommendation algorithm, this paper summarizes the traditional collaborative filtering recommendation algorithms based on the similarity of PoI and designs a superior improved algorithm which is the PoI recommendation algorithm introducing time attenuation item. The test results on real datasets show that the improved algorithm performs better than the traditional collaborative filtering recommendation algorithms based on the similarity of PoI in terms of precision, recall rate and F-measure.

Key words：point-of-interest recommendation; collaborative filtering; time attenuation item; recommendation algorithm