基于集成学习的云平台异常点检测

王智远，陈 榕，任崇广

(山东理工大学 计算机科学与技术学院，山东 淄博 255000)

0 引 言

云计算与大数据技术为分布式计算提供了一种解决方案。对于大型的分布式系统，出现异常或请求超时可能带来巨大的损失，而由于系统规模较大，复杂度较高，给系统维护人员带来了巨大挑战。监测告警对于保证云平台的高效性与可用性至关重要，如何全面、精准地定位异常点越来越受到工业界与学术界的关注。

异常点检测是找出被检测样本中行为很不同于预期值的样本，这些样本叫异常点或离群点。常见的离群点检测算法包括基于机器学习的检测模型、基于统计的检测模型、基于线性或非线性的检测模型、基于距离的检测模型等[1]。基于统计的检测模型将违背正常数据分布的样本判为异常点；基于距离的检测模型将远离其它对象的样本判为异常点[2-4]；基于线性与非线性的检测模型将违背数据相关性的样本判为异常点[5，6]；基于机器学习的检测模型将不在超平面内的样本判为异常点[7，8]。

传统基于阈值的异常点检测方法存在适用场景单一、误报率或漏报率高等问题，本文提出了一种基于集成学习的异常点检测系统，对于异常点检测有一定的通用性与有效性。通过监测相似序列的聚类、监测序列的预处理、监测序列特征化、异常点检测器构建、结果评估几个流程对工业界带有标注的监测序列进行异常点检测，实验结果表明，基于集成学习的异常点检测系统效果优于单一检测系统。

1 集成学习

集成学习，有时也被称为多分类器系统，通过构建并结合多个弱检测器来完成检测任务。集成学习先产生一组弱检测器，再按某种策略将它们结合，常可获得比弱检测器显著优越的泛化性能。集成学习方法大致可分为两大类：第一Boosting，该方法弱检测器间存在强依赖关系，需串行生成；第二类是Bagging，该方法弱检测器间不存在强依赖关系，可并行生成[9]。

1.1 Boosting

(1)

(2)

Xgboost对于式(2)利用泰勒公式进行二阶近似展开得到式(3)，求解后得到式(4)，确定树的结构后可用式(4) 求相应的权重值

(3)

(4)

求树的结构时采用贪心算法，求在分裂前后使式(5)减小最大的特征为分裂节点

(5)

其中，ObjnoSplit代表按某个检测特征分裂前的损失，ObjSplit代表按某个检测特征分裂后的损失，GL，GR代表分裂后弱检测器的左子树与右子树上被检测样本损失的一阶导数和，HL，HR代表分裂后弱检测器左子树与右子树相应被检测样本损失的二阶导数和，Tsplit，Tnosplit代表弱检测器分裂前后叶节点的个数，γ为常数项。

1.2 Bagging

Bagging通过构造多个相互独立的弱检测器来提高泛化能力，基本思想是从m个被检测样本中有放回地抽样m个样本得到一个训练集，采样T次得到T个训练集，训练T个检测器，基于一定的投票策略产生最终结果。本文使用了Bagging流派的随机森林[11]，对其基本原理进行分析。

随机森林是Bagging的一个变体，加入了随机特征选择的思想，传统决策树在分类时采用式(6)衡量纯度，在所有特征中选择使式(7)增益最大的特征分裂。而随机森林的每个弱检测器随机选取k个检测特征进行树的构建，最终结果由多个弱检测器投票产生

(6)

其中，D代表被检测样本，Ck代表第k个类别的样本，K代表所有类的总数

(7)

其中，A代表检测特征，D1、D2代表按相应检测特征划分后的样本，Gini的计算方式为式(6)。

1.3 Stacking

Stacking[12]从原始被检测样本集中训练第一级检测器，由第一级检测器生成新的被检测样本集用于训练第二级检测器。在新的被检测样本集中，第一级检测器的输出作为第二级检测器的输入，第二级的标注与第一级相同。检测器构建阶段，直接将第一级检测器的结果作为第二级检测器的输入容易过拟合，采用k折交叉验证生成第二级的检测集。图1显示了一个检测器生成训练集，测试集的过程，5折交叉验证，其中的一折与其它4折交替，训练预测5次后构成了Model1的次级训练数据，n个检测器最终会构造出m×n的训练集与p×n的预测集，其中m，p为原训练集，测试集的样本个数，利用次级训练测试数据进行学习得到最终结果。

图1 Stacking融合过程

2 监测序列特征工程

监测序列特征化是一个数据处理过程，通过各种运算将原始监测序列处理成异常点检测器可直接训练的数据，特征化是为了更好地捕捉异常值特征，提高检测精度。与原始监测序列相比，特征化的监测序列检测精度有显著提高，特征化过程包括监测序列预处理、监测序列特征化、监测序列特征选择。不同监测序列表现出不同的特性，直接使用原始监测序列构造检测器会造成误报，需要将相同特性的监测序列归为一类，同一类序列统一训练检测。原始的监测序列值不能很好捕获序列的特性，需要从多个方面构建特征减少误报漏报，更好捕获异常特性。现实场景中异常极少发生，导致标注为异常的样本远少于标注为正常的样本，使用不平衡数据训练的检测器将导致检测器向正常类倾斜，不平衡样本的过采样可以在一定程度上解决正常样本远大于异常样本的问题。将原始监测序列转换成监测序列特征后，需要对监测特征进行特征筛选，使用发挥作用较大的监测特征可提高训练速度与检测速度。对筛选后的监测特征进行主成分分析，消除特征之间的线性关系。

2.1 监测序列聚类

不同特性的监测序列异常表现方式不一样，直接使用原始监测序列构造统一的检测器不能适用于所有场景，因此需要将相同特性的监测序列归为一类，同一类序列统一训练检测。

监测序列X=[x1，x2…xn] 与监测序列Y=[y1，y2,…,yn] 之间的相似度定义为式(8)，m条监测序列的相似度矩阵定义为式(10)，将相似度矩阵作为监测序列聚类的输入

(8)

其中，X，Y代表监测序列，φi(X) 的定义为式(9)，Cov代表协方差，Var代表方差，n代表监测序列的长度，i∈[-n+1，n+1]

(9)

其中，Xn代表监测序列的值

(10)

其中，Cij代表第i个监测序列与第j个监测序列的相似度。

自组织映射(self-organizing maps)算法是一种无导师的聚类方法，可以将多维度的监测序列映射成二维离散变量。SOM网络在样本聚类、样本的组合优化等问题上有着广泛的应用，具有优良的自组织、自适应等特性。SOM网络没有中间层，只有监测序列输入层与输出层，网络将监测序列类别映射到输出层的某个神经元。在训练阶段，各神经元竞争学习，每个监测序列通过计算到神经元之间的距离得到激活结点。计算出激活结点后，对相关结点的参数迭代更新；在测试阶段，计算待分类的监测序列与各神经元之间的距离，距离最小的神经元为该测试序列的类别。

监测序列相似度矩阵的每行Ci=[Ci1，Ci2…Cin](i=1，2…n) 代表SOM网络的一个待训练监测序列，Wj=[Wi1，Wi2…Win](j=1，2…l，l为输出层神经元的总量)代表输出层神经元的权重向量，通过式(11)计算出与待训练监测序列最匹配的神经元k。计算出最匹配的神经元k后，通过式(12)找到获胜神经元的邻域半径，用式(13)对最匹配的神经元及其邻域内的神经元进行权值更新。对上述操作进行多次迭代，直到映射关系不在发生显著变化

(11)

其中，k代表最匹配神经元的编号，Wj表示与第j个神经元相关的权值系数 (j=1，2…l，l代表输出层的总量)，Ci代表式(10)的一行

(12)

式中：neighbor_redius代表邻域半径，neighbor0代表邻域的初始值，neighbor_para代表邻域参数，t代表网络迭代更新的次数

(13)

式中：wk(t) 代表最匹配的神经元节点更新后的权值，wk(t-1) 代表最匹配神经元节点上次一更新的权值系数，Ci代表式(10)中的一行，ηt代表学习速率，式(14)为ηt的计算公式，式(11)为dk的计算公式，式(15)为σt的计算公式

(14)

其中，learn0为初始的学习速率，learn_para为学习速率参数，t代表迭代次数

(15)

其中，σ0代表邻域函数的初始值，neighbor_para代表邻域参数，t代表网络迭代更新的次数。

与K-Means相比，监测序列采用SOM神经网络进行聚类有以下优点：①在聚类之前，K-Means方法需要确定监测序列的类别总量(K值)，而监测序列的类别总量与SOM神经网络输出层神经元个数是多对多的关系，无需指定该值，因此K值对K-Means方法影响较大；②监测序列使用K-Means聚类后，只对相应簇的中心迭代更新，而SOM神经网络聚类会迭代更新最匹配神经元及邻域神经元的权重系数，因此，SOM神经网络聚类相对于K-Means聚类不易受噪声点的影响，抗干扰性更强；③SOM神经网络输出层的拓扑关系较明确，可视化较好。

2.2 监测序列预处理

监测数据在采集的过程中不可避免的会出现漏采的现象，因此需要对数据的缺失值进行填充。本文利用牛顿插值法进行缺失数据处理，先求出f(x)的各阶差商，再利用式(16)进行缺失值填充。

对于异常检测，监测序列的标注大部分是正常的，只有少量序列的标注为异常。在检测器构建阶段，如果标注为异常的监测序列较少，检测器从异常类学习到的信息就少，很难检测异常类。直接使用原始数据建模会导致模型偏向于正常一类，导致异常点的漏报与误报。本文对监测序列进行SMOTE过采样操作，采样之后正常监测序列的数量：异常监测序列的数量≈1∶1。

由于异常对象多种多样，直接使用原始值检测器的效果较差，需要考虑监测序列的数据结构与一些隐含特性，从多方面对原始序列进行特征转换。本文参考Opprentice框架[13]和动态数列提取特征的方法，对原始监测序列进行统计特征转换、拟合特征转换、分解特征转换

f(x)=f(x0)+f[x0,x1](x-x0)+
f[x0,x1,x2](x-x0)(x-x1)+…+
f[x0,x1,…,xn-2,xn-1](x-x0)(x-x1)…
(x-xn-2)(x-xn-1)+f[x0,x1,…,xn-1,xn]
(x-x0)(x-x1)…(x-xn-1)(x-xn)

(16)

2.3 特征构建

监测序列是在时间维度上呈现一定规律性的动态序列，对原始监测序列进行统计特征转换、拟合特征转换、分解特征转换，具体的特征见表1。

表1 特征

监测序列的统计特征对业务人员关注的指标进行统计方面的刻画。如果监测的业务指标出现非常大或非常小的反常变化，该业务指标在反常值的时间点可能出现了异常。业务指标的z-score值代表监测序列的每个点相对于整体基线的偏离程度，距离基线越远越有可能是异常，很多现实的业务一天一周期，因此计算整体基线时以天为单位。业务指标的同比差分反映了现时刻与上一周期同时刻的差值情况，环比差分反映了现时刻与上一时刻的差值情况，同比差分或环比差分值越大，越有可能是异常。

监测序列的分解特征将序列分解成周期序列、趋势序列、随机序列，如果分解后的序列存在非常大或非常小的反常变化，该业务指标在反常值的时段可能出现了异常。在文件系统中，磁盘利用率是业务人员很关注的一个指标，将该指标分解后可从趋势序列分析使用情况，趋势序列陡增或持续增加考虑异常或扩容，趋势序列陡降或一直很低考虑异常或缩容；对于具有周期性的业务指标，分解后对周期序列进行分析，如果某个周期序列相对于其它周期非常大或非常小，则该业务指标在反常值的时间点可能出现了异常。每个业务指标都有随机成分，如果分解后的随机序列存在非常大的波动，则该业务指标在反常值的时间点可能出现了异常。小波分解对业务指标进行频率方面的刻画，按天将监测序列分解为高频、中频、低频3个序列，高频序列对监测指标短期内的陡升或陡降类异常识别较好，低频序列对监测指标长期内的持续升高类异常识别较好。

监测序列的拟合特征综合序列的趋势性、周期性、历史性对序列的期望值进行预测，真实值与期望值差别差值越大，相应的指标在异常值的时间点可能出现了异常。监测序列是动态数列，在时间维度上具有一定的规律性，预测点受相邻点的变化规律影响较大，距离越远的点对预测的贡献度越小。监测序列的指数平滑预测法可以消除毛刺，通过平滑系数控制历史值对当前预测值的影响，对持续上升或持续下降类的业务异常识别效果较好；监测序列的移动均值法将窗口内的序列均值作为期望值，序列值与期望值差值越大越有可能是异常，移动均值预测法可以消除序列的随机噪声；序列的三次指数平滑预测法综合趋势、周期、随机因素对期望值做出预测，距离预测点越远对预测点的影响越小，序列值与期望值差值越大越有可能是异常；ARIMA对原始序列进行差分操作去除序列不平稳因素，结合历史值与历史噪声值对期望值进行预测，序列值与期望值差值越大越有可能是异常。

监测序列特征化后，某些特征对于检测的贡献度较小或有冗余特征，为了降低时间复杂度进行特征选择与特征降维。序列标注与特征之间的互信息描述了特征包含标注的信息量，将互信息作为贡献度，计算出贡献度后本文选取贡献较大的度前70%特征作为候选特征。检测器进行异常检测时可能存在冗余特征，需要对候选特征进行降维处理，采用PCA进行主成分提取(主成分占比90%)。

3 基于集成学习的异常点检测系统

图2是基于集成学习的异常点检测算法的基本框架，检测流程包括离线训练检测器、在线使用检测器、检测器迭代更新。离线训练阶段，将具有相同特性的监测序列归为一类形成该类的训练集，利用训练集训练出该类的最优检测器。在线检测阶段，根据训练好的网络识别出待测试监测序列的所属类别，用相应类的检测器进行检测。检测器迭代更新阶段，将检测器检测为异常但标注为正常的监测序列、检测器检测为正常但标注为异常的监测序列、新收集的监测序列作为回注训练集，定期用回注训练集对检测器迭代更新。离线检测器构建提供检测器是正反馈，在线检测器提供错检、漏检样本是负反馈，检测的整个流程是闭环，随着迭代轮数的增加，异常点检测系统的准度逐渐增加，抗干扰能力逐渐增强，直至达到一定程度的收敛。

图2 异常点检测框架

3.1 单检测器构建

对监测序列进行归属类计算、预处理、特征化、筛选降维、样本均衡后，形成离群点检测器所需要的数据格式，每个簇采用相同的训练方式。对每个簇按8∶2划分离线训练集与在线测试集，在离线训练集上进行训练，在线测试集上进行检测。单检测器的结构为Xgboost检测器、Random forest检测器、Bagging检测器(基学习器为Logistic回归)、Bagging检测器(基学习器为神经网络)，使用网格搜索进行参数调优。

3.2 多检测器融合

检测器融合综合考虑不同模型的优缺点，将它们的结果融合到一起对于检测结果的提高有一定帮助。检测器融合的优点有：①减少因误选单检测器而导致泛化性能不佳的风险；②降低陷入局部极小点的风险；③可以扩大假设空间，得到更好的近似。

本文考虑到Random forest检测器是低方差的模型，Xgboost检测器是低偏差的模型，利用Stacking方法将两者融合，可能会在低方差与低偏差之间找到最优解。设计了两层Stacking模型，第一层包含3个低方差模型：Random forest检测器、Bagging检测器(基检测器为逻辑回归)和Bagging检测器(基检测器为神经网络)，在生成监测序列样本时每个检测器进行5轮交叉验证；融合模型的第二层是Xgboost检测器，第二层利用第一层生成的监测样本训练与预测。融合结构如图3所示。

图3 检测器融合

3.3 实验评估

本文采用真实场景带标记的数据集(http://iops.ai/，数据量约300兆)进行检测，异常样本标记为1，正常样本标记为0，共26个监测指标。聚类后形成6类序列，每类序列分为离线检测器训练数据和在线检测器使用数据(随机划分)，划分比例为8∶2，离线检测器训练数据分为训练集和模型选择验证集(随机划分)，划分比列为7∶3。

实验环境为：英特尔i7 8700K(3.7GHz,六核心)，金士顿内存条(16 G)。

检测器构建阶段采用ROC曲线对训练的结果评估，ROC曲线是反映敏感度和特异度连续变量的综合指标，ROC曲线的横坐标为FPR(false positive rate)，纵坐标为TPR(true positive rate)，计算方式为式(17)

(17)

其中，TP(true positive)为真阳性，代表数据集的标注为异常且检测器检测为异常的个数；FP(false positive)为假阳性，代表数据集的标注为正常且检测器检测为异常的个数；TN(true negative)为真负性，代表数据集的标注为正常且检测器检测为正常的个数；FN(false negative)为假负性，代表数据集的标注为异常且检测器检测为正常的个数。

每个监测序列的异常概率值可以作为检测阈值，得到一组FPR和TPR，利用所有组绘制得到ROC曲线。计算ROC曲线与水平轴之间的面积可以得到AUC，AUC的范围为[0,1]，AUC≈1，说明检测器检测结果接近完美，AUC在0.7-0.9之间，说明检测器检测精度较高，AUC=0.5，说明检测器检测效果很差。

训练后序列1在离线验证集上融合前后的ROC如图4(其它的簇的AUC值波动在[-0.02,0.03]，融合后的检测器AUC值均优于单检测器)所示。

图4 融合检测模型与单一检测模型ROC曲线

利用在线测试数据评估各检测器的效果，评估的标准为式(18)F1-score，表2为各检测器的F1-score均值(在6类监测序列的测试结果上取了均值)，表中效果最好的是融合检测器，表明检测器的融合对于检测结果的提升有非常大的帮助

(18)

其中，precision为检测的准确率，recall为检测的召回率。

表2 在线检测结果

准确率precision的计算方式如下

(19)

其中，TP(true positive)为真阳性，代表数据集的标注为异常且检测器检测为异常的个数；FP(false positive)为假阳性，代表数据集的标注为正常且检测器检测为异常的个数。

召回率recall的计算方式如下

(20)

其中，FN(false negative)为假负性，代表数据集的标注为异常且检测器检测为正常的个数。

4 结束语

本文设计了一个异常点检测系统，系统由检测器的构建、检测器的使用、检测器的迭代更新构成。离线检测器构建提供检测器是正反馈，在线检测器提供错检、漏检样本是负反馈，随着迭代次数的增加，系统的精度会逐渐提高；异常点检测系统的特征构建阶段可以增加与修改特征，扩展性较好。对异构的检测器进行基于委员会的学习，提高了异常点检测的精度与泛化性。实验中的随机森林与Xgboost均可并行计算，对于工业界的大数据具有适用性。异常点检测特征依赖于人的先验知识，如何利用深度学习模型自动学习特征是本文下一步的研究重点[14]。