飛機故障維修記錄關(guān)聯(lián)規(guī)則挖掘方法

朱興動,章思宇,王 正

(1.海軍航空大學(xué)， 山東 煙臺 264000； 2.海軍航空大學(xué) a.青島校區(qū)研究生隊； b.青島校區(qū)裝備保障信息化中心， 山東 青島 266000)

飛機的故障維修記錄是技術(shù)人員用于評估飛機的技術(shù)狀態(tài)，分析故障規(guī)律的重要數(shù)據(jù)來源。但是，實際的維修記錄大都以自然語言進行描述，一些常用的數(shù)學(xué)分析方法并不適用，而且在一些單位，技術(shù)人員針對這些數(shù)據(jù)也只僅僅進行一些簡單的統(tǒng)計分析，統(tǒng)計故障率、事故率等信息，并不能得到有用的結(jié)論。本研究針對這種現(xiàn)狀，對海軍航空兵某型現(xiàn)役飛機的故障維修記錄采用關(guān)聯(lián)規(guī)則分析的方法，采用兩種關(guān)聯(lián)規(guī)則分析算法并通過C#語言編程實現(xiàn)，比較兩種算法在挖掘故障關(guān)聯(lián)規(guī)則問題上的性能，找出飛機故障與其他因素之間存在的關(guān)系。

1 故障維修數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘問題描述

故障維修數(shù)據(jù)集的一部分如表1所示， 如果想要得知故障所在系統(tǒng)與發(fā)現(xiàn)時機，修后時間或其他要素之間的關(guān)系，顯然，僅僅從數(shù)據(jù)表面上來看是無法得到的，而關(guān)聯(lián)規(guī)則挖掘恰恰可以很好地解決這個問題。

表1 故障維修記錄數(shù)據(jù)(部分)

故障維修數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘問題可以用以下形式化語言描述：

設(shè)故障維修數(shù)據(jù)集為D，項集I={I1,I2,…,Im}是包含諸如發(fā)現(xiàn)時間、飛機修后工作時間等具體數(shù)據(jù)項的集合，T為每條故障維修記錄，且T?I。設(shè)A、B分別是I中的一個項集，當(dāng)且僅當(dāng)A?T時，記錄T中包含A，那么，故障關(guān)聯(lián)規(guī)則就可以由以下蘊含式表示[1]：

A?B[support=s%,confidence=c%]

(1)

其中：

support表示關(guān)聯(lián)規(guī)則的支持度，且：

support(A?B)=P(A∪B)

(2)

confidence表示關(guān)聯(lián)規(guī)則的置信度，且：

confidence(A?B)=P(A|B)

(3)

同時滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱為強規(guī)則。本研究希望通過關(guān)聯(lián)規(guī)則挖掘，發(fā)現(xiàn)故障維修記錄中，故障所在系統(tǒng)與其他要素之間存在的強關(guān)聯(lián)規(guī)則。

2 關(guān)聯(lián)規(guī)則挖掘算法研究

2.1 Apriori算法

Apriori算法針對布爾關(guān)聯(lián)規(guī)則挖掘頻繁項集，算法使用頻繁項集的先驗知識，采用逐層搜索的迭代搜索方法得到全部的頻繁項集，即由頻繁K-項集搜索得到頻繁(k+1)-項集[2]。算法首先找出頻繁1-項集合，記為L1，再由L1生成候選2-項集C2，再掃描一次數(shù)據(jù)集獲得頻繁2-項集L2，如此反復(fù)直至無法再找到頻繁k-項集。算法還利用了Apriori的性質(zhì)，即頻繁項集的任何非空子集必是頻繁的，非頻繁項集的超集必不是頻繁的，通過該性質(zhì)可以提前過濾掉候選項集中不可能頻繁的項集，以提高算法的效率。

使用Apriori性質(zhì)來提高算法效率主要分為兩步，連接步和剪枝步[3]。

1) 連接步

設(shè)l1和l2為Lk-1中的兩個項集，li中的第j項記為li[j]，將Lk-1的連接操作記為Lk-1?Lk-1，對于l1和l2，只有當(dāng)l1、l2中的前(k-2)項相同時，才可進行連接操作，連接產(chǎn)生的結(jié)果為項集l1[1]l2[2] …l1[k-1]l2[k-2]。

2) 剪枝步

若項集中所含項較多，那么，通過連接產(chǎn)生的候選項集Ck中項的數(shù)目可能較為龐大，直接對Ck進行數(shù)據(jù)庫掃描的開銷會變的十分巨大。利用Apriori性質(zhì)，在掃描前剔除不可能頻繁的項集壓縮Ck，從而減少掃描數(shù)據(jù)庫的開銷，提高算法的效率。

2.2 FP-Growth算法

FP-Growth算法以Apriori算法為基礎(chǔ)，先將各頻繁1-項集統(tǒng)計出來，再將各頻繁項集之間的關(guān)系以結(jié)構(gòu)樹形式儲存，F(xiàn)P樹是如下的一種樹結(jié)構(gòu)[4]：

1) 由3個部分組成：標記為空(NULL)的根節(jié)點，作為根節(jié)點的孩子的項目前綴子樹，頻繁項頭表。

2) 項目前綴子樹中的每一個節(jié)點由3個域組成：項目名，支持計數(shù)和節(jié)點鏈。其中，項目名表示節(jié)點代表哪個項目，支持度計數(shù)表示到目前節(jié)點為止路徑中的事務(wù)數(shù)，節(jié)點鏈指向該節(jié)點在FP-Tree中第一次出現(xiàn)時的位置和之后再次出現(xiàn)該項目的位置。

3) 頻繁項頭表中各項包含3個域：項目名，支持度計數(shù)和節(jié)點鏈頭指針。

FP-Growth只通過兩次遍歷數(shù)據(jù)集就可以找出所有的頻繁項，第一次用于建立頻繁項頭表，第二次則用于建立FP(Frequent Pattern)樹，從而減少查找頻繁項集的開銷[5]，算法的具體步驟如下所述：

1) 以表1中的數(shù)據(jù)為例，首先，將表1中的數(shù)據(jù)轉(zhuǎn)化為事務(wù)記錄，如表2所示。

表2 事務(wù)記錄

設(shè)最小支持度閾值為0.3，對數(shù)據(jù)集進行第一遍掃描，過濾不滿足最小支持度的項，并按照每個項的支持度大小降序排列，結(jié)果如表3和表4所示。

表3 第一次數(shù)據(jù)集掃描結(jié)果

2) 第二次掃描過濾之后的數(shù)據(jù)集，開始逐步構(gòu)建FP樹。如果某個項是第一次出現(xiàn)，那么就創(chuàng)建該節(jié)點，并在項頭表中添加一個指向該節(jié)點的指針，否則按路徑找到該項對應(yīng)的節(jié)點，修改節(jié)點信息[6]，圖1和圖2分別展示了FP樹建立過程的第一步和建立完成的情況。

3) 對于每個項，找到其條件模式基，遞歸調(diào)用樹結(jié)構(gòu)，刪除支持度未達閾值的項。若最終呈現(xiàn)單一路徑的樹結(jié)構(gòu)，則直接列舉所有組合，若非單一路徑的則循環(huán)繼續(xù)調(diào)用樹結(jié)構(gòu)，直到形成單一路徑。最后從形成的單一路徑中，通過排列組合的方式找到達到支持度閾值要求的關(guān)聯(lián)規(guī)則。

表4 過濾掉非頻繁項后的數(shù)據(jù)集

圖1 包含事務(wù)編號001的FP樹

圖2 完整的FP樹

2.3 算法實現(xiàn)

本文在充分研究兩種算法的基礎(chǔ)上，采用C#語言編程實現(xiàn)Apriori與FP-Growth算法的關(guān)聯(lián)規(guī)則挖掘程序，兩種算法實現(xiàn)的偽代碼為：

1) Apriori算法[7]

Input：數(shù)據(jù)集D，最小支持度min_sup，最小置信度min_conf

Output：數(shù)據(jù)集D中的頻繁項集Frequent_L

方法：

L1={Frequent 1-itemsets};//得到頻繁1-項集

for(k=2;Lk-1≠?;k++)do

{

Ck=apriori_gen(Lk-1);//新的候選集

for each transaction t ∈D do

{

Ct=subset(Ck,t);//事務(wù)t中包含的候選集

for each candidate c ∈ Ctdo

c.count++;

}

Lk={c ∈ Ck|c.count>=min_sup}

}

AsRules=judgeconfidence(Lk,min_conf);//在候選集中剔除不滿足最小置信度的項集

return AsRules

2) FP-Growth 算法[8]

Input：數(shù)據(jù)集D，最小支持數(shù) min_supnum

Output：頻繁項集L

方法：

foreach transaction t ∈ D

{

foreach item x ∈ t

if (c ∈ C1&&x=c) c.count++;//從候選1-項集C1中找出與x同名的候選項c，使c的支持度計數(shù)加1,

}

if (c.count>=min_supnum) F.Add;//選取C1中支持度計數(shù)大于最小支持度計數(shù)的項，得到頻繁1-項集F

L=Bubble(F);//使用冒泡排序法將F按支持度計數(shù)降序排列得到L

create root=NULL;//創(chuàng)建樹根，開始建立FP樹

foreach transaction t ∈ D

{

FP_Tree=InsertTree([p|P,root]);//選取t中的頻繁項目，并按L順序排序，記為[p]P]，p為第一個元素，P為余下元素列表

}

Frequent_L=FP_growth(FP_Tree,min_supnum);//通過調(diào)用FP_growth方法來獲取全部頻繁項集

2.4 Apriori算法與FP-Growth算法的比較

FP-Growth算法解決了Apriori算法在尋找頻繁項集的過程中，需要反復(fù)掃描數(shù)據(jù)集的問題和反復(fù)產(chǎn)生候選項集的問題，大大提高了算法挖掘關(guān)聯(lián)規(guī)則的效率[9]。但是，F(xiàn)P-Growth算法將大量的開銷用于FP樹的建立上，Apriori算法獲得候選項集的過程僅僅是通過簡單的排列組合，而后再使用Apriori性質(zhì)來減少候選項集的數(shù)量，再通過掃描數(shù)據(jù)集獲得頻繁項集，而FP-Growth算法則需要反復(fù)構(gòu)建FP樹來獲取頻繁項集，如果數(shù)據(jù)集的項較多，對于算法的效率將會有較大的影響。

而本研究中所使用的故障維修記錄數(shù)據(jù)，數(shù)據(jù)量較大，而且包含的項目較多，經(jīng)過前期統(tǒng)計，項目數(shù)量已經(jīng)超過100項，隨著新的記錄的加入，項目的數(shù)目還會進一步增加，這就意味著，通過FP-Growth算法建立的FP樹的寬度會比較大，由于該算法需要反復(fù)對FP樹進行重建與掃描，F(xiàn)P樹的寬度過大可能會對其算法運行速度造成較大影響。對于故障維修記錄數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘而言，到底這兩種算法哪種更適合，效率更高，則需要通過實驗來判明。

3 關(guān)聯(lián)規(guī)則挖掘算法研究

本文通過.NET環(huán)境實現(xiàn)了Apriori與FP-Growth兩種算法，并通過一系列實驗來判明哪種算法更加適合故障維修數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘問題。實驗平臺計算機CPU為i5-3470，主頻為3.20GHz，內(nèi)存為4GB，操作系統(tǒng)為Windows XP。

3.1 算法的比較與選擇

首先，關(guān)聯(lián)規(guī)則挖掘的根本，算法在數(shù)據(jù)集中找到的頻繁項集必須是完整的，沒有缺漏的，為此，實驗中先使用這兩種算法對如表5中的經(jīng)典購物籃數(shù)據(jù)進行挖掘，設(shè)定最小支持度為0.3，挖掘得到的頻繁項集如表6所示。

表5 購物籃數(shù)據(jù)

表6 購物籃數(shù)據(jù)挖掘測試結(jié)果

通過測試發(fā)現(xiàn)，算法所得的結(jié)果與手工分析所得的結(jié)果完全一致，且再增加購物籃數(shù)據(jù)的數(shù)據(jù)量，兩種算法的結(jié)果也一致，這就說明了這兩種算法均能夠完整地找出數(shù)據(jù)集中的所有滿足最小置信度的頻繁項集，選擇哪一種算法需要進一步比較其運算效率。

為了對比這兩種算法在挖掘故障記錄關(guān)聯(lián)規(guī)則上的效率，實驗中又設(shè)計了兩種情況對算法進行測試[10]。

實驗一

固定記錄條數(shù)為5 000條，考查不同最小支持度閾值min_sup情況下，兩種算法執(zhí)行時間。圖3所示為實驗一結(jié)果，表7所示為兩種算法完成分析所耗費的具體時間。

圖3 實驗一結(jié)果示意圖

從表7和圖3中可以很明顯看到：在相同的數(shù)據(jù)規(guī)模下和不同最小支持度閾值條件下，F(xiàn)P-Growth算法的運行時間都比Apriori算法要短，而且，隨著最小支持度閾值越低，兩種算法之間的差距越大。

實驗二

固定最小支持度閾值為0.02，考查兩種算法在不同數(shù)據(jù)量情況下的運行時間，圖4與表8所示為實驗的結(jié)果。

從表8和圖4中可以看出，Apriori算法的分析時間會隨著記錄條數(shù)的增加而不斷增大，而FP-Growth算法的運算時間隨記錄條數(shù)的增加變化不大，這是由于FP-Growth算法在建立FP樹之后，無需再對數(shù)據(jù)集掃描，之后進行的頻繁項集的尋找只需要不斷遞歸掃描條件FP樹即可，運算時間僅與FP樹的規(guī)模有關(guān)，也即與通過第一次數(shù)據(jù)集掃描得到的1-頻繁項集的數(shù)目有關(guān)。

圖4 實驗二結(jié)果示意圖

表8 實驗二算法運行時間結(jié)果 ms

通過實驗一和實驗二以及購物籃數(shù)據(jù)的測試，可以明顯發(fā)現(xiàn)兩種算法均能完整地找出全部的頻繁項集，而在同樣的數(shù)據(jù)條件下，F(xiàn)P-Growth算法的效率明顯要比Apriori算法高，且差距較大，因此，在之后的關(guān)聯(lián)規(guī)則挖掘過程中將使用FP-Growth算法進行。

3.2 關(guān)聯(lián)規(guī)則挖掘分析

設(shè)定最小支持度為0.005，最小置信度為0.4，通過FP-Growth算法挖掘得到符合上述條件的關(guān)聯(lián)規(guī)則總計963條，其中與故障所在系統(tǒng)相關(guān)的規(guī)則共計62條，由于篇幅有限，僅列出十條置信度最高的關(guān)聯(lián)規(guī)則，如表9所示。

表9 故障維修記錄數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘

對上述挖掘得到的關(guān)聯(lián)規(guī)則進行整理，刪除本身并不具備意義的關(guān)聯(lián)規(guī)則后，得到相關(guān)結(jié)論如下：

1) 隨機性故障：位于座艙，后機身等部位，主要故障屬于指示/記錄系統(tǒng)，液壓系統(tǒng)等。這些故障產(chǎn)生的原因主要是因為在飛機的使用過程中，突發(fā)性的零部件故障或零件到達使用壽命，一般的判明方法是在機械日或定期檢查時使用儀器檢查。為盡量減少這樣的故障對于飛機的影響，應(yīng)在飛行完成之后，仔細檢查飛行參數(shù)，以便及時發(fā)現(xiàn)這類故障。

2) 周期性故障：位于機翼和起落架等部位，主要故障屬于燃油系統(tǒng)和起落裝置系統(tǒng)，當(dāng)飛機修后工作時次達600～900 h，為故障多發(fā)期，因此，當(dāng)飛機修后工作時次達到600 h以上時，應(yīng)著重對于上述部位及系統(tǒng)做細致檢查，及時更換部件。

4 結(jié)論

主要研究了某型飛機故障關(guān)聯(lián)規(guī)則挖掘的方法，將關(guān)聯(lián)規(guī)則挖掘這一思想應(yīng)用到了故障維修記錄分析當(dāng)中。通過兩種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，Apriori算法與FP-Growth算法在該問題上分析效率的比較，采用實際數(shù)據(jù)測試的方法，最終使用FP-Growth算法進行挖掘。通過關(guān)聯(lián)規(guī)則挖掘，可以發(fā)現(xiàn)在數(shù)據(jù)之中存在著一些有趣的，對于維修保障有一定指導(dǎo)意義的關(guān)聯(lián)規(guī)則。但是，由于數(shù)據(jù)的完整性和準確性還存在一定問題，導(dǎo)致關(guān)聯(lián)規(guī)則挖掘所得有限，在之后的研究過程中還需加入諸如使用情況，天氣，季節(jié)等影響要素進行綜合考慮，以得出更加有意義的結(jié)論。此外，算法的分析過程中，還存在著一些無用的開銷，仍需進一步提高算法的效率，以應(yīng)對更龐大的數(shù)據(jù)。