cs.LGFeb 16, 2026

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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∗F^{*}_{wo} . 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 100100 simulations and the shaded region (usually too small to appear) covers plus or minus one standard deviation. In each scenario, the proposed Fwo∗F^{*}_{wo} 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.50.5 , 1.01.0 , and 3.753.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.
More in this topic

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Explore similar work

CardsList

  1. How to evaluate clustering with ground truth?

    Jun 25, 2026Pasi FräntiClustering

    School of Computing University of Eastern Finland Joensuu, Finland

  2. External Clustering Validation by the Homogeneity-Parsimony Trade-off

    Jul 22, 2026Andreas Tiffeau-MayerClusteringInformation Bottleneck

    Division of Infection and Immunity & Institute for the Physics of Living Systems, University College London

  3. ERICA: Quantifying Replicability of Cluster Analysis

    May 29, 2026Siamak K. Sorooshyari, Manuel A. Rivas, Robert TibshiraniClusteringML Reproducibility

    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