孫 亮

(蘭州文理學院 數(shù)字媒體學院，甘肅 蘭州 730000)

軌跡相似度計算是數(shù)據(jù)分析的重要步驟，亦是諸如路線規(guī)劃[1]、軌跡聚類[2]和交通優(yōu)化[3]等實際應用的關(guān)鍵技術(shù)。軌跡描述了物體隨時間在空間中移動的路徑，通常由一系列離散的點組成。為了衡量兩條軌跡之間的相似性，現(xiàn)有研究提出了多種度量[4-6]，但是這些度量需要二次的計算復雜度O(n2，其中n是軌跡的平均長度)，且在處理海量軌跡數(shù)據(jù)時，這些相似性度量會帶來較高的計算成本。另外，雖然上述度量對于測量歐幾里得空間中的軌跡相似度是有效的，但它們不能應用于空間網(wǎng)絡中的軌跡相似度計算問題。在實際應用場景中，對象大多是在空間網(wǎng)絡中移動，而不是在歐幾里得空間中移動。

對此，為了提高軌跡相似度計算的效率，本研究方案提出了基于圖神經(jīng)網(wǎng)絡的軌跡相似度計算優(yōu)化(TrajSimi-GNN)策略。TrajSimi-GNN是一種用于空間網(wǎng)絡相似度計算的軌跡表示學習框架，由三個步驟組成，即軌跡相似度度量、興趣點表示學習和軌跡嵌入學習。

1 軌跡相似度度量

空間網(wǎng)絡由無向圖G=(V,E)表示，其中每個頂點v∈V是空間網(wǎng)絡中的一個興趣點，表示道路的交叉口或道路終點，其屬性是緯度和經(jīng)度；每條邊e=(vi,vj)∈E代表兩個興趣點vi和vj之間的距離。原始軌跡τ={p1,p2,…,pk}由具有經(jīng)緯度的連續(xù)點組成，將該軌跡映射到距離最近的興趣點集合V中，生成對應的頂點軌跡τ={vn1,vn2,…,vnk}和軌跡的長度|τ|，|τ|定義為其中的興趣點數(shù)量。

道路網(wǎng)絡上兩條軌跡之間的相似性度量不僅要反映軌跡的屬性，還要反映空間網(wǎng)絡的屬性。對此，從興趣點距離和興趣點軌跡距離兩個方面來定義軌跡相似性。興趣點距離是道路網(wǎng)絡上兩個興趣點之間最短路徑的距離d(vi,vj)。

興趣點軌跡距離是指興趣點與軌跡之間的最短距離，但是計算興趣點和軌跡中所有興趣點之間的距離會消耗大量的計算資源。為了減少計算開銷，將興趣點軌跡距離定義為興趣點與軌跡中興趣點之間的最短興趣點距離，即對于軌跡τ，興趣點v的興趣點軌跡距離為：

(1)

結(jié)合興趣點距離和興趣點軌跡距離，可以定義軌跡τ1和軌跡τ2的相似度，如式(2)所示：

(2)

關(guān)于軌跡相似度計算問題，給定空間網(wǎng)絡G=(V,E)和軌跡集合T={τ1,τ2,…,τn}，對于任意的τi∈T，需要找到一個軌跡τj使sim(τi,τj)最小。為了解決這個問題，提出了兩步優(yōu)化框架TrajSimi-GNN，如算法1所示。

算法1 TrajSimi-GNN優(yōu)化算法

輸入：無向圖G=(V,E)，原始軌跡τ

(1)Forvi,vj∈Vdo

(2)d(vi,vj)←CalShorestPath(vi,vj);

(3) For each pairτ1,τ2do

(4) sim(τ1,τ2)←∑vi∈τ1e-d(vi,τ1)/|τ1|+∑vj∈τ2e-d(vj,τ2)/|τ2|;

(5) For eachv∈Vdo

(6)Ns(v)←RandomWalk();

(7) For eachvi,vj∈Vdo

(8) If (vi,vj)∈Edo

(9)Gij←1;

(10) Else

(11)Gij←0;

(12)A←I+αΩ(G);

(13) For eachvi∈Vdo

(15)E←LSTM(P);

(16) For each,τ1,τ2do

>sim(τi,τj));

2 興趣點表示學習

為了學習高質(zhì)量的興趣點表示，需要設計一個與學習軌跡相似度目標一致的目標函數(shù)。由軌跡相似度的定義可知，要計算相似度必須獲取興趣點之間的距離信息。興趣點之間有兩種關(guān)系：第一個關(guān)系是興趣點之間的拓撲關(guān)系，第二個關(guān)系是兩個興趣點是否屬于同一軌跡。這兩種關(guān)系可以統(tǒng)稱為興趣點的鄰居關(guān)系，對此可以使用能捕獲鄰居屬性的嵌入方法對該關(guān)系進行建模。

為了捕捉鄰居的屬性，TrajSimi-GNN使用Skip-gram嵌入方法，給定興趣點集合V={v1,v2,…,vm}，Skip-gram目標函數(shù)如式(3)所示：

(3)

其中f:v→Rd是將興趣點映射到d維向量的編碼器，P(·)是概率函數(shù)，Ns(v)?V是通過隨機游走算法所獲得的興趣點v鄰居。通過優(yōu)化該目標函數(shù)，學習到的興趣點嵌入將與其鄰居的嵌入有明確的聯(lián)系。

求解式(3)的計算效率并不高，對此需要在精度和效率之間做出權(quán)衡。對于給定的興趣點v，假設其鄰居都是相互獨立，這樣可以降低函數(shù)P(Ns(v)|f(v))的計算復雜度。在此假設下，函數(shù)P(Ns(v)|f(v))具有表達式(4)：

(4)

其中，P(vi|f(v))的表達式如式(5)所示：

(5)

對此，TrajSimi-GNN使用隨機游走算法來找到給定興趣點v的鄰居集合Ns(v)。給定起始點v和游走長度nw，隨機游走方法生成起始點為v、具有nw個節(jié)點的隨機路徑。假設co=v，生成第i個節(jié)點ci的轉(zhuǎn)移概率如式(6)所示：

(6)

其中πsx是從s到x的轉(zhuǎn)移概率，Z是歸一化常數(shù)。

TrajSimi-GNN使用基于采樣的方法，不只考慮前兩個節(jié)點，而是根據(jù)前兩個節(jié)點和起始節(jié)點來選擇下一個節(jié)點。前后兩個節(jié)點之間的關(guān)系可以保持圖的拓撲結(jié)構(gòu)，且軌跡信息將保持在下一個節(jié)點和起始節(jié)點之間的連接中。

假設隨機游走訪問了當前節(jié)點s的邊(t,s)，轉(zhuǎn)移概率定義為πsx=α(t,x)e-d(s,x)，其中α(t,x)為采樣概率，即：

(7)

其中dtx是在t和x之間包含最少數(shù)量的興趣點的路徑。

3 軌跡嵌入學習

雖然興趣點表示已經(jīng)從空間網(wǎng)絡中捕獲了信息，但仍需要將其納入學習軌跡嵌入的過程中，以捕獲來自不同方面的空間網(wǎng)絡信息：在興趣點表示學習的過程中，利用空間網(wǎng)絡使連接的興趣點在空間網(wǎng)絡中的嵌入相似；而在學習軌跡嵌入的過程中，需要更多來自空間網(wǎng)絡的節(jié)點連接信息，促進軌跡表示更具穩(wěn)定性和魯棒性。

軌跡表示的主要挑戰(zhàn)是由于搜索空間包含了所有興趣點組合的枚舉，導致搜索空間巨大， 因此無法獲得足夠的訓練實例來覆蓋所有可能的軌跡模式，引起數(shù)據(jù)稀疏問題。對此，可以利用圖神經(jīng)網(wǎng)絡(GNN)將更多空間網(wǎng)絡信息整合到每個軌跡中。

對于一個軌跡中的每個興趣點，可以強加其相鄰的興趣點以生成軌跡嵌入。如此一來，相似軌跡之間就會有更多的公共興趣點。因此，對于給定的軌跡，可以更容易地在訓練集中找到最相似的軌跡。

2.5 兩組不良反應發(fā)生率對比 觀察組不良反應發(fā)生率(16.07%)與對照組(10.71%)相比，差異無統(tǒng)計學意義(χ2=0.693，P=0.405)。見表6。

基于對軌跡中每個興趣點加強的興趣點構(gòu)建圖，并將該圖作為GNN的輸入。同時，可以使用空間網(wǎng)絡為GNN構(gòu)建相鄰圖，其中只有空間網(wǎng)絡中的興趣點才會在相鄰圖中連接。這樣一來，就可以直接結(jié)合空間網(wǎng)絡來計算軌跡表示。

給定興趣點集合V={v1,v2,…,vm}和權(quán)重集合E，鄰接圖G的構(gòu)造方式如式(8)所示：

(8)

由式(8)可知，鄰接圖G是對稱的，且其對角線元素均為0。

盡管如此，由于鄰接圖G中的元素值不等于節(jié)點之間的影響，因此該鄰接圖G仍然無法準確地反映興趣點之間的關(guān)系。對此，使用權(quán)重α來構(gòu)建拉普拉斯矩陣A，以準確刻畫鄰居的影響，即：

A=I+αΩ(G)

(9)

(10)

其中Ai是鄰接矩陣A中對應興趣點vi的行向量，Pi={pi,pi1;pi2；…pik}，W是將興趣點組合特征投影到新空間中的學習參數(shù)。

根據(jù)軌跡相似性的定義，本目標是為給定的軌跡找到最相似的軌跡，對此可以使用軌跡的嵌入向量之間的點積來表示它們之間的相似性。假設軌跡τiI和τj的嵌入向量分別是Ei和Ej，則相似度sim(τi,τj)的計算方式如下：

(11)

由于本目標是找到最相似的軌跡，并不需要計算準確的相似度分數(shù)，因此不需要在測試過程中進行實際的相似度計算。對此可以通過以下兩種方式確定目標函數(shù)：第一個是使用真實相似度的回歸損失來優(yōu)化式(11)；第二個是使用成對損失來最大化最相似軌跡和給定軌跡之間的相似性。使用成對損失作為目標函數(shù)。

給定軌跡訓練集Ttr，目標函數(shù)如下所示：

(12)

4 實驗評估

本節(jié)試圖通過大量實驗來驗證所提出的方法的有效性，將提出的方法與四個最先進的基線方法進行比較。實驗使用兩個城市的路網(wǎng)作為空間網(wǎng)絡，分別記為RN1和RN2。RN1數(shù)據(jù)集是北京市的路網(wǎng)數(shù)據(jù)，由28341個興趣點和27688條邊組成；RN2數(shù)據(jù)集是紐約市的路網(wǎng)數(shù)據(jù)，由95581個興趣點和260855條邊組成。實驗環(huán)境是工作站，配置了i7-11700 2.5 GHz處理器，該處理器擁有8個核心和6個線程，內(nèi)存為32 GB，固態(tài)硬盤的內(nèi)容為1 T，圖形處理器GPU為RTX 3060TI。

對于RN1中的軌跡，使用T-drive項目中的出租車駕駛數(shù)據(jù)，出租車軌跡是通過出租車的標識號收集得到。由于一條軌跡的時間范圍可能持續(xù)數(shù)天，因此按照小時分割這些軌跡，總共得到 5621428條軌跡。對于RN2中的軌跡，使用來自該城市的出租車駕駛數(shù)據(jù)，該數(shù)據(jù)集包含了10541288條軌跡。兩個軌跡數(shù)據(jù)集隨機分為訓練集、評估集和測試集，比例分別為20%、10%和70%。

興趣點嵌入的維數(shù)為128，所提出的采樣策略中的參數(shù)p和q都設置為1。GNN嵌入的維度和軌跡的維度均從范圍[32,64,128,256]中選擇。控制GNN中鄰居影響的參數(shù)α選自[0，0.9]的范圍。Adam被用作為優(yōu)化器來訓練所提出的方法，Adam的學習率為0.001。

實驗中使用Top-K命中率(TPH)作為指標來展示不同方法的性能，其定義如式(13)所示：

(13)

實驗選擇了TrajSeqtoSeq[7]、Siamese[8]和NeuTraj[9]三種方法進行對比。其中，TrajSeqtoSeq使用序列到序列模型來學習軌跡的表示，使用均方誤差作為損失函數(shù)來進行優(yōu)化；Siamese是基于連體網(wǎng)絡的時間序列學習方法，使用交叉熵作為目標函數(shù)來進行訓練；NeuTraj對LSTM的結(jié)構(gòu)進行修改以學習嵌入。

兩個數(shù)據(jù)集的實驗結(jié)果如圖1所示。由實驗結(jié)果可知，所提出的TrajSimi-GNN在所有指標上均優(yōu)于其他方法，其中的主要原因是TrajSimi-GNN利用了來自空間網(wǎng)絡的信息，而其他方法僅考慮了網(wǎng)格的信息。與NeuTraj相比，TrajSimi-GNN的興趣點的嵌入生成獨立于軌跡相似性學習，而NeuTraj則是同時學習這兩方面。另外，NeuTraj利用回歸損失來學習兩條軌跡之間的實際相似性，而TrajSimi-GNN可以學習軌跡之間的偏序關(guān)系。這兩個因素都提高了軌跡相似度計算的性能，因此TrajSimi-GNN的性能要優(yōu)于NeuTraj。

圖1 Top-K命中率結(jié)果對比

TrajSimi-GNN優(yōu)于TrajSeqtoSeq的原因是TrajSimi-GNN使用嵌入向量的點積來計算兩個軌跡之間的相似性，而TrajSeqtoSeq使用嵌入向量之間絕對差的范數(shù)。使用點積計算相似度可以有效地在間接連接的樣本之間傳播信息，在計算相似度方面比線性運算更有效。

Siamese 中的交叉熵損失無法學習相似和不相似軌跡之間的偏序關(guān)系。Siamese的目標是使相似軌跡之間的相似性盡可能大，然而這種優(yōu)化過程會導致過擬合。而TrajSimi-GNN的損失函數(shù)可以避免這個問題：如果相似軌跡之間的預測相似度大于不相似軌跡之間的相似度，它的值將為零。

下面的實驗分析了參數(shù)和軌跡嵌入維數(shù)對TrajSimi-GNN性能的影響。如圖2所示，不同的參數(shù)值會使實驗結(jié)果產(chǎn)生較大的差異。當α的值為0.1時，TrajSimi-GNN的性能最好，這意味著TrajSimi-GNN學習到了較佳的軌跡相似性。當α的值太大時，TrajSimi-GNN的性能會變差。這是因為在這種情況下，鄰接圖中的權(quán)重不能反映興趣點之間的實際關(guān)系。

圖2 參數(shù)α對性能的影響

軌跡嵌入維度的影響如圖3所示。軌跡嵌入的維度決定了訓練過程中軌跡嵌入可以包含多少信息。如果維度太小，則會導致欠擬合問題，模型無法很好地擬合訓練數(shù)據(jù)集。 同時；如果維度太大，可能會導致過擬合問題，模型無法在測試數(shù)據(jù)集上取得良好的性能。

圖3 軌跡嵌入維度對性能的影響

5 結(jié)論

本研究提出了基于深度學習的空間網(wǎng)絡軌跡相似度計算優(yōu)化策略，即TrajSimi-GNN。TrajSimi-GNN通過考慮空間網(wǎng)絡的結(jié)構(gòu)來捕獲軌跡的底層路線信息，對缺乏可用訓練實例和由系統(tǒng)錯誤引入的噪聲具有魯棒性。結(jié)合真實數(shù)據(jù)集，將TrajSimi-GNN與現(xiàn)有的策略進行比較，驗證了TrajSimi-GNN的有效性。在未來的工作中，將擴展TrajSimi-GNN來共同學習軌跡的空間和時間信息，并通過改善圖神經(jīng)網(wǎng)絡模型來進一步提高TrajSimi-GNN的整體性能。