Worst-Case Discriminative Feature Selection

1 Introduction

Nowadays, the dimensionality of the data involved many realworld applications has increased explosively. The presence of many irrelevant and redundant features [Ben-Bassat, 1982] tends to make a learning model overfitting, resulting in its performance degenerates. Dimensionality reduction is one of the most popular techniques to help address this problem. Feature selection is a widely employed technique for reducing dimensionality among practitioners. It aims to select a small number of significant and useful original features without any transformation. Thus, feature selection could maintain the original representation of variables, which leads to better readability and interpretability. Many efforts have been devoted to the research in feature selection during the past few years [Romero and Sopena, 2008] [Pena and Nilsson, 2010].

∗Contact Author: Q. Gao. (qxgao@xidian.edu.cn)

†Contact Author: F. Nie. (feipingnie@gmail.com)

According to how the learning algorithm is integrated into the process of evaluating and selecting features, feature selection methods can be roughly categorized as wrapper methods [Kohavi and John, 1997] [Wang et al., 2008], embedded methods [Nie et al., 2010] [Cai et al., 2013] and filter methods. The wrapper methods and embedded methods are tightly coupled with the specific classifier, they always have better performance than filter methods on the particular classifier but not on the other classifiers. Different from wrapper and embedded methods, the filter-type methods, which evaluate features based on a certain criterion, are absolutely independent on any classifier. Most existing filter-type feature selection methods conducted the selection process in the manner of feature ranking [Robnik et al., 2003] [Raileanu and Stoffel, 2004] or feature subset evaluation [Nie et al., 2008]. Methods based on the feature ranking compute the relevance of a feature with respect to the class label distribution of data. In this paper, we propose a new filter-type feature selection method in the manner of feature ranking.

For the classification problem, feature selection aims to select subset of highly discriminant features. In other words, it selects features that are capable of discriminating samples that belong to different classes. Fisher discriminant criterion [Fisher, 1936] is probably the most widely used one. One of the most representative algorithms is Fisher score [He et al., 2005], which optimizes the so-called Fisher criterion that maximizes the ratio of between-class scatter over within-class scatter in a individual feature level. On this basis, the Laplacian score [He et al., 2005] also consider the feature ability of preserving the local manifold structure. Then Trace Ratio [Nie et al., 2008] was proposed to improve the computational efficiency of Fisher score, which selects a feature subset based on the corresponding subset-level score that is calculated in a Trace Ratio form. Moreover, there are many feature selection method, combining the popular transformationbased dimensionality reduction method linear discriminant analysis (LDA) and sparsity regularization [Masaeli et al., 2010]. For example, Discriminative Feature Selection (DF- S) [Tao et al., 2016] imposes the row sparsity on the transformation matrix of LDA through ℓ2,1-norm regularization to achieve feature selection. Zhang et al. proposed a selfweighted supervised discriminative feature selection (SSDFS) method [Zhang et al., 2018], which constrains the transformation matrix to be orthogonal and introduces the ℓ2,1norm regularization to select features.

However, according to the definition of between-class scatter, the aforementioned methods actually maximize the average of all pairwise distances between classes [Bian and Tao, 2011] [Su et al., 2018]. This may cause the so-called class separation problem [Loog et al., 2001]. Specifically, these methods tend to pay close attention to classes with larger distances, but ignore those with smaller distances, resulting in the overlap of neighboring classes in the lower-dimensional space. An example to illustrate the class separation problem is shown in Figure 1, where class 1 and class 2 locate closely to each other while class 3 is far away from them, and all classes have the same covariance. We can directly see that the Feature 2 could easily separates three class, while the Feature 1 would result in a complete confusion of class 1 and class 2. But according to the muti-class Fisher certeria [Rao, 1948], the average of pairwise distances between classes is maximized in the Feature 1.

Due to the fact that many feature selection methods based on the discriminative criteria usually consider the overall (or average) separation of data, thus they cannot guarantee the separation (as best as possible) of any class pairs. Thus, we propose a new criterion for discriminative feature selection, namely worst-case discriminative feature selection (WDFS), which adopt a worst-case view [Yu and Yeung, 2010] but the average view. Specifically, WDFS directly maximizes the ratio of the minimum of between-class variance of all class pairs over the maximum of within-class variance, and thus it duly considers the separation of all classes. For the solution, we take a greedy strategy by finding one feature at a time, but that is very easy to implement. Moreover, in order to reduce the redundancy of selected feature subset, we extend WDFS to uncorrelated WDFS (UWDFS) with the help of the correlation between features. Finally, in the experiment, we respectively use the original features and the score vectors of features over all class pairs to calculate the correlation coefficients, and analyze the experimental results in these two ways. Our contribution are summarized as follows:

1. Our method WDFS duly considers the separation of all classes, which adopts a new view called worst-case view different from the conventional average view.
2. Considering the feature evaluation mechanism of the WDFS model, we propose a method to help reduce the redundancy, which only needs to calculate the correlation coefficients between features or feature score vectors.
3. Although we take a greedy strategy by finding one feature at a time, that is very easy to implement with low computational complexity.

2 RelatedWorks

2.1 Fisher Score

Given a set of N data points {xk ∈ Rd×1 |k = 1, · · · ,N } which are sampled from C classes. The within-class matrix Sw and between-class matrix Sb are defined as

where ni denotes the number of samples in the i - th class, µi denotes the mean of the i - th class, and xip denotes the p - th sample in the i - th class.

To specify the selected features in the procedure of feature selection, we equip the conventional transportation matrix with an explainable structure to specify the selected features, namely selective matrix. Next, we will go into details. First, concatenate the dataset {x1, x2, . . . , xN} to a matrix X=[x1, x2, . . . , xN] ∈ Rd×N . Then let fr T ∈ R1×N denotes the r-th row of X, i.e. the r-th feature of the dataset, and then let F = XT = [f1, f2 . . . , fd] ∈ RN×d . Formally, for a feature subset FI ∈ F, we could define the corresponding selective matrix as

where wI(k) ∈ Rd×1 (k = 1, 2, . . . ,m ≤ d) refers to a column vector whose components are all 0 expect 1 for the I (k) - th one. Note that this WI is indeed a column-fullrank transformation matrix. With the selective matrix WI, the process of feature selection could be expressed as

Then the model of Fisher Score could be formulated as

It should be noted that each feature is evaluated individually. It is easy to see that the model in the Eq. (5) consider the overall (or average) separation of data, thus it cannot guarantee the separation (as best as possible) of any class pairs.

2.2 Redundancy

The Redundancy (feature-feature) analysis has been another concerned part of supervised filter models, which has many similarities to the Relevance (feature-class) in term of measurement. Yu and Liu [Yu and Liu, 2004] explored further feature redundancy, and more restrictively defined relevant features as any feature that is neither irrelevant nor redundant to the target concept. The independence or complementarity of one feature can be defined based on correlation coefficient, mutual information, or any criterion characterizing feature redundancy. Many models use Euclidean distance, Pearson correlation [Battiti, 1994], and information measures for redundancy analysis. Some feature selection methods seek to remove redundant features while others do not. A classical criterion for feature selection based on relevance and redundancy analysis is Max-Relevance and Min-Redundancy (mRMR) [Bian and Tao, 2011], which maximizes the correlation between features and categorical variables while minimizing the correlation between features by measuring the mutual information.

3 Approach

In order to guarantee the separation (as best as possible) of any class pairs, we propose a new criterion for discriminative feature selection, worst-case discriminative feature selection (WDFS) in the subsection 3.1. Unlike Fisher Score and other methods based on the discriminative criteria considering the overall (or average) separation of data, WDFS adopts a worst-case view which duly considers the separation of all classes. Specifically, WDFS directly maximizes the ratio of the minimum of between-class variance of all class pairs over the maximum of within-class variance of all classes.

Apart from the analysis of relevance (feature-class), the analysis of redundancy (feature-feature) is another crucial part of supervised filter models. This work simply uses the correlation coefficient to help reduce redundancy among features. Then WDFS is extended to uncorrelated WDFS (UWDFS) in the subsection 3.2.

3.1 Worst-Case Discriminative Feature Selection

In the Eq. (1), due to the fact that µ = 1N c∑ i=1 niµi, thus the equation (1) would be equal to the following equation by simple derivation.

Next, we define the between-class matrix Si,j b for the class pair (i, j) and the within-class matrix Siw as

where µi denotes the mean of the i - th class, and denotes the sample in the class. Similarly, based on the Fisher discriminative criterion, we formulate the model of worst-case

Algorithm 1 WDFS

Input: Train dataset {(xi, yi) |i = 1, 2, . . . ,N }, wherein xi ∈ Rd×1 and yi ∈ {1, 2, · · · , C}, the selected number m. Initialize: Concatenate the dataset {x1, x2, . . . , xN} to a matrix X=[x1, x2, . . . , xN] ∈ Rd×N , and let F = XT = [f1, f2 . . . , fd].

Output: Selective matrix WI ∈ Rd×m.

• 1: Calculate the within-class matrix Siw for all class by the Eq. (7), and between-class matrix Si,j b for all class pair (i, j) , 1 ≤ i < j ≤ C by the Eq. (8).
• 2: For each feature, calculate the score score(fr),r = 1, 2, . . . , d by the Eq. (10).
• 3: Sort the scores of all features.
• 4: Select the m feature indexes corresponding to the first m largest feature scores and construct the corresponding selective matrix WI .

discriminative feature selection as

It should be noted that each feature is evaluated individually. Thus, we could a greedy strategy by finding one feature at a time to solve this optimization problem. Define the score of the r - th feature in F as

where wr is a selective vector corresponding to the r - th feature in F. For clarity, Algorithm 1 lists the pseudo code of solving the model WDFS.

3.2 UncorrelatedWDFS

In this subsection, we extend WDFS to Uncorrelated WDFS (UWDFS) by calculating correlation coefficients between features to help reduce the redundancy. For a feature pair (fi, fj), we define the correlation coefficient as

where σ (·) is a scalar function, which calculate the similarity (correlation) between two vectors. It is worth noting that the larger correlation coefficient means a greater redundancy between features.

Moreover, according to the aforementioned analysis, we have that WDFS evaluates feature individually. Then we calculate the correlation coefficient between each feature of the rest features (current candidate feature subset except for the feature with the largest score) and the feature with the largest score. These correlation coefficients can further be used to calculate the weights, indicating the importance difference among the rest features.

Specifically, suppose the current selected feature subset be Fk = {fI(1), fI(2), · · · , fI(k)} ⊂ F, and its complement, namely the candidate feature set, could be defined as

Algorithm 2 UWDFS

Input: Train dataset {(xi, yi) |i = 1, 2, . . . ,N }, wherein xi ∈ Rd×1 and yi ∈ {1, 2, · · · , C}, the selected number m. Initialize: Concatenate the dataset {x1, x2, . . . , xN} to a matrix X=[x1, x2, . . . , xN] ∈ Rd×N , and let F = XT = [f1, f2 . . . , fd].

Output: Selective matrix WI ∈ Rd×m.

• 1: Calculate the score vector s(0) by the Eq. (10).
• 2: for k = 1 to mdo
• 3: Find the feature fI(k) = fmax and remove it from the current candidate feature subset F c k , then obtain the new candidate feature subset F c k+1 .
• 4: Calculate the correlation coefficient vector
• 5: ρ = [ρ1, ρ2, · · · , ρd-k-1] between F c k+1 and current fmax by the Eq. (11).
• 6: Update the score vector by the Eq. (16), then s(k) = [s(k) 1 , s(k) 2 , · · · , s(k) d-k-1 ]

7: end for

• 8: Construct the selective matrixWI corresponding to the selected feature subset {fI(1), fI(2), · · · , fI(m)}.

Here, we take the process of selecting the first two features as an example. The main steps are summarized as follows.

Step 1 : When k = 0, i.e. F0 = ∅, we calculate the score for ˜ fr (r = 1, · · · , d) by the Eq. (10), then we get a score vector

where sr (r = 1, · · · , d) is a scalar. Then we find the feature fmax with the largest score as

Then we obtain F c 1 = F - {fI(1)} = { ˜ f1, ˜ f2, · · · , ˜ fd-1}. Step 2 : We calculate the correlation coefficient between ˜ fr (r = 1, · · · , d-1) and fmax = fI(1) by the Eq. (11). Then we get the correlation coefficient vector

Then we can use the 1 - ρr (r = 1, · · · , d - 1) as the weight of ˜ fr. This is consistent with the assumption that a less redundant feature should be assigned a larger weight, while a more redundant feature should be assigned a smaller weight. Finally, we update the score of ˜ fr (r = 1, · · · , d-1) as

Then the new score vector is s(1) = [s(1) 1 , s(1) 2 , · · · , s(1) d-1 ] and the new fmax is

So far, we have described a complete operation of selecting a feature in UWDFS. For clarity, Algorithm 2 lists the pseudo code of solving the model UWDFS.

4 Experiments

In this section, we will validate our proposed methods compared with other state-of-the-art methods on five datasets.

4.1 Datasets Descriptions

These datasets include one object image dataset, COIL20, USPS, two face image datasets ORL 1 and UMIST, and one biological gene expression microarray dataset, lung cancer (LUNG). (The COIL20, USPS and LUNG datasets are download from the Internet 2 ). We summarize the statistics of the data sets in Table 2 and briefly introduce them as follows.

1. COIL20 contains 1440 images of 20 objects. The images of each object were taken 5 degrees apart as the object is rotated on a turntable, and each object has 72 images.
2. The original USPS handwritten digit database contains 9298 images. In this paper, we select a balanced random sample of the original data set.
3. ORL consists of 400 face images. There are ten different images of each of 40 distinct subjects. For some subjects, the images were taken at different times with varying lighting, different facial expressions, and facial details.
4. UMIST contains 20 persons and totally 575 images. The number of data in each class is between 10 and 24.
5. LUNG is composed of 203 samples in five classes with 139, 21, 20, 6, and 17 samples, respectively. Each sample has 12600 genes. The genes with standard deviations smaller than 50 expression units were removed and the remaining data set contains 203 samples with 3312 genes.

4.2 Reducing Feature Redundancy

A redundant feature does not add anything new to the target concept [Dash and Liu, 1997]. Thus, removing redundancy is straightforward when we require the number of selected features is as small as possible. Actually, we want the preserved features to be informative and complemental to each other. Considering that our proposed method selects one feature at a time, so we simply uses the correlation criteria to help reduce redundancy among features. The Pearson correlation coefficient [Battiti, 1994] is one of the simplest criteria. Moreover, in the experiment, we also try to use the score vectors over all class pairs instead of original feature as the input for calculating the correlation coefficients. The corresponding calculation formulas are as follows.

1 http://www.zjucadcg.cn/dengcai/Data/FaceData.html

2 http://featureselection.asu.edu/datasets.php

1. Pearson correlation coefficient

where a and b are two vectors.

(2) The score vector over all class pairs

For the feature fr, similar to its score in the Eq. (10), we could define the corresponding score vector vr ∈ R C(C-1) 2 over all class pairs as

4.3 Comparison Algorithms and Parameter Setting

In our experiments, we compare our methods (WDFS and UWDFS) with other five methods, including RALMFS [Cai et al., 2013], mRMR [Peng et al., 2005], RFS [Nie et al., 2010], DFS [Tao et al., 2016], TR[Nie et al., 2008] and FisherScore [He et al., 2005]. (The code of mRMR, TR and FisherScore are downloaded from the ASU feature selection repository 3 and the code of DFS is implemented by ourselves in Python2.7.) Among them, RALMFS and RFS algorithms are embedded methods based on the linear regression model. The other methods belong to filter-type methods and except mRMR are all based on the Fisher discriminant criterion. Moreover, we respectively use the original features and the score vectors of features over all class pairs to calculate the correlation coefficients for UWDFS. For clarity, we call them UWDFS-1 and UWDFS-1 respectively.

We randomly divide each dataset into two parts that are approximately equal, one for training and the other for testing, and we repeat each group experiment for ten times. For the sake of simplicity and justice, we use the 1NN calssifier for classification and Euclidean distance as the metric and let the number of selected features be between 10 and 100 with an interval of 10.(There is no ideal method for choosing the dimension of the feature space.) In particular, the trade-off parameters in DFS and RFS, the trade-off parameters in DFS and RFS are set α from [1e - 6, 1e - 4, 1e - 3, 1e - 2, 0.1, 1, 10, 100, 1e3, 1e4].

4.4 Results Analysis

Figure 2 shows the average classification accuracy vs. the number of selected features on six datasets with five different methods. Tables 1 and 3 list the average classification accuracy and the corresponding standard deviation, using the top 20, 40, 60 and 80 features respectively. As can be seen in the experimental results, we have that

3 http://featureselection.asu.edu/index.php

1. As shown in Figure 2, with the increase in the number of selected features, the trends of average classification accuracy of different methods almost have a steady rise on different datasets. With the specific values in Tables1 and 3, we can see that our methods have a better classification performance with minor exceptions. Particularly, our methods trumps all the other algorithms at the small number of features with a noticeable rise.
2. On the ORL dataset, WDFS has better classification results than the other methods in most feature numbers. Our Uncorrelated WDFS is almost inferior to the WDFS algorithm. This may be an indication that the decorrelation process is working in a bad way, resulting in removing some weakly relevant and redundant features.
3. Comparing the model UWDFS-1 with UWDFS-2, we can see that UWDFS-2 always has better performance than UWDFS-1. Especially on the LUNG dataset, UWDFS-2 shows a steady rise but UWDFS-1 has a completely opposite trend.

5 Conclusions

In this paper, we propose a new criterion for discriminative feature selection, worst-case discriminative feature selection (WDFS). Based on a worst-case view, WDFS duly considers the separation of all classes by maximizing the ratio of the minimum of between-class variance of all class pairs over the maximum of within-class variance. Moreover, we also utilize the correlation between features to help reduce the redundancy and extend WDFS to uncorrelated WDFS (UWDFS). Last but not least, the solution process in our model is simple and effective. Experimental results demonstrate the effectiveness of WDFS and UWDFS.

Acknowledgements

This work is supported by National Natural Science Foundation of China under Grant 61773302, Innovation Fund of Xidian University No.10221150004, China Postdoctoral Science Foundation (Grant 2019M653564) and the Fundamental Research Funds for the Central Universities.