结合局部加权回归的时序异常检测方法研究

江新乐 龙军 陈刚 夏雷 梁多姿 刘丽敏 范慧龙

摘  要：局部加权回归是非参数学习方法，可自动规避在数据拟合过程中异常值对近邻点的影响。通过使用基于局部加权回归的时间序列分解方法，我们对时间序列进行特征分解，将原始时间序列分解为趋势项、周期项和残差项;在给出合理的检出水平阈值后，我们使用改进的格雷布斯检验法在得到残差项后对残差项进行异常值检测。经过实验证明，该方法相比传统的时间序列方法三次指数平滑法可减低离群值对模型拟合的影响，更能有效适应数据中潜存的趋势项的复杂变换，从而更加精准地找到数据中的真实异常点。

关键词：局部加权回归;时间序列分解;假设检验;异常检测

中图分类号：TP309     文献标识码：A

Research on Time Series Anomaly Detection Based on Locally Weighted Regression

JIANG Xinle1，LONG Jun2，CHEN Gang1，XIA Lei1，LIANG Duozi1，LIU Limin2，FAN Huilong2

（1.Information Technology Department，China Railway Shanghai Group Co.，Ltd.，Shanghai 200071，China;

2.School of Computer Science and Engineering，Central South University，Changsha 410083，China）

Abstract：Locally Weighted Regression is a non-parametric method，which can automatically avoid the influence of anomaly values against adjacent data in the process of data fitting.By means of time series decomposition method based on Locally Weighted Regression，the original time series can be decomposed into trend，seasonality and residual.After reasonable threshold of detection level is given，we implement anomaly detection for the residual gained by the improved Grubbs testing method.Experiments show that compared with traditional time series method-Holt Winters，this method can reduce the effect of outliers during model fitting process，and adapt the complex variation of the trend in the data more effectively so as to find the real anomaly in the data accurately.

Keywords：Locally Weighted Regression;time series decomposition;hypothesis testing;anomaly detection

1   引言（Introduction）

智能运维将传统机械、人力驱动的监、管、控运维平台，逐步转变成为依托于大数据技术和人工智能技术的智能运维平台。大数据技术，人工智能技术是智能运维平台的核心驱动力：大数据技术可以帮助IT运维人员快速，全面的处理过去无法处理的海量机器数据，发掘其中“信息寶藏”，从而为企业带来极大业务价值;而人工智能技术的算法模型，通过大量有价值的机器数据训练和自我调参，使得机器可以学习到“知识”，赋予运维以“智慧”，大大提升运维分析和判断力并通过前所未有的智能技术帮助企业降低风险和成本，帮助IT部门敏捷的应对企业业务快速变化。

运维过程中由于其复杂的性质是容易出现性能异常的。虽然以前的工作已经表明使用统计学习来检测性能异常的有效性，但以前的方案基本都是采用监督学习方式，即往往需要标记训练数据，这需要大量的人力成本，并且需要花费大量的时间及数据进行训练，并且只能处理以前已知的异常。针对以上情况我们自研并落地了基于智能无监督的行为学习（UBL）运维系统。UBL系统利用自组织映射来捕获系统行为并预测未知异常。考虑到部署的灵活性，UBL可以使用基础架构中的剩余资源进行行为学习和异常预测，能保证其开销甚微。我们在多个分布式平台和系统上进行广泛的实验和验证。研究结果表明，UBL可以高准确性地同时预测多个异常指标，通过关联分析多指标的异常准确定位问题，不仅如此，无监督行为学习ULB系统还能以充裕的时间提前量实现故障自动预测。

本论文定位于智能运维之无监督行为学习实现指标异常检测算法的研究，是集团公司借助大数据及人工智能技术来改变传统运维固有的方式，以解决集团公司实际运维过程中痛点及难点的一次重要尝试。

2   局部加权回归法（Locally weighted regression）

2.1   局部加权回归概念

局部加权回归[1]是一种非参数学习方法，在拟合具有复杂波动性的数据时相比传统的线性回归和多项式回归表现优秀，因为通常情况下的线性拟合不能很好地预测所有的值，因为它容易导致欠拟合（under fitting），比如数据集是一个钟形的曲线。一个方法是多项式或者其他函数如正余弦等等，多项式甚至能拟合所有数据，但是在预测新样本的时候又会变得很糟糕，因为它导致模型的过拟合[2]（overfitting），不符合数据背后的“逻辑”。而通过采用局部加权回归方法，既避免了复杂的参数调整过程，又不会出现“过拟合”或者“欠拟合”的问题。局部加权回归通过每个实际点的权重代表实际值相对于其他位置值的可靠性[3]，在每次迭代过程中更新样本权重，则可以不断将拟合过程中每个样本的可靠性进行调整，从而使得异常点对拟合值的影响降到最低。

2.2   局部加权回归的过程

假设和为自变量和因变量，Loess（Locally weighted regression，局部加权回归）回归曲线可认为是对于、的平滑曲线[4]，的计算方法如下：

对于一个正整数，目前假设小于，值代表与最接近的个点，而且每一个点根据其与的距离给出一个邻近权重。假设是指距离点第个远的点的距离。让表示三次方程：

则对于，其邻近权重为：

由于的取值可无最大限制，现在我们假设，此时是中与最远点的距离;对于，我们定义：

然后我们像之前一样使用定义邻近变量。

局部加权回归的损失函数如下：

同理推导：

其中，α为是权重的对角矩阵。对w求导得到：

所以得到：

其加权矩阵为：

在得到其加权矩阵后，我们可通过回归计算得到其原始序列的拟合值，并通过迭代不断调节权重矩阵中每个点的权重，从而降低离群点的影响，使得拟合效果最优。

迭代过程如下：

首先，已知原始值序列为，拟合序列为，残差为：，记s为的中位数，则对任意一点k：

其权重调整值为：

其修正后的权重为：。

在得到其权重调整值后，我们可一直更新每个点的权重，从而在计算出新的后进行权重调整。

2.3   基于局部加权回归的时间序列分解

时间序列分解方法[5]將原始时间序列分解为：趋势项、季节项、余项，其中趋势项是指数据中蕴含的长期的波动情况，不会在短期内发生剧烈变化，而季节项指原始序列中不同周期间具备的相同走势和变化，余项是指原始序列减去趋势项、季节项后的剩余部分;趋势项[6]、季节项都是相对稳定的分量，而经过分解后的余项可被视为是符合正态分布的，由此我们便可以通过假设检验[7]方法对余项进行分析，从而寻找数据中的异常点。

我们以表示原始的时间序列，则有以下假设：

其中，Tv表示v点的趋势分量，Sv表示v点的季节分量，Rv表示v点的余项。

基于局部加权回归的时间序列分解方法分为内循环、外循环[8]，其中内循环主要做了趋势分量和周期分量的计算，假定、为内循环中第k-1次结束时的趋势分量、周期分量，初始化时，并有以下参数：

①内层循环数

②外层循环数

③一个周期的样本数

④Step2中局部加权回归平滑参数

⑤Step3中局部加权回归平滑参数

⑥Step6中局部加权回归平滑参数

每个周期相同位置的样本点组成一个子序列，容易知道这样的子序列共有个，我们称为cycle-subseries;内循环主要分为以下六个步骤：

Step 1：去趋势，减去上一轮结果的趋势分量，。

Step 2：周期子序列平滑，使用局部加权回归对每个子序列做回归，并向前向后各延展一个周期;平滑结果组成 temporary seasonal series，记为

Step 3：周期子序列的低通量过滤，对上一个步骤的结果序列依次做长度为、、3的滑动平均，然后做局部加权回归，得到结果序列

Step 4：去除平滑周期子序列趋势：

Step 5：去周期，减去周期分量：。

Step 6：趋势平滑，对于去除周期之后的序列做局部加权回归，得到趋势分量。

外循环主要用于调节每个点的权重，如果数据序列中存在异常点，则该点余项会较大，定义

对于位置为的数据点，其权重为：

其中，B为bisquare函数：

然后在每一次迭代的内循环中，在Step 2与Step 6中做局部加权回归时，将每个点的原始权重乘以，以减少异常点对回归的影响[9]。

图1 时序分解图

Fig.1 Time series decomposition

3 基于假设检验的异常值检测方法（Anomaly detection method based on hypothesis testing）

在完成时间序列分解后，我们抽取余项进行格雷布斯检验。

格雷布斯检验是对于类正态分布样本中异常点的检验方法，该方法最初是用来检验单个异常点的，我们通过对已知异常点进行剔除，重复计算剩余样本中的异常点，便可以使用格雷布斯检验按照余项的绝对值大小对余项进行排序后进行多异常点的检验[10-12]。

格雷布斯检验法有以下统计量：

其中，表示当前数据集的样本均值，s表示当前数据集的样本方差。

通过设定检出水平，可在附表中查出其临界值。

图1为附表部分。得到临界值后，可对当前序列中绝对值最大的点或进行异常判定：

上侧判断：当时，判定为异常点，否则非异常点;

下侧判断：当时，判定为异常点，否则非异常点。

因此我们在设定检出水平后，便可快速进行异常检测。

4   实验结果（The experimental results）

实验数据选择真实来源的CPU数据、交易量数据，数据大小分别为Data1、Data2（43200个数据点，时间跨度30天，数据的时间间隔为1min），Data3、Data4（86400个数据点，时间跨度60天，数据的时间间隔为1min）。为了验证算法的准确性，我们采用F1-Score、精度、召回率进行算法的准确性评估，并与传统的时间序列方法三次指数平滑法（Holt-winters）、基于统计的3σ准则方法进行对比。对比结果如下：

从实验结果中可以看到，3σ准则算法由于未考虑到数据的时间特性，只从统计方面进行异常度量，其准确率及召回率远低于其他算法，而Holt-winters三次指数平滑法由于受到异常值对模型拟合的影响，其整体效果也是差于基于采用局部加权回归的时间序列分解方法和假设检验的无监督异常检测算法的。

5   结论（Conclusion）

将局部加权回归算法融入时间序列分解模型中，通过自动调节权重的方式可以有效提升算法对正常值的拟合精度，并结合假设检验方法进行异常检测使得检测效果更加优秀，为实时、精准的发现业务故障、为生产环境护驾保航。

参考文献（References）

[1] Robert B.Cleveland，William S.Cleveland，Jean E.McRae，et al.STL：A Seasonal-Trend Decomposition Procedure Based on Loess[N].Journal of Offical Statistics，1990：3-72.

[2] Nawar N.Chaker，Doug Walker，Edward L.Nowlin，et al.When and how does sales manager physical attractiveness impact credibility：A test of two competing hypotheses[J].Journal of Business Research，2019，1（6）：105.

[3] 楊永娇，邱宇，占力超.基于宽度学习的智能电网数据服务器流量异常检测算法[J].计算机与现代化，2019（09）：77-82;89.

[4] Jia Zhang，Zhiyong Li，Ke Nai，et al.DELR：A double-level ensemble learning method for unsupervised anomaly detection[J].Knowledge-Based Systems，2019，2（6）：181.

[5] 杨姣，高仲合，王来花.网络数据流异常检测研究[J].通信技术，2019，52（01）：129-133.

[6] 陈波，刘厚泉，赵志凯.时间序列多尺度异常检测方法[J].计算机工程与应用，2018，54（20）：122-127.

[7] 杨金艳，江曾杰，陈伟.稳健统计与格拉布斯准则在能力验证结果分析中的应用[J].计量学报，2018，39（06）：862-867.

[8] D.F.Andrews.A Robust Method for Multiple Linear Regression[J/OL].Technometrics，1974，16（4）：523-531.

[9] 李忠武.时间序列分析与数据挖掘[J].电子商务，2016（11）：41-44.

[10] 孟永伟，秦涛，赵亮，等.利用残差分析的网络异常流量检测方法[J/OL].西安交通大学学报.http：//kns.cnki.net/kcms/detail/61.1069.T.20190808.1349.002.html，2019-09-11.

[11] Treant.时间序列分解算法：STL[EB/OL].https：//www.cnblogs.com/en-heng/p/7390310.html，2016.

[12] batistuta_lj.Grubbs检验法[EB/OL].https：//wenku.baidu.com/view/84695b4e852458fb770b56bb.html，2010-11-19.

作者简介：

江新乐（1963-），男，本科，高级工程师.研究领域：信息化管理.

龙   军（1972-），男，博士，教授.研究领域：计算机科学.

陈   刚（1976-），男，本科，高级工程师.研究领域：信息化管理.

夏   雷（1978-），男，本科，高级工程师.研究领域：信息化管理.

梁多姿（1982-），男，本科，高级工程师.研究领域：信息化管理.

刘丽敏（1976-），女，博士，讲师.研究领域：计算机科学.

范慧龙（1992-），男，博士生.研究领域：计算机科学.