2022/01/13 by Brian A. Powell, Powell, Brian A.
Computer Science · #Advanced Clustering Algorithms Research #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #cs.LG
paper · pdf · doi:10.48550/arxiv.2201.05214
20 pages, 10 figures
arxiv created 2022/01/13 · openalex publication_date 2022/01/13 · arxiv updated 2022/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.