提出高效公平聚类算法,兼顾准确率与大规模数据处理能力。
Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering
- 基于参数化与流式处理设计,分两阶段优化公平性约束下的聚类
- 在欧氏空间中实现2.732和4.464的近似比,可提升至2.414和3.828
- 适合大规模数据场景,实测显著优于现有方法
为应对机器学习中公平性日益重要的需求,公平k-中心聚类成为关键问题。该问题将数据集划分为m个互不重叠的组,需选择k个点作为中心,每组中心数量受上限约束,目标是最小化任意数据点到其分配中心的最大距离。针对广泛应用于机器学习的欧氏空间,本文首先提出参数化近似算法,近似比为2.732;将其嵌入单轮流式框架后,得到近似比4.464。若允许指数级于k的运行时间,近似比可分别提升至2.414和3.828。为保证多项式时间复杂度,进一步设计单轮流算法,近似比为4.732,可优化至4.42,优于当前最优结果。大量实验表明,本方法在聚类精度上显著超越现有技术。
原文摘要 · Abstract (English)
Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。