Measuring group-separability in geometrical space for evaluation of pattern recognition and embedding algorithms

Aldo Acevedo, Sara Ciucci, Ming-Ju Kuo, Claudio Durán, Carlo V. CannistraciarXiv 2019 · arXiv

Introduction

Dimensionality reduction (DR) algorithms, such as t-SNE, PCA, and Isomap, are fundamental tools in data science for visualizing high-dimensional datasets. However, evaluating the success of these algorithms remains a significant challenge. Researchers often rely on Cluster Validity Indices (CVIs) like the Silhouette or Dunn indices to determine if groups are well-separated in the resulting low-dimensional space.

This paper argues that traditional CVIs are often unsuitable for DR evaluation due to two primary flaws: dimension dependency and geometric bias. Because many CVIs lack a fixed upper bound, comparing separability across different dimensions (e.g., a 2D plot versus a 3D plot) is statistically invalid. Furthermore, many indices reward the collapse of clusters into single points, which ignores the internal variability and structure that DR algorithms are specifically designed to preserve.

The Projection Separability (PS) Framework

To address these limitations, the authors introduce the Projection Separability (PS) rationale. This framework provides a robust, dimension-independent method for measuring how well groups are separated in a geometric space. The workflow follows a three-step process:

  1. Centroid Identification: For any two groups of data, the geometric centers (centroids) are identified.
  2. 1D Projection: A line is drawn connecting these centroids, and all data points from both groups are projected onto this 1D axis.
  3. Statistical Measurement: Once the data is projected into 1D, standard statistical measures are applied to quantify the separation between the groups.

Based on this rationale, the authors propose three specific Projection Separability Indices (PSIs):

  • PSI-P: Utilizes the p-value from the Mann-Whitney U test.
  • PSI-ROC: Utilizes the Area Under the ROC Curve (AUC-ROC).
  • PSI-PR: Utilizes the Area Under the Precision-Recall Curve (AUC-PR).

Because these indices are grounded in probability and statistics, they are inherently bounded (e.g., between 0 and 1), allowing for objective comparisons across different datasets and embedding dimensions.

Experimental Validation

The authors evaluated the PS indices across a diverse range of synthetic and real-world high-dimensional datasets, including:

  • Tripartite-Swiss-Roll: A synthetic 3D manifold used to test nonlinear cluster separation.
  • Gastric Mucosa Microbiome: 16S rRNA gene sequences, representing a small sample size challenge.
  • Radar Signal: 350 signals from the ionosphere used to test the "crowding problem" where clusters overlap.
  • Image Proteomics: 42 samples related to neuropathic pain and ALS.
  • MNIST: The classic handwritten digit dataset, used to evaluate performance across 10 groups in both 2D and 3D embeddings.

Key Insights and Advantages

Preservation of Intra-cluster Variability

Unlike traditional indices that penalize clusters for being "spread out," PSIs only measure separation along the projection line. This allows researchers to select embeddings that reveal the internal "gradient" or structure of a group without being penalized for the cluster's spread.

Dimension Independence

The statistical bounding of PSIs ensures that a score (e.g., 0.9) carries the same meaning in a 2D embedding as it does in a 3D embedding. This is a significant improvement over traditional metrics like the Calinski-Harabasz index, which can scale arbitrarily with dimensionality.

Automated Parameter Tuning

The PS framework can serve as an objective function to automatically optimize DR algorithm parameters. The authors demonstrated that PSIs can find the ideal "perplexity" for t-SNE or the optimal "k-neighbors" for Isomap, replacing the subjective "trial and error" approach typically used by practitioners.

Results and Performance

In comparative testing against six baseline CVIs, the PSIs consistently demonstrated superior accuracy in identifying the DR methods that best preserved the original data's group structure.

In the Radar dataset—a known challenge for DR due to overlapping clusters—the PSIs correctly identified Minimum Curvilinearity Embedding (MCE) as the most effective method. In contrast, traditional metrics like the Dunn index provided misleading or untrustworthy results. Furthermore, a similarity analysis (the "PSI-triangle") revealed that the three PS indices are highly consistent with one another across different datasets, whereas traditional CVIs often yield contradictory rankings.

Limitations and Future Work

While the PS rationale is a significant advancement, the authors acknowledge certain areas for future development. The current "all-pairs" comparison approach may become computationally expensive for datasets with a very large number of classes. Additionally, while the current method relies on centroids to define the projection line, future iterations may explore alternative projection axes to better handle highly irregular or non-convex cluster shapes. Finally, the authors suggest that other statistical measures, such as the Matthews correlation coefficient, could be integrated into the PS framework.

Summary updated

Abstract

Evaluating data separation in a geometrical space is fundamental for pattern recognition. A plethora of dimensionality reduction (DR) algorithms have been developed in order to reveal the emergence of geometrical patterns in a low dimensional visible representation space, in which high-dimensional samples similarities are approximated by geometrical distances. However, statistical measures to evaluate directly in the low dimensional geometrical space the sample group separability attaiend by these DR algorithms are missing. Certainly, these separability measures could be used both to compare algorithms performance and to tune algorithms parameters. Here, we propose three statistical measures (named as PSI-ROC, PSI-PR, and PSI-P) that have origin from the Projection Separability (PS) rationale introduced in this study, which is expressly designed to assess group separability of data samples in a geometrical space. Traditional cluster validity indices (CVIs) might be applied in this context but they show limitations because they are not specifically tailored for DR. Our PS measures are compared to six baseline cluster validity indices, using five non-linear datasets and six different DR algorithms. The results provide clear evidence that statistical-based measures based on PS rationale are more accurate than CVIs and can be adopted to control the tuning of parameter-dependent DR algorithms.
BibTeX
@misc{acevedo2019measuring,
  author = {Aldo Acevedo and Sara Ciucci and Ming-Ju Kuo and Claudio Durán and Carlo V. Cannistraci},
  title = {{Measuring group-separability in geometrical space for evaluation of pattern recognition and embedding algorithms}},
  year = {2019},
  eprint = {1912.12418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.12418},
}
Figure