朱興動,章思宇,王 正

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

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

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

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

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

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

設(shè)故障維修數(shù)據(jù)集為D，項(xiàng)集I={I1,I2,…,Im}是包含諸如發(fā)現(xiàn)時間、飛機(jī)修后工作時間等具體數(shù)據(jù)項(xiàng)的集合，T為每條故障維修記錄，且T?I。設(shè)A、B分別是I中的一個項(xiàng)集，當(dāng)且僅當(dāng)A?T時，記錄T中包含A，那么，故障關(guān)聯(lián)規(guī)則就可以由以下蘊(yùn)含式表示[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ī)則稱為強(qiáng)規(guī)則。本研究希望通過關(guān)聯(lián)規(guī)則挖掘，發(fā)現(xiàn)故障維修記錄中，故障所在系統(tǒng)與其他要素之間存在的強(qiáng)關(guān)聯(lián)規(guī)則。

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

2.1 Apriori算法

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

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

1) 連接步

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

2) 剪枝步

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

2.2 FP-Growth算法

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

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

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

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

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

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

表2 事務(wù)記錄

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

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

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

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

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

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

圖2 完整的FP樹

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

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

1) Apriori算法[7]

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

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

方法：

L1={Frequent 1-itemsets};//得到頻繁1-項(xiàng)集

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);//在候選集中剔除不滿足最小置信度的項(xiàng)集

return AsRules

2) FP-Growth 算法[8]

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

Output：頻繁項(xiàng)集L

方法：

foreach transaction t ∈ D

{

foreach item x ∈ t

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

}

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

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

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

foreach transaction t ∈ D

{

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

}

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

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

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

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

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

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

3.1 算法的比較與選擇

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

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

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

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

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

實(shí)驗(yàn)一

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

圖3 實(shí)驗(yàn)一結(jié)果示意圖

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

實(shí)驗(yàn)二

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

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

圖4 實(shí)驗(yàn)二結(jié)果示意圖

表8 實(shí)驗(yàn)二算法運(yùn)行時間結(jié)果 ms

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

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

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

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

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

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

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

4 結(jié)論

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