Probabilistic Fair Clustering
Probabilistic Fair Clustering
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Seyed-Alireza Esmaeili;Brian Brubach;Leonidas Tsepenekas;John P. Dickerson
中科院分区：
文献类型：
--
作者：
Seyed-Alireza Esmaeili;Brian Brubach;Leonidas Tsepenekas;John P. Dickerson
在聚类问题中，中心决策者被赋予一个关于顶点的完全度量图，并且必须提供一个最小化某一目标函数的顶点聚类。在公平聚类问题中，顶点被赋予颜色(例如，组中的成员)，并且有效聚类的特征还可能包括该聚类中颜色的表示。公平聚类之前的工作假设完全了解组成员身份。在本文中，我们通过概率赋值假设群成员的不完全知识来推广先前的工作。我们在这种更一般的环境下提出了具有逼近比保证的聚类算法。我们还解决了“度量成员资格”的问题，其中不同的组具有顺序和距离的概念。使用我们提出的算法和基线进行了实验，以验证我们的方法，并在组成员身份不确定的情况下揭示了细微差别的问题。
In clustering problems, a central decision-maker is given a complete metric graph over vertices and must provide a clustering of vertices that minimizes some objective function. In fair clustering problems, vertices are endowed with a color (e.g., membership in a group), and the features of a valid clustering might also include the representation of colors in that clustering. Prior work in fair clustering assumes complete knowledge of group membership. In this paper, we generalize prior work by assuming imperfect knowledge of group membership through probabilistic assignments. We present clustering algorithms in this more general setting with approximation ratio guarantees. We also address the problem of "metric membership", where different groups have a notion of order and distance. Experiments are conducted using our proposed algorithms as well as baselines to validate our approach and also surface nuanced concerns when group membership is not known deterministically.