MONIC at a glance

There is much recent work on detecting and tracking change in clusters, often based on the study of the spatiotemporal properties of a cluster. For the many applications where cluster change is relevant, among them customer relationship management, fraud detection and marketing, it is also necessary to provide insights about the nature of cluster change: Is a cluster corresponding to a group of customers simply disappearing or are its members migrating to other clusters? Is a new emerging cluster reflecting a new target group of customers or does it rather consist of existing customers whose preferences shift?

To answer such questions, we propose the framework MONIC for modeling and tracking of cluster transitions over time. Our cluster transition model encompasses changes that involve more than one cluster, thus allowing for insights on cluster change in the whole clustering. In MONIC, a cluster transition at a given time point is a change experienced by a cluster that has been discovered at an earlier time point. Such a transition may concern the content and form of the cluster itself i.e. be an "internal transition" to it, or it may concern its relationship to the rest of the clustering, i.e. be an "external transition". We define these types of transitions and introduce heuristics that trace them. Our transition tracking mechanism is not based on the topological properties of clusters, which are only available for some types of clustering, but on the contents of the underlying data stream.

MONIC was originally published in [1]; an extended version was published in [2]. The original transitions in MONIC are independent of the clustering algorithm since they rely on cluster members. MONIC for different cluster types was published in [3] and also in [4]. MONIC was part of my PhD, so further details can be also found in [5] (Chapter 6). The original MONIC was applied over numerical data and text data. MONIC has been successfully applied in social networks monitoring (e.g. [6]). Based on MONIC transitions we have lately proposed the FINGERPRINT framework for the efficient and effective maintenance of cluster changes in an evolving environment like data streams [7].

Related publications

1.	M. Spiliopoulou, E. Ntoutsi, Y. Theodoridis and R. Schult "MONIC - Modeling and Monitoring Cluster Transitions", Proc. of 12th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD'06), Philadelphia, USA, 2006. [pdf]
2.	M. Spiliopoulou, E. Ntoutsi, Y. Theodoridis and R. Schult "The MONIC framework for Cluster Transition Detection", 5th Hellenic Data Management Symposium (HDMS'06), Thessaloniki, Greece, 2006. [pdf]
3.	M. Spiliopoulou, E. Ntoutsi, Y. Theodoridis "Tracing Cluster Transitions for Different Cluster Types", 3rd ADBIS Workshop on Data Mining and Knowledge Discovery (ADMKD'07), Varna, Bulgaria, 2007.
4.	E. Ntoutsi, M. Spiliopoulou, Y. Theodoridis "Tracing cluster transitions for different cluster types", Control and Cybernetics Journal, 38(1):239-260, 2009. Polish Academy of Sciences.
5.	E. Ntoutsi "Similarity Issues in Data Mining - Methodologies and Techniques". PhD thesis, Department of Informatics, University of Piraeus, Greece, 2008. [pdf] (In Greek also [pdf])
6.	T. Falkowski, M. Spiliopoulou "Users in Volatile Communities: Studying Active Participation and Community Evolution", Proc. of 11th Int. Conf. on User Modeling (UM '07), Corfu, Greece, 2007.
7.	E. Ntoutsi, M. Spiliopoulou, Y. Theodoridis "Summarizing Cluster Evolution in Dynamic Environments", Proc. of 11th International Conference on Computational Science and Its Applications (ICCSA'11), Santander, Spain, 2011. [pdf] [ppt]
8.	E. Ntoutsi, M. Spiliopoulou, Y. Theodoridis "FINGERPRINT - Summarizing Cluster Evolution in Dynamic Environments", Int’l Journal of Data Warehousing and Mining (IJDWM), 8(3):27-45, July-September 2012. Idea Group. [bib]
9.	M. Spiliopoulou, E. Ntoutsi, Y. Theodoridis and R. Schult " MONIC and Followups on Modeling and Monitoring Cluster Transitions.", European Conference on “Machine Learning” and “Principles and Practice of Knowledge Discovery in Databases”, Nectar track (ECML-PKDD), September 23-27, Prague, Czech Republic (to appear).

Implementation

MONIC has been implemented in Java. It can be downloaded from here. FINGERPRINT code can be found here, it also includes the basic MONIC algorithm.

Contact us

Please contact us for further details.
- M. Spiliopoulou, University of Magdeburg, Germany (myra@iti.cs.unimagdeburg.de)
- E. Ntoutsi, Ludwig-Maximilians University of Munich (LMU), Germany (ntoutsi@dbs.ifi.lmu.de)
- Y. Theodoridis, University of Pireus, Greece (ytheod@unipi.gr)
- R. Schult, University of Magdeburg, Germany (schult@iti.cs.unimagdeburg.de)