王艳辉， 王淑君， 李 曼， 林 帅

(1. 北京交通大学 轨道交通控制与安全国家重点实验室，北京 100044； 2. 北京交通大学 交通运输学院，北京 100044；3. 北京交通大学 北京市城市交通信息智能感知与服务工程技术研究中心，北京 100044)

动车组是由自动化控制设备、列车设备以及线路等众多单元构成的复杂机电设备集成系统，系统中的不同设备之间及同1设备的不同部分之间相互关联、紧密耦合，单1故障往往会引起“牵一发而动全身”的“水波效应”，造成由微小故障涌现成严重故障的后果。

为此，本文基于CRHX型动车组牵引系统的故障数据，课题组前期利用改进N-Gram算法[1]提取故障信息特征词，在此研究成果的基础上，挖掘故障数据中蕴含的关联规则，研究设备间的关联失效关系。

对于关联规则挖掘算法的研究始于Agrawal等人于1993年首次提出Apriori算法[2]，传统的关联规则挖掘算法大多数是以Apriori算法为基础。该算法需要多次扫描数据库并生成大量候选集，效率较低。针对Apriori算法的缺陷，Han J[3]等人提出一种基于频繁模式树(FP-tree)进行频繁项集挖掘的FP-Growth算法，该算法只需扫描数据库两次且不需要产生候选集，显著缩小了搜索空间，相对于Apriori算法的效率有1个数量级的改善[4]。但是该算法需要递归地生成大量的条件FP-树，耗费大量的存储空间和时间。为此研究者提出了许多基于该算法的改进算法：基于hash表的FP-tree频繁模式挖掘算法[5]，频繁项集并行挖掘算法[6]，基于MapReduce的FP-Growth算法[7]，MS-FP-Growth算法[8]，信息导向的FP-Growth算法[9]，基于项目约束的改进FP-Growth算法[10]等。上述算法从不同方面对FP-Growth算法进行了改进，但每次生成新的FP树时依然需要2次遍历条件模式基，导致系统需要反复申请本地以及数据库服务器的资源查询相同内容的海量数据，一方面使算法的执行效率大大降低，另一方面给数据库服务器带来负担。

基于上述算法存在的问题，同时结合动车组故障信息特征词的特点，本文在经典FP-Growth算法的基础上加入关系表得到改进的FP-Growth算法，避免了第1次遍历条件模式基，提高了算法的效率。利用改进的FP-Growth算法针对设备故障信息特征词挖掘频繁项集，进一步得到设备关联失效规则，构建设备关联失效模型并以CRHX型动车组牵引系统为例进行分析，验证了该算法的可行性、实用性和高效性。

1 动车组故障信息特征词的特点分析

本文依据CRHX型动车组牵引系统自2011年1月至2012年4月的故障数据进行研究，共计6 000余条，部分故障数据见表1。对以上数据进行初步分析后发现存在以下问题。

表1 CRHX型动车组牵引系统部分故障数据表

(1) 故障数据量较大

动车组系统包含两万多个零部件，每个零部件都有可能存在多种故障情况；另外，每条故障数据又包含故障时间、故障描述、所属列车编号等73个属性字段，由此可见故障数据量的巨大。

(2) 故障数据的不一致性

目前故障数据主要是由人工记录，大部分为描述性语言，不同的人对同一故障现象的命名不同，描述的详细程度也不同，例如：对于部件的异常排风，有的故障描述中用的是“漏风”一词，有的是“排风”，有的是“打风”。因此故障数据的格式缺乏统一的标准。

(3) 故障数据的不完整性

虽然经过人员的审核，故障数据中仍出现空缺值或由于人工记录造成部分数据错误的情况。例如：“故障所属设备”这一列数据中空缺值达到20%；某条故障数据中，危害等级为灾难，而运营模式为正常，故障类别为碎修(未晚点)，数据明显错误。

(4) 故障数据属性字段的冗余性

并非所有的故障数据都可以用来进行分析。比如部分数据为空白数据，部分数据为冗余数据对于本研究没有意义。例如整列空白的字段包括：维修材料费用、修复后系统测试时间、修复后系统调试时间等，冗余字段包括：故障录入人、故障录入时间、审核人、审核时间等。

这些故障数据往往由于不便量化、不够精确或由于应用技术的限制而无法被直接利用，无法充分有效地挖掘其中隐含的相关信息，因此前期课题组提出改进的N-Gram算法[1]，利用此算法从故障数据中提取故障信息特征词，经初步分析得出，故障信息特征词具有以下特点：

(1) 故障信息特征词是从故障数据中提取的概念标识，保留了原始故障数据的基本特征，仍可反映系统故障的基本情况。

(2) 相较于原始故障数据，故障信息特征词更加简洁、直观、明了，便于关联规则挖掘算法的应用。

(3) 故障信息特征词中蕴含着设备的关联失效关系。

(4) 故障信息特征词提取的方式是否得当、提取的特征是否有效，直接影响到设备关联失效规则挖掘的准确性。

基于动车组的故障数据及故障信息特征词的以上特点，本文提出改进的FP-Growth算法挖掘设备的关联失效规则，研究设备间的关联失效关系。改进算法适用于此类以文字记录为主的文本型数据库的关联规则挖掘。

2 改进的FP-Growth算法

2.1 FP-Growth算法基本理论

FP-Growth算法是经典的关联规则挖掘算法之一，该算法不产生候选模式，采用频繁模式增长算法对频繁项集进行压缩，得到频繁模式FP树(Frequent Pattern Tree)[3]。FP树是一种特殊的前缀树，分为频繁项目头表和频繁项前缀子树，用树的分支标识项目名称，用树的节点存储后缀项。用路径表示项集，存储在1棵子树中的项目具有相同前缀的项集。算法的主要思路为：把事务数据库中所有的频繁项集压缩到1棵FP树上，保留各个项集之间的关联关系；之后把这种压缩后的数据库分成条件数据库(特殊类型的映射数据库)，每条关联规则就是1个频繁项目，分别挖掘各个条件数据库，并且创建1个项目头表，每个项都要通过1个节点指向它在树上的出现位置。所以项目事务数据库中包含的所有信息都压缩在FP树中，对事务数据库的挖掘变成对FP树的挖掘。FP树结构对数据起到良好的压缩作用，只需扫描事务名称和项目集合2次数据库，即可将数据库中频繁项目信息全部压缩存储在FP树上，其后对频繁项集支持度的计算只需在FP树上进行，不需要扫描整个数据库。

2.2 FP-Growth算法的改进思路

2.1节的经典FP-Growth算法忽略了新支持度计数列表与原有支持度计数列表间的关系，因此需要2次遍历条件模式基，不仅降低了算法效率而且给数据库服务器造成负担。在经典FP-Growth算法的基础上加入关系表，通过使用二维向量记录频繁度，省略了每次构造新的条件FP树时对条件模式基的第1次遍历，仅需遍历1次条件模式基，大大缩短建立FP树的时间，算法效率明显提高。具体改进思路为

(1) 遍历事务集合S，得到各个项目的频繁度后，剔除频繁度低于支持度的项目，剩余项目按照支持度降序排列，生成频繁项目集合L，得到项目表和FP树。同时创建任意两项关系表，词关系表为1个二维表，记录事务数据库中任何两项目同时出现的支持度计数。

(2) 关系表中记录了事务数据库中所有同时出现的任意2项的频繁度F。删除两项目同时出现的频繁度小于给定最小支持度的组合项目，得到新的关系表，称此表为关系简表。

(3) 根据关系简表，创建不同后缀项目集β条件下的FP子树。如当β={x}时，抽取关系简表中与x相关的行、列值，将对应行值和列值相加，可得到条件β下，x与其他项的支持度计数，构建出当前条件下的FP子树，进而得到不同后缀项目集β条件下的所有频繁项目集。

2.3 改进FP-Growth算法的实现

改进的FP-Growth算法在对FP树遍历搜索频繁项集时，利用关系简表有效地提高了算法的效率。改进前后的FP-Growth算法，在FP树的构造过程中是相同的，都是1次遍历每个事务得到FP树，同时统计每个事务的频繁度，并降级排列，得到与FP树对应的项目头表。改进算法的实现流程为

Step1建立项目关系表。统计项目事务数据库S中任意两项同时出现的频繁度，建立项目关系表，项目关系表中记录了所有的两两项目同时出现的频繁度，这里称组合项的频繁度。例如事务{A,B,C,D},则得到的所有二维向量关系为A,B、(A,C)、A,D、B,C、B,D、C,D，其中B,C≠C,B。

Step2建立项目关系简表。由于对于组合频繁度小于最小支持度的两项目关系并不关心，因此需要把这些项目关系从表中删除，得到新的项目关系表，将此表称为关系简表，见图1。

Step3考虑项目头表中项目频繁度最小的项目。项目A出现在表格的最后为项目频繁度最小的项，此时令后缀项目集β={A},获取关系简表中第1行和第1列中关于A的所有项目的支持度信息，可以得到{(A,B):1+0;(A,C):2+0;(A,D)：1+0；A,E:1+0};相关项目的支持度集合记为L_A,因此L_A={B:1+0;C:2+0;D:1+0;E:1+0}；剔除支持度小于2的项目，可得条件项目基为{(C:2)}，得到对应的频繁项目集合为{{C,A}:2}。

Step4当后缀项目集β={E}时，在关系简表中获取与E相关的第5列的所有项目的支持度信息，具体结果为{(E,A):0+1;(E,B):0+3;(E,C):0+2;(E+D):0+0}；相关项目的支持度集合L_E={A:0+1,B:0+3,C:0+2}；剔除支持度小于2的项目，可得条件项目基为{(B:2),C:2}，得到对应的频繁项目集合为{{B,E}:2,{C,E}:2}。

同上述步骤，当β={C}时，相关项目的支持度集合L_C={A:0+2,B:0+2,D:1+0,E:2+0}，条件项目基{B:2,E:2}，得到对应的频繁项目集合为{{B,C}:2,{E,C}:2}，整个算法的具体实现流程见图2。

2.4 算法分析与讨论

为证明本文中改进FP-Growth算法的准确性与高效性，将其与两类经典算法(改进Apriori算法与FP-Growth算法)进行了性能方面的对比与分析。测试环境为Intel Core 2，主频2 GHz，内存2 GB，操作系统为Windows7，使用Java编程。其中改进Apriori算法代码中采用了许多优化措施，其性能已大大优于最初的Apriori算法，是公认的Apriori算法的最佳实现。由于所采用的3种算法在同一数据集和相同支持度下得到的频繁项集完全相同，因此很好地证明了改进FP-Growth算法的准确性。

本实验中采用的测试数据集为T10I4D100K和Retail，均属于稀疏型数据集，其中T10I4D100K共有10 0000条记录，包含870个项目，项目的支持度分布较均匀，最大项目支持度计数为7 828，而Retail是更稀疏数据集，共有88 162条记录，包含8 708个项目，项目的支持度跨度较大，最大项目支持度计数为50 675。实验分别对这2个数据集从2个方面进行算法运行时间的比较，一个方面是测试使用关系简表后对算法运行时间的影响，在对两个数据集都选择支持度为0.1的条件下，每次加载不同的事务数量进行测试，实验结果见图3；另一个方面是测试至多扫描一次事务数据库对算法运行时间的影响，对2个数据集都加载全部事务，每次选择不同的支持度，实验结果见图4。图4中给出的运行时间是从读取数据开始，一直到得出所有频繁项集的时间，但不包括输出结果的时间。

表2 针对T10I4D100K数据集不同支持度下的算法占用内存比

支持度/%FP⁃Growth算法/改进FP⁃Growth算法改进Apriori算法/改进FP⁃Growth算法81．211．361．212．842．914．223．819．315．227．5

表3 针对Retail数据集不同支持度下的算法占用内存比

图3(a)、3(b)分别给出了针对两个数据集在不同事务数量下的算法运行时间比较情况。性能大致为：改进FP-Growth大于改进Apriori大于FP-Growth，且事务数量越多效率越高，主要原因是当事务数量增大时只需更新关系简表，此后的挖掘可以脱离原数据库进行，极大地缩小了开销。对于T10I4D100K数据集，改进FP-Growth的效率比FP-Growth快3～5倍，比改进Apriori快2～4倍；对于Retail数据集，改进FP-Growth的效率比FP-Growth快4～8倍，比改进Apriori快2～4倍。图4(a)、4(b)分别给出了在针对两个数据集在不同支持度下的算法运行时间比较情况。性能大致为：改进FP-Growth>改进Apriori大于FP-Growth，且随着支持度的增加，算法的效率也更高，当支持度增加到一定程度后，算法运行时间趋向1个稳定值。主要原因是绝大部分时间消耗在1次扫描事务数据库上，而这部分时间不会发生变化。对于T10I4D100K数据集，改进FP-Growth的效率比FP-Growth快2～3倍，比改进Apriori快1倍以上；对于Retail数据集，改进FP-Growth的效率比FP-Growth快10%～40%，比改进Apriori快10%～30%。从测试结果可以看出，采用加入关系简表改进措施后，改进FP-Growth算法的性能对于2个数据集都是效率最高的，其次为改进Apriori算法、FP-Growth算法。其中，采用优化措施后的Apriori算法，对于非稠密数据具有较高的效率，其性能优于FP-Growth算法。

此外可将算法所占用内存的比值对比其性能。结果见表2、表3，占用内存的比值分别为FP-Growth算法和改进Apriori算法与改进FP-Growth算法的比值。可见改进FP-Growth算法占用内存效率最低。其中，改进Apriori算法经优化后虽然运行速度较快，但是由于算法需要生成候选项集，因此占用内存仍然较高。而FP-Growth算法和改进FP-Growth算法不需产生候选项集，因此占用内存要明显小于改进Apriori算法。此外，由于改进FP-Growth算法大大降低了扫描数据库的次数，而且当支持度变化时无需再次访问数据库，因此内存占用也明显小于FP-Growth算法。

因此，改进的FP-Growth算法在挖掘频繁项集时优势明显，具有较好的性能。实验结果证明了改进FP-Growth算法的准确性与高效性。

3 基于改进FP-Growth算法的关联失效模型研究

3.1 关联失效规则挖掘

基于改进的FP-Growth算法挖掘设备的关联失效规则，在前节中已经利用改进的FP-Growth算法得到了事务数据库S中项目所有的频繁项集，具体结果见表4。根据得到的频繁项集，生成关联失效规则，见表5，具体步骤[11]为

Step1对于任何一个频繁项集l，产生l的所有非空子集；

Step2对于l的每个非空子集s，如果满足置信度Confidence(s⟹l-s)≥minConf，则说明s与l-s之间存在关联失效关系，则说明s⟹l-s为强关联规则，即项l-s发生失效引起项s失效。

表4 事务数据库S对应的频繁项集

表5 关联失效规则表

3.2 关联失效模型构建

利用改进的FP-Growth算法对设备故障信息特征词的事务数据库进行分析，得到设备失效的频繁项目集，挖掘出各个项目之间的关联失效规则，进而建立关联失效模型，具体步骤为

Step1建立事务数据库。由设备故障信息特征词构成的事务集合得到事务数据库；

Step2建立频繁项目集库。根据改进的FP-Growth算法，得到事务数据库中的频繁i-项集(i=1,2,…,n)，进而建立频繁项集库；

Step3挖掘项目的关联失效规则。根据得到的频繁项集找出影响项目和被影响项目，生成项目之间的关联失效规则。关联失效规则的前项和后项存在关联失效关系，前项为被影响项，后项为影响项，后项发生失效会引起前项失效；

Step4建立关联失效模型。由每个项目的关联失效规则，得到所有项目的关联失效规则，建立关联失效模型，见图5。

4 CRHX型动车组牵引系统的关联失效模型研究

4.1 CRHX型动车组牵引系统故障数据处理

利用改进的FP-Growth算法对CRHX型动车组的牵引系统进行实例分析。CRHX型动车组采用动力分散交流传动方式，最高运营速度为250 km/h。整个车体采用8辆编组形式，4动2拖，分为2个动力单元，每个动力单元包括两个动车和2辆拖车(T-M-M-T)[12]。CRHX型动车组牵引系统由两个基本动力单元组成，每个基本动力单元主要由1台牵引变压器、2台牵引变流器、8台三相交流异步牵引电机构成。

基于2011年至2012年期间CRHX型动车组牵引系统的故障数据进行分析，每条故障数据包含故障编号、列车编号、故障模式、故障日期、初步处理措施、初步原因、危害等级、运营模式、运行公里数、故障所属系统、所属子系统、所属部件等属性。提取到的CRHX型动车组牵引系统故障信息特征词如下：电压互感器、自动过分相装置、受电弓、高压隔离开关、主断路器、避雷器、四象限整流器、辅助逆变器、牵引电机、牵引逆变器等设备。选取6 000多条故障数据，构建2 000多个事务，得到包含2 000多个项目集合的事务数据库，事务数据库的部分结果见表6。

为使关联分析简单化，需要对事务数据库中的设备进行字母编码，编码规则见表7。将牵引系统设备的事务数据库按照编码规则进行设备编码，得到新的事务数据库，部分编码后的事务数据库见表8。

表6 事务数据库的部分结果

表7 设备编码定义表

表8 部分编码后的事务数据库

4.2 CRHX型动车组牵引系统关联失效模型构建

基于改进的FP-Growth算法对设备的编码事务数据库进行关联失效分析，具体分析步骤为

Step1构建频繁模式树FP-tree

(1) 扫描编码事务数据库，统计各个项目的支持度，生成长度为l的频繁项目候选集q及其支持度。对候选集q，按照支持度降序排列，本文设定最小支持度为20，将支持度小于20的项目删除，生成频繁项目集合L，具体生成结果见表9。

表9 各个项目频繁度汇总表

(2) 创建FP树根节点，标记为“null”，按照FP树的创建过程，得到牵引系统的FP树，见图6。

Step2遍历FP树挖掘频繁项集

按照改进的FP-Growth算法构建频繁项集，基于Java编程语言对该算法进行实现。经过程序的运行，遍历根据牵引系统事务数据库构造的FP树，同时结合根据支持度构建的二维简表，得到项目的各个频繁项集。

Step3构建关联失效模型

根据各个频繁项目集合可以找到各个项目的关联项目，找到被影响项目和影响项目，得到设备之间的关联失效规则，见表10。

表10 牵引系统设备的关联失效规则表

根据关联失效规则中前项与后项的关系便可建立设备的关联失效模型，结果见图7。该模型很好地描述了动车组设备的关联失效过程及机理。以关联失效模型为研究基础，进一步展开对设备间关联失效特性、关联失效传播的机制及相关防控策略的研究，可以使设备故障得到早诊断、早预防、早处理，防止设备故障的进一步扩大。因此本文提出的关联失效模型构建方法具有一定的理论依据和指导意义，并为其他领域的关联失效研究提供了参考。

4.3 算法分析与讨论(CRHX型动车组牵引系统为例)

采用与前节相同的3种算法代码进行性能测试。实验采用的测试数据集为CRHX型动车组牵引系统的设备故障信息特征词，具有6 850条记录，包含2 730个事务，与T10I4D100K、Retail数据集同属于稀疏型数据集。测试环境为Intel Core 2，主频2 GHz，内存2 GB，操作系统为Windows7，使用Java编程。

图8给出了在上述数据集不同支持度下的算法运行时间比较情况。在不同支持度下改进FP-Growth算法的运行效率都明显优于FP-Growth算法和改进Apriori算法，大致为改进FP-Growth算法大于改进Apriori算法，改进Apriori算法大于FP-Growth算法，改进FP-Growth算法的效率比FP-Growth算法快2～3倍，比改进Apriori算法快1～2倍。而且随着支持度阈值的减小，改进FP-Growth算法的增长趋势也较平缓，当支持度阈值较小时，改进FP-Growth算法的优势更能凸显。因此，改进FP-Growth算法优势明显，具有较好的性能。

5 结论

本文依据前期课题组对故障数据的研究成果，在故障信息特征词的基础上展开对动车组的设备间关联失效关系的研究。在深入了解关联分析的理论知识和经典案例的基础上提出关联规则挖掘算法，即改进的FP-Growth算法。经典FP-Growth算法中需要2次扫描数据库建立FP树，针对此问题对算法进行改进，提出了使用关系表的方法，从而省去经典算法对条件模式基的第1次遍历，至多扫描数据库1次。而且当支持度计数和数据变化时，只需要更新关系表，此后的挖掘可以脱离原数据库进行，极大地缩小了开销。以两类经典数据集对改进算法进行了性能测试，表明该算法是1个高效准确的关联规则挖掘算法。

基于改进的FP-Growth算法对故障信息的特征词进行关联分析，挖掘设备关联失效规则并构建设备关联失效模型，为动车组故障传播、故障诊断及维修方面的研究提供了理论依据。并以CRHX型动车组牵引系统进行了实例分析，验证了本方法的有效性，由于故障数据有限，后续需要从大样本角度对该方法的实用性进行进一步的应用和检验。然而对于具有关联失效关系的设备，其发生的故障相互影响，甚至循环作用，使得故障诊断变得非常复杂，以关联失效模型为载体探求系统故障诊断方法成为进一步研究的重点问题。另外，一般的关联规则挖掘方法多数是大众化、通用型的，很少有专门为分析和挖掘动车组的故障数据而设计的。为此必须根据动车组的特点进行改进和创新现有方法，并进行合理组合，从而提高关联失效规则挖掘的高效性和准确性。

参考文献：

[1] 李曼. 基于机器学习的故障识别方法与系统研制[D].北京：北京交通大学, 2015.

[2] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining Association Rules Between Sets of Items in Large Databases[J]. ACM Sigmod Record, 1993, 22(2): 207-216.

[3] HAN Mining. Frequent Patterns without Candidate Generation[C]//Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data.New York:ACM, 2000:1-12．

[4] SINGH A K, KUMAR A, MAURYA A K. An Empirical Analysis and Comparison of Apriori and FP-growth Algorithm for Frequent Pattern Mining[C]// Proceedings of the IEEE 2014 International Conference on Advanced Communication Control and Computing Technologies(ICACCCT). New York: IEEE, 2014:1 599-1 602.

[5] 李也白, 唐辉, 张淳, 等. 基于改进的FP-tree的频繁模式挖掘算法[J].计算机应用, 2011,31(1): 101-105.

LI Yebai,TANG Hui,ZHANG Chun,et al. Frequent Pattern Mining Algorithm Based on Improved FP-tree [J].Application Research of Computers, 2011,31(1): 101-105.

[6] 李力, 翟东海, 靳蕃. 一种频繁项集并行挖掘算法[J].铁道学报, 2003,25(6):71-75.

LI Li,ZHAI Haidong, JIN Fan. A Parallel Algorithm for Frequent Itemsets Mining[J]. Journal of the China Railway Society, 2003, 25(6):71-75.

[7] CHEN X S, ZHANG S, TONG H, et al. FP-growth Algorithm Based on the Boolean Matrix and Mapreduce[J].Journal of South China University of Technology,2014:42(1)：135-141.

[8] TAKTAK W, SLIMANI Y. MS-FP-Growth: A Multi-support Vrsion of FP-Growth Agorithm[J]. International Journal of Hybrid Information Technology, 2014, 7(3):147-157.

[9] NEERBEK J. Message-driven FP-growth[C]//Proceedings of the ACM 2012 International Conference on WICSA/ECSA Companion Volume. New York:ACM, 2012: 29-36.

[10] 赵孝敏, 何松华, 李贤鹏, 等. 一种改进的 FP-Growth 算法及其在业务关联中的应用[J]. 计算机应用, 2008,28(9):2 341-2 344.

ZHAO Xiaomin,HE Songhua, LI Xianpeng,et al. Improved FP-Growth Algorithm and Its Application in the Business Association [J].Application Research of Computers, 2008, 28(9):2 341-2 344.

[11] 沈斌. 关联规则技术研究[M].杭州:浙江大学出版社,2011:3-12.

[12] 王华胜, 王忆岩, 谢川川, 等. CRH2型动车组可靠性建模与分配[J].铁道学报, 2009,31(5):108-112.

WANG Huasheng,WANG Yiyan, XIE Chuanchuan, et al. Reliability Modeling and Assigning for CRH2 Electric Multiple Unit [J]. Journal of the China Railway Society, 2009,31(5):108-112.