On-line outlier and change point detection for time series

Abstract

The detection of outliers and change points from time series has become research focus in the area of time series data mining since it can be used for fraud detection, rare event discovery, event/trend change detection, etc. In most previous works, outlier detection and change point detection have not been related explicitly and the change point detections did not consider the influence of outliers, in this work, a unified detection framework was presented to deal with both of them. The framework is based on ALARCON-AQUINO and BARRIA’s change points detection method and adopts two-stage detection to divide the outliers and change points. The advantages of it lie in that: firstly, unified structure for change detection and outlier detection further reduces the computational complexity and make the detective procedure simple; Secondly, the detection strategy of outlier detection before change point detection avoids the influence of outliers to the change point detection, and thus improves the accuracy of the change point detection. The simulation experiments of the proposed method for both model data and actual application data have been made and gotten 100% detection accuracy. The comparisons between traditional detection method and the proposed method further demonstrate that the unified detection structure is more accurate when the time series are contaminated by outliers.

Keywords

outlier detection / change point detection / time series / hypothesis test

References

[1] YamanishiK., TakeychiJ., WilliansG., MilneP.. Online unsupervised outlier detection using finite mixtures with discounting learning algorithms [J]. Data Mining and Knowledge Discovery, 2004, 8(3): 275-300

[2] Martinez-ÁlvarezF., TroncosoA., RiquelmeJ. C., Aguilar-ruizJ. S.. Discovery of motifs to forecast outlier occurrence in time series [J]. Pattern Recognition Letters, 2011, 32(12): 1652-1665

[3] YangL., WangY.-r., PaiS.-zanne.. Statistical and economic analyses of an EWMA-based synthesised control scheme for monitoring processes with outliers [J]. International Journal of Systems Science, 2012, 43(2): 285-295

[4] ZandiF., NiakiS. T. A., NayeriM. A., FathiM.. Change-point estimation of the process fraction non-conforming with a linear trend in statistical process control [J]. International Journal of Computer Integrated Manufacturing, 2011, 24(10): 939-947

[5] AngiulliF., FassettiF.. Distance-based outlier queries in data streams: The novel task and algorithms [J]. Data Mining and Knowledge Discovery, 2010, 20(2): 290-324

[6] AngiulliF., BastaS., PizzutiC.. Distance-based detection and prediction of outliers [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(2): 145-160

[7] HeZ.-y., XuX.-f., DengS.-chun.. Discovering cluster-based local outliers [J]. Pattern Recognition Letters, 2003, 24(9/10): 1641-1650

[8] YuH.-w., LiZ.-f., BaoZheng.. Residues cluster-based segmentation and outlier-detection method for large-scale phase unwrapping [J]. IEEE Transactions on Image Processing, 2011, 20(10): 2865-2875

[9] ChenY.-x., DangX., PengH.-x., BartJ., HenryL.. Outlier detection with the kernelized spatial depth function [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 288-305

[10] RutsI., RousseeuwP.. Computing depth contours of bivariate point clouds [J]. Computational Statistics and Data Analysis, 1996, 23(1): 153-168

[11] JORDAAN E M. Development of robust inferential sensors: Industrial application of support vector machines for regression [D]. Eindhoven:Eindhoven University of Technology, 2002.

[12] MaruyamaN., MatsyokaS.. Model-based fault localization: Finding behavioral outliers in large-scale computing systems [J]. New Generation Computing, 2010, 28(3): 237-255

[13] TakeychiJ. I., YamanishiK.. A unifying framework for detecting outliers and change points from time series [J]. IEEE transactions on knowledge and data engineering, 2006, 18(4): 482-492

[14] FredrikG.. The marginalized likelihood ratio test for detecting abrupt changes [J]. IEEE transactions on automatic control, 1996, 41(1): 66-78

[15] WangL.-hong.. Change-point estimation in long memory nonparametric models with applications [J]. Communications in Statistics: Simulation and Computation, 2008, 37(1): 48-61

[16] CamciF.. Change point detection in time series data using support vectors [J]. International Journal of Pattern Recognition and Artificial Intelligence, 2010, 24(1): 73-95

[17] WillskyA. S.. A survey of design methods for failure detection in dynamic systems [J]. Automatica, 1976, 12: 601-611

[18] KerrT.. Decentralized filtering and redundancy management for multisensor navigation [J]. IEEE Transactions on Aerospace and Electronic Systems, 1987, 23(1): 83-119

[19] Alarcon-AquinoV., BarriaJ. A.. Anomaly detection in communication networks using wavelets [J]. IEEE Proceedings Communications, 2001, 148(6): 355-362

[20] AlexA., HaralambosS., GeorgeB.. A new algorithm for online structure and parameter adaptation of RBF networks [J]. Neural Networks, 2003, 16(7): 1003-1017

[21] Alarcon-AquinoV., BarriaJ. A.. Change detection in time series using the maximal overalp discrete wavelet transform [J]. Latin American Applied research, 2009, 39(2): 145-152

[22] BernardoJ. M., SmithA. F. M.Bayesian Theory [M], 1994NewYorkWiley

[23] KassR. E., WassermanL.. The selection of prior distribution by formal rules [J]. Journal of the American Statistical Association, 1996, 91(435): 1343-1370