17. K-Nearest Neighbors (KNN).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       "\n",
       "div.cell { /* Tunes the space between cells */\n",
       "margin-top:1em;\n",
       "margin-bottom:1em;\n",
       "}\n",
       "\n",
       "div.text_cell_render h1 { /* Main titles bigger, centered */\n",
       "font-size: 2.2em;\n",
       "line-height:1.4em;\n",
       "text-align:center;\n",
       "}\n",
       "\n",
       "div.text_cell_render h2 { /*  Parts names nearer from text */\n",
       "margin-bottom: -0.4em;\n",
       "}\n",
       "\n",
       "\n",
       "div.text_cell_render { /* Customize text cells */\n",
       "font-family: 'Arial';\n",
       "font-size:1.5em;\n",
       "line-height:1.4em;\n",
       "padding-left:3em;\n",
       "padding-right:3em;\n",
       "}\n",
       "\n",
       ".MathJax {\n",
       "    font-size: 70%;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "css_file = './custom.css'\n",
    "HTML(open(css_file, \"r\").read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-Nearest Neighbors (KNN)\n",
    "\n",
    "© 2018 Daniel Voigt Godoy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Definition\n",
    "\n",
    "KNN is a ***non-parametric*** method used for both classification and regression. It uses ***instance based*** learning instead of model based learning, that is, it approximates a function locally and performs computations only at prediction time.\n",
    "\n",
    "### 1.1 Algorithm\n",
    "\n",
    "Given a new instance, KNN uses the ***k closest instances*** to it to make the prediction:\n",
    "- for ***classification*** tasks, it uses a ***voting*** rule to assign the ***most frequent label*** (among the k-nearest neighbors) to the new instance (although it may be a problem for ***imbalanced*** datasets)\n",
    "- for ***regression*** tasks, it computes the ***average*** of the k-nearest neighbor to output the predicted value\n",
    "\n",
    "### 1.2 Finding Neighbors\n",
    "\n",
    "The definition of ***closest instances*** depends on the ***distance*** used. The most common distances used are the ***Euclidean Distance*** (continuous) and the [Hamming Distance](https://en.wikipedia.org/wiki/Hamming_distance) (categorical), although different distances (like correlation metrics) can be used depending on the problem.\n",
    "\n",
    "### 1.3 Defining k\n",
    "\n",
    "The ***hyper-parameter k*** can be fine tuned as any other hyper-parameter. Once again, we face the ***bias-variance tradeoff***:\n",
    "- ***small k*** will ***overfit*** (low bias, high variance) as it is aware of a small local region and more sensitive to noise - making the boundaries more jagged\n",
    "- ***large k*** will ***underfit*** (high bias, low variance) as it is covering a larger region - smoothing the boundaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Experiment\n",
    "\n",
    "Time to try it yourself!\n",
    "\n",
    "There are 35 points in two dimensions belonging to three different classes: red, green and blue.\n",
    "\n",
    "A new data point will have its class assigned to the same class as the majority of its k-neighbors.\n",
    "\n",
    "The ***dotted lines*** show the ***k*** nearest neighbors (using Euclidean distance).\n",
    "\n",
    "The controls below allow you:\n",
    "- define ***coordinates*** x1 and x2 of the new data point\n",
    "- define ***how many (k) neighbors*** to use for classification\n",
    "- show ***boundaries*** corresponding to the chosen k\n",
    "\n",
    "Use the controls to play with different configurations and answer the ***questions*** below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from intuitiveml.supervised.classification.KNN import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, y = data()\n",
    "myk = plotKNN(X, y)\n",
    "vb = VBox(build_figure(myk), layout={'align_items': 'center'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "4f5f56f0a71a4ad4b63afe2d30fdcfc8",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'marker': {'color': [green, green, green, green, green, green,\n",
       "   …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1. Change the ***coordinates*** x1 and x2 and make the new data point change colors. Can you pinpoint the boundaries like this?\n",
    "\n",
    "\n",
    "2. Change the number of neighbors ***k*** and repeat the exercise.\n",
    "\n",
    "\n",
    "3. Set the new data point to the coordinates (3.8, 0.6) and change ***k***\n",
    "    - what do you observe?\n",
    "    - set ***k*** to 3 and zoom into that region - what do you see? Do you agree with the assignment?\n",
    "\n",
    "4. Leave the data point at the same coordinates, set ***k*** to 1 and check ***show boundaries***:\n",
    "    - how many points would be ***misclassified*** using the boundaries?\n",
    "    - increase ***k*** gradually - are there any ***misclassified*** points now? Why? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Scikit-Learn\n",
    "\n",
    "[Nearest Neighbors](https://scikit-learn.org/stable/modules/neighbors.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. More Resources\n",
    "\n",
    "[A Complete Guide to K-Nearest-Neighbors with Applications in Python and R](https://kevinzakka.github.io/2016/07/13/k-nearest-neighbor/)\n",
    "\n",
    "[The use of KNN for missing values](https://towardsdatascience.com/the-use-of-knn-for-missing-values-cf33d935c637)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### This material is copyright Daniel Voigt Godoy and made available under the Creative Commons Attribution (CC-BY) license ([link](https://creativecommons.org/licenses/by/4.0/)). \n",
    "\n",
    "#### Code is also made available under the MIT License ([link](https://opensource.org/licenses/MIT))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "  function code_toggle() {\n",
       "    if (code_shown){\n",
       "      $('div.input').hide('500');\n",
       "      $('#toggleButton').val('Show Code')\n",
       "    } else {\n",
       "      $('div.input').show('500');\n",
       "      $('#toggleButton').val('Hide Code')\n",
       "    }\n",
       "    code_shown = !code_shown\n",
       "  }\n",
       "\n",
       "  $( document ).ready(function(){\n",
       "    code_shown=false;\n",
       "    $('div.input').hide()\n",
       "  });\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('''<script>\n",
    "  function code_toggle() {\n",
    "    if (code_shown){\n",
    "      $('div.input').hide('500');\n",
    "      $('#toggleButton').val('Show Code')\n",
    "    } else {\n",
    "      $('div.input').show('500');\n",
    "      $('#toggleButton').val('Hide Code')\n",
    "    }\n",
    "    code_shown = !code_shown\n",
    "  }\n",
    "\n",
    "  $( document ).ready(function(){\n",
    "    code_shown=false;\n",
    "    $('div.input').hide()\n",
    "  });\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}