Distriubuted Semi-supervised Classification Algorithm Base On Graph Signal Processing

Semi-Supervised Learning is an important technology in the field of computer science,which has been called attention widely.By combing supervised learning and unsupervised learning,SSL can process learning task with less human intervention.After years of research and exploration,SSL has achieved considerable results in theoretical research and practical application promotion.Classification is an important issue in SSL.At present,most SSL algorithm for classification are implemented in centralized manner,that is,all data is collected in a central progress unit which performs calculation.Such manner not only has hidden dangers in terms of privacy,but also creates a larger computational burden when the data scale is large.Graph signal process(GSP)processes the data that resides on graph with graph structure,its related research promotes the development of distributed computation.Base on this,we focus on the classification problem in SSL based on GSP.Firstly,in graph semi-supervised learning(GSSL),the centralized manner has high computational complexity.To solve this problem,a distributed semi-supervised classification algorithm based on the decomposition of graph is proposed.In this algorithm,the GSSL problem is formulated as an unconstrained least squares problem.Based on the decomposition of affinity graph,the optimization problem is decomposed into a series of sub-problems which only require local information to solve.Then original problem is solved approximately by combining the solution of sub-problems.In order to reduce the error between the approximate and the optimal solution,an iterative calculation method is used.Proposed algorithm is distributed by the sparsity of affinity graph.Simulation shows that the algorithm converges to optimal solution with fast rate,compared with other algorithms,it can efficiently assign the label to unlabeled nodes.Then,classification based on graph decomposition needs to exchanges information with multi-order neighbors.In the view of this,a semi-supervised classification algorithm based on the quasi-Newton method is proposed,and applied to hyper-spectral image(HSI)classification problem.The algorithm formulates the classification problem as an unconstrained optimization problem.In order to avoid the inversion of the matrix,a quasi-Newton method based on matrix decomposition is used to solve problem.By decomposing the graph Laplacian matrix,the Hessian matrix can be divided into two parts,diagonal and non-diagonal.Then,calculation of Newton step only includes the inversion of diagonal part of Hessian matrix and the multiplication of sparse matrix.Due to the sparsity of affinity graph,proposed algorithm can be implemented in distributed manner.Experiments show that,proposed algorithm has fast convergence rate and can classify HSI data efficiently.