基于改進(jìn)Apriori算法的地鐵故障關(guān)聯(lián)規(guī)則挖掘

劉文雅，徐永能

(南京理工大學(xué)， 南京 210094)

1 引言

近年來，國內(nèi)城市地鐵行業(yè)已迎來建設(shè)高峰期，運營線路逐年遞增，投入運營總里程不斷刷新記錄。截止2020年底，南京地鐵已開通運營1、2、3、4、10、S1、S3、S7、S8、S9共10條線路，總線路長度達(dá)394.3 km，日均客運量達(dá)到218萬人次[1]。隨著網(wǎng)絡(luò)化線路的逐步形成，系統(tǒng)設(shè)備故障明顯增多。對故障數(shù)據(jù)進(jìn)行有效地處理分析從而找到故障之間的關(guān)聯(lián)性，將關(guān)聯(lián)性結(jié)果量化處理，為后續(xù)故障影響程度分析、風(fēng)險等級劃分、故障診斷、故障預(yù)警等研究奠定基礎(chǔ)，具有重要意義。

關(guān)聯(lián)規(guī)則挖掘[2]是大數(shù)據(jù)分析的重要課題，在數(shù)據(jù)分析領(lǐng)域得到廣泛應(yīng)用，很多國內(nèi)外學(xué)者對關(guān)聯(lián)規(guī)則挖掘算法[3-7]展開了深入研究，F(xiàn)P-Growth算法[8-9]和Apriori算法[10-12]是進(jìn)行關(guān)聯(lián)規(guī)則挖掘最常用的2種算法。FP-Growth算法是在Apriori算法的基礎(chǔ)上，將Apriori算法遍歷得到的頻繁項按樹結(jié)構(gòu)進(jìn)行統(tǒng)計得到頻繁項集樹FP-tree。該算法只能處理布爾類數(shù)據(jù)，輸出得到的是頻繁項集，而不是關(guān)聯(lián)結(jié)果。本文從綜合考慮地鐵故障數(shù)據(jù)冗余以及規(guī)則難以挖掘的問題出發(fā)，以提高算法處理效率、深入挖掘故障間關(guān)聯(lián)規(guī)則為優(yōu)化目標(biāo)，對Apriori算法的思想和流程進(jìn)行優(yōu)化，提出了一種考慮地鐵故障關(guān)聯(lián)規(guī)則的改進(jìn)Apriori算法。將改進(jìn)的算法與經(jīng)典的FP-Growth算法仿真對比，驗證其有效性。計算得到的故障數(shù)據(jù)的關(guān)聯(lián)規(guī)則結(jié)果，為地鐵故障影響分析、故障診斷、故障預(yù)測、故障預(yù)警提供重要參考依據(jù)。

2 關(guān)聯(lián)規(guī)則問題描述及基本理論

2.1 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘是進(jìn)行大數(shù)據(jù)分析最常用的研究方法之一，它的目的在于從龐大數(shù)據(jù)集中找出各項之間的關(guān)聯(lián)，而這種關(guān)聯(lián)不會在數(shù)據(jù)中表現(xiàn)出來，需要進(jìn)行關(guān)聯(lián)分析，分析多個變量之間的聯(lián)系。關(guān)聯(lián)分析多被分為3類：簡單關(guān)聯(lián)、時序關(guān)聯(lián)、因果關(guān)聯(lián)[13]。其2個重要參數(shù)是最小支持度、最小可信度，參數(shù)取值會直接影響最后得到的關(guān)聯(lián)結(jié)果。因此，為了使挖掘結(jié)果更具研究價值，相關(guān)學(xué)者多引入其他關(guān)聯(lián)分析參數(shù)對關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行改進(jìn)[14-15]。

1) 關(guān)聯(lián)規(guī)則(Association Rules)。

把形如X?Y這樣的表達(dá)式簡稱為關(guān)聯(lián)規(guī)則，符號?稱為關(guān)聯(lián)，X稱為?的先決條件，Y則稱為?的結(jié)果。其中X?I，Y?I，X≠?、Y≠?且X∩Y=?，非空集合為某些項目組成。

2) 支持度(Support)。

支持集合X在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的頻率，即為支持度。假設(shè)d={Q，S}為一事務(wù)，如果存在X?S，則稱為事務(wù)d支持X，即事務(wù)數(shù)據(jù)庫D支持集合X，稱為支持度，記作S(X)。支持度是用來衡量關(guān)聯(lián)規(guī)則重要性的關(guān)鍵量，支持度越高關(guān)聯(lián)規(guī)則越重要。

Sup(X?Y)=S(X∪Y)為關(guān)聯(lián)規(guī)則X?Y的支持度，表示X∪Y在數(shù)據(jù)庫D中出現(xiàn)的頻率。Sup(X?Y)記作S(X?Y)。

3) 頻繁項(Frequent ItemSets)。

當(dāng)S(X)≥MinSup，則稱X為頻繁項。其中，X?I且X≠?X，MinSup為支持度閥值，也是最小支持度。如果構(gòu)成X的項目數(shù)為K，則X稱為K-維頻繁項。若X為頻繁項，S(X)為其支持度，有X′?X且X′≠?，X′其支持度為S(X′)，當(dāng)S(X′)≥S(X)，則X′為頻繁項。

4) 置信度(Confidence)。

Conf(X?Y)=S(X∪Y)/S(X)為關(guān)聯(lián)規(guī)則X?Y的置信度。關(guān)聯(lián)規(guī)則X?Y的置信度在[0,1]之間取值，0≤Conf(X?Y)≤1。置信度是用來衡量關(guān)聯(lián)規(guī)則可靠性的關(guān)鍵參數(shù)，置信度的高低代表關(guān)聯(lián)規(guī)則可信程度的高低。

關(guān)聯(lián)規(guī)則挖掘基本模型如圖1所示。

圖1 關(guān)聯(lián)規(guī)則挖掘基本模型Fig.1 Basic model of association rule mining

2.2 Apriori算法

2.2.1Apriori算法描述

Apriori算法目的是找出事務(wù)數(shù)據(jù)集中的最大的頻繁項集，其基本思想是預(yù)先設(shè)定最小置信度閾值，然后找到最大頻繁項集與預(yù)先設(shè)定的最小置信度閾值之間的關(guān)聯(lián)規(guī)則。需要對數(shù)據(jù)庫不斷掃描，第一次掃描得到1-頻繁項集合l1，第k-1次得到頻繁項集Lk-1，產(chǎn)生k-候選項集合Ck，確定Ck中每事務(wù)項的支持度，然后計算找出k-頻繁項集合Lk，直到Ck=?時停止。

為提高算法運行的效率，事務(wù)數(shù)據(jù)庫中找到的最大頻繁項集所有的非空子集都是頻繁的，假如存在項集不是頻繁的，且P(i)

2.2.2Apriori算法流程

第1步：連接。

找到k-頻繁項集合Lk。首先預(yù)先設(shè)定最小支持度閾值，刪除1項候選集C1中小于最小支持度閾值的項，得到1-頻繁項集L1，L1自連接產(chǎn)生2項頻繁項集L2，L2與L3連接產(chǎn)生候選集C3，刪除2項候選集C2中小于最小支持度閾值的項，得到3項頻繁項集L3,以此類推，最終得到最大頻繁項集Lk。

第2步：剪枝。

剪枝在連接完成后進(jìn)行，即刪除選項Ck中不滿足判別條件的項。Ck是Lk-1與L1連接產(chǎn)生的，由于使用Apriori算法在事務(wù)數(shù)據(jù)庫中找到的最大頻繁項集所有的非空子集都是頻繁的，這樣會篩選出很多不滿足該性質(zhì)的項集，將這些項在Ck中刪除，即為剪枝。

3 改進(jìn)的Apriori算法

3.1 改進(jìn)Apriori算法的主要思想

本文結(jié)合地鐵故障數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘需求，對Apriori算法進(jìn)行改進(jìn)：

1) 建立強(qiáng)關(guān)聯(lián)規(guī)則，刪除無關(guān)聯(lián)單事務(wù)項，找出項與項之間存在的某種的關(guān)聯(lián)關(guān)系，挖掘其關(guān)聯(lián)性。Apriori算法產(chǎn)生頻繁項的過程中需要對龐大的事務(wù)數(shù)據(jù)集進(jìn)行多次掃描，刪除無關(guān)聯(lián)的事務(wù)項從而在一定程度上縮小數(shù)據(jù)集，提高運算效率。

2) 減少對事務(wù)數(shù)據(jù)庫的掃描次數(shù)，對每個刪除項進(jìn)行計數(shù)。首先對頻繁k-1項集進(jìn)行剪枝，計算所有頻繁k-1項集中項的支持度并對每個頻繁項中的每個事務(wù)項進(jìn)行計數(shù)，刪除計數(shù)小于k-1的項集，確定刪除項后再進(jìn)行第二部的連接過程，減少Ck的數(shù)量，有效縮短算法運行時間。

3) 減少掃描次數(shù)，對每一個事務(wù)項用TID進(jìn)行標(biāo)識。在使用Apriori算法找到頻繁項的過程中，需要對龐大的事務(wù)數(shù)據(jù)集進(jìn)行多次掃描，進(jìn)而給I/O帶來較大的負(fù)擔(dān)，進(jìn)行TID標(biāo)識后的算法只需在對數(shù)據(jù)庫無關(guān)事務(wù)項的刪除以及事務(wù)項的標(biāo)識過程中進(jìn)行掃描。

改進(jìn)的Apriori算法只需遍歷一次數(shù)據(jù)庫，得到的是頻繁項集之間的關(guān)聯(lián)規(guī)則結(jié)果，其基本思想是遍歷數(shù)據(jù)庫，得到關(guān)聯(lián)規(guī)則結(jié)果。

第1步：對每個事務(wù)項進(jìn)行TID標(biāo)識；

第2步：一次遍歷數(shù)據(jù)庫，刪除不相關(guān)事務(wù)項，并對刪除項計數(shù)，得到感興趣集合B；

第3步：自連接，產(chǎn)生候選項；

第4步：集合交集運算，得到關(guān)聯(lián)事務(wù)項。

改進(jìn)Apriori 算法的主要步驟如下：

第2步：挖掘頻繁項集。

對每個事務(wù)項進(jìn)行計數(shù)，得到候選1-項集，其中≥min_sup的項組成頻繁項集L1。

對生成的頻繁項集L1自連接，產(chǎn)生候選2-項集，對其進(jìn)行集合交集運算得到事務(wù)TID集，≥min_sup的項組成頻繁項集L2。

計算Lk的模|Lk|，|Lk|≤k時運算終止，得到頻繁項集L，否則重復(fù)步驟B。

3) 挖掘關(guān)聯(lián)規(guī)則。計算支持度和置信度，分析變量之間的關(guān)聯(lián)關(guān)系總結(jié)變量間的某種規(guī)律性，生成關(guān)聯(lián)規(guī)則。

改進(jìn)Apriori 算法流程如圖2所示。

圖2 改進(jìn)Apriori算法流程框圖Fig.2 Improved apriori algorithm flow chart

3.2 改進(jìn)Apriori算法的代碼實現(xiàn)

算法1：刪減事務(wù)項算法實現(xiàn)。

輸入：事務(wù)數(shù)據(jù)庫D，事務(wù)項總數(shù)為m，感興趣集為B；

輸出：事務(wù)數(shù)據(jù)庫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：挖掘關(guān)聯(lián)規(guī)則改進(jìn)Apriori 算法。

輸入：數(shù)據(jù)集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進(jìn)行剪枝

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 實例分析

選取某地鐵三號線故障數(shù)據(jù)進(jìn)行實驗，對比分析Apriori 算法、FP-Growth算法與改進(jìn)的Apriori 算法，程序在Python 3.7.1中進(jìn)行編寫，對算法其他參數(shù)的不同取值分別進(jìn)行仿真分析，包括支持度、置信度，根據(jù)仿真結(jié)果選用適用性強(qiáng)的算法并進(jìn)行合理的參數(shù)設(shè)置，深入挖掘地鐵故障間的隱性關(guān)聯(lián)規(guī)則。仿真的硬件環(huán)境為Inter(R) Core(TM) i7-10875H CPU @2.30GHz 16.0 GB RAM。

4.1 故障數(shù)據(jù)引入

本文收集了某地鐵2020年7月的地鐵三號線、四號線、寧和線、寧天線、機(jī)場線的信號故障數(shù)據(jù)，共有277條數(shù)據(jù)。由于篇幅有限，僅選取三號線的53條數(shù)據(jù)作為一個案例分析，后期再對數(shù)據(jù)量擴(kuò)大升級進(jìn)行研究。數(shù)據(jù)中的信號故障類型分為車載ATP故障、信號設(shè)備故障、對標(biāo)故障、列車緊制故障、站臺門聯(lián)動故障等5種，其中每種類型又分為A、B、C、D等4個故障等級。

4.2 數(shù)據(jù)預(yù)處理

本案例中對數(shù)據(jù)預(yù)處理包括數(shù)據(jù)篩選和數(shù)據(jù)變換。數(shù)據(jù)來源于某地鐵公司，需要篩選出對案例分析有價值的數(shù)據(jù)列表，即“故障號、線路、故障類型、接報時間”，對于無效選項列進(jìn)行剔除，數(shù)據(jù)篩選后剩下5列數(shù)據(jù)內(nèi)容，由于該數(shù)據(jù)庫數(shù)據(jù)為連續(xù)性數(shù)值變量，Apriori關(guān)聯(lián)規(guī)則挖掘算法無法對其進(jìn)行處理，故需要對數(shù)據(jù)進(jìn)行屬性歸類以及數(shù)據(jù)離散處理。將一天24 h以2 h為一個單元區(qū)間，劃分為12個區(qū)段1、2、3…12。數(shù)據(jù)預(yù)處理后，根據(jù)故障等級形成最終的數(shù)據(jù)集，如表1所示。

表1 最終的建模數(shù)據(jù)集

表4中，A1、B1、C1、D1、X1分別表示車載ATP故障等級；A2、B2、C2、D2、Y2分別表示信號設(shè)備故障等級；A3、B3、C3、D3、P3分別表示對標(biāo)故障等級；A4、B4、C4、D4、Q4分別表示列車緊制故障等級；A5、B5、C5、D5、Z5分別表示站臺門聯(lián)動故障等級。

4.3 模型建立

依據(jù)Apriori算法、FP-Growth算法、改進(jìn)Apriori算法的流程圖分別創(chuàng)建模型，對算法其他參數(shù)的不同取值分別進(jìn)行仿真分析，包括支持度、置信度，根據(jù)仿真結(jié)果選用適用性強(qiáng)的算法并進(jìn)行合理的參數(shù)設(shè)置開展地鐵故障數(shù)據(jù)與時間的關(guān)聯(lián)規(guī)則挖掘工作。

建模過程包括：輸入樣本數(shù)據(jù)以及建模參數(shù)；對比Apriori算法、FP-Growth算法、改進(jìn)Apriori算法不同參數(shù)設(shè)置下的運行效率；根據(jù)仿真結(jié)果選用適用性強(qiáng)的算法建模仿真；對故障數(shù)據(jù)庫以及輸入?yún)?shù)進(jìn)行處理；輸出車載ATP故障、信號設(shè)備故障等多類故障之間的關(guān)聯(lián)規(guī)則，進(jìn)而對關(guān)聯(lián)規(guī)則結(jié)果進(jìn)行分析。

使用故障數(shù)據(jù)集，將優(yōu)化前后的算法與FP-Growth算法進(jìn)行仿真對比，分析運行時長隨支持度和置信度兩個參數(shù)的變化情況如圖3、圖4所示。

圖3為改進(jìn)前后最小支持度變化情況對比，隨著支持度的增大，改進(jìn)前后的算法運行時長都在縮短，當(dāng)支持度較小時，改進(jìn)算法的運行時長遠(yuǎn)小于優(yōu)化前小于FP-Growth算法，支持度越大關(guān)聯(lián)規(guī)則越重要，運行時長越短。

圖3 改進(jìn)前后最小支持度曲線Fig.3 Comparison of minimum support before and after improvement

圖4 改進(jìn)前后最小置信度曲線Fig.4 Comparison of minimum confidence before and after improvement

如圖4所示，為改進(jìn)前后2種算法的執(zhí)行時間與最小置信度參數(shù)變化對比情況。隨著置信度的增大，2種算法的運行時長差距不大，當(dāng)置信度較小時，改進(jìn)算法的運行時長遠(yuǎn)小于優(yōu)化前小于FP-Growth算法，而此時關(guān)聯(lián)規(guī)則的可靠性最強(qiáng)。

綜上，在同樣的數(shù)據(jù)庫條件下，不同參數(shù)設(shè)置對比發(fā)現(xiàn)，改進(jìn)后的Apriori算法運行效率明顯優(yōu)于FP-Growth算法，算法有效性得到充分驗證。因此，本文應(yīng)用改進(jìn)的Apriori算法建模仿真，深入挖掘故障關(guān)聯(lián)規(guī)則，參數(shù)取值最小支持度為6%、最小置信度為75%。運行界面輸出的部分內(nèi)容如圖5所示。

圖5 輸出結(jié)果Fig.5 Output result

4.4 模型分析

根據(jù)上述的運行結(jié)果，研究得出了525個關(guān)聯(lián)規(guī)則(如D2—X1—4 0.125 00 0.800 000)，其表示D2，X14，代表著信號設(shè)備D級故障和車載ATP設(shè)備X1級故障均發(fā)生在6∶00—8∶00時間段內(nèi)的支持度是12.5%，置信度是80%。由于篇幅有限，選取關(guān)聯(lián)規(guī)則結(jié)果的前6條以及后4條進(jìn)行闡述，地鐵故障間關(guān)聯(lián)規(guī)則部分內(nèi)容如表2所示。

表2 地鐵故障關(guān)聯(lián)規(guī)則挖掘

挖掘得到的地鐵故障關(guān)聯(lián)規(guī)則包含了時間關(guān)聯(lián)，但并非所有挖掘出來的關(guān)聯(lián)規(guī)則都具有研究價值，故需要通過二次篩選提取有效的關(guān)聯(lián)規(guī)則進(jìn)行故障影響分析。

5 結(jié)論

針對地鐵故障數(shù)據(jù)種類多樣、影響程度難以界定等問題，本文建立了關(guān)聯(lián)規(guī)則挖掘算法模型；挖掘項與項之間的強(qiáng)關(guān)聯(lián)規(guī)則，減少數(shù)據(jù)庫掃描次數(shù)，提出了改進(jìn)的Apriori算法；選取南京地鐵2020年7月三號線的5種故障數(shù)據(jù)，將每種故障劃分為A、B、C、D等4個等級，挖掘故障間隱藏的關(guān)聯(lián)規(guī)則以及頻繁發(fā)生時段。仿真結(jié)果表明，改進(jìn)的Apriori算法可以滿足地鐵故障關(guān)聯(lián)規(guī)則挖掘的要求，提高數(shù)據(jù)處理的效率以及地鐵故障關(guān)聯(lián)規(guī)則挖掘的可靠性，具有較好的應(yīng)用價值。