# Graph clustering for balanced sum of absolute deviations within each cluster (same sum of intracluster distances)

I'm given a set of points and a distance matrix. With these I'm trying to develop an algorithm similar to k-means that tries to minimize the sum of distances from each cluster datapoint to it's center with the restriction that every cluster should have more or less the same value (I'm not using "size" because that most often refers to number of datapoints in a cluster instead of sum of center distances).

K-means aims at minimizing the sum of squared intracluster distances. Instead we care about minimizing the sum of (linear) intracluster distances (under the mentioned restriction). For that I'm not using the arithmetic mean of datapoints to find the new cluster center, but find the datapoint within a cluster with the minimum sum of distances to other points in this cluster (using the distance matrix). We can do this because there is a theorem stating that the edgepoint with minimal average distance to all vertices on a graph is itself a vertex. Now the problem is that this algorithm does not follow the goal of same distance sums for each cluster.

In short: let $$S_i$$ be the clusters and $$\mu_i$$ their center. I'm trying to minimize $$J := \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|$$ with the restriction: $$\forall i \in \{1,2,\dots,k\}:\; \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\| \approx \frac J k$$

Does anyone know of an algorithm or a paper that discusses the problem of same sized clusters in terms of distance sums but not in terms of number of datapoints?

I read about so-called "MinMax k-means clustering" but I doubt it solves our problem since minmax's goal is minimzing the biggest sum of intracluster distances. However I think it could be a first idea.

• Isn't PAM and k-medoids more related than k-means? – Erich Schubert Apr 12 '19 at 15:47