Abstract: Sparse representation originating from signal compressed sensing theory has attracted increasing interest in computer vision research community. In this paper, we present a novel non-parametric feature selection method based on sparse representation in text classification. In order to solve the problem of polysems and synonyms in VSM, we construct semantic structure to represent document with PLSA. Motivated by the fact that kernel trick can capture the nonlinear similarity of features, which may reduce the feature quantization error, we propose Empirical Kernel Sparse Representation (EKSR). We apply EKSR to reconstruct weight vector between samples, then design evaluating mechanism CKernel Sparsity Score (KSS) to select excellent feature subset. As the natural discriminative power of EKSR, KSS can find Agood@ feature which preserves the original structure with less information loss. The results of experiment both on English and Chinese dataset demonstrate the effectiveness of the proposed method.
INTRODUCTION
With the rapid development of Internet applications, there will be a huge number of content-rich news release page and forum posts every day. However, the data in network is usually provided in high-dimensional form, which brings on the so-called “curse of dimensionality”. Feature selection is an effective approach to deal with such problem, because it preserves original structure and selects excellent feature subsets according as evaluate mechanism. Researchers have developed a variety of feature selection methods such as Document Frequency (DF), Information Gain (IG), Mutual Information (MI), Expected Cross Entropy (ECE) (CHI) and Term Strength (TS).
Studies (Wright et al., 2009) have shown that no feature selection method has excellent classification effect in any datasets. Therefore, we focus on designing generalized feature selection method which selects characters of a global and makes the best use of various features of the information to reflect the inner structure of the data reasonably. In this paper, motivated by the recent development of Sparse Representation (SR) (Huang and Aviyente, 2007) which succeed in statistics and pattern recognition (Mairal et al., 2008a, b). We propose a simple feature selection method called kernel sparsity score based on semantic (Se-KSS). Specifically, semantic structure of documents is firstly constructed based on probabilistic latent semantic analysis (PLSA) (Hofmann, 1999). Secondly, an “Aadjacent” weight matrix of data set is constructed based on modified sparse representation framework Cempirical kernel Sparse Representation (EKSR), and then the low-dimensional embedding of the data is evaluated to best preserve such weight matrix. At last, evaluating mechanism kernel sparsity score (KSS) is designed to select excellent feature subset. Although supervised information is not needed, KSS tends to find the “good” feature which preserves the original structure.
DOCUMENT REPRESENTATION
Probabilistic Latent Semantic Analysis (PLSA) simulates the occurrence process of word in document by the probabilistic model, and shows the relationship with “document-semantic-word”. Suppose we have given a collection of text documents D = {dI,....., dM} with terms from a vocabulary W = (ωI,....., ωM), z ε Ζ = {zI,....., zk} is an unobserved class variable. Then a joint probability model over D x W is defined by the mixture:
| (1) |
According as the principle of maximum likelihood estimation, the objective function of PLSA is described as Log-Likelihood function as follows:
| (2) |
The standard procedure for maximum likelihood estimation in latent variable models is the Expectation Maximization (EM) algorithm (Hofmann, 2001).Then, K-dimensional vector is considered as term probability representation of document (Sivic et al., 2005).
KERNEL SPARSE FEATURE SELECTION
Motivated by kernel trick, nonlinear data is mapped into kernel space in which the nonlinear similarity of the features can be captured and reconstruct by sparse representation.
Empirical kernel sparse representation: Sparse representation is initially proposed as an extension to traditional signal representation (Mallat and Zhifeng, 1993). Suppose we have given a signal χ ε Rm and a matrix X = [x1, x2,...., x3] ε Rmxn containing the elements of an over-complete dictionary (Murray and Kreutz-Delgado, 2007.) in its columns, the goal of SR is to represent x using as few entries of X as possible. In many practical problems, the signal x is generally noisy, thus an error tolerance ε was used to handle this problem. This can be formally expressed as follows:
| (3) |
In general, the minimization problem can be solved by standard
In order to solve nonlinear problem, we map the input data into feature spaces by kernel trick. Traditionally, the mapping is implicitly represented by specifying a kernel function as the inner product between each pair of samples in the feature space (Shawe-Taylor and Cristianini, 2004). Recently, Kernel Sparse Representation (KSR) method (Gao et al., 2010) has shown the necessity in face recognition, but it is difficult in optimization of sparse matrix. Conversely, the mapping in this paper, is given in an explicit form as describe in Xiong et al. (2005). If the rank of the kernel matrix K is r, it can be decomposed as:
| (4) |
where, is a diagonal matrix consisting of the r positive eigenvalues of K and Q consists of the corresponding orthonormal eigenvectors. Thus, the explicit mapping also called the Empirical Kernel Mapping (EKM) in Xiong et al. (2005), is given as Φe χ→Fr:
| (5) |
Let B = KQA-1/2and then the dot product matrix {Φe (χi)}Ni = 1 of generated by EKM can be calculated as:
| (6) |
That is exactly equal to the kernel matrix in the Implicit Kernel Mapping (IKM) and, the mapped samples generated by EKM and IKM, respectively, have the same geometrical structure. In Xiong et al. (2005), it is shown that comparing EKM with IKM, the former is easier to access and easier to study the adaptability of a kernel to the input space than the latter. This is why we select EKM here.
In this study, the samples explicitly mapped into, where is called new view of the original input space, corresponding to kernel. Then we substitute the mapped features and basis to the formulation of sparse representation, and arrive at empirical kernel sparse representation (EKSR), the optimization problem is expressed as follows:
| (7) |
Equation 7 is convex and the li minimization problem also can be solved by standard li-magic software. Then we can calculate the weight matrix S = [S1, S2,…, Sm]T based on Eq. 7.
Kernel sparsity score: Although the sparse reconstructive weight matrix has no labels of data, it can reflect intrinsic geometric properties of the data and contain natural discriminating information (Qiao et al., 2010).
Let X = [x1, x2,…xm]εRnxm be the data matrix including all the training samples in its columns, xij represents the jth character of the ith sample. We expect to reconstruct each sample xi by EKSR, using as few samples as possible. A sparse reconstructive weight vector Si = [Si1,…Si(I-1), 0, Si(I+1),…Sim]T for each xi can be calculated through Eq. 7, where the elements Sij (j ≠I) denote the contribution of each xj to reconstruct the sample xi. That is:
| (8) |
Algorithm: Kernel sparsity score based on semantic
| Fig. 1: | Se-KSS algorithm |
After computing the weight vector Si for each xi, I =
1, 2, Y, m. We can define the sparse reconstructive weight matrix
| (9) |
Extended to the entire data, we construct evaluate mechanism (Dan, 2010) by the reconstruction error as follows:
| (10) |
The ability of preserving sparse structure is the stronger as the value of KS_Score is the smaller. We select excellent feature subsets by the value of KS_Score, called Kernel Sparsity Score (KSS) algorithm. Based on the above discussion, we summarize the proposed algorithm as shown in Fig. 1.
EXPERIMENT AND RESULT
As described above, DF, IG, Chi and TDE (Song et al., 2010.) have been successfully applied to text classification. In what follows, we test the performance of our proposed algorithm compared with four popular algorithms on two datasets.
The datasets: Retuers is a subset of Retuers 21578 which has 6 different classes and contains 6223 documents for training and 2428 documents for test. Sogou is provided for classifying Chinese by Sogou Lab. We select a subset which contains 5000 documents of 5 classes, where there are 1000 samples per subject. At the moment of pretreatment, we use ICTCLAS provided by CAS for participle.
Experimental results:
| • | Based on K-NN classifier. To verify the effect of different topics, we evaluate the performance of the proposed method with several topics in the series of experiments using the K-NN classifier, where we set neighborhood size k = 30. In experiments, the frame of multi-class classification is one against rest. We show the performance of the number of PLSA = s topics in Fig. 2 |
| • | To verify the effectiveness of the proposed method, we evaluate the mentioned methods based on two classifiers including KNN and SVM, where the number of topics with Se-KSS selects the optimization from Fig. 2. The experimental results are presented in Table 1. For SVM, we simply use the linear kernel |
| Fig. 2(a-b): | The performance of k-NN classifier on the different number of PLSA = s topics |
| Table 1: | The average F1-Measure of different classifiers based on different feature selection |
From above, we can draw the t as follows: (1) Se-KSS has excellent performance in classification on both datasets. This shows that by reconstructing the sparse weight matrix of data, the F1-Measure can be improved. From Fig. 2, we know that the performance of Se-KSS is under the influence of the number of topics. According to different datasets, we should select appropriate topics. (2) DF is simple to perform, but it generally performs as well as IG and CHI. In order to improve efficiency, we can use it instead of IG and CHI. Because TDE uses information entropy to describe the distribution, its performance exceeds DF, IG and CHI. (3) . The classifiers also affect the F1-Measure performance significantly. However, the proposed Se-KSS can generally achieve better performance than other methods based on KNN or SVM.
CONCLUSION
We introduced a non-parametric feature selection method based on Empirical Kernel Sparse Representation (EKSR) for text classification, which gets the sparse weight matrix in a high dimensional feature space mapped by empirical kernel function. Then the excellent features are acquired automatically and capture spatial information among documents. The result of experiment has shown the performance of the proposed algorithm outperforms the compared methods on the two datasets used here without label information.
However, for PLSA model, there is no way to assign probability to an unseen document and it is prone to overfitting. We can consider using Latent Dirichlet Allocation (LDA) (Blei et al., 2003.), which is a well-defined generative probabilistic model and generalizes easily to new documents. Secondly, the use of label information should be considered, one way is to reconstruct weight matrix using Tree Group Lasso (Liu and Ye, 2010). In the future work, we will try to overcome this limitation to further improve its performance.
ACKNOWLEDGMENTS
This study was partly supported by National Natural Science Foundation of China 60603029.