与一般相似度函数相关的谱聚类的收敛性

谱聚类算法由与相似度函数相关的图Laplace 算子的特征函数产生. 本文证明与一般相似度函数相关的谱聚类算法的收敛性, 并使用覆盖数方法对收敛性给出量化估计. 当相似度函数是欧氏空间子集上一个Lipschitz s > 0 函数时, O(√log(n + 1)/√n) 形式的收敛率得到证实. 我们同时指出一个相应函数集的覆盖数的增长可以表现任意差.

Convergence of spectral clustering with a general similarity function

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（（log（n＋1））～（1/2）/n～（1/2）） is verified.We also show that the covering numbers of an involved function set may behave as badly as possible.