An empirical evaluation of strategies based on the triangle inequality for accelerating the k-means algorithm. (26th September 2022)

• Record Type: Journal Article
• Authors: Matte, Marcelo Kuchar; Nicoletti, Maria do Carmo
• Is Part Of: International journal of innovative computing and applications. Volume 13:Number 4(2022)
• Page Start: 198
• Page End: 209
• Publication Date: 2022-09-26
• Subjects: k-means -- optimisation -- triangular inequality -- clustering -- machine learning -- acceleration strategies; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

Abstract

The k-means clustering algorithm has a long history of success in a wide range of applications in many different research areas. Part of its success is due to both, the simplicity of the algorithm, which helps its quick implementation and the good results it produces. Despite success, however, the original k-means has some shortcomings. One of them relates to the processing time required for the algorithm to finish the iterative process that, given a set of data instances, and an integer value k, induces a clustering having k clusters of the given data instances. This article presents an empirical evaluation of three strategies found in the literature that employ the triangle inequality, with the purpose of accelerating the k-means processing time. Experiments were conducted using two groups of datasets, seven real datasets and ten artificially created datasets. Besides empirically evaluating the impact of variables involved in clustering processes that can interfere with accelerating processes, the article also discusses the different ways the triangle inequality concept is employed by the strategies.