On detecting space-time clusters

ABSTRACT

Detection of space-time clusters is an important function in various domains (e.g., epidemiology and public health). The pioneering work on the spatial scan statistic is often used as the basis to detect and evaluate such clusters. State-of-the-art systems based on this approach detect clusters with restrictive shapes that cannot model growth and shifts in location over time. We extend these methods significantly by using the flexible square pyramid shape to model such effects. A heuristic search method is developed to detect the most likely clusters using a randomized algorithm in combination with geometric shapes processing. The use of Monte Carlo methods in the original scan statistic formulation is continued in our work to address the multiple hypothesis testing issues. Our method is applied to a real data set on brain cancer occurrences over a 19 year period. The cluster detected by our method shows both growth and movement which could not have been modeled with the simpler cylindrical shapes used earlier. Our general framework can be extended quite easily to handle other flexible shapes for the space-time clusters.

REFERENCES

• 1: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 2: L. Duczmal and R. Assuncao. A simulated annealing strategy for the detection of arbitrary shaped spatial clusters. Computational Statistics and Data Analysis, March 2003.
• 3: J. Fleiss. Statistical methods for Rates and Proportions. John Wiley & Sons, 1981.
• 4: J. Glaz and N. Balakrishnan. Scan Statistics and Applications. Birkhauser, 1999.
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: M. Kulldorff. A spatial scan statistic. Communications in Statistics: Theory and Methods, 26(6):1481--1496, 1997.
• 7: M. Kulldorff. Spatial scan statistics: models, calculations, and applications. In Scan Statistics and Applications, edited by Glaz and Balakrishnan, 1999.
• 8: M. Kulldorff, W. Athas, E. Feuer, B. Miller, and C. Key. Evaluating cluster alarms: A space-time scan statistic and brain cancer in Los Alamos. American Journal of Public Health, 88:1377--1380, 1998.
• 9: M. Kulldorff and Information Management Services Inc. Satscan v. 3.1: Software for the spatial and space-time scan statistics. Technical report, 2002. http://www.satscan.org/.
• 10: National Cancer Institute. Brain cancer in New Mexico. Technical Report Data set (1973-1991), Division of Cancer Prevention, Biometry Research Group.
• 11: D. Neill and A. Moore. A fast multi-resolution method for detection of significant spatial overdensities. Technical Report Carnegie Mellon CSD Technical Report CMU-CS-03-154 (Abbreviated version to appear in NIPS 2003), Carnegie Mellon University, June 2003.
• 12: P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
• 13: D. G. Wilson , B. D. Rudin, Introduction to the IBM optimization subroutine library, IBM Systems Journal, v.31 n.1, p.4-10, Jan. 1992

INDEX TERMS

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

Keywords:
Monte Carlo, clusters, search, space-time region, spatial scan statistic