论文部分内容阅读
谱聚类算法由与相似度函数相关的图Laplace算子的特征函数产生.本文证明与一般相似度函数相关的谱聚类算法的收敛性,并使用覆盖数方法对收敛性给出量化估计.当相似度函数是欧氏空间子集上一个Lipschitzs>0函数时,O((log(n+1))～(1/2)/n～(1/2))形式的收敛率得到证实.我们同时指出一个相应函数集的覆盖数的增长可以表现任意差.
The spectral clustering algorithm is generated by the eigenfunctions of the graph Laplacian operator which is related to the similarity function.This paper proves the convergence of the spectral clustering algorithm related to the general similarity function and gives a quantitative estimation of the convergence using the cover number method. The convergence rate of O ((log (n + 1)) ~ (1/2) / n ~ (1/2) is confirmed when the similarity function is a Lipschitzs> 0 function on the Euclidean space subset. We also point out that the growth of the number of coverings of a corresponding set of functions can show any difference.