使用随机分箱特征的可扩展谱聚类

谱聚类是一种捕捉数据中隐藏聚类结构的有效方法。然而，由于在构建相似图和计算后续特征值分解时具有二次复杂度，它在大规模问题上的扩展性较差。尽管已提出多种加速谱聚类的方法，但大多数方法为了减少计算瓶颈而牺牲了原始数据中的大量信息。本文提出了一种基于随机分箱特征（Random Binning features, RB）的新型可扩展谱聚类方法，该方法同时加速相似图的构建和特征值分解。具体而言，我们通过RB生成的大规模稀疏特征矩阵的内积来隐式近似图相似（核）矩阵。然后，我们引入了一种先进的奇异值分解（SVD）求解器，以高效地计算该大规模矩阵的特征向量用于谱聚类。利用这两个关键组件，我们将计算成本从数据点数的二次复杂度降低到线性复杂度，同时保持了类似的准确性。我们的理论分析表明，通过RB进行的谱聚类比标准随机特征近似更快地收敛到精确的谱聚类结果。广泛的实验测试表明，在8个基准数据集上，所提出的方法在准确性和运行时间方面均优于或匹配现有最先进的方法。此外，我们的方法在数据样本数量和RB特征数量上表现出线性的可扩展性。