<abstract xmlns="http://www.w3.org/1999/xhtml">
<p>The widely applied <italic>k</italic>-means algorithm produces clusterings that violate our expectations with respect to high/low similarity/density within/between clusters and is in conflict with Kleinberg’s axiomatic system for distance based clustering algorithms that formalizes those expectations. In particular, <italic>k</italic>-means violates the consistency axiom. We hypothesise that this clash is due to the unexplained expectation that the data themselves should have the property of being clusterable in order to expect the algorithm clustering them to fit a clustering axiomatic system. To demonstrate this, we introduce two new clusterability properties, i.e., variational <italic>k</italic>-separability and residual <italic>k</italic>-separability, and show that then Kleinberg’s consistency axiom holds for <italic>k</italic>-means operating in the Euclidean or non-Euclidean space. Furthermore, we propose extensions of the <italic>k</italic>-means algorithm that fit approximately Kleinberg’s richness axiom, which does not hold for <italic>k</italic>-means. In this way, we reconcile <italic>k</italic>-means with Kleinberg’s axiomatic framework in Euclidean and non-Euclidean settings. Besides contribution to the theory of axiomatic frameworks of clustering and to clusterability theory, the practical benefit is the possibility to construct datasets for testing purposes of algorithms optimizing the <italic>k</italic>-means cost function. This includes a method of construction of clusterable data with a global optimum known in advance.</p>
</abstract>

The widely applied k-means algorithm produces clusterings that violate our expectations with respect to high/low similarity/density within/between clusters and is in conflict with Kleinberg’s axiomatic system for distance based clustering algorithms that formalizes those expectations. In particular, k-means violates the consistency axiom. We hypothesise that this clash is due to the unexplained expectation that the data themselves should have the property of being clusterable in order to expect the algorithm clustering them to fit a clustering axiomatic system. To demonstrate this, we introduce two new clusterability properties, i.e., variational k-separability and residual k-separability, and show that then Kleinberg’s consistency axiom holds for k-means operating in the Euclidean or non-Euclidean space. Furthermore, we propose extensions of the k-means algorithm that fit approximately Kleinberg’s richness axiom, which does not hold for k-means. In this way, we reconcile k-means with Kleinberg’s axiomatic framework in Euclidean and non-Euclidean settings. Besides contribution to the theory of axiomatic frameworks of clustering and to clusterability theory, the practical benefit is the possibility to construct datasets for testing purposes of algorithms optimizing the k-means cost function. This includes a method of construction of clusterable data with a global optimum known in advance.

Wide Gaps and Kleinberg’s Clustering Axioms for <italic>k</italic>–Means

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Wide Gaps and Kleinberg’s Clustering Axioms for –Means

The widely applied k-means algorithm produces clusterings that violate our expectations with respect to high/low similarity/density within/between clusters and...

Wide Gaps and Kleinberg’s Clustering Axioms for k–Means

Published Online: Mar 26, 2024

Page range: 135 - 147

Received: Aug 18, 2023

Accepted: Nov 28, 2023

DOI: https://doi.org/10.61822/amcs-2024-0010

Keywords
clustering theory, clustering axioms, clusterability

© 2024 Mieczysław A. Kłopotek, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Wide Gaps and Kleinberg’s Clustering Axioms for k–Means

Published Online: Mar 26, 2024

Page range: 135 - 147

Received: Aug 18, 2023

Accepted: Nov 28, 2023

DOI: https://doi.org/10.61822/amcs-2024-0010

Keywordsclustering theory, clustering axioms, clusterability

© 2024 Mieczysław A. Kłopotek, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
clustering theory, clustering axioms, clusterability