在随机噪声下构建聚类压缩数据集,提升精度与规模。
Coresets for Clustering Under Stochastic Noise
- 设计新误差度量,更贴近真实聚类代价。
- 理论证明可缩小核心集达多项式级,最优时减少poly(k)倍。
- 适合高噪声环境下需高效聚类的工程应用。
我们研究在输入数据受已知分布随机噪声污染的情况下,为$(k, z)$-聚类构造压缩数据集(coreset)的问题。由于真实底层数据不可观测,评估压缩数据集质量极具挑战性。为此,我们考察使用可计算且与真实聚类代价有理论关联的代理误差度量来构造压缩数据集。分析了已有工作的传统度量,并提出一种新误差度量,虽独立于噪声分布,但其近似保证随噪声水平缩放。基于此度量,设计了一种压缩数据集构造算法,在数据与噪声满足温和假设下,强制$varepsilon$-界可获得更小的核心集和对真实聚类代价更紧的保证。特别地,我们证明核心集大小可提升高达$mathrm{poly}(k)$倍,其中$n$为数据集规模。在真实数据集上的实验支持了理论结果,展示了该方法的实用优势。
原文摘要 · Abstract (English)
We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independently of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an $\varepsilon$-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to $\mathrm{poly}(k)$, where $n$ is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。