lab3/lab3-trees_SVM_answers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 3: Trees and SVMs\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This lab uses the Python package [`graphviz`](https://pypi.org/project/graphviz). If you are using your own machine and using conda for installation do: `conda install conda-forge::python-graphviz`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import sklearn\n",
    "from sklearn import datasets\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.datasets import fetch_openml\n",
    "\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "import graphviz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1) Decision Trees\n",
    "\n",
    "Decision trees are a very simple machine learning technique that can be surprisingly powerful and offer a much more easily interpretable decision making process than many other methods. As the name suggests, decision trees are comprised of a set of nodes in a tree structure. All non-terminal nodes are called *decision nodes* which typically have two child nodes and contain a conditional expression involving a single feature of the input data. For a given input, starting at the root node, this condition is evaluated and this determines which of the two child nodes are selected for evaluation next. Once a *leaf node* is reached, the decision tree is able to produce an output class (classification) or a target value (regression). In this lab we will focus on the case of classification tasks.\n",
    "\n",
    "For a given dataset of input-output pairs, there are a number of ways to construct a decision tree that can accurately classify the set of examples. We will be using the implementation of decision trees from the scikit-learn library which uses the CART (Classification And Regression Tree) algorithm with (by default) the Gini impurity criterion (see [this](https://victorzhou.com/blog/gini-impurity/) for simple explanation of Gini impurity). The CART algorithm can be summarised as follows:\n",
    "1. **Obtaining the root node**: Test the possible splits of the dataset using conditions involving each of the input features and measure the Gini impurity of each split. The root node is given by the split that minimises the weighted sum of the Gini impurities of the two branches. The weights are equal to the number of data points that satisfy the condition of the corresponding branch.\n",
    "2. **Creating the remaining decision nodes**: Iteratively follow the same process as step 1 using only the data points that match the conditions necessary to reach this point in the tree.\n",
    "3. **Creating the leaf nodes**: These nodes are created when one of the stopping criteria is met. This set of criteria includes the case where all points of each class have been completely separated by a split (i.e. when the impurity is 0) or when some maximum depth has been reached.\n",
    "4. **Pruning**: The tree can then be 'pruned' back to a smaller tree in an attempt to prevent overfitting. The degree of pruning can be selected using either a validation set or cross-validation. Note however that the scikit-learn method `DecisionTreeClassifier.fit` by default does **no** pruning (but you can turn pruning on by setting `ccp_alpha` to a positive value)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1) Training a Decision Tree Classifier\n",
    "\n",
    "To start off, we will load in a classification dataset from scikit-learn: [the famous iris flower dataset](https://scikit-learn.org/stable/auto_examples/datasets/plot_iris_dataset.html#sphx-glr-auto-examples-datasets-plot-iris-dataset-py), compiled by Ronald Fisher in 1936. This is often used as a toy dataset for machine learning and contains three classes (species of Iris) with a number of named features such as petal length and width. The code below loads in the iris dataset but also includes the code to load in several other datasets that you can test your decision tree or ensemble methods on. These are commented out for now but you may wish to explore them later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = datasets.load_iris()\n",
    "#dataset = datasets.load_wine()\n",
    "#dataset = datasets.load_digits()\n",
    "\n",
    "X = np.array(dataset['data'])\n",
    "X_feature_names = dataset['feature_names']\n",
    "y = np.array(dataset['target'])\n",
    "y_target_names = dataset['target_names']\n",
    "\n",
    "# 60% training, 20% dev and 20% test\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=8) \n",
    "X_train, X_validation, y_train, y_validation = train_test_split(X_train, y_train, test_size = 0.25, random_state=8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1) Training a Decision Tree Classifier\n",
    "\n",
    "Use scikit-learn to train a [DecisionTreeClassifier](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier), (with no pruning) assigning it the variable name `model`, on the Iris dataset and compute its accuracy score on both the training and test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##CORRECT ANSWER##\n",
    "# write your code here\n",
    "model = DecisionTreeClassifier()\n",
    "model.fit(X_train, y_train)\n",
    "\n",
    "print(\"Training set accuracy: {}\".format(model.score(X_train, y_train)))\n",
    "print(\"Test set accuracy: {}\".format(model.score(X_test, y_test)))\n",
    "\n",
    "##CORRECT ANSWER##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is the model overfitting to the training data?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2) Visualise the tree\n",
    "\n",
    "The code below has been provided to create a visualisation for your decision tree. This cell will also print out a number of examples from the test set along with your tree's predictions to help you understand how the classification is being made. Run the cell and try to answer the questions that follow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Visualise the Decision Tree\n",
    "dot_data = sklearn.tree.export_graphviz(model, out_file=None, feature_names=X_feature_names, class_names=y_target_names, filled=True, rounded=True, special_characters=True)  \n",
    "graph = graphviz.Source(dot_data)\n",
    "graph.render(\"iris\")\n",
    "display(graph)\n",
    "\n",
    "# Print examples from the test dataset\n",
    "wdth = max([len(name) for name in X_feature_names] + [len(lab) for lab in y_target_names]) + 1\n",
    "print('| '.join([f'{X_feature_names[i]: <{wdth}}' for i in range(len(X_feature_names))] + [f'{\"Label\":<{wdth}}', \"Prediction\"]))\n",
    "print('-'*110)\n",
    "predicted_labels = model.predict(X_test)\n",
    "num_examples = 15\n",
    "for example, label, predicted_label in zip(X_test[:num_examples], y_test[:num_examples], predicted_labels[:num_examples]):\n",
    "    print('| '.join([f'{example[i]: <{wdth}}' for i in range(len(example))] + [f'{y_target_names[label]: <{wdth}}', f'{y_target_names[predicted_label]}']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try to answer the following questions for your tree (note that taking the left path from a decision node corresponds to the condition in that node being true):\n",
    "1. What features are most informative for identifying the Iris Setosa species and what values must they have? \n",
    "2. What features can be used to discriminate between Iris Virginica and Iris Versicolor if the petals are longer than 4.75cm (hint: look at the paths through the decision tree from root to leaf)?\n",
    "3. Choose one of the examples from the data set and follow the path that would be taken by the decision tree to produce a classification.\n",
    "4. If we had more training data, which decision nodes do you think are most likely to change (hint: look at numbers of samples)?\n",
    "5. Which decision nodes do you think may lead to the most errors if we deploy this model on a new test dataset? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3) Train a decision tree for MNIST\n",
    "\n",
    "For the iris dataset, we saw that our classifier was able to perform extremely well because of the dataset's simplicity. In this section, we will try to apply a decision tree to a more challenging dataset, the MNIST handwritten digits (as seen in week 5)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load the MNIST data\n",
    "X_mnist, y_mnist = fetch_openml(name='mnist_784',return_X_y=True, as_frame=False)\n",
    "frac_of_dataset = 0.5\n",
    "index = int(frac_of_dataset*X_mnist.shape[0])\n",
    "X_train, X_test, y_train, y_test = train_test_split(X_mnist[:index,:], y_mnist[:index], test_size=0.2, random_state=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like you did before, create and train a decision tree using scikit-learn and using the variable name `model`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##CORRECT ANSWER##\n",
    "# write your code to train a decision tree classifier here\n",
    "model = DecisionTreeClassifier()\n",
    "model.fit(X_train, y_train)\n",
    "##CORRECT ANSWER##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4) Compute the model's accuracy on MNIST train and test sets \n",
    "\n",
    "Compare the performance on train and test sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##CORRECT ANSWER##\n",
    "print(\"Training set accuracy: {}\".format(model.score(X_train, y_train)))\n",
    "print(\"Test set accuracy: {}\".format(model.score(X_test, y_test)))\n",
    "##CORRECT ANSWER##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is the model overfitting on the MNIST data? What happens if you set the pruning parameter `ccp_alpha` to, say, a high positive value?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2) Support vector machines (SVM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.svm import SVC\n",
    "from sklearn.neural_network import MLPClassifier\n",
    "from sklearn.datasets import make_moons\n",
    "from matplotlib.colors import ListedColormap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a parametric appoach a fixed number parameters are learn using training data which is then discarded and the learnt model used to make prediction on new data. In this section we implement support vector machines, a nonparametric model where the number of parameters are not fixed in advanced but grow with the amount of data.\n",
    "\n",
    "A support vector machine constructs a hyper-plane to separate classes by maximising the distance (or margin) to the nearest training data points of any class. The figure below shows the decision boundary for linearly separable data, with three instances on the margin boundaries, called “support vectors”.\n",
    "\n",
    "<img src=\"images/svm.png\" style=\"width:450px;height:300px;\">\n",
    "\n",
    "<caption><center> <u>Figure 4</u>: SVM decision boundary, margin and support vectors.</center></caption>\n",
    "\n",
    "For data that is not linearly separable, SVM classification involves quadratic programming optimisation to maximise the margin while incurring a penalty for each sample within the margin or a misclassification. The penalty strength is controlled by the hyperparameter `C`, a regularisation parameter that scales inversely.\n",
    "\n",
    "SVMs can perform non-linear classification using the kernel trick. The kernel function maps the non-linear data into a feature space in which the linear support vector regression model is fit. But SVMs do this without ever constructing a new data set in feature space.\n",
    "\n",
    "For more information on SVMs, see Bishop section 7.1.\n",
    "\n",
    "The exercise for SVM classification involves a toy dataset generated in the cell below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(0)\n",
    "N = 100\n",
    "x1 = np.linspace(-4,3.5,N).reshape(-1,1) + np.random.normal(0,0.2,N).reshape(-1,1)\n",
    "y1 = np.exp(0.6*x1) - 1 + np.random.normal(0,1.5,N).reshape(-1,1)\n",
    "x2 = np.random.normal(-1, 1.5, N).reshape(-1,1)\n",
    "y2 = np.random.normal(4, 1.5, N).reshape(-1,1)\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(7, 5))\n",
    "ax.scatter(x1,y1)\n",
    "ax.scatter(x2,y2)\n",
    "ax.set_xlim([-5,4])\n",
    "ax.set_ylim([-2,7])\n",
    "ax.set_xlabel('X')\n",
    "ax.set_ylabel('y')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logistic regression classifier\n",
    "A logistic regression classifier has been implemented on the toy dataset below, clearly not suitable for the non-linear data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.concatenate((np.concatenate((x1,x2)), np.concatenate((y1,y2))), axis=1)\n",
    "Y = np.concatenate((np.zeros(N),np.ones(N)))\n",
    "# blue = 0, orange = 1\n",
    "\n",
    "def plot_clf(clf):\n",
    "    h = 0.01\n",
    "    xx, yy = np.meshgrid(np.arange(-5, 4, h), np.arange(-2, 7, h))\n",
    "    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])\n",
    "    Z = Z.reshape(xx.shape)\n",
    "    fig, ax = plt.subplots(figsize=(7, 5))\n",
    "    ax.pcolormesh(xx, yy, Z, cmap=plt.cm.Paired, shading='auto')\n",
    "    ax.scatter(x1,y1)\n",
    "    ax.scatter(x2,y2)\n",
    "    ax.set_xlim([-5,4])\n",
    "    ax.set_ylim([-2,7])\n",
    "    ax.set_xlabel('X')\n",
    "    ax.set_ylabel('y')\n",
    "    \n",
    "logreg = LogisticRegression(solver='lbfgs')\n",
    "logreg.fit(X, Y)\n",
    "print(f'Logistic regression classifier accuracy: {logreg.score(X, Y)}')\n",
    "plot_clf(logreg)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1) SVM classifier\n",
    "Implement a SVM classifier using scikit-learn [SVC](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html#sklearn.svm.SVC) and the `plot_clf` function defined in the previous cell.\n",
    "\n",
    "Experiment with the hyperparameter `C` considering overfitting and generalisation. How would you tune `C`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# write your code here\n",
    "\n",
    "##CORRECT ANSWER##\n",
    "\n",
    "svm = SVC(C=4)\n",
    "svm.fit(X, Y)\n",
    "print(f'SVM classifier accuracy: {svm.score(X, Y)}')\n",
    "plot_clf(svm)\n",
    "plt.show()\n",
    "\n",
    "##CORRECT ANSWER##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3) Classifier comparison\n",
    "We are now going to compare the classifiers introduced above on a toy dataset plotted below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, y = make_moons(noise=0.3, random_state=0)\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(6, 4))\n",
    "# Plot the points\n",
    "cm_bright = ListedColormap(['#FF0000', '#0000FF'])\n",
    "ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cm_bright, edgecolors='k')\n",
    "ax.set_title(\"Input data\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The task is to train 4 classifiers on the dataset and compare the respective decision boundaries using a [contour](https://matplotlib.org/3.1.1/api/_as_gen/matplotlib.pyplot.contourf.html) plot, as shown below in figure 5.\n",
    "\n",
    "<img src=\"images/contour.png\" style=\"width:800px;height:200px;\">\n",
    "\n",
    "<caption><center> <u>Figure 5</u>: Example contour plot.</center></caption>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "names = [\"Logistic Regression\", \"Neural Net\", \"Linear SVM\", \"RBF SVM\"]\n",
    "              \n",
    "classifiers = [\n",
    "    LogisticRegression(C=1e5),\n",
    "    MLPClassifier(alpha=1, max_iter=1000),    \n",
    "    SVC(kernel=\"linear\", C=0.025),\n",
    "    SVC(gamma=2, C=1)]\n",
    "\n",
    "# create meshgrid\n",
    "x_min, x_max = X[:, 0].min() - .5, X[:, 0].max() + .5\n",
    "y_min, y_max = X[:, 1].min() - .5, X[:, 1].max() + .5\n",
    "h = .02  # step size in the mesh\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))\n",
    "\n",
    "# colour map (contourf cmap parameter)\n",
    "cm = plt.cm.RdBu\n",
    "\n",
    "def Z_mesh(clf):\n",
    "    # Plot the decision boundary. For that, we will assign a color to each\n",
    "    # point in the mesh [x_min, x_max]x[y_min, y_max].\n",
    "    if hasattr(clf, \"decision_function\"):\n",
    "        Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])\n",
    "    else:\n",
    "        Z = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1]        \n",
    "    return Z.reshape(xx.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The classifiers, with initial hyperparameters, are defined above. To help with making the contour plot, a [meshgrid](https://numpy.org/doc/stable/reference/generated/numpy.meshgrid.html) has been defined along with a `Z_mesh` function that returns the decision probability or decision output for the classifier for every point in the meshgrid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# write your code here\n",
    "\n",
    "##CORRECT ANSWER##\n",
    "\n",
    "figure = plt.figure(figsize=(20, 5))\n",
    "for i, clf in enumerate(classifiers):\n",
    "    \n",
    "    ax = plt.subplot(1, len(classifiers), i+1)\n",
    "    \n",
    "    clf.fit(X, y)\n",
    "    \n",
    "    Z = Z_mesh(clf)\n",
    "    \n",
    "    ax.contourf(xx, yy, Z, cmap=cm, alpha=.8)\n",
    "    ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cm_bright, edgecolors='k')\n",
    "    ax.set_title(names[i])\n",
    "    \n",
    "plt.show()\n",
    "##CORRECT ANSWER##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wrap up\n",
    "\n",
    "- Experiments with classification trees and looking into overfitting.\n",
    "- Support Vector Machine classification was used to fit a non-linear decision boundary and overfitting was explored.\n",
    "\n",
    "### References\n",
    "- Bishop Pattern Recognition and Machine Learning: Chapter 7 for support vector machines. \n",
    "\n"
   ]
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}