{"cells":[{"metadata":{"_uuid":"4ab839ef88b7164f3e462d4b6b2b517c41780421","_cell_guid":"36f3a002-0ece-4663-a2ae-c4faa4b797a6"},"cell_type":"markdown","source":"# KNN Implementation \n\nhttps://www.kaggle.com/c/digit-recognizer\n"},{"metadata":{"_uuid":"95a590b3f9576bea92ce436b87cc625fc5049467","_cell_guid":"372536e0-483e-468e-a276-e5e0e2b1d4b2","trusted":true},"cell_type":"code","source":"import numpy as np \nimport pandas as pd \nimport matplotlib.pyplot as plt ","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"40eedc5785228d3b5b6b2d25aad1560dd2282ecd","_cell_guid":"e3552116-08bf-4f40-ba19-c92b3a0555fd"},"cell_type":"markdown","source":"Import dataset ( numpy arrays) from `../train.csv` and `../test.csv, will take about 10sec.\n\nand print out their shape to check data size."},{"metadata":{"_uuid":"a52a719e96c36384d35ae13154d1fa440591b804","_cell_guid":"3d9a24ea-b5cb-446b-acf5-b892702fe2db","trusted":true},"cell_type":"code","source":"\ndata_dir = \"../input/\"\n\n# load csv files to numpy arrays\ndef load_data(data_dir, train_row):\n    train = pd.read_csv(data_dir + \"train.csv\")\n    print(train.shape)\n#     print(train.head())\n#     print(train.shape)\n#     print(train.head())\n#     print(train[0:])\n    X_train = train.values[0:train_row,1:] # 取下标为1-784的列（pixel0 - pixel783）\n    y_train = train.values[0:train_row,0] # 取下标为0的列 (label)\n    \n    \n    Pred_test = pd.read_csv(data_dir + \"test.csv\").values  \n#     print(Pred_test.shape)\n#     print(pd.read_csv(data_dir + \"test.csv\").head())\n    return X_train, y_train, Pred_test\n\ntrain_row = 5000    # partially take the data, the max = 42000\nOrigin_X_train, Origin_y_train, Origin_y_test = load_data(data_dir, train_row)\n\n","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"f97ab1f5602d47c2d30a245db38e290e2f9df2ea","_cell_guid":"5ebd5585-9271-40db-988e-715cc0160840","trusted":true},"cell_type":"code","source":"print(Origin_X_train.shape, Origin_y_train.shape, Origin_y_test.shape)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"49475a65056182e8935ca05307035e9db6189d42","_cell_guid":"05e04925-5089-44a3-9936-1c5b92f7db31"},"cell_type":"markdown","source":"Plot the data"},{"metadata":{"_uuid":"00dc4a2e9ac784101d716889c3c05f02d1938557","_cell_guid":"b758a301-b318-4a66-9731-38b95a33c241","scrolled":true,"trusted":true},"cell_type":"code","source":"import matplotlib\nimport matplotlib.pyplot as plt\nrow = 3\n\n# print (X_train[row].reshape((28, 28)))\n\nprint (Origin_y_train[row])\n\nplt.imshow(Origin_X_train[row].reshape((28, 28)))\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"945556c15c967d6b4a72569dc28a694b8deafca8","_cell_guid":"acd4fdc4-ec23-47dd-99bb-4c3901e4fd36","trusted":true},"cell_type":"code","source":"classes = [\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]\nrows = 4\n\nprint(classes)\nfor y, cls in enumerate(classes):\n    idxs = np.nonzero([i == y for i in Origin_y_train])\n    idxs = np.random.choice(idxs[0], rows)\n    for i , idx in enumerate(idxs):\n        plt_idx = i * len(classes) + y + 1\n        plt.subplot(rows, len(classes), plt_idx)\n        plt.imshow(Origin_X_train[idx].reshape((28, 28)))\n        plt.axis(\"off\")\n        if i == 0:\n            plt.title(cls)\n        \n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"4b7f62bf8b331da61a02e3f2030524d749ec4bc8","_cell_guid":"59ccc732-2b1f-4085-95c3-e83f53a86ead"},"cell_type":"markdown","source":"Divide the imported dataset into 20% training set（8400），80% test set（33600）"},{"metadata":{"_uuid":"9c238cd880be647f0f78b900aa9a51a9939c9140","_cell_guid":"d0a5f6d9-613f-47c7-b1fa-c3c6a8e8185f","trusted":true},"cell_type":"code","source":"from sklearn.model_selection import train_test_split\n\nX_train,X_test, y_train, y_test = train_test_split(Origin_X_train,\n                                                   Origin_y_train,\n                                                   test_size = 0.2,\n                                                   random_state = 0)\n\nprint(X_train.shape, X_test.shape, y_train.shape, y_test.shape)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"6d91707613d4d2159a5751d79fd012fb3e929a11","_cell_guid":"bfa00f97-9b70-4083-bd74-655881d04321"},"cell_type":"markdown","source":"\nTo train the KNN model\n"},{"metadata":{"_uuid":"c8fbdf6be4b25de80099f9a1afd5553d35dfa19c","_cell_guid":"49d225a9-ebc7-42ff-aa98-67395f7c1904","trusted":true},"cell_type":"code","source":"from sklearn.metrics import accuracy_score\n\nclass knn():\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        \n\n    def predict(self, X, num, k=3):\n        dataSet = X_train\n        labels = y_train\n      \n        dataSetSize = dataSet.shape[0]\n        diffMat = np.tile(X,(dataSetSize,1)) - dataSet\n        sqDiffMat = diffMat**2\n        sumDiffMat = sqDiffMat.sum(axis=1)\n        distances = sumDiffMat**0.5\n        sortedDistances = distances.argsort()\n        classCount = {}\n        \n        for i in range(k):\n            vote = labels[sortedDistances[i]]\n            classCount[vote] = classCount.get(vote,0) + 1\n        max = 0\n        ans = 0\n        for k,v in classCount.items():\n            if(v>max):\n                ans = k\n                max = v\n#         print(\"test #\"+ str(num+1) + \" prediction is \" + str(ans)\n        return(ans)\n\n\nclassifier = knn()\nclassifier.train(X_train, y_train)\n\n\n# clf = KNeighborsClassifier(n_neighbors=5)\n# clf.fit(trainX, trainY)\n# predictions = clf.predict(validX)\n# accuracy = accuracy_score(validY, predictions)\n# print(\"the accuracy of kNN is : %f\" % accuracy)\n\nmax = 0\nans_k = 0\n\nfor k in range(1, 4):\n    print ('when k = ' + str(k) + ', start training')\n    predictions = np.zeros(len(y_test))\n    for i in range(X_test.shape[0]):\n        if i % 500 == 0:\n            print(\"Computing  \" + str(i+1) + \"/\" + str(int(len(X_test))) + \"...\")\n        output = classifier.predict(X_test[i], i, k)\n        predictions[i] = output\n    \n#     print(k, predictions)\n#     predictions.shape\n    accuracy = accuracy_score(y_test, predictions)\n    print ('k = '+ str(k) , ' accuracy =' + str(accuracy))\n    if max < accuracy:\n        ans_k = k\n        max = accuracy\n        \n    ","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"884d21ce22caaebc8a0d49da6bb4f5f8fba38636","_cell_guid":"cbb3cae6-6eab-4296-a742-e7fb267dbcc7","trusted":true},"cell_type":"code","source":"print(y_test)\nprint(predictions)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"4ae5d0294c0c3e21d09fa9c8a18f07ec6689b668","_cell_guid":"ebfcbbed-04da-45d7-ade2-7762695c4a7a","trusted":true},"cell_type":"code","source":"k = 3\npredictions = np.zeros(Origin_y_test.shape[0])\nfor i in range(Origin_y_test.shape[0]):\n    if i % 500 ==0:\n        print(\"Computing  \" + str(i+1) + \"/\" + str(int(len(Origin_y_test))) + \"...\")\n    predictions[i] = classifier.predict(Origin_y_test[i], i, k)\n","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"10e5ad5da5109bba0b1201a52a83bb2e8f8a8564","_cell_guid":"b190b95a-1f07-45c5-b73f-346a5807dd24","trusted":true},"cell_type":"code","source":"print (predictions[200])\nplt.imshow(Origin_y_test[200].reshape((28, 28)))","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"eb84f7341d8b696530d09227102811a137666507","_cell_guid":"1ea02f86-7d8c-4173-93b9-f4d4d1d7b709"},"cell_type":"markdown","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."},{"metadata":{"_uuid":"75728007194f0346c51c04c462d6107f5b430015","_cell_guid":"cf8b050b-bd3c-4a61-987b-a0de4df4b7a4","trusted":true},"cell_type":"code","source":"print(len(predictions))\nout_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()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"2fabf4c33a7aa24e928d326081e499edb3af05f2"},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}