基于改进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.