Fair Coresets and Streaming Algorithms for Fair k-Means Clustering
arXiv:1812.10854
Abstract
We study fair clustering problems as proposed by Chierichetti et al. (NIPS 2017). Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable and show how to compute them in a streaming setting. Furthermore, we propose a variant of Lloyd's algorithm that computes fair clusterings and extend it to a fair k-means++ clustering algorithm. We implement these algorithms and provide empirical evidence that the combination of our approximation algorithms and the coreset construction yields a scalable algorithm for fair k-means clustering.
References in corpus (3)
Cited by in corpus (18)
- Fair k-Center Clustering for Data Summarization
- Fairness in Clustering with Multiple Sensitive Attributes
- Equalized odds postprocessing under imperfect group information
- Fair Generative Modeling via Weak Supervision
- Rényi Fair Inference
- A Notion of Individual Fairness for Clustering
- Distributional Individual Fairness in Clustering
- Principal Fairness: Removing Bias via Projections
- Fair Correlation Clustering
- Approximate Group Fairness for Clustering
- Coresets for Ordered Weighted Clustering
- Beyond Individual and Group Fairness
- Fair Classification via Unconstrained Optimization
- Fairness Constraints in Semi-supervised Learning
- Decorrelated Clustering with Data Selection Bias
- Fairness-Aware Unsupervised Feature Selection
- Preventing Adversarial Use of Datasets through Fair Core-Set Construction
- Attraction-Repulsion clustering with applications to fairness