Online Group Feature Selection

1 Introduction

High dimensional data present a lot of challenges for data mining and pattern recognition. Fortunately, feature selection is an effective approach to reduce dimensionality by eliminating the irrelevant and redundant features [Guyon and Elisseeff, 2003]. Feature selection efforts can be categorized into two branches: standard feature selection and online feature selection. The former is only performed after all of the features are calculated and obtained, while in some real-world applications such as image analysis and email spam filtering [Liu and Wang, 2012], features arrive dynamically. It is very time-consuming (if not unrealistic) to wait for all of the incoming features. So it is necessary to perform feature selection incrementally in these applications, which is referred to as online feature selection.

∗Corresponding author.

Online feature selection assumes that features flow into the model one by one dynamically and the selection is performed at the time they arrive. It is different from the standard online learning problem which assumes instances arrive dynamically [Hoi et al., 2012]. Several online feature selection methods have been proposed recently, such as Grafting [Perkins and Theiler, 2003], Alpha-investing [Zhou et al., 2005], and OSFS [Wu et al., 2013]. The Grafting approach selects features by minimizing the predefined binomial negative log-likelihood loss function. The Alpha-investing approach evaluates the new feature based on a streamwise regression model. The OSFS approach obtains the optimal subset by the relevance and redundancy analysis. These approaches can evaluate features dynamically with the arrival of each new feature, but they present a common limit: existing online feature selection approaches evaluate the features individually, thus, they overlook the relationship between features which is very important in some real-world data sets. For example, in image analysis, each image could be represented by multiple kinds of descriptors (groups), such as SIFT for shape information and Color Moment for color information, each of which has a high dimension of features. To solve this problem, some researchers have studied the group structure information, such as group Lasso [Wang and Leng, 2008]. However, theses methods limit their applications in online features selection since they require a global feature space in advance.

To overcome the weakness of online feature selection approaches and the limitations of group selection approaches mentioned above, we propose a new online approach for group feature selection in a dynamic feature stream, called Online Group Feature Selection (OGFS). As a group of features arrives, we first introduce our criteria based on spectral analysis to select features with discriminative ability, referred to as online intra-group selection. Second, we refine the sparse linear regression model of Lasso to find the global optimal subset after seeing all features in the group, referred to as online inter-group selection.

With the above motivation, we formulate the problem of online group feature selection with a feature stream and propose a solution to this problem in this paper. Our major contributions can be summarized as follows:

• Different from the traditional online feature selection, we address the problem of online group feature selection

instead of online individual feature selection. To the best of our knowledge, this is the first effort that considers the online group feature selection problem.

• To evaluate the features dynamically, we introduce spectral analysis into the online feature selection and provide two novel effective criteria.
• Our proposed Online Group Feature Selection (OGFS) method achieves the best classification accuracy compared with other state-of-the-art methods for online feature selection.

The rest of the paper is organized as follows. Section 2 presents a review of related work. Section 3 introduces our framework for online group feature selection. Section 4 reports some experimental results to demonstrate the effectiveness of the proposed method. We conclude this work in Section 5.

2 RelatedWork

There are two categories of feature selection approaches: standard feature selection and online methods. Standard feature selection is performed after all the features are computed. It consists of three categories: filter [Farahat et al., 2012], wrapper [Das, 2001] and embedded methods [Tibshirani, 1996]. Filter methods usually explore the intrinsic statistical properties of features. Wrapper methods use forward or backward strategies to search the whole candidate subsets and a classifier is directly applied. Embedded methods attempt to find an optimal subset based on a regression model with specific penalties on coefficients of features. In general, standard feature selection methods process the features individually. Considering some specific applications where the feature space comes with prior knowledge of group structures, some standard methods have been developed accordingly, such as group Lasso.

All of the standard methods mentioned above require the global feature space in advance to perform the selection. However, in some real-world applications, it is difficult to get the global feature space. To overcome this problem of standard feature selection, online feature selection has attracted a lot of attention in recent years. It assumes that features flow in one by one and it aims to discard or select the newly generated feature dynamically. Representative online feature selection approaches include Grafting, Alpha-investing and OSFS. Grafting performs the selection based on a gradient descent technique which has been proven to be effective in pixel classification. It still requires a global feature space to define the key parameters in the selection of new features. Hence, it cannot handle the case that the feature stream is infinite or with an unknown size. Alpha-investing evaluates the new feature with a p-value returned by a regression model. If the p-value of the new feature reaches a certain threshold α, the feature will be selected. In Alpha-investing, once the features are selected, they will never be discarded. OSFS selects features based on an online relevance and redundancy analysis. According to the relevance to the class label, input features could be characterized as strongly relevant, weakly relevant or irrelevant. Relevant features will be obtained by online relevance analysis, and redundant features will be removed by Markov blankets. In OSFS, each time when a new feature is included, the redundancy of all selected features will be reanalyzed. To speed up the redundancy analysis, a faster version of OSFS, called Fast-OSFS, was proposed [Wu et al., 2013]. Fast-OSFS first analyzes the redundancy of a new relevant feature, then decides whether the redundancy analysis of the selected feature subset will be performed or not. It is still inefficient with the increase of selected features. In addition, all of these online feature selection methods evaluate features individually, thus, they overlook the prior knowledge of group information of features.

In contrast to the above existing efforts, we address the online group feature selection problem in this paper. To make use of the prior knowledge of group information, we propose an efficient online feature selection framework including the intra-group feature selection and inter-group feature selection, and based on this framework, we develop a novel algorithm called OGFS.

3 A Framework for Online Group Feature Selection

We first formalize our problem for online group feature selection. Assume a data matrix X = [x1, · · · , xn] ∈ Rd×n , where d is the number of features arrived so far and n is the number of data points, and a class label vector Y = [y1, · · · , yn]T ∈ Rn , yi ∈ {1, · · · , c}, where c is the number of classes. The feature space is a dynamic stream vector F consisting of groups of features, F = [G1, · · · ,Gj, · · · ]T ∈ R∑ dj , where dj is the number of features in group Gj. Gj = [fj1, fj2, · · · , fjm]T ∈ Rm where fjk is an individual feature. In terms of feature stream F and class label vector Y , we aim to select an optimal feature subset U = [g1, · · · , gj, · · · , gu]T ∈ R∑ uj when the algorithm terminates, where uj is the number of groups arrived so far, where gj ∈ Rmg , gj ⊆ Gj , mg < m, and gj can be empty.

To solve this problem, we propose a framework for online group feature selection which has two components: intragroup selection and inter-group selection. The intra-group selection is to process features dynamically at their arrival. That is, when a group of features Gj arrives, we get a subset G′j from Gj. In this part, we design two novel criteria based on spectral analysis to obtain the subset. In terms of the features obtained by the intra-group selection, we further consider the global group information by introducing Lasso to get an optimal subset gj from G′j , namely the inter-group selection. In the following subsections, we will provide details for intra-group selection and inter-group selection.

3.1 Online Intra-Group Selection

Spectral feature selection methods have demonstrated excellent performance [Zhao et al., 2010]. Given a data matrix X ∈ Rd×n , a weighted graph with edges between data points close to each other is constructed. Let Sb ∈ Rn×n evaluate the between-class distance, and Sw ∈ Rn×n evaluate the within-class distances. In this work, we only consider supervised online feature selection. The between-class affinity matrix Sb and the within-class affinity matrix Sb are calculated as follows [Nie et al., 2008]:

where ni denotes the number of data points from class i.

Let the feature selector matrix W = [wi, · · · ,wm]T ∈ Rd×m where d is the number of features arrived and m is the number of features selected so far. wi = [wi1, · · · ,wid]T ∈ Rd , where wij = 1 indicates that the j-th feature is selected, while wij = 0 indicates that the j-th feature is discarded. Spectral feature selection approaches can be categorized into subset-level selection and feature-level selection approaches. The subset-level selection is to find an optimal subset U by maximizing the following criterion:

where WU corresponds to the features in subset U, Lb and Lw are the Laplacian matrices, Lb = Db - Sb, Db is a diagonal matrix, Db = diag(Sb1); Lw = Dw - Sw, Dw is a diagonal matrix and Dw = diag(Sw1).

The feature-level spectral feature selection approach evaluates feature fi by a score defined below:

After calculating scores of all features, the feature-level approach will select the leading features by the rankings of scores. As traditional spectral feature selection approaches rely on the global information, they are not efficient with online feature selection. Hence, we design two novel spectralbased criteria as follows.

Criterion 1 Given U ∈ Rb as the previously selected subset, fi denotes the newly arrived feature, we assume that with the inclusion of a "good" feature, the between-class distances will be maximized, while the within-class distance will be minimized. That is, feature fi will be selected if the following criterion is satisfied:

where ε is a small positive parameter (we use ε = 0.001 in our experiments.

However, with the increase of selected features, the criterion defined in Eq. (3) will be more and more difficult to be satisfied. Hence, to avoid leaving out discriminative features, we design a second criterion.

Criterion 2 Given U ∈ Rb as the previously selected subset, and the newly arrived feature fi, we calculate the score of feature fi by Eq. (4) which shows the discriminative power of the feature. If it is a significant feature with discriminative power, it will be selected.

The significance of a feature can be evaluated by the t-test [Zimmerman, 1997] defined bellow:

where |U| stands for the number of features in U, ˆµ and ˆσ are the mean and standard deviation of scores of all the features in U. If the t-value returned by Eq. (6) reaches 0.05, then the feature is assumed to be significant among the selected subset U and will be selected (0.05 is often used to measure the significance level).

After intra-group selection, we will obtain a subset G′j ∈ Rm′ from the original feature space Gj, G′j ⊂ Gj. As intragroup selection evaluates the features individually and does not consider the group information, we will apply inter-group selection.

3.2 Online Inter-Group Selection

In this subsection, we introduce Lasso to obtain an optimal subset based on global group information. Given the subset selected during the first phase G′j = [fj1, fj2, · · · , fjm′ ]T ∈ Rm′ , the previously selected subset of features U T ∈ Rb , the combined feature space with dimensionality of m′′ (m′ +d = m′′ ), a data set matrix X ∈ Rm′′×n , and a class label vector Y ∈ Rn , ˆ β = [ ˆ β1, · · · , ˆ βm′′ ] ∈ Rm′′ is the projection vector which constructs the predictive variable ˆ Y :

Lasso chooses an optimal ˆ β by minimizing the objective function defined as follows:

where || · ||2 stands for l2 norm, and || · ||1 stands for l1 norm of a vector, λ is a parameter that controls the amount of regularization applied to estimators, and λ ≥ 0 [Lu et al., 2012]. In general, a smaller λ will lead to a sparser model. By regression, the component in βi will be set to zero corresponding to feature fi which is irrelevant to the class label. Finally, the features corresponding to non-zero coefficients will be selected. After inter-group selection, we get the ultimate subset Uj .

With the combination of the online intra-group and the inter-group selection, the algorithm of Online Group Feature Selection (OGFS for short) can be formed.

3.3 OGFS: Online Group Feature Selection Algorithm

Algorithm 1 shows the pseudo-code of our online group feature selection (OGFS) algorithm. OGFS is divided into two parts: intra-group selection (Steps 4-15) and inter-group selection (Step 16). Details are as follows.

In the intra-group selection, for each feature fi in group Gj, we evaluate features by the criteria defined in Section 3.1. Steps (9-11) evaluate the significance of features based on criterion 1. With the inclusion of the new feature fi, if

Algorithm 1 OGFS (Online Group Feature Selection)

Input: feature stream F ∈ Rm∗q , label vector Y ∈ Rn . Output: selected subset U. 1: U =[], i = 1, j = 1; 2: while ψ(U) not satisfied do 3: for j = 1 to q do 4: Gj ←generate a new group of features; 5: for i = 1 to m do 6: G′j = []; 7: fi ← new feature; 8: /*evaluate feature fi by criterion 1, 2*/ 9: if F (fi ⋃ G′j ) - F (G′j ) > ε then 10: G′j = G′j ⋃ fi; 11: end if 12: if t(fi, U) > 0.05 then 13: G′j = G′j ⋃ fi; 14: end if 15: end for 16: gj ←find the global optimal subset G′j by Eq. (8); 17: U = U ⋃ gj 18: end for 19: end while

the within-class distance is minimized and the between-class distance is maximized, feature fi is thought to be a "good" feature and will be added to G′j . Steps (12-14) evaluate the features according to criterion 2. Based on the selected subset U, we validate the significance of the feature by t-test. If the t-value returned by Eq. (6) is larger than 0.05, feature fi is thought to be significant in discrimination. Then fi will be added to G′j . After intra-group selection, we get a subset of features G′j . To implement the global information of groups, we build a sparse representation model based on the selected subset U and the newly selected subset G′j . An optimal subset gj will be returned by the objective function defined in Eq. (8).

In our algorithm, the selected features will be revaluated in the intra-group selection in each iteration. The time complexity of intra-group selection is O(m), and the time complexity of inter-group selection is O(q). Thus, our OGFS algorithm, whose time complexity is linear with the number of features and the number of groups, is very fast.

The iterations will continue until the performance of ψ(U) reaches a predefined threshold as follows:

• |U| ≥ k, k is the number of features we need to select;
• accu(U) ≥ max, the predictive accuracy of the model based on U reaches the predefined accuracy max;
• There are no more features to come.

4 Experiments

In this section, extensive experiments are performed to validate the efficiency of our proposed method. We use the benchmark data sets with self-defined group feature structure and two image data sets with pre-existing feature structures. Several state-of-the-art online feature selection methods are used for comparison, including Alpha-investing and Fast-OSFS. The classification accuracy and the compactness (the number of selected features) are used to measure the performances of the algorithms in our experiments.

We divide this section into three subsections, including an introduction to our data sets, the experimental setting in our experiments and the experimental comparison conducted on the benchmark and real-world data sets. Details are as follows.

4.1 Data Sets

Our experimental data include benchmark data sets (the first 8 data sets) and real-world data sets (Soccer, the Flower-17 and 15 Scenes) described in Table 1. The column "groups" denotes the number of groups. The eight benchmark data sets are from the UCI repository (the first 4 data sets) and microarray domains 1 (colon, prostate, leukemia, and lungcancer) . The real-world data sets include: 15 Scenes 2 , the Soccer data set 3 and the Flower-17 data set 4 . The 15-Scenes data set contains totally 4485 images from 15 categories, with the number of images ranging from 200 to 400 per class. We take 100 images per class for training and the rest for testing. In our experiment setup, we use the SPM (Spatial Pyramid Matching) to partition each image into 21 segmentations and extract local information for each patch by the SIFT descriptor. Then the sparse coding is used for vector quantification [Zhao et al., 2012]. The Soccer data set contains 280 images from 7 football teams. We take 28 images per class for training and use the rest for testing. The Flower-17 data set contains 17 categories of flowers. We take 680 images for training and 340 images for testing. For both the Soccer and Flower-17 data sets, we use three descriptors, including PHOG, Color Moment and texture.

4.2 Experimental Settings

We describe the experimental setting here. The threshold parameter α is set to be 0.5 and 0.05 in Alpha-investing and Fast-OSFS, respectively. The sparse linear regression model of Lasso used in the inter-group selection is solved by SPAMS 5 with the parameter λ ∈ [0.01, 0.5].

To simulate online group feature selection, we allow the features to flow in by groups. For the eight benchmark data sets, we define the group structures of the feature space by dividing the feature space of each data set as follows. The global feature stream is represented by F = [G1, · · · ,Gi, · · · ], where Gi = [f(i-1)∗m+1, f(i-1)∗m+2, · · · , fi∗m] with m features. In our experiments, we can get optimal results if we set m ∈ [5, 10].

For the three real-world data sets, we use pre-existing feature groups, each of which represents a descriptor. That is, for the 15 Scenes data set, the global feature stream F = [G1, · · · ,G21]T ∈ R21∗1024 , where Gi ∈ R1024 denotes the SIFT descriptor for a local region of the image. For the Soccer and Flower-17 data sets, the global feature stream F = [G1,G2,G3]T ∈ R182 , where G1 ∈ R168 denotes the PHOG descriptor, G2 ∈ R6 denotes the Color Moment descriptor, and G3 ∈ R8 denotes the texture descriptor.

1 http://www.cs.binghamton.edu/ lyu/KDD08/data/

2 http://www-cvr.ai.uiuc.edu/ponce grp/data/

3 http://lear.inrialpes.fr/people/vandeweijer/soccer/soccerdata.tar

4 http://www.robots.ox.ac.uk/ vgg/data/flowers/

5 http://spams-devel.gforge.inria.fr/

The classification of the eight benchmark data sets is based on three classifiers, k-NN, J48 and Randomforest in Spider Toolbox 6 . We adopt 10-fold cross-validation on three classifiers and choose the best accuracy as the final result. For the real-world data sets, we use the nearest neighbor classifier.

All experiments are conducted on a PC computer with Windows XP, 2.5GHz CPU and 2GB memory.

4.3 Experimental Results on Benchmark Data

Table 2 shows experimental results of classification accuracy versus compactness on the eight benchmark data sets.

• OGFS vs. the Baseline

Though the Baseline is based on the global feature space, our algorithm outperforms Baseline on 7 out of the 8 data sets on both accuracy and compactness. On the data set Spambase, our OGFS is only 1% lower than Baseline but is much more compact. The results show that OGFS could efficiently select the features with most discriminative power.

· OGFS vs. Alpha-investing Alpha-investing obtains more compactness than our OGFS algorithm on 6 data sets, but it loses on 7 out of the 8 data sets in the accuracy except on the Spambase data set. On the Spambase data set, our algorithm achieves the same accuracy as Alpha-investing while obtaining more compactness. More specifically, on data sets Colon and Leukemia, the accuracies of Alpha-investing are 0.80 and 0.65 while OGFS reaches up to 0.91 and 1.0. This is because the previously selected subset will never be revaluated in Alphainvesting, which affects the selection of the later arrived features. However, in our algorithm, selected features will be revaluated in the inter-group selection in each iteration. Thus, our algorithm tends to select sufficient features with discriminative power.

6 http://www.kyb.mpg.de/bs/people/spider/main.html

• OGFS vs. Fast-OSFS

Fast-OSFS obtains more compactness on most of the data sets, but our algorithm is better than Fast-OSFS in accuracy on 7 out of the 8 data sets with a little compactness loss. More precisely, on the Spambase data set, the accuracy of our algorithm is slightly lower than FastOSFS, but it selects many fewer features. The reason is that Fast-OSFS evaluates features individually rather than in groups. Meanwhile, contrary to Fast-OSFS, our algorithm facilitates the relationship of features within groups and the correlation between groups, which will lead to the optimum of the ultimate subset.

Experimental results on benchmark data sets show that our algorithm is superior to Alpha-investing and Fast-OSFS in classification accuracy in most cases, while maintaining the compactness.

4.4 Experimental Results on Real-world Data Sets

The results obtained on real-world data sets with pre-existing group structures are shown in Table 3. As the original dimensionality of the 15 Scenes data set is more than 20,000, Fast-OSFS (provided by the authors) is out of memory when performing on this data set. We have the following observations:

• OGFS vs. the Baseline

OGFS obtains more compactness than Baseline on all the three data sets. On the Soccer data set, our algorithm obtains the best accuracy. The accuracy of OGFS on Flower-17 is only slightly lower than Baseline. Baseline outperforms OGFS on the 15 Scenes data set, but OGFS selects many fewer features while obtains the best accuracy among all the competing feature selection methods.

• OGFS vs. Alpha-investing

Compared to Alpha-investing, OGFS obtains higher accuracies with a little compactness loss. In particular, on the 15 Scenes data set, the accuracy of Alpha-investing is only 0.393, while our method could reach 0.54. The reason is the same as we mentioned above.

• OGFS vs. Fast-OSFS

OGFS outperforms Fast-OSFS on both compactness and accuracy on the Soccer data set. On the Flower-17 data set, OGFS and Fast-OSFS obtain the same accuracy while our algorithm achieves more compactness. These results demonstrate that our algorithm is better than Fast-OSFS when applied on real-world data sets with pre-existing group structures. The reason is the same as we analyzed before.

In sum, the above experimental results on real-world data sets reveal the effectiveness of our algorithm, and indicate that our algorithm is more suitable for real-world applications than existing state-of-the-art online feature selection methods.

5 Conclusion

In this paper, we have formulated the problem online group feature selection with a feature stream and presented an algorithm called OGFS for this problem. In contrast with traditional online feature selection, we have considered the situation that features arrive by groups in real-world applications. We divided online group feature selection into two stages, i.e., online intra-group and inter-group selection. Then we designed two novel criteria based on spectral analysis for intra-group selection, and introduced Lasso to reduce the redundancy in inter-group selection. Extensive experimental results on benchmark and real-world data sets have demonstrated that OGFS is superior to other state-of-the-art online feature selection methods.

Acknowledgments

The authors would like to thank Dr. Canyi Lu and Dr. Peipei Li for their helpful and informative discussions. This research was supported by the National Natural Science Foundation of China (Nos. 61005007, 61229301, 61272366, 61272540, and 61273292), the US National Science Foundation (NSF CCF0905337), the 973 Program of China (No. 2013CB329604), the 863 Program of China (No. 2012AA011005), the Hong Kong Scholars Program (No. XJ2012012) and the Research Grant Council of Hong Kong SAR (No. HKBU 210309).