K-Means Clustering using Tabu Search with Quantized Means

Sarfo Gyamfi, James Brusey, Andrew Hunt

    Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

    39 Downloads (Pure)


    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
    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

    Publication series

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


    ConferenceWorld Congress on Engineering and Computer Science 2016
    Abbreviated titleWCECS 2016
    Country/TerritoryUnited States
    CitySan Francisco
    Internet address

    Bibliographical note

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


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


    Dive into the research topics of 'K-Means Clustering using Tabu Search with Quantized Means'. Together they form a unique fingerprint.

    Cite this