针对大规模聚类，提出高效近似最近邻搜索方法加速算法
Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
- 引入种子近似最近邻搜索新范式，优化聚类核心步骤
- 实现 $k$ 超大时仍保持线性级复杂度，显著降低计算开销
- 适合超大规模高维数据聚类，如百万以上点的场景
当聚类中心数 $k$ 极大时，我们研究在包含 $10^7\sim10^9$ 个高维点（维度 $d\geq100$）的数据集上进行快速 $k$-均值聚类。当前所有实用方法的时间复杂度至少为 $Ω(k^2)$。我们发现初始化并非瓶颈，关键在于加速 Lloyd 算法中重新分配点至最近中心的步骤。为此，我们引入“种子近似最近邻搜索”这一新问题，并提出“种子搜索图”方法作为解决方案。该方法利用近似最近邻技术，在保证精度的前提下大幅提升可扩展性。
原文摘要 · Abstract (English)
For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $Ω(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。