Assessing data mining results via swap randomization

ABSTRACT

The problem of assessing the significance of data mining results on high-dimensional 0-1 data sets has been studied extensively in the literature. For problems such as mining frequent sets and finding correlations, significance testing can be done by, e.g., chi-square tests, or many 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 more difficult to apply to sets of patterns or other complex results of data mining. In this paper, 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 with the given dataset, computing the results of interest on the randomized instances, and comparing them against 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 rankings. 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 a random artifact, while for other datasets the discovered structure conveys meaningful information.

REFERENCES

• 1: Bezáková, I., Bhatnagar, N., and Vigoda, E. Sampling binary contingency tables with a greedy start. In SODA (2006), SIAM.
• 2: 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]
• 3: 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
• 4: Chen, Y., Diaconis, P., Holmes, S. P., and Liu, J. S. Sequential Monte Carlo methods for statistical analysis of tables. Journal of the American Statistical Association 100, 469 (2005), 109--120.
• 5: Cobb, G. W., and Chen, Y.-P. An application of Markov chain Monte Carlo to community ecology. American Mathematical Monthly 110 (2003), 264--288.
• 6: Diaconis, P., and Gangolli, A. Rectangular arrays with fixed margins. In Discrete Probability and Algorithms (1995), pp. 15--41.
• 7: 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]
• 8: Good, P. Permutation Tests: A Practical Guide to Resampling Methods for Testing Hypotheses. Springer, 2000.
• 9: Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 (1970).
• 10: 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
• 11: 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]
• 12: 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]
• 13: Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. Equations of state calculations by fast computing machines. Journal of Chemical Physics 21 (1953).
• 14: Milo, R., Shen-Orr, S., Itzkovirz, S., Kashtan, N., Chklovskii, D., and Alon, U. Network motifs: Simple building blocks of complex networks. Science 298, (2002).
• 15: Newman, M. The structure and function of complex networks. SIAM Review 45, 2 (2003), 167--256.
• 16: Sanderson, J. Testing ecological patterns. American Scientist 88, 332--339 (2000).
• 17: Snijders, F. Enumeration and simulation methods for 0-1 matrices with given marginals. Psychometrika 56 (1991), 397--417.
• 18: 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]
• 19: 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]
• 20: 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, randomization tests, significance testing, swaps