Abstract
This study investigates a general variational formulation of fair clustering,which can integrate fairness constraints with a large class of clusteringobjectives. Unlike the existing methods, our formulation can impose any desired(target) demographic proportions within each cluster. Furthermore, it enablesto control the trade-off between the fairness and clustering terms. We derivean auxiliary function (tight upper bound) of our KL-based fairness penalty viaits concave-convex decomposition and Lipschitz-gradient property. Our upperbound can be optimized jointly with various clustering objectives, includingprototype-based, such as K-means and K-median, or graph-based such asNormalized Cut. Interestingly, at each iteration, our general fair-clusteringalgorithm performs an independent update for each assignment variable, whileguaranteeing convergence. Therefore, it can be easily distributed forlarge-scale data sets. Such scalability is important as it enables to exploredifferent trade-off levels between the fairness and clustering objectives.Unlike fairness-constrained spectral clustering, our formulation does not needstoring an affinity matrix and computing its eigenvalue decomposition. We showthe effectiveness, flexibility and scalability of our approach throughcomprehensive evaluations and comparisons to the existing methods over severaldata sets.