关键词: 谱聚类, 判别割算法, 主成分分析, 图像分割

Abstract: Spectral clustering algorithms can cluster samples in any form of feature space and has global optimal solutions. However, Discriminant cut (Dcut) algorithm is time-consuming when calculating the regularization similarity matrix and its eigenvectors and Dcut based Subspace (SDcut) algorithm is unstable. Concerning these problems, the paper proposed an improved Dcut algorithm based on Principal Component Analysis (PCA), named PCA-Dcut. PCA-Dcut algorithm constructed a new matrix using the m eigenvectors corresponding to the m largest eigenvalues of the similarity matrix, then used matrix computation between the constructed matrix with the similarity matrix and Laplacian matrix respectively, and got an m-order regularization similarity matrix, and calculated its eigenvectors, then used the constructed matrix to multiply the eigenvectors to get the final feature vectors for classification. Therefore, PCA-Dcut reduces the computational complexity of Dcut. The experiments on man-made data set, UCI data set and real images show that the PCA-Dcut algorithm is comparable with other spectral clustering algorithms such as Dcut in accuracy, and its running speed is 5.4 times of Dcut, and has faster speed and better performance compared with SDcut.

Key words: spectral clustering, Discriminant cut (Dcut) algorithm, Principal Component Analysis (PCA), image segmentation