葉繼華 楊思渝 左家莉 王明文

(江西師范大學計算機信息工程學院 南昌 330022)

1 引言

隨著基于位置的社交網(wǎng)絡(Location-Based Social Networking, LBSN)應用的迅速發(fā)展，Gowalla,Foursquare等平臺作為一種媒介捕捉到了大量的行為信息。然而，隨著信息量的爆炸式增長，如何提取用戶的有效信息，解決社交網(wǎng)絡所產(chǎn)生的數(shù)據(jù)冗余等問題也引起了該領域內各位專家學者的關注?；诖耍琍OI推薦作為當前推薦研究領域內的熱點，通過在LBSN中對不同用戶的不同簽到數(shù)據(jù)的挖掘及分析，為用戶尋求下一個新的位置提供了更為便捷的服務，增加了用戶體驗。

目前，國內外學者研究發(fā)現(xiàn)用戶行為會受到多種因素的影響，為了提高POI推薦的效果，可以通過對簽到用戶的活躍度[1]、時空遷移影響[2]、社交影響[3]和用戶簽到序列相關的上下文信息[4]等影響的分析進行個性化推薦，并且采用協(xié)同過濾[5]、矩陣分解[6]、深度學習[7,8]等方法來更好地挖掘用戶行為的潛在偏好，為用戶生成推薦列表。

在POI推薦研究中，將空間、時間的影響作為重要因素進行考慮，在POI推薦中有著不可替代的地位。文獻[9]發(fā)現(xiàn)距離越近，相似度越高越能提高POI推薦性能，但由于構建二叉樹的方法與空間上信息相關性較弱，因此仍需加入其他信息來提升預測效果。文獻[10]通過POI之間可接受性和影響性的不對稱性來分析不同地理影響對POI的推薦，由于僅僅著重對地理影響的深度研究，因此仍需綜合考慮不同因素對POI的影響。同樣，文獻[11]通過張量因式分解，利用切分的時間片段通過兩兩交叉的方式進行建模。然而在現(xiàn)實世界中，用戶訪問的POI個數(shù)會因為時間及頻率的影響而形成稀疏性的約束。因此，為了解決數(shù)據(jù)稀疏性問題，仍需增加相關信息。文獻[4]研究發(fā)現(xiàn)簽到的兩個POI之間的轉移概率是非均勻分布的，為此利用POI之間的內容語義和上下文關系進行建模，但由于提出的模型缺少對文本語義特征的考慮，因此并沒有很好地突出個性化。

目前，隨著對基于位置的感知社交數(shù)據(jù)可用性的深入研究，基于POI推薦的研究方向在各種算法及模型上也得到了不斷的更新及拓展，而不再只是停駐在特征因素分析的層面。例如文獻[6]將時間序列、空間兩種因素進行融合，從而提出了基于矩陣分解的POI推薦模型。雖然該模型表現(xiàn)效果較好，但由于未能解決數(shù)據(jù)稀疏性，因此在用戶與POI之間關聯(lián)不強時，其推薦效果欠佳。文獻[12]采用因式分解的方法通過對空間和時間建立模型，但是由于因式分解的算法難以自由靈活組合與用戶相關的各項指標，因此仍存在一定不足。文獻[7]通過對簽到數(shù)據(jù)中的用戶信息和評論信息的分析，采用矩陣分解和CNN的方式建立模型，雖然有效地避免了局部最優(yōu)的問題，但是對樣本的需求量較大。文獻[8]通過RNN網(wǎng)絡建立的模型，可以推導預測出用戶下一個簽到訪問軌跡的深度表示。雖然該模型的表現(xiàn)效果較為不錯，但仍未解決梯度消失的情況。

為了解決上述提出的問題，本文的主要工作如下：

(1)通過研究時間、空間上下文，探究用戶潛在行為模式。并且把空間、類別及時間等異構信息編碼整合，將融合后的上下文信息嵌入基于GRU[13]網(wǎng)絡的模型中?；跁r空上下文信息所建立的序列模型，不但可以較好地處理序列關系，打破因為單一信息所帶來的局限性，還能通過增加對用戶偏好的關聯(lián)性來緩解由簽到數(shù)據(jù)稀疏性所帶來的困難，從而提高了預測精度。

(2)在時空上下文信息的POL模型推薦(Spatio-Temporal Context information of POI Recommendations, STCPR)模型中，引入時間注意力機制、全局和局部的空間注意力[14]，獲取用戶的個性化偏好及移動行為，獲得更好的個性化POI預測。

(3)基于兩個真實數(shù)據(jù)集上的實驗結果表明，與現(xiàn)有的幾種方法進行對比，本文所提模型占據(jù)了相對優(yōu)勢，并且兩種注意力機制對模型效果的提升是有幫助的。

2 時空上下文信息的POI推薦

2.1 問題定義

定義1 (check-in行為) 每條打卡簽到紀錄h由一個4元組(u,y,t,C)構成，其含義為用戶u在t時刻基于用戶上下文C對某位置y的簽到行為。

定義2 (上下文信息) 用戶上下文信息C主要由xcat和xct來表示其序列相關性。xcat描述POI的內在屬性，主要考慮POI的類別屬性；xct表示用戶簽到的時序相關轉換信息，其中，通過相鄰兩次簽到信息的時間間隔以此代表時間轉換信息，通過當前簽到POI與上一次簽到POI之間的地理距離代表地理轉換信息。

定義3 (問題描述) 令U和P分別表示用戶集合和POI集合，對于用戶u ∈U，在給出當前查詢到的簽到地點Yt ∈P和當前查詢到的時間T的條件下，依據(jù)簽到歷史記錄H，推測用戶在t+1時刻可能感興趣的POI，并向用戶進行推薦。

2.2 融合空間注意力的GRU模型

由于不同用戶簽到信息長度不同，為了處理不同長度的序列信息，本文基于序列到序列(Sequence-to-sequence, Seq2seq)的框架進行建模。如圖1所示，在編碼框架(Encoder)中，主要將融合嵌入的異構數(shù)據(jù)輸入基于空間注意力的GRU的序列模型，在解碼框架(Decoder)中，通過對編碼過程輸入與輸出的處理，從而生成指定的序列。本文通過GRU編碼-解碼框架來學習概率分布，根據(jù)預測概率大小排序生成POI推薦列表，從而對用戶進行推薦。

圖1 時空上下文信息的POI推薦(STCPR)模型框架圖

對于編碼階段如圖1左側所示，首先通過對歷史數(shù)據(jù)的采集，對POI信息、用戶信息、類別信息以及上下文信息等信息都采用One-hot編碼，以統(tǒng)一的方式整合異構數(shù)據(jù)后，將拼接好的向量輸入編碼器中。

由于用戶對時間有著高度的敏感性，為了捕獲時間特征對于用戶行為的影響，通過時間的周期性和連續(xù)性兩個隱含特征，來對時間進行多維度的劃分。因此，我們將時間戳劃分為小時與周的形式。對一天通過h ∈{0,1,...,23}來表示24小時；通過w=0或1來表示工作日和休息日，最后通過One-hot編碼的拼接得到其潛在向量。

由于用戶的高流動性，且兩個POI之間的地理影響性和接受性是非均勻的，為了挖掘其上下文序列關系，本文通過時間間隔以及距離間隔來度量其上下文序列的影響。選擇不同的間隔會生成不同的空間，因此，加入兩個潛在向量cl,cs描述長、短兩個間隔之間的轉換。如

不可避免地，在不同POI之間存在或多或少的地理關聯(lián)，為了能夠更加準確地發(fā)現(xiàn)用戶的動態(tài)行為關系，引入基于空間的宏觀注意力層。考慮不同因素時空數(shù)據(jù)的相互關聯(lián)，測量出不同POI之間潛在向量的決策影響。

2.3 基于時間注意力的GRU模型

在解碼階段，由于每個簽到序列對下一個POI的貢獻和偏好不同，并且隨著編碼長度的增長性能會有所下降，因此引入時間注意力機制的GRU模型自適應地選擇相關的簽入活動，從而獲得更佳的推薦。

結束解碼階段后，通過一個全連接層，利用softmax函數(shù)輸出t時刻POI概率的目標函數(shù)，如式(8)，其中，u為用戶，T為前查詢時間，Yt為當前查詢的簽到地點，H為簽到的歷史數(shù)據(jù)。并且通過對目標函數(shù)的最大對數(shù)似然估計來對參數(shù)θ={u,H,Pt,T}進行學習。

3 實驗和結果分析

3.1 實驗設置

為了驗證本文所提STCPR模型的有效性，本節(jié)使用來自LBSN簽到的Gowalla和Foursquare數(shù)據(jù)集進行實驗，并通過評價指標進行分析。在TensorFlow的框架下進行不同參數(shù)的實驗對比，找到時間間隔閾值和地理距離閾值等參數(shù)最優(yōu)的取值。通過召回率和歸一化折損累計增益兩種評價指標，對STCPR變體從時間注意力機制和空間注意力機制上的影響性能進行對比分析，用以說明考慮時空注意力機制方法的有效性。最后，通過與其他現(xiàn)有方法的實驗和性能結果對比，分析STCPR模型有效性的原因。

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

本文在LBSN簽到的真實數(shù)據(jù)集Gowalla和Foursquare上進行實驗。將2009-2011年數(shù)據(jù)集中的POI通過7個類的基礎上再劃分為335個小類。基于此我們對兩個數(shù)據(jù)集進行了預處理，將數(shù)據(jù)集的70%作為訓練集，10%作為驗證集，20%作為測試集，刪除訪問少于10個POIs的用戶和少于10個用戶訪問的POIs，具體的信息如表1所示。

表1 數(shù)據(jù)集

3.3 評價指標

本文使用T召回率(Recall@N)和的歸一化折損累計增益(NDCG@N)來衡量和評價搜索結果。召回率作為應用廣泛的度量值，具體指推薦結果中用戶實際去的地點值占推薦列表的比例。其中，R(u)表示POI推薦列表的數(shù)量，T(u)表示用戶實際訪問POI的數(shù)量。NDCG是最受歡迎的排名評價指標，對于關聯(lián)度較高且排序靠前的對象，其NDCG指標會越高。其中，DCG是折損累計增益，IDCG為理想情況下最大的DCG。定義為

3.4 實驗過程與結果分析

3.4.1 參數(shù)選擇

本文實驗基于TensorFlow框架，將推薦列表長度N的取值分別為2, 5, 10，并采用了隨機梯度下降算法和Adam優(yōu)化器對參數(shù)進行更新，將其隱藏層的維度設置為{20, 40, 60}，并將批量大小設置為512。作為衡量地理相似度影響的超參數(shù)τ，通過經(jīng)驗固定取值在0.2～0.4?；诖耍覀冞M行了多次的實驗對比，確定了最優(yōu)超參數(shù)的組合。

如圖2所示，分別表示在Gowalla和Foursquare數(shù)據(jù)集上實驗選擇合適的學習率α。將學習率范圍設置為0.001到0.1，在Gowalla數(shù)據(jù)集中當推薦列表長度N值取2, 5和10時，α=0.01的召回率分別是0.1526, 0.2121和0.2654，與其他值相比效果最好。同樣地，在Foursquare數(shù)據(jù)集上，在相同推薦列表長度N值的情況下α=0.01時，相較于其他學習率效果更好。當N=10時學習率α效果最好，且為0.2703。

圖2 在不同數(shù)據(jù)集上學習率α 對召回率的影響

為了研究序列長度的影響，如圖3，考慮N=2,5,10時的召回率在其不同簽到數(shù)據(jù)序列長度{5, 10, 15, 20, 25}的取值。隨著簽到序列長度的增加，模型的效果也在不斷提升。當簽到序列長度為15時，在兩個數(shù)據(jù)集中歸一化值為1表現(xiàn)效果最佳。但隨著簽到序列長度的增加，計算復雜度增加，使得模型的效果下降。特別是Gowalla數(shù)據(jù)集中下降的速度比Foursquare數(shù)據(jù)集下降得更快。因此，當序列長度為15時，模型的性能表現(xiàn)更佳。

圖3 簽到序列長度在不同數(shù)據(jù)集上的變化

為了更深入地探索時間對于用戶移動行為的影響，通過將時間分片，來確定時間間隔對用戶行為產(chǎn)生的影響。當時間間隔πt的分別取值為0, 3, 6,9及12時，以N取2, 5, 10的召回率來對時間間隔敏感性進行度量。

如圖4可知，在Gowalla數(shù)據(jù)集上，發(fā)現(xiàn)當時間閾值πt=3h效果最佳，且隨著時間的增長，閾值的趨勢較為穩(wěn)定。同樣地，在Foursquare數(shù)據(jù)集中，當時間間隔增加到3 h時，其歸一化值為1，模型的性能取得了更好的表現(xiàn)。但是3 h后，隨著時間間隔的增大，模型的性能開始出現(xiàn)逐漸下降的趨勢，其中，當時間間隔處于6～12 h范圍內時，隨著間隔的增大，F(xiàn)oursquare數(shù)據(jù)集中模型性能下降速度相較于Gowalla數(shù)據(jù)集幅度更大，因此設置最佳的時間間隔的閾值為πt=3。

圖4 時間閾值π t在 不同數(shù)據(jù)集上的變化

為了確定用戶的簽到行為具有強烈的地理屬性限制，通過對地理間隔的實驗來確定其最佳閾值。在圖5的Gowalla數(shù)據(jù)集中，當召回率為10時，其距離間隔πd=10時達到最佳。雖然召回率為10時，12的距離間隔是最佳，但在πd=10時其歸一化值為0.998，接近最佳。因此在Gowalla數(shù)據(jù)集中將距離間隔閾值πd=10設置為10 km。同樣地，在Foursquare中雖然在9 km時，Recall@2在模型中效果最佳。但隨著地理距離閾值的變大，召回率也在增長，當距離間隔πd=10時達到最佳，且歸一化值為1。因此，本文將距離間隔閾值πd設置為10 km。

圖5 距離閾值π d在不同數(shù)據(jù)集上的變化

3.4.2 實驗過程

為了評估POI推薦算法的性能，選取以下幾組不同方法和本文提出的STCPR模型對比，以驗證本文模型的有效性。

FPMC[15]：是個性化馬爾可夫鏈模型的代表，通過在時間序列上觀測和模擬用戶偏好，來建立矩陣模型，解決其數(shù)據(jù)稀疏的問題。

Distance2Pre[16]：通過建立連續(xù)POIs之間的距離交互關系來獲取基于空間的RNN模型。

ST-RNN[17]：通過考慮空間及時間的上下文影響，在簽到序列中，將時間間隔和空間間隔以轉移矩陣的方式表示一種特殊距離的設定。將空間及時間這兩種特征導入到RNN的網(wǎng)絡結構中。

GRU[18]：是RNN模型的一個變體，為了研究注意力的影響。

UCGSMF_GEN[19]：從用戶簽到的地理位置、社交網(wǎng)絡數(shù)據(jù)和POI類別信息等方面建立一個通用的矩陣分解模型。

MFM-HNN[7]：基于擴展的矩陣分解模型融合評論信息特征和用戶簽到信息的初始值進行興趣點推薦。

3.4.3 結果分析

為了驗證本文模型的相關性能，對其STCPR模型通過不同的影響因素設置不同的變體并進行比較，結果如圖6和圖7所示。主要分為簡單的GRU模型，考慮時間注意力機制的STCPR-T模型，考慮空間注意力機制的STCPR-S模型這3類變體。結果表明，簡單的GRU網(wǎng)絡，由于沒有考慮隨著時間增加而引起的衰減效果，因此效果最不明顯。在STCPR-S和STCPR-T兩個模型中，其性能效果比較接近，但是STCPR-T改進更加顯著。對于STCPR模型來說，在考慮了時間、空間的上下文信息的同時，還對用戶的空間意圖進行了多層次分析。因此，STAPR模型在兩個數(shù)據(jù)集上表現(xiàn)都明顯較好。

圖6 Gowalla數(shù)據(jù)集上STCPR不同變體對比

圖7 Foursquare數(shù)據(jù)集上STCPR不同變體

為了觀測各種模型在不同N值時Recall和NDCG的實驗效果，通過在Gowalla和Foursquare上進行多次實驗比較，結果如表2所示。在N值增加的情況下，各種模型的歸一化損失和召回率都出現(xiàn)了一定程度的提高，但與其他模型相比，本文提出的STCPR模型的提高最為明顯。

表2 不同方法在兩個數(shù)據(jù)集上的實驗結果(%)

當Recall@10時，與考慮了時間、空間影響的傳統(tǒng)神經(jīng)網(wǎng)絡模型相比，STCPR模型性能表現(xiàn)分別要高出15.19%和16.16%。STCPR模型表現(xiàn)更高的主要原因在于RNN模型對實際序列數(shù)據(jù)的處理存在一定的局限性，如缺少長期依賴，短期記憶比長期記憶更具有影響力，從而出現(xiàn)梯度爆炸和梯度消失等情況。因此，在捕獲用戶興趣方面GRU神經(jīng)網(wǎng)絡比RNN有著更優(yōu)異的表現(xiàn)。當與最簡單的GRU網(wǎng)絡進行比較時，因其不對各種影響因素進行細粒度分析，相較于對用戶偏好多樣性分析的模型來說，其推薦效果略差。但與將矩陣分解和馬爾可夫鏈結合起來的FPMC模型相比，效果要略好一些。以RNN網(wǎng)絡為基礎的基于個性化空間影響的Distance2Pre模型，由于深入全面地考慮用戶與地理影響之間關系，減少了由數(shù)據(jù)稀疏所帶來的問題。但由于在序列關系中，對長短期的記憶影響考慮不足，同STCPR相比其模型分別降低了12.6%和12.06%。UCGSMF_GEN模型由于綜合考慮了用戶自身偏好、地理位置和社交網(wǎng)絡信息來建模用戶簽到行為，因此它的推薦效果優(yōu)于GRU和FPMC模型。相比于UCGSMF_GEN，本文提出的STCPR模型的推薦性能提高了17.12%和17.68%，主要由于深度神經(jīng)網(wǎng)絡能夠很好地將簽到信息的特征和潛在特征向量融合起來，相比于矩陣分解模型在特征訓練方面有著顯著優(yōu)勢。對于MFM-HNN模型來說，由于Gowalla數(shù)據(jù)集沒有提供評論信息，因此主要考慮評論信息的MFM-HNN模型僅在Foursquare數(shù)據(jù)集上進行方法對比。相對于考慮詞序及上下文信息的MFM-HNN模型來說，STCPR模型性能效果高出13.14%左右，其原因在于，相比社交信息和地理信息對于POI推薦性能的影響，評論文本信息的影響較小。

同樣地，當NDCG@10時模型性能達到最佳，在兩個數(shù)據(jù)集中相對較好的是Distance2Pre模型，由于其基于序列的方式分析了地理信息的可接受性和影響性，因此獲得較好的性能。但由于其既沒有融入有效的上下文信息，又沒有關注用戶對不同POI簽到序列的偏好差異，因此其效果略低于融合時空上下文信息的STCPR模型。MFM-HNN模型由于充分考慮詞序及上下文信息對學習的潛在特征表示的影響，因此在Foursquare數(shù)據(jù)集上表現(xiàn)也較好，但相對于本文提出的STCPR模型來說，它沒有挖掘用戶的長期偏好。由于沒有使用合適的排序技術，在召回率中表現(xiàn)較好的ST-RNN和UCGSMF_GEN模型在排序指標NDCG中的表現(xiàn)效果卻不盡如人意。同樣地，對于傳統(tǒng)的FPMC模型來說，雖然在用戶-項目的推薦模式下通過矩陣分解的方法有著較為不錯的表現(xiàn)，但相對于其他基于序列影響的模型而言無法產(chǎn)生相對較好的效果。GRU網(wǎng)絡作為本文模型的基礎，通過在兩個真實數(shù)據(jù)集下的實驗對比，實驗結果充分表明了結合空間及時間影響的注意力機制的重要性。

4 結束語

本文提出了一種基于時空上下文信息的POI推薦(STCPR)模型用于POI的推薦。為了緩解數(shù)據(jù)稀疏帶來的困難和打破單個序列信息的有限性，基于Seq2seq的框架結構，將地理距離、時間和POI分類等上下文信息，利用嵌入方法來整合輸入編碼-解碼器的GRU模型中。此外，還引入時間與空間注意力機制來挖掘與分析用戶的動態(tài)行為與個性偏好，從而實現(xiàn)更有效的個性化POI預測。實驗結果表明，本文提出的STCPR模型在召回率和歸一化折損累計增益方面均優(yōu)于現(xiàn)有的幾種方法，并且兩種注意力機制都能有效地提高推薦性能。

在未來的工作中，計劃融合更多有效的多源數(shù)據(jù)，幫助克服單一信息所帶來的不足。其次，通過實驗來查看不同密集度數(shù)據(jù)集對POI推薦模型表現(xiàn)的限制，并針對數(shù)據(jù)稀疏問題提出相應的解決方案。最后，希望在提高推薦性能的同時增加其模型的可解釋性，從而提升用戶的體驗感。