How I learned to stop worrying and love the curse of dimensionality: an appraisal of cluster validation in high-dimensional spaces
This work addresses the problem of cluster validation in high-dimensional data for researchers and practitioners in data mining and machine learning, providing evidence that common methods remain effective, though it is incremental as it builds on existing validation techniques.
The paper investigates the performance of Euclidean norm-based cluster validity indices in high-dimensional spaces, finding that most indices maintain or improve sensitivity across various synthetic data schemes, effectively countering the curse of dimensionality for cluster validation.
The failure of the Euclidean norm to reliably distinguish between nearby and distant points in high dimensional space is well-known. This phenomenon of distance concentration manifests in a variety of data distributions, with iid or correlated features, including centrally-distributed and clustered data. Unsupervised learning based on Euclidean nearest-neighbors and more general proximity-oriented data mining tasks like clustering, might therefore be adversely affected by distance concentration for high-dimensional applications. While considerable work has been done developing clustering algorithms with reliable high-dimensional performance, the problem of cluster validation--of determining the natural number of clusters in a dataset--has not been carefully examined in high-dimensional problems. In this work we investigate how the sensitivities of common Euclidean norm-based cluster validity indices scale with dimension for a variety of synthetic data schemes, including well-separated and noisy clusters, and find that the overwhelming majority of indices have improved or stable sensitivity in high dimensions. The curse of dimensionality is therefore dispelled for this class of fairly generic data schemes.