基于聚类算法的飞行航迹分析

李琳丹，许雅玺，张榆薪，刘坤

（1.中国民用航空飞行学院机场学院，广汉 618300；2.中国民用航空飞行学院计算机学院，广汉 618300；3.中国民用航空飞行学院航空工程学院，广汉 618300）

0 引言

信息爆炸的新时代，大数据已成为当下流行词汇之一。数据内部隐藏着大量有用信息，对数据隐藏信息进行挖掘，已成为当下各行业竞争的重要手段之一，这种信息分析技术，称为数据挖掘。聚类分析是数据挖掘中应用范围较广的方法。聚类分析已在生物、工程、语言、医药、人类学、心理学和市场学等方面得到广泛应用，如地质勘探、古生物研究、大坝监控、图像识别、图像检索等。在航空领域，聚类分析也有较为广泛的应用，在空中交通流量管理和分析层面，聚类分析从错综复杂的航迹中提取出主要流（Major Traffic Flow）信息，识别出扇区中流量的主要模式和特征；在扇区规划方面，对历史航迹进行聚类得到航迹簇，根据航迹簇建立扇区边界；在实际飞行程序设计分析方面[1]，聚类计算航迹簇平均飞行航迹，对比理想航迹分析实际飞行程序存在的不足及改进。

国内航迹聚类方法及应用也较多，王超[2]等人的基于改进的模糊C-means航迹聚类方法研究，在C-means算法聚类的基础上结合了模拟退火和遗传算法进行改进，一定程度上增强了新算法的有效性；肖宇[3]等人的基于近邻传播算法的半监督聚类方法，利用已有的标签数据或者成对点约束对数据产生的相似度矩阵进行调整，提高了近邻传播算法的聚类性能；徐涛[4]等人的基于航迹点法向距离的航迹聚类研究，解决了因飞机速度差异引起的航迹点对选取不匹配问题；郑乐[5]等人的基于转弯点聚类的航空器飞行轨迹分析，实现了盛行交通流的识别。

国外存在的主流聚类分析方法，一是Gaffney S[6]等人对移动对象轨道聚类进行的研究，将单条轨迹视为整体处理，但一般轨迹路径较复杂，在小段上相似在整体上不相似。二是Lee Jaegil[7]等人将单条轨迹分为系列短线段进行聚类，缺乏轨迹整体性。

本文基于近邻传播（AP）算法对飞行器航迹进行聚类分析，采集中国民航飞行学院历史飞行训练数据，将雷达监测航迹点视为时间序列，采用与传统欧氏距离区别的DTW距离作为AP算法的相似度测量指标，增强了航迹距离的适用性，同时采用离散余弦变换（DCT）对航迹时序列做平滑处理，有效地降低航迹时序列的噪声数据，实验结果显示该聚类方法在航迹聚类分析方面效果更佳。

1 基本概念

1.1 近邻传播（AAPP）算法

近邻传播算法是近年来出现在数据挖掘领域的基于代表点的聚类方法，在数据挖掘中起着至关重要的作用。近邻传播算法是在数据点的相似度矩阵的基础上进行聚类[8]，所有数据点都会被考虑为潜在的类代表点，将每个类代表点视为聚类网络中的节点，同时由结点之间的信息传递，使得类代表点的相似度信息最大，最后得到最佳的类代表点集合。近邻传播算法信息的传递更新基于max-product、sum-product原则，该信息幅度代表近邻的程度，即将一个数据点选为类代表点的相似度。此外，近邻传播算法相较于传统聚类方法，针对大规模数据聚类能更快更优的处理，针对非欧空间问题也有较好表现。

1.2 飞行航迹

飞行航迹是指连接一系列点构成一条预计的或经过的路线，通常用来表示飞行器在空间上形成或遵循的航行路线。这一系列点是由检测雷达固定周期扫描得到的一系列离散点列，因此可以将其视为等间隔时间序列。

1.3 离散余弦变换（DDCT）

DCT是一种针对实信号的与傅里叶变换相关的可分离变换，由于傅里叶变换的共轭对称性，实际处理实信号时，导致频域中数据冗余。利用DCT对实信号变换，DCT变换其核心为余弦函数，变换后依旧为实信号，同时简化了实际计算。如图像、声音等实信号，其能量主要存在于DCT变换的低频部分，因此其在图像语音信号处理中运用甚广。

1.4 动态时间规整（DTW）

DTW算法，即动态时间规整算法，又名动态时间规划算法，是一种衡量两个时间序列之间的相似度的方法，其特点在于能衡量长短不一样的信息数据的相似度，一般用以解决发音长短不一的模板匹配问题。

2 基于近邻传播的航迹聚类算法

2.1 基于DCT的航迹数据降噪处理

本文利用AP算法对航迹时序列进行聚类，由于实际雷达监测中存在噪声数据对真实数据的影响，为了增强算法初始数据的有效性，降低噪声数据对后续的航迹相似性度量的不利影响，利用离散余弦变换（DCT）对航迹数据进行预处理。首先将时域序列变换到频域序列，接着通过观察频域序列，去掉噪声频域分量，然后再进行逆变换，将频域序列返回到时域序列，从而实现时间序列的平滑。

对一条航迹时序列AM×N其DCT变换公式如下：

以此类推，将本文采集实际数据按照上述方法对航迹时序列做平滑降噪处理，通过DCT离散余弦变化预处理后的数据剔除了影响航迹点的噪声数据，比较传统聚类，在数据输入的起始段就增强了航迹初始数据的准确性，进而以达到更为真实准确的聚类效果，最后得到的数据作为DTW距离的输入。

2.2 基于DDTTWW距离的航迹相似性度量

假设需要对n条航迹构成的样本空间实现航迹聚类，轨迹的相似性度量方法的优劣直接影响聚类质量的高低。传统方法一般采用欧氏距离来计算航迹之间的相似性。但是欧氏距离的计算要求航迹必须是于等长序列，这就使得算法具有很大的局限性。在本文采集的数据集中，航迹具有非等长的特点，因此本文采用DTW距离作为相似性度量的指标。

动态时间规整是60年代，由日本学者Itakura提出将未知量伸长或缩短到与参考模板长度一致[9]，使得特征量与标准模式相互对应。其本质可简述为寻找一条弯曲代价最小的最优路径。给定两个航迹时序列Q和C，他们的长度分别是n和m：

若n=m，可直接计算两个序列的距离；

若n≠m，则需要线性缩放，即把短的航迹时序列线性放大到和长序列一样的长度，或者把长的线性缩短到和短序列一样的长度，再进行比较。具体如下：

构造一个n×m的矩阵网格，矩阵(i,j)处的元素为qi和cj两个点的距d(qi,cj)=运用运筹学中动态规划的思想，寻找一条使得点与点之间距离最小，相似度最高的路径。并将该路径定义为warping path规整路径，用W表示，第k个元素为Wk=(i,j)k，

但这条路径不是任意选择的，需要满足边界条件，连续性，单调性几个约束条件，找到使得DTW规整代价最小的路径，使得最后总距离最小。将上述降噪后航迹数据输入，找出最佳路径，将DTW距离作为非等长航迹聚类相似性度量指标。

2.3 基于近邻传播算法的航迹聚类

聚类分析是将物理或抽象对象的集合分组成为类似的对象组成的多个类的分析过程[10]，在DCT航迹时序列降噪处理和DTW相似度量基础上，用两类矩阵：代表矩阵a(i,k)和适选矩阵r(i,k)来分别表示归属度和吸引度信息。a(i,k)由候选聚类中心xk指向数据样本点xi，以此描述数据点作为其类代表点的合适程度。r(i,k)由数据样本点xi指向候选聚类中心xk，为数据点搜寻相关信息决定其作为类代表点的代表程度。代表矩阵和适选矩阵的大小决定数据点成为聚类中心可能性大小。通过各个数据样本点的迭代更新后，使得r(i,k)和a(i,k)最大的点即为我们寻求的聚类中心。其对应迭代更新公式如下：

近邻传播在各个数据样本点之间反复迭代结束时，xk为xi的类代表点，其中k满足：

argkmin(a(i,k)+r(i,k)) （8）

实际迭代更新过程中近邻传播算法引入阻尼因子λ∈[0 ,1)来预防震荡出现。当最终迭代次数超过设定阈值或迭代结果相同时，则停止迭代。

近邻传播算法相关步骤：

代表矩阵初始化，令a（i,k）=0,设置实验参考值p并计算相似矩阵s。

根据上述公式（1）～（3）更新代表矩阵及适选矩阵。

最终得到聚类结果，结合实际情况判断该聚类结果是否符合要求，符合，迭代终止；反之重复上述步骤（2），直至达到实际聚类要求，迭代终止，输出结果。

3 算例分析

3.1 数据采集

本文实际数据采集自中国民航飞行学院飞行训练飞机的 ADS-B数据。ADS-B（Automatic Dependent Surveillance-Broadcast）即广播式自动相关监视，其实际原理是利用航空器将机载导航设备确定的航空器识别信息、位置、速度、高度、方向和爬升率等相关信息按照标准组成ADS-B报文，通过数据链路，按照一定的时间间隔进行广播式发送。飞行器的运行轨迹是连续平滑的，航迹数据就是飞行器在运动过程中根据ADSB报文采样得到的数据。每个航迹点包含经度、纬度、高度的三维坐标信息。本文选取100-400的航迹数据点，利用离散余弦变化对航迹数据集做预处理[11]。

3.2 实验参数设定

AP聚类算法需要预先设置偏向参数p以得到不同类别个数的缺陷[12]，偏向参数p和阻尼因子λ分别对聚类数量大小和聚类震荡程度造成相关影响。因此设定适宜的偏向参数p和阻尼因子对聚类结果也有较大影响，本文设定阻尼因子λ=0.9，偏向参数初值为相似度中值。设置上限迭代次数为500次，聚类中心迭代次数50次为迭代终止条件[11]。

3.3 具体步骤

（1）数据过滤：初选航迹数据点数在100-400之间的航迹数据集，筛选过滤其中的意外突发事件造成的非正常航迹数据点。

（2）降噪处理：利用离散余弦变换对航迹数据进行预处理，利用离散余弦变换保留大于300的DCT系数，再对保留数据进行离散余弦逆变换重新构建飞行器航迹。

（3）DTW处理：基于上述处理计算DTW相似度矩阵s。

（4）聚类分析：利用AP算法对上述航迹进行聚类。

3.4 实验结果分析

其最后聚类结果显示，291条飞行航迹数据集，共划分出7个聚类。如图1和2所示。图中我们可以看出前面6类的聚类的效果比较好，但第七类结果表现并不令人满意，分析其原因是该类里的航迹与其他类里的航迹相似度低，同时由于偏向参数p对聚类结果影响很大却又难以确定其具体某一个值来得到最佳聚类结果，使得该类里看上去不相似的航迹也聚类到一个类里。针对上述问题，如何进行进一步的聚类优化，文献[13]和[14]提出了解决方案，除此之外以进一步搜索偏向参数也可以达到更佳的聚类效果。

图1 聚类结果前三类

图2 聚类结果后四类

4 结语

由于我国民航事业的快速发展，空中运输需求与空域资源不足的矛盾日益加大，解决矛盾的根本途径就是要对空中交通管理实施更加精准化的管理，对飞行器航迹进行分析和规划，对实现智慧化空中交通管理有着重大意义。本文利用AP算法对飞行器航迹进行聚类，AP算法相对于传统聚类算法具有更高效更快速更精准更便捷的优点，其在其他领域也有着十分出色的表现。航迹聚类分析是依据数据挖掘（Data Min⁃ing）中聚类分析的方法，通过引入相关学科的知识来不断改善聚类的效果。本文结合中国民航飞行学院飞行训练飞机的ADS-B飞行数据，根据检测雷达固定扫描周期特性，确立航迹时序列，针对航迹不等长的特性，采用与传统欧氏距离相区别的DTW距离来作为AP算法的相似性度量指标。同时为了降低航迹噪声数据，使用了经典的离散余弦变换DCT方法来对航迹数据进行降噪优化，其最后得到的航迹聚类效果良好，同时也对该方法中偏向参数p造成的某些聚类效果不佳的情况进行了分析，并提出了解决方法。