yola/zaoYun/master/MNIST-K-Means-Clustering/Kmeans.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from base64 import b64decode\n",
    "from json import loads\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "# set matplotlib to display all plots inline with the notebook\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse(x):\n",
    "    \"\"\"\n",
    "    to parse the digits file into tuples of \n",
    "    (labelled digit, numpy array of vector representation of digit)\n",
    "    \"\"\"\n",
    "    digit = loads(x)\n",
    "    array = np.fromstring(b64decode(digit[\"data\"]),dtype=np.ubyte)\n",
    "    array = array.astype(np.float64)\n",
    "    return (digit[\"label\"], array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read in the digits file. Digits is a list of 60,000 tuples,\n",
    "# each containing a labelled digit and its vector representation.\n",
    "with open(\"digits.base64.json\",\"r\") as f:\n",
    "    digits = map(parse, f.readlines())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-4-08d5e3e094a6>, line 3)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-4-08d5e3e094a6>\"\u001b[1;36m, line \u001b[1;32m3\u001b[0m\n\u001b[1;33m    validation = digits[:ratio]\u001b[0m\n\u001b[1;37m             ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "# pick a ratio for splitting the digits list into a training and a validation set.\n",
    "ratio = int(len(list(digits)*0.25)\n",
    "validation = digits[:ratio]\n",
    "training = digits[ratio:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def display_digit(digit, labeled = True, title = \"\"):\n",
    "    \"\"\" \n",
    "    graphically displays a 784x1 vector, representing a digit\n",
    "    \"\"\"\n",
    "    if labeled:\n",
    "        digit = digit[1]\n",
    "    image = digit\n",
    "    plt.figure()\n",
    "    fig = plt.imshow(image.reshape(28,28))\n",
    "    fig.set_cmap('gray_r')\n",
    "    fig.axes.get_xaxis().set_visible(False)\n",
    "    fig.axes.get_yaxis().set_visible(False)\n",
    "    if title != \"\":\n",
    "        plt.title(\"Inferred label: \" + str(title))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# writing Lloyd's Algorithm for K-Means clustering.\n",
    "# (This exists in various libraries, but it's good practice to write by hand.)\n",
    "def init_centroids(labelled_data,k):\n",
    "    \"\"\"\n",
    "    randomly pick some k centers from the data as starting values for centroids.\n",
    "    Remove labels.\n",
    "    \"\"\"\n",
    "    return map(lambda x: x[1], random.sample(labelled_data,k))\n",
    "\n",
    "def sum_cluster(labelled_cluster):\n",
    "    \"\"\"\n",
    "    from http://stackoverflow.com/questions/20640396/quickly-summing-numpy-arrays-element-wise\n",
    "    element-wise sums a list of arrays. assumes all datapoints in labelled_cluster are labelled.\n",
    "    \"\"\"\n",
    "    # assumes len(cluster) > 0\n",
    "    sum_ = labelled_cluster[0][1].copy()\n",
    "    for (label,vector) in labelled_cluster[1:]:\n",
    "        sum_ += vector\n",
    "    return sum_\n",
    "\n",
    "def mean_cluster(labelled_cluster):\n",
    "    \"\"\"\n",
    "    computes the mean (i.e. the centroid at the middle) of a list of vectors (a cluster).\n",
    "    take the sum and then divide by the size of the cluster.\n",
    "    assumes all datapoints in labelled_cluster are labelled.\n",
    "    \"\"\"\n",
    "    sum_of_points = sum_cluster(labelled_cluster)\n",
    "    mean_of_points = sum_of_points * (1.0 / len(labelled_cluster))\n",
    "    return mean_of_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def form_clusters(labelled_data, unlabelled_centroids):\n",
    "    \"\"\"\n",
    "    given some data and centroids for the data, allocate each datapoint\n",
    "    to its closest centroid. This forms clusters.\n",
    "    \"\"\"\n",
    "    # enumerate because centroids are arrays which are unhashable,\n",
    "    centroids_indices = range(len(unlabelled_centroids))\n",
    "    \n",
    "    # initialize an empty list for each centroid. The list will contain\n",
    "    # all the datapoints that are closer to that centroid than to any other.\n",
    "    # That list is the cluster of that centroid.\n",
    "    clusters = {c: [] for c in centroids_indices}\n",
    "    \n",
    "    for (label,Xi) in labelled_data:\n",
    "        # for each datapoint, pick the closest centroid.\n",
    "        smallest_distance = float(\"inf\")\n",
    "        for cj_index in centroids_indices:\n",
    "            cj = unlabelled_centroids[cj_index]\n",
    "            distance = np.linalg.norm(Xi - cj)\n",
    "            if distance < smallest_distance:\n",
    "                closest_centroid_index = cj_index\n",
    "                smallest_distance = distance\n",
    "        # allocate that datapoint to the cluster of that centroid.\n",
    "        clusters[closest_centroid_index].append((label,Xi))\n",
    "    return clusters.values()\n",
    "\n",
    "def move_centroids(labelled_clusters):\n",
    "    \"\"\"\n",
    "    returns a list of centroids corresponding to the clusters.\n",
    "    \"\"\"\n",
    "    new_centroids = []\n",
    "    for cluster in labelled_clusters:\n",
    "        new_centroids.append(mean_cluster(cluster))\n",
    "    return new_centroids\n",
    "\n",
    "def repeat_until_convergence(labelled_data, labelled_clusters, unlabelled_centroids):\n",
    "    \"\"\"\n",
    "    form clusters around centroids, then keep moving the centroids\n",
    "    until the moves are no longer significant, i.e. we've found\n",
    "    the best-fitting centroids for the data.\n",
    "    \"\"\"\n",
    "    previous_max_difference = 0\n",
    "    while True:\n",
    "        unlabelled_old_centroids = unlabelled_centroids\n",
    "        unlabelled_centroids = move_centroids(labelled_clusters)\n",
    "        labelled_clusters = form_clusters(labelled_data, unlabelled_centroids)\n",
    "        # we keep old_clusters and clusters so we can get the maximum difference\n",
    "        # between centroid positions every time. we say the centroids have converged\n",
    "        # when the maximum difference between centroid positions is small.   \n",
    "        differences = map(lambda a, b: np.linalg.norm(a-b),unlabelled_old_centroids,unlabelled_centroids)\n",
    "        max_difference = max(differences)\n",
    "        difference_change = abs((max_difference-previous_max_difference)/np.mean([previous_max_difference,max_difference])) * 100\n",
    "        previous_max_difference = max_difference\n",
    "        # difference change is nan once the list of differences is all zeroes.\n",
    "        if np.isnan(difference_change):\n",
    "            break\n",
    "    return labelled_clusters, unlabelled_centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cluster(labelled_data, k):\n",
    "    \"\"\"\n",
    "    runs k-means clustering on the data. It is assumed that the data is labelled.\n",
    "    \"\"\"\n",
    "    centroids = init_centroids(labelled_data, k)\n",
    "    clusters = form_clusters(labelled_data, centroids)\n",
    "    final_clusters, final_centroids = repeat_until_convergence(labelled_data, clusters, centroids)\n",
    "    return final_clusters, final_centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def assign_labels_to_centroids(clusters, centroids):\n",
    "    \"\"\"\n",
    "    Assigns a digit label to each cluster.\n",
    "    Cluster is a list of clusters containing labelled datapoints.\n",
    "    NOTE: this function depends on clusters and centroids being in the same order.\n",
    "    \"\"\"\n",
    "    labelled_centroids = []\n",
    "    for i in range(len(clusters)):\n",
    "        labels = map(lambda x: x[0], clusters[i])\n",
    "        # pick the most common label\n",
    "        most_common = max(set(labels), key=labels.count)\n",
    "        centroid = (most_common, centroids[i])\n",
    "        labelled_centroids.append(centroid)\n",
    "    return labelled_centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify_digit(digit, labelled_centroids):\n",
    "    \"\"\"\n",
    "    given an unlabelled digit represented by a vector and a list of\n",
    "    labelled centroids [(label,vector)], determine the closest centroid\n",
    "    and thus classify the digit.\n",
    "    \"\"\"\n",
    "    mindistance = float(\"inf\")\n",
    "    for (label, centroid) in labelled_centroids:\n",
    "        distance = np.linalg.norm(centroid - digit)\n",
    "        if distance < mindistance:\n",
    "            mindistance = distance\n",
    "            closest_centroid_label = label\n",
    "    return closest_centroid_label\n",
    "\n",
    "def get_error_rate(digits,labelled_centroids):\n",
    "    \"\"\"\n",
    "    classifies a list of labelled digits. returns the error rate.\n",
    "    \"\"\"\n",
    "    classified_incorrect = 0\n",
    "    for (label,digit) in digits:\n",
    "        classified_label = classify_digit(digit, labelled_centroids)\n",
    "        if classified_label != label:\n",
    "            classified_incorrect +=1\n",
    "    error_rate = classified_incorrect / float(len(digits))\n",
    "    return error_rate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "error_rates = {x:None for x in range(5,25)+[100]}\n",
    "for k in range(5,25):\n",
    "    trained_clusters, trained_centroids = cluster(training, k)\n",
    "    labelled_centroids = assign_labels_to_centroids(trained_clusters, trained_centroids)\n",
    "    error_rate = get_error_rate(validation, labelled_centroids)\n",
    "    error_rates[k] = error_rate\n",
    "\n",
    "# Show the error rates\n",
    "x_axis = sorted(error_rates.keys())\n",
    "y_axis = [error_rates[key] for key in x_axis]\n",
    "plt.figure()\n",
    "plt.title(\"Error Rate by Number of Clusters\")\n",
    "plt.scatter(x_axis, y_axis)\n",
    "plt.xlabel(\"Number of Clusters\")\n",
    "plt.ylabel(\"Error Rate\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 16\n",
    "trained_clusters, trained_centroids = cluster(training, k)\n",
    "labelled_centroids = assign_labels_to_centroids(trained_clusters, trained_centroids)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in labelled_centroids:\n",
    "    display_digit(x, title=x[0])"
   ]
  },
  {
   "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}