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:

    for (leaf in all_the_leaves_in_that_layer){
        for (v in variables){
            for (s in possible_split_values_for_variable_v){ 
                if (criteria(s,v)<min_over_s_for_variable_j){
             if (min_over_s_for_variable_j<min_over_s_and_j){ 

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)

  • $\begingroup$ If you build fair documentation, I will tranfer it to LabVIEW which for applications has nice performance features. Let me know. $\endgroup$ Aug 27, 2015 at 0:36
  • $\begingroup$ 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 ? $\endgroup$
    – jeandut
    Aug 27, 2015 at 0:54
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2015 at 2:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – jeandut
    Aug 27, 2015 at 16:42
  • $\begingroup$ I meant CART. Oblique is higher order than that. $\endgroup$ Jul 11, 2016 at 23:03

3 Answers 3


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.

  • $\begingroup$ Thank you very much for your answer I am diving into it right now ! $\endgroup$
    – jeandut
    Aug 26, 2015 at 23:03
  • $\begingroup$ 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! $\endgroup$
    – jeandut
    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.

  • $\begingroup$ 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 ! $\endgroup$
    – jeandut
    Aug 27, 2015 at 1:08
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2015 at 8:11
  • $\begingroup$ 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. $\endgroup$
    – jeandut
    Aug 27, 2015 at 16:52

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

library for plot of tree


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

  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)

Split entropy function

  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

  for(i in 2:length(X))
    if(ent<min_ent) {min_ent<-ent;node<-i}

Creating decision tree

  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
    node<-fnd_node(lstX[[i]],lstC[[i]]) #find node for current dataset
    ent<-get_entropy(lstX[[i]],lstC[[i]]) #calculate entropy
      #Split data set by node
      #Add to list new datasets
      #Save information
  tree<-list(HF,PosN,ValN) #Key information about tree

Main program

set.seed(6) #We set seed for freezing results

#Variables from Gaussian distribution with different parameters
#Create a tree

Create informations for plotting (edges)

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

for(i in 1:(length(hf)-1))
  for (j in (i+1):length(hf))
    if ((substr(ch,1,nchar(bch))==bch)&&(nchar(ch)==(nchar(bch)+1))) 

Create a plot

g <- graph.empty (length(hf), directed = T) #creating empty plot
g<-add.edges(g, edges) #add edges
#Create names
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])
#print(X);print(C) #For testing
par(mar = c(0,0,0,0), ps=14,cex=1 )
plot(g, layout = layout.reingold.tilford(g, root = 1, flip.y = T, circular = F),
     vertex.size=32, vertex.shape="rectangle")
  • $\begingroup$ 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. $\endgroup$ Dec 9, 2017 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.