Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space
Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space
复制标题
DOI：
10.1587/transinf.2017edp7392
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
K. Aoyama;Kazumi Saito;Tetsuo Ikeda
中科院分区：
文献类型：
--
作者：
K. Aoyama;Kazumi Saito;Tetsuo Ikeda
本文提出了一种有效的加速算法，该算法适用于大规模高维数据集，具有潜在的许多类的聚类。该算法采用了一种新的基于投影的滤波器（PRJ），以避免不必要的距离计算，从而使高速性能保持与标准劳埃德算法相同的结果。PRJ利用数据点投影到的低维空间中定义的平方距离上的可求和下界。可求和下界可以通过在每次迭代中在低维空间中增量添加分量来动态地使边界更紧，尽管其他加速算法中使用的现有下界仅作为固定滤波器工作一次。在大规模、高维真实的图像数据集上的实验结果表明，与现有算法相比，该算法在k值较大的情况下具有较高的运算速度和较低的内存消耗.关键词：算法
SUMMARY This paper presents an e ffi cient acceleration algorithm for Lloyd-type k -means clustering, which is suitable to a large-scale and high-dimensional data set with potentially numerous classes. The algorithm employs a novel projection-based filter ( PRJ ) to avoid unnecessary distance calculations, resulting in high-speed performance keeping the same results as a standard Lloyd’s algorithm. The PRJ exploits a summable lower bound on a squared distance defined in a lower-dimensional space to which data points are projected. The summable lower bound can make the bound tighter dynamically by incremental addition of components in the lower-dimensional space within each iteration although the existing lower bounds used in other acceleration algorithms work only once as a fixed filter. Experimental results on large-scale and high-dimensional real image data sets demonstrate that the proposed algorithm works at high speed and with low memory consumption when large k values are given, compared with the state-of-the-art algorithms. key words: algorithm