A LRT framework for fast spatial anomaly detection

ABSTRACT

Given a spatial data set placed on an n x n grid, our goal is to find the rectangular regions within which subsets of the data set exhibit anomalous behavior. We develop algorithms that, given any user-supplied arbitrary likelihood function, conduct a likelihood ratio hypothesis test (LRT) over each rectangular region in the grid, rank all of the rectangles based on the computed LRT statistics, and return the top few most interesting rectangles. To speed this process, we develop methods to prune rectangles without computing their associated LRT statistics.

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: ]]A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal Royal Stat. Soc., Series B, 39(1):1--38, 1977.
• 4: ]]S. Dudoit, J. P. Shaffer, and J. C. Boldrick. Multiple hypothesis testing in microarray experiments. Statistical Science, 18:71--103, 2003.
• 5: ]]M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. KDD 1996, pages 226--231, Sept. 1996.
• 6: ]]M. Kulldorff. A spatial scan statistic. Comm. in stat.: Theory and Methods, 26(6):1481--1496, 1997.
• 7: ]]M. Kulldorff. Spatial scan statistics: model, calculations, and applications. In Scan Statistics and Applications, pages 303---322, 1999.
• 8: 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]
• 9: 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]
• 10: Raymond T. Ng , Jiawei Han, CLARANS: A Method for Clustering Objects for Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.1003-1016, September 2002 [doi>10.1109/TKDE.2002.1033770]
• 11: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997
• 12: ]]S. S. Wilks. The large sample distribution of the likelihood ratio for testing composite hypotheses. Annals of Mathematical Statistics, 9:60--62, 1938.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Experimentation

Keywords:
LRT spatial anomaly