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

作者：高炜; 周定轩

来源：中国科学:数学 , 2012, (10): 985-994.

• 谱聚类
• 图Laplace算子
• 相似度函数
• 收敛率
• 覆盖数 spectral clustering
• graph Laplacian
• similarity function
• rate of convergence
• covering number

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

• 单位
  苏州大学; 香港城市大学