Fast in-memory spectral clustering using a fixed-size approach
Rocco Langone, Raghvendra Mall, Vilen Jumutc, Johan A. K. Suykens · Lirias · 2016
Spectral clustering represents a successful approach to data clustering. Despite its high performance in solving complex tasks, it is often disregarded in favor of the less accurate k-means algorithm because of its computational inefficiency. In this article we present a fast in-memory spectral clustering algorithm, which can handle millions of datapoints at a desktop PC scale. The proposed technique relies on a kernel-based formulation of the spectral clustering problem, also known as kernel spectral clustering. In particular, we use a fixed-size approach based on an approximation of the feature map via the Nyström method to solve the primal optimization problem. We experimented on several small and large scale real-world datasets to show the computational efficiency and clustering quality of the proposed algorithm.