Improving k -means through distributed scalable metaheuristics

Oliveira, G.V., Coutinho, F.P., Campello, R.J.G.B., and Naldi, M.C. (2017) Improving k -means through distributed scalable metaheuristics. Neurocomputing, 246. pp. 45-57.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website:


The recent growing size of datasets requires scalability of data mining algorithms, such as clustering algorithms. The MapReduce programing model provides the scalability needed, alongside with portability as well as automatic data safety and management. k-means is one of the most popular algorithms in data mining and can be easily adapted to the MapReduce model. Nevertheless, k-means has drawbacks, such as the need to provide the number of clusters (k) in advance and the sensitivity of the algorithm to the initial cluster prototypes. This paper presents two evolutionary scalable metaheuristics in MapReduce that automatically seek the solution with the optimal number of clusters and best clustering structure for scalable datasets. The first consists in an algorithm able to iteratively enhance k-means clusterings through evolutionary operators designed to handle distributed data. The second consists in applying evolutionary k-means to cluster each distributed portion of a dataset in an independent way, combining the obtained results into an ensemble afterwards. The proposed techniques are compared asymptotically and experimentally with other state-of-the-art clustering algorithms also developed in MapReduce. The results are analyzed by statistical tests and show that the first proposed metaheuristic yielded results with the best quality, while the second achieved the best computing times.

Item ID: 49164
Item Type: Article (Research - C1)
ISSN: 1872-8286
Keywords: k-means, metaheuristics, evolutionary algorithms, optimization, distributed algorithms, MapReduce, scalability
Funders: CNPq, Brazil, CAPES, FAPEMIG
Projects and Grants: FAPEMIG CHE-APQ-00156-14
Date Deposited: 12 Jun 2017 03:49
FoR Codes: 49 MATHEMATICAL SCIENCES > 4905 Statistics > 490502 Biostatistics @ 100%
SEO Codes: 97 EXPANDING KNOWLEDGE > 970101 Expanding Knowledge in the Mathematical Sciences @ 100%
Downloads: Total: 1
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page