Decision Tree Regressor from scratch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import mean_squared_error\n",
    "\n",
    "# Built in sklearn es muchisimo mas rapido que python, en un coment dice que es poruqe usa cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "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>x0</th>\n",
       "      <th>x1</th>\n",
       "      <th>x2</th>\n",
       "      <th>x3</th>\n",
       "      <th>x4</th>\n",
       "      <th>y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>800</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.3048</td>\n",
       "      <td>71.3</td>\n",
       "      <td>0.002663</td>\n",
       "      <td>126.201</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.3048</td>\n",
       "      <td>71.3</td>\n",
       "      <td>0.002663</td>\n",
       "      <td>125.201</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1250</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.3048</td>\n",
       "      <td>71.3</td>\n",
       "      <td>0.002663</td>\n",
       "      <td>125.951</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1600</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.3048</td>\n",
       "      <td>71.3</td>\n",
       "      <td>0.002663</td>\n",
       "      <td>127.591</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>2000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.3048</td>\n",
       "      <td>71.3</td>\n",
       "      <td>0.002663</td>\n",
       "      <td>127.461</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     x0   x1      x2    x3        x4        y\n",
       "0   800  0.0  0.3048  71.3  0.002663  126.201\n",
       "1  1000  0.0  0.3048  71.3  0.002663  125.201\n",
       "2  1250  0.0  0.3048  71.3  0.002663  125.951\n",
       "3  1600  0.0  0.3048  71.3  0.002663  127.591\n",
       "4  2000  0.0  0.3048  71.3  0.002663  127.461"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = pd.read_csv(\"airfoil_noise_data.csv\")\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    def __init__(self, feature_index=None, threshold=None, left=None, right=None, var_red=None, value=None): # init se usa para constructor methods de la class\n",
    "        self.feature_index = feature_index\n",
    "        self.threshold = threshold\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.var_red = var_red\n",
    "        self.value =value # only for leaf nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeRegressor():\n",
    "    def __init__(self, min_samples_split=2, max_depth=2): # To prevent oferfitting we define these variables\n",
    "        self.root = None # Starting point\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.max_depth = max_depth\n",
    "        \n",
    "    def build_tree(self, dataset, curr_depth=0):\n",
    "        X,Y = dataset[:,:-1], dataset[:,-1] # simplemente esta definiendo X y Y\n",
    "        num_samples, num_features = np.shape(X)\n",
    "        best_split = {} \n",
    "        if num_samples>=self.min_samples_split and curr_depth<= self.max_depth:\n",
    "            best_split= self.get_best_split(dataset, num_samples, num_features)\n",
    "            if best_split[\"var_red\"]>0: # porque cuando es 0 es un nodo puro\n",
    "                \n",
    "                # Nota que es recursive method, estamos llamando a build_tree adentro de build tree\n",
    "                left_subtree = self.build_tree(best_split[\"dataset_left\"], curr_depth+1)\n",
    "                right_subtree = self.build_tree(best_split[\"dataset_right\"], curr_depth+1)\n",
    "                \n",
    "                return Node(best_split[\"feature_index\"], best_split[\"threshold\"], left_subtree,\n",
    "                           right_subtree, best_split[\"var_red\"])\n",
    "            \n",
    "        leaf_value = self.calculate_leaf_value(Y)\n",
    "        return Node(value= leaf_value) # leaf node\n",
    "    \n",
    "    \n",
    "    def variance_reduction(self, parent, l_child, r_child):\n",
    "        weight_l = len(l_child)/len(parent)\n",
    "        weight_r = len(r_child)/len(parent)\n",
    "        reduction = np.var(parent) -(weight_l*np.var(l_child) + weight_r*np.var(r_child))\n",
    "        return reduction\n",
    "    \n",
    "    def calculate_leaf_value(self, Y): # mean of values in a leaf node\n",
    "        val = np.mean(Y)\n",
    "        return val\n",
    "    \n",
    "    def split(self, dataset, feature_index, threshold):\n",
    "        dataset_left = np.array([row for row in dataset if row[feature_index]<=threshold])\n",
    "        dataset_right = np.array([row for row in dataset if row[feature_index]>threshold])\n",
    "        return dataset_left, dataset_right\n",
    "    \n",
    "    def get_best_split(self, dataset, num_samples, num_features):\n",
    "        best_split = {}\n",
    "        max_var_red = -float(\"inf\") # para maximizar variance reduction\n",
    "        \n",
    "        for feature_index in range(num_features): # iteramos para cada feature\n",
    "            feature_values = dataset[:, feature_index]\n",
    "            possible_thresholds = np.unique(feature_values)\n",
    "            \n",
    "            for threshold in possible_thresholds: # iteramos para cada valor de cada feature\n",
    "                dataset_left, dataset_right = self.split(dataset, feature_index, threshold)\n",
    "                \n",
    "                if len(dataset_left)>0 and len(dataset_right)>0: # ensure not empty\n",
    "                    y,left_y, right_y = dataset[:,-1], dataset_left[:,-1], dataset_right[:,-1]\n",
    "                    curr_var_red = self.variance_reduction(y, left_y, right_y)\n",
    "                    \n",
    "                    if curr_var_red> max_var_red:\n",
    "                        best_split[\"feature_index\"] = feature_index\n",
    "                        best_split[\"threshold\"] = threshold\n",
    "                        best_split[\"dataset_left\"] = dataset_left\n",
    "                        best_split[\"dataset_right\"] = dataset_right\n",
    "                        best_split[\"var_red\"] = curr_var_red\n",
    "                        max_var_red = curr_var_red\n",
    "        return best_split # returns dictionary of the characteristics of the best split\n",
    "    \n",
    "    def print_tree(self, tree= None, indent=\" \"):\n",
    "        if not tree:\n",
    "            tree = self.root\n",
    "        \n",
    "        if tree.value is not None:\n",
    "            print(tree.value)\n",
    "            \n",
    "        else:\n",
    "            print(\"X_\"+str(tree.feature_index), \"<=\", tree.threshold, \"var_red = \", tree.var_red)\n",
    "            print(\"%sleft:\"% (indent), end=\"\")\n",
    "            self.print_tree(tree.left, indent + indent)\n",
    "            print(\"%sright:\"% (indent), end=\"\")\n",
    "            self.print_tree(tree.right, indent + indent)\n",
    "            \n",
    "    def fit(self, X, Y): # trains the model\n",
    "        dataset = np.concatenate((X,Y), axis=1)\n",
    "        self.root = self.build_tree(dataset)\n",
    "        \n",
    "    def make_prediction(self, x, tree):\n",
    "        if tree.value!= None: return tree.value\n",
    "        feature_val = x[tree.feature_index]\n",
    "        if feature_val<= tree.threshold:\n",
    "            return self.make_prediction(x, tree.left)\n",
    "        else:\n",
    "            return self.make_prediction(x, tree.right)\n",
    "        \n",
    "    def predict(self, X):\n",
    "        predictions = [self.make_prediction(x, self.root) for x in X]\n",
    "        return predictions\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = data.iloc[:, :-1].values\n",
    "Y = data.iloc[:, -1].values.reshape(-1,1)\n",
    "X_train, X_test, Y_train, Y_test = train_test_split(X,Y, test_size = .2, random_state= 41)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X_0 <= 3150.0 var_red =  7.132048702017748\n",
      " left:X_4 <= 0.033779199999999995 var_red =  3.5903305690676675\n",
      "  left:X_3 <= 55.5 var_red =  1.1789899981318328\n",
      "    left:X_4 <= 0.00251435 var_red =  1.614396721819876\n",
      "        left:128.9919833333333\n",
      "        right:125.90953579676673\n",
      "    right:X_1 <= 15.4 var_red =  2.2342245360792994\n",
      "        left:129.39160280373832\n",
      "        right:123.80422222222222\n",
      "  right:X_0 <= 1250.0 var_red =  9.970884020498875\n",
      "    left:X_4 <= 0.0483159 var_red =  6.355275159824863\n",
      "        left:124.38024528301887\n",
      "        right:118.30039999999998\n",
      "    right:X_3 <= 39.6 var_red =  5.036286657241022\n",
      "        left:113.58091666666667\n",
      "        right:118.07284615384614\n",
      " right:X_4 <= 0.00146332 var_red =  29.082992105065273\n",
      "  left:X_0 <= 8000.0 var_red =  11.886497073996967\n",
      "    left:X_2 <= 0.0508 var_red =  7.608945827689513\n",
      "        left:134.04247500000002\n",
      "        right:127.33581818181818\n",
      "    right:X_4 <= 0.00076193 var_red =  10.622919322400815\n",
      "        left:128.94078571428574\n",
      "        right:122.4076875\n",
      "  right:X_4 <= 0.022902799999999997 var_red =  5.638575922510647\n",
      "    left:X_0 <= 6300.0 var_red =  5.985051045988911\n",
      "        left:120.04740816326529\n",
      "        right:114.67370491803278\n",
      "    right:X_4 <= 0.0368233 var_red =  8.63874479304644\n",
      "        left:113.83169565217393\n",
      "        right:107.6395833333333\n"
     ]
    }
   ],
   "source": [
    "Tree_regression = DecisionTreeRegressor(min_samples_split=3, max_depth=3)\n",
    "Tree_regression.fit(X_train, Y_train)\n",
    "Tree_regression.print_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.851358097184457"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# MSE\n",
    "Y_pred = Tree_regression.predict(X_test)\n",
    "np.sqrt(mean_squared_error(Y_test, Y_pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  },
  "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
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}