Published on Sun Feb 10 2019

Scalable Fair Clustering

Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner

We study the fair variant of the classic -median problem introduced by Chierichetti et al. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. Our algorithm additionally allows for finer control over the balance of resulting clusters.

0
0
0
Abstract

We study the fair variant of the classic -median problem introduced by Chierichetti et al. [2017]. In the standard -median problem, given an input pointset , the goal is to find centers and assign each input point to one of the centers in such that the average distance of points to their cluster center is minimized. In the fair variant of -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 -clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the -median objective. In the second step, fairlets are merged into clusters by one of the existing -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.

Mon Oct 26 2020
Machine Learning
KFC: A Scalable Approximation Algorithm for -center Fair Clustering
In fair clustering, the input is points, each belonging to at least one of protected groups. We obtain a randomized approximation algorithm for the center objective function, beating the previous state of the art.
0
0
0
Mon Feb 17 2020
Machine Learning
Individual Fairness for -Clustering
We give a local search based algorithm for -median and $ k$-means. We show how to get a bicriteria approximation for fair -clustering.
0
0
0
Wed Jun 23 2021
Machine Learning
Better Algorithms for Individually Fair -Clustering
We study data clustering problems with -norm objectives in the context of individual fairness. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20. We obtain noticeably fairer solutions.
0
0
0
Tue Jan 08 2019
Machine Learning
Fair Algorithms for Clustering
We study the problem of finding low-cost Fair Clusterings in data where each data point may belong to many protected groups. Our work significantly generalizes the seminal work of Chierichetti et.al. (NIPS 2017) as follows.
0
0
0
Sat Jun 26 2021
Artificial Intelligence
Improved Approximation Algorithms for Individually Fair Clustering
We consider the -clustering problem with -norm cost. We extend the framework of Charikar et al., 2002, Swamy, 2016. Our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement.
0
0
0
Mon Jul 20 2020
Machine Learning
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
0
0
0