大维数据的核谱聚类

Oct, 2015

Kernel spectral clustering of large dimensional data

Romain Couillet, Florent Benaych-Georges

TL;DR本文通过对核谱聚类方法进行首次分析，发现在维度和数量同时增长的情况下，核矩阵的归一化拉普拉斯矩阵与所谓的尖峰随机矩阵呈类似的渐近行为。通过一种如尖峰矩阵模型的可分离条件，证明该模型中的一些孤立特征值 - 特征向量对携带聚类信息。我们精确评估了这些特征值的位置和特征向量内容，在理论和实践角度揭示了核谱聚类中非常重要（有时相当破坏性）的方面。最后将结果与 MNIST 数据库中图像实际聚类的性能进行比较，证明了理论和实践之间的重要匹配。

Abstract

This article proposes a first analysis of kernel spectral clustering methods in the regime where the dimension $p$ of the data vectors to be clustered and their number $n$ grow large at the same rate. We demonstrate, under a $k$-class Gaussian mixture model, that the →

kernel spectral clustering normalized laplacian matrix spiked random matrix clustering information mnist database

发现论文，激发创造

核随机矩阵的光谱

在高维统计推断中，通过分析核随机矩阵的谱，发现在某些模型情况下，非线性主成分分析的问题本质上是线性问题，这与现有的一些启发式方法不符。同时，该研究还凸显了随机矩阵理论中广泛研究的某些奇异性，并对其在实际高维数据建模工具中的相关性提出了一些问题。

Jan, 2010

谱聚类中特征向量的渐近高斯波动

通过对相似性矩阵的特征向量的波动性进行建模，证明了在大维空间中其元素的波动服从高斯分布，从而精确预测了谱聚类的分类性能。通过对合成数据和真实数据的数值实验，证明了这一现象的普适性。

Feb, 2024

用于大规模图聚类的随机并行可分解特征值间隔扩张

该研究探讨了一种可并行化的方法，通过对大型图的频谱进行扩展，以加速奇异值分解求解器和谱聚类，并利用多项式逼近来实现此目的。

Jul, 2022

通过幂法的谱聚类 —— 可证明性

本文通过理论分析证明，在光谱聚类时，使用小量的幂迭代即可通过近似特征向量来达到接近最优的 K-means 聚类结果。

Nov, 2013

谱聚类的更紧密分析，以及更多

本研究针对典型的谱聚类算法，探讨在一些较弱条件下其性能为何，还研究了利用少于 k 个特征向量进行嵌入的谱聚类，实验表明在合成和真实数据上，使用少于 k 个特征向量时，谱聚类也能够产生相当或更好的结果。

Aug, 2022

带谱范数和 k-means 算法的聚类

该论文证明了一个简单的聚类算法可以在不假设任何生成模型的情况下运作，只需要假定一种叫做 “接近条件” 的规律。该算法依赖于著名的 k-means 算法，能够产生大多数现有生成模型的结果，同时提出了一种新的技术来提高间距与标准差之比。

Apr, 2010

随机内积核矩阵的谱

在 “大 p、大 n” 条件下，研究了随机核矩阵的特征值分布，发现针对非平滑核函数，其极限谱密度的分布不同于以前研究的 Marcenko-Pastur 分布。

Feb, 2012

压缩谱聚类

本文提出了一种基于图信号处理的方法，采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤，该方法在控制误差的同时计算时间效率可达到数个数量级的提升，并在人工合成数据和真实网络数据集上进行测试。

Feb, 2016

Fokker-Planck 算子的扩散映射，谱聚类和特征函数

该论文提出了一种基于扩散的谱聚类和降维算法的概率解释，利用规范化图拉普拉斯算子的特征向量。通过定义数据点之间的扩散距离，并证明了对应马尔科夫矩阵的前几个特征向量的低维表示在一定均方误差标准下是最佳的。此外，假设数据点是从密度 $p (x)=e^{-U (x)}$ 中随机抽取的，作者将这些特征向量视为具有反射边界条件下潜在 $2U (x)$ 力学势中福克 - 普朗克算子的离散近似的本征函数。最后，应用已知结果，对连续福克 - 普朗克算子的本征值和本征函数进行解析，从而为基于前几个特征向量的谱聚类和降维算法的成功提供了数学论证。这项分析阐明了许多经验发现关于谱聚类算法的特征和扩散进程。

Jun, 2005

理论与实践中的快速简单谱聚类

本研究提出了一种基于顶点嵌入的简单谱聚类算法，通过幂法计算的向量，在接近线性时间内计算顶点嵌入，并在输入图形的自然假设下，算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现，该算法与其他聚类算法相比，具有显著更快的速度，并且产生的聚类准确度基本相同。

Oct, 2023