Parallelization of an antbased clustering approach

• Published in: Kybernetes 2010-05, Vol.39 (4), p.656-677
• Main Authors: Gemici Gunes, Ozlem, Sima Uyar, A.
• Format: Article
• Language: English
• Subjects: Cluster analysis; Cybernetics; Programming and algorithm theory
• ISSN: 0368-492X
• DOI: 10.1108/03684921011036844

Purpose The purpose of this paper is to propose parallelization of a successful sequential antbased clustering algorithm SABCA to increase time performance. Designmethodologyapproach A SABCA is parallelized through the chosen parallelization library MPI. Parallelization is performed in two stages. In the first stage, data to be clustered are divided among processors. After the sequential antbased approach running on each processor clusters the data assigned to it, the resulting clusters are merged in the second stage. The merging is also performed through the same antbased technique. The experimental analysis focuses on whether the implemented parallel antbased clustering method leads to a better time performance than its fully sequential version or not. Since the aim of this paper is to speedup the time consuming, but otherwise successful, antbased clustering method, no extra steps are taken to improve the clustering solution. Tests are executed using 2 and 4 processors on selected sample datasets. Results are analyzed through commonly used cluster validity indices and parallelization performance metrices. Findings As a result of the experiments, it is seen that the proposed algorithm performs better based on time measurements and parallelization performance metrices as expected, it does not improve the clustering quality based on the cluster validity indices. Furthermore, the communication cost is very small compared to other antbased clustering parallelization techniques proposed so far. Research limitationsimplications The use of MPI for the parallelization step has been very effective. Also, the proposed parallelization technique is quite successful in increasing time performance however, as a future study, improvements to clustering quality can be made in the final step where the partially clustered data are merged. Practical implications The results in literature show that antbased clustering techniques are successful however, their hightime complexity prohibit their effective use in practical applications. Through this lowcommunicationcost parallelization technique, this limitation may be overcome. Originalityvalue A new parallelization approach to antbased clustering is proposed. The proposed approach does not decrease clustering performance while it increases time performance. Also, another major contribution of this paper is the fact that the communication costs required for parallelization is lower than the previously proposed parallel antbased