Find the optimal set of subsets

Question

Consider a set of $N$ individuals and let their distance be given by $R$, a $N\times N$ matrix. In that, $R(1,2)$ is the distance between individual 1 and 2. Now lets say that I want to separate the individuals into $k$ subsets (or clusters) such that the distance between individuals in each subset is the minimum possible.

For instance, lets assume that $N=5$, $k=3$ and $R$ is

0.00000 0.56570 0.93140 0.98990 0.98990
0.56570 0.00000 0.84850 0.64850 0.98990
0.93140 0.84850 0.00000 0.78990 1.13140
0.98990 0.64850 0.78990 0.00000 0.93140
0.98990 0.98990 1.13140 0.93140 0.00000

One possible solution is $S_1=\{ \{1,2,3\}, \{4\}, \{5\} \}$ where subset 1 is $\{1,2,3\}$, subset 2 is $\{4\}$ and subset 3 is $\{5\}$. In this case the total distance is given by \begin{equation} R(1,2)+R(1,3)+R(2,3)=2.3456. \end{equation} In the above, consider that the distance for subsets $\{4\}$ and $\{5\}$ is zero since there is only one individual in each of these subsets. Although $S_1$ is a feasible solution, it is not the optimal one. The optimal solution in this case is $S_2=\{ \{1,2,4\}, \{3\}, \{5\} \}$ since the total distance is \begin{equation} R(1,2)+R(1,4)+R(2,4)=2.2041, \end{equation} which is lower than that given by $S_1$.

Is it possible to formulate this problem as a clustering problem where k is the number of clusters? Could I apply k-means? If so, what should the centroid be?

Alternatively, I have been trying to formulate this problem as integer programming problem. In that, there is $N$ integer variables bounded by $k$. A solution can then be represented by $X=[X_1\ldots X_N]$ and the variables can only take values as give by $X_i \in \{1,...,k\}$, for $i=1,...N$. For the above problem, the optimal solution is given by $X=[1~1~2~1~3]$, which means that individual 1 corresponds to subset 1, individual 2 corresponds to subset 1, individual 3 corresponds to subset 2, individual 4 corresponds to subset 1, and individual 5 corresponds to subset 3. The objective function can be formulated as minimize the sum of all distances between individuals that belong to the same subset, for all subsets. One constraint for this problem is that all subsets (or clusters) need to have at least one individual. For instance, for $k=3$ the solution $X=[1~1~1~1~1]$ is unfeasible because subset 2 and subset 3 have no individuals. I think this is an NP-hard problem and it will take long for an optimization method to find the optimal solution if $N$ increases beyond some threshold.

Therefore, I was thinking that formulating this problem as a clustering problem should be more appropriate. Any ideas on this?

Answer 1

I quote from Garey & Johnson, Computers and Intractability, page 281. In the list of NP-complete problems, we find

Clustering

Instance: Finite set $X$, a distance $d(x,y)\in Z_0^+$ for each pair $x,y\in X$, and two positive integers $K$ and $B$.

Question: Is there a partition of $X$ into disjoint sets $X_1,X_2,\dots,X_k$ such that, for $1\le i\le k$ and all pairs $x,y\in X_i$, $d(x,y)\le B$?

[I think $K$ and $k$ are supposed to be the same symbol.]

Comment: Remains NP-complete even for fixed $K=3$ and all distances in $\{0,1\}$.

I hope this helps.

Answer 2

For your problem, where the relations between objects are specified via a distance matrix, the formulation of Correlation Clustering, seems to be more appropriate. Here you do not need to pick $k$ in advance. Also, the version of relevance is the weighted version. Chasing that paper and the keyword, you'll find a lot of relevant literature for this version of the problem.