<jupyter_start><jupyter_text>Copyright 2020 <NAME>(<NAME>Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 .<jupyter_code>import numpy as np
import pandas as pd
from sklearn import datasets
from collections import OrderedDict
iris = datasets.load_iris()
x = iris.data
y = iris.target[:,np.newaxis]
columns = ['Sepal Length', 'Sepal Width', 'Petal Length', 'Petal Width', "Target"]
df = pd.DataFrame(np.concatenate((x,y),axis=1), columns =  columns)
df.Target = df.Target.astype('category')<jupyter_output><empty_output><jupyter_text>We shuffle the rows of the dataframe, and split into train and test sets.<jupyter_code>#len(df) = 150
df = df.sample(frac=1)
df_train = df[:125]
df_test = df[125:]
def partition(df, column, value):
  """
  rows - a dataframe
  column - a column label, string or int
  value - if a float, then the question >= ? is asked. if categorical the question ==? is asked.
  Returns a list of rows for which the question is True and one for which question is False.
  """
  if df[column].dtype.name in ["category","object","bool"]:
    return df.loc[df[column]==value], df.loc[df[column]!=value]
  else:
    return df.loc[df[column]>=value], df.loc[df[column]<value]
def gini_impurity(df):
  """
  input:
  df - a dataframe with the last column containing class labels
  returns: 
  the gini impurity"""

  counts = df.iloc[:,-1].value_counts()
  impurity = 1
  for label in counts.index:
    if df.iloc[:,-1].dtype.name == 'category' and isinstance(label,float):
      label = int(label)
      prob_label = counts.iloc[label]/counts.sum()
    else:
      prob_label = counts[label]/counts.sum() 
    impurity = impurity - prob_label**2
  return impurity
def information_gain(left, right, current):
  """Returns the information gain of a node split"""

  p = float(len(left))/(len(left)+len(right))
  return current -p * gini_impurity(left) - (1-p)*gini_impurity(right)

#test
current = gini_impurity(df)
left,right = partition(df,"Sepal Width", 3.0)
information_gain(left,right,current)
def best_split(df):
  """
  Finds the best partition over the feature columns
  Input:
  df - a pd.Dataframe
  Returns:
  best_gain - information gain of best partition
  saved_col - the partition feature
  saved_value - the partition threshold/value
  """
  current = gini_impurity(df)
  best_gain = 0
  saved_col = None
  saved_value = None

  for column in df.columns[:-1]:
    values = df[column]
    for value in values:
      # split the data
      left, right = partition(df, column, value)
      # skip the split if one of the splits is empty
      if len(left) == 0 or len(right) == 0:
        continue
      info_gain = information_gain(left, right, current)
      if info_gain > best_gain:
        best_gain = info_gain
        saved_col = column
        saved_value = value
  return best_gain, saved_col, saved_value
class Leaf:
  def __init__(self, df):

    #a dictionary of counts of target classes in the Leaf's branch
    self.predictions = df.iloc[:,-1].value_counts().to_dict()
    self.predictions = OrderedDict(sorted(self.predictions.items()))
    self.__sum = np.asarray(list(self.predictions.values())).astype(float).sum()

    #normalize the counts to return a dictionary of confidences
    self.predict = {key:str(value/self.__sum) for (key,value) in self.predictions.items()}
    self.predict = OrderedDict(sorted(self.predict.items()))
class Node:
  def __init__(self, col, value, left, right):
    """
    Inputs:
    col - a dataframe column index
    value - a value in the column
    left - a dataframe
    right - a dataframe
    """

    self.threshold = (col,value)
    self.left = left
    self.right = right
def build_tree(df, depth = 0, max_depth = None):

  """Recursively build the tree from df using partitions calculated with CART
    Inputs:
    df - a pd.Dataframe
    Returns:
    a tree of Node and Leaf"""
  
  gain, col, val = best_split(df)

  #base cases:
  #reach Leaf node
  #max depth is reached
  if gain == 0:
    return Leaf(df)
  if isinstance(max_depth,int) and depth >= max_depth:
    return Leaf(df)
  
  left, right = partition(df, col, val)

  #recursive calls
  left_branch = build_tree(left, depth + 1, max_depth)
  right_branch = build_tree(right, depth + 1, max_depth)
  return Node(col,val, left_branch, right_branch)
def print_tree(node, df, spacing= ""):
    """Recursively prints the tree from df """

    #base case: node is Leaf
    if isinstance(node,Leaf):
        print (spacing + "Predict", node.predict)
        return

    (col,val) = node.threshold
    
    if df[col].dtype.name in ["category","object","bool"]:
      print( df[col].dtype.name )
      print (spacing + str(col)+"=="+str(val)+"?")
    else:
      print (spacing + str(col)+">="+str(val)+"?")     


    #recursive calls  
    print (spacing + '--> True:')
    print_tree(node.left, df, spacing + "  ")
    print (spacing + '--> False:')
    print_tree(node.right, df, spacing + "  ")

tree = build_tree(df, max_depth = 3)
print_tree(tree, df)
def classify(row, node):
    """Recursively follow the tree
      Inputs:
      row - a dataframe row with features
      node - a tree to traverse
      returns:
      a dictionary with predicted probabilities"""
    if isinstance(node, Leaf):
        return node.predict
    col, val = node.threshold

    if row[col].dtype.name == "float64":
      if row[col]>=val:
        return classify(row, node.left)
      else:
        return classify(row, node.right)
    else:
      if row[col]==val:
        return classify(row, node.left)
      else:
        return classify(row, node.right)
def make_rand_tree(df, k, feature_num, depth = 0, max_depth = None):
  """Recursively build the tree from df using partitions calculated with feature subsampling
    Inputs:
    df - a pd.Dataframe
    k - number of features to subsample
    feature_num - total number of features
    Returns:
    a tree composed of Node and Leaf
    """

  #Randomly choose k feature columns
  columns_randindex = np.random.choice(np.arange(feature_num), k, replace = False)
  columns_randindex = np.sort(columns_randindex)
  columns = df.columns[columns_randindex]

  reduced_df = df[columns]
  #we calculate the split based on the reduced dataframe
  gain, col, val = best_split(reduced_df)
  if gain == 0:
    return Leaf(df)
  if isinstance(max_depth,int) and depth >= max_depth:
    return Leaf(df)

  left, right = partition(df, col, val)

  #recursive calls
  left_branch = make_rand_tree(left, k, feature_num, depth + 1, max_depth)
  right_branch = make_rand_tree(right, k, feature_num, depth + 1, max_depth)
  return Node(col, val, left_branch, right_branch)
class Random_forest():
  def __init__(self, k, m, df):
    """ 
    Inputs:
    k - number of features to subsample
    m - number of trees
    df - a pd.Dataframe
    """
    self.k = k
    self.m = m
    self.df = df
    self.num_features = len(df.columns) - 1
    self.trees = None
    self.df_samples = [df.sample(frac = 1, replace = True) for i in range(self.m)]

  def train(self, max_depth = None):
    df_samples = self.df_samples
    self.trees = [make_rand_tree(df, self.k, self.num_features) for df in df_samples]

  def predict(self, row):
    """Predicts an integer output of a single row. The prediction is returned as an integer corresponding to the index of the OrderedDict.
      i.e. The classes are sorted, and the prediction returns the index.
    """

    predictions = [classify(row, tree) for tree in self.trees]
    average_pred = np.asarray([list(dic.values()) for dic in predictions]).astype(float)
    average_pred = np.mean(average_pred, axis = 0)
  
    return np.argmax(average_pred)

  def predictions(self, df):
    """
    Outputs an array of predictions from the rows of Dataframe df
    """
    predictions = []
    for i in range(len(df)):
      row = df.iloc[i]
      predictions.append(self.predict(row))
    return predictions

  def evaluate(self,test):
    """
    Outputs the prediction accuracy of a Dataframe test - test.iloc[:,-1] must be the target column
    """
    length = float(len(test))     
    predictions = self.predictions(test)

    return ((predictions == test.iloc[:,-1])).sum()/length
rand_forest = Random_forest(2, 4, df_train)
rand_forest.train()
rand_forest.predict(df.iloc[5])
rand_forest.evaluate(df_test)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11816578483245149, 'fraction_numerical': 0.005878894767783657, 'mean_word_length': 3.3890608875129, 'pattern_counts': {'":': 1, '<': 12, '<?xml version=': 0, '>': 20, 'https://': 0, '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': '391488', 'license': 'Apache-2.0', 'n_tokens_mistral': 2827, 'n_tokens_neox': 2720, 'n_words': 838, 'path': 'From_Scratch_RandomForest.ipynb', 'repo_name': 'kyle-gao/ML_ipynb', 'size': '8508'}