0
$\begingroup$

The $k$-means problem in its common form can be stated as follows:

Given a data set $\mathcal{X}=x_1, ..., x_n$ consisting of $d$-dimensional vectors find a set $C = c_1,...,c_k$ of $d$-dimensional centroids such that the summed square distance between the vectors and their nearest centroid is minimized, i.e. $C$ should minimize the following function:

$$\phi=\sum_{x\in\mathcal{X}} \underset{c\in C}{min} \|c-x\|^{2} $$ Since the $k$-means problem is known to be NP-complete, for practical problems one has to settle for approximative methods like the $k$-means algorithm which converges to a local minimum. Using "careful" seeding methods like k-means++ the quality of the obtained local minima often becomes better than with random initialization but may still be far from the global optimum.

Are there any known (not exponentially expensive) methods which deliver better solutions than the k-means/k-means++ algorithm?

Improve this question
$\endgroup$
5
  • $\begingroup$ k-means++ is just a method to suggest initial centres, not the clustering algorithm itself. Here is some alternative to k-means++ initializations stats.stackexchange.com/q/317493/3277. $\endgroup$
    – ttnphns
    Aug 7, 2019 at 4:59
  • $\begingroup$ If the data meet the assumptions of k-means method, the clustering most of the time hits quite close to the general optimum or right on it. $\endgroup$
    – ttnphns
    Aug 7, 2019 at 5:04
  • $\begingroup$ @ttnphns: In section 2.2. of their original paper (ilpubs.stanford.edu:8090/778/1/2006-13.pdf) Arthur and Vassilvitskii denote with "k-means++" the combination of their proposed initialization method and the normal k-means algorithm. $\endgroup$
    – Barden
    Aug 7, 2019 at 12:11
  • $\begingroup$ @ttnphns: thks for commenting. Granted, k-means++ works near-optimally e.g. if you have 100 Gaussian well-separated clusters of identical variance in your data and choose k=100. In general, however, you do not know the appropriate value of k and if you choose e.g. k=400 for the above data set you will end up likely with most clusters having 4 centroids, but also several clusters having 3 centroids and others having 5 centroids whereas the optimal solution w.r.t. the above error function would be 4 centroids in each cluster. Try it out. $\endgroup$
    – Barden
    Aug 7, 2019 at 12:24
  • $\begingroup$ This issue - the correct or best number of clusters/centroids k - is, methodologically, independent and different from the topic of k-means optimality. $\endgroup$
    – ttnphns
    Aug 7, 2019 at 14:18

1 Answer 1

Reset to default
1
$\begingroup$

K-means++ is one of the few approaches than can give you optimality guarantees. Please study the original paper and the work by Ostrovski et al. for details on the theoretical guarantee.

Given the NP-hardness of the problem, I doubt you'll get much better than k-means++ when it comes to efficient algorithms. So the best you can then try is running k-means++ several times to maximize your chance of finding the true optimum. Same theoretical properties, but higher chance of being better.

When you are less interested intheoretical guarantees, but practical efficiency to speed up k-means++, then use sampling. Finding even a local optimum of k-means on huge data sets is a pretty useless toy exercise for those detached from real applications. Nobody needs k-means on big data, the result is not more useful than k-means on a sample that fits on a single host (because even just 32 GB RAM can fit huge data sets, good enough for approximating k-means on any data set where it works and is useful - in particular compared to minibatch and any other approach that only finds the fix point up to a certain tolerance value...).

There are also approaches where you simply run k-means on a sample, and use this as starting point to refine on the full data set.

Improve this answer
$\endgroup$
9
  • $\begingroup$ The theoretical result says that for the error E[φ] of a solution constructed with k-means++ the following holds: E[φ]≤8(ln k + 2)φOPT with φOPT being the error of the optimal solution. For k-values of 10 and 100 resp. this says that the error obtained is not larger than 34 or 52 times the optimal error. That is not really a tight bound and I have trouble imagining problems where k-means with random initialization would produce higher errors than that. It is good to have some theoretical result at all, but I wouldn't term a solution good if its error is more than 20% away from the optimum. $\endgroup$
    – Barden
    Aug 7, 2019 at 13:25
  • $\begingroup$ Well, it's an NP-hard problem. And the mentioned work by Ostrovski may provide a lower bound. Somehow I remembered 9*OPT as a bound which is pretty good for a NP-hard problem. Because that by no means means 9*worse on an actual data set - asymptotic worst-case is completely useless for real problems. Because that is on data sets where k-means does not at all make sense to use in the first place. So unless you are stupid enough to guarantee quality as part of some SLA then you don't need to care. $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 7, 2019 at 17:56
  • $\begingroup$ There was some work probably by Ulrike Luxbourg that stated that if k-means makes sense to use then the solution space must be well-behaved enough that you are almost certain to find the true optimum with a few restarts. If the result surface is mean enough to have plenty of local optima, then k-means on this data set is useless anyway. $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 7, 2019 at 17:58
  • $\begingroup$ I found the interesting work from Ulrike von Luxburg on spectral clustering (tml.cs.uni-tuebingen.de/team/luxburg/publications/…). I am however interpreting k-means as a vector quantization method in order to have a clear measure of quality which is not so much present if you interpret k-means as a clustering method, as you also illustrate in your excellent answer to another question: stats.stackexchange.com/questions/133656/…). I agree that n*OPT for small n is good for NP-complete problems. $\endgroup$
    – Barden
    Aug 8, 2019 at 0:03
  • $\begingroup$ I am skeptical that one can establish much tighter general bounds wrt. solution quality for any algorithm since they must hold for any - also constructed - data set. I am currently working on a k-means variant which delivers better solutions than k-means++ in very many cases (and by construction never inferior solutions since it builds upon k-means++). I'll post once it is available. $\endgroup$
    – Barden
    Aug 8, 2019 at 0:12

Your Answer

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

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