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?


4 Answers 4


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.

  • $\begingroup$ p.s. see also answer stats.stackexchange.com/a/350191/3277 $\endgroup$
    – ttnphns
    Commented Jun 7, 2018 at 8:31
  • $\begingroup$ I'd be happy to see your answer to something like - Deterministic yet effective ways to initialize K-Means. $\endgroup$
    – Royi
    Commented Apr 22, 2020 at 18:20
  • $\begingroup$ @Royi, if you have a question about it why not post the question? $\endgroup$
    – ttnphns
    Commented Apr 22, 2020 at 20:06
  • $\begingroup$ Do you have many methods to share? I have created few "Find Farthest Samples" tricks, but are many good ones worth opening a question on? $\endgroup$
    – Royi
    Commented Apr 22, 2020 at 20:19
  • $\begingroup$ If you have anything you regard as worthy, share it in a form of a question if something worthy can be asked about it by the question. $\endgroup$
    – ttnphns
    Commented Apr 22, 2020 at 20:30

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:

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.

  • $\begingroup$ In your simulations did you notice any change in behaviour for high dimensional data? $\endgroup$ Commented Dec 7, 2017 at 16:27
  • $\begingroup$ Not that I can recall. However, my simulations wouldn't have used more than about 20 variables I think. However, the higher the dimensionality, the greater the number of random starts required all else being the same. $\endgroup$
    – Tim
    Commented Dec 7, 2017 at 23:49
  • $\begingroup$ A note: The default SPSS algorithm (btw your link is broke) is what I acronamed as RUNFP in my answer. $\endgroup$
    – ttnphns
    Commented Jul 21, 2019 at 8:30

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.

  • $\begingroup$ Thanks. I will be dealing with large dimension data so this is quite useful. $\endgroup$ Commented Dec 7, 2017 at 16:29

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.

  • $\begingroup$ If this a new algorithm to initialize k centres? If not, it would be off-topic. $\endgroup$
    – ttnphns
    Commented Nov 11, 2021 at 7:38
  • $\begingroup$ Since the last step of "Breathing K-Means" is a run of Lloyd's algorithm, one can interpret all activities before that as a new kind of initialization for this final step. It may seem involved, but so are approaches using genetic algorithms or simulated annealing to find a suitable initial codebook. One can also interpret "Breathing K-Means" as an approach that overcomes the limits of the traditional strict separation of initialization and local optimization by mixing runs of Lloyd's algorithm with "smart" insertions and deletions. $\endgroup$
    – Barden
    Commented Nov 11, 2021 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.