|
使用随机二进制特征的可扩展光谱聚类
Scalable Spectral Clustering Using Random Binning Features |
|
| |
| 课程网址: |
http://videolectures.net/kdd2018_chen_scalable_spectral/
|
| 主讲教师: |
Pin-Yu Chen
|
| 开课单位: |
沃森研究中心
|
| 开课时间: |
2018-11-23
|
| 课程语种: |
英语
|
| 中文简介: |
光谱聚类是捕获数据中隐藏的聚类结构的最有效的聚类方法之一。然而，由于其在构造相似图和计算后续特征分解时的二次复杂性，它不能很好地扩展到大规模问题。尽管已经提出了许多方法来加速光谱聚类，但大多数方法都会在原始数据中减少大量信息损失，以减少计算瓶颈。在本文中，我们提出了一种新的可扩展光谱聚类方法，该方法使用随机二进制特征（RB）来同时加速相似度图的构建和特征分解。具体来说，我们通过RB生成的大型稀疏特征矩阵的内积来隐式地近似图相似性（核）矩阵。然后，我们引入了最先进的SVD解算器，以有效地计算这个大矩阵的特征向量，用于光谱聚类。使用这两个构建块，我们将数据点数量的计算成本从二次减少到线性，同时实现了类似的精度。我们的理论分析表明，与标准随机特征近似相比，通过RB进行的光谱聚类更快地收敛到精确的光谱聚类。在8个基准测试上的大量实验表明，所提出的方法在准确性和运行时间方面都优于或匹配最先进的方法。此外，我们的方法在数据样本数量和RB特征数量方面都表现出线性可伸缩性。
|
| 课程简介: |
Spectral clustering is one of the most effective clustering approaches that capture hidden cluster structures in the data. However, it does not scale well to large-scale problems due to its quadratic complexity in constructing similarity graphs and computing subsequent eigendecomposition. Although a number of methods have been proposed to accelerate spectral clustering, most of them compromise considerable information loss in the original data for reducing computational bottlenecks. In this paper, we present a novel scalable spectral clustering method using Random Binning features (RB) to simultaneously accelerate both similarity graph construction and the eigendecomposition. Specifically, we implicitly approximate the graph similarity (kernel) matrix by the inner product of a large sparse feature matrix generated by RB. Then we introduce a state-of-the-art SVD solver to effectively compute eigenvectors of this large matrix for spectral clustering. Using these two building blocks, we reduce the computational cost from quadratic to linear in the number of data points while achieving similar accuracy. Our theoretical analysis shows that spectral clustering via RB converges faster to the exact spectral clustering than the standard Random Feature approximation. Extensive experiments on 8 benchmarks show that the proposed method either outperforms or matches the state-of-the-art methods in both accuracy and runtime. Moreover, our method exhibits linear scalability in both the number of data samples and the number of RB features.
|
| 关 键 词: |
光谱聚类是捕获数据; 最有效的聚类方法; 随机二进制特征; 大矩阵的特征向量
|
| 课程来源: |
视频讲座网
|
| 数据采集: |
2023-01-24：cyh
|
| 最后编审: |
2023-01-24：cyh
|
| 阅读次数: |
30
|
|
图 书 馆