{ "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 (, line 3)", "output_type": "error", "traceback": [ "\u001b[1;36m File \u001b[1;32m\"\"\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 }