Feature-based Individual Fairness in k-clustering

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 𝑘-clustering problem, fairness at an individual level is not so well-studied. We introduce a new notion of individual fairness in 𝑘-clustering based on features not necessarily used for clustering. The problem is NPhard 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.