{"cells": [{"metadata": {"_execution_state": "idle", "_uuid": "b3ea31f33ad3ac137f102917dc51e0a5d6dfd09c"}, "outputs": [], "cell_type": "code", "execution_count": null, "source": "import numpy as np\nimport pandas as pd\nimport matplotlib.pyplot as plt\n\n%matplotlib inline\nplt.rcParams['figure.figsize'] = (20.0, 16.0)"}, {"source": "class KNearestNeighbours:\n\n    def __init__(self, k=1, samples_per_class=None):\n        # Number of examples to save from each class (if None all is saved)\n        self.samples_per_class = samples_per_class\n        self.k = k\n\n\n    def train(self, X, y):\n        groups = list(set(y))\n        zipped = list(zip(y, X))\n        data = {a : np.array([b[1] for b in zipped if b[0] == a]) for a in groups}\n        features, targets = [], []\n\n        self.group_means = {}\n        for group in data:\n\n            # Calculation of a mean example for each class\n            mean = np.mean(data[group], axis=0)\n            features.append(mean)\n            targets.append(group)\n            self.group_means[group] = mean\n\n            # Here we randomly choose self.samples_per_class examples for each class. \n            # A better approach would be to keep only a few 'typical' instances.\n            nb_samples = len(data[group]) if not self.samples_per_class else self.samples_per_class\n            idxs = np.random.choice(range(len(data[group])), nb_samples, replace=False)\n            for i in idxs:\n                features.append(data[group][i])\n                targets.append(group)\n\n        self.X_train = np.array(features)\n        self.y_train = np.array(targets)\n\n\n    def predict(self, X):\n        # Calculation of Euclidean distances\n        p_squared = np.square(X).sum(axis=1)\n        q_squared = np.square(self.X_train).sum(axis=1)\n        product   = -2 * X.dot(self.X_train.T)\n        distances = np.sqrt(product + q_squared + np.matrix(p_squared).T)\n\n        # Selection of the nearest neighbours for each example\n        predictions = np.zeros(len(distances))\n        for i in range(len(distances)):\n            labels = self.y_train[np.argsort(distances[i])].flatten()\n            closest = list(labels[:self.k])\n            predictions[i] = max(closest, key=closest.count)\n        return predictions", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "60cf45997fe8bc2f89f84c3794cdb2313b45c30f", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "train_data = pd.read_csv(\"../input/train.csv\")\nX_train = train_data.iloc[:, 1:].as_matrix()\ny_train = train_data[\"label\"].as_matrix()\nX_test = pd.read_csv(\"../input/test.csv\").as_matrix()\n\nprint(X_train.shape, y_train.shape, X_test.shape)", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "0b1af109a712ab3c23cb292f613e99b572fcf5d6", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "classifier = KNearestNeighbours(k=3, samples_per_class=2000)\nclassifier.train(X_train, y_train)", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "3c1643a7919f3d70b55b2378305e7ad45d5a478c", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "### Here we plot the mean value of all examples for each class", "cell_type": "markdown", "metadata": {"_execution_state": "idle", "_uuid": "f737ad34afabc061ba67a961d9279792dd997d76", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "for target, features in classifier.group_means.items():\n    plt.subplot(1, 10, target + 1)\n    plt.imshow(features.reshape((28,28)))\n    plt.axis(\"off\")\n    plt.title(target)\nplt.show()", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "a6864b72bd8fdb312a529cd6fc8a58a94877e11a", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "batch = 2000\npredictions = []\nfor i in range(0, len(X_test), batch):\n    print(\"Computing tests {} to {}\".format(i, i + batch))\n    pred = classifier.predict(X_test[i: i + batch])\n    predictions += list(pred)", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "e8f198b613601687616d06822666fb3557810d7a", "collapsed": false}, "execution_count": null, "outputs": []}, {"source": "predictions = pd.DataFrame(predictions, dtype=int)\npredictions.index+=1\npredictions.index.name='ImageId'\npredictions.columns=['Label']\npredictions.to_csv('preds.csv', header=True)", "cell_type": "code", "metadata": {"_execution_state": "idle", "_uuid": "8c8c145b7cb11ef49f8991ad8819ca01fa9d80b6", "collapsed": false}, "execution_count": null, "outputs": []}], "nbformat": 4, "metadata": {"kernelspec": {"name": "python3", "display_name": "Python 3", "language": "python"}, "language_info": {"name": "python", "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "codemirror_mode": {"name": "ipython", "version": 3}, "version": "3.6.0", "mimetype": "text/x-python", "file_extension": ".py"}}, "nbformat_minor": 0}