BanditPAM: 基于多臂老虎机的近线性时间 k-中位数聚类

新闻摘要： BanditPAM：一种几乎线性时间的k-medoids聚类算法 近日，研究人员发布了名为BanditPAM的新算法，该算法显著提升了k-medoids聚类的效率，将其时间复杂度从O(n²)降低到O(n log n)。k-medoids是一种与k-means类似的聚类算法，但其聚类中心（medoids）必须是实际数据点，这使得结果更具可解释性，并支持任意距离度量，适用于更广泛的数据类型。 传统的k-medoids算法（如PAM）由于其较高的时间复杂度，限制了其在大规模数据集上的应用。BanditPAM通过将PAM算法中的关键步骤转化为多臂老虎机（multi-armed bandits）问题，并采用随机采样策略，显著减少了计算量。该算法保留了PAM的聚类质量，同时将其效率提高了一个数量级。 该算法的实现采用C++编写，以提升运行速度，并支持并行化和智能缓存，同时提供了Python接口，方便用户通过pip安装和使用。其接口与scikit-learn的KMeans接口相匹配，使用户能够轻松集成到现有代码中。此外，用户还可以自定义距离度量，提升聚类的灵活性和适用性。 BanditPAM的发布标志着k-medoids聚类在效率和实用性上的重要突破，为数据科学家提供了更强大、更灵活的聚类工具。