On the discrepancy between Kleinberg's clustering axioms and k-means clustering algorithm behavior

DOI10.1007/S10994-023-06308-XMaRDI QIDQ6134326zbMATH OpenOpenAlexFDO

Authors Mieczysław Kłopotek, Robert A. Kłopotek

Publication date 22 August 2023

Published in Machine Learning (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1702.04577

zbMATH Keywords

\(k\)-meansclusterabilitylearnabilityEuclidean space embeddingKleinberg axioms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: This paper investigates the validity of Kleinberg's axioms for clustering functions with respect to the quite popular clustering algorithm called $k$-means. While Kleinberg's axioms have been discussed heavily in the past, we concentrate here on the case predominantly relevant for $k$-means algorithm, that is behavior embedded in Euclidean space. We point at some contradictions and counter intuitiveness aspects of this axiomatic set within $mathbb{R}^m$ that were evidently not discussed so far. Our results suggest that apparently without defining clearly what kind of clusters we expect we will not be able to construct a valid axiomatic system. In particular we look at the shape and the gaps between the clusters. Finally we demonstrate that there exist several ways to reconcile the formulation of the axioms with their intended meaning and that under this reformulation the axioms stop to be contradictory and the real-world $k$-means algorithm conforms to this axiomatic system.

Recommendations

• Wide gaps and Kleinberg's clustering axioms for \(k\)-means
• Clustering algorithm consistency in fixed dimensional spaces
• In-The-Limit Clustering Axioms
• An indication of unification for different clustering approaches
• Stability of k-Means Clustering

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 500948 (Why is no real title available?)
• A feasible \(k\)-means kernel trick under non-Euclidean feature space
• A local search approximation algorithm for \(k\)-means clustering
• Axioms for graph clustering quality functions
• Characterization, stability and convergence of hierarchical clustering methods
• Clustering algorithm consistency in fixed dimensional spaces
• Clustering stability: an overview
• Pattern classification.
• The effectiveness of Lloyd-type methods for the \(k\)-means problem

Cited in

(4)

• Also for \(k\)-means: more data does not imply better performance
• Wide gaps and Kleinberg's clustering axioms for \(k\)-means
• On the quality of k-means clustering based on grouped data
• Good (K-means) clusterings are unique (up to small perturbations)

This page was built for publication: On the discrepancy between Kleinberg's clustering axioms and \(k\)-means clustering algorithm behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134326)