FML2w1_decision_trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clustering\n",
    "#### Part of the course on \"Foundations of machine learning\", Department of Mathematics and Statistics, University of Turku, Finland\n",
    "#### Lectures available on YouTube: https://youtube.com/playlist?list=PLbkSohdmxoVAZ9DEHEWHjeGK7Ei-DjKHI&si=Msu74_I0qhLrRWcu\n",
    "#### Code available on GitHub: https://github.com/ionpetre/FoundML_course_assignments\n",
    "\n",
    "#### This notebook is based on the following sources: \n",
    "> https://www.kaggle.com/code/mcmuralishclint/decision-tree-regression (MURALISH)\n",
    "\n",
    "> https://www.kaggle.com/code/marklvl/decision-tree-regressor-on-bike-sharing-dataset (MARK KAGHAZGARIAN)\n",
    "\n",
    "> https://www.kaggle.com/code/akashchola/decision-tree-for-classification-regression (AKASH GUPTA)\n",
    "\n",
    "> https://www.kaggle.com/code/arunmohan003/pruning-decision-trees-tutorial (ARUNMOHAN_003)\n",
    "\n",
    "Decision trees are a popular machine learning technique that offers a structured and intuitive way to make decisions based on data. They can be seen as a flowchart-like structure where each node represents a decision (a test on a feature), and each branch represents an outcome of that test. Decision trees are widely used for classification and regression tasks, as they excel in breaking down complex decision-making processes into a series of simple choices. One of the key advantages of decision trees is their interpretability, making them an excellent choice when transparency and understanding of the underlying logic are important. Additionally, decision trees can handle both categorical and numerical data, making them versatile tools in the data scientist's toolkit. However, they are prone to overfitting, especially when they become deep and complex, so careful pruning and tuning are often required to ensure optimal performance.\n",
    "\n",
    "In this noteebook we demonstrate how decisoin trees can be used for classification and for regrerssion. We use the UCI heart disease dataset for the classifier and a dataset on 2005 used GM car prices for the rergressor. We discuss the training of decision trees and how to prune them in different ways to address their tendency to overfit. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Load the libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-09-09T17:34:11.060373Z",
     "iopub.status.busy": "2021-09-09T17:34:11.059927Z",
     "iopub.status.idle": "2021-09-09T17:34:12.616363Z",
     "shell.execute_reply": "2021-09-09T17:34:12.615487Z",
     "shell.execute_reply.started": "2021-09-09T17:34:11.06034Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.model_selection import RandomizedSearchCV, GridSearchCV\n",
    "from sklearn import tree\n",
    "from sklearn.metrics import accuracy_score,confusion_matrix\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.metrics import make_scorer\n",
    "from sklearn.metrics import f1_score\n",
    "from sklearn.metrics import mean_squared_error as MSE\n",
    "from sklearn.metrics import r2_score as R2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reset the seed of the random number generator, for reproducibility purposes\n",
    "\n",
    "import os\n",
    "\n",
    "def reset_seed(SEED = 0):\n",
    "    \"\"\"Reset the seed for every random library in use (System, numpy)\"\"\"\n",
    "\n",
    "    os.environ['PYTHONHASHSEED']=str(SEED)\n",
    "    np.random.seed(SEED)\n",
    "\n",
    "\n",
    "reset_seed(220)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prepare the style of the plots\n",
    "\n",
    "plt.style.use(\"seaborn-whitegrid\")\n",
    "plt.rc(\"figure\", autolayout=True)\n",
    "plt.rc(\n",
    "    \"axes\",\n",
    "    labelweight=\"bold\",\n",
    "    labelsize=\"large\",\n",
    "    titleweight=\"bold\",\n",
    "    titlesize=14,\n",
    "    titlepad=10,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I. Demo decision trees on the UCI heart disease dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The UCI heart disease dataset: https://archive.ics.uci.edu/dataset/45/heart+disease\n",
    "\n",
    "The UCI Heart Disease dataset is a well-known dataset used in machine learning and data analysis to study and predict the presence of heart disease in individuals. It is often referred to as the \"Cleveland Heart Disease dataset\" because it was collected from the Cleveland Clinic Foundation in the late 1980s.\n",
    "\n",
    "Here are some key details about the UCI Heart Disease dataset:\n",
    "\n",
    "1. Data Source: The dataset was collected from the Cleveland Clinic Foundation's Heart Disease Institute. The original dataset had several contributors, including Robert Detrano, Don Brownlee, and Wesley Turner.\n",
    "\n",
    "2. Data Description: The UCI Heart Disease dataset consists of 303 instances, each representing a patient, and contains 76 attributes. However, only 14 of these attributes are typically used in analysis and modeling. These attributes include features such as age, sex, chest pain type, resting blood pressure, cholesterol level, maximum heart rate, exercise-induced angina, and more.\n",
    "\n",
    "3. Target Variable: The primary target variable in this dataset is the presence of heart disease, where '0' typically indicates no heart disease and '1' indicates the presence of heart disease. This binary classification task makes it a popular choice for predictive modeling.\n",
    "\n",
    "4. Purpose: The UCI Heart Disease dataset is commonly used for research, practice, and educational purposes in the field of cardiovascular medicine, as well as in machine learning and data science. Researchers and data scientists use this dataset to develop predictive models for diagnosing heart disease and assessing cardiovascular risk factors.\n",
    "\n",
    "5. Data Availability: The UCI Heart Disease dataset is publicly available and can be accessed through the UCI Machine Learning Repository or various data science platforms and libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_openml\n",
    "\n",
    "X, _ = fetch_openml(\n",
    "    data_id=43823,\n",
    "    as_frame=True,\n",
    "    return_X_y=True,\n",
    "    parser = 'auto'\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X.info()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The target feature is 'Heart_Disease'. We save it in the variable y and encode it as 0/1.\n",
    "\n",
    "from sklearn.preprocessing import LabelEncoder\n",
    "le = LabelEncoder()\n",
    "y = pd.DataFrame(le.fit_transform(X['Heart_Disease']))\n",
    "y.value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We drop the target feature 'Heart_Disease' from the X dataset. \n",
    "\n",
    "X = X.drop('Heart_Disease', axis=1)\n",
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train_valid, X_test, y_train_valid, y_test = train_test_split(\n",
    "    X, \n",
    "    y, \n",
    "    test_size=0.2, \n",
    "    random_state=150, \n",
    "    stratify=y,\n",
    "    shuffle=True\n",
    ")\n",
    "\n",
    "X_train, X_valid, y_train, y_valid = train_test_split(\n",
    "    X_train_valid, \n",
    "    y_train_valid, \n",
    "    test_size=0.25, \n",
    "    random_state=150, \n",
    "    stratify=y_train_valid,\n",
    "    shuffle=True\n",
    ")\n",
    "\n",
    "# convert to pandas dataframe\n",
    "X_train = pd.DataFrame(X_train, columns=X.columns)\n",
    "X_valid = pd.DataFrame(X_valid, columns=X.columns)\n",
    "X_test = pd.DataFrame(X_test, columns=X.columns)\n",
    "y_train = pd.DataFrame(y_train, columns=y.columns)\n",
    "y_valid = pd.DataFrame(y_valid, columns=y.columns)\n",
    "y_test = pd.DataFrame(y_test, columns=y.columns)\n",
    "\n",
    "del X\n",
    "del y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(X_train.info(), \"\\n\", X_valid.info(), \"\\n\", X_test.info())\n",
    "print(y_train.value_counts(), \"\\n\", y_valid.value_counts(), \"\\n\", y_test.value_counts())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Train a decision tree classifier with its default setup. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = tree.DecisionTreeClassifier(random_state=2023)\n",
    "clf.fit(X_train,y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Display the decision tree. \n",
    "Each node is shown with its internal characteristics: the decision rule, the impurity, the class balance. The decision that could be made in each node based on the class balance is indicated through the coloring of the node. The more orange the node, the clearer the decision for \"Not heart disease\". The more blue the node, the clearer the decision for \"Heart disease\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(60,30))\n",
    "features = list(X_train.columns.values)\n",
    "classes = ['NO','YES']\n",
    "tree.plot_tree(\n",
    "    clf,\n",
    "    feature_names = features,\n",
    "    class_names = classes,\n",
    "    filled = True,\n",
    "    proportion = False,\n",
    "    impurity = True, \n",
    "    rounded = True,\n",
    "    fontsize = 16\n",
    ")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check some of the characteristics of the tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Depth of the decision tree: \", clf.get_depth())\n",
    "print(\"Number of leaves: \", clf.get_n_leaves())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check the quality of the predictions through the accuracy score (on train and validation) and through the confusion matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_confusionmatrix(y_train_pred,y_train,dom):\n",
    "    print(f'{dom} confusion matrix:')\n",
    "    cf = confusion_matrix(y_train_pred,y_train, normalize=None)\n",
    "    plt.figure(figsize=(4,3))\n",
    "    sns.heatmap(cf,annot=True,yticklabels=classes\n",
    "               ,xticklabels=classes,cmap='Blues', fmt='g')\n",
    "    plt.tight_layout()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_train_pred = clf.predict(X_train)\n",
    "y_valid_pred = clf.predict(X_valid)\n",
    "\n",
    "print(f'Train score {accuracy_score(y_train, y_train_pred)}')\n",
    "print(f'Validation score {accuracy_score(y_valid, y_valid_pred)}')\n",
    "\n",
    "plot_confusionmatrix(y_train, y_train_pred, dom='Train')\n",
    "plot_confusionmatrix(y_valid, y_valid_pred, dom='Validation')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The confusion matrix shows that the model gets perfect predictions on the training set, and only about 80% correct on the validation set: 23/30 for class 'NO' and 16/24 for class 'YES'. This is a sign that the classifier is overfit. This is a typical problem for decision trees. \n",
    "\n",
    "We explore next some pruning techniques: limiting the depth, the number of leaves, and the minimal-cost complexity pruning. We also check if using a different split criterion may help. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Minimal cost complexity pruning (also known as minimal cost complexity pruning, cost-complexity pruning, or simply cost pruning) is a method used to prune decision trees to avoid overfitting. Decision trees, when fully grown, can become overly complex and capture noise in the training data, leading to poor generalization on unseen data. Pruning helps simplify the tree by removing branches and nodes that do not significantly contribute to its predictive power.\n",
    "\n",
    "The main idea behind minimal cost complexity pruning is to add a penalty term for tree complexity during the pruning process. The penalty term is controlled by a tuning parameter, typically denoted as \"alpha\" (α). By varying the value of alpha, you can adjust the trade-off between tree complexity and predictive accuracy.\n",
    "\n",
    "Here's how minimal cost complexity pruning works:\n",
    "\n",
    "> Initial Tree Construction: Start by growing a full, potentially overfit decision tree using a standard tree-building algorithm.\n",
    "\n",
    "> Calculate Cost Complexity Measure: For each node in the tree, calculate a cost complexity measure that combines two factors: the impurity of the node (such as Gini impurity or entropy) and the size of the subtree rooted at that node.\n",
    "\n",
    "> Introduce the Complexity Penalty: Introduce the tuning parameter alpha (α), which controls the strength of the penalty. A small alpha value encourages a more complex tree, while a large alpha value encourages a simpler tree.\n",
    "\n",
    "> Pruning Process: Starting from the leaves and moving toward the root of the tree, evaluate whether the \"cost\" of removing a subtree (as determined by the complexity measure) is smaller than the \"benefit\" in terms of reduced complexity and potential improvements in predictive accuracy. Prune subtrees that do not pass this cost-benefit analysis.\n",
    "\n",
    "> Select the Optimal Alpha: You can use techniques like cross-validation to find the optimal value of alpha that balances model complexity and predictive accuracy.\n",
    "\n",
    "> Final Pruned Tree: The result is a pruned decision tree with a balanced trade-off between model complexity and predictive performance. The pruned tree is typically more interpretable and less prone to overfitting.\n",
    "\n",
    "Minimal cost complexity pruning helps ensure that the final decision tree is a good compromise between capturing the training data's patterns and avoiding overfitting. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We apply a GridSearch to explore various combinations of parameter values. We do this with a 5-fold cross-validation apporach. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "param_grid = {\n",
    "              \"min_samples_split\": [2, 3, 5, 7],\n",
    "              \"max_depth\": [3, 4, 5, 6, 7, 8, 9],\n",
    "              \"max_leaf_nodes\": [10, 20, 30, 50],\n",
    "              'ccp_alpha': [0, 0.1, 0.2]\n",
    "              }\n",
    "\n",
    "\n",
    "clf = tree.DecisionTreeClassifier(random_state=2023)\n",
    "gcv = GridSearchCV(\n",
    "    estimator = clf,\n",
    "    cv = 5,\n",
    "    param_grid = param_grid,\n",
    "    refit = True,\n",
    "    n_jobs = -1,\n",
    "    verbose = 1,\n",
    ")\n",
    "gcv.fit(X_train_valid,y_train_valid)\n",
    "\n",
    "best_clf = gcv.best_estimator_\n",
    "best_clf.fit(X_train,y_train)\n",
    "y_train_pred = best_clf.predict(X_train)\n",
    "y_valid_pred = best_clf.predict(X_valid)\n",
    "\n",
    "print(f'Train score {accuracy_score(y_train, y_train_pred)}')\n",
    "print(f'Validation score {accuracy_score(y_valid, y_valid_pred)}')\n",
    "plot_confusionmatrix(y_train, y_train_pred, dom='Train')\n",
    "plot_confusionmatrix(y_valid, y_valid_pred, dom='Validation')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our hyper-parameter tuning worked out: we got a model that does better on the validation set, while remaining very good on the training set. Comparing the confusion matrices, we see that the model improved: 27/30 correct predictions in class 'NO' and 17/24 correct predictions in class 'YES'. We check its properties. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Depth of the improved decision tree: \", best_clf.get_depth())\n",
    "print(\"Number of leaves: \", best_clf.get_n_leaves())\n",
    "\n",
    "plt.figure(figsize=(60,30))\n",
    "features = list(X_train.columns.values)\n",
    "classes = ['NO','YES']\n",
    "tree.plot_tree(\n",
    "    best_clf,\n",
    "    feature_names = features,\n",
    "    class_names = classes,\n",
    "    filled = True,\n",
    "    proportion = False,\n",
    "    impurity = True, \n",
    "    rounded = True,\n",
    "    fontsize = 16\n",
    ")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the parameters of the best model we got through GridSearchCV\n",
    "\n",
    "best_clf.get_params()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Model's performance on the test dataset\n",
    "\n",
    "y_test_pred = best_clf.predict(X_test)\n",
    "\n",
    "print(f'Test score {accuracy_score(y_test, y_test_pred)}')\n",
    "plot_confusionmatrix(y_test, y_test_pred, dom='Test')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "del X_train_valid\n",
    "del y_train_valid\n",
    "del X_train\n",
    "del y_train\n",
    "del X_valid\n",
    "del y_valid\n",
    "del X_test\n",
    "del y_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will train a decision tree regressor on a dataset of used car prices. This is taken from the 2005 version of the Kelly Blue Book and concerns several models of General Motors cars. \n",
    "\n",
    "Link to the dataset: https://www.openml.org/search?type=data&status=any&id=44994&sort=runs\n",
    "\n",
    "**Data Description**\n",
    "\n",
    "Data frame of the suggested retail prices (column Price) and various characteristics of each car.\n",
    "\n",
    "For this data set, a representative sample of over eight hundred 2005 GM cars were selected, then retail prices were calculated from the tables provided in the 2005 Central Edition of the Kelly Blue Book.\n",
    "\n",
    "Attribute Description\n",
    "\n",
    "All features describe different self-explanatory characteristics for the cars.\n",
    "\n",
    "Price - target feature\n",
    "Mileage\n",
    "Cylinder\n",
    "Doors\n",
    "Cruise\n",
    "Sound\n",
    "Leather\n",
    "Buick\n",
    "Cadillac\n",
    "Chevy\n",
    "Pontiac\n",
    "Saab\n",
    "Saturn\n",
    "convertible\n",
    "coupe\n",
    "hatchback\n",
    "sedan\n",
    "wagon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_openml\n",
    "\n",
    "X, y = fetch_openml(\n",
    "    data_id=???,\n",
    "    as_frame=True,\n",
    "    return_X_y=True,\n",
    "    parser = 'auto'\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q1. How many features you have in the dataset (not counting the target feature 'Price')?\n",
    "#### Q2. Do you have missing values in your dataset? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Split the data into train/validation/test. Use random_state=150 and the same ratios train/valid/test as in the demo part.\n",
    "# Your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q3. Train a decision tree regressor with the sklearn libary, where all parameters are left to their default values, except for random_state, to be set to 2023. What is the depth of the tree?\n",
    "#### Q4. What is the number of its leaves? \n",
    "#### Q5. What is the mean squared error on the training dataset? \n",
    "#### Q6. What is the mean squared error on the validation dataset (0 decimals)?\n",
    "#### Q7. What is the r2 score on the training dataset (2 decimals)? \n",
    "#### Q8. What is the r2 score on the validation dataset (2 decimals)? \n",
    "#### Q9. Do you consider this tree to be overfit? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Train a decision tree regressor\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q10. Do a parameter grid search on the following combination of parameter values. What is the r2 score of the best model on the training data (2 decimals)?\n",
    "\n",
    "param_grid = {\n",
    "              \"max_depth\": [5, 10, 15, 20, 25],\n",
    "              \"max_leaf_nodes\": [50, 100, 200, 400],\n",
    "              'ccp_alpha': [0, 0.2, 0.4]\n",
    "              }\n",
    "              \n",
    "#### Q11. What is the r2 score of the best model on the validation data (2 decimals)? \n",
    "#### Q12. Do you consider this model to be better than the one with the default parameter values? \n",
    "#### Q13. What is the depth of this model? \n",
    "#### Q14. What is the r2 score of the best model (either the initial one or the one obtained through the grid search) on the test data (2 decimals)? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.9.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}