'''Balanced clustering''' is a special case of [[Cluster analysis|clustering]], where, in the strictest sense, the cluster sizes are constrained to <math>\lfloor {n\over k}\rfloor</math> or <math>\lceil{n \over k}\rceil</math>, where <math>n</math> is the number of points and <math>k</math> is the number of clusters.<ref>{{Cite journal|last=M. I. Malinen and P. Fränti|first=|date=August 2014|title=Balanced k-Means for Clustering|url=|journal=Joint Int. Workshop on Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2014), LNCS 8621|doi=|pmid=|access-date=}}</ref> ThisA typetypical of balanced clusteringalgorithm is calledbalanced balance[[K-constrainedmeans clustering. Typical algorithm is Balanced |k-Meansmeans]], which minimizes [[Mean squared error|mean square error (MSE)]]. There is also anotherAnother type of balanced clustering, it is called balance-driven clustering.Inhas ita thetwo-objective cost function is two-objective that minimizes both the imbalance and the MSE. Typical cost functions are Ratioratio cut<ref>{{Cite journal|last=L. Hagen and A. B. Kahng|first=|date=1992|title=New spectral methods for ratio cut partitioning and clustering|url=|journal=IEEE Transactions on Computer-Aided Design|doi=|pmid=|access-date=}}</ref> and Ncut.<ref>{{Cite journal|author=J. Shi and J. Malik|first=|date=2000|title=Normalized cuts and image segmentation|url=|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|doi=10.1109/34.868688}}</ref>▼
{{Underlinked|date=March 2016}}
▲Balanced clustering is a special case of [[Cluster analysis|clustering]], where in the strictest sense, the cluster sizes are constrained to <math>\lfloor {n\over k}\rfloor</math> or <math>\lceil{n \over k}\rceil</math>, where <math>n</math> is the number of points and <math>k</math> is the number of clusters.<ref>{{Cite journal|last=M. I. Malinen and P. Fränti|first=|date=August 2014|title=Balanced k-Means for Clustering|url=|journal=Joint Int. Workshop on Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2014), LNCS 8621|doi=|pmid=|access-date=}}</ref> This type of balanced clustering is called balance-constrained clustering. Typical algorithm is Balanced k-Means, which minimizes [[Mean squared error|mean square error (MSE)]]. There is also another type of balanced clustering, it is called balance-driven clustering. In it the cost function is two-objective that minimizes both imbalance and MSE. Typical cost functions are Ratio cut<ref>{{Cite journal|last=L. Hagen and A. B. Kahng|first=|date=1992|title=New spectral methods for ratio cut partitioning and clustering|url=|journal=IEEE Transactions on Computer-Aided Design|doi=|pmid=|access-date=}}</ref> and Ncut.<ref>{{Cite journal|author=J. Shi and J. Malik|first=|date=2000|title=Normalized cuts and image segmentation|url=|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|doi=10.1109/34.868688}}</ref>
== Software ==
There exists implementations for Balancednalanced k-Meansmeans<ref>{{Cite web|url=http://cs.uef.fi/sipu/soft/Balanced.zip|title=Balanced k-Means implementation|last=M. I. Malinen and P. Fränti|first=|date=|website=|publisher=University of Eastern Finland|access-date=}}</ref> and Ncut<ref>{{Cite web|url=http://www.cis.upenn.edu/~jshi/software/|title=Ncut implementation|last=T. Cour, S. Yu and J. Shi|first=|date=|website=|publisher=University of Pennsylvania|access-date=}}</ref>
