Proportionally Fair Clustering
Proportionally Fair Clustering
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
中科院分区：
文献类型：
--
作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
我们通过考虑度量背景下的比例中心点聚类问题，扩展了公平机器学习文献。对于以 $k$ 为中心对 $n$ 个点进行聚类的问题，我们将公平性定义为比例性，即对于所有 $n/k$ 个点来说，如果存在另一个距离更近的中心，则任何 $n/k$ 个点都有权组建自己的聚类。我们寻求的聚类方案不存在来自任何代理子集的合理投诉，也不假定任何受保护子集的先验概念。我们提出并分析了高效计算、优化和审核比例解决方案的算法。最后，我们对比例解决方案与 $k$ 均值目标之间的权衡进行了实证检验。
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.