Efficient Algorithms For Fair Clustering with a New Fairness Notion
This work addresses scalability and optimality issues in fair clustering for applications requiring equitable representation of protected attributes, though it is incremental as it builds on existing fairness notions.
The paper tackles the problem of fair clustering by introducing a new fairness notion called $\tau$-fair fairness, which generalizes existing balance properties and allows for a fine-grained trade-off between clustering efficiency and fairness. The proposed greedy round-robin algorithms achieve this trade-off efficiently, with experimental results showing they outperform state-of-the-art methods, particularly for large numbers of clusters.
We revisit the problem of fair clustering, first introduced by Chierichetti et al., that requires each protected attribute to have approximately equal representation in every cluster; i.e., a balance property. Existing solutions to fair clustering are either not scalable or do not achieve an optimal trade-off between clustering objective and fairness. In this paper, we propose a new notion of fairness, which we call $tau$-fair fairness, that strictly generalizes the balance property and enables a fine-grained efficiency vs. fairness trade-off. Furthermore, we show that simple greedy round-robin based algorithms achieve this trade-off efficiently. Under a more general setting of multi-valued protected attributes, we rigorously analyze the theoretical properties of the our algorithms. Our experimental results suggest that the proposed solution outperforms all the state-of-the-art algorithms and works exceptionally well even for a large number of clusters.