Cluster Analysis using Growing Neural Gas and Graph Partitioning

The size and complexity of data sets is ever increasing. Clustering, considered the most important unsupervised learning problem, is used to reveal structures and to identify "natural" groupings on the multivariate data. Several competitive learning algorithms were developed for this application. The Growing Neural Gas (GNG) is an incremental algorithm, where no previous information about the number of clusters is preset. New units are added according to the training dynamics. GNG produces a graph that represents the topology of trained data. Each vertex corresponds to a neuron in which input data have been mapped. This paper describes a simple algorithm to better produce the partitioning of this graph, generating connected components that represent different data clusters. The algorithm automatically finds the number of classes and the associated neurons.