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

刘文雅,徐永能

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

摘要:地铁作为城市公共客运的重要载体,其系统设备在运营过程中难免发生一些故障。因此,应用数据挖掘技术对已有地铁故障数据进行关联规则挖掘,分析其影响,对故障预警与风险危害评估具有重大意义。针对地铁故障数据种类多样、影响程度难以界定等问题,建立考虑故障关联的改进Apriori算法,与经典的FP-Growth算法进行对比,对地铁故障关联规则进行研究,优化该算法的基本思想和流程。选取某地铁2020年设备故障数据为例,对其进行详细地分析,基于Python语言实现建模仿真,输出得到车载ATP故障、信号设备故障等多类故障之间的关联规则结果,为地铁故障影响程度分析、故障诊断、故障预警、风险危害等级划分等提供重要的参考依据。

关键词:地铁故障;数据挖掘;关联规则;Apriori算法

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)。

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

2) 支持度(Support)。

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

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

3) 频繁项(Frequent ItemSets)。

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

4) 置信度(Confidence)。

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

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

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

2.2 Apriori算法

2.2.1 Apriori算法描述

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

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

2.2.2 Apriori算法流程

第1步:连接。

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

第2步:剪枝。

剪枝在连接完成后进行,即删除选项Ck中不满足判别条件的项。CkLk-1L1连接产生的,由于使用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 算法的主要步骤如下:

第1步:删除无关事务项记录。设事务项总数为m,遍历数据库为D,当Dx(x=1,2,…,m).count=1时,删除Dx,删除的事务项个数计为1,以此类推遍历循环后得到新的数据库D′。设感兴趣集为B,若则删除遍历循环得到新的数据集D″。

第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″;

处理流程如下:

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

Repeat

For each TiD do

Set flag=false;

For each bB do

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

If(flag=false)

Set D″=D″-1;

Set m′=m′-1;

Untilm;

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

输入:数据集D″,小支持度min_sup;

输出:频繁项集Lk

处理流程如下:

L1=findfrequent1-itemsets(D″);

C2=L1L1

L1=items in C2≥min_sup;

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

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

LxLkLyLk;

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

If (k-1)-subsets of cLk-1

Then delet c from Ck

Ck=cCk;

Lk=New_quick_support_count(Ck,TID_Set)

Answer=UkLk;

New_quick_support_count(Ck,TID_Set)

For all itemsets cck

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

C.Sup=Length(Ck.TID_Set

If C.Sup

Delet C from Ck

Lk={CCk|C.Sup≥min_sup}

Prunel(Lk)

For all itemsets L1Lk

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 最终的建模数据集

Table 1 Final modeling data set

时间车载ATP故障信号设备故障对标故障列车紧制故障站台门联动故障1X1C2P3Q4Z51D1D2P3Q4Z53X1C2P3Q4Z53X1D2P3Q4Z54D1A2P3Q4Z54D1C2P3Q4Z5………………8X1Y2P3C4Z58C1D2P3C4Z58D1D2P3C4Z5………………10C1C2D3Q4B510D1Y2P3Q4Z511C1Y2P3Q4Z511D1Y2P3Q4Z5

表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 地铁故障关联规则挖掘

Table 2 Mining of association rules for subway faults

序号关联规则支持度置信度1站台门联动Z级故障→对标故障P3⇒关联发生0.968 751.000 0002对标故障P3→站台门联动Z级故障⇒关联发生0.968 751.000 0003列车紧制装置Q级故障→站台门联动Z级故障→对标故障P3⇒关联发生0.812 501.000 0004列车紧制装置Q级故障→站台门联动Z级故障→对标故障P3⇒关联发生0.812 501.000 0005车载ATP系统D级故障→对标故障P3⇒关联发生0.562 501.000 0006车载ATP系统D级故障→站台门联动Z级故障⇒关联发生0.562 501.000 0007车载ATP系统D级故障→列车紧制装置Q级故障→车载ATP系统X级故障→站台门联动Z级故障⇒故障均发生在6∶00—8∶00时间段内0.125 000.800 008信号设备C级故障→车载ATP系统D级故障→对标故障P3→站台门联动Z级故障→列车紧制装置Q级故障⇒关联发生0.125 000.800 009对标故障P3→列车紧制装置Q级故障→站台门联动Z级故障→站台门联动Z级故障→车载ATP系统D级故障⇒故障均在16∶00—18∶00发生0.125 000.800 0010车载ATP系统D级故障→对标故障P3→列车紧制装置Q级故障→车载ATP系统X级故障→站台门联动Z级故障⇒故障均发生在6∶00—8∶00时间段内0.125 000.800 00

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

5 结论

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

参考文献:

[1] China Urban Rail Transit Association.Urban Rail Transit 2020 Annual Statistics and Analysis Report[R].2020.

[2] Park J S,Chen M S,Yu P S.An effective hash-based algorithm for mining association rules[J].Acm Sigmod Record,2016,24(2):175-186.

[3] Liu X Y,Niu X Z.Fournier Viger Philippe Fast Top-K association rule mining using rule generation property pruning[J].Applied Intelligence,2020,51(04):2077-2093.

[4] Djenouri Y, Djenouri D, Habbas Z, et al.How to exploit high performance computing in population-based metaheuristics for solving association rule mining problem[J].Distributed and Parallel Databases,2018,36(02):369-397.

[5] 张春,周静.动车组故障关联规则挖掘优化算法研究与应用[J].计算机与现代化,2017(09):74-78.

Zhang C,Zhou J.Research and application of optimization algorithm for mining EMU fault association rules[J].Computer and Modernization,2017(09):74-78.

[6] Zhou J.Research on the correlation analysis technology of the operation and maintenance efficiency of the key components of the EMU[D].Beijing Jiaotong University,2017.

[7] Zhou B.Research on association rules mining method of massive engineering data based on Hadoop[D].Beijing Jiaotong University,2016.

[8] 朱兴动,章思宇,王正.飞机故障维修记录关联规则挖掘方法[J].兵器装备工程学报,2019,40(07):164-169.

Zhu X D,Zhang S Y,Wang Z.Method for mining association rules of aircraft fault maintenance records[J].Ordnance Equipment Engineering Journal,2019,40(07):164-169.

[9] Russell I,Markov Z.An Introduction to the Weka Data Mining System ACM Sigcse Technical Symposium on Computer Science Education ACM,2017:742-742.

[10] 周凯,顾洪博,李爱国.基于关联规则挖掘Apriori算法的改进算法[J].陕西理工大学学报(自然科学版),2018,34(05):40-44.

Zhou K,Gu H B,Li A G.Improved algorithm based on association rule mining Apriori algorithm[J].Journal of Shaanxi University of Technology(Natural Science Edition),2018,34(05):40-44.

[11] Sharmila S,Vijayarani S.Association rule mining using fuzzy logic and whale optimization algorithm[J].Soft Computing,2021,25(02):1431-1446.

[12] Agapito G,Guzzi P H,Cannataro M. Parallel and distributed association rule mining in life science: A novel parallel algorithm to mine genomics data[J].Information Sciences, 2018(prepublish).DOI:10.1016/j.ins.2018.07.055.

[13] Qin X G.Research on signal system equipment maintenance strategy based on big data risk analysis[D].Beijing Jiaotong University,2018.

[14] 白莹莹,申晨晨.基于关联规则挖掘的Apriori改进算法[J].电子技术与软件工程,2017(03):203-204.

Bai Y Y,Shen C C.Improved Apriori algorithm based on association rule mining[J].Electronic Technology and Software Engineering,2017(03):203-204.

[15] 曾子贤,巩青歌,张俊.改进的关联规则挖掘算法——MIFP-Apriori算法[J].科学技术与工程,2019,19(16):216-220.

Zeng Z X,Gong Q G,Zhang J.Improved algorithm for mining association rules-MIFP-Apriori algorithm[J].Science Technology and Engineering,2019,19(16):216-220.

Association Rule Mining of Metro Failures Based on Improved Apriori Algorithm

LIU Wenya, XU Yongneng

(Nanjing University of Science and Technology, Nanjing 210094, China)

Abstract: As an important carrier of urban public transportation, metro system equipment inevitably has some failures during its operation. It is of great significance to apply data mining technology to mine some association rules from existing metro failure data and analyze their influence, so as to evaluate earl yfailure warning and risk hazards. Targeting the variety of metro failure data and the difficulty in defining an impact degree, an improved Apriori algorithm that considers failure association was proposed. Compared with a classic FP-Growth algorithm, metro failure association rules were studied, and subsequently their basic ideas and processes were optimized. Finally, taking metro equipment failure data in 2020 as an example, a model was simulated and established based on the Python. Results showed an association rule among ATP failures, signal equipment failures and other types of failures, which provides an important reference for failure degree analysis, failure diagnosis, failure warning, risk hazard classification, etc.

Key words: metro failure;data mining;association rule;Apriori algorithm

收稿日期:2021-05-14;

修回日期:2021-06-19

基金项目:国家自然科学基金项目(52072214);国家重点研发计划项目(2017YFB1001801)

作者简介:刘文雅(1996—),女,硕士研究生,E-mail:964483562@qq.com。

通信作者:徐永能(1972—),男,博士,副教授,E-mail:x780906yn@163.com。

doi: 10.11809/bqzbgcxb2021.12.033

本文引用格式:刘文雅,徐永能.基于改进Apriori算法的地铁故障关联规则挖掘[J].兵器装备工程学报,2021,42(12):210-215.

Citation format: LIU Wenya, XU Yongneng.Association Rule Mining of Metro Failures Based on Improved Apriori Algorithm[J].Journal of Ordnance Equipment Engineering,2021,42(12):210-215.

中图分类号:TP181TP391U-9U1U4

文献标识码:A

文章编号:2096-2304(2021)12-0210-06

科学编辑 王冬 博士(上海交通大学副教授、博导)

责任编辑 唐定国