Study Of Path-based Similarity Measurement For Spectral Clustering

As an important means of data analysis, clustering is one of the major research inthe field of machine learning and pattern recognition. The purpose of clustering is todivide a dataset into natural groups so that data points in the same group are similarwhile data points in different groups are dissimilar to each other. It has beentraditionally viewed as an unsupervised method for data analysis without use of priorknowledge or assumptions.Spectral clustering algorithm is a high performance computing method, whichreceived widespread attention in recent years. Compared with traditional clusteringmethods, spectral clustering algorithms are effective to solve the clustering of arbitrarysphere of sample spaces, and they can converge to global optimal solution. They areideally suited for solving many practical applications, such as computer vision, imagesegmentation and so on. So far, research on spectral clustering is still in its infancy.There are still many problems needed to be solved in spectral clustering algorithms. Forinstance, it is greatly affected by its scale parameter used in Gaussian kernel, and issensitive to noise and outliers in the data, and can’t use priori information to guide theclustering process. To solve these problems, this paper proposed a Robust Path-Basedsimilarity measurement for Spectral Clustering(RPB-SC). We also proposed anextension of our RPB-SC for semi-supervised clustering. This extension of RPB-SC iscalled Robust Path-Based similarity measurement for Semi-supervised SpectralClustering(RPB-SSC). The specific contents are as follows:①Constructing similarity matrix. In this paper, we will introduce path-basedclustering into spectral clustering algorithm to design a new similarity measure function.This function can avoid setting a global scale parameter, reducing the influence on theclustering results, so that the similarity matrix is more coincident with clusteringassumptions.②Research on robust of spectral clustering. Considering that spectral clusteringalgorithms are sensitive to noise in the data, our proposed algorithm computes thesimilarity between samples by defining a weighted local scale in Gaussian kernel. Withthis method, the noise is suppressed effectively.③Research on semi-supervised spectral clustering algorithms. In this paper, weattempt to introduce pairwise constraints priori information into our spectral clustering algorithm. So that, pairwise constraints prior knowledge can be used to improve theperformance of our algorithm. We also make the limit priori information at the samplelevel spread spatially to direct the clustering process.○4Research on the application of spectral clustering technology into the imagesegmentation. In the application of color image segmentation, large amount of dataoften need to be processed and the image may contain a lot of noise, which brings a lotof difficulties in image segmentation. We introduce a color image segmentationframework based on our improved algorithm. Under this framework, segmentation ofthe image containing noise can be accomplished. At the same time, priori informationwould help to guide segmentation.In order to verify the effectiveness of the algorithm, the paper conductedexperiments on several artificial data sets, real data sets and image from Berkeleydatabase, compared with some typical algorithms. The experiment results show that ourproposed method will not be affected by the scale parameter and is significantly morerobust, achieving good performance on clustering and image segmentation.