Scalable Feature Selection in High-Dimensional Data Based on GRASP

Abstract

Feature selection in high-dimensional data is one of the active areas of research in pattern recognition. Most of the algorithms in this area try to select a subset of features in a way to maximize the accuracy of classification regardless of the number of selected features that affect classification time. In this article, a new method for feature selection algorithm in high-dimensional data is proposed that can control the trade-off between accuracy and classification time. This method is based on a greedy metaheuristic algorithm called greedy randomized adaptive search procedure (GRASP). It uses an extended version of a simulated annealing (SA) algorithm for local search. In this version of SA, new parameters are embedded that allow the algorithm to control the trade-off between accuracy and classification time. Experimental results show supremacy of the proposed method over previous versions of GRASP for feature selection. Also, they show how the trade-off between accuracy and classification time is controllable by the parameters introduced in the proposed method.

INTRODUCTION

In recent years, increasing growth of machine readable data (digital information) has led to new challenges for machine learning algorithms. Nowadays, many tasks in machine learning such as clustering, classification, and regression deal with huge datasets. In these tasks, a machine learning algorithm should analyze the related datasets entirely and fit them to a model. The huge size of most datasets generally leads to unacceptable process time or intractable complexity. The size of a dataset depends on the number of its instances and the dimensionality of feature space. Dimensionality of a dataset is the same as the number of features that describe each instance. Therefore, reduction of the number of dataset instances and features are two main problems to consider in reducing the size of datasets. Sampling methods can be used to reduce the number of instances.

Dimension reduction is the process of transforming a feature space to another one with lower dimensionality. Dimension reduction is divided into two main categories: transformation-based dimension reduction and selection-based dimension reduction. Principal component analysis (PCA) is an efficient and well-known transformation-based dimension reduction method. Feature selection is a type of dimension reduction in which the meaning of the features after reduction is similar to the original features. Benefits of feature selection include reducing data processing time, improving the accuracy of machine learning tasks such as classification and regression, and making the data available in a more compact and more understandable form. Usually, redundant and irrelevant features increase the complexity of the learning process. Knowledge discovery in a large dataset is more difficult and sometimes intractable.

In high-dimensional datasets, drawbacks of redundant and irrelevant features become even more critical. In this case, feature selection is almost unavoidable. In this study, a new feature selection method for high-dimensional data is proposed.

FEATURE SELECTION

Given a dataset with n features, there are 2ⁿ−1 nonempty feature subsets, each with the potential to become the optimal subset for representing that dataset within the specific problem area. Subset generator and subset evaluator are main components of a feature selection method. Hence, feature selection methods can be distinguished from each other according to these components.

Subset generator is equivalent to a searching method that determines the sequence of subset evaluations. By definition, the best subset generator reaches to optimal feature subset as fast as possible. There is no unique method with optimal performance for all problem areas.

Subset evaluator is the second component of a feature selection method. It determines the merit of each feature subset. Ideally, it should assign the best merit to the optimal feature subset, which contains the most relevant features to the target feature and excludes irrelevant and redundant features as much as possible. The overall procedure of feature selection is depicted in Figure 1.

FIGURE 1 Overall procedure of feature selection.

There are three types of feature selection methods: filters, wrappers, and hybrids (or embedded). Most filter methods use measures that usually have a background in statistics or information theory. Feature subsets are not directly scored by fitting a model on them and measuring accuracy or error rate of the model. Data variance, correlation coefficient, Fisher score (Chen and Li 2010; Chen and Lin 2006), and chi-squared (Hoel 1984) are statistical filter measures, and mutual information (Estévez et al. 2009; Novovičová et al. 2007), max-dependency, max-relevance, min-redundancy (Peng, Long, and Ding 2005), information gain (Liu and Yu 2005), and gain ratio (Duda, Hart, and Stork 2001) are some of the information-theory-based measures. Filter measures are not limited to these two categories, and some other kinds of measures exist such as class separability (Liu and Zheng 2006) and RELIEF measure (Dash and Liu 1997). Ratanamahatana and Gunopulos (2003) proposed a simple method that uses a filter method implicitly. They trained a C4.5 decision tree on the training set and then trained a new classifier named selective Bayesian classifier (SBC) that uses features selected by the C4.5 decision tree. They claimed that SBC outperforms naïve Bayes and C4.5 classifiers.

Wrappers use predictors and fit models on data to evaluate feature subsets. They need to train a predictor (classifier or regression model) to evaluate each feature subset; therefore, they are more precise but slower than the filters. The main challenges in wrapper methods are selecting a proper predictor (Li et al. 2009; Maldonado and Weber 2009; Monirul Kabir, Monirul Islam, and Murase 2010; Sánchez-Maroño and Alonso-Betanzos 2011) and how to generate appropriate subsets (Macas et al. 2012; Tay and Cao 2001; Vignolo, Milone, and Scharcanski 2013). Finally, hybrid methods use both filter and wrapper evaluators simultaneously (Bermejo et al. 2012; Bermejo, Gámez, and Puerta 2011; Gheyas and Smith 2010; Ruiz et al. 2012). In the hybrid approaches, filter measures are usually used when a rough evaluation is acceptable, and the wrapper evaluator is utilized when more precise evaluation is needed. Hybrid approaches are meant to establish an intermediate solution by combining the advantages of filters and wrappers and managing a trade-off between speed and precision.

RELATED WORKS

In many real-world applications such as bioinformatics (Armananzas et al. 2011; García-Torres et al. 2013; Akand, Bain, and Temple 2010), medicine (da Silva et al. 2011), text mining (Azam and Yao 2012; Feng et al. 2012; Meng, Lin, and Yu 2011; Pinheiro et al. 2012; Uğuz 2011; Imani, Keyvanpour, and Azmi 2013), image processing (Jia et al. 2013; Rashedi, Nezamabadi-pour, and Saryazdi 2013; Vignolo, Milone, and Scharcanski 2013) remote sensing (Ghosh, Datta, and Ghosh et al. 2013; Guo et al. 2008; Li et al. 2011) and other domains (Pérez-Benitez and Padovese 2011; Wu et al. 2010; Zhang et al. 2011; Waad, Ghazi, and Mohamed 2013), the dimensionality of data are so high that they may lead to the breakdown of an ordinary feature selection algorithm. High dimensionality of the data asks for the development of more complicated methods to apply feature selection on a large number of features.

In addition, in many data analysis tasks, multiple interacting features are ignored assuming independency between features or considering only pair-wise features interaction (Zhanga, Chena, and Zhoub 2008). Zhang and Hancock (2012) address the problem of considering multiple interacting features in high-dimensional datasets. Their work was inspired by studies on hypergraph clustering to evaluate feature subsets. They proposed a new evaluation measure based on information theory called multidimensional interaction information (MII) that determines significance of different conditional feature subsets with respect to the decision feature. In the case of datasets with a combination of nominal and numerical features, Michalak et al. (2011) proposed a new feature similarity measure based on the probabilistic dependency between features.

A considerable number of the reported works concentrate on efficient search in feature subsets space. Each point in feature subsets space is a subset of features. Ahila, Sadasivam, and Manimala (2012), proposed an evolutionary algorithm based on particle swarm optimization (PSO) to perform simultaneous feature and model selection. They used a probabilistic neural network as the classifier and PSO as the searching algorithm to explore feature subset space and model parameters. Bermejo, Gámez, and Puerta (2011) proposed a new search method that reduces the number of wrapper evaluations by iteratively switching between filter and wrapper evaluations. Their method is based on the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic algorithm. GRASP is a two-step iterative algorithm in which in each iteration a solution is initially constructed and is improved later. In this algorithm, in the construction step, evaluation is carried out using a lighter filter measure, while during the improvement step a more costly wrapper measure is utilized.

Bermejo, Gámez, and Puerta (2011) proposed a new combinatorial method. Their algorithm iteratively switches between filter and wrapper evaluators. It uses a filter evaluator for constructing a ranked list of the features and considers the first block of the ranked features as selected candidates for inclusion in the wrapper evaluator’s selected features. The algorithm stops when there are no new feature candidates for inclusion in the wrapper evaluator’s feature selection.

GRASP FOR FEATURE SELECTION (FCGRASP)

Feature selection can be formulated as an optimization problem. In this case, feature selection is a search procedure for finding a subset of conditional features with the most relevancies to the target feature. This section is devoted to reviewing the application of GRASP for feature selection in high-dimensional data.

GRASP is a two-phase optimization algorithm introduced by Feo and Resende (1989). Extensions of this algorithm and its applications can be found in their subsequent works (Feo and Resende 1995; Festa and Resende 2010; Resende and Ribeiro 2010). The two phases of the GRASP include

• Construction phase: in this phase, a greedy randomized heuristic algorithm is used to construct a solution with which to begin. The process starts from an empty set and enlarges the set by selecting items from a randomly selected list of promising candidates.

• Improvement phase: here, the algorithm improves the output of the construction phase using a local search algorithm. The constructed solution is fed to the local search algorithm as an initial point.

GRASP is an iterative algorithm. During each iteration, after the completion of these phases, both the constructed and the improved solutions are added to nondominated solutions. The nondominated solutions set is a set of solutions in which no item has a complete priority over any other one. This is because in GRASP we are dealing with a multiobjective optimization problem.

Bermejo, Gámez, and Puerta (2011) introduced FCGRASP, a new search method for feature selection in high-dimensional data that reduces the number of wrapper evaluations by alternatively switching between filter and wrapper evaluations. Their proposed method is based on the GRASP metaheuristic algorithm. It is a two-step iterative algorithm in which, in each iteration, a solution is constructed and then improved. In this algorithm, evaluation process in the construction phase is performed using a lighter filter measure while improving the constructed solution is performed using a costly wrapper. This algorithm is depicted in Figure 2.

FIGURE 2 GRASP algorithm for feature selection (FCGRASP).

The GRASP algorithm for feature selection has two input parameters: 1-Size: determines the number of features to be considered at each iteration, and 2- NumIter: determines how many iterations the algorithm needs. The only output variable of the algorithm is a set of nondominated solutions (NDS). A set of solutions is said to be nondominated if no member of the set is dominated by another in terms of length and precision simultaneously.

The first part of the algorithm is the initialization presented in lines 7–11 of the algorithm. At this stage, NDS is initialized to be empty and a probability is assigned to each feature. These probabilities are proportionate to predictability of a decision feature (class label or target feature) based on each conditional feature. In other words, each assigned probability is proportionate to the relevancy of the conditional feature and the decision feature. This relevancy can be evaluated by any filter or wrapper measure and stored in ProbSel array of variables.

After initialization, construction and improvement phases are performed iteratively (lines 13 to 29). Each iteration starts with the construction phase and ends after the improvement phase. The number of iterations is determined by NumIter parameter. In the construction phase (lines 15 to 24), a subset of features is randomly sampled from the set of all features. The chance of selecting feature X_i is proportionate to ProbSel[i]. The number of selected features is determined by the Size parameter and the subset is stored in the Subset variable. The Subset variables comprise an unsorted set; therefore, its features are sorted and stored in a new list R. The final step of the construction phase is to add features to the solution subset S incrementally. Initially, S contains only the best feature of R. Then, from the second features to the last, all features are checked, and if a feature improves the accuracy of classification, it is added to S.

The improvement phase is performed at the second part of the iteration. This phase is performed if and only if there are no solutions in NDS to dominate the last solution S constructed during the same iteration. Consequently, a new constructed solution is added to the NDS and the improvement phase begins. During the improvement phase, a local search algorithm is applied to the current solution S. There are several options, one of which is to search locally using methods such as hill climbing, simulated annealing (SA) and genetic algorithms (GA). In their reported work, Bermejo, Gámez, and Puerta (2011) used a hill climbing algorithm for the improvement phase.

THE PROPOSED METHOD

There are some drawbacks in using hill climbing as the choice for the local search algorithm. In this section, a new method based on GRASP is proposed that uses an adopted version of SA for the improvement phase. The extended version of SA is presented in Figure 3. Compared against the hill climbing algorithm, advantages of the proposed SA-based improvement phase include the following:

• It is more likely to escape the local minimums in SA whereas there is no chance to escape in hill climbing.

  FIGURE 3 An extended version of SA used in the improvement phase.

  

• In each iteration, SA needs only one wrapper evaluation whereas hill climbing needs to evaluate all successor states. The number of all successors of each state is proportionate to the number of features in X_nds. Here, each successor state is constructed by adding a feature from X_nds to the current state or by removing a feature from the current state. It allows SA to have more steps than hill climbing and further exploration.

• As the most important characteristic for this version of SA, it is made possible to implicitly control the trade-off between the length of the solution (number of finally selected features) and the precision of the results. In the proposed version of SA, there is a parameter to control the length of the solution.

The pseudocode of the proposed version of SA algorithm is shown in Figure 3.

The algorithm starts with initialization at lines 9 and 10. In these lines, the current state of the algorithm Sol is initialized to specified input parameter S which determines the start of the search point, and then the merit of Sol calculates and stores in CurPrecision. Lines 11 to 25 represent the iterative part of the algorithm. The number of iterations is determined by NumIter parameter. Iteration consists of two steps: (1) constructing a successor state, and (2) acceptance or rejection of the constructed state. In the first step, the successor state is constructed by randomly adding one of features from X_nds that currently does not exist in the current state or by randomly removing a feature from the current state (lines 13 to 16). In the second step, the algorithm decides whether to accept or reject the new state. If the successor state S′ is better than the current state Sol, the current state is replaced with its successor, otherwise, replacement may occur with a probability proportionate to the current iteration of the algorithm and the difference between quality of these two states (CurPrecision-AuxPrecision or ΔP). The diagrams in Figure 4 show how acceptance probability changes against ΔP for different values of T. T is a variable that has maximum value k_temperature at the start of the algorithm and linearly decreases to 0 while algorithm approaches to the end. When T is high, it is more likely to accept worse states, and when it reaches to its minimum 0, there is no chance for worse states to be selected.

FIGURE 4 The acceptance probability against ΔP in the proposed SA.

Using this version of SA in the improvement phase of GRASP algorithms results in a new algorithm referred to as SAGRASP in what follows.

EXPERIMENTAL RESULTS

In this section, the results of comparing GRASP and SAGRASP are presented. The experiments reported are meant to compare the precision and speed of GRASP and SAGRASP, and also investigate the effect of SAGRASP parameters in implicitly controlling the size of the selected subset.

Experiment Setup and Datasets

Experiments are performed on 9 high-dimensional datasets (Feature Selection Datasets 2013¹; UCI Machine Learning Repository 2013²) selected from different areas such as cancer prediction based on mass spectrometry, and text classification. Also, they are diverse enough in different aspects such as number of instances, number of features, and number of classes. Their characteristics are listed in Table 1.

TABLE 1 Characteristics of the Datasets

Dataset	Abbreviation	#instances	#features	#classes
Connectionist Bench	CB	200	60	2
WarpPIE10P	WAR	210	2420	10
PCMAC	PCM	1943	3289	2
TOX-171	TOX	171	5748	4
Arcene	ARC	200	9961	2
Pixraw10P	PIX	100	10000	10
ORLRaws10P	ORL	100	10340	10
CLL-SUB-111	CLL	111	11340	3
GLI-85	GLI	85	22283	2

Algorithms are implemented in MATLAB 2010a on a PC with Intel Core2Due CPU 2.8 GHz and 2GB RAM. All wrapper evaluations are performed by embedded functions in MATLAB 2010a for training and testing decision trees. The output of each wrapper evaluation is the average accuracy obtained by 10 decision trees that trained independently.

TABLE 2 The Accuracy, Runtime, and Parameters Set for FSGRASP and SAGRASP

						Parameters
Abbreviation		FCGRASP Precision	SAGRASP Precision	FCGRASP Run-Time	SAGRASP Run-Time	Size	NumIter	K_temp	P_add	SA_iter
1	CB	0.873	0.895	149	2054	20	100	0.5	0.7	1000
2	WAR	0.937	0.940	802	1865	150	100	1	0.75	1000
3	PCM	0.976	0.976	1278	1677	150	100	0.5	0.5	1000
4	TOX	0.926	0.967	1622	3867	200	100	1	0.75	1000
5	ARC	0.923	0.930	1502	4209	300	100	0.5	0.7	1000
6	PIX	1.000	1.000	1628	2036	300	100	2	0.75	1000
7	ORL	1.000	1.000	1684	1688	300	100	0.5	0.7	1000
8	CLL	0.868	0.865	4655	1599	300	100	10	0.6	500
9	GLI	0.972	0.972	2784	3364	500	100	0.5	0.5	1000

Experiment 1: FSGRASP vs. SAGRASP

Table 2 shows the results of running FSGRASP and SAGRASP on 9 datasets introduced in Table 1. Columns 3 and 4 show average accuracy of these two algorithms in 10 runs over the specified datasets. Columns 5 and 6 show the average runtime in seconds. The last five columns show parameter values used in algorithms. While Size and NumIter are used in both, K_temp and P_add, SA_iter is used only in SAGRASP. These parameters were explained in previous sections (see algorithms in Figures 2 and 3). Time complexity of both algorithms is proportionate to

(1)

in which WE is the time complexity of wrapper evaluations and LS is the time complexity of running local search algorithms (hill climbing in FSGRASP and SA in SAGRASP). The parameters Size and NumIter have a linear effect on the total execution time of these algorithms. Thus, these parameters are not set based on trial and error, but they are set according to processing limitations and the number of features in each dataset (NumIter fixed to 100 and Size is set to a number between 20 and 500 based on the number of features in each dataset).

As seen in Table 2, SAGRASP outperforms FSGRASP significantly on CB and TOX datasets and slightly on ARC dataset. Over other datasets, there is no preference between algorithms. With respect to runtime, FSGRASP outperforms SAGRASP in almost all cases, but it is not too important because as the number of features increases, the difference between runtime of algorithms decreases. For example, FSGRASP is 13.8 times faster than SAGRASP over the smallest dataset CB, but in datasets with a higher number of dimensions such as ORL, CLL, and GLI there is no significant difference between the two algorithms.

Experiment 2: Trade-Off Between Accuracy and Runtime

The results of the GRASP algorithm for feature selection in high-dimensional datasets show its superiority over a wide range of feature selection methods as presented in (Bermejo, Gámez, and Puerta 2011). The main superiority of SAGRASP over GRASP is not in accuracy improvement, but in its capability to explicitly control the trade-off between accuracy and runtime. This capability is related to P_add parameter of the proposed algorithm. Figure 5 shows the effect of P_add on accuracy over the ARC dataset. As depicted in Figure. 5, there is a high correlation between P_add and accuracy such that as P_add increases, the accuracy also increases.

FIGURE 5 The effect of acceptance probability on accuracy over the ARC dataset.

Figure 6 shows a similar relationship between P_add and the size of the selected subset of features.

FIGURE 6 The effect of acceptance probability on the size of the selected subset of features over the ARC dataset.

CONCLUSIONS AND FUTURE WORKS

In this article, a new feature selection algorithm for high-dimensional datasets, named SAGRASP, was proposed. It uses the GRASP algorithm as its basic framework and applies it with an extended version of SA as a local search algorithm. The proposed algorithm has two advantages over FSGRASP: better accuracy and controllability. SAGRASP outperforms FSGRASP significantly over two datasets. It has a P_add parameter to control the trade-off between accuracy and classification time.

Although the proposed method can implicitly control the trade-off between accuracy and classification time, it is still unable to control it explicitly. In other words, it is possible to increase or decrease the number of selected features by changing P_add parameter, but it is not clear how P_add must be set in order to obtain a specific number of features. An open line of research is to extend the proposed method in order to perform the control explicitly.

Notes

¹ http://featureselection.asu.edu/datasets.php, retrieved September 21, 2013.

² http://archive.ics.uci.edu/ml/datasets.html September 21, 2013.