Fair Coresets and Streaming Algorithms for Fair k-Means Clustering

By Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler. 2018

42 citations recorded by the source corpus.

We study fair clustering problems as proposed by Chierichetti et al. (NIPS 2017). Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable and show how to compute them in a streaming setting. Furthermore, we propose a variant of Lloyd's algorithm that computes fair clusterings and extend it to a fair k-means++ clustering algorithm. We implement these algorithms and provide empirical evidence that the combination of our approximation algorithms and the coreset construction yields a scalable algorithm for fair k-means clustering.

Subfields: Artificial Intelligence, Organizational Behavior and Human Resource Management

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Organizational Behavior and Human Resource Management

Citations in the corpus

Beyond Individual and Group Fairness (2020, background): “…fairness criteria and algorithms for ranking [Celis et al., 2018, Beutel et al., 2019, Narasimhan et al., 2019] and clustering problems [Chierichetti et al., 2017, Schmidt et al., 2018, Backurs et al., 2019] with requirement of a proportional representation of populations within each cluster.”
Scalable Fair Clustering (2019, background): “The work most relevant to our paper is a recent manuscript by Schmidt et al. (2018), which proposed eﬃcient streaming algorithms for fair k -means (which is similar to k -median studied here).”
Fair Algorithms for Clustering (2019, background): “2 Comparison with Schmidt et al. [38]: In a very recent independent and concurrent work, Schmidt et al. [38] consider the fair k -means problem in the streaming model.”
Fair Generative Modeling via Weak Supervision (2019, background): “There is also a body of work on fair clustering (Chierichetti et al., 2017; Backurs et al., 2019; Bera et al., 2019; Schmidt et al., 2018) which ensure that the clustering assignments are balanced with respect to some sensitive attribute.”
Rényi Fair Inference (2019, methodology): “Unlike the twophase methods proposed in [13, 5, 43, 7, 47], our method does not require any pre-processing step, is scalable, and allows for regulating the trade-off between the clustering quality and fairness.”
Fairness in representation: quantifying stereotyping as a representational harm (2019, background): “In the context of unsupervised learning, recent work on fair clustering[12, 31, 3] and PCA[30, 28] seeks to generate a modiﬁed representation of the input points so that the new representation (clustering or reduced dimension) satisﬁes a notion of “balance” with respect to groups.”