文献标识码:A
DOI:10.16157/j.issn.0258-7998.2015.09.023
中文引用格式:张玲,刘波. 基于残差统计的时间序列加性离群点检测算法研究[J].电子技术应用,2015,41(9):85-87,91.
英文引用格式:Zhang Ling,Liu Bo. Residuals statistics-based additive outlier detection algorithm for time series[J].Application of Electronic Technique,2015,41(9):85-87,91.
0 引言
在时间序列数据挖掘中,不可避免地存在一些远离序列一般水平的极端大值和极端小值,或者与其他序列样本点一般行为或特征不一致的点值,这些点被称做离群点。离群点的产生可能是采样中的误差,也可能是被研究对象本身由于受各种偶然非正常的因素影响而引起的。一方面,离群点的存在会影响时间序列模式表示,可能使数据挖掘陷入混乱,导致在随后的数据处理过程中产生偏差或误导;另一方面,离群点可以提供一些潜在的重要信息。目前,时间序列离群点检测作为对数据进行挖掘处理的第一步,已经成为该研究领域的重要方向之一,并广泛应用于通信流量监测、工业故障诊断、金融贸易等方面。
时间序列中的离群点有很多类型,按照出现的个数,可以分为孤立离群点和成片离群点,按照产生的影响可以分为加性离群点AO(Additive Outlier)、更新离群点IO(Innovational Outlier)、水平移位离群点LS(Level Shift Outlier)和暂时变更离群点TC(Temporary Change Outlier)[1]。本文主要对时间序列中的加性离群点检测方法进行研究,并在此基础上提出了一种基于残差统计的检测方法,仿真结果表明该方法在检测加性离群点方面具有较好的性能。
1 离群点检测方法研究
针对无序的数据集,离群点检测方法主要有基于统计的方法、基于距离的方法[4]、基于密度的方法[5]和基于偏离的方法。近年来,不少研究人员提出了专门针对时间序列的离群点检验算法,主要有统计诊断方法、贝叶斯方法、遗传算法、人工神经网络、小波检测等。国内也有相关人员对此做了深入的研究[2-5]。文献[6]提出了基于粗糙集理论的序列离群点检测方法,它利用粗糙集理论中的知识熵和属性重要性等概念来构建三种类型的序列,并通过分析序列中元素的变化情况来检测离群点。文献[7]通过建立多变量时间序列数据相似度矩阵,对相似度矩阵进行转换以最大化数据之间的相关性,并采用随机游走模型计算数据点之间的连接系数来检测数据点上的异常。文献[8]指出离群点与它所在时间段内的其他数据不具有相似性,从时序图上看,离群点相对于它相邻区域内的数据具有很强的跳跃性,进而提出基于数据相对变化率的时间序列离群点识别方法。
2 基于残差统计的加性离群点检测算法
2.1 问题提出
对于时间序列,离群点可能会隐藏在时间序列的趋势、季节或其他变化中,增加了检测难度。以图1所示的时间序列为例,两个时间序列都处于上升趋势,A点明显偏离了整个趋势,应判定为离群点;B点虽然与前向时刻点在幅度变化率上发生了较大变化,但符合后向时刻点的变化趋势,是一个正常时间序列点,因此不应判定为离群点。
图1 受加性离群点“干扰”的时间序列与正常时间序列
本文以一维时间序列为研究对象,提出了一种基于残差统计的加性离群点检测算法,基本思想是利用p阶AR模型对时间序列进行前向与后向拟合,得到每个时间点拟合残差。采用了邻域区间变化率判别法对离群点进行初判,初判的疑似离群点不参与拟合运算。最后根据高斯分布假设检验的方法对残差进行统计分析并最终确定离群点。
定义待检测时间序列数据样本为xt,t=1,2,3,4…M,xt∈R,并做如下假设:
(1)离群点随机分布;
(2)正常数据的数量远大于离群点数量。
2.2 算法描述
2.2.1 邻域区间变化率
定义1 邻域区间变化率:时间序列各时刻点与相邻前后时刻的幅度变化率。设时刻t的邻域区间变化率为δt,则:
δt=|(xt-xt-1)+(xt-xt+1)|
对所有δt进行考虑,选定门限δ,δ值的计算可以采用平均法或加权计算等。若δt>δ,则将xt标志为LK点(疑似离群点),否则标志为uLK点(非疑似离群点)。
离群点相对于它前后相邻数据都会有较大变化,因此邻域区间变化率要同时对前向时刻和后向时刻进行考虑。定义LK点和uLK点是为了在拟合过程中尽量减少离群点的影响,对疑似离群点不作拟合参考。
2.2.2 AR模型拟合与参数计算
拟合常用的模型有AR模型、MA模型、ARIMA模型等。AR模型一般用于拟合平稳的时间序列,而时间序列从局部来看近似一个平稳的过程,并且AR模型结构相对简单,拟合精度较高,因此本文选用p阶自回归AR模型。为了准确反应各检测点的局部变化属性,并减少离群点对参数估计的影响,本文在文献[9]所采用的两窗口模型基础上,提出了改进的窗口计算模型,基本原理是:检测窗口仅包含t时刻待检测点,前向学习窗口和后向学习窗口位于检测窗口邻近两侧,宽度为N,并且N>p,根据前向和后向学习窗口中的数据分别对t时刻待检测点进行前向和后向拟合,采用剪枝思想,若学习窗口中包含疑似离群点LK,则该点退出学习窗口不参与计算,其余时间轴上的uLK点向t时刻整体移位并填满窗口。如图2所示。
图2 改进的窗口模型
2.2.3 高斯统计检测
基于假设检验理论,在一定的显著性水平下,拟合残差εt近似服从高斯分布,即ε~N(u,σ2)。并且在假设2前提下,高斯分布作为残差统计模型对离群点判决同样具有较高置信度。在此,选择高斯分布做为统计模型,εt的概率密度为:
3 仿真
为了验证本文所提算法的有效性,以局域网内某主机通信流量监测数据为对象进行测试。通信流量监测是网络管理的重要内容,通过流量监测,可以全面透视网络的流量控制,快速定位和发现网络故障,并保障关键应用的稳定运行,减少泄密风险。一般情况下,主机通信流量的具体业务包括Web、Telnet、SNMP、请求应答数据包等,在仿真实验中,通过随机加入异常事件,比如网络拥塞、数据分发等来模拟加性离群点。
图3所示为某日上午8:00-12:00的某主机通信流量监测数据,单位为KB/min,数据样本200个,离群点5个。窗口宽度取15,模型阶数取4,拟合残差分布情况如图4所示。由图看出,拟合后,离群点的残差值与正常的浮动范围相比有较大偏移。
图3 加入AO的通信流量监测数据
为了验证算法对离群点数量的鲁棒性,在200个流量监测数据样本点中分别随机加入5、10、15、20个离群点,拟合计算的窗口宽度取15,模型阶数取4,概率判决临界值分别取0.95、0.95、0.9、0.9。在仿真测试中并未使用离群点数量先验知识。在此定义两个检测指标:
图4 拟合残差
检出率:检测出的真实离群点数量与实际离群点数量之比。
误检率:检测出的错误离群点数量与实际离群点数量之比。
检测统计结果如表1所示。结果显示,当实际离群点数量在样本中的比重小于0.05时,算法能对离群点进行完全有效地检测,当实际离群点数量在样本中的比重大于0.1时,检出率下降,误检率有所上升,但此时离群点的发生不再是小概率事件,根据加性离群点对时间序列产生的影响上看,它不符合加性离群点特征。因此,本文所提算法对检测时间序列中的加性离群点有较好的性能,同时,在实际应用中证明该算法对其他类型离群点的检测也有一定的鲁棒性。
4 结论
本文针对时间序列中的加性离群点检测,提出了一种基于残差统计的检测算法。该算法利用AR模型计算每个样本点拟合残差,通过统计分析残差的概率分布来判别离群点。通过对局域网某主机通信流量监测数据的仿真结果显示,该算法在检测加性离群点方面是有效的,结果有较高的置信度。此外,在对拟合残差进行分析时,除了本文采用的统计模型方法外,还可以采用基于密度的聚类的方法。另外如何检测时间序列中其他类型的离群点也是值得研究的内容。
参考文献
[1] 胡云,王崇骏,谢俊元,等.社群演化的隐健迁移估计及演化离群点检测[J].软件学报,2013,24(11):2710-2720.
[2] Hu Tianming,Sung Sam Yuan.A trimmed mean approach to finding spatial outliers[J].Intelligent Data Analysis,2004,8(1):79-95.
[3] ALARCON-AQUINO V,BARRIA J A.Anomaly detection in communication networks using wavelets[J].Communications,IEEE,2001,148(6):355-362.
[4] 刘耀宗,张宏,孟锦,等.基于小波密度估计的数据流离群点检测[J].计算机工程,2013,39(2):178-181.
[5] 江峰,杜军威,葛艳,等.基于粗糙集理论的序列离群点检测[J].电子学报,2011(2):345-350.
[6] 李权,周兴社.一种新的多变量时间序列数据异常检测方法[J].时间频率学报,2011,34(2):154-158.
[7] 周勇.时间序列时序关联规则挖掘研究[D].成都:西南财经大学,2008.
[8] 苏卫星,朱云龙,胡琨元,等.基于模型的过程工业时间序列异常值检测方法[J].仪器仪表学报,2012(9):2080-2087.
[9] 皇甫堪,陈建文,楼生强.现代数字信号处理[M].北京:电子工业出版社,2003.
[10] 薛安荣,鞠时光,何伟华,等.局部离群点挖掘算法研究[J].计算机学报,2007(8):1455-1463.