# Random Normed k-Means: A Paradigm-Shift in Clustering within Probabilistic Metric Spaces

arXiv: https://arxiv.org/abs/2504.03928 · HTML: https://mlsanity.com/paper/2504.03928/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 90 references that are in the map.
- First posted on arXiv 4 Apr 2025.

## Builds on (most cited first, 11 of 11)

- [Deep k-Means: Jointly clustering with k-Means and learning representations](https://mlsanity.com/paper/1806.10069/) (2018)
- [The Impact of Random Models on Clustering Similarity](https://mlsanity.com/paper/1701.06508/) (2017)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Neural network-based clustering using pairwise constraints](https://mlsanity.com/paper/1511.06321/) (2015)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Asynchronous Federated Clustering with Unknown Number of Clusters](https://mlsanity.com/paper/2412.20341/) (2024)
- [Learning Self-Growth Maps for Fast and Accurate Imbalanced Streaming Data Clustering](https://mlsanity.com/paper/2404.09243/) (2024)
- [Medoid Silhouette clustering with automatic cluster number selection](https://mlsanity.com/paper/2309.03751/) (2023)
- [Categorical Data Clustering via Value Order Estimated Distance Metric Learning](https://mlsanity.com/paper/2411.15189/) (2024)
- [Query-augmented Active Metric Learning](https://mlsanity.com/paper/2111.04871/) (2021)

## Abstract (arXiv)

Existing approaches remain largely constrained by traditional distance metrics, limiting their effectiveness in handling random data. In this work, we introduce the first k-means variant in the literature that operates within a probabilistic metric space, replacing conventional distance measures with a well-defined distance distribution function. This pioneering approach enables more flexible and robust clustering in both deterministic and random datasets, establishing a new foundation for clustering in stochastic environments. By adopting a probabilistic perspective, our method not only introduces a fresh paradigm but also establishes a rigorous theoretical framework that is expected to serve as a key reference for future clustering research involving random data. Extensive experiments on diverse real and synthetic datasets assess our model's effectiveness using widely recognized evaluation metrics, including Silhouette, Davies-Bouldin, Calinski Harabasz, the adjusted Rand index, and distortion. Comparative analyses against established methods such as k-means++, fuzzy c-means, and kernel probabilistic k-means demonstrate the superior performance of our proposed random normed k-means (RNKM) algorithm. Notably, RNKM exhibits a remarkable ability to identify nonlinearly separable structures, making it highly effective in complex clustering scenarios. These findings position RNKM as a groundbreaking advancement in clustering research, offering a powerful alternative to traditional techniques while addressing a long-standing gap in the literature. By bridging probabilistic metrics with clustering, this study provides a foundational reference for future developments and opens new avenues for advanced data analysis in dynamic, data-driven applications.