Robust growing neural gas algorithm with application in cluster analysis.

*(English)*Zbl 1079.68596Summary: We propose a novel robust clustering algorithm within the Growing Neural Gas (GNG) framework, called Robust Growing Neural Gas (RGNG) network.1 By incorporating several robust strategies, such as outlier resistant scheme, adaptive modulation of learning rates and cluster repulsion method into the traditional GNG framework, the proposed RGNG network possesses better robustness properties. The RGNG is insensitive to initialization, input sequence ordering and the presence of outliers. Furthermore, the RGNG network can automatically determine the optimal number of clusters by seeking the extreme value of the Minimum Description Length (MDL) measure during network growing process. The resulting center positions of the optimal number of clusters represented by prototype vectors are close to the actual ones irrespective of the existence of outliers. Topology relationships among these prototypes can also be established. Experimental results have shown the superior performance of our proposed method over the original GNG incorporating MDL method, called GNG-M, in static data clustering tasks on both artificial and UCI data sets.

##### MSC:

68T05 | Learning and adaptive systems in artificial intelligence |

68T10 | Pattern recognition, speech recognition |

68W05 | Nonnumerical algorithms |

62H30 | Classification and discrimination; cluster analysis (statistical aspects) |

##### Keywords:

Robust clustering algorithm; Robust growing neural gas; Prototypes; Outlier resistant; Minimum description length; Topology formation##### Software:

UCI-ml
PDF
BibTeX
XML
Cite

\textit{A. K. Qin} and \textit{P. N. Suganthan}, Neural Netw. 17, No. 8--9, 1135--1148 (2004; Zbl 1079.68596)

Full Text:
DOI

##### References:

[1] | Ahalt, S.C.; Krishnamurty, A.K.; Chen, P.; Melton, D.E., Competitive learning algorithms for vector quantization, Neural networks, 3, 3, 277-291, (1990) |

[2] | Atukorale, A.S.; Downs, T.; Suganthan, P.N., Boosting the HONG network, Neurocomputing, 51, 75-86, (2003) |

[3] | Berkhin, P., Survey of clustering data mining techniques, (2002), Accrue Software |

[4] | Bezdek, J.C.; Keller, J.M.; Krishnapuram, R.; Pal, N.R., Fuzzy models and algorithms for pattern recognition and image processing, (1999), Kluwer Norwell, MA · Zbl 0998.68138 |

[5] | Bhatia, S.K.; Deogun, J.S., Conceptual clustering in information retrieval, IEEE transactions on system, man, cybernetics, part B, 28, 3, 427-436, (1998) |

[6] | Bischof, H.; Leonardis, A.; Selb, A., MDL principle for robust vector quantization, Pattern analysis and application, 2, 1, 59-72, (1999) · Zbl 0926.68151 |

[7] | Blake, C.; Keogh, E.; Metz, C.J., UCI repository of machine learning databases, (1998), Department of Information and Computer Science, University of California at Irvine, CA |

[8] | Cao, X.; Sugantahn, P.N., Video shot motion characterization based on hierarchical overlapped growing neural gas networks, Multimedia systems, 9, 4, 378-385, (2003) |

[9] | Carlevarino, A., Martinotti, R., Metta, G., & Sandini, G. (2000). Incremental growing neural network and its application to robot control. Proceeding of the 2000 international joint conference on neural networks (IJCNN00), 5 (pp. 323-328), Como, Italy. |

[10] | Chintalapudi, K.K.; Kam, M., The credibilistic fuzzy c-means algorithm, Proceeding of 1998 IEEE international conference on systems, man and cybernetics, San Diego, CA, 2034-2040, (1998) |

[11] | Clark, M.C.; Hall, L.O.; Goldgof, D.B.; Clarke, L.P.; Velthuizen, R.P.; Silbiger, M.S., MRI segmentation using fuzzy clustering techniques, IEEE engineering in medicine and biology magazine, 13, 730-742, (1994) |

[12] | Dave, R.N.; Krishnapuram, R., Robust clustering methods: a unified view, IEEE transactions on fuzzy systems, 5, 270-293, (1997) |

[13] | Duda, R.; Hart, P., Pattern recognition and scene analysis, (1973), Wiley/Interscience New York |

[14] | Frigui, H.; Krishnapuram, R., Clustering by competitive agglomeration, Pattern recognition, 30, 7, 1109-1119, (1997) |

[15] | Frigui, H.; Krishnapuram, R., A robust competitive clustering algorithm with applications in computer vision, IEEE transactions on pattern analysis machine intelligence, 21, 450-465, (1999) |

[16] | Fritzke, B., Growing cells structures—a self-organizing network for unsupervised and supervised learning, Neural networks, 7, 9, 1441-1460, (1994) |

[17] | Fritzke, B., A growing neural gas network learns topologies, (), 625-632 |

[18] | Fritzke, B. (1997). Some competitive learning methods (draft). Technique report. Institute for Neural Computation, Ruhr-University, Bochum, http://www.neuroinformatik.ruhr-uni-bochum.de/ini/VDM/research/gsn/JavaPaper/. |

[19] | Girolami, M., Mercer kernel based clustering in feature space, IEEE transactions on neural networks, 13, 780-784, (2002) |

[20] | Hamerly, G., & Elkan, C. (2003). Learning the k in k-means. Proceeding of 17th annual conference on neural information processing systems (NIPS2003), Canada. |

[21] | Haykin, S., Neural networks: a comprehensive foundation, (1998), Prentice-Hall Englewood Cliffs, NJ · Zbl 0828.68103 |

[22] | Haykin, S., Adaptive filter theory, (2001), Prentice-Hall Englewood Cliffs, NJ |

[23] | Jain, I.K.; Murty, N.N.; Flynn, P.J., Data clustering: a review, ACM computing surveys, 264-323, (1999) |

[24] | Kato, N.; Nemoto, Y., Large scale handwritten character recognition system using subspace methods, Proceeding of 1996 IEEE international conference on systems, man and cybernetics, Beijing, China, 1, 432-437, (1996) |

[25] | Kohonen, T., Self-organizing maps, (2001), Springer Berlin · Zbl 0957.68097 |

[26] | Martinetz, T. M. (1993). Competitive Hebbian learning rule forms perfectly topology preserving maps. Proceeding of 1993 international conference on artificial neural networks (ICANN93) (pp. 427-434), Amsterdam, The Netherlands. |

[27] | Martinetz, T.M.; Berkovich, S.G.; Schulten, K.J., Neural gas network for vector quantization and its application to time-series prediction, IEEE transactions on neural networks, 4, 558-569, (1993) |

[28] | Martinetz, T.M.; Schulten, K., Topology representing networks, Neural networks, 3, 507-522, (1994) |

[29] | Pal, N. R., Pal, K., & Bezdek, J. C. (1997). A mixed c-means clustering model. Proceeding of 1997 IEEE international conference on fuzzy system, Spain. |

[30] | Pelleg, D., & Moore, A. (2000). X-means: Extending k-means with efficient estimation of the number of clusters. Proceeding of the 17th international conference on machine learning (pp. 727-734), San Francisco, USA. |

[31] | Qin, A. K., & Suganthan, P. N. (2004). A robust neural gas algorithm for clustering analysis. Proceeding of 2004 international conference on intelligent sensing and information processing (ICISIP2004) (pp. 342-347), Chennai, India. |

[32] | Ray, S., & Turi, R. H. (1999). Determination of number of clusters in k-means clustering and application in color image segmentation. Proceeding of the fourth international conference on advances in pattern recognition and digital techniques (ICAPRDT’99) (pp. 137-143), Calcutta, India. |

[33] | Ressom, H.; Wang, D.; Natarajan, P., Adaptive double self-organizing maps for clustering gene expression profiles, Neural networks, 16, 5-6, 633-640, (2003) |

[34] | Rissanen, J., Stochastic complexity in statistical inquiry, World scientific: series in computer science, 15, (1989) · Zbl 0800.68508 |

[35] | Tenmoto, H., Kudo, M., & Shimbo, M. (1998). MDL-based selection of the number of components in mixture models for pattern classification. In Advance in Pattern Recognition, edited by A. Amin, D. Dori, P. Pudil & H. Freeman, Lecture Notes in Computer Science, Springer, no. 1451, pp. 831-836. |

[36] | Timm, H.; Borgelt, C.; Döring, C.; Kruse, R., Fuzzy cluster analysis with cluster repulsion, Proceeding of European symposium on intelligent technologies, hybrid systems and their implementation on smart adaptive systems, Germany, (2001) |

[37] | Winter, M., Metta, G., & Sandini, G. (2000). Neural-gas for function approximation: a heuristic for minimizing the local estimation error. Proceeding of 2000 international joint conference on neural network (IJCNN00), 4 (pp. 535-538), Italy. |

[38] | Wu, K.-L.; Yang, M.-S., Alternative c-means clustering algorithms, Pattern recognition, 35, 2267-2278, (2002) · Zbl 1006.68876 |

[39] | Yang, T.-N.; Wang, S.-D.; Yen, S.-J., Fuzzy algorithms for robust clustering, Proceeding of international computer symposium, Houlian, Taiwan, (2002) |

[40] | Yu, H. (1998). Automatically determining number of clusters. Information retrieval (CMU CS11-741) final report. |

[41] | Zemel, R. S. (1994). A minimum description length framework for unsupervised learning. PhD thesis, University of Toronto. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.