Gene transposon based clonal selection algorithm for clustering

ABSTRACT

Inspired by the principle of gene transposon proposed by Barbara McClintock, a new immune computing algorithm for clustering multi-class data sets named as Gene Transposition based Clone Selection Algorithm (GTCSA) is proposed in this paper, The proposed algorithm does not require a prior knowledge of the numbers of clustering; an improved variant of the clonal selection algorithm has been used to determine the number of clusters as well as to refine the cluster center. a novel operator called antibody transposon is introduced to the framework of clonal selection algorithm which can realize to find the optimal number of cluster automatically. The proposed method has been extensively compared with Variable-string-length Genetic Algorithm(VGA)based clustering techniques over a test suit of several real life data sets and synthetic data sets. The results of experiments indicate the superiority of the GTCSA over VGA on stability and convergence rate, when clustering multi-class data sets.

REFERENCES

• 1: I. E. Evangelou, D. G. Hadjimitsis, A. A. Lazakidou. Data mining and knowledge discovery in complex image data using artificial neural networks. In Proc. Workshop Complex Reason. Geogr.Data, Paphos, Cyprus, 2001.
• 2: M. R. Rao. Cluster analysis and mathematical programming J. Amer.Stat. Assoc., 1971, 66(335): 622--626.
• 3: Thomas Martin Lillesand, Remote Sensing and Image Interpretation, John Wiley & Sons, 2006
• 4: Hichem Frigui , Raghu Krishnapuram, A Robust Competitive Clustering Algorithm With Applications in Computer Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.450-465, May 1999 [doi>10.1109/34.765656]
• 5: Yee Leung , Jiang-She Zhang , Zong-Ben Xu, Clustering by Scale-Space Filtering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1396-1410, December 2000 [doi>10.1109/34.895974]
• 6: D. Lee, S. Baek, and K. Sung. Modified K--means algorithm for vector quantizer design, IEEE Signal Process. Lett, 1997, 4(1): 2--4.
• 7: K. K. Paliwal and V. Ramasubramanian, Comments on Modified K--means algorithm for vector quantizer design, IEEE Trans. Image Process., 2000, 9(3):. 1964--1967.
• 8: G P Babu and M. N. Murty. Clustering with evolution strategies. Pattern Recognition, 1994, 27 (2): 321--329.
• 9: U Maulik, S. Bandyopadhyay. Genetic Algorithm--based Clustering Technique. Pattern Recognition, 2000, 33 (9): 1455--1465.
• 10: Leandro Nunes de Castro , Fernando J. Von Zuben, An Evolutionary Immune Network for Data Clustering, Proceedings of the VI Brazilian Symposium on Neural Networks (SBRN'00), p.84, January 22-25, 2000
• 11: Yu Chen , Changjie Tang , Jun Zhu , Chuan Li , Shaojie Qiao , Rui Li , Jiang Wu, Clustering Without Prior Knowledge Based on Gene Expression Programming, Proceedings of the Third International Conference on Natural Computation, p.451-455, August 24-27, 2007 [doi>10.1109/ICNC.2007.302]
• 12: G. Hamerly, C. Elkan, Learning the k in k-means. Neural Information Processing Systems, NIPS 2003, December 8-13, Vancouver and Whistler, British Columbia, Canada, 2003
• 13: S. Bandyopadhyay and U. Maulik Nonparametric genetic clustering: Comparison of validity indices. IEEE Transaction on System, Man, and Cybernetics. Part C: Application and Reviews, 2001, 1(31): 120--125
• 14: N. Fedom and Batstein, eds, The dynamic genome: Barbara McClintock ideas in the century of genetics, Cold Spring Harbor, N. Y.: Cold Spring Harbor Laboratory Press, 1992.
• 15: F. M. Burnet. The Clonal Selection Theory of Acquired Immunity. Cambridge University Press. 1959.
• 16: L. N. De Castro, F. J. Von Zuben. The clonal selection algorithm with engineering applications//Proceedings of Genetic and Evolutionary Computation Conference 2000 (CEC'00), Workshop on Artificial Immune Systems and Their Applications, Las Vegas, USA, 2000: 36--37.
• 17: R. C. Liu, et al. Clonal strategy algorithm based on the immune memory. Journal of Computer Science and Technology (JCST). 2005, 20(6): 728--734.
• 18: B McClintock. The origin and behavior of mutable loci in maize//Proceedings of the National Academy of Sciences, USA, 1950, 36: 344--355
• 19: T. M. Chan , K. F. Man , K. S. Tang , S. Kwong, A Jumping Gene Algorithm for Multiobjective Resource Management in Wideband CDMA Systems, The Computer Journal, v.48 n.6, p.749-768, November 2005 [doi>10.1093/comjnl/bxh135]
• 20: T. M. Chan , K. F. Man , K. S. Tang , S. Kwong, A Jumping Gene Algorithm for Multiobjective Resource Management in Wideband CDMA Systems, The Computer Journal, v.48 n.6, p.749-768, November 2005 [doi>10.1093/comjnl/bxh135]
• 21: M K Pakhira, S Bandyopadhyay and U. Maulik. Validity index for crisp and fuzzy clusters. Pattern Recognition, 2004, 3(37): 487--501. 1258.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Experimentation

Keywords:
clone selection algorithm, clustering, gene transposon, pbm index