Efficient evolutionary spectral clustering

doi:10.1016/j.patrec.2016.08.012

Return

Efficient evolutionary spectral clustering

2016-12-01

PRE

Rocco Langone *

Marc Van Barel

Johan A. K. Suykens

DOI：10.1016/j.patrec.2016.08.012

Original

Original request for help

Save

Abstract

En 中文

Evolutionary spectral clustering (ESC) represents a state-of-the-art algorithm for grouping objects evolving over time. It typically outperforms traditional static clustering by producing clustering results that can adapt to data drifts while being robust to short-term noise. A major drawback of ESC is given by its cubic complexity, e. g. O(N-3), and high memory demand, namely O(N-2), that make it unfeasible to handle datasets characterized by a large number N of patterns. In this paper, we propose a solution to this issue by presenting the efficient evolutionary spectral clustering algorithm (E2SC). First we introduce the notion of a smoothed graph Laplacian, then we exploit the incomplete Cholesky decomposition (ICD) to construct an approximation of the this smoothed Laplacian and reduce the size of the related eigenvalue problem from N to m, with m << N. Furthermore, in contrast to the standard ICD algorithm, a stopping criterion based on the convergence of the cluster assignments after the selection of each pivot is used, which is effective also when there is not a fast decay of the Laplacian spectrum. Overall, the proposed approach scales linearly with respect to the number of input datapoints N and has low memory requirements because only matrices of size N x m and m x m are constructed. (C) 2016 Elsevier B. V. All rights reserved.

Keywords:

Evolutionary spectral clustering

Incomplete Cholesky decomposition

Linear complexity

Temporal smoothness

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.