张榆薪 王欣

摘 要：随着航空事业的发展，对航迹进行聚类分析，存在许多应用价值。在分析历史飞行航迹特征的基础上，将航迹看作时间序列，采用近邻传播聚类算法，对航迹进行聚类分析，得到聚类结果并进行优化分析。近邻传播算法（AP）是建立在相似度矩阵基础上进行的聚类，为了得到相似度矩阵，结合航迹不等长的特征，选择使用DTW距离作为航迹间相似性的度量；同时，使用DCT对航迹时序列进行降噪，以求得到更好的聚类效果。实验结果表明：该方法在393条航迹的数据集中，划分出11个聚类，提高了航迹聚类的准确性。

关键词：飞行航迹；近邻传播算法；DTW距离；DCT

DOI：10.11907/rjdk.172682

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）004-0089-02

Abstract：With the development of aviation industry， clustering analysis of trajectories has much application value. Based on the analysis of the characteristics of historical flight trajectories， this paper regards the trajectory as time series， and uses AP（Affinity Propagation） clustering algorithm to cluster the trajectories and get clustered results for optimization analysis. The AP algorithm is based on the similarity matrix. In order to get the similarity matrix， the DTW（Dynamic time warping） distance is selected as the measure of the similarity between trajectories， for which are of unequal length. Besides， we use DCT（Discrete Cosine Transform） to denoise the track time series to get a better clustering effect. The experimental results show that the method is divided into 11 clusters in the data set of 393 tracks， which improves the accuracy of track clustering.

Key Words：flight trajectories； Affinity Propagation； DTW distance； DCT

0 引言

将物理或抽象对象的集合分组成为由类似对象组成多个类的过程称为聚类[1]。聚类分析已经在多个领域广泛应用，如图像识别、图像检索等。在民航领域，对飞行航迹数据的聚类分析，也有着良好应用前景，如：在飞行程序分析和评价方面，计算出历史航迹簇中的平均飞行航迹，然后与标准航线进行对比，可以分析飞行程序的适用性和改进方法等[2]。

飞行航迹是由检测雷达周期扫描而得到的空中位置离散点列，可看作是时间序列。由于雷达的扫描周期往往是固定的，所以每条航迹实际上是一条等间隔时间序列。当航迹被看成时间序列时，许多对时间序列的聚類算法也就可以被运用，如基于密度的时间序列聚类算法[1]、基于相似性的时间序列聚类算法。

目前，已有不少对飞行航迹的聚类研究，如基于密度的航迹聚类[1]、基于分层的航迹聚类[2]、自动化粒子群算法的航迹聚类[3]、基于C_Means的航迹聚类[4]等。

本文针对某机场终端区的实际飞行航迹数据，首先采用离散余弦变换（DCT）对航迹进行平滑处理，然后用动态时间弯曲（DTW）计算不等长航迹之间的相似性度量，在此基础之上应用近邻传播算法（Affinity Propagation，AP）对航迹进行聚类分析。最后进行实验结果分析，该方法在航迹聚类分析方面有效。

1 AP聚类算法

AP算法是由Frey等[5]在《Science》一篇文章中提出的，通过消息传递实现聚类。

当迭代次数超过设定值或者多次聚类结果相同时，迭代终止。为了避免震荡发生，AP算法在信息更新时引入一个阻尼因子λ∈[0，1）。

AP算法的基本流程如下：

（1）初始化a（i，k）=0，计算相似矩阵s，并设置参考值p。

（2）按照式（1）-式（3）更新矩阵r（i，k）和a（i，k）。

（3）判断聚类结果是否满足要求，如果没有，则重复步骤（2），直到满足要求，输出结果。

2 相似度测量与轨迹表示

2.1 基于DTW距离的相似度测量

常用于AP算法的相似度指标为欧式距离，不过欧式距离只适用于等长序列，考虑到航迹时序列的不等长特性，欧式距离不再适合作为其相似性的指标。当然有的文章，如文献[3]提出了处理数据集的方法，使欧式距离也能使用在航迹聚类上，不过其本质是等长序列。考虑到航迹数据不等长特性本身固有的意义，这里采用不等长也可以使用的DTW距离作为相似度测量指标。

DTW距离的算法思想可以归结为：运用动态规划思想寻找一条具有最小弯曲代价的最佳路径[6]。

2.2 航迹表示

为了提高航迹时序列的相似性检索性能，用离散余弦变换（DCT）对时间进行处理，以降低时序列的噪声，使时序列更加平滑。

作为一种经典的时域-频域转换方法，离散余弦变换目前已经得到了广泛应用。将此方法用于时序列的相似性检索上，也被证明了相对以前方法，性能有很大提升[7]。

3 实验与分析

3.1 实验数据集及预处理

本文使用的实验数据集来自于文献[3]里提到的航迹数据集，该数据集中包含了许多旧金山国际机场的航班轨迹及每条航迹的描述信息。每条航迹都包含x、y、z坐标，其中z坐标就是航班的实际飞行高度。本文提取2006年1月1日航迹数据点在150～400之间的航迹数据集，并进行DCT预处理。

3.2 实验参数设定及基本流程

AP 算法中有两个重要参数：参数p的大小会影响聚类数目，而参数λ的大小会影响聚类过程的震荡程度。本文实验设定p初值为相似度中值，λ=0.9。其次，迭代停止的限制条件为：最大迭代次数为500，聚类中心保持不变，迭代次数50。

实验基本流程如下：

（1）筛选数据。排除占小部分的突发飞行航迹数据，并取数据点数在150～400之间的航迹数据集。

（2）对航迹进行DCT处理，首先进行DCT变换，然后保留大于2 500的DCT系数，再进行DCT逆变换重构飞行航迹。

（3）计算基于DTW的相似度矩阵s。

（4）进行AP聚类。

3.3 实验结果与分析

初次聚类分析将航迹划分为10个聚类，如图1、图2所示。不过第7类结果并不理想，它至少能分成两类。该问题是偏向参数p难以确定其值而得到最优聚类结果引起的。文献[8]和[9]各自提出了一种可行的优化方案。本文结合数据科学中的简单算法，用数据解决具体问题的思想，用如下基本流程进行优化：

（1）搜索偏值空间（这里即简单的向小或向大）。

（2）将新的偏值用来对第7类进行再次聚类，直到得到不少于两类的聚类结果为止。

再次聚类的结果如图3所示，第7类被成功地分成了兩类。

5 结语

使用基于DTW距离相似性测量的AP算法对飞行航迹进行了聚类分析，实验证实了在图像识别、图像检索等领域有出色表现的AP聚类算法，对航迹聚类也是可行与出色的。在聚类前，使用DCT对航迹数据进行降噪优化。对由于偏向参数p难以确定其值以获得最优解的问题，提出了一种解决办法，实验也证明了其可行性。

参考文献：

[1] 赵恩来，郝文宁，赵飞，等.改进的基于密度的航迹聚类算法[J].计算机工程， 2011（9）：270-272.

[2] 王超，徐肖豪，王飞.基于航迹聚类的终端区进场程序管制适用性分析[J].南京航空航天大学学报，2013（1）：130-139.

[3] ZAHEDEH I， MOHAMMAD S M， AJITH A. Automated clustering of trajectory data using a particle swarm optimization[J]. Computers，Environment and Urban Systems，2016，55（1）：55-65.

[4] 王超，王明明，王飞.基于改进的模糊C-Means航迹聚类方法研究[J].中国民航大学报，2013（3）：14-18.

[5] FREY B J， DUECK D. Clustering by passing messages between data points[J].Science，2007，315：972-976.

[6] 陆薛妹，胡轶，方建安.基于分段极值DTW距离的时间序列相似性度量[J].微计算机信息，2007（27）：204-206.

[7] 刘端阳，张瑞强.基于离散余弦变换的时间序列相似性检索[J].计算机系统应用， 2012（9）：195-197+186.

[8] 唐东明，朱清新，杨凡，等.一种有效的蛋白质序列聚类分析方法[J].软件学报， 2011（8）：1827-1837.

[9] 王开军，张军英，李丹，等.自适应仿射传播聚类[J].自动化学报，2007（12）：1242-1246.

（责任编辑：何 丽）