融合時間序列的POI動態(tài)推薦算法

原福永，李 晨，雷 瑜，劉宏陽，馮凱東，梁順攀

(燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)

1 引 言

研究用戶偏好的興趣點，不僅能幫助用戶和游客探索之前從未訪問過的城市中的潛在興趣點，而且可以吸引潛在的游客為POI商家?guī)斫?jīng)濟效益.但不同于傳統(tǒng)的顯式反饋推薦，可以利用用戶對物品的評分直接表達(dá)用戶的直接偏好，隱式反饋是通過用戶的簽到行為記錄挖掘其潛在的偏好，這增加了推薦的復(fù)雜性.近些年，利用多種異構(gòu)類型的上下文信息(例如時間、地理位置、標(biāo)簽、評論信息等)挖掘用戶的潛在偏好，為用戶生成推薦列表，是興趣點推薦領(lǐng)域的發(fā)展趨勢.多種異構(gòu)信息的結(jié)合主要包括以下幾個方面.

越來越多的興趣點推薦模型考慮興趣點的位置信息.文獻(xiàn)[1]提出了兩種模型：高斯混合模型(GMM)和基于遺傳算法的高斯混合模型(GA-GMM)來捕捉地理影響.文獻(xiàn)[2]使用三個因素來模擬兩個POI之間的地理影響：POI的地理影響，POI的地理敏感性以及它們的物理距離.文獻(xiàn)[3]分析LBSN的用戶登記活動中呈現(xiàn)的空間聚類現(xiàn)象而導(dǎo)致的地理影響并基于樸素貝葉斯基于地理影響開發(fā)了一種協(xié)同推薦算法.文獻(xiàn)[4]將用戶的登記記錄和社會影響力整合在一個組合模型中，形成一個新的框架，效果優(yōu)于其他算法.

在興趣點推薦領(lǐng)域，時間在多方面影響著用戶的興趣偏好.Song等人[5]提出一種利用用戶POI簽到時間差異性，以及用戶行為相似性進(jìn)行協(xié)同過濾的興趣點推薦算法.首先，用戶對興趣點的偏好程度會隨時間改變.其次，在較短的時間間隔內(nèi)，用戶的興趣具有周期性[6].再者，用戶在一天中不同的時間段對不同興趣點的喜好有明顯差別.Gao等人[7]提出了時序聚合策略，將用戶簽到行為與對應(yīng)的不同時間狀態(tài)整合，證明了引入時間意識因子的重要性.文獻(xiàn)[8]支持實時POI推薦，跟蹤不斷變化的用戶興趣.因此興趣點推薦是一項時間敏感的任務(wù).

現(xiàn)有的POI推薦領(lǐng)域中，多種異構(gòu)信息被考慮在內(nèi).McAuley.J等人[9]提出了一種將評分與評論文本結(jié)合的模型，提高了推薦的準(zhǔn)確性.Gao等人[10]提出GeoSoRev模型，將社交因子，地理因子，評論文本信息融合，基于矩陣分解處理三種因子信息，揚長補短，更好的進(jìn)行個性化興趣點推薦.文獻(xiàn)[11]將基于用戶的協(xié)同過濾、社交影響因子以及地理因素融合到模型中，提升了POI的推薦效果.文獻(xiàn)[12]和文獻(xiàn)[13]將一天分成時刻，統(tǒng)計用戶在不同的時刻中的訪問不同的興趣點的簽到信息，生成用戶-時間-興趣點矩陣，提升推薦效果.

興趣點推薦中主要存在以下問題.1)簽到數(shù)據(jù)稀疏，降低推薦性能；2)經(jīng)典的興趣點推薦算法未能充分利用興趣點的上下文信息，推薦性能沒有顯著增加；3)大部分興趣點領(lǐng)域的推薦算法沒有和時間結(jié)合，不能在具體的時間點動態(tài)推薦.

本文工作主要有：1)結(jié)合用戶與用戶之間的偏好的關(guān)系，充分利用數(shù)據(jù)集中的用戶信息為用戶推薦；2)加入時間序列，獲得與時間有關(guān)的興趣點，形成具有時間意識的興趣點動態(tài)推薦；3)結(jié)合地理位置和流行度信息，進(jìn)一步提升地點推薦的準(zhǔn)確性；4)將子模型融合，形成本文提出的融合時間序列的POI動態(tài)推薦模型(UTPG).

2 概念介紹及算法框架

本章列出了融合時間序列的POI動態(tài)推薦算法所涉及到的相關(guān)概念.

2.1 相關(guān)概念介紹

主要介紹本模型所利用的各個因子，以及如何將不同因子結(jié)合到興趣點推薦模型中.

2.2 具有個性化特征的時間意識的興趣點

由于人類的一天中的行為、甚至一周內(nèi)的行為具有一定的周期性，利用人類的周期性特征，分析用戶的行為特征，一方面緩解數(shù)據(jù)的稀疏性問題，另一方面在某個確定的時刻對用戶進(jìn)行推薦時，結(jié)合用戶歷史簽到記錄推薦.因此，本文引入時間因素，形成與時間有關(guān)的興趣點動態(tài)推薦.

時間的個性化特征是由于不同時間段的社會特征以及人類的習(xí)性具有相關(guān)性，例如早上8點左右的時間段、中午12點左右的時間段以及晚上7點左右的時間段都是進(jìn)餐時間，因此對于不同的興趣點，在不同的時間段被訪問的頻率存在一定的關(guān)聯(lián)性.除此之外，時間具有連續(xù)性特征，分割后的時間段間隔越相鄰，其反映的人類社會習(xí)性的相似程度越高.

2.3 地理位置影響因子

位置是標(biāo)記用戶簽到的興趣點的地理屬性，近年來基于位置的社交網(wǎng)絡(luò)受到廣泛關(guān)注.為了將空間地理位置因素加入到本文算法中，使用冪律分布函數(shù)表示距離對用戶訪問興趣點的影響.

2.4 融合時間序列的興趣點動態(tài)推薦框架

引入具有時間意識的興趣點動態(tài)推薦算法主要分為以下幾個部分，如圖1所示.

3 融合時間序列的POI動態(tài)推薦算法

引入時間意識因子、基于用戶的協(xié)同過濾算法、以及結(jié)合地理位置信息，形成融合時間序列興趣點動態(tài)推薦模型.

3.1 基于用戶的協(xié)同過濾算法

傳統(tǒng)的基于用戶的協(xié)同過濾的方式是根據(jù)用戶之間訪問相同位置的次數(shù)度量.余弦相似度經(jīng)常被用來表示用戶之間的相似程度，如公式(1)所示.

圖1 融合時間序列的POI動態(tài)推薦算法框架圖Fig.1 POI dynamic recommendation algorithm framework diagram of fusion time series

(1)

式中Num(i，l)代表用戶i訪問地點l的次數(shù)，Num(k，l)代表用戶k訪問地點l的次數(shù).

3.2 時間序列劃分

時間序列的劃分，常見的劃分方式有：將一周劃分為以天為時間單位的方式，例如Hosseini S[11]選擇每周間隔來提高POI推薦的效率，將一周分為兩個時間序列：工作日與休息日.Song等人[5]和Yuan Q等人[14]將一天的時間按照小時劃分為24個相等的時間槽.本文將一天劃分為24個小時.統(tǒng)計用戶在不同時刻的偏好，t為0到23之間的整數(shù)，結(jié)合時間段的相似度度量，獲得用戶當(dāng)前的時間為用戶進(jìn)行動態(tài)推薦.

如2.2節(jié)介紹，用戶訪問興趣點的偏好通常與時間有關(guān)，不同興趣點在不同時間具有不同的流行度，因此考慮時間之間的關(guān)系有助于準(zhǔn)確的描述用戶喜好.

3.3 時間序列度量方式

使用時間序列對基于用戶的協(xié)同過濾算法進(jìn)行改進(jìn)，用戶相似性是根據(jù)時間序列的特征計算，不同用戶在相同時間對同一位置的頻率越高，用戶之間的相似度越高.衡量用戶相似度采用余弦相似度度量，如公式(2)所示.

(2)

統(tǒng)計所有用戶在任意兩個時間點之間的相似度，得到平均值作為兩個時間序列的相似性，如公式(3)所示.

(3)

為了緩解孤立的時間點帶來的推薦效果差等問題，使用平滑技術(shù)對時刻進(jìn)行過渡.

用戶在t時刻訪問位置l的預(yù)測評分如公式(4)所示.

(4)

其中，n表示距離當(dāng)前t時刻的跨度.

用戶的相似度如公式(5)所示.

(5)

最終基于用戶的協(xié)同過濾結(jié)果預(yù)測評分如公式(6)所示.

(6)

3.4 結(jié)合地理影響因子與時間流行度的算法

3.4.1 基于地理因子的推薦算法

POI的訪問符合冪律分布.POI間距離越小，用戶訪問的概率越大.因此，地理位置在興趣點推薦領(lǐng)域有重要影響.

冪律分布表示兩個興趣點之間距離和用戶的簽到幾率之間的關(guān)系，如公式(7)所示.

P(dis)=x×disy

(7)

式中，p：簽到POI的概率，dis：POI之間的距離，x和y：參數(shù).取對數(shù)，得到公式(8).

logP=logx+ylogdis

(8)

(9)

通過最小二乘回歸得出到參數(shù)a，b的值，得到用戶訪問某興趣點概率和興趣點之間的距離的關(guān)系表達(dá)式.再使用樸素貝葉斯方法推薦未訪問過的興趣點.數(shù)據(jù)集中全部的興趣點集合為P，用戶訪問過的興趣點標(biāo)記為Pu，則用戶未訪問過的興趣點P′被用戶訪問的概率為P(P′|Pu)，使用貝葉斯的前提為興趣點之間是否被訪問是相互獨立的.用戶在已經(jīng)訪問過Li的前提下，訪問Lj的預(yù)測值如公式(10)所示.

(10)

(11)

3.4.2 基于流行度信息的推薦算法

根據(jù)劃分的時間序列統(tǒng)一興趣點的流行度信息，得到基于時間的流行度特征分布，預(yù)測用戶對興趣點的評分，如公式(12)所示.

(12)

其中，分子是興趣點l在t時刻被用戶訪問過的次數(shù)，L是所有的興趣點集合.

3.5 地理因子與流行度信息融合

將地理因子、流行度信息結(jié)合，得到用戶對興趣點的評分，如公式(13)所示.

(13)

3.6 UTPG模型

將基于時間序列的用戶的協(xié)同過濾算法與結(jié)合地理位置、流行度信息影響的算法結(jié)果融合，得到融合時間序列的POI動態(tài)推薦算法，采用線性加權(quán)的方式融合，得到用戶u在t時刻訪問l的預(yù)測評分，如公式(14)所示.

Pu，t，l=aP(u)+(1-a)P(PTG)

(14)

其中，a是調(diào)節(jié)參數(shù)，其范圍是[0，1].

3.7 算法流程

輸入：用戶、興趣點以及訪問的時間和位置集合；

輸出：興趣點推薦序列；

步驟1.遍歷所有user，計算時刻之間相似度、平均相似度、基于時刻之間的相似度求用戶在某個時間訪問興趣點評分；

步驟2.計算基于連續(xù)時間概念的兩個用戶之間余弦相似度W(i，k)，然后計算基于連續(xù)時間內(nèi)，用戶在時間t訪問興趣點l的評分P(u)；

步驟3.求出冪律分布表達(dá)式，得出用戶基于地理影響因子的評分P(G)；

步驟4.計算基于流行度信息的預(yù)測評分P(P)；

步驟5.將基于地理位置、流行度信息的兩種方法結(jié)合，得到用戶對興趣點的預(yù)測評分P(PTG)；

步驟6.將基于用戶的協(xié)同過濾算法與結(jié)合地理信息與流行度的算法融合，得到最終的預(yù)測結(jié)果Pu，t，i.

4 實驗及結(jié)果分析

4.1 數(shù)據(jù)集

本文提出的算法采用興趣點推薦領(lǐng)域常用的真實數(shù)據(jù)集：Gowalla的用戶簽到數(shù)據(jù)集.將該數(shù)據(jù)集分為3個數(shù)據(jù)集，數(shù)據(jù)集記錄了用戶信息、POI信息、位置信息(經(jīng)、緯度)等信息.

數(shù)據(jù)集中80%的數(shù)據(jù)作為訓(xùn)練集，20%作為測試集.數(shù)據(jù)集信息如表1所示.

表1 數(shù)據(jù)集信息表Table 1 Dataset information

其中，Gowalla-X代表從數(shù)據(jù)集里篩選出去過X個地點以上的用戶的簽到記錄.

4.2 評價標(biāo)準(zhǔn)

本文采用常見的評估指標(biāo)：精度@N(P)、召回率@N(R)衡量推薦結(jié)果的質(zhì)量，其中N是推薦結(jié)果的數(shù)量，并采用F1值評價兩者之間的關(guān)系.精度是一個客觀且真實的評價指標(biāo)，衡量算法的準(zhǔn)確率，是推薦系統(tǒng)中常見的指標(biāo).召回率是衡量算法覆蓋能力的指標(biāo)，算法覆蓋面越大，算法的效果則較優(yōu)，F(xiàn)1值是調(diào)和精確率和召回率的指標(biāo)，由于精確度和召回率存在一定的矛盾性，因此本文的算法衡量指標(biāo)采用了F1值.精度計算方式如公式(15)所示.

(15)

其中Ca為預(yù)測正確的集合，Call為預(yù)測的全部集合.

召回率的計算方式如公式(16)所示.

(16)

其中Ca為預(yù)測正確的集合，Ct為實際正確的集合.

F1值的計算方式如公式(17)所示.

(17)

4.3 對比算法

1)TCFRA[5]，考慮了時間敏感的POI的特性，得到推薦結(jié)果.

2)PT：根據(jù)興趣點的時間分布特征，得到用戶在某時刻對興趣點的預(yù)測評分.

3)UPT：將基于用戶、流行度結(jié)合，計算預(yù)測評分.

4)UTPG算法(基于時間序列的POI動態(tài)推薦算法)：將基于用戶的協(xié)同過濾、基于地理影響因子和時間流行度信息的算法結(jié)合，得到用戶在某時刻對興趣點的預(yù)測評分.

Gowalla-10數(shù)據(jù)集：Top-5的推薦結(jié)果，UTPG在U：PG為4：1，其中P：G為4：1時的結(jié)果最優(yōu).Top-10的推薦結(jié)果，UTPG在U：PG為4：1，其中P：G為9：1結(jié)果最優(yōu)，推薦結(jié)果如表2、3所示.其中U、G、P分別代表基于用戶的協(xié)同過濾、結(jié)合地理位置、流行度信息影響的算法.

Gowalla-20：TOP-5的推薦結(jié)果，U：PG為4：1，P：G為3：2結(jié)果最優(yōu).TOP-10的推薦結(jié)果，U：PG為4：1，P：G為4：1時的結(jié)果最優(yōu).結(jié)果如表4、表5所示.

Gowalla-30：TOP-5的推薦結(jié)果，U：PG為4：1，P：G為1：9或者P為0時的結(jié)果最優(yōu)，TOP-10的推薦結(jié)果中，U：PG為4：1，P：G為3：2時結(jié)果最優(yōu).結(jié)果如表6、表7所示.

表2 Gowalla-10數(shù)據(jù)集Top-5推薦結(jié)果Table 2 Top-5 recommendation results of Gowalla-10

表3 Gowalla-10數(shù)據(jù)集Top-10推薦結(jié)果Table 3 Top-10 recommendation results of Gowalla-10

表4 Gowalla-20數(shù)據(jù)集Top-5推薦結(jié)果Table 4 Top-5 recommendation results of Gowalla-20

表5 Gowalla-20數(shù)據(jù)集Top-10推薦結(jié)果Table 5 Top-10 recommendation results of Gowalla-20

1)算法性能分析：根據(jù)實驗結(jié)果，可以得出，本文算法UTPG模型在TOP-N的N值分別取5、10時，在數(shù)據(jù)集gowalla-10、gowalla-20、gowalla-30中，不論在精度，召回率，還是F1值方面，效果均為最優(yōu).

這也證明了實驗選擇4個異構(gòu)信息方面：用戶之間的影響、時間的分布特征、興趣點的流行度信息、地理影響因子都能有效地提升推薦的性能.在新生成的推薦中，算法根據(jù)歷史簽到特征為其動態(tài)推薦.

表6 Gowalla-30數(shù)據(jù)集Top-5推薦結(jié)果Table 6 Top-5 recommendation results of Gowalla-30

2)不同數(shù)據(jù)集中不同影響因子分析：在gowalla-10、gowalla-20、gowalla-30數(shù)據(jù)集，UPT的準(zhǔn)確率、召回率均比PT高，說明用戶相互之間的偏好影響比較大，同時UTPG均比PT和UPT的結(jié)果好，得出地理影響因子一定程度上提高了推薦性能.因此得出，用戶、時間流行度、地理影響因子可以提高推薦的準(zhǔn)確率和召回率.

在gowalla-10、gowalla-20、gowalla-30數(shù)據(jù)集，U：PG均為4：1時取得推薦結(jié)果為最優(yōu)，因此，說明興趣點推薦中，用戶之間的影響比較大.且在gowalla-10、gowalla-20中，基于時間的流行度影響因子大于地理因子所帶來的影響.地理影響因子也一定程度上提升了POI推薦的性能.

經(jīng)過對數(shù)據(jù)集的分析，可以得出，在簽到數(shù)據(jù)比較少時，使用地理、時間信息能提高推薦的性能，因此，UTPG模型，可以在一定程度上緩解推薦算法中由于數(shù)據(jù)稀疏而引發(fā)的推薦結(jié)果差等問題.

5 結(jié) 論

本文提出的基于時間序列的POI動態(tài)推薦算法，充分考慮了4種異構(gòu)信息：

1)用戶之間的偏好影響信息；

2)興趣點的時間特征信息，分析不同時刻興趣點的時間特征；

3)地理位置信息，通過冪律分布函數(shù)分析用戶訪問興趣點之間的關(guān)系；

4)統(tǒng)計各個興趣點在不同時刻的流行度信息，并將此融合到算法當(dāng)中，得出用戶訪問興趣點的預(yù)測概率.

在數(shù)據(jù)比較稀疏時，本文算法可以進(jìn)一步提高推薦性能，緩解由于數(shù)據(jù)稀疏性而帶來的推薦不準(zhǔn)確等問題.通過實驗驗證，本文提出的UTPG算法優(yōu)于其他幾個對比算法，有效提高了推薦的精確度與召回率.