加權增量關聯規則挖掘在通信告警預測中的應用

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

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

0 引言

通信網絡產生的大量數據如指令、告警，其中包含了對故障的檢測預測十分有用的信息，通過對告警數據進行分析和挖掘，能夠獲得其中隱含的告警關聯規則，當實時告警數據到來時，通過匹配告警關聯規則，可對不久的將來可能發生的告警進行預測，從而指導網絡故障管理。

當前，通信告警預測的解決方案主要有：基于神經網絡的預測方法[1]、基于支持向量機的方法[2]、基于遺傳算法的預測方法[3]、基于挖掘的時間序列預測方法[4-5]等。基于神經網絡的告警預測技術具有較強的非線性映射能力和動態自適應能力；但是存在網絡訓練時間較長、難以選取輸入變量和隱含層數及節點數、訓練結果不穩定、容易陷入局部最優值等缺點。基于支持向量機(Support Vector Machine, SVM)的方法能在較少的樣本上得到很好的預測效果；但是復雜度較高，并且存在過學習的問題。基于遺傳算法的告警預測技術具有通用、魯棒性強等特點；但是也存在隨機性大、未成熟收斂、收斂速度低等問題。基于關聯規則挖掘和序列模式挖掘方法的優點是不需要知道網絡拓撲的關系，當網絡拓撲結構發生變化時，可以通過對歷史告警數據進行分析，自動發現新的告警模式，適應網絡的變化，解決網絡中出現的新問題；不足之處就在構建預測模型時需要多次掃描數據庫，且候選項的數量巨大，導致構建效率較低。

本文考慮到不同屬性、級別的告警表示的故障嚴重程度不一樣，發出告警的網絡節點在整個網絡拓撲中的地位也不一樣，因此，對通信網絡告警數據進行挖掘時，需要綜合告警屬性和節點位置進行權值分配，從而實現對告警、故障的預測，使數據挖掘的結果對故障的分析、排查、修復更有參考價值。同時，由于告警數據庫數據不斷增加，帶來兩方面的問題：一是隨時間增加，舊數據變得越來越不可信，因此要考慮數據新鮮度權值，適當增大新數據的權值比例；二是當數據增加時，重新挖掘原有告警數據庫浪費時間、資源，因此，考慮對告警數據庫進行增量維護，在利用原有的挖掘基礎上，生成新的關聯規則并刪除舊的關聯規則。基于上述需求，本文提出一種告警權值確定方法和基于自然序樹(Canonical-order tree, Can-tree)的加權增量關聯規則挖掘模型。

1 通信網絡告警預測過程

加權增量關聯規則挖掘的通信網絡告警預測方案的流程如圖1所示。

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

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

2 告警權值確定

本文從三個方面考慮告警權值：告警級別、告警節點重要程度和告警數據的新鮮程度。假設告警數據的權值為w，告警級別權值是wα(0≤wα≤1)，根據發出告警節點在網絡拓撲中的重要程度賦予的權值是wβ(0≤wβ≤1)，告警數據的新鮮程度權值是wγ(0≤wγ≤1)，每種權值分別對應的系數為α、β、γ(0≤α,β,γ≤1)，則告警權值：

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

(1)

三個權值系數α、β、γ表示了告警級別權值、源節點重要度權值和數據新鮮度權值在總權值中的比重，具體的數值需要網絡管理員根據網絡的實際情況和需求進行設置，在本文中分別設置為0.4、0.3、0.3。

2.1 告警級別的權值

本文根據在某通信公司提供的告警數據中，涉及了提示告警、次要告警、重要告警和嚴重告警四種不同的級別，并設置對應的權值為0.25、0.50、0.75、1.00。

2.2 告警發生的節點重要度權值

參考文獻[6]提出的告警節點重要度權值確定方案，本文對節點的重要度的權值評估主要從兩方面考慮：

1)根據告警發生的節點分支數確定。分支數越大，網絡上其他節點與該節點的業務關聯越多，因此,節點分支數越大，其節點分配的權值越高；節點i的權值定義為i的分支數degreei(0

wβi=「degreei/degreemax?

(2)

2)考慮網絡中的特殊節點。例如網絡中某些承擔關鍵服務的節點、兩個子網的連接節點等，根據專家經驗為這些節點指定權值。

2.3 告警數據新鮮度權值

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

wγh_j=j/n

(3)

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

(4)

3 加權增量關聯規則挖掘

通過數據預處理和告警權值確定，獲得了原始告警事務數據庫以及相應的權值信息，利用這些加工后的數據和信息，本文在Can-tree結構上進行加權關聯規則挖掘。

3.1 相關概念

對通信網絡的告警數據庫進行挖掘的目標，就是找出令人感興趣的加權關聯規則，然后進行應用。由于引入了權值，加權頻繁項集的子集可能不再是加權頻繁項集，在加權關聯規則挖掘過程中并不能像傳統的關聯規則挖掘一樣進行頻繁項集的挖掘。文獻[8]中首先提出了加權關聯規則挖掘的MINWAL(O)算法，參照其定義，在加權關聯規則挖掘中，令I為項的全集，Y為一個q-項集，且q

(5)

如果包含Y的k-項集是頻繁的，那么其最小支持計數應為：

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

(6)

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

Support_count(X)≥Bmin(Y)

(7)

時被稱為加權潛在q-項集。

3.2 算法改進思想

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

1)在原來的Can-tree設計中，由于只能夠從父節點出發尋找子節點，當要得到某一項item的條件模式基，需要遍歷整棵樹結構，挖掘效率不高。因此，修改了樹節點設計方法，將節點結構中的child指針修改為parent指針，逆轉了指針方向，將樹節點的遍歷方向改變為自底向上進行，目的是減少剪枝時間和提高條件模式基的生成速度。

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

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

3.3 算法描述

3.3.1 對原始告警數據庫的加權關聯規則挖掘

改進后的Can-tree節點組成如下：

·項目名：item。

·節點支持計數值：supcount。

·由當前項指向前一項的節點：parent。

·指向同名節點指針：back。

構建及挖掘Can-tree的步驟如下：

1)輸入原始告警數據集，初始化樹T的根節點為Null。

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

3)對數據庫進行掃描，將事務數據按照指定的排序方式進行排序，然后按照建立前綴樹的方式插入到T所標示的Can-tree中，并更新項頭表中的節點和信息:現有支持計數為supc的事務trans，令事務trans中的每個數據項x，x的前一個數據項對應節點為pi，即pi為x在T中對應節點的父節點：

①判斷x是否被項頭表T.head記錄，如果沒有被記錄，那么按照排序方式插入對應的head[x]節點到項頭表；

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

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

④令pi=N,為插入下一項作準備。

4)構建完成后，保存一份Can-tree樹的節點索引信息用于增量挖掘。

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

6)遍歷過程中，讀取告警項權值記錄表，修剪非頻繁節點。

7)構造加權條件Can-tree。

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

9)記錄每個item的挖掘結果和加權支持度參數。

10)整理挖掘結果，保存到告警關聯規則庫。

3.3.2 對增量Can-tree的加權關聯規則挖掘

Can-tree中節點的順序不會受到數據量變化或最小加權支持度閾值變化的影響，因此，當有新的增量告警數據庫db需要挖掘時，按照以下步驟執行。

1)輸入增量告警數據集，對增量告警數據集進行預處理，并計算各數據項的權值。

2)獲取上次挖掘的Can-tree節點索引信息，恢復上次挖掘建立的未修剪的Can-tree。

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

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

①若發生變化，對整個Can-tree重新挖掘，并更新告警關聯規則庫。

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

5)保存當前挖掘建立的Can-tree結構和各item對應的結果集合，用于下次的增量挖掘。

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

表1 告警數據樣本Tab. 1 Alarm data samples

4 實時告警預測

通過對告警事務數據庫的關聯規則挖掘，可獲得滿足用戶參數的告警關聯規則。告警預測結合實時告警數據和告警關聯規則，進行規則匹配，對不久的將來可能發生的告警進行預測。

4.1 實時告警數據預處理

在告警預測之前，需要對實時告警數據進行預處理。相比歷史告警數據的預處理，由于不需要對實時告警數據進行關聯規則挖掘，因此預處理步驟較為簡單，不需要結果滑動時間窗口的處理和權值計算，只需要對告警數據進行清洗即可。

4.2 實時告警預測

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

實時告警預測算法主要步驟描述如下：

1)讀取實時告警數據，對實時告警數據進行預處理。

2)從關聯規則庫中讀取告警關聯規則，并存儲到相應的數據結構中。

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

4)遍歷告警關聯規則，將時間窗口內所有的告警數據項集合s依次與關聯規則的前件項進行匹配，判斷關聯規則前件中的全部項是否在集合s中都出現了，如果是，輸出對應的預測結果；否則遍歷下一條規則，再次進行匹配，直至遍歷完所有的規則。

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

6)處理預測結果集合，對預測的重復結果進行過濾，然后按照加權支持度、加權置信度參數進行排序并展現到用戶界面，算法終止。

5 實驗分析

本文以某通信公司提供的通信網絡告警數據為樣本，表1展示了告警數據樣本，對告警數據的特點進行分析，按照告警數據格式和分布規律進行數據仿真，仿真時長為2個多月，產出約20萬條告警，包括了220個網絡節點的296個不同的告警類型。

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

本文使用數據挖掘領域中常用的模型性能度量標準對網絡告警預測結果進行評估，包括了告警預測的準確率(Precision)[10]、召回率(Recall)[11]和F-值(F-Measure)等指標，使用響應時間(Response time)[12-13]作為告警預測效率的評價指標，對網絡告警預測方案進行綜合的評估。另外，對于增量挖掘算法的時間效率，使用算法的執行時間進行衡量。

5.1 關聯規則挖掘算法的性能比較實驗

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

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

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

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

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

從圖4～5可看出：本文方法在對更新告警數據庫進行挖掘時，執行時間最低，挖掘地效率最高。從長遠的目標來看，增量數據集越頻繁地加入數據庫，增量挖掘算法的時間效率越高，能夠有效節省資源。

5.1.2 與加權關聯規則算法MINWAL(O)的比較

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

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

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

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

圖7 不同數據量的執行時間比較Fig. 7 Execution time comparison with different amount of data

5.2 告警測試方案的有效性實驗

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

表3表征本文方法在不同加權支持度閾值情況下告警預測的表現。可以看出，隨著支持度閾值降低，準確率緩慢上升后逐漸下降，這是因為隨著加權支持度閾值的降低，挖掘出的告警關聯規則越多，當加權支持度閾值過高時，由于挖掘出的告警關聯規則太少，較難進行有效預測；當加權支持度閾值過低時，挖掘出的告警關聯規則大幅增加，導致預測的準確率降低。召回率隨著加權支持度閾值的減小而增大，這是因為加權支持度閾值越小，挖掘出的告警關聯規則模式越多，正確預測的告警數量也越多。對于算法預測的響應時間，可以看到，隨著加權支持度閾值降低預測響應時間逐漸增加，這是因為支持度閾值越小，生成的告警關聯規則就越多，實時告警與關聯規則匹配需要的時間就越多。但告警預測時間一直保持在秒級范圍內，可以滿足用戶快速獲取告警預測信息的需求。

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

6 結語

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