終端區(qū)航空器的異常軌跡檢測(cè)方法

卜寧+張旭紅

【摘 要】 終端區(qū)航空器的異常軌跡檢測(cè)是一個(gè)嶄新的研究領(lǐng)域。異常軌跡檢測(cè)常使用基于全局特征、軌跡片段、分類器的檢測(cè)方法，后續(xù)又出現(xiàn)了基于劃分、蟻群算法、軌跡模型、人工免疫等一系列的改進(jìn)方法，各具特點(diǎn)。但是以上的方法在準(zhǔn)確性、復(fù)雜度、評(píng)價(jià)方法等方面依然存在不足，需要進(jìn)一步改進(jìn)和創(chuàng)新。此領(lǐng)域具有良好的發(fā)展和應(yīng)用前景。

【關(guān)鍵詞】 數(shù)據(jù)挖掘 異常軌跡 異常點(diǎn)檢測(cè)

【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 引言

隨著人類認(rèn)識(shí)和管理水平的提高，信息處理手段的多樣化以及數(shù)據(jù)挖掘技術(shù)的發(fā)展，各領(lǐng)域的大量信息數(shù)據(jù)被收集和整理，形成數(shù)據(jù)庫(kù)。決策者往往基于提取自數(shù)據(jù)庫(kù)中有價(jià)值的信息和知識(shí)，制定相適應(yīng)的策略，因此在信息龐大結(jié)構(gòu)復(fù)雜的數(shù)據(jù)庫(kù)中高效的提取有效信息至關(guān)重要。針對(duì)各類數(shù)據(jù)的特點(diǎn)和結(jié)構(gòu)，多種數(shù)據(jù)挖掘方法應(yīng)運(yùn)而生。

數(shù)據(jù)挖掘方法主要包括：分類方法、聚類方法、關(guān)聯(lián)規(guī)則、序列模式、異常點(diǎn)檢測(cè)和可視化技術(shù)等。其中異常點(diǎn)檢測(cè)可以大量數(shù)據(jù)中檢測(cè)到異常點(diǎn)所蘊(yùn)含的特異知識(shí)，對(duì)決策者的決策具有重要指導(dǎo)意義?，F(xiàn)已廣泛應(yīng)用于電信和信用卡欺騙、貸款審批、藥物研究、醫(yī)療分析、消費(fèi)者行為分析、氣象預(yù)報(bào)、金融領(lǐng)域客戶分類、網(wǎng)絡(luò)入侵檢測(cè)等領(lǐng)域。

2 異常軌跡檢測(cè)

2.1 概念和意義

異常點(diǎn)是數(shù)據(jù)庫(kù)中不符合一般數(shù)據(jù)模型的數(shù)據(jù)。在挖掘正常類知識(shí)時(shí)，通?？偸前阉鼈冏鳛樵肼朁c(diǎn)來處理。在航空交通領(lǐng)域，航空器在終端區(qū)進(jìn)場(chǎng)的軌跡信息是重要的研究數(shù)據(jù)。通過雷達(dá)或各類導(dǎo)航等設(shè)備獲取的軌跡信息，包含了航空器的位置、速度、時(shí)刻等時(shí)空信息，同時(shí)體現(xiàn)了航空器的飛行性能和實(shí)時(shí)的空域環(huán)境狀態(tài)，蘊(yùn)含管制員指揮習(xí)慣和飛行員的操作習(xí)慣等信息。

在大量的軌跡數(shù)據(jù)中，偏離主干交通流的軌跡被稱為異常軌跡，是軌跡數(shù)據(jù)庫(kù)中的異常點(diǎn)數(shù)據(jù)。由于異常點(diǎn)數(shù)據(jù)并不是隨機(jī)出現(xiàn)的，而是具有與一般數(shù)據(jù)點(diǎn)不同的產(chǎn)生機(jī)制，所以通過對(duì)異常軌跡的檢測(cè)，可以對(duì)飛行員操作、管制員指揮、進(jìn)離場(chǎng)程序設(shè)計(jì)、飛機(jī)性能等多項(xiàng)可能存在的異常環(huán)節(jié)進(jìn)行分析，從而提出改進(jìn)或調(diào)整策略，實(shí)現(xiàn)終端區(qū)航空器的流暢運(yùn)行。

2.2 傳統(tǒng)的檢測(cè)方法

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

2000年，Knorr等人提出。首先使用組成軌跡的點(diǎn)的數(shù)目、方向、速度等屬性來表征該軌跡。其次將每條軌跡視為一個(gè)整體，作為異常點(diǎn)檢測(cè)算法的基本單元并基于距離進(jìn)行異常點(diǎn)檢測(cè)。如果每條軌跡的主要特征完全不同，上述方法可以檢測(cè)出整體軌跡是異常軌跡，比較直觀，實(shí)現(xiàn)比較簡(jiǎn)單；如果主要特征中的某一項(xiàng)或幾項(xiàng)不同，軌跡異常可能會(huì)因?yàn)榫嚯x函數(shù)的加權(quán)作用而被丟失。當(dāng)構(gòu)成軌跡的點(diǎn)數(shù)量較多時(shí)，僅通過比較軌跡的全局屬性來判斷異常，而不考慮局部特征是不合理的。

2.2.2 基于分類器的方法

2006年，Li等人提出了有效的和可伸縮的分類方法motion-classifier，用于檢測(cè)移動(dòng)對(duì)象的異常行為，開發(fā)出移動(dòng)對(duì)象異常點(diǎn)檢測(cè)系統(tǒng)Motion-Alert，并將motion-classifier作為該系統(tǒng)的核心組件。這種方法存在一定缺陷，首先對(duì)于一個(gè)應(yīng)用領(lǐng)域，通常很難找到一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集；其次每條軌跡往往長(zhǎng)而復(fù)雜，存在許多局部異常軌跡片段。異常軌跡片段的異常有可能被整體軌跡所平均化，導(dǎo)致檢測(cè)失效。

2.2.3 基于軌跡片段相似度檢測(cè)的方法

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

2.3 改進(jìn)的檢測(cè)方法

2.3.1 基于劃分的方法

使用空間劃分的方法將數(shù)據(jù)的搜索區(qū)域劃分為若干不重疊的超矩形單元，將異常點(diǎn)的檢測(cè)限制在局部空間內(nèi)。并設(shè)計(jì)網(wǎng)格索引樹GI-Tree只存儲(chǔ)非空網(wǎng)格，同時(shí)保持網(wǎng)格間的鄰近關(guān)系，使得最近鄰搜索更加高效地完成。endprint

2.3.2 基于蟻群算法的方法

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

2.3.3 基于人工免疫的方法

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

2.2.4 基于半監(jiān)督的方法

STOD算法（semi-supervised trajectory outlier detection），利用半監(jiān)督技術(shù)輔助離群軌跡探測(cè)過程，并在軌跡片段相似性度量中考慮軌跡形狀，同時(shí)從整體局部?jī)煞矫嫱瑫r(shí)考察離群軌跡，使得探測(cè)出的異常軌跡更加合理。

2.2.5 基于軌跡模型的方法

該算法不依賴于先驗(yàn)知識(shí)，采用改進(jìn)的LCSS距離作為度量，結(jié)合自適應(yīng)聚類方法，實(shí)現(xiàn)軌跡的無監(jiān)督建模過程。軌跡模型隨輸入數(shù)據(jù)實(shí)時(shí)更新，能夠很好地適應(yīng)統(tǒng)計(jì)特性變化的場(chǎng)景，具有較強(qiáng)的應(yīng)用和推廣價(jià)值。

3 研究展望

異常軌跡檢測(cè)是一個(gè)非常有發(fā)展前景的數(shù)據(jù)挖掘研究和應(yīng)用領(lǐng)域，盡管已經(jīng)有了一些研究成果但是整體依然處于起步階段，在終端區(qū)航空器的異常軌跡檢測(cè)領(lǐng)域更是如此。以上各類方法具有不同的特點(diǎn)，但是依然存在諸多方面需要改進(jìn)。

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

4 結(jié)語(yǔ)

本文針對(duì)終端區(qū)航空器異常軌跡檢測(cè)領(lǐng)域分析了傳統(tǒng)的檢測(cè)方法，同時(shí)總結(jié)了現(xiàn)有的各類改進(jìn)方法，并對(duì)今后的改進(jìn)和創(chuàng)新切入點(diǎn)做出了歸納?？陀^全面的展現(xiàn)該領(lǐng)域現(xiàn)階段研究狀態(tài)的同時(shí)，為各類方法的改進(jìn)提供了建議性的觀點(diǎn)和理論參考。

參考文獻(xiàn)：

[1]姜金鳳.移動(dòng)對(duì)象軌道異常檢測(cè)算法的研究.南京：南京航空航天大學(xué)，2010.

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

[3]陳剛，錢猛，劉金.基于劃分的高效異常軌跡檢測(cè).計(jì)算機(jī)工程與應(yīng)用， 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