Fair Clustering Through Fairlets
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.
While there is a growing body of work on fair supervised learning, here the authors present a first exploration of fair unsupervised learning by considering fair clustering. Each data point is labeled either red or blue, then an optimal k-clustering is sought which respects a given fairness criterion specified by a minimum threshold level of balance in each cluster. Balance lies in [0,1] with higher values corresponding to more equal numbers of red and blue points in every cluster. This is an interesting and natural problem formulation - though a more explicit example of exactly how this might be useful in practice would be helpful.
For both k-center and k-median versions of the problem, it is neatly shown that fair clustering may be reduced to first finding a good 'fairlet' decomposition and then solving the usual clustering problem on the centers of each fairlet. While this is NP-hard, efficient approximation algorithms are provided based on combining earlier methods with an elegant min cost flow construction.
On 3 example datasets, it is shown that standard clustering yields low balance (perhaps not surprising). A preliminary investigation of the cost of fairness is provided where balance of at least 0.5 is required and the number of clusters is varied. It would be interesting to see also the sensitivity to balance: keep the number of clusters fixed, and vary the required balance.
Minor points:
l. 16 machine learning are -> machine learning is
In a few places, e.g. l. 19, \citep{} would improve the readability, so Kleinberg et al. (2017a) -> (Kleinberg et al. 2017a).
l. 53 define -> defines. In fact, I think you just look at the costs of regular clusterings compared to fair so don't really use this ratio?
Fig 1 caption, would give -> might give. x is assigned to a -> x is assigned to the same cluster as a
l. 102 other measure -> other measures, please could you elaborate?
l. 132, 136 Y -> Y_j as in l. 161
Near Definition 5, an image showing an example of how fairlets together make up the fair clustering would be helpful, though I appreciate it's hard given space constraints - in the Supplement would still be good.