飛機故障維修記錄關聯規則挖掘方法

朱興動,章思宇,王 正

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

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

1 故障維修數據關聯規則挖掘問題描述

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

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

故障維修數據關聯規則挖掘問題可以用以下形式化語言描述：

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

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

(1)

其中：

support表示關聯規則的支持度，且：

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

(2)

confidence表示關聯規則的置信度，且：

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

(3)

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

2 關聯規則挖掘算法研究

2.1 Apriori算法

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

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

1) 連接步

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

2) 剪枝步

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

2.2 FP-Growth算法

FP-Growth算法以Apriori算法為基礎，先將各頻繁1-項集統計出來，再將各頻繁項集之間的關系以結構樹形式儲存，FP樹是如下的一種樹結構[4]：

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

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

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

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

1) 以表1中的數據為例，首先，將表1中的數據轉化為事務記錄，如表2所示。

表2 事務記錄

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

表3 第一次數據集掃描結果

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

3) 對于每個項，找到其條件模式基，遞歸調用樹結構，刪除支持度未達閾值的項。若最終呈現單一路徑的樹結構，則直接列舉所有組合，若非單一路徑的則循環繼續調用樹結構，直到形成單一路徑。最后從形成的單一路徑中，通過排列組合的方式找到達到支持度閾值要求的關聯規則。

表4 過濾掉非頻繁項后的數據集

圖1 包含事務編號001的FP樹

圖2 完整的FP樹

2.3 算法實現

本文在充分研究兩種算法的基礎上，采用C#語言編程實現Apriori與FP-Growth算法的關聯規則挖掘程序，兩種算法實現的偽代碼為：

1) Apriori算法[7]

Input：數據集D，最小支持度min_sup，最小置信度min_conf

Output：數據集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);//事務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：數據集D，最小支持數 min_supnum

Output：頻繁項集L

方法：

foreach transaction t ∈ D

{

foreach item x ∈ t

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

}

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

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

create root=NULL;//創建樹根，開始建立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);//通過調用FP_growth方法來獲取全部頻繁項集

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

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

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

3 關聯規則挖掘算法研究

本文通過.NET環境實現了Apriori與FP-Growth兩種算法，并通過一系列實驗來判明哪種算法更加適合故障維修數據關聯規則挖掘問題。實驗平臺計算機CPU為i5-3470，主頻為3.20GHz，內存為4GB，操作系統為Windows XP。

3.1 算法的比較與選擇

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

表5 購物籃數據

表6 購物籃數據挖掘測試結果

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

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

實驗一

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

圖3 實驗一結果示意圖

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

實驗二

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

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

圖4 實驗二結果示意圖

表8 實驗二算法運行時間結果 ms

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

3.2 關聯規則挖掘分析

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

表9 故障維修記錄數據關聯規則挖掘

對上述挖掘得到的關聯規則進行整理，刪除本身并不具備意義的關聯規則后，得到相關結論如下：

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

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

4 結論

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