Centroid matching problem 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. 
 A: 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.

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$.
A: 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. 
A: 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 -
Perry
