Extracting semantics from data cubes using cube transversals and closures

ABSTRACT

In this paper we propose a lattice-based approach intended for extracting semantics from datacubes: borders of version spaces for supervised classification, closed cube lattice to summarize the semantics of datacubes w.r.t. COUNT, SUM, and covering graph of the quotient cube as a visualization tool of minimal multidimensional associations. With this intention, we introduce two novel concepts: the cube transversals and the cube closures over the cube lattice of a categorical database relation. We propose a levelwise merging algorithm for mining minimal cube transversals with a single database scan. We introduce the cube connection, show that it is a Galois connection and derive a closure operator over the cube lattice. Using cube transversals and closures, we define a new characterization of boundary sets which provide a condensed representation of version spaces used to enhance supervised classification. The algorithm designed for computing such borders improves the complexity of previous proposals. We also introduce the concept of closed cube lattice and show that it is isomorph to on one hand the Galois lattice and on the other hand the quotient cube w.r.t. COUNT, SUM. Proposed in [16], the quotient cube is a succinct summary of a datacube preserving the Rollup/Drilldown semantics. We show that the quotient cube w.r.t. COUNT, SUM and the closed cube lattice have a similar expression power but the latter has the smallest possible size. Finally we focus on the multidimensional association issue and introduce the covering graph of the quotient cube which provides the user with a visualization tool of minimal multidimensional associations.

REFERENCES

• 1: Yves Bastide , Nicolas Pasquier , Rafik Taouil , Gerd Stumme , Lotfi Lakhal, Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of the First International Conference on Computational Logic, p.972-986, July 01, 2000
• 2: C. Berge. Hypergraphs: combinatorics of finite sets. North-Holland, Amsterdam, 1989.
• 3: Claudio Carpineto , Giovanni Romano, A lattice conceptual clustering system and its application to browsing retrieval, Machine Learning, v.24 n.2, p.95-122, Aug. 1996 [doi>10.1023/A:1018050230279]
• 4: A. Casali, R. Cicchetti, and L. Lakhal. Cube Lattices: a Framework for Multidimensional Data Mining. In Proceedings of the 3rd SIAM International Conference on Data Mining, SDM, pages 304--308, 2003.
• 5: A. Casali, R. Cicchetti, and L. Lakhal. Lattice-Based Discovery of Semantics from Datacubes. Technical report, Université de la Méditerranée, 2003.
• 6: A. Casali, R. Cicchetti, and L. Lakhal. Mining Concise Représentations of Frequent Multidimensional Patterns. In Proceedings of the 11th International Conference on Conceptual Structures, ICCS, 2003.
• 7: Guozhu Dong , Jiawei Han , Joyce M. W. Lam , Jian Pei , Ke Wang, Mining Multi-Dimensional Constrained Gradients in Data Cubes, Proceedings of the 27th International Conference on Very Large Data Bases, p.321-330, September 11-14, 2001
• 8: Thomas Eiter , Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, v.24 n.6, p.1278-1304, Dec. 1995 [doi>10.1137/S0097539793250299]
• 9: Bernhard Ganter , C. Franzke , Rudolf Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 11: Dimitrios Gunopulos , Heikki Mannila , Roni Khardon , Hannu Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.209-216, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263684]
• 12: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 13: Jiawei Han , Jian Pei , Guozhu Dong , Ke Wang, Efficient computation of Iceberg cubes with complex measures, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.1-12, May 21-24, 2001, Santa Barbara, California, United States
• 14: H. Hirsh. Theoretical Underpinnings of Version Spaces. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, IJCAI, pages 665--670, 1991.
• 15: H. Hirsh. The Computational Compexity of the Candidate-Elimination Algorithm. Technical report, Rutgers Univeristy, 1992.
• 16: L. Lakshmanan, J. Pei, and J. Han. Quotient Cube: How to Summarize the Semantics of a Data Cube. In Proceedings of the 28th International Conference on Very Large Databases, VLDB, pages 778--789, 2002.
• 17: Stéphane Lopes , Jean-Marc Petit , Lotfi Lakhal, Efficient Discovery of Functional Dependencies and Armstrong Relations, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.350-364, March 27-31, 2000
• 18: Hongjun Lu , Hongyan Liu, Decision Tables: Scalable Classification Exploring RDBMS Capabilities, Proceedings of the 26th International Conference on Very Large Data Bases, p.373-384, September 10-14, 2000
• 19: Heikki Mannila , Kari-Jouko Räihä, The design of relational databases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 20: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 21: Engelbert Mephu Nguifo , Patrick Njiwoua, Using Lattice-Based Framework as a Tool for Feature Extraction, Proceedings of the 10th European Conference on Machine Learning, p.304-309, April 21-23, 1998
• 22: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 23: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 24: Jian Pei , Jiawei Han, Constrained frequent pattern mining: a pattern-growth view, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002 [doi>10.1145/568574.568580]
• 25: J. Pei, J. Han, and R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets. In Workshop on Research Issues in Data Mining and Knowledge Discovery, DMKD, pages 21--30, 2000.
• 26: J. Pfaltz and R. Jamison. Closure systems and their structure. In Information Sciences, volume 139(3--4), pages 275--286, 2001.
• 27: Gerd Stumme , Rafik Taouil , Yves Bastide , Nicolas Pasquier , Lotfi Lakhal, Computing iceberg concept lattices with TITANIC, Data & Knowledge Engineering, v.42 n.2, p.189-222, August 2002 [doi>10.1016/S0169-023X(02)00057-5]
• 28: Toon Calders , Raymond T. Ng , Jef Wijsen, Searching for dependencies at multiple abstraction levels, ACM Transactions on Database Systems (TODS), v.27 n.3, p.229-260, September 2002 [doi>10.1145/581751.581752]
• 29: Anthony K. H. Tung , Hongjun Lu , Jiawei Han , Ling Feng, Efficient Mining of Intertransaction Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.43-56, January 2003 [doi>10.1109/TKDE.2003.1161581]
• 30: Condensed Cube: An Efficient Approach to Reducing Data Cube Size, Proceedings of the 18th International Conference on Data Engineering, p.155, February 26-March 01, 2002
• 31: M. Zaki and C. Hsio. CHARM: An Efficient Algorithm for Closed Itemset Mining. In Proceedings of the 2nd SIAM International Conference on Data mining, 2002.
• 32: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]

INDEX TERMS

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

Keywords:
algorithm, closures, datacubes, hypergraph transversals, lattices, version spaces