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.

• If I understand you correctly, you want to match each (estimated) $k_i$ with only one (predefined) $c_j$? – chl Apr 25 '11 at 9:11
• @chi yes i wanted to have one-one mapping between estimated $k_i$ and predefined $c_j$ – 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.

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$.

• 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. – 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 -
Perry

• 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...). – whuber Apr 25 '11 at 18:15