{"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":"The following notebook was very helpful.\n\nI will speed this up.\nObviously, speeding up the process by grouping rows that have the same result. I use the technique of compressing coordinates\n\n<https://www.kaggle.com/code/thedevastator/how-to-ensemble-clustering-algorithms>\n\nI have ensembled Best Score notebooks thanks.","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-07-04T15:41:53.439899Z","iopub.execute_input":"2022-07-04T15:41:53.440308Z","iopub.status.idle":"2022-07-04T15:41:53.45155Z","shell.execute_reply.started":"2022-07-04T15:41:53.440276Z","shell.execute_reply":"2022-07-04T15:41:53.450577Z"}}},{"cell_type":"code","source":"import numpy as np\nimport pandas as pd\nfrom tqdm import trange\nfrom sklearn.cluster import KMeans\nfrom sklearn.mixture import GaussianMixture\nimport matplotlib.pyplot as plt\nfrom collections import defaultdict\nfrom sklearn.metrics import adjusted_rand_score\nimport matplotlib.pyplot as plt","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:52.549212Z","iopub.execute_input":"2022-07-06T01:35:52.549624Z","iopub.status.idle":"2022-07-06T01:35:52.556223Z","shell.execute_reply.started":"2022-07-06T01:35:52.549582Z","shell.execute_reply":"2022-07-06T01:35:52.555214Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"clusters_1 = pd.read_csv(\"../input/tabular-playground-july-eda-gmm-pca/Submission16.csv\")[\"Predicted\"]  # .596\nclusters_2 = pd.read_csv(\"../input/bruteforce-clustering/submission.csv\")[\"Predicted\"]  # .596\nclusters_3 = pd.read_csv(\"../input/tps-jun22-unsupervised-clustering-with-keras/submission.csv\")[\"Predicted\"]  # .581\nclusters_4 = pd.read_csv(\"../input/tps-jul-2022-bayesiangaussianmixture/submission.csv\")[\"Predicted\"]  # .596\nclusters_5 = pd.read_csv(\"../input/tps-july-2022-clustering/submission.csv\")[\"Predicted\"]  # .578\n\nprint(set(clusters_1))\nprint(set(clusters_2))\nprint(set(clusters_3))\nprint(set(clusters_4))\nprint(set(clusters_5))\n\nclusters_list = [clusters_1, clusters_2, clusters_3, clusters_4, clusters_5]","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:52.589471Z","iopub.execute_input":"2022-07-06T01:35:52.590036Z","iopub.status.idle":"2022-07-06T01:35:52.778267Z","shell.execute_reply.started":"2022-07-06T01:35:52.590003Z","shell.execute_reply":"2022-07-06T01:35:52.777439Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"pd.DataFrame(clusters_5.to_list()).groupby([0]).size()","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:52.779813Z","iopub.execute_input":"2022-07-06T01:35:52.780564Z","iopub.status.idle":"2022-07-06T01:35:52.832595Z","shell.execute_reply.started":"2022-07-06T01:35:52.780532Z","shell.execute_reply":"2022-07-06T01:35:52.831669Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## compress coordinates for higher speed","metadata":{}},{"cell_type":"code","source":"# create tuple of cluster number\ncls_tup_list = []  # [(cluster_1, cluster_2), ..]\nfor cls_tup in zip(*clusters_list):\n    cls_tup_list.append(cls_tup)\n\n# compress coordinates the same clusters\nzipper = {x: i for i, x in enumerate(sorted(set(cls_tup_list)))}\nzipped_list = [zipper[x] for x in cls_tup_list]\nunzipper = defaultdict(set)  # unzipper[value] = set(idx)\nfor idx, cls_tup in enumerate(cls_tup_list):\n    zipped = zipper[cls_tup]\n    unzipper[zipped].add(idx)\n\n# compress clusters\ncomp_clusters_list = [[-1]*len(zipper) for _ in range(len(clusters_list))]\n\nfor clusters, comp_clusters in zip(clusters_list, comp_clusters_list):\n    for i, cluster_i in enumerate(clusters):\n            value = zipped_list[i]\n            comp_clusters[value] = cluster_i\n","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:52.834166Z","iopub.execute_input":"2022-07-06T01:35:52.834775Z","iopub.status.idle":"2022-07-06T01:35:53.189468Z","shell.execute_reply.started":"2022-07-06T01:35:52.834741Z","shell.execute_reply":"2022-07-06T01:35:53.188485Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# We were able to reduce the number of lines significantly!\nlen(comp_clusters_list[0])","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.191706Z","iopub.execute_input":"2022-07-06T01:35:53.192011Z","iopub.status.idle":"2022-07-06T01:35:53.199308Z","shell.execute_reply.started":"2022-07-06T01:35:53.191983Z","shell.execute_reply":"2022-07-06T01:35:53.198386Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from scipy.sparse import csr_matrix\n\ndef create_sparse_matrix(clusters):\n    n = len(clusters)\n    data = []\n    row = []\n    col = []\n    # O(n**2)\n    for i in trange(n):\n        for j in range(i+1, n):\n            if clusters[i] == clusters[j]:\n                data.append(1)\n                row.append(i)\n                col.append(j)\n    return csr_matrix((data, (row, col)), shape=(n, n))\n\nsparse_matrix_list = [create_sparse_matrix(comp_clusters) for comp_clusters in comp_clusters_list]","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-07-06T01:35:53.200562Z","iopub.execute_input":"2022-07-06T01:35:53.201009Z","iopub.status.idle":"2022-07-06T01:35:53.265176Z","shell.execute_reply.started":"2022-07-06T01:35:53.200976Z","shell.execute_reply":"2022-07-06T01:35:53.264044Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### We then simply take the mean/median of all sparse matrices, apply a threshold, and convert it back to cluster ids.\n\n![](https://i.ibb.co/84nnT31/1-s2-0-S153204641300021-X-gr1.jpg)\n[[source](https://www.sciencedirect.com/science/article/pii/S153204641300021X)]\n","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"code","source":"sparse_matrix_mean = (sparse_matrix_list[0]*1.05 + sparse_matrix_list[1]*1.031 + sparse_matrix_list[2]*1.03 + sparse_matrix_list[3]*0.04 + sparse_matrix_list[4]*1.02)/(1.05+1.031+1.03+0.04+1.02)","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-07-06T01:35:53.266480Z","iopub.execute_input":"2022-07-06T01:35:53.266800Z","iopub.status.idle":"2022-07-06T01:35:53.274812Z","shell.execute_reply.started":"2022-07-06T01:35:53.266771Z","shell.execute_reply":"2022-07-06T01:35:53.273738Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Now we apply the threshold","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"markdown","source":"The original method of using thresholds did not work because the clusters stuck together.\n\nUse DSU to control the upper limit of each cluster size to prevent clusters from sticking together.\n\nIf you are interested in this phenomenon, try setting SIZ_MAX to float('inf') and experiment with it!","metadata":{}},{"cell_type":"code","source":"# In this ensemble, a lower threshold will reduce the number of clusters, since we are counting by the connected component.\n# It seems desirable to set it a little higher.\n# -> controll SIZ_MAX\nthreshold = 0.5\nsparse_matrix_mean[sparse_matrix_mean < threshold] = 0\n# sparse_matrix_mean[sparse_matrix_mean >= threshold]","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-07-06T01:35:53.276480Z","iopub.execute_input":"2022-07-06T01:35:53.277182Z","iopub.status.idle":"2022-07-06T01:35:53.298469Z","shell.execute_reply.started":"2022-07-06T01:35:53.277138Z","shell.execute_reply":"2022-07-06T01:35:53.297347Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Now we reconstruct our clusters and return an integer column","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"code","source":"sparse_matrix_mean = sparse_matrix_mean.toarray()\nsparse_matrix_mean","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.300257Z","iopub.execute_input":"2022-07-06T01:35:53.300711Z","iopub.status.idle":"2022-07-06T01:35:53.308483Z","shell.execute_reply.started":"2022-07-06T01:35:53.300668Z","shell.execute_reply":"2022-07-06T01:35:53.307734Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"If sparse_matrix_mean[node1][node2]=1, then node1 and node2 belong to the same cluster\n\nDisjoint Set Union(DSU) is useful. O(α(N)).\nThe operation of grouping identical items together is intuitive.","metadata":{}},{"cell_type":"code","source":"node_end = len(comp_clusters_list[0])\nedge_list = []  # [(w, fr, to), ...]\nfor fr in range(node_end):\n    for to in range(fr, node_end):\n        w = sparse_matrix_mean[fr][to]\n        if w == 0:\n            continue\n        edge_list.append((w, fr, to))\nedge_list.sort(reverse=True)","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.309729Z","iopub.execute_input":"2022-07-06T01:35:53.310887Z","iopub.status.idle":"2022-07-06T01:35:53.340077Z","shell.execute_reply.started":"2022-07-06T01:35:53.310845Z","shell.execute_reply":"2022-07-06T01:35:53.338852Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"SIZ_MAX = 18000","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.343450Z","iopub.execute_input":"2022-07-06T01:35:53.343946Z","iopub.status.idle":"2022-07-06T01:35:53.351481Z","shell.execute_reply.started":"2022-07-06T01:35:53.343911Z","shell.execute_reply":"2022-07-06T01:35:53.350584Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Disjoint Set Union(DSU)\n\npar = [i for i in range(node_end)]\nsiz = [len(unzipper[i]) for i in range(node_end)]  # each node is zipped. set unzipped size\n\ndef find(x):\n    if par[x] == x:\n        return x\n    par[x] = find(par[x])\n    return par[x]\n\ndef union(x, y):\n    x = find(x)\n    y = find(y)\n    if x == y:\n        return\n\n    if siz[x] > siz[y]:\n        x, y = y, x\n\n    par[x] = y\n    siz[y] += siz[x]\n\ndef get_siz(x):\n    x = find(x)\n    return siz[x]\n\nfor w, fr, to in edge_list:\n    if (get_siz(fr)+get_siz(to)) > SIZ_MAX:\n        continue\n    union(fr, to)","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.353145Z","iopub.execute_input":"2022-07-06T01:35:53.353860Z","iopub.status.idle":"2022-07-06T01:35:53.367933Z","shell.execute_reply.started":"2022-07-06T01:35:53.353817Z","shell.execute_reply":"2022-07-06T01:35:53.367000Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# uncompression\nclusters_final = [0]*len(clusters_1)\nfor node in range(node_end):\n    cluster_id = find(node)\n    idx_list = unzipper[node]\n    for idx in idx_list:\n        clusters_final[idx] = cluster_id","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.369081Z","iopub.execute_input":"2022-07-06T01:35:53.369826Z","iopub.status.idle":"2022-07-06T01:35:53.396359Z","shell.execute_reply.started":"2022-07-06T01:35:53.369791Z","shell.execute_reply":"2022-07-06T01:35:53.395341Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"clusters_final[:10]","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.397748Z","iopub.execute_input":"2022-07-06T01:35:53.398253Z","iopub.status.idle":"2022-07-06T01:35:53.404661Z","shell.execute_reply.started":"2022-07-06T01:35:53.398220Z","shell.execute_reply":"2022-07-06T01:35:53.403446Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# compress cluster_final to replace it with an integer starting from 0.\nzipper = {x: i for i, x in enumerate(sorted(set(clusters_final)))}\nclusters_final = [zipper[x] for x in clusters_final]\nclusters_final[:10]","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.406165Z","iopub.execute_input":"2022-07-06T01:35:53.407393Z","iopub.status.idle":"2022-07-06T01:35:53.427221Z","shell.execute_reply.started":"2022-07-06T01:35:53.407331Z","shell.execute_reply":"2022-07-06T01:35:53.426041Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The ensemble itself seems to be working well, although cluster 0  become large.\n\nLet's visualize the results of the ensemble.","metadata":{}},{"cell_type":"code","source":"# cluster count\npd.DataFrame(clusters_final).groupby([0]).size()","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.428873Z","iopub.execute_input":"2022-07-06T01:35:53.429451Z","iopub.status.idle":"2022-07-06T01:35:53.485809Z","shell.execute_reply.started":"2022-07-06T01:35:53.429418Z","shell.execute_reply":"2022-07-06T01:35:53.484741Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# https://www.kaggle.com/code/ambrosm/tpsjul22-gaussian-mixture-cluster-analysis\ndef compare_clusterings(y1, y2, title=''):\n    \"\"\"Show the adjusted rand score and plot the two clusterings in color\"\"\"\n    ars = adjusted_rand_score(y1, y2)\n    n1 = y1.max() + 1\n    n2 = y2.max() + 1\n    argsort = np.argsort(y1*100 + y2) if n1 >= n2 else np.argsort(y2*100 + y1)\n    plt.figure(figsize=(16, 0.5))\n    for i in range(6, 11):\n        plt.scatter(np.arange(len(y1)), np.full_like(y1, i), c=y1[argsort], s=1, cmap='tab10')\n    for i in range(5):\n        plt.scatter(np.arange(len(y2)), np.full_like(y2, i), c=y2[argsort], s=1, cmap='tab10')\n    plt.gca().axis('off')\n    plt.title(f'{title}\\nAdjusted Rand score: {ars:.5f}')\n    plt.savefig(title + '.png', bbox_inches='tight')\n    plt.show()\n\nfor clusters in clusters_list:\n    compare_clusterings(np.array(clusters), np.array(clusters_final))","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:35:53.487491Z","iopub.execute_input":"2022-07-06T01:35:53.488497Z","iopub.status.idle":"2022-07-06T01:38:34.091081Z","shell.execute_reply.started":"2022-07-06T01:35:53.488452Z","shell.execute_reply":"2022-07-06T01:38:34.089911Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission = pd.read_csv(\"../input/tabular-playground-series-jul-2022/sample_submission.csv\")","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:38:34.095318Z","iopub.execute_input":"2022-07-06T01:38:34.095656Z","iopub.status.idle":"2022-07-06T01:38:34.119246Z","shell.execute_reply.started":"2022-07-06T01:38:34.095625Z","shell.execute_reply":"2022-07-06T01:38:34.118275Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission[\"Predicted\"] = clusters_final\nsubmission.to_csv(\"submission.csv\", index=False)","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:38:34.120850Z","iopub.execute_input":"2022-07-06T01:38:34.121240Z","iopub.status.idle":"2022-07-06T01:38:34.321037Z","shell.execute_reply.started":"2022-07-06T01:38:34.121199Z","shell.execute_reply":"2022-07-06T01:38:34.319866Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission","metadata":{"execution":{"iopub.status.busy":"2022-07-06T01:38:34.322613Z","iopub.execute_input":"2022-07-06T01:38:34.323255Z","iopub.status.idle":"2022-07-06T01:38:34.335722Z","shell.execute_reply.started":"2022-07-06T01:38:34.323201Z","shell.execute_reply":"2022-07-06T01:38:34.334600Z"},"trusted":true},"execution_count":null,"outputs":[]}]}