indepth_KMeans.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:52d0366aa82af43633deaad52d9a5b52a4e649150bdccb048354423038a9636c"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<small><i>This notebook was put together by [Jake Vanderplas](http://www.vanderplas.com) for PyCon 2015. Source and license info is on [GitHub](https://github.com/jakevdp/sklearn_pycon2015/).</i></small>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Clustering: K-Means In-Depth"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here we'll explore **K Means Clustering**, which is an unsupervised clustering technique.\n",
      "\n",
      "We'll start with our standard set of initial imports"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import numpy as np\n",
      "import matplotlib.pyplot as plt\n",
      "from scipy import stats\n",
      "\n",
      "# use seaborn plotting defaults\n",
      "import seaborn as sns; sns.set()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Introducing K-Means"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "K Means is an algorithm for **unsupervised clustering**: that is, finding clusters in data based on the data attributes alone (not the labels).\n",
      "\n",
      "K Means is a relatively easy-to-understand algorithm.  It searches for cluster centers which are the mean of the points within them, such that every point is closest to the cluster center it is assigned to.\n",
      "\n",
      "Let's look at how KMeans operates on the simple clusters we looked at previously. To emphasize that this is unsupervised, we'll not plot the colors of the clusters:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.datasets.samples_generator import make_blobs\n",
      "X, y = make_blobs(n_samples=300, centers=4,\n",
      "                  random_state=0, cluster_std=0.60)\n",
      "plt.scatter(X[:, 0], X[:, 1], s=50);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "By eye, it is relatively easy to pick out the four clusters. If you were to perform an exhaustive search for the different segmentations of the data, however, the search space would be exponential in the number of points. Fortunately, there is a well-known *Expectation Maximization (EM)* procedure which scikit-learn implements, so that KMeans can be solved relatively quickly."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.cluster import KMeans\n",
      "est = KMeans(4)  # 4 clusters\n",
      "est.fit(X)\n",
      "y_kmeans = est.predict(X)\n",
      "plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='rainbow');"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The algorithm identifies the four clusters of points in a manner very similar to what we would do by eye!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## The K-Means Algorithm: Expectation Maximization\n",
      "\n",
      "K-Means is an example of an algorithm which uses an *Expectation-Maximization* approach to arrive at the solution.\n",
      "*Expectation-Maximization* is a two-step approach which works as follows:\n",
      "\n",
      "1. Guess some cluster centers\n",
      "2. Repeat until converged\n",
      "\n",
      "   1. Assign points to the nearest cluster center\n",
      "   2. Set the cluster centers to the mean \n",
      "   \n",
      "Let's quickly visualize this process:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from fig_code import plot_kmeans_interactive\n",
      "plot_kmeans_interactive();"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This algorithm will (often) converge to the optimal cluster centers."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### KMeans Caveats\n",
      "\n",
      "The convergence of this algorithm is not guaranteed; for that reason, scikit-learn by default uses a large number of random initializations and finds the best results.\n",
      "\n",
      "Also, the number of clusters must be set beforehand... there are other clustering algorithms for which this requirement may be lifted."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Application of KMeans to Digits\n",
      "\n",
      "For a closer-to-real-world example, let's again take a look at the digits data. Here we'll use KMeans to automatically cluster the data in 64 dimensions, and then look at the cluster centers to see what the algorithm has found."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.datasets import load_digits\n",
      "digits = load_digits()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "est = KMeans(n_clusters=10)\n",
      "clusters = est.fit_predict(digits.data)\n",
      "est.cluster_centers_.shape"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We see ten clusters in 64 dimensions. Let's visualize each of these cluster centers to see what they represent:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "fig = plt.figure(figsize=(8, 3))\n",
      "for i in range(10):\n",
      "    ax = fig.add_subplot(2, 5, 1 + i, xticks=[], yticks=[])\n",
      "    ax.imshow(est.cluster_centers_[i].reshape((8, 8)), cmap=plt.cm.binary)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We see that *even without the labels*, KMeans is able to find clusters whose means are recognizable digits (with apologies to the number 8)!\n",
      "\n",
      "The cluster labels are permuted; let's fix this:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from scipy.stats import mode\n",
      "\n",
      "labels = np.zeros_like(clusters)\n",
      "for i in range(10):\n",
      "    mask = (clusters == i)\n",
      "    labels[mask] = mode(digits.target[mask])[0]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For good measure, let's use our PCA visualization and look at the true cluster labels and K-means cluster labels:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.decomposition import PCA\n",
      "\n",
      "X = PCA(2).fit_transform(digits.data)\n",
      "\n",
      "kwargs = dict(cmap = plt.cm.get_cmap('rainbow', 10),\n",
      "              edgecolor='none', alpha=0.6)\n",
      "fig, ax = plt.subplots(1, 2, figsize=(8, 4))\n",
      "ax[0].scatter(X[:, 0], X[:, 1], c=labels, **kwargs)\n",
      "ax[0].set_title('learned cluster labels')\n",
      "\n",
      "ax[1].scatter(X[:, 0], X[:, 1], c=digits.target, **kwargs)\n",
      "ax[1].set_title('true labels');"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Just for kicks, let's see how accurate our K-Means classifier is **with no label information:**"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.metrics import accuracy_score\n",
      "accuracy_score(digits.target, labels)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "80% \u2013 not bad! Let's check-out the confusion matrix for this:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.metrics import confusion_matrix\n",
      "print(confusion_matrix(digits.target, labels))\n",
      "\n",
      "plt.imshow(confusion_matrix(digits.target, labels),\n",
      "           cmap='Blues', interpolation='nearest')\n",
      "plt.colorbar()\n",
      "plt.grid(False)\n",
      "plt.ylabel('true')\n",
      "plt.xlabel('predicted');"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Again, this is an 80% classification accuracy for an **entirely unsupervised estimator** which knew nothing about the labels."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Example: KMeans for Color Compression\n",
      "\n",
      "One interesting application of clustering is in color image compression. For example, imagine you have an image with millions of colors. In most images, a large number of the colors will be unused, and conversely a large number of pixels will have similar or identical colors.\n",
      "\n",
      "Scikit-learn has a number of images that you can play with, accessed through the datasets module. For example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sklearn.datasets import load_sample_image\n",
      "china = load_sample_image(\"china.jpg\")\n",
      "plt.imshow(china)\n",
      "plt.grid(False);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The image itself is stored in a 3-dimensional array, of size ``(height, width, RGB)``:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "china.shape"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can envision this image as a cloud of points in a 3-dimensional color space. We'll rescale the colors so they lie between 0 and 1, then reshape the array to be a typical scikit-learn input:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "X = (china / 255.0).reshape(-1, 3)\n",
      "print(X.shape)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We now have 273,280 points in 3 dimensions.\n",
      "\n",
      "Our task is to use KMeans to compress the $256^3$ colors into a smaller number (say, 64 colors). Basically, we want to find $N_{color}$ clusters in the data, and create a new image where the true input color is replaced by the color of the closest cluster."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# reduce the size of the image for speed\n",
      "image = china[::3, ::3]\n",
      "n_colors = 64\n",
      "\n",
      "X = (image / 255.0).reshape(-1, 3)\n",
      "    \n",
      "model = KMeans(n_colors)\n",
      "labels = model.fit_predict(X)\n",
      "colors = model.cluster_centers_\n",
      "new_image = colors[labels].reshape(image.shape)\n",
      "new_image = (255 * new_image).astype(np.uint8)\n",
      "\n",
      "# create and plot the new image\n",
      "with sns.axes_style('white'):\n",
      "    plt.figure()\n",
      "    plt.imshow(image)\n",
      "    plt.title('input')\n",
      "\n",
      "    plt.figure()\n",
      "    plt.imshow(new_image)\n",
      "    plt.title('{0} colors'.format(n_colors))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Compare the input and output image: we've reduced the $256^3$ colors to just 64."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}