基于稀疏重构的超图谱聚类方法

Hypergraph Spectral Clustering with Sparse Representation

超图谱聚类方法由于能很好地描述数据点间的高阶信息,近年来受到了广泛的关注。不同于传统图结构,超图结构中的超边不是两两数据点间的连接,而是一组具有某种相同特性的数据子集。在实际应用中,常用K-近邻来构建超图中的超边,因此,并没有考虑到数据内在的关联性。提出一种新的基于稀疏重构的超图构建方法。对每一样本,用稀疏表示来找到与其最有关联的近邻样本,以此形成基于稀疏重构的超图模型,使得每个超边内的样本都具有很强的关联性。最后通过对超图拉普拉斯矩阵进行谱分解得到聚类结果。在人脸数据库、手写体数据库上的实验结果验证了算法的有效性。

Hypergraph spectral clustering method attracts much attention,because it can effectively describe high-order information among the data. Different from traditional graph model, hyperedge in hypergraph is not a pair-wise link be- tween two data points, while it is a subset of data points sharing with some attribute. In practices, hyperedge is usually built by simple K-NN clustering, so it does not consider inherent relationship among the data. We proposed a new hy- pergraph spectral clustering algorithm with sparse representation. For each data point,sparse representation was used to seek its related neighbors to form a hyperedge, so the data points in a hyperedge have strong dependency. Finally, the spectral decomposition was performed on the Laplace matrix of the hypergraph to obtain the clustering result. Extensive experiments on face database and handwriting database demonstrate the effectiveness of the proposed method.