K-Means Clustering using Tabu Search with Quantized Means

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

8 Downloads (Pure)

Abstract

The Tabu Search (TS) metaheuristic has been proposed for K-Means clustering as an alternative to Lloyd’s algorithm, which for all its ease of implementation and fast runtime, has the major drawback of being trapped at local optima. While the TS approach can yield superior performance, it involves a high computational complexity. Moreover, the difficulty in parameter selection in the existing TS approach does not make it any more attractive. This paper presents an alternative, low-complexity formulation of the TS optimization procedure for K-Means clustering. This approach does not require many parameter settings. We initially constrain the centers to points in the dataset. We then aim at evolving these centers using a unique neighborhood structure that makes use of gradient information of the objective function. This results in an efficient exploration of the search space, after which the means are refined. The proposed scheme is implemented in MATLAB and tested on four real-world datasets, and it achieves a significant improvement over the existing TS approach in terms of the intra cluster sum of squares and computational time.
Original languageEnglish
Title of host publicationProceedings of the World Congress on Engineering and Computer Science 2016
EditorsSio-Iong Ao, Craig C Douglas, W. S. Grundfest
PublisherNewswood Limited
Pages426-432
Number of pages7
ISBN (Print)978-988-14047-1-8
Publication statusPublished - 2016
EventWorld Congress on Engineering and Computer Science 2016 - San Francisco, United States
Duration: 19 Oct 201621 Oct 2016
Conference number: 24
http://www.iaeng.org/WCECS2016/

Publication series

NameLecture Notes in Engineering and Computer Science
ISSN (Print)2078-0958
ISSN (Electronic)2078-0966

Conference

ConferenceWorld Congress on Engineering and Computer Science 2016
Abbreviated titleWCECS 2016
CountryUnited States
CitySan Francisco
Period19/10/1621/10/16
Internet address

Fingerprint

Tabu search
MATLAB
Computational complexity

Bibliographical note

All the papers in the online version are available freely with open access full-text content and permanent worldwide web link.

Keywords

  • Unsupervised learning
  • Clustering
  • K-Means
  • Tabu Search

Cite this

Gyamfi, S., Brusey, J., & Hunt, A. (2016). K-Means Clustering using Tabu Search with Quantized Means. In S-I. Ao, C. C. Douglas, & W. S. Grundfest (Eds.), Proceedings of the World Congress on Engineering and Computer Science 2016 (pp. 426-432). (Lecture Notes in Engineering and Computer Science). Newswood Limited.

K-Means Clustering using Tabu Search with Quantized Means. / Gyamfi, Sarfo; Brusey, James; Hunt, Andrew.

Proceedings of the World Congress on Engineering and Computer Science 2016. ed. / Sio-Iong Ao; Craig C Douglas; W. S. Grundfest. Newswood Limited, 2016. p. 426-432 (Lecture Notes in Engineering and Computer Science).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

Gyamfi, S, Brusey, J & Hunt, A 2016, K-Means Clustering using Tabu Search with Quantized Means. in S-I Ao, CC Douglas & WS Grundfest (eds), Proceedings of the World Congress on Engineering and Computer Science 2016. Lecture Notes in Engineering and Computer Science, Newswood Limited, pp. 426-432, World Congress on Engineering and Computer Science 2016 , San Francisco, United States, 19/10/16.
Gyamfi S, Brusey J, Hunt A. K-Means Clustering using Tabu Search with Quantized Means. In Ao S-I, Douglas CC, Grundfest WS, editors, Proceedings of the World Congress on Engineering and Computer Science 2016. Newswood Limited. 2016. p. 426-432. (Lecture Notes in Engineering and Computer Science).
Gyamfi, Sarfo ; Brusey, James ; Hunt, Andrew. / K-Means Clustering using Tabu Search with Quantized Means. Proceedings of the World Congress on Engineering and Computer Science 2016. editor / Sio-Iong Ao ; Craig C Douglas ; W. S. Grundfest. Newswood Limited, 2016. pp. 426-432 (Lecture Notes in Engineering and Computer Science).
@inproceedings{a1936e541de844cfb2b47bf02cc55988,
title = "K-Means Clustering using Tabu Search with Quantized Means",
abstract = "The Tabu Search (TS) metaheuristic has been proposed for K-Means clustering as an alternative to Lloyd’s algorithm, which for all its ease of implementation and fast runtime, has the major drawback of being trapped at local optima. While the TS approach can yield superior performance, it involves a high computational complexity. Moreover, the difficulty in parameter selection in the existing TS approach does not make it any more attractive. This paper presents an alternative, low-complexity formulation of the TS optimization procedure for K-Means clustering. This approach does not require many parameter settings. We initially constrain the centers to points in the dataset. We then aim at evolving these centers using a unique neighborhood structure that makes use of gradient information of the objective function. This results in an efficient exploration of the search space, after which the means are refined. The proposed scheme is implemented in MATLAB and tested on four real-world datasets, and it achieves a significant improvement over the existing TS approach in terms of the intra cluster sum of squares and computational time.",
keywords = "Unsupervised learning, Clustering, K-Means, Tabu Search",
author = "Sarfo Gyamfi and James Brusey and Andrew Hunt",
note = "All the papers in the online version are available freely with open access full-text content and permanent worldwide web link.",
year = "2016",
language = "English",
isbn = "978-988-14047-1-8",
series = "Lecture Notes in Engineering and Computer Science",
publisher = "Newswood Limited",
pages = "426--432",
editor = "Ao, {Sio-Iong } and Douglas, {Craig C} and Grundfest, {W. S. }",
booktitle = "Proceedings of the World Congress on Engineering and Computer Science 2016",

}

TY - GEN

T1 - K-Means Clustering using Tabu Search with Quantized Means

AU - Gyamfi, Sarfo

AU - Brusey, James

AU - Hunt, Andrew

N1 - All the papers in the online version are available freely with open access full-text content and permanent worldwide web link.

PY - 2016

Y1 - 2016

N2 - The Tabu Search (TS) metaheuristic has been proposed for K-Means clustering as an alternative to Lloyd’s algorithm, which for all its ease of implementation and fast runtime, has the major drawback of being trapped at local optima. While the TS approach can yield superior performance, it involves a high computational complexity. Moreover, the difficulty in parameter selection in the existing TS approach does not make it any more attractive. This paper presents an alternative, low-complexity formulation of the TS optimization procedure for K-Means clustering. This approach does not require many parameter settings. We initially constrain the centers to points in the dataset. We then aim at evolving these centers using a unique neighborhood structure that makes use of gradient information of the objective function. This results in an efficient exploration of the search space, after which the means are refined. The proposed scheme is implemented in MATLAB and tested on four real-world datasets, and it achieves a significant improvement over the existing TS approach in terms of the intra cluster sum of squares and computational time.

AB - The Tabu Search (TS) metaheuristic has been proposed for K-Means clustering as an alternative to Lloyd’s algorithm, which for all its ease of implementation and fast runtime, has the major drawback of being trapped at local optima. While the TS approach can yield superior performance, it involves a high computational complexity. Moreover, the difficulty in parameter selection in the existing TS approach does not make it any more attractive. This paper presents an alternative, low-complexity formulation of the TS optimization procedure for K-Means clustering. This approach does not require many parameter settings. We initially constrain the centers to points in the dataset. We then aim at evolving these centers using a unique neighborhood structure that makes use of gradient information of the objective function. This results in an efficient exploration of the search space, after which the means are refined. The proposed scheme is implemented in MATLAB and tested on four real-world datasets, and it achieves a significant improvement over the existing TS approach in terms of the intra cluster sum of squares and computational time.

KW - Unsupervised learning

KW - Clustering

KW - K-Means

KW - Tabu Search

UR - http://www.iaeng.org/publication/WCECS2016

M3 - Conference proceeding

SN - 978-988-14047-1-8

T3 - Lecture Notes in Engineering and Computer Science

SP - 426

EP - 432

BT - Proceedings of the World Congress on Engineering and Computer Science 2016

A2 - Ao, Sio-Iong

A2 - Douglas, Craig C

A2 - Grundfest, W. S.

PB - Newswood Limited

ER -