Coresets for Clustering with Fairness Constraints Article Swipe

MAKE IMPACT

Lingxiao Huang , Shaofeng H.-C. Jiang , Nisheeth K. Vishnoi · YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1906.08484

In a recent work, [19] studied the following "fair" variants of classical clustering problems such as $k$-means and $k$-median: given a set of $n$ data points in $\mathbb{R}^d$ and a binary type associated to each data point, the goal is to cluster the points while ensuring that the proportion of each type in each cluster is roughly the same as its underlying proportion. Subsequent work has focused on either extending this setting to when each data point has multiple, non-disjoint sensitive types such as race and gender [6], or to address the problem that the clustering algorithms in the above work do not scale well. The main contribution of this paper is an approach to clustering with fairness constraints that involve multiple, non-disjoint types, that is also scalable. Our approach is based on novel constructions of coresets: for the $k$-median objective, we construct an $\varepsilon$-coreset of size $O(Γk^2 \varepsilon^{-d})$ where $Γ$ is the number of distinct collections of groups that a point may belong to, and for the $k$-means objective, we show how to construct an $\varepsilon$-coreset of size $O(Γk^3\varepsilon^{-d-1})$. The former result is the first known coreset construction for the fair clustering problem with the $k$-median objective, and the latter result removes the dependence on the size of the full dataset as in [39] and generalizes it to multiple, non-disjoint types. Plugging our coresets into existing algorithms for fair clustering such as [5] results in the fastest algorithms for several cases. Empirically, we assess our approach over the \textbf{Adult}, \textbf{Bank}, \textbf{Diabetes} and \textbf{Athlete} dataset, and show that the coreset sizes are much smaller than the full dataset. We also achieve a speed-up to recent fair clustering algorithms [5,6] by incorporating our coreset construction.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1906.08484

PDF

https://arxiv.org/pdf/1906.08484

OA Status

green

Cited By

21

References

31

Related Works

10

OpenAlex ID

https://openalex.org/W2951203646

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2951203646

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1906.08484

Digital Object Identifier

Title

Coresets for Clustering with Fairness Constraints

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2019

Year of publication

Publication date

2019-06-20

Full publication date if available

Authors

Lingxiao Huang, Shaofeng H.-C. Jiang, Nisheeth K. Vishnoi

List of authors in order

Landing page

https://arxiv.org/abs/1906.08484

Publisher landing page

PDF URL

https://arxiv.org/pdf/1906.08484

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1906.08484

Direct OA link when available

Concepts

Cluster analysis, Computer science, Business, Artificial intelligence

Top concepts (fields/topics) attached by OpenAlex

Cited by

21

Total citation count in OpenAlex

Citations by year (recent)

2025: 1, 2024: 3, 2023: 5, 2022: 3, 2021: 6

Per-year citation counts (last 5 years)

References (count)

31

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload