QAR数据多维子序列的相似性搜索

杨 慧，张国振

中国民航大学 计算机科学与技术学院，天津 300300

1 前言

QAR数据是对飞机飞行状态和性能参数的记录，是检修人员进行飞机维护，专家确定飞机故障的重要依据。根据故障模型对QAR数据库进行相似性搜索和匹配，可以有效地发现该类故障，并确定故障点，故障模型由专家通过专业知识和经验来建立。此外也可以根据专家给出的正常模型，对数据库进行搜索，找出与之不相似的序列，然后供专家进一步确定故障，为民航的安全飞行提供决策支持和保障。Yang K，Shahabi C[1]认为多元时间序列的多个参数之间存在一定的关联，这些参数应该作为一个整体看待而不应该割裂开来。考虑到QAR数据具有数据量大，维度高的特点，特别地针对飞机故障通常不是由单一因素造成的，不同飞机故障受各维度的影响程度不同，并且维与维之间存在着难以确定的联系，本文引入层次分析法（Analytic Hierarchy Process，AHP）来确定与指定故障类型有关的维度及其重要度。该方法通过建立系统的递阶层次，构造判断矩阵，将决策过程量化，并通过一致性检验对偏差进行调整。Lee S，Chun S，Kim D[2]把多维时间序列看成多维空间中的一条曲线，然后计算查询曲线与待查曲线之间的距离。但该方法只能体现序列间的整体关系，而不能体现局部变化。飞机发生故障表现在QAR数据上主要是数值的波动和变化情况，飞机故障关注局部的变化而且对数值敏感。因此本文采用波形与距离相结合的度量方法，先对多维子序列进行符号化表示，然后利用符号序列作为特征值，建立基于形状的k-d树[3]作为多维子序列的索引。在k-d树中对已确定的故障模型进行查找，得到波形相似的序列候选集。最后通过基于权重的多维时序序列的距离度量公式进一步筛选，权重通过AHP算法计算得到。

2 AHP层次分析法

不同类型的故障受各维度的影响程度不同，可以通过加权欧氏距离来体现，但这要求分析者对数据的意义等相关专业知识有相当的了解，这在实际中很难保证。所以引入AHP以确定各维度的权值。AHP[4]能够合理地把定性和定量的决策结合起来，按照思维、心理的规律把决策过程层次化、数量化，从而避免了人的主观性导致权重与客观实际情况相矛盾。运用AHP法进行决策的4个步骤[5]：

步骤1建立系统的递阶层次结构。

步骤2构造两两比较判断矩阵。

首先对各维进行重要度比较。这个工作需要借助相关专家的经验知识，回答相对某个准则两维di与dj之间的重要程度。一般采用1至9的表示方法，其中数值1表示维di相对维dj具有同样的重要性，数值3，5，7，9依次表示维di相对维dj前者比后者稍重要、明显重要、强烈重要、极端重要，数值2、4、6、8表示维di相对于维dj的重要程度位于前面判断的中间值，并用相应上述数值的倒数来表示一个因素比另一个因素不重要的程度。本文对襟翼故障进行分析，专家通过上述方法获得各维度重要度的分析矩阵如表1所示，其中T.E表示后缘襟翼，L.E表示前缘襟翼。

步骤3运用方根近似方法求得各指标的权值。

文献[5]给出了具体的计算过程，w1,w2,…,w7分别对应上述相应的属性维度的权值：

步骤4进行一致性检验。

人为确定各维度重要程度可能会出现相互矛盾的现象，因此需要对判断矩阵进行一致性检测。文献[6]给出了AHP一致性检验的方法，当随机一致性比例C R＜0.10时，认为结果一致，通过计算得到的C R=0.120 8＞0.1，因此需要进行偏差修正，直到一致性满足要求为止，此处采用偏差最大项修改法进行了两次偏差修正，C R=0.092＜0.1，对于襟翼故障，各维度重要度权值如下：

3 相似性搜索

QAR多维子序列的相似性搜索问题描述如[2]：一个k维QAR序列由多维空间中的点组成，记为S=(S[0],S[1],…,S[n-1])，其中 S[i]=(S[i,0],S[i,1],…,S[i,k-1])是一个k元向量；n表示序列的长度，k表示序列的维数，给定一个QAR数据库，它包括N个可能不相等的多维QAR序列S0,S1,…,SN-1，给定查询序列Q以及允许误差ε，找出数据库中所有的多维QAR序列Si(0≤i≤N-1)及其每个子序列 Si[j:j+L en(Q)-1](0≤j≤Len(Si)-L en(Q))使得子序列与Q起伏形状相似且它们之间的距离小于ε。距离的度量采用带权的欧几里德距离，公式定义如下：

定义1给定两个长度为n的多维QAR序列s1和s2,s1和s2之间的距离可以定义为：

其中d(s1[i],s2[i])表示s1和s2中任意两点之间的欧几里德距离[7]：

其中wi为第i维的权重。由AHP算法计算得到。

定义2 s1和s2的任意两点的带权欧几里德距离[7]为：

4 QAR数据的符号化表示

QAR数据不同维度的采样频率不同，符号化之前要先进行数据的预处理，采用分段集成近似算法（Piecewise Aggregate Approximation，PAA）[8-9]，可以将长度为n的时间序列进行降维，将其转换为长度w的离散字符序列=

经过上述操作使得QAR数据各维的采样频率一致，对于给定的多维QAR序列S=(S[0],S[1],…,S[n-1])，它在每一维上的投影Sj=(S[0,j],S[1,j],…,S[n-1,j])(0≤j≤k-1)是一个一维时间序列，通过描绘每个Sj的形状特征可以表示S的形状特征。在每个数据点处用垂直线将序列分割，对于分隔的每一条线段，若上升，则用“1”表示，若下降用“0”表示；若水平则一律视为上升，为避免曲线起伏过于频繁，消除噪声的干扰，将数据序列L=(l0,l1,…,ln-1)分成h段，并计算段内的趋势，其计算过程如下公式：

表1 襟翼故障属性调查表

sh a pe(i)产生的长度为h的“0”，“1”串，作为序列L的形状特征值。

5 QAR数据k-d树索引的建立

利用QAR数据的多维子序列相似性搜索来检测飞机故障，必须保证信息的完整性，因此必须采用滑动窗口技术来划分子序列。可将故障模型序列的长度设定为窗口的大小，对子序列进行信息提取，构造信息结点，内容主要包括QAR源序列在数据库中的ID，子序列相对于源序列的偏移量，子序列的特征向量S F，以及指向下一个信息结点的指针。k-d树是一种多维二叉搜索树，在本文中，k-d树的结点由四部分组成，依次是：子序列的形状特征向量S F=[S F0,S F1,…,S Fk-1]；鉴别器axis，它表示在某结点处应该比较哪个S F分量；头结点的指针，它指向一个链表，该链表由具有形同形状特征向量的子序列信息结点组成；指向左孩子的指针LeftChild和指向右孩子的指针RightChild。文献[9]给出了k-d树要满足的性质以及建树和搜索的算法。

6 相关实验

取某航空公司CAB738型飞机的2008年8月份的30个航班记录，每个航班记录序列的长度为6 089～11 949不等，作为实验1，以及2008年8月-2009年2月共180个航班记录，每个航班记录的序列长度为4 000～12 000不等的航班记录为实验数据作，作为实验2，选择与襟翼故障最相关的 T.E.FlapPosition-Left，T.E.FlapPosition-Right，FlapHandle-Position作为实验维度，通过专家确定的襟翼故障模型如图1。

图1 CAB738型飞机襟翼故障模型

故障模型数据长度为201，分段参数h=5，允许误差ε=3.5，符号化编码后的特征向量表示为[01010，01010，01010]，建立k-d树，进行相似性搜索，对剪枝率Prune，精确率Precision，以及查全率Recall进行计算：

实验1的剪枝率达到99.6%，实验2的剪枝率达到99.2%，而文献[2]中的方法，剪枝率最好情况下只能达到92%～94%。由图2可以看出，利用本文的方法，当ε=3.5时Precision达到95%。由于飞机故障检测不允许出现漏报，因此要对多维QAR数据的所有子序列进行相似性的匹配，故文中采用步长为1的滑动窗口，取遍所有子序列，并提取落入窗口的子序列特征，保证了查询结果的完备性，即查全率Recall为1，文献[2]中采用序列的无重叠分段方法，将序列分为若干个最小边界矩形的方式，必然存在各分段间信息的丢失，无法保证算法在查询结果方面的完整性。

图2 两实验不同阈值情况下精确率的比较

图3为建立k-d树所用时间随时间序列规模的变化情况，横坐标每增加一个单位即序列规模增加一个月的航班记录。实验表明了在短时间内建立k-d树，用于相似性的搜索的可行性。

图3 建立k-d树所用时间

图4为通过k-d树对故障模型进行查询与顺序扫描花费时间的对比情况。

由图4可以看出，对符号化后的多维时序飞行数据的子序列，使用k-d树进行查找的速度要远远快于顺序扫描的速度。该方法适用于大规模时序飞行序列中子序列的相似性搜索。

7 结论和展望

图4 k-d搜索与顺序搜索所花时间比较

多维时序飞行数据子序列的相似性搜索问题是开发飞机故障检测和预警系统中的关键问题，现有的一些方法没有考虑到各个属性对故障发生的不同影响程度，由于计算量巨大，直接使用距离度量来计算飞行序列与查询序列之间的相似性来进行搜索对于大规模数据不可行，而且相似度的准确性较低，针对以上问题，使用AHP层次分析法来确定各属性维度对于指定故障发生的重要度。在相似性的度量上，利用波形和距离相结合的方法，抽取子序列的形状特征进行符号化表示，并用k-d树进行索引，搜索k-d树，找到与故障模型具有相同波形的子序列作为查询候选集，剪枝率达到99%以上，然后对候选集对应的子序列的原记录进行基于各维权重的多维距离度量，极大地提高了查询效率和正确率。下一步的工作是：针对专家提供的距离阈值ε的取值，找到更加客观准确的方法来确定。可以根据飞行手册中对飞机故障各属性取值范围的明确规定，确定取值的上界和下界，然后计算得到一个最小边界距离，作为ε的取值。

[1]Yang K，Shahabi C.A PCA-based similarity measure for multivariate time series[C]//Proc of MMDB’04.Washington DC，USA：ACM Press，2004.

[2]Lee S，Chun S，Kim D.Similarity search for multidimensional data sequences[C]//Proc of the 16th Int’1 Conf on Data Engineering.Washington：IEEE Computer Society，2000：599-608.

[3]Bentley J.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[4]Saaty T L.The analytic hierarchy process[M].New York：McGraw-Hill，1980.

[5] 张吉军.模糊层次分析法[J].模糊系统与数学，2000，4（2）：89-91.

[6]许树伯.层次分析原理[M].天津：天津大学出版社，1998.

[7]Agrawal R，Faloutsos C，Swami A.Efficient similarity search in sequences database[C]//Proc of the 4th Int’l Conf of Foundations of Data Organization and Algorithms.Chicago：Springer-Verlag，1993：69-84.

[8]Keogh E，Chakrabarti K，Pazzani M，et al.Dimensionality reduction for fast similarity search in large time series databases[J].Knowledge and Information System，2000，3（3）：263-286.

[9]Shieh J，Keogh E.iSAX：indexing and mining terabyte sized time series[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2008：623-631.

[10]Huang He，Shi Zhongzhi，Zheng Zhen.Similarity search based on shape k-d tree for multidimensional time sequences[J].Journal of Software，2006，17（10）：2048-2056.