Statistical change detection for multi-dimensional data

ABSTRACT

This paper deals with detecting change of distribution in multi-dimensional data sets. For a given baseline data set and a set of newly observed data points, we define a statistical test called the density test for deciding if the observed data points are sampled from the underlying distribution that produced the baseline data set. We define a test statistic that is strictly distribution-free under the null hypothesis. Our experimental results show that the density test has substantially more power than the two existing methods for multi-dimensional change detection.

REFERENCES

• 1: Deepak Agarwal , Andrew McGregor , Jeff M. Phillips , Suresh Venkatasubramanian , Zhengyuan Zhu, Spatial scan statistics: approximations and performance study, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150410]
• 2: Deepak Agarwal , Jeff M. Phillips , Suresh Venkatasubramanian, The hunting of the bump: on maximizing statistical discrepancy, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1137-1146, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109683]
• 3: Charu C. Aggarwal, A framework for diagnosing changes in evolving data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872826]
• 4: Stephen D. Bay , Michael J. Pazzani, Detecting Group Differences: Mining Contrast Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.213-246, July 2001 [doi>10.1023/A:1011429418057]
• 5: J. Bilmes. A gentle tutorial on the em algorithm and its application to parameter estimation for gaussian mixture and hidden markov models, 1997.
• 6: Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, LOF: identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.93-104, May 15-18, 2000, Dallas, Texas, United States
• 7: Dorin Comaniciu, An Algorithm for Data-Driven Bandwidth Selection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.2, p.281-288, February 2003 [doi>10.1109/TPAMI.2003.1177159]
• 8: T. Dasu, S. Krishnan, S. Venkatasubramanian, and K. Yi. An information-theoretic approach to detecting changes in multi-dimensional data streams. In Interface, 2006.
• 9: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. JRSS Series B), 39(1):1--38, 1977.
• 10: B. Efron and R. J. Tibshirani. An introduction to the Bootstrap, volume 57 of Monographs on Statistics and Applied Probability. Chapman and Hall, 1993.
• 11: Edwin M. Knorr , Raymond T. Ng , Vladimir Tucakov, Distance-based outliers: algorithms and applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.237-253, February 2000 [doi>10.1007/s007780050006]
• 12: M. Kulldorff. A spatial scan statistic. Comm. in Statistics: Theory and Methods, 26(6):1481--1496, 1997.
• 13: J.-F. Maa, D. Pearl, and R. Bartoszynski. Reducing multidimensional two-sample data to one-dimensional interpoint comparisons. The Annals of Statistics, 24(3): 1069--1074, 1996.
• 14: R. Miller. Simultaneous Statistical Inference. McGraw-Hill, New York, 1966.
• 15: Daniel B. Neill , Andrew W. Moore, Rapid detection of significant spatial clusters, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014082]
• 16: P. R. Rosenbaum. An exact distribution-free test comparing two multivariate distributions based on adjacency. JRSS Series B), 67(4): 515--530, 2005.
• 17: D. Scott. Multivariate Density Estimation: Theory, Practice and Visualization. Wiley-Interscience, New York, 1992.
• 18: S. Sheather and M. Jones. A reliable databased bandwidth selection method for kernel density estimation. JRSS Series B, (53):683--690, 1991.
• 19: B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, London, 1986.
• 20: M. Wand and M. Jones. Kernel Smoothing. Chapman and Hall, 1995.
• 21: W.-K. Wong, A. Moore, G. Cooper, and M. Wagner. Bayesian network anomaly pattern detection for disease outbreaks. In ICML, pages 808--815, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Reliability

Keywords:
change detection, density test, kernel density estimation