QAR數(shù)據(jù)多維子序列的相似性搜索

楊 慧，張國(guó)振

中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300

1 前言

QAR數(shù)據(jù)是對(duì)飛機(jī)飛行狀態(tài)和性能參數(shù)的記錄，是檢修人員進(jìn)行飛機(jī)維護(hù)，專家確定飛機(jī)故障的重要依據(jù)。根據(jù)故障模型對(duì)QAR數(shù)據(jù)庫(kù)進(jìn)行相似性搜索和匹配，可以有效地發(fā)現(xiàn)該類故障，并確定故障點(diǎn)，故障模型由專家通過(guò)專業(yè)知識(shí)和經(jīng)驗(yàn)來(lái)建立。此外也可以根據(jù)專家給出的正常模型，對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索，找出與之不相似的序列，然后供專家進(jìn)一步確定故障，為民航的安全飛行提供決策支持和保障。Yang K，Shahabi C[1]認(rèn)為多元時(shí)間序列的多個(gè)參數(shù)之間存在一定的關(guān)聯(lián)，這些參數(shù)應(yīng)該作為一個(gè)整體看待而不應(yīng)該割裂開(kāi)來(lái)?？紤]到QAR數(shù)據(jù)具有數(shù)據(jù)量大，維度高的特點(diǎn)，特別地針對(duì)飛機(jī)故障通常不是由單一因素造成的，不同飛機(jī)故障受各維度的影響程度不同，并且維與維之間存在著難以確定的聯(lián)系，本文引入層次分析法（Analytic Hierarchy Process，AHP）來(lái)確定與指定故障類型有關(guān)的維度及其重要度。該方法通過(guò)建立系統(tǒng)的遞階層次，構(gòu)造判斷矩陣，將決策過(guò)程量化，并通過(guò)一致性檢驗(yàn)對(duì)偏差進(jìn)行調(diào)整。Lee S，Chun S，Kim D[2]把多維時(shí)間序列看成多維空間中的一條曲線，然后計(jì)算查詢曲線與待查曲線之間的距離。但該方法只能體現(xiàn)序列間的整體關(guān)系，而不能體現(xiàn)局部變化。飛機(jī)發(fā)生故障表現(xiàn)在QAR數(shù)據(jù)上主要是數(shù)值的波動(dòng)和變化情況，飛機(jī)故障關(guān)注局部的變化而且對(duì)數(shù)值敏感。因此本文采用波形與距離相結(jié)合的度量方法，先對(duì)多維子序列進(jìn)行符號(hào)化表示，然后利用符號(hào)序列作為特征值，建立基于形狀的k-d樹(shù)[3]作為多維子序列的索引。在k-d樹(shù)中對(duì)已確定的故障模型進(jìn)行查找，得到波形相似的序列候選集。最后通過(guò)基于權(quán)重的多維時(shí)序序列的距離度量公式進(jìn)一步篩選，權(quán)重通過(guò)AHP算法計(jì)算得到。

2 AHP層次分析法

不同類型的故障受各維度的影響程度不同，可以通過(guò)加權(quán)歐氏距離來(lái)體現(xiàn)，但這要求分析者對(duì)數(shù)據(jù)的意義等相關(guān)專業(yè)知識(shí)有相當(dāng)?shù)牧私?，這在實(shí)際中很難保證。所以引入AHP以確定各維度的權(quán)值。AHP[4]能夠合理地把定性和定量的決策結(jié)合起來(lái)，按照思維、心理的規(guī)律把決策過(guò)程層次化、數(shù)量化，從而避免了人的主觀性導(dǎo)致權(quán)重與客觀實(shí)際情況相矛盾。運(yùn)用AHP法進(jìn)行決策的4個(gè)步驟[5]：

步驟1建立系統(tǒng)的遞階層次結(jié)構(gòu)。

步驟2構(gòu)造兩兩比較判斷矩陣。

首先對(duì)各維進(jìn)行重要度比較。這個(gè)工作需要借助相關(guān)專家的經(jīng)驗(yàn)知識(shí)，回答相對(duì)某個(gè)準(zhǔn)則兩維di與dj之間的重要程度。一般采用1至9的表示方法，其中數(shù)值1表示維di相對(duì)維dj具有同樣的重要性，數(shù)值3，5，7，9依次表示維di相對(duì)維dj前者比后者稍重要、明顯重要、強(qiáng)烈重要、極端重要，數(shù)值2、4、6、8表示維di相對(duì)于維dj的重要程度位于前面判斷的中間值，并用相應(yīng)上述數(shù)值的倒數(shù)來(lái)表示一個(gè)因素比另一個(gè)因素不重要的程度。本文對(duì)襟翼故障進(jìn)行分析，專家通過(guò)上述方法獲得各維度重要度的分析矩陣如表1所示，其中T.E表示后緣襟翼，L.E表示前緣襟翼。

步驟3運(yùn)用方根近似方法求得各指標(biāo)的權(quán)值。

文獻(xiàn)[5]給出了具體的計(jì)算過(guò)程，w1,w2,…,w7分別對(duì)應(yīng)上述相應(yīng)的屬性維度的權(quán)值：

步驟4進(jìn)行一致性檢驗(yàn)。

人為確定各維度重要程度可能會(huì)出現(xiàn)相互矛盾的現(xiàn)象，因此需要對(duì)判斷矩陣進(jìn)行一致性檢測(cè)。文獻(xiàn)[6]給出了AHP一致性檢驗(yàn)的方法，當(dāng)隨機(jī)一致性比例C R＜0.10時(shí)，認(rèn)為結(jié)果一致，通過(guò)計(jì)算得到的C R=0.120 8＞0.1，因此需要進(jìn)行偏差修正，直到一致性滿足要求為止，此處采用偏差最大項(xiàng)修改法進(jìn)行了兩次偏差修正，C R=0.092＜0.1，對(duì)于襟翼故障，各維度重要度權(quán)值如下：

3 相似性搜索

QAR多維子序列的相似性搜索問(wèn)題描述如[2]：一個(gè)k維QAR序列由多維空間中的點(diǎn)組成，記為S=(S[0],S[1],…,S[n-1])，其中 S[i]=(S[i,0],S[i,1],…,S[i,k-1])是一個(gè)k元向量；n表示序列的長(zhǎng)度，k表示序列的維數(shù)，給定一個(gè)QAR數(shù)據(jù)庫(kù)，它包括N個(gè)可能不相等的多維QAR序列S0,S1,…,SN-1，給定查詢序列Q以及允許誤差ε，找出數(shù)據(jù)庫(kù)中所有的多維QAR序列Si(0≤i≤N-1)及其每個(gè)子序列 Si[j:j+L en(Q)-1](0≤j≤Len(Si)-L en(Q))使得子序列與Q起伏形狀相似且它們之間的距離小于ε。距離的度量采用帶權(quán)的歐幾里德距離，公式定義如下：

定義1給定兩個(gè)長(zhǎng)度為n的多維QAR序列s1和s2,s1和s2之間的距離可以定義為：

其中d(s1[i],s2[i])表示s1和s2中任意兩點(diǎn)之間的歐幾里德距離[7]：

其中wi為第i維的權(quán)重。由AHP算法計(jì)算得到。

定義2 s1和s2的任意兩點(diǎn)的帶權(quán)歐幾里德距離[7]為：

4 QAR數(shù)據(jù)的符號(hào)化表示

QAR數(shù)據(jù)不同維度的采樣頻率不同，符號(hào)化之前要先進(jìn)行數(shù)據(jù)的預(yù)處理，采用分段集成近似算法（Piecewise Aggregate Approximation，PAA）[8-9]，可以將長(zhǎng)度為n的時(shí)間序列進(jìn)行降維，將其轉(zhuǎn)換為長(zhǎng)度w的離散字符序列=

經(jīng)過(guò)上述操作使得QAR數(shù)據(jù)各維的采樣頻率一致，對(duì)于給定的多維QAR序列S=(S[0],S[1],…,S[n-1])，它在每一維上的投影Sj=(S[0,j],S[1,j],…,S[n-1,j])(0≤j≤k-1)是一個(gè)一維時(shí)間序列，通過(guò)描繪每個(gè)Sj的形狀特征可以表示S的形狀特征。在每個(gè)數(shù)據(jù)點(diǎn)處用垂直線將序列分割，對(duì)于分隔的每一條線段，若上升，則用“1”表示，若下降用“0”表示；若水平則一律視為上升，為避免曲線起伏過(guò)于頻繁，消除噪聲的干擾，將數(shù)據(jù)序列L=(l0,l1,…,ln-1)分成h段，并計(jì)算段內(nèi)的趨勢(shì)，其計(jì)算過(guò)程如下公式：

表1 襟翼故障屬性調(diào)查表

sh a pe(i)產(chǎn)生的長(zhǎng)度為h的“0”，“1”串，作為序列L的形狀特征值。

5 QAR數(shù)據(jù)k-d樹(shù)索引的建立

利用QAR數(shù)據(jù)的多維子序列相似性搜索來(lái)檢測(cè)飛機(jī)故障，必須保證信息的完整性，因此必須采用滑動(dòng)窗口技術(shù)來(lái)劃分子序列。可將故障模型序列的長(zhǎng)度設(shè)定為窗口的大小，對(duì)子序列進(jìn)行信息提取，構(gòu)造信息結(jié)點(diǎn)，內(nèi)容主要包括QAR源序列在數(shù)據(jù)庫(kù)中的ID，子序列相對(duì)于源序列的偏移量，子序列的特征向量S F，以及指向下一個(gè)信息結(jié)點(diǎn)的指針。k-d樹(shù)是一種多維二叉搜索樹(shù)，在本文中，k-d樹(shù)的結(jié)點(diǎn)由四部分組成，依次是：子序列的形狀特征向量S F=[S F0,S F1,…,S Fk-1]；鑒別器axis，它表示在某結(jié)點(diǎn)處應(yīng)該比較哪個(gè)S F分量；頭結(jié)點(diǎn)的指針，它指向一個(gè)鏈表，該鏈表由具有形同形狀特征向量的子序列信息結(jié)點(diǎn)組成；指向左孩子的指針LeftChild和指向右孩子的指針RightChild。文獻(xiàn)[9]給出了k-d樹(shù)要滿足的性質(zhì)以及建樹(shù)和搜索的算法。

6 相關(guān)實(shí)驗(yàn)

取某航空公司CAB738型飛機(jī)的2008年8月份的30個(gè)航班記錄，每個(gè)航班記錄序列的長(zhǎng)度為6 089～11 949不等，作為實(shí)驗(yàn)1，以及2008年8月-2009年2月共180個(gè)航班記錄，每個(gè)航班記錄的序列長(zhǎng)度為4 000～12 000不等的航班記錄為實(shí)驗(yàn)數(shù)據(jù)作，作為實(shí)驗(yàn)2，選擇與襟翼故障最相關(guān)的 T.E.FlapPosition-Left，T.E.FlapPosition-Right，F(xiàn)lapHandle-Position作為實(shí)驗(yàn)維度，通過(guò)專家確定的襟翼故障模型如圖1。

圖1 CAB738型飛機(jī)襟翼故障模型

故障模型數(shù)據(jù)長(zhǎng)度為201，分段參數(shù)h=5，允許誤差ε=3.5，符號(hào)化編碼后的特征向量表示為[01010，01010，01010]，建立k-d樹(shù)，進(jìn)行相似性搜索，對(duì)剪枝率Prune，精確率Precision，以及查全率Recall進(jìn)行計(jì)算：

實(shí)驗(yàn)1的剪枝率達(dá)到99.6%，實(shí)驗(yàn)2的剪枝率達(dá)到99.2%，而文獻(xiàn)[2]中的方法，剪枝率最好情況下只能達(dá)到92%～94%。由圖2可以看出，利用本文的方法，當(dāng)ε=3.5時(shí)Precision達(dá)到95%。由于飛機(jī)故障檢測(cè)不允許出現(xiàn)漏報(bào)，因此要對(duì)多維QAR數(shù)據(jù)的所有子序列進(jìn)行相似性的匹配，故文中采用步長(zhǎng)為1的滑動(dòng)窗口，取遍所有子序列，并提取落入窗口的子序列特征，保證了查詢結(jié)果的完備性，即查全率Recall為1，文獻(xiàn)[2]中采用序列的無(wú)重疊分段方法，將序列分為若干個(gè)最小邊界矩形的方式，必然存在各分段間信息的丟失，無(wú)法保證算法在查詢結(jié)果方面的完整性。

圖2 兩實(shí)驗(yàn)不同閾值情況下精確率的比較

圖3為建立k-d樹(shù)所用時(shí)間隨時(shí)間序列規(guī)模的變化情況，橫坐標(biāo)每增加一個(gè)單位即序列規(guī)模增加一個(gè)月的航班記錄。實(shí)驗(yàn)表明了在短時(shí)間內(nèi)建立k-d樹(shù)，用于相似性的搜索的可行性。

圖3 建立k-d樹(shù)所用時(shí)間

圖4為通過(guò)k-d樹(shù)對(duì)故障模型進(jìn)行查詢與順序掃描花費(fèi)時(shí)間的對(duì)比情況。

由圖4可以看出，對(duì)符號(hào)化后的多維時(shí)序飛行數(shù)據(jù)的子序列，使用k-d樹(shù)進(jìn)行查找的速度要遠(yuǎn)遠(yuǎn)快于順序掃描的速度。該方法適用于大規(guī)模時(shí)序飛行序列中子序列的相似性搜索。

7 結(jié)論和展望

圖4 k-d搜索與順序搜索所花時(shí)間比較

多維時(shí)序飛行數(shù)據(jù)子序列的相似性搜索問(wèn)題是開(kāi)發(fā)飛機(jī)故障檢測(cè)和預(yù)警系統(tǒng)中的關(guān)鍵問(wèn)題，現(xiàn)有的一些方法沒(méi)有考慮到各個(gè)屬性對(duì)故障發(fā)生的不同影響程度，由于計(jì)算量巨大，直接使用距離度量來(lái)計(jì)算飛行序列與查詢序列之間的相似性來(lái)進(jìn)行搜索對(duì)于大規(guī)模數(shù)據(jù)不可行，而且相似度的準(zhǔn)確性較低，針對(duì)以上問(wèn)題，使用AHP層次分析法來(lái)確定各屬性維度對(duì)于指定故障發(fā)生的重要度。在相似性的度量上，利用波形和距離相結(jié)合的方法，抽取子序列的形狀特征進(jìn)行符號(hào)化表示，并用k-d樹(shù)進(jìn)行索引，搜索k-d樹(shù)，找到與故障模型具有相同波形的子序列作為查詢候選集，剪枝率達(dá)到99%以上，然后對(duì)候選集對(duì)應(yīng)的子序列的原記錄進(jìn)行基于各維權(quán)重的多維距離度量，極大地提高了查詢效率和正確率。下一步的工作是：針對(duì)專家提供的距離閾值ε的取值，找到更加客觀準(zhǔn)確的方法來(lái)確定。可以根據(jù)飛行手冊(cè)中對(duì)飛機(jī)故障各屬性取值范圍的明確規(guī)定，確定取值的上界和下界，然后計(jì)算得到一個(gè)最小邊界距離，作為ε的取值。

[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].模糊系統(tǒng)與數(shù)學(xué)，2000，4（2）：89-91.

[6]許樹(shù)伯.層次分析原理[M].天津：天津大學(xué)出版社，1998.

[7]Agrawal R，F(xiàn)aloutsos 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.