Methods of initializing K-means clustering

Question

I am interested in the current state of the art for selecting initial seeds (cluster centers) for K-means.

Googling leads to two popular choices:

1. random selection of initial seeds, and,
2. using the KMeans++ selection technique: Arthur & Vassilvitskii 2006 k-means++: The Advantages of Careful Seeding

Are there any other promising methods that anyone here is aware of, which might not be as popular?

Answer 1

Allow me, without going far, simply to copy-paste a list of options from my own function !kmini (a macro for SPSS), found in collection "Clustering" here.

Method to create or select initial cluster centres. Choose:

• RGC - centroids of random subsamples. The data are partitioned randomly by k nonoverlapping, by membership, groups, and centroids of these groups are appointed to be the initial centres. Thus, centres are calculated, not selected from the existent dataset cases. This method yields centres that lie close to each other and to the general centroid of the data.
• RP - randomly selected points. k distinct cases of the data are randomly selected to be the initial centres.
• RUNFP - farthest points (running selection). First k cases are taken as centres and then during the run through the rest of the cases of the dataset there progressively replacements among the centres are done; the aim of the replacements is to obtain in the end k points most distant from each other in the variable space. These points (cases) occupying peripheral positions in the data cloud are the produced initial centres. (The method is used as the default in SPSS k-means procedure QUICK CLUSTER. See details in SPSS Algorithms. See also described here).
• SIMFP - farthest points (simple selection). The first centre is selected as a random case from the dataset. The 2nd centre is selected as the case maximally distant from that centre. The 3rd centre is selected as the case maximally distant from those two (from the nearest of the two), - and so on.
• KMPP - random farthest points, or k-means++. The first centre is selected as a random case from the dataset. The 2nd centre is selected also randomly, but the probability of selection of a case is proportional to the distance (square euclidean) of it to that (1st) centre. The 3rd centre is selected also randomly with the probability of selection proportional to the distance of a case to the nearest of those two centres, - and so on. (Arthur, D., Vassilvitskii, S.. K-means++: the advantages of careful seeding. // Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms. 2007., 1027–1035.)
• GREP - group representative points. The method idea – to collect as centres k most representative, “deputy” cases. The 1st centre is taken as the case closest to the general data cenroid. Then the rest of the centres are selected from the data points in such a way that each point is considered as to whether it is closer (and how much, in terms of squared euclidean distance) to a set of points than each one of the latter is to any of the already existing centres. I.e. each point is examed as a candidate to represent some group of points not yet well enough represented by the centres already collected. Point most representative in this respect is selected as the next centre. (Kaufman, L. Rousseeuw, P.J. Finding groups in data: an introduction to cluster analysis., 1990. See also: Pena, J.M. et al. An empirical comparison of four initialization methods for the K-means algorithm // Pattern Recognition Lett. 20 (10), 1999, 1027-1040.)
• [There is also a nice method, not yet implemented by me in the macro, to generate k points which are from random uniform but "less random than random", somewhere between random and greed; see potential theoretical basis for that method]
• One more method is to do hierarchical clustering by Ward's method. You may do it on subsample of objects if the sample is too big. Then means of the k clusters produced by it are the initial seeds for k-means procedure. Ward's is preferable over other hierarchical clustering methods because it shares the common target objective with k-means.

Methods RGC, RP, SIMFP, KMPP depend on random numbers and may change their result from run to run.

Method RUNFP may be sensitive to case order in the dataset; but method GREP is not (apart from occasions when there are many identical cases, ties, in the data). Method GREP may fail to collect all k centres if k is large relative the number of cases in the data (n), especially when k>n/2. [The macro will inform if the data do not allow that method to collect k centres]. Method GREP is the slowest one, it computes [in my implementation] matrix of distances between all cases, therefore it won’t suit if there are many tens of thousands or millions of cases. You could, however, do it on a random subsample of the data.

I'm not discussing presently which method is "better" and in what circumstance, because I haven't done extensive simulational probing of the question so far. My very preliminary and superficial impressions have been that GREP is particularly worthy (but it is expensive), and that if you want really cheap method still competitive enough, then just random k points, RP, is a decent choice.

Answer 2

Last time I did a comprehensive literature review on this, which was admittedly almost 20 years ago, the two main recommendations were:

1. To use Ward's Method (this is a standard hierarchical cluster analysis algorithm) to find initial centers.
2. Use random starts.

In big data applications, Ward's method doesn't work so well, although it can be applied to a sub-sample.

I did some simulations, which I didn't ever get around to publishing, and found that:

• 100 Random starts consistently outperformed Ward's Method.
• The default SPSS algorithm for finding start points outperformed 100 random startpoints.
• At 1,000 random start points, randomization consistently was the best method.

The main take out I took from this is that the SPSS algorithm is surprisingly good, but if one has the resources, 1000+ random start points is the way to go.

Answer 3

With ttnphns nomenclature, I tested RGC, RP, and KMPP on:

• 2D/3D points
• bag of words from textual documents
• curves with essentially $L^2$ distance.

I don't recommend RGC because the resulting centers are very close to each other: the mean of many points is close to the global mean (law of large numbers). This can slow down convergence a lot: it takes some time before clusters start to individualize.

RP is generally good and would recommand as the first easy choice.

KMPP is very popular and works very well in small dimension: compared to RP it tends to reduce the probability of ending in a local minimum.

However when I was working on big datasets (1M points that are bag of words from textual documents with big dimension), RP slightly outperformed KMPP in the sense that it ended with slightly fewer iterations. I was surprised of this. In big dataset/high dimension, the convergence to the global minimum is impossible, you measure quality as "how good the local minimum is" = "how small final SOD is". Both methods had the same quality.

Note that it is important to use a randomized method if you want to use replications to improve the quality.

Answer 4

I assume from your question that you are interested in good solutions to k-means problems (otherwise any initialization method would do). You might want to have a look at the "Breathing K-Means" algorithm (I am the inventor). Instead of just being an initilization method for Lloyd's algorithm (a.k.a. the k-means algorithm) it adds and removes groups of centroids based on error and utility while running Lloyd's algorithm after each add or remove step. This algorithm beats k-means++ on 39 of 40 test problems, mainly taken from the literature. It is on par for the one test problem where k-means++ finds the optimum (and thus cannot be beaten). Software: https://pypi.org/project/bkmeans (API compatible with scikit-learn) Preprint: https://arxiv.org/abs/2006.15666.