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.