Computational Complexity Analysis of Ant Colony Clustering Algorithms: Application to Student’s Grouping Problem

The task of assessing, grouping and arranging data into meaningful groups or clusters based on their similarities/dissimilarities measures known as cluster analysis. Thereby, there are numerous clustering algorithms: hierarchical and partitional. In the last decade, clustering using bio-inspired algorithms received more attention, specifically the ant clustering algorithms. Regardless, they have required a lot of processing power due to the massive amount of data that has been generated during the last years. As a consequence, determining the computational cost of these algorithms is one of the most interesting tasks in the quest for optimal clustering solutions in a real-time system. This study presents a research guide for the researchers working in the same field. A series of experiments are elaborated to investigate the computational complexity of the most promising algorithms applied to students grouping problem. The results indicate two challenges that arise when using ant clustering algorithms: the difficulty in adjusting parameters and extended computation time.

I. Introduction

Cluster analysis or clustering is the task of analyzing, categorizing, and grouping data into meaningful groups or clusters. Indeed, the data gathered in the same cluster show high similarity measures and the data in different clusters show high dissimilarity ones [1]. There are two basic types of clustering: hierarchical and partitional, with various algorithms. Noticeably, the partitional clustering algorithms acquired more attention because they are faster than hierarchical ones, and they offer strong assumptions in terms of their clustering quality, computational complexity, and parameters adjustment [2]. At their beginning, clustering algorithms required a big consumption of processing power due to the evolution of the huge volume of data. Hence, evaluating the computational complexity of these algorithms represents one of the most challenging issues in various domains. Recently, clustering based on heuristic approaches, specifically the ant colony clustering approach is most promising and has been shown satisfactory results in solving a wide variety of grouping problems [1],[3],[4]. Nonetheless, ant-based clustering algorithms applied with large datasets may represent a complex and time-consuming task. To deal with this research issue, we carried out a systematic literature review and try to give answers to the following Research Questions (RQs):