【KDD2021】可扩展凝聚层次聚类

聚合聚类(用于推断层次和平面聚类)的适用性受到其可扩展性的限制。现有的可扩展层次聚类方法牺牲了质量以提高速度，并且经常导致聚类的过度合并。在本文中，我们提出了一种可扩展的、凝聚的分层聚类方法，不牺牲质量和规模到数十亿数据点。我们进行了详细的理论分析，表明在温和的可分性条件下，我们的算法不仅可以恢复最优的平面分割，而且提供了一个非参数DP-Means目标[32]的双近似。本文介绍了一种新的应用层次聚类作为逼近算法的非参数聚类目标。此外，我们还将我们的算法与经典的层次凝聚聚类方法联系起来。我们在分层和平面聚类设置中进行了大量的经验实验，并表明我们提出的方法在公开可用的聚类基准上取得了最先进的结果。最后，我们将该方法应用于300亿个查询的数据集，从而演示了该方法的可扩展性。人类对已发现的聚类的评估表明，我们的方法发现的聚类质量比当前的技术水平更好。

https://storage.googleapis.com/pub-tools-public-publication-data/pdf/fcbefa25e4d6ad6ea8174449fcff779083ce80ff.pdf