13
$\begingroup$

I know k-means is usually optimized using Expectation Maximization. However we could optimize its loss function the same way we optimize any other!

I found some papers that actually use stochastic gradient descent for large scale k-means, but I couldn't get my question answered.

So, do anyone know why is that? Is it because Expectation Maximization converges faster? Does it has any particular guarantee? Or is it a historical reason?

$\endgroup$
6
  • $\begingroup$ The maximization step already does climb the likelihood gradient (conditional on the values chosen by the expectation step), right? $\endgroup$ Sep 4, 2013 at 22:28
  • $\begingroup$ @DavidJ.Harris I don't think that the OP is disputing that EM behaves as it does, but asking why one method seems to be widely used and another method not used so much. Your comment doesn't seem to directly address why EM might be preferred. $\endgroup$
    – Glen_b
    Sep 5, 2013 at 2:38
  • 1
    $\begingroup$ Hi @DavidJ.Harris, it is as Glen_b, I understand that both algorithms optimize either the likelihood (EM) or the log likelihood (gradient descent). After digging into google and friends, I got to this paper link whether this question is addressed. If I didn't miss understand, EM gets to a better solution than gradient descent. $\endgroup$
    – elsonidoq
    Sep 6, 2013 at 16:48
  • $\begingroup$ What is the objective function for k-means to optimize? Is it differentiable? $\endgroup$ Apr 9, 2015 at 0:42
  • 3
    $\begingroup$ It is smoothly differentiable in the parameters (cluster means) but surely not in the cluster assignments (which are multinomial indicator variables)? $\endgroup$ Mar 10, 2017 at 14:46

2 Answers 2

10
$\begingroup$

As the OP mentions, it's possible to solve k-means using gradient descent, and this may be useful in the case of large scale problems.

There are certainly historical reasons for the prevalence of EM style algorithms for solving k-means (i.e. Lloyd's algorithm). Lloyd's algorithm is so popular that people sometimes call it "the k-means algorithm", and may even be unaware that other approaches exist. But, this popularity is not undeserved.

Bottou and Bengio (1995) showed that Lloyd's algorithm is equivalent to optimizing the k-means cost function using Newton's method. In general optimization problems, second order methods like Newton's method can converge faster than first order methods like gradient descent because they exploit information about the curvature of the objective function (and first order methods don't). In an experiment on the well-known Iris dataset, they showed that Lloyd's algorithm did indeed converge faster than gradient descent. It would be interesting to see this comparison on a wider variety of datasets.

References:

Bottou and Bengio (1995). Convergence properties of the k-means algorithms.

$\endgroup$
2
$\begingroup$

K-means clustering is unsupervised, and the closest unsupervised technique which uses EM is model-based clustering (Gaussian mixture models, GMM). An annoying problem with GMM model-based clustering occurs when many of the features are correlated, which causes near-singularity in the feature-based covariance(correlation) matrix. In this situation, the likelihood function becomes unstable, with condition indexes reaching infinity, causing GMM to break down completely.

Thus, drop the idea of EM and kNN -- since it's based on covariance (correlation) matrices for unsupervised analysis. Your inquiry on optimization closely resembles Sammon mapping, and classical metric and non-metric multidimensional scaling (MDS). Sammon mapping is derivative-iterative based, while various forms of MDS are commonly iterative or one-step eigendecompositions, which can nevertheless optimize during a one-step matrix operation.

Looking again back at your request: the answer is: it's already been done in Sammon mapping.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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