A general framework for accurate and fast regression by data summarization in random decision trees

ABSTRACT

Predicting the values of continuous variable as a function of several independent variables is one of the most important problems for data mining. A very large number of regression methods, both parametric and nonparametric, have been proposed in the past. However, since the list is quite extensive and many of these models make rather explicit, strong yet different assumptions about the type of applicable problems and involve a lot of parameters and options, choosing the appropriate regression methodology and then specifying the parameter values is a none-trivial, sometimes frustrating, task for data mining practitioners. Choosing the inappropriate methodology can have rather disappointing results. This issue is against the general utility of data mining software. For example,linear regression methods are straightforward and well-understood. However, since the linear assumption is very strong, its performance is compromised for complicated non-linear problems. Kernel-based methods perform quite well if the kernel functions are selected correctly. In this paper, we propose a straightforward approach based on summarizing the training data using an ensemble of random decisions trees. It requires very little knowledge from the user, yet is applicable to every type of regression problem that we are currently aware of. We have experimented on a wide range of problems including those that parametric methods performwell, a large selection of benchmark datasets for nonparametric regression, as well as highly non-linear stochastic problems. Our results are either significantly better than or identical to many approaches that are known to perform well on these problems.

REFERENCES

• 1: Yali Amit , Donald Geman, Shape quantization and recognition with randomized trees, Neural Computation, v.9 n.7, p.1545-1588, Oct. 1, 1997 [doi>10.1162/neco.1997.9.7.1545]
• 2: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 3: Breiman, L., Friedman, J., Olshen, R., and Stone, C. (1984). Classification and Regression Trees. Wadsworth.
• 4: Fan, J. and Huang, L.-S. (2001). Goodness-of-fit tests for parametric regression models. Journal of the American Statistical Association, 96(454):640--664.
• 5: Wei Fan , Ed Greengrass , Joe McCloskey , Philip S. Yu , Kevin Drummey, Effective Estimation of Posterior Probabilities: Explaining the Accuracy of Randomized Decision Tree Approaches, Proceedings of the Fifth IEEE International Conference on Data Mining, p.154-161, November 27-30, 2005 [doi>10.1109/ICDM.2005.54]
• 6: Wei Fan , Haixun Wang , Philip S. Yu , Sheng Ma, Is random model better? On its accuracy and efficiency, Proceedings of the Third IEEE International Conference on Data Mining, p.51, November 19-22, 2003
• 7: Hardle, W. (1990). Applied Nonparametric Regression. Cambridge University Press.
• 8: Hastie, T. and Tibshirani, R. (1986). Generalized additive models. Statistical Science, 1:297--318.
• 9: Nitin Indurkhya , Sholom M. Weiss, Solving regression problems with rule-based ensemble classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.287-292, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502553]
• 10: Kedem, B. and Fokianos, K. (2002). Regression Models for Time Series Analysis.
• 11: Liu, T. F. (July 2005). The utility of randomness in decision tree ensemble. Master's thesis, Faculty of Information Technology, Monash University.
• 12: Loh, W.-Y. (2002). Regression trees with unbiased variable selection and interaction detection. Statistica Sinica, 12:361--386.
• 13: McCullagh, P. and Nelder, J. A. (1989). Generlized linear models, 2nd edition. Chapman and Hall, London.
• 14: Nelder, J. A. and Wedderburn, R. W. M. (1972). Generlized linear models. Journal of Royal Statistical Survey. Series A, 135:370--384.
• 15: Segal, M. R. (2004). Machine learning benchmarks and random forest regression. available from eScholarship repository, http://repositories.cdlib.org/cbmb/bench_rf_regn/.
• 16: Yan, J., Li, S., Zhu, S., and Zhang, H. (2001). Ensemble svm regression based multi-view face detection system. Technical Report MSR-TR-2001-09, Microsoft Research.
• 17: Kun Zhang , Zujia Xu , Jing Peng , Bill Buckles, Learning through Changes: An Empirical Study of Dynamic Behaviors of Probability Estimation Trees, Proceedings of the Fifth IEEE International Conference on Data Mining, p.817-820, November 27-30, 2005 [doi>10.1109/ICDM.2005.88]
• 18: Zhou, Z. H., Wu, J. X., Tang, W., and Chen., Z. Q. (2001). Combining regresson estimators: Ga-based selective neural network ensemble. International Journal of Computational Intelligence and Applications, 2001, 1(4):341-356, 1(4):341--356.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
decision trees, random, regression