ICMLJun, 2024

带有可证明近似保证的动态谱聚类

PDF
TL;DR该研究论文探讨了用于动态演变图的聚类算法，证明了在某些簇结构的条件下，最终图的簇可以被谱聚类算法的动态变体很好地近似，并运行时间复杂度为 O (1) 和查询时间复杂度为 o (n_T)，实验证明了该算法的实用性。
clustering algorithmsdynamically evolving graphsspectral clustering algorithmamortised update timereal-world datasets
发现论文，激发创造
  • 理论与实践中的快速简单谱聚类

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

    Oct, 2023

  • 动态随机块模型的谱聚类：稀疏平滑性的改进保证

    该论文分析了动态随机块模型下的经典谱聚类算法，提出了更加精细的 DSGB 的稀疏性和平滑度之间的关系描述，同时将保证扩展到了归一化拉普拉斯算子，从而提高了矩阵谱集中度误差下界的精度。

    Feb, 2020

  • 小批量谱聚类

    采用自适应随机梯度优化的实用方法可以学习拉普拉斯矩阵的完整光谱，且每个迭代的成本与样本数量成线性关系，实验证明其具备比近似方法更好的计算可扩展性。

    Jul, 2016

  • 基于时间标签平滑性的时变图聚类

    本文提出一种基于时间变化图的节点聚类方法，其假设聚类标签在时间上平滑变化。采用基于谱聚类的优化问题公式来解决节点聚类问题，增加了标签平滑约束条件，然后采用原始双重分割算法来解决，实验结果表明，该方法是有效的。

    May, 2023

  • 动态随机块模型中的谱聚类

    本文介绍了一种基于 Dynamic Stochastic Block Model（DSBM）的方法，使用核函数估计边缘概率张量并进行谱聚类，可适应未知的连续时间点连接概率平滑度、群体成员转换率和聚类数目，并伴随着对估计精度和聚类结果的非渐进性保证。

    May, 2017

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

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

    Aug, 2022

  • 基于局部线性逼近的谱聚类

    本文研究了一种基于局部线性逼近残差的高阶谱聚类方法，考虑了聚类过程中的数据噪声和异常值问题，并在实验中验证了该算法具有更好的聚类效果。

    Jan, 2010

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012

  • 子线性时间下的谱聚类预测器

    本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

    Jan, 2021

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

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

    Apr, 2010