Proportionally Fair Clustering of Distributions

Choosing cluster centers to minimize average distance from data points can leave a substantial part of the training data poorly represented. Proportional fairness asks that no group of data points large enough to deserve a center to represent them unanimously prefer a new center. Our main contribution is to expand this framework from clustering a finite set of data points to clustering a given probability distribution. A natural question is whether every distribution admits a proportionally fair clustering once the number of centers is large enough; we answer this negatively. We also identify broad families of distributions which admit a proportionally fair clustering when the number of centers is sufficiently large, and those that admit one for any number of centers. We also establish deep connections between proportional fairness for a distribution and that for a finite set of i.i.d. samples drawn from the distribution, allowing us to efficiently transfer approximation guarantees (and nonexistence results) known for the finite sample case.