{"cells":[{"cell_type":"markdown","metadata":{"_cell_guid":"74049e3d-a18e-459e-a1aa-3664d3cc4361"},"source":"Hey everyone, this is my first go at Kaggle competitions and Kernels.\n\nIn this Kernel, I implemented kNN classifier from scratch.\nAnd the results got 97.1% accuracy on public leaderboard."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"3c18419a-6dc3-41af-b4eb-55afbea5633a"},"outputs":[],"source":"import numpy as np\nimport matplotlib.pyplot as plt\nfrom collections import Counter\nimport time\n\n%matplotlib inline\nplt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots\nplt.rcParams['image.interpolation'] = 'nearest'\nplt.rcParams['image.cmap'] = 'gray'\n\n# load csv files to numpy arrays\ndef 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\nclass 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":"948f3147-acec-401e-bfec-124548a595e0"},"source":"Let's read `../input/train.csv` and `../input/test.csv` files to numpy arrays.\n\nPrint shapes of those arrays as a sanity check."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"f9bd5529-99c4-4dbe-bc9a-311e39059681"},"outputs":[],"source":"# runs for 35 seconds\ndata_dir = \"../input/\"\nX_train, y_train, X_test = load_data(data_dir)"},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"fe67f1cf-a304-4903-94c0-1ccce0bc615a"},"outputs":[],"source":"print(X_train.shape, y_train.shape, X_test.shape)"},{"cell_type":"markdown","metadata":{"_cell_guid":"7a68f23e-f59b-4dad-910a-c01905a79d18"},"source":"Visualize random samples from training data."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"075eb284-e1a6-46f1-8bde-7c1f9a2bb7e6"},"outputs":[],"source":"# runs for 10 seconds\nclasses = [\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]\nnum_classes = len(classes)\nsamples = 8\n\nfor 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\nplt.show()"},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"076ec3a8-82f1-49b0-b6ba-2bd2812d5c02"},"outputs":[],"source":"# just to visualize ith test image\nplt.imshow(X_test[2311].reshape((28, 28)))"},{"cell_type":"markdown","metadata":{"_cell_guid":"259c517b-38ab-4f62-8a94-e54c8e0a0c58"},"source":"Split testing data into batches as distances of 10,000 test images and\n60,000 train images won't fit in memory."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"cfbc29d8-3ec0-4f8f-ad31-5b684ccb9f41"},"outputs":[],"source":"# predict labels for batch_size number of test images at a time.\nbatch_size = 2000\n# k = 3\nk = 1\nclassifier = simple_knn()\nclassifier.train(X_train, y_train)"},{"cell_type":"markdown","metadata":{"_cell_guid":"2816f592-5f1c-4f0d-bd7b-92d4b27123d8"},"source":"As Kaggle kernels have 1200 seconds limit, I have divided the prediction step\ninto two cells each cell running for 13 minutes and saving prediction to `predictions`."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"e7ef1928-6a2f-4b82-a15f-778f3a1c44ee"},"outputs":[],"source":"# runs for 13 minutes\npredictions = []\n\nfor 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\nprint(\"Completed predicting the test data.\")"},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"e2c15b90-e5ad-4349-8810-9d3327538804"},"outputs":[],"source":"# runs for 13 minutes\n# uncomment predict lines to predict second half of test data\n\nfor 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\nprint(\"Completed predicting the test data.\")"},{"cell_type":"markdown","metadata":{"_cell_guid":"8a5d826a-d2a9-49f5-94c0-8c85208fb190"},"source":"After predicting and saving results in Python array, we dump our predictions to a csv file\nnamed `predictions.csv` which gets an accuracy of 97.114% on public leaderboard."},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"283d440a-bc32-4a92-bbf8-f04ac49b2829"},"outputs":[],"source":"out_file = open(\"predictions.csv\", \"w\")\nout_file.write(\"ImageId,Label\\n\")\nfor i in range(len(predictions)):\n    out_file.write(str(i+1) + \",\" + str(int(predictions[i])) + \"\\n\")\nout_file.close()"},{"cell_type":"code","execution_count":null,"metadata":{"_cell_guid":"b838e6c1-41c5-4b63-859e-8069c7d8c965"},"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}