Tell me something I don't know: randomization strategies for iterative data mining

ABSTRACT

There is a wide variety of data mining methods available, and it is generally useful in exploratory data analysis to use many different methods for the same dataset. This, however, leads to the problem of whether the results found by one method are a reflection of the phenomenon shown by the results of another method, or whether the results depict in some sense unrelated properties of the data. For example, using clustering can give indication of a clear cluster structure, and computing correlations between variables can show that there are many significant correlations in the data. However, it can be the case that the correlations are actually determined by the cluster structure.

In this paper, we consider the problem of randomizing data so that previously discovered patterns or models are taken into account. The randomization methods can be used in iterative data mining. At each step in the data mining process, the randomization produces random samples from the set of data matrices satisfying the already discovered patterns or models. That is, given a data set and some statistics (e.g., cluster centers or co-occurrence counts) of the data, the randomization methods sample data sets having similar values of the given statistics as the original data set. We use Metropolis sampling based on local swaps to achieve this. We describe experiments on real data that demonstrate the usefulness of our approach. Our results indicate that in many cases, the results of, e.g., clustering actually imply the results of, say, frequent pattern discovery.

REFERENCES

• 1: Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series B (Methodological), 57(1):289--300, 1995.
• 2: Julian Besag. Markov chain Monte Carlo methods for statistical inference. http://www.ims.nus.edu.sg/Programs/mcmc/files/besag\_tl.pdf, 2004.
• 3: Julian Besag and Peter Clifford. Generalized Monte Carlo significance tests. Biometrica, 76(4):633--642, 1989.
• 4: Toon Calders , Bart Goethals, Non-derivable itemset mining, Data Mining and Knowledge Discovery, v.14 n.1, p.171-206, February 2007 [doi>10.1007/s10618-006-0054-6]
• 5: G. W. Cobb and Y.-P. Chen. An application of markov chain monte carlo to community ecology. American Mathematical Monthly, (110):264--288, 2003.
• 6: Mikael Fortelius and Jussi Eronen. Now - neogene of the old world. http://www.helsinki.fi/science/now/, 2005. Database of fossil mammals.
• 7: Arianna Gallo , Tijl Bie , Nello Cristianini, MINI: Mining Informative Non-redundant Itemsets, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_44]
• 8: Charles J. Geyer. Markov chain monte carlo maximum likelihood. In Computing Science and Statistics: Proc. of 23rd Symposium on the Interface Foundation, 1991.
• 9: Aristides Gionis , Heikki Mannila , Taneli Mielikäinen , Panayiotis Tsaparas, Assessing data mining results via swap randomization, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.3, p.14-es, December 2007 [doi>10.1145/1297332.1297338]
• 10: Phillip Good. Permutation Tests: A Practical Guide to Resampling Methods for Testing Hypotheses. Springer-Verlag, 2000.
• 11: S. Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 1979.
• 12: Szymon Jaroszewicz. Interactive hmm construction based on interesting sequences. In Local Patterns to Global Models (LeGo'08) Workshop at the the European Conference on Principles and Practice of Knowledge Discovery in Databases, 2008.
• 13: David Jensen. Knowledge discovery through induction with randomization testing. In Proc. of the 1991 Knowledge Discovery in Databases Workshop, 1991.
• 14: N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculation by fast computing machines. Journal of Chemical Physics, 21(1):1087--91, 1953.
• 15: Taneli Mielikainen and Heikki Mannila. The pattern ordering problem. Lecture Notes in Computer Science, 2838:327--338, 2003.
• 16: Markus Ojala, Niko Vuokko, Aleksi Kallio, Niina Haiminen, and Heikki Mannila. Randomization of real-valued matrices for assessing the significance of data mining results. In Proc. of the 2008 SIAM International Conference on Data Mining, 2008.
• 17: Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 18: Geoffrey I. Webb, Discovering Significant Patterns, Machine Learning, v.68 n.1, p.1-33, July 2007 [doi>10.1007/s10994-007-5006-x]
• 19: Geoffrey I. Webb, Layered critical values: a powerful direct-adjustment approach to discovering significant patterns, Machine Learning, v.71 n.2-3, p.307-323, June 2008 [doi>10.1007/s10994-008-5046-x]
• 20: Peter H. Westfall and S. Stanley Young. Resampling-based multiple testing: examples and methods for p-value adjustment. Wiley, 1993.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Experimentation, Theory

Keywords:
inverse frequent set mining, matrix randomization, statistical significance