基于航迹点法向距离的航迹聚类研究

2015-07-26李永祥吕宗平

系统工程与电子技术 2015年9期

关键词：法向航迹相似性

徐涛，李永祥，吕宗平

（1.中国民航大学计算机科学与技术学院，天津300300；2.中国民航大学中国民航信息技术科研基地，天津300300）

基于航迹点法向距离的航迹聚类研究

徐涛1，2，李永祥1，吕宗平2

（1.中国民航大学计算机科学与技术学院，天津300300；2.中国民航大学中国民航信息技术科研基地，天津300300）

随着民航业的飞速发展，机场噪声污染问题越来越严重，研究航迹聚类对机场噪声预防治理工作具有重要意义。现有航迹聚类算法所采用的航迹点对选取方式，无法实现所选航迹点对在空间上的对应，严重影响聚类效果。针对这一问题，提出一种基于航迹点法向距离的航迹聚类模型。该模型采用航迹点法向距离作为航迹相似性度量方法，有效地解决了因飞机速度差异引起的航迹点对选取不匹配问题。通过K-medoids聚类算法对航迹进行二维和三维聚类，使用Davies Bouldin（DB）指标、Dunn指标对聚类结果进行评价。实验表明，提出的模型能够更好地度量航迹之间的相似性，航迹聚类效果更好，从而验证了该模型的合理性和有效性。

航迹相似性；航迹聚类；K-medoids；聚类有效性评价；噪声预测

0 引言

随着民用航空成为更加高效和快捷的出行方式，越来越多的人将飞机作为出行选择，从而促进了中国民航业迅猛发展。新建、扩建机场带来了日益严重的机场周边噪声问题。机场噪声预测是开展机场噪声评价及其环境影响评估的重要基础，因此，科学合理地对机场周边的噪声进行预测尤为重要。

飞行航迹决定机场周围噪声的分布模式，民用机场的运行每天都会产生大量航迹数据，每年积累海量的历史航迹数据。直接利用海量航迹进行噪声预测、噪声评估、航迹优化等研究，易导致研究方法的复杂以及研究结果的不理想。因此，本文基于航迹聚类思想针对具有代表性的航迹进行研究。同时根据噪声监测点数据、雷达数据，结合具体地理位置研究每一簇航迹的噪声分布模式。

目前，关于航迹聚类的研究主要有两大类方法：一类为文献［1］提出的基于航迹点比对的航迹聚类方法，该方法仅建立了一个初步的航迹聚类过程框架，没有考虑因航空器飞行速度差异所带来的空间航迹点不匹配所导致的相似度偏差；另一类是文献［2］提出的基于最长公共子序列的相似性度量算法，并把聚类结果应用到异常航迹预警，该方法根据航迹转折点进行聚类，用转折点落入同一簇的数目来度量航迹相似性。通常，实际数据中航迹转折点数目较少，故其航迹相似性度量误差较大。此外，文献［3］研究了基于轨迹的异常检测；文献［4］分析了常用轨迹相似性度量方法在聚类有效性和时间成本上的优劣。

文献［5］改进了文献［1］的算法，提出根据前后附近点最短距离来度量航迹相似性，将聚类结果应用到终端区的进场程序管制，改进并优化现有进离场飞行程序。文献［6］提出了基于时空分布的航迹聚类分析，并在空管进近管制指挥中得到了应用。

上述提出的两种航迹聚类方法同样没有解决因飞行速度不同引起的航迹点对选取不匹配的问题，故航迹聚类效果并不理想，聚类结果也没有使用聚类有效性指标进行评价。根据“环境影响评价技术导则：声环境”［7］，深入研究航迹的噪声影响范围和大小需要更加精细的航迹相似性度量方法对航迹数据聚类，并使用航迹聚类结果和机场噪声数据进行结合研究。

1 基本概念及理论

1.1 航迹的特征与表示

航迹数据是由空管部门使用雷达监测设备获取飞机的实时经纬度、海拔高度等数据。雷达获取的航迹数据由一系列离散的航迹点组成，离散化程度由雷达的扫描周期（通常为3～5 s）决定。若将每条航迹所有航迹点按时间顺序连接，则形成一条由多个离散航迹点构成的航迹线。飞机进离场时，发动机引擎推力大小不一，飞行的速度随之改变，导致在相同的时间间隔内，雷达获取的航迹数据所表征的实际空间间隔分布不均匀。

不失一般性，航迹可表示为

式中，Ti为第i条航迹；i∈［1，n］为航迹编号；n为航迹总条数。且Ti可用航迹点的数据集表示为式中，Pij表示第i条航迹中第j个航迹点的信息；j∈［1，m］为航迹点编号；m为航迹点总数。

每一个航迹点Pij定义为一个4维向量，即

式中，x、y、z、t分别表示第i条航迹中第j个航迹点的横坐标纬度、纵坐标经度、海拔高度和航迹点记录时间，分别用pij（x）、pij（y）、pij（z）、pij（t）表示。

1.2 航迹相似性度量方法

飞机的离港航迹初始段，由于低空飞行，雷达无法监测，现有的离港航迹数据都是从海拔250～350 m才开始被雷达监测到。正由于航迹的这种特殊性，雷达监测到的每条航迹的起始海拔高度通常互不相同，如果直接使用基于航迹点对之间的距离来度量两条航迹之间的相似性，会引起很大的误差。因此，当两条离港航迹数据起始海拔高度不一致时，需对航迹进行对准截取，即

设Ti＝｛Pi1，Pi2，…，Piu｝和Tj＝｛Pj1，Pj2，…，Pjv｝是任意两条航迹。其中，u，v∈［1，m］分别表示第i条和第j条航迹的航迹点数目。分别以航迹Ti、Tj中第一个航迹点Pi1、Pj1海拔高度最高的点作为起始航迹点。不失一般性，假设pi1（z）＞pj1（z），则以Pi1作为起始航迹点，然后根据式（4），以Ti为基准航迹确定航迹Tj中与Pi1最近的航迹点Pjw，对航迹进行对准截取。

图1给出了现有两种基于航迹点比对的航迹相似性度量方法，图1（a）表示文献［1］方法的航迹点选取方式，该方法直接使用对准后的两条航迹点对之间的距离和除以比对的点数，其航迹相似性度量r1（Ti，Tj）定义为

图1 航迹相似性度量方法

图1（b）表示文献［5］方法的航迹点选取方式，该方法在图1（a）基础上进行改进，在计算每一对航迹点（如Pi2和Pj（w+1））间距离时，同时选取各航迹点前后最相近的两个航迹点进行计算，以获取在此位置附近的两个航迹点之间的最短距离。其航迹相似性度量r2（Ti，Tj）定义为在5条距离中选取最短的距离作为当前航迹点对的距离，即

但是，这两种方法都没有解决因飞行速度不同引起的航迹点对选取不匹配的问题，故使用图1中的方法进行航迹聚类效果不好。

1.3 初始簇中心算法

传统聚类算法随机选择初始簇中心，易于导致聚类结果陷入局部最优。为合理选取初始簇中心，航迹聚类初始簇中心的计算考虑采用最大距离积法［8］。

簇中心集合可表示为

式中，k表示簇中心的个数；ck表示第k个簇中心。

簇集合定义为

式中，C1，C2，…，Ck分别表示以c1，c2，…，ck为簇中心的航迹簇数据。

在航迹数据集F中取最高密度区域内的航迹c1作为第1个聚类簇中心；取距离c1最远的另一个航迹c2作为第2个聚类簇中心，计算F中其余每条航迹数据Ti与αk中的数据之间的距离d（Ti，c1）和d（Ti，c2）；推而论之，ck为满足max（d（Ti，c1）×d（Ti，c2）×…×d（Ti，ck－1））的航迹数据Ti，Ti∈F，以此可得到k个初始聚类中心。

1.4 聚类评价指标

为了更好地评价聚类结果并选取理想的航迹聚类簇数目，选用Davies Bouldin（DB）指标［9］和Dunn指标［10］对航迹聚类结果进行评价。

DB指标定义为

式中，

Dunn指标定义为

式中，Ci表示第i个航迹簇内的航迹数据；｜Ci｜表示第i簇内的航迹条数，ci表示第i类的簇中心；Si表示第i簇内各航迹数据与簇中心ci的距离和，即第i簇内航迹数据的分散程度；d（ci，cj）表示第i簇中心到第j簇中心的距离；

理想的聚类结果是同一类间的各数据对象间相似度大，而不同类之间的相似度小。DB指标越小，Dunn指标越大聚类结果越好。使用这两种评价指标可以确定理想的航迹聚类簇的个数。

2 基本航迹点法向距离的航迹聚类

2.1 基于航迹点法相距离的相似性度量方法

在分析航迹数据特征与图1两种航迹相似性度量方法基础上，提出了一种基于航迹点法向距离的航迹相似性度量方法。该方法在图1（b）基础上，计算当前计算航迹点对的前后航迹点的法向距离，这样就能很好地解决因飞行速度不同引起的航迹点对选取不匹配的问题，如图2所示。

图2 基于航迹点法向距离的相似性度量方法

根据航迹相似性度量方法r（Ti，Tj）的定义，从以下几个方面对其合理性证明：

证明当i＝j时，Pie关于点Pi（e－1），Pie的对称点是其本身，即Pie＝P′ie，根据两点距离公式知d（Pie，P′ie）＝0，得出r（Ti，Ti）＝0成立。

证毕

证明由于d（Pie，P′ie）+d（Pjq，P′jq）计算的是两点之间的欧式距离，即r（Ti，Tj）≥0成立。

证毕

（3）r（Ti，Tj）＝r（Tj，Ti）

证明

定义航迹相似性度量方法r（Ti，Tj）表示为

由d（Pjq，P′jq）+d（Pie，P′ie）＝d（Pie，P′ie）+d（Pjq，P′jq）可知，即r（Ti，Tj）＝r（Tj，Ti）成立。

证毕

（4）r（Ti，Ta）+r（Ta，Tj）≥r（Ti，Tj）

证明

证毕

由以上证明可知，基于航迹点法相距离的航迹相似性度量方法满足距离公式的基本性质，使用该度量方法结合航迹数据可以构造出计算航迹间的相似性矩阵R，且

2.2 K-medoids航迹聚类算法

考虑到每一条航迹数据都是由一系列的航迹点组成，航迹点数目可能都不相同，不具备典型的数据与属性之间的对应关系特征，因此，本文选用基于划分的聚类算法［11-12］对满足指定条件的航迹数据集进行航迹相似度的聚类分析。由于航迹的离散性，K-medoids算法在航迹簇中选取真实的航迹作为簇中心，能很好地采用该方法结合航迹数据进行聚类。表1给出结合航迹数据的K-medoids算法。

表1 K-medoids航迹聚类算法

2.3 基于航迹点法向距离的航迹聚类模型

针对海量历史航迹数据，使用航迹相似性度量方法第1.3节中初始簇中心算法、聚类评价指标构建适合机场噪声预测的基于航迹点法向距离的航迹聚类模型。

将空管部门监测到的机场原始雷达数据导入数据库进行数据预处理。原始雷达航迹数据中有缺失、错误、不规则等脏数据，通过人工方式对数据清洗并筛选出完整的航迹数据。结合航迹相似性度量方法对选取的航迹数据计算相似性矩阵R。采用最大距离积的初始化簇中心算法选取k个初始簇中心。结合航迹相似性矩阵和选取的初始簇中心，使用K-medoids算法对航迹聚类，并用DB指标、Dunn指标对航迹聚类结果进行评价。根据评价结果，输出聚类效果最好的航迹聚类中心和各个航迹簇内的航迹对象信息。表2中给出了基于航迹点法向距离的航迹聚类模型。

表2 基于航迹点法向距离的航迹聚类模型

3 实验结果与分析

为了验证基于航迹点法向距离的航迹聚类模型的合理性，基于航迹的二维、三维聚类及航迹聚类结果导入NoiseMap（美国国防部研发的机场噪声预测软件，根据飞行航迹绘制噪声等值线、计算噪声影响范围等），根据“机场周围飞机噪声环境标准”［13］对航迹聚类结果评估，设计了以下3组实验。

实验1 基于航迹的二维聚类。实验采用某大型枢纽机场2013年的航迹数据，选取机场单条跑道一天的离港航迹数据进行试验。为了保证航迹长度大致相同，以跑道中心为圆心，截取半径为65 km内的航迹数据。通过数据预处理，共获取113条标准离港航迹数据。根据K-medoids聚类算法的特性，聚类数目小于样本总数开平方，因此，聚类数目在2～≈11之间最好。通过第2.3节中的基于航迹点法向距离的航迹聚类模型计算可以得出不同聚类数目下二维航迹聚类评价指标结果，如表3所示。

表3 二维航迹聚类评价指标结果值

DB指标越小，Dunn指标越大，聚类效果越好。由表3可以看出，航迹聚类个数为5簇时的聚类结果最好。为了比较以上几种航迹相似性度量方法的聚类效果，图3给出了文献［1］方法、文献［5］方法、本文方法（基于航迹点法向距离）3种度量方法最好聚类结果的对比。

图3 二维航迹聚类3种相似性度量方法对比

由图3可以看出，本文方法DB指标比其他方法都小，Dunn指标比其他方法都大，表明其在二维航迹聚类中效果最好，其航迹聚类结果如图4所示。

图4 二维航迹聚类结果

图4（a）是5簇的航迹聚类结果，图4（b）、图4（c）、图4（f）成功地把相似性的航迹聚在一起。图4（d）、图4（e）两种航迹簇比较接近，但图4（d）的聚类结果有两个航迹转折点，图4（e）的聚类结果有一个航迹转折点，因此，图4（d）、图4（e）符合机场实际标准进离场飞行程序设计。

实验2 基于航迹的三维聚类。在实验1的航迹数据基础上，加入航迹海拔高度信息，形成三维航迹数据。为保证三维航迹的长度基本相同，以跑道中心为球心，截取空间航迹点到球心距离小于65 km的航迹数据。通过第2.3节中的基于航迹点法向距离的航迹聚类模型计算可以得出不同聚类数目下基于航迹三维聚类的评价指标结果值，如表4所示。

表4 三维航迹聚类评价指标结果值

从表4可以看出，聚类个数为5簇时聚类效果最好。分别使用文献［1］方法、文献［5］方法代入航迹聚类模型，并选取最好的聚类评价结果值对比在图5中。

由图5得出，本文方法DB指标比其他两种方法小，Dunn指标比其他两种方法大，表明其在三维航迹聚类中结果最好，其航迹聚类结果如图6所示。

图5 三维航迹聚类3种相似性度量方法对比

图6（a）是5簇的航迹聚类结果，图6（b）、图6（c）、图6（d）、图6（e）、图6（f）分别表示单独的每一簇的结果，每一航迹簇的结果在空间上都是独立的，能够很好地对航迹进行划分。

实验3 航迹聚类结果导入NoiseMap噪声预测软件绘制噪声等值线。由于航迹簇内航迹较多，将每一簇中所有航迹全部导入NoiseMap比较困难，因此，选取航迹簇内具有代表性的航迹导入，实验结果如图7所示。由图7可以得出，航迹簇内的航迹噪声等值线非常相似，表明航迹簇内的航迹噪声影响范围相似。

图6 三维航迹聚类结果

图7 航迹聚类结果的噪声等值线

由实验1、实验2得出，基于航迹点法向距离的相似性度量方法效果最好，能够应用到更加精细的航迹聚类模型中。由实验3得出每一航迹簇内的噪声影响范围均具有相似性，由此验证了基于航迹点法向距离的航迹聚类模型的合理性和有效性。

4 结束语

在分析航迹数据特征和航迹点比对方法的基础上，提出了一种基于航迹点法向距离的航迹间相似性度量方法。通过实验分析文献［1］方法、文献［5］方法、航迹点法向距离3种相似性度量方法在航迹二维和三维的聚类结果。使用聚类评价指标对结果进行评价，对比两组实验得出基于航迹点法向距离的方法聚类效果最好，并把聚类结果导入到Noise Map输出噪声等值线分析其噪声影响范围，每一簇的噪声等值线基本相似，验证了模型的合理性和有效性，并能够很好的研究航迹聚类在机场噪声预测上的应用。进一步的工作将结合三维航迹相似性矩阵、机场标准进离场程序、机型、飞行速度、天气等噪声主要影响因素，使用模糊聚类算法［14］或者模糊加权的聚类算法［15-16］提高航迹聚类的效率，挖掘噪声分布模式和噪声值相似的航迹簇，并对航迹聚类结果和机场噪声监测实际数据进行关联研究。

［1］Frank R.Clustering of flight tracks［C］∥Proc.of the American Institute of Aeronautics and Astronautics，2010：1-9.

［2］Gariel M，Srivastava A N，Feron E.Trajectory clustering and an application to airspace monitoring［J］.IEEE Trans.on Intelligent Transportation Systems，2011，12（4）：1511-1524.

［3］Lee J G，Han J，Li X.Trajectory outlier detection：a partition and detect framework［C］∥Proc.of the 24th IEEE International Conference on Data Engineering，2008：140-149.

［4］Dahlbom A，Niklasson L.Trajectory clustering for coastal surveillance［C］∥Proc.of the 10th IEEE International Conference on Information Fusion，2007：1-8.

［5］Wang C，Xu X H，Wang F.ATC serviceability analysis of terminal arrival procedures using trajectory clustering［J］.Journal of Nanjing University of Aeronautics and Astronautics，2013，45（1）：130-139.（王超，徐肖豪，王飞.基于航迹聚类的终端区进场程序管制适用性分析［J］.南京航空航天大学学报，2013，45（1）：130-139.）

［6］Wang J N，Sun H，Zhao Y D.Approach trajectory clustering analysis based on time-space［J］.Science Technology and Engineering，2013，13（33）：78-81.（王洁宁，孙禾，赵元棣.基于时间-空间的进场航迹聚类分析［J］.科学技术与工程，2013，13（33）：78-81.）

［7］Ministry of Environment Protection of China.Technical guidelines for noise impact assessment［S］.Beijing：China Environmental Science Press，2009.（国家环境保护局.环境影响评价技术导则：声环境［S］.北京：中国环境科学出版社，2009.）

［8］Xu J L，Xu B W，Zhang W F.Stable initialization scheme for K-means clustering［J］.Wuhan University Journal of Natural Sciences，2009，14（1）：24-28.

［9］Lee S S，Lin J C.An Accelerated K-means clustering algorithmusing selection and erasure rules［J］.Journal of Zhejiang University（Computers&Electronics），2012，13（10）：761-768.

［10］Zalik K R，Zalik B.Validity index for clusters of different sizes and densities［J］.Pattern Recognition Letters，2011，32（2）：221-234.

［11］Pardeshi B，Toshniwal D.Improved K-medoids clustering based on cluster validity index and object density［C］∥Proc.of the 2nd IEEE International Advance Computing Conference，2010：379-384.

［12］Gao D Y，Yang B R.An improved K-medoids clustering algorithm［C］∥Proc.of the 2nd International Conference on Computer and Automation Engineering，2010：132-135.

［13］Ministryof Environment Protection of China.GB9660-88 Standard of Aircraft Noise Environment Around Airport［S］.Beijing：China Environmental Science Press，1988.（国家环境保护局.GB／T9660-1988机场周围飞机噪声环境标准［S］.北京：中国环境科学出版社，1988.）

［14］Chen N，Xu Z S，Xia M M.Hierarchical hesitant fuzzy K-means clustering algorithm［J］.Applied Mathematics Journal of Chinese Universities（Series B），2014，29（1）：1-17.

［15］Wang L N，Wang J D，Li T.Cluster's feature weighting fuzzy clustering integrating rough sets and shadowed sets［J］.Systems Engineering and Electronics，2013，35（8）：1769-1776.（王丽娜，王建东，李涛.集成粗糙集和阴影集的簇特征加权模糊聚类算法［J］.系统工程与电子技术，2013，35（8）：1769-1776.）

［16］Wang L N，Wang J D.Feature weighting fuzzy clustering integrating rough sets and shadowed sets［J］.International Journal of Pattern Recognition and Artificial Intelligence，2012，26（4）：1-25.

Research on flight tracks clustering based on the vertical distance of track points

XU Tao1，2，LI Yong-xiang1，LÜZong-ping2
（1.College of Computer Science and Technology，Civil Aviation University of China，Tianjin 300300，China；2.Information Technology Research Base of Civil Aviation Administration of China，Civil Aviation University of China，Tianjin 300300，China）

With the rapid development of the civil aviation industry，the noise pollution problem of airport is more and more serious.Research on flight tracks clustering is important for prevention and control of airport noise.The flight track point pair chose method which is the existing flight track clustering common method，could not achieve one to one match in the space，and it has a strong influence on the clustering results.In order to solve this problem，a flight track similarity measure model is proposed based on the vertical distance of track points.It can ignore the effects of flight's speed on flight tracks similarity.According to the daily tracks data，flight tracks can be clustered.2D and 3D clustering of the flight tracks can be achieved by the K-medoids clustering algorithm.And Davies Bouldin（DB）index and the Dunn index are used to evaluate the clustering results.Experimental results show that the proposed model can measure the similarity more profitably between the tracks and the results of flight tracks clustering are better.Therefore，the rationality and availability of the model，have been verified.

flight tracks similarity；flight tracks clustering；K-medoids；cluster validity assessment；noise prediction

TP 399 文献标志码：A DOI：10.3969／j.issn.1001-506X.2015.09.36

徐涛（1962-），男，教授，博士研究生导师，主要研究方向为智能信息处理、民航信息系统理论与分析。

E-mail：txu＠cauc.edu.cn

李永祥（1990-），男，硕士研究生，主要研究方向为数据挖掘、机器学习。

E-mail：xiangcool5＠qq.com

吕宗平（1964-），男，副教授，主要研究方向为民航信息处理。

E-mail：zplv＠cauc.edu.cn

1001-506X（2015）09-2198-07

2014-10-21；

2015-01-02；网络优先出版日期：2015-03-23。

网络优先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150323.1706.005.html