For a Dataset $D$, we have gold standard centroids say $c_1, c_2, \cdots, c_n$. Now if we run k-means algorithm on $D$ with input $n$, we get k-means centroid $k_1, k_2, \cdots, k_n$.

I just wanted to know, is there any algorithm/heuristic to match the centroids between $k_i$ and $c_j$ where $i, j= 1, \cdots, n$ (One to one mapping between $k$'s and $c$'s)

I tried to calculate the pairwise distance between $k_p$ and $c_j,\; j= 1, \cdots, n$, and match $k_p$ to $c_r$ where the distance between them is minimum. But in this case $k_p$ and $k_q$ are assigned to $c_r$, which we dont need.

  • $\begingroup$ If I understand you correctly, you want to match each (estimated) $k_i$ with only one (predefined) $c_j$? $\endgroup$ – chl Apr 25 '11 at 9:11
  • $\begingroup$ @chi yes i wanted to have one-one mapping between estimated $k_i$ and predefined $c_j$ $\endgroup$ – Learner Apr 25 '11 at 9:17

Because K-means minimizes variances, a good criterion is to minimize the sum of squared distances between the pairs of points.

This is an integral (0/1) linear program. Specifically, the pairing can be specified by a matrix $\Lambda = (\lambda_{ij})$ where $\lambda_{ij} = 1$ if $c_i$ is paired with $k_j$ and $\lambda_{ij}=0$ otherwise. We seek to minimize

$$\sum_{i,j}\lambda_{ij}|c_i - k_j|^2$$

subject to the constraints (which enforce the one-to-one pairing)

$$\sum_{j}\lambda_{ij}=1$$ $$\sum_{i}\lambda_{ij}=1$$ $$\lambda_{ij} \in\{0,1\}.$$

Provided the centroids do not number more than a few hundred, this is quickly solved. (The matrices involved in setting up the problem will quickly exhaust RAM with more than a few hundred centroids, because they scale as $O(n^3)$, and then you might have to be a little fussier with the programming.) For instance, Mathematica 8's `LinearProgramming' function takes no measurable time with fewer than $n=20$ centroids, escalating to about 5 seconds with 400 centroids.

Solution with 20 points

By means of line segments to show the pairings, this figure depicts an optimal solution with $n=20$ bivariate normal centroids $c_i$ and independent bivariate normal K-means solutions $k_i$.

  • $\begingroup$ If you look closely at the figure (about one-third from the left) you can see where the minimum-distance heuristic is clearly violated. The trick is to keep the largest distances pretty small. Note, too, that this formulation is insensitive to the dimension of the original K-means problem: all that matters are the mutual distances between the two sets of coefficients. $\endgroup$ – whuber Apr 25 '11 at 17:58

The problem you're trying to solve is a min-cost matching problem, specifically the problem of minimizing the functional

$F(\pi) = \sum_i \|c_i - k_{\pi(i)}\|^2 $

where $\pi$ is over all permutations in $S_n$.

This can be solved by the Hungarian algorithm (which is a primal-dual method in disguise) and takes $n^3$ time.


Sounds like you might want to consider using/writing an energy function. More here: http://en.wikipedia.org/wiki/Optimization_%28mathematics%29#Multi-objective_optimization

I suppose if your number of k centroids is "small" you can run a distance function for all c k pairings and select the set which minimizes total distance as the 'best' solution.
Hope that helps -

  • $\begingroup$ Thanks for your contribution. It leaves some questions hanging, though: (a) In what sense do you see this as a multi-objective optimization problem? (b) What do you specifically propose as the "energy" to minimize? (c) Because there are $n!$ possible pairings, an exhaustive search will be prohibitively long once $n$ is much larger than $13$ or so (at which point there are over 6 billion pairings to examine...). $\endgroup$ – whuber Apr 25 '11 at 18:15

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.