18. Clustering - KMeans.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": [
    "# Clustering - K-Means\n",
    "\n",
    "© 2018 Daniel Voigt Godoy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Definition\n",
    "\n",
    "K-Means an ***unsupervided learning*** algorithm, meaning, it does not depend on ***labels***.\n",
    "\n",
    "It is used to iteratively ***cluster*** instances into ***k*** distinct groups. The number of clusters ***k*** must be provided.\n",
    "\n",
    "### 1.1 Algorithm\n",
    "\n",
    "It starts with ***k*** initial ***centroids*** - randomly select data points, for instance - and then:\n",
    "1. computes ***distances*** of each point to ***all centroids*** and assigns each point to the ***centroid*** corresponding to the ***shortest distance***\n",
    "2. ***recomputing*** the centroid coordinates using the ***mean of all points assigned to it***\n",
    "\n",
    "The process is repeated until ***no reassignment*** happens anymore, or the maximum number of iterations is reached (like 100).\n",
    "\n",
    "### 1.2 Centroids' Initialization\n",
    "\n",
    "One of the caveats of ***K-means*** algorithm is the fact that it is resulting clustering is ***dependent on initialization***. If you randomly initialize the centroids and apply K-means multiple times, it is very likely you'll end up with slightly different clusters every time.\n",
    "\n",
    "One way of mitigating this issue is to perform ***several random initializations*** and then choose the one that minimizes better the inertia. There are also other ***initialization methods***, but this is out of our scope now.\n",
    "\n",
    "### 1.3 Loss\n",
    "\n",
    "Effectively, the algorithm is ***minimizing*** the ***within-cluster squared sum of errors (SSE)*** or ***inertia***, computing it for each cluste using its points and the corresponding mean. \n",
    "\n",
    "At the extremes:\n",
    "- single cluster (no clustering): the same SSE as the full dataset\n",
    "- k = m (every point is its own cluster): the within-cluster SSE is ***zero***, as each point equals its cluster mean\n",
    "\n",
    "In between, the sum of all cluster's SSE is going to ***decrease towards zero*** as ***k approaches m***.\n",
    "\n",
    "### 1.4 Choosing k\n",
    "\n",
    "There are some possibilities for choosing the number of clusters ***k***:\n",
    "- if you know beforehand into how many groups your data should be clustered, this is your ***k***\n",
    "- if you don't know it, you can use the ***elbow*** rule (the same principle used in ***PCA***) for the ***total sum of SSE***\n",
    "\n",
    "Sometimes the elbow rule suggests a number of clusters which may not make the most sense for your data - then you can use a ***lesser*** number of clusters to better explain your data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Experiment\n",
    "\n",
    "Time to try it yourself!\n",
    "\n",
    "There are 35 points in two dimensions without any labels.\n",
    "\n",
    "The left plot shows the data points with ***k*** centroids marked as ***colored crosses***.\n",
    "\n",
    "The right plot shows the ***within SSE*** (or inertia) for ***each*** cluster. The title shows the ***total sum of SSE***. The initial value, when all points are ***gray*** is the ***SSE of the full dataset***.\n",
    "\n",
    "The sliders below allow you to:\n",
    "- perform each iterative step\n",
    "    - odd steps perform the ***recomputation of centroids*** \n",
    "    - even steps perform the ***assignment of points to a cluster***\n",
    "- change the number of clusters (***k***)\n",
    "    - every time you change k, it will ***randomly initialize*** the centroids - so you can restart the centroids sliding it back and forth\n",
    "\n",
    "Use the sliders to play with different configurations and answer the ***questions*** below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from intuitiveml.unsupervised.KMeans import *\n",
    "X, y = data()\n",
    "n_centroids = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "myk = plotKMeans(X, y, n_centroids)\n",
    "vb = VBox(build_figure(myk), layout={'align_items': 'center'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a46d62ee94184e54a192cb0eef977315",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'marker': {'color': 'black', 'line': {'color': 'black', 'width': 2…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1. Starting with ***2 clusters***, go ***step-by-step*** through the iterations:\n",
    "    - what happens to the ***total sum of SSE*** as you move through the iterations?\n",
    "    - how many iterations till you see ***no change***?\n",
    "    \n",
    "    \n",
    "2. Slide the number of clusters to some other number and ***back to 2*** (reinitializing centroids), set ***iteration to 1*** and repeat the steps from previous question:\n",
    "    - the initial iterations should be quite different - what about the final clustering?\n",
    "    \n",
    "    \n",
    "3. Set ***number of clusters to 3*** and ***iteration to 1*** and repeat the steps from first question:\n",
    "    - how the ***total sum of SSE*** compare between 2 and 3 clusters at the end?\n",
    "\n",
    "\n",
    "4. ***Reinitialize centroids*** for ***3 clusters***:\n",
    "    - did the final clustering change after reinitializing?\n",
    "\n",
    "\n",
    "5. Set ***iterations to 20*** and ***clusters to 1***:\n",
    "    - as you increase the number of clusters, what happens to the ***total sum of SSE***? Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Scikit-Learn\n",
    "\n",
    "[Clustering](https://scikit-learn.org/stable/modules/clustering.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. More Resources\n",
    "\n",
    "[Iterative Initial Centroid Search via Sampling for k-Means Clustering](https://towardsdatascience.com/iterative-initial-centroid-search-via-sampling-for-k-means-clustering-2b505119ae37)\n",
    "\n",
    "[Unsupervised Learning with Python](https://towardsdatascience.com/unsupervised-learning-with-python-173c51dc7f03)\n",
    "\n",
    "[An Introduction to Clustering and different methods of clustering](https://www.analyticsvidhya.com/blog/2016/11/an-introduction-to-clustering-and-different-methods-of-clustering/)\n",
    "\n",
    "[Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values](http://www.cs.ust.hk/~qyang/Teaching/537/Papers/huang98extensions.pdf)"
   ]
  },
  {
   "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": 5,
   "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": 5,
     "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
}