{"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":"___\n# **Librairies**","metadata":{}},{"cell_type":"code","source":"import pandas as pd\nimport re\nimport numpy as np\nfrom tqdm import tqdm\nfrom scipy import spatial\nfrom difflib import SequenceMatcher\nfrom collections import Counter\nfrom tqdm import tqdm\nfrom sklearn import preprocessing\nfrom sklearn.utils import shuffle\nfrom sklearn.ensemble import RandomForestClassifier\nfrom sklearn import svm\nfrom sklearn.neural_network import MLPClassifier\nfrom sklearn.decomposition import PCA\n#from sklearn.linear_model import SGDClassifier\nfrom sklearn.metrics import confusion_matrix, classification_report\nfrom sklearn.preprocessing import StandardScaler, LabelEncoder\nfrom sklearn.model_selection import train_test_split\nfrom sklearn.metrics import classification_report, confusion_matrix, accuracy_score\nfrom sklearn.neighbors import KNeighborsRegressor\nfrom sklearn.svm import SVR\nfrom sklearn.metrics import r2_score\nfrom sklearn.naive_bayes import GaussianNB\nfrom sklearn.linear_model import LogisticRegression\nfrom sklearn.metrics import roc_auc_score\nfrom sklearn.metrics import roc_curve\n\nimport Levenshtein\nimport difflib\nfrom unidecode import unidecode\n\nimport gc\nimport lightgbm as lgb\nimport matplotlib.pyplot as plt\nimport joblib\nimport seaborn as sns\nfrom collections import defaultdict\nfrom sklearn.feature_extraction.text import TfidfVectorizer\nfrom sklearn.metrics.pairwise import linear_kernel # faster than cosine_similarity\nfrom sklearn.metrics.pairwise import cosine_similarity\nimport psutil\nimport re","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:12.689763Z","iopub.execute_input":"2022-07-08T15:45:12.690107Z","iopub.status.idle":"2022-07-08T15:45:14.680194Z","shell.execute_reply.started":"2022-07-08T15:45:12.690022Z","shell.execute_reply":"2022-07-08T15:45:14.679217Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def distance(lat1,lon1,lat2,lon2): # en km\n    from math import sin, cos, sqrt, atan2, radians\n    R = 6373.0\n\n    lat1 = radians(abs(lat1))\n    lon1 = radians(abs(lon1))\n    lat2 = radians(abs(lat2))\n    lon2 = radians(abs(lon2))\n    dlon = lon2 - lon1\n    dlat = lat2 - lat1\n\n    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2\n    c = 2 * atan2(sqrt(a), sqrt(1 - a))\n\n    distance = R * c\n    return distance","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:14.682164Z","iopub.execute_input":"2022-07-08T15:45:14.682779Z","iopub.status.idle":"2022-07-08T15:45:14.692172Z","shell.execute_reply.started":"2022-07-08T15:45:14.682716Z","shell.execute_reply":"2022-07-08T15:45:14.691295Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Open Data**","metadata":{}},{"cell_type":"code","source":"df_train = pd.read_csv(\"../input/foursquare-location-matching/train.csv\") #.iloc[:50000]\nprint(df_train.shape)\ndf_train.head(1)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:14.693506Z","iopub.execute_input":"2022-07-08T15:45:14.694008Z","iopub.status.idle":"2022-07-08T15:45:23.579986Z","shell.execute_reply.started":"2022-07-08T15:45:14.693972Z","shell.execute_reply":"2022-07-08T15:45:23.578913Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Clean categories**","metadata":{}},{"cell_type":"code","source":"# remove all spaces, symbols, lower case\ndef st(x, remove_space):\n    # turn to latin alphabet\n    x = unidecode(x)\n    # lower case\n    x = x.lower()\n    # remove symbols\n    x = x.replace('\"', \"\")\n    ss = \":;'/-+&()!#$%*.|\\@`~^<>?[]{}_=\\n\"\n    if remove_space :\n        ss = \" \" + ss\n    for i in range(len(ss)):\n        x = x.replace(ss[i], \"\")\n    return x\ndef st2(x): # remove numbers - applies to cities only\n    ss = \" 0123456789\"\n    for i in range(len(ss)):\n        x = x.replace(ss[i], \"\")\n    return x\n\n# Apply function\ndf_train['name'] = df_train['name'].astype('str').apply(lambda x : st(x, remove_space=False))\ndf_train['categories'] = df_train['categories'].astype('str').apply(lambda x : st(x, remove_space=True))\n\n# Nan replaced by ''\ndf_train['categories'].loc[df_train['categories']=='nan'] = ''","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:23.582147Z","iopub.execute_input":"2022-07-08T15:45:23.582454Z","iopub.status.idle":"2022-07-08T15:45:24.794114Z","shell.execute_reply.started":"2022-07-08T15:45:23.582419Z","shell.execute_reply":"2022-07-08T15:45:24.793019Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_train.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:24.795318Z","iopub.execute_input":"2022-07-08T15:45:24.796005Z","iopub.status.idle":"2022-07-08T15:45:24.813885Z","shell.execute_reply.started":"2022-07-08T15:45:24.795967Z","shell.execute_reply":"2022-07-08T15:45:24.813032Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **List and count of categories**","metadata":{}},{"cell_type":"code","source":"cats = df_train['categories'].to_list()\ncats = [x for cat in cats for x in cat.split(',') if cat != '']\n\n# Keep only letters\ncats = [re.sub(r'[^a-zA-Z]', ' ', x) for x in cats]\n        \n# Delete multi space\ncats = [re.sub('\\\\s+', ' ', x).strip() for x in cats]\n\ncats[:10]","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:24.815286Z","iopub.execute_input":"2022-07-08T15:45:24.815528Z","iopub.status.idle":"2022-07-08T15:45:25.042438Z","shell.execute_reply.started":"2022-07-08T15:45:24.815499Z","shell.execute_reply":"2022-07-08T15:45:25.041388Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Most frequents cats\nCounter(cats).most_common(15)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:25.043550Z","iopub.execute_input":"2022-07-08T15:45:25.043781Z","iopub.status.idle":"2022-07-08T15:45:25.061067Z","shell.execute_reply.started":"2022-07-08T15:45:25.043752Z","shell.execute_reply":"2022-07-08T15:45:25.060103Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Group categories**","metadata":{}},{"cell_type":"code","source":"%%time\n\n# Cats to int\nDico_trans_cat = {cat:i for i, cat in enumerate(cats)}\n\n# Create df with no nan values\ntrain = df_train[(df_train['categories']!='') & (df_train['categories'].str.len()>=3)].reset_index(drop=True).copy()\n\n# Keep only letters and delete multi-space\n#train['categories'] = train['categories'].apply(lambda cat : ' '.join([re.sub('\\\\s+', ' ', re.sub(r'[^a-zA-Z]', ' ', x)).strip() for x in cat.split( )]))","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:34.465171Z","iopub.execute_input":"2022-07-08T15:45:34.465435Z","iopub.status.idle":"2022-07-08T15:45:34.550065Z","shell.execute_reply.started":"2022-07-08T15:45:34.465408Z","shell.execute_reply":"2022-07-08T15:45:34.549178Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Count categories\ncount_cat = train['categories'].value_counts().to_frame().reset_index()\ncount_cat = dict(zip(count_cat['index'], count_cat['categories']))\ncount_cat['banks']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:34.551802Z","iopub.execute_input":"2022-07-08T15:45:34.552584Z","iopub.status.idle":"2022-07-08T15:45:34.581676Z","shell.execute_reply.started":"2022-07-08T15:45:34.552536Z","shell.execute_reply":"2022-07-08T15:45:34.580633Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# POI to ID\nPOI_to_ID = train.copy()\nPOI_to_ID['index'] = POI_to_ID.index\nPOI_to_ID = POI_to_ID.groupby('point_of_interest')['index'].apply(list).to_dict()\nN = len(POI_to_ID)//10","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:34.583229Z","iopub.execute_input":"2022-07-08T15:45:34.583926Z","iopub.status.idle":"2022-07-08T15:45:35.777989Z","shell.execute_reply.started":"2022-07-08T15:45:34.583879Z","shell.execute_reply":"2022-07-08T15:45:35.776987Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Count how many times a category, or a pair of categories, appears and how many times they are matched**","metadata":{}},{"cell_type":"code","source":"%%time\nPaires = defaultdict(int)\ncount_cat = defaultdict(int)\n\ndef process_text(text):\n    res = ' '.join([re.sub(r'[^a-zA-Z]', ' ', x).strip() for x in text.split()])\n    return re.sub('\\\\s+', ' ', res).strip()\n\nfor i, (poi, Liste_idx) in enumerate(POI_to_ID.items()):\n    if i%N == 0 :\n        print(f\"{i}/{len(POI_to_ID)}...\")\n    if len(Liste_idx)==1 : continue\n    cat = train.loc[Liste_idx]['categories'].value_counts().to_frame().reset_index()\n    if len(cat) >= 3 :\n        cat = cat.merge(cat, how='cross')\n        cat = cat[cat['index_x'] <  cat['index_y']]\n        for cats1, cats2 in zip(cat['index_x'], cat['index_y']) :\n            Liste_cat = cats1.split(',') + cats2.split(',')\n            # Keep only letters and delete multi-space\n            Liste_cat = list(set([process_text(x) for x in Liste_cat]))\n            for i in range(len(Liste_cat)) :\n                for j in range(i+1, len(Liste_cat)) :\n                    cat1, cat2 = Liste_cat[i], Liste_cat[j]\n                    if cat1 != cat2 :\n                        count_cat[cat1] += 1\n                        count_cat[cat2] += 1\n                        Paires[tuple(sorted([cat1, cat2]))] += 1","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:35.780105Z","iopub.execute_input":"2022-07-08T15:45:35.781902Z","iopub.status.idle":"2022-07-08T15:45:37.409365Z","shell.execute_reply.started":"2022-07-08T15:45:35.781850Z","shell.execute_reply":"2022-07-08T15:45:37.408362Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"Counter(Paires).most_common(10)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:38.311241Z","iopub.execute_input":"2022-07-08T15:45:38.311516Z","iopub.status.idle":"2022-07-08T15:45:38.319290Z","shell.execute_reply.started":"2022-07-08T15:45:38.311486Z","shell.execute_reply":"2022-07-08T15:45:38.318642Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def str_to_list(s):\n    return [re.sub('\\\\s+', ' ', x.replace(\"'\", \"\")).strip() for x in s[1:-1].split(',')]\nstr_to_list(\"['airport lounges', 'airports']\")","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:38.325459Z","iopub.execute_input":"2022-07-08T15:45:38.325748Z","iopub.status.idle":"2022-07-08T15:45:38.339023Z","shell.execute_reply.started":"2022-07-08T15:45:38.325701Z","shell.execute_reply":"2022-07-08T15:45:38.338022Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Create a graph between categories, and then find connected components (graph theory) to group them**","metadata":{}},{"cell_type":"code","source":"%%time\n\nimport Levenshtein\n\ndef get_connected_components(graph):\n    seen = set()\n    components = []\n\n    for node in graph:\n        if node not in seen:\n            component = []\n            nodes = {node}\n\n            while nodes:\n                node = nodes.pop()\n                seen.add(node)\n                component.append(node)\n                nodes.update(graph[node].difference(seen))\n            components.append(component)\n\n    return components\n\n# ======================\n\n# Create a graph \ngraph = defaultdict(set)\nfor (cat1, cat2), count in Paires.items() :\n    max_, min_ = max(count_cat[cat1],count_cat[cat2]), min(count_cat[cat1],count_cat[cat2])\n    \n    # Create an edge in the graph if the cats are closely related\n    if 2 <= min_ <= 5 and count/min_ == 1 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif 10 > min_ >= 5 and count/min_ > 0.6 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 10 and count/min_ >= 0.3 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 100 and count/min_ >= 0.2 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 5 and count/min_ >= 0.15 and Levenshtein.jaro_winkler(cat1, cat2) > 0.7 and 'restaurant' not in cat1:\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 10 and count/min_ >= 0.1 and Levenshtein.jaro_winkler(cat1, cat2) > 0.92 and 'restaurant' not in cat1:\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n        \n# Get connected components\nConnexes = get_connected_components(graph)\n\n# Show the groups\nConnexes","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:38.346672Z","iopub.execute_input":"2022-07-08T15:45:38.347424Z","iopub.status.idle":"2022-07-08T15:45:38.361538Z","shell.execute_reply.started":"2022-07-08T15:45:38.347384Z","shell.execute_reply":"2022-07-08T15:45:38.360901Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n___\n# **Fill missing categories based on names**\n#### Search words that belongs to a category\n#### Example : name \"Paris international airport\" -> category \"Airport\".","metadata":{}},{"cell_type":"code","source":"%%time\ncats = df_train[['name', 'categories']].copy()\n\ndef process(cat, split=' '):\n    cat = [x for x in cat.split(split) if cat != '' and len(x)>=2]\n    # Keep only letters\n    cat = [re.sub(r'[^a-zA-Z]', ' ', x) for x in cat]\n    # Delete multi space\n    cat = [re.sub('\\\\s+', ' ', x).strip() for x in cat]\n    return cat\n\n# Drop nan categories\ncats['categories'] = cats['categories'].astype(str)\ncats = cats[cats['categories']!='']\n\n# Split in words\ncats.loc[:, 'name']       = cats['name'].apply(lambda cat : process(cat))\ncats.loc[:, 'categories'] = cats['categories'].apply(lambda cat : process(cat,split=','))\n\n# Stemmatisation (word roots) -> It's long\n#cats['name'] = cats['name'].apply(lambda cat : [ps.stem(x) for x in cat]) # Apply 2 times for foreign words\n\n# Show\ncats.head()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:44.779380Z","iopub.execute_input":"2022-07-08T15:45:44.780395Z","iopub.status.idle":"2022-07-08T15:45:45.825194Z","shell.execute_reply.started":"2022-07-08T15:45:44.780353Z","shell.execute_reply":"2022-07-08T15:45:45.824261Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\nCount_cat   = defaultdict(int)\nCount_words = defaultdict(int)\nCount_cat_of_words = defaultdict(lambda: defaultdict(int))\nN = len(cats)\n\n# Count how many times a word appear in a category\nfor i, (name_words, cat_words) in enumerate(zip(cats['name'], cats['categories'])) :\n    for cat in cat_words :\n        Count_cat[cat] += 1\n        for name in name_words :\n            Count_words[name] += 1\n            Count_cat_of_words[name][cat] += 1\n        \nprint(\"Times that category 'Airport' occurs :\", Count_cat['airports'])\nprint(f\"Times that the word 'airport' occurs in category 'airport': {Count_cat_of_words['airport']['airports']}/{Count_words['airport']}.\")","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:48.077486Z","iopub.execute_input":"2022-07-08T15:45:48.078058Z","iopub.status.idle":"2022-07-08T15:45:48.329402Z","shell.execute_reply.started":"2022-07-08T15:45:48.078017Z","shell.execute_reply":"2022-07-08T15:45:48.328486Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"Count_cat_of_words['aeroporto']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T15:45:50.335777Z","iopub.execute_input":"2022-07-08T15:45:50.336093Z","iopub.status.idle":"2022-07-08T15:45:50.342794Z","shell.execute_reply.started":"2022-07-08T15:45:50.336060Z","shell.execute_reply":"2022-07-08T15:45:50.341889Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Check the proportion\nKey_words_for_cat = defaultdict(set)\nfor word, count_cats in Count_cat_of_words.items() :\n    count_word = Count_words[word]\n    for cat, count_cat in count_cats.items() :\n        if 7 <= count_cat <= 10  and count_cat/count_word >= 0.75 and count_cat == max(count_cats.values()):\n            Key_words_for_cat[cat].add(word)\n        elif count_cat >= 10 and count_cat/count_word >= 0.45 and count_cat == max(count_cats.values()):\n            Key_words_for_cat[cat].add(word)\n        elif count_cat >= 10 and count_cat/count_word >= 0.3 and count_cat == max(count_cats.values()) and Levenshtein.jaro_winkler(word, cat)>=0.75:\n            Key_words_for_cat[cat].add(word)\n            \n# Save dict\nimport pickle\nwith open('dict_for_missing_cat.pkl', 'wb') as f:\n    pickle.dump(Key_words_for_cat, f)\n\n# Show\nKey_words_for_cat['airports']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T08:38:23.030099Z","iopub.execute_input":"2022-07-08T08:38:23.030435Z","iopub.status.idle":"2022-07-08T08:38:23.113085Z","shell.execute_reply.started":"2022-07-08T08:38:23.030389Z","shell.execute_reply":"2022-07-08T08:38:23.112174Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(\"Categories :\", len(Key_words_for_cat))\nprint(\"Words used :\", sum([len(L) for L in Key_words_for_cat.values()]))","metadata":{"execution":{"iopub.status.busy":"2022-07-08T08:38:23.114322Z","iopub.execute_input":"2022-07-08T08:38:23.114669Z","iopub.status.idle":"2022-07-08T08:38:23.121086Z","shell.execute_reply.started":"2022-07-08T08:38:23.114632Z","shell.execute_reply":"2022-07-08T08:38:23.120079Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Function to fill missing categories**","metadata":{}},{"cell_type":"code","source":"%%time\n\ndef find_cat(name):\n    global Key_words_for_cat\n    name_list = process(name)\n    for cat, wordlist in Key_words_for_cat.items() :\n        if any(name_word in name_list for name_word in wordlist) :\n            return cat\n    return ''\n    \nidx_missing_cat = df_train[df_train['categories'] == ''].index\nprint(f\"Missing cat before : {len(idx_missing_cat)}/{len(df_train)}.\")\n\ndf_train.loc[idx_missing_cat, 'categories'] = df_train.loc[idx_missing_cat, 'name'].apply(find_cat)\n\nprint(f\"Missing cat after : {len(df_train[df_train['categories'] == ''])}/{len(df_train)}.\")","metadata":{"execution":{"iopub.status.busy":"2022-07-08T08:38:23.122376Z","iopub.execute_input":"2022-07-08T08:38:23.122668Z","iopub.status.idle":"2022-07-08T08:38:23.694266Z","shell.execute_reply.started":"2022-07-08T08:38:23.122635Z","shell.execute_reply":"2022-07-08T08:38:23.693315Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Show categories that were filled\na = df_train.loc[idx_missing_cat].copy()\na[a['categories'] != ''].head()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T08:38:23.695619Z","iopub.execute_input":"2022-07-08T08:38:23.695903Z","iopub.status.idle":"2022-07-08T08:38:23.720471Z","shell.execute_reply.started":"2022-07-08T08:38:23.695871Z","shell.execute_reply":"2022-07-08T08:38:23.719648Z"},"trusted":true},"execution_count":null,"outputs":[]}]}