Minimize distance between centroids of subsets of points

Question

In a n-dimensional space, I want to divide a set of m points into v (non-empty) subsets. I want to minimize the sum of the pairwise Euclidean distances between the centroids of the resulting subsets.

It seems to me that this is related to K-mean clustering but that in this case, I want the resulting centroids to be as close as possible from each other.

What is the correct name for this problem ? Is there a known algorithm to solve it (excluding brute force) ?

Answer 1

Actually, the k-means objective function can be written as a weighted difference between means but the task there is to maximize this weighted difference. In particular, suppose $x_1,\ldots,x_n$ are input vectors, and $n_i$, $n_j$ give the number of points in cluster $i$ and cluster $j$ (for $K$ clusters). Then, the usual k-means optimization can be written as \begin{equation*} \max\frac{1}{2n} \sum_i\sum_j n_in_j\|\mu_i - \mu_j\|^2, \end{equation*} where $\mu_i$ and $\mu_j$ are centroids of their respective clusters.

If you want the detailed derivation, have a look at these lecture notes (from 2001) of Inderjit Dhillon

Answer 2

This is just a naive heuristic, not an algorithm, analogous to $K$-means.

Let $K$ be the number of clusters (your v). Let $D(c_1,c_2,\ldots,c_K)$ be a measure of the dispersion of $K$ points $c_i$. E.g., $D(\;)$ could be the radius of the smallest enclosing sphere, or (in your case), the sum of the pairwise distances $||c_i - c_j||$.

(1) Partition the given set $S$ of points into $K$ subsets $S_1, S_2, \ldots, S_K$ with centroids $c_1,c_2,\ldots,c_K$. Use random sampling to create the initial partition. Compute $D(c_1,c_2,\ldots,c_K)$.

(2) For each pair of clusters $S_i$ and $S_j$, for each point point $p$ in each cluster, move $p$ from one cluster to the other if this decreases the dispersion of their centroids.

(3) Repeat until no further improvements are possible.

Answer 3

This is more of a comment but are you sure that this is a well-motivated problem ? Also this question is probaly not a good fit for MO (maybe stats.stack or math.stack?). What I mean is that usually if your data does not have outliers then if you just randomly sample your data you would expect all of your clusters to have mean very close to each other. For example look at this matlab code.

r=rand(1000,2); 
p=randperm(1000);
cm_k_out_of_K=@(k,K) mean(r(p(1000/K*k+1:1000/K*k+100),:));
cm_k_out_ofK(1,10)
   0.52446      0.51745
cm_k_out_ofK(2,10)
   0.50057      0.51456
disp(cell2mat(arrayfun(@(i) cm_k_out_ofK(i,10), 0:9, 'UniformOutput', false)'))
  0.48863      0.55331
  0.52436      0.51838
   0.4981      0.51501
  0.49325      0.47997
  0.52885      0.52759
  0.49473      0.51646
  0.56129       0.5826
    0.539       0.5074
  0.51717      0.49958
  0.48119      0.41474

As you can see just randomly sampling the data gives you pretty good clusters.