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

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.

• – D.W.
May 4 at 7:29

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.

• thanks. The first two answers are very well known to me. None of those actually fulfil my requirements. I need a solution that combines Answer1 and Answer2. May 3 at 17:55
• @dipaknarayanan They are already combined. I do not understand what are you are asking. May 3 at 17:57
• how are they combined? If I follow Answer1, I get $k$ number of clusters with different sizes. When I follow Elbow method, I get the optimal number of clusters. Lets say I then apply Answer1 with $k$ equal to the optimal number of clusters that I get using elbow method. Will these $k$ clusters follow the constraints that I have for min and maximum cluster sizes? May 3 at 18:04
• @dipaknarayanan Let us forget Answer 1 since it might not satisfy cluster constraints. Now, we want to combine A2 and A3. You just need to run A3 for different values of $k$. And when $k$-means cost starts to appear constant; that is your desired value of $k$.. May 3 at 18:08
• @dipaknarayanan Technically speaking, there is nothing like "optimal value of $k$" since the $k$-means cost always decreases with increasing value of $k$. For example: set $k = n$. The optimal clustering would assign single point to each cluster and the $k$-means cost would be $0$. And, that does not make sense for unconstrained version May 3 at 18:16

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

• thanks a lot for your answer. Looks very interesting. Would you please provide a full mathematical formulation with objective and constraints. Is it easy to solve? May 4 at 7:26