終端區航空器的異常軌跡檢測方法

卜寧+張旭紅

【摘 要】 終端區航空器的異常軌跡檢測是一個嶄新的研究領域。異常軌跡檢測常使用基于全局特征、軌跡片段、分類器的檢測方法，后續又出現了基于劃分、蟻群算法、軌跡模型、人工免疫等一系列的改進方法，各具特點。但是以上的方法在準確性、復雜度、評價方法等方面依然存在不足，需要進一步改進和創新。此領域具有良好的發展和應用前景。

【關鍵詞】 數據挖掘 異常軌跡 異常點檢測

【Abstract】 The trajectory outlier detection of the aircraft in terminal area is a new research. The usual methods often bases on global features， track clips and classification. There are a series of improved methods with distinct characteristics， which base on division， antcolony algorithm， trajectory model and artificial immune etc. Nevertheless， in terms of accuracy， complexity of count and evaluation， the methods above need further improvement and innovation. Besides，this field has good prospects of development and application.

【Key words】 Data Mining Outliers Detection Trajectory Outlier Detection

1 引言

隨著人類認識和管理水平的提高，信息處理手段的多樣化以及數據挖掘技術的發展，各領域的大量信息數據被收集和整理，形成數據庫。決策者往往基于提取自數據庫中有價值的信息和知識，制定相適應的策略，因此在信息龐大結構復雜的數據庫中高效的提取有效信息至關重要。針對各類數據的特點和結構，多種數據挖掘方法應運而生。

數據挖掘方法主要包括：分類方法、聚類方法、關聯規則、序列模式、異常點檢測和可視化技術等。其中異常點檢測可以大量數據中檢測到異常點所蘊含的特異知識，對決策者的決策具有重要指導意義?，F已廣泛應用于電信和信用卡欺騙、貸款審批、藥物研究、醫療分析、消費者行為分析、氣象預報、金融領域客戶分類、網絡入侵檢測等領域。

2 異常軌跡檢測

2.1 概念和意義

異常點是數據庫中不符合一般數據模型的數據。在挖掘正常類知識時，通?？偸前阉鼈冏鳛樵肼朁c來處理。在航空交通領域，航空器在終端區進場的軌跡信息是重要的研究數據。通過雷達或各類導航等設備獲取的軌跡信息，包含了航空器的位置、速度、時刻等時空信息，同時體現了航空器的飛行性能和實時的空域環境狀態，蘊含管制員指揮習慣和飛行員的操作習慣等信息。

在大量的軌跡數據中，偏離主干交通流的軌跡被稱為異常軌跡，是軌跡數據庫中的異常點數據。由于異常點數據并不是隨機出現的，而是具有與一般數據點不同的產生機制，所以通過對異常軌跡的檢測，可以對飛行員操作、管制員指揮、進離場程序設計、飛機性能等多項可能存在的異常環節進行分析，從而提出改進或調整策略，實現終端區航空器的流暢運行。

2.2 傳統的檢測方法

2.2.1 基于抽取軌跡全局特征的方法

2000年，Knorr等人提出。首先使用組成軌跡的點的數目、方向、速度等屬性來表征該軌跡。其次將每條軌跡視為一個整體，作為異常點檢測算法的基本單元并基于距離進行異常點檢測。如果每條軌跡的主要特征完全不同，上述方法可以檢測出整體軌跡是異常軌跡，比較直觀，實現比較簡單；如果主要特征中的某一項或幾項不同，軌跡異?？赡軙驗榫嚯x函數的加權作用而被丟失。當構成軌跡的點數量較多時，僅通過比較軌跡的全局屬性來判斷異常，而不考慮局部特征是不合理的。

2.2.2 基于分類器的方法

2006年，Li等人提出了有效的和可伸縮的分類方法motion-classifier，用于檢測移動對象的異常行為，開發出移動對象異常點檢測系統Motion-Alert，并將motion-classifier作為該系統的核心組件。這種方法存在一定缺陷，首先對于一個應用領域，通常很難找到一個標準數據集作為訓練數據集；其次每條軌跡往往長而復雜，存在許多局部異常軌跡片段。異常軌跡片段的異常有可能被整體軌跡所平均化，導致檢測失效。

2.2.3 基于軌跡片段相似度檢測的方法

2008年，Lee提出TRAOD算法，TRAOD分成劃分和檢測這兩個階段。首先依據MDL（最小描述長度）原則將每條軌跡分割成軌跡片段，選擇變化趨勢最大的點作為分割點；其次采用距離度量檢測每個片段的相鄰片段數目，鄰域片段最少的片段判定為異常片段。此法在確保劃分質量的同時也具有很高的效率。應用領域較廣，可以檢測出異常子軌道，也可以檢測出整條異常軌跡。2009年，劉良旭，喬少杰等人提出了一種基于R-Tree的算法。首先抽取軌跡中所有長度為k的軌跡片段構成基本比較單元，然后采用基于平移的最新Hausdorff距離作為度量基本比較單元之間的距離。在此基礎上提出了局部匹配、全局匹配和異常軌跡的定義?；诖颂岢隽艘环N基于R-Tree的異常軌跡檢測算法。該算法具有很高的計算效率，是一種有效的異常軌跡檢測算法。

2.3 改進的檢測方法

2.3.1 基于劃分的方法

使用空間劃分的方法將數據的搜索區域劃分為若干不重疊的超矩形單元，將異常點的檢測限制在局部空間內。并設計網格索引樹GI-Tree只存儲非空網格，同時保持網格間的鄰近關系，使得最近鄰搜索更加高效地完成。endprint

2.3.2 基于蟻群算法的方法

GODAC算法（Graph-cut based OutlierDetection using Ant Colony Algorithm），使用改進的蟻群算法構建圖像，然后對圖像進行有效切割，其中將距離和分布兩個方面綜合考慮放入蟻群算法中。蟻群算法的正反饋信息機制降低了對用戶定義的閾值的依賴程度。

2.3.3 基于人工免疫的方法

AIBTOD算法將人工免疫算法引入到異常軌跡檢測，對 TRAOD算法作出改進。思想是將核心線段作為抗體，模擬免疫系統的克隆選擇原理，不斷克隆并篩選最優核心線段，進行軌跡線段簇劃分。AIBTOD算法比TRAOD算法在保證檢測效果的前提下異常檢測效率更高。

2.2.4 基于半監督的方法

STOD算法（semi-supervised trajectory outlier detection），利用半監督技術輔助離群軌跡探測過程，并在軌跡片段相似性度量中考慮軌跡形狀，同時從整體局部兩方面同時考察離群軌跡，使得探測出的異常軌跡更加合理。

2.2.5 基于軌跡模型的方法

該算法不依賴于先驗知識，采用改進的LCSS距離作為度量，結合自適應聚類方法，實現軌跡的無監督建模過程。軌跡模型隨輸入數據實時更新，能夠很好地適應統計特性變化的場景，具有較強的應用和推廣價值。

3 研究展望

異常軌跡檢測是一個非常有發展前景的數據挖掘研究和應用領域，盡管已經有了一些研究成果但是整體依然處于起步階段，在終端區航空器的異常軌跡檢測領域更是如此。以上各類方法具有不同的特點，但是依然存在諸多方面需要改進。

參數的輸入，目前多數算法需要用戶人工輸入參數，并不斷嘗試已達到滿意效果。自適應參數是以后的一個研究切入點；度量的選取，單一性度量無法全面反映數據的聯系，全面分析數據并提高挖掘精度是今后工作重點；準確性，在基于軌跡片段劃分的算法中，采用各種原則和距離進行的劃分都不同程度的犧牲了準確性，選取適當的劃分準則對提高檢測效果至關重要；時間性，航空器的軌跡構型與飛行速度緊密相關，多數算法只考慮了軌跡的空間信息，而忽略了軌跡的時間維信息。融合軌跡的空間和時間維，將是未來的研究方向；算法復雜度，當軌跡數量較多時，算法的時間復雜度較大影響檢測效率，有待提高；評價方法，面對諸多異常軌跡檢測方法，如何客觀的定量的評價檢測結果是尚未以及難以解決的問題。

4 結語

本文針對終端區航空器異常軌跡檢測領域分析了傳統的檢測方法，同時總結了現有的各類改進方法，并對今后的改進和創新切入點做出了歸納?？陀^全面的展現該領域現階段研究狀態的同時，為各類方法的改進提供了建議性的觀點和理論參考。

參考文獻：

[1]姜金鳳.移動對象軌道異常檢測算法的研究.南京：南京航空航天大學，2010.

[2]姚明宇.基于人工免疫的軌跡聚類和異常檢測算法研究.南京：南京航空航天大學，2011.

[3]陳剛，錢猛，劉金.基于劃分的高效異常軌跡檢測.計算機工程與應用， 2013.

[4]Guan Yuan， Shixiong Xia， Lei Zhang， Yong Zhou， Cheng Ji.Trajectory Outlier Detection Algorithm Based on Structural Features. School of Computer Science and Technology， China University of Mining and Technology，2011

[5]Jae-Gil Lee，Jiawei Han，Xiaolei Li.Trajectory Outlier Detection：A Partition-and-Detect Framework. Department of Computer Science， University of Illinois at Urbana-Champaign，2011.endprint