Maximally informative k-itemsets and their efficient discovery

ABSTRACT

In this paper we present a new approach to mining binary data. We treat each binary feature (item) as a means of distinguishing two sets of examples. Our interest is in selecting from the total set of items an itemset of specified size, such that the database is partitioned with as uniform a distribution over the parts as possible. To achieve this goal, we propose the use of joint entropy as a quality measure for itemsets, and refer to optimal itemsets of cardinality k as maximally informative k-itemsets. We claim that this approach maximises distinctive power, as well as minimises redundancy within the feature set. A number of algorithms is presented for computing optimal itemsets efficiently.

REFERENCES

• 1: 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
• 2: Almuallim, H., Dietterich, T. G., Learning with Many Irrelevant Features, In Proceedings of AAAI '91, 1991
• 3: Ella Bingham , Heikki Mannila , Jouni K. Seppänen, Topics in 0--1 data, 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.775112]
• 4: Pierre Comon, Independent component analysis, a new concept?, Signal Processing, v.36 n.3, p.287-314, April 1994 [doi>10.1016/0165-1684(94)90029-9]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 8: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 9: Hyvärinen, A., Karhunen, J., Oja, E., Independent Component Analysis, John Wiley & Sons, 2001
• 10: Kenji Kira , Larry A. Rendell, A Practical Approach to Feature Selection, Proceedings of the Ninth International Workshop on Machine Learning, p.249-256, July 01-03, 1992
• 11: Willi Klösgen, Explora: a multipattern and multistrategy discovery assistant, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 12: Knobbe, A. J., Adriaans, P. W., Discovering Foreign Key Relations in Relational Databases, In Proceedings of EMCSR '96, 1996
• 13: Knobbe, A. J., Multi-Relational Data Mining, Ph.D. dissertation, 2004, http://www.kiminkii.com/thesis.pdf
• 14: Ron Kohavi, The Power of Decision Tables, Proceedings of the 8th European Conference on Machine Learning, p.174-189, April 25-27, 1995
• 15: Koller, D., Sahami, M., Toward Optimal Feature Selection, In Proceedings of ICML '96, 1996
• 16: Stefan Kramer , Nada Lavrač , Peter Flach, Propositionalization approaches to relational data mining, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
• 17: Kreher, D. L., Stinson, D. R., Combinatorial Algorithms, CRC Press, 1999
• 18: Nada Lavrač , Peter A. Flach, An extended transformation approach to inductive logic programming, ACM Transactions on Computational Logic (TOCL), v.2 n.4, p.458-494, Oct. 2001 [doi>10.1145/383779.383781]
• 19: Pfahringer, B., Compression-Based Feature Subset Selection, In Proceedings of IJCAI '95, 1995
• 20: Safarii Multi-Relational Data Mining environment, http://www.kiminkii.com/safarii.html, 2006
• 21: Ashwin Srinivasan , S. H. Muggleton , M. J. E. Sternberg , R. D. King, Theories for mutagenicity: a study in first-order and feature-based induction, Artificial Intelligence, v.85 n.1-2, p.277-299, Aug. 1996 [doi>10.1016/0004-3702(95)00122-0]
• 22: Hui Wang , David Bell , Fionn Murtagh, Axiomatic Approach to Feature Subset Selection Based on Relevance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.3, p.271-277, March 1999 [doi>10.1109/34.754624]
• 23: Stefan Wrobel, An Algorithm for Multi-relational Discovery of Subgroups, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.78-87, June 24-27, 1997
• 24: Zaki, M. J., Orihara, M., Theoretical Foundations of Association Rules, In Proceedings ACM SIGMED workshop on research issues in KDD, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Theory

Keywords:
binary data, feature selection, information theory, joint entropy, maximally informative k-itemsets, subgroup discovery