Dynamic Evolving Cluster Models Using Split-and-Merge Operations

In this paper, we propose a new dynamic split-andmerge concept for evolving prototype-based cluster models, i.e. cluster partitions which are incrementally learned and extended on-the-fly from data streams. New criteria when clusters should be merged are based on a touching and on a homogeneity condition between two ellipsoidal clusters, the merging itself is conducted by using weighted averaging of cluster centers and a convex combination of cluster spreads based on the recursive variance update concept. The splitting criterion for an updated cluster employs a 2-means algorithm on its sub-samples and compares the quality of the split cluster with the original cluster by using Bayesian information criterion; the cluster partition with the better quality remains for the next incremental update cycle. The results on 2-dimensional as well high-dimensional streaming clustering data sets show that the new split-and-merge concept is able to produce more reliable cluster partitions than conventional evolving clustering.