Week4_solutions.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",
    "We will represent points in the space as tuples, and use lists of tuples for our dataset, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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",
    "\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)]"
   ]
  },
  {
   "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": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "% matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "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": 3,
   "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": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1.1557723128457436, 1.5503127000227539), (1.0695293336394693, 1.1790517898280206), (0.67203811682232506, 1.1050177863681467), (0.97865652694273497, 1.2632685634138405), (0.60801910810883197, 0.71652631379457865)]\n"
     ]
    }
   ],
   "source": [
    "points_array = 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": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x110a85470>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXsAAAD8CAYAAACW/ATfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGoZJREFUeJzt3X2MnVWdB/Dvl2HUcSGOsZMIQ2vZ\nlUAWEAqTimmyKVVDRRcawGzdRMVoGl2JLzEkxT94yybUkLhZxZWtgYgvQVwgdZASwqY1Klkr0zew\nlG66GpcOjYxAi25HaOtv/7h3nDt3nnufl3ue5znnPN9PMunMvc/MnOe50989z+/8zjk0M4iISNxO\nqbsBIiJSPgV7EZEGULAXEWkABXsRkQZQsBcRaQAFexGRBlCwFxFpAAV7EZEGULAXEWmAU+v6xUuW\nLLHly5fX9etFRIK0c+fO35vZWN7vqy3YL1++HFNTU3X9ehGRIJH8bZHvS03jkHwTyV+S3EtyH8nb\nEo55I8kHSB4kuYPk8iKNERGRcmTJ2b8GYI2ZXQTgYgBrSV7WdcwnAbxiZu8E8C8AvuK2mSIiMojU\nYG8tf2x/Odz+6F4q82oA97U/fxDAe0nSWStFRGQgmapxSA6R3APgRQBPmNmOrkPGATwPAGZ2AsBR\nAG9L+DkbSE6RnJqZmRms5SIiklmmYG9mJ83sYgBnAVhJ8oKuQ5J68YsWyjezzWY2YWYTY2O5B5NF\nRKSgXHX2ZnYEwE8ArO166hCApQBA8lQAbwHwsoP2iYiIA6mllyTHABw3syMkRwC8D4sHYCcBfBzA\nfwG4DsA20xZYIrls2T2NOx8/gBeOzOLM0RHceMW5WLdivO5meUHXZnBZ6uzPAHAfySG07gR+aGY/\nJnk7gCkzmwRwD4DvkjyIVo9+fWktFonQlt3TuOnhZzB7/CQAYPrILG56+BkAaHxQ07VxIzXYm9nT\nAFYkPH5zx+d/AvBht00TaY47Hz/wl2A2Z/b4Sdz5+IHGBzRdGze0No6IB144Mpvr8SbRtXGjtuUS\nJD7KqxZ35ugIphOC15mjIzW0xi+6Nm6oZy9OzOVVp4/MwjCfV92ye7rupgXhxivOxcjw0ILHRoaH\ncOMV59bUIn/o2rihYC9O9MurSrp1K8ZxxzUXYnx0BAQwPjqCO665UHdG0LVxRWkccUJ51cGtWzGu\nANaDrs3g1LMXJ3rlT5VXFfGDgr04obyqiN+UxhEn5m6xVY0j4icFe3FGeVURfymNIyLSAOrZi5RM\nk83EBwr2IiXSIl7iC6VxREqkyWbiCwV7kRJpspn4QsFepESabCa+ULAXKZEmm4kvNEArMoC0ShtN\nNhNfKNiLFJS10kaTzcQHSuOIFKRKGwmJgr1IQaq0kZAo2IsUpEobCYmCvUhBqrSRkGiAVqQgVdpI\nSBTsRQagShsJhdI4IiINkBrsSS4luZ3kfpL7SH4+4ZjVJI+S3NP+uLmc5oqISBFZ0jgnAHzJzHaR\nPB3ATpJPmNmzXcf9zMw+5L6JIiIyqNRgb2aHARxuf/4HkvsBjAPoDvYildGGICL55MrZk1wOYAWA\nHQlPv4fkXpKPkTzfQdtEEs0tUzB9ZBaG+WUKtuyerrtpIt7KHOxJngbgIQBfMLNXu57eBeAdZnYR\ngK8D2NLjZ2wgOUVyamZmpmibpeG0TIFIfpmCPclhtAL9983s4e7nzexVM/tj+/OtAIZJLkk4brOZ\nTZjZxNjY2IBNl6bSMgUi+WWpxiGAewDsN7Ov9jjm7e3jQHJl++e+5LKhInO0TIFIfll69qsAfBTA\nmo7SyitJfprkp9vHXAfgVyT3AvgagPVmZiW1WRpOyxSI5JelGufnAJhyzF0A7nLVKJF+tEyBSH5a\nLkGCpGUKRPLRcgkiIg2gYC8i0gBK40hjaRauNImCvTRS1s3Cs/wcvWFICJTGkUZyMQtXyzZISBTs\npZFczMLVsg0SEgV7aSQXs3C1bIOERMFeorNl9zRWbdqGszc+ilWbtiWmVVzMwtWyDRISBXuJStY8\n+roV47jjmgsxPjoCAhgfHcEd11yYa3BVyzZISFjXEjYTExM2NTVVy++WeK3atA3TCWmU8dERPLlx\nTc/vK1pVo2ocqRrJnWY2kff7VHopUSmSRx+kDFPLNkgoFOwlKmeOjiT27Pvl0XtV1dw6uU+9domG\ncvYSlSJ59F69/iOzx1VDL9FQsJeoJA28XnvpOO58/EDP6pys1TOqoZeQKY0j0enMo2fJx994xbkL\njulHNfQSKvXsJWpZZrkm3Q289c3DiT9PNfQSKvXsJWpZq3O6q2q67wgA1dBL2NSzl6gVneXqYtKV\niE/Us5eoJeXjs/bQQ6qh1+QuSaNgL6VKC0JlB6mqNievM9i6Wptf4qblEqQ0vfLec+mQtOdDUfd5\nFF0iQsJUdLkE5eylNGmVMLGsB1/3eWipZclCwV5KkxaEYglSdZ+HllqWLBTspTRpQSiWINXvPLKs\nrT8oLbUsWaQGe5JLSW4nuZ/kPpKfTziGJL9G8iDJp0leUk5zJSRpQSiWINXrPC4/b6ySPWpVJipZ\nZKnGOQHgS2a2i+TpAHaSfMLMnu045gMAzml/vBvAN9v/SoOlVcJUVSlTtl7n0S+X7/ocQyoTlXrk\nrsYh+SMAd5nZEx2P/TuAn5jZ/e2vDwBYbWaHe/0cVeNI7M7e+CiS/ncRwG82fbDq5kgkKtm8hORy\nACsA7Oh6ahzA8x1fH2o/1jPYi7jk46Sifmvr+9heiVvmAVqSpwF4CMAXzOzV7qcTvmVRp4bkBpJT\nJKdmZmbytVSkh6z7zlat7lx+HaoYkJZiMgV7ksNoBfrvm9nDCYccArC04+uzALzQfZCZbTazCTOb\nGBsbK9JekUXqrnPvpdfA6fbnZrxs76B8fdOVltQ0DkkCuAfAfjP7ao/DJgHcQPIHaA3MHu2Xrxdx\nKU+de9Xpk6SB0y8+sCfx2Kx1+b6mgKockJb8suTsVwH4KIBnSM79lX4ZwDIAMLO7AWwFcCWAgwCO\nAfiE+6aKJMu676wva8gU2Sd3ji/nkKTuyWXSX2oax8x+bmY0s3eZ2cXtj61mdnc70MNaPmtmf2Nm\nF5qZymykMkm5cQA49vqJBSkEX9I9g8wv8OUcksQySS5WmkErwZvLjY+OLNxd6pVjxxfkjPOme8oa\naBxkEpTPvedYJsnFSkscSxTWrWhtKn5k9viCxztzxj6le4pOghokBVS2WCbJxUrBXrxTdAAyrdeb\ndSMTnwcaB9mMpQqayesvBXvxyiC96rReb9aep8+pEvWepSgFe/HKIL3qtF5vljuGLbuncQqJkwnL\niPiQKgHUe5ZiFOzFK4P0qvv1erPcMcwdkxTofUqViBShYB8gXyfVuJBnEDXpGvTq9Wa5Y0g6BgCG\nSC0ZLMFT6WVgYp+SnqV8r8g1yHLH0OuYP5sp0EvwFOwD4/OkGhey1KAXuQZZJvxoUpDETGmcwPhc\nKeJK2gBkkWuQpWTR97JGkUGoZx8Y9T6LXYMsdwza3k9ipp59YNT7LH4NspQsqqxRYqVgHxhNqtE1\nCEHMFWOhyr0HrSvag1YkTt1zGoDWnZdSYm5UsgetiCykHuxiPq8t1GQK9iIF+byRSJ2aUDEWIlXj\niBQU+5yHolQx5icFe5GC1INNpk1M/KQ0jkiCLLl4nzcSqZOqpfykYC/SJWsuXnMeetN8Bf8ojSPS\nJWsuXjNuJSTq2Yt0yZOLVw9WQqFgL9JFufjqaJ5CdZTGEa9s2T2NVZu24eyNj2LVpm21rNOvapJq\nxL43g2/Usxdv+DJJqQnVJD70qDXTtlqpwZ7kvQA+BOBFM7sg4fnVAH4E4Dfthx42s9tdNlKawaf/\n/DHn4n15U9U8hWplSeN8G8DalGN+ZmYXtz8U6KUQ/eevhi8zfzXTtlqpwd7Mfgrg5QraIg2n//zV\n8OVN9fLzxsCuxzQ2Uh5XA7TvIbmX5GMkz3f0M6VhNDBaDR/eVLfsnsZDO6fRucA6AVx7abzps7q5\nCPa7ALzDzC4C8HUAW3odSHIDySmSUzMzMw5+tcREk5Sq4cObalIqyQBsf05xoSwDV+OY2asdn28l\n+W8kl5jZ7xOO3QxgM9DavGTQ3y3xiXlg1Bc+VBv5kkpqkoGDPcm3A/idmRnJlWjdLbw0cMtEpDR1\nv6lq4lr1spRe3g9gNYAlJA8BuAXAMACY2d0ArgPwGZInAMwCWG917XUoIt5JqukvsoicD3MDQqY9\naEU8EWMw67cfLZA9laR9bedpD1qRgPky0cm1fjX9T25ck/ncfJpwFyqtjSPiAV8mOrnmaiBWA7qD\nU7AX8UCswcxVTb8PcwNCp2Av4oFYg5mrmn4f5gaETjl7EQ/4tsWhq8FiVzX9PswNCJ2qcSRRKJUh\nobQzC1/ORZUvfitajaNgL4uE8p89lHaGZtWmbYkTnsZHR/DkxjU1tEg6FQ32ytnLIr0qQ26d3FdT\ni5LFWsFSt1gHi5tOwV4W6fWf+sjs8UVbxtW5jaCCUjl6DQobUNtWkTK44IK9D3uUxq5fBUhnr7nu\nPURjrWCpW1LlyxztExuuoIJ93cGlanW9sfWrAOnsNdedRlE5Xjk6l5pOMvcaq+MVlqCCfd3BpUp1\nvrGtWzGOt755OPG5zl5z3WkUrX9fnnUrxvHkxjWLdpKaM/f32JSOVwyCqrOvO7hUqe61QG75+/NT\n6759WKa27qV6Y9frNR4itVZNYILq2TcpR1vlG1vS7XiWXnOMaRSlJhbq9Rqf7FGyHWPHKxZB9ex9\nm2VYpqp6zWmrLfbrpXXOapw+MvuX3t5cWq3ze32ZMNRPrCtPDqLXzNW517xbjB2vWAQ3qSqEoOFC\nlglDLq6Fiwk0aW1Nep5olfKNe/QaajJRdprQVp/GrGfflBxt2logrnqhLtJFaeMLvTaXHqTdZWjS\nmNCgtFZNeIIL9k3S743N1QCui3RRWpBMC5a+DOz5MOAckqZ0vGIR1ACtzHPVC3UxyJo2cJ4lWPrQ\ne45xwFnyi3WQXsE+UK4qk1zUqqcFyX4zMou2uwyq25eYJ24qjROoy88bw/d+8b+Jj+c16O14Wv62\nu2pnbnB2jk+9Z6Um/FVFcUbd81vKpGAfqO3PzeR6vGxZyjRdVhHJvCZcz6rKYmMepFewD1TaH6XP\nAUC9Z3eaMjegqh53zIP0ytkHql/OPua8oyzUlPWiqupxlzlIX/fAr4J9oPr9UTYlAEjcaYdOVS2V\nUtYgvQ8dMKVxAtVvUPSLD+xJ/J7YAoDEnXboVOVSKWWkGX0Y+E0N9iTvBfAhAC+a2QUJzxPAvwK4\nEsAxANeb2S7XDZXFev1R+hgAfB5DqJrLa9GU9aJCn7Hrwx1Ylp79twHcBeA7PZ7/AIBz2h/vBvDN\n9r9SkzoCQL8A1pRBxCxcX4vQg2AeIQ/s+9ABSw32ZvZTksv7HHI1gO9Ya0W1X5AcJXmGmR121EbJ\nqeoAkBbAfLiF9UUZ16LMIKg7Mjd8uANzkbMfB/B8x9eH2o8tCvYkNwDYAADLli1z8Kullyp7QWkB\nzIdbWF+EdC10R+aOD3dgLoJ90s5liesmm9lmAJuB1hLHDn63eCAtgPlwC+uLkK6F7sjcqjsN5aL0\n8hCApR1fnwXgBQc/VwKRVhZX9wJjddc3d6r7WuQR0l2IpHMR7CcBfIwtlwE4qnx9s6QFsKTa5Wsv\nbeXyyw7APtQ3dwppsbUmbQPaBKk7VZG8H8BqAEsA/A7ALQCGAcDM7m6XXt4FYC1apZefMLPULaiK\n7lQlfsozkLdl9zRufHAvjp+c/9sbHiLuvO4i50FPu08V5+tuVE0fNC5tpyoz+0jK8wbgs3l/scQl\nTz7ytkf2LQj0AHD8pOG2R/Y5/0+rVERxPgwqdtOgcXGaQSuVe+XY8VyPDyKkAVEf1T2o2E2DxsVp\nbRyJWkgDopJOd2rFqWcvlRsdGcaR2cW9+NGRYee/y8dUhKTrlZfXnVpxCvZSuVuvOh83/sdeHP9z\nxwDtKcStV51fyu/zLRUh/fXLy/swEzVUCvZSOfW2pZ9+efm5Cir97eQXdbBveomWz9Tbll7S8vL6\n2ykm2mCvEq0w6A1ZuikvX45oq3G0W5P/fJvdKovVsdREUgXV8CnEsddPeLHkRaii7dmrRMt/ZdRM\n605h3qDXoq674+4xnbeMDOP/Xj/xl3kYuksvJtqevdb18J/rN2TdKcxzcS3y3B27vgNYt2IcT25c\ng99s+iD+6o2nLppxrbv0/KIN9ppM4z/Xb8hK3c1zcS2yvhmX/Saru3Q3og32Ia0u2I9Py/O65voN\nWUFhnotrkfXNuOw3Wd2luxFtzh4Iv0Qr9ooi1/X2quKY5+JaZJ3AVPabrCZSuRF1sA9dExZ9yvuG\n3G/QUUFhnotrkfXNuOw3WU3Cc0PB3mNKSyyUdqejoDDP1bXI8mZcxZts6HfpPlCw95jSEgtludNR\nUJhX1bXQm2wYFOw9prTEQrrT8ZfeZP0XbTVODGKpKHJFVRkixaln7zn1mObpTkekOAV7CUZsueFe\nlUVa8kHKwNZ+4dWbmJiwqampWn63SN26K4uA1l3KtZeO46Gd04seb3L6ThYiudPMJvJ+n3L2IjXo\nVVl0/47nteSDlEJpnAZSmqAa/a5zrwqikz3utFVxJINSsG+Y2Jdg8EXade41h2KITAz4qjiSQSmN\n0zBaGbIaade51yJwH3n30sau1hrzon8+yBTsSa4leYDkQZIbE56/nuQMyT3tj0+5b6q4oIlJ1ciy\nj2rSHIp/XndhI+dWaC+C8qWmcUgOAfgGgPcDOATgKZKTZvZs16EPmNkNJbRRHNISDNXIcp17zaFo\n4tyKJiz6V7csPfuVAA6a2a/N7HUAPwBwdbnNkrJoU5dq6DrnozvO8mUJ9uMAnu/4+lD7sW7Xknya\n5IMklzppnTinJRiqoeucj5bCKF+WahwmPNZdLvAIgPvN7DWSnwZwH4A1i34QuQHABgBYtmxZzqaK\nK01ME9RB1zk710thqLx4sSw9+0MAOnvqZwF4ofMAM3vJzF5rf/ktAJcm/SAz22xmE2Y2MTY2VqS9\nIhIhl3dCGuxNlqVn/xSAc0ieDWAawHoA/9h5AMkzzOxw+8urAOx32koRiZ6rOyEN9iZLDfZmdoLk\nDQAeBzAE4F4z20fydgBTZjYJ4HMkrwJwAsDLAK4vsc0iIj1psDdZphm0ZrYVwNaux27u+PwmADe5\nbZqISH4qL06mGbQiEhWVvSbT2jgiGai6Ixyx7XvgioJ9xRQ0wqPF48KjstfFlMapkErCwqTF4yQG\nCvYVUtAIk6o7JAYK9hVS0AiTpvJLDBTsK6SgESZVd0gMFOwrpKARJi1qJjFQNU6FVBIWLlV3SOgU\n7CumoCEidVCwF4mU5nRIJwV7kQhpIph00wCtSIQ0p0O6KdiLREhzOqSbgr1IhDSnQ7op2ItE6PLz\nkrf97PW4xE/BXiRC25+byfW4xE/BXiRCytlLNwV7kQgpZy/dFOx72LJ7Gqs2bcPZGx/Fqk3btOa8\nBEXrMEk3TapKoAkpEjqtwyTdFOwT9JuQov8sEgqtwySdFOwTaHCrRWuriMRDOfsEGtzSfrkisVGw\nT6DBLa2tIhKbTMGe5FqSB0geJLkx4fk3knyg/fwOkstdN7RK2plIqSyR2KTm7EkOAfgGgPcDOATg\nKZKTZvZsx2GfBPCKmb2T5HoAXwHwD2U0uCpNH9w6c3QE0wmBvUmpLJGYZOnZrwRw0Mx+bWavA/gB\ngKu7jrkawH3tzx8E8F6SdNdMqZpSWSJxyRLsxwE83/H1ofZjiceY2QkARwG8zUUDpR5KZYnEJUvp\nZVIP3QocA5IbAGwAgGXLlmX41VKnpqeyRGKSpWd/CMDSjq/PAvBCr2NIngrgLQBe7v5BZrbZzCbM\nbGJsTEutiohUJUuwfwrAOSTPJvkGAOsBTHYdMwng4+3PrwOwzcwW9exFRKQeqWkcMztB8gYAjwMY\nAnCvme0jeTuAKTObBHAPgO+SPIhWj359mY0WEZF8Mi2XYGZbAWzteuzmjs//BODDbpsmIiKuaAat\niEgDKNiLiDQA6xpHJTkD4LcZD18C4PclNqcuOq+w6LzCEut5nWtmp+f9ptqWODazzLWXJKfMbKLM\n9tRB5xUWnVdYYj6vIt+nNI6ISAMo2IuINEAowX5z3Q0oic4rLDqvsOi8OtQ2QCsiItUJpWcvIiID\n8CbYx7obVobzup7kDMk97Y9P1dHOvEjeS/JFkr/q8TxJfq193k+TvKTqNhaR4bxWkzza8XrdnHSc\nb0guJbmd5H6S+0h+PuGY4F6zjOcV3GtG8k0kf0lyb/u8bks4Jl9MNLPaP9Bac+d/APw1gDcA2Avg\nb7uO+ScAd7c/Xw/ggbrb7ei8rgdwV91tLXBufwfgEgC/6vH8lQAeQ2v568sA7Ki7zY7OazWAH9fd\nzgLndQaAS9qfnw7gvxP+FoN7zTKeV3CvWfs1OK39+TCAHQAu6zomV0z0pWcf625YWc4rSGb2UyQs\nY93hagDfsZZfABgleUY1rSsuw3kFycwOm9mu9ud/ALAfizchCu41y3hewWm/Bn9sfznc/ugeYM0V\nE30J9rHuhpXlvADg2vZt84MklyY8H6Ks5x6i97Rvrx8jeX7djcmrfbu/Aq3eYqegX7M+5wUE+JqR\nHCK5B8CLAJ4ws56vV5aY6Euwd7YblmeytPkRAMvN7F0A/hPz79ShC/H1ymIXgHeY2UUAvg5gS83t\nyYXkaQAeAvAFM3u1++mEbwniNUs5ryBfMzM7aWYXo7Vh1EqSF3Qdkuv18iXYO9sNyzOp52VmL5nZ\na+0vvwXg0oraVrYsr2lwzOzVudtray39PUxySc3NyoTkMFoB8ftm9nDCIUG+ZmnnFfJrBgBmdgTA\nTwCs7XoqV0z0JdjHuhtW6nl15USvQivnGINJAB9rV3hcBuComR2uu1GDIvn2ubwoyZVo/R96qd5W\npWu3+R4A+83sqz0OC+41y3JeIb5mJMdIjrY/HwHwPgDPdR2WKybWthBaJ4t0N6yM5/U5klcBOIHW\neV1fW4NzIHk/WlUOS0geAnALWoNIMLO70drs5koABwEcA/CJelqaT4bzug7AZ0ieADALYH0AnQ4A\nWAXgowCeaeeBAeDLAJYBQb9mWc4rxNfsDAD3kRxC683ph2b240FiombQiog0gC9pHBERKZGCvYhI\nAyjYi4g0gIK9iEgDKNiLiDSAgr2ISAMo2IuINICCvYhIA/w/FpoEcUs2X/oAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot the points\n",
    "# NB if using a numpy array instead of a list, we'd write\n",
    "#   plt.scatter(points[:,0],points[:,1])\n",
    "\n",
    "x_values = [x for (x,y) in points]\n",
    "y_values = [y for (x,y) in points]\n",
    "plt.scatter(x_values, y_values)"
   ]
  },
  {
   "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": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "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 = len(data[0])\n",
    "    # Make the data into a numpy array\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 our centroids as a list of tuples\n",
    "    return [tuple(c) for c in 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": 7,
   "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": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "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",
    "    closest_centroids = []\n",
    "    for point in data:\n",
    "        distances = [euclidean_distance(point, centroid) for centroid in centroids]\n",
    "        min_distance = distances[0]\n",
    "        closest_centroid = 0\n",
    "        for (i,d) in enumerate(distances):\n",
    "            if d < min_distance:\n",
    "                closest_centroid = i\n",
    "                min_distance = d\n",
    "        closest_centroids.append(closest_centroid)\n",
    "    return closest_centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 0, 1, 1]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return [0, 1, 0, 1, 1]\n",
    "example_centroids = [(2,2),(4,4)]\n",
    "assign_points(example_centroids, example_data_2d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 1, 1, 1]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return [1, 0, 1, 1, 1]\n",
    "example_centroids = [(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": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function is provided for you\n",
    "from kmeans_utilities import average_point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_mean_centroids(data, assignments, k):\n",
    "    \"\"\"\n",
    "    Take list of N data points (a list of tuples)  \n",
    "    and a list of N centroid assignments, \n",
    "    and return a list of k centroids.\n",
    "    \"\"\"\n",
    "    # Check that our data and assignments have matching N\n",
    "    assert len(data)==len(assignments)\n",
    "    # Check that our centroid assignments are valid, i.e. numbers up to k-1\n",
    "    assert max(assignments) < k\n",
    "    centroids = []\n",
    "    for cluster in range(k):\n",
    "        cluster_points = [point for (point,assignment) in zip(data,assignments)\n",
    "                             if assignment==cluster]\n",
    "        centroids.append(average_point(cluster_points))\n",
    "    return centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1.6499999999999999, 1.6000000000000001),\n",
       " (3.4333333333333336, 3.4666666666666668)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return centroids [( 1.65,  1.6 ), (3.43333333,  3.46666667)]\n",
    "calculate_mean_centroids(example_data_2d, [0, 1, 0, 1, 1], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(5.0, 3.3999999999999999, 4.0),\n",
       " (2.1500000000000004, 2.5499999999999998, 2.8500000000000001)]"
      ]
     },
     "execution_count": 15,
     "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, [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": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# These function is provided for you (and used already below)\n",
    "from kmeans_utilities import points_equal, plot_kmeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "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",
    "    N = len(data)\n",
    "    d = len(data[0])\n",
    "    centroids = initialise_centroids(data, k)\n",
    "    cluster_assignments = assign_points(centroids, data)\n",
    "    old_centroids = [(0,)*d]*k  # unlikely to be equal to centroids at start\n",
    "    while not points_equal(centroids,old_centroids):\n",
    "        old_centroids = centroids\n",
    "        ### YOUR CODE HERE: Fill in the iterative k-means steps \n",
    "        centroids = calculate_mean_centroids(data, cluster_assignments, k)\n",
    "        cluster_assignments = assign_points(centroids, data)\n",
    "        ###\n",
    "        # Optionally, if you'd like to plot what is happening at each step, \n",
    "        # uncomment the following line\n",
    "        #plot_kmeans(data, centroids, assignments, k)\n",
    "    \n",
    "    return (centroids, cluster_assignments)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([(3.1333333333333333, 2.1999999999999997), (2.1000000000000001, 3.5)],\n",
       " [1, 0, 0, 0, 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": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1.4613457232160569, 2.1215467696475918), (0.90430903044718114, 0.92555648706682869), (2.1469835956759917, 0.98508613319598026)]\n",
      "[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 0, 2, 1, 0, 1, 1, 2, 2, 2, 2, 2, 0, 2, 0, 0, 2, 0, 1, 1, 0, 0, 0, 2, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "k = 3\n",
    "centroids, assignments = kmeans(points, k)\n",
    "print(centroids)\n",
    "print(assignments)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD8CAYAAAB5Pm/hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAHpdJREFUeJzt3X+QXWWd5/H3N01LeoKV1knXJHQS\nAyvFlkIkoQvRVFmdMAsMUcMgMuzWqsy6m2JmHNp2lir0jxjZqjUWW3Q1Yi0bhRVnLDWFTIwkFqid\nFOM4w9gJEMEMbpbdWRLikAESBALkx3f/uPcmt2+fc++59557zznP/byquvr2uae7n9M3+d7nfJ/n\n+T7m7oiISLjmZN0AERHpLAV6EZHAKdCLiAROgV5EJHAK9CIigVOgFxEJnAK9iEjgFOhFRAKnQC8i\nErizsvrFCxYs8GXLlmX160VECmn37t3/4u5DzXxPZoF+2bJlTE9PZ/XrRUQKycz+qdnvaZi6MbO5\nZvYPZvakmT1tZl+KOOdsM/ueme03s8fMbFmzDRERkc5IkqN/E1jj7u8DLgGuNrPLa875NPCyu78b\nmAC+km4zRUSkVQ0DvZe8Wv6yv/xRW/JyHXB/+fEDwBVmZqm1UkREWpZo1o2Z9ZnZE8ALwI/d/bGa\nU4aB5wDc/QRwFPjdiJ+z3symzWz68OHD7bVcREQSSRTo3f2ku18CLAYuM7OLak6J6r3PKnTv7pvd\nfcTdR4aGmho0FhGRFjU1j97djwC7gKtrnjoALAEws7OA+cBLKbRPRETa1HB6pZkNAcfd/YiZDQC/\nz+zB1m3Ap4C/A64HplxbV4k0ZevjB7nj4Wd4/sgxzh0c4NarLuTaFcNZNytz+ru0L8k8+kXA/WbW\nR+kOYIu7P2RmtwPT7r4NuBf4SzPbT6knf2PHWiwSoK2PH+TzD/6SY8dPAnDwyDE+/+AvAXo6qOnv\nko6Ggd7d9wIrIo5vqHr8BvDxdJsm0jvuePiZ08Gs4tjxk9zx8DM9HdD0d0mHat2I5MDzR441dbxX\n6O+SjsxKIEh4lEtt3bmDAxyMCF7nDg5k0Jr80N8lHerRSyoqudSDR47hnMmlbn38YNZNK4Rbr7qQ\ngf6+GccG+vu49aoLM2pRPujvkg4FeklFvVyqNHbtimG+fN3FDA8OYMDw4ABfvu7inr8j0t8lHUrd\nSCqUS23ftSuGFcAi6O/SPvXoJRVxOVPlUkWyp0AvqVAuVSS/lLqRVFRurTXrRiR/FOglNcqliuST\nUjciIoFTj16kw7SQTLKmQC/SQSrKJXmg1I1IB2khmeSBAr1IB2khmeSBAr1IB2khmeSBAr1IB2kh\nmeSBBmNFWpRkNo0WkkkeKNCLtKCZ2TRaSCZZU+pGpAWaTSNFokAv0gLNppEiUaAXaYFm00iRKNCL\ntECzaaRINBgr0gLNppEiUaAXaZFm00hRKHUjIhK4hoHezJaY2U4z22dmT5vZWMQ5o2Z21MyeKH9s\n6ExzRUSkWUlSNyeAv3D3PWb2dmC3mf3Y3X9Vc97fuPuH02+iiIi0o2Ggd/dDwKHy49+a2T5gGKgN\n9CJdo808RJJrKkdvZsuAFcBjEU9/wMyeNLMfmdl7U2ibSKRK+YGDR47hnCk/sPXxg1k3TSSXEgd6\nMzsH+D7wWXd/pebpPcC73P19wFeBrTE/Y72ZTZvZ9OHDh1tts/Q4lR8QaU6iQG9m/ZSC/Lfd/cHa\n5939FXd/tfx4B9BvZgsiztvs7iPuPjI0NNRm06VXqfyASHOSzLox4F5gn7vfGXPOwvJ5mNll5Z/7\nYpoNFalQ+QGR5iTp0a8CPgGsqZo+eY2Z3WxmN5fPuR54ysyeBO4CbnR371Cbpcep/IBIc5LMuvkZ\nYA3OuRu4O61GidSj8gMizVEJBCkklR8QSU4lEEREAqdALyISOKVupGdpda30CgV66UnNbO7d6Ofo\nzULyTqkb6UlprK5VKQYpCgV66UlprK5VKQYpCgV66UlprK5VKQYpCgV6Cc7Wxw+yatMU5922nVWb\npiJTKWmsrlUpBikKBXoJStK8+bUrhvnydRczPDiAAcODA3z5uoubGkhVKQYpCsuqJM3IyIhPT09n\n8rslXKs2TXEwInUyPDjA3962Jvb7Wp09o1k30m1mttvdR5r5Hk2vlKC0kjdvZ6qlSjFIESh1I0Fp\nJW8eN3vmL7Y8WTfPL1IUCvQSlFby5nG9/ZPumh8vQVCgl6BEDbJ+7NJh7nj4mdjeeZJZMpofL0Wm\nHL0EpzpvniT/futVF3LLnX+FnfteyhulzeDuvPn/fsnzLO/SFYikSz16CVqS1avzj/ya5/7qNo7/\n7H+CO31Vwd7defmnX+efv/sF5r34j11rt0iaFOglaElm4YyOjjI2Nsahnz/ItW/+hP/28eUM9Ped\nDvK/3b2Nd1y2jv/yJ3/UrWaLpEqpGwnauYMDkfPqq/PyZsbExAQAk5OTAPzXT/5n/uzPx/jt7m0s\n+uB1fO2rk/zhysXdabRIyhToJWi3XnXhjBw9RM/CqQ32lYA/NjbGxMREZO4+L7RoSxrRyljpqEZB\nqBtBqpnf4e7MmXMmo3nq1KlEQT6rYFs72AylN7JmyzlIcWhlrORKoxkvaW3+0UjS1avuzvj4+Ixj\n4+PjDXv03bqOKPUGmxXopUKDsdIxjWa85KmeeyXIT05OMjY2xqlTpxgbG2NycpLx8XHq3flmeR0q\nlSxJqEcvHdMoCOUlSNUG+UoPvnaANq5nn+V1JBlsFlGPXjqmUd2ZvNRz37Vr16wgD2cGaCs9+127\ndkV+f73rSFIbvx0qlSxJNAz0ZrbEzHaa2T4ze9rMxiLOMTO7y8z2m9leM1vZmeZKkTQKQnkJUqtX\nr2Zqaiqyx14J9lNTU6xevTry++OuY/W/Hur4nrJp1NWX8DWcdWNmi4BF7r7HzN4O7AaudfdfVZ1z\nDfDnwDXA+4FJd39/vZ+rWTe9IQ+zbroh6jruePiZlmrji9TTyqybpqdXmtkPgLvd/cdVx/4HsMvd\nv1P++hlg1N0Pxf0cBXoJ3Xm3bSfqf5cB/2fT2m43RwLR8emVZrYMWAE8VvPUMPBc1dcHysdiA71I\nmvJ4ZxA3UDr4O/2s2jSVq7ZK2BIPxprZOcD3gc+6+yu1T0d8y6zOjJmtN7NpM5s+fPhwcy0ViZF0\nn9hui8rd9/cZr75xIndtTUOnB56ldYkCvZn1Uwry33b3ByNOOQAsqfp6MfB87UnuvtndR9x9ZGho\nqJX2iszSzDz2bgajqIHSeW87i+OnZvaBQqh1n9c3WylpmLqx0jSEe4F97n5nzGnbgM+Y2XcpDcYe\nrZefF0lT0nnsWaxgrV2Ve95t2xO1NU4eU1SgFbp5l6RHvwr4BLDGzJ4of1xjZjeb2c3lc3YAzwL7\nga8Df9qZ5orMlnQ+fh5W4razdiDPvea8LH6TaA0Dvbv/zN3N3Ze7+yXljx3ufo+731M+x939z9z9\nX7n7xe6u6TTSNVG5cIDX3zoxIwjmIRi1s3YgD29UcfKy+E2iaWWsFF4lFz440D/j+MuvH5/R400a\njDqZx29ngVMe3qji5GXxm0RTrRsJwrUrShuAHzl2fMbx6jxxktr03cjjJ62mWSvPdW0q15PH8QNR\noJccanXAsVGPN0kwyvOgYtJNVLLS6huYdJ4CveRKOz3qJD3eRsEoz+kR9ZqlVQr0kivt9Kjr9XiT\n3iXMH+iflf6BfKRHQL1maY0CveRKOz3quB4vkOguYevjB3ntrROzfm7/HMtNekSkFQr0BZXXhTPt\nSjrgGHf9UT3eVZumEt0l3PHwMxw/ObsM2Tlzzwribyu9S9MrCyjPC2falWSaXrPXn/QuIe68I6/P\nTuWIFIkCfQHleeFMu5LMM2/2+pPOn9eiHwmVUjcFlOeZIWlIe2ZM0mmJeZ++KNIq9egLqNd7ns1e\nf9LVqNqWT0KlHn0B9XrPs5XrTzotUdMXJUQK9AXU6wtnev368277s9uZ3DPJb177DQvnLWRs5Rhr\nz9fWiVlqes/YtGjPWJHwbH92Oxt/vpE3Tr5x+tjcvrls/OBGBfuUtLJnrHL0Ii3S1nmzTe6ZnBHk\nAd44+QaTeyYzapGAUjciLclit6oi+M1rv2nquHSHevQiLQh5LUM7Fs5b2NRx6Q4FepEIjdIyoa9l\naNXYyjHm9s2dcWxu31zGVo5l1CIBpW5EZkmSlsnzJiBZqgy4atZNvijQi9RIUiq519cy1LP2/LUK\n7DmjQC9SI0laRnP5pUgU6EVqJE3LaBWtFIUGYyVX8jA3PUmpZGnf9me3c+UDV7L8/uVc+cCVbH92\ne9ZNCpZ69JIbeZmbrrRM59WuoD302iE2/nwjgPL7HaASCJIbqzZNRaZMhgcH+Nvb1mTQojDloRbN\nlQ9cyaHXDs06vmjeIh65/pGutqVoOlICwczuM7MXzOypmOdHzeyomT1R/tjQTANEKjQ3vfMqPelD\nrx3C8dM96W6nTbSCtruS5Oi/CVzd4Jy/cfdLyh+3t98s6UW9Xme/G/JSi0YraLurYaB390eBl7rQ\nFulxGgTtvLz0pD+0+EOzjmkFbeekNevmA2b2pJn9yMzem9LPlB6jHZ46Lw896e3PbucH+38w6/i6\nd6/TQGyHpDHrZg/wLnd/1cyuAbYCF0SdaGbrgfUAS5cuTeFXS2g0N72zxlaORdaL72ZPOip9BPDo\ngUe71oZe03aP3t1fcfdXy493AP1mtiDm3M3uPuLuI0NDQ+3+ahFp0trz17LxgxtZNG8RhrFo3qKu\nbwqSl/RRL2m7R29mC4F/dnc3s8sovXm82HbLRKQjsq5Fs3DewsiplRqI7Zwk0yu/A/wdcKGZHTCz\nT5vZzWZ2c/mU64GnzOxJ4C7gRs9qcr6I5ErU6tdWShlrFW17tGBKJAfysIgpbfX2j4XkpYy1D+1M\nrSyYUqAXyViogSyt1a9aRTuTNgcXKaC8LGJKW1qDrhq8bZ8CvUjGQg1kac3Zz8Pc/6JToBfJWKiB\nLK39Y7UPbfsU6EUylsdAlsYsl7Tm7Odh7n/RaTBWou3dAj+9HY4egPmL4YoNsPyGrFs1W1Ha2UCe\nZt2EOjgcCs26kXTs3QI/vAWOV5cHNhj5D/DhOzNr1ixR7ewfgI/cVchgnxea5ZJvmnUj6fjp7TVB\nHsBh+r5ScM2LqHYeP1Y6Li0LdXC4lynQy2xHD8Q84dFBdO8WmLgINg6WPnfrzSCunbHtlyTiBoHN\nTCtSC6qYgT6rwNIr5i+Of642iFbSJ0efA7z0+Ye3dOc1iWtnvfZLQ1GDwwCn/FQmu1FJ+4oX6LMM\nLFnI4k3tig2ART9XG0SzTJ9csaGUk6/WP1Buv7SqMstljs0OD5WFXKo9UyzFC/S9lJfN6k1t+Q2l\ngdfaYB8VRLNMnyy/oTTwOn8JYKXPGohNxdrz1xI3UaOyz2zW+85KcsUL9L2Ul83yTe3Dd8J1mxsH\n0azTJ8tvgPGnYOOR0ud2g7zSgqfF5ern2JwgSzaErHiBPuvA0k3delOLC25JgmhI6ZNeSws2ELeQ\n65Sfijxfs3Lyq3iBPqTA0kijN7U0ep/tBrdK+mTgnWeOnTUw+7zqtn7lvNJH3nrNvZQWTCBuReqi\neYsizy96yYaQpbFnbHdVepUBrIZs6IoN0QuCrtgwe7FQJUBDc3+LesGtmZ9zoupnHHtpZltq23rs\npTPnttruTuiltGBCcbtRZb3vrDSneIEeSgEh66DQDfXe1CYuSidApxHcGr1ZRC7Aijk3S/MXl+9s\nIo7LaZXAn5eSDdJYMQN9L4l7U0ur95lGcGvUliRtykOvud4dlMyQ9b6z0pzi5eilJK1B6TTGPBq1\nJUmb8tBr1nTNnhfq+gAF+qKKCtAYXHBlcz8njeDW6M0isq0x52Yt7emaUhiVqp0hrg9Q9coie+hz\npUJjVL2GWVVvbFQuuPr5gXeUjh17OezBdElNN8o4F6VqZyvVK5WjL7L/9QgzgjxkN7DZaIC8VwbQ\nuyxPdew7pbY+fqWnDaR6rSFX7VTqpsjqDYJqhWfwQk41VOvW5umhbukICvTFFjeAOfAOrfDsAd0K\ngFnrVk+7U1s65mGAV4G+yOIGQUErPHtAyKmGat3qaXdib9q83HU1DPRmdp+ZvWBmT8U8b2Z2l5nt\nN7O9ZrYy/WZKpLgZM8dejj4/D3PVJTVZpBp27twZW9XS3dm5c2fqv7Obm6evPX8tj1z/CHs/tZdH\nrn+k7TGAvNx1JenRfxO4us7zfwBcUP5YD/z39psliUVNB8yi8FujMQGNGZyW1q18NwMglIL8mjVr\nGB8fnxXs3Z3x8XHWrFmTerDvRE+7W/Jy19Vw1o27P2pmy+qcsg74lpde+b83s0EzW+Tus+cpSXd0\ne4Vno7o7adXlCUCaM0i6XYpgdHSUsbExJidLvdGJiQnM7HSQn5ycZGxsjNHR0dR/d1FX4i6ctzBy\nyma3B3jTmF45DFSvoT9QPqZAn5VuF35rpdZNXurbdFm9W/lWAlknA2DU1M2JiQmAGcG+OshXgr+U\njK0cy0UBuDQCfdSrGpnEM7P1lNI7LF26NIVfLbFSmLe+c+dORkdHI//juju7du1i9erVrde66cEx\ng7zcyjdS786jOthXAr6CfLS8FIBLY9bNAWBJ1deLgeejTnT3ze4+4u4jQ0NDKfxq6ZSm8rGt1rrJ\nQ32bLivKXO16dx5mdjrYVyjIx0t7gLcVaQT6bcAny7NvLgeOKj9ffNX52OpgH5mPbaXWTTfr2+Ro\nILjbA6itqnfnUfk3UC2qQyD50TB1Y2bfAUaBBWZ2APgi0A/g7vcAO4BrgP3A68Afd6qx0j3VvbaG\n+dhGYwJRz7/zfPjrm+HB/wTWB5feVNqnNm05GwjOy618I3GDiL/3O783699A5WvofM++F0o+dIKK\nmkld1T34irbzsQ99DqbvnX185NPpB/uJi2Lq7S8pTUeVSLU5eoCz55zN8NQw2765bca/gdq7vE4F\n+6g2ze2bW5iplmlppaiZAr005O7MmXMmy3fq1Kn2/iN/6Z3gJ2cftz744kuzj7dj4yDRcwOstPZA\nYtX2nle/uZov/PsvRAbz6mA/NTVVGqRPWVGqS3aaqldK6uLysW312qKCfL3j7dD2gC2Lmrp5+bmX\nR87EqqT61q1b15EgD8WZsZRHqnUjsWpvyU+dOhU5QNs062vueDuyHggOzOrVq2Pf4M0slSAft3K4\nKDOW8kg9eokUl3eNGqBtumd/6U3ROfpLb2qv0VG6vXhM2lJv/n5eFh8VkXL0Eqkyj75j+diHPge7\nv1lK13Ry1o0USqM8vGbdaDBWUpZ4ZaxISpbfvxyPGDw3jL2f2ptBi/KnlUAffo4+R4tliqYb+ViR\nasrDd0bYgb6yWEY7LeWX3oilSlFWDhdN2IG+XtVEyV4n3oj1xpGaLLbAi6o9v+7d65jcM5npVnxF\nF/asG1VNzLe0yxfnrNxBltodtEyzbn6zqufvZ9mOkITdo1fVxHxL+41Yd3BAOvuUNrMFXid7/nnZ\niq/owg70oSyWCTUdkfYbse7ggHSCY9JVqJ3e/FqrYdMRdqCP2zy7SLfxIQ8op/1GrDs4IJ3gmHT2\nS6d73JqFk46wAz1Eb55dJCGnI9J+Iw7lDq5NaQTHpLNfOt3j1iycdIQ9GBuC0NMRzW55uHdLc3Xv\ne7DcQRqlApLWze/05tdFqd+fd1oZm3eqp35G7awaKPXYi5aO64JulQpQjfjuUwmEECm4naE3vVxS\n/ZnuUj36ECkdcUboaayCiqpbL/miQF8EzeaxQ6VNRERaEv6sGwlHYLNqsigxIL1JPXopjoDSWPWW\n9oNmmUi6NBgrkoG4DTbmv20+b558U7NYJJbq0UsyoZZUyJFGaZm4BUVH3zqq2i6SOqVueo0qPHZc\nkoqLcQuN4qi2i7RDPfpeE3JJhZxIUv8lbmn/4NmDkT9TtV2kHerR9xrNRe+4JPVf4pb2A22XLygi\nLbrqrESB3syuBiaBPuAb7r6p5vmbgDuAg+VDd7v7N1Jsp6RFc9E7Lmn9l3oLjXop6Glzkc5rGOjN\nrA/4GvBvgAPAL8xsm7v/qubU77n7ZzrQRknTFRuiSyoUdC56HrVbVKzXVprWS3X10t+hk5L06C8D\n9rv7swBm9l1gHVAb6KUIApqLnlequNgcbS7SeUkC/TBQfa9/AHh/xHkfM7MPAb8Gxt19Vn7AzNYD\n6wGWLl3afGslHSqp0HG91itvR6dLHUuyWTcWcax2ldUPgWXuvhz4CXB/1A9y983uPuLuI0NDQ821\nVESClPbmIiotMVuSHv0BYEnV14uB56tPcPcXq778OvCV9psmIr0gzVSXBnajJQn0vwAuMLPzKM2q\nuRH4d9UnmNkid6/ce30U2JdqK0UkaGmlujSwG61hoHf3E2b2GeBhStMr73P3p83sdmDa3bcBt5jZ\nR4ETwEvATR1ss4hIJA3sRks0j97ddwA7ao5tqHr8eeDz6TZNRKQ5GtiNphIIIhKMtAd2Q6ESCCJJ\n7N2itQcFoDUM0RTos6CgUSyq+FkoWsMwm1I33VYJGkefA/xM0FBN+PxSxU8pOAX6blPQKB5V/JSC\nU6DvNgWN4omr7KmKn1IQCvTdpqBRPFdsKFX4rKaKn1IgCvTdpqBRPMtvgI/cBfOXAFb6/JG7NBAr\nhaFZN92mMsHFpIqfUmAK9FlQ0BCRLlLqRiRAKtUr1dSjFwmMSvVKLfXoRQJTr1Sv9CYFepHAqFSv\n1FKgFwnM/LPnN3VcwqdALxIY99otnesfl/Ap0IsE5pW3XmnquIRPgV4kMHG7KfX6Lku9TIG+nr1b\nYOIi2DhY+qxSwlIA2mVJamkefRxtNiEFpV2WpJZlNUAzMjLi09PTmfzuRCYuKm8OUmP+Ehh/qvvt\nEREBzGy3u4808z1K3cRR3XilrkQCoUAfp9frxmvLQ5FgKNDH6fW68dryUCQYCvRxen2zCaWuRIKR\naNaNmV0NTAJ9wDfcfVPN82cD3wIuBV4E/sjd/2+6Tc1AL9eNn784ZjC6R1JXIgFp2KM3sz7ga8Af\nAO8B/q2ZvafmtE8DL7v7u4EJ4CtpN1S6rNdTVyIBSZK6uQzY7+7PuvtbwHeBdTXnrAPuLz9+ALjC\nzCy9ZkrX9XrqSiQgSVI3w0D1PfwB4P1x57j7CTM7Cvwu8C/VJ5nZemA9wNKlS1tssnRNL6euRAKS\npEcf1TOvXWWV5BzcfbO7j7j7yNDQUJL2iYhIm5IE+gPAkqqvFwPPx51jZmcB84GX0migiIi0J0mg\n/wVwgZmdZ2ZvA24EttWcsw34VPnx9cCUq/i1iEguNMzRl3PunwEepjS98j53f9rMbgem3X0bcC/w\nl2a2n1JP/sZONlpERJJLNI/e3XcAO2qObah6/Abw8XSbJiIiadDKWBGRwCnQi4gELrN69GZ2GPin\nJr5lATXz8gMQ4jVBmNcV4jWBrqtIKtf0Lndvan56ZoG+WWY23Wyx/bwL8ZogzOsK8ZpA11Uk7VyT\nUjciIoFToBcRCVyRAv3mrBvQASFeE4R5XSFeE+i6iqTlaypMjl5ERFpTpB69iIi0IFeB3syuNrNn\nzGy/md0W8fzZZva98vOPmdmy7reyeQmu6yYzO2xmT5Q//mMW7WyGmd1nZi+Y2VMxz5uZ3VW+5r1m\ntrLbbWxFgusaNbOjVa9V7ndiMbMlZrbTzPaZ2dNmNhZxTqFer4TXVMTXaq6Z/YOZPVm+ri9FnNN8\nHHT3XHxQqqPzv4HzgbcBTwLvqTnnT4F7yo9vBL6XdbtTuq6bgLuzbmuT1/UhYCXwVMzz1wA/olTC\n+nLgsazbnNJ1jQIPZd3OJq9pEbCy/PjtwK8j/g0W6vVKeE1FfK0MOKf8uB94DLi85pym42CeevSh\n7mSV5LoKx90fpX4p6nXAt7zk74FBM1vUnda1LsF1FY67H3L3PeXHvwX2UdosqFqhXq+E11Q45b//\nq+Uv+8sftQOpTcfBPAX6qJ2sal+4GTtZAZWdrPIsyXUBfKx8y/yAmS2JeL5okl53EX2gfGv9IzN7\nb9aNaUb5Nn8FpZ5itcK+XnWuCQr4WplZn5k9AbwA/NjdY1+rpHEwT4E+tZ2sciZJm38ILHP35cBP\nOPNuXWRFfK2S2ENpCfr7gK8CWzNuT2Jmdg7wfeCz7v5K7dMR35L716vBNRXytXL3k+5+CaVNni4z\ns4tqTmn6tcpToA91J6uG1+XuL7r7m+Uvvw5c2qW2dVKS17Nw3P2Vyq21l8p395vZgoyb1ZCZ9VMK\niN929wcjTinc69Xomor6WlW4+xFgF3B1zVNNx8E8BfpQd7JqeF01udCPUso3Ft024JPl2RyXA0fd\n/VDWjWqXmS2s5EPN7DJK/4dezLZV9ZXbey+wz93vjDmtUK9Xkmsq6Gs1ZGaD5ccDwO8D/1hzWtNx\nMNHGI93gge5klfC6bjGzjwInKF3XTZk1OCEz+w6lWQ0LzOwA8EVKA0e4+z2UNqq5BtgPvA78cTYt\nbU6C67oe+BMzOwEcA24sQGdjFfAJ4Jfl3C/AF4ClUNjXK8k1FfG1WgTcb2Z9lN6Ytrj7Q+3GQa2M\nFREJXJ5SNyIi0gEK9CIigVOgFxEJnAK9iEjgFOhFRAKnQC8iEjgFehGRwCnQi4gE7v8DHeOOacFK\n3IAAAAAASUVORK5CYII=\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
}