Scalable Fair Clustering

Abstract

We study the fair variant of the classic $k$-median problem introduced by Chierichetti et al. [2017]. In the standard $k$-median problem, given an input pointset $P$, the goal is to find $k$ centers $C$ and assign each input point to one of the centers in $C$ such that the average distance of points to their cluster center is minimized. In the fair variant of $k$-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the $k$-median objective. In the second step, fairlets are merged into $k$ clusters by one of the existing $k$-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.

ICML 2019

Cited by in corpus (27)

• Fairness in Machine Learning: A Survey
• Individual Fairness for $k$-Clustering
• Fair Hierarchical Clustering
• Explainable $k$-Means and $k$-Medians Clustering
• Man is to Person as Woman is to Location: Measuring Gender Bias in Named Entity Recognition
• ExKMC: Expanding Explainable $k$-Means Clustering
• Does Gender Matter? Towards Fairness in Dialogue Systems
• Distributional Individual Fairness in Clustering
• Scalable Nearest Neighbor Search for Optimal Transport
• Approximation Algorithms for Socially Fair Clustering
• Fair Correlation Clustering
• Near-Optimal Explainable $k$-Means for All Dimensions
• Fair Clustering with Multiple Colors
• Principal Fairness: Removing Bias via Projections
• Improved Approximation Algorithms for Individually Fair Clustering
• Deep Fair Discriminative Clustering
• Approximate Group Fairness for Clustering
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
• Tree-Sliced Variants of Wasserstein Distances
• Fairness Constraints in Semi-supervised Learning
• Probabilistic Fair Clustering
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center
• Fair Clustering Using Antidote Data
• Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
• Towards Fair Deep Anomaly Detection
• Fairness Degrading Adversarial Attacks Against Clustering Algorithms
• A Sociotechnical View of Algorithmic Fairness