基于改进Apriori算法的地铁故障关联规则挖掘

刘文雅，徐永能

(南京理工大学， 南京 210094)

1 引言

近年来，国内城市地铁行业已迎来建设高峰期，运营线路逐年递增，投入运营总里程不断刷新记录。截止2020年底，南京地铁已开通运营1、2、3、4、10、S1、S3、S7、S8、S9共10条线路，总线路长度达394.3 km，日均客运量达到218万人次[1]。随着网络化线路的逐步形成，系统设备故障明显增多。对故障数据进行有效地处理分析从而找到故障之间的关联性，将关联性结果量化处理，为后续故障影响程度分析、风险等级划分、故障诊断、故障预警等研究奠定基础，具有重要意义。

关联规则挖掘[2]是大数据分析的重要课题，在数据分析领域得到广泛应用，很多国内外学者对关联规则挖掘算法[3-7]展开了深入研究，FP-Growth算法[8-9]和Apriori算法[10-12]是进行关联规则挖掘最常用的2种算法。FP-Growth算法是在Apriori算法的基础上，将Apriori算法遍历得到的频繁项按树结构进行统计得到频繁项集树FP-tree。该算法只能处理布尔类数据，输出得到的是频繁项集，而不是关联结果。本文从综合考虑地铁故障数据冗余以及规则难以挖掘的问题出发，以提高算法处理效率、深入挖掘故障间关联规则为优化目标，对Apriori算法的思想和流程进行优化，提出了一种考虑地铁故障关联规则的改进Apriori算法。将改进的算法与经典的FP-Growth算法仿真对比，验证其有效性。计算得到的故障数据的关联规则结果，为地铁故障影响分析、故障诊断、故障预测、故障预警提供重要参考依据。

2 关联规则问题描述及基本理论

2.1 关联规则挖掘

关联规则挖掘是进行大数据分析最常用的研究方法之一，它的目的在于从庞大数据集中找出各项之间的关联，而这种关联不会在数据中表现出来，需要进行关联分析，分析多个变量之间的联系。关联分析多被分为3类：简单关联、时序关联、因果关联[13]。其2个重要参数是最小支持度、最小可信度，参数取值会直接影响最后得到的关联结果。因此，为了使挖掘结果更具研究价值，相关学者多引入其他关联分析参数对关联规则挖掘算法进行改进[14-15]。

1) 关联规则(Association Rules)。

把形如X⟹Y这样的表达式简称为关联规则，符号⟹称为关联，X称为⟹的先决条件，Y则称为⟹的结果。其中X⊆I，Y⊆I，X≠∅、Y≠∅且X∩Y=∅，非空集合为某些项目组成。

2) 支持度(Support)。

支持集合X在事务数据库D中出现的频率，即为支持度。假设d={Q，S}为一事务，如果存在X⊆S，则称为事务d支持X，即事务数据库D支持集合X，称为支持度，记作S(X)。支持度是用来衡量关联规则重要性的关键量，支持度越高关联规则越重要。

Sup(X⟹Y)=S(X∪Y)为关联规则X⟹Y的支持度，表示X∪Y在数据库D中出现的频率。Sup(X⟹Y)记作S(X⟹Y)。

3) 频繁项(Frequent ItemSets)。

当S(X)≥MinSup，则称X为频繁项。其中，X⊆I且X≠∅X，MinSup为支持度阀值，也是最小支持度。如果构成X的项目数为K，则X称为K-维频繁项。若X为频繁项，S(X)为其支持度，有X′⊆X且X′≠∅，X′其支持度为S(X′)，当S(X′)≥S(X)，则X′为频繁项。

4) 置信度(Confidence)。

Conf(X⟹Y)=S(X∪Y)/S(X)为关联规则X⟹Y的置信度。关联规则X⟹Y的置信度在[0,1]之间取值，0≤Conf(X⟹Y)≤1。置信度是用来衡量关联规则可靠性的关键参数，置信度的高低代表关联规则可信程度的高低。

关联规则挖掘基本模型如图1所示。

图1 关联规则挖掘基本模型Fig.1 Basic model of association rule mining

2.2 Apriori算法

2.2.1Apriori算法描述

Apriori算法目的是找出事务数据集中的最大的频繁项集，其基本思想是预先设定最小置信度阈值，然后找到最大频繁项集与预先设定的最小置信度阈值之间的关联规则。需要对数据库不断扫描，第一次扫描得到1-频繁项集合l1，第k-1次得到频繁项集Lk-1，产生k-候选项集合Ck，确定Ck中每事务项的支持度，然后计算找出k-频繁项集合Lk，直到Ck=∅时停止。

为提高算法运行的效率，事务数据库中找到的最大频繁项集所有的非空子集都是频繁的，假如存在项集不是频繁的，且P(i)

2.2.2Apriori算法流程

第1步：连接。

找到k-频繁项集合Lk。首先预先设定最小支持度阈值，删除1项候选集C1中小于最小支持度阈值的项，得到1-频繁项集L1，L1自连接产生2项频繁项集L2，L2与L3连接产生候选集C3，删除2项候选集C2中小于最小支持度阈值的项，得到3项频繁项集L3,以此类推，最终得到最大频繁项集Lk。

第2步：剪枝。

剪枝在连接完成后进行，即删除选项Ck中不满足判别条件的项。Ck是Lk-1与L1连接产生的，由于使用Apriori算法在事务数据库中找到的最大频繁项集所有的非空子集都是频繁的，这样会筛选出很多不满足该性质的项集，将这些项在Ck中删除，即为剪枝。

3 改进的Apriori算法

3.1 改进Apriori算法的主要思想

本文结合地铁故障数据的关联规则挖掘需求，对Apriori算法进行改进：

1) 建立强关联规则，删除无关联单事务项，找出项与项之间存在的某种的关联关系，挖掘其关联性。Apriori算法产生频繁项的过程中需要对庞大的事务数据集进行多次扫描，删除无关联的事务项从而在一定程度上缩小数据集，提高运算效率。

2) 减少对事务数据库的扫描次数，对每个删除项进行计数。首先对频繁k-1项集进行剪枝，计算所有频繁k-1项集中项的支持度并对每个频繁项中的每个事务项进行计数，删除计数小于k-1的项集，确定删除项后再进行第二部的连接过程，减少Ck的数量，有效缩短算法运行时间。

3) 减少扫描次数，对每一个事务项用TID进行标识。在使用Apriori算法找到频繁项的过程中，需要对庞大的事务数据集进行多次扫描，进而给I/O带来较大的负担，进行TID标识后的算法只需在对数据库无关事务项的删除以及事务项的标识过程中进行扫描。

改进的Apriori算法只需遍历一次数据库，得到的是频繁项集之间的关联规则结果，其基本思想是遍历数据库，得到关联规则结果。

第1步：对每个事务项进行TID标识；

第2步：一次遍历数据库，删除不相关事务项，并对删除项计数，得到感兴趣集合B；

第3步：自连接，产生候选项；

第4步：集合交集运算，得到关联事务项。

改进Apriori 算法的主要步骤如下：

第2步：挖掘频繁项集。

对每个事务项进行计数，得到候选1-项集，其中≥min_sup的项组成频繁项集L1。

对生成的频繁项集L1自连接，产生候选2-项集，对其进行集合交集运算得到事务TID集，≥min_sup的项组成频繁项集L2。

计算Lk的模|Lk|，|Lk|≤k时运算终止，得到频繁项集L，否则重复步骤B。

3) 挖掘关联规则。计算支持度和置信度，分析变量之间的关联关系总结变量间的某种规律性，生成关联规则。

改进Apriori 算法流程如图2所示。

图2 改进Apriori算法流程框图Fig.2 Improved apriori algorithm flow chart

3.2 改进Apriori算法的代码实现

算法1：删减事务项算法实现。

输入：事务数据库D，事务项总数为m，感兴趣集为B；

输出：事务数据库D″；

处理流程如下：

SetD″=D;m′=m;i=1;

Repeat

For eachTi∈Ddo

Set flag=false;

For eachb∈Bdo

Flag=flag∪Ti[b]∪(Ti.count≠1);

If(flag=false)

SetD″=D″-1;

Setm′=m′-1;

Untilm;

算法2：挖掘关联规则改进Apriori 算法。

输入：数据集D″，小支持度min_sup；

输出：频繁项集Lk；

处理流程如下：

L1=findfrequent1-itemsets(D″);

C2=L1∞L1

L1=items inC2≥min_sup;

For(k=3;Lk-1≠∅;k++);

Prunel(Lk-1);//对Lk-1进行剪枝

Lx∈Lk，Ly∈Lk;

if (Lx[1]=Ly[1]∧Lx[2]=Ly[2]∧…∧Lx[k-2]=Ly[k-2]∧Lx[k-1]

If (k-1)-subsets ofc∉Lk-1

Then delet c fromCk

Ck=c∪Ck;

Lk=New_quick_support_count(Ck，TID_Set)

Answer=UkLk;

New_quick_support_count(Ck，TID_Set)

For all itemsetsc∈ck

C.TID_Set=Lk-1.TID_Set∩L1.TID_Set

C.Sup=Length(Ck.TID_Set

IfC.Sup

DeletCfromCk

Lk={C∈Ck|C.Sup≥min_sup}

Prunel(Lk)

For all itemsetsL1∈Lk

4 实例分析

选取某地铁三号线故障数据进行实验，对比分析Apriori 算法、FP-Growth算法与改进的Apriori 算法，程序在Python 3.7.1中进行编写，对算法其他参数的不同取值分别进行仿真分析，包括支持度、置信度，根据仿真结果选用适用性强的算法并进行合理的参数设置，深入挖掘地铁故障间的隐性关联规则。仿真的硬件环境为Inter(R) Core(TM) i7-10875H CPU @2.30GHz 16.0 GB RAM。

4.1 故障数据引入

本文收集了某地铁2020年7月的地铁三号线、四号线、宁和线、宁天线、机场线的信号故障数据，共有277条数据。由于篇幅有限，仅选取三号线的53条数据作为一个案例分析，后期再对数据量扩大升级进行研究。数据中的信号故障类型分为车载ATP故障、信号设备故障、对标故障、列车紧制故障、站台门联动故障等5种，其中每种类型又分为A、B、C、D等4个故障等级。

4.2 数据预处理

本案例中对数据预处理包括数据筛选和数据变换。数据来源于某地铁公司，需要筛选出对案例分析有价值的数据列表，即“故障号、线路、故障类型、接报时间”，对于无效选项列进行剔除，数据筛选后剩下5列数据内容，由于该数据库数据为连续性数值变量，Apriori关联规则挖掘算法无法对其进行处理，故需要对数据进行属性归类以及数据离散处理。将一天24 h以2 h为一个单元区间，划分为12个区段1、2、3…12。数据预处理后，根据故障等级形成最终的数据集，如表1所示。

表1 最终的建模数据集

表4中，A1、B1、C1、D1、X1分别表示车载ATP故障等级；A2、B2、C2、D2、Y2分别表示信号设备故障等级；A3、B3、C3、D3、P3分别表示对标故障等级；A4、B4、C4、D4、Q4分别表示列车紧制故障等级；A5、B5、C5、D5、Z5分别表示站台门联动故障等级。

4.3 模型建立

依据Apriori算法、FP-Growth算法、改进Apriori算法的流程图分别创建模型，对算法其他参数的不同取值分别进行仿真分析，包括支持度、置信度，根据仿真结果选用适用性强的算法并进行合理的参数设置开展地铁故障数据与时间的关联规则挖掘工作。

建模过程包括：输入样本数据以及建模参数；对比Apriori算法、FP-Growth算法、改进Apriori算法不同参数设置下的运行效率；根据仿真结果选用适用性强的算法建模仿真；对故障数据库以及输入参数进行处理；输出车载ATP故障、信号设备故障等多类故障之间的关联规则，进而对关联规则结果进行分析。

使用故障数据集，将优化前后的算法与FP-Growth算法进行仿真对比，分析运行时长随支持度和置信度两个参数的变化情况如图3、图4所示。

图3为改进前后最小支持度变化情况对比，随着支持度的增大，改进前后的算法运行时长都在缩短，当支持度较小时，改进算法的运行时长远小于优化前小于FP-Growth算法，支持度越大关联规则越重要，运行时长越短。

图3 改进前后最小支持度曲线Fig.3 Comparison of minimum support before and after improvement

图4 改进前后最小置信度曲线Fig.4 Comparison of minimum confidence before and after improvement

如图4所示，为改进前后2种算法的执行时间与最小置信度参数变化对比情况。随着置信度的增大，2种算法的运行时长差距不大，当置信度较小时，改进算法的运行时长远小于优化前小于FP-Growth算法，而此时关联规则的可靠性最强。

综上，在同样的数据库条件下，不同参数设置对比发现，改进后的Apriori算法运行效率明显优于FP-Growth算法，算法有效性得到充分验证。因此，本文应用改进的Apriori算法建模仿真，深入挖掘故障关联规则，参数取值最小支持度为6%、最小置信度为75%。运行界面输出的部分内容如图5所示。

图5 输出结果Fig.5 Output result

4.4 模型分析

根据上述的运行结果，研究得出了525个关联规则(如D2—X1—4 0.125 00 0.800 000)，其表示D2，X14，代表着信号设备D级故障和车载ATP设备X1级故障均发生在6∶00—8∶00时间段内的支持度是12.5%，置信度是80%。由于篇幅有限，选取关联规则结果的前6条以及后4条进行阐述，地铁故障间关联规则部分内容如表2所示。

表2 地铁故障关联规则挖掘

挖掘得到的地铁故障关联规则包含了时间关联，但并非所有挖掘出来的关联规则都具有研究价值，故需要通过二次筛选提取有效的关联规则进行故障影响分析。

5 结论

针对地铁故障数据种类多样、影响程度难以界定等问题，本文建立了关联规则挖掘算法模型；挖掘项与项之间的强关联规则，减少数据库扫描次数，提出了改进的Apriori算法；选取南京地铁2020年7月三号线的5种故障数据，将每种故障划分为A、B、C、D等4个等级，挖掘故障间隐藏的关联规则以及频繁发生时段。仿真结果表明，改进的Apriori算法可以满足地铁故障关联规则挖掘的要求，提高数据处理的效率以及地铁故障关联规则挖掘的可靠性，具有较好的应用价值。