基于改進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算法可以滿足地鐵故障關聯規則挖掘的要求，提高數據處理的效率以及地鐵故障關聯規則挖掘的可靠性，具有較好的應用價值。