# Regression tree algorithm with linear regression models in each leaf

Short version: I'm looking for an R package that can build decision trees whereas each leaf in the decision tree is a full Linear Regression model. AFAIK, the library rpart creates decision trees where the dependent variable is constant in each leaf. Is there another library (or a rpart setting I'm not aware of) that can build such trees?

Long version: I'm looking for an algorithm that builds a decision tree based on a training data set. Each decision in the tree splits the training data set into two parts, according to a condition on one of the independent variables. The root of the tree contains the full data set, and each item in the data set is contained in exactly one leaf node.

The algorithm goes like this:

1. Begin with the full dataset, which is the root node of the tree. Pick this node and call it $N$.
2. Create a Linear Regression model on the data in $N$.
3. If $R^2$ of $N$'s linear model is higher than some threshold $\theta_{R^2}$, then we're done with $N$, so mark $N$ as a leaf and jump to step 5.
4. Try $n$ random decisions, and pick the one that yields the best $R^2$ in the subnodes:
• Pick a random independent variable $v_i$, as well as a random threshold $\theta_i$.
• The decision $v_i \leq \theta_i$ splits the data set of $N$ into two new nodes, $\hat{N}$ and $\tilde{N}$.
• Create Linear Regression models on both $\hat{N}$ and $\tilde{N}$, and calculate their $R^2$ (call them $\hat{r}$ and $\tilde{r}$).
• From all those $n$ tuples $(v_i, \theta_i, \hat{r}, \tilde{r})$, select the one with the maximal $min(\hat{r}, \tilde{r})$. This yields a new decision in the tree, and $N$ has two new subnodes $\hat{N}$ and $\tilde{N}$.
5. We have finished processing $N$. Pick a new node $N$ which has not yet been processed and go back to step 2. If all nodes have been processed, the algorithm ends.

This will recursively build a decision tree which splits the data into smaller parts, and calculates a Linear Model on each of those parts.

Step 3 is the exit condition, which prevents the algorithm from overfitting. Of course, there are other possible exit conditions:

• Exit if $N$'s depth in the tree is above $\theta_{depth}$
• Exit if the data set in $N$ is smaller than $\theta_{data set}$

Is there such an algorithm in an R package?

• Take a look at the party package and see if this suits your needs. It can handle a number of types of models in the nodes of trees IIRC. – Gavin Simpson Dec 4 '13 at 17:40

While they work differently than your algorithm, I believe you'll find mob() and FTtree interesting. For Zeileis' mob see http://cran.r-project.org/web/packages/party/vignettes/MOB.pdf For FTtree,Gama's functional trees an implementation is available in Weka and thus RWeka. See http://cran.r-project.org/web/packages/RWeka/index.html for details.

• +1 for mob, which allows plugging almost any model into the recursive partitioning framework – etov Sep 21 '14 at 9:05

The Cubist package fits rule-based models (similar to trees) with linear regression models in the terminal leaves, instance-based corrections and boosting.

RWeka package offers many regression methods. Among them, you can find M5P (M5 Prime), which is exactly tree based regression model with linear equations in leafs. For further details about M5 method, see publication.

An example code would be:

library(RWeka)
M5_model = M5P (Dep_var ~ ., data = train, control = Weka_control(N=F, M=10))
train_predicted = predict(M5_model, train)
test_predicted = predict(M5_model, test)


If you would like to use bagging ensemble with M5 method, try something like:

M5_bag = Bagging(Dep_var ~ ., data = train, control = Weka_control(P=100, I = 100, W = list("weka.classifiers.trees.M5P", M = 4)))


To see control options for M5P model, try:

WOW(M5P)


If you would like to optimize M5 method, there is a solution for that in caret package:

library(caret)
Optimization = train (Dep_var ~ .,data = train, method = 'M5')

• This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review – kjetil b halvorsen Sep 8 '16 at 11:31
• I am interested, why my suggestion is not an answer? Method M5 is well known tree-based method with linear equations in leaves. Previous answers suggested some packages, but package RWeka has not been suggested yet. I am using this package and method M5(P) for a long time and in my opinion is worth testing. However, there might be new users who will want to test RWeka package. – JerryTheForester Sep 8 '16 at 11:43
• It is very short for our standards, as such is a comment. You should provide more details, maybe an example, for it to be an answer. – kjetil b halvorsen Sep 8 '16 at 11:48
• Perhaps while you are expanding it you could compare it with the package suggested in the existing comment? – mdewey Sep 8 '16 at 12:59
• I agree, it is quite short. Give me a few hours to imrpove it and decorate it with an example. – JerryTheForester Sep 8 '16 at 13:22