{"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> Sugata Ghosh </center></h2>","metadata":{"papermill":{"duration":0.0044,"end_time":"2022-07-05T11:58:37.453851","exception":false,"start_time":"2022-07-05T11:58:37.449451","status":"completed"},"tags":[]}},{"cell_type":"code","source":"# Importing libraries\nimport time\nimport numpy as np\nimport pandas as pd \nfrom sklearn.neighbors import BallTree","metadata":{"papermill":{"duration":1.317043,"end_time":"2022-07-05T11:58:38.774322","exception":false,"start_time":"2022-07-05T11:58:37.457279","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:19.932682Z","iopub.execute_input":"2022-07-07T09:54:19.93309Z","iopub.status.idle":"2022-07-07T09:54:19.938919Z","shell.execute_reply.started":"2022-07-07T09:54:19.933057Z","shell.execute_reply":"2022-07-07T09:54:19.937609Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Recording the starting time, complemented with a stopping time check in the end to compute process runtime\nstart = time.time()","metadata":{"papermill":{"duration":0.012724,"end_time":"2022-07-05T11:58:38.790526","exception":false,"start_time":"2022-07-05T11:58:38.777802","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:19.945704Z","iopub.execute_input":"2022-07-07T09:54:19.946403Z","iopub.status.idle":"2022-07-07T09:54:19.952028Z","shell.execute_reply.started":"2022-07-07T09:54:19.946354Z","shell.execute_reply":"2022-07-07T09:54:19.951037Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Loading the test data\ntest = pd.read_csv('../input/foursquare-location-matching/test.csv')","metadata":{"papermill":{"duration":0.025243,"end_time":"2022-07-05T11:58:38.819217","exception":false,"start_time":"2022-07-05T11:58:38.793974","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:19.961192Z","iopub.execute_input":"2022-07-07T09:54:19.96156Z","iopub.status.idle":"2022-07-07T09:54:19.971624Z","shell.execute_reply.started":"2022-07-07T09:54:19.961528Z","shell.execute_reply":"2022-07-07T09:54:19.970801Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Missing data handling\ntest['name'] = test['name'].fillna('NaN')\ntest['country'] = test['country'].fillna('NaN')\ntest['categories'] = test['categories'].fillna('NaN')\n\n# Converting to string format\ntest['name'] = [str(test['name'][i]) for i in test.index]\ntest['categories'] = [str(test['categories'][i]) for i in test.index]","metadata":{"papermill":{"duration":0.024019,"end_time":"2022-07-05T11:58:38.846888","exception":false,"start_time":"2022-07-05T11:58:38.822869","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:19.976754Z","iopub.execute_input":"2022-07-07T09:54:19.977893Z","iopub.status.idle":"2022-07-07T09:54:19.989105Z","shell.execute_reply.started":"2022-07-07T09:54:19.977858Z","shell.execute_reply":"2022-07-07T09:54:19.988173Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# BallTree\nball_tree = BallTree(np.deg2rad(test[['latitude', 'longitude']].values), metric = 'haversine')","metadata":{"papermill":{"duration":0.021741,"end_time":"2022-07-05T11:58:38.872265","exception":false,"start_time":"2022-07-05T11:58:38.850524","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:19.991466Z","iopub.execute_input":"2022-07-07T09:54:19.992663Z","iopub.status.idle":"2022-07-07T09:54:20.007613Z","shell.execute_reply.started":"2022-07-07T09:54:19.99262Z","shell.execute_reply":"2022-07-07T09:54:20.006542Z"},"trusted":true},"execution_count":null,"outputs":[]},{"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\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","metadata":{"papermill":{"duration":0.018353,"end_time":"2022-07-05T11:58:38.89453","exception":false,"start_time":"2022-07-05T11:58:38.876177","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:20.011387Z","iopub.execute_input":"2022-07-07T09:54:20.011964Z","iopub.status.idle":"2022-07-07T09:54:20.021355Z","shell.execute_reply.started":"2022-07-07T09:54:20.011932Z","shell.execute_reply":"2022-07-07T09:54:20.019983Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n# List of matches\nmatches = []\nn_neigbours, max_match, max_dist = min(10, len(test)), 4, 0.5\nfor i, row in test.iterrows():\n    dist, ind = ball_tree.query(np.deg2rad(np.c_[row['latitude'], row['longitude']]), k = n_neigbours)\n    id_match = []\n    for d, j in zip(dist[0], ind[0]):\n        c11 = (row['name'] != 'NaN')\n        c12 = (lcss(row['name'], test['name'][j]) > 0.5)\n        c21 = (row['country'] != 'NaN')\n        c22 = (row['country'] in test['country'][j] or test['country'][j] in row['country'])\n        c31 = (row['categories'] != 'NaN')\n        c32 = (lcss(row['categories'], test['categories'][j]) > 0.5)\n        \n        if d <= max_dist and c11 and c12 and c21 and c22 and c31 and c32:\n            id_match.append(test['id'][j])\n        if d > max_dist or len(id_match) >= max_match:\n            break\n    \n    if len(id_match) == 0:\n        matches.append(row['id'])\n    else:\n        matches.append(' '.join(id_match))","metadata":{"papermill":{"duration":0.026765,"end_time":"2022-07-05T11:58:38.925034","exception":false,"start_time":"2022-07-05T11:58:38.898269","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:20.023057Z","iopub.execute_input":"2022-07-07T09:54:20.023447Z","iopub.status.idle":"2022-07-07T09:54:20.046537Z","shell.execute_reply.started":"2022-07-07T09:54:20.023414Z","shell.execute_reply":"2022-07-07T09:54:20.045219Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Submission DataFrame\ndf_submission = pd.DataFrame()\ndf_submission['id'] = test['id']\ndf_submission['matches'] = matches\ndf_submission.head()","metadata":{"papermill":{"duration":0.029534,"end_time":"2022-07-05T11:58:38.959272","exception":false,"start_time":"2022-07-05T11:58:38.929738","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:20.047975Z","iopub.execute_input":"2022-07-07T09:54:20.049209Z","iopub.status.idle":"2022-07-07T09:54:20.062449Z","shell.execute_reply.started":"2022-07-07T09:54:20.049134Z","shell.execute_reply":"2022-07-07T09:54:20.061547Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"test","metadata":{"execution":{"iopub.status.busy":"2022-07-07T09:54:20.124427Z","iopub.execute_input":"2022-07-07T09:54:20.125101Z","iopub.status.idle":"2022-07-07T09:54:20.144151Z","shell.execute_reply.started":"2022-07-07T09:54:20.125062Z","shell.execute_reply":"2022-07-07T09:54:20.143102Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Submission\ndf_submission.to_csv('submission.csv', index = False)","metadata":{"papermill":{"duration":0.016677,"end_time":"2022-07-05T11:58:38.98009","exception":false,"start_time":"2022-07-05T11:58:38.963413","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:20.146265Z","iopub.execute_input":"2022-07-07T09:54:20.14659Z","iopub.status.idle":"2022-07-07T09:54:20.156544Z","shell.execute_reply.started":"2022-07-07T09:54:20.146561Z","shell.execute_reply":"2022-07-07T09:54:20.155696Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Recording the stopping time and computing process runtime\nstop = time.time()\nprint(pd.Series({\"Process runtime\": \"{:.2f} seconds\".format(float(stop - start))}).to_string())","metadata":{"papermill":{"duration":0.015807,"end_time":"2022-07-05T11:58:39.000212","exception":false,"start_time":"2022-07-05T11:58:38.984405","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2022-07-07T09:54:20.157645Z","iopub.execute_input":"2022-07-07T09:54:20.157967Z","iopub.status.idle":"2022-07-07T09:54:20.167838Z","shell.execute_reply.started":"2022-07-07T09:54:20.157938Z","shell.execute_reply":"2022-07-07T09:54:20.166729Z"},"trusted":true},"execution_count":null,"outputs":[]}]}