馬發(fā)民+王錦彪+張林

摘要：針對(duì)飛機(jī)故障檢測(cè)數(shù)據(jù)中重復(fù)率高數(shù)據(jù)量大，監(jiān)測(cè)算法效率和準(zhǔn)確率低的問(wèn)題，本文在PAA壓縮數(shù)據(jù)的基礎(chǔ)上使用分段概率提取細(xì)分QAR數(shù)據(jù)，調(diào)整FP-Growth算法創(chuàng)建獨(dú)具特色FP-Tree降低數(shù)據(jù)的重復(fù)度，提高數(shù)據(jù)的查詢速度，提出了基于分段距離和子序列匹配算法，本文采用真實(shí)的飛機(jī)飛行QAR數(shù)據(jù)驗(yàn)證該算法的有效性和準(zhǔn)確度。

關(guān)鍵詞：飛機(jī)故障檢測(cè)； 分段概率提??；QAR數(shù)據(jù)；FP-Tree；子序列匹配

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：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對(duì)QAR數(shù)據(jù)建立分段后的樹(shù)形結(jié)構(gòu)

飛機(jī)飛行狀態(tài)通常是穩(wěn)定的，即QAR數(shù)據(jù)的屬性值大量重復(fù)出現(xiàn)[1-2]，如此使得分段后的數(shù)據(jù)規(guī)律跟關(guān)聯(lián)規(guī)則挖掘中大量項(xiàng)目同時(shí)出現(xiàn)的情況很類(lèi)似[3]，因而可以把每個(gè)數(shù)據(jù)段當(dāng)作一個(gè)項(xiàng)集，采用類(lèi)似頻繁項(xiàng)集挖掘的方法對(duì)其進(jìn)一步信息整合，將類(lèi)似的數(shù)據(jù)段集中到相近的位置，相同數(shù)據(jù)段只計(jì)算一次，提高數(shù)據(jù)搜索匹配的效率。

分段概率提取后的21元組的元素順序既定[4]，在使用FP-Growth算法進(jìn)行建樹(shù)操作之前，不需第一步掃描數(shù)據(jù)庫(kù)并按各項(xiàng)支持?jǐn)?shù)進(jìn)行排序，只需直接進(jìn)行類(lèi)似FP-Growth模式增長(zhǎng)的建樹(shù)操作。需要增加的是在該FP樹(shù)的每個(gè)葉子節(jié)點(diǎn)上要添加一個(gè)indexList鏈表，用以記錄所有重復(fù)了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有數(shù)據(jù)域的數(shù)據(jù)段，即每條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)據(jù)段，而indexList則記錄了跟本路徑相同的所有數(shù)據(jù)段標(biāo)記。建樹(shù)過(guò)程可通過(guò)以下示例對(duì)分段后所形成數(shù)據(jù)段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}的處理具體描述如下：

①創(chuàng)建T的根節(jié)點(diǎn)，標(biāo)號(hào)為“null”（如圖1中的（1）），T節(jié)點(diǎn)含有如下成員：節(jié)點(diǎn)數(shù)據(jù)（data），指向其子節(jié)點(diǎn)的指針和指向其右節(jié)點(diǎn)的指針；

②讀取下一段數(shù)據(jù)（現(xiàn)在是第一個(gè)元組）0：[0，...， 0， 0.97， 0.03， 0， 0 ]T，在T中從根節(jié)點(diǎn)開(kāi)始搜索。首先搜索0， T中如果有此節(jié)點(diǎn)，接著搜索下一個(gè)元素0.97；T中沒(méi)有此節(jié)點(diǎn)，于是不用再繼續(xù)搜索，直接建立整個(gè)0：[0，...， 0， 0.97， 0.03， 0， 0 ]T序列的子樹(shù)（如圖1中（2）所示，其中多個(gè)連續(xù)重復(fù)出現(xiàn)的符號(hào)在圖中只出現(xiàn)一次，并在其節(jié)點(diǎn)數(shù)據(jù)后的括號(hào)中標(biāo)注其連續(xù)出現(xiàn)的次數(shù)，如圖5-1中的（2）中根節(jié)點(diǎn)的左子節(jié)點(diǎn)0.0（15）表示0.0共連續(xù)出現(xiàn)了15次），建立到葉子節(jié)點(diǎn)后，看該葉子節(jié)點(diǎn)是否存在名為indexList的一個(gè)索引鏈表，若存在，則直接將正在處理的數(shù)據(jù)段的段號(hào)添加到indexList中若不存在則為該葉子節(jié)點(diǎn)創(chuàng)建indexList鏈表，并添加當(dāng)前段號(hào)到indexList中；

③重復(fù)過(guò)程②，直到S中的最后一個(gè)數(shù)據(jù)段處理完畢，對(duì)S的第二段數(shù)據(jù)處理后fp樹(shù)如圖1中的（3）所示。S全部數(shù)據(jù)段處理完畢后fp樹(shù)如圖1中的（4）所示。

2子序列匹配定位故障數(shù)據(jù)段

樹(shù)型數(shù)據(jù)結(jié)構(gòu)由于其前綴共享的特點(diǎn)，能夠避免數(shù)據(jù)操作過(guò)程中大量的重復(fù)操作，大幅提高數(shù)據(jù)處理效率。數(shù)據(jù)大爆炸環(huán)境下，為高效處理數(shù)據(jù)，無(wú)不考慮引入樹(shù)型結(jié)構(gòu)改進(jìn)算法，例如文獻(xiàn)[5]中將DFST-Tree結(jié)構(gòu)引入數(shù)據(jù)流挖掘算法研究，而在人工智能與數(shù)據(jù)挖掘方向的prifix前綴樹(shù)與FP-Growth等算法更是久負(fù)盛名。目前樹(shù)型結(jié)構(gòu)用于匹配查詢方向的算法如k-d樹(shù)查詢[6]及子樹(shù)匹配，前者是從k-d樹(shù)中查詢給定序列，給定序列并非樹(shù)型結(jié)構(gòu)；后者則用于查詢兩棵樹(shù)的結(jié)構(gòu)是否類(lèi)似，但是并不關(guān)心樹(shù)的節(jié)點(diǎn)數(shù)據(jù)。本文基于FP-Growth算法對(duì)分段后的源數(shù)據(jù)序列建立樹(shù)形結(jié)構(gòu)，然后根據(jù)故障模型進(jìn)行序列匹配，定位到可能出現(xiàn)故障的數(shù)據(jù)段。序列匹配定位算法的具體描述如下：

先序遍歷fp樹(shù)，從根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)的路徑都是一個(gè)數(shù)據(jù)段的代表，從根節(jié)點(diǎn)搜索到葉節(jié)點(diǎn)的匹配過(guò)程如下：

①計(jì)算加入當(dāng)前節(jié)點(diǎn)后該條路徑上所有點(diǎn)與故障模型的距離，若距離小于給定閾值，檢查當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，若是轉(zhuǎn)③，若不是葉子節(jié)點(diǎn)轉(zhuǎn)②；若距離大于給定閾值則剪去該節(jié)點(diǎn)及其所有左子節(jié)點(diǎn)并轉(zhuǎn)②。

②轉(zhuǎn)入當(dāng)前節(jié)點(diǎn)的左子樹(shù)并重復(fù)步驟①。

③當(dāng)前節(jié)點(diǎn)已經(jīng)是葉子節(jié)點(diǎn)，且從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)整條路徑上所有點(diǎn)與故障模型的距離不超過(guò)給定閾值，則該條路徑所代表的數(shù)據(jù)段即為與故障模型匹配成功，得到葉子節(jié)點(diǎn)的indexList鏈表，即為故障數(shù)據(jù)段位置鏈表，本條路徑匹配完畢。

3實(shí)驗(yàn)結(jié)果及分析

取航空公司CAB737-800型飛機(jī)的2008年8月份的25個(gè)航班記錄，每個(gè)航班記錄序列的長(zhǎng)度為6089～11949不等，數(shù)據(jù)分段段長(zhǎng)取100，數(shù)據(jù)符號(hào)化范圍為0到20。飛機(jī)故障通常情況下不是由單一因素引起，面與飛機(jī)故障有關(guān)的不同屬性在飛機(jī)發(fā)生故障過(guò)程中的重要程序也各不相同，根據(jù)專家經(jīng)驗(yàn)給出的空中顛簸故障屬性重要度調(diào)查表[7-8]，垂直加速度屬性是對(duì)空中顛簸故障發(fā)生的最重要影響屬性，因此主要針對(duì)該故障數(shù)據(jù)的垂直加速度屬性數(shù)據(jù)實(shí)驗(yàn)。

文獻(xiàn)[9-10]通過(guò)研究并驗(yàn)證k-d樹(shù)的特點(diǎn)和優(yōu)勢(shì)，對(duì)QAR數(shù)據(jù)進(jìn)行符號(hào)化并建立了多維時(shí)序飛行數(shù)據(jù)的子序列，并驗(yàn)證了k-d樹(shù)查找的速度相比于順序掃描的明顯優(yōu)勢(shì)，適用于大規(guī)模時(shí)序飛行序列中子序列的相似性搜索。其實(shí)驗(yàn)結(jié)果如表1所示。

表1清晰表明了k-d樹(shù)查找的速度遠(yuǎn)快于順序掃描的速度，適合大規(guī)模時(shí)序飛行序列中子序列的相似性搜索。但是在k-d查詢之前所需的建樹(shù)時(shí)間依然不容忽視，本文通過(guò)分段符號(hào)化并概率提取然后再建樹(shù)查詢，分段及離散化共用時(shí)間平均為310.1ms，建樹(shù)和查詢所用時(shí)間之和平均僅為2.5ms。綜合表1和表2，顯然分段后的查詢時(shí)間僅為不分段就順序查詢的一半，而采用樹(shù)形結(jié)構(gòu)查詢之后搜索時(shí)間再一次得到提升，從建樹(shù)到查詢結(jié)束的總時(shí)間低于k-d樹(shù)的僅查詢時(shí)間。

另外子序列查找過(guò)程中以查找到的類(lèi)似故障數(shù)據(jù)段為目標(biāo)輸出，并將類(lèi)似故障數(shù)據(jù)段輸出到到文件，當(dāng)檢測(cè)數(shù)據(jù)為模擬的非故障數(shù)據(jù)時(shí)，輸出文件無(wú)內(nèi)容，而當(dāng)檢測(cè)數(shù)據(jù)為模擬的故障數(shù)據(jù)時(shí)，輸出文件中會(huì)得到如圖2的結(jié)果，其中“文件0”是一個(gè)待檢測(cè)的故障數(shù)據(jù)文件，“異常數(shù)據(jù)段0”則是故障模型中的一個(gè)故障點(diǎn)代表，與其相似的數(shù)據(jù)段表示采集到該待檢測(cè)數(shù)據(jù)的航班有可能會(huì)發(fā)生與故障模型相同的故障。實(shí)驗(yàn)得到故障相似數(shù)據(jù)段之后可以根據(jù)其數(shù)據(jù)段號(hào)（比如圖2中“數(shù)據(jù)段42”的“42”）來(lái)定位故障發(fā)生的具體位置。由此可見(jiàn)本程序可以正確識(shí)別出并定位本類(lèi)型的故障數(shù)據(jù)段，具有相當(dāng)?shù)膮⒖純r(jià)值。

綜上可知本文所用方法對(duì)于大規(guī)模數(shù)據(jù)處理具有足夠的正確率和高效性。

4小結(jié)

本文主要介紹了針對(duì)突發(fā)故障點(diǎn)數(shù)據(jù)段的檢測(cè)和定位方法，在PAA表示方法的基礎(chǔ)上進(jìn)一步對(duì)QAR數(shù)據(jù)進(jìn)行分段細(xì)化，將故障點(diǎn)鎖定在更小的數(shù)據(jù)段內(nèi)，對(duì)于時(shí)序數(shù)據(jù)來(lái)說(shuō)，能夠定位到更貼近故障突發(fā)的時(shí)間段；通過(guò)基于樹(shù)的子序列查詢算法提高了搜索查詢的效率的同時(shí)保證了查詢的正確性，實(shí)驗(yàn)證明本文采用算法是有效可行的。

參考文獻(xiàn)

[1] 王天明.基于QAR數(shù)據(jù)的飛行安全模型研究[D]：[碩士學(xué)位論文].天津：中國(guó)民航大學(xué).航空自動(dòng)化系，2008.

[2] 閆偉. QAR飛行時(shí)序數(shù)據(jù)相似性搜索算法研究[D]. 天津： 中國(guó)民航大學(xué)， 2010： 21-25.

[3] 趙恒. 數(shù)據(jù)挖掘中聚類(lèi)若干問(wèn)題研究[D]. 西安： 西安電子科技大學(xué)， 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] 張國(guó)振. 多元時(shí)序飛行數(shù)據(jù)子序列的相似性搜索算法研究[D]：[碩士學(xué)位論文]. 天津：中國(guó)民航大學(xué). 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 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] 肖輝.時(shí)間序列的相似性查詢與異常檢測(cè)[D]：[博士學(xué)位論文].上海：復(fù)旦大學(xué).計(jì)算機(jī)與信息技術(shù)系，2005.

[10] 郝飛. 基于粗糙集的時(shí)序數(shù)據(jù)挖掘及其應(yīng)用[D]. 成都： 西華大學(xué)， 2008： 9-10.