Semi-supervised Spectral Clustering Based On Signed Networks

Clustering is the process of grouping a set of objects in such a way that objects in the same group are more similar to each other than to those in other groups.It is a technique in multivariate statistical analysis.Normalized cut(Ncut)as a graph partitioning criterion,is a typical clustering methods.It usually use unsigned network to express data,measure the similarity of nodes based on non-negative weight,and obtain the clustering results through analyzing eigenvalues and eigenvectors of the Laplace matrix of graphs.This kind of method has been applied in many fields because of its partitioning balance and ability of dealing with complex data space.In machine learning,clustering is generally classified as unsupervised learning.This unsupervised property of clustering often makes it ill-posed.Semi-supervised clustering improves the clustering performance by using both partial supervised information and unsupervised samples,which can help users obtain more appropriate clustering results.Unsigned networks have limited expressive ability,since it can not represent similarity and dissimilarity simultaneously.But in actual fact there are negative,antagonistic,and mutually exclusive relationships in real complex systems.By means of signed networks,positive and negative relationships are expressed in positive and negative sides,respectively.Recently,negative edges have shown additional value in various network analyses.Therefore,we extract strong relations from partial supervision information as positive and negative edges respectively,and discuss the problem of semisupervised clustering based on signed networks,and apply it to image segmentation.Signed Normalized cut(SNcut in short)is a kind of graph partitioning principle defined in the signed networks,which integrates information of positive and negative edges.This paper proposes to use the SNcut for semisupervised clustering,performs image segmentation experiments on the MSRA1 K image database,and analyzes the commonly used image clustering statistical indicators and clustering results of some images.The clustering performance of various SNcuts is evaluated qualitatively and quantitatively,and the additional value of negative edges is verified.Furthermore,an improved scheme based on MRF regularization is proposed.The main work of this paper is shown as follows:1.Summarized and discussed the existing spectral clustering methods based on signed networks.2.Used the Signed Normalization cuts for semi-supervised clustering,and conducted empirical research through interactive image segmentation.The semi-supervised information is transformed into pairwise constraints and the negative edges are used to express the cannot-link constraint.Some SNcut algorithms are compared on the database.3.Verified the additional value of the negative edges in image segmentation.By comparing results from original Ncut,Ncut with positive edges,Ncut with negative edges and Ncut with both positive edges and negative edges,it is found that adding negative edges have a greater impact on Ncut clustering results.4.Proposed a clustering model combining SNcut and MRF regularization.By integrating the MRF potential function into the target function,the spectral method and the kernel cut method are respectively used to solve the problem.The experimental results verified the improved performance of the two methods and made a comparative analysis of the two methods.