基于网络和时间约束的告警序列模式挖掘研究∗

徐立坤 李建路 朱 珠 陈海平 王 林

（南方电网调峰调频发电有限公司 广州 510630）

1 引言

随着电力通信网络及业务的快速发展，电力通信技术已经成为电力生产的一个重要环节，电力通信传输网络的可靠性成为影响着电力生产安全的重要组成部分［1］。

告警是故障的外在呈现，具有传递性和多方面、多环节显现等特点［2～6］，即一条根告警会引起大量次要衍生告警，甚至可能引起“告警风暴”。运维人员如能第一时间对系统告警准确判断并及时处理，可以大大减少故障处理时间，迅速恢复业务系统正常使用，故告警相关性分析是故障分析和处理的基础。

由于传统手段依赖告警规则树、白名单等先验知识，无法适应网络复杂多变的特点，而告警序列模式挖掘是实现告警相关性分析的重要方法。序列模式挖掘最早由 Agrawal和 Srikant提出［7］，序列模式是在一组有序的数据列组成的数据集中，经常出现的那些序列组合构成的模式。与关联规则挖掘不同，序列模式挖掘的对象以及结果都是有序的，即数据集中的每个序列的条目在时间或空间上是有序排列的，输出的结果也是有序的。由此可发现告警关联知识，提供告警过滤，为进一步实现从告警到故障提供支撑。

考虑电力传输网络复杂多变，告警数量庞大、实时性强，本文旨在研究告警的设备交互和时间窗特征，提出一种基于网络和时间约束的告警序列模式挖掘方法，从而能够有效地发现告警关联知识，支撑根告警分析和故障诊断，协助运维人员进行快速的告警定位和故障处理。

2 序列模式挖掘研究现状

近年国内外学者对序列模式挖掘做了大量的研究，序列模式挖掘就是从序列数据库中找出所有满足最小支持度的序列模式。通常需要引入约束以减少算法的搜索范围，提高算法的有效性和执行效率。在序列模式挖掘算法中，引入特定的约束条件，可有效引导算法以搜索出其所关心的序列模式，避免产生大量没有价值甚至会产生干扰作用的模式结论。

文献［7］最早提出序列模式挖掘的理论和方法，介绍了3种基于Apriori算法框架的AprioriAll，AprioriSome和DynamicSome算法；文献［8］提出了基于序列模式的增长不产生候选集的FreeSpan算法；文献［9］提出PrefixsSpan算法是对FreeSpan算法的改进，减少了投影数据库和子序列连接次数；文献［10］给提出了一种基于PrefixSpan算法的改进算法，该算法可以减少构建投影数据库的时间开销和降低支持度增加对算法效率的影响；文献［11］提出了周期性一般间隙约束的序列模式挖掘问题。

序列模式发掘非常适用于告警相关性分析，国内外学者也做了相关研究。文献［12］研究了序列模式挖掘在网络告警分析中的具体应用，提出了基于拓扑约束的互联设备告警序列模式挖掘算法；文献［13］提出了一种基于序列模式挖掘提取告警相关性规则的方法，构造了引入时间约束的序列模式挖掘算法；文献［14］讨论了挖掘情景规则的常用算法，提出了基于序列模式挖掘的告警关联分析的网管系统模型。

此外关于告警相关性分析的一些其他研究，文献［6］研究了基于组合规则的电力通信网故障分析方法；文献［15］系统地介绍了提出了网络相关性和时间相关性概念模型，并将其应用于告警相关性分析；文献［1］给出了电力通信故障防御软件的研究及实际应用案例，这些研究成果可和序列模式挖掘相结合，完善告警序列模式挖掘的研究应用。

3 算法设计

3.1 告警序列模式挖掘关键定义

定义1 项目:序列中最小组成单位，比如电力传输网络的某条告警。

定义2 项目集:各种项目组成的集合。

定义3 序列:不同项目集的有序排列，序列s可以表示为s=＜ s1，s2，…，si，…，sl＞；sj（1 ≤ i≤l）为项目集，也称为序列s的元素。

定义4 k频繁序列:如果频繁序列的项目个数为k，则称之为k频繁序列，以Fk表示。

定义5 支持度:序列x在序列数据库S中的支持度为序列数据库S中包含序列x的序列个数，记为Support（x）。

定义6 序列模式:给定支持度阈值ξ，如果序列x在序列数据库S中的次数不低于ξ，则称序列x为序列模式。长度为1的模式成为1-模式。

定义7 置信度:对于模式a和模式b（a∈b）之间的蕴涵关系a ≥ b-a，定义置信度conf=fr（b，s）/fr（a，s）表征蕴涵关系的强度。

定义8 模式规则:告警数据集中置信度conf大于给定最小置信度minConf的两个频繁模式之间蕴含的关系，表示为a≥b-a with conf。

序列模式挖掘，就是给定一个序列数据库S以及最小支持度min_sup，找出所有支持度大于min_sup的序列模式。基于序列模式，合理设置置信度，可到得到模式规则，即最终提交给用户或作为故障管理系统基础的告警关联知识，支撑告警过滤、告警定位及故障诊断等应用。

3.2 网络约束分析

电力通信传输网络发生的一组告警，其所在网元设备相同（存在关系Re），或其所在传输段相同（存在关系Rc），或其所在的业务通道相同（存在关系Rb），则被认为这组告警具备网络相关性。

假设n个具备网络相关性的告警依次为a1，a2，…，an，满足网络相关性要求的计算公式，如式（1）所示:

式中R表示关系；1≤x≤n，l≤y≤n。

3.3 时间约束分析

电力通信传输网络发生的一组具有网络相关性的告警，其发生时间基本处在一个有限或相对较短的时问段内，才被认为具有时间相关性。

为定量地描述时间相关性，可定义时间窗来实现。时间窗是为了界定一组告警在时间上是否相关，假设从最初一条到达，到最后一条到达之间的最长等待时间为Tmax。只有在时间窗内发生的告警，才被认为具有时间相关性。

设定n个具有时间相关性的告警的发生时间为:tl，ti，…，tn，则满足时间相关性要求的计算公式，如式（2）所示:

3.4 告警序列模式挖掘流程

本文所述基于网络和时间约束的告警序列模式挖掘算法流程，如图1所示。

图1 算法流程

步骤一:生成初始序列，获取网络管理系统中某段时间的告警记录，进行数据整理和预处理，生成初始序列。

步骤二:网络约束分析，结合告警所涉及的设备集，进行告警项目集分组，将单条的初始序列拆解为若干条序列，每条序列对应一组存在网络约束关系的设备。

步骤三:时间约束分析，在网络约束分析的基础上，根据设定的时间跨度Δt，过滤掉时间窗之外的告警项目集，得到更新后的时间约束条件下的序列。

步骤四:序列模式挖掘，设定频繁模式阈值C，找出度大于给定阈值的所有频繁模式。频繁模式的发现过程包括迭代的两个阶段，频繁模式和剪枝，依次得到1-项集，2-项集，3-项集，…，l-项集。

步骤五:规范生成，设定合适的置信度Conf，基于步骤四得到的序列模式，生成最终规则，即提供给用户的告警关联知识。

4 算例分析

表1为某电网公司某段时间告警记录数据，以此告警数据记录为例，给出本文所述基于网络和时间约束的告警序列模式挖掘方法的算例分析。

表1 某段时间告警记录

4.1 生成初始序列

为表述更清晰直观，对告警类型进行映射，如表2所示。

表2 告警类型映射表

基于告警类型映射表，可得到告警序列S=｛A（0），A（1），B（1），C（2），C（2），D（2），G（2），E（3），G（4），F（5），F（6），E（10），F（12），D（35）｝，K（i），K表示具有不同属性的告警事件，i表示事件发生的相对时间。

告警序列S，即初始序列，可用表3方法表示。

表3 初始序列

4.2 网络约束分析

由告警序列相关的告警设备，可知告警来自设备集M，其中设备集M=｛设备1，设备2，设备3，设备4，设备5，设备6，设备7｝，结合网络管理系统得到设备连接关系如图2所示。

图2 SDH网络传输拓扑图

结合网络管理系统业务开通情况，可得到图中包含的两条电路，分别为设备1＜-＞设备3＜-＞设备4；设备2＜-＞设备5＜-＞设备6＜-＞设备7。故可将初始序列拆分为两条子序列，如表4所示。

表4 网络约束下的序列

4.3 时间约束分析

假定时间跨度Δt=15s，过滤掉时间窗之外的告警项目集，可得到时间约束条件下的序列，如表5所示。

表5 时间约束下的序列

4.4 序列模式挖掘

假定频繁模式的阈值C=2，找出度大于给定阈值的所有频繁模式。频繁模式的发现过程包括迭代的两个阶段，频繁模式和剪枝，依次得到1-项集，2-项集，3-项集，4-项集，如图3所示。

图3 序列模式挖掘

4.5 规则生成

假定置信度为70%，基于上一小节得到的序列模 式 ＜A，C，E，F＞，生 成 最 终 规 则 :R_LOS-＞MS_AIS-＞AU_AIS-＞TU_AIS。

类似的规则依靠传统手段不易获得，需依赖传输设备及网络非常精通的业务技术专家添加和维护。

4.6 实际验证

结合某电网公司3个月的传输网络告警数据进行了算法验证。该电网公司3个月期间共收到告警数据593561条，平均每条告警数量6000多条，给运维人员的告警监视和故障分析工作带来了很大挑战，之前采用人工配置维护白名单的方式，但是由于网络拓扑和设备类型、型号等变化较快，导致告警关联规则更新不及时，实际告警压缩和分析效果不理想。

采用本文所述方案，对不同的时间窗、支持度、置信度进行算法验证，分别得到的规则数如表5所示。经过业务专家深入细致的比对和核实，发现时间窗设置为15s，支持度设置为3次，置信度设置为70%时效果最佳。既避免了规则数过少失去挖掘分析的意义，又避免规则数过多，部分规则不符合实际需求的情况。

采用本文所述方法，该电网公司故障管理系统的告警关联规则库实现了自动学习和更新，提升了告警压缩率和故障处理效率。

表5 规则生成

5 结语

算例分析和实际验证表明，相较于传统的人工配置告警白名单的告警过滤手段，基于网络和时间约束的告警序列模式挖掘方法不依赖于专家经验和先验知识，可识别复杂网络的告警特征，提高告警序列模式挖掘的针对性和效率，可有效发现告警关联知识，有利于告警的准确有效定位，使运维人员能及时发现故障并快速解决，提高了电力通信网可靠性及通信运维管理水平，对电力业务运行的安全性和稳定性具有重大意义。