Research On Graph Based Semi-Supervised Classification

In many practical tasks of machine learning,the acquisition of sufficient labeled data is quite expensive and time consuming,while large volume of unlabeled data is easy to obtain.Applying supervised classifiers on scarce labeled samples often results in poor generalization capability and overfitting.On the other hand,the valuable information embedded in the labeled samples is wasted when applying unsupervised learning techniques.Semi-supervised learning can leverage both the labeled data and unlabeled data to achieve a learner with good generalization ability,and has been widely studied and applied.Because of good performance of graph-based semi-supervised classification algorithm,the objective function is convex,getting the solution is easier and other advantages gained more attention.Graph construction is an important preceding work in graph-based semi-supervised classification,and graph is one of the key factors that determine the performance of graph-based semi-supervised classification.However,it is quite difficult to construct a graph that correctly reflects the distribution of samples.Sparse representation has been applied to graph construction for graph-based semi-supervised learning,which is shown to be robust to noisy samples and features.However,it takes all the available samples as the basic samples or as the dictionary and often asks for huge computational resources.In addition,One basic assumption in graph-based semi-supervised classification is manifold assumption,which assumes nearby samples should have similar outputs(or labels).However,manifold assumption may not always hold for two samples lying nearby but across the boundary of different classes.As a result,methods solely based on the manifold assumption may misclassify the boundary samples of different classes.To address these problems associated with graph-based semi-supervised classification,proposing three graph-based semi-supervised classification algorithms based on the existing research.The specific works of this paper are as follows:(1)We propose a method coined as Semi-Supervised Classification based on Local Sparse Representation(SSC-LSR in short).SSC-LSR first utilizes k nearest neighbors of a sample to compute the reconstruction weights,instead of all the available samples as the dictionary.Then,these weights are adopted to construct a local sparse representation graph.Finally,SSC-LSR trains a widely used Gaussian Random Filed and Harmonic Functions classifier on the local sparse representation graph to classify unlabeled samples.Experimental results on two public available facial datasets demonstrate that the proposed method has higher classification accuracy than traditional methods.(2)We propose a method coined as semi-supervised classification based on local subspace sparse representation(abbreviated as “SSC-LSSR”).SSC-LSSR first generates several random subspaces from original space and then utilizes k nearest neighbors of a sample to solve the sparse reconstruction coefficients in each subspace.Next,it constructs a local sparse representation graph using the coefficients in each subspace.Finally,it trains a graph-based semi-supervised classifier on each graph and fuses these classifiers into an ensemble classifier by majority voting to classify unlabeled and new samples.Experimental results on two public available facial datasets demonstrate that the proposed method not only achieves higher accuracy than other related methods,but also costs much less time.(3)We introduce an approach called Semi-Supervised Classification by Discriminative Regularization(SSCDR for short).SSCDR first constructs a k nearest neighborhood graph to capture the local manifold structure of samples,and a discriminative graph to encode the discriminative information derived from constrained clustering.Next,it incorporates these two graphs into a discriminative regularization framework to classify unlabeled and new samples.Experimental results on UCI and facial datasets demonstrate that SSCDR achieves better performance than other related methods,and it is also robust to the input values of parameter k.