Kmeans for Number Identification.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import struct\n",
    "import numpy as np\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NearestNeighborClassifier(object):\n",
    "    \"\"\"A generic k-nearest neighbor predictor.\n",
    "\n",
    "    You need to extend this class and implement distance(from, to)\n",
    "    and consensus(label_list) in order to make this functional.\"\"\"\n",
    "    \n",
    "    def __init__(self, dataset, k):\n",
    "        \"\"\"Create a new nearest neighbor classifier.\n",
    "\n",
    "        dataset - a list of data points. Each data point is an (x, y) pair,\n",
    "                  where x is the input and y is the label.\n",
    "        k - the number of neighbors to search for.\"\"\"\n",
    "        # Note how we don't have to do any initialization!\n",
    "        # Once we have a dataset, we can immediately get predictions on new values.\n",
    "        self.dataset = dataset\n",
    "        self.k = k\n",
    "        \n",
    "    def predict(self, point):\n",
    "        \"\"\"Return the k-nearest neighbor prediction for a point.\"\"\"\n",
    "        # Compute distances to every point in the data set.\n",
    "        distances = [self.distance(x[0], point) for x in self.dataset]\n",
    "        \n",
    "        # Naive approach: sort based on distances, take the first k elements.\n",
    "        values = zip(distances, self.dataset)\n",
    "        values.sort(key = lambda val: val[0])\n",
    "        \n",
    "        # Predict by averaging the closets k elements.\n",
    "        prediction = self.consensus([value[1][1] for value in values[0:k]])\n",
    "        return prediction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict(self, point):\n",
    "    # We have to copy the data set list, because once we've located the best\n",
    "    # candidate from it, we don't want to see that candidate again, so we'll delete it.\n",
    "    candidates = self.dataset[:]\n",
    "    \n",
    "    # Loop until we've gotten all the neighbors we want.\n",
    "    neighbors = []\n",
    "    while len(neighbors) < self.k:\n",
    "        # Compute distances to every candidate.\n",
    "        distances = [self.distance(x[0], point) for x in candidates]\n",
    "        \n",
    "        # Find the minimum distance neighbor.\n",
    "        best_distance = min(distances)\n",
    "        index = distances.index(best_distance)\n",
    "        neighbors.append(candidates[index])\n",
    "        \n",
    "        # Remove the neighbor from the candidates list.\n",
    "        del candidates[index]\n",
    "    \n",
    "    # Predict by averaging the closets k elements.\n",
    "    prediction = self.consensus([value[1] for value in neighbors])\n",
    "    return prediction\n",
    "        \n",
    "# Let's go ahead and replace the old implementation.\n",
    "NearestNeighborClassifier.predict = predict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import subprocess\n",
    "\n",
    "def download(url):\n",
    "    \"\"\"Download a GZIP archive, return the data as a byte string.\"\"\"\n",
    "    # Do the download by shelling out to curl.\n",
    "    cmd = 'curl \"%s\" | gzip -d' % url\n",
    "    return subprocess.check_output(cmd, shell=True)\n",
    "\n",
    "def get_files():\n",
    "    \"\"\"Download MNIST files from the internet.\"\"\"\n",
    "    url_format = \"http://yann.lecun.com/exdb/mnist/%s-%s-idx%d-ubyte.gz\"\n",
    "    files = [(\"train\", \"images\", 3), (\"train\", \"labels\", 1),\n",
    "             (\"t10k\", \"images\", 3), (\"t10k\", \"labels\", 1)]\n",
    "    \n",
    "    urls = [url_format % values for values in files]\n",
    "    data = [download(url) for url in urls]\n",
    "    return data\n",
    "\n",
    "data = get_files()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import struct\n",
    "from numpy import *\n",
    "\n",
    "def parse_labels(data):\n",
    "    \"\"\"Parse labels from the binary file.\"\"\"\n",
    "    \n",
    "    # We're going to use the Python 'struct' package. \n",
    "    # This is an incredibly nice package which allows us to specify the format\n",
    "    # our data is in, and then automatically parses the data from the string.\n",
    "    # Let's start by getting the magic number and the length: the first character\n",
    "    # represents the endianness of the data (in our case, '>' for big endian), while\n",
    "    # the next characters are the format string ('2i' for two integers).\n",
    "    magic, n = struct.unpack_from('>2i', data)\n",
    "    assert magic == 2049, \"Wrong magic number: %d\" % magic\n",
    "    \n",
    "    # Next, let's extract the labels.\n",
    "    labels = struct.unpack_from('>%dB' % n, data, offset=8)\n",
    "    return labels\n",
    "    \n",
    "def parse_images(data):\n",
    "    \"\"\"Parse images from the binary file.\"\"\"\n",
    "    \n",
    "    # Parse metadata.\n",
    "    magic, n, rows, cols = struct.unpack_from('>4i', data)\n",
    "    assert magic == 2051, \"Wrong magic number: %d\" % magic\n",
    "    \n",
    "    # Get all the pixel intensity values.\n",
    "    num_pixels = n * rows * cols\n",
    "    pixels = struct.unpack_from('>%dB' % num_pixels, data, offset=16)\n",
    "    \n",
    "    # Convert this data to a NumPy array for ease of use.\n",
    "    pixels = asarray(pixels, dtype=ubyte)\n",
    "    \n",
    "    # Reshape into actual images instead of a 1-D array of pixels.\n",
    "    images = pixels.reshape((n, cols, rows))\n",
    "    return images\n",
    "\n",
    "train_images = parse_images(data[0])\n",
    "train_labels = parse_labels(data[1])\n",
    "test_images = parse_images(data[2])\n",
    "test_labels = parse_labels(data[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAU8AAAEICAYAAADfkHYmAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztnXucjdX6wL+vmcEw4x6GGENKU27JpcYtKURyxq0ikcit\ndOSW0z2FVDIn4xA/FOoUJ4fkJFExCFGRkDEMcmnMGHO/7P38/tjzvs2e69579nWs7+ezPjPvfte7\n9vM+e73Pu9aznrWWJiIoFAqFwj4qeFoAhUKh8EWU8VQoFAoHUMZToVAoHEAZT4VCoXAAZTwVCoXC\nAZTxVCgUCgdQxtOH0DStu6Zp5zwthzvRNG2lpmmz8/7vomnacQ/IoGmatkLTtCRN0/a5+/sV3oky\nnmVE07TTmqZlaJqWqmnaxbyHPcjTcpUVTdMe0jTtJ03TrmmalqBp2nZN08I8KZOI7BSRWzzw1Z2B\n+4AbRaRDwZOapo3UNE00TVtQ4POH8j5fmXfcJO/4ywL5Vmua9kre/1YvSE3TbtM0baumaYmapl3V\nNO1HTdMe0DRtWF6dS82rf+Z8x6nOV4GiIMp4OocHRSQIaAO0BZ73sDxlQtO0m4APgeeA6kAYsAgw\neVIuDxIKnBaRtBLyxAJDNE3zz/fZ48CJIvJ21DTtbhu/exPwNVAfqAs8A1wTkTUiEpRX7/oAf+jH\neZ8pXIwynk5ERC4CX2ExogBomtZX07RDeS24s3oLI++c3hJ5XNO0+LwW3j/ynQ/Ma8kmaZp2FGif\n//s0TbtV07Rv81okv2qa1j/fuZWapkVrmrYlrzUSo2lafU3T3ssr75imaW2LuZU2QJyIfCMWUkRk\nvYjE55XdQdO0PXnfe0HTtPc1TauY77tF07QJmqb9rmlaiqZpr2ua1kzTtN15evhUz6+3tDRNm5V3\n/6c1TRtWlFBFtMpOa5o2VdO0XzRNS9Y07d+aplXOd356nnx/aJr2ZJ5cNxVTdgNN0zbmtfBOapo2\nJu/z0cAy4K48Pb5ajM4uAoeBXnnX1QLuBjYWkfct4I1iyskvUx0sL64PRCQ7L8WIyK7SrlW4HmU8\nnYimaTdiaQWczPdxGjACqAH0BcZrmjagwKWdgVuAe4GXNE27Ne/zl4FmeakXlpaM/l0BWFolW7G0\nSJ4G1mialr9bOwR4AagDZAF7gIN5x+uAd4u5lYNAC03TFmiadk8RbggT8Pe8cu7Kk3tCgTy9gHZA\nJ2A6sBQYDjQCbgceyZe3fl5ZDfPucWmB+yiJIUBvLEamFTASQNO03sAUoCdwE9C9lHI+Ac4BDYBB\nwJuapvUQkeXAOGBPXqvu5RLK+BDLbw3wMPBfLHovSDRws6ZpPUuR6QqWurRa07QBmqbVKyW/wo0o\n4+kcNmialgKcBS5jMXoAiMi3InJYRMwi8gvwMdCtwPWvikiGiPwM/Ay0zvt8CPCGiCSKyFkgKt81\nnYAgYG5ei2Q78AXWRulzEflRRDKBz4FMEflQREzAv7G4GAohIqewGJuGwKdAgpbPl5tX5l4RyRWR\n08CSIu7pLRG5JiK/AkeArSJySkSSgS1FfPeLIpIlIt8Bm/Pu3RaiROQPEUnE8jLRW/1DgBUi8quI\npAOvFFeApmmNgAhghohkishPWFqbI4q7phg+B7prmlY979oPi8mXgaXlObukwsSy8MQ9wGngHeCC\npmnfa5rW3E65FC5AGU/nMEBEgrEYnBZYWlEAaJrWUdO0HZqm/alpWjKWVkydAtdfzPd/OhajCJZW\n0Nl8587k+78BcFZEzAXON8x3fCnf/xlFHBfrG8szjkNE5AagC9AV+EfePd2sadoXmmWA7BrwZhH3\nZM93JxXwJ57Juz9bsFV3+f8vSAMgUURSCsjQsJj8RSIiGVgM/wtAbRGJKSH7MqCepmkPllLmORGZ\nJCLNsPhe0yjeKCvciDKeTiSv1bQSeDvfx2ux+L0aiUh14F+AZmORF7B0c3Ua5/v/D6CRpmkVCpw/\nb6fYpSIi+4H/YOluAywGjgHNRaQaMAvb76koamqaVjXfcWMs91cWLgA35jtuVFzGvO+qpWlacAEZ\nHNGlPtC2uqRMIpINvAq8jo26y+t9LOKv30HhQZTxdD7vAfdpmqZ3vYOxtGoyNU3rADxqR1mfAs9r\nmlYzz5/6dL5zP2BpaU3XNC1A07TuwINYfHdlQtO0zpqmjdE0rW7ecQugP7A3L0swcA1IzTs3vqzf\nCbyqaVpFTdO6AP2Az8pY3qfAqLxBtSrAi8VlzDNKu4E5mqZV1jStFTCaUgxgMXyHJazpnzbk/Qio\njMVnW4i83/1VTdNu0jStQt4A0hP89TsoPIgynk5GRP7E0vp4Ke+jCcBreT7Rl7A81LbyKpbuYxyW\ngaGP8n1PNhZj2QdIwDIIMUJEjpX1HoCrWIzlYc0SM/g/LP68t/LOT8XyEkgBPsDiPy0LF4EkLC3A\nNcC4st6HiGzB4iPegWXQRTc4RQ3ggMVX3CRPhs+Bl0VkmwPfK3lRCok25DVhqRO1ismSnSfTNiwv\nqyNY5B9pr1wK56OpxZAVniSvxbxaRG4sLW8Zv+dWLMankojkuvK7FNcHquWpKLdomvY3TdMqaZpW\nE5gHbFKGU+EslPFUlGeewhI6FoslNtUZvlmFAlDddoVCoXAI1fJUKBQKB1DGU6FQKBxAGU+FQqFw\nAGU8FQqFwgGU8VQoFAoHUMZToVAoHEAZT4VCoXAAZTwVCoXCAZTxVCgUCgdQxlOhUCgcQBlPhUKh\ncABlPBUKhcIBlPFUKBQKB1DGU6FQKBxAGU+FQqFwAH97Mmua5pWLf4pIWXZuLBNKJ4XxVp0ACXlb\nKXsEb9WLqiuFsUUnquWpuJ44U3oWhcI2lPFUKBQKB1DGU6FQKBzALp+no1SoUIHp06czaNAgAO64\n4w7WrVuH2WwGYMmSJTRr1oyNGzcCkJKSQkZGhjtEUyh8jvr169OtWzdee+01AKpXr87Zs2f57bff\nAJg9ezYnTpzwpIjXBarlqVAoFA5g1+6Zjo6MBQcHc/Xq1YJlUfC79TwJCQlcu3aNt99+G4B///vf\nJZbvi6OFVatWxd/f32g9VK1alcDAQB555BEjT1paGr169QLgp59+Ij093ebyfVEnbuBHEbnTU19e\nVr00bNgQgDVr1tC1a9di82VmZjJ48GA2b95sU7nlsa5ERkayfv1643jx4sVMmDDB5utt0YlbjGfl\nypWtbiSvrELG84YbLFEk7dq1AyA1NRWwdEPmz59fbPm+9OP37NkTgA0bNlClShWbr0tOTmbbtm3M\nmjULgN9//73E/L6kk+Lo06cPw4YNo1+/fgBUq1bN6nxWVhbvvfcezz//vK1F+qzx9PPzY8+ePQC0\nb9+eixcvMm3aNAA+//xzWrZsyYoVKwC45ZZbSEtLIzg42Kayy0NdKcixY8e45ZZbij1fmjG1SSci\nYnMCxJXJz89P/Pz8pGrVqvLdd9+JyWQSk8kk+/btK/E6e+7B2cme+2vZsqWkpKRISkqKmM1mh9Lu\n3btl9+7d4u/vXy50UjANHDhQrl69KlevXhWTyWR17+fPn5eff/5ZEhMTJTExUcxms5hMJnnxxRfl\nxRdftKX8A76ql65duxp6+OGHH6Rx48aF8qxYsUJWrFghZrNZ0tLSbC7bV3VSVIqOjpbo6GixhWPH\njsmxY8cc1onyeSoUCoUDuGW03VZMJhNg8fWNHz+ew4cPe1gi51C1alUA3nrrLeN/gEuXLpGTkwPA\n/PnzycnJMSIQCtK+fXtGjx5N69atAahVqxaXL192seTuQXdlzJkzh7Zt21KhguWdfuHCBTZv3mx0\ny9PS0sjMzDR0uHHjRu65554Su2flhWHDhhn/T506lfj4+EJ5OnXqBEBubi4HDx50m2yeIjIy0qg7\nPXr0YPv27YwfPx6A48ePs337dqNrHhkZyZtvvuncuuLJJnZxqVmzZnL58mWJjY2V2NhYmTt3rk93\nOxo3biyNGzeWK1euyLlz5+TcuXOyadMmqVq1qs06qV+/vkyePFnOnz8v58+fl8WLFxtuDl/UiZ4W\nLVok6enpkp6eLmazWU6fPi2PP/64PP7441K5cuUir3nuuefkueeek9zcXDGbzfLMM8/IM888Y8v3\n+Wy3/erVq0a3vW3btoXOT548WXJzcyU3N1f2799vV9m+qpPIyEgpjuK643pXXc+juu0KhULhZryi\n2z558mQeffRRwsPDAfD390fTNObMmQPAggULPClemUlKSgLg8ccfZ9euXQCFQreK4+677wZg5cqV\nVK9enUqVKgHw/fffu0BS93PPPfcQHR0NwPLly4mLiyMzM7PY/HPmzGHy5MmAZfLFwYMHWbp0qVtk\ndScVK1bk66+/BqB169Yljpz7+fnxzDPPGO6Of/3rX26R0ZPo3XAdvZuud9uLu8apuKOJHRISIh07\ndpTg4GAJDg4WQCpWrCiNGjWSRo0aSceOHeX06dNy5coVuXLlikyfPl2qVKlS7rsdpaXRo0fLn3/+\nKX/++afRZZs+fbpMnz79utJJUFCQBAUFyZw5cyQ3N1dSU1MlNTVVoqOjpUGDBvaU5TPd9rFjxxYb\ncfHaa69Z5V25cqWYzWbZsmWLbNmyxW79+opO8qeCXfbiut96KmoEvqw6cWmcpz4d81//+hc1a9bk\n/PnzgGX6ZeXKlalduzZgCaI3mUxMmTIFgPfff9+er0F8JE6tR48efPrpp8We/+WXX2jVqpVxHBQU\nRMWKFY3jFStW8MILLwCWwZSS8BWdlEaXLl1YsmQJAC1atCAzM5PRo0cD8PHHH9tbnM/EedaoUcOI\n62zevDmapqFplp80IyODHj16GHl3795NQkIC7du3ByhyMKkkfLWuFIzl1PVTMA9g5Dt+/DgAs2bN\n4j//+U+xZduiE+XzVCgUCkdwZRP7l19+kV9++cUIds+f9ABnk8kk58+flxYtWjjcrfOVbsecOXPs\nDopPTk6W5ORkueeeeyQgIKDc6aSoVKFCBalQoYKMGzdO0tLSDF0cOnRImjVrVpayfabbXjD16NHD\nKiohLS3NSNnZ2dK1a9dy//wUTPqouU5kZKRxrqhuev7zztCJy260S5cukp2dLdnZ2WI2myU1NdXw\naebm5oqIGA9Fnz59yvSw+cqPP2jQILuNpx62U151kj9VqFBB6tSpIzt37pSdO3caOoiJiZGYmBip\nWLFimeoJPmw8AenXr5/069dPMjIyrOrIpEmTrovnp6hk64yi0nyijujEpTeq/9iPP/64NG3a1Ph8\n8ODBcvLkSaPlmZSUJOHh4eX+x2/atKkkJSVJUlKSUfH12LzMzEzJyMiQBQsWyIIFC2TdunUiIsaA\nUVhYWLnUCSCdOnWSTp06yZ49e0p8kcTHx8s//vGPsjxsPm08e/bsKT179jRan3oKCQkpU7m+rJN8\n91AkkZGRdrU47dGJ8nkqFAqFA7hlVaWiqF+/vrF4a7Vq1Vi4cKEx2m4v4kOjhWPGjAHgxhtvBDCm\n0f33v/+1yjdp0iSioqL48ccfARgxYoShL1vwFZ3s3LmTiIgIq8/0GNiTJ09St25dQkNDAfSWCuPG\njQNwJL7TZ0bbC1KxYkXj9w8LC7M6Fx8fz1133VVqBEZx+EpdKUjBZefA9tH00rBJJ55oYuspPDxc\nwsPDJSUlRdLT043um73llIduR8F0++23F/J9lkednDlzRjIzMyUzM1P27NkjEyZMkICAAGNwzM/P\nTwIDAyUwMFCOHTsmZrNZ5syZI3PmzHFErz7bbY+JiTHqQkZGhqxbt86qfowfP15q1qwpNWvWvC6e\nn+L8nPqUS0e66vbqxKMzjI4ePQrAtWvXqF+/Pk899RQAe/fu9aRYHqVNmzaAZUYRwLJlywC4cuWK\np0RyKeHh4QQEBABFz7oymUzGliz6LJuLFy+6T0AvYNy4cbRv397Qw6BBg9i7dy+5ubkADBkyhEWL\nFnHTTTcB8Nxzz3lMVldTXNymfuzORWKUz1OhUCgcwCvmtuscOHDA0yI4BT8/PwCio6Np3Lgxffr0\nsfm6Bx54AIA6deoAf/m3fv31VxdI6nnS0tJKzfPOO+8AFj95VlZWqduylBf0bTf++c9/4ufnZ8wu\n27JlC4Ax0+rBBx8kMDDQ8KcvX77c6NWVB/Q56UX5N1u0aAGguwCMlmhZ/J224jTjefvtt9O+fXtW\nrVoFWBZt0LsVRVGhQgVjXUZ9QYPyRqVKlbj33nuNaXZ/+9vfSuxyBgQEMHbsWAAaNGgAYGytEBcX\n52JpvZNatWrx6KOPApbpd6+++up1022fOXMmYHmpmkwm9u/fb3Vef/F07dqV/fv3ExQUBMCLL75o\ntReWr5N/ARCdgQMH8p///MfoxuvoxtQdlNl41q9fH7CMmlarVo1Ro0YBlpbT6dOnAdi1axfffPMN\nd911F2BZ2Dc0NNQ4BsjOzuabb74pqzhegd7yTE1NJTU1lY4dOwLw+uuvWy1Su3r1agYOHAjAK6+8\nQkBAACEhIYBlE6/333+fL7/80s3Sew+1a9dm37591KtXD4A//viDqKgoD0vlPkaOHGn87+fnZ2zN\nnZ2dzb59+/j5558BjLECHd33WR7QW5Rg3dIES88uv49z8eLFbpWtfDb5FAqFwtWUNaygRYsW0qJF\niyLnr5eU8s9tN5lMMm/ePJeGFXgi1KJq1apy4sSJYmfMJCUlGTOMCp7bt2+f3bOKfEEntiR9bvve\nvXuNjd/Onz8vPXr0KFO5+FioUt++faVv375y6dIlu6b0bt68udzUlYLoM4bKOnfdGTopc7c9NjYW\ngDfeeIPmzZsby9CV5sfMyspiw4YNACxZsqTcLO6bH39/f44ePVpsN6p69epWx3FxcUZQ/AcffHBd\n+jkrVKjAwoULAejQoQMAw4cPB2DHjh0ek8sT6Puu33LLLbRo0YIBAwYAlsXDK1WqxA8//ADA5cuX\nueeeewwXjz6JoDxw/Phxq655wUEjncWLF7tlkCg/qtuuUCgUjuDO7pirkrd2OypUqCBhYWHywQcf\nyAcffCDbt28vsbvlhFWDvF4nJaWAgADZsmWLoY/s7GyZOnWqM+uKT3Xbr/fnB4rf5O3YsWMSHR3t\nUZ14bG67MxEfnZvrSnxJJ/qWuWvWrCEsLMzYgnrkyJGsWbPGmaL57Nx2V+JLdcVd2KITZTzLiNJJ\nYbxVJyjjWSSqrhTGFp0on6dCoVA4gDKeCoVC4QD2hiolAGdcIUgZCPXw9yudFMYbdQJKL0WhdFIY\nm3Ril89ToVAoFBZUt12hUCgcQBlPhUKhcABlPBUKhcIBlPFUKBQKB1DGU6FQKBxAGU+FQqFwALvi\nPH15KpWrUDopjLfqBEgQkRs89eXeqhdVVwqjpmcqFNZ4WzC2wodRxlOhUCgcQBlPhUKhcACP7tv+\n9ttvA/Dcc8+RmZnJ4MGDAfjiiy949NFHjV0Bu3Xr5jEZFQpvJywsjGHDhhEeHg7A/PnzOXTokIel\nKv+olqdCoVA4gMdanpMmTeKZZ54BQESoVKkSTz75JGBpeSYlJXHnnR5bt9YtBAYG8uabbwLQuHFj\nAFq2bAlAxYoVqV27Nlu3bgXgtddeM/bpLu9EREQAlhXmt2zZwtGjR4vNGx4eTp8+fQAYMmQI7du3\nB2DLli307dvX9cJ6iLp16zJ+/HgAXn75ZfIv8DN06FDCwsKIj4/3lHhOpXfv3gA0adKE2rVrA1C5\ncmUefPBBKlWqBMCvv/7K+vXr+fjjj90ml0dWkg8NDeXIkSNUrVoVAJPJxHfffWfspvn+++8TFBTE\nf//7XwDuv/9+Y2uGovDVUIvo6Gibdzo0mUwMGDDA2FGxNHxVJ5988gn3338/YNld9PLly3Tt2tUq\nj24gX3zxRWrVqkWdOnWKLMvPz6/gRz69krz+vERFRREREUHz5s0ByM3NJSMjg+DgYCPvpUuXeO21\n1wD4z3/+w+XLl4st19vqir+/pU03depUhg4dym233QZYfs+srCwjX36b4O/vT0BAAA8++CBgeXmW\nBVt04taWp9662r9/P1WrVuXatWuA5WH4/fffrfKmpqZy8eJFAB599FE++ugjd4rqcgIDA3nggQds\nzu/n50e/fv1sNp6+SEREBPfff7/Vlsx169bl+PHjABT1otc0rcjP9+/f7zpBPUD37t3ZuHEj8JcR\n1evCxIkTycrKYsyYMYCll1K/fn0WLVoEwIABA4zWmy8wefJkwLKdeXJyMlFRUQCcOHGCTz/9FLC0\nPHX7AHDrrbfy66+/Gi1Rd6B8ngqFQuEAbmt5+vv7889//hOAOnXqkJmZyd133w1QqNUJUKVKFe67\n7z4AAgICyl3Lc9++fUZLHCA9PZ2NGzfy66+/Gp81bNiQ4cOHAxAUFMSwYcOYM2cOQLnxZ+XniSee\nsGp12svVq1f5/vvvARgxYoSzxPIYdevWBWDlypVWLccLFy7w/PPP8+GHH1rlz87OBiyt8aysLCpU\nsLSN7r//fmN8QW/FeTPz588H4KOPPmLGjBlWLcziuPfee10tViHcZjwfeOABwx9hMpkYNWpUiQMB\nERERhnN4/fr1bpHRHYSGWlb4b9asmdXnL730Eu+++26h/Lqx3LdvH/Xq1WPq1KkAxsNQHpgxYwYA\no0aNKrILXhr/93//B8CKFSvYvXu3U2XzFJUrV2bHjh0AtGjRAhFh5cqVALz++uucPn260DV6l3X9\n+vV8++23PProo4Bl4O2FF14AfMN4Xrp0CYBVq1aVajiDgoIAy8tS09zrulXddoVCoXAEEbE5AeJo\nOnjwoJjNZjGbzRIZGVli3p49e8qVK1fk9OnTcvr06VLLtucenJ3s0UGFChVkxYoVsmLFCjGbzZKT\nkyNRUVESFRUlfn5+JV67dOlSMZvNsmXLFtmyZYvkjVL6vE4aNmwoJ06ckBMnToiIGHUkf9LRj2Ni\nYiQmJkb69u1rbz084O16admypbRs2VLi4+PFZDKJyWSSI0eOSK9evex+5pYuXSpLly41yjGZTD5d\nVwqmwMBA2bNnj+zZs0dMJpNkZGRIu3btpF27dg6XaY9O3Haj586dM260uAd/zJgxMmbMGDl06JBc\nvXpVQkJCJCQkxCk36g0/focOHQwDYDKZZNSoUTZf26RJEzGbzfLHH3/IH3/8Uaqx9RWdjB071niw\ndb0UTPl1ZjKZpHv37tK9e3dH6qFXG8+WLVvKvn37ZN++fWI2myU5OVmSk5PlzjvvdOiZ6927t/Tu\n3btcGs977rlHDh06ZHVvubm5snnzZtm8ebMMHz5cBg0aZLMNcUQnbrnRtm3bSnZ2tixcuFAWLlxo\nfB4UFCRBQUESFhYm8+bNk+zsbMnOzpYff/xRmjZt6tQb9YYfPzo62jAEZ8+etUuHlStXluPHjxvX\nBwQE+LROIiMjJTIyUtLT0+02nkePHpWjR486Uhe92nhOmzbNuNfk5GSjFeroc6cbz/yteF+sK/nT\nfffdJ/fdd5+kpqYWWU+Kqj8mk0k2bdpk10vIFtmVz1OhUCgcwC2j7cnJyaSmphpTEcEySrZv3z7A\nMpqYmppKUlISANOmTePUqVPuEM0tVKxYEcCYfgrQq1cvu8rIzMzk6tWrJc608iWaNGkCFDkLqFT0\nSIWFCxcaAdW+zoABA3jllVf01hidO3fm8OHDZSozMjISwCizPNCxY0fAMskEMKYv69EEOt26dSMi\nIsKYndS3b1969uzJV199BVj0XVbcNj1z7dq1xqyPYcOGcccdd+Qvl9TUVGO6mS1xXfkRL5teVpCw\nsDAAYmNjyczMBKBp06Z23WedOnWIjY3lu+++A6B///4l5vd2negsXLiQSZMm6dcVetC//PJLI16x\nqFkydhpfr5ueqc8W+uWXX2jSpAm7du0CnLOSWExMDGAJVdIpSl++UlcAYyruhAkT2LVrF9u3b7fp\nuqioKJ566ikCAgIASziXvopbUdikE1f6J/TUunVrOXz4sJXvJScnRz777DP57LPPpEmTJtKwYUOH\nfTve7rN57LHH5LHHHhOz2Sx79+6VvXv32n2PgwcPFrPZLBs3bpSNGzf6vE6KSv369ZPWrVsXe/7Y\nsWNWdWjz5s32fofX+TxHjRolo0aNMnxzbdq0kTZt2jj8LOipcePGkpWVJVlZWWIymWTWrFkya9as\nclNXHEkRERFGBE96eroMHjxYBg8e7LBOlM9ToVAoHMClPk/dN7Vjxw5q1KhhdW7Lli0lNpvLE/ln\nE+nddnuZPXu2s8TxWr744osSz+drrQBFd+N9DX12lIiwe/dufvrppzKXWb16dasZSLt377Yab7he\niYmJYd26dQD8/e9/54knngDgs88+c6g8lxrPl19+GYAaNWpw6dIlli9fDlim47Vq1Yp69eoBf03H\nKq9UrlzZ+N/eqaYNGzYELD5SwFi2T1E+0F8GImI82I6iz4XX/aZ//vknYJm2qrDwzjvvABbjGRIS\nUqay3NLyzMnJ4bXXXmPx4sUAJCYmMnfuXGMA6Y477iAhIcGVongNOTk5Nudt2LAhe/bsASyO/u3b\nt7t1sVdX0LBhQzZv3my1KIpOjx49imx56fOx9ReITklrVPoiv/32m8PXPvnkk0brsnbt2uTk5BiL\no+gjzAqMBaTBMoBbFpTPU6FQKBzAZS3PwMBA2rZtC1haCHqrE+Ddd99F0zTmzp0LwNixY68bn4we\nouXn51dkzKYeunLDDTcwffp0brzxRuPcxx9/TEZGhnsEdRE7duwotKKUzrZt27j33nsLbTeihzLp\nXVy9xdmjRw8XSur9dO/eHbAs4daqVStjBfbNmzczceJEzp4960HpnIe+clLNmjUdvqfAwECGDh1q\ntMY1TStzz8VlxjM7O5tz584BltisWrVqkZiYaJx/5513jPjH4cOHl2vjmX/tzfyB8q+//rpRGYYM\nGUL37t2NfXcaNWpkFfd44cIFvv76azdK7RqaN29uNeiTn9q1axMWFmYYz7FjxzJ16tRCS41dvXoV\nKFs311vQ1+CsWLEiDz30ECdOnAAgLi7O8JXrvjk9trdjx47069fPMCoAGRkZvPTSSwDMmzfPbfK7\ng2XLlgGMKRn/AAAgAElEQVTQp08fLly4AFhepPv27TPcWmCZjKNv06H7f0eOHAlA/fr1adSokZH3\n3LlzTJs2rUxyuTRIXl+LcsaMGWRlZRmzAT744AMGDRpkrO8ZGBhod9B4fsTLg3z1GUYFR9pTU1NJ\nS0sDLD92UesR6r7gtm3bcv78eZvl8ladLFu2jFGjRhV3HefOnTN00rRpU/z9/Q29iAiZmZk8/vjj\nAI4MsHhdkHy/fv0A+Pe//201sLh3714jQqVFixb69YBFDxkZGcbz8tZbb7F169Yi1/i0BW+tKzp6\nD3bRokW0atUKsOggICDACHrXP9PtmT6xIv+5jIwMVq1aBVjWz83fmCuILTpRPk+FQqFwAJe2PPVu\nxdKlSxkwYIDVmzU///73v3nkkUfsKdoKb39z6i2Gu+++m507d9pUrt5SnzBhAoBdrU7wXp1ERESw\ncePGQnG/edcV2aXX9ZeRkcGwYcPKEq7ldS1PnQEDBvD2228brqyCukhISDC2q1m3bh3btm3jyJEj\nTpHLW+tKabRr186Yo56WlkZiYqKxev7nn39uNT5w7do1PvnkE5vLtkUnbpvbHh4ebsQ43nLLLVbn\npk6dWuQWFLbiKz9+8+bNjbm4evxmQeLi4gB47733jD2fHMGbdXLnnXca++80a9bMGOgoynhevnyZ\nzp07A5Ytds+cOVMW0bzWeIJlsPCGG24o8lxycrKxcI6z8ea64ilUt12hUChchNtanq7El96cwcHB\ngKVlWb16dVq2bAnA4cOH2bRpk7EvdVlDknxFJ2PGjDFGPW+66Sarlufly5fp0aOHM0fVvbrl6Sl8\npa64E6/qtrsS9eMXRumkSJTxLAJVVwqjuu0KhULhIpTxVCgUCgdQxlOhUCgcwN7pmQlAmWJFXECo\nh79f6aQw3qgTUHopCqWTwtikE7sGjBQKhUJhQXXbFQqFwgGU8VQoFAoHUMZToVAoHEAZT4VCoXAA\nZTwVCoXCAZTxVCgUCgewK87Tl+ehugqlk8J4q06ABBEpes03N+CtelF1pTBqbrtCYY23BWMrfBhl\nPBUKhcIBlPFUKBQKB1DGU6FQKBxAGU+FQqFwAHtXVVI4iYCAANq2bUt0dDQAVapUAeDbb78FIDo6\n2mm7I3oblStXJioqqtDn/fr1Iz4+nl9++cX4LDo6mmPHjgGQnZ2N2Wx2m5wK3+fpp58GICoqigsX\nLtCoUSMATCZT2QvXN4q3JQHizjR8+HAZPny45ObmyqFDh+TQoUNF5rPnHpyd7L2nypUrS+XKlWXV\nqlViNpvFZDKJyWSSS5cuydWrV8VsNovZbJbk5GRp3bq1w7rzZp088cQTxn3ak3bs2CGhoaFlqVMH\nvFkvBVPbtm2lbdu20qtXL3n22Wflhx9+kB9++EFERI4fPy4bNmyQDRs2SN26dcv0nPmSTuxNly5d\nkkuXLonZbJaDBw9KhQoVpEKFCk7RiVtutE+fPnZf8/jjj0tubq7k5uaK2WyW2NhYiY2N9fkf//PP\nP5fPP/9ckpKSZOHChRIeHi7h4eECSJUqVWTChAkyYcIEERH58ccfy+UDob849KS/QNLT0wsl/ffX\n0/vvvy/+/v7i7+/viF683nj6+fmJn5+fzJw50+rBLymNHTvWUX14fV0pSzp06JBRt0wmk9x3331O\n1YnyeSoUCoUjuPItsXr1alm9erVkZ2fL77//LiEhIRISElLqdUFBQXLixAmrt2tUVJRERUX59Juz\nbt26Rovq5ptvLjHv119/LSaTyaplak/yZp0MGDBAsrKyJCsrSzIyMmTNmjWyZs2aIvOOHDlSPvvs\nM/nss8+MunDffffZ1YrIl7y65RkYGCh79uyRPXv22OXOOHHihMTFxcmUKVNkypQpEhAQUG7qSlnS\n2bNnDR0dPXrU6Tpx2Y2uXr3aaC6bzWa5evWqNG/eXJo3b17sNdWrV5fq1avLTz/9ZFU5YmNjjXPX\ny48/ffp0MZvN0rp1a4d8n96uk169ekmvXr2kbdu2peYNDQ2V0NBQSUxMFLPZLDt37pSdO3c6olev\nNp7Dhg0zXipFGckVK1bIihUrZO/evbJ161a5cOGCXLhwoVC+xx57rFzVFUdSx44dJTMz09DJl19+\n6XSdqG67QqFQOIDTQ5VatmwJwMCBA9G0v+bWjxgxgt9//73Ea+vVqwdAq1atAMjJyQHgzjvvJDk5\n2dmi+gS6Ln7++WcPS+JcvvrqK5vznjljmZJ+9epVatSo4SqRPE5UVBQBAQHGcWpqKgArV67k0KFD\nrFq1CsAI19q3bx/w13Oj89577/HRRx+5Q2SvQ9fFN998Q8WKFTl06BAAgwYNcvp3OdV4tmzZku+/\n/x6ASpUqce3aNQBWr17N1q1bS7y2Ro0arF692jg2mUzMnDkTgKSkJGeK6RPUqVPH0yIo3EhgYCB+\nfn7GcUJCAi1atAAgMTGxyGtCQ0PdIpsvMXHiROCvuOlPPvkEgPT0dKd/l9OM5+233873339P9erV\njc/0N+XkyZNLvX758uXceeedxvHSpUtZsGCBs8TzGfQg3ilTpnDlyhXjZXQ9ExERAUD9+vU9LInr\nqFq1KhUq/OVFy8rKIjAwsNj89evXL/H89cgjjzzCrFmzjONPPvmEd99912Xfp3yeCoVC4QBlbnmG\nh4cDsGvXLqpVq2Z8vnr1ambMmGGVt0+fPgDUqlUL+Ks7UqdOHR544AEjn8lkYu/evWUVzSvx97eo\n/I477uDAgQNW0w0DAgIM14WI8N577xn+vuuZu+66C7BM6wT4v//7P0+K4xISEhIMHz9Aw4YN2bBh\nAwCdOnWymk5488038/e//52goKAiy9J9pdcT/v7+DBkyxGi9X7t2jRkzZjhnGmYxaHnhArZlLmLV\nZ30gp1q1auQvKz4+vpDgN954IwAVK1ZERIzKYjKZjAcD4OTJk9x88802yyU+tBJ2mzZtADh48CBn\nzpxh/fr1gKXb1r9/f2rXrg3As88+y7/+9S+H5fIlnZREp06dDB2FhISwc+dO+vXrB0BKSoq9xf0o\nIneWns01lKaXn376yRggzE9cXBxms5mTJ08CcM8991CxYsViy+nQoQMHDhywWa7yUFeioqKYNGkS\nWVlZAIwaNcrwdzqCTTopa0zW1atXreZklyWlpKRISkqKNGrUqNzGqdWtW1fq1q0rP//8c6Gph/Hx\n8dK7d2/p3bt3mePcfEknxaVatWpJfHy8oZ+0tDSHJgzkS14d51m1alX59ddf5ddffy3Tc7Rq1arr\npq7o8d9paWliNpvl+PHjcvz4cbc8P8rnqVAoFA5QZp+n7o/avHmz1WhhUSxatAiAc+fO0apVq0I+\nUT027ezZs2UVy2u5fPkyAK1bt2bu3LlMnz7dOJeUlFRqLOz1QM2aNQH43//+Z7h6ADZt2sTRo0c9\nJZbLSUtLo3PnzgC88cYbRozi8OHDiYiIICMjA4Ann3ySli1b0qFDBwB69uxpVY7u1ijvBAYGcvr0\naeP/uLg4Onbs6D4BPNEdA2TMmDFGN0NEJDk5WZo0aSJNmjS5rrqoercjJiZGTCaT4bp49tln7Z6j\nXF508vTTT8vTTz9t1I9Tp07JqVOnJCgoqKz1zqu77aWlli1bSsuWLY3jyZMny+TJkwt12w8ePHhd\n1JU333zTuOfjx49LnTp1ylo/7NKJW3/8/Om3336z+sGjo6OvS0ORPw0ZMkQSExONOdzffPONVKxY\nUSpWrHhd6URft9JsNktqaqo89NBD8tBDDxWb//bbb5fbb79dKleuXFrZPm08CyZ9gZSCxjMnJ8fp\ny695m07atGljNXd98uTJTtWtLbIrn6dCoVA4gifenFWqVJHY2Firt+W4ceNc+pbwtjdncSk4OFiC\ng4Nl06ZNpS7FVx51MnbsWKuVhcaPH19s3tGjR8vHH38sqampkpqaKgcPHiytpV6uWp41a9aUmjVr\nFjniHhkZWS7rSp06daROnTpGFMauXbtk165dZVoM2lGdeGQPo48++oiwsDDjOCUlhe3bt3tCFK9D\nj1186KGHiI2NNSYWXC+MGDHCanGMK1euGP83bdqUwYMHG/OXGzRoQIUKFYx9nwYPHkx2drZb5fUk\n+RfeseecL7NkyRLAEjOelpZG//79AcjNzXW7LG41nnpgb7t27aw+T0hI4MSJE+4Uxevp3LkzoaGh\nvPPOO54Wxe3oD/61a9fIzMw0Zl0NHDiQSpUqWeX99ttvGTlyJGBtaK8H9BftyZMnuemmm6zO5bXq\nyhWzZ8/moYceAiAjI4OHHnqo2EVT3IHyeSoUCoUDuLXlOXjwYAAaN24MYCxZ17dvX3eK4dXoq1It\nW7aM5ORkq2X6rhf0VlNwcDDr1q0z1gPQSUhIAKB79+4cP37cpfOXvRl9evOff/5ZqOVZnrrtrVu3\nBmDSpEnGfa1du9bjrj63Gs8ff/wRsCwIIiK88cYbAMa+3NcTb731VqFFbOvWrcvdd99tHHft2rXc\nLYJsL/kNZ1JSEnPmzDEmW+hB44ryi7+/v+HTrlatGrt27QJgzJgxHpTKguq2KxQKhQO4teWptzDV\nKunw3XffER4ezpAhQwCoXbs2CQkJrFmzBoAZM2Y4smqQz9O9e3ejRzJt2jS+//57vvjiC8CyvYQn\nRlUVnkXvYZjNZkaNGuVhaf6izEvSeQNSDpbUcjZKJ0Xi1UvSOUpkZCQLFiww1tMNCAggIiLCZpeP\nqiuFsUUnyniWEaWTwnirTiinxrOsqLpSGFt0onyeCoVC4QDKeCoUCoUD2DtglAB426Y6oR7+fqWT\nwnijTkDppSiUTgpjk07s8nkqFAqFwoLqtisUCoUDKOOpUCgUDqCMp0KhUDiAMp4KhULhAMp4KhQK\nhQMo46lQKBQOYFecpy9PpXIVSieF8VadAAkicoOnvtxb9aLqSmHU9EyFwhpvC8ZW+DDKeCoUCoUD\nKOOpUCgUDuCRrYcVCoXj9O7dm7CwMGOvp65du/Lwww8bWzJv2bKF06dPe1DC6wPV8lQoFAoHUIsh\nlxFn6mTAgAGcPXsW+GuzvJLQ93SfOHEiGzduNLb0gPKjk9LIv2Fefvbv32/sLpkPn14MOSYmBoDb\nbruNatWqGS1PTdMQEWNnyaeeeooPPvjA5nKvl7piDzbpRERsToC4Is2bN09ERM6cOSNnzpyx+3p7\n7sHZqSz3Xa9ePRk9erSMHj1aYmNjJTc3V7KzsyU7O1vS0tLknXfekYYNG0rDhg2Na9q0aSNt2rSR\n+Ph4MZlMYjKZZP369VK1atVyoZPSUvfu3WX27Nkye/Zs+eWXX8RsNht6yJ969uxZ1PUHfFUvvXv3\nFh2z2Vxquh6eH1cmm2R35Y1OmDBBJkyYILm5uTJx4sRC5xs0aCANGjSQ9PR0SU9Plx49ekiPHj1c\ncqPe9uPfd999Eh8fX+pDkJqaKqmpqfLQQw/Jk08+KVlZWZKVlSVms1nmzZsn8+bNk4CAgHKhk6LS\nypUr5fz583L+/Hk5d+6cZGRkWBnJ4oxnampqUeX5pPHs3bu3XL161agTBe87/2f6/3PmzCnXz09p\nKTAwsNBnAQEBUrVq1SKTIzpRPk+FQqFwAJeNtg8YMICoqCgAPv/8c6KjowvlqV69OgCVK1dm3759\nbN++3VXieB2dO3fmxhtvNI6/+OILdu3aZWzPPHz4cAYNGkSVKlUAiw4BY+vdSZMmsXTpUqvPygvz\n5s0DYMKECQQGBlKhguUdn9dSKcRPP/0EwJEjR2jZsiUAcXFxbpDUPYwYMYJq1aoZPk2d/McF/x8y\nZIjhA7948SIRERHuEdZDRERE8MQTT/D7778D8MILL/D666/Tv39/I09oaCgNGjQo8nq9jtmDy4zn\n9OnTSUpKAmDMmDHFVnydU6dOuUoUn+CJJ54gISHBON64cSNRUVFMmjTJ+Cw3N5eRI0cCsHbtWneL\n6HI2bNhgVdl1dMNgNpvJyMgwBtU2bdrEjBkz3CqjO5kzZw4ADz/8sNXzIyLExcUZL5lu3brxyCOP\nGHoSEatQptq1a9OrVy8AvvrqK3fegkupVasWr776KgBjx44lICDAOJeamsqDDz7Id999B8Att9zC\nxYsXOX78uNO+X3XbFQqFwhGc7dwdOHCgDBw4UMxms+zZs0f27NlTbF59QMlsNkv//v0ddg77osO7\nU6dOkpqaKjrLly+3Oh8aGipJSUnGIEBWVpY88sgj5VInU6ZMkSlTphQa/Ll06ZKcPXtWTp48KSdP\nnpTHHnusrAMJPjNgNH78eOO3FxHjr/5/UdfExsZKbGxskQOPq1evltWrV/t8XdFTgwYN5JtvvpHE\nxERJTEyU5557Tt566y0jNWjQoEx1xRbZnd5tz990Lq2LoHclALKyspwtilezd+9ePvroI5566ikA\nBg8ezD//+U9OnjwJWOIUq1evTnZ2NgCjR4/m448/9pi8rmLIkCHMnTu3yHMLFy7k3XffJTMz081S\neZ58xsU41l1bene9IPfeey8A27Zto2nTpsb1mqbxyCOPABZfui+j+/kfe+wx9u7dS/v27QGIjY11\nvzDOfkvMnz9f5s+fL2azWfr27St9+/YtNm9MTIzExMSI2WyWXr16ufQt4W1vTrC0PjMzMyUzM1PM\nZrP89ttvcvr0aTl9+rTRYhgxYoSMGDGi3Omkd+/eRghOSWFHFy5cMFpUjuihQPL6lqeul6Jaj3Pm\nzLE5BKm40LeYmBifqyt6Wrx4sXEfUVFR4ufnV9b6UKbnR/k8FQqFwgGc3m2//fbbjf9Lm2IYGhpq\n/F+nTh1ni+L17N271xgtXrBgAbfccovV+XfffbdcjqoD1KhRA4Dg4OAS89WtW9cYRV6+fDn9+/c3\nIhAuXrzoWiE9wAsvvGD8n9cyQ9M0Vq9ezfPPP29zOWvXrjW66vr0zfxl+iLXrl0z5O/YsSONGzc2\n3H3Xrl0jNTXVrfI43XiuW7cOsPgz9fm1s2bN4tSpU7Rp08bIFxkZaTxAAMuWLWPBggWAxdf1xhtv\nOFs0r0SPdS3IsWPHmDp1qpulcR+ffPIJAA0aNOAf//gHAL/99hsnT56ka9eugCX+t1atWlSqVAkA\nPz8/IiMjqVWrFgA9evTwgOSuY/z48VZz9fWXRkpKCmvWrLGrrF27dvHoo48WKqtgrKgvMWPGDMxm\nMwCTJ08mNjbWMJ7JyckkJiaybNkywOIbdbkxdbZ/okWLFtKiRQtJSUkx/BPZ2dlWI8f6tMOUlBQj\nX2pqqtx6661y6623ljv/XnFp3LhxolPQN5WYmOhyn4036qRgateunWzbtk22bdtm+EGvXLkiV65c\nkfDwcHvL82qf57hx44r0/+7atcuhulVUWUWNLXizTkpKgwcPNqYob968WY4ePWrYFBGRAwcOSEhI\niISEhLjk+VE+T4VCoXAEV70lIiIiJDo6WqKjo2X9+vXy4Ycfyptvvilvvvmm3HnnnRISEiJdunSR\nLl26iNlslmvXrl1XrayhQ4dKTk6OVUtz0qRJkpSUZLTSN23aJP7+/uLv739d6KS4VLt2baldu7Yk\nJydbjcSvWrXK3rK8uuWZP7aztBHyolJYWJiEhYXJuHHjrK5PTk6WXr16FRvR4s06sTfVqVNH6tSp\nI6+//rqYzWYZN26cjBs3ziXPj8umZ8bExBjrDxaHPn3z0qVL1KhRg7CwMKB8zUsuSPPmzQGLX9fP\nz89Yc/Lpp59mzZo1hn9v/vz59O3b1/AL55+6eb2RkZEBWOpJUFCQh6VxHfkMikODPHrc9KJFi6yu\nO3z4cLmallkSN9xg2Rx13LhxAEWt6eo0PLoNhx78fPDgQfr06WMsZFBcEHB5QB9dr1u3LvDXHHV9\nQOCjjz4CLMZTYWHQoEEANGvWzOrz2bNne0Icl6FpWpGLfZQ2yBMWFkavXr0KLb6jN0I6d+7sZEm9\njypVqrBq1SoGDhxofLZlyxaWL1/usu9UPk+FQqFwAK/YAG7ixIn8/vvvPPfcc4ClS1sep+TVq1eP\noUOHGsfHjh1j1KhRHpTI/eTvmhbkxIkT7Nu3zzhu2bIlrVu3tlotCODbb78FMJYfKy/Y023v3bu3\nERMaEhJCkyZNrMqJi4ujZ8+erhfahYSHh3P06NEiz4WEhNC0aVNjWcdXXnmF0NBQDh8+DFhvaeMq\nvMJ4nj59miVLljBhwgQAnn322WLnO/sy/fr1o2rVqsZxUXPV8y9Bl5GR4VKfjSc4f/68Vexmfm6+\n+WbDJ6yT33CICMeOHSu3Lo3iuu133323Ed9oC3FxcXz22Wc+v4PmwYMHSUhIMPy1rVq1IiQkBIBq\n1aoRFBRkrP0wb948Vq1a5dalLb3CeAK89dZbhvEcNmxYuTSef/75p/F/VlZWoU26hg0bZrU+5cSJ\nE0lOTnabfO7gxhtvpEOHDsbg4Lhx44yg94oVK3LzzTcXusZkMgGWwO+hQ4dy+fJl9wnsRopreRbc\n4E3/v+B53cfZs2dPnzec8NcMxRYtWgCQnZ3NmTNnAPj0009JTExk9+7dgGcWBlE+T4VCoXAAr9l6\nuHLlyuzcuROwbK2qbz9hC+IjW6dOmDCB999/3zj+7rvvSE9PB6BDhw7UqFEDPz8/wNIyDQwMdFgu\nX9FJfgICArjjjjsKfa5vM2LLdsyl4PVbD+urx9u7Qv6pU6f47LPPAOyaAw++WVdcjS068Zpue2Zm\nJl9++SVg8W00btyY+Ph4D0vlXL7++mujaxUWFka3bt0K5dHn6uYfWLpeyMnJ4YcffvC0GB5FN3xx\ncXFMnz4dwFibs7hu+/jx49m6dWu56Kr7EqrbrlAoFA7gNd12wAjbWbp0KREREVZhKyXhS92O8PBw\nwBIc36pVK+Pz+Ph4fvrpJ2NDq0OHDpVJLl/SiRvx+m67J1B1pTA+1W3Pz6VLl2w2nL6GHreWf3k+\nhULhe3hVy9NR1JuzMEonRaJankWg6kphbNGJ8nkqFAqFAyjjqVAoFA5gr88zATjjCkHKQKiHv1/p\npDDeqBNQeikKpZPC2KQTu3yeCoVCobCguu0KhULhAMp4KhQKhQMo46lQKBQOoIynQqFQOIAyngqF\nQuEAyngqFAqFA9gV5+nLU6lchdJJYbxVJ0CCiNzgqS/3Vr2oulIYNT1TobDG24KxFT6MMp4KhULh\nAB5bki4pKYmAgADAsvHXH3/8wcmTJwEYMWIEf/zxh6dEUygUilLxWMvz9ddfJygoiKCgIFatWkV6\nejqdOnWiU6dO/Pjjj8Ye7orri6pVq7Jp0yY2bdpk7CappyNHjnhaPK8mJCSEkJAQUlJS6Nq1q6fF\nKfeobrtCoVA4gNcshly3bl3uueceAKZMmcIdd9zBo48+CmDsClgcarSwML6kkyZNmgDw9ttvc//9\n9xMUFFRkvpycHCpVqlQW0cr1YsibN28GoE+fPmzbto3777/fput8qa64C5t0UrBrVFICxF3pwoUL\ncuTIETly5Eipee25B2cnd+rEnuQrOmnbtq0cOHBADhw4IGaz2SplZGRIQkKCpKWlSVpamphMJhky\nZEhZ9HLAV/RibwoLC5Pk5GRJTk6WjIwMGTBgQLmrK972/LhtwOixxx7j9ttvByAiIoLevXuTmppa\nbP5vvvmGhx9+GIABAwawYcMGt8jpbsLCwgAYO3Ys3bp147bbbgOgWrVq7Nmzh48++giAxYsXe0xG\nV1C7dm0Atm/fTvXq1a3O7d+/H4CZM2eyY8cOFixYAMCzzz5r6EdhzVdffUVwcDBg0Vt5fV78/f2N\nv/379+fHH38ELPvcDx48mD///BOAM2fO8MUXX7BkyRIAcnNzERHMZjOAbrjLhPJ5KhQKhSO4o4k9\nbdo0MZvNkpOTIzk5OfLbb79JUFBQidcEBQVJfHy8xMfHywcffFDuuh1hYWGye/du0UlOTpa1a9fK\n+PHjZfz48TJnzhxJTk42zo8fP97p3Q5P6cTPz08+/PBD+fDDDwt11efOnSs1atSQGjVqGPkXLFgg\nCxYsEBGRV199tSzdsXLZbW/WrJmIiGRnZ0t2draEh4eXm7qiaZqMGTNGxowZI6tWrZLz58/L+fPn\nC9Wb0tKFCxfk559/lrCwMAkLC5Po6GipXr26VK9e3Tu77SEhIQDMnj2bJUuWcOrUKQDmz59f6rWp\nqam89dZbgKVLW94YO3Ysd911F3PnzgXg+eefL5Rn6dKlrFmzBoDo6Gji4uL43//+51Y5XUFQUBDD\nhw83jrOysgCYNWsWK1as4OrVq0VeZzabiYuLc4uMvsS7776LiPDiiy8Cf21vXR6oX7++0fW2h9zc\nXKOLD1CvXj3q1avH9u3bAQgNDaVKlSoAjBw50iHZVLddoVAoHMBlLc/GjRsTExMDWFoMb775JmfP\nnrWrjIMHDwLQrFkzWrRoAcCxY8ecK6ib6d27N2Bx6s+dO7fIFqdOXFycMWB01113MWLEiHLR8kxN\nTSU6OhqArl278thjjwHw888/F5n/8ccfByytiZUrV7pFRl+gefPmgKVO5eTk8Mknn3hYIuej98yK\nwmw2k56ebhxv2LCB33//HYA9e/Zw1113Gefq16/PE088QWhoKGAJe0tOTi6TbC4znlu2bKFhw4YA\nHD9+3G7DCXDHHXcAEBgYaHRJhg0b5jwhPcCiRYsAOHXqVImGU2fq1KmuFsntmEwmnn32WcDShS+u\nm65TtWpVd4jlc0ybNg2AgIAAVq9ezZkz5W/dkytXrhRp5L7++mu2bt3KsmXLir1227ZtRszw2bNn\nrWKEhw0bxrp168omnKsc3vmduvbEnOVPO3bskB07dkhMTIzceuutcuutt/qcw7sIWUVEZPfu3SXm\nGz9+vNWAUWxsbLkZBLAnbdq0yahHy5YtK2t55WbAqFatWpKSkiIpKSliNpulS5cuDpdVXnRSMD3y\nyCNy4sQJOXHihFGHtm3bJtu2bZOaNWuWWSfK56lQKBQO4NRue0BAAP/4xz8AqFGjBqtXrwZwKGC3\neqNenoUAAAbDSURBVPXqVK5cGbCM2hcMpPZV9IiD0pg6dSrVqlUzjj/99FNXieTVdO/e3fh/woQJ\nnhPEyxgzZozhzvj555/ZuXOnhyXyDvSJAkuWLOFvf/ub0VW/cuUKR44coX///gBWvlJHcarxbN++\nPS+99JJxfPHiRYfLWrRoEe3atQPg8uXLJc5G8iV0Izhz5kx69+5daABIn3F06dIlmjZtyp49e4Ci\nQ5nKK/pShbrPavny5QBkZ2d7UiyvISgoiClTphjHUVFRHpTGc1SpUoU777QsVXD//ffTtGlTOnTo\nAEDTpk0BjGUu27VrR0pKilO/36nG85ZbbjH+T01NLXGkrDT69u1rTEmcPHlymWXzFpYuXQpYWlGL\nFi2iZ8+egEV33bp1Y8iQIYDlxz916hR33323x2T1FKNHjwagS5cuiAhffPGFTdfVq1ePihUrAvDH\nH39gMplcJqMneemll7jhhhsMw1AeR9mLQ++NLl68mIiICG666aYS88+ZMwfA6YYTVJynQqFQOIRT\nW54jRoww/l+6dCmJiYkOl7Vz5062bt3qDLG8Cn2GTHR0NDNnzizRB/r222+7SyyvoUmTJlazj/bs\n2WMstabToEEDwBLKlr9XEhERYbRMZs6cacxQKy80a9YMsIQoiQjvvfceABkZGZ4Uy600atQI+Cv2\ntzgyMzPx8/Nj4sSJgKX77my/sFPX89yxYwfdunUD4O6772bv3r0OCfX1119z8OBBZsyYYVN+8dH1\nCMPCwoygeX3qZWxsrHFef1gcwRd1EhwczNGjR434YICHH36YCxcuANCjRw+Cg4ONbn1Jg4iJiYk0\natSooGHx6fU8dTfY9OnT+e2332jfvj1Q9sEPX6or+sSA48ePFzqXlZVlPD9vvPEGt912mxFPvGPH\nDh588EGbv8cmnTgzJmvTpk2i06lTp1LjsPSJ+dOmTZPdu3cbsVjR0dHXZZza+PHjDf2tXbu2TGX5\nkk6Cg4MlODhYvv/++xIXdxARmxeCWL9+vfj7+xf8Lp+N82zevLmkpqZKamqq5ObmSu/evZ1W73xJ\nJ82bN5fmzZtLQkKCZGZmysGDB+XgwYOyadMmadeunVXeJ5980qgPR48elSpVqjhVJ8rnqVAoFA7g\nVJ/nrFmzuO+++wAYN24cFSpYbHN2djYHDhww8tWuXZsnn3ySJ554ArCMkm7dutWYLnW9bv42depU\nrl27BmDEy5Z3goKCjN+7c+fODpVx+vRpAPbu3cvatWsB2Lp1K7m5uU6R0RuIiooyVgH67rvvysUa\nB46gT0Ft27YtderU4dChQ8Xmzb9wdoMGDahWrZpT4jsNnN3E3rx5s2zevNmqC5WTkyOHDx+WmTNn\nysyZM2XlypViNpslKSlJkpKS5Nq1a9K8efProttRXNK77GvXri1zl92XdKLXBVuSiGXNypiYGCM9\n+eSTRrffhu/zyW57p06drNbDLctUTF+uK/akoUOHSlJSklF33n77bafrxOkLg+ibtkVHRxstiUaN\nGnHbbbfx5ptvWuXVl8yPjIw0VkO5XmncuDHAdTNTpH79+gDGVivFsWvXLiPO84svviAnJ+e6qSv6\nDCJ9YoXeyrpe6oi9NGjQgAceeACAF154gfT0dNavXw9YesXORvk8FQqFwgFcuvWwvhxUdHQ0Fy9e\nJC0tDbDEqb388svGCtFlnXopPhRqURz6slvOmsPv7TrR4/UKLqP2ww8/GHGdK1as4OLFi86cKeRT\noUr6GEBkZCQAQ4cOBUrfittevL2ulES9evUA+Pjjj2nSpImx9OVzzz3HqVOnjJlFOTk5dpVrk068\nwT9R1uTLPht9zyKRsocn+ZJO9DC18+fPG0urvfDCC+Ln5+fKuuJTPs/8/t4///xTAgMDJTAwUD0/\nIEOGDJGjR48a21KbzWa5du2ahIeH272Hk6M6Ud12hUKhcAC37duuKBp9oAjgww8/9KAk7kV3U+Sf\nTaSwRg/1U1gIDg5m3759ANx00034+fkZ5w4cOMCXX37p1s3vXOrzdBfiwz6b3bt3A5Y9ijTNebfh\nyzpxIT7l83QXvlJXGjVqVMhHro+jdOnShZ9++slpctmiE9Xy9DD6JlX6up0KhaJoHnzwQaOBsX//\nfrZs2cLs2bMB+weEnIHqFygUCoUDqG57GVE6KYy36gTVbS8SVVcK44puewLgbfubhnr4+5VOCuON\nOgGll6JQOimMTTqxq+WpUCgUCgvK56lQKBQOoIynQqFQOIAyngqFQuEAyngqFAqFAyjjqVAoFA6g\njKdCoVA4gDKeCoVC4QDKeCoUCoUDKOOpUCgUDvD/fzvGopHmwaMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10e4ff860>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib.pyplot import *\n",
    "\n",
    "# Get the figure and axes.\n",
    "fig, axes = subplots(5, 5)\n",
    "axes = axes.reshape(25)\n",
    "fig.suptitle(\"Random Sampling of MNIST\")\n",
    "\n",
    "# Plot random images.\n",
    "indices = random.randint(len(train_images), size=25)\n",
    "for axis, index in zip(axes, indices):\n",
    "    image = train_images[index, :, :]\n",
    "    axis.get_xaxis().set_visible(False)\n",
    "    axis.get_yaxis().set_visible(False)\n",
    "    axis.imshow(image, cmap = cm.Greys_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def euclidean_distance(img1, img2):\n",
    "    # Since we're using NumPy arrays, all our operations are automatically vectorized.\n",
    "    # A breakdown of this expression:\n",
    "    #     img1 - img2 is the pixel-wise difference between the images\n",
    "    #     (img1 - img2) ** 2 is the same thing, with each value squared\n",
    "    #     sum((img1 - img2) ** 2) is the sum of the elements in the matrix.\n",
    "    return sum((img1 - img2) ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "def get_majority(votes):\n",
    "    # For convenience, we're going to use a defaultdict.\n",
    "    # This is just a dictionary where values are initialized to zero\n",
    "    # if they don't exist.\n",
    "    counter = defaultdict(int)\n",
    "    for vote in votes:\n",
    "        # If this weren't a defaultdict, this would error on new vote values.\n",
    "        counter[vote] += 1\n",
    "    \n",
    "    # Find out who was the majority.\n",
    "    majority_count = max(counter.values())\n",
    "    for key, value in counter.items():\n",
    "        if value == majority_count:\n",
    "            return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the predictor class.\n",
    "class MNISTPredictor(NearestNeighborClassifier):\n",
    "    def distance(self, p1, p2):\n",
    "        return euclidean_distance(p1, p2)\n",
    "    \n",
    "    def consensus(self, values):\n",
    "        return get_majority(values)\n",
    "    \n",
    "# Convert our data set into an easy format to use.\n",
    "# This is a list of (x, y) pairs. x is an image, y is a label.\n",
    "dataset = []\n",
    "for i in range(len(train_images)):\n",
    "    dataset.append((train_images[i, :, :], train_labels[i]))\n",
    "    \n",
    "# Create a predictor for various values of k.\n",
    "ks = [1, 2, 3, 4, 5, 6]\n",
    "predictors = [MNISTPredictor(dataset, k) for k in ks] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_test_set(predictor, test_set):\n",
    "    \"\"\"Compute the prediction for every element of the test set.\"\"\"\n",
    "    predictions = [predictor.predict(test_set[i, :, :]) \n",
    "                   for i in range(len(test_set))]\n",
    "    return predictions\n",
    "\n",
    "# Choose a subset of the test set. Otherwise this will never finish.\n",
    "test_set = test_images[0:100, :, :]\n",
    "all_predictions = [predict_test_set(predictor, test_set) for predictor in predictors]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEjCAYAAADdZh27AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucHFWZ//HPNxcICZcoiS4kISDEYLyAMoCyiCiwElDR\nXVQwgKCIUVBcFwUVAXUV/bmisoD8IgJiuOgKrBFZ7peILJqJXEJAIIZcCCABTCTBEEKe/eOcKTrN\nTE9NmOpOJ9/369WvqcvpU09V9/TTdU71KUUEZmZmAANaHYCZma07nBTMzKzgpGBmZgUnBTMzKzgp\nmJlZwUnBzMwKTgrWdJK+LOm8kmVPkzS1wfp5kvbtv+j6RtItko6uqO5tJC2TNDDPv1rSdEnPSPpe\nX47jhiAfq9e0Oo5256TQJPnD6wlJw2qWHS3plhaG9RKSjpR0Wy9lbpG0QtKYmmX7SppXZhsR8a2I\nqOSDtL9J2ignpockLc+v4/mStq162xGxICI2jYgX8qJjgCeBzSPi36o6jvn1/aukjfu77irlYzW3\n1XG0OyeF5hoIHF/1RiQNqnobwHLgq03YTlM0OGa/BN4HfATYAtgJ6AT2aVJotcYC98XL/MWpkm7/\n93OyezsQpP1umia9b60XTgrN9V3gBEnDu1spaUdJ10t6WtIDkj5Us+5ASXdK+pukhZJOq1m3raSQ\n9HFJC4Cb8vK3Srpd0hJJd0vau+Y5R0qam5siHpY0SdLrgHOBt+VT8SUN9uVM4FBJ2/ewL1tLulzS\n4lz/Z2vWrdEkJOkISfMlPSXpq900CW0k6aIc62xJHXWb21XSffnb7QWShtTU/QlJc/IxnSZp65p1\nIelYSQ8BD3WzD/sC+wEHRcSMiFgVEUsj4pyI+Ek35beXdFPejyclXVz7Wks6UdKivB8PSNonL99N\nUmd+bf8i6Yy8vOt1HSTpQuCjwBfza7NvN8ex0et9i6RvSvod8CzQUzPLEcAdQNf2avdvE6Vmq/mS\nlkq6TdImed2eNdteKOnImu0eXVPHGmei3b0Gkn6Y6/ibpJmS3l5TfqBSs9mf83GcqXzGmuvaIU9v\nLOk/JC3Ix/TcmlhHSLoqx/q0pN+qhyS5QYoIP5rwAOYB+wJXAP+elx0N3JKnhwELgaOAQcCbSU0F\nE/L6vYE3khL5m4C/AO/P67YlfbO7KNezCTAKeAo4ID9nvzw/Mpf5GzA+P38r4PV5+kjgtl725ZYc\n+xnA1LxsX2Benh4AzAROATYifQDNBd6d159W87wJwDJgz1z2P4DngX1ryq7I+zEQOB24o+643guM\nAV4J/K7m+L4rH8O3ABsD/wlMr3luANfn523SzX5+G7i1zLHI0zvk47xxPs7TgR/kdePz67t1zWu2\nfZ7+X+DwPL0p8Na613VQnr+wa9+6OY49vt41cS4AXk96fw3uYX/mAJ8Gdsmvw6tr1p2d6xmVX4s9\n8r6OBZ4BDgUGA1sCO9cfn+7eX929BsBhuY5BwL8BjwND8rovALPy8RTpzG3Lmrp2yNPfB6blejcD\nfg2cntedTvryMzg/3g6o1Z8R68rD2bH5TgE+I2lk3fL3kD5UL4j0jfRO4HLggwARcUtEzIqI1RFx\nD3Ap8I66Ok6LiOUR8XfSP9bVEXF1fs71pGaPA3LZ1cAbJG0SEY9FxOy12JfTgfdKen3d8l1JH0Zf\nj4iVkdp5fwwc0k0dBwO/jojbImIl6fjUN4/clvfjBeBnpA+CWmdFxMKIeBr4JunDCWAScH5E/DEi\nngO+RDoL2rZ2HyLi6XzM6m0JPNbz7q8pIuZExPUR8VxELCYlza7X6AXSB+gESYMjYl5E/Dmvex7Y\nQdKIiFgWEXeU3WaN3l5vgAsjYnZ+fz1fX4GkPUkf8L+IiJnAn0nNZuRv0h8Djo+IRRHxQkTcno/r\nR4AbIuLSiHg+Ip6KiLv6EPsar0FETM11rIqI75GO2/hc9mjg5Ih4IJK7I+Kpuv0Qqf/lX3O9zwDf\n4sX33/OkL0Jjc7y/jQgPApc5KTRZRNwLXAWcVLdqLLB7PqVdkptuJgH/ACBpd0k35+aYpcBkYERd\nHQvr6vtgXX17AltFxHLgw7mOxyT9RtKOa7Evi4GzgK93sy9b1237y8Cru6lm69q4I+JZ0jfcWo/X\nTD8LDNGa7c+1+z0/19lV9/yaupflukf18Nx6T5E+PEpRujrostxE9DdgKvk1iog5wOdI3+6fyOW6\n4vw48FrgT5JmSHpP2W3W6PH1rinTaF8hNRddFxFP5vlLeLEJaQQwhJQo6o3pYXlZa8Ql6QRJ9+cm\nqiWkvpyu93qZbY0EhgIza47FNXk5pGbcOcB1Sk2o9f+LGzQnhdY4FfgEL/1wujUihtc8No2IT+X1\nl5BOh8dExBak01/V1Rt19f2srr5hEfFtgIi4NiL2I31o/In0Tb6+jjK+C7yT1NxQu+2H67a9WUQc\n0M3zHwNGd83kdt8t+xjDmJrpbYBH8/SjpA/LrrqH5boX1ZRvtL83ALtJGt2gTK1v5freGBGbk769\nF69RRFwSEV3fxgP4Tl7+UEQcCrwqL/ulaq5SK6nh690VQk9Pzsf9Q8A7JD0u6XHgX4GdJO1EaoZb\nAXTXh7Swh+WQLkgYWjP/D92UKeLK/QdfzLG8IiKGA0t58Tg22laXJ4G/k5pEu47FFhGxKUBEPBPp\n6q3XkDrTP9/Vv2NOCi2RvzX+HPhszeKrgNdKOlzS4PzYVanzF1K76NMRsULSbuTT+gamkpp23p07\n54ZI2lvS6PyN9qD8wfMcqU1/dX7eX4DRkjYquS9LgO+R/pG7/AF4RqljdZO8/TdI2rWbKn6Z49wj\nb/M0XprsenNs3q9XAl8hHVtITWxHSdpZ6fLKbwG/j4h5JfftBlJ795WSdlHq8N1M0mRJH+vmKZuR\njuVSSaNI7d8ASBov6V05jhWkD63Ved1hkkZGxGqgq3N/NX3T4+td8vnvJzVxTQB2zo/XAb8Fjsix\nnQ+coXQRwUBJb8v7czGwr6QP5WO0paSdc713Af8saWjuBP54L3FsBqwCFgODJJ0CbF6z/jzgG5LG\nKXmTpDW+RORYfwx8X9KrACSNkvTuPP0eSTvkZqaleb/7erzXW04KrfN1UocvkL69AP9Eavd8lNRk\n8h1Seyqkzr+vS3qG1O7+i0aVR8RC4CBSs81i0jesL5Be8wHA5/N2nia1e3edkdwEzAYel/Qk5fyQ\n9I/Vte0XSH0kOwMPk765nUdqBqiPczbwGeAy0lnDMuAJUrIq6xLgOlJn9p+Bf89130C6bPbyXPf2\ndN+v0cjBwNWkRLOU1KndQTqLqPc1Uqf2UuA3pIsKumxM6rh+kvTavorUxwGwPzBb0jLSsTykhz6O\nHvXyepfxUeCCSL+NeLzrQWoenJSb604gdfLOIL1vvgMMiIgFpL6Lf8vL7+LFfp/vAytJXzZ+Skog\njVxLaup5kNT0t4I1m5fOIL33ryNdLPET0oUV9U4kNRHdkZvybuDFfolxeX4ZqZP/nIi4uZe4Nhhy\n/4qtSyRtSvq2PC4iHm51PGYbGp8pWMtJem9uXhhGuiR1FulSUzNrMicFWxccRGrKepR0an+ILxE0\naw03H5mZWcFnCmZmVnBSMDOzgpOCmZkVnBTMzKzgpGBmZgUnBTMzKzgpmJlZwUnBzMwKTgpmZlZw\nUjAzs4KTgpmZFSpLCpLOl/SEpHt7WC9JZ0qaI+keSW+pKhYzMyunyjOFC0k3D+nJRNKImONIN9n+\nUYWxmJlZCZUlhYiYTroLU08OAi6K5A5guKTSN0k3M7P+N6iF2x7FmrfZeyQve6y+oKRjSGcTDBs2\nbJcdd9yxKQGama0vZs6c+WREjOytXCuTQmkRMQWYAtDR0RGdnZ0tjsjMrL1Iml+mXCuvPloEjKmZ\nH52XmZlZi7QyKUwDjshXIb0VWBoRL2k6MjOz5qms+UjSpcDewAhJjwCnAoMBIuJc4GrgAGAO8Cxw\nVFWxmJlZOZUlhYg4tJf1ARxb1fbNzKzv/ItmMzMrOCmYmVnBScHMzApOCmZmVnBSMDOzgpOCmZkV\nnBTMzKzgpGBmZgUnBTMzKzgpmJlZwUnBzMwKTgpmZlZwUjAzs4KTgpmZFZwUzMys4KRgZmYFJwUz\nMys4KZiZWcFJwczMCk4KZmZWcFIwM7OCk4KZmRWcFMzMrOCkYGZmBScFMzMrOCmYmVnBScHMzApO\nCmZmVnBSMDOzgpOCmZkVnBTMzKzgpGBmZgUnBTMzKzgpmJlZodKkIGl/SQ9ImiPppG7WbyHp15Lu\nljRb0lFVxmNmZo1VlhQkDQTOBiYCE4BDJU2oK3YscF9E7ATsDXxP0kZVxWRmZo1VeaawGzAnIuZG\nxErgMuCgujIBbCZJwKbA08CqCmMyM7MGqkwKo4CFNfOP5GW1zgJeBzwKzAKOj4jVFcZkZmYNtLqj\n+d3AXcDWwM7AWZI2ry8k6RhJnZI6Fy9e3OwYzcw2GFUmhUXAmJr50XlZraOAKyKZAzwM7FhfUURM\niYiOiOgYOXJkZQGbmW3oqkwKM4BxkrbLnceHANPqyiwA9gGQ9GpgPDC3wpjMzKyBQVVVHBGrJB0H\nXAsMBM6PiNmSJuf15wLfAC6UNAsQcGJEPFlVTGZm1lhlSQEgIq4Grq5bdm7N9KPAP1UZg5mZldfq\njmYzM1uHOCmYmVnBScHMzApOCmZmVnBSMDOzgpOCmZkVnBTMzKzgpGBmZgUnBTMzKzgpmJlZwUnB\nzMwKDcc+kvQ24DDg7cBWwN+Be4HfAFMjYmnlEZqZWdP0eKYg6X+Ao0mjnO5PSgoTgJOBIcCvJL2v\nGUGamVlzNDpTOLybYayXAX/Mj+9JGlFZZGZm1nQ9nil0JQRJ36lf17XM9z4wM1u/lOlo3q+bZRP7\nOxAzM2u9HpuPJH0K+DSwvaR7alZtBtxedWBmZtZ8jfoULgH+BzgdOKlm+TMR8XSlUZmZWUs06lNY\nGhHzgB8CT0fE/IiYD6yStHuzAjQzs+Yp06fwI9JVR12W5WVmZraeKZMUFBHRNRMRq+nlR29mZtae\nyiSFuZI+K2lwfhwPzK06MDMza74ySWEysAewCHgE2B04psqgzMysNXptBoqIJ4BDmhCLmZm1WK9n\nCpJeK+lGSffm+TdJOrn60MzMrNnKNB/9GPgS8DxARNyDzxzMzNZLZZLC0Ij4Q92yVVUEY2ZmrVUm\nKTwpaXsgACQdDDxWaVRmZtYSZX5vcCwwBdhR0iLgYWBSpVGZmVlL9HbntQFAR0TsK2kYMCAinmlO\naGZm1mwNm4/yr5e/mKeXOyGYma3fyvQp3CDpBEljJL2y61F5ZGZm1nRl+hQ+nP8eW7MsgNf0fzhm\nZtZKZfoUDouI3zUpHjMza6EyfQpnNSkWMzNrsTJ9CjdK+hdJ6mvlkvaX9ICkOZJO6qHM3pLukjRb\n0q193YaZmfWfMn0KnwQ+D7wg6e+AgIiIzRs9SdJA4GxgP9LoqjMkTYuI+2rKDAfOAfaPiAWSXrWW\n+2FmZv2gzCipm61l3bsBcyJiLoCky4CDgPtqynwEuCIiFuRtPbGW2zIzs35Q6g5qkt4H7JVnb4mI\nq0o8bRSwsGa+614MtV4LDJZ0C7AZ8MOIuKib7R9DvofDNttsUyZkMzNbC2WGzv42cDzpG/59wPGS\nTu+n7Q8CdgEOBN4NfFXSa+sLRcSUiOiIiI6RI0f206bNzKxemTOFA4Cd85VISPopcCdpOO1GFgFj\nauZH52W1HgGeiojlwHJJ04GdgAdLxGVmZv2szNVHAMNrprco+ZwZwDhJ20naiHQPhml1ZX4F7Clp\nkKShpOal+0vWb2Zm/azMmcLpwJ2SbiZdebQX0O3lpbUiYpWk44BrgYHA+RExW9LkvP7ciLhf0jXA\nPcBq4LyIuHct98XMzF4mRUTvhaStgF3z7B8i4vFKo2qgo6MjOjs7W7V5M7O2JGlmRHT0Vq5MR/MH\ngGcjYlpETANWSHp/fwRpZmbrljJ9CqdGxNKumYhYApxaXUhmZtYqZZJCd2VK/b7BzMzaS5mk0Cnp\nDEnb58cZwMyqAzMzs+YrkxQ+A6wEfg5cBqxgzXsrmJnZeqLM2EfLKXEJqpmZtb+yP14zM7MNgJOC\nmZkVnBTMzKxQOilIeq+kWyTdIenTVQZlZmat0WNSkLRz3aLDgXcCewCfqjIoMzNrjUZXH31K0gDg\nq3mso4XAyaSB6x5tRnBmZtZcPSaFiPikpJ2A/y9pJnAK8DZgKPAfTYrPzMyaqGGfQkTcHREHkW6q\n8ytg6zww3nNNic7MzJqqUZ/CZEm3S7odGAbsDwyXdK2kvXp6npmZta9GZwqfjog9SJ3LX4iIVRFx\nJukOah4628xsPdSoo3mRpC+T+hD+1LUwIv4KfL7qwMzMrPkanSkcBMwCbgOOaE44ZmbWSo3OFLaO\niF/3tFKSgFER8Uj/h2VmZq3QKCl8N/9O4Vek+ycsBoYAO5D6GfYh3YHNScHMbD3R6HcKH5Q0AZgE\nfAzYCngWuB+4GvhmRKxoSpRmZtYUDe+nEBH3AV9pUixmZtZiHiXVzMwKTgpmZlZwUjAzs0KvSUHS\nFZIOzFcimZnZeqzMB/05wEeAhyR9W9L4imMyM7MW6TUpRMQNETEJeAswD7ghD5R3lKTBVQdoZmbN\nU6pJSNKWwJHA0aRhtH9IShLXVxaZmZk1XcPfKQBIuhIYD/wMeG9EPJZX/VxSZ5XBmZlZc/WaFIAz\nI+Lm7lZEREc/x2NmZi1UpvlogqThXTOSXiHp0xXGZGZmLVImKXwiIpZ0zeT7KXyiupDMzKxVyiSF\ngXmYbAAkDQQ2qi4kMzNrlTJJ4RpSp/I+kvYBLs3LeiVpf0kPSJoj6aQG5XaVtErSweXCNjOzKpTp\naD4R+CTwqTx/PXBeb0/KZxRnA/uR7rkwQ9K0PPJqfbnvANf1IW4zM6tAr0khIlYDP8qPvtgNmBMR\ncwEkXUa6xed9deU+A1wO7NrH+s3MrJ+VGftonKRfSrpP0tyuR4m6RwELa+Yfyctq6x4FfIC+Jxwz\nM6tAmT6FC0gf2qtIt+G8CJjaT9v/AXBiPhvpkaRjJHVK6ly8eHE/bdrMzOqVSQqbRMSNgCJifkSc\nBhxY4nmLgDE186PzslodwGWS5gEHA+dIen99RRExJSI6IqJj5MiRJTZtZmZro0xH83N52OyHJB1H\n+mDftMTzZgDjJG2Xn3MIabTVQkRs1zUt6ULgqoj475Kxm5lZPytzpnA8MBT4LLALcBjw0d6eFBGr\ngOOAa4H7gV9ExGxJkyVNXvuQzcysKoqInlfmy0Uj4oTmhdRYR0dHdHZ6HD4zs76QNLPMeHUNzxQi\n4gVgz36LyszM1mll+hTulDQN+C9gedfCiLiisqjMzKwlyiSFIcBTwLtqlgXgpGBmtp4p84vmo5oR\niJmZtV6ZO69dQDozWENEfKySiMzMrGXKNB9dVTM9hDQsxaPVhGNmZq1Upvno8tp5SZcCt1UWkZmZ\ntUyZH6/VGwe8qr8DMTOz1ivTp/AMa/YpPE66x4KZma1nyjQfbdaMQMzMrPXK3E/hA5K2qJkf3t1I\npmZm1v7K9CmcGhFLu2YiYglwanUhmdl65eKLYdttYcCA9Pfii1sdkTVQ5pLU7hJHmeeZ2Ybu4ovh\nmGPg2WfT/Pz5aR5g0qTWxWU9KnOm0CnpDEnb58cZwMyqAzOz9cBXvvJiQujy7LNpua2TyiSFzwAr\ngZ8DlwErgGOrDGq91O6n0O0ev7XGggV9W74u2sDe+2WuPloOnNSEWNZf7X4K3e7xW+tss016v3S3\nvB1sgO/9MlcfXS9peM38KyRdW21Y65l2P4Vu9/itdb75TRg6dM1lQ4em5e1gA3zvl2k+GpGvOAIg\nIv6Kf9HcN+1+Ct3u8VvrTJoEU6bA2LEgpb9TprTPt+wN8L1fJimsllSc60kaSzejploDPZ0qt8sp\ndLvHD+3fLtzO8U+aBPPmwerV6W+7JARYP977fVQmKXwFuE3SzyRNBaYDX6o2rPVMu59Ct3v8Xe3C\n8+dDxIvtwu3ywdru8bezdn/vr42I6PUBjADekx8jyjynqscuu+wSbWnq1IixYyOk9Hfq1FZH1Dft\nHP/YsRHp43TNx9ixrY6snHaPv92183u/BtAZJT5jlco2JukVpNFRh9Qkk+mVZKledHR0RGdnZys2\nbe1qwID0MVpPSk0a67p2j9/WCZJmRkRHb+XKXH10NKnJ6Frga/nvaS83QLOmafd24XaP39pKmT6F\n44FdgfkR8U7gzcCSxk8xW4e0e7twu8dvbaVMUlgRESsAJG0cEX8Cxlcbllk/avfLIts9fmsrvfYp\nSLoSOAr4HPAu4K/A4Ig4oPrwXsp9CmZmfVe2T6HMMBcfyJOnSboZ2AK45mXGZ2Zm66A+DYEdEbdW\nFYiZmbVemT4FMzPbQDgpmJlZwUnBzMwKTgpmZlZwUjAzs4KTgpmZFZwUzMysUGlSkLS/pAckzZH0\nkvs8S5ok6R5JsyTdLmmnKuMxM7PGKksKkgYCZwMTgQnAoZIm1BV7GHhHRLwR+AYwpap4zMysd1We\nKewGzImIuRGxErgMOKi2QETcHumezwB3AKMrjMfMzHpRZVIYBSysmX8kL+vJx4H/6W6FpGMkdUrq\nXLx4cT+GaGZmtdaJjmZJ7yQlhRO7Wx8RUyKiIyI6Ro4c2dzgzMw2IH0aEK+PFgFjauZH52VrkPQm\n4DxgYkQ8VWE8ZmbWiyrPFGYA4yRtJ2kj4BBgWm0BSdsAVwCHR8SDFcZiZmYlVHamEBGrJB1Huqfz\nQOD8iJgtaXJefy5wCrAlcI4kgFVlbgJhZmbV6PXOa+sa33nNzKzvyt55bZ3oaDYzs3WDk4KZmRWc\nFMzMrOCkYGZmBScFMzMrOCmYmVnBScHMzApOCmZmVnBSMDOzgpOCmZkVnBTMzKzgpGBmZgUnBTMz\nKzgpmJlZwUnBzMwKTgpmZlZwUjAzs4KTgpmZFZwUzMys4KRgZmYFJwUzMys4KZiZWcFJwczMCk4K\nZmZWcFIwM7OCk4KZmRWcFMzMrOCkYGZmBScFMzMrOCmYmVnBScHMzApOCmZmVnBSMDOzgpOCmZkV\nKk0KkvaX9ICkOZJO6ma9JJ2Z198j6S1VxmNmZo1VlhQkDQTOBiYCE4BDJU2oKzYRGJcfxwA/qioe\nMzPrXZVnCrsBcyJibkSsBC4DDqorcxBwUSR3AMMlbVVhTGZm1kCVSWEUsLBm/pG8rK9lzMysSQa1\nOoAyJB1Dal4CeE7Sva2M52UaATzZ6iBeBsffWu0cfzvHDu0f//gyhapMCouAMTXzo/OyvpYhIqYA\nUwAkdUZER/+G2jyOv7Ucf+u0c+ywfsRfplyVzUczgHGStpO0EXAIMK2uzDTgiHwV0luBpRHxWIUx\nmZlZA5WdKUTEKknHAdcCA4HzI2K2pMl5/bnA1cABwBzgWeCoquIxM7PeVdqnEBFXkz74a5edWzMd\nwLF9rHZKP4TWSo6/tRx/67Rz7LCBxK/0uWxmZuZhLszMrEZbJYXehs1Yl0k6X9IT7Xg5raQxkm6W\ndJ+k2ZKOb3VMfSFpiKQ/SLo7x/+1Vse0NiQNlHSnpKtaHUtfSZonaZaku8peBbMukTRc0i8l/UnS\n/ZLe1uqYypI0Ph/3rsffJH2ux/Lt0nyUh814ENiP9CO3GcChEXFfSwMrSdJewDLSL7jf0Op4+iL/\nynyriPijpM2AmcD72+jYCxgWEcskDQZuA47Pv6JvG5I+D3QAm0fEe1odT19Imgd0RERbXucv6afA\nbyPivHw15dCIWNLquPoqf44uAnaPiPndlWmnM4Uyw2assyJiOvB0q+NYGxHxWET8MU8/A9xPG/3y\nPA+jsizPDs6P9vg2lEkaDRwInNfqWDY0krYA9gJ+AhARK9sxIWT7AH/uKSFAeyUFD4mxDpC0LfBm\n4PetjaRvctPLXcATwPUR0VbxAz8AvgisbnUgaymAGyTNzCMUtJPtgMXABbn57jxJw1od1Fo6BLi0\nUYF2SgrWYpI2BS4HPhcRf2t1PH0RES9ExM6kX83vJqltmvAkvQd4IiJmtjqWl2HPfPwnAsfm5tR2\nMQh4C/CjiHgzsBxoqz5NgNzs9T7gvxqVa6ekUGpIDKtGbou/HLg4Iq5odTxrK5/23wzs3+pY+uAf\ngffldvnLgHdJmtrakPomIhblv08AV5Kag9vFI8AjNWeXvyQliXYzEfhjRPylUaF2Sgplhs2wCuSO\n2p8A90fEGa2Op68kjZQ0PE9vQrpY4U+tjaq8iPhSRIyOiG1J7/ubIuKwFodVmqRh+QIFcrPLPwFt\ncxVeRDwOLJTUNaDcPkBbXGRR51B6aTqCNhklFXoeNqPFYZUm6VJgb2CEpEeAUyPiJ62NqrR/BA4H\nZuV2eYAv51+st4OtgJ/mKy8GAL+IiLa7rLONvRq4Mn23YBBwSURc09qQ+uwzwMX5C+lc2mxInpyM\n9wM+2WvZdrkk1czMqtdOzUdmZlYxJwUzMys4KZiZWcFJwczMCk4KZmZWcFKwXknatszorpK26m4E\nzzzC6hBJP+jr6JKS3p5HNr0r/8ZgrUmaLOmIXsocKemsHtYt6255u5B0ew/LL5R0cEXbnCdphKSN\nJE2X1DaXwW+onBSsP30e+HHtgvxBvjoiVgC7An0dNnkScHpE7BwRf385wUXEuRFx0cupY22tCx+G\nEbFHf9SzNvuSB7G8Efhwf8Rg1XFSsD6R9Jo8KNiu3az+F+CamrI3A7OAN0iaBbwRmCHpgG7q3SfX\nOyvfe2JjSUcDHwK+IeniuvLb5nHtf5zPJK7rOpOQtL2ka/Lga7+VtGNefpqkE/L0rpLuyWcg3607\nE9o6P/8hSf+vbrvfz9u7UdLIvGxnSXfk+q6U9Iq8/JZ8dtQJHC/pg5LuVbqvw/Qeju+J+RjcLenb\nJer/jtK9Ih6U9Pa8/PV52V35OePy8mX5rySdpXRvkhuAV9VsfxdJt+Zjd63SsOnd7ctISZdLmpEf\n/5jLbZlfi9mSzgNUs3v/TUryti6LCD/8aPgAtiUNSzAeuBPYqZsy2wEzu1n+BVKyeAfw3R7qH0Ia\nAfe1ef4v0/OxAAAEDklEQVQi0qB7ABcCB/cQ0ypg5zz/C+CwPH0jMC5P704aFgLgNOCEPH0v8LY8\n/W3g3jx9JOkXq1vkuOYDY/K6ACbl6VOAs/L0PcA78vTXgR/k6VuAc2pingWMytPDu9mnicDtpLH6\nAV5Zov7v5ekDgBvy9H/WxLkRsEmeXpb//jNwPWlkgK2BJcDBpCHFbwdG5nIfJo0c0N2+XEIa5A5g\nG9IQKABnAqfk6QPzMRuR5wcCi1v9fvaj8aPlp7TWNkYCvwL+Obq/uc5WpOGF672FNADaRODuHuoe\nDzwcEQ/m+Z8Cx5KGi27k4YjoGnZjJrCt0kiuewD/lYdVANi49klK4yBtFhH/mxddAtTetObGiFia\ny94HjCUlrdXAz3OZqcAVSmPtD4+IW2tirx2F8uc1078DLpT0C6C7QQX3BS6IiGcBIuLpEvV31TOT\nlCgB/hf4itI9GK6IiIfqtrMXcGlEvAA8KummvHw88Abg+nzsBgKP9bAv+wITao7x5vnY70VKOkTE\nbyT9tatARLwgaaWkzSLdl8PWQU4KVtZSYAGwJ90PBvZ30jdrAHLTz3HADsDrSN8m/yJpYkT0VxPC\nczXTLwCbkJpEl0Qaprm/6u3p/6TMGDHLi8IRkyXtTvoGPVPSLhHx1NqHCbwYaxFnRFwi6fd5O1dL\n+mRE3NRTBTUEzI6Ini4GWF4zPQB4a6S+ohcrkOjFxsCK3gpZ67hPwcpaCXwAOELSR7pZ/yAvflMl\nIs4jjYZ5U/6AnhMRr+shITxA+pa/Q54/HLi1m3K9inSfh4clfRCK9vOd6sosAZ7JH9CQRh4tYwCp\nmQXgI8Bt+Yzir13t+Y1il7R9RPw+Ik4hnVWNqStyPXCUpKG5/Cv7Un/Ndl4DzI2IM0lnd2+qKzId\n+LDSjYe2At6Zlz8AjFS+QkzSYEmv72Ez15EGievaZlcSnk46NkiaCLyipsyWwJMR8Xyj+K21fKZg\npUXEcqUbvlwvaVlETKtb92dJO0TEnLx4L+A2SWNIbfM91btC0lGkJp9BpGHSz30ZoU4CfiTpZFI7\n+WW8tOnq48CPJa0mfcguLVHvctINek4m3cGt60qajwLn5g/zRiNofjd3+orU77FGTBFxTf5w7ZS0\nErga+HIf6u/yIeBwSc8DjwPfqlt/JfAu0hnfAlJzExGxUunS1DNzs9UgUhNed6MRfxY4W9I9udx0\nYDLwNeBSSbNJ/RMLap7zTuA3vcRuLeZRUq3fSPoAsEtEnNzqWHojadPI922WdBKwVUQc3+Kw1muS\nrgBOquk7snWQzxSs30TElbmJoB0cKOlLpP+B+aSrjqwiSvch+G8nhHWfzxTMzKzgjmYzMys4KZiZ\nWcFJwczMCk4KZmZWcFIwM7OCk4KZmRX+D2djK4e2eklZAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x11f22b668>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def evaluate_prediction(predictions, answers):\n",
    "    \"\"\"Compute how many were identical in the answers and predictions,\n",
    "    and divide this by the number of predictions to get a percentage.\"\"\"\n",
    "    correct = sum(asarray(predictions) == asarray(answers))\n",
    "    total = float(prod(answers.shape))\n",
    "    return correct / total\n",
    "\n",
    "labels = asarray(test_labels[0:100])\n",
    "accuracies = [evaluate_prediction(pred, labels) for pred in all_predictions]\n",
    "\n",
    "# Draw the figure.\n",
    "fig = figure(1)\n",
    "plt.plot(ks, accuracies, 'ro', figure=fig)\n",
    "\n",
    "fig.suptitle(\"Nearest Neighbor Classifier Accuracies\")\n",
    "fig.axes[0].set_xlabel(\"k (# of neighbors considered)\")\n",
    "fig.axes[0].set_ylabel(\"accuracy (% correct)\");\n",
    "fig.axes[0].axis([0, max(ks) + 1, 0, 1]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}