The Algorithms logo
The Algorithms
AboutDonate

Decision Tree

H
W
c
9
A
E
N
and 2 more contributors
"""
Implementation of a basic regression decision tree.
Input data set: The input data set must be 1-dimensional with continuous labels.
Output: The decision tree maps a real number input to a real number output.
"""
import numpy as np


class Decision_Tree:
    def __init__(self, depth=5, min_leaf_size=5):
        self.depth = depth
        self.decision_boundary = 0
        self.left = None
        self.right = None
        self.min_leaf_size = min_leaf_size
        self.prediction = None

    def mean_squared_error(self, labels, prediction):
        """
        mean_squared_error:
        @param labels: a one dimensional numpy array
        @param prediction: a floating point value
        return value: mean_squared_error calculates the error if prediction is used to
            estimate the labels
        >>> tester = Decision_Tree()
        >>> test_labels = np.array([1,2,3,4,5,6,7,8,9,10])
        >>> test_prediction = np.float(6)
        >>> tester.mean_squared_error(test_labels, test_prediction) == (
        ...     Test_Decision_Tree.helper_mean_squared_error_test(test_labels,
        ...         test_prediction))
        True
        >>> test_labels = np.array([1,2,3])
        >>> test_prediction = np.float(2)
        >>> tester.mean_squared_error(test_labels, test_prediction) == (
        ...     Test_Decision_Tree.helper_mean_squared_error_test(test_labels,
        ...         test_prediction))
        True
        """
        if labels.ndim != 1:
            print("Error: Input labels must be one dimensional")

        return np.mean((labels - prediction) ** 2)

    def train(self, X, y):
        """
        train:
        @param X: a one dimensional numpy array
        @param y: a one dimensional numpy array.
        The contents of y are the labels for the corresponding X values

        train does not have a return value
        """

        """
        this section is to check that the inputs conform to our dimensionality
        constraints
        """
        if X.ndim != 1:
            print("Error: Input data set must be one dimensional")
            return
        if len(X) != len(y):
            print("Error: X and y have different lengths")
            return
        if y.ndim != 1:
            print("Error: Data set labels must be one dimensional")
            return

        if len(X) < 2 * self.min_leaf_size:
            self.prediction = np.mean(y)
            return

        if self.depth == 1:
            self.prediction = np.mean(y)
            return

        best_split = 0
        min_error = self.mean_squared_error(X, np.mean(y)) * 2

        """
        loop over all possible splits for the decision tree. find the best split.
        if no split exists that is less than 2 * error for the entire array
        then the data set is not split and the average for the entire array is used as
        the predictor
        """
        for i in range(len(X)):
            if len(X[:i]) < self.min_leaf_size:
                continue
            elif len(X[i:]) < self.min_leaf_size:
                continue
            else:
                error_left = self.mean_squared_error(X[:i], np.mean(y[:i]))
                error_right = self.mean_squared_error(X[i:], np.mean(y[i:]))
                error = error_left + error_right
                if error < min_error:
                    best_split = i
                    min_error = error

        if best_split != 0:
            left_X = X[:best_split]
            left_y = y[:best_split]
            right_X = X[best_split:]
            right_y = y[best_split:]

            self.decision_boundary = X[best_split]
            self.left = Decision_Tree(
                depth=self.depth - 1, min_leaf_size=self.min_leaf_size
            )
            self.right = Decision_Tree(
                depth=self.depth - 1, min_leaf_size=self.min_leaf_size
            )
            self.left.train(left_X, left_y)
            self.right.train(right_X, right_y)
        else:
            self.prediction = np.mean(y)

        return

    def predict(self, x):
        """
        predict:
        @param x: a floating point value to predict the label of
        the prediction function works by recursively calling the predict function
        of the appropriate subtrees based on the tree's decision boundary
        """
        if self.prediction is not None:
            return self.prediction
        elif self.left or self.right is not None:
            if x >= self.decision_boundary:
                return self.right.predict(x)
            else:
                return self.left.predict(x)
        else:
            print("Error: Decision tree not yet trained")
            return None


class Test_Decision_Tree:
    """Decision Tres test class"""

    @staticmethod
    def helper_mean_squared_error_test(labels, prediction):
        """
        helper_mean_squared_error_test:
        @param labels: a one dimensional numpy array
        @param prediction: a floating point value
        return value: helper_mean_squared_error_test calculates the mean squared error
        """
        squared_error_sum = np.float(0)
        for label in labels:
            squared_error_sum += (label - prediction) ** 2

        return np.float(squared_error_sum / labels.size)


def main():
    """
    In this demonstration we're generating a sample data set from the sin function in
    numpy.  We then train a decision tree on the data set and use the decision tree to
    predict the label of 10 different test values. Then the mean squared error over
    this test is displayed.
    """
    X = np.arange(-1.0, 1.0, 0.005)
    y = np.sin(X)

    tree = Decision_Tree(depth=10, min_leaf_size=10)
    tree.train(X, y)

    test_cases = (np.random.rand(10) * 2) - 1
    predictions = np.array([tree.predict(x) for x in test_cases])
    avg_error = np.mean((predictions - test_cases) ** 2)

    print("Test values: " + str(test_cases))
    print("Predictions: " + str(predictions))
    print("Average error: " + str(avg_error))


if __name__ == "__main__":
    main()
    import doctest

    doctest.testmod(name="mean_squarred_error", verbose=True)
About this Algorithm
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import numpy as np


# In[ ]:


class D_TREE :
    
    def fit(self,Xin):
        #fitting the values
        self.X=Xin                            #training_dataset_
        self.my_tree=self.tree(Xin)           #calls tree() function to create a tree based on the dataset provided
    
    
    
    def label_count(self,t):
        #count the unique labels
        count = {}                           #a dictionary that will store the no of times every label has occurred
        for i in range(len(t)):
            lbl = t[i][-1]                   #The last field or column in t actually contains the labels 
            if lbl not in count:
                count[lbl] = 0               #If the label is not present previously,initialize it with zero
            count[lbl]+=1                    #Everytime a particular label is encountered its count is increased by 1           
        return count

    
    
    
    class Question :
        #stores the question and matches the question 
        def __init__(self,col,value):
            self.col = col                  #The column to which the question belongs to
            self.question = value           #the particualr cell in the column which is treated as question
        
        
        def is_digit_or_char(self,n):
            #checks whether a particular value is a number or not
            return isinstance(n,int) or isinstance(n,float)
    
        def check(self,row):
            value=row[self.col]              #the value to be tested with the question
            if(self.is_digit_or_char(self.question)):
                return value&gt;=self.question  #if the value is numeric in nature check whether it is greater or equal to question
            else :
                return value==self.question  #if the value is a character or string check whether it is equal to the question or not
         
        
   

    def gini(self,t):
        #Calculates the gini score
        label = np.unique(t)                #No of unique labels
        impurity = 1
    
        for i in range(len(label)):
            impurity -= (np.sum(t[:,-1]==label[i])/t.shape[0])**2    #formula for calculating impurity based on probability
    
        return impurity

    
    

    def information_gain(self,l,r,current_uncertainity):
        #Information gain is calculated
        p = len (l) / float ( len(l) + len(r) )             
        return current_uncertainity - p*self.gini(l) - (1-p)*self.gini(r)
    
    
    
    
    def best_split(self,t):
        #Selects the best question and split based on the gini score
        maxm=0
        best_question = None
        tr_row=[]
        fl_row=[]
            
        for i in range(t.shape[1]-1):
            y=np.unique(t[:,i])                         #no of unique labels in a particular column
            m=y.shape[0]                                #no of examples
            for j in range(m):
                question = self.Question(i,y[j])        #each unique label is considered a question one at a time
                tr_row , fl_row = self.split(t,question)#splits the rows based on the question
                if(len(fl_row)==0 or len(tr_row)==0):
                    continue                            #if any of the branch has zero rows,the question is skipped
                
                info_gain= self.information_gain(tr_row,fl_row,self.gini(t))  #information gain is calculated
                
                if(info_gain&gt;maxm):
                    """best question
                       with maximum informaion
                       gain is selected"""
                    maxm = info_gain                 
                    best_question = question
                
        return maxm,best_question

    
    
   
    def split(self,t,question)
    #Splits the dataset based on the best question
        tr_row=[]       
        fl_row=[]
        for k in range(t.shape[0]):
            """checks every row of the dataset 
               with the queston & if it matches,
               it is appended to the true rows
               else to the false rows"""
            if question.check(t[k]):
                tr_row=np.append(tr_row,t[k])   
            else:
                fl_row=np.append(fl_row,t[k])
                    
        tr_row = np.reshape(tr_row,(len(tr_row)//t.shape[1],t.shape[1]))   #just reshapes the one-d matrix into a readable 2d matrix
        fl_row = np.reshape(fl_row,(len(fl_row)//t.shape[1],t.shape[1]))   #just reshapes the one-d matrix into a readable 2d matrix
    
        return tr_row,fl_row
    
    
    
    
    
    class Decision_Node:
        #Stores the different question,true branch and false branch for all parts of the tree
        def __init__(self,question,true_branch,false_branch):
            self.question = question                        
            self.true_branch = true_branch
            self.false_branch = false_branch


            
            
    class Leaf:
        #the terminal of a tree is the leaf
        def __init__(self,t):
            self.predictions = D_TREE().label_count(t)    

            
            
            

    def tree(self,t):
        """the most important part of the entire algorithm
        this is where the tree is constructed from the root 
        to the leaves"""
        gain,question = self.best_split(t)                #best question with maximum gain is selected
        if(gain==0):
            return self.Leaf(t)                           #no gain indicates that leaf is reached
        
        """if the control has reached this far,it means
        there is useful gain and teh datset can be subdivided
        or branched into true rows and false rows"""
        true_rows , false_rows = self.split(t,question)    
        true_node = self.tree(true_rows)                  #A recursion is carried out till all the true rows are found out
        false_node= self.tree(false_rows)                 #after true rows,the false rows are assigned to the node in a reverse fashion
                                                            
        return self.Decision_Node(question,true_node,false_node)  
    
    
    
    
    
    def check_testing_data(self,test,node):
        #checks the testing data by recursively calling itself
        if isinstance(node,self.Leaf):
            return node.predictions        #when the leaf is reached prediction is made
        
        """a row is made to travel in the tree,till it reaches a leaf,
           it is checked with all decision nodes, and accordingly
           it travels along true branch or false branch,till
           it reaches a leaf"""
        if(node.question.check(test)):
            return self.check_testing_data(test,node.true_branch)
        else:
            return self.check_testing_data(test,node.false_branch)
        
    
    
    
    
    def print_leaf(self,LEAF):
        #prints a leaf
        p={}
        for i in LEAF.keys():
            p[i] = str(100*LEAF[i]/float(sum(LEAF.values()))) + "%"
        
        print(p)
        
    
    
    
    
    def pred(self,X_test):
        #predicts values for test data
        y_pred=[0]*X_test.shape[0]
        for i in range(X_test.shape[0]):
            """when a row reaches a particular leaf
               it is assigned the label which
               appears maximum in the leaf"""
            r= self.check_testing_data(X_test[i],self.my_tree)      #deals with one row at a time
            y_pred[i] = max(r.keys(), key=(lambda k: r[k]))         
        return y_pred
    
    
    
    
    
    def accuracy(self,y_test,y_pred):
        #Calculate the accuracy of the model
        return np.mean(y_test==y_pred)*100
    
    
    

#Importing libraries
import numpy as np

#Importing data set
from sklearn.datasets import load_breast_cancer
data = load_breast_cancer()


X=data['data']
Y=data['target']
Y=np.reshape(Y,(Y.shape[0],1))
X=X[:,:5]
X=np.append(X,Y,axis=1)
#Separating training set and test set
sz = len(X)//4
X_test=X[:sz,:]
X_train=X[sz:,:]   #X_train already contains Y_train as its last column so no need to define it separately
Y_test=X_test[:,-1]
n=X.shape[1]
#Training the algorithm
train=D_TREE()
train.fit(X_train)
#Predictions on test data
y_pred=train.pred(X_test)
#A few predictions
for i in range(10):
    train.print_leaf(train.check_testing_data(X_test[i],train.my_tree))
{1.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{1.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{1.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{0.0: &#x27;100.0%&#x27;}
{1.0: &#x27;100.0%&#x27;}
print("Accuracy of my model : ",train.accuracy(Y_test,y_pred),"%")
Accuracy of my model :  80.28169014084507 %
#calculating accuracy using sklearn model
from sklearn import tree
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X_train[:,0:n-1], Y_train)
y_pred=clf.predict(X_test[:,:n-1])
error=(y_pred==Y_test.flatten())
print("accuracy of sklearn model = ",np.mean(error)*100,"%")
accuracy of sklearn model =  80.28169014084507 %