安計勇，朱 猛，翟靖軒，3，王大阜

（1.中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116；2.信陽農(nóng)林學(xué)院 計算機科學(xué)系，河南 信陽464006；3.中國礦業(yè)大學(xué) 科技園公共信息服務(wù)中心，江蘇 徐州221116；4.中國礦業(yè)大學(xué) 圖文信息中心，江蘇 徐州221116）

0 引 言

由于軌跡數(shù)據(jù)的特殊性，對于軌跡異常檢測的研究非常稀缺。文獻 ［1－4］中算法及目前一些算法針對軌跡異常檢測，都只關(guān)注與軌跡位置相關(guān)的低層次信息，忽略了與軌跡運動特征相關(guān)的速度、加速度以及轉(zhuǎn)角等重要因素，因此這些方法通常很難直接應(yīng)用于實際生活中，無法很好挖掘出更具有實際意義的軌跡異常點。

針對以上問題，本文提出一種軌跡多因素的異常集成檢測 方 法TRODEM （trajectory outlier detection ensemble based on multi－factors），該方法采用了集成分析技術(shù)，將軌跡數(shù)據(jù)多因素特征分別作為一個集成組件進行處理，并將處理所得的結(jié)果通過組合函數(shù)集成為一個最終用于異常檢測的最終分值，最后通過該分值來判定軌跡點是否為異常點。在真實數(shù)據(jù)上進行的實驗結(jié)果表明，TRODEM 可以提高原有算法的質(zhì)量并發(fā)現(xiàn)更具有現(xiàn)實意義的異常點。

1 軌跡多因素異常集成檢測

1.1 軌跡基本定義以及多因素距離

軌跡的本質(zhì)上是一種空間－時間點序列，為便于描述，通常 用Tr表 示，則Tr＝｛p0，p1，p2，…，pi…pn｝，其 中i＝0，1，2，…n，pi為軌跡點pi＝｛locationi，timei…，…｝，軌跡點序列根據(jù)采樣時間的先后順序排列。pi屬性至少包括地理位置信息以及時間信息，對于二維平面數(shù)據(jù)來講，Pi＝｛Xi，yi，ti，…｝，i＝0，1，2，…n；t0＜t1＜t2＜……＜tn；xi，yi∈R，ti∈R＋；有些采樣數(shù)據(jù)還包含其它移動對象軌跡特征，如瞬時速度、環(huán)境因素等，當前大多數(shù)據(jù)采用二維軌跡數(shù)據(jù)，三維數(shù)據(jù)除以上特征外包含海拔信息。移動對象數(shù)據(jù)分析往往針對大規(guī)模軌跡數(shù)據(jù)集，用I 表示，I＝｛T1，T2，……，Ti，……，Tn｝，其中Ti即為上述軌跡概念，i＝0，1，2，…n，軌跡集I一般為軌跡研究對象。

軌跡數(shù)據(jù)是描述移動對象運動狀態(tài)的有效方法，數(shù)據(jù)所反映的不僅僅是運動物體地理位置特征，也包含其它重要運動特征，如速度，轉(zhuǎn)角等。

（1）地理位置：地理位置特征是軌跡的基本特征之一，標記了移動物體在采樣范圍內(nèi)的空間位置情況。

（2）時間：時間特征是軌跡的一個重要特征，標記軌跡點的采樣時間。

（3）速度：速度是移動對象的固有屬性之一，表示移動對象在運動方向上移動的快慢程度。

（4）加速度：加速度是運動的內(nèi)在屬性，反映了運動物體受力作用情況。

（5）轉(zhuǎn)角：即軌跡運動過程中方向的變化量。軌跡點的轉(zhuǎn)角指的是：與該點的左相鄰點和該點連線延長線和該點與該點右相鄰點連線所構(gòu)成的角，其中左相鄰點為該軌跡點上一時刻采樣點，右相鄰點為該軌跡點下一時刻采樣點。通常情況下，轉(zhuǎn)角大小范圍為 ［0，180］，方向以延長線為起始邊，逆時針為正方向，順時針為負方向。

對于一條軌跡Ti上的軌跡點Pi，對應(yīng)的速度、加速度、轉(zhuǎn)角可以分別表示為

在得到了速度、加速度、轉(zhuǎn)角之后，將這些因素加入的軌跡描述中，從而對軌跡的維度進行擴充。因此，在加入這些因素后，軌跡點Pi可以描述為

軌跡Ti可以描述為

在進行異常檢測之前，首先要給出軌跡點間距離的度量。傳統(tǒng)基于距離算法只考慮到軌跡點的位置，因此通常采用歐式距離來度量軌跡點的距離。例如，對于點pm和點pn來說，它們之間的距離可以表示為

由于本文算法考慮了軌跡點的速度、加速度、轉(zhuǎn)角等因素，因此在進行異常檢測前，需要分別對這些因素間的距離給出一個度量，本文采用這些因素標量之間的差的絕對值來度量它們之間的距離，得到了多因素間的距離后。對于軌跡點P，歸一化處理后的速度

式中：vmax和vmin——數(shù)據(jù)集中速度的最大值和最小值，由此可知歸一化處理后的速度v／的取值范圍是0～1。那么，對于點pm和點pn，它們之間的速度、加速度、轉(zhuǎn)角之間的距離分別可以表示為

1.2 異常集成檢測

集成分析是一種十分常見的方法，主要是用于減少在特定數(shù)據(jù)集或者局部數(shù)據(jù)上建模的獨立性。在異常分析領(lǐng)域中，關(guān)于集成分析的研究還不是很多。盡管如此，還是有很多學(xué)者對異常集成進行了研究［5－7］。這些方法表明，當采用了合適的集成分析方法，算法的效果提升的非常顯著。集成分析在高維度異常檢測［8－10］中非常有效，在這種方法中，為發(fā)現(xiàn)異常點需要對數(shù)據(jù)的多重子空間進行探索。

典型的異常集成應(yīng)當包含一些不同組件，通過這些組件來構(gòu)造最終的集成結(jié)果。通常來說，一個標準的異常集成過程應(yīng)當包括以下幾個部分：①模型建立：利用特定的技術(shù)或者算法來建立集成組件。②標準化：利用特定的技術(shù)將不同異常分值轉(zhuǎn)化為可以有效組合的分值。③模型組合：指的是最終的組合函數(shù)，該函數(shù)用于建立最終的異常分值。

1.3 軌跡多因素異常集成檢測算法

由于軌跡數(shù)據(jù)的特殊性，在軌跡數(shù)據(jù)挖掘領(lǐng)域這方面的研究目前卻嚴重缺乏，如今還沒有比較好的算法用于軌跡數(shù)據(jù)異常檢測。目前已有的算法通常只關(guān)注了軌跡數(shù)據(jù)的位置信息，無法有效地處理與運動相關(guān)的速度、加速度、轉(zhuǎn)角等重要因素。本文提出一種軌跡多因素異常集成檢測方法，采用數(shù)據(jù)為中心的集成思想，并分別對軌跡數(shù)據(jù)的速度、加速度、轉(zhuǎn)角等多因素特征進行異常檢測并將其結(jié)果通過組合函數(shù)進行集成，最終挖掘出更有意義的軌跡異常點。該方法的偽代碼描述如下所示。

算法以整條軌跡作為算法輸入，首先對軌跡點需要用于異常檢測的因素進行計算并對擴充后的軌跡數(shù)據(jù)進行標準化處理操作Normalize。在標準化處理的過程中，采用歸一化處理方法。隨后依次遍歷與該點處于同一軌跡上的所有軌跡點，在集成過程中，將每種因素特征都看作是一個集成組件，并利用基于距離的異常檢測方法DB［5］為軌跡點不同因素特征賦予一個用于異常檢測的分值。在對每種特征的異常分值進行計算的過程中，算法采用這些因素標量之間的差的絕對值來度量它們之間的距離，并將這些距離作為異常分值，當然這些分值都是進行歸一化處理后的結(jié)果。接下來通過組合函數(shù)CombineFunction對t個分值進行集成處理并得到每個軌跡點的最終分值，其中t為用于異常檢測因素的個數(shù)。在得到每個軌跡點的最終分值之后，通過基于距離方法的計算軌跡點間的分值A(chǔ)S（pi，pj），如果整條軌跡中與該點之間距離大于距離閾值Scoremin的點個數(shù)大于數(shù)值閾值時，認為該點為異常點，其中數(shù)值閾值的大小為總軌跡點數(shù)n與pct的乘積。算法將檢測到的異常點加入異常點集合OT中，并最終將OT輸出。通過對算法進行分析可知，該算法的時間復(fù)雜性為O（N2）。

1.4 帶有權(quán)值的累積和方法

本文算法采用集成學(xué)習思想，將與軌跡運動特性相關(guān)的多因素作為不同特征集，通過基于距離的異常檢測算法分別對其進行檢測，從而得到不同的異常分值，并最終通過對這些異常分值進行集成從而得到最終的異常分值，進而判定軌跡點是否為異常點。由于不同的特征表示的意義不同，因此為了對其異常分值進行集成需要對這些不同的分值進行有效地處理。在傳統(tǒng)的異常集成檢測方法中，通常采用排序方法或者累積和方法來對不同集成組件的分值進行集成，然而這兩種典型的方法都存在一些缺點。在排序方法中，一種集成組件檢測出來的異常點可能在其它組件檢測中不被當作異常點。另一方面，在累積和方法中，一個集成組件所得的分值可能充分大，使得最終的集成結(jié)果對它過分依賴。針對以上不足，本文中利用帶有權(quán)值的累積和方法CombineFunction對由不同特征所產(chǎn)生的分值進行集成，該方法根據(jù)不同特征對軌跡的影響程度為不同特征賦予相應(yīng)的權(quán)重，根據(jù)權(quán)重對不同分值進行加權(quán)處理，并將所得的分值作為最終分值進行異常檢測。CombineFunction方法的描述如下所示。

算法以不同特征集所得的異常分值作為輸入，其中m為應(yīng)用于異常檢測的特征數(shù)量。隨后算法為這些特征賦予一個權(quán)重w，其中w1＋w2＋…＋wi＋…＋wm＝1，并將不同特征所得的異常分值通過加權(quán)的方式集成起來，并將結(jié)果輸出作為最終的異常分值用于多因素異常檢測。在實際進行異常檢測的過程中，根據(jù)實驗的情況對權(quán)值進行調(diào)節(jié)從而克服傳統(tǒng)集成方法中可能存在的集成結(jié)果對某種特征過分依賴的情況。

2 實驗與分析

為更好地挖掘軌跡數(shù)據(jù)中的異常信息，開發(fā)軌跡異常檢測分析平臺Trajectory Outlier Detection System。該系統(tǒng)由Visual C＋＋2008開發(fā)，軌跡數(shù)據(jù)存儲在Access數(shù)據(jù)表中。實驗進行的軟硬件環(huán)境包括：Windows XP Professional SP3，Visual Studio 2008，CPU （CORE 2DUO 2.93GH），內(nèi)存3G。本文選取大西洋颶風數(shù)據(jù)以及動物運動軌跡這兩個真實數(shù)據(jù)集作為實驗數(shù)據(jù)。本文的實驗部分主要由數(shù)據(jù)規(guī)模對異常檢測的影響、算法參數(shù)對異常檢測的影響、軌跡多因素異常集成檢測的效果以及多因素特征對異常集成檢測的影響等部分組成。

2.1 軌跡數(shù)據(jù)規(guī)模對異常檢測的影響

本實驗選取1993年到1996年麋鹿運動數(shù)據(jù)進行實驗，參與異常檢測的因素為速度、加速度、轉(zhuǎn)角，Scoremin＝0.1，pct＝0.9，3種因素在集成函數(shù)中的權(quán)重分別為0.4、0.3、0.3，時間單位為ms，對比軌跡數(shù)據(jù)規(guī)模逐漸增大時，異常檢測耗時情況，具體實驗結(jié)果如圖1 所示。圖1選取的自1993年到1996年鹿的運動數(shù)據(jù)進行實驗，以單條軌跡為單位增加軌跡數(shù)據(jù)規(guī)模。如圖1所示，從圖中趨勢可以看出，隨著軌跡數(shù)據(jù)規(guī)模的增大，異常檢測時間逐漸增加，但并非是指數(shù)型的增長，而是平方階增長。這一實驗結(jié)果也驗證了本文算法時間復(fù)雜度分析結(jié)論，時間為平方階增長。

圖1 軌跡點數(shù)對異常檢測時間的影響

2.2 參數(shù)對異常檢測的影響

本實驗取麋鹿運動數(shù)據(jù)作為實驗數(shù)據(jù)，選取速度、加速度以及轉(zhuǎn)角作為異常集成檢測的因素，驗證參數(shù)Scoremin、pct值大小同異常點數(shù)目之間的關(guān)系。實驗所用的軌跡編號為311，軌跡點數(shù)1018。具體情況如圖2和圖3所示。

圖2 Scoremin對異常檢測結(jié)果的影響

圖2為pct取0.9，速度、加速度、轉(zhuǎn)角3種因素在集成函數(shù)中的權(quán)值分別取0.4、0.3、0.3時，不同Scoremin值下檢測到的異常點的數(shù)目，用于驗證Scoremin值對異常點數(shù)目的影響。從圖中可以看出，隨著Scoremin值的增大，檢測到的異常點數(shù)目減少，這一結(jié)果與算法預(yù)期相符。圖3為Scoremin取0.1，速度、加速度、轉(zhuǎn)角3 種因素在集成函數(shù)中的權(quán)值分別取0.4、0.3、0.3時，不同pct值下檢測到的異常點數(shù)目，用于驗證pct值對異常點數(shù)目的影響。從圖中可以看出，隨著pct值的增大，檢測到的異常點數(shù)目減少，這一結(jié)果符合算法的預(yù)期。

圖3 pct對異常檢測結(jié)果的影響

2.3 軌跡多因素異常集成檢測結(jié)果

為了驗證TRODEM 算法的有效性，本文分別選取麋鹿運動數(shù)據(jù)以及颶風數(shù)據(jù)進行實驗，具體的異常檢測結(jié)果如圖4和圖5所示，圖中實線代表是軌跡，帶有＋標記的點為正常軌跡點，帶有＊標記的點為檢測出的異常點。

圖4為Scoremin取0.1，pct取0.9，速度、加速度、轉(zhuǎn)角3種因素在集成函數(shù)中的權(quán)值分別取0.4、0.3、0.3 的情況下，對麋鹿數(shù)據(jù)進行檢測的結(jié)果，實驗所選用的軌跡編號為311。從圖中可以發(fā)現(xiàn)本文挖掘出的異常點絕大多數(shù)都位于軌跡的拐點處，這些拐點可以反映出移動對象運動的變化，與軌跡數(shù)據(jù)中絕大多數(shù)的運動狀態(tài)不一致，符合異常點的定義。

圖5為Scoremin取0.1，pct取0.9，速度、加速度、轉(zhuǎn)角3種因素在集成函數(shù)中的權(quán)值分別取0.4、0.3、0.3 的情況下，對颶風數(shù)據(jù)進行檢測的結(jié)果，實驗所選用的為1995年的數(shù)據(jù)。從圖中可以發(fā)現(xiàn)這些異常點也基本都位于軌跡的拐點處。通過對這些異常點進行進一步地挖掘可以得到有價值的信息。

傳統(tǒng)的軌跡異常檢測算法通常都只關(guān)注于軌跡的位置信息，忽略了與軌跡運動相關(guān)的速度、加速度、轉(zhuǎn)角等因素，然而這些因素在實際生活中有很重要的應(yīng)用。本文算法在傳統(tǒng)基于距離的異常檢測算法的基礎(chǔ)上，采用軌跡多因素集成的方法來發(fā)現(xiàn)異常點，通過實驗驗證，本文算法可以很好地處理速度、加速度、轉(zhuǎn)角等因素從而發(fā)現(xiàn)這些與移動對象運動相關(guān)的異常點，極大程度上提升了異常檢測算法性能和可用性。

2.4 多因素特征對異常集成檢測的影響

本實驗分別選取了麋鹿數(shù)據(jù)以及颶風數(shù)據(jù)進行實驗，通過對組合函數(shù)中多因素權(quán)重進行調(diào)節(jié)來驗證多因素特征對異常集成檢測結(jié)果的影響，具體的結(jié)果如圖6和圖7所示。

圖4 麋鹿數(shù)據(jù)的異常檢測結(jié)果

圖5 颶風數(shù)據(jù)的異常檢測結(jié)果

圖6 麋鹿數(shù)據(jù)下多因素特征對異常檢測的影響

圖7 颶風數(shù)據(jù)下多因素特征對異常檢測的影響

圖6和圖7分別為Scoremin取0.1，pct取0.9，用于集 成檢測的軌跡多因素特征為速度、加速度以及轉(zhuǎn)角時，異常檢測結(jié)果隨多因素特征權(quán)重的變化情況。圖6所選用的是麋鹿數(shù)據(jù)，軌跡編號為311，圖7選取的是1995年的颶風數(shù)據(jù)。其中，橫坐標w 代表相應(yīng)特征的權(quán)重，縱坐標代表檢測出異常點的數(shù)量，帶有圓形標識的折線用于表示隨著速度權(quán)重的變化異常點數(shù)量的變化情況，帶有正方形標識的折線用于表示隨著加速度權(quán)重的變化異常點數(shù)量的變化情況，而帶有三角形標識的折線則用于表示隨著轉(zhuǎn)角權(quán)重的變化異常點數(shù)量的變化情況。

可以發(fā)現(xiàn)，隨著多因素特征在集成過程中權(quán)重的變化異常檢測的結(jié)果也隨之發(fā)生變化。在圖6中，相對于速度和加速度，異常點數(shù)量隨著轉(zhuǎn)角權(quán)重的變化較為明顯；而在圖7中，變化則較為平緩。由此可知，在對不同的軌跡數(shù)據(jù)采用異常集成檢測的過程中，多因素特征對異常集成檢測的結(jié)果影響程度是不同的，如果簡單地采用累積和方法可能會造成檢測結(jié)果對于某種特征過分依賴，而本文算法在累積和的基礎(chǔ)上加入了多因素權(quán)重，從而可以通過對權(quán)重的調(diào)節(jié)克服以上缺點，很大程度上增強了異常集成檢測算法的性能。

3 結(jié)束語

本文針對已有軌跡異常檢測算法只關(guān)注軌跡數(shù)據(jù)的位置信息，提出一種軌跡多因素的異常檢測集成檢測方法TRODEM。主要采用了集成學(xué)習思想，并利用一種新穎的數(shù)據(jù)為中心的集成框架來對軌跡數(shù)據(jù)的多因素特征進行集成。算法將軌跡數(shù)據(jù)的速度、加速度以及轉(zhuǎn)角等多因素特征分別作為異常集成的一個組件，對這些因素進行檢測并為每種特征檢測出的結(jié)果賦予一個用于集成的異常分值，隨后利用組合函數(shù)對這些分值進行集成從而得到一個最終異常分值，并以此基礎(chǔ)上判定軌跡異常點。在集成過程中，本文采用帶有權(quán)值的累積和方法從而克服可能存在的集成結(jié)果對某種因素過分依賴的缺點。最后，本文通過真實數(shù)據(jù)上的實驗驗證了TRODEM 算法的有效性和魯棒性。

［1］Artur Ribeiro de Aquino，Luis Otavio Alvares，Chiara Renso，et al.Towards semantic trajectory outlier detection ［C］／／Proceedings of the Brazilian Symposium on GeoInformatics，2013：115－126.

［2］Keller F，Muller E，Bohm K.HiCS：High contrast subspaces for density－based outlier rangking ［C］／／IEEE 28th International Conference on Data Engineering，2012：1037－1048.

［3］Kriegel HP，Kroger P，Schubert E，et al.Interpretin and unifying outlier scores［C］／／Proceedings of the 11th SIAM International Conference on Data Mining，SDM，2011：13－14.

［4］Han J，Li Z，Tang LA.Mining moving object，trajectory and traffic data［G］.LNCS 5982：Database Systems for Advanced Applications.Springer Beerlin Heidelberg，2010：485－486.

［5］Rousseeuw PJ，Hubert M.Robust statistics for outlier detection ［J］.Wiley Interdisciplinary Reviews：Data Mining and Knowledge Discovery，2011，1 （1）：73－79.

［6］Xuan Hong Dang，Ira Assent，Raymond T Ng，et al.Discriminative features for identifying and interpreting outliers［C］／／IEEE 30th International Conference on Data Engineering，2014：88－99.

［7］Keller F，Muller E，Bohm K.HiCS：High contrast subspaces for density－based outlier ranking ［C］／／IEEE 28th International Conference on Data Engineering，2012：1037－1048.

［8］Müller E，Assent I，Iglesias P，et al.Outlier ranking via subspace analysis in multiple views of the data ［C］／／IEEE 12th International Conference on Data Mining，2012：529－538.

［9］Xia Ying，Liu Shenyi.Real time trajectory anomaly detection method and its application ［J］.Journal of Chongqing University of Posts and Telecommunication（Natural Science Edition），2011，23 （4）：496－499.

［10］Isaloo Mehdi1，Azimifar Zohreh1.Anomaly detection on traffic videos based on trajectory simplification ［C］／／8th Iranian Conference on Machine Vision and Image Processing，2013：200－203.