面向故障联合定位的告警数据信息填充算法

许鸿飞+于然+李雪梅+寇晓溪+赵子兰+金燊+杨清海

摘 要： 数据完整性是网络告警信息的基本质量属性，是进一步进行网络告警故障分析的基础。然而在现实中，网管系统可能接收到信息缺失的网元告警信息，从而影响网络故障定位的准确性。分别使用决策树算法、窗关联规则挖掘（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 引 言

当前国家电网数据网络架构中，通信网络与信息网络分别通过两套不同的网络管理系统实现网络运维，然而通信网络中的故障往往会关联引发信息网络中的故障。故障联合定位分析能够从信息网络关联故障准确定位到通信网络的根源故障，从而提高国家电网信息通信网络的整体运维效率。故障联合定位依赖于完整一致的网络告警信息，然而在现实中由于网络继发故障等种种原因，网管系统可能收集到信息缺失的网元告警信息。网络告警信息的缺失会导致网络管理性能下降，降低网络故障定位的准确性[1]。因此，对告警缺失信息的有效估计和填充是提高国家电网信息通信网的整体运维效率亟需解决的问题。

数据填充[2]是指采用一定的方法对数据资料的缺失值进行合理的估计。当前在各个领域已经展开对数据填充算法的研究，但是仍缺乏在网络故障联合定位场景下的应用以及性能分析。文献[3]采用贝叶斯网络进行网络联合故障定位，然而该研究并没有考虑告警信息的缺失问题，以及告警信息缺失导致的故障定位不准确问题。文献[4]基于神经网络进行网络联合故障定位，但该方法需要经历较长时间的模型训练才能获得贴近实际情况的模型。告警信息中的数据缺失会导致最终训练得到的模型误差很大，从而使定位产生较大的偏差。文献[5]中提出基于模型的故障定位算法，其主要优点是在节点无法确定先验概率的情况下仍可以定位网络故障，然而告警信息中的数据缺失将会导致产生故障的节点判断错误，从而无法准确定位根源故障。

网络告警信息的完整性是实现高效网络运维的基础，本文针对国家电网信息通信网络告警数据缺失问题进行了分析研究。首先，分析评估了已有的数据填充方法[6?8]，并采用决策树方法实现缺失告警数据的填充。其次，介绍了面向故障联合定位的二分图故障关联模型以及联合故障定位方法。最后，在实际网络应用场景中进行仿真实验并比较了上述算法在故障联合定位场景下的故障诊断率。仿真结果表明，通过决策树算法[9?11]进行告警数据信息填充的方法具有较高的故障诊断率。

1 问题背景

网络故障诊断是通过分析监测设备向网络运维系统发出网络告警数据进行网络故障的判断。例如，通过分析告警数据，确定告警与故障之间的关联关系以及告警的属性之间的关联关系，从而判断网络故障类型以及位置。国家电网通信网络与信息网络中常见的告警属性数据格式如图1所示。告警信息包含多个属性项，如告警级别、告警类型等。然而在现实中，网管系统可能接收到某些属性项缺失的告警信息，例如缺失告警级别属性。当告警属性缺失时会导致无法进行准确的故障诊断。

在本文中，首先根据告警属性之间的关联关系对缺失属性项进行填充，形成完整的告警信息。其次，基于填充完整的告警信息进行网络故障诊断。

2 缺失告警信息填充

在本文中主要分析评估决策树算法、WARM（Window Association Rule Mining）算法[2]以及相似度算法[12]三种数据填充算法的性能。

2.1 决策树算法

本文提出使用ID3分类算法[6]对缺失告警属性进行数据填充。该方法包含对关键属性进行特征选择以及生成决策树两步。实现步骤如下：

输入：完整告警信息数据集[D]，特征集[A]即关键告警属性集，阈值[ε]

输出：决策树[U]

步骤1：若[D]中所有实例属于同一类[El]，其中[l=1，2，…，L]，[L]为告警数据集中类的总数，则[T]为单节点树，并将类[El]作为该节点的类标记，返回[U]；

步骤2：若[A=?]，则[U]为单节点树，并将[D]中实例数最大的类[El]作为该节点的类标记，返回[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]为单节点树，并将[D]中实例数最大的类[El]作为该节点的类标记，返回[U]；

步骤5：否则，对[Aq]的每一可能值[as，]其中[s=1，2，…，S，][S]表示[Aq]所有可能值的个数，依[Aq=as]将[D]分割为若干非空子集[Ds，]将[Ds]中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树[U，]返回[U]；

步骤6：对第[s]个子节点，以[Ds]为训练集，以[A-{Aq}]为特征集，递归地调用步骤1～步骤5，得到子树[Us，]返回[Us]。

最后，以每个叶子节点为一类对缺失告警信息的告警属性进行填充。

2.2 WARM算法

WARM算法是当某一节点的数据存在缺失时，该算法首先找到与之关联的一个节点，并用关联节点的值填充其缺失值。本文根据每条告警信息之间的相关系数来填补缺失数据的告警信息的告警属性。本文采用皮尔逊相关系数求各个告警信息间的相关性。

信息通信网络中的告警信息矩阵[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 故障联合定位

基于填充后得到告警信息，进一步进行网络故障分析。关联规则分析常用于推理告警与故障之间的关联关系，从而有效定位网络故障。在国家电网现有的信息网络与通信网络中，网络运维系统可以基于完备的告警信息分别定位两个网络的网内故障，而本节着重讨論如何实现两网的联合故障定位，即由信息网络关联故障定位通信网络根源故障。

利用二分图[14]故障关联模型进行通信网络与信息网络的联合故障定位。二分图故障关联模型是一种特殊的因果关系模型，它不但可以准确描述通信网源故障节点和信息网关联故障节点的关联关系[15]，而且模型简单、易于求解实现。

以图2为例，该模型以通信网络源故障节点作为根源故障层，以信息网关联故障节点作为关联故障层，通过源故障节点和关联故障节点之间的故障传播关联关系，实现通信信息网的联合定位。假设在某一时刻通信网的故障状态用源故障集合[T=T1，T2，…，TK]表示，其中[K]表示产生通信网络源故障的总数，信息网的故障状态用关联故障集[C=C1，C2，…，CG]表示，其中[G]表示产生信息网络关联故障的总数。通信网相关节点发生故障时，[Ti]取值为1，反之则取为0。同理，信息网网络节点故障状态用[Cj]表示。设[wji]为边[（Ti，Cj）]的权重，表示通信网源故障节点[Ti ]对信息网关联故障节点[Cj]的故障传播概率。

在二分图模型的基础上，可以将故障定位问题描述为：在候选的通信网源故障集中找到故障假设集合[Y（Y?T）]，使得发生实际观察到的信息网的关联故障集[H（H?C）]时，该故障假设发生的概率最大。因[H]是观察到的关联故障集，则先验概率[PH]为常数，根据贝叶斯法则该优化目标可以表示为：

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

定义[K]维向量[y=（y1，y2，…，yK）]。源故障[Ti]与向量[y]的关系如下：

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

定义[pTi]为通信网源第[Ti]个故障节点的先验概率，源故障集的先验概率[P（Y）]为：

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

设[PCjY]为当故障[Y]发生时，信息网关联故障节点[Cj]发生的概率：

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

假设故障[Y]发生时，信息网关联故障发生的概率为：

[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）]的大小与优化变量无关，因此可以直接消除。设：

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

则目标函数最终转化为：

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

对于每一个信息网的关联故障集[H，]系统的最优诊断定位中应该至少包含一个通信网的源故障，在二分图模型中，源故障可以解释关联故障的前提是[ wji>0]。将[wji]作为矩阵元素构建源故障和关联故障的关联关系矩阵[W。]该矩阵的每一行表示一个关联故障[Cj]对应的源故障（即这些故障可以导致该关联故障发生），该约束可以表示为：

[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规划的问题。本文采用隐枚举法中的目标排序法对该问题进行求解。该方法不需要过滤条件，也略去了用过滤条件检验每个目标函数的工作。在用过滤法求出解集中各解点[z]的基础上，将[z]值按大小排序，然后按[z]值顺序检验各解的可行性，确保通过检验的第一个可行解即为最优解。

4 仿真结果分析

使用国家电网通信网络中14个网络节点以及信息网络11个网络节点的相关500条历史告警信息数据进行仿真实验。在仿真实验中，首先使用MCAR算法（Missing Completely At Random）[16]对原始完整的告警信息进行处理以得到不同缺失率的缺失数据集。然后分别使用文中的三种算法进行数据填充，比较算法的恢复正确率。数据填充算法的数据恢复正确率仿真结果如图3所示。随着数据缺失率的增加，各算法的数据恢复正确率逐渐减小。仿真结果显示，决策树算法的告警数据恢复正确率最高。

其次，利用各个算法数据填充后的告警信息进行通信信息网络联合故障定位分析，判断通信网的根源故障，并比较各个算法的信息通信网络故障联合定位诊断率。使用TP表示故障诊断率，即故障发生诊断出故障的概率，故障诊断率定义如下：

[TP=正确诊断故障数故障发生总数×100%]

在告警信息缺失率为10% 时，将数据填充算法恢复的完备数据集应用到故障联合定位场景中，得到的故障诊断率结果如图4所示。首先，该结果表明在通信网络信息网络联合故障定位中，告警数据的信息缺失对故障联合定位的影响很大。在缺失告警信息条件下故障诊断率降低了约30%。其次，相似度算法的故障诊断率的均值为75%，WARM算法均值约为85%。而决策树算法均值约为89%。该实验结果与数据恢复正确率实验结果一致。最后，决策树算法的故障诊断率十分接近完备数据集的故障诊断率。该结果表明，使用决策树算法进行告警信息数据填充具有较高的通信信息网络联合故障定位性能。

同样，研究了这三种数据填充算法在不同数据缺失率条件下的网络联合故障定位性能。在数据缺失率为50%时，使用恢复数据集进行联合故障定位的故障诊断率结果如图5所示。结果显示，在该数据缺失率条件下，决策树算法填充后的告警数据得到的联合故障定位相较于其他两种算法更加精确。

5 结 语

准确恢复告警信息缺失，对国网通信网络信息网络的故障联合定位有非常重大的意义。本文首次提出利用数据填充解决通信网中的告警信息的缺失，并分析比较了多个数据填充算法。本文不仅提出了将决策树分类算法用于缺失数据的填充，并通过仿真实验验证了该方法的网络故障联合定位性能。该方法数据恢复正确率高，故障诊断率高，实现了准确的故障联合定位。

参考文献

[1] 沈琳，陈千红，谭红专.缺失数据的识别与处理[J].中南大学学报（医学版），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神经网络的网络智能诊断系统[J].微电子学与计算机，2004，21（10）：10?13.

[5] 李文超，杨妮妮.基于本体的语义相似性研究[J].科学技术与工程，2012，20（21）：5328?5330.

[6] HAN J，KAMBER M.数据挖掘：概念与技术[M].范明，孟小峰，译.3版.北京：机械工业出版社，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] 李航.统计学习方法[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.