Feature Selection via Scaling Factor Integrated Multi-Class Support Vector Machines

1 Introduction

With the rapid advance of computer techniques, immense quantities of high dimensional data have been yielded in many applications, such as computer vision, pattern recognition and data mining, which pose unprecedented challenges for learning tasks due to the curse of dimensionality. Those high dimensional, complex and irrelevant features often make learning models tend to over-fitting and become less comprehensible. In order to utilize this kind of data effectively, feature selection is an essential component to successful data mining [Liu and Motoda, 2007]. As a process of selecting a subset of original features or learning the feature weighting according to certain criteria, feature selection is an important and frequently used dimensionality reduction technique which not only reduces the number of features, removes irrelevant, redundant, or noisy data, but also brings the immediate effects for real applications, such as gait recognition

[Kusakunniran et al., 2010], expression recognition [Gupta and Xiao, 2011], image annotation [Huang et al., 2012] and disease diagnosis [Zhu et al., 2014].

During the past few decades, researchers have developed a large amount of feature selection algorithms. Based on the different computational models, feature selection methods can be roughly classified into three categories [Guyon and Elisseeff, 2003; Zhao et al., 2010]: filter, wrapper and embedded models. The filter model utilizes the intrinsic properties or some global statistical information of the data, and evaluates features without any learning mechanism. Some popular feature selection methods based on filter model include Fisher Score (FS) [Duda et al., 1973], ReliefF (RF) [Liu and Motoda, 2007], mRMR (MR) [Peng et al., 2005], T-test (Ttest) [Montgomery et al., 2009], Chi-Square (Chi) [Liu and Setiono, 1995], Information Gain (IG) [Cover and Thomas, 1991] and so on. Most of these methods are evaluated independently for each feature, therefore they cannot deal with redundant features effectively. The wrapper model [Kohavi and John, 1997] uses a given learning algorithm to select features according to its evaluation criteria. In spite of good performance, they often have expensive computational cost. The embedded model [Lal et al., 2006] performs feature selection as a part of the training process, and often shows good performance since it is coupled with specific classifier. These different models are designed from different perspectives and all have their own strengths and weaknesses. In this paper, we propose a novel method based on embedded model for performing supervised feature selection.

Feature selection methods based on embedded model are coupled with specific classifiers, where Support Vector Machines (SVMs) are the most commonly used classifier. One of the standard embedded methods with SVMs is Recursive Feature Elimination (RFE) [Guyon et al., 2002] which is based on the idea that the importance of a feature should be related to the magnitude of its weight and the feature with the smallest magnitude is removed. In order to reduce the time consumption, ℓ1-SVM [Mangasarian, 2006] was proposed, which can obtain a sparse solution by changing the ℓ2-norm regularization in SVM to an ℓ1-norm. However, considering that the number of selected features using ℓ1-SVM is upper bounded by the sample size, a Hybrid Huberized SVM (HHSVM) [Wang et al., 2007] was presented via combining both ℓ1-norm and ℓ2-norm to form a more structured regularization. Unfortunately, the above methods were designed only for binary classification. Actually many classification problems in practice involve many categories, thus some works [Hou et al., 2011; Yang et al., 2011; He et al., 2012; Han and Kim, 2015] were developed to deal with multi-class feature selection problem based on other models (such as iteratively re-weighted Least Squares and Half-quadratic optimization).

Although original SVMs can be extended to the multiclass case via one vs one or one vs all strategy, it ignores the correlation between classes, since the extended strategy just simply breaks the multi-class problem into several independent binary classification problems. To overcome this drawback, multi-class SVMs [Fan et al., 2008; Chapelle and Keerthi, 2008] are invented to consider all classes simultaneously by solving a unified optimization problem. [Obozinski et al., 2006] proposed ℓ2,1-norm based a multitask learning method to take advantage of the structural sparsity to select the discriminative features across multi-class. However, this work used Least Square loss function instead of the hinge loss function, where the latter is usually better than the former in terms of feature selection and classification tasks [Cristianini and Shawe-Taylor, 2000]. Recently, the work [Cai et al., 2011] proposed a new feature selection method that adopted the multi-class hinge loss with a structured regularization term for all classes without requiring further heuristic strategy. Although this work has been tackled based on the existing method, it doesn't consider scaling flexibility of each feature, and thus can not automatically eliminate irrelevant features efficiently.

The large number of features and the small number of data samples form the serious challenge for classification. To address this challenge more efficiently, this paper develops a novel and general model based on multi-class SVM, which integrates a scaling factor θ with p2 power to renewedly adjust the distribution of feature weights and select the most discriminative features. During the process of weight allocation on each feature, the proposed model also shows its property. Concretely, when p is close to infinity, the property of ℓ2, 2 1+p -norm is closest to that of ℓ2,0-norm. However, solving ℓ2, 2 1+p -norm in the proposed model is more feasible than solving ℓ2,0-norm. When p is equal to one, the property of ℓ2, 2 1+p -norm is equivalent to that of ℓ2,1-norm which is structured sparse. In addition, to solve the proposed model, we provide an alternative and iterative optimization method. Specifically, in the process of optimization, through mathematical transformations and Larange multiplier method, our optimization makes solutions of weighting matrix W and scaling factor θ independently, which not only better addresses the difficulty of solving ℓ2,0-norm but also searches optimal p to ensure the proper sparsity of weighting matrix. What's more, the theoretical analysis including convergence is also provided. Comprehensive experiments are conducted on six datasets to demonstrate that this work can obtain better performance compared with a number of existing state-of-the-art multi-class feature selection methods.

2 RelatedWork

In this section, we briefly review some feature selection methods based on multi-class SVM [Chapelle and Keerthi, 2008; Fan et al., 2008; Cai et al., 2011] which are very close to the proposed methods.

2.1 Multi-class SVMby Crammer and Singer

The index i runs over the data samples (i=1,. . . ,n), v runs over the features (v = 1,. . . ,d), and k runs over the classes (k=1,. . . ,c). W=(w1, . . . ,wc) ∈ Rd×c is the projection matrix. X= (x1, . . . , xn) ∈ Rd×n is the data matrix. yi ∈ {1,. . . ,c} is the label for each sample. The efficient approach developed by Crammer's formulation [Crammer and Singer, 2001] can be adopted to solve them, which is equivalent to solving the following optimization problem:

where α is the regularization parameter to balance the loss and penalty, and the bias bk for each class is absorbed by augmenting the vector wT k and each sample xi with an additional dimension: wT k ←[wT k , bk], xTi ←[xTi , 1]. The format of problem (1) can be written as:

Given data matrix X and label matrix Y = {yik} ∈ Rn×c , problem (2) can be generalized as:

2.2 Multi-class SVMwith ℓ2,1-norm Regularization

Recently, considering the superiority of ℓ2,1-norm in terms of [Nie et al., 2010], the work [Cai et al., 2011] combined the multi-class hinge loss with ℓ2,1-norm regularization term for the feature selection:

where ‖W‖2,1 = ∑di=1 ‖wi ‖2, and wi and wj denote the i-th row and the j-th column vector of matrix W, respectively. This work combines multi-class hinge loss with ℓ2,1-norm regularization and is solved by changing ℓ2,1-norm to trace optimization on W.

3 The ProposedMethod

3.1 Formulation

In this paper, we tend to learn c classifications functions fk(x) = wT k x, 1 ≤ k ≤ c and perform simultaneous feature selection, namely find a small set of features which are good for all the classifiers. Considering the flexibility of each feature and making W with optimal sparsity, we propose a novel framework of scaling factors for performing feature selection in the multi-class cases:

where θ is a vector which consists of d scaling factors θv(v= 1. . .d), and p ≥ 1 is the power exponent of θv. In the following part, we will further analyze how to solve this framework.

3.2 Optimization

Theorem 1. Solving problem (5) can be transformed into solving the following problem:

Proof. Let ˜wvk=θ p2 v wvk, then wvk=θ -p 2 v ˜wvk. After variable substitutions, problem (5) is equivalent to:

Making the change of variables wvk← ˜wvk, problem (7) can be rewritten as:

For updating scaling factors θ, we fix other variables and simplify the first term of problem (8) as follows:

where r =-p(r ≤-1) and hv = ∑ck=1w2 vk = ‖wv ‖22 . The Lagrangian function of problem (9) is:

where λ and µv ≥0 are the Lagrangian multipliers.

Taking derivatives of L(θv, λ, µv) with respect to θv and setting it to zero, and then according to the KKT condition µvθv =0, we can calculate the solution of problem (9):

Substituting original variables (p and wv ) back to Eq.(11), there is:

Algorithm 1 : Solving problem (5)

Input: Data X ∈ Rd×n , label Y ∈ Rn×c , parameters C and

p.

Initialization: Set t=0.

Initialize W(0) = {wvk = 1}.

Initialize scaled factor θ, where its v-th element is θv = 1c .

Repeat

• 1: Calculate scaled factor of each feature θt+1 by Eq.(12).
• 2: Update feature weighting matrixWt+1 by solving problem (15) using Crammer's algorithm [Fan et al., 2008].
• 3: t = t +1

Until converges.

Output: W and θ.

Using Eq.(12), the objective function of the first term in problem (8) can be further rewritten as:

Therefore, we can arrive at problem (6) after submitting Eq.(13) into problem (8). This completes the proof and realizes rewriting problem (5) without an explicit θ by using W.

For the proposed method, we utilize an alternative and iterative method to solve W and θ in problem (5). When W is fixed, we can use Eq.(12) to update θ, and then update W when θ has been obtained. When θ is fixed, problem (5) becomes a classical multi-class SVM model and is simplified as:

where ˜xvi=θ p2 v xvi is known. Given ˜X=(˜xvi), problem (14) can be generalized as:

which can be solved by using [Fan et al., 2008; Cai et al., 2011]. For clarity, we summarize our method in Algorithm 1.

In above theoretical derivation, we transfer problem (5) into problem (6) which is a novel framework with flexible sparsity realized by tuning p in range of [1,∞). Concretely, when p→∞, ‖W‖2, 2 1+p is closest to ‖W‖2,0. However, solving ‖W‖2, 2 1+p in the proposed model is much easier than solving ‖W‖2,0. When p=1, ‖W‖2, 2 1+p degrades as ‖W‖2,1 which is structured sparse. At this time, problem (5) becomes:

which can be transformed into:

For problem (16), we also use the alternative and iterative method to solve W and θ. If W is fixed, we can use Eq.(12) with p=1 to update θ, and then solve problem (15) to update W if θ has been calculated.

3.3 Convergence

Theorem 2. The Algorithm 1 monotonically decreases the objective of problem (5) in each iteration and converges to the optimum of the problem.

Proof. Suppose that at the t-th iteration, we have obtained Wt and θt. In the t+1-th iteration, the updatedWis denoted as Wt+1. Considering that problem (5) can be rewritten as problem (6), we have:

Referring to the way of argumentation for [Chang et al., 2014], through rewriting Eq.(18) we have:

Thus, Eq.(19) proves that problem (5) and its variant problem (6) are lower bounded and their objective function value decreases after each iteration.

4 Experiment

4.1 Experiment Setup

In our experiments, six different public datasets are adopted to illustrate the performance of different feature selection methods. These datasets include five microarray datasets (LUNG, CAR, SRBCT, GLIOM and MLLML) 1 and one primary tumor dataset (BrainT2) 2 . These datasets are widely used by many previous feature selection methods such as [Padungweang et al., 2012; Liu et al., 2013; Hong et al., 2016] to evaluate their performance. All datasets are standardized to be zero-mean and normalized by standard deviation, and satisfy that in each dataset the number of samples is much less than the number of the features. We show more information of the datasets in Table 1.

1 http://csse.szu.edu.cn/staff/zhuzx/Datasets.html

2 https://archive.ics.uci.edu/ml/datasets/Primary+Tumor

In order to demonstrate the effectiveness of the proposed method (p > 1, denoted as square ℓ2, 2 1+p -norm (SL2P)) and its simple version (p=1, denoted as square ℓ2,1-norm (SL21)) for feature selection, we compare them with six classical feature selection methods (i.e. IG [Cover and Thomas, 1991], Ttest [Montgomery et al., 2009], FS [Duda et al., 1973], Chi [Liu and Setiono, 1995], RF [Liu and Motoda, 2007] and MR [Peng et al., 2005]) as well as two widely used methods which are multi-class hinge loss with ℓ2-norm regularization (denoted as CS) [Fan et al., 2008] and multi-class hinge loss with ℓ2,1-norm regularization (denoted as L21) [Cai et al., 2011]. Because our work concerns multi-class feature selection, we do not compare binary feature selection method (like ℓ1-SVM).

In addition, for each dataset, we randomly sample 50% instances as training data and the remaining are used as test data. We tune parameters based on the training set and predict classification accuracy based on the test set. We choose the classification accuracy as metric, achieved by Crammer and Singer's SVM [Fan et al., 2008] classifier using the selected features. The numbers of selected features are set as {10,20,30,40,50,60,70,80}, respectively. A good feature selection algorithm should select a few of features that result in high classification accuracy.

4.2 Experiment Results

In our experiments, we utilize the Crammer's method [Fan et al., 2008] for solving multi-class SVM to evaluate the effectiveness of selected features. As shown in Table 2 and 3, in terms of the classification accuracy, it is obvious that proposed methods (SL21 and SL2P) outperform all other feature selection methods on six datasets.

In Tables 2 and 3, for almost all the datasets, the proposed SL2P method can achieve significant improvements compared with six filter feature selection methods. These results demonstrate that incorporating feature selection as a part of the training process and obtaining feature weighting analytically from a learning mechanism are more efficient. In contrast, filter feature selection methods select features without involving any learning mechanism.

Furthermore, compared with two multi-class SVM methods (CS and L21), the proposed SL21 method obtains better results on LUNG, SRBCT, GLIOM and MLLML datasets. For example, in Table 2, the proposed SL21 method averagely achieves 12.6316%, 12.6984%, 4.1667% and 12.7451% improvements, respectively. Similarly, compared with CS and L21 methods, the proposed SL2P method can obtain the best results on LUNG, CAR, BrainT2, SRBCT, GLIOM and MLLML datasets. This is because the ℓ22, 2 1+p -norm is more efficient than other norms (Frobenius-norm and ℓ2,1), by renewedly scaling factors and tuning parameter p to allocate each feature weight with optimal sparsity. For example, in Table 2, the SL2P method averagely achieves 11.5789%, 20.9459%, 14.2858%, 15.8730%, 12.5001% and 16.6667% improvements, respectively.

Besides, the proposed SL2P method can achieve higher classification accuracy than the proposed SL21 method. For example, in Table 3, it can achieve 3.1579%, 1.3513%,

17.8572%, 6.3492%, 8.3333% and 3.9216% improvements, respectively on all datasets. These results illustrate that when flexibly tuning parameter p in (1,∞), the SL2P method can obtain more proper sparsity than the SL21 method. Thus, due to the introduction of parameter p, the SL2P method not only makes the optimal sparsity of the weighting matrix adaptively, but also naturally selects the most discriminative features.

Finally, we tune the number of selected features instead of only picking 20 or 40 features and show their experimental results in Figure 1. It can be seen that two proposed methods SL21 (green dotted line marked as lower triangular) and SL2p (red solid line marked as circle) can achieve higher classification accuracy and converge within 50 iterations. What's more, to validate the convergence analysis of the proposed SL21 and SL2P methods, we present their convergence behavior curves in Figures 2 and 3, respectively.

4.3 Parameters Setup

In our experiments, for six filter-based methods (IG, Ttest, FS, Chi, RF and MR), their parameters can be tuned according to [Zhao et al., 2010]. In the two multi-class SVMs methods (CS and L21), there is only one parameter C which can be adjusted on training data by grid search. Concretely, from 10-1 to 101 with 0.1 step, we search for optimal parameters with the highest accuracy. For the proposed SL21 and SL2P methods, two parameters C and p need to be tuned. The parameter C controls the trade-off between discrimination and sparsity, and the parameter p emphasizes the proper sparsity of the feature weighting. They all play important roles in our methods. For p = 1, there is only one parameter C in Algorithm 1. For p > 1, there are two parameters C and p in Algorithm 1.

We also vary these two parameters from 10-1 to 101 with 0.1 step and search for optimal parameters corresponding to the highest accuracy, where their results satisfy constraints of θ in the end. All classification results are conducted on each selected feature set from six datasets and methods by Crammer and Singer's SVM [Fan et al., 2008].

5 Conclusion

To tackle the challenge of high feature dimensionality and noisy features in multi-class classification, this work proposes a novel and general feature selection framework, the square ℓ2, 2 1+p -norm method, via flexibly scaling factor for each feature, where parameter p is the power exponent of scaling factor. The proposed methods capture a small number of more discriminative features across multiple classes by tuning different values of p, and shows the connection between ℓ2, 2 1+p -normmethod and ℓ2,1-normmethod. Furthermore, the theoretical proof of the convergence has also been provided. Compared with the state-of-the-art methods, the proposed methods can always achieve the best performance.

Acknowledgments

This work was supported in part by the National Science Foundation of China under Grants 61522207 and 61473231.