潘 曉，馬 昂，郭景峰，吳 雷,2，劉風陽

(1.石家莊鐵道大學 經(jīng)濟管理學院，石家莊 050043；2.燕山大學 信息科學與工程學院，河北 秦皇島 066004；3.天津師范大學 軟件學院，天津 300387)

0 引言

在無線通信技術(shù)、全球定位技術(shù)和智能移動終端高速發(fā)展的背景下，無時無刻不在產(chǎn)生時空數(shù)據(jù)。隨著位置信息的積累，形成了TB甚至PB規(guī)模的軌跡大數(shù)據(jù)。過去軌跡數(shù)據(jù)的構(gòu)成通常只包括時間和空間信息，可稱之為原始軌跡。如今，隨著社交媒體的普及和流行(例如，微博、微信等)地理位置與文本數(shù)據(jù)的融合變得越來越普遍，軌跡數(shù)據(jù)中蘊含的信息更加豐富。軌跡數(shù)據(jù)在交通、物流、應(yīng)急疏散管理、動物遷移等諸多方面有著重要的應(yīng)用。

軌跡相似性度量的研究是軌跡數(shù)據(jù)管理和挖掘的基礎(chǔ)，在軌跡計算的各個領(lǐng)域發(fā)揮著重要作用。例如，在交通管理領(lǐng)域，通過相似性度量可以發(fā)現(xiàn)軌跡集中區(qū)域，推斷交通擁堵情況，提早進行交通疏導[1-3]；在城市規(guī)劃領(lǐng)域，通過發(fā)現(xiàn)人類活動的相似性，可以推斷城市的功能模塊，為城市發(fā)展提供幫助[4]；在智能推薦領(lǐng)域，通過尋找滿足一定時空約束的相似性活動軌跡，可以為用戶進行推薦，提高用戶體驗和用戶黏度[5-8]；在智慧出行領(lǐng)域，通過借鑒用戶相似軌跡，可以合理規(guī)劃用戶出行時間，為智慧出行提供可能[9]；在環(huán)境空氣預測領(lǐng)域，通過與空氣的歷史軌跡數(shù)據(jù)進行比較，結(jié)合氣象、交通流等信息，可預測各區(qū)域地區(qū)的空氣質(zhì)量[10-11]，為環(huán)境保護提供助力。

1 軌跡大數(shù)據(jù)特點

據(jù)滴滴工作的最新數(shù)據(jù)，滴滴出行每天新產(chǎn)生的數(shù)據(jù)量為70 TB+，每天要處理的軌跡數(shù)據(jù)量可達4 500 TB。2017年交通運輸行業(yè)發(fā)展統(tǒng)計公報表明，至2017年末全國擁有公路營運汽車1 450.22萬輛。國家工信部稱截止至2018年5月我國移動電話用戶總數(shù)近15億?！犊纱┐髟O(shè)備研究報告》報告顯示，到2018年，成熟市場中每位消費者將擁有3件以上智能穿戴設(shè)備。海量的位置信息為軌跡數(shù)據(jù)的采集、存儲和計算帶來巨大挑戰(zhàn)。軌跡大數(shù)據(jù)除具有大數(shù)據(jù)傳統(tǒng)的“4V”特點外，還具有以下特點。

1) 高維異構(gòu)

軌跡數(shù)據(jù)中的位置本就屬于二維數(shù)據(jù)。由于位置采樣策略和頻率的不同，原始軌跡本身就具有數(shù)據(jù)異構(gòu)的特點。許多研究者開展了針對軌跡等長、位置對齊等相關(guān)工作的研究。最近，伴隨著移動社交網(wǎng)絡(luò)(如Facebook、Twitter、微博等)的流行，原始軌跡中進一步融入了社交圖、圖片、音頻、視頻等多元數(shù)據(jù)，致使軌跡數(shù)據(jù)的維度劇增。在軌跡大數(shù)據(jù)上進行相關(guān)處理時，需要同時兼顧動態(tài)的空間、時間、文本、社交關(guān)系等，這并不是一項平凡的任務(wù)。此外，隨著時間的推移，軌跡數(shù)據(jù)持續(xù)增加，這為在軌跡上的查詢處理和挖掘帶來巨大挑戰(zhàn)。

2) 多粒度

軌跡大數(shù)據(jù)上的信息具有多粒度的特點。單就位置而言，位置可以分別用離散點、線段、整條軌跡表示。單就一個位置點包含的語義而言，語義本身又體現(xiàn)著層次性。例如，用戶的位置是中國人民大學的經(jīng)緯度，中國人民大學又隸屬于高等院校，是教育機構(gòu)之一。位置與蘊含的語義信息的結(jié)合，加劇了軌跡的多粒度特性。具體來講，每一個特定的語義層次都可以評價單點、軌跡片段、片段集合、乃至整條軌跡。因此，在軌跡上進行相似性度量計算時，如何衡量軌跡上不同信息的粒度、如何支持全粒度(即局部和全局)搜索是一項具有挑戰(zhàn)性的工作。

3) 不確定

軌跡的不確定性表現(xiàn)在位置和語義兩個方面。受定位設(shè)備自身限制、軌跡采樣頻率的限制，存在采樣點丟失或采樣頻率不均勻等問題，位置采樣點和采樣點間的推理位置均具有不確定的特點。同時，與軌跡關(guān)聯(lián)的語義，受上下文環(huán)境或人為因素的影響，也具有明顯的不確定性，如用戶的評價回復中存在手工錄入的錯誤信息、同語義的感興趣點對應(yīng)不同物理位置的分店等。有時數(shù)據(jù)的不確定性是由人為故意為之，例如在數(shù)據(jù)輸入階段，當出現(xiàn)用戶不想要公開的信息時，會選擇輸入一些錯誤的值或輸入替代符號(如*)。數(shù)據(jù)的不確定性為軌跡相似性的精確計算帶來挑戰(zhàn)。

4) 高冗余

軌跡中的位置和語義均具有高冗余的特點。位置方面，由于傳感器設(shè)備以及GPS設(shè)備在固定的時間間隔記錄數(shù)據(jù)，并未考慮數(shù)據(jù)的代表性，所以會造成位置數(shù)據(jù)冗余。例如，車載GPS在車輛狀態(tài)沒有發(fā)生變化的情況下，仍然不停地記錄著車輛的當前位置數(shù)據(jù)。語義信息的冗余更加明顯，如關(guān)鍵字單復數(shù)重復記錄問題、詞語的同語義問題等。例如，公開數(shù)據(jù)集Foursquare[12-13]在興趣點(Points of Interested, POI)的標注中會同時出現(xiàn)名詞的單數(shù)和復數(shù)形式。再如，堵車、阻塞、等待時間長均表示交通擁堵，只是關(guān)鍵字不同而已。數(shù)據(jù)的高冗余性為軌跡存儲、軌跡相似性的計算帶來挑戰(zhàn)。

至今，在數(shù)據(jù)庫、數(shù)據(jù)挖掘、地理信息系統(tǒng)等領(lǐng)域，圍繞軌跡相似性度量，已發(fā)表了大量的研究工作。本文對現(xiàn)有工作進行總結(jié)歸納，第2章對軌跡的形式化表示和相似性度量問題進行了定義，第3章對軌跡相似性度量技術(shù)進行了分類，并針對每一種類型總結(jié)了相應(yīng)的特點。第4章梳理了軌跡相似性計算的幾個典型應(yīng)用領(lǐng)域。第5章對未來的研究方向進行展望。最后，對文章進行了總結(jié)。

2 問題描述

軌跡大數(shù)據(jù)上的相似性度量需要同時考慮時間、空間以及語義三方面信息的相似性?？臻g與時間相似性較直觀。語義信息包括文字、圖片、語音、視頻等，然而無論哪一種形式都可以將其抽象為關(guān)鍵字集合的形式。因此，簡單起見，在后續(xù)的描述中語義信息均以關(guān)鍵字集合進行代替。

2.1 軌跡表示法

軌跡的表示形式有很多種，主要分為三類：時間序列表示法、圖表示法和矩陣表示法。

2.1.1時間序列表示法

一條軌跡t可以表示成為按時間點排列的序列，形式化表示為t={p1,p2,…，pn}，其中，對于任意點pi=(l，c，w).pil表示該點所在經(jīng)緯度,pic表示該對象在此位置的時刻pi.w表示與位置pil相關(guān)的語義信息，用文本集合表示。時間序列表示法是軌跡最常用的表示方法之一。例如，用戶某天的簽到軌跡t1={((116.32, 39.97), 8:00, {Hotel, Sandwich}), ((116.37, 39.96), 12:00, {Gym, pizza}), ((116.37, 39.95), 15:00, {Mall, Coffee}), ((116.44, 39.95), 21:00, {Cinema}), ((135.44, 39.95), 23:00, {Bar})}。本文主要研究用時間序列表示的軌跡。

2.1.2軌跡其他表示法

圖表示法：軌跡集合亦可以用圖形式化地表示。設(shè)G=，其中V是位置點的集合，E是邊的集合，任意軌跡t可以表示為從起始點νi到終點νj的一條通路。例如，在圖1中，虛線表示用戶u1的軌跡。其中軌跡的語義信息可以作為頂點標簽或邊標簽的形式存在，說明頂點或路徑語義。

矩陣表示法：軌跡還可以用高維矩陣表示，如圖2所示，圖2中間位置的矩陣是將軌跡轉(zhuǎn)化為一個用戶—位置矩陣。矩陣的每一行代表一個用戶，矩陣的每一列表示簽到點的位置，如經(jīng)緯度，矩陣中的每一個元素代表用戶對某個位置的訪問次數(shù)或訪問持續(xù)時間等。圖2右側(cè)矩陣是將軌跡轉(zhuǎn)化為一個位置—活動矩陣。矩陣的每一行代表一個點的位置，矩陣的每一列表示用戶在簽到點的活動，如購物等，矩陣中的每一個元素代表在用戶是否在該個位置進行某項活動或活動的頻率。

圖2 軌跡的矩陣表示法Fig.2 Matrix representation of trajectories

2.2 軌跡相似性表示

定義1(軌跡相似性)設(shè)向量ω=(ω1,ω2,ω3)為軌跡相似性權(quán)重向量，其中ωi(i=1,2,3)分別表示空間、時間、文本的相似性權(quán)重，ω1+ω2+ω3=1。給定任意兩條軌跡t1,t2，則軌跡t1,t2的相似性可用向量點積表示

(1)

其中，d1(·),d2(·),d3(·)分別表示兩條軌跡在空間，時間，文本的距離函數(shù)。利用點到點的距離(記為distk(·))并將其歸一化，可以求得軌跡與軌跡的距離

(2)

當ω取不同值時，代表不同的軌跡相似性。例如，當ω是僅有一個元素為1的單位向量時，分別代表軌跡的空間相似性、時間相似性和文本相似性。現(xiàn)有工作[14-26]中有關(guān)ω的不同取值總結(jié)如表1所示。

表1 ω與軌跡相似性度量范圍的關(guān)系Tab.1 The relationship between ω and trajectorysimilarity measure range

定義1中的軌跡相似性定義對噪音敏感，可以采用設(shè)定閾值的方法解決對噪音敏感的問題[5-6,22,26-27]。

定義2(基于閾值的軌跡相似性)設(shè)θ={θ1,θ2,θ3}為距離約束閾值集合，其中θi(i= 1,2,3)分別表示空間、時間、文本的距離閾值。對于軌跡t1,t2上任意兩點p1,i，p2,j,修訂點到點的距離distk(p1,i,p2,j)如式(3)或式(4)所示，

(3)

(4)

式(3),式(4)通過設(shè)定約束閾值集合θ，可以過濾超過閾值的噪音。當然，對于噪音的清洗還有很多其他的方法，如針對可接受噪音可用地圖匹配(Map Matching)算法予以糾正，針對不可接受噪音可以用均值過濾(Mean Filter)法或卡爾曼與粒子濾波過濾(Kalman and Particle Filters)法用估計值替代，也可用基于啟發(fā)式規(guī)則的異常點檢測(Heuristics-Based Outlier Detection)法直接去噪，具體可參見文獻[28]，本文不一一贅述。

3 軌跡相似性度量方法

軌跡相似性受很多因素影響，例如，軌跡長度、形狀、運動趨勢、時間約束等。軌跡相似性度量分類方法很多，下面分別從數(shù)據(jù)類型、軌跡形式和度量范圍幾個方面對現(xiàn)有工作進行總結(jié)。

3.1 面向不同數(shù)據(jù)類型的相似性度量方法

從軌跡包含的數(shù)據(jù)類型的角度，相似性可從空間、時間、文本三個方面度量。

3.1.1空間相似性

空間相似性[14-16]是指從空間位置角度，若兩條軌跡距離很近或者軌跡形狀相似，則認為兩條軌跡相似。本文將定義軌跡與軌跡空間相似性的度量方法分為常用空間度量方法、基于時間序列的度量方法和基于編輯距離及其擴展的度量方法三種。表2展示了各典型方法在噪音敏感、時間約束和軌跡是否要求等長等方面的比較。

表2 軌跡空間距離函數(shù)Tab.2 Trajectory space distance function

1) 常用空間距離度量方法

Lp-norm距離：該方法是計算位置距離最常用的方法，形式化表示為

(5)

式中，x的不同取值代表了不同的距離函數(shù)，如表3所示?，F(xiàn)有軌跡相似性度量大多基于歐氏距離[5-6,20,26,29-33]。Lp-norm距離的缺點是不能處理局部時間偏移，局部時移是指在對齊兩條軌跡時容忍短期差異(例如，樣本點缺失，測量誤差等)的能力。

表3 x的取值與Lp-normTab.3 x and Lp-norm

Hausdorff距離：Hausdorff距離由Felix Hausdorff提出，原本用來度量空間中的兩個位置點集合的距離。將其應(yīng)用在軌跡中，直觀上來講，是將軌跡上最近點距離的最大值作為軌跡空間距離，具體公式為

dH(t1,t2)=max(h(t1,t2),h(t2,t1))，

(6)

(7)

其中，dH(t1,t2)為雙向?qū)ΨQ距離，h(t1,t2)為單向非對稱距離，‖p1,i-p2,j‖為兩點之間的空間距離。文獻[15]在道路網(wǎng)絡(luò)中利用Hausdorff距離計算軌跡空間相似性。如圖3所示，對于軌跡t1上的每一個點，依次計算該點到軌跡t2上所有點距離中的最小值，然后針對軌跡t1上的所有點，求最小值中的最大值即h(t1,t2)=3。同理可計算h(t2,t1)=4。所以，dH(t1,t2)=max(3,4)=4。由于Hausdorff距離是基于集合定義的，因此，將其應(yīng)用于軌跡時，位置上的時間信息被忽略了。

圖3 Hausdorff距離在路網(wǎng)中的應(yīng)用Fig.3 Application of Hausdorff distance in road network

片段距離：考慮到度量整條軌跡不能很好地表示軌跡間的相似性，可用軌跡中具有代表性的軌跡片段來評價軌跡相似性。文獻[19]將軌跡劃分成了若干片段，通過衡量軌跡片段的相似性評價兩條軌跡的空間相似性，如圖4所示。為了便于區(qū)別，軌跡線段記為Li。文獻[19]通過計算軌跡片段的垂直距離(式(8))，平行距離(式(9))以及角度距離(式(10))，并將三者加權(quán)求和(式(11))，得出兩條軌跡片段的距離。然而，該方法僅考慮了軌跡形狀的相似程度，忽略了位置上的時間因素。

圖4 軌跡線段表示Fig.4 Line segment representation of trajectory

(8)

dl(Li,Lj)=min(Ll1,Ll2)，

(9)

(10)

dLS(Li,Lj)=ωνdν(Li,Lj)+ωldl(Li,Lj)+
ωθdθ(Li,Lj)。

(11)

Fréchet距離：Fréchet距離[34]是法國數(shù)學家Maurice René Fréchet在1906年提出的一種路徑空間相似性描述，也稱為狗繩距離，如圖5所示。主人按路徑t1行走，狗按路徑t2行走，各自完成這兩條路徑的過程中需要的最短狗繩長度即直觀意義上的Fréchet距離。設(shè)t1和t2是兩條軌跡，α和β是兩個重參數(shù)化函數(shù)，c為時間，則軌跡t1與軌跡t2的Fréchet距離dF(t1,t2)定義為

dF(t1,t2)=

(12)

圖5 Fréchet距離Fig.5 Fréchet Distance

OWD距離：文獻[35]從軌跡空間形狀出發(fā)，提出了一種新的空間距離計算方法OWD(One Way Distance)距離。該方法將一條軌跡t1看作離散點的集合，另一個軌跡t2看作連續(xù)的線段集合(用分段函數(shù)表示)。OWD是軌跡t1上的所有點到軌跡t2所有線段的距離平均值作為兩條軌跡空間相似距離，具體公式為

(13)

TS-Join距離：文獻[36]考慮到軌跡的相似性與軌跡距離并不是呈線性遞增的特點，運用指數(shù)函數(shù)更好地度量了軌跡間的相似性。點到軌跡的距離定義為點到軌跡上所有點的距離的最小值，具體公式為

(14)

則軌跡與軌跡的相似性為

2) 基于時間序列的度量方法

動態(tài)時間規(guī)劃及其擴展：DTW大概在1970年左右被提出。DTW通過把時間序列進行延伸和縮短，計算兩個時間序列之間的相似性。由于軌跡數(shù)據(jù)可以看成是在多維空間中的時間序列，因此，可以采用DTW定義軌跡間的相似度。給定軌跡t1={p1,1,p1,2,…,p1,n} ，設(shè)Hd(t1)=p1,1，R(t1)={p1,2,…，p1,n}，t2={p2,1,p2,2,…,p2,n}則軌跡t1和t2的DTW距離為

(16)

式中，函數(shù)dist1(·)為距離函數(shù)可采用曼哈頓距離、歐式距離等。DTW解決了軌跡采樣頻率不同的問題，但對噪音較為敏感。PDTW[37]在DTW基礎(chǔ)上進行改進，利用軌跡簡化率將軌跡簡化，在簡化后的軌跡上套用DTW，求解軌跡間距離，提高了DTW的算法效率，其計算原理與DTW相同。

最長公共子序列：軌跡中的噪音可能導致軌跡局部距離過大。為了解決相似性計算對噪音敏感的問題，文獻[38]提出利用最長公共子序列定義兩條軌跡的空間距離。設(shè)軌跡t1={p1,1,p1,2,…,p1,n},t2={p2,1,p2,2,…,p2,n}，則軌跡t1和t2的LCSS距離定義為

(17)

式中，參數(shù)δ用于控制兩條軌跡的長度。θ1是一個距離閾值，用以判斷某點是否用于計算LCSS距離。若兩點間的距離小于閾值θ1，則將兩者距離記為1；否則忽略。LCSS距離的本質(zhì)是統(tǒng)計在一定范圍內(nèi)軌跡上距離較近的匹配點數(shù)量。LCSS距離雖然可防止噪音干擾，但兩個閾值δ和θ1較難確定。因此，有可能誤將兩條不相似的軌跡定義為相似軌跡。

同步歐幾里得距離：文獻[39]將軌跡的每一條線段看成一個關(guān)于時間u的線性函數(shù)t1(u)，計算移動物體1在c時刻的位置。利用此線性函數(shù)可計算每一個時刻軌跡上對應(yīng)點對的歐式距離。如此，將所有同步的歐式距離積分再除以兩條軌跡總的時間，即是兩條軌跡的距離，

3) 編輯距離及其擴展

基于序列的編輯距離：文獻[40]擴展了在字符串上的編輯距離定義，提出了一個新的距離函數(shù)—基于序列的編輯距離(EDR距離)，如式(19)所示。與LCSS關(guān)注尋找軌跡的相同點不同，EDR距離更關(guān)心的是兩條軌跡的不同點。直觀上，EDR是兩條軌跡上一個位置轉(zhuǎn)成另一個位置的代價和。該代價是將一個位置轉(zhuǎn)成另一個位置所需的編輯操作次數(shù)，編輯操作包括插入、刪除和替代。如圖6所示，實心點表示原有軌跡上的點，空心點表示插入或替代的點。如果兩個位置間的距離大于閾值則進行插入或替代操作，如圖6中的p1″,p2″,p5″。需要說明的是，EDR考慮了由于軌跡長度不同對軌跡相似性所造成的影響，最終得出的是編輯操作的次數(shù)，但并不是具體的空間距離值。式(19)中若t1和t2軌跡對應(yīng)兩點間距離小于閾值，則c值為0;反之，c值為1。

(19)

圖6 EDR距離Fig.6 EDR distance

ERP距離：文獻[41]提出一種稱為ERP(Edit distance with Real Penalty)的度量方法，該方法既滿足三角不等式，又能處理局部時間偏移。設(shè)軌跡t1與t2的長度分別為n和m(n≥m)，二者間的ERP距離定義為

(20)

ERP距離通過為軌跡添加間隙點(即零點)解決軌跡對齊問題。間隙點選取位置以使軌跡的ERP距離最小為原則。若p2,j和p1,i均不是間隙點，則dist(p2,j,p1,i)為這點間實際距離;若兩點中有一個為間隙點，則 為間隙點與另一個非間隙點的距離。

ERP使用了參考點g計算不匹配點的距離，而不像LCSS將這個距離設(shè)置為0，因此它滿足三角不等式的約束。

基于線段的編輯距離：文獻[14]基于EDR方法提出一種在軌跡線段上的編輯距離空間相似性計算方法EDS(Edit Distance on Segment)。首先將軌跡劃分成若干軌跡片段，兩個軌跡之間的距離定義為子軌跡轉(zhuǎn)換的最小代價，包括替代代價、拉伸代價和旋轉(zhuǎn)代價，即C(r,r′)。兩條軌跡的空間相似性距離為

(21)

por(L1·r1,L2·r2)為用軌跡片段L2·r1替代L1·r1的部分，L1L1·r1為軌跡L1除去r1后剩余軌跡。

3.1.2文本相似性

文本相似性主要用以評價軌跡數(shù)據(jù)上所標注的文本信息的相似程度。在軌跡上文本信息標注的粒度由粗到細分別為整條軌跡、線段及線段集合和單位置點。無論哪一種粒度，其文本相似性的評價方法主要包括TF-IDF[17-19]、Jaccard距離[22]、編輯距離[23]、余弦相似性、SimHash+漢明距離和語言模型。

1) TF-IDF

TF-IDF的主要思想是，如果某個詞或短語，(記為A)，在一篇文檔中(記為B)出現(xiàn)的頻率dTF高，并且在其他文檔中很少出現(xiàn)，則認為此詞或者短語具有很好的類別區(qū)分能力。TF-IDF具體的計算公式為

dTF-IDF=dTF·dIDF，

(22)

式中，dTF為詞頻(Term Frequency)，dIDF為反文檔頻率(Inverse Document Frequency)，該方法綜合考慮了詞的頻率和詞的文檔頻率，

(23)

(24)

在軌跡中應(yīng)用該模型時，文檔對應(yīng)于一條軌跡上所有的文本信息集合，語料庫即所有軌跡上的文本信息的值域。

2) Jaccard距離

Jaccard系數(shù)用于比較文本集之間的相似性與差異性。Jaccard系數(shù)值越大，文本相似度越高。

(25)

式中，t1·w表示第1條軌跡所含的全部文本信息的集合。

Jaccard距離與Jaccard系數(shù)相關(guān)，Jaccard距離越大，文本集合相似度越低，

dJD(t1·w,t2·w)=1-J(t1·w,t2·w)。

(26)

3) 編輯距離

編輯距離(Edit Distance)，又稱Levenshtein距離，是指兩個字串之間，由一個串轉(zhuǎn)成另一個串所需的最少編輯操作次數(shù)。編輯操作包括替換、插入和刪除。一般來說，編輯距離越小，兩個串的相似度越大。兩個字符串s1，s2的編輯距離定義為

(27)

式中，dEdit(s1,i,s2,j)表示s1字符串中長度為i的子串到s2字符串中長度為j的子串的編輯距離。

4) 余弦相似性

直觀的，如果兩句話中用詞越相似，則其內(nèi)容就越相似。因此，余弦相似性從詞頻入手，計算文本的相似程度。首先，統(tǒng)計文本信息中蘊含詞的詞頻。例如，I am a girl和I am a boy，其中單詞有I、am、a、girl、boy。第一個句子中的詞頻向量為(1,1,1,1,0)，第二個句子中的詞頻向量為(1,1,1,0,1)。然后，文本的相似度可以通過向量夾角表示。夾角越小代表兩個句子越相似。數(shù)學家已經(jīng)證明，余弦的這種計算方法對n維向量也成立，計算公式為

(28)

5) SimHash+漢明距離

SimHash是谷歌發(fā)明的算法，可以將一個文檔或字符串通過Hash算法轉(zhuǎn)換成64位的字節(jié)。通過判斷兩個字節(jié)的漢明距離計算字符串相似性。與編輯距離不同，漢明距離是計算兩個等長字符串相同位置不同字符的個數(shù)，如式(29)所示，其中⊕表示異或，

dSH(p1·w,p2·w)=∑p1·w[i]⊕p2·w[i]。

(29)

例如，兩個對象p1·w=“toned”，p2·w=“roses”。p1·w與p2·w的漢明距離dSH(p1·w,p2·w)=3。

6) 統(tǒng)計語言模型

統(tǒng)計語言模型被廣泛應(yīng)用于各種自然語言處理問題，如語音識別、機器翻譯、分詞、詞性標注等。Okapi BM25 是一種文獻匹配度評分模型。Okapi BM25考慮到既使兩個相同主題的文檔其關(guān)鍵詞頻率和文檔長度不一定相同，因此在TF-IDF 的基礎(chǔ)上改進，增加了兩個可調(diào)參數(shù)(k和b)，分別代表詞語頻率飽和度(term frequency saturation)和字段長度規(guī)約，使得文本相似性更加公平客觀。軌跡t1和t2的文本相似性計算公式為

(30)

f(p1,i·w,t2·w)為p1,i中的關(guān)鍵字在t2軌跡關(guān)鍵字集合中出現(xiàn)的頻率，avg表示所有軌跡包含關(guān)鍵字個數(shù)的均值。

3.1.3時間相似性

就時間表示粒度而言，時間可以用精確的時刻，也可用時段進行表示。當用時刻表示時，判斷時間相似性有兩種方法：第一，僅比較兩時刻是否一致，如果一致則認為相似，反之亦然，見式(31)。顯然，該方法過于嚴苛。第二種方法是為時間相似性設(shè)定某個閾值，如果兩時刻的時間差在閾值范圍內(nèi)，則認為相似，如果超出某個閾值則認為不相似，見式(32)。當時間是一個時段時，可以通過衡量兩區(qū)間是否相似來衡量時間的相似性。具體來講，兩個區(qū)間相似性可以定義為兩時段的相交區(qū)域與兩個時段的并的比值，見式(33)，該比值越大說明時間相似性越高。

(31)

(32)

d2(p1,i·c,p2,j·c)=

(33)

軌跡時間標注的粒度與文本類似，由細到粗亦可分為單點位置、軌跡線段、整條軌跡。如果時間標注粒度為單點位置，根據(jù)時間的不同表示形式可以采用式(31)～(32)計算相應(yīng)的時間相似性。如果時間粒度為軌跡線段或整條軌跡，根據(jù)時間的不同表示形式可分為：如果線段端點用時刻表示，可采用式(32)計算相應(yīng)的時間相似性;如果線段端點用區(qū)間表示，可采用式(33)計算時間相似性;如果整條線段采用區(qū)間表示，也可以采用式(33)計算時間相似性。

3.2 面向不同軌跡形式及度量范圍的相似性度量方法

從前面的描述可知，軌跡具有兩種形式：離散點和軌跡片段。整條軌跡可作為軌跡片段的特例。根據(jù)評價相似軌跡的粒度不同，可以將相似性度量范圍分為局部相似性和全局相似性。局部相似性是從整條軌跡中尋找滿足相似性要求的軌跡片段或片段集合;全局相似性旨在尋找滿足相似性要求的整條軌跡。綜合軌跡形式與度量范圍，可以將現(xiàn)有工作分為4類，離散點+全局相似性、離散點+局部相似性、片段+全局相似性、片段+局部相似性。目前，大部分工作主要集中于全局相似性研究上。

1) 基于離散點的軌跡全局相似性

基于離散點的軌跡全局相似性即通過計算軌跡上的離散點的相似性返回滿足要求的整條軌跡。此類工作大部分是通過單獨計算軌跡在時間、空間、文本三類數(shù)據(jù)的相似度距離，通過設(shè)定不同的權(quán)重，求得單方面或綜合兩兩組合的相似性距離的加權(quán)平均值。針對軌跡空間單方面相似性的研究存在大量工作[15,16,34,42-50]。文獻[22]和文獻[24]針對空間、文本兩種數(shù)據(jù)類型定義相似性，文獻[26]是針對軌跡時間、空間、文本三類數(shù)據(jù)的加權(quán)平均。文獻[22,24,26]主要針對在自由空間的空間數(shù)據(jù)。文獻[15]利用Hausdorff距離求解在道路網(wǎng)絡(luò)中的軌跡相似性。

2) 基于離散點的軌跡局部相似性

基于離散點的軌跡局部相似性即通過計算軌跡上離散點的時空和文本相似性，返回滿足要求的軌跡片段。若兩條軌跡的子軌跡間距離小于給定閾值，則認為這兩個子軌跡是相似的。文獻[23]利用編輯距離計算文本相關(guān)性，利用軌跡長度(即軌跡上相鄰兩個位置點的距離和)作為空間距離，并用sigmoid函數(shù)歸一化。通過對空間和文本加權(quán)求和計算相似性，返回滿足相似性要求的軌跡片段。文獻[21]針對軌跡空間，時間兩種數(shù)據(jù)類型定義軌跡相似度，提出了一種基于時間約束的Hausdorff距離時空軌跡相似性計算方法，該方法利用滑動窗口找到兩條較長軌跡中所有相似的子軌跡，從而判斷出較長軌跡間的相似性。

3) 基于線段的軌跡相似性

基于線段的軌跡相似性可以分為全局相似與局部相似兩類。無論是全局相似性還是局部相似性，其計算方法本質(zhì)相同，均將線段作為計算的基本單元，只是返回的軌跡形式不同。全局相似性返回整條軌跡，而局部相似性返回軌跡片段或片段集合。

基于軌跡線段的軌跡全局相似性通過計算整條軌跡是否滿足事先設(shè)定的相似性閾值，判斷兩條軌跡的相似性。文獻[14]將軌跡劃分成若干軌跡片段，定義兩個軌跡之間的距離為子軌跡轉(zhuǎn)換的最小代價，包括替代代價、拉伸代價和旋轉(zhuǎn)代價三者加權(quán)和，返回包含與查詢軌跡相似的部分的整條軌跡。文獻[16,32]同樣將軌跡劃分為若干軌跡片段，將軌跡線段的相似性定義為軌跡線段的垂直距離，水平距離以及角度距離三方面加權(quán)和，將這三個距離整合為軌跡線段間的距離，距離越小則軌跡線段相似度越大，返回與查詢軌跡相似的軌跡線段。

不同軌跡相似性度量方法的對比如表4所示。

4 應(yīng)用場景

軌跡相似性度量作為軌跡數(shù)據(jù)分析與挖掘的基礎(chǔ)，在各個領(lǐng)域具有十分重要的意義。

4.1 交通管理

城市交通管理一直都是各個國家為之困擾的問題。隨著經(jīng)濟貿(mào)易和社會活動日益繁忙，城市交通以前所未有的速度迅速增長，交通管理問題也日益嚴重。我國城市特別是大城市，在交通擁堵、車道違法占用、不安全駕駛行為等方面存在嚴重的交通安全隱患。

表4 軌跡相似性度量方法比較Tab.4 Comparison of trajectory similarity measurement methods

現(xiàn)在，大多數(shù)公共交通以及私家車都安裝有GPS，通過對車載GPS模塊采集的車輛軌跡數(shù)據(jù)進行相似性分析，可以發(fā)現(xiàn)城市中車輛在一定時間范圍內(nèi)容易集中的區(qū)域，對這些區(qū)域提早進行交通疏導管理，從根源上排除安全隱患。文獻[43]先定義了軌跡間距離，通過基于密度聚類算法對歷史軌跡進行聚類，推測用戶目的地。該項研究有助于避免人流聚集，防范重大交通事故和災(zāi)難性城市安全事件，避免類似上海外灘事件的事件發(fā)生。

文獻[1-2]分別通過對出租車軌跡進行空間和時間相似性分析，實現(xiàn)檢測大規(guī)模軌跡流中的異常對象。例如，文獻[1]通過判斷在一定時間閾值下軌跡所含相鄰軌跡的個數(shù)來判斷軌跡是否相似。若司機不停地改變車道，則該司機將可能被歸類為異常對象。文獻[2]通過分析整條軌跡序列的時間是否大于給定閾值來判斷軌跡是否為異常軌跡。該研究有助于檢測超速駕駛、酒后駕車等其他異常行為，為交通管理部門評價和管理駕駛員的駕駛行為提供科學的依據(jù)。

4.2 城市規(guī)劃

城市化與現(xiàn)代文明的發(fā)展使得城市在發(fā)展中形成了不同的功能區(qū)域，如住宅區(qū)、商業(yè)區(qū)、教育區(qū)等。這些功能區(qū)域可以根據(jù)人們的生活方式自然形成，也可以由規(guī)劃師人為設(shè)計。隨著時間的推移，功能區(qū)域亦會隨著城市發(fā)展不斷變化。功能區(qū)域的識別可為城市規(guī)劃、商業(yè)布局選址等多方面提供幫助。

文獻[4]利用移動軌跡相似性分析找到所蘊含的相似移動行為模式。通過相同行為模式推導出城市區(qū)域?qū)傩?。例如，如果大多?shù)軌跡在深夜訪問某個區(qū)域，則該區(qū)域很有可能為住宅區(qū)，如果大多數(shù)軌跡在工作日的上班時間段聚集，則該區(qū)域很可能為公司或教育區(qū)等等，圖7顯示的是文獻[4]對北京市功能區(qū)域的識別，不同深淺度代表不同的功能區(qū)域。

圖7 城市區(qū)域標記Fig.7 City area marker

文獻[46]通過對出租車軌跡的相似性分析，發(fā)現(xiàn)不同時間段居民出行的熱點路徑和出租車上下客熱點區(qū)域，獲取其隱含的出行行為規(guī)律信息，為城市區(qū)域設(shè)置和城市路線規(guī)劃問題的解決提供新途徑。

4.3 智能推薦

智能推薦是通過數(shù)據(jù)挖掘、人工智能等技術(shù)，為用戶推薦更優(yōu)化的服務(wù)。海量軌跡數(shù)據(jù)中除了位置和時間外，還包括豐富的語義信息，如興趣點類型、地理環(huán)境、用戶評價、道路狀況、天氣條件、鄰近朋友等數(shù)據(jù)。豐富的數(shù)據(jù)和信息為學習用戶習慣、用戶行為模式提供了強有力的數(shù)據(jù)支撐，為基于位置的推薦服務(wù)研究提供了助力。

文獻[33]從包含空間及文本信息的軌跡中利用kNN方法，找到與用戶查詢軌跡空間、文本方面均滿足的k條軌跡，并將其推薦給用戶。基于用戶軌跡或行為相似則偏好可能相似這一觀察，文獻[6]利用基于密度的聚類方法，從軌跡中發(fā)現(xiàn)移動對象密集區(qū)域，學習其中的共同行為模式并識別在一定時間段內(nèi)聚集的移動物體，這些聚集能夠為智能推薦提供推薦依據(jù)。文獻[7]利用核密度估計模型以及加權(quán)snippet shift方法從軌跡中發(fā)現(xiàn)相同高頻的移動行為模式，如圖8所示，例如，辦公-飯店-辦公-小區(qū)模式。文獻[8]通過一種潛在的基于主題的聚類算法，針對軌跡的語義層面識別出頻繁語義區(qū)域，通過條件概率模型得到區(qū)域間的轉(zhuǎn)換概率，學習其中的共同行為模式。文獻[3]使用帶有優(yōu)化聚類的MapReduce編程模型來挖掘Coterie模式，即要求在不等時間間隔約束下找出具有相似軌跡行為的模式，并提出基于語義的距離敏感推薦策略和基于語義的從眾性推薦策略。

圖8 相似行為模式Fig.8 Similar behavior model

4.4 智慧出行

出行是人類生活必不可少的一部分，在私家車泛濫的年代，合理規(guī)劃出行顯得更加重要。智慧出行是指基于大數(shù)據(jù)利用數(shù)據(jù)挖掘、人工智能等方法合理規(guī)劃出行時間、出行費用、出行方式等[50]。用戶出行時，可以把今天要去的地方以及時間羅列出來，通過對歷史軌跡數(shù)據(jù)的相似性分析，結(jié)合其他數(shù)據(jù)源如實時的天氣數(shù)據(jù)，得出與用戶需求相近的軌跡數(shù)據(jù)，用戶可以以這些數(shù)據(jù)為參考合理安排空閑時間。

文獻[9]設(shè)計實現(xiàn)了一個實時拼車系統(tǒng)，如圖9所示，在9(a)中，藍色軌跡為某車輛規(guī)劃軌跡，當出現(xiàn)一個新的用戶需求時(如9(a)中紅色虛線部分)，該車輛會及時調(diào)整路線規(guī)劃，調(diào)整后規(guī)劃路線如圖9(b)所示，圖9(c)為行程完成后的界面。該系統(tǒng)可以找到有相似出行需求的用戶，在不耽誤用戶到達時間的前提下為用戶節(jié)約資金，用戶可以自行設(shè)定節(jié)約資金與延長時間的比例，使得用戶不被頻繁打擾。

圖9 實時拼車系統(tǒng)T-ShareFig.9 Real-time car sharing system T-Share

4.5 環(huán)境保護

近年來隨著PM2.5、PM10等問題日益嚴重，環(huán)境質(zhì)量預測及污染物檢測受到廣泛關(guān)注。氣象預測和空氣質(zhì)量預測是通過已取得的情報資料和監(jiān)測統(tǒng)計數(shù)據(jù)，對未來或未知的環(huán)境進行估計和推測，對控制污染保護環(huán)境和人們身體健康有著非常重要的意義。

許多城市都有自己的天氣檢測系統(tǒng)，和地面空氣監(jiān)測站一起實時感知氣象數(shù)據(jù)和地面的空氣質(zhì)量。然而，由于監(jiān)測站等設(shè)備和儀器的建設(shè)和維護成本很高，一個城市通常也僅有有限個站點，例如，偌大的北京市只有22個空氣監(jiān)測站，這些站點并不能完全覆蓋整個城市范圍[10]。同時，氣候和空氣質(zhì)量的變化受很多因素影響(如，交通流量、氣象條件等)。即使空間距離很近的監(jiān)測站得出的數(shù)據(jù)信息也會存在顯著差異。

文獻[10]利用歷史天氣質(zhì)量軌跡數(shù)據(jù)，提出了一種基于由兩個獨立的分類器組成的協(xié)同訓練框架的半監(jiān)督學習方法。利用人工神經(jīng)網(wǎng)絡(luò)(ANN)和條件隨機場(CRF)，分別針對時間相關(guān)特征(例如，交通和氣象)以及位置相關(guān)特征(例如，道路長度和興趣點類別)進行建模，結(jié)合天氣、交通流量、路網(wǎng)和興趣點等多種數(shù)據(jù)源，預測各區(qū)域的空氣質(zhì)量信息。

5 研究趨勢展望

5.1 技術(shù)方面

1) 可調(diào)節(jié)匹配度的相似軌跡研究

現(xiàn)有大部分工作研究的是嚴格(強)相似性定義下的全局相似軌跡。具體來說，在計算軌跡相似性時，尋找的相似軌跡需要同時滿足時空約束與文本約束，同時這些約束是集中在相同對象上的。如圖10中的兩條軌跡，在強相似性要求的定義下，兩軌跡是不匹配的。因為軌跡上沒有一個點與另一個軌跡上的任意一點滿足時間、空間和文本一致性要求。然而，這兩條軌跡符合弱匹配的要求，即允許滿足時空相似性的點與滿足文本相似性的點不是同一個點。

圖10 弱匹配度舉例Fig.10 An example for weak match

研究具有弱匹配度的相似性軌跡是有意義的。例如，在為簽到用戶推薦簽到地址時，只需關(guān)注用戶簽到的地點和順序，無需嚴格要求簽到時間完全相同?，F(xiàn)有在弱匹配度的方面研究較少。實際上，不同的應(yīng)用場景，軌跡匹配度的要求不一樣。研究可調(diào)節(jié)匹配度、具有自適應(yīng)特點的軌跡相似性研究仍是一項開放的課題。

2) 約束閾值學習

相似性軌跡的確定需要很多閾值，如空間、文本和時間的權(quán)重、相似程度的閾值?，F(xiàn)有的大部分工作都是讓用戶自己定義相關(guān)閾值。約束閾值取值的好壞直接影響最終的相似性。如何合理設(shè)定這些閾值,使得查詢結(jié)果更好地滿足用戶需求,是一個非常有意義的研究問題。目前，機器學習領(lǐng)域的回歸模型、分類模型、主成分分析方法、層次分析法等方法可以通過訓練樣本數(shù)據(jù)給出更客觀和符合規(guī)律的權(quán)重值，這樣得出的權(quán)重或閾值比人為設(shè)定得出的相似性結(jié)果將更客觀。

3) 圖相似性計算方法

如前所述，軌跡除了使用時間序列表示以外還可以使用圖來表示。現(xiàn)有軌跡相似性計算大部分基于時間序列的表示形式[9,26,29,36-37,46,51]。眾所周知，在圖中具有很多經(jīng)典的理論和方法。如針對圖的分析方法有Deepwalk、Node2Vec、Struc2Vec、RolX核心方法等，可以根據(jù)相鄰節(jié)點和邊將結(jié)構(gòu)相同即相似的節(jié)點進行分類。目前，這些方法主要用于比較節(jié)點的相似性，對于軌跡圖的相似性還需進行改進。

4) 高階張量技術(shù)

張量是一個可用來表示矢量、標量和其他張量之間線性關(guān)系的多線性函數(shù)。正如引言部分所述，軌跡可以由高維矩陣來表示，即高階張量，則軌跡的相似性還可以通過張量分解等技術(shù)來計算，常見的張量分解方法有Basic MF，正則化矩陣分解，CP分解等。當將這些方法應(yīng)用到高維軌跡數(shù)據(jù)時，可以進行適當?shù)母倪M和擴展。

5.2 應(yīng)用場景

軌跡的概念可以被拓展到很多場景。除了通常認為的位置相關(guān)軌跡外，還可以延伸到各個領(lǐng)域，例如，購買軌跡，職業(yè)軌跡，健康軌跡等。

1) 購買行為軌跡

中國的網(wǎng)購熱潮推動了經(jīng)濟的快速發(fā)展，網(wǎng)上購物也已經(jīng)成為人們生活的重要一部分。人們在這些網(wǎng)站上的行為構(gòu)成了各種各樣的行為軌跡信息。個人在網(wǎng)絡(luò)上進行購物時，將進行一系列行為，例如，瀏覽，收藏，加入購物車，購買等。將用戶的這些購買行為按照時間進行排序，就形成了用戶的購買行為軌跡。用戶的購買行為并不是孤立的，相互之間具有聯(lián)系。通過分析相似客戶的購買行為，可以根據(jù)用戶最近購買、收藏、加入購物車中的物品等推斷用戶即將購買的產(chǎn)品。此外，對客戶的購買行為軌跡進行分析，有助于為用戶畫像、發(fā)現(xiàn)相似用戶群體。商家可以利用這些信息為用戶進行個性化推薦，提高廣告投放價值。

2) 職業(yè)軌跡

職業(yè)軌跡指將個人的職業(yè)經(jīng)歷按時間進行排序形成的軌跡數(shù)據(jù)。人的一生可能會經(jīng)歷幾次職業(yè)的轉(zhuǎn)變，每一次職業(yè)的轉(zhuǎn)變都會面臨著風險。通過對人的職業(yè)軌跡進行相似性分析，可以識別擁有相似性就職經(jīng)歷的人群。此外，雖然成功人士的經(jīng)歷不可復制，但是其成功的經(jīng)驗仍具有一定的借鑒意義。通過在若干職業(yè)軌跡中查找相似性軌跡，可以幫助人們對今后的就職方向進行決策。文獻[25]通過利用經(jīng)典序列對比方法，研究人與人之間的職業(yè)軌跡的相似性，為人們職業(yè)規(guī)劃提供幫助。

3) 健康軌跡

隨著智能穿戴設(shè)備的普及和流行，智能穿戴設(shè)備上記錄的信息隨著時間的積累將形成用戶的健康軌跡，通過對這些軌跡進行分析，可以找到身體狀況相似的用戶群體。同群體用戶的相關(guān)經(jīng)驗有助于彼此借鑒，同時對商家來說可提高廣告投放的回報率和價值。

5.3 安全與隱私

軌跡數(shù)據(jù)包含了許多個人敏感信息，對軌跡進行分析必然會帶來隱私泄露的風險。文獻[52-53]指出連續(xù)性的軌跡數(shù)據(jù)暴露會更容易被攻擊者獲取其行為習慣或者其日常工作場景。雖然已有一些對用戶隱私數(shù)據(jù)提供保護的方法研究，例如，加密、匿名化、差分等[54-55]。然而，現(xiàn)有方法在解決軌跡數(shù)據(jù)隱私保護問題上仍需進一步提高。在用戶軌跡隱私保護方面仍有很多開放的問題有待進一步討論研究。

6 結(jié)束語

定位技術(shù)和基于位置服務(wù)應(yīng)用的蓬勃發(fā)展積累了大量的用戶時空、文本、圖像數(shù)據(jù)，形成海量軌跡大數(shù)據(jù)。這些軌跡數(shù)據(jù)中蘊含了豐富的信息，為交通管理、城市規(guī)劃、智慧出行、環(huán)境保護等提供了重要的幫助。本文通過對現(xiàn)有的軌跡相似性度量工作進行總結(jié)歸納，提煉了軌跡大數(shù)據(jù)的特點以及在軌跡大數(shù)據(jù)上度量相似性存在的挑戰(zhàn)。從不同的數(shù)據(jù)類型、軌跡形式和度量范圍對現(xiàn)有的相似性計算方法進行了歸納總結(jié)，并分析了各種方法的優(yōu)缺點。討論了軌跡相似性在各個典型領(lǐng)域中的具體應(yīng)用場景。最后，針對軌跡大數(shù)據(jù)未來可能的研究方向提出了展望。