Proportionally Fair Clustering

Abstract

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering $n$ points with $k$ centers, we define fairness as proportionality to mean that any $n/k$ points are entitled to form their own cluster if there is another center that is closer in distance for all $n/k$ points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the $k$-means objective.

To appear in ICML 2019

Cited by in corpus (25)

• Fairness in Machine Learning: A Survey
• Individual Fairness for $k$-Clustering
• Fair Hierarchical Clustering
• Representativity Fairness in Clustering
• Distributional Individual Fairness in Clustering
• Does Gender Matter? Towards Fairness in Dialogue Systems
• Approximation Algorithms for Socially Fair Clustering
• Fair Correlation Clustering
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• Fair Clustering with Multiple Colors
• Better Algorithms for Individually Fair $k$-Clustering
• Deep Fair Discriminative Clustering
• Approximate Group Fairness for Clustering
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
• Improved Approximation Algorithms for Individually Fair Clustering
• Fairness Constraints in Semi-supervised Learning
• Fair Clustering Using Antidote Data
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center
• FPT Approximation for Fair Minimum-Load Clustering
• Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
• Fair for All: Best-effort Fairness Guarantees for Classification
• Approximately Stable Committee Selection
• Fairness Degrading Adversarial Attacks Against Clustering Algorithms
• Fair Allocation with Interval Scheduling Constraints
• A Sociotechnical View of Algorithmic Fairness