肖嘯騏

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 關(guān)鍵點(diǎn)

本文提出關(guān)鍵點(diǎn)的原因是ERP和EDR方法都是以原始坐標(biāo)數(shù)據(jù)計(jì)算的，每個(gè)軌跡點(diǎn)的坐標(biāo)都作為一個(gè)元素來計(jì)算稀疏軌跡。噪聲點(diǎn)的出現(xiàn)，會(huì)使得這些方法的準(zhǔn)確率受到干擾。本文采用尋找關(guān)鍵點(diǎn)方法，找出移動(dòng)對(duì)象的稀疏軌跡中的關(guān)鍵點(diǎn)，然后對(duì)關(guān)鍵點(diǎn)軌跡進(jìn)行軌跡挖掘和分析，提高了準(zhǔn)確度。

移動(dòng)對(duì)象的運(yùn)行軌跡是受該移動(dòng)對(duì)象的意識(shí)支配的，一般在確定目的地后，行為軌跡不會(huì)發(fā)生太大的變化。通常移動(dòng)對(duì)象的運(yùn)動(dòng)具有保持運(yùn)動(dòng)方向的趨勢(shì)，而改變運(yùn)動(dòng)方向的軌跡點(diǎn)更有意義。如果移動(dòng)對(duì)象的運(yùn)行方向發(fā)生較小的變化以至于微乎其微，那么就認(rèn)為移動(dòng)對(duì)象繼續(xù)保持著運(yùn)動(dòng)方向；但當(dāng)移動(dòng)對(duì)象的運(yùn)行方向發(fā)生較大的變化，那么就認(rèn)為移動(dòng)對(duì)象的軌跡中運(yùn)行方向發(fā)生改變。

文中給定閾值λ，當(dāng)軌跡的運(yùn)行方向變化超過λ時(shí)，將此時(shí)的軌跡點(diǎn)稱為關(guān)鍵點(diǎn)，如圖1所示：

圖1 示例軌跡TR

圖1中的λ設(shè)為 30度，對(duì)于一條軌跡TR=p1p2p3p4p5p6p7p8，只有在p4和p6軌跡點(diǎn)上運(yùn)行方向改變值超過了30度，因此p4和p6被視為關(guān)鍵點(diǎn)；另外p1和p8屬于軌跡的開始點(diǎn)和結(jié)束點(diǎn)，也要被視為關(guān)鍵點(diǎn)。因此，圖3中的關(guān)鍵點(diǎn)構(gòu)成的軌跡為TRkey=p1p4p6p8。

關(guān)鍵點(diǎn)的尋找應(yīng)該遵循兩個(gè)原則：精確度和簡(jiǎn)明性。精確度意味著原軌跡和它的關(guān)鍵點(diǎn)軌跡之間的差異應(yīng)該越小越好，體現(xiàn)著原軌跡運(yùn)動(dòng)軌跡的風(fēng)貌。簡(jiǎn)明性意味著關(guān)鍵點(diǎn)數(shù)量應(yīng)該越少越好，體現(xiàn)著軌跡挖掘和分析方法的運(yùn)行效率。精確度和簡(jiǎn)明性是相對(duì)的，如果一條軌跡中所有的點(diǎn)都視為關(guān)鍵點(diǎn)，那么精確度達(dá)到最高，簡(jiǎn)明性達(dá)到最低，軌跡挖掘和分析方法的運(yùn)行效率最低；如果只有開始點(diǎn)和結(jié)束點(diǎn)被視為關(guān)鍵點(diǎn)，那么簡(jiǎn)明性達(dá)到最高，而精確度達(dá)到最低，則很容易將兩個(gè)軌跡相差很大的移動(dòng)對(duì)象視為軌跡相似。因此本文尋找關(guān)鍵點(diǎn)時(shí)應(yīng)該在這兩個(gè)原則中達(dá)到平衡。

尋找關(guān)鍵點(diǎn)的具體規(guī)則如下：

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

(2)如果軌跡中運(yùn)動(dòng)方向變化值都未超出閾值λ，根據(jù)規(guī)則(1)，僅僅會(huì)得到兩個(gè)關(guān)鍵點(diǎn)：軌跡的開始點(diǎn)和結(jié)束點(diǎn)。如圖2所示：

圖2 示例軌跡TR

圖2中閾值λ設(shè)為30度，軌跡TR= p1p2p3p4p5p6p7p8，從p2到p7中，每個(gè)點(diǎn)的運(yùn)動(dòng)方向變化值都小于閾值λ，最終只有p1和p8是關(guān)鍵點(diǎn)，這樣就不能很好的反映出軌跡內(nèi)部的運(yùn)動(dòng)變化細(xì)節(jié)，因此本文規(guī)定如果從一個(gè)關(guān)鍵點(diǎn)開始，經(jīng)過η個(gè)點(diǎn)，仍未出現(xiàn)運(yùn)動(dòng)方向改變超出閾值λ的情況，那么將第η個(gè)點(diǎn)視為關(guān)鍵點(diǎn)，并依次類推。

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

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

3 時(shí)間分段

移動(dòng)對(duì)象的稀疏軌跡的軌跡點(diǎn)在時(shí)間維度上分布不均勻，有些軌跡點(diǎn)之間的時(shí)間間隔很短，而有些軌跡點(diǎn)之間的時(shí)間間隔很長(zhǎng)。為了提高尋找關(guān)鍵點(diǎn)的效率，如果將整個(gè)觀察時(shí)間分段成若干個(gè)時(shí)間子段，并同時(shí)在這些時(shí)間子段內(nèi)尋找關(guān)鍵點(diǎn)，這樣會(huì)大大提高尋找關(guān)鍵點(diǎn)的效率。

當(dāng)時(shí)間子段內(nèi)軌跡點(diǎn)數(shù)較少，為了使關(guān)鍵點(diǎn)軌跡體現(xiàn)原軌跡的運(yùn)動(dòng)風(fēng)貌，可以將該時(shí)間子段內(nèi)的每個(gè)軌跡點(diǎn)都視為關(guān)鍵點(diǎn)。當(dāng)時(shí)間子段內(nèi)軌跡點(diǎn)數(shù)較多時(shí)，為了加快尋找關(guān)鍵點(diǎn)的效率，可以在該時(shí)間子段內(nèi)利用 KP算法尋找關(guān)鍵點(diǎn)。因此本文給定閾值ε，當(dāng)時(shí)間子段內(nèi)的軌跡點(diǎn)大于ε時(shí)，就視為在該時(shí)間子段內(nèi)利用KP算法尋找關(guān)鍵點(diǎn)；否則將該時(shí)間子段內(nèi)的軌跡點(diǎn)都視為關(guān)鍵點(diǎn)。

接下來文中給出了時(shí)間分段的具體規(guī)則，如下：

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

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

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

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

4 稀疏軌跡相似性度量及其計(jì)算算法

定義編輯距離的關(guān)鍵是設(shè)置合理的代價(jià)值，即編輯操作應(yīng)付出相應(yīng)的代價(jià)值。代價(jià)值越小，兩軌跡相似性越高。在關(guān)鍵點(diǎn)和時(shí)間分段算法的基礎(chǔ)上，本文采用編輯距離來計(jì)算插入操作的代價(jià)、替換操作的代價(jià)和刪除操作的代價(jià)。

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

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

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

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

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

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

STS算法首先利用TS和KP算法尋找關(guān)鍵點(diǎn)(第1行)，然后根據(jù)公式(1)、(2)和(3)計(jì)算編輯代價(jià)。當(dāng)?shù)谝粭l軌跡的關(guān)鍵點(diǎn)軌跡長(zhǎng)度為0時(shí)，直接計(jì)算兩條軌跡間的插入操作代價(jià)(第2-3行)；當(dāng)?shù)诙l軌跡的關(guān)鍵點(diǎn)軌跡長(zhǎng)度為0時(shí)，直接計(jì)算兩條軌跡間的刪除操作代價(jià)(第4-6行)。再通過遞歸函數(shù)，根據(jù)公式(4)計(jì)算得出兩條軌跡間的編輯代價(jià)(第7-10行)。最后根據(jù)公式(5)，求得兩條軌跡間的相似性(第11行)。

5 實(shí)驗(yàn)

實(shí)驗(yàn)平臺(tái)是Windows 7，CPU 3.20GHz，內(nèi)存4GB。實(shí)驗(yàn)采用的是舊金山的出租車 GPS移動(dòng)軌跡數(shù)據(jù)[http://www.datatang.com/data/15731]，出租車數(shù)目為500輛，監(jiān)控時(shí)間是30天。該數(shù)據(jù)集中的出租車軌跡稠密度差異大，是一個(gè)典型的稀疏軌跡數(shù)據(jù)集，如表1所示：

表1 出租車GPS移動(dòng)軌跡數(shù)據(jù)

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

5.1 效率

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

圖3 STS和ERP算法在100輛出租車的GPS移動(dòng)軌跡數(shù)據(jù)集上的運(yùn)行

圖4 STS和ERP算法在200輛出租車的GPS移動(dòng)軌跡數(shù)據(jù)集上的運(yùn)行結(jié)果

圖5 STS和ERP算法在500輛出租車的GPS移動(dòng)軌跡數(shù)據(jù)集上的運(yùn)行結(jié)果

在圖3中STS算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間都小于ERP算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間。在圖4中STS算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間也都小于ERP算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間。在圖5中STS算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間也都小于ERP算法的最大運(yùn)行時(shí)間和最小運(yùn)行時(shí)間。

當(dāng)樣本中出租車輛數(shù)為100時(shí)，STS算法的最小運(yùn)行時(shí)間和最大運(yùn)行時(shí)間分別為1000ms和2000ms，ERP算法的最小運(yùn)行時(shí)間和最大運(yùn)行時(shí)間分別為8000ms和9000ms。當(dāng)出租車輛數(shù)增大時(shí)，STS算法的最小運(yùn)行時(shí)間和最小運(yùn)行時(shí)間增幅不大,始終低于10000ms；而ERP算法運(yùn)行時(shí)間增幅很大。這是因?yàn)?STS算法通過關(guān)鍵點(diǎn)的篩選，去除了不必要的計(jì)算開銷，而 ERP算法始終對(duì)原始軌跡點(diǎn)坐標(biāo)進(jìn)行計(jì)算，在不必要的軌跡點(diǎn)上花費(fèi)了大量的時(shí)間。STS算法的運(yùn)行速度相較ERP算法有很大的提高。

5.2 有效性

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

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

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

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

在對(duì)3個(gè)樣本數(shù)據(jù)集進(jìn)行聚類時(shí)，STS算法的聚類結(jié)果中的最大purity值和NMI值都大于ERP算法中的最大purity值和NMI值。同時(shí)STS算法的最小purity值和NMI值都大于ERP算法的最大purity值和NMI值。這是因?yàn)镾TS算法通過關(guān)鍵點(diǎn)的篩選，去除了噪聲軌跡點(diǎn)的干擾，故提高了聚類準(zhǔn)確率。ERP沒有去除噪聲軌跡點(diǎn)的干擾，所以聚類準(zhǔn)確率低。

6 總結(jié)

本文的主要目的是研究如何用編輯距離來計(jì)算稀疏軌跡之間的相似性。本文考慮到運(yùn)動(dòng)軌跡的主要特征在于人或物體運(yùn)動(dòng)方向的變化，提出的基于關(guān)鍵點(diǎn)和時(shí)間分段的稀疏軌跡相似性計(jì)算算法，提高了傳統(tǒng)的軌跡相似性方法分析稀疏軌跡相似性的運(yùn)行效率和準(zhǔn)確度。

[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]李備友.基于復(fù)雜網(wǎng)絡(luò)的證券市場(chǎng)傳聞擴(kuò)散與羊群行為演化研究[D].南京:南京航空航天大學(xué),2012:

[4]李策.基于軌跡分析的視覺目標(biāo)異常行為檢測(cè)算法研究[D].北京：中國(guó)科學(xué)院，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]楊澤雪,郝忠孝.空間數(shù)據(jù)庫(kù)中的組障礙最近鄰查詢研究[J].計(jì)算機(jī)研究與發(fā)展,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]袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[D].合肥：中國(guó)科技大學(xué),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.