9. CART - Decision Tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "da37fcfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cd80269c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Outlook</th>\n",
       "      <th>Temperature</th>\n",
       "      <th>Humidity</th>\n",
       "      <th>Wind</th>\n",
       "      <th>Play</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Hot</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Outlook Temperature Humidity    Wind Play\n",
       "0      Sunny         Hot     High    Weak   No\n",
       "1      Sunny         Hot     High  Strong   No\n",
       "2   Overcast         Hot     High    Weak  Yes\n",
       "3       Rain        Mild     High    Weak  Yes\n",
       "4       Rain        Cool   Normal    Weak  Yes\n",
       "5       Rain        Cool   Normal  Strong   No\n",
       "6   Overcast        Cool   Normal  Strong  Yes\n",
       "7      Sunny        Mild     High    Weak   No\n",
       "8      Sunny        Cool   Normal    Weak  Yes\n",
       "9       Rain        Mild   Normal    Weak  Yes\n",
       "10     Sunny        Mild   Normal  Strong  Yes\n",
       "11  Overcast        Mild     High  Strong  Yes\n",
       "12  Overcast         Hot   Normal    Weak  Yes\n",
       "13      Rain        Mild     High  Strong   No"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = pd.read_csv(\"DecisionTree.csv\")\n",
    "data\n",
    "# data.columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2a1f6883",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['No', 'No', 'Yes', 'Yes', 'Yes', 'No', 'Yes', 'No', 'Yes', 'Yes',\n",
       "       'Yes', 'Yes', 'Yes', 'No'], dtype=object)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = data[['Outlook', 'Temperature', 'Humidity', 'Wind' ]]\n",
    "Y = data['Play'].values\n",
    "Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c00bea43",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "bbcad786",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node: \n",
    "\n",
    "    def __init__(\n",
    "        self, \n",
    "        Y: list,\n",
    "        X: pd.DataFrame,\n",
    "        min_samples_split=None,\n",
    "        max_depth=None,\n",
    "        depth=None,\n",
    "        node_type=None,\n",
    "        rule=None\n",
    "    ):\n",
    "        self.Y = Y \n",
    "        self.X = X\n",
    "\n",
    "\n",
    "        self.min_samples_split = min_samples_split if min_samples_split else 20\n",
    "        self.max_depth = max_depth if max_depth else 5\n",
    "\n",
    "        self.depth = depth if depth else 0\n",
    "\n",
    "        self.features = list(self.X.columns)\n",
    "\n",
    "        self.node_type = node_type if node_type else 'root'\n",
    "\n",
    "        self.rule = rule if rule else \"\"\n",
    "\n",
    "        self.counts = Counter(Y)\n",
    "\n",
    "        self.gini_impurity = self.get_GINI()\n",
    "\n",
    "        counts_sorted = list(sorted(self.counts.items(), key=lambda item: item[1]))\n",
    "\n",
    "        yhat = None\n",
    "        if len(counts_sorted) > 0:\n",
    "            yhat = counts_sorted[-1][0]\n",
    "\n",
    "        self.yhat = yhat \n",
    " \n",
    "        self.n = len(Y)\n",
    "\n",
    "        self.left = None \n",
    "        self.right = None \n",
    "\n",
    "        self.best_feature = None \n",
    "        self.best_value = None \n",
    "\n",
    "    @staticmethod\n",
    "    def GINI_impurity(y1_count: int, y2_count: int) -> float:\n",
    "\n",
    "        if y1_count is None:\n",
    "            y1_count = 0\n",
    "\n",
    "        if y2_count is None:\n",
    "            y2_count = 0\n",
    "\n",
    "        n = y1_count + y2_count\n",
    "\n",
    "        if n == 0:\n",
    "            return 0.0\n",
    "\n",
    "        p1 = y1_count / n\n",
    "        p2 = y2_count / n\n",
    "        \n",
    "        gini = 1 - (p1 ** 2 + p2 ** 2)\n",
    "\n",
    "        return gini\n",
    "\n",
    "    @staticmethod\n",
    "    def ma(x: np.array, window: int) -> np.array:\n",
    "        return np.convolve(x, np.ones(window), 'valid') / window\n",
    "\n",
    "    def get_GINI(self):\n",
    "        y1_count, y2_count = self.counts.get(0, 0), self.counts.get(1, 0)\n",
    "\n",
    "        return self.GINI_impurity(y1_count, y2_count)\n",
    "\n",
    "    def best_split(self) -> tuple:\n",
    "        df = self.X.copy()\n",
    "        df['Y'] = self.Y\n",
    "\n",
    "        GINI_base = self.get_GINI()\n",
    "\n",
    "        max_gain = 0\n",
    "\n",
    "        best_feature = None\n",
    "        best_value = None\n",
    "\n",
    "        for feature in self.features:\n",
    "            Xdf = df.dropna().sort_values(feature)\n",
    "\n",
    "            xmeans = self.ma(Xdf[feature].unique(), 2)\n",
    "\n",
    "            for value in xmeans:\n",
    "                left_counts = Counter(Xdf[Xdf[feature]<value]['Y'])\n",
    "                right_counts = Counter(Xdf[Xdf[feature]>=value]['Y'])\n",
    "\n",
    "                y0_left, y1_left, y0_right, y1_right = left_counts.get(0, 0), left_counts.get(1, 0), right_counts.get(0, 0), right_counts.get(1, 0)\n",
    "\n",
    "                gini_left = self.GINI_impurity(y0_left, y1_left)\n",
    "                gini_right = self.GINI_impurity(y0_right, y1_right)\n",
    "\n",
    "                n_left = y0_left + y1_left\n",
    "                n_right = y0_right + y1_right\n",
    "\n",
    "                w_left = n_left / (n_left + n_right)\n",
    "                w_right = n_right / (n_left + n_right)\n",
    "\n",
    "                wGINI = w_left * gini_left + w_right * gini_right\n",
    "\n",
    "\n",
    "                GINIgain = GINI_base - wGINI\n",
    "\n",
    "                if GINIgain > max_gain:\n",
    "                    best_feature = feature\n",
    "                    best_value = value \n",
    "\n",
    "                    max_gain = GINIgain\n",
    "\n",
    "        return (best_feature, best_value)\n",
    "\n",
    "    def grow_tree(self):\n",
    "        df = self.X.copy()\n",
    "        df['Y'] = self.Y\n",
    "\n",
    "        if (self.depth < self.max_depth) and (self.n >= self.min_samples_split):\n",
    "\n",
    "            best_feature, best_value = self.best_split()\n",
    "\n",
    "            if best_feature is not None:\n",
    "                self.best_feature = best_feature\n",
    "                self.best_value = best_value\n",
    "\n",
    "                left_df, right_df = df[df[best_feature]<=best_value].copy(), df[df[best_feature]>best_value].copy()\n",
    "\n",
    "                left = Node(\n",
    "                    left_df['Y'].values.tolist(), \n",
    "                    left_df[self.features], \n",
    "                    depth=self.depth + 1, \n",
    "                    max_depth=self.max_depth, \n",
    "                    min_samples_split=self.min_samples_split, \n",
    "                    node_type='left_node',\n",
    "                    rule=f\"{best_feature} <= {round(best_value, 3)}\"\n",
    "                    )\n",
    "\n",
    "                self.left = left \n",
    "                self.left.grow_tree()\n",
    "\n",
    "                right = Node(\n",
    "                    right_df['Y'].values.tolist(), \n",
    "                    right_df[self.features], \n",
    "                    depth=self.depth + 1, \n",
    "                    max_depth=self.max_depth, \n",
    "                    min_samples_split=self.min_samples_split,\n",
    "                    node_type='right_node',\n",
    "                    rule=f\"{best_feature} > {round(best_value, 3)}\"\n",
    "                    )\n",
    "\n",
    "                self.right = right\n",
    "                self.right.grow_tree()\n",
    "\n",
    "    def print_info(self, width=4):\n",
    "        # Defining the number of spaces \n",
    "        const = int(self.depth * width ** 1.5)\n",
    "        spaces = \"-\" * const\n",
    "        \n",
    "        if self.node_type == 'root':\n",
    "            print(\"Root\")\n",
    "        else:\n",
    "            print(f\"|{spaces} Split rule: {self.rule}\")\n",
    "        print(f\"{' ' * const}   | GINI impurity of the node: {round(self.gini_impurity, 2)}\")\n",
    "        print(f\"{' ' * const}   | Class distribution in the node: {dict(self.counts)}\")\n",
    "        print(f\"{' ' * const}   | Predicted class: {self.yhat}\")   \n",
    "\n",
    "    def print_tree(self):\n",
    "        self.print_info() \n",
    "        \n",
    "        if self.left is not None: \n",
    "            self.left.print_tree()\n",
    "        \n",
    "        if self.right is not None:\n",
    "            self.right.print_tree()\n",
    "\n",
    "    def predict(self, X:pd.DataFrame):\n",
    "        predictions = []\n",
    "\n",
    "        for _, x in X.iterrows():\n",
    "            values = {}\n",
    "            for feature in self.features:\n",
    "                values.update({feature: x[feature]})\n",
    "        \n",
    "            predictions.append(self.predict_obs(values))\n",
    "        \n",
    "        return predictions\n",
    "\n",
    "    def predict_obs(self, values: dict) -> int:\n",
    "        cur_node = self\n",
    "        while cur_node.depth < cur_node.max_depth:\n",
    "            \n",
    "            best_feature = cur_node.best_feature\n",
    "            best_value = cur_node.best_value\n",
    "\n",
    "            if cur_node.n < cur_node.min_samples_split:\n",
    "                break \n",
    "\n",
    "            if (values.get(best_feature) < best_value):\n",
    "                if self.left is not None:\n",
    "                    cur_node = cur_node.left\n",
    "            else:\n",
    "                if self.right is not None:\n",
    "                    cur_node = cur_node.right\n",
    "            \n",
    "        return cur_node.yhat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "45c3f3a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "hp = {\n",
    " 'max_depth': 3,\n",
    " 'min_samples_split': 50\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "22e7acb8",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(Y, X, **hp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "90c9e08f",
   "metadata": {},
   "outputs": [],
   "source": [
    "root.grow_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "de557c35",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root\n",
      "   | GINI impurity of the node: 0.0\n",
      "   | Class distribution in the node: {'No': 5, 'Yes': 9}\n",
      "   | Predicted class: Yes\n"
     ]
    }
   ],
   "source": [
    "root.print_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fbcb88c6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}