基于改進FP-Growth算法的無人機飛行故障診斷

鄭偉 李強 張永飛

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

關鍵詞：數據挖掘;關聯規則;FP-Growth;無人機;故障診斷

中圖分類號：TP182 ? ? ? ?文獻標志碼：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

引言

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

基于無人機飛行數據的故障診斷已受到了廣泛的關注，文獻[1]中提出了基于專家系統的無人機故障診斷。文獻[2]中利用專家系統與人工智能的融合算法，診斷無人機故障。文獻[3]基于BP神經網絡，建立了無人機故障診斷專家系統。上述方法雖然實現了對無人機故障的定位，但僅是找到了征兆與故障間一一對應的關系，并沒有挖掘出征兆與故障間的深層聯系。

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

1 總體思路

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

本文設定的約束條件為：在形如X→Y的關聯規則中，征兆必須出現在先導的位置（即X），故障必須出現在后繼的位置（即Y）。不符合這一約束的規則認為無效。無人機飛行故障診斷的數據挖掘主要包括以下3個環節：

第一，收集飛行數據，建立飛行數據特征庫并設定約束條件。

第二，在標準FP-Growth算法的基礎上，添加約束條件，按照選取的最小支持度與最小置信度挖掘關聯規則，形成故障診斷規則庫。

第三，將出現異常的飛行數據與規則庫中的規則進行匹配，得到故障診斷結果。

2 基本定義及飛行數據篩選

2.1 基本定義

3 改進FP-Growth算法及算法示例

3.1 改進FP-Growth算法

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

3.2 算法示例

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

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

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

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

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

4 實驗討論

4.1 應用實驗

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

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

在后續的測試過程中，當無人機出現異常數據時，可將征兆輸入規則庫進行匹配，得到相應的診斷結果，定位故障所在位置，為無人機的研發及維護提供幫助。

4.2 對比討論

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

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

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

5 結論

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

參考文獻：

[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].長春理工大學學報（自然科學版），2011，34（04）：137-139.

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

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

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

[7]張令杰，徐維祥.基于時態約束的關聯規則挖掘算法[J].計算機工程，2012，38（5）：50-52.

[8]王潘，劉魁.大數據技術在航空發動機中的應用[J].航空動力，2018（01）：48-51.

[9]趙佳璐，楊俊，韓晶，等.基于事務ID集合的帶約束的關聯規則挖掘算法[J].計算機工程與設計，2013，34（05）：1663-1667.

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