The search functionality is under construction.

The search functionality is under construction.

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

Kazuo AOYAMA

NTT Communication Science Laboratories

Kazumi SAITO

Kanagawa University

Tetsuo IKEDA

University of Shizuoka

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.

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 -