吴欣蓬，汤新民，毛继志，郭鸿滨，管祥民

（1.南京航空航天大学民航学院，南京 211106；2.中国航空无线电电子研究所航空电子系统综合技术国防科技重点实验室，上海 200241；3.中国民航管理干部学院民航通用航空运行重点实验室，北京 100102）

伴随着航空运输全球化趋势，中国民航运输快速发展。中国民航2019年完成旅客运输6.6 亿人次，较上年增长7.9 %，其中国际航线完成的旅客运输量则高达7425.1 万人次，增长16.6 %［1］。客运量的大幅增长给原本紧张的空域资源分配和调度带来了巨大压力，使得管制员和飞行员的工作负荷倍增。历年空管不安全事件报告显示，在这样的背景下，飞机的异常飞行行为日益频发，例如：因恶劣天气、管制员指挥不当、军民航冲突和无线电干扰等原因导致飞机在飞行过程中产生偏离既定航路，不满足最小间隔标准等异常飞行行为。

空中交通管制的主要任务是避免异常飞行行为的发生，保障飞机的安全运行。但是，目前在空管实践环节，自动化监视设备只能够在战术阶段对小于间隔的异常飞行行为进行预警，不能够发现上述多样化异常飞行行为，难以分析其机理并制定相关针对性措施。而在理论研究环节，随着新航行系统的发展，广播式自动相关监视（Automatic dependent surveillance-broadcast，ADS-B）技术在民航领域广泛推广，每天都会产生大量的航迹运行数据。许多学者采用航迹大数据对飞机异常飞行行进行了探索性研究［2-7］。其中比较有代表性的是Ho等［8］基于ADS-B数据综合回归预测和鞅方法来辨识航迹空间位置不匹配数据的异常飞行行为，其异常偏航行为检出率达81%，但是无法辨识其他类型的 异常飞行行为。Gariel等［9］以ADS-B数据中的飞行计划航路点和航迹转弯点来表征原始航迹，通过重采样方法和主成分分析法获取降维后的等长航迹序列，利用基于密度的有噪声应用中的空间聚 类（Density-based spatial clustering of applications with noise，DBSCAN）算法的噪声辨识功能识别异常航迹，完成空域异常飞行行为的监视。王超等［10］对航迹空间特征利用层次聚类算法来辨识航迹样本类别，并进一步通过偏差建模来量化异常飞行的严重程度。潘新龙等［11］基于定义的多因素定向Hausdorff距离，构造航迹多维度局部异常因子来辨识异常飞行行为，实现航迹的异常行为检测与挖掘，但是对多维特征采取欧氏距离度量存在误差，同时在邻居搜索时时间成本较高。Liu等［12］利用滤波算法剔除航迹数据的噪声和离群点，然后采用自然语言处理中的可变长度N-Grams算法来提取正常飞行行为特征向量，通过训练One-class SVM分类器来辨识异常飞行行为，但不适用于海量航迹的分析。

与上述研究方法不同的是，本文认为航迹是航空器在飞行员、管制员和客观环境因素影响下所表现出来的具有时空特性的行为轨迹。而航迹变化的形成机理主要是飞机速度、航向和高度调整的结果。同时，实际飞行航迹与航路存在偏差。因此，本文首先提出带速度、航向和高度层约束的局部异常因子改进的考虑速度、方向及高度的基于密度聚类方法（Density-based spatial clustering considering speed，direction and high level improved by local outlier factor，LOFDBSC-SDH），提取飞机正常航迹模式，并附加上相对时间特征；通过构建海量ADS-B航迹数据的快速覆盖树［13］来提高算法的处理速度；然后本文引入4D航迹中的过点时间［14］概念和过点时间的偏移约束开展实际航迹与正常航迹模式地相似性匹配；最终实现对航空器异常飞行行为地辨识挖掘。

1 基本概念

1.1 ADS⁃B航迹数据

ADS-B接收机异步解析航迹数据存在数据缺失问题，采用中值滤波算法进行填补；而对于航迹点极少的航班，即ADS-B有效接受范围边界处的航班数据，将视为无效数据进行剔除。最终获得包括飞机ICAO呼号-地址、时间、经度、纬度、高度、速度和航向等航迹信息，部分示意如表1所示。由此可见，飞机的历史航迹是一种时空大数据。

表1 ADS⁃B航迹数据Table1 ADS⁃B track data

1.2 正常航迹模式

本文定义飞机正常航迹模式是指在历史无冲突表现的条件下，飞机在规定过点时间上位于既定的空间位置，并且速度、航向和高度特征与历史上的正常航迹模式相一致的类簇。因此，对飞机的航迹进行定义

式中：S为飞机航迹数据集，其中第j个飞机的航迹数据集为Tj，对于Tj中第i个航迹点有经度、纬度、高度、对地速 度和真航向对应过点时间。过点时间定义为相对于当天凌晨0点的毫秒计数，取值范围为0～86400000ms，该数据需要对表1时间数据按协调世界时（Universal time coordinated，UTC）进行转换。故同一正常航迹模式类簇可由一个S来表示。

1.3 异常飞行行为

所谓异常飞行行为，定义为飞机在运行过程中，表现出在过点时间、空间位置、速度、航向或高度层特征与历史正常航迹模式相异的飞行行为，即飞行表现违反1.2 节正常航迹模式定义。因此，异常飞行行为与正常航迹模式是相反关系。

鉴于航迹需分段处理，进一步给出异常飞行行为在航迹分段条件下的定义：若一飞机航迹的任意子轨迹符合上述异常飞行行为定义，则称该飞机存在异常飞行行为。

2 基于ADS⁃B数据的正常航迹模式提取

2.2 正常航迹模式的提取原理

2.2.1 约束的引入

异常飞行行为的形成过程主要表现为2种形式：（1）飞机之间在原本既定的高度层、航路上产生异常飞行行为，表现为同航路前后追赶、交叉航路相互接近。这主要是速度异常改变导致的。（2）飞机未在原本既定的高度层或航路上而产生异常飞行行为，表现为飞机偏航、穿越高度层而发生飞行冲突，这主要是航向和高度异常改变导致的。因此，正常航迹模式的提取应当将高度层、速度和航向作为必要特征。

传统DBSCAN轨迹挖掘算法［15］通过计算航迹点与其他航迹点之间的距离，将位于邻居半径ε范围内的航迹点进行归并。如果归并结束后类簇的元素个数大于密度μ则认为聚类成功；反之，将该类簇视为噪声剔除。该算法只考虑了航迹的空间位置关系。进一步作图1分析可知，虚线圆圈为ε所形成的的邻居半径范围，即水平间隔安全区域，而高度层下界高hk和hk+1刻画了垂直间隔标准。当航迹Ti穿越高度层hk+1后，其子轨迹Tsubi2将不再与Tj发生聚类关系。因此，通过高度层标准来划分航迹可以规避不必要的聚类操作。目前，国内仅有交叉航路，不存在平行航路，因此交叉航路汇聚点处会出现不同类航迹点ε邻域的交叠，即Ti和Tj，这样将会引起错误的聚类。但是通过引入速度和航向特征可以很好地区分这2种航迹，从而将其标记为不同的类型。反之，对于同航路同航向且速度近似的航迹将被聚类为同一类簇，即Tm和Tn。

图1 轨迹特征与正常航迹模式的联系Fig.1 Relationship between track characteristics and normal track patterns

此外，DBSCAN基于欧氏距离判定航迹点之间的邻居关系。如果将这3个特征纳入欧氏距离计算会增加算法的运算时间。因此，为了兼顾速度、航向和高度层特征而又不增加欧氏距离计算复杂度，本文将3个特征以约束形式（式（2～4））引入DBSCAN算法进行改进，以使其适用于正常航迹模式的提取

式中{hk，hk+1}⊂H。

式中：H为高度层约束集合；hk为第k个飞行高度层的下边界高度值，因此对于满足高度层约束（2）的两航空器航迹点和将位于同一高度层中，可近似投影为hk所在平面进行DBSCAN聚类，而无须在三维空间进行空间距离计算，节省计算时间。这即是“高度层划分策略”。速度和航向约束为式（3，4），其中δv和δθ分别为速度阈值和航向阈值。可以依据飞机性能参数设定，从而辨识出相同飞行行为的航迹模式。此外，算法并未让式（1）中的时间特征参与计算，而是将其作为附加属性，置于提取的正常航迹模式中。这主要是考虑到时间和空间度量尺不具有相同物理量纲，以及ADS-B数据的时间点由于异步解析可能无法对齐。因此，同一正常航迹模式中将存在时间不同而在空间上相似的轨迹。

2.2.2 局部异常因子

虽然，在大部分时间下，飞机的航迹数据均属于正常航迹模式。但是过滤掉一些隐藏的异常模式，对本文借助模式匹配来辨识异常飞行行为是有必要的。原始的DBSCAN的异常点剔除能力有限，依赖于参数ε和μ。为了获得较为干净的正常航迹模式，继续在DBSCAN的邻居判别过程中引入局部异常因子（Local outlier factor，LOF）［11］lrdμ(p)=

式 中：|neighborPts(p)|为p的 邻 居 个 数；reachDistμ(p，q)表示p和p的邻居q之间在密度为μ条件下的可达距离；lrdμ(p)为航迹点p的局部可达 密 度；LOFμ(p)为p的 局 部 异 常 因 子。当LOFμ(p)≤1时，则p的局部可达密度与其邻居航迹点相接近，可视为属于同一类簇；否则，p为离群的异常点，进行剔除。

2.2.3 快速覆盖树

除此之外，DBSCAN和LOF的计算均以蛮力算法来寻找邻居对象，时间成本较高，不能满足航迹大数据的快速分析要求。本文提出构建ADS-B航迹数据集的快速覆盖树数据结构［13］来降低邻居查找过程的时间消耗。对一棵快速覆盖树而言，任意结点均包含一个单一的航迹点数据，并且满足3个不变量约束：

（1）层次不变量即结点a所对应的一个关联整数level(a)。并且对结点a的子结点b存在如下等式约束关系

（2）覆 盖 不 变 量 定 义 为covdist(a)=2level(a)。结点a和其子结点b的距离满足如下约束关系

（3）分离不变量定义为sepdist(a)=2level(a)-1。结点a的任意两个子结点b1、b2的距离满足如下约束关系

依据上述结点与子结点约束关系可知，从根结点出发，每个父结点均向下覆盖其子结点，即子结点对应航迹点为其父结点对应航迹点的邻居。基于上述约束规则可以构建ADS-B航迹数据集对应的一棵快速覆盖树。

为了在快速覆盖树中查找航迹点p的邻居，设结点a的子结点集合为children(a)，后代结点集合为descendant(a)，定义结点a到其后代结点之间的最大距离为

从根结点出发查找p的邻居。分别向下按层次寻找p所属的覆盖结点。对某层p所属结点a，计算该航迹点与结点a的各子结点b之间的距离，并按距离从小到大排序考察结点a及其子结点b和航迹点p是否满足如下约束

若满足，则该子结点是p在快速覆盖树下一层次所属的覆盖结点。重复该步骤，直到所有子结点均不满足式（11），则该父结点为p的邻居。依据文献［13］可知，n结点快速覆盖树的查找时间复杂度为O(c6logn)，其中c为常量，一般取2。故相对于使用蛮力算法查找邻居航迹点的幂级时间复杂度来说，使用快速覆盖树数据结构降低了算法查找邻居的时间成本。

2.2.4 LOFDBSC-SDH算法

将基于上述方案改进DBSCAN提取正常航迹模式的算法称为LOFDBSC-SDH，相关符号定义如表2所示，其伪代码如算法1 所示。算法第2行首先基于ε邻居半径标准，按2.2.3 节所述方法将输入的航迹点逐步插入到快速覆盖树相应结点，形成ADS-B航迹数据集对应的完整快速覆盖树，即建立算法的快速邻居搜索空间。算法第7行和18～28行在邻居搜索环节引入高度层约束[hk，hk+1]、速度约束δv和航向约束δθ，结合密度阈值μ完成同类航迹地辨识。算法8 ～11行基于上述邻居结果计算该航迹点的LOF值，辨识异常点。将异常点及其邻居一并剔除，节省算法聚类时间。待航迹数据中异常点剔除后，从第12～17行开始利用mergeClusters方法（34～41行）进行正常航迹类簇地合并，最终提取得到正常航迹模式。

表2 符号定义表Table2 Symbol definition

算法1LOFDBSC-SDH算法

结合LOFDBSC-SDH算法的设计思路和航空器实际运行场景，参数ε可取最小水平间隔，而参数密度阈值μ则一般依据经验设定［16］。

3 基于匹配算法的异常飞行行为辨识

异常飞行行为虽然有偏航和间隔缩小等具体形式，但是从宏观角度来看就是不同于正常航迹的异常模式。因此，基于匹配算法辨识实际航迹是否归属于正常航迹模式，将未匹配上的航迹认为存在异常飞行行为。

3.1 航迹的分割

航迹中包含航路点、转弯起始点、转弯结束点等有效特征，常规对全航迹实施匹配的方法可能忽略掉这些局部特征。因此，基于航迹划分对其子轨迹实施匹配以克服该问题，同时也可降低单次匹配的时间消耗。最小描述长度（Minimum description length，MDL）［17］能够为某种模式类中的所有成员寻找不可约、最小的特征表达方式。由于文献［17］提出的MDL是用于二维轨迹划分，因此本文首先采用2.2.1 节提出的高度层划分策略提取同高度层子轨迹，然后将子轨迹投影至高度层平面按MDL算法进行划分，获取该子轨迹的有效特征表达。

3.2 异常飞行行为辨识

基于航迹匹配辨识异常飞行行为需要采用合适的相似性度量。由于欧式距离EucDistance对轨迹点的时间偏移敏感，动态时间规整距离时间复杂度高，最大公共子轨迹距离对稀疏轨迹度量效果较差，本文从轨迹差异度的角度进行分析，采用Hausdorff距离［17］来实现轨迹距离度量，并引入时间、速度和航向因素对其进行改进，以更好地判断异常飞行行为。

进而得到式（13～14）构造两航迹Hausdorff距离计算式（15）

依据相似性匹配算法，如算法2 所示，最终可分别在各高度层内完成子轨迹的相似性匹配，辨识异常飞行行为。

4 实验分析

4.1 实验设计

本文选取华东地区某空域ADS-B接收机所获取的2019-12-1至2019-12-30清洗后的1776207条有效航迹数据记录作为训练数据集，2019-12-31清洗后56572条有效航迹数据作为测试数据集。首先基于LOFDBSC-SDH算法利用训练数据提取正常航迹模式，其中ε取最小水平间隔10km［18］，μ取50，高度层约束H设置参考文献［18］，依据速度航向变化 值的 统计分析，δv取100m/s，δθ取10°。然后，基于δTD=2000ms运用匹配算法辨识测试数据集中的异常飞行行为。

最后，为了验证本文提出异常飞行行为挖掘方案的准确性，取清洗后的2019-11-31的63129条有效正常航迹（共2107个航班）数据，对其中100个航班的高度数据进行分段切分、混合后再拼接操作，构造异常飞行行为航迹样本数据，并给定标签1；然后继续各选取100个航班做速度、航向数据的相同处理，其中航向异常数据，即空间位置的偏差异常，故其构造需要将航向数据连同经纬度数据一并更换，分别给定标签2和3，最终生成300个异常飞行行为的航班航迹数据。其余未处理数据给定标签0，视为正常飞行航迹样。最终形成验证数据集。按照上述相同的异常飞行行为挖掘步骤处理验证数据集，分析本文方法的准确率。

4.2 实验结果

4.2.1 真实场景异常飞行行为挖掘

对4.1 节所述训练数据集，使用本文提出的LOFDBSC-SDH算法提取飞机正常航迹模式，共获得124种正常航迹模式，其可视化结果如图2（a）所示。从结果可知，LOFDBSC-SDH算法相较于基线算法DBSCAN，如图2（b），所提取得到的正常航迹模式其轮廓更为清晰，离群点较少，方向性更强；图2（c）左下角的许多航迹模式在LOFDBSC-SDH算法作用下得到强化（红色虚线区域），同时图2（b）中心部分的橙色航迹表征出了该空域内的交叉航路事实，具有典型的代表性。综上所述，本文提出的LOFDBSC-SDH算法通过引入局部异常因子提高了算法DBSCAN的离群点剔除能力，可以获取较为干净的正常航迹模式，降低离群点对航迹匹配的干扰。

进一步采用3.2 节异常飞行行为辨识方法对华东地区某研究空域某日全天航迹进行异常飞行行为挖掘，结果如图2（c）所示。该航班直接从常熟市和张家港市上空飞跃，而查阅航图数据发现并无此航路，可以肯定存在异常飞行行为。

4.2.2 实验结果分析

在正常航迹模式数据库中，按时间节点和高度层约束进行检索，分析数据，发现图2（b）中的异常飞行行为主要与正常航迹模式66存在一定联系，其所在时间、高度层、经度与模式66基本一致，但是在纬度、航向和速度分布上存在较大差异，如图3所示。该异常飞行行为的航班的飞行速度呈现加速状态，与正常模式66所显示出的匀速变化状态相异。此外，图2（b）显示器航迹不同于图2（a）中的各典型正常航迹模式，即从常熟市上空直接汇入正常航迹所在航路，该事实与图3所示与正常航迹模式存在显著纬度差异、23200～23400ms时间区间内存在显著航向差异的实验结果相符。

图2 华东地区某研究空域Fig.2 Research airspace in East China

图3 异常飞行行为特征曲线Fig.3 Characteristic curves of abnormal flight behaviors

因此，本文所提出的方案挖掘出了实际ADSB数据中存在的违反速度和航向约束的异常飞行行为。

4.2.3 准确率分析

在验证数据集上，按4.2.1 节相同实验步骤进行异常飞行行为地挖掘辨识。对有效结果进行统计分析，如表3所示。本文所提出的方案在验证数据集上能够辨识出其中93.3 %的异常飞行行为，其中高度异常辨识准确度为91%，速度异常辨识准确度为96%，而航向异常辨识准确度为93%。需要注意的是，位置异常是这3种异常的最终表现，包含于总体准确性表述中。

表3 异常飞行行为挖掘准确性Table3 Mining accuracy of abnormal flight behaviors %

综上所述，实验结果表明本文所提出的异常飞行行为挖掘方法对于实际飞机的异常飞行行为挖掘是有效的；并且，从异常飞行行为的产生机理出发，挖掘辨识飞机的过点时间、高度、速度和航向特征来判定飞机的异常状态，相较于引言中相关文献算法只通过空间位置特征偏差判定飞机异常飞行的做法，本文的方案更为合理。

4.3 算法分析

4.3.1 聚类质量分析

对于没有基准的数据集，一般采用内在方法来评 估 聚 类 质 量，DAVIES-BOULDIN指 标［16］，即DBI，就是一种有效的方法，其定义如下

表4 算法DBI比较Table4 Comparison of DBIs

从表4结果可知，LOFDBSC-SDH算法相较于传统的DBSCAN算法具有更好的聚类效果，该评估结果与可视化结果图2（a，b）一致。

4.3.2 算法运行效率分析

本文对引言中多数文献采用的基线算法DBSCAN、所提出的LOFDBSC-SDH算法以及引入快速覆盖树的FCT LOFDBSC-SDH进行了运行时间分析，其结果如图4所示。可见，LOFDBSC-SDH算法引入LOF后，虽然在正常航迹模式的提取上取得了较好的效果，但是增大了算法的时间复杂度，运行时间有所增加。之后引入快速覆盖树数据结构，预先构建ADS-B航迹数据的邻居搜索空间，加快了算法邻居计算速度，降低了算法的时间复杂度，运行所需时间减少。因此，基于快速覆盖树的LOFDBSCSDH算法在实验结果的优良性和算法的时间复杂度上做出一种良好地平衡，可以应用于海量ADS-B航迹数据的正常航迹模式提取，辅助异常飞行行为的辨识，规避引言相关方案［8，11-12］的不足。

图4 算法性能比较Fig.4 Comparison of algorithm performance

5 结 论

本文提出了一套LOFDBSC-SDH密度聚类算法和匹配算法相结合的异常飞行行为挖掘方案。首先，为了克服传统方法只以飞机空间位置偏差作为异常飞行行为判定的不足，考虑异常飞行行为的产生原因，提出在位置异常基础上进一步考虑速度、高度和航向异常特征来设计挖掘算法。其次，为了弥补传统算法水平扩展局限性，提出高度层划分策略规避算法不必要聚类过程，并结合局部异常因子和快速覆盖树提出LOFDBSC-SDH算法，对海量ADS-B航迹数据进行正常航迹模式的快速、有效提取。然后，考虑过点时间和高度、速度、航向3个异常特征，设计相似度匹配算法来挖掘辨识异常飞行模式。最后，算法的DBI指标和运行时间实验表明，本文提出的LOFDBSC-SDH算法克服了传统DBSCAN的水平可扩展局限性，并提高了聚类的精度；而仿真实验结果表明所述方案能够有效辨识存在位置、速度、高度和航向异常的飞行行为，弥补了传统方法只能辨识空间位置偏差异常的不足；采用实际ADS-B数据的实验表明本文的方案能够挖掘真实运行场景中的异常飞行行为，具有良好地应用价值。

不过，本文方案还无法有效解决恶劣天气等环境因素所带来的影响等问题，需要在接下来的研究中引入多源数据进行进一步改进。