A simple regression based heuristic for learning model trees

Article type: Research Article

Authors: Vens, Celine^{; *} | Blockeel, Hendrik

Affiliations: Department of Computer Science, K.U. Leuven, Belgium

Correspondence: [*] Corresponding author: Celine Vens, K.U. Leuven - Department of Computer Science, Celestijnenlaan 200A, B-3000 Leuven, Belgium. Tel.: +32 (0)16 32 75 67; Fax: +32 (0)16 32 79 96; E-mail: celine.vens@cs.kuleuven.be.

Abstract: The term “model trees” is commonly used for regression trees that contain some non-trivial model in their leaves. Popular implementations of model tree learners build trees with linear regression models in their leaves. They use reduction of variance as a heuristic for selecting tests during the tree construction process. In this article, we show that systems employing this heuristic may exhibit pathological behaviour in some quite simple cases. This is not visible in the predictive accuracy of the tree, but it reduces its explanatory power. We propose an alternative heuristic that yields equally accurate but simpler trees with better explanatory power, and this at little or no additional computational cost. The resulting model tree induction algorithm is experimentally evaluated and compared with simpler and more complex approaches on a variety of synthetic and real world data sets.

Keywords: Model trees, Regression, Heuristics, Machine learning

DOI: 10.3233/IDA-2006-10303

Journal: Intelligent Data Analysis, vol. 10, no. 3, pp. 215-236, 2006