Scalable Fair Clustering

2019-02-10 · Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner

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.

📄 PDF Abstract BibTeX arXiv:1902.03519

Code (1)

talwagner/fair_clustering 공식 구현

Tasks

ClusteringFairness

Scalable Spectral Clustering with Group Fairness Constraints

2022-10-28 · Ji Wang, Ding Lu, Ian Davidson, Zhaojun Bai

There are synergies of research interests and industrial efforts in modeling fairness and correcting algorithmic bias in machine learning. In this paper, we present a scalable algorithm for spectral clustering (SC) with …

Clustering Fairness Stochastic Block Model

A Scalable Algorithm for Individually Fair K-means Clustering

2024-02-09 · Mohammadhossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi

We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. Given $n$ points $P$ in a metric space, let $\delta(x)$ for $x\in P$ be the radius of …

Clustering

Efficient Algorithms For Fair Clustering with a New Fairness Notion

2021-09-02 · Shivam Gupta, Ganesh Ghalme, Narayanan C. Krishnan, Shweta Jain

We revisit the problem of fair clustering, first introduced by Chierichetti et al., that requires each protected attribute to have approximately equal representation in every cluster; i.e., a balance property. Existing s…

Attribute Clustering Fairness

A General Anchor-Based Framework for Scalable Fair Clustering

2025-11-13 · Shengfei Wei, Suyuan Liu, Jun Wang, Ke Liang 외 arxiv

Fair clustering is crucial for mitigating bias in unsupervised learning, yet existing algorithms often suffer from quadratic or super-quadratic computational complexity, rendering them impractical for large-scale dataset…

Variational Fair Clustering

2019-06-19 · Imtiaz Masud Ziko, Eric Granger, Jing Yuan, Ismail Ben Ayed

We propose a general variational framework of fair clustering, which integrates an original Kullback-Leibler (KL) fairness term with a large class of clustering objectives, including prototype or graph based. Fundamental…

Clustering Fairness