{"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","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:49:00.804643Z","iopub.execute_input":"2022-07-08T07:49:00.804989Z","iopub.status.idle":"2022-07-08T07:49:03.109943Z","shell.execute_reply.started":"2022-07-08T07:49:00.804904Z","shell.execute_reply":"2022-07-08T07:49:03.108865Z"},"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-08T07:49:03.112602Z","iopub.execute_input":"2022-07-08T07:49:03.113070Z","iopub.status.idle":"2022-07-08T07:49:03.126465Z","shell.execute_reply.started":"2022-07-08T07:49:03.113011Z","shell.execute_reply":"2022-07-08T07:49:03.125512Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Open Data**","metadata":{}},{"cell_type":"code","source":"train = pd.read_csv(\"../input/foursquare-location-matching/train.csv\")#.iloc[:50000]\nprint(train.shape)\ntrain.head(1)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:49:03.127783Z","iopub.execute_input":"2022-07-08T07:49:03.128484Z","iopub.status.idle":"2022-07-08T07:49:12.834440Z","shell.execute_reply.started":"2022-07-08T07:49:03.128431Z","shell.execute_reply":"2022-07-08T07:49:12.833465Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## **Translate japanese**","metadata":{}},{"cell_type":"code","source":"conda install pykakasi","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:49:12.837388Z","iopub.execute_input":"2022-07-08T07:49:12.837776Z","iopub.status.idle":"2022-07-08T07:51:14.848653Z","shell.execute_reply.started":"2022-07-08T07:49:12.837728Z","shell.execute_reply":"2022-07-08T07:51:14.847645Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"import pykakasi\n\nfrom tqdm import tqdm\ntqdm.pandas()\n\ndef convert_japanese_alphabet(df):\n    kakasi = pykakasi.kakasi()\n    kakasi.setMode('H', 'a')  # Convert Hiragana into alphabet\n    kakasi.setMode('K', 'a')  # Convert Katakana into alphabet\n    kakasi.setMode('J', 'a')  # Convert Kanji into alphabet\n    conversion = kakasi.getConverter()\n\n    def convert(row):\n        for column in [\"city\", \"state\"]:\n            try:\n                row[column] = conversion.do(row[column])\n            except:\n                pass\n        return row\n\n    df = df.progress_apply(convert, axis=1)\n    return df\n\nidx_JP = train[train[\"country\"] == \"JP\"].index\ntrain.loc[idx_JP] = convert_japanese_alphabet(train.loc[idx_JP])","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:51:14.850329Z","iopub.execute_input":"2022-07-08T07:51:14.851252Z","iopub.status.idle":"2022-07-08T07:51:36.512925Z","shell.execute_reply.started":"2022-07-08T07:51:14.851208Z","shell.execute_reply":"2022-07-08T07:51:36.511552Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## **Clean city and state**","metadata":{}},{"cell_type":"code","source":"# remove all spaces, symbols, lower case\ndef st(x, remove_space=True):\n    # turn to latin alphabet\n    x = unidecode(str(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\n\nfor col in ['city', 'state']:\n    train[col] = train[col].astype('str').apply(st)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:51:36.514738Z","iopub.execute_input":"2022-07-08T07:51:36.515123Z","iopub.status.idle":"2022-07-08T07:51:58.024395Z","shell.execute_reply.started":"2022-07-08T07:51:36.515075Z","shell.execute_reply":"2022-07-08T07:51:58.023342Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def 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\ntrain['city'] = train['city'].apply(st2) # remove digits from cities","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:51:58.025924Z","iopub.execute_input":"2022-07-08T07:51:58.026256Z","iopub.status.idle":"2022-07-08T07:52:01.112169Z","shell.execute_reply.started":"2022-07-08T07:51:58.026211Z","shell.execute_reply":"2022-07-08T07:52:01.111417Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# clean city\ncity_di = {'alkhubar': 'alkhobar', 'khobar': 'alkhobar', 'muratpasa': 'antalya', 'antwerpen': 'antwerp', 'kuta': 'badung', 'bandungregency': 'bandung', 'bengaluru': 'bangalore', 'bkk': 'bangkok',\n'krungethphmhaankhr': 'bangkok', 'pattaya': 'banglamung', 'sathon': 'bangrak', 'silom': 'bangrak', 'beijingshi': 'beijing', 'beograd': 'belgrade', 'ratchathewi': 'bangkok', 'brussels': 'brussel',\n'bruxelles': 'brussel', 'bucuresti': 'bucharest', 'capitalfederal': 'buenosaires', 'busangwangyeogsi': 'busan', 'cagayandeorocity': 'cagayandeoro', 'cebucity': 'cebu', 'mueangchiangmai': 'chiangmai', 'qianxieshi': 'chiba', 'qiandaitianqu': 'chiyoda', 'zhongyangqu': 'chuo', 'sumedang': 'cikeruh', 'mexico': 'ciudaddemexico', 'mexicocity': 'ciudaddemexico', 'mexicodf': 'ciudaddemexico', 'koln': 'cologne', 'kobenhavn': 'copenhagen', 'osaka': 'dabanshibeiqu', 'jakarta': 'dkijakarta', 'dnipropetrovsk': 'dnepropetrovsk', 'frankfurtammain': 'frankfurt', 'fukuoka': 'fugangshi', 'minato': 'gangqu', 'moscow': 'gorodmoskva', 'moskva': 'gorodmoskva', 'sanktpeterburg': 'gorodsanktpeterburg', 'spb': 'gorodsanktpeterburg', 'hoankiem': 'hanoi', 'yokohama': 'hengbangshi', 'hochiminhcity': 'hochiminh', 'shouye_': 'home_', 'krungethph': 'huaikhwang', 'konak': 'izmir', 'kocaeli': 'izmit', 'jakartacapitalregion': 'dkijakarta', 'southjakarta': 'jakartaselatan', 'shanghai': 'jingan', 'shanghaishi': 'jingan', 'kyoto': 'jingdushi', 'melikgazi': 'kayseri', 'kharkov': 'kharkiv', 'kiyiv': 'kiev', 'kyiv': 'kiev', 'paradise': 'lasvegas', 'lisbon': 'lisboa', 'makaticity': 'makati', 'mandaluyongcity': 'mandaluyong', 'milano': 'milan', 'mingguwushizhongqu': 'mingguwushi', 'nagoyashi': 'mingguwushi', 'munich': 'munchen', 'muntinlupacity': 'muntinlupa', 'pasaycity': 'pasay', 'pasigcity': 'pasig', 'samsennai': 'phayathai', 'praha': 'prague', 'santiagodechile': 'santiago', 'zhahuangshi': 'sapporo', 'seoulteugbyeolsi': 'seoul', 'shenhushizhongyangqu': 'shenhushi', 'shibuya': 'shibuiguqu', 'xinsuqu': 'shinjuku', 'sofiia': 'sofia', 'surakarta': 'solo', 'suwonsi': 'suweonsi', 'taguigcity': 'taguig', 'taipei': 'taibeishi', 'watthana': 'vadhana', 'wien': 'vienna', 'warszawa': 'warsaw', 'washingtondc': 'washington',\n'surgutkhantymansiiskiiavtonomnyiokrugiugraaorossiiskaiafederatsiia':'surgut', 'newyorkcity':'newyork', 'newyorknyus':'newyork', 'ny':'newyork', 'nyc':'newyork',\n'londongreaterlondon':'london', 'greaterlondon':'london', 'losangelescaus':'losangeles', 'dabanshibeiqu':'dabanshi', 'seoulsi':'seoul', 'kuwaitcity':'kuwait', 'bangkoknoi':'bangkok'}\nfor key in city_di.keys():\n    train['city'].loc[train['city'] == key] = city_di[key]\n# second pass\ncity_di2 = {'jakartaselatan':'dkijakarta','jakartapusat':'dkijakarta','jakartabarat':'dkijakarta','jakartautara':'dkijakarta','jakartatimur':'dkijakarta','saintpetersburg':'sanktpeterburg'}\nfor key in city_di2.keys():\n    train['city'].loc[train['city'] == key] = city_di2[key]\n    \n# clean state\nstate_di = {'calif':'ca', 'jakartacapitalregion':'jakarta', 'moscow':'moskva', 'seoulteugbyeolsi':'seoul'}\nfor key in state_di.keys():\n    train['state'].loc[train['state'] == key] = state_di[key]","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:52:01.113436Z","iopub.execute_input":"2022-07-08T07:52:01.113819Z","iopub.status.idle":"2022-07-08T07:52:20.494581Z","shell.execute_reply.started":"2022-07-08T07:52:01.113787Z","shell.execute_reply":"2022-07-08T07:52:20.493587Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"train[['city', 'state', 'country']].head()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:52:20.495927Z","iopub.execute_input":"2022-07-08T07:52:20.496254Z","iopub.status.idle":"2022-07-08T07:52:20.569130Z","shell.execute_reply.started":"2022-07-08T07:52:20.496219Z","shell.execute_reply":"2022-07-08T07:52:20.568099Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Group cities**","metadata":{}},{"cell_type":"markdown","source":"### **Find close neighbours**","metadata":{}},{"cell_type":"code","source":"from scipy import spatial\n\n# Function to seek for the nearest neighbours\ndef Compute_Mdist_Mindex(test, nb_max_candidates=1000, thr_distance=None) :\n    \n    Z = tuple(zip(test[:, 2], test[:, 3])) # latitude, longitude\n\n    tree = spatial.KDTree(Z)\n    M_dist, M_index = (tree.query(Z, min(nb_max_candidates, len(test))))\n    \n    if thr_distance is None : \n        return M_dist, M_index\n\n    # Threshold filter\n    Nb_matches_potentiels = []\n    for i in range(len(M_index)) :\n        n = len([d for d in M_dist[i] if d <= thr_distance])\n        Nb_matches_potentiels.append(n)\n    M_dist  = [m[:Nb_matches_potentiels[i]] for i, m in enumerate(M_dist)]\n    M_index = [m[:Nb_matches_potentiels[i]] for i, m in enumerate(M_index)]\n    \n    return M_dist, M_index","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:52:20.571781Z","iopub.execute_input":"2022-07-08T07:52:20.572298Z","iopub.status.idle":"2022-07-08T07:52:20.582025Z","shell.execute_reply.started":"2022-07-08T07:52:20.572258Z","shell.execute_reply":"2022-07-08T07:52:20.580641Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\n# Create df with no nan values\ndf = train[~train['city'].isin(['', 'nan'])].reset_index(drop=True).copy()\n\n# POI to ID\nPOI_to_ID = df.copy()\nPOI_to_ID['index'] = POI_to_ID.index\nPOI_to_ID = POI_to_ID.groupby('point_of_interest')['index'].apply(list).to_dict()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:52:20.583408Z","iopub.execute_input":"2022-07-08T07:52:20.583849Z","iopub.status.idle":"2022-07-08T07:52:38.131256Z","shell.execute_reply.started":"2022-07-08T07:52:20.583800Z","shell.execute_reply":"2022-07-08T07:52:38.130341Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\n# To numpy for faster computing\ndf_np = df.to_numpy()\n\n# Find close neighbours\nM_dist, M_index = Compute_Mdist_Mindex(df_np,\n                                       nb_max_candidates=150,\n                                       thr_distance=0.005)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:52:38.132511Z","iopub.execute_input":"2022-07-08T07:52:38.133048Z","iopub.status.idle":"2022-07-08T07:53:47.995812Z","shell.execute_reply.started":"2022-07-08T07:52:38.133012Z","shell.execute_reply":"2022-07-08T07:53:47.994895Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Count how many times a city, or a pair of cities, appears and how many times they are matched**","metadata":{}},{"cell_type":"code","source":"%%time\n\nPaires = defaultdict(int)\ncount  = defaultdict(int)\nN = len(M_index)//10\n\nfor i, Liste_idx in enumerate(M_index) :\n    \n    if i%N == 0 :\n        print(f\"{i}/{len(M_index)}...\")\n        \n    city1 = df_np[i, 5]\n        \n    for j in Liste_idx :\n        if i<j : # Unicity\n            city2 = df_np[j, 5] # city\n            count[city1] += 1\n            count[city2] += 1\n            Paires[tuple(sorted([city1, city2]))] += 1","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:53:47.997663Z","iopub.execute_input":"2022-07-08T07:53:47.997939Z","iopub.status.idle":"2022-07-08T07:54:31.169026Z","shell.execute_reply.started":"2022-07-08T07:53:47.997904Z","shell.execute_reply":"2022-07-08T07:54:31.168148Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Create a graph between cities, 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\ndef get_seuil(x) : # linear function to give a threshold\n    return round(0.78 - 0.00147*x, 3)\n\n# ======================\n\n# Create a graph (if the cities are closely related)\ngraph = defaultdict(set)\nfor (cat1, cat2), count_pair in Paires.items() :\n    \n    if cat1 == cat2 : continue\n    \n    max_, min_ = max(count[cat1],count[cat2]), min(count[cat1],count[cat2])\n\n    if 4 <= min_ <= 10 and count_pair/min_ >= 0.8 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 150 and count_pair/min_ >= 0.5 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif 10 <= min_ <= 150 and count_pair/min_ >= get_seuil(min_) :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n\n# Get the connected components\nConnexes = get_connected_components(graph)\n\n# Show\nConnexes[0]","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:55:03.988433Z","iopub.execute_input":"2022-07-08T07:55:03.988729Z","iopub.status.idle":"2022-07-08T07:55:04.288027Z","shell.execute_reply.started":"2022-07-08T07:55:03.988700Z","shell.execute_reply":"2022-07-08T07:55:04.287024Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Keep a representant (most frequent element)**","metadata":{}},{"cell_type":"code","source":"# Keep the most frequent of each group as representant\nBest = {}\nfor group in Connexes :\n    best, best_count = 0, 0\n    for c in group :\n        if count[c] > best_count :\n            best, best_count = c, count[c]\n    Best[best] = group\n    \n# Show\nBest['pasay']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:55:09.124843Z","iopub.execute_input":"2022-07-08T07:55:09.125391Z","iopub.status.idle":"2022-07-08T07:55:09.143539Z","shell.execute_reply.started":"2022-07-08T07:55:09.125324Z","shell.execute_reply":"2022-07-08T07:55:09.142463Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Just show are closely the cities are related to the city 'Pasay'\nfor c in Best['pasay'] :\n    print(c, Paires[tuple(sorted(['pasay', c]))], count[c])","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:55:16.359279Z","iopub.execute_input":"2022-07-08T07:55:16.359605Z","iopub.status.idle":"2022-07-08T07:55:16.369137Z","shell.execute_reply.started":"2022-07-08T07:55:16.359573Z","shell.execute_reply":"2022-07-08T07:55:16.366662Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Save a dictionnary\ndict_for_city_groups = {}\nfor representant, Liste in Best.items() :\n    for city in Liste :\n        dict_for_city_groups[city] = representant\n            \n# Save dict\nimport pickle\nwith open('dict_for_city_groups.pkl', 'wb') as f:\n    pickle.dump(dict_for_city_groups, f)\n        \n# Show\ndict_for_city_groups['pasaycitynationalcapitalregion']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:57:35.482736Z","iopub.execute_input":"2022-07-08T07:57:35.483060Z","iopub.status.idle":"2022-07-08T07:57:35.504119Z","shell.execute_reply.started":"2022-07-08T07:57:35.483030Z","shell.execute_reply":"2022-07-08T07:57:35.503428Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"___\n# **Group state (same principle)**","metadata":{}},{"cell_type":"markdown","source":"### **Find close neighbours**","metadata":{}},{"cell_type":"code","source":"%%time\n\n# Create df with no nan values\ndf = train[~train['state'].isin(['', 'nan'])].reset_index(drop=True).copy()\n\n# POI to ID\nPOI_to_ID = df.copy()\nPOI_to_ID['index'] = POI_to_ID.index\nPOI_to_ID = POI_to_ID.groupby('point_of_interest')['index'].apply(list).to_dict()","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:57:53.622665Z","iopub.execute_input":"2022-07-08T07:57:53.622976Z","iopub.status.idle":"2022-07-08T07:58:08.882435Z","shell.execute_reply.started":"2022-07-08T07:57:53.622946Z","shell.execute_reply":"2022-07-08T07:58:08.881363Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\ndf_np = df.to_numpy()\n\n# Find close neighbours\nM_dist, M_index = Compute_Mdist_Mindex(df_np,\n                                       nb_max_candidates=150,\n                                       thr_distance=0.005)","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:58:08.884484Z","iopub.execute_input":"2022-07-08T07:58:08.884935Z","iopub.status.idle":"2022-07-08T07:59:07.922585Z","shell.execute_reply.started":"2022-07-08T07:58:08.884890Z","shell.execute_reply":"2022-07-08T07:59:07.921651Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Count how many times a state, or a pair of state, appears and how many times they are matched**","metadata":{}},{"cell_type":"code","source":"%%time\nPaires = defaultdict(int)\ncount  = defaultdict(int)\nN = len(M_index)//10\n\nfor i, Liste_idx in enumerate(M_index) :\n    \n    if i%N == 0 :\n        print(f\"{i}/{len(M_index)}...\")\n        \n    state1 = df_np[i, 6]\n        \n    for j in Liste_idx :\n        if i<j : # Unicity\n            state2 = df_np[j, 6]\n            count[state1] += 1\n            count[state2] += 1\n            Paires[tuple(sorted([state1, state2]))] += 1","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:59:07.924520Z","iopub.execute_input":"2022-07-08T07:59:07.924826Z","iopub.status.idle":"2022-07-08T07:59:41.007805Z","shell.execute_reply.started":"2022-07-08T07:59:07.924775Z","shell.execute_reply":"2022-07-08T07:59:41.006973Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Create a graph between states, and then find connected components (graph theory) to group them**","metadata":{}},{"cell_type":"code","source":"%%time\n\ngraph = defaultdict(set)\nfor (cat1, cat2), count_pair in Paires.items() :\n    \n    if cat1 == cat2 : continue\n    \n    max_, min_ = max(count[cat1],count[cat2]), min(count[cat1],count[cat2])\n\n    if 4 <= min_ <= 10 and count_pair/min_ >= 0.8 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif min_ >= 150 and count_pair/min_ >= 0.55 :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n    elif 10 <= min_ <= 150 and count_pair/min_ >= get_seuil(min_) :\n        graph[cat1].add(cat2)\n        graph[cat2].add(cat1)\n\n# Connected components\nConnexes = get_connected_components(graph)\n\n# Show\nConnexes[:2]","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:59:41.009964Z","iopub.execute_input":"2022-07-08T07:59:41.010199Z","iopub.status.idle":"2022-07-08T07:59:41.137471Z","shell.execute_reply.started":"2022-07-08T07:59:41.010172Z","shell.execute_reply":"2022-07-08T07:59:41.136581Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### **Keep a representant (most frequent element)**","metadata":{}},{"cell_type":"code","source":"# Keep the most frequent of each group as representant\nBest = {}\nfor group in Connexes :\n    best, best_count = 0, 0\n    for c in group :\n        if count[c] > best_count :\n            best, best_count = c, count[c]\n    Best[best] = group","metadata":{"execution":{"iopub.status.busy":"2022-07-08T07:59:41.138847Z","iopub.execute_input":"2022-07-08T07:59:41.139297Z","iopub.status.idle":"2022-07-08T07:59:41.147231Z","shell.execute_reply.started":"2022-07-08T07:59:41.139264Z","shell.execute_reply":"2022-07-08T07:59:41.146599Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Save a dictionnary\ndict_for_state_groups = {}\nfor representant, Liste in Best.items() :\n    for state in Liste :\n        dict_for_state_groups[state] = representant\n            \n# Save dict\nimport pickle\nwith open('dict_for_state_groups.pkl', 'wb') as f:\n    pickle.dump(dict_for_state_groups, f)\n    \n# Show\ndict_for_state_groups['metromanilaphilippines']","metadata":{"execution":{"iopub.status.busy":"2022-07-08T08:01:56.373469Z","iopub.execute_input":"2022-07-08T08:01:56.373839Z","iopub.status.idle":"2022-07-08T08:01:56.390641Z","shell.execute_reply.started":"2022-07-08T08:01:56.373806Z","shell.execute_reply":"2022-07-08T08:01:56.389663Z"},"trusted":true},"execution_count":null,"outputs":[]}]}