基于分段距离和子序列匹配的飞机故障检测

马发民+王锦彪+张林

摘要：针对飞机故障检测数据中重复率高数据量大，监测算法效率和准确率低的问题，本文在PAA压缩数据的基础上使用分段概率提取细分QAR数据，调整FP-Growth算法创建独具特色FP-Tree降低数据的重复度，提高数据的查询速度，提出了基于分段距离和子序列匹配算法，本文采用真实的飞机飞行QAR数据验证该算法的有效性和准确度。

关键词：飞机故障检测； 分段概率提取；QAR数据；FP-Tree；子序列匹配

中图分类号：TP301 文献标识码：A

Abstract： As about high repetition and large volume of data in airplane fault detection data as well as low efficiency and accuracy of monitoring algorithm， this paper， based on PAA packed data， utilizes Segmental Probability to extract， adjust FP-Growth and establish FP-Tree， thereby reducing repetition degree of data and improving its searching speed. In addition， algorithm on the basis of segmental distance and subsequence match is proposed. In this paper， the real QAR data of flight will be adopted to verify reliability and accurateness of the algorithm.

Key words： airplane fault detection；segmental probability extract；QAR data；FP-Tree；subsequence matc

1對QAR数据建立分段后的树形结构

飞机飞行状态通常是稳定的，即QAR数据的属性值大量重复出现[1-2]，如此使得分段后的数据规律跟关联规则挖掘中大量项目同时出现的情况很类似[3]，因而可以把每个数据段当作一个项集，采用类似频繁项集挖掘的方法对其进一步信息整合，将类似的数据段集中到相近的位置，相同数据段只计算一次，提高数据搜索匹配的效率。

分段概率提取后的21元组的元素顺序既定[4]，在使用FP-Growth算法进行建树操作之前，不需第一步扫描数据库并按各项支持数进行排序，只需直接进行类似FP-Growth模式增长的建树操作。需要增加的是在该FP树的每个叶子节点上要添加一个indexList链表，用以记录所有重复了从根节点到叶子节点的所有数据域的数据段，即每条从根节点到叶子节点的路径都代表一个数据段，而indexList则记录了跟本路径相同的所有数据段标记。建树过程可通过以下示例对分段后所形成数据段S={ 0：[0，...， 0， 0.97， 0.03， 0， 0 ]T， 1： [ 0，...， 0， 0.94， 0.06 ， 0， 0]T， 2： [0，...， 0， 0.98， 0.02 ， 0， 0]T， 3：[ 0，...， 0， 0.97， 0.03， 0， 0]T}的处理具体描述如下：

①创建T的根节点，标号为“null”（如图1中的（1）），T节点含有如下成员：节点数据（data），指向其子节点的指针和指向其右节点的指针；

②读取下一段数据（现在是第一个元组）0：[0，...， 0， 0.97， 0.03， 0， 0 ]T，在T中从根节点开始搜索。首先搜索0， T中如果有此节点，接着搜索下一个元素0.97；T中没有此节点，于是不用再继续搜索，直接建立整个0：[0，...， 0， 0.97， 0.03， 0， 0 ]T序列的子树（如图1中（2）所示，其中多个连续重复出现的符号在图中只出现一次，并在其节点数据后的括号中标注其连续出现的次数，如图5-1中的（2）中根节点的左子节点0.0（15）表示0.0共连续出现了15次），建立到叶子节点后，看该叶子节点是否存在名为indexList的一个索引链表，若存在，则直接将正在处理的数据段的段号添加到indexList中若不存在则为该叶子节点创建indexList链表，并添加当前段号到indexList中；

③重复过程②，直到S中的最后一个数据段处理完毕，对S的第二段数据处理后fp树如图1中的（3）所示。S全部数据段处理完毕后fp树如图1中的（4）所示。

2子序列匹配定位故障数据段

树型数据结构由于其前缀共享的特点，能够避免数据操作过程中大量的重复操作，大幅提高数据处理效率。数据大爆炸环境下，为高效处理数据，无不考虑引入树型结构改进算法，例如文献[5]中将DFST-Tree结构引入数据流挖掘算法研究，而在人工智能与数据挖掘方向的prifix前缀树与FP-Growth等算法更是久负盛名。目前树型结构用于匹配查询方向的算法如k-d树查询[6]及子树匹配，前者是从k-d树中查询给定序列，给定序列并非树型结构；后者则用于查询两棵树的结构是否类似，但是并不关心树的节点数据。本文基于FP-Growth算法对分段后的源数据序列建立树形结构，然后根据故障模型进行序列匹配，定位到可能出现故障的数据段。序列匹配定位算法的具体描述如下：

先序遍历fp树，从根节点到每个叶节点的路径都是一个数据段的代表，从根节点搜索到叶节点的匹配过程如下：

①计算加入当前节点后该条路径上所有点与故障模型的距离，若距离小于给定阈值，检查当前节点是否为叶子节点，若是转③，若不是叶子节点转②；若距离大于给定阈值则剪去该节点及其所有左子节点并转②。

②转入当前节点的左子树并重复步骤①。

③当前节点已经是叶子节点，且从根节点到叶子节点整条路径上所有点与故障模型的距离不超过给定阈值，则该条路径所代表的数据段即为与故障模型匹配成功，得到叶子节点的indexList链表，即为故障数据段位置链表，本条路径匹配完毕。

3实验结果及分析

取航空公司CAB737-800型飞机的2008年8月份的25个航班记录，每个航班记录序列的长度为6089～11949不等，数据分段段长取100，数据符号化范围为0到20。飞机故障通常情况下不是由单一因素引起，面与飞机故障有关的不同属性在飞机发生故障过程中的重要程序也各不相同，根据专家经验给出的空中颠簸故障属性重要度调查表[7-8]，垂直加速度属性是对空中颠簸故障发生的最重要影响属性，因此主要针对该故障数据的垂直加速度属性数据实验。

文献[9-10]通过研究并验证k-d树的特点和优势，对QAR数据进行符号化并建立了多维时序飞行数据的子序列，并验证了k-d树查找的速度相比于顺序扫描的明显优势，适用于大规模时序飞行序列中子序列的相似性搜索。其实验结果如表1所示。

表1清晰表明了k-d树查找的速度远快于顺序扫描的速度，适合大规模时序飞行序列中子序列的相似性搜索。但是在k-d查询之前所需的建树时间依然不容忽视，本文通过分段符号化并概率提取然后再建树查询，分段及离散化共用时间平均为310.1ms，建树和查询所用时间之和平均仅为2.5ms。综合表1和表2，显然分段后的查询时间仅为不分段就顺序查询的一半，而采用树形结构查询之后搜索时间再一次得到提升，从建树到查询结束的总时间低于k-d树的僅查询时间。

另外子序列查找过程中以查找到的类似故障数据段为目标输出，并将类似故障数据段输出到到文件，当检测数据为模拟的非故障数据时，输出文件无内容，而当检测数据为模拟的故障数据时，输出文件中会得到如图2的结果，其中“文件0”是一个待检测的故障数据文件，“异常数据段0”则是故障模型中的一个故障点代表，与其相似的数据段表示采集到该待检测数据的航班有可能会发生与故障模型相同的故障。实验得到故障相似数据段之后可以根据其数据段号（比如图2中“数据段42”的“42”）来定位故障发生的具体位置。由此可见本程序可以正确识别出并定位本类型的故障数据段，具有相当的参考价值。

综上可知本文所用方法对于大规模数据处理具有足够的正确率和高效性。

4小结

本文主要介绍了针对突发故障点数据段的检测和定位方法，在PAA表示方法的基础上进一步对QAR数据进行分段细化，将故障点锁定在更小的数据段内，对于时序数据来说，能够定位到更贴近故障突发的时间段；通过基于树的子序列查询算法提高了搜索查询的效率的同时保证了查询的正确性，实验证明本文采用算法是有效可行的。

参考文献

[1] 王天明.基于QAR数据的飞行安全模型研究[D]：[硕士学位论文].天津：中国民航大学.航空自动化系，2008.

[2] 闫伟. QAR飞行时序数据相似性搜索算法研究[D]. 天津： 中国民航大学， 2010： 21-25.

[3] 赵恒. 数据挖掘中聚类若干问题研究[D]. 西安： 西安电子科技大学， 2005 ： 10-11.

[4] Jong P.Yoon，Jieun Lee，Sung Kim.Trend Similarity and Prediction in Time-Series Database.Proceeding of SPIE，2000，4057：13-20.

[5] Tomas Flouri， Jan Janousˇek， and Borˇivoj Melichar. Subtree Matching by Pushdown Automata. ComSIS， Special Issue， April 2010， 7（2） ：331-357.

[6] 张国振. 多元时序飞行数据子序列的相似性搜索算法研究[D]：[硕士学位论文]. 天津：中国民航大学. 计算机科学与技术学院， 2011.

[7] Chakrabarti，K. et al.， Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans on Database Systems， 27， 2002： 188-228.

[8] Kamran Rokhsaz， Linda K. Kliment， and Alhambra L. Yee， etc. Comparison of Two Business Jets – Usage and Flight Loads. 2013 Aviation Technology， Integration， and Operations Conference August 12-14， 2013， Los Angeles， CA.

[9] 肖辉.时间序列的相似性查询与异常检测[D]：[博士学位论文].上海：复旦大学.计算机与信息技术系，2005.

[10] 郝飞. 基于粗糙集的时序数据挖掘及其应用[D]. 成都： 西华大学， 2008： 9-10.