基于動態(tài)關(guān)聯(lián)規(guī)則的TApriori算法

李文鋒，陳俊賢

(1.金陵科技學(xué)院軟件工程學(xué)院，江蘇南京 211169 2.蘇州工業(yè)園區(qū)服務(wù)外包職業(yè)學(xué)院信息工程學(xué)院，江蘇蘇州 215125)

隨著我國軌道交通的快速建設(shè)，大量的系統(tǒng)設(shè)備已經(jīng)步入運維管理階段。然而，由于我國前期重點關(guān)注軌道交通系統(tǒng)的系統(tǒng)建設(shè)及建設(shè)人才的培養(yǎng)，導(dǎo)致現(xiàn)在軌道交通行業(yè)在檢修運維技術(shù)尤其是故障診斷和壽命預(yù)測方面的能力差［1］，依舊采用傳統(tǒng)故障修、計劃修手段進行故障判斷及處理，維護決策多以人工經(jīng)驗為主，缺乏有效的數(shù)據(jù)支持和智能化指導(dǎo)［2］。隨著大數(shù)據(jù)時代的到來，信息數(shù)據(jù)在生活中的作用越來越重要，人們需要高效自動化的數(shù)據(jù)分析技術(shù)對大量冗雜無規(guī)律的信息進行分類管理，數(shù)據(jù)挖掘技術(shù)［3－4］應(yīng)運而生。

Apriori算法［5］是用于尋找給定數(shù)據(jù)集中元素之間的關(guān)聯(lián)關(guān)系的經(jīng)典算法。在應(yīng)用過程中，最小支持度和最小置信度的值均是根據(jù)人的經(jīng)驗設(shè)定。當(dāng)每個事務(wù)中元素數(shù)量多時，如果最小支持度、最小置信度設(shè)置太低，關(guān)聯(lián)規(guī)則會特別多，得到的結(jié)果沒有價值；當(dāng)每個事務(wù)中的元素數(shù)量少時，如果最小支持度、最小置信度設(shè)置太高，關(guān)聯(lián)規(guī)則會特別少，得到的結(jié)果也是沒有價值。所以，確定合適的最小支持度和最小置信度的值非常重要。有關(guān)Apriori算法進行優(yōu)化的相關(guān)研究成果不少，研究成果主要有對頻繁項集進行優(yōu)化和關(guān)聯(lián)規(guī)則優(yōu)化兩個方面。文獻［6－7］提出的優(yōu)化頻繁項集方法，對Apriori算法進行優(yōu)化；文獻［8］首先指定一個全局最小支持度 ，然后用該支持度與每步頻繁項集的支持度進行比較 ，得到最小支持度。文獻［9］采用貝葉斯算法對元素進行預(yù)估，得到動態(tài)的置信度。文獻［10］使用更新的事務(wù)和前面階段的挖掘結(jié)果，用Apriori類算法作為局部過程來產(chǎn)生頻集。文獻［11］利用趨勢度方法挖掘出類關(guān)聯(lián)規(guī)則集。但是，這些關(guān)聯(lián)規(guī)則優(yōu)化都是通過人工加入或利用歷史數(shù)據(jù)統(tǒng)計最小支持度作為參考數(shù)據(jù)，在實際頻繁項集過程中選用的最小支持度，其本質(zhì)沒有擺脫設(shè)定最小支持度和最小置信度值的問題。

軌道交通專用通信系統(tǒng)中的集中告警系統(tǒng)在運維過程中一旦出現(xiàn)故障，手工排除故障是當(dāng)前軌道交通安全運營的唯一手段［12－14］。集中告警系統(tǒng)雖然采集了大量告警數(shù)據(jù)，但如何處理并利用相關(guān)數(shù)據(jù)分析預(yù)測設(shè)備狀態(tài)和故障，目前還沒有成熟的解決方案［15］，須通過大數(shù)據(jù)、人工智能等技術(shù)提升設(shè)備監(jiān)測和智能維修管理的能力。目前軌道交通設(shè)備的故障關(guān)聯(lián)分析在綜合監(jiān)控專業(yè)、信號專業(yè)和車輛專業(yè)已經(jīng)開始，但是在通信專業(yè)的相關(guān)研究剛剛起步。在綜合監(jiān)控專業(yè)方面，文獻［16－17］主要利用專家知識庫在發(fā)生的故障時，提供故障的快速定位和處理措施供值班員參考。文獻［18］提出構(gòu)建故障屬性集建立樣本空間，根據(jù)當(dāng)前監(jiān)測數(shù)據(jù)，推斷可能跟此故障相關(guān)的新故障，供值班人員盡早發(fā)現(xiàn)風(fēng)險隱患，降低運營風(fēng)險。

本文在不引入歷史經(jīng)驗數(shù)據(jù)及人工加入最小支持度和最小置信度的情況下，利用事務(wù)中呈現(xiàn)的數(shù)據(jù)，動態(tài)生成最小支持度及最小置信度，實現(xiàn)軌道交通專用通信系統(tǒng)中的集中告警系統(tǒng)進行故障分析。由于系統(tǒng)的故障跟時間是相關(guān)的，任何一條故障一定對應(yīng)有一個時間屬性，而且一些關(guān)聯(lián)故障在時間上具有相近性，因此，本文利用時間屬性作為關(guān)聯(lián)故障的特征之一進行研究。

1 TApriori算法

1.1 算法描述

本算法是在Apriori算法的基礎(chǔ)上對事務(wù)和子數(shù)據(jù)進行構(gòu)建，根據(jù)給定的事務(wù)集的元素計算子數(shù)據(jù)集的最小支持度和最小置信度，然后計算數(shù)據(jù)集的最小支持度和最小置信度。具體描述如下：

（1）構(gòu)建事務(wù)。根據(jù)事務(wù)中元素出現(xiàn)的時間，以固定時間為單位，將固定時間單位內(nèi)的所有元素構(gòu)成一個事務(wù)。以同樣的方式構(gòu)建其他所有的事務(wù)；

（2）建立子數(shù)據(jù)集。根據(jù)事務(wù)發(fā)生的時間順序，以固定的連續(xù)的時間段為單位，構(gòu)建子數(shù)據(jù)集。在建立子數(shù)據(jù)集時，如果出現(xiàn)某個事務(wù)與前后相鄰的事務(wù)不連續(xù)，則其單獨建立一個子數(shù)據(jù)集；

（3）掃描各子數(shù)據(jù)集事務(wù)中各元素的出現(xiàn)次數(shù)，計算其在當(dāng)前子數(shù)據(jù)集中的最小置信度和最小支持度，找出對應(yīng)的一元頻集；將各子數(shù)據(jù)集的最小支持度和最小置信度分別求均值，計算出子數(shù)據(jù)集最小支持度和最小置信度；

（4）產(chǎn)生候選項集。前一頻繁項集與自身連接產(chǎn)生候選當(dāng)前項集；

（5）計算數(shù)據(jù)集的最小支持度和最小置信度，產(chǎn)生數(shù)據(jù)集的頻繁集。

1.2 相關(guān)術(shù)語

假設(shè)數(shù)據(jù)集中共有n個元素，m個事務(wù)和l個子數(shù)據(jù)集，則元素、子數(shù)據(jù)集及數(shù)據(jù)集的定義如下：

元素，最小的表示單位。一條事務(wù)中可能包含一個或多個元素。 Tj＝ ｛I1，I2，I3，…，Ii，…，In｝，Tj表示第 j個事務(wù) （j≤ m），Ii表示第 i個元素（i≤n）。

子數(shù)據(jù)集Dk。由多條事務(wù)組成的集合。

Dk＝ ｛T1，T2，T3，…，Tj，…，Tl｝，Dk表 示 第k（k≤l）個子數(shù)據(jù)集。

數(shù)據(jù)集D。是子數(shù)據(jù)集的集合。D＝｛D1，D2，D3，…，Dk，…，Dl｝。

1.3 事務(wù) Tj的構(gòu)建

構(gòu)建每個事務(wù)時需要對元素進行分類，根據(jù)元素的時間屬性值將他們劃分到不同的事務(wù)中。實際在過程中，將第一個元素作為第一個事務(wù)的第一個元素，然后順序取下一個元素，判定是否滿足隸屬本事務(wù)，如果隸屬則繼續(xù)下一條；否則，新構(gòu)建事務(wù)。在事務(wù)構(gòu)建時，首先構(gòu)建事務(wù)T1，選取最早時間出現(xiàn)的元素I1，記錄其時間屬性值t1，然后選擇下一個元素時間屬性值與元素I1的時間屬性值進行距離運算。用d1i（I1，Ii）表示第1個元素與第 i個元素之間的距離，則可以表示為

當(dāng)計算結(jié)果 d1i（I1，Ii） 為 0，則說明第 1 個元素與第i個元素隸屬于同一事務(wù)。當(dāng)計算結(jié)果d1i（I1，Ii）不為0，則說明第1個元素與第i個元素隸屬于不同的事務(wù)，此時構(gòu)建事務(wù)T2，將第i個元素編號重新從1開始，依次重新排序后續(xù)元素編號，重復(fù)上述步驟，直到下一個事務(wù)的元素產(chǎn)生，以此類推，建立所有的事務(wù)。

1.4 子數(shù)據(jù)集 Dk的構(gòu)建

事務(wù)構(gòu)建結(jié)束后，需要進一步構(gòu)建子數(shù)據(jù)集Dk，即將多個相似的事務(wù)歸并在同一類，形成子數(shù)據(jù)集。在構(gòu)建過程中，從第一個事務(wù)T1開始，計算所有事務(wù)Tj與第一個事務(wù)之間的距離，將相同距離的事務(wù)歸為同一子數(shù)據(jù)集，直到所有事務(wù)歸到子數(shù)據(jù)集。

假定每個事務(wù)Tj對應(yīng)的時間屬性為tj（j≤m），則任意兩個事務(wù) Ti，Tj之間的距離可以用 dij（Ii，Ij）表示

在子數(shù)據(jù)集Dk構(gòu)建時，首先選取第一個事務(wù)Ti（i＝ 1） 與事務(wù) Tj（j＝ 2） 的時間屬性進行式（2）計算，如果 dij（Ii，Ij） ≤ C（C 為常量），則將事務(wù) Ti，Tj合并到同一個子數(shù)據(jù)集中，然后取事務(wù)Tj（j＝2）對應(yīng)的下一個事務(wù)Tj（j＝j(luò)＋1），重復(fù)上述比較過程，直到出現(xiàn) dij（Ii，Ij） ≥ C。 當(dāng)出現(xiàn) dij（Ii，Ij） ≥ C 時，構(gòu)建下一個子數(shù)據(jù)集，則將此時的j值賦給i，j取下一個事務(wù)對應(yīng)的值，重復(fù)執(zhí)行上述比較過程，直到所有事務(wù)比較結(jié)束。

子數(shù)據(jù)集的數(shù)量取決于每個事務(wù)的時間屬性及C常量。當(dāng)C設(shè)置為60 s時，則將每個事務(wù)的時間屬性相差間隔小于60 s內(nèi)的所有事務(wù)構(gòu)成一個數(shù)據(jù)子集，否則構(gòu)成新的子數(shù)據(jù)集。

2 動態(tài)關(guān)聯(lián)規(guī)則

2.1 子數(shù)據(jù)集Dk的最小支持度

子數(shù)據(jù)集Dk的最小支持度用 Sk（IX→ IY）表示，用同時出現(xiàn)IX，IY的事務(wù)次數(shù)／總的事務(wù)次數(shù)的比值表示

其中，σ（IX∪IY）表示子數(shù)據(jù)集中元素IX，IY出現(xiàn)的事務(wù)次數(shù)，N表示在子數(shù)據(jù)集中總的事務(wù)次數(shù)。

對于子數(shù)據(jù)集任意的IX事務(wù)出現(xiàn)的次數(shù)，可表示為

其中，Tj表示第j個事務(wù)，Dk表示事務(wù)的集合。

2.2 數(shù)據(jù)集的最小支持度

假定數(shù)據(jù)集D有l(wèi)個子數(shù)據(jù)集，則數(shù)據(jù)集D的最小支持度用所有子數(shù)據(jù)集Dk的最小支持度Si（IX→IY）之和與子數(shù)據(jù)集Dk的總數(shù)的比值表示，有

用σsdi表示數(shù)據(jù)集D的最小支持度SD（IX→IY）與子數(shù)據(jù)集Dk的最小支持度Sk（IX→IY）的差，有

當(dāng)σsdi＜0時，表示子數(shù)據(jù)集Dk的最小支持度Si（IX→IY）達到數(shù)據(jù)集D的最小支持度，在生成頻繁集時，要參與運算。當(dāng)σsdi≥0時，表示子數(shù)據(jù)集Dk的最小支持度Sk（IX→IY）達不到數(shù)據(jù)集D的最小支持度，在生成頻繁集時，不用運算。因此，在數(shù)據(jù)集D的 n個子數(shù)據(jù)集的最小支持度中，如果σsdi≥0的總數(shù)m越多，需要參與生成的元素數(shù)減少，算法運行時間也越短。

2.3 子數(shù)據(jù)集Dk的最小置信度

子數(shù)據(jù)集Dk的最小置信度Ck（IX→IY）定義為同時出現(xiàn)IX，IY的事務(wù)次數(shù)／IX出現(xiàn)的事務(wù)次數(shù)，有

2.4 數(shù)據(jù)集的最小置信度

假定數(shù)據(jù)集D有n個子數(shù)據(jù)集，則數(shù)據(jù)集D的最小置信度用所有子數(shù)據(jù)集Dk的最小支持度Ck（IX→IY）之和與子數(shù)據(jù)集Dk的總數(shù)的比值表示，有

用σcdi表示數(shù)據(jù)集D的最小置信度CD（IX→IY）與子數(shù)據(jù)集Dk的最小置信度Ck（IX→IY）的差，有

當(dāng)σcdi＜0時，表示子數(shù)據(jù)集Dk的最小置信度Ck（IX→IY）達到數(shù)據(jù)集D的最小置信度，在生成頻繁集時，要參與運算。當(dāng)σcdi≥0時，表示子數(shù)據(jù)集Dk的最小置信度Ck（IX→IY）達不到數(shù)據(jù)集D的最小置信度，在生成頻繁集時，不用運算。因此，在數(shù)據(jù)集D的k個子數(shù)據(jù)集的最小置信度中，如果σcdi≥0的總數(shù)k越多，需要參與生成的元素數(shù)減少，算法運行時間也越短。

3 性能分析

3.1 頻繁集的準(zhǔn)確率

為了驗證本算法改進后的效果，在實驗環(huán)境為至強處理器E7、八核、裝有Windows Server 2008操作系統(tǒng)的服務(wù)器上進行以下試驗。利用Apriori算法和TApriori算法在相同的測試數(shù)據(jù)集基礎(chǔ)上產(chǎn)生頻繁集時的準(zhǔn)確率進行比較，Apriori算法采用的最小支持度和最小置信度分別預(yù)先設(shè)定為10%、10%進行驗證，TApriori算法則根據(jù)實際的數(shù)據(jù)情況動態(tài)產(chǎn)生的最小支持度和最小置信度得到各項目頻繁集。如圖1所示，實驗結(jié)果表明，在大于2項頻繁集時，TApriori算法比Apriori算法更快獲得頻繁集，且產(chǎn)生的頻繁集相同。

圖1 準(zhǔn)確率比較

3.2 不同關(guān)聯(lián)規(guī)則使用的時間

在服務(wù)器上分別運行兩種算法在不同事務(wù)規(guī)則的情況下，測試兩種算法的運行時間情況。分別假定事務(wù)數(shù) 5個、10個、100個、1 000個、10 000個，每個事務(wù)都有8個元素。實驗結(jié)果如圖2所示。

圖2 同事務(wù)對應(yīng)的運行時間

實驗結(jié)果表明，在事務(wù)數(shù)量較小的情況下，TApriori算法運行時間與Apriori算法的運行時間相差不大。隨著事務(wù)數(shù)量的增大，TApriori算法運行時間比Apriori算法的運行時間少。

3.3 子數(shù)據(jù)集Dk最小支持度對速度的影響

在數(shù)據(jù)集D的l個子數(shù)據(jù)集的最小支持度中，如果σsdi≥0的總數(shù)n越多，需要參與生成的元素數(shù)減少，算法運行時間也越短。測試結(jié)果如圖3所示。

圖3 子數(shù)據(jù)集Dk最小支持度對速度的影響

上圖是數(shù)據(jù)集D中子數(shù)據(jù)集的個數(shù)l不變，減少σsdi≥0的總數(shù)n的情況下的實驗結(jié)果。試驗結(jié)果表明，隨著總數(shù)n的增大，TApriori算法在運算過程中使用的時間比較穩(wěn)定。

4 應(yīng)用分析

將算法用于軌道交通通信專用系統(tǒng)集中告警系統(tǒng)上，通過對某地鐵線路自2017年12月—2020年3月的告警分析。用TApriori算法進行事務(wù)的構(gòu)建、子數(shù)據(jù)集的構(gòu)建、數(shù)據(jù)集的構(gòu)建，并利用動態(tài)關(guān)聯(lián)規(guī)則分別計算事務(wù)、子數(shù)據(jù)集及數(shù)據(jù)集的最小支持度和最小置信度，對系統(tǒng)故障的分析，生成頻繁集。表1為構(gòu)建產(chǎn)生的事務(wù)集。

表1中事務(wù)列對應(yīng)的事務(wù)序號，元素列對應(yīng)具體事務(wù)中的元素，列表中的每一個字母或字母數(shù)字組合表示集中告警收集到的故障告警，每個事務(wù)中的元素先后順序表示該元素產(chǎn)生的時間前后。如事務(wù)3中，兩個元素A14表示相同時間內(nèi)出現(xiàn)兩次A14故障。事務(wù)列中只有一個元素，表示相同時間內(nèi)當(dāng)且僅當(dāng)出現(xiàn)一次故障。其中，事務(wù)中元素W，X分別表示在2019-07-22 19：47：31同時出現(xiàn)的故障代碼100474和100420故障。元素V表示在2019-07-22 19：47：42出現(xiàn)的故障代碼1003CA故障。其他事務(wù)及元素表示含義類似。

表1 生成的事務(wù)集

通過對以上事務(wù)中元素的時間屬性進行距離計算，構(gòu)建子數(shù)據(jù)集。本實驗中采用的固定時間段為3 d，即連續(xù)三天內(nèi)產(chǎn)生的事務(wù)集構(gòu)建成同一子數(shù)據(jù)組。不在連續(xù)三天之內(nèi)的分別構(gòu)建不同的子數(shù)據(jù)集。不同的子數(shù)據(jù)集通過D后面的數(shù)字表示第幾個子數(shù)據(jù)集，事務(wù)對應(yīng)表 1中的事務(wù)序號。用TApriori算法構(gòu)建的子數(shù)據(jù)集如表2所示。

表2 生成的子數(shù)據(jù)集

最終生成的二元頻繁集如表3所示。

表3 生成的二元頻繁集

通過二元頻繁集分析，可以知道經(jīng)常發(fā)生故障分別為G、D，G、H，A9、A11 和F、G。 通過對發(fā)生的故障實際明細進行排查，由于某站在改造為換乘站后，本站專用電話系統(tǒng)、PIS系統(tǒng)、廣播系統(tǒng)、電源系統(tǒng)、專用無線系統(tǒng)設(shè)備和系統(tǒng)受網(wǎng)絡(luò)不穩(wěn)定的影響，導(dǎo)致各子系統(tǒng)頻繁出現(xiàn)故障。

5 結(jié)束語

在分析集中告警系統(tǒng)收集的告警數(shù)據(jù)具有清晰的時間性和地域性特點，本文將收集的告警信息根據(jù)時間進行分塊，產(chǎn)生子數(shù)據(jù)集，分別計算各子數(shù)據(jù)集的最小支持度和最小置信度，然后計算數(shù)據(jù)集的最小支持度和最小置信度，為集中告警系統(tǒng)數(shù)據(jù)分析處理提供了動態(tài)的關(guān)聯(lián)規(guī)則。通過實際線路的數(shù)據(jù)進行驗證，結(jié)果表明用TApriori算法可以有效挖掘出系統(tǒng)間的故障關(guān)聯(lián)關(guān)系，為系統(tǒng)的故障排除提供了可靠的手段。