用小批量估算加速k-中位数算法，大幅降低内存和计算量。
OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
- 用小批量数据估算目标函数，迭代优化中位数选择。
- 仅需O(mn)次相似度计算，比传统方法快得多。
- 适合大规模数据集，尤其对内存受限场景友好。
本文提出一种新型k-中位数近似算法，可在合理计算时间和内存复杂度下处理大规模数据集。我们设计了一种基于目标函数估计的局部搜索算法，仅需一个大小为m << n的小批量即可完成估计，将所需内存和成对不相似度计算次数从多数基线方法的O(n²)降至O(mn)。理论分析表明，当批量大小m = O(log(n))时，可高概率保证与原始局部搜索算法相当的性能。在多个真实数据集上的实验显示，该算法在不同规模和维度下均能实现与FasterPAM和BanditPAM++相当的性能，同时运行时间显著降低。
原文摘要 · Abstract (English)
This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m << n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n^2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。