Self-splitting competitive learning: a new on-line clustering paradigm

Clustering in the neural-network literature is generally based on the competitive learning paradigm. The paper addresses two major issues associated with conventional competitive learning, namely, sensitivity to initialization and difficulty in determining the number of prototypes. In general, selecting the appropriate number of prototypes is a difficult task, as we do not usually know the number of clusters in the input data a priori. It is therefore desirable to develop an algorithm that has no dependency on the initial prototype locations and is able to adaptively generate prototypes to fit the input data patterns. We present a new, more powerful competitive learning algorithm, self-splitting competitive learning (SSCL), that is able to find the natural number of clusters based on the one-prototype-take-one-cluster (OPTOC) paradigm and a self-splitting validity measure. It starts with a single prototype randomly initialized in the feature space and splits adaptively during the learning process until all clusters are found; each cluster is associated with a prototype at its center. We have conducted extensive experiments to demonstrate the effectiveness of the SSCL algorithm. The results show that SSCL has the desired ability for a variety of applications, including unsupervised classification, curve detection, and image segmentation.

I. Introduction

Data Clustering aims at discovering and emphasizing structure which is hidden in a data set. Thus the structural relationships between individual data points can be detected. In general, clustering is an unsupervised learning process [1], [2]. Traditional clustering algorithms can be classified into two main categories: One is based on model identification by parametric statistics and probability, e.g., [3]–[7]; the other that has become more attractive recently is a group of vector quantization-based techniques, e.g., self-organizing feature maps (SOFMs) [8]–[12], the adaptive resonance theory (ART) series [13]–[17], and fuzzy logic [18]–[26]. In the neural-networks literature, clustering is commonly implemented by distortion-based competitive learning (CL) techniques [2], [27]–[31]where the prototypes correspond to the weights of neurons, e.g., the center of their receptive field in the input feature space. A common trait of these algorithms is a competitive stage which precedes each learning steps and decides to what extent a neuron may adapt its weights to a new input pattern [32]. The goal of competitive learning is the minimization of the distortion in clustering analysis or the quantization error in vector quantization.