Feature selection algorithms: a survey and experimental evaluation

Feature Selection Algorithms: A Survey and Experimental Evaluation Luis Carlos Molina, Lluis Belanche, Angela Nebot Universitat Polit2cnica de Catalunya Departament de Llenguatges i Sistemes Informdtics Jordi Girona 1-3, C6, 08034, Barcelona, Spain. (lcmolina,belanche,angela} @ 1si.upc.es Abstract In view of rhe subsranrial number of exisling feature selecrion algorithms, rhe need arises to counr on criteria thar enables ro adequately decide which algorithm to use in cerrain situarions. This work assesses the performance of severalfundnmental algorirhms found in the lireralurr in a conrmlled scenario. A scoring measure ranks the algorithms by raking info accounr the amounr of rplevance, irrelevance and redundance on sample data sers. This measure compura rhe degree of marching between rhe ourpur given by rhe algorithm and rhe known oprimal solurion. 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 hest 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 perspectivemay 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[5]. In this research. several fundamental algorithms found in the literature are studied to assess their performance in 0-7695-1754-4/02 $17.00 Q 2002 IEEE 306 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 dependence on 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 specially when there is poor knowledge available about the structure of the solution. 2 Algorithms for Feature Selection A FSA should he seen as a computational approach to a definition of relevance, although in many cases these definitions are followed in a somewhat loose sense. For a review of such definitions, see [161. 2.1 Feature Selection Definition Let X he the original set of features, with cardinality 1x1 = n. The conrinuous feature selection problem refers to the assignment of weights wi to each feature zi E X 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 leaming [4,9]), orfilrering the output of the continuous problem solution (see $4.1). These are quite different problems reflecting different design objectives. In the continuous case, one is interested in keeping all the features hut 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 2". In this case, a general definition is [131: Definition 1 (Feature Selection) Let J(X') be an evaluation measure to be optimized (say to maximize) defined as J : X' E X + !R The selection of a fearure subset can be seen under three considerations: e Set IX'I = m < n. Find X' C X, such that J(X') is maximum. Set a value J,,, this is, the minimum J that is going to be tolerated. Find the X' 2 X with smaller IX'I, such that J(X') 2 J,. Find a compmmise among minimizing IX'I and mimiring J(X') (general case). Notice that, with these definitions, an optimal subset of features is not necessarily unique. 2.2 Characterization of FSAs There exist in the literature several considerations to characterize feature selection algorithms [3,8, 141. 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. 2.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 w1,. . . , w, of the possible features of X, with 1x1 = n. In the binary case, wi E {O, 1). whereas in the continuous case wi E [O,l]. 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 SI < Sz if SI C Sz. whereas in the continuous case SI < Sz if, for all i, wi(S1) 5 w,(Sz) holds. BeingLa(lahe1ed)listofweighed subsets of features (i.e. states), L 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 ILI = 1, whereas exponential and random ones typically use ILI 2 1. Exponential Sear& It corresponds to algorithms that carry out searches whose cost is O(2"). 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[l7] algorithm is optimal. A measure J is monotonic if for any two subsets SI, Sz and SI C_ Sz, then J(Sl) 2 J(Sz). Another example would be an A' search with an admissible heuristic[l8]. 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 O(n) in order to qualify as a sequential search. The complexity is determined taking into account the number k of evaluated subsets in each state change. The cost of this search is therefore polynomial O(nk+'). Consequently, these methods do not guarantee an optimal result, since the optimal solution could 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[l4] and can give several optimal subsets as solution. 222 Generation of Successors All of the operators act by modifying in some way the weights wi of the features 2,. with w, E P (in the case of the weighting operator), or wi E {0,1} (for the rest). Forward Add features to the current solution XI, among those that have not been selected yet. In each step. the feature that makes J be greater is added to the solution. Starting with X' = 0, thefonvard step consists of: X':=X'u{zi ~X\X'IJ(X'U{zi})isbigger} (I) The stopping criterion can be: IX'I = n' (if n' has been fixed in advance), the value of J has not increased in the last j steps, or it surpasses a prefixed value Jo. The cost of the operator is O(n). The main disadvantage is that it is not possible to have in consideration certain basic interactions among features. For example, if q,z2 are such that J({zl,zz}) >> J({zl}), J({ZZ)). neither21 and22 could be selected, in spite of king very useful. Backward Remove features from the current solution X', among those that have not been removed yet. In each step, the feature that makes J be greater is removed from the solution. Starting with X' = X, the backward step is: X' := X' \ {zi E X' I J(X' \ {z,}) is bigger} (2) The stopping criterion can be. IX'( = n', the value of J has not increased in the last j steps, or it falls below a prefixed value Jo. This operator remedies some problems although there still will be many hidden interactions (in the sense of being unobtainable). The cost is O(n), although in practice it demands more computation than forward [I 21. Both operators (forward and backward) can be generalized selecting, at each step, subsets of k elements X" and 307 selecting the one making J(X'uX") or J(X'\X") bigger, respectively. The cost of the operator is then O(n*). Compound Apply f consecutive forward steps and b consecutive backward ones. If f > b the 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 J. This allows to discover new interactions among features. An interesting "backtracking mechanism" is obtained, although other stopping conditions should be established iff = b. For example, for f = b = 1, if z; is added and zi is removed, this could be undone in the following steps. A possible stopping criterion is zi = zj. In sequential FSA, f # b assures a maximum of n steps, with a cost O(nf'"1). 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 orher 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 J at each step. 2.2.3 Evaluation Measures Probability of error: Provided the ultimate goal is to build a classifier able of correctly labelling instances generated by the same probability distribution, minimizing the (bayesian) probability of error P. of the classifier seems to be the most natural choice. Therefore, it is also a clear choice for J. Let z' E R" represent the unlabeled instances, and R = {wl,. . . , wm} a set of labels (classes), so that c : R" + R. Such probability is efined as [71: P, = r. 11 - mpP(wiJz71p(i)di (3) where p(5) = C~lp(flw;)P(wi) is the (unconditional) probability distribution of the instances. and P(wil?) is the a posteriori probability of wi being the class of 2'. 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 respective decision boundaries between the classes [71. Some of these classifiers, like the one-nearest-neighbor rule. have a direct relation to the probability of error. This 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 densitiesp(z'1w;). using the general formula: J = f[p(z'lwi),p(~lwz)]di (4) I To qualify as a valid measure. the function f must be such that the value of J satisfies the following conditions: (a) J 2 0, (b) J = 0 only when the p(qw,) are equal and (c) J is maximum when they are non-overlapping. If the features used in a solution X' C X are good ones, the divergence among the conditional probabilities will be significant. Poor features will result in very similar probabilities. Some classical choices are: Chemoff, Bhattacharyya, Kullback-Liebler, Kolmogorov and Matusita [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. 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: m m J= zP(wi) P(wj)D(wi,wj) (6) being z(;,j) the instance j of class wi, and Ni the number of instances of the class wi. The most usual distances d 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 i and compute the a posteriori probabilities P(w;lZ) to determine how much information on the class of 2' 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. Consistency: An inconsistency in X' and S is defined as two instances in S that are equal when considering only the features in X' and that belong to different classes. The aim is thus to find the minimum subset of features leading to zero inconsistencies [I]. The inconsistency count of an instance A E S is defined as [14]: where X'(A) is the number of instances in S equal to A using only the features in X' and X;(A) is the number of instances in S of class k equal to A using only the features in XI. The inconsisrency rare of a feature subset in a sample S is then: is1 j=;+1 lCx8(A) = X'(A) -rn*pX;(A) (7) (8) Cats ICX~ (A) IS1 lR(X') = This is a monotonic measure, in the sense XI C Xz IR(X1) 2 IR(X2). 308 2.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[20] provide an example of this embedding. Other traditional machine Ieaming tools like decision trees or artificial neural networks are included in this scheme[lS]. Filter Scheme: If the feature selection process takes place before the induction step, the former can be seen as a filter 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 subroutine11 11. 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. 2.4 General Algorithm for Feature Selection An abstract algorithm that unifies the behavior of any FSA is depicted in Fig. 1. In particular, being La (weighed) list of weighed subsets of features (i.e. states), L keeps the ordered set of solutions in course. Exponential algorithms are typically characterized by ILI > 1 (examples are BRANCH AND BOUND 1171 or A' 1181). The presence in the list is a function of the evaluation measure and defines the expansion order. Heuristic search algorithms also keep this list (of open nodes), and the weighting is the value of the heuristic. Random search methods as Evolutionary Algorithms [2] are characterized by ILI 2 l (the list is the population and the weighting is the fitness value of the individuals). Sequential algorithms maintain ILI = 1. though there are exceptions (e.g., a bidirectional algorithm [SI would use ILI = 2). The second weighting (on the features of each solution subset) allows to include the two types of FSA according to their outcome (see 62.1). The initial list L is in general built out of the original set of features and the algorithm maintains the best solution at all times (Solution). 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 J. The result is an updated list and the eventual update of the best solution found so far. Notice that the data sample S is considered global to the algorithm. 3 Empirical Evaluation of FSAs The first question arising in relation to a feature selection experimental design is: what are the aspects that we would like to evaluate of a FSA solution in a given data set? In this study we decided to evaluate FSA performance with respect to four particularities: relevance, irrelevance, redundance and sample size. To this end, several fundamental FSAs are studied to assess their performance on synthetic data sets with known relevant features. Then sample data sets of different sizes are cormpted with irrelevant andor redundant features. The experiments are designed to test the endurance of different FSAs (e.g., behaviour against the ratio number-of-irrelevant vs. number-of-relevant features). 3.1 Particularities to be evaluated Relevance: Different families of problems are generated by varying the number of relevant features NR. These are features that, by construction, have an influence on the output and whose role can not be assumed by the rest (i.e., there is no redundance) Irrelevance: Irrelevant features are defined as those features not having any influence on the output, and whose values are generated at random for each example. For a problem with NR relevant features, different numbers of irrelevant features NI are added to the corresponding data sets (thus providing with several subproblems for each choice of NR). Redundance: In these experiments, a redundance exists whenever a feature can take the role of another (perhaps the simplest way to model redundance). This is obtained by choosing a relevant feature randomly and replicating it in the data set. For a problem with NR relevant features, different numbers of redundant features NR~ are added in a way analogous to the generation of irrelevant features. Input: S - data sample with features X,IXJ=n J - evaluation measure to be maximized GS - successor generation operator Solution - (weighed) feature subset output: L:= Start_Point(X): Solution:= 1 best of L according to J); repeat L := Search-Strategy (L,GS(J),X); X':= {best of L according to 51; if J(X') 2 J(Soiution) or (J(X') = J(So1ution) then Solution := X' ; and IX'J < ISoiutionl) until Stor,(J.L) Fig. 1. General Feature Selection Algorithm. 309 Sample Size: It refers to the number of instances IS1 of a data sample S. In these experiments, IS/ is defined as 1.9 = akNTc, where a is a constant. k is a multiplying factor, NT is the total number of features (NR +NI + NR~) and c is the number of classes. Note this means that the sample size will depend linearly on the number of features. 3.2 Evaluation of Performance The score criterion expresses the degree to which a solution obtained by a FSA matches the correct solution. This criterion behaves as a similarity s(z, y) : X x X + [0,1] in the classical sense [6], satisfying: 1. s(z,y)=l~z=y 2. S(Z>Y) = S(Y>Z) where s(z,y) > s(z,z) indicates that y is more similar to z than z. Let us denote by X the total set of features, partitioned in X = XR U XJ U XR,, being XR, XI, XR~ the subsets of relevant, irrelevant and redundant features of X, respectively and call X' 2 X the ideal solution. Let us denote by d the feature subset selected by a FSA. The idea is to check how much d and X' have in common. Let us definedR = XRnd, Ar = Xr nd anddR, = XR, nd. In general, we have AT = XT nd (hereafter T stands for a subindex in {R, I, R')), Since necessarily A g X, we have A = dR U Ar U dRf. The score Sx (d) : P(X) + [0,1] will fulfill the following conditions: Sx(d)=O*d=Xr Sx(A)=l*d=X* Sx(d) > Sx(d') indicates that A is more similar to The score is defined in terms of the similarity in that for all A & X,Sx(d) = s(A,X'). This scoring measure will also be parameterized, so that it can ponder each type of divergence (in relevance. irrelevance and redundance) to the optimal solution. The set of parameters is expressed as a={an,crr,a~,}withCIT~OandCcr~=l. Intuitive Description The criterion SX (A) penalizes three situations: I. There are relevant features lacking in A (the solution 2. There are more than enough relevant features in A (the 3. There are some irrelevant features in A (the solution is An order of importance and a weight will be assigned X' than A'. is incomplete). solution is redundant). incorrect). (via the a~ parameters). to each of these situations. Formal Description The precedent point (3.) is simple to model: if suffices to check whether > 0, being A the solution of the FSA. Relevance and redundance are strongly related given that, in this context, a feature is redundant or not depending on what other relevant features are present in d. Notice then that the optimal solution X' is not unique, though all them should be equally valid for the score. To this end, the features are broken down in equivalence classes, where elements of the same class are redundant to each other (i.e., any optimal solution must comprise only one feature of each equivalence class). Being A a feature set, we define a binary relation between two features zi,zj E d as: z; - zj - z; and zj represent the same information. Clearly - is an equivalence relation. Let A" be the quotient set of A under -, A" = {[z] I z E A}, any optimal solution A' will satisfy: I. IA'I = IXRI 2. V[zi] E A" : 3zj E [zi] : zj E A' We denote by A' any of these solutions. Construction of the score In the present case, the set to be split in equivalence classes is formed by all the relevant features (redundant or not) chosen by a FSA. We define then: A: = (dR U dR,)" (equivalence classes in which the relevant features chosen by ~1 FSA ore split) x; = (X, U xR<)- (equivalence classes in which the original feature1 ore split) Letdj;WX; = {[zi] E X; I 3[q] E A: : [zj] 2 [z;]} and define, for Q quotient set: F(Q) = (121 - 1) IdGQ The idea is to express the quotient between the number of redundant features chosen by the FSA and the number it could have chosen, given the relevant features present in its solution. In the precedent notation, this is written (provided the denominator is not null): F(4i) F(A; w x;) Let us finally build the score, formed by three terms: relevance, irrelevance and redundance. Defining: 0 if F(dg W X;) = 0 otherwise. '' = [ & (1 - m) F(A-) the score is Sx(d) = ~RR + a~tR' + arI,A E X. Restrictions on the a= We can establish now the desired restrictions on the behavior of the score. From the more to the less severe: there are relevant fearures lacking, there are irrelevant features, and there is redundancy in the solution. This is reflected in the following conditions on the aT: 1. Choosing an irrelevant feature is better than missing a relevant one: fi'fi 310 2. Choosing a redundant feature is better than choosing We also define a~ = 0 if IXT~ = 0. Notice that the denominators are important for, as an example, expressing the fact that it is not the same choosing an irrelevant feature when there were only two that when there were three (in the latter case, there is an irrelevant feature that could have been chosen when it was not). 4 Experimental Evaluation an irrelevant one: fi > fi In this section we detail the experimental methodology and quantify the various parameters of the experiments. The basic idea consists on generating sample data sets with known particularities (synthetic functions f) and hand them over to the different FSAs to obtained a hypothesis H. The divergence between the defined function and the obtained hypothesis will be evaluated by the score criterion. This experimental design is illustrated in Fig. 2. Figure 2. FlowChart of Experimental Design. 4.1 Description of the FSAs used Table 1. FSAs used in the experiments. 4.2 Implementations of Data Families A total of twelve families of data sets were generated studying three different problems and four instances of each, by varying the number of relevant features NR. Let zl,. . . , xn be the relevant features of a problem f. Panty: This is the classic binary problem of parity n, where the output is f (q,. . . , xn) = 1 if the number of z; = 1 is oddand f(zl,... ,zn) =Outherwise. Disjunction: A disjunctive task, with f (21,' . ' ,z,) = 1 if (21 A ... Ax,,) V A. .. Az,), withn' = ndiw2 if n is even and n' = (ndiu2) + 1 if n is odd. GMonks: This problem is a generalization of the classic monk problems [19]. In its original version, three independent problems were applied on sets of n = 6 features that take values of a discrete, finite and unordered set (nominal features). Here we have grouped the three problems in a sinele one comouted on each seement of 6 features. Let n The ten FSAs used in the experiments were : E-SFG. QBB, LVF, LVI, C-SBG, RELIEF, SFBG, smc, W-SBG. and versions of SFG using entropy and the accuracy of a C4.5 inducer, respectively. The algorithms C-SBG, W-SBG are be &iple of k, k = ,,div6 .&j b = 6(kt - 1) + 1, for 1 5 k' 5 k. Letusdenotefor"l"thefirstvalueofafeature, zb+4 = W-SFG (see Table 1). The algorithms E-SFG. W-SFG are for ~~~ the second, etc. ne problems are the following: p1 : (za = za+l) 2~ p2 ! n~ 2; = , in 2L,, , zLli. I -"_" -. . - . .. ...... _. ~ ~~~ - versions of SBG using consistency and the accuracy of a C4.5 inducer, respectively. During the course of the experiments the algorithms FOCUS, B&B, ABB and LVW were put aside due to their unaffordable consumption of resources. For a review of all these algorithms, see [161. Since RELIEF and E-SFG give as output an ordered list 3, p3 : (zb+4 = 3AJb+3 = 1)V(zs+4 + 3Azs+l + 2) For each segment, the boolean condition p2 A 7(p1 ~ P3) is checked. If this condition is satisfied for s or more segments with s = n. diw 2 (being n, the number of segments) the function GMonks is 1; otherwise, it is 0. of features zi according to their weight w;. a filtering criterion is necessary to transform this solution to a subset of features. The procedure used here is simple: since the interest is in determining a gwd cut point, first those w; further than two variances from the mean are discarded (that is to say, with very high or very low weights). Then define si = wi + and aj = E:=, si. The objective is to search for the feature zj such that: is maximum. 4.3 Experimental Setup The fint group refers to the relationship between irrelevance vs. relevance. The second refers to the relationship between redundance vs. relevance. The last group refers to sample size. Each group uses three families of problems (Parity, Disjunction and GMonks) with four different instances for each problem, varying the number of relevant features NR. Relevance: The different numbers NR vary for each problem, as follows: (4,8, 16, 32) (for Parity), (5, 10, 15, 20) (for Disjunction) and (6,12, 18,24) (for GMonkr). The experiments were divided in three a.n-3 1 - 1an n The cut point is then set between zj and zj+l. 311 Irrelevance: In these experiments, we have NI running from 0 to 2 times the value of NR, in intervals of 0.2 (that is, eleven different experiments of irrelevance for each NR). Redundance: Similarly to the generation of irrelevant features, we have Nn, running from 0 to 2 times the value of NR. in intervals of 0.2. Sample Size: Given the formula JSI = akNTc (see 53.1). different problems were generated considering k E t0.25, 0.5, 0.75, 1.0, 1.25, 1.75, 2.0). NT = NR + NI + NR*. C= 2, O( = 20andN1 = NR, = N~div2. 4.4 Results Due to space reasons, only a sample of the results are presented, in Figs. 3(a) and (b). Each pint is the average of 10 independent runs with different random data samples. The horizontal axis represents the ratios between these particularities as explained above. The vertical axis represents the average results given by the score criterion. In Fig. 3(a) the C-SBG algorithm shows at first a good performance but clearly as the irrelevance ratio increases, it falls dramatically (below the 0.5 level from NI = NR on). Note that for NR = 4 performance is always perfect (the plot is on top of the graphic). The plots in Fig. 3(b) show additional interesting results because we can appreciate the curse of dimensionality effect [IO]. In this figure, W-SBG present an increasingly poor performance (see the figure from top to bottom) with the number of features provided the number of examples is increasing in a linear way. However, in general, as long as more examples are added performance is better (see the figure from left to right). A summary of the resulls is displayed in Fig. 4 for the ten algorithms, allowing for a comparison across all the sample data sets with respect to each studied particularity. Specifically. Figs. 4(a). (b) and (c) show the average score of each algorithm for irrelevance, redundance and sample size, respectively. In each graphic there are two keys: the key to the left shows the algorithms ordered by ioial average performance, from top to bottom. The key to the right shows the algorithms ordered by average performance on the lusi abscissa value, also from top to bottom. In other words, the left list is topped by the algorithm that wins on average, while the right list is topped by the algorithm that ends on the lead. This is also useful to help reading the graphics. Fig. 4(a) shows that RELIEF ends up on the lead of the irrelevance vs. relevance problems, while SFFG shows the best average performance. The algorithm W-SFG is also wellpositioned. Fig.4@) showsthatthealgorithms ~v~and LVI together with C-sBG are the overall best. In fact, there is a bunch of algorithms that also includes the twoflooring and QBB showing a close performance. Note how RELIEF and the wrcrppers are very poor performers. Fig. 4(c) shows that the wrapper algorithms seem to be able to extract the most of the data when there is a shortage of it. Surprisingly, :I , , , , , , , , , (a) Irrelevance YS. Relevance - Parity - C-SBG. s .a a. U. .1 II I. I' /. IS 1 -,I_ Figure 3. Some results to irrelevance, rele vance and sample size. the backward wrapper is just fairly positioned on average. The SWG is again quite good on average, together with CSBG. However, all of the algorithms are quite close and show the same kind of dependency to the data. Note the general poor performance of E-SFC, provided it is the only algorithm that computes its evaluation measure (entropy in this case) independently for each feature. 5 Conclusions The task of a feature selection algorithm (FSA) is to provide with a computational solution to the feature selection problem motivated by a certain definition of relevance. This algorithm should be reliable and efficient. The many FSAs proposed in the literature are based on quite different principles (as the evaluation measure used, the precise way to explore the search space, etc) and loosely follow different definitions of relevance. In this work a way to evaluate FSAs was proposed in order to understand their general behaviour on the particularities of relevance, irrelevance, redundancy and sample size of synthetic data sets. To achieve this goal, a set of controlled experiments using artificially generated data sets were designed and carried out. The set of optimal solutions is then compared with the output given by the FSAs (the obtained hypotheses). To this end, a scoring measure was defined to express the degree of approximation of 3 12 ,Redundance Figure 4. Results ordered by total average performance on the data sets (left inset) and by end performance (right inset). the FSA solution to the real solution. The final outcome of the experiments can be seen as an illustrative step towards gaining useful knowledge that enables to decide which algorithm to use in certain situations. The behaviour of the alp rithms to different data particularities is shown and thus the danger in relying in a single algorithm. This points in the direction of using new hybrid algorithms or combinations thereof for a more reliable assessment of feature relevance. Acknowledgements TAP99-0747 and by the Mexican Petroleum Institute. This work is supported by the Spanish CICyT Project References [I1 H. Almuallim and T. G. Dietterich. Leaming Boolean Concepts in the Presence of Many Irrelevant Features. Anificin1 Intelligence, 69( 1-2):279-305. 1994. I21 T. Back. Evolutionnry Algorithm in Theory and Practice. Oxford University Press. Oxford. 1996. [3] A. L. Blwn and P. Langley. Selection of Relevant Fatures and Examples in Machine Leaming. In R. Greiner and D. Subrammian, editors, Anificial Intelligence on Relevance, volume 97, pp. 245-21 I. AI, 1997. I41 R. A. Caruanaand D. Freitag. Greedy AttributeSelection. In Pmc. of the 11th ht. Conf on Machine Lmming, pp. 28-36, New Brunswick, NJ, 1994. Morgan Kaufmam. [5] R. A. Camana and D. Freitag. How Useful is Relevance? Technical repon, AAA1 Symposium on Relevance. 1994. 161 S. Chandon and L. Pinson. A~lyse Tygologique. Masson, 1981. [7] P.A. Devijver and 1. Kittler. PonernRecognition-A Statistical Appmach. Prentice Hall, London. GB, 1982. [E] 1. Doak An Evaluation of Feature Selection Methods and their Application to Computer Security. Technical Repon CSE-92-18, Univ. of California, 1992. [9] M. A. Hall. Correlotion-bared Feature Selection for Mochinelearning. PhD thesis, University of Waikato. 1999. [IO] A. K. lain and D. Zongker. Feature Selection: Evaluation, Application, and Small Sample Performance. IEEE Tmnroctionr on Panern Anolvsis and Machine Intelli~ence. -. 19(2):153-158. 1997. [I I] G. H. John. R. Kohavi, and K. PReger. Irrelevant Features and the Subset Selection Problem. in Pmc. of the 11th Inr. Conf on Machine Learning, pp. 121-129, New Brunswick, NI, 1994. Morgan Kaufmann. [I21 D. Koller and M. Sahami. Toward Optimal Feature Selection. In Pmc. of the 13th Inl. CO@ on Machine Learning, pp. 284-292, Bari, IT. 1996. Morgan Kaufmann. [I31 M. Kudo and J. Sklansky. A Comparative Evaluation of medium and large-scale Feature Selectors for Pattern Classifiers. In Proc. of rhc 1st Inr. Workhop on Srotisticol Techniques in Portern Recognition, pp. 91-96, Prague, 1997. [I41 H. Liu and H. Motoda. Feature Selection for Knowledge Discoverv nnd Dam Mining. Kluwer Academic Publishers. I London. GB, 1998. 1151 T. M. Mitchell. Generalization as Search. Anificial Intelli- ~~ gencc, 18(2):203-226.1982. [I61 L. C. Molina. L. Belanche, and A. Nebot. Feature Selection Algorithms: A Survey and Experimental Evaluation. Technical Repon LSI-02-62-R, Universitat Polithcnica de Catalunya. Barcelona, Spain, 2002. 1171 P. Narendra and K. Fukunaga. A Branch and Bound Algorithm for Feature Subset Selection. IEEE Trnnsoctionr on Computer. C-26(9):917-922, 1977. [I81 J. Pearl. Heuristics. Addison Wesley, 1983. [19] S. B. Thmn et al. The MONKS Problems: A Performance Comparison of Different Learning Algorithms. Technical Report CS-91-197, CMU, Pittsburgh.PA. 1991. 1201 P. H. Winston. Leaming Structural Descriptions fmm Examples. In Winston, P. H.. editor, The Psychology of Computer %ion, New York, NY. 1975. McGraw Hill. 313