Improved spectral clustering using PCA based similarity measure on different Laplacian graphs

摘要

In data mining, clustering is one of the most significant task, and has been widely used in pattern recognition and image processing. One of the tradition and most widely used clustering algorithm is k-Means clustering algorithm, but this algorithm fails to find structural similarity in the data or if the data is non-linear. Spectral clustering is a graph clustering method in which the nodes are clustered and useful if the data is non-linear and it finds clusters of different shapes. A spectral graph is constructed based on the affinity matrix or similarity matrix and the graph cut is found using Laplacian matrix. Traditional spectral clustering use Gaussian kernel function to construct a spectral graph. In this paper we implement PCA based similarity measure for graph construction and generated different Laplacian graphs for spectral clustering. In PCA based similarity measure, the similarity measure based on eigenvalues and its eigenvectors is used for building the graph and we study the efficiency of two types of Laplacian graph matrices. This graph is then clustered using spectral clustering algorithm. Effect of PCA similarity measure is analyzed on two types of Laplacian graphs i.e., un-normalized Laplacian and normalized Laplacian. The outcome shows accurate result of PCA measure on these two Laplacian graphs. It predicts perfect clustering of non-linear data. This spectral clustering is widely used in image processing.