clustering-quality.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Similarity between two clusters\n",
    "\n",
    "Compared to supervised classification algorithms, evaluating quality of two partitions of the same data is harder. This is often done in two ways: 1) comparing how well the predicted cluster matches with the ground truth and 2) checking if the generated clusters are consistent. The second approach is useful in case there are no available ground truths. See [Scikit-learn's documentation](https://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation) for a detailed discussion. \n",
    "\n",
    "In this notebook, I will show few comparison indices and their limitations.\n",
    "\n",
    "![](./assets/pair-confusion.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## One way is to compute the *pair*-confusion matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics.cluster import pair_confusion_matrix\n",
    "from sklearn import metrics\n",
    "import numpy as np\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8, 0],\n",
       "       [2, 2]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])\n",
    "C\n",
    "TN = C[0, 0]\n",
    "FP = C[0, 1]\n",
    "FN = C[1, 0]\n",
    "TP = C[1, 1]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fowlkes–Mallows Index (FMI)\n",
    "\n",
    "- FMI, a measure for cluster similarity, is computed using the elements of $C$ as $FMI = \\frac{TP}{\\sqrt{(TP + FP) (TP + FN)}}$. \n",
    "- FMI is useful because it gives a number—and not a matrix like the pair confusion matrix—for quickly comparing two clusterings. \n",
    "- Check [Scikit-learn docs](https://scikit-learn.org/stable/modules/clustering.html#fowlkes-mallows-scores) for more."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7071067811865475"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "0.7071067811865476"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FMI = TP / np.sqrt((TP + FP) * (TP + FN))\n",
    "FMI\n",
    "\n",
    "# You can also compute FMI using scikit-learn. The results match, of course.\n",
    "metrics.fowlkes_mallows_score([0, 0, 1, 1], [0, 0, 1, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8, 0],\n",
       "       [0, 4]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Also two same partitions will have no off-diagonal elements in the pair confusion matrix and a FMI score of 1.\n",
    "\n",
    "C = pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])\n",
    "C\n",
    "TN = C[0, 0]\n",
    "FP = C[0, 1]\n",
    "FN = C[1, 0]\n",
    "TP = C[1, 1]\n",
    "\n",
    "FMI = TP / np.sqrt((TP + FP) * (TP + FN))\n",
    "FMI\n",
    "\n",
    "metrics.fowlkes_mallows_score([0, 0, 1, 1], [0, 0, 1, 1])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems with FMI and NMI\n",
    "\n",
    "Gates et al. raised an objection against FMI and [Normalized mutual information](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.normalized_mutual_info_score.html) in the following papers:\n",
    "\n",
    "- Gates, A.J., Wood, I.B., Hetrick, W.P. et al. Element-centric clustering comparison unifies overlaps and hierarchy. Sci Rep 9, 8574 (2019). https://doi.org/10.1038/s41598-019-44892-y\n",
    "- Gates et al., (2019). CluSim: a python package for calculating clustering similarity. Journal of Open Source Software, 4(35), 1264, https://doi.org/10.21105/joss.01264\n",
    "\n",
    "- One figure from their paper, reproduced below, summarizes the problem well. They also have a [GitHub repo](https://github.com/Hoosier-Clusters/clusim) with their proposed index. Below you can find an example code that reproduces the numbers in the schematic.\n",
    "\n",
    "![](./assets/41598_2019_44892_Fig1_HTML.webp)\n",
    "\n",
    "### Figure by [Gates et al. Scientific Reports](https://doi.org/10.1038/s41598-019-44892-y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The code reproduces the numbers in the schematic, using their python package.\n",
    "\n",
    "Their package can compute many indices. That's useful. Of course, the common scores (FMI, NMI etc.) matches if you compute with scikit-learn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FMI = 0.4811252243246881, NMI = 0.5451600159416435, elem-cent = 0.5407407407407406\n",
      "FMI = 0.5, NMI = 0.0, elem-cent = 0.33333333333333326\n",
      "FMI = 0.0, NMI = 0.6666666666666665, elem-cent = 0.33333333333333326\n"
     ]
    }
   ],
   "source": [
    "from clusim.clustering import Clustering\n",
    "import clusim.sim as sim\n",
    "\n",
    "true_labels = [1, 1, 1, 2, 2, 2, 3, 3, 3]\n",
    "predicted_labels = [1, 2, 2, 3, 3, 1, 1, 1, 1]\n",
    "single_cluster_labels = [1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
    "completely_fragmented_labels = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "# their data is differently formatted.\n",
    "true_clustering = Clustering().from_membership_list(true_labels)\n",
    "predicted_clustering = Clustering().from_membership_list(predicted_labels)\n",
    "predicted_single_cluster = Clustering().from_membership_list(single_cluster_labels)\n",
    "predicted_completely_fragmented = Clustering().from_membership_list(\n",
    "    completely_fragmented_labels\n",
    ")\n",
    "\n",
    "for _ in [\n",
    "    predicted_clustering,\n",
    "    predicted_single_cluster,\n",
    "    predicted_completely_fragmented,\n",
    "]:\n",
    "    print(\n",
    "        f\"FMI = {sim.fowlkes_mallows_index(true_clustering,_)}, NMI = {sim.nmi(true_clustering,_)}, elem-cent = {sim.element_sim(true_clustering,_)}\"\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "            jaccard_index                   0.3125\n",
      "               rand_index       0.6944444444444444\n",
      "            adjrand_index      0.26666666666666655\n",
      "    fowlkes_mallows_index       0.4811252243246881\n",
      "                 fmeasure      0.47619047619047616\n",
      "             purity_index       0.7777777777777777\n",
      "     classification_error      0.22222222222222232\n",
      "        czekanowski_index      0.47619047619047616\n",
      "               dice_index      0.47619047619047616\n",
      "           sorensen_index      0.47619047619047616\n",
      "    rogers_tanimoto_index       0.5319148936170213\n",
      "          southwood_index      0.45454545454545453\n",
      "      pearson_correlation      0.00102880658436214\n",
      "         corrected_chance       0.1698418780480507\n",
      "      sample_expected_sim      0.10526315789473684\n",
      "                      nmi       0.5451600159416435\n",
      "                       mi       0.8233232815796736\n",
      "                   adj_mi       0.3410389011275906\n",
      "                      rmi       0.1464053299155769\n",
      "                       vi       1.3738364418444755\n",
      "       geometric_accuracy       0.7777777777777778\n",
      "          overlap_quality                     -0.0\n",
      "                     onmi       0.6303315236619905\n",
      "              omega_index      0.26666666666666655\n"
     ]
    }
   ],
   "source": [
    "# The package can compute many scores such as... (code from their documentation https://hoosier-clusters.github.io/clusim/html/clusim.html)\n",
    "\n",
    "row_format2 = \"{:>25}\" * (2)\n",
    "for simfunc in sim.available_similarity_measures:\n",
    "    print(\n",
    "        row_format2.format(\n",
    "            simfunc, eval(\"sim.\" + simfunc +\n",
    "                          \"(true_clustering, predicted_clustering)\")\n",
    "        )\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.9.16"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}