融合時間序列的POI動態推薦算法

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

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

1 引 言

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

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

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

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

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

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

2 概念介紹及算法框架

本章列出了融合時間序列的POI動態推薦算法所涉及到的相關概念.

2.1 相關概念介紹

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

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

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

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

2.3 地理位置影響因子

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

2.4 融合時間序列的興趣點動態推薦框架

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

3 融合時間序列的POI動態推薦算法

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

3.1 基于用戶的協同過濾算法

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

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

(1)

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

3.2 時間序列劃分

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

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

3.3 時間序列度量方式

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

(2)

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

(3)

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

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

(4)

其中，n表示距離當前t時刻的跨度.

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

(5)

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

(6)

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

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

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

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

P(dis)=x×disy

(7)

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

logP=logx+ylogdis

(8)

(9)

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

(10)

(11)

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

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

(12)

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

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

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

(13)

3.6 UTPG模型

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

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

(14)

其中，a是調節參數，其范圍是[0，1].

3.7 算法流程

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

輸出：興趣點推薦序列；

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

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

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

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

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

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

4 實驗及結果分析

4.1 數據集

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

數據集中80%的數據作為訓練集，20%作為測試集.數據集信息如表1所示.

表1 數據集信息表Table 1 Dataset information

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

4.2 評價標準

本文采用常見的評估指標：精度@N(P)、召回率@N(R)衡量推薦結果的質量，其中N是推薦結果的數量，并采用F1值評價兩者之間的關系.精度是一個客觀且真實的評價指標，衡量算法的準確率，是推薦系統中常見的指標.召回率是衡量算法覆蓋能力的指標，算法覆蓋面越大，算法的效果則較優，F1值是調和精確率和召回率的指標，由于精確度和召回率存在一定的矛盾性，因此本文的算法衡量指標采用了F1值.精度計算方式如公式(15)所示.

(15)

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

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

(16)

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

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

(17)

4.3 對比算法

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

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

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

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

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

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

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

表2 Gowalla-10數據集Top-5推薦結果Table 2 Top-5 recommendation results of Gowalla-10

表3 Gowalla-10數據集Top-10推薦結果Table 3 Top-10 recommendation results of Gowalla-10

表4 Gowalla-20數據集Top-5推薦結果Table 4 Top-5 recommendation results of Gowalla-20

表5 Gowalla-20數據集Top-10推薦結果Table 5 Top-10 recommendation results of Gowalla-20

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

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

表6 Gowalla-30數據集Top-5推薦結果Table 6 Top-5 recommendation results of Gowalla-30

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

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

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

5 結 論

本文提出的基于時間序列的POI動態推薦算法，充分考慮了4種異構信息：

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

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

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

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

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