013_MML_Decision_Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "creative-aruba",
   "metadata": {},
   "source": [
    "# 5. Decision Trees\n",
    "***\n",
    "\n",
    "- Decision trees are a non-parametric model used for both regression and classification tasks\n",
    "- This notebook demonstrates how to use decision trees for classification\n",
    "- Decision trees are constructed from only two elements - nodes and branches\n",
    "- Decision trees are based on recursion\n",
    "    - A function that calls itself until some exit condition is met\n",
    "    - The algorithm is built by recursively evaluating different features and using the best split feature and criteria at each node\n",
    "    - You'll learn how the best split feature and criteria are calculated in the math section\n",
    "- There are multiple types of node a decision tree could have, and all are presented in the following figure:\n",
    "\n",
    "<img src=\"dtree/dtree.jpg\" style=\"display:block; margin-left:auto; margin-right:auto;\">\n",
    "\n",
    "- **Root node** - node at the top of the tree, contains a feature that best splits the data (a single feature that alone classifies the target variable most accurately)\n",
    "- **Decision nodes** - nodes where the variables are evaluated. These nodes have arrows pointing to them and away from them\n",
    "- **Leaf nodes** - final node at which the prediction is made\n",
    "\n",
    "\n",
    "### How to determine the root node\n",
    "- Check how every input feature classifies the target variable independently\n",
    "- If neither is 100% correct, we can consider them as *impure*\n",
    "- The **Entropy** metric can be used to calculate impuritz\n",
    "    - Formula discussed later\n",
    "    - Values range from 0 (best) to 1 (worst)\n",
    "- The variable with the lowest entropy (impurity) is used as a root node\n",
    "\n",
    "\n",
    "### Training process\n",
    "- Determine the root node (discussed earlier)\n",
    "- Calculate the **Information gain** for a single split\n",
    "    - Formula discussed later\n",
    "    - The higher the gain the better the split\n",
    "- Do a greedy search\n",
    "    - Go over all input feature and their unique values (thresholds)\n",
    "    - Calculate information gain for every feature/threshold combination\n",
    "    - Save the best split feature and best split threshold for every node\n",
    "    - Build the tree recursively\n",
    "    - Some stopping criteria should be applied when doing so\n",
    "        - Think of it as an exit condition of a recursive function\n",
    "        - This could be maximum depth, minimum samples at node...\n",
    "    - If at the leaf node, return the prediction (most common value)\n",
    "        - You'll know you're at a leaf node if a stopping criteria has been met or if the split is pure\n",
    "        \n",
    "        \n",
    "### Prediction process\n",
    "- Recursively traverse the tree\n",
    "- At each node check if the direction of the traversal (left or right), based on the input data\n",
    "- When the leaf node is reached, the most common value is returned\n",
    "\n",
    "\n",
    "## Math behind\n",
    "- Essentially, you only need to implement two formulas\n",
    "    - Entropy\n",
    "    - Information gain\n",
    "    \n",
    "- **Entropy**\n",
    "    - Measures the purity of the split\n",
    "    - Calculated at the node level\n",
    "    - Ranges between 0 (pure) and 1 (impure)\n",
    "    \n",
    "$$ \\large E(S) = \\sum_{i=1}^{c} - p_i log_2 p_i $$\n",
    "<br>\n",
    "<br>\n",
    "\n",
    "- Example:\n",
    "\n",
    "$$ \\large s = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1] $$\n",
    "<br>\n",
    "<br>\n",
    "$$ \\large n_0 = 7 $$\n",
    "<br>\n",
    "$$ \\large n_1 = 3 $$\n",
    "<br>\n",
    "<br>\n",
    "$$ \\large E(S) = - \\frac{7}{10} log_2(\\frac{7}{10}) - \\frac{3}{10} log_2(\\frac{3}{10}) $$\n",
    "<br>\n",
    "<br>\n",
    "$$ \\large E(S) = - 0.7 log_2(0.7) - 0.3 log_2(0.3) $$\n",
    "<br>\n",
    "<br>\n",
    "$$ \\large E(S) = - 0.7 \\times -0.51457 - 0.3 \\times -1.73697 $$\n",
    "<br>\n",
    "<br>\n",
    "$$ \\large E(S) = 0.88129 $$\n",
    "\n",
    "- Example in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "premium-toner",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cognitive-recipient",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(s):\n",
    "    counts = np.bincount(s)\n",
    "    percentages = counts / len(s)\n",
    "    \n",
    "    entropy = 0\n",
    "    for pct in percentages:\n",
    "        if pct > 0:\n",
    "            entropy += pct * np.log2(pct)\n",
    "    return -entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "significant-march",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entropy: 0.88129\n"
     ]
    }
   ],
   "source": [
    "s = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1]\n",
    "print(f'Entropy: {np.round(entropy(s), 5)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "musical-expert",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "- **Information gain**:\n",
    "    - Simply an average of all entropy based on a specific split\n",
    "    - The higher the information gain, the better the decision split is\n",
    "    \n",
    "$$ \\large Gain(S, A) = E(S) - \\sum_{v \\in Values(A)} \\frac{|S_v|}{|S|} E(S_v) $$\n",
    "\n",
    "- Example:\n",
    "\n",
    "<img src=\"dtree/info_gain.png\" style=\"display:block; margin-left:auto; margin-right:auto;\">\n",
    "\n",
    "$$ \\large Gain(S, A) = E(S) - \\sum_{v \\in Values(A)} \\frac{|S_v|}{|S|} E(S_v) $$\n",
    "<br><br>\n",
    "$$ \\large Gain(S, A) = 0.97095 - \\frac{12}{20} \\times 0.65002 - \\frac{8}{20} \\times 1 $$\n",
    "<br><br>\n",
    "$$ \\large Gain(S, A) = 0.97095 - \\frac{12}{20} \\times 0.65002 - \\frac{8}{20} \\times 1 $$\n",
    "<br><br>\n",
    "$$ \\large Gain(S, A) = 0.18094 $$\n",
    "\n",
    "- Example in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "available-funds",
   "metadata": {},
   "outputs": [],
   "source": [
    "def information_gain(parent, left_child, right_child):\n",
    "    num_left = len(left_child) / len(parent)\n",
    "    num_right = len(right_child) / len(parent)\n",
    "    \n",
    "    gain = entropy(parent) - (num_left * entropy(left_child) + num_right * entropy(right_child))\n",
    "    return gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "international-theorem",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Information gain: 0.18094\n"
     ]
    }
   ],
   "source": [
    "parent = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]\n",
    "left_child = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]\n",
    "right_child = [0, 0, 0, 0, 1, 1, 1, 1]\n",
    "\n",
    "print(f'Information gain: {np.round(information_gain(parent, left_child, right_child), 5)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "numeric-heavy",
   "metadata": {},
   "source": [
    "<br><br>\n",
    "\n",
    "## Recursion Crash Course\n",
    "- A lot of decision trees implementation boils down to recursion\n",
    "- Put simply, recursive function is a function that calls itself\n",
    "- Some \"exit condition\" is required if a function will call itself multiple times\n",
    "    - It's common to write it at the top of the function\n",
    "- Let's take a look at the simplest example - a recursive function that returns a factorial of an integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "otherwise-trader",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Factorial of 5 is 120\n"
     ]
    }
   ],
   "source": [
    "def factorial(x):\n",
    "    # Exit condition\n",
    "    if x == 1:\n",
    "        return 1\n",
    "    return x * factorial(x - 1)\n",
    "\n",
    "print(f'Factorial of 5 is {factorial(5)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "technical-european",
   "metadata": {},
   "source": [
    "- Recursion is needed in decision tree classifiers to build additional nodes of a tree until some condition (exit) is met"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "consecutive-appliance",
   "metadata": {},
   "source": [
    "<br><br>\n",
    "\n",
    "# Implementation\n",
    "***\n",
    "- We'll need two classes\n",
    "    - `Node` - implements a single node of a decision tree\n",
    "    - `DecisionTree` - implements the algorithm\n",
    "- The `Node` class is here to store the data about the feature, threshold, data going left and right, information gain, and the leaf node value\n",
    "    - All are initially set to `None`\n",
    "    - The leaf node value is available only for leaf nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "sealed-basketball",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    '''\n",
    "    Helper class which implements a single tree node.\n",
    "    '''\n",
    "    def __init__(self, feature=None, threshold=None, data_left=None, data_right=None, gain=None, value=None):\n",
    "        self.feature = feature\n",
    "        self.threshold = threshold\n",
    "        self.data_left = data_left\n",
    "        self.data_right = data_right\n",
    "        self.gain = gain\n",
    "        self.value = value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "embedded-thumbnail",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "- The `DecisionTree` class contains a bunch of methods\n",
    "- The constructor holds values for `min_samples_split` and `max_depth`. These are hyperparameters. The first one is used to specify a minimum number of samples required to split a node, and the second one specifies a maximum depth of a tree. Both are used in recursive functions as exit conditions\n",
    "- The `_entropy(s)` function calculates the impurity of an input vector `s`\n",
    "- The `_information_gain(parent, left_child, right_child)` calculates the information gain value of a split between a parent and two children\n",
    "- The `_best_split(X, y)` function calculates the best splitting parameters for input features `X` and a target variable `y`\n",
    "    - It does so by iterating over every column in `X` and every thresold value in every column to find the optimal split using information gain\n",
    "- The `_build(X, y, depth)` function recursively builds a decision tree until stopping criterias are met (hyperparameters in the constructor)\n",
    "- The `fit(X, y)` function calls the `_build()` function and stores the built tree to the constructor\n",
    "- The `_predict(x)` function traverses the tree to classify a single instance\n",
    "- The `predict(X)` function applies the `_predict()` function to every instance in matrix `X`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ignored-approach",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTree:\n",
    "    '''\n",
    "    Class which implements a decision tree classifier algorithm.\n",
    "    '''\n",
    "    def __init__(self, min_samples_split=2, max_depth=5):\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.max_depth = max_depth\n",
    "        self.root = None\n",
    "        \n",
    "    @staticmethod\n",
    "    def _entropy(s):\n",
    "        '''\n",
    "        Helper function, calculates entropy from an array of integer values.\n",
    "        \n",
    "        :param s: list\n",
    "        :return: float, entropy value\n",
    "        '''\n",
    "        # Convert to integers to avoid runtime errors\n",
    "        counts = np.bincount(np.array(s, dtype=np.int64))\n",
    "        # Probabilities of each class label\n",
    "        percentages = counts / len(s)\n",
    "\n",
    "        # Caclulate entropy\n",
    "        entropy = 0\n",
    "        for pct in percentages:\n",
    "            if pct > 0:\n",
    "                entropy += pct * np.log2(pct)\n",
    "        return -entropy\n",
    "    \n",
    "    def _information_gain(self, parent, left_child, right_child):\n",
    "        '''\n",
    "        Helper function, calculates information gain from a parent and two child nodes.\n",
    "        \n",
    "        :param parent: list, the parent node\n",
    "        :param left_child: list, left child of a parent\n",
    "        :param right_child: list, right child of a parent\n",
    "        :return: float, information gain\n",
    "        '''\n",
    "        num_left = len(left_child) / len(parent)\n",
    "        num_right = len(right_child) / len(parent)\n",
    "        \n",
    "        # One-liner which implements the previously discussed formula\n",
    "        return self._entropy(parent) - (num_left * self._entropy(left_child) + num_right * self._entropy(right_child))\n",
    "    \n",
    "    def _best_split(self, X, y):\n",
    "        '''\n",
    "        Helper function, calculates the best split for given features and target\n",
    "        \n",
    "        :param X: np.array, features\n",
    "        :param y: np.array or list, target\n",
    "        :return: dict\n",
    "        '''\n",
    "        best_split = {}\n",
    "        best_info_gain = -1\n",
    "        n_rows, n_cols = X.shape\n",
    "        \n",
    "        # For every dataset feature\n",
    "        for f_idx in range(n_cols):\n",
    "            X_curr = X[:, f_idx]\n",
    "            # For every unique value of that feature\n",
    "            for threshold in np.unique(X_curr):\n",
    "                # Construct a dataset and split it to the left and right parts\n",
    "                # Left part includes records lower or equal to the threshold\n",
    "                # Right part includes records higher than the threshold\n",
    "                df = np.concatenate((X, y.reshape(1, -1).T), axis=1)\n",
    "                df_left = np.array([row for row in df if row[f_idx] <= threshold])\n",
    "                df_right = np.array([row for row in df if row[f_idx] > threshold])\n",
    "\n",
    "                # Do the calculation only if there's data in both subsets\n",
    "                if len(df_left) > 0 and len(df_right) > 0:\n",
    "                    # Obtain the value of the target variable for subsets\n",
    "                    y = df[:, -1]\n",
    "                    y_left = df_left[:, -1]\n",
    "                    y_right = df_right[:, -1]\n",
    "\n",
    "                    # Caclulate the information gain and save the split parameters\n",
    "                    # if the current split if better then the previous best\n",
    "                    gain = self._information_gain(y, y_left, y_right)\n",
    "                    if gain > best_info_gain:\n",
    "                        best_split = {\n",
    "                            'feature_index': f_idx,\n",
    "                            'threshold': threshold,\n",
    "                            'df_left': df_left,\n",
    "                            'df_right': df_right,\n",
    "                            'gain': gain\n",
    "                        }\n",
    "                        best_info_gain = gain\n",
    "        return best_split\n",
    "    \n",
    "    def _build(self, X, y, depth=0):\n",
    "        '''\n",
    "        Helper recursive function, used to build a decision tree from the input data.\n",
    "        \n",
    "        :param X: np.array, features\n",
    "        :param y: np.array or list, target\n",
    "        :param depth: current depth of a tree, used as a stopping criteria\n",
    "        :return: Node\n",
    "        '''\n",
    "        n_rows, n_cols = X.shape\n",
    "        \n",
    "        # Check to see if a node should be leaf node\n",
    "        if n_rows >= self.min_samples_split and depth <= self.max_depth:\n",
    "            # Get the best split\n",
    "            best = self._best_split(X, y)\n",
    "            # If the split isn't pure\n",
    "            if best['gain'] > 0:\n",
    "                # Build a tree on the left\n",
    "                left = self._build(\n",
    "                    X=best['df_left'][:, :-1], \n",
    "                    y=best['df_left'][:, -1], \n",
    "                    depth=depth + 1\n",
    "                )\n",
    "                right = self._build(\n",
    "                    X=best['df_right'][:, :-1], \n",
    "                    y=best['df_right'][:, -1], \n",
    "                    depth=depth + 1\n",
    "                )\n",
    "                return Node(\n",
    "                    feature=best['feature_index'], \n",
    "                    threshold=best['threshold'], \n",
    "                    data_left=left, \n",
    "                    data_right=right, \n",
    "                    gain=best['gain']\n",
    "                )\n",
    "        # Leaf node - value is the most common target value \n",
    "        return Node(\n",
    "            value=Counter(y).most_common(1)[0][0]\n",
    "        )\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        '''\n",
    "        Function used to train a decision tree classifier model.\n",
    "        \n",
    "        :param X: np.array, features\n",
    "        :param y: np.array or list, target\n",
    "        :return: None\n",
    "        '''\n",
    "        # Call a recursive function to build the tree\n",
    "        self.root = self._build(X, y)\n",
    "        \n",
    "    def _predict(self, x, tree):\n",
    "        '''\n",
    "        Helper recursive function, used to predict a single instance (tree traversal).\n",
    "        \n",
    "        :param x: single observation\n",
    "        :param tree: built tree\n",
    "        :return: float, predicted class\n",
    "        '''\n",
    "        # Leaf node\n",
    "        if tree.value != None:\n",
    "            return tree.value\n",
    "        feature_value = x[tree.feature]\n",
    "        \n",
    "        # Go to the left\n",
    "        if feature_value <= tree.threshold:\n",
    "            return self._predict(x=x, tree=tree.data_left)\n",
    "        \n",
    "        # Go to the right\n",
    "        if feature_value > tree.threshold:\n",
    "            return self._predict(x=x, tree=tree.data_right)\n",
    "        \n",
    "    def predict(self, X):\n",
    "        '''\n",
    "        Function used to classify new instances.\n",
    "        \n",
    "        :param X: np.array, features\n",
    "        :return: np.array, predicted classes\n",
    "        '''\n",
    "        # Call the _predict() function for every observation\n",
    "        return [self._predict(x, self.root) for x in X]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "metric-genealogy",
   "metadata": {},
   "source": [
    "<br><br>\n",
    "\n",
    "## Testing\n",
    "- We'll use the Iris dataset from Scikit-Learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "polyphonic-details",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "\n",
    "iris = load_iris()\n",
    "\n",
    "X = iris['data']\n",
    "y = iris['target']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "appreciated-accident",
   "metadata": {},
   "source": [
    "- The below code applies train/test split to the dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "upset-atlas",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "linear-alpha",
   "metadata": {},
   "source": [
    "- You can now initialize and train the model, and make the predictions afterwards:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "stable-deputy",
   "metadata": {},
   "outputs": [],
   "source": [
    "model = DecisionTree()\n",
    "model.fit(X_train, y_train)\n",
    "preds = model.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "southeast-party",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0, 2, 1, 1, 0, 1, 2, 1, 1, 2, 0, 0, 0, 0, 1, 2, 1, 1, 2, 0, 2,\n",
       "       0, 2, 2, 2, 2, 2, 0, 0])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.array(preds, dtype=np.int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "armed-evans",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0, 2, 1, 1, 0, 1, 2, 1, 1, 2, 0, 0, 0, 0, 1, 2, 1, 1, 2, 0, 2,\n",
       "       0, 2, 2, 2, 2, 2, 0, 0])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_test"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "former-image",
   "metadata": {},
   "source": [
    "- As you can see, the arrays are identical\n",
    "- Let's calculate the accuracy to confirm this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "sharp-offer",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "accuracy_score(y_test, preds)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "israeli-portrait",
   "metadata": {},
   "source": [
    "- As expected, the perfect score was obtained on the test set"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "formal-cigarette",
   "metadata": {},
   "source": [
    "<br><br>\n",
    "\n",
    "## Comparison with Scikit-Learn\n",
    "- We already know our model works good, but let's compare it to the `DecisionTreeClassifier` from Scikit-Learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "exterior-found",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "sk_model = DecisionTreeClassifier()\n",
    "sk_model.fit(X_train, y_train)\n",
    "sk_preds = sk_model.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "happy-shuttle",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "accuracy_score(y_test, sk_preds)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "formal-evening",
   "metadata": {},
   "source": [
    "- Both perform the same, at least accuracy-wise"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}