基于聚類和擬合的QAR 數(shù)據(jù)離群點(diǎn)檢測(cè)算法

楊 慧，王麗婧

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

0 引 言

分析挖掘QAR （quick access recorder）數(shù)據(jù)［1，2］的主要目的在于找出其中包含的異常數(shù)據(jù)，從而發(fā)現(xiàn)一些有價(jià)值的存在于正常情況之外的其它情況。發(fā)達(dá)國(guó)家已經(jīng)開始通過QAR 數(shù)據(jù)分析進(jìn)行故障診斷，例如英國(guó)民航局的InsightFDM 系統(tǒng)根據(jù)對(duì)QAR 數(shù)據(jù)的處理來發(fā)現(xiàn)飛機(jī)維護(hù)計(jì)劃之外的其它問題［3］，美國(guó)開發(fā)的軟件I－Trend利用QAR數(shù)據(jù)提高飛機(jī)的飛行安全。國(guó)內(nèi)民航業(yè)對(duì)QAR 數(shù)據(jù)的利用還并不充分，目前主要應(yīng)用序列相似性分析法［4］、小波變換［5］以及關(guān)聯(lián)規(guī)則［6］等方法對(duì)數(shù)據(jù)進(jìn)行研究，但是這些方法并不能對(duì)QAR 中出現(xiàn)的異常數(shù)據(jù)進(jìn)行有效檢測(cè)。

由于QAR數(shù)據(jù)所包含的數(shù)據(jù)量大、處理困難，所對(duì)應(yīng)的離群點(diǎn)檢測(cè)算法應(yīng)該具有高計(jì)算效率和少量幾遍掃描存儲(chǔ)數(shù)據(jù)等特點(diǎn)。本文通過對(duì)QAR數(shù)據(jù)的分析，結(jié)合K均值聚類算法和最小二乘法提出了一種適用于QAR數(shù)據(jù)的離群點(diǎn)檢測(cè)算法，為QAR數(shù)據(jù)在故障檢測(cè)中的應(yīng)用提供了前期準(zhǔn)備。

1 相關(guān)工作

1.1 QAR 數(shù)據(jù)特點(diǎn)

QAR 數(shù)據(jù)是檢修人員進(jìn)行飛機(jī)維護(hù)，專家確定飛機(jī)故障的重要依據(jù)。其數(shù)據(jù)嚴(yán)格按照時(shí)間規(guī)律，采樣頻率為一秒一次。飛機(jī)發(fā)生故障時(shí)在QAR 數(shù)據(jù)上所表現(xiàn)出的主要是數(shù)值的波動(dòng)和變化情況，飛機(jī)故障關(guān)注局部的變化，同時(shí)對(duì)數(shù)值比較敏感［7］，且部分故障數(shù)據(jù)產(chǎn)生的時(shí)間是連續(xù)的。

QAR 數(shù)據(jù)記錄的屬性值數(shù)量巨大，但飛機(jī)的某一具體故障發(fā)生時(shí)，往往只與其中有限個(gè)數(shù)的屬性有緊密關(guān)系。針對(duì)飛機(jī)故障的主要屬性進(jìn)行處理能夠快速準(zhǔn)確的對(duì)故障數(shù)據(jù)的產(chǎn)生進(jìn)行定位，因此本文采用考慮主導(dǎo)因素的方法來提高算法檢測(cè)故障的準(zhǔn)確性。

1.2 離群點(diǎn)挖掘問題

從大量數(shù)據(jù)集中快速而且準(zhǔn)確地找出飛機(jī)行駛過程中的異常數(shù)據(jù)并進(jìn)行分析和判斷，反映了離群點(diǎn)檢測(cè)方法的時(shí)間效率和準(zhǔn)確度［8］。

飛機(jī)發(fā)生某些故障時(shí)所對(duì)應(yīng)的屬性值比較集中，離散化程度較低，因此一些檢測(cè)稀疏無規(guī)則離群點(diǎn)的算法［9］用于分辨QAR 離群數(shù)據(jù)效果并不理想。本文在基于距離的離群點(diǎn)定義的基礎(chǔ)上，提出了一種新的算法實(shí)現(xiàn)對(duì)QAR 數(shù)據(jù)的離群點(diǎn)檢測(cè)，相關(guān)定義請(qǐng)參見文獻(xiàn) ［10］。

2 算法KLS介紹

針對(duì)QAR 數(shù)據(jù)的特點(diǎn)，算法KLS滿足對(duì)QAR 數(shù)據(jù)離群點(diǎn)檢測(cè)的如下要求：首先，為了及時(shí)發(fā)現(xiàn)飛機(jī)在飛行過程中隱含的問題，算法對(duì)QAR 數(shù)據(jù)的分析時(shí)間較短；其次，由于QAR 數(shù)據(jù)量大，算法對(duì)數(shù)據(jù)庫的掃描只有一遍或者少量幾遍，減少了時(shí)間和空間的開銷。

2.1 算法相關(guān)原理

2.1.1 K 均值聚類

K－means聚類算法能夠?qū)⒋罅繑?shù)據(jù)分類聚合，有效處理大數(shù)據(jù)集，同時(shí)其迭代速度快，數(shù)據(jù)查找快速準(zhǔn)確，因此在流數(shù)據(jù)中也得到廣泛應(yīng)用。文獻(xiàn) ［11］在利用Kmeans算法對(duì)流數(shù)據(jù)進(jìn)行處理時(shí)采用了按時(shí)間順序分區(qū)聚類的思想。借鑒上述思想，算法KLS第一階段對(duì)QAR 數(shù)據(jù)按照時(shí)間順序進(jìn)行分割并聚類，生成對(duì)應(yīng)的K 均值點(diǎn)集。

QAR 異常數(shù)據(jù)發(fā)生時(shí)間較集中，同時(shí)發(fā)生故障時(shí)的數(shù)據(jù)關(guān)聯(lián)性強(qiáng)，因此聚類生成的QAR 故障數(shù)據(jù)簇比較緊密且遠(yuǎn)離正常簇。根據(jù)這一特點(diǎn)，算法第二階段忽略數(shù)據(jù)簇密度因素，利用生成簇的均值中心點(diǎn)來尋找離群數(shù)據(jù)。

2.1.2 最小二乘法

最小二乘法依靠樣本數(shù)據(jù)尋找最優(yōu)擬合，當(dāng)數(shù)據(jù)依賴關(guān)系強(qiáng)且按照某種規(guī)律變化時(shí)擬合效果較好。

飛機(jī)在穩(wěn)定飛行過程中，其各個(gè)參數(shù)都是按規(guī)律變化的，對(duì)QAR 數(shù)據(jù)聚類所得的均值點(diǎn)中包含大量的飛行正常數(shù)據(jù)均值參考點(diǎn)和少量的故障數(shù)據(jù)均值參考點(diǎn)，此時(shí)離群點(diǎn)對(duì)擬合效果的影響較小。算法KLS利用最小二乘法擬合參數(shù)曲線時(shí)，以實(shí)測(cè)值Yi與擬合值＾Yi的差Yi－＾Yi的平方和SQ 最小化來尋找最優(yōu)模型

2.2 關(guān)鍵定義

假設(shè)QAR 數(shù)據(jù)被劃分為數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊包含相同數(shù)目的數(shù)據(jù)點(diǎn)。按照數(shù)據(jù)流分區(qū)聚類算法對(duì)QAR 數(shù)據(jù)進(jìn)行處理并進(jìn)一步擬合尋找離群均值參考點(diǎn)的過程中，有相關(guān)定義如下：

定義1 對(duì)QAR 劃分成的數(shù)據(jù)塊分別進(jìn)行聚類，每個(gè)數(shù)據(jù)塊都生成k 個(gè)簇，每個(gè)簇的中心點(diǎn)為ct1，ct2，…，ctk，每個(gè)中心點(diǎn)的權(quán)重h1，h2，…，hk代表它所在的簇的數(shù)據(jù)個(gè)數(shù)，則每個(gè)數(shù)據(jù)塊將由k 個(gè)均值參考點(diǎn)rei（cti，hi）所代表。

定義2 設(shè)均值參考點(diǎn)集為RE，對(duì)于每一個(gè)均值參考點(diǎn)rei，其中的中心點(diǎn)cti＝ （x1i，…，xni）所對(duì)應(yīng)的離群因子pi定義為均值中心點(diǎn)到直線擬合點(diǎn)y＝ （y1i，…，yni）的偏差距離

定義2將離群因子表示為兩個(gè)值之間的歐氏距離，確保均值參考點(diǎn)距擬合線越遠(yuǎn)，所對(duì)應(yīng)的離群因子的值就越大，距離擬合線越近，其離群因子的值就越小。

定義3 設(shè)離群因子集為P，那么屬于離群因子集P的判定值A(chǔ)P 定義如下

定義4 設(shè)離群程度為δ，離群因子最小值為min（pi），那么

其中，ε為0到1之間的隨機(jī)數(shù)。

定義5 對(duì)于離群因子集中任意pi∈P，若pi＞δ＊AP，則pi所對(duì)應(yīng)的均值參考點(diǎn)rei為離群點(diǎn)，其所在簇中的數(shù)據(jù)即為離群數(shù)據(jù)。

從定義3可以看出，AP 值為所有離群因子總和的平均值，而定義4中離群程度δ值在離群點(diǎn)的判定中影響較大。由于符合離群點(diǎn)條件的均值參考點(diǎn)rei對(duì)應(yīng)的離群因子pi的值遠(yuǎn)大于正常的離群因子值，設(shè)定的δ在依照離群因子最小值min（pi）和平均值A(chǔ)P 計(jì)算出的理想離群程度的基礎(chǔ)上，加入隨機(jī)數(shù)ε成為最終的離群程度δ，以確保少數(shù)離群因子值pi略高于理想離群因子范圍的正常均值參考點(diǎn)與離群均值參考點(diǎn)的分離，保證了離群對(duì)象的獲取。

2.3 算法實(shí)現(xiàn)

采用KLS算法對(duì)QAR 數(shù)據(jù)進(jìn)行離群點(diǎn)檢測(cè)大致分為以下兩個(gè)階段：第一階段，將數(shù)據(jù)分區(qū)并進(jìn)行聚類，找出均值參考點(diǎn)集；第二階段，采用最小二乘法進(jìn)行擬合，根據(jù)設(shè)定范圍找出離群參考點(diǎn)，進(jìn)而得到離群數(shù)據(jù)。QAR 數(shù)據(jù)量大，但其中所包含的故障數(shù)據(jù)是少量的，對(duì)數(shù)據(jù)劃分之后利用K 均值聚類確保了聚類效果及速度，同時(shí)生成的均值參考點(diǎn)集中離群均值參考點(diǎn)個(gè)數(shù)也是極少量的，最小二乘法擬合幾乎不受離群點(diǎn)影響，保證了算法的可行性。

算法輸入：QAR 時(shí)序數(shù)據(jù)X，數(shù)據(jù)劃分長(zhǎng)度S

算法輸出：QAR 中的異常數(shù)據(jù)

具體步驟：

步驟1 將輸入的QAR 數(shù)據(jù)按照時(shí)間順序每S 個(gè)數(shù)據(jù)點(diǎn)為一個(gè)長(zhǎng)度區(qū)域進(jìn)行劃分，則當(dāng)前輸入數(shù)據(jù)可被劃分為X＝ ｛X1，X2，X3，…，XM｝；

步驟2 對(duì)每個(gè)數(shù)據(jù)區(qū)域Xi內(nèi)的數(shù)據(jù)按照k 均值聚類算法進(jìn)行聚類，當(dāng)中心點(diǎn)ctx（j）＝ctx＋1（j）（j＝1，2，…，k），即聚類中心不再改變時(shí)，輸出中心點(diǎn)值cti及其權(quán)重值hi，生成k個(gè)均值參考點(diǎn) ｛re1，re2，…，rek｝，寫入中心點(diǎn)集RE；

步驟3 重復(fù)步驟2，將每次生成的k個(gè)參考點(diǎn)按順序依次寫入RE，直至QAR 數(shù)據(jù)所有分區(qū)中的K 均值點(diǎn)全部產(chǎn)生；

步驟4 根據(jù)最小二乘法對(duì)步驟2中生成的均值參考點(diǎn)集RE 中各點(diǎn)的中心點(diǎn)值cti進(jìn)行擬合，計(jì)算出當(dāng)前飛機(jī)參數(shù)曲線模型；

步驟5 依據(jù)RE 中各點(diǎn)的中心點(diǎn)值cti＝ （x1i，…，xni），找出曲線模型中對(duì)應(yīng)的擬合值y＝ （y1i，…，yni），按照式 （2）計(jì)算RE 中各個(gè)均值參考點(diǎn)rei的離群因子pi，寫入離群因子集P；

步驟6 利用式 （3）計(jì)算離群因子集P 的判定值A(chǔ)P，同時(shí)找出離群因子集中的最小值min（pi），根據(jù)式 （4）計(jì)算出離群程度δ；

步驟7 在離群因子集P 中找到滿足pi＞δ＊AP 條件的離群因子，組成離群集OP；

步驟8 找出OP 中所有的離群因子pi所對(duì)應(yīng)的均值參考點(diǎn)rei，組成離群中心點(diǎn)集ORE，則其中的rei被視為離群點(diǎn)，其權(quán)重值hi的總和即視為離群數(shù)據(jù)的個(gè)數(shù)；

步驟9 掃描QAR 數(shù)據(jù)，找出ORE 中的rei所對(duì)應(yīng)簇中的數(shù)據(jù)，這些數(shù)據(jù)作為QAR 故障數(shù)據(jù)或者干擾數(shù)據(jù)輸出。

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

對(duì)文章所提出的KLS算法在飛機(jī)故障數(shù)據(jù)中的應(yīng)用進(jìn)行檢測(cè)，算法采用MATLAB 7.0 實(shí)現(xiàn)，實(shí)驗(yàn)平臺(tái)配置為Intel Core i5，2.5 GHz，4 GB 內(nèi) 存 的PC，操 作 系 統(tǒng) 為Windows 7，通過某B737－800 型飛機(jī)記錄的數(shù)據(jù)，對(duì)KLS算法用兩種不同的故障類型進(jìn)行實(shí)際檢測(cè)驗(yàn)證，實(shí)驗(yàn)數(shù)據(jù)相關(guān)信息見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)相關(guān)信息

實(shí)驗(yàn)一根據(jù)擾流板故障的特點(diǎn)，選用QAR 數(shù)據(jù)中的飛機(jī)高度和10號(hào)擾流板位置作為屬性。在飛機(jī)飛行過程中，將飛機(jī)高度作為判斷飛機(jī)飛行階段的條件。根據(jù)專家經(jīng)驗(yàn)，十號(hào)擾流板位置數(shù)值在－3 左右的時(shí)候視為正常。數(shù)據(jù)為飛機(jī)的一次飛行過程中記錄的9184條QAR 數(shù)據(jù)值，其中擾流板故障數(shù)據(jù)有194條，取S＝300，實(shí)驗(yàn)結(jié)果見表2。

表2 擾流板故障算法效果

為了考慮K 值的選取對(duì)算法效果的影響，本文選擇了4個(gè)不同的K 值分別進(jìn)行實(shí)驗(yàn)以檢測(cè)結(jié)果。從表2中可以看出，K 值較小時(shí)，對(duì)QAR 異常數(shù)據(jù)的檢測(cè)比較準(zhǔn)確，但同時(shí)對(duì)正常數(shù)據(jù)檢測(cè)的準(zhǔn)確率也相應(yīng)較低。因?yàn)樗惴▽?duì)數(shù)據(jù)比較敏感，受飛機(jī)高度的影響，當(dāng)K 值較小時(shí)，所得離群中心點(diǎn)中包含有飛機(jī)故障數(shù)據(jù)，但同時(shí)也會(huì)把正常數(shù)據(jù)誤劃為異常數(shù)據(jù)；當(dāng)K 值逐漸增大時(shí)，對(duì)故障數(shù)據(jù)準(zhǔn)確的檢測(cè)個(gè)數(shù)有所下降，但其中包含的正常數(shù)據(jù)相對(duì)減少，所以總體準(zhǔn)確率增加，但還是有部分?jǐn)?shù)據(jù)因?yàn)轱w機(jī)高度的起伏變化而出現(xiàn)判斷誤差。

實(shí)驗(yàn)二選取的是空中顛簸的故障。由專家經(jīng)驗(yàn)可得飛機(jī)在空中是否有空中顛簸的故障發(fā)生主要與飛機(jī)的垂直加速度的屬性值有關(guān)，垂直加速度 （ALV）在大于1.5或小于0.5的時(shí)候顛簸感較強(qiáng)烈。由于空中顛簸的狀況一般發(fā)生在飛機(jī)起飛之后，因此選取飛機(jī)的Air／Ground和垂直加速度為所用屬性，并對(duì)Air／Ground 非數(shù)值屬性進(jìn)行預(yù)處理。數(shù)據(jù)為某航班飛機(jī)巡航階段65521 條數(shù)據(jù)，其中含空中顛簸數(shù)據(jù)36條。取S＝500，實(shí)驗(yàn)結(jié)果見表3。

表3 空中顛簸算法效果

從表3可以看出，由于所選屬性相對(duì)擾流板故障屬性來說較為穩(wěn)定，K 值較小的時(shí)候，生成的聚類簇個(gè)數(shù)較少，因此部分正常數(shù)據(jù)被劃為了異常數(shù)據(jù)；但是隨著K 值的增加，算法聚類效果增強(qiáng)，正常數(shù)據(jù)逐漸被排除，同時(shí)故障數(shù)據(jù)沒有出現(xiàn)聚類偏差，因此離群點(diǎn)檢測(cè)的準(zhǔn)確率也隨之增加。當(dāng)K 值增加到一定程度之后，故障數(shù)據(jù)的聚類效果趨于穩(wěn)定而不再發(fā)生變化。

由以上兩個(gè)飛機(jī)故障的實(shí)驗(yàn)結(jié)果，得到算法在兩個(gè)實(shí)驗(yàn)中所用時(shí)間的對(duì)比如圖1所示。

圖1 算法運(yùn)行時(shí)間

由圖1可以看出，KLS算法在空中顛簸故障樣本中的執(zhí)行時(shí)間大于擾流板樣本數(shù)據(jù)中的執(zhí)行時(shí)間。分析可知由于空中顛簸故障樣本數(shù)據(jù)集遠(yuǎn)遠(yuǎn)大于擾流板樣本中的數(shù)據(jù)，同時(shí)空中顛簸故障樣本數(shù)據(jù)分區(qū)所取S 值較大，因此其時(shí)間也相應(yīng)增加。隨著K 值逐漸增加，離群點(diǎn)檢測(cè)耗費(fèi)的時(shí)間也隨之增加，因此在算法應(yīng)用時(shí)，應(yīng)該綜合考慮時(shí)間和準(zhǔn)確率等各方面的因素，選擇合適的K 值，從而得到需要的檢測(cè)結(jié)果。

4 結(jié)束語

本文針對(duì)QAR 數(shù)據(jù)參數(shù)穩(wěn)定，故障數(shù)據(jù)聚類效果好的特點(diǎn)，提出了一種適用于QAR 數(shù)據(jù)的算法。該算法前期基于聚類對(duì)QAR 數(shù)據(jù)進(jìn)行分區(qū)并利用K－means算法生成中間均值點(diǎn)，后期根據(jù)生成的聚類均值點(diǎn)進(jìn)行最小二乘法擬合直線，通過計(jì)算均值點(diǎn)到直線的離群因子找出最有可能的離群點(diǎn)。算法的時(shí)間和效率都得到了有效驗(yàn)證，同時(shí)算法也滿足了對(duì)QAR 數(shù)據(jù)少量掃描的特點(diǎn)，實(shí)驗(yàn)驗(yàn)證了該方法可行。

算法在應(yīng)用中還需根據(jù)實(shí)際情況進(jìn)一步改進(jìn)來提高性能。比如在數(shù)據(jù)選取方面，應(yīng)充分考慮如何有效地從QAR數(shù)據(jù)中選取各個(gè)故障具有代表性的精簡(jiǎn)屬性。并且在考慮主導(dǎo)因素的同時(shí)加入次要因素的影響，使算法在故障檢測(cè)中的應(yīng)用范圍更廣泛。

［1］CAO Lin.QAR principle analysis and application in aircraft maintenance［J］.Jiangsu Aviation，2011 （1）：36－37 （in Chinese）. ［曹琳.QAR 原理分析及在飛機(jī)維護(hù)中的應(yīng)用［J］.江蘇航空，2011 （1）：36－37.］

［2］GAO Yuan.Research on fault early warning of B777airplane based on data mining ［D］.Tianjin：Civil Aviation University of China，2008 （in Chinese）. ［高原.數(shù)據(jù)挖掘算法在B777飛機(jī)故障預(yù)警中的應(yīng)用研究 ［D］.天津：中國(guó)民航大學(xué)，2008.］

［3］Kiyak E，Caliskan F.Application of fuzzy logic in aircraft sensor fault diagnosis［J］.International Journal of Systems Applications，Engineering ＆ Development， 2012， 6 （4）：317－324.

［4］YAN Wei，ZHAO Yang，GAO Yuan.Study on similarity search of flight time series data ［J］.China Computer ＆ Network，2008，34 （21）：54－57 （in Chinese）. ［閆偉，趙楊，高原.飛行時(shí)序數(shù)據(jù)相似性挖掘算法研究 ［J］.計(jì)算機(jī)與網(wǎng)絡(luò)，2008，34 （21）：54－57.］

［5］FENG Xingjie，LI Sheng，XUN Xiuxia.Civil aviation QAR data reduction and it’s performance analysis based on wavelet scaling coefficients ［J］.Computer Engineering and Design，2009，30 （5）：1255－1258 （in Chinese）.［馮興杰，李勝，郇秀霞.基于小波尺度系數(shù)的民航QAR 數(shù)據(jù)約簡(jiǎn)及其性能分析［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （5）：1255－1258.］

［6］LIU Yang，CAO Huiling，LIANG Dajiao.The application of association rules mining in aeroengine QAR data［D］.Beijing：Publishing House of Electronics Industry，2009：233－237 （in Chinese）.［劉揚(yáng)，曹惠玲，梁大教.關(guān)聯(lián)規(guī)則挖掘在航空發(fā)動(dòng)機(jī)QAR 數(shù)據(jù)中的應(yīng)用 ［D］.北京：電子工業(yè)出版社，2009：233－237.］

［7］YANG Hui，ZHANG Guozhen.Similarity search for multidimensional QAR data subsequence ［J］.Computer Engineering and Applications，2013，49 （5）：136－139 （in Chinese）. ［楊慧，張國(guó)振.QAR 數(shù)據(jù)多維子序列的相似性搜索 ［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49 （5）：136－139.］

［8］XUE Anrong，JU Shiguang，HE Weihua，et al.Research of local outlier mining algorithms ［J］.Journal of Computers，2007，30 （8）：1455－1463 （in Chinese）. ［薛安榮，鞠時(shí)光，何偉華，等.局部離群點(diǎn)挖掘算法研究 ［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30 （8）：1455－1463.］

［9］SUN Meiyu.Research on discords detect on time series based on distance and density ［J］.Computer Engineering and Applications，2012，48 （20）：11－17 （in Chinese）.［孫梅玉.基于距離和密度的時(shí)間序列異常檢測(cè)方法研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48 （20）：11－17.］

［10］XUE Anrong，YAO Lin，JU Shiguang，et al.Survey of outlier mining ［J］.Computer Science，2008，35 （11）：13－18（in Chinese）.［薛安榮，姚林，鞠時(shí)光，等.離群點(diǎn)挖掘方法綜述 ［J］.計(jì)算機(jī)科學(xué)，2008，35 （11）：13－18.］

［11］ZENG Ying，LUO Ke，ZOU Ruizhi.Outliers detection method based on K－means and agglomerative clustering ［J］.Computer Engineering and Applications，2009，45 （29）：131－133 （in Chinese）. ［曾穎，羅可，鄒瑞芝.基于K－均值聚類和凝聚聚類的離群點(diǎn)查找方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （29）：131－133.］