To this end, we propose a new problem, the so-called fair-capacitated clustering that ensures fairness and balanced cardinalities of the resulting clusters. We decompose the problem into two subproblems: i) the fairness-requirement compliance step that preserves fairness at a minimum threshold of balance score
and ii) the capacity-requirement compliance step that ensures clusters of comparable sizes.
For the first step, we generate fairlets [1]}, which are minimal sets that satisfy fair representation w.r.t. a protected attribute while approximately preserving the clustering objective. For the second step, we propose two solutions for two different clustering types, namely hierarchical and partitioning-based clustering, that consider the capacity constraint during the merge step (for the hierarchical approach) and during the assignment step (for the partitioning approach). Experimental results, on four real datasets from the education domain, show that our methods result in fair and capacitated clusters while preserving the clustering quality.
