Fair-Capacitated Clustering
  Traditionally, clustering algorithms focus on partitioning the data into
groups of similar instances. The similarity objective, however, is not
sufficient in applications where a fair-representation of the groups in terms
of protected attributes like gender or race, is required for each cluster.
Moreover, in many applications, to make the clusters useful for the end-user, a
balanced cardinality among the clusters is required. Our motivation comes from
the education domain where studies indicate that students might learn better in
diverse student groups and of course groups of similar cardinality are more
practical e.g., for group assignments. To this end, we introduce the
fair-capacitated clustering problem that partitions the data into clusters of
similar instances while ensuring cluster fairness and balancing cluster
cardinalities. We propose a two-step solution to the problem: i) we rely on
fairlets to generate minimal sets that satisfy the fair constraint and ii) we
propose two approaches, namely hierarchical clustering and partitioning-based
clustering, to obtain the fair-capacitated clustering. The hierarchical
approach embeds the additional cardinality requirements during the merging step
while the partitioning-based one alters the assignment step using a knapsack
problem formulation to satisfy the additional requirements. Our experiments on
four educational datasets show that our approaches deliver well-balanced
clusters in terms of both fairness and cardinality while maintaining a good
clustering quality.
