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

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

關鍵詞： 網絡告警故障； 決策樹算法； WARM算法； 相似度算法； 故障聯合定位

中圖分類號： 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 引 言

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

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

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

1 問題背景

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

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

2 缺失告警信息填充

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

2.1 決策樹算法

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

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

輸出：決策樹[U]

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

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

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

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

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

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

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

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

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

2.2 WARM算法

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

信息通信網絡中的告警信息矩陣[X]表示如下：

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

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

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

[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]時為弱相關，其他的情況為中度相關。在實現時使用與告警關聯性強的完整告警信息的屬性值對缺失告警中的屬性值進行填充。

2.3 相似度算法

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

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

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

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

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

3 故障聯合定位

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

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

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

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

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

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

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

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

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

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

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

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

[PHY=Cj∈HPCjY] （9）

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

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

對式（10）中的目標函數取對數可得：

[ 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）

則目標函數最終轉化為：

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

對于每一個信息網的關聯故障集[H，]系統(tǒng)的最優(yōu)診斷定位中應該至少包含一個通信網的源故障，在二分圖模型中，源故障可以解釋關聯故障的前提是[ wji>0]。將[wji]作為矩陣元素構建源故障和關聯故障的關聯關系矩陣[W。]該矩陣的每一行表示一個關聯故障[Cj]對應的源故障（即這些故障可以導致該關聯故障發(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ī)劃的問題。本文采用隱枚舉法中的目標排序法對該問題進行求解。該方法不需要過濾條件，也略去了用過濾條件檢驗每個目標函數的工作。在用過濾法求出解集中各解點[z]的基礎上，將[z]值按大小排序，然后按[z]值順序檢驗各解的可行性，確保通過檢驗的第一個可行解即為最優(yōu)解。

4 仿真結果分析

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

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

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

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

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

5 結 語

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

參考文獻

[1] 沈琳，陳千紅，譚紅專.缺失數據的識別與處理[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] 鄧歆，孟洛明.基于貝葉斯網絡的通信網告警相關性和故障診斷模型[J].電子與信息學報，2007（5）：1182?1186.

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

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

[6] HAN J，KAMBER M.數據挖掘：概念與技術[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] 彭熙，李艷，肖德寶.事件關聯策略的實現及其應用研究[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.