Proportionally Fair Clustering

Xingyu Chen, Brandon Fain, Liang Lyu, Kamesh Munagala
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1032-1041, 2019.

Abstract

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to form their own cluster if there is another center that is closer in distance for all n/k points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the k-means objective.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-chen19d, title = {Proportionally Fair Clustering}, author = {Chen, Xingyu and Fain, Brandon and Lyu, Liang and Munagala, Kamesh}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {1032--1041}, 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/chen19d/chen19d.pdf}, url = {https://proceedings.mlr.press/v97/chen19d.html}, abstract = {We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to form their own cluster if there is another center that is closer in distance for all n/k points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the k-means objective.} }
Endnote
%0 Conference Paper %T Proportionally Fair Clustering %A Xingyu Chen %A Brandon Fain %A Liang Lyu %A Kamesh Munagala %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-chen19d %I PMLR %P 1032--1041 %U https://proceedings.mlr.press/v97/chen19d.html %V 97 %X We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to form their own cluster if there is another center that is closer in distance for all n/k points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the k-means objective.
APA
Chen, X., Fain, B., Lyu, L. & Munagala, K.. (2019). Proportionally Fair Clustering. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1032-1041 Available from https://proceedings.mlr.press/v97/chen19d.html.

Related Material