Feature-based Individual Fairness in k-clustering
Debajyoti Kar, Mert Kosan, Debmalya Mandal, Sourav Medya, Arlei Silva, Palash Dey, Swagato Sanyal · 2023
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 not so well-studied. We introduce a new notion of individual fairness in k-clustering based on features not necessarily used for clustering. The problem is NP-hard and does not admit a constant factor approximation. Therefore, we design a randomized heuristic algorithm. Our experimental results against six competing baselines validate that our algorithm produces individually fairer clusters than the fairest baseline.