Week4_solutions_with_numpy_arrays.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 4 - k-means clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lab we'll implement the k-means algorithm.\n",
    "\n",
    "This notebook shows solutions using **numpy arrays**. (Exercise descriptions, docstrings etc all still describe the solution using lists and tuples.) Using numpy arrays requires a bit of extra knowledge compared to the main solutions notebook. However numpy is extremely useful for scientific programming in Python. \n",
    "\n",
    "In these solutions we're passing arrays around instead of lists of tuples. So our example data becomes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Five two-dimensional points\n",
    "example_data_2d = [(2,3),(5,3.4),(1.3,0.2),(3.1,3),(2.2,4)]\n",
    "example_data_2d = np.array(example_data_2d)\n",
    "\n",
    "# Five three-dimensional points\n",
    "example_data_3d = [(2,3,1.2),(5,3.4,4),(1.3,0.2,5.2),(3.1,3,3),(2.2,4,2)]\n",
    "example_data_3d = np.array(example_data_3d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2. ,  3. ],\n",
       "       [ 5. ,  3.4],\n",
       "       [ 1.3,  0.2],\n",
       "       [ 3.1,  3. ],\n",
       "       [ 2.2,  4. ]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_data_2d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2. ,  3. ,  1.2],\n",
       "       [ 5. ,  3.4,  4. ],\n",
       "       [ 1.3,  0.2,  5.2],\n",
       "       [ 3.1,  3. ,  3. ],\n",
       "       [ 2.2,  4. ,  2. ]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_data_3d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.3"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Just like Python lists, arrays are zero-indexed\n",
    "# First coordinate (\"x coordinate\") of the third point:\n",
    "example_data_2d[2,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 2)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 5 points, 2 dimensions\n",
    "example_data_2d.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These algorithms can be written more efficiently using numpy arrays. All the hints are set up to assume that you will write your functions using lists of tuples, but if you're experienced with Python, you can try using numpy arrays instead. Numpy implements vectorised maths and so it will be faster to run, and in many cases more concise to write."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "% matplotlib inline\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll use 2D data points so it's easy to visualise our results. This code generates some \"real\" clusters probabilistically, and a smattering of random points all over the space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# cluster 3 is a little more widely spread than clusters 1 and 2\n",
    "\n",
    "# cluster1 is centred at (1,1) and has standard deviation 0.2, and 20 points\n",
    "cluster1 = np.random.randn(20,2)*0.2+np.array([[1,1]])\n",
    "cluster2 = np.random.randn(20,2)*0.3+np.array([[2,1]])\n",
    "cluster3 = np.random.randn(20,2)*0.2+np.array([[1.5,2]])\n",
    "background = np.random.uniform(low=[0,0],high=[3,3],size=(30,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.92861439  1.1449852 ]\n",
      " [ 1.19387549  0.7846904 ]\n",
      " [ 1.0396265   1.18812744]\n",
      " [ 1.02491086  0.99236857]\n",
      " [ 1.10591285  0.84523391]]\n"
     ]
    }
   ],
   "source": [
    "points = np.concatenate([cluster1,cluster2,cluster3,background])\n",
    "# We'll represent the points as a list of tuples\n",
    "#points = [tuple(p) for p in points_array]\n",
    "# Show the first five\n",
    "print(points[:5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x10deab0f0>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD8CAYAAACSCdTiAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGutJREFUeJzt3W1sXFeZB/D/v64L7hZhRCKRThPcFVWkFkjdWqEoEqoC2qRlaSJaVmEloAgU8Sboqmsp4UP68oWgaEHitQrbioIQtLSRlUJQVBQQUC0BJ06ahmxQFoQaJ1LdUqeUusV2n/0wM814cmfm3plz55x77v8nWZmXG8+5cz3PnPuc55xLM4OIiMTpIt8NEBGR/CjIi4hETEFeRCRiCvIiIhFTkBcRiZiCvIhIxBTkRUQipiAvIhIxBXkRkYhd7OuFly1bZiMjI75eXkSkkA4dOvSsmS1Pu723ID8yMoLJyUlfLy8iUkgk/5Jl+47pGpKvJ/k7kkdJHid5T8I2ryP5EMlTJA+SHMnSCBERyUeanPwrANab2RoA1wLYSPKGpm0+AeB5M3sbgK8C+LLbZoqISDc6BnmrerF2d7D207x05SYAD9ZuPwLgvSTprJUiItKVVNU1JAdIHgHwDIDHzexg0yYVAE8DgJktADgH4M0Jv2cryUmSkzMzM721XEREOkoV5M1s0cyuBXAFgLUk3960SVKv/YKF6s1st5mNmdnY8uWpB4dFRKRLmerkzWwWwC8BbGx66jSAlQBA8mIAbwTwVwftExGRHnQsoSS5HMC8mc2SHALwPlw4sLoXwMcA/A+A2wAcMF1ySjyamJrGrv0ncWZ2DpcPD2F8w2psHq34bpZI36Wpk18B4EGSA6j2/B82s5+QvBfApJntBXA/gO+TPIVqD35Lbi0W6WBiahrb9xzD3PwiAGB6dg7b9xwDAAV6KZ2OQd7MngQwmvD4jobbLwP4kNumiXRn1/6TrwX4urn5Rezaf1JBXkpHa9dIdM7MzmV6XCRmCvISncuHhzI9LhIzBXmJzviG1RgaHFjy2NDgAMY3rPbUIhF/vC1QJpKXet5d1TUiCvISqc2jFQV1EShdIyISNQV5EZGIKciLiERMQV5EJGIK8iIiEVOQFxGJmIK8iEjEFORFRCKmIC8iEjEFeRGRiCnIi4hETEFeRCRiCvIiIhFTkBcRiZiCvIhIxBTkRUQipiAvIhIxBXkRkYjp8n8AJqamdT1QEYlS6YP8xNQ0tu85hrn5RQDA9Owctu85BgAK9CJSeB3TNSRXkvwFyRMkj5P8QsI2N5I8R/JI7WdHPs11b9f+k68F+Lq5+UXs2n/SU4tERNxJ05NfAHCnmR0m+QYAh0g+bmZ/aNru12b2r+6bmK8zs3OZHpfiUTpOyqxjT97MzprZ4drtvwE4ASCaT8jlw0OZHpdiqafjpmfnYDifjpuYmvbdNJG+yFRdQ3IEwCiAgwlPv5vkUZI/I3lNi/+/leQkycmZmZnMjc3D+IbVGBocWPLY0OAAxjes9tQicUnpOCm71EGe5GUAHgVwh5m90PT0YQBvNbM1AL4OYCLpd5jZbjMbM7Ox5cuXd9tmpzaPVvClD74DleEhEEBleAhf+uA7dDofCaXjpOxSVdeQHEQ1wP/AzPY0P98Y9M1sH8lvkVxmZs+6a2p+No9WFNQjdfnwEKYTArrScdIPIYwHpamuIYD7AZwws6+02OYtte1Acm3t9z7nsqEi3VA6TnwJZTwoTU9+HYCPADhG8kjtsS8CWAUAZnYfgNsAfJrkAoA5AFvMzHJor0gm9V6T796UlE+78aB+/v11DPJm9hsA7LDNNwB8w1WjRFxSOk58CGU8SGvXiIjkIJTybAV5EZEchDIeVPq1a0IQwgi8iLgVyniQgrxnWiBNJF4hjAcpXeOZZmSKSJ7Uk/cslBF4CYtSeOKKgrxnmpHpX2gBVSk8cUnpGs9CGYEvq6yzEiemprFu5wFcue2nWLfzQC6zF5XC868fx7lfFOQ90wJpfmUJqP2apq4Unl+hLEfgitI1AQhhBL6ssgTUfk1TVwrPr1CWI3BFPXkprYmpaVzE5BU7kgJqv3rYSuH5FduZlIK8lFL9lHwxYR29VgG1X9PUlcLzK5TlCFxRukZKKemUHAAGyJYBdXzD6iVVLwAwOED8/ZUFXLntp04rc5TC8yfpOBf5TEpBXkqp1an3q2Ytg2vzNPXhSwfx4ssLmJ2bB6BSx1iEshyBKwryUkrdDm429rDX7TyA51+aX/L83Pwi7nnseGEDglTFdCalnLyUkovBzVZnA8+/NF/YcjuJj4J8oGKajBEiF4Ob7Xr9mrgkoVC6JkCa1t4fvZ6Sj29YjTseOpL4XFHL7SQ+6skHSNPai2HzaAXDQ4OJzxW13E7ioyAfoNgmY8Ts7luu0cQlCZrSNQHStPbiyFpuF9qKlxI/BfkAxTYZI3Zpc/saaxEfaAnTuvthbGzMJicnvbx2EajHl580720e7/+6nQcSz9AGSLxqpuMsqZA8ZGZjabdXTz5QMU3GCEma3nRePe5WYyr19XNc9+zVURBAA69SMmkql/KqbkozpuKqiiq2NdGlex2DPMmVJH9B8gTJ4yS/kLANSX6N5CmST5K8Lp/mivQmTeVSq22mZ+d6CpJJs2w7taVbKsOVujTpmgUAd5rZYZJvAHCI5ONm9oeGbW4CcFXt510Avl37Vwom9lP8NJVLrbYB0FM6pbkS5yIycaljF1VUKsOVuo49eTM7a2aHa7f/BuAEgOa/8E0AvmdVvwUwTHKF89ZKrmI9xW9cIuLvryxgcGDphUKaK5fa9bh77Q1vHq3giW3r8eed78d//dua3GrsY1sTXbqXKSdPcgTAKICDTU9VADzdcP80LvwikMDFeIrf/MU1OzcPGPCmSwdbrllTX9emlenZOSfrCeV5cRBdXUrqUlfXkLwMwKMA7jCzF5qfTvgvF5yHktwKYCsArFq1KkMzpR9iPMVP+uKaf9Vw6SUXY2rHv7T8f5tHK9i1/2TLtI2rSpi8qqhiWxNdupcqyJMcRDXA/8DM9iRschrAyob7VwA407yRme0GsBuo1slnbq3kKsaZtt18cdXHJaZn50Ak9FZq5uYXcefDRwGEOZlJZbgCpKuuIYD7AZwws6+02GwvgI/WqmxuAHDOzM46bKf0QYyn+Flz043pHaAa4JMv9V21aBbFuIXEK01Ofh2AjwBYT/JI7edmkp8i+anaNvsA/AnAKQDfAfCZfJoreYrxAtJZv7iS0juG6qzUVoo+biFx65iuMbPfoH1nBlZdG+Gzrhol/sR2ip81N91uVurQ4EDixb/b/T8R37SsgUQvyxdXq3GJSu3L4c6Hj+ZW2y6SBy1rINKgXXpn82gl19p2kTyoJy/SoFN6R6WJUjRaalhECiH2JTfS0lLDIgIgrqCoC650Tzl5kQjFtg5RjEtu9IuCvEiEYguKMS650S9K14hEKI+g6DP9E+OSG/2inrxIhFwvNew7/RPjkhv9oiAvkpPGdexdLE2cheug6Dv9E+OSG/2idI1nMVVAyHm+q0Fc1/OHkBOPbcmNflGQ98h3IJD8tOv59uvYugyKyokXl9I1Hvk+BZb8hNDzdUk58eJSTz5HnVIxsQUCOS+2nq+WcyguBfmcpEnFxBYI5LzxDauXHH+g+D1f5cSLSemanKRJxegUOF6qBpFQRNmTD6FiJU0qRqfAcVPPV0IQXZAPpWIlbSpGgUBE8hRduiaUihWlYkQkBNH15EOpWFEqRkRCEF2QD6liRakYEfEtunSN0iTigs91Z0Rciq4nrzSJ9CqUwXsRF6IL8oDSJNKbENadkWxCKJsOVZRBXqQXoQzeSzo682qvY06e5AMknyH5VIvnbyR5juSR2s8O980U6R/XF9yQqrzGOUIpmw5VmoHX7wLY2GGbX5vZtbWfe3tvVpw0mFcMGrx3L88rS+nMq72O6Roz+xXJkfybEjedUhZHPwbvy5ZDznOcI6Sy6RC5ysm/m+RRAGcA/KeZHXf0e6OhwbxiyXPwvoxf+Hn2tmNc8dMlF3XyhwG81czWAPg6gIlWG5LcSnKS5OTMzIyDly4OnVJKXRlzyHmOc2jFz/Z67smb2QsNt/eR/BbJZWb2bMK2uwHsBoCxsTHr9bWLRKeUUlfGL/y8e9sqm26t5548ybeQZO322trvfK7X3xsbDeZJXRmrd9Tb9qdjT57kDwHcCGAZydMA7gIwCABmdh+A2wB8muQCgDkAW8ysVL30NDQTV+rKmkNWb9sP+orHY2NjNjk56eW1RXzLq7qmbFU7ZUTykJmNpd1eM15FPMijV1vGqh3pTEFeJBKtqnbu3nvca42/zi78im6pYZGyalWdMzs372x2ddaZq3nOdJV0FORFItGuOsdVDX7WGv8yzgkIjYK8SCTaVee4qsHPWuNfxjkBoVGQF4nE5tEK3nTpYOJzrmrws9b4l3FOQGgKF+S1kqNIa3d94JpcJ91lndSnSYD+Faq6RiViIu3lPeku6+/XJED/CjUZat3OA4nrv1SGh/DEtvWumiYiEqysk6EKla7RII6ISDaFCvIaxBERyaZQOfmyLuzkm2YsSj/p782tQgV5DeK4k/aDpMFu6Sf9vblXqIFXcaP5gwRUz4iS1vfudbA7hl5ZDPtQFCqu6EyrUEpHWa4328tgdwy9sqLsQyxfRCqucK9QA6/iRpYPUi+D3TGsW1KEfYhpETAVV7inIF9CWT5ISTMWiWog6TTjOIZeWSj70G6mdxG+iNLSDFn3FORLKMsHqfHanEA1wNdHcTr1GGPolYWwD5166kk57HaPh0zXgnVPQb6Esn6QNo9W8MS29agMD6F5mL5djzGGXlkI+9Cppz5AJv6/Vo+Hrv739ued78cT29YrwPdIA68l1c3l57KmLmIoeQ1hHzq974stKuRaPS7loiAvqV0+PJSYAmiXunBxLVPflSN5XI81i07ve6XF85UCpcW65ftvowiUrpHUfKQuYqoc6Van9z2ElJIP+ttIRz15SS1t6sJl7ypLTX+sOr3vPlNKPnvS+ttIR0G+xLr5gHZKXXQ7eahVW0IpYfSt0/vuI6Xke6KY/jbSUbqmpPI61e2mZrtdW0IoYZRkvuvz9beRTscgT/IBks+QfKrF8yT5NZKnSD5J8jr3zRTX8vqAdtO7atWWu/ceL22+uQh896T1t5FOmp78dwFsbPP8TQCuqv1sBfDt3pslecvrA9qqFzXc4gLT7V5zdm4eADQ5JkEI1zr23ZPWxKl0OubkzexXJEfabLIJwPesupzlb0kOk1xhZmcdtVFy0E05ZBrjG1Zj/JGjmF9cWqP94ssLmJiaTvwAtmoLUO3la0LMUr5z4XVpru+Q98Cs7/LWInCRk68AeLrh/unaYxKwPE91FxYvnIQz/6q1nRnbigbRLuQ7F17XqSetEscwuKiuSZo7nTjVjuRWVFM6WLVqlYOXlm7lUXZX/1C3mmfZbmbsPY8dx/MvzV/wXFkG0bL0eH3nwhu160mrxDEMLoL8aQArG+5fAeBM0oZmthvAbqB60RAHry09cH2qm/ShbtQuYN/1gWtKe2nHrOmXvFJtroX0ZVRmLtI1ewF8tFZlcwOAc8rHl1O7D2+ngF3mQbSs6ZfxDasxOLD0BHpwgMF9IfoemJWqjj15kj8EcCOAZSRPA7gLwCAAmNl9APYBuBnAKQAvAfh4Xo2VsLXqYQ6QLQO21h7pssfbfB4c4HlxmoFZyV+a6poPd3jeAHzWWYuksFp9qNsF+E5piomp6SX5+uGhQdx9yzVRfRFkTb/s2n8S868ujer1ge2Q3pcQVvAULWsgXWrXA0/7oe40MDcxNX1BOebs3DzGf3wUQFjXWO1F1h5vkXLdKnH0T0FeMuvUA0/7oe4UrHbtP3lBvT2Qf6+13ymkrF+ORRl4lTAoyEtmrkrjhi8dbFs22a5nmlev1ddEoyxfjsp1SxZaoEwyc5EumJiaxosvL1zweGOVSLueaV691lAmGrVT5kokyU49ecnMRbogafAQAP7pkotfC1atlkgYvCi/csGi5LuV65a01JOXzFwsidAqaJ6bO5++2Txawa7b1uBNDYubDQ8NYteH1gBALgt0qbZbYqOevGTmojQu7dlAUo81z7y58t0SGwV56Uqv6YK0wTSp0iXPNVFU2y2xUZAXL9IE01Y99lbr47jKm/cz3+1rxm+oM41DbVeRKciLN52Caase+wCJRbtw0LZoeXPXaae0ATKU9eiL0q6i08CrBKtVz3zRLIrLvrks18yydnuoZaKhtqvoFOQlWK165vW68KLXibss18wSIEMtEw21XUVX2nSNcn/90+173W5wNoY6cZfLE2QJkGlft9+fES3XkI9S9uR1WbL+6eW93jxawa3XVzDA6trpAyRuvb74wb3O5SUYs9T3p3ldH5+RPC9JWWalDPLK/fVPL+/1xNQ0Hj00/dog66IZHj00Xegv44mp6dcmce3afxK3Xl9xknbKEiDTLIvg4zOi5RryUcp0jXJ//dPLex3bNUKTqkcePTTtJJBlre/vlO7y9RmJIQ0XmlIGeeX++qeX9zrvQNPvnHPeX1ouA6Q+I/EoZbpGub/+6eW9znMdGR855yKdQeozkl1jKs7lekq9KmWQV+6vf3p5r/MMND5yzkVa/EyfkWxCLuagJcwc7IexsTGbnJz08tpSHHmlVK7c9tPEa18TwJ93vr/n35+kOScPtL8GrhTHup0HEtNbleEhPLFtvdPXInnIzMbSbl/KnLwUR14DcT5yzlr8LF4hp+IU5KWUfC0prOqROIU8UF3KnLyIcs7iUsgD1erJS2mpVy2uhJyKU5AXEelCUlGA60FWF1Kla0huJHmS5CmS2xKev53kDMkjtZ9Pum+qiEgYQi6ZbNYxyJMcAPBNADcBuBrAh0lenbDpQ2Z2be3nvx23U0QkGEVa/ypNT34tgFNm9icz+weAHwHYlG+zRETCFXLJZLM0OfkKgKcb7p8G8K6E7W4l+R4AfwTwH2b2dMI2IuKIrongT8glk83S9OSZ8FjzZMHHAIyY2TsB/BzAg4m/iNxKcpLk5MzMTLaWishripQTjlHIJZPN0gT50wBWNty/AsCZxg3M7Dkze6V29zsArk/6RWa228zGzGxs+fLl3bRXRFCsnHCMijTPIk265vcAriJ5JYBpAFsA/HvjBiRXmNnZ2t1bAJxw2koRWaJIOeFYFWWeRccgb2YLJD8HYD+AAQAPmNlxkvcCmDSzvQA+T/IWAAsA/grg9hzbLFJ6RcoJi1+pJkOZ2T4A+5oe29FwezuA7W6bJiKt+Fp7R4pHM15FCijkafQSFgV5cULlfP1XlJyw+KUgLz1LukD19j3HAEBBSMQzLTUsPVM5n0i4FOSlZyrnEwmX0jU9UB66SuV8IuFST75LmlZ+XpGmeIuUjYJ8l5SHPq9IU7xFykbpmi4pD72UyvlE2vOV3lVPvkut8s3KQ4tIM5/pXQX5LikPLSJp+UzvKl3TJU0rF5G0fKZ3FeR7oDy0iKThs8xY6RoRkZz5TO+qJy8ikjOf6V0FeZFIaUZ2WHyldxXkRSKklUGlTjl5kQhpRrbUKciLREgzsqVOQV4kQpqRLXUK8iIR0oxsqdPAq/REFRxh0oxsqVOQl66pgiNsmpEtgIJ8aeTR425XwaHgIhIGBfkSyKvHrQoOkfClGngluZHkSZKnSG5LeP51JB+qPX+Q5Ijrhkr38qqZVgWHSPg6BnmSAwC+CeAmAFcD+DDJq5s2+wSA583sbQC+CuDLrhsq3curx60KDpHwpenJrwVwysz+ZGb/APAjAJuattkE4MHa7UcAvJck3TVTepFXj1vXdhUJX5qcfAXA0w33TwN4V6ttzGyB5DkAbwbwrItGSm/GN6xekpMH3PW4VcEhErY0QT6pR25dbAOSWwFsBYBVq1aleGlxQTXTIuWVJsifBrCy4f4VAM602OY0yYsBvBHAX5t/kZntBrAbAMbGxi74EpD8qMctUk5pcvK/B3AVyStJXgJgC4C9TdvsBfCx2u3bABwwMwVxERHPOvbkazn2zwHYD2AAwANmdpzkvQAmzWwvgPsBfJ/kKVR78FvybLSIiKSTajKUme0DsK/psR0Nt18G8CG3TRMRkV5pFUoRkYgpyIuIRExBXkQkYvRVBENyBsBfMv63ZYhvgpX2qThi3C/tU3HU9+utZrY87X/yFuS7QXLSzMZ8t8Ml7VNxxLhf2qfi6Ha/lK4REYmYgryISMSKFuR3+25ADrRPxRHjfmmfiqOr/SpUTl5ERLIpWk9eREQyCDLIx3i5wRT7dDvJGZJHaj+f9NHOLEg+QPIZkk+1eJ4kv1bb5ydJXtfvNmaVYp9uJHmu4TjtSNouJCRXkvwFyRMkj5P8QsI2hTpWKfepUMeK5OtJ/o7k0do+3ZOwTfbYZ2ZB/aC6CNr/AfhnAJcAOArg6qZtPgPgvtrtLQAe8t1uB/t0O4Bv+G5rxv16D4DrADzV4vmbAfwM1esN3ADgoO82O9inGwH8xHc7M+7TCgDX1W6/AcAfE/7+CnWsUu5ToY5V7b2/rHZ7EMBBADc0bZM59oXYk4/xcoNp9qlwzOxXSLhuQINNAL5nVb8FMExyRX9a150U+1Q4ZnbWzA7Xbv8NwAlUr+bWqFDHKuU+FUrtvX+xdnew9tM8aJo59oUY5JMuN9h88JZcbhBA/XKDoUqzTwBwa+1U+RGSKxOeL5q0+100766dUv+M5DW+G5NF7fR+FNVeYqPCHqs2+wQU7FiRHCB5BMAzAB43s5bHKW3sCzHIO7vcYEDStPcxACNm9k4AP8f5b+siK9pxSuMwqtPK1wD4OoAJz+1JjeRlAB4FcIeZvdD8dMJ/Cf5Yddinwh0rM1s0s2tRvQLfWpJvb9ok83EKMchnudwg2l1uMCAd98nMnjOzV2p3vwPg+j61LU9pjmWhmNkL9VNqq15nYZDkMs/N6ojkIKrB8Admtidhk8Idq077VNRjBQBmNgvglwA2Nj2VOfaFGORjvNxgx31qyn/egmqOsej2AvhorXLjBgDnzOys70b1guRb6jlQkmtR/Qw957dV7dXaez+AE2b2lRabFepYpdmnoh0rkstJDtduDwF4H4D/bdosc+xLdWWofrIILzeYcp8+T/IWAAuo7tPt3hqcEskfolrBsIzkaQB3oTpYBDO7D9Wrid0M4BSAlwB83E9L00uxT7cB+DTJBQBzALYE3sEAgHUAPgLgWC3fCwBfBLAKKOyxSrNPRTtWKwA8SHIA1S+kh83sJ73GPs14FRGJWIjpGhERcURBXkQkYgryIiIRU5AXEYmYgryISMQU5EVEIqYgLyISMQV5EZGI/T/+DPvd2k+p0gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot the points\n",
    "# points[:,0] will retrieve all points (:), but only the first (x) coordinate (0)\n",
    "\n",
    "plt.scatter(points[:,0], points[:,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## K-means "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function to initialise centroids is provided for you. This function returns a list of k centroids, randomly placed. Notice that it is completely random - we could improve this function by trying to space the centroids far apart from one another."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now takes in data as numpy array, and returns centroids as numpy array\n",
    "def initialise_centroids(data, k):\n",
    "    \"\"\"\n",
    "    Place centroids randomly into range of data of arbitrary dimension.\n",
    "    Takes a list of N data points.\n",
    "    Returns a list of k centroids, each of which will be a tuple of the same\n",
    "    dimensionality as the data points.\n",
    "    \"\"\"\n",
    "    d = data.shape[1]\n",
    "    arr = np.array(data)\n",
    "    minvals = np.min(data,axis=0)\n",
    "    maxvals = np.max(data,axis=0)\n",
    "    centroids = np.random.uniform(low=minvals,high=maxvals,size=(k,d))\n",
    "    return centroids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1:**\n",
    "\n",
    "Complete the function `assign_points()`. Given a list of k centroids and a list of N points, find which is the closest centroid to each point. Your function should return a list of N integers. Each integer should be a number from 0 to k-1, corresponding to the closest centroid for that point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.82842712475\n"
     ]
    }
   ],
   "source": [
    "# This function is provided for you. It calculates Euclidean distance between two points.\n",
    "from kmeans_utilities import euclidean_distance\n",
    "print(euclidean_distance((1,1),(3,3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now takes in centroids and data as numpy arrays of shape (k,d) and (N,d),\n",
    "# and returns an array of length N specifying the closest centroids\n",
    "\n",
    "def assign_points(centroids, data):\n",
    "    \"\"\"\n",
    "    Assign each point to its closest centroid.\n",
    "    Takes in a list of k centroids and a list of N data points.\n",
    "    Should return a list of N ints, each a number from 0 to k-1,\n",
    "    representing the index of the closest cluster.\n",
    "    \"\"\"\n",
    "    # subtract distances, square, sum along d-dimension, square root. gives array k by d\n",
    "    # use numpy broadcasting to make dimensions of both arrays match [centroid,point,dimension] (i.e. [k,N,d])\n",
    "    vectors_data_to_centroids = centroids[:,np.newaxis,:] - data[np.newaxis,:,:]\n",
    "    # square then sum over the dimension axis to get Euclidean distance\n",
    "    # the resulting array all_distances is of shape (k,d)\n",
    "    all_distances = np.sqrt(np.sum(vectors_data_to_centroids**2,axis=2))\n",
    "    # for each point, pick minimum distance centroid. argmin gives the index of the minumum value\n",
    "    closest_centroids = np.argmin(all_distances, axis=0)\n",
    "    return closest_centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1, 0, 1, 1])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return [0, 1, 0, 1, 1]\n",
    "example_centroids = np.array([(2,2),(4,4)])\n",
    "assign_points(example_centroids, example_data_2d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0, 1, 1, 1])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return [1, 0, 1, 1, 1]\n",
    "example_centroids = np.array([(5,2,0),(3,1,1)])\n",
    "assign_points(example_centroids, example_data_3d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2:**\n",
    "\n",
    "Complete the function `calculate_mean_centroids()`. This function should take in the list of data points, the list of assignments to clusters, and k, and return the a list of centroids.\n",
    "\n",
    "The function `points_average()` is provided for you. Given a list of points, it finds the mean. You need to pass it the correct points for each cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function is provided for you\n",
    "\n",
    "# Notice we now use average_point_array not average_point - this is the\n",
    "# same but returns a 1D array instead of a tuple to represent the coordinate\n",
    "\n",
    "from kmeans_utilities import average_point_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Data and assignments should now both be arrays, and centroids returned\n",
    "# will be an array with shape (k,d)\n",
    "# This solution isn't much more vectorised than the non-array version, \n",
    "# as we still have to iterate over clusters\n",
    "\n",
    "def calculate_mean_centroids(data, assignments, k):\n",
    "    \"\"\"\n",
    "    Take data of shape (N,d) and assignments of shape (N) and\n",
    "    return centroids array of shape (k,d).\n",
    "    \"\"\"\n",
    "    assert np.max(assignments) < k\n",
    "    centroid_list = [average_point_array(data[assignments==c,:]) for c in range(k)]\n",
    "    centroids = np.concatenate([centroid[np.newaxis,:] for centroid in centroid_list])\n",
    "    return centroids\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.65      ,  1.6       ],\n",
       "       [ 3.43333333,  3.46666667]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return centroids [( 1.65,  1.6 ), (3.43333333,  3.46666667)]\n",
    "calculate_mean_centroids(example_data_2d, np.array([0, 1, 0, 1, 1]), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5.  ,  3.4 ,  4.  ],\n",
       "       [ 2.15,  2.55,  2.85]])"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return centroids [(5, 3.34, 4), (2.15,2.55,2.85)]\n",
    "calculate_mean_centroids(example_data_3d, np.array([1, 0, 1, 1, 1]), 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3:**\n",
    "\n",
    "Complete the `kmeans()` function to carry out k-means clustering. You can use the functions you created in the first two exercises. You only need to fill in the missing lines in the iterative loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instead of importing plot_kmeans, here's a version that uses arrays \n",
    "\n",
    "def plot_kmeans(data, centroids, assignments, k):\n",
    "    for cluster in range(k):\n",
    "        cluster_points = data[assignments==cluster, :]\n",
    "        plt.scatter(cluster_points[:,0],cluster_points[:,1])\n",
    "    # draw centroids\n",
    "    plt.scatter(centroids[:,0],centroids[:,1],marker='x',s=80,c='k')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Input data should now be an array of shape (N,d) representing the points\n",
    "\n",
    "# We no longer need the points_equal function to make the code more readable \n",
    "# - it's pretty easy to calculate if all points are equal with numpy subtraction\n",
    "\n",
    "def kmeans(data, k):\n",
    "    \"\"\"\n",
    "    Implement k-means clustering on a given set of points.\n",
    "    data should be a list of N points, where each point is a tuple.\n",
    "    Returns a tuple of (centroids, cluster_assignments)\n",
    "    where \n",
    "    centroids is a list of centroid points, and each centroid is a tuple\n",
    "    cluster_assignments a list of N numbers representing cluster assignments,\n",
    "     where each number is between 0 and k-1.\n",
    "    \"\"\"\n",
    "    epsilon = 0.001\n",
    "    N, d = data.shape\n",
    "    centroids = initialise_centroids(data, k)\n",
    "    cluster_assignments = assign_points(centroids, data)\n",
    "    old_centroids = centroids - 1 # ensure not equal at start\n",
    "    # This uses subtraction of entire arrays (via numpy)\n",
    "    # to check that all centroid coordinates match previous values\n",
    "    while not np.all(centroids - old_centroids < epsilon):\n",
    "        old_centroids = centroids\n",
    "        centroids = calculate_mean_centroids(data, cluster_assignments, k)\n",
    "        cluster_assignments = assign_points(centroids, data)\n",
    "    return (centroids, cluster_assignments)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 1.3  ,  0.2  ],\n",
       "        [ 3.075,  3.35 ]]), array([1, 1, 0, 1, 1]))"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Answer can be random depending on random initialisation. \n",
    "# Likely solutions are:\n",
    "# centroids [(1.3,0.2),(3.075,3.35)]\n",
    "# cluster assignments [1, 1, 0, 1, 1] or [0, 0, 1, 0, 0]\n",
    "#  OR\n",
    "# centroids [(2.1,3.5),(3.1333,2.2)]\n",
    "# cluster assignments [0, 1, 1, 1, 0] or [1, 0, 0, 0, 1]\n",
    "#  OR\n",
    "# centroids [(5,3.4),(2.15,2.55)]\n",
    "# cluster assignments [1, 0, 1, 1, 1] or [0, 1, 0, 0, 0]\n",
    "\n",
    "kmeans(example_data_2d,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now test on the 2D data we created at the top of the notebook:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.9052757   0.94465108]\n",
      " [ 1.51522242  2.12672629]\n",
      " [ 2.09518476  1.00673772]]\n",
      "[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n",
      " 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0 1 0 0 2 1 0 2 2 2 2 2 1 0\n",
      " 1 0 1 2 1 0 1 0 1 0 0 2 0 1 0 2]\n"
     ]
    }
   ],
   "source": [
    "k = 3\n",
    "centroids, assignments = kmeans(points, k)\n",
    "print(centroids)\n",
    "print(assignments)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAHvdJREFUeJzt3X1sXNWZBvDnsTHEBBSzTaQEJxBo2XT5CCREfDTaXTvpEiBLEpU0G7ZqoWqJ6IdwrSoq7B8hZbWCCqmW0+0WpQsqVBUlCygKJCi0taOy7Tatk0CADVRZaBebsLhADA0OJPG7f8xMPB7fmbl35t659577/CQr4zvX9rme+J1z33POe2hmEBERtzTF3QAREQmfgruIiIMU3EVEHKTgLiLiIAV3EREHKbiLiDhIwV1ExEEK7iIiDlJwFxFx0Clx/eDp06fb3Llz4/rxIiKptGfPnj+Z2Yxq58UW3OfOnYuBgYG4fryISCqR/KOf86qmZUhOIflbks+TfInktz3OOY3koyQPktxNcm7wJouISFj85Nw/BLDEzC4FcBmAa0leVXLOlwC8a2afANAD4DvhNlNERIKoGtwt58/5T1vyH6WlJFcCeCj/+DEAS0kytFaKiEggvmbLkGwm+RyAtwD8zMx2l5zSDuB1ADCz4wBGAHwszIaKiIh/voK7mZ0ws8sAzAZwBcmLS07x6qVPKhRPch3JAZIDw8PDwVsrIiK+BJrnbmaHAewCcG3JU4MA5gAAyVMATAPwjsfXbzazRWa2aMaMqjN5RESkRn5my8wg2ZZ/3Arg0wBeLjltG4Cb849XA+gzbfEkIhIbP/PcZwF4iGQzcm8GW8zsKZJ3Axgws20AHgDwY5IHkeuxr42sxSLV7N8C/OJuYGQQmDYbWLoBmL8m7laJNFTV4G5m+wEs8Di+oejxUQCfDbdpIjXYvwV48nbg2Gju85HXc58DCvCSKaotI275xd3jgb3g2GjuuEiGKLiLW0YGgx0XcZSCu7hl2uxgx0UcpeAublm6AWhpnXispTV3XCRDFNzFLfPXADdsAqbNAcDcvzds0mCqZE5sJX9FIjN/jYK5ZJ567iIiDlJwFxFxkIK7iIiDFNxFRByk4C4i4iAFdxERBym4i4g4SMFdRMRBCu4iIg5ScBcRcZCCu4iIgxTcRUQcpOAuIuIgBXcREQcpuIuIOEjBXUTEQQruIiIOUnAXEXGQgjsA7N8C9FwMbGzL/bt/S9wtEhGpS9XgTnIOyX6SB0i+RLLL45wOkiMkn8t/pGer+f1bgCdvB0ZeB2C5f5+8XQFeRFLNzwbZxwF808z2kjwTwB6SPzOz/y4571kz+/vwmxixX9wNHBudeOzYaO64NlkWkZSq2nM3s0Nmtjf/+H0ABwC0R92whhkZDHZc0kUpN8moQDl3knMBLACw2+Ppq0k+T/JpkheF0LbGmDY72HFJD6XcJMN8B3eSZwB4HMA3zOy9kqf3AjjXzC4F8D0AW8t8j3UkB0gODA8P19rmcC3dALS0TjzW0po7LulWKeUm4jhfwZ1kC3KB/Sdm9kTp82b2npn9Of94B4AWktM9zttsZovMbNGMGTPqbHpI5q8BbtgETJsDgLl/b9ikfLsLlHKTDKs6oEqSAB4AcMDMvlvmnJkA/s/MjOQVyL1pvB1qS6M0f42CuYumzc6nZDyOi0Rp/5bcHeLIYO7/29INDY8xfmbLLAbweQAvkHwuf+yfAJwDAGZ2P4DVAL5C8jiAUQBrzcwiaK+If0s35HLsxakZpdwkaoWxnsL/u8JYD9DQAM+4YvCiRYtsYGAglp8tGZKAHpRkTM/FZe4Y5wDdL9b97UnuMbNF1c7z03MXSS+l3KTREjLWo/IDIiJhSsj0agX3uGmRjYhbEjK9WmmZOCVk4EVEQlT4203BbBmJiuraiLgpAWM9SsvEKSEDL5IwStVJCBTc45SQgZdMS1ogVT0cCYmCe5wSMvCSWUkMpKqHIyFRcI+T6trEK2ggbUQvX6m6+CXtbq5GGlCNWwIGXjIrSCBt1Mwm1cOJl0Mz2NRzl+wKMubRqHSJUnXxcigtpuAu2bR/C/DRkcnHywXSRqVLlKqLl0NpMaVlJHtKb70LWv8CuO473oG0XLqETbncbJgLVZSqi49DaTH13CV7vG69AeDUqeWDqle6BADsBBIz00bq51BaTMFdsqeWW+/SdAmbJ59zbBR4+luhNFFi4lBaTGkZyR6ft979/f3o6OhAbjMyTEiX2F3TsOsPx9F5Xsmf0Og7ud57CoOB5DmSFlPPXbLHx613f38/lixZgu7ubpRuaGNm6O4/BUse/gD9rx2f/P1TOLNC3KPgnlSOLKRIJB+33h0dHejq6kJvb++EAG9m6O7uRu+z76DrylPRMdcjPZPCmRXiHqVlksihhRSJVeXWmyR6enoAAL29vQCAnp6eXGDv7UVXVxd6Zm4Fj747+YtTOLNC3KPgnkQqBZwIpQG+EOS7urrQ09MDvvApbcAtiaUNspNoYxsAr9eFwMbDjW5N5pkZmprGM5hjY2Pjg6x+N+DWRt0SEm2QnWYOLaRIu0KOvVh3d3eu5076m1mhNJvEQAOqSeTQQopUyg9m213T0P2300/m2MfGxjwHWatyqF6JpId67kmUkD0YnVQtPZLvZdtHH6B754fo3f0Ruq4+HT1fvLrsIOvJFE05ZRdNvZ6bCaXXWCKg4J5UjiykSBQ/6ZF8L3vXH07kAvuVp6Ln75rBvn8GLv2HSQF+5cqV6OzsrPxzy6XZwPHjYaZqlN8X+EjLkJxDsp/kAZIvkezyOIckN5E8SHI/yYXRNFekDn7SI/ledud5p6DvC6ejZ9lpuZ55Ue+7EOD7+vqqB3agTF0aYtKgeRipmiTuLiWx8JNzPw7gm2b2VwCuAvA1kheWnHMdgAvyH+sA/CDUVoqEwU9NmaJB687zThlPubBpQoAk6S+wA96LpjxnQ1Voo1/K70te1eBuZofMbG/+8fsADgBoLzltJYCHLec3ANpIzgq9tRIt11fF+tmco1L1x3p6wPPXAN0v5qaydr+YD/AB2uiXQ/XIpT6BZsuQnAtgAYDdJU+1AyhOKg5i8huAJJmrt/PFb1gfHQGaT534fOkspEIvu1zVxyduDeeNL6oZUUF2lxKn+Q7uJM8A8DiAb5jZe6VPe3zJpPtOkutIDpAcGB4eDtZSiZaLt/Olb1ij7wBmuU05KpVznb8GsLHy3zeMN76oSstqGq3k+ZotQ7IFucD+EzN7wuOUQQDF95mzAbxRepKZbQawGcitUA3cWomOi7fzXm9YY8dym3J867XKX1t2hkteGOUgopgRpWm0klc1uDM3ovQAgANm9t0yp20D8HWSPwVwJYARMzsUXjMlci6uiq3lDevkNMLX4TmjZcL3qRD846RptAJ/aZnFAD4PYAnJ5/If15O8jeRt+XN2AHgVwEEAPwTw1WiaK5Fx8XY+aP55QhoHyAX2SguUmP4xCXFW1Z67mf0nKv8Ph+XWYX8trEZJDFy8nV+6IVjVRs+9VfM5+tF3MbkXb6rUKYmlFaoyzrXb+aBvWOXSNZ6BvcrXiMRMwV3cFuQNq9q4g2tjEuI0VYUUKag07uDimIQ4TT13kQI/aRyXxiRSYvur29G7txdvHnkTM6fORNfCLiw/f3nczUo87cQkIom1/dXt2PjrjTh64ujJY1Oap2DjpzZmNsD73YlJaRkR1zhUI6h3b++EwA4AR08cRe/e3phalB5Ky4i4xLEt/d488mag4zJOPXcRl0RRIyjGO4GZU2cGOi7jFNxFXBJ2jaCYq4V2LezClOYpE45NaZ6CroWT9gySEgruIi4Ju+RvzNVCl5+/HBs/tRGzps4CQcyaOivTg6lBKOcuEoW49jENWnKhmgRUC11+/nIF8xoouMds674h3LfzFbxxeBRnt7Vi/bJ5WLVA+5ykWpyDmmHXCHKxWmhGKLjHaOu+Idz5xAsYPXYCADB0eBR3PvECACjAp1mlVEYjeu9h1ggK+05AGkY59wht3TeExff24bw7tmPxvX3Yum9owvP37XzlZGAvGD12AvftfKWRzZSwJSCVEZqodoySyKnnHhE/vfI3DpeWl0XF45ISrqUyXKsWmhHquUfET6/87LbW0i+reFxSQkXGJAGcDO7V0iGN4KdXvn7ZPLS2NE94vrWlGeuXzYu0bRIxpTIkAZxLyyRlkPLstlYMeQT44l55oT2aLeMgpTIkZs4F90rpkEYGzfXL5k14kwG8e+WrFrQrmItI6JwL7kkZpFSvXETi5Fxw95MOaRT1ykUkLs4NqGqQUurmUD10yS7neu5Kh0hdHKuHLtmlbfZEivVcXGYB0hyg+8XGt0eqytoeq3632XOu5y5SF5dKB2RA6R6rh44cwsZfbwQApwO8H1Vz7iQfJPkWSc9uC8kOkiMkn8t/aBmepFfY9dAlUtpjtTw/A6o/AnBtlXOeNbPL8h+NqeKfQklYOStVqHRAJLa/uh3XPHYN5j80H9c8dg22v7o9lO+rPVbLqxrczeyXAN5pQFucVlg5O3R4FIbxlbMK8AkTcemAqIJckhVSJ4eOHILBTqZOwrh27bFaXlhTIa8m+TzJp0leFNL3dIrK+6bI/DW5wdONh3P/hhjYowpySRZl6kR7rJYXRnDfC+BcM7sUwPcAbC13Isl1JAdIDgwPD4fwo9MjKStnJT5ZzQ9HmTrRHqvl1T1bxszeK3q8g+S/kZxuZn/yOHczgM1AbipkvT87TZK0clbikdX88MypM3HoyCHP42HQHqve6u65k5xJkvnHV+S/59v1fl/XaOWsZDU/rNRJPPxMhXwEwH8BmEdykOSXSN5G8rb8KasBvEjyeQCbAKy1uFZGJdiqBe245zOXoL2tFQTQ3taKez5ziVbOZkhWg5xSJ/HQClWRBopyNWXWVmpmlVaoiiRQVPlhrdSUUs5VhRTJoqzOxJHyFNxFHOA1G6XS8VoFXYSVxUVbSaG0jIgDmtiEMRvzPB6WoKkfpYripZ67iAO8Anul47UImvpRqiheCu4iDpg1dVag47UIuggrq4u2kiJ1wV2VFUUma8Qc+qCLsLK6aCspUhXcVVlRxFsjFgoFfQPJ6qKtpEjVgGqlyopa6SlZF3WNlcL39rtQKuj5Eq5UBXdVVhSJV9A3EBX1ik+q0jLlKiiqsqKIyESpCu6qrBgPDWKLpE+q0jKFvPp9O1/BG4dHcXZbK9Yvm6d8e0Bb9w35/h0WBrELYx2FQWwA+r1L6FT8LDyqCpkxpcEayN39lCs/vPjePs9NRtrbWvGrO5ZU/VlpfyNWsGmc0hWtQG52jcoDT+S3KmSq0jJSv6B7udY6iO3CtNWs7nkaF61oDZeCe8YEDda1DmK7sCF4WoKNK8W5tKI1XAruGRM0WHsNYgPAkQ+PV+yFuzBtNQnBplrgdunuQitaw6XgnjFBZxwVtgc86/SWCccPjx6rmGZxYdpq3MHGT+BOy92FH1rRGi4F94ypZS/XVQvacfqpkydWVUqzuDBtNe5g4ydwN6qOeyNor9VwpWoqpIRj1YL2wLNWgqZZXJi2GvfyeT9poUbUcW8krWgNj4K7+HJ2W6vnlMhKaZZa3kSSJs5gM3PqTM8eeHFaqBF13JNIU1SrS+fbuzRcXGmWLK+O9ZMWakQd96RxaRA5Sgru4ovfXH2YwdiFufL18JODjnNcIK4pmC4NIkdJK1QzLOwVpEFXv1ZrRz2rY7MkjhRFnKtJ5z80H4bJcYsg9t+8P9KfnQR+V6gq555RUdSMqaXefqV2uDBXvhHCHhfo7+9HR0cHSE56zsywa9cu9L5dvvccdXD3MxYhPtIyJB8k+RbJF8s8T5KbSB4kuZ/kwvCbKWGLYgVpLcG4UjtcmCufNv39/ViyZAm6u7tReldvZuju7saSJUtwcOCg59c3YoFX3FNU08JPzv1HAK6t8Px1AC7If6wD8IP6myVRi6JXXEswLvfzhg6POjFXPgpR5ro7OjrQ1dWF3t7eCQG+ENh7e3vR1dWFj1/+cc+vb0TvWfPh/amaljGzX5KcW+GUlQAettz/gt+QbCM5y8zSt4oiQ2qZ2ljN+mXzJuXcCaDzkzMCt6OQELjnM5ekeq582Epz3YWZIgBCCW4k0dPTAwDo7c0NUPb09EwI7D09Pdjx2g7PnHtx7znKsQDNh68ujNky7QBeL/p8MH9MEsxPr7i/v3/SrXmBmaG/v3/ScZYMdBmAx/cMlZ3hsn7ZPEzO7Oa+rpCr/9UdS/DavcvxqzuWZDqwA42ZKVII8IUefFNT04TATrJq71nTFeMXRnAv97c5+URyHckBkgPDw8Mh/GipVbWpjX5zr4UAXxgY/eDY5MUzlXL5qxa0e/9nQXYGToOkWRpVzKy4B19QCOwFy89fjmdWP4P9N+/HM6ufmdCT1nTF+IUxW2YQwJyiz2cDeMPrRDPbDGAzkJsKGcLPljpUWkFanHsFxv+wS3OvHR0dALwHRotVCtTtEaSI0iJomqVRM0UKr3Ox7u7uSQG+nCRU1My6MHru2wB8IT9r5ioAI8q3p1/prXmhB1+aey38oVfrZVcK1FkeOA3aw+1a2IWWpokVOluaWkKdKVL6Oo+NjXkOslYSd0VN8dFzJ/kIgA4A00kOArgLQAsAmNn9AHYAuB7AQQAfAPhiVI2VxiodXCv04ksDO1B+YBQoH6iLFy+1nd6C005pwsjosUwNnNbSw/VKk4Wl3Bu41yBrpR5818KuqgOuEi2tUJWqzAxNTeM3eWNjY5P+sL1WpwJAW2sLNq64yLNMQbXVrFv3DeHbT76Edz84VvF7pdk1j13jmWaZNXUWnln9TN3nB1UYa/F6Ay8O/H19fejs7Kz4vVTcKxpaoSqh8Mq9rvjcrXj7kptwaOTopF6232mL1Vazbt03hPWPPY9jJ8Y7H4dHj2H9fzwPoPZVtEkTtIcbdS67s7MTfX19nitUCz34lStXVg3sgKYrxk3BXcryukVf8blb8dQjD+DM3w/jrKW3Tipb4DfoVltEdd/OVyYE9oJjY1axnEG9wq63U03QmvGNGFCtFLhJ+grsEj8Fd/FULvf69iU34czfD+P9PdsAAGctvbVq/Rgv1RZRVRqgjWqKZBT1dvwI0sNVLlv8Uslf8bRr1y7PWTGHRo7irKW34szLV+D9Pdvw4f9WLvJVTucnZ0xaIFE88Fppdk1UUySjqLcTNi29F7/UcxdP5XKvhR73WUtvxekXXIUp584/edyvrfuG8PieoQmLlwjgxsvH0zrrl82blHMHgJYmRjZFMi1VKJXLFj/Uc5eyOjs7Jw2qFeakkzwZ2IPOSffqIRuA/pfHVy2vWtCO+1ZfirNOH5/T3dbagvs+e2lkKRJVoRSXqOcugYSx8bXfHnK5AdqoBj29Cp9lZTGVuEfBXQKrd+NrvxUpvYI4gMgGPcN44xJJCi1ikobzu4DJ65wpLU0nFzUVS9vWe3Eu8Enq4qKktitptIhJEstPD7nczJVyxcmSNuhZSRQ12f0Gxqjrwdcqqe1KM/XcJZHOu2N72VLAXtLUcw+7hECQzaqjLl9Qq6S2K4n89tw1W0YSqdwMlbbWltRXkAy7hECQypJJLcWb1HalWSaD+9Z9Q1h8bx/Ou2M7Ft/bV3aXIKlfrb/rcmWAN664qOImI2kQdjncIIExqaV4k9quNMtccC8M1A0dHoVhfLaFAnz46vldr1rQjhsvb0dzfp59M3lykVPat97rWtiFKc1TJhyrp4RAkMDo92dHuQm3l7B/J5LB4J6GJeauqOd3XVjFeiI/JnTCrOJerGlQCJh3PnsnTms+DW2ntYVSQiBIYPRTviCO/U9VViF8mZstk5Yl5i6o53ddrSRw2pQOeo58NIIpzVNwz1/fU3cAC1pZslr5gko5/CiDrcoqhCtzwd3vAhqpXz2/66jfhBtd2jfqgBlmYNTgphsyl5bJ8n6djVbP7zrKOi9xjLukKWBqcDOYRo9P+JW54L5qQXvqZ1ukRT2/6yjfhOMYd0lTwNTgpn9xjE/4lbm0DFB/bRTxr9bfdZR1XuIYd0nTJhtBc/hZFtf4hB+ZDO6SDlG9Cccx7pK2gKnBTX+SnG5TcJfMiau0rwKmexqxp22tMpdzF9G4i4QlyeMT6rlLJmncRcKQ5HSbgruISABe5ZWTWLnSV1qG5LUkXyF5kOQdHs/fQnKY5HP5jy+H31QRkXgleepjqarBnWQzgO8DuA7AhQBuInmhx6mPmtll+Y9/D7mdIiKxC1JeOW5+eu5XADhoZq+a2UcAfgpgZbTNEhFJniRPfSzlJ7i3A3i96PPB/LFSN5LcT/IxknNCaZ2ITJLU5e5ZkKaVxn6COz2Ole6A9iSAuWY2H8DPATzk+Y3IdSQHSA4MDw8Ha6mIpCrn66IkT30s5Se4DwIo7onPBvBG8Qlm9raZfZj/9IcALvf6Rma22cwWmdmiGTNm1NJekUxLU87XRWmqO+9nKuTvAFxA8jwAQwDWAvjH4hNIzjKzwjKtFQAOhNpKEQGQrpyvq9Ky0rhqcDez4yS/DmAngGYAD5rZSyTvBjBgZtsA3E5yBYDjAN4BcEuEbRbJrCQvd5dk8TXP3cx2mNlfmtnHzexf8sc25AM7zOxOM7vIzC41s04zeznKRotkVZpyvhIvrVAVSZEkL3eXZFFwl7o1esu6rEtLzlfipeAudSlsWVcon1vYsg6AArxIjFTyV+oSx5Z1IlKdgrvUJY4t60SkOqVl6qBcczxb1olIdeq516iQax46PArDeK55676huJvWUOuXzUNrS/OEY43Ysk5EKlNwr5FyzTnask4kmZSWqZFyzeO0ZZ1IeV47NzViKqt67jUql1NWrllECuKs4qngXiPlmkWkmjireCotU6NCGiLrs2VEpLw4q3gquNdBuWYRqSTOKp5Ky4iIRCTOKp7quYuIRCTOKp4K7iIOimv6nUwWVxVPBXcRxxSm3xVmaRSm3wFQgM8Q5dxFHKNNtAVQcBdxjjbRFkDBXcQ55abZaRPtbFFwF3GMNtEWQAOqUifVtE8ebaItgIK71EH7pyaXNtEWBfeMiKKHXammvYK7SLwU3DMgqh62atqLJJevAVWS15J8heRBknd4PH8ayUfzz+8mOTfshkrtoto1SjXtRZKranAn2Qzg+wCuA3AhgJtIXlhy2pcAvGtmnwDQA+A7YTdUahdVD1s17UWSy0/P/QoAB83sVTP7CMBPAawsOWclgIfyjx8DsJQkw2um1COqHrb2TxVJLj8593YArxd9PgjgynLnmNlxkiMAPgbgT2E0Uuqzftm8CTl3ILwetmraiySTn+Du1QO3Gs4ByXUA1gHAOeec4+NHSxi0a5RI9vgJ7oMA5hR9PhvAG2XOGSR5CoBpAN4p/UZmthnAZgBYtGjRpOAv0VEPWyRb/OTcfwfgApLnkTwVwFoA20rO2Qbg5vzj1QD6zEzBW0QkJlV77vkc+tcB7ATQDOBBM3uJ5N0ABsxsG4AHAPyY5EHkeuxro2y0iIhU5msRk5ntALCj5NiGosdHAXw23KaJiEitVBVSRMRBCu4iIg5ScBcRcRDjmtRCchjAHwN+2XS4tzBK15QOuqZ0yMI1nWtmM6p9UWzBvRYkB8xsUdztCJOuKR10TemgaxqntIyIiIMU3EVEHJS24L457gZEQNeUDrqmdNA15aUq5y4iIv6krecuIiI+JDK4u7atn4/ruYXkMMnn8h9fjqOdQZB8kORbJF8s8zxJbspf836SCxvdxqB8XFMHyZGi12mD13lJQXIOyX6SB0i+RLLL45xUvU4+ryltr9MUkr8l+Xz+mr7tcU7wmGdmifpArjjZ/wA4H8CpAJ4HcGHJOV8FcH/+8VoAj8bd7jqv5xYA/xp3WwNe198AWAjgxTLPXw/gaeRq/V8FYHfcbQ7hmjoAPBV3OwNczywAC/OPzwTwe4//e6l6nXxeU9peJwI4I/+4BcBuAFeVnBM45iWx5+7atn5+rid1zOyX8KjZX2QlgIct5zcA2kjOakzrauPjmlLFzA6Z2d784/cBHEBu17RiqXqdfF5TquR/93/Of9qS/ygdDA0c85IY3L229St98SZs6wegsK1fEvm5HgC4MX9b/BjJOR7Pp43f606bq/O3z0+TvCjuxviVv41fgFyvsFhqX6cK1wSk7HUi2UzyOQBvAfiZmZV9nfzGvCQG99C29UsIP219EsBcM5sP4OcYf4dOszS9Rn7tRW7p96UAvgdga8zt8YXkGQAeB/ANM3uv9GmPL0n861TlmlL3OpnZCTO7DLmd7q4geXHJKYFfpyQG9yDb+qHStn4JUfV6zOxtM/sw/+kPAVzeoLZFyc/rmCpm9l7h9tlyexy0kJwec7MqItmCXBD8iZk94XFK6l6nateUxtepwMwOA9gF4NqSpwLHvCQGd9e29at6PSU5zhXI5RHTbhuAL+RnY1wFYMTMDsXdqHqQnFnIc5K8Arm/n7fjbVV5+bY+AOCAmX23zGmpep38XFMKX6cZJNvyj1sBfBrAyyWnBY55vnZiaiRzbFs/n9dzO8kVAI4jdz23xNZgn0g+gtyshOkkBwHchdxAEMzsfuR27roewEEAHwD4Yjwt9c/HNa0G8BWSxwGMAlib4E4FACwG8HkAL+TzuQDwTwDOAVL7Ovm5prS9TrMAPESyGbk3oi1m9lS9MU8rVEVEHJTEtIyIiNRJwV1ExEEK7iIiDlJwFxFxkIK7iIiDFNxFRByk4C4i4iAFdxERB/0/WKyAzZt30akAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_kmeans(points, centroids, assignments, k)"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}