<jupyter_start><jupyter_text>Introduction The intent of this notebook is to implement decision tree from scratch, following modular structure for each component and function so that it can be used in other modules and can be customized easily.You may be thinking why to implement from scratch rather than using ready to use available packages from sklearn.Learning and in future use the same for customized implementing if required is the main idea.  Background of decision tree -	Decision trees are a method of splitting the data based on features to either classify or predicting some value.-	Each branch in a decision tree divides the data into one or two (or several, if the tree is not binary) groups.-	Each leaf node is allocated with a single label (class or predicted value). -	When predicting using the decision tree, the data is allocated to the appropriate leaf node, and the prediction is the label of that leaf node.  ImplementationFor implementation we need to answer two question - What type of question to ask and wheni.e. out of all the available features which feature to use for splitting the data and when?There are a family of decision tree algorithms that can be used to answer this question, some are- ID3 (Iterative Dichotomiser 3)- C4.5 - C5.0- CART (Classification and Regression Trees)Here we will be using CART algorithm for implementation  Some details of CART - CART algorithm produces only binary trees- It is a greedy algorithm how it's work- All tree will start with root node(it will receive all the training set)- Now each node will ask a true/false question for one of the features(which feature we will see later)- In response to above question we will split the data into two subsets.- This subset becomes input to two child node that we add to the tree- The goal of the split is to unmix data, to create purest possible distribution as we go down the tree. (how to check purity we will see later)- We will keep dividing the data until there is no further question to ask at which point, we will add a leaf node.Now coming back to the question of splitting the data, what question to ask and when?- Before we can think of "what question to ask" we need all available question for which we have to find out how many questions can unmix the label or class- we can find the number of question to ask at any node using metric Gini Impurity.- and which question to ask using concept of Information Gain.- we will use Gini Impurity and Information Gain to ask best question at each point.Note: the best question is one that reduces our uncertainity the most, Gini Impurity caculate how much uncertinity is there in the node and Information gain let us know how much uncertinity is reduced by the that question. Gini ImpurityGini Impurity is a measurement of the likelihood of an incorrect classification of class labels from the data set. Information GainInformation gain is the reduction in entropy or surprise by transforming a dataset and is often used in training decision trees. Information gain is calculated by comparing the entropy of the dataset before and after a transformation. References:- https://mlexplained.com/2018/01/05/lightgbm-and-xgboost-explained/- https://www.youtube.com/watch?v=LDRbO9a6XPU<jupyter_code># import utils
from utils.is_numeric import is_numeric
from utils.class_counts import class_counts
from utils.gini import gini
from utils.info_gain import info_gain
from utils.unique_vals import unique_vals
training_data = [
    ['Green', 3, 'Apple'],
    ['Yellow', 3, 'Apple'],
    ['Red', 1, 'Grape'],
    ['Red', 1, 'Grape'],
    ['Yellow', 3, 'Lemon'],
]
# Column labels.
# These are used only to print the tree.
header = ["color", "diameter", "label"]
class Question:
    """ A Question is used to partition a dataset 

    This class just records a 'column number' and a 'column value'.
    The 'match' method is used to compare the feature value in an example 
    to the feature value store in the question.
    """

    def __init__(self, column, value):
        self.column = column
        self.value = value

    def match(self, example):
        """ compare the feature value in an example to the feature value in this question """
        val = example[self.column]
        if is_numeric(val):
            return val >= self.value
        else:
            return val == self.value
    
    def __repr__(self):
        # This is just a helper method to print
        # the question in a readable format.
        condition = "=="
        if is_numeric(self.value):
            condition = ">="
        return "Is %s %s %s?" % (
            header[self.column], condition, str(self.value))
        
# test
q = Question(0,'Green')
q
def partition(rows, question):
    """ Partitions a dataset. For each row in the dataset, 
    check if it matches the question if so, 
    add it to true_rows else to fasle_rows"""
    true_rows, false_rows = [], []
    for row in rows:
        if question.match(row):
            true_rows.append(row)
        else:
            false_rows.append(row)
    return true_rows, false_rows
def find_best_split(rows, column_number):
    """ Find the best quesiton to ask by iterating over every feature / value
    and calculating the information gain"""
    best_gain = 0 # track of the best Information gain
    best_quetion = None # best question for the gain
    current_uncertainty = gini(rows, column_number) # column = -1 as or target is in last column
    n_features = len(rows[0]) -1 # number of columns
    for col in range(n_features):
        values = unique_vals(rows,col) # unique values in the columns
        for val in values: # for each unique value in the column
            question = Question(col,val)
            
            # try splitting the dataset
            true_rows, false_rows = partition(rows, question)
            
            # skip the split if it doesn't divide the dataset
            if len(true_rows) == 0 or len(false_rows) == 0:
                continue
            
            # calculate information gain on this split
            gain = info_gain(true_rows, false_rows, current_uncertainty, column_number)
            
            # You actually can use '>' instead of '>=' here
            # but I wanted the tree to look a certain way for our toy dataset.
            if gain >= best_gain:
                best_gain,best_quetion = gain, question
    
    return best_gain, best_quetion
            
# test
best_gain, best_question = find_best_split(training_data,column_number=-1)
best_question
class Leaf:
    """ A Leaf node classifies data.
    This holds a dictionary of class and number of times it appears 
    in the rows from the training data that reaches this leaf.
    e.g Apple:2"""
    def __init__(self, rows):
        self.predictions = class_counts(rows,column_number=-1)
class Decision_Node:
    """A Decision Node asks a question.
    This holds a reference to the question and the two child"""
    
    def __init__(self, question, true_branch, false_branch):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch
def build_tree(rows):
    """Build the tree
    recursively build the tree"""
    
    # try partitioning the dataset on each of the unique attribute,
    # calculate the information gain and return the question 
    #that produces the hightes gain.
    gain, question = find_best_split(rows, column_number=-1)
    
    # Base case: no further information gain, 
    # since we cannot ask futher question we'll return a leaf.
    if gain==0:
        return Leaf(rows)
    
    # if came upto this point then there are useful feature to partition
    true_rows, false_rows = partition(rows, question)
    
    # Recursively build the true branch
    true_branch = build_tree(true_rows)
    # Recursively build the false branch
    false_branch = build_tree(false_rows)
    
    # Return a Question node.
    # This records the best feature / value to ask at this point, as well as the branches to follow dependingo on the answer.
    return Decision_Node(question, true_branch, false_branch)
def print_tree(node, spacing=""):
    """ Funtion to print the tree structure"""
    # base case if its a leaf node
    if isinstance(node, Leaf):
        print(spacing + "Predict",node.predictions)
        return
    # if not leaf print the question
    print(spacing + str(node.question))
    
    # call the function recursively on the true and false branch
    print (spacing + '--> True:')
    print_tree(node.true_branch, spacing + "  ")

    print (spacing + '--> False:')
    print_tree(node.false_branch, spacing + "  ")
my_tree = build_tree(training_data)
print_tree(my_tree)
def classify(row, node):
    """ Based on the rule of recursion, decide which label to assign for current row"""
    if isinstance(node,Leaf):
        return node.predictions
    # decide whether to move left or right
    if node.question.match(row):
        return classify(row, node.true_branch)
    else:
        return classify(row, node.false_branch)
    
# test
classify(training_data[0], my_tree)
def print_leaf(counts):
    """A nicer way to print the predictions at a leaf."""
    total = sum(counts.values()) * 1.0
    probs = {}
    for lbl in counts.keys():
        probs[lbl] = str(int(counts[lbl] / total * 100)) + "%"
    return probs
print_leaf(classify(training_data[0], my_tree))
print_leaf(classify(training_data[1], my_tree))
# Evaluate
testing_data = [
    ['Green', 3, 'Apple'],
    ['Yellow', 4, 'Apple'],
    ['Red', 2, 'Grape'],
    ['Red', 1, 'Grape'],
    ['Yellow', 3, 'Lemon'],
]
for row in testing_data:
    print ("Actual: %s. Predicted: %s" %
           (row[-1], print_leaf(classify(row, my_tree))))<jupyter_output>Actual: Apple. Predicted: {'Apple': '100%'}
Actual: Apple. Predicted: {'Apple': '50%', 'Lemon': '50%'}
Actual: Grape. Predicted: {'Grape': '100%'}
Actual: Grape. Predicted: {'Grape': '100%'}
Actual: Lemon. Predicted: {'Apple': '50%', 'Lemon': '50%'}<jupyter_text>Testing with Social media data<jupyter_code># test for social media dataset
import pandas as pd
from sklearn.model_selection import train_test_split
df=pd.read_csv('Social_Network_Ads.csv')
print(df.head())
train_df,test_df = train_test_split(df)
header = ["Gender","Age","EstimatedSalary","Purchased"]
tree_fil = build_tree(train_df.drop('User ID',axis=1).values)
print_tree(tree_fil)
di={1:2}
# dir(di)
list(di.keys())[0]
for row in test_df.drop('User ID',axis=1).values:
    model_pred = classify(row, tree_fil)
    status=""
    if list(model_pred.keys())[0] == row[-1]:
        status="Correct"
    else:
        status="Incorrect"
    print(model_pred)
    print ("Actual: %s. Predicted: %s, Status: %s" %
           (row[-1], print_leaf(model_pred), status))<jupyter_output>{0: 26}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{1: 20}
Actual: 1. Predicted: {1: '100%'}, Status: Correct
{1: 9}
Actual: 1. Predicted: {1: '100%'}, Status: Correct
{1: 25}
Actual: 1. Predicted: {1: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{1: 25}
Actual: 1. Predicted: {1: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{1: 20}
Actual: 1. Predicted: {1: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 7}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 3}
Actual: 1. Predicted: {0: '100%'}, Status: Incorrect
{0: 26}
Actual: 0. Predicted: {0: '100%'}, Status: Correct
{0: 117}
Actual: 0. Predicted: {0: '100%'}, Status[...]
{'fraction_non_alphanumeric': 0.09774881516587677, 'fraction_numerical': 0.018026404874746108, 'mean_word_length': 3.4011173184357544, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 14, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '97467', 'license': 'MIT', 'n_tokens_mistral': 3605, 'n_tokens_neox': 3392, 'n_words': 1451, 'path': 'random_forest/decision_tree_main.ipynb', 'repo_name': 'somexgupta/ml_algorithm_from_scratch_in_python', 'size': '11816'}