軌跡多因素異常集成檢測

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

對于一條軌跡Ti上的軌跡點Pi，對應的速度、加速度、轉角可以分別表示為

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

軌跡Ti可以描述為

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

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

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

1.2 異常集成檢測

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

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

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

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

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

1.4 帶有權值的累積和方法

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

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

2 實驗與分析

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

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

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

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

2.2 參數對異常檢測的影響

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

圖2 Scoremin對異常檢測結果的影響

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

圖3 pct對異常檢測結果的影響

2.3 軌跡多因素異常集成檢測結果

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

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

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

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

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

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

圖4 麋鹿數據的異常檢測結果

圖5 颶風數據的異常檢測結果

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

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

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

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

3 結束語

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