融入時間的興趣點協(xié)同推薦算法

包 玄，陳紅梅，肖 清

（云南大學信息學院，昆明 650500）

0 引言

隨著全球定位系統(tǒng)、移動互聯(lián)網(wǎng)等信息技術(shù)的發(fā)展以及移動設備的普及，基于位置的社交網(wǎng)絡（Location-Based Social Network，LBSN）受到越來越多人的喜愛，人們在網(wǎng)絡平臺（如Yelp、微博、Twitter等）上分享豐富的位置相關(guān)信息，使得位置數(shù)據(jù)激劇膨脹，導致信息過載，不論服務商還是用戶，都難以從海量位置數(shù)據(jù)中獲取感興趣的信息，于是位置推薦應運而生，其中興趣點（Point-Of-Interest，POI）推薦備受關(guān)注。POI推薦是根據(jù)用戶的POI訪問歷史，以及用戶和POI的描述信息，分析用戶興趣偏好，發(fā)現(xiàn)用戶潛在感興趣的POI并推薦給用戶。POI推薦不僅可以幫助用戶快速獲取所需信息，改進用戶體驗，也可以幫助服務商快速定位目標客戶，提高商業(yè)利潤。

傳統(tǒng)POI推薦大致可以描述為：首先，將用戶的POI訪問歷史建模為一個二維簽到矩陣User-POI，用以表達用戶訪問POI的情況，例如，如果用戶u訪問過POIl，則簽到矩陣元素（u，l）的值1，否則為0。然后，基于簽到矩陣User-POI，采用協(xié)同過濾技術(shù)，學習用戶的POI偏好，估計用戶沒訪問過但可能感興趣的POI評分，即簽到矩陣中為0的元素的可能值。最后，按估計的評分高低，將用戶沒訪問過但可能感興趣的POI推薦給用戶。

為了提升POI推薦效果，研究者在傳統(tǒng)推薦的基礎上，融合上下文信息，如用戶間的社交關(guān)系、POI間的距離關(guān)系等。最近，研究者也開始關(guān)注用戶訪問POI的時間信息。文獻［1-2］的研究表明，人們一天的活動具有規(guī)律性。例如，中午12點用戶大概率訪問餐館，半夜12點訪問酒吧等。在POI推薦中，如果不考慮時間因素，則可能出現(xiàn)中午11點向用戶推薦酒吧，晚上12點向用戶推薦餐館，降低POI推薦效果。因此，在POI推薦中，時間是一個重要的影響因素。

基于上述分析，本文研究融入時間的POI推薦，問題描述為：根據(jù)用戶的POI訪問歷史（包括用戶、時間、POI信息），分析用戶的訪問時間及POI偏好，發(fā)現(xiàn)用戶潛在感興趣的POI及訪問時間，按時間推薦POI給用戶。為解決該問題，本文主要做了如下工作：

1）首先，分析用戶的POI訪問歷史，探索用戶訪問POI的時間關(guān)系，發(fā)現(xiàn)兩個關(guān)于不同時間片間POI訪問相似度變化的規(guī)律。

2）然后，基于上述兩個發(fā)現(xiàn)規(guī)律，提出新的用戶簽到數(shù)據(jù)平滑方法和候選POI評分計算方法，進而提出一個融入時間的POI協(xié)同推薦模型。

3）最后，在兩個真實數(shù)據(jù)集Foursquare和Gowalla上進行實驗，評估所提出的推薦模型。實驗結(jié)果表明所提推薦算法在精確率、召回率、平均絕對誤差方面均優(yōu)于對比算法。

1 相關(guān)工作

推薦系統(tǒng)廣泛采用的技術(shù)是協(xié)同過濾（Collaborative Filtering，CF），可分為基于記憶的協(xié)同過濾（Memory-Based CF）和基于模型的協(xié)同過濾（Model-Based CF）。基于記憶的協(xié)同過濾又可分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾。該類方法依據(jù)相似的用戶（項目）具有相似的偏好，主要包括兩個關(guān)鍵步驟：首先計算用戶（項目）相似度，然后利用相似用戶（項目）的加權(quán)評分估計目標用戶對未評分項目的評分，從而根據(jù)評分形成推薦列表［2］?；谀Ｐ偷膮f(xié)同過濾采用數(shù)據(jù)挖掘和機器學習，建立推薦模型，該類方法包括決策樹模型、貝葉斯方法、矩陣分解方法等［3］。

針對位置數(shù)據(jù)膨脹及信息過載，上述推薦技術(shù)被用于POI推薦，在此分兩類進行介紹：

1）POI推薦。

為了提升POI推薦效果，研究者在傳統(tǒng)方法上融合上下文信息，如用戶間的社會關(guān)系、POI間的距離關(guān)系等。文獻［4］采用線性插值將用戶間的社會關(guān)系以及POI間的距離關(guān)系融入基于用戶的協(xié)同過濾框架；文獻［5］在基于用戶的協(xié)同過濾框架中融入用戶間的社會關(guān)系，并貝葉斯方法對空間影響進行建模；文獻［6］探索用戶的2-度好友的社交影響，采用PageRank算法計算地點影響力，采用核密度估計方法發(fā)現(xiàn)用戶的位置偏好，最后將三者融合進行POI推薦；文獻［7］將用戶偏好和個性化的地理社會影響整合到地理社會推薦框架中，提出一種潛在的基于地理社會關(guān)系的POI推薦模型；文獻［8-10］利用社會友誼提高推薦的效率和性能，計算所有用戶之間的相似性，并利用用戶相似性作為正則化約束矩陣分解。

2）考慮時間因素的POI推薦。

由于用戶會在不同的時間訪問不同類型的POI（如餐館、咖啡店、酒吧），所以時間是POI推薦中的重要因素。為了進一步提升POI推薦效果，增強用戶體驗，最近，研究者也開始關(guān)注融合用戶訪問POI的時間信息，提出了考慮時間因素的POI推薦。文獻［2］在基于用戶的協(xié)同過濾框架下建模用戶偏好和時間影響，采用冪律分布建模地理影響，提出了融合時間與地理影響的時間感知POI推薦算法；文獻［11-12］中提出了一種基于張量因子分解的協(xié)同過濾方法，利用一個高階張量來融合用戶簽到的異構(gòu)上下文信息——時間信息、社交關(guān)系、地理位置；文獻［13］用概率模型將用戶對地點的興趣度，用戶所處的時間段和地點自身的流行度融合起來進行POI推薦；文獻［14］在基于用戶協(xié)同過濾的基礎上，結(jié)合有序圖探索用戶偏好，基于用戶當前時間的位置，為用戶推薦下一個訪問的POI；文獻［15］將用戶簽到的時間信息以及空間信息融入用戶相似度的計算中，提出一種改進的基于用戶協(xié)同過濾的算法；文獻［16］用有向圖表示用戶的歷史訪問數(shù)據(jù)，考慮相似用戶、時間以及簽到序列，基于圖的性質(zhì)提出一種新穎的基于用戶協(xié)同過濾模型。

本文受文獻［2］啟發(fā)，研究融入時間的POI推薦，但是與文獻［2］不同，本文深入分析用戶簽到的時間關(guān)系，基于兩個關(guān)于不同時間片間POI訪問相似度變化規(guī)律的發(fā)現(xiàn)（將在3.1節(jié)中詳述），提出新的用戶簽到數(shù)據(jù)平滑方法和候選POI評分計算方法，進而提出一個融入時間的POI推薦模型，不僅有效解決了簽到數(shù)據(jù)的稀疏性問題，還獲得了相對較高的推薦質(zhì)量。

2 基于用戶的協(xié)同推薦

本文所用符號和含義描述如表1所示。

表1 本文所用符號及其含義描述Tab.1 Symbols used in this paper and their meaning descriptions

基于用戶的協(xié)同過濾（User-based collaborative filtering，U）算法，主要步驟是：首先，根據(jù)用戶的POI訪問歷史度量用戶間的相似性，找到目標用戶的一組相似用戶。然后，利用相似用戶的加權(quán)評分，估計目標用戶對沒訪問POI的評分，從而根據(jù)評分形成POI推薦列表。具體地，根據(jù)用戶的POI訪問歷史，建立二維簽到矩陣即User-POI矩陣，對于其中的每個元素Cul（u∈U，l∈I），如果用戶u訪問過POIl，則設置Cul=1，否則設置Cul=0。給定一個目標用戶u，則用戶u對沒訪問POIl的評分估計計算如式（1）所示：

其中Wuv表示目標用戶u和相似用戶v之間的相似度。兩個用戶間的相似性度量有多種，本文采用使用最廣泛的余弦相似性度量，計算方法如下：

3 融入時間的POI協(xié)同推薦

3.1 時間關(guān)系分析

用戶在一天甚至一周內(nèi)的活動具有一定的規(guī)律。這個規(guī)律主要分為用戶訪問POI的時間差異性和連續(xù)性。差異性是指用戶中午去餐館，晚上去酒吧等；工作日在家和單位附近，而周末去離家較遠的地方游玩等，即用戶訪問POI隨時間的變化而變化。連續(xù)性是指在相鄰時間段，用戶的活動具有相似性［15］。例如，用戶在中午12—13點會訪問餐廳等相似的POI。因此，本文將一天按小時劃分為24個時間片，如24（hh）：01（mm）：00（ss）為時間片0，10（hh）：15（mm）：30（ss）為時間片10，構(gòu)成時間片集合T=｛0，1，…，23｝。然后，在兩個真實數(shù)據(jù)集Foursquare和Gowalla上，利用常用的相似性度量方法——余弦相似性，度量任意兩個時間片間的相似度，分析用戶訪問POI的時間關(guān)系可發(fā)現(xiàn)：

1）用戶在不同時間片訪問的POI具有不同程度的相似性。

本文以Foursquare數(shù)據(jù)集上的結(jié)果為例。圖1顯示了該數(shù)據(jù)集上3個時間片（7點、12點和18點）與其他時間片的相似度曲線。從圖1中可以看出這3個時間片與0—6點的相似度很低，在6點以后逐漸升高，7點以后（8—23點）的相似度均比6點以前的高。這和實際生活中大多數(shù)人上午6—7點出門，凌晨進入睡眠相符合。在18點時間片的曲線上，11點時相似度有小幅上升，同樣，在7點與12點兩個時間片的曲線上，17點和18點時相似度也有小幅上升，這符合早飯、午飯、晚飯的時間。綜上，用戶在不同時間片訪問的POI具有不同程度的相似性。

圖1 給定時間片與任意時間片之間的相似度Fig.1 Similarities between given time slicesand other time slices

2）用戶訪問POI的相似性隨時間差增加而衰減。

進一步，本文分析不同時間差下，用戶訪問POI的相似度，其 中，時 間 差Δt=|t-t'|(|t-t'|≤12)或Δt=24-|t-t'|(|t-t'|>12)，結(jié)果如圖2所示。

本文以Foursquare數(shù)據(jù)集上的結(jié)果為例。由圖2可以看出時間差越大，時間片間相似度越低。當時間差為0時，在總相似度中占比為58%，剩余時間差占比為42%。即，相同時間片上用戶簽到偏好具有最大的相似性。也就是說，相同時間上用戶偏好對用戶決定是否訪問某一POI的影響最大；同時其余時間片上的簽到偏好也不能忽視。因此，本文首先利用所有時間片間的相似度平滑簽到矩陣以緩解數(shù)據(jù)稀疏問題，進而使用平滑之后獲得的簽到矩陣，發(fā)現(xiàn)用戶偏好。其次，利用相同時間片的用戶訪問偏好最相似這一特點，按時間給用戶推薦POI，從而提高推薦效果。

圖2 時間差與相似度Fig.2 Time differenceand similarity

3.2 融入時間的POI協(xié)同推薦算法

對簽到數(shù)據(jù)按小時劃分之后，原本的二維簽到矩陣User-POI，被建模為一個三維簽到張量即User-Time-POI。對于其中每個元素Cutl（u∈U，t∈T，l∈L），如果用戶u在時間片t訪問POIl，那么設置Cutl=1，否則設置Cutl=0。融入時間的POI協(xié)同推薦算法，首先利用獲取的時間關(guān)系平滑用戶的簽到矩陣，然后根據(jù)平滑后的簽到矩陣尋找相似用戶，最后利用相似用戶簽到偏好為目標用戶u在時間片t進行POI推薦。

3.2.1 時間片平滑

其中Simtt'表示時間片t與t'的相似度。采用常用的相似性方法——余弦相似性，計算如下：

3.2.2 用戶相似度計算

為解決融入時間的POI協(xié)同推薦，首先尋找目標用戶u的相似用戶。為使搜索到的相似用戶更加準確，在度量相似用戶時，不僅考慮訪問的POI，還加入訪問的時間。例如，用戶u1在時間t1以及t2訪問l1和l2，用戶u2在時間t1以及t2訪問l2和l1，在不考慮時間的情況下，利用式（1）計算得到u1、u2的相似度為1，融入時間之后相似度為0。

在更加稀疏的三維簽到張量中，直接引入時間計算兩個用戶相似度雖然會提高相似用戶的質(zhì)量，但當不同的用戶在不同的時間片訪問同一個POI時，直接加入時間片尋找相似用戶忽略了用戶在某一個時間片上簽到行為和其他時間片上的簽到行為具有相似性。例如，用戶u和v分別在時間t1和t2訪問l1，不考慮時間片相似的情況用戶u和v的相似度為0；考慮時間片相似的情況，用戶u和v的相似度則大于0。因此，根據(jù)平滑后的簽到矩陣計算用戶相似度，計算如式（5）所示：

3.2.3 POI推薦

由3.1節(jié)分析可知，相同時間片上用戶簽到偏好具有最大的相似性，即相同時間片上用戶簽到偏好對用戶決定是否訪問某一POI的影響最大。所以，本文利用相似用戶在同一時間片的訪問偏好評估候選POI。采用基于用戶的協(xié)同過濾，以及3.2.1節(jié)中平滑后的簽到矩陣、3.2.2節(jié)中的相似用戶及其相似性，估計目標用戶u在時間片t訪問POIl的評分，計算方法如式（6）所示：

排序式（6）得到的估計評分，即可獲得在時間片t，向目標用戶u推薦的POI列表。融入時間的POI協(xié)同推薦（Timeincorporated User-based Collaborative Filtering POI recommendation，TUCF）算法描述如下。

輸入：用戶簽到數(shù)據(jù)集，目標用戶u，時間片集合T；

輸出：目標用戶u在各個時間片上的推薦列表。

1）將用戶簽到數(shù)據(jù)建模為User-Time-POI張量；

2）利用式（4）計算各個時間片間的余弦相似度；

3）根據(jù)式（3）平滑User-Time-POI簽到張量；

4）根據(jù)式（5）計算用戶間的相似度；

5）獲取候選POI：用戶在時間片t沒有訪問過的POI；

6）利用式（6）計算每個候選POI的評分；

7）對評估分數(shù)排序，取前N個POI作為推薦列表Rank，并返回Rank。

在TUCF算法中，選出估計評分最高的N個POI作為最終的推薦結(jié)果，根據(jù)實際推薦的情況N的取值不同。

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

4.1 實驗設置

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

本文使用文獻［2］提供的兩個真實數(shù)據(jù)集Foursquare和Gowalla。Foursquare數(shù)據(jù)集為2010年8月—2011年7月的新加坡簽到數(shù)據(jù)，包含2 321個用戶，5 596個POI，共194 108條簽到。Gowalla數(shù)據(jù)集為2009年8月—2010年9月加州和內(nèi)華達州的簽到數(shù)據(jù)，包含10 162個用戶，24 250個POI，共456 988條簽到。兩個數(shù)據(jù)集中每個用戶簽到至少5個POI，每個POI至少被5個用戶簽到，每個數(shù)據(jù)集被劃分為訓練集、測試集和調(diào)參集。本文使用每個數(shù)據(jù)集中的訓練集和測試集。

4.1.2 對比算法

為了驗證本文所提出的融入時間的POI協(xié)同推薦（TUCF）算法的性能，選用了以下對比算法驗證該算法的有效性：1）U算法［2］；2）具有平滑增強時間偏好的協(xié)同過濾（Uwith Temporal preference with smoothing Enhancement，UTE）算法［2］。

4.1.3 評價指標

本文采用評價指標：精確率Precision、召回率Recall、平均絕對誤差MAE來評估推薦算法的效果。在評估指標中涉及的符號和描述如表2所示。

表2 評估指標中的符號描述Tab.2 Description of symbolsused in evaluation indices

1）精確率和召回率。

采用文獻［2］中的方法評估推薦算法的精確率和召回率。Pre@N(t)和Rec@N(t)分別表示在時間片t推薦N個POI的精確率和召回率，計算如式（7）～（8）所示：

算法推薦N個POI的精確率Pre@N和召回率Rec@N是所有時間片的平均精確率和召回率，如式（9）～（10）所示：

2）平均絕對誤差。

在簽到張量中，如果用戶u在時間t對POIl進行了簽到則cutl=1，否則cutl=0，將其作為用戶評分。首先計算每個時間片上的平均絕對誤差MAE(t)，然后平均所有時間片上的MAE(t)，得到推薦算法的平均絕對誤差。每個時間片上的平均絕對誤差計算方法如式（11）所示：

推薦算法的平均絕對誤差MAE是所有時間片的平均值，計算方法如式（12）所示：

4.2 實驗結(jié)果與分析

本文TUCF算法與對比算法U和UTE的實驗結(jié)果及分析如下。文中的相似用戶數(shù)固定為500，推薦的POI個數(shù)N分別取5、10、15。

1）推薦算法的精確率和召回率。

TUCF、U和UTE算法在數(shù)據(jù)集Foursquare和Gowalla上的精確率和召回率如圖3所示。

從圖3可以看出：在兩個數(shù)據(jù)集上，考慮時間因素的UTE算法、TUCF算法均優(yōu)于未考慮時間因素的U算法，說明考慮時間因素可以提高POI推薦效果。同時TUCF算法的精確率和召回率均高于對比算法U和UTE。尤其是，在POI推薦數(shù)目N=5時，在Foursquare中TUCF算法比U算法在精確率以及召回率上分別提高了63%和69%，TUCF算法比UTE算法的精確率以及召回率分別提高了8%和12%，這表明采用時間關(guān)系平滑用戶簽到獲取相似用戶，以及利用相似用戶在相同時間片的訪問偏好，可以提高推薦效果。

圖3 推薦算法的精確率和召回率比較Fig.3 Comparison of precision and recall of recommendation algorithms

2）各時間片上的精確率和召回率。

本文以Gowalla數(shù)據(jù)集上的結(jié)果為例，結(jié)果如圖4所示，其中N=5。從圖4中可以看出，精確率和召回率的變化在兩個方法中相似，且TUCF算法在24個時間片上均高于UTE算法。在時間片11點時，兩個算法的精確率和召回率達到最高，在時間片9點時，精確率和召回率達到最低。尤其在時間片7點時，TUCF算法的精確率和召回率相比UTE算法分別改善了67%和50%。這說明采用時間關(guān)系平滑用戶簽到獲取相似用戶，以及利用相似用戶在相同時間片的訪問偏好，可以提高推薦效果。

圖4 不同時間片上的準確率和召回率比較Fig.4 Comparison of precision and recall on different time slices

3）MAE對比。

本節(jié)將推薦POI數(shù)量N固定為5，目標用戶的相似用戶數(shù)量M從50增長到2 000，分析相似用戶數(shù)量對算法的影響，以圖5所示的Foursquare數(shù)據(jù)集上的結(jié)果為例。

圖5 MAE比較Fig.5 Comparison of MAE

從圖5中可以看出當M取500時，取得較好的推薦效果，且對于不同的M，TUCF的MAE值均低于對比算法U和UTE。其中考慮時間因素的TUCF算法、UTE算法，MAE值均比未考慮時間因素的U算法低，說明考慮時間因素可以提高POI推薦效果。考慮時間因素的TUCF算法和UTE算法，TUCF算法的MAE值低于UTE算法，表明采用時間關(guān)系平滑用戶簽到獲取相似用戶，以及利用相似用戶在相同時間片的訪問偏好，可以提高推薦效果。

5 結(jié)語

本文分析基于位置的社交網(wǎng)絡的用戶簽到數(shù)據(jù)，探索用戶簽到的時間關(guān)系，并利用時間關(guān)系對用戶簽到數(shù)據(jù)進行平滑處理，然后基于用戶的協(xié)同過濾算法，提出了融入時間的協(xié)同過濾POI推薦算法。在兩個真實數(shù)據(jù)集Foursquare和Gowalla上的實驗結(jié)果表明，本文算法不僅可以有效緩解數(shù)據(jù)的稀疏性，還提高了POI推薦的精確率和召回率，減小了平均絕對誤差。

時間作為POI推薦的一個重要因素，除了一天內(nèi)不同時間對用戶簽到有影響，用戶的簽到行為還受星期或月份的影響，今后將進一步探索其他時間粒度。此外，POI通常具有類別信息，也將探索類別信息提高POI推薦效果的可能性。