Abstract
We discuss topological aspects of cluster analysis and show that inferring the topological structure of a dataset before clustering it can considerably enhance cluster detection: we show that clustering embedding vectors representing the inherent structure of a dataset instead of the observed feature vectors themselves is highly beneficial. To demonstrate, we combine manifold learning method UMAP for inferring the topological structure with density-based clustering method DBSCAN. Synthetic and real data results show that this both simplifies and improves clustering in a diverse set of low- and high-dimensional problems including clusters of varying density and/or entangled shapes. Our approach simplifies clustering because topological pre-processing consistently reduces parameter sensitivity of DBSCAN. Clustering the resulting embeddings with DBSCAN can then even outperform complex methods such as SPECTACL and ClusterGAN. Finally, our investigation suggests that the crucial issue in clustering does not appear to be the nominal dimension of the data or how many irrelevant features it contains, but rather how separable the clusters are in the ambient observation space they are embedded in, which is usually the (high-dimensional) Euclidean space defined by the features of the data. The approach is successful because it performs the cluster analysis after projecting the data into a more suitable space that is optimized for separability, in some sense.
Introduction
Clustering analysis is a fundamental task in data science, yet it remains plagued by two significant hurdles: the "curse of dimensionality" and extreme sensitivity to hyperparameters. Traditional density-based algorithms, such as DBSCAN, often struggle when clusters exhibit varying densities or entangled geometric shapes. Furthermore, selecting the appropriate neighborhood size ($\epsilon$) is notoriously difficult; a value optimized for one region of the data manifold may fail catastrophically in another.
This research proposes a shift in perspective, moving from a probabilistic view—where data is assumed to follow a mixture of distributions—to a topological one. By treating clustering as the identification of connected components on a manifold, the authors demonstrate that results can be significantly improved through topological pre-processing.
Methodology: The UMAP-DBSCAN Pipeline
The proposed approach utilizes a two-step pipeline: Topological Manifold Learning followed by Density-Based Clustering.
- UMAP (Uniform Manifold Approximation and Projection): UMAP is employed as a pre-processing step to infer the dataset's underlying topological structure. It constructs a fuzzy simplicial complex (a graph-like structure) of the data and finds a low-dimensional embedding. Crucially, UMAP’s optimization process is designed to enhance cluster separability by pulling similar points closer together and pushing dissimilar components further apart. This creates distinct "white space" between potential clusters in the embedding space.
- DBSCAN: The density-based clustering algorithm is then applied to the resulting UMAP embeddings rather than the raw feature vectors.
While combining dimensionality reduction with clustering is a known technique, this work provides a rigorous topological justification: UMAP transforms the data into a space where "connected components" are significantly more apparent to density-based algorithms.
Experimental Evaluation
The study evaluated the UMAP-DBSCAN pipeline against a comprehensive suite of synthetic and real-world benchmarks:
- Synthetic Data: High-dimensional Gaussians (up to 1,000 dimensions) with varying densities and irrelevant features, as well as complex geometric toys like nested spheres and entangled spirals.
- FCPS (Fundamental Clustering Problem Suite): Standard benchmarks including Hepta, Lsun, and Target.
- Real-World Datasets: Image datasets such as COIL-20, MNIST, and Fashion-MNIST, alongside classic datasets like Iris and Wine.
Key Performance Metrics
The results were striking, particularly on high-dimensional data. On the MNIST dataset, raw DBSCAN failed completely, yielding an Adjusted Rand Index (ARI) of 0.00. However, when combined with UMAP, the performance surged to an ARI of 0.90, matching or exceeding state-of-the-art deep learning methods like ClusterGAN and SPECTACL.
Key Insights
Separability and Dimension Inflation
A core finding of the paper is that the "nominal" dimension of a dataset is less critical than the separability of its clusters in the ambient space. UMAP effectively "sharpens" this separability. Interestingly, the authors discovered that embedding data into a higher dimension than the original (e.g., projecting 2D data into a 3D UMAP space) can improve clustering performance—a phenomenon termed "dimension inflation."
Parameter Robustness
One of the most practical advantages of this approach is the reduction in hyperparameter sensitivity. In raw data space, the range of $\epsilon$ values that yield accurate clustering is often extremely narrow. In the UMAP embedding space, this "optimal" range expands significantly, making the algorithm nearly "tuning-free" and much easier to deploy in unsupervised settings.
Topology vs. Geometry
The enhancement in clustering comes at a cost: the loss of geometric information. While UMAP preserves connectedness, it may distort the physical shape of clusters (e.g., flattening a sphere) or lose information regarding "nested" structures. This trade-off is acceptable for clustering but may be problematic for other types of analysis.
Limitations and Conclusion
Despite its strengths, the UMAP-DBSCAN approach has limitations. Because UMAP ensures every point is connected to at least its nearest neighbor, it tends to force outliers into the nearest cluster, making it unsuitable for outlier detection. Additionally, if clusters truly overlap in a probabilistic sense without topological distinction, the method will likely merge them.
In conclusion, this research demonstrates that topological manifold learning is a powerful tool for enhancing cluster analysis. By optimizing for separability and connectedness, UMAP provides a superior input for density-based clustering, outperforming complex deep learning models while remaining computationally efficient and robust to parameter selection.
Summary updated