基于輪廓系數(shù)的參數(shù)無關(guān)空中交通軌跡聚類方法

孫石磊 王超 趙元棣

摘 要：為消除專家經(jīng)驗(yàn)的主觀性、避免依賴軌跡特征并且減輕實(shí)驗(yàn)調(diào)參的負(fù)擔(dān)，提出一種基于輪廓系數(shù)的參數(shù)無關(guān)聚類分析（PICBASIC）算法。首先，比較了現(xiàn)有基于歐氏距離的航跡配對(duì)方法，并且建立基于動(dòng)態(tài)時(shí)間彎曲（DWT）距離和高斯核函數(shù)的軌跡相似度計(jì)算模型;其次，利用譜聚類對(duì)空中交通軌跡進(jìn)行聚類劃分;最后，提出一種基于輪廓系數(shù)的最佳簇?cái)?shù)尋優(yōu)方法，并且其具有對(duì)聚類結(jié)果量化評(píng)價(jià)功能。利用真實(shí)進(jìn)場(chǎng)軌跡進(jìn)行實(shí)驗(yàn)驗(yàn)證，PICBASIC判斷將28L跑道的365條軌跡聚為5個(gè)簇，28R跑道的530條軌跡聚為6個(gè)簇時(shí)聚類質(zhì)量最佳，平均輪廓系數(shù)分別為0.809-9和0.805-6。相同實(shí)驗(yàn)數(shù)據(jù)條件下，PICBASIC與MeanShift聚類的平均輪廓系數(shù)差異率分別為-1.23% 和0.19%。實(shí)驗(yàn)結(jié)果表明：PICBASIC包容軌跡的速度和長(zhǎng)度差異，全程無需人工指導(dǎo)或?qū)嶒?yàn)調(diào)參，而且能夠篩除異常軌跡對(duì)聚類質(zhì)量的不利影響。

關(guān)鍵詞：空中交通軌跡;聚類分析;輪廓系數(shù);譜聚類;動(dòng)態(tài)時(shí)間彎曲;高斯核函數(shù);參數(shù)無關(guān)

中圖分類號(hào)： TP181

文獻(xiàn)標(biāo)志碼：A

Parameter independent clustering of air traffic trajectory based on silhouette coefficient

SUN Shilei*， WANG Chao，ZHAO Yuandi

Research Base of Air Traffic Management， Civil Aviation University of China， Tianjin 300300， China

Abstract：

In order to eliminate the subjectivity of expert experience， get rid of the dependence on trajectory characteristics and reduce the burden of experimental parameter tuning， a Parameter Independent Clustering BAsed on SIlhoutte Coefficient （PICBASIC） algorithm was proposed. Firstly， existing Euclidean distance based track pairing methods were compared， and a trajectory similarity calculation model based on Dynamic Time Warping （DWT） distance and Gaussian kernel function was established. Secondly， the air traffic trajectories were partitioned and clustered by spectral clustering. Finally， a cluster number optimization method based on silhouette coefficient was proposed， and it had the function of quantitative evaluation of clustering results. Experiments were carried out by using real arrival trajectories to verify the validity of the proposed algorithm. PICBASIC judged that the clustering quality would be respectively optimum if the 365 trajectories of runway 28L were clustered into 5 clusters and the 530 trajectories of runway 28R were clustered into 6 clusters. The average silhouette coefficients in the two situations were respectively 0.809-9 and 0.805-6. Under the same experimental conditions， the difference rates of average silhouette coefficient between PICBASIC and MeanShift clustering were respectively -1.23% and 0.19%. The experimental results demonstrate that PICBASIC can tolerate the speed and length differences of trajectories， dispense with manual guidance or experimental parameter tuning and filter out the adverse impact of abnormal trajectories on the clustering quality.

Key words：

air traffic trajectory; clustering analysis; silhouette coefficient; spectral clustering; Dynamic Time Warping （DTW）; Gaussian kernel function; parameter independent

0?引言

針對(duì)空中交通軌跡的聚類分析是提高進(jìn)離場(chǎng)程序的管制適用性、增強(qiáng)空域扇區(qū)劃分科學(xué)性的有效技術(shù)手段[1]。但是，當(dāng)前絕大多數(shù)聚類算法都需要一個(gè)甚至多個(gè)顯式或隱式的輸入?yún)?shù)，它們的聚類結(jié)果通常嚴(yán)重依賴于這些參數(shù)[2]。確定合理的參數(shù)是困難的，一般需要根據(jù)專家經(jīng)驗(yàn)[3]、軌跡數(shù)據(jù)特點(diǎn)[4-6]或者多次實(shí)驗(yàn)[1，6-9]獲得，其中：專家經(jīng)驗(yàn)判斷參數(shù)依賴于專家主觀經(jīng)驗(yàn)，缺乏客觀的量化分析指標(biāo);基于軌跡數(shù)據(jù)特點(diǎn)設(shè)定參數(shù)，受軌跡訓(xùn)練樣本的飛行速度、交通流量、空域特征等影響，算法局限性強(qiáng)，普適性難以保證;多次實(shí)驗(yàn)的方法顯然加重了用戶的負(fù)擔(dān)，而且實(shí)驗(yàn)參數(shù)的候選值一般在某個(gè)指定范圍和變化步長(zhǎng)內(nèi)選取，并不是理論最優(yōu)值。

針對(duì)以上問題，本文提出一種基于輪廓系數(shù)的參數(shù)無關(guān)聚類分析（Parameter Independent Clustering BAsed on SIlhouette Coefficient，PICBASIC）算法。首先，分析空中交通軌跡的數(shù)據(jù)結(jié)構(gòu); 然后，將軌跡作為一個(gè)整體，通過局部縮放時(shí)間維求出軌跡間的動(dòng)態(tài)時(shí)間彎曲（Dynamic Time Warping，DTW）距離，再應(yīng)用高斯核函數(shù)變換獲得軌跡相似度矩陣;接下來，利用譜聚類提取出相似度矩陣的特征子空間，并對(duì)聚類結(jié)果基于輪廓系數(shù)進(jìn)行量化評(píng)價(jià)，進(jìn)而確定最佳簇?cái)?shù);最后，通過終端區(qū)真實(shí)空中交通軌跡樣本對(duì)模型和方法進(jìn)行驗(yàn)證和分析。

1?空中交通軌跡的特征與表示

根據(jù)文獻(xiàn)[5]的定義，航跡（track）是指某時(shí)刻監(jiān)視設(shè)備記錄的某航空器的某個(gè)空間位置、速度、航向等特征。軌跡（trajectory）是指在一段時(shí)間內(nèi)，航空器飛行經(jīng)過的歷史痕跡，由一系列按照時(shí)序順序排列的離散航跡組成。

通常，軌跡集可表示為：

TS={T1，T2，…，Ti，…，Tn}

式中：Ti為第i條軌跡，n為軌跡總數(shù)。

軌跡Ti可用航跡的數(shù)據(jù)集表示為：

Ti={pi1，pi2，…，pij，…，pim}

式中：pij表示第i條軌跡中第j個(gè)航跡，m為航跡總數(shù)。

每一個(gè)航跡pij定義為一個(gè)4維向量，即：

pij={x，y，z，t}

式中：x、y、z、t分別表示航跡pij的空間位置橫坐標(biāo)、空間位置縱坐標(biāo)、飛行高度和記錄時(shí)間。

2?參數(shù)無關(guān)空中交通軌跡聚類

2.1?定義軌跡的DTW距離

空中交通軌跡聚類分析關(guān)鍵是選擇合適的不同軌跡間的相似性度量方法[10]。本文采用歐氏距離來度量軌跡間的相似性，因?yàn)樗庇^性最強(qiáng)，最易被理解與接受。

在求解軌跡間距離過程中，首先需要將不同軌跡的航跡按照某種規(guī)則配對(duì)，然后以航跡點(diǎn)對(duì)的歐氏距離作為軌跡間的距離。圖1表示了三種基于航跡點(diǎn)對(duì)歐氏距離的軌跡相似性度量方法。

圖1（a）方法直接使用兩條軌跡順序航跡點(diǎn)對(duì)之間的距離和除以配對(duì)的航跡數(shù)[11]。該方法完全沒有考慮航空器速度的差別，順序航跡點(diǎn)對(duì)的歐氏距離有可能成為兩條軌跡之間的斜距，增大了空間位置相似的軌跡的距離。圖1（b）方法在圖1（a）基礎(chǔ)上進(jìn)行改進(jìn)，在計(jì)算每一對(duì)航跡距離時(shí)，同時(shí)選取其前后最相近的兩個(gè)航跡進(jìn)行計(jì)算，獲取在此位置附近的5段距離之間的最短歐氏距離[3]。圖1（b）方法考慮了航空器速度的差別，但是速度差大小與選取最相鄰航跡個(gè)數(shù)的關(guān)系沒有深入研究，在兩條軌跡的航跡疏密具有顯著區(qū)別時(shí)，仍然無法完全避免圖1（a）的問題。圖1（c）方法在圖1（b）基礎(chǔ)上進(jìn)一步改進(jìn)，計(jì)算局部航跡點(diǎn)與線的法向距離作為兩條軌跡間的距離[12]。圖1（c）方法直觀上縮短了圖1（b）方法的局部歐氏距離，但是同樣存在圖1（b）的問題。而且，三種方法均期望進(jìn)行比較的兩條軌跡的航跡數(shù)目相同，否則較長(zhǎng)的軌跡會(huì)在無法配對(duì)的航跡處被截?cái)?，信息損失較高。

現(xiàn)實(shí)中，大部分空中交通軌跡都不等長(zhǎng)，而且由于機(jī)型和飛行性能的區(qū)別，航空器飛行的速度不同導(dǎo)致不同軌跡的航跡疏密不同。所以，本文利用動(dòng)態(tài)時(shí)間彎曲距離的特性來表示軌跡間的距離。首先，DTW距離對(duì)相比較的兩條軌跡的長(zhǎng)度不作要求，即兩條軌跡的長(zhǎng)度既可以是相等的也可以是不相等的[13]。其次，在保證航跡順序不變的前提下，基于DTW距離的方法通過重復(fù)部分航跡來完成時(shí)間維的局部縮放，尋找兩條軌跡之間的最佳對(duì)齊方式。軌跡間計(jì)算DTW距離的航跡配對(duì)原理如圖2[14]所示。

DTW距離計(jì)算方法[14]為：

DTW（Ti，Tj）=

0，mi=mj=0

∞，mi=0ormj=0

dist（pi1，pj1）+min{DTW（Rest（Ti），Rest（Tj）），

DTW（Rest（Ti），Tj），DTW（Ti，Rest）Tj））}，

mi≠0，mj≠0 （1）

式中：DTW（Ti，Tj）表示兩條軌跡Ti與Tj間的DTW距離;mi和mj分別代表軌跡Ti與Tj的航跡個(gè)數(shù);dist（pi1，pj1） 表示兩個(gè)航跡pi1和pj1之間的歐氏距離;Rest（Ti）和Rest（Tj）分別表示軌跡Ti與Tj去掉第一個(gè)航跡pi1和pj1所得的剩余軌跡區(qū)間。

根據(jù)式（1），如果兩條軌跡均存在航跡，則采用遞歸的方式求取最小歐氏距離作為DTW距離，在這個(gè)過程中會(huì)產(chǎn)生航跡的最優(yōu)對(duì)應(yīng)關(guān)系。

實(shí)踐中，航跡空間位置的橫、縱坐標(biāo)與高度坐標(biāo)的數(shù)值范圍可能存在較大差異，若不做處理直接計(jì)算歐氏距離，則數(shù)值范圍小的坐標(biāo)對(duì)航跡空間距離的影響程度會(huì)降低。此時(shí)可將三維坐標(biāo)逐個(gè)歸一化，再計(jì)算航跡間歐氏距離。例如，高度坐標(biāo)的歸一化，如式（2）所示：

znorm=z-zminzmax-zmin（2）

進(jìn)一步構(gòu)建軌跡集TS的距離矩陣R，其元素rij表示軌跡Ti和Tj之間的距離，計(jì)算方法如式（3）所示。R為對(duì)稱方陣。

rij=0，i=j2×DTW（Ti，Tj）mi+mj，i≠j （3）

2.2?基于高斯核函數(shù)構(gòu)造相似度矩陣

軌跡間的距離越小，相似度越高;反之，相似度越低。從距離矩陣到相似度矩陣的轉(zhuǎn)化采用高斯核函數(shù)，因?yàn)樗軌蛲怀鲕壽E的差異性，顯著降低空間距離遠(yuǎn)的軌跡相似度，有利于提高聚類質(zhì)量。高斯核函數(shù)的基本形式如式（4）所示：

K（xi，xj）=exp（-‖xi-xj‖2β）（4）

式中：‖xi-xj‖2為xi和xj的2范數(shù)，β為帶寬參數(shù)，控制著高斯核函數(shù)的局部作用范圍。

高斯核函數(shù)的結(jié)果對(duì)參數(shù)β敏感，本文利用文獻(xiàn)[15]的方法選擇β，計(jì)算方法如式（5）所示，無需任何領(lǐng)域知識(shí)或試錯(cuò)實(shí)驗(yàn)，僅僅取決于數(shù)據(jù)樣本集自身特征。

β≈σ2/2.6，λ≤0.01σ2L（λ），0.01<λ<100λσ2=μ2，λ≥100 （5）

式中：σ2是數(shù)據(jù)樣本集的方差， μ是均值，參數(shù)λ=（μ/σ）2，L（λ）是關(guān)于λ的函數(shù)。

構(gòu)建相似度矩陣S，其元素sij表示軌跡Ti和Tj的相似度，計(jì)算方法如式（6）所示：

sij=0，i=jexp[-r2ij/β]，i≠j（6）

S為對(duì)稱方陣，且已歸一化。重構(gòu)距離矩陣，記為R′， 其元素rij′表示軌跡Ti和Tj的距離，計(jì)算方法如式（7）所示：

rij′=1-sij（7）

2.3?構(gòu)造譜聚類的拉普拉斯矩陣

譜聚類的聚類質(zhì)量一般優(yōu)于傳統(tǒng)聚類算法[16]，而且，譜聚類只需確定“聚類簇?cái)?shù)”這唯一的參數(shù)，所以，本文采用譜聚類構(gòu)造參數(shù)無關(guān)的空中交通軌跡聚類方法PICBASIC。

譜聚類算法建立在圖論中的譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題。首先構(gòu)造無向加權(quán)圖G=（V，E），其中每個(gè)頂點(diǎn)vi代表一條軌跡，每條邊eij賦予權(quán)重為軌跡Ti和Tj的相似度sij。于是，軌跡聚類轉(zhuǎn)化為對(duì)該圖頂點(diǎn)的劃分問題，使不同子圖之間的邊具有低權(quán)重（即不同簇的軌跡相似度低），而子圖內(nèi)的邊具有高權(quán)重（即同簇內(nèi)軌跡相似度高）。

然后構(gòu)造度矩陣D，D為對(duì)角矩陣，對(duì)角線元素

dii=∑nj=1sij

最后構(gòu)造正則化的拉普拉斯（Laplacian）矩陣L[16]：

L=D-12（D-S）D-12

2.4?基于輪廓系數(shù)確定最佳簇?cái)?shù)

經(jīng)典譜聚類算法需要知曉最終聚類的簇?cái)?shù)，設(shè)為k; 然后對(duì)L求前k個(gè)最小特征值及對(duì)應(yīng)的特征向量，構(gòu)造特征子空間; 最后調(diào)用Kmeans聚類算法對(duì)特征子空間進(jìn)行聚類。

文獻(xiàn)[5，16]利用特征向量最大譜系值所對(duì)應(yīng)的下標(biāo)作為簇?cái)?shù)k，但是，若數(shù)據(jù)集之間存在較多相互重疊部分，會(huì)出現(xiàn)有2～3個(gè)數(shù)值相差不大的較大譜隙值，較難確定合理的簇?cái)?shù)，需要結(jié)合領(lǐng)域知識(shí)或者專家經(jīng)驗(yàn)判斷。

最佳的簇?cái)?shù)本質(zhì)上要求的是最佳的聚類質(zhì)量，使得簇內(nèi)的對(duì)象相似度最高，不同簇的對(duì)象相似度最低。驗(yàn)證聚類結(jié)果的方法包括分析、實(shí)驗(yàn)、評(píng)價(jià)和舉例[10]。本文利用輪廓系數(shù)[17]作為對(duì)空中交通軌跡聚類結(jié)果的評(píng)價(jià)。軌跡間的距離由式（7）計(jì)算。每條軌跡的輪廓系數(shù)取值在-1～1，值越大表示該條軌跡所在簇越緊湊，且遠(yuǎn)離其他簇。為了度量在完整軌跡集上的聚類質(zhì)量，計(jì)算所有軌跡的輪廓系數(shù)的平均值，如式（8）所示：

savg=1n∑ni=1s（Ti）（8）

式中：savg為當(dāng)簇?cái)?shù)為k時(shí)的軌跡集平均輪廓系數(shù)，s（Ti）為軌跡Ti的輪廓系數(shù)，n為軌跡總數(shù)。

直觀上，增加簇?cái)?shù)似乎有助于降低每個(gè)簇內(nèi)的軌跡平均距離，因?yàn)橛袡C(jī)會(huì)形成更多稠密的簇，簇中軌跡更為相似。然而由于邊際效應(yīng)，劃分太多的簇會(huì)導(dǎo)致降低簇內(nèi)軌跡平均距離的效果下降。因此，PICBASIC預(yù)先設(shè)定一個(gè)充分大的簇?cái)?shù)kmax，然后計(jì)算從2～kmax范圍內(nèi)各個(gè)候選簇?cái)?shù)k的平均輪廓系數(shù)savg。利用肘方法（elbow method）思想，使用savg關(guān)于k的曲線的拐點(diǎn)作為最佳簇?cái)?shù)[18]。

實(shí)際情況下，空中交通軌跡樣本集中常包含航空器脫離標(biāo)準(zhǔn)進(jìn)離場(chǎng)航線而形成的異常軌跡。當(dāng)候選簇?cái)?shù)k不合理時(shí)，異常軌跡會(huì)被錯(cuò)誤分類到某正常軌跡簇中，導(dǎo)致savg顯著降低。除非異常軌跡被單獨(dú)聚類為一個(gè)簇或幾個(gè)簇，savg才會(huì)增大。所以，應(yīng)用輪廓系數(shù)作為聚類結(jié)果的評(píng)價(jià)量化指標(biāo)，能夠有效篩除將異常軌跡混入正常軌跡簇的情況，提高聚類質(zhì)量。

2.5?PICBASIC算法步驟

輸入?空中交通軌跡集TS，充分大的簇?cái)?shù)kmax。

輸出?最佳簇?cái)?shù)kopt，最佳聚類Copt，最大平均輪廓系數(shù)smax。

程序前

1）

歸一化TS的每個(gè)航跡pij;

2）

計(jì)算每?jī)蓷l軌跡Ti和Tj之間的DTW距離;

3）

計(jì)算rij，構(gòu)建距離矩陣R;

4）

計(jì)算R的方差σ2、均值μ、參數(shù)λ、L（λ），進(jìn)而計(jì)算β;

5）

計(jì)算sij，構(gòu)建相似度矩陣S;

6）

計(jì)算rij′，重構(gòu)距離矩陣R′;

7）

初始化kopt=0;

8）

初始化smax=-1;

9）

for k=2 to kmax

10）

聚類C=spectral_clustering（TS， k）;

11）

計(jì)算平均輪廓系數(shù)savg;

12）

if savg>smaxthen

13）

smax=savg;

14）

kopt=k;

15）

Copt=C;

16）

end if

17）

end for

程序后

3?實(shí)例分析

為驗(yàn)證PICBASIC的合理性，選擇舊金山國(guó)際機(jī)場(chǎng)連續(xù)48h 的真實(shí)進(jìn)場(chǎng)空中交通軌跡[19]進(jìn)行實(shí)驗(yàn)，其中28L跑道共365條軌跡，28R跑道共530條軌跡，未剔除任何異常軌跡，運(yùn)用Matlab軟件進(jìn)行聚類分析。

3.1?高斯核函數(shù)的參數(shù)尋優(yōu)

由軌跡距離矩陣R，根據(jù)式（5）或文獻(xiàn)[20]，可確定高斯核函數(shù)的帶寬參數(shù)β。相關(guān)參數(shù)如表1所示。

3.2?確定最佳簇?cái)?shù)

初選設(shè)定充分大的候選簇?cái)?shù)范圍為2到30，繪制平均輪廓系數(shù)關(guān)于候選簇?cái)?shù)的曲線，如圖3所示?？梢姡黾哟?cái)?shù)并不能增大平均輪廓系數(shù)，反而隨簇?cái)?shù)增加，平均輪廓系數(shù)呈明顯下降趨勢(shì)。當(dāng)簇?cái)?shù)不合理時(shí)，會(huì)極大降低平均輪廓系數(shù)。由圖3（a）可知，當(dāng)簇?cái)?shù)為5時(shí)，平均輪廓系數(shù)達(dá)到最大值0.809-9，故確定最佳簇?cái)?shù)kopt為5。同理，由圖3（b）可知，kopt為6，此時(shí)smax達(dá)到0.805-6。

應(yīng)該指出，由于Kmeans算法具有一定的隨機(jī)性，每次聚類的結(jié)果會(huì)存在部分差異。但經(jīng)多次實(shí)驗(yàn)驗(yàn)證，平均輪廓系數(shù)關(guān)于候選簇?cái)?shù)的變化趨勢(shì)是穩(wěn)定的，最佳簇?cái)?shù)與最大平均輪廓系數(shù)也是穩(wěn)定的。即使由于Kmeans算法的隨機(jī)性，導(dǎo)致某次聚類產(chǎn)生了不佳的結(jié)果，由于PICBASIC利用輪廓系數(shù)同時(shí)對(duì)聚類結(jié)果進(jìn)行量化評(píng)價(jià)，能夠幫助用戶有效地識(shí)別和剔除該次不佳聚類。

通常終端區(qū)內(nèi)空中交通軌跡的盛行流會(huì)符合該機(jī)場(chǎng)的標(biāo)準(zhǔn)儀表進(jìn)離場(chǎng)程序，個(gè)別情況由于惡劣天氣和流量控制會(huì)出現(xiàn)等待、繞飛、返航或備降，所以最佳簇?cái)?shù)一般不會(huì)與原有進(jìn)離場(chǎng)飛行程序數(shù)量相差很大[5]。如果結(jié)合空域結(jié)構(gòu)知識(shí)，參考機(jī)場(chǎng)跑道的標(biāo)準(zhǔn)儀表進(jìn)離場(chǎng)程序數(shù)量，可適當(dāng)縮減最佳簇?cái)?shù)尋優(yōu)范圍，提高算法運(yùn)行效率。

3.3?聚類結(jié)果與分析

28L和28R跑道進(jìn)場(chǎng)空中交通軌跡聚類結(jié)果如圖4所示，每個(gè)簇用不同線形區(qū)分。

由圖4（a）可見28L跑道所有進(jìn)場(chǎng)軌跡被聚類為5個(gè)簇，其中進(jìn)場(chǎng)方向分別為西南、正南、東北的軌跡被劃分為同一個(gè)簇，區(qū)分度明顯，但西北方向進(jìn)場(chǎng)軌跡卻被劃分為2個(gè)簇。再參考圖4（b）可知西北方向進(jìn)場(chǎng)軌跡的起始進(jìn)場(chǎng)飛行高度存在高低之分，因此被劃分為2個(gè)簇。28R和28L跑道進(jìn)場(chǎng)軌跡的走向、飛行高度和形態(tài)等具有較高的相似度，聚類結(jié)果也相似。由圖4（c）和圖4（d）可見，28R跑道所有進(jìn)場(chǎng)軌跡被聚類為6個(gè)簇，其中少數(shù)幾條低飛行高度的異常軌跡被聚為一簇，該種聚類方式避免了異常軌跡對(duì)其他簇聚合度的破壞，能有效提高平均輪廓系數(shù)。

4?與其他聚類算法對(duì)比

在使用相同實(shí)驗(yàn)數(shù)據(jù)的情況下，選取文獻(xiàn)[1]中MeanShift聚類與PICBASIC進(jìn)行對(duì)比分析。文獻(xiàn)[1]方法非參數(shù)無關(guān)，無法識(shí)別最佳簇?cái)?shù)，為了方便比較，人為指定其簇?cái)?shù)與PICBASIC按照最大平均輪廓系數(shù)確定的最佳簇?cái)?shù)相同。此外，文獻(xiàn)[1]方法包括3個(gè)重要的參數(shù)需要設(shè)定，分別是采樣點(diǎn)數(shù)、主成分個(gè)數(shù)、帶寬。為獲得滿意的聚類結(jié)果，多次實(shí)驗(yàn)調(diào)參后具體參數(shù)值詳見表2。

聚類結(jié)果如圖5所示。與圖4相比，相似之處在于稠密的、大致相同進(jìn)場(chǎng)方向的軌跡均被聚為一簇。但兩次聚類結(jié)果也存在些許差異。由圖5（a）和圖5（b）可見，文獻(xiàn)[1]方法將28L跑道西北方向高低兩個(gè)飛行高度進(jìn)場(chǎng)的軌跡劃分為同一個(gè)簇; 由圖5（c）和圖5（d）可見，文獻(xiàn)[1]方法依然將28R跑道西北方向高低兩個(gè)飛行高度進(jìn)場(chǎng)的軌跡劃分為同一個(gè)簇，而且把東側(cè)進(jìn)場(chǎng)軌跡劃分為正東和東北兩個(gè)簇。此外，個(gè)別異常軌跡被兩種方法劃分到不同的簇。

為比較兩種方法的聚類質(zhì)量，統(tǒng)一采用平均輪廓系數(shù)進(jìn)行評(píng)價(jià)，結(jié)果如表3所示。

PICBASIC與文獻(xiàn)[1]方法的平均輪廓系數(shù)差異很小，證明應(yīng)用PICBASIC得到的聚類結(jié)果具有較高的可信度，而且聚類質(zhì)量較好。但由于PICBASIC參數(shù)無關(guān)，可避免文獻(xiàn)[1]方法中人工指導(dǎo)聚類簇?cái)?shù)和多次實(shí)驗(yàn)調(diào)參，具有更強(qiáng)的客觀性、普適性和更低的用戶負(fù)擔(dān)。

5?結(jié)語

本文從分析空中交通軌跡的相似性度量出發(fā)，針對(duì)其聚類問題展開研究，提出一種基于輪廓系數(shù)評(píng)價(jià)的參數(shù)無關(guān)聚類方法，得到如下結(jié)論：

1）PICBASIC基于DTW距離定義軌跡間的相似度，具有歐氏距離直觀性強(qiáng)、可信度高的優(yōu)點(diǎn)，而且包容軌跡的速度和長(zhǎng)度差異。

2）PICBASIC運(yùn)算全程無需領(lǐng)域知識(shí)或人工經(jīng)驗(yàn)確定任何參數(shù)，提高了算法普適性，增強(qiáng)了聚類結(jié)果客觀性。

3）PICBASIC對(duì)每次軌跡聚類的結(jié)果提供量化評(píng)價(jià)指標(biāo)，有利于比較聚類質(zhì)量，降低Kmeans算法隨機(jī)性的影響。

未來的研究工作包括在軌跡相似性度量中增加時(shí)間（航班繁忙時(shí)段或空閑時(shí)段）維度、剔除異常軌跡、以機(jī)型為指定條件進(jìn)行更細(xì)粒度的軌跡聚類分析等，并在此基礎(chǔ)上進(jìn)一步評(píng)估和優(yōu)化終端區(qū)飛行程。

參考文獻(xiàn) （References）

[1]趙元棣，王超，李善梅，等. 基于重采樣的終端區(qū)飛行軌跡可信聚類方法[J]. 西南交通大學(xué)學(xué)報(bào)， 2017， 52（4）：817-825.（ZHAO Y D， WANG C， LI S M， et al. Dependable clustering method of flight trajectory in terminal area based on resampling[J]. Journal of Southwest Jiaotong University， 2017， 52（4）： 817-825.）

[2]HOU J， LIU W. Parameter independent clustering based on dominant sets and cluster merging[J]. Information Sciences， 2017， 405： 1-17.

[3]王超，徐肖豪，王飛. 基于航跡聚類的終端區(qū)進(jìn)場(chǎng)程序管制適用性分析[J]. 南京航空航天大學(xué)學(xué)報(bào)， 2013， 45（1）：130-139. （WANG C， XU X H， WANG F. ATC serviceability analysis of terminal arrival procedures using trajectory clustering[J]. Journal of Nanjing University of Aeronautics & Astronautics， 2013， 45（1）： 130-139.）

[4]王莉莉，彭勃. 基于LOFC時(shí)間窗分割算法的航跡聚類研究[J]. 南京航空航天大學(xué)學(xué)報(bào)，2018，50（5）：661-665. （WANG L L， PENG B. Track clustering based on LOFC time window segmentation algorithm[J]. Journal of Nanjing University of Aeronautics & Astronautics， 2018， 50（5）： 661-665.）

[5]王超，韓邦村，王飛. 基于軌跡譜聚類的終端區(qū)盛行交通流識(shí)別方法[J]. 西南交通大學(xué)學(xué)報(bào)， 2014， 49（3）：546-552. （WANG C， HAN B C， WANG F. Identification of prevalent air traffic flow in terminal airspace based on trajectory spectral clustering[J]. Journal of Southwest Jiaotong University， 2014， 49（3）： 546-552.）

[6]KALAYEH M M， MUSSMANN S， PETRAKOVA A， et al. Understanding trajectory behavior： a motion pattern approach[EB/OL]. [2019-01-01]. https：//arxiv.org/pdf/1501.00614.pdf.

[7]王超，鄭旭芳，卜寧. 基于小波聚類的終端區(qū)進(jìn)場(chǎng)軌跡模式識(shí)別[J].計(jì)算機(jī)應(yīng)用與軟件， 2016， 33（11）：112-116. （WANG C， ZHENG X F， BU N. Pattern recognition of approach landing trajectories in terminal airspace based on wavelet clustering[J]. Computer Applications and Software， 2016， 33（11）： 112-116.）

[8]石陸魁，張延茹，張欣. 基于時(shí)空模式的軌跡數(shù)據(jù)聚類算法[J]. 計(jì)算機(jī)應(yīng)用， 2017， 37（3）：854-859. （SHI L K， ZHANG Y R， ZHANG X. Trajectory data clustering algorithm based on spatiotemporal pattern [J]. Journal of Computer Applications， 2017， 37（3）： 854-859.）

[9]ZHANG D， LEE K， LEE I. Hierarchical trajectory clustering for spatiotemporal periodic pattern mining[J]. Expert Systems with Applications， 2018， 92： 1-11.

[10]YUAN G， SUN P， ZHAO J， et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review， 2017， 47（1）： 123-144.

[11]REHM F. Clustering of flight tracks[C]// Proceedings of the 2010 American Institute of Aeronautics and Astronautics Infotech and Aerospace. Reston， VA： AIAA， 2010： 1-9.

[12]徐濤，李永祥，呂宗平. 基于航跡點(diǎn)法向距離的航跡聚類研究[J]. 系統(tǒng)工程與電子技術(shù)， 2015， 37（9）：2198-2204. （XU T， LI Y X， LYU Z P. Research on flight tracks clustering based on the vertical distance of track points[J]. Systems Engineering and Electronics， 2015， 37（9）： 2198-2204.）

[13]AGRAWAL R， LIN K I， SAWHNEY H S， et al. Fast similarity search in the presence of noise， scaling， and translation in timeseries databases[C]// Proceedings of the 21th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers， 1995：490-501.

[14]龔璽，裴韜，孫嘉，等. 時(shí)空軌跡聚類方法研究進(jìn)展[J]. 地理科學(xué)進(jìn)展， 2011， 30（5）：522-534. （GONG X， PEI T， SUN J， et al. Review of the research progresses in trajectory clustering methods[J]. Progress in Geography， 2011， 30（5）： 522-534.）

[15]LEI J， YIN J， SHEN H. GFO： a data driven approach for optimizing the Gaussian function based similarity metric in computational biology[J]. Neurocomputing， 2013， 99： 307-315.

[16]von LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing， 2007， 17： 395-416.

[17]ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis[J]. Journal of Computational and Applied Mathematics， 1987， 20： 53-65.

[18]HAN J， KAMBER M， PEI J.數(shù)據(jù)挖掘： 概念與技術(shù)[M]. 范明，孟小峰，譯. 3版. 北京： 機(jī)械工業(yè)出版社， 2015：317. （HAN J W， KAMBER M， PEI J. Data Mining： Concepts and Techniques[M]. FAN M， MENG X F， translated. 3rd edition. Beijing： China Machine Press， 2015： 317.）

[19]OZO N. Flight tracks， Northern California TRACON[DB/OL]. [2019-01-01]. https：//c3.nasa.gov/dashlink/resources/132.

[20]SHEN H. On optimizing Gaussian function based similarity metric in computational biology[EB/OL]. [2019-04-01]. http：//www.csbio.sjtu.edu.cn/bioinf/GFO/.

This work is partially supported by the Foundation of Research Base of Air Traffic Management of Civil Aviation University of China （KGJD201702）.

SUN Shilei， born in 1982， M. S.， lecturer. His research interests include machine learning， data mining.

WANG Chao， born in 1971， Ph. D.， professor. His research interests include air traffic system simulation and analysis， transportation planning and management.

Zhao Yuandi， born in 1983， Ph. D.， research assistant. His research interests include air traffic management information processing.