Streaming spectral clustering
Shinjae Yoo, Hao Huang, Shiva Prasad Kasiviswanathan · 2016
Clustering is a classical data mining task used for discovering interrelated pattern of similarities in the data. In many modern day domains, data is getting continuously generated as a stream. For scalability reasons, clustering the points in a data stream requires designing single pass, limited memory streaming clustering algorithms. However, the performance of the known streaming clustering algorithms, that typically use K-means (or its variants) on the original feature space, tend to suffer when the feature space is high-dimensional. To overcome this problem, we propose a streaming spectral clustering algorithm. Our algorithm maintains an approximation of the normalized Laplacian of the data stream over time and efficiently updates the changing eigenvectors of this Laplacian in a streaming fashion. It requires just one pass over the data, consumes limited memory, and is stable to the ordering of the data stream. We provide a theoretical analysis of our streaming spectral clustering algorithm and our experimental results show that while gaining in scalability, its performance compares well with other known batch/streaming clustering approaches.