基于层次聚类算法的平均航迹构造

基于层次聚类算法的平均航迹构造

王雪艳

民航西南空管局  四川成都610202

摘要：以当前航迹数据应用现状及未来对平均航迹的需求作为研究背景，通过对雷达数据的航迹特征分析，采用FastDTW算法以及平均距离度量方法对航迹距离进行计算，建立航迹相似性度量模型，并运用改进的经典层次聚类算法对航迹进行聚类，最后提出平均航迹构造算法，完成平均航迹的构造。

关键词：航迹数据；FastDTW算法；层次聚类；平均航迹

虽然当前受“新冠”疫情影响，民航发展遇到阻碍，流量减少，但疫情之前终端区流量与日俱增，且未来疫情结束后，终端区流量也会“井喷式”增加。流量的增长以及新的导航技术的出现，会使得标准进离场飞行程序与空管人员指挥的实际的进离场航空器飞行轨迹之间出现差异，这种差异程度客观上反映了飞行程序及其组成的航线网络适应变化的交通流量水平的能力。通过对航空器航迹的聚类分析，不仅可以识别离群航迹或者异常航迹，得到盛行交通流，还能建立代表大量航迹的平均航迹，有利于后续对飞行程序的评估与优化。

一、雷达数据处理

目前，二次雷达监视系统在空中交通领域中的应用比较广泛，其能记录并提取大量信息，所以通过二次雷达也可以获得大量的航迹信息。将终端区提供的原始雷达数据解码后运用linux系统下的Xshell软件对该数据进行整理得到规范的航迹数据。

二、运行航迹特征分析

1.航迹数据特征分析

由于二次雷达监视设备并不是连续记录信息的，具有一定的扫描周期。所以航空器的飞行轨迹是离散的航迹点，并且由于飞机的机型不同，性能不同，发动机推力不同导致不同航迹的航迹点不能完全重合。即每一个进场或离场的航空器都将形成一条由多个离散轨迹点组成的航迹。

2.航迹相似性度量方法

目前，在对航迹数据的运行特征进行研究时，多采用欧氏距离作为相似性度量方法，但基于欧氏距离的度量方法对于不等航迹点的航迹数据来讲衡量效果较差。而动态时间规整(DTW)虽然初期只针对语音进行相似性识别，但经过不断的发展，DTW的应用也扩展到其他领域。DTW算法的思想很适合航迹间航迹点对的匹配，首先其通过将时间扭曲来对某一航迹点重复采样，改变航迹点一一对应匹配来计算航迹距离的方法，从而使航迹点对的匹配范围得到扩展；接着其通过迭代的方式从所有可能的变换路径中找出距离最短的匹配规则。

基础的DTW算法具有较高的时间复杂度，在计算时对时间和空间要求极大，为此很多专家学者改进了DTW算法，简单来说就是从约束范围和细化路径这两个方面加快算法的计算速度。文章则也将从这两方面出发，运用FastDTW算法对航迹间距离进行计算，其构造的表示航迹集合 中所有航迹两两之间的距离相似度矩阵D_T。

由于层次聚类在使用时需要度量航迹簇之间的距离，常用的度量簇之间距离的方法有三种：最小距离、最大距离以及平均距离。最大距离和最小距离比较极端，当两个航迹中有离群航迹或有离群点时，最大距离和最小距离度量方法不能很好的反映两个航迹间真实的距离情况。因此，文章选择对噪声点和离群航迹不是很敏感的平均距离作为度量航迹簇之间距离的方法，以达到较好的聚类效果。

3.航迹的聚类分析

通过对常用聚类方法的分析对比，层次聚类算法更适合文章对航迹数据的研究分析。通过对航迹运行特征的研究，文章将采用凝聚层次聚类算法，此算法先将每条航迹看做一个航迹簇，然后不断的将距离最近的两个簇合并，直到所有的航迹都进行过此步骤，无法再进行合并或达到研究需要的某个条件，则聚类完成。

但经典凝聚层次聚类算法有两个缺点：一是无法在更新完距离矩阵后处理噪点，而噪点的存在使计算时间与空间浪费，同时还降低了聚类结果的准确性；二是在算法运行过程中需要不断的进行距离计算和合并，而且为单步合并，即每更新一次距离矩阵只能合并其中的两个航迹簇，形成一个新的航迹簇。因此经典的凝聚层次聚类计算量和存储需求代价昂贵，对大数据量的航迹集合处理效率差。因此，为了解决经典凝聚层次聚类算法的这个缺点，需要对该算法进行改进。

进离场航空器在飞行过程中由于不利天气、特情等可能会严重偏离标准飞行程序，由此产生的航迹我们称之为离群航迹，离群航迹在整个航迹集中所占的比例较小，但在聚类过程中会干扰聚类，影响聚类结果，因此需要在聚类过程中将离群航迹舍弃。

航迹to是否为离群航迹主要从以下两个指标进行判断：①Dnearest(to)> Dstop；②(nCi Dstop)。只要航迹 满足两个指标中的一个就可确定其为离群航迹。其中，Dnearest(to)为航迹to与离其最近的航迹之间的DTW距离，航迹to属于航迹簇Ci，Dstop为聚类算法终止判定阈值，nCi为第 个航迹簇内包含的所有航迹数量，ndrop为离群航迹簇的判定阈值。

通俗来讲离群航迹指的就是距离聚类簇较远，无法属于任何一个聚类簇的航迹，因此，最终得到的聚类簇个数k以及舍弃的离群航迹数量与参数Dstop、ndrop相关，增大Dstop，聚类簇数目会增加，同时离群航迹数目nco会减少，而减小ndrop，聚类簇数目 会增加，同样会使nco减少。

接下来对经典凝聚层次聚类算法进行改进：第一步输入数据，并初始化每条航迹作为一个航迹簇；第二步用FastDTW算法构造距离矩阵；第三步把航迹簇分类剪枝，主要是为了剔除离群航迹，提高收敛速度和聚类效果，具体流程如图1所示；第四步中改进的层次聚类不像经典层次聚类一样，单步合并航迹簇，而是采用并行操作，将优先队列Q里面的航迹簇同时进行合并操作，当Q里面的航迹簇都完成合并，每两个簇之间再无法进行新的聚类后，再次根据平均距离函数计算簇间距离，完成距离矩阵的革新，循环往复，直至所有的航迹被分类，则聚类完成。

图1 航迹分类及剪枝过程

综上，对经典凝聚层次聚类算法的改进主要体现在两个方面：一是增加了剪枝过程，让离群航迹以及聚类完成的航迹簇不再加入后续的流程，减少没有必要的计算；二是并行操作，即航迹聚类时不再更新一次距离矩阵只合并一次，而是合并多次。经典层次聚类算法与改进后层次聚类算法的性能对比如表1所示。

表1改进前后层次聚类算法性能对比

由表1可明显看出,改进层次聚类算法的复杂度要小于经典层次聚类算法的复杂度。通过抽取定量的航迹数据，测试对比了改进前后层次聚类算法的的时间成本，具体结果如表2所示。

表2 算法时间成本对比

由表2可明显看出,相同条件下改进层次聚类算法的计算时间远远低于经典层次聚类算法的计算时间。

综上，改进的聚类算法使收敛速度得到改善，聚类的时间代价降低，聚类效果增强。

三、平均航迹构造

航迹簇脱离不了标准飞行程序独立存在，有的飞行程序可能形成两个航迹簇，有的飞行程序由于各种原因可能不能形成航迹簇。而平均航迹则就是从数据统计的角度较为直观的展示一个航迹簇的平均运行情况，代表了进离场飞行轨迹中比较典型的一个航迹。平均航迹不是一条真实的运行航迹，是某个航迹聚类簇内比较典型的飞行轨迹，由该簇内的所有航迹的所有航迹点的横坐标、纵坐标和高度进行均值计算获得。

在构造平均航迹时由于每个簇内航迹点对间的高度并不是一致的，因此最开始要对每条航迹进行规范处理，使之处在同一高度，然后对规范后的每条航迹的航迹点数量进行逐一的统计并记录，然后用其中航迹点最少的航迹作为平均航迹的基准航迹点集。其次，初始化平均航迹，使其的每个航迹点的横、纵坐标以及高度都为零，最后对规范后的航迹聚类簇中所有航迹的航迹点求平均值得到最后的平均航迹。具体构造算法如下：

输入：航迹聚类簇C={t1,t2,t3,…,tn}（假设该簇中有n条航迹）

输出：该航迹聚类簇的平均航迹tm={pm1, pm2,…,pmi,…, pmNu}

（1）规范航迹聚类簇C，使得C中每条航迹的起始航迹点的海拔高度一样，得到规范化后的航迹聚类簇。

（2）将规范后的航迹聚类簇中每条航迹的航迹点个数Nuj进行记录，构造的平均航迹的航迹点个数则为Nu。

（3）对平均航迹进行初始化处理，将平均航迹上的所有航迹点的横坐标、纵坐标、以及高度初始化为0。

（4）对航迹聚类簇中每条航迹的每个航迹点的横坐标、纵坐标和高度进行均值计算，按顺序赋值到平均航迹各个航迹点上，直到平均航迹的每个航迹点均被计算。

（5）输出航迹聚类簇 的平均航迹tm={pm1, pm2,…,pmi,…, pmNu}。

四、结语

文章先对雷达数据进行整理，为航迹聚类做了基础铺垫。其次概括了雷达数据的航迹特征，采用FastDTW算法以及平均距离度量方法对航迹距离进行计算，建立航迹相似性度量模型，并运用改进的经典层次聚类算法对航迹进行聚类分析，最后提出平均航迹构造算法，完成平均航迹的构造。此平均航迹的构造是从管制员指挥角度出发，对后续研究飞行程序，管制员管制负荷，运行容量，空域资源等问题具有重要的意义。

参考文献：

[1]王超.仪表飞行程序运行安全性评价模型与仿真分析[J].中国民航大学学报, 2011.

[2]王超.飞行程序运行评估的理论方法及仿真应用研究[D].南京：南京航空航天大学 2012.

[3]赵恩来,郝文宁,等.改进的基于密度的航迹聚类算法[J].计算机工程, 2011,37(09):270-272.

[4]王洁宁,孙禾,等.基于时间-空间的进场航迹聚类分析[J].科学技术与工程,2013,13(33):178-181.

[5]马广辉,张军峰,等.基于历史雷达轨迹分析的4D航迹规划[J].交通信息与安全,2015,33(04):106-112.

[6]徐涛,陈雪蕊,等.基于航迹聚类的终端区飞行程序轨迹表示[J].四川大学学报(工程科学版),2016,48(06):188-196.

[7]彭勃.基于雷达数据的航迹分析方法研究[D].天津：中国民航大学,2018.

[8]陶洋,邓行,等.基于DTW距离度量的层次聚类算法[J].计算机工程与设计,2019,40(01):116-121.

[9]张勇,张建伟,等.一种改进的航迹聚类方法[J].现代计算机,2020(18): 11-18.

[10]Srivastava AN Gariel M and Feron E.Trajectory clustering and an application to airspace moni-toring[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1511-1524.

 【作者简介】王雪艳（1996.04-），女，汉族，河北省唐山市人，硕士研究生学历，民航西南空管局助理工程师，主要研究方向：交通运输。