用采样法提升高维空间中学习增强k-中位数聚类的效率与精度
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
- 通过简单采样预处理点集，提升聚类效率
- 显著降低计算复杂度，实测聚类代价更低
- 适合高维数据聚类场景，尤其对大规模数据有效
本文研究学习增强型k-中位数聚类问题，旨在通过一个误差率预测器α∈[0,1)对点集进行预处理，为点分配潜在标签以提升传统聚类算法性能。提出一种基于采样策略的算法，大幅降低现有方法的时间复杂度，并缓解其在欧氏空间维度上的指数依赖问题。实验表明，所提方法在实际应用中显著降低计算开销，同时实现更低的聚类代价，优于多个前沿学习增强型k-中位数聚类方法。
原文摘要 · Abstract (English)
In this paper, we investigate the learning-augmented $k$-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate $α\in [0,1)$. This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented $k$-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。