MONIC: modeling and monitoring cluster transitions

ABSTRACT

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. Our cluster transition model encompasses changes that involve more than one cluster, thus allowing for insights on cluster change in the whole clustering. 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. We present our first results on monitoring cluster transitions over the ACM digital library.

REFERENCES

• 1: Charu C. Aggarwal, On Change Diagnosis in Evolving Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.587-600, May 2005 [doi>10.1109/TKDE.2005.78]
• 2: S. Baron, M. Spiliopoulou, and O. Günther. Efficient monitoring of patterns in data mining environments. In Proc. of 7th East-European Conf. on Advances in Databases and Inf. Sys. (ADBIS'03), LNCS, pages 253--265. Springer, Sept. 2003.
• 3: Ilaria Bartolini , Paolo Ciaccia , Irene Ntoutsi , Marco Patella , Yannis Theodoridis, A unified and flexible framework for comparing simple and complex patterns, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.496-499, September 20-24, 2004, Pisa, Italy
• 4: C. Borgelt and A. Nürnberger. Experiments in Document Clustering using Cluster Specific Term Weights. In Proc. Workshop Machine Learning and Interaction for Text-based Information Retrieval (TIR 2004), pages 55--68, Ulm, Germany, 2004.
• 5: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 6: P. Kalnis, N. Mamoulis, and S. Bakiras. On Discovering Moving Clusters in Spatio-temporal Data. In Proc. of 9th Int. Symposium on Advances in Spatial and Temporal Databases (SSTD'2005), number 3633 in LNCS, pages 364--381, Angra dos Reis, Brazil, Aug. 2005. Springer.
• 7: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 8: Satoshi Morinaga , Kenji Yamanishi, Tracking dynamics of topic trends using a finite mixture model, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1016919]
• 9: R. Schult and M. Spiliopoulou. Discovering emerging topics in unlabelled text collections. In Proc. of ADBIS'2006, Thessaloniki, Greece, Sept. 2006. Springer. to appear.
• 10: I. H. Witten and E. Frank. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, San Fransisco, 2nd edition, 2005.
• 11: Hui Yang , Srinivasan Parthasarathy , Sameep Mehta, A generalized framework for mining spatio-temporal patterns in scientific data, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081962]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Theory

Keywords:
cluster change detection, cluster transitions, clusters, data streams, temporal analysis