基于改進(jìn)FP-Growth算法的無人機(jī)飛行故障診斷

鄭偉 李強(qiáng) 張永飛

摘 ?要：為了探究無人機(jī)飛行數(shù)據(jù)中征兆與故障的內(nèi)在聯(lián)系，提出了一種改進(jìn)FP-Growth算法。該算法首先在數(shù)據(jù)挖掘中設(shè)計了符合無人機(jī)飛行故障特點的約束條件，作為對FP-Growth算法的改進(jìn)重點，然后對飛行數(shù)據(jù)特征庫進(jìn)行篩選并建立FP-tree，進(jìn)而挖掘出有效的關(guān)聯(lián)規(guī)則，最后生成規(guī)則庫，為無人機(jī)飛行故障的定位提供依據(jù)。應(yīng)用實驗表明，提出的改進(jìn)FP-Growth算法能夠快速、準(zhǔn)確地為無人機(jī)飛行故障做出診斷，并且規(guī)則庫具有良好的規(guī)模增長性。

關(guān)鍵詞：數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;FP-Growth;無人機(jī);故障診斷

中圖分類號：TP182 ? ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? ? ? 文章編號：2095-2945（2019）13-0016-04

Abstract： In order to explore the internal relationship between symptoms and faults in UAV flight data， an improved FP-Growth algorithm is proposed. In this algorithm， the constraints in accordance with the flight fault characteristics of UAV are designed in data mining， which is the focus of the improvement of FP-Growth algorithm. Then， the flight data feature database is screened， FP-tree is established， and valid association rules are mined. Finally， the rule base is generated， which provides the basis for the location of UAV flight faults. The application experiments show that the improved FP-Growth algorithm can diagnose the flight fault of UAV quickly and accurately， and the rule base proves to have growth in scale.

Keywords： data mining; association rules; FP-Growth; UAV; fault diagnosis

引言

隨著無人機(jī)技術(shù)的不斷發(fā)展和廣泛應(yīng)用，無人機(jī)的系統(tǒng)構(gòu)成及控制算法越來越復(fù)雜，使得無人機(jī)出現(xiàn)故障的概率升高，故障的定位以及征兆與故障之間的關(guān)聯(lián)變得越來越難以查找。雖然無人機(jī)在測試及使用過程中會產(chǎn)生海量的飛行數(shù)據(jù)，但是數(shù)據(jù)之間不能形成可識別的故障信息，無法為無人機(jī)的故障診斷提供有效幫助。因此，如何利用飛行數(shù)據(jù)發(fā)現(xiàn)無人機(jī)征兆與故障之間的聯(lián)系，進(jìn)而診斷出無人機(jī)故障，已成為一個亟待解決的問題。

基于無人機(jī)飛行數(shù)據(jù)的故障診斷已受到了廣泛的關(guān)注，文獻(xiàn)[1]中提出了基于專家系統(tǒng)的無人機(jī)故障診斷。文獻(xiàn)[2]中利用專家系統(tǒng)與人工智能的融合算法，診斷無人機(jī)故障。文獻(xiàn)[3]基于BP神經(jīng)網(wǎng)絡(luò)，建立了無人機(jī)故障診斷專家系統(tǒng)。上述方法雖然實現(xiàn)了對無人機(jī)故障的定位，但僅是找到了征兆與故障間一一對應(yīng)的關(guān)系，并沒有挖掘出征兆與故障間的深層聯(lián)系。

隨著對大數(shù)據(jù)研究的不斷深入，越來越多的數(shù)據(jù)挖掘技術(shù)被應(yīng)用到各種領(lǐng)域的故障診斷中。數(shù)據(jù)挖掘技術(shù)可以找到數(shù)據(jù)之間的深層聯(lián)系，進(jìn)而預(yù)測未來的發(fā)展趨勢，更好的做出決策[4]。為了減少冗余規(guī)則，使挖掘出的規(guī)則真實有效，眾多學(xué)者提出了諸多基于約束的關(guān)聯(lián)規(guī)則挖掘算法。文獻(xiàn)[5]中提出了基于數(shù)據(jù)垂直分布的關(guān)聯(lián)規(guī)則挖掘算法;文獻(xiàn)[6]中提出了基于FP-tree的約束關(guān)聯(lián)規(guī)則挖掘算法;文獻(xiàn)[7]中提出了基于時態(tài)約束的關(guān)聯(lián)規(guī)則挖掘算法。上述方法是通過篩選用戶興趣度的方法來降低運(yùn)算量，但并未考慮規(guī)則中先導(dǎo)和后繼的約束條件。而在無人機(jī)的故障診斷中，正是要考慮先導(dǎo)和后繼的約束條件，即征兆與故障的約束條件。為此，本文提出了一種改進(jìn)FP-Growth算法，通過添加征兆與故障的約束，找到無人機(jī)征兆與故障之間的關(guān)聯(lián)規(guī)則，從而快速定位故障，完成故障診斷。

1 總體思路

FP-Growth算法旨在發(fā)現(xiàn)項之間的關(guān)聯(lián)規(guī)則，而不會去區(qū)分所發(fā)現(xiàn)規(guī)則是否有意義。挖掘無人機(jī)飛行數(shù)據(jù)是為了尋找征兆與故障之間的關(guān)聯(lián)規(guī)則，若發(fā)現(xiàn)的規(guī)則只包含征兆或只包含故障，則違背了問題提出的初衷。因此，在使用FP-Growth算法時，如果能根據(jù)挖掘?qū)ο笤O(shè)計出合理的約束條件，將大大提高數(shù)據(jù)挖掘的效率和效果，約束條件的設(shè)定也是本文對FP-Growth算法改進(jìn)的主要內(nèi)容。

本文設(shè)定的約束條件為：在形如X→Y的關(guān)聯(lián)規(guī)則中，征兆必須出現(xiàn)在先導(dǎo)的位置（即X），故障必須出現(xiàn)在后繼的位置（即Y）。不符合這一約束的規(guī)則認(rèn)為無效。無人機(jī)飛行故障診斷的數(shù)據(jù)挖掘主要包括以下3個環(huán)節(jié)：

第一，收集飛行數(shù)據(jù)，建立飛行數(shù)據(jù)特征庫并設(shè)定約束條件。

第二，在標(biāo)準(zhǔn)FP-Growth算法的基礎(chǔ)上，添加約束條件，按照選取的最小支持度與最小置信度挖掘關(guān)聯(lián)規(guī)則，形成故障診斷規(guī)則庫。

第三，將出現(xiàn)異常的飛行數(shù)據(jù)與規(guī)則庫中的規(guī)則進(jìn)行匹配，得到故障診斷結(jié)果。

2 基本定義及飛行數(shù)據(jù)篩選

2.1 基本定義

3 改進(jìn)FP-Growth算法及算法示例

3.1 改進(jìn)FP-Growth算法

本文根據(jù)無人機(jī)飛行數(shù)據(jù)特點，提出的改進(jìn)FP-Growth算法，包括5個步驟，其流程如圖1所示。

3.2 算法示例

為更好地理解改進(jìn)FP-Growth算法，現(xiàn)以包含10條數(shù)據(jù)的飛行數(shù)據(jù)特征庫D為例進(jìn)行說明：如表1所示，設(shè)征兆項集為S={i1，i2}，故障項集為F={i3，i5}，minsup=0.15，TID為每條數(shù)據(jù)的編號，每條數(shù)據(jù)為若干項組成的項集。

步驟1：構(gòu)建F-list表。輸入飛行數(shù)據(jù)特征庫，進(jìn)行第一次掃描，得到頻繁1-項集和它們的支持度，并按降序排列構(gòu)建F-list表，如表2所示。表F-list包含以下4個域：item、sup-count、label和link。每一項按照sup-count由大到小排序，label用s或f區(qū)分該項屬于征兆項集還是故障項集，屬于征兆項集用s表，屬于故障項集用f表示，link指向該項的首位置（項頭），方便后續(xù)算法的遞歸調(diào)用。

步驟2：縮減數(shù)據(jù)規(guī)模。分三種情況進(jìn)行篩：一是刪除一次掃描結(jié)果中支持度小于minsup的項;二是根據(jù)依據(jù)1，刪除沒有標(biāo)記為s或f的項;三是根據(jù)依據(jù)2，刪除只標(biāo)記有s或f的數(shù)據(jù)。刪除后生成新的F-list表，刪除情況如圖2所示。

步驟3：建立FP-tree。對飛行數(shù)據(jù)特征庫進(jìn)行第二次掃描，把每一條篩選后數(shù)據(jù)的項按降序依次插入到一棵以null為根節(jié)點的樹中，同時在每個節(jié)點處，記錄該節(jié)點出現(xiàn)的支持度，直至整棵樹建立完成。最后以F-list作為項頭表，指向其在FP-tree中的位置。最終建立的FP-tree如圖3所示。

步驟4：挖掘FP-tree。在已建立FP-tree的基礎(chǔ)上，使用遞歸算法挖掘出所有的征兆-故障頻繁項集LSF和征兆頻繁項集LS。當(dāng)挖掘標(biāo)記為s項的分枝時，可生成同時標(biāo)記有s和f的頻繁項集，歸為LSF，也可生成只標(biāo)記有s的頻繁項集，歸為LS。當(dāng)挖掘標(biāo)記為f項的分枝時，先序遍歷整個分枝，將所有節(jié)點歸入征兆項集S和故障項集F，故障項集只保留包含本項的項集并與征兆項集兩兩結(jié)合，歸為LSF。

4 實驗討論

4.1 應(yīng)用實驗

為驗證提出的改進(jìn)FP-Growth算法在無人機(jī)飛行故障數(shù)據(jù)挖掘中的有效性，以近兩年某無人機(jī)公司在無人機(jī)研發(fā)測試過程中積累的飛行數(shù)據(jù)特征庫為基礎(chǔ)，進(jìn)行實驗分析。本算例選取了其中1000條故障數(shù)據(jù)，用上文描述的算法進(jìn)行驗證與分析。

選定最小支持度為15%，最小置信度為80%。用改進(jìn)FP-Growth算法生成的規(guī)則庫，如表3所示。

在后續(xù)的測試過程中，當(dāng)無人機(jī)出現(xiàn)異常數(shù)據(jù)時，可將征兆輸入規(guī)則庫進(jìn)行匹配，得到相應(yīng)的診斷結(jié)果，定位故障所在位置，為無人機(jī)的研發(fā)及維護(hù)提供幫助。

4.2 對比討論

為了進(jìn)一步驗證本文所提改進(jìn)FP-Growth算法的優(yōu)越性，將本文算法與經(jīng)典Apriori算法、經(jīng)典FP-Growth算法進(jìn)行對比，在相同飛行數(shù)據(jù)特征庫以及相同最小支持度和最小置信度的條件下，運(yùn)行時間對比如圖4所示，生成關(guān)聯(lián)規(guī)則數(shù)對比如圖5所示。

由圖4可以看出，在運(yùn)行相同數(shù)據(jù)集的情況下，本文算法快于FP-Growth算法，兩者又均快于Apriori算法，且隨著數(shù)據(jù)集增大，說明本文算法所花費(fèi)時間僅略有上升，基本呈線性增長。

由圖5可以看出，由于Apriori算法和FP-Growth 算法沒有加入約束條件，在相同數(shù)據(jù)集的情況下，生成的關(guān)聯(lián)規(guī)則數(shù)明顯多于本文算法。而多出的關(guān)聯(lián)規(guī)則也不符合無人機(jī)故障診斷的要求，為冗余規(guī)則。

5 結(jié)論

為了探究無人機(jī)飛行故障中征兆與故障的深層聯(lián)系，本文提出了一種改進(jìn)FP-Growth算法，對規(guī)則的范圍及方式做了進(jìn)一步的約束，從而生成了具有實用價值的關(guān)聯(lián)規(guī)則，也提高了算法運(yùn)行的效率。但隨著飛行測試的繼續(xù)進(jìn)行，飛行數(shù)據(jù)特征庫進(jìn)一步增大時，如何實時對規(guī)則庫進(jìn)行擴(kuò)充，則是今后研究的一個重點。

參考文獻(xiàn)：

[1]Y Park， B Kim， S Chun. New knowledge extraction technique using probability for case-based reasoning： application to medical diagnosis [J]. Expert Systems， 2010，23（1）：2-20.

[2]Davis L， Gamble R F， Kimsen S. A patterned approach for linking knowledge-based systems to external resources[J]. IEEE Trans Syst Man Cybern B Cybern， 2004，34（1）：222-233.

[3]馬巖，曹金成，黃勇，等.基于BP神經(jīng)網(wǎng)絡(luò)的無人機(jī)故障診斷專家系統(tǒng)研究[J].長春理工大學(xué)學(xué)報（自然科學(xué)版），2011，34（04）：137-139.

[4]孟魁杰，董瑩，趙宗濤.一種基于數(shù)據(jù)挖掘的無人飛行器故障分析方法[J].計算機(jī)技術(shù)與發(fā)展，2010，20（06）：225-227+232.

[5]李海磊，王晗，孔令富，等.一種基于數(shù)據(jù)兩方垂直分布的多維關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)應(yīng)用與軟件，2014，31（01）：18-21+80.

[6]陳義明，李舟軍，傅自綱.基于FP-Tree的約束關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)工程與設(shè)計，2007，28（18）：4450-4453.

[7]張令杰，徐維祥.基于時態(tài)約束的關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)工程，2012，38（5）：50-52.

[8]王潘，劉魁.大數(shù)據(jù)技術(shù)在航空發(fā)動機(jī)中的應(yīng)用[J].航空動力，2018（01）：48-51.

[9]趙佳璐，楊俊，韓晶，等.基于事務(wù)ID集合的帶約束的關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)工程與設(shè)計，2013，34（05）：1663-1667.

[10]孟月昊，王朝霞，郭宇棟.基于規(guī)則前后部約束的關(guān)聯(lián)規(guī)則挖掘算法[J].后勤工程學(xué)院學(xué)報，2017，33（01）：79-84.