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 }${\displaystyle \lfloor {n \over k}\rfloor } or ${\displaystyle \lceil {n \over k}\rceil }${\displaystyle \lceil {n \over k}\rceil }, where ${\displaystyle n}${\displaystyle n} is the number of points and ${\displaystyle k}${\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}${\displaystyle n} locations with ${\displaystyle k}${\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.

• Clustering criteria