<jupyter_start><jupyter_text>Decision TreesDecision trees are algorithms that classify data by recursively creating nodes that separate the data. In other words, this methods creates a tree where each node ask a particular question about the data to create smaller subsets.<jupyter_code>from sklearn import datasets

import numpy as np
import pandas as pd
iris = datasets.load_iris()

X = iris.data
y = iris.target

print("The dataset has", X.shape[0], "entries with", X.shape[1], "different features and", len(set(y)), "different labels.\n")

print("Dataset Head:")
print(pd.DataFrame(X, columns=iris.feature_names).head())
def Write(value):
    x = str(value)
    i = 0
    counter = 0
    
    while i < len(x):
        if x[i] == '}':
            counter -= 1
            
        if x[i] == '{':
            counter += 1
            
        if x[i] in '{}':
            if i+1 < len(x) and x[i+1] == ' ':
                x = x[:i] + '\n' + ('  ' * counter) + x[i] + '\n' + ('  ' * counter) + x[i+2:]
            else:
                x = x[:i] + '\n' + ('  ' * counter) + x[i] + '\n' + ('  ' * counter) + x[i+1:]
            
            i += 2 * (counter + 1)
        
            
        if x[i] in ',':
            if i+1 < len(x) and x[i+1] == ' ':
                x = x[:i+1] + '\n' + ('  ' * counter) + x[i+2:]
            else:
                x = x[:i+1] + '\n' + ('  ' * counter) + x[i+1:]
            
        i += 1
    print(x)<jupyter_output><empty_output><jupyter_text>Simple treeThis simple tree will assume that every feature in the dataset is categorical. This means that every node is asking if the input value corresponds exactly with one of the features and won't be able to work with values that are not already part of the training set.We will define the extension of the tree by the number of nodes it has<jupyter_code># Simple Decision Tree will asume that all features in the dataset are categorical
class SimpleDecisionTree:
    def __init__(self, nodes = 0):
        self.nodes = max(0, nodes-1)
        
        # After Training, which feature is this layer looking for 
        self.index = None
        
        # Predictions for each value a feature can take (assuming qualitative data)
        # It can be a value or a sub-decision tree
        self.prediction = dict()
    
    def Fit(self, X, y):
        # Get the best feature
        self.index = self.__Choices(X,y)
        
        # For each value that feature can take
        # Create a sub-tree if it is necessary (diverse labels available) and we can (max layers over 0)
        # or save the most probable label
        for value in set(X[:,self.index]):
            targets = set(y[X[:,self.index] == value])
            
            if self.nodes == 0 or len(targets) <= 1:
                counts = np.bincount(y[X[:,self.index] == value])
                self.prediction[value] = np.argmax(counts)
            else:
                self.prediction[value] = SimpleDecisionTree(nodes=self.nodes-1)
                self.prediction[value].Fit(X[X[:,self.index] == value], y[X[:,self.index] == value])
                
    def Predict(self, X):
        l = np.shape(X)[0]
        output = l * [-1]
        
        for i in range(l):
            value = X[i, self.index]
            if value not in self.prediction:
                continue
                
            if type(self.prediction[value]) == SimpleDecisionTree:
                output[i] = self.prediction[value].Predict(X[i].reshape((1,-1)))[0]
            else:
                output[i] = self.prediction[value]
        return output
    
    def Indexes(self):
        output = dict()
        
        tree = dict()
        for key, value in self.prediction.items():
            if type(value) == SimpleDecisionTree:
                tree[key] = value.Indexes()
            else:
                tree[key] = value
                
        output["feature"] = self.index
        output["choices"] = tree
        return output
    
        
    # Computes the information entropy for each feature
    # and returns the best option
    def __Choices(self, X, y):
        targets = set(y)
        
        index = -1
        max_value = float('Inf')
        for i in range(X.shape[-1]):
            value = 0
            for j in set(X[:,i]):
                counter = []
                for k in targets:
                    counter.append((y[X[:,i] == j] == k).sum())
                value += self.__Entropy(np.array(counter))
            
            if value < max_value:
                index, max_value = i, value
                    
        return index
            
    
    def __Entropy(self, values):
        p = values / values.sum()  
        log = p.copy()
        log[p>0] = np.log2(p[p>0])
        return ((-p * log).sum())
for i in [1,2,3]:
    tree = SimpleDecisionTree(i)

    tree.Fit(X,y)
    pred = tree.Predict(X)

    print(i, "nodes - Train accuracy:", (pred == y).sum() / len(y))
tree = SimpleDecisionTree(2)
tree.Fit(X,y)

Write(str(tree.Indexes()))<jupyter_output>{
  'feature': 3,
  'choices': 
    {
    0.2: 0,
    0.4: 0,
    0.3: 0,
    0.5: 0,
    0.6: 0,
    1.4: 
      {
      'feature': 1,
      'choices': 
        {
        2.9: 1,
        3.1: 1,
        2.7: 1,
        3.2: 1,
        3.0: 1,
        2.8: 1,
        2.6: 2
      }
      
    }
    ,
    1.5: 
      {
      'feature': 2,
      'choices': 
        {
        4.7: 1,
        4.2: 1,
        4.5: 1,
        4.9: 1,
        4.6: 1,
        5.0: 2,
        5.1: 2
      }
      
    }
    ,
    1.3: 1,
    1.6: 
      {
      'feature': 0,
      'choices': 
        {
        7.2: 2,
        6.3: 1,
        6.0: 1
      }
      
    }
    ,
    1.0: 1,
    1.1: 1,
    2.5: 2,
    2.0: 2,
    2.1: 2,
    1.2: 1,
    1.7: 
      {
      'feature': 0,
      'choices': 
        {
        4.9: 2,
        6.7: 1
      }
      
    }
    ,
    0.1: 0,
    2.2: 2,
    2.3: 2,
    1.8: 
      {
      'feature': 3,
      'choices': 
        {
        1.8: 2
      }
      
    }
    ,[...]<jupyter_text>Decision TreeIn this case, we will not assuming that each feature is categorical and we will convert the dataset before building a simple decision tree.To convert the dataset to categorical, each numerical feature will be converted to n different columns, where n is the number of unique values of that feature. To create each of the n new columns, we will be asking if the values are less than one of those unique values.<jupyter_code>class DecisionTree:
    def __init__(self, nodes):
        self.__partitions = {}
        self.__st = SimpleDecisionTree(nodes)
        
    def __is_numeric(self, values):
        return values.dtype.kind in set('buifc')
    
    def __to_categorical(self, X):
        output = np.empty((X.shape[0], 0))
        
        # Categorize each column
        for i in range(X.shape[1]):
            # skip if it is not partitionable
            if i not in self.__partitions:
                output = np.hstack( (output, X[:,i]))
                continue
            
            # add a column "feature < value", for each value present in
            # that feature
            for value in self.__partitions[i]:
                col = (X[:,i] < value).reshape((-1,1)).astype('int')
                output = np.hstack( (output, col))
                
        return output
            
    
    def Fit(self, X, y):
        # Define the partitions for each feature
        for i in range(X.shape[1]):
            if not self.__is_numeric(X[:,i]):
                continue   
            self.__partitions[i] = list(set(X[:,i]))
        
        # Transform the input to a categorical dataset
        Xc = self.__to_categorical(X)
        
        self.__st.Fit(Xc,y)
        
    def Predict(self,X):
        Xc = self.__to_categorical(X)
        return self.__st.Predict(Xc)
    
    def Indexes(self):
        indexes = self.__st.Indexes()
        
        indexes = self.__convert_index(indexes)
        return indexes
        
    def __index_feature(self, feature):
        
        for key, value in self.__partitions.items():
            if feature < len(value):
                return "[{}] < {}".format(key, value[feature])
            else:
                feature -= len(value)                    
        return -1
        
    def __convert_index(self, indexes):
        indexes["feature"] = self.__index_feature(indexes["feature"])
        
        if type(indexes["choices"]) != dict:
            return indexes
        
        for key, value in indexes["choices"].items():
            if type(value) == dict:
                indexes[key] = self.__convert_index(value)
        return indexes
for i in range(10):
    tree = DecisionTree(i)

    tree.Fit(X,y)
    pred = tree.Predict(X)

    print(i, "nodes - Train accuracy:", (pred == y).sum() / len(y))
tree = DecisionTree(2)
tree.Fit(X,y)
Write(tree.Indexes())<jupyter_output>{
  'feature': '[2] < 3.0',
  'choices': 
    {
    0.0: 
      {
      'feature': '[3] < 1.8',
      'choices': 
        {
        0.0: 2,
        1.0: 1
      }
      
    }
    ,
    1.0: 0
  }
  ,
  0.0: 
    {
    'feature': '[3] < 1.8',
    'choices': 
      {
      0.0: 2,
      1.0: 1
    }
    
  }
  
}
{'fraction_non_alphanumeric': 0.12818574514038877, 'fraction_numerical': 0.02159827213822894, 'mean_word_length': 1.522745845818578, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '410027', 'license': 'MIT', 'n_tokens_mistral': 3094, 'n_tokens_neox': 2943, 'n_words': 828, 'path': '3. Decision Trees.ipynb', 'repo_name': 'bar0net/MachineLearning_from_scratch', 'size': '9260'}