Understanding Clusters' Evolution

Abstract

In this paper we are interested in the study of evolving data, whose distribution may be non-stationary.We address the problem of monitoring the evolution of clusters over time. We adopt two main strategies for cluster characterization - representation by enumeration and representation by comprehension -, and propose the MEC framework, which was developed along the lines of Change Mining paradigm. MEC includes a taxonomy of various types of clusters' transitions, a tracking mechanism that depends on the cluster representation, and a transition detection algorithm. Our tracking mechanism can be subdivided in two novel methods that were designed to monitor the evolution of clusters' structures: one based on graph transitions, and another based on the overlapping degree. These are the most relevant contributions of this work. We experimentally evaluate our framework with a real world case study.