Finding low-entropy sets and trees from binary data

ABSTRACT

The discovery of subsets with special properties from binary data hasbeen one of the key themes in pattern discovery. Pattern classes suchas frequent itemsets stress the co-occurrence of the value 1 in the data. While this choice makes sense in the context of sparse binary data, it disregards potentially interesting subsets of attributes that have some other type of dependency structure.

We consider the problem of finding all subsets of attributes that have low complexity. The complexity is measured by either the entropy of the projection of the data on the subset, or the entropy of the data for the subset when modeled using a Bayesian tree, with downward or upward pointing edges. We show that the entropy measure on sets has a monotonicity property, and thus a levelwise approach can find all low-entropy itemsets. We also show that the tree-based measures are bounded above by the entropy of the corresponding itemset, allowing similar algorithms to be used for finding low-entropy trees. We describe algorithms for finding all subsets satisfying an entropy condition. We give an extensive empirical evaluation of the performance of the methods both on synthetic and on real data. We also discuss the search for high-entropy subsets and the computation of the Vapnik-Chervonenkis dimension of the data.

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: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 4: Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
• 5: Bringmann, B., Zimmermann, A., De Raedt, L., and Nijssen, S. Don't be afraid of simpler patterns. In PKDD (2006), pp. 55--66.
• 6: Chow, C. K., and Liu, C. N. Approximating discrete probability distributions with dependence trees. IEEE Trans. Info. Theory 14, 3 (1968), 462--467.
• 7: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: J. H. Friedman , J. W. Tukey, A Projection Pursuit Algorithm for Exploratory Data Analysis, IEEE Transactions on Computers, v.23 n.9, p.881-890, September 1974 [doi>10.1109/T-C.1974.224051]
• 10: Aristides Gionis , Teija Kujala , Heikki Mannila, Fragments of order, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956768]
• 11: Aristides Gionis , Heikki Mannila , Taneli Mielikäinen , Panayiotis Tsaparas, Assessing data mining results via swap randomization, 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.1150424]
• 12: Hastie, T., Tibshirani, R., and Friedman, J. The Elements of Statistical Learning. Springer, 2001.
• 13: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 14: Heikinheimo, H., Mannila, H., and Seppänen, J. K. Finding trees from unordered 0-1 data. In PKDD (2006), pp. 175--186.
• 15: Huber, P. J. Projection pursuit. The Annals of Statistics 13, 2 (June 1985), 435--475.
• 16: Arno J. Knobbe , Eric K. Y. Ho, Maximally informative k-itemsets and their efficient discovery, 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.1150431]
• 17: Koivisto, M. Advances in exact Bayesian structure discovery in Bayesian networks. In UAI (2006), pp. 241--248.
• 18: Marina Meila , Michael I. Jordan, Learning with mixtures of trees, The Journal of Machine Learning Research, 1, p.1-48, 9/1/2001
• 19: Shinichi Morishita , Jun Sese, Transversing itemset lattices with statistical metric pruning, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.226-236, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335226]
• 20: Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004 [doi>10.1145/1007730.1007731]
• 21: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: Siebes, A., Vreeken, J., and van Leeuwen, M. Item sets that compress. In SDM (2006), J. Ghosh, D. Lambert, D. B. Skillicorn, and J. Srivastava, Eds., SIAM.
• 23: van Leeuwen, M., Vreeken, J., and Siebes, A. Compression picks item sets that matter. In PKDD (2006), pp. 585--592.
• 24: Zimmermann, A., and De Raedt, L. CorClass: Correlated association rule mining for classification. In Discovery Science (2004), E. Suzuki and S. Arikawa, Eds., vol. 3245 of Lecture Notes in Computer Science, Springer, pp. 60--72.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
local models, pattern discovery