基于DBSCAN算法的告警数据聚类研究

2021-01-21邓翠艳姚旭清

太原理工大学学报 2021年1期

邓翠艳，姚旭清

(1.太原理工大学现代科技学院，太原 030027；2.中国移动通信集团山西有限公司，太原 030009)

通信网络时刻会产生大量的告警数据，由于网络设备的连通性，原始告警数据通常存在信息冗余、时间不同步、含有噪声等一系列问题[1]，无法直接完成对原始告警数据的关联挖掘。告警关联挖掘需要输入各项事务数据集，因此首先需对原始的告警数据进行转换[2-3]，生成适合挖掘的事务集才能完成后期的相关工作。目前对于时间序列数据的挖掘，大部分研究都设定固定的时间窗口和滑动步长来建立事务数据库[1]。但由于告警具有随机性，采用固定滑动时间窗口在告警频发时段可能会把有关联的告警截断到不同的事务集中，在告警稀疏的时间段会产生空的告警事务集，降低了告警关联规则挖掘的准确性，同时由于网络短暂的振动或不稳定容易产生大量的噪音告警，影响关联规则挖掘的准确性。文献[3-5]提出了多种聚类的智能算法，但是对于告警数据的聚类及冗余数据清除均无法满足告警数据本身特征。DBSCAN聚类算法[6]是一种以密度为基础的聚类分析算法，主要由可达关系导出的最大密度相连的样本集合，即为最终聚类的一个类别。在告警数据聚类中，以告警时间间隔作为度量距离的标准，最大密度相连的告警数据会被聚到同一个时间段，同时清除噪音告警。本文提出了一种基于DBSCAN算法和多约束算法的告警预处理方法。

1 告警数据预处理

伴随设备产生并获取大量告警数据后，需要先对告警数据进行预处理。告警数据的预处理主要是完成对告警数据信息的数据集成、清洗、简化。本文涉及到的预处理方法主要包含活动时间窗口设置、DBSCAN聚类、告警数据分段及有效的事物提取。

1.1 滑动时间窗口

1) 时间窗口和窗口宽度。对于告警事件E，告警序列S={m,Ts,Te}，其中Ts是告警开始发生时间，Te是告警结束时间，m=(e1,t1)，(e2,t2),…,(en,tn)，ei∈E,Ts≤ti≤Te,i=1,…,n.子序列Sw={w,ts,te}为S的一个时间窗口，Ts

2) 滑动步长。告警序列在当前窗口内起始时间为ts，结束时间为te，则te-ts=W.窗口经过s时间后滑动到一个新的位置，新窗口的起始时间和结束时间分别为ts+s和te+s.则s为窗口滑动步长。

3) 告警时间间隔。告警序列中两个告警发生的时间差。

图1为均匀滑动窗口的示例。其中e1,e2,…,e9为告警事件，{(e1,5),(e6,6)(e3,7),…,(e7,34)}是一个告警序列。时间窗口宽度为8，滑动步长为5.

图1 滑动时间窗口示例Fig.1 Example of sliding time window

1.2 告警数据分段及事务提取约束条件

为了告警关联规则挖掘的准确性，告警数据在分段及提取告警事务数据过程中，各个时间段或事务之间的中心点距离(段间差异)越大越好，时间段内或事务内各个告警数据与中心点的距离(段内差异)越小越好。本文均采用告警时间间隔作为距离的度量标准。

定义1中心点：对于一个包含n个告警数据的告警序列T={(e1,t1),(e2,t2),…,(en,tn)}的中心点为

T1/2=t1+(t2-t1)/2.

定义2段间差异：相邻两个时间段或事务中的中心点之间的平均距离。即

定义3段内差异：各时间段或事务内每条告警数据与该时间段或事务中心点的平均距离。即

定义4告警数据分段或事务提取总体质量定义为：

总体质量越大说明分段或事务提取效果越好。

2 基于DBSCAN和多约束滑动时间窗口算法

本文完成的主要工作有：

1) 根据原始告警数据的特点，利用DBSCAN密度聚类算法以时间维护将原流水告警数据划分为多个告警事件时间戳。

2) 通过约束条件选取DBSCAN最佳输入参数，在各个时间段利用滑动时间窗口提取告警事务。

2.1 算法的提出

通信网中告警的发生具有不确定性，但相关性越强的告警数据会在某一个时间段内产生的比较密集，相关性较弱或无相关性的告警数据产生的时间间隔会比较大，而且在其他因素的影响下会引起少量的噪音告警。若采用固定的滑动时间窗口，在告警比较密集的时间段内，相关性比较大的告警数据可能会截断到不同的事务中，在告警稀疏的时间段产生大量空的告警事务，且不能清除噪音告警，降低了告警关联规则挖掘的效率和准确性。DBSCAN算法是一种以密度为基础的聚类分析算法，该算法在不需要预先指定聚类数量的情况下找出任何形状的聚类，且能有效地分辨数据集中的噪音。因此可用DBSCAN算法先将告警数据分成多个告警产生比较密集的时间段，并根据约束条件确定输入的最佳参数，然后利用滑动时间窗在各个时间段进行告警事务提取。该方法不仅可以减少噪音告警对告警事务提取的影响，而且能确定最佳的输入参数，具有很大的灵活性和实用性。

2.2 时间窗口宽度和滑动步长选择

滑动时间窗口主要解决网络设备时间不同步和告警事件时间间隔过小问题，因此在聚类后的各个时间段用滑动时间窗口法进行事务提取。由于同一个时间窗内的告警事件为同一事务，时间窗口宽度W的取值范围为Gmax

为了能充分利用告警数据，防止将几乎同时发生的告警截断到两个告警事务集中，选择的滑动步长应该使相邻两个时间窗口有足够的重叠。滑动步长越小，相邻两个窗口重叠的告警数据越多，提取的事务就越多；滑动步长越大，相邻两个窗口重叠的告警数据越少，提取的事务就会相对减少。当滑动步长大于时间窗口宽度时，就会遗漏部分告警信息。因此滑动步长s的取值范围为Gmin

伪代码如下：

3 实验评测

实验分别采用某省通信公司6月份的全量告警记录和USENIX的计算机故障数据库(CFDR)来自Intrepid的Blue Gene/P数据。针对原始通信公司告警数据信息冗余、字段不完整和噪音告警等问题，对原始告警数据进行数据清洗，并提取告警标准名、告警发生时间、告警对象设备类型、告警类别4个属性来表述告警事件；BlueGene数据由Blue Gene/P Intrepid系统在6个月内收集到的RAS日志消息组成，选取部分数据并提取标识符MSG_ID和消息发生时间表述一致的消息。利用DBSCAN算法在邻域半径为240 s，300 s，360 s和420 s下分别设置不同的邻域阈值(MinPts)来计算告警数据分段的总体质量和噪音数据百分比。

由图2、图3可以看出，在同一邻域半径下，随着邻域阈值增大，DBSCAN聚类密度越大，各聚类时间段内的告警数据越密集，噪音数据随之增多，分段质量持续增加。在实际应用中，清除过多的噪音数据可能会同时清除包含有很多信息量的数据。因此本文根据实际需求，在噪音数据百分比小于6%的情况下对两个数据集分别选取使分段总体质量最大的邻域半径和邻域阈值。

图2 不同邻域半径下告警分段的总体质量Fig.2 Overall quality of alarm segmentation under different neighborhood radius

图3 不同邻域半径下告警分段噪音百分比Fig.3 Noise percentage of alarm section under different neighborhood radius

本文设定时间窗分别为360 s和420 s，利用DBSCAN-滑动窗口法、固定滑动窗口法和基于近邻传播的滑动窗口法分别计算在相同时间窗口宽度的不同滑动步长下所提取的事务数、段内差异和事务集总体质量，如图4-图6所示。

(a)某省通信公司数据集；(b)Blue Gene数据集图4 不同滑动窗口下告警数据集的变化Fig.4 Changes of alarm data sets under different sliding windows

由图4可以明显看出，DBSCAN-滑动窗口法能有效减少所提取的告警事务数，其原因是在DBSCAN对告警分段过程中清除了噪音告警数据，且在时间窗口提取事务过程中不会因该时间段告警稀疏而产生空事务集。由于BlueGene数据集在某时间段内产生消息相对稀疏，因此滑动窗口法产生了大量空的数据集，DBSCAN算法有效地消除了空事务集对事务提取的影响使事务集数量大大减少。由图5和图6可看出，DBSCAN-滑动窗口法所提取事务的段内差异和总体质量均明显优于固定滑动窗口和基于近邻传播的滑动窗口法。由于段间差异随着滑动步长的增加而增加，事务提取总体质量也不断增加，在这种情况下，段内差异越小越好。在实际应

用中，为了保证相邻窗口有足够多的重叠，应根据实际要求和段内差异设置最佳时间窗口宽度和滑动步长。

根据告警数据特点以及固定时间窗口提取事务数据集的不合理性，提出了一种基于DBSCAN算法和多约束的滑动时间窗口法。实验结果证明，与固定的滑动时间窗口法和基于近邻传播的滑动窗口法相比，该算法在DBSCAN分段过程中能清除噪音告警，有效地减少了噪音告警对事务提取的影响，从而减小了事务提取的段内差异，提高了事务提取的总体质量。在实际应用中，可根据实际需求及多约束条件选取最佳参数，更加充分利用告警数据。随着通信网的发展，产生的告警数据越来越多，传统的单机处理告警数据的效率会越来越低，因此接下来的研究应侧重于该将分布式数据处理应用于告警预处理以及告警分析，从而提高告警关联规则挖掘效率。