摘要
经典的谱聚类算法包含两个步骤。(1)谱嵌入过程:求解Laplacian矩阵的特征值分解,得到分类指示矩阵的连续松弛解。(2)后处理过程:对谱嵌入连续松弛矩阵应用k-means或者谱旋转,得到最终的二值指示矩阵。由于有用信息的丢失,这种单独求解步骤不能保证最佳聚类结果。同时,谱聚类算法在处理大规模数据集时,存在聚类精度低、数据相似度矩阵存储开销大和Laplacian矩阵特征值分解计算复杂度高的问题。已有的联合谱聚类算法使用标准正交矩阵逼近非标准正交簇指示矩阵,这会导致较大的逼近误差。为了克服这一缺点,提出用一个改进的标准正交簇指示矩阵代替非正交指示矩阵,得到一个新的联合谱嵌入和谱旋转的谱聚类算法。因为两个标准正交矩阵更容易最小化,所以提出的算法可以取得更好的性能。进一步通过地标点方法对原始数据集进行稀疏特征表示,提出一种基于地标表示的联合谱嵌入和谱旋转算法(LJSESR),解决了大规模数据谱聚类的高效求解问题。实验结果表明,提出的LJSESR算法具有可行性和有效性。
Classical spectral clustering algorithms consist of two separate stages.One is spectral embedding,computing eigenvalue decomposition of a Laplacian matrix to obtain a relaxed continuous indication matrix.The other is post processing,applying k-means or spectral rotation to round the real matrix into the binary cluster indicator matrix.Such a separate scheme is not guaranteed to achieve jointly optimal result because of the loss of useful information.Meanwhile,there are difficulties of low clustering precision,high storage cost for the similarity matrix and high computational complexity for the eigenvalue decomposition of Laplacian matrix.The existing joint model adopts an orthonormal real matrix to approximate the orthogonal but nonorthonormal cluster indicator matrix.The error of approximating a nonorthonormal matrix is inevitably large.To overcome the drawback,we propose replacing the nonorthonormal cluster indicator matrix with an improved orthonormal cluster indicator matrix.The proposed method is capable of obtaining better performance because it is easy to minimize the difference between two orthonormal matrices.Furthermore,a novel landmark-based joint spectral embedding and spectral rotation algorithm is proposed based on the sparse representation by landmark points,which greatly solves the effective computation of spectral clustering for large scale dataset.Experimental results on benchmark datasets demonstrate the effectiveness of the proposed method.
作者
李鹏
刘力军
黄永东
LI Peng;LIU Li-jun;HUANG Yong-dong(School of Science,Dalian Minzu University,Dalian,Liaoning 116600,China)
出处
《计算机科学》
CSCD
北大核心
2021年第S01期220-225,共6页
Computer Science
基金
国家自然科学基金(61002039,61572018,11761001)。
关键词
谱聚类
谱旋转
谱嵌入
地标表示
联合谱聚类
Spectral clustering
Spectral rotation
Spectral embedding
Landmark representation
Joint spectral clustering
