On evolutionary spectral clustering
- 1 November 2009
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 3 (4), 1-30
- https://doi.org/10.1145/1631162.1631165
Abstract
Evolutionary clustering is an emerging research area essential to important applications such as clustering dynamic Web and blog contents and clustering data streams. In evolutionary clustering, a good clustering result should fit the current data well, while simultaneously not deviate too dramatically from the recent history. To fulfill this dual purpose, a measure of temporal smoothness is integrated in the overall measure of clustering quality. In this article, we propose two frameworks that incorporate temporal smoothness in evolutionary spectral clustering. For both frameworks, we start with intuitions gained from the well-known k -means clustering problem, and then propose and solve corresponding cost functions for the evolutionary spectral clustering problems. Our solutions to the evolutionary spectral clustering problems provide more stable and consistent clustering results that are less sensitive to short-term noises while at the same time are adaptive to long-term cluster drifts. Furthermore, we demonstrate that our methods provide the optimal solutions to the relaxed versions of the corresponding evolutionary k -means clustering problems. Performance experiments over a number of real and synthetic data sets illustrate our evolutionary spectral clustering methods provide more robust clustering results that are not sensitive to noise and can adapt to data drifts.Keywords
This publication has 20 references indexed in Scilit:
- An event-based framework for characterizing the evolutionary behavior of interaction graphsPublished by Association for Computing Machinery (ACM) ,2007
- GraphScopePublished by Association for Computing Machinery (ACM) ,2007
- Evolutionary spectral clustering by incorporating temporal smoothnessPublished by Association for Computing Machinery (ACM) ,2007
- Quantifying social group evolutionNature, 2007
- Dynamic social network analysis using latent space modelsACM SIGKDD Explorations Newsletter, 2005
- Learning from labeled and unlabeled data on a directed graphPublished by Association for Computing Machinery (ACM) ,2005
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- A Multilinear Singular Value DecompositionSIAM Journal on Matrix Analysis and Applications, 2000
- Comparing partitionsJournal of Classification, 1985
- On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations IProceedings of the National Academy of Sciences of the United States of America, 1949