论文题目：Accelerating Exact K-Means++ Seeding Using Lower Bound Based Framework

      第一作者：张浩文

      收录会议：2023 International Conference on Database Systems for Advanced Applications

      会议级别：数据挖掘领域CCF-B

      论文概述：

      k-means++是一种广泛使用的方法，可以获得合理的k-means聚类初始中心，并且它的经验表现良好。然而，k-means++的时间复杂度使其在大型数据集上运行缓慢。因此，有必要提高k-means++的效率，使其能够很好地扩展到大型数据集。之前的大部分工作都集中在近似k-means++上。它们可以有效地实现加速；然而，它们本质上是近似方法，不能获得与k-means++相同的结果。本文提出了一种基于下界的框架（LBF）来加速k-means++的种子选择。LBF是一种精确的方法，可以在更短的时间内执行k-means++，同时保证相同的结果。本文提出了基于渐进部分距离和分段聚合近似的下界，并将两个下界方案嵌入到LBF中，我们提供了理论分析，以展示它们的下界特性和计算效率。在各种合成和真实数据集上的实验结果证明，与基线k-means++和近似方法相比，所提算法是有效的。