Title: Entropy-based Incomplete Cholesky Decomposition for a Scalable Spectral Clustering Algorithm
Authors: Langone, Rocco ×
Van Barel, Marc
Suykens, Johan #
Issue Date: 2016
Publisher: Molecular Diversity Preservation International
Series Title: Entropy
Abstract: Spectral clustering methods allow to partition a dataset into clusters by mapping the input datapoints into the space spanned by the eigenvectors of the Laplacian matrix. In this article we make use of the incomplete Cholesky decomposition (ICD) to construct an approximation of the graph Laplacian and reduce the size of the related eigenvalue problem from N to m, with m ≪ N. In particular, we introduce a new stopping criterion based on normalized mutual information between consecutive partitions, which terminates the ICD when the change in the cluster assignments is below a given threshold. Compared with existing ICD-based spectral clustering approaches, the proposed method allows to reduce the number m of selected pivots (i.e. to obtain a sparser model) and at the same time to maintain high clustering quality. The method scales linearly with respect to the number of input datapoints N and has low memory requirements because only matrices of size N × m and m × m are calculated (in contrast to standard spectral clustering where the construction of the full N × N similarity matrix is needed). Furthermore, we show that the number of clusters can be reliably selected based on the gap heuristics computed using just a small matrix R of size m × m instead of the entire graph Laplacian. The effectiveness of the proposed algorithm is tested on several datasets.
ISSN: 1099-4300
Publication status: accepted
KU Leuven publication type: IT
Appears in Collections:Numerical Analysis and Applied Mathematics Section
ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
ICD_entropy.pdf Submitted 1841KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.