Capturing truthiness: mining truth tables in binary datasets

ABSTRACT

We introduce a new data mining problem: mining truth tables in binary datasets. Given a matrix of objects and the properties they satisfy, a truth table identifies a subset of properties that exhibit maximal variability (and hence, complete independence) in occurrence patterns over the underlying objects. This problem is relevant in many domains, e.g., in bioinformatics where we seek to identify and model independent components of combinatorial regulatory pathways, and in social/economic demographics where we desire to determine independent behavioral attributes of populations. We outline a family of levelwise approaches adapted to mining truth tables, algorithmic optimizations, and applications to bioinformatics and political datasets.

REFERENCES

• 1: Aristides Gionis , Heikki Mannila , Jouni K. Seppänen, Geometric and combinatorial tiles in 0-1 data, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.173-184, September 20-24, 2004, Pisa, Italy
• 2: C. Owens et al. Capturing truthiness: Mining truth tables in binary datasets. Technical report, Virginia Tech, March 2007. http://eprints.cs.vt.edu/archive/00000948/.
• 3: Craig Silverstein , Sergey Brin , Rajeev Motwani, Beyond Market Baskets: Generalizing Association Rules to Dependence Rules, Data Mining and Knowledge Discovery, v.2 n.1, p.39-68, January 1998 [doi>10.1023/A:1009713703947]
• 4: D. -I. Lin , Z. M. Kedem, Pincer-Search: An Efficient Algorithm for Discovering the Maximum Frequent Set, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.553-566, May 2002 [doi>10.1109/TKDE.2002.1000342]
• 5: Dmitry Pavlov , Heikki Mannila , Padhraic Smyth, Beyond Independence: Probabilistic Models for Query Approximation on Binary Transaction Data, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1409-1421, November 2003 [doi>10.1109/TKDE.2003.1245281]
• 6: Floris Geerts , Bart Goethals , Jan Van Den Bussche, Tight upper bounds on the number of candidate patterns, ACM Transactions on Database Systems (TODS), v.30 n.2, p.333-363, June 2005 [doi>10.1145/1071610.1071611]
• 7: Hui Xiong , Shashi Shekhar , Pang-Ning Tan , Vipin Kumar, TAPER: A Two-Step Approach for All-Strong-Pairs Correlation Query in Large Databases, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.493-508, April 2006 [doi>10.1109/TKDE.2006.68]
• 8: J. Fitzgerald et al. Systems Biology and Combination Therapy in the Quest for Clinical Efficacy. Nature Chemical Biology, Vol. 2(9): 458--466, Sep 2006.
• 9: Jouni K. Seppänen , Heikki Mannila, Dense itemsets, 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.1014140]
• 10: J. K. Seppanen et al. Using and Extending Itemsets in Data Mining. PhD thesis, Helsinki University of Technology, 2006.
• 11: J. L. Tuegels et al. Generalized Graphical Models for Discrete Data. Statistics and Probability Letters, Vol. 38: 41--47, May 1998.
• 12: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 13: L. O. Barrera et al. The transcriptional regulatory code of eukaryotic cells-insights from genome-wide analysis of chromatin organization and transcription factor binding. Curr Opin Cell Biol, 18(3): 291--8, 2006.
• 14: M. Natarajan et al. A Global Analysis of Cross-talk in a Mammalian Cellular Signaling Network. Nature Cell Biology, Vol. 8(6): 571--580, June 2006.
• 15: Mohammed J. Zaki , Naren Ramakrishnan, Reasoning about sets using redescription mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081912]
• 16: Naren Ramakrishnan , Deept Kumar , Bud Mishra , Malcolm Potts , Richard F. Helm, Turning CARTwheels: an alternating algorithm for mining redescriptions, 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.1014083]
• 17: Nikolaj Tatti , Taneli Mielikainen , Aristides Gionis , Heikki Mannila, What is the Dimension of Your Binary Data?, Proceedings of the Sixth International Conference on Data Mining, p.603-612, December 18-22, 2006 [doi>10.1109/ICDM.2006.167]
• 18: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 19: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 20: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 21: T. Lee et al. Transcriptional Regulatory Networks in Saccharomyces cerevisiae. Science, 298(5594): 799--804, 2002.
• 22: Truthiness. Wikipedia. http://en.wikipedia.org/wiki/Truthiness.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
independence models, levelwise algorithms, truth tables