# Feature-based Individual Fairness in k-Clustering

arXiv: https://arxiv.org/abs/2109.04554 · HTML: https://mlsanity.com/paper/2109.04554/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 51 references that are in the map.
- First posted on arXiv 9 Sep 2021.

## Builds on (most cited first, 24 of 24)

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees](https://mlsanity.com/paper/1806.06055/) (2018)
- [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Fairness in representation: quantifying stereotyping as a representational harm](https://mlsanity.com/paper/1901.09565/) (2019)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Fair Coresets and Streaming Algorithms for Fair k-Means Clustering](https://mlsanity.com/paper/1812.10854/) (2018)

## Built on by (most cited first, 4 of 4)

- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Personalized Reinforcement Learning with a Budget of Policies](https://mlsanity.com/paper/2401.06514/) (2024)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)

## Abstract (arXiv)

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.