何艷，王運(yùn)鋒

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

大數(shù)據(jù)時(shí)代，人們可以訪問(wèn)到各行各業(yè)的信息資源呈現(xiàn)出爆炸式的增長(zhǎng)，航空業(yè)也不例外。隨著航空業(yè)的迅速發(fā)展，航空公司的規(guī)模不斷擴(kuò)大，機(jī)隊(duì)數(shù)量的不斷增加，飛行目標(biāo)的航跡數(shù)據(jù)也越來(lái)越龐大復(fù)雜。面對(duì)龐大復(fù)雜的航跡數(shù)據(jù)，如何有效地利用不同管制意圖的歷史航跡特征，并對(duì)新的航跡意圖進(jìn)行識(shí)別已成為航空業(yè)領(lǐng)域的新穎之處。

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

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

本文提出的基于航跡形狀約束的半監(jiān)督K-means聚類改進(jìn)算法，其中基于航跡形狀約束的思想是根據(jù)不同飛行目標(biāo)的航跡形狀特點(diǎn)得來(lái)的。一般普通客機(jī)做直線飛行運(yùn)動(dòng)，而特殊偵查戰(zhàn)斗機(jī)做近似圓周、八字形或者更復(fù)雜的飛行運(yùn)動(dòng)。利用這一特點(diǎn)，本文通過(guò)曲線擬合的思想對(duì)航跡進(jìn)行擬合來(lái)確定航跡的形狀。

1 確定航跡的形狀

航跡是由一系列帶有速度、位置信息、航向的點(diǎn)跡構(gòu)成。航跡可能會(huì)因?yàn)橐恍┩饨缫蛩卦斐蓴?shù)據(jù)丟失或者數(shù)據(jù)過(guò)大過(guò)小的情況。為了使這些異常點(diǎn)對(duì)整個(gè)航跡的誤差減小得到一條較穩(wěn)定的航跡，我們考慮一系列去燥、剔除異常點(diǎn)、濾波等方法對(duì)航跡進(jìn)行預(yù)處理。在航跡預(yù)處理后，應(yīng)確定航跡的形狀，考慮到復(fù)雜的航跡在小范圍內(nèi)可以用曲線擬合來(lái)逼近，本文結(jié)合最小二乘擬合方法確定航跡的形狀。

1.1 航跡的擬合

（1）基本直線擬合

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

通過(guò)解二元一次方程組或者利用矩陣求逆運(yùn)算，可以得到直線參數(shù)：

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

同時(shí)可以計(jì)算出擬合度Q1：

（2）圓擬合

給定N 個(gè)二維空間中的點(diǎn)，每個(gè)點(diǎn)用（x(i)，y(i)）來(lái)表示，最小二乘法進(jìn)行圓擬合的基本思想是通過(guò)最小化下面的誤差函數(shù)來(lái)求取圓參數(shù)：

求取誤差函數(shù)對(duì)三個(gè)圓參數(shù)的偏導(dǎo)數(shù)，并令其值為0：

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

1.2 航跡的形狀

具體實(shí)現(xiàn)步驟如下：

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

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

（3）如果Q1

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

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

2 歷史航跡的處理

2.1 航跡標(biāo)注

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

2.2 航跡特征

歷史航跡數(shù)據(jù)由一系列帶有飛行編號(hào)、空間位置、運(yùn)動(dòng)速度、運(yùn)動(dòng)方向的點(diǎn)跡構(gòu)成。為了更好地挖掘歷史航跡的特征信息，本文引入了2.2.1 節(jié)的特征參數(shù)。

2.2.1 特征集描述

各個(gè)特征參數(shù)代表的含義如下：

ID：航跡編號(hào)

Flag：航跡形狀標(biāo)志（1 為圓，0 為直線）

ClusterNum：每類航跡的數(shù)目

avg_fx，avg_fy：航跡平均起始點(diǎn)位置

GH：航跡平均高度

GV：航跡平均速度

Gpx，Gpy：航跡平均中心點(diǎn)位置

GHS：航跡平均航向

GR：航跡平均半徑

Lables：航跡標(biāo)注信息（包括：飛行目標(biāo)的編號(hào)、類型、用途、起始地點(diǎn)）

注：當(dāng)航跡不涉及某個(gè)特征參數(shù)時(shí)，該參數(shù)置為0。

2.2.2 特征提取

航跡特征分析是飛行目標(biāo)意圖識(shí)別的關(guān)鍵之處。特征的選取好壞直接影響航跡意圖識(shí)別效果。

在一般簡(jiǎn)單場(chǎng)景中，僅考慮飛行目標(biāo)的空間位置、速度、航向等特征參數(shù)，就能完成簡(jiǎn)單飛機(jī)航跡意圖的識(shí)別過(guò)程。但是在一些復(fù)雜場(chǎng)景中，例如一些做近似圓周、八字形或者更復(fù)雜的飛行運(yùn)動(dòng)的特殊偵查戰(zhàn)斗機(jī)，如果沒有考慮航跡的形狀特點(diǎn)，則航跡意圖識(shí)別對(duì)航跡的形狀不太敏感，識(shí)別效果將會(huì)不理想。為了克服這個(gè)缺點(diǎn)，本文引入了航跡形狀特征參數(shù)。

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

3 歷史航跡的聚類分析

本文描述的歷史航跡聚類是在航跡形狀的約束下，利用少量標(biāo)記航跡數(shù)據(jù)，通過(guò)空間距離對(duì)航跡進(jìn)行聚類的一個(gè)過(guò)程。航跡聚類的目的是為了進(jìn)一步準(zhǔn)確的對(duì)航跡進(jìn)行分類與識(shí)別。針對(duì)航跡序列的長(zhǎng)度不固定的特點(diǎn)，本文采用K-means 算法對(duì)航跡訓(xùn)練樣本進(jìn)行聚類。

3.1 航跡的空間距離

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

其中：

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

3.2 基于航跡形狀約束的半監(jiān)督K-means聚類改進(jìn)算法

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

根據(jù)標(biāo)記航跡樣本總結(jié)航跡特征，具體實(shí)現(xiàn)步驟如下：

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

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

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

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

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

總結(jié)各類聚類樣本特征。對(duì)每類樣本分別計(jì)算特征集參數(shù)（見第2 章2.2.1 小節(jié)），并存到數(shù)據(jù)庫(kù)。

4 靜態(tài)航跡意圖的識(shí)別

航跡意圖識(shí)別就是在完成建立各個(gè)歷史標(biāo)記航跡類的特征集數(shù)據(jù)庫(kù)后，將新的未標(biāo)記航跡測(cè)試樣本代入數(shù)據(jù)庫(kù)中進(jìn)行意圖識(shí)別的一個(gè)過(guò)程。

主要步驟如下：

啟動(dòng)數(shù)據(jù)庫(kù)。

設(shè)定參數(shù)初始閾值，加載測(cè)試樣本航跡，并確定航跡的形狀。

（1）航跡意圖識(shí)別。通過(guò)航跡的形狀標(biāo)志，識(shí)別數(shù)據(jù)庫(kù)中相同形狀標(biāo)志的航跡參數(shù)信息。如果參數(shù)值在閾值范圍內(nèi)，則識(shí)別成功，否則識(shí)別失敗。

（2）自動(dòng)標(biāo)注信息。如果測(cè)試樣本中航跡識(shí)別成功，則自動(dòng)標(biāo)注該航跡信息。

（3）更新數(shù)據(jù)庫(kù)。將測(cè)試樣本中識(shí)別到的航跡和數(shù)據(jù)庫(kù)中相應(yīng)航跡重新計(jì)算特征集參數(shù)值，并更新數(shù)據(jù)庫(kù)。

5 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出基于航跡形狀約束的半監(jiān)督K-means 聚類改進(jìn)算法的有效性，本文用實(shí)驗(yàn)4.1 對(duì)訓(xùn)練樣本的航跡進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)4.1 分別用文獻(xiàn)[1]和本文使用的聚類算法做對(duì)比實(shí)驗(yàn)；試驗(yàn)系統(tǒng)建立在1Gbyte內(nèi)存的普通PC 上，仿真軟件采用VS2010、Qt 工具。飛行目標(biāo)航跡的聚類與識(shí)別系統(tǒng)流程圖如圖1 所示。

圖1 流程圖

分別采用文獻(xiàn)[1]方法和本文方法對(duì)航跡進(jìn)行聚類，選取500 條未標(biāo)記航跡訓(xùn)練樣本數(shù)據(jù)進(jìn)行聚類仿真實(shí)驗(yàn)，對(duì)其均值化如表1 所示。

表1 航跡訓(xùn)練樣本數(shù)據(jù)

對(duì)部分航跡標(biāo)記如圖2 所示，其中橙色字體表示航跡標(biāo)記信息（航跡號(hào)、飛機(jī)型號(hào)、飛機(jī)用途、飛機(jī)始末地點(diǎn)），白色點(diǎn)表示航跡。

注：該實(shí)驗(yàn)中選取的航跡均無(wú)拐點(diǎn)（斜率變化超過(guò)初始閾值）。

文獻(xiàn)[1]和本文聚類方法通過(guò)訓(xùn)練樣本航跡生成數(shù)據(jù)庫(kù)特征集后，然后測(cè)試樣本再根據(jù)特征集用識(shí)別算法（見第4 章）對(duì)兩種方法的識(shí)別正確率進(jìn)行比較。

圖2 航跡標(biāo)注靜態(tài)展示圖

根據(jù)上述標(biāo)注航跡信息，通過(guò)文獻(xiàn)1 和本文聚類方法將航跡訓(xùn)練樣本進(jìn)行聚類，得到部分?jǐn)?shù)據(jù)庫(kù)中特征集如表2 所示。

表2 本文特征集

本實(shí)驗(yàn)共選取了50 條測(cè)試樣本進(jìn)行了仿真實(shí)驗(yàn)，抽取了25 條較為典型的航跡進(jìn)行分析。

測(cè)試樣本如表3 所示。

表3 測(cè)試樣本數(shù)據(jù)

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

圖3 文獻(xiàn)[1]航跡識(shí)別靜態(tài)展示圖

本文的展示圖如圖4。

圖4 本文航跡識(shí)別靜態(tài)展示圖

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

識(shí)別結(jié)果如表4 所示。

表4 識(shí)別率結(jié)果

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

6 結(jié)語(yǔ)

本文針對(duì)在海量航跡數(shù)據(jù)中，如何有效地總結(jié)出普通客機(jī)飛行航跡和特殊偵查飛行航跡的特征這一問(wèn)題，提出了基于航跡形狀約束的半監(jiān)督K-means 聚類改進(jìn)算法，并通過(guò)對(duì)比實(shí)驗(yàn)利用不同訓(xùn)練、測(cè)試航跡樣本對(duì)該改進(jìn)算法的高效性進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明該算法是相對(duì)精準(zhǔn)高效的。