A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
This addresses fairness issues in applications like loan approvals and ad recommendations, but it is incremental as it builds on existing fair clustering methods with a hybrid approach.
The paper tackles the problem of unfairness in clustering for human-centric decision systems by balancing clustering cost and demographic group representation, proposing a stochastic alternating balance fair k-means algorithm that efficiently constructs high-quality Pareto fronts on synthetic and real datasets.
In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups across the clusters, leading to a bi-objective optimization problem that is nonconvex and nonsmooth. To determine the complete trade-off between these two competing goals, we design a novel stochastic alternating balance fair $k$-means (SAfairKM) algorithm, which consists of alternating classical mini-batch $k$-means updates and group swap updates. The number of $k$-means updates and the number of swap updates essentially parameterize the weight put on optimizing each objective function. Our numerical experiments show that the proposed SAfairKM algorithm is robust and computationally efficient in constructing well-spread and high-quality Pareto fronts both on synthetic and real datasets.