Also for k-means: more data does not imply better performance
Open Access
- 25 July 2023
- journal article
- research article
- Published by Springer Nature in Machine Learning
- Vol. 112 (8) , 3033-3050
Abstract
Arguably, a desirable feature of a learner is that its performance gets better with an increasing amount of training data, at least in expectation. This issue has received renewed attention in recent years and some curious and surprising findings have been reported on. In essence, these results show that more data does actually not necessarily lead to improved performance—worse even, performance can deteriorate. Clustering, however, has not been subjected to such kind of study up to now. This paper shows that k-means clustering, a ubiquitous technique in machine learning and data mining, suffers from the same lack of so-called monotonicity and can display deterioration in expected performance with increasing training set sizes. Our main, theoretical contributions prove that 1-means clustering is monotonic, while 2-means is not even weakly monotonic, i.e., the occurrence of nonmonotonic behavior persists indefinitely, beyond any training sample size. For larger k, the question remains open.Keywords
This publication has 31 references indexed in Scilit:
- The Dipping Phenomenon2012
- NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 2009
- Clustering Methods: A History of k-Means Algorithms2007
- Bayesian K-Means as a “Maximization-Expectation” Algorithm2006
- A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median ClusteringLecture Notes in Computer Science, 2004
- Linear and Nonlinear Extension of the Pseudo-Inverse Solution for Learning Boolean FunctionsEurophysics Letters, 1989
- Strong Consistency of $K$-Means ClusteringThe Annals of Statistics, 1981
- Asymptotic Distributions for Clustering CriteriaThe Annals of Statistics, 1978
- Multidimensional group analysisAustralian Journal of Botany, 1966
- The Problem of Optimum StratificationScandinavian Actuarial Journal, 1950