arXiv:2506.08673cs.LGcs.DS2025-06中稿 · the Conference on …被引 4

让聚类结果公平代表各类群体,首次给出可证明的近似解法。

Towards Fair Representation: Clustering and Consensus

  • 从公平性视角重构共识聚类,确保各群体在聚类中比例合理。
  • 提出等量群体下的最优算法与不等量时的近似算法,性能有保障。
  • 适用于需公平性的数据聚类场景,如医疗、招聘等敏感领域。

共识聚类是机器学习与数据分析中的基础任务,旨在将基于不同非敏感属性的多个输入聚类整合为一个能最好反映数据整体结构的单一聚类。本文从公平聚类视角研究该问题,引入Chierichetti等人(NeurIPS'17)提出的差异影响原则,确保每个受保护群体在每个聚类中均获得成比例的代表。目标是寻找既具代表性又符合特定受保护属性公平性的共识聚类。据我们所知,这是首个解决此问题并提供常数因子近似的方案。研究还探讨如何最小修改现有聚类以实现公平性——许多需要公平表示的聚类应用中的关键后处理步骤。针对等比例群体,提出最优算法;对更一般情况(两组大小不等),设计近似因子常数的近乎线性时间算法。同时证明该问题对两组大小不等情形为NP难。鉴于其基础性,本研究对其他无先验近似保证的公平聚类问题可能具有广泛影响。

原文摘要 · Abstract (English)

Consensus clustering, a fundamental task in machine learning and data analysis, aims to aggregate multiple input clusterings of a dataset, potentially based on different non-sensitive attributes, into a single clustering that best represents the collective structure of the data. In this work, we study this fundamental problem through the lens of fair clustering, as introduced by Chierichetti et al. [NeurIPS'17], which incorporates the disparate impact doctrine to ensure proportional representation of each protected group in the dataset within every cluster. Our objective is to find a consensus clustering that is not only representative but also fair with respect to specific protected attributes. To the best of our knowledge, we are the first to address this problem and provide a constant-factor approximation. As part of our investigation, we examine how to minimally modify an existing clustering to enforce fairness -- an essential postprocessing step in many clustering applications that require fair representation. We develop an optimal algorithm for datasets with equal group representation and near-linear time constant factor approximation algorithms for more general scenarios with different proportions of two group sizes. We complement our approximation result by showing that the problem is NP-hard for two unequal-sized groups. Given the fundamental nature of this problem, we believe our results on Closest Fair Clustering could have broader implications for other clustering problems, particularly those for which no prior approximation guarantees exist for their fair variants.

公平聚类共识聚类近似算法

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