A Pragmatic Method for Comparing Clusterings with Overlaps and Outliers
Authors: Ryan DeWolfe, Paweł Prałat, François Théberge
Organizations: Department of Mathematics, Toronto Metropolitan University, Toronto, Canada · Tutte Institute for Mathematics and Computing, Ottawa, Canada
Clustering algorithms are an essential part of the unsupervised data science ecosystem, and extrinsic evaluation of clustering algorithms requires a method for comparing the detected clustering to a ground truth clustering. In a general setting, the detected and ground truth clusterings may have outliers (objects belonging to no cluster), overlapping clusters (objects may belong to more than one cluster), or both, but methods for comparing these clusterings are currently undeveloped. In this note, we define a pragmatic similarity measure for comparing clusterings with overlaps and outliers, show that it has several desirable properties, and experimentally confirm that it is not subject to several common biases afflicting other clustering comparison measures.
Figures & tables
Figure 1: Recreation of the experiment in Figure 2 of [ 10 ] with Fwo∗ . Each column represents one scenario, including a visual of the scenario, the intuitive behaviour of a similarity measure in this scenario, and the actual behaviour of several measures in each row respectively. Each line is the average of 100 simulations and the shaded region (usually too small to appear) covers plus or minus one standard deviation. In each scenario, the proposed Fwo∗ measure matches our intuition.
Figure 2: Comparing comparison measure behaviour on intuitive scenarios when overlaps or outliers are present. The top row is the scenario with overlapping clusters, and the second row has outliers; the columns, from left to right, show a visual of the scenario, the intuitive behaviour, and the actual behaviour of each method.
Figure 3: An experiment comparing graph aware clustering comparison, similar to that of Figure 5 from [ 24 ] . We use three resolutions ( 0.5 , 1.0 , and 3.75 shown in red, green, and yellow respectively) of the Leiden clustering algorithm on ABCD graphs with 2000 vertices and show, the similarity of each detected vertex clustering to the ground truth vertex clusters, the similarity of the detected induced edge clustering to the ground truth induced edge clusters, and the number of clusters The solid line represents the average over 10 samples and the shaded region covers plus or minus one standard deviation.
External indexes can be used for cluster evaluation when ground truth is available. We review the most common external validity indexes focusing on set-matching-based measures. We recommend centroid index (CI), because it is an intuitive cluster-level measure with an explainable result. If we need a more fine-tuned, point-level measure, there are more choices. Pair-set index (PSI) provides a normalized score which is not biased by cluster sizes. If all points should matter equally, then clustering accuracy (ACC) or any other set-matching measure is suitable.
Pasi Fränti
School of Computing University of Eastern Finland Joensuu, Finland
Scalar metrics are often used to evaluate clusterings against known classes, but they can obscure a fundamental trade-off: clusterings should be informative about class labels while avoiding unnecessary fragmentation. Here we describe normalized scores of cluster homogeneity and parsimony that quantify this trade-off. These scores build on the information bottleneck principle, modified to not reward lossy compression. We show by example and mathematical proof that our definitions of these scores have the intuitive property of varying monotonically under cluster refinement in contrast to related proposals. Extending the information-theoretic framework beyond Shannon entropies, we furthermore derive set-matching and pair-based counterparts of the homogeneity and parsimony scores. These unify commonly used evaluation criteria and show that, in the pair-based setting, the homogeneity-parsimony trade-off recovers the receiver operating characteristic of binary classifiers. We demonstrate the framework's utility for feature selection and algorithm comparison, illustrating how considering scores jointly can clarify clustering operating points and identify Pareto-optimal solutions.
Andreas Tiffeau-Mayer
Division of Infection and Immunity & Institute for the Physics of Living Systems, University College London
Despite being ubiquitous in science, clustering lacks a unified framework for quantitatively evaluating the replicability of its results. We present evaluating replicability via iterative clustering assignments (ERICA), a method for determining whether clusters can be identified reproducibly in a dataset. The pipeline computes a statistic that determines whether reproducible cluster structure is present in a dataset. Quantitative visualization methods are also introduced to characterize similarities between clusters and identify observations that may represent outliers or unstable assignments. Experiments on synthetic datasets demonstrate that ERICA successfully identifies reproducible cluster structure. In contrast, application of ERICA to three breast cancer gene-expression datasets reveals instances in which clustering solutions are not reproducible. The study underscores the importance of rigorously evaluating clustering solutions and provides a practical framework for doing so.
Siamak K. Sorooshyari, Manuel A. Rivas, Robert Tibshirani
Department of Statistics Stanford University Stanford, CA 94305, USA · Department of Biomedical Data Science Stanford University Stanford, CA 94305, USA · Department of Statistics and Biomedical Data Science Stanford University Stanford, CA 94305, USA