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.