超大规模谱聚类和集成聚类

本文重点关注在资源有限的情况下，针对极大规模数据集的谱聚类的可扩展性和鲁棒性。提出了两种新颖的算法，即超可扩展谱聚类（U-SPEC）和超可扩展集成聚类（U-SENC）。在U-SPEC中，提出了一种混合代表选择策略以及K最近代表的快速近似方法，用于构建稀疏相似度子矩阵。通过将稀疏子矩阵解释为二部图，利用传递切割法高效地对图进行划分并获得聚类结果。在U-SENC中，进一步将多个U-SPEC聚类器集成到一个集成聚类框架中，以增强U-SPEC的鲁棒性同时保持高效率。基于通过多个U-SEPC生成的集成，构建了一个新的对象与基础聚类之间的二部图，并对其进行高效划分以实现共识聚类结果。值得注意的是，U-SPEC和U-SENC都具有接近线性的时空复杂度，并且能够在配备64GB内存的个人计算机上稳健高效地对千万级别的非线性可分数据集进行划分。各种大规模数据集上的实验表明了我们算法的可扩展性和鲁棒性。MATLAB代码和实验数据可在https://www.researchgate.net/publication/330760669 获取。