1
$\begingroup$

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $P_1, P_2, \dots, P_N$ in $\mathbb{R}^d$, the problem is to find $K$ centres $Q_1, Q_2, \dots, Q_K$ (in $\mathbb{R}^d$) and assign the points to the centres with indicator-variables $\left\{x_{nk}, \, n=1, \dots,N, \,k=1,\dots,K\right\}$, so that this problem is minimized: $$\min\sum_{n=1}^N\sum_{k=1}^K x_{nk}\left\| P_n-Q_k\right\|^2_2 \\ \text{s.t. } \sum_{k=1}^K x_{nk} = 1, \; n=1, \dots, N \\ x_{nk} \in \left\{0, 1\right\}, \; Q_k \in \mathbb{R}^d $$ k-means problem can be reformulated the following way: $$ \min\sum_{n=1}^N d_n \\ \text{s.t. } \\ \left\|P_1-Q_k\right\|_2^2 \leq d_1 + (1-x_{1k})M, \quad k=1,\dots,K, \\ \left\|P_2-Q_k\right\|_2^2 \leq d_2 + (1-x_{2k})M, \quad k=1,\dots,K,\\ \dots \\ \left\|P_N-Q_k\right\|_2^2 \leq d_N + (1-x_{Nk})M, \quad k=1,\dots,K $$ Here $M$ is a sufficiently large constant. In the thesis I have read, this is called ``the big-M technique''.

The above problem is a MIQCP (mixed-integer-quadratically-constrained-programming) problem and could be approached with, for example, gurobi.

I wonder who should be addressed (as a reference) to be the first one who has come up with such problem formulation.

$\endgroup$

1 Answer 1

0
$\begingroup$

From your question, I can't tell if you're asking about the origin of big-M constraints or the origin of k-means via MIP. I'm going to assume that you mean the latter, and it's a deep hole. The paper that you referenced is not nearly sufficient. Here is some more to read to get history and context on this topic:

  1. "APPROXIMATING K-MEANS-TYPE CLUSTERING VIA SEMIDEFINITE PROGRAMMING" by Peng and Wei.
  2. "The ratio-cut polytope and K-means clustering" by Rosa and Khajavirad. And they have a follow-up paper on that.
$\endgroup$
1
  • $\begingroup$ thank you for the reply. I was actually interested about the origins of big-M MIQCP formulation. I know that it is possible to formulate k-means problems alternatively, e.g., using the work by Peng and Wei, which I am actually familiar with, but I am particularly interested in MIQCP formulation as presented in the question, because Peng's approach cannot be applied in my situation. The second reference I have not studied, I will take a look, thank you. I agree that the thesis I have referenced is very basic one, but it is a good start in my opinion to get an overview of the formulation. $\endgroup$
    – MindaugasK
    Commented Jun 28 at 8:25

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.