基于歷史航跡特征的飛行意圖識別

何艷，王運鋒

（四川大學計算機學院，成都610065）

0 引言

大數據時代，人們可以訪問到各行各業的信息資源呈現出爆炸式的增長，航空業也不例外。隨著航空業的迅速發展，航空公司的規模不斷擴大，機隊數量的不斷增加，飛行目標的航跡數據也越來越龐大復雜。面對龐大復雜的航跡數據，如何有效地利用不同管制意圖的歷史航跡特征，并對新的航跡意圖進行識別已成為航空業領域的新穎之處。

為了避免對歷史航跡進行大量標記人工成本高且難度大的缺點，本文采用半監督的思想，對少量歷史航跡進行標注并定義其意圖。標記完成后，首先，利用均值及曲線擬合的思想對歷史航跡數據總結航跡特征。其次，通過基于航跡形狀約束的半監督K-means 聚類改進算法對歷史航跡進行聚類。并將聚類后的特征集存到數據庫。最后，通過數據庫中的特征集對新的航跡意圖進行識別。

目前，航跡的聚類方法較多，常用的聚類算法有：k均值聚類算法、層次聚類算法、SOM 聚類算法、FCM 聚類算法等，這四種算法在運行時間及準確度方面綜合考慮，各有千秋。為了避免傳統的k 均值聚類算法的初始點選擇不穩定及SOM 時間復雜度較高且大量標記信息成本高的缺點，本文提出了一種基于航跡形狀約束的半監督k 均值聚類改進算法，利用少量標注信息指導未標注航跡完成聚類。

本文提出的基于航跡形狀約束的半監督K-means聚類改進算法，其中基于航跡形狀約束的思想是根據不同飛行目標的航跡形狀特點得來的。一般普通客機做直線飛行運動，而特殊偵查戰斗機做近似圓周、八字形或者更復雜的飛行運動。利用這一特點，本文通過曲線擬合的思想對航跡進行擬合來確定航跡的形狀。

1 確定航跡的形狀

航跡是由一系列帶有速度、位置信息、航向的點跡構成。航跡可能會因為一些外界因素造成數據丟失或者數據過大過小的情況。為了使這些異常點對整個航跡的誤差減小得到一條較穩定的航跡，我們考慮一系列去燥、剔除異常點、濾波等方法對航跡進行預處理。在航跡預處理后，應確定航跡的形狀，考慮到復雜的航跡在小范圍內可以用曲線擬合來逼近，本文結合最小二乘擬合方法確定航跡的形狀。

1.1 航跡的擬合

（1）基本直線擬合

給定N 個二維空間中的點，每個點用（x(i)，y(i)）來表示，最小二乘法進行直線擬合的基本思想是通過最小化下面的誤差函數來求取直線參數：

通過解二元一次方程組或者利用矩陣求逆運算，可以得到直線參數：

為此，我們擬合出了直線方程：y=b+kx

同時可以計算出擬合度Q1：

（2）圓擬合

給定N 個二維空間中的點，每個點用（x(i)，y(i)）來表示，最小二乘法進行圓擬合的基本思想是通過最小化下面的誤差函數來求取圓參數：

求取誤差函數對三個圓參數的偏導數，并令其值為0：

同理（1）可得：x0，y0，R，擬合度Q2。

1.2 航跡的形狀

具體實現步驟如下：

（1）確定航跡的直線y=kx+b 圓(x-x0)2+(y-y0)2-R2=0 參數。將航跡的點跡分別用最小二乘法直線、圓進行擬合（第1 章1.1 節），并得到直線參數（k，b，Q1），圓參數（x0，y0，R，Q2）。

（2）比較擬合度Q1、Q2 的大小。

（3）如果Q1

（4）如果Q1>=Q2，不能判斷航跡形狀。設定一個初始半徑R0，如果R

注：如果擬合成直線，則形狀標志為0；如果擬合成圓，則形狀標志為1。

2 歷史航跡的處理

2.1 航跡標注

本文采用半監督的思想對少量歷史航跡進行標記并定義其航跡意圖，標注信息包括：飛行目標的編號、類型、用途、起始地點等。航跡的標注根據標記信息是否相同可以分為兩種：同類航跡一次標注和多次標注。如果有兩條及以上的航跡標注信息相同，則要對這些有相同標記信息的航跡進行中心化處理，最終得到一條具有代表性的標記航跡。

2.2 航跡特征

歷史航跡數據由一系列帶有飛行編號、空間位置、運動速度、運動方向的點跡構成。為了更好地挖掘歷史航跡的特征信息，本文引入了2.2.1 節的特征參數。

2.2.1 特征集描述

各個特征參數代表的含義如下：

ID：航跡編號

Flag：航跡形狀標志（1 為圓，0 為直線）

ClusterNum：每類航跡的數目

avg_fx，avg_fy：航跡平均起始點位置

GH：航跡平均高度

GV：航跡平均速度

Gpx，Gpy：航跡平均中心點位置

GHS：航跡平均航向

GR：航跡平均半徑

Lables：航跡標注信息（包括：飛行目標的編號、類型、用途、起始地點）

注：當航跡不涉及某個特征參數時，該參數置為0。

2.2.2 特征提取

航跡特征分析是飛行目標意圖識別的關鍵之處。特征的選取好壞直接影響航跡意圖識別效果。

在一般簡單場景中，僅考慮飛行目標的空間位置、速度、航向等特征參數，就能完成簡單飛機航跡意圖的識別過程。但是在一些復雜場景中，例如一些做近似圓周、八字形或者更復雜的飛行運動的特殊偵查戰斗機，如果沒有考慮航跡的形狀特點，則航跡意圖識別對航跡的形狀不太敏感，識別效果將會不理想。為了克服這個缺點，本文引入了航跡形狀特征參數。

本文利用均值及曲線擬合的思想對歷史航跡數據總結航跡特征。首先，利用均值的思想，對每條航跡求得航跡平均速度、平均高度、平均起始點位置等。其次，利用曲線擬合的思想，通過“確定航跡形狀”算法（見第1 章第2 小節，得到每條航跡的航跡形狀標志參數及直線參數（k，b，Q1），圓參數（x0，y0，R，Q2）。如果形狀標志參數為0，則表示該條航跡擬合為直線；反之，為1 時，則表示該條航跡擬合為圓形。最后，將得到的航跡特征參數作為歷史航跡聚類分析的輸入，目的是將同類型管制意圖的航跡聚成一類，以便新航跡管制意圖的識別。

3 歷史航跡的聚類分析

本文描述的歷史航跡聚類是在航跡形狀的約束下，利用少量標記航跡數據，通過空間距離對航跡進行聚類的一個過程。航跡聚類的目的是為了進一步準確的對航跡進行分類與識別。針對航跡序列的長度不固定的特點，本文采用K-means 算法對航跡訓練樣本進行聚類。

3.1 航跡的空間距離

給定歐氏空間中航跡的兩點集A={a1,a2,…,an}，B={b1,b2,…,bm} ，它們之間的空間相似距離H 定義為：H(A,B)=min[h(A,B),h(B,A)]。

其中：

這里di,j是一條航跡上的第i 個點到另一條航跡上的第j 個點之間的歐氏距離。

3.2 基于航跡形狀約束的半監督K-means聚類改進算法

假設訓練航跡樣本為A={a1,a2,…,am}，其中每一個元素ai為一條航跡序列。用戶根據需求標注n(n

根據標記航跡樣本總結航跡特征，具體實現步驟如下：

（1）初始化聚類“中心”。用已標記的航跡集合B求得k 個聚類中心，C={c1,c2,…,ck}（k<=n）

（2）計算訓練航跡樣本A、聚類中心樣本C 中每條航跡序列的形狀、擬合斜率、擬合半徑等參數。（見第2章2.2.2 節）

（3）確定A 中每條航跡ai所屬的類。計算ai到C={c1,c2....ck}的空間距離，如果形狀相同且斜率、擬合半徑均在初始約束范圍內，則該航跡被分到與它距離最近的“聚類中心”所在的類。

（4）調整聚類“中心”。由步驟（3）可得到k 類聚類結果，對每一類，找出屬于該類的所有樣本，尋找一個新的聚類“中心”，使其到該類內所有樣本的距離之和最小。 Xj,i表示屬于第i 類的第j 個樣本，ni表示第i類中航跡的個數。

重復步驟（3）和（4），直到連續兩次的迭代結果（即聚類中心）不再發生變化。此時k 類聚類樣本就是最終聚類結果，各個類中的航跡屬于同一類航跡模式。

總結各類聚類樣本特征。對每類樣本分別計算特征集參數（見第2 章2.2.1 小節），并存到數據庫。

4 靜態航跡意圖的識別

航跡意圖識別就是在完成建立各個歷史標記航跡類的特征集數據庫后，將新的未標記航跡測試樣本代入數據庫中進行意圖識別的一個過程。

主要步驟如下：

啟動數據庫。

設定參數初始閾值，加載測試樣本航跡，并確定航跡的形狀。

（1）航跡意圖識別。通過航跡的形狀標志，識別數據庫中相同形狀標志的航跡參數信息。如果參數值在閾值范圍內，則識別成功，否則識別失敗。

（2）自動標注信息。如果測試樣本中航跡識別成功，則自動標注該航跡信息。

（3）更新數據庫。將測試樣本中識別到的航跡和數據庫中相應航跡重新計算特征集參數值，并更新數據庫。

5 仿真實驗

為了驗證本文提出基于航跡形狀約束的半監督K-means 聚類改進算法的有效性，本文用實驗4.1 對訓練樣本的航跡進行仿真實驗。實驗4.1 分別用文獻[1]和本文使用的聚類算法做對比實驗；試驗系統建立在1Gbyte內存的普通PC 上，仿真軟件采用VS2010、Qt 工具。飛行目標航跡的聚類與識別系統流程圖如圖1 所示。

圖1 流程圖

分別采用文獻[1]方法和本文方法對航跡進行聚類，選取500 條未標記航跡訓練樣本數據進行聚類仿真實驗，對其均值化如表1 所示。

表1 航跡訓練樣本數據

對部分航跡標記如圖2 所示，其中橙色字體表示航跡標記信息（航跡號、飛機型號、飛機用途、飛機始末地點），白色點表示航跡。

注：該實驗中選取的航跡均無拐點（斜率變化超過初始閾值）。

文獻[1]和本文聚類方法通過訓練樣本航跡生成數據庫特征集后，然后測試樣本再根據特征集用識別算法（見第4 章）對兩種方法的識別正確率進行比較。

圖2 航跡標注靜態展示圖

根據上述標注航跡信息，通過文獻1 和本文聚類方法將航跡訓練樣本進行聚類，得到部分數據庫中特征集如表2 所示。

表2 本文特征集

本實驗共選取了50 條測試樣本進行了仿真實驗，抽取了25 條較為典型的航跡進行分析。

測試樣本如表3 所示。

表3 測試樣本數據

將測試樣本航跡分別用兩種方法匹配如下：文獻[1]的展示圖如圖3。

圖3 文獻[1]航跡識別靜態展示圖

本文的展示圖如圖4。

圖4 本文航跡識別靜態展示圖

上述圖3、4 選取部分測試航跡樣本的識別情況作為展示。圖3 可以看出航跡編號為2、10、11、24 的航跡被正確識別；圖4 可以看出編號為1、6、7、9、10、11、23、24 的航跡被正確識別。

識別結果如表4 所示。

表4 識別率結果

從上面的實驗結論可以得到，本文采用的聚類方法的識別率比文獻[1]高。文獻[1]中的聚類方法在傳統方法上雖有了好的改進，即：在用距離進行聚類時，綜合考慮了目標的速度、航向的歐氏距離。但是，該聚類算法沒有考慮航跡的形狀特點，以至使測試樣本在進行意圖識別時，對航跡的形狀不太敏感。為了克服這個缺點，本文在此在聚類中引入了航跡形狀標志及形狀參數（直線的斜率、圓的中心點及半徑）等，大大提高了測試航跡樣本意圖識別的精準率。

6 結語

本文針對在海量航跡數據中，如何有效地總結出普通客機飛行航跡和特殊偵查飛行航跡的特征這一問題，提出了基于航跡形狀約束的半監督K-means 聚類改進算法，并通過對比實驗利用不同訓練、測試航跡樣本對該改進算法的高效性進行了驗證，實驗結果表明該算法是相對精準高效的。