Random_Forest.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "150\n",
      "[[5.1 3.5 1.4 0.2]\n",
      " [4.9 3.  1.4 0.2]\n",
      " [4.7 3.2 1.3 0.2]\n",
      " [4.6 3.1 1.5 0.2]\n",
      " [5.  3.6 1.4 0.2]]\n",
      "[0 0 0 0 0]\n",
      "[117  26  71  17 108]\n",
      "[[7.7 3.8 6.7 2.2]\n",
      " [5.  3.4 1.6 0.4]\n",
      " [6.1 2.8 4.  1.3]\n",
      " [5.1 3.5 1.4 0.3]\n",
      " [6.7 2.5 5.8 1.8]\n",
      " [6.4 2.8 5.6 2.1]\n",
      " [5.  2.  3.5 1. ]\n",
      " [5.9 3.2 4.8 1.8]\n",
      " [6.1 3.  4.6 1.4]\n",
      " [5.7 3.  4.2 1.2]]\n",
      "[2 0 1 0 2 2 1 1 1 1]\n"
     ]
    }
   ],
   "source": [
    "# upload the data\n",
    "# IRIS dataset is chosen for training, testing and predictions\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn import datasets\n",
    "%matplotlib inline\n",
    "import numpy as np\n",
    "\n",
    "# import Iris Dataset \n",
    "iris = datasets.load_iris()\n",
    "data = iris.data  # we only take the first two features.\n",
    "labels = iris.target\n",
    "\n",
    "# take a look at the data\n",
    "print(len(data))\n",
    "print(data[0:5])\n",
    "print(labels[0:5])\n",
    "\n",
    "# shuffle both the data and its labels \n",
    "random_indices = np.random.permutation(len(data))\n",
    "print(random_indices[:5])\n",
    "data = data[random_indices]\n",
    "labels = labels[random_indices]\n",
    "\n",
    "# fix the randomly chosen samples, so that they will not keep shuffling everytime the cell is executed\n",
    "\n",
    "# take a look at the shuffled data\n",
    "print(data[:10])\n",
    "print(labels[:10])\n",
    "\n",
    "# split the data for training and testing. \n",
    "# Build the model with training set and then check the accuracy with testing set\n",
    "# use 80 percent of the data for training and 20 percent for testing\n",
    "X_train = data[:130] \n",
    "y_train = labels[:130]\n",
    "X_test = data[130:]\n",
    "y_test = labels[130:]\n",
    "#prediction_data = data[140:]\n",
    "#prediction_labels = labels[140:]\n",
    "#len(prediction_data) == len(prediction_labels)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To make a Random Forest there needs to be n decision trees which are the building blocks of a Random Forest.\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Decision_Tree():\n",
    "    def __init__(self, training_data, training_labels, test_data, test_labels, min_training_gini = 0.05): \n",
    "        # initiate the decision tree with all the training data & labels, set an optional min_training_gini value\n",
    "        self.training_data = training_data\n",
    "        self.training_labels = training_labels\n",
    "        self.test_data = test_data\n",
    "        self.test_labels = test_labels\n",
    "        self.min_training_gini = min_training_gini\n",
    "\n",
    "                \n",
    "    def train(self):\n",
    "        # create the root node\n",
    "        self.root = Node(data = self.training_data, labels = self.training_labels)\n",
    "        # make this part below recallable\n",
    "        key_node = self.root\n",
    "        gini_of_key_node = self.gini(key_node.labels)\n",
    "        if gini_of_key_node < self.min_training_gini: \n",
    "            print('the requested min gini is too high, decrease the min required gini for splits')\n",
    "            return\n",
    "        if len(key_node.labels) <= 1: return\n",
    "        assert(key_node.data != None).all() \n",
    "        if gini_of_key_node > self.min_training_gini:\n",
    "            self.split(key_node)\n",
    "    \n",
    "    \n",
    "    def split(self, key_node):\n",
    "        # if there is not enough data to split, return\n",
    "        # if gini is reaching the min standard, assign the label of the node \n",
    "        if len(key_node.labels) <= 1 or self.gini(key_node.labels) <= self.min_training_gini:\n",
    "            key_node.node_id = self.most_common_label(key_node.labels)\n",
    "            return \n",
    "        else:\n",
    "            # do the split\n",
    "            split_loc, split_value, True_list, True_label, False_list, False_label = self.best_split(key_node.data, key_node.labels)\n",
    "            # assign the attributes to the key_node that is split into two parts\n",
    "            key_node.split_loc = split_loc\n",
    "            key_node.split_value = split_value\n",
    "            \n",
    "            # if split does not yield two seperate nodes, give an ID to the node and return\n",
    "            if True_list == None or False_list == None: # No need to branch out\n",
    "                key_node.node_id = self.most_common_label(key_node.labels)\n",
    "                return\n",
    "            \n",
    "            else:\n",
    "                # create a node, assign the attributes to the leftchild, connect with the parent node\n",
    "                new_node = Node(data = True_list, labels = True_label, parent_T_F = True)\n",
    "                new_node.parent = key_node\n",
    "                key_node.leftchild = new_node\n",
    "\n",
    "                # create a node, assign the attributes to the rightchild, connect with the parent node\n",
    "                new_node = Node(data = False_list, labels = False_label, parent_T_F = False)\n",
    "                new_node.parent = key_node\n",
    "                key_node.rightchild = new_node\n",
    "            \n",
    "        # create branches recursively\n",
    "        self.split(key_node.leftchild)\n",
    "        self.split(key_node.rightchild)\n",
    "    \n",
    " \n",
    "    \n",
    "    def test(self, test_data, test_labels):\n",
    "        self.test_results = []\n",
    "        for each_instance in test_data: # test each instance \n",
    "            current_node = self.root\n",
    "            if self.root == None: return\n",
    "            while current_node.leftchild != None and current_node.rightchild != None:\n",
    "                # split_loc, split_value, split_T_F will be imported\n",
    "                if current_node.split_value < each_instance[current_node.split_loc]: # go to the leftchild\n",
    "                    current_node = current_node.leftchild\n",
    "                else: # go to the rightchild\n",
    "                    current_node = current_node.rightchild\n",
    "            self.test_results.append(current_node.node_id)\n",
    "        accuracy_of_test_data = self.accuracy(self.test_results, self.test_labels)     \n",
    "        return accuracy_of_test_data\n",
    "        \n",
    "        \n",
    "    def predict(self, data_to_be_labeled): # takes a 2d array with multiple instances and outputs predicted labels\n",
    "        pred_results = []\n",
    "        for each_instance in data_to_be_labeled: # test each instance \n",
    "            current_node = self.root\n",
    "            while current_node.leftchild != None and current_node.rightchild != None:\n",
    "                # split_loc, split_value, split_T_F will be imported\n",
    "                if current_node.split_value < each_instance[current_node.split_loc]: # go to the leftchild\n",
    "                    current_node = current_node.leftchild\n",
    "                else: # go to the rightchild\n",
    "                    current_node = current_node.rightchild\n",
    "            if current_node.node_id != None:\n",
    "                pred_results.append(current_node.node_id)   \n",
    "        return pred_results\n",
    "        \n",
    "        \n",
    "    def class_count(self, labels): # counts the number of labels in the target data (label list)\n",
    "        a_dict = {}\n",
    "        for label in labels:\n",
    "            if label in a_dict.keys():\n",
    "                a_dict[label] += 1\n",
    "            else:\n",
    "                a_dict[label] = 1\n",
    "        return a_dict\n",
    "\n",
    "\n",
    "    def most_common_label(self, labels): # returns the most commonly seen item in an array\n",
    "        a_dict = self.class_count(labels)\n",
    "        most_common = 0\n",
    "        for k,v in a_dict.items():\n",
    "            if v > most_common:\n",
    "                most_common = v\n",
    "                set_the_most_freq_item = k\n",
    "        return set_the_most_freq_item\n",
    "\n",
    "    \n",
    "    def gini(self, labels): # calculates the impurity of the target list\n",
    "        count = self.class_count(labels)\n",
    "        gini_impurity = 1\n",
    "        for k,v in count.items():\n",
    "            prob = v / len(labels)\n",
    "            gini_impurity -= prob**2\n",
    "        return gini_impurity\n",
    "\n",
    "\n",
    "    def information_gain(self, labels, T_labels, F_labels): \n",
    "        # after the split is done, compare the differences in gini and output the information gain\n",
    "        T_len = len(T_labels)\n",
    "        F_len = len(F_labels)\n",
    "        total_len = len(labels)\n",
    "        info_gain = self.gini(labels) - (T_len/total_len * self.gini(T_labels)) - (F_len/total_len * self.gini(F_labels))\n",
    "        return info_gain\n",
    "\n",
    "\n",
    "    def partition(self, data, labels, column, value): # does partition based on the specified column's value\n",
    "        assert(len(data) == len(labels))\n",
    "        if len(data) <= 1: return\n",
    "        T_data, T_label, F_data, F_label = [], [], [], [] # both the data and labels will split into two lists\n",
    "        for i in range(len(data)):\n",
    "            if data[i][column] >= value:\n",
    "                T_data.append(data[i])\n",
    "                T_label.append(labels[i])\n",
    "            else:\n",
    "                F_data.append(data[i])\n",
    "                F_label.append(labels[i])\n",
    "        return T_data, T_label, F_data, F_label\n",
    "\n",
    "\n",
    "    def best_split(self, data, labels): # decides which attribute is the best for the split that yields highest info gain\n",
    "        if len(data) <= 1: return # not enough data, terminate the function\n",
    "        if len(set(labels)) == 1: return None # there is nothing to split, return None\n",
    "        max_info_gain = 0\n",
    "        # loop over all columns of data\n",
    "        for att_loc in range(len(data[0])):\n",
    "            # find all the atttributes in each column\n",
    "            set_of_att = set([row[att_loc] for row in data])\n",
    "            # for each instance\n",
    "            for each_att in set_of_att:\n",
    "                # do the partition for column and attributes\n",
    "                T_data, T_label, F_data, F_label = self.partition(data, labels, att_loc, each_att)\n",
    "                info_gain = self.information_gain(labels, T_label, F_label)\n",
    "                if info_gain > max_info_gain:\n",
    "                    max_info_gain = info_gain\n",
    "                    best_split_loc = att_loc\n",
    "                    best_split_att = each_att\n",
    "                    True_list = T_data\n",
    "                    False_list = F_data\n",
    "                    True_label = T_label\n",
    "                    False_label = F_label\n",
    "        # return the best split's attributes and the T and F lists based on the best info gain achieved\n",
    "        return (best_split_loc, best_split_att, True_list, True_label, False_list, False_label)\n",
    "\n",
    "\n",
    "\n",
    "    # accuracy will be calculated by comparing obtained targets with the actual labels \n",
    "    # Ex: accuracy(our_obtained_target_list, actual_labels) for the accuracy  \n",
    "    def accuracy(self, testing_labels, actual_labels):\n",
    "        assert (len(testing_labels) == len(actual_labels))\n",
    "        testing_labels = np.array(testing_labels)\n",
    "        actual_labels = np.array(actual_labels)\n",
    "        matching_labels = (testing_labels == actual_labels) \n",
    "        # this will output an array with False and True results for each labels \n",
    "        accuracy_of_model = sum(matching_labels) / len(testing_labels)\n",
    "        return accuracy_of_model * 100\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "class Node():\n",
    "    def __init__(self, data = None, labels = None, parent = None, node_id = None,\n",
    "                 leftchild = None, rightchild = None, split_loc = None, split_value = None, parent_T_F = None):\n",
    "    \n",
    "        self.data = data\n",
    "        self.labels = labels\n",
    "        self.parent = parent\n",
    "        self.node_id = node_id\n",
    "        self.leftchild = leftchild\n",
    "        self.rightchild = rightchild\n",
    "        self.split_loc = split_loc\n",
    "        self.split_value = split_value\n",
    "        self.parent_T_F = parent_T_F\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "80.0\n"
     ]
    }
   ],
   "source": [
    "# test the decision tree with data\n",
    "testing_results = []\n",
    "# output the test and prediction scores based on the different min accepted gini level for a split \n",
    "test_D_T = Decision_Tree(X_train, y_train, X_test, y_test, min_training_gini = 0.4)     \n",
    "test_D_T.train()\n",
    "test_accuracy = test_D_T.test(X_test, y_test)\n",
    "print(test_accuracy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sample with replacement, n training dataset chosen randomly\n",
    "# Train n decision trees with the randomly chosen portion of the training dataset\n",
    "# Take the majority vote of these trees to make a decision\n",
    "# This technique is called bagging, or bootstrap aggregating: Training the same classifier on different subsets \n",
    "# The sampling with replacement is known as a bootstrap sampling\n",
    "\n",
    "\n",
    "class Random_Forest():\n",
    "    # load all the training and test data and decide for 'n trees' and sample percentage, 'm', for each tree \n",
    "    def __init__(self, n, m, X_train, y_train, X_test, y_test, min_training_gini = 0.3): \n",
    "        self.n = n # number of trees to be created\n",
    "        self.m = m # percentage of the data allocated for each tree to train (ex: 60 means 60 percent)\n",
    "        self.min_training_gini = min_training_gini # set a min training gini for each tree\n",
    "        self.X_train = X_train\n",
    "        self.y_train = y_train\n",
    "        self.X_test = X_test\n",
    "        self.y_test = y_test\n",
    "        \n",
    "    def fit_and_test(self): # create and train multiple trees \n",
    "        # keep track of the accuracy of the voted averages of all trees with the test set  \n",
    "        # create a table to store all the test set predictions of n trees\n",
    "        self.votes = np.zeros([self.n, len(self.X_test)])\n",
    "        # with a portion of training samples, sample with replacement (BAGGING)\n",
    "        for i in range(self.n):\n",
    "            decision_tree = None\n",
    "            train_random_indices = np.random.permutation(len(self.X_train)) # shuffle the training set indices\n",
    "            portion = len(train_random_indices) * self.m // 100\n",
    "            m_random_ind_picked = train_random_indices[:portion] # take a portion of the indices\n",
    "            training_set = self.X_train[m_random_ind_picked] # prepare the training set \n",
    "            training_labels = self.y_train[m_random_ind_picked] # prepare the training labels\n",
    "            # create decision trees based on the training set and labels for each decision tree \n",
    "            decision_tree = Decision_Tree(training_set, training_labels, self.X_test, self.y_test, self.min_training_gini)\n",
    "            # train the decision tree\n",
    "            decision_tree.train()\n",
    "            # test the decsion tree with the test set\n",
    "            results = decision_tree.predict(self.X_test) # outputs the predicted labels of the test set\n",
    "            # make all predictions and append the prediction into a voting 2d array\n",
    "            # print('results', results)\n",
    "            self.votes[i] = results\n",
    "        # when the voting table is completed take the average of votes with axis = 1 and output the predictions\n",
    "        most_common_label = self.voted_average()\n",
    "        # compare the accuracy of results with the voted predictions\n",
    "        accuracy_of_test = self.accuracy(most_common_label, self.y_test)\n",
    "        return accuracy_of_test\n",
    "        \n",
    "        \n",
    "    def voted_average(self): # gets the most common item seen on axis = 1\n",
    "        N, D = self.votes.shape\n",
    "        voted_predictions = np.zeros(D)\n",
    "        # for each instance results, pick the most common element on axis = 1\n",
    "        for i in range(D):\n",
    "            labels = self.votes[:,i]\n",
    "            a_dict = {}\n",
    "            for label in labels:\n",
    "                if label in a_dict.keys():\n",
    "                    a_dict[label] += 1\n",
    "                else:\n",
    "                    a_dict[label] = 1\n",
    "            # now a_dict has the number of each labels\n",
    "            most_common = 0\n",
    "            set_the_most_freq_item = ''\n",
    "            for k,v in a_dict.items():\n",
    "                if v > most_common:\n",
    "                    most_common = v\n",
    "                    set_the_most_freq_item = k\n",
    "            voted_predictions[i] = set_the_most_freq_item\n",
    "        return voted_predictions\n",
    "        \n",
    "    \n",
    "    def accuracy(self, testing_labels, actual_labels):\n",
    "        return np.mean(testing_labels == actual_labels)*100\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test the model\n",
    "rf = Random_Forest(5, 30, X_train, y_train, X_test, y_test, min_training_gini = 0.4)\n",
    "rf.fit_and_test()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_gini: 0.0, best_n: 3, best_m: 40, best_accuracy:95.0\n"
     ]
    }
   ],
   "source": [
    "# computationally too costly for large data, good for learning purposes\n",
    "# choose the best model for n trees with m portion of the dataset that were trained with some min gini k\n",
    "def best_model():\n",
    "    # find the best model for the random forest for this dataset and save this model for predictions\n",
    "    # grid search for the best hyperparameters\n",
    "    best_accuracy = 0\n",
    "    for i in range(3,7): # 2 trees minimum and 10 trees maximum (n)\n",
    "        for j in np.arange(40,100,20): # 10 percent to underfit and 90 percent to overfit (m)\n",
    "            for k in np.linspace(0,30,5)*0.01: # gini values set\n",
    "                # instantiate the object with different i,j,k values and find the best accuracy\n",
    "                random_forest = Random_Forest(i, j, X_train, y_train, X_test, y_test, min_training_gini = k)\n",
    "                current_accuracy = random_forest.fit_and_test()\n",
    "                if current_accuracy > best_accuracy:\n",
    "                    best_accuracy = current_accuracy\n",
    "                    best_n = i\n",
    "                    best_m = j\n",
    "                    best_gini = k\n",
    "    return best_gini, best_n, best_m, best_accuracy\n",
    "best_gini, best_n, best_m, best_accuracy = best_model()\n",
    "print('best_gini: {}, best_n: {}, best_m: {}, best_accuracy:{}'.format(best_gini, best_n, best_m, best_accuracy))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}