Feature-based Individual Fairness in k-Clustering
It addresses individual fairness in clustering, an underexplored area, but is incremental as it builds on existing fairness constraints.
The paper tackles the problem of ensuring individual fairness in k-clustering by introducing a new notion based on features not used for clustering, showing it is NP-hard with no constant factor approximation, and presents a randomized algorithm that improves fairness by 12.5% and reduces clustering cost by 34.5% compared to baselines.
Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. While there have been several attempts to capture group fairness in the $k$-clustering problem, fairness at an individual level is relatively less explored. We introduce a new notion of individual fairness in $k$-clustering based on features not necessarily used for clustering. We show that this problem is NP-hard and does not admit a constant factor approximation. Therefore, we design a randomized algorithm that guarantees approximation both in terms of minimizing the clustering distance objective and individual fairness under natural restrictions on the distance metric and fairness constraints. Finally, our experimental results against six competing baselines validate that our algorithm produces individually fairer clusters than the fairest baseline by 12.5% on average while also being less costly in terms of the clustering objective than the best baseline by 34.5% on average.