终端区航空器的异常轨迹检测方法

卜宁+张旭红

【摘 要】 终端区航空器的异常轨迹检测是一个崭新的研究领域。异常轨迹检测常使用基于全局特征、轨迹片段、分类器的检测方法，后续又出现了基于划分、蚁群算法、轨迹模型、人工免疫等一系列的改进方法，各具特点。但是以上的方法在准确性、复杂度、评价方法等方面依然存在不足，需要进一步改进和创新。此领域具有良好的发展和应用前景。

【关键词】 数据挖掘 异常轨迹 异常点检测

【Abstract】 The trajectory outlier detection of the aircraft in terminal area is a new research. The usual methods often bases on global features， track clips and classification. There are a series of improved methods with distinct characteristics， which base on division， antcolony algorithm， trajectory model and artificial immune etc. Nevertheless， in terms of accuracy， complexity of count and evaluation， the methods above need further improvement and innovation. Besides，this field has good prospects of development and application.

【Key words】 Data Mining Outliers Detection Trajectory Outlier Detection

1 引言

随着人类认识和管理水平的提高，信息处理手段的多样化以及数据挖掘技术的发展，各领域的大量信息数据被收集和整理，形成数据库。决策者往往基于提取自数据库中有价值的信息和知识，制定相适应的策略，因此在信息庞大结构复杂的数据库中高效的提取有效信息至关重要。针对各类数据的特点和结构，多种数据挖掘方法应运而生。

数据挖掘方法主要包括：分类方法、聚类方法、关联规则、序列模式、异常点检测和可视化技术等。其中异常点检测可以大量数据中检测到异常点所蕴含的特异知识，对决策者的决策具有重要指导意义。现已广泛应用于电信和信用卡欺骗、贷款审批、药物研究、医疗分析、消费者行为分析、气象预报、金融领域客户分类、网络入侵检测等领域。

2 异常轨迹检测

2.1 概念和意义

异常点是数据库中不符合一般数据模型的数据。在挖掘正常类知识时，通常总是把它们作为噪声点来处理。在航空交通领域，航空器在终端区进场的轨迹信息是重要的研究数据。通过雷达或各类导航等设备获取的轨迹信息，包含了航空器的位置、速度、时刻等时空信息，同时体现了航空器的飞行性能和实时的空域环境状态，蕴含管制员指挥习惯和飞行员的操作习惯等信息。

在大量的轨迹数据中，偏离主干交通流的轨迹被称为异常轨迹，是轨迹数据库中的异常点数据。由于异常点数据并不是随机出现的，而是具有与一般数据点不同的产生机制，所以通过对异常轨迹的检测，可以对飞行员操作、管制员指挥、进离场程序设计、飞机性能等多项可能存在的异常环节进行分析，从而提出改进或调整策略，实现终端区航空器的流畅运行。

2.2 传统的检测方法

2.2.1 基于抽取轨迹全局特征的方法

2000年，Knorr等人提出。首先使用组成轨迹的点的数目、方向、速度等属性来表征该轨迹。其次将每条轨迹视为一个整体，作为异常点检测算法的基本单元并基于距离进行异常点检测。如果每条轨迹的主要特征完全不同，上述方法可以检测出整体轨迹是异常轨迹，比较直观，实现比较简单；如果主要特征中的某一项或几项不同，轨迹异常可能会因为距离函数的加权作用而被丢失。当构成轨迹的点数量较多时，仅通过比较轨迹的全局属性来判断异常，而不考虑局部特征是不合理的。

2.2.2 基于分类器的方法

2006年，Li等人提出了有效的和可伸缩的分类方法motion-classifier，用于检测移动对象的异常行为，开发出移动对象异常点检测系统Motion-Alert，并将motion-classifier作为该系统的核心组件。这种方法存在一定缺陷，首先对于一个应用领域，通常很难找到一个标准数据集作为训练数据集；其次每条轨迹往往长而复杂，存在许多局部异常轨迹片段。异常轨迹片段的异常有可能被整体轨迹所平均化，导致检测失效。

2.2.3 基于轨迹片段相似度检测的方法

2008年，Lee提出TRAOD算法，TRAOD分成划分和检测这两个阶段。首先依据MDL（最小描述长度）原则将每条轨迹分割成轨迹片段，选择变化趋势最大的点作为分割点；其次采用距离度量检测每个片段的相邻片段数目，邻域片段最少的片段判定为异常片段。此法在确保划分质量的同时也具有很高的效率。应用领域较广，可以检测出异常子轨道，也可以检测出整条异常轨迹。2009年，刘良旭，乔少杰等人提出了一种基于R-Tree的算法。首先抽取轨迹中所有长度为k的轨迹片段构成基本比较单元，然后采用基于平移的最新Hausdorff距离作为度量基本比较单元之间的距离。在此基础上提出了局部匹配、全局匹配和异常轨迹的定义。基于此提出了一种基于R-Tree的异常轨迹检测算法。该算法具有很高的计算效率，是一种有效的异常轨迹检测算法。

2.3 改进的检测方法

2.3.1 基于划分的方法

使用空间划分的方法将数据的搜索区域划分为若干不重叠的超矩形单元，将异常点的检测限制在局部空间内。并设计网格索引树GI-Tree只存储非空网格，同时保持网格间的邻近关系，使得最近邻搜索更加高效地完成。endprint

2.3.2 基于蚁群算法的方法

GODAC算法（Graph-cut based OutlierDetection using Ant Colony Algorithm），使用改进的蚁群算法构建图像，然后对图像进行有效切割，其中将距离和分布两个方面综合考虑放入蚁群算法中。蚁群算法的正反馈信息机制降低了对用户定义的阈值的依赖程度。

2.3.3 基于人工免疫的方法

AIBTOD算法将人工免疫算法引入到异常轨迹检测，对 TRAOD算法作出改进。思想是将核心线段作为抗体，模拟免疫系统的克隆选择原理，不断克隆并筛选最优核心线段，进行轨迹线段簇划分。AIBTOD算法比TRAOD算法在保证检测效果的前提下异常检测效率更高。

2.2.4 基于半监督的方法

STOD算法（semi-supervised trajectory outlier detection），利用半监督技术辅助离群轨迹探测过程，并在轨迹片段相似性度量中考虑轨迹形状，同时从整体局部两方面同时考察离群轨迹，使得探测出的异常轨迹更加合理。

2.2.5 基于轨迹模型的方法

该算法不依赖于先验知识，采用改进的LCSS距离作为度量，结合自适应聚类方法，实现轨迹的无监督建模过程。轨迹模型随输入数据实时更新，能够很好地适应统计特性变化的场景，具有较强的应用和推广价值。

3 研究展望

异常轨迹检测是一个非常有发展前景的数据挖掘研究和应用领域，尽管已经有了一些研究成果但是整体依然处于起步阶段，在终端区航空器的异常轨迹检测领域更是如此。以上各类方法具有不同的特点，但是依然存在诸多方面需要改进。

参数的输入，目前多数算法需要用户人工输入参数，并不断尝试已达到满意效果。自适应参数是以后的一个研究切入点；度量的选取，单一性度量无法全面反映数据的联系，全面分析数据并提高挖掘精度是今后工作重点；准确性，在基于轨迹片段划分的算法中，采用各种原则和距离进行的划分都不同程度的牺牲了准确性，选取适当的划分准则对提高检测效果至关重要；时间性，航空器的轨迹构型与飞行速度紧密相关，多数算法只考虑了轨迹的空间信息，而忽略了轨迹的时间维信息。融合轨迹的空间和时间维，将是未来的研究方向；算法复杂度，当轨迹数量较多时，算法的时间复杂度较大影响检测效率，有待提高；评价方法，面对诸多异常轨迹检测方法，如何客观的定量的评价检测结果是尚未以及难以解决的问题。

4 结语

本文针对终端区航空器异常轨迹检测领域分析了传统的检测方法，同时总结了现有的各类改进方法，并对今后的改进和创新切入点做出了归纳。客观全面的展现该领域现阶段研究状态的同时，为各类方法的改进提供了建议性的观点和理论参考。

参考文献：

[1]姜金凤.移动对象轨道异常检测算法的研究.南京：南京航空航天大学，2010.

[2]姚明宇.基于人工免疫的轨迹聚类和异常检测算法研究.南京：南京航空航天大学，2011.

[3]陈刚，钱猛，刘金.基于划分的高效异常轨迹检测.计算机工程与应用， 2013.

[4]Guan Yuan， Shixiong Xia， Lei Zhang， Yong Zhou， Cheng Ji.Trajectory Outlier Detection Algorithm Based on Structural Features. School of Computer Science and Technology， China University of Mining and Technology，2011

[5]Jae-Gil Lee，Jiawei Han，Xiaolei Li.Trajectory Outlier Detection：A Partition-and-Detect Framework. Department of Computer Science， University of Illinois at Urbana-Champaign，2011.endprint