IEICE TRANSACTIONS on Information
Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space
Summary :
This paper presents an efficient 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E101-D No.11 pp.2773-2783
- Publication Date
- 2018/11/01
- Publicized
- 2018/08/02
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2017EDP7392
- Type of Manuscript
- PAPER
- Category
- Artificial Intelligence, Data Mining
Authors
Kazuo AOYAMA
NTT Communication Science Laboratories
Kazumi SAITO
Kanagawa University
Tetsuo IKEDA
University of Shizuoka
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuo AOYAMA, Kazumi SAITO, Tetsuo IKEDA, "Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 11, pp. 2773-2783, November 2018, doi: 10.1587/transinf.2017EDP7392.
Abstract: This paper presents an efficient 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017EDP7392/_p
Copy
@ARTICLE{e101-d_11_2773,
author={Kazuo AOYAMA, Kazumi SAITO, Tetsuo IKEDA, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space},
year={2018},
volume={E101-D},
number={11},
pages={2773-2783},
abstract={This paper presents an efficient 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.},
keywords={},
doi={10.1587/transinf.2017EDP7392},
ISSN={1745-1361},
month={November},}
Copy
TY - JOUR
TI - Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space
T2 - IEICE TRANSACTIONS on Information
SP - 2773
EP - 2783
AU - Kazuo AOYAMA
AU - Kazumi SAITO
AU - Tetsuo IKEDA
PY - 2018
DO - 10.1587/transinf.2017EDP7392
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2018
AB - This paper presents an efficient 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.
ER -
English
