代雨柔，楊 慶，2，張鳳荔，周 帆*

（1.電子科技大學(xué)信息與軟件工程學(xué)院，成都 610054；2.中國電子科技集團(tuán)公司第十研究所，成都 610036）

（*通信作者電子郵箱fan.zhou@uestc.edu.cn）

0 引言

在基于位置的社交網(wǎng)絡(luò)（Location based Social Network，LBSN）中，預(yù)測人類的移動(dòng)軌跡是一項(xiàng)重要且困難的任務(wù)。在日常的生活中，人們不斷地從一個(gè)地方到另一個(gè)地點(diǎn)移動(dòng)，但移動(dòng)的規(guī)律因人而異，且受各種如節(jié)假日、天氣、心情等因素的影響。通過預(yù)測人們的軌跡，在某些方面能夠反映出該用戶的生活方式、移動(dòng)規(guī)律以及人脈關(guān)系網(wǎng)絡(luò)等。獲取這些信息可以幫助用戶提前做好路線規(guī)劃、周邊購物與飲食推薦等實(shí)際建議，這也為學(xué)習(xí)用戶移動(dòng)行為提供了新的研究，如社會(huì)中的關(guān)系推斷［1］、友情預(yù)測［2］、軌跡-用戶預(yù)測［3］、個(gè)性化社交事件推薦［4］、軌跡預(yù)測［5］等。

在用戶的軌跡預(yù)測中，最重要的是預(yù)測下一個(gè)將要去的興趣點(diǎn)（Point Of Interest，POI）。準(zhǔn)確預(yù)測出人們的下一個(gè)興趣點(diǎn)，不僅能方便個(gè)人的出行，也能給其他人的出行帶來影響。以往收集軌跡數(shù)據(jù)主要是通過問卷調(diào)查的方式，但問卷調(diào)查不僅成本高、效率低，而且難以長時(shí)間對(duì)用戶的軌跡進(jìn)行記錄。隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和各種設(shè)備中全球定位系統(tǒng)（Global Positioning System，GPS）的廣泛使用，諸如Foursquare（https：//foursquare.com）和Gowalla（http：//blog.gowalla.com）這樣基于位置的社交網(wǎng)絡(luò)變得無處不在。用戶通過這些設(shè)備，留下他們的足跡并分享他們的心情或經(jīng)驗(yàn)，使得擁有相同興趣點(diǎn)的用戶軌跡中的簽到點(diǎn)相互交匯，例如美術(shù)館、食堂、購物中心、音樂廳等。

文獻(xiàn)［6］通過對(duì)100 萬用戶的研究，發(fā)現(xiàn)用戶的移動(dòng)行為具有明顯的穩(wěn)定性，93%的用戶移動(dòng)模式是可以被預(yù)測的，與早期文獻(xiàn)［7］中對(duì)45 000 個(gè)匿名用戶的運(yùn)動(dòng)模式進(jìn)行研究的結(jié)論大致相同。結(jié)論也表明不同的個(gè)體可預(yù)測性的差別并不是很大，這種高可預(yù)測性是由于人們的運(yùn)動(dòng)具有高度的規(guī)律性。到目前為止，人們做了大量的研究來將這種可預(yù)測性轉(zhuǎn)化為實(shí)際的移動(dòng)行為預(yù)測模型。早期預(yù)測移動(dòng)行為的方法大多數(shù)是基于模式的，這種基于模式的預(yù)測方法［8-9］首先從用戶的軌跡中發(fā)現(xiàn)預(yù)定義的移動(dòng)機(jī)制，如周期模式、序列模式等，然后根據(jù)提取到的這些模式來預(yù)測下一個(gè)位置。這些關(guān)于人類移動(dòng)行為的研究大多是提取人類移動(dòng)行為中的統(tǒng)計(jì)特征，而忽略了社會(huì)關(guān)系中的因素對(duì)人類移動(dòng)模式的影響。事實(shí)上，用戶偏好、社交關(guān)系等因素對(duì)人類移動(dòng)的預(yù)測至關(guān)重要。最近的發(fā)展轉(zhuǎn)向基于模型的方法［10-12］來進(jìn)行軌跡預(yù)測，利用序列統(tǒng)計(jì)模型如：馬爾可夫鏈（Markov Chain，MC）、循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）來捕捉人類運(yùn)動(dòng)的轉(zhuǎn)移規(guī)律，并從給定的訓(xùn)練語料庫中學(xué)習(xí)模型參數(shù)。

最近深度學(xué)習(xí)如卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）、長短時(shí)記憶網(wǎng)絡(luò)（Long Short-Term Memory Network，LSTM）、注意力機(jī)制（Attention Mechanism）等在許多領(lǐng)域逐漸嶄露頭角（如圖像處理、行人識(shí)別等領(lǐng)域［13］），并取得了比較突出的貢獻(xiàn)，為用戶軌跡預(yù)測提供了新的解決思路。Liu 等［14］在2016 年提出的ST-RNN（Spatial Temporal Recurrent Neural Network）模型利用時(shí)空上下文信息來分析用戶行為，使用并擴(kuò)展了RNN。ST-RNN 可以用不同時(shí)間間隔的時(shí)間-轉(zhuǎn)移矩陣和不同地理距離的距離-轉(zhuǎn)移矩陣對(duì)每一層的局部時(shí)空上下文進(jìn)行建模。Feng 等［15］沒有從傳統(tǒng)的用戶角度對(duì)POI 進(jìn)行探索，而是考慮了一個(gè)新的研究問題，即預(yù)測在給定的未來時(shí)間內(nèi)訪問給定的POI的用戶。該方法通過結(jié)合地理因素的影響，建模用戶偏好和POI 序列轉(zhuǎn)換，來預(yù)測給定POI的潛在訪問者。Feng 等［16］在2018 年設(shè)計(jì)了一種多模式嵌入循環(huán)神經(jīng)網(wǎng)絡(luò)，通過聯(lián)合嵌入控制人類活動(dòng)性的多種因素來捕獲復(fù)雜的軌跡序列的狀態(tài)轉(zhuǎn)換，同時(shí)還提出了兩種注意力機(jī)制模型，捕獲軌跡的多層次周期性。該模型有效地利用了周期性來增強(qiáng)循環(huán)神經(jīng)網(wǎng)絡(luò)的移動(dòng)模式預(yù)測。但上述模型都存在樣本量不足、足跡點(diǎn)稀疏等問題，沒有充分挖掘歷史軌跡的隱含信息，且無法高效地表示和利用整個(gè)歷史軌跡。

針對(duì)上述問題，本文使用深度學(xué)習(xí)中的一種新的自監(jiān)督學(xué)習(xí)方法對(duì)軌跡預(yù)測進(jìn)行建模。首先使用數(shù)據(jù)增強(qiáng)豐富樣本，提高模型的泛化能力。其次，結(jié)合軌跡的時(shí)序特點(diǎn)，將軌跡劃分為歷史軌跡和當(dāng)前軌跡，并使用RNN 對(duì)當(dāng)前軌跡進(jìn)行編碼，針對(duì)軌跡具有時(shí)間依賴性的特點(diǎn)，學(xué)習(xí)當(dāng)前軌跡數(shù)據(jù)中潛在的特征信息；使用CNN 學(xué)習(xí)用戶的歷史軌跡移動(dòng)模式，該方法可以有效地捕獲個(gè)人的長期運(yùn)動(dòng)模式，比常用的RNN的效率有所提升；同時(shí)使用了注意機(jī)制學(xué)習(xí)對(duì)歷史軌跡的關(guān)注度，可以利用最近軌跡的潛在表示來匹配用戶過去最相似的移動(dòng)方式。然后使用概率對(duì)比損失，捕獲對(duì)預(yù)測未來樣本最有用的信息，并采用負(fù)采樣（Negative Sampling，NS）的方法，每次隨機(jī)選擇一部分的負(fù)樣本來更新模型對(duì)應(yīng)的權(quán)重，使模型更容易訓(xùn)練。本文模型在Foursquare 和Gowalla 這兩個(gè)現(xiàn)實(shí)生活中具有代表性的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，在紐約測試集上的評(píng)估結(jié)果表明，SeNext 在Top@1 的預(yù)測準(zhǔn)確率比最新的VANext模型［17］高出10%以上，且優(yōu)于其他軌跡預(yù)測模型。

1 相關(guān)工作

通過分析以往軌跡預(yù)測的模型，可以將軌跡預(yù)測的手段分為兩類：一種是基于模式的方法，另一種是基于模型的方法。

1.1 基于模式的方法

基于模式的方法［8，18］首先從軌跡中發(fā)現(xiàn)常用的序列移動(dòng)模式，然后根據(jù)這些常用的模式來預(yù)測用戶的移動(dòng)行為。矩陣分解（Matrix Factorization，MF）［19］可以看作是一種探究軌跡移動(dòng)模式的方法，它在推薦系統(tǒng)中經(jīng)常出現(xiàn)，其基本思想是將用戶-項(xiàng)目矩陣分解為代表用戶和項(xiàng)目特征的兩個(gè)潛在矩陣。Cheng 等［8］通過將位置概率建模為多中心高斯模型，將MF 與地理影響融合在一起。Rendle等［20］將馬爾可夫（Markov）模型與矩陣分解相結(jié)合，提出了分解個(gè)性化馬爾可夫鏈（Factorizing Personalized Markov Chains，F(xiàn)PMC）模型來進(jìn)行項(xiàng)目推薦。Cheng 等［21］基于FPMC 提出了一種稱為FPMC-LR（FPMC with Localized Region constraint）的矩陣分解方法，在考慮局部區(qū)域約束的情況下捕獲馬爾可夫鏈的序列轉(zhuǎn)換。這些方法中的預(yù)定義移動(dòng)模式比較固定且片面，與基于模式的方法相比，本文模型不僅可以對(duì)所有用戶軌跡的轉(zhuǎn)移規(guī)律進(jìn)行建模，還可以基于個(gè)人歷史軌跡對(duì)個(gè)人偏好進(jìn)行建模。

1.2 基于模型的方法

基于模型的方法主要是馬爾可夫模型［22］及其變體，它們根據(jù)歷史軌跡在多個(gè)地點(diǎn)之間建立狀態(tài)轉(zhuǎn)移矩陣來對(duì)未來移動(dòng)的可能性進(jìn)行建模。為了捕獲位置轉(zhuǎn)移之間未觀察到的特征，Mathew 等［11］根據(jù)軌跡對(duì)位置進(jìn)行聚類，然后為每個(gè)用戶訓(xùn)練隱馬爾可夫模型?？紤]到用戶組群之間移動(dòng)模式的相似性，Zhang 等［12］提出了組級(jí)移動(dòng)性建模方法GMove 來共享重要的運(yùn)動(dòng)規(guī)律。盡管基于模型的軌跡預(yù)測取得了不錯(cuò)的結(jié)果，但仍難以挖掘出復(fù)雜軌跡序列的移動(dòng)特征。與現(xiàn)有基于Markov 的模型不同，本文模型通過對(duì)歷史軌跡和當(dāng)前軌跡的劃分，能更好地提取不同時(shí)間軌跡更鮮明的特征，可以對(duì)既有時(shí)間依賴性又有高度順序性的軌跡建模；同時(shí)使用對(duì)比學(xué)習(xí)，通過負(fù)采樣的方式對(duì)比錨與正樣本、錨與負(fù)樣本之間的相似度，獲取互信息。

1.3 數(shù)據(jù)增強(qiáng)

在訓(xùn)練模型時(shí)，研究人員經(jīng)常會(huì)遇到數(shù)據(jù)不足的情況。一些任務(wù)只有幾百條數(shù)據(jù)，這樣的數(shù)據(jù)訓(xùn)練出來的模型泛化性往往不好。深度學(xué)習(xí)在訓(xùn)練一個(gè)模型時(shí)，其優(yōu)化目標(biāo)是降低代價(jià)函數(shù)，使模型的損失最低。此時(shí)需要以正確的方式調(diào)整模型參數(shù)，而參數(shù)的數(shù)量與樣本量成正比，所以模型通常需要大量的數(shù)據(jù)。目前最先進(jìn)的神經(jīng)網(wǎng)絡(luò)都需要成千上萬的數(shù)據(jù)（如SimCLR（Simple framework for Contrastive Learning of visual Representations）模型［23］），而獲取數(shù)據(jù)是一件耗時(shí)且困難的事，需要采取一些方式達(dá)到降低代價(jià)的目的。

數(shù)據(jù)增強(qiáng)是指在沒有真正實(shí)質(zhì)性增加數(shù)據(jù)的基礎(chǔ)上，讓有限的樣本產(chǎn)生更多具有相同數(shù)據(jù)分布的樣本。數(shù)據(jù)增強(qiáng)需要保證變換前后的數(shù)據(jù)和初始樣本的主要特征和數(shù)據(jù)分布一致，確保模型能夠?qū)W習(xí)到數(shù)據(jù)中的模式。目前，數(shù)據(jù)增強(qiáng)在圖像學(xué)習(xí)領(lǐng)域被廣泛使用，通過對(duì)圖片進(jìn)行翻轉(zhuǎn)、縮放比例、扭曲、移位和添加高斯噪聲等，或者改變同一個(gè)場景下的不同投影方式（如光線、角度、距離和焦距等）來增加樣本量，提高模型的泛化能力。同時(shí)數(shù)據(jù)增強(qiáng)起正則化作用并避免過擬合，可以降低模型網(wǎng)絡(luò)結(jié)構(gòu)過于復(fù)雜的風(fēng)險(xiǎn)。訓(xùn)練樣本的豐富，會(huì)增加數(shù)據(jù)噪聲，能提升模型的魯棒性。本文模型利用現(xiàn)有的數(shù)據(jù)進(jìn)行數(shù)據(jù)增強(qiáng)，來獲取更好的實(shí)際效果。

1.4 自監(jiān)督學(xué)習(xí)

深度學(xué)習(xí)中的監(jiān)督學(xué)習(xí)需要足夠多的標(biāo)記數(shù)據(jù)，某些領(lǐng)域盡管數(shù)據(jù)很多，但大部分都是未標(biāo)記的數(shù)據(jù)。自監(jiān)督學(xué)習(xí)主要從大規(guī)模的無標(biāo)注數(shù)據(jù)中挖掘自身的監(jiān)督信息，通過這種構(gòu)造的有效監(jiān)督信息對(duì)模型進(jìn)行訓(xùn)練，可以學(xué)習(xí)到價(jià)值的表示。自監(jiān)督學(xué)習(xí)的方法主要可以分為三類：基于上下文（Context Based）、基于時(shí)序（Temporal Based）和基于對(duì)比（Contrastive Based）的方法。基于上下文的方法是根據(jù)數(shù)據(jù)本身的上下文信息來構(gòu)造任務(wù)，比如在自然語言處理領(lǐng)域中的word2vec［24］就是利用語句的順序來預(yù)測不同位置的詞語?；跁r(shí)序的自監(jiān)督學(xué)習(xí)主要是利用時(shí)序的約束關(guān)系來學(xué)習(xí)，如視頻中相鄰幀的特征都比較相似，而間距較遠(yuǎn)的視頻幀不太相似。另一種自監(jiān)督學(xué)習(xí)是以對(duì)比學(xué)習(xí)（Contrastive Learning，CL）為基礎(chǔ)，這種方法通過對(duì)比樣本的相似或不相似程度進(jìn)行編碼來學(xué)習(xí)數(shù)據(jù)的表示，通過構(gòu)建正樣本和負(fù)樣本，然后度量正負(fù)樣本的距離來實(shí)現(xiàn)自監(jiān)督學(xué)習(xí)，進(jìn)而使得更容易解決下游的任務(wù)。

對(duì)比自監(jiān)督學(xué)習(xí)作為一種比較突出的處理無標(biāo)簽或少量標(biāo)簽的方法，在圖像學(xué)習(xí)領(lǐng)域得到了廣泛的應(yīng)用并取得了巨大的成功。SimCLR 簡化了對(duì)比自監(jiān)督學(xué)習(xí)算法，不需要專門的架構(gòu)或者存儲(chǔ)庫，并證明了數(shù)據(jù)增強(qiáng)之后的樣本在定義有效的預(yù)測任務(wù)中起著至關(guān)重要的作用。CPC（Contrastive Predictive Coding）［25］使用自監(jiān)督里面的對(duì)比學(xué)習(xí)，通過對(duì)比正負(fù)樣本的互信息量，在潛在空間中預(yù)測未來可能發(fā)生的步驟。鑒于自監(jiān)督學(xué)習(xí)在這些模型上的成功，本文提出了基于對(duì)比自監(jiān)督學(xué)習(xí)的軌跡預(yù)測方法。本文模型將自監(jiān)督學(xué)習(xí)用在軌跡預(yù)測上，使用正負(fù)采樣的方法讓復(fù)雜的模型更易于訓(xùn)練。

2 問題定義

在預(yù)測人類移動(dòng)軌跡的模式中，主要目的是學(xué)習(xí)下一個(gè)POI 的預(yù)測。興趣點(diǎn)可以是一個(gè)GPS 點(diǎn)、一個(gè)區(qū)域的中心或者是一個(gè)用戶可以訪問的地址，該地址在適當(dāng)?shù)淖鴺?biāo)系中有唯一的標(biāo)識(shí)。本文定義c=為POI 的一個(gè)三元組表示，其中id、lo、la分別表示興趣點(diǎn)的ID、經(jīng)度和緯度。用戶u的軌跡可以表示為一個(gè)有序序列Tu=，其中：是用戶u在時(shí)間ti訪問的第i個(gè)興趣點(diǎn)。通常省略去用戶表示的上標(biāo)，簡寫為。一條軌跡T是連續(xù)且有序的POI 序列，將每條軌跡劃分為在時(shí)間間隔[t1，tn]內(nèi)的m段子軌跡，則T=T1，T2，…，Tm。

本文將軌跡劃分為歷史軌跡和當(dāng)前軌跡，用Th=T1，T2，…，Tm表示用戶完整的歷史軌跡，Tc=Tm+1=表示用戶的當(dāng)前子軌跡，其中當(dāng)前軌跡的長度通常小于歷史軌跡的長度。

人類軌跡預(yù)測問題通常被定義為：給定一個(gè)用戶ui、其對(duì)應(yīng)的歷史軌跡Th=T1，T2，…，Tm以及當(dāng)前軌跡Tc=，訓(xùn)練一個(gè)模型M去預(yù)測用戶ui的下一個(gè)興趣點(diǎn)，形式化表示為

3 軌跡預(yù)測模型

本文模型主要包括軌跡數(shù)據(jù)增強(qiáng)模塊、因果POI 嵌入模塊、當(dāng)前軌跡學(xué)習(xí)模塊、歷史軌跡學(xué)習(xí)模塊和分類器模塊。首先對(duì)初始劃分好的軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)增強(qiáng)處理；其次使用因果嵌入方法把當(dāng)前軌跡和歷史軌跡中的POI都嵌入到低維表示中；然后用變體RNN 對(duì)當(dāng)前軌跡Tc進(jìn)行編碼，用共享權(quán)重矩陣和CNN 對(duì)歷史軌跡Th進(jìn)行編碼；結(jié)合注意力機(jī)制搜索歷史軌跡Th，尋求與當(dāng)前軌跡Tc最相似的移動(dòng)軌跡；接著將當(dāng)前軌跡的最后一個(gè)隱藏狀態(tài)和歷史軌跡的注意力集中到一個(gè)特征表示中，并預(yù)測下一個(gè)POI；最后通過自監(jiān)督學(xué)習(xí)中的對(duì)比學(xué)習(xí)方式，使得樣本和正樣本之間的距離遠(yuǎn)遠(yuǎn)大于樣本和負(fù)樣本之間的距離，然后構(gòu)造一個(gè)Softmax 分類器，以正確分類正樣本和負(fù)樣本，進(jìn)而可以更好地訓(xùn)練模型。本文的軌跡預(yù)測模型框架如圖1所示。

圖1 基于自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型框架Fig.1 Framework of trajectory prediction model based on self-supervised learning

3.1 軌跡數(shù)據(jù)增強(qiáng)

在深入研究本文模型的實(shí)現(xiàn)方法之前，首先介紹軌跡數(shù)據(jù)處理方法。由于用戶的軌跡序列長度通常有所不同，一些用戶可能去過很多地點(diǎn)，而另一些用戶只是去了少量的地點(diǎn)。不同用戶在不同時(shí)間段內(nèi)的軌跡序列長度也不同，本文的目標(biāo)應(yīng)該是無論序列長度如何，都能準(zhǔn)確地預(yù)測出下一個(gè)興趣點(diǎn)。在此，本文提出了一種增強(qiáng)軌跡數(shù)據(jù)的方法。

文獻(xiàn)［26］首先提出對(duì)軌跡序列進(jìn)行預(yù)處理，本文分別為每個(gè)用戶的每條軌跡進(jìn)行數(shù)據(jù)增強(qiáng)。將初始輸入的軌跡序列與數(shù)據(jù)增強(qiáng)之后的軌跡序列一起作為新的訓(xùn)練序列。給定一條軌跡Si=l1，l2，…，ln，表示用戶i在給定時(shí)間段內(nèi)的一條子軌跡序列。數(shù)據(jù)增強(qiáng)之后的軌跡序列表示形式為“l(fā)1，l2”“l(fā)1，l2，l3”……“l(fā)1，l2，l3，…，ln”，然后將增強(qiáng)之后的軌跡數(shù)據(jù)送入模型進(jìn)行訓(xùn)練。將該方法用于所有的軌跡數(shù)據(jù)，圖2 是該方法的圖形示例，li表示一個(gè)簽入點(diǎn)，p表示要預(yù)測的下一個(gè)POI。

圖2 數(shù)據(jù)增強(qiáng)示意圖Fig.2 Schematic diagram of data augmentation

3.2 因果POI嵌入層

為了更好地呈現(xiàn)不同POI 之間的語義關(guān)系，本文模型采用因果嵌入的方法，將POI 從當(dāng)前軌跡和歷史軌跡嵌入到一個(gè)低維表示中。受word2vec 的啟發(fā)，之前的工作使用CBOW（Continuous Bag of Word）或Skip-Gram 模型將POI與上下文信息一起進(jìn)行嵌入。然而，對(duì)于預(yù)測下一個(gè)POI的問題，更感興趣的是嵌入軌跡的后續(xù)部分，而不是興趣點(diǎn)的上下文。這是因?yàn)楫?dāng)前的POI是由它之前的足跡而不是它之后的足跡決定的，這與高階馬爾可夫過程的思想非常相似。也就是說，當(dāng)嵌入POI時(shí)，不會(huì)將未來的位置泄露到過去。

可以通過因果嵌入層來實(shí)現(xiàn)，具體來說，給定先前的足跡點(diǎn)lτ-ω：lτ-1，通過預(yù)測歷史軌跡Th和當(dāng)前軌跡Tc中的當(dāng)前位置lτ來獲得簽到點(diǎn)的向量表示，其中：ω表示滑動(dòng)窗口的大?。粅ζ| 表示數(shù)據(jù)集中簽到點(diǎn)的數(shù)量；d表示矩陣的維度。然后最大化簽到點(diǎn)lτ被訪問的概率p(lτ|C(lτ))，由Softmax函數(shù)定義：

其中：l′表示被訪問過的lτ簽到點(diǎn)集合；l″∈ζ，每次表示ζ中的一個(gè)點(diǎn)，該點(diǎn)在式（1）中計(jì)算后再分別累加。為了加速模型計(jì)算，保證模型訓(xùn)練的效果，每次優(yōu)化參數(shù)只關(guān)注代價(jià)函數(shù)涉及的詞向量。本文采用了負(fù)采樣技術(shù)來避免對(duì)所有簽到點(diǎn)l″進(jìn)行枚舉，以提高模型處理的效率。

3.3 當(dāng)前軌跡和歷史軌跡模塊

該模塊使用門循環(huán)單元（Gate Recurrent Unit，GRU）來提取用戶當(dāng)前軌跡的簽到模式。值得注意的是，用戶的當(dāng)前軌跡往往小于歷史軌跡的長度，即|Tc|?|Th|。因此選擇RNN捕獲當(dāng)前軌跡數(shù)據(jù)的表示，由于GRU 具有參數(shù)少且易收斂等特性，所以選擇GRU作為神經(jīng)網(wǎng)絡(luò)單元，其更新過程：

其中：gτ是在τ時(shí)刻的更新門，控制著當(dāng)前的候選狀態(tài)中有多少是來源于上一時(shí)刻的候選狀態(tài)；候選狀態(tài)的計(jì)算和傳統(tǒng)的RNN單元很相似；sτ是重置門，決定了怎么將新的輸入信息與之前的信息相結(jié)合；σ為Sigmoid 激活函數(shù)，將數(shù)據(jù)轉(zhuǎn)換為區(qū)間［0，1］內(nèi)的值，用來充當(dāng)門控信號(hào)；⊙為哈達(dá)瑪積；W*和U*均為參數(shù)矩陣。

接下來對(duì)歷史軌跡Th進(jìn)行處理。在對(duì)歷史軌跡的處理中，先使用權(quán)重共享層多層感知機(jī)（Multi-Layer Preceptron，MLP）將每個(gè)POI 的嵌入向量合并到隱藏狀態(tài)；再利用非線性神經(jīng)網(wǎng)絡(luò)進(jìn)行1×D卷積來挖掘隱藏狀態(tài)，獲得的卷積狀態(tài)作為下一個(gè)注意力層的輸入；然后使用注意力機(jī)制來學(xué)習(xí)歷史軌跡中卷積狀態(tài)的權(quán)值。

其中：z是從當(dāng)前軌跡最后一個(gè)隱藏狀態(tài)中采樣的潛在變量；q為利用MLP 從z中獲取的向量；uti是q和ot間的相似度；ot為卷積層所獲得的卷積狀態(tài)；αi為通過Softmax 函數(shù)得到重要性權(quán)重。

然后通過對(duì)POI 加權(quán)求和得到了歷史軌跡的表示。為了預(yù)測Tc的下一個(gè)POI，需要將當(dāng)前軌跡的最后隱藏狀態(tài)hn+k-1和注意力歷史軌跡連接起來以獲得Φ，如下所示：

將Φ輸入Softmax 函數(shù)，計(jì)算數(shù)據(jù)集中每個(gè)POI 的概率p(l)。在訓(xùn)練時(shí)，將最小化預(yù)測下一個(gè)POI的經(jīng)驗(yàn)風(fēng)險(xiǎn)。

3.4 自監(jiān)督學(xué)習(xí)

當(dāng)前的機(jī)器學(xué)習(xí)訓(xùn)練方法大都依賴于手工標(biāo)注信息，這樣會(huì)導(dǎo)致樣本需求量大、模型脆弱等不良影響。本文使用自監(jiān)督學(xué)習(xí)的方法對(duì)模型進(jìn)行訓(xùn)練，通過學(xué)習(xí)編碼器k，使得：

其中：x通常被稱為錨數(shù)據(jù)，x+是與x相似或者相同的數(shù)據(jù)點(diǎn)，稱為正樣本；x-指的是與x不同的數(shù)據(jù)，稱為負(fù)樣本。fθ是一個(gè)由θ參數(shù)化的相似度衡量函數(shù)，用來衡量特征之間的相似性（如一個(gè)詞和它上下文的編碼表示之間的點(diǎn)積［27］，圖像與圖像的局部區(qū)域的編碼表示之間的點(diǎn)積［28］）。在對(duì)比自監(jiān)督學(xué)習(xí)中，通過對(duì)比正負(fù)樣本來學(xué)習(xí)表示，其目標(biāo)就是讓式（11）中左邊的部分盡可能大于右邊的部分，即讓正樣本x+與錨數(shù)據(jù)的相關(guān)程度盡可能最大化。

為解決此問題，首先引入互信息（Mutual Information，MI）來描述兩個(gè)變量之間的相關(guān)程度。假設(shè)存在一個(gè)隨機(jī)變量X，和另外一個(gè)隨機(jī)變量Y，那么它們的互信息是：

其中：H(X)是X的信息熵；H(X|Y)是已知Y的前提下，使X的不確定性減少的信息量，即X的信息熵。

互信息實(shí)際上是相對(duì)熵的特殊情形，它度量兩個(gè)對(duì)象之間的相關(guān)性，在信息論中可以看成是一個(gè)隨機(jī)變量中包含關(guān)于另一個(gè)隨機(jī)變量的信息量，如果信息量為0，則表示兩個(gè)隨機(jī)變量相互獨(dú)立。使用互信息理論進(jìn)行POI預(yù)測是基于如下假設(shè)：當(dāng)簽到點(diǎn)在某個(gè)特定類別出現(xiàn)頻率高，但在其他類別出現(xiàn)頻率比較低時(shí)，該簽到點(diǎn)與該類的互信息比較大，也就是說正樣本之間的互信息較大，負(fù)樣本之間的互信息小。

一般地，互信息I(X，Y)可以通過計(jì)算聯(lián)合概率分布p(x，y)與邊緣概率分布p(x)、p(y)乘積之間的相對(duì)熵（KL散度（Kullback-Leibler divergence，KLD））來確定變量之間的差異程度：

KL 散度越小，說明兩個(gè)變量之間接近彼此獨(dú)立，相互提供信息就很少，也就是互信息很小。最大化KL 散度，互信息MI 就越大，同時(shí)相似度衡量函數(shù)fθ也越大。在實(shí)際的應(yīng)用中，增大MI 很難實(shí)現(xiàn)，受到文獻(xiàn)［25］的啟發(fā)，本文模型減小MI 的下界，即優(yōu)化噪聲對(duì)比估計(jì)（Noise Contrastive Estimation，InfoNCE）損失函數(shù)：

在本模型中，每次負(fù)采樣包含一個(gè)正樣本x+和Nneg個(gè)負(fù)樣本x-，在對(duì)數(shù)據(jù)進(jìn)行詞向量訓(xùn)練時(shí)也用到了負(fù)采樣技術(shù)，這種對(duì)比方法已被廣泛應(yīng)用于一系列基于自監(jiān)督學(xué)習(xí)的語言、圖像和視覺識(shí)別任務(wù)中［23，25，29］。

由于InfoNCE 與交叉熵有關(guān)，幾乎包含隨機(jī)變量的所有可能值，并且它們是均勻分布的，所以最小化InfoNCE 等同于最小化標(biāo)準(zhǔn)交叉熵?fù)p失：

其中：y是指正樣本；是負(fù)樣本。同時(shí)，由這個(gè)方程可知InfoNCE 與最大化fθ(x，y)有關(guān)，基于上述方程，可以通過利用特定的X和Y來最大化原始數(shù)據(jù)不同變量之間的互信息。通過對(duì)比正負(fù)樣本與原始數(shù)據(jù)之間的相似程度，最大化正樣本對(duì)的互信息，提高了預(yù)測下一個(gè)POI的準(zhǔn)確性。

InfoNCE 損失可以同時(shí)優(yōu)化嵌入層和當(dāng)前和歷史軌跡模型。同時(shí)式（14）是一個(gè)分類交叉熵，用來區(qū)分?jǐn)?shù)據(jù)中的正負(fù)樣本。實(shí)際操作中可以通過Softmax 分類器來區(qū)分正負(fù)樣本。本文模型SeNext的算法流程如下所示。

4 實(shí)驗(yàn)與結(jié)果分析

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

本文模型在Foursquare 和Gowalla 這兩個(gè)數(shù)據(jù)集的四個(gè)城市上進(jìn)行實(shí)驗(yàn)，比較SeNext與幾個(gè)經(jīng)典模型的性能。

本文對(duì)Foursquare 和Gowalla 兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，從Foursquare 中選擇了紐約和新加坡兩個(gè)城市，從Gowalla 中選擇了加利福尼亞州和休斯敦這兩個(gè)區(qū)域的數(shù)據(jù)。對(duì)于每個(gè)數(shù)據(jù)集，刪除了少于5 個(gè)用戶訪問的POI。對(duì)于每個(gè)用戶，本文將所有簽到的位置連接起來形成一條軌跡。隨后，將每條軌跡劃分為子軌跡，設(shè)置每條軌跡的時(shí)間間隔為6 h。此外，本文篩選并剔除少于5 個(gè)子軌跡的用戶。對(duì)于所有數(shù)據(jù)集，選擇每個(gè)用戶前80%的子軌跡作為訓(xùn)練集，并選擇其余的20%作為測試數(shù)據(jù)。表1總結(jié)了預(yù)處理后的數(shù)據(jù)集統(tǒng)計(jì)信息。

表1 數(shù)據(jù)集統(tǒng)計(jì)信息Tab.1 Statistical information of datasets

4.2 實(shí)驗(yàn)設(shè)置

表2 描述了實(shí)現(xiàn)基于對(duì)比自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型的特定設(shè)置和超參數(shù)。對(duì)于嵌入層，單詞嵌入模型CBOW 的目的是給定上下文來預(yù)測輸入詞語。與之相反，Skip-Gram 是基于輸入詞語預(yù)測上下文。不同于分層Softmax（Hierarchical Softmax，HS）中每個(gè)訓(xùn)練樣本更新所有權(quán)重，負(fù)采樣（NS）每次只更新一部分權(quán)重。本文使用負(fù)采樣來確保計(jì)算效率和可擴(kuò)展性。實(shí)驗(yàn)環(huán)境是在Linux 的TensorFlow 框架上，并使用GTX1080 GPU加速計(jì)算。

表2 實(shí)驗(yàn)參數(shù)設(shè)置Tab.2 Setting of experimental parameters

4.3 基準(zhǔn)模型比較

為了驗(yàn)證本文提出模型的有效性，本文模型與幾種經(jīng)典模型以及有關(guān)下一個(gè)POI預(yù)測的最新模型進(jìn)行了比較，包括：

1）Markov chain［10］：馬爾可夫鏈?zhǔn)鞘褂霉烙?jì)的轉(zhuǎn)移概率預(yù)測POI的經(jīng)典方法之一。

2）ST-RNN［14］：是一種結(jié)合了時(shí)空上下文，并在RNN 框架內(nèi)預(yù)測用戶的下一次訪問的深度學(xué)習(xí)模型。

3）POI2vec［15］：是一種結(jié)合基于word2vec技術(shù)的地理影響來預(yù)測下一個(gè)POI的嵌入表示學(xué)習(xí)方法。

4）DeepMove［16］：是學(xué)習(xí)人類移動(dòng)性的第一個(gè)基于歷史注意力的方法，包括一個(gè)帶有RNN 的序列編碼模塊，用于從最近軌跡和歷史軌跡中學(xué)習(xí)移動(dòng)模式。

5）VANext［17］：它采用變分注意力機(jī)制對(duì)最近的軌跡進(jìn)行編碼，挖掘用戶軌跡的歷史移動(dòng)行為模式。

4.4 總體性能比較

表3 和表4 給出了四個(gè)數(shù)據(jù)集的Top@k性能比較?？梢钥吹?，就預(yù)測精度而言，所提出的基于對(duì)比自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型在所有方法中均表現(xiàn)出最佳的性能。

表3展示了模型在Top@1上的性能比較，從表3中可以發(fā)現(xiàn)，在紐約數(shù)據(jù)集和新加坡數(shù)據(jù)集上，SeNext在Top@1上的準(zhǔn)確率分別比VANext提高了11.10%和12.93%。在性能方面，基于深度神經(jīng)網(wǎng)絡(luò)的模型（ST-RNN、POI2vec、DeepMove）的預(yù)測精度高于傳統(tǒng)基于特征的嵌入方法和基于馬爾可夫鏈的方法。此外，DeepMove 通常比大部分基準(zhǔn)模型表現(xiàn)更好，因?yàn)樗軌蚶脷v史軌跡，而其他基準(zhǔn)模型只能在訓(xùn)練期間學(xué)習(xí)當(dāng)前軌跡中的序列模式。盡管所有這些方法都使用了RNN來獲取長期的POI 依賴，但由于RNN 存在固有的梯度消失問題，即使是LSTM 和GRU 也不能很好地處理非常長的歷史軌跡。這一結(jié)果符合了RNN 應(yīng)用于自然語言處理的局限性。因此，DeepMove 的主要優(yōu)勢在于它對(duì)歷史軌跡的重要性區(qū)分，這也證實(shí)了注意機(jī)制在處理序列數(shù)據(jù)方面的優(yōu)越性。

表3 不同模型在Top@1上的準(zhǔn)確率比較 單位：%Tab.3 Accuracy comparison of different models on Top@1 unit：%

另一方面，SeNext 優(yōu)于DeepMove，主要是因?yàn)橐氲能壽E預(yù)測模型不僅能更有效地捕捉短期的人類移動(dòng)模式，而且數(shù)據(jù)增強(qiáng)能增提升模型的泛化能力，同時(shí)使用對(duì)比自監(jiān)督學(xué)習(xí)方法中的負(fù)采樣使模型更易于訓(xùn)練。

表4 中展示了模型在Top@5 上的性能比較，與表3 中在Top@1 上的結(jié)果類似，基于對(duì)比自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型在所有方法中仍表現(xiàn)出最佳的性能。值得注意的是，對(duì)比表3和表4的實(shí)驗(yàn)結(jié)果，可以觀察到本文的模型在Top@5上提升的幅度低于Top@1。Top@1 強(qiáng)調(diào)的是預(yù)測結(jié)果取最后概率向量值最大的那一維作為預(yù)測結(jié)果，Top@5 是預(yù)測前五個(gè)中只要任意一個(gè)出現(xiàn)了目標(biāo)值即為預(yù)測正確，但這五個(gè)中也可能是排名靠后的第四個(gè)被判斷是正確的，這樣模型的判斷并非可靠。而本文模型是利用正負(fù)樣本對(duì)比學(xué)習(xí)的方式對(duì)模型進(jìn)行訓(xùn)練，正樣本即是正確的POI，負(fù)樣本是一個(gè)訓(xùn)練批次中除這個(gè)點(diǎn)之外其他任意的點(diǎn)，通過將正樣本與錨數(shù)據(jù)的相似度最大化，與負(fù)樣本相擬度的最小化，這使得模型更關(guān)注于Top@1而非Top@5。

表4 不同模型在Top@5上的準(zhǔn)確率比較 單位：%Tab.4 Accuracy comparison of different models on Top@5 unit：%

4.5 模塊性能比較

為了驗(yàn)證本文模型中各個(gè)模塊的有效性，本文采用不同的方式改變模塊來進(jìn)行實(shí)驗(yàn)。具體來說，DeepMove 主要利用RNN 和注意力機(jī)制從最近軌跡和歷史軌跡中學(xué)習(xí)移動(dòng)模式。VANext 在DeepMove 的基礎(chǔ)上增加了變分貝葉斯技術(shù)，利用變分注意力將最近的移動(dòng)性編碼為潛變量，并使用它來查詢用戶的歷史移動(dòng)性；而SeNext 進(jìn)一步將變分注意力替換為以自監(jiān)督學(xué)習(xí)的方式來挖掘軌跡中更有價(jià)值的表示。將本文基于自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型與DeepMove 和VANext 在紐約數(shù)據(jù)集上進(jìn)行比較，如圖3 所示，其中縱坐標(biāo)表示的是進(jìn)行對(duì)比的三個(gè)模型分別在Top@1、Top@5 和AUC（Area Under Curve）上的結(jié)果值。實(shí)驗(yàn)結(jié)果顯示，VANext 的預(yù)測效果要優(yōu)于DeepMove，表明變分注意力機(jī)制要比注意力機(jī)制更能匹配用戶過去最相似的移動(dòng)方式；而SeNext 優(yōu)于VANext，說明本文的對(duì)比自監(jiān)督學(xué)習(xí)方法可以更好地挖掘用戶軌跡的潛在移動(dòng)規(guī)律。在后續(xù)的工作中，會(huì)進(jìn)一步結(jié)合其他上下文POI 屬性信息，并改進(jìn)對(duì)比自監(jiān)督學(xué)習(xí)中的優(yōu)化函數(shù)來更好地提升預(yù)測效果。

圖3 模型性能比較實(shí)驗(yàn)結(jié)果Fig.3 Experimental results of model performance comparison

5 結(jié)語

本文提出了一種新穎的基于對(duì)比自監(jiān)督學(xué)習(xí)的軌跡預(yù)測模型，用于學(xué)習(xí)并預(yù)測下一個(gè)POI 的人類移動(dòng)模式。通過使用數(shù)據(jù)增強(qiáng)來豐富訓(xùn)練樣本，提高了模型的泛化能力。使用RNN 來獲取當(dāng)前軌跡的特征信息，使用CNN 與注意力機(jī)制來獲取并匹配與當(dāng)前軌跡最相似的用戶歷史移動(dòng)方式，大大提高了現(xiàn)有基于RNN 的方法的效率。通過對(duì)比自監(jiān)督的方式訓(xùn)練模型，更好地捕獲軌跡的移動(dòng)模式和多層次語義。未來進(jìn)一步的研究工作一部分將集中于結(jié)合其他的上下文POI屬性（例如博物館、餐廳），以提高模型的效率；另一種可能的擴(kuò)展是考慮用戶軌跡的交通運(yùn)行模式（例如步行、公共汽車、出租車）以提高模型綜合預(yù)測能力。