劉樹越，于亞新，吳曉露，夏子芳，王子騰

1(東北大學 計算機科學與工程學院，沈陽 110819) 2(東北大學 醫(yī)學影像智能計算教育部重點實驗室，沈陽 110169)

1 引 言

無線網(wǎng)絡(luò)和定位技術(shù)的不斷創(chuàng)新，使得用戶能夠隨時隨地利用智能設(shè)備記錄自己當前的地理信息[1]，產(chǎn)生了海量時空數(shù)據(jù)，造成信息過載.如何有效的處理數(shù)據(jù)量持續(xù)上升的時空數(shù)據(jù)，挖掘用戶有意義的運動行為模式，為用戶推薦可靠的POI[2]受到了人們的普遍關(guān)注.

傳統(tǒng)的POI推薦通常會根據(jù)位置、時間或者評論信息等向用戶推薦POI，但是傳統(tǒng)方法僅僅從靜態(tài)的角度出發(fā)考慮用戶和POI之間的關(guān)系，無法有效地捕獲用戶的動態(tài)偏好.與傳統(tǒng)的POI推薦不同，POI序列推薦考慮了用戶的順序移動模式，利用用戶的歷史簽到序列，從中挖掘用戶的動態(tài)偏好，根據(jù)該偏好為用戶提供準確的POI推薦.典型的解決方案有馬爾可夫鏈MC(Markov Chain)，循環(huán)神經(jīng)網(wǎng)絡(luò)RNN(Recurrent Neural Network)以及自注意力SA(Self Attention)機制，它們都能夠從用戶的歷史簽到序列中捕獲用戶的動態(tài)偏好.基于馬爾可夫鏈的方法[3，4]，用戶狀態(tài)間的轉(zhuǎn)移僅依賴于前n個狀態(tài).此方法已經(jīng)被成功地用來捕獲推薦系統(tǒng)中的短期項目過渡，但是馬爾可夫鏈難以捕獲較長的上下文序列并且計算復雜度較高.循環(huán)神經(jīng)網(wǎng)絡(luò)RNN[5，6]也被應(yīng)用到推薦中，包括長短期記憶網(wǎng)絡(luò)LSTM[7](Long Short-Term Memory)和門控循環(huán)單元GRU[8](Gated Recurrent Unit).雖然它們可以解決長期依賴問題，但是每一時刻的狀態(tài)輸入都需要等待上一時刻狀態(tài)輸出完成，不能捕獲全局信息，另外也不適合并行計算.相較于馬爾可夫鏈和循環(huán)神經(jīng)網(wǎng)絡(luò)，自注意力機制[9]的提出有效地解決該問題.在序列推薦中，采用自注意力機制處理用戶簽到序列能夠較好地捕獲全局信息，而且可以實現(xiàn)并行處理.

然而，基于上述模型的POI序列推薦在處理用戶與POI的交互數(shù)據(jù)時，都是將用戶的歷史簽到數(shù)據(jù)假設(shè)為有序序列，而不考慮每個交互之間的時間間隔(即它們建模的是時間順序，而不是實際的時間戳).顯然，這不符合實際情況.即使用戶的POI簽到順序相同，但具有更短時間間隔的POI將會對推薦效果產(chǎn)生更大的影響.另外，POI之間的地理距離以及語義信息也是影響推薦的重要因素.因此，本文提出了自注意力下時空-語義相融合的POI序列推薦模型SA-TDS-PRec(POI sequence recommendation model based on the integration of spatiotemporal and semantics under self-attention)，主要貢獻如下：

1) 提出自注意力下時空-語義相融合的POI序列推薦模型SA-TDS-PRec，將用戶簽到數(shù)據(jù)之間的時間間隔、空間間隔以及語義相關(guān)性進行結(jié)合，利用自注意力機制捕獲用戶動態(tài)偏好的演化，從而提升POI推薦的準確性.

2) 提出基于行為語義序列的POI關(guān)聯(lián)度計算方法.通過構(gòu)建POI語義關(guān)聯(lián)圖，從用戶的歷史簽到序列中提取語義信息，計算用戶簽到序列中POI之間的語義相關(guān)性.

3) 進行可擴展性實驗設(shè)計與測試.在公開數(shù)據(jù)上進行驗證，結(jié)果表明SA-TDS-Prec模型優(yōu)于其他基準模型.

2 相關(guān)工作

2.1 傳統(tǒng)POI推薦

傳統(tǒng)POI推薦利用用戶對POI的簽到次數(shù)挖掘用戶偏好，根據(jù)該偏好為用戶推薦POI.受項目推薦的啟發(fā)，傳統(tǒng)POI推薦算法把POI類比成項目，將項目推薦的一些方法直接應(yīng)用到POI推薦上[10，11].比如說協(xié)同過濾CF(Collaborative Filtering)算法.在POI推薦的早期工作中，Ye等人將基于用戶的協(xié)同過濾[12]和基于項目的協(xié)同過濾用于POI推薦[13].

矩陣分解MF(Matrix Factorization)是基于模型的協(xié)同過濾方法，它在POI推薦中的應(yīng)用也十分廣泛.矩陣分解通過將所有用戶和項目投射到具有相同維度的空間中，利用隱向量表示用戶偏好和項目屬性，通過內(nèi)積的方式預測用戶與項目交互的可能性.另外矩陣分解方法具有良好的可擴展性，許多影響推薦效果的因素(如POI的地理信息、時間信息以及用戶的社交關(guān)系等)都能與之相結(jié)合，因此衍生出許多POI推薦算法.

Cheng等人[14]利用多中心高斯模型MGM(Mutil-center Gaussian Model)建模POI之間地理距離關(guān)系，然后將MGM模型和矩陣分解MF模型相結(jié)合，并引入地理距離進行推薦.Li 等人[15]對地理社交網(wǎng)絡(luò)中用戶之間的關(guān)系進行了重新定位，分別為普通的社交關(guān)系，基于位置的關(guān)系以及鄰居關(guān)系，通過使用兩階段模型，從朋友中學習潛在位置信息，然后將潛在位置與其他簽到進行合并，最后融入到加權(quán)矩陣分解中，從而有效克服了推薦中的冷啟動問題.Yang等人[16]提出一種基于張量分解得多維信息融合興趣點推薦通用模型，利用三階張量融合時間、社會關(guān)系和類別影響，有效解決數(shù)據(jù)稀疏和冷啟動問題.Yuan等人[17]提出融合時間序列POI動態(tài)推薦算法，將用戶與用戶之間的關(guān)系、興趣點位置以及流行度信息相結(jié)合，從而有效緩解數(shù)據(jù)稀疏的問題.Yu等人[18]利用社交網(wǎng)中大眾數(shù)據(jù)的文本內(nèi)容和簽到服務(wù)地點，提出了挖掘活動和服務(wù)對應(yīng)關(guān)系的ASTM，并將用戶的活動區(qū)域與服務(wù)地點間的距離以及地點屬性間的耦合性融合到矩陣分解中，實現(xiàn)個性化服務(wù)場所推薦.

2.2 POI序列推薦

與傳統(tǒng)POI推薦(比如說基于協(xié)同過濾的方法)不同，POI序列推薦認為用戶的每個簽到行為并不是離散的，用戶對POI的簽到是有序的[19].POI序列推薦就是通過將用戶與POI的交互建模成一個序列，通過分析序列的復雜順序關(guān)系捕獲用戶的動態(tài)偏好，利用該偏好給用戶推薦POI.

目前，POI序列推薦算法中常使用的一些技術(shù)主要有馬爾可夫鏈、循環(huán)神經(jīng)網(wǎng)絡(luò)RNN、卷積神經(jīng)網(wǎng)絡(luò)CNN、自注意力機制等.Wu等人[20]提出了長短期偏好學習模型(LSPL)，在長期模塊中通過注意力機制捕捉POI長期偏好，在短期模塊中通過兩個LSTM模型學習針對位置和類別的偏好信息，將長短期偏好相結(jié)合更好地捕捉用戶在特定時間對下一個POI的偏好信息.Kong等人[21]提出一種時空長短期記憶網(wǎng)絡(luò)模型HST-LSTM，該網(wǎng)絡(luò)模型在LSTM中結(jié)合了時空影響，在一定程度上緩解數(shù)據(jù)的稀疏性.Xu等人[22]提出利用RNN模型捕獲復雜的長期依賴，同時也利用CNN模型提取在短期下隱藏狀態(tài)之間的序列模式.Zhao等人[23]提出新的時空門控網(wǎng)絡(luò)模型(STGN)，通過引入時空門捕獲連續(xù)簽到之間的時空關(guān)系.Zheng等人[24]提出基于注意力的動態(tài)偏好模型(ADPM)，設(shè)計了時空自注意力網(wǎng)絡(luò)來探索復雜的POI順序關(guān)系，捕獲用戶的動態(tài)偏好.

然而，上述模型都存在不足.傳統(tǒng)的基于矩陣分解方法僅僅從靜態(tài)的角度出發(fā)考慮用戶和POI之間的關(guān)系，無法對用戶簽到序列進行有效地建模.基于馬爾可夫鏈的方法無法同時考慮多種上下文信息以及上下文信息的交互作用.現(xiàn)有基于RNN的方法對時空信息建模，忽略了上下文的語義信息.雖然RNN可以解決長期依賴問題，但是需要大量數(shù)據(jù)才能優(yōu)于更簡單的基線方法.不同于已有模型，本文提出的SA-TDS-Prec模型將用戶簽到數(shù)據(jù)之間的時空間隔以及語義相關(guān)性相融合，利用自注意力機制捕獲用戶動態(tài)偏好的演化，從而提升POI推薦的準確性.

3 問題定義及描述

表1給出本文使用的符號列表和描述.

表1 符號列表Table 1 Symbol List

定義1.興趣點POI.一個具有特定功能的地理位置，能夠滿足用戶需求(如電影院或咖啡館).在本文提出的模型中，POI包含3個屬性：唯一標識符id、語義信息c和地理信息d(lng,lat)，其中l(wèi)ng代表經(jīng)度，lat代表緯度.

定義2.簽到記錄(Check-in).一個簽到記錄被表示為一個五元組(u,l,t,d,c)，這個五元組的含義就是用戶u在t時刻訪問POIl，POIl的地理信息是d(lng,lat)，類別信息是c.

4 自注意力下時空-語義相融合的POI序列推薦(SA-TDS-PRec)模型描述

本文提出的自注意力下時空-語義相融合的POI序列推薦模型SA-TDS-PRec，根據(jù)用戶實際簽到時間對用戶簽到序列建模.同時將用戶簽到序列中POI之間的時間間隔、空間間隔和語義相關(guān)性相融合，并利用自注意力機制捕獲用戶動態(tài)偏好，從而為用戶提供準確的POI推薦.

本文首先介紹時間間隔、空間間隔和語義相關(guān)性的具體計算方式，然后描述SA-TDS-PRec模型的具體組件，主要包括嵌入層、自注意力層和預測層.SA-TDS-PRec模型結(jié)構(gòu)如圖1所示.

圖1 SA-TDS-PRec模型結(jié)構(gòu)Fig.1 Framework of SA-TDS-PRec

4.1 基于時空不等間隔的POI軌跡建模

(1)

根據(jù)第一地理學法則[25]可知，用戶通常會訪問距離自己當前位置較近的地點，用戶的移動會受到空間距離的影響.因此，POI之間的空間距離也是影響推薦效果的重要因素之一.

Distance(li,lj)=

(2)

其中，Distance(li,lj)表示POIi和POIj間的平面距離，radi表示弧度值，a=|lati-latj|表示兩點的緯度差，b=|lngi-lngi|表示兩點的經(jīng)度差，r表示地球半徑(r=6371公里)，最終形成空間間隔集合Du.

(3)

4.2 基于行為語義序列的POI關(guān)聯(lián)度計算

語義序列是由用戶POI軌跡中提取的每一個POI類別信息組成的.用戶的每一次簽到行為之間都存在著一定的語義相關(guān)性，并且簽到序列之間語義相關(guān)性是成對的.語義相關(guān)性越大，代表用戶選擇的可能性越大.

之前關(guān)于語義相關(guān)性的計算是通過統(tǒng)計的方法來進行的，語義序列中兩個類別之間的轉(zhuǎn)換次數(shù)越多代表兩個類別之間的語義相關(guān)度越高.但是，僅僅通過統(tǒng)計類別之間的轉(zhuǎn)換次數(shù)來計算語義相關(guān)性的方法會受到數(shù)據(jù)量的影響.如果用戶的簽到數(shù)據(jù)很少，則計算結(jié)果會產(chǎn)生誤差.由于用戶簽到POI之間的時間間隔會影響用戶的移動，所以本文提出融入時間間隔計算語義相關(guān)性.

圖2 語義關(guān)聯(lián)圖Fig.2 Semantic correlational graph

然后根據(jù)構(gòu)建的語義關(guān)聯(lián)圖，計算用戶語義行為序列中POI之間的關(guān)聯(lián)度(即語義相關(guān)性).具體的計算規(guī)則如下：

1)如果兩個相鄰節(jié)點之間有向邊的權(quán)重(即時間間隔)相等，那么兩個節(jié)點之間有向邊的數(shù)量越多表明POI之間的語義相關(guān)性越大，反之亦然.

(4)

(5)

(6)

(7)

語義相關(guān)性算法偽代碼如算法1所示.

算法1.語義相關(guān)性計算

輸入：用戶u的歷史簽到序列

1.構(gòu)建語義關(guān)聯(lián)圖Gu

2.提取語義序列cu

3.劃分cu為一對一的序列集合c′u

5.遍歷Gu，統(tǒng)計m和we

6.如果m>0，執(zhí)行

8.否則

4.3 SA-TDS-PRec模型

4.3.1 嵌入層

在給定用戶歷史簽到序列后，利用詞嵌入技術(shù)創(chuàng)建POI嵌入矩陣ML∈RN×d，其中N代表POI的數(shù)量，d代表潛在維度.通過檢索，獲得用戶簽到序列的嵌入向量為EL∈Rn×d：EL=[l1l2…ln].

(8)

同樣，個性化空間間隔嵌入向量如式(9)所示：

(9)

語義相關(guān)性嵌入向量如式(10)所示：

(10)

4.3.2 自注意力層

將上述嵌入層獲得的POI絕對位置、時間間隔、空間間隔、語義相關(guān)性嵌入向量進行融合，輸入到自注意力層中捕獲用戶的動態(tài)偏好.關(guān)于模型的每一步輸出，自注意力層都考慮到了用戶歷史簽到序列中其他所有POI對當前步的影響.最后得到輸出序列Z={z1，z2，z3，…,zn}，zi∈Rd.輸出序列的每一項zi的計算公式如式(11)所示：

(11)

(12)

其中eij表示輸入序列中POIj對當前POIi的影響分數(shù)，通過將鍵向量與查詢向量進行點積運算來獲得，如式(13)所示：

(13)

雖然自注意力機制能夠?qū)⒂脩艉灥降腜OI絕對位置信息、時間間隔、空間間隔以及語義相關(guān)性相結(jié)合，但是它采用線性組合的方式進行的.因此在自注意力層之后，使用前饋神經(jīng)網(wǎng)絡(luò)FNN(Feedforward neural network)，利用ReLU激活函數(shù)賦予模型非線性，具體計算公式如式(14)所示：

FFN(zi)=max(0,ziW1+b1)W2+b2

(14)

其中W1，W2代表權(quán)重，b1,b2代表偏差.

為了避免在堆疊很多層后出現(xiàn)過擬合、梯度消失等問題，模型采用了層歸一化、殘差連接和Dropout技術(shù).殘差連接的主要作用是保證有用的底層特征能夠直接傳播到最后一層，計算公式見式(15).層歸一化操作用來對特征向量進行規(guī)范化處理，簡化學習難度，計算公式見式(16).Dropout技術(shù)用來防止出現(xiàn)過擬合現(xiàn)象.

Zi=zi+Dropout(f(LayerNorm(zi)))

(15)

(16)

其中，f(·)是前饋神經(jīng)網(wǎng)絡(luò)或者自我注意層，⊙是element-wise product，μ和σ是輸入向量zi的均值和方差，α和β是學習的縮放因子和偏置項.

4.3.3 預測層

(17)

其中l(wèi)j表示POIj的嵌入表示.Ri,j越高意味著用戶的興趣越大，POIj被推薦的可能性越大.

4.4 模型訓練

(18)

5 實驗及結(jié)果分析

5.1 實驗設(shè)計及數(shù)據(jù)集

本文在兩個開源的數(shù)據(jù)集Gowalla和Yelp上進行模型評估.首先進行數(shù)據(jù)清洗，如果用戶和POI出現(xiàn)次數(shù)少于10，刪除該用戶.清洗完數(shù)據(jù)后，根據(jù)每個用戶的具體簽到時間建模用戶的簽到序列.數(shù)據(jù)統(tǒng)計見表2.

表2 數(shù)據(jù)集統(tǒng)計Table 2 Statistics of datasets

5.2 評估指標

為了驗證SA-TDS-PRec模型的性能，采用兩個常用指標命中率Hit@k和NDCG@k.Hit@k是一種常用的衡量召回率的指標，計算出真實的下一個POI在推薦的前k個POI中所占的比重大小，計算公式如式(19)所示：

(19)

其中，GT分母是所有的測試集合，NumberOfHit@k分子表示用戶top-k列表中屬于測試集合的個數(shù)總和.

NDCG@k是一種衡量排序質(zhì)量的評價指標，該指標考慮了所有元素的相關(guān)性，同時還引入了位置影響因素，它在較高的位置上分配較大的權(quán)重.計算公式如式(20)所示：

(20)

其中，DCG@k是折損累計增益，它是讓相關(guān)性越好的結(jié)果排名越靠前.IDCG@k表示理想情況下最大的DCG值.

5.3 對比模型

為驗證所提出的SA-TDS-PRec模型的性能，對比模型如下：

1)BPR[26]：一種基于矩陣分解算法的排序算法，采用貝葉斯最大后驗概率，利用成對方法來進行排序.

2)FPMC[3]：因式分解個性化馬爾可夫鏈，該方法將矩陣分解和一階馬爾可夫鏈進行結(jié)合，矩陣分解用來捕獲用戶的長期偏好，一階馬爾可夫鏈用于建模用戶與項目交互的序列信息，通過上一時刻的交互預測下一時刻的交互.

3)GRU4Rec[6]：利用循環(huán)神經(jīng)網(wǎng)絡(luò)進行會話行為推薦.傳統(tǒng)的序列化推薦方法在進行推薦時只考慮用戶的最后一個行為，沒有考慮完整的行為序列信息.而該模型恰好解決了這一問題.

4)Caser[27]：卷積序列嵌入推薦模型，該模型利用卷積神經(jīng)網(wǎng)絡(luò)CNN建模用戶行為序列，學習用戶短期序列特征，并結(jié)合用戶靜態(tài)偏好，共同為用戶進行推薦.

5.4 性能測試與分析

5.4.1 總體性能

表3展示了該方法在Gowalla和Yelp數(shù)據(jù)集上與基準方法的對比結(jié)果.從表中可以看到，SA-TDS-PRec模型與最優(yōu)的基線模型相比，在Gowalla數(shù)據(jù)集中命中率和NDCG兩個評價指標分別提高了7.9%和11.0%.在Yelp數(shù)據(jù)集中命中率和NDCG兩個評價指標分別提高了12.0%和8.6%.一方面，SA-TDS-PRec模型采用自注意力機制，在訓練模型的時候每一時刻狀態(tài)輸出都考慮了用戶所有的簽到信息，而不像傳統(tǒng)的馬爾可夫鏈模型和循環(huán)神經(jīng)網(wǎng)絡(luò)模型，它們每一時刻的狀態(tài)輸出都依賴上一時刻的狀態(tài)輸入.另一方面，SA-TDS-PRec模型融合了用戶歷史簽到序列中POI之間的時間間隔、空間間隔和語義相關(guān)性，進一步提高了推薦的準確性.

表3 整體性能比較Table 3 Overall performance comparison

5.4.2 時間、空間、語義對模型影響

本文利用自注意力機制處理用戶軌跡，另外融合用戶軌跡中POI之間的時間間隔、空間間隔和語義相關(guān)性的信息.為驗證提出方法的有效性，設(shè)計4組消融實驗.其中SA模型是只利用自注意機制進行推薦，不考慮其他因素.SA-T模型是只考慮時間間隔因素.SA-D模型只考慮空間間隔因素.SA-S模型是只考慮POI的語義相關(guān)性.SA-TDS-PRec融入時間間隔，空間間隔以及語義相關(guān)性.實驗結(jié)果如表4所示.

從表4中可以看出，與只利用自注意力機制推薦的模型SA相比，融合時間間隔因素SA-T模型、融合空間間隔因素SA-D模型和融合語義相關(guān)性模型SA-S，推薦準確性都得到了提升.這表明在個性化POI推薦中，不論是時間間隔、空間間隔還是語義相關(guān)性，都會影響推薦的準確性.而且本研究也發(fā)現(xiàn)，時間、空間以及POI的語義信息對推薦的影響程度幾乎相同.這說明用戶在出行的時候會考慮多方面因素，實驗結(jié)果也表明將3種因素綜合考慮，會進一步提升推薦的準確性.

表4 消融實驗結(jié)果比較Table 4 Comparison of ablation experiment results

5.4.3 簽到序列長度n對模型影響

圖3和圖4分別在Gowalla和Yelp數(shù)據(jù)集上展示了用戶簽到序列長度n對于評估指標NDCG@10的影響.將用戶簽到序列長度n的值設(shè)為從10～50，其他參數(shù)保持不變.從圖中可以直觀的看到，無論是在Gowalla數(shù)據(jù)集上還是Yelp數(shù)據(jù)集上，當用戶簽到序列長度不斷增加時，現(xiàn)有模型的推薦效果整體呈現(xiàn)上升趨勢.這說明用戶的簽到序列越長，模型所學習到的用戶信息就越多，因此能夠更好的捕獲到用戶的動態(tài)偏好.

圖3 Gowalla數(shù)據(jù)集中序列長度對NDCG的影響 圖4 Yelp數(shù)據(jù)集中序列長度對NDCG的影響Fig.3 Effect of sequence length on NDCG in the Gowalla dataset Fig.4 Effect of sequence length on NDCGin the Yelp dataset

5.4.4 特征表示維度d對模型影響

圖5和圖6分別在Gowalla和Yelp數(shù)據(jù)集上展示了特征維度d對于評估指標NDCG@10的影響.將特征維度d的值設(shè)為從10～50，其他參數(shù)保持不變.從圖中可以看出，無論是在Gowalla數(shù)據(jù)集上還是Yelp數(shù)據(jù)集上，隨著特征表示維度的不斷增加，現(xiàn)有模型的推薦效果整體呈現(xiàn)上升的趨勢.相較于SA模型，SA-TDS-PRec模型的性能始終優(yōu)于SA模型.

圖5 Gowalla數(shù)據(jù)集中特征表示維度對NDCG的影響 圖6 Yelp數(shù)據(jù)集中特征表示維度對NDCG的影響Fig.5 Effect of feature representation dimension on NDCG in the Gowalla dataset Fig.6 Effect of feature representation dimension on NDCG in the Yelp dataset

6 結(jié) 論

本文提出自注意下時空-語義相融合的POI序列推薦模型SA-TDS-PRec.該模型根據(jù)用戶對POI的具體訪問時間對用戶簽到序列進行建模，另外還將序列中POI之間的時間間隔、空間間隔和語義相關(guān)性納入考慮范圍，利用自注意力機制捕獲用戶動態(tài)偏好的演化，進一步提升推薦的準確性.本文在公開數(shù)據(jù)集Gowalla和Yelp上進行模型評估，實驗結(jié)果表明，本文提出的模型在性能上優(yōu)于其他基準模型，有效提升推薦結(jié)果準確性.在未來的研究工作中，希望可以加入用戶對POI的評論信息，以此來更好的挖掘用戶的動態(tài)偏好.