Fast adaptive k-means clustering: some empirical results

Abstract

The authors present learning rate schedules for fast adaptive <e1 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</e1> -means clustering which surpass the standard MacQueen learning rate schedule (J. MacQeen, 1967) in speed and quality of solution by several orders of magnitude for large <e1 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</e1> . The methods accomplish this by largely overcoming the problems of metastable local minima and nonstationarity of cluster region boundaries which plague the MacQueen approach. The authors use simulation results to compare the clustering performances of four learning rate schedules applied to independently sampled data from a uniform distribution in one and two dimensions