K_NN.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "K-NN.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOs/bskHRB9LYfc/zHFpIzQ",
      "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/wingated/cs180_labs/blob/main/K_NN.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xf2ALkYYXymA"
      },
      "source": [
        "import numpy as np\n",
        "import spacy"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qn3rWE4yYCCZ"
      },
      "source": [
        "# this will take a moment, run as soon as you can\n",
        "!python -m spacy download en_core_web_lg"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8EM9P_VYgVw4"
      },
      "source": [
        "# RESTART YOUR RUNTIME. COLAB BUG. WON'T LOAD SPACY PACKAGE OTHERWISE"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8lgtH0ChYP04"
      },
      "source": [
        "When trying to find the k-nearest neighbors you have to have a few foundational pieces first. \n",
        "\n",
        "Primary among this is a measure of \"nearest\". The purpose of the KNN algorithm is to classify a new, previously unseen, point given a set of training data. That classification process is a search for the point in the training data that is closest to the query (test) point. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kSS9Zzh0ZCtY"
      },
      "source": [
        "## Distances"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z2aEGdn7ZElw"
      },
      "source": [
        "There are a number of ways to define distance between vectors\n",
        "\n",
        "L1: |v1 - v2|\n",
        "\n",
        "L2: sqrt(sum((v1 - v2)**2)) often called euclidean norm\n",
        "\n",
        "L$\\infty$: max(|v1 - v2|)\n",
        "\n",
        "cosine: \n",
        "\n",
        "![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAaIAAABzCAYAAADaHgZRAAAcmElEQVR4Ae2dPa41zVWFGwsEQkL8TQBbIgcmwI+ERGawSJwg8AQ+8AQMTMAgkQMRoSEjAxOSGENAgmQ8ApgB6Ln3rPdb33ZVd/XfuX3OWSX1W93VVbt2rT7vXrV3VfedpqQgEASCQBAIAkEgCASBIBAEgkAQCAJBIAgEgSAQBIJAEAgCQSAIBIEgEASCQBAIAq+BwB9P0/Qb0zT93DRNnH92O3+N0WeUQSAIBIEg8KEIQDy/Mk3T/03T9KfTNP3SNE1/cSOkD1UsnQeBIBAEgsBrIPCHNyL6b/OCICJIKSkIBIEgEASCwF0Q+JNpmv7WeoKUftWucxoEgkAQCAJB4FQE/n6apj+69UCYDiIi4S0lBYEgEASCQBA4HYH/va0N0RFrRhATOetFSUEgCASBIBAETkfgd0sPeEIhoQJKLoNAEAgCQSAIBIEgEASCQBAIAkEgCASBIBAEgsA+BH5smqatx76e0zoIBIEgEAReHoF/vr24yq44zr9bDsp0UIeXXP34zZ0Isu6UtaedIKZ5EAgCQeCREeDdIIjlf6Zp+vLgQNjIIALzd40Gm3+qxueD6PfPPpWMn7Cl/J9uepDX4zvTNP3euLjUDAJBIAgEgY9EACKAjDDma9I3pmlimzeEsiWp3y1ERH8QJx4cumuX38/fvpHHVyAo/+stiqVNEAgCQSAI3B8BeThrSYH6W15yhUQgMciCvrcmwoU/vK1xVRnI5mD9KykIBIEgEAQujgCehIhhzboP3tCWNR7I59d2EhFkBtH8TQNbyId7jClE1AAoRUEgCASBKyLAmgrGm3UbiOmsRD+sLYks/m0jWfAJIvTVp4hcX4X9Wve8Xs6DQBAIAkHgYgj85c2480mfsxLEI6KDSDi2eC2QGW2/clMUGXhJ3759Gy+bFc56gpEbBIJAEDgZAYgCA88XuI9OeCouV2tTW4iI9SFCb8jQtnPOKQ8JHf3kIi8IBIEgcEcE2NKt9aIj//QD3gpE4aQjIpKH5MPkHh9abSWtD7W2j7PGBZHi3XniL87+wAtyHgSCQBAIAtdFQOsvR/4xPEgDIoBg9N4P61GQRmuDBFuye1vDpV9vDQiZHE56yNI27+siH82CQBAIAkHgDQGIAcI4KiHvH27EADno0KaCFhHN9a31ITyjmpANCWXHXEUm10EgCASBB0GAcBwk1PNGtgyDdacWaYiI3LPBa+FPk89tmGAdiKOVJNNDc8hjTITnkoJAEAgCQeDCCLBWg8He8m5Qa1jI4+sGPVIRaZArEQ6EjHpE4+tDHnqjL31RwdeO9LeU0GHLy7fSK3kQCAJBIAjcAQE8F77jtib1NjSIFLRe4y+eQnQq91wESN26UQG9vG49JxRH+K+1Yw653D/Sy1uDUeoGgSAQBILAAAIYfw+RDTR58zB8O/ZIG9XROpGulUMWbGKAPERMukfu7fzc69RzdGR8yAsZVXRyHQSCQBC4AALf3PAVbDwhCKO19rNnSKzjKDx4VCgNeYT7jtwFuGeMaRsEgsAOBJhR/vqO9nNNMWjsntKBQfJzrn1NYE5W7o0jgBfkaypzLcEfjwKDDgkRyjs68RtjPaeG5vb0g754RGvDjnv6TNsgEAROQoCZJbH5M3YfaeG6xv7rNQbwSCN1ElQPIVZeDbvKMNY6eBacf+uWc593f/TVBT2TrWG5hwAnSgaBIHA9BDBaMkCjM+i1o2DG7YT0W2VNgFCNdPDtuWv7Sf13BPCGwHvr0VrDCbZBIAgEgdMQILQhEiBvfZbliM6diFovOvqsPKG6IxCPjCAQBILAAyAA6RAS490OkREL3GekOSKCeFyHs8jwjHFFZhAIAkEgCOxAQH8WWn/MDDKCEM7wSOaIiFCdiBAPLWk/AnvCa3va7tc8EoJAEHgpBAiHaU1GGxYghNbLg3uBcSKCbLSAzhv6IkDKkvYjwKYTXvRcm8Cf54GXnBQEgkAQOB0BbVLQ+yIscMsr4U320cS235GXCZ2I2BTBtQ6RIDu4zti5NzqWZ6q3xasBew5+B0lBIAgEgdMRgAz8fRHCccyiRUYiqCVFaMMMeomMnIhamxUgP/Xdur+kR+6/I8Bz2PNOWIgov6QgEATugoA2KfT+jgyEAHGMJMhsJAy0RERbPbIRHV+lDiREeI3Qp97JwjOSp9PLfRIRInqVX0vGGQQ+GAGMPuTBJgE/vmZeydGbFpaICC9IHhGhuqT1CEAiEI9/kZprsJ07QkTrsU6LIBAEdiKAF9N7eVXrNZDCkSGyJSLCeIqIztgssROyh2kO8TDJcHJZo3w8ojVopW4QOAAB/rOu3S5M/a3/yQ9QeZcIyIDPumDwGQeekSfus2FAhMA5ZXsIibaEi1wufVOm43vWJ/0lbUeAkBz48v01heXAdO6gnlKISEhcIOchHmlskOULiDx4vvfEf04Mw5Gp9nWk7GeThWfA7rFWopxZOnX8GRHKovzREpsRqjFqEVGtwzXGaWuCiFoyaxm65EXWrSh/3g6PVn8N9fPS8TPaMhFxchpvnZqHIaAHcaSxUdhBC4iQBf/xeOBHx8PVV/3UOn2O7oQ6DMwLC8IQOsG4qkxEWCPRV30JdbhXQDvaJwWBqyHApAE7o9/uGv2wGfyu8VTJqw1ZIyt1dyLATADD0zNSW8Tzw0AmJOfpDCLiR0RfdRarman3/6rnkDJbjlszcMrYTeZfIGayoBc/wQxCB+NW+1fFNOMOAkHgQRE4g4h6UGBIM4t/Rwcceh4vExBIxhNEVD1X2jtZef2cB4EgEASGEZDXwAyZ44i05jtdPSJCBq71iKyROszg8QAwwNQfaXMEFltloB86z+mJNzJ330ORNd79/Q6JIJNnwmKvEn1ATJWIwLKWqU3yIBAEgsAiAsx6mdFqZkwoRmsAGJ1KECqjHPKiLUaIcuKokIbKKOdjkkqE5WjHQX+eaj8YTzYwYAjxYFinqCFC14V1JhbTIRmMbasv6nCfvhgn8jkwsOita3L1RRuVq8z1PvMcL4NxgwGYorMTCc9JGwioA96+4YC6tENvkYUTBuMGCz1vHwt9c8+3D0OIlHlojjb6UOccGbrsnAeBIBAEPiHAl4YxdJ4wVG6YMHRuvKiLccMguWHmnDLuyaOCmOr6AwafektExPoO9chJWouo7TDA1ONdEPrjXAuLEGXt60tWhuGsxpOxorOXgwH9alw3lb6Q0SdtR486ji8Iu3kp6C5iER5qxzOCiMFTifFSBlYknoXqcw0x+bNEBn2o/nur93+pxz1ImHNybS2uYTh9sdp/Ny5L57QbxYd6rrtkJD8OAdZp8zyOwzOSNiIgQ/SZtafMZ936oVqVN3KoBkyG0o2RiMDLMPC0rUYGA0pfShh9ZLrxn9NFfbjurb5aZeqTXDv4JI/63/UKM+fUHT1mxLzdAg//4GbFgwmE4yV5lENAJO5DHk5WjE+JMfIs0LkmyiFg6uhAXn3utKM95cKsyvLrFj6SUe95u975T03T9NM5mhj0MPPyivnctbfrnf9knkXzWbzyb/Qnej8WlWPcMDYYEQ5CP3U325zx50erBLFUYyRD5waKNtSrRERZNazoh6eh0BRGtpKCCNB1kU5zfdX+vQ0koLftCU3VUJTqnpULt56OrfUb6QKG8ui0/R5sOb5TSEn9qK1yyXePFyzBpXrQaoN8f84qPzv/j9vYNMbk788aHH78bPAb8v8xz+Pt/1p+h5//Dv+q8Tv5kSKMPbNkZtEYGgB0MlpLRHhBSvKIvKxHDnWGzyweg4pemtGP6qL+W33VMjwoMPCkMCMGGUJqha68vs6RPXqoTSsXQfSICH14TpWUkQVG3EMPEnWRowkHkw0l9aO6Ktdza3lPXqb6tKfPESIaxafqpL5q/rPTNP1ijiYGFavW9dHP42fyLJrP4pV/o3iDswnCcdLBIGPI8ECURo0/xg5j5KQjQ+cGSkarGlna0pcSxFRn39IF8pBMeURq5/lcX7QjoYfrTJkMPfdaxv695Rf/xXOj7uhRx+/S1L8/B92HlBkXkwbHi/u13D0a7rPe5ISh5+PhTOrJIxLGlKELZNZKa9aIRvGh3hxGLT1Stg6Btb/Z+nta11tqB4EOAvxHZxHaEwbHDYCMv9dpGX/ajBARcqjnfagM40OSQWV9QwmSxEOiDAOp9i1dvE2vL/2nIneDq7byIFoegOqcmRMORHdtVqAv9BSBalebe3Pcp43Gw7Nj96CSCAaiI4moVf9W/JYxCdCmBHSA+FwXr6tdc8hPCgJBIAjMIYDNxU592pGLMcfgEP5idkQFrjFuzLwhKYw/B+cYLowb1wiiTO0I+VAGUbTKkI1R5z71qE+Z+qHM+6EuZfy5XuTRrwZAv3gxVRfuK9Gm9qV71KMvvnHnGwJ0n5z+Mb6M+SMSz4CwIHpCPhyM14lHz0/3eXZOnNSnjPGCB2tEInCNiToiHJWRIwcyZiMLMnokRF3p4e1zHgSCQBBoIYCzg23/ZHu1PqJQl8+MRUYIwhhrnUahIcohA9oyw5bBVpnX45xD/blM74f7HiZDLjpRJgMsOchQH/TN4cay1RdtlGiLbMlVufKP2KSgvj0XBv5s/D5eCPda98GApPuOz+3WGwlpl53KlAsjXfdy2t97Q0dLF/8tcd9/S636W8s8nN3rB+z8t3WGLq4Hz1rPe+u40i4I3AsB7FrP7txLh0v2g9HAQ8KAkGBtwHr2BJHh+W0Nq4ERs5srGEGMvXt8nGuCtPQc8Sr17Jfq4kUqQfLep8qR5+RT6xDO1ASBnLq65pwv1C/p43rQxr1h6fHIOf8n/2Capt9/wOO3DwT+dx5w/Hpmv9zBgYl+KxLTqf46xRgBDKoMkof5nh0FjGQ1lKNjBqetbUf7GK3HM3RdOB8hIgw4z350hgYBSG7tU7rSN/dI1HVduKa/kYMQtuTcxH2S6UTU08PbPNo5mP3nNE3/+oDH3x0ENr+V/3rA8euZfb2DA//XrjB57aj3scUY1auEme6NBONemoFXnZjVs47kIaha557X1RgTgxZhzOmhjSkQw4gX7ESEJ4LBrKkSERMc14VzfeWDfl2m6vFMRFaVjKjz7ETE+Ld66vV5POp17/f1qONBb8bEmnVSEPgRBCATwpFrEvWvQkLoXYmIXZgy6r1x0UbGnnxkrctJo2coWkRUdUA39e2konqum16w1r1KREwKWoSo+o+WM75/GXh+jzautfrirX/aXba2ceoHgSBwfwQqETlh9LTBwLtHxC7FJfJyuSNERN+QRJXL9RwRYYB0H+/AE22dvOrYve4jntfxPeIYjtCZiVFrk9ERsiMjCASBExCoxtgJo9UdYR8MPbNOD4MtLfq73BEiwqiuJSJ0Y7s9+rGZhH48VUNdx+51H/H82caz9Rn4b22rjLQLAkHgjghU47X0n5hdO3pXzL0P3lObSy73KCJiUwLrSBy8O6f38iDI1qLusxMRz+bVQ1L1Gc/9JnMvCASBiyCwloh4UVdrQvyn51qhsLlNC1uIqLVeRZ/qj/CgtnSTY4SlD55RJaNqpOrYL/JINquRkNT7xpm6NrgZ0DQMAkHgPghU78QJo2qA4YYEvnJbu8GwEz4TMYigajuunVRqn6qPLA+noUtNTkSt+79g+uAheaKtPolF+bMR0dyzEw5slOF9K3Kdr935KVlXzJmMjLxrw+9M42Y96asX20R0RWyjUxA4DYFqjOeMGTNNkU4rZ9NCL7ncOSJCH5JIg9zTEhFRl76kn+RRTlvuKdWxq/wR8zq23hgIY+pTXrx6gTHGs5RR7rV7lHImM/7MW3ozVr4niffMLlbIi+u6uaXVNmVBIAicgEA1xk4Y3p02Kfz5LRxGKEwHXoYMf2/Tgsu9JxG5h1WNdR27j/fRzpnVz3mkGg8GtxpdiGjJeKv91XP/nfV0hYjxBvnNioAp80lKr23Kg0AQOAGBaox7/5G/cduk0FKBGaWIqDerdLlnEhEGWbpgYDE4Ss9MREwARkJSYMEz0oSBdTTweobE8/1+Y8t/a2z87vGIlPCMRvFTm+RBIAgchMASERG+gUQIu3GwO06zSFTgPmUy/uTU5/A0SkTuwfi6ErK4Ro76Qh+u6V+H7mFk6uYJDNWzrhGNhKT0PNj1qI0cGF/tMlSZ6j1ajtf+6evUC8qDl7+MDib8Xvz3tyAit4NAEDgKgUpE1fgzc+Y/rR9usAhp+D0/dx1HiQh9SCINciVkExrU4X3pHMNaCUjtkYUeSoQWafcMyfGdGw+TiOoJ8Ayv9sWPuTH07tXfcq8e5eDFuEmQj9bJVHa7lSwIBIF7IFDDZKwzuPE/Sgc3lLVP9QEpOBE5aajOnvxZiYhxjX7ah0mE/ykMiIkNDD652IPxR7b138+SHhCOh21ZNwsJLaGW+0HgJATqLJL/zGcRkYYwQkTUrd6Z2m/NKxHVsW+V+9Ht8ABHQ1IfreuZ/RNi7HnDZ/Yb2UEgCOxEoJLCWUTkpNIjAJ/RQhq+nrNzmG/Nn5WIengegdmjyDjj9/IoY4+eQeDhEahG7Cwi8jAb4SD6qcmJiHuEjI5Orgdj1+6xo/u5p7yKm/eNgdZBuc6Xcpdx5DnPnvUoDtZlPEy4px/G48/WZXGP5LnGr3Jd1/y95fH/EgrURiA22niY8PjeIjEIPAAC9/hPMNLHSJ29cNY+6vVe+R/RnrAcO8ZqwjBj5Mh1rt2FrTLdUy7DXeWOXkM6FV/6pZzEmgw7H2ud2+1VWZ1QqTGTGY2nNeaKi+oq59WEoxPj/56NGx18B9/R/UVeEAgCQeBUBCCL3rszbDxhOztrJyKV1oxfZbyDhXfFVmba7THCrNUgA4LwxI49vAESBpk6hIf3JnZLtrxbxsR4IDzOHQf6rNfojRzCwugGYYwkxgDpzR1av9K4Rci0wTtMCgJBIAg8JAIYUmbUrcQ9DBwGdc3LmngoyITAtibat4jI5RGWo84RO/YgXYimlSAW+gGLlufYakOZ2o3oRx1IV3hDTByUkQuPFrnjDe3Buqd/yoNAEAgCd0GgF5JS5/IIMMQ9Q626nkNGeC9bwmb+pY05AsRoH7VlGkMv78bHoXPCl2Aw8hkktSFHfzyWkUT/9IEuNUFUIkO/h1fkLxj7vZwHgSAQBB4CgV5IypXXzH6tR8BMfg15qU/6UZ+tTSnUwws4ioTmvELphCcEsUIGLa9E9Vo5YxlJTAqQ3xozOFYiguTxhEY8rpH+UycIBIEg8CEI8EX0EbLA4GEIz14UxwhDjnNGGQISCUF2WivZCiDjH/kbRFqbYb1I6zVb+2y1Y+xgzNhr0nqdSA0S4lnI49S6WW2X6yAQBILA5RFYCklpAHs8AslYypnZKywlItK12kJA/NHCb91CXuxOkzFWnbU5Hs5cCNDliSzw2o5OjBUi+pIJBne2aRN+c0+MupQT9gOLrBEZaDkNAkHgcRAYCUn5aBQeOssjwCuRN4ABxihXIuK6Hq7jlnPIRf2OtKd/dKPdUUnrQ4T/kMuBx8M1O+/ca8UzqxjEIzrqSUROEAgCd0VgNCTlSmEgMcKj25K97dw5RFDDYyIijPSZCaO+pg9IUlvU1xDY3BiQ0yM3PB/I3z2iOVm5FwSCQBB4GARYbxgNSfmg5BGwPnNU4l0myI1QG/LJMcwca0hirT7I7r1HNScLUkC3o0JiIvgWsck7PCMcODfG3AsCQSAInI4Axq9l+JY6hryq97LUZu4+8liMRxc/MLxnExFGfssHX1mXQr+jdqyJ3Fs4KSQaImqhk7IgEAQuiwC7uiCaubQ2JIUsiIJ2RyWIoGdgZZzrZgSMP6Gqkd1ySx4L41nCqTVWdPN1m1adNWUQbu8jvdoxV/Vk48bS+NbokLpBIAgEgUMRwGOZ81oISfkXzUc6x/BigCsxjLRt1UEOIbjeQruICLLwRLuRj53SDgMP2fXSFq8QXLWNuid3Tbn0rETDM6KMMbS2zUPEI2S8RpfUDQJBIAgcggDeEMYLQ95L1FkTksKYI++oUBSGFR058G70XhD6QjK+RvSDjTN/yahE5piAwZp3giCGShgur3XeW+PSOBkfONQ1MnAB82xSaKGasiAQBC6NADN2fQWgZwQxzmsMKuGztaEodnv12qCXjhaYulf1RyYktvTZHMYnDHobMpC9xivEC5rzMlvjgLiXCN/HWs9bMvEI9aHToyYGrX5SFgSCQBDYhACze4wlxo9Zdo8IIKE5T8E73xKKwmhDBJVIXO7ac8JQeE6QEcdcYvxfu2HQ+z4cus15jS5/S1hS619HhvHQCRKCjMA3oTl/SjkPAkHgEggQ7oGMIBqIqBfWwVDPrZ1oMN9c6TkhE0NJ3z0CkOyt+YgBxvhDNOjRI5tRr1CEMoKXxoRsQm30v6ad2i/l8viW6uV+EAgCQeDDENB7Lq3wGwZ65N0ZZLBOgQzIhcPPVUaOh8KaDPUxvhw9b2wPKDLAeAQcc4lxKjzHeU2E7Ja8FfqAUNid5uMFhxYW1BMBgcFSWK7qNHpNeBL9E5obRSz1gkAQuDsCkEDPEGKUe16CK4pRZQ2Fujq41qGyVn6WAYbw2GXHMWKE0Q0cWhsS8NiWyJJ+tmJA3z2P1HHecq4//bAUotwiO22CQBAIAocgANlggNlkUL2B0ZDUIYocLITQI54J+UjCawEHxlwTRFGxqXWueo1HBAlljeiqTyh6BYEg8IYAJIQRrsaWkM5ZM/WrQU/oDQwgJE9gAhElBYEgEASCwIkIEB5reQPsglsKSZ2o1l1F4wmBAR6EJ8a/diu2t895EAgCQSAIDCCgsFRdkB8NSbE+stZrYHH/q9M0fXtD24Ehra6C5wMR1XGASe/9otqJ1mNq+dw1IbPPpmniZdUjPw4712fuBYEgEAQuh4C8AQ9LrQlJsRlgZEOADxwiwvCyflGNv9e71znj/eGNjDhXApPWupHue76FSCAiDkhwS3vvP+dBIAgEgYdFgJ1i1RsgJDXyfg+EwrE1saHgCkSE/gpRejgS3ZyYeuNcS8QuB/khIkck50EgCLwcAjKE/oWDkZAUxhePhs0OMsTM7pnZzx0O8JWISCFKbdAAl5H3qMBAB2OTtzeHgZO38I9H5L+MnAeBIPByCDDzZ1aOUSThDS2FpCARkq+NQES0mztuzd6yKxERBAQGClHiKS6958R4+ZwQ49BGB0hmbvzcE3EDgoiI8qQgEASCwMsiwM4wjLCM4WhIivd08Ii2pisRESE5MBD5gIVIaWl8I58T6skIEfWQSXkQCAIvhYDCUoTkMIyjRMRXFWijGT476PiET++Q1yBwr0REIgQ+vUMCExHzraiZEVKDiPCEwIEc/HoYUO5hOPU70ldTgRQGgSAQBJ4BAYygwlIjISmNmTYYXtZItqQrERH6+8u9eEYjHyJlDByjnxNq4QSOTk6tOikLAkEgCDw1AhhcjCEzedZKRkNSEBBGGDJam/CO6IcDGf5H79bKOqq+75z7d1szm5PPOhFj2aK/SIxcOMz1lXtBIAgEgadFgPAQmw54sRKD+KphIsYOIfM3iiDlpCAQBIJAELgjAhheeUUjIak7qna3rhSi5EvakFJSEAgCQSAI3BEBtmxDRP4+0R27v0RXerkXHPQ+0SUUixJBIAgEgVdAgG+qYYC1ffkVxlzHqB1s4AApJQWBIBAEgsAdEVBY6tVDUgpRQkpJQSAIBIEgcEcE5A28ekiKl3uzUeGOP7x0FQSCQBAQAhAR60OvHpIiRDnywVfhljwIBIEgEAQORGDLuzAHdn8JUXwdgXeDkoJAEAgCQSAIBIGPROD/AaFKAuUEgtYGAAAAAElFTkSuQmCC)\n",
        "\n",
        "arccos(similarity) gives the angle between two vectors\n",
        "\n",
        "Note: While we are using vector notation here, you actually have an elementwise subtraction and all other operations are also elementwise. Luckily, numpy supports this natively. \n",
        "\n",
        "\n",
        "Feel free to look on wikipedia for a full definition of these distances"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kaK0psnNaOj-"
      },
      "source": [
        "## Question 1\n",
        "\n",
        "Fill in the three remaining distance metrics for 1 dimensional input vectors v1 and v2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8xzop7t-YKyk"
      },
      "source": [
        "def L1_norm(v1, v2):\n",
        "    v1 = np.array(v1)\n",
        "    v2 = np.array(v2)\n",
        "    return np.sum(np.abs(v1 - v2))\n",
        "\n",
        "def L2_norm(v1, v2):\n",
        "    pass\n",
        "\n",
        "def Linfinity_norm(v1, v2):\n",
        "    pass\n",
        "\n",
        "def cosine_similarity(v1, v2):\n",
        "    pass"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UovVmQwLbet0"
      },
      "source": [
        "#sanity check\n",
        "a = np.random.random(10)\n",
        "b = np.ones(10)\n",
        "print(L1_norm(a, b) == np.linalg.norm(a - b, ord=1))\n",
        "print(L2_norm(a, b) == np.linalg.norm(a - b)) # L2 norm is default\n",
        "print(Linfinity_norm(a, b) == np.linalg.norm(a - b, ord=np.inf))\n",
        "print(cosine_similarity(a, b) == np.arccos(np.dot(a, b)/(np.linalg.norm(a)*np.linalg.norm(b)))) # you're welcome"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B41H4AEKbMR4"
      },
      "source": [
        "## Question 2\n",
        "\n",
        "Code up a function that takes a query vector, training_data matrix, distance function, and parameter k. \n",
        "\n",
        "This function will compute the k nearest neighbors from the training_data matrix to the test_query vector according to your distance_function. \n",
        "\n",
        "You will want to return the distance values and the vectors (or a descriptive label) for each neighbor found.\n",
        "\n",
        "You can use a heap to efficiently keep track of minimum distances if you'd like. But it's up to you. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Jy0Fdi0zbL_8"
      },
      "source": [
        "import heapq # you can use this to keep track of distances if you want. It's good data structure practice\n",
        "def knn(test_query, training_data, distance_function, k=3):\n",
        "    pass"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "u4kexrsCdwm2"
      },
      "source": [
        "knn(np.array([1,0,0]), np.eye(3), L1_norm, k = 1) # should return an identical element with a distance 0"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "380yHEULfuIc"
      },
      "source": [
        "## Question 3"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "N3aPEnK8hnjt"
      },
      "source": [
        "!wget https://dasl.datadescription.com/download/data/3043\n",
        "!mv 3043 adoptions.txt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LDKYEO7Jif7T"
      },
      "source": [
        "import pandas as pd\n",
        "df = pd.read_csv('adoptions.txt', sep=\"\\t\") # this is an example of a tab separated dataset\n",
        "df.head()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MwIACUNdjKOS"
      },
      "source": [
        "df.iloc[0].array"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wXebVN8rkjGG"
      },
      "source": [
        "Find the top 4 neighbor states to Utah state using the three numeric columns and your choice of distance function.\n",
        "\n",
        "## Note: You will need to modify your KNN function to handle a data frame\n",
        "\n",
        "you can copy and paste a new definition here"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VF14GgakqAyU"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LV715x0ZqyyZ"
      },
      "source": [
        "# find 4 nearest neighbors to utah"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TpSgpE4Okv28"
      },
      "source": [
        "Explore the differences in results between various distance functions, show us something interesting and write about why you think this is the case. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sqO3BYL1kvLi"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ghkYA8QEk9Y-"
      },
      "source": [
        "your written answer here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "50--LM3ti91w"
      },
      "source": [
        "# Question 4"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wA-TW9eGftae"
      },
      "source": [
        "nlp = spacy.load('en_core_web_lg') # restart your runtime, if you haven't already, this load also takes some time"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DsHUck0few51"
      },
      "source": [
        "v1 = nlp(\"this is a sentence about bananas\").vector\n",
        "v2 = nlp(\"on the other hand, here we talk about oranges\").vector\n",
        "v3 = nlp(\"totally unrelated paris sentence\").vector"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tcgQxsXUhGke"
      },
      "source": [
        "print(v1.shape, v2.shape, v3.shape)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y_tYfp1og9bH"
      },
      "source": [
        "print(L1_norm(v1, v2))\n",
        "print(L1_norm(v2, v3))\n",
        "print(L1_norm(v1, v3))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eEuol2ndhWIq"
      },
      "source": [
        "Spacy is a great package for easy natural language. It allows you to turn arbitrary sentences into vectors of size 300. You can then use \"distance\" operations to measure the similarity of two sentences.\n",
        "\n",
        "Notice that the bananas and oranges sentence are far more similar than the random sentence about paris. Neat!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8Sl-3825nMcO"
      },
      "source": [
        "## We are going to be building a clickbait classification detector. \n",
        "\n",
        "Let's first prepare the dataset by downloading, reading, and formatting. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "37TcmTp-lrwH"
      },
      "source": [
        "!wget https://github.com/bhargaviparanjape/clickbait/raw/master/dataset/clickbait_data.gz\n",
        "!wget https://github.com/bhargaviparanjape/clickbait/raw/master/dataset/non_clickbait_data.gz"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jytwp9vKluHe"
      },
      "source": [
        "!gunzip clickbait_data.gz\n",
        "!gunzip non_clickbait_data.gz"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r3-ZuefJhKaG"
      },
      "source": [
        "with open(\"clickbait_data\", \"r\") as f:\n",
        "    cb = # read in the data and split on double new lines\n",
        "\n",
        "with open(\"non_clickbait_data\", \"r\") as f:\n",
        "    ncb = # read in the data and split on double new lines"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zn2n1ji7mlA0"
      },
      "source": [
        "cb = np.array(cb)\n",
        "ncb = np.array(ncb)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lu_bUhxFno-S"
      },
      "source": [
        "## Add a column of ones to the clickbait and zeros to the non click bait then merge the two lists. You can make a dataframe, iterate, use list comprehensions, or use vstack/hstack (transpose). \n",
        "\n",
        "Your new dataset should be [len(cb)+len(ncb), 2]"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cKTT7gvHnypL"
      },
      "source": [
        "df = pd.DataFrame(np.vstack((np.vstack((cb, np.ones_like(cb))).T,\n",
        "                             np.vstack((ncb, np.zeros_like(ncb))).T)), columns=[\"text\", \"label\"])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rbXDXfDUpRk9"
      },
      "source": [
        "## Question 5"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e7uesz0jpYPP"
      },
      "source": [
        "Test your knn function on this clickbait dataset. Try and write the best clickbait title you can. \n",
        "\n",
        "Demonstrate that your method is working with a few example test_queries. \n",
        "\n",
        "## Note: You will need to use `.vector` on the text columns to get a vector you can pass into your knn function."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yBpevGtupQt8"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "S1_8BW4gpnPj"
      },
      "source": [
        "## EXTRA CREDIT + 10%\n",
        "\n",
        "split the dataset into a train set and a test set. Show the accuracy of the different distance functions. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3H-3VT9Jpwem"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}