基于小波聚类的终端区进场轨迹模式识别

王 超 郑旭芳 卜 宁

(中国民航大学空中交通管理学院 天津 300300)



基于小波聚类的终端区进场轨迹模式识别

王 超 郑旭芳 卜 宁

(中国民航大学空中交通管理学院 天津 300300)

为改善终端区航空器轨迹聚类方法中存在的自动化程度低、无法精确识别异常轨迹的不足，提出基于小波聚类的进场轨迹模式识别方法。首先，建立基于3D空间网格的轨迹相似性矩阵，推导得到轨迹间相似特征子空间，进一步构建轨迹相似特征2D图模型。通过特征图模型的数字化、小波变换与聚类，实现对盛行交通流模式以及异常交通流轨迹的识别。实例分析在无人工指导情况下，从352条进场轨迹中识别出4个类的331条盛行交通流轨迹，以及 21条异常轨迹。实验结果证明，该算法克服了目前航空器轨迹聚类领域需要人工确定类数以及难以识别异常轨迹的不足。

模式识别 小波聚类 航空器轨迹聚类 异常轨迹识别

0 引 言

空中交通运行中产生的海量历史轨迹数据是大量航班飞行与空中交通管制决策交互作用的结果，隐含着丰富的交通模式信息，其中包括盛行交通流和异常轨迹。盛行交通流反映了航空器轨迹在空间分布的频繁模式。异常轨迹是与盛行交通流偏差显著的少数轨迹，是交通拥塞、危险天气和飞行冲突解脱等异常交通控制行为的反映。因此，基于轨迹聚类的交通模式识别可以用来量化分析空中交通系统性能，发现现有空域结构的不足。根据盛行交通流的分布来改进终端空域的设计可以提高容纳动态交通流能力，同时降低空中交通管制难度，从而提高终端区空中交通运行效率。

近年来，许多学者在轨迹聚类领域开展了研究，主要方法有：基于离散特征点的聚类方法、基于子轨迹的聚类方法、基于完整轨迹的聚类方法和基于时间区间的聚类方法。

针对航空器的飞行轨迹聚类，Rehm[1]提出了一种基于离散航迹点对之间的欧式距离构建相似度的层次聚类方法。但当不同的轨迹所包含的航迹点数量差异显著时，该相似度模型不能准确表达轨迹的空间接近程度。Gariel等[2]提取转弯点作为聚类对象，然后采用K-means和DBSCAN相结合的方法实现聚类，但依然需要人工确认聚类数目。Enrgquze等[3]提出了基于谱聚类的轨迹聚类方法，该方法首先建立相似邻接矩阵，并采用谱聚类方法分割邻接图，聚类效果良好。但需要对航空器位置信息进行线性预处理，导致长度差异显著的轨迹的相似度失真，也存在自动化程度不高的问题。

综上，现有航空器轨迹聚类方法普遍存在两个不足：一是需要根据经验人工确定聚类的簇数，使得聚类的结果受到人为干预的影响；二是无法在大量轨迹数据中精确识别异常轨迹，从而影响聚类质量。

针对以上问题，本文提出一种基于小波聚类的进场轨迹模式识别方法。首先，分析了航空器轨迹数据结构，建立了轨迹相似性矩阵，推导出相似矩阵的特征子空间，构造了2D相似特征图模型。然后，通过对相似特征图模型的数字化、小波变换、空间映射和聚类等过程，识别出盛行交通流轨迹和异常轨迹。最后，通过实际进场轨迹样本对模型和方法进行验证和分析。

1 航空器轨迹数据集相似性

1.1 航空器轨迹的数据结构

图1 航空器进场轨迹的结构

(1)

(2)

1.2 航空器轨迹的相似性

轨迹相似度构建方法的优劣直接影响着聚类质量的高低。轨迹的相似度构建有基于欧氏距离的模型，简单直观但对噪声数据较为敏感；基于最小外包矩形距离的模型，容易遗漏不在对应时刻的相似轨迹的划分；基于全区间变换封装距离的模型，对噪声数据较为敏感；基于子轨迹相似性的模型，受子轨迹时间区间影响较大[4]。

(3)

(4)

2 航空器轨迹的相似特征提取

在数据挖掘领域中，有很多数据由于类型特殊、维度过高、规模庞大等原因导致很难直接对其使用挖掘算法。但通过数据集进行特征提取，可以在保证所提取的特征完整以及准确表达原始数据集特点的前提下，达到提高数据类型的适用性、降低维度和减小数据规模的目的。基于相似度对航空器轨迹进行特征提取，可以解决数据维度过高的问题。

2.1 轨迹的特征提取原理

Jenssen[7]等人对Renyi熵进行估计，发现该熵的最大化与相似矩阵相关，并通过推导确认相似矩阵前k个最大特征值对应的特征向量即为Renyi熵最大化的近似解。根据这一思想，用轨迹数据集的相似矩阵的前k个最大特征值对应的特征向量来构造特征空间，并用特征空间来代表原始轨迹数据。

2.2 轨迹的特征提取方法

(1) 构造原始特征空间V

(5)

(2) 提取特征子空间B

依据Jenssen关于Renyi熵的思想，越大的特征值所对应的特征向量对原始数据的表征能力更强。将轨迹相似特征矩阵W的特征值λ由大到小排序，并选取前k个最大λ对应的特征向量组成n×k维的子空间，可以进一步减小空间维度[8]。选择k值时，需要考虑具体数据的结构特征、类型和应用环境。

由于构建的轨迹相似度涵盖了所有轨迹的空间位置、速度、航向等因素的影响，所以每一个特征向量都能在一定程度上表达所有轨迹的特征信息。当k=1时，由于维度和信息量过小，无法有效实施聚类，所以将k值初步设定为2。经实验验证，当k值由2开始增大时，聚类质量和效果并无明显提升，但维度的增加会导致计算复杂度大幅增高。综合考虑算法的质量和效率，最终将k值设定为2。由此得到的二维特征子空间如下：

(6)

(3) 构造轨迹的相似特征图

为了实现轨迹的小波聚类，在特征提取的基础上提出了一种新的图模型，称为轨迹的相似特征图。以特征子空间B中的值为数据源，以di1和di2两个维度设置x、y坐标系，将[di1,di2]表示为图中的点，称为轨迹特征点，如图2所示。

图2 航空器轨迹的相似特征图模型

3 基于小波聚类的进场轨迹模式识别

小波聚类是一种基于网格和密度相结合的多分辨率算法，目前多用在图像处理、网络入侵检测、信号去噪和多目标定位等领域。将小波聚类应用到航空器轨迹聚类领域，利用其特性可以实现无指导聚类和异常轨迹检测，从而完成航空器轨迹模式的识别。基于小波聚类的航空器轨迹模式识别，是以相似特征图为基础展开的，其总体工作流程如图3所示。

图3 基于小波聚类的进场轨迹模式识别流程

对航空器轨迹的特征数据实施小波变换后，得到的低频信息表征着特征数据稳定集中的区域，最终将这些特征数据所对应的轨迹识别为盛行交通流；高频信息表征着高速变化的特征数据，对应轨迹识别为异常轨迹。

3.1 相似特征图的数字化

小波聚类属于网格聚类，应首先建立覆盖整个运算空间的格网。网格边长的确定主要取决于数据范围大小以及数据的密集程度。为确保每个网格中包含的点数在0～10之间，经过分析，本文取网格边长为0.004。 在图2所示的相似特征图上覆盖一个网格边长为0.004×0.004的二维格网来汇总轨迹的特征点信息，如图4所示。

图4 使用网格对相似特征图进行数字化

统计每个网格中所含特征点的数量，将数值填入对应网格中，构成量化特征空间C，如图5所示。

图5 量化特征空间C

3.2 小波变换

图6 空间单元的映射关系

使用Haar基函数，对空间C进行2个尺度的二维离散小波变换，得到变换空间D，如图7所示。

图7 变换空间D

3.3 寻找连通区域

在变换空间D中采取基于密度的思想寻找连通区域。设定一个密度阈值δ，将包含点数大于或等于δ的单元定义为“显著单元”，小于δ的单元定义为“非显著单元”。

“显著单元”的相邻单元中，如果有“显著单元”，则将两个单元视为同一连通区域并继续搜索相邻的“显著单元”，直到该连通区域找不到相邻的“显著单元”[9]。此时生成的连通区域，定义为“连通单元簇”。

扫描变换空间D中的所有单元，以“显著单元”为基础寻找连通区域。经过多次实验，设定密度阈值δ=10，此时单元中数值的均匀度和单元整体连通性都较好。如图8所示，当δ=10时，灰色背景的单元即为自动生成的连通单元簇。

图8 连通单元簇

3.4 标记簇号及空间映射

经过连通区域的寻找，变换空间D中自动生成了许多连通单元簇，依次标记簇号wi。根据空间C与空间D中单元的映射关系，为各连通单元簇所对应的C中的单元标记簇号wi。在空间C中，将ci的簇号wi标记给ci所包含的特征点。由于特征点与轨迹一一对应，此时轨迹也被标记了簇号wi，如图9所示。

图9 标记簇号及空间映射

最后，算法将标有簇号的轨迹识别为盛行交通流，并将有相同簇号的轨迹各自划分为一个聚类；而将没有标号的轨迹识别为异常轨迹。

4 算例分析

选用西安咸阳机场采用05L/R跑道独立运行模式时，两条跑道某1天内共计352条进场轨迹作为实验数据，如图10所示；使用Matlab作为数据处理和实验分析软件。

图10 咸阳机场05L/R跑道进场轨迹

实验数据的相似特征图如图2所示，以该图为基础，按照基于小波聚类的航空器轨迹模式识别方法进行实验。经过无人工指导的实验后，变换空间D中自动生成了4个连通单元簇w1、w2、w3和w4。将它们映射到轨迹的相似特征图上，如图11所示。

图11 4个连通单元簇

4.1 盛行交通流的识别

算法将4个簇包含的特征点所对应的轨迹识别为盛行交通流，共计331条，用不同灰度标记，如图12所示。

图12 盛行交通流识别结果

图12表明，算法识别出了符合标称进场航线的盛行交通流；且有效地区分出了由西北、东北、西南和东南方向进场的航空器轨迹，将它们各自划分为一个聚类，实现了无指导聚类。4个簇的轨迹彼此在形态和空间分布上有着显著的差异，而同一簇内的轨迹进场方向是一致的，有着较高的相似度和形态特征。

4.2 异常轨迹的识别

将没有标号的轨迹识别为异常轨迹，共计21条，如图13所示。

图13 异常轨迹

识别出的异常轨迹偏离标准进场程序的标称航线，在形态上与盛行交通流差异显著，这说明了算法识别异常轨迹的准确性。

异常轨迹中含有环线的轨迹，称为等待轨迹。这类异常轨迹是管制员为了调配飞行冲突，指挥进场航空器进入等待程序而造成的。图13中有5条等待轨迹，约占总交通流量2%，说明指挥航空器进入等待程序并非在西安终端区管制实施的主要策略。

5 结 语

通过对航空器轨迹的相似度矩阵进行相似特征提取，解决了高维数据不能适用小波聚类的问题；提出了基于小波聚类的航空器轨迹模式识别方法，并实现了对异常轨迹的识别。实验结果表明，在无人工指导的情况下，算法可以有效识别盛行交通流并准确划分聚类。同时可以精确识别异常轨迹，并对轨迹的异常模式做进一步的识别。该方法提出了一种崭新的轨迹模式识别思路，对航空器轨迹聚类方法做出了补充和改进，为终端区空域扇区和进离场航线的优化设计奠定了技术基础。未来将对异常轨迹的形成原因和轨迹模式识别进行进一步研究。

[1] Rehm F.Clustering of flight tracks[C]//6th AIAA Infotech @ Aerospace 2010.Atlanta:AIAA,2010:AIAA-2010-3412.

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

[3] Enriquez M,Kurcz C.A simple and robust flow detection algorithm based on spectral clustering[C]//ICRAT Conference,2012:1-6.

[4] 龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534.

[5] 王超,韩邦村,王飞.基于轨迹谱聚类的终端区盛行交通流识别方法[J].西南交通大学学报,2014,49(3):546-552.

[6] 袁冠.移动对象轨迹数据挖掘方法研究[D].徐州:中国矿业大学,2012.

[7] Jenssen R,Hild K E,Erdogmus D,et al.Clustering using Renyi’s entropy [C]//Neural Networks,2003 International Joint Conference on.IEEE,2003,1:523-528.

[8] Kishore D.Character segmentation from multi-oriented video words using Discrete Wavelet Transform and K-Means Clustering[J].IJSEAT,2014,2(12):1033-1039.

[9] Sheikholeslami G,Chatterjee S,Zhang A D.WaveCluster:a wavelet-based clustering approach for spatial data in very large databases[J].The VLDB Journal,2000,8(3-4):289-304.

PATTERN RECOGNITION OF APPROACH LANDING TRAJECTORIES IN TERMINAL AIRSPACE BASED ON WAVELET CLUSTERING

Wang Chao Zheng Xufang Bu Ning

(CollegeofAirTrafficManagement,CivilAviationUniversityofChina,Tianjin300300,China)

In order to ameliorate the deficiencies existed in trajectories clustering methods of aircrafts in terminal airspace such as low automation degree and cannot precisely identify the abnormal trajectories, we proposed a wavelet clustering-based pattern recognition method of approach landing trajectories. First we set up the 3D spatial grid-based similarity matrix of trajectories, and obtained through derivation the similar characteristic subspace between trajectories. Furthermore we built the 2D graph model of trajectories similar characteristic. The identification on prevailing traffic flows pattern and abnormal traffic trajectories is implemented through the digitisation, wavelet transformation and clustering on the characteristic graph model. We made analyses on examples, under the condition of no artificial guidance, we identified 331 prevailing traffic flows trajectories of 4 categories and 21 abnormal trajectories from 352 approach landing trajectories. Experimental result proved that this algorithm overcomes the deficiency of current aircraft trajectories clustering field that it requires artificial confirmation on the number of categories and is difficult to identify abnormal trajectories.

Pattern recognition Wavelet clustering Aircraft trajectories clustering Abnormal trajectory identification

2015-09-06。国家自然科学基金项目(61039001)。王超，副教授，主研领域：空中交通系统仿真与分析。郑旭芳，硕士生。卜宁，硕士。

TP301 V355

A

10.3969/j.issn.1000-386x.2016.11.027