趙 薇，李建波，呂志強(qiáng)，董傳浩

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266071)

0 引言

隨著智能手機(jī)和平板電腦等帶GPS定位的移動(dòng)終端設(shè)備的普及，位置社交網(wǎng)絡(luò)(Location-Based Social Network，LBSN)得到了快速發(fā)展，用戶可以輕松地獲取已訪問興趣點(diǎn)的地理信息，并進(jìn)行實(shí)時(shí)簽到。由此產(chǎn)生了海量的簽到數(shù)據(jù)，引起了學(xué)者的廣泛關(guān)注[1-5]。如何從海量的簽到數(shù)據(jù)中篩選出用戶感興趣的內(nèi)容是一個(gè)值得研究的問題。對于興趣點(diǎn)推薦的研究則可以解決這一難題。興趣點(diǎn)推薦是一項(xiàng)致力于從大量的候選位置中為用戶推薦滿足其訪問需求的興趣點(diǎn)的研究，它既可以幫助用戶制定合理的出行計(jì)劃，探索未知的地理區(qū)域；也可以幫助商家向潛在的用戶提供個(gè)性化服務(wù)，提高其營業(yè)收入；同時(shí)可以讓政府提前進(jìn)行交通規(guī)劃，避免出行高峰期造成的道路阻塞。

現(xiàn)階段，關(guān)于興趣點(diǎn)推薦的研究主要是根據(jù)歷史簽到數(shù)據(jù)，挖掘用戶潛在的移動(dòng)模式，模擬用戶訪問下一個(gè)地點(diǎn)的決策過程，達(dá)到為用戶推薦滿足其訪問要求的興趣點(diǎn)的目的[6]。不同于傳統(tǒng)的推薦任務(wù)，興趣點(diǎn)推薦是一個(gè)融合時(shí)間和地理信息的推薦。例如，用戶在每天早晨8點(diǎn)去早餐店吃早餐，在工作日下午3點(diǎn)去咖啡店買咖啡，在每周日晚上7點(diǎn)和朋友去電影院看電影。對于即將到來的一天，如何為用戶合理地安排行程，推薦其感興趣的地點(diǎn)。這時(shí)的興趣點(diǎn)推薦任務(wù)一定是融合時(shí)間和地理信息的推薦。

在融合時(shí)間信息的興趣點(diǎn)推薦工作中，He等[7]認(rèn)為用戶與興趣點(diǎn)交互的時(shí)間戳是有規(guī)律的，它不僅是用戶訪問興趣點(diǎn)的時(shí)間節(jié)點(diǎn)，還隱藏著用戶訪問行為的周期性特征。因此，時(shí)間信息在興趣點(diǎn)推薦中起著重要作用[8]。Zhao等[9]通過門控機(jī)制來捕獲兩個(gè)相鄰興趣點(diǎn)之間的訪問時(shí)間間隔。Feng等[10]提出注意力機(jī)制來捕獲具有周期性特征的時(shí)間信息。另外，在融合地理信息的興趣點(diǎn)推薦工作中，考慮到興趣點(diǎn)之間的距離，Cheng等[11]將地理信息作為一種區(qū)域約束，結(jié)合馬爾可夫鏈，提出了FPMC-LR模型。Sun等[12]提出了一個(gè)針對短期建模的地理空洞循環(huán)神經(jīng)網(wǎng)絡(luò)模型，該模型解決了已訪問興趣點(diǎn)在地理上分散的問題。Lian等[13]通過用戶訪問興趣點(diǎn)的地理信息來捕捉用戶訪問行為的空間聚類現(xiàn)象。

綜上所述，現(xiàn)有方法在一定程度上提高了興趣點(diǎn)推薦準(zhǔn)確率，但忽略了時(shí)間和地理信息之間的關(guān)系。雖然按時(shí)間周期對簽到記錄進(jìn)行了劃分，但忽略了不同時(shí)間用戶訪問行為受地點(diǎn)距離約束程度的差異性。例如，工作日用戶的訪問行為受區(qū)域限制較大，訪問地點(diǎn)受距離約束嚴(yán)重；節(jié)假日用戶的訪問行為相對自由，訪問的地點(diǎn)受距離約束程度相對較輕，訪問的地點(diǎn)更具有隨機(jī)性。

針對上述問題，本文對簽到數(shù)據(jù)進(jìn)行了工作日和節(jié)假日的劃分，提出了一種融合時(shí)間和地理信息的興趣點(diǎn)推薦模型。該模型主要分為兩個(gè)部分：一是利用長短期記憶網(wǎng)絡(luò)(Long Short-Term Memory，LSTM)提取當(dāng)前軌跡中序列特征的時(shí)空關(guān)系模塊；二是學(xué)習(xí)歷史軌跡中地理信息的地理關(guān)系模塊。在地理關(guān)系模塊中，利用卷積神經(jīng)網(wǎng)絡(luò)捕獲用戶的局部地理偏好；根據(jù)用戶之間的訪問相似度，生成關(guān)于地理位置的評分矩陣。融合上述兩部分，獲得用戶下一步訪問興趣點(diǎn)的推薦意見。

1 預(yù)備知識

1.1 興趣點(diǎn)推薦

興趣點(diǎn)推薦被認(rèn)為是推薦領(lǐng)域中的一個(gè)重要任務(wù)。與傳統(tǒng)的電影、音樂、新聞等推薦任務(wù)不同，興趣點(diǎn)推薦需要用戶去訪問物理世界中真實(shí)存在的地點(diǎn)，因此推薦難度更大。在基于傳統(tǒng)方法的研究中，協(xié)同過濾算法是被普遍認(rèn)可的[14-16]。Ye等[17]基于用戶的協(xié)同過濾框架，采用線性插值的方法，結(jié)合地理與社會影響進(jìn)行興趣點(diǎn)推薦。夏英等[18]先通過協(xié)同過濾算法模擬用戶的社交關(guān)系，然后通過加權(quán)矩陣分解學(xué)習(xí)地理信息，進(jìn)而將兩者融合進(jìn)行興趣點(diǎn)推薦。另外，由于簽到數(shù)據(jù)是連續(xù)的序列數(shù)據(jù)，因此采用馬爾可夫鏈也可以很好地計(jì)算簽到序列之間的轉(zhuǎn)移概率。

近年來，深度學(xué)習(xí)的發(fā)展極大地推動(dòng)了興趣點(diǎn)推薦的研究。針對簽到數(shù)據(jù)的特點(diǎn)，循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network，RNN)及其變體(LSTM、GRU)在興趣點(diǎn)推薦領(lǐng)域的應(yīng)用十分廣泛。Zhong等[19]利用LSTM基于流行度和社交網(wǎng)絡(luò)進(jìn)行興趣點(diǎn)推薦。Liu等[20]利用GRU基于類別感知進(jìn)行推薦工作。Liu等[21]擴(kuò)張了RNN，使用時(shí)間轉(zhuǎn)移矩陣和距離轉(zhuǎn)移矩陣來分別捕獲時(shí)空上下文信息，并采用線性插值的方法緩解數(shù)據(jù)稀疏帶來的影響。另外，卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network，CNN)既可以從評論內(nèi)容中獲取語義和情感信息[22]，也可以從最相似的友誼關(guān)系圖中提取特征[23]，因此在興趣點(diǎn)推薦中得到了廣泛應(yīng)用。

1.2 興趣點(diǎn)推薦問題定義

2 融合時(shí)間和地理信息的興趣點(diǎn)推薦模型

圖1展示了所提模型的總體架構(gòu)，它主要由時(shí)空關(guān)系模塊、地理關(guān)系模塊和預(yù)測模塊三部分組成。

2.1 時(shí)空關(guān)系模塊

當(dāng)前軌跡中的序列信息(位置、時(shí)間)反映了用戶最近一段時(shí)間內(nèi)的興趣偏好，直接影響用戶下一步的決策過程。因此，將當(dāng)前軌跡中的不同信息通過嵌入學(xué)習(xí)，映射成對應(yīng)的嵌入向量。然后，將時(shí)空嵌入向量進(jìn)行連接，利用LSTM學(xué)習(xí)當(dāng)前軌跡中的時(shí)空轉(zhuǎn)換規(guī)律。計(jì)算公式為

(1)

ht=LSTM(elt,ht-1)

(2)

2.2 地理關(guān)系模塊

2.2.1 時(shí)間判別器

考慮到用戶的出行受時(shí)間和距離的影響程度不同，本文將簽到數(shù)據(jù)按時(shí)間劃分為工作日軌跡和節(jié)假日軌跡。在數(shù)據(jù)預(yù)處理時(shí)，為了減小訓(xùn)練量，提高訓(xùn)練效率，僅保留簽到時(shí)間的“時(shí)”，作為該條記錄的時(shí)間，例：“2021-7-1 12:34:23”，僅保留“12”作為該條簽到記錄的時(shí)間標(biāo)簽。為了區(qū)分工作日軌跡和節(jié)假日軌跡，令工作日的簽到時(shí)間tday=t，0≤tday<24，節(jié)假日的簽到時(shí)間tend=t+24，24≤tend<48。在將軌跡輸入到地理關(guān)系模塊之前，先根據(jù)當(dāng)前軌跡的第一條簽到記錄判斷該軌跡是工作日簽到還是節(jié)假日簽到，然后選擇對應(yīng)的歷史軌跡。即：若t0<24成立，則選取歷史軌跡中屬于工作日的簽到軌跡，反之，選擇屬于節(jié)假日的簽到軌跡。另外，需要判斷獲得的歷史軌跡是否為空，這樣做可以排除已知的歷史軌跡中僅包含某一種時(shí)間軌跡，而當(dāng)前軌跡是另一種時(shí)間軌跡的情況，如：歷史軌跡全部是節(jié)假日軌跡，而當(dāng)前軌跡是工作日軌跡。針對這一情況，可以隨機(jī)生成一個(gè)集合P={l1,l2,…,l|P|}作為歷史軌跡，|P|為集合的長度。

圖1 興趣點(diǎn)推薦模型Fig.1 POI recommendation model

圖2 鄰居興趣點(diǎn)訪問次數(shù)Fig.2 Number of visits to neighbor POIs

2.2.2 局部地理偏好模塊

由于鄰居興趣點(diǎn)的距離可以滿足用戶的時(shí)間可行性，用戶下一步訪問的興趣點(diǎn)，極大概率是當(dāng)前興趣點(diǎn)的鄰居興趣點(diǎn)。圖2為鄰居興趣點(diǎn)訪問次數(shù)的分布圖?？梢钥闯觯航o定用戶訪問的興趣點(diǎn)li，用戶訪問li的次數(shù)與訪問li鄰居的次數(shù)呈正相關(guān)，與距離呈負(fù)相關(guān)(顏色深淺表示訪問次數(shù)，顏色越深表示訪問次數(shù)越多)。

因此，根據(jù)距離，對時(shí)間判別器的輸出結(jié)果進(jìn)行篩選，生成更小的興趣點(diǎn)候選集合Q。這里需要分別計(jì)算歷史軌跡中的每一個(gè)興趣點(diǎn)li，i∈{1,2,…,|P|}與當(dāng)前軌跡中t-1時(shí)刻訪問的興趣點(diǎn)lt-1的距離：

(3)

其中，(lonli，latli)為歷史軌跡中第i個(gè)興趣點(diǎn)的經(jīng)緯度，(lonlt-1，latlt-1)為當(dāng)前軌跡中t-1時(shí)刻的興趣點(diǎn)lt-1的經(jīng)緯度。若di<Δd成立(Δd為距離閾值)，則將興趣點(diǎn)li添加到新的興趣點(diǎn)候選集合Q中。新生成的興趣點(diǎn)候選集合Q的長度要比歷史軌跡的長度短很多，這樣做既可以減少后續(xù)計(jì)算的成本花費(fèi)，也可以避免某些距離較遠(yuǎn)的興趣點(diǎn)對預(yù)測結(jié)果的影響。

圖3 局部地理偏好模塊結(jié)構(gòu)圖Fig.3 Architecture of local geographical preferences module

為了進(jìn)一步獲得鄰居興趣點(diǎn)的地理特征，將興趣點(diǎn)候選集合Q嵌入后可以得到Qe，然后通過卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)特征提取，如圖3所示。

Z=ReLU(fconv(Qe))

(4)

2.2.3 位置評分模塊

該模塊主要是根據(jù)用戶的歷史軌跡，計(jì)算不同用戶之間已訪問興趣點(diǎn)的相似度，進(jìn)一步生成用戶關(guān)于興趣點(diǎn)的評分矩陣。

(5)

(6)

2.3 預(yù)測模塊

預(yù)測模塊由一個(gè)全連接層和一個(gè)輸出層組成。全連接層將時(shí)空關(guān)系模塊和地理關(guān)系模塊的所有特征結(jié)合到一個(gè)新的向量中，并進(jìn)一步將特征向量處理成一個(gè)維度更小、更具有表征意義的向量。然后，由輸出層經(jīng)過負(fù)采樣后，輸出預(yù)測結(jié)果。具體過程如下：

(7)

其中，y是一個(gè)融合時(shí)序特征、地理特征及用戶個(gè)性化特征的向量，將其與評分矩陣做最后的融合，并經(jīng)過softmax層處理后，得到模型預(yù)測輸出，如式(8)所示：

out=softmax(y*W′*Cui)

(8)

其中，W′是一個(gè)可訓(xùn)練矩陣。out表示概率分布，概率最大的興趣點(diǎn)是用戶最有可能訪問的位置。如果用戶真實(shí)訪問是興趣點(diǎn)lt，其對應(yīng)的概率為plt，那么損失函數(shù)可以表示為

(9)

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文所用的數(shù)據(jù)集分別來自Foursquare、Weeplaces和Gowalla。其中，F(xiàn)oursquare數(shù)據(jù)集收集了2012年4月到2013年2月的845個(gè)真實(shí)用戶在紐約的簽到數(shù)據(jù)，共包括12 649個(gè)位置上的99 205條簽到記錄；Weeplaces數(shù)據(jù)集收集了2009年7月到2010年9月的307個(gè)真實(shí)用戶在全球的簽到數(shù)據(jù)，共包括18 288個(gè)位置上的127 974條簽到記錄；Gowalla數(shù)據(jù)集收集了2010年1月到2010年9月的384個(gè)真實(shí)用戶在全球的簽到數(shù)據(jù)，共包括16 486個(gè)位置上的79 356條簽到記錄。這3個(gè)數(shù)據(jù)集具有與模型相關(guān)的所有屬性(用戶ID、經(jīng)緯度、興趣點(diǎn)ID、簽到時(shí)間)。

為了降低數(shù)據(jù)稀疏性的影響，本文對數(shù)據(jù)進(jìn)行了預(yù)處理，將用戶一天中所有的簽到記錄視為一條簽到軌跡，僅保留擁有不少于5條簽到軌跡且每條軌跡不少于3條簽到記錄的用戶。對于每個(gè)用戶的簽到軌跡，前80%用作訓(xùn)練集，后20%用作測試集。

3.2 指標(biāo)與參數(shù)設(shè)置

本文采用了3個(gè)常用的評估指標(biāo)：準(zhǔn)確率(Pre@K)、召回率(Rec@K)，歸一化貼現(xiàn)累計(jì)收益(NDCG@K)，定義為

(10)

(11)

(12)

其中，K為給每個(gè)用戶推薦的POIs數(shù)量，Ri為測試集中用戶訪問的真實(shí)位置集合，Vi為給用戶推薦的K個(gè)POIs，Gi為給用戶推薦的K個(gè)POIs的等級，|U|表示用戶的數(shù)量。本文取K={5,10}來分別計(jì)算準(zhǔn)確率、召回率和歸一化貼現(xiàn)累計(jì)收益。

通過實(shí)驗(yàn)，本文將隱藏層節(jié)點(diǎn)數(shù)設(shè)置為300，興趣點(diǎn)和用戶ID的嵌入維度設(shè)置為300，時(shí)間的嵌入維度設(shè)置為10，批量大小設(shè)置為32，學(xué)習(xí)率設(shè)置為0.000 1，距離約束設(shè)置為Δd=4 km，候選歷史軌跡長度設(shè)置為|P|=20。另外，本文采用了Adam優(yōu)化算法對模型中的參數(shù)進(jìn)行優(yōu)化。

3.3 基線

本文選擇了一些經(jīng)典方法與所提出模型進(jìn)行了性能比較：

Markov：作為一種經(jīng)典的序列預(yù)測方法，可以學(xué)習(xí)序列之間的轉(zhuǎn)移概率，從而預(yù)測用戶未來的訪問行為，是興趣點(diǎn)推薦常用的基線模型。

RNN：一種基礎(chǔ)的處理序列數(shù)據(jù)的循環(huán)神經(jīng)網(wǎng)絡(luò)模型，由輸入層、隱藏層和輸出層組成，層間采用全連接的方式。

LSTM：在傳統(tǒng)RNN的基礎(chǔ)上，增加了3個(gè)門控機(jī)制(更新門、遺忘門、輸出門)，可以用來捕獲長期依賴。

ST-RNN：基于RNN的興趣點(diǎn)推薦模型，將時(shí)間信息和地理信息同時(shí)融入循環(huán)結(jié)構(gòu)中。

DeepMove：該模型利用歷史注意力模塊捕獲歷史軌跡中的周期性規(guī)律，并利用循環(huán)神經(jīng)網(wǎng)絡(luò)捕獲當(dāng)前軌跡的時(shí)空上下文。

LSTPM：該模型考慮了長期和短期偏好，使用上下文感知非局部結(jié)構(gòu)來識別歷史軌跡中的時(shí)空相關(guān)性，可以捕獲當(dāng)前軌跡中不連續(xù)興趣點(diǎn)的地理影響。

3.4 實(shí)驗(yàn)分析

本文所提模型與基線模型在3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖4所示。從圖4可以得出以下結(jié)論：

1)在3個(gè)數(shù)據(jù)集上，本文所提模型在所有指標(biāo)上都明顯優(yōu)于基線模型。而在基線模型中，LSTPM模型在3個(gè)數(shù)據(jù)集上表現(xiàn)最好，DeepMove模型次之。這兩個(gè)模型都將用戶的軌跡劃分為當(dāng)前軌跡和歷史軌跡，將用戶的短期偏好和長期偏好分開考慮。其中，LSTPM模型的優(yōu)勢在于考慮了序列中的距離。因此，對于地理信息的處理在興趣點(diǎn)推薦中十分重要。本文模型既利用距離關(guān)系生成了一個(gè)小的候選興趣點(diǎn)集合，又對每一個(gè)興趣點(diǎn)進(jìn)行了評分。由于本文所提模型充分學(xué)習(xí)了地理信息對于用戶選擇的影響，所以在推薦準(zhǔn)確率方面有了較大提升。

2)ST-RNN在推薦表現(xiàn)上優(yōu)于LSTM、RNN，這說明除了學(xué)習(xí)序列信息，建模不同興趣點(diǎn)之間的時(shí)空關(guān)系同樣可以提高模型的預(yù)測能力。Markov方法的推薦效果最差，這表明僅使用用戶訪問位置的轉(zhuǎn)換矩陣來進(jìn)行預(yù)測所包含的信息太少，導(dǎo)致模型無法實(shí)現(xiàn)較好的推薦效果。

圖4 3個(gè)數(shù)據(jù)集上的性能比較Fig.4 Performance comparison on three datasets

3.5 組件分析

為了驗(yàn)證模型中不同組件對于性能的增益，本文進(jìn)一步簡化了模型。

OURS-1：該模型移除了對于歷史軌跡處理的組件，僅保留了處理當(dāng)前軌跡的組件。

OURS-2：該模型移除了對于當(dāng)前軌跡處理的組件，僅保留了處理歷史軌跡的組件。

表1 不同簡化模型的性能比較Tab.1 Performance comparison of different simplified models

簡化模型在3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表1所示，可以看出：

1)模型OURS-2在所有指標(biāo)上的表現(xiàn)都優(yōu)于模型OURS-1。這說明OURS-2的推薦準(zhǔn)確率更高。原因在于OURS-2可以更好地捕捉用戶簽到記錄中的地理信息，更好地模擬用戶的長期依賴。這說明地理信息在興趣點(diǎn)推薦中十分重要，也清楚地展示了本文建模個(gè)性化地理影響的優(yōu)勢。

2)雖然OURS-1比OURS-2略差。但是OURS-1的預(yù)測能力比圖4中的很多基線要好，如：RNN、LSTM。這說明對用戶短期依賴的捕獲，除了序列特征，對用戶個(gè)性化信息的建模也同樣重要。因此，本文所提模型將OURS-1和OURS-2組合在一起，在這3個(gè)數(shù)據(jù)集上都取得了最好的表現(xiàn)。

3.6 參數(shù)分析

本文分析了興趣點(diǎn)嵌入維度、候選歷史軌跡長度|P|對模型性能的影響。

圖5a顯示了在3個(gè)數(shù)據(jù)集上不同興趣點(diǎn)嵌入維度在Pre@5上的結(jié)果，可以看出：嵌入維度在[300，500]范圍內(nèi)，模型性能基本是穩(wěn)定。這是因?yàn)榫S度過低時(shí)，會丟失很多特征；維度過高時(shí)，又會產(chǎn)生無關(guān)的噪聲信息。最終，本文將300作為興趣點(diǎn)的嵌入維度，一方面可以減少參數(shù)量，另一方面可以提高運(yùn)算效率。

圖5 不同參數(shù)的性能比較Fig.5 Performance comparison of different parameters

圖5b顯示了在3個(gè)數(shù)據(jù)集上不同候選歷史軌跡長度|P|在Rec@10上的結(jié)果，可以看出，候選歷史軌跡長度|P|對于模型的預(yù)測性能幾乎沒有影響。這說明絕大多數(shù)用戶不存在2.2.1節(jié)中所提到的歷史軌跡不存在的情況。

4 結(jié)論

本文提出了一種融合時(shí)間和地理信息的興趣點(diǎn)推薦模型。首先，針對時(shí)間對用戶訪問行為的不同影響，本文將用戶軌跡劃分為工作日軌跡和節(jié)假日軌跡，并在此基礎(chǔ)上進(jìn)行了當(dāng)前軌跡和歷史軌跡的劃分。其次，模型分別利用時(shí)空關(guān)系模塊和地理關(guān)系模塊學(xué)習(xí)不同軌跡中的特征。具體而言，時(shí)空關(guān)系模塊利用長短期記憶網(wǎng)絡(luò)學(xué)習(xí)當(dāng)前軌跡中的時(shí)空特征；地理關(guān)系模塊一方面通過卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)鄰居興趣點(diǎn)的特征；另一方面根據(jù)用戶之間的相似度，生成用戶對興趣點(diǎn)的評分矩陣。實(shí)驗(yàn)證明，本文所提模型在興趣點(diǎn)推薦性能方面優(yōu)于現(xiàn)有的其他模型。目前的興趣點(diǎn)推薦研究都是針對單個(gè)用戶，未來可以考慮根據(jù)社交關(guān)系以用戶組的形式進(jìn)行興趣點(diǎn)推薦。