Efficient Clustering based on Population Markov Chain

H.-J. Lin, F.-W. Yang, and Y.-T. Kao (Taiwan)


clustering, unsupervised classification, geneticalgorithms, Markov chain, Davies-Bouldin index.


This paper proposes a new clustering technique that is based on genetic algorithms, without the need for any GA operation. With the aid of an analysis of population Markov chains and some modifications to the genetic operations, the proposed technique markedly outperforms the existing conventional GA-based clustering methods. The proposed strategy adopts a modified version of Markov chain modeling introduced by Yong Gao et al. [16] to perform the evolutionary process. In the evolutionary process, offspring are simply produced according to the probabilities provided from Markov chain modeling, without any conventional genetic operators. Hence, a great deal of the processing time required by genetic operators can be eliminated. In the clustering procedure, the center candidates of the clusters are taken from the data set, so that we can in advance create a look up table that saves the distances between every pair of data points and prevent the repeated computation of distances in evaluating the fitness function. A binary representation is used to encode a certain set of cluster centers and the validity of the clusters is measured using the Davies-Bouldin index [12]. The experimental results indicate the superiority of the proposed algorithm over conventional genetic algorithms, and show that the proposed algorithms achieve better performance with less computational time than the conventional genetic algorithms.

Important Links:

Go Back