A multi-objective genetic graph-based clustering algorithm with memory optimization

Abstract

Clustering is one of the most versatile tools for data analysis. Over the last few years, clustering that seeks the continuity of data (in opposition to classical centroid-based approaches) has attracted an increasing research interest. It is a challenging problem with a remarkable practical interest. The most popular continuity clustering method is the Spectral Clustering algorithm, which is based on graph cut: it initially generates a Similarity Graph using a distance measure and then uses its Graph Spectrum to find the best cut. Memory consuption is a serious limitation in that algorithm: The Similarity Graph representation usually requires a very large matrix with a high memory cost. This work proposes a new algorithm, based on a previous implementation named Genetic Graph-based Clustering (GGC), that improves the memory usage while maintaining the quality of the solution. The new algorithm, called Multi-Objective Genetic Graph-based Clustering (MOGGC), uses an evolutionary approach introducing a Multi-Objective Genetic Algorithm to manage a reduced version of the Similarity Graph. The experimental validation shows that MOGGC increases the memory efficiency, maintaining and improving the GGC results in the synthetic and real datasets used in the experiments. An experimental comparison with several classical clustering methods (EM, SC and K-means) has been included to show the efficiency of the proposed algorithm.