标题： 连接谱聚类与最大边缘和水平集 显示英文标题

标题： Connecting Spectral Clustering to Maximum Margins and Level Sets

摘要： 我们研究了谱聚类与最大边缘聚类问题以及密度函数水平集分量估计之间的联系。具体来说，我们得到了图拉普拉斯矩阵特征向量关于簇间分离和簇内连通性的界。这些界确保了当缩放参数趋于零时，谱聚类解会收敛到最大边缘聚类解。最大边缘聚类解对离群点的敏感性是众所周知的，但可以通过首先移除这些离群点，然后对剩余点应用最大边缘聚类来缓解。如果使用潜在概率密度的估计来识别离群点，则剩余点可以被视为该密度函数的一个水平集的估计。我们证明了在非常温和的假设下，这种方法可以一致地估计密度函数水平集的分量。 显示英文摘要

摘要： We study the connections between spectral clustering and the problems of maximum margin clustering, and estimation of the components of level sets of a density function. Specifically, we obtain bounds on the eigenvectors of graph Laplacian matrices in terms of the between cluster separation, and within cluster connectivity. These bounds ensure that the spectral clustering solution converges to the maximum margin clustering solution as the scaling parameter is reduced towards zero. The sensitivity of maximum margin clustering solutions to outlying points is well known, but can be mitigated by first removing such outliers, and applying maximum margin clustering to the remaining points. If outliers are identified using an estimate of the underlying probability density, then the remaining points may be seen as an estimate of a level set of this density function. We show that such an approach can be used to consistently estimate the components of the level sets of a density function under very mild assumptions.