Building a regression Tree with R FROM SCRATCH

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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];
      #Add to list new datasets
      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
  }
  tree<-list(HF,PosN,ValN) #Key information about tree
  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
g<-add.edges(g, edges) #add edges
#Create names
nV<-c()
for(i in 1:(gsize(g)+1))
{
if(sum(g[i])!=0) nV<-c(nV,paste0(paste0("x<",nn[i])))
  else nV<-c(nV,nn[i])
}
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"
plot(g, layout = layout.reingold.tilford(g, root = 1, flip.y = T, circular = F),
     vertex.size=32, vertex.shape="rectangle")