基于地理空間感知型表征學(xué)習(xí)的軌跡相似度計算

摘要：度量軌跡間的相似性不僅是一項基礎(chǔ)的研究問題, 同時也為眾多軌跡數(shù)據(jù)挖掘應(yīng)用提供支持。傳統(tǒng)相似性度量方法面臨數(shù)據(jù)噪聲敏感、算法效率低等問題, 難以進(jìn)行大規(guī)模數(shù)據(jù)計算。當(dāng)前研究開始嘗試使用深度表征學(xué)習(xí)方法, 將高維軌跡數(shù)據(jù)映射到低維向量空間, 通過度量表征間的距離高效地完成相似度計算任務(wù)。本文在軌跡表征學(xué)習(xí)中引入Transformer機(jī)制, 提出了一種地理空間感知的深度軌跡表征學(xué)習(xí)方法。首先, 使用Geohash編碼將二維空間坐標(biāo)點(diǎn)轉(zhuǎn)換為一維編碼序列, 使軌跡點(diǎn)在嵌入過程中保留空間相關(guān)性。然后, 引入Transformer框架構(gòu)建軌跡表征的深度學(xué)習(xí)模型, 并采用一種隱軌跡點(diǎn)訓(xùn)練模式, 以保證模型能從低頻、噪聲的數(shù)據(jù)中習(xí)得更穩(wěn)健的向量表示。最后, 設(shè)計了一個空間感知損失函數(shù), 通過距離因子調(diào)整模型誤差, 拉近空間相近軌跡的表征。試驗表明, 本文方法在軌跡相似性計算任務(wù)中超越了基準(zhǔn)模型, 并且計算效率遠(yuǎn)高于傳統(tǒng)度量方法。

(相關(guān)資料圖)

引 言

通信技術(shù)和位置采集設(shè)備日新月異，衛(wèi)星、監(jiān)控系統(tǒng)和移動設(shè)備無時無刻不在收集各種地理時空對象的軌跡數(shù)據(jù)，并廣泛應(yīng)用于位置推薦

[1

-2

]

、智慧交通

[3

-5

]

和公共安全

[6

-7

]

等場景中。學(xué)者們挖掘軌跡數(shù)據(jù)中蘊(yùn)含的豐富信息與知識，在軌跡數(shù)據(jù)挖掘領(lǐng)域開展大量研究，如目的地預(yù)測

[8

-9

]

、移動群體發(fā)現(xiàn)

[10

-12

]

和軌跡聚類

[13

-14

]

等。而眾多研究均依賴于一項基礎(chǔ)工作，即軌跡相似性度量，只有正確度量軌跡之間的相似與差異情況，才能進(jìn)一步開展相關(guān)的挖掘工作。經(jīng)典方法(如LCSS、DTW和EDR等)主要基于逐點(diǎn)匹配的思想，雖然可以實(shí)現(xiàn)軌跡間相似度的計算，但受制于算法效率低、噪聲影響大、擴(kuò)展性和遷移性弱等問題，難以在海量數(shù)據(jù)場景中落地。

近年來，受自然語言處理(nature language processing，NLP)技術(shù)的啟發(fā)(如NNLM

[15

]

、word2vec

[16

]

)，學(xué)習(xí)數(shù)據(jù)的向量化通用表征已經(jīng)在語言翻譯、文本分類，乃至圖像檢索等相似性分析任務(wù)中取得巨大的成功。學(xué)者們將這個思想借鑒到軌跡挖掘任務(wù)中，催生了軌跡表征學(xué)習(xí)這一研究方向。不同于傳統(tǒng)“經(jīng)緯度坐標(biāo)-時間戳”的數(shù)據(jù)格式，軌跡表征是通過深度神經(jīng)網(wǎng)絡(luò)將高維軌跡映射到低維向量空間，在保留軌跡原有特征的基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)的降維表達(dá)。軌跡表征模型可以從大量訓(xùn)練數(shù)據(jù)中學(xué)習(xí)到地理對象的真實(shí)移動路徑，從而糾正異常數(shù)據(jù)中的噪聲點(diǎn)、漂移點(diǎn)，提升相似性計算的精度；同時，將原始的采樣軌跡轉(zhuǎn)化為一維向量后，相似性計算的效率得以大幅度提升，更適用于大規(guī)模數(shù)據(jù)挖掘應(yīng)用。

當(dāng)前軌跡表征學(xué)習(xí)技術(shù)主要是借鑒循環(huán)神經(jīng)網(wǎng)絡(luò)的編碼-解碼架構(gòu)，如序列到序列(seq2seq)

[17

]

，來學(xué)習(xí)軌跡序列數(shù)據(jù)的表征。文獻(xiàn)[18—19]將軌跡轉(zhuǎn)化為空間網(wǎng)格編碼序列，使用seq2seq的學(xué)習(xí)模型來獲取軌跡表征，并應(yīng)用于軌跡相似性計算，克服了軌跡采樣不一致、點(diǎn)位漂移等問題；文獻(xiàn)[20]基于滑動窗口思想提取了軌跡的動態(tài)特征作為行為序列，并用seq2seq模型生成行為序列的深度表征，解決了軌跡聚類中的時空偏移問題；文獻(xiàn)[21]采用地圖匹配方法將軌跡映射為道路編號序列，同時通過預(yù)訓(xùn)練任務(wù)捕獲路段之間的相關(guān)性，二者融合后再使用seq2seq模型來學(xué)習(xí)軌跡表征。這些方法雖然可以實(shí)現(xiàn)高維軌跡向低維向量的轉(zhuǎn)換，但依然存在兩個問題：①基于空間網(wǎng)格的方法將軌跡點(diǎn)表示為獨(dú)立的網(wǎng)格編號，使得軌跡點(diǎn)在編碼階段丟失了原有的地理空間相關(guān)性，在解碼過程中也無法依據(jù)空間距離關(guān)系來計算模型損失；②seq2seq的編解碼器是基于循環(huán)神經(jīng)網(wǎng)絡(luò)，容易出現(xiàn)信息遺忘問題，導(dǎo)致模型對長序列軌跡的建模能力差，難以捕獲軌跡的全局信息。

為了解決上述問題，本文提出一種基于地理空間感知型表征學(xué)習(xí)的軌跡相似度計算方法，總體流程如圖 1所示。首先，在軌跡點(diǎn)嵌入過程中引入Geohash編碼方法，保證軌跡點(diǎn)從二維向一維轉(zhuǎn)換的過程中保留它們的空間位置關(guān)系，并通過門控循環(huán)神經(jīng)網(wǎng)絡(luò)(GRU)捕獲編碼間的相關(guān)性。然后，本文將Transformer模型引入軌跡表征學(xué)習(xí)中，利用注意力機(jī)制讓模型學(xué)習(xí)各個軌跡點(diǎn)之間的空間相關(guān)性，捕獲長序列軌跡的全局信息。同時，模型采用隱軌跡點(diǎn)訓(xùn)練模式，通過隨機(jī)掩蔽的方法模擬真實(shí)世界中軌跡的采樣頻率不一致、失真等問題，使軌跡表征模型更具穩(wěn)健性。本文還設(shè)計了一個空間感知的損失函數(shù)，根據(jù)預(yù)測位置與目標(biāo)位置的空間距離對模型損失進(jìn)行加權(quán)，進(jìn)一步提升模型的精度。最后，通過余弦函數(shù)度量軌跡表征，完成軌跡相似度計算。本文在大型公開數(shù)據(jù)集中評估模型的表現(xiàn)，試驗證明，本文方法在相似性度量任務(wù)中表現(xiàn)優(yōu)于基準(zhǔn)模型，同時在計算效率上遠(yuǎn)超傳統(tǒng)度量算法。

圖 1本文方法流程 Fig. 1Flowchart of the proposed method

1 地理空間感知的深度軌跡表征模型1.1 問題定義

定義1：軌跡序列，軌跡T是由移動對象產(chǎn)生的一系列時空采樣點(diǎn)p組成。點(diǎn)p包含對象的地理位置(x,y)(即經(jīng)度和緯度)和時間戳t。

定義2：軌跡表征學(xué)習(xí)，給定一條離散采樣的軌跡數(shù)據(jù)T，軌跡表征的目的是找到一個映射

將軌跡數(shù)據(jù)轉(zhuǎn)化為低維空間中的向量V∈R

d

(d是向量空間的維度)。本文中該映射函數(shù)即為一個經(jīng)過訓(xùn)練的深度神經(jīng)網(wǎng)絡(luò)編碼器。

軌跡表征旨在反映了地理對象在現(xiàn)實(shí)路徑上的活動情況，不僅需要克服數(shù)據(jù)采樣不一致和噪聲影響，還要盡可能地保留原始軌跡數(shù)據(jù)的時空屬性

[22

]

。

定義3：基于表征的相似性度量，給定兩條采樣軌跡T

a

和T

b

，經(jīng)軌跡表征編碼后得到向量V

a

和V

b

，通過計算兩個向量之間的距離來評估軌跡間的相似度。本文以余弦函數(shù)作為度量公式，即

1.2 地理空間感知的軌跡點(diǎn)嵌入

軌跡點(diǎn)的位置通常用緯度和經(jīng)度來描述，雖然數(shù)值上它們是連續(xù)的，但它們并不適合直接輸入到深度學(xué)習(xí)模型中，其原因有兩個：首先，緯度和經(jīng)度可以描述整個地球表面，但實(shí)際軌跡所經(jīng)過的地點(diǎn)，通常只占地球表面一個非常小的區(qū)域。因此，用軌跡點(diǎn)的經(jīng)緯度坐標(biāo)來訓(xùn)練的模型會受到了稀疏性問題的影響。第二，緯度和經(jīng)度之間有很強(qiáng)的相互作用關(guān)系，只有通過聯(lián)合使用它們才能識別一個地點(diǎn)。如果將它們作為兩個獨(dú)立的值輸入，模型將難以捕獲這種地理空間的關(guān)聯(lián)性

[23

]

。為解決以上問題，本文引入了Geohash編碼。Geohash是一種常見的地理編碼，其原理是將地球理解為一個二維平面，將平面按規(guī)律遞歸剖分成更小的網(wǎng)格，每個網(wǎng)格表示一定的經(jīng)緯度范圍，范圍內(nèi)所有的經(jīng)緯度坐標(biāo)都用相同的一維編碼進(jìn)行表示。Geohash編碼的優(yōu)勢是在數(shù)據(jù)降維的基礎(chǔ)上保留坐標(biāo)的空間鄰近屬性。如圖 2(右側(cè))所示，先將上海東方明珠電視塔的坐標(biāo)(121.499 706°E，31.239 893°N)依據(jù)Geohash標(biāo)準(zhǔn)轉(zhuǎn)換為二進(jìn)制碼，再按照固定間隔劃分后轉(zhuǎn)換為十進(jìn)制序列[28, 25, 28, 3, 24, 31, 1]。序列的長度與其所代表空間網(wǎng)格的精度呈正相關(guān)，本文軌跡點(diǎn)坐標(biāo)轉(zhuǎn)換后的編碼長度設(shè)為7，表示空間網(wǎng)格尺寸約為150 m×150 m。以整數(shù)序列進(jìn)行表示具有兩個優(yōu)點(diǎn)：①將二維離散的空間坐標(biāo)轉(zhuǎn)換為一維的數(shù)字序列，更適合作為模型和算法的輸入；②序列編碼有效地保存了空間位置的鄰近關(guān)系，在空間上相近的點(diǎn)位，它們的序列前綴保持一致。

圖 2地理空間感知的深度軌跡表征學(xué)習(xí)模型 Fig. 2Geography-aware deep trajectory representation learning model

將空間軌跡點(diǎn)轉(zhuǎn)換為序列編碼后，需要進(jìn)一步將其映射到高維空間中，提取編碼的深度信息同時捕獲序列間的相關(guān)性。這里采用門控循環(huán)神經(jīng)網(wǎng)絡(luò)(GRU)

[24

]

來進(jìn)行軌跡點(diǎn)編碼的嵌入。GRU是長短期記憶網(wǎng)絡(luò)(LSTM)

[25

]

的變體，它能夠?qū)W習(xí)順序數(shù)據(jù)的長期依賴性，而不會導(dǎo)致性能下降。GRU通過引入一個更新門z和一個復(fù)位門r來控制信息在時間步長內(nèi)的流動，從而順序地更新隱藏態(tài)。在i∈{1, 2, …,n}的每個序列位置，給定位置編碼l

i

和前一位置的隱藏態(tài)向量e

i-1

，通過以下公式得到e

i

(1)

(2)

(3)

(4)

式中，W代表各個門控單元的權(quán)重；b是它們的偏差；σ是Sigmoid激活函數(shù)。這里將軌跡點(diǎn)編碼嵌入過程進(jìn)行簡化為

(5)

最后的狀態(tài)e

n

∈R

d

即為感知了空間信息的軌跡點(diǎn)嵌入表示，它將進(jìn)一步作為軌跡表征學(xué)習(xí)模型的輸入。

1.3 基于Transformer的軌跡表征學(xué)習(xí)框架

目前，已有的軌跡表征模型均是基于序列到序列的方法，由一個基于循環(huán)神經(jīng)網(wǎng)絡(luò)的編碼器將輸入軌跡轉(zhuǎn)化為指定維度的向量，再通過一個解碼器將這個向量還原為軌跡序列。但基于循環(huán)神經(jīng)網(wǎng)絡(luò)的單向傳播模式難以捕獲長序列的全局信息，容易出現(xiàn)信息遺忘的現(xiàn)象，這制約了軌跡表征的效果。最近出現(xiàn)的Transformer模型

[26

]

在自然語言處理與圖像處理領(lǐng)域的相關(guān)任務(wù)中表現(xiàn)優(yōu)越，其成功主要?dú)w因于內(nèi)部的自注意力機(jī)制，該機(jī)制保證模型可以學(xué)習(xí)到序列中各個位置之間的相關(guān)性，捕獲序列的長程依賴關(guān)系?；诖?，本文將它引入到軌跡表征的學(xué)習(xí)任務(wù)中。

圖 2展示了基于Transformer框架的軌跡表征學(xué)習(xí)模型。

Transformer編碼器是由一個自注意力層和一個前饋網(wǎng)絡(luò)層組成，自注意力層以序列張量E∈R

m×d

(m表示序列的長度)作為輸入，然后通過W

Q

,W

K

,W

v

∈R

d×d

3個不同的矩陣轉(zhuǎn)換運(yùn)算后，得到帶有不同位置權(quán)重的輸出，公式為

(6)

需要注意的是，由于自注意力編碼器不能像RNN那樣捕捉序列中的相對位置，本文參考文獻(xiàn)[27]的方法，將融合位置編碼P與張量E融合，即E=E+P。函數(shù)Attn()表示一種通過矩陣點(diǎn)積的計算機(jī)制，公式為

(7)

自注意力層的輸出將被輸入到前饋網(wǎng)絡(luò)層中，它包含一個簡單全連接層和一個ReLU激活函數(shù)，分別用于捕獲維度內(nèi)部的相關(guān)性和非線性變換。前饋網(wǎng)絡(luò)層在第i個位置的計算公式為

(8)

經(jīng)過N個Transformer編碼器的計算后，得到輸出張量F∈R

m×d

。為了進(jìn)一步求取軌跡的全局表征，需引入了一個池化層對輸出張量進(jìn)行降維。本文采用的池化策略為平均池化，最終得到軌跡序列的深度表征V。

1.4 隱軌跡點(diǎn)訓(xùn)練模式

現(xiàn)實(shí)世界中的活動軌跡往往采樣頻率不一致，同時伴有噪聲點(diǎn)、漂移點(diǎn)等問題，對軌跡數(shù)據(jù)挖掘相關(guān)任務(wù)產(chǎn)生很大的影響。針對這個問題，本文設(shè)計了一個隱軌跡點(diǎn)訓(xùn)練模式

[27

]

，通過隨機(jī)地隱藏部分軌跡點(diǎn)，或加入位置偏移的噪聲，讓模型根據(jù)上下文關(guān)系預(yù)測被隱藏的軌跡點(diǎn)。首先，對原始軌跡序列進(jìn)行處理，通過隨機(jī)掩蔽將原始軌跡模擬成帶噪聲的軌跡，如圖 2中將掩蔽軌跡點(diǎn)用[MASK]標(biāo)識。本文的掩蔽方式有兩種：一種是將軌跡點(diǎn)編碼序列替換為指定的標(biāo)號，且該標(biāo)號與原有編碼值不重復(fù)；另一種是將軌跡點(diǎn)編碼序列中任意位置的編號進(jìn)行隨機(jī)替換，替換后的編碼序列代表空間位置中的另一個點(diǎn)位，以此構(gòu)建噪聲點(diǎn)。模型的目標(biāo)是利用上下文的點(diǎn)位來預(yù)測被掩蔽的軌跡點(diǎn)，這種訓(xùn)練模式能夠有效拉近空間相鄰點(diǎn)的向量表征。最后，將預(yù)測得到的軌跡點(diǎn)表征輸入解碼器，還原為軌跡點(diǎn)編碼序列，并與真值進(jìn)行比較，計算模型損失。解碼器使用的是與軌跡點(diǎn)嵌入方法中相同的GRU網(wǎng)絡(luò)。

隱軌跡點(diǎn)訓(xùn)練模式模擬了真實(shí)采樣軌跡的噪聲情況，讓模型能夠克服點(diǎn)位漂移的影響，使最終的軌跡表征模型具有更強(qiáng)的穩(wěn)健性；同時隱軌跡點(diǎn)訓(xùn)練模式還可以讓模型學(xué)習(xí)到序列中每個位置之間的相關(guān)性，使軌跡點(diǎn)表征具備空間上下文的特性，即使面對低頻采樣軌跡，模型依然可以得到有效的軌跡表征。

1.5 空間感知損失函數(shù)

損失函數(shù)是模型訓(xùn)練過程中十分重要的部分，它的差異會導(dǎo)致模型習(xí)得不同的表征。當(dāng)前表征學(xué)習(xí)主要應(yīng)用交叉熵?fù)p失函數(shù)進(jìn)行模型優(yōu)化，其公式為

(9)

由于本文采用基于Geohash的軌跡點(diǎn)編碼方法，它將坐標(biāo)點(diǎn)轉(zhuǎn)化為帶有空間信息的整數(shù)序列。這個序列的前后關(guān)系代表了不同空間尺度，序列位置靠前表示的空間范圍越大，且每個位置的編號對應(yīng)該空間尺度下的不同網(wǎng)格。交叉熵?fù)p失函數(shù)中的y

i

∈R

c

是解碼器在第i個位置的輸出，通過Softmax函數(shù)將其轉(zhuǎn)化為c個類別(網(wǎng)格編碼)的概率值。這種損失函數(shù)并不適用于空間數(shù)據(jù)，因為該計算方法將序列中所有位置的損失都認(rèn)為是相等的，使得模型無論在序列中哪個位置預(yù)測錯誤，懲罰都是一致的。而軌跡數(shù)據(jù)的空間相關(guān)性很強(qiáng)，預(yù)測點(diǎn)與目標(biāo)點(diǎn)的空間距離決定了它們之間的相似程度，如果距離越小，那么模型的損失也應(yīng)減小。根據(jù)這一思想，本文設(shè)計了一個具有地理空間感知能力的損失函數(shù)，它能夠在不同空間尺度下設(shè)置動態(tài)的懲罰系數(shù)，同時在尺度內(nèi)按照預(yù)測格網(wǎng)與目標(biāo)網(wǎng)格的空間距離設(shè)置損失，具體公式為

(10)

(11)

式中，w

ic

是距離因子，它由網(wǎng)格編碼c和當(dāng)前解碼位置i決定；||c-y

i

||表示編碼c與模型輸出y

i

所代表網(wǎng)格的空間距離；dist/i是一個尺度系數(shù)，代表不同序列位置的空間尺度，具體系數(shù)值根據(jù)Geohash位數(shù)換算得到。

2 試驗與分析

2.1 數(shù)據(jù)集與試驗設(shè)置

試驗在開源的波爾圖出租車數(shù)據(jù)集上進(jìn)行，該數(shù)據(jù)集中約170萬條軌跡，時間跨度為19個月，每輛出租車的軌跡采樣時間間隔為15 s。數(shù)據(jù)預(yù)處理中去掉了長度小于20的軌跡，得到約120萬條軌跡，并按照8∶1∶1的比例劃分為訓(xùn)練集、驗證集、測試集。模型訓(xùn)練過程中，軌跡點(diǎn)掩蔽比例設(shè)置為[0.0，0.2，0.4，0.6]。模型共訓(xùn)練50輪(epoch)，訓(xùn)練過程中采用early stopping策略，當(dāng)模型在驗證集上的損失不再下降時，模型停止訓(xùn)練。由于計算機(jī)內(nèi)存有限，本文試驗將訓(xùn)練數(shù)據(jù)集分為不同批次輸入模型，批大小(batch size)設(shè)置為256。本文的深度學(xué)習(xí)模型優(yōu)化器采用Adam

[28

]

，并將初始學(xué)習(xí)率設(shè)置為0.001。所有模型均是在一臺帶有兩個GTX 2080Ti圖形處理器和英特爾i7 7700K中央處理器的計算機(jī)上用開源編程語言Python實(shí)現(xiàn)的。

2.2 對比模型與相似性度量指標(biāo)

軌跡的相似性計算是數(shù)據(jù)挖掘分析中最重要的任務(wù)之一，本文通過這項經(jīng)典任務(wù)來評估軌跡表征模型的效果。試驗選取的對比模型可以分為兩類，一是傳統(tǒng)的度量算法，包含DTW

[29

]

、EDR

[30

]

和LCSS

[31

]

，其中DTW用于解決兩個時序數(shù)據(jù)不對齊的問題，后被廣泛應(yīng)用于軌跡相似性計算；EDR和LCSS分別基于編輯距離和最長公共子序列的方法來進(jìn)行軌跡相似性度量。二是基于軌跡表征的深度學(xué)習(xí)模型，包含GRU和t2vec。其中GRU是門控循環(huán)神經(jīng)網(wǎng)絡(luò)，它屬于循環(huán)神經(jīng)網(wǎng)絡(luò)的一個變體，本文通過預(yù)測下一個軌跡點(diǎn)位置的方式來訓(xùn)練模型，并取其最后一個時間步的隱藏態(tài)作為軌跡表征；t2vec

[18

]

是一項關(guān)于深度軌跡表征的開創(chuàng)性工作，它通過seq2seq模型來學(xué)習(xí)軌跡表征，解決了軌跡點(diǎn)采樣不一致、噪聲敏感等問題，是目前最先進(jìn)的軌跡相似度計算方法。

由于真實(shí)數(shù)據(jù)缺少可用標(biāo)簽，本文采用文獻(xiàn)[18]中的相似軌跡查詢排名方法來評估模型的性能：從測試集中隨機(jī)選擇了10 000條軌跡作為待查詢軌跡，表示為P，然后另選擇1000條軌跡作為查詢軌跡，表示為Q。對于Q中的每條軌跡，通過交替取點(diǎn)來創(chuàng)建兩條子軌跡，表示為T

q

和T

q′

，并構(gòu)建兩個數(shù)據(jù)集D

Q

和D′

Q

。對P中的軌跡執(zhí)行相同的操作，得到D

P

和D′

P

。對于每條查詢軌跡T

q

，將其與數(shù)據(jù)集D′

Q

∪D′

P

中所有軌跡進(jìn)行相似度計算，之后觀察T

q

與T

q′

的相似度在所有軌跡相似度中的排名。理想情況下，T

q

與T

q′

的相似度應(yīng)排在第一名，因為它們是由同一條軌跡生成的。最終統(tǒng)計Q中1000條軌跡的平均排名作為性能評估指標(biāo)。對于軌跡表征模型，試驗采用余弦函數(shù)來度量兩個軌跡表征之間的向量距離作為其相似性計算結(jié)果。

2.3 試驗結(jié)果

待查詢數(shù)據(jù)集P的軌跡數(shù)量為2000~10 000，各模型相似軌跡查詢的平均排名情況見表 1。當(dāng)數(shù)據(jù)集規(guī)模變大時，所有模型的平均排名均有下降，這是因為隨著數(shù)據(jù)集內(nèi)的軌跡數(shù)量增加，更多與目標(biāo)相似的軌跡出現(xiàn)，影響了平均排名。傳統(tǒng)方法中，DTW的軌跡查詢平均排名情況最差，EDR和LCSS算法的表現(xiàn)接近。基于深度軌跡表征的方法中，GRU并沒有取得突出的效果，主要原因是其單向的訓(xùn)練模式難以獲取有效的全局軌跡表征。t2vec模型采用序列到序列編解碼結(jié)構(gòu)，有效地實(shí)現(xiàn)軌跡深度表征，試驗結(jié)果超越了傳統(tǒng)度量方法。表格下半部分展示了本文方法的消融試驗，僅使用Transformer進(jìn)行軌跡表征，效果較t2vec有小幅提升，證明了該框架相比基于seq2seq的模型具有更強(qiáng)的表征能力。引入軌跡點(diǎn)嵌入模塊(trajectory point embedding，TE)代替一般的網(wǎng)格編碼，模型的性能得到提升，說明具備地理空間相關(guān)性的編碼有助于軌跡的降維表征。進(jìn)一步將交叉熵?fù)p失函數(shù)(L

1

)改進(jìn)為空間感知損失函數(shù)(L

2

)后，模型性能達(dá)到最優(yōu)，主要原因是相似軌跡往往出現(xiàn)在相同的空間路徑上，L

2

損失函數(shù)能夠根據(jù)空間距離來動態(tài)調(diào)整懲罰值，可以有效拉近相似軌跡的表征，有助于提升相似度計算的表現(xiàn)。試驗結(jié)果顯示本文提出的具備地理空間感知能力的軌跡表征模型，在相似軌跡查詢平均排名的表現(xiàn)較t2vec提升了約23.5%，較傳統(tǒng)方法精度提升約55.3%。

表 1不同數(shù)據(jù)集規(guī)模的平均排名對比

Tab. 1Comparison of mean rank with different database sizes

為進(jìn)一步驗證本文方法的穩(wěn)健性，試驗評估了模型對不同長度和不同采樣率的軌跡的表征能力。將待查詢數(shù)據(jù)集P的規(guī)模固定為2000，觀察各模型的相似軌跡查詢排名情況。由圖 3可知，當(dāng)降采樣頻率提升時，LCSS模型性能退化最為嚴(yán)重，表明傳統(tǒng)方法對降采樣后的軌跡較為敏感，缺失軌跡點(diǎn)會嚴(yán)重影響模型的相似性度量的表現(xiàn)。而基于深度軌跡表征的方法能在一定程度上克服低頻采樣軌跡的影響，本文提出的方法較t2vec還有提升，是因為自注意力機(jī)制成功捕獲了軌跡內(nèi)所有軌跡點(diǎn)之間的相關(guān)性，即使部分軌跡點(diǎn)缺失，模型依然可以得到有效的表征。圖 4展示了模型針對不同長度軌跡的表征能力，試驗將軌跡按不同長度區(qū)間篩選后，進(jìn)行相似軌跡查詢并觀察平均排名情況。隨著軌跡長度的提升，GRU和t2vec模型的表征能力開始退化，這是因為基于循環(huán)神經(jīng)網(wǎng)絡(luò)的單向傳播結(jié)構(gòu)更注重相鄰時間步的信息，忽略了軌跡序列中靠前位置的影響。而本文方法能夠捕獲軌跡內(nèi)所有軌跡點(diǎn)的依賴關(guān)系，因此對長軌跡依然有較強(qiáng)的表征能力。

圖 3不同降采樣率下的平均排名對比 Fig. 3Comparison of mean rank with different down-sampling rates

圖 4不同軌跡長度的平均排名對比 Fig. 4Comparison of mean rank with different trajectory lengths

深度學(xué)習(xí)模型的參數(shù)設(shè)置會導(dǎo)致結(jié)果存在差異，本文試驗將討論不同表征維度與池化策略對模型表征能力的影響。由圖 5可知，當(dāng)表征維度為32時，模型性能最差。這是因為表征的維度大小將決定該表征蘊(yùn)含信息的容量，當(dāng)表征維度過小，數(shù)據(jù)向量化的過程中就會出現(xiàn)信息丟失，導(dǎo)致模型性能退化；而提高表征維度，就需要足夠多的訓(xùn)練樣本來滿足向量空間的表達(dá)。本文試驗中當(dāng)維度大小為128時，模型的表征能力最佳?；赥ransformer的表征模型需要進(jìn)一步連接一個池化層以得到序列的全局表征，試驗分別采用了First池化策略(選取序列首位的表征代表全局表征)、Max池化策略(選取序列中的最大值代表全局表征)和Average池化策略(選取序列中所有位置的平均值代表全局表征)，由圖 5可以發(fā)現(xiàn)First池化策略的表現(xiàn)最差，盡管模型中自注意力機(jī)制能夠捕獲序列中任意位置的相關(guān)性，但只選取序列首位仍然不足以反映軌跡的全局情況。Average池化策略在試驗中的表現(xiàn)最優(yōu)，證明該策略更適用于全局軌跡表征。未來工作將進(jìn)一步研究如何獲取更好的軌跡全局表征，如將池化層代替為神經(jīng)網(wǎng)絡(luò)層，通過微調(diào)的方式來改善模型的表現(xiàn)，同時匹配更多下游任務(wù)。

圖 5表征維度與池化策略對平均排名的影響 Fig. 5The dimension size and the pooling strategy impact on mean rank

圖選項

最后，圖 6展示了軌跡表征學(xué)習(xí)方法與傳統(tǒng)相似性度量方法在計算效率上的區(qū)別。試驗從測試集中隨機(jī)選取了20 000條軌跡并計算兩兩軌跡間的相似性。DTW和LCSS均是基于動態(tài)規(guī)劃思想，按順序匹配軌跡點(diǎn)后進(jìn)行距離計算，導(dǎo)致算法的時間復(fù)雜度為O(n

2

)，其中n為數(shù)據(jù)集中軌跡序列的平均長度?；诒碚鞯姆椒ㄊ鞘褂镁€下訓(xùn)練好的深度學(xué)習(xí)模型，將待計算軌跡編碼為一維向量，并通過余弦函數(shù)度量向量之間的距離，屬于線性復(fù)雜度O(n+d)，其中d是向量的維度。在未使用加速算法的情況下，本文試驗中DTW和LCSS完成計算耗時為78 643 s和76 970 s。深度表征模型雖然訓(xùn)練成本較高(本文模型在約100萬條數(shù)據(jù)上訓(xùn)練18 h)，但將訓(xùn)練好的模型部署到線上能夠大幅度提升軌跡相似性度量任務(wù)的計算效率，最終本文模型與t2vec完成計算耗時分別為2198 s與2184 s。

圖 6模型計算效率對比 Fig. 6Efficiency comparison with different methods

3 結(jié)語

軌跡相似性度量是眾多軌跡挖掘任務(wù)的基礎(chǔ)工作，傳統(tǒng)算法對數(shù)據(jù)質(zhì)量敏感且計算效率低，因此研究借助深度表征學(xué)習(xí)方法，將原始軌跡數(shù)據(jù)映射到低維向量空間后進(jìn)行相似度計算。但現(xiàn)有的軌跡表征模型均是基于樸素的空間網(wǎng)格編碼結(jié)合序列到序列的編解碼結(jié)構(gòu)來學(xué)習(xí)，這使得軌跡點(diǎn)的空間位置屬性丟失，同時難以構(gòu)建長軌跡的全局表征。針對這些問題，本文提出了一個地理空間感知型軌跡表征學(xué)習(xí)模型，通過Geohash編碼使軌跡點(diǎn)在嵌入過程中保留地理空間屬性，并首次引入Transformer框架進(jìn)行軌跡表征學(xué)習(xí)，利用自注意力機(jī)制解決了長軌跡信息遺忘的問題。同時，本文采用隱軌跡點(diǎn)訓(xùn)練模式保證模型能從低頻、有噪聲的軌跡中習(xí)得穩(wěn)健的表征。為了進(jìn)一步提升模型的效果，本文還設(shè)計了一個空間感知函數(shù)，通過距離因子調(diào)節(jié)模型的損失。在波爾圖公開數(shù)據(jù)集中，本文方法在軌跡相似性度量任務(wù)中超越了基準(zhǔn)模型。同時試驗也證明了軌跡表征方法較傳統(tǒng)度量模型的高效性。在后續(xù)研究中，將進(jìn)一步引入對比學(xué)習(xí)機(jī)制

[32

]

，解決軌跡向量表征的各向異性問題，提升模型對正負(fù)樣本的區(qū)分能力；考慮引入軌跡的時間屬性和語義信息

[33

]

，如道路信息、興趣點(diǎn)信息等，擴(kuò)充深度模型的軌跡表征能力，使軌跡表征與更多下游任務(wù)耦合，如目的地預(yù)測、軌跡分類等。

關(guān)鍵詞：