×

Convergence of spectral clustering with a general similarity function. (Chinese. English summary) Zbl 1488.68043

Summary: Spectral clustering algorithms are generated by eigenfunctions of graph Laplacians associated with similarity functions. In this paper, we prove the convergence of the spectral clustering associated with a general similarity function, and give quantitative estimates for the convergence based on a covering number argument. When the similarity function is Lipschitz \(s>0\) on a subset of a Euclidean space, a convergence rate of \(O(\sqrt{\log(n+1)}/\sqrt{n})\) is verified. We also show that the covering numbers of an involved function set may behave as badly as possible.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
62H30 Classification and discrimination; cluster analysis (statistical aspects)
PDFBibTeX XMLCite
Full Text: DOI