Socially Fair k-Means Clustering
Socially Fair k-Means Clustering
复制标题
DOI：
10.1145/3442188.3445906
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Mehrdad Ghadiri;S. Samadi;S. Vempala
中科院分区：
文献类型：
--
作者：
Mehrdad Ghadiri;S. Samadi;S. Vempala
我们表明，用于各种科学数据的流行的k - 均值聚类算法（劳埃德启发式算法）可能会导致对数据子组（例如，人口群体）不利的结果。这种有偏差的聚类可能对以人类为中心的应用（如资源分配）产生有害影响。我们提出了一个公平的k - 均值目标和算法来选择聚类中心，为不同群体提供公平的成本。该算法，公平 - 劳埃德算法，是对k - 均值的劳埃德启发式算法的一种修改，继承了其简单性、高效性和稳定性。与标准的劳埃德算法相比，我们发现，在基准数据集上，公平 - 劳埃德算法通过确保所有群体在输出的k - 聚类中具有相等的成本，表现出无偏差的性能，同时运行时间的增加可以忽略不计，因此，在当前使用k - 均值的任何地方，它都是一个可行的公平选择。
We show that the popular k-means clustering algorithm (Lloyd's heuristic), used for a variety of scientific data, can result in outcomes that are unfavorable to subgroups of data (e.g., demographic groups). Such biased clusterings can have deleterious implications for human-centric applications such as resource allocation. We present a fair k-means objective and algorithm to choose cluster centers that provide equitable costs for different groups. The algorithm, Fair-Lloyd, is a modification of Lloyd's heuristic for k-means, inheriting its simplicity, efficiency, and stability. In comparison with standard Lloyd's, we find that on benchmark datasets, Fair-Lloyd exhibits unbiased performance by ensuring that all groups have equal costs in the output k-clustering, while incurring a negligible increase in running time, thus making it a viable fair option wherever k-means is currently used.