融合時空網絡和自注意力的興趣點序列推薦

朱建豪，馬文明，王 冰，武 聰

(煙臺大學 計算機與控制工程學院，山東 煙臺 264005)

0 引 言

在現實生活中，用戶的簽到行為通常發生在一個序列中，推薦系統通過用戶的歷史簽到記錄和當前的簽到狀態，來為用戶推薦接下來可能去的興趣點。目前先進的序列推薦算法通過綜合計算用戶的長期偏好和短期偏好進行POI推薦，比如用戶X是一個體育愛好者，平時喜歡去籃球場打籃球，當他放假準備行李坐飛機外出旅游時，推薦系統會根據用戶短期偏好進行相關景點推薦，而不會根據用戶長期偏好進行籃球場等相關地點推薦。然而目前序列推薦算法存在一些問題，沒有考慮有效利用用戶簽到地點之間的時間和空間間隔的信息，不能夠準確地表達用戶的偏好，用戶的簽到行為可能為用戶提供了關鍵信息，比如用戶V星期五公司下班后，習慣去公司周圍籃球場打籃球，然后在附近餐廳吃飯，到了星期六，用戶會在家周圍的籃球場打籃球并在附近餐廳吃飯，這種簽到之間的時間間隔和空間間隔信息會為用戶推薦在籃球場附近的餐廳以及下一步的行動[1,2]。

為此，本文提出一種融合時空網絡和自注意力的興趣點序列推薦系統模型(sequential recommendation of point of interest combines spatio-temporal network with self-attention，STSASP)，為用戶推薦一個POI序列。以經緯度表示POI的地理位置，計算用戶簽到行為之間的時間間隔以及簽到地點之間的空間間隔，將時空間隔信息融入門控循環單元(gated recurrent unit，GRU)模型中，捕捉用戶反饋數據的序列性，同時使用自注意力(self-attention)機制在簽到序列上為每次簽到分配不同的權重，反映用戶的長期偏好，最后通過時空間隔信息為用戶匹配POI序列。

1 相關工作

傳統的推薦系統分為：基于內容的推薦系統和協同過濾的推薦系統，都是以靜態方式對用戶反饋數據進行建模，只能捕獲用戶的一般偏好。隨著時間的推移，用戶的交互行為和用戶的偏好很有可能發生改變，傳統的推薦系統忽略了用戶偏好的動態變化，所以傳統的推薦系統不能有效地處理POI推薦問題。

序列推薦系統把用戶歷史數據看作一個動態序列，在用戶項目序列中，通過考慮用戶順序行為和歷史數據的相互依賴性預測用戶的偏好，從而更加精確地進行推薦[3]。序列推薦主要有兩種模型：基于馬爾可夫[4]的模型和基于深度學習[5]的模型。馬爾可夫模型通過轉移概率矩陣預測下一個行為的概率，但由于序列數據的稀疏性，FPMC[6]模型被提出，該方法將矩陣分解機和馬爾可夫鏈相結合提取序列信息，考慮用戶偏好。但是在處理高階順序依賴關系時，高階馬爾可夫鏈[7]模型因參數數量隨階數指數增長，其分析歷史狀態有限。因此基于深度學習的序列推薦系統模型迅速發展起來，其中循環神經網絡(recurrent neural network，RNN)[8]最具有代表性并在各個應用上表現良好。然而隨著輸入序列長度的增加，RNN無法學習和利用前面的信息，面臨著長期依賴、梯度爆炸問題[9]，文獻[10,11]分別使用長短期記憶模型(long-short term memory，LSTM)和門控循環單元模型來解決這一問題，它們能夠對有價值的交互信息進行長期記憶，并且可以較好地解決梯度消失和爆炸問題，從而提升網絡模型的學習能力。

進一步研究發現，將時間和空間信息融入模型中能夠提升推薦結果。STRNN[12]將時間和空間信息融入到循環神經網絡，考慮連續兩次交互的時間和距離間隔，通過轉移矩陣融合時空信息。LSTPM[13]聚集用戶最近訪問位置，將地理因素融入RNN中。Time-LSTM[14]在LSTM中加入時間門。STGN[15]通過添加時空門進一步增強了LSTM結構。但是由于RNN的超強假設，序列中任何相鄰的交互假設都是相互依賴的，容易產生錯誤的依賴關系。注意力機制[16]能夠為不同的序列數據賦予不同的權重，有效捕捉用戶長序列數據之間的相互依賴。SASRec[17]使用自注意力進行序列推薦，DeepMove[18]通過注意層和循環層學習長期周期性和短期序列規律。ATST-LSTM[19]使用注意力機制為每個交互分配不同的權重，但只考慮了連續訪問。CSALSR[20]融合自注意力機制與長短期偏好進行序列推薦，但是沒有考慮時間間隔和空間間隔的信息。

2 時空網絡自注意力模型

2.1 問題描述和問題定義

2.1.1 問題描述

在融合時空網絡和自注意力的興趣點序列推薦系統模型中，模型通過用戶的歷史簽到序列數據，預測用戶接下來將要去的3個連續地點的POI序列，比如用戶去過的簽到序列為 [Pseq1,Pseq2,Pseq3,…,PseqH]， 需要預測的POI序列為Pj=[PseqH+1,PseqH+2,PseqH+3]。

2.1.2 問題定義

(1)

(2)

(3)

其中，r為地球半徑6371 KM。計算地點集合P=[P1,P2,P3,…,PM] 中每個地點與用戶簽到序列C(Ui)=[Pseq1,Pseq2,Pseq3,…,PseqH] 中每個地點的空間距離，計算3次來填充矩陣，用E(N)表示；計算POI序列Pj=[PseqH+1,PseqH+2,PseqH+3] 中每次簽到與簽到序列中 [Pseq1,Pseq2,Pseq3,…,PseqH] 中每次簽到的時間間隔，計算M次來填充矩陣，用E(S)表示，E(S),E(N)∈R3*M*H。

2.2 模型結構

本文提出了融合時空網絡和自注意力的興趣點序列推薦系統模型，模型的輸入為用戶的歷史簽到數據Pseqi=[Ui,Pi,Ti] 和地點數據Pi=[Pi,lngi,lati]， 將數據通過Embedding層，接著將用戶簽到序列以及時間間隔和空間間隔信息通過GRU模型，然后通過自注意力機制對簽到時序地點進行建模，得到用戶簽到序列的更新表示，最后通過興趣點匹配候選地點，模型的輸出為包含3個連續地點的POI序列。模型結構如圖1所示。

圖1 模型結構

2.2.1 Embedding層

將用戶歷史簽到數據中的用戶、地點和時間進行Embedding，轉化為密集Embedding表示，以向量化的形式輸入到網絡模型中。Embedding層的輸出為C(Ui)=[Pseq1,Pseq2,Pseq3,…,PseqH]。

2.2.2 GRU-SelfAttention層

GRU模型能夠很好地學習和利用用戶的歷史簽到序列數據，在每一步接收序列中的數據輸入和上一個隱藏層的輸出，并輸出到隱藏層，將用戶簽到序列的時間間隔和空間間隔信息融入GRU模型中，增加時間門和空間門后的GRU模型結構如圖2所示。

圖2 GRU模型結構

rt=σ(Wr[ht-1,xt])

(4)

zt=σ(Wz[ht-1,xt])

(5)

Tt=σ(Wt[xt,Δt])

(6)

Dt=σ(Wd[xt,Δd])

(7)

h′t=tanh(Wh′[rt*ht-1,xt*Tt*Dt])

(8)

ht=zt*h′t+(1-zt)*ht-1

(9)

yt=σ(Wyht)

(10)

其中，xt和ht-1分別表示當前時間t的輸入向量和上一時間t-1的輸入向量，rt和zt分別表示重置門和更新門，通過xt和ht-1來獲取兩個門的狀態。Tt和Dt分別表示時間門和空間門，將用戶簽到地點之間的時間間隔和空間間隔信息融入到GRU模型中，Tt和Dt分別控制當前地點的時間信息和空間信息對將來POI推薦的影響。其中Δt,Δd分別表示兩個地點之間的時間間隔和空間間隔。Δd通過兩個地點經緯度坐標的Haversine距離公式計算得到，Δt通過兩個地點之間時間差得到。xt*Tt*Dt表示通過時間門Tt和空間門Dt控制當前地點的時間和空間信息對于POI推薦的影響。σ和tanh分別代表sigmoid激活函數和tanh激活函數，Wr,Wz,Wt,Wd,Wh′,Wy為權重矩陣，*表示基于矩陣元素中對應元素相乘運算。rt*ht-1表示通過重置門rt控制上一時間輸入需保留的信息，再與當前輸入進行拼接。zt*h′t通過更新門zt控制當前時間輸入的信息量，進行選擇性記憶，后半部分再通過1-zt選擇性遺忘上一時間輸入的信息量。yt∈RH*d表示模型的輸出。

在POI序列推薦的預測中，用戶的歷史簽到地點中可能只有某些地點對預測的POI序列有影響，因此，引入注意力機制，可以幫助模型為用戶簽到數據賦予不同的權重，動態地捕捉每一個用戶的重點信息。

自注意力機制是一種特殊的注意力機制[21]，在動態賦予權重的同時，捕捉了用戶反饋數據之間的相互依賴，并在長序列的數據上表現出色，因此，本文考慮將自注意力機制應用于用戶簽到反饋數據，在用戶簽到序列內為每次訪問分配不同的權重。Query,Key,Value分別表示自注意力機制中的查詢、索引、需要被加權的數據。yt∈RH*d表示GRU模型的輸出，GRU-SelfAttention層的結構如圖3所示。

圖3 GRU-SelfAttention層結構

Q′=WQyt

(11)

K′=WKyt

(12)

V′=WVyt

(13)

(14)

2.2.3 興趣點匹配層

根據GRU-SelfAttention層輸出的用戶簽到長期偏好表示S(U)∈RH*d， 以及地點矩陣E(P)∈R3*M*d， 時空間隔矩陣E(S),E(N)∈R3*M*H， 從所有地點中為用戶選出將來可能去的POI序列

(15)

A(U)=Sum(softmax(B(U)))

(16)

Sum運算是最后一個維度的加權和，將A(U)的維度轉化成R3*M。

2.2.4 損失函數

POI序列推薦屬于隱反饋推薦模型，將用戶沒去過的地點隨機設置為負樣本。給出用戶簽到序列C(Ui)， 候選地點Pj=[PseqH+1,PseqH+2,PseqH+3]∈A(Ui)， 其中j∈[1,M]，Pk表示正樣本，模型使用交叉熵損失函數進行訓練

(17)

2.2.5 算法設計

在融合時空網絡和自注意力的興趣點序列推薦系統模型中，用戶序列數據構造和模型訓練過程如算法1所示。

算法1：STSASP算法

輸入：用戶簽到數據，地點位置信息

輸出：用戶的簽到序列，推薦POI序列

//構造訓練數據

(1)For user in (1, number):

(2) Check-in order by time

(3)Pi=(lngi,lati)

(6)C(Ui)=[Pseq1,Pseq2,Pseq3,…,PseqH]

(7)End

//模型訓練

(8)For a in (1, epoch):

(9) For b in (1,batch):

(10) POI=Model(C(Ui),Δt,Δd)

(11) Select the POI sequence from all locations

(12) Loss=Loss(POI，Label)

(13) Recommend POI sequence in different K

(14)Recall@K=(POI，Label)

(15) End

(16)End

在STSASP算法中，首先將輸入的用戶簽到序列數據按照時間順序進行升序排序，然后根據地點的地理位置信息和簽到時間信息計算空間距離和時間間隔，構造每一個用戶的簽到序列。接著將用戶簽到序列信息以及時空間隔信息送入模型中進行訓練，計算損失函數，從所有的候選地點中為推薦POI序列，通過不同的前K項值來比較實驗結果，最后以召回率為評價指標和其它算法進行對比。本算法的時間復雜度T(n)=O(n2)， 空間復雜度S(n)=O(n)。

3 實 驗

3.1 實驗配置

3.1.1 數據集

本文在真實簽到數據集Foursquare[22]和Gowalla[23]上進行訓練和測試。Foursquare數據集是用戶在紐約市長期登機簽到加密數據集。Gowalla數據集是社交簽到類應用場景下的用戶行為日志。剔除在數據集中出現次數少于10次的地點，將用戶簽到序列中的地點按照簽到時間順序升序排列。將連續的時間戳分為7*24=168維，表示用戶一天或一周的簽到行為，用來反映周期性。將80%數據作為訓練集，20%數據作為測試集。訓練時，將用戶簽到序列前h項作為簽到數據，比如 [Pseq1,Pseq2,Pseq3,…,Pseqh]，h后3個地點作為將要去的包含3個連續地點的POI序列，比如 [Pseqh+1,Pseqh+2,Pseqh+3]。 數據集的基本數據信息：用戶、地點、簽到見表1。

表1 數據集基本信息

3.1.2 評價指標

針對上述數據集，本文選擇召回率(Recall)作為評價指標，Recall@K表示為用戶推薦前K項中的正樣本在原始正樣本中的比例。為用戶推薦一個包含3個連續地點的POI序列，召回率越高，表示推薦結果越好

(18)

3.1.3 參數設置

本文使用Adam優化器進行模型優化訓練，學習率為0.003，迭代訓練次數為20，丟棄率Dropout[24]為0.2，每個batch的大小為1024，模型Embedding的維度為50，負樣本數量為10。

3.2 實驗分析

3.2.1 本文實驗

本文首先考慮為用戶推薦不同長度地點的POI序列，POI序列長度分別為1個地點，包含2個連續地點的POI序列，包含3個連續地點的POI序列，圖4(a)和圖4(b)分別展示了以召回率@K為評價指標，在Foursquare數據集和Gowalla數據集上，STSASP模型為用戶推薦不同長度地點的POI序列的表現。

圖4 在Foursquare和Gowalla數據集上不同K值的召回率

1個POI、2個POI、3個POI分別表示為用戶推薦1個POI、2個連續地點的POI序列、3個連續地點的POI序列。實驗結果表明，為用戶連續推薦多個POI時，Recall@K會有一定程度的下降。在POI序列推薦中，順序因素為關鍵，要求推薦的POI序列是用戶將來連續要去的地點，并且順序要對應正確，所以為用戶推薦3個地點的POI序列相比與較少地點的POI序列在召回率上會相應下降。不同的K值對于POI序列推薦的結果是不同的，在Foursquare和Gowalla數據集中，隨著K值的增大，為用戶推薦前K項中的正樣本在原始正樣本中的比例也在增大，召回率也會相應的增大。本文最終選擇為用戶推薦1個包含3個地點的POI序列。

3.2.2 對比實驗

為了驗證STSASP模型的推薦效果，將STSASP模型與其它6種地點推薦算法分別在Foursquare和Gowalla數據集上進行比較和分析：

(1)BPR[25]。該方法將貝葉斯個性化排名與矩陣分解相結合，分析潛在語義信息。

(2)FPMC。該方法將矩陣分解機和馬爾可夫鏈相結合，捕獲用戶順序行為。

(3)STRNN。該方法是在循環神經網絡中融合時空信息特征的地點推薦算法。

(4)DeepMove。該方法通過注意力循環網絡來進行地點推薦，捕獲用戶行為周期性。

(5)LSTPM。該方法結合了長期和短期順序模型進行地點推薦。

(6)CSALSR。該方法是融合自注意力機制和長短期偏好的序列推薦模型。

表2和圖5展示了以召回率@5和召回率@10為評價指標，各方法在Foursquare和Gowalla數據集上的表現。

圖5 各方法在Foursquare和Gowalla數據集上的表現

表2 各方法在Foursquare和Gowalla數據集上的表現

實驗結果表明，基于深度學習的序列推薦系統模型優于傳統馬爾可夫序列推薦模型，主要原因是深度學習模型通過非線性方式對用戶地點進行建模，能夠捕獲到序列中的復雜關系，同時在模型訓練過程中，通過正則化、Dropout等技術避免過擬合，能夠提高模型魯棒性。

STSASP在整體上都優于融合自注意力機制和長短期偏好的CSALSR模型，STSASP在Foursquare數據集上為用戶推薦3個連續地點的POI序列的召回率@5和召回率@10分別為0.131、0.194，在Gowalla數據集上分別為0.103、0.151，相比于CSALSR模型，STSASP在Foursquare數據集上和Gowalla數據集上的召回率分別提升了19.63%、22.01%和10.75%、11.02%。實驗結果表明，相比于CSALSR通過融合自注意力機制和長短期偏好，忽略了時間間隔和空間間隔信息進行序列推薦，STSASP從用戶簽到反饋序列數據中提取了有效的時間和空間信息，更充分地獲取了用戶的偏好，召回率更高，推薦結果更好。

3.2.3 超參數分析

Embedding的維度參數對模型的效果存在影響，保持其它參數不變，在召回率@20時，選擇不同維度參數d在數據集上進行實驗。圖6展示了關于超參數分析的實驗結果。圖6(a)反映了維度參數d在不同數據集上對模型推薦效果的影響，可以發現，高維度能夠更精確地表達用戶和地點，有助于模型歷史信息地交互。隨著維度的增加，召回率在相應地提高，但是更大的維度不一定能帶來更好的模型性能。在本文中，設置維度參數d為50。模型的丟棄率Dropout對模型的效果存在影響，由圖6(b)可知當Dropout為0.2時，模型有較好的效果。

圖6 超參數分析

3.2.4 消融實驗

STSASP1為STSASP消去時間間隔和空間間隔的模型，由圖7可知，STSASP1模型在失去時空間隔信息后，無法有效地表達用戶的偏好，因此表現不佳，在Foursquare和Gowalla數據集上的Recall@5和Recall@10上分別降低了27.48%、23.71%和20.42%、19.03%，在K大于20后，Gowalla數據集中STSASP1與STSASP的差距越來越大，原因是在多地點的環境中，時空因素對推薦結果的影響更大。通過比較發現CLALSR模型效果略優于STSASP1，因此說明了時間間隔和空間間隔對模型的重要性。

圖7 Foursquare和Gowalla數據集上STSASP和STSASP1不同K值的召回率

4 結束語

本文提出了融合時空網絡和自注意力的興趣點序列推薦系統模型，模型用于預測用戶將來要去的POI序列。本模型將用戶簽到序列的時間和空間間隔信息融入GRU模型中，然后通過自注意力機制對簽到時序地點進行建模，得到用戶的長期偏好序列，最后通過簽到地點與候選地點的時間間隔和空間間隔匹配候選地點，為用戶推薦包含3個連續地點的POI序列，更好地解決了POI序列推薦問題。在Foursquare數據集和Gowalla數據集上進行測試和驗證，實驗結果表明本文提出的STSASP模型優于之前提出的先進的模型。同時通過消融實驗，驗證了時間間隔和空間間隔因素在興趣點序列推薦模型中的重要性。在今后的工作中，將考慮進一步優化網絡結構，優化算法的時間復雜度和空間復雜度，從而進一步提升模型性能和推薦精度。