arXiv:2512.15210cs.DScs.LG2025-12KDD被引 1

让聚类结果随时间平滑演化,同时保持标签一致性。

Label-consistent clustering for evolving data

  • 设计新算法,在保留旧聚类标签基础上动态更新中心点。
  • 允许最多改变b个聚类标签,保证新解与旧解差异可控。
  • 适合需要稳定聚类结果的实时数据场景,如用户分群演化。

数据分析常需迭代更新,当新数据到来时,应调整现有聚类方案以融入最新信息。除追求高质量聚类外,还需保持一致性,避免与历史解产生剧烈变动。本文研究聚类中的这一问题,聚焦k-center问题:给定点集X、参数k和b,以及先前聚类解H,目标是寻找新的k个中心构成的解C,使聚类代价最小化,同时最多改变b个原始聚类标签。该问题称为标签一致k-center。本文提出两种常数倍近似算法,并通过真实数据集实验验证方法有效性。

原文摘要 · Abstract (English)

Data analysis often involves an iterative process, where solutions must be continuously refined in response to new data. Typically, as new data becomes available, an existing solution must be updated to incorporate the latest information. In addition to seeking a high-quality solution for the task at hand, it is also crucial to ensure consistency by minimizing drastic changes from previous solutions. Applying this approach across many iterations, ensures that the solution evolves gradually and smoothly. In this paper, we study the above problem in the context of clustering, specifically focusing on the $k$-center problem. More precisely, we study the following problem: Given a set of points $X$, parameters $k$ and $b$, and a prior clustering solution $H$ for $X$, our goal is to compute a new solution $C$ for $X$, consisting of $k$ centers, which minimizes the clustering cost while introducing at most $b$ changes from $H$. We refer to this problem as label-consistent $k$-center, and we propose two constant-factor approximation algorithms for it. We complement our theoretical findings with an experimental evaluation demonstrating the effectiveness of our methods on real-world datasets.

聚类动态数据标签一致优化算法

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