李小昌 陳貝 董啟文 陸雪松

摘要：隨著移動(dòng)設(shè)備的廣泛應(yīng)用，當(dāng)今的位置跟蹤系統(tǒng)不斷產(chǎn)生大量的軌跡數(shù)據(jù)。同時(shí)，許多應(yīng)用亟需具備從移動(dòng)物體的軌跡數(shù)據(jù)中挖掘出一起旅行的物體（旅行同伴）的能力，如智慧交通系統(tǒng)和智慧營(yíng)銷?，F(xiàn)有算法或是基于模式挖掘方法，按照特定模式匹配旅行同伴：或是基于表征學(xué)習(xí)方法，學(xué)習(xí)相似軌跡的相似表征。前一種方法受限于點(diǎn)對(duì)匹配的問(wèn)題，后一種方法往往忽略軌跡之間的時(shí)間相近性。為了改善這些問(wèn)題，提出了一個(gè)基于自編碼器的深度表征學(xué)習(xí)模型Mean-Attn（Mean-Attention），用于發(fā)現(xiàn)旅行同伴。Mean-Attn分別使用低維稠密向量表征和位置編碼技術(shù)，將空間和時(shí)間信息同時(shí)注入軌跡的嵌入表征中;此外，還利用Sort-Tile-Recursive（sTR）算法、均值運(yùn)算和全局注意力機(jī)制，鼓勵(lì)軌跡向鄰近的軌跡學(xué)習(xí);從編碼器獲得軌跡表征后，利用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）對(duì)表征進(jìn)行聚類，從而找到旅行同伴。實(shí)驗(yàn)結(jié)果表明，Mean-Attn在尋找旅行同伴方面的表現(xiàn)要優(yōu)于傳統(tǒng)的數(shù)據(jù)挖掘算法和最新的深度學(xué)習(xí)算法。

關(guān)鍵詞：旅伴同伴;自編碼器;時(shí)空信息;STR算法;注意力機(jī)制

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A DOI：10.3969/j.issn。1000-5641.202091003

0引言

挖掘結(jié)伴同行的移動(dòng)物體（旅行同伴）在許多實(shí)際應(yīng)用中是一個(gè)非常有價(jià)值的問(wèn)題。例如，在智慧交通系統(tǒng)中，交通流的優(yōu)化需要依賴道路傳感器監(jiān)控車流量。如果傳感器能夠發(fā)現(xiàn)大量汽車正沿同一路徑行進(jìn)，交通管制人員則可以及時(shí)管控和調(diào)整車輛行進(jìn)路線，以減輕可能發(fā)生的交通擁堵。再如，在移動(dòng)廣告中，有研究證明，在同一時(shí)間出現(xiàn)在同一地點(diǎn)的消費(fèi)者，通常會(huì)表現(xiàn)出共同的消費(fèi)偏好。因而，發(fā)現(xiàn)一起行走的消費(fèi)者群體，并向他們發(fā)放同一產(chǎn)品類別的優(yōu)惠券，有可能會(huì)增加廣告的營(yíng)銷效益。尋找旅行同伴在其他方面也有著廣泛應(yīng)用，包括機(jī)場(chǎng)安防、動(dòng)物遷徙監(jiān)測(cè)和公共游行管理等。

旅行同伴可以從物體的軌跡中挖掘。物體的軌跡是指按時(shí)間順序排列的一系列位置點(diǎn)，而旅行同伴的軌跡在空間和時(shí)間上都比較接近，即在相近的時(shí)間內(nèi)互相有大量彼此靠近的位置點(diǎn)?，F(xiàn)有的旅行同伴挖掘方法可以大致分為兩類：一類是基于模式挖掘的方法;另一類是基于表示學(xué)習(xí)的方法?；谀Ｊ酵诰虻姆椒ǎǔＪ紫纫罁?jù)專家經(jīng)驗(yàn)來(lái)定義和旅行同伴有關(guān)的軌跡模式，即相似的軌跡，然后開發(fā)相應(yīng)的算法從軌跡數(shù)據(jù)集中挖掘預(yù)定義的模式。這類算法中，軌跡的相似性計(jì)算通?；邳c(diǎn)對(duì)之間的歐氏距離，因此要求待檢驗(yàn)的軌跡按照時(shí)間戳對(duì)齊。但是，實(shí)際應(yīng)用中的軌跡通常包含許多缺失的位置點(diǎn)，必須通過(guò)插值補(bǔ)齊后才能有效對(duì)齊，因而在挖掘過(guò)程中會(huì)引入大量的測(cè)量誤差。另外，基于表示學(xué)習(xí)的方法不需要定義模式或逐點(diǎn)比較，而是使用機(jī)器/深度學(xué)習(xí)模型來(lái)學(xué)習(xí)軌跡的嵌入表征，然后將這些表征進(jìn)行聚類，從而挖掘出相似的軌跡?，F(xiàn)有的軌跡表征模型，一般需要一定的特征工程，或者需要特定的標(biāo)簽以進(jìn)行有監(jiān)督學(xué)習(xí)。在實(shí)踐中，特征工程通常依賴于問(wèn)題的定義并且很耗時(shí)，會(huì)給數(shù)據(jù)挖掘帶來(lái)額外的開銷;而軌跡標(biāo)簽信息通常很難收集，并且在使用時(shí)經(jīng)常存在倫理問(wèn)題。除此以外，現(xiàn)有模型更多關(guān)注的是軌跡之間空間接近性上的特征，而忽略了軌跡之間時(shí)間接近性上的特征。因而，這樣挖掘出的軌跡雖然形狀相似，但并不一定對(duì)應(yīng)一起旅行的同伴。

為了解決上述問(wèn)題，本文開發(fā)了一種基于自編碼器的無(wú)監(jiān)督模型MEAN-Attn。該模型可以直接從原始軌跡中學(xué)習(xí)表征，輸入的原始軌跡不需要按照時(shí)間戳對(duì)齊，即允許具有不同數(shù)量的位置點(diǎn)，也即軌跡長(zhǎng)度可以不同。模型學(xué)習(xí)到的表征同時(shí)包含了原始軌跡的空間和時(shí)間特征，從而允許通過(guò)聚類軌跡表征的方式來(lái)發(fā)現(xiàn)旅行同伴。Mean-Attn的靈感來(lái)源于文本摘要模型MeanSum。MeanSum模型可以用于對(duì)主題相似的文本進(jìn)行摘要式總結(jié)。基于此，本文首先使用STR算法對(duì)原始軌跡進(jìn)行分組。STR算法最初用于對(duì)空間數(shù)據(jù)進(jìn)行分組，以支持R樹的批量構(gòu)建。利用STR分組，可以使同一組內(nèi)的軌跡具有一定的時(shí)空接近性。隨后，從每組軌跡中抽取小的批次輸入基于注意力的自編碼器中。這背后的想法是鼓勵(lì)時(shí)空上更近的軌跡能互相學(xué)習(xí)到更多相似的表征，同時(shí)在軌跡嵌入的時(shí)候，本文使用了位置編碼技術(shù)，將軌跡的時(shí)間信息注入模型的輸入表征中。然后，對(duì)每組軌跡學(xué)到的表征做均值計(jì)算，并使用一個(gè)解碼器一編碼器結(jié)構(gòu)對(duì)表征均值進(jìn)行重編碼。模型的損失函數(shù)分為兩部分：一部分是軌跡的重構(gòu)損失，用以控制軌跡學(xué)習(xí)自身的特征;另一部分是前述重編碼表征和相應(yīng)批次中其他軌跡表征的相似性，用以引導(dǎo)批次中的軌跡互相學(xué)習(xí)對(duì)方的特征。由于在編碼時(shí)使用了注意力機(jī)制，并且使用均值計(jì)算來(lái)聚合一個(gè)批次的編碼，因此本文將模型稱為Mean-Attn自編碼器。當(dāng)模型訓(xùn)練完畢，就可以使用它的編碼器對(duì)軌跡進(jìn)行編碼，然后使用聚類算法，如DBSCAN，對(duì)編碼得到的表征進(jìn)行聚類。最后，在聚類后同一個(gè)簇中的表征所對(duì)應(yīng)的軌跡中，同時(shí)具有時(shí)間和空間上的相似性的可視為旅行同伴。

1相關(guān)工作介紹

1.1基于點(diǎn)對(duì)匹配的同伴挖掘

在過(guò)去的10年中，尋找旅行同伴的問(wèn)題在數(shù)據(jù)挖掘領(lǐng)域已經(jīng)有了非常廣泛的研究。一些具有代表性的研究主要是Flock、Convoy、Swarm和Gathering。本文重點(diǎn)闡述與本文要解決的問(wèn)題更相關(guān)的Convoy和Swarm這兩個(gè)工作。Flock、Gathering與Convoy、Swarm這兩個(gè)工作類似，但是定義旅行同伴模式的方法不同。Convoy被定義為一組至少包含m個(gè)移動(dòng)物體的集合，且要求集合中中的移動(dòng)物體需要在至少k個(gè)連續(xù)時(shí)間點(diǎn)內(nèi)都是密度連通的：首先，通過(guò)在每個(gè)時(shí)間點(diǎn)執(zhí)行聚類算法，發(fā)現(xiàn)密度聯(lián)通的簇后，找出那些在連續(xù)的時(shí)間點(diǎn)內(nèi)能夠至少維護(hù)n個(gè)簇的對(duì)象;然后把這些對(duì)象加入Convoy候選集;最后，對(duì)于候選集中的每個(gè)對(duì)象，對(duì)其中的所有簇相交以測(cè)試所有的簇是否至少包含m個(gè)相同的軌跡。為了緩解計(jì)算復(fù)雜度過(guò)高的問(wèn)題，Jeung等建議，首先根據(jù)簡(jiǎn)化的軌跡挖掘Convoy候選集，然后在微調(diào)步中確定每個(gè)候選集是否確實(shí)合格。另一個(gè)類似的工作是Swarm，它通過(guò)將旅行同伴定義為在至少k個(gè)可能不連續(xù)的時(shí)間點(diǎn)內(nèi)具有密度連通特性的移動(dòng)物體。這個(gè)定義放松了Convoy對(duì)旅行同伴的約束，即k個(gè)時(shí)間點(diǎn)可以不連續(xù)。這項(xiàng)工作的目的是發(fā)現(xiàn)所有封閉的群體，即群體中的軌跡集或者時(shí)間點(diǎn)都不能被擴(kuò)大。由于候選的封閉Swarm數(shù)量過(guò)高，因此Li等提出了利用兩種剪枝策略來(lái)縮小模式的搜索空間。

1.2基于表征學(xué)習(xí)的軌跡相似度計(jì)算

近年來(lái)，軌跡的表征學(xué)習(xí)引起了很多關(guān)注。因?yàn)樗鼛缀醪恍枰卣鞴こ?，并且不依賴于基于點(diǎn)對(duì)的相似度計(jì)算，一旦表征被學(xué)習(xí)到，就可以非常高效地將表征用于其他任務(wù)。與本文工作最相關(guān)的研究包括軌跡聚類和基于表征學(xué)習(xí)的軌跡相似度計(jì)算。Yao等使用序列到序列的自編碼器來(lái)學(xué)習(xí)軌跡表征，并用于軌跡聚類任務(wù)：首先提取軌跡特征，例如速度和轉(zhuǎn)彎速率等;然后將其轉(zhuǎn)換為能描述相應(yīng)對(duì)象移動(dòng)模式的特征序列;最后，將特征序列輸入自編碼器模型，以學(xué)習(xí)固定長(zhǎng)度的軌跡表征。隨后，Li等提出了一種基于循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）的模型來(lái)學(xué)習(xí)用于相似度計(jì)算的軌跡表征。該模型不需要特征提取，直接從原始軌跡中學(xué)習(xí)表征。但是，該模型的訓(xùn)練是有監(jiān)督學(xué)習(xí)，需要對(duì)每條原始軌跡進(jìn)行下采樣，以構(gòu)建訓(xùn)練對(duì)。值得一提的是，這兩個(gè)工作都只關(guān)注尋找具有相似形狀的軌跡，因此它們所發(fā)現(xiàn)的相似軌跡，有可能是時(shí)間上間隔很遠(yuǎn)的軌跡，因此不能被直接用來(lái)發(fā)現(xiàn)旅行同伴。另外，Zhang等的模型將額外的語(yǔ)義信息（例如環(huán)境約束和軌跡活動(dòng)）注入到模型中，以獲得更精確的軌跡表征。盡管如此，到目前為止還沒(méi)有發(fā)現(xiàn)一個(gè)現(xiàn)有模型可以同時(shí)學(xué)習(xí)軌跡之間的時(shí)間相似性和空間相似性。

2Mean-Attn模型

2.1軌跡點(diǎn)的嵌入表征

首先，對(duì)于給定的軌跡數(shù)據(jù)集，將整個(gè)空間劃分為大小相同的正方形單元。然后使用低維稠密表征技術(shù)對(duì)所有單元的嵌入表征進(jìn)行預(yù)訓(xùn)練，使得空間上接近的單元具有更相似的嵌入表征。對(duì)于軌跡中的每個(gè)點(diǎn)，使用該點(diǎn)所在單元格的表征作為其表征，那么每條軌跡就可以表示為它所有點(diǎn)的表征的序列。

其次，為了捕獲軌跡的時(shí)間特征，使用位置編碼技術(shù)將時(shí)間信息注入軌跡的每個(gè)點(diǎn)的表征中。位置編碼原先被用于Transformer模型中用來(lái)捕獲文本中各個(gè)單詞之間的位置信息。由于已經(jīng)將軌跡表示成了一個(gè)標(biāo)識(shí)序列，因此可以使用相同的機(jī)制來(lái)給每個(gè)標(biāo)識(shí)加入時(shí)間信息。位置編碼PE（Positional Encoding）的計(jì)算方法為（本文用PpE表示）

2.2Mean-Attn自編碼器

為了鼓勵(lì)每條軌跡更多地向時(shí)空接近的軌跡學(xué)習(xí)，首先根據(jù)軌跡的時(shí)空接近性將它們粗略地劃分為不同的組，然后將每個(gè)組獨(dú)立地輸入到自編碼器中。這里使用STR算法對(duì)軌跡進(jìn)行分組。STR算法最初用于將空間接近的對(duì)象打包為最小邊界矩形MBR（Minimum Bounding Rectangle），并用來(lái)構(gòu)建R樹索引的批量加載。由于每個(gè)軌跡都可以視為三維空間（t，x，y）中的一個(gè)對(duì)象，其中t是時(shí)間維度，x和y代表兩個(gè)空間維度，因此可借用STR的思想粗略地對(duì)軌跡進(jìn)行分組。被分到同一個(gè)MBR的軌跡在時(shí)間上和空間上都更為接近，因此更有可能是旅行同伴。隨后從每個(gè)MBR中單獨(dú)抽取軌跡，組成小批次送入模型，相比原來(lái)開放式地抽取軌跡組成一個(gè)批次，小批次的處理更有可能包含旅行同伴，從而有更多的機(jī)會(huì)學(xué)習(xí)到彼此相似的特征。

整個(gè)模型由兩個(gè)共享參數(shù)的自編碼器構(gòu)建，如圖1所示。左側(cè)的編碼器和解碼器構(gòu)成了第一個(gè)自編碼器，用于重構(gòu)每條輸入的軌跡。編碼器和解碼器均采用LSTM（Long Short-Term Memory）網(wǎng)絡(luò)。在模型右側(cè)是一個(gè)解碼器一編碼器結(jié)構(gòu)。首先，對(duì)左側(cè)的編碼器輸出的一個(gè)小批次的軌跡表征進(jìn)行均值運(yùn)算，得到一個(gè)小批次的平均編碼，后將其送入右側(cè)的解碼器，將解碼器輸出的中間軌跡再次輸?shù)接覀?cè)的編碼器中，以獲得重編碼的軌跡平均表征;然后，計(jì)算左側(cè)編碼器輸出的每條軌跡的編碼與右側(cè)編碼器輸出的平均軌跡的重編碼之間的相似性，用以控制軌跡在自我編碼的同時(shí)，盡量學(xué)習(xí)與其鄰近軌跡的特征。為了既保證軌跡的自我重構(gòu)，又保證從鄰近軌跡學(xué)到相似的表征，左右兩側(cè)的兩個(gè)編碼器和解碼器分別需要共享相同的結(jié)構(gòu)和參數(shù)。

在兩個(gè)LSTM編碼器上，本文還使用全局注意力機(jī)制來(lái)匯總每個(gè)步驟的隱藏狀態(tài)，以形成最終的輸出編碼。該編碼考慮了整個(gè)軌跡的全局信息，實(shí)驗(yàn)證明能夠提高編碼的表征能力。具體來(lái)說(shuō)，首先初始化與軌跡點(diǎn)維度相等的全局注意力向量a，用來(lái)計(jì)算軌跡中每個(gè)軌跡點(diǎn)的注意力得分，相應(yīng)公式為其中，Hti表示在左側(cè)模塊中編碼器生成的針對(duì)ti軌跡的注意力聚合編碼，Ht'代表由右側(cè)的編碼器生成的平均軌跡重編碼。通過(guò)同時(shí)最小化重構(gòu)損失和相似性損失，迫使編碼器產(chǎn)生的編碼，既保持軌跡自身的獨(dú)特特征，也能從同一組中的鄰居軌跡那里學(xué)到相似的特征。這樣，相似的編碼所對(duì)應(yīng)的軌跡，同時(shí)在時(shí)間和空間上具有相似性。

3實(shí)驗(yàn)結(jié)果

3.1實(shí)驗(yàn)數(shù)據(jù)和評(píng)估指標(biāo)

本文在與亞洲某機(jī)場(chǎng)的合作研究中，獲得了一個(gè)真實(shí)的乘客機(jī)場(chǎng)軌跡數(shù)據(jù)集。該數(shù)據(jù)集包含14 605個(gè)軌跡，約有719 507個(gè)位置點(diǎn)，每個(gè)軌跡包含20至120個(gè)點(diǎn)。本文使用此數(shù)據(jù)集來(lái)訓(xùn)練模型，挖掘一起行走的乘客。

將Mean-Attn與簡(jiǎn)單的LSTM自編碼器（LSTM-AE）、兩個(gè)經(jīng)典的模式挖掘算法Convoy和Swarm，以及兩個(gè)機(jī)器學(xué)習(xí)模型T2Vec（Trajectory to Vector）和BFEA（Behavior Feature ExtractionAlgorithm）進(jìn)行比較。對(duì)于基于模式挖掘的兩個(gè)算法Convoy和Swarm，本文比較它們抽取的簇?cái)?shù)（旅行同伴的組數(shù)），且先學(xué)習(xí)軌跡表征，然后對(duì)表征聚類得到的簇?cái)?shù)進(jìn)行比較。為了遵循算法的要求，本文在數(shù)據(jù)集中進(jìn)行線性插值，針對(duì)每條軌跡，每10s為一個(gè)時(shí)間步，在軌跡點(diǎn)缺失時(shí)生成一個(gè)插值點(diǎn)。對(duì)于T2Vec和BFEA，修改模型的輸入，將位置編碼添加到其原始嵌入中，以便和本文的模型進(jìn)行公平比較。本文使用DBSCAN對(duì)學(xué)習(xí)到的編碼進(jìn)行聚類，并比較各個(gè)算法的聚類性能。

在評(píng)估軌跡表征聚類效果時(shí)，本文采用Davis-Bouldin Index、Silhouette Coefficient以及WeightedAverage Entropy（加權(quán)平均熵）這3個(gè)指標(biāo)來(lái)衡量。Davis-Bouldin Index首先根據(jù)每個(gè)簇的直徑找到最相似的簇，然后計(jì)算這些簇的平均相似度，因此較小的值通常表示著較好的聚類性能。SilhouetteCoefficient是衡量每個(gè)對(duì)象與相同簇內(nèi)的其他對(duì)象相比于簇外的對(duì)象是否更相似的一種度量;較高的Silhouette Coefficient值表示每個(gè)對(duì)象與相同簇內(nèi)的對(duì)象相似度較高，而與簇外對(duì)象的相似度較低，因此表明聚類效果更好。Davis-Bouldin Index和Silhouette Coefficient是進(jìn)行聚類評(píng)估的內(nèi)部指標(biāo)。除此之外，本文還計(jì)算所有簇的加權(quán)平均熵并將其作為外部指標(biāo)。簇的熵是聚類對(duì)象的最大似然估計(jì)，當(dāng)簇中的對(duì)象的類別較為一致時(shí)，簇的熵較小。加權(quán)平均熵是所有簇的熵的加權(quán)總和，其中每個(gè)簇的權(quán)重是簇的大小除以對(duì)象總數(shù)。更好的軌跡表征應(yīng)使得簇的加權(quán)平均熵較小。盡管無(wú)法得到軌跡的類別標(biāo)簽，但如果幾名乘客是旅行同伴，那么他們更有可能乘坐同一航班?；诖思僭O(shè)，本文將每個(gè)軌跡的最后位置點(diǎn)，與10 min后的第一個(gè)航班相關(guān)聯(lián)，并將該航班用作進(jìn)行熵計(jì)算的軌跡標(biāo)簽。對(duì)于所有這些實(shí)驗(yàn)，本文丟棄大小為1的簇，即被視為單獨(dú)移動(dòng)的軌跡。

3.2實(shí)驗(yàn)參數(shù)設(shè)定和訓(xùn)練細(xì)節(jié)

MBR的大小和小批次大小設(shè)定：本文將MBR的大小和小批次的大小（輸入模型時(shí)軌跡與其鄰居軌跡數(shù)目的總和）分別設(shè)定為64和8，MBR的大小即使用STR算法對(duì)軌跡進(jìn)行粗略分組時(shí)的組的大小。

網(wǎng)格單元的大小設(shè)定：將整個(gè)機(jī)場(chǎng)空間劃分為大小相同的網(wǎng)格單元，每個(gè)單元的邊長(zhǎng)為5 m，共得到15 354個(gè)單元。

訓(xùn)練細(xì)節(jié)：本文使用Adam算法對(duì)模型進(jìn)行優(yōu)化，學(xué)習(xí)率固定為0.001，權(quán)重衰減率為0.000 01.當(dāng)軌跡重建損失和表征相似性損失都收斂時(shí)，訓(xùn)練即可停止。本文觀察到所有的模型都會(huì)在20輪后收斂。

3.3主要結(jié)果

本文使用DBSCAN對(duì)4個(gè)深度學(xué)習(xí)模型學(xué)到的軌跡表征進(jìn)行聚類。其中，距離參數(shù)Epsilon從0到0.2進(jìn)行變化，以0.000 1的增量遞增;然后針對(duì)每個(gè)Epsilon進(jìn)行聚類，并計(jì)算前述3種指標(biāo)的結(jié)果。結(jié)果分別如圖2a）、圖2b）和圖2c）所示。

在圖2a）和圖2b）中可觀察到，Mean-Attn在Epsilon變化時(shí)，基本上都具有較小的Davis-BouldinIndex值和較大的Silhouette Coefficient值，這表明Mean-Attn的性能在以內(nèi)部標(biāo)準(zhǔn)來(lái)評(píng)估時(shí)，在大部分情況下都優(yōu)于LSTM-AE，T2Vec和BFEA。在圖2a）中，當(dāng)Epsilon大于0.16時(shí)，使用LSTM-AE訓(xùn)練的所有模型表征都被聚類到同一個(gè)簇中，因此不再有相應(yīng)的指標(biāo)值。當(dāng)Epsilon大于0.04時(shí)，BFEA同理。T2Vec在Epsilon較小的時(shí)候表現(xiàn)不如Mean-Attn。但是當(dāng)Epsilon大于0.15時(shí)，Davis-Bouldin Index值比Mean-Attn小，這是因?yàn)榻?jīng)過(guò)Mean-Attn聚類得到的同行軌跡之間的表征相似度較大，更易被分到一個(gè)簇中;而當(dāng)Epsilon變大時(shí)，簇內(nèi)則更易引入不相似的噪聲軌跡。在圖2b）中，Mean-Attn的表現(xiàn)穩(wěn)定地優(yōu)于其他3種模型。在圖2c）中，還可觀察到，對(duì)于變化的Epsilon，Mean-Attn生成的簇的加權(quán)平均熵始終要小于LSTM-AE、T2Vec和BFEA生成的簇。這意味著Mean-Attn產(chǎn)生的簇內(nèi)部，乘客對(duì)應(yīng)的航班標(biāo)簽較為一致，也即意味著相較于其他模型，Mean-Attn產(chǎn)生的同一個(gè)簇中的軌跡更有可能成為旅行同伴。

此外，本文還將LSTM-AE和Mean-Attn這兩個(gè)模型找到的至少具有2條軌跡的簇的數(shù)量，與Convoy和Swarm提取出來(lái)的簇的數(shù)量進(jìn)行了比較，結(jié)果如表1所示。對(duì)于Convoy和Swarm，本文將k設(shè)置為18（至少3 min），將m設(shè)置為2（至少有2人同行），然后將e設(shè)置為3 m和5 m。例如，表1中的第一行表示一個(gè)Convoy必須要在至少18個(gè)連續(xù)的時(shí)間點(diǎn)中，包含至少2條軌跡，他們的軌跡點(diǎn)始終是3 m密度連通的。對(duì)于LSTM-AE和Mean-Attn這兩個(gè)模型，僅顯示當(dāng)它們發(fā)現(xiàn)最大數(shù)量的簇時(shí)的結(jié)果。可以觀察到，即使放寬變量設(shè)定的限制，Convoy和Swarm仍生成許多只包含單個(gè)軌跡的簇。相比之下，本文提出的模型可以將更多的軌跡進(jìn)行聚類，即發(fā)現(xiàn)更多的旅行同伴。

3.4敏感性分析

本節(jié)通過(guò)更改Mean-Attn模型中STR算法的MBR容量和小批次大小這兩個(gè)超參數(shù)來(lái)執(zhí)行敏感度分析。

首先，將輸入模型的小批次大小固定為8，然后將STR算法的MBR容量（capacity）設(shè)為（32，64，96）。圖3a）、圖3b）和圖3c）顯示了結(jié)果。從圖3中可以觀察到，盡管存在細(xì)微的差異，但是當(dāng)MBR容量變化時(shí)，3個(gè)測(cè)量都會(huì)產(chǎn)生較為相似的結(jié)果。這表明，Mean-Attn對(duì)MBR容量的選擇具有一定的魯棒性。

然后，將MBR容量固定為64，并將小批次大?。ㄓ密壽E數(shù)量（Trajectories）表示）設(shè)為（4，8，16）。圖4a）、圖4b）和圖4c）顯示了結(jié)果。從圖4中可以觀察到，當(dāng)小批次大小等于16時(shí)，3個(gè)指標(biāo)的表現(xiàn)均為最差。本文認(rèn)為這是合理的，因?yàn)楫?dāng)小批次大小較大時(shí)，利用Mean-Attn訓(xùn)練的編碼，更有可能從不太相似的軌跡中學(xué)習(xí)到特征。因此，平均編碼與各個(gè)軌跡表征的偏差也會(huì)更大，這使得表征相似度損失收斂變得更加困難。根據(jù)這一結(jié)果，本文認(rèn)為Mean-Attn更偏向于使用較小的批次進(jìn)行訓(xùn)練。

3.5位置編碼的效果

本文利用位置編碼技術(shù)來(lái)捕獲軌跡點(diǎn)的時(shí)間信息。為了展示這種想法的有效性，本文從軌跡點(diǎn)的嵌入表征中刪除位置編碼，然后再次訓(xùn)練Mean-Attn模型。隨后，計(jì)算相應(yīng)的Davis-Bouldin Index、Silhouette Coefficient和加權(quán)平均熵這3個(gè)指標(biāo)，并和原模型的指標(biāo)進(jìn)行對(duì)比。結(jié)果如圖5a）、圖5b）和圖5c1所示。

從圖5中可以觀察到，使用了位置編碼的模型比沒(méi)有使用位置編碼的模型，在絕大多數(shù)情況下都表現(xiàn)出了更好的聚類性能。這是因?yàn)闆](méi)有位置編碼的Mean-Attn只能學(xué)習(xí)軌跡之間的空間相似性。在這種情況下，形狀相似但在時(shí)間維度上完全偏離的軌跡，仍可能生成相似的表征，從而被誤認(rèn)為是旅行同伴;而包含了位置編碼的Mean-Attn能夠同時(shí)學(xué)習(xí)軌跡之間的時(shí)間和空間相似性，從而能被用于更精確地找到旅行同伴。

3.6軌跡可視化

為了展示旅行同伴挖掘的直觀效果，本文選擇數(shù)據(jù)集中某一天從凌晨00：00到凌晨02：00這2 h內(nèi)的軌跡。這段時(shí)間內(nèi)軌跡相對(duì)較少，能夠更清晰地展示結(jié)果。本文分別對(duì)LSTM-AE和Mean-Attn生成的軌跡表征進(jìn)行了DBSCAN聚類，對(duì)同一個(gè)簇中的軌跡使用相同的顏色來(lái)表示。對(duì)當(dāng)DBSCAN發(fā)現(xiàn)最大數(shù)目的簇時(shí)（排除單個(gè)軌跡）的結(jié)果進(jìn)行可視化，結(jié)果如圖6a）和圖6b）所示。圖6中，x和y代表空間維度，z是時(shí)間維度。軌跡通常從右下位置移動(dòng)到左上位置，代表從航站樓入口移動(dòng)到登機(jī)口。

從圖6中可以觀察到，Mean-Attn可以發(fā)現(xiàn)5組旅行同伴，而LSTM-AE只能發(fā)現(xiàn)3組。在藍(lán)色組中，Mean-Attn發(fā)現(xiàn)了3條軌跡，而LSTM-AE僅發(fā)現(xiàn)了2條軌跡，從圖中可見(jiàn)，LSTM-AE沒(méi)有發(fā)現(xiàn)最初偏離其他兩個(gè)軌跡的那條軌跡。在LSTM-AE發(fā)現(xiàn)的粉紅色組中，這4個(gè)軌跡其實(shí)在大部分時(shí)間里都偏離了，只是最后移到了同一個(gè)登機(jī)口。而Mean-Attn可以將它們分為2個(gè)簇（粉紅色和綠色），每個(gè)簇中的2條軌跡看起來(lái)更像是旅行同伴。最后，Mean-Attn會(huì)識(shí)別LSTM-AE未發(fā)現(xiàn)的2個(gè)黃色旅行同伴，即使他們?cè)诖蠖鄶?shù)情況下的距離都非常接近。由此可見(jiàn)，Mean-Attn可以比LSTM-AE學(xué)到更適合用來(lái)挖掘旅行同伴的軌跡表征。

4結(jié)論

本文提出了一個(gè)無(wú)監(jiān)督的深度模型Mean-Attn，用于發(fā)現(xiàn)軌跡數(shù)據(jù)中的旅行同伴。首先采用低維稠密表征技術(shù)和位置編碼技術(shù)對(duì)每條軌跡進(jìn)行嵌入表示。利用這兩種技術(shù)，可以同時(shí)捕獲每條軌跡的空間和時(shí)間信息。然后，使用Sort-Tile-Recursive算法對(duì)原始軌跡進(jìn)行分組，并從每組中單獨(dú)抽取小批次輸?shù)侥Ｐ椭校怨膭?lì)它們向鄰近軌跡學(xué)習(xí)。在模型的具體結(jié)構(gòu)中，使用了共享參數(shù)的雙重自編碼器，分別從軌跡重構(gòu)和小批次中軌跡之間的相似性兩方面來(lái)約束表征的訓(xùn)練，同時(shí)使用了全局注意力機(jī)制對(duì)LSTM的所有隱層進(jìn)行聚合，以獲取最終的軌跡表征。實(shí)驗(yàn)結(jié)果表明，相比LSTM-AE、T2Vec和BFEA，本文提出的Mean-Attn學(xué)習(xí)到的軌跡表征，在尋找旅行同伴的應(yīng)用上有更好的表現(xiàn)。在未來(lái)的工作中，一方面將尋找更多的真實(shí)數(shù)據(jù)集，進(jìn)一步驗(yàn)證模型的效果;另一方面，將采用其他架構(gòu)，如自注意力機(jī)制等，來(lái)改進(jìn)自編碼器的編碼效果，從而改進(jìn)旅行同伴的挖掘效率。