arXiv:2410.12913cs.LGcs.AI2024-10被引 9

提出更优公平数据聚类算法,逼近比从5降至3,兼顾效率与公平性。

Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights

  • 针对分组数据设计双变体公平k-供应商算法,支持互斥与重叠分组
  • 实现3倍近似比,优于此前5倍上限,且达理论下限
  • 算法可扩展至大规模数据,实证揭示公平约束带来的性能代价

数据摘要常建模为k-聚类问题,目标是选取k个中心点以最小化聚类目标。经典k-中心问题中,所有数据点均可作为中心;而一般情形下,中心必须从预定义的设施点中选择,即k-供应商问题。本文研究基于公平性的数据摘要,建模为公平k-供应商问题:数据由多个组构成,每组需至少选一定数量中心,同时最小化k-供应商目标。分组可为互斥或重叠,对应两种不同复杂度的变体。本文提出两种3-近似算法,优于此前5-近似,对互斥分组可在多项式时间内求解,对重叠分组给出固定参数可追踪算法(指数时间仅依赖组数与中心数)。证明该近似比在标准复杂度假设下已达理论下限。通过开源实现,在大规模合成数据上验证算法可扩展性,并在真实数据上评估公平性带来的性能代价,对比有无公平约束下的解质量。

原文摘要 · Abstract (English)

Data summarization tasks are often modeled as $k$-clustering problems, where the goal is to choose $k$ data points, called cluster centers, that best represent the dataset by minimizing a clustering objective. A popular objective is to minimize the maximum distance between any data point and its nearest center, which is formalized as the $k$-center problem. While in some applications all data points can be chosen as centers, in the general setting, centers must be chosen from a predefined subset of points, referred as facilities or suppliers; this is known as the $k$-supplier problem. In this work, we focus on fair data summarization modeled as the fair $k$-supplier problem, where data consists of several groups, and a minimum number of centers must be selected from each group while minimizing the $k$-supplier objective. The groups can be disjoint or overlapping, leading to two distinct problem variants each with different computational complexity. We present $3$-approximation algorithms for both variants, improving the previously known factor of $5$. For disjoint groups, our algorithm runs in polynomial time, while for overlapping groups, we present a fixed-parameter tractable algorithm, where the exponential runtime depends only on the number of groups and centers. We show that these approximation factors match the theoretical lower bounds, assuming standard complexity theory conjectures. Finally, using an open-source implementation, we demonstrate the scalability of our algorithms on large synthetic datasets and assess the price of fairness on real-world data, comparing solution quality with and without fairness constraints.

聚类优化公平性近似算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。