Fair k-Center Clustering for Data Summarization

Matthäus Kleindessner, Pranjal Awasthi, Jamie Morgenstern
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3448-3457, 2019.

Abstract

In data summarization we want to choose k prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose ki prototypes belonging to group i. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as k-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard k-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the k-center problem under the fairness constraint with running time linear in the size of the data set and k. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kleindessner19a, title = {Fair k-Center Clustering for Data Summarization}, author = {Kleindessner, Matth{\"a}us and Awasthi, Pranjal and Morgenstern, Jamie}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3448--3457}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kleindessner19a/kleindessner19a.pdf}, url = {https://proceedings.mlr.press/v97/kleindessner19a.html}, abstract = {In data summarization we want to choose $k$ prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose $k_i$ prototypes belonging to group $i$. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as $k$-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard $k$-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the $k$-center problem under the fairness constraint with running time linear in the size of the data set and $k$. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.} }
Endnote
%0 Conference Paper %T Fair k-Center Clustering for Data Summarization %A Matthäus Kleindessner %A Pranjal Awasthi %A Jamie Morgenstern %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kleindessner19a %I PMLR %P 3448--3457 %U https://proceedings.mlr.press/v97/kleindessner19a.html %V 97 %X In data summarization we want to choose $k$ prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose $k_i$ prototypes belonging to group $i$. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as $k$-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard $k$-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the $k$-center problem under the fairness constraint with running time linear in the size of the data set and $k$. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.
APA
Kleindessner, M., Awasthi, P. & Morgenstern, J.. (2019). Fair k-Center Clustering for Data Summarization. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3448-3457 Available from https://proceedings.mlr.press/v97/kleindessner19a.html.

Related Material