SQL database primitives for decision tree classifiers

ABSTRACT

Scalable data mining in large databases is one of today's challenges to database technologies. Thus, substantial effort is dedicated to a tight coupling of database and data mining systems leading to database primitives supporting data mining tasks. In order to support a wide range of tasks and to be of general usage these primitives should be rather building blocks than implementations of specific algorithms. In this paper, we describe primitives for building and applying decision tree classifiers. Based on the analysis of available algorithms and previous work in this area we have identified operations which are useful for a number of classification algorithms. We discuss the implementation of these primitives on top of a commercial DBMS and present experimental results demonstrating the performance benefit.

REFERENCES

• 1: K. Alsabti, S. Ranka, and V. Singh. CLOUDS: A Decision Tree Classifier for Large Datasets. In R. Agrawal, P. Stolorz, and G. Piatetsky-Shapiro, editors, Proc. KDD-98, New York City, New York, 1998.
• 2: L. Breiman, J. Friedman, R. Olshen, and C. Stone. CIassiJication and Regression Trees. Chapman & Hall, 1984.
• 3: S. Chaudhuri. Data Mining and Database Systems: Where is the Intersection? Data Engineering Bulletin, 21( 1):48, 1998.
• 4: Scalable Classification over SQL Databases, Proceedings of the 15th International Conference on Data Engineering, p.470, March 23-26, 1999
• 5: Surajit Chaudhuri , Kyuseok Shim, Query Optimization in the Presence of Foreign Functions, Proceedings of the 19th International Conference on Very Large Data Bases, p.529-542, August 24-27, 1993
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Minos Garofalakis , Dongjoon Hyun , Rajeev Rastogi , Kyuseok Shim, Efficient algorithms for constructing decision trees with constraints, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.335-339, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347163]
• 8: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 10: D. M. Group. Predictive Model Markup Language (PMML) 1.1,2000. http://www.dmg.org/html/pmml-vl-l.html.
• 11: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 12: Joseph M. Hellerstein, Optimization techniques for queries with expensive methods, ACM Transactions on Database Systems (TODS), v.23 n.2, p.113-157, June 1998 [doi>10.1145/292481.277627]
• 13: Michael Jaedicke , Bernhard Mitschang, User-Defined Table Operators: Enhancing Extensibility for ORDBMS, Proceedings of the 25th International Conference on Very Large Data Bases, p.494-505, September 07-10, 1999
• 14: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• 15: M. Mehta, J. Rissanen, and R. Agrawal. MDL-based Decision Tree Pruning. In U. Fayyad and R. Uthurusamy, editors, Proc. KDD-95, Montreal, Canada, 1995.
• 16: 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
• 17: Amir Netz , Surajit Chaudhuri , Jeff Bernhardt , Usama M. Fayyad, Integration of Data Mining with Database Technology, Proceedings of the 26th International Conference on Very Large Data Bases, p.719-722, September 10-14, 2000
• 18: Carlos Ordonez , Paul Cereghini, SQLEM: fast clustering in SQL using the EM algorithm, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.559-570, May 15-18, 2000, Dallas, Texas, United States
• 19: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 20: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: 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
• 22: Kai-Uwe Sattler , Eike Schallehn, A Data Preparation Framework based on a Multidatabase Language, Proceedings of the International Database Engineering & Applications Symposium, p.219-228, July 16-18, 2001
• 23: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 24: Haixun Wang , Carlo Zaniolo, Using SQL to Build New Aggregates and Extenders for Object- Relational Systems, Proceedings of the 26th International Conference on Very Large Data Bases, p.166-175, September 10-14, 2000

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Performance

Keywords:
SQL-aware data mining, data mining primitives, query operators