{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"code","source":"# This Python 3 environment comes with many helpful analytics libraries installed\n# It is defined by the kaggle/python Docker image: https://github.com/kaggle/docker-python\n# For example, here's several helpful packages to load\n\nimport numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n\n# Input data files are available in the read-only \"../input/\" directory\n# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory\n\nl_filenames = []\n\nimport os\nfor dirname, _, filenames in os.walk('/kaggle/input'):\n    for filename in filenames:\n        print(os.path.join(dirname, filename))\n        l_filenames.append(os.path.join(dirname, filename))\n        \n\n        \n\n# You can write up to 20GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using \"Save & Run All\" \n# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:04:04.151289Z","iopub.execute_input":"2021-11-29T19:04:04.151920Z","iopub.status.idle":"2021-11-29T19:04:04.161658Z","shell.execute_reply.started":"2021-11-29T19:04:04.151875Z","shell.execute_reply":"2021-11-29T19:04:04.160771Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Facebook V: Predicting Check Ins\n\nFacebook created an artificial world consisting of more than 100,000 places located in a 10 km by 10 km square. Data was fabricated to resemble location signals coming from mobile devices, giving you a flavor of what it takes to work with real data complicated by inaccurate and noisy values. Inconsistent and erroneous location data can disrupt experience for services like Facebook Check In.\n\n## The task\n\nBuild a model that shall predict which business a user is checking into based on their location, accuracy, and timestamp. \nFor a given set of coordinates, the task is to return a ranked list of the most likely places the customers checked in. \n\n## The data sets\n\ntrain.csv, test.csv \n- row_id: id of the check-in event\n- x y: coordinates\n- accuracy: location accuracy \n- time: timestamp\n- place_id: id of the business, this is the target you are predicting\n\nsample_submission.csv - a sample submission file in the correct format with random predictions\n\n## Further notes\n\nIn the competition the participants were given around 30 million (simulated) check-ins on Facebook in a 10km by 10km grid. The goal is to build a model that predicts what business a user checks into based on spatial and temporal information. The difficult part is that there are around 100.000 different classes (place_id’s) so most supervised learning techniques won’t work on the entire dataset. However most classes are clustered in only certain parts of the grid so the idea is to select a sub-square within the grid and try to classify within small square. First I’ll do some exploratory data analysis in the smaller square then I’ll use a random forest algorithm for prediction and finally, I’ll analyze the results.\n\n## Approach:\n\n1. Exploratory data analysis in the sub-square\n2. Use of different classification algorithms for prediction \n3. Analysis of the results\n\n\n\n\n# 1. Exploratory data anylsis in sub-square","metadata":{}},{"cell_type":"code","source":"# load datasets\ndf_train = pd.read_csv(str(l_filenames[0]))\ndf_test = pd.read_csv(str(l_filenames[2]))\ndf_sample=pd.read_csv(str(l_filenames[1]))\n","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:04:04.450293Z","iopub.execute_input":"2021-11-29T19:04:04.450633Z","iopub.status.idle":"2021-11-29T19:05:04.567979Z","shell.execute_reply.started":"2021-11-29T19:04:04.450581Z","shell.execute_reply":"2021-11-29T19:05:04.567015Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# import all modules needed in the following\nimport tensorflow\nimport keras\nimport sklearn\nimport xgboost as xgb\nimport seaborn as sns\nimport matplotlib as mpl\nimport matplotlib.pyplot as plt","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:04.569963Z","iopub.execute_input":"2021-11-29T19:05:04.570325Z","iopub.status.idle":"2021-11-29T19:05:10.677196Z","shell.execute_reply.started":"2021-11-29T19:05:04.570276Z","shell.execute_reply":"2021-11-29T19:05:10.676448Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# inspect and clean datasets\n\ndf_train = df_train[((df_train[\"x\"] != np.NaN) | (df_train[\"x\"] != 0)) & ((df_train[\"y\"] != np.NaN) | (df_train[\"y\"] != 0))]\nprint(df_train)\n\n\n# print max and min of each values\nprint(\"Range of x: \", df_train.x.max(), df_train.x.min())\nprint(\"Range of y: \",df_train.y.max(), df_train.y.min())\nprint(\"Range of time: \",df_train.time.max(), df_train.time.min())\nprint(\"Range of place_id: \",df_train.place_id.max(), df_train.place_id.min())\n","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:10.678956Z","iopub.execute_input":"2021-11-29T19:05:10.679337Z","iopub.status.idle":"2021-11-29T19:05:12.153672Z","shell.execute_reply.started":"2021-11-29T19:05:10.679289Z","shell.execute_reply":"2021-11-29T19:05:12.152676Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Data cleaning and selection\n\nThe data set is very large (29.1 Million check ins). For testing methods I randomly choose a subset of the data based on the location (x, and y coordinates) of the samples. I will randomly choose \n\nIn addition, the time column (which is currently numeric) shall be transformed to hour, day, week, month, and year.\n","metadata":{}},{"cell_type":"code","source":"# selection of sub-square of the datat grid. Maximum in x and y coordinates is 10, minimum is 0\ndf_sub = df_train[((df_train.loc[:,\"x\"] > 2.5) & (df_train.loc[:,\"x\"] < 2.75)) &\n                  ((df_train.loc[:,\"y\"] > 2.5) & (df_train.loc[:,\"y\"] < 2.75))]\n\n# transformation to extract temporal features\ndf_sub.loc[:,\"hour\"] =    (df_sub.loc[:,\"time\"]/60).round().mod(24).astype(int)\ndf_sub.loc[:,\"weekday\"] = (df_sub.loc[:,\"time\"]/(60*24)).round().mod(7).astype(int)\ndf_sub.loc[:,\"month\"] =   (df_sub.loc[:,\"time\"]/(60*24*30)).round().mod(12).astype(int) #month-ish\ndf_sub.loc[:,\"year\"] =    (df_sub.loc[:,\"time\"]/(60*24*365)).astype(int)\ndf_sub.loc[:,\"day\"] =     (df_sub.loc[:,\"time\"]/(60*24)).round().mod(365).astype(int)\n\n# number of different businesses\nprint(\"Distinct labels: \", df_sub.place_id.nunique())","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:12.156200Z","iopub.execute_input":"2021-11-29T19:05:12.157071Z","iopub.status.idle":"2021-11-29T19:05:12.346716Z","shell.execute_reply.started":"2021-11-29T19:05:12.157024Z","shell.execute_reply":"2021-11-29T19:05:12.345846Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Preliminary plot of the data","metadata":{}},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(15,15)})\nsns.scatterplot(data=df_sub, x=\"x\", y=\"y\", hue=\"place_id\", palette = \"Accent\", legend = False)","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:12.348232Z","iopub.execute_input":"2021-11-29T19:05:12.348857Z","iopub.status.idle":"2021-11-29T19:05:13.735356Z","shell.execute_reply.started":"2021-11-29T19:05:12.348810Z","shell.execute_reply":"2021-11-29T19:05:13.734679Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It is visible that in the classes in the data subset are not well separated.\n\nLet us now introduce the time feature to the scatterplot and transform it to a 3d plot.\n\nI will try to use the *time* column, followed by the distinct time features that have been created above: **hour**, **minute**, and **day**","metadata":{}},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(18,20)})\n#sns.set(style = \"darkgrid\")\n\nfig = plt.figure()\nax = fig.add_subplot(111, projection = '3d')\n\nx = df_sub['x']\ny = df_sub['y']\nz = df_sub['time']\nc = df_sub[\"place_id\"]\n\nax.set_xlabel(\"x\")\nax.set_ylabel(\"y\")\nax.set_zlabel(\"time\")\n\nax.scatter(x, y, z, c=c, cmap = \"hsv\")\n\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:13.736502Z","iopub.execute_input":"2021-11-29T19:05:13.736932Z","iopub.status.idle":"2021-11-29T19:05:14.665512Z","shell.execute_reply.started":"2021-11-29T19:05:13.736889Z","shell.execute_reply":"2021-11-29T19:05:14.664548Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The 3d plot shows a more distinct distribution of classes. However, it is still visible that the classes are not at all separated.\n\nLets try it with the **hour** as well as **weekday** feature, to see if the classes seem better separated when the examples are arranged based on the hour or the wekday of visit.\n\n","metadata":{}},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(18,20)})\n#sns.set(style = \"darkgrid\")\n\nfig = plt.figure()\nax = fig.add_subplot(111, projection = '3d')\n\nx = df_sub['x']\ny = df_sub['y']\nz = df_sub['hour']\nc = df_sub[\"place_id\"]\n\nax.set_xlabel(\"x\")\nax.set_ylabel(\"y\")\nax.set_zlabel(\"time\")\n\nax.scatter(x, y, z, c=c, cmap = \"hsv\")\n\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:14.666749Z","iopub.execute_input":"2021-11-29T19:05:14.666974Z","iopub.status.idle":"2021-11-29T19:05:15.566717Z","shell.execute_reply.started":"2021-11-29T19:05:14.666946Z","shell.execute_reply":"2021-11-29T19:05:15.566085Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(18,20)})\n#sns.set(style = \"darkgrid\")\n\nfig = plt.figure()\nax = fig.add_subplot(111, projection = '3d')\n\nx = df_sub['x']\ny = df_sub['y']\nz = df_sub['time']\nc = df_sub[\"weekday\"]\n\nax.set_xlabel(\"x\")\nax.set_ylabel(\"y\")\nax.set_zlabel(\"time\")\n\nax.scatter(x, y, z, c=c, cmap = \"hsv\")\n\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:15.567694Z","iopub.execute_input":"2021-11-29T19:05:15.568449Z","iopub.status.idle":"2021-11-29T19:05:16.495466Z","shell.execute_reply.started":"2021-11-29T19:05:15.568416Z","shell.execute_reply":"2021-11-29T19:05:16.494576Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It is visible that the weekday feature leads to much less visible groups of data points from either classes, compared to the hour feature.\n\nLet us have a quick look at only classes that have a minimum of **n assignments**. This is important because some classes only have very few examples assigned to them, which might distort the classification.\n\nFor this example, I will only print the class assignments for classes with **minimum 200 examples being assigned to them.**","metadata":{}},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(18,20)})\n#sns.set(style = \"darkgrid\")\nplace_counts = df_sub.place_id.value_counts()\nmask = (place_counts[df_sub.place_id.values] >= 200).values\ndf_only = df_sub.loc[mask]\n\nfig = plt.figure()\nax = fig.add_subplot(111, projection = '3d')\n\nx = df_only['x']\ny = df_only['y']\nz = df_only['hour']\nc = df_only[\"place_id\"]\n\nax.set_xlabel(\"x\")\nax.set_ylabel(\"y\")\nax.set_zlabel(\"time\")\n\nax.scatter(x, y, z, c=c, cmap = \"hsv\")\n\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:16.496799Z","iopub.execute_input":"2021-11-29T19:05:16.497830Z","iopub.status.idle":"2021-11-29T19:05:17.139677Z","shell.execute_reply.started":"2021-11-29T19:05:16.497784Z","shell.execute_reply":"2021-11-29T19:05:17.138776Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Result from preliminary plots\n\nThe preliminary scatterplots show no clear decision boundary. The classes are not well separated on a 2-dimensional level.\n\nHowever, adding a temporal feature, it is visible that especially on the hourly resolution, there are some classes which are more present in certain hours.\n\n## Accuracy distribution\n\nThe accuracy of the class assignment of the check ins given in the dataset isn’t exactly defined. From first principles, we could think of it a few ways -\n\n- Error on some arbitary scale. This seems unlikely, since the max is > 1,000.\n- Error on the same scale as x and y. Now, this could be an estimated radius (with the x and y values as the center); either normal or squared.\n\nPlot the distribution of accuracy aswell as a default kernel density estimation plot:\n","metadata":{}},{"cell_type":"code","source":"# histogramm & KDE of the accuracy feature\nsns.set(rc={'figure.figsize':(15,15)})\nsns.displot(data = df_sub, x=\"accuracy\", bins=50)\nsns.displot(data=df_sub, x=\"accuracy\", kind=\"kde\")","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:17.142317Z","iopub.execute_input":"2021-11-29T19:05:17.142558Z","iopub.status.idle":"2021-11-29T19:05:18.275005Z","shell.execute_reply.started":"2021-11-29T19:05:17.142528Z","shell.execute_reply":"2021-11-29T19:05:18.274019Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It looks like we have three peaks (two peaks if we exclude the examples with an accuracy value of 0. Are there underlying parameters in the simulation at these peaks?\n\nWe might also think that there are different measures of accuracy at different locations.\n\nLet’s see how even the accuracy is distributed over x and y.\n","metadata":{}},{"cell_type":"code","source":"# scatterplot of the accuracy in 3d scale\nsns.set(rc={'figure.figsize':(18,20)})\n#sns.set(style = \"darkgrid\")\n\nfig = plt.figure()\nax = fig.add_subplot(111, projection = '3d')\n\nx = df_sub['x']\ny = df_sub['y']\nz = df_sub['accuracy']\n\nax.set_xlabel(\"x\")\nax.set_ylabel(\"y\")\nax.set_zlabel(\"time\")\n\nax.scatter(x, y, z,color = \"blue\")\n\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:18.276225Z","iopub.execute_input":"2021-11-29T19:05:18.276449Z","iopub.status.idle":"2021-11-29T19:05:19.125207Z","shell.execute_reply.started":"2021-11-29T19:05:18.276420Z","shell.execute_reply":"2021-11-29T19:05:19.124235Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The accuracy distribution seems visually random with a few accuracy outliers and overall low values.\n\nLet us look at the outliers and if there are centers of these outliers. Outliers are hereby defined as examples with accuracy > 250.\n\n","metadata":{}},{"cell_type":"code","source":"# scatterplot of classes  (businesses) within the subgrid\nsns.set(rc={'figure.figsize':(15,15)})\nsns.scatterplot(data=df_sub[df_sub.accuracy >250], x=\"x\", y=\"y\", hue=\"accuracy\", palette = \"Accent\", legend = False)","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:19.126700Z","iopub.execute_input":"2021-11-29T19:05:19.127032Z","iopub.status.idle":"2021-11-29T19:05:19.546450Z","shell.execute_reply.started":"2021-11-29T19:05:19.126988Z","shell.execute_reply":"2021-11-29T19:05:19.545578Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Results of the accuracy analysis:\n\nThere are no centers of particularly high / low accuracy of the class assignments in the data on geographic scale.\n\nGiven the interpretation of the accuracy, it could be that the examples with high accuracy rating (= higher probability of the label assignment being wrong) distort the quality of the classification training and can lead to a model that systematically misclassifies examples. \n\nThis will later be tested via a grid search using a threshold to **clude training examples** with an accuracy **above**his certain threshold.  \n\n\n## Time distribution\n\nLet us now investigate the distribution of the time features **hour**, **weekday**, and **day** of the year, to investigate if there are significant peaks in the data","metadata":{}},{"cell_type":"code","source":"# histogramm & KDE of the time features:\nsns.set(rc={'figure.figsize':(15,15)})\n\n# hour\nsns.displot(data = df_sub, x=\"hour\", bins=24)\nsns.displot(data=df_sub, x=\"hour\", kind=\"kde\")\n\n# weekday\nsns.displot(data = df_sub, x=\"weekday\", bins=7)\nsns.displot(data=df_sub, x=\"weekday\", kind=\"kde\")\n\n# day\nsns.displot(data = df_sub, x=\"day\", bins=24)\nsns.displot(data=df_sub, x=\"day\", kind=\"kde\")","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:19.547952Z","iopub.execute_input":"2021-11-29T19:05:19.548687Z","iopub.status.idle":"2021-11-29T19:05:22.466527Z","shell.execute_reply.started":"2021-11-29T19:05:19.548635Z","shell.execute_reply":"2021-11-29T19:05:22.465506Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"While there is no specific distribution recognizable in the weekday feature (similar number of sign ins per weekday) there is a peak in the afternoon hours recognizable as well as a higher number of sign ins in the first half of the year.\n\n\n## Place ID Distribution\n\nNow that we have some background on time, accuracy and (sideways) on x and y let’s look at place_id.\n\nFirst, a quick check. Sometimes ID values aren’t really uniformly distributed.","metadata":{}},{"cell_type":"code","source":"# histogramm & KDE of the time features:\nsns.set(rc={'figure.figsize':(15,15)})\n\n# hour\nsns.displot(data = df_sub, x=\"place_id\", bins=50)\nsns.displot(data=df_sub, x=\"place_id\", kind=\"kde\", bw_adjust=1.5)","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:22.467749Z","iopub.execute_input":"2021-11-29T19:05:22.467976Z","iopub.status.idle":"2021-11-29T19:05:23.527425Z","shell.execute_reply.started":"2021-11-29T19:05:22.467948Z","shell.execute_reply":"2021-11-29T19:05:23.526788Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The distribution clearly has two peaks, looking like a bimodal distribution. There seem to be certain places that have particularly high amounts of sign ins.\n\nLet us group the data by the place ID and investigate the distribution of the grouped data, i.e. distribution of places having x sign ins in our sub square.","metadata":{}},{"cell_type":"code","source":"# distribution of grouped data\ngrouped_id = df_sub.groupby(\"place_id\").count().sort_values(by=\"row_id\")\ngrouped_id = grouped_id[grouped_id[\"row_id\"]!=0]\nprint(grouped_id)\n\n\n# grouped_id\nsns.displot(data = grouped_id, x=\"row_id\", bins=50)\nsns.displot(data=grouped_id, x=\"row_id\", kind=\"kde\")","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:23.528913Z","iopub.execute_input":"2021-11-29T19:05:23.530471Z","iopub.status.idle":"2021-11-29T19:05:24.598965Z","shell.execute_reply.started":"2021-11-29T19:05:23.530427Z","shell.execute_reply":"2021-11-29T19:05:24.598086Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It becomes visible that there is a majority of place_id's that receive very few check ins, while a few place_ids contain the majority of the check ins.\n\nThe distribution could be similar to poisson or pareto distribution.\n\n\n\n\n## K-Nearest-Neighbours\n\nAs a first classification algorithm, we will run a KNN algorithm on the sub-square of data using a grid of k parameters. This might be used as benchmark for later classification approaches.\n\nThe following cell contains an **algorithm to classify the examples within that sub-square of the grid** using a validation set.\n\n### Data preparation for classification algorithm\n\nSince there are extremely many classes with very few check_ins, for the classification model we will **remove** the examples which belong to **classes that are only classified a few times *th***. The magnitude of ***th*** will be treated as a hyperparameter.\n\nIn addition, the algorithm will also **remove** examples from the training which have an **accuracy** rating that is **above the given threshold *o***, so that examples with a rather uncertain classification are not trained on.","metadata":{}},{"cell_type":"code","source":"# analysis function\ndef print_largest_entries(dict_, n):\n    '''\n    Return n largest key value pairs from dict\n    '''\n    n_largest = sorted(dict_.items(), key=lambda pair: pair[1], reverse=True )[:n]\n    \n    pprint(\"5 Combinations with highest prediction accuracy: \")\n    print(n_largest)\n    \n    return n_largest","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:05:24.600203Z","iopub.execute_input":"2021-11-29T19:05:24.600449Z","iopub.status.idle":"2021-11-29T19:05:24.606349Z","shell.execute_reply.started":"2021-11-29T19:05:24.600418Z","shell.execute_reply":"2021-11-29T19:05:24.605481Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from sklearn.preprocessing import LabelEncoder\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.model_selection import train_test_split\nfrom sklearn import metrics\nfrom pprint import *\nimport warnings\nwarnings.filterwarnings('ignore')\n\n# define function to perform classification on a subsquare of the grid, initialized by a grid ID (will be defined later on)\ndef process_subsquare(df_train, th, n, o):\n    \"\"\"   \n    Classification inside one grid cell.\n    \"\"\"  \n    \n    #Working on df_train\n    place_counts = df_train.place_id.value_counts()\n    mask = (place_counts[df_train.place_id.values] >= th).values\n    df_train = df_train.loc[mask]\n    \n    df_train = df_train[df_train[\"accuracy\"] < o]\n    \n\n    #Working on df_test\n    #df_cell_test = df_test.loc[df_test.grid_cell == grid_id]\n    row_ids = df_test.index\n    \n    #Preparing data\n    le = LabelEncoder()\n    \n    X = df_train.drop(['place_id'], axis=1).values.astype(int)\n    y = le.fit_transform(df_train.place_id.values)\n    \n    X_train, X_test, y_train, y_test = train_test_split(X,y,train_size=0.95, random_state = 999)\n    \n    #Applying the classifier\n    clf = KNeighborsClassifier(n_neighbors=n, weights='distance', metric='euclidean')\n    clf.fit(X_train, y_train)\n    \n    y_pred = clf.predict_proba(X_test)\n    y_predi = np.argmax(y_pred, axis = 1)\n    \n    pred_labels = le.inverse_transform(np.argsort(y_pred, axis=1)[:,::-1][:,:1])\n    acc = round(sklearn.metrics.accuracy_score(y_predi, y_test),2)\n    return pred_labels, row_ids, acc\n   \n\n\n# predict for different number of neighbours and different number of classes:\ndict_acc= {}\nfor n in (100,150,200,250,300,350,400,450,500):\n    for m in (50,100,200,250,300,350,400,450,500): #,3,4,5,6,7,8,9,10,20,30\n        for o in (15,25,50,100): # 150,200,300,400\n            pred_labels, row_ids, acc = process_subsquare(df_sub, th = m, n = n, o = o)\n            dict_acc[(n,m,o)] = acc\n\n\n\n\n# sort dictionary\nn_largest = print_largest_entries(dict_acc, 5)            \n       \nprint(\"Max. accuracy: \", max(dict_acc, key=dict_acc.get), max(dict_acc.values()))\n\n","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:23:56.558931Z","iopub.execute_input":"2021-11-29T19:23:56.560733Z","iopub.status.idle":"2021-11-29T19:24:04.827182Z","shell.execute_reply.started":"2021-11-29T19:23:56.560655Z","shell.execute_reply":"2021-11-29T19:24:04.825260Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Results from the subsquare analysis\n\nThe prediction accuracy using the validation set approach is rather high given its simplicity (maximum of **46%** for a combination of ). It shall be noted that in this example only one feature label is assigned to each example rather than 3, as mentioned in the task description. \n\nI will now parse the entire set by dividing it cell by cell, using a modified version of this parsing script: https://www.kaggle.com/svpons/grid-plus-classifier\n\nThe classification of the full dataset will be performed by using the hyperparameters of the test run that yielded the highest accuracy.\n\n- k (number of nearest neighbours) = 200\n- th (Minimum number of training set class assignments for class to be valid) = 500\n- o (Maximum accuracy (error) value for training example to be kept) = 15\n\n\n\n\n## Application of KNN to the full dataset\n\nThe parsing of the full dataset will be performed using a splitting algorithm for splitting the dataset into cells and applying the classification for each cell.","metadata":{}},{"cell_type":"code","source":"from sklearn.preprocessing import LabelEncoder\nfrom sklearn.neighbors import KNeighborsClassifier\n\ndef prepare_data(df, n_cell_x, n_cell_y):\n    \"\"\"\n    Computation of the grid.\n    \"\"\"\n    #Creating the grid\n    size_x = 10. / n_cell_x\n    size_y = 10. / n_cell_y\n    eps = 0.00001  \n    xs = np.where(df.x.values < eps, 0, df.x.values - eps)\n    ys = np.where(df.y.values < eps, 0, df.y.values - eps)\n    pos_x = (xs / size_x).astype(np.int)\n    pos_y = (ys / size_y).astype(np.int)\n    df['grid_cell'] = pos_y * n_cell_x + pos_x\n    \n    #Feature engineering\n    fw = [500, 1000, 4, 3, 1./22., 2, 10] #feature weights (black magic here)\n    df.x = df.x.values * fw[0]\n    df.y = df.y.values * fw[1]\n    initial_date = np.datetime64('2014-01-01T01:01') \n    d_times = pd.DatetimeIndex(initial_date + np.timedelta64(int(mn), 'm') \n                               for mn in df.time.values)    \n    df['hour'] = d_times.hour * fw[2]\n    df['weekday'] = d_times.weekday * fw[3]\n    df['day'] = (d_times.dayofyear * fw[4]).astype(int)\n    df['month'] = d_times.month * fw[5]\n    df['year'] = (d_times.year - 2013) * fw[6]\n\n    df = df.drop(['time'], axis=1) \n    return df\n\n\ndef process_one_cell(df_train, df_test, grid_id, th):\n    \"\"\"   \n    Classification inside one grid cell.\n    \"\"\"  \n    \n    o = 15\n    \n    #Working on df_train\n    df_cell_train = df_train.loc[df_train.grid_cell == grid_id]\n    place_counts = df_cell_train.place_id.value_counts()\n    mask = (place_counts[df_cell_train.place_id.values] >= th).values\n    df_cell_train = df_cell_train.loc[mask]\n    df_cell_train = df_cell_train[df_cell_train[\"accuracy\"] < o]\n    \n\n    #Working on df_test\n    df_cell_test = df_test.loc[df_test.grid_cell == grid_id]\n    row_ids = df_cell_test.index\n    \n    #Preparing data\n    le = LabelEncoder()\n    y = le.fit_transform(df_cell_train.place_id.values)\n    print(y)\n    X = df_cell_train.drop(['place_id', 'grid_cell'], axis=1).values.astype(int)\n    print(X)\n    X_test = df_cell_test.drop(['grid_cell'], axis = 1).values.astype(int)\n    print(X_test)\n    \n    #Applying the classifier\n    clf = KNeighborsClassifier(n_neighbors=200, weights='distance', \n                               metric='manhattan')\n    clf.fit(X, y)\n    y_pred = clf.predict_proba(X_test)\n    pred_labels = le.inverse_transform(np.argsort(y_pred, axis=1)[:,::-1][:,:3])\n    return pred_labels, row_ids\n\n\n\ndef process_grid(df_train, df_test, th, n_cells):\n    \"\"\"\n    Iterates over all grid cells, aggregates the results and makes the\n    submission.\n    \"\"\" \n    preds = np.zeros((df_test.shape[0], 3), dtype=int)\n    print(preds)\n    \n    for g_id in range(n_cells):\n        if g_id % 100 == 0:\n            print('iter: %s' %(g_id))\n        \n        #Applying classifier to one grid cell\n        pred_labels, row_ids = process_one_cell(df_train, df_test, g_id, th)\n\n        #Updating predictions\n        print(\"preds[row_ids]:\", preds[row_ids])\n        \n        preds[row_ids] = pred_labels\n\n    print('Generating submission file ...')\n    #Auxiliary dataframe with the 3 best predictions for each sample\n    df_aux = pd.DataFrame(preds, dtype=str, columns=['l1', 'l2', 'l3'])  \n    \n    #Concatenating the 3 predictions for each sample\n    ds_sub = df_aux.l1.str.cat([df_aux.l2, df_aux.l3], sep=' ')\n    \n    #Writting to csv\n    ds_sub.name = 'place_id'\n    ds_sub.to_csv('sub_knn.csv', index=True, header=True, index_label='row_id')  \n      \n\n#Defining the size of the grid\nn_cell_x = 20\nn_cell_y = 40 \n\nprint('Preparing train data')\ndf_train_ = prepare_data(df_train, n_cell_x, n_cell_y)\n\nprint('Preparing test data')\ndf_test_ = prepare_data(df_test, n_cell_x, n_cell_y)\n\n#Solving classification problems inside each grid cell\nth = 500 #Keeping place_ids with more than th samples.   \n#process_grid(df_train_, df_test_, th, n_cell_x*n_cell_y)\n\nprint('Generating submission file ...')\n#df_submission.to_csv(\"sub.csv\", index=True) ","metadata":{"execution":{"iopub.status.busy":"2021-11-29T17:54:28.219776Z","iopub.execute_input":"2021-11-29T17:54:28.220027Z","iopub.status.idle":"2021-11-29T17:58:58.37737Z","shell.execute_reply.started":"2021-11-29T17:54:28.219997Z","shell.execute_reply":"2021-11-29T17:58:58.376259Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Gradient Boosting\n\nSince we have now seen the accuracy and classification results from the cell-wise KNN algorithm, the approach is now to apply the cell-wise parsing of the data grid and to analyze each cell and predict the labels using a gradient boosting classifier.\n\nFor this example, I will use the XGBClassifier from the XGB toolbox. Again, I am using this parsing algorithm: https://www.kaggle.com/svpons/grid-plus-classifier\n","metadata":{}},{"cell_type":"code","source":"from sklearn.preprocessing import LabelEncoder\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.model_selection import train_test_split\nfrom sklearn import metrics\nfrom pprint import *\n\nimport xgboost as xgb\n\nxgb_cl = xgb.XGBClassifier()\n\nprint(type(xgb_cl))\n\n\n# define function to perform classification on a subsquare of the grid, initialized by a grid ID (will be defined later on)\ndef process_subsquare_xgb(df_train, th, o):\n    \"\"\"   \n    Classification inside one grid cell.\n    \"\"\"  \n    print(th, o)\n    #Working on df_train\n    place_counts = df_train.place_id.value_counts()\n    mask = (place_counts[df_train.place_id.values] >= th).values\n    df_train = df_train.loc[mask]\n    \n    df_train = df_train[df_train[\"accuracy\"] < o]\n    \n\n    #Working on df_test\n    #df_cell_test = df_test.loc[df_test.grid_cell == grid_id]\n    row_ids = df_test.index\n    \n    #Preparing data\n    le = LabelEncoder()\n    \n    X = df_train.drop(['place_id'], axis=1).values.astype(int)\n    y = le.fit_transform(df_train.place_id.values)\n    \n    X_train, X_test, y_train, y_test = train_test_split(X,y,train_size=0.95, random_state=999)\n    \n    \n#     #Applying the classifier\n#     clf = KNeighborsClassifier(n_neighbors=n, weights='distance', metric='euclidean')\n#     clf.fit(X_train, y_train)\n    \n#     y_pred = clf.predict_proba(X_test)\n#     y_predi = np.argmax(y_pred, axis = 1)\n    \n#     pred_labels = le.inverse_transform(np.argsort(y_pred, axis=1)[:,::-1][:,:1])\n#     acc = round(sklearn.metrics.accuracy_score(y_predi, y_test),2)\n#     return pred_labels, row_ids, acc\n    \n    \n    \n    #Applying the classifier\n    xgb_cl = xgb.XGBClassifier()    \n    xgb_cl.fit(X_train, y_train)\n    \n    y_pred = xgb_cl.predict(X_test)\n    \n    #pred_labels = le.inverse_transform(np.argsort(y_pred, axis=1)[:,::-1][:,:1])\n    acc = round(metrics.accuracy_score(y_pred, y_test),2)\n    return acc\n    # return pred_labels, row_ids, acc\n\n\n\n# predict for different number of neighbours and different number of classes:\ndict_acc_xgb= {}\nfor m in (350,400,450,500): #,3,4,5,6,7,8,9,10,20,30\n    for o in (10,12,15,25,50): # 150,200,300,400\n        acc = process_subsquare_xgb(df_sub, th = m, o = o)\n        dict_acc_xgb[(m,o)] = acc\n\n\n\n\n# sort dictionary\nn_largest = print_largest_entries(dict_acc_xgb, 5)            \n       \nprint(\"Max. accuracy: \", max(dict_acc_xgb, key=dict_acc_xgb.get), max(dict_acc_xgb.values()))","metadata":{"execution":{"iopub.status.busy":"2021-11-29T18:34:29.115183Z","iopub.execute_input":"2021-11-29T18:34:29.115465Z","iopub.status.idle":"2021-11-29T18:34:51.188475Z","shell.execute_reply.started":"2021-11-29T18:34:29.115435Z","shell.execute_reply":"2021-11-29T18:34:51.18769Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Results from the subsquare analysis (XGB)\n\nThe prediction accuracy using the validation set approach is high given the number of classes (maximum of up to **75%**). It shall be noted that in this example only one feature label is assigned to each example rather than 3, as mentioned in the task description. \n\nI will now parse the entire set by dividing it cell by cell, using a modified version of this parsing script: https://www.kaggle.com/svpons/grid-plus-classifier\n\nThe classification of the full dataset will be performed by using the hyperparameters of the test run that yielded the highest accuracy.\n\n- th (Minimum number of training set class assignments for class to be valid) = 450\n- o (Maximum accuracy (error) value for training example to be kept) = 15\n\n\n\n\n## Application of XGB classifier to the full dataset\n\nThe parsing of the full dataset will be performed using a splitting algorithm for splitting the dataset into cells and applying the classification for each cell.","metadata":{}},{"cell_type":"code","source":"# coding: utf-8\n__author__ = 'Sandro Vega Pons : https://www.kaggle.com/svpons'\n\nimport numpy as np\nimport pandas as pd\nfrom sklearn.preprocessing import LabelEncoder\nfrom sklearn.linear_model import SGDClassifier\nimport xgboost as xgb\n\nxgb_cl = xgb.XGBClassifier()\n\ndef prepare_data(df_train, df_test, n_cell_x, n_cell_y):\n    \"\"\"\n    Some feature engineering (mainly with the time feature) + normalization \n    of all features (substracting the mean and dividing by std) +  \n    computation of a grid (size = n_cell_x * n_cell_y), which is included\n    as a new column (grid_cell) in the dataframes.\n    \n    Parameters:\n    ----------    \n    df_train: pandas DataFrame\n              Training data\n    df_test : pandas DataFrame\n              Test data\n    n_cell_x: int\n              Number of grid cells on the x axis\n    n_cell_y: int\n              Number of grid cells on the y axis\n    \n    Returns:\n    -------    \n    df_train, df_test: pandas DataFrame\n                       Modified training and test datasets.\n    \"\"\"  \n    print('Feature engineering...')\n    print('    Computing some features from x and y ...')\n    ##x, y, and accuracy remain the same\n        ##New feature x/y\n    eps = 0.00001  #required to avoid some divisions by zero.\n    df_train['x_d_y'] = df_train.x.values / (df_train.y.values + eps) \n    df_test['x_d_y'] = df_test.x.values / (df_test.y.values + eps) \n        ##New feature x*y\n    df_train['x_t_y'] = df_train.x.values * df_train.y.values  \n    df_test['x_t_y'] = df_test.x.values * df_test.y.values\n    \n    print('    Creating datetime features ...')\n    ##time related features (assuming the time = minutes)\n    initial_date = np.datetime64('2014-01-01T01:01') \n        #working on df_train  \n    d_times = pd.DatetimeIndex(initial_date + np.timedelta64(int(mn), 'm') \n                               for mn in df_train.time.values)    \n    df_train['hour'] = d_times.hour\n    df_train['weekday'] = d_times.weekday\n    df_train['day'] = d_times.day\n    df_train['month'] = d_times.month\n    df_train['year'] = d_times.year\n    df_train = df_train.drop(['time'], axis=1)\n        #working on df_test    \n    d_times = pd.DatetimeIndex(initial_date + np.timedelta64(int(mn), 'm') \n                               for mn in df_test.time.values)    \n    df_test['hour'] = d_times.hour\n    df_test['weekday'] = d_times.weekday\n    df_test['day'] = d_times.day\n    df_test['month'] = d_times.month\n    df_test['year'] = d_times.year\n    df_test = df_test.drop(['time'], axis=1)\n    \n    print('Computing the grid ...')\n    #Creating a new colum with grid_cell id  (there will be \n    #n = (n_cell_x * n_cell_y) cells enumerated from 0 to n-1)\n    size_x = 10. / n_cell_x\n    size_y = 10. / n_cell_y\n        #df_train\n    xs = np.where(df_train.x.values < eps, 0, df_train.x.values - eps)\n    ys = np.where(df_train.y.values < eps, 0, df_train.y.values - eps)\n    pos_x = (xs / size_x).astype(np.int)\n    pos_y = (ys / size_y).astype(np.int)\n    df_train['grid_cell'] = pos_y * n_cell_x + pos_x\n            #df_test\n    xs = np.where(df_test.x.values < eps, 0, df_test.x.values - eps)\n    ys = np.where(df_test.y.values < eps, 0, df_test.y.values - eps)\n    pos_x = (xs / size_x).astype(np.int)\n    pos_y = (ys / size_y).astype(np.int)\n    df_test['grid_cell'] = pos_y * n_cell_x + pos_x \n    \n    ##Normalization\n    print('Normalizing the data: (X - mean(X)) / std(X) ...')\n    cols = ['x', 'y', 'accuracy', 'x_d_y', 'x_t_y', 'hour', \n            'weekday', 'day', 'month', 'year']\n    for cl in cols:\n        ave = df_train[cl].mean()\n        std = df_train[cl].std()\n        df_train[cl] = (df_train[cl].values - ave ) / std\n        df_test[cl] = (df_test[cl].values - ave ) / std\n        \n    #Returning the modified dataframes\n    return df_train, df_test\n\n\ndef process_one_cell(df_train, df_test, grid_id, th):\n    \"\"\"\n    Does all the processing inside a single grid cell: Computes the training\n    and test sets inside the cell. Fits a classifier to the training data\n    and predicts on the test data. Selects the top 3 predictions.\n    \n    Parameters:\n    ----------    \n    df_train: pandas DataFrame\n              Training set\n    df_test: pandas DataFrame\n             Test set\n    grid_id: int\n             The id of the grid to be analyzed\n    th: int\n       Threshold for place_id. Only samples with place_id with at least th\n       occurrences are kept in the training set.\n    \n    Return:\n    ------    \n    pred_labels: numpy ndarray\n                 Array with the prediction of the top 3 labels for each sample\n    row_ids: IDs of the samples in the submission dataframe \n    \"\"\"   \n    #Working on df_train\n    df_cell_train = df_train.loc[df_train.grid_cell == grid_id]\n    place_counts = df_cell_train.place_id.value_counts()\n    mask = place_counts[df_cell_train.place_id.values] >= th\n    df_cell_train = df_cell_train.loc[mask.values]\n    \n    o = 15\n    df_train = df_train[df_train[\"accuracy\"] < o]\n    \n    #Working on df_test\n    df_cell_test = df_test.loc[df_test.grid_cell == grid_id]\n    row_ids = df_cell_test.index\n    \n    le = LabelEncoder()\n    y = le.fit_transform(df_cell_train.place_id.values)\n    X = df_cell_train.drop(['place_id', 'grid_cell'], axis = 1).values\n\n    #Training Classifier\n    xgb_cl = xgb.XGBClassifier()  \n    xgb_cl.fit(X, y)\n    X_test = df_cell_test.drop(['grid_cell'], axis = 1).values\n    y_pred = xgb_cl.predict_proba(X_test)\n\n    pred_labels = le.inverse_transform(np.argsort(y_pred, axis=1)[:,::-1][:,:3])    \n    return pred_labels, row_ids\n   \n   \ndef process_grid(df_train, df_test, df_sub, th, n_cells):\n    \"\"\"\n    Iterates over all grid cells and aggregates the results of individual cells\n    \"\"\"    \n    for g_id in range(n_cells):\n        if g_id % 10 == 0:\n            print('iteration: %s' %(g_id))\n        \n        #Applying classifier to one grid cell\n        pred_labels, row_ids = process_one_cell(df_train, df_test, g_id, th)\n        #Converting the prediction to the submission format\n        str_labels = np.apply_along_axis(lambda x: ' '.join(x.astype(str)), \n                                         1, pred_labels)\n        #Updating submission file\n        df_sub.loc[row_ids] = str_labels.reshape(-1,1)\n        \n    return df_sub       \n                 \n\n\n#Defining the size of the grid\nn_cell_x = 10\nn_cell_y = 10 \ndf_train, df_test = prepare_data(df_train, df_test, n_cell_x, n_cell_y)\n\n#Solving classification problems inside each grid cell\nth = 450 #Threshold on place_id inside each cell. Only place_ids with at \n        #least th occurrences inside each grid_cell are considered. This\n        #is to avoid classes with very few samples and speed-up the \n        #computation.\n\n#df_submission  = process_grid(df_train, df_test, df_sub, th = 450, n_cell_x * n_cell_y)                                 \n#creating the submission\nprint('Generating submission file ...')\n#df_submission.to_csv(\"sub.csv\", index=True) ","metadata":{"execution":{"iopub.status.busy":"2021-11-29T19:14:26.817086Z","iopub.execute_input":"2021-11-29T19:14:26.817437Z","iopub.status.idle":"2021-11-29T19:19:19.362610Z","shell.execute_reply.started":"2021-11-29T19:14:26.817401Z","shell.execute_reply":"2021-11-29T19:19:19.360925Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Summary of results\n\nIn summary, the classification approach using gradient boosting (XGB) worked well for the data, especially if the quantity of possible classes was reduced to a number of classes with many check ins. This way, the class assignment distortion could be reduced. In addition, reducing the training data by the training examples that had a low classification confidence (high accuracy value) improved the classification further, up to an accuracy of 75 % in the training subsquare using gradient boosting. ","metadata":{}}]}