Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The problem of assessing the significance of data mining results on high-dimensional 0--1 datasets has been studied extensively in the literature. For problems such as mining frequent sets and finding correlations, significance testing can be done by standard statistical tests such as chi-square, or other methods. However, the results of such tests depend only on the specific attributes and not on the dataset as a whole. Moreover, the tests are difficult to apply to sets of patterns or other complex results of data mining algorithms. In this article, we consider a simple randomization technique that deals with this shortcoming. The approach consists of producing random datasets that have the same row and column margins as the given dataset, computing the results of interest on the randomized instances and comparing them to the results on the actual data. This randomization technique can be used to assess the results of many different types of data mining algorithms, such as frequent sets, clustering, and spectral analysis. To generate random datasets with given margins, we use variations of a Markov chain approach which is based on a simple swap operation. We give theoretical results on the efficiency of different randomization methods, and apply the swap randomization method to several well-known datasets. Our results indicate that for some datasets the structure discovered by the data mining algorithms is expected, given the row and column margins of the datasets, while for other datasets the discovered structure conveys information that is not captured by the margin counts.

REFERENCES

• 1: Besag, J. 2004. Markov chain Monte Carlo methods for statistical inference. http://www.ims.nus.edu.sg/Programs/mcmc/files/besag_tl.pdf.
• 2: Besag, J. and Clifford, P. 1989. Generalized Monte Carlo significance tests. Biometrika 76, 4, 633--642.
• 3: Besag, J. and Clifford, P. 1991. Sequential Monte Carlo p-values. Biometrika 78, 2, 301--304.
• 4: Ivona Bezáková , Nayantara Bhatnagar , Eric Vigoda, Sampling binary contingency tables with a greedy start, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.414-423, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109604]
• 5: Bezáková, I., Sinclair, A., Stefankovic, D., and Vigoda, E. 2006. Negative examples for sequential importance sampling of binary contingency tables. http://arxiv.org/abs/math.ST/0606650.
• 6: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 7: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 8: Toon Calders, Computational complexity of itemset frequency satisfiability, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055580]
• 9: Chen, Y., Diaconis, P., Holmes, S. P., and Liu, J. S. 2005. Sequential Monte Carlo methods for statistical analysis of tables. J. Amer. Statis. Assoc. 100, 469, 109--120.
• 10: Cobb, G. W. and Chen, Y.-P. 2003. An application of Markov chain Monte Carlo to community ecology. Amer. Math. Month. 110, 264--288.
• 11: Diaconis, P. and Gangolli, A. 1995. Rectangular arrays with fixed margins. In Discrete Probability and Algorithms, 15--41.
• 12: Diaconis, P. and Saloff-Coste, L. 1995. Random walk on contingency tables with fixed row and column sums. Tech. Rep., Department of Mathematics, Harvard University.
• 13: 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]
• 14: Martin Dyer, Approximate counting by dynamic programming, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780643]
• 15: Fortelius, M. 2006. Neogene of the old world database of fossil mammals (NOW). http://www.helsinki.fi/science/now/.
• 16: Good, P. 2000. Permutation Tests: A Practical Guide to Resampling Methods for Testing Hypotheses. Springer.
• 17: Hastings, W. K. 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 1, 97--109.
• 18: Szymon Jaroszewicz , Dan A. Simovici, A General Measure of Rule Interestingness, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.253-265, September 03-05, 2001
• 19: N. Kashtan , S. Itzkovitz , R. Milo , U. Alon, Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs, Bioinformatics, v.20 n.11, p.1746-1758, July 2004 [doi>10.1093/bioinformatics/bth163]
• 20: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 21: Bing Liu , Wynne Hsu , Yiming Ma, Identifying non-actionable association rules, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.329-334, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502560]
• 22: Megiddo, N. and Srikant, R. 1998. Discovering predictive association rules. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining (KDD), New York, 274--278.
• 23: Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. 1953. Equations of state calculations by fast computing machines. J. Chem. Phys. 21, 1087--1092.
• 24: Mielikäinen, T. 2003. On inverse frequent set mining. In Proceedings of the 2nd Workshop on Privacy Preserving Data Mining (PPDM), IEEE Computer Society, 18--23.
• 25: Milo, R., Shen-Orr, S., Itzkovirz, S., Kashtan, N., Chklovskii, D., and Alon, U. 2002. Network motifs: Simple building blocks of complex networks. Sci. 298, 824--827.
• 26: Newman, M. 2003. The structure and function of complex networks. SIAM Rev. 45, 2, 167--256.
• 27: Ryser, H. J. 1957. Combinatorial properties of matrices of zeros and ones. Canadian J. Math. 9, 371--377.
• 28: Sanderson, J. 2000. Testing ecological patterns. Amer. Sci. 88, 332--339.
• 29: Snijders, F. 1991. Enumeration and simulation methods for 0--1 matrices with given marginals. Psychometrika 56, 397--417.
• 30: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, 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.775053]
• 31: Tomkins, A. 2006. Private communication.
• 32: Bo-Ying Wang , Fuzhen Zhang, On the precise number of (0,1)-matrices in U(R,S), Discrete Mathematics, v.187 n.1-3, p.211-220, June 6, 1998 [doi>10.1016/S0012-365X(97)00197-0]
• 33: Geoffrey I. Webb, Discovering significant rules, 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.1150451]
• 34: Geoffrey I. Webb, Discovering Significant Patterns, Machine Learning, v.68 n.1, p.1-33, July 2007 [doi>10.1007/s10994-007-5006-x]
• 35: Hui Xiong , Shashi Shekhar , Pang-Ning Tan , Vipin Kumar, Exploiting a support-based upper bound of Pearson's correlation coefficient for efficiently identifying strongly correlated pairs, 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.1014090]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Management

Keywords:
0--1 data, Significance testing, randomization tests, swaps