Expressive power of an algebra for data mining

ABSTRACT

The relational data model has simple and clear foundations on which significant theoretical and systems research has flourished. By contrast, most research on data mining has focused on algorithmic issues. A major open question is: what's an appropriate foundation for data mining, which can accommodate disparate mining tasks? We address this problem by presenting a database model and an algebra for data mining. The database model is based on the 3W-model introduced by Johnson et al. [2000]. This model relied on black box mining operators. A main contribution of this article is to open up these black boxes, by using generic operators in a data mining algebra. Two key operators in this algebra are regionize, which creates regions (or models) from data tuples, and a restricted form of looping called mining loop. Then the resulting data mining algebra MA is studied and properties concerning expressive power and complexity are established. We present results in three directions: (1) expressiveness of the mining algebra; (2) relations with alternative frameworks, and (3) interactions between regionize and mining loop.

REFERENCES

• 1: Serge Abiteboul , Gerd G. Hillebrand, Space Usage in Functional Query Languages, Proceedings of the 5th International Conference on Database Theory, p.439-454, January 11-13, 1995
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: 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
• 4: 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
• 5: Jean-Francois Boulicaut , Mika Klemettinen , Heikki Mannila, Modeling KDD Processes within the Inductive Database Framework, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.293-302, September 01, 1999
• 6: Breiman, L., Friedman, J., Olshen, R., and Stone, C. 1984. Classification and Regression Trees. Wadsworth, Belmont, CA.
• 7: Calders, T., Rigotti, C., and Boulicaut, J.-F. 2006. A survey on condensed representations for frequent sets. In Constraint-Based Mining and Inductive Databases, J.-F. Boulicaut, L. de Raedt, and H. Mannila, Eds. Lecture Notes in Computer Science, vol. 3848. Springer-Verlag, London, U.K.
• 8: Efficient Evaluation of Queries with Mining Predicates, Proceedings of the 18th International Conference on Data Engineering, p.529, February 26-March 01, 2002
• 9: Mariano P. Consens , Alberto O. Mendelzon, Low-complexity aggregation in GraphLog and Datalog, Theoretical Computer Science, v.116 n.1, p.95-116, Aug. 2, 1993
• 10: Dantzig, G. 1963. Linear Programming and Extensions. Princeton University Press, Princeton, NJ.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Geist, I. and Sattler, K. 2002. Towards data mining operators in database systems: Algebra and implementation. In Proceedings of the DBFusion International Workshop on Databases, Documents, and Information Fusion. Vol. 124. CEUR-WS, Karlsruhe, Germany.
• 13: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 14: Jaiwei Han , Youngjian Fu , Wei Wang , Jenny Chiang , Osmar R. Zaïane , Krzysztof Koperski, DBMiner: interactive mining of multiple-level knowledge in relational databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.550, June 04-06, 1996, Montreal, Quebec, Canada
• 15: 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
• 16: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 17: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 18: Tomasz Imieliński , Aashu Virmani, MSQL: A Query Language for Database Mining, Data Mining and Knowledge Discovery, v.3 n.4, p.373-408, December 1999 [doi>10.1023/A:1009816913055]
• 19: Theodore Johnson , Laks V. S. Lakshmanan , Raymond T. Ng, The 3W Model and Algebra for Unified Data Mining, Proceedings of the 26th International Conference on Very Large Data Bases, p.21-32, September 10-14, 2000
• 20: Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
• 21: Law, Y.-N., Wang, H., and Zaniolo, C. 2004. Query languages and data models for database sequences and data streams. In Proceedings of the VLDB International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, 492--503.
• 22: Leonid Libkin , Limsoon Wong, On the Power of Aggregation in Relational Query Languages, Proceedings of the 6th International Workshop on Database Programming Languages, p.260-280, August 18-20, 1997
• 23: Mannila, H. and Toivonen, H. 1996. Multiple uses of frequent sets and condensed representations. In Proceedings of the KDD International Conference on Knowledge Discovery in Databases. ACM Press, New York, NY.
• 24: Rosa Meo , Giuseppe Psaila , Stefano Ceri, A New SQL-like Operator for Mining Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.122-133, September 03-06, 1996
• 25: Murty, K. G. 1983. Linear Programming. John Wiley & Sons, New York, NY.
• 26: Amir Netz , Surajit Chaudhuri , Usama M. Fayyad , Jeff Bernhardt, Integrating Data Mining with SQL Databases: OLE DB for Data Mining, Proceedings of the 17th International Conference on Data Engineering, p.379-387, April 02-06, 2001
• 27: Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, Towards a theory of spatial database queries (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.279-288, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182640]
• 28: Jan Paredaens , Dirk Van Gucht, Possibilities and limitations of using flat operators in nested algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.29-38, March 1988, Austin, Texas, United States [doi>10.1145/308386.308402]
• 29: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 30: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States
• 31: Jan Van den Bussche, Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions, Theoretical Computer Science, v.254 n.1-2, p.363-377, March 6, 2001 [doi>10.1016/S0304-3975(99)00301-1]
• 32: Haixun Wang , Carlo Zaniolo, Nonmonotonic reasoning in LDL++, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2001
• 33: Wang, H. and Zaniolo, C. 2003. ATLaS: A native extension of sql for data mining. In Proceedings of the Third SIAM International Conference on Data Mining. SIAM Press, Philadelphia, PA.
• 34: Zaniolo, C. 2005. Mining databases and data streams with query languages and rules. In Proceedings of the ECML-PKDD 2005 Workshop on Knowledge Discovery in Inductive Databases. Lecture Notes in Computer Science, vol. 3933. Springer-Verlag, London, U.K.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Languages, Theory

Keywords:
Algebra, data mining, expressive power