How I learned to stop worrying and love the curse of dimensionality: an appraisal of cluster validation in high-dimensional spaces

• URL: http://arxiv.org/abs/2201.05214v1
• Date: Thu, 13 Jan 2022 21:17:10 GMT
• Title: How I learned to stop worrying and love the curse of dimensionality: an appraisal of cluster validation in high-dimensional spaces
• Authors: Brian A. Powell
• Abstract summary: We investigate how the sensitivities of common Euclidean norm-based cluster indices scale with dimension for a variety of synthetic data schemes. We find that the overwhelming majority of indices have improved or stable sensitivity in high dimensions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Fuzzy K-Means Clustering without Cluster Centroids [79.19713746387337]
  Fuzzy K-Means clustering is a critical computation technique in unsupervised data analysis. This paper proposes a novel Fuzzy K-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Deep Clustering Evaluation: How to Validate Internal Clustering Validation Measures [2.2252684361733284]
  Deep clustering is a method for partitioning complex, high-dimensional data using deep neural networks. Traditional clustering validation measures, designed for low-dimensional spaces, are problematic for deep clustering. This paper addresses these challenges in evaluating clustering quality in deep learning.
  arXiv  Detail & Related papers  (2024-03-21T20:43:44Z)
• A general theory for robust clustering via trimmed mean [7.650319416775203]
  We introduce a hybrid clustering technique with a novel trimmed mean type centroid estimate to produce mislabeling guarantees. Our results reduce to the sub-Gaussian case when errors follow sub-Gaussian distributions. We show that these initial centroid estimates are sufficiently good for the subsequent clustering algorithm to achieve the optimal mislabeling rates.
  arXiv  Detail & Related papers  (2024-01-10T22:56:44Z)
• Beyond Labels: Advancing Cluster Analysis with the Entropy of Distance Distribution (EDD) [0.0]
  Entropy of Distance Distribution (EDD) is a paradigm shift in label-free clustering analysis. Our method employs the Shannon information entropy to quantify the 'peakedness' or 'flatness' of distance distributions in a data set. EDD's potential extends beyond conventional clustering analysis, offering a robust, scalable tool for unraveling complex data structures.
  arXiv  Detail & Related papers  (2023-11-28T09:22:17Z)
• Sanitized Clustering against Confounding Bias [38.928080236294775]
  This paper presents a new clustering framework named Sanitized Clustering Against confounding Bias (SCAB) SCAB removes the confounding factor in the semantic latent space of complex data through a non-linear dependence measure. Experiments on complex datasets demonstrate that our SCAB achieves a significant gain in clustering performance.
  arXiv  Detail & Related papers  (2023-11-02T14:10:14Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Intrinsic dimension estimation for discrete metrics [65.5438227932088]
  In this letter we introduce an algorithm to infer the intrinsic dimension (ID) of datasets embedded in discrete spaces. We demonstrate its accuracy on benchmark datasets, and we apply it to analyze a metagenomic dataset for species fingerprinting. This suggests that evolutive pressure acts on a low-dimensional manifold despite the high-dimensionality of sequences' space.
  arXiv  Detail & Related papers  (2022-07-20T06:38:36Z)
• Anomaly Clustering: Grouping Images into Coherent Clusters of Anomaly Types [60.45942774425782]
  We introduce anomaly clustering, whose goal is to group data into coherent clusters of anomaly types. This is different from anomaly detection, whose goal is to divide anomalies from normal data. We present a simple yet effective clustering framework using a patch-based pretrained deep embeddings and off-the-shelf clustering methods.
  arXiv  Detail & Related papers  (2021-12-21T23:11:33Z)
• Density-Based Clustering with Kernel Diffusion [59.4179549482505]
  A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in density-based clustering algorithms. We propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness.
  arXiv  Detail & Related papers  (2021-10-11T09:00:33Z)
• Deep Semi-Supervised Embedded Clustering (DSEC) for Stratification of Heart Failure Patients [50.48904066814385]
  In this work we apply deep semi-supervised embedded clustering to determine data-driven patient subgroups of heart failure. We find clinically relevant clusters from an embedded space derived from heterogeneous data. The proposed algorithm can potentially find new undiagnosed subgroups of patients that have different outcomes.
  arXiv  Detail & Related papers  (2020-12-24T12:56:46Z)
• On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters [0.0]
  This work considers the notion of Wasserstein barycenters, accompanied by appropriate clustering indices based on the intrinsic geometry of the Wasserstein space where the clustering task is performed. Such type of clustering approaches are highly appreciated in many fields where the observational/experimental error is significant. Under this perspective, each observation is identified by an appropriate probability measure and the proposed clustering schemes rely on discrimination criteria.
  arXiv  Detail & Related papers  (2019-12-26T08:46:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.