random_forest_classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Random Forest Classifier from scratch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Why Random Forest?\n",
    "`Decision tree` is susceptible to high variance if it is not pruned. \n",
    "\n",
    "`Bagging` is the combination of many Decision Tree models, and the prediction follows the crowd; but these tree are highly correlated.\n",
    "\n",
    "`Random Forest`, the extension of `Bagging`, constrains the features that can be used to build the trees, forcing trees to be different. This, in turn, can give a lift in performance.\n",
    "\n",
    "`Bagging` and `Random Forest` execute Decision Tree upon a sample with replacement of the training dataset. **Sample with replacement** means that the same row may be chosen and added to samples more than once.\n",
    "\n",
    "Of that training sample, one-third of it is set aside as test data, known as the out-of-bag (`oob`) sample, used for cross-validation, finalizing that prediction.\n",
    "\n",
    "**Key Benefits**\n",
    "- Reduced risk of **overfitting**: Averaging of **uncorrelated trees** lowers the overall **variance** and prediction **error**\n",
    "- Provides flexibility: Handle both **regression** and **classification** tasks with a high degree of accuracy\n",
    "- Easy to determine **feature importance**: Gini importance, mean decrease in impurity (MDI) and permutation importance known as mean decrease accuracy (MDA)\n",
    "\n",
    "**Key Challenges**\n",
    "- Time-consuming process\n",
    "- Requires more resources\n",
    "- More complex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from csv import reader\n",
    "from math import log,sqrt\n",
    "from random import randrange, seed\n",
    "from statistics import mode\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = [[2.771244718, 1.784783929, 0],\n",
    "           [1.728571309, 1.169761413, 0],\n",
    "           [3.678319846, 2.81281357, 0],\n",
    "           [3.961043357, 2.61995032, 0],\n",
    "           [2.999208922, 2.209014212, 0],\n",
    "           [7.497545867, 3.162953546, 1],\n",
    "           [9.00220326, 3.339047188, 1],\n",
    "           [7.444542326, 0.476683375, 1],\n",
    "           [10.12493903, 3.234550982, 1],\n",
    "           [6.642287351, 3.319983761, 1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Calculating splits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini_index(groups, classes):\n",
    "\t\"\"\"\n",
    "\tGini_index(S,A) = Sum(|Si|/|S| * (1 - Sum(Pj*Pj))),\n",
    "\twhere,\n",
    "\t\tA: Attribute A\n",
    "\t\tS: Root group\n",
    "\t\tSi: Child ith when apply attribute A\n",
    "\t\tPj: % of class j\n",
    "\tComplexity: O(#groups x #classes)\n",
    "\t\n",
    "\tArgs:\n",
    "\t\t`groups`: A list of groups after choose Attribute A\n",
    "\t\t`classes`: A list of classes' values\n",
    "\tReturn:\n",
    "\t\tGini_index(S,A)\n",
    "\tFor example,\n",
    "\t>>> gini_index([[[1,0],[2,0]],[[0,1],[1,1],[2,1]]], [0,1])\n",
    "\t>>> 0.0\n",
    "\t\"\"\"\n",
    "\t# count all samples at split point\n",
    "\tn_instances = float(sum([len(group) for group in groups]))\n",
    "\t# sum weighted Gini index for each group\n",
    "\tgini = 0.0\n",
    "\tfor group in groups:\n",
    "\t\tsize = float(len(group))\n",
    "\t\t# avoid divide by zero\n",
    "\t\tif size == 0:\n",
    "\t\t\tcontinue\n",
    "\t\tscore = 0.0\n",
    "\t\t# score the group based on the score for each class\n",
    "\t\tfor class_val in classes:\n",
    "\t\t\tp = [row[-1] for row in group].count(class_val) / size\n",
    "\t\t\tscore += p * p\n",
    "\t\t# weight the group score by its relative size\n",
    "\t\tgini += (1.0 - score) * (size / n_instances)\n",
    "\treturn gini\n",
    "\n",
    "# Another way: calculate the entropy (slow)\n",
    "def entropy(groups, classes):\n",
    "\t\"\"\"\n",
    "\tEntropy(S,A) = Sum(|Si|/|S| * E(Si))\n",
    "\tE(Si) = sum (-Pj log(Pj))\n",
    "\t\"\"\"\n",
    "\t# count all samples at split point\n",
    "\tn_instances = float(sum([len(group) for group in groups]))\n",
    "\t# sum weighted Gini index for each group\n",
    "\tentropy = 0.0\n",
    "\tfor group in groups:\n",
    "\t\tsize = float(len(group))\n",
    "\t\t# avoid divide by zero\n",
    "\t\tif size == 0:\n",
    "\t\t\tcontinue\n",
    "\t\tscore = 0.0\n",
    "\t\t# score the group based on the score for each class\n",
    "\t\tfor class_val in classes:\n",
    "\t\t\tp = [row[-1] for row in group].count(class_val) / size\n",
    "\t\t\tif p ==0 or p==1:\n",
    "\t\t\t\tscore = 0\n",
    "\t\t\telse:\n",
    "\t\t\t\tscore -= p * log(p)\n",
    "\t\t# weight the group score by its relative size\n",
    "\t\tentropy += score * (size / n_instances)\n",
    "\treturn entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.38190850097688767, 0.26666666666666666)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy([[[1,0],[2,0]],[[0,0],[1,1],[2,1]]], [0,1]), \\\n",
    "gini_index([[[1,0],[2,0]],[[0,0],[1,1],[2,1]]], [0,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'attribute': 0,\n",
       " 'value': 6.642287351,\n",
       " 'groups': ([[2.771244718, 1.784783929, 0],\n",
       "   [1.728571309, 1.169761413, 0],\n",
       "   [3.678319846, 2.81281357, 0],\n",
       "   [3.961043357, 2.61995032, 0],\n",
       "   [2.999208922, 2.209014212, 0]],\n",
       "  [[7.497545867, 3.162953546, 1],\n",
       "   [9.00220326, 3.339047188, 1],\n",
       "   [7.444542326, 0.476683375, 1],\n",
       "   [10.12493903, 3.234550982, 1],\n",
       "   [6.642287351, 3.319983761, 1]])}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def test_split(index, value, dataset):\n",
    "    \"\"\"\n",
    "    Split a dataset based on an attribute and an attribute value.\n",
    "    Complexity: O(#rows)\n",
    "    \"\"\"\n",
    "    left, right = list(), list()\n",
    "    for row in dataset:\n",
    "        if row[index] < value:\n",
    "            left.append(row)\n",
    "        else:\n",
    "            right.append(row)\n",
    "    return left, right\n",
    "\n",
    "\n",
    "def get_split(dataset, n_features):\n",
    "    \"\"\"\n",
    "    This heuristic algorithm loops all rows (samples) and column (attributes), thus it is painful for computing.\n",
    "    Complexity: O(#rows^2 x #columns) x O(gini_index)\n",
    "    \"\"\"\n",
    "    classes = list(set(row[-1] for row in dataset))\n",
    "    retAttribute, retValue, retGroups, min_gini = None, None, None, 999\n",
    "\n",
    "    features = list()\n",
    "    counter = 0\n",
    "    while counter < n_features:\n",
    "        index = randrange(len(dataset[0])-1)\n",
    "        if index not in features:\n",
    "            counter = counter + 1\n",
    "            features.append(index)\n",
    "    for row in dataset:\n",
    "        for attribute in features:\n",
    "            groups = test_split(attribute, row[attribute], dataset)\n",
    "            gini = gini_index(groups, classes)\n",
    "            if gini < min_gini:\n",
    "                min_gini = gini\n",
    "                retAttribute, retValue, retGroups = attribute, row[attribute], groups\n",
    "    return {'attribute': retAttribute, 'value': retValue, 'groups': retGroups}\n",
    "\n",
    "\n",
    "get_split(dataset, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_terminal(group):\n",
    "    assert group, 'group should not be empty'\n",
    "    outcomes = [row[-1] for row in group]\n",
    "    return mode(outcomes)  # most frequency\n",
    "\n",
    "def split(node, max_depth, min_size, depth, n_features):\n",
    "    left, right = node['groups']\n",
    "    del(node['groups'])\n",
    "    # check for a no split\n",
    "    if not left or not right:  # left or right is empty list\n",
    "        node['left'] = node['right'] = to_terminal(left + right)\n",
    "        return\n",
    "    # check for max depth\n",
    "    if depth >= max_depth:\n",
    "        node['left'], node['right'] = to_terminal(left), to_terminal(right)\n",
    "        return\n",
    "    # process left child\n",
    "    if len(left) <= min_size:\n",
    "        node['left'] = to_terminal(left)\n",
    "    else:\n",
    "        node['left'] = get_split(left, n_features)\n",
    "        split(node['left'], max_depth, min_size, depth+1, n_features)\n",
    "    # process right child\n",
    "    if len(right) <= min_size:\n",
    "        node['right'] = to_terminal(right)\n",
    "    else:\n",
    "        node['right'] = get_split(right, n_features)\n",
    "        split(node['right'], max_depth, min_size, depth+1, n_features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Build a tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[X1 < 6.642]\n",
      "--[X2 < 1.785]\n",
      "----[0]\n",
      "----[X2 < 1.785]\n",
      "------[0]\n",
      "------[0]\n",
      "--[X1 < 7.498]\n",
      "----[X2 < 0.477]\n",
      "------[1]\n",
      "------[1]\n",
      "----[X2 < 3.163]\n",
      "------[1]\n",
      "------[1]\n"
     ]
    }
   ],
   "source": [
    "def build_tree(train_set, max_depth, min_size, n_features):\n",
    "\troot = get_split(dataset= train_set, n_features=n_features)\n",
    "\tsplit(root, max_depth, min_size, 0, n_features)\n",
    "\treturn root\n",
    "\n",
    "def print_tree(node, depth=0):\n",
    "    if isinstance(node, dict):\n",
    "        print('%s[X%d < %.3f]' %\n",
    "              ((depth*'-', (node['attribute']+1), node['value'])))\n",
    "        print_tree(node['left'], depth+2)\n",
    "        print_tree(node['right'], depth+2)\n",
    "    else:\n",
    "        print('%s[%s]' % ((depth*'-', node)))  # This is cool!\n",
    "\n",
    "\n",
    "tree = build_tree(dataset, 6, 1, 1)\n",
    "print_tree(tree)\n",
    "# print(tree)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(tree, input_row):\n",
    "\tif input_row[tree['attribute']] < tree['value']:\n",
    "\t\tif isinstance(tree['left'], dict):\n",
    "\t\t\treturn predict(tree['left'], input_row)\n",
    "\t\telse:\n",
    "\t\t\treturn tree['left']\n",
    "\telse:\n",
    "\t\tif isinstance(tree['right'], dict):\n",
    "\t\t\treturn predict(tree['right'], input_row)\n",
    "\t\telse:\n",
    "\t\t\treturn tree['right']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Build a forest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "def subsample_idx(data_size, sample_size):\n",
    "    \"\"\"\n",
    "    Retrieve from the `dataset` indices *randomly* with `sample_size`\n",
    "    \"\"\"\n",
    "    sample_indices = list()\n",
    "    counter = 0\n",
    "    while(counter < sample_size):\n",
    "        index = randrange(data_size)\n",
    "        sample_indices.append(index)\n",
    "        counter += 1\n",
    "    return sample_indices\n",
    "\n",
    "def bagging_predict(trees, row):\n",
    "    return mode([predict(tree, row) for tree in trees])  # most freq\n",
    "\n",
    "def random_forest(train_set, test_set, max_depth, min_size, n_features, n_trees, sample_size):\n",
    "    trees = list()\n",
    "    for i in range(n_trees):\n",
    "        sample_indices = subsample_idx(len(train_set), sample_size)\n",
    "        sample = [train_set[i] for i in sample_indices]\n",
    "        tree = build_tree(sample, max_depth, min_size, n_features)\n",
    "        trees.append(tree)\n",
    "    predictions = [bagging_predict(trees, row) for row in test_set]\n",
    "    return predictions\n",
    "\n",
    "print(random_forest(dataset[:int(len(dataset)*7/10)], dataset[int(len(dataset)*7/10):], 5, 1, 1, 5, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Out-of-bag error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f1_score(y, y_hat):\n",
    "    score = np.mean(y == y_hat)*100\n",
    "    return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oob_classifier_f1_score(train_set, max_depth, min_size, n_features, n_trees, sample_size):\n",
    "    X_train = np.array([x[:-1] for x in train_set])\n",
    "    y_train = np.array([x[-1] for x in train_set])\n",
    "    n_samples = len(X_train)\n",
    "    classes = list(set(y_train))\n",
    "    n_classes = len(classes) # 2 for binary\n",
    "\n",
    "    predictions = np.zeros((n_samples, n_classes))\n",
    "    def encode(class_name):\n",
    "        \"\"\"\n",
    "        Args: name of a class, can be str or int\n",
    "        Return:\n",
    "            one-hot encoding of that class\n",
    "        For example,\n",
    "        >>> list= ['a', 'b', 'c']\n",
    "        >>> ecode('a'), ecode('b'), ecode('c')\n",
    "        >>> ([1,0,0], [0,1,0], [0,0,1])\n",
    "        \"\"\"\n",
    "        return [int(class_name == classes[i]) for i in range(n_classes)]\n",
    "    \n",
    "    for i in range(n_trees):\n",
    "        # Sampling and collect out-of-bag(oob) indices\n",
    "        sample_indices = subsample_idx(len(train_set), sample_size)\n",
    "        oob_indices = np.array([i for i in range(n_samples) if i not in sample_indices])\n",
    "        \n",
    "        # Build a tree\n",
    "        sample = [train_set[i] for i in sample_indices]\n",
    "        tree = build_tree(sample, max_depth, min_size, n_features)\n",
    "        \n",
    "        # Accumulate probability over d classes in OOB dataset\n",
    "        tree_preds = [encode(predict(tree, X_train[oob_index])) for oob_index in oob_indices]\n",
    "        predictions[oob_indices] += tree_preds\n",
    "    \n",
    "    predicted_class_index = np.argmax(predictions, axis = 1)\n",
    "    predicted_class = [classes[i] for i in predicted_class_index] # Decode to list of classes and find score\n",
    "    return f1_score(y_train, predicted_class)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Work with real data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load a CSV file\n",
    "def load_csv(filename):\n",
    "    file = open(filename, \"rt\")\n",
    "    lines = reader(file)\n",
    "    dataset = list(lines)\n",
    "    return dataset\n",
    "\n",
    "# Convert string column to float\n",
    "def str_column_to_float(dataset, column):\n",
    "    for row in dataset:\n",
    "        row[column] = float(row[column])\n",
    "        \n",
    "# Convert string column to integer\n",
    "def str_column_to_int(dataset, column):\n",
    "\tclass_values = [row[column] for row in dataset]\n",
    "\tunique = set(class_values)\n",
    "\tlookup = dict()\n",
    "\tfor i, value in enumerate(unique):\n",
    "\t\tlookup[value] = i\n",
    "\tfor row in dataset:\n",
    "\t\trow[column] = lookup[row[column]]\n",
    "\treturn lookup\n",
    "\n",
    "# Split a dataset into k folds\n",
    "def cross_validation_split(dataset, n_folds):\n",
    "    dataset_split = list()\n",
    "    dataset_copy = list(dataset)\n",
    "    fold_size = int(len(dataset) / n_folds)\n",
    "    for i in range(n_folds):\n",
    "        fold = list()\n",
    "        while len(fold) < fold_size:\n",
    "            index = randrange(len(dataset_copy))\n",
    "            fold.append(dataset_copy.pop(index))\n",
    "        dataset_split.append(fold)\n",
    "    return dataset_split\n",
    "\n",
    "# Calculate accuracy percentage\n",
    "def accuracy_metric(actual, predicted):\n",
    "    correct = 0\n",
    "    for i in range(len(actual)):\n",
    "        if actual[i] == predicted[i]:\n",
    "            correct += 1\n",
    "    return correct / float(len(actual)) * 100.0\n",
    "\n",
    "# Evaluate an algorithm using a cross validation split\n",
    "def evaluate_algorithm(dataset, algorithm, n_folds, *args):\n",
    "    folds = cross_validation_split(dataset, n_folds)\n",
    "    scores = list()\n",
    "    for fold in folds:\n",
    "        train_set = list(folds)\n",
    "        train_set.remove(fold)\n",
    "        train_set = sum(train_set, [])  # concatenate lists of lists to a list\n",
    "        test_set = list()\n",
    "        for row in fold:\n",
    "            row_copy = list(row)\n",
    "            test_set.append(row_copy)\n",
    "            # test_set use to predict => no need to hold [class] data\n",
    "            row_copy[-1] = None\n",
    "        predicted = algorithm(train_set, test_set, *args)\n",
    "        actual = [row[-1] for row in fold]\n",
    "        accuracy = accuracy_metric(actual, predicted)\n",
    "        scores.append(accuracy)\n",
    "    return scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The last row convert from str to int\n",
      "# trees: 1\n",
      "======> Runned in 1174.3699 seconds\n",
      "Mean Accuracy: 96.567%\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_270/3809404564.py:2: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray.\n",
      "  X_train = np.array([x[:-1] for x in train_set])\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "======> Runned in 245.7938 seconds\n",
      "OOB_f1_score: 16.656%\n",
      "# trees: 5\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_270/2286118283.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     26\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'# trees: %s'\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mn_tree\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     27\u001b[0m     \u001b[0mtic\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mperf_counter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 28\u001b[0;31m     \u001b[0mscores\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mevaluate_algorithm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdataset\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrandom_forest\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_folds\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_tree\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msample_size\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     29\u001b[0m     \u001b[0mtoc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mperf_counter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     30\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"======> Runned in {toc - tic:0.4f} seconds\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/1459687123.py\u001b[0m in \u001b[0;36mevaluate_algorithm\u001b[0;34m(dataset, algorithm, n_folds, *args)\u001b[0m\n\u001b[1;32m     57\u001b[0m             \u001b[0;31m# test_set use to predict => no need to hold [class] data\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     58\u001b[0m             \u001b[0mrow_copy\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 59\u001b[0;31m         \u001b[0mpredicted\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0malgorithm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrain_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtest_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     60\u001b[0m         \u001b[0mactual\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mrow\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfold\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     61\u001b[0m         \u001b[0maccuracy\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0maccuracy_metric\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mactual\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpredicted\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/1178571305.py\u001b[0m in \u001b[0;36mrandom_forest\u001b[0;34m(train_set, test_set, max_depth, min_size, n_features, n_trees, sample_size)\u001b[0m\n\u001b[1;32m     19\u001b[0m         \u001b[0msample_indices\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msubsample_idx\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrain_set\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msample_size\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m         \u001b[0msample\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mtrain_set\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msample_indices\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 21\u001b[0;31m         \u001b[0mtree\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbuild_tree\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msample\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     22\u001b[0m         \u001b[0mtrees\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtree\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     23\u001b[0m     \u001b[0mpredictions\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mbagging_predict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrees\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrow\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mrow\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mtest_set\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/3098159825.py\u001b[0m in \u001b[0;36mbuild_tree\u001b[0;34m(train_set, max_depth, min_size, n_features)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mbuild_tree\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrain_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m         \u001b[0mroot\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_split\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdataset\u001b[0m\u001b[0;34m=\u001b[0m \u001b[0mtrain_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m         \u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mroot\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mroot\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/3739003609.py\u001b[0m in \u001b[0;36msplit\u001b[0;34m(node, max_depth, min_size, depth, n_features)\u001b[0m\n\u001b[1;32m     26\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     27\u001b[0m         \u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'right'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_split\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 28\u001b[0;31m         \u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'right'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m/tmp/ipykernel_270/3739003609.py\u001b[0m in \u001b[0;36msplit\u001b[0;34m(node, max_depth, min_size, depth, n_features)\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     21\u001b[0m         \u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'left'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_split\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mleft\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 22\u001b[0;31m         \u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'left'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     23\u001b[0m     \u001b[0;31m# process right child\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     24\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m<=\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/3739003609.py\u001b[0m in \u001b[0;36msplit\u001b[0;34m(node, max_depth, min_size, depth, n_features)\u001b[0m\n\u001b[1;32m     25\u001b[0m         \u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'right'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto_terminal\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     26\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 27\u001b[0;31m         \u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'right'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_split\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     28\u001b[0m         \u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'right'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_size\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn_features\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/1283381405.py\u001b[0m in \u001b[0;36mget_split\u001b[0;34m(dataset, n_features)\u001b[0m\n\u001b[1;32m     30\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mrow\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mdataset\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mattribute\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfeatures\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 32\u001b[0;31m             \u001b[0mgroups\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtest_split\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mattribute\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrow\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mattribute\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdataset\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     33\u001b[0m             \u001b[0mgini\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgini_index\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgroups\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mclasses\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     34\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mgini\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mmin_gini\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/tmp/ipykernel_270/1283381405.py\u001b[0m in \u001b[0;36mtest_split\u001b[0;34m(index, value, dataset)\u001b[0m\n\u001b[1;32m      9\u001b[0m             \u001b[0mleft\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m             \u001b[0mright\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mleft\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mright\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "seed(1)\n",
    "# load and prepare data\n",
    "filename = '/mnt/c/Users/trihu/Doc/data/features.csv'\n",
    "# filename = 'data/BankNote_Authentication.csv'\n",
    "dataset = load_csv(filename)\n",
    "# remove the string attributes\n",
    "dataset.pop(0) \n",
    "\n",
    "# convert string attributes to float\n",
    "for i in range(len(dataset[0]) - 1):\n",
    "    str_column_to_float(dataset, i)\n",
    "\n",
    "# Check if the last row is not INT{0,1}\n",
    "if not isinstance(dataset[0][-1], int):\n",
    "    print(\"The last row convert from str to int\")\n",
    "    str_column_to_int(dataset, len(dataset[0])-1)\n",
    "\n",
    "n_folds = 5\n",
    "max_depth = 5\n",
    "min_size = 10\n",
    "n_trees = [1, 5, 10]\n",
    "n_features = round(sqrt(len(dataset[0]) - 1))\n",
    "sample_size = len(dataset)\n",
    "# (train_set, max_depth, min_size, n_features, n_trees, sample_size):\n",
    "for n_tree in n_trees:\n",
    "    print('# trees: %s' % n_tree)\n",
    "    tic = time.perf_counter()\n",
    "    scores = evaluate_algorithm(dataset, random_forest, n_folds, max_depth, min_size, n_features, n_tree, sample_size)\n",
    "    toc = time.perf_counter()\n",
    "    print(f\"======> Runned in {toc - tic:0.4f} seconds\")\n",
    "    print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))\n",
    "    tic = time.perf_counter()\n",
    "    oob_score = oob_classifier_f1_score(dataset, max_depth, min_size, n_features, n_tree, sample_size)\n",
    "    toc = time.perf_counter()\n",
    "    print(f\"======> Runned in {toc - tic:0.4f} seconds\")\n",
    "    print('OOB_f1_score: %.3f%%' % oob_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Conclusion\n",
    "\n",
    "Version 0.1:\n",
    "* Accuracy:\n",
    "    - 80.000% - 10 trees data/sonar.csv\n",
    "\n",
    "`Note`: Increasing the number of tree upgrade the model's accuracy and also converge to around 80%.\n",
    "\n",
    "Version 0.2: 11/09/2021\n",
    "* Add Out-of-bag(**oob**) error utilizing unsample data for cross-validation (NOT **k cross-validation**), this test is particularly used in `Random Forest` algorithms.\n",
    "* OOB_f1_score:\n",
    "    - 74.038% - 10 trees data/sonar.csv\n",
    "    \n",
    "Version 0.3: 20/09/2021:\n",
    "* Update **oob_f1_score** function, move **f1_score** outside of the function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Refs\n",
    "https://machinelearningmastery.com/implement-random-forest-scratch-python/\n",
    "\n",
    "https://www.ibm.com/cloud/learn/random-forest\n",
    "\n",
    "https://github.com/parrt/random-forest-importances/blob/master/src/rfpimp.py"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "28f96ec01d3331ab2b5d4a1bb32d02e762004829634cea2cd2eeaefdb8bb653c"
  },
  "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}