Feature selection algorithms: a survey and experimental evaluation
Abstract
In view of the substantial number of existing feature selection algorithms, the need arises to count on criteria that enables to adequately decide which algorithm to use in certain situations. This work reviews several fundamental algorithms found in the literature and assesses their performance in a controlled scenario. A scoring measure ranks the algorithms by taking into account the amount of relevance, irrelevance and redundance on sample data sets. This measure computes the degree of matching between the output given by the algorithm and the known optimal solution. Sample size effects are also studied.
Full text
Feature Selection Algorithms: A Survey and Experimental Evaluation Luis Carlos Molina, Lluís Belanche, Àngela Nebot Universitat Politècnica de Catalunya Departament de Llenguatges i Sistemes Informátics Jordi Girona 1-3, Campus Nord C6, 08034, Barcelona, Spain. {lcmolina,belanche,angela}@lsi.upc.es Abstract In view of the substantial number of existing feature selection algorithms, the need arises to count on criteria that enables to adequately decide which algorithm to use in certain situations. This work reviews several fundamental algorithms found in the literature and assesses their performance in a controlled scenario. A scoring measure ranks the algorithms by taking into account the amount of relevance, irrelevance and redundance on sample data sets. This measure computes the degree of matching between the output given by the algorithm and the known optimal solution. Sample size effects are also studied. 1. Introduction The feature selection problem in terms of supervised inductive learning is: given a set of candidate features select a subset defined by one of three approaches: a) the subset with a specified size that optimizes an evaluation measure, b) the subset of smaller size that satisfies a certain restriction on the evaluation measure and c) the subset with the best commitment among its size and the value of its evaluation measure (general case). The generic purpose pursued is the improvement of the inductive learner, either in terms of learning speed, generalization capacity or simplicity of the representation. It is then possible to understand better the results obtained by the inducer, diminish its volume of storage, reduce the noise generated by irrelevant or redundant features and eliminate useless knowledge. A feature selection algorithm (FSA) is a computational solution that is motivated by a certain definition of relevance. However, the relevance of a feature –as seen from the inductive learning perspective– may have several definitions depending on the objective that is looked for. An irrelevant feature is not useful for induction, but not all relevant features are necessarily useful for induction [14]. The FSAs can be classified according to the kind of output they yield: (1) those algorithms giving a (weighed) linearorderoffeaturesand(2)thosealgorithmsgivinga subset of the original features. Both types can be seen in an unified way by noting that in (2) the weighting is binary. The work presented in this paper is centered in FSAs tackling the feature selection problem of type (2), studied for many years by the statistical [18] as well as the machine learning [38] communities. Research developed within the machine learning area is usually focused on the proposal of new algorithms, theoretical learning results of existing algorithms or empirical studies (evaluations or applications). In this research, several fundamental algorithms found in the literature are studied to assess their performance in a controlled scenario. To this end, a measure to evaluate FSAs is proposed that takes into account the particularities of relevance, irrelevance and redundance on the sample data set. This measure computes the degree of matching between the output given by a FSA and the known optimal solution. Sample size effects are also studied. The results illustrate the strong dependenceon the particular conditions of the FSA used and on the amount of irrelevance and redundance in the data set description, relative to the total number of features. This should prevent the use of a single algorithm even when there is poor knowledge available about the structure of the solution. The paper is organizedas follows: in section 2 we review some different approaches to provide with a formal definition of relevance. In section 3 we set a more precise definition of the feature selection problem and survey the main characteristics of a FSA in an unified framework. Next, we describe some of the most widespread FSA in machine learning in terms of this framework. The methodology and tools used for the empirical evaluation are covered in section 5. Finally the experimental studyis describedin section 6 as well as the results. The paper ends with the conclusions and the knowledge gained. 1
2 Relevance of a Feature The purpose of a FSA is to identify relevant features according to a definition of relevance. However, the notion of relevance in machine learning has not yet been rigorously defined on a common agreement [6]. Let , with , be domains of features ; an instancespaceis defined as , whereaninstance is a point in this space. Consider a probability distributionon and ! a space of labels (e.g. classes). It is desired to model or identify an objective function "$# &% ! according to its relevant features. A data set ' composed by ( ' ( instances can be seen as the result of sampling under a total of ( ' ( times and labelling its elements using " . A primary definition of relevance [9] is the notion of being “relevant with respect to an objective”. It is assumed here to be a classification objective. Definition 1 (Relevance with respect to an objective) A feature *) is relevant to an objective " if there exist two examples + , , in the instance space such that + and , differ only in their assignment to and ".-/+10324"5-,60 . In other words, if there exist two instances that can only be classified thanks to . This definition has the inconvenience that the learning algorithm can not necessarily determine if a feature is relevant or not, using only a sample ' of . Moreover, if the problem representation is redundant (e.g., some features are replicated), it will never be the case that two instances differ only in one feature. A proposal oriented to solve this problem [24] includes two notions of relevance, one with respect to a sample and another with respect to the distribution. Definition 2 (Strong relevance with respect to S)A feature *) is strongly relevant to the sample ' if there exist two examples +$7, ) ' that only differ in their assignment to and "5-+1012"5-/,0 . That is to say, it is the same Definition 1, but now +87, ) ' and the definition is with respect to ' . Definition 3 (Strong relevance with respect to p)A feature 9) is strongly relevant to an objective " in the distribution if there exist two examples +87, ): with ;-/+<0124= and >-/,6032?= that only differ in their assignment to and "5-/+<0<2"5-/,0 . This definition is the natural extension of Definition 2 and, contrary to it, the distribution is assumed to be known. Definition 4 (Weak relevance with respect to S)A feature ) is weakly relevant to the sample ' if there exists at least a proper A@BC ( 9) D@ ) where is strongly relevant with respect to ' . A weakly relevant feature can appear when a subset containing at least one strongly relevant feature is removed. Definition 5 (Weak relevance with respect to p)A feature ) is weakly relevant to the objective " in the distribution if there exists at least a proper A@EBF ( ) A@ ) where is strongly relevant with respect to . These definitions are important to decide what features should be conserved and which can be eliminated. The strongly relevant features are, in theory, important to maintain a structure in the domain, and they should be conserved by any feature selection algorithm in order to avoid the addition of ambiguity to the sample. Weakly relevant features could be important or not depending on the other features alreadyselectedandon the evaluationmeasurethathas been chosen (accuracy, simplicity, consistency, etc.). From another point of view, instead of focusing in which features are relevant, it is possible to use relevance as a "complexity measure" with respect to the objective " . In this case, it will depend on the chosen inducer. Definition 6 (Relevance as a complexity measure) [9] Given a data sample ' and an objective " , define GH-'IJ"0 as the smallest number of relevant features to " using Definition 1 only in ' , and such that the error in ' is the least possible for the inducer. In other words, it refers to the smallest number of features required by a specific inducer to reach optimum performance in the task of modelling " using ' . Definition 7 (Incremental usefulness) [13] Given a data sample ' , a learning algorithm K , and a subset of features A@ , the feature is incrementally useful to K with respect to A@ if the accuracy of the hypothesis that K produces using the group of features MLN @ is better than the accuracy reached using only the subset of features A@ . This definition is specially natural in FSAs that search in the feature subset space in an incremental way, adding or removing features to a current solution. It is also related to a traditional understanding of relevance in the philosophy literature [21]. Definition 8 (Entropic relevance) [55] Denoting the (Shannon) entropy by OP-/0 and the mutual information by Q -/ER7SH0TOP-U0WVXOY-U ( S0 (the difference of entropy in generated by the knowledge of S ), the entropic relevance of to S is defined as GZ-/ER7SH0M Q -U;RS07[5OP-US0 . Let be the original set of features and let \ be the objective seen as a feature, a set D@]B^ is sufficient if Q -/A@/R_\`0a Q -U]_\`0 (i.e., if it preserves the learning information). For a sufficient set A@ , it turns out that 2
GZ-/A@RJ\`0bcGH-U]_\`0 . The most favorable set is that sufficient set D@dB for which OP-/A@e0 is smaller. This implies that GH-\R7A@f0 is greater. In short, the aim is to have GZ-g\RA@e0 and GH-UA@RJ\`0 jointly maximized. To make these definitions more clear, we borrow [9] an example that considers concepts expressible as disjunctions of features (e.g., Mh ji hjk ), assuming that the learning algorithm has access to the following 5 examples: 100000000000000000000000000000 + 111111111100000000000000000000 + 000000000011111111110000000000 + 000000000000000000001111111111 + 000000000000000000000000000000 - The relevant features using Definition 1 depend on the actual (unknown) objective, although any consistent disjunction must include the first feature. Using Definitions 2, 3, 4 and 5 it can be concluded that (both with regard to ' and to ) is strongly relevant and the rest of features are weakly relevant. Using Definition 6 it is simply stated that there are three relevant features -/GH-'IJ"0lmn0 , because this is the minimum number of features leading to a consistent disjunction. Notice that the features are not specified (e.g., Ih 7oh p ). Definition 7 depends on the inducer. As an example, given A@qr 7jp. , a set of already selected features, none of jis ut would be incrementally useful, and any of 7>7 it would. Definition 8 requires the computationof the correspondingmutual entropies. Notice this is the only definition that considers relevance in a quantitative way. 3 Algorithms for Feature Selection A FSA should be seen as a computational approach to a definition of relevance, although in many cases the previous definitions are followed in a somewhat loose sense. 3.1 Feature Selection Definition Let be the original set of features, with cardinality ( ( . The continuous feature selection problem refers to the assignment of weights v to each feature ) in such a way that the order corresponding to its theoretical relevance is preserved. The binary feature selection problem refers to the assignment of binary weights. This can be carried out directly (like many FSAs in machine learning [2, 13, 22]), or filtering the output of the continuous problem solution (see §6.2). These are quite different problems reflecting different design objectives. In the continuous case, one is interested in keeping all the features but in using them differentially in the learning process. On the contrary, in the binary case one is interested in keeping just a subset of the features and using them equally in the learning process. The feature selection problem can be seen as a search in a hypothesis space (set of possible solutions). In the case of the binary problem, the number of potential subsets to evaluate is w . In this case, a general definition is [29]: Definition 9 (Feature Selection) Let xo-UA@e0 be an evaluation measure to be optimized (say to maximize) defined as xy#nA@Ez{ %}| . The selection of a feature subset can be seen under three considerations: ~ Set ( D@ ( . Find A@;B4 , such that xs-/A@e0 is maximum. ~ Set a value xZ , this is, the minimum x that is going to be tolerated. Find the A@z{ with smaller ( A@ ( , such that xo-UA@e0xn . ~ Find a compromise among minimizing ( A@ ( and maximizing xo-/A@0 (general case). Notice that, with these definitions, an optimal subset of features is not necessarily unique. 3.2 Characterization of FSAs There exist in the literature several considerations to characterize feature selection algorithms [9, 19, 32]. In view of them it is possible to describe this characterization as a search problem in the hypothesis space as follows: Search Organization. General strategy with which the space of hypothesis is explored. This strategy is in relation to the portion of hypothesis explored with respect to their total number. Generation of Successors. Mechanism by which possible variants (successor candidates) of the current hypothesis are proposed. Evaluation Measure. Function by which successor candidates are evaluated, allowing to compare different hypothesis to guide the search process. 3.2.1 Search Organization A search algorithm is responsible for driving the feature selection process using a specific strategy. Each state in the search space specifies a weighting vv of the possible features of , with ( ( . In the binary case, v ) = , whereas in the continuous case v ) = . Notice we are stating that relevance should be upper and lower bounded. Also in the binary case a partial order exists in the search space, with 'E' p if ';B' p (see 3
Fig. 1), whereas in the continuous case 'E' p if, for all , v -';0 v -' p0 holds (see Fig. 2). In general, a search procedure examines only a part of the search space. When a specific state has to be visited, the algorithm uses the information of the previously visited states and eventually heuristic knowledge about non-visited ones. Being a (labeled) list of weighed subsets of features (i.e. states), maintains the (ordered) current list of solutions. The labels indicate the value of the evaluation measure. We consider three types of search: exponential, sequential and random. Most sequential algorithms are characterized by ( ( , whereas exponential and random ones typically use ( ( . Figure 1. States in the binary search space involving 4 features. A black square represents the inclusion of a feature in the state and a white square represents its exclusion. Figure 2. A path of states in the continuous search space involving 4 features. Relevances are represented as a degree of filling. Exponential Search: It corresponds to algorithms that carry out searches whose cost is -w 0 . The exhaustive search is an optimal search, in the sense that the best solution is guaranteed. An optimal search need not be exhaustive; for example, if an evaluation measure is monotonic a BRANCH AND BOUND [42] algorithm is optimal. A measure x is monotonic if for any two subsets 'J'p and 'z?'p , then xo-g' 0lxo-'p0 . Another example would be an +3 search with an admissible heuristic [44]. Sequential Search: This sort of search selects one among all the successors to the current state. This is done in an iterative manner and once the state is selected it is not possible to go back. Although there is no explicit backtracking the number of such steps must be limited by - 0 in order to qualify as a sequential search. The complexity is determined taking into account the number of evaluated subsets in each state change. The cost of this search is therefore polynomial - E 0 . Consequently, these methods do not guaranteean optimalresult, since theoptimal solutioncould be in a region of the search space that is not visited. Random Search: The idea underlying this type of search is to use its randomness to avoid the algorithm to stay on a local minimum and to allow temporarily moving to other states with worse solutions. These are anytime algorithms [32] and can give several optimal subsets as solution. 3.2.2 Generation of Successors Up to five different operators can be considered to generate a successor for each state: Forward, Backward, Compound, Weighting, and Random. All of the operators act by modifying in some way the weights v of the features , with v )| (in the case of the weighting operator), or v ) = (in the case of the rest of operators). In the following descriptions, it is assumed that the evaluation measure x is to be maximized. Forward: This operator adds features to the current solution D@ , among those that have not been selected yet. In each step, the feature that makes x be greater is added to the solution. Starting with A@M , the forward step consists of: @ #? @ L] I) M @ ( xs-/ @ LA 0 is bigger (1) The stopping criterion can be: ( A@ ( @ (if @ has been fixed in advance), the value of x has not increased in the last steps, or it surpasses a prefixed value xt . The cost of the operator is - 0 . The main disadvantage is that it is not possible to have in consideration certain basic interactions among features. For example, if 7jp are such that xo-u 7jp.0o¡xo-u 0xo-up50 , neither and jp could be selected, in spite of being very useful. Backward: This operator removes features from the current solution A@ , among those that have not been removed yet. In each step, the feature that makes x be greater is removed from the solution. Starting with D@ , the backward step consists of: @ #¢4 @ d s) @ ( xo-U @ d 0 is bigger (2) The stopping criterion can be: ( D@ ( @ , the value of x has not increased in the last steps, or it falls below a prefixed value xt . This operator remedies some problems although there still will be many hidden interactions (in the sense of being unobtainable). The cost is - 0 , although in practice it demands more computation than its forward counterpart [27]. 4
Both operators (forward and backward) can be generalized selecting, at each step, subsets of elements A@ @ and selecting the one making xo-UD@gLA@ @f0 or xo-UA@uZA@ @0 bigger, respectively. The cost of the operator is then - 0 . Compound: The idea of this tactic is simple: apply £ consecutive forward steps and ¤ consecutive backward ones. If £¦¥T¤ the net result is a forward operator, otherwise it is a backward one. An interesting approach is to perform the forward or the backward steps, depending on the respective values of x . This allows to discover new interactions among features. An interesting “backtracking mechanism” is obtained, although other stopping conditions should be established if £a&¤ . For example, for £a&¤$ , if is added and H§ is removed, this could be undone in the following steps. A possible stopping criterion is ¨ § . In sequential FSA, the condition £P24¤ assures a maximum of steps, with a total cost - E©Eªg 0 . Weighting: In the weighting operators, the search space is continuous, and all of the features are present in the solution to a certain degree. A successor state is a state with a different weighting. This is typically done by iteratively sampling the available set of instances. Random: This group includes those operators that can potentially generate any other state in a single step. The rest of operators can also have random components, but they are restricted to some criterion of "advance" in the number of features or in improving the measure x at each step. 3.2.3 Evaluation Measures There are several approaches to evaluate the goodness xs-/A@«0 of a feature subset A@ . It is clear to observe that the relevance of a feature is solely a function of this measure and not a characteristic of the feature itself. Another important considerationis the factthat the range and scale of x are immaterial. What counts is that the relative values assigned to different subsets reflect their greater or lesser relevance to the objective function. Among the reviewed measures the probabilistic and the interclass distances, together with consistency, are measures of class separability. Further, the interclass distance, consistency, entropy and estimations of the probability of error may not require the explicit modeling of probability distributions. Let x#D@lz¨ %¬| be an evaluation measure to be maximized, where D@ is a (weighed) feature subset. Probability of error: Provided the ultimate goal is to build a classifier able of correctly labelling instancesgenerated by the same probability distribution, minimizing the (bayesian) probability of error I® of the classifier seems to be the most natural choice. Therefore, it is also a clear choice for x . Let ¯ )°| represent the unlabeled instances, and ±¦ ²s³²I´$ a set of labels (classes), so that "<# | % ± . Such probability is defined as [18]: ® µ Vy¶·5¸ *-U² ( ¯0 ;-¯0³¹¯ (3) where >-¯0º ´ «» ;-¯ ( ² 0³*-f² 0 is the (unconditional) probability distribution of the instances, and *-f² ( ¯0 is the a posteriori probability of ² being the class of ¯ . Since the class-conditional densities are usually unknown, they can either be explicitly modeled (using parametric or non-parametric methods) or implicitly via the design of a classifier that builds the respectivedecision boundaries between the classes [18]. Some of these classifiers, like the one-nearest-neighbor rule, have a direct relation to the probability of error. The use of (an estimate ¼I® of) this probability by means of the construction of a classifier, using a sample dataset, is the base of the wrapper methods [26]. Provided the classifier has been built using only a subset A@*B of the features, we have: ¼ ® V ( ' ½j¾ ( ( ' ½j¾ ( (4) so that x] V¿¼ ® , being ' ½j¾ a test data sample, and ' ½j¾ the subset of ' ½¾ where the classifier performed correctly (again using only a partial description A@ ). The estimation ¼ ® may require the use of more elaborate methods than a simple holdout procedure (cross validation, bootstrapping) in order to yield a more reliable value. Divergence: These measures compute a probabilistic distance or divergence among the class-conditional probability densities ;-¯ ( ² 0 , using the general formula: x µ £ ;-¯ ( ²s0/ >-¯ ( ²p0 ¹>¯ (5) To qualify as a valid measure, the function £ must be such that the value of x satisfies the following conditions: (a) xDF= , (b) xA?= only when the >-¯ ( ² 0 are equal and (c) x is maximum when they are non-overlapping. If the features used in a solution @B¨ are good ones, the divergence among the conditionalprobabilitieswill be significant. Poor features will result in very similar probabilities. Some classical choices are [18]: Chernoff £I-Àj_¤0o?ÀHÁ¤ _ Ájà )° =Ä and then xÆÅ>Ç ®:VÈÉ3x (6) Bhattacharyya £I-/ÀJ¤0IÊ ÀH¤ and then xÆËIÇÌ3¦V9ÈÉ3x (7) Kullback-Liebler £I-/ÀJ¤0o:-/À6V°¤0-UÈÉÀ$VyÈÉd¤0 and then xÆÍlÎx (8) 5
Kolmogorov £I-Àj_¤0s ( À$Va¤ ( and then xÍÏ x (9) Matusita £I-ÀJ¤0sÐÊ À8VPÊ ¤0 p and then xnÑ Ì_Ò Êx (10) Patrick-Fisher £I-/ÀJ¤0o-/À6Va¤0 p and then xÆÓÔPÊ x (11) These measures satisfy the previous conditions and can be used in a weighed form, taking into account the prior class probabilities *-U² 0 so that £ ;-¯ ( ²o0/ ;-¯ ( ²p0 becomes £ ;-¯ ( ²o0*-f²s0 ;-¯ ( ²p0*-f² p0 . They can also be related to ® in the form of upper-bounds [18, 7]. Dependence: These measures quantify how strongly two features are associated with one another, in the sense that knowing the value of one it is possible to predict the value of the other. In the context of feature selection, a feature is better evaluated the better it predicts the class. The correlation coefficientis a classical measure that still finds application [22]. A somewhat different approach is to estimate the divergence between the class-conditional and the unconditional densities. Any unweighedprobabilistic distance measure serves this purpose. Specifically, we have measures of the form £ ;-¯ ( ² 0/ >-¯0 JwH Interclass distance: These measures are based on the assumption that instances of a different class are distant in the instance space. It is enough then to define a metric between classes and use it as measure: Õ -U² ³²§0o ÖÖ §Y×>Ø Ù Ú ×;Û Ù _Ü » Ú ¹j-/Ý /Þ Ú³ß Ý § Þ _ÜJß 0 (12) x ´ Ù «» *-U² 0 ´ Ù § » *-U²§0 Õ -f² ²§0 (13) being EÝ UÞ § ß the instance of class ² , and Ö6 the number of instances of the class ² . The most usual distances ¹ belong to the Euclidean family. These measures do not require the modeling of any density function, but their relation to the probability of error can be very loose. Information or Uncertainty: Similarly to the probabilistic dependence, we may observe ¯ and compute the a posteriori probabilities *-f² ( ¯0 to determine how much information on the class of ¯ has been gained, with respect to its prior probability. If all the classes become roughly equally probable, then the information gain is minimal and the uncertainty (entropy) is maximum. Many measures can then be derived that make use of ;-¯0 and the set *-U² ( ¯0 . For instance, using Shannon’s entropy, we have: xnàZÇÌ<V µ ;-¯0 ´ Ù «» *-U² ( ¯0³á/âã p*-f² ( ¯0¹>¯ (14) Measures derived from generalizations of Shannon’s entropy –as Renyi’s entropy and the entropy of degree ä – are discussed in [7]. Entropy can also be used without knowledge of the densities as is done in the induction of decision trees [46], where the information gain is typically computed independently for each feature in the induction process. Also, the notion of entropy-based relevance is heuristically used in [55] as xs-/A@e0o?GH-\R7A@f0 (see Definition 8). Consistency: An inconsistency in A@ and ' is defined as two instances in ' that are equal when considering only the features in @ and that belong to different classes. The aim is thus to find theminimum subset of features leading to zero inconsistencies [4]. The inconsistency count of an instance + ) ' is defined as [32]: Q \MåWæ7-/+10o4 @ -/+<0IVD¶*·5¸ @ -/+<0 (15) where @-/+<0 is the number of instances in ' equal to + using only the features in A@ and A@ -/+<0 is the number of instances in ' of class equal to + using only the features in A@ . The inconsistencyrate of a featuresubset in a sample ' is then: QÆç -U @ 0o º4è>é à Q \åWæ-+10 ( ' ( (16) This is a monotonic measure, in the sense BY*pdê Qnç -U 0 Qnç -/*p0 A possible evaluation measure is then xs-/A@e0 ë_ì Ý åWæ ß/ . This measure is in = and can be evaluated in - ( ' ( 0 time using a hash table [32]. 3.3 General Schemes for Feature Selection The relationship between a FSA and the inducer chosen to evaluate the usefulness of the feature selection process can take three main forms: embedded,filter and wrapper. Embedded Scheme: The inducer has its own FSA (either explicit or implicit). The methods to induce logical conjunctions[54, 56] providean exampleof this embedding. Other traditional machine learning tools like decision trees or artificial neural networks are includedin this scheme[38]. Filter Scheme: If the feature selection process takes place before the induction step, the former can be seen as a filter 6
of non-useful features prior to induction. In a general sense it can be seen as a particular case of the embedded scheme in which feature selection is used as a pre-processing. The filter schemes are independent of the induction algorithm. Wrapper Scheme: In this scheme the relationship is taken the other way around: it is the FSA that uses the learning algorithm as a subroutine [24]. The general argument in favor of this scheme is to equal the bias of both the FSA and the learning algorithm that will be used later on to assess the goodness of the solution. The main disadvantage is the computational burden that comes from calling the induction algorithm to evaluate each subset of considered features. 3.4 General Algorithm for Feature Selection An abstract algorithm for feature selection that shows in a unified form the behavior of any FSA is depicted in Fig. 3. In particular, being a (weighed) list of weighed subsets of features (i.e. states), maintains the ordered set of solutions in course. Exponential algorithms are typically characterized by ( ( (examples would be BRANCH AND BOUND [42] or +< [44]). The presence in the list is a function of the evaluation measure and defines the expansion order. Heuristic search algorithms also maintain this list (of open nodes), and the weighting is the value of the heuristic. Random searchmethods as EvolutionaryAlgorithms [5] are characterized by ( ( (the list is the population and the weighting is the fitness value of the individuals). Sequential algorithms maintain ( ( , though there are exceptions (e.g., a bidirectional algorithm [19] would use ( ( íw ). The second weighting (on the features of each solution subset) allows to include the two types of FSA according to their outcome (see §1). The initial list K is in general built out of the original set of features and the algorithm maintains the best solution at all times ( 'sâáUîï â ). At each step, a FSA with a given search organization manipulates the list in a specific way and calls its mechanism for the generation of successors which in turn uses x . The result is an updated list and the eventual update of the best solution found so far. Notice that the data sample ' is considered global to the algorithm. 3.5 Space of Characteristics of a FSA All FSA can be represented in a space of characteristics according to the criteria of: search organization (Org), generation of successorstates (GS) and evaluationmeasures (J) (Fig. 4), in accordance with the description in §3.2. This space Org,GS,J ¥ encompasses the whole spectrum of possibilities for a FSA. New proposals for evaluation measures (not expressible as a combination of the already existent) would extend the vertical axis. Input: ðòñ data sample with features óôõ óõöa÷ ø ñ evaluation measure to be maximized ùlðñ successor generation operator Output : ðúûünýgþ/ú ÷ ñ ( weighed ) f eatur e subset ÿ ö Start _Point ( ó ) ; ðúûüný þUú ÷ ö { best of ÿ according to ø }; repeat ÿ ö Search_Strategy ( ÿ ô ùlð ø ô³ó ) ; ó ö { best of ÿ according to ø }; if ø ó °ø /ðúû«üný þUú ÷ or ø ó ö ø /ðúûüÆý þUú ÷ and õ ó õ Xõ ðúûüÆý þUú ÷Eõ then ðúûünýgþUú ÷ ö°ó ; until Stop ( ø ô ÿ ) Figure 3. General Algorithm for Feature Selection. Search Organization Evaluation Measure Generation of Successors Distance Dependence Information Consistency Accuracy Divergence RandomSequentialExponential Forward Backward Compound Weighting Random Figure 4. Characterization of a FSA. Notice that the search organization and the generation of successor states are coordinates whose elements are, in principle, exclusive of each other, in the sense that a certain FSA will use only one combination organization/generation. We then speak of a hybrid FSA when it requires more than a point in the same coordinate to be characterized. This is unusual in the literature, although recent works seem to point in this direction [16, 8]. On the contrary, it is very feasible to combine several evaluation measures in a single FSA. Moreover, a measure could be regarded as belonging to more than one category (e.g., the divergence,dependence and information measures are very interrelated). In this vain, the vertical axis cate7
gorization should be regarded as conceptual (that is to say, what is measured more than how it is measured). Non-classical algorithms (in the context of feature selection), can also be located in this space. For example, evolutionary approaches with fitness x correspond to <random, random,any> and artificial neural networks to <sequential, weighting,accuracy>. An extensive bibliographical revision of FSAs is shown in Table 1. Algorithm SO GS J Ref. ABB E B Consistency [33] B&B E B Consistency [42] BDS S F/B Accuracy [19] BEAM E F any [1] BFF E F Distance [57] BOBRO E B Distance [10] BSE S F/B Information/Accuracy [13] CARDIE E F Information/Accuracy [12] CFS E F Dependence [22] DTM S B Information [11] FOCUS/-2 E F Consistency [2] GA R R Accuracy [53] K2-AS S F Probability/Accuracy [50] KOLLER S B Information [27] LVF R R Consistency [34] LVI R R Consistency [36] LVW R R Accuracy [35] MDLM E B Informacion [49] MIFES-1 E B Consistency [43] OBLIVION E B Distance/Accuracy [30] POE-ACC S F Dependence [41] PQSS S C Accuracy [19] PRESET S W Dependence [39] QBB R/E R/B Consistency [16] RACE S F/B Probability/Accuracy [40] RC S B Accuracy [20] RELIEF R W Distance [25] RGSS R F/B Accuracy [19] RMHC-PF1 R R Distance/Accuracy [51] SA R R Accuracy [19] SBG S B any [18] SBS S B Distance [37] SBS-W S B Accuracy [18] SBS-SLASH S B Accuracy [13] SCHLIMMER E F Consistency [47] SEGEN S F Distance [48] SFG S F any [18] SFFS E C any [45] SFBS E C any [45] WINNOW S W Consistency [31] W-SBG S B Accuracy [26] W-SFG S F Accuracy [26] Table 1. Space of Characteristics of some FSA. Key: SO = Search Organization (E = Exponential, S = Sequential, R = Random), GS = Generation of Successors (F = Forward, B = Backward, C = Compound, W = Weighting, R = Random), J = Evaluation Measure. 4 Description of fundamental FSAs In this section several of the currently most widespread FSA in machine learning are briefly described and commented on. In the following let us assume again that the evaluation measure is to be maximized. 4.1 LVF Algorithm LVF (LAS VEGAS FILTER) [34] (<random, random, any>) repeatedly generates random feature subsets and then computes their evaluation measure. It was originally implemented with consistency of the sample as evaluation measure. The algorithm is described in Fig. 5. Input: ñ the maximum number of i t e r a t i o n s ø ñ evaluation measure ð ó ñ a sample ð described by ó , õ óõö°÷ Output : ÿ ñ a l l equivalent so lu tio ns found ÿ : = [ ] / / L stores equally good sets ý : = ó / / Initialize best solution ø : = ø /ð ó / / minimum allowed value of J repeat times ó : = Random_SubSet( ý )/ / õ ó õ {õ ý õ if ø /ð ! ó °ø then i f õ ó õ Xõ " ý õ then ý : = ó ÿ : = [ ó ]/ / L is reinitialized else i f õ ó õö4õ ý õ then ÿ : = append ( ÿ ôuó ) end end end end Figure 5. LVF (Las Vegas Filter Algorithm). LVW (Las Vegas Wrapper) [35] is a wrapper algorithm that uses LVF to generate candidate subsets and accuracy of an inducer as the evaluation measure. 4.2 LVI Algorithm LVI (LAS VEGAS INCREMENTAL) [36] (<random, random, consistency>) is based on the grounds that it is not necessary to use the whole sample ' in order to evaluate the measure x . The algorithm departs from a portion 't of ' ; if LVF finds a sufficiently good solution in 't then LVI halts. Otherwise the set of samples in 'P`' t making 't inconsistent is added to 't , this new portion is handed over to LVF and the process is iterated. Actually the evaluation measure could be any. The algorithm is described in Fig. 6. 8
Input: ñ the maximum number of i t e r a t i o n s ø ñ evaluation measure ð ! ó ñ a sample ð described by óôõ óõöP÷ # ñ i n i t i a l percentage Output : ó ñ solution found ð : = portion ( ð ô # )/ / Initial portion ð %$ : = ð & oð / / Test set ø : = ø /ð ó / / Minimum allowed value of J repeat forever ó : = LVF ( ô ø ô ð ó ) if ø /ð ó aø then stop else ' : = { elements in ð $ with low contr ibution to ø using ó } ð : = ð )( ' ð $ : = ð $& ' end end Figure 6. LVI (Las Vegas Incremental Algorithm). Intuitively, the portion can be neither too small nor too big. If it is too small, after the first iteration many inconsistencies will be found and added to the current subsample, which will hence be very similar to ' . If it is too big, the computational savings will be modest. The authors suggest = +* or a value proportional to the number of features. 4.3 Relief Algorithm RELIEF [25] (<random, weighting, distance>) chooses randomly an instance + of ' and determines its near hit and its near miss in relation to ' . The former is the closest instance to + among all the instances in the same class of + . The latter is the closest instance to + among all the instances in a different class. The underlying idea is that a feature is more relevant to + the more it separates + and its near miss, and the least it separates + and its near hit. The result is a weighed version of the original feature set. The basic algorithm is described in Fig. 7. An improvedversion [28] is proposed(RELIEF-F) where the more similar instances are selected (belonging to the same or different class, respectively) and their averages are computed. Input: # ñ sampling percentage , ñ distance measure ð ó ñ a sample ð described by óôõ óõö°÷ Output : - ñ array of fea ture weights i n i t i a l i z e - [ ] to zero do # õ ð õ times . : = Random_Instance /ð .0/21 : = Near ñ Hit . ô ð ./43 : = Near ñ Miss . ô ð for each þ 6587:9";:; ÷ =< do - 7 þ < : = - 7 þ <> ,? . ô . /43 ñ ,? . ô .0/21 end end Figure 7. RELIEF Algorithm. 4.4 SFG/SBG Algorithms SFG (SEQUENTIAL FORWARD GENERATION) (<sequential, forward, any>) iteratively adds features to a initial subset, in such a way that improves a given measure x taking into account those features already present in the solution. Additionally, an ordered list can also be obtained. SBG (SEQUENTIAL BACKWARD GENERATION) (<sequential, backward, any>) is the backward counterpart. The algorithms are jointly described in Fig. 8. Input: ð ó ñ a sample ð described by óôõ óõö°÷ ø ñ evaluation measure Output : ó ñ solution found ó ö A@ / / forward ó ö°ó / / backward repeat ö BDCFE ø /ð ! ó ( EGFH õ 5 ó & ó H //forward ö BDCFE ø /ð ! ó & EDIH õ 5 ó H //backward ó öPó ( ED H //forward ó öPó & EG H / / backward until no improvement in ø in l a s t J steps or ó ö°ó / / forward or ó ö A@ / / backward Figure 8. SBG/SFG (Sequential Backward /Forward Generation Algorithms). The algorithms W-SFG and W-SBG (wfor wrapper) use the accuracy of an external inducer as evaluation measure. 9
[7] M. Ben-Bassat. Use of Distance Measures, Information Measures and Error Bounds in Fuature Evaluation. In P. R. Krishnaiah and L. N. Kanal, editors, Handbook of Statistics, volume 2, pages 773–791, North Holland, 1982. [8] J. Bins and B. Draper. Feature Selection from Huge Feature Sets. In Int. Conf. on Computer Vision, volume 2, pages 159–165, Vancouver, CA, 2001. [9] A. L. Blum and P. Langley. Selection of Relevant Features and Examples in Machine Learning. In R. Greiner and D. Subramanian, eds., Artificial Intelligence on Relevance, volume 97, pages 245–271. Artificial Intelligence, 1997. [10] L. Bobrowski. Feature Selection Based on Some Homogeneity Coefficient. In Proc. of 9th Int. Conf. on Pattern Recognition, pages 544–546. IEEE Press, 1988. [11] J. Callan, T. Fawcett, and E. Rissland. An Adaptive Approach to Case–Based Search. In Proc. of the 12th Int. Joint Conf. on Artificial Intelligence, pages 803–808. Morgan Kaufmann, 1991. [12] C. Cardie. Using Decision Trees to Improve Case–Based Learning. In Proc. of the 10th Int. Conf. on Machine Learning, pages 25–32, Amherst, MA, 1993. Morgan Kaufmann. [13] R. A. Caruana and D. Freitag. Greedy Attribute Selection. In Proc. of the 11th Int. Conf. on Machine Learning, pages 28–36, New Brunswick, NJ, 1994. Morgan Kaufmann. [14] R. A. Caruana and D. Freitag. How Useful is Relevance? Technical report, Fall’94 AAAI Symposium on Relevance, New Orleans, 1994. [15] S. Chandon and L. Pinson. Analyse Typologique. Masson, 1981. [16] M. Dash and H. Liu. Hybrid Search of Feature Subsets. In H. Y. Lee and H. Motoda, editors, Proc. of the 15th Pacific Rim Int. Conf. on AI, pages 22–27, Singapore, 1998. Springer Verlag. [17] M. Dash, H. Liu, and H. Motoda. Consistency Based Feature Selection. In Pacific–Asia Conf. on Knowledge Discovery and Data Mining, pages 98–109, 2000. [18] P. A. Devijver and J. Kittler. Pattern Recognition – A Statistical Approach. Prentice Hall, London, GB, 1982. [19] J. Doak. An Evaluation of Feature Selection Methods and their Application to Computer Security. Technical Report CSE–92–18, Davis, CA: University of California, Department of Computer Science, 1992. [20] P. Domingos. Context–Sensitive Feature Selection for Lazy Learners. Artificial Intelligence Review, 11:227–253, 1997. [21] P. Gärdenfors. On the Logic of Relevance. Synthese, 37:351–367, 1978. [22] M. A. Hall. Correlation–based Feature Selection for Machine Learning. PhD thesis, University of Waikato, 1999. [23] A. K. Jain and D. Zongker. Feature Selection: Evaluation, Application, and Small Sample Performance. Transactions on Pattern Analysis and Machine Intelligence, 19(2):153– 158, 1997. [24] G. H. John, R. Kohavi, and K. Pfleger. Irrelevant Features and the Subset Selection Problem. In Proc. of the 11th Int. Conf. on Machine Learning, pages 121–129, New Brunswick, NJ, 1994. Morgan Kaufmann. [25] K. Kira and L. Rendell. A Practical Approach to Feature Selection. In Proc. of the 9th Int. Conf. on Machine Learning, pages 249–256, Aberdeen, Scotland, 1992. Morgan Kaufmann. [26] R. Kohavi. Wrapper for Performance Enhancement and Oblivious Decision Graphs. PhD thesis, Stanford University, 1995. [27] D. Koller and M. Sahami. Toward Optimal Feature Selection. In Proc. of the 13th Int. Conf. on Machine Learning, pages 284–292, Bari, IT, 1996. Morgan Kaufmann. [28] I. Kononenko. Estimating Attributes: Analysis and Extensions of Relief. In Proc. of the European Conf. on Machine Learning, pages 171–182, Vienna, 1994. Springer Verlag. [29] M. Kudo and J. Sklansky. A Comparative Evaluation of medium and large–scale Feature Selectors for Pattern Classifiers. In Proc. of the 1st Int. Workshop on Statistical Techniques in Pattern Recognition, pages 91–96, Prague, Czech Republic, 1997. [30] P. Langley and S. Sage. Oblivious Decision Trees and Abstract Cases. In Working Notes of the AAAI94 Workshop on Case Based Reasoning, pages 113–117, Seattle, WA, 1994. AAAI Press. [31] N. Littlestone. Learning Quickly when Irrelevant Attributes Abound: A New Linear Threshold Algorithm. Machine Learning, 2:285–318, 1988. [32] H. Liu and H. Motoda. Feature Selection for Knowledge Discovery and Data Mining. Kluwer Academic Publishers, London, GB, 1998. [33] H. Liu, H. Motoda, and M. Dash. A Monotonic Measure for Optimal Feature Selection. In Proc. of the European Conf. on Machine Learning, pages 101–106. Springer Verlag, 1998. [34] H. Liu and R. Setiono. A Probabilistic Approach to Feature Selection: a Filter Solution. In Proc. of the 13th Int. Conf. on Machine Learning, pages 319–327. Morgan Kaufmann, 1996. [35] H. Liu and R. Setiono. Feature Selection and Classification: a Probabilistic Wrapper Approach. In Proc. of the 9th Int. Conf. on Industrial and Engineering Applications of AI and ES, pages 129–135. Morgan Kaufmann, 1996. [36] H. Liu and R. Setiono. Scalable Feature Selection for Large Sized Databases. In Proc. of the 4th World Congress on Expert System, pages 68–75. Morgan Kaufmann, 1998. [37] T. Marill and D. M. Green. On Effectiveness on Receptors in Recognition Systems. IEEE Transactions on Information Theory, 9:11–17, 1963. [38] T. M. Mitchell. Generalization as Search. Artificial Intelligence, 18(2):203–226, 1982. [39] M. Modrzejewski. Feature Selection Using Rough Sets Theory. In Proc. of the European Conf. on Machine Learning, volume 667, pages 213–226. Springer Verlag, 1993. [40] A. W. Moore and M. S. Lee. Efficient Algorithms for Minimizing Cross Validation Error. In Proc. of the 11th Int. Conf. on Machine Learning, pages 190–198, New Brunswick, NJ, 1994. Morgan Kaufmann. [41] A. Mucciardi and E. Gose. A Comparison of Seven Techniques for Choosing Subsets of Pattern Recognition Properties. IEEE Transactions on Computers, C–20(9):1023– 1031, 1971. [42] P. Narendra and K. Fukunaga. A Branch and Bound Algorithm for Feature Subset Selection. IEEE Transactions on Computer, C–26(9):917–922, 1977. 16
[43] A. Oliveira and A. Sangiovanni-Vincentelli. Constructive Induction using a non–greedy Strategy for Feature Selection. In Proc. of the 9th Int. Workshop on Machine Learning, pages 354–360, 1992. [44] J. Pearl. Heuristics. Addison-Wesley, 1983. [45] P. Pudil, J. Novovicová, and J. Kittler. Floating Search Methods in Feature Selection. Pattern Recognition Letters, 15(11):1119–1125, 1994. [46] J. R. Quinlan. C4.5 Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA, 1993. [47] J. C. Schlimmer. Efficiently Inducing Determinations: A Complete and Efficient Search Algorithm that uses Optimal Pruning. In Proc. of the 10th Int. Conf. on Machine Learning, pages 284–290, Amherst, MA, 1993. Morgan Kaufmann. [48] J. Segen. Feature Selection and Constructive Inference. In Proc. of 7th Int. Conf. on Pattern Recognition, pages 1344– 1346. IEEE Press, 1984. [49] J. Sheinvald, B. Dom, and W. Niblack. A Modelling Approach to Feature Selection. In Proc. of 10th Int. Conf. on Pattern Recognition, volume 1, pages 535–539. IEEE Press, 1990. [50] M. Singh and G. M. Provan. Efficient Learning of Selective Bayesian Network Classifiers. In Proc. of the 13th Int. Conf. on Machine Learning, pages 453–461. Morgan Kaufmann, 1996. [51] D. Skalak. Prototype and Feature Selection by Samplingand Random Mutation Hill Climbing Algorithms. In Proc. of the 11th Int. Conf. on Machine Learning, pages 293–301, New Brunswick, NJ, 1994. Morgan Kaufmann. [52] S. B. Thrun, J. Bala, E. Bloedorn, I. Bratko, B. Cestnik, J. Cheng, K. De Jong, S. Dvzeroski, S. E. Fahlman, D. Fisher, R. Hamann, K. Kaufman,S. Keller, I. Kononenko, J. Kreuziger, R. S. Michalski, T. Mitchell, P. Pachowicz, Y. Reich, H. Vafaie, W. Van de Welde, W. Wenzel, J. Wnek, and J. Zhang. The MONK’s Problems: A Performance Comparison of Different Learning Algorithms. Technical Report CS-91-197, Carnegie Mellon University, Pittsburgh, PA, 1991. [53] H. Vafaie and I. F. Imam. Feature Selection Methods: Genetic Algorithms vs. Greedy like Search. In Proc. of Int. Conf. on Fuzzy and Intelligent Control Systems, 1994. [54] S. A. Vere. Induction of Concepts in the Predicate Calculus. In Proc. of the 4th Int. Joint Conf. on Artificial Intelligence, pages 281–287, Tbilisi, Georgia, 1975. Morgan Kaufmann. [55] K. Wang, D. Bell, and F. Murtagh. Relevance Approach to Feature Subset Selection. In H. Liu and H. Motoda, editors, Feature Extraction, Construction and Selection, pages 85– 97. Kluwer Academic Publishers, 1998. [56] P. H. Winston. Learning StructuralDescriptions fromExamples. In Winston, P. H., editor, The Psychology of Computer Vision, New York, NY, 1975. McGraw Hill. [57] L. Xu, P. Yan, and T. Chang. Best First Strategy for Feature Selection. In Proc. of 9th Int. Conf. on Pattern Recognition, pages 706–708. IEEE Press, 1988.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance #Relevant = 4 #Relevant = 8 #Relevant = 16 #Relevant = 32 (a) Irrelevance vs. Relevance - Parity - C-SBG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance #Relevant = 6 #Relevant = 12 #Relevant = 18 #Relevant = 24 (b) Irrelevance vs. Relevance - GMonks - RELIEF 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance #Relevant = 4 #Relevant = 8 #Relevant = 16 #Relevant = 32 (c) Redundance vs. Relevance - Parity - LVF 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance #Relevant = 4 #Relevant = 8 #Relevant = 16 #Relevant = 32 (d) Redundance vs. Relevance - Disjunction - QBB 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.75 2 Score Sample Size = k * 20 * N_T * c #Relevant = 5 #Relevant = 10 #Relevant = 15 #Relevant = 20 (e) Sample Size - Disjunction - LVI 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.75 2 Score Sample Size = k * 20 * N_T * c #Relevant = 6 #Relevant = 12 #Relevant = 18 #Relevant = 24 (f) Sample Size - Parity - W-SBG Figure 14. Some results of the experiments. 18
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance RELIEF W-SFG SFFG W-SBG E-SFG LVF SFBG LVI QBB C-SBG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance SFFG RELIEF W-SFG SFBG W-SBG LVF QBB C-SBG E-SFG LVI (a) Irrelevance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance RELIEF W-SFG SFFG E-SFG W-SBG C-SBG LVF SFBG LVI QBB 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Irrelevance / #Relevance RELIEF W-SFG SFFG SFBG LVF W-SBG QBB C-SBG E-SFG LVI (b) Irrelevance - W 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance LVF LVI C-SBG QBB SFBG SFFG W-SFG W-SBG RELIEF E-SFG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance LVF C-SBG QBB SFBG SFFG W-SFG LVI W-SBG RELIEF E-SFG (c) Redundance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance LVF LVI QBB C-SBG W-SFG SFFG W-SBG RELIEF SFBG E-SFG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Score #Redundance / #Relevance LVF QBB C-SBG SFFG W-SFG LVI SFBG W-SBG RELIEF E-SFG (d) Redundance - W 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Score Sample Size = k * 20 * N_T * c W-SFG C-SBG W-SBG SFBG SFFG QBB LVF LVI RELIEF E-SFG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Score Sample Size = k * 20 * N_T * c W-SFG SFFG C-SBG QBB LVF SFBG W-SBG RELIEF LVI E-SFG (e) Sample Size 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Score Sample Size = k * 20 * N_T * c W-SFG RELIEF C-SBG LVF LVI QBB W-SBG SFBG SFFG E-SFG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Score Sample Size = k * 20 * N_T * c RELIEF W-SFG C-SBG LVF SFFG LVI QBB W-SBG SFBG E-SFG (f) Sample Size - W Figure 15. Results ordered by total average performance on the data sets (left inset) and by end performance (right inset). Figs. (b), (d) and (f) are weighed versions of (a), (c) and (e), respectively. 19