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

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 時空網(wǎng)絡(luò)自注意力模型

2.1 問題描述和問題定義

2.1.1 問題描述

在融合時空網(wǎng)絡(luò)和自注意力的興趣點序列推薦系統(tǒng)模型中，模型通過用戶的歷史簽到序列數(shù)據(jù)，預(yù)測用戶接下來將要去的3個連續(xù)地點的POI序列，比如用戶去過的簽到序列為 [Pseq1,Pseq2,Pseq3,…,PseqH]， 需要預(yù)測的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 模型結(jié)構(gòu)

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

圖1 模型結(jié)構(gòu)

2.2.1 Embedding層

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

2.2.2 GRU-SelfAttention層

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

圖2 GRU模型結(jié)構(gòu)

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

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

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

圖3 GRU-SelfAttention層結(jié)構(gòu)

Q′=WQyt

(11)

K′=WKyt

(12)

V′=WVyt

(13)

(14)

2.2.3 興趣點匹配層

根據(jù)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運算是最后一個維度的加權(quán)和，將A(U)的維度轉(zhuǎn)化成R3*M。

2.2.4 損失函數(shù)

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

(17)

2.2.5 算法設(shè)計

在融合時空網(wǎng)絡(luò)和自注意力的興趣點序列推薦系統(tǒng)模型中，用戶序列數(shù)據(jù)構(gòu)造和模型訓(xùn)練過程如算法1所示。

算法1：STSASP算法

輸入：用戶簽到數(shù)據(jù)，地點位置信息

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

//構(gòu)造訓(xùn)練數(shù)據(jù)

(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

//模型訓(xùn)練

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

3 實 驗

3.1 實驗配置

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

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

表1 數(shù)據(jù)集基本信息

3.1.2 評價指標(biāo)

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

(18)

3.1.3 參數(shù)設(shè)置

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

3.2 實驗分析

3.2.1 本文實驗

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

圖4 在Foursquare和Gowalla數(shù)據(jù)集上不同K值的召回率

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

3.2.2 對比實驗

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

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

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

(3)STRNN。該方法是在循環(huán)神經(jīng)網(wǎng)絡(luò)中融合時空信息特征的地點推薦算法。

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

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

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

表2和圖5展示了以召回率@5和召回率@10為評價指標(biāo)，各方法在Foursquare和Gowalla數(shù)據(jù)集上的表現(xiàn)。

圖5 各方法在Foursquare和Gowalla數(shù)據(jù)集上的表現(xiàn)

表2 各方法在Foursquare和Gowalla數(shù)據(jù)集上的表現(xiàn)

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

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

3.2.3 超參數(shù)分析

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

圖6 超參數(shù)分析

3.2.4 消融實驗

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

圖7 Foursquare和Gowalla數(shù)據(jù)集上STSASP和STSASP1不同K值的召回率

4 結(jié)束語

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