We study the question of fair clustering under the disparate impact doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the k-center and the k-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution can violate common conventions - for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding good fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically demonstrate the price of fairness by quantifying the value of fair clustering on real-world datasets with sensitive attributes.

Fair Clustering Through Fairlets / Chierichetti, Flavio; Kumar, Ravi; Lattanzi, Silvio; Vassilvitskii, Sergei. - (2017), pp. 5030-5038. (Intervento presentato al convegno Neural Information Processing Systems 2017 tenutosi a Long Beach; CA, USA).

Fair Clustering Through Fairlets

Chierichetti, Flavio;
2017

Abstract

We study the question of fair clustering under the disparate impact doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the k-center and the k-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution can violate common conventions - for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding good fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically demonstrate the price of fairness by quantifying the value of fair clustering on real-world datasets with sensitive attributes.
2017
Neural Information Processing Systems 2017
Computer Networks and Communications; Information Systems; Signal Processing
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Fair Clustering Through Fairlets / Chierichetti, Flavio; Kumar, Ravi; Lattanzi, Silvio; Vassilvitskii, Sergei. - (2017), pp. 5030-5038. (Intervento presentato al convegno Neural Information Processing Systems 2017 tenutosi a Long Beach; CA, USA).
File allegati a questo prodotto
File Dimensione Formato  
Chierichetti_fair_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 350.5 kB
Formato Adobe PDF
350.5 kB Adobe PDF   Contatta l'autore
Chierichetti_fair_postprint_2017.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 395.39 kB
Formato Adobe PDF
395.39 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1166994
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 234
  • ???jsp.display-item.citation.isi??? 111
social impact