# A Computational Approach to Improving Fairness in K-means Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 29 May 2025.

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

- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making](https://mlsanity.com/paper/1806.04959/) (2018)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [K-nearest Neighbor Search by Random Projection Forests](https://mlsanity.com/paper/1812.11689/) (2018)
- [Group Fairness in Committee Selection](https://mlsanity.com/paper/1905.04438/) (2019)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Hiring Under Uncertainty](https://mlsanity.com/paper/1905.02709/) (2019)
- [DC2: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering](https://mlsanity.com/paper/1911.06944/) (2019)
- [Automatically Score Tissue Images Like a Pathologist by Transfer Learning](https://mlsanity.com/paper/2209.05954/) (2022)

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

- [Correcting Variable Importance Scored by Random Forests](https://mlsanity.com/paper/2606.10770/) (2026)

## Abstract (arXiv)

The popular K-means clustering algorithm potentially suffers from a major weakness for further analysis or interpretation. Some cluster may have disproportionately more (or fewer) points from one of the subpopulations in terms of some sensitive variable, e.g., gender or race. Such a fairness issue may cause bias and unexpected social consequences. This work attempts to improve the fairness of K-means clustering with a two-stage optimization formulation--clustering first and then adjust cluster membership of a small subset of selected data points. Two computationally efficient algorithms are proposed in identifying those data points that are expensive for fairness, with one focusing on nearest data points outside of a cluster and the other on highly 'mixed' data points. Experiments on benchmark datasets show substantial improvement on fairness with a minimal impact to clustering quality. The proposed algorithms can be easily extended to a broad class of clustering algorithms or fairness metrics.