Abstract: Algorithmic fairness in clustering aims to balance the proportions of instances assigned to each cluster with respect to a given sensitive attribute.While recently developed fair clustering algorithms optimize clustering objectives under specific fairness constraints, their inherent complexity or approximation often results in suboptimal clustering utility or numerical instability in practice.To resolve these limitations, we propose a new fair clustering algorithm based on a novel decomposition of the fair $K$-means clustering objective function.The proposed algorithm, called Fair Clustering via Alignment (FCA), operates by alternately (i) finding a joint probability distribution to align the data from different protected groups, and (ii) optimizing cluster centers in the aligned space.A key advantage of FCA is that it theoretically guarantees approximately optimal clustering utility for any given fairness level without complex constraints, thereby enabling high-utility fair clustering in practice.Experiments show that FCA outperforms existing methods by (i) attaining a superior trade-off between fairness level and clustering utility, and (ii) achieving near-perfect fairness without numerical instability.

Lay Summary:

(1) Fair clustering aims to balance cluster proportions by a sensitive attribute, but inherent complexity or approximation of existing methods often yields suboptimal utility or numerical instability.(2) We propose Fair Clustering via Alignment (FCA), which optimizes (i) a joint probability distribution to align data from different protected groups and (ii) cluster centers in the aligned space.(3) FCA guarantees approximately optimal clustering utility for any given fairness level without complex constraints and outperforms existing methods in the trade‐off between fairness and utility.