Using python to build a CART algorithm
In this article, I described a method how we can code CART algorithm in python language. I think it is a good exercise to build your own algorithm to increase your coding skills and tree knowledge. It's not the fastest algorithm implementation but it's enough to understand CART and object oriented programming.
Cart algorithm
In 1983, Breiman et al first described CART algorithm like classified and Regression Tree. It could be used for regression and classification of binary target.
It's a recursive algorithm, at each iteration it finds the best splitting of data which could increase the probability of predicting the target values.
Tree definition
A tree is composed of nodes. Each node could have one, two children or could be a leaf node, a node with no children.
In a list, I stored each object Node.
Tree=[node1, node2, node3, node4….]
Tree structure
To store links and paths between Nodes, I am using Breadth first Search layout.
If the node(x) has a left child the index of the child node is : node(2*x + 1)
If the node(x) has a right child the index of the child node is : node(2*x + 2)
Each node is a python object :
class Node:
def init(self,t,L,R,D,S,V,M) :
self.t=t Index of Node
self.L=L Index of Left child
self.R=R Index of right child
self.D=D Depth of the Node
self.S=S Value of split
self.V=V Feature of split
self.M=M Subset array
self.X=X Execution Flag
Splitting criteria : Gini impurity gain
$$i (n) = 1 - \sum p^2_j $$ where
$$p_j ( t) = \frac{n_t ( t)}{n ( t)}$$
is the relative proportion of category j in Node(t)
For instance, if a data set has only one class target, its gini index is zero, is a purity data set.
We have two subsets : left and right induced by the value A and feature of the split.
$$ \Delta i ( n) = i ( n) - p_{left} i ( n_{left}) - p_{right} i ( n_{right}) $$
For each features, and for each split value A, we compute gini impurity gain and we choose the partition that maximize gini impurity gain.
Example of split calculus
In this example, we considered only one feature x which is continuous.
y
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
x
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
(0+1)/2=0.5 => 0.5 split
Feature x for 0.5 split value
|
|||
0
|
1
|
||
Target y class
|
0
|
10
|
0
|
1
|
3
|
7
|
|
$$i ( n) = 1 - \left( \frac{10}{20} \right)^2 - \left( \frac{10}{20} \right)^2 = 0.5$$
$$i ( left) = 1 - \left( \frac{10}{13} \right)^2 - \left( \frac{3}{13} \right)^2 = 0.3550295$$
$$i ( right) = 1 - \left( \frac{10}{20} \right)^2 = 0$$
$$\Delta i ( n) = 0.5 - \left( \frac{13}{20} \right)0.355 = 0.2692308$$
If we have had more than one feature, we compute for each feature all the splits, and we choose the best gini impurity gain.
Code of the Cart Algorithm
GitHub link : Tree_Cart_clean.py
Function Build(Tr):
Tr : node of the tree
Ex: T[0] : node one of the list T(list of the all nodes)
Using result of ginisplit function to define or not children Node
Function Split(v,a):
v: feature, a:array
Ex: Split(2,a) : feature 2, array a
Compute maximum gini gain for one feature, it computes all the split possibility
Function Giniplit(matrix):
Matrix: Array of features
Agregate all the best split, feature, and find the best partitionning.
Function TT(depth): Main program
depth : depth of the tree, if you want a max depth of 3 you must type 2.
It's the maximum depth of root node.
Build Tree list and define node
Comparison between my Cart algorithm and sklearn Cart : Same data, same depth, same criterion
import numpy as np
import random
np.random.seed(42)
X=np.random.randint(10, size=(100, 4))
Y=np.random.randint(2, size=100)
a=np.column_stack((Y,X))
Tree from Sklearn
from sklearn import tree
clf = tree.DecisionTreeClassifier(criterion='gini',max_depth=3)
clf = clf.fit(X, Y)
tree.export_graphviz(clf,out_file='tree.dot')
Tree from my Cart algorithm
#Initialisation ot the Tree list
Tree=[]
#Initialisation of Node[0]
Tree.append(Node(0,"L","R",0,"S","V",a,"X"))
#2 for 3 depth
TT(2)
#Print Tree
for index,node in enumerate(Tree):
print index,node.t,"*",node.L,node.R,"*","Depth:",node.D,node.S,len(node.M)
| Index | t | left | right | depth | split value | shape |
| 0 | 0 | 1 | 2 | 0 | 7,5 | 100 |
| 1 | 1 | 3 | 4 | 1 | 0,5 | 78 |
| 2 | 2 | 5 | 6 | 1 | 3,5 | 22 |
| 3 | 3 | * | * | 2 | * | 7 |
| 4 | 4 | 9 | 10 | 2 | 2,5 | 71 |
| 5 | 9 | * | * | 3 | * | 24 |
| 6 | 10 | * | * | 3 | * | 47 |
| 7 | 5 | 11 | 12 | 2 | 8,5 | 9 |
| 8 | 6 | 13 | 14 | 2 | 8,5 | 13 |
| 11 | 11 | * | * | 3 | * | 4 |
| 12 | 12 | * | * | 3 | * | 5 |
| 13 | 13 | * | * | 3 | * | 12 |
| 14 | 14 | * | * | 3 | * | 1 |
If we compare the tree generate by sklearn Cart and my tree generate by my Cart algorithm, they have the same results.
Usefull documents :
- Cart algorithm
- Gilles Louppe : Understanding Random Forests
To do :
- improve recursion loop in TT function to remove execution flag. This flag prevent algorithm to create children from a Node which has already been built.
- create predict function
- change the storage of array in object to rules to save memory