<jupyter_start><jupyter_text>Assignment 2: Decision TreesIn this assignment, you are going to implement a decision tree (or random forest) to forcast the weather. Description- You must implement a `Model` class for training and prediction:  ```python  X, y = load_dataset()  model = Model(num_features, num_classes)   training  model.fit(X, y)   prediction  y_pred = model.predict(X)  ```- Please search (Ctrl+F) for `TODO` to see what you need to do. You have to implement the classifier from scratch (do not directly use the classifier in scikit-learn).- About the dataset  - Given the **training set**, please **train/validate** on it.    (note that your model will get bad testing score if it overfits on the training set)  - After submitting the assignment, we will train on the same training set and test on the hidden **testing set** for scoring (using [f1-score](https://towardsdatascience.com/a-look-at-precision-recall-and-f1-score-36b5fd0dd3ec11b8)). Typical performance- **Random Guess**    F1-Score: 0.30    Accuracy: 0.50- **Always Predict 1**    F1-Score: 0.37    Accuracy: 0.22- **Always Predict 0**    F1-Score: 0.00    Accuracy: 0.77- **sklearn.tree.DecisionTreeClassifier**    - **Training (5-fold cross-validation mean)**      F1-Score: 0.63-0.99      Accuracy: 0.85-0.99  - **Validation (5-fold cross-validation mean)**      F1-Score: 0.50-0.60      Accuracy: 0.75-0.90<jupyter_code>###########################
# DO NOT CHANGE THIS CELL #
###########################

import os
import urllib.request
import numpy as np
import pandas as pd
from sklearn.model_selection import KFold
from sklearn.metrics import f1_score, accuracy_score


def load_dataset(url):
  """ Get and load weather dataset. """

  path = url.split('/')[-1] # get the file name from url

  if not os.path.exists(path):
    print('Download:', url)
    urllib.request.urlretrieve(url, path)

  return pd.read_pickle(path) # pickle protocol=4


def get_input_target(df):
  """ Get X and y from weather dataset. """
  
  target_column = 'RainTomorrow' # predict 1 of it rains tomorrow

  X = df.drop(columns=[target_column]).to_numpy()
  y = df[target_column].to_numpy()

  return X, y


def k_fold_cv(model_create_fn, X, y, k=5):
  """ Run k-fold cross-validation. """

  results = []

  idxs = list(range(X.shape[0]))
  np.random.shuffle(idxs)

  for i, (train_idxs, val_idxs) in enumerate(KFold(k).split(idxs)):
    splits = {'train': (X[train_idxs], y[train_idxs]),
              'val':   (X[val_idxs],   y[val_idxs]  )}

    print('Run {}:'.format(i+1))

    model = model_create_fn()
    model.fit(*splits['train']) # training

    for name, (X_split, y_split) in splits.items():
      y_pred = model.predict(X_split)

      result = {'split': name,
                'f1': f1_score(y_pred, y_split),
                'acc': accuracy_score(y_pred, y_split)}
      results.append(result)

      print('{split:>8s}: f1={f1:.4f} acc={acc:.4f}'.format(**result))

  return pd.DataFrame(results)


# @begin
# TODO: you can define or import something here (optional)
from __future__ import division
import random
import numpy as np
from scipy.stats import mode
from collections import Counter
import time



class Model:

  def __init__(self, num_features, num_classes: int):
    """
    Initialize the model.

    Args:
        num_features (int) : the input feature size.
        num_classes (int) : number of output classes.
    """

    self.num_features = num_features
    self.num_classes = num_classes
    self.max_depth=10
    # TODO: implement your model initialization here (optional)


  def build_tree(self,X,y,feature_indexes,depth):
    if len(y) < self.num_classes or entropy(y) is 0 or depth is self.max_depth:
      
      return mode(y)[0][0]
    feature_index,threshold=find_split(X,y,feature_indexes)
    X_true,y_true,X_false,y_false=split(X,y,feature_index,threshold)
    if y_false.shape[0] is 0 or y_true.shape[0] is 0:
      return mode(y)[0][0]
    
    branch_true=self.build_tree(X_true,y_true,feature_indexes,depth+1)
    branch_false=self.build_tree(X_false,y_false,feature_indexes,depth+1)
    return node(feature_index,threshold,branch_true,branch_false)
  def fit(self, X: np.ndarray, y: np.ndarray):
    """
    Train on input/target pairs.

    Args:
        X (np.ndarray) : training inputs with shape (num_inputs, num_features).
        y (np.ndarray) : training targets with shape (num_inputs,).
    """

    # TODO: implement your training algorithm here
    n_features=X.shape[1]
    n_sub_features=(self.num_features)
    feature_indexes=random.sample(range(n_features),n_sub_features)
    self.tree=self.build_tree(X,y,feature_indexes,0)
    
  def predict(self, X: np.ndarray) -> np.ndarray:
    '''
    Predict y given X.

    Args:
        X (np.ndarray) : inputs, shape: (num_inputs, num_features).
    
    Returns:
        np.ndarray : the predicted integer outputs, shape: (num_inputs,).
    '''

    # TODO: implement your prediction algorithm here
    #p = np.random.randint(0, self.num_classes, size=X.shape[0]) # (delete this)
    num_sample=X.shape[0]
    p=np.empty(num_sample)
    for i in range(num_sample):
      n=self.tree
      while isinstance(n,node):
        if X[i][n.feature_index] <= n.threshold:
          n=n.branch_true
        else:
          n=n.branch_false
      p[i]=n
    return p


    
class node(object):
  def __init__(self,feature_index,threshold,branch_true,branch_false):
    self.feature_index=feature_index
    self.threshold=threshold
    self.branch_true=branch_true
    self.branch_false=branch_false    

def find_split(X,y,feature_indexes):
  num_features=X.shape[1]
  best_gain=0
  best_feature_index=0
  best_threshold=0
  for feature_index in feature_indexes:
    values=sorted(set(X[:,feature_index]))
    total=0
    for i in range(len(values)):
      total+=values[i]
    for i in range(7):
      pivot=int(random.uniform(0,len(values)-1))
      threshold=values[pivot]
      #total=total*random.uniform(0.1,0.5)
      X_true,y_true,X_false,y_false=split(X,y,feature_index,threshold)
      gain=information_gain(y,y_true,y_false)
      if gain > best_gain:
        best_gain=gain
        best_feature_index=feature_index
        best_threshold=threshold
  return  best_feature_index,best_threshold

def split(X,y,feature_index,threshold):
  X_true=[]
  y_true=[]
  X_false=[]
  y_false=[]
  for i in range(len(y)):
    if X[i][feature_index] <= threshold :
      X_true.append(X[i])
      y_true.append(y[i])
    else:
      X_false.append(X[i])      
      y_false.append(y[i])
  X_true=np.array(X_true)
  y_true=np.array(y_true)
  X_false=np.array(X_false)
  y_false=np.array(y_false)

  return X_true,y_true,X_false,y_false

def entropy(Y):
  start=time.process_time()
  
  distribution=Counter(Y)
  s=0.0
  total=len(Y)
  for y,num_y in distribution.items():
    p_y=(num_y/total)
    s+=p_y*np.log(p_y)
  return -s  

def information_gain(y,y_true,y_false):
  return entropy(y)-(entropy(y_true)*len(y_true)+entropy(y_false)*len(y_false))/len(y)



  # TODO: define your methods if needed (optional)
# @end

###########################
# DO NOT CHANGE THIS CELL #
###########################

df = load_dataset('https://lab.djosix.com/weather.pkl')
X_train, y_train = get_input_target(df)

df.head(100000)<jupyter_output>Download: https://lab.djosix.com/weather.pkl<jupyter_text><jupyter_code>###########################
# DO NOT CHANGE THIS CELL #
###########################

create_model = lambda: Model(X_train.shape[1], 2)
k_fold_cv(create_model, X_train, y_train).groupby('split').mean()<jupyter_output>Run 1:
   train: f1=0.6157 acc=0.8534
     val: f1=0.5311 acc=0.8341
Run 2:
   train: f1=0.6066 acc=0.8553
     val: f1=0.5514 acc=0.8180
Run 3:
   train: f1=0.6106 acc=0.8545
     val: f1=0.5710 acc=0.8240
Run 4:
   train: f1=0.6043 acc=0.8527
     val: f1=0.5544 acc=0.8271
Run 5:
   train: f1=0.6003 acc=0.8450
     val: f1=0.5517 acc=0.8526
{'fraction_non_alphanumeric': 0.145268993322414, 'fraction_numerical': 0.02910419553987653, 'mean_word_length': 3.7221891731112433, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '510711', 'license': 'MIT', 'n_tokens_mistral': 2973, 'n_tokens_neox': 2818, 'n_words': 633, 'path': 'HW2/0816183_2.ipynb', 'repo_name': 'jasonsie88/Intro.-to-Artificial-Intelligence', 'size': '7937'}