Proportionally Representative Clustering
In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering--one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportionally representative fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom. Our algorithm for the discrete setting also matches the best known approximation factor for PF.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringFairnessSimilar Papers 제목 키워드 기반
Efficient Clustering with Provable Guardrails for LLM Inference at Scale
Scaling LLM-based applications to millions of users is bottlenecked by the inference cost and latency of modern foundation models. A natural fix is to cluster the inputs and call the LLM only on cluster representatives, …
A characterization of proportionally representative committees
A well-known axiom for proportional representation is Proportionality of Solid Coalitions (PSC). We characterize committees satisfying PSC as possible outcomes of the Minimal Demand rule, which generalizes an approach pi…
Proportional Selection in Networks
We address the problem of selecting $k$ representative nodes from a network, aiming to achieve two objectives: identifying the most influential nodes and ensuring the selection proportionally reflects the network's diver…
DiversityProportionally Fair Clustering
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…
ClusteringFairnessGuarantees for Spectral Clustering with Fairness Constraints
Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). Acc…
ClusteringFairnessStochastic Block Model