Abstract
Monitoring and interpretation of changing patterns is a task of paramount importance for data mining applications in dynamic environments. While there is much research in adapting patterns in the presence of drift or shift, there is less research on how to maintain an overview of pattern changes over time. A major challenge lays in summarizing changes in an effective way, so that the nature of change can be understood by the user, while the demand on resources remains low. To this end, we propose FINGERPRINT, an environment for the summarization of cluster evolution. Cluster changes are captured into an “evolution graph”, which is then summarized based on cluster similarity into a fingerprint of evolution by merging similar clusters. We propose a batch summarization method that traverses and summarizes the Evolution Graph as a whole, and an incremental method that is applied during the process of cluster transition discovery. We present experiments on different data streams and discuss the space reduction and information preservation achieved by the two methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, C.C.: On change diagnosis in evolving data streams. IEEE Trans. Knowl. Data Eng. 17(5), 587–600 (2005)
Aggarwal, C.C., Han, J., Wang, J., Yu, P.: A framework for clustering evolving data streams. In: VLDB (2003)
Aggarwal, C.C., Yu, P.S.: A framework for clustering massive text and categorical data streams. SIAM Data Mining Conf. (2006)
Bartolini, I., Ciaccia, P., Ntoutsi, I., Patella, M., Theodoridis, Y.: A unified and flexible framework for comparing simple and complex patterns. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 496–499. Springer, Heidelberg (2004)
Cao, F., Ester, M., Qian, W., Zhou, A.: Density-based clustering over an evolving data stream with noise. In: SDM 2006 (2006)
Chandola, V., Kumar, V.: Summarization – compressing data into an informative representation. In: ICDM (2005)
Chen, Y., Tu, L.: Density-based clustering for real-time stream data. In: KDD, pp. 133–142 (2007)
Farnstrom, F., Lewis, J., Elkan, C.: Scalability for clustering algorithms revisited. SIGKDD Explorations 2(1), 51–57 (2000)
Gama, J.: Knowledge Discovery from Data Streams. CRC Press, Boca Raton (2010)
Ipeirotis, P.G., Ntoulas, A., Cho, J., Gravano, L.: Modeling and managing content changes in text databases. In: ICDE, pp. 606–617 (2005)
Kalnis, P., Mamoulis, N., Bakiras, S.: On discovering moving clusters in spatio-temporal data. In: Anshelevich, E., Egenhofer, M.J., Hwang, J. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 364–381. Springer, Heidelberg (2005)
Mei, Q., Zhai, C.: Discovering evolutionary theme patterns from text: an exploration of temporal text mining. In: KDD, pp. 198–207 (2005)
Spiliopoulou, M., Ntoutsi, I., Theodoridis, Y., Schult, R.: Monic: Mdeling and Monitoring Cluster Transitions. In: KDD, pp. 706–711 (2006)
Yang, H., Parthasarathy, S., Mehta, S.: A generalized framework for mining spatio-temporal patterns in scientific data. In: KDD 2005 (2005)
Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: An efficient data clustering method for very large databases. In: SIGMOD 1996, pp. 103–114 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ntoutsi, I., Spiliopoulou, M., Theodoridis, Y. (2011). Summarizing Cluster Evolution in Dynamic Environments. In: Murgante, B., Gervasi, O., Iglesias, A., Taniar, D., Apduhan, B.O. (eds) Computational Science and Its Applications - ICCSA 2011. ICCSA 2011. Lecture Notes in Computer Science, vol 6783. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21887-3_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-21887-3_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21886-6
Online ISBN: 978-3-642-21887-3
eBook Packages: Computer ScienceComputer Science (R0)