evoStream — Evolutionary Stream Clustering Utilizing Idle Times

Clustering is an important field in data mining that aims to reveal hidden patterns in data sets. It is widely popular in marketing or medical applications and used to identify groups of similar objects. Clustering possibly unbounded and evolving data streams is of particular interest due to the widespread deployment of large and fast data sources such as sensors. The vast majority of stream clustering algorithms employ a two-phase approach where the stream is first summarized in an online phase. Upon request, an offline phase reclusters the aggregations into the final clusters. In this setup, the online component will idle and wait for the next observation in times where the stream is slow. This paper proposes a new stream clustering algorithm called evoStream which performs evolutionary optimization in the idle times of the online phase to incrementally build and refine the final clusters. Since the online phase would idle otherwise, our approach does not reduce the processing speed while effectively removing the computational overhead of the offline phase. In extensive experiments on real data streams we show that the proposed algorithm allows to output clusters of high quality at any time within the stream without the need for additional computational resources.