The k-means algorithm reduces to computing the objective function:

$ \underset{\textbf{S}}{\operatorname{argmax}} \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i \rVert $

for some observations $\textbf{x}_1,\ldots\textbf{x}_n$ to be partitioned into sets $\textbf{S}_i$.

How can this problem be reduced to an Integer Programming problem, which like k-means, is NP-hard.

  • 2
    $\begingroup$ k-means would be hard only if integer programming reduced to k-means, not the other way round. $\endgroup$ – David Eisenstat Sep 4 '14 at 19:13

I'm not sure if you can reduce this problem to an Integer Problem, because the centers are still continuous variables. There are ways to write equivalent Mixed-Integer Problems (i.e., both integer and continuous variables) but I struggle to formulate as a Linear one because of the Euclidean norm.

First you create a boolean variable $w_{ij}$ for assignment. $w_{ij} = 1$ means observation j belongs to cluster i (and zero means it does not belong). The following constraint ensures that one sample can only belong to one group: $$ \sum_i{w_{ij} = 1}, \forall i \in 1..k $$

You also create non-negative continuous variables $d_{ij} \geq 0$ for distances between every observation j to every center, but use the Big M method to turn this distance zero if the observation does not belong to the cluster: $$ d_{ij} \geq ||x_j - \mu_i|| - M(1 - w_{ij}) $$

To select a value of M you can find the distance between the two points that are furthest from each other, or any other bigger value. If M is big enough and j doesn't belong to i, we have $d_{ij} \geq L$ where L is negative, so the constraint is trivially satisfied - which means $d_{ij}$ can assume any value greater or equal to zero. If j does belong to i, then the minimum value for $d_{ij}$ is the euclidean distance between observation and cluster center.

(Note: you could use a multiplicative factor instead of Big M, like this: $ d_{ij} = ||x_j - \mu_i||w_{ij}$ - this is matematically accurate but generally doesn't work well in practice because it adds non-linearity. But since this norm is already non-linear, who knows?)

Now, if you minimize the distances (I saw in Wikipedia that the correct formulation tries to minimize the sum of distances), optimization will try to reduce every single value of $d_{ij}$, so they will clamp to the correct distances if j belongs to i, and to zero if j doesn not belong to i:

$$ \min{\sum_{ij}{d_{ij}}} $$

I hope that helps.


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.