Optimal clustering with optimal number of clusters as well as max and min cluster size constraints

Question

I need to cluster $N$ data points.

I don't know the number of clusters to be formed. It needs to be found optimally.

Also, there is maximum and minimum cluster size constraints, where $C_{\max}$ is the maximum size that one cluster can get and $C_{\min}$ is the minimum size that one cluster must get.

The coordinates of the $N$ data points are stored in a matrix $D\in\mathbb{R}^{2\times N}$, $D$ is a matrix of $N$ rows and each row has two elements defining the $x-$axis and $y-$axis coordinates. However, $D$ can be expressed in any convenient form, for example, $D\in\mathbb{R}^{N\times 2}$ or $D\in\mathbb{C}^{N\times 1}$ (where the coordinates are expressed as a complex number: $x+iy$)

How can I formulate this as a mathematical optimization problem and solve it efficiently?

Data points can be uniformly distributed over a 2D plan of any given size.

Answer 1

Answer 1. There are various clustering algorithms depending on different requirements. You can employ $k$-means clustering method since it is fast, simple, and popular.

Answer 2. If you do not know the number of clusters, employ Elbow method. That is, first cluster the data for $k = 1$. Then cluster the data with $k = 2$, then $k = 3$ and so on. Initially, the cost of the clustering will decrease rapidly with increase in $k$. Once the $k$-means cost starts to appear constant with increase in $k$; that value of $k$ is the desired number of clusters.

Answer 3. When there are constraints on the size of clusters, the problem is (informally) known as the balanced clustering problem or capacitated clustering problem. The Wikipedia article does contain a few links of its implementation. This is a research paper for the balanced $k$-means problem. You might have to do some more research on this topic to find the perfect answer as per your requirement.

---

Note: The clustering problem that minimizes the $k$-means objective is $\mathsf{NP}$-hard. Therefore, you can expect to find an optimal solution to your problem in polynomial time.

Answer 2

One possible approach is to use agglomerative clustering, merging clusters until you get something whose size is in the acceptable range.

If you prefer to use optimization, another possible approach is to define an objective function $\Phi$ that measures the quality of a clustering, as a sum of two terms: $$\Phi = L + P$$ where $L$ measures how tightly coupled the clusters are (it might be any standard objective function for clustering, e.g., sum of pairwise squared distances between pairs of points in the same cluster, as in k-means clustering), and $P$ is a penalty term that measures whether the cluster sizes are as desired (e.g., $P = \max(\ell-s,0)^2 + \max(s-u,0)^2$, where $s$ is the size of an individual cluster and $\ell,u$ are the desired minimum and maximum cluster sizes). This is basically applying the penalty method for constrained optimization. As an alternative, you could use the barrier method instead of the penalty method, which would involve replacing $P$ with a barrier function that becomes infinite once the cluster size is too big or too small (e.g., $P = b_u(x) + b_{-\ell}(-x)$ where $b_u(x) = -\log(u-x)$ if $x < u$ or $b_u(x) = +\infty$ if $x \ge u$).