突破最坏情况！新采样法让聚类核心集缩小，ε依赖指数首破2！
Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling
📖 AI 总结
该研究针对大规模数据聚类中的核心集构造问题，提出了一种超越最坏情况界限的新方法。传统上，(k,z)-聚类问题的ε-核心集大小在最坏情况下存在紧致下界，难以进一步压缩。作者引入基于行列式点过程的“行列式采样”框架，在数据分布满足温和自然假设的条件下，构造出可高效计算的ε-核心集。其关键突破在于，当维度d固定时，核心集大小对1/ε的依赖指数严格小于2，从而突破了此前ε⁻²的最坏情况屏障。这是首个通过超越最坏情况假设在理论上证明可超越该下界的工作。实验部分在合成与真实基准数据集上验证了方法有效性，即便未显式满足分析假设，其核心集规模也持续优于现有最先进方法，展示了实际应用潜力。
🔑 关键词速览
| ε-coreset | 一个小的加权数据子集，用于近似保留所有可能聚类中心下的聚类成本，是数据缩减的关键工具。 |
| (k,z)-clustering | 一种广义聚类问题，其中成本函数基于距离的 z 次幂，k 表示聚类中心数量，涵盖 k-means (z=2) 和 k-median (z=1) 等特例。 |
| determinantal sampling | 一种基于行列式点过程的采样方法，通过引入相关性选择多样且代表性的样本，用于构建更小的核心集。 |
| beyond-worst-case assumptions | 对数据分布施加温和自然条件（如低内在维度或结构特性），以突破最坏情况下的理论界限，获得更优的实际性能保证。 |
| determinantal point processes (DPPs) | 一种概率模型，用于描述点集的选择概率与行列式成正比，促进样本多样性，常用于采样和子集选择。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅