ppcic_ml_knn.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ppcic-ml-knn.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyMmIyckOCbIVu0dXmS47Lyd",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/MLRG-CEFET-RJ/ml-class/blob/master/ppcic_ml_knn.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w96g8_ZaVNn3",
        "colab_type": "text"
      },
      "source": [
        "# Introduction\n",
        "\n",
        "The $k$ nearest neighbors ($k$-NN) algorithm is one of the simplest supervised learning methods. Despite being simple, it often produces satisfactory results. It can be used for both classification and regression problems.\n",
        "\n",
        "$k$-NN is said to be a *lazy learning* algorithm. This means the training phase consists only of storing the representations of the examples. That is, the algorithm does not explicitly produce a classification model. Another way to interpret this is that, in $k$-NN, the training set is the model.\n",
        "\n",
        "$k$-NN is a distance-based method, that is, it considers some metric to compute the distance between a given pair of examples. For this, $k$-NN interpret each example in the data matrix $X$ as a point in the $n$-dimensional space. Bellow, we give more details about this geometric interpretation of examples as points. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eheXoU_tR5tJ",
        "colab_type": "text"
      },
      "source": [
        "# Geometric interpretation of a dataset\n",
        "\n",
        "A common characteristic of many learning algorithms (for classification and for other tasks) is that they interpret each example in a dataset as a *geometric point*. See the following figure (taken from [here](https://www.mathplanet.com/education/geometry/points,-lines,-planes-and-angles/an-introduction-to-geometry)). \n",
        "\n",
        "![three points in 2D](https://www.mathplanet.com/Oldsite/media/43053/picture04.png)\n",
        "\n",
        "To get a sense of this interpretation, consider a ficticious dataset for binary classification with 17 examples. Furthermore, for simplicity´s sake, consider that each example has only two features, which means that each example is of the form $\\mathbf{x} = [x_1, x_2]$. The code cell below presents this dataset as two separated numpy arrays, $X$ and $y$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mFksDhm3UBAS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "\n",
        "X = np.array([[-0.1, 1.4],\n",
        "              [-0.5,-0.1],\n",
        "              [ 1.3, 0.9],\n",
        "              [-0.6, 0.4],\n",
        "              [-1.5, 0.4],\n",
        "              [ 0.2, 0.2],\n",
        "              [-0.3,-0.4],\n",
        "              [ 0.7,-0.8],\n",
        "              [ 1.1,-1.5],\n",
        "              [-1.0, 0.9],\n",
        "              [-0.5,-1.5],\n",
        "              [-1.3,-0.4],\n",
        "              [-1.4,-1.2],\n",
        "              [-0.9,-1.1],\n",
        "              [ 0.4,-1.3],\n",
        "              [-0.4, 0.6],\n",
        "              [ 0.3,-0.5]])\n",
        "\n",
        "y = np.array([0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RRXIv5AiUV-x",
        "colab_type": "text"
      },
      "source": [
        "Since each example is represented by a pair of numbers, we can plot these examples for visualization purposes."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i4ljwlU7TNWg",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 480
        },
        "outputId": "9a76b7a3-a260-4871-98bc-a3166ed26f66"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "plt.style.use('classic')\n",
        "np.set_printoptions(precision=3, suppress=True)\n",
        "\n",
        "colormap = np.array(['r', 'b'])\n",
        "\n",
        "def plot_scatter(X, y, colormap):\n",
        "  plt.grid()\n",
        "  plt.xlim([-2.0, 2.0])\n",
        "  plt.ylim([-2.0, 2.0])\n",
        "  plt.xlabel('$x_1$', size=20)\n",
        "  plt.ylabel('$x_2$', size=20)\n",
        "  plt.title('Input 2D points', size=18)\n",
        "  plt.scatter(X[:,0], X[:, 1], s=50, c=colormap[y])\n",
        "\n",
        "plot_scatter(X, y, colormap)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkkAAAHPCAYAAABHgU5sAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAMTQAADE0B0s6tTgAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOzdeVhUZfsH8C8Oy4AoqCmYlRtuRZKmuJSZaaGlUYmhaWoumUupU686lPWWuZAtktnruKSZmtiiiKZjlqbvm6gtoqaomKVlg4qCIAyDML8/Cn7CmUE8zszD4fl+rsvLi3POzNzfORd1e849z3ht377dDiIiIiIqo4boAoiIiIiqIjZJRERERA6wSSIiIiJygE0SERERkQNskoiIiIgcYJNERERE5ACbJCIiIiIH2CQREVVRFosFPXr0wJw5c0SXQiQlb9EFEJFr9OjRAwCwfft2wZVUzsCBAwEAa9asua7HHTx4EP/73/+wf/9+WCwW5OXloV69emjfvj2eeuopNGrUSPGYSZMmITU1tfTnGjVqICAgAHXq1EGzZs3QqVMn3H///fD397+xUFWY2vebSGZskohIU1577TVkZ2fjjjvuQK9evaDT6fDLL7/gq6++wrfffou3334bd9xxh8PHRkVFITQ0FHa7HXl5efjrr7/w008/4bvvvsOSJUvwr3/9C507d/ZwIuduuukmfPzxx6hZs6boUoikxCaJiDRlwIABePDBB3HTTTeV2b5y5UosXboU77zzDj766COHj+3duzfuuuuuMttsNhvWrl2LZcuW4dVXX8XcuXMRERHhtvqvh7e3N2677TbRZRBJi00SUTVmsVgwaNAgREVFYfjw4Vi0aBF+/PFH5Ofno2nTphg+fDi6dOlS5jFbtmxBfHw8pk6diqCgIKxatQonTpyAt7c32rdvj9GjR+OWW24p85iS21mObvVd/Xy9e/fG/v37MXny5NL9JbcJgb+v9EybNq3CTIMGDXK6feXKlTh58iSys7MRFBR0zfcHAHx9fTFkyBAUFhZixYoV+OCDD7B48eJrPu7q9/app57CokWLcODAARQWFiIsLAxDhw5Fx44dFY+z2Wz4/PPPsW3bNpw5cwY6nQ7NmzfH448/Xua9KP8aV78vc+bMgdlsxqeffoq9e/di/fr1+OOPPxAYGIiuXbviueeeQ2BgIABU+v0+cOAA1qxZg+PHjyM7OxuBgYEIDQ1Fp06dMGzYsEq9l0TVDZskIglkZGRg7NixaNiwIR566CFcunQJ27dvxyuvvIK3334b7dq1Uzxm165d2LNnD+69915ERETgxIkT2LlzJ/bv34/58+ervsIRGhqKYcOG4fPPPwcAxMTElO4LCwtTFxCAl5cXdDodAJT+fT1iY2ORmJiI9PR0nDx5Ek2bNq3U4/766y+MHz8ezZo1Q79+/ZCZmYnt27dj2rRpePnll/HAAw+UHltYWIgpU6YgNTUVt912Gx577DFYrVbs3LkTb7zxBtLT0zF69OhK17xw4UL88MMP6NKlCzp06ID9+/dj06ZNOHPmDN59910AlXu/9+7dC6PRiICAAHTt2hU33XQTcnJy8PvvvyMpKYlNEkmLTRKRBPbv34/hw4eX+Z9dz549MXXqVCQmJjpskr7//nvMmjWrzJWmzz//HAsWLMC8efNK/yd8vUJDQzF8+HBs2bIFADB8+HBVz1Pejh07kJeXh9tvv730Ksr1CAgIQMuWLXHw4EGkpaVVukk6cOAAYmNj8dxzz5Vue/zxxzF+/Hi899576NSpU+lM0dq1a5GamopOnTph5syZpc3csGHDMHbsWKxevRpdunRBeHh4pV77yJEjWLp0KUJCQgAARUVFMBgM+Pnnn3HkyBG0adOmUu/3xo0bUVxcjPfee0/RqGZnZ1eqFqLqiEsAEEkgJCQEQ4YMKbMtMjISISEhOHLkiMPHtGvXTnEr7vHHH8fNN9+Mn3/+GRaLxW31Xq+//voL8+fPh06nw7hx41Q/T8mcU1ZWVqUfU7NmTQwdOrTMtlatWqFXr17Izc3Frl27Srdv3rwZXl5eGDduXJmrXXXq1MHTTz8NANi0aVOlX3vo0KGlDRLw9xW03r17AwDS0tIq/Twl/Pz8FNsqe9uSqDpik0QkgbCwMIe3oOrXr4/c3FyHj3E0vKzT6XDnnXcCANLT011bpEoXL17E1KlTkZWVhQkTJjj9ZFtl2O12AH/fuqusli1bIiAgQLG9ZEC85H3Ky8vDn3/+iXr16jm8Vdm+ffsyx1dGq1atFNsaNGgAAMjJyan08/Tq1QsAMG7cOLz77rv49ttvce7cuUo/nqi64u02Igk4u/2k0+lQXFzscF+dOnUcbq9bty4AOG2uPOnixYswGAw4ffo0JkyYgMcee+yGni8zMxMAEBwcXOnHXOt9unz5cpm/69Wr5/D4ku3X8746Oq8lzbCz8+rIfffdh1mzZuGzzz7D5s2bkZycDODvBnD06NHo0KFDpZ+LqDphk0REDl28eNHh9gsXLgAo+z/oGjX+vihdVFSkuGLlrmYqMzMTL774Ik6dOoWJEyfecIOUl5eHY8eOAQDatGlT6cdd630qmUcq+btke3klDZqoNZG6dOmCLl26ID8/H0eOHMHu3buxYcMGxMXFYdGiRWjSpImQuohE4u02InLo6hWqSxQVFeHgwYMAyn4SraRhOnv2rOIxR48edfj8FV3FupZz585h0qRJOHXqFCZPnnzDDRLw90rUBQUFaNGiBRo3blzpxx07dgx5eXmK7fv37wfw/+9TQEAAbr75Zpw/fx5//PGH4viff/4ZANCiRQs15V9TZd9vf39/tG/fHuPHj8fgwYNRWFiIvXv3uqUmoqqOTRIROfTzzz9j9+7dZbatW7cOZ86cQbt27RAaGlq6veTKy8aNG8sc/+OPP+Lbb791+Py1a9dGVlYWCgoKrqsui8WCiRMn4syZM5gyZQr69et3XY8vz2azYeXKlVi1ahV8fHzw/PPPX9fjL1++jBUrVpTZdvToUWzbtg01a9ZEt27dSrf36dMHdrsdCxcuRFFRUen27OxsfPLJJwCAhx9++AbSOFfR+52amlqmnhIlV8kcDXQTyYC324jIoa5du2L69Om499570ahRI5w4cQJ79uxB7dq1MWnSpDLH9u7dG2vWrMHq1atx4sQJNGnSBKdPn8bevXtx7733YufOnYrnb9++PdLS0jBlyhRERETAx8cHzZs3R9euXSusa/LkybBYLGjZsiUsFguWL1+uOKZ3795lmrgSW7ZsKb3CU/K1JAcOHMClS5dQr149TJkypXQwvbLatm2LTZs24ciRIwgPDy9dJ8lut8NgMJS5fRYbG4u9e/fif//7H0aNGoVOnTqhoKAA3333HS5evIiBAwde9+tXVkXv9/z583H+/HmEh4cjNDQU3t7eOHbsGH7++WeEhISUWeuJSCZskojIoW7duqFv375YuXIl9uzZA51Oh27dumH06NG49dZbyxxbp04dzJs3DyaTCQcOHEBqaipatWqFuXPnwmKxOGyShgwZgtzcXHz//fc4dOgQiouLERUVdc0mqWTpgWPHjpXOEJV31113OWySzGYzgL9nqPz9/VG3bl20b98enTp1Qvfu3VV9wW3Dhg1hMBiwaNEibNiwAYWFhWjRogWGDh2KyMjIMsf6+Pjg7bffxtq1a/HNN99g3bp1pStujx8/Hj179rzu16+sit7vwYMH47///S+OHj2KH3/8ETVq1ECDBg0wePBgxMTEoFatWm6ri6gq89q+fbtddBFqLFq0CCkpKcjIyIBer8ddd92FMWPGlH781RGbzYYPP/wQ27dvR2FhISIiIjB58uQKH0Mkm/JfI0KOOfvKECKqPjQ7k+Tl5YWpU6di/fr1+PjjjwEAcXFxFT7mww8/xMGDB2EymfDZZ5+hVq1aePnll1UPjxIREVH1pdkmafTo0WjVqhV8fHwQGBiIQYMG4cSJE04XULPZbNiyZQueeeYZhIaGombNmhg/fjxOnjyJQ4cOebh6IiIiquo02ySVt2/fPoSEhDi9d37q1CkUFBSUWf8kKCgIDRs2xPHjxz1VJhEREWlEtRjc/vHHH7FixQq8/vrrTo8pWcek/Aq1gYGBDtc4KS4uRmZmJvz9/a/rKwqItK5bt26lH1svWSWalGrVqlW65AHfJ6Kqw263Iz8/H/Xq1Std6FYtzTdJu3fvxsyZMxEXF6f4JMnVSr5bKTc3t8yaH7m5uQ6/dykzMxNPPvmk6wsmIiIit1u7di3q169/Q8+h6Sbp66+/RkJCAl599dUKGyQAuO222+Dn54e0tDTcc889AP5ewM1isThc4bbko8CnT59G7dq1XV98FRYVFVX6UWmZMLdcmFsuzC2PS5cu4dZbb1W1pEd5mm2S1q1bh48++gizZs1C27Ztr3m8r68vevfujWXLliEsLAy1atXChx9+iMaNGyM8PFxxfMktttq1a0vXJLVq1Uq6zABzy4a55cLc8nHFqIxmB7fff/995OfnY+rUqejTp0/pnwMHDpQe06dPH3z99delP48bNw7h4eF49tln0b9/f2RnZ2PWrFk3fM+yuin59nLZMLdcmFsuzE1qaPZK0vbt2695zObNm8v87Ovri0mTJim+UoHKioqKEl2CEMwtF+aWC3OTGryEQgpBQUGiSxCCueXC3HJhblKDTRIppKamii5BCOaWC3PLhblJDc1+d5u7Xb58GX379kV2dra0Q29ERERac+nSJQQFBWHjxo2oWbPmDT0XryQREREROcAmiYiIiMgBNkmkYDQaRZcgBHPLhbnlwtykBmeSnJB5JslisSA0NFR0GR7H3HJhbrkwtzw4k0RuJdsvVAnmlgtzy4W5SQ02SUREREQOsEkiBdm+DLEEc8uFueXC3KQGmyRSyMrKEl2CEMwtF+aWC3OTGhzcdkLmwW0iIiKt4uA2ERERkZuxSSIFq9UqugQhmFsuzC0X5iY12CSRQlxcnOgShGBuuTC3XJib1OBMkhMyzyRZrVbo9XrRZXgcc8uFueXC3PLgTBK5lWy/UCWYWy7MLRfmJjXYJBERERE5wCaJFBITE0WXIARzy4W55cLcpAabJFIIDg4WXYIQzC0X5pYLc5MaHNx2QubBbSIiIq3i4DYRERGRm7FJIgWLxSK6BCGYWy7MLRfmJjXYJJFCQkKC6BKEYG65MLdcmJvU4EySE5xJIiIi0h7OJBERERG5GZskIiIiIgfYJJGCyWQSXYIQzC0X5pYLc5MabJJIISIiQnQJQjC3XJhbLsxNanBw2wkObhMREWkPB7eJiIiI3IxNEimkpaWJLkEI5pYLc8uFuUkNNkmkkJSUJLoEIZhbLswtF+YmNTiT5ARnkoiIiLSHM0lEREREbsYmiYiIiMgBNkmkEB8fL7oEIZhbLswtF+YmNdgkkUJ0dLToEoRgbrkwt1yYm9TwFl2AWt9++y3Wr1+PEydOIC8vD9u2bYNOp3N6/KRJk/DLL7/A2/v/I48ZMwaPPfaYJ8rVlNatW4suQQjmlgtzy4W5SQ3NNkmBgYGIjo5GQUEB5s6dW6nHDBw4ECNHjnRzZURERFQdaPZ2W2RkJHr27Imbb75ZdCnVTkpKiugShGBuuTC3XJib1NBsk6TGhg0b0K9fPwwdOhSLFi1Cfn6+6JKqpNTUVNElCMHccmFuuTA3qaH5xST379+PyZMnX3Mm6dChQ7jtttsQGBiIX3/9FfHx8bjlllvw2muvOTyei0kSERFpDxeTVCE8PBy1a9dGjRo1EBYWhvHjx2Pnzp0oKCio8HEDBgyAwWCAwWBAcnIyDAYDrFZr6f7ExESYzebSny0WC4xGY5nnMJlMZS55pqWlKT6WGR8fX+Y7dlJSUmAymcocYzQaYbFYSn82m81ITEws/dlqtbI+1sf6WB/rY33S1Wc2mzFmzBhERkYiLi4OriLNlaTyUlNTYTAYsGnTJuj1esV+XkkiIiLSHl5JAlBUVASbzYbCwkIAgM1mg81mQ3FxseLYCxcuYO/evcjPz4fdbsfJkyfx4Ycf4p577nHYIMmu/L8UZMHccmFuuTA3qaHZK0lbtmxxuJLoe++9h4YNG2L48OGIj49H27ZtYbFY8Prrr+P06dMoKipC3bp10a1bNwwdOhQBAQEOn1/mK0kWiwWhoaGiy/A45pYLc8uFueXhyitJmm2S3E3mJomIiEireLuNiKR3/vx5zHjjDbRt3hzNQkMxoF8/7Ny5U3RZRFSNsEkihas/zSAT5taOU6dOoUN4OLbPno1Xfv0VSzMy0Pyrr9C3Vy+89847lXoOLeZ2BeaWi6y5XUWzX0tC7pOVlSW6BCGYWzvGPfMMHsjMxNIrV+D1z7YexcUYUFyMe6dNQ59HHrnmd1ZpMbcrMLdcZM3tKpxJcoIzSURV0+nTp9G8SROcLC5GIwf7n/b1RYOxY/HOvHker42IxONMEhFJ69dff0Ujvd5hgwQAnWw2pP/yi0drIqLqiU0SKVy9oqlMmFsbGjRogAybDZec7D+u06FBJb74Wmu5XYW55SJrbldhk0QKrlzSXUuYWxvatGmD8Fat8IGDfX8BWKHTYdjo0dd8Hq3ldhXmlousuV2FM0lOyDyTZLVapVyJnLm1IyUlBQ/efz/G2GwYa7ejPoAtAF7R69H18cexbNUqeHl5VfgcWsztCswtFxlzcyaJ3Eq2X6gSzK0dnTt3xs7du3EiKgotvbwQBMDYsCHGzZqFj1auvGaDBGgztyswt1xkze0qXAKAiDSpXbt2WLd5M6xWK6xWK4KCgirVHBERVRavJJFCYmKi6BKEYG5t0uv1CA4Ovu4GSeu51WJuucia21XYJJFCcHCw6BKEYG65MLdcmJvU4OC2EzIPbhMREWkVB7eJiIiI3IxNEilYLBbRJQjB3HJhbrkwN6nBJokUEhISRJcgBHPLhbnlwtykBmeSnOBMEhERkfZwJomIiIjIzdgkERERETnAJokUTCaT6BKEYG65MLdcmJvUYJNEChEREaJLEIK55cLccmFuUoOD205wcJuIiEh7OLhNRERE5GZskkghLS1NdAlCMLdcmFsuzE1qsEkihaSkJNElCMHccmFuuTA3qcGZJCc4k0RERKQ9nEkiIiIicjM2SUREREQOsEkihfj4eNElCMHccmFuuTA3qcEmiRSio6NFlyAEc8uFueXC3KQGmyRSaN26tegShGBuuTC3XJib1GCTREREROQAmyRSSElJEV2CEMwtF+aWC3OTGmySSCE1NVV0CUIwt1yYWy7MTWpwMUknuJgkERGR9nAxSSIiIiI3Y5NERERE5ACbJFIwGo2iSxCCueXC3HJhblJDszNJ3377LdavX48TJ04gLy8P27Ztg06nc3p8Tk4OEhISSif9O3fujEmTJiEwMNDh8TLPJFksFoSGhoouw+OYWy7MLRfmlgdnkgAEBgYiOjoa48ePr9TxM2fOxMWLF7Fq1SqsWrUKFy9exOzZs91cpTbJ9gtVgrnlwtxyYW5SQ7NNUmRkJHr27Imbb775msdaLBbs2bMHY8eORVBQEIKCgjB27Fh8//33yMjI8EC1REREpDWabZKuR3p6Onx8fBAWFla6LSwsDD4+PkhPTxdYWdVkNptFlyAEc8uFueXC3KSGFE1SXl6ew9mjwMBA5OXlCaioasvKyhJdghDMLRfmlgtzkxpSNEkBAQHIzc1VbM/NzUVAQECFjx0wYAAMBgMMBgOSk5NhMBhgtVpL9ycmJpbp1C0Wi+LTBCaTqczS8GlpaYiPjy9zTHx8PNLS0kp/TklJgclkKnOM0WiExWIp/dlsNiMxMbH0Z6vV6pL6IiIiqnR97nr/oqOjq3R97nr/YmNjq3R9gHvev9jY2CpdH+Ce9y82NrZK1we45/2LjY2t0vUB7nn/YmNjq3R9JW60PrPZjDFjxiAyMhJxcXFwFc1+uq3E/v37MXny5Ao/3WaxWDBo0CAsWbIEzZs3BwCcOHECo0aNwpo1axASEqJ4jMyfbiMiItIqfroNQFFREWw2GwoLCwEANpsNNpsNxcXFimNDQ0PRqVMnLFy4ENnZ2cjOzsbChQvRtWtXhw2S7K7u1GXC3HJhbrkwN6mh2Sbp66+/RlRUFKZMmQIAePjhhxEVFYUDBw4gIyMDffr0wYEDB0qPj4uLQ+3atTF48GAMHjwYQUFBXGTLCVdeqtQS5pYLc8uFuUkNzd9ucxeZb7dZrVbo9XrRZXgcc8uFueXC3PLg7TZyK1l+oex2O9atW4eo++5D05AQ3Hf33Zg/f750n3iU5XyXx9xyqSq5d+/ejSeeGISGDZujadNwvPLKq25dr6+q5NYqNkkkJbvdjvGjR2PcoEG4f9cuLD97FmMPH8ZHU6agR5cuyMnJEV0iEVUzJtMidO/+IDZsuBkWy2L89tvrePvtfbjjjvZcs6+KYpNECld/7LK6Sk5OxpcrV2JvQQGMALoDCACQYrUi4OhRvPbKK4Ir9BwZzrcjzC0X0blPnTqFCRNeQGHhFhQVvQPgAQD9UVDwFbKy+uOpp0a65XVF59Y6NkmkEBwcLLoEt1uUkIAJNhtuvWpbMAA/AG8UFGDZkiWln5ys7mQ4344wt1xE5168eCl0uj4A7i23xwtFRa/hp5/2lllLyFVE59Y6NkmkEBUVJboEtzt+9Cgi7WU/s1CSuhOArLw8ZGZmerwuEWQ4344wt1xE5z58OB0FBZFO9taDXh+GEydOuPx1RefWOjZJJKWQkBA4mwBIB+Dr7Y2goCBPlkRE1VijRg3g4+PsvzpWFBb+gQYNGni0Jro2NkmkcPXS8NXV0LFj8YG/P67+HJsFgB3AW97eePKJJ+Dv7y+oOs+S4Xw7wtxyEZ37mWeGwm5fA+B3B3sX4+abG6JDhw4uf13RubWOTRIpJCQkiC7B7Z5++mk0aNsWD/j5YSuAXAAvAxjq7Q1zrVqYUe67h6ozGc63I8wtF9G527VrhxEjnoFe3x3AKgDZAH6Dl9fL8PWdho8+WgAvLy+Xv67o3FrHxSSdkHkxSVnk5eVh1ptvYvGHH+Jsdjb0Pj4YOGAAXps5E02aNBFdHhFVM3a7HQsXLsTs2fNw+vQxeHl5oUePhzFr1nR06tRJdHnVhisXk2ST5ASbJHkUFRUhOzsbgYGB8PX1FV0OEVVzdrsd2dnZ8PPzk+a2vie5sknydlFNRJql0+lQt25d0WUQkSS8vLz40XyN4EwSKZhMJtElCMHccmFuuTA3qcEmiRQiIiJElyAEc8uFueXC3KQGZ5Kc4EwSERGR9rhyJolXkoiIiIgcYJNECu74/iAtYG65MLdcmJvUYJNECklJSaJLEIK55cLccmFuUoMzSU5wJomIiEh7OJNERERE5GZskoiIiIgcYJNECvESfbnr1ZhbLswtF+YmNdgkkUJ0dLToEoRgbrkwt1yYm9Rgk0QKrVu3Fl2CEMwtF+aWC3OTGmySiIiIiBxgk0QKKSkpoksQgrnlwtxyYW5Sg00SKaSmpoouQQjmlgtzy4W5SQ0uJukEF5MkIiLSHi4mSURERORmbJKIqNJycnJw6dIl0WUQEXkEmyRSMBqNoksQgrmd27RpE+5p1w61a9dGUFAQIsPD8eWXX3qgOvfh+ZYLc5ManElyQuaZJIvFgtDQUNFleBxzO/bR0qWYNHYsXi8sxFMAdAASAbzi64vX33oLL0yc6KlSXYrnWy7MLQ9XziSxSXJC5iaJqERubi5url8fn1mtiCq373sAPX188Mdff6FevXoiyiMiUuDgNhF5xPr169GsRg085GBfVwB3+/jgs88+83RZREQewSaJFMxms+gShGBupbNnzyLMboeXk/1hhYU4e/asewpzM55vuTA3qcEmiRSysrJElyAEcyuFhYXhBwBFDvbZAez19kZYWJi7SnMrnm+5MDepwZkkJziTRARcuXIFTRs2xNTz5zGh3L6PAbxYqxb+OHsWer1eRHlERAqunEnydlFNRFQNeXt7Y/WXX+KRhx7C7uJiPGWzQQdgrY8P1np54cvPP2eDRETVFm+3kYLVahVdghDM7Vi3bt3w08GDuGnUKBgaNcILN98Mv6FD8UNqKh56yNFItzbwfMuFuUkNTTdJdrsdy5YtQ0xMDPr06YOJEyfi5MmTTo+fNGkSHnzwQfTp06f0z/r16z1YsTbExcWJLkEI5nYuLCwMCQsW4Ogff+DYn3/iP0uWoHXr1h6ozn14vuXC3KSGpmeS1qxZgy+//BJz5sxBo0aNsGLFCmzduhUrVqyAv7+/4vhJkybhzjvvxMiRI6/53DLPJFmtVilvoTC3XJhbLswtD66T9I+kpCQ8+eSTaNasGfz8/DBixAgUFhZi165dokvTNNl+oUowt1yYWy7MTWpotknKzc2FxWJBmzZtSrfpdDq0aNECx48fd/q4DRs2oF+/fhg6dCgWLVqE/Px8T5RLREREGqPZJikvLw8AEBgYWGZ7YGBg6b7yRo0ahU8++QRJSUl49dVXsW/fPrz11ltur1VrEhMTRZcgBHPLhbnlwtykhmabpICAAAB/X1G6Wm5ubum+8sLDw1G7dm3UqFEDYWFhGD9+PHbu3ImCggKnrzNgwAAYDAYYDAYkJyfDYDCU+bRAYmJimRVNLRaL4luXTSYTUlJSSn9OS0tDfHx8mWPi4+ORlpZW+nNKSgpMJlOZY4xGIywWS+nPZrO5zC+A1Wp1SX05OTlVuj53vX8BAQFVuj53vX/BwcFVuj7APe9fcHBwla4PcM/7FxwcXKXrA9zz/gUHB1fp+gD3vH/BwcFVur4SN1qf2WzGmDFjEBkZ6dJhdU0Pbg8aNAgxMTHo378/AKCoqAgxMTEYO3ZspT6anJqaCoPBgE2bNinu28o8uE1ERKRVHNz+R3R0NNauXYuTJ0+ioKAAy5Ytg7e3N7p166Y49sKFC9i7dy/y8/Nht9tx8uRJfPjhh7jnnns42EZEREQKml5xOzY2Fnl5eXjxxReRl5eHVq1aIT4+Hv7+/sjIyMDw4cMRHx+Ptm3bwmazYdmyZTh9+jSKiopQt25ddOvWDUOHDhUdo8qxWCwIDQ0VXYbHMbdcmFsuzE1qaPpKkpeXF0aMGIEvv/wSW/+6CbQAACAASURBVLZsQUJCApo1awYACAkJwebNm9G2bVsAQGhoKP7zn/9g48aN2Lx5M1atWoXnnnvO6fySzBISEkSXIARzy4W55cLcpIamZ5LcSaaZJLvdjvXr12Phe+/h2NGjqH/TTXj6uecwcuRINpEacP78efznww/x2ccfI/fyZdzdsSOe/9e/cN9994kujYjI4ziTRC5jt9sxfvRojBs0CPfv2oXlZ89i7OHD+GjKFPTo0gU5OTmiS6QKnDp1Ch3Cw7F99my88uuvWJqRgeZffYW+vXrhvXfeEV0eEZGmsUmSXHJyMr5cuRJ7CwpgBNAdwDMAUqxWBBw9itdeeUVwhVSRcc88gwcyM/GN1YonAfQAMKe4GNsLCxE3bVqZj90SEdH1YZMkuUUJCZhgs+HWq7aZAPgBeKOgAMuWLEFhYaGg6jyr/LodVd3p06exdccOzLhyBV7l9t0NIKZGDSxeuPCaz6O13K7C3HJhblKDTZLkjh89ikh72bG0iH/+7gQgKy8PmZmZHq9LhIiIiGsfVIX8+uuvaKTXo5GT/Z1sNqT/8ss1n0druV2FueXC3KQGmyTJhYSEIL3cts7//J0OwNfbG0FBQR6uSozOnTtf+6AqpEGDBsiw2XDJyf7jOh0a3HzzNZ9Ha7ldhbnlwtykBpskyQ0dOxYf+Puj/Lfd2QG85e2NJ594Av7+/iJKo2to06YNwlu1wgcO9v0FYIVOh2GjR3u6LCKiaoNNkuSefvppNGjbFg/4+WErgFwASQCGenvDXKsWZpT7Dp7qTItDzu8vWYLZfn54ycsLJwBcArAWQHe9HtH9++Oee+655nNoMbcrMLdcmJvUYJMkOT8/P3z17bfoZTDg6aAg1MLfA7/eTz6J3T/9hCZNmogu0WOSkpJEl3DdOnfujJ27d+NEVBRaenkhCICxYUOMmzULH61cCS+v8iPdSlrM7QrMLRfmJjW4mKQTMi0mWaKoqAjZ2dkIDAyEr6+v6HLoOlmtVlitVgQFBVWqOSIiqo5cuZikpr+7jVxLp9Ohbt26ossglfR6Pb+smYjIhXi7jYiIiMgBNkmkEC/RsPbVmFsuzC0X5iY12CSRQnR0tOgShGBuuTC3XJib1GCTRAqtW7cWXYIQzC0X5pYLc5MabJKIiIiIHGCTRAopKSmiSxCCueXC3HJhblKDTRIppKamii5BCOaWC3PLhblJDS4m6YSMi0kSERFpHReTJCKqon744QcsWbIcp09b0KZNczz77Ei0bNlSdFlEpAJvtxERuYDdbseYMRPQtWsPLF1aiK++6oL580/h9tvb4t1354kuj4hUYJNECkajUXQJQjC3XFyde9GiRVixIhmFhb/gyhUTgBdhs32KoqL/wWh8Ddu3b3fp66nF8y0XWXO7CmeSnJB5JslisSA0NFR0GR7H3HJxZW673Y6mTe/A779PAzBUsd/L62VERR3G5s3rXPJ6N4LnWy4y5nblTBKvJJGCbL9QJZhbLq7MnZeXh99/PwKgj8P9dvvD2LfvB5e93o3g+ZaLrLldhU0SEdEN8vX1RY0aOgCZTo7IhL9/gCdLIiIXYJNECmazWXQJQjC3XFyZ28fHB336PIYaNRY52GuHn58JQ4bEuOz1bgTPt1xkze0qbJJIISsrS3QJQjC3XFyde+bM6fDxWQxgDoDcf7aeg073AmrW/BkTJz7v0tdTi+dbLrLmdhUObjsh8+A2Eamze/dujBgxHunpx+Dn1whW6++IjLwHK1aYEBYWJro8IilwMUkioiqoS5cuOHz4Rxw6dAgZGRlo0qQJmyMiDWOTRApWqxV6vV50GR7H3HJxV24vLy/ceeeduPPOO13+3K7A8y0XWXO7CmeSSCEuLk50CUIwt1yYWy7MTWpwJskJmWeSZP2XB3PLhbnlwtzy4GKS5Fay/UKVYG65MLdcmJvUYJNERERE5ACbJFJITEwUXYIQzC0X5pYLc5Maqj/dtnr1aiQlJeHSpUuIiIjA+PHjceuttwIANm3ahPT0dOTn52PatGkuK5Y8Izg4WHQJQjC3XJhbLsxNaqga3F67di3WrFmDjh07IigoCMeOHcPRo0fx+uuvIzIyEgCwd+9eGI1GfPPNNy4v2hNkHtwmIiLSKuGLSe7duxcff/wxatWqVbrtyJEjeP/99+Hj44N27drdUFFEREREoqmaSWrZsmWZBgkA2rRpg/feew9btmzBTz/95JLirsVut2PZsmWIiYlBnz59MHHiRJw8edLp8Tk5OXjzzTfRt29f9O3bF2+++SZyc3OdHi8ri8UiugQhmFsuzC0X5iY1VDVJXl5esNlsSE9Px44dO0q36/V6GI1GHDp0CPv27XNVjU4lJiZi8+bNeOutt7B+/XqEh4djypQpyM/Pd3j8zJkzcfHiRaxatQqrVq3CxYsXMXv2bLfXqTUJCQmiSxCCueXC3HJhblJD1UzShQsXsGTJEhw5cgRZWVlYt26d4pgtW7bg3XffxdatW11SqCODBg1C//79ERMTAwAoKipC//79MW7cODz00ENljrVYLBg0aBAWL15c+l1K6enpGD16NNasWYOQkJAyx3MmiYiISHuEzyTVrVsXU6ZMwZ9//glvb8dP0bt3b4SHh99QcRXJzc2FxWJBmzZtSrfpdDq0aNECx48fVzRJ6enp8PHxKfNlk2FhYfDx8UF6erqiSSIiIiK5Xdfttt9//x3vv/8+Dh8+DABo1KhRhc3FLbfccmPVVSAvLw8AEBgYWGZ7YGBg6b7yx5c/tqLjiYiISG7X1SStXLkSycnJmDt3bpntmzZtwty5c3Hu3DmXFleRgIAAAFAMXufm5pbuK3+8oyFtZ8eXGDBgAAwGAwwGA5KTk2EwGGC1Wkv3JyYmwmw2l/5ssVhgNBrLPIfJZEJKSkrpz2lpaYiPjy9zTHx8PNLS0kp/TklJgclkKnOM0WgsM4RnNpvLLBRmtVpdUt/rr79epetz1/v3wQcfVOn63PX+mUymKl0f4J73z2QyVen6APe8fyXHV9X6APe8fyaTqUrXB7jn/Sv5u6rWV+JG6zObzRgzZgwiIyNd+qW+1zWT9P7776Nr164oLi4uXQ+pRHZ2Nt5//30MGTIETZs2dVmBFRk0aBBiYmLQv39/AH/PJMXExGDs2LFOZ5KWLFmC5s2bAwBOnDiBUaNGcSapnJSUFHTu3Fl0GR7H3HJhbrkwtzyEfsHtLbfcomiQACAoKAgvvfQSPv300xsq6HpER0dj7dq1OHnyJAoKCrBs2TJ4e3ujW7duimNDQ0PRqVMnLFy4ENnZ2cjOzsbChQvRtWtXziOVI9svVAnmlgtzy4W5SY3rapKee+45LFiwAAsWLMC+ffsUH7X39/eHj4+PSwusSGxsLKKiovDiiy8iOjoaBw8eRHx8PPz9/ZGRkYE+ffrgwIEDpcfHxcWhdu3aGDx4MAYPHoygoCDFpUMiIiIi4Do/3fbNN9/g+++/h91uxxdffAFvb2+0aNECd911F1q3bo38/HxkZGS4q1YFLy8vjBgxAiNGjFDsCwkJwebNm8tsq127NqZPn+6p8jQrLS0NrVu3Fl2GxzG3XJhbLsxNalzXlaQdO3Zg9erV+OKLLzBr1iw8/vjjKCwsxJo1a/Daa69hyZIlGDVqlLtqJQ9JSkoSXYIQsuS22+1Yt24dou67D01DQvBg9+6YP3++dJ/ylOV8l8fccpE1t6tc9+D2Cy+8oNiek5ODvXv3YseOHRg9ejRuu+02lxYpgsyD21R92e12jB89GutWrsQLBQXoCuBXAO/r9fBt2RLb/vtfxVcOERFpibDBbZ1OhwsXLii216pVCz179sT06dOxevXqGyqIiNwnOTkZX65cib0FBTAC6A7gGQApVisCjh7Fa6+8IrhCIqKq47qapGHDhmHBggU4ePCgYt9HH32ETz/9FP7+/i4rjohca1FCAibYbLi13HY/AG8UFGDZkiUoLCwUURoRUZVzXU1SYGAgjEYjjh8/jm+++abMvn379uHjjz/mf2CrgfILgclChtzHjx5FpL3sHfaS1J0AZOXlITMz0+N1iSDD+XaEueUia25Xue7vbvP29sYTTzyh2D5nzhzs37/f4RpKpC3R0dGiSxBChtwhISFI//NPXL3UaknqdAC+3t4ICgoSUJnnyXC+HWFuucia21WuezFJZ4KCgtC9e3febqsGZP24qAy5h44diw/8/XH159haA7ADeMvbG08+8YQ0v8MynG9HmFsusuZ2FZc1SURU9T399NNo0LYtHvDzw1YAuQAOABjq7Q1zrVqYwUvzRESl2CSRwtVfVigTGXL7+fnhq2+/RS+DAU8HBaEWgI46HbyffBK7f/oJTZo0EV2ix8hwvh1hbrnImttV2CSRQmpqqugShJAld0BAAN6cNQtnMjORmZmJdxMSsGzVKqkaJECe810ec8tF1tyucl2LScqEi0kSERFpj7DFJImIiIhkwSaJiIiIyAE2SaRgNBpFlyAEc8uFueXC3KQGZ5KckHkmyWKxIDQ0VHQZHsfccmFuuTC3PDiTRG4l2y9UCeaWC3PLhblJDTZJRERERA6wSSIFs9ksugQhmFsuzC0X5iY12CSRQlZWlugShGBuuTC3XJib1ODgthMyD24TERFpFQe3iYiIiNyMTRIpWK1W0SUIwdxyYW65MDepwSaJFOLi4kSXIARzy4W55cLcpAZnkpyQeSbJarVCr9eLLsPjmFsuzC0X5pYHZ5LIrWT7hSrB3HJhbrkwN6nBJomIiIjIATZJpJCYmCi6BCGYWy7MLRfmJjXYJJFCcHCw6BKEYG65MLdcmJvU4OC2EzIPbrtTYWEhcnJyEBQUBJ1OJ7occjOebyLyNA5uk+acOXMGzz7zDIIDA1GvXj00CA7GlBdfRE5OjujSyA3OnDmDZ555FoGBwahXrx6CgxvgxRen8HwTkaawSSIFi8Xi0uc7c+YMurRvj6xVq7DLZkMOgC9yc7FnwQL0vOceXL582aWvp5arc2uFO853+/ZdsGpVFmy2XQBykJv7BRYs2IN77unJ8y0Yc8tF1tyuwiaJFBISElz6fDNefRUdL1xAYmEh2gMIBHA/gK0FBSg6fhyLFy926eup5ercWuHq3K++OgMXLnREYWEicNUZLyjYiuPHi3i+BWNuucia21U4k+QEZ5Jco6ioCMGBgdhmtaKTg/2fAHi3RQv8fOyYp0sjNygqKkJgYDCs1m2AkzPeosW7OHbsZ0+XRkSS4EwSaUZ+fj5yrVaEOdkfBuBcZqYnSyI3ys/Ph9WaC1RwxjMzz3myJCIi1dgkkVvVrFkToXXqYK+T/XsANG/WzJMlkRvVrFkTdeqEAhWc8WbNmnuyJCIi1dgkkYLJZHLZc3l5eeHZ8ePxb70eeeX2ZQB4V6/HmMmTXfZ6N8KVubXE1ed7/Phnodf/G3BwxvX6dzF58hiXvd6N4PmWC3OTGmySSCEiIsKlzzctLg76tm3R0d8fiwB8B+BtAB30etwfHY2BAwe69PXUcnVurXB17ri4aWjbVg9//47AVWdcr++A6Oj7eb4FY265yJrbVTi47QQHt12roKAAy5cvx/IFC5Bx9iyaNWuGZydNQkxMDGrUYK9e3ZSc7wULluPs2Qw0a9YMkyY9y/NNRG7nysFtzTZJ3333HZYuXYqMjAyEhoZi5MiRuO+++5wev3z5cnzyySfw9fUt3da1a1dMnz7d4fFskojIE+x2O3bs2IG9e/fC398f0dHRaNy4seiyiDRL+k+3HT58GDNnzsTIkSOxadMmjBgxAjNnzsTRo0crfNztt9+OzZs3l/5x1iDJLi0tTXQJQjC3XKpC7pMnT6JNm/bo3XsA/v3vn2A0bkKzZi0wevR4XLlyxS2vWRVyi8DcpIYmm6Tk5GR06tQJ3bt3h7e3N7p3747IyEgkJSWJLq1akPV9ZG65iM5dUFCA++57CCdOdIHN9ges1kTk5ZlRXJyGlSu3w2h0zz/iROcWhblJDU3ebhs9ejTuv/9+DB48uHTbypUrsXPnTixatMjhY5YvX47ExET4+flBr9fjjjvuwKhRo9CwYUOHx/N2GxG506pVqzB69BvIzz8C5b9X98HP7wGcPfsn//tDdJ1cebvN20U1ucScOXNgNpud7o+IiMC8efOQl5eHwMDAMvtq1apV4XdCde/eHb1790ZISAjOnz8Pk8mEl156CUuWLIG/v7/LMhARVcamTV8jPz8Wji/od0SNGg2we/duREVFebo0IvpHlbrdNnHiRKxfv97pnzfffBMAEBAQgNzc3DKPzcnJqbBjbNq0KUJDQ+Hl5YX69etjypQpOHfuHA4dOlRhTQMGDIDBYIDBYEBycjIMBgOsVmvp/sTExDKNncVigdFoLPMcJpMJKSkppT+npaUhPj6+zDHx8fFl7h2npKQo1rcwGo1lvqzQbDYjMTGx9Ger1cr6WB/r00h9f/31J4BfrjrCCsDwz99/++677/j+sT7WV4n6zGYzxowZg8jISMTFxcFVNHm7LT4+HpcvX8Ybb7xRuu3VV19FYGAgpkyZUqnnKCwsRN++fTFjxgxERkYq9st8uy0+Ph5Tp04VXYbHMbdcROcWdbtNdG5RmFse0n+6rV+/fkhJScGuXbtw5coV7Nq1C3v27MGjjz7q9DHbt29HdnY2AODChQuYO3cu6tSpg/DwcE+VrRnR0dGiSxCCueUiOndMTAzq1SuGt/cEXH31CPgVev1QPP/8BLf8A010blGYm9TQ5JUkANixYwc++ugjWCyW0nWSunfvXrp/+PDh6NWrF4YMGQIAePnll/HLL7/AarWiVq1aaNu2LUaMGIFGjRo5fH6ZryQRkWf89ttv6N37cfz222l4efVEjRpZsFq3Y8SI0fjPfxLg7V2lxkaJNIGLSXoAmyQi8gS73Y7vvvsOe/bsQUBAAB599FEuJkl0A6S/3UbudfUQnkyYWy5VJbeXlxfuv/9+TJ06Fc8//7zbG6SqktvTmJvUYJNECqmpqaJLEIK55cLccmFuUoO325zg7TYiIiLt4e02IiIiIjdjk0RERETkAJskUii/oqosmFsuzC0X5iY1OJPkhMwzSSVrT8mGueXC3HJhbnlwJoncSrZfqBLMLRfmlgtzkxpskoiIiIgcYJNECld/67NMmFsuzC0X5iY12CSRQlZWlugShGBuuTC3XJib1ODgthMyD24TERFpFQe3iYiIiNyMTRIpWK1W0SUIwdxyYW65MDepwSaJFOLi4kSXIARzy4W55cLcpAZnkpyQeSbJarVCr9eLLsPjmFsuzC0X5pYHZ5LIrWT7hSrB3HJhbrkwN6nBJomIiIjIATZJpJCYmCi6BCGYWy7MLRfmJjW8RRdAVU9wcLDoEoRgbrkwt2v98MMPWLJkOU6ftqBNm+Z49tmRaNmypVteSw2eb1KDg9tOyDy4TURUWXa7Hc899zyWLfsYdvtTuHKlJXx9f0BR0Tq89dYcGAyTRJdIknHl4DavJBERkWqLFi3CihXJKCz8BcBtAACbDQB+hNH4ANq1i0CPHj1ElkikGmeSSMFisYguQQjmlgtz3zi73Y7ZsxNgtc5ASYP0/+5GYeEEvPXW+y57vRvB801qsEkihYSEBNElCMHccmHuG5eXl4fffz8CoI/D/Xb7w9i37weXvd6N4PkmNTiT5ARnkoiIKlZYWAi93h/FxYcAtHZwxAbccsu/cPr0UU+XRhLjYpJERCScj48P+vR5DDVqLHKw1w4/PxOGDInxeF1ErsImiYiIVJs5czp8fBYDmAMg95+t56DTvYCaNX/GxInPC6yO6MawSSIFk8kkugQhmFsuzO0aERER2L59K1q3Xgtv71DUrNkKOt2tiIw8jD17diI0NNSlr6cWzzepwSUASCEiIkJ0CUIwt1yY23W6dOmCw4d/xKFDh5CRkYEmTZogLCzM5a9zI3i+SQ0ObjvBwW0iIiLt4eA2ERERkZuxSSKFtLQ00SUIwdxyYW65MDepwSaJFJKSkkSXIARzy4W55cLcpAZnkpzgTBIREZH2cCaJiIiIyM3YJBERERE5wCaJFOLj40WXIARzy4W55cLcpAabJFKIjo4WXYIQzC0X5pYLc5MamlxxOz09HYsXL8bx48dx8eJFvP3227j77rsrfIzdbsfy5cuxadMmXL58GS1btsSkSZPQtGlTD1WtHa1bO/o27+qPueXC3HJhblJDk1eSfHx80K1bN8yePbvSj0lMTMTmzZvx1ltvYf369QgPD8eUKVOQn5/vxkqJiIhIqzTZJDVu3Bh9+/ZFq1atKv2YpKQkPPnkk2jWrBn8/PwwYsQIFBYWYteuXW6sVJtSUlJElyAEc8uFueXC3KSGJpuk65WbmwuLxYI2bdqUbtPpdGjRogWOHz8usLKqKTU1VXQJQjC3XJhbLsxNalSpmaQ5c+bAbDY73R8REYF58+Zd9/Pm5eUBAAIDA8tsDwwMLN1H/2/MmDGiSxCCueXC3HJhblKjSl1JmjhxItavX+/0z5tvvqnqeQMCAgD8fUXparm5uaX7nBkwYAAMBgMMBgOSk5NhMBhgtVpL9ycmJpZp7CwWC4xGY5nnMJlMZS55pqWlKT6WGR8fX+Y7dlJSUmAymcocYzQaYbFYSn82m81ITEws/dlqtbI+1sf6WB/rY33S1Wc2mzFmzBhERkYiLi4OrqL5ryXp0aNHpT7dNmjQIMTExKB///4AgKKiIsTExGDs2LF46KGHFMfza0mIiIi0R/qvJbHb7bDZbLDZbACAK1euwGazoaioyOljoqOjsXbtWpw8eRIFBQVYtmwZvL290a1bN0+VrRnl/6UgC+aWC3PLhblJDU1eSbJYLBg0aJBi+7BhwzB8+HAAwPDhw9GrVy8MGTIEwN+N1bJly7Bx40bk5eWhVatWmDhxIpo1a+bwNWS+kmSxWBAaGiq6DI9jbrkwt1yYWx6uvJKkySbJE2RukoiIiLRK+tttRKKkp6dj3LgXcMstrdCoUQuMGjUWR44cEV0WERG5AZskUqhoGYbq7Fq5d+3ahTvvbI+lSy/gzz/fw5kz87FiRQHuuqsjtm7d6qEqXY/nWy7MLRdZc7tKlVoniaqGrKws0SUIUVHuK1eu4IknnoLVOgvAhNLthYW9AXRHTMxTyMg4DX9/f/cX6mI833JhbrnImttVOJPkBGeS6GobNmzAwIEvID//BABdub12+PvfgSVLXsFTTz0lojwiIvoHZ5KIPCw9PR1ABygbJADwwpUrkf8cQ0RE1QWbJFK4ekVTmVSUu0GDBvDySgfg+MKrj086GjRo4KbK3IvnWy7MLRdZc7sKmyRScOWS7lpSUe7HHnsMxcW/AnA0oP09Cgt/xIABA9xWmzvxfMuFueUia25X4UySEzLPJFmtVuj1etFleNy1ci9d+hHGjp2EwsLXATyFv2+9JcLX9xW89dbrmDjxBU+V6lI833JhbrnImJszSeRWsv1ClbhW7pEjR2Dduk/Rrt0XAEIB1Mcdd3yMTz9dqtkGCeD5lg1zy0XW3K7CJQBItby8POzbtw/FxcXo2LEjAgMDRZfkdo888ggeeeQR5OTkwG63S3eVkYhIJrySRAqJiYkV7i8uLsaMf/8bjerXx5A+fTD8kUdwc/36eHnq1Aq/ZLiqu1buq9WqVavaNEjXk7s6YW65MDepwStJpBAcHFzh/qkGA740mbDBasW9/2zbC+CZ99/HhfPn8Z+lS91eoztcK3d1xdxyYW65yJrbVTi47YTMg9sVsVgsaHzLLfi5qAi3l9v3G4BWOh3Sjh9H06ZNBVRHRESy4+A2CbNhwwZ09vNTNEgA0ARAL19ffPnllx6uioiIyPXYJJGCxWJxuu/y5cuoZ3d+8bFeURHy8vLcUZbbVZS7OmNuuTC3XGTN7SpskkghISHB6b6OHTtiR1ERHLVBNgBfe3mhQ4cObqvNnSrKXZ0xt1yYWy6y5nYVziQ5wZkkx+x2OzrccQcijx/HgitXSrtsO4ApNWog+dZbcfjXX1GjBvtvIiLyPFfOJPHTbXRdvLy88MVXX+HBbt0QnpmJgfn50AFY6++PrNq1sdVsZoNERETVApskum5NmjTBwePHsXbtWmxJSoK9uBjPP/IIBg0adMNdOxERUVXBf/KTgslkuuYxer0eQ4cOxeovvsCn69Zh1KhRmm+QKpO7OmJubSkuLsZXX32FwYOfQd++AzB79hycPXu20o/Xau4bxdykBpskUoiIiBBdghDMLRct5r58+TK6dXsQTzwxEp9+2gCbNkVixoxv0Lhxc5jN5ko9hxZzuwJzkxoc3HaCg9tEVNUMH/4s1qw5hoKCTQCuvnK7Gn5+Y/Dbb8cRGhoqqjyiKoGLSRIRSebChQtYvfoTFBR8gLINEgA8BS+ve7B48RIRpRFVW2ySSCEtLU10CUIwt1y0lvvQoUPw9q4PINzhfqv1Yeza9cM1n0druV2FuUkNNkmkkJSUJLoEIZhbLlrLXbNmTVy5cglAoZMjMlGrVsA1n0druV2FuUkNziQ5wZkkIqpKiouL0ahRGCyWGQAGl9trhV7fGqtXv4fHH39cRHlEVQZnkoiIJFOjRg28994s+PiMA7AGwJV/9qTDz+9xtG7dEP369RNYIVH1wyaJiEgjBg4ciI8/XogGDabBzy8UAQEtoNPdgUcfvQk7dmyBtzfXByZyJTZJpBAfHy+6BCGYWy5azT1o0CCcOXMCO3ZsxIYNC/Hnn6ewdu0nCAoKqtTjtZr7RjE3qcF/dpBCdHS06BKEYG65aDm3TqdD586dVT1Wy7lvBHOTGrySRAqtW7cWXYIQzC0X5pYLc5MabJKIiIiIHGCTRAopKSmiSxCCueXC3HJhblKDTRIppKamii5BCOaWC3PLhblJDS4m6QQXkyQiItIeLiZJRERE5GZskoiIiIgcYJNECkajUXQJQjC3XJhbLsxNamhyJik9PR2LFy/GOZnJMQAAE5xJREFU8ePHcfHiRbz99tu4++67K3zM8uXL8cknn8DX17d0W9euXTF9+nSHx8s8k2SxWBAaGiq6DI+TKbfNZsPGjRtx9OhR+Pr6YsSIEahTp47osjxKpvN9Neau2MGDB7F161bY7Xb07NkT7dq180B17iPj+XblTJImV9z28fFBt27dMGLECDz33HOVftztt9+O+fPnu7Gy6kG2X6gSsuTetWsXHnssFvn5/igu7gSd7iSMxul4++14vPDC86LL8xhZznd5zO1YTk4OYmKG4JtvtsLXNwp2ew0Yja+ha9d7sX79Gs3+I0LW8+0qmmySGjdujMaNG4sug0hzfv31Vzz00COwWucAeA7/f8f9v/jXv/qhYcNQDBgwQGCFRGLExg7Dd9/loKjoD+Tn1/tnaxb27BmMfv2exH//+7XQ+kgMqWaS0tPT8dhjj2HgwIGYMWMG/vrrL9ElVUlms1l0CULIkHvevA9QXPwIgHH4/19/M4B7YbPNxvTps2G3a+4OvCoynG9HmFvpyJEj2Lr1KxQUrAFQ76o9wSgoWI09e3bjhx9+cHuN7iDr+XaVKnUlac6cORWe0IiICMybN0/Vc3fv3h29e/dGSEgIzp8/D5PJhJdeeglLliyBv7+/2pKrpaysLNElCCFD7o0bv4bN9ma5rSW5B+Lo0bG4cOEC6tWrV/6h1Y4M59sR5lbatm0b/Px6Ii+vgYO9QdDpHsHWrVvRoUMH9xXoJrKeb1epUleSJk6ciPXr1zv98+ab5f/jXnlNmzZFaGgovLy8UL9+fUyZMgXnzp3DoUOHKnzcgAEDYDAYYDAYkJycDIPBAKvVWro/MTGxTGNnsVgUnyYwmUxlloZPS0tDfHx8mWPi4+ORlpZW+nNKSgpMJlOZY4xGIywWS+nPZrMZiYmJpT9brVaX1BcREVGl63PX+xcdHV2l63PV+wf8AeDq+mL/+flYlajPU+9fbGxsla4PcM/7FxsbW6XrA9zz/sXGxjqt7+TJk1dtSUPZ3w/gypUjOHfunFvrA9zz/sXGxlbp+krcaH1msxljxoxBZGQk4uLi4Cqa/HTb1Xr06FGpT7eVV1hYiL59+2LGjBmIjIxU7Jf5021UfU2caMDChX/BZvvUwd6FaN16MQ4f/gFeXl4er41IlLS0NISH34WiolMAyl9Nyoa3dyOkpHx33f+fITGkX3HbbrfDZrPBZrMBAK5cuQKbzYaioiKnj9m+fTuys7MBABcuXMDcuXNRp04dhIeHe6RmLbm6U5eJDLknTpyAGjU2AVgAoPifrVYAu+Dra8Qbb0yTpkGS4Xw7wtxKrVu3xkMPPQw/v4EAMq/akwU/v6fQuXMXzTZIsp5vV9Fkk5SRkYGoqChERUUBAKZNm4aoqCh88sknpccMHz4cK1euLP1527ZtGDZsGHr37o0xY8agqKgI77zzDgICAjxef1XnykuVWiJD7mbNmmHr1k2oW3cm/P1bQK9/Ct7eTeHjE4W5c9+Q6pNtMpxvR5jbscTEj3H//bWh090Cf/9o6PVPwNu7ETp3LsKGDWs9VKXryXq+XUXzt9vcRebbbVarFXq9XnQZHidT7sLCQiQnJ+PYsWMIDg5GbGysZteBUUum83015q7YoUOHYDabq81ikjKeb+kXkyT3ku0XqoRMuX18fPDEE0+ILkMomc731Zi7YuHh4dVqDEPW8+0qmrzdRkRERORubJJI4eqPXcqEueXC3HJhblKDTRIpBAcHiy5BCOaWC3PLhblJDQ5uOyHz4DYREZFWSb9OEhEREZG7sUkihauXhpcJc8uFueXC3KQGmyRSSEhIEF2CEMwtF+aWC3OTGpxJcoIzSURERNrDmSQiIiIiN2OTREREROQAmyRSMJlMoksQgrnlwtxyYW5Sg00SKURERIguQQjmlgtzy4W5SQ0ObjvBwW0iIiLt4eA2ERERkZuxSSKFtLQ00SUIwdxyYW65MDepwSaJFJKSkkSXIARzy4W55cLcpAZnkpzgTBIREZH2cCaJiIiIyM3YJBERERE5wCaJFOLj40WXIARzy4W55cLcpAabJFKIjo4WXYIQzC0X5pYLc5MabJJIoXXr1qJLEIK55cLccmFuUoNNEhEREZEDbJJIISUlRXQJQjC3XJhbLsxNarBJIoXU1FTRJQjB3HJhbrkwN6nBxSSd4GKSRERE2sPFJImIiIjcjE0SERERkQNskkjBaDSKLkEI5pYLc8uFuUkNziQ5IfNMksViQWhoqOgyPI655cLccmFueXAmidxKtl+oEswtF+aWC3OTGmySiIiIiBxgk0QKZrNZdAlCMLdcmFsuzE1qsEkihaysLNElCMHccmFuuTA3qcHBbSdkHtwmIiLSKg5uExEREbkZmyRSsFqtoksQgrnlwtxyYW5SQ5NNktlsxoQJE/Doo48iOjoakyZNwsGDB6/5uHXr1mHgwIHo3bs3nn32WX7xnxNxcXGiSxCCueXC3HJhblJDk01SXl4ehg4dijVr1uCLL77Avffei6lTp+LcuXNOH7Njxw4sXboU06ZNQ3JyMvr06YNp06bh7NmzHqxcG3r06CG6BCGYWy7MLRfmJjU02SQ9/n/t3W1sU+X7B/BvWbux2boow3aKm2DnQGFbYuwMYw55SIYBCwkxbJI5NwkpM9mDOCJEDZqpUxSmyTJwOtDwAnzhBs7NYKhmTjeJ0WFHCrQuAQmtMZQ9ta5d198LXf/0v9PRdg9tz76fhITdvU97Xb1O22vndPfZsgUajQYJCQmQSqXYunUr5s2bB6PR6HeblpYWbNiwAVlZWZDJZNiyZQsWLVqE9vb2WYw8Ouj1+nCHEBbMe25h3nML86ZQRGWT9P9duHABDocDDz74oN85JpMJS5cu9RlLT0+HyWSa6fCIiIgoCknDHcCt3nnnnUkXvsrMzMShQ4d8xv766y+88cYbKCwsxL333ut3W7vdDrlc7jOmUChw/fp1wfkez78rIwwMDAQavmj09vYy7zmEec8tzHtumYt5j+c7/jk+FRHVJJWXl0On0/m9PSYmxufna9euYffu3Vi9ejVKS0snve+EhAQMDQ35jA0ODvpdQ8HhcAAA7r///kBCF53ExMRwhxAWzHtuYd5zC/OeWxwOx4SDI8GKqCYpPj4e8fHxAc01m82orq6GVqtFUVHRbeer1WoYjUasXbvWO3bp0iWsWrVKcP6CBQtw8uRJxMfHQyKRBJYAERERhZXH44HD4cCCBQumfF8R1SQFymAwYO/evSgqKsLWrVsD2kar1eLAgQPIzc3FsmXL8PXXX+Pq1avIz88XnD9v3jwsXLhwOsMmIiKiWTDVI0jjovKyJJWVlejp6UFcXJzP+LPPPovt27cDAPbs2QOlUomqqirv7V9++SVOnDgBm82G1NRU7Nq1C1lZWbMaOxEREUWHqGySiIiIiGaaKJYAICIiIppuUfmdpJnwzTff4PTp07hy5QokEgkWL16M0tJSrFixYtLtxk/h3bx5EykpKSgrK0NmZuYsRT11JpMJH3/8MS5fvgybzYYDBw7g0UcfnXSbo0eP4vPPP0dsbKx3bOXKlXj11VdnOtxpE0reHo8HR48eRWtrK4aHh/HQQw+hoqICixcvnqWop8f333+PTz75BFarFSqVCqWlpXjiiSf8zo/Gegdbq8HBQdTV1aGrqwsA8Pjjj6OiomLavtcwW4LNu6KiAr29vZBK/++jYOfOndi8efNshTxlZ8+eRXNzM8xmM+x2O7799tsJfwl9K7HUOti8xVBrADhy5Ai6urpgtVoxf/58ZGVlYefOnbjnnnv8buN0OlFfXw+9Xg+Xy4XMzExUVlZOus04Hkn6z1y91IlMJkNubi7efvvtoLZ7+OGH0dbW5v0XyR+YQkLJ+8SJE2hra8O7776L5uZmLF++HNXV1d7lIqLBhQsXUFNTg9LSUrS2tqKkpAQ1NTW4ePHipNtFW72DrVVNTQ1sNhuOHz+O48ePw2azBf2aiASh7KPbtm3zqW20fWjK5XJotVqUlZUFNF8stQ42byD6aw0AEokEe/bsQXNzM44dOwbg9tenq6+vx++//47Dhw/jiy++gEKhwL59+zA2Nnbbx2OT9J+5eqmT1NRUbNy4Eenp6eEOZVaFkndLSwueeeYZLFmyBHFxcSgpKYHL5UJHR8cMRjq9Tp8+jezsbOTl5UEqlSIvLw8ajQYtLS3hDm1aBVMri8WC7u5u6HQ6JCYmIjExETqdDj/++COsVmsYog+dGPbRYGk0Gqxdu3bSxYTHianWweQtJjt27EB6ejpkMhnkcjkKCgpgNpsxODgoON/pdKK9vR3PP/88VCoV7rjjDpSVlaGvrw8Gg+G2j8cmyQ9e6mRyJpMJmzdvxrZt2/Dmm2/6XblcLIaGhmCxWLBs2TLvWExMDNLS0nD58uUwRhacUPfZaKp3sLUymUyQyWRQq9XeMbVaDZlMFlWv5VD30VOnTmHTpk0oKirCkSNHourIaLDEUutQibHW586dg1KphEKhELz9ypUrGBkZ8XldJCYmIjk5OaD3btF/JymSLnUym0LJO1B5eXnIz8+HUqnE33//jcOHD2P37t1obGwMeDHQmTJTedvtdgAT196Qy+Xe28Ip0Lz97bPDw8N+t43kegsJtlZCz8lk8yNVKPvoCy+8gJSUFMjlcvzxxx+ora3F9evX8frrr894vOEgllqHQoy1/uWXX/DZZ59h//79fudM9b1b9E1SJF3qZDYFm3cwbv0S6MKFC1FdXY2NGzfCYDDgscceC/l+p8NM5Z2QkAAAE+o9NDSEpKSkkO5zOgWadyj7bCTXW0iwtRJ6Tsbnj99XNAhlH12+fLn3/2q1GmVlZXjppZcwMjIyYR06MRBLrUMhtlr/9NNPqKmpwd69e6HRaPzOu/V1cWuegdZc9E1SJF3qZDYFk/dUSSQSSCSSabmY4FTNVN5yuRwqlQpGoxGPPPIIAMDtdsNkMmH9+vXT/njBCjRvtVo94Uvaly5d8jn9cDuRVG8hwdZKrVbD5XLBbDZ7T6+bzWa4XK6gnpdwm459dPwSTJFa26kSS62nQzTX+syZM6irq8Nrr702aYMEACkpKYiLi4PRaEROTg4AoL+/HxaLBWlpabd9LH4n6T8GgwGVlZUoKCgIqEEC/r3USVtbG86fPw+Xy4WWlpZJL3USiTweD5xOJ5xOJwBgdHQUTqcTbrfb7zZ6vR79/f0AgBs3buC9997DXXfd5fObSqQLJW+tVouTJ0+ir68PIyMjaGpqglQqRW5u7myFPWWbNm1CV1cXOjo6MDo6io6ODnR3d+Ppp5/2u0001juYWqlUKmRnZ6OhoQH9/f3o7+9HQ0MDVq5cCaVSGYboQxdM3jdu3MDPP/8Mh8MBj8eDvr4+1NfXIycnB/Pnzw9D9KFxu91wOp1wuVwA4H1dC/3lkphqHUzeYqk18O+yOx9++CHeeuut2zZIABAbG4v8/Hw0NTXBarXCbrejvr4eqampAb2HccXt/8zVS51YLBYUFBRMGH/uuedQXFwMACguLsa6deu8z8O+ffvQ29uLf/75BwqFAhkZGSgpKcF99903m6FPSSh5ezweNDU14auvvoLdbkd6ejrKy8uxZMmS2Qx9yr777jt8+umnsFgs3nWS8vLyvLeLod6T1cpqtaK4uBi1tbXIyMgAAAwMDKCurg7d3d0AonftnGDytlgs2L9/P65evQq32427774bubm5KCoqiqpTT+3t7aitrZ0wfvDgQSQnJ4u21sHkLZZaA8CTTz6JmJgYyGQyn/Fba7xhwwZUVVV5j6Deuk6S0+lEZmYmqqqqAloniU0SERERkQCebiMiIiISwCaJiIiISACbJCIiIiIBbJKIiIiIBLBJIiIiIhLAJomIiIhIAJskIiIiIgFskoiIiIgEsEkiIiIiEsAmiYiIiEgAmyQiIiIiAWySiIiIiARIwx0AEdFMGBwcxLFjx+B2u3Ht2jWsXr0a69atQ0NDAzweDwYHB7F9+3Y88MAD4Q6ViCIUmyQiEh2Xy4VDhw5Bp9MhKSkJFosFhYWF6OzsxIsvvog///wTr7zyChQKBcrLy8MdLhFFKJ5uIyLROXXqFLRaLZKSkgAAsbGx8Hg8UKlUSE5OxtjYGBYtWoQ1a9Z4t/F4PDhz5gwOHjwYrrCJKMLwSBIRic6dd96JjIwM788XL14EAGg0GgBAdnY2srOzvbefPXsWRqMR58+f5+k3IvLikSQiEp3169f7/Pzbb78hJiYGK1asEJy/Zs0a7Nq1iw0SEflgk0REovfrr78iLS0NCQkJ4Q6FiKIImyQiErWBgQGYzWZkZWX5jLe2toYpIiKKFmySiEhUbt68CZ1Oh8bGRgDAuXPnMDY2hqVLl/rMMRgM4QqRiKIEmyQiEpWenh4YjUZIpVKMjIxAr9cjKSkJDocDAOBwOPDRRx+huLg4vIESUcTjX7cRkahoNBo89dRTsNlseP/997Fjxw4MDw+jsbERPT09GB0dRWFhIZRKZbhDJaIIxyaJiEQlPj4eL7/88oTxDz74IAzREFE04+k2IiIiIgE8kkREc94PP/yAzs5OdHZ2wuPxoLa2Fjk5OVi1alW4QyOiMJLo9XpPuIMgIiIiijQ83UZEREQkgE0SERERkQA2SUREREQC2CQRERERCWCTRERERCSATRIRERGRADZJRERERALYJBEREREJYJNEREREJOB/nT0WGPcv3SMAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 640x480 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JvpNQqRXWNkS",
        "colab_type": "text"
      },
      "source": [
        "In this plot, each point represents a example in our toy dataset. Also, we use colors blue and red to represent the class of each example.\n",
        "\n",
        "The above example is for a 2-dimensional dataset so that we can visualize them. Nevertheless, this geometric interpretation can also be used for high dimensional datasets."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IPOf31zBjY7l",
        "colab_type": "text"
      },
      "source": [
        "The geometric interpretation is useful because we can view the distance between two points as a kind of similarity measure between the corresponding examples: the closer the two points are, the more similar they are. \n",
        "\n",
        "The image below (source) illustrates this concept in the simple case of 2-dimensional points. But you should convince yourself that this interpretation of *distances as similarities* can be extended to $n$-dimensional examples $\\mathbf{x} = [x_0, x_1, x_2, \\cdots, x_n]$, $n > 2$. \n",
        "\n",
        "![Source: Wikipedia](http://chrisjmccormick.files.wordpress.com/2013/08/2d_euclidean_distance_illustration.png)\n",
        "\n",
        "In the particular case of a binary classification task, consider that points $A$ and $B$ belong to the positive and negative classes, respectively. Then, if an unclassified point $C$ is closer to point $B$ than to point $A$, we would expect $C$ to belong to the negative class.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BT5ph5TBkETh",
        "colab_type": "text"
      },
      "source": [
        "# Distance measures\n",
        "\n",
        "$k$-NN uses some distance measure to compute the similarity between pairs of points $\\mathbf{u}$ and $\\mathbf{v}$ in a $n$-dimensional space. Some popular measures are listed below.\n",
        "\n",
        "## $L_p$ norms\n",
        "\n",
        "$L_p$ norm (aka Minkowski distance) is actually a family of distance measures adequate for continuous features.\n",
        "\n",
        "$$\n",
        "{\\begin{aligned}\n",
        "L_p(\\mathbf {u} ,\\mathbf{v} ) &= \\|\\mathbf{u} -\\mathbf {v} \\|_{p} = \\\\\n",
        "\t& = {\\sqrt[p]{(u_{1}-v_{1})^{p}+(u_{2}-v_{2})^{p}+\\cdots +(u_{n}-v_{n})^{p}}} = \\\\\n",
        "\t&\t=\t{\\sqrt[p]{\\sum _{i=1}^{n}(u_{i}-v_{i})^{p}}}\n",
        "\\end{aligned}}\n",
        "$$\n",
        "\n",
        "We can get a particular distance by fixing the value o $p$ in the equation above. In particular, both $L_1$ and $L_2$ norms, defined bellow, are special cases of the $L_p$ norm:\n",
        "\n",
        "* Manhattan Distance ($L_1$ norm)\n",
        "$$\n",
        "{\\begin{aligned}\n",
        "L_1(\\mathbf{u},\\mathbf{v} ) &= \\|\\mathbf{u} -\\mathbf{v} \\|_{1}= \\\\\n",
        "& = \\sum_{i=1}^{n}|u_{i}-v_{i}|\n",
        "\\end{aligned}}\n",
        "$$\n",
        "\n",
        "* Euclidean Distance ($L_2$ norm)\n",
        "$$\n",
        "{\\begin{aligned}\n",
        "L_2(\\mathbf {u} ,\\mathbf {v} ) &= \\|\\mathbf {u} -\\mathbf{v} \\|_{2} = \\\\\n",
        "\t& = {\\sqrt{(u_{1}-v_{1})^{2}+(u_{2}-v_{2})^{2}+\\cdots +(u_{n}-v_{n})^{2}}} = \\\\\n",
        "\t&\t=\t{\\sqrt {\\sum_{i=1}^{n}(u_{i}-v_{i})^{2}}}\n",
        "\\end{aligned}}\n",
        "$$\n",
        "\n",
        "## Cosine distance\n",
        "\n",
        "The cosine distance (aka cosine similarity) is also adequate for both continuous and binary features. Its value ranges between 0 and +1, since it corresponds to the cosine of the angle between $u$ and $v$. Both $\\mathbf{u}$ and $\\mathbf{v}$ are considered to be vectors located in the first quadrant.\n",
        "\n",
        "$$\n",
        "1 - \\cos(\\theta) = 1 - \\frac{\\sum_{i=1}^{n}{u_i v_i}}{\\sqrt{\\sum_{i=1}^{n}{u_{i}^2}}\\sqrt{\\sum_{i=1}^{n}{v_{i}^2}}}\n",
        "$$\n",
        "\n",
        "$$\n",
        "1 - \\cos(\\theta) = 1 - \\frac{\\mathbf{u} \\cdot \\mathbf{v}}{\\|\\mathbf {u}\\| \\|\\mathbf{v}\\|}\n",
        "$$\n",
        "\n",
        "In the equation above, $\\mathbf{u} \\cdot \\mathbf{v}$ is the dot product between vectors $\\mathbf{u}$ and $\\mathbf{v}$:\n",
        "\n",
        "$$\n",
        "\\mathbf{u} \\cdot \\mathbf{v} = \\sum_{i=1}^{n}{u_i v_i}\n",
        "$$\n",
        "\n",
        "## Hamming Distance\n",
        "\n",
        "The Hamming distance is adequate for binary features only. This distance considers that each feature is binary. In the equation bellow, $h(u_{i}, v_{i}) = 0$ if $u_{i} = v_{i}$, and $h(u_{i}, v_{i}) = 1$ if $u_{i} \\neq v_{i}$.\n",
        "\n",
        "\n",
        "$$\n",
        "H(\\mathbf {u} ,\\mathbf {v} ) = \\sum _{i=1}^{n} h(u_{i}, v_{i})\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bzlmRPUUDaws",
        "colab_type": "text"
      },
      "source": [
        "As an example, the following code cell uses the Scipy function called [distance_matrix](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance_matrix.html) to compute the pairwise distances between points in a data matrix $X$. This function presents a parameter `p` that defines which Minkowski distance is to be used. In the example below, the Euclidean distance is used. In general, a distance matrix shows all the pairwise distances between points in a dataset. By definition, such matrix is symetric.\n",
        "\n",
        "The code also presents a heatmap, which is a graphical way to inspect a distance matrix. In such heatmap, an entry with a colder color correspond to a closer (i.e., more similar) pair of points. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m_GjdgiE2_4P",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 319
        },
        "outputId": "a952ca4a-bc0e-4949-d3c6-bd93c492c0f6"
      },
      "source": [
        "from scipy.spatial import distance_matrix\n",
        "import seaborn as sns\n",
        "import matplotlib.pylab as plt\n",
        "\n",
        "dists = distance_matrix(X, X, p = 2)\n",
        "\n",
        "ax = sns.heatmap(dists, linewidth=0.5)\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.6/dist-packages/statsmodels/tools/_testing.py:19: FutureWarning: pandas.util.testing is deprecated. Use the functions in the public API at pandas.testing instead.\n",
            "  import pandas.util.testing as tm\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAAD4CAYAAABPLjVeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3de7xVdZ3/8ddHQeJimpDc4UDpWONdNG36GXgXFLwMimkmmTiRo45jZWM/UiebLLNsJhJMKT2IgiJ3E03A+qUGMnIRyAwOcA4XFScVYVQ4n98fa1Gb09l77fVd++yz9+n95LEe7LPX+uz1PftsvqzzXd/1XubuiIhIeezT2g0QEflbok5XRKSM1OmKiJSROl0RkTJSpysiUkbtyrAPTY8QkWJZ1hf44I21Rfc57bsNzLy/tMrR6dJuv95BdbvebwBgfvdRQfVnbH2YmT0+F1QLMGLLQ9zW/9Kg2nHrJwOwpM95QfWD6mcAcHe/y4Lqr9tQy6qPDQuqBfjkH+fyztizg2r3H/8EAP/74oyg+g8dF71nX6+5JKj+jropAOyc+6Og+o7DrufNEZ8NqgU4aOYids66M2zfw28EYMePrg6q73T9BAB2Tvpa2P5Hf4/RNRcG1QJMqnuM9ceeFlTbf+nTwfutJmXpdEVEyqZxd2u3oCB1uiLStuze1dotKEidroi0Ke6Nrd2EghI7XTM7DBgB7BmYbQBmufvqlmyYiEiQxsrudAtOGTOzrwMPE51R/F28GDDFzG5q+eaJiKTkjcUvrSDpSPdK4O/d/YPcJ83sLuBl4LvNFZnZGGAMwIQJE0rQTBGRIlX4ibSkiyMagV7NPN8zXtcsd5/o7oPcfdCYMWOytE9EJJ0qP9K9HviVmf0B2Bg/1w/4OHBNSzZMRCSEV/PsBXf/pZkdCpzA3ifSFrt7ZR/Di8jfpgo/kZY4e8Gj+RfPl6EtIiLZVfiUMSvDnSOUvSAixcqchfDemkVF9zkdDvts28xeEBEpmwo/0i1Lp5slsAayBeZsHRIeXNJ9wSJO6j0kqPa5hgUAmQNzRvYfEVQ/bf1MDjv4+KBagDWvLaa2V1jYzmWbagHYNizsve86dxGQ/b2bHNj+SzfVZg59eaRnWNsv3hy1/Zs1YUFN3657CIDZPcLCgs7dMoUR/c4JqgWYuWEOV9WMDKq9t25a8H73Us0n0kREqk61n0gTEakmlT6xSp2uiLQtGtMVESmjCh9eCL5HmpmNLmVDRERKosIvA85yY8pb860wszFmtsTMlkycODHDLkREUtr9QfFLKyg4vGBmy/OtArrnq3P3icCe3tbn/99nwlonIpJWhQ8vJI3pdgfOBP6nyfMG/LZFWiQikkWVn0ibA3Rx95earjCzhS3SIhGRLKr5SNfdryywLvze5iIiLaVEna6ZfQh4FuhA1Fc+6u7farJNB+AB4DhgG3Cxu9cVfF0F3ohIBckcQLNz4f1F9zkdB38x7/7MzIDO7r7dzNoDvwGuc/fnc7YZCxzp7v9kZqOA89394kL7zDJ7QUSk8pRoyphHtsdfto+Xph36COAX8eNHgVPjzjqvslwcMbNH2EjEiC1ReEdoaE33BYuCw3IgCszZePypQbV9F/8KgJ1Tbwuq73jROAAm9AkLbbm6vjZz2M/KgWHBJ4evnQPA9hvDwnq63DkTgLevOiOo/sP3zgdg56/Cpit2PHUMO2fdGVQL0HH4jXzwxtqg2vbdBgKwc/74sH2fMRaAd64N+9nt/+M5LO0b9nMDOHbjTJb0OS+odlD9jOD97iXF8ELu/RxjE+PZV3vW7wu8SHS3nJ+4+wtNXqI38V113H2Xmb0FdAXeyLdPXZEmIm1LitkLTaa3Nrd+N3C0mR0IPG5mh7v7yizN0/CCiLQtjY3FL0Vy9z8BC4CzmqxqAPoCmFk74ACiE2p5qdMVkbalRGO6ZvbR+AgXM+sInA6sabLZLOAL8eN/BJ7xhNkJicMLZnYY0bjFCzmDypjZWe7+y6R6EZGy2lWyEPOewC/icd19gKnuPsfMbgOWuPss4D7gQTN7FXgTSLxjQ9JlwNcCXwFWA/eZ2XXuPjNe/R2g2U43d3B6woQJ+a8XFhEptRJdkebuy4Fjmnl+XM7j/wVS3Soj6Uj3KuC4eJ5aDfComdW4+90UmE/XNHth5riFadokIhKumq9IA/bZM6Tg7nVmNpio4+1PCSYxi4iUXIVnLySdSNtqZkfv+SLugM8BugFHtGTDRESCtMDshVJKOtK9HNhrVNrddwGXm9mEFmuViEioCj/STQq8qS+w7v+VvjkiIhmVbvZCi1DgjYhUkuyBN4/cWnzgzcXfKvu5qbJcBnxb/0uD6satnwzASb2HBNU/17AgODsBovyE0OyGXe83AHB1TarZJH82oW4aAJ/vf0FQ/YPrpzO65sKgWoBJdY+xvObcoNoj62YD8O7tlwfVd775AQDO7Ht2UP2TG58AYO0RYdkNA1fM5+aa8OTS2+seYsWAsPfuiHXRezeve+J0z2YN3fowQKbMkAFdjwqqBVi3bRnj+4blhYzdWBu8371U+ewFEZHqok5XRKSMqvlEmohI1dm9u7VbUFAx2QsnEOX5LjazTxKl7Kxx93kt3joRkbSqeXjBzL4FnA20M7OngE8RxZvdZGbHuPvtZWijiEjxqrnTJYoqO5roxmxbgD7u/raZ3Qm8ADTb6TYNvBERKZsqH9PdFSen7zCzP7r72wDuvtPM8n5nTQNvbrt9UWlaKyKSwBsr+9KApE73fTPr5O47iG4xDICZHQBU9n8nIvK3qcqHF0529/cA3Pc6Zm/PX9LSRUQqRzXPXtjT4Tbz/BsUuNuliEirqfIjXRGR6lLhna4Cb0SkkmQOoNnxo6uL7nM6XT+hbQbeLOlzXlDdoPoZQLbAnJ1TbwuqBeh40bjMgTVZA3OyvHfTeoa9bwAjN0/m3VsuCartfMsUAN5bvSCovsMnooCjEf3OCaqfuWEOANvO/WxQfdfZi4KDhiAKG3qm+0VBtadsnQrAwu5hn7vBW6PPXZawodB/bxD9m9v06bCAql6/Dfu8/JUKP9LV8IKItC1VPmVMRKS6VPPsBRGRauMVPryQdGPKv2JmD7REQ0RESqLRi18KMLO+ZrbAzFaZ2ctmdl0z2ww2s7fM7KV4GZfUvKTAm1lNnwKGmNmBAO4+PGkHIiJlVbrshV3Av7r7UjPbH3jRzJ5y91VNtvu1uxd91jdpeKEPsAr4GdHULwMGAT8oVNQ08ObYYlsjIpJViU6kuftmYHP8+B0zWw30JuoTgyUNLwwCXgRuBt5y94XATndf5O55U2zcfaK7D3L3QWPGjMnSPhGRdHbtLnoxszFmtiRnabbDMrMa4BiidMWmTjKzZWb2hJn9fVLzki4DbgR+aGbT4r+3JtWIiLSqFMMLTRIRm2VmXYDHgOv3JC3mWAr0d/ftZjYUmAEcUuj1ijqR5u717j4SeAIo0S07RURaQIlOpAGYWXuiDneyu09vut7d33b37fHjeUB7M+tW6DVTHbW6+1xgbpoaEZFyKtWUMTMz4D5gtbvflWebHsBWd/f41mb7ANsKva6GCkSkbSndFWn/AHweWGFmL8XP/RvQD8Dd7yG6u86XzWwXsBMY5QmBNgq8EZFKkjmAZvtXzy+6z+ny/cfbZuDN3f0uC6q7bkM0fDyy/4ig+mnrZzKhT9i+Aa6urw0OPnlwfTT8kzXsJ0tgziX9w/YNMGX9jExBQwDrjjo9qH7AsqcAqO0V9rO7bFP0uVlz6NCg+sNemRccOANR6My2YYFhO3OjSUGLe58fVH98w+MAzO0eFlY0bOsUzu93blAtwOMbZmcOKspMlwGLiJRPtd8jTUSkuqjTFREpowoPvEnV6ZrZZ4ATgJXuPr9lmiQikkGFH+kWvDjCzH6X8/gq4L+A/YFvmdlNLdw2EZH0SnhxREtIOtJtn/N4DHC6u79uZncCzwPfba6oaeCNiEi5+O7qHl7Yx8w+QnREbO7+OoC7vxtPBm5Wk+uZ/e5vP1uSxoqIJKrw4YWkTvcAopQxA9zMerr75jgAouyTikVEklT1lDF3r8mzqhEIm70tItKSqrnTzcfddwDrStwWEZHsKntIV9kLIlJRMg9b/umSIUX3OQdOWdA2sxdERMqmwo90y9LprvrYsKC6T/4xiu497ODjg+rXvLaYrUPCgkcAui9YxOiaC4NqJ9U9BsC0nmGhMSM3R6ExoaE1U9bPCA7LgSgw55s1nwuq/XbdQwCsGBAWnHLEutkAzOgRtv/ztkT7zxLYc0PNqKBagLvqHubnvcPCeq5oiMJ6xtZcFFQ/vm4qALcHfu83r5/MjTVhYTkAd9ZN4bS+ZwbVPr3xyeD95qrqE2kiIlVHR7oiIuWjI10RkXKq5iNdM/sU0f2B3jazjsBNwLFE933/jru/VYY2iogUzfNeK1sZku4GfD+wI358N9EVanfEz03KV5R7L/mJEwve3VhEpKS8sfilNSRmL7j/+f+NQe5+bPz4Nzk3avsrTbMXVt0xM2MzRUSKVOHDC0lHuivNbHT8eJmZDQIws0OBD1q0ZSIiASr9SDep0/0S8Fkz+yPwSeA5M1sL3BuvExGpKJXe6SYF3rwFXGFmHwYGxNvXu/vWcjRORCQt313ZAYhJR7oAuPvb7r7M3V9UhysilaxUR7pm1tfMFpjZKjN72cyua2YbM7Mfm9mrZrbczI5t7rX2qlHgjYhUkMyHqZs/U3zgTc/f5A+8MbOeQE93X2pm+xNli5/n7qtythkK/DMwFPgUcLe7f6rQPos60hURqRalOtJ1983uvjR+/A6wGmgaaDICeMAjzwMHxp11XmW5Iu2dsWcH1e0//gkAanuFhYdctqmWlQPPCaoFOHztHJbXhIW2HFkXhba8e0tYeEjnW6YA2UJbQgNrIAqtCQ3M2fV+AwCX9b8gqL52/XQAtt8wPKi+y12zotfJ8LnZcvLgoFqAHs8uZNuwsKClrnMXAfBsj5FB9SdvmQbAkD6nB9UvqH8qOKgIorCiE3sNDqp9ftPC4P3mci/+YDn3fo6xifGU16bb1QDHAC80WdUb2JjzdX383OZ8+9RlwCLSpqSZldDkmoJmxbcnewy43t3fztQ41OmKSBvTWMLZC2bWnqjDnezu05vZpAHom/N1n/i5vDSmKyJtijda0UshZmbAfUT5M3fl2WwWcHk8i+FE4C13zzu0AMmBN9cCj7v7xkLbiYhUiqTONIV/AD4PrMiJPfg3oB+Au98DzCOaufAqUSbN6GZeZy9Jwwv/DtwUX5E2BZjm7q8nvWju4PSECRMIz6EXEUmnVLNg3f03JExh82jO7VfSvG5Sp7sWOA44DbgYuNXMXiTqgKfH0yiaa8hegTfvjH08TZtERIKV8Ei3RSSN6bq7N7r7fHe/EugFjAfOIuqQRUQqirsVvbSGpCPdvVrl7h8QDRzPMrNOLdYqEZFAuys8eyGp07043wp335FvnYhIa2mtI9hiJaWMvVKuhoiIlEKlj+kq8EZEKknmHnP1IUOL7nM+8Yd5Ze+hy3JF2v++OCOo7kPHnQeQ6Tr27TeOCKoF6HLnTN69/fKg2s43PwDAe6sXBNV3+MQQANYdFXYN/YBl2a+hz5qdkDW74b3lTwbVdzjyTACe6X5RUP0pW6ey4+5/CqoF6HTdPbx7W1hmRudxkwGCsx96PLsQgAv6h+VWTF8/ix3f/2JQLUCnr97P+L5hmRdjN9YG7zdXpR/p6jJgEWlTdjdW9oW26nRFpE1p+RHTbNTpikib0ljNsxfMbD9gFLDJ3Z82s88BnyYK850Yz9sVEakYVT1lDJgUb9PJzL4AdAGmA6cCJwBfaNnmiYikU+3DC0e4+5Fm1o4oI7KXu+82s1pgWb6ipoE3lx93cMkaLCJSSFUPLwD7xEMMnYFOwAHAm0AHoH2+oqaBN6FTxkRE0qr22Qv3AWuAfYGbgWlmthY4EXi4hdsmIpJahY8uJF4G/EMzeyR+vMnMHiCKebzX3X9XjgaKiKRR7cMLuPumnMd/Ah5t0RaJiGRQ7bMXRESqSoqbAbcKBd6ISCXJfJj6bI+RRfc5J2+Z1jYDb75eE3aXtDvqpgBwW/+w8JBx6yfz9lVnBNUCfPje+ZzZ9+yg2ic3PgHAiH7nBNXP3DAHgNpeYeEhl22qZUaPzwXVApy35SG23xAWmtLlrllA9sCarIE5279xYVB9l/94jPv6hL3vAFfW12YKaQJoOOmUoPrezz0DwI67rgqq73TDvZzTb1hQLcCcDXNZe0TYv7mBK+YH7zfXLg0viIiUj2c/WG5R6nRFpE2p9DHdyp5FLCKSkmNFL0nM7H4ze83MVuZZP9jM3jKzl+JlXNJrJh7pmtlA4AKgL7AbeAV4yN3fTmyxiEiZlfhI9+fAfwEPFNjm1+5e9Mmbgke6ZnYtcA/wIeB4ost/+wLPm9ngYnciIlIuu7GilyTu/ixR9EHJJB3pXgUcHYfc3AXMc/fBZjYBmAkc01xR08AbEZFySXO3nty+KjYxzo5J4yQzWwZsAm5095cLbVzMibR2RMMKHYiiHXH3DWZWdODN178Tdp8wEZG0GlPMXmjSV4VYCvR39+1mNhSYARxSqCDpRNrPgMVmdi/wHPATADP7KCU+5BYRKQVPsWTel/vb7r49fjwPaG9m3QrVJAXe3G1mTwOfAH7g7mvi518HTi5Bm0VESqqcU8bMrAew1d3dzE4gOpDdVqimmMCbl4GCYxQiIpWi0Up3cYSZTQEGA93MrB74FnGWuLvfA/wj8GUz2wXsBEZ5QraCLo4QkTZldwlfy90LZhi4+38RTSkrmgJvRKSSZD5MndLr0qL7nEs2TW6bgTc75/4oqK7jsOsBmBwY+nLpplp2/ir8xGTHU8dkDu/Ydm5g8MnsKPhkzaFDg+oPe2VecFAQRGFBWcJ2AJ7pflFQ/SlbpwLZAmsgW2DOz3uHB95c0VDLtTUXB9X+uO4RAAb3OS2ofmH90wCMrQl778fXTeWNM8M+swDdnlzE+L5h793YjbXB+82VZvZCa9Dwgoi0KZX+q7U6XRFpU9JcHNEa1OmKSJtS6Slj6nRFpE3ZrSNdEZHyqfQj3aSUsQPM7LtmtsbM3jSzbWa2On7uwAJ1Y8xsiZktmTgxy2XNIiLpNKZYWkNS9sJU4H+Awe5+kLt3BYbEz03NV+TuE919kLsPGjNmTL7NRERKzq34pTUkdbo17n6Hu2/Z84S7b3H3O4D+Lds0EZH0qv1Id72Zfc3Muu95wsy6m9nXgY0t2zQRkfR2p1haQ1KnezHQFVgUj+m+CSwEDgJGtnDbRERSa7Til9YQnL1gZqPdfVIRm1b6BSIiUjkyd4U/7HdZ0X3Ov2yoLXvXm+VuwLeWrBUiIiVS6WO6BefpmtnyfKuA7nnW/ZU3R4QFaBw0Mwp9GV0TFnwyqe4xds66M6gWoOPwG7m55nNBtbfXPQTA5/tfEFT/4PrpACzsHjaKM3jrNG6oGRVUC3BX3cNsOXlwUG2PZxcCsOPufwqq73TdPQDc1ycsOOXK+ig4JTS05oqG2uCwHIgCcy4L/LnXxj/3rPXrjjo9qH7AsqeYlCHsZ3RDbeago6wq/VfrpIsjugNnEk0Ry2XAb1ukRSIiGVR79sIcoIu7v9R0hZktbJEWiYhk0FqzEoqVdI+0KwusC/u9W0SkBTVW+ACDshdEpE2p6uyFUMpeEJHWUs5bsIcIPtI1syfc/ezm1rn7RGBPb+tvzp0cuhsRkVQq/Ug3acrYsflWAUeXvjkiItnssuoe010MLKL5q0TyRjuKiLSWyu5ykzvd1cDV7v6HpivMTIE3IlJxSjm8YGb3A+cAr7n74c2sN+BuYCiwA7jC3ZcWes2kE2m3FNjmn5MaLCJSbo140UsRfg6cVWD92cAh8TIG+GnSCyrwRkQqSebryb5Wc0nRfc736qYk7s/MaoA5eY50JwAL3X1K/PXviW76sDnf6ynwRkTalDSBN7nTW+Ml7a1uerN3tnh9/FxeZQm8CQ2d6Tj8RgAe6XlpUP3FmyfzwRtrg2oB2ncbyIoB5wbVHrFuNkDm8I9tw8LCgrrOXRQc+AJR6EuWfQO8e1vYz63zuGiKYdb9X1tzcVD9j+seCQ6cgSh0JjQwZ9f7DQCc1HtIUP1zDQsAWDnwnKD6w9fOYeuQsPcdoPuCRaw5dGhQ7WGvzAveb67dKX65bjK9tSwUeCMibUqZ5+k2AH1zvu4TP5eXAm9EpE3x8p5GmgVcY2YPA58C3io0ngsKvBGRNqbEU8amAIOBbmZWD3wLaA/g7vcA84imi71KNGVsdNJrKvBGRNqUUqaMufslCesd+Eqa11TgjYi0KVUdeGNmHwa+QTQ4/IS7P5Szbry7j22urmngTZZb5oiIpLGrwi8NSDrSnUQ0U+ExYJSZPWZmHeJ1J7Zoy0REAniKP60haUz3Y+6+566QM8zsZuAZMxvewu0SEQlS1dGOQAcz28fdGwHc/XYzawCeBbq0eOtERFJqrSPYYiUNL8wGTsl9wt1/Dvwr8H4LtUlEJFiay4BbgwJvRKSSZA68uaz/BUX3ObXrp5f9hu1Z5uneSnSiLdGOH10dtINO108A4Js1YddhfLvuIXbOHx9UC9DxjLHM6z4qqHbo1ocBWNh9ZFD94K3TAFjc+/yg+uMbHmdsTVjuA8D4uqk82yOs7Sdvidq+5eTBQfU9nl0IQMNJpxTeMI/ezz0DwOA+pwXVL6x/OnP2QtbshKzZDff2CcvduKq+luU1YXkjAEfWzWZSYObH6Iba4P3mquq7AZcq8EZEpFwqfUxXgTci0qZU++wFBd6ISFWp6uEFBd6ISLWp9uEFEZGqsjtwRla5FJyna2Y9zOynZvYTM+tqZreY2Qozm2pmPQvUKfBGRFpFiW9MWXJJF0f8HFhFdA+gBcBOouzIXwP35Cty94nuPsjdB40Zk/aWQyIi4Sr94ojE2Qvu/p8AZjbW3e+In/9PM8s73isi0lqqfUw390j4gSbr9i1xW0REMqvq2QvATDPr4u7b3f2be540s48Dv2/ZpomIpBcabVAuSVPGxuV5/lUzm9syTRIRCZfmFuytIUvgzQZ371fEppX9DohIJckcQHNa3zOL7nOe3vhkZQXelCp7Yeekr6Vp0591HP09AGb3KHhvuLzO3TKFd649J6gWYP8fz2Hj8acG1fZd/CsA3r398qD6zjdHQ+hzu4d978O2TuH2/pcG1QLcvH4yQ/qcHlS7oP4pAC7oH5Z1P339LAB23HVVUH2nG+4FCA78GV83lXVHhX3vAAOWPcXKgWGfu8PXzgGyBdZAtsCcrUM+G1QL0H3BouCwoNr104P3m6uqhxdQ9oKIVJlqP5Gm7AURqSqVPmWs4MUR7n6lu/8mzzplL4hIxdntXvSSxMzOMrPfm9mrZnZTM+uvMLPXzeylePlS0msqe0FE2pRSDS+Y2b7AT4DTgXpgsZnNcvdVTTZ9xN2vKfZ1ky4Dbq4hB6etEREplxJmL5wAvOrua939feBhYETW9iUF3hzUZOkK/M7MPmJmBxWoU+CNiLQKdy96ye2r4iU3LKY3Ue7MHvXxc01daGbLzexRM+ub1L6k4YU3gPVNnusNLCWafzuwuSJ3nwjs6W09dMqYiEhaaYYXmvRVIWYDU9z9PTO7GvgFTe6g3lTS8MJXiS73He7uA9x9AFAfP262wxURaU2e4k+CBiD3yLVP/Nxf9uW+zd3fi7/8GXBc0osmzV74AfAlYJyZ3WVm+6MrzESkgu32xqKXBIuBQ8xsgJntB4wCZuVu0CRXfDiwOulFE2cvuHs9MNLMhgNPAZ2SakREWkuprkhz911mdg3wJFGq4v3u/rKZ3QYscfdZwLVx37gLeBO4Iul1U2UvmFlH4GPuvtLMRrv7pGLaXvQORORvXeYshKN6fLroPmfZlt+WPXsh1ZQxd9/p7ivjL29tgfaIiGRSwjHdFlGWwJvRNRemadOfTap7DIAR/cLCQ2ZumMPSvuHT6o7dOJMBXY8Kql23bRkAtwWGzoxbPxmA8/udG1T/+IbZ3FgTFpYDcGfdFFYMCNv3EetmA7Dj+18Mqu/01fsBOKffsKD6ORui1NE3zgwLbun25CIm9Q4LnAEY3VAbHBrTfcEiAJbXhL33R9ZF732W/YeG5UAUmDMhMKzn6jisJ6tGBd6IiJRPpWcvKPBGRNqUImYltKqkO0fkvfmkAm9EpBJV+/CCiEhVqfbhBRGRqlLpR7pJgTdn5Tw+wMzui4MdHjKzvLMXFHgjIq2l0qeMJc3T/U7O4x8Am4FziS6Pm5CvyN0nuvsgdx80ZsyYfJuJiJTcbt9d9NIa0gwvDHL3o+PHPzSzL7REg0REsqj2G1MebGY3EM3L/bCZmf/lO0odgC4i0tKq/caU9wL7x49/AXQDXjezHsBfzd0VEWltlX6kmyrwZq9CBd6ISOllDqDpeeAni+5zNv9pVWUH3jShwBsRqTiVPnuhLIE36489LU2b/qz/0qcBuKpmZFD9vXXTWNLnvKBagEH1MxjfNyy8Y+zGKLxj06eHBNX3+u0CIFvYz2l9zwyqBXh645Oc2GtwUO3zmxYCZH7v1h5xRlD9wBXzM+//me4XBdUCnLJ1KmsOHRpUe9gr8wCCA3dGN0Tv3WX9Lwiqr10/PTiwBqLQmtDAnF3vNyRvVISqvgwYBd6ISJWp9DFdBd6ISJtS6VekKfBGRNqUaj/SFRGpKpU+Tzf17AUz61rENspeEJFW4e5FL60hKfDmu2bWLX48yMzWAi+Y2Xozy3s/EGUviEhrKeEt2FtE0pHuMHd/I378feBid/84cDpRAI6ISEVpdC96aQ1JY7rtzKydu+8COrr7YgB3f8XMOrR880RE0qn0E2lJR7rjgXlmdgrwSzO728w+a2a3ouwFEalApbwizczOMrPfm9mrZnZTM+s7mNkj8foXzKwm6TWTpoz9p5mtAL4MHBpvfwgwA/j3xBaLiJRZqY50zWxf4CdEw6n1wGIzm+Xuq3I2uxL4H3f/uJmNAu4ALi74ugq8EZEKkjmApt1+vYvuc3a935B3f2Z2EnCLu58Zf/0NAHf/j5xtnoy3ec7M2gFbgI96gYm8o8IAAAbQSURBVI61HIE3Vmgxs6uTtqnU+mpuu753fe8Vuu/Mdr3fYMUuudNb4yV3ulVvYGPO1/XxczS3TXzu6y2g4LTapCljy/MsK0gReJMg65yy1qyv5rZnra/mtmetr+a2Z61v7baXVO701nhp8QsLFHgjItK8BqBvztd94uea26Y+Hl44ANhW6EUVeCMi0rzFwCFmNoCocx0FNM2cmQV8AXgO+EfgmULjuVAZgTdZD+dbs76a2561vprbnrW+mtuetb6121427r7LzK4BngT2Be5395fN7DZgibvPAu4DHjSzV4E3iTrmgoJnL4iISHq6o6+ISBmp0xURKaNW7XSTLrFLqL3fzF4zs5UB++1rZgvMbJWZvWxm16Ws/5CZ/c7MlsX1twa0YV8z+28zmxNQW2dmK8zsJTNbElB/oJk9amZrzGx1PAm82Nq/i/e7Z3nbzK5Puf9/id+3lWY2xcw+lKL2urju5WL229znxMwOMrOnzOwP8d8fSVk/Mt5/o5kNCtj/9+P3frmZPW5mB6as//e49iUzm29mvYqtzVn3r2bmFqcIptj3LWbWkPPzz3szuHz7N7N/jr//l83se/nq26w02ZOlXIgGpv8IDAT2A5YBn0xRfzJwLLAyYN89gWPjx/sDr6TctxHN6gBoD7wAnJiyDTcADwFzAtpfB3TL8N7/AvhS/Hg/4MAMP8MtQP8UNb2BdUQBSgBTgSuKrD0cWAl0IjoJ/DTw8bSfE+B7wE3x45uAO1LWfwL4O2AhMChg/2cA7eLHdwTs/8M5j68F7im2Nn6+L9HJofWFPkd59n0LcGORP6/m6ofEP7cO8dcHh36Oq3VpzSPdE4BX3X2tu78PPAyMKLbY3Z8lOluYmrtvdvel8eN3gNX89ZUmherd3bfHX7aPl6LPSJpZH2AY8LOiG10iZnYA0T+G+wDc/X13/1Pgy50K/NHd16esawd0jOc1dgI2FVn3CeAFd9/h0dU/i4CCt73N8zkZQfQfD/HfeW8Z3Vy9u692998X0+A89fPj9gM8TzT/M0392zlfdibPZ6/Av5EfAl/LV1dEfVHy1H8Z+K67vxdv81ro61er1ux0i7nErsWZWQ1wDNHRapq6fc3sJeA14Cl3T1P/I6IPfWiKsgPzzezFJpctFmMA8DowKR7e+JmZdQ5sxyhgSpoCd28A7gQ2AJuBt9x9fpHlK4H/Y2ZdzawTMJS9J68Xq7u7b44fb6F0V1eG+CLwRNoiM7vdzDYClwLjUtSNABrcfVnafea4Jh7euL/Q0EwehxL9DF8ws0VmdnyGdlSlv+kTaWbWBXgMuL7J0UMid9/t7kcTHaWcYGaHF7nPc4DX3P3F1A3+i8+4+7HA2cBXzOzkFLXtiH7l+6m7HwO8S/Qrdipmth8wHJiWsu4jREeaA4BeQGczu6yYWndfTfTr+Hzgl0TxorvT7L+Z13RaKZTJzG4GdgGT09a6+83u3jeuvabI/XUC/o0UnXQzfgp8DDia6D/NtDczaAccBJwIfBWYamYlyVyoFq3Z6RZziV2LMbP2RB3uZHefHvo68a/mC4Cziiz5B2C4mdURDamcYma1KffZEP/9GvA40VBNseqB+pwj80eJOuG0zgaWuvvWlHWnAevc/XV3/wCYDny62GJ3v8/dj3P3k4kuT38l5f4BtppZT4D477L/imtmVwDnAJfGHX+oycCFRW77MaL/7JbFn78+wFIz61Hsztx9a3zA0QjcS7rPHkSfv+nxEN3viH7by3syry1qzU73z5fYxUdNo4guqWtx8f+s9wGr3f2ugPqP7jnjbGYdifI21xRT6+7fcPc+7l5D9D0/4+5FHenF++tsZvvveUx0UqboGRzuvgXYaGZ/Fz91KrCqQEk+l5ByaCG2ATjRzDrFP4dTicbUi2JmB8d/9yMaz30ooA17Lt0k/ntmwGsEM7OziIaXhrv7joD6Q3K+HEHxn70V7n6wu9fEn796ohPKW1Lsu2fOl+eT4rMXm0F0Mg0zO5ToRO4bBSvamtY8i0c0JvcK0SyGm1PWTiH69eYDog/PlSlqP0P0K+Vyol9RXwKGpqg/EvjvuH4lMC7w+x9MytkLRLM9lsXLy2nft/g1jgaWxO2fAXwkZX1nolCPAwK/71uJOoqVwIPEZ7KLrP010X8Sy4BTQz4nRNF7vwL+QHQm/aCU9efHj98DtgJPpqx/leh8xp7PXrOzDwrUPxa/d8uB2UDvkH8jJMyCybPvB4EV8b5nAT1T1u8H1MbtXwqcEvIZquZFlwGLiJTR3/SJNBGRclOnKyJSRup0RUTKSJ2uiEgZqdMVESkjdboiImWkTldEpIz+P6Mfmo1xTGyiAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 2 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WUKl4DdEAy5V",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 595
        },
        "outputId": "9bb1e09d-959a-4e8d-ff9f-13e292a44498"
      },
      "source": [
        "print(dists)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[0.    1.552 1.487 1.118 1.72  1.237 1.811 2.341 3.138 1.03  2.927 2.163\n",
            "  2.907 2.625 2.746 0.854 1.942]\n",
            " [1.552 0.    2.059 0.51  1.118 0.762 0.361 1.389 2.126 1.118 1.4   0.854\n",
            "  1.421 1.077 1.5   0.707 0.894]\n",
            " [1.487 2.059 0.    1.965 2.844 1.304 2.062 1.803 2.408 2.3   3.    2.907\n",
            "  3.421 2.973 2.377 1.726 1.72 ]\n",
            " [1.118 0.51  1.965 0.    0.9   0.825 0.854 1.769 2.55  0.64  1.903 1.063\n",
            "  1.789 1.53  1.972 0.283 1.273]\n",
            " [1.72  1.118 2.844 0.9   0.    1.712 1.442 2.506 3.22  0.707 2.147 0.825\n",
            "  1.603 1.616 2.55  1.118 2.012]\n",
            " [1.237 0.762 1.304 0.825 1.712 0.    0.781 1.118 1.924 1.389 1.838 1.616\n",
            "  2.126 1.703 1.513 0.721 0.707]\n",
            " [1.811 0.361 2.062 0.854 1.442 0.781 0.    1.077 1.78  1.476 1.118 1.\n",
            "  1.36  0.922 1.14  1.005 0.608]\n",
            " [2.341 1.389 1.803 1.769 2.506 1.118 1.077 0.    0.806 2.404 1.389 2.04\n",
            "  2.138 1.628 0.583 1.78  0.5  ]\n",
            " [3.138 2.126 2.408 2.55  3.22  1.924 1.78  0.806 0.    3.189 1.6   2.64\n",
            "  2.518 2.04  0.728 2.581 1.281]\n",
            " [1.03  1.118 2.3   0.64  0.707 1.389 1.476 2.404 3.189 0.    2.452 1.334\n",
            "  2.138 2.002 2.608 0.671 1.91 ]\n",
            " [2.927 1.4   3.    1.903 2.147 1.838 1.118 1.389 1.6   2.452 0.    1.36\n",
            "  0.949 0.566 0.922 2.102 1.281]\n",
            " [2.163 0.854 2.907 1.063 0.825 1.616 1.    2.04  2.64  1.334 1.36  0.\n",
            "  0.806 0.806 1.924 1.345 1.603]\n",
            " [2.907 1.421 3.421 1.789 1.603 2.126 1.36  2.138 2.518 2.138 0.949 0.806\n",
            "  0.    0.51  1.803 2.059 1.838]\n",
            " [2.625 1.077 2.973 1.53  1.616 1.703 0.922 1.628 2.04  2.002 0.566 0.806\n",
            "  0.51  0.    1.315 1.772 1.342]\n",
            " [2.746 1.5   2.377 1.972 2.55  1.513 1.14  0.583 0.728 2.608 0.922 1.924\n",
            "  1.803 1.315 0.    2.062 0.806]\n",
            " [0.854 0.707 1.726 0.283 1.118 0.721 1.005 1.78  2.581 0.671 2.102 1.345\n",
            "  2.059 1.772 2.062 0.    1.304]\n",
            " [1.942 0.894 1.72  1.273 2.012 0.707 0.608 0.5   1.281 1.91  1.281 1.603\n",
            "  1.838 1.342 0.806 1.304 0.   ]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sj5AiUauBJYs",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "a79000ce-111c-43ad-c51c-c3fa9996bc6c"
      },
      "source": [
        "print(X[3,:])\n",
        "print(X[15,:])\n",
        "print(np.sqrt(np.square(X[3,0]-X[15,0]) + np.square(X[3,1]-X[15,1])))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[-0.6  0.4]\n",
            "[-0.4  0.6]\n",
            "0.28284271247461895\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Ft1zQ-UHYqz",
        "colab_type": "text"
      },
      "source": [
        "# $k$-NN for classification"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kvg1kn9YHkdH",
        "colab_type": "text"
      },
      "source": [
        "## Definition of neighbors\n",
        "\n",
        "To classify an example $\\mathbf{x}$, $k$-NN produces a total order on the $\\mathbf{x}$ “neighbors”, taken from the training set $X$.\n",
        "\n",
        "The meaning of neighbor here is in the context of *similarity*. The classes of the $k$ most similar neighbors are used to predict the class of $\\mathbf{x}$.\n",
        "\n",
        "The following figure ([source](https://www.datacamp.com/community/tutorials/k-nearest-neighbor-classification-scikit-learn)) illustrates the behavior of $k$-NN for $k = 1$ in the context of binary classification. Notice that there is only one example inside the ball of neighbors for $\\mathbf{x}$. Hence $1$-NN would predict that $\\mathbf{x}$ belongs to the *red* class.\n",
        "\n",
        "![alt text](http://res.cloudinary.com/dyd911kmh/image/upload/f_auto,q_auto:best/v1531424125/Knn_k1_z96jba.png)\n",
        "\n",
        "In the case where $k$ is chosen to greater than 1, then the [majority rule](https://en.wikipedia.org/wiki/Majority_rule) is applied to predict the class of $\\mathbf{x}$. See the image below for the case $k=3$.\n",
        "\n",
        "![alt text](http://res.cloudinary.com/dyd911kmh/image/upload/f_auto,q_auto:best/v1531424125/KNN_final1_ibdm8a.png)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5Q-BIZzNRFn8",
        "colab_type": "text"
      },
      "source": [
        "Pr(pos) = 2/3\n",
        "Pr(neg) = 1/3\n",
        "\n",
        "![alt text](http://res.cloudinary.com/dyd911kmh/image/upload/f_auto,q_auto:best/v1531424125/KNN_final1_ibdm8a.png)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CgtFVJfD_THZ",
        "colab_type": "text"
      },
      "source": [
        "The animation below illustrates the behavior of $k$-NN in a toy dataset with two predictive features and two classes."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_JuEazbKJGl1",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 502
        },
        "outputId": "9ace34b0-79ab-48b8-9108-91ee80447d37"
      },
      "source": [
        "from IPython.display import HTML\n",
        "\n",
        "HTML(\"\"\"\n",
        "<video width=\"640\" height=\"480\" controls>\n",
        "  <source src=\"https://assets.yihui.name/figures/animation/example/knn-ani/demo-a.mp4?dl=1\" type=\"video/mp4\">\n",
        "</video>\n",
        "\"\"\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "\n",
              "<video width=\"640\" height=\"480\" controls>\n",
              "  <source src=\"https://assets.yihui.name/figures/animation/example/knn-ani/demo-a.mp4?dl=1\" type=\"video/mp4\">\n",
              "</video>\n"
            ],
            "text/plain": [
              "<IPython.core.display.HTML object>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h4XIbL5FIClk",
        "colab_type": "text"
      },
      "source": [
        "## Steps of the Algorithm\n",
        "\n",
        "* Compute the $k$ neighborhood for an example $\\mathbf{x}$. i.e., determine the $k$ “nearest” neighboring examples of $\\mathbf{x}$.\n",
        "\n",
        "* Count the amount $q(c_i)$ of examples in the $k$-neighborhood that belong to the class $c_i$.\n",
        "\n",
        "* Produce an estimate of $\\Pr(c_i \\mid \\mathbf{x})$:\n",
        "\n",
        "* Classify $\\mathbf{x}$ as belonging to the most likely class (called the *majority class*)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o892vfTYL2gg",
        "colab_type": "text"
      },
      "source": [
        "## $k$-NN in Scikit-Learn\n",
        "\n",
        "Scikit-Learn's [KNeighborsClassifier](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html) class implements the $k$-NN algorithm. In its simplest form of instantiation, it is only necessary to configure the hyperparameter $k$, which corresponds to the number of neighbors."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gKZpaBFwMFPy",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 69
        },
        "outputId": "76b91973-a6c5-430c-a7cb-d9bdc28917b1"
      },
      "source": [
        "from sklearn.neighbors import KNeighborsClassifier\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "from sklearn import datasets\n",
        "iris = datasets.load_iris()\n",
        "\n",
        "X = iris.data    # data matrix\n",
        "y = iris.target  # response vector\n",
        "\n",
        "train_X, test_X, train_y, test_y = train_test_split(\n",
        "    X, y, test_size=0.2, random_state=1, stratify=y)\n",
        "\n",
        "modelKNN = KNeighborsClassifier(n_neighbors=3) # k = 3\n",
        "\n",
        "modelKNN.fit(train_X, train_y)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
              "                     metric_params=None, n_jobs=None, n_neighbors=3, p=2,\n",
              "                     weights='uniform')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DGGbhbSLAi3B",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "5051e99c-5ace-4825-a770-feeba5358ad1"
      },
      "source": [
        "# predict the class for example x = [1.1, 1.2, 3, 2] \n",
        "x = [1.1, 1.2, 3, 2]\n",
        "print(modelKNN.predict([x]))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eGpxNUQ8Cg91",
        "colab_type": "text"
      },
      "source": [
        "Notice that we can predict the classes for a bunch of examples."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3MWWCd_BBanl",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "e3f08441-a982-41c3-c848-20a407a1cb54"
      },
      "source": [
        "y_pred_prob_KNN = modelKNN.predict(test_X)\n",
        "\n",
        "# Imprime as estimativas de probabilidades para cada classe\n",
        "print(y_pred_prob_KNN)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2 0 1 0 0 0 2 2 2 1 0 1 2 1 2 0 2 1 1 2 1 1 0 0 2 1 0 0 1 1]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mJP3S__gWPzj",
        "colab_type": "text"
      },
      "source": [
        "# $k$-NN for regression"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "738WUxu8S3CN",
        "colab_type": "text"
      },
      "source": [
        "When $k$-NN is used for regression, the target values of the neighbors are averaged to computed the predicted value for the query point. The image below ([source](https://www.jeremyjordan.me/k-nearest-neighbors/)) illustrates this. On the right, we have $k$-NN in a classification context. In this case, the majority rule is applied. On the left, we have $k$-NN for regression. Is this case, the simple average of the three neighbors is used as the predicted value.\n",
        "\n",
        "![alt text](https://www.jeremyjordan.me/content/images/2017/06/Screen-Shot-2017-06-17-at-9.30.39-AM-1.png)\n",
        "\n",
        "A more general version of $k$-NN algorithm, called *distance weighted k-NN* can be used for producing a regression model. This algorithm computes weights $w_i$ ($1 \\leq i \\leq k$) associated with neighbors of a query example $x_q$ using the equation below, in which $d(x_q, x_i)$ is the distance between the query point $x_q$ and other point $x_i$ in the training set.\n",
        "\n",
        "$$\n",
        "w_i = \\frac{1}{d(x_q, x_i)^2}\n",
        "$$\n",
        "\n",
        "After the weights are computed, the predicted value $\\hat{y}_q$ for the query point $x_q$ is computed as follows:\n",
        "\n",
        "$$\n",
        "\\hat{y}_q \\leftarrow \\frac{\\sum_{i=1}^{k} w_i \\times y_i}{\\sum_{i=1}^{k} w_i}\n",
        "$$\n",
        "\n",
        "In the above expression, $y_i$ is the target value for the $i$-th neighbor. This way, the predicted value $\\hat{y}_q$ is a weighted sum of the target values for the neighbors. Notice that this gives the most weight to the data points nearest to $x_q$, and the least weight to the data points that are furthest away. \n",
        "\n",
        "In this variant of $k$-NN for regression, it makes sense to use all training examples as neighbors (that is $k$ equals the size of the training set)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lETcJRdg6Cl0",
        "colab_type": "text"
      },
      "source": [
        "In Scikit-Learn, the class [KNeighborsRegressor](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html) implements the version of $k$-NN for regression. See the example below, which shows how to apply this class to the [Boston house price](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_boston.html) dataset."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EFNOYXNe9Lak",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 259
        },
        "outputId": "6e5388a8-64d6-432b-dd0f-b7c75230584b"
      },
      "source": [
        "from sklearn.neighbors import KNeighborsRegressor\n",
        "from sklearn.metrics import mean_squared_error \n",
        "from sklearn.datasets import load_boston\n",
        "from sklearn.model_selection import train_test_split\n",
        "from math import sqrt\n",
        "from sklearn.preprocessing import StandardScaler\n",
        "import matplotlib.pyplot as plt\n",
        "import pandas as pd\n",
        "\n",
        "dataset = load_boston()\n",
        "print(dataset.keys())\n",
        "\n",
        "boston_df = pd.DataFrame(dataset.data, columns = dataset.feature_names)\n",
        "print(boston_df.head(3))\n",
        "\n",
        "X = dataset.data\n",
        "y = dataset.target\n",
        "\n",
        "X_train, X_test, y_train, y_test = train_test_split(X, y, \n",
        "                                                    test_size=0.3, \n",
        "                                                    random_state=31)\n",
        "\n",
        "scaler = StandardScaler()\n",
        "scaler.fit(X_train)\n",
        "\n",
        "X_train_scaled = scaler.transform(X_train)\n",
        "X_test_scaled = scaler.transform(X_test)\n",
        "\n",
        "\n",
        "boston_df = pd.DataFrame(X_train_scaled, columns = dataset.feature_names)\n",
        "print(boston_df.head(3))\n",
        "\n",
        "# In a practical setting, n_neighbors has to be defined using model selection.\n",
        "model = KNeighborsRegressor(n_neighbors = 15, weights = 'distance')\n",
        "\n",
        "model.fit(X_train_scaled, y_train)  #fit the model\n",
        "y_pred = model.predict(X_test_scaled) #make prediction on test set\n",
        "    \n",
        "error = sqrt(mean_squared_error(y_test, y_pred)) #calculate rmse\n",
        "rmse_val.append(error) #store rmse values\n",
        "print('RMSE value for k=%d is %.2f' % (K, error))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "dict_keys(['data', 'target', 'feature_names', 'DESCR', 'filename'])\n",
            "      CRIM    ZN  INDUS  CHAS    NOX  ...  RAD    TAX  PTRATIO       B  LSTAT\n",
            "0  0.00632  18.0   2.31   0.0  0.538  ...  1.0  296.0     15.3  396.90   4.98\n",
            "1  0.02731   0.0   7.07   0.0  0.469  ...  2.0  242.0     17.8  396.90   9.14\n",
            "2  0.02729   0.0   7.07   0.0  0.469  ...  2.0  242.0     17.8  392.83   4.03\n",
            "\n",
            "[3 rows x 13 columns]\n",
            "       CRIM        ZN     INDUS  ...   PTRATIO         B     LSTAT\n",
            "0 -0.389279  3.411723 -1.329831  ... -0.561453  0.294711 -1.125821\n",
            "1 -0.386258  0.716968  0.573843  ... -0.028004  0.436368 -0.262037\n",
            "2 -0.380684  0.369258 -0.607546  ...  0.149813  0.373055  0.171983\n",
            "\n",
            "[3 rows x 13 columns]\n",
            "RMSE value for k=50 is 4.37\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zrlxr2EF95LV",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 466
        },
        "outputId": "6182cdac-c9da-4c3c-c4cb-3ddd98be94dc"
      },
      "source": [
        "#predicting on the test set\n",
        "predict = model.predict(X_test_scaled)\n",
        "print(predict)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[28.26747942 14.71900206 22.22464171 20.25913378 22.55997755 23.76476085\n",
            " 13.9564192  25.13218819 23.91897183 22.26196039 15.23535039 18.17024123\n",
            " 18.23860928 18.57418054 14.90285359 22.62031379 22.22298975 24.28472557\n",
            " 23.38714521 27.68573961 19.34440264 16.57569257 26.36501906 29.39533489\n",
            " 19.99769016 20.48449326 19.97995391 22.01996112 18.98628072 24.35633002\n",
            " 27.9751017  16.70884491 16.59987662 18.64992673 23.45839919 20.85547024\n",
            " 27.96744737 15.80057434 15.66912717 33.35098665 12.91528709 14.40524538\n",
            " 17.15206845 28.77957093 18.93500128 21.10546579 27.13052839 19.59420048\n",
            " 23.29496988 25.89620951 20.07652377 18.66381045 14.15834116 28.78633783\n",
            " 19.04068122 19.72884966 14.56846461 17.68683052 15.6610228  26.3116879\n",
            " 17.88044938 15.57814121 22.0406903  26.082238   14.16450925 13.20187139\n",
            " 23.44336993 17.73956265 26.55035112 22.81010453 19.61153444 17.04552692\n",
            " 30.00557596 21.44512993 17.65988084 29.84009712 22.35672644 21.72681936\n",
            " 18.15555704 21.66996167 31.63046401 24.83412266 26.25814663 13.17899985\n",
            " 22.53179711 22.06306895 19.65125939 37.76869519 21.6612686  18.52083588\n",
            " 15.57636034 21.23103801 21.80428996 29.0961994  14.46620206 14.60813198\n",
            " 21.96359173 26.10219341 15.54636632 28.65093035 22.31749286 16.14161299\n",
            " 29.81487249 32.58991665 12.5055791  25.85242634 20.52668065 18.69655992\n",
            " 17.22194226 34.41195196 26.24618228 22.37478992 19.26100075 19.37549995\n",
            " 14.60766797 17.46004506 26.05718674 17.15361581 24.55739178 13.78162712\n",
            " 16.96284386 23.84593445 27.46843918 24.5355564  18.8539324  19.83962517\n",
            " 17.6838209  25.06907881 14.58361295 13.60541422 27.29069758 18.64355943\n",
            " 23.71962294 23.81071961 23.49083157 28.64514715 31.03180459 13.6639332\n",
            " 19.78076659 21.62142912 31.34067653 21.80421783 21.09238797 24.10087515\n",
            " 17.91947519 29.6833078  21.58895456 18.89449648 18.33732716 14.18745326\n",
            " 16.50484777 24.31786376]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Bk_XcZ3CtOIh",
        "colab_type": "text"
      },
      "source": [
        "# Final Remarks\n",
        "\n",
        "No optimal number of neighbors suits all kind of datasets. The value of $k$ for a particular dataset can be determined using *model selection*, which is a concept we will cover later on in this course.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_sThq1NvNDE9",
        "colab_type": "text"
      },
      "source": [
        "Contrary to what one might think, \n",
        "$k$-NN can produce very complex decision boundaries. The following image ([source](https://pt.wikipedia.org/wiki/Diagrama_de_Voronoy)) is a Voronoi diagrama that illustrate this behavior of the algorithm. A Voronoi diagram is a partition of a plane in several non-overlaping regions by a set of points. Each region is called a Voronoi cell and contains just one point. The Voronoi cell for a point $p$ contains all the points closer to $p$ than to any other point in the plane.\n",
        "\n",
        "![alt text](https://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Coloured_Voronoi_2D.svg/220px-Coloured_Voronoi_2D.svg.png)\n",
        "\n",
        "The following animation ([source](https://en.wikipedia.org/wiki/Voronoi_diagram)) shows the formation of a Voronoi diagram for a set of nine points.\n",
        "\n",
        "![alt text](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Voronoi_growth_euclidean.gif/220px-Voronoi_growth_euclidean.gif)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_N7VpZr3xlXo",
        "colab_type": "text"
      },
      "source": [
        "Alternatives do avoid overfitting:\n",
        "\n",
        "* Model selection (measure performance on validation data for increasing values of k);\n",
        "* Replace a bunch of points by their prototypes; \n",
        "* Remove outliers, i.e., remove data points for which all (or at least the majority) of the neighbor voronoi cells are from a different class."
      ]
    }
  ]
}