# Building a regression Tree with R FROM SCRATCH

I am trying to build a basic regression Tree in R FROM SCRATCH (I know of rpart, tree, RandomForest,etc.). But it is just something that I would want to code myself for my culture.

In terms of pseudo-code it should look something like that:

while(!stopping_condition){
for (leaf in all_the_leaves_in_that_layer){
min_over_s_and_j=min_over_s_for_variable_j=criteria(first_s,first_v)
for (v in variables){
for (s in possible_split_values_for_variable_v){
if (criteria(s,v)<min_over_s_for_variable_j){
min_over_s_for_variable_j<-criteria(s,v)}}
if (min_over_s_for_variable_j<min_over_s_and_j){
min_over_s_and_j<-min_over_s_for_variable_j}}
tree=split_tree(tree,chosen_j,chosen_s)
}}


But I am at a loss regarding what structure to use for the tree and how to deal with all the leaves. My first thought was to have a tree as a list of list of list etc. but to access a specific layer of nodes I don't know what command to use ( I want to be able to prune it myself afterwards). Do you think it is worth implementing a new class in R ? Can I use something already created (for the class) ?

Also do you think the structure of my code is correct or could it be improved ?

I am also at a loss on how the splits should be for a continuous variables I know that you have to sort the values in the variable you want to split but afterwards do you create 2*(n-2)+2 splits by using each value as a threshold the two extremes giving birth to only two thresholds but each one in the middle creating two splits (the point corresponding to the value either left or right of the split). Or do you take the middle of each segment ? I dont know if I am being clear enough.

Do you know if R is a good choice of language to do it ?

Do you know some good step-by-step tutorials ?(I also accept them in C++,Java or Python)

• If you build fair documentation, I will tranfer it to LabVIEW which for applications has nice performance features. Let me know. Commented Aug 27, 2015 at 0:36
• Thanks for commenting but I am not sure to understand what you mean for I have never heard of LabVIEW do you mean that you wish that I send you my code once I finished to be able to test its performance ? Commented Aug 27, 2015 at 0:54
• LabVIEW (aka G) is a visual programming environment that is strongly typed and decently optimized, and compiled. There are solid arguments that while eventually "C runs fastest on the machine" that G is very fast to make, and it runs very fast out the box - so its the fastest to make very fast. I want to make a forest of oblique convolutional/boosted trees in that language, but the step-0 is RF. If you have a decent step-by-step for RF in pseudocode, I can start there. Commented Aug 27, 2015 at 2:08
• For the moment I want to implement regression Tree, random Forest (or step-0 as you call it) is one step further (by using bootstrapped regression trees and averaging them (more or less)). But I will post my pseudo code if it is of interest to you. Commented Aug 27, 2015 at 16:42
• I meant CART. Oblique is higher order than that. Commented Jul 11, 2016 at 23:03

The R package partykit provides infrastructure for creating trees from scratch. It contains class for nodes and splits and then has general methods for printing, plotting, and predicting. The package comes with various vignettes, specifically "partykit" and "constparty" would be interesting for you. The latter also contains an example for creating a decision tree learner from scratch.

As for splitting numeric variables: Usually, all possible binary splits of type <= threshold vs. > threshold are considered.

• Thank you very much for your answer I am diving into it right now ! Commented Aug 26, 2015 at 23:03
• I want to hear what the others have to say on this so I am not accepting your answer yet but it definitely is a great answer! Thanks a lot! Commented Aug 26, 2015 at 23:11

You can find complete Python code for a simple decision tree model in Programming Collective Intelligence by Segaran. Translating this to R would be a good start if you want to build decision trees from scratch.

• Thanks this is great ! The tutorial looks a lot more user friendly than the one for R provided by the constparty vignette. I think that will be a good start ! Commented Aug 27, 2015 at 1:08
• I think the purpose is different: Segaran's book is a first introduction to classification trees by exhaustive search (CART) and provides the complete Python code for a simple tree. It seems to do a good job for that. The purpose of partykit is different: It provides a unified framework for more general trees (classification, regression, survival) learned by different approaches (exhaustive search, inference-based, unbiased, etc.). Section 3 assumes that you already have an idea of the algorithm you want to implement and then tries to give you some ready-made building blocks for that. Commented Aug 27, 2015 at 8:11
• I agree with you completely, I think both of your answers complete each other in a sense that the tutorial is a first step to make sure I understood correctly the process and I cannot just copy and paste the code as it presents classification and not regression which is nice. And your answer provides a good framework to implement that on R once I am familiar with every step of the algorithm. Commented Aug 27, 2015 at 16:52

Here's my version of implementing decision tree classifier in R.

# library for plot of tree

library(igraph)


# Entropy function X - values data set, C - classes data set

get_entropy<-function(X,C)
{
n<-length(X)
nc1<-sum(C==1);nc2<-sum(C==2) #number of classes 1 and 2 in X
p1<-nc1/n;  p2<-nc2/n
ent<- -p1*ifelse(p1>0,log2(p1),0)-p2*ifelse(p2>0,log2(p2),0)
return(ent)
}


# Split entropy function

get_split_entropy<-function(X,C,node)
{
n<-length(X)
pos<-which(X<=X[node]) #Decision rule
X1<-X[pos];  X2<-X[-pos] #Split X by set node
C1<-C[pos];  C2<-C[-pos]; #Split C by set node
#Entropy X1
ent1<-0; n1<-length(X1)
if(n1!=0) ent1<-get_entropy(X1,C1)
#Entropy X2
ent2<-0;  n2<-length(X2)
if(n2!=0) ent2<-get_entropy(X2,C2)
#Split entropy
s_ent<- ent1*n1/n+ent2*n2/n
return (s_ent)
}


# Find a node with minimum entropy

fnd_node<-function(X,C)
{
node<-1
min_ent<-get_split_entropy(X,C,node)
for(i in 2:length(X))
{
ent<-get_split_entropy(X,C,i)
if(ent<min_ent) {min_ent<-ent;node<-i}
}
return(node)
}


# Creating decision tree

crt_dtree<-function(X,C)
{
lstX<-list(X) #List of splitted variables datasets
lstC<-list(C) #List of splitted classes datasets
PosN<-rbind("root") #Position of node in current data set
ValN<-rbind("-") #Value of node
HF<-rbind("r") #Hierarchical flag
i<-1
while(i<=length(lstX))
{
node<-fnd_node(lstX[[i]],lstC[[i]]) #find node for current dataset
ent<-get_entropy(lstX[[i]],lstC[[i]]) #calculate entropy
if(ent!=0)
{
#Split data set by node
pos<-which(lstX[[i]]<=lstX[[i]][node])
X1<-lstX[[i]][pos];X2<-lstX[[i]][-pos];
C1<-lstC[[i]][pos];C2<-lstC[[i]][-pos];
lstX[length(lstX)+1]<-list(X1)
lstX[length(lstX)+1]<-list(X2)
lstC[length(lstC)+1]<-list(C1)
lstC[length(lstC)+1]<-list(C2)
#Save information
HF<-rbind(HF,paste0(HF[i],"x"))
HF<-rbind(HF,paste0(HF[i],"y"))
PosN<-c(PosN,node)
ValN<-c(ValN,round(lstX[[i]][node],3))
}
else
ValN<-c(ValN,round(unique(lstC[[i]]),3))
i<-i+1
}
names(tree)<-c("HF","PosN","ValN")
return(tree)
}


# Main program

set.seed(6) #We set seed for freezing results
n1<-10;n2<-10

#Variables from Gaussian distribution with different parameters
X<-c(rnorm(n1,0),rnorm(n2,1))
#Classes
C<-c(rep(1,n1),rep(2,n2))
#Create a tree
tree<-crt_dtree(X,C)


# Create informations for plotting (edges)

hf<-as.character(unlist(tree$HF)) #nodes nn<-as.numeric(unlist(tree$ValN)[-1]) #values of nodes

edges<-c()
for(i in 1:(length(hf)-1))
{
bch<-hf[i]
for (j in (i+1):length(hf))
{
ch<-hf[j]
if ((substr(ch,1,nchar(bch))==bch)&&(nchar(ch)==(nchar(bch)+1)))
{edges<-c(edges,i,j)}
}
}


# Create a plot

g <- graph.empty (length(hf), directed = T) #creating empty plot
V(g)$name<-nV #Plotting #print(X);print(C) #For testing par(mar = c(0,0,0,0), ps=14,cex=1 ) V(g)$color="white"

• If you would couple your tree learning function with the creation of a constparty object instead of an igraph you would get various utility functions "for free", e.g., plotting with enhanced displays in the leafs (such as barplots etc.), printing (with leaf sizes and error proportions), predicting (in-sample and out-of-sample), subsetting the tree etc. See my reply for the exact reference. Commented Dec 9, 2017 at 21:10