8 - Random Forest/Random Forest.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "516230d8",
   "metadata": {},
   "source": [
    "# Random Forest\n",
    "## Overview\n",
    "- [1. Bagging](#1)\n",
    "- [2. What is Random Forest?](#2)\n",
    "- [3. Important Features of Random Forest](#3)\n",
    "- [4. Important Hyperparameters](#4)\n",
    "- [5. Pseudo-code](#5)\n",
    "- [6. Implementation](#6)\n",
    "- [7. Advantages and Disadvantages](#7)\n",
    "- [8. References](#8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c57ee67",
   "metadata": {},
   "source": [
    "<a name='1' ></a>\n",
    "## 1. Bagging  \n",
    "**Ensemble learning** is a general meta approach to machine learning that seeks better predictive performance by combining the predictions from multiple models. \n",
    "\n",
    "There are certain rules that we need to follow while creating an ensemble model,\n",
    "\n",
    "- Diversity: All the models that we have created should be diverse and independent of each other. Each model that we would have created can have different features but all of them should be independent.\n",
    "- Acceptability: All the models should be acceptable and should perform good to some extent. We can assure this by evaluating against a random model and check if our model performs better than it.\n",
    "\n",
    "Although there are a seemingly unlimited number of ensembles that you can develop for your predictive modeling problem, there are three methods that dominate the field of ensemble learning including: Bagging , Boosting, and Stacking. In this lecture, we only focus on **Bagging**. \n",
    "\n",
    "### Bagging \n",
    "**Bagging**, also known as **Bootstrap Aggregation** is the ensemble technique used by random forest. Bagging chooses a random sample from the data set. Hence each model is generated from the samples (Bootstrap Samples) provided by the Original Data with replacement known as **row sampling**. This step of row sampling with replacement is called **bootstrap**. Now each model is trained **independently** which generates results. The final output is based on majority voting after combining the results of all models. This step which involves combining all the results and generating output based on majority voting is known as **aggregation**.\n",
    "\n",
    "<div style=\"width:image width px; font-size:80%; text-align:center;\"><img src='images/Bagging.png' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:600px;height:350px;\" />  </div>\n",
    "\n",
    "\n",
    "*Note: When sampling is performed without replacement, it is called pasting. In other words, both bagging and pasting allow training instances to be sampled several times across multiple predictors, but only bagging allows training instances to be sampled several times for the same predictor.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45417da5",
   "metadata": {},
   "source": [
    "<a name='2' ></a>\n",
    "## 2. What is Random Forest?\n",
    "*Random forest is a supervised learning algorithm. The \"forest\" it builds is an ensemble of decision trees, usually trained with the “bagging” method. The general idea of the bagging method is that a combination of learning models increases the overall result.*\n",
    "\n",
    "Two key concepts that give it the name random:\n",
    "- A random sampling of training data set when building trees\n",
    "- Random subsets of features considered when splitting nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6477975",
   "metadata": {},
   "source": [
    "<a name='3' ></a>\n",
    "## 3. Important Features of Random Forest\n",
    "- **Diversity**: Not all attributes/variables/features are considered while making an individual tree, each tree is different.\n",
    "- **Immune to the curse of dimensionality**: Since each tree does not consider all the features, the feature space is reduced.\n",
    "- **Parallelization**: Each tree is created independently out of different data and attributes. This means that we can make full use of the CPU to build random forests.\n",
    "- **Train-Test split**: In a random forest we don’t have to segregate the data for train and test as there will always be 30% of the data which is not seen by the decision tree.\n",
    "- **Stability**: Stability arises because the result is based on majority voting/averaging."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a49cb007",
   "metadata": {},
   "source": [
    "<a name='4' ></a>\n",
    "## 4. Important Hyperparameters\n",
    "Hyperparameters are used in random forests to either enhance the performance and predictive power of models or to make the model faster.\n",
    "\n",
    "*Following hyperparameters increases the predictive power:*\n",
    "- **n_estimators**: number of trees the algorithm builds before averaging the predictions.\n",
    "- **criterion**: The function to measure the quality of a split. Supported criteria are “gini” for the Gini impurity and “log_loss” and “entropy” both for the Shannon information gain.\n",
    "- **max_features**: maximum number of features random forest considers splitting a node.\n",
    "- **min_samples_leaf**: determines the minimum number of leaves required to split an internal node.\n",
    "- **min_impurity_decrease**: A node will be split if this split induces a decrease of the impurity greater than or equal to this value.\n",
    "\n",
    "*Following hyperparameters increases the speed:*\n",
    "- **n_jobs**: it tells the engine how many processors it is allowed to use. If the value is 1, it can use only one processor but if the value is -1 there is no limit.\n",
    "- **random_state**: controls randomness of the sample. The model will always produce the same results if it has a definite value of random state and if it has been given the same hyperparameters and the same training data.\n",
    "- **oob_score**: OOB means out of the bag. It is a random forest cross-validation method. In this one-third of the sample is not used to train the data instead used to evaluate its performance. These samples are called out of bag samples."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b12f285",
   "metadata": {},
   "source": [
    "<a name='5' ></a>\n",
    "## 5. Pseudo-code\n",
    "Given a training set $X = x_1, ..., x_n$ with responses $Y = y_1, ..., y_n$, bagging repeatedly (B times) selects a random sample with replacement of the training set and fits trees to these samples:\n",
    "\n",
    "For b = 1, ..., B:\n",
    "1. Sample, with replacement, $n$ training examples from $X, Y$; call these $X_b, Y_b$.\n",
    "2. Train a classification or regression tree $f_b$ on $X_b, Y_b$.\n",
    "\n",
    "After training, predictions for unseen samples $x'$ can be made by averaging the predictions from all the individual regression trees on $x'$:\n",
    "- For regression problem: $\\hat{f} = \\frac{1}{B} \\sum_{b=1}^{B} f_b(x')$\n",
    "- For classification problem: $\\hat{f} = mode(\\hat{Y})$, where $\\hat{Y} = \\{ f_b(x') \\}_{b=1}^{B}$, f_b(x') is categorical (discrete) variable."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b19a5be0",
   "metadata": {},
   "source": [
    "<a name='6' ></a>\n",
    "## 6. Implementation\n",
    "The below is Random Forest's code for classification problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1e4a2fc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from scipy import stats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d062f6aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# IMPLEMENTATION\n",
    "class RandomForest():\n",
    "    \"\"\"Implement Random Forest classifier from scratch using Decision Tree.\"\"\"\n",
    "    \n",
    "    def __init__(\n",
    "        self,\n",
    "        n_estimators=100,\n",
    "        criterion='gini', \n",
    "        max_depth=None,\n",
    "        min_samples_leaf=1,\n",
    "        max_features='sqrt', \n",
    "        min_impurity_decrease=0.0,\n",
    "        random_state=0\n",
    "    ):\n",
    "        \"\"\"\n",
    "        Some important parameters in Random Forest.\n",
    "        \n",
    "        Args:\n",
    "            n_estimators (int): The number of trees in the forest, default 100.\n",
    "            criterion (str): The function to measure the quality of a split, default gini.\n",
    "            max_depth (int): The maximum depth of the tree, default None.\n",
    "            min_samples_leaf (int): The minimum number of samples required to be at a leaf node.\n",
    "            max_features (int): The number of features to consider when looking for the best split,default sqrt.\n",
    "            min_impurity_decrease (int): A node will be split if this split induces a decrease of \n",
    "            the impurity greater than or equal to this value.\n",
    "            random_state (int): Controls randomness of the sample, default 0.\n",
    "\n",
    "        \"\"\"\n",
    "        self.n_estimators = n_estimators\n",
    "        self.criterion =  criterion\n",
    "        self.max_depth = max_depth\n",
    "        self.min_samples_leaf = min_samples_leaf\n",
    "        self.max_features = max_features\n",
    "        self.random_state = random_state\n",
    "        \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"Training model.\"\"\"\n",
    "        # Specify the number of features in each tree\n",
    "        self.n_samples, self.n_features = X.shape\n",
    "        if self.max_features == 'sqrt':\n",
    "            self.max_feature = int(np.sqrt(self.n_features))\n",
    "            \n",
    "        # Loop through all trees in the forest\n",
    "        self.tree_lst = []\n",
    "        for i in range(self.n_estimators):\n",
    "            X_train, _, y_train, _ = train_test_split(\n",
    "                X, \n",
    "                y, \n",
    "                test_size=0.3, \n",
    "                random_state=self.random_state + i\n",
    "            )\n",
    "            tree = DecisionTreeClassifier(\n",
    "                criterion = self.criterion,\n",
    "                max_depth = self.max_depth,\n",
    "                min_samples_leaf = self.min_samples_leaf,\n",
    "                max_features = self.max_features,\n",
    "                random_state = self.random_state\n",
    "            )\n",
    "            tree.fit(X_train, y_train)\n",
    "            self.tree_lst.append(tree)\n",
    "    \n",
    "    def predict(self, X_test):\n",
    "        \"\"\"Predict labels for X_test.\"\"\"\n",
    "        predict_arr = []\n",
    "        for tree in self.tree_lst:\n",
    "            predict = tree.predict(X_test)\n",
    "            predict_arr.append(predict)\n",
    "            \n",
    "        predicted_labels = np.squeeze(stats.mode(predict_arr, axis=0)[0])\n",
    "        return predicted_labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "61c940d5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accurary on train set: 1.0\n",
      "Accurary on test set: 0.9111111111111111\n"
     ]
    }
   ],
   "source": [
    "from sklearn import datasets\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "# Make dataset\n",
    "X, y = datasets.make_blobs(n_samples=300, n_features=10, centers=3, cluster_std=5, random_state=42)\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)\n",
    "\n",
    "# Initialize and fit model\n",
    "clf = RandomForest(\n",
    "    n_estimators=100,\n",
    "    criterion='gini', \n",
    "    max_depth=10,\n",
    "    min_samples_leaf=1,\n",
    "    max_features='sqrt', \n",
    "    min_impurity_decrease=0.0,\n",
    "    random_state=0\n",
    ")\n",
    "clf.fit(X_train, y_train)\n",
    "\n",
    "# Predict and evaluate\n",
    "y_pred = clf.predict(X_test)\n",
    "print(f'Accurary on train set: {accuracy_score(y_train, clf.predict(X_train))}')\n",
    "print(f'Accurary on test set: {accuracy_score(y_test, y_pred)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bff66e2b",
   "metadata": {},
   "source": [
    "<a name='7' ></a>\n",
    "## 7. Advantages and Disadvantages\n",
    "**Advantages of Random Forest algorithm:**\n",
    "- Can handle large amounts of data and a large number of features.\n",
    "- Can be used for both classification and regression tasks.\n",
    "- The algorithm is easy to implement and interpret.\n",
    "- Random Forest algorithm is less prone to overfitting than other decision tree algorithms. It creates as many trees on the subset of the data and combines the output of all the trees. In this way it reduces overfitting problem in decision trees and also reduces the variance and therefore improves the accuracy. All the trees in a random forest are diverse and independent of each other. \n",
    "- It is very stable because the majority vote is taken combining the results of all those trees. It is not prone to over fitting\n",
    "- It is immune to the curse of dimensionality- since we take only a subset of rows & columns the feature space is reduced considerably\n",
    "- It is parallelizable since all the trees are independent of each other, we can run each model separately and so it is parallelizable\n",
    "\n",
    "**Disadvantages of Random Forest algorithm:**\n",
    "- The algorithm can be slow for real-time predictions because it has multiple decision trees.\n",
    "- The algorithm may not work well with highly skewed data.\n",
    "- The algorithm requires more computational resources than other decision tree algorithms.\n",
    "- It can be less accurate when the data set is small.\n",
    "\n",
    "**More:** Run time depends upon 3 things- the number of trees (t), the depth of each tree (d) and the number of rows in each tree (m). Run time for training is $O(t*mlogd)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9126310",
   "metadata": {},
   "source": [
    "<a name='8' ></a>\n",
    "## 8. References\n",
    "- [https://en.wikipedia.org/wiki/Random_forest](https://en.wikipedia.org/wiki/Random_forest)\n",
    "- [https://builtin.com/data-science/random-forest-algorithm](https://builtin.com/data-science/random-forest-algorithm)\n",
    "- [https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html](https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html)\n",
    "- [https://machinelearningmastery.com/tour-of-ensemble-learning-algorithms/](https://machinelearningmastery.com/tour-of-ensemble-learning-algorithms/)\n",
    "- [https://www.analyticsvidhya.com/blog/2021/06/understanding-random-forest/](https://www.analyticsvidhya.com/blog/2021/06/understanding-random-forest/)\n",
    "- [https://madhuramiah.medium.com/introduction-to-ensembling-techniques-bagging-1458cfdb150c](https://madhuramiah.medium.com/introduction-to-ensembling-techniques-bagging-1458cfdb150c)\n",
    "- [https://www.kdnuggets.com/2020/01/random-forest-powerful-ensemble-learning-algorithm.html](https://www.kdnuggets.com/2020/01/random-forest-powerful-ensemble-learning-algorithm.html)"
   ]
  }
 ],
 "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.8.10"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}