Parameter independent clustering of air traffic trajectory based on silhouette coefficient

doi:10.11772/j.issn.1001-9081.2019040738

Abstract

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.8099 and 0.8056. 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

摘要： 为消除专家经验的主观性、避免依赖轨迹特征并且减轻实验调参的负担，提出一种基于轮廓系数的参数无关聚类分析（PICBASIC）算法。首先，比较了现有基于欧氏距离的航迹配对方法，并且建立基于动态时间弯曲（DWT）距离和高斯核函数的轨迹相似度计算模型；其次，利用谱聚类对空中交通轨迹进行聚类划分；最后，提出一种基于轮廓系数的最佳簇数寻优方法，并且其具有对聚类结果量化评价功能。利用真实进场轨迹进行实验验证，PICBASIC判断将28L跑道的365条轨迹聚为5个簇，28R跑道的530条轨迹聚为6个簇时聚类质量最佳，平均轮廓系数分别为0.8099和0.8056。相同实验数据条件下，PICBASIC与MeanShift聚类的平均轮廓系数差异率分别为-1.23%和0.19%。实验结果表明：PICBASIC包容轨迹的速度和长度差异，全程无需人工指导或实验调参，而且能够筛除异常轨迹对聚类质量的不利影响。

关键词: 空中交通轨迹, 聚类分析, 轮廓系数, 谱聚类, 动态时间弯曲, 高斯核函数, 参数无关

CLC Number:

TP181

SUN Shilei, WANG Chao, ZHAO Yuandi. Parameter independent clustering of air traffic trajectory based on silhouette coefficient[J]. Journal of Computer Applications, 2019, 39(11): 3293-3297.

孙石磊, 王超, 赵元棣. 基于轮廓系数的参数无关空中交通轨迹聚类方法[J]. 计算机应用, 2019, 39(11): 3293-3297.

References

[1] 赵元棣,王超,李善梅,等. 基于重采样的终端区飞行轨迹可信聚类方法[J]. 西南交通大学学报, 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] 王超,徐肖豪,王飞. 基于航迹聚类的终端区进场程序管制适用性分析[J]. 南京航空航天大学学报, 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时间窗分割算法的航迹聚类研究[J]. 南京航空航天大学学报,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] 王超,韩邦村,王飞. 基于轨迹谱聚类的终端区盛行交通流识别方法[J]. 西南交通大学学报, 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] 王超,郑旭芳,卜宁. 基于小波聚类的终端区进场轨迹模式识别[J].计算机应用与软件, 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] 石陆魁,张延茹,张欣. 基于时空模式的轨迹数据聚类算法[J]. 计算机应用, 2017, 37(3):854-859. (SHI L K, ZHANG Y R, ZHANG X. Trajectory data clustering algorithm based on spatio-temporal pattern[J]. Journal of Computer Applications, 2017, 37(3):854-859.)
[9] ZHANG D, LEE K, LEE I. Hierarchical trajectory clustering for spatio-temporal 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] 徐涛,李永祥,吕宗平. 基于航迹点法向距离的航迹聚类研究[J]. 系统工程与电子技术, 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] 龚玺,裴韬,孙嘉,等. 时空轨迹聚类方法研究进展[J]. 地理科学进展, 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.数据挖掘:概念与技术[M]. 范明,孟小峰,译. 3版. 北京:机械工业出版社, 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/.