{"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":"markdown","source":"<h1><center> Foursquare Location Matching </center></h1>\n<h2><center> XGBoost </center></h2>\n<h2><center> Sugata Ghosh </center></h2>","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"markdown","source":"### Competition: [Foursquare - Location Matching](https://www.kaggle.com/competitions/foursquare-location-matching)\n\n### Notebook on Exploratory Data Analysis: [Foursquare Location Matching - EDA](https://www.kaggle.com/code/sugataghosh/foursquare-location-matching-eda)\n\n### Notebook on Baseline Modeling: [Foursquare Location Matching - Baseline Modeling](https://www.kaggle.com/code/sugataghosh/foursquare-location-matching-baseline-modeling)","metadata":{}},{"cell_type":"markdown","source":"The present notebook implements the [XGBoost](https://en.wikipedia.org/wiki/XGBoost) classifier to classify whether two given [points of interest](https://en.wikipedia.org/wiki/Point_of_interest) (POI) match or not. The algorithm has been optimized in terms of hyperparameters to achieve maximal performance. Note that the first four sections (*Introduction*, *Train-Test Split*, *Data Preprocessing* and *Feature Engineering*) are more or less same as in [Foursquare Location Matching - Baseline Modeling](https://www.kaggle.com/code/sugataghosh/foursquare-location-matching-baseline-modeling). The focus of the notebook is the fifth section (*Baseline XGBoost*), where we first implement the baseline XGBoost classifier, and the sixth section (*Hyperparameter Tuning*), where we employ [hyperparameter optimization](https://en.wikipedia.org/wiki/Hyperparameter_optimization) on the algorithm.","metadata":{}},{"cell_type":"markdown","source":"### Contents\n\n- [Introduction](#1.-Introduction)\n- [Train-Test Split](#2.-Train-Test-Split)\n- [Data Preprocessing](#3.-Data-Preprocessing)\n- [Feature Engineering](#4.-Feature-Engineering)\n- [Baseline XGBoost](#5.-Baseline-XGBoost)\n- [Hyperparameter Tuning](#6.-Hyperparameter-Tuning)\n- [Acknowledgements](#Acknowledgements)\n- [References](#References)","metadata":{}},{"cell_type":"markdown","source":"### Importing libraries","metadata":{}},{"cell_type":"code","source":"# File system manangement\nimport time, psutil, os, gc\n\n# Mathematical functions\nimport math\nfrom math import cos, asin, sqrt, pi\n\n# Data manipulation\nimport numpy as np\nimport pandas as pd\n\n# Plotting and visualization\nimport matplotlib.pyplot as plt\nimport seaborn as sns\nsns.set_theme()\nimport plotly\nimport plotly.express as px\nimport plotly.graph_objects as go\nfrom plotly.subplots import make_subplots\nfrom plotly.offline import init_notebook_mode, iplot\ninit_notebook_mode(connected=True)\n\n# Train-test split and k-fold cross validation\nfrom sklearn.model_selection import train_test_split, KFold, cross_val_score, GridSearchCV, RepeatedStratifiedKFold\n\n# Classifier\nfrom xgboost import XGBClassifier\n\n# Others\nimport operator as op\nfrom functools import reduce, lru_cache","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:13.639455Z","iopub.execute_input":"2022-07-16T17:09:13.639854Z","iopub.status.idle":"2022-07-16T17:09:16.280739Z","shell.execute_reply.started":"2022-07-16T17:09:13.639772Z","shell.execute_reply":"2022-07-16T17:09:16.279723Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Runtime and memory usage","metadata":{}},{"cell_type":"code","source":"# Recording the starting time, complemented with a stopping time check in the end to compute process runtime\nstart = time.time()\n\n# Class representing the OS process and having memory_info() method to compute process memory usage\nprocess = psutil.Process(os.getpid())","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:16.282651Z","iopub.execute_input":"2022-07-16T17:09:16.283219Z","iopub.status.idle":"2022-07-16T17:09:16.289935Z","shell.execute_reply.started":"2022-07-16T17:09:16.283185Z","shell.execute_reply":"2022-07-16T17:09:16.288854Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 1. Introduction\n\n- [Point of Interest](#Point-of-Interest)\n- [The Problem of POI Matching](#The-Problem-of-POI-Matching)\n- [About Foursquare](#About-Foursquare)\n- [Data](#Data)\n- [Project Objective](#Project-Objective)\n- [Evaluation Metric](#Evaluation-Metric)","metadata":{}},{"cell_type":"markdown","source":"**Note:** The introduction section from the [Foursquare Location Matching - EDA](https://www.kaggle.com/code/sugataghosh/foursquare-location-matching-eda) notebook is reproduced here to make the present notebook self-contained, so that one can understand the problem, as well as the objective of the competition, without requiring to go back to the EDA notebook.","metadata":{}},{"cell_type":"markdown","source":"## Point of Interest\n\nA point of interest (POI) is a specific point location that someone may find useful or interesting. An example is a point on the Earth representing the location of the Eiffel Tower, or a point on Mars representing the location of its highest mountain, [Olympus Mons](https://en.wikipedia.org/wiki/Olympus_Mons). Most consumers use the term when referring to hotels, campsites, fuel stations or any other categories used in modern automotive navigation systems. Users of a mobile device can be provided with geolocation and time aware POI service that recommends geolocations nearby and with a temporal relevance (e.g. POI to special services in a ski resort are available only in winter). The notion of POI is widely used in cartography, especially in electronic variants including GIS, and GPS navigation software.","metadata":{}},{"cell_type":"markdown","source":"## The Problem of POI Matching\n\nIt is useful to combine POI data obtained from multiple sources for effective reusability. One issue in merging such data is that different dataset may have variations in POI name, address, and other identifying information for the same POI. It is thus important to identify observations which refer to the same POI. The process of POI matching involves finding POI pairs that refer to the same real-world entity, which is the core issue in geospatial data integration and is perhaps the most technically difficult part of multi-source POI fusion. The raw location data can contain noise, unstructured information, and incomplete or inaccurate attributes, which makes the task even more difficult. Nonetheless, to maintain the highest level of accuracy, the data must be matched and duplicate POIs must be identified and merged with timely updates from multiple sources. A combination of machine-learning algorithms and rigorous human validation methods are optimal for effective de-duplication of such data.","metadata":{}},{"cell_type":"markdown","source":"## About Foursquare\n\n[Foursquare Labs Inc.](https://foursquare.com/), commonly known as Foursquare, is an American location technology company and data cloud platform. The company's location platform is the foundation of several business and consumer products, including the [Foursquare City Guide](https://en.wikipedia.org/wiki/Foursquare_City_Guide) and [Foursquare Swarm](https://en.wikipedia.org/wiki/Foursquare_Swarm) apps. Foursquare's products include Pilgrim SDK, Places, Visits, Attribution, Audience, Proximity, and Unfolded Studio. It is one of the leading independent providers of global POI data and is dedicated to building meaningful bridges between digital spaces and physical places. Trusted by leading enterprises like Apple, Microsoft, Samsung, and Uber, Foursquare's tech stack harnesses the power of places and movement to improve customer experiences and drive better business outcomes.","metadata":{}},{"cell_type":"markdown","source":"## Data\n\n**Source:** https://www.kaggle.com/competitions/foursquare-location-matching/data\n\nThe data considered in the competition comprises over one-and-a-half million place entries for hundreds of thousands of commercial Points-of-Interest (POIs) around the globe. Though the data entries may represent or resemble entries for real places, they may be contaminated with artificial information or additional noise.\n\nThe training data comprises eleven attribute fields for over one million place entries, together with:\n- `id` : A unique identifier for each entry.\n- `point_of_interest` : An identifier for the POI the entry represents. There may be one or many entries describing the same POI. Two entries *match* when they describe a common POI.","metadata":{}},{"cell_type":"code","source":"# Loading the training data\ndata_train = pd.read_csv('../input/foursquare-location-matching/train.csv')\nprint(pd.Series({\"Memory usage\": \"{:.2f} MB\".format(data_train.memory_usage().sum()/(1024*1024)),\n                 \"Dataset shape\": \"{}\".format(data_train.shape)}).to_string())\nprint(\" \")\ndata_train.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:16.291443Z","iopub.execute_input":"2022-07-16T17:09:16.292037Z","iopub.status.idle":"2022-07-16T17:09:24.719890Z","shell.execute_reply.started":"2022-07-16T17:09:16.292002Z","shell.execute_reply":"2022-07-16T17:09:24.718660Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# A typical observation from the training set\ndata_train.iloc[0]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:24.722599Z","iopub.execute_input":"2022-07-16T17:09:24.723318Z","iopub.status.idle":"2022-07-16T17:09:24.733737Z","shell.execute_reply.started":"2022-07-16T17:09:24.723287Z","shell.execute_reply":"2022-07-16T17:09:24.732137Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The pairs data is a pregenerated set of pairs of place entries from the training data designed to improve detection of matches. It includes:\n- `match` : Boolean variables denoting whether or not the pair of entries describes a common POI.","metadata":{}},{"cell_type":"code","source":"# Loading pregenerated set of pairs of place entries from the training data\ndata_pairs = pd.read_csv('../input/foursquare-location-matching/pairs.csv')\nprint(pd.Series({\"Memory usage\": \"{:.2f} MB\".format(data_pairs.memory_usage().sum()/(1024*1024)),\n                 \"Dataset shape\": \"{}\".format(data_pairs.shape)}).to_string())\nprint(\" \")\ndata_pairs.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:24.735724Z","iopub.execute_input":"2022-07-16T17:09:24.736034Z","iopub.status.idle":"2022-07-16T17:09:31.952781Z","shell.execute_reply.started":"2022-07-16T17:09:24.736007Z","shell.execute_reply":"2022-07-16T17:09:31.951591Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# A typical observation from the pregenerated set of pairs\ndata_pairs.iloc[0]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:31.954580Z","iopub.execute_input":"2022-07-16T17:09:31.955542Z","iopub.status.idle":"2022-07-16T17:09:31.964368Z","shell.execute_reply.started":"2022-07-16T17:09:31.955492Z","shell.execute_reply":"2022-07-16T17:09:31.963133Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The test data comprises a set of place entries with their recorded attribute fields, similar to the training set. The POIs in the test data are distinct from the POIs in the training data.","metadata":{}},{"cell_type":"code","source":"# Loading the test data\ndata_test = pd.read_csv('../input/foursquare-location-matching/test.csv')\nprint(pd.Series({\"Memory usage\": \"{:.5f} MB\".format(data_test.memory_usage().sum()/(1024*1024)),\n                 \"Dataset shape\": \"{}\".format(data_test.shape)}).to_string())\nprint(\" \")\ndata_test.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:31.966618Z","iopub.execute_input":"2022-07-16T17:09:31.967309Z","iopub.status.idle":"2022-07-16T17:09:32.002593Z","shell.execute_reply.started":"2022-07-16T17:09:31.967271Z","shell.execute_reply":"2022-07-16T17:09:32.001180Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# A typical observation from the test set\ndata_test.iloc[0]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:32.004140Z","iopub.execute_input":"2022-07-16T17:09:32.005578Z","iopub.status.idle":"2022-07-16T17:09:32.014415Z","shell.execute_reply.started":"2022-07-16T17:09:32.005547Z","shell.execute_reply":"2022-07-16T17:09:32.013261Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Project Objective\n\nThe goal of the project is to match POIs together. Using the provided dataset of over one-and-a-half million places entries, heavily altered to include noise, duplications, extraneous, or incorrect information, the objective is to produce an algorithm that predicts which place entries represent the same POI. Each place entry in the data includes useful attributes like name, street address, and coordinates. Efficient and successful matching of POIs will make it easier to identify where new stores or businesses would benefit people the most.","metadata":{}},{"cell_type":"markdown","source":"## Evaluation Metric\n\n**[Jaccard index](https://en.wikipedia.org/wiki/Jaccard_index).** Also known as *Jaccard similarity coefficient*, it is a statistic used for gauging the similarity and diversity of sample sets. It was developed by [Grove Karl Gilbert](https://en.wikipedia.org/wiki/Grove_Karl_Gilbert) in 1884 as his *ratio of verification (v)* and now is frequently referred to as the *Critical Success Index* in meteorology. It was later developed independently by [Paul Jaccard](https://en.wikipedia.org/wiki/Paul_Jaccard), originally giving the French name *coefficient de communauté* and independently formulated again by T. T. Tanimoto. Thus, the *Tanimoto index* or *Tanimoto coefficient* are also used in some fields. However, they are identical in generally taking the ratio of Intersection over Union. The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets:\n\n$$ J(A, B) := \\frac{\\left\\vert A \\cap B \\right\\vert}{\\left\\vert A \\cup B \\right\\vert} = \\frac{\\left\\vert A \\cap B \\right\\vert}{\\left\\vert A \\right\\vert + \\left\\vert B \\right\\vert - \\left\\vert A \\cap B \\right\\vert}. $$\n\nNote that by design, $0\\leq J\\left(A, B\\right)\\leq 1$. If $A$ and $B$ are both empty, define $J(A, B) = 1$. The Jaccard coefficient is widely used in computer science, ecology, genomics, and other sciences, where binary or binarized data are used. Both the exact solution and approximation methods are available for hypothesis testing with the Jaccard coefficient. See [this paper](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-019-3118-5) ([arxiv version](https://arxiv.org/abs/1903.11372)) for details.\n\nLet us assume that for a specific `id` $a$, our algorithm produces three matches $a$, $b$ and $c$ whereas the true matches are $a$, $b$, $d$ and $e$. Then the Jaccard index for the prediction on this particular `id` will be\n\n$$ \\frac{\\left\\vert \\left\\{a, b, c\\right\\} \\cap \\left\\{a, b, d, e\\right\\} \\right\\vert}{\\left\\vert \\left\\{a, b, c\\right\\} \\cup \\left\\{a, b, d, e\\right\\} \\right\\vert} = \\frac{\\left\\vert \\left\\{a, b\\right\\} \\right\\vert}{\\left\\vert \\left\\{a, b, c, d, e\\right\\} \\right\\vert} = \\frac{2}{5}. $$\n\nThus, while correct matching predictions are rewarded, incorrect matching predictions are penalised by equal measure. The evaluation metric is simply the mean of Jaccard indices for each of the test observations, i.e. if the test data comprises $n_{\\text{test}}$ observations and $J_i$ denotes the Jaccard index corresponding to the $i$th test observation, $i = 1,2,\\cdots,n_{\\text{test}}$, then the final metric by which a model will be evaluated is:\n\n$$ \\frac{1}{n_{\\text{test}}} \\sum_{i=1}^{n_{\\text{test}}} J_i. $$","metadata":{}},{"cell_type":"markdown","source":"**Note:** In this notebook, we shall rely solely on the provided pairs set `data_pairs` to build the baseline models.","metadata":{}},{"cell_type":"markdown","source":"# 2. Train-Test Split","metadata":{}},{"cell_type":"markdown","source":"We split `data_pairs` into two parts:\n- `data_pairs_train`: The portion of data that we use to *train* the models\n- `data_pairs_test`: The portion of data that we use to *test* or evaluate the models\n\nWe shall keep `data_test`, which has only five observations, separate from the modeling procedure.","metadata":{}},{"cell_type":"code","source":"# Splitting data_train\ndata_pairs_train, data_pairs_test = train_test_split(data_pairs, test_size = 0.2, random_state = 40)\n\nlabels = ['Train','Test']\nvalues = [len(data_pairs_train), len(data_pairs_test)]\nfig_data = [go.Pie(values = values, labels = labels, hole = 0.0, textinfo = 'label+percent')]\nfig_title = dict(text = \"Train-test split\", x = 0.5, y = 0.95)\nfig = go.Figure(data = fig_data)\nfig.update_layout(height = 500, width = 800, showlegend = False, title = fig_title)\nfig.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:32.015339Z","iopub.execute_input":"2022-07-16T17:09:32.015598Z","iopub.status.idle":"2022-07-16T17:09:32.721600Z","shell.execute_reply.started":"2022-07-16T17:09:32.015572Z","shell.execute_reply":"2022-07-16T17:09:32.720573Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Donutplots of the 'match' column\nfig = make_subplots(rows = 1, cols = 2, specs = [[{'type': 'domain'}, {'type': 'domain'}]])\nx_val_train = data_pairs_train['match'].value_counts(sort = False).index.tolist()\ny_val_train = data_pairs_train['match'].value_counts(sort = False).tolist()\nx_val_test = data_pairs_test['match'].value_counts(sort = False).index.tolist()\ny_val_test = data_pairs_test['match'].value_counts(sort = False).tolist()\nfig.add_trace(go.Pie(values = y_val_train, labels = x_val_train, hole = 0.5, textinfo = 'label+percent', title = \"Train\"), row = 1, col = 1)\nfig.add_trace(go.Pie(values = y_val_test, labels = x_val_test, hole = 0.5, textinfo = 'label+percent', title = \"Test\"), row = 1, col = 2)\nfig.update_layout(height = 500, width = 800, showlegend = False, xaxis = dict(tickmode = 'linear', tick0 = 0, dtick = 1), title = dict(text = \"Frequency comparison of 'match'\", x = 0.5, y = 0.95)) \nfig.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:32.726718Z","iopub.execute_input":"2022-07-16T17:09:32.727632Z","iopub.status.idle":"2022-07-16T17:09:32.890756Z","shell.execute_reply.started":"2022-07-16T17:09:32.727602Z","shell.execute_reply":"2022-07-16T17:09:32.889718Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We observe that in both the `data_pairs_train` and the `data_pairs_test`, the count of pairs that match is higher than the count of pairs that do not match. However, the imbalance is not too big.","metadata":{}},{"cell_type":"markdown","source":"# 3. Data Preprocessing\n\n- [Decoding States Abbreviations](#Decoding-States-Abbreviations)\n- [Conversion to Lowercase](#Conversion-to-Lowercase)\n- [Missing Data Imputation](#Missing-Data-Imputation)","metadata":{}},{"cell_type":"markdown","source":"## Decoding States Abbreviations","metadata":{}},{"cell_type":"code","source":"# Dictionary of US states abbreviations and names\nurl_abbrev_to_name = \"https://raw.githubusercontent.com/sugatagh/Foursquare-Location-Matching/main/JSON/US_states_abbrev_to_name.json\"\ndict_abbrev_to_name = pd.read_json(url_abbrev_to_name, typ = 'series')\ndict_abbrev_to_name","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:32.892025Z","iopub.execute_input":"2022-07-16T17:09:32.892356Z","iopub.status.idle":"2022-07-16T17:09:33.063042Z","shell.execute_reply.started":"2022-07-16T17:09:32.892328Z","shell.execute_reply":"2022-07-16T17:09:33.061825Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Converting US states abbreviations to names\ndata_pairs_train.replace({'state_1': dict_abbrev_to_name}, inplace = True)\ndata_pairs_train.replace({'state_2': dict_abbrev_to_name}, inplace = True)\ndata_pairs_test.replace({'state_1': dict_abbrev_to_name}, inplace = True)\ndata_pairs_test.replace({'state_2': dict_abbrev_to_name}, inplace = True)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:33.064224Z","iopub.execute_input":"2022-07-16T17:09:33.065097Z","iopub.status.idle":"2022-07-16T17:09:36.985815Z","shell.execute_reply.started":"2022-07-16T17:09:33.065019Z","shell.execute_reply":"2022-07-16T17:09:36.984920Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Conversion to Lowercase","metadata":{}},{"cell_type":"markdown","source":"We convert all alphabetical characters in the relevant object-type columns to lowercase so that the models do not differentiate identical words due to [case sensitivity](https://en.wikipedia.org/wiki/Case_sensitivity).","metadata":{}},{"cell_type":"code","source":"# Converting to lowercase\ndef convert_to_lowercase_skipna(x):\n    \"\"\"\n    Converts a given string to lowercase\n    Arg:\n      x (string/NaN): input string (possibly NaN due to missing value)\n    Returns:\n      y (string/NaN): x.lower() if x is not NaN, x otherwise\n    \"\"\"\n    if str(x) == 'nan':\n        y = x\n    else:\n        y = x.lower()\n    return y\n\ntext = \"Mobile Phone Shops\"\nprint(\"Input: {}\".format(text))\nprint(\"Output: {}\".format(convert_to_lowercase_skipna(text)))","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:36.987151Z","iopub.execute_input":"2022-07-16T17:09:36.987411Z","iopub.status.idle":"2022-07-16T17:09:36.994609Z","shell.execute_reply.started":"2022-07-16T17:09:36.987386Z","shell.execute_reply":"2022-07-16T17:09:36.993926Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Before applying this conversion, we have to ensure that the argument is of `string` type. However, we do not want to convert the `nan` values to the string `'nan'`, as the converted string will no longer be identified as a missing value, and hence will go unaltered in the *missing value imputation* step.","metadata":{}},{"cell_type":"code","source":"# Converting to string, unless the argument is nan\ndef convert_to_string_skipna(x):\n    \"\"\"\n    Converts an input to string if it is not NaN, otherwise it is left unaltered\n    Arg:\n      x (any python data type): input to be converted (possibly NaN due to missing value)\n    Returns:\n      y (str/NaN): str(x) if x is not NaN, x otherwise\n    \"\"\"\n    if str(x) == 'nan':\n        y = x\n    else:\n        y = str(x)\n    return y\n\nnumber = 40\nprint(\"Input: {}\".format(number))\nprint(\"Output:\")\nconvert_to_string_skipna(number)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:36.995893Z","iopub.execute_input":"2022-07-16T17:09:36.996381Z","iopub.status.idle":"2022-07-16T17:09:37.009971Z","shell.execute_reply.started":"2022-07-16T17:09:36.996354Z","shell.execute_reply":"2022-07-16T17:09:37.009243Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We convert the columns `name`, `address`, `city`, `state` and `categories`. We leave the column `url` as it is, for its case sensitivity.","metadata":{}},{"cell_type":"code","source":"# Applying the conversion to object columns\ncols_lower = ['name', 'address', 'city', 'state', 'categories']\ncols_lower_pairs = ['name_1', 'address_1', 'city_1', 'state_1', 'categories_1',\n                    'name_2', 'address_2', 'city_2', 'state_2', 'categories_2']\nfor col in cols_lower:\n    data_test[col] = data_test[col].apply(convert_to_string_skipna).apply(convert_to_lowercase_skipna)\nfor col in cols_lower_pairs:\n    data_pairs_train[col] = data_pairs_train[col].apply(convert_to_string_skipna).apply(convert_to_lowercase_skipna)\n    data_pairs_test[col] = data_pairs_test[col].apply(convert_to_string_skipna).apply(convert_to_lowercase_skipna)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:37.011194Z","iopub.execute_input":"2022-07-16T17:09:37.011886Z","iopub.status.idle":"2022-07-16T17:09:45.358111Z","shell.execute_reply.started":"2022-07-16T17:09:37.011858Z","shell.execute_reply":"2022-07-16T17:09:45.357255Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Missing Data Imputation","metadata":{}},{"cell_type":"code","source":"# Columns with missing values in the training set with respective proportion of missing values\n(data_pairs_train.isna().sum()[data_pairs_train.isna().sum() != 0] / len(data_pairs_train)).sort_values(ascending = False)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:45.359270Z","iopub.execute_input":"2022-07-16T17:09:45.359680Z","iopub.status.idle":"2022-07-16T17:09:47.583744Z","shell.execute_reply.started":"2022-07-16T17:09:45.359652Z","shell.execute_reply":"2022-07-16T17:09:47.583079Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Missing values in the training set\nplt.figure(figsize = (9, 6))\ndf_temp = data_pairs_train.isna().sum() * 100 / len(data_pairs_train)\ns = sns.barplot(x = df_temp.values, y = df_temp.index)\ns.set_xlim(0, 100)\ns.set_xlabel(\"% of missing values\", fontsize = 14)\ns.set_ylabel(\"column\", fontsize = 14)\nplt.axvline(x = 30)\nplt.axvline(x = 50)\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:47.585398Z","iopub.execute_input":"2022-07-16T17:09:47.585662Z","iopub.status.idle":"2022-07-16T17:09:49.278873Z","shell.execute_reply.started":"2022-07-16T17:09:47.585636Z","shell.execute_reply":"2022-07-16T17:09:49.277602Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Seven columns `zip_1`, `url_1`, `phone_1`, `address_2`, `zip_2`, `url_2` and `phone_2` have over $30\\%$ values missing. We shall drop these columns from the subsequent analysis.","metadata":{}},{"cell_type":"markdown","source":"#### Dropping columns with more than 30% missing values","metadata":{}},{"cell_type":"markdown","source":"Even though `address_1` has less than $30\\%$ missing values, `address_2` has a very high proportion of it. For a comparison purpose, `address_1` cannot contribute anything alone because *one hand cannot clap*. Thus we drop it alongside all the columns with more than $30\\%$ missing values.","metadata":{}},{"cell_type":"code","source":"# Dropping columns with more than 30% missing values in the training set\ncols_drop = ['address', 'zip', 'url', 'phone']\ncols_drop_pairs = ['address_1', 'zip_1', 'url_1', 'phone_1', 'address_2', 'zip_2', 'url_2', 'phone_2']\ndata_test.drop(cols_drop, axis = 1, inplace = True)\ndata_pairs_train.drop(cols_drop_pairs, axis = 1, inplace = True)\ndata_pairs_test.drop(cols_drop_pairs, axis = 1, inplace = True)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:49.280190Z","iopub.execute_input":"2022-07-16T17:09:49.281674Z","iopub.status.idle":"2022-07-16T17:09:49.496918Z","shell.execute_reply.started":"2022-07-16T17:09:49.281644Z","shell.execute_reply":"2022-07-16T17:09:49.496038Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### Imputing missing values with 'unknown'","metadata":{}},{"cell_type":"code","source":"# Imputing missing names with 'unknown'\ncols_unknown = ['name', 'city', 'state', 'country']\nfor col in cols_unknown:\n    data_test[col].fillna('unknown', inplace = True)\ncols_unknown_pairs = ['name_1', 'city_1', 'state_1', 'country_1', 'name_2', 'city_2', 'state_2', 'country_2']\nfor col in cols_unknown_pairs:\n    data_pairs_train[col].fillna('unknown', inplace = True)\n    data_pairs_test[col].fillna('unknown', inplace = True)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:49.498205Z","iopub.execute_input":"2022-07-16T17:09:49.498480Z","iopub.status.idle":"2022-07-16T17:09:50.020789Z","shell.execute_reply.started":"2022-07-16T17:09:49.498453Z","shell.execute_reply":"2022-07-16T17:09:50.019383Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### Mode imputation for categories","metadata":{}},{"cell_type":"code","source":"# Mode imputation for categories\ndata_test['categories'].fillna(data_test['categories'].mode()[0], inplace = True)\ndata_pairs_train['categories_1'].fillna(data_pairs_train['categories_1'].mode()[0], inplace = True)\ndata_pairs_train['categories_2'].fillna(data_pairs_train['categories_2'].mode()[0], inplace = True)\ndata_pairs_test['categories_1'].fillna(data_pairs_test['categories_1'].mode()[0], inplace = True)\ndata_pairs_test['categories_2'].fillna(data_pairs_test['categories_2'].mode()[0], inplace = True)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:50.022033Z","iopub.execute_input":"2022-07-16T17:09:50.022328Z","iopub.status.idle":"2022-07-16T17:09:50.415450Z","shell.execute_reply.started":"2022-07-16T17:09:50.022302Z","shell.execute_reply":"2022-07-16T17:09:50.414324Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Count of missing values in the 'data_pairs_train'\ndata_pairs_train.isna().sum()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:50.416842Z","iopub.execute_input":"2022-07-16T17:09:50.417194Z","iopub.status.idle":"2022-07-16T17:09:51.105542Z","shell.execute_reply.started":"2022-07-16T17:09:50.417166Z","shell.execute_reply":"2022-07-16T17:09:51.104842Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Count of missing values in the 'data_pairs_test'\ndata_pairs_test.isna().sum()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.106704Z","iopub.execute_input":"2022-07-16T17:09:51.106955Z","iopub.status.idle":"2022-07-16T17:09:51.286560Z","shell.execute_reply.started":"2022-07-16T17:09:51.106930Z","shell.execute_reply":"2022-07-16T17:09:51.285320Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Count of missing values in the true test set\ndata_test.isna().sum()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.287536Z","iopub.execute_input":"2022-07-16T17:09:51.288246Z","iopub.status.idle":"2022-07-16T17:09:51.296656Z","shell.execute_reply.started":"2022-07-16T17:09:51.288218Z","shell.execute_reply":"2022-07-16T17:09:51.295715Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 4. Feature Engineering\n\n- [Distance between Locations](#Distance-between-Locations)\n- [Features Based on Largest Common Substring](#Features-Based-on-Largest-Common-Substring)\n- [Matching of Countries](#Matching-of-Countries)\n- [The Target Variable](#The-Target-Variable)","metadata":{}},{"cell_type":"markdown","source":"Each row in `data_pairs_train` or `data_pairs_test` consists of two training observations and a `match` variable which indicates whether the two observations match or not. As we have seen in the previous section, an observation in the pairs set can be represented as:\n\n$$ \\left(a_1,a_2,\\ldots,a_n; b_1,b_2,\\ldots,b_n; y\\right), $$\n\nwhere $a_1,a_2,\\ldots,a_n$ is the observed features of the first observation, $b_1,b_2,\\ldots,b_n$ is the same for the second observation and $y$ is the `match` variable. Now, suppose that $\\left(c_1,c_2,\\ldots,c_n\\right)$ and $\\left(d_1,d_2,\\ldots,d_n\\right)$ are two observations from the `test set`. To predict whether these two observations refer to the same POI or not, we have to predict the corresponding `match` variable $y$. The general idea in this section is to construct a vector of features $\\left(z_1,z_2,\\ldots,z_m\\right)$, with $m \\leq n$, which captures the key information about $y$, contained in $\\left(c_1,c_2,\\ldots,c_n; d_1,d_2,\\ldots,d_n\\right)$. The goal of the current section is to produce a function that takes in a pair of observations, in the form of $\\left(a_1,a_2,\\ldots,a_n; b_1,b_2,\\ldots,b_n\\right)$, as an input and produce $\\left(z_1,z_2,\\ldots,z_m\\right)$ as an output, i.e.\n\n$$ \\left(a_1,a_2,\\ldots,a_n; b_1,b_2,\\ldots,b_n\\right) \\mapsto \\left(z_1,z_2,\\ldots,z_m\\right). $$","metadata":{}},{"cell_type":"code","source":"# Typical observation from the 'data_pairs_train'\ndata_pairs_train.iloc[0]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.298242Z","iopub.execute_input":"2022-07-16T17:09:51.298697Z","iopub.status.idle":"2022-07-16T17:09:51.308866Z","shell.execute_reply.started":"2022-07-16T17:09:51.298661Z","shell.execute_reply":"2022-07-16T17:09:51.307830Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It contains a pair of observations. The *id* of the two observations are expectedly different. The *name* is slightly different, as are the *latitude* and *longitude*. *Country* and *category* are identical. Some of the attributes are missing in one of the observations, while some are missing in both. The target variable here is `match`, which is a Boolean variable taking the value `True` if the two observations refer to the same POI and `False` otherwise. We observe that the number of features can be greatly reduced if we focus on the information that are relevant in predicting `match`, and discard the rest. We initiate a dataframe to extract and store these relevant information out of the attributes in `data_pairs`.","metadata":{}},{"cell_type":"code","source":"# Dataframe initialization for new features\ndf_train = pd.DataFrame()\ndf_test = pd.DataFrame()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.310323Z","iopub.execute_input":"2022-07-16T17:09:51.310994Z","iopub.status.idle":"2022-07-16T17:09:51.317530Z","shell.execute_reply.started":"2022-07-16T17:09:51.310959Z","shell.execute_reply":"2022-07-16T17:09:51.316494Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Distance between Locations","metadata":{}},{"cell_type":"markdown","source":"The information that is relevant in predicting `match`, contained in `latitude_1`, `longitude_1`, `latitude_2` and `longitude_2`, can be encapsulted into a single variable, which is the distance `dist_loc` between the two locations (`latitude_1`, `longitude_1`) and (`latitude_2`, `longitude_2`), given by the haversine formula. Let $\\left(\\phi_1, \\lambda_1\\right)$ and $\\left(\\phi_2, \\lambda_2\\right)$ be the coordinates of two POIs. Then the distance between the two POIs is\n\n$$ d = 2r \\arcsin\\left(\\sqrt{\\text{hav}\\left(\\phi_1 - \\phi_2\\right) + \\text{cos}\\left(\\phi_1\\right) \\text{cos}\\left(\\phi_2\\right) \\text{hav}\\left(\\lambda_1 - \\lambda_2\\right)}\\right), $$\n\nwhere\n\n$$ \\text{hav}\\left(\\theta\\right) = \\sin^2\\left(\\frac{\\theta}{2}\\right) = \\frac{1-\\cos{\\theta}}{2}. $$","metadata":{}},{"cell_type":"code","source":"# Haversine formula\ndef dist(lat1, lon1, lat2, lon2):\n    \"\"\"\n    Computes the distance (over the surface) between two coordinates (lat1, lon1) and (lat2, lon2)\n    Args:\n      lat1 (float): latitude of first location\n      lon1 (float): longitude of first location\n      lat2 (float): latitude of second location\n      lon2 (float): longitude of second location\n    Returns:\n      d (float): distance between the two locations in km\n    \"\"\"\n    r = 6371\n    lat1, lon1, lat2, lon2 = np.radians(lat1), np.radians(lon1), np.radians(lat2), np.radians(lon2)\n    dlat, dlon = lat1 - lat2, lon1 - lon2\n    h = ((1 - cos(dlat)) / 2) + (cos(lat1) * cos(lat2) * ((1 - cos(dlon)) / 2))\n    d = 2 * r * asin(sqrt(h))\n    return d\n\nlat1, lon1, lat2, lon2 = 5.012169, 100.535805, 40.434209, -80.564160\nprint(f\"Input: ({lat1}, {lon1}) and ({lat2}, {lon2})\")\nprint(f\"Output: {dist(lat1, lon1, lat2, lon2)} km\")","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.320753Z","iopub.execute_input":"2022-07-16T17:09:51.321447Z","iopub.status.idle":"2022-07-16T17:09:51.332942Z","shell.execute_reply.started":"2022-07-16T17:09:51.321417Z","shell.execute_reply":"2022-07-16T17:09:51.331732Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Distance between locations\ndist_loc_train = [dist(data_pairs_train['latitude_1'][i], data_pairs_train['longitude_1'][i], data_pairs_train['latitude_2'][i], data_pairs_train['longitude_2'][i]) for i in data_pairs_train.index]\ndist_loc_test = [dist(data_pairs_test['latitude_1'][i], data_pairs_test['longitude_1'][i], data_pairs_test['latitude_2'][i], data_pairs_test['longitude_2'][i]) for i in data_pairs_test.index]\ndf_train['dist_loc'] = dist_loc_train\ndf_test['dist_loc'] = dist_loc_test","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:09:51.334351Z","iopub.execute_input":"2022-07-16T17:09:51.334993Z","iopub.status.idle":"2022-07-16T17:10:21.437220Z","shell.execute_reply.started":"2022-07-16T17:09:51.334965Z","shell.execute_reply":"2022-07-16T17:10:21.436002Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'dist_loc' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'dist_loc', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'dist_loc', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:21.444857Z","iopub.execute_input":"2022-07-16T17:10:21.445209Z","iopub.status.idle":"2022-07-16T17:10:22.098107Z","shell.execute_reply.started":"2022-07-16T17:10:21.445182Z","shell.execute_reply":"2022-07-16T17:10:22.097095Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"In both `df_train` and `df_test`, `dist_loc` is concentrated near $0$. It is likely that in both `df_train` and `df_test`, `dist_loc` is positively skewed to an extreme degree. To elaborate, [Skewness](https://en.wikipedia.org/wiki/Skewness) quantifies the asymmetry of a distribution about its mean. It is given by\n\n$$ g_1 := \\frac{\\frac{1}{n}\\sum_{i=1}^n\\left(x_i-\\bar{x}\\right)^3}{\\left[\\frac{1}{n}\\sum_{i=1}^n\\left(x_i-\\bar{x}\\right)^2\\right]^{3/2}}, $$\n\nwhere $\\bar{x}$ is the mean of the observations, given by $\\bar{x} = \\frac{1}{n}\\sum_{i=1}^n x_i$. The measure $g_1$ can be negative, zero, positive. A value close to $0$ suggests that the distribution is more or less symmetric. However, as it deviates from $0$, it becomes more and more skewed (either positively or negatively). A positive skewness indicates that the distribution is concentrated towards the left side, with the longer tail being on the right side. A negative skewness indicates that the distribution is concentrated towards the right side, with the longer tail being on the left side. We back up the observation about skewness of `dist_loc` in `df_train` and `df_test` by computing the corresponding $g_1$ values.","metadata":{}},{"cell_type":"code","source":"# Skewness of 'dist_loc'\nprint(pd.Series({\"Skewness of 'dist_loc' in 'df_train'\": df_train['dist_loc'].skew(),\n                 \"Skewness of 'dist_loc' in 'df_test'\": df_test['dist_loc'].skew()}).to_string())","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:22.099521Z","iopub.execute_input":"2022-07-16T17:10:22.099888Z","iopub.status.idle":"2022-07-16T17:10:22.112356Z","shell.execute_reply.started":"2022-07-16T17:10:22.099852Z","shell.execute_reply":"2022-07-16T17:10:22.110985Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"To deal with the extreme skewness, we have applied the following transformation:\n\n$$ x \\mapsto log(x+\\epsilon), $$\n\nwhere $\\epsilon$ is a very small positive real number. Here we have taken $\\epsilon = 0.00000001$. The reason behind making this small shift to the data is that the log function maps $0$ to $-\\infty$. The shift keeps the transformed data finite, and keeping $\\epsilon$ small ensures that the data points which were originally $0$, stands out from the rest in the transformed setup. Visualizations of the distribution of both the original feature and the transformed feature have been shown.","metadata":{}},{"cell_type":"code","source":"# Applying the transformation\nepsilon = 0.00000001\ndf_train['dist_loc_transformed'] = df_train['dist_loc'].apply(lambda x: np.log(x + epsilon))\ndf_test['dist_loc_transformed'] = df_test['dist_loc'].apply(lambda x: np.log(x + epsilon))","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:22.113927Z","iopub.execute_input":"2022-07-16T17:10:22.114804Z","iopub.status.idle":"2022-07-16T17:10:23.199372Z","shell.execute_reply.started":"2022-07-16T17:10:22.114774Z","shell.execute_reply":"2022-07-16T17:10:23.197994Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Deleting old features\ndf_train.drop('dist_loc', axis = 1, inplace = True)\ndf_test.drop('dist_loc', axis = 1, inplace = True)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:23.200705Z","iopub.execute_input":"2022-07-16T17:10:23.201357Z","iopub.status.idle":"2022-07-16T17:10:23.211687Z","shell.execute_reply.started":"2022-07-16T17:10:23.201328Z","shell.execute_reply":"2022-07-16T17:10:23.210571Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'dist_loc_transformed' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'dist_loc_transformed', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'dist_loc_transformed', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:23.212924Z","iopub.execute_input":"2022-07-16T17:10:23.213281Z","iopub.status.idle":"2022-07-16T17:10:23.823241Z","shell.execute_reply.started":"2022-07-16T17:10:23.213249Z","shell.execute_reply":"2022-07-16T17:10:23.821568Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# MinMax normalization of 'dist_loc_transformed'\nloc_train, loc_test = df_train['dist_loc_transformed'], df_test['dist_loc_transformed']\ndf_train['dist_loc_transformed'] = (loc_train - loc_train.min()) / (loc_train.max() - loc_train.min())\ndf_test['dist_loc_transformed'] = (loc_test - loc_test.min()) / (loc_test.max() - loc_test.min())","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:23.824903Z","iopub.execute_input":"2022-07-16T17:10:23.825210Z","iopub.status.idle":"2022-07-16T17:10:23.837850Z","shell.execute_reply.started":"2022-07-16T17:10:23.825182Z","shell.execute_reply":"2022-07-16T17:10:23.836380Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Features Based on Largest Common Substring","metadata":{}},{"cell_type":"markdown","source":"We observe that, in `data_pairs_train` and `data_pairs_test`, the name for the same POI varies in different records for variety of reasons. For example, some records may contain shortened versions of the names. Similar phenomenon is observed in the city, state and categories attribute. For these reasons, we create similarity features based on these attributes using the length of the largest common substring of two strings, relative to the length of the shorter string. Note that we have to convert some of the input data to string format before feeding it to the function that computes this quantity.","metadata":{}},{"cell_type":"code","source":"# Relative length proportion of largest common substring of two strings\ndef lcss(str1, str2):\n    \"\"\"\n    Computes length proportion of largest common substring of two strings, relative to the length of the shorter string\n    Args:\n      str1 (string): a general string\n      str2 (string): a general string\n    Returns:\n      prop (float): length of the largest common substring of two strings, scaled by length of the shorter string\n    \"\"\"\n    n1, n2 = len(str1), len(str2)\n    lc = [[0 for k in range(n2 + 1)] for l in range(n1 + 1)]\n    out = 0\n    for i in range(n1 + 1):\n        for j in range(n2 + 1):\n            if (i == 0 or j == 0):\n                lc[i][j] = 0\n            elif (str1[i-1] == str2[j-1]):\n                lc[i][j] = lc[i-1][j-1] + 1\n                out = max(out, lc[i][j])\n            else:\n                lc[i][j] = 0\n    prop = out / min(n1, n2)\n    return prop\n\nstr1, str2 = '118th street bus stop', '118th street beach'\nprint(f\"Input: '{str1}' and '{str2}'\")\nprint(f\"Output: {lcss(str1, str2)}\")","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:23.839431Z","iopub.execute_input":"2022-07-16T17:10:23.839921Z","iopub.status.idle":"2022-07-16T17:10:23.852832Z","shell.execute_reply.started":"2022-07-16T17:10:23.839893Z","shell.execute_reply":"2022-07-16T17:10:23.851635Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Relative length of largest common substring between names, cities, states and categories\nlcss_name_train, lcss_name_test = [], []\nlcss_city_train, lcss_city_test = [], []\nlcss_state_train, lcss_state_test = [], []\nlcss_categories_train, lcss_categories_test = [], []\nfor i in data_pairs_train.index:\n    lcss_name_train.append(lcss(data_pairs_train['name_1'][i], data_pairs_train['name_2'][i]))\n    lcss_city_train.append(lcss(data_pairs_train['city_1'][i], data_pairs_train['city_2'][i]))\n    lcss_state_train.append(lcss(data_pairs_train['state_1'][i], data_pairs_train['state_2'][i]))\n    lcss_categories_train.append(lcss(data_pairs_train['categories_1'][i], data_pairs_train['categories_2'][i]))\nfor i in data_pairs_test.index:\n    lcss_name_test.append(lcss(data_pairs_test['name_1'][i], data_pairs_test['name_2'][i]))\n    lcss_city_test.append(lcss(data_pairs_test['city_1'][i], data_pairs_test['city_2'][i]))\n    lcss_state_test.append(lcss(data_pairs_test['state_1'][i], data_pairs_test['state_2'][i]))\n    lcss_categories_test.append(lcss(data_pairs_test['categories_1'][i], data_pairs_test['categories_2'][i]))\ndf_train['lcss_name'], df_test['lcss_name'] = lcss_name_train, lcss_name_test\ndf_train['lcss_city'], df_test['lcss_city'] = lcss_city_train, lcss_city_test\ndf_train['lcss_state'], df_test['lcss_state'] = lcss_state_train, lcss_state_test\ndf_train['lcss_categories'], df_test['lcss_categories'] = lcss_categories_train, lcss_categories_test","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:10:23.854536Z","iopub.execute_input":"2022-07-16T17:10:23.854932Z","iopub.status.idle":"2022-07-16T17:18:19.601075Z","shell.execute_reply.started":"2022-07-16T17:10:23.854896Z","shell.execute_reply":"2022-07-16T17:18:19.599966Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'lcss_name' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'lcss_name', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'lcss_name', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:19.602462Z","iopub.execute_input":"2022-07-16T17:18:19.602747Z","iopub.status.idle":"2022-07-16T17:18:20.484179Z","shell.execute_reply.started":"2022-07-16T17:18:19.602720Z","shell.execute_reply":"2022-07-16T17:18:20.483418Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'lcss_city' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'lcss_city', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'lcss_city', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:20.485617Z","iopub.execute_input":"2022-07-16T17:18:20.485916Z","iopub.status.idle":"2022-07-16T17:18:21.112893Z","shell.execute_reply.started":"2022-07-16T17:18:20.485880Z","shell.execute_reply":"2022-07-16T17:18:21.111612Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'lcss_state' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'lcss_state', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'lcss_state', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:21.114805Z","iopub.execute_input":"2022-07-16T17:18:21.115363Z","iopub.status.idle":"2022-07-16T17:18:21.726005Z","shell.execute_reply.started":"2022-07-16T17:18:21.115324Z","shell.execute_reply":"2022-07-16T17:18:21.725066Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Histogram of 'lcss_categories' for 'df_train' and 'df_test'\nfig, ax = plt.subplots(1, 2, figsize = (15, 6), sharey = True)\nsns.histplot(data = df_train, x = 'lcss_categories', bins = 30, ax = ax[0])\nsns.histplot(data = df_test, x = 'lcss_categories', bins = 30, ax = ax[1])\nax[0].set_title(\"df_train\", fontsize = 14)\nax[1].set_title(\"df_test\", fontsize = 14)\nax[1].set_ylabel(\"\")\nplt.tight_layout()\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:21.727372Z","iopub.execute_input":"2022-07-16T17:18:21.727649Z","iopub.status.idle":"2022-07-16T17:18:22.350387Z","shell.execute_reply.started":"2022-07-16T17:18:21.727623Z","shell.execute_reply":"2022-07-16T17:18:22.349345Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Matching of Countries","metadata":{}},{"cell_type":"code","source":"# Matching of countries\ndf_train['match_country'] = [float(data_pairs_train['country_1'][i] == data_pairs_train['country_2'][i]) for i in data_pairs_train.index]\ndf_test['match_country'] = [float(data_pairs_test['country_1'][i] == data_pairs_test['country_2'][i]) for i in data_pairs_test.index]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:22.351654Z","iopub.execute_input":"2022-07-16T17:18:22.352374Z","iopub.status.idle":"2022-07-16T17:18:34.452345Z","shell.execute_reply.started":"2022-07-16T17:18:22.352347Z","shell.execute_reply":"2022-07-16T17:18:34.451037Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Donutplots of the 'match_country' column\nfig = make_subplots(rows = 1, cols = 2, specs = [[{'type': 'domain'}, {'type': 'domain'}]])\nx_val_train = df_train['match_country'].value_counts(sort = False).index.tolist()\ny_val_train = df_train['match_country'].value_counts(sort = False).tolist()\nx_val_test = df_test['match_country'].value_counts(sort = False).index.tolist()\ny_val_test = df_test['match_country'].value_counts(sort = False).tolist()\nfig.add_trace(go.Pie(values = y_val_train, labels = x_val_train, hole = 0.5, textinfo = 'label+percent', title = \"Train\"), row = 1, col = 1)\nfig.add_trace(go.Pie(values = y_val_test, labels = x_val_test, hole = 0.5, textinfo = 'label+percent', title = \"Test\"), row = 1, col = 2)\nfig.update_layout(height = 500, width = 800, showlegend = False, xaxis = dict(tickmode = 'linear', tick0 = 0, dtick = 1), title = dict(text = \"Frequency comparison of 'match_country'\", x = 0.5, y = 0.95)) \nfig.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:34.453883Z","iopub.execute_input":"2022-07-16T17:18:34.454191Z","iopub.status.idle":"2022-07-16T17:18:34.506690Z","shell.execute_reply.started":"2022-07-16T17:18:34.454164Z","shell.execute_reply":"2022-07-16T17:18:34.505757Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## The Target Variable","metadata":{}},{"cell_type":"code","source":"# 'match' column\ndf_train['match'] = [float(data_pairs_train['match'][i]) for i in data_pairs_train.index]\ndf_test['match'] = [float(data_pairs_test['match'][i]) for i in data_pairs_test.index]","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:34.507771Z","iopub.execute_input":"2022-07-16T17:18:34.508766Z","iopub.status.idle":"2022-07-16T17:18:40.927082Z","shell.execute_reply.started":"2022-07-16T17:18:34.508737Z","shell.execute_reply":"2022-07-16T17:18:40.926011Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"From this point on, we shall refer to `df_train` as the *effective training set*, or just `training set` and `df_test` as the *effective test set*, or just `test set`. We shall refer to the five-observations-strong `data_test` as the *true test set*.","metadata":{}},{"cell_type":"code","source":"# Effective training set\nprint(pd.Series({\"Memory usage\": \"{:.2f} MB\".format(df_train.memory_usage().sum()/(1024*1024)),\n                 \"Dataframe shape\": \"{}\".format(df_train.shape)}).to_string())\nprint(\" \")\ndf_train.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:40.928646Z","iopub.execute_input":"2022-07-16T17:18:40.928988Z","iopub.status.idle":"2022-07-16T17:18:40.952977Z","shell.execute_reply.started":"2022-07-16T17:18:40.928954Z","shell.execute_reply":"2022-07-16T17:18:40.951639Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Effective test set\nprint(pd.Series({\"Memory usage\": \"{:.2f} MB\".format(df_test.memory_usage().sum()/(1024*1024)),\n                 \"Dataframe shape\": \"{}\".format(df_test.shape)}).to_string())\nprint(\" \")\ndf_test.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:40.954534Z","iopub.execute_input":"2022-07-16T17:18:40.954810Z","iopub.status.idle":"2022-07-16T17:18:40.975047Z","shell.execute_reply.started":"2022-07-16T17:18:40.954784Z","shell.execute_reply":"2022-07-16T17:18:40.973739Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 5. Baseline XGBoost","metadata":{}},{"cell_type":"markdown","source":"Each row in `df_train` or `df_test` are of the form $\\left(z_1,z_2,\\ldots,z_m\\right)$, which is essentially a vector representing the differences between two POI observations. The task of modeling is to predict the `match` variable $y$ based on $\\left(z_1,z_2,\\ldots,z_m\\right)$, i.e.\n\n$$ \\left(z_1,z_2,\\ldots,z_m\\right) \\mapsto \\hat{y} \\,\\,(\\text{estimation of } y). $$\n\nThe plan is to train a baseline XGBoost classifier on `df_train`, and evaluate it on `df_test`. First, we separate out the target variable from the feature variables.","metadata":{}},{"cell_type":"code","source":"# Feature-target split\nX_train, y_train = df_train.drop('match', axis = 1), df_train['match']\nX_test, y_test = df_test.drop('match', axis = 1), df_test['match']","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:40.976737Z","iopub.execute_input":"2022-07-16T17:18:40.977090Z","iopub.status.idle":"2022-07-16T17:18:41.003359Z","shell.execute_reply.started":"2022-07-16T17:18:40.977037Z","shell.execute_reply":"2022-07-16T17:18:41.002258Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Next, we construct functions to compute and display the *confusion matrix*, given the true labels and the predicted labels of the target.","metadata":{}},{"cell_type":"code","source":"# Function to compute confusion matrix\ndef conf_mat(y_test, y_pred):\n    \"\"\"\n    Computes confusion matrix\n    Args:\n      y_test (list/array/tuple/set/series): true binary (0/1) labels\n      y_pred (list/array/tuple/set/series): predicted binary (0/1) labels\n    Returns:\n      confusion_mat (array): A 2D array representing a 2x2 confusion matrix\n    \"\"\"\n    y_test, y_pred = list(y_test), list(y_pred)\n    count, labels, confusion_mat = len(y_test), [0, 1], np.zeros(shape = (2, 2), dtype = int)\n    for i in range(2):\n        for j in range(2):\n            confusion_mat[i][j] = len([k for k in range(count) if y_test[k] == labels[i] and y_pred[k] == labels[j]])\n    return confusion_mat","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:41.004771Z","iopub.execute_input":"2022-07-16T17:18:41.005155Z","iopub.status.idle":"2022-07-16T17:18:41.014390Z","shell.execute_reply.started":"2022-07-16T17:18:41.005119Z","shell.execute_reply":"2022-07-16T17:18:41.013510Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Function to print confusion matrix\ndef conf_mat_heatmap(y_test, y_pred):\n    \"\"\"\n    Prints confusion matrix\n    Args:\n      y_test (list/array/tuple/set/series): true binary (0/1) labels\n      y_pred (list/array/tuple/set/series): predicted binary (0/1) labels\n    Returns:\n      Nothing, prints a heatmap representing a 2x2 confusion matrix\n    \"\"\"\n    confusion_mat = conf_mat(y_test, y_pred)\n    labels, confusion_mat_df = [0, 1], pd.DataFrame(confusion_mat, range(2), range(2))\n    plt.figure(figsize = (6, 4.75))\n    # sns.set(font_scale = 1.4) # label size\n    sns.heatmap(confusion_mat_df, annot = True, annot_kws = {\"size\": 16}, fmt = 'd')\n    plt.xticks([0.5, 1.5], labels, rotation = 'horizontal')\n    plt.yticks([0.5, 1.5], labels, rotation = 'horizontal')\n    plt.xlabel(\"Predicted label\", fontsize = 14)\n    plt.ylabel(\"True label\", fontsize = 14)\n    plt.title(\"Confusion Matrix\", fontsize = 14)\n    plt.grid(False)\n    plt.show()","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:41.015678Z","iopub.execute_input":"2022-07-16T17:18:41.015948Z","iopub.status.idle":"2022-07-16T17:18:41.029574Z","shell.execute_reply.started":"2022-07-16T17:18:41.015922Z","shell.execute_reply":"2022-07-16T17:18:41.028896Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We shall use the *accuracy* measure as an evaluation metric to assess the models. The measure is given by\n\n$$ \\text{Accuracy} = \\frac{\\text{Number of correct predictions}}{\\text{Number of total predictions}}. $$","metadata":{}},{"cell_type":"code","source":"# Function to compute accuracy\ndef accuracy(y_test, y_pred):\n    \"\"\"\n    Computes accuracy, given true and predicted binary (0/1) labels\n    Args:\n      y_test (list/array/tuple/set/series): true binary (0/1) labels\n      y_pred (list/array/tuple/set/series): predicted binary (0/1) labels\n    Returns:\n      acc (float): accuracy obtained from y_test and y_pred\n    \"\"\"\n    confusion_mat = conf_mat(y_test, y_pred)\n    num = confusion_mat[0, 0] + confusion_mat[1, 1]\n    denom = num + confusion_mat[0, 1] + confusion_mat[1, 0]\n    acc = num / denom\n    return acc","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:18:41.030962Z","iopub.execute_input":"2022-07-16T17:18:41.031295Z","iopub.status.idle":"2022-07-16T17:18:41.041531Z","shell.execute_reply.started":"2022-07-16T17:18:41.031260Z","shell.execute_reply":"2022-07-16T17:18:41.040773Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now, we consider the XGBoost classifier, fit the model on the training set, predict and evaluate on both the training set and the test set, and report the respective accuracy scores. Furthermore, we print the confusion matrix for the predictions on observations in the test set.","metadata":{}},{"cell_type":"code","source":"# Model\nxgb = XGBClassifier()\nprint(f\"Model: {xgb}\")\n\n# Fitting the model on the training set\nxgb.fit(X_train, y_train)\n\n# Prediction and evaluation on the training set\ny_train_pred = xgb.predict(X_train)\nscore_train = accuracy(y_train, y_train_pred)\nprint(f\"Training accuracy: {score_train}\")\n\n# Prediction and evaluation on the test set\ny_test_pred = xgb.predict(X_test)\nscore_test = accuracy(y_test, y_test_pred)\nprint(f\"Test accuracy: {score_test}\")\n\n# Confusion matrix for prediction on the test set\nconf_mat_heatmap(y_test, y_test_pred)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T17:19:30.029219Z","iopub.execute_input":"2022-07-16T17:19:30.029577Z","iopub.status.idle":"2022-07-16T17:19:53.075135Z","shell.execute_reply.started":"2022-07-16T17:19:30.029548Z","shell.execute_reply":"2022-07-16T17:19:53.073495Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# 6. Hyperparameter Tuning","metadata":{}},{"cell_type":"code","source":"%%time\n# Hyperparameter tuning for XGBoost\ncv = KFold(n_splits = 6, shuffle = True, random_state = 40).split(X = X_train, y = y_train)\nxgb = XGBClassifier()\nparams = {\n    'subsample': [0.5, 1],\n    'max_depth': [6],\n    'learning_rate': [0.01, 0.2, 0.3],\n    'gamma': [0, 0.5, 1, 2],\n    'reg_alpha': [0, 0.5, 1]\n}\ngsearch_xgb = GridSearchCV(estimator = xgb, param_grid = params, scoring = 'accuracy', n_jobs = -1, cv = cv, verbose = 1)\ngsearch_xgb_fit = gsearch_xgb.fit(X = X_train, y = y_train)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T18:22:17.508532Z","iopub.execute_input":"2022-07-16T18:22:17.509002Z","iopub.status.idle":"2022-07-16T19:54:51.431043Z","shell.execute_reply.started":"2022-07-16T18:22:17.508953Z","shell.execute_reply":"2022-07-16T19:54:51.430096Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Best parameters and score\nprint(f\"Best parameters: {gsearch_xgb.best_params_}\")\nprint(f\"Best cross-validation accuracy: {gsearch_xgb.best_score_}\")","metadata":{"execution":{"iopub.status.busy":"2022-07-16T19:54:51.433220Z","iopub.execute_input":"2022-07-16T19:54:51.433755Z","iopub.status.idle":"2022-07-16T19:54:51.438664Z","shell.execute_reply.started":"2022-07-16T19:54:51.433722Z","shell.execute_reply":"2022-07-16T19:54:51.438007Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Model\nxgb_best = gsearch_xgb.best_estimator_\nprint(f\"Model: {xgb_best}\")\n\n# Fitting the model on the training set\nxgb_best.fit(X_train, y_train)\n\n# Prediction and evaluation on the training set\ny_train_pred_tuning = xgb_best.predict(X_train)\nscore_train = accuracy(y_train, y_train_pred_tuning)\nprint(f\"Training accuracy: {score_train}\")\n\n# Prediction and evaluation on the test set\ny_test_pred_tuning = xgb_best.predict(X_test)\nscore_test = accuracy(y_test, y_test_pred_tuning)\nprint(f\"Test accuracy: {score_test}\")\n\n# Confusion matrix for prediction on the test set\nconf_mat_heatmap(y_test, y_test_pred_tuning)","metadata":{"execution":{"iopub.status.busy":"2022-07-16T19:54:51.439780Z","iopub.execute_input":"2022-07-16T19:54:51.440267Z","iopub.status.idle":"2022-07-16T19:55:14.823752Z","shell.execute_reply.started":"2022-07-16T19:54:51.440239Z","shell.execute_reply":"2022-07-16T19:55:14.822427Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"- Hyperparameter tuning very slightly increases the test accuracy\n- It improves performance of the model over the positive class (observations with true label $1$)\n- On the flip side, it slightly worsens performance of the model over the negative class (observations with true label $0$)","metadata":{}},{"cell_type":"markdown","source":"# Acknowledgements\n\n- [Foursquare - Location Matching](https://www.kaggle.com/competitions/foursquare-location-matching) competition","metadata":{}},{"cell_type":"markdown","source":"# References\n\n- [Case sensitivity](https://en.wikipedia.org/wiki/Case_sensitivity)\n- [Correlation coefficient](https://en.wikipedia.org/wiki/Pearson_correlation_coefficient)\n- [Foursquare City Guide](https://en.wikipedia.org/wiki/Foursquare_City_Guide)\n- [Foursquare Labs Inc.](https://foursquare.com/)\n- [Foursquare Swarm](https://en.wikipedia.org/wiki/Foursquare_Swarm)\n- [Grove Karl Gilbert](https://en.wikipedia.org/wiki/Grove_Karl_Gilbert)\n- [Haversine formula](https://en.wikipedia.org/wiki/Haversine_formula)\n- [Hyperparameter optimization](https://en.wikipedia.org/wiki/Hyperparameter_optimization)\n- [ISO 3166-1 alpha-2](https://en.wikipedia.org/wiki/ISO_3166-1_alpha-2)\n- [Jaccard index](https://en.wikipedia.org/wiki/Jaccard_index)\n- [Jaccard/Tanimoto similarity test and estimation methods for biological presence-absence data](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-019-3118-5)\n- [Jaccard/Tanimoto similarity test and estimation methods (arxiv version)](https://arxiv.org/abs/1903.11372)\n- [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance)\n- [List of U.S. state and territory abbreviations](https://en.wikipedia.org/wiki/List_of_U.S._state_and_territory_abbreviations)\n- [Olympus Mons](https://en.wikipedia.org/wiki/Olympus_Mons)\n- [Paul Jaccard](https://en.wikipedia.org/wiki/Paul_Jaccard)\n- [Point of Interest](https://en.wikipedia.org/wiki/Point_of_interest)\n- [Skewness](https://en.wikipedia.org/wiki/Skewness)\n- [Vladimir Levenshtein](https://en.wikipedia.org/wiki/Vladimir_Levenshtein)\n- [XGBoost](https://en.wikipedia.org/wiki/XGBoost)","metadata":{}},{"cell_type":"code","source":"# Runtime and memory usage\nstop = time.time()\nprint(pd.Series({\"Process runtime\": \"{:.2f} seconds\".format(float(stop - start)),\n                 \"Process memory usage\": \"{:.2f} MB\".format(float(process.memory_info()[0]/(1024*1024)))}).to_string())","metadata":{"execution":{"iopub.status.busy":"2022-07-16T19:55:14.826347Z","iopub.execute_input":"2022-07-16T19:55:14.826749Z","iopub.status.idle":"2022-07-16T19:55:14.837013Z","shell.execute_reply.started":"2022-07-16T19:55:14.826711Z","shell.execute_reply":"2022-07-16T19:55:14.835746Z"},"trusted":true},"execution_count":null,"outputs":[]}]}