Fast Large-Scale Spectral Clustering via Explicit Feature Mapping
Lists
Only you see this
Abstract
We propose an efficient spectral clustering method for large-scale data. The main idea in our method consists of employing random Fourier features to explicitly represent data in kernel space. The complexity of spectral clustering thus is shown lower than existing Nyström approximations on largescale data. With m training points from a total of n data points, Nyström method requires O(nmd + m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> + nm <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) operations, where d is the input dimension. In contrast, our proposed method requires O(nDd + D <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> + n'D <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), where n' is the number of data points needed until convergence and D is the kernel mapped dimension. In large-scale datasets where n ≪ n hold true, our explicitly mapping method can significantly speed up eigenvector approximation and benefit prediction speed in spectral clustering. For instance, on MNIST (60000 data points), the proposed method is similar in clustering accuracy to Nyström methods while its speed is twice as fast as Nyström.
BibTeX
@article{he2019fast,
author = {Li He and Nilanjan Ray and Yisheng Guan and Hong Zhang},
title = {{Fast Large-Scale Spectral Clustering via Explicit Feature Mapping}},
journal = {IEEE Trans. Cybernetics},
year = {2019},
url = {https://openreview.net/forum?id=xYrTPZ3DbJX},
}Loading related content...