An iterative hypothesis-testing strategy for pattern discovery

ABSTRACT

Pattern discovery has emerged as a direct result of increased data storage and analytic capabilities available to the data analyst. Without a massive amount of data, we do not have the evidence to support the discovery of the local deterministic structures that we call patterns. As such, pattern discovery is one of the few areas of data mining that cannot be considered simply as a 'scaling-up' of current statistical methodology to analyze large data sets. However, the philosophies of hypothesis testing and modeling in traditional statistics do lend themselves to forming a framework for pattern discovery, and we can also draw from ideas relating to outlier discovery and residual analysis to discover patterns. We illustrate an iterative strategy in a statistical framework by way of its application to one simulated and two real data sets.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 2: Bellman, R. E. Adaptive control processes: a guided tour. Princeton, N.J.: Princeton University Press, 1961.
• 3: Bolton, R. J. and Krzanowski, W. J. (1999) A characterization of principal components for projection pursuit, American Statistician, 53:108--109.
• 4: Richard J. Bolton , David J. Hand, Significance Tests for Patterns in Continuous Data, Proceedings of the 2001 IEEE International Conference on Data Mining, p.67-74, November 29-December 02, 2001
• 5: Richard J. Bolton , David J. Hand , Niall M. Adams, Determining Hit Rate in Pattern Search, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.36-48, September 16-19, 2002
• 6: Breiman, L. (2001) Statistical modeling: The two cultures, Statistical Science, 16:199--215.
• 7: Darya Chudova , Padhraic Smyth, Pattern discovery in sequences under a Markov assumption, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775070]
• 8: Cook, R. D. and Weisberg, S. Residuals and Influence in Regression. New York: Chapman and Hall, 1982.
• 9: DuMouchel, W. (1999) Bayesian data mining in large frequency tables, with an application to the FDA spontaneous reporting system (with discussion), The American Statistician, 53: 177--202.
• 10: William DuMouchel , Daryl Pregibon, Empirical bayes screening for multi-item associations, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.67-76, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502526]
• 11: Hand, D. J. (1998) Data mining - reaching beyond statistics, Research in Official Statistics, 2.
• 12: Hand, D. J., Blunt, G., Kelly, M. G., and Adams, N. M. (2000) Data mining for fun and profit, Statistical Science, 15: 111--126.
• 13: Hand, D. J. and Blunt, G. (2001) Prospecting for gems in credit card data, IMA Journal of Management Mathematics, 12: 173--200.
• 14: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 15: Hand, D. J. and Bolton, R. J. (2002) Pattern Discovery, Imperial College Technical Report.
• 16: Ingrassia, S. (1992) A comparison between the simulated annealing and the EM algorithms in normal mixture decompositions, Statistics and Computing, 2: 203--211.
• 17: Bing Liu , Wynne Hsu , Lai-Fun Mun , Hing-Yan Lee, Finding Interesting Patterns Using User Expectations, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.817-832, November 1999 [doi>10.1109/69.824588]
• 18: Katharina Morik, Detecting Interesting Instances, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.13-23, September 16-19, 2002
• 19: Padmanabhan, B. and Tuzhilin, A. A belief-driven method for discovering unexpected patterns, in Proceedings of the Fourth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1998, pp. 94--110.
• 20: Balaji Padmanabhan , Alexander Tuzhilin, Knowledge refinement based on the discovery of unexpected patterns in data mining, Decision Support Systems, v.33 n.3, p.309-321, July 2002 [doi>10.1016/S0167-9236(02)00018-0]
• 21: Pigeot, I. (2000) Basic concepts of multiple tests - a survey, Statistical Papers, 41: 3--36.
• 22: Redner, R. A. and Walker, H. F. (1984) Mixture densities, maximum likelihood and the EM algorithm, SIAM Review, 26: 195--239.
• 23: Schonlau, M., DuMouchel, W., Ju, W.-H., Karr, A. F., Theus, M., and Vardi, Y. (2001) Computer intrusion: detecting masquerades, Statistical Science, 16: 1--17.
• 24: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 25: Venables, W. N. and Ripley, B. D. Modern applied statistics with S-PLUS. New York: Springer-Verlag, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Keywords:
data mining, outlier detection, residual analysis, statistical models, uncertainty