Balanced clustering

Balanced clustering is a special case of clustering where, in the strictest sense, cluster sizes are constrained to ${\displaystyle \lfloor {n \over k}\rfloor }$ or ${\displaystyle \lceil {n \over k}\rceil }$, where ${\displaystyle n}$ is the number of points and ${\displaystyle k}$ is the number of clusters.^[1] A typical algorithm is balanced k-means, which minimizes mean square error (MSE). Another type of balanced clustering called balance-driven clustering has a two-objective cost function that minimizes both the imbalance and the MSE. Typical cost functions are ratio cut^[2] and Ncut.^[3] Balanced clustering can be used for example in scenarios where freight has to be delivered to ${\displaystyle n}$ locations with ${\displaystyle k}$ cars. It is then preferred that each car delivers to an equal number of locations.

There exists implementations for balanced k-means^[4] and Ncut^[5]

Levin, M. Sh. (2017). "On Balanced Clustering (Indices, Models, Examples)". Journal of Communications Technology and Electronics. 62 (12): 1506–1515. doi:10.1134/S1064226917120105. S2CID 255277095.