軌跡數據的多特征融合及檢測方法

饒元淇，趙旭俊，蔡江輝

(太原科技大學 計算機科學與技術學院，太原 030024)

1 引 言

在如今智能化時代，隨著定位設備、Wi-Fi網絡、視頻監控、以及無線傳感器等設備的發展，產生越來越多的軌跡數據[1].同時，這些數據中又包含了大量的信息，在無人駕駛、導航系統、智能化的交通系統等領域有關軌跡數據的研究需求不斷日益增長.傳統的檢測方法將軌跡視為一維序列，并在單一尺度下進行處理，無法挖掘不同特征尺度下豐富多樣的信息[1].由于軌跡數據中隱藏著一系列影響用戶出行行為的復雜特征，因此挖掘軌跡仍然具有一定的挑戰性[2,3].例如，在氣象臺臺風檢測，可以探測到臺風路徑的變化，通過提前預測軌跡路徑.對于可能造成的損失提前做好防護措施，以減少損失；在“網約車”軟件使用過程中，系統檢測到車輛異常軌跡時，對乘客發出安全性預警等，可以有效避免危險的發生.因此，在大規模軌跡數據集中挖掘軌跡具有很重要的現實意義和實用價值.如何從大規模的軌跡數據中挖掘出有用的知識，并且有效的發現許多隱藏在數據信息中的有價值的軌跡數據越來越受到人們的關注.

傳統的軌跡檢測方法是將軌跡數據進行切分為子段，綜合考慮軌跡子段的比例和軌跡子段的密度，確定軌跡數據的劃分[4-6].研究將軌跡數據直接以整條軌跡數據作為基本單元的軌跡檢測的算法相對較少.因此，本文設計了一種基于圖劃分的軌跡聚類方法，首先使用核函數可以將軌跡數據映射到高維空間，使得數據線性可分[7].然后，通過構建軌跡數據無向加權圖，使用核函數度量圖中節點之間的相似度，通過譜聚類進行圖劃分得到的子圖.最后，將軌跡數據劃分到不同的類.由于軌跡數據存在更多的不確定性的形狀，因此，采用譜聚類會得到更好的檢測效果.

2 相關工作

軌跡數據檢測技術可以分為監督、半監督、和非監督，主要包括的方法有基于分類的方法、基于聚類的方法、基于密度的方法、基于統計的方法等.

2.1 基于距離的軌跡檢測方法

Knorr[8]等提出了基于距離的軌跡異常檢測的概念,屬于最早的軌跡異常數據檢測研究.他將每個軌跡轉轉換一個組合的對象，組合的對象由4個關鍵的特征組成：位置、長度、方向和速度.然后采用傳統的基于距離的異常點檢測方法來發現異常軌跡.該方法的不足之處在于，其誤差在整個軌跡平均之后，可能無法檢測出異常子軌跡.為了克服這一問題，Lee[9]等人提出了一種分段檢測框架，并且在這個框架的基礎上提出了一種異常軌跡檢測的方法TRAOD.TRAOD包括兩個階段：1)劃分階段;2)檢測階段.首先對于軌跡進行粗粒度劃分，然后對軌跡進行細粒度劃分.在檢測階段，采用基于距離的檢測方法檢測邊遠的軌跡片段.采用模式識別中的Hausdorff距離[10]來測量兩個分段之間的距離.TRAOD中沒有消除子軌跡之間的共同偏差.Liu[11]等提出一種新的距離函數，該函數有最小的Hausdorff距離推導而來.該距離函數以數量為k的連續點作為基本單元計算軌跡的局部異常點.基于局部異常點來檢測兩種軌跡是否具有全局相似性.當目標軌跡沒有足夠的相似軌跡時，將被視為異常軌跡.同時，為了提高算法性能引入R樹.為了解決靜態數據序列沒有考慮有價值的特征問題，Yuan[12]等人提出了一種基于結構相似的軌跡異常檢測算法(TOD-SS).TOD-SS考慮了更多的軌跡特征，每個特征的重要性可以根據權重進行調整.結構相似性不僅能更好地反應內部和外部特征的差異，而且還能增強分析效果.

2.2 基于密度的軌跡檢測方法

為了克服距離方法在處理復雜分布特征數據集的方面存在不足，Liu等[13]提出了基于密度的軌跡異常檢測方法DBTOD.DBTOD利用TRAOD引入了考慮鄰域對象分布的軌跡密度概念.軌跡密度由兩部分組成：子軌跡之間的距離和給定范圍內子軌跡的數量.DBTOD算法充分利用了分區檢測框架，由劃分階段和檢測階段組成.使用與TRAOD相同的軌跡劃分算法，將每個軌跡劃分成一組t分段，然后用基于密度的檢測算法代替基于距離的檢測算法來發現異常自軌跡.與基于距離的算法相比，該方法不僅能夠檢測異常軌跡數據和異常局部軌跡數據，還克服了基于距離的方法中參數敏感的問題.為了加快軌跡異常點檢測的速度，劉等提出了用R-Tree數據結構來存儲軌跡數據.

2.3 基于分類的軌跡檢測方法

王[14]等提出了以運動方向為主導的軌跡相似性度量方法，運用聚類方法來分析軌跡數據.Li等人[15]提出了一種基于分類的軌跡異常檢測算法Roam.該方法中常用的模式使用基序來表示軌跡.該框架由3個部分組成：1)基于單元的特征空間.將軌跡劃分為基序，并在基序上構造一個具有相關屬性的多維特征空間；2)自動提取層次結構.通過研究軌跡中的模式，得到特征空間中的層次結構；3)基于規則的分級分類器.基于規則的分級分類器可以對特征空間分層探索，找到有效的分類區域.Lee[16]使用基于層次聚類的方法分類軌跡數據.

綜上所述，在傳統的融合度量軌跡的檢測算法是針對于數據位置信息的處理，僅僅在單一特征上評測軌跡的相似度，忽略了軌跡信息中的其他包含特征信息.對于交通軌跡的大數據的挖掘[17]忽略了速度信息等在內的其他特征.不同的觀測對象感興趣的軌跡特征也不盡相同.例如，在同一路段車輛軌跡位置信息相同，如果有遠高于其他車輛軌跡的數據，有可能存在車輛超速或者緊急事件(消防車輛、救護車輛等).如果僅從位置信息一個特征上度量不能檢測出此類信息.

基于上面描述的局限性，本文提出軌跡融合度量檢測算法Trajectory Detection Based on Multi Feature Fusion(TD-MFF)，主要分為3個部分：1)運用相應核函數方法分別在軌跡的空間特征、速度特征和時間特征3個特征上對軌跡數據進行相似性度量；2)設計了一個融合多特征的核函數方法得到融合特征的相似性度量；3)通過譜聚類對圖模型進行劃分子圖，最后在子圖中搜索數據.最后，設計了一種異常軌跡的檢測方法.

3 多特征融合的軌跡數據度量及檢測

軌跡數據包含有不同特征信息，取任意兩條數據，在不同特征描述下的相似度有所不同.針對這種在相同數據集中取不同特征情況下會產生不同的度量結果的問題，本文將軌跡數據抽象為無向圖，其中每條數據用圖中一個節點表示，用節點間的權值來表示軌跡數據間的相似度度量.在軌跡相似性度量過程中，直接度量整段軌跡數據相似度會產生：位置特征數據不能對齊計算，速度特征數據不能處理軌跡數據中速度信息包含的軌跡位置等問題.核函數是將數據樣本空間映射到高維特征空間[18]，由于經過了核函數的映射,使原來沒有顯現的特征突現出來.

軌跡數據往往包含有不同的特征屬性，不同特征屬性的度量方式不能統一.例如：對于位置特征屬性，由于不同的軌跡數據中包含點的數量不同，因此，我們需要通過對數據的拉伸或者伸縮目的是使得數據對齊；對于速度特征屬性，我們需要考慮軌跡的速度信息帶有位置屬性，我們需要比較在不同位置的速度大小和方向.因此，不同的特征使用不同的核函數來度量.

由于軌跡數據被映射到高維空間通過核函數，我們很難判別映射后數據的分布情況.傳統的聚類算法，例如K-means，很難適應這種現象.這里，我們采用譜聚類的方法.與傳統的比較算法相比，通過特征融合度量后結合譜聚類的方法可以更好的辨別、提取并放大有用的特征，正確的聚類結果即使傳統聚類算法不能得到很好的結果的情況下.

3.1 特征融合軌跡描述及特征信息建模

本文將軌跡數據抽象成為圖中節點，軌跡數據形式化描述如下：

定義 1.定義一個軌跡數據X={x1,…,xk,…,xn,}T.其中，軌跡數據元素xk是由nk連續的點構成的元素，nk={sk,vk,ek}，sk表示位置特征信息，vk表示速度特征信息，ek表示時間戳的信息.

定義 2.給定N條軌跡數據，定義軌跡數據圖為G，令N為圖G的節點數量.其中，一個節點代表一條軌跡數據.軌跡數據圖G是一個無向連通圖，由G=(V,E,ω)表示.其中：

V={v1,v2,…,vn}是節點構成的集合表示N條軌跡數據；

E={e1,e2,…,en}是節點之間邊的集合；

ω={ω1,ω2,…,ωn}是節點之間的邊的權值表示兩條軌跡的相似度.

軌跡數據圖G中節點之間的相似度ω是通過多個信息屬性度量后加權求和得到的融合了多個測量信息的權值.本文使用加權組合相似矩陣K(xk,xk′)來計算軌跡數據間的相似性，構造出相似矩陣K，我們令ω=K得出節點之間的相似度.每個元素K(xk,xk′)表示圖中兩個節點的相似度.本文定義K(xk,xk′):

(1)

其中，K(xk,xk)=1，k=1,2,…,N,K(xk,xk)=1表示一條軌跡與其自身的相似性最大，αm表示預先分配的權重.用來反映人們對于第m維的特征的感興趣程度.

空間位置特征相似度量.在處理兩條軌跡的位置信息時候，每條軌跡的位置信息隨著時間的變化，因此，軌跡數據采取的信息通常存在數據點數量不同情況，在比較相似的過程中，必然出現不同數量的位置點進行匹配的情況.為了解決軌跡位置信息在度量過程中出現的這種不匹配的情況，the Global Alignment Kernel(GAK)[19]利用動態規劃時間序列(DTW)思想構造核函數.但是，DTW算法復雜度高，需要遍歷整個搜索范圍.為了解決這一問題，本文搜索路徑時增加了路徑約束提高計算效率.如圖1中所示，白色區域即為約簡的空間，減少了尋找路徑時候的搜索空間.

圖1 粗粒度和細粒度Fig.1 Coarse-grained and fine-grained

cx(π1(i))和cy(π2(j))表示軌跡π1(i)和π2(j)的二維空間坐標.為了解決計算兩段序列相似度存在序列長度不同的問題，采用了快速DTW思想：1)軌跡像素粗粒度化.從矩陣的左下角到右上角計算最短的歐式距離ei,j=‖π1(i)-π2(j)‖2確定路徑di,j.公式(2)展示了計算最短路徑的方法：從目標位置的右di-1,j、上di,j-1和斜對角向上di-1,j-1三個方向進行前進搜索，取三個方向之中的最小值.

di,j=eij+min(di-1,j,di,j-1,di-1,j-1)

(2)

其中，di,j表示當前需要計算的路徑距離，eij表示當前兩個位置點之間的歐式距離，min(di-1,j,di,j-1,di-1,j-1)表示從開始位置到該位置的最短距離.2)軌跡像素細粒度化.細粒度的像素是粗粒度的一半，在已經確定的粗粒度像素中重復第一步的操作確定路徑.3)然后，重復前兩步操作，直到確定最終路徑.計算出兩條路徑的結束位置cx(π1(m)),cy(π2(n))的距離，記作φ(x,y)=dm,n.本文構造空間位置特征度量的核函數見公式(3)：

Kp(cx,cy)=e-φ(x,y)

(3)

速度特征相似度量.在分析真實的軌跡數據中，軌跡在不同位置的速度可能包含不同的意義，比如某一區域的瞬時速度相對集中于較小的區間，這個區域可能是十字路口或者學校路段；在某一區域車輛方向如果集中于一個較小的角度范圍，那么這個路段可能禁止掉頭等情況.如果出現異常的瞬時速度或者方向.從軌跡的位置這一個特征角度，不足以選取出有關的軌跡信息.同時，對于軌跡中的速度信息，由于軌跡數據的速度信息包含有：速度的大小，速度的方向并且需要考慮此時的速度位置.傳統度量矢量數據的方法不能同時處理矢量速度和位置信息.本文這里使用圖像處理中計算直方圖的卡方的距離度量.

首先，粗粒度劃分速度信息的大小和方向為L量級.類似于圖像中的灰度值劃分，標準化速度的大小和方向數據.同量級下，將相同的速度方向和速度大小的個數記錄到不同的直方圖，建立速度的直方圖特征hk.然后，細粒度劃分速度數據的大小和方向劃分到L/2量級，重復上述操作，直到將數據劃分到預期量級.最后，計算軌跡數據k和k′的直方圖hk(i)和hk′(i)的卡方距離.速度特征的相似度度量Kh(k,k′)，如公式 (4)所示：

(4)

時間特征相似度量.由于軌跡帶有的時間戳信息，本文使用t(0)表示軌跡的開始時間，t(1)表示軌跡的結束時間.將兩條軌跡的開始時間t(0)和結束時間t(1)分別進行做差后，通過公式(5)t(k,k′)求和來比較軌跡在時間度量上的差異.最后，本文使用高斯核函數度量時間特征相似，通過Kh(k,k′)公式(6)計算度量相似度：

(5)

Kt(k,k′)=e-βt(k,k′)

(6)

給定有N條軌跡數據，則參數β=|n(k)-n(k′)|,每個軌跡數據時間數據數目不同，用兩條軌跡中時間點個數差的作為參數，表示個數差值越小時間特征相似度越大.

對于同一個軌跡數據集來說，不同的觀察者感興趣的場景不同.例如，乘客在乘坐出租車時候，他關心的是司機師傅是否繞路；當私家車主在開車旅行時候，關心的是車輛是否超速；在當前時間段，對于應急車輛來說，它是很重要的對于是否可以避開擁擠路段.因此，與在單一的特征上進行度量的傳統的度量方式不同，本文使用一個結合了公式(3)中的位置度量Kp(k,k′)，公式(4)中的速度度量Kh(k,k′)，公式(6)中的時間信息度量Kt(k,k′)的融合相似度量K(xk,xk′)，如公式(7)所示：

(7)

其中，αp代表的Kp(k,k′)權重值，αh代表的Kh(k,k′)權重值，αt代表Kt(k,k′)權重值.由于人們對于相同數據在不同場景下所關注的特征信息有所不同，可以通過調整公式(7)中不同特征度量的權重值來滿足人們不同場景下的需求.例如，當我們想了解車輛是否繞路等信息時候，我們可以調整對于位置信息度量的權值αp；如果我們想了解車輛是否有超速情況的時候，我們可以調整對于速度信息度量的權值αh；如果我們想了解軌跡數據產生的時間段分布時候，可以增加時間信息度量的權值αt.最終，通過調整權值來搜尋出符合觀察者的需求的數據信息.

3.2 基于譜聚類的軌跡異常檢測

本文采用譜聚類的方法對軌跡數據的圖模型中的節點對象進行劃分.聚類的結果是使得組內的對象之間很相似，而組與組之間的對象不相似.在譜聚類的模型中，聚類將圖劃分為若干個子圖，使得同一個子圖中的對象很相似.但是,不同子圖內的對象相似程度不高.

定義 3.給定圖G=，圖G′=.若集合V′?V，E′?E，ω′?ω,則稱圖G′是圖G的一個子圖,也稱子圖G′.

(8)

軌跡特征融合的相似度量.經過特征融合度量的數據分布很難判斷，針對這一情況，本文采用譜聚類的方法將圖的劃分若干個子圖，具體軌跡數據的檢測方法步驟如下：

第1步.本文將每條軌跡抽象為圖中的一個節點，運用公式K(xk,xk′)=αpKp(k,k′)+αhKh(k,k′)+αtKt(k,k′),來計算不同軌跡節點之間的相似度度量.

第2步.構建親和矩陣W，將不同軌跡的相似度度量放到一個矩陣W中，其中wi,j=K(xk,xk′)，wkk′∈W.

第4步.求解矩陣L中的特征值k.本文計算特征值之間的差值K=ki+1-ki，如果Ki+1/Ki和Ki/Ki-1值出現了較大的變化，本文就將聚類簇的個數選取為K.

第5步.將特征向量使用K-means進行聚類，軌跡節點劃分到各個子圖G′中.最后，輸出所有子圖的劃分.

4 算法描述

本文采用融合度量軌跡數據的方法，運用核函數和圖分割方法對軌跡數據進行圖劃分為若干個子圖，將軌跡數據劃分到不同類別.

軌跡檢測算法Trajectory Detection Based on Multi Feature Fusion(TD-MFF)算法具體步驟如下：首先，算法將每條軌跡抽象為一個節點對象，在軌跡融合度量fusion_metric()中運用核函數計算軌跡數據在空間特征，速度特征和時間特征上的相似度量.最后，在第22行構建了軌跡融合度量的方法.在軌跡融合度量TD-MFF算法中，構建軌跡數據的圖模型，運用譜聚類進行圖分割為子圖，每個子圖內的數據即為相似的軌跡數據.在異常檢測算法中，設置閾值τ，通過搜索權值系數小于閾值τ的子圖來判斷軌跡數據的異常.

算法1.軌跡融合度量fusion_metric()

輸入：軌跡數據xk，xk′

輸出：融合軌跡度量

1.xk,xk′←軌跡k，k′中的軌跡信息

2.In Coarse-grained: //在粗粒度下計算

3. In Fine-grained://在細粒度下計算

4. shrink(xk) = reduce_by_half(xk)//

5. shrink(xk′) =reduce_by_half(xk′)

6. window =window(len(xk),len(xk′),radius)

7.fori in window{

8.forj in window{

9.di,j=eij+min(di-1,j,di,j-1,di-1,j-1)

10.}}//將計算window中的最短距離

11.dn1,n2←記錄最短路徑值

12.Kp(k,k′)←exp(-dn1,n2)//取DTW的最短距離計算得到位置相似度度量

13.hk(i),hk′(i)←xk,xk′//建立直方圖

14.for(i =0;i

15.for(j=0; j

16.hk(i)←Bin 1//統計軌跡1中該區域的速度大小和速度方向的個數

17.hk′(i)←(dic2)//統計軌跡2中該區域的速度大小和速度方向的個數

20.β=|n(k)-n(k′)|

21.Kp(k,k′)←exp(-β·RBF)//計算時間特征的相似度量

22.K(xk,xk′)=αpKp(k,k′)+αhKh(k,k′)+αtKt(k,k′)

23.returnK(xk,xk′)//返回融合度量值

在fusion_metric()中，第2-第10行在粗粒度和細粒度約束下約簡了搜索范圍，獲得最短路徑距離.第12行中運用公式(3)計算出計算空間位置特征的相似度.第13-第17行構建了軌跡速度的直方圖信息，第18行運用公式(4)計算了直方圖距離，即為速度特征的相似度.第19-第21行用公式(5)和公式(6)計算了時間特征的相似度.最后，在第22行運用公式(7)將3種特征融合，構建了軌跡的融合度量.

算法2.融合度量TD-MFF算法：

輸入：軌跡數據

輸出：軌跡數據劃分

1.for(i =0;i

2.for(j=0;j

3.K(xi,xj)=fusion_metric(xi,xj)

4.wi,j=K(xi,xj)

5.W←wi,j//構建親和矩陣

6.}}

8.L=D-W//構建拉普拉斯矩陣

9.K-means(L) //劃分子圖G′

10.returnG′

TD-MFF算法通過譜聚類對軌跡數據進行分類.第1-第6行是計算軌跡間的特征融合相似度，第7行計算相似矩陣的度矩陣D，第7-第8行構建拉普拉斯矩陣L.第9行采用K-means算法聚類，將每個圖模型中的節點劃分到子圖中.最后，輸出劃分好的軌跡分類.

算法3.異常檢測

輸入：圖模型數據G

輸出：異常軌跡

2. TR←V//記錄子圖的節點標號

3. outlier←transform(TR)//轉化標號為軌跡數據

4.returnoutlier

在異常檢測算法中，算法第1行是判斷子圖的稀疏系數，對于符合異常條件，即子圖的稀疏系數小于閾值τ的子圖在第3行進行轉換數據.最后，輸出符合稀疏系數M小于閾值τ的子圖中的軌跡數據即為異常軌跡數據.

5 實驗結果及分析

實驗環境：Intel(R)Core(TM)i5-6640HQ CPU,8GB內存，Windows 10操作系統，PyCharm作為開發平臺，采用Python語言實現算法的編程.

為了驗證本文中算法的可行性，本文采用的數據集是2007年2月20日上海市出租車軌跡數據.數據集中包含了4000多輛出租車在24小時內的車輛行駛軌跡，車輛的行駛軌跡采樣間隔為1min，其中，軌跡數據屬性包括車輛的ID號，車輛的經度、維度信息，時間戳信息，瞬時速度的大小，車輛朝向(從順時針方向與北方向的夾角).每條軌跡信息包含數據信息條數不相等，大約在1700～7000條數量不等的信息.本文中的將軌跡的屬性處理為軌跡的位置特征(經度、緯度信息)，速度特征(經度、緯度信息，瞬時速度的大小，車輛朝向)，時間特征(時間戳)作為軌跡的位置特征.由于軌跡信息量大，本文每隔20次取一次點，進行實驗.本文首先選取了劃分兩個數據集，每個數據集包含82條不同軌跡；文本采用2017-2018年颶風數據進行測試，數據包含了1131條軌跡的28798個數據點進行測試.為了更好展示實驗結果，本節以數據可視化的方式展示了實驗結果.

5.1 特征融合的聚類實驗

上海出租車軌跡實驗.實驗測試了的出租車輛軌跡數據在不同參數下的聚類實驗結果，其中設置實驗參數為：k=5.圖2展示了在單一特征下的軌跡聚類結果和融合度量的軌跡聚類結果的對比.

單一特征度量.圖2(a)中展示了度量速度特征的相似度聚類結果，令αh=1.軌跡數據的速度特征帶有位置屬性，從數據聚類效果來看比較分散，效果較差；在圖2(b)中展示了度量空間位置特征相似度的聚類結果，令αp=0.5.空間位置特征度量下的效果具有明顯的區分效果.

融合特征度量.圖2(c)展示了融合特征下的聚類效果，令αp=0.5，αh=0.5.直觀的看，在融合特征下，TD-MFF算法對軌跡數據劃分明顯.

圖2 特征融合度量聚類實驗Fig.2 Result on measurement of position feature

圖2(b)和圖2(c)中實驗結果的對比：圖2(b)中的區域I有兩個部分距離較遠，在圖2(c)中劃分為兩個類，明顯的圖2(c)的劃分更為合理.同時，圖2(c)中的區域V是兩條數據偏離度大的軌跡數據，而其他區域的數據相對集中.因此，特征融合后的聚類效果更好.

直觀地看出，使用特征融合后的度量檢測的軌跡劃分更有意義.這是由于使用DTW核函數度量是對于兩條軌跡直接進行度量，很容易忽略掉局部數據.包含了位置特征和速度特征的融合度量有了局部調整，很好的彌補了直接度量位置特征時候的不足.這是因為速度特征同時帶有位置標簽，采用直方圖核函數的匹配使得會檢測到得局部的速度信息，這樣可以對于位置度量進行一個局部調整，很好的彌補了位置特征在直接度量時候無法檢測到局部檢測的不足.TD-MFF算法實驗測試了融合度量的表現更好的聚類效果，特征融合度量方法是十分有效的.

5.2 軌跡的異常檢測

異常軌跡檢測實驗.實驗測試了算法在異常軌跡場景下的性能.圖3展示TD-MFF算法在異常檢測中的實驗結果.采用融合度量方式.實驗中，令αp=0.5，αh=0.5；設置聚類個數k=3，閾值τ=0.

圖3 軌跡異常檢測實驗Fig.3 Result on measurement of fusion feature

實驗結果展示了TD-MFF有效地將數據在劃分的3個區域中.其中，區域I部分是33條軌跡的聚合區域，區域II和III中分別包含了一條軌跡.異常檢測算法輸出了區域II和III中的軌跡數據.

實驗結果表明，TD-MFF算法可以有效的檢測出全局的異常軌跡，因此，TD-MFF算法可以有效地在異常檢測場景下使用.但是，由于算法在度量數據相似方法上采用了全局度量，使得圖4中區域I存在的局部異常現象無法檢測出來.

圖4 TD-MFF算法和TRAOD算法對比實驗Fig.4 Experimental comparison between TD-MFF and TRAOD

5.3 算法比較

采用軌跡數404條，其中參數設置：D=15.0,P=1.0,F=0.1,WeightPar=5,WeightAngle=5 WeightPer=5；TD-MFF算法參數設置:k=35，τ=0.在算法的參數設置中，TD-MFF算法設置了2個參數，TRAOD算法在6個參數.在參數設置上，TD-MFF算法具有優勢，更少的參數設置可以有效減少的人為因素的干擾，使得結果更加客觀.

圖4(a)中展示了TRAOD檢測30條異常軌跡，圖4(b)中展示了TD-MFF算法檢測41條異常軌跡.從比較中可以看出兩個算法找出的異常軌跡有許多明顯的相同部分.從圖4(a)中標注的記號I，II處可以看出，算法TD-MFF在記號I，II找出了在位置上偏出的異常數據，在記號3處多數軌跡方向為東西走勢，而III處的走勢為南北走向，是一處明顯的異常數據.TRAOD在圖中的左下方沒有找到異常數據，說明TD-MFF算法搜索的異常軌跡數據.在實驗過程中，當數據為1131條軌跡時，TRAOD算法由于內存原因無法計算，而TD-MFF算法可以檢測出異常軌跡，因此，在處理大規模軌跡數據時候，TD-MFF是十分有效的.

在算法效率上.我們比較了TD-MFF、TPRO和TRAOD 3種算法在不同數目的數據下的時間.表1中展示了3種算法在比較時的參數設置.圖5展示了算法在不同軌跡數據集上的時間消耗.由于TRAOD算法在大規模數據下會產生內存溢出錯誤，因此我們這里采用數據規模為100，200和400.

表1 參數設置Table 1 Parameter settings

圖5中數據表明，3種算法的時間消耗與數據集的規模呈正相關.其中，TD-MFF算法在200和400條軌跡的數據集測試中明顯優于TPRO和TRAOD.

圖5 效率比較Fig.5 Efficiency comparison

實驗中當軌跡數量達到1000條時候會TRAOD算法會產生內存溢出的錯誤.TRAOD算法是將軌跡切分為子段，然后比較子段之間的相似度.在大規模數據集中，軌跡子段的劃分會消耗時間，同時，軌跡子段需要同軌跡集中所有的軌跡子段進行比較，消耗大量內存并且容易產生內存溢出.TPRO是將地圖劃分為網格，僅對于網格周圍的數據進行比較，與TRAOD相比減少了計算成本.TD-MFF算法使用核函數將數據映射到一個圖模型中，簡化了數據模型，提高了計算效率.從實驗結果來看，TD-MFF算法效率高于TPRO和TRAOD算法.

6 結束語

本文針對軌跡數據，給出了一種特征融合度量的軌跡數據挖掘算法TD-MFF.TD-MFF算法在多個特征上度量軌跡數據相似度，有效的解決了傳統算法中的單一度量導致的挖掘數據不充分.從多個特征進行數據挖掘，更能發現在大量數據中存在的隱藏信息；同時，TD-MFF算法并且有效減少了傳統方法中的多個參數設置問題，僅僅需要從觀察者的角度出發，增加其感興趣的特征的權值比重，更加傾向于可發現觀察者所關注的問題；最后，采用真實數據進行驗證.下一步將對于算法進行并行化設計，以便算法適應更加海量的軌跡數據.