{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "9cfadabb-9212-431f-87fc-cce15aa4a9fd"
      },
      "source": [
        "Hey everyone, this is my first go at Kaggle competitions and Kernels.\n",
        "\n",
        "In this Kernel, I implemented kNN classifier from scratch.\n",
        "And the results got 97.1% accuracy on public leaderboard."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "c5e8cf89-8805-4d72-9a92-40d2977e566a"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from collections import Counter\n",
        "import time\n",
        "\n",
        "%matplotlib inline\n",
        "plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots\n",
        "plt.rcParams['image.interpolation'] = 'nearest'\n",
        "plt.rcParams['image.cmap'] = 'gray'\n",
        "\n",
        "# load csv files to numpy arrays\n",
        "def load_data(data_dir):\n",
        "    train_data = open(data_dir + \"train.csv\").read()\n",
        "    train_data = train_data.split(\"\\n\")[1:-1]\n",
        "    train_data = [i.split(\",\") for i in train_data]\n",
        "    # print(len(train_data))\n",
        "    X_train = np.array([[int(i[j]) for j in range(1,len(i))] for i in train_data])\n",
        "    y_train = np.array([int(i[0]) for i in train_data])\n",
        "\n",
        "    # print(X_train.shape, y_train.shape)\n",
        "\n",
        "    test_data = open(data_dir + \"test.csv\").read()\n",
        "    test_data = test_data.split(\"\\n\")[1:-1]\n",
        "    test_data = [i.split(\",\") for i in test_data]\n",
        "    # print(len(test_data))\n",
        "    X_test = np.array([[int(i[j]) for j in range(0,len(i))] for i in test_data])\n",
        "\n",
        "    # print(X_test.shape)\n",
        "\n",
        "    return X_train, y_train, X_test\n",
        "\n",
        "\n",
        "class simple_knn():\n",
        "    \"a simple kNN with L2 distance\"\n",
        "\n",
        "    def __init__(self):\n",
        "        pass\n",
        "\n",
        "    def train(self, X, y):\n",
        "        self.X_train = X\n",
        "        self.y_train = y\n",
        "\n",
        "    def predict(self, X, k=1):\n",
        "        dists = self.compute_distances(X)\n",
        "        # print(\"computed distances\")\n",
        "\n",
        "        num_test = dists.shape[0]\n",
        "        y_pred = np.zeros(num_test)\n",
        "\n",
        "        for i in range(num_test):\n",
        "            k_closest_y = []\n",
        "            labels = self.y_train[np.argsort(dists[i,:])].flatten()\n",
        "            # find k nearest lables\n",
        "            k_closest_y = labels[:k]\n",
        "\n",
        "            # out of these k nearest lables which one is most common\n",
        "            # for 5NN [1, 1, 1, 2, 3] returns 1\n",
        "            # break ties by selecting smaller label\n",
        "            # for 5NN [1, 2, 1, 2, 3] return 1 even though 1 and 2 appeared twice.\n",
        "            c = Counter(k_closest_y)\n",
        "            y_pred[i] = c.most_common(1)[0][0]\n",
        "\n",
        "        return(y_pred)\n",
        "\n",
        "    def compute_distances(self, X):\n",
        "        num_test = X.shape[0]\n",
        "        num_train = self.X_train.shape[0]\n",
        "\n",
        "        dot_pro = np.dot(X, self.X_train.T)\n",
        "        sum_square_test = np.square(X).sum(axis = 1)\n",
        "        sum_square_train = np.square(self.X_train).sum(axis = 1)\n",
        "        dists = np.sqrt(-2 * dot_pro + sum_square_train + np.matrix(sum_square_test).T)\n",
        "\n",
        "        return(dists)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "021e2a3d-cee0-439a-9959-7f9ee4d0ff97"
      },
      "source": [
        "Let's read `../input/train.csv` and `../input/test.csv` files to numpy arrays.\n",
        "\n",
        "Print shapes of those arrays as a sanity check."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "9b502e3b-eccb-4f2e-9d3f-fb06eeae187d"
      },
      "outputs": [],
      "source": [
        "# runs for 35 seconds\n",
        "data_dir = \"../input/\"\n",
        "X_train, y_train, X_test = load_data(data_dir)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "8747606a-fdea-4f3f-850b-0274a32f2803"
      },
      "outputs": [],
      "source": [
        "print(X_train.shape, y_train.shape, X_test.shape)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "50ee5b96-a42f-4a1b-b1a4-022926f5b065"
      },
      "source": [
        "Visualize random samples from training data."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "4f298648-5e52-4b8f-9c81-50598483a83f"
      },
      "outputs": [],
      "source": [
        "# runs for 10 seconds\n",
        "classes = [\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]\n",
        "num_classes = len(classes)\n",
        "samples = 8\n",
        "\n",
        "for y, cls in enumerate(classes):\n",
        "    idxs = np.nonzero([i == y for i in y_train])\n",
        "    idxs = np.random.choice(idxs[0], samples, replace=False)\n",
        "    for i , idx in enumerate(idxs):\n",
        "        plt_idx = i * num_classes + y + 1\n",
        "        plt.subplot(samples, num_classes, plt_idx)\n",
        "        plt.imshow(X_train[idx].reshape((28, 28)))\n",
        "        plt.axis(\"off\")\n",
        "        if i == 0:\n",
        "            plt.title(cls)\n",
        "        \n",
        "\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "a26097ee-a176-4a7e-9883-1ad1da0894f0"
      },
      "outputs": [],
      "source": [
        "# just to visualize ith test image\n",
        "plt.imshow(X_test[2311].reshape((28, 28)))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "26f4efad-5c19-4ee3-9a15-33eb9cbaae80"
      },
      "source": [
        "Split testing data into batches as distances of 10,000 test images and\n",
        "60,000 train images won't fit in memory."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "cfbd5fd9-aae8-44be-ad6a-609268ef6d80"
      },
      "outputs": [],
      "source": [
        "# predict labels for batch_size number of test images at a time.\n",
        "batch_size = 2000\n",
        "# k = 3\n",
        "k = 1\n",
        "classifier = simple_knn()\n",
        "classifier.train(X_train, y_train)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "d8b73c89-983c-42db-abbb-5a81b0d170c4"
      },
      "source": [
        "As Kaggle kernels have 1200 seconds limit, I have divided the prediction step\n",
        "into two cells each cell running for 13 minutes and saving prediction to `predictions`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "fdbc04ab-b1bf-4607-b590-c4e95ff9d4e3"
      },
      "outputs": [],
      "source": [
        "# runs for 13 minutes\n",
        "predictions = []\n",
        "\n",
        "for i in range(int(len(X_test)/(2*batch_size))):\n",
        "    # predicts from i * batch_size to (i+1) * batch_size\n",
        "    print(\"Computing batch \" + str(i+1) + \"/\" + str(int(len(X_test)/batch_size)) + \"...\")\n",
        "    tic = time.time()\n",
        "    predts = classifier.predict(X_test[i * batch_size:(i+1) * batch_size], k)\n",
        "    toc = time.time()\n",
        "    predictions = predictions + list(predts)\n",
        "#     print(\"Len of predictions: \" + str(len(predictions)))\n",
        "    print(\"Completed this batch in \" + str(toc-tic) + \" Secs.\")\n",
        "\n",
        "print(\"Completed predicting the test data.\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "c3a81fb4-1489-49d0-b619-00458d215cb7"
      },
      "outputs": [],
      "source": [
        "# runs for 13 minutes\n",
        "# uncomment predict lines to predict second half of test data\n",
        "\n",
        "for i in range(int(len(X_test)/(2*batch_size)), int(len(X_test)/batch_size)):\n",
        "    # predicts from i * batch_size to (i+1) * batch_size\n",
        "    print(\"Computing batch \" + str(i+1) + \"/\" + str(int(len(X_test)/batch_size)) + \"...\")\n",
        "    tic = time.time()\n",
        "    #predts = classifier.predict(X_test[i * batch_size:(i+1) * batch_size], k)\n",
        "    toc = time.time()\n",
        "    #predictions = predictions + list(predts)\n",
        "#     print(\"Len of predictions: \" + str(len(predictions)))\n",
        "    print(\"Completed this batch in \" + str(toc-tic) + \" Secs.\")\n",
        "\n",
        "print(\"Completed predicting the test data.\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "0523f79f-75db-4663-ac7e-b7442ff129df"
      },
      "source": [
        "After predicting and saving results in Python array, we dump our predictions to a csv file\n",
        "named `predictions.csv` which gets an accuracy of 97.114% on public leaderboard."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "64593dac-d1be-44df-b985-7671853d5033"
      },
      "outputs": [],
      "source": [
        "out_file = open(\"predictions.csv\", \"w\")\n",
        "out_file.write(\"ImageId,Label\\n\")\n",
        "for i in range(len(predictions)):\n",
        "    out_file.write(str(i+1) + \",\" + str(int(predictions[i])) + \"\\n\")\n",
        "out_file.close()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "24b45155-2a05-445f-b7db-477c16363cf7"
      },
      "outputs": [],
      "source": [
        ""
      ]
    }
  ],
  "metadata": {
    "_change_revision": 0,
    "_is_fork": false,
    "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.5.2"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}