加權(quán)增量關(guān)聯(lián)規(guī)則挖掘在通信告警預(yù)測中的應(yīng)用

王 帥，楊秋輝，曾嘉彥，萬 瑩，樊哲寧，張光蘭

(四川大學(xué) 計算機(jī)學(xué)院，成都 610065)(*通信作者電子郵箱yangqiuhui@scu.edu.cn)

0 引言

通信網(wǎng)絡(luò)產(chǎn)生的大量數(shù)據(jù)如指令、告警，其中包含了對故障的檢測預(yù)測十分有用的信息，通過對告警數(shù)據(jù)進(jìn)行分析和挖掘，能夠獲得其中隱含的告警關(guān)聯(lián)規(guī)則，當(dāng)實(shí)時告警數(shù)據(jù)到來時，通過匹配告警關(guān)聯(lián)規(guī)則，可對不久的將來可能發(fā)生的告警進(jìn)行預(yù)測，從而指導(dǎo)網(wǎng)絡(luò)故障管理。

當(dāng)前，通信告警預(yù)測的解決方案主要有：基于神經(jīng)網(wǎng)絡(luò)的預(yù)測方法[1]、基于支持向量機(jī)的方法[2]、基于遺傳算法的預(yù)測方法[3]、基于挖掘的時間序列預(yù)測方法[4-5]等?；谏窠?jīng)網(wǎng)絡(luò)的告警預(yù)測技術(shù)具有較強(qiáng)的非線性映射能力和動態(tài)自適應(yīng)能力；但是存在網(wǎng)絡(luò)訓(xùn)練時間較長、難以選取輸入變量和隱含層數(shù)及節(jié)點(diǎn)數(shù)、訓(xùn)練結(jié)果不穩(wěn)定、容易陷入局部最優(yōu)值等缺點(diǎn)?；谥С窒蛄繖C(jī)(Support Vector Machine, SVM)的方法能在較少的樣本上得到很好的預(yù)測效果；但是復(fù)雜度較高，并且存在過學(xué)習(xí)的問題。基于遺傳算法的告警預(yù)測技術(shù)具有通用、魯棒性強(qiáng)等特點(diǎn)；但是也存在隨機(jī)性大、未成熟收斂、收斂速度低等問題?；陉P(guān)聯(lián)規(guī)則挖掘和序列模式挖掘方法的優(yōu)點(diǎn)是不需要知道網(wǎng)絡(luò)拓?fù)涞年P(guān)系，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，可以通過對歷史告警數(shù)據(jù)進(jìn)行分析，自動發(fā)現(xiàn)新的告警模式，適應(yīng)網(wǎng)絡(luò)的變化，解決網(wǎng)絡(luò)中出現(xiàn)的新問題；不足之處就在構(gòu)建預(yù)測模型時需要多次掃描數(shù)據(jù)庫，且候選項的數(shù)量巨大，導(dǎo)致構(gòu)建效率較低。

本文考慮到不同屬性、級別的告警表示的故障嚴(yán)重程度不一樣，發(fā)出告警的網(wǎng)絡(luò)節(jié)點(diǎn)在整個網(wǎng)絡(luò)拓?fù)渲械牡匚灰膊灰粯?，因此，對通信網(wǎng)絡(luò)告警數(shù)據(jù)進(jìn)行挖掘時，需要綜合告警屬性和節(jié)點(diǎn)位置進(jìn)行權(quán)值分配，從而實(shí)現(xiàn)對告警、故障的預(yù)測，使數(shù)據(jù)挖掘的結(jié)果對故障的分析、排查、修復(fù)更有參考價值。同時，由于告警數(shù)據(jù)庫數(shù)據(jù)不斷增加，帶來兩方面的問題：一是隨時間增加，舊數(shù)據(jù)變得越來越不可信，因此要考慮數(shù)據(jù)新鮮度權(quán)值，適當(dāng)增大新數(shù)據(jù)的權(quán)值比例；二是當(dāng)數(shù)據(jù)增加時，重新挖掘原有告警數(shù)據(jù)庫浪費(fèi)時間、資源，因此，考慮對告警數(shù)據(jù)庫進(jìn)行增量維護(hù)，在利用原有的挖掘基礎(chǔ)上，生成新的關(guān)聯(lián)規(guī)則并刪除舊的關(guān)聯(lián)規(guī)則?；谏鲜鲂枨?，本文提出一種告警權(quán)值確定方法和基于自然序樹(Canonical-order tree, Can-tree)的加權(quán)增量關(guān)聯(lián)規(guī)則挖掘模型。

1 通信網(wǎng)絡(luò)告警預(yù)測過程

加權(quán)增量關(guān)聯(lián)規(guī)則挖掘的通信網(wǎng)絡(luò)告警預(yù)測方案的流程如圖1所示。

圖1 本文方案的流程Fig. 1 Flow chart of the proposed plan

通信網(wǎng)絡(luò)告警預(yù)測要對原始數(shù)據(jù)、增量數(shù)據(jù)、實(shí)時數(shù)據(jù)進(jìn)行冗余去除、丟失處理和告警屬性提取，并使用滑動時間窗將原始和增量告警數(shù)據(jù)庫轉(zhuǎn)換為事務(wù)數(shù)據(jù)庫；結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息、已有知識對告警屬性的認(rèn)知和時序，為告警數(shù)據(jù)分配相應(yīng)的權(quán)值，并建立數(shù)據(jù)表記錄告警項的權(quán)值信息；將告警事務(wù)數(shù)據(jù)庫中的事務(wù)信息壓縮到Can-tree結(jié)構(gòu)中，然后應(yīng)用關(guān)聯(lián)規(guī)則挖掘算法對Can-tree進(jìn)行挖掘，生成告警關(guān)聯(lián)規(guī)則，并將新增的事務(wù)數(shù)據(jù)添加到Can-tree結(jié)構(gòu)中，再使用增量挖掘策略對Can-tree進(jìn)行挖掘，并更新告警關(guān)聯(lián)規(guī)則庫；根據(jù)挖掘獲得的告警關(guān)聯(lián)規(guī)則建立預(yù)測模型，使用模式匹配的方法對未來一段時間會出現(xiàn)的告警進(jìn)行預(yù)測，根據(jù)結(jié)果優(yōu)化策略對預(yù)測結(jié)果進(jìn)行優(yōu)化，進(jìn)行過濾和排序，并將優(yōu)化后的預(yù)測結(jié)果呈現(xiàn)在用戶界面上。本文將工作重心放在告警數(shù)據(jù)權(quán)值的確定、加權(quán)增量關(guān)聯(lián)規(guī)則挖掘以及實(shí)時預(yù)測模型的構(gòu)建上，以下進(jìn)行詳細(xì)闡述。

2 告警權(quán)值確定

本文從三個方面考慮告警權(quán)值：告警級別、告警節(jié)點(diǎn)重要程度和告警數(shù)據(jù)的新鮮程度。假設(shè)告警數(shù)據(jù)的權(quán)值為w，告警級別權(quán)值是wα(0≤wα≤1)，根據(jù)發(fā)出告警節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械闹匾潭荣x予的權(quán)值是wβ(0≤wβ≤1)，告警數(shù)據(jù)的新鮮程度權(quán)值是wγ(0≤wγ≤1)，每種權(quán)值分別對應(yīng)的系數(shù)為α、β、γ(0≤α,β,γ≤1)，則告警權(quán)值：

w=αwα+βwβ+γwγ

(1)

三個權(quán)值系數(shù)α、β、γ表示了告警級別權(quán)值、源節(jié)點(diǎn)重要度權(quán)值和數(shù)據(jù)新鮮度權(quán)值在總權(quán)值中的比重，具體的數(shù)值需要網(wǎng)絡(luò)管理員根據(jù)網(wǎng)絡(luò)的實(shí)際情況和需求進(jìn)行設(shè)置，在本文中分別設(shè)置為0.4、0.3、0.3。

2.1 告警級別的權(quán)值

本文根據(jù)在某通信公司提供的告警數(shù)據(jù)中，涉及了提示告警、次要告警、重要告警和嚴(yán)重告警四種不同的級別，并設(shè)置對應(yīng)的權(quán)值為0.25、0.50、0.75、1.00。

2.2 告警發(fā)生的節(jié)點(diǎn)重要度權(quán)值

參考文獻(xiàn)[6]提出的告警節(jié)點(diǎn)重要度權(quán)值確定方案，本文對節(jié)點(diǎn)的重要度的權(quán)值評估主要從兩方面考慮：

1)根據(jù)告警發(fā)生的節(jié)點(diǎn)分支數(shù)確定。分支數(shù)越大，網(wǎng)絡(luò)上其他節(jié)點(diǎn)與該節(jié)點(diǎn)的業(yè)務(wù)關(guān)聯(lián)越多，因此,節(jié)點(diǎn)分支數(shù)越大，其節(jié)點(diǎn)分配的權(quán)值越高；節(jié)點(diǎn)i的權(quán)值定義為i的分支數(shù)degreei(0

wβi=「degreei/degreemax?

(2)

2)考慮網(wǎng)絡(luò)中的特殊節(jié)點(diǎn)。例如網(wǎng)絡(luò)中某些承擔(dān)關(guān)鍵服務(wù)的節(jié)點(diǎn)、兩個子網(wǎng)的連接節(jié)點(diǎn)等，根據(jù)專家經(jīng)驗為這些節(jié)點(diǎn)指定權(quán)值。

2.3 告警數(shù)據(jù)新鮮度權(quán)值

參考文獻(xiàn)[7]給出告警數(shù)據(jù)新鮮度權(quán)值確定方案，本文設(shè)現(xiàn)有原始通信告警數(shù)據(jù)庫為DB，新增告警數(shù)據(jù)庫為db，告警數(shù)據(jù)新鮮度權(quán)值為wγ。根據(jù)給定的時間單位(如年、季、月)將更新后的數(shù)據(jù)庫DB∪db劃分為n個時間段，那么第j(j=1,2,…,n)個時間段h_j的權(quán)值是：

wγh_j=j/n

(3)

對于歷史數(shù)據(jù)中某一個數(shù)據(jù)項，其權(quán)值等于所在時間段h_j的權(quán)值。一個告警項可能存在多個時間新鮮度權(quán)值，在生成告警關(guān)聯(lián)規(guī)則計算加權(quán)支持度時，需要對告警數(shù)據(jù)新鮮度權(quán)值求均值?，F(xiàn)有告警項alarm，在時間段h1,h2,…,hn分別出現(xiàn)的支持度計數(shù)為S1,S2,…,Sn，那么告警項alarm的新鮮度權(quán)值是：

(4)

3 加權(quán)增量關(guān)聯(lián)規(guī)則挖掘

通過數(shù)據(jù)預(yù)處理和告警權(quán)值確定，獲得了原始告警事務(wù)數(shù)據(jù)庫以及相應(yīng)的權(quán)值信息，利用這些加工后的數(shù)據(jù)和信息，本文在Can-tree結(jié)構(gòu)上進(jìn)行加權(quán)關(guān)聯(lián)規(guī)則挖掘。

3.1 相關(guān)概念

對通信網(wǎng)絡(luò)的告警數(shù)據(jù)庫進(jìn)行挖掘的目標(biāo)，就是找出令人感興趣的加權(quán)關(guān)聯(lián)規(guī)則，然后進(jìn)行應(yīng)用。由于引入了權(quán)值，加權(quán)頻繁項集的子集可能不再是加權(quán)頻繁項集，在加權(quán)關(guān)聯(lián)規(guī)則挖掘過程中并不能像傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘一樣進(jìn)行頻繁項集的挖掘。文獻(xiàn)[8]中首先提出了加權(quán)關(guān)聯(lián)規(guī)則挖掘的MINWAL(O)算法，參照其定義，在加權(quán)關(guān)聯(lián)規(guī)則挖掘中，令I(lǐng)為項的全集，Y為一個q-項集，且q

(5)

如果包含Y的k-項集是頻繁的，那么其最小支持計數(shù)應(yīng)為：

B(Y,k)=「Wminsup×|D|/W(Y,k)?

(6)

其中：Wminsup為最小加權(quán)支持度閾值；|D|是數(shù)據(jù)庫事務(wù)總數(shù)。稱B(Y,k)為項集Y的k-支持期望，令Bmin=min{B(Y,k)|q

Support_count(X)≥Bmin(Y)

(7)

時被稱為加權(quán)潛在q-項集。

3.2 算法改進(jìn)思想

Can-tree中數(shù)據(jù)項的排序是事先指定的，不會受到數(shù)據(jù)更新的影響，也不會受到子節(jié)點(diǎn)支持計數(shù)的影響，如果數(shù)據(jù)項的排序確定了，Can-tree就是唯一的。因此，Can-tree的性質(zhì)使得它非常適用于增量挖掘的，實(shí)現(xiàn)樹結(jié)構(gòu)的重復(fù)利用。本文結(jié)合鄒力鹍等[9]提出的基于Can-tree的改進(jìn)算法，即快速增量式關(guān)聯(lián)規(guī)則挖掘算法(Fast Incremental Algorithm to Find Association Rules, FIAFAR)，將加權(quán)關(guān)聯(lián)規(guī)則的思想實(shí)現(xiàn)到算法中。改進(jìn)思想主要體現(xiàn)在以下幾點(diǎn)：

1)在原來的Can-tree設(shè)計中，由于只能夠從父節(jié)點(diǎn)出發(fā)尋找子節(jié)點(diǎn)，當(dāng)要得到某一項item的條件模式基，需要遍歷整棵樹結(jié)構(gòu)，挖掘效率不高。因此，修改了樹節(jié)點(diǎn)設(shè)計方法，將節(jié)點(diǎn)結(jié)構(gòu)中的child指針修改為parent指針，逆轉(zhuǎn)了指針方向，將樹節(jié)點(diǎn)的遍歷方向改變?yōu)樽缘紫蛏线M(jìn)行，目的是減少剪枝時間和提高條件模式基的生成速度。

2)結(jié)合通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘問題，將數(shù)據(jù)項的排序方式指定為根據(jù)數(shù)據(jù)項節(jié)點(diǎn)重要程度權(quán)值和項字典序組合的排序方式。由于節(jié)點(diǎn)的重要程度權(quán)值由節(jié)點(diǎn)分支數(shù)和專家經(jīng)驗確定，重要程度高的節(jié)點(diǎn)往往與之關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點(diǎn)較多，根據(jù)節(jié)點(diǎn)重要程度權(quán)值排序，當(dāng)節(jié)點(diǎn)權(quán)值一樣時再根據(jù)項的字典序排序，可以達(dá)到使更多的數(shù)據(jù)項共用前綴的目的，使Can-tree的壓縮更緊湊，并且符合Can-tree排序方式不隨挖掘數(shù)據(jù)集變化的要求。

3)FIAFAR對Can-tree改進(jìn)后需要對數(shù)據(jù)庫進(jìn)行兩次全面掃描：第一次掃描是獲取各數(shù)據(jù)項及其支持計數(shù)，按照指定的排序方式對數(shù)據(jù)項進(jìn)行排序并對項頭表進(jìn)行初始化；第二次掃描是將排序后的事務(wù)數(shù)據(jù)信息插入到Can-tree中。由于項頭表中項的排序是已知的，因此項頭表的建立和樹結(jié)構(gòu)的建立可以同時進(jìn)行，在掃描過程中，將已經(jīng)掃描到的事務(wù)數(shù)據(jù)按照指定排序方式排序，將新出現(xiàn)的項作為節(jié)點(diǎn)插入到項頭表和樹中，或?qū)σ殉霈F(xiàn)的項進(jìn)行計數(shù)值更新和指針鏈更新。本文對FIAFAR算法改進(jìn)后，只需要通過一次的數(shù)據(jù)庫掃描就完成Can-tree的構(gòu)建，能減少構(gòu)建樹的時間。

3.3 算法描述

3.3.1 對原始告警數(shù)據(jù)庫的加權(quán)關(guān)聯(lián)規(guī)則挖掘

改進(jìn)后的Can-tree節(jié)點(diǎn)組成如下：

·項目名：item。

·節(jié)點(diǎn)支持計數(shù)值：supcount。

·由當(dāng)前項指向前一項的節(jié)點(diǎn)：parent。

·指向同名節(jié)點(diǎn)指針：back。

構(gòu)建及挖掘Can-tree的步驟如下：

1)輸入原始告警數(shù)據(jù)集，初始化樹T的根節(jié)點(diǎn)為Null。

2)根據(jù)指定的排序方式初始化項頭表T.head，該項頭表的每一個節(jié)點(diǎn)T.head[i]記錄第i項的支持計數(shù)值supcount和節(jié)點(diǎn)鏈信息list。

3)對數(shù)據(jù)庫進(jìn)行掃描，將事務(wù)數(shù)據(jù)按照指定的排序方式進(jìn)行排序，然后按照建立前綴樹的方式插入到T所標(biāo)示的Can-tree中，并更新項頭表中的節(jié)點(diǎn)和信息:現(xiàn)有支持計數(shù)為supc的事務(wù)trans，令事務(wù)trans中的每個數(shù)據(jù)項x，x的前一個數(shù)據(jù)項對應(yīng)節(jié)點(diǎn)為pi，即pi為x在T中對應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)：

①判斷x是否被項頭表T.head記錄，如果沒有被記錄，那么按照排序方式插入對應(yīng)的head[x]節(jié)點(diǎn)到項頭表；

②若x是trans中的第一個數(shù)據(jù)項，則pi為空，head[x].supcount增加supc；

③若x不是trans中的第一個數(shù)據(jù)項，且head[x].list節(jié)點(diǎn)鏈中存在一個節(jié)點(diǎn)N，N.parent=pi,則N.supcount增加supc；否則創(chuàng)建一個新樹節(jié)點(diǎn)N，使其計數(shù)值設(shè)置為supc,并將N鏈接到其父節(jié)點(diǎn)pi，并修改head[x].list節(jié)點(diǎn)鏈，將新建節(jié)點(diǎn)鏈接到具有相同item的節(jié)點(diǎn)；

④令pi=N,為插入下一項作準(zhǔn)備。

4)構(gòu)建完成后，保存一份Can-tree樹的節(jié)點(diǎn)索引信息用于增量挖掘。

5)從項頭表最下面的item開始，沿著head指針鏈構(gòu)造item的條件模式基。

6)遍歷過程中，讀取告警項權(quán)值記錄表，修剪非頻繁節(jié)點(diǎn)。

7)構(gòu)造加權(quán)條件Can-tree。

8)遞歸挖掘每個加權(quán)條件Can-tree，直到Can-tree為空或Can-tree中只有一條路徑，輸出告警加權(quán)頻繁項集，并根據(jù)加權(quán)置信度的概念生成告警關(guān)聯(lián)模式。

9)記錄每個item的挖掘結(jié)果和加權(quán)支持度參數(shù)。

10)整理挖掘結(jié)果，保存到告警關(guān)聯(lián)規(guī)則庫。

3.3.2 對增量Can-tree的加權(quán)關(guān)聯(lián)規(guī)則挖掘

Can-tree中節(jié)點(diǎn)的順序不會受到數(shù)據(jù)量變化或最小加權(quán)支持度閾值變化的影響，因此，當(dāng)有新的增量告警數(shù)據(jù)庫db需要挖掘時，按照以下步驟執(zhí)行。

1)輸入增量告警數(shù)據(jù)集，對增量告警數(shù)據(jù)集進(jìn)行預(yù)處理，并計算各數(shù)據(jù)項的權(quán)值。

2)獲取上次挖掘的Can-tree節(jié)點(diǎn)索引信息，恢復(fù)上次挖掘建立的未修剪的Can-tree。

3)遍歷新增告警事務(wù)數(shù)據(jù)集，按照指定的排序方法對事務(wù)數(shù)據(jù)中的項進(jìn)行排序，并根據(jù)構(gòu)建Can-tree算法將新數(shù)據(jù)插入到樹中，對Can-tree中的數(shù)據(jù)進(jìn)行增量更新。

4)判斷前次挖掘和本次增量挖掘的最小加權(quán)支持度是否發(fā)生變化：

①若發(fā)生變化，對整個Can-tree重新挖掘，并更新告警關(guān)聯(lián)規(guī)則庫。

②若未發(fā)生變化，則利用上次挖掘的關(guān)聯(lián)規(guī)則結(jié)果記錄進(jìn)行增量挖掘。自下而上遍歷項頭表中的item，與上次挖掘的項頭表進(jìn)行比較，根據(jù)item的計數(shù)值是否發(fā)生變化，分為兩種情況：發(fā)生變化(包括上一次挖掘中item計數(shù)值為0的情況)，那么重新構(gòu)造當(dāng)前item的條件模式基，重新挖掘包含item的頻繁項集，并更新規(guī)則庫；未發(fā)生變化，說明增量數(shù)據(jù)集中沒再次出現(xiàn)數(shù)據(jù)item，那么只要對上一次挖掘中包含item的關(guān)聯(lián)規(guī)則結(jié)果進(jìn)行加權(quán)支持度和加權(quán)置信度的更新，并淘汰已經(jīng)低于加權(quán)支持度閾值和置信度閾值的規(guī)則，并更新規(guī)則庫。

5)保存當(dāng)前挖掘建立的Can-tree結(jié)構(gòu)和各item對應(yīng)的結(jié)果集合，用于下次的增量挖掘。

對增量告警數(shù)據(jù)庫的挖掘，增量策略主要體現(xiàn)在兩方面：一是利用上次挖掘建立的Can-tree樹結(jié)構(gòu)，通過已有信息重建Can-tree樹，節(jié)省了再次掃描原始告警數(shù)據(jù)庫的時間；二是在生成加權(quán)關(guān)聯(lián)規(guī)則過程中，利用了上一次挖掘的結(jié)果集合，對沒有發(fā)生支持度計數(shù)改變的item的挖掘結(jié)果不需要重新挖掘，只需再次計算其加權(quán)支持度和置信度是否滿足閾值即可。通過重復(fù)利用上一次挖掘的信息，算法提高了挖掘效率，節(jié)省了挖掘時間。

表1 告警數(shù)據(jù)樣本Tab. 1 Alarm data samples

4 實(shí)時告警預(yù)測

通過對告警事務(wù)數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則挖掘，可獲得滿足用戶參數(shù)的告警關(guān)聯(lián)規(guī)則。告警預(yù)測結(jié)合實(shí)時告警數(shù)據(jù)和告警關(guān)聯(lián)規(guī)則，進(jìn)行規(guī)則匹配，對不久的將來可能發(fā)生的告警進(jìn)行預(yù)測。

4.1 實(shí)時告警數(shù)據(jù)預(yù)處理

在告警預(yù)測之前，需要對實(shí)時告警數(shù)據(jù)進(jìn)行預(yù)處理。相比歷史告警數(shù)據(jù)的預(yù)處理，由于不需要對實(shí)時告警數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，因此預(yù)處理步驟較為簡單，不需要結(jié)果滑動時間窗口的處理和權(quán)值計算，只需要對告警數(shù)據(jù)進(jìn)行清洗即可。

4.2 實(shí)時告警預(yù)測

在一定的時間窗口寬度width內(nèi)，如果告警集合CausationSet出現(xiàn)了，那么告警集合CausationSet在下一個時間窗口內(nèi)出現(xiàn)的可能性為b。因此，在實(shí)時告警預(yù)測中，如果在同一個時間窗口內(nèi)的實(shí)時告警數(shù)據(jù)能夠全部匹配CausationSet中的每一個項，即CausationSet中的每一個項都在同一個實(shí)時告警時間窗口內(nèi)出現(xiàn)了，那么就可以推出在接下來的時間內(nèi)，CausationSet會出現(xiàn)，且概率為b。

實(shí)時告警預(yù)測算法主要步驟描述如下：

1)讀取實(shí)時告警數(shù)據(jù)，對實(shí)時告警數(shù)據(jù)進(jìn)行預(yù)處理。

2)從關(guān)聯(lián)規(guī)則庫中讀取告警關(guān)聯(lián)規(guī)則，并存儲到相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。

3)設(shè)置一個窗口寬度為width的時間窗口，時間窗口是一個長度為width的時間區(qū)間[StartTime,EndTime]，將讀取的第一個告警(E0,T0)的時間T0作為時間窗口的開始時間，即時間窗口區(qū)間為[T0,T0+width]，依次讀取告警實(shí)時數(shù)據(jù)，將告警數(shù)據(jù)放入時間窗口內(nèi)，直至下一個告警超出時間窗口范圍為止。

4)遍歷告警關(guān)聯(lián)規(guī)則，將時間窗口內(nèi)所有的告警數(shù)據(jù)項集合s依次與關(guān)聯(lián)規(guī)則的前件項進(jìn)行匹配，判斷關(guān)聯(lián)規(guī)則前件中的全部項是否在集合s中都出現(xiàn)了，如果是，輸出對應(yīng)的預(yù)測結(jié)果；否則遍歷下一條規(guī)則，再次進(jìn)行匹配，直至遍歷完所有的規(guī)則。

5)將時間窗口進(jìn)行滑動，讀入一個新數(shù)據(jù)(Ei,Ti)，將新數(shù)據(jù)的時間戳Ti設(shè)置為EndTime，那么窗口的StartTime=EndTime-width=Ti-width，此時窗口區(qū)間為[Ti,Ti+width]，清除窗口數(shù)據(jù)結(jié)構(gòu)內(nèi)超時的告警數(shù)據(jù)，然后將StartTime重新設(shè)置為窗口內(nèi)時間最早的告警(Ek,Tk)時間戳Tk，更新窗口的EndTime獲得新的時間窗[Tk,Tk+width]。然后嘗試再次讀入新的實(shí)時告警數(shù)據(jù)，直至下一個新的告警數(shù)據(jù)超出時間窗區(qū)間范圍為止，重復(fù)步驟4)～5)，直至所有的實(shí)時告警數(shù)據(jù)處理完畢。

6)處理預(yù)測結(jié)果集合，對預(yù)測的重復(fù)結(jié)果進(jìn)行過濾，然后按照加權(quán)支持度、加權(quán)置信度參數(shù)進(jìn)行排序并展現(xiàn)到用戶界面，算法終止。

5 實(shí)驗分析

本文以某通信公司提供的通信網(wǎng)絡(luò)告警數(shù)據(jù)為樣本，表1展示了告警數(shù)據(jù)樣本，對告警數(shù)據(jù)的特點(diǎn)進(jìn)行分析，按照告警數(shù)據(jù)格式和分布規(guī)律進(jìn)行數(shù)據(jù)仿真，仿真時長為2個多月，產(chǎn)出約20萬條告警，包括了220個網(wǎng)絡(luò)節(jié)點(diǎn)的296個不同的告警類型。

表2 告警級別數(shù)量表Tab. 2 Alarm numbers of each alarm level

本文使用數(shù)據(jù)挖掘領(lǐng)域中常用的模型性能度量標(biāo)準(zhǔn)對網(wǎng)絡(luò)告警預(yù)測結(jié)果進(jìn)行評估，包括了告警預(yù)測的準(zhǔn)確率(Precision)[10]、召回率(Recall)[11]和F-值(F-Measure)等指標(biāo)，使用響應(yīng)時間(Response time)[12-13]作為告警預(yù)測效率的評價指標(biāo)，對網(wǎng)絡(luò)告警預(yù)測方案進(jìn)行綜合的評估。另外，對于增量挖掘算法的時間效率，使用算法的執(zhí)行時間進(jìn)行衡量。

5.1 關(guān)聯(lián)規(guī)則挖掘算法的性能比較實(shí)驗

實(shí)驗數(shù)據(jù)包括兩部分：一部分是原始告警事務(wù)數(shù)據(jù)集DB,另一部分是增量告警事務(wù)數(shù)據(jù)db，原始告警數(shù)據(jù)和增量告警數(shù)據(jù)共同組成更新告警事務(wù)數(shù)據(jù)集，即DB∪db。設(shè)置支持度閾值為0.3，置信度閾值為0.7。

5.1.1 與原始CAN-tree算法、FP-growth算法的比較

從圖2～3可看出：對單一數(shù)據(jù)集而言，本文方法時間效率介于Can-tree算法和FP-growth算法之間，相對于改進(jìn)前的原始Can-tree算法，明顯提高了挖掘效率。

圖2 原始告警數(shù)據(jù)集的建樹時間比較Fig. 2 Can-tree construction time comparison of original alarm data set

圖3 原始告警數(shù)據(jù)庫的挖掘時間比較Fig. 3 Mining time comparison of original alarm data set

從圖4～5可看出：本文方法在對更新告警數(shù)據(jù)庫進(jìn)行挖掘時，執(zhí)行時間最低，挖掘地效率最高。從長遠(yuǎn)的目標(biāo)來看，增量數(shù)據(jù)集越頻繁地加入數(shù)據(jù)庫，增量挖掘算法的時間效率越高，能夠有效節(jié)省資源。

5.1.2 與加權(quán)關(guān)聯(lián)規(guī)則算法MINWAL(O)的比較

從圖6～7可看出：本文方法和MINWAL(O)隨著最小加權(quán)支持度升高(加權(quán)頻繁項集變少)，執(zhí)行時間快速下降然后逐漸趨于平衡，而本文方法的變化趨勢比MINWAL(O)平緩得多；隨著數(shù)據(jù)庫的增大，本文方法和MINWAL(O)的執(zhí)行時間變長，本文方法增長較為緩慢，并且時間效率上優(yōu)于MINWAL(O)。因此，本文方法具有較好的挖掘效率和伸縮性。

圖4 更新告警數(shù)據(jù)庫的建樹時間比較Fig. 4 Can-tree construction time comparison ofupdated alarm data set

圖5 更新告警數(shù)據(jù)庫的挖掘時間比較Fig. 5 Mining time comparison of updated alarm data set

圖6 不同最小加權(quán)支持度下執(zhí)行時間比較Fig. 6 Execution time comparison with different minimum weighted support

圖7 不同數(shù)據(jù)量的執(zhí)行時間比較Fig. 7 Execution time comparison with different amount of data

5.2 告警測試方案的有效性實(shí)驗

考慮實(shí)際的告警數(shù)據(jù)產(chǎn)生速率以及預(yù)測結(jié)果的輸出時間，將告警數(shù)據(jù)的設(shè)置告警時間窗口大小為30 min，比較本文方法在不同的加權(quán)支持度閾值下的挖掘效果如表3所示。

表3表征本文方法在不同加權(quán)支持度閾值情況下告警預(yù)測的表現(xiàn)?？梢钥闯觯S著支持度閾值降低，準(zhǔn)確率緩慢上升后逐漸下降，這是因為隨著加權(quán)支持度閾值的降低，挖掘出的告警關(guān)聯(lián)規(guī)則越多，當(dāng)加權(quán)支持度閾值過高時，由于挖掘出的告警關(guān)聯(lián)規(guī)則太少，較難進(jìn)行有效預(yù)測；當(dāng)加權(quán)支持度閾值過低時，挖掘出的告警關(guān)聯(lián)規(guī)則大幅增加，導(dǎo)致預(yù)測的準(zhǔn)確率降低。召回率隨著加權(quán)支持度閾值的減小而增大，這是因為加權(quán)支持度閾值越小，挖掘出的告警關(guān)聯(lián)規(guī)則模式越多，正確預(yù)測的告警數(shù)量也越多。對于算法預(yù)測的響應(yīng)時間，可以看到，隨著加權(quán)支持度閾值降低預(yù)測響應(yīng)時間逐漸增加，這是因為支持度閾值越小，生成的告警關(guān)聯(lián)規(guī)則就越多，實(shí)時告警與關(guān)聯(lián)規(guī)則匹配需要的時間就越多。但告警預(yù)測時間一直保持在秒級范圍內(nèi)，可以滿足用戶快速獲取告警預(yù)測信息的需求。

表3 本文方法在不同的加權(quán)支持度閾值下的挖掘效果對比Tab. 3 Mining effects of proposed algorithm with different weighted support thresholds

6 結(jié)語

為提高通信網(wǎng)絡(luò)告警預(yù)測的準(zhǔn)確度、縮短預(yù)測模型的訓(xùn)練時間，本文提出了基于Can-tree的加權(quán)增量挖掘的告警預(yù)測方案。實(shí)驗結(jié)果表明本文方案能有效地預(yù)測網(wǎng)絡(luò)告警，并通過本文提出的權(quán)值確定方案提升告警預(yù)測的價值，在較短的時間內(nèi)完成挖掘和預(yù)測工作，使網(wǎng)絡(luò)管理員能夠提前作好保護(hù)、預(yù)防等措施，減少網(wǎng)絡(luò)故障引起的損失，提高網(wǎng)絡(luò)的可靠性和穩(wěn)定性。本文方案還存在一些不足之處，未來的研究方向和工作包括但不限于：告警權(quán)值的考慮還可以更全面；使用滑動時間窗口處理告警數(shù)據(jù)庫時，可以添加對告警數(shù)據(jù)的自適應(yīng)調(diào)整的窗口寬度、步長策略；在告警預(yù)測階段，考慮加入機(jī)器學(xué)習(xí)的算法，提高預(yù)測的準(zhǔn)確率和可信度。