Copy_of_2_Neighborhood_Classifiers_and_decision_boundaries.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.4"
    },
    "colab": {
      "name": "Copy of 2 - Neighborhood Classifiers and decision boundaries.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/brleandro/ml_course/blob/master/Copy_of_2_Neighborhood_Classifiers_and_decision_boundaries.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EiWpaedHq11D",
        "colab_type": "text"
      },
      "source": [
        "# Demo 2: Neighborhood Classifiers, Training and Test set, Decision boundaries. 19/09"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wMfDlERyq11H",
        "colab_type": "text"
      },
      "source": [
        "Last week you implemented the 1 nearest neighbor (1-NN) algorithm. This week you will implement the KNN algorithm and the Parzen windows algorithm with hard neighborhood. On top of this, we will touch upon training and test sets, as well as decision boundaries.\n",
        "\n",
        "- Your first step is to remember how KNN and Parzen windows work.\n",
        "- You will need to implement a function that evaluates the [confusion matrix](http://en.wikipedia.org/wiki/Confusion_matrix) given true labels and predicted labels.\n",
        "- We provide you with the boilerplate code in which you will need to insert your KNN and Parzen windows implementations. This way you will be able to focus on the actual algorithm itself and you will not have to worry about things as printing or displaying results.\n",
        "- Once your implementation is correct, you will try different values of $k$ (number of neighbors) and pick the best ones.\n",
        "\n",
        "Familiarize yourself with the code in the following 5 sections:\n",
        "   - **Utility Functions:** Defines helper functions such as for visualization, evaluation, etc. This is where you will implement the confusion matrix function.\n",
        "   - **NeighborhoodClassifier class:** This is where you will implement the KNN and Parzen windows classifiers.\n",
        "   - **Loading and splitting the data:** Loads a dataset and splits it into two parts (train, test).\n",
        "   - **Initialization and training of classifiers:** Trains a KNN/Parzen windows model on the train dataset and obtains predictions on the test set.\n",
        "   - **Confusion matrix and decision boundary:** Displays the confusion matrix and visualizes the decision boundary of our trained classifiers.\n",
        "   - **Trying different values of $k$ for k-NN:** This is where you will fill in the function `get_test_error`, that would help plot the test error as a function of the number of neighbors (the plotting code is provided for you).\n",
        "\n",
        "**Your objective for this demo session** is to understand the general functioning of the code below and then to fill in the functions `conf_mat`, `NeighborhoodClassifier.compute_predictions()`, and `get_test_error`. All the places where you have to insert code are signaled by a `pass` statement.\n",
        "\n",
        "<hr />\n",
        "\n",
        "La semaine dernière vous avez implanté un 1-Plus-Proche-Voisin (1-PPV). Cette semaine vous implanterez un K-PPV et la méthode de Parzen. Par contre, cette semaine nous ferons aussi appel à la notion d'ensembles d'entrainement et de test, ainsi qu'à la notion de surface de décision. \n",
        "\n",
        "- Votre première étape est de vous remémorer le fonctionnement du K-PPV et de la méthode de Parzen.\n",
        "- Vous implanterez une fonction qui évalue la [matrice de confusion](http://fr.wikipedia.org/wiki/Matrice_de_confusion), etant données les vraies étiquettes et les étiquettes prédites. \n",
        "- Nous fournissons le cadre général où il vous faudra insérer le code de k-ppv et de la méthode de Parzen. On y retrouve notamment des fonctions pour rendre certaines tâches (comme l'affichage des résultats) plus faciles. Cela vous permettra de vous concentrer sur la partie algorithmique de ces méthodes.\n",
        "- Vous essaierez différentes valeurs pour le nombre de voisins, et vous choisirez la meilleure.\n",
        "Familiarisez-vous avec le code des cinq sections suivantes:\n",
        "    - **Fonctions utilitaires:** définit des fonctions utiles (visualisation, évaluation). C'est ici que vous implanterez la fonction qui évalue la matrice de confusion.\n",
        "    - **Classe NeighborhoodClassifier:** c'est ici que vous devez implanter les classifieurs.\n",
        "    - **Chargement et division des données:** charge un jeu de données et le divise en deux parties (train, test).\n",
        "    - **Initialisation et entraînement des classifieurs:** entraîne un modèle k-PPV et Parzen sur les données d'entraînement et obtient les prédictions des étiquettes pour les données de test.\n",
        "    - **Matrice de confusion et surface de décision:** Affiche la matrice de confusion et visualise la surface de décision pour les deux classifieurs\n",
        "    - **Essayez differentes valeurs de $k$ pour k-PPV:** C'est ici que vous implanterez la fonction `get_test_error`, qui aide à tracer la courbe de l'erreur sur le test en fonction du nombre de voisins (le code pour tracer cette courbe est déjà fourni).\n",
        "\n",
        "**Votre objectif pour la séance** est de comprendre le fonctionnement général du code fourni puis de compléter les fonctions `conf_mat`, `NeighborhoodClassifier.compute_predictions()`, et `get_test_error`.\n",
        "Inserez du code a chaque assertion `pass`.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iZ5_VALCq11J",
        "colab_type": "text"
      },
      "source": [
        "### Python classes / Classes en python"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "56jepwlVq11M",
        "colab_type": "text"
      },
      "source": [
        "For this demo, we will implement both KNN and Parzen windows as a **class** (one class for both algorithms). You can read this [tutorial](http://docs.python.org/3/tutorial/classes.html) if you are not familiar with the concept of classes in Object-oriented programming or its syntax in python. The class `NeighborhoodClassifier` is already partially implemented. All that you have left to do to implement the classifiers is to write the method `compute_predictions`.\n",
        "\n",
        "<hr />\n",
        "\n",
        "Pour cette démo, nous implémenterons k-ppv et la méthode de Parzen à l'intérieure d'une **classe** (une seule classe pour les deux algorithmes). Vous pouvez lire ce [tutoriel](http://docs.python.org/3/tutorial/classes.html) si vous n'êtes pas à l'aise avec les classes en python. La classe `NeighborhoodClassifier` est déjà partiellement implémentée, il ne vous reste qu'à compléter la méthode `compute_predictions` pour obtenir vos classifieurs."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OSDv-wTBq11O",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "## Utility Functions / Fonctions utilitaires"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mVlw-ooKq11T",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%matplotlib inline\n",
        "import numpy as np\n",
        "import random\n",
        "import matplotlib.pyplot as plt\n",
        "import time\n",
        "import sys\n",
        "IN_COLAB = 'google.colab' in sys.modules"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aCyOu-6Lq11f",
        "colab_type": "text"
      },
      "source": [
        "This functions calculates the Minkowski distance between a vector x and a matrix Y. Does this remind you of anything?\n",
        "<hr/>\n",
        "Cette fonction calcule la distance Minkowski entre un vecteur x et une matrice Y. Ça vous rappelle quelque chose?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VKHzxMjiq11h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def minkowski_mat(x, Y, p=2):\n",
        "    return (np.sum((np.abs(x - Y)) ** p, axis=1)) ** (1.0 / p)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y0csAL-Fq11l",
        "colab_type": "text"
      },
      "source": [
        "The function `conf_matrix` takes as input:\n",
        "\n",
        "- `testlabels` - test labels\n",
        "- `predlabels` - prediction labels\n",
        "and returns a table presenting the results.\n",
        "\n",
        "We initialize the matrix with zeros. Your job is to loop through the labels (true labels and predicted ones) to update the values of the matrix.\n",
        "\n",
        "<hr/>\n",
        "La fonction `conf_matrix` prend en entrée:\n",
        "\n",
        " - `testlabels` - les étiquettes de test\n",
        " - `predlabels` - les étiquettes prédites\n",
        "et retourne une table présentant les résultats.\n",
        "\n",
        "On initialise la matrice avec des zéros. Vous devrez passer sur les étiquettes de test et les étiquettes prédites pour mettre à jour les valeurs de la matrice."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HNXWb2ujq11n",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def conf_matrix(testlabels, predlabels):\n",
        "\n",
        "    n_classes = int(max(testlabels))\n",
        "    matrix = np.zeros((n_classes,n_classes))\n",
        "\n",
        "    for (test, pred) in zip(testlabels, predlabels):\n",
        "        matrix[int(test-1), int(pred -1)] += 1 \n",
        "\n",
        "    return matrix\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ToLwknviErZ6",
        "colab_type": "code",
        "outputId": "27778445-4dfd-46aa-9154-94341facb04a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        }
      },
      "source": [
        "a = ['a','b']\n",
        "for i in a:\n",
        "  print(i)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "a\n",
            "b\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VAkr5XMnq11s",
        "colab_type": "text"
      },
      "source": [
        "The function `gridplot` takes as input:\n",
        "\n",
        "- `classifier` - a classifier such as `NeighborhoodClassifier`\n",
        "- `train` - a training set\n",
        "- `test` - a test set\n",
        "- `n_points` - the width/height of the grid on which to visualize the decision boundary (n, n)\n",
        "\n",
        "Depending on the speed of your computer, calculating of predictions on the grid can be slow. We recommend doing the first tests with a small grid (say, 25 by 25). You could then augment the size of the grid to 50x50 or even 100x100 to obtain better looking visualizations.\n",
        "\n",
        "<hr/>\n",
        "\n",
        "La fonction `gridplot` prend en entrée:\n",
        "\n",
        " - `classifier` - un classifieur tel que `NeighborhoodClassifier`\n",
        " - `train` - un ensemble d'entraînement\n",
        " - `test` - un ensemble de test\n",
        " - `n_points` - la taille de la grille pour afficher la surface de décision (n,n)\n",
        "\n",
        "Dépendamment de la puissance de calcul de votre ordinateur, le calcul des prédictions sur la grille peut être lent. Il est préférable de faire vos premiers tests avec une grille moins fine, disons de 25 par 25. Vous pourrez ensuite augmenter la valeur à 50 ou même 100 pour obtenir de plus beaux graphiques."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nvngYoRyq11u",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# function plot\n",
        "def gridplot(classifier, train, test, n_points=50):\n",
        "\n",
        "    train_test = np.vstack((train,test))\n",
        "    (min_x1,max_x1) = (min(train_test[:, 0]) - .25, max(train_test[:, 0]) + .25)\n",
        "    (min_x2,max_x2) = (min(train_test[:, 1]) - .25, max(train_test[:, 1]) + .25)\n",
        "\n",
        "    xgrid = np.linspace(min_x1, max_x1,num=n_points)\n",
        "    ygrid = np.linspace(min_x2, max_x2,num=n_points)\n",
        "\n",
        "    # calculates the cartesian product between two lists and stores the result in an array\n",
        "    thegrid = np.array(combine(xgrid, ygrid))\n",
        "\n",
        "    predictedClasses = classifier.compute_predictions(thegrid)\n",
        "\n",
        "    # The grid\n",
        "    plt.pcolormesh(xgrid, ygrid, predictedClasses.reshape((n_points, n_points)).T, cmap=plt.cm.cool, alpha=.1)\n",
        "    # Training data points\n",
        "    plt.scatter(train[:, 0], train[:, 1], c=train[:,-1], cmap=plt.cm.cool, marker='v', s=70, label='train')\n",
        "    # Test data points\n",
        "    plt.scatter(test[:, 0], test[:, 1], c=test[:,-1], cmap=plt.cm.cool, marker='s', s=70, label='test')\n",
        "\n",
        "    plt.legend()\n",
        "    plt.show()\n",
        "    \n",
        "# http://code.activestate.com/recipes/302478/\n",
        "def combine(*seqin):\n",
        "    '''returns a list of all combinations of argument sequences.\n",
        "    for example: combine((1,2),(3,4)) returns\n",
        "    [[1, 3], [1, 4], [2, 3], [2, 4]]'''\n",
        "    def rloop(seqin,listout,comb):\n",
        "        '''recursive looping function'''\n",
        "        if seqin:                       # any more sequences to process?\n",
        "            for item in seqin[0]:\n",
        "                newcomb=comb+[item]     # add next item to current comb\n",
        "                # call rloop w/ rem seqs, newcomb\n",
        "                rloop(seqin[1:], listout, newcomb)\n",
        "        else:                           # processing last sequence\n",
        "            listout.append(comb)        # comb finished, add to list\n",
        "    listout=[]                      # listout initialization\n",
        "    rloop(seqin,listout,[])         # start recursive process\n",
        "    return listout"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Te_pw7u3q11x",
        "colab_type": "text"
      },
      "source": [
        "## NeighborhoodClassifier Class"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ME0KoSbrq11y",
        "colab_type": "text"
      },
      "source": [
        "The class `NeighborhoodClassifier` takes as parameters:\n",
        "\n",
        "- `parzen` - if set to True, the classifier is a Parzen windows one ; otherwise, the classifier is KNN\n",
        "- `dist_func` - a function to calculate the distance between points\n",
        "- `k` - the number of neighbors to visit (For knn only)\n",
        "- `radius` - the radius that defines the Parzen Windows (For Parzen windows only)\n",
        "\n",
        "The method `train` is actually really only storing the dataset. All of the work is done at prediction time for `NeighborhoodClassifier`  models.\n",
        "\n",
        "The method `compute_predictions` takes as input the unlabeled test set in matrix form and returns the array containing the predictions. The returned array is one-dimensional and has `n_examples` elements.\n",
        "\n",
        "You will need, for each test set example, to:\n",
        "\n",
        " - **Calculate distances** for every point of the training set (using dist_func)\n",
        " - Look through the distances to **find the $k$ nearest neighbors** (or **find the training points belonging to the ball of the wanted radius** in the case of a Parzen windows classifier) of the current test example\n",
        " - **Calculate the number of neighbors per class** and save them in `counts`\n",
        " - **Evaluate the predicted class** from `counts` and save it in `classes_pred`\n",
        " \n",
        "\n",
        "For Parzen classifiers, sometimes the test example is far from train examples, and the list of neighbors would then be empty. **One way to deal with such test examples is to double the radius until the list of neighbors contains at least one element.** Randomly selecting the label for such test examples is a common alternative.\n",
        "\n",
        "<hr/>\n",
        "\n",
        "La classe `NeighborhoodClassifier` prend en paramètre:\n",
        "\n",
        "- `parzen` - si ce booléen est True, alors le classifieur implémente la méthode de Parzel; sinon, il implémente k-ppv. \n",
        " - `dist_func` - une fonction pour calculer la distance des points\n",
        " - `k` - le nombre de voisin à visiter (Pour k-ppv seulement)\n",
        " - `radius` - le rayon qui définit les fenêtres de Parzen (Pour Parzen seulement)\n",
        "\n",
        "La méthode `train` n'est en fait que le stockage de l'ensemble d'entraînement. Tout le travail des modèles `NeighborhoodClassifier` s'effectue lors de la prédiction. \n",
        "\n",
        "La méthode `compute_predictions` prend en entré une matrice de données de test (sans étiquettes) et retourne une liste uni-dimensionnelle de taille `n_examples` contenant les prédictions.\n",
        "\n",
        "Vous devrez pour chaque point de l'ensemble de test :\n",
        "\n",
        " - **calculer les distances** à tous les points de l'ensemble d'entraînement (en utilisant dist_func)\n",
        " - parcourir les distances pour **trouver les $k$ voisins** du point de test courant (ou **trouver les points appartenant à la boule du rayon donné** dans le cas de la méthode de Parzen)\n",
        " - **dénombrer les voisins** correspondant à chaque classe et les sauvegarder dans `counts`\n",
        " - **évaluer l'étiquette prédite** à partir de `counts`, et la sauvegarder dans `classes_pred`\n",
        "\n",
        "Pour la méthode de Parzen, il arrive que l'exemple test soit loin des exemples d'entraînement, rendant ainsi la liste des voisins vide. **Une façon de contourner le problème serait de doubler le rayon jusqu'à ce que la liste des voisins contienne au moins un élément**. Une solution alternative serait d'assigner une étiquette de façon aléatoire à ces éléments-là.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kiDBPHnsq111",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class NeighborhoodClassifier:\n",
        "    def __init__(self, parzen=False, dist_func=minkowski_mat, k=1, radius=0.4):\n",
        "        self.parzen = parzen\n",
        "        self.dist_func = dist_func\n",
        "        self.k = k\n",
        "        self.radius = radius\n",
        "\n",
        "    # The train function for knn / Parzen windows is really only storing the dataset\n",
        "    def train(self, train_inputs, train_labels):\n",
        "        self.train_inputs = train_inputs\n",
        "        self.train_labels = train_labels\n",
        "        self.n_classes = len(np.unique(train_labels))\n",
        "\n",
        "    # The prediction function takes as input test_data and returns an array containing the predicted classes. \n",
        "    def compute_predictions(self, test_data):\n",
        "        # Initialization of the count matrix and the predicted classes array\n",
        "        num_test = test_data.shape[0]\n",
        "        counts = np.ones((num_test, self.n_classes))\n",
        "        classes_pred = np.zeros(num_test)\n",
        "\n",
        "        # For each test datapoint\n",
        "        for (i, ex) in enumerate(test_data):\n",
        "            pass\n",
        "\n",
        "            # i is the row index\n",
        "            # ex is the i'th row\n",
        "\n",
        "            # Find the distances to each training set point using dist_func\n",
        "            # ---> Write code here \n",
        "            \n",
        "            distance = self.dist_func(ex, self.train_inputs)\n",
        "            \n",
        "            \n",
        "            # Go through the training set to find the neighbors of the current point (ex)\n",
        "            # You will distinguish between Parzen and KNN here\n",
        "            if parzen:\n",
        "              n = [d for d in range(len(distance)) if distance[d] <= radius]  \n",
        "            else:\n",
        "              n = np.argsort(distance)[:self.k]\n",
        "            \n",
        "                \n",
        "            # Calculate the number of neighbors belonging to each class and write them in counts[i,:]\n",
        "            # ---> Write code here\n",
        "            cl_neighbors = self.train_labels[n]\n",
        "            for j in range(len(cl_neighbors)):\n",
        "              counts[i, cl_neighbors[j] -1] += 1\n",
        "            # From the counts matrix, define classes_pred[i] (don't forget that classes are labeled from 1 to n)\n",
        "            # ---> Write code here\n",
        "            classes_pred[i] = np.argmax(counts[i,:]) + 1\n",
        "            \n",
        "        return classes_pred"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LnHJmW5kq113",
        "colab_type": "text"
      },
      "source": [
        "## Loading and splitting the data / Chargement et division des données"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mbMVHGVsq115",
        "colab_type": "text"
      },
      "source": [
        "The `iris` dataset is divided into two parts, one for training and the other for testing.\n",
        "It is important to shuffle randomly the dataset before splitting it. Can you tell why?\n",
        "\n",
        "Only two columns of the dataset are used for this lab (the goal is to visualize them in 2-dimensions).\n",
        "\n",
        "<hr/>\n",
        "\n",
        "L'ensemble de donnée `iris` est divisé en deux parties, une pour l'entraînement et l'autre pour éffectuer des tests. Il est important de mélanger aléatoirement l'ensemble de données avant d'éffectuer la division. Pouvez-vous dire pourquoi? \n",
        "\n",
        "Seulement deux colonnes des données sont utilisées dans cette démo (afin de pouvoir les visualiser en deux dimensions)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ensHg-diq116",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# load iris\n",
        "if IN_COLAB:\n",
        "  iris = np.loadtxt('http://www.iro.umontreal.ca/~dift3395/files/iris.txt')\n",
        "else:\n",
        "  iris = np.loadtxt('iris.txt')\n",
        "data = iris\n",
        "\n",
        "# Number of classes\n",
        "n_classes = 3\n",
        "# Size of training set\n",
        "n_train = 100\n",
        "\n",
        "# The columns (features) on which to train our model\n",
        "# For gridplot to work, len(train_cols) should be 2\n",
        "train_cols = [0, 1]\n",
        "# The index of the column containing the labels\n",
        "target_ind = [data.shape[1] - 1]\n",
        "\n",
        "# Comment to have random (non-deterministic) results\n",
        "random.seed(3395)\n",
        "# Randomly choose indexes for the train and test dataset\n",
        "inds = list(range(data.shape[0]))\n",
        "random.shuffle(inds)\n",
        "train_inds = inds[:n_train]\n",
        "test_inds = inds[n_train:]\n",
        "\n",
        "# Split the data into both sets\n",
        "train_set = data[train_inds, :]\n",
        "train_set = train_set[:, train_cols + target_ind]\n",
        "test_set = data[test_inds, :]\n",
        "test_set = test_set[:, train_cols + target_ind]\n",
        "\n",
        "# Separate the test set into inputs and labels\n",
        "test_inputs = test_set[:, :-1]\n",
        "test_labels = test_set[:, -1].astype('int32')\n",
        "train_inputs = train_set[:, :-1]\n",
        "train_labels = train_set[:, -1].astype('int32')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rsiIojpgq11_",
        "colab_type": "text"
      },
      "source": [
        "## Initialization and training of the classifiers / Initialisation et entraînement des classifieurs\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7Us0QK0eq12A",
        "colab_type": "code",
        "outputId": "47a50ad1-57fe-41bb-f32b-cef9e93c13b1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        }
      },
      "source": [
        "# Number of neighbors (k) for knn\n",
        "k = 3\n",
        "radius = 0.9\n",
        "print(\"We will train \", k, \"-NN and a Parzen classifier with radius \", radius, \" on \", n_train, \" training examples\")\n",
        "\n",
        "# Create the classifiers\n",
        "knn = NeighborhoodClassifier(parzen=False, dist_func=minkowski_mat, k=k)\n",
        "parzen = NeighborhoodClassifier(parzen=True, dist_func=minkowski_mat, radius=radius)\n",
        "\n",
        "# We train the models\n",
        "knn.train(train_inputs, train_labels)\n",
        "parzen.train(train_inputs, train_labels)\n",
        "\n",
        "# We get predictions\n",
        "t1 = time.clock()\n",
        "classes_pred_knn = knn.compute_predictions(test_inputs)\n",
        "t2 = time.clock()\n",
        "print('It took knn ', t2 - t1, ' seconds to get the predictions on ', test_inputs.shape[0],' test set examples')\n",
        "t1 = time.clock()\n",
        "classes_pred_parzen = parzen.compute_predictions(test_inputs)\n",
        "t2 = time.clock()\n",
        "print('It took Parzen ', t2 - t1, ' seconds to get the predictions on ', test_inputs.shape[0],' test set examples')"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "We will train  3 -NN and a Parzen classifier with radius  0.9  on  100  training examples\n",
            "It took knn  0.009703999999999713  seconds to get the predictions on  50  test set examples\n",
            "It took Parzen  0.010421000000000014  seconds to get the predictions on  50  test set examples\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DEqE7Yxgq12E",
        "colab_type": "text"
      },
      "source": [
        "## Confusion matrix and decision boundary / Matrice de confusion et surface de décision"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q3kAtk_oq12G",
        "colab_type": "text"
      },
      "source": [
        "Here we define a function that given a model and a prediction array, prints the confusion matrix, which is very useful for analyzing which classes our classifier is having a hard time predicting. It also creates a graph displaying the training points as well as the test points and the decision boundary of our model. We try this function on the predictions made by both classifiers. We run this function on the two classifiers we trained in the previous section.\n",
        "\n",
        "Before moving on to the next section, please make sure that your implementation works well by executing this code. Do not hesitate to ask questions if you have trouble interpreting the confusion matrix or the graph.\n",
        "\n",
        "<hr/>\n",
        "\n",
        "On définit ici une fonction qui prend en paramètre un modèle et ses prédiction et imprime la matrice de confusion, très utile pour comprendre quelles classes sont moins bien prédites par notre classifieur. Elle crée aussi un graphique qui affiche les points d'entraînement ainsi que ceux de test et la surface de décision de notre modèle. On exécute cette fonction sur les deux classifieurs entraînés à la section précédente.\n",
        "\n",
        "Avant de passer à la section suivante, assurez-vous que votre implémentation fonctionne bien en exécutant ce code. N'hésitez surtout pas à poser des questions si vous avez de la difficulté à interpréter la matrice de confusion et le graphique."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wRNZpR7Tq12G",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def show_results(model, classes_pred):\n",
        "    # Confusion Matrix\n",
        "    confmat = conf_matrix(test_labels, classes_pred)\n",
        "    print('The confusion matrix is:')\n",
        "    print(confmat)\n",
        "\n",
        "    # Test error\n",
        "    sum_preds = np.sum(confmat)\n",
        "    sum_correct = np.sum(np.diag(confmat))\n",
        "    print(\"The test error is \", round(100 * (1.0 - (float(sum_correct) / float(sum_preds))), 2), \"%\")\n",
        "\n",
        "    # The grid size will be = grid_size x grid_size\n",
        "    grid_size = 200\n",
        "\n",
        "    if len(train_cols) == 2:\n",
        "        # Decision boundary\n",
        "        t1 = time.clock()\n",
        "        gridplot(model, train_set, test_set, n_points=grid_size)\n",
        "        t2 = time.clock()\n",
        "        print('It took ', round(t2 - t1, 2), ' seconds to calculate the predictions on', grid_size * grid_size,\n",
        "              ' points of the grid')\n",
        "        if model.parzen:\n",
        "            filename = 'grid_' + '_radius=' + str(model.radius) + '_c1=' + str(train_cols[0]) + '_c2=' + str(\n",
        "                train_cols[1]) + '.png'\n",
        "        else:\n",
        "            filename = 'grid_' + '_k=' + str(model.k) + '_c1=' + str(train_cols[0]) + '_c2=' + str(\n",
        "                train_cols[1]) + '.png'\n",
        "        print('We will save the plot into {}'.format(filename))\n",
        "        plt.savefig(filename, format='png')\n",
        "    else:\n",
        "        print('Too many dimensions (', len(train_cols), ') to print the decision boundary')\n",
        "\n",
        "show_results(knn, classes_pred_knn)\n",
        "show_results(parzen, classes_pred_parzen)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F49eVeWBq12J",
        "colab_type": "text"
      },
      "source": [
        "## Trying different values of k for k-NN / Essayez differentes valeurs de $k$ pour k-NN\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iglWTc3lq12K",
        "colab_type": "text"
      },
      "source": [
        "Now that your implementation is correct, we can train different k-NN classifiers, and choose the best value for $k$. The way we are going to do this is to plot the test error as a function of $k$, and use the plot to pick the best value. However, this method has a shortcoming (**what is it?**), and one way to mitigate it is to use a validation set. You will have the opportunity in the next section to try using it.\n",
        "\n",
        "You will need to fill in the following `get_test_error`.\n",
        "\n",
        "This function takes as input `k`, and returns the test error of a k-NN classifier. You will need to instantiate the classifier, train it, compute the predictions on the `test_inputs`, compute the confusion matrix, and use it to get the test error.\n",
        "\n",
        "<hr/>\n",
        "\n",
        "Maintenant que votre code marche bien, on peut entraîner différents classifieurs k-ppv, et choisir la meilleure valeur pour $k$. Nous allons tracer l'erreur de test en fonction de $k$, et nous utiliserons la courbe obtenue pour choisir la meilleure valeur. Cependant, cette méthode a un gros défaut (**c'est quoi?**), et une façon de mitiger cette imperfection est d'utiliser un ensemble de validation. Vous aurez l'opportunité d'essayer cela dans la prochaine section.\n",
        "\n",
        "Vous devez remplir la fonction `get_test_error`.\n",
        "\n",
        "Cette fonction prend en entrée `k`, et retourne l'erreur de test d'un classifieur k-ppv. Vous devez instancier le classifieur, l'entraîner, calculer les prédictions sur les données de test (`test_inputs`), calculer la matrice de confusion, et l'utiliser pour obtenir l'erreur de test."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gb9p5IVRq12M",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_test_error(k):\n",
        "    # ---> Write code here \n",
        "    pass"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8JsAY52Iq12P",
        "colab_type": "text"
      },
      "source": [
        "Using the function `get_test_error`, we will plot the test error against the values of $k$ from 1 to 100 (remember that there are 100 training examples).\n",
        "\n",
        "<hr/>\n",
        "\n",
        "En utilisant la fonction `get_test_error`, on trace la courbe de l'erreur de test en fonction de $k$, pour $k$ allant de 1 à 100 (100 étant la taille de l'ensemble d'entraînement)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cM1rAlPOq12Q",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "plt.plot(range(1, 100), [get_test_error(k) for k in range(1, 100)], label='test error')\n",
        "plt.legend()\n",
        "plt.xlabel('number of neighbors')\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZPamvznSq12V",
        "colab_type": "text"
      },
      "source": [
        "## Experimenting / Expérimentations"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nPgFdHnPq12X",
        "colab_type": "text"
      },
      "source": [
        "Now that everything is working properly, it is time to play with the model in order to better understand the different parameters. Work directly with the code above to run these tests.\n",
        "\n",
        "- Try different values for the radius of the Parzen windows classifier, and plot a similar figure than the one you made in the previous section. Which of the two algorithms is more robust to its hyperparameter on this dataset?\n",
        "\n",
        "- Vary the size of `train_set` and `test_set` and observe the impact that it has on the test error and the decision boundary\n",
        "\n",
        "- Divide the training set into 3 parts: `train_set`, `valid_set` and `test_set` (of size 100, 25 and 25, for example). Train $k$-nn on `train_set`, then choose the optimal $k$ using the `valid_set` and finally obtain an estimate of the generalization error of your model by testing on `test_set`. This time, use all 4 features of the dataset. What do you think the validation set is used for?\n",
        "  - Is there a difference between the validation error and the test error for the optimal $k$ found using the validation set? Should there be?\n",
        "\n",
        "- Uncomment the line `random.seed(3395)` and run your code multiple times to get statistics on the validation and test errors. You can write a `for` loop to execute the same piece of code multiple times; 10 times should be enough. Calculate the mean and standard deviation for each error.\n",
        "\n",
        "Do not hesitate to validate your answers by asking questions.\n",
        "\n",
        "<hr/>\n",
        "\n",
        "Maintenant que tous fonctionne, il est temps de faire des expérimentations pour mieux comprendre l'importance de différents facteurs. Travaillez directement sur le code précédent pour effectuer ces tests. \n",
        "\n",
        "- Essayez différentes valeurs du rayon de la méthode de Parzen, et tracez une courbe similaire à celle obtenue à la section précédente. Lequel des deux algorithmes est plus rabuste à son hyperparamètre sur cet ensemble de données?\n",
        "\n",
        "- Variez les tailles de `train_set` et `test_set` et observez l'impact sur l'erreur de test et la surface de décision\n",
        "\n",
        "- Divisez l'ensemble d'entrainement en 3 parties: `train_set`, `valid_set` et `test_set` (de taille 100, 25 et 25, par exemple). Entrainez $k$-ppv sur `train_set`, choisissez la valeur optimale de `k` en testant sur `valid_set` et obtenez un estimé de l'erreur de généralisation en testant sur `test_set`. Cette fois-ci, utilisez tous les (quatre) traits/caractéristiques/features. D'après-vous, à quoi sert l'ensemble de validation?\n",
        "  - Est-ce qu'il y a un écart entre l'erreur de validation et l'erreur de test pour le $k$ optimal trouvé avec l'ensemble de validation? Est-ce qu'il devrait y en avoir? \n",
        "- Décommentez la ligne `random.seed(3395)` et roulez votre code plusieurs fois pour obtenir des statistiques sur les erreurs de validation et de test. Vous pouvez écrire une boucle `for` qui exécute le même code plusieurs fois; 10 fois devrait suffire. Calculez l'écart-type et la moyenne de chaque erreur.\n",
        "\n",
        "N'hésitez pas à valider vos réponses en posant des questions."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qQZGsoagMSdd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}