周開來 等

孟慶磊? 馮鑫偉

摘? 要：軌跡數(shù)據(jù)廣泛應(yīng)用于智能交通、自然保護(hù)、疫情防控等領(lǐng)域。軌跡相似性度量是軌跡查詢分析中最復(fù)雜和耗時(shí)的操作之一，是軌跡數(shù)據(jù)管理領(lǐng)域的研究基礎(chǔ)。文章首先將軌跡相似性度量方法按對(duì)時(shí)間信息是否敏感劃分為時(shí)間敏感型和非時(shí)間敏感型，同時(shí)介紹了基于語義和深度學(xué)習(xí)的新型軌跡相似性度量方法；然后對(duì)每類度量方法進(jìn)行了綜合對(duì)比分析，并給出了各自的優(yōu)缺點(diǎn)；最后對(duì)本領(lǐng)域未來的研究趨勢(shì)進(jìn)行了展望。

關(guān)鍵詞：軌跡數(shù)據(jù)；時(shí)空軌跡；軌跡相似性；相似性度量

中圖分類號(hào)：TP301? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2023）23-0099-07

New Progress of Research on Trajectory Similarity Measurement Methods

ZHOU Kailai， MENG Qinglei， FENG Xinwei

（Software College， Zhengzhou University of Light Industry， Zhengzhou? 450001， China）

Abstract： Trajectory data is widely used in fields such as intelligent transportation， natural conservation， and epidemic prevention and control. Trajectory similarity measurement is one of the most complex and time-consuming operations in trajectory query analysis， and is the research foundation in the field of trajectory data management. This paper first divides trajectory similarity measurement methods into time sensitive and non time sensitive based on whether they are sensitive to time information， and introduces a new trajectory similarity measurement method based on semantics and deep learning; then， a comprehensive comparative analysis is conducted on each type of measurement method， and their respective advantages and disadvantages are given; finally， prospects for future research trends in this field are presented.

Keywords： trajectory data; spatial-temporal trajectory; trajectory similarity; similarity measurement

0? 引? 言

近年來，隨著位置傳感器、支持定位服務(wù)的移動(dòng)設(shè)備和無線通信等技術(shù)的快速進(jìn)步和廣泛應(yīng)用，由人員、動(dòng)物或交通工具等移動(dòng)對(duì)象所產(chǎn)生的運(yùn)動(dòng)軌跡正呈指數(shù)級(jí)增長(zhǎng)。軌跡數(shù)據(jù)在各個(gè)領(lǐng)域具有廣泛應(yīng)用，如：在疫情防控方面，通過分析感染人員的出行軌跡來實(shí)現(xiàn)對(duì)傳染病的控制和預(yù)防[1]；在交通管理方面，人們通過獲取城市中車輛的軌跡數(shù)據(jù)來更好的管理城市交通[2]；在自然保護(hù)方面，通過分析珍稀野生動(dòng)物的軌跡來更好的觀察它們的行為并制定相關(guān)的保護(hù)策略[3]，通過對(duì)一些自然現(xiàn)象的軌跡（如颶風(fēng)）分析來更好發(fā)現(xiàn)的自然規(guī)律，幫助人們避開一些自然災(zāi)害[4]等。

盡管有廣泛的應(yīng)用領(lǐng)域，但是軌跡相似性度量是各種應(yīng)用中的一個(gè)基本問題[5]，它在軌跡檢索、分類、挖掘等軌跡分析過程中起著關(guān)鍵性的作用[6]。

迄今為止，有很多對(duì)于軌跡相似性度量進(jìn)行比較和分析的綜述性文獻(xiàn)，其中比較有代表性包括Toohey[7]及Magdy[8]等人所作的調(diào)研，最新的研究由Cleasby等人[9]和Tao等人[10]所提出，但是這些研究?jī)H考慮空間維度的軌跡相似性度量方法，對(duì)于近年來新出現(xiàn)的時(shí)間敏感型以及一些新型的軌跡相似性度量方法未能深入分析和總結(jié)。為使本領(lǐng)域的學(xué)者更全面的了解軌跡相似性度量方法的研究現(xiàn)狀，本文對(duì)軌跡相似性度量進(jìn)行了全面性的總結(jié)，并著重分析了時(shí)間敏感型的軌跡相似性度量方法。

1? 軌跡相似性度量概述

與為了方便描述以下介紹的各種相似性度量方法，本節(jié)就有關(guān)概念進(jìn)行闡述。

1.1? 基本概念

軌跡本質(zhì)上應(yīng)該是移動(dòng)對(duì)象一個(gè)連續(xù)移動(dòng)的記錄，但是由于數(shù)據(jù)采樣和存儲(chǔ)的局限性，在實(shí)踐中能使用的軌跡數(shù)據(jù)只能以離散形式來獲取和表示。鑒于此給出軌跡的定義，即軌跡T是按照時(shí)間戳排序的一系列軌跡采樣點(diǎn)，表示為T = （ p1，p2，…，pn）。實(shí)際上軌跡采樣點(diǎn)應(yīng)該在多維空間中表示，但是為了方便且不失通用性的情況下，一般都在二維空間中進(jìn)行討論，所以在軌跡T中觀察到的第i個(gè)采樣點(diǎn)pi通?？梢员硎緸椋ń?jīng)度，緯度，時(shí)間戳），即pi = （ pi.x，pi.y，pi.t）。

1.2? 軌跡相似性度量的分類

軌跡相似性度量分類的方式有多種。周星星等人[11]則根據(jù)軌跡相似性度量方法是基于軌跡點(diǎn)還是基于軌跡段來進(jìn)行分類；潘曉等人[12]將軌跡相似性度量方法分為了無時(shí)間約束，基于時(shí)間序列和基于編輯距離三種類型；Su等人[5]提到了通過相似性度量距離函數(shù)的采用方式，分為L(zhǎng)p-norm和編輯距離兩種類型。

本文在現(xiàn)有分類方法的基礎(chǔ)上，將軌跡相似性度量方法按照對(duì)時(shí)間是否敏感分為兩類，也就是是否僅考慮了空間信息，還是同時(shí)考慮了空間信息和時(shí)間信息，前者稱為非時(shí)間敏感型軌跡相似性度量，后者則稱為時(shí)間敏感型軌跡相似性度量，除此之外，現(xiàn)有研究中還提出了一些基于語義和深度學(xué)習(xí)的新型軌跡相似性度量方法。

1.3? 軌跡相似性度量的特征

隨著軌跡數(shù)據(jù)的不斷增長(zhǎng)以及對(duì)其研究的不斷深入，軌跡相似性度量的設(shè)計(jì)需要考慮其一些獨(dú)有的特征，總結(jié)如下：

1）時(shí)間屬性。在本文中，時(shí)間序列的軌跡相似性度量方法（如DTW等）將被看作未考慮時(shí)間信息的度量方法，因?yàn)闀r(shí)間序列在實(shí)踐中所有的時(shí)間序列數(shù)據(jù)都有一樣的時(shí)間戳。對(duì)于軌跡來說，不同軌跡的長(zhǎng)度和時(shí)間戳并不相同，所以時(shí)間戳并不能像時(shí)間序列數(shù)據(jù)一樣看作未考慮時(shí)間信息的度量方法，例如在考慮兩個(gè)移動(dòng)對(duì)象A和B時(shí)，假設(shè)它們擁有相同的位置信息的集合，但是每個(gè)位置的時(shí)間戳并不相同，當(dāng)不考慮時(shí)間信息時(shí)，這兩條軌跡就是相同的。

2）度量與非度量。一般來說，軌跡相似性度量與距離的函數(shù)有關(guān)，如果在軌跡集中的所有x、y、z軌跡距離函數(shù)滿足這些條件：非負(fù)性：dist（x，y）≥0；對(duì)稱性：dist（x，y） = dist（ y，x）；自反性：dist（x，y） = 0 ? x = y；三角不等式：dist（x，y） + dist（y，z）≥dist（x，z）。則認(rèn)為其是度量的。度量與非度量的屬性會(huì)在軌跡查詢中的索引結(jié)構(gòu)和軌跡聚類等軌跡分析中產(chǎn)生一定影響。

3）連續(xù)度量與離散度量。如果只考慮在軌跡采樣點(diǎn)上計(jì)算距離值，則稱為離散度量，離散度量只使用特定時(shí)間的位置，忽略了采樣點(diǎn)之間的移動(dòng)；如果同時(shí)考慮采樣點(diǎn)上和采樣點(diǎn)之間的移動(dòng)來計(jì)算距離值，則稱為連續(xù)度量，連續(xù)測(cè)量一般采取在一組離散時(shí)間內(nèi)測(cè)量的位置之間進(jìn)行插值的方法。

4）全局匹配與局部匹配。在離散度量中，采樣點(diǎn)的匹配策略顯得尤為重要，全局匹配需要R和S兩條軌跡每個(gè)采樣點(diǎn)都有相對(duì)應(yīng)的匹配點(diǎn)，如果有些采樣點(diǎn)有多余的匹配點(diǎn)，這時(shí)就要進(jìn)行移動(dòng)或者壓縮和拉伸軌跡來尋找最適合的匹配點(diǎn)。對(duì)于局部匹配并不要求所有的采樣點(diǎn)都一一對(duì)應(yīng)。

5）穩(wěn)健性。由于軌跡數(shù)據(jù)是在各種復(fù)雜的環(huán)境中產(chǎn)生的，再加上各種軌跡數(shù)據(jù)采集的傳感器和GPS等采集方式會(huì)存在一定的精度限制，同時(shí)采集到的軌跡點(diǎn)可能并不是移動(dòng)對(duì)象的真實(shí)位置，可能存在一些偏差，甚至可能采集到的是一個(gè)完全錯(cuò)誤的位置，這使得軌跡數(shù)據(jù)的質(zhì)量很低，導(dǎo)致采樣點(diǎn)的增多或減少，產(chǎn)生噪聲點(diǎn)，以及點(diǎn)偏移等問題，會(huì)對(duì)軌跡相似性度量方法的穩(wěn)健性產(chǎn)生很大影響。

2? 非時(shí)間敏感型軌跡相似性度量方法

非時(shí)間敏感型軌跡相似性度量方法不考慮時(shí)間信息，僅考慮兩條軌跡之間的空間信息，本節(jié)對(duì)每種方法進(jìn)行簡(jiǎn)要概述并總結(jié)了其優(yōu)缺點(diǎn)以及滿足的特征，常見的方法有以下9種：

1）歐幾里得距離（ED）。歐氏距離是一種最常見且最基礎(chǔ)的軌跡相似性度量方法，開始被用于時(shí)間序列距離度量，后逐漸被用于測(cè)量軌跡之間的相似性[13]，兩條軌跡之間的歐式距離先計(jì)算同一時(shí)間對(duì)應(yīng)點(diǎn)之間的距離，然后對(duì)點(diǎn)之間的歐式距離進(jìn)行綜合考慮，如求和、求平均值等。

2）動(dòng)態(tài)時(shí)間規(guī)整（DTW）。動(dòng)態(tài)時(shí)間規(guī)整是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃的算法，開始用于時(shí)間序列中處理局部時(shí)間偏移，近些年的研究中被用來度量軌跡之間的距離[14]，算法可以使得軌跡中的點(diǎn)進(jìn)行多次復(fù)制，用這種方法來讓兩條進(jìn)行比較的軌跡長(zhǎng)度相等，最后軌跡之間的相似值用兩條軌跡之間的最小距離來表示。

3）最長(zhǎng)公共子序列（LCSS）。通過計(jì)算兩條軌跡之間最長(zhǎng)公共子序列的大小，然后將其轉(zhuǎn)為軌跡之間的距離，以此來確定兩條軌跡間的相似程度[15]。

4）真實(shí)序列編輯距離（EDR）。EDR開始用于判斷兩個(gè)字符串之間的相似度，現(xiàn)在可以用于度量?jī)蓷l軌跡之間的相似性，EDR本質(zhì)上是將兩條軌跡中的其中一條軌跡進(jìn)行編輯（插入、替換、刪除）操作變成另外一條的過程，兩條軌跡之間所需要進(jìn)行編輯的次數(shù)越少，兩條軌跡之間的相似性就越高[16]。

5）實(shí)際懲罰編輯距離（ERP）。ERP是對(duì)EDR的擴(kuò)展和延伸的一種相似性度量方法，同時(shí)使用L1范數(shù)作為距離度量。相較于歐式距離無法處理局部時(shí)間偏移，DTW、LCSS、EDR不滿足三角不等式，不滿足度量函數(shù)的條件，ERP既可以處理局部時(shí)間偏移，又是度量的[17]。

6）豪斯多夫距離（Hausdorff）。Hausdorff是一個(gè)用于表示兩個(gè)點(diǎn)集合之間的相似性度量的方法，目前也被用在軌跡相似性距離度量中[18]，Hausdorff表示的是兩條軌跡最近點(diǎn)距離的最大值。

7）多線位置距離（LIP）。多線位置距離的思想是計(jì)算兩個(gè)軌跡之間形成的形狀的面積[19]，軌跡可以映射到二維空間中，如圖1所示，計(jì)算面積的同時(shí)需要考慮每個(gè)對(duì)應(yīng)軌跡段圍成的多邊形區(qū)域的所占權(quán)重，當(dāng)兩條軌跡圍成的多邊形區(qū)域的周長(zhǎng)在總長(zhǎng)中越長(zhǎng)時(shí)，即權(quán)重越大。多線位置距離越小，說明軌跡間的縫隙越小，兩條軌跡之間的相似性也就越高。

8）單向距離（OWD）。單向距離[20]中時(shí)間和速度以及方向等屬性并不重要，只關(guān)注于軌跡的空間形狀，它指的是兩條軌跡之間其中一條軌跡上的所有采樣點(diǎn)到另一條軌跡上的平均最小距離，由此看出單向距離OWD并不是對(duì)稱的。

9）投影編輯距離（EDwP）。EDwP通過動(dòng)態(tài)插值的方法來匹配不一致和可變采樣率的軌跡，使用兩條軌跡間的編輯距離來表示兩條軌跡間的距離，主要包括替換和插入兩種編輯操作[21]。主要思想是計(jì)算能夠使得兩條軌跡相同的最小編輯序列，編輯通過計(jì)算采樣點(diǎn)從一個(gè)軌跡到另一個(gè)軌跡的投影代價(jià)來匹配它們。

對(duì)于非時(shí)間敏感型相似性度量方法，每種方法的優(yōu)缺點(diǎn)如表1所示，每種方法所滿足的特征，包括是否有參數(shù)，是否連續(xù)，是否滿足三角不等式，是否對(duì)噪聲敏感，每個(gè)點(diǎn)是否要求匹配，時(shí)間復(fù)雜度是多少。如表2所示。

3? 時(shí)間敏感型軌跡相似性度量方法

本節(jié)對(duì)一些常見的時(shí)間敏感型軌跡相似性度量方法進(jìn)行簡(jiǎn)要概述并總結(jié)了其優(yōu)缺點(diǎn)以及滿足的特征，此類方法同時(shí)考慮了時(shí)間信息和空間信息，時(shí)間信息對(duì)于軌跡相似性度量方法的重要性如圖2所示，圖2中有三條時(shí)空軌跡T1、T2、T3，其在二維平面上的投影分別是T1'、T2'、T3'，和另外兩條軌跡相比，若只考慮空間，則T2與T1更相似。如果同時(shí)考慮空間和時(shí)間，T2則與T3更為相似。

常見的方法有以下10種：

1）時(shí)空歐式距離（STED）。STED主要描述移動(dòng)對(duì)象在給定時(shí)間段內(nèi)兩條軌跡之間的歐式距離的均值，通過給定時(shí)間間隔內(nèi)移動(dòng)對(duì)象之間距離的積分來計(jì)算，即對(duì)移動(dòng)對(duì)象每個(gè)時(shí)刻的位置進(jìn)行比較來獲得距離值的集合并累加求和，這排除了進(jìn)行軌跡對(duì)齊和子序列匹配的操作[22]。

2）時(shí)空最長(zhǎng)公共子序列（STLCSS）。STLCSS是對(duì)LCSS進(jìn)行了擴(kuò)展的一個(gè)考慮時(shí)間信息的軌跡相似性度量方法[15]，它通過設(shè)定時(shí)間和空間上的閾值來對(duì)兩條軌跡的相似性進(jìn)行判斷。

3）時(shí)空多線位置距離（STLIP）。LIP不考慮時(shí)間信息，因?yàn)樗鼘⒁苿?dòng)對(duì)象的投影與笛卡爾平面進(jìn)行了比較，STLIP則是對(duì)LIP擴(kuò)展后的一種考慮了時(shí)間信息的局部多線段位置度量方法[17]，首先找出兩條軌跡的公共時(shí)間時(shí)域，根據(jù)此再將其投影到空間平面進(jìn)行比較。

4）時(shí)空豪斯多夫距離（STHausdorff）。STHausdorff是對(duì)Hausdorff進(jìn)行擴(kuò)展的一種基于時(shí)間約束的時(shí)空軌跡相似性度量[23]，它使用滑動(dòng)窗口來找出兩條目標(biāo)軌跡中所有相似的子軌跡，再根據(jù)所有相似子軌跡的長(zhǎng)度之和與目標(biāo)軌跡的總軌跡長(zhǎng)度的比值來比較兩條軌跡之間的相似性。為了解決時(shí)空軌跡的有序性和相關(guān)性，采用了一對(duì)三的比較方式。

5）軌跡間隔距離估計(jì)（TIDE）。TIDE是一種軌跡間隔距離的軌跡度量方法[24]，它解決了STLCSS和STLIP會(huì)由于異步采樣和不同采樣率造成的不確定性問題，其認(rèn)定如果可以從一條采樣率較高的軌跡中導(dǎo)出兩條軌跡，則認(rèn)為這兩條軌跡非常相似。

6）加權(quán)幾何平均值（WGM）。WGM使用逐點(diǎn)距離的算術(shù)平均值（例如原點(diǎn)到原點(diǎn)，終點(diǎn)到終點(diǎn)）作為相似性度量，每個(gè)對(duì)應(yīng)點(diǎn)之間的距離通過歐式距離的加權(quán)平均值和時(shí)間相似性實(shí)現(xiàn)[25]。位置和時(shí)間特征都縮放為[0，1]，使用這種方法的目的是幾何平均值可以根據(jù)時(shí)間相似性調(diào)整兩點(diǎn)的空間分量，算術(shù)平均值根據(jù)所有點(diǎn)的相似性度量。

7）時(shí)間加權(quán)相似度（TWS）和空間加權(quán)相似度（SWS）。TWS和SWS可以用來測(cè)量具有不同定位精度，采樣頻率和長(zhǎng)度的時(shí)空軌跡的相似性[26]。其核心思想是，如果軌跡在更長(zhǎng)的時(shí)間和距離內(nèi)保持接近，它們會(huì)更相似。為了定義TWS和SWS，首先進(jìn)行分析點(diǎn)之間的相似性，然后根據(jù)軌跡持續(xù)時(shí)間或空間距離來定義軌跡相似性。

8）軌跡相似連接（TSJOIN）。TSJOIN將指數(shù)函數(shù)運(yùn)用到了軌跡相似性度量中，并且使用線性組合的方法組合空間和時(shí)間的相似性的時(shí)空軌跡相似性度量方法[27]。

9）同步匹配相似（MPS）。TSJOIN存在具有高空間相似性和低時(shí)間相似性的兩條軌跡與具有低空間相似性和高時(shí)間相似性的另外兩條軌跡具有相同的總體相似性的問題，MPS的提出是為了解決這種不匹配的問題，它能夠基于軌跡間匹配點(diǎn)對(duì)的時(shí)空距離有效度量軌跡之間的相似性[28]，因?yàn)橐粭l軌跡S可能只類似于軌跡R的一部分，反之亦然，所以計(jì)算軌跡R和S之間的相似性需要考慮屬于R和S各自的相似段。

10）時(shí)空相似度（STS）。STS是一種基于時(shí)空概率估計(jì)建立的時(shí)空相似性度量方法[29]，它解決了MPS在效果上依賴于參數(shù)的設(shè)置，參數(shù)設(shè)置較難確定，并且對(duì)于零星和異構(gòu)采樣也不夠靈活的問題，它將軌跡中的每個(gè)位置建模為網(wǎng)格上概率分布的可觀察結(jié)果，然后從自身軌跡估計(jì)對(duì)象位置的個(gè)性化時(shí)空概率分布來減少了對(duì)訓(xùn)練數(shù)據(jù)的需求，基于此來得到共定位概率，即估計(jì)軌跡之間在時(shí)間t同時(shí)位于網(wǎng)格上的概率，由此得出所有共定位概率的平均值作為時(shí)空相似性度量。

對(duì)于時(shí)間敏感型軌跡相似性度量方法，每種方法的優(yōu)缺點(diǎn)如表3所示。每種方法所滿足的特征，包括是否有參數(shù)，是否連續(xù)，是否對(duì)噪聲敏感，是否滿足三角不等式，時(shí)間復(fù)雜度是多少。如表4所示。

4? 新型軌跡相似性度量方法

4.1? 基于語義的軌跡相似性度量方法

由于地理信息數(shù)據(jù)和社交媒體數(shù)據(jù)的快速增加和使用，有些研究學(xué)者開始向軌跡數(shù)據(jù)中添加更多的信息，從而產(chǎn)生了語義軌跡的概念，語義軌跡是表示停留點(diǎn)和移動(dòng)點(diǎn)的序列，移動(dòng)點(diǎn)是停留點(diǎn)之間的軌跡點(diǎn)，停留點(diǎn)是軌跡中最重要的部分，表示移動(dòng)對(duì)象在最短時(shí)間內(nèi)訪問過的位置[30]。由于語義軌跡概念的提出，研究學(xué)者們開始對(duì)于語義軌跡相似性度量進(jìn)行研究，MSTP[31]是首次被提出的一種考慮軌跡語義信息的相似性度量，即通過轉(zhuǎn)化后的兩條語義軌跡中的最長(zhǎng)公共子序列來定義兩條語義軌跡之間的相似性，但是它并沒有考慮空間和時(shí)間維度；Liu等人[32]基于地理特征和軌跡的語義屬性提出了一種新的軌跡相似性度量，首先通過考慮軌跡轉(zhuǎn)彎和時(shí)間約束將軌跡劃分為子軌跡，然后對(duì)子軌跡之間的地理相似性和語義相似性進(jìn)行定義，最后定義距離函數(shù)來對(duì)地理相似性和語義相似性進(jìn)行度量，但是這種方法沒有考慮時(shí)間維度；前面提到的方法不可擴(kuò)展到多個(gè)維度，或者可以擴(kuò)展但是僅僅在所有維度中存在一定的相似性才執(zhí)行匹配，MSM[33]是一種多維序列相似性度量，它通過考慮加權(quán)所有維度的相似性來克制對(duì)噪聲敏感度和最差維度相似性的普遍性等限制，它可以應(yīng)用于不同領(lǐng)域（例如語義軌跡），可以擴(kuò)展到多個(gè)維度，并且支持部分匹配；MSM等度量方法只考慮了停止，忽略了移動(dòng)SMSM[34]通過對(duì)MSM進(jìn)行擴(kuò)展提出了一種同時(shí)考慮停止和移動(dòng)的相似性度量方法，它克服了MSM不支持的停止順序，允許不同的移動(dòng)語義，并且使用權(quán)值為移動(dòng)，停止和屬性提供重要度等的局限性。還有一些其他的語義軌跡度量方法如考慮屬性之間語義關(guān)系的MUITAS[35]等。

4.2? 基于深度學(xué)習(xí)的軌跡相似性度量方法

隨著深度學(xué)習(xí)的迅速發(fā)展，研究學(xué)者們開始將深度學(xué)習(xí)方面的知識(shí)與軌跡相似性度量方面進(jìn)行結(jié)合，t2vec[36]是第一個(gè)計(jì)算軌跡相似性的基于深度學(xué)習(xí)的方法，此方法基于深度表示學(xué)習(xí)來推斷和表示軌跡的潛在路徑信息，首先提出了一個(gè)基于序列對(duì)序列的模型Seq2Seq來盡可能恢復(fù)真實(shí)軌跡的概率，然后設(shè)計(jì)了一個(gè)新的空間鄰近感知損失函數(shù)使模型學(xué)習(xí)相同路線生成軌跡的一致表示，此方法對(duì)于非均勻和低采樣率和噪聲采樣點(diǎn)具有魯棒性；NEUTRAJ[37]是一種加速現(xiàn)有軌跡相似性的計(jì)算的通用方法，例如Hausdorff、ERP、DTW等，NEUTRAJ從給定的數(shù)據(jù)庫中提取一些種子軌跡，然后使用其中成對(duì)的相似性作為指導(dǎo)，用一個(gè)度量學(xué)習(xí)框架近似相似性函數(shù)，它可以在線性時(shí)間內(nèi)快速計(jì)算給定軌跡的相似性，同時(shí)能夠與所有基于空間的軌跡索引方法協(xié)作來減少搜索空間；盡管NEUTARAJ可以達(dá)到可接受的精度，但是仍然很耗時(shí)，T3S[38]的提出一定程度上解決了這個(gè)問題，它是一種基于深度學(xué)習(xí)的軌跡相似性的計(jì)算模型，通過應(yīng)用注意力神經(jīng)網(wǎng)絡(luò)來捕捉軌跡的空間和結(jié)構(gòu)信息等各種特征，對(duì)于給定的相似性度量，它將每個(gè)軌跡嵌入到d維空間中的向量中來加速軌跡之間的相似性度量，同時(shí)可以通過訓(xùn)練調(diào)整參數(shù)處理任何軌跡相似性度量；At2vec[39]將軌跡的時(shí)空特征和活動(dòng)信息相結(jié)合，利用包含這三種語義信息的向量作為深度學(xué)習(xí)模型的輸入來獲得最終的軌跡表示，同時(shí)擴(kuò)展具有活動(dòng)信息的Seq2Seq模型，設(shè)計(jì)了一個(gè)新的損失函數(shù)來區(qū)分這三種信息，它對(duì)于低采樣率具有魯棒性，但是At2vec模型存在一定的局限性，首先沒有考慮相似性度量中三個(gè)軌跡特征的重要性，其次沒有突出訓(xùn)練過程中的關(guān)鍵點(diǎn)，最后，使用的RNN無法捕捉長(zhǎng)序列中的長(zhǎng)期依賴關(guān)系，為了解決這些局限性，Liu等人[40]用LSTM取代了RNN，提出了一種具有多級(jí)注意機(jī)制的新模型。此外還有一些減少了DTW的時(shí)間消耗的基于深度學(xué)習(xí)的相似性模型，如CTSM模型[41]等。

5? 結(jié)? 論

本文系統(tǒng)分析了軌跡相似性度量方法的最新研究進(jìn)展，同時(shí)對(duì)比分析了每類方法的優(yōu)缺點(diǎn)及其滿足的特征，旨在從全新角度為時(shí)空軌跡數(shù)據(jù)挖掘相關(guān)研究人員提供一定的幫助。盡管國(guó)內(nèi)外研究學(xué)者在此領(lǐng)域已經(jīng)取得了一些研究成果，但仍然存在著諸多挑戰(zhàn)，未來可能的研究方向可以從以下工作中展開：

1）軌跡數(shù)據(jù)收集和轉(zhuǎn)化效率。理論上軌跡連續(xù)的，但是現(xiàn)實(shí)情況下，由于軌跡采集和存儲(chǔ)的局限性以及各種不確定性，軌跡一般是不準(zhǔn)確的或不完整的。同時(shí)盡管現(xiàn)有研究采取了一些方法進(jìn)行重建原始軌跡，但是轉(zhuǎn)化效率并不理想，這對(duì)于軌跡相似性度量方法的準(zhǔn)確性有較大的影響，因此如何更精確的收集軌跡數(shù)據(jù)以及如何盡可能地將收集數(shù)據(jù)轉(zhuǎn)化為原始軌跡數(shù)據(jù)方面仍有待研究。

2）軌跡數(shù)據(jù)的實(shí)時(shí)處理和預(yù)測(cè)。軌跡數(shù)據(jù)分析大都采用的是歷史軌跡數(shù)據(jù)，但是在實(shí)際應(yīng)用中對(duì)于實(shí)時(shí)性的要求越來越高。在后續(xù)可以研究能夠滿足實(shí)時(shí)軌跡數(shù)據(jù)的相似性度量方法，這會(huì)使得軌跡數(shù)據(jù)分析效率更高并且預(yù)測(cè)結(jié)果更準(zhǔn)確。

3）軌跡數(shù)據(jù)的存儲(chǔ)和查詢。隨著軌跡數(shù)據(jù)量的指數(shù)級(jí)增長(zhǎng)，軌跡數(shù)據(jù)的存儲(chǔ)及查詢都難以滿足大規(guī)模軌跡數(shù)據(jù)的應(yīng)用需求。未來可以通過研究性能更優(yōu)異的軌跡數(shù)據(jù)壓縮算法，支持分布式處理且更通用的軌跡索引結(jié)構(gòu)等方面來不斷提高存儲(chǔ)和查詢的效率。

4）多源軌跡數(shù)據(jù)的融合。由于軌跡數(shù)據(jù)類型的不斷增加，軌跡數(shù)據(jù)涵蓋的信息除了時(shí)空信息之外還有社交信息、出行信息等，將這些信息融合在一起進(jìn)行軌跡數(shù)據(jù)的分析和挖掘?qū)?huì)更好地實(shí)現(xiàn)各種類型數(shù)據(jù)的價(jià)值，更好的體現(xiàn)多源時(shí)空軌跡數(shù)據(jù)融合后的全面性，所以如何將這些不同類型的軌跡數(shù)據(jù)進(jìn)行融合，以及融合后如何制定相應(yīng)的查詢，索引，相似性度量等方法是一個(gè)新的挑戰(zhàn)。

5）軌跡相似性度量方法的優(yōu)化研究?，F(xiàn)有的時(shí)空軌跡相似性度量方法大都存在閾值和權(quán)重值選取不合理的問題，一般都是在特定應(yīng)用場(chǎng)景下對(duì)閾值與權(quán)重值的主觀選取，這對(duì)于算法的精確度和效率有很大的影響，基于此未來研究可以通過機(jī)器學(xué)習(xí)等方法對(duì)不同應(yīng)用場(chǎng)景下的閾值和權(quán)重值進(jìn)行大量訓(xùn)練，使其更具通用性且符合規(guī)律；現(xiàn)有不確定性的軌跡相似性度量方法存在相似性分析數(shù)據(jù)準(zhǔn)備耗時(shí)的問題，未來可以在設(shè)計(jì)并行算法，復(fù)用計(jì)算結(jié)果等方面進(jìn)行研究來提高此類方法的效率；現(xiàn)有深度學(xué)習(xí)的軌跡相似性度量方法中考慮語義信息的方法較少并且提取語義信息的模型性能已無法滿足現(xiàn)有工作的要求，未來研究可以將更新的模型和深度學(xué)習(xí)技術(shù)應(yīng)用到軌跡相似性度量方法中，以此來提高相似性度量方法的精度和效率。

參考文獻(xiàn)：

[1] SCHLOSSER F，BROCKMANN D. Finding disease outbreak locations from human mobility data [J].EPJ Data Science，2021，10（1）：1-17.

[2] CAO S Q，WU L B，WU J，et al. A spatio-temporal sequence-to-sequence network for traffic flow prediction [J].Information Sciences，2022，610：185-203.

[3] MCLEAN D J，VOLPONI S M A. trajr： An R package for characterisation of animal trajectories [J].Ethology，2018，124（6）：440-448.

[4] BOSE R，PINTAR A，SIMIU E. A real time prediction methodology for hurricane evolution using LSTM recurrent neural networks [J].Neural Computing and Applications，2022：34：17491-17505.

[5] SU H，LIU S C，ZHENG B，et al. A survey of trajectory distance measures and performance evaluation [J].The VLDB Journal，2020，29（1）：3-32.

[6] 高強(qiáng)，張鳳荔，王瑞錦，等.軌跡大數(shù)據(jù)：數(shù)據(jù)處理關(guān)鍵技術(shù)研究綜述 [J].軟件學(xué)報(bào)，2017，28（4）：959-992.

[7] TOOHEY K，DUCKHAM M. Trajectory similarity measures [J].Sigspatial Special，2015，7（1）：43-50.

[8] MAGDY N，SAKR M A，MOSTAFA T，et al. Review on trajectory similarity measures [C]//2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems （ICICIS）.Cairo：IEEE，2015：613-619.

[9] CLEASBY I R，WAKEFIELD E D，MORRISSEY B J，et al. Using time-series similarity measures to compare animal movement trajectories in ecology [J].Behavioral Ecology and Sociobiology，2019，73（11）：1-19.

[10] TAO Y G，BOTH A，SILVEIRA R I，et al. A comparative analysis of trajectory similarity measures [J].GIScience & Remote Sensing，2021，58（5）：643-669.

[11] 周星星，吉根林，張書亮.時(shí)空軌跡相似性度量方法綜述 [J].地理信息世界，2018，25（4）：11-18.

[12] 潘曉，馬昂，郭景峰，等.基于時(shí)間序列的軌跡數(shù)據(jù)相似性度量方法研究及應(yīng)用綜述 [J].燕山大學(xué)學(xué)報(bào)，2019，43（6）：531-545.

[13] AGRAWAL R，F(xiàn)ALOUTSOS C，SWAMI A. Efficient Similarity Search In Sequence Databases [C]//Proceedings of International Conference on Foundations of Data Organization and Algorithms. Berlin：Springer，1993：69-84.

[14] KEOGH E J，PAZZANI M J. Scaling up dynamic time warping for datamining applications [C]//Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining.New York：ACM Press，2000：285-289.

[15] VLACHOS M，KOLLIOS G，GUNOPULOS D. Discovering similar multidimensional trajectories [C]//Proceedings 18th International Conference on Data Engineering.San Jose：IEEE，2002：673-684.

[16] CHEN L，?zsu M T，ORIA V. Robust and fast similarity search for moving object trajectories [C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data.New York：Association for Computing Machinery，2005：491-502.

[17] CHEN L，NG R. On The Marriage of Lp-norms and Edit Distance [C]//Proceedings 2004 VLDB Conference.Toronto：Elsevier Inc，2004：792-803.

[18] LEE J G，HAN J，WHANG K Y.Trajectory clustering： a partition-and-group framework [C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data.New York：Association for Computing Machinery，2007：593-604.

[19] PELEKIS N，KOPANAKIS I，MARKETOS G，et al. Similarity Search in Trajectory Databases [C]//14th International Symposium on Temporal Representation and Reasoning （TIME'07）.Alicante：IEEE，2007：129-140.

[20] LIN B，SU J W. One Way Distance： For Shape Based Similarity Search of Moving Object Trajectories [J].GeoInformatica，2008，12（2）：117-142.

[21] RANU S，DEEPAK P，TELANG A D，et al. Indexing and matching trajectories under inconsistent sampling rates [C]//Proc of the 31st International Conference on Data Engineering.Piscataway：IEEE Press，2015：999-1010.

[22] NANNI M，PEDRESCHI D. Time-focused clustering of trajectories of moving objects [J].Journal of Intelligent Information Systems，2006，27（3）：267-289.

[23] 張曉濱，楊東山.基于時(shí)間約束的Hausdorff距離的時(shí)空軌跡相似度量 [J].計(jì)算機(jī)應(yīng)用研究，2017，34（7）：2077-2079.

[24] NADERIVESAL S，KULIK L，BAILEY J. An effective and versatile distance measure for spatiotemporal trajectories [J].Data Mining and Knowledge Discovery，2019，33（3）：577-606.

[25] KETABI R，ALIPOUR B，HELMY A. Playing with matches： vehicular mobility through analysis of trip similarity and matching [C]//Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York：Association for Computing Machinery，2018：544-547.

[26] GONG X R，HUANG Z，Wang Y l，et al. High-performance spatiotemporal trajectory matching across heterogeneous data sources [J].Future Generation Computer Systems，2020，105：148-161.

[27] SHANG S，CHEN L S，WEI Z W，et al. Parallel trajectory similarity joins in spatial networks [J].The VLDB Journal，2018，27（3）：395-420.

[28] ZHAO P，RAO W X，ZHANG C X，et al.SST： Synchronized Spatial-Temporal Trajectory Similarity Search [J].GeoInformatica，2020，24（4）：777-800.

[29] LI G Y，HUNG C C，LIU M Y，et al. Spatial-Temporal Similarity for Trajectories with Location Noise and Sporadic Sampling [C]//2021 IEEE 37th International Conference on Data Engineering （ICDE）.Chania：IEEE，2021：1224-1235.

[30] SPACCAPIETRA S，PARENT C，DAMIANI M L，et al. A conceptual view on trajectories [J].Data & Knowledge Engineering，2008，65（1）：126-146.

[31] YING J J C，LU E H C，LEE W C，et al. Mining user similarity from semantic trajectories [C]//Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks.New York：Association for Computing Machinery，2010：19-26.

[32] LIU H C，SCHNEIDER M. Similarity measurement of moving object trajectories [C]//Proceedings of the 3rd ACM SIGSPATIAL International Workshop on GeoStreaming.New York：Association for Computing Machinery，2012：19-22.

[33] FURTADO A S，KOPANAKI D，ALVARES L O，et al. Multidimensional Similarity Measuring for Semantic Trajectories [J].Transactions in GIS，2016，20（2）：280-298.

[34] LEHMANN A L，ALVARES L O，BOGORNY V. SMSM：a similarity measure for trajectory stops and moves [J].International Journal of Geographical Information Science，2019，33（9）：1847-1872.

[35] PETRY L M，F(xiàn)ERRERO C A，ALVARES L O，et al. Towards semantic‐aware multiple‐aspect trajectory similarity measuring [J].Transactions in GIS，2019，23（5）：960-975.

[36] LI X C，ZHAO K Q，CONG G，et al. Deep Representation Learning for Trajectory Similarity Computation [C]//2018 IEEE 34th International Conference on Data Engineering （ICDE）.Paris：IEEE，2018：617-628.

[37] YAO D，CONG G，ZHANG C，et al. Computing Trajectory Similarity in Linear Time： A Generic Seed-Guided Neural Metric Learning Approach [C]//2019 IEEE 35th International Conference on Data Engineering （ICDE）.Macao：IEEE，2019：1358-1369.

[38] YANG P L，WANG H C，ZHANG Y，et al. T3S： Effective Representation Learning for Trajectory Similarity Computation [C]//T3S： Effective Representation Learning for Trajectory Similarity Computation.Chania：IEEE，2021：2183-2188.

[39] ZHANG Y F，LIU A，LIU G F，et al. Deep Representation Learning of Activity Trajectory Similarity Computation [C]//2019 IEEE International Conference on Web Services （ICWS）.Milan：IEEE，2019：312-319.

[40] LIU A，ZHANG Y F，ZHANG X L，et al. Representation Learning With Multi-Level Attention for Activity Trajectory Similarity Computation [J].IEEE Transactions on Knowledge and Data Engineering，2022，34（5）：2387-2400.

[41] GUO J Y，ZHANG R B，HU J M，et al. Convolutional Trajectory Similarity Model： a faster method for trajectory similarity measurement [C]//2019 IEEE Intelligent Transportation Systems Conference （ITSC）.Auckland：IEEE，2019：3770-3775.

作者簡(jiǎn)介：周開來（1978—），男，漢族，湖北襄陽人，副教授，博士研究生，研究方向：數(shù)據(jù)庫和并行計(jì)算；孟慶磊（1998—），男，漢族，河南商丘人，碩士研究生在讀，研究方向：數(shù)據(jù)庫和大數(shù)據(jù)分析；馮鑫偉（1997—），男，漢族，河南鄭州人，碩士研究生在讀，研究方向：數(shù)據(jù)庫和大數(shù)據(jù)分析。