Vector quantization based approximate spectral clustering of large datasets

Spectral partitioning, recently popular for unsupervised clustering, is infeasible for large datasets due to its computational complexity and memory requirement. Therefore, approximate spectral clustering of data representatives (selected by various sampling methods) was used. Alternatively, we propose to use neural networks (self-organizing maps and neural gas), which are shown successful in quantization with small distortion, as preliminary sampling for approximate spectral clustering (ASC). We show that they usually outperform k-means sampling (which was shown superior to various sampling methods), in terms of clustering accuracy obtained by ASC. More importantly, for quantization based ASC, we introduce a local density-based similarity measure – constructed without any user-set parameter – which achieves accuracies superior to the accuracies of commonly used distance based similarity.

► We use neural networks based quantization for approximate spectral clustering (ASC).
► Neural networks usually outperform k-means, in terms of clustering accuracy achieved by ASC.
► We propose a local density-based similarity, CONN (constructed without any parameter), for quantization prototypes.
► Compared to distance based similarity, CONN achieves superior accuracies for ASC.