A Quantum-inspired Genetic Algorithm for data clustering

The conventional k-means clustering algorithm must know the number of clusters in advance and the clustering result is sensitive to the selection of the initial cluster centroids. The sensitivity may make the algorithm converge to the local optima. This paper proposes an improved k-means clustering algorithm based on quantum-inspired genetic algorithm (KMQGA). In KMQGA, Q-bit based representation is employed for exploration and exploitation in discrete 0-1 hyperspace by using rotation operation of quantum gate as well as three genetic algorithm operations (selection, crossover and mutation) of Q-bit. Without knowing the exact number of clusters beforehand, the KMQGA can get the optimal number of clusters as well as providing the optimal cluster centroids after several iterations of the four operations (selection, crossover, mutation, and rotation). The simulated datasets and the real datasets are used to validate KMQGA and to compare KMQGA with an improved k-means clustering algorithm based on the famous variable string length genetic algorithm (KMVGA) respectively. The experimental results show that KMQGA is promising and the effectiveness and the search quality of KMQGA is better than those of KMVGA.