基于時(shí)間序列的軌跡數(shù)據(jù)相似性度量方法研究及應(yīng)用綜述

潘 曉，馬 昂，郭景峰，吳 雷,2，劉風(fēng)陽

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

0 引言

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

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

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

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

1) 高維異構(gòu)

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

2) 多粒度

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

3) 不確定

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

4) 高冗余

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

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

2 問題描述

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

2.1 軌跡表示法

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

2.1.1時(shí)間序列表示法

一條軌跡t可以表示成為按時(shí)間點(diǎn)排列的序列，形式化表示為t={p1,p2,…，pn}，其中，對于任意點(diǎn)pi=(l，c，w).pil表示該點(diǎn)所在經(jīng)緯度,pic表示該對象在此位置的時(shí)刻pi.w表示與位置pil相關(guān)的語義信息，用文本集合表示。時(shí)間序列表示法是軌跡最常用的表示方法之一。例如，用戶某天的簽到軌跡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})}。本文主要研究用時(shí)間序列表示的軌跡。

2.1.2軌跡其他表示法

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

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

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

2.2 軌跡相似性表示

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

(1)

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

(2)

當(dāng)ω取不同值時(shí)，代表不同的軌跡相似性。例如，當(dāng)ω是僅有一個元素為1的單位向量時(shí)，分別代表軌跡的空間相似性、時(shí)間相似性和文本相似性?，F(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)分別表示空間、時(shí)間、文本的距離閾值。對于軌跡t1,t2上任意兩點(diǎn)p1,i，p2,j,修訂點(diǎn)到點(diǎn)的距離distk(p1,i,p2,j)如式(3)或式(4)所示，

(3)

(4)

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

3 軌跡相似性度量方法

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

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

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

3.1.1空間相似性

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

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

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

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

(5)

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

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

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

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

(6)

(7)

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

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

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

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

dF(t1,t2)=

(12)

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

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

(13)

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

(14)

則軌跡與軌跡的相似性為

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

動態(tài)時(shí)間規(guī)劃及其擴(kuò)展：DTW大概在1970年左右被提出。DTW通過把時(shí)間序列進(jìn)行延伸和縮短，計(jì)算兩個時(shí)間序列之間的相似性。由于軌跡數(shù)據(jù)可以看成是在多維空間中的時(shí)間序列，因此，可以采用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ǔ)上進(jìn)行改進(jìn)，利用軌跡簡化率將軌跡簡化，在簡化后的軌跡上套用DTW，求解軌跡間距離，提高了DTW的算法效率，其計(jì)算原理與DTW相同。

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

(17)

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

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

3) 編輯距離及其擴(kuò)展

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

(19)

圖6 EDR距離Fig.6 EDR distance

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

(20)

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

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

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

(21)

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

3.1.2文本相似性

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

1) TF-IDF

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

dTF-IDF=dTF·dIDF，

(22)

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

(23)

(24)

在軌跡中應(yīng)用該模型時(shí)，文檔對應(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)容就越相似。因此，余弦相似性從詞頻入手，計(jì)算文本的相似程度。首先，統(tǒng)計(jì)文本信息中蘊(yùn)含詞的詞頻。例如，I am a girl和I am a boy，其中單詞有I、am、a、girl、boy。第一個句子中的詞頻向量為(1,1,1,1,0)，第二個句子中的詞頻向量為(1,1,1,0,1)。然后，文本的相似度可以通過向量夾角表示。夾角越小代表兩個句子越相似。數(shù)學(xué)家已經(jīng)證明，余弦的這種計(jì)算方法對n維向量也成立，計(jì)算公式為

(28)

5) SimHash+漢明距離

SimHash是谷歌發(fā)明的算法，可以將一個文檔或字符串通過Hash算法轉(zhuǎn)換成64位的字節(jié)。通過判斷兩個字節(jié)的漢明距離計(jì)算字符串相似性。與編輯距離不同，漢明距離是計(jì)算兩個等長字符串相同位置不同字符的個數(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)計(jì)語言模型

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

(30)

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

3.1.3時(shí)間相似性

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

(31)

(32)

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

(33)

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

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

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

1) 基于離散點(diǎn)的軌跡全局相似性

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

2) 基于離散點(diǎn)的軌跡局部相似性

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

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

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

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

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

4 應(yīng)用場景

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

4.1 交通管理

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

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

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

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

4.2 城市規(guī)劃

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

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

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

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

4.3 智能推薦

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

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

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

4.4 智慧出行

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

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

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

4.5 環(huán)境保護(hù)

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

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

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

5 研究趨勢展望

5.1 技術(shù)方面

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

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

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

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

2) 約束閾值學(xué)習(xí)

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

3) 圖相似性計(jì)算方法

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

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

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

5.2 應(yīng)用場景

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

1) 購買行為軌跡

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

2) 職業(yè)軌跡

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

3) 健康軌跡

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

5.3 安全與隱私

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

6 結(jié)束語

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