提出首个流式公平共识聚类算法,内存仅需对数级。
A Generic Framework for Fair Consensus Clustering in Streams
- 设计新框架,结合最近公平聚类与聚类拟合,支持流式处理。
- 只需存储对数级输入聚类,实现常数因子近似解。
- 适用于任意可高效计算近似公平聚类的公平定义,适合大规模场景。
共识聚类旨在将同一数据集的多个聚类结果(可能由多代理环境中的不同非敏感属性生成)融合为一个能最好反映数据底层结构的单一划分。近期工作由Chakraborty等人提出比例公平变体,并通过简单选择最接近的公平输入聚类获得常数因子近似解;然而其离线方法需存储所有输入聚类,在大多数大规模应用中开销过高。本文首次研究流式环境下的公平共识聚类,其中输入聚类按顺序到达且内存受限。我们设计了首个常数因子算法,可在仅存储对数级输入的情况下处理数据流。过程中,我们提出一种新通用算法框架,整合最近公平聚类与聚类拟合,不仅提升流式设置下的近似保证,离线重访时亦有改进。此外,该框架具备公平性无关性:只要能高效计算近似公平聚类,即可适用任意公平定义。最后,我们将方法扩展至更一般的k-median共识聚类问题。
原文摘要 · Abstract (English)
Consensus clustering seeks to combine multiple clusterings of the same dataset, potentially derived by considering various non-sensitive attributes by different agents in a multi-agent environment, into a single partitioning that best reflects the overall structure of the underlying dataset. Recent work by Chakraborty et al, introduced a fair variant under proportionate fairness and obtained a constant-factor approximation by naively selecting the best closest fair input clustering; however, their offline approach requires storing all input clusterings, which is prohibitively expensive for most large-scale applications. In this paper, we initiate the study of fair consensus clustering in the streaming model, where input clusterings arrive sequentially and memory is limited. We design the first constant-factor algorithm that processes the stream while storing only a logarithmic number of inputs. En route, we introduce a new generic algorithmic framework that integrates closest fair clustering with cluster fitting, yielding improved approximation guarantees not only in the streaming setting but also when revisited offline. Furthermore, the framework is fairness-agnostic: it applies to any fairness definition for which an approximately close fair clustering can be computed efficiently. Finally, we extend our methods to the more general k-median consensus clustering problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。