1. Dataset Labeling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distance Metric Recommendation for $k$-Means Clustering: A Meta-Learning Approach\n",
    "\n",
    "**Mark Edward M. Gonzales<sup>1</sup>, Lorene C. Uy<sup>1</sup>, Jacob Adrianne L. Sy<sup>1</sup>, Macario O. Cordel, II<sup>2</sup>**\n",
    "\n",
    "<sup>1</sup> Department of Software Technology, College of Computer Studies, De La Salle University <br>\n",
    "<sup>2</sup> Department of Computer Technology, College of Computer Studies, De La Salle University \n",
    "\n",
    "{mark_gonzales, lorene_c_uy, jacob_adrianne_l_sy, macario.cordel}@dlsu.edu.ph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PART I: Preliminaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following libraries and modules — most of which are automatically bundled with an Anaconda installation — were used in this notebook:\n",
    "\n",
    "Library/Module | Description | License\n",
    ":-- | :-- | :--\n",
    "<a href = \"https://docs.python.org/3/library/os.html\">`os`</a> | Provides miscellaneous operating system interfaces | Python Software Foundation License\n",
    "<a href = \"https://docs.python.org/3/library/shutil.html\">`shutil`</a> | Provides high-level operations on files and collections of files | Python Software Foundation License\n",
    "<a href = \"https://docs.python.org/3/library/json.html\">`json`</a> | Provides methods for encoding and decoding JavaScript Object Notation files | Python Software Foundation License\n",
    "<a href = \"https://docs.python.org/3/library/math.html\">`math`</a> | Provides access to the mathematical functions defined by the C standard | Python Software Foundation License\n",
    "<a href = \"https://docs.python.org/3/library/warnings.html\">`warnings`</a> | Provides control over warning messages | Python Software Foundation License\n",
    "<a href = \"https://pandas.pydata.org/\">`pandas`</a> | Provides functions for data analysis and manipulation\t | BSD 3-Clause \"New\" or \"Revised\" License\n",
    "<a href = \"https://numpy.org/\">`numpy`</a> | Provides a multidimensional array object, various derived objects, and an assortment of routines for fast operations on arrays | BSD 3-Clause \"New\" or \"Revised\" License\n",
    "<a href = \"https://www.scipy.org/\">`scipy`</a> | Provides efficient numerical routines, such as those for numerical integration, interpolation, optimization, linear algebra, and statistics | BSD 3-Clause \"New\" or \"Revised\" License\n",
    "<a href = \"https://pyclustering.github.io/docs/0.8.2/html/index.html\">`pyclustering`</a> | Collection of cluster analysis, graph coloring, travelling salesman problem algorithms, oscillatory and neural network models, containers, tools for visualization and result analysis | BSD 3-Clause \"New\" or \"Revised\" License\n",
    "<a href = \"https://scikit-learn.org/stable/\">`scikit-learn`</a> | Python module for machine learning and predictive data analysis | BSD 3-Clause \"New\" or \"Revised\" License\n",
    "\n",
    "*The descriptions were lifted from their respective websites.*\n",
    "<br><br>\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "    <b>Note:</b>  The <a href = \"https://pyclustering.github.io/docs/0.8.2/html/index.html\"><code>pyclustering</code></a> library is not included in Anaconda by default. The fastest way to install this library is to use pip and run the following command on the terminal: <br>\n",
    "\n",
    "**`pip3 install pyclustering`**\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from os import listdir\n",
    "\n",
    "import json\n",
    "import re\n",
    "import warnings\n",
    "import time\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "from pyclustering.cluster.kmeans import kmeans\n",
    "from pyclustering.cluster.center_initializer import random_center_initializer\n",
    "from pyclustering.utils.metric import distance_metric\n",
    "from pyclustering.utils.metric import type_metric\n",
    "\n",
    "from scipy.spatial import distance\n",
    "from sklearn import metrics\n",
    "from sklearn.preprocessing import MinMaxScaler\n",
    "from sklearn.impute import SimpleImputer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "If some of the methods in this notebook are not running (especially those related to <a href=\"https://scikit-learn.org/stable/modules/classes.html#module-sklearn.metrics\"><code>sklearn.metrics</code></a>, it may be necessary to update the installed versions of these libraries. A quick way to do so is by running the following command on the Anaconda prompt: <br>\n",
    "\n",
    "**`conda install anaconda`**\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PART II: Initial Clustering of the Datasets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This section details the initial clustering of the datasets using the nine (9) distance metrics considered in [[1]](https://dl.acm.org/doi/10.1145/3418228)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A. Distance Metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Let $o_i$ and $o_j$ be two observations (data points) in the dataset $d = \\{a_{n \\times m}\\}$, where $n$ is the number of observations and $m$ is the number of features. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Manhattan Distance\n",
    "\n",
    "$$\\text{dist}_{\\text{manhattan}}(o_i, o_j) = \\sum_{k = 1}^{m} |a_{ik} - a_{jk}|$$\n",
    "\n",
    "`pyclustering` provides a built-in [implementation](https://pyclustering.github.io/docs/0.9.0/html/da/d3a/classpyclustering_1_1utils_1_1metric_1_1type__metric.html#a49a236683bbe19f1771fb16b9f68e144) of the Manhattan distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Euclidean Distance\n",
    "\n",
    "$$\\text{dist}_{\\text{euclidean}}(o_i, o_j) = \\sqrt{\\sum_{k = 1}^{m} \\left(a_{ik} - a_{jk}\\right)^2}$$\n",
    "\n",
    "`pyclustering` provides a built-in [implementation](https://pyclustering.github.io/docs/0.9.0/html/da/d3a/classpyclustering_1_1utils_1_1metric_1_1type__metric.html#ada41bdfbf917a3463b48f75c9a6ccae1) of the Euclidean distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Chebyshev Distance\n",
    "\n",
    "$$\\text{dist}_{\\text{chebyshev}}(o_i, o_j) = \\max_{0<k<m+1}\\{|a_{ik} - a_{jk}|\\}$$\n",
    "\n",
    "`pyclustering` provides a built-in [implementation](https://pyclustering.github.io/docs/0.9.0/html/da/d3a/classpyclustering_1_1utils_1_1metric_1_1type__metric.html#ad4419ac00c1f1c484f86d0af82bf0164) of the Chebyshev distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Standardized Euclidean Distance\n",
    "\n",
    "$$\\text{dist}_{\\text{standardized euclidean}}(o_i, o_j) = \\sqrt{\\sum_{k = 1}^{m} \\frac{\\left(a_{ik} - a_{jk}\\right)^2}{s_k^2}}$$\n",
    "\n",
    "where $s_k^2$ is the variance of $a_{\\cdot k}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method returns the standardized Euclidean distance between two observations.\n",
    "\n",
    "**Parameters**:\n",
    "- `u`: First observation \n",
    "- `v`: Second observation\n",
    "\n",
    "**Return Value**:\n",
    "- Standardized Euclidean distance between two observations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def standardized_euclidean(u, v):\n",
    "    return distance.cdist([u], [v], 'seuclidean')[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sanity Check**: The standardized Euclidean distance between these two vectors should be 2.4495."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "standardized_euclidean([0.1, 0.7, 0.3], [0.4, 0.6, 0.9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Canberra Distance\n",
    "$$\\text{dist}_{\\text{canberra}}(o_i, o_j) = \\sum_{k = 1}^{m} \\frac{|a_{ik} - a_{jk}|}{|a_{ik}| + |a_{jk}|}$$\n",
    "\n",
    "`pyclustering` provides a built-in [implementation](https://pyclustering.github.io/docs/0.9.0/html/da/d3a/classpyclustering_1_1utils_1_1metric_1_1type__metric.html#a98e4af29af65e57b6dfbabcbd94c3be7) of the Canberra distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Mahalanobis Distance\n",
    "$$\\text{dist}_{\\text{mahalanobis}}(o_i, o_j) = \\sqrt{(o_i - o_j)^TM^{-1}(o_i - o_j)}$$\n",
    "\n",
    "where $M$ is the covariance of $d$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method returns the Mahalanobis distance between two observations. Note that `iv` is the inverse covariance matrix of the dataset; it is a global variable that will be set in the method `label_dataset`.\n",
    "\n",
    "**Parameters**:\n",
    "- `u`: First observation \n",
    "- `v`: Second observation\n",
    "\n",
    "**Return Value**:\n",
    "- Mahalanobis distance between two observations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mahalanobis(u, v):\n",
    "    return distance.mahalanobis(u, v, iv)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7. Cosine Distance\n",
    "$$\\text{dist}_{\\text{cosine}}(o_i, o_j) = 1 - \\frac{o_i \\cdot o_j}{||o_i|| \\cdot ||o_j||}$$\n",
    "\n",
    "`scipy` provides a built-in [implementation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cosine.html#scipy.spatial.distance.cosine) of the cosine distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8. Adjusted Cosine Distance\n",
    "$$\\text{dist}_{\\text{adjusted cosine}}(o_i, o_j) = 1 - \\frac{\\sum_{k=1}^m \\left(a_{jk} - \\text{mean}(a_{\\cdot k})\\right)\\left(a_{jk} - \\text{mean}(a_{\\cdot k})\\right)}{\\sqrt{\\sum_{k=1}^m \\left(a_{ik} - \\text{mean}(a_{\\cdot k})\\right)^2} \\sqrt{\\sum_{k=1}^m \\left(a_{jk} - \\text{mean}(a_{\\cdot k})\\right)^2}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def adjusted_cosine(u, v):\n",
    "    return distance.cosine(u - np.mean(u), v - np.mean(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sanity Check**: The standardized Euclidean distance between these two vectors should be 0.7832."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "adjusted_cosine([0.1, 0.7, 0.3], [0.4, 0.6, 0.9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. Pearson Correlation Distance\n",
    "$$\\text{dist}_{\\text{pearson}}(o_i, o_j) = 1 - \\frac{\\sum_{k=1}^m \\left(a_{jk} - \\text{mean}(a_{i \\cdot})\\right)\\left(a_{jk} - \\text{mean}(a_{j \\cdot})\\right)}{\\sqrt{\\sum_{k=1}^m \\left(a_{ik} - \\text{mean}(a_{i \\cdot})\\right)^2} \\sqrt{\\sum_{k=1}^m \\left(a_{jk} - \\text{mean}(a_{j \\cdot})\\right)^2}}$$\n",
    "\n",
    "`scipy` provides a built-in [implementation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.correlation.html) of the cosine distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mapping the Distance Metrics to Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dictionary below maps the distance metrics to the method implementing them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "metric_functions =  {'manhattan': distance_metric(type_metric.MANHATTAN),\n",
    "                     'euclidean': distance_metric(type_metric.EUCLIDEAN),\n",
    "                     'chebyshev': distance_metric(type_metric.CHEBYSHEV),\n",
    "                     'standardized_euclidean': distance_metric(type_metric.USER_DEFINED, func=standardized_euclidean),\n",
    "                     'canberra': distance_metric(type_metric.CANBERRA),\n",
    "                     'mahalanobis': distance_metric(type_metric.USER_DEFINED, func=mahalanobis),\n",
    "                     'cosine': distance_metric(type_metric.USER_DEFINED, func=distance.cosine),\n",
    "                     'adjusted-cosine': distance_metric(type_metric.USER_DEFINED, func=adjusted_cosine), \n",
    "                     'pearson': distance_metric(type_metric.USER_DEFINED, func=distance.correlation)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method returns the function corresponding to the specified distance metric.\n",
    "\n",
    "**Parameter**:\n",
    "- `metric`: Distance metric\n",
    "\n",
    "**Return**:\n",
    "- Function corresponding to the specified distance metric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_metric_function(metric):\n",
    "    return metric_functions[metric]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## B. Helper Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This subsection focuses on the helper functions for returning the cluster assignment and the ground-truth labels of the observations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Cluster assignment of the observations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method returns a list representing the cluster assignment of the observations. Formally, it returns a list $A$ where $A[i]$ is the cluster to which the $i^{\\text{th}}$ observation belongs.\n",
    "\n",
    "**Parameters**:\n",
    "- `num_observations`: Number of observations in the dataset\n",
    "- `clusters`: Two-dimensional list where `clusters[i]` contains the indices of the observations that belong to the $i^{\\text{th}}$ cluster\n",
    "\n",
    "**Return Value**:\n",
    "- A one-dimensional list $A$ where $A[i]$ is the cluster to which the $i^{\\text{th}}$ observation belongs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_cluster_mapping(num_observations, clusters):\n",
    "    cluster_mapping = [0 for _ in range(num_observations)]\n",
    "    \n",
    "    cluster_idx = 0\n",
    "    for cluster in clusters:\n",
    "        for x in cluster:\n",
    "            cluster_mapping[x] = cluster_idx\n",
    "            \n",
    "        cluster_idx += 1\n",
    "        \n",
    "    return cluster_mapping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Ground-truth labels of the observations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Returns a list representing the ground-truth labels of the observations. Formally, it returns a list $A$ where $A[i]$ is the ground-truth label of the $i^{\\text{th}}$ observation.\n",
    "\n",
    "**Precondition**:\n",
    "- The labels are found at the last column of the dataset.\n",
    "\n",
    "**Parameter**:\n",
    "- `data`: Dataset\n",
    "\n",
    "**Return Value**:\n",
    "- A one-dimensional list $A$ where $A[i]$ is the ground-truth label of the $i^{\\text{th}}$ observation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_ground_truth(data):\n",
    "    return data[data.columns[-1]].astype('category').cat.codes.to_numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. $k$-means clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Returns the cluster assignment of the observations after performing $k$-means clustering. Formally, it returns a two-dimensional list $A$ where $A[i]$ contains the indices of the observations that belong to the $i^{\\text{th}}$ cluster. \n",
    "\n",
    "**Parameters**:\n",
    "- `X`: Observations\n",
    "- `k`: Number of clusters\n",
    "- `distance_metric`: Distance measure to be used in clustering\n",
    "\n",
    "**Return Value**:\n",
    "- A two-dimensional list $A$ where $A[i]$ contains the indices of the observations that belong to the $i^{\\text{th}}$ cluster"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_means_cluster(X, k, distance_metric):\n",
    "    initial_centers = random_center_initializer(X, k, random_state=96024).initialize()\n",
    "    \n",
    "    k_means = kmeans(X, initial_centers, metric=distance_metric)    \n",
    "    k_means.process()\n",
    "    clusters = k_means.get_clusters()\n",
    "    \n",
    "    return clusters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## C. Dataset Labeling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before performing $k$-means, a minimal suite of preprocessing techniques is performed:\n",
    "- **Data imputation** (using the mean of the values for numerical features)\n",
    "- **Data normalization** (following [2, 3]). Let $x$ be the value to be normalized and $x_{\\text{max}}$ and $x_{\\text{min}}$ be the maximum and minimum values:\n",
    "\n",
    "   $$x_\\text{normalized} = \\frac{x - x_\\text{min}}{x_\\text{max} - x_\\text{min}},$$\n",
    "\n",
    "   thus $x_\\text{normalized}$ will always fall in the interval $[0, 1]$.\n",
    "   \n",
    "These preprocessing techniques are performed via the [simple imputation transformer](https://scikit-learn.org/stable/modules/generated/sklearn.impute.SimpleImputer.html) and the [min-max scaler](https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.MinMaxScaler.html) of `scikit-learn`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the evaluation, two cluster validity indices are used:\n",
    "- **Adjusted Rand Index (ARI)**. An external measure, it compares the cluster assignments against the ground-truth assignments. The (unadjusted) Rand index is given by the formula\n",
    "\n",
    "   $$\\text{ARI} =\\text{ } \\frac{\\text{TP}+\\text{TN}}{\\text{TP} + \\text{TN} + \\text{FP} + \\text{FN}},$$\n",
    "   \n",
    "   where $\\text{TP}$, $\\text{TN}$, $\\text{FP}$, and $\\text{FN}$ refer to the number of true positives, true negatives, false positives, and false negatives.\n",
    "   \n",
    "   The adjusted Rand index is a corrected-for-chance version following the scheme introduced in [[2]](https://link.springer.com/article/10.1007/BF01908075). \n",
    "  \n",
    "  \n",
    "- **Davies-Bouldin Index (DBI)**. An internal measure, it captures the average similarity score (ratio of within-cluster to between-cluster distances) of each cluster with the most similar cluster, as delineated in [[3]](https://ieeexplore.ieee.org/document/4766909).\n",
    "\n",
    "These scores are computed via the `scikit-learn` methods for calculating the [ARI](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.adjusted_rand_score.html) and [DBI](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.davies_bouldin_score.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The method below returns two dictionaries containing the evaluation results after performing $k$-means clustering using the distance measures of interest. The first dictionary uses the adjusted Rand Index as the cluster validation index while the second dictionary uses the Davies-Bouldin index.\n",
    "\n",
    "**Parameter**:\n",
    "- `dataset`: Dataset\n",
    "\n",
    "**Return Values**:\n",
    "- Dictionary containing the adjusted rand indices after performing $k$-means clustering using the distance measures of interest\n",
    "- Dictionary containing the Davies-Bouldin indices after performing $k$-means clustering using the distance measures of interest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def label_dataset(dataset):\n",
    "    NO_HEADER = r'noheader'\n",
    "    \n",
    "    # Denotes that using the distance metric results in the k-means clustering \n",
    "    # to fail to converge or the execution to run into a mathematical error\n",
    "    # (e.g., division by zero)\n",
    "    NOT_APPLICABLE = \"NOT_APPLICABLE\"\n",
    "    \n",
    "    # Some of the datasets are not encoded in the default UTF-8.\n",
    "    if re.search(NO_HEADER, dataset):\n",
    "        data_raw = pd.read_csv(dataset, encoding='latin-1', header = None)\n",
    "    else:\n",
    "        data_raw = pd.read_csv(dataset, encoding='latin-1')\n",
    "        \n",
    "    data_raw[data_raw.columns[-1]] = data_raw[data_raw.columns[-1]].fillna(data_raw[data_raw.columns[-1]].mode()[0])\n",
    "        \n",
    "    data = data_raw.to_numpy()    \n",
    "    X, y = np.split(data, [-1], axis=1)\n",
    "    \n",
    "    # Data imputation\n",
    "    imp = SimpleImputer(missing_values=np.nan, strategy='mean')\n",
    "    X = imp.fit_transform(X)\n",
    "    \n",
    "    # Min-max normalization to [0, 1]\n",
    "    scaler = MinMaxScaler()\n",
    "    X = scaler.fit_transform(X)\n",
    "    \n",
    "    # Dictionaries for storing the evaluation results\n",
    "    eval_results_ari = {}        # For adjusted Rand index\n",
    "    eval_results_dbi = {}        # For Davies-Bouldin index\n",
    "    \n",
    "    time_elapsed = {}\n",
    "    \n",
    "    X_tolist = X.tolist()\n",
    "    num_clusters = len(np.unique(y))\n",
    "    \n",
    "    # Iterate through all the distance metrics.\n",
    "    for distance_metric in metric_functions:\n",
    "        # Compute the inverse of the covariance matrix for Mahalanobis distance.\n",
    "        if distance_metric == 'mahalanobis': \n",
    "            global iv\n",
    "            \n",
    "            # Taken from https://github.com/scipy/scipy/blob/v1.8.0/scipy/spatial/distance.py#L246-L247\n",
    "            iv = np.linalg.pinv(np.atleast_2d(np.cov(X.astype(np.double, copy=False).T))).T.copy()\n",
    "        \n",
    "        metric_not_applicable = False\n",
    "        with warnings.catch_warnings(record=True) as w:\n",
    "            # Perform k-means clustering.\n",
    "            try:\n",
    "                clusters = k_means_cluster(X_tolist, num_clusters, get_metric_function(distance_metric))\n",
    "            except RuntimeWarning:\n",
    "                # Performing k-means runs into an error.\n",
    "                metric_not_applicable = True\n",
    "            \n",
    "            # Performing k-means runs into an error.\n",
    "            if len(w) > 0:\n",
    "                metric_not_applicable = True\n",
    "        \n",
    "        # Get the cluster assignments and ground-truth labels.\n",
    "        start_time = time.perf_counter()\n",
    "        cluster_mapping = get_cluster_mapping(len(X), clusters)\n",
    "        end_time = time.perf_counter()\n",
    "        \n",
    "        time_elapsed[distance_metric] = end_time - start_time\n",
    "        \n",
    "        ground_truth = get_ground_truth(data_raw)\n",
    "                \n",
    "        if metric_not_applicable:\n",
    "            eval_results_ari[distance_metric] = NOT_APPLICABLE\n",
    "            eval_results_dbi[distance_metric] = NOT_APPLICABLE\n",
    "        else:\n",
    "            # Evaluate the results of clustering.\n",
    "            eval_results_ari[distance_metric] = metrics.adjusted_rand_score(ground_truth, cluster_mapping)\n",
    "            \n",
    "            if len(np.unique(cluster_mapping)) < 2:\n",
    "                eval_results_dbi[distance_metric] = NOT_APPLICABLE\n",
    "            else:\n",
    "                eval_results_dbi[distance_metric] = metrics.davies_bouldin_score(X, cluster_mapping)\n",
    "                    \n",
    "    return eval_results_ari, eval_results_dbi, time_elapsed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function below is a utility method for logging the results of the $k$-means clustering to text files. For each dataset, three output files are produced, corresponding to the *(i)* performance based on ARI, *(ii)* performance based on DBI, and *(iii)* the time taken to perform $k$-means using each distance metric.\n",
    "\n",
    "**Parameter**:\n",
    "- `path`: Path to the text file\n",
    "- `str_data`: Results of the $k$-means clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def labels_to_txt(path, str_data):\n",
    "    f = open(f\"{path}\", \"w\")\n",
    "    f.write(str_data)\n",
    "    f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below calls the previous methods to perform $k$-means clustering on the datasets and log the results to text files. It assumes that the datasets are stored in the folder `final_datasets` and that the output files will be saved inside the folder `dataset_labels/txt_indiv`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "folder = 'new_folder'\n",
    "datasets = listdir(folder)\n",
    "\n",
    "warnings.filterwarnings(\"error\")\n",
    "\n",
    "# Number of batches into which the datasets will be split\n",
    "NUMBER_OF_BATCHES = 5\n",
    "\n",
    "batched_datasets = np.array_split(datasets, NUMBER_OF_BATCHES)\n",
    "\n",
    "# Current batch to be processed\n",
    "current_batch = 0\n",
    "\n",
    "for i, datasets in enumerate(batched_datasets[current_batch:]):\n",
    "    for dataset in datasets:    \n",
    "        # Label the dataset with the pertinent distance metrics.\n",
    "        ari, dbs, time_elapsed = label_dataset(f\"{folder}/{dataset}\")\n",
    "\n",
    "        # Create file paths for the logging the results.\n",
    "        filename, ext = dataset.rsplit('.', 1)\n",
    "        ari_path =  f\"./dataset_labels/txt_indiv/{filename}_ari.txt\"\n",
    "        dbs_path = f\"./dataset_labels/txt_indiv/{filename}_dbs.txt\"\n",
    "        time_path = f\"./dataset_labels/txt_indiv/{filename}_time.txt\"\n",
    "        \n",
    "        # Save the results to text files.\n",
    "        labels_to_txt(ari_path, str(ari))\n",
    "        labels_to_txt(dbs_path, str(dbs))\n",
    "        labels_to_txt(time_path, str(time_elapsed))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below consolidates the [output text files](https://github.com/memgonzales/meta-learning-clustering/tree/master/dataset_labels) into a [single CSV file](https://github.com/memgonzales/meta-learning-clustering/blob/master/dataset_labels/csv_collated/results_all_metrics.csv) with filename `results_all_metrics.csv` and with the following columns:\n",
    "- Name of dataset\n",
    "- Best distance metric based on ARI\n",
    "- ARI value when the best distance betric based on ARI is used\n",
    "- Best distance metric based on DBI\n",
    "- DBI value when the best distance betric based on ARI is used\n",
    "- Worst distance metric based on ARI\n",
    "- ARI value when the worst distance betric based on ARI is used\n",
    "- Worst distance metric based on DBI\n",
    "- DBI value when the worst distance betric based on ARI is used\n",
    "\n",
    "Note that:\n",
    "- For ARI, higher values denote better clustering quality.\n",
    "- For DBI, lower values denote better clustering quality.\n",
    "- Since the study is a essentially a multiclass classification task, ties in the selection of the best metric are broken by choosing the distance metric that requires a lower runtime (measured empirically).\n",
    "\n",
    "It is assumed that the output text files are in the folder `dataset_labels/txt_indiv` and that the consolidated CSV file will be stored in the folder `dataset_labels/csv_collated`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "folder = \"dataset_labels/txt_indiv\"\n",
    "datasets = listdir(folder)\n",
    "\n",
    "NOT_APPLICABLE = \"NOT_APPLICABLE\"\n",
    "\n",
    "# Number of output text files for each dataset (ARI, DBS, and time elapsed)\n",
    "CHUNKED_BY = 3 \n",
    "chunked_datasets=[datasets[i:i + CHUNKED_BY] for i in range(0, len(datasets), CHUNKED_BY)]\n",
    "\n",
    "HEADER = \"dataset,best_dist_metric_ari,best_dist_metric_ari_eval,best_dist_metric_dbs,best_dist_metric_dbs_eval,worst_dist_metric_ari,worst_dist_metric_ari_eval,worst_dist_metric_dbs,worst_dist_metric_dbs_eval\\n\"\n",
    "f_out = open('./dataset_labels/csv_collated/results_all_metrics.csv', 'w')\n",
    "f_out.write(HEADER)\n",
    "\n",
    "for dataset in chunked_datasets:\n",
    "    ari, dbs, time_elapsed = dataset[0], dataset[1], dataset[2]\n",
    "\n",
    "    # Convert text files to dictionaries.\n",
    "    f_ari = open(f\"./dataset_labels/txt_indiv/{ari}\", \"r\")\n",
    "    ari_dict = f_ari.read()\n",
    "    ari_dict = ari_dict.replace(\"'\", '\"')\n",
    "    ari_dict = json.loads(ari_dict)\n",
    "    f_ari.close()\n",
    "\n",
    "    f_dbs = open(f\"./dataset_labels/txt_indiv/{dbs}\", \"r\")\n",
    "    dbs_dict = f_dbs.read()\n",
    "    dbs_dict = dbs_dict.replace(\"'\", '\"')\n",
    "    dbs_dict = json.loads(dbs_dict)\n",
    "    f_dbs.close()\n",
    "\n",
    "    f_time = open(f\"./dataset_labels/txt_indiv/{time_elapsed}\", \"r\")\n",
    "    time_dict = f_time.read()\n",
    "    time_dict = time_dict.replace(\"'\", '\"')\n",
    "    time_dict = json.loads(time_dict)\n",
    "    f_time.close()\n",
    "\n",
    "    ari_sorted = []\n",
    "    dbs_sorted = []\n",
    "\n",
    "    # Convert dictionaries to arrays of the form\n",
    "    # [key, perfomance, time].\n",
    "    for key in ari_dict.keys():\n",
    "        if ari_dict[key] != NOT_APPLICABLE:\n",
    "            ari_sorted.append([key, ari_dict[key], time_dict[key]])\n",
    "        if dbs_dict[key] != NOT_APPLICABLE:\n",
    "            dbs_sorted.append([key, dbs_dict[key], time_dict[key]])\n",
    "                    \n",
    "    # Sort arrays by performance (best to worst) then by time (fastest to slowest).\n",
    "    ari_sorted.sort(key=lambda items: (items[1], -items[2]), reverse = True)\n",
    "    dbs_sorted.sort(key=lambda items: (items[1], items[2]))\n",
    "\n",
    "    filename, _ = ari.rsplit('_', 1)\n",
    "\n",
    "    # Get the best distance metric based on ARI\n",
    "    ari_len = len(ari_sorted)\n",
    "    if ari_len != 0:\n",
    "        best_dist_metric_ari = ari_sorted[0][0]\n",
    "        best_dist_metric_ari_eval = ari_sorted[0][1]\n",
    "    else:\n",
    "        best_dist_metric_ari = NOT_APPLICABLE\n",
    "        best_dist_metric_ari_eval = NOT_APPLICABLE\n",
    "    \n",
    "    # Get the best distance metric based on DBS\n",
    "    dbs_len = len(dbs_sorted)\n",
    "    if dbs_len != 0:\n",
    "        best_dist_metric_dbs = dbs_sorted[0][0]\n",
    "        best_dist_metric_dbs_eval = dbs_sorted[0][1]\n",
    "    else:\n",
    "        best_dist_metric_dbs = NOT_APPLICABLE\n",
    "        best_dist_metric_dbs_eval = NOT_APPLICABLE\n",
    "\n",
    "    # Get the worst distance metric based on ARI\n",
    "    if ari_len != 0:\n",
    "        worst_dist_metric_ari = ari_sorted[ari_len - 1][0]\n",
    "        worst_dist_metric_ari_eval = ari_sorted[ari_len - 1][1]\n",
    "    else:\n",
    "        worst_dist_metric_ari = NOT_APPLICABLE\n",
    "        worst_dist_metric_ari_eval = NOT_APPLICABLE\n",
    "\n",
    "    # Get the worst distance metric based on DBS\n",
    "    if dbs_len != 0:\n",
    "        worst_dist_metric_dbs = dbs_sorted[dbs_len - 1][0]\n",
    "        worst_dist_metric_dbs_eval = dbs_sorted[dbs_len - 1][1]\n",
    "    else:\n",
    "        worst_dist_metric_dbs = NOT_APPLICABLE\n",
    "        worst_dist_metric_dbs_eval = NOT_APPLICABLE\n",
    "\n",
    "    DATA = f\"{filename},{best_dist_metric_ari},{best_dist_metric_ari_eval},{best_dist_metric_dbs},{best_dist_metric_dbs_eval},{worst_dist_metric_ari},{worst_dist_metric_ari_eval},{worst_dist_metric_dbs},{worst_dist_metric_dbs_eval}\\n\"\n",
    "    f_out.write(DATA)\n",
    "\n",
    "f_out.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PART III: Reclustering of the Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results = pd.read_csv('dataset_labels/csv_collated/results_all_metrics.csv')\n",
    "clustering_results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results['best_dist_metric_ari'].value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results['best_dist_metric_dbs'].value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "folder = \"dataset_labels/txt_indiv\"\n",
    "datasets = listdir(folder)\n",
    "\n",
    "NOT_APPLICABLE = \"NOT_APPLICABLE\"\n",
    "\n",
    "TOP_N = 3\n",
    "\n",
    "# Number of output text files for each dataset (ARI, DBS, and time elapsed)\n",
    "CHUNKED_BY = 3 \n",
    "chunked_datasets=[datasets[i:i + CHUNKED_BY] for i in range(0, len(datasets), CHUNKED_BY)]\n",
    "\n",
    "HEADER = \"dataset,best_dist_metric_ari,best_dist_metric_ari_eval,best_dist_metric_dbs,best_dist_metric_dbs_eval\\n\"\n",
    "f_out = open('./dataset_labels/csv_collated/results_top_metrics.csv', 'w')\n",
    "f_out.write(HEADER)\n",
    "\n",
    "for dataset in chunked_datasets:\n",
    "    ari, dbs, time_elapsed = dataset[0], dataset[1], dataset[2]\n",
    "\n",
    "    # Convert text files to dictionaries.\n",
    "    f_ari = open(f\"./dataset_labels/txt_indiv/{ari}\", \"r\")\n",
    "    ari_dict = f_ari.read()\n",
    "    ari_dict = ari_dict.replace(\"'\", '\"')\n",
    "    ari_dict = json.loads(ari_dict)\n",
    "    f_ari.close()\n",
    "    \n",
    "    for distance_metric in clustering_results['best_dist_metric_ari'].value_counts().index[TOP_N:]:\n",
    "        ari_dict[distance_metric] = NOT_APPLICABLE\n",
    "\n",
    "    f_dbs = open(f\"./dataset_labels/txt_indiv/{dbs}\", \"r\")\n",
    "    dbs_dict = f_dbs.read()\n",
    "    dbs_dict = dbs_dict.replace(\"'\", '\"')\n",
    "    dbs_dict = json.loads(dbs_dict)\n",
    "    f_dbs.close()\n",
    "    \n",
    "    for distance_metric in clustering_results['best_dist_metric_dbs'].value_counts().index[TOP_N:]:\n",
    "        dbs_dict[distance_metric] = NOT_APPLICABLE\n",
    "\n",
    "    f_time = open(f\"./dataset_labels/txt_indiv/{time_elapsed}\", \"r\")\n",
    "    time_dict = f_time.read()\n",
    "    time_dict = time_dict.replace(\"'\", '\"')\n",
    "    time_dict = json.loads(time_dict)\n",
    "    f_time.close()\n",
    "\n",
    "    ari_sorted = []\n",
    "    dbs_sorted = []\n",
    "\n",
    "    # Convert dictionaries to arrays of the form\n",
    "    # [key, perfomance, time].\n",
    "    for key in ari_dict.keys():\n",
    "        if ari_dict[key] != NOT_APPLICABLE:\n",
    "            ari_sorted.append([key, ari_dict[key], time_dict[key]])\n",
    "        if dbs_dict[key] != NOT_APPLICABLE and key != 'standardized_euclidean':\n",
    "            dbs_sorted.append([key, dbs_dict[key], time_dict[key]])\n",
    "            \n",
    "    print(dbs_sorted)\n",
    "    \n",
    "    # Sort arrays by performance (best to worst) then by time (fastest to slowest).\n",
    "    ari_sorted.sort(key=lambda items: (items[1], -items[2]), reverse = True)\n",
    "    dbs_sorted.sort(key=lambda items: (items[1], items[2]))\n",
    "\n",
    "    filename, _ = ari.rsplit('_', 1)\n",
    "\n",
    "    # Get the best distance metric based on ARI\n",
    "    ari_len = len(ari_sorted)\n",
    "    if ari_len != 0:\n",
    "        best_dist_metric_ari = ari_sorted[0][0]\n",
    "        best_dist_metric_ari_eval = ari_sorted[0][1]\n",
    "    else:\n",
    "        best_dist_metric_ari = NOT_APPLICABLE\n",
    "        best_dist_metric_ari_eval = NOT_APPLICABLE\n",
    "    \n",
    "    # Get the best distance metric based on DBS\n",
    "    dbs_len = len(dbs_sorted)\n",
    "    if dbs_len != 0:\n",
    "        best_dist_metric_dbs = dbs_sorted[0][0]\n",
    "        best_dist_metric_dbs_eval = dbs_sorted[0][1]\n",
    "    else:\n",
    "        best_dist_metric_dbs = NOT_APPLICABLE\n",
    "        best_dist_metric_dbs_eval = NOT_APPLICABLE    \n",
    "        \n",
    "    DATA = f\"{filename},{best_dist_metric_ari},{best_dist_metric_ari_eval},{best_dist_metric_dbs},{best_dist_metric_dbs_eval}\\n\"\n",
    "    f_out.write(DATA)\n",
    "\n",
    "f_out.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results = pd.read_csv('dataset_labels/csv_collated/results_top_metrics.csv')\n",
    "clustering_results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results['best_dist_metric_ari'].value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clustering_results['best_dist_metric_dbs'].value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In the actual study, only Davies-Bouldin score was considered. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Although the datasets in the collection have ground-truth assignments, clustering is an unsupervised task, and the ground-truth assignments may not be available in most real-world use cases [[6]](https://ieeexplore.ieee.org/document/5694060), these considerations motivated the usage of an internal validation index, specifically DBS."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[1] X. Zhu, Y. Li, J. Wang, T. Zheng, and J. Fu, \"Automatic recommendation of a distance measure for\n",
    "clustering algorithms,\" *ACM Transactions on Knowledge Discovery from Data*, vol. 15, no. 1, pp. 7-22,\n",
    "December 2020.\n",
    "\n",
    "[2] L. Hubert and P. Arabie, \"Comparing partitions,\" *Journal of Classification*, vol. 2, pp. 193-218, December 1985.\n",
    "\n",
    "[3] D. L. Davies and D. W. Bouldin, \"A cluster separation measure,\" *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. PAMI-1, no. 2, pp. 224-227, April 1979.\n",
    "\n",
    "[4] Y. Liu, Z. Li, H. Xiong, X. Gao, and J. Wu, “Understanding of internal clustering validation measures,” in *2010 IEEE International Conference on Data Mining*, 2010, pp. 911–916."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.15"
  },
  "vscode": {
   "interpreter": {
    "hash": "ad2bdc8ecc057115af97d19610ffacc2b4e99fae6737bb82f5d7fb13d2f2c186"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}