01b_feature_based_learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Music Machine Learning - feature-based mining (nearest neighbors)\n",
    "\n",
    "### Author: Philippe Esling (esling@ircam.fr)\n",
    "\n",
    "In this course we will cover\n",
    "1. A [quick recap](#recap) on the idea of feature-based learning\n",
    "2. An introduction to [Nearest Neighbors](#nn) for querying\n",
    "3. An implementation of [classification](#classification) using k-NN\n",
    "4. A discussion on the [evaluation](#evaluation) of classification results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"recap\"> </a>\n",
    "\n",
    "## Feature-based learning\n",
    "\n",
    "This tutorials corresponds to the same slides following the introductory developments performed in the [previous tutorial](01a_machine_learning.ipynb). As we have seen previously, we can compute a whole set of features out of audio waveforms. These features were used in the traditional approaches of machine learning, which performed _feature-based learning_. If we look at the space induced by these features, we can clearly see that similar examples are somewhat grouped together.\n",
    "\n",
    "<img src=\"images/01_knn_space.png\" align=\"center\"/>\n",
    "\n",
    "Therefore, a naive way to approach the problem would be to look at examples in our training set that are near a new (unseen) file. Based on the features computed, we will implement a simple *querying* and *classification* system based on [Nearest Neighbors](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "from matplotlib import gridspec\n",
    "from mpl_toolkits.mplot3d import Axes3D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"nn\"> </a>\n",
    "## Nearest-neighbors\n",
    "\n",
    "In this tutorial, we will cover the simplest querying and classification algorithm, namely the *$k$-Nearest Neighbor* method. The idea is for a given (usually *unknown*) element, to find its closest neighbor(s), based on the distances between this element and the known dataset for a given set of features. Formally, given a set of elements $e_{i}$, $i\\in\\left[1,N\\right]$ and their corresponding features $\\mathbf{f_{i,m}}\\in\\mathbb{R}^{d}$ (which denotes the $m^{th}$ feature of the $i^{th}$ element, which can be $d$-dimensional), we will need to compute a distance measure $\\mathcal{D}\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)$ between the features of elements of the dataset. This distance will express the dissimilarity between two features. For the first two questions of the tutorial, we will simply consider that the dissimilarity between features is expressed by their Euclidean $(l_{2})$ distance.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\mathcal{D}\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)=\\sqrt{\\sum_{d=1}^{D}\\left(f_{i,m}^{d}-f_{j,m}^{d}\\right)^{2}}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "Given distances for each feature, we need to *merge* these various dissimilarities and then select the nearest neighbor of a particular element by computing\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "kNN\\left(e_{i}\\right)=\\overset{k}{\\underset{j\\neq i}{argmin}}\\left(\\frac{1}{M}\\sum_{m=1}^{M}\\left(\\mathcal{D}\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)\\right)\\right)\n",
    "\\end{equation}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "**Questions**  \n",
    "\n",
    "  1. What problems can arise from $n$-dimensional audio features?\n",
    "  2. Based on the selection equation, what constraints are implicitly made on the distances?\n",
    "  3. Does the Euclidean distance seems like a sound way to measure the similarity between temporal features?\n",
    "  \n",
    "***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper_data import import_dataset, compute_transforms, compute_features\n",
    "class_path = 'data/classification'\n",
    "# 0.1 - Import the classification dataset\n",
    "data_struct = import_dataset(class_path, 'classification')\n",
    "# 0.2 - Pre-process the audio to obtain spectral transforms \n",
    "data_struct = compute_transforms(data_struct)\n",
    "# 0.3 - Compute a set of temporal and spectral features\n",
    "data_struct = compute_features(data_struct)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Querying \n",
    "\n",
    "First, we can use the nearest-neighbor idea to devise a very simple *querying* system. This type of method is typically used in many systems such as *Query By Humming (QBH)* softwares (similar to [Shazam](http://www.shazam.com/)). As previously, we provide a baseline code in the main script. First, we create a $ N \\times M $ distance matrix `data_matrix` corresponding to the $M$ features of the $ N $ elements of the datasets. We selected here only the *spectral_centroid_mean, SpectralFlatnessMean* and *SpectralSkewnessMean* features. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "used_features = ['spectral_centroid_mean', 'loudness_mean', 'spectral_contrast_mean']\n",
    "# Create a data matrix only from selected features\n",
    "data_matrix = np.zeros((len(data_struct[\"filenames\"]), len(used_features)))\n",
    "for f in range(len(used_features)):\n",
    "    data_matrix[:, f] = data_struct[used_features[f]]\n",
    "# Avoid NaN and inf values\n",
    "data_matrix = np.nan_to_num(data_matrix)\n",
    "# Normalize the matrix (unit-variance)\n",
    "for f in range(len(used_features)):\n",
    "    data_matrix[:,f] = (data_matrix[:, f] - np.mean(data_matrix[:, f])) / np.std(data_matrix[:, f])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, after your code is filled, the `dist` matrix should contain the mean distances (eventually, for various types of distances), which will then be sorted to the `nn_ids` vector allowing to select the nearest neighbors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "**Exercise**  \n",
    "\n",
    "  1. Compute the set of distances between a random element and the rest of the dataset.\n",
    "  2. Complete the plotting code in order to plot the element and its 10 nearest neighbors.\n",
    "  3. Check that you obtain plots similar to those displayed below.\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper_plot import hdr_plot_style\n",
    "hdr_plot_style()\n",
    "# Create a vector of colors\n",
    "color_vect = plt.cm.inferno_r.colors[1::10]\n",
    "# Q 1.1.1 - Perform some 10-NN queries and plot the result\n",
    "for test in range(10):\n",
    "    select_id = int(np.random.randint(low=0, high=len(data_struct[\"filenames\"]), size=1))\n",
    "    select_mask = [True] * len(data_struct[\"filenames\"])\n",
    "    select_mask[select_id] = False\n",
    "    tmp_copy = data_matrix[select_mask]\n",
    "    tmp_class = data_struct[\"classes\"][select_mask]\n",
    "    \n",
    "    ######################\n",
    "    # YOUR CODE GOES HERE\n",
    "    ######################\n",
    "    \n",
    "    # Performing a slightly complicated plot\n",
    "    fig = plt.figure(figsize=(12,8))\n",
    "    ax = fig.add_subplot(111, projection='3d')\n",
    "    for c in range(len(data_struct[\"class_names\"])):\n",
    "        cur_points = (data_struct[\"classes\"] == c);\n",
    "        curColor = color_vect[c]\n",
    "        s = ax.scatter(xs=data_matrix[cur_points, 0], ys=data_matrix[cur_points, 1], zs=data_matrix[cur_points, 2], s=80, c=np.array(curColor).reshape(1, -1));\n",
    "    s = ax.scatter(tmp_copy[nn_ids[:10], 0], tmp_copy[nn_ids[:10], 1], tmp_copy[nn_ids[:10], 2], s=100, linewidths=6, edgecolor='w');\n",
    "    s.set_edgecolors = s.set_facecolors = lambda *args:None\n",
    "    s = ax.scatter(data_matrix[select_id, 0], data_matrix[select_id, 1], data_matrix[select_id, 2], s=200, linewidths=6, edgecolor='w');\n",
    "    for t in range(10):\n",
    "        fD = (tmp_copy[nn_ids[t], :] - data_matrix[select_id, :]) * 4;\n",
    "        s = ax.text(tmp_copy[nn_ids[t], 0] + fD[0], tmp_copy[nn_ids[t], 1] + fD[1], tmp_copy[nn_ids[t], 2] + fD[2], data_struct[\"class_names\"][tmp_class[nn_ids[t]]], fontsize=22, fontweight='bold', horizontalalignment='center');\n",
    "        s.set_edgecolors = s.set_facecolors = lambda *args:None; s.set_zorder(200)\n",
    "        lines = ax.plot([tmp_copy[nn_ids[t], 0], tmp_copy[nn_ids[t], 0] + (fD[0] * 0.8)], [tmp_copy[nn_ids[t], 1], tmp_copy[nn_ids[t], 1] + (fD[1] * 0.8)], [tmp_copy[nn_ids[t], 2], tmp_copy[nn_ids[t], 2] + (fD[2] * 0.8)], linewidth=2, c='w')\n",
    "        for l in lines:\n",
    "            l.set_zorder(199)\n",
    "    ax.set_xlabel('Centroid'); ax.set_xlim(-2, 2); ax.set_ylabel('Loudness'); ax.set_ylim(-2, 3); ax.set_zlabel('Contrast'); ax.set_zlim(-3, 2); \n",
    "    ax.set_title('True class : ' + data_struct[\"class_names\"][data_struct[\"classes\"][select_id]]);\n",
    "    ax.dist = 10\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Going further\n",
    "\n",
    "Of course, based on the types of features, different distance measures can be used, such as any of the $l_{p}$ distances (a generalization of the Euclidean distance)\n",
    "\n",
    "$$\n",
    "l_{p}\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)=\\sqrt[p]{\\sum_{d=1}^{D}\\left|f_{i,m}^{d}-f_{j,m}^{d}\\right|^{p}}\n",
    "$$\n",
    "\n",
    "the *Cosine* distance\n",
    "\n",
    "$$\n",
    "cosine\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)=1-\\frac{\\mathbf{f_{i,m}}\\cdot\\mathbf{f_{j,m}}}{\\left\\Vert \\mathbf{f_{i,m}}\\right\\Vert \\left\\Vert \\mathbf{f_{j,m}}\\right\\Vert }=1-\\frac{\\sum_{d=1}^{D}f_{i,m}^{d}f_{j,m}^{d}}{\\sum_{d=1}^{D}\\left(f_{i,m}^{d}\\right)^{2}\\sum_{d=1}^{D}\\left(f_{j,m}^{d}\\right)^{2}}\n",
    "$$\n",
    "\n",
    "or the *correlation* distance.\n",
    "\n",
    "$$\n",
    "correlation\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)=1-\\frac{\\mathbf{\\left(f_{i,m}-\\mu_{\\mathbf{f_{i,m}}}\\right)}\\cdot\\left(\\mathbf{f_{j,m}}-\\mu_{\\mathbf{f_{j,m}}}\\right)}{\\left\\Vert \\mathbf{f_{i,m}-\\mu_{\\mathbf{f_{i,m}}}}\\right\\Vert \\left\\Vert \\mathbf{f_{j,m}}-\\mu_{\\mathbf{f_{j,m}}}\\right\\Vert }\n",
    "$$\n",
    "\n",
    "The same observation holds for the way we decided to \"merge\" the different distances. By looking at these given definitions, start by thinking about the following questions.\n",
    "\n",
    "***\n",
    "\n",
    "**Exercise**\n",
    "\n",
    "  4. Implement the $l_{p}$, *Cosine* and *correlation* distances\n",
    "  5. Try the same piece of code by varying the distances and the `used_features`.\n",
    "  6. What can you tell about the discriminative power of features?\n",
    "  7. What other steps should we perform on the features?\n",
    "  8. (Optional) Extend your code to include temporal features\n",
    "  9. (Optional) Extend your code to a fully functional *Query-By-Example* (QBE) system.\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "######################\n",
    "# YOUR CODE GOES HERE\n",
    "######################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"classification\"> </a>\n",
    "## Classification\n",
    "\n",
    "For the second part of this tutorial, we will rely on the same technique (computing the distance of a selected point to the rest of the dataset) in a *classification* framework. The overarching idea behind $k$-NN classification is that elements from a same class should have similar properties in the *feature space*. Hence, the closest feature to those of an element should be from elements of its right class. These types of approaches are usually termed as *distance-based* classification methods. The skeleton for this algorithm is provided in the `knn_classify` function.\n",
    "\n",
    "```Python\n",
    "def knn_classify(data_struct, test_sample, k, normalize, useL1dist):\n",
    "    \"\"\"\n",
    "    % This function is used for classifying an unknown sample using the kNN\n",
    "    % algorithm, in its multi-class form.\n",
    "    %\n",
    "    % Arguments :\n",
    "    % - data_struct  : the data structure\n",
    "    % - test_sample  : the input sample id to be classified\n",
    "    % - k           : the k (number of neighbors) parameter\n",
    "    % - dist_type    : type of distance ['Euclidean', 'Manhattan', 'Cosine'] (optional)\n",
    "    % - normalize   : use class priors to weight results (optional)\n",
    "    % Returns :\n",
    "    % - probas      : an array that contains the classification probabilities for each class\n",
    "    % - winner_class : the label of the winner class\n",
    "    \"\"\"\n",
    "    return probas, winner_class\n",
    "```\n",
    "\n",
    "The algorithm will globally look quite similar to the previous one. However, this time we will compute the $k$ Nearest Neighbors *for each of the classes separately*, which will allow to consider the resulting distance vectors as probabilities. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, we will compute for the set of classes $\\mathcal{C}_{t}$ the vector of distances, and select the $k$ closest elements per class.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "kNN_{\\mathcal{C}_{t}}\\left(e_{i}\\right)=\\overset{k}{\\underset{j\\in\\mathcal{C}_{t} \\wedge j\\neq i}{argmin}}\\left(\\frac{1}{M}\\sum_{m=1}^{M}\\left(\\mathcal{D}\\left(\\mathbf{f_{i,m}},\\mathbf{f_{j,m}}\\right)\\right)\\right)\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "Then, in order to consider the distances as probabilities, we compute for each class the mean distance of its $k$ nearest neighbors and normalize these distances across classes\n",
    "\n",
    "$$\n",
    "p_{\\mathcal{C}_{t}}\\left(e_{i}\\right)=\\frac{1}{k}\\sum_{j=1}^{k}kNN_{\\mathcal{C}_{t}}\\left(e_{i}\\right)\n",
    "$$\n",
    "\n",
    "In the `knn_classify` function, we store in `testFeatures` the vector of features from the element we are trying to classify, and construct a cell of features for each class in the `class_feats` cell."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "**Exercise**  \n",
    "\n",
    "  1. Update the `knn_classify` code to perform the basic k-NN classification function\n",
    "  2. Run the algorithms for both 1-NN and 5-NN evaluation\n",
    "  3. Plot the different confusion matrix to visually check the accuracies (you should obtain the values displayed in the following figure).\n",
    "  4. Extend the code to take various distances into account (argument `dist_type`)\n",
    "  5. What is the use of \"class weighting\" (argument `normalize`)?\n",
    "  6. Implement the class weighting system and evaluate its effect\n",
    "  4. Perform the same classification with various K and features to evaluate the properties and qualities of different parametrizations.\n",
    "  5. (Optional) Automatize the evaluation of various configurations.\n",
    " \n",
    "***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%%\n",
    "# 1.2 - K-Nearest Neighbors classification based on static properties\n",
    "#\n",
    "nb_classes = len(data_struct[\"class_names\"])\n",
    "nb_files = len(data_struct[\"filenames\"])\n",
    "correct_elements_5NN = 0\n",
    "confusion_matrix_5NN = np.zeros((nb_classes, nb_classes))\n",
    "probas_matrix_5NN = np.zeros((nb_files, nb_classes))\n",
    "\n",
    "#\n",
    "# function [probas, winner_class] = knn_classify(data_struct, test_sample, k, normalize, useL1dist);\n",
    "# \n",
    "def knn_classify(data_struct, test_sample, usedFeatures, k=1, dist_type='Euclidean', normalize=0):\n",
    "    # Keep the number of classes\n",
    "    n_classes = len(data_struct[\"class_names\"]);\n",
    "    # Initialization of class properties\n",
    "    n_dims = np.zeros(n_classes)\n",
    "    n_samples = np.zeros(n_classes)\n",
    "    class_feats = [];\n",
    "    # Create a data matrix with the features of all data\n",
    "    data_matrix = np.zeros((len(data_struct[\"filenames\"]), len(usedFeatures)))\n",
    "    for f in range(len(usedFeatures)):\n",
    "        data_matrix[:, f] = np.array(data_struct[used_features[f]]);\n",
    "        # Remove NaN and Inf\n",
    "        data_matrix[:, f] = np.nan_to_num(data_matrix[:, f])\n",
    "        data_matrix[:, f] = data_matrix[:, f] / np.max(data_matrix[:, f])\n",
    "    # Retrieve the features of the test samples\n",
    "    testFeatures = data_matrix[test_sample, :]\n",
    "    # dist{i} will the vector of distance of the testing sample to all the samples of i-th class\n",
    "    dist = []\n",
    "    # We create a vector of \"inf\" distances for each class and a cell of features\n",
    "    for i in range(n_classes):\n",
    "        # Retrieve the class points\n",
    "        cur_points = np.linspace(0, len(data_struct[\"classes\"])-1, len(data_struct[\"classes\"]), dtype=int)[data_struct[\"classes\"] == i]\n",
    "        # Eventually remove the current sample\n",
    "        cur_points = cur_points[cur_points != test_sample];\n",
    "        n_samples[i] = len(cur_points);\n",
    "        n_dims[i] = len(usedFeatures);\n",
    "        # Fill the dist cell with \"inf\" values\n",
    "        dist.append(np.inf * np.ones(int(np.max(n_samples))));\n",
    "        # Keep the cell of class features\n",
    "        class_feats.append(data_matrix[cur_points, :])\n",
    "        class_feats[i] = np.nan_to_num(class_feats[i])\n",
    "    # Compute the distance vectors for each class\n",
    "    for i in range(n_classes):\n",
    "        \n",
    "        #################\n",
    "        # YOUR CODE GOES HERE\n",
    "        #################   \n",
    "        \n",
    "    kAll = np.zeros((n_classes, 1))\n",
    "    # Compute the mean distance value for k neighbors\n",
    "    for j in range(k):\n",
    "        \n",
    "        #################\n",
    "        # YOUR CODE GOES HERE\n",
    "        #################\n",
    "        \n",
    "    # Normalize the class probabilities\n",
    "    \n",
    "    #################\n",
    "    # YOUR CODE GOES HERE\n",
    "    #################\n",
    "        \n",
    "    # Retrieve the winning class\n",
    "    \n",
    "    #################\n",
    "    # YOUR CODE GOES HERE\n",
    "    #################\n",
    "\n",
    "    return probas, winner_class\n",
    "\n",
    "# Q 1.2.1 Perform 1-NN and 5-NN classification\n",
    "for f in range(nb_files):\n",
    "    # Perform 5-NN classification\n",
    "    probas, winClass = knn_classify(data_struct, f, ['spectral_centroid_mean', 'loudness_mean', 'spectral_contrast_mean'], 5);\n",
    "    if (winClass == data_struct[\"classes\"][f]):\n",
    "        correct_elements_5NN = correct_elements_5NN + 1;\n",
    "    confusion_matrix_5NN[data_struct[\"classes\"][f], winClass] = confusion_matrix_5NN[data_struct[\"classes\"][f], winClass] + 1;\n",
    "    probas_matrix_5NN[f, :] = probas[0, :];\n",
    "# Q 1.2.3 - Plotting the confusion matrices\n",
    "plt.figure(figsize=(10, 8))\n",
    "plt.imshow(confusion_matrix_5NN)\n",
    "#plt.set_cmap(plt.jet)\n",
    "plt.title('1-NN Confusion')\n",
    "for c in range(confusion_matrix_5NN.shape[0]):\n",
    "    plt.text(c, c, '%.3f'%(confusion_matrix_5NN[c, c] / np.sum(confusion_matrix_5NN[c, :])), fontsize=22, fontweight='bold', color=[1, 0, 0], horizontalalignment='center');\n",
    "plt.yticks(range(len(data_struct[\"class_names\"])), data_struct[\"class_names\"])\n",
    "plt.xticks(range(len(data_struct[\"class_names\"])), data_struct[\"class_names\"]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"evaluation\"> </a>\n",
    "## Evaluation\n",
    "\n",
    "When proposing machine learning algorithms, the fundamental aspects lies in correctly evaluating their performances. Depending on the application, methods, dataset and even the nature of corresponding data, a plethora of evaluation measures can be used. We highly recommend the following articles for those interested in machine learning, so that you develop your critical mind and do not limit yourself to narrow evaluations (by relying on statistical tests) and also that you avoid **cherry picking**  \n",
    "\n",
    "  * Demšar, J. (2006).   *Statistical comparisons of classifiers over multiple data sets.*   The Journal of Machine Learning Research, 7, 1-30.   [PDF](http://machinelearning.wustl.edu/mlpapers/paper_files/Demsar06.pdf)  \n",
    "  * Sturm, B. L. (2013).   *Classification accuracy is not enough.*   Journal of Intelligent Information Systems, **41**(3), 371-406. [PDF](http://vbn.aau.dk/files/70797941/Sturm20121030.pdf)  \n",
    "  * Keogh, E., & Kasetty, S. (2003).   *On the need for time series data mining benchmarks: a survey and empirical demonstration.*   Data Mining and knowledge discovery, **7**(4), 349-371. [PDF](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.2240&rep=rep1&type=pdf)  \n",
    "\n",
    "However, for the scope of this tutorial, we will limit ourselves to typical measures minimally required to evaluate your classifier. Overall, the most important aspects of evaluation lies in different ways of comparing the *real labels* (ground truth) to the *assigned labels* (picked by the classifier).\n",
    "\n",
    "  * The **confusion matrix** is computed simply by counting the occurences in which a particular instance of a real label (row) is classified to an assigned label (column). This code is already provided in the starter code, and all the following measures can be derived directly from it.\n",
    "  * The **overall accuracy** is computed as the ratio of correctly classified examples divided by the complete number of examples.\n",
    "  * The (per-class) **precision** defines the ratio of examples correctly assigned to a class divided by the number of instances assigned to that class by the classifier.\n",
    "  * The (per-class) **recall** defines the ratio of examples correctly assigned to a class divided by the number of instances really belonging to that class.\n",
    "  * The **F1 measure** is defined as the ratio between the geometric and harmonic means between the precision and recall measures.\n",
    "\n",
    "You can implement these measures by simply completing the starter code. If you have doubts about the implementation of these measures, you can check the corresponding [Wikipedia article](https://en.wikipedia.org/wiki/Precision_and_recall)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "**Exercise**  \n",
    "\n",
    "  1. Implement the *accuracy*, *recall*, *precision* and *F1 measure*\n",
    "  2. Evaluate the previous algorithms with your new measures.\n",
    "  3. Perform an automatization of the previous evaluations.\n",
    "  4. Run the automatic evaluation for different K, distances and features.\n",
    "  5. Plot the corresponding results for comparison\n",
    "    \n",
    "***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%%\n",
    "# 1.3 - Evaluating classification accuracy with various measures\n",
    "#\n",
    "# Type of normalization\n",
    "normalizationMode = 2\n",
    "# number of classes\n",
    "nClasses = confusion_matrix_1NN.shape[0]\n",
    "# confusion matrix normalization:\n",
    "\n",
    "######################\n",
    "# YOUR CODE GOES HERE\n",
    "######################\n",
    "if (normalizationMode == 1): \n",
    "    print('Standard normalization')\n",
    "elif (normalizationMode == 2): \n",
    "    print('Row-wise normalization')\n",
    "else:         \n",
    "    print('No normalization')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute overal accuracy\n",
    "# compute class precision\n",
    "# compute class recall\n",
    "# compute class F1 measure\n",
    "\n",
    "maxK = 10\n",
    "classPrecisions = np.zeros((maxK, nClasses))\n",
    "classRecalls = np.zeros((maxK, nClasses))\n",
    "# Q 1.3.4 - Evaluate per-class precisions and recalls for various K\n",
    "for k in range(maxK):\n",
    "    confusionMatrix = np.zeros(nb_classes)\n",
    "    \n",
    "    ######################\n",
    "    # YOUR CODE GOES HERE\n",
    "    ######################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%% Plot the evaluations for different K\n",
    "\n",
    "######################\n",
    "# YOUR CODE GOES HERE\n",
    "######################"
   ]
  }
 ],
 "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.9.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}