{"cells":[{"metadata":{"_uuid":"ef259b70ae73fce47a648d210dd43cd3405db06f"},"cell_type":"markdown","source":"Hello, and thank you for reading my Kernal submission for the Google Quick Draw image recogniztion challenge. \n\nThis kernel is dedicated to taking a non-standard approach to 2-D  image recogniztion for an exercise in the merits and drawbacks of potential innovations.\nThe approach I will take is as follows: \n1.  Scale the drawings down into smaller resolutions\n2. Convert the drawings from 2-D arrys to 1-D arrays of pixel intensity, 1 and 0 (present or not), where the index corresponds to a pixel location in a NxN grid\n3. Convert each 1-D array into a row, where each column is a pixel location, and thus a factor for training. *\n4. Train various mdoels on these factors, and the word is a target, then predict future targets. \n\nThis approach is not typical from what I've seen other talented Kagglers take - which is why I wanted to do it. I can immeidately identify possible reasons this will go horribly, horribly wrong. I will discuss these reasons at the end, but for now items with asterisks that could be potentially problematic. \n\nFor now, let's get going. First - let's import and inspect the simplified data:"},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"scrolled":true},"cell_type":"code","source":"# This Python 3 environment \nimport pandas as pd\nimport numpy as np  \nimport os\nimport json\nimport copy\nfrom sklearn.externals import joblib\n\n# Input data files are available in the \"../input/\" directory.\n# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory\n\nimport os\nprint(os.listdir(\"../input/\"))\n\n\n# Any results you write to the current directory are saved as output.","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"5d44b734334c811df5a385f4677d26861b6ed361"},"cell_type":"markdown","source":"One by one, I'll select a few rows from a few categories of words and construct a primary dataframe, df. "},{"metadata":{"trusted":true,"_uuid":"57c30c71c5915887cd33d26943cc5b5d88e2b042"},"cell_type":"code","source":"df = pd.DataFrame()\nfiles_directory = sorted([f for f in os.listdir(\"../input/train_simplified\")]) # Sort the directory first\ntraining_categories = len(files_directory) #340\ncategory_samples = 60\ntest_sample_cats = 112199 # Number of rows to load from the test set\ndownsize = 25 # Resolution of images, max is 255 but please don't do this unless you've got time to kill / compuational power\nzero_lst = np.zeros(downsize**2, dtype=int)\n\ndf_from_each_file = [pd.read_csv(\"../input/train_simplified/\"+f, nrows=category_samples) for f in files_directory]\ndf = pd.concat(df_from_each_file, ignore_index=True)\n\nprint(\"From {a} to {z}..\".format(a=files_directory[0], z=files_directory[training_categories-1]))\nprint(\"-------\")\n\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"8d402bf33a1729a6181d15494ef56273517e7803"},"cell_type":"markdown","source":"Great, do we've got df which contains all the information about the drawings, with a small sample from the number of categories defined by \"training_categories\".\n\nNow, I only want to include correctly identified drawings. Furthermore, I want to make sure that the lists are being evaluated as python lists, not as strings which is what the default behavior of pandas is. For this excersize, I also only include data on the drawings and nothing else. We lose information, but we save some memory which is a very real objective on my current machine, but not so much for others. "},{"metadata":{"trusted":true,"_uuid":"19cffd62514c7cf113ca3b6dec3f9585d918f1fc"},"cell_type":"code","source":"df = df[df[\"recognized\"]==True]\ndf['drawing'] = df['drawing'].apply(json.loads)\ndf = df[[\"drawing\",\"word\"]].reset_index(drop=True)\nprint(df.info())","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"01b946e472982f2fde3a8d636126e6ec6850bf32"},"cell_type":"markdown","source":"This is where things start to deviate from a typical approach. I will now define a series of functions. The first function will create a list of point coordiate tuples. The next will transform the tuples into a lower resolution, scaled down to \"downsize\" number of pixels in width and height. The last function will convert the \"drawing\", now a collection of scaled points, to a 1-D array of pixel intensity. \n"},{"metadata":{"trusted":true,"_uuid":"8edab49d71c43b5e2191bfd4f91bd4a85ef3d877"},"cell_type":"code","source":"## Gather all the points\ndef pointList(draw_list):\n    point_list = []\n    for n in range(0,len(draw_list)):\n        for x,y in list(zip(draw_list[n][0],draw_list[n][1])):\n            point_list.append((x,y))\n    return point_list","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"ae3246479459a2e7904faf242a08f2c0cd1684ae"},"cell_type":"code","source":"## Bound the points, and scale\ndef transform(pt_list):\n    xlist = []\n    ylist = []\n    scl_list = []\n    for x,y in pt_list:\n        xlist.append(x)\n        ylist.append(y)\n    xmx = max(xlist)\n    xmn = min(xlist)\n    ymx = max(ylist)\n    ymn = min(ylist)\n    for x,y in pt_list:\n        try:\n            x_scl = round((x-xmn)*downsize/(xmx - xmn))\n            y_scl = round((y-ymn)*downsize/(ymx - ymn))\n        except ZeroDivisionError:\n            x_scl = round((x-xmn)*downsize/(xmx - xmn + 0.0001))\n            y_scl = round((y-ymn)*downsize/(ymx - ymn + 0.0001))\n        scl_list.append((x_scl, y_scl))\n    return scl_list","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"92eaa50f3d468237fe6b09ac70068f16ef077bad"},"cell_type":"markdown","source":"The \"drawing\" column of the simplified data is a list. The Nth element of the list is the Nth stroke of the user. A stroke is defined by another list. For each stoke, a list with two elements is created. The first element is the x value of the points along that stroke, and the second element is the y values along that stroke. For example, a \"drawing\" data point may be a list with three elements.  The first element is a list with two elements, the x- and y-points created during that stroke. The next stoke has a different set of x- and y-values, etc. The raw dataset also has a timestamp of each point, but I don't need that for this exercize. \n\nThe following function will take the drawing data, and convert it to a single list of either 0 or 1. A zero means a pixel is not present, and a 1 means a pixel is present. The length of the list is downsize^2 (30^2)elements. The positional index corresponds uniquely to a point in 2-D space. 0 is the origin, and 900 is the point(30,30).\n\nThe 1-D vector array is mostly zeroes. So I only replace it with a 1 where a pixel exists. "},{"metadata":{"trusted":true,"_uuid":"2812e5fdad6507fd5c06e0300061d25495e3df27"},"cell_type":"code","source":"def ConvertTo1D(scl_pt_list):\n    indx_lst = copy.copy(zero_lst)\n    for x,y in scl_pt_list:\n            i = x + downsize*(y-1)\n            indx_lst[i-1] = 1\n    return indx_lst","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"153268552293157827c02c5544a5751dfbefca0c"},"cell_type":"markdown","source":"Now I simply apply these function to every drawing in the df. The power of pandas is palpable. We also convert each vector element to a new column in a new training df. \n"},{"metadata":{"trusted":true,"_uuid":"d51171a368110af3281298bf3b99d01336fe3971"},"cell_type":"code","source":"print(\"Preparing df_vec..\")\ndf_vec = df[\"drawing\"].apply(pointList\n                     ).apply(transform\n                     ).apply(ConvertTo1D\n                     ).apply(pd.Series)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"6e57e7732b85742539fbfb9ecbac7d455a36f625"},"cell_type":"markdown","source":"Now we are ready to train a series of models. I will choose a few here, then use the best one to predict drawings on our test set. I like to do at least two-fold cross valdiations, but more folds should yield a more accuracte picture at additional computational cost. "},{"metadata":{"trusted":true,"_uuid":"eea584272ef74be4450456e9fb25fa6da421f55a"},"cell_type":"code","source":"print(\"Learning..\")\nX = df_vec\ny = df[\"word\"]\nprint(\"{} accuracy would be better than guessing\".format(round(1/training_categories, 4)))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"3c027ec19aab19816c577ceb90a84d8e03fcfd16"},"cell_type":"code","source":"# Let's get learning!\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.ensemble import RandomForestClassifier\nfrom sklearn.svm import LinearSVC\nfrom sklearn.linear_model import LogisticRegression\nfrom sklearn.linear_model import Perceptron\nfrom sklearn.naive_bayes import GaussianNB\nfrom sklearn.tree import DecisionTreeClassifier\nimport warnings\nwarnings.simplefilter(action='ignore', category=FutureWarning)\n\nclassifiers = {#\"K-Nearest Neighbors\" : KNeighborsClassifier(n_neighbors=2),\n               \"Random Forest\" : RandomForestClassifier(n_estimators=10, random_state=0),\n               #\"Support Vector Clf\" : LinearSVC(penalty=\"l2\", random_state=0),\n               \"Logistic Regression\" : LogisticRegression(penalty=\"l2\", random_state=0),\n               #\"Perceptron\" : Perceptron(penalty=\"l2\", random_state=0),\n               #\"Naive Bayes\" : GaussianNB(),\n               #\"Decision Tree\" : DecisionTreeClassifier(random_state=0)\n               }","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"7b8c06dc7fabcdb88831ec101fc78f5a62b9075e"},"cell_type":"markdown","source":"Please note that this process below takes a bit of computational time. From running this kernel a few times, I already knmow which model will perform best. If you would like to try this kernel yourself with different parameters, make sure you un-comment these codes after you make a fork. "},{"metadata":{"trusted":true,"_uuid":"917bfa8397c7b5f5df1073f8140ae71773a5a406"},"cell_type":"code","source":"# Find best Test_Train test accuracy\n\nfrom sklearn.model_selection import cross_val_score\nfrom sklearn.model_selection import cross_val_predict\n\nsplits=2\nrounding_prec = '.4f'\nclfy_acc = []\nfor name,clfy in classifiers.items():\n    res = format(cross_val_score(clfy, X, y, cv=splits).mean(), rounding_prec)\n    print(\"{s}-fold split: {n} test accuracy = {r}\".format(s=splits, n=name, r=res))\n    clfy_acc.append(res)\n  \n# Save the best trained model\nprint(\"..Saving..\")\nclf_acc_finder = list(zip(classifiers.keys(), clfy_acc))\nfor cl,ac in clf_acc_finder:\n    if ac == max(clfy_acc):\n        fitted_clf = classifiers[cl].fit(X, y)\n#        joblib.dump(classifiers[cl], \n#                            \"{c}_Trained_{cat}_by_{sam}.joblib\".format(c=str(cl),\n#                                                                       cat=training_categories,\n#                                                                       sam=category_samples)) \n        print(\"Model Selected! {c} with {a} testing accuracy:\".format(c=cl, a=ac))","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"032741022b8cdf8b6ebf3bba38f8903a3eaeceb3"},"cell_type":"markdown","source":"Some of the models have better accuracy than just randomly guessing. Now is the time to import our test set, convert the drawings, and throw it into the correct model. Due to  computational limitations, I practice with a quantity called \"test_sample_cats\" which limits the test set to work with. For submission, we have to use the full set. \n\nFor the real submission, I import my pre-trained model."},{"metadata":{"trusted":true,"_uuid":"31a9a381a53c3ec3ea47396fec8d504e289a52c5"},"cell_type":"code","source":"print(\"..Loading & transforming test data..\")\ntest_df = pd.read_csv(\"../input/test_simplified.csv\", nrows=test_sample_cats)\nX_test = test_df[\"drawing\"].apply(json.loads\n                          ).apply(pointList\n                          ).apply(transform\n                          ).apply(ConvertTo1D\n                          ).apply(pd.Series)\n\nX_test_keys = test_df[\"key_id\"]\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"b857dc429d18b291dde7235f92fb92c56f769312","scrolled":true},"cell_type":"code","source":"## Load in the model\n\n# model_loaded = os.listdir(\"../input/training-vector-representations-of-google-q-d/\")[-2] # Picks the model out\n# clf_loaded = joblib.load(\"../input/training-vector-representations-of-google-q-d/\"+str(model_loaded))\n# print(\"..{} model selected!\".format(str(model_loaded)[0:-24]))\nprint(\"..Predicting..\")\n\npred = fitted_clf.predict(X_test)\npred = [p.replace(\" \", \"_\") for p in pred]","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"4d98189c0b88ccc89ac92b633e5d7cb05454260d"},"cell_type":"markdown","source":"Finally, let's prepare the predictions for submission to the challenge by setting up a predictions dataframe. At this time, I'm not sure how to predict multiple targets, so I just predict a single label. *"},{"metadata":{"trusted":true,"_uuid":"4ed3b856821b4b06e20c5ab70c734f9fa6b079ab"},"cell_type":"code","source":"df_pred = pd.DataFrame.from_dict({\"key_id\":X_test_keys, \n                                  \"word\":[\"{pr}\".format(pr=p) for p in pred]}, orient=\"columns\")\n\nprint(\"Submission shape: {s}\".format(s=df_pred.shape))\nprint(\"Number of possible classes: {n}\".format(n=training_categories))\n\ndf_pred.to_csv(\"SubmissionMG.csv\", index=False)\nprint(\"Sucessfully created file\") ","execution_count":null,"outputs":[]},{"metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","collapsed":true,"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","trusted":false},"cell_type":"markdown","source":"Thank for you reading my Kernel, I hope I have inspired you to try something new even if the results don't get you into the top leaderboard. An accuracy of 1/(# of categories) is the same as randomly guessing, so my opinion is that if it's better, it's better.\n\nAs I mentioned early on, there are a multitude of ways this algorithm can be improved. The largest problem is that since each image is reduced to a string of pixels, rotations, horizontal,  and vertical translations will result in different combinations of columns being \"activated\". When taken all togther, it'll just be a superimposition of all the images of that word, which will not be very effective. One solution I propose is to some how make sure the images are alinged first. Second, I can modify the algorithm to predict multiple values instead of just one. This should also improve accuracy drastically. \n\nIt may also be more efficient to export a trained model in pne phase, and use it on a pre-processed test set in a second phase. I am currently investigating this approach. \n\nPlease feel free to fork and modify this algorithm by changing the number of categories imported, number of sample in each category, the number of testing samples, or whatever you want - let me know where you take this idea. I welcome constructive feedback and comments. \n\n**Thank you again**\n\nMichael Greene"}],"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}