許鴻飛+于然+李雪梅+寇曉溪+趙子蘭+金燊+楊清海

摘 要： 數(shù)據(jù)完整性是網(wǎng)絡告警信息的基本質量屬性，是進一步進行網(wǎng)絡告警故障分析的基礎。然而在現(xiàn)實中，網(wǎng)管系統(tǒng)可能接收到信息缺失的網(wǎng)元告警信息，從而影響網(wǎng)絡故障定位的準確性。分別使用決策樹算法、窗關聯(lián)規(guī)則挖掘（WARM）算法和相似度算法對網(wǎng)絡告警信息中缺失的屬性進行數(shù)據(jù)填充，并在國家電網(wǎng)信息網(wǎng)絡和通信網(wǎng)絡共存的場景下研究分析上述算法對聯(lián)合故障定位性能的提升。實驗結果表明，在該場景下決策樹算法有更高的聯(lián)合故障定位準確率。

關鍵詞： 網(wǎng)絡告警故障； 決策樹算法； WARM算法； 相似度算法； 故障聯(lián)合定位

中圖分類號： TN915.08?34 文獻標識碼： A 文章編號： 1004?373X（2017）19?0062?05

Research on alarm data information filling algorithm for fault joint location

XU Hongfei1， YU Ran1， LI Xuemei1， KOU Xiaoxi1， ZHAO Zilan1， JIN Shen1， YANG Qinghai2

（1. Information and Telecommunication Branch Company， State Grid Jibei Electric Power Co.， Ltd.， Beijing 100053， China；

2. Xidian University， Xian 710071， China）

Abstract： The data integrity is the basic quality attribute of network alarm information and the foundation for further network alarm fault analysis. However， the network management system in reality can receive the network element alarm information with information loss， which influences the location accuracy of network fault. The decision tree algorithm， WARM algorithm and similarity algorithm are respectively used to perform data filling for the missing attribute in network alarm information. The performance promotion of the fault joint location with above algorithms is studied in the scenario of the co?existence of State Grid information network and communication network. The experimental results show that the decision tree algorithm has higher accuracy of fault joint location in the above scenario.

Keywords： network alarm fault； decision tree algorithm； WARM algorithm； similarity algorithm； fault joint location

0 引 言

當前國家電網(wǎng)數(shù)據(jù)網(wǎng)絡架構中，通信網(wǎng)絡與信息網(wǎng)絡分別通過兩套不同的網(wǎng)絡管理系統(tǒng)實現(xiàn)網(wǎng)絡運維，然而通信網(wǎng)絡中的故障往往會關聯(lián)引發(fā)信息網(wǎng)絡中的故障。故障聯(lián)合定位分析能夠從信息網(wǎng)絡關聯(lián)故障準確定位到通信網(wǎng)絡的根源故障，從而提高國家電網(wǎng)信息通信網(wǎng)絡的整體運維效率。故障聯(lián)合定位依賴于完整一致的網(wǎng)絡告警信息，然而在現(xiàn)實中由于網(wǎng)絡繼發(fā)故障等種種原因，網(wǎng)管系統(tǒng)可能收集到信息缺失的網(wǎng)元告警信息。網(wǎng)絡告警信息的缺失會導致網(wǎng)絡管理性能下降，降低網(wǎng)絡故障定位的準確性[1]。因此，對告警缺失信息的有效估計和填充是提高國家電網(wǎng)信息通信網(wǎng)的整體運維效率亟需解決的問題。

數(shù)據(jù)填充[2]是指采用一定的方法對數(shù)據(jù)資料的缺失值進行合理的估計。當前在各個領域已經(jīng)展開對數(shù)據(jù)填充算法的研究，但是仍缺乏在網(wǎng)絡故障聯(lián)合定位場景下的應用以及性能分析。文獻[3]采用貝葉斯網(wǎng)絡進行網(wǎng)絡聯(lián)合故障定位，然而該研究并沒有考慮告警信息的缺失問題，以及告警信息缺失導致的故障定位不準確問題。文獻[4]基于神經(jīng)網(wǎng)絡進行網(wǎng)絡聯(lián)合故障定位，但該方法需要經(jīng)歷較長時間的模型訓練才能獲得貼近實際情況的模型。告警信息中的數(shù)據(jù)缺失會導致最終訓練得到的模型誤差很大，從而使定位產生較大的偏差。文獻[5]中提出基于模型的故障定位算法，其主要優(yōu)點是在節(jié)點無法確定先驗概率的情況下仍可以定位網(wǎng)絡故障，然而告警信息中的數(shù)據(jù)缺失將會導致產生故障的節(jié)點判斷錯誤，從而無法準確定位根源故障。

網(wǎng)絡告警信息的完整性是實現(xiàn)高效網(wǎng)絡運維的基礎，本文針對國家電網(wǎng)信息通信網(wǎng)絡告警數(shù)據(jù)缺失問題進行了分析研究。首先，分析評估了已有的數(shù)據(jù)填充方法[6?8]，并采用決策樹方法實現(xiàn)缺失告警數(shù)據(jù)的填充。其次，介紹了面向故障聯(lián)合定位的二分圖故障關聯(lián)模型以及聯(lián)合故障定位方法。最后，在實際網(wǎng)絡應用場景中進行仿真實驗并比較了上述算法在故障聯(lián)合定位場景下的故障診斷率。仿真結果表明，通過決策樹算法[9?11]進行告警數(shù)據(jù)信息填充的方法具有較高的故障診斷率。

1 問題背景

網(wǎng)絡故障診斷是通過分析監(jiān)測設備向網(wǎng)絡運維系統(tǒng)發(fā)出網(wǎng)絡告警數(shù)據(jù)進行網(wǎng)絡故障的判斷。例如，通過分析告警數(shù)據(jù)，確定告警與故障之間的關聯(lián)關系以及告警的屬性之間的關聯(lián)關系，從而判斷網(wǎng)絡故障類型以及位置。國家電網(wǎng)通信網(wǎng)絡與信息網(wǎng)絡中常見的告警屬性數(shù)據(jù)格式如圖1所示。告警信息包含多個屬性項，如告警級別、告警類型等。然而在現(xiàn)實中，網(wǎng)管系統(tǒng)可能接收到某些屬性項缺失的告警信息，例如缺失告警級別屬性。當告警屬性缺失時會導致無法進行準確的故障診斷。

在本文中，首先根據(jù)告警屬性之間的關聯(lián)關系對缺失屬性項進行填充，形成完整的告警信息。其次，基于填充完整的告警信息進行網(wǎng)絡故障診斷。

2 缺失告警信息填充

在本文中主要分析評估決策樹算法、WARM（Window Association Rule Mining）算法[2]以及相似度算法[12]三種數(shù)據(jù)填充算法的性能。

2.1 決策樹算法

本文提出使用ID3分類算法[6]對缺失告警屬性進行數(shù)據(jù)填充。該方法包含對關鍵屬性進行特征選擇以及生成決策樹兩步。實現(xiàn)步驟如下：

輸入：完整告警信息數(shù)據(jù)集[D]，特征集[A]即關鍵告警屬性集，閾值[ε]

輸出：決策樹[U]

步驟1：若[D]中所有實例屬于同一類[El]，其中[l=1，2，…，L]，[L]為告警數(shù)據(jù)集中類的總數(shù)，則[T]為單節(jié)點樹，并將類[El]作為該節(jié)點的類標記，返回[U]；

步驟2：若[A=?]，則[U]為單節(jié)點樹，并將[D]中實例數(shù)最大的類[El]作為該節(jié)點的類標記，返回[U]；

步驟3：否則，計算[A]中各特征對[D]的信息增益[6]，如式（1），并選擇信息增益最大的特征[Aq，]其中[q=1，2，…，Q]，[Q]為特征集中特征的個數(shù)；

[g（D，A）=H（D）-HDA] （1）

式中：[H（D）]表示[D]的經(jīng)驗熵；[HDA]表示[A]對[D]的經(jīng)驗條件熵。

步驟4：如果[Aq]的信息增益小于閾值[ε，]則置[U]為單節(jié)點樹，并將[D]中實例數(shù)最大的類[El]作為該節(jié)點的類標記，返回[U]；

步驟5：否則，對[Aq]的每一可能值[as，]其中[s=1，2，…，S，][S]表示[Aq]所有可能值的個數(shù)，依[Aq=as]將[D]分割為若干非空子集[Ds，]將[Ds]中實例數(shù)最大的類作為標記，構建子節(jié)點，由節(jié)點及其子節(jié)點構成樹[U，]返回[U]；

步驟6：對第[s]個子節(jié)點，以[Ds]為訓練集，以[A-{Aq}]為特征集，遞歸地調用步驟1～步驟5，得到子樹[Us，]返回[Us]。

最后，以每個葉子節(jié)點為一類對缺失告警信息的告警屬性進行填充。

2.2 WARM算法

WARM算法是當某一節(jié)點的數(shù)據(jù)存在缺失時，該算法首先找到與之關聯(lián)的一個節(jié)點，并用關聯(lián)節(jié)點的值填充其缺失值。本文根據(jù)每條告警信息之間的相關系數(shù)來填補缺失數(shù)據(jù)的告警信息的告警屬性。本文采用皮爾遜相關系數(shù)求各個告警信息間的相關性。

信息通信網(wǎng)絡中的告警信息矩陣[X]表示如下：

[X=x11x12…x1Mx21x22…x2M????xN1xN2…xNM]

式中：[N]代表信息通信網(wǎng)中產生的告警信息的條數(shù)；[M]表示在告警屬性不丟失的情況下每條告警信息的告警屬性的個數(shù)；[xnm]表示第[n]條告警信息的第[m]個告警屬性，其中[n=1，2，…，N；][m=1，2，…，M]。

任意告警信息[n]和[n]之間的相關系數(shù)計算公式如下：

[r（n，n）=m=1Mxnm-xnxnm-xnm=1Mxnm-xn2m=1Mxnm-xn2] （2）

式中：[n≠n；][xn]表示告警信息[n]的平均值；[r（n，n）∈[-1，1]，]反映兩條告警信息之間的相關性強弱。定義[r（n，n）>0.8]時為強相關，當[r（n，n）<0.3]時為弱相關，其他的情況為中度相關。在實現(xiàn)時使用與告警關聯(lián)性強的完整告警信息的屬性值對缺失告警中的屬性值進行填充。

2.3 相似度算法

基于閔可夫斯基距離[13]定義“相似度度量”，距離越大則相似度越小。假設第[n]條告警信息為[xn=（xn1；xn2；…；xnM）]，閔可夫斯基距離表示如下：

[dxn，xn=m=1Mxnm-xnmp1p] （3）

式中，[M]表示告警屬性缺失后的告警屬性的個數(shù)。[p=1]時，閔可夫斯基距離即曼哈頓距離；[p=2]時，閔可夫斯基距離即歐氏距離。本文使用歐氏距離定義了“相似度度量”，表示如下：

[dxn，xn=xn-xn2=m=1Mxnm-xnm2] （4）

如果第[n]條告警信息是完備數(shù)據(jù)集，第[n]條告警信息是缺失數(shù)據(jù)告警信息，通過計算，歐氏距離越小，相似度越大。相似度超過一定的門限后則使用該完整告警信息的告警屬性填充缺失告警信息數(shù)據(jù)。

3 故障聯(lián)合定位

基于填充后得到告警信息，進一步進行網(wǎng)絡故障分析。關聯(lián)規(guī)則分析常用于推理告警與故障之間的關聯(lián)關系，從而有效定位網(wǎng)絡故障。在國家電網(wǎng)現(xiàn)有的信息網(wǎng)絡與通信網(wǎng)絡中，網(wǎng)絡運維系統(tǒng)可以基于完備的告警信息分別定位兩個網(wǎng)絡的網(wǎng)內故障，而本節(jié)著重討論如何實現(xiàn)兩網(wǎng)的聯(lián)合故障定位，即由信息網(wǎng)絡關聯(lián)故障定位通信網(wǎng)絡根源故障。

利用二分圖[14]故障關聯(lián)模型進行通信網(wǎng)絡與信息網(wǎng)絡的聯(lián)合故障定位。二分圖故障關聯(lián)模型是一種特殊的因果關系模型，它不但可以準確描述通信網(wǎng)源故障節(jié)點和信息網(wǎng)關聯(lián)故障節(jié)點的關聯(lián)關系[15]，而且模型簡單、易于求解實現(xiàn)。

以圖2為例，該模型以通信網(wǎng)絡源故障節(jié)點作為根源故障層，以信息網(wǎng)關聯(lián)故障節(jié)點作為關聯(lián)故障層，通過源故障節(jié)點和關聯(lián)故障節(jié)點之間的故障傳播關聯(lián)關系，實現(xiàn)通信信息網(wǎng)的聯(lián)合定位。假設在某一時刻通信網(wǎng)的故障狀態(tài)用源故障集合[T=T1，T2，…，TK]表示，其中[K]表示產生通信網(wǎng)絡源故障的總數(shù)，信息網(wǎng)的故障狀態(tài)用關聯(lián)故障集[C=C1，C2，…，CG]表示，其中[G]表示產生信息網(wǎng)絡關聯(lián)故障的總數(shù)。通信網(wǎng)相關節(jié)點發(fā)生故障時，[Ti]取值為1，反之則取為0。同理，信息網(wǎng)網(wǎng)絡節(jié)點故障狀態(tài)用[Cj]表示。設[wji]為邊[（Ti，Cj）]的權重，表示通信網(wǎng)源故障節(jié)點[Ti ]對信息網(wǎng)關聯(lián)故障節(jié)點[Cj]的故障傳播概率。

在二分圖模型的基礎上，可以將故障定位問題描述為：在候選的通信網(wǎng)源故障集中找到故障假設集合[Y（Y?T）]，使得發(fā)生實際觀察到的信息網(wǎng)的關聯(lián)故障集[H（H?C）]時，該故障假設發(fā)生的概率最大。因[H]是觀察到的關聯(lián)故障集，則先驗概率[PH]為常數(shù)，根據(jù)貝葉斯法則該優(yōu)化目標可以表示為：

[ maxY?T PYHPH= maxY?T PHYPY] （5）

定義[K]維向量[y=（y1，y2，…，yK）]。源故障[Ti]與向量[y]的關系如下：

[Ti∈y， yi=1Ti?y， 其他] （6）

定義[pTi]為通信網(wǎng)源第[Ti]個故障節(jié)點的先驗概率，源故障集的先驗概率[P（Y）]為：

[PY=i=1KpTiyi1-pTi1-yi] （7）

設[PCjY]為當故障[Y]發(fā)生時，信息網(wǎng)關聯(lián)故障節(jié)點[Cj]發(fā)生的概率：

[PCjY=1-i=1K1-wjiyi] （8）

假設故障[Y]發(fā)生時，信息網(wǎng)關聯(lián)故障發(fā)生的概率為：

[PHY=Cj∈HPCjY] （9）

把式（7）和式（9）代入式（5），目標函數(shù)表示為：

[argmaxY?T PHYPY=argmaxY?T Cj∈H1-i=1K1-wjiyi? i=1KpTiyi 1-pTi1-yi] （10）

對式（10）中的目標函數(shù)取對數(shù)可得：

[ maxY?T Cj∈Hln1-i=1K1-wjiyi+ i=1Kyi·lnpTi1-pTi+ln1-pTi] （11）

由于[ln（1-pTi）]的大小與優(yōu)化變量無關，因此可以直接消除。設：

[bi=-lnpTi1-pTi， i=1，2，…，K] （12）

則目標函數(shù)最終轉化為：

[maxY?T Cj∈Hln1-i=1K1-wjiyi -i=1Kyibi] （13）

對于每一個信息網(wǎng)的關聯(lián)故障集[H，]系統(tǒng)的最優(yōu)診斷定位中應該至少包含一個通信網(wǎng)的源故障，在二分圖模型中，源故障可以解釋關聯(lián)故障的前提是[ wji>0]。將[wji]作為矩陣元素構建源故障和關聯(lián)故障的關聯(lián)關系矩陣[W。]該矩陣的每一行表示一個關聯(lián)故障[Cj]對應的源故障（即這些故障可以導致該關聯(lián)故障發(fā)生），該約束可以表示為：

[Wy≥c] （14）

其中[c]是包含[Cj]的向量。

最后故障定位問題可以轉化為下列最小化問題：

[minY?T z（y）=-Cj∈Hln1-i=1K1-wjiyi +i=1Kyibis.t. Wy≥c yi∈0，1， i=1，2，…，K] （15）

該問題為0?1規(guī)劃的問題。本文采用隱枚舉法中的目標排序法對該問題進行求解。該方法不需要過濾條件，也略去了用過濾條件檢驗每個目標函數(shù)的工作。在用過濾法求出解集中各解點[z]的基礎上，將[z]值按大小排序，然后按[z]值順序檢驗各解的可行性，確保通過檢驗的第一個可行解即為最優(yōu)解。

4 仿真結果分析

使用國家電網(wǎng)通信網(wǎng)絡中14個網(wǎng)絡節(jié)點以及信息網(wǎng)絡11個網(wǎng)絡節(jié)點的相關500條歷史告警信息數(shù)據(jù)進行仿真實驗。在仿真實驗中，首先使用MCAR算法（Missing Completely At Random）[16]對原始完整的告警信息進行處理以得到不同缺失率的缺失數(shù)據(jù)集。然后分別使用文中的三種算法進行數(shù)據(jù)填充，比較算法的恢復正確率。數(shù)據(jù)填充算法的數(shù)據(jù)恢復正確率仿真結果如圖3所示。隨著數(shù)據(jù)缺失率的增加，各算法的數(shù)據(jù)恢復正確率逐漸減小。仿真結果顯示，決策樹算法的告警數(shù)據(jù)恢復正確率最高。

其次，利用各個算法數(shù)據(jù)填充后的告警信息進行通信信息網(wǎng)絡聯(lián)合故障定位分析，判斷通信網(wǎng)的根源故障，并比較各個算法的信息通信網(wǎng)絡故障聯(lián)合定位診斷率。使用TP表示故障診斷率，即故障發(fā)生診斷出故障的概率，故障診斷率定義如下：

[TP=正確診斷故障數(shù)故障發(fā)生總數(shù)×100%]

在告警信息缺失率為10% 時，將數(shù)據(jù)填充算法恢復的完備數(shù)據(jù)集應用到故障聯(lián)合定位場景中，得到的故障診斷率結果如圖4所示。首先，該結果表明在通信網(wǎng)絡信息網(wǎng)絡聯(lián)合故障定位中，告警數(shù)據(jù)的信息缺失對故障聯(lián)合定位的影響很大。在缺失告警信息條件下故障診斷率降低了約30%。其次，相似度算法的故障診斷率的均值為75%，WARM算法均值約為85%。而決策樹算法均值約為89%。該實驗結果與數(shù)據(jù)恢復正確率實驗結果一致。最后，決策樹算法的故障診斷率十分接近完備數(shù)據(jù)集的故障診斷率。該結果表明，使用決策樹算法進行告警信息數(shù)據(jù)填充具有較高的通信信息網(wǎng)絡聯(lián)合故障定位性能。

同樣，研究了這三種數(shù)據(jù)填充算法在不同數(shù)據(jù)缺失率條件下的網(wǎng)絡聯(lián)合故障定位性能。在數(shù)據(jù)缺失率為50%時，使用恢復數(shù)據(jù)集進行聯(lián)合故障定位的故障診斷率結果如圖5所示。結果顯示，在該數(shù)據(jù)缺失率條件下，決策樹算法填充后的告警數(shù)據(jù)得到的聯(lián)合故障定位相較于其他兩種算法更加精確。

5 結 語

準確恢復告警信息缺失，對國網(wǎng)通信網(wǎng)絡信息網(wǎng)絡的故障聯(lián)合定位有非常重大的意義。本文首次提出利用數(shù)據(jù)填充解決通信網(wǎng)中的告警信息的缺失，并分析比較了多個數(shù)據(jù)填充算法。本文不僅提出了將決策樹分類算法用于缺失數(shù)據(jù)的填充，并通過仿真實驗驗證了該方法的網(wǎng)絡故障聯(lián)合定位性能。該方法數(shù)據(jù)恢復正確率高，故障診斷率高，實現(xiàn)了準確的故障聯(lián)合定位。

參考文獻

[1] 沈琳，陳千紅，譚紅專.缺失數(shù)據(jù)的識別與處理[J].中南大學學報（醫(yī)學版），2013，38（12）：1289?1294.

[2] HALATCHEW M， GRUENWALD L. Estimating missing values in related sensor data streams [C]// Proceedings of 2005 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2005： 83?94.

[3] 鄧歆，孟洛明.基于貝葉斯網(wǎng)絡的通信網(wǎng)告警相關性和故障診斷模型[J].電子與信息學報，2007（5）：1182?1186.

[4] 戚勇，李千目，劉鳳玉.基于BP神經(jīng)網(wǎng)絡的網(wǎng)絡智能診斷系統(tǒng)[J].微電子學與計算機，2004，21（10）：10?13.

[5] 李文超，楊妮妮.基于本體的語義相似性研究[J].科學技術與工程，2012，20（21）：5328?5330.

[6] HAN J，KAMBER M.數(shù)據(jù)挖掘：概念與技術[M].范明，孟小峰，譯.3版.北京：機械工業(yè)出版社，2012：213?222.

[7] COVILLE A， SIDDIQUI A， VOGSTAD K O. The effect of missing data on wind resource estimation [J]. Energy， 2011， 36（7）： 4505?4517.

[8] GHOLAMI M R， JANSSON M， STR?M E G， et al. Diffusion estimation over cooperative multi?agent networks with missing data [J]. IEEE transactions on signal and information processing over networks， 2016， 2（3）： 276?289.

[9] 張琳，陳燕，李桃迎，等.決策樹分類算法研究[J].計算機工程，2011，37（13）：66?67.

[10] 季桂樹，陳沛玲，宋航.決策樹分類算法研究綜述[J].科技廣場，2007（1）：59?62.

[11] 路翀，徐輝，楊永春.基于決策樹分類算法的研究與應用[J].電子設計工程，2016（18）：1?3.

[12] 李航.統(tǒng)計學習方法[M].北京：清華大學出版社，2012：61?67.

[13] 周志華.機器學習[M].北京：清華大學出版社，2016：199?201.

[14] 杜曉麗，朱程榮，熊齊邦.一種基于依賴圖的故障定位算法[J].計算機應用，2004，24（z2）：67?69.

[15] 彭熙，李艷，肖德寶.事件關聯(lián)策略的實現(xiàn)及其應用研究[J].計算機工程與設計，2003，24（10）：16?19.

[16] NOWICKI R K， SCHERER R， RUTKOWSKI L. Novel rough neural network for classification with missing data [C]// Proceedings of 2016 the 21st International Conference on Methods and Models in Automation and Robotics （MMAR）. [S.l.]： IEEE， 2016： 820?825.