Fair Algorithms for Clustering

By Suman Kalyan Bera, Deeparnab Chakrabarty, Maryam Negahbani. 2019

292 citations recorded by the source corpus.

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 this http URL. (NIPS 2017) as follows. - We allow the user to specify the parameters that define fair representation. More precisely, these parameters define the maximum over- and minimum under-representation of any group in any cluster. - Our clustering algorithm works on any $\ell_p$-norm objective (e.g. $k$-means, $k$-median, and $k$-center). Indeed, our algorithm transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. - Our algorithm also allows individuals to lie in multiple protected groups. In other words, we do not need the protected groups to partition the data and we can maintain fairness across different groups simultaneously. Our experiments show that on established data sets, our algorithm performs much better in practice than what our theoretical results suggest.

How researchers see this paper

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

Citations in the corpus

Proportionally Fair Clustering (2019, background): “, 2017) and subsequent generalizations (Rösner & Schmidt, 2018; Bera et al., 2019), the authors consider fair clustering in terms of balance: There are red and blue points, and a balanced solution has roughly the same ratio of blue to red points in every cluster as in the overall population.”
Scalable Fair Clustering (2019, methodology): “Similarly, another algorithm proposed in Bera et al. (2019), requires solving n linear programs with Ω( nk ) variables each.”
Robust Optimization for Fairness with Noisy Protected Groups (2020, methodology): “We use m = 3 groups based on education levels: “graduate school,” “university,” and “high school/other” (the use of education in credit lending has previously been studied in the algorithmic fairness and economics literature [26, 9, 44]).”
Fairness in Machine Learning: A Survey (2020, unknown): “The literature typically hints toward “optimizing” fairness without transparency of the root(s) of (un)fairness [192] rarely extending beyond “(un)fair” [80, 270] typically to mirror current legal thought [98].”
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.”
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.”
A survey on datasets for fairness‐aware machine learning (2021, background): “Protected attributes: In the literature, sex (Deepak & Abraham, 2020; Bechavod & Ligett, 2017; Berk et al., 2017), education, marriage (Deepak & Abraham, 2020; Bera et al., 2019) are considered as the protected attributes.”