赵泽玲, 冯海林, 齐小刚, 刘美丽
(西安电子科技大学 数学与统计学院, 西安 710126)
随着通信技术(如5G)的快速发展以及网络业务的不断拓宽, 通信网络中的告警数据量呈指数级增长, 一旦网络发生中断或异常, 将会严重影响人们的生产、 生活, 为维持具有高水平可用性和可靠性的网络系统, 必须要求高水平的网络管理技术. 为应对网络告警数据量的指数级增长、 网络规模的持续扩大以及不断增加的网络操作复杂性, 必须提高通信网络的自动化和智能化, 将机器学习(machine learning, ML)算法部署到通信网络是目前的主要趋势[1].
相比于机器学习的引入, 在传统的通信网络管理领域, 告警相关性分析主要分为基于案例的方法、 基于因果模型的方法、 基于相似性的方法和基于数据挖掘的方法. 数据挖掘中的关联规则挖掘算法和序列模式挖掘算法在分析网络告警数据的相关性以及追溯网络故障根源方面的应用最普遍. Li等[2]将关联规则挖掘用于告警关联分析系统中, 以寻找告警事件之间的相关性; Wang等[3]利用序列模式挖掘算法建立了拍打规则和父子规则, 以揭示电信网络中大量告警的操作模式; Solmaz等[4]应用关联规则挖掘技术确定告警相关性, 并基于拓扑图形的方法识别告警的根本原因.
由于告警数据多为无标记数据, 告警特征多用于定量分析, 因此传统方法多通过神经网络、 聚类等为关联规则算法提供权值[5-7], 在多维特征空间中快速定位导致网络异常的主要特征值组合研究较少[8]. 当数据规模较小时, 管理人员可通过手动发现有影响的特征值组合. 但当数据量巨大时, 采用人工的方式总结其中的规律十分困难, 因此, 需要借助机器学习中的相关算法挖掘数据的特征, 定位导致网络异常的具体特征值. 但引入机器学习需要有标签的告警数据, 因此本文通过对数据的分析处理, 利用关联规则生成可读的规则并构建出决策树, 然后使用决策树对新数据进行分析.
近年来, 机器学习已被广泛应用于通信网络[9-12]. 机器学习是一个多领域交叉的庞大体系, 包括监督学习、 半监督学习和无监督学习. 监督学习中输入向量和目标输出向量组成的样本被输入到机器学习模型中, 以推断出一个映射输入和输出的函数, 算法包含分类[13-14]、 人工神经网络[15]、 深度学习等[16]. 半监督学习算法考虑利用少量的标记样本和大量的未标记样本进行训练和分类, 包括生成模型算法等. 无监督学习使用未标记的数据集进行训练, 算法有聚类[17]、 关联规则等.
决策树是机器学习中常见的方法, 被用于解决分类问题, 目标是从大量的样本数据特征中找到分类决策路径. 在对通信网络进行告警数据分析时, 决策树具有易于通过可视化操作对模型进行解释、 易于通过静态测试对模型进行评测以及操作简等优点, 因此, 决策树的应用可对网络告警特征基于树结构进行决策, 进一步分析影响网络异常的告警特征因素, 从而实现网络故障的溯源分析. 决策树算法在机器学习中广泛使用[18]. Xu等[19]提出了一种新的特征转换方法, 即决策树算法的动态特征捆绑; 文帅川等[20]通过构建二叉决策树模型开发推理机机制实现故障定位; 针对缺失网络告警信息, 许鸿飞等[21]应用决策树算法对告警信息中缺失的属性值进行填充; Dorgo等[22]利用决策树分类器提出了一种设计告警信息进行故障检测的方法, 而不是过滤或修改现有的告警信息; Mijumbi等[23]提出了一种用于自动操作和恢复的分析算法, 决策树用于创建告警之间的模式作为关联规则. 决策树算法具有构造速度快、 分类精度高以及自适应性强等特点, 可用于网络故障管理. 本文利用决策树算法, 对告警数据中的特征信息进行分析, 找出对根源信息影响较大的特征, 从而辅助网络管理人员有针对性地了解特征信息, 快速解决网络异常问题.
1.1 数据收集
为客户提供高质量、 高水平的网络通信服务对网络运营商十分重要. 当通信网络出现故障或异常时, 极大可能会映射到网络业务中, 使各类业务受到冲击, 从而导致通信网络事故, 影响客户的使用. 网络故障是网络运行过程中发生的异常现象, 导致设备无法支持正常的网络运行. 设备类型包括PTN(packet transport network)，BSC(base station controller)，ONU(optical network unit)等, 其中PTN设备是用在接入层和汇聚层的光传输设备, 在固网和移动回传中用于传输语音业务和数据业务；
通信BSC是指基站控制器, 为基站收发台和移动交换中心之间交换信息提供接口.
通常, 网络故障首先以告警的形式从设备发出传送到网络管理系统(network management system, NMS), 然后NMS对监控到的数据进行管理和分析, 同时, NMS会在第一时间处理告警信息并安排专业人员进行设备检修. 移动运营商收集、 处理NMS报告的大量原始告警数据, 这些数据不仅包括由网络设备生成的告警信息, 还包括NMS统计的其他信息, 收集到的数据信息分为告警数据、 派单数据、 拓扑数据. 其中告警数据表示网络状态的症状信息；
派单数据表示故障设备的检修信息；
拓扑数据表示网络节点间的链路关系. 数据收集过程如图1所示.
图1 数据收集过程Fig.1 Data collection process
1.2 数据预处理
在通信网络中, NMS监控到的由网络设备产生的告警数据规模庞大且复杂多变, 因此通过分析告警数据获得各类告警信息之间的从属关系, 并从中挖掘能反映故障的根源告警对网络管理人员十分必要, 而对海量告警数据进行数据预处理, 压缩告警, 减轻网络管理人员的工作量是首要任务. 数据预处理过程如图2所示.
1) 数据合并：
单个告警集多数以5 h为时间单位, 不足以支撑实验分析, 因此需将一系列的告警集合并生成大数据集, 如图2(A)所示.
2) 地域划分：
告警的相关性分析一般只考虑了时间上的相关性, 对合并后的告警按地域划分, 对每个城域的告警进行单独分析, 如图2(B)所示.
3) 告警时长处理：
根据派单数据依次计算派单数据中相邻告警发生、 清除时间的时间差, 根据派单数据时间确定告警数据相邻告警的时间差, 如图2(C)所示.
4) 特征提取, 缺失值、 冗余值处理：
针对告警信息特征繁多、 重复性和缺失性的特点, 对其进行特征提取、 删除缺失值和冗余值操作, 如图2(D)所示.
算法1TimeDiff算法.
输入:TTs,TTe,TAs,TAe：
派单数据和告警数据的告警开始、 结束时间；
输出:TdTA；
步骤1)TdTA=[ ]
步骤2) forTTsti∈TTsdo
步骤3) Time difference:TTdsi=TTsti+1-TTsti,i=0,1,2,…
步骤4) forTTeti∈TTedo
步骤5) Time difference:TTdei=TTeti+1-TTeti,i=0,1,2,…
步骤6)ws=[TTdsmin,TTdsmax],we=[TTdemin,TTdemax]
步骤7) forTAstj∈TAsdo
步骤8)TAdsj=TTstj+1-TTstj,j=0,1,2,…
步骤9) forTAetj∈TAedo
步骤10)TAdej=TTetj+1-TTetj,j=0,1,2,…
步骤11) whileTAdsj∈wsandTAdej∈wethen
步骤12) addTAjtoTdTA
步骤13) continue
步骤14) ReturnTdTA.
图2 数据预处理过程Fig.2 Data pre-processing process
2.1 数据相关性分析
NMS的历史告警信息具有缺失性、 冗余性、 无标记和时空分布性等特征, 因此要构建决策树需先得到标记数据, 可根据告警相关性分析方法获得根源告警信息进而为数据添加标签, 分析步骤如图3所示.
图3 告警数据关联分析步骤Fig.3 Alarm data correlation analysis steps
告警数据中的关联规则算法主要分为经典关联规则挖掘算法和序列模式挖掘算法, 但预处理后的数据不能直接用于关联分析, 需将清洗后的数据根据需求转换为事务数据集的形式, 典型的数据转换方法有固定时间窗口法、 动态滑动窗口法和DBSCAN(density-based spatial clustering of applications with noise)聚类算法等. 采用前两种方法生成告警事务集, 需人为设定窗口的宽度和滑动步长, 虽然简便易用, 但设定的窗口过小或过大, 都可能导致一次性引发的告警未被划归到一个告警事务集中或有过多不相关告警被归并到同一告警事务集中, 从而降低窗口内告警事件关联的整体相关性, 影响关联规则的准确度. DBSCAN聚类生成事务集将相似度大的告警划分为同一类别时, 会自适应地调整时间窗规模, 使各告警更具关联性, 也可加入其他告警信息进行事务集划分, 进一步增强各告警的相关联性.
关联规则是用来反映一条告警与其他告警的相互依存性和关联性, 用于从大量告警数据中挖掘出告警项之间的有效相关关系. 关联规则的目标是发现频繁项集, 发现满足最小支持度的所有项集, 从而进一步发现强关联规则, 从频繁项集中筛选出满足高置信度的规则.
定义1支持度定义为关联的告警数据在告警事务集中出现的次数占告警事务集D的比例, 公式为
(1)
其中X,Y表示两条不同的告警.
定义2置信度定义为一条告警数据出现后, 另一条告警出现的概率, 或者称为条件概率.规则的置信度为
(2)
告警关联分析在告警事务集合D中发现既满足最小支持度又满足最小置信度的告警关联规则, 即发现强关联告警关联事件.强关联告警事件中各告警通过置信度互相影响, 根据置信度确定的最主要告警, 称为根源告警, 其他统一称为非根源告警.得到根源告警后, 结合派单数据, 即管理员对网络异常进行的检修信息, 以及历史经验对根源告警进行匹配, 从而确定最终根源告警集.根源告警集包含的根源告警和非根源告警为决策树添加标记.
2.2 告警特征多维化
要构建决策树, 需先对提取后的由NMS采集到的数据特征进一步归一化处理, 使告警数据格式统一, 方便生成决策树. 在分析多维特征对告警的影响时, 在告警数据集S={F,Y}中, 其中特征集F={告警级别,告警对象类型,对设备影响,对业务影响,告警逻辑分类},Y={根源信息}为分类标准.通信网络中,F的特征对告警数据的根源故障挖掘均有一定影响.通常告警影响越严重, 越有可能是根源告警或接近根源故障.告警级别越高越严重, 对设备和业务的影响程度越大, 对根源告警越有影响, 告警逻辑分类越接近物理逻辑, 越有可能是根源告警或者越接近根源故障.因此, 需找出影响根源告警或根源故障的最主要特征及特征值.各告警特征内部的特征值是离散且相互独立的, 因此可用One-Hot编码将特征数字化. 对告警原因进行分析时, 主要是对告警标题这一特征进行分析, 因为告警标题内含有告警原因. 一维特征在执行决策树算法时无法进行决策分支, 因此需对告警标题进行升维, 若是该告警表示为1, 否则表示为0, 如表1所示, 此时告警数据集中F为告警原因, 即F={B3_EXC,ETH_LOS,CE,…}.
表1 告警原因升维
2.3 构建决策树
告警数据关联分析得到标记数据且对告警特征One-Hot编码、 升维后开始构建决策树. 构建决策树的关键是如何在5类特征中选择最优划分特征. 在划分过程中, 需尽可能实现节点的高“纯度”. 信息熵(information entropy)和基尼指数(Gini index)是度量告警集纯度的常用指标. 假设告警数据集S中第k类样本所占比例为pk(k=1,2,…,|m|), CART(classification and regression tree)算法使用基尼指数选择划分特征,S的基尼值定义为
(3)
与信息熵相同, Gini(S)值越小, 则S的纯度越高.对离散特征f有N个可能的取值{f1,f2,…,fN}, 用f对S划分时会产生N个分支节点,Sn用于描述包含在S中全部在特征f上取值为fn的样本的第n个分支节点, 以此对S进行划分得到的基尼指数表示为
(4)
与信息增益相反, 使用基尼指数作为指标时, 应该选择基尼指数最小的特征作为最优划分特征, 即
(5)
信息熵复杂度为O(log2n), 基尼指数复杂度为O(n2), 由于对数函数计算复杂度较高, 因此, 在告警数据量十分庞大的情况下不利于实现, 基尼指数的提出恰好解决了该问题.基本决策树的构造方法忽略了噪声的问题, 决策树在决策分支过程中可能会学习过好, 即产生过拟合现象, 降低决策树的分类性能.引入剪枝技术可克服告警噪声数据对决策分类的不良影响, 同时保证准确率.
算法2DecisionTree_pruning.
输入：
告警特征多维化的数据集(S,f);
输出：
Decision tree [ ];
BuildTrees:
步骤1) for attributesfinSdo
步骤2) calculate the Gini (attributes) by formula (4)
步骤3) if Gini (f) satisfy formula (5) then
步骤4) partition (S,f)
步骤5) end for
步骤6) until all partition processed
PrunDepth:
步骤7) create function depth_score (train_score, test_score)
步骤8) best_score=0, para=[apara,bpara]
步骤9) foriin para do
步骤10) score calculate depth_score
步骤11) if score 步骤12) best_score=score 步骤13) end for 步骤14) best_para=depth_score[best_score]. 决策树在训练告警数据集样本时, 会出现几乎所有特征都产生分支的情形, 因而进行剪枝十分必要, 如步骤7)先构建depth_score函数计算得分数据, 当决策树达到best_score时, 将不再进行分裂, 得到最佳参数best_para, 从而在一定程度上防止过拟合. 用决策树性能指标分类正确率(得分)作为决策树分类器的评价指标, 计算的准确率为 (6) 将收集到的原始告警数据经过预处理操作后, 每个区域的告警数量都会得到压缩, 从而节约了后续研究的时间, 提高了准确率, 图4为各区域预处理后的告警数量、 基于地域和时间关联分析得到根源信息的告警量与原始告警量的对比结果及相对原始告警的压缩率曲线. 由图4可见, 10个地区告警数据预处理后的压缩率约为70%, 基于地域和时间关联分析后压缩率约为90%. a. 小店区; b. 杏花岭区; c. 万柏林区; d. 迎泽区; e. 太原市区; f. 尖草坪区; g. 普源区; h. 清徐县; i. 古交市; j. 阳曲县.图4 各地区相对原始告警的告警量及压缩率Fig.4 Alarm volume and compression rate of each region relative to original alarms 对压缩后的告警数据进行相关性分析后, 将挖掘出的强关联规则与历史案例和派单数据进行匹配判断根源信息, 得到部分强关联事件及根源信息列于表2. 表2 部分强关联事件以及根源信息 图5 剪枝后决策树Fig.5 Post-pruning decision tree 对根源告警信息以及特征进行决策树算法分析, 用函数depth_score限定决策树分裂, 在一定程度上防止过拟合提高算法得分. 图5为max_depth=5时达到best_score输出的决策树. 其中根源告警包含的告警原因主要为B3_EXC,ETH_LOS,ELAN_AUTO_LOOP,CE和NE五种. ETH_LOS为网口连接丢失告警, 表示以太网端口接收不到以太网信号, 在告警逻辑分类中为通信告警, B3_EXC和ELAN_AUTO_LOOP的告警逻辑分类也为通信告警. 因此, 从告警逻辑分类看, 实验结果表明根源告警多为通信告警, 由根源告警衍生的告警所属逻辑分类则以链路告警、 协议告警和硬件告警居多, 如图6所示. 分析多维特征对告警的影响时, 获取告警逻辑分类等5个特征的分类重要性, 通过对10个地区的告警数据建立决策树模型得到结果, 图7为小店区、 杏花岭区与太原市区3个地区的5个特征的特征重要性, 其中告警逻辑分类、 告警对象类型对根源信息影响较大且稳定. 表3列出了逐次加入各特征时决策树分类的正确率. 由表3可见, 在告警对象类型加入告警逻辑分类特征后, 准确率变化最大, 约为5%. 图6 告警逻辑分类中的衍生关系Fig.6 Derivative relations in alarm logic classification 图7 3个地区5个特征的影响比较Fig.7 Comparison of impact of five features in three regions 表3 加入特征的正确率 综上所述, 本文针对通信网络中网络异常原因分析的问题, 提出了一种基于决策树进行告警数据特征分析的方法. 首先将告警数据按地域进行划分, 在对时间相关性进行分析的同时加强了对空间地域相关性的分析, 再对依据地域、 空间相关性分析后得到的根源信息建立决策树， 以对多维特征进行分析, 找出影响告警产生的特征. 本文得到的最主要特征为告警逻辑分类和告警对象类型, 以通信告警居多, 可根据特征值提前采取措施, 以减少网络异常的出现并降低由网络异常带来的损失.
