5-Tree Based Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5fbae9db-1adc-46e9-b7da-16e0c3fcbc56",
   "metadata": {},
   "source": [
    "# Tree Based models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43477788-1670-4083-910f-d67f229faa81",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f303e16-c93c-4a54-9a51-fdfcb2990978",
   "metadata": {},
   "source": [
    "Tree-based models are the models that use **Decision Trees** as their base algorithm. decision tree itself isn't that powerful model but other tree-based models like **Random Forest** and **Boosting Trees** are one of the most powerful algorithms out there. so in order to learn these algorithms first, we have to learn the decision tree. so first we will talk about decision trees and how to implement them from scratch, then we will talk about the ensemble methods."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73b5e114-1361-47d6-b985-ff2b6aade2a4",
   "metadata": {},
   "source": [
    "## Decision Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be49e68a-293f-4816-af5b-65ad9a76b3b2",
   "metadata": {},
   "source": [
    "in general, a Decision Tree (DT) makes a statement and then makes a decision based on whether or not the statement is True or False. usually, it is assumed that if the statement is True we go to the left and if it is False, we go to the right (this is the assumption we want to use from now on and also in our code). like other algorithms, if a DT classifies things, it is called **Classification Tree** and when a DT predicts numeric values, it is called **Regression Tree**.<br>\n",
    "These two types of trees have so much in common but have some differences too, so we gonna talk about them separately. but let's first talk about some terminology that we want to use when talking about tree-based models.<br>\n",
    "**Terminology:**<br>\n",
    "   * **Root node** or **the Root**: the first statement that our tree decides to make about our data.\n",
    "   * **Internal nodes** or **Branches**: other statements throughout our tree construction.\n",
    "   * **Leaf Nodes** or **Leaves**: nodes without any statement. these are the nodes we use to predict.\n",
    "   * **Depth**: number of times our tree splits.\n",
    "   * **Pure** or **Impure** leaf: in the Classification Tree if a leaf only contains one category it will be called pure if not, it will be called impure.<br>\n",
    "   \n",
    "**Classification Trees**:<br>\n",
    "the classification trees, are used when we want to classify things, so in our leaf nude we will have classes. as we said before, if in leaf nodes we just have one class category then we call the leaf pure otherwise it is impure. so now the question is, how do we construct our tree? how do we choose our statement? for choosing our statement we need some criteria to compare different statements and then choose one with respect to our criteria. in classification trees we will use **Gini Index** or **Cross-Entropy**, and choose the statement that has smallest Gini or Entropy. lower criteria mean we separate more classes using that statement. so we have to search over all possible statements and choose the one with the smallest criteria. for categorical variables, we check all the possible questions but for numerical variables, we have to do something else. so we sort our feature column values and use the mean value between unique values and use that threshold to make a statement and choose the one with smallest criteria. for each split, we have to check all the possible statements for all columns and choose the smallest criteria. after that, we split our data using that statement. for the next split now we have 2 separate datasets so again we check all possible statements and use one with the smallest criteria. but before we compare criteria we have to do one more thing and use some weight because these 2 datasets probably won't have the same number of samples so we assign some weight with respect to their sample size, so we will call that weighted criteria **Weighted Gini** or **Weighted Entropy**. we use the sum of these 2 weighted criteria to represent our statement criteria. we continue these steps until we reach pure leaves and after that, we won't split. so as you can see we can learn our data perfectly or in other words, we will overfit.<br>\n",
    "in the **prediction phase**, we move from top to bottom with respect to our sample feature values and we end up in some leaf, so the class in that leaf will be our prediction. if the leaf isn't pure (later) we will use the majority class as our prediction.<br>\n",
    "to **prevent overfitting** we can use these techniques:<br>\n",
    "   * Pruning\n",
    "   * Maximum depth\n",
    "   * Maximum leaf nodes\n",
    "   * minimum sample split\n",
    "   * minimum impurity decrease<br>\n",
    "\n",
    "**Notes**:\n",
    "   * Gini index is between 0 and 0.5 and entropy is between 0 and 1 (from best separation to worst)\n",
    "   * We have to treat these overfitting techniques as hyperparameters\n",
    "   * by using these techniques some leaf wont be pure.\n",
    "\n",
    "\n",
    "**Regression Trees**:<br>\n",
    "Regression trees are like classification trees in various ways but they have some differences too. in leaves, we will have continuous values. for criteria we are using **Mean Square Error** or **Mean Absolute Error** (and again use minimum for choosing our statement). in the prediction phase we will use the mean of values in leaf as our prediction.<br>\n",
    "\n",
    "**Some Pros and Cons of DT**:<br>\n",
    "   * Trees are non-linear and non-parametric models, which means they can grow as complex as necessary for any given dataset.\n",
    "   * They don't need preprocessing and can be trained with categorical data.\n",
    "   * They are interpretable.\n",
    "   * Without using any prohibition, our tree will overfit the training data.\n",
    "   * Trees are unstable, which means if we have a slight change in our dataset we may end up with a completely different tree.\n",
    "   * Generally they have low prediction accuracy.<br>\n",
    "\n",
    "now let's talk about how we can implement DT from scratch."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9d74c60-69cb-45aa-999a-5eaa0ddde75a",
   "metadata": {},
   "source": [
    "### Implementing decision Tree from scratch"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "681703fd-b3a4-4339-880b-c2a24bf35b07",
   "metadata": {},
   "source": [
    "#### Psudo code for classification tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce072cdb-067b-4fcc-8479-ac8fe33a7957",
   "metadata": {},
   "source": [
    "here I will use a recursive function to build my tree (I don't know if there is another way to implement it). because it is a recursive function so it has a base case and our function will call itself. the base case is when we want our function to stop repeating itself and here it is when we reach our leaf so we need a condition that defines when we want to stop from splitting or in other words we reach our leaf.\n",
    "\n",
    "1. check if the data is pure (this is where we define our base case. we can use other base cases too).\n",
    "2. if the base case is True, then treat the data as a leaf and predict. (by using the vast majority for classification and averaging for regression).\n",
    "3. if the base case is False, then treat these data as a node and split it with the next steps:<br>\n",
    "   * Find all potential splits.\n",
    "   * find the best split from all the potential splits using our criteria.\n",
    "   * split the node with our best split.\n",
    "4. now that we split our data, perform steps 1 to 3 again for each split data. (this is our recursive part)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd778313-fbd5-443b-bb85-4bb8cc43ad38",
   "metadata": {},
   "source": [
    "#### Some Notes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dcf0fbbd-4f14-43b2-83ac-00e67a7fd0f9",
   "metadata": {},
   "source": [
    "* here we can't use categorical variables so we have to change them in advance.\n",
    "* the algorithm will continue until all the split data reach our base case i.e becoming leaf. but we add two more base case to prevent overfitting.\n",
    "* The data we are using is our breast cancer dataset but the feature columns and label column are in the same data and the label column is our last column.\n",
    "* My goal for writing the codes is to write them as easy as possible to not distract by code complexity. so I try not to use classes or even functions but here at the end, I have to use them because it is a recursive algorithm :) so I decide to use function through all the code and it is make everything much simpler and we can go through our algorithm step by step and not lost in the middle.\n",
    "* here I will code the classification tree but I also write the functions we need for regression.\n",
    "* The code is inspired by https://www.youtube.com/c/SebastianMantey youtube channel but I try to make it simpler and cleaner and add some other think or not use some part of the code that explained in the channel.\n",
    "* I'm a beginner in coding and it should be a better way to write the code, so try it your way :)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e91d894-eb68-4eef-b44e-84d3e69573c1",
   "metadata": {},
   "source": [
    "#### code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c5e7185d-1e3e-41f8-a95f-9f86dda63aed",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "abf7c045-f56f-48d0-8556-2a6b76b29ed4",
   "metadata": {},
   "outputs": [],
   "source": [
    "data,target= load_breast_cancer(return_X_y=True, as_frame=True) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6cac4c85-6c7c-4065-93c3-548a6b42d24d",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(data,target, test_size=0.2, random_state=42,stratify=target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8b066428-1957-4f3a-b1b9-bf27823fd154",
   "metadata": {},
   "outputs": [],
   "source": [
    "data_train = pd.concat([X_train,y_train],axis=1)\n",
    "data_test = pd.concat([X_test,y_test],axis=1)\n",
    "data_train = np.array(data_train)\n",
    "data_test = np.array(data_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c8cd389-4e11-4f6c-9bb2-05f155c6aeff",
   "metadata": {},
   "source": [
    "##### Helper Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c8cbbd4-65c0-48c6-8c23-fc09d46658ab",
   "metadata": {},
   "source": [
    "1. checking the purity of data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d22b2e6a-77b4-4512-8c71-800d32d088d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_purity(data):\n",
    "    labels = data[:,-1]\n",
    "    unique_class = np.unique(labels)\n",
    "    if len(unique_class) == 1:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3d96f0e-f143-434a-bfdc-e6cafb2fc5a9",
   "metadata": {},
   "source": [
    "2.1 leaf output for classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "846c7c06-cd29-41de-a755-559c64eed65f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leaf_classification(data):\n",
    "    labels = data[:,-1]\n",
    "    unique_classes, count_unique_classes = np.unique(labels,return_counts=True)\n",
    "    index = np.argmax(count_unique_classes)\n",
    "    return unique_classes[index]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a02c1e1-d886-44db-84ea-b4852cfc295b",
   "metadata": {},
   "source": [
    "2.2 leaf output for regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "135ae769-6b16-40e7-b5d2-8eb33b5c4801",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leaf_regression(data):\n",
    "    output = data[:,-1]\n",
    "    return np.mean(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "558a4193-754d-46bc-aa6f-42802dc30096",
   "metadata": {},
   "source": [
    "3. Potential split for numerical columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a6eb6bca-4599-46ca-917d-4b8bf4df6a89",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_potential_splits(data):\n",
    "    potential_splits = {}\n",
    "    n = data.shape[1] # number of columns for features\n",
    "    for column_index in range(n-1): ## if data and labels are in the same df then n-1\n",
    "        potential_splits[column_index] = []\n",
    "        values = data[:, column_index]\n",
    "        unique_values = np.unique(values)\n",
    "        for i in range(1, len(unique_values)):\n",
    "            average_unique_values = (unique_values[i] + unique_values[i-1])/2\n",
    "            potential_splits[column_index].append(average_unique_values)\n",
    "    return potential_splits\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7dec449-d77a-4e7f-a908-abe815d7b985",
   "metadata": {},
   "source": [
    "4. Split Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "51799644-2d7a-4094-bb1c-f2c16fc51a31",
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_data(data,split_column,split_value):\n",
    "    split_column_value = data[:, split_column]\n",
    "    data_below = data[split_column_value <= split_value]\n",
    "    data_above = data[split_column_value > split_value]\n",
    "    return data_below, data_above"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4ab3845-0d85-4068-b4b9-643fe9032375",
   "metadata": {},
   "source": [
    "5.1 Overall entropy of leaves for classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "778b3716-3e1d-4066-ad40-75d2e2d58825",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(data):\n",
    "    labels = data[:,-1]\n",
    "    counts = np.unique(labels,return_counts=True)[1]\n",
    "    probabilites = counts/np.sum(counts)\n",
    "    entropy = np.sum(-probabilites*np.log2(probabilites))\n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "824bcd6c-7210-4d94-81aa-698542c9fec3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_overall_entropy(data_below,data_above):\n",
    "    data_points = len(data_below) + len(data_above)\n",
    "    w_data_below = len(data_below)/data_points\n",
    "    w_data_above = len(data_above)/data_points\n",
    "    overall_entropy = (w_data_below * entropy(data_below)) + (w_data_above * entropy(data_above))\n",
    "    return overall_entropy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3e6e28e-6f7f-48f7-8033-d87e7e9952bc",
   "metadata": {},
   "source": [
    "5.2 overall gini of leaves for classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "baae7a48-49fe-4d1d-9a6b-73076b8c26be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(data):\n",
    "    labels = data[:,-1]\n",
    "    counts = np.unique(labels,return_counts=True)[1]\n",
    "    probabilites = counts/np.sum(counts)\n",
    "    gini = 1 - np.sum(probabilites**2)\n",
    "    return gini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4cd065eb-e818-4bf3-88a8-08f379e15cde",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_overall_gini(data_below,data_above):\n",
    "    data_points = len(data_below) + len(data_above)\n",
    "    w_data_below = len(data_below)/data_points\n",
    "    w_data_above = len(data_above)/data_points\n",
    "    overall_gini = (w_data_below * gini(data_below)) + (w_data_above * gini(data_above))\n",
    "    return overall_gini"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d080a664-bb92-47a0-ab03-ac1b7b3b8af2",
   "metadata": {},
   "source": [
    "5.3 Overall mean square error of leaves for regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3d4e22bb-ea03-4b2d-976e-dc4d54385f27",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mse(data):\n",
    "    actual_values = data[:,-1]\n",
    "    mean_actual_values = np.mean(actual_values)\n",
    "    mse = np.mean((actual_values-mean_actual_values)**2)\n",
    "    return mse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "264a9ee3-888f-478a-843c-6b6fcc54fa5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_overall_mse(data_below,data_above):\n",
    "    data_points = len(data_below) + len(data_above)\n",
    "    w_data_below = len(data_below)/data_points\n",
    "    w_data_above = len(data_above)/data_points\n",
    "    overall_mse = (w_data_below * mse(data_below)) + (w_data_above * mse(data_above))\n",
    "    return overall_mse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64680245-5c75-49cf-bb87-ba4add60c683",
   "metadata": {},
   "source": [
    "6.1 Determine best split value and column for classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "37afe15e-721a-466a-b973-b7fb9729902e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_split_classification(data, potential_splits): # or we can use calculate_overall_gini\n",
    "    \n",
    "    overall_entropy = 1000 # we know that entropy is between 0 and 1 so we choose a high number so our code at least executes once then overwrite it with a new value\n",
    "    for column_index in potential_splits:\n",
    "        for value in potential_splits[column_index]:\n",
    "            data_below, data_above = split_data(data, split_column=column_index, split_value = value)\n",
    "            current_overall_entropy = calculate_overall_entropy(data_below, data_above) \n",
    "            if current_overall_entropy < overall_entropy:\n",
    "                overall_entropy = current_overall_entropy\n",
    "                best_split_column = column_index\n",
    "                best_split_value = value\n",
    "            \n",
    "    return best_split_column, best_split_value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c9a5d31-0dcd-4abd-bd95-a5650acfe370",
   "metadata": {},
   "source": [
    "6.2 Determine best split value and column for regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b68f1af8-f333-4a9c-b6fb-c759574fa0e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_split_regression(data, potential_splits):\n",
    "    \n",
    "    first_iteration = True\n",
    "    for column_index in potential_splits:\n",
    "        for value in potential_splits[column_index]:\n",
    "            data_below, data_above = split_data(data, split_column=column_index, split_value = value)\n",
    "            current_overall_mse = calculate_overall_mse(data_below, data_above) \n",
    "            if first_iteration or current_overall_mse < best_overall_mse:\n",
    "                best_overall_mse = current_overall_mse\n",
    "                best_split_column = column_index\n",
    "                best_split_value = value\n",
    "            \n",
    "    return best_split_column, best_split_value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ad9d83f-4eba-42fd-9b22-5d9f93b0ac48",
   "metadata": {},
   "source": [
    "##### DT Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "97c7b801-1877-49c2-9a71-0bf2c185fe64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def DT_algorithm(data,counter=0,min_sample=2,max_depth=5):\n",
    "    if (check_purity(data)) or (len(data) < min_sample) or (counter==max_depth):\n",
    "        classification = leaf_classification(data)\n",
    "        return classification\n",
    "    else:\n",
    "        counter+=1\n",
    "        potential_splits = get_potential_splits(data)\n",
    "        split_column, split_value = best_split_classification(data, potential_splits)\n",
    "        data_below, data_above = split_data(data,split_column, split_value)\n",
    "        \n",
    "        question = '{} <= {}'.format(split_column,split_value)\n",
    "        subtree = {question : []}\n",
    "        \n",
    "        yes_answer = DT_algorithm(data_below,counter,min_sample,max_depth)\n",
    "        no_answer = DT_algorithm(data_above,counter,min_sample,max_depth)\n",
    "        \n",
    "        subtree[question].append(yes_answer)\n",
    "        subtree[question].append(no_answer)\n",
    "        return subtree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "3ad92276-6226-4f58-83c2-52278ee44bc5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: total: 3.62 s\n",
      "Wall time: 3.63 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "tree = DT_algorithm(data_train,max_depth=3,min_sample=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8a6b56d5-e938-4398-86d7-c4c1577f026e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'20 <= 16.795': [{'27 <= 0.13595': [{'13 <= 38.605000000000004': [1.0, 1.0]},\n",
       "    {'1 <= 20.299999999999997': [1.0, 0.0]}]},\n",
       "  {'11 <= 0.47315': [1.0, {'26 <= 0.1907': [1.0, 0.0]}]}]}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "373ad67e-6948-47c8-b1d7-dade84826751",
   "metadata": {},
   "source": [
    "##### Prediction with our tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "02c44f6e-aba7-4c92-af93-8cd83d64f9bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prediction(data,tree):\n",
    "    question = list(tree.keys())[0]\n",
    "    feature_name,comparison_operator,value = question.split() # it will split the string into several split with string type\n",
    "    \n",
    "    if data[int(feature_name)] <= float(value): # we have to change the splits into numbers\n",
    "        answer = tree[question][0]\n",
    "    else:\n",
    "        answer = tree[question][1]\n",
    "    if not isinstance(answer, dict): # will return true of answer is dict, if is not dict it is our leaf i.e our answer if is dict, its another node with split\n",
    "        return answer\n",
    "    else:\n",
    "        return prediction(data,answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "d4fd616d-ab4d-45bd-a8cb-8f7b4f0b7c12",
   "metadata": {},
   "outputs": [],
   "source": [
    "predictions = []\n",
    "for i in range(len(data_test)):\n",
    "    predictions.append(prediction(data_test[i],tree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "07ee6037-5f3f-4b95-851c-3f45531dd2b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9473684210526315"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "accuracy = np.sum(predictions==data_test[:,-1])/len(data_test[:,-1])\n",
    "accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80be193e-c6c9-496c-92c0-c4a2be5cbad7",
   "metadata": {},
   "source": [
    "### Implementing Decision Tree with Scikit Learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "167486a2-0db2-4a6c-9832-336ea454d1e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "023438d0-45ba-4197-8a1f-73014a29dd14",
   "metadata": {},
   "outputs": [],
   "source": [
    "data,target= load_breast_cancer(return_X_y=True) \n",
    "X_train, X_test, y_train, y_test = train_test_split(data,target, test_size=0.2, random_state=42,stratify=target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "e92b3a92-3ed5-4ea9-86b5-574500ab29e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9473684210526315"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = DecisionTreeClassifier(criterion='entropy',min_samples_split=20)\n",
    "tree.fit(X_train,y_train)\n",
    "tree.score(X_test,y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fdd6dbb-8946-49de-80be-d5a485cfe24e",
   "metadata": {},
   "source": [
    "well, we get the same accuracy, it feels good, right? :)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "426ee6cf-ee5b-470e-afef-40337f5c8585",
   "metadata": {},
   "source": [
    "## Ensemble Technique"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deda3860-b52b-4870-95dd-37ad678ba8b1",
   "metadata": {},
   "source": [
    "The idea here is instead of asking a question from one person (even an expert one or in our topic, the algorithm with high accuracy), we can ask our question to thousands of random people (random and independent from each other which means they won't affect each other answers) and the majority vote or someother combination their answers, is our answer. we will often get better predictions to compare with the best individual predictors. the group of predictors is called **Ensemble** so this technique is called **Ensemble Learning**. therefore we can train our dataset with different algorithms (e.g LR, SVM, DT) and use voting or averaging between the result of these algorithms and use it as our final prediction, we usually get better answers. but besides that, there are three methods of ensembling:<br>\n",
    "   * Bagging (Bootstrap AGGregation)\n",
    "   * Boosting\n",
    "   * Stacking (Stacked Generalization)\n",
    "\n",
    "in **Bagging** we use **Bootstrap** sampling which means random sampling subsets of our original dataset with replacement same size as our dataset and train our model on them and use voting or averaging for prediction. with this model, we can have the same bias with lower variance compared to the individual model so it is a good fit for a high variance algorithm (like a decision tree).<br>\n",
    "in **Boosting** we combine several **Weak Learners** into a strong learner. the weak learner means models that do slightly better than random chance i.e having accuracy slightly bigger than 50%. the general idea of most boosting methods is to train predictors sequentially, and each one trying to correct its predecessor.<br>\n",
    "in **Stacking** like simple ensembling, we use different algorithms but instead of using voting we assign some weight to each model and determine which algorithm we should trust more i.e have more impact on our final prediction. so these weights should learned through the algorithm.<br>\n",
    "in the following, we want to talk about the combination of these ensemble methods with DT and make two of the most powerful models."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b084e756-d23f-4277-9578-124e75a34f2f",
   "metadata": {},
   "source": [
    "## Random forest"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94566cfd-ac3c-4f2a-8289-e56d53d537ec",
   "metadata": {},
   "source": [
    "Random forest is the combination of bagging and decision tree. so the idea here is to create new datasets using bootstrap sampling and train decision tree on each of the bootstraped dataset. so:<br>\n",
    "1. Create a bootstrapped dataset, which means sampling randomly with replacement.\n",
    "2. create a decision tree using the bootstrapped dataset, but instead of using all the feature columns choose only random subsets of feature columns and build your tree with them.\n",
    "3. repeat steps 1 and 2 bunch of time.<br>\n",
    "\n",
    "by using bootstrap sampling and subset of our columns to build a tree, we will have wide varity of trees (that reasonably independent from each other). now in prediction phase, we run our new sample through all the trees and use vast majority of answers as our prediction for classification and average for regression.<br>\n",
    "**NOTES:**<br>\n",
    "   * in random forest beside all the hyperparameters in DT, now we have number of trees or number of estimators (maybe something between 100-1000).\n",
    "   * number of random columns is also can be treated as hyperparameter or we can use sqrt(#columns).\n",
    "   * when we are bootstrapping our dataset typically 1/3 of our original data doesn't endup in the bootsrapped dataset. these part of dataset called **Out Of Bag** dataset. we can use these out of bag datasets as cross validation set and tune our random forrest with it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f30a263-7455-43a1-b04b-dbd876db653a",
   "metadata": {},
   "source": [
    "### Implementing Random forest in Scikit Learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "e4067dab-3b47-4751-b87f-5d140e16a4ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "d6e09aea-2f0b-45f9-bb15-a6ff7ffe08b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "data,target= load_breast_cancer(return_X_y=True) \n",
    "X_train, X_test, y_train, y_test = train_test_split(data,target, test_size=0.2, random_state=42,stratify=target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e82888b9-6abc-4bd5-a9e6-6ef4cb924289",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.956140350877193"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RF = RandomForestClassifier(n_estimators=200,criterion='gini')\n",
    "RF.fit(X_train,y_train)\n",
    "RF.score(X_test,y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "209d0b85-be93-4460-abf5-b901242fb790",
   "metadata": {},
   "source": [
    "## Boosting Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c629c428-751c-408c-ab1e-04b4b66631f9",
   "metadata": {},
   "source": [
    "in general, as we said before, in boosting we have weak learners (here, shallow tree) and will use a bunch of them to create a strong model. because we have weak learners, like Rf, averaging them won't do much for us so instead in each step, somehow we have to specify the mistake we make and use the next learner and try to overcome those mistakes, and at the end instead of averaging we use the sum of all learners to make a prediction. the popular choice for weak learners is trees (relatively small ones) so we will talk about them.<br>\n",
    "in general, there are two main approaches to boosting trees that differ in how we specify our mistakes and how we use trees as weak learners. so let's talk about them separately."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73f0638d-1d0a-4e84-9671-a8d5b5d15d8b",
   "metadata": {},
   "source": [
    "### Adaptive Boosting or **AdaBoost**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a6e3203-5e56-49c0-868e-9fc94fbccfae",
   "metadata": {},
   "source": [
    "In **AdaBoost**, we are using **Stumps** as weak learners. stumps are trees with just one node and 2 leaves. so in each step, we choose the best feature and threshold and separate our data using them. each sample has its weight (equal weight at first), if we make mistake in classifying our sample we have to somehow increase its weight so that the next stumps pay more attention to them. in contrast, we will decrease the weight of samples that classify correctly. there is one more thing we have to specify, and that is how good our stump doing in each iteration so we need to assign some number to it so at the end, in the prediction phase, we more rely on stumps with higher performance. this number called **amount of say** or **stump performance**. lets see how we can wright Adaboost Algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9d3b0b8-d667-4cda-a170-56072913bd3e",
   "metadata": {},
   "source": [
    "#### AdaBoost Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "635329c1-6197-4959-be99-6d1947d4092a",
   "metadata": {},
   "source": [
    "1. Give each sample a weight that indicates how important it is to be correctly classified. at the start, all the samples get the same weight, and that makes the samples all equally important.<br> \n",
    "${Weights} = \\frac{1}{Total Number Of Samples}\\$ <br>\n",
    "2. Create a stump with the lowest criteria\n",
    "3. Now we need to determine how much say this stump will have in the final classification, based on how well it classified the samples.<br>\n",
    "    * Total Error (TE) for a Stump = sum of the weights associated with the incorrectly classified samples.<br>\n",
    "    \n",
    "    * Amount of say of a stump = $\\frac{1}{2}\\ ln\\frac{1-TE}{TE}\\$<br>\n",
    "    \n",
    "4. modify sample weights: we have to increase the weights of samples that the stump misclassified and decrease others.\n",
    "    * for increasing, new sample weight = sample weight.${e}^{Amount Of Say}$<br>\n",
    "    * for decreasing, new sample weight = sample weight.${e}^{-Amount Of Say}$<br>\n",
    "5. now normalize weights so they add up to 1. we divide all the weights by the sum of all the weights. so these weights are our new sample weights for our next stump.\n",
    "6. now we perform step 2 and use weighted criteria (like weighted Gini) for determining how to split our new stump. weighted Gini will put more emphasis on the sample that has more weight i.e misclassified in the previous stump.\n",
    "7. we continue making stumps with these 6 steps until we reach our maximum number of stumps or our tolerance. so in the end, we have some stumps with a specific amount of say.\n",
    "8. at the prediction phase new sample comes, and we check it with all of our stumps, some of them will classify it as 1 and some will classify it as 0, so we add all the amount of say that classify it as 1 and all of them that classify it as 0, and pick maximum as our prediction.<br>\n",
    "**NOTES:**\n",
    "   * because all the sample weights add up to 1, so total error always will be between 0 for the perfect stump and 1 for the horrible stump.\n",
    "   * when stump does a good job, and total error is small, the amount of say will be a relatively large positive value.<br>\n",
    "     if the total error is 0.5 (stump doing 50/50), the amount of say will be 0.<br>\n",
    "     and when stump does a terrible job and total error is close to 1, the amount of say will be a relatively large negative value.\n",
    "   * if the total error is equal to 1 or 0, the amount of say will be $+\\infty\\ , -\\infty\\$, so in practice, a small amount of error term is added to prevent this from happening.\n",
    "   * Alternatively, instead of using weighted criteria, we can make a new collection of samples that contains duplicate copies of the samples with larger sample weights (same size as our original dataset). so:\n",
    "        * we create bins with our weights by adding them one by one. so instead of weights now we have a range of weights for each sample (a sample with a bigger weight will have a wider bin).\n",
    "        * we start with an empty dataset that has the same size as our original dataset.\n",
    "        * pick a random number between 0 and 1.\n",
    "        * we see where that number falls in our bins and pick that sample and put it in our new dataset.\n",
    "        * we repeat last two steps until we fill our new dataset. what will happen here is that samples with larger weights will add multiple times in our new dataset.\n",
    "        * now get rid of the original dataset, and use our new dataset. here we will give all the samples the same weight again.\n",
    "        * now pick the stump with the lowest criteria value and do the rest of the steps."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7036838-574f-40ef-954c-2ae64e762557",
   "metadata": {},
   "source": [
    "### Gradient Boosting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ab1c062-d8d5-4952-8a38-64fff97f572f",
   "metadata": {},
   "source": [
    "In **Gradient Boosting** instead of using stumps we will use a bigger tree but still, we will restrict the size of trees. also instead of bolding our misclassified samples using weights, we will use something else called **Residuals** which are the difference between predicted values and real values. so in each tree, we will try to predict these residuals (as our mistake to overcome). there is one more thing we should do and it is scaling our tree in each iteration because we don't want to fully rely on our tree in each step in other words we just want some of its information in each step, so we scale them with **learning rate**. the learning rate is some number between 0,1 and constant so all the trees will have the same learning rate.. so we will have something like this:<br>\n",
    "$$\n",
    "{f_1(x)}\\approx{y}\n",
    "$$\n",
    "$$\n",
    "{f_2(x)}\\approx{y}-\\alpha{f_1(x)}\n",
    "$$\n",
    "$$\n",
    "{f_3(x)}\\approx{y}-\\alpha{f_1(x)}-\\alpha{f_2(x)}\n",
    "$$\n",
    "$$\n",
    "{.}\n",
    "$$\n",
    "$$\n",
    "{.}\n",
    "$$\n",
    "$$\n",
    "{.}\n",
    "$$\n",
    "\n",
    "so if we do it long enough our right-hand side (residuals) will be close to zero and our functions **together** will approximate y more closely. although gradient boosting algorithms for regression and classification have much in common but they have some minor differences so we will talk about them separately."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26c97ed6-960a-4b30-8e97-600c6dee2e96",
   "metadata": {},
   "source": [
    "#### Gradient Boosting Algorithm for Regression"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22e26bc7-f9cc-4b37-9c15-ea59a2f37061",
   "metadata": {},
   "source": [
    "1. calculate average of output value ${y}$, $\\bar{y}$. this is our first attempt to predict everyone's, but that's not good enough and we want to do better.<br>\n",
    "\n",
    "2. Calculate the error we make by assuming $\\bar{y}$ as our answer. so the error is the difference between observed ${y}$ and $\\bar{y}$.so we will have:<br>\n",
    "    ${Residuals} = {y} - \\bar{y}$\n",
    "\n",
    "3. now build a tree to predict residuals. in the result, we will have some leaves that contain residuals and because we restrict our tree from growing, so the leaves will have multiple values of residuals, so we will average each leaf and have one value for each leaf. what we have now is ${m}$ samples that connect to 8-32 leaves that output one value (average of our residuals in each leaf).\n",
    "4. now define learning rate $\\alpha$\n",
    "5. new predicted ${y}$ for each sample will be:\n",
    "\n",
    "    ${y}_{Predicted} = \\bar{y} + \\alpha$ (value of leaf that connected to this sample)<br>\n",
    "\n",
    "6. Calculate new residuals with new predicted ${y}$ like step 2.\n",
    "7. Again perform step 3 (in practice branches of the tree can be the same or different, but it is usually different)\n",
    "8. ${y}_{Predicted} = \\bar{y} + \\alpha$ (Tree1 + Tree2 + ... )<br>\n",
    "9. Perform steps 6-8 until we reach the maximum step that we define or adding more trees doesn't significantly reduce the size of residuals.\n",
    "10. in the prediction phase new sample comes, so:<br>\n",
    "\n",
    "    ${y}_{Prediction} = \\bar{y} + \\alpha$ (residual that connects this sample in tree 1 + residual that connects this sample in tree 2 + ... )<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e9bf2d9-9c54-4f3b-9376-531191c0761f",
   "metadata": {},
   "source": [
    "#### Gradient Boosting Algorithm for Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2953833e-b9b7-4c27-b541-faed89bba0cc",
   "metadata": {},
   "source": [
    "1. Guess initial prediction using log odds and convert it to probability using a logistic function.\n",
    "\n",
    "    ${Log Odds} = \\ln{\\frac{class 1}{class 0}}$\n",
    "    \n",
    "    Probability of class 1 = $\\frac{\\exp^{Log Odds}}{1 + \\exp^{LogOdds}}$\n",
    "\n",
    "2. Calculate Residuals:\n",
    "\n",
    "    ${Residual}$ = (Observed value Probability - Predicted Probability)<br>\n",
    "    Observed Probability = 0 and 1<br>\n",
    "    Predicted Probability = here is the value from step 1 but will change later<br>\n",
    "3. build a tree to predict residuals just like regression. here again, we limit grow of our tree.\n",
    "4. now we have to calculate the output of each leaf, even leaf with one residual, with this formula:<br>\n",
    "\n",
    "    output of leaves = $\\frac{\\sum{Residual_{i}}}{\\sum{Previous Probability_{i}) \\times (1 - Previous Probability_{i})}}$<br>\n",
    "    \n",
    "   in the first tree, previous probabilities are the same for all of the residuals, but later in other trees, it will be different. now every leaf has a single output.<br>\n",
    "5. define learning rate $\\alpha$\n",
    "6. for each sample we calculate a new ${LogOdds}$ prediction.<br>\n",
    "    \n",
    "    new ${LogOdds}$ Prediction = ${LogOdds}$ Prediction (from step 1) + $\\alpha$ (output value for each sample)\n",
    "    \n",
    "7. Convert new ${LogOdds}$ Prediction to probability using a logistic function. now all the samples have new probability and they are not the same.\n",
    "8. Calculate residuals with new predicted probability (like step 2).\n",
    "9. Build a tree to predict new residuals (like step 3).\n",
    "10. Calculate the output value of leaves (like step 4).\n",
    "11. new ${LogOdds}$ Prediction for each sample:<br>\n",
    "    \n",
    "    new ${LogOdds}$ Prediction = ${LogOdds}$ Prediction (from step 1) + $\\alpha$ (output value for each sample in tree 1 + output value for each sample in tree 2 + . . . )<br>\n",
    "\n",
    "12. Perform steps 7 - 11 until we reach the maximum number of trees or the residuals get super small.\n",
    "13. in the prediction phase, a new sample comes:<br>\n",
    "    \n",
    "    ${LogOdds}$ Prediction = ${LogOdds}$ Prediction (from step 1) + $\\alpha$ (output value for each sample in tree 1 + output value for each sample in tree 2 + . . . )<br>\n",
    "    \n",
    "    Probability Prediction = ${logistic({LogOdds})}$ Prediction<br>\n",
    "    \n",
    "    if the predicted probability is bigger than some threshold (default 0.5) classify as 1 else classify as 0.\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c0fb0f8-6c9f-441a-94a7-08b794737a25",
   "metadata": {},
   "source": [
    "#### Other Variants of Gradient Boosting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6969865c-53c3-437d-b870-1d899c3e7103",
   "metadata": {},
   "source": [
    "what we discussed before, is the raw gradient boost method. by some modifications we can get faster and more accurate algorithms like **XGBoost**, **LightGBM**, and **CatBoost**. let's talk about some of these modifications:<br>\n",
    "   * Have a unique way for create trees\n",
    "   * instead of averaging or counting, they optimize all the values in leaves. they also use regularization and second-order derivatives for optimization.\n",
    "   * instead of sorting and searching threshold for each split, they use binning (approximate algorithm for split finding). by using this algorithm we go from O(NlogN) to O(N).\n",
    "   * Aggressive sub-sampling and row sampling for creating each tree to prevent overfitting.\n",
    "   * parallel learning (using multi-core computation)\n",
    "   * and some other modifications"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25e5e508-d041-489d-872b-b092eeb908f1",
   "metadata": {},
   "source": [
    "#### Tuning Gradient Boost methods"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8dfcd9c-5b1a-4c7a-9865-56f32a3f9907",
   "metadata": {},
   "source": [
    "* Number of trees\n",
    "* Learning Rate\n",
    "* Typically strong pruning via maximum depth\n",
    "* Maximum feature\n",
    "* Column subsampling, row subsampling\n",
    "* Regularization in leaf (typically using L2 regularization)\n",
    "* we can use early stopping maybe by fixing the learning rate (i don't like early stopping even in gradient descent base models like neural networks :) )."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f407197-d731-48ef-9e9c-93e52ac9d4e2",
   "metadata": {},
   "source": [
    "#### Implementing XGBoost"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "595f5e02-92ce-4fb9-a4e5-057eaa9fbc99",
   "metadata": {},
   "source": [
    "we are going to solve our breast cancer problem using the XGBoost algorithm but not with the sklearn package. instead, we are going to use the xgboost package. so be sure to install the package first using any package manager like `pip` or `conda`.<br>\n",
    "it is more accurate and faster than the implementation in scikit learn and also has some other features like supporting categorical variables, supporting multi-core computation, and also supporting GPU. so let's use it :).\n",
    "for more information visit https://xgboost.readthedocs.io/en/stable/."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "6bd4a8b1-3852-464e-97b8-029ed7ffdb3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from xgboost import XGBClassifier #scikit learn implementation in xgboost package but in general it has its own format\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "3a2c0d0d-5b07-463a-a0bd-863ea48fa549",
   "metadata": {},
   "outputs": [],
   "source": [
    "data,target= load_breast_cancer(return_X_y=True) \n",
    "X_train, X_test, y_train, y_test = train_test_split(data,target, test_size=0.2, random_state=42,stratify=target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "7660e534-e56b-4ae2-9f6a-151e5fd6e98f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.956140350877193"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgb = XGBClassifier(n_estimators=100,max_depth=3,learning_rate=0.1)\n",
    "xgb.fit(X_train,y_train)\n",
    "xgb.score(X_test,y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1b6182b-8f2b-4d74-a74e-9b017228a58b",
   "metadata": {},
   "source": [
    "## Recap of Tree Based Models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4038a0d6-f44d-44e3-8fd8-95887429dd77",
   "metadata": {},
   "source": [
    "* Model non-linear relationships.\n",
    "* Doesn't care about scaling, and supports categorical data.\n",
    "* Single tree: very interpretable (if small).\n",
    "* Random Forests are very robust and have good benchmarks (always a good model, so always try it).\n",
    "* Gradient Boosting often gets the best performance but with careful tuning.\n",
    "* in general Boosting methods are harder to tune compared to RF.\n",
    "* in RF more trees are always better but in GB number of trees is strongly dependent on the learning rate.\n",
    "* by using a high number of trees in GB, we can overfit our model.\n",
    "* not good when we deal with wide or sparse datasets."
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}