mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-21 09:54:43 +00:00
447 lines
419 KiB
Text
447 lines
419 KiB
Text
|
|
{
|
||
|
|
"metadata": {
|
||
|
|
"name": "40-kmeans-2d"
|
||
|
|
},
|
||
|
|
"nbformat": 3,
|
||
|
|
"nbformat_minor": 0,
|
||
|
|
"worksheets": [
|
||
|
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Title: The k-means Algorithm\n",
|
||
|
|
"Author: Thomas Breuel\n",
|
||
|
|
"Institution: UniKL"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"from pylab import *\n",
|
||
|
|
"import random as pyrandom\n",
|
||
|
|
"from scipy.spatial.distance import cdist"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 2
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Mixture Densities"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Consider a collection of points that are sampled from three different densities,\n",
|
||
|
|
"in this case normal densities with the same covariances but different means.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"data = r_[10*randn(1000,2)+array([70,30]),\n",
|
||
|
|
" 10*randn(1000,2)+array([10,10]),\n",
|
||
|
|
" 10*randn(1000,2)+array([50,80])]\n",
|
||
|
|
"data = data[pyrandom.sample(xrange(len(data)),len(data))]"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 3
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Here is a scatterplot of this data.\n",
|
||
|
|
"\n",
|
||
|
|
"We clearly see three _clusters_, corresponding to the three _mixture components_.\n",
|
||
|
|
"How can we recover these clusters?\n",
|
||
|
|
"\n",
|
||
|
|
"This is the job of _clustering algorithms_.\n",
|
||
|
|
"One of the most useful clustering algorithms is the _k-means_ algorithm"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"plot(data[:,0],data[:,1],'b+')"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 4,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x3b0fc90>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnW2MZFd1rtcQAx3MZcoOcbdgSJdkQBNjbncS7EwiUJcU\nmbFQhFoosTH5mAah6Aqhm06i2Bb5MTWJwIOIog5BCCkiVCuOAig/GieyZpB1Va1YSQui3O4IHF/A\nohoGmIlGpgdsMrIA3x+b13vVqr3P96k6VfU+Uquqz8fe+5w65+z3rLX22seef/7554UQQgghhNTG\niybdAEIIIYSQWYeCixBCCCGkZii4CCGEEEJqhoKLEEIIIaRmKLgIIYQQQmqGgosQQgghpGYyCa73\nvOc9sri4KG984xtfWPbHf/zH8vM///OysrIi73jHO+TatWsvrHvooYfkda97nZw8eVI+//nPV99q\nQgghhJApIpPgeve73y0XLlwYWvbWt75VvvzlL8vBwYG8/vWvl4ceekhERJ544gn5zGc+I0888YRc\nuHBB3ve+98mPf/zj6ltOCCGEEDIlZBJcb3nLW+Smm24aWnbXXXfJi17kdv/lX/5luXTpkoiIfO5z\nn5P77rtPXvziF0u73ZbXvva18oUvfKHiZhNCCCGETA+VxHD9zd/8jbztbW8TEZFvf/vbcuLEiRfW\nnThxQr71rW9VUQ0hhBBCyFRyQ9kCPvjBD8pLXvISede73hXd5tixY5mWEUIIIYQ0lTKzIZaycPV6\nPXn00Ufl7/7u715Y9upXv1q++c1vvvD/pUuX5NWvfnVw/+eff55/Bf/Onj078TZM8x/PH88fz910\n/vH88fxN6q8shQXXhQsX5CMf+Yh87nOfk4WFhReWv/3tb5dPf/rT8txzz8nXv/51+epXvyp33nln\n6YYSQgghhEwrmVyK9913n+zu7srVq1flNa95jZw7d04eeughee655+Suu+4SEZFf+ZVfkY9//ONy\n2223yT333CO33Xab3HDDDfLxj3+c7kNCCCGEzDXHnq/CTlak4mPHKjHRzSv9fl86nc6kmzG18PyV\ng+evODx35eD5KwfPX3HK6hYKLkIIIYSQFMrqFk7tQwghhBBSMxRchBBCCCE1Q8FFCCGEEFIzFFyE\nEEIIITVDwUUIIYQQUjMUXIQQQgghNUPBRQghhBBSMxRchBBCCCE1Q8FFCCGEEFIzFFyEEEIIITVD\nwUUIIYQQUjMUXIQQQgghNUPBRQghhBBSMxRchBBCCCE1Q8FFCCGEEFIzFFyEEEIIITVDwUUIIYQQ\nUjMUXIQQQgghNUPBRQghhBBSMxRchBBCMtPvT7oFhEwnFFyEEEIyQ8FFSDEouAghhBBCauaGSTeA\nEELIeOj3RTqdYvvBsnXunF/e6RQrj5B5hIKLEELmhKKCywqrbreS5hAyV9ClSAghhBBSM7RwEUJq\npahVhVRD1e5A/paEFIOCixBSKxRck6VqdyB/S0KKQZciIYQQQkjN0MJFCKkcjmprJjz3hEyOY88/\n//zzE6n42DGZUNWEkDHS7XJUGyFk+imrW+hSJIQQQgipGQouQkit0I1FCCF0KRJCCCGEpEKXIiGE\nEEJIw6HgIoSQFDDikhBCikLBRQghKVBwEULKQsFFCCGEEFIzTHxKCCEBmLyVEFIlFFyEEBKg6jkI\nCSHzDV2KhJBasHFPjIMihMwzFFyEkFqYJcFFFyIhpCwUXIQQkgIFFyGkLIzhIoRUhg00HwzcX7st\nsr3tt2PgOSFk3qDgIoRURlKgebtdXeB5vz/dgm3a208IyQ9dioSQ2qgrbmua48FEpr/9hJD8UHAR\nQmqh0xkWFrToEELmGboUCSG1ULXgmvZEpNPefkJIOSi4CCGVUpewmPZEpNPefkJIOSi4CJlD6gza\nprAghJBRGMNFyBwy7UHb43DB1XmO6EIkZP6g4CKE1EadVrS6oeAihFQJXYqEzAmTCNoet7BgfitC\nSFOh4CJkTpiH2KqygosjCQkhdUHBRQghP2EeRCkhZDJQcBEyh0zCWlOXu68Oq1Se+K2046KbkxAi\nQsFFyFwyS4KrDqtUnrZScBFCssBRioQQEoAiiRBSJbRwEUJqY9xB6OMKmE/blsH3hBDLseeff/75\niVR87JhMqGpCyATodpsXhB5z9+Vpa9q2TTxuQkh+yuoWuhQJIXPLtGfcJ4RMD5kE13ve8x5ZXFyU\nN77xjS8se/rpp+Wuu+6S17/+9fLWt75Vjo6OXlj30EMPyete9zo5efKkfP7zn6++1YSQqaMKV9o4\nBFLeIPe0belCJISIZBRc7373u+XChQtDy86fPy933XWXfOUrX5Ff+7Vfk/Pnz4uIyBNPPCGf+cxn\n5IknnpALFy7I+973Pvnxj39cfcsJIVNFUwRXv+/dfOfO+e8om4KLEFIHmYLm3/KWt8hgMBha9sgj\nj8ju7q6IiJw5c0Y6nY6cP39ePve5z8l9990nL37xi6XdbstrX/ta+cIXviCnTp2qvPGEkHw0LUXB\nJNrD5KaEkElQeJTilStXZHFxUUREFhcX5cqVKyIi8u1vf3tIXJ04cUK+9a1vlWwmIaQKqhQ4VZSV\npYxxjPhr0qjCpoliQkg1VJIW4tixY3Ls2LHE9SG66tWy0+lIh08ZQqaGKpODJlGnRQrl5qmjbkE0\nLsFFYUdIMv1+X/oVBo4WFlyLi4ty+fJlWVpaku985ztyyy23iIjIq1/9avnmN7/5wnaXLl2SV7/6\n1cEyurTlE1I747LexDpw1I91k7ImhdpXpL4mC5VxiWBC5gFrCDqnH1gFKCy43v72t8v29rY88MAD\nsr29Levr6y8sf9e73iV/+Id/KN/61rfkq1/9qtx5552lGkkIKU6VFqIksZQkuKpqT5kpdLKun9S0\nR1WIUIooQppLJsF13333ye7urly9elVe85rXyJ/+6Z/Kgw8+KPfcc4988pOflHa7LZ/97GdFROS2\n226Te+65R2677Ta54YYb5OMf/3iiu5EQMj0kiSUrrCAi+n2Rn4yvCZaRt/4Q1opWBLQ/yUonUr1V\nLiT06jL+NylWjZB5I5Pg+vu///vg8sceeyy4/AMf+IB84AMfKN4qQkgtVN2pxjrwVksEqfl2d0XW\n1nz9ug1VBr3naV9MYMREW52CqAqhmPUYOUKTkMnBuRQJmSOqFFzovLN24HV07mlWtLT2WbGytua2\nmaTFJ2+9FFGETAcUXIRMkGmOucna7sFAZGMjvM4ef96gb4ilJCtaEjqQf23NlYN4NL0+tE8ZmuDa\nm9brjpBphYKLkAkyzYLLYo9DH1sdI+dC4iTJuhMrF+V0uyLtdrqFqIrfqy6rVJUZ8gkh1ULBRQip\nhJjgardHl8esO1XWn7Q+liJi2t1xFFGENBcKLkLGTBZ3UhMsX2XagGPEfIUglGgULrx+v7h7rYr0\nCSFxWDdN+J0JIeOBgouQMZPFnYSOeJIdcq+Xv24bV9XpiCwvDx8zjjckvvT6PFQ1ym9724uuccRT\nQZTOChSQhMSh4CJkgpg54UcIdWDj6tTS2hYiJJ6S2jvOzjnJsqhFzywJoHFDwUVIHAouQhpCSBCE\nEnqWdfWlZVvXFiptjcqTxV27FHd33SjF/X237uDAb6OtSfqzDqoKVB9n3ixCyOxAwUXIBNExQ+hw\nrejRoquqrOZV72+Xw2pk3Yj6e0jw5I3DyrtPGlnKKnsO8wq/pluNKCAJyQYFFyFjJq2D0mkKRLxb\nrmxgeRZsIHsoUWhafeOak7DXc4K1SD2tVnh5kwYtgCa1JUTdiVebfvyEZIWCi5Axk6WDCo2gK9qp\nFZ3eJm3EXqzcwWDU2lUkJ5dtj2UwKD6qENMOZa2zLitOHdbGWWNejpPMPhRchDSQKmOaioo1ZIdP\nCzbHupir0LoXywiuft9ZtgYD526Fy7Xddu3Nan3LuhzUZcWJjUSdltQhlqa1h5AmQcFFyARJ66BC\n6+vo1GIdPOpLEhv9vp++p92u
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 4
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Mixture densities arise in both unsupervised learning and in supervised learning.\n",
|
||
|
|
"In both cases, they commonly represent a problem structure in which data is\n",
|
||
|
|
"generated from a number of ideal prototypes (the cluster centers) but then\n",
|
||
|
|
"corrupted by noise.\n",
|
||
|
|
"\n",
|
||
|
|
"- When each cluster has a distinct class label, we have a regular classification\n",
|
||
|
|
"problem with normal densities.\n",
|
||
|
|
"\n",
|
||
|
|
"- When no cluster has any labels, we can hope to recover the underlying\n",
|
||
|
|
"clusters with a clustering algorithm and then assign labels to these clusters.\n",
|
||
|
|
"This is a form of _semi-supervised learning_.\n",
|
||
|
|
"\n",
|
||
|
|
"- When there is training data with labels available, often each class is\n",
|
||
|
|
"a mixture of multiple clusters. That is, each class is generated by multiple\n",
|
||
|
|
"prototypes (think characters in different fonts).\n",
|
||
|
|
"You can perform clustering either at th\n",
|
||
|
|
"class level or across all samples and then label each cluster with its\n",
|
||
|
|
"corresponding class label."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"k-Means Algorithm\n",
|
||
|
|
"================="
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(: EM Algorithms )\n",
|
||
|
|
"\n",
|
||
|
|
"Expectation Maximization (EM) algorithm:\n",
|
||
|
|
"\n",
|
||
|
|
"- solution depends on hidden information (cluster asignment)\n",
|
||
|
|
"- guess an initial solution (guess can be random)\n",
|
||
|
|
"- update the guess based on the data\n",
|
||
|
|
"- repeat until convergence"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
" The _k-means algorithm_ is an example of an expectation maximization algorithm.\n",
|
||
|
|
"Such algorithms generally have a form in which we need to find some parameters,\n",
|
||
|
|
"but in order to find those parameters, we need to know some other values that\n",
|
||
|
|
"we can't observe directly.\n",
|
||
|
|
"\n",
|
||
|
|
"In this case, we want to find the cluster centers (`protos` array), but\n",
|
||
|
|
"in order to compute the cluster center for each cluste, we would have to\n",
|
||
|
|
"know what cluster each data point belongs do, which we don't."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"# starting guess\n",
|
||
|
|
"protos = array([[30,30],[40,20],[0,90],[50,50]])\n",
|
||
|
|
"start = protos.copy()"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 5
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# plotting the starting guess\n",
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"plot(data[:,0],data[:,1],'b+')\n",
|
||
|
|
"plot(protos[:,0],protos[:,1],'ro',markersize=10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 6,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x3b07610>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvX+MXNd53/3QEa015Zoj1dHua9LawSvbYBW5u21tliwc\n7UCtQsIIgkWgSrabhOvAKIogaNcuKgsJUA6dxKKRoN46hhGgcD3rqqhlCC/Wal6BDIRiVtUbLeS8\n6W4QK6ptvZlVSJsMCHkZWzQj2tb7x9FX55lnzv1978ydme8HWOzunXvPOffOnXu+8/w6+1577bXX\nhBBCCCGEVMabRj0AQgghhJBJh4KLEEIIIaRiKLgIIYQQQiqGgosQQgghpGIouAghhBBCKoaCixBC\nCCGkYlIJrl/91V+V2dlZee973/vGtn/37/6d/L2/9/dkYWFBfvEXf1GuXr36xmuPPPKIvPvd75Yj\nR47IH/3RH5U/akIIIYSQMSKV4ProRz8q586d69v2cz/3c/KNb3xDdnZ25D3veY888sgjIiLy/PPP\ny2OPPSbPP/+8nDt3Tn7t135NfvKTn5Q/ckIIIYSQMSGV4PrZn/1ZufXWW/u23XffffKmN7nD//E/\n/sdy4cIFERH52te+Jh/+8Idl//790mw25V3vepc899xzJQ+bEEIIIWR8KCWG6z//5/8sH/zgB0VE\n5Dvf+Y4cPnz4jdcOHz4sFy9eLKMbQgghhJCx5KaiDfzO7/yOvPnNb5aPfOQjkfvs27cv1TZCCCGE\nkLpSZDXEQhauTqcjTz75pPzX//pf39h26NAh+au/+qs3/r9w4YIcOnQoePxrr73Gn5w/p0+fHvkY\nxvmH14/Xj9duPH94/Xj9RvVTlNyC69y5c/K7v/u78rWvfU1mZmbe2P4Lv/AL8pWvfEVeffVV+cu/\n/Ev51re+JUePHi08UEIIIYSQcSWVS/HDH/6wbG5uypUrV+Sd73ynnDlzRh555BF59dVX5b777hMR\nkePHj8sXvvAFueuuu+SBBx6Qu+66S2666Sb5whe+QPchIYQQQqaafa+VYSfL0/G+faWY6KaVbrcr\nrVZr1MMYW3j9isHrlx9eu2Lw+hWD1y8/RXULBRchhBBCSAJFdQuX9iGEEEIIqRgKLkIIIYSQiqHg\nIoQQQgipGAouQgghhJCKoeAihBBCCKkYCi5CCCGEkIqh4CKEEEIIqRgKLkIIIYSQiqHgIoQQQgip\nGAouQgghhJCKoeAihBBCCKkYCi5CCCGEkIqh4CKEEEIIqRgKLkIIIYSQiqHgIoQQQgipGAouQggh\nhJCKoeAihBBCCKkYCi5CCCGEkIqh4CKEEEIIqRgKLkIIIanpdkc9AkLGEwouQgghqaHgIiQfFFyE\nEEIIIRVz06gHQAghZDh0uyKtVr7jYNk6c8Zvb7XytUfINELBRQghU0JewWWFVbtdynAImSroUiSE\nEEIIqRhauAghlZLXqkLKoWx3IN9LQvJBwUUIqRQKrtFStjuQ7yUh+aBLkRBCCCGkYmjhIoSUDrPa\n6gmvPSGjY99rr7322kg63rdPRtQ1IWSItNvMaiOEjD9FdQtdioQQQgghFUPBRQipFLqxCCGELkVC\nCCGEkEToUiSEEEIIqTkUXIQQkgAyLgkhJC8UXIQQkgAFFyGkKBRchBBCCCEVw8KnhBASgMVbCSFl\nQsFFCCEByl6DkBAy3dClSAipBBv3xDgoQsg0Q8FFCKmESRJcdCESQopCwUUIIQlQcBFCisIYLkJI\nadhA817P/TSbIuvrfj8GnhNCpg0KLkJIacQFmjeb5QWed7vjLdjGffyEkOzQpUgIqYyq4rbGOR5M\nZPzHTwjJDgUXIaQSWq1+YUGLDiFkmqFLkRBSCWULrnEvRDru4yeEFIOCixBSKlUJi3EvRDru4yeE\nFIOCi5AppMqgbQoLQggZhDFchEwh4x60PQwXXJXXiC5EQqYPCi5CSGVUaUWrGgouQkiZ0KVIyJQw\niqDtYQsL1rcihNQVCi5CpoRpiK0qKriYSUgIqQoKLkIIeZ1pEKWEkNFAwUXIFDIKa01V7r4qrFJZ\n4reSzotuTkKICAUXIVPJJAmuKqxSWcZKwUUISQOzFAkhJABFEiGkTGjhIoRUxrCD0IcVMJ+0L4Pv\nCSGWfa+99tprI+l43z4ZUdeEkBHQbtcvCD3K3ZdlrEn71vG8CSHZKapb6FIkhEwt415xnxAyPqQS\nXL/6q78qs7Oz8t73vveNbS+//LLcd9998p73vEd+7ud+Tvb29t547ZFHHpF3v/vdcuTIEfmjP/qj\n8kdNCBk7ynClDUMgZQ1yT9qXLkRCiEhKwfXRj35Uzp0717ft7Nmzct9998k3v/lN+af/9J/K2bNn\nRUTk+eefl8cee0yef/55OXfunPzar/2a/OQnPyl/5ISQsaIugqvb9W6+M2f832ibgosQUgWpguZ/\n9md/Vnq9Xt+2J554QjY3N0VE5NSpU9JqteTs2bPyta99TT784Q/L/v37pdlsyrve9S557rnn5Nix\nY6UPnhCSjbqVKBjFeFjclBAyCnJnKV6+fFlmZ2dFRGR2dlYuX74sIiLf+c53+sTV4cOH5eLFiwWH\nSQgpgzIFThltpWljGBl/dcoqrJsoJoSUQyllIfbt2yf79u2LfT1EW321bLVa0uJThpCxoczioHFU\naZFCu1n6qFoQDUtwUdgREk+325VuiYGjuQXX7OysXLp0Sebm5uS73/2u3H777SIicujQIfmrv/qr\nN/a7cOGCHDp0KNhGm7Z8QipnWNabqAkc/eO1UVmTQuPL01+dhcqwRDAh04A1BJ3RD6wc5BZcv/AL\nvyDr6+vyyU9+UtbX12V5efmN7R/5yEfkE5/4hFy8eFG+9a1vydGjRwsNkhCSnzItRHFiKU5wlTWe\nIkvopH19VMselSFCKaIIqS+pBNeHP/xh2dzclCtXrsg73/lO+dSnPiUPP/ywPPDAA/LFL35Rms2m\nfPWrXxURkbvuukseeOABueuuu+Smm26SL3zhC7HuRkLI+BAnlqywgojodkVez68JtpG1/xDWipYH\njD/OSidSvlUuJPSqMv7XKVaNkGkjleD6b//tvwW3P/XUU8Htv/EbvyG/8Ru/kX9UhJBKKHtSjZrA\nGw0RlObb3BRZWvL96zGUGfSeZXxRAiNKtFUpiMoQimnPkRmahIwOrqVIyBRRpuDC5J12Aq9ick+y\noiWNz4qVpSW3zygtPln7pYgiZDyg4CJkhIxzzE3acfd6Iisr4dfs+WcN+oZYirOixaED+ZeWXDuI\nR9Ovh44pQh1ce+N63xEyrlBwETJCxllwWex56HOrInMuJE7irDtR7aKddluk2Uy2EJXxflVllSqz\nQj4hpFwouAghpRAluJrNwe1R1p0y+497PapExLi74yiiCKkvFFyEDJk07qQ6WL6KjAHniPUKQajQ\nKFx43W5+91oZ5RNC4rBq6vA+E0KGAwUXIUMmjTsJE/EoJ+ROJ3vfNq6q1RKZn+8/Z5xvSHzp17NQ\nVpbf+roXXcOIp4IonRQoIAmJhoKLkBFi1oQfIDSBDWtSSxpbiJB4ihvvMCfnOMuiFj2TJICGDQUX\nIdFQcBFSE0KCIFTQs6irL6naurZQaWtUliru2qW4uemyFLe33Ws7O34fbU3Sv6ugrED1YdbNIoRM\nDhRchIwQHTOECdeKHi26yqpqXvbxdjusRtaNqP8OCZ6scVhZj0kiTVtFr2FW4Vd3qxEFJCHpoOAi\nZMgkTVC6TIGId8sVDSxPgw1kDxUKTepvWGsSdjpOsObpp9EIb69T0gKo01hCVF14te7nT0haKLgI\nGTJpJqhQBl3eSS3v8jZJGXtR7fZ6g9auPDW57HgsvV7+rEIsO5S2z6qsOFVYGyeNaTlPMvlQcBFS\nQ8qMacor1lAdPinYHK9FuQqte7GI4Op2nWWr13PuVrhcm0033rTWt7TbQVVWnKhM1HEpHWKp23gI\nqRMUXISMkKQJKvR6FZNa1ASP
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 6
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(update)\n",
|
||
|
|
"\n",
|
||
|
|
"Obviously, those centers are wildly wrong, but let's keep going.\n",
|
||
|
|
"\n",
|
||
|
|
"Now, we compute the assignment of the data points to the prototypes\n",
|
||
|
|
"(array `closest`).\n",
|
||
|
|
"\n",
|
||
|
|
"This is also wildly wrong, but we're going to be using it anyay."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# k-means update\n",
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"dists = cdist(protos,data)\n",
|
||
|
|
"closest = argmin(dists,axis=0)\n",
|
||
|
|
"for i in range(len(protos)):\n",
|
||
|
|
" plot(data[closest==i,0],data[closest==i,1],['c+','g+','b+','y+'][i])\n",
|
||
|
|
"plot(protos[:,0],protos[:,1],'ro',markersize=10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 7,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x3fb1790>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvX9sXOd55/slPaJH8lQ6UVhzUDHSALED1W0qbps48iIN\nBylcG8GiEArXblJ0xRSL4qK4uKtksY7RAqtRtq0VtNhq226wwCINmU2xceA/lOzewC6Mi2Ea1Kzr\n7h1lNy6RKOiRQiejC1YZ0WNpTI2k+8eZ553nvHN+zcyZn/x+AILkzDnv+54zlM/Xz/O832fm3r17\n90AIIYQQQgbG7KgXQAghhBAy7VBwEUIIIYQMGAouQgghhJABQ8FFCCGEEDJgKLgIIYQQQgYMBRch\nhBBCyIBJJLh+67d+CwsLC3j/+99vXvu3//bf4qd/+qdx4sQJ/Oqv/ipu3Lhh3nv++efx8MMP4/jx\n4/irv/qr9FdNCCGEEDJBJBJcn/zkJ/HSSy/5XvvlX/5lfOc738GlS5fwvve9D88//zwA4I033sAL\nL7yAN954Ay+99BJ+53d+B3fv3k1/5YQQQgghE0IiwfWLv/iLeNe73uV77fHHH8fsrHf6hz70IWxt\nbQEAvva1r+HjH/849u3bh0KhgIceegivvfZayssmhBBCCJkcUqnh+ou/+At87GMfAwD88Ic/xOLi\nonlvcXERb775ZhrTEEIIIYRMJJl+B/iDP/gDzM3N4ROf+EToMTMzM4leI4QQQggZV/rphthXhGt1\ndRXf+MY38Jd/+ZfmtSNHjuAHP/iB+X1rawtHjhwJPP/evXv86vHr7NmzI1/DJH/x/vH+8d5N5hfv\nH+/fqL76pWfB9dJLL+GP/uiP8LWvfQ3ZbNa8/iu/8iv4yle+gt3dXfzjP/4jvve97+HRRx/te6GE\nEEIIIZNKopTixz/+cayvr2N7exvvec97cO7cOTz//PPY3d3F448/DgB47LHH8PnPfx6PPPIInn76\naTzyyCPIZDL4/Oc/z/QhIYQQQvY0M/fSiJP1MvHMTCohur1KuVxGsVgc9TImFt6//uD96x3eu/7g\n/esP3r/e6Ve3UHARQgghhMTQr25hax9CCCGEkAFDwUUIIYQQMmAouAghhBBCBgwFFyGEEELIgKHg\nIoQQQggZMBRchBBCCCEDhoKLEEIIIWTAUHARQgghhAwYCi5CCCGEkAFDwUUIIYQQMmAouAghhBBC\nBgwFFyGEEELIgKHgIoQQQggZMBRchBBCCCEDhoKLEEIIIWTAUHARQgghhAwYCi5CCCGEkAFDwUUI\nIYQQMmAouAghhBBCBgwFFyGEkMTUauVRL4GQiYSCixBCSGIouAjpDQouQgghhJABkxn1AgghhAyH\nWq0Mxyn2dJ5Etlz3nHndcYo9jUfIXoSCixBC9gi9Ci5bWBUKpdTWRMhegSlFQgghhJABwwgXIWSg\nlMtAsTjqVexd0k4HMoVISG9QcBFCBgoF12hJOx1IwUVIbzClSAghhBAyYBjhIoSkTrnsfQHAuXYW\nC8Uio12jhNEpQkbHzL179+6NZOKZGYxoakLIECmVvC9CCJlk+tUtTCkSQgghhAwYCi5CyEBhCpEQ\nQphSJIQQQgiJhSlFQgghhJAxh4KLEEJiEONQQgjpFQouQgiJgYKLENIvFFyEEEIIIQOGxqeEEBJA\n2j0ICSF7GwouQggJIO0ehISQvQ1TioSQgSCtfcJ+J4SQvQQFFyFkIEyT4GIKkRDSLxRchBASAwUX\nIaRfWMNFCEmNcrkdyTp3DnBd76tQANbW2scVi2z5QwjZW1BwEUJSwxZSpVL750LB/3s/lMuTLdhq\ntTKjZoTsMZhSJIQMjEHVbU1yPRhAI1VC9iIUXISQgVAs+oXRJEekCCGkX5hSJIQMhLQFl10fpsed\nBDFHI1VC9jYUXISQVBmUMIqqD5sEaKRKyN6GgouQPcggi84nXRgRQsggYA0XIXuQSS86H0YKcZCF\n7UwhErL3oOAihAyMQUbRBg0FFyEkTZhSJGSPMIqi82EXs0+6PxchZHqh4CJkj7AXaqv6FVzcSUgI\nGRQUXIQQ0oI7CQkhg4KCi5A9yCjSboNK9w0iVdpN/VZcmx628SGEABRchOxJpklwDSJV2o1IouAi\nhCSBuxQJISQAiiRCSJowwkUIGRjD3hk5rIL5uGNZfE8IsZm5d+/evZFMPDODEU1NCBkBpdL47YwM\nS/e5bilxwXzcsd2MRQgZX/rVLUwpEkL2LIM0NyWEEE0iwfVbv/VbWFhYwPvf/37z2vXr1/H444/j\nfe97H375l38ZtVrNvPf888/j4YcfxvHjx/FXf/VX6a+aEDJxpJFCHEZLom6L3OOOZQqREAIkFFyf\n/OQn8dJLL/leO3/+PB5//HF897vfxS/90i/h/PnzAIA33ngDL7zwAt544w289NJL+J3f+R3cvXs3\n/ZUTQiaKcRFctVoZrltqfZ0zP0u0i4KLEDIIEhXN/+Iv/iJc1/W99vWvfx3r6+sAgNOnT6NYLOL8\n+fP42te+ho9//OPYt28fCoUCHnroIbz22ms4efJk6osnhHTHuLW+GcV6aG5KCBkFPe9SvHbtGhYW\nFgAACwsLuHbtGgDghz/8oU9cLS4u4s033+xzmYSQNEhT4KQxVpIxhrHTcZx2FdK3i5DpJBVbiJmZ\nGczMzES+H0RJbVkqFosojtP/ehNCIulGcPUjzgbZA1KETTdRr0ELomEJLgo7QqIpl8sop1g42rPg\nWlhYQLVaRT6fx49+9CM8+OCDAIAjR47gBz/4gTlua2sLR44cCRyjNG57xAmZQoblhRUmqmR+eW/Y\n3lxCkMDoRXCMs1BJ0yGfkL2OHQg6p/+D1QM9C65f+ZVfwdraGj7zmc9gbW0Np06dMq9/4hOfwKc/\n/Wm8+eab+N73vodHH320r0USQnonzQhRlFiKElxprSdKkPXbYkfeH4UISSulSRFFyPiSSHB9/OMf\nx/r6Ora3t/Ge97wHn/3sZ/Hcc8/h6aefxhe+8AUUCgV89atfBQA88sgjePrpp/HII48gk8ng85//\nfGS6kRAyOUSJJVtYiTgrl4HW/prAMbqdPwgRLP2IDRE8QWMMssYrSOgNqpB/nGrVCNlrJBJc/+2/\n/bfA11955ZXA13/3d38Xv/u7v9v7qgghAyHtlF1YxMtxALHmW18Hlpfb8+s1pFn0HvZ6NwIjTLQN\nUhClIRSTXiN3aBIyOthLkZA9RJqCS8RT0vTgIEo2RWx4X+0wmgiLOIFhixXHWYbrlkYa8el2Xooo\nQiYDCi5CRsi4+WJ1Q9J1uy6wshL8nn393dwPLZZqtXU4jhdG60YsyXFelGm5NU4xMr2YhhAbh9Qe\nU4iEDBcKLkJGyCQLLhv7OvS1DcI+IkicREV3wgSGjOO6JWSzhdgIURpCZVBRqTQd8gkh6ULBRQhJ\nhTDBVSh0vh6207EfummxE2YR4bql/hYxYiiiCBlfKLgIGTJJfKjGIfLVzxrkGkulYFGlr1UsJcrl\n3n250rBPcJwistlC4jHSgDYOhOwdKLgIGTJJCs1F7IxSeK2udj+3FpPr6975x475r1muN0h86fe7\nIa1dftXqmhFdw6inqtXKU1XkTgFJSDgUXISMEKsnfAdBgmtYIixubUEEiaeo9Q5TTEYVqmvRM00C\naNhQcBESDgUXIWNCUKrRbosjr/WT6os6145Q6WhU3Hn2GiWluL7u7VKsVLz3Ll1qHyP1Xd0W1/dC\nWoXqw/TNIoRMDxRchIwQXVAuosYWPVp09StI+o2ORbXvsQ1NS6XONKL+OSh12M3aoqwbeiXJWP0K\nrm6F37hHjSggCUkGBRchQyauaF6+tDDRbXIG2fDZLmS3RVESwZaWOIyjWl1FNlvo6aGeyTiBr/t9\nubofdxCM01qCGLTx6rhfPyFJoeAiZMgkKRK3xUo/heVJdkXaxwfZOSQd13U7o129eHIJYQ/cRsPt\neVdhs1nras5BRXH6TU3uBSGy
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 7
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"history = [protos.copy()]\n",
|
||
|
|
"\n",
|
||
|
|
"for i in range(len(protos)):\n",
|
||
|
|
" protos[i,:] = average(data[closest==i],axis=0)\n",
|
||
|
|
" \n",
|
||
|
|
"history.append(protos.copy())"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 8
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Now we pretend that the cluster assignments are correct and\n",
|
||
|
|
"recompute the location of the centers.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"plot(data[:,0],data[:,1],'b+')\n",
|
||
|
|
"harray = array(history)\n",
|
||
|
|
"for i in range(len(protos)):\n",
|
||
|
|
" plot(harray[:,i,0],harray[:,i,1],'r')\n",
|
||
|
|
"plot(harray[0,:,0],harray[0,:,1],'ko',markersize=10)\n",
|
||
|
|
"plot(protos[:,0],protos[:,1],'ro',markersize=10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 106,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x9ac7610>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvX+QXFd55/2VsUCMHdR2HM8UY2t6yz/WMfDOkIAi5wVN\n45TwLEXYKVaxYgKZgbApiqUSARXZRd5ELRawKLIw2biAVHDco4gK8s5WDQ7ryOBke4TfeFbJ8s5Q\nYLyAoEe27BFo2RG2B2H5x/vH8eP79Olz7u/uvt3z/VRNzfTte88593ZP329/n+c8Z9Pzzz//PAgh\nhBBCSNu4oNsDIIQQQgjpdyi4CCGEEELaDAUXIYQQQkiboeAihBBCCGkzFFyEEEIIIW2GgosQQggh\npM3EElzvec97MDg4iNe85jUvbvujP/oj/PIv/zJGR0fx9re/HWfPnn3xudtvvx3XXHMNrrvuOnz1\nq1/Nf9SEEEIIIT1ELMH17ne/G0ePHm3a9uY3vxnf/va3sby8jGuvvRa33347AOChhx7CkSNH8NBD\nD+Ho0aN4//vfj+eeey7/kRNCCCGE9AixBNcb3/hGXHLJJU3bdu3ahQsuMIf/2q/9Gh599FEAwJe/\n/GXccsst2Lx5M8rlMq6++mocP34852ETQgghhPQOF+bRyF//9V/jlltuAQA89thj2LFjx4vPXXHF\nFTh16lTT/ps2bcqjW0IIIYSQjpB1YZ7MSfMf//jH8dKXvhTveMc7vPu4BNbzzz/Pn5Q/+/fv7/oY\nevmH14/Xj9euN394/Xj9uvWTB5kcrlqthnvvvRf/8A//8OK24eFhPPLIIy8+fvTRRzE8PJylG0II\nIYSQnia1w3X06FF86lOfwpe//GVs2bLlxe1ve9vb8KUvfQlPP/00fvjDH+J73/setm/fnstgCSGE\nEEJ6kVgO1y233IKFhQWcOXMGV155JQ4cOIDbb78dTz/9NHbt2gUAuOGGG/DZz34W119/PW6++WZc\nf/31uPDCC/HZz36WOVs5U6lUuj2EnobXLxu8funhtcsGr182eP26y6bn8wpOJul006bcYqKEEEII\nIe0kD93CSvOEEEIIIW2GgosQQgghpM1QcBFCCCGEtBkKLkIIIYSQNkPBRQghhBDSZii4CCGEEELa\nDAUXIYQQQkiboeAihBBCCGkzFFyEEEIIIW2GgosQQgghpM1QcBFCCCGEtBkKLkIIIYSQNkPBRQgh\nhBDSZii4CCGEEELaDAUXIYQQQkiboeAihBBCCGkzFFyEEEIIIW2GgosQQgghpM1QcBFCCCGEtBkK\nLkJIT1Ovd3sEhBASDQUXIaSnoeAihPQCFFyEEEIIIW3mwm4PgBBCklKvB87WgQPB9krF/BBCSNGg\n4CKE9By2sKpWuzQQQgiJCUOKhBBCCCFthoKLENLTMIRICOkFNj3//PPPd7zTTZvQhW4JIYQQQhKT\nh26hw0UIIYQQ0mYouAghhBBC2gwFFyGEEEJIm6HgIoT0PaxGTwjpNhRchJC+h4KLENJtKLgIIYQQ\nQtoMK80TQvoSLv9DCCkSFFyEkL6Ey/8QQooEQ4qEkMLAXCtCSL9CwUUIKQztElwMIRJCug0FFyGk\n76HgIoR0G+ZwEUK6CpPbCSEbAQouQkhXYXI7IWQjwJAiIYQQQkiboeAihBSGXgkhcjYlISQpFFyE\nkMJAwUUI6VcouAghhBBC2gyT5gkhJAacTUkIyQIFFyEkFvV6/wuLsHPkbEpCSBYYUiSExGIj5C1t\nhHMkhHQHCi5CNhgUFdnpd6ePEJI/DCkSssFIEhrcCHlLac6xX86dENI5KLgIIV76KW/JJzT76RwJ\nIcWFgouQDcBGcKqi2AhJ/4SQ4kLBRcgGIA8Xp11ipUhCqCjj2GgU6T1ASLug4CKExKIXBVdSZ483\n/e5AwUU2AhRchGwweu3GlvRmrPdnfhYhpChQcBGywSiC4JqZAdbWzN9RzlMWwUWKC/MKyUaDgosQ\n0nHW1gK3qV7vjPPUCzfxjSQW6T6SjQYFFyEkF/IUC0ndjzj794KQ2UiCi5CNBgUXISQXosSCLYrk\n74WFwN0QgZTU/aBb0ttQZJKNAAUXIaQj+ERRtbqxBVK7cpl6yS3rlXESkgUKLkJIajqR+Jy0nXbc\nvNspXtrlzvWS4CJkIxBr8er3vOc9GBwcxGte85oXt/3kJz/Brl27cO211+LNb34z1mTKEYDbb78d\n11xzDa677jp89atfzX/UhBAvnVyculIJHKr9+4O/o270+vkk+/rQ59wuwUUIIVmIJbje/e534+jR\no03bDh48iF27duG73/0ufuM3fgMHDx4EADz00EM4cuQIHnroIRw9ehTvf//78dxzz+U/ckIKTrdu\n0na/WcfRjvNIIrji0C+CKOu1kBmf1apxHOXvfrk+hPQysUKKb3zjG9FoNJq23XPPPVhYWAAATE1N\noVKp4ODBg/jyl7+MW265BZs3b0a5XMbVV1+N48ePY8eOHbkPnpAiU5SQTtZxxD2+COcaRpp6Xp2u\nE5W13bDwZFHej4RsVFLncJ0+fRqDg4MAgMHBQZw+fRoA8NhjjzWJqyuuuAKnTp3KOExCSBhh4qBT\ndPpmnqZ0RJIxdnvmY94CiYKLkO6SS9L8pk2bsGnTptDnbarq06tSqaDCTwLSB3SrerbdfqUSjCXN\nONotZvKg24LIR17XIms7/EglJD31eh31nGPxqQXX4OAgVldXMTQ0hMcffxyXX345AGB4eBiPPPLI\ni/s9+uijGB4ebjm+WpRPR0JypCgiIOs4kh5fJPdEjyUvAdyLSwtp0Q1w+RxCkmAbQQf0P1BKUguu\nt73tbZidncWtt96K2dlZTE5Ovrj9He94Bz70oQ/h1KlT+N73voft27dnHighJB4b8Uaqz7kdi1dn\nXd8xLnkLpKJ8ASCExBRct9xyCxYWFnDmzBlceeWV+OhHP4rbbrsNN998M+68806Uy2XcfffdAIDr\nr78eN998M66//npceOGF+OxnPxsabiSkX+mW8LH7zSMR20VR3JNOLW5tO2e2yMvLSYsSSEVx0Agh\nyYgluP72b//Wuf3+++93bv/IRz6Cj3zkI+lHRUgfUJSbYtJx2Dd03/FFCTuK0Im7lmIegst+3Ekn\nKe34i/J+JGSjwkrzhPQZnSgDkaaPbldr94mluDQaQbuyFqT0247zyrtNCi5CugsFFyF9RidCTlEu\nWLvHkLQMhmvh7DhiSR83O2uq6QPA1BRQLrcKuzzPO0nIkmFGQooPBRchJHMOkk9wtSvPK2kIz9Vf\n2DE+QVYqAWtrxu2anW1tXyq9u9rKQtT5UnARUnwouAjpA/IQTHGStZP20Y1ZclEuV70OvLBIxov7\nx3Xo1tbMOczMmOfjnA/FECEEoOAipC/ohLCxk89dLku3ir7G3U+7bmlqk8n5ra0F2+3zbjRMuLHd\nuV0zM8E4OtEvISQbFFyEkJYZd3H2s4kSfUURAVo4aXyC0RVGrNeBF0oPOgWOFnZ5i085Xtw2Dets\nEVJcKLgI6TOyljxIk7MVh3YJLp0vFqcPX3mHKME4PQ2Mj5u/FxaCkKJPcOkyFAw9EkIouAjpM/K+\nafucn7C+uiEckgguLYDs42Zm3MeVy80zE+026nV3Mn1c4pbjsMOXjQawZQtw333N/VK8EVIsKLgI\n2aDEybnS7o/sG3d2X7twFToV4ZGm6rz+u1IBarVAdNnXaGrKnH+j0dyOPmfJo9IJ+nLN2jk7s1qN\nH1Kkm0ZI56HgIn3LRrmpZKk8HmdmohZfaceS52shDpUWNY2GETby2D43nzO0tgYsLze3u7bWHF61\n6435csA0cScxdGuiwUb53yCkSFBwkb4lyU2ll29AnRx73PIJNnm/Fq6cs7AyDT4BVK2a5PdSKagk\nv7IS7Ds5Cezd29pv2PiSvBZZ6mu58sbiEEc4E0Lyh4KLEPS24MoDlxsk+Uhyg5baVa4wY54ujSsJ\n3lUpvlwGlpaAoSGTvzQ+7k9i
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 106
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"As you can see, the centers have moved, and it looks like they have generally moved in the right direction. Now let's just repeat this process multiple times.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"for round in range(1000):\n",
|
||
|
|
" if round%100==0: sys.stderr.write(\"%d \"%round)\n",
|
||
|
|
" dists = cdist(protos,data)\n",
|
||
|
|
" closest = argmin(dists,axis=0)\n",
|
||
|
|
" for i in range(len(protos)):\n",
|
||
|
|
" protos[i,:] = average(data[closest==i],axis=0)\n",
|
||
|
|
" history.append(protos.copy())"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stderr",
|
||
|
|
"text": [
|
||
|
|
"0 100 "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stderr",
|
||
|
|
"text": [
|
||
|
|
"200 300 "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stderr",
|
||
|
|
"text": [
|
||
|
|
"400 500 "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stderr",
|
||
|
|
"text": [
|
||
|
|
"600 700 "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stderr",
|
||
|
|
"text": [
|
||
|
|
"800 900 "
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 107
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We can now plot the path that the prototype guesses have taken.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"plot(data[:,0],data[:,1],'b+')\n",
|
||
|
|
"history = array(history)\n",
|
||
|
|
"for i in range(len(protos)):\n",
|
||
|
|
" plot(history[:,i,0],history[:,i,1],'r')\n",
|
||
|
|
"plot(history[0,:,0],history[0,:,1],'ko',markersize=10)\n",
|
||
|
|
"plot(protos[:,0],protos[:,1],'ro',markersize=10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 108,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x9e43750>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvX2cnVV59/sbIBICyoYiMyUx2S0vIkpnbDUGi5ldNDKP\n9bFTG4n4lkGpx+OjddSnwNGeZscXCNVPHSsPtS/IHpo+GprTMyDlEyy2eyKWNNaeGauUKuieQGCi\nqZ1IGAPh5fyxuHJfe+217vf9Or/v5zOf2fve973Wuu+9Z9+/+V3Xulbfs88++ywIIYQQQkjTOK7d\nAyCEEEII6XUouAghhBBCmgwFFyGEEEJIk6HgIoQQQghpMhRchBBCCCFNhoKLEEIIIaTJxBJc7373\nu9Hf348LL7zw2Lbf//3fx0te8hIMDg7izW9+Mw4dOnTsteuuuw7nnnsuzj//fHzta1/Lf9SEEEII\nIV1ELMF1xRVXYNeuXXXbXv/61+N73/seZmdncd555+G6664DANx3333YsWMH7rvvPuzatQvvf//7\n8cwzz+Q/ckIIIYSQLiGW4HrNa16D0047rW7bhg0bcNxx5vBXvepVePjhhwEAt912Gy6//HIsW7YM\nxWIR55xzDvbu3ZvzsAkhhBBCuocT8mjkS1/6Ei6//HIAwCOPPIJ169Yde23VqlXYv39/3f59fX15\ndEsIIYQQ0hKyLsyTOWn+05/+NJ73vOfhbW97m3cfl8B69tln+ZPyZ8uWLW0fQzf/8Prx+vHadecP\nrx+vX7t+8iCTw1WpVHDnnXfi61//+rFtK1euxEMPPXTs+cMPP4yVK1dm6YYQQgghpKtJ7XDt2rUL\nn/nMZ3Dbbbdh+fLlx7a/6U1vwle+8hU8+eST+NGPfoQf/OAHWLt2bS6DJYQQQgjpRmI5XJdffjmm\np6dx8OBBvOhFL8LWrVtx3XXX4cknn8SGDRsAABdddBFuvPFGXHDBBbjssstwwQUX4IQTTsCNN97I\nnK2cKZVK7R5CV8Prlw1ev/Tw2mWD1y8bvH7tpe/ZvIKTSTrt68stJkoIIYQQ0kzy0C2sNE8IIYQQ\n0mQouAghhBBCmgwFFyGEEEJIk6HgIoQQQghpMhRchBBCCCFNhoKLEEIIIaTJUHARQgghhDQZCi5C\nCCGEkCZDwUUIIYQQ0mQouAghhBBCmgwFFyGEEEJIk6HgIoQQQghpMhRchBBCCCFNhoKLEEIIIaTJ\nUHARQgghhDQZCi5CCCGEkCZDwUUIIYQQ0mQouAghhBBCmgwFFyGEEEJIk6HgIoR0NdVqu0dACCHR\nUHARQroaCi5CSDdAwUUIIYQQ0mROaPcACCEkKdVq4Gxt3RpsL5XMDyGEdBoUXISQrsMWVuVymwZC\nCCExYUiREEIIIaTJUHARQroahhAJId1A37PPPvtsyzvt60MbuiWEEEIISUweuoUOFyGEEEJIk6Hg\nIoQQQghpMhRchBBCCCFNhoKLENLzsBo9IaTdUHARQnoeCi5CSLuh4CKEEEIIaTKsNE8I6Um4/A8h\npJOg4CKE9CRc/ocQ0kkwpEgI6RiYa0UI6VUouAghHUOzBBdDiISQdkPBRQjpeSi4CCHthjlchJC2\nwuR2QshSgIKLENJWmNxOCFkKMKRICCGEENJkKLgIIR1Dt4QQOZuSEJIUCi5CSMdAwUUI6VUouAgh\nhBBCmgyT5gkhJAacTUkIyQIFFyEkFtVq7wuLsHPkbEpCSBYYUiSExGIp5C0thXMkhLQHCi5ClhgU\nFdnpdaePEJI/DCkSssRIEhpcCnlLac6xV86dENI6KLgIIV56KW/JJzR76RwJIZ0LBRchS4Cl4FRF\nsRSS/gkhnQsFFyFLgDxcnGaJlU4SQp0yjqVGJ30GCGkWFFyEkFh0o+BK6uzxpt8eKLjIUoCCi5Al\nRrfd2JLejPX+zM8ihHQKFFyELDE6QXBNTAALC+ZxlPOURXCRzoV5hWSpQcFFCGk5CwuB21SttsZ5\n6oab+FISi3QfyVKDgosQkgt5ioWk7kec/btByCwlwUXIUoOCixCSC1FiwRZF8nh6OnA3RCAldT/o\nlnQ3FJlkKUDBRQhpCT5RVC4vbYHUrFymbnLLumWchGSBgosQkppWJD4nbacZN+9mipdmuXPdJLgI\nWQrEWrz63e9+N/r7+3HhhRce2/bTn/4UGzZswHnnnYfXv/71WJApRwCuu+46nHvuuTj//PPxta99\nLf9RE0K8tHJx6lIpcKi2bAkeR93o9etJ9vWhz7lZgosQQrIQS3BdccUV2LVrV922bdu2YcOGDfj+\n97+P1772tdi2bRsA4L777sOOHTtw3333YdeuXXj/+9+PZ555Jv+RE9LhtOsmbfebdRzNOI8kgisO\nvSKIsl4LmfFZLhvHUR73yvUhpJuJFVJ8zWteg1qtVrft9ttvx/T0NABg8+bNKJVK2LZtG2677TZc\nfvnlWLZsGYrFIs455xzs3bsX69aty33whHQynRLSyTqOuMd3wrmGkaaeV6vrRGVtNyw82SmfR0KW\nKqlzuA4cOID+/n4AQH9/Pw4cOAAAeOSRR+rE1apVq7B///6MwySEhBEmDlpFq2/maUpHJBlju2c+\n5i2QKLgIaS+5JM339fWhr68v9HWbsvr2KpVKKPGbgPQA7aqebbdfKgVjSTOOZouZPGi3IPKR17XI\n2g6/UglJT7VaRTXnWHxqwdXf34/5+XkMDAzg0UcfxZlnngkAWLlyJR566KFj+z388MNYuXJlw/Hl\nTvl2JCRHOkUEZB1H0uM7yT3RY8lLAHfj0kJadANcPoeQJNhG0Fb9B5SS1ILrTW96EyYnJ3H11Vdj\ncnISo6Ojx7a/7W1vw0c+8hHs378fP/jBD7B27drMAyWExGMp3kj1OTdj8eqs6zvGJW+B1Cn/ABBC\nYgquyy+/HNPT0zh48CBe9KIX4ROf+ASuueYaXHbZZbjppptQLBZx6623AgAuuOACXHbZZbjgggtw\nwgkn4MYbbwwNNxLSq7RL+Nj95pGI7aJT3JNWLW5tO2e2yMvLSYsSSJ3ioBFCkhFLcH35y192br/7\n7rud2z/2sY/hYx/7WPpREdIDdMpNMek47Bu67/hOCTuK0Im7lmIegst+3konKe34O+XzSMhShZXm\nCekxWlEGIk0f7a7W7hNLcanVgnZlLUjptxnnlXebFFyEtBcKLkJ6jFaEnKJcsGaPIWkZDNfC2XHE\nkj5uctJU0weAzZuBYrFR2OV53klClgwzEtL5UHARQjLnIPkEV7PyvJKG8Fz9hR3jE2SFArCwYNyu\nycnG9qXSu6utLESdLwUXIZ0PBRchPUAegilOsnbSPtoxSy7K5apWgecWyTi2f1yHbmHBnMPEhHk9\nzvlQDBFCAAouQnqCVggbO/nc5bK0q+hr3P2065amNpmc38JCsN0+71rNhBubnds1MRGMoxX9EkKy\nQcFFCGmYcRdnP5so0dcpIkALJ41PMLrCiNUq8FzpQafA0cIub/Epx4vbpmGdLUI6FwouQnqMrCUP\n0uRsxaFZgkvni8Xpw1feIUowjo0Bw8Pm8fR0EFL0CS5dhoKhR0IIBRchPUbeN22f8xPWVzuEQxLB\npQWQfdzEhPu4YrF+ZqLdRrXqTqaPS9xyHHb4slYDli8H7rqrvl+KN0I6CwouQpYocXKutPsj+8ad\n3dcsXIVORXikqTqvH5dKQKUSiC77Gm3ebM6/VqtvR5+z5FHpBH25Zs2cnVkuxw8p0k0jpPVQcJGe\nZancVLJUHo8zM1GLr7RjyfO9EIdKi5pazQgbeW6fm88ZWlgAZmfr211YqA+v2vXGfDlgmriTGNo1\n0WCp/G0Q0klQcJGeJclNpZtvQK0ce9zyCTZ5vxeunLOwMg0+AVQum+T3QiGoJD83F+w7OgqMjzf2\nGza+JO9FlvparryxOMQRzoSQ/KHgIgTdLbjywOUGST6S3KCldpUrzJinS+NKgndVii8WgZkZYGDA\n5C8ND/uT2DX2Ej1r1hjBNTdn
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 108
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"As you can see, the final location of the prototype centers (red) are nicely\n",
|
||
|
|
"in the center of the classes.\n",
|
||
|
|
"\n",
|
||
|
|
"The algorithm doesn't give us exactly the cluster centers because there are\n",
|
||
|
|
"three clusters but we postulated four cluster centers."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"figsize(10,10)\n",
|
||
|
|
"dists = cdist(protos,data)\n",
|
||
|
|
"closest = argmin(dists,axis=0)\n",
|
||
|
|
"for i in range(len(protos)):\n",
|
||
|
|
" plot(data[closest==i,0],data[closest==i,1],['c+','g+','b+','y+'][i])\n",
|
||
|
|
"plot(protos[:,0],protos[:,1],'ro',markersize=10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 110,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x9e69510>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAAJMCAYAAAAvyngrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvX+MJFd59/tds8bN7oZtOxtPi108rbs22hjzziQBZ50L\nTIlk8Qq9F83ldWyZkMyAuBGXGymTRLEtImV7kxe8XFAyeWMhdCOHnmSlYMvSHRxkrXkd3WrCG28c\nEvUQcPYFNtSYNe4JK+g166VtL/b9o/apeur0qV/d1T/n+5FG01196pxT1eOtr5/nOd+z49VXX30V\nhBBCCCFkYFw16gkQQgghhEw7FFyEEEIIIQOGgosQQgghZMBQcBFCCCGEDBgKLkIIIYSQAUPBRQgh\nhBAyYDIJrg996EOYmZnBW97yluDY7//+7+Nnf/ZnMTc3h/e97324cOFC8Nn999+Pm266CYcOHcKX\nvvSl4mdNCCGEEDJBZBJcH/zgB3Hq1KnIsXe/+934xje+gY2NDbzpTW/C/fffDwB4+umn8dBDD+Hp\np5/GqVOn8NGPfhSvvPJK8TMnhBBCCJkQMgmud7zjHbj22msjx44cOYKrrvJP/8Vf/EWcO3cOAPCF\nL3wBd999N66++mpUq1XceOONeOqppwqeNiGEEELI5LCziE7+8i//EnfffTcA4Hvf+x4OHz4cfHbg\nwAE8++yzkfY7duwoYlhCCCGEkKHQ78Y8fRfNf/zjH8drX/tavP/9749tYxNYr776Kn96/Dl27NjI\n5zDJP7x/vH+8d5P5w/vH+zeqnyLoK8JVr9fx2GOP4e/+7u+CY/v378d3v/vd4P25c+ewf//+foYh\nhBBCCJloeo5wnTp1Cp/61KfwhS98AaVSKTj+3ve+F5///Ofx0ksv4Tvf+Q6+9a1v4dZbby1ksoQQ\nQgghk0imCNfdd9+NRqOB8+fP441vfCOOHz+O+++/Hy+99BKOHDkCALjtttvwmc98BjfffDPuvPNO\n3Hzzzdi5cyc+85nPsGarYBzHGfUUJhrev/7g/esd3rv+4P3rD96/0bLj1aKSk3kG3bGjsJwoIYQQ\nQsggKUK30GmeEEIIIWTAUHARQgghhAwYCi5CCCGEkAFDwUUIIYQQMmAouAghhBBCBgwFFyGEEELI\ngKHgIoQQQggZMBRchBBCCCEDhoKLEEIIIWTAUHARQgghhAwYCi5CCCGEkAFDwUUIIYQQMmAouAgh\nhBBCBgwFFyGEEELIgKHgIoQQQggZMBRchBBCCCEDhoKLEEIIIWTAUHARQgghhAwYCi5CCCGEkAFD\nwUUImWhcd9QzIISQdCi4CCETDQUXIWQSoOAihBBCCBkwO0c9AUIIyYvrhpGt48fD447j/xBCyLhB\nwUUImThMYVWrjWgihBCSEaYUCSGEEEIGDAUXIWSiYQqREDIJ7Hj11VdfHfqgO3ZgBMMSQgghhOSm\nCN3CCBchhBBCyICh4CKEEEIIGTAUXIQQQgghA4aCixAy9dCNnhAyaii4CCFTDwUXIWTUUHARQggh\nhAwYOs0TQqYSbv9DCBknKLgIIVMJt/8hhIwTTCkSQsYG1loRQqYVCi5CyNgwKMHFFCIhZNRQcBFC\nph4KLkLIqGENFyFkpLC4nRCyHaDgIoSMFBa3E0K2A0wpEkIIIYQMGAouQsjYMCkpRK6mJITkhYKL\nEDI2UHARQqYVCi5CCCGEkAHDonlCCMkAV1MSQvqBgosQkgnXnX5hkXSNXE1JCOkHphQJIZnYDnVL\n2+EaCSGjgYKLkG0GRUX/THukjxBSPEwpErLNyJMa3A51S71c47RcOyFkeFBwEUJimaa6pTihOU3X\nSAgZXyi4CNkGbIdIVRrboeifEDK+UHARsg0oIoozKLEyTkJoXOax3RinvwFCBgUFFyEkE5MouPJG\n9vjQHw0UXGQ7QMFFyDZj0h5seR/Guj3rswgh4wIFFyHbjHEQXKurQLvtv06LPPUjuMj4wrpCst2g\n4CKEDJ12O4w2ue5wIk+T8BDfTmKR0Uey3aDgIoQUQpFiIW/0I0v7SRAy20lwEbLdoOAihBRCmlgw\nRZG8bjTC6IYIpLzRD0ZLJhuKTLIdoOAihAyFOFFUq21vgTSoWqZJipZNyjwJ6QcKLkJIzwyj8Dlv\nP4N4eA9SvAwqOjdJgouQ7UCmzas/9KEPYWZmBm95y1uCYz/4wQ9w5MgRvOlNb8K73/1utGXJEYD7\n778fN910Ew4dOoQvfelLxc+aEBLLMDendpwwQnXsWPg67UGvP8/TNg59zYMSXIQQ0g+ZBNcHP/hB\nnDp1KnLsxIkTOHLkCL75zW/il3/5l3HixAkAwNNPP42HHnoITz/9NE6dOoWPfvSjeOWVV4qfOSFj\nzqge0ua4/c5jENeRR3BlYVoEUb/3QlZ81mp+xFFeT8v9IWSSyZRSfMc73gHP8yLHHn30UTQaDQDA\n0tISHMfBiRMn8IUvfAF33303rr76alSrVdx444146qmncPjw4cInT8g4My4pnX7nkfX8cbjWJHrx\n8xq2T1S//SalJ8fl75GQ7UrPNVxbW1uYmZkBAMzMzGBrawsA8L3vfS8irg4cOIBnn322z2kSQpJI\nEgfDYtgP816sI/LMcdQrH4sWSBRchIyWQormd+zYgR07diR+blJT/3o5jgOH/xKQKWBU7tlm/44T\nzqWXeQxazBTBqAVRHEXdi3774T+phPSO67pwC87F9yy4ZmZm0Gq1UKlU8Nxzz+H6668HAOzfvx/f\n/e53g3bnzp3D/v37u86vjcu/joQUyLiIgH7nkff8cYqe6LkUJYAncWshLboBbp9DSB7MQNBx/R9Q\nj/QsuN773vdibW0N9957L9bW1rC4uBgcf//734/f/d3fxbPPPotvfetbuPXWW/ueKCEkG9vxQaqv\neRCbV/e7v2NWihZI4/I/AISQjILr7rvvRqPRwPnz5/HGN74Rf/RHf4T77rsPd955Jx588EFUq1U8\n/PDDAICbb74Zd955J26++Wbs3LkTn/nMZxLTjYRMK6MSPua4RRRi2xiX6MmwNrc2I2emyCsqkpYm\nkMYlgkYIyUcmwfU3f/M31uNPPPGE9fjHPvYxfOxjH+t9VoRMAePyUMw7D/OBHnf+uKQdRehk3Uux\nCMFlvh9mJKnX+Y/L3yMh2xU6zRMyZQzDBqKXMUbt1h4nlrLieWG/shekjDuI6yq6TwouQkYLBRch\nU8YwUk5pUbBBzyGvDYZt4+wsYkmft7bmu+kDwNISUK12C7sirztPypJpRkLGHwouQkjfNUhxgmtQ\ndV55U3i28ZLOiRNk5TLQbvvRrrW17v7F6d3WVz+kXS8FFyHjDwUXIVNAEYIpS7F23jFGsUouLcrl\nusCVTTKC9lkjdO22fw2rq/7nWa6HYogQAlBwETIVDEPYmMXntijLqExfs7bTUbdevMnk+trt8Lh5\n3Z7npxsHXdu1uhrOYxjjEkL6g4KLENK14i5LO5M00TcuIkALJ02cYLSlEV0XuGI9aBU4WtgVLT7l\nfIm2aeizRcj4QsFFyJTRr+VBLzVbWRiU4NL1YlnGiLN3SBOMy8vAwoL/utEIU4pxgkvbUDD1SAih\n4CJkyij6oR0X+UkaaxTCIY/g0gLIPG911X5etRpdmWj24br2YvqsZLXjMNOXngeUSsDjj0fHpXgj\nZLyg4CJkm5Kl5kpHf6Rt1tV9g8JmdCrCoxfXef3acYB6PRRd5j1aWvKv3/Oi/ehrljoqXaAv92yQ\nqzNrtewpRUbTCBk+FFxkatkuD5V+nMezrEzU4qvXuRT5XUiESosaz/OFjbw3ry0uMtRuAxsb0X7b\n7Wh61fQbi6sB02RdxDCqhQbb5b8NQsYJCi4yteR5qEzyA2iYc89qn2BS9HdhqzlLsmmIE0C1ml/8\nXi6HTvKbm2HbxUVgZaV73KT55fku+vHXstWNZSGLcCaEFA8FFyGYbMFVBLZokNQjyQNavKtsacYi\nozS2InibU3y1CjSbQKXi1y8t
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 110
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 109
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {}
|
||
|
|
}
|
||
|
|
]
|
||
|
|
}
|