一個有效的稀疏軌跡數據相似性度量

肖嘯騏

0 引言

隨著位置感知技術[1]的發展，使得人們能夠以較高的時空分辨率記錄位置歷史數據，對于位置歷史數據的處理和分析逐漸成為新的研究熱點。由于移動對象的軌跡數據的多樣性和復雜性與日遞增，對這些軌跡數據的挖掘和分析顯得更加重要。由于移動對象的運動軌跡是不斷發生變化的，軌跡點之間的時間間隔也在不斷變化著，并且移動對象的軌跡的時間跨度占整個觀察時間的比例很小，因此移動對象的軌跡數據在時間維度上呈現稀疏性。相似性是各項軌跡數據挖掘任務的核心，在基于位置的社交網絡中需要衡量用戶行為軌跡的相似性，來找出地理位置相似的用戶[2]；在證券市場股票交易行為中需要衡量交易帳戶的證券交易行為的相似性，來挖掘涉嫌操縱股票的交易帳戶[3]；在視覺監控中需要衡量目標的運動軌跡相似性，來提供異常運動預測[4]。因此，有效的定義稀疏軌跡相似性有助于對移動對象的稀疏軌跡數據進行挖掘和分析。

歐幾里德距離[5]是一種最常用的相似度表示，但它要求兩軌跡的軌跡點數相等。最小外包矩形距離方法[6]是將整條軌跡劃分為一些相對平滑的軌跡區間，再將每條子軌跡用其最小外包矩形表示，這樣通過比較最小外包矩形序列即可度量軌跡間的相似性。它的優點是非常直觀且易于理解，但是如何有效地將稀疏軌跡劃分成平滑軌跡區間仍有待于研究。DTW(Dynamic time warping)是一種有效的計算不同長度的軌跡相似性方法，但它對于稀疏軌跡中的噪聲數據點敏感[7]。隱馬爾可夫模型(Hidden Markov Model,HMM)[8]或其他概率模型的軌跡建模方法在軌跡相似性研究中經常被使用，它的思路是先根據其他軌跡建立模型，再根據當前軌跡在模型中的生成概率來計算軌跡匹配度。概率模型在計算稀疏軌跡相似度時計算代價較大，細節區分能力不足，分析時需要額外的信息。

文獻[9]中對稀疏軌跡數據進行了研究，它提出了一種基于概率的推薦模型，對大量出租車軌跡進行挖掘，分析出租車軌跡的相似性。但文獻[9]中的方法在計算相似性時計算代價大，運行效率低。

編輯距離[10][11][12](Edit Distance)，又稱Levenshtein距離，是指兩個字符串S1和S2之間，由S1轉成S2所需的最少編輯操作次數。編輯操作包括：插入、刪除和替換三種操作。在基于編輯距離比較方法中，將對象軌跡視為字符串，兩軌跡之間相似性就可以用編輯距離來度量。在編輯距離方法中，比較的兩字符串長度可以不一致，并且字符串中可以有多個空字符(即字符串具有稀疏的特性)。 因此編輯距離適合分析移動對象的稀疏軌跡，本文也主要探討編輯距離在移動對象的稀疏軌跡相似性上的運用。

在移動對象的稀疏軌跡中，由于噪聲點的存在，使得軌跡挖掘和分析方法的精確度會受到影響。如果能找到軌跡中的關鍵點，在用關鍵點構成的軌跡來代替原軌跡，那么會在一定程度上提高軌跡挖掘和分析方法的精確度。由于移動對象的稀疏軌跡中的軌跡點分布不均勻，有些軌跡點在時間維度上比較接近，有些軌跡點在時間維度上間隔很遠。如果能夠有效的將時間分段，將在整個觀察時間內尋找關鍵點的任務劃分為在若干個時間子段內尋找關鍵點，那么也會在一定程度上提高軌跡挖掘和分析方法的效率。

1 相關工作

單純的編輯距離直接運用到稀疏軌跡相似性分析中還有不足之處，例如ERP[13](Edit Distance with Real Penalty)適合于實數序列的方法分析，然而對于稀疏軌跡相似性分析時，還存在一些缺陷。ERP用真實值來度量距離，而不是將距離概化為0和1，所以該方法對噪聲敏感。

文獻[14]提出了 EDR方法(Edit Distance on Real sequence)，采用了編輯距離，通過正態化處理降低了噪聲的干擾，使得度量方法更加精確。但EDR方法是針對一般的數據檢索提出來的，在分析移動對象的稀疏軌跡時稍有不足。

文獻[15]也提出了改進的ERP算法，采用編輯距離，定義了插入、刪除和替換操作的代價函數，分析兩條軌跡之間的相似性。不足之處在于分析稀疏軌跡時，它是以原始坐標數據計算的，每個坐標作為一個元素來計算編輯距離，則需要花費大量時間比較兩條軌跡中所有軌跡點，導致算法效率較低。

本文針對移動對象的運動軌跡分析，考慮到運動軌跡的主要特征在于移動對象的運動方向的變化，根據編輯距離思想，提出了一種基于關鍵點和時間分段的稀疏軌跡相似性度量算法(Sparse Trajectory Similarity)。

2 關鍵點

本文提出關鍵點的原因是ERP和EDR方法都是以原始坐標數據計算的，每個軌跡點的坐標都作為一個元素來計算稀疏軌跡。噪聲點的出現，會使得這些方法的準確率受到干擾。本文采用尋找關鍵點方法，找出移動對象的稀疏軌跡中的關鍵點，然后對關鍵點軌跡進行軌跡挖掘和分析，提高了準確度。

移動對象的運行軌跡是受該移動對象的意識支配的，一般在確定目的地后，行為軌跡不會發生太大的變化。通常移動對象的運動具有保持運動方向的趨勢，而改變運動方向的軌跡點更有意義。如果移動對象的運行方向發生較小的變化以至于微乎其微，那么就認為移動對象繼續保持著運動方向；但當移動對象的運行方向發生較大的變化，那么就認為移動對象的軌跡中運行方向發生改變。

文中給定閾值λ，當軌跡的運行方向變化超過λ時，將此時的軌跡點稱為關鍵點，如圖1所示：

圖1 示例軌跡TR

圖1中的λ設為 30度，對于一條軌跡TR=p1p2p3p4p5p6p7p8，只有在p4和p6軌跡點上運行方向改變值超過了30度，因此p4和p6被視為關鍵點；另外p1和p8屬于軌跡的開始點和結束點，也要被視為關鍵點。因此，圖3中的關鍵點構成的軌跡為TRkey=p1p4p6p8。

關鍵點的尋找應該遵循兩個原則：精確度和簡明性。精確度意味著原軌跡和它的關鍵點軌跡之間的差異應該越小越好，體現著原軌跡運動軌跡的風貌。簡明性意味著關鍵點數量應該越少越好，體現著軌跡挖掘和分析方法的運行效率。精確度和簡明性是相對的，如果一條軌跡中所有的點都視為關鍵點，那么精確度達到最高，簡明性達到最低，軌跡挖掘和分析方法的運行效率最低；如果只有開始點和結束點被視為關鍵點，那么簡明性達到最高，而精確度達到最低，則很容易將兩個軌跡相差很大的移動對象視為軌跡相似。因此本文尋找關鍵點時應該在這兩個原則中達到平衡。

尋找關鍵點的具體規則如下：

(1)對于一條軌跡 TR=p1p2p3...pi...pn，pi(1<=i<=n)為軌跡上的點，軌跡開始點p1和結束點pn肯定為關鍵點。如果在軌跡pi點的運動方向變化值θi大于閾值λ，那么pi視為關鍵點。本文中,軌跡pi點的運動方向變化值θi的計算方法如下：

(2)如果軌跡中運動方向變化值都未超出閾值λ，根據規則(1)，僅僅會得到兩個關鍵點：軌跡的開始點和結束點。如圖2所示：

圖2 示例軌跡TR

圖2中閾值λ設為30度，軌跡TR= p1p2p3p4p5p6p7p8，從p2到p7中，每個點的運動方向變化值都小于閾值λ，最終只有p1和p8是關鍵點，這樣就不能很好的反映出軌跡內部的運動變化細節，因此本文規定如果從一個關鍵點開始，經過η個點，仍未出現運動方向改變超出閾值λ的情況，那么將第η個點視為關鍵點，并依次類推。

本文將尋找關鍵點的算法稱為KP(Key Point)算法，KP算法具體如下：

KP算法首先將軌跡開始點和結束點標為關鍵點(第 1行)，并且初始化關鍵點軌跡(第2行)，然后遍歷軌跡中的軌跡點，將符合關鍵點條件的軌跡點標為關鍵點(第3-12行)，再將標記的關鍵點加入到關鍵點軌跡中(第13-17行)，最后返回關鍵點軌跡(第 18行)。其中 Flagi是關鍵標志，若 pi是關鍵點，則Flagi=1;否則Flagi=0。

3 時間分段

移動對象的稀疏軌跡的軌跡點在時間維度上分布不均勻，有些軌跡點之間的時間間隔很短，而有些軌跡點之間的時間間隔很長。為了提高尋找關鍵點的效率，如果將整個觀察時間分段成若干個時間子段，并同時在這些時間子段內尋找關鍵點，這樣會大大提高尋找關鍵點的效率。

當時間子段內軌跡點數較少，為了使關鍵點軌跡體現原軌跡的運動風貌，可以將該時間子段內的每個軌跡點都視為關鍵點。當時間子段內軌跡點數較多時，為了加快尋找關鍵點的效率，可以在該時間子段內利用 KP算法尋找關鍵點。因此本文給定閾值ε，當時間子段內的軌跡點大于ε時，就視為在該時間子段內利用KP算法尋找關鍵點；否則將該時間子段內的軌跡點都視為關鍵點。

接下來文中給出了時間分段的具體規則，如下：

(1)對于一條軌跡的時間序列 TR=t1t2t3...ti...tn，ti(1<=i<=n)對應軌跡上時間為ti的軌跡點，若ti與ti+1相隔時間小于閾值δ，則ti與ti+1分別對應的軌跡點屬于同一段時間子段。

(2)若時間子段中的點數大于ε，則運用KP算法在該子軌跡中尋找關鍵點，否則將該時間子段中的點都視為關鍵點。

本文將針對稀疏軌跡的時間分段算法稱為 TS(Time Slicing)算法，該算法具體如下：

TS算法首先初始化關鍵點軌跡(第1行),再遍歷軌跡點，生成時間子段集合(第2-10行)，然后在時間子段中尋找關鍵點(第11-17行)。對于時間子段中點數大于閾值ε時，運用KP算法尋找關鍵點(第12-13行)；否則將該時間子段中的軌跡點都視為關鍵點(第 14-15)。最后返回關鍵點軌跡(第 18行)。

4 稀疏軌跡相似性度量及其計算算法

定義編輯距離的關鍵是設置合理的代價值，即編輯操作應付出相應的代價值。代價值越小，兩軌跡相似性越高。在關鍵點和時間分段算法的基礎上，本文采用編輯距離來計算插入操作的代價、替換操作的代價和刪除操作的代價。

對于兩條軌跡關鍵點構成的序列P和Q，m和n分別為序列P和Q的長度，pi為序列P的第i個元素,qj為序列Q的第j個元素，Rest(P)為P中除去當前比較字符以外的其他字符部分，Rest(Q)同理如此。計算將序列P轉換為序列 Q的代價，所有操作都在序列P上進行，因為，軌跡是按時序建立的，因此，本文定義插入操作(insert)的代價為插入的坐標與當前狀態前一個坐標的歐幾里德距離，如公式(1)：

定義替換操作(substitute)的代價為替換的2個元素之間的歐幾里德距離，如公式(2)：

其中，若替換的2個元素之間的歐幾里德距離小于σ時，2個元素的替換操作的代價視為0，本文中σ設為單位長度的二分之一；定義刪除操作(delete)的代價為刪除的坐標與當前狀態前一個坐標的歐幾里德距離，如公式(3)：

在公式(1)、(2)和(3)中：O 代表原點坐標(0,0)；|pi-qj|為兩坐標點之間的歐幾里德距離。序列P和Q之間的編輯操作代價如公式(4)：

當兩條稀疏軌跡之間的編輯代價越大時，表示需要更多的編輯操作，才能實現兩條稀疏軌跡之間的編輯轉換，則這兩條稀疏軌跡間的相似性越小。當兩條稀疏軌跡之間的編輯代價越小時，表示需要更少的編輯操作，就能實現兩條稀疏軌跡之間的編輯轉換。當編輯代價等于0時，表示不需要編輯操作，就可以實現兩條稀疏軌跡之間的編輯轉換，則這兩條稀疏軌跡完全相同。因此以稀疏軌跡間的編輯代價為變量，稀疏軌跡之間的相似性隨著編輯代價的遞增而減小，隨著編輯代價的遞減而增大，故稀疏軌跡之間的相似性函數應滿足單調遞減性。因此，本文提出用于計算稀疏軌跡之間的相似性如公式(5)：

本文基于關鍵點和時間分段算法，提出了稀疏軌跡相似性計算算法，稱為STS(Sparse Trajectory Similarity)算法，具體如下：

STS算法首先利用TS和KP算法尋找關鍵點(第1行)，然后根據公式(1)、(2)和(3)計算編輯代價。當第一條軌跡的關鍵點軌跡長度為0時，直接計算兩條軌跡間的插入操作代價(第2-3行)；當第二條軌跡的關鍵點軌跡長度為0時，直接計算兩條軌跡間的刪除操作代價(第4-6行)。再通過遞歸函數，根據公式(4)計算得出兩條軌跡間的編輯代價(第7-10行)。最后根據公式(5)，求得兩條軌跡間的相似性(第11行)。

5 實驗

實驗平臺是Windows 7，CPU 3.20GHz，內存4GB。實驗采用的是舊金山的出租車 GPS移動軌跡數據[http://www.datatang.com/data/15731]，出租車數目為500輛，監控時間是30天。該數據集中的出租車軌跡稠密度差異大，是一個典型的稀疏軌跡數據集，如表1所示：

表1 出租車GPS移動軌跡數據

表1中車輛的位置信息為(北緯，西經)，例如車輛 O1在時間t1的位置為北緯37.75度，西經122.39度。

5.1 效率

實驗隨機抽取了3個樣本數據集，包括100輛、200輛和500輛出租車在30天內的GPS移動軌跡數據。實驗分別比較了STS算法與文獻[15]中以原始坐標數據進行編輯距離計算的ERP算法在計算軌跡相似性的運行效率，其中閾值λ從20度依次遞增1度、直到60度；閾值η從2依次遞增1、直到 20；閾值ε從 2依次遞增，直到 20；閾值δ從 2依次遞增，直到10秒。兩種算法在每種參數組合的情況下分別運行10次。兩種算法在3個樣本數據集上的運行結果如圖3、圖4、圖5所示：

圖3 STS和ERP算法在100輛出租車的GPS移動軌跡數據集上的運行

圖4 STS和ERP算法在200輛出租車的GPS移動軌跡數據集上的運行結果

圖5 STS和ERP算法在500輛出租車的GPS移動軌跡數據集上的運行結果

在圖3中STS算法的最大運行時間和最小運行時間都小于ERP算法的最大運行時間和最小運行時間。在圖4中STS算法的最大運行時間和最小運行時間也都小于ERP算法的最大運行時間和最小運行時間。在圖5中STS算法的最大運行時間和最小運行時間也都小于ERP算法的最大運行時間和最小運行時間。

當樣本中出租車輛數為100時，STS算法的最小運行時間和最大運行時間分別為1000ms和2000ms，ERP算法的最小運行時間和最大運行時間分別為8000ms和9000ms。當出租車輛數增大時，STS算法的最小運行時間和最小運行時間增幅不大,始終低于10000ms；而ERP算法運行時間增幅很大。這是因為 STS算法通過關鍵點的篩選，去除了不必要的計算開銷，而 ERP算法始終對原始軌跡點坐標進行計算，在不必要的軌跡點上花費了大量的時間。STS算法的運行速度相較ERP算法有很大的提高。

5.2 有效性

實驗分別用本文中的STS算法和文獻[15]中的ERP算法對3個樣本數據集進行聚類，聚類方法選用Kmeans方法，聚類結果用purity和NMI衡量。其中閾值λ從20度依次遞增1度、直到60度；閾值η從2依次遞增1、直到20；閾值ε從2依次遞增，直到20；閾值δ從2依次遞增，直到10秒。兩種算法在每種參數組合的情況下分別運行10次，聚類效果如表2、表3、表4所示：

表2 STS和ERP算法在100輛出租車數據集上的聚類效果

表3 STS和ERP算法在200輛出租車數據集上的聚類效果

表4 STS和ERP算法在500輛出租車數據集上的聚類效果

在對3個樣本數據集進行聚類時，STS算法的聚類結果中的最大purity值和NMI值都大于ERP算法中的最大purity值和NMI值。同時STS算法的最小purity值和NMI值都大于ERP算法的最大purity值和NMI值。這是因為STS算法通過關鍵點的篩選，去除了噪聲軌跡點的干擾，故提高了聚類準確率。ERP沒有去除噪聲軌跡點的干擾，所以聚類準確率低。

6 總結

本文的主要目的是研究如何用編輯距離來計算稀疏軌跡之間的相似性。本文考慮到運動軌跡的主要特征在于人或物體運動方向的變化，提出的基于關鍵點和時間分段的稀疏軌跡相似性計算算法，提高了傳統的軌跡相似性方法分析稀疏軌跡相似性的運行效率和準確度。

[1]Jie Liu,Bodhi Priyantha,Ted Hart,Heitor S.Ramos,Antonio Alfredo Ferreira Loureiro,Qiang Wang.Energy efficient GPS sensing with cloud offloading[C].SenSys,2012:85-98.

[2]Shuo Shang,Ruogu Ding,Kai Zheng,Christian S.Jensen,Panos Kalnis,Xiaofang Zhou.Personalized trajectory matching in spatial networks[J].VLDB,2013,7.

[3]李備友.基于復雜網絡的證券市場傳聞擴散與羊群行為演化研究[D].南京:南京航空航天大學,2012:

[4]李策.基于軌跡分析的視覺目標異常行為檢測算法研究[D].北京：中國科學院，2012:

[5]Hongbin Zhao,Han Qilong,Pan Haiwei,Yin Guisheng.Spatio-temporal similarity measure for trajectories on road networks[C].ICICSE,2009:189-193.

[6]楊澤雪,郝忠孝.空間數據庫中的組障礙最近鄰查詢研究[J].計算機研究與發展,2013,50(11):2455-2462.

[7]Pekka Siirtola,Perttu Laurinen,Juha Roning.A Weighted Distance Measure for Calculating the Similarity of Sparsely Distributed Trajectories[C].ICMLA,2008:802-807.

[8]Alexandre Hervieu,Patrick Bouthemy,Jean-Pierre Le Cadre.A HMM-based method for recognizing dynamic video contents from trajectories[C].ICIP,2007,4:533-536.

[9]袁晶.大規模軌跡數據的檢索、挖掘和應用[D].合肥：中國科技大學,2012:

[10]Horst Bunke.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(8):689-694.

[11]Philip Bille.A survey on tree edit distance and related problems[J].Theoretical Computer Science,2005,337(1-3):217-239.

[12]Zaiben Chen,Heng Tao Shen,Xiaofang Zhou,Yu Zheng,Xing Xie[C].SIGMOD,2010:255-266.

[13]Lei Chen,Raymond T.Ng.On the marriage of Lp-norms and edit distance[C].VLDB,2004:792-803.

[14]Chen L,Qzsu M T,Oria V.Robust and fast similaritysearch for moving object trajectories[C].ACM,2005:491-502.

[15][15]Liu Kun,Yang Jie.Trajectory distance metric based on edit distance[J].Journal of Shanghai jiaotong university,2009,43(11):1725-1729.