Evolutionary spectral clustering by incorporating temporal smoothness

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 paper, 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.

REFERENCES

• 1: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, A framework for clustering evolving data streams, Proceedings of the 29th international conference on Very large data bases, p.81-92, September 09-12, 2003, Berlin, Germany
• 2: Francis R. Bach , Michael I. Jordan, Learning Spectral Clustering, With Application To Speech Separation, The Journal of Machine Learning Research, 7, p.1963-2001, 12/1/2006
• 3: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150467]
• 4: Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258657]
• 5: C. Chatfield. The Analysis of Time Series: An Introduction. Chapman & Hall/CRC.
• 6: F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
• 7: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, A Multilinear Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1253-1278, March – May 2000 [doi>10.1137/S0895479896305696]
• 8: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Kernel k-means: spectral clustering and normalized cuts, 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.1014118]
• 9: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 10: K. Fan. On a theorem of Weyl concerning eigenvalues of linear transformations. In Proc. Natl. Acad. Sci., 1949.
• 11: G. Golub and C. V. Loan. Matrix Computations. Johns Hopkins University Press, third edition, 1996.
• 12: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 13: C. Gupta and R. Grossman. Genic: A single pass generalized incremental algorithm for clustering. In SIAM Int. Conf. on Data Mining, 2004.
• 14: L. J. Hubert and P. Arabie. Comparing partitions. Journal of Classification, 2, 1985.
• 15: Xiang Ji , Wei Xu, Document clustering with prior knowledge, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148241]
• 16: Yifan Li , Jiawei Han , Jiong Yang, Clustering moving objects, 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.1014129]
• 17: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS,2001.
• 18: H. Ning, W. Xu, Y. Chi, Y. Gong, and T. Huang. Incremental spectral clustering with application to monitoring of evolving blog communities. In SIAM Int. Conf. on Data Mining, 2007.
• 19: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 20: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 21: Yair Weiss, Segmentation Using Eigenvectors: A Unifying View, Proceedings of the International Conference on Computer Vision-Volume 2, p.975, September 20-25, 1999
• 22: H. Zha, X. He, C. H. Q. Ding, M. Gu, and H. D. Simon. Spectral relaxation for k-means clustering. In NIPS, 2001.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
evolutionary spectral clustering, mining data streams, preserving cluster membership, temporal smoothness, treserving cluster quality