Skip to main content
Advertisement
Browse Subject Areas
?

Click through the PLOS taxonomy to find articles in your field.

For more information about PLOS Subject Areas, click here.

  • Loading metrics

DWFS: A Wrapper Feature Selection Tool Based on a Parallel Genetic Algorithm

  • Othman Soufan,

    Affiliation King Abdullah University of Science and Technology (KAUST), Computational Bioscience Research Center (CBRC), Computer, Electrical and Mathematical Sciences and Engineering Division (CEMSE), Thuwal 23955–6900, Saudi Arabia

  • Dimitrios Kleftogiannis,

    Affiliation King Abdullah University of Science and Technology (KAUST), Computer, Electrical and Mathematical Sciences and Engineering Division (CEMSE), Thuwal 23955–6900, Saudi Arabia

  • Panos Kalnis,

    Affiliation King Abdullah University of Science and Technology (KAUST), Computer, Electrical and Mathematical Sciences and Engineering Division (CEMSE), Thuwal 23955–6900, Saudi Arabia

  • Vladimir B. Bajic

    vladimir.bajic@kaust.edu.sa

    Affiliation King Abdullah University of Science and Technology (KAUST), Computational Bioscience Research Center (CBRC), Computer, Electrical and Mathematical Sciences and Engineering Division (CEMSE), Thuwal 23955–6900, Saudi Arabia

Abstract

Many scientific problems can be formulated as classification tasks. Data that harbor relevant information are usually described by a large number of features. Frequently, many of these features are irrelevant for the class prediction. The efficient implementation of classification models requires identification of suitable combinations of features. The smaller number of features reduces the problem’s dimensionality and may result in higher classification performance. We developed DWFS, a web-based tool that allows for efficient selection of features for a variety of problems. DWFS follows the wrapper paradigm and applies a search strategy based on Genetic Algorithms (GAs). A parallel GA implementation examines and evaluates simultaneously large number of candidate collections of features. DWFS also integrates various filtering methods that may be applied as a pre-processing step in the feature selection process. Furthermore, weights and parameters in the fitness function of GA can be adjusted according to the application requirements. Experiments using heterogeneous datasets from different biomedical applications demonstrate that DWFS is fast and leads to a significant reduction of the number of features without sacrificing performance as compared to several widely used existing methods. DWFS can be accessed online at www.cbrc.kaust.edu.sa/dwfs.

Introduction

In the last decade, the leading high-throughput experimental techniques in biology, such as next generation sequencing, mass spectrometry, array-based methods and others, let to the massively increasing volume and dimensionality of the produced data in this field. This expansion in volume and dimensionality of data is also occurring in many other domains such as, for example, web content, social networks, graphical information systems, etc. From a Data Mining perspective, the need for faster, more reliable and more cost-effective classification models based on such data requires the extraction of a smaller and optimized set of features that can be obtained by removing largely redundant, irrelevant and unnecessary features for the class prediction [1]. A reduced number of features may also in some cases improve the classification performance [1]. In addition, the reduced number of features may lead to a better description of the underlying process from which data is generated and, thus, may contribute to better interpretation of the results [2]. Consequently, the feature selection (FS) problem is a fundamental problem for the development of efficient data-driven Machine Learning models. Although FS has a great use in many fields, we will restrict our consideration to biology and biomedical domains [3,4].

There are three basic FS methodologies: a/ the filters, b/ the wrappers, c/ and those based on the embedded FS models.

a/ Filtering approaches are mostly fast statistical methods that rank features according to specific criteria. In principle, filters do not get feedback from classification models. When the set of top ranked features is used for class prediction, classification performance is frequently inferior to the case when all features are used.

b/ In the wrapper models the process of FS is tied to the performance of a specific classification model and FS is made using some optimization methods and various search strategies [5]. A well-studied variant of the wrapper model is the randomized one, which relies on search strategies such as, for example, genetic algorithms (GA), hill climbing and simulated annealing. In these methods, through iterations, numerous heuristically selected feature subsets are evaluated based on the resultant error of the classifier. Based on the characteristics of the feature search space from where features are selected, evolutionary search methods like GA may be able to avoid to stuck in locally optimal solutions although there is no guarantees for this [5,6]. While this is an advantage, on the downside the wrapper-based FS combined with randomized search strategies is a very computationally demanding task. Also, the wrapper-based FS may lead to the selection of features biased to the classifier used in the wrapper [7,8].

c/ Embedded FS methods incorporate FS into the model development process. In the embedded FS setting, searching for the optimized feature subsets is a combined optimization process comprising selection of optimized set of features and tuning parameters of the model. A well-known embedded FS method is based on Decision Trees that has an automated FS strategy to select features according to the class discrimination capability [9].

Some of the FS methods used for biological and biomedical problems are not general enough and may be developed for specific data types (i.e., those obtained from microarrays).

With all the above-mentioned issues in mind we developed DWFS, an on-line web-based FS tool that follows the GA-based wrapper paradigm. To the best of our knowledge, there is no other FS web tool that provides: 1/ a hybrid combination of wrapper-based FS with effective filtering FS methods, 2/ parallel implementation that reduces the time required for FS, 3/ options to optimize the wrapper setting and tune weights and parameters of the FS process according to the application requirements, and 4/ applicability to a broad spectrum of applications and processing of larger multi-dimensional datasets (not only from biology and biomedicine) that existing web-based FS tools may fail to handle. DWFS is aimed for biologists that have little or no computer skills.

Our experimentation with several benchmark datasets from different biological and biomedical problems demonstrates that DWFS is capable of reducing significantly the number of original features without sacrificing classification performance. Moreover, through the use of different performance indicators we show that DWFS performs well relative to the existing FS methods.

Materials and Methods

Prevalent FS techniques used for biomedical problems

Previous review articles addressed the importance of selecting relevant features in biological and biomedical problems and illustrated the state-of-the–art methods [4,10,11]. From the category of wrappers, FST3 [12] and WEKA [13] offer a variety of wrapper and filtering models based on different search strategies. WEKA is widely used for its easy access and functionality. However, it is not scalable to multicore computers or high-end clusters and consequently as the data volume increases it cannot handle effectively computationally intensive FS in the wrapper setting.

From the category of filters, mRMR [14] belongs to multivariate filtering methods and a web tool is available. However, the web-tool has some limitations since only input files with size less than 2 MB are supported. FSelector [15] presents an extensive collection of existing filtering algorithms implemented in a Ruby package whereas, the CBFS algorithm [16] introduces the clearness-based scoring scheme for describing features that maximize separability between the classes.

There are also many dataset-specific FS methods, e.g. ArrayMining [17] that targets selection of genes from microarray datasets, Multi-Relief that [18] ranks crucial residues for protein functionality or MetaboloAnalyst [19] that selects important metabolites from metabolic network data. Table 1 summarizes the advantages and disadvantages of the above-mentioned FS techniques.

thumbnail
Table 1. FS programs frequently used in biomedical applications.

https://doi.org/10.1371/journal.pone.0117988.t001

DWFS web-tool

Search strategy description. DWFS takes as input text files with tab-delimited format where rows represent data samples and columns represent features. The last column represents class labels. The multiclass classification tasks (classes> = 2) are supported. The wrapper FS search strategy is based on GA that is a well-known heuristic optimization technique inspired by the principles of natural selection [6]. Initially, a starting population Θ0 = {θ01, θ02,…, θ0r} (the collection of initial solutions) of individuals θ0i,i = 1,2,…,r, where r is the number of individuals, is formed. The individuals represent chromosomes. Note that in our case the chromosomes are always described by vectors of length n whose components correspond to genes (features); n is the number of all features. The values of the components are binary 1s and 0s, where ‘1’ encodes the existence and ‘0’ the absence of a gene. In the initial population chromosomes are initialized by a random selection of 1s and 0s. In GA, the population changes in each evolutionary cycle forming different generations. An evolutionary cycle k, is characterized by the population Θk = {θk1, θk2,…, θkr}; θki represents the ith chromosome in population Θk. In every evolutionary cycle, a fitness value is computed based on a predefined fitness (objective) function. DWFS uses the fitness function described by Equation (1), where Performanceki) is the classification performance achieved by using chromosome θki, sizeki) is the sum of binary 1s in chromosome θki, and α is a weighting parameter (default 0.15).

(1)

Note that in our case the actual Performance function is determined by the selected criterion from the web-tool. Then, GA applies two operations, crossover and mutation, and the best solutions are selected to survive to the next generation. The optimization process is run for a specified number of evolutionary cycles, during which time GA attempts to increase the value of the fitness function. The chromosome that produces the largest value of the fitness function during this specified number of evolutionary cycles is considered an optimized solution and it may or may not be the global (optimal) solution. It is difficult to know if the obtained optimized solution is the global one. The procedure terminates whenever termination criteria are satisfied [6].

Implementation. DWFS search strategy is based on the PGAPack software [20], which is a collection of libraries that execute all GA steps. PGAPack deploys a parallel master/slave single population GA using the message-passing interface (MPI). Master node stores the initial population and applies the GA operations. Slave nodes are responsible for evaluating the fitness function for every chromosome. The master/slave paradigm is very efficient in terms of execution time because the most costly part is the fitness function evaluation, whereas the communication overhead is minimal [21]. Fig. 1 demonstrates the GA algorithm under the master/slave framework of PGAPack. In principle, increasing the population size does not necessarily improve the classification performance as there is no guarantee that the algorithm will be able to find any better solution than it does with the original population size. We use a population size of 100 individuals, which is a good compromise considering the trade-off between the performance and over-fitting [22]. Note, that DWFS master/slave model was deployed on a cluster with nodes having 64-cores. In our experimentation in one experiment 63 cores are used for replacing the old solutions for every new generation and the 64th core (i.e. the master) was responsible only for executing the GA operators. In the first population we initialize genes to 0 and 1 randomly with equal probability and we ensure that a chromosome containing all genes set to 1 is present (i.e., this represents the solution that contains all features). In our implementation we adopt constant rates for crossover and mutation. The crossover operator produces new offspring by combining genes of two chromosomes (they are considered parents in the GA terminology). We use two-point crossover technique that swaps all genes between two crossover points for both chromosomes. The following example illustrates the two-point crossover operation over a pair of chromosomes with 9 genes.

Chromosome1 (Parent1): [0 0 1 1 0 1 1 0 1]

Chromosome2 (Parent2): [1 1 1 0 0 0 1 1 1]

Two-point crossover operator ↓

Chromosome1 (Child1): [0 0 1 0 0 0 1 0 1]

Chromosome2 (Child2): [1 1 1 1 0 1 1 1 1]

The underlined features in the chosen parent solutions indicate the points within which crossover will take place (i.e. genes between these points will be crossed-over to generate child solutions). A pre-defined crossover rate will determine the number of genes where crossover will take place.

Mutation modifies specific genes of a given chromosome. We use the simple bit-string mutation that flips specific genes at random positions. Both GA operations simulate parts of the natural evolutionary process and are used to control transfer of information between different generations of population. The evolution of the population follows a binary tournament selection, where the best two chromosomes in the population are selected to serve as parents of new offspring. The GA operators including selection, mutation and crossover are then carried over in an iterative process through a predefined number of generations.

Tuning search strategy parameters. Depending on the application requirements users can specify mutation and crossover rates, as well as the number of generations for the optimization procedure. After experimentation with different mutation and crossover rates we observed that values close to 0.8 for crossover and 0.01 for mutation are effective in various classification tasks (see also [5]). These values we selected as default for DWFS. The effects of extensive experimentation with various mutation and crossover rates for all datasets are captured in Fig. 2 and Fig. 3. Both Fig. 2 and Fig. 3, indicate a considerable sensitivity of GA towards mutation and crossover rates. Overall, increasing either one of these rates leads to not exploiting surrounding regions of good solutions and mostly exploring the search space in a random manner. This is apparent in Fig. 2 and Fig. 3 for most of the datasets. More results about the effects of mutation and crossover rates over stability and reduction in size of selected features are provided in S1 Table and S2 Table. The default number of evolutionary cycles in DWFS is 100. Also, in order to reduce the processing time we included additional stopping criteria in which we consider that the population has reached the steady-state (i.e. it has converged) if there is no difference in the fitness function value for 50 consecutive generations.

thumbnail
Fig 2. Effects of changing mutation rate on GMean of NBC.

For every mutation rate on each dataset, a full run of GA is executed for 5 times to compute scores over the 5-folds of the dataset. The specific used mutation rates are 0.01, 0.05, 0.1, 0.25, 0.5, 1.

https://doi.org/10.1371/journal.pone.0117988.g002

thumbnail
Fig 3. Effects of changing crossover rate on GMean of NBC.

For every mutation rate on each dataset, a full run of GA is executed for 5 time to compute scores over the 5-folds of the dataset. The specific applied crossover rates are 0.5, 0.7, 0.8, 0.9, 1.

https://doi.org/10.1371/journal.pone.0117988.g003

Modifying the fitness function. DWFS supports different validation methods and users can choose between automatic split of data to training and testing sets, or the custom option in which they can upload explicitly the training and testing datasets. DWFS offers different performance metrics for the fitness function from Equation (1) including accuracy, geometric mean of sensitivity and specificity (GMean), F1-score and Mathews Correlation Coefficient (MCC). Possibility to select different performance metrics for the optimization process increases the utility of DWFS. For instance, GMean is preferable in cases where the data classes are highly imbalanced [23]. Three different classification models can be used: a/ Naïve Bayes Classifier (NBC-in-house implementation), b/ K-Nearest-Neighbors (KNN) available from the AlgLib library (http://www.alglib.net/) [24], and c/ and the combination of a/ and b/. In principle, selecting more than one classifier tends to minimize potential bias towards a particular type of classifier. The idea behind this is relatively simple: features selected using a single classifier in the wrapper FS usually result in higher performance for that particular classification model and weaker performance for other classifiers. Including a combination of classifiers in the wrapper FS setting, may lead to the selection of a feature subset that is less biased, but this is not guaranteed.

Hybrid combination of filtering and wrapping. When the number of features is very large, the GA becomes very computationally demanding and its run time can be prohibitive. To reduce the time required for training, DWFS supports a two-phase hybrid combination of filtering and wrapping. In the first phase, filtering is applied as a pre-processing step and the top-ranked features are selected based on a pre-defined but tunable threshold. In the second phase, the GA-based wrapper FS is applied to the selected features, which in practice means that the FS process uses a much smaller search space instead of the original large search space. This heuristic optimization technique may or may not result in combinations of features that have high discriminative power. However, this cannot be known in advance. In practice, however, the experiments show that this heuristics performs well and that it is fast and memory efficient for datasets described by large number of features and having large number of samples. Of course, the user may choose not to use filtering at all. Current implementation of DWFS incorporates the following well-known and widely-used filtering techniques: minimum redundancy maximum relevance (mRMR) [14], joint mutual information (JMI) [25], conditional mutual information maximization (CMIM) [26] and interaction capping (ICAP) [27]. mRMR selects features based on the minimum redundancy-maximum relevancy criterion. Both JMI and CMIM are based on different notions of mutual information (joint vs conditional), whereas ICAP selects features based on the concept of “interaction” of the class label with different sets of features. Recently, a study has proposed a unifying framework for information theoretic feature selection that derive the previous criteria from conditional likelihood of the training labels [28]. In particular, the scoring criteria including mRMR, JMI, CMIM and ICAP can be derived from the following function F described by Equation (2).

(2)

The first term is a likelihood ratio between the true distribution p(y|xθ of a class given some particular selected features xθ and the predicted class distribution q(y|xθ, τ) given the selected features and a model parameter τ, averaged over the input space. Given the selected features Xθ, defines conditional mutual information between the class label Y and the unselected features . The final term H(Y|X) is the conditional entropy of labels Y given all original set of features X. In [28] a rigorous derivation of many information theoretic measures for feature selection from Equation (2) is provided to eventually reveal either a direct or conditionally dependent relationship between the target label and the selected features of dataset.

Results and Discussion

Experimental setup

Datasets. In our experiments we use nine datasets related to different biomedical problems. Table 2 summarizes the number of samples, number of features, ratio between positive and negative samples and corresponding data sources. We chose on purpose datasets from a broad spectrum of different problems to demonstrate that DWFS is a general tool for FS and that it performs well over a variety of different types of data.

The methods used in comparison. To estimate the effectiveness of DWFS and quantify the contribution of the filtering (pre-processing) step, we select features using wrapper FS only (denoted as DWFS), wrapper FS combined with mRMR (denoted as mRMR+DWFS) and wrapper FS combined with JMI (denoted as JMI+DWFS). To provide better cross-benchmarking results, we compare the classification performance of DWFS and its variants with the most effective wrappers and the filtering approaches presented in Table 1. Specifically, we include in the comparison WEKA (version 3.6.6) wrapper that uses an integrated method of forward and backward search (Bi-directional BestFirst), FST3 that implements a powerful wrapper-based method called sequential forward floating search (SFFS), as well as mRMR and JMI filters. In our comparison analysis, we view WEKA and FST3 wrappers as representative implementations for other tools that use similar sophisticated approaches for FS. Moreover, mRMR and JMI filters are also considered representatives of a wider class of advanced filtering approaches. In particular, JMI stands as a representative for single-objective filtering methods that examine joint relevance between features with the target variable, while mRMR represent methods that consider multi-objective formulation for filtering features with high relevance to the target and minimum redundancy between each other. In other words, comparison with WEKA and FST3 wrappers and mRMR and JMI filters, is expected to reveal how our approach may compare to other filters or wrappers. We used two baselines, one where the classification performance is obtained utilizing all features (the initial/original feature vector), and the other that uses top 10% of features with the highest class correlation (we call it Correlation-baseline). We did not include in the comparison the dataset-specific FS tools such as Arraymining, Multi-Relief and MetaboloAnalyst, or tools that at the time of this study were not fully functional (e.g. that crushed during experiments).

Performance assessment. Classification performance is assessed using nested 5-fold cross-validation. This technique splits data to five folds and for every fold FS is applied. To evaluate the performance of the model inside a single fold we split again this particular fold to five folds, assign the performances and average the classification performance of the folds. Such cross-validation setup has been proposed in [29] for avoiding potential over-fitting effects. Given the large size of our experimental datasets, 5-fold setup seems to be a proper choice for computing a representative (i.e. not biased) estimate while being computationally faster compared to a setup with a larger number of folds [30,31].

Classification performance is measured using five classification performance metrics, namely: Sensitivity that measures the true positive rate; Specificity that measures true negative rate; GMean that measures the combined effect of Sensitivity and Specificity; Positive Predictive Value (PPV) that measures proportion of correctly predicted positives out of all predicted positives; and F1-measure that estimates the combined effect of PPV and Sensitivity. These performance metrics are frequently used performance indicators for classification systems [23,32]. Let TP be the number of true positives, FP the number of false positives, TN the number of true negatives and FN the number of false negatives, Equations 3 to 7 show formulae of these performance metrics: (3) (4) (5) (6) (7)

In addition to classification performance indicators, we also include a measure of robustness called stability [33]. The stability S(θi, θj) between two selected feature subsets θi, θj over two different folds of the data is defined by Equation (8). The sizes of these two feature subsets are represented by ki, kj, respectively. The size of common features (i.e. the number of elements in the intersection between the two sets) is c: (8)

We compute the pair-wise scores in Equation (8) for different folds (i.e. 5 folds in our setup) and report their average. The stability measure in Equation (8) has a range of (−1,1] were a value of 0 indicates an output from a random FS. A positive range states that the FS method is more stable than a random one and a negative value indicate the opposite [33].

Comparison analysis

Classification performance and ranking. We do not know in advance the specifics of the classifier implementation that the different tools have. For this reason, we select features with each of the wrapper-based tools included in the comparison, using their in-house implementations. However, we evaluate all programs using the same MATLAB R2012b implementations as these were not part of any of the wrapper-based FS tools used in the comparison analysis. This ensures fairness in the comparison. Finally, for JMI, mRMR and Correlation-baseline, we select the 10% of the top-ranked features.

Tables 320 present the actual average and standard deviation of classification performance for all studied methods using NBC and KNN classifiers. We observe that, using different performance indicators the studied programs show different advantages and disadvantages and perform differently on different datasets. In terms of GMean, DWFS is comparable in many cases to the other methods. For the KNN classifier, in 6 out of 9 datasets, DWFS hybrid with a filtering method enhanced the filtering performance. This, nevertheless, is not the case for the NBC classifier where such enhancement happens in 4 out of 9 datasets. In 3 out of 18 cases (9 datasets with 2 classifiers), WEKA achieved the best results with the NBC and KNN classifiers. The same was also the case for FST3. Interestingly, the Correlation-baseline achieved the best result for the Microarray dataset with the KNN classifier (Table 16). These experimental results suggest that DWFS or one of its variants are better suited for datasets with large number of samples (>200).

thumbnail
Table 3. Actual classification performance for WDBC dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t003

thumbnail
Table 4. Actual classification performance for Promoter dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t004

thumbnail
Table 5. Actual classification performance for miRNA dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t005

thumbnail
Table 6. Actual classification performance for Prostate cancer dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t006

thumbnail
Table 7. Actual classification performance for Leukemia dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t007

thumbnail
Table 8. Actual classification performance for Lung cancer dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t008

thumbnail
Table 9. Actual classification performance for TFTF dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t009

thumbnail
Table 10. Actual classification performance for TIS dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t010

thumbnail
Table 11. Actual classification performance for Medelon dataset using KNN classifier.

https://doi.org/10.1371/journal.pone.0117988.t011

thumbnail
Table 12. Actual classification performance for WDBC dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t012

thumbnail
Table 13. Actual classification performance for Promoters dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t013

thumbnail
Table 14. Actual classification performance for miRNA dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t014

thumbnail
Table 15. Actual classification performance for Prostate cancer dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t015

thumbnail
Table 16. Actual classification performance for Leukemia dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t016

thumbnail
Table 17. Actual classification performance for Lung cancer dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t017

thumbnail
Table 18. Actual classification performance for TFTF dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t018

thumbnail
Table 19. Actual classification performance for TIS dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t019

thumbnail
Table 20. Actual classification performance for Medelon dataset using NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.t020

To draw conclusions about their relative performance, we rank the FS methods following the method presented in [34] as follows: for every dataset and for every performance indicator, the FS method that achieves the best result is ranked first and obtains 1 point, the second best obtains 2 points and so on, up to 9 points. The overall ranking for each FS method is reflected in the sum of obtained points across all datasets and all performance metrics using KNN and NBC, which we call the final ranking score. At the end, the FS method with the smallest sum of ranking scores is ranked at position 1 and so on. One can also divide the final ranking score with the total number of tests and obtain the average rank position. This however does not change the final ranking order. The ranking that we present and conclusions that we derive from it are relative: they are based on the collection of methods that are compared, the collection of criteria used, and the collection of datasets used. Based on our experiments, we observe that the simple DWFS wrapper FS has the best (smallest) average rank across all tests. Yet, for a specific performance metric or a particular dataset, this need not be the case. WEKA is ranked second followed by JMI combined with DWFS. Table 21 presents these ranked positions. Note that in the ranking process all the tested cases equally contribute to the ranking score.

thumbnail
Table 21. Sum of ranking points for every method, for every performance metric across all datasets and different classification techniques.

https://doi.org/10.1371/journal.pone.0117988.t021

Effectiveness of selected features and feature subset size reduction. Next, to provide more insights about the performance of the studied methods we compute the ratio of classification performance over the number of selected features. This ratio measures the effectiveness of the FS process and depicts the maximum classification performance that can be achieved using the reduced number of features selected by an FS method. As performance indicator, we choose GMean since it combines two other important performance metrics (note that other selections were also possible). The results for the NBC and KNN classifiers are presented in Fig. 4. DWFS and its variants achieve the best results in 10 out of 18 tested cases. For the remaining 8 cases (Lung cancer, Leukemia, Prostate cancer and TFTF datasets) WEKA is the best method for both the NBC and KNN classifiers.

thumbnail
Fig 4. Performance indicator values divided by the absolute number of selected features for all the studied methods and across all the studied datasets.

As a performance indicator we use Geometric Mean of Specificity and Sensitivity (GMean). A) Results for NBC classifier. B) Results for KNN

https://doi.org/10.1371/journal.pone.0117988.g004

In order to quantify the reduction of the number of features we compute the percentage of the extracted features over all features. Tables 22 and 23 present results for the NBC-based wrapper FS and KNN-based wrapper FS, respectively. We observe that DWFS combined with JMI and mRMR leads to the largest feature set size reduction. On average and across all studied datasets, the percentage of the finally selected features for the NBC classifier for DWFS+mRMR and DWFS+JMI is 2.21% and 1.94% of all features, respectively. Regarding the KNN classifier, the percentage of the selected features for DWFS+mRMR and DWFS+JMI, is 2.40% and 2.31% of all features, respectively.

thumbnail
Table 22. Feature subset reduction over the original feature set size using NBC-based wrapper FS.

https://doi.org/10.1371/journal.pone.0117988.t022

thumbnail
Table 23. Feature subset reduction over the original feature set size using KNN-based wrapper FS.

https://doi.org/10.1371/journal.pone.0117988.t023

Run time. In Table 24 and Table 25 we report the run time required for selecting features and evaluating classification performance. From this comparison we exclude mRMR and JMI since they are filtering methods and their run time is much shorter than for any of the wrapper models. We observe that on average and across different datasets, DWFS is the slowest. However, the combination of DWFS wrapper with mRMR reduces significantly the run time and achieves the fastest wrapper setting compared to WEKA and FST3.

thumbnail
Table 24. Actual average execution time in seconds for NBC-based wrapper FS and NBC classification.

https://doi.org/10.1371/journal.pone.0117988.t024

thumbnail
Table 25. Actual average execution time in seconds for KNN-based wrapper FS and KNN classification.

https://doi.org/10.1371/journal.pone.0117988.t025

Stability results. Stability quantifies the degree of presence of selected features over different splits of the training data. Features that appear more frequently in selected subsets may represent more significant ones for the class prediction, but this factor is not explicitly correlated to classification performance. Note, that most stability metrics are defined for feature subsets of equal size. However, this is not the case for wrappers, where the final selected subsets have different size for every split of data. In our case, we use a definition proposed by Lustgarten et al. [33] (see Equation (8)), which meets our need for measuring stability between feature subsets of different sizes. It should be noted that higher stability may not necessarily reflect a better classification performance. Fig. 5 depicts the results of the comparison analysis using the NBC classifier for all the methods used and across all studied datasets. We observe that filtering approaches are more stable than wrapper-based ones in FS. WEKA with forward and backward search achieves more stable results than the other wrappers. For specific datasets (i.e. WDBC, TIS and Pre-miRNAs), DWFS combined with any of the filters achieves the most stable results.

thumbnail
Fig 5. Stability of different FS methods across all datasets using the NBC classifier.

https://doi.org/10.1371/journal.pone.0117988.g005

Conclusion

In this study we present DWFS, a web-based FS tool based on the wrapper model combined with a randomized search strategy. DWFS offers a variety of options to enhance the optimized FS including incorporation of filtering methods as pre-processing step and many other options for tailoring the objective function according to application requirements. From our extensive experimentation with several benchmark datasets from different biological and biomedical problems we observe that, DWFS integrated in a hybrid setup with a filtering approach for FS is capable of reducing significantly the number of features without sacrificing classification performance. Moreover, using different performance indicators we show that DWFS performs well relative to the existing FS methods. We hope that DWFS will find good use in the analysis of many complex biological and biomedical data complementing other available tools for FS that biologists may use.

Supporting Information

S1 Table. Effects of changing crossover rate on stability of NBC and reduction in the size of selected features.

https://doi.org/10.1371/journal.pone.0117988.s001

(XLS)

S2 Table. Effect of changing mutation rate on stability of NBC and reduction in the size of selected features.

https://doi.org/10.1371/journal.pone.0117988.s002

(XLS)

Author Contributions

Conceived and designed the experiments: OS DK PK VBB. Performed the experiments: OS. Analyzed the data: DK OS VBB. Contributed reagents/materials/analysis tools: OS DK. Wrote the paper: OS DK PK VBB.

References

  1. 1. Guyon I, Elisseeff A (2003) An introduction to variable and feature selection. The Journal of Machine Learning Research 3: 1157–1182.
  2. 2. Garbarine E, DePasquale J, Gadia V, Polikar R, Rosen G (2011) Information-theoretic approaches to SVM feature selection for metagenome read classification. Computational biology and chemistry 35: 199–209. pmid:21704267
  3. 3. Liu H, Yu L (2005) Toward integrating feature selection algorithms for classification and clustering. Knowledge and Data Engineering, IEEE Transactions on 17: 491–502.
  4. 4. Saeys Y, Inza I, Larrañaga P (2007) A review of feature selection techniques in bioinformatics. bioinformatics 23: 2507–2517. pmid:17720704
  5. 5. Kohavi R, John GH (1997) Wrappers for feature subset selection. Artificial intelligence 97: 273–324.
  6. 6. Holland JH (1975) Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press. pmid:25077283
  7. 7. Wang H, Lo S-H, Zheng T, Hu I (2012) Interaction-based feature selection and classification for high-dimensional biological data. bioinformatics 28: 2834–2842. pmid:22945786
  8. 8. Somol P, Grim J, Pudil P (2010) The problem of fragile feature subset preference in feature selection methods and a proposal of algorithmic workaround. IEEE. pp. 4396–4399. https://doi.org/10.1016/j.febslet.2010.10.013 pmid:20951136
  9. 9. Rokach L (2008) Data mining with decision trees: theory and applications: World scientific. pmid:25506952
  10. 10. Duval B, Hao J-K (2010) Advances in metaheuristics for gene selection and classification of microarray data. Briefings in Bioinformatics 11: 127–141. pmid:19789265
  11. 11. Hilario M, Kalousis A (2008) Approaches to dimensionality reduction in proteomic biomarker studies. Briefings in Bioinformatics 9: 102–118. pmid:18310106
  12. 12. Somol P, Vácha P, Mikeš S, Hora J, Pudil P, et al. (2010) Introduction to Feature Selection Toolbox 3–The C++ Library for Subset Search, Data Modeling and Classification. Research Report for Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic.
  13. 13. Hall M, Frank E, Holmes G, Pfahringer B, Reutemann P, et al. (2009) The WEKA data mining software: an update. ACM SIGKDD explorations newsletter 11: 10–18.
  14. 14. Peng H, Long F, Ding C (2005) Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy. Pattern Analysis and Machine Intelligence, IEEE Transactions on 27: 1226–1238.
  15. 15. Cheng T, Wang Y, Bryant SH (2012) FSelector: a Ruby gem for feature selection. bioinformatics 28: 2851–2852. pmid:22942017
  16. 16. Seo M, Oh S (2012) CBFS: High performance feature selection algorithm based on feature clearness. PloS one 7: e40419. pmid:22792310
  17. 17. Glaab E, Garibaldi JM, Krasnogor N (2009) ArrayMining: a modular web-application for microarray analysis combining ensemble and consensus methods with cross-study normalization. BMC bioinformatics 10: 358. pmid:19863798
  18. 18. Ye K, Feenstra KA, Heringa J, IJzerman AP, Marchiori E (2008) Multi-RELIEF: a method to recognize specificity determining residues from multiple sequence alignments using a Machine-Learning approach for feature weighting. bioinformatics 24: 18–25. pmid:18024975
  19. 19. Xia J, Psychogios N, Young N, Wishart DS (2009) MetaboAnalyst: a web server for metabolomic data analysis and interpretation. Nucleic acids research 37: W652–W660. pmid:19429898
  20. 20. Levine D (1996) Users guide to the PGAPack parallel genetic algorithm library. Argonne National Laboratory 9700. pmid:8703941
  21. 21. Cantú-Paz E (1998) A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis 10: 141–171.
  22. 22. Siedlecki W, Sklansky J (1989) A note on genetic algorithms for large-scale feature selection. Pattern recognition letters 10: 335–347.
  23. 23. Akbani R, Kwek S, Japkowicz N (2004) Applying support vector machines to imbalanced datasets. Machine Learning: ECML 2004: Springer. pp. 39–50.
  24. 24. Bochkanov S (2010) ALGLIB software library, L-BFGS C++ implementation.
  25. 25. Yang HH, Moody JE (1999) Data Visualization and Feature Selection: New Algorithms for Nongaussian Data. Citeseer. pp. 687–702. https://doi.org/10.1094/PHYTO.1999.89.8.687 pmid:18944682
  26. 26. Fleuret F (2004) Fast binary feature selection with conditional mutual information. The Journal of Machine Learning Research 5: 1531–1555.
  27. 27. Jakulin A (2005) Machine learning based on attribute interactions: Univerza v Ljubljani. pmid:25275211
  28. 28. Brown G, Pocock A, Zhao M-J, Luján M (2012) Conditional likelihood maximisation: a unifying framework for information theoretic feature selection. The Journal of Machine Learning Research 13: 27–66.
  29. 29. Cawley GC, Talbot NL (2010) On over-fitting in model selection and subsequent selection bias in performance evaluation. The Journal of Machine Learning Research 11: 2079–2107.
  30. 30. Braga-Neto UM, Dougherty ER (2004) Is cross-validation valid for small-sample microarray classification? bioinformatics 20: 374–380. pmid:14960464
  31. 31. Kohavi R (1995) A study of cross-validation and bootstrap for accuracy estimation and model selection. pp. 1137–1145.
  32. 32. Schmeier S, Jankovic B, Bajic VB (2011) Simplified method to predict mutual interactions of human transcription factors based on their primary structure. PloS one 6: e21887. pmid:21750739
  33. 33. Lustgarten JL, Gopalakrishnan V, Visweswaran S (2009) Measuring stability of feature selection in biomedical datasets American Medical Informatics Association. pp. 406. https://doi.org/10.1111/j.1551-6709.2009.01079.x pmid:21564219
  34. 34. Bajić VB (2000) Comparing the success of different prediction software in sequence analysis: a review. Briefings in Bioinformatics 1: 214–228. pmid:11465033
  35. 35. Zare H (2011) FeaLect: Feature seLection by computing statistical scores.
  36. 36. Magana-Mora A, Ashoor H, Jankovic BR, Kamau A, Awara K, et al. (2013) Dragon TIS Spotter: an Arabidopsis-derived predictor of translation initiation sites in plants. bioinformatics 29: 117–118. pmid:23110968
  37. 37. Blake C, Merz CJ (1998) {UCI} Repository of machine learning databases.
  38. 38. Batuwita R, Palade V (2009) microPred: effective classification of pre-miRNAs for human miRNA gene prediction. bioinformatics 25: 989–995. pmid:19233894
  39. 39. Spira A, Beane JE, Shah V, Steiling K, Liu G, et al. (2007) Airway epithelial gene expression in the diagnostic evaluation of smokers with suspect lung cancer. Nature medicine 13: 361–366. pmid:17334370
  40. 40. Golub TR, Slonim DK, Tamayo P, Huard C, Gaasenbeek M, et al. (1999) Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. science 286: 531–537. pmid:10521349
  41. 41. Singh D, Febbo PG, Ross K, Jackson DG, Manola J, et al. (2002) Gene expression correlates of clinical prostate cancer behavior. Cancer cell 1: 203–209. pmid:12086878