{'fraction_non_alphanumeric': 0.028297702474940123, 'fraction_numerical': 0.004612791626009048, 'mean_word_length': 5.180921052631579, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semi-supervised Data Representation via Affinity Graph Learning

We consider the general problem of utilizing both labeled and unlabeled data to improve data representation performance. A new semi-supervised learning framework is proposed by combing manifold regularization and data representation methods such as Non negative matrix factorization and sparse coding. We adopt unsupervised data representation methods as the learning machines because they do not depend on the labeled data, which can improve machine's generation ability as much as possible. The proposed framework forms the Laplacian regularizer through learning the affinity graph. We incorporate the new Laplacian regularizer into the unsupervised data representation to smooth the low dimensional representation of data and make use of label information. Experimental results on several real benchmark datasets indicate that our semi-supervised learning framework achieves encouraging results compared with state-of-art methods.


I. INTRODUCTION
The task of semi-supervised learning (SSL) algorithms is to utilize both labeled and unlabeled data to improve learning ability. A variety of graph-based semi-supervised learning (GSSL) [1,5,8,9,10,13] have recently become popular due to their high accuracy and computational efficiency. Most SSL algorithms use label information to improve the learning performance. However, they may also face many problems such as over-fitting. In order to improve learning machine's generation ability as much as possible, we aim to propose a semi-supervised framework that learns the predictions that do not directly depend on the label samples.
We adopt unsupervised data representation methods, such as nonnegative matrix factorization (NMF) and sparse coding (SC) as the learning machines. Without considering the difference between labeled samples and unlabeled samples, these data representation methods always have a good generation ability. Inspired by graph based method [3,4,6], which usually use an affinity graph to smooth the representation of data. We make use of label information by learning an affinity graph, which contains label information, i.e., prior information is embedded in the manifold regularization to control the smoothness of the data representation. When such an affinity graph is obtained, the corresponding graph Laplacian regularizer is incorporated into the unsupervised data representation methods. Different from GSSL framework and manifold regularization framework [3], which always use unsupervised Gussian kernel to construct similarity graph, we utilize metric learning method [7,11,12] to produce a kernel matrix (also known as a "Gram matrix") to measure the similarity between all pairs of samples, subsequently, the similarity matrix is sparsified and reweighted to produce the final affinity graph.
Notice that in GSSL, the sparsification of affinity matrix is important since it leads to improved efficiency in the label inference stage, better accuracy and robustness to noise. In fact, spurious connections between dissimilar nodes (which tend to be in different classes) are removed and each node connects to only a few nodes. Metric learning method, which learn the similarity and dissimilarity of pairs of the labeled samples, is a good way to lead the sparsification stage more accurate (delete more "right" spurious connections). In this way, the affinity graph is more suitable with considering the label information.
In this paper, we propose a novel semi-supervised framework. Experimental results on several real benchmark datasets indicate that our semi-supervised learning framework achieves encouraging results. We compared our proposed methods with state-of-art methods, include some excellent GSSL and unsupervised methods.
The rest of the paper is organized as follows: Section 2 gives a brief review of several basic algorithms. In Section 3, we introduce our proposed framework. Experimental results are presented in Section 4. Finally, we conclude in Section 5.

A. Graph-based Semi-supervised Learning (GSSL)
GSSL techniques start with computing a similarity score between all pairs of nodes using a similarity function or kernel. Then, an algorithm is selected for finding a sparse weighted subgraph from the fully connected similarity graph.
There are two typical ways to build a sparse graph: neighborhood approaches including the k-nearest and neighbors algorithms, and matching approaches such as b-matching [10].
Once a graph has been sparsified, several procedures can then be used to update the graph weights such as Binary weighting and Gaussian kernel weighting. At last, given the final affinity graph and some initial label information, GSSL algorithms diffuse the labels on the known part of the graph to the unknown nodes. The current best GSSL techniques include the greedy max-cut method [1], Laplacian support vector machine [8], the local and global consistency method [5] and the alternating graph transduction method [13].

B. Metric learning
Metric learning expects that the learned metric makes distances between similar samples small and distances between dissimilar samples large. In general, a Mahalanobis distance metric measures the squared distance between two data points and : where is a positive semi-definite matrix and is a pair of samples .

A. Framwork
We adopt unsupervised data representation methods as the learning machines. Traditional semi-supervised manner for unsupervised data representation usually use the Label Weight as the affinity [15]. Label Weight is constructed as follows: In this way, the unlabeled data is totally ignored. In the proposed framework, prior information is embedded in the manifold regularization to control the smoothness of the data representation.
Given independent and identically distributed samples of feature dimensions and instances, and the first samples have labels. The learned weight matrix forms the following Laplacian regularizer which is used to measure the smoothness of the low dimensional representation: where is the data representation of data , . denotes the trace of a matrix and is a diagonal matrix whose entries are column sums of .
Then the loss function in the proposed framework is defined as follows: (4) where is the loss function of one unsupervised method, ( ) is the Laplacian regularizer, is the regularization parameter to measure the smoothness of the low dimensional representation.

B. Affinity graph learning
We utilize KISS metric learning method [7] to produce a kernel matrix to measure the similarity between all pairs of samples. Then, the similarity scores between all pairs of nodes creates a full adjacency matrix , where ( ) .
Subsequently, -nearest neighbors algorithm or -matching algorithm can be applied to build a sparse graph ( ). When the graph is sparsified, Gaussian kernel weighting is used to update the graph weights produce a final affinity graph. Therein, the edge weight between two connected samples and is computed as: where is the kernel bandwidth parameter and we always set ∑ ∑ √ .

C. Algorithms under the proposed framework
We adopt two powerful unsupervised data representation methods: Graph Regularized Nonnegative Matrix Factorization (GNMF) [4] and Graph Regularized Sparse Coding (GSC) [6] to display our framework. GNMF is extended to a semi-supervised method by using the proposed affinity graph. Given a nonnegative data matrix , let be the basis matrix, and be the coefficient matrix. The loss function in GNMF is defined as follows: where the regularization parameter .
The Euclidian distance based GNMF algorithms is: 2) Semi-supervised Graph Regularized Sparse Coding Graph regularized Sparse Coding (GSC) learns the sparse representations that explicitly take into account the local manifold structure of the data. By incorporating the new Laplacian regularizer into the original sparse coding, GSC is extended to its semi-supervised manner. Given a data matrix , let be the dictionary matrix, and be the coefficient matrix. The loss function in GSC is defined as follows: where , are the regularization parameter.
Following the iteratively optimization method in [6], the GSC algorithm can learn the graph regularized sparse codes and the learning dictionary iteratively.

IV. EXPERIMENTS
Previous studies show that GNMF, GSC and GMC are very powerful for clustering, especially in the document clustering and image clustering tasks [1], [4], [6]. We investigate the clustering performance of the proposed semi-supervised framework on three real world image data sets, i.e., the Yale database 1 ,the ORL database 2 , and the We compare the following algorithms for data clustering:  The K-means clustering algorithm (K-means).
 Greedy Max-Cut (GMC) [1].  The clustering result is evaluated by comparing the obtained label of each sample with that provided by the data set.
GSSL methods such as LGC and GMC directly propagate label from labeled data to unlabeled data. For other methods, we use Accuracy Metric (AC) [14] to evaluate the clustering performance. The AC value is obtained by mapping the cluster to the corresponding predicted label, so it can be compared with the predicted accuracy in GSSL. All algorithms expect GSSL methods obtain a new data representations of . We set the dimensionality of the new space to be the same as the number of clusters. We follow the parameter settings for all algorithms to achieve their best performance, see details in [1,4,6]. For each data set, the evaluations are conducted with different numbers of clusters.
For all algorithms, we randomly choose categories from the normalized data set ( ), and mix the images of these categories as the collection for clustering. For the fixed number of clusters , we randomly pick up two images from each subject as label information. Clustering performance on 10 algorithms are shown in Table 1 labeled samples of each subject increase from two to more, clustering performance on 7 semi-supervised algorithms are shown in Table 2. These experiments reveal a number of interesting points:  The unsupervised methods under our framework outperform themselves and their original semi-supervised manner (using the Label Weigh).
 The unsupervised methods under our framework perform better than the best GSSL methods (LGC, GMC) especially when number of clusters becomes larger.
 When labeled samples of each subject increase, the unsupervised methods under our framework outperform the other semi-supervised algorithms. It seems that some algorithms like LGC and LGNMF are not sensitive to label information.
 Regardless of the data sets, the Graph Sparse Coding method under our framework always performs good. This suggests that the sparsity is important for data representation.

V. CONCLUSIONS
We present a novel semi-supervised framework that explicitly considers the generation ability of learning machines and the prior information. By learning the affinity graph, the graph Laplacian regularizer is incorporated into the unsupervised data representation method. The experimental results on clustering have demonstrated that our proposed framework can have better discriminating power and significantly enhance the data representation performance.