Individual Fairness for $k$-Clustering

Abstract

We give a local search based algorithm for $k$-median and $k$-means (and more generally for any $k$-clustering with ${\ell }_p$ norm cost function) from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. An individually fair clustering provides such a guarantee for every point $x\in P$. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible $k$-clustering with respect to this fairness condition. In this work, we show how to get a bicriteria approximation for fair $k$-clustering: The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor). Further, we complement our theoretical bounds with empirical evaluation.

arXiv commentICML 2020

References in corpus (10)

• Equality of Opportunity in Supervised Learning
• The Frontiers of Fairness in Machine Learning
• Clustering without Over-Representation
• Scalable Fair Clustering
• Coresets for Clustering with Fairness Constraints
• Guarantees for Spectral Clustering with Fairness Constraints
• Proportionally Fair Clustering
• Fairness in Clustering with Multiple Sensitive Attributes
• Rényi Fair Inference
• A Center in Your Neighborhood: Fairness in Facility Location

Cited by in corpus (12)

• A survey on datasets for fairness-aware machine learning
• Learning Certified Individually Fair Representations
• Explainable $k$-Means and $k$-Medians Clustering
• ExKMC: Expanding Explainable $k$-Means Clustering
• A Notion of Individual Fairness for Clustering
• Distributional Individual Fairness in Clustering
• Approximation Algorithms for Socially Fair Clustering
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
• Improved Approximation Algorithms for Individually Fair Clustering
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center
• Fair Clustering Under a Bounded Cost