Iterative ensemble normalized cuts

•We provide a novel interpretation of the gap-view concept in NCut.•We improve NCut by assembling out-of-sample extensions of multiple training sets.•We speed up the clustering method by employing an iterative algorithm.•Our proposed algorithm performs better than the state-of-the-art algorithms.

A fast spectral clustering method is proposed. Eigenvectors used in NCut are studied as the gap-normalized distances defined in this paper. The out-of-sample extensions of NCut are derived by extending the gap-normalized distances to new data, which is interestingly found to be perfectly matched with the Nyström-based eigenfunction approximation. From the view of gap-normalized distance, the ensemble NCut method is built by assembling distances of small groups to learn the partitions of the entire dataset. By iteratively calling such assembly, the iterative ensemble NCut method is proposed. Experiments on real world datasets and the image segmentation tasks show that, compared with the state-of-the-art, the proposed IENCut method produces improved clustering quality although this improvement may sometimes come at the expense of increased processing time.