16
$\begingroup$

I read that the k-means algorithm only converges to a local minimum and not to a global minimum. Why is this? I can logically think of how initialization could affect the final clustering and there is a possibility of sub-optimum clustering, but I did not find anything that will mathematically prove that.

Also, why is k-means an iterative process? Can't we just partially differentiate the objective function w.r.t. to the centroids, equate it to zero to find the centroids that minimizes this function? Why do we have to use gradient descent to reach the minimum step by step?

$\endgroup$
  • 4
    $\begingroup$ When a smooth function has multiple local minima, then necessarily each one of them will be a critical point (where all the partial derivatives vanish), so your algorithm is correct but typically it's useless: you can get a horribly complicated equation with a huge number of solutions (even infinitely many). But there's another issue: how do you know the k-means objective function is even differentiable everywhere? $\endgroup$ – whuber Jan 29 '13 at 8:37
  • 1
    $\begingroup$ I believe that when I partially differentiate the objective function with respect to one centroid, the points in the cluster of another centroid vanish in the derivative. So, the centroid we can get will minimize only the sum of squared distances of only the particular cluster. $\endgroup$ – Prateek Kulkarni Jan 30 '13 at 9:28
  • 3
    $\begingroup$ That's partly it, but does not really explain the behavior. Of more import is the fact that the assignment of points to centroids is the big part of what k-means is doing. (Once the assignment is made, the centroids are easily computed and there's nothing left to do.) That assignment is discrete: it's not something that can be differentiated at all. Moreover, it's combinatorially complex: there are $O(n^k)$ ways to assign $n$ points to $k$ clusters. Indeed, it's completely unnecessary to use gradient descent to find the centroids. $\endgroup$ – whuber Jan 30 '13 at 14:31
  • $\begingroup$ I agree, the assignment part cannot be directly put into the mathematical form. Only by this isolated step can we move the centroids around to minimize the function. Here's how I look at gradient descent: If, by bad initialization, we are near the local minima, the gradient descent will drag you down to local minima. If you are near the global minima by good initialization, it will drag you down the global minima. But how this movement is mapping to cluster assignments is a blur. $\endgroup$ – Prateek Kulkarni Jan 31 '13 at 6:10
  • $\begingroup$ The non-differentiability is overrated: Leon Bottou has done some work on estimating K-Means with stochastic gradient descent on very large data sets with quite some success. The non-differentiability does not pose such a big problem there as in many problems due to the many data points. (e.g. convolutional networks are also locally non-differentiable but work great anyway, so are many neural net architectures with the rectified linear transfer function). The real reason here is the multiple minima. $\endgroup$ – bayerj Feb 19 '13 at 20:38
9
$\begingroup$

You can see k-means as a special version of the EM algorithm, which may help a little.

Say you are estimating a multivariate normal distribution for each cluster with the covariance matrix fixed to the identity matrix for all, but variable mean $\mu_i$ where $i$ is the cluster's index. Clearly, if the parameters $\{\mu_i\}$ are known, you can assign each point $p$ its maximum likelihood cluster (ie. the $\mu_i$ for which the distance to $p$ in minimal). The EM algorithm for this problem is almost equivalent to k-means.

The other way around, if you know which points belong to which cluster, you can estimate the optimal $\mu_i$. The closed form solution to this (which finds a global optimum) basically says that to find the maximum likelihood models $\{\hat\mu_i\}$ you integrate over all possible assignments of points to clusters. Since even with just thirty points and two clusters, there are about a billion such possible assignments, this is unfeasible to calculate.

Instead, we can take some guess as to the hidden parameters (or the model parameters) and iterate the two steps (with the posibility of ending up in a local maximum). If you allow each cluster to take a partial responsibility for a point, you end up with EM, if you just assign the optimal cluster, you get k-means.

So, executive summary: in probabilistic terms, there is a global solution, but it requires you to iterate over all possible clusterings. Clearly if you have an objective function, the same is true. You could iterate over all solutions and maximize the objective function, but the number of iterations is exponential in the size of your data.

$\endgroup$
  • $\begingroup$ Well put! I'll mark this as the answer! $\endgroup$ – Prateek Kulkarni Feb 19 '13 at 10:54
4
$\begingroup$

This is the problem that you want to solve: \begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - c_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ & c_j\textit{ is the centroid of cluster j}\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ \end{align}

The binary variable $x_{ij}$ indicates whether or not point $i$ is assigned to cluster $j$. Symbols $p_i$ and $c_j$ denote the coordinates of $i$th point and centroid of $j$th cluster, respectively. They are both located in $\mathbb{R}^d$, where $d$ is the dimensionality of data points.

The first group of constraints say that each point should be assigned to exactly one cluster. The second group of constraints (which we have not defined mathematically) say that the coordinates of centroid of cluster $j$ actually depend on values of $x_{ij}$ variables. We can for example express this constraint as follows: \begin{equation} c_j = \frac{\sum_{i} x_{ij} p_{ij}}{\sum_{i} x_{ij}} \end{equation}

However, instead of dealing with these non-linear constraints, in K-Means we (approximately) solve a different problem which has the same optimal solution as our original problem: \begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - y_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ &y_j \in \mathbb{R}^d \quad \forall j \end{align}

Instead of minimizing the distance to centroids, we minimize the distance to just any set of points that will give a better solution. It turns out that these points are exactly the centroids.

Now to solve this problem, we iterate in steps 2-3 of this algorithm, until convergence:

  1. Assign some values to $y_j$ variables
  2. Fix the values for $y_{j}$ variables and find the optimal values for $x_{ij}$ variables.
  3. Fix the values of $x_{ij}$ variables, and find the optimal values for $y_{j}$ variables.

In each step the objective function improves (or remains the same when the algorithm converges), since the solution found in the previous step is in the search space of current step. However, since we are fixing some of the variables in each step, this is a local search procedure which does not guarantee optimality.

Luckily, the optimization problems in steps 2 and 3 can be solved in closed form. If we know $x_{ij}$ (i.e. if we know to which cluster each point is assigned), the best values for $y_j$ variables are the centroids of clusters. If we know values for $y_j$, obviously best choice for $x_{ij}$ variables is to assign each point to the closest $y_j$.

$\endgroup$
2
$\begingroup$

A simple example might help..

Let us define the set of points to be clustered as A = {1,2,3,4}.

Say you're trying to find 2 appropriate clusters for A (2-means). There are (at least) two different settings which satisfy the stationary condition of k-means.

Setting 1:

Center1 = 1, Cluster1 = {1}
Center2 = 3, Cluster1 = {2,3,4}

Here the objective is 2. As a matter of fact this is a saddle point (try center1 = 1 + epsilon and center1 = 1 - epsilon)

Setting 1:

Center1 = 1.5, Cluster1 = {1,2}
Center2 = 3.5, Cluster1 = {3,4}

here the objective is 1/4.

If k-means would be initialized as the first setting then it would be stuck.. and that's by no means a global minimum.

You can use a variant of previous example to create two different local minima. For A = {1,2,3,4,5}, setting cluster1={1,2} and cluster2={3,4,5} would results in the same objective value as cluster1={1,2,3} and cluster2={4,5}

Finally, what would happen if you choose

A = {1,2,3,4,6}
center1={2.5} cluster1={1,2,3,4} and 
center1={6} cluster1={6}

vs

center1={2} cluster1={1,2,3} and 
center1={5} cluster1={4,6}

?

$\endgroup$
0
$\begingroup$

[This was before @Peter answered]
After a small discussion (in the comments section), I feel I have to answer my own question.

I believe that when I partially differentiate the objective function with respect to one centroid, the points in the cluster of another centroid vanish in the derivative. So, the centroid we can get will minimize only the sum of squared distances of only the particular cluster.

@whuber adds:

That's partly it, but does not really explain the behavior. Of more import is the fact that the assignment of points to centroids is the big part of what k-means is doing. (Once the assignment is made, the centroids are easily computed and there's nothing left to do.) That assignment is discrete: it's not something that can be differentiated at all.

It would be awesome if anybody has more to add.

$\endgroup$
0
$\begingroup$

Everybody has explained everything, but I would like to add that if a sample data is not distributed as a Gaussian distribution then it can stuck to a local minima. In the K-means algorithm we are actually trying to get that.

$\endgroup$
  • $\begingroup$ Rather than Gaussian, I think you mean “unimodal” $\endgroup$ – Peter Leopold Mar 1 at 14:01

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.