陳 剛，錢 猛，劉 金

中國工程物理研究院 計(jì)算機(jī)應(yīng)用研究所，四川 綿陽 621900

基于劃分的高效異常軌跡檢測

陳 剛，錢 猛，劉 金

中國工程物理研究院 計(jì)算機(jī)應(yīng)用研究所，四川 綿陽 621900

1 引言

隨著多種移動(dòng)定位、傳感器網(wǎng)絡(luò)和無線通信技術(shù)的發(fā)展，人們可以收集和存儲(chǔ)越來越多的軌跡數(shù)據(jù)[1]，如何從這些數(shù)據(jù)中發(fā)現(xiàn)異常模式引起了許多研究人員的注意[2-4]。然而，現(xiàn)存的方法由于采用的軌跡描述方法和匹配（距離）函數(shù)的不同，導(dǎo)致挖掘算法在檢測結(jié)果和檢測效率方面存在諸多不同。

Knorr等人利用傳統(tǒng)的基于距離的異常挖掘方法檢測數(shù)據(jù)集中的異常軌跡[5-7]。由于該方法利用的都是軌跡的全局屬性，它忽略了軌跡間的局部差異，因此，該算法只能應(yīng)用于長度較短且較為簡單的軌跡。

Li等人提出了基于軌跡代表模式motifs的異常軌跡檢測算法[8]，它使用聚類方法從滑動(dòng)窗口中收集motif，然后用分類的思想過濾異常軌跡。該算法由于采用了分類的思想，因此在實(shí)際應(yīng)用中需要尋找較為標(biāo)準(zhǔn)的訓(xùn)練集。

J.-G Lee等人提出基于二階段劃分思想的異常軌跡處理算法TRAOD[9]，它首先將每條軌跡劃分為多個(gè)連續(xù)線段的組合，然后采用Hausdorff距離[10-12]來計(jì)算任意兩個(gè)線段之間的距離，從而挖掘出異常軌跡片段。TRAOD算法較好地解決了長軌跡間的匹配問題，但它同時(shí)存在以下幾個(gè)問題：首先，使用近似方法獲得的線段同樣會(huì)隱藏軌跡的部分局部特征；其次，Hausdorff距離這種度量方法并不符合歐式空間的標(biāo)準(zhǔn)，進(jìn)而無法使用傳統(tǒng)的索引方法來提高計(jì)算效率；再次，Hausdorff距離僅依賴于軌跡的形狀，軌跡的其他運(yùn)動(dòng)特征，例如運(yùn)動(dòng)方向和速度等，并沒有考慮進(jìn)匹配函數(shù)中。例如圖1所示的三條軌跡，假設(shè)其他軌跡的運(yùn)動(dòng)規(guī)律與T1類似，可以很容易發(fā)現(xiàn)，T2和T3都是異常軌跡，因?yàn)門2雖然運(yùn)動(dòng)速度與T1一致，但是運(yùn)動(dòng)方向不同，T3雖然運(yùn)動(dòng)方向一致，但是速度卻比其他軌跡要快，TRAOD算法在檢測這類異常軌跡時(shí)便有一定的難度。

圖1 軌跡的運(yùn)動(dòng)規(guī)律

針對上述問題，本文提出了基于劃分的異常軌跡檢測方法，它首先定義了一種新的異常軌跡判定方法，其次設(shè)計(jì)了一種索引結(jié)構(gòu)網(wǎng)格索引樹來提高挖掘效率，該結(jié)構(gòu)在時(shí)間和空間方面均優(yōu)于傳統(tǒng)的空間劃分方法，尤其是在維度的適用性方面有較大的提高。

2 異常軌跡的基本概念和描述

隨著探知技術(shù)和用戶需求的日益提高，軌跡數(shù)據(jù)集的屬性也在不斷地發(fā)生變化。首先，軌跡在時(shí)間和空間上的深度和廣度都得到擴(kuò)展，所獲取到的運(yùn)動(dòng)規(guī)律隨時(shí)間和空間的變化一直在變化。其次，用戶對挖掘算法的精度和效率也提出了越來越高的要求。針對這種現(xiàn)象，本文引入了軌跡局部異常點(diǎn)的概念，根據(jù)Apriori性質(zhì)[13-15]，如果某個(gè)軌跡片段不是異常的，那么組成該片段的軌跡點(diǎn)必然不是異常的，同樣，如果某個(gè)軌跡不是異常的，那么組成該軌跡的軌跡片段同樣不是異常的，從而將轉(zhuǎn)化為傳統(tǒng)的異常軌跡點(diǎn)檢測問題。為了將每個(gè)軌跡點(diǎn)異常度的計(jì)算限制在其周圍的局部鄰域內(nèi)，下面給出一些相關(guān)的概念和描述。

定義1（局部軌跡點(diǎn)）假設(shè)軌跡在兩個(gè)連續(xù)采樣點(diǎn)之間是均勻連續(xù)的，可以將軌跡視為無窮個(gè)軌跡點(diǎn)的集合，記為T=p1p2…pn，其中 pi(1＜j＜n)稱為局部軌跡點(diǎn)，記作 pj∈T。

定義2（軌跡瞬時(shí)矢量）假定軌跡的屬性集為A= {A1，A2，…，Ad}，d為屬性維度，在一個(gè)采樣時(shí)刻t，軌跡Ti對應(yīng)的軌跡點(diǎn)為 pj，該時(shí)刻軌跡的屬性值為 Aj= {a1，a2，…，ad}，其中ak(1≤k≤d)為Ak的瞬時(shí)值，可以將Aj視作軌跡點(diǎn) pj的瞬時(shí)矢量，記作 pvj={a1，a2，…，ad}。

定義3（軌跡局部距離）軌跡點(diǎn)m∈Ti，n∈Tj，m和n的瞬時(shí)矢量分別是 Am，k和 An，k，其中1≤k≤d，則m與n之間的距離為：

其中wk≥0是用戶給定的維度權(quán)值參數(shù)。

定義4（核心軌跡點(diǎn)）設(shè)trω-set(p)表示 p軌跡點(diǎn)ω-鄰域內(nèi)包含的軌跡對象，trω-set(p)={T|o∈T∧o∈pω-set}，給定參數(shù)Minpts，若|trω-set(p)|＞Minpts，則稱 p為核心軌跡點(diǎn)。

定義5（局部異常軌跡點(diǎn)）給定軌跡數(shù)據(jù)集，對應(yīng)的軌跡點(diǎn)集合為P，o∈P，o不被包含在P的任何一個(gè)核心軌跡點(diǎn)的ω-鄰域內(nèi)，且|trω-set(o)|≤Minpts，則稱o為局部異常軌跡點(diǎn)。

定理1軌跡點(diǎn)m為異常軌跡點(diǎn)的充要條件是m是非核心軌跡點(diǎn)，并且m的ω-鄰域（以m為圓心，半徑為ω的區(qū)域）與核心軌跡點(diǎn)集不存在交集。

證明（充分性）由于m是異常軌跡點(diǎn)，根據(jù)定義可知，|trω-set(m)|≤Minpts且m位于所有核心軌跡點(diǎn)的ω-鄰域之外。因此m即為非核心軌跡點(diǎn)，其ω-鄰域與核心軌跡點(diǎn)集也不存在交集。

（必要性）如果m為非核心軌跡點(diǎn)，那么|trω-set(m)|≤Minpts，又因m的ω-鄰域與核心軌跡點(diǎn)集沒有交集，即m不被包含在任何核心軌跡點(diǎn)的ω-鄰域內(nèi)。根據(jù)定義可知，m為異常軌跡點(diǎn)。

定義6（異常軌跡片段）給定閾值δ，軌跡片段Lk= pipi+1…pj（i＜j≤N，N為軌跡點(diǎn)個(gè)數(shù)）為異常軌跡片段，當(dāng)且僅當(dāng)滿足：

其中O(Lk)是軌跡片段的異常軌跡點(diǎn)集，Nl是軌跡片段的軌跡點(diǎn)集。

定義7（軌跡異常度）一條軌跡T的異常度TOF（Trajectory Outlier Factor）為異常軌跡片段在整條軌跡長度中的比例，即O(T)為軌跡T的異常片段集合。

圖2中有四條軌跡，P1，P2，P3是軌跡T3上的三個(gè)軌跡點(diǎn)，可以發(fā)現(xiàn)，無論是空間位置，還是速度方向，這三個(gè)點(diǎn)都是異常軌跡點(diǎn)。它們組成異常軌跡片段L1和L2，如果L1和L2的長度和占T3的比例超過一定閾值，則T3就是異常軌跡。

圖2 異常軌跡點(diǎn)示例

在現(xiàn)實(shí)的軌跡采集中，由于采樣頻率和移動(dòng)物體運(yùn)動(dòng)速度的不同，導(dǎo)致軌跡在軌跡點(diǎn)的疏密程度上有差異，因此會(huì)造成一定的計(jì)算誤差，所以在實(shí)際操作中要對軌跡進(jìn)行基于距離的線性插值。

3 異常軌跡檢測的樸素算法

假設(shè)給定軌跡數(shù)據(jù)集TS={Ti|1≤i≤n}，樸素算法的基本思想就是通過將每條軌跡上的軌跡點(diǎn)逐一與其他軌跡點(diǎn)進(jìn)行比較來找出異常軌跡點(diǎn)，然后再根據(jù)定義來判斷異常軌跡。圖3給出了樸素算法的偽代碼。

圖3 異常軌跡檢測的樸素算法

下面以距離計(jì)算為基本單元分析一下樸素算法的計(jì)算復(fù)雜度。給定一條軌跡Ti，包含ti個(gè)軌跡點(diǎn)，那么對于兩條軌跡Ti和Tj，需要計(jì)算距離的次數(shù)為ti×tj，假定兩個(gè)軌跡點(diǎn)之間的距離計(jì)算復(fù)雜度為u，則軌跡Ti和Tj之間的匹配復(fù)雜度為：

由于軌跡數(shù)量眾多，因此樸素算法的計(jì)算復(fù)雜度為：

設(shè)每條軌跡具有相同數(shù)量的軌跡點(diǎn)，即ti=tj=t，那么樸素算法的計(jì)算復(fù)雜度為：

4 基于劃分的異常軌跡檢測

在搜索軌跡點(diǎn)的鄰近點(diǎn)個(gè)數(shù)時(shí)，為了避免全局空間的搜索，本文使用空間劃分的方法將數(shù)據(jù)的搜索區(qū)域劃分為若干不重疊的超矩形單元，將異常點(diǎn)的檢測限制在局部空間內(nèi)。與傳統(tǒng)的空間劃分不同的是，為了提高檢索效率和保持網(wǎng)格的位置關(guān)系，本文設(shè)計(jì)了一種網(wǎng)格索引結(jié)構(gòu)，只存儲(chǔ)非空網(wǎng)格，同時(shí)保持網(wǎng)格間的鄰近關(guān)系，使得最近鄰搜索更加高效地完成。

4.1 網(wǎng)格索引樹（Grid Index Tree）

假設(shè)G={G1，G2，…，Gk}是一個(gè)k維的有序域集合，數(shù)據(jù)集 X={x1，x2，…，xN}表示 N個(gè)點(diǎn)的集合，X的取值范圍被G完全覆蓋，稱G為X的覆蓋集?，F(xiàn)將數(shù)據(jù)集 X的覆蓋集G的每一個(gè)維度劃分為m個(gè)相等的單元，從而將空間劃分為超矩形單元集合P。每個(gè)單元C的空間位置表示為{c1，c2，…，cd}，其中，ci為大于或等于0的整數(shù)，d為數(shù)據(jù)維度數(shù)目。

k維覆蓋集劃分后的單元數(shù)為md，當(dāng)覆蓋集的每個(gè)維度跨度很大時(shí)將導(dǎo)致m較大，且維度個(gè)數(shù)d也較大時(shí)，也會(huì)導(dǎo)致單元數(shù)量的龐大。在實(shí)際中，劃分后會(huì)有大量的空單元產(chǎn)生，為此，設(shè)計(jì)了網(wǎng)格索引樹，只索引非空單元。

定義8（網(wǎng)格索引樹GI-Tree）

覆蓋集G劃分后生成的GI-Tree結(jié)構(gòu)定義如下：

（1）GI-Tree共有d+1層，其中d是G的基數(shù)。

（2）除d+1層外，GI-Tree的每一層對應(yīng)G的一個(gè)維度，從第1層到第d層的維度排序遵循事先約定的順序。

（3）第i層(i≠d+1)中的每個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)部節(jié)點(diǎn)是升冪排序的，記錄格式為（cNO，NextPointer），其中cNO是該單元在第i維上的序列號，NextPointer為下一層指針；如果i=d+1，則節(jié)點(diǎn)記錄格式為（cNO，NextPointer，lk），NextPointer指向葉節(jié)點(diǎn)，lk為單鏈表，保存落入該單元的數(shù)據(jù)對象。

（4）從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑唯一約束一個(gè)單元。

圖4（a）是一個(gè)三維的劃分立方體，每個(gè)維度等分為4個(gè)單元，藍(lán)色單元表示有存儲(chǔ)數(shù)據(jù)。圖4（b）為對應(yīng)的GI-Tree，前三層分別對應(yīng)數(shù)據(jù)三個(gè)維度（約定的維度順序?yàn)閄→Y→Z），最后一層為數(shù)據(jù)存儲(chǔ)層。X維分為4段，但只有1，2，4非空，所以GI-Tree的第一層節(jié)點(diǎn)有3個(gè)內(nèi)部節(jié)點(diǎn)，以此類推。

圖4 GI-Tree實(shí)例

GI-Tree的優(yōu)勢如下：

（1）GI-Tree可以有效地保持?jǐn)?shù)據(jù)的鄰近關(guān)系，在原始劃分中相鄰的兩個(gè)單元，在GI-Tree中也是鄰近的，這有利于實(shí)現(xiàn)數(shù)據(jù)的高效鄰域檢索，提高整個(gè)算法的效率。

（2）GI-Tree只索引非空單元，這對于軌跡數(shù)據(jù)尤為重要。軌跡數(shù)據(jù)的一些維度，例如空間位置，其空間跨度很大，而且移動(dòng)對象一般呈現(xiàn)出群體行為，這導(dǎo)致在軌跡數(shù)據(jù)的劃分中空單元的數(shù)量遠(yuǎn)遠(yuǎn)大于非空單元的數(shù)量。

4.2 GI-Tree索引的維護(hù)算法

下面介紹GI-Tree的構(gòu)建和范圍查詢算法。

4.2.1 GI-Tree的構(gòu)建算法

構(gòu)建GI-Tree的過程是依次將數(shù)據(jù)集中的各個(gè)點(diǎn)插入到樹中。子程序InsertPoint以約定的維度順序?qū)?shù)據(jù)對象在各個(gè)維度上的單元在樹中查找相應(yīng)的路徑，如果該路徑已經(jīng)存在，將對象插入葉節(jié)點(diǎn)的單鏈表中，否則，從當(dāng)前一層創(chuàng)建以下各層的節(jié)點(diǎn)。GI-Tree創(chuàng)建算法如圖5所示。

圖5 GI-Tree創(chuàng)建算法

4.2.2 GI-Tree的范圍查詢

在空間網(wǎng)格中，點(diǎn)p的k近鄰是這樣一個(gè)集合，它包含了以p為中心，以k為厚度的超矩形體內(nèi)的所有單元。如圖6所示，點(diǎn)p的1-鄰域是指包圍目標(biāo)立方體且厚度為1單元塊，包括8個(gè)灰色單元。

圖6 k近鄰查詢

基于GI-Tree的范圍查詢算法如圖7所示。

圖7 范圍查詢算法

4.3 異常軌跡檢測算法

4.3.1 基于GI-Tree的異常軌跡點(diǎn)檢測算法

算法4是本文提出的基于GI-Tree的異常軌跡點(diǎn)檢測算法。首先計(jì)算經(jīng)過每個(gè)單元的軌跡數(shù)目，如果大于閾值Minpts則將其標(biāo)記為red，表明該單元中的軌跡點(diǎn)都不是異常的，否則標(biāo)記為white。然后針對white單元中的每個(gè)軌跡點(diǎn)，根據(jù)定義5和算法4判斷是否異常。異常軌跡點(diǎn)檢測算法如圖8所示。

圖8 異常軌跡點(diǎn)檢測算法

4.3.2 異常軌跡檢測算法

算法5給出了異常軌跡檢測的完整算法，該算法首先對軌跡數(shù)據(jù)庫做基于距離的線性插值（步驟1），然后構(gòu)建GI-Tree（步驟2），在檢測出異常軌跡點(diǎn)后，根據(jù)定義計(jì)算軌跡的異常度（步驟3），最后輸出異常軌跡（步驟4）。異常軌跡檢測算法如圖9所示。

圖9 異常軌跡檢測算法

4.3.3 性能分析

在空間復(fù)雜度方面，設(shè)每個(gè)空間劃分單元的存儲(chǔ)代價(jià)為c，每個(gè)維度均勻劃分為m個(gè)單元，則GI-Tree索引的單元數(shù)為(1-s)×md，其中s表示軌跡點(diǎn)集在空間的分布情況，分布均勻時(shí)，s趨近于0，分布越不均勻，s就越趨近于1。在真實(shí)的軌跡數(shù)據(jù)集中，軌跡點(diǎn)的分布往往是不均勻的，所以(1-s)×md＜＜md，即該算法的空間復(fù)雜度SC＜＜md×c。

在時(shí)間復(fù)雜度方面，步驟1的時(shí)間復(fù)雜度為O(nu)，nu為線性插入的軌跡點(diǎn)個(gè)數(shù)。步驟2是建立網(wǎng)格索引樹，假定軌跡點(diǎn)均勻分布，d個(gè)維度共劃分為md個(gè)單元，則建立的GI-Tree共有d+1層，每個(gè)非葉節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)為m個(gè)。由于內(nèi)部節(jié)點(diǎn)是排序的，因此每插入一個(gè)軌跡點(diǎn)，每層都需要進(jìn)行l(wèi)bm次比較，即一次完整的插入過程需要比較d×lbm次。所以，n條軌跡的建樹過程需要n×d×lbm次比較。在步驟3中僅考慮GI-Tree的搜索和計(jì)算代價(jià)，GI-Tree的每層內(nèi)部查找為二分查找，因此一次查找花費(fèi)O(dlbm)，計(jì)算代價(jià)與ω和d成正比，即O(ωd)。設(shè)有n條軌跡，平均每條軌跡中有t個(gè)軌跡點(diǎn)，則步驟3的計(jì)算復(fù)雜度為O(dωdlbm×n×t)。

5 實(shí)驗(yàn)結(jié)果

這一章對本文提出的異常檢測算法在有效性和性能方面進(jìn)行測試。本章的全部實(shí)驗(yàn)所使用的數(shù)據(jù)來自于1849年至2006年大西洋颶風(fēng)中心運(yùn)動(dòng)軌跡（http：// weather.unisys.com/hurricane/index.html），維度信息包括經(jīng)緯度、最大風(fēng)力、壓力等。本文采用的數(shù)據(jù)為：（1）數(shù)據(jù)1，1849年到2006年的軌跡，包含20 371個(gè)軌跡點(diǎn)，1 278條軌跡；（2）數(shù)據(jù)2，1950年到2006年的軌跡，包含19 581個(gè)軌跡點(diǎn)，608條軌跡；（3）數(shù)據(jù)3，1990年到2006年的軌跡，包含7 301個(gè)軌跡點(diǎn)，224條軌跡，維度信息采用了經(jīng)緯度、風(fēng)力和速度矢量共5維。

實(shí)驗(yàn)環(huán)境：Windows XP操作系統(tǒng)，Intel Pentinum Dual 2.8 GHz CPU，2 GB內(nèi)存。開發(fā)環(huán)境：Microsoft Visual Studio 2005。

5.1 算法的效果分析

為了驗(yàn)證算法的效果，本文以TRAOD算法作為比較算法，實(shí)驗(yàn)數(shù)據(jù)采用數(shù)據(jù)2和3。從圖10（a）和（b）中可以發(fā)現(xiàn)，TRAOD算法能夠發(fā)現(xiàn)軌跡稀疏區(qū)域的異常軌跡和擁有異常移動(dòng)路徑的軌跡，也就是說，TRAOD的結(jié)果只依賴于軌跡的形狀。

圖10 與TRAOD算法的檢測效果對比

圖10（c）和（d）顯示了本文提出的算法在同樣兩個(gè)數(shù)據(jù)集中檢測出的異常軌跡的情況(ω=26，δ=0.7，Minpts=10)，從結(jié)果中可以很容易發(fā)現(xiàn)，除了TRAOD能夠檢測出的那些具有異常形狀的軌跡外，本文的算法還能夠檢測那些擁有更快的移動(dòng)速度的異常軌跡（圖中圓圈標(biāo)示），而在TRAOD算法中，這些異常軌跡的路徑由于與其他軌跡路徑相似而被認(rèn)為是正常軌跡。因此，本文提出的異常軌跡判定算法要比TRAOD更加具有現(xiàn)實(shí)意義。

5.2 參數(shù)影響

本文算法主要涉及到如下參數(shù)：ω，Minpts。下面以數(shù)據(jù)3作為實(shí)驗(yàn)數(shù)據(jù)來測試算法，分析不同參數(shù)對實(shí)驗(yàn)結(jié)果的影響。

鄰域半徑ω對算法的影響最大，不但直接決定了算法的計(jì)算代價(jià)，而且較為明顯地影響算法檢測出的異常軌跡的數(shù)目。從圖11可以發(fā)現(xiàn)，隨著ω的增大，異常軌跡的數(shù)目在逐漸減少，這是因?yàn)椋害刂翟酱螅惴ㄐ枰诟蠓秶鷥?nèi)查詢與對象軌跡運(yùn)動(dòng)規(guī)律不相匹配的軌跡，有些軌跡盡管在其較近鄰域具有特殊的運(yùn)動(dòng)規(guī)律，但查詢范圍增大卻和較遠(yuǎn)區(qū)域的軌跡具有相似的運(yùn)動(dòng)規(guī)律。同時(shí)可以看出，ω值越大，算法的執(zhí)行時(shí)間就越長。因此，為ω設(shè)定一個(gè)合理值不僅有助于提高計(jì)算效率，而且對算法的檢測效果也有較大提高。

圖11 不同參數(shù)下算法的執(zhí)行時(shí)間和檢測效果對比

參數(shù)Minpts表示軌跡的局部匹配的精度，從圖11可以看出，當(dāng)Minpts增大時(shí)，算法檢測出來的異常軌跡數(shù)目在減少，這是因?yàn)镸inpts增大表明算法對異常的容忍度在增加，Minpts越大，異常軌跡的數(shù)目就越少。

從表1中可以發(fā)現(xiàn)，本文所提出的算法在計(jì)算效率方面遠(yuǎn)遠(yuǎn)超過TRAOD算法，雖然TRAOD算法采用了粗細(xì)結(jié)合的分段方法來減少鄰域軌跡段的個(gè)數(shù)，但由于不能夠索引軌跡段，算法的計(jì)算復(fù)雜度非常大。同時(shí)，TRAOD算法采用的度量方法也增加了計(jì)算代價(jià)。

表1 算法執(zhí)行效率的對比

圖12 內(nèi)存使用情況

為了測試算法的空間復(fù)雜度，本文分別使用500條軌跡和200條軌跡，分別測試使用傳統(tǒng)網(wǎng)格劃分和使用網(wǎng)格索引樹算法的最大內(nèi)存占用情況。從圖12中可以發(fā)現(xiàn)，隨著網(wǎng)格單元數(shù)目的增加，內(nèi)存的占用呈線性增長的趨勢，但是采用網(wǎng)格索引樹時(shí)，內(nèi)存使用增長率遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的網(wǎng)格劃分方法，主要原因是網(wǎng)格索引樹只索引非空網(wǎng)格單元，從而大大降低了內(nèi)存占用量。

6 結(jié)束語

隨著無線傳感技術(shù)和定位服務(wù)的發(fā)展，挖掘軌跡數(shù)據(jù)庫中蘊(yùn)含的異常信息已經(jīng)成為當(dāng)前的研究熱點(diǎn)。本文針對軌跡數(shù)據(jù)的運(yùn)動(dòng)規(guī)律和特征，結(jié)合空間劃分的方法，提出了一種基于網(wǎng)格索引的異常軌跡檢測方法。實(shí)驗(yàn)結(jié)果表明本文提出的算法不僅提高了異常軌跡的挖掘效率，而且能夠挖掘出更富現(xiàn)實(shí)意義的異常軌跡。

本文提出的算法同樣遇到了參數(shù)敏感的問題，需要領(lǐng)域?qū)＜业膮⑴c或多次嘗試才能確定合適的參數(shù)值。同時(shí)，本文的算法目前只能適用于靜態(tài)歷史軌跡數(shù)據(jù)庫，因此，本文的后續(xù)工作包括研究自適應(yīng)參數(shù)和研究從軌跡流中即時(shí)發(fā)現(xiàn)異常軌跡的算法。

[1]Guting G H，Schneider M.Moving objects databases[M]. [S.l.]：Morgan Kaufmann，2005：217-224.

[2]Bu Y，Chen L.Efficient anomaly monitoring over moving object trajectory streams[C]//SIGKDD，Rhode Island，USA，2009：159-168.

[3]Li X，Li Z，Han J，et al.Temporal outlier detection in vehicle traffic data[C]//Proceedings of ICDE，2009：1319-1322.

[4]Ge Y，Xiong H，Zhou Z H，et al.Top-eye：top-k evolving trajectory outlier detection[C]//Proceedings of CIKM，2010：1733-1736.

[5]Knorr E M，Ng R T.Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of 24th VLDB，New York City，1998：392-403.

[6]Knorr E M，Ng R T.Finding intensions knowledge of distance-based outliers[C]//Proceedings of 25th VLDB，Edinburgh，Scotland，1999：211-222.

[7]Knorr E M，Ng R T，Tucakov V.Distance-based outlier：algorithms and applications[J].VLDB Journal，2000，8（3）：237-253.

[8]Li X，Han J，Kim S，et al.ROAM：rule and motif-based anomaly detection in massive moving object data sets[C]// Proceedings of 7th SIAM International Conference on Data Mining，Minneapolis，Minnesota，2007：296-307.

[9]Lee J G，Han J，Li X.Trajectory outlier detection：a partition-and-detect framework[C]//Proceedings of ICDE，2008.

[10]Lee J G，Han J，Whang K Y.Trajectory clustering：a partition-and-group framework[C]//Proceedings of ACM SIGMOD，Beijing，China，2007：593-604.

[11]Chen J，Leung M K H，Gao Y.Noisy logo recognition using line segment Hausdorff distance[J].Pattern Recognition，2003，36（4）：943-955.

[12]Lee J G，Han J，Li X，et al.TraClass：trajectory classification using hierarchical region-based and trajectory-based clustering[C]//Proceedings of PVLDB，2008.

[13]Agrawal R，Srikant R.Fast algorithm for mining association rules[C]//Proceedings of the 20th International Conference on VLDB，Santiago，Chile，1994：487-499.

[14]Agrawal R，Srikant A R.Mining sequential patterns[C]// Proceedings of ICDE，1995：3-14.

[15]Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[R].School of Computing Science，Simon Fraser University，1999.

CHEN Gang,QIAN Meng,LIU Jin

Institute of Computer Application,China Academy of Engineering Physics,Mianyang,Sichuan 621900,China

As the development of mobile computing technology and GPS-enabled mobile devices,the services of moving object receive more and more attention.And trajectory outlier detection is a widely appealing application.In this paper,a novel detection algorithm is proposed to mine trajectory outliers from massive trajectory datasets more efficiently.The algorithm is based on space partition and finds trajectory outliers through mining the local trajectory point outlier.In this way, it converts the problem of finding trajectory to traditional outlier detection problem.In addition,a novel index structure is designed to improve the computing efficiency.Experiments show its higher efficiency and its power to find more meaningful trajectory outlier.

trajectory outlier;trajectory point;space partition;grid index tree

為了在海量軌跡數(shù)據(jù)庫中高效準(zhǔn)確地挖掘出異常軌跡，提出了基于劃分的異常軌跡檢測算法。該算法通過計(jì)算局部軌跡點(diǎn)之間的匹配程度來探測異常軌跡，將異常軌跡檢測由形狀匹配問題轉(zhuǎn)化為傳統(tǒng)的異常點(diǎn)檢測問題，并設(shè)計(jì)了一種基于空間劃分的網(wǎng)格索引結(jié)構(gòu)，提高算法的運(yùn)行效率。實(shí)驗(yàn)證明，該算法不僅具有較高的挖掘效率，而且能夠檢測出更具實(shí)際意義的異常軌跡。

異常軌跡；軌跡點(diǎn)；空間劃分；網(wǎng)格索引樹

A

TP393

10.3778/j.issn.1002-8331.1301-0243

CHEN Gang,QIAN Meng,LIU Jin.Trajectory outlier detection based on space partition.Computer Engineering and Applications,2014,50（24）：127-132.

國家自然科學(xué)基金（No.60728204/F020404）；科技重大專項(xiàng)經(jīng)費(fèi)資助（No.2013ZX04006011-102-002）。

陳剛（1984—），男，助理工程師，主要研究方向：信息可視化、數(shù)據(jù)挖掘、自動(dòng)化控制；錢猛（1988—），男，助理工程師，主要研究方向：數(shù)據(jù)庫、網(wǎng)絡(luò)化控制系統(tǒng)；劉金（1974—），男，研究員，碩士生導(dǎo)師，主要研究方向：系統(tǒng)工程、自動(dòng)化控制系統(tǒng)、武器預(yù)研等。E-mail：zjucg@zju.edu.cn

2013-01-22

2013-04-22

1002-8331（2014）24-0127-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-05-13，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130513.1601.004.html