本研究提出了一种基于顶点嵌入的简单谱聚类算法,通过幂法计算的向量,在接近线性时间内计算顶点嵌入,并在输入图形的自然假设下,算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现,该算法与其他聚类算法相比,具有显著更快的速度,并且产生的聚类准确度基本相同。
Oct, 2023
本文探讨了如何用非线性特征值问题来解决与机器学习和统计相关的约束优化问题, 并提出了一个新型的逆幂方法来解决这些问题,在 1 - 谱聚类和稀疏 PCA 的应用中取得了最先进的解决方案。
Dec, 2010
本研究针对典型的谱聚类算法,探讨在一些较弱条件下其性能为何,还研究了利用少于 k 个特征向量进行嵌入的谱聚类,实验表明在合成和真实数据上,使用少于 k 个特征向量时,谱聚类也能够产生相当或更好的结果。
Aug, 2022
本文提出了一种基于图信号处理的方法,采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤,该方法在控制误差的同时计算时间效率可达到数个数量级的提升,并在人工合成数据和真实网络数据集上进行测试。
Feb, 2016
本文通过对核谱聚类方法进行首次分析,发现在维度和数量同时增长的情况下,核矩阵的归一化拉普拉斯矩阵与所谓的尖峰随机矩阵呈类似的渐近行为。通过一种如尖峰矩阵模型的可分离条件,证明该模型中的一些孤立特征值 - 特征向量对携带聚类信息。我们精确评估了这些特征值的位置和特征向量内容,在理论和实践角度揭示了核谱聚类中非常重要(有时相当破坏性)的方面。最后将结果与 MNIST 数据库中图像实际聚类的性能进行比较,证明了理论和实践之间的重要匹配。
Oct, 2015
该研究提出了使用一种带有参数的拉普拉斯变换簇集算法来处理有正有负关系的图结构,并在多个模型中取得了比当前领先技术更好的聚类效果。
May, 2019
本文研究了如何对多层图进行聚类,引入了一种参数化的矩阵幂均值来合并不同层的拉普拉斯矩阵,并在随机块模型中分析它。我们证明了这种方法可以在不同设置下恢复地面真实聚类并在实际世界数据中验证。而对于大型图形计算矩阵幂均值可能非常昂贵,我们引入了一种计算其特征向量的数值方案,以便用于大型稀疏图形的情况。
Mar, 2018
本文提出了一种基于稀疏图构造的简单和通用的算法,称为图构建,它通过处理稀疏的 ER 和 SBM 图可以更规范地去除干扰性特征值,并且与先前的光谱算法相比在纠结和团块方面表现更加鲁棒。
Sep, 2018
该论文介绍了谱聚类算法和图拉普拉斯的基本性质,推导了不同的谱聚类算法,比较了它们之间的优缺点。
Nov, 2007
该研究探讨了一种可并行化的方法,通过对大型图的频谱进行扩展,以加速奇异值分解求解器和谱聚类,并利用多项式逼近来实现此目的。
Jul, 2022