SECRET: a scalable linear regression tree algorithm

ABSTRACT

Developing regression models for large datasets that are both accurate and easy to interpret is a very important data mining problem. Regression trees with linear models in the leaves satisfy both these requirements, but thus far, no truly scalable regression tree algorithm is known. This paper proposes a novel regression tree construction algorithm (SECRET) that produces trees of high quality and scales to very large datasets. At every node, SECRET uses the EM algorithm for Gaussian mixtures to find two clusters in the data and to locally transform the regression problem into a classification problem based on closeness to these clusters. Goodness of split measures, like the gini gain, can then be used to determine the split variable and the split point much like in classification tree construction. Scalability of the algorithm can be achieved by employing scalable versions of the EM and classification tree construction algorithms. An experimental evaluation on real and artificial data shows that SECRET has accuracy comparable to other linear regression tree algorithms but takes orders of magnitude less computation time for large datasets.

REFERENCES

• 1: W. P. Alexander and S. D. Grimshaw. Treed regression. Journal of Computational and Graphical Statistics, (5):156--175, 1996.
• 2: P. S. Bradley, U. M. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In Knowledge Discovery and Data Mining, pages 9--15, 1998.
• 3: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, 1984.
• 4: P. Chaudhuri, M.-C. Huang, W.-Y. Loh, and R. Yao. Piecewise-polynomial regression trees. Statistica Sinica, 4:143--167, 1994.
• 5: J. H. Friedman. Multivariate adaptive regression splines. The Annals of Statistics, 19:1--141 (with discussion), 1991.
• 6: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 7: 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
• 8: G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins, 1996.
• 9: Aram Karalič, Employing linear regression in regression tree leaves, Proceedings of the 10th European conference on Artificial intelligence, p.440-441, August 1992, Vienna, Austria
• 10: K.-C. Li, H.-H. Lue, and C.-H. Chen. Interactive tree-structured regression via principal hessian directions. journal of the American Statistical Association, (95):547--560, 2000.
• 11: W.-Y. Loh. Regression trees with unbiased variable selection and interaction detection. Statistica Sinica, 2002. in press.
• 12: W.-Y. Loh and Y.-S. Shih. Split selection methods for classification trees. Statistica Sinica, 7(4), October 1997.
• 13: Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998 [doi>10.1023/A:1009744630224]
• 14: J. R. Quinlan. Learning with Continuous Classes. In 5th Australian Joint Conference on Artificial Intelligence, pages 343--348, 1992.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: Luís Torgo, Functional Models for Regression Tree Leaves, Proceedings of the Fourteenth International Conference on Machine Learning, p.385-393, July 08-12, 1997
• 17: L. Torgo. Kernel regression trees. In European Conference on Machine Learning, 1997. Poster paper.
• 18: Luís Torgo, Error Estimators for Pruning Regression Trees, Proceedings of the 10th European Conference on Machine Learning, p.125-130, April 21-23, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance