Comparing yinyang and fission-fusion algorithms for accelerating the k-means

Marcelo Kuchar Matte and Maria do Carmo Nicoletti

International Journal of Knowledge and Learning, 2024, vol. 17, issue 4, 408-426

Abstract: Given both, a set of data instances and an integer value k as input to the k-means clustering algorithm, a clustering represented as a partition of the given set into k groups (clusters) is produced by the algorithm. The k-means is considered relatively scalable and efficient in processing large sets of data instances. However, the inductive process the algorithm implements can have high time-related computational cost, depending on the given set of instances. Considering the algorithm invests most of its runtime in distance calculations, a way of accelerating its execution time is by avoiding calculations when possible. One way of doing that is by using a mathematical result known as triangle inequality. The main goal of the work described in this paper is to empirically investigate the contribution of the triangle inequality employed by two algorithms, the yinyang and the fission-fusion. Results from experiments using both algorithms on 17 datasets are evidence that, in general, the yinyang algorithm had a speed-up performance higher than that of the fission-fusion. However, in datasets where instances are described by a relatively small number of attributes (≤8), the fission-fusion had a better speed-up performance.

Keywords: k-means; optimisation; triangle inequality; accelerating algorithms; yinyang; fission-fusion. (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=139558 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijklea:v:17:y:2024:i:4:p:408-426

Access Statistics for this article

More articles in International Journal of Knowledge and Learning from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().