Abstract
This paper discusses the topological aspects of cluster analysis, demonstrating that inferring the topological structure of a dataset prior to clustering can significantly enhance performance. By combining Uniform Manifold Approximation and Projection (UMAP) for manifold inference with the density-based clustering algorithm DBSCAN, we show that clustering embedding vectors—which represent the underlying data manifold—is superior to clustering raw feature vectors. Our results across synthetic and real-world datasets indicate that this approach simplifies clustering by reducing hyperparameter sensitivity and improves accuracy, even outperforming complex deep learning methods like SPECTACL and ClusterGAN. We conclude that the primary challenge in clustering is not the nominal dimensionality of the data, but rather the separability of clusters within the ambient observation space.
Introduction
Clustering is a fundamental task in unsupervised learning, yet it remains fraught with practical difficulties. Most traditional clustering algorithms struggle with two primary hurdles: the "curse of dimensionality," where irrelevant features obscure structural relationships, and extreme sensitivity to hyperparameters. For density-based algorithms like DBSCAN, the choice of the neighborhood radius ($\epsilon$) is often critical; a slight deviation can lead to the merger of distinct clusters or the fragmentation of a single cluster into noise.
This research argues that these difficulties stem from a predominantly probabilistic view of clustering—treating data as a mixture of distributions. By shifting to a topological perspective, where clusters are viewed as connected components of a manifold, we can leverage manifold learning to "preprocess" the data space, making it more amenable to density-based extraction.
Methodology: The UMAP-DBSCAN Pipeline
The proposed methodology follows a two-stage pipeline designed to optimize cluster separability before the clustering algorithm is applied.
1. Topological Manifold Learning (UMAP)
UMAP is employed to infer the topological structure of the data. It operates by constructing a fuzzy $k$-nearest neighbor graph that captures the local connectivity of the manifold. It then optimizes a low-dimensional layout by minimizing the cross-entropy between the high-dimensional graph and the low-dimensional representation. This process naturally "pulls" connected points together and "pushes" disconnected components apart, effectively sharpening the boundaries between potential clusters.
2. Density-Based Clustering (DBSCAN)
The resulting embeddings are then processed using DBSCAN. Because the UMAP stage has already created significant "white space" between disconnected components, DBSCAN becomes much more robust. The algorithm is no longer required to navigate the dense, noisy feature space of the original data; instead, it identifies the clearly separated components in the embedding space.
Key Insights
Separability vs. Dimensionality
A core finding of this study is that the nominal dimension of a dataset (the number of features) is less important than its separability in the ambient space. If clusters are topologically distinct, manifold learning can successfully project them into a space where they are easily identifiable, regardless of how many irrelevant features are present.
The "White Space" Effect and Parameter Robustness
One of the most significant practical benefits of this approach is the reduction in parameter sensitivity. In raw feature space, the range of $\epsilon$ values that yield a correct clustering is often extremely narrow. After UMAP processing, the "white space" created between clusters allows for a much wider plateau of valid $\epsilon$ values. In synthetic tests, the range of functional $\epsilon$ values expanded from a narrow window (e.g., [0.1, 0.3]) to a massive range (e.g., [0.0, 8.1]), making the system nearly "tuning-free."
Dimension Inflation
While manifold learning is typically associated with dimensionality reduction, the authors observed that "dimension inflation"—embedding data into a higher dimension than its original state (e.g., from 2D to 3D)—can sometimes further improve separability. This suggests that the goal of the embedding is not necessarily compression, but the optimization of the space for component separation.
Experimental Results
The UMAP-DBSCAN pipeline was tested against a variety of benchmarks, including synthetic Gaussians, the Fundamental Clustering Problem Suite (FCPS), and high-dimensional image datasets like MNIST and Fashion-MNIST (FMNIST).
- MNIST Performance: On the MNIST dataset, raw DBSCAN failed completely, achieving an Adjusted Rand Index (ARI) of 0.00. The UMAP+DBSCAN approach achieved an ARI of 0.90.
- Comparison with Deep Learning: The pipeline outperformed more complex and computationally expensive generative models. On datasets such as Pendigits and Fashion-MNIST, UMAP+DBSCAN yielded higher ARI scores than ClusterGAN and SPECTACL.
- Complex Geometries: The method successfully resolved "impossible" shapes in the FCPS benchmarks, such as the Chainlink and Hepta datasets, which often defeat traditional centroid-based or simple density-based methods.
Limitations and Considerations
Despite its strengths, the topological approach has specific limitations:
- Outlier Handling: UMAP’s local connectivity constraint forces every point to connect to at least one neighbor, which can inadvertently pull outliers into the nearest cluster. Pre-processing for outlier detection may be required for very noisy datasets.
- Overlapping Clusters: If clusters physically overlap in the ambient observation space (i.e., they are not topologically distinct), UMAP cannot separate them. In such instances, probabilistic models like Gaussian Mixture Models remain more appropriate.
- Geometric Preservation: Manifold learning prioritizes connectedness over global geometry. Consequently, the relative distances or nested structures (like concentric spheres) in the original space may be lost in the embedding.
Conclusion
Enhancing cluster analysis via topological manifold learning represents a significant shift in how we approach unsupervised learning. By focusing on the separability of connected components rather than raw feature distances, we can achieve superior clustering performance with significantly less manual hyperparameter tuning. This approach proves that even simple density-based algorithms can outperform state-of-the-art deep learning models when the underlying topological structure of the data is properly leveraged.
Summary updated