Genetic algorithm with healthy population and multiple streams sharing information for clustering

Abstract

Many popular clustering techniques including K-means require various user inputs such as the number of clusters k, which can often be very difficult for a user to guess in advance. Moreover, existing techniques like K-means also have a tendency of getting stuck at local optima. As a result, various evolutionary algorithm based clustering techniques have been proposed. Typically, they choose the initial population randomly, whereas carefully selected initial population can improve final clustering results. Hence, some existing techniques such as GenClust carefully select high-quality initial population with a complexity of O(n2) which is very high. We propose a clustering technique that in addition to selecting an initial population with a low complexity of O(n), uses a number of new components including multiple streams, information exchange between neighboring streams, regular health improvement of the chromosomes, and mutation which also aims to improve chromosome health. We compare the proposed technique HeMI with five (5) existing techniques on 20 publicly available data sets in terms of two well-known evaluation criteria. We also carry out a thorough experimentation to investigate the usefulness of the new components of HeMI. Our experimental results demonstrate statistically significant superiority of HeMI over existing techniques and the effectiveness of the proposed components.