按年被提到
20202023 · 3 次2026
机器学习与深度学习›贝叶斯方法与 AutoML·arXiv:2006.06856 · cs.LG

BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits

BanditPAM:借助多臂老虎机实现近线性时间的 k-medoids 聚类
Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris Piech, Ilan Shomorony · 2020

用多臂老虎机把 k-medoids 聚类加速到近线性时间

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2021-11-25 · 最近 2023-04-05
3不同的人
3活跃月份
3讨论串
26被引(OpenAlex)

k-medoids 要求聚类中心是真实数据点并支持任意距离度量,但 PAM 等主流算法每轮迭代是 n 的平方复杂度,难以用于大数据集。BanditPAM 借用多臂老虎机的随机化技术,把每轮 PAM 迭代的复杂度从 O(n²) 降到 O(n log n),并在对数据的一定假设下以高概率返回相同的结果。在多个真实数据集上,它与最先进的 PAM 类算法结果相同,速度最多快 4 倍,距离计算最多少 200 倍。

HN 为什么提它

HN 上主要是作者本人在讨论中介绍这项把最优已知算法从 O(n²) 提速到 O(n log n) 的工作,并获得其他评论者的称赞。

方法难度 4 / 5约 50 分钟经得起时间
读之前最好知道
1k-medoids 聚类与 PAM 算法
2多臂老虎机(multi-armed bandits)
3算法复杂度与概率界
4k-means 聚类

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选里只有 Hyperband 一篇与目标论文的「用多臂老虎机加速机器学习计算」思路相近,所以路径很短。

  1. 1
    Hyperband: A Novel Bandit-Based Approach to Hyperparameter OptimizationHyperband:一种基于老虎机的超参数优化新方法 · 2016

    Hyperband 把多臂老虎机的自适应资源分配与早停用于超参数搜索,与 BanditPAM 把老虎机思想用于加速聚类相呼应。

    读successive halving 与自适应分配预算的思想;超参数搜索的实验可略读。

  2. 2
    BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed BanditsBanditPAM:借助多臂老虎机实现近线性时间的 k-medoids 聚类 · 2020 · 就是这篇

    把 k-medoids 的 PAM 算法中每一步的最优选择转化为多臂老虎机问题,实现近线性时间。

    读BUILD 与 SWAP 阶段如何变为最优臂识别,以及置信区间驱动的随机化抽样。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐eternalban · 2023-04

“Thanks for sharing your great work!”

感谢分享,称赞这项可扩展的 k-medoids 聚类工作
Show HN: Want something better than k-means? Try BanditPAM原评论 ↗
引用motiwari · 2023-03

“In our NeurIPS 2020 paper, BanditPAM, we sped up the best known algorithm from O(n^2) to O(nlogn).”

作者自述 BanditPAM 把最优已知算法从 O(n^2) 提速到 O(nlogn)
Show HN: Want something better than k-means? Try BanditPAM原评论 ↗
引用motiwari · 2023-04

“In our NeurIPS 2020 paper, BanditPAM, we sped up the best known algorithm from O(n^2) to O(nlogn) by using techniques from multi-armed bandits.”

作者自述借助多臂老虎机技术把已知最快算法从 O(n^2) 提速到 O(nlogn)
Show HN: Want something better than k-means? Try BanditPAM原评论 ↗
被提交为 story · 1 次