A unifying framework for detecting outliers and change points from non-stationary time series data

ABSTRACT

We are concerned with the issues of outlier detection and change point detection from a data stream. In the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. Specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. Although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. Then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.

REFERENCES

• 1: H. Akaike and G. Kitagawa, Practices in Time Series Analysis I, II, Asakura Shoten (in Japanese), 1994, 1995.
• 2: V. Barnett and T. Lewis, Outliers in Statistical Data, John Wiley & Sons, 1994.
• 3: P. Burge and J. Shaw-Taylor, Detecting cellular fraud using adaptive prototypes, in Proc. of AI Approaches to Fraud Detection and Risk Management, pp:9--13, 1997.
• 4: Tom Fawcett , Foster Provost, Activity monitoring: noticing interesting changes in behavior, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.53-62, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312195]
• 5: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 6: 2S. B. Guthery, Partition regression, Jr. Amer. Statist. Ass., 69:945--947, 1974.
• 7: D. M. Hawkins, Point estimation of parameters of piecewise regression models, Jr. of the Royal Statistical Society Series C, 25(1):51--57, 1976.
• 8: M.Huskova, Nonparametric procedures for detecting a change in simple linear regression models, in Applied Change Point Problems in Statistics (1993).
• 9: G. Kitagawa and W.Gersch, Smoothness Priors Analysis of Time Series, Lecture Notes in Statistics, 116, Springer-Verlag (1996).
• 10: Edwin M. Knorr , Raymond T. Ng, Algorithms for Mining Distance-Based Outliers in Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.392-403, August 24-27, 1998
• 11: Uzi Murad , Gadi Pinkas, Unsupervised Profiling for Identifying Superimposed Fraud, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.251-261, September 15-18, 1999
• 12: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Proceedings of the NATO Advanced Study Institute on Learning in graphical models, p.355-368, March 1998, Erice, Italy
• 13: T.Ozaki and G.Kitagawa, A Method for Time Series Analysis, (in Japanese), Asakura Shoten, (1995).
• 14: J. Rissanen, Fisher information and stochastic complexity, IEEE Trans. Inf. Theory, IT-42, 1, pp. 40--47 (1996).
• 15: Kenji Yamanishi , Jun-Ichi Takeuchi , Graham Williams , Peter Milne, On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.320-324, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347160]
• 16: Kenji Yamanishi , Jun-ichi Takeuchi, Discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.389-394, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502570]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Measurement, Performance