Fair Clustering Under a Bounded Cost
Fair Clustering Under a Bounded Cost
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Seyed-Alireza Esmaeili;Brian Brubach;A. Srinivasan;John P. Dickerson
中科院分区：
文献类型：
--
作者：
Seyed-Alireza Esmaeili;Brian Brubach;A. Srinivasan;John P. Dickerson
聚类是一个基本的无监督学习问题，其中数据集被划分为由度量空间中的邻近点组成的聚类。最近的一个变体，公平聚类，将颜色与代表其组成员的每个点相关联，并要求每个颜色在每个聚类中具有（近似）相等的表示以满足组公平性。在该模型中，由于在算法中强制执行公平性，聚类目标的成本增加。成本的相对增加，“公平的价格”，确实可以是无限的。因此，在本文中，我们建议把聚类目标的上限作为聚类问题的约束条件，并最大限度地提高平等的代表受到it.We考虑两个公平的目标：组功利主义的目标和组平等主义的目标，以及组leximin目标，概括了组平等主义的目标。我们推导出基本的下限近似的功利主义和平等主义的目标，并引入算法与可证明的保证。对于leximin目标，我们引入了一个有效的启发式算法。我们进一步推导出其他自然公平目标的不可能结果。最后，我们在真实世界的数据集上的实验结果证明了我们的算法的有效性。
Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the ''price of fairness,'' can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.