Rough Sets and Evolutionary Computation to Solve the Feature Selection Problem Rafael Bello1 , Yudel G´omez1 , Yail´e Caballero2 , Ann Nowe3 and Rafael Falc´on1 1

2

3

Computer Science Department, Central University of Las Villas (UCLV) Carretera Camajuan´ı km 5.5, Santa Clara, Cuba {rbellop, ygomezd, rfalcon}@uclv.edu.cu Informatics Department, University of Camag¨ uey, Cuba [email protected] CoMo Lab, Computer Science Department, Vrije Universiteit Brussel, Belgium [email protected]

Summary. The feature selection problem has been usually addressed through heuristic approaches given its significant computational complexity. In this context, evolutionary techniques have drawn the researchers’ attention owing to their appealing optimization capabilities. In this chapter, promising results achieved by the authors in solving the feature selection problem through a joint effort between rough set theory and evolutionary computation techniques are reviewed. In particular, two new heuristic search algorithms are introduced, i.e. Dynamic Mesh Optimization and another approach which splits the search process carried out by swarm intelligence methods.

Key words: meta-heuristic, evolutionary computation, feature selection

1 Introduction The solution of a great deal of problems can be formulated as an optimization problem. The quest for the problem’s solution is often stated as finding the optimum of an objective function f : D → nf then assign the first m ants according to (2) and the remaining ones as in (1). The process of finding the candidate reduct sets B happens in a sequence of cycles N C = 1, 2, . . . In each cycle, all ants build their own set Bk . The process stop criterion is met (PSC = true) once the maximal number of cycles has been exceeded N C > N Cmax . Each ant k keeps adding one feature at a time to its current partial set Bk until γBk (Y ) = γA (Y ). This is known as the ant stopping criterion (ASCk =true). The population size is envisioned as a function of the number of features m = f (nf) where round(x) denotes the closest integer to x. R1 : If nf < 19 then m = nf R2 : If 20 ≤ nf ≤ 49 then if 2/3 nf ≤ 24 then m=24 else m=round(2/3 nf) R3 : If nf > 50 then if nf/2 ≤ 33 then m = 33 else m = round(nf/2) The above rules are the direct outcome of a thorough experimental analysis conducted with the purpose in mind of setting the population size on the basis of the number of features describing the data set. Now we are ready to present the ACS-RST-FS approach in a more formal way. Let us look at Algorithm 4. A new approach in Ant Colony Optimization for solving the feature selection problem was introduced in [3]. The two-step ACO algorithm is also based on the idea of splitting the process of finding reducts into two stages. The algorithm dynamically constructs candidate feature subsets during the first stage which shall be afterwards used as starting points for each ant’s

RST and Evolutionary Computation to Feature Selection

17

Algorithm 4 ACS-RST-FS 1: procedure ACS-RST-FS( ) 2: PSC ← false, NC ← 1 3: Calculate τi (0), i = 1, . . . ,nf (random initial values for trail intensity) 4: repeat 5: Each ant k is assigned to an attribute ai , ∀k ∈ {1, . . . , m} and B k ← {ai } 6: ASCk ← false ∀k ∈ {1, . . . , m} 7: repeat 8: for k ← 1 to m do 9: if ASCk = false then 10: Select new feature a∗i according to (1) 11: Bk = Bk ∪ {a∗i } 12: τi ← (1 − ξ) · τi + ξ · τi (0) . i is the index of a∗i 13: Update ASCk . Did ant k complete a reduct Bk ? 14: end if 15: end for 16: until ASCk = true ∀k ∈ {1, . . . , m} 17: Bk∗ ← best Bk . Now that all ants have finished, select the best reduct 18: for each ai ∈ Bk∗ do k 19: τi ← (1 − ρ) · τi + ρ · γB (Y ) . update global pheromone trail 20: end for 21: For each feature i do τi = nτi X τj j=1

22: NC ← NC + 1 23: Update PSC 24: until PSC = true 25: end procedure

own candidate feature subset in the second stage. The number of cycles, the number of ants and the desired quality of the subsets are degrees of freedom of the model related to each stage. We use the same ratio r that affects the three aforementioned parameters. For instance, suppose we are interested in carrying out 100 cycles as the overall algorithm’s execution and we will use 30 ants for generating Bk subsets with the maximum possible quality of classification (N Cmax = 100, m = 30, γB (Y ) = 1). Setting r = 0.3 means that the first stage will last only 30 iterations, involving 9 ants and will settle for reducts whose quality would be 0.3 or above. Being this so, the values of these parameters during the second phase will be N Cmax = 70, m = 21 and the algorithm will look for subsets with the maximum possible quality of classification. The workflow of activities of the TS-ACS-RST-FS proposed approach is depicted in Algorithm 5. Of course, any other alternative ACO-based implementation can be used rather than the ACS-RST-FS algorithm. An important issue in this approach is to study which is the most suitable value for ratio r. High values of r (near to 1) cause the two-step algorithm to obtain candidate subsets close to the

18

Rafael Bello et al.

Algorithm 5 TS-ACS-RST-FS procedure TS-ACS-RST-FS( ) Compute the population size (m) on the basis of the number of features (nf) Compute the quality of classification using (1) and B = A STAGE 1 Calculate parameter values in the first stage as follows: N Cmax1 = r · N Cmax , m1 = r · m, γB 1 (Y ) = r · γB (Y ) Run the ACS-RST-FS approach CS ← output of ACS-RST-FS . CS holds the candidate reducts STAGE 2 Calculate parameter values in the second stage as follows: N Cmax2 = N Cmax − N Cmax1 , m2 = m − m1 , γB 2 (Y ) = γB (Y ) Run the ACS-RST-FS approach but assign in each cycle a random subset from CS as initial subset for each ant end procedure

definition of reducts in the first stage, therefore ants in the second step swiftly find reducts but using very limited iterations and a scarce number of search agents (ants). On the contrary, if the ratio value is low, the quality of the candidate feature subsets computed during the first stage is poor yet there are more ants to work for a larger number of cycles in the second stage. We have developed an experimental study which is concerned with this tradeoff. The following values for the ratio parameter have been proposed r ∈ {0.2, 0.3, 0.36, 0.5, 0.6, 0.8} and the impact of each of these values over the number of reducts obtained, their length as well as the computational time needed to produce the output has been observed. Table 4 reports the average results achieved after 20 iterations. A synthetic repository comprised of 20 objects which are described by 16 features provides the data for conducting the experiments. The maximum number of cycles is 21. Table 4: Results obtained with the proposed ACO-based approaches. The last two columns portray the average number of reducts, the average length of the reducts and the computational time (in seconds), these three indicators separated by backslash. Algorithm ACS TS-ACS TS-ACS TS-ACS TS-ACS TS-ACS TS-ACS

r r r r r r

N Cmax 1 N Cmax 2 m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3 = 0.2 = 0.3 = 0.36 = 0.5 = 0.6 = 0.8

– 4 6 8 10 13 17

– 17 15 13 11 8 4

– – 46.7/3.95/228 3 13 32.7/4.2/82 5 11 43.3/4.1/53 6 10 38.7/3.9/39 8 8 29.7/3.8/32 10 6 20.33/3.8/41 13 3 9/3.8/82

123/4.19/274 76.3/4.2/89.9 71.3/4.2/64 67.3/4.1/47 43.3/4.1/44 37/4.2/49 10.67/4.2/97

RST and Evolutionary Computation to Feature Selection

19

We can see that r = 0.3 bears the best results. This setting implies a number of reducts similar to ACS-RST-FS but only in the 23% of the time. Similar results can be witnessed across other data sets. For instance, in Table 5 we display the results using the Breast Cancer database from UCI Repository. The result here is not surprising, since the value r = 0.3 provides a good balance between both stages; a higher number of ants and cycles in the second stage allows the algorithms to perform a larger exploration of the search space departing from initial subsets with an acceptable quality. Another point worthwhile stressing is that the time complexity of TS-ACSRST-FS is very low. In light of this, we propose a second idea: to increase the number of ants in order to bring about a greater exploration of the search space. In Table 6 the same data set than in Table 4 was used but now the population size is increased by the factors 1.33, 1.5, 1.8 and 2.1, respectively. In columns 4 and 5 the relationship between each alternative and the ACSRST-FS benchmark algorithm is reported in terms of the amount of reducts achieved and the computational time needed. For instance, when the number of ants is 1.8m, the TS-ACS-RST-FS approach gets 120% of reducts with respect to the number of reducts computed via ACS-RST-FS only in 52% of the time required by the latter one (for β = 5 and q0 = 0.9). Here we have set r = 0.3 because this value accomplishes the most encouraging results throughout several experimental studies. In the case of β = 1 and q0 = 3, the TS-ACS-RST-FS method reached the same number of reducts (99%) but only using 69% of the CPU time than its counterpart, the ACS-RST-FS model. Table 5: A comparison between ACS and several configurations of the two-step ACO approach using r = 0.3, N Cmax 1 = 6 and N Cmax 2 = 15 Algorithm

m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3

ACS (m = 16) TS-ACS (m = 16) TS-ACS (m0 = 1.33m = 21) TS-ACS (m0 = 1.5m = 24) TS-ACS (m0 = 1.8m = 29) TS-ACS (m0 = 2.1m = 34)

– 5 6 7 9 10

– 11 15 17 20 24

46.7/228 92%/23% 96%/31% 109%/38% 120%/52% 126%/66%

123/274 58%/23% 81%/37% 83%/42% 89%/55% 99%/69%

Table 6 sketches a similar study using the Breast Cancer database. These results are very interesting because the two-step ACO approach enables us to obtain the same or an even greater number of reducts in less time than ACSRST-FS, hence the feasibility of splitting the search process is empirically confirmed once again.

20

Rafael Bello et al.

Table 6: A comparison between ACS and several configurations of the two-step ACO approach using N Cmax1 = 6 and N Cmax2 = 15 Algorithm ACS (m = 9) TS-ACS (r = 0.2) TS-ACS (r = 0.3) TS-ACS (r = 0.36) TS-ACS (r = 0.5) TS-ACS (r = 0.6) TS-ACS (r = 0.8) TS-ACS (r = 0.3, m0 = 1.8m = 16) TS-ACS (r = 0.3, m0 = 2.1m = 19)

m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3 – 2 3 3 4 5 7 5 6

– 7 6 6 9 4 2 11 13

46.7/228 60%/34% 109%/31% 105%/25% 100%/22% 65%/13% 33%/27% 102%/58% 124%/67%

123/274 70%/49% 73%/37% 77%/31% 73%/26% 50%/20% 31%/26% 98%/74% 103%/83%

6 Dynamic Mesh Optimization in Feature Selection We want to elaborate now on a novel optimization technique called “Dynamic Mesh Optimization” (DMO) [5] which follows some patterns already present in earlier evolutionary approaches but provides a unique framework for managing both discrete and continuous optimization problems. The essentials behind the DMO method is the creation of a mesh of points in the multi-dimensional space wherein the optimization of the objective function is being carried out. The mesh endures an expansion process toward the most promising regions of the search space but, at the same time, becomes finer in those areas where there exist points that constitute local ends of the function. The dynamic nature of the mesh is given by the fact that its size (number of nodes) and configuration both change over time. When it comes to the feature selection problem, nodes can be visualized as binary vectors n = (n1 , n2 , . . . , nN ) of N components, one per attribute, with the component ni = 1 if the i-th attribute is being considered as part of the solution or zero otherwise. This is the same representation adopted in the previously discussed evolutionary approaches. At every cycle, the mesh is created with an initial number of nodes. Subsequently, new nodes are generated until an upper boundary in the number of nodes is reached. The mesh at the next cycle is comprised of the fittest nodes of the mesh in the current iteration. Along the search process, the node carrying the best value of the objective (evaluation) function so far is recorded, so ng denotes the global end attained up to now by the search algorithm. In the case of the feature selection problem, the evaluation (fitness) function for the DMO meta-heuristic is expression (11), which attempts to achieve a tradeoff between the classificatory ability of a reduct and its length. The dynamic nature of our proposal manifests in the generation of (i) the initial mesh; (ii) intermediate nodes oriented toward the local optima; (iii) intermediate nodes in the direction of the global optimum and (iv) nodes aiming at expanding the dimensions of the current mesh.

RST and Evolutionary Computation to Feature Selection

21

The model gives rise to the following parameters: (i) Ni → size of the initial mesh, (ii) N → maximum size of the mesh across each cycle (Ni < N ) and (iii) M → number of cycles. The DMO method is defined in the following manner: STEP 1. Generate the initial mesh for each cycle: At the beginning of the algorithm’s execution, the initial mesh will be made up of Ni randomly generated nodes while in the remaining iterations, the initial mesh is built upon the selection of the best (in terms of evaluation measure) Ni nodes of the mesh in the preceding cycle. STEP 2. Node generation toward local optima: The aim of this step is to come up with new nodes laid in the direction of the local optima found by the algorithm. For each node n, its K-nearest neighbor nodes are computed (the Hamming distance is a suitable option for the FSP). If none of the neighbors surpasses n in fitness function value, then n is said to be a local optimum and no nodes are begotten out of it in this step. Conversely, suppose that node ne is “better” than n and the rest of its neighbors. In this case, a new node arises somewhere between n and ne. The proximity of the newly generated node n∗ to the current node n or to the local optimum ne is contingent upon a factor r which is calculated based on the fitness function values at both nodes n and ne. Each component of n∗ takes either the value of ni or nei according to a rule involving a stochastic component. The threshold r determining how every component n∗i must be fixed is calculated as in (19). r = 1 − 0.5

Eval(n) Eval(ne)

(19)

f (n, ne, r) : For each component ni : If random() < r then n∗i = nei otherwise n∗i = ni Notice from (19) that the lower the ratio between Eval(n) and Eval(ne), the more likely it is that n∗i takes the value of the i-th component of the local optimum. STEP 3. Node generation toward global optimum: Here the idea is the same as in the previous step but now r is computed differently and a new function g is introduced. Needless to say that ng represents the global optimum found thus far by the algorithm. r = 1 − 0.5

Eval(n) Eval(ng)

(20)

g(n, ng, r) : For each component ni : If random() < r then n∗i = ngi otherwise n∗i = ni STEP 4. Mesh expansion: In this step, the mesh is stretched from its outer nodes using function h, i.e. using nodes located at the boundary of the initial

22

Rafael Bello et al.

mesh in each cycle. The weight w depicted in (13) assures that the expansion declines along the search process (i.e., a bigger expansion is achieved at the early cycles and it fades out as the algorithm progresses). To determine which nodes lie in the outskirts of the mesh, we turn to the norm of a vector. Those nodes exhibiting the lowest and greatest norm values are picked. Remark that, in this step, as many outer nodes as needed are selected so as to fill out the maximum mesh size N . The rules regulating this sort of node generation can be found next: For each node nl in the lower boundary (those with the lowest norm): h(nl, w) : For each component ni : If random() < w then n∗i = 0 otherwise n∗i = nli For each node nu in the upper boundary (those with the greatest norm): h(nu, w) : For each component ni : If random() < w then n∗i = 1 otherwise n∗i = nui In the context of feature selection, the norm of a node (vector) is the number of components set to one. Algorithm 6 outlines the workflow of the DMO approach. It is also worth remarking that no direct search algorithm guarantees to find the global optimum no matter how refined the heuristic search might be. Algorithm 6 The DMO meta-heuristic 1: procedure D(M)O 2: Randomly generate Ni nodes to build the initial mesh 3: Evaluate all the mesh nodes 4: repeat 5: for each node n in the mesh do 6: Find its K-nearest neighbors 7: nbest ← the best of its neighbors 8: if nbest is better than n then 9: Generate a new node by using function f 10: end if 11: end for 12: for each initial node in the current mesh do 13: Generate a new node by using function g 14: end for 15: repeat 16: Select the most outward node of the mesh 17: Generate a new node by using function h 18: until M eshSize = N 19: Select the best Ni nodes of the current mesh and set up the next mesh 20: until CurrentIteration = M 21: end procedure

RST and Evolutionary Computation to Feature Selection

23

7 A Comparative Study The conducted experimentation embraces a comparison between DMO and existing ACO- and PSO-based approaches. The chosen criteria were the number and length of the reducts found as well as the computational time required by every method. Concerning ACO, the Ant Colony System (ACS) model was picked for benchmarking following the advice in [1] and [2], for it reported the most encouraging outcomes. As to the parameter setting, we stuck to the guidelines provided in the aforesaid studies, i.e. β = 5, q0 = 0.9, N Cmax = 21 and the population size (number of ants) depending on the number of features as in the previously enunciated rules. Regarding the TS-ACS-RST-FS approach, the value of the ratio r used for determining the number of ants, number of cycles and threshold of the quality of the classification in each stage was set to 0.3 whereas the number of ants m is increased 2.1 times, i.e. m0 = 2.1m Moving on to the PSO-driven approaches’ configuration, each individual was shaped as a binary vector whose length matches the number of attributes in the system. The parameters associated with the PSO-RST-FS were fixed as c1 = c2 = 2, maxCycles = 120 and swarmSize = 21. The inertia weight w keeps its dynamic character as reflected in (13). As to the TS-PSO-RST-FS method, the factor used to calculate the quality of the classification in the first stage (ratioQ ) takes 0.75 while the parameter involved in the computation of the number of cycles (ratioC ) for each phase was set to 0.3. The configuration of the DMO-RST-FS (DMO + RST to feature selection) has been defined as follows: a mesh with 30 nodes is used, 9 of them regarded as initial nodes (which means that it is necessary to generate 21 nodes per cycle, just the same number of particles than in the PSO-based models) and the computations lasted for 90 iterations. Table 7 reports the experimental results obtained after applying the above methods over the Breast Cancer, Heart and Dermatology data sets coming from the UCI Repository. Each table entry holds the average number of reducts found, the average length (number of attributes) of the reducts in addition to the length of the shortest reduct and the number of times it was found with regards to the number of runs performed by the algorithm. Every algorithm was executed six times per data set. From the information in Table 7 we notice, for instance, that the DMO-RST-FS algorithm discovered 18.3 reducts on average for the Breast Cancer data set, the reducts having average length of 5.1 and the shortest reduct found is composed of four attributes, having a reduct of such length always (100%) been found throughout the different runs of the algorithm. From the outlook of the computational cost, one may notice that the DMORST-FS, TS-PSO-RST-FS and PSO-RST-FS algorithms have a very similar performance. This is clearly understood if we keep in mind that the greater the number of times expression (1) is computed, the more time-consuming

24

Rafael Bello et al.

Table 7: Quality of the reducts found by different evolutionary algorithms. First datum is the average number of reducts found, followed by their average length, the length of the shortest reduct and, finally, the percentage of times a reduct of the same length was found throughout the different executions of the algorithm. Method

BreastCancer

Heart

Dermatology

DMO-RST-FS TS-PSO-RST-FS PSO-RST-FS TS-ACS-RST-FS ACS-RST-FS

18.3/5.1/4,100% 11/4.6/4,100% 14/4.95/4,100% 12.7/4.74/4,100% 11.75/4.94/4,100%

14.8/8.29/6, 83% 3/6.8/6,100% 6/7.97/6,67% 7/7/6,67% 14.3/7.53/6,100%

179.5/20.9/9,50% 39.3/12.6/9, 50% 78.2/15.3/9, 50% 249/13/9,33% 300/14.17/10,66%

the algorithm turns into. While PSO-based and DMO approaches compute this indicator roughly P × Q times (P being the number of cycles and Q the number of agents engaged in the search process, viz particles in PSO and nodes in DMO), the ACO-based models evaluate this function a far greater number of times, i.e. roughly P × Q × k (Q being the number of ants and k the average length of the reducts found, since every time an ant adds a node to the solution, it must evaluate all possible alternatives at hand, namely, all attributes still not considered so far). Regarding the average amount of times the fitness function was calculated by all approaches under discussion, Table 8 presents the corresponding magnitudes. Table 8: Average number of evaluations of the fitness function in each algorithm Algorithm DMO-RST-FS TS-PSO-RST-FS PSO-RST-FS TS-ACS-RST-FS ACS-RST-FS

Avg. number of times 2530 2542 2968 17222 13487

8 Conclusions An study on the performance of several evolutionary techniques for tackling the feature selection problem has been outlined. The common denominator has been the pivotal role played by rough set theory in assessing the quality of a feature subset as a prospective reduct of the system under consideration.

RST and Evolutionary Computation to Feature Selection

25

Therefore this criterion has been successfully incorporated to the fitness function of all the studied algorithms and the preliminary results allow to confirm the feasibility and efficiency of this sort of techniques for attribute reduction. Moreover, the introduction of the two-step search paradigm for the swarm intelligence methods translated into a substantial reduction of the computational time needed to find the reducts of the information system. Under empirical evidence we can also conclude that the Dynamic Mesh Optimization approach explores the search space in a similar way to the algorithms based on the Ant Colony Optimization model but with a computational cost very close to that of Particle Swarm Optimization. Acknowledgment The authors would like to thanks VLIR (Vlaamse InterUniversitaire Raad, Flemish Interuniversity Council, Belgium) for supporting this work under the IUC Program VLIR-UCLV.

References 1. Bello R, Nowe A (2005) Using ACO and rough set theory to feature selection. In: WSEAS Trans. on Information Science and Applications 512–517 2. Bello R, Nowe A (2005) A model based on ant colony system and rough set theory to feature selection. In: Proc. of Genetic and Evolutionary Computation Conference (GECCO’05) 275–276 3. Bello R, Puris A, Nowe A, Mart´ınez Y, Garc´ıa M (2006) Two-step ant colony system to solve the feature selection problem. In: Mart´ınez-Trinidad JF, Carrasco JA, Kittler J (eds.) CIARP 2006. LNCS 4225. Springer, Heidelberg 4. Bello R, G´ omez Y, Now´e A, Garc´ıa M (2007) Two-step particle swarm optimization to solve the feature selection problem. In: Proc. of 7th Int’l Conf. on Intelligent Systems Design and Applications, 691–696. IEEE Computer Society, Washington DC 5. Bello R, Puris A, Falc´ on R (2008) Feature selection through dynamic mesh optimization. Accepted for oral presentation at the 13th Iberoamerican Congress on Pattern Recognition (CIARP 2008), Havana, Cuba 6. Blake CL, Merz CJ (1998) UCI repository of machine learning databases http://www.ics.uci.edu/∼mlearn/MLRepository.html. 7. Caballero, Y, Bello R (2006) Two new feature selection algorithms with rough sets theory. In: Bramer M (eds) Artificial Intelligence in Theory and Practice. Springer, Boston 8. Dash M, Liu H (2003) Consistency-based search in feature selection. Artificial Intelligence 151:155–176 9. Dorigo M, St¨ utzle T (2005) Ant colony optimization. Cambridge University Press, New York 10. Goldberg, DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Boston 11. Jensen R, Shen Q (2003) Finding rough set reducts with ant colony optimization. In: Proceedings of 6th Annual UK Workshop on Computational Intelligence, 15–22

26

Rafael Bello et al.

12. Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proc. of IEEE Int’l. Conf. on Neural Networks, 1942–1948. IEEE Service Center, Piscataway 13. Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm optimization algorithm. In: IEEE International Conference on Neural Networks, 4104–4108. 14. Komorowski J, Polkowski L, Skowron A (1999) Rough sets: a tutorial. In: Pal S, Skowron A (eds): Rough-Fuzzy Hybridization: A New Trend in DecisionMaking. Springer-Verlag, New York 15. Kudo M, Sklansky J (2000) Comparison of algorithms that select features for pattern classifiers. Pattern Recognition 33:25–41 naga P, Etxeberria R, Lozano JA, Pe˜ na JM (2000) Optimization in con16. Larra˜ tinuous domains by learning and simulation of Gaussian networks. In: Wu AS (ed) Proceedings of the 2000 Genetic and Evolutionary Computation Conference, 201–204 17. Mitchell TM (1997) Machine learning. McGraw Hill 18. M¨ uhlenbein H, Mahnig T, Ochoa A (1999) Schemata, distributions and graphical models on evolutionary optimization. Journal of Heuristics 5(2):215–247 19. Pawlak Z (1982) Rough sets. International Journal of Information & Computer Sciences 11:341–356 20. Piˆ nero P, Arco L, Garc´ıa M, Caballero Y (2003) Two new metrics for feature selection in pattern recognition. LNCS 2905, 488-497. Springer-Verlag, Berlin Heidelberg 21. Polkowski L (2002) Rough sets: mathematical foundations. Physica-Verlag, Berlin 22. Stefanowski J (2004) An experimental evaluation of improving rule-based classifiers with two approaches that change representations of learning examples. Engineering Applications of Artificial Intelligence 17:439–445 23. Tay FE, Shen L (2002) Economic and financial prediction using rough set model. European Journal of Operational Research 141:641–659 24. Wang X, Yang Y, Peng N, Teng X (2005) Finding minimal rough set reducts with particle swarm optimization. In: Slezak D, Yao J, Peters J, Ziarko W, Xiaohua H (eds): RsFsDGrC 2005. LNCS 3641, 451–460. Springer, Heidelberg 25. Wang X, Yang J, Jensen R, Liu X (2006) Rough set feature selection and rule induction for prediction of malignancy degree in brain glioma. Computer Methods and Programs in Biomedicine 83:147–156 26. Wang X, Yang J, Teng X, Xia W, Jensen R (2007) Feature selection based on rough sets and particle swarm optimization. Pattern Recognition Letters 28:459–471 27. Wroblewski, J (1995) Finding minimal reducts using genetic algorithms. In: Wang PP (ed) Proceedings of the 2nd Annual Joint Conference on Information Sciences, 186-189 28. Xing H, Xu L (2001) Feature space theory -a mathematical foundation for data mining. Knowledge-based systems 14:253-257 29. Xu ZB, Liang J, Dang C, Chin KS (2002) Inclusion degree: a perspective on measures for rough set data analysis. Information Sciences 141:227-236 30. Yuan S, Chu FL (2007) Fault diagnostics based on particle swarm optimization and support vector machines. Mechanical Systems and Signal Processing 21:1787–1798

2

3

Computer Science Department, Central University of Las Villas (UCLV) Carretera Camajuan´ı km 5.5, Santa Clara, Cuba {rbellop, ygomezd, rfalcon}@uclv.edu.cu Informatics Department, University of Camag¨ uey, Cuba [email protected] CoMo Lab, Computer Science Department, Vrije Universiteit Brussel, Belgium [email protected]

Summary. The feature selection problem has been usually addressed through heuristic approaches given its significant computational complexity. In this context, evolutionary techniques have drawn the researchers’ attention owing to their appealing optimization capabilities. In this chapter, promising results achieved by the authors in solving the feature selection problem through a joint effort between rough set theory and evolutionary computation techniques are reviewed. In particular, two new heuristic search algorithms are introduced, i.e. Dynamic Mesh Optimization and another approach which splits the search process carried out by swarm intelligence methods.

Key words: meta-heuristic, evolutionary computation, feature selection

1 Introduction The solution of a great deal of problems can be formulated as an optimization problem. The quest for the problem’s solution is often stated as finding the optimum of an objective function f : D → nf then assign the first m ants according to (2) and the remaining ones as in (1). The process of finding the candidate reduct sets B happens in a sequence of cycles N C = 1, 2, . . . In each cycle, all ants build their own set Bk . The process stop criterion is met (PSC = true) once the maximal number of cycles has been exceeded N C > N Cmax . Each ant k keeps adding one feature at a time to its current partial set Bk until γBk (Y ) = γA (Y ). This is known as the ant stopping criterion (ASCk =true). The population size is envisioned as a function of the number of features m = f (nf) where round(x) denotes the closest integer to x. R1 : If nf < 19 then m = nf R2 : If 20 ≤ nf ≤ 49 then if 2/3 nf ≤ 24 then m=24 else m=round(2/3 nf) R3 : If nf > 50 then if nf/2 ≤ 33 then m = 33 else m = round(nf/2) The above rules are the direct outcome of a thorough experimental analysis conducted with the purpose in mind of setting the population size on the basis of the number of features describing the data set. Now we are ready to present the ACS-RST-FS approach in a more formal way. Let us look at Algorithm 4. A new approach in Ant Colony Optimization for solving the feature selection problem was introduced in [3]. The two-step ACO algorithm is also based on the idea of splitting the process of finding reducts into two stages. The algorithm dynamically constructs candidate feature subsets during the first stage which shall be afterwards used as starting points for each ant’s

RST and Evolutionary Computation to Feature Selection

17

Algorithm 4 ACS-RST-FS 1: procedure ACS-RST-FS( ) 2: PSC ← false, NC ← 1 3: Calculate τi (0), i = 1, . . . ,nf (random initial values for trail intensity) 4: repeat 5: Each ant k is assigned to an attribute ai , ∀k ∈ {1, . . . , m} and B k ← {ai } 6: ASCk ← false ∀k ∈ {1, . . . , m} 7: repeat 8: for k ← 1 to m do 9: if ASCk = false then 10: Select new feature a∗i according to (1) 11: Bk = Bk ∪ {a∗i } 12: τi ← (1 − ξ) · τi + ξ · τi (0) . i is the index of a∗i 13: Update ASCk . Did ant k complete a reduct Bk ? 14: end if 15: end for 16: until ASCk = true ∀k ∈ {1, . . . , m} 17: Bk∗ ← best Bk . Now that all ants have finished, select the best reduct 18: for each ai ∈ Bk∗ do k 19: τi ← (1 − ρ) · τi + ρ · γB (Y ) . update global pheromone trail 20: end for 21: For each feature i do τi = nτi X τj j=1

22: NC ← NC + 1 23: Update PSC 24: until PSC = true 25: end procedure

own candidate feature subset in the second stage. The number of cycles, the number of ants and the desired quality of the subsets are degrees of freedom of the model related to each stage. We use the same ratio r that affects the three aforementioned parameters. For instance, suppose we are interested in carrying out 100 cycles as the overall algorithm’s execution and we will use 30 ants for generating Bk subsets with the maximum possible quality of classification (N Cmax = 100, m = 30, γB (Y ) = 1). Setting r = 0.3 means that the first stage will last only 30 iterations, involving 9 ants and will settle for reducts whose quality would be 0.3 or above. Being this so, the values of these parameters during the second phase will be N Cmax = 70, m = 21 and the algorithm will look for subsets with the maximum possible quality of classification. The workflow of activities of the TS-ACS-RST-FS proposed approach is depicted in Algorithm 5. Of course, any other alternative ACO-based implementation can be used rather than the ACS-RST-FS algorithm. An important issue in this approach is to study which is the most suitable value for ratio r. High values of r (near to 1) cause the two-step algorithm to obtain candidate subsets close to the

18

Rafael Bello et al.

Algorithm 5 TS-ACS-RST-FS procedure TS-ACS-RST-FS( ) Compute the population size (m) on the basis of the number of features (nf) Compute the quality of classification using (1) and B = A STAGE 1 Calculate parameter values in the first stage as follows: N Cmax1 = r · N Cmax , m1 = r · m, γB 1 (Y ) = r · γB (Y ) Run the ACS-RST-FS approach CS ← output of ACS-RST-FS . CS holds the candidate reducts STAGE 2 Calculate parameter values in the second stage as follows: N Cmax2 = N Cmax − N Cmax1 , m2 = m − m1 , γB 2 (Y ) = γB (Y ) Run the ACS-RST-FS approach but assign in each cycle a random subset from CS as initial subset for each ant end procedure

definition of reducts in the first stage, therefore ants in the second step swiftly find reducts but using very limited iterations and a scarce number of search agents (ants). On the contrary, if the ratio value is low, the quality of the candidate feature subsets computed during the first stage is poor yet there are more ants to work for a larger number of cycles in the second stage. We have developed an experimental study which is concerned with this tradeoff. The following values for the ratio parameter have been proposed r ∈ {0.2, 0.3, 0.36, 0.5, 0.6, 0.8} and the impact of each of these values over the number of reducts obtained, their length as well as the computational time needed to produce the output has been observed. Table 4 reports the average results achieved after 20 iterations. A synthetic repository comprised of 20 objects which are described by 16 features provides the data for conducting the experiments. The maximum number of cycles is 21. Table 4: Results obtained with the proposed ACO-based approaches. The last two columns portray the average number of reducts, the average length of the reducts and the computational time (in seconds), these three indicators separated by backslash. Algorithm ACS TS-ACS TS-ACS TS-ACS TS-ACS TS-ACS TS-ACS

r r r r r r

N Cmax 1 N Cmax 2 m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3 = 0.2 = 0.3 = 0.36 = 0.5 = 0.6 = 0.8

– 4 6 8 10 13 17

– 17 15 13 11 8 4

– – 46.7/3.95/228 3 13 32.7/4.2/82 5 11 43.3/4.1/53 6 10 38.7/3.9/39 8 8 29.7/3.8/32 10 6 20.33/3.8/41 13 3 9/3.8/82

123/4.19/274 76.3/4.2/89.9 71.3/4.2/64 67.3/4.1/47 43.3/4.1/44 37/4.2/49 10.67/4.2/97

RST and Evolutionary Computation to Feature Selection

19

We can see that r = 0.3 bears the best results. This setting implies a number of reducts similar to ACS-RST-FS but only in the 23% of the time. Similar results can be witnessed across other data sets. For instance, in Table 5 we display the results using the Breast Cancer database from UCI Repository. The result here is not surprising, since the value r = 0.3 provides a good balance between both stages; a higher number of ants and cycles in the second stage allows the algorithms to perform a larger exploration of the search space departing from initial subsets with an acceptable quality. Another point worthwhile stressing is that the time complexity of TS-ACSRST-FS is very low. In light of this, we propose a second idea: to increase the number of ants in order to bring about a greater exploration of the search space. In Table 6 the same data set than in Table 4 was used but now the population size is increased by the factors 1.33, 1.5, 1.8 and 2.1, respectively. In columns 4 and 5 the relationship between each alternative and the ACSRST-FS benchmark algorithm is reported in terms of the amount of reducts achieved and the computational time needed. For instance, when the number of ants is 1.8m, the TS-ACS-RST-FS approach gets 120% of reducts with respect to the number of reducts computed via ACS-RST-FS only in 52% of the time required by the latter one (for β = 5 and q0 = 0.9). Here we have set r = 0.3 because this value accomplishes the most encouraging results throughout several experimental studies. In the case of β = 1 and q0 = 3, the TS-ACS-RST-FS method reached the same number of reducts (99%) but only using 69% of the CPU time than its counterpart, the ACS-RST-FS model. Table 5: A comparison between ACS and several configurations of the two-step ACO approach using r = 0.3, N Cmax 1 = 6 and N Cmax 2 = 15 Algorithm

m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3

ACS (m = 16) TS-ACS (m = 16) TS-ACS (m0 = 1.33m = 21) TS-ACS (m0 = 1.5m = 24) TS-ACS (m0 = 1.8m = 29) TS-ACS (m0 = 2.1m = 34)

– 5 6 7 9 10

– 11 15 17 20 24

46.7/228 92%/23% 96%/31% 109%/38% 120%/52% 126%/66%

123/274 58%/23% 81%/37% 83%/42% 89%/55% 99%/69%

Table 6 sketches a similar study using the Breast Cancer database. These results are very interesting because the two-step ACO approach enables us to obtain the same or an even greater number of reducts in less time than ACSRST-FS, hence the feasibility of splitting the search process is empirically confirmed once again.

20

Rafael Bello et al.

Table 6: A comparison between ACS and several configurations of the two-step ACO approach using N Cmax1 = 6 and N Cmax2 = 15 Algorithm ACS (m = 9) TS-ACS (r = 0.2) TS-ACS (r = 0.3) TS-ACS (r = 0.36) TS-ACS (r = 0.5) TS-ACS (r = 0.6) TS-ACS (r = 0.8) TS-ACS (r = 0.3, m0 = 1.8m = 16) TS-ACS (r = 0.3, m0 = 2.1m = 19)

m1 m2 β = 5, q0 = 0.9 β = 1, q0 = 0.3 – 2 3 3 4 5 7 5 6

– 7 6 6 9 4 2 11 13

46.7/228 60%/34% 109%/31% 105%/25% 100%/22% 65%/13% 33%/27% 102%/58% 124%/67%

123/274 70%/49% 73%/37% 77%/31% 73%/26% 50%/20% 31%/26% 98%/74% 103%/83%

6 Dynamic Mesh Optimization in Feature Selection We want to elaborate now on a novel optimization technique called “Dynamic Mesh Optimization” (DMO) [5] which follows some patterns already present in earlier evolutionary approaches but provides a unique framework for managing both discrete and continuous optimization problems. The essentials behind the DMO method is the creation of a mesh of points in the multi-dimensional space wherein the optimization of the objective function is being carried out. The mesh endures an expansion process toward the most promising regions of the search space but, at the same time, becomes finer in those areas where there exist points that constitute local ends of the function. The dynamic nature of the mesh is given by the fact that its size (number of nodes) and configuration both change over time. When it comes to the feature selection problem, nodes can be visualized as binary vectors n = (n1 , n2 , . . . , nN ) of N components, one per attribute, with the component ni = 1 if the i-th attribute is being considered as part of the solution or zero otherwise. This is the same representation adopted in the previously discussed evolutionary approaches. At every cycle, the mesh is created with an initial number of nodes. Subsequently, new nodes are generated until an upper boundary in the number of nodes is reached. The mesh at the next cycle is comprised of the fittest nodes of the mesh in the current iteration. Along the search process, the node carrying the best value of the objective (evaluation) function so far is recorded, so ng denotes the global end attained up to now by the search algorithm. In the case of the feature selection problem, the evaluation (fitness) function for the DMO meta-heuristic is expression (11), which attempts to achieve a tradeoff between the classificatory ability of a reduct and its length. The dynamic nature of our proposal manifests in the generation of (i) the initial mesh; (ii) intermediate nodes oriented toward the local optima; (iii) intermediate nodes in the direction of the global optimum and (iv) nodes aiming at expanding the dimensions of the current mesh.

RST and Evolutionary Computation to Feature Selection

21

The model gives rise to the following parameters: (i) Ni → size of the initial mesh, (ii) N → maximum size of the mesh across each cycle (Ni < N ) and (iii) M → number of cycles. The DMO method is defined in the following manner: STEP 1. Generate the initial mesh for each cycle: At the beginning of the algorithm’s execution, the initial mesh will be made up of Ni randomly generated nodes while in the remaining iterations, the initial mesh is built upon the selection of the best (in terms of evaluation measure) Ni nodes of the mesh in the preceding cycle. STEP 2. Node generation toward local optima: The aim of this step is to come up with new nodes laid in the direction of the local optima found by the algorithm. For each node n, its K-nearest neighbor nodes are computed (the Hamming distance is a suitable option for the FSP). If none of the neighbors surpasses n in fitness function value, then n is said to be a local optimum and no nodes are begotten out of it in this step. Conversely, suppose that node ne is “better” than n and the rest of its neighbors. In this case, a new node arises somewhere between n and ne. The proximity of the newly generated node n∗ to the current node n or to the local optimum ne is contingent upon a factor r which is calculated based on the fitness function values at both nodes n and ne. Each component of n∗ takes either the value of ni or nei according to a rule involving a stochastic component. The threshold r determining how every component n∗i must be fixed is calculated as in (19). r = 1 − 0.5

Eval(n) Eval(ne)

(19)

f (n, ne, r) : For each component ni : If random() < r then n∗i = nei otherwise n∗i = ni Notice from (19) that the lower the ratio between Eval(n) and Eval(ne), the more likely it is that n∗i takes the value of the i-th component of the local optimum. STEP 3. Node generation toward global optimum: Here the idea is the same as in the previous step but now r is computed differently and a new function g is introduced. Needless to say that ng represents the global optimum found thus far by the algorithm. r = 1 − 0.5

Eval(n) Eval(ng)

(20)

g(n, ng, r) : For each component ni : If random() < r then n∗i = ngi otherwise n∗i = ni STEP 4. Mesh expansion: In this step, the mesh is stretched from its outer nodes using function h, i.e. using nodes located at the boundary of the initial

22

Rafael Bello et al.

mesh in each cycle. The weight w depicted in (13) assures that the expansion declines along the search process (i.e., a bigger expansion is achieved at the early cycles and it fades out as the algorithm progresses). To determine which nodes lie in the outskirts of the mesh, we turn to the norm of a vector. Those nodes exhibiting the lowest and greatest norm values are picked. Remark that, in this step, as many outer nodes as needed are selected so as to fill out the maximum mesh size N . The rules regulating this sort of node generation can be found next: For each node nl in the lower boundary (those with the lowest norm): h(nl, w) : For each component ni : If random() < w then n∗i = 0 otherwise n∗i = nli For each node nu in the upper boundary (those with the greatest norm): h(nu, w) : For each component ni : If random() < w then n∗i = 1 otherwise n∗i = nui In the context of feature selection, the norm of a node (vector) is the number of components set to one. Algorithm 6 outlines the workflow of the DMO approach. It is also worth remarking that no direct search algorithm guarantees to find the global optimum no matter how refined the heuristic search might be. Algorithm 6 The DMO meta-heuristic 1: procedure D(M)O 2: Randomly generate Ni nodes to build the initial mesh 3: Evaluate all the mesh nodes 4: repeat 5: for each node n in the mesh do 6: Find its K-nearest neighbors 7: nbest ← the best of its neighbors 8: if nbest is better than n then 9: Generate a new node by using function f 10: end if 11: end for 12: for each initial node in the current mesh do 13: Generate a new node by using function g 14: end for 15: repeat 16: Select the most outward node of the mesh 17: Generate a new node by using function h 18: until M eshSize = N 19: Select the best Ni nodes of the current mesh and set up the next mesh 20: until CurrentIteration = M 21: end procedure

RST and Evolutionary Computation to Feature Selection

23

7 A Comparative Study The conducted experimentation embraces a comparison between DMO and existing ACO- and PSO-based approaches. The chosen criteria were the number and length of the reducts found as well as the computational time required by every method. Concerning ACO, the Ant Colony System (ACS) model was picked for benchmarking following the advice in [1] and [2], for it reported the most encouraging outcomes. As to the parameter setting, we stuck to the guidelines provided in the aforesaid studies, i.e. β = 5, q0 = 0.9, N Cmax = 21 and the population size (number of ants) depending on the number of features as in the previously enunciated rules. Regarding the TS-ACS-RST-FS approach, the value of the ratio r used for determining the number of ants, number of cycles and threshold of the quality of the classification in each stage was set to 0.3 whereas the number of ants m is increased 2.1 times, i.e. m0 = 2.1m Moving on to the PSO-driven approaches’ configuration, each individual was shaped as a binary vector whose length matches the number of attributes in the system. The parameters associated with the PSO-RST-FS were fixed as c1 = c2 = 2, maxCycles = 120 and swarmSize = 21. The inertia weight w keeps its dynamic character as reflected in (13). As to the TS-PSO-RST-FS method, the factor used to calculate the quality of the classification in the first stage (ratioQ ) takes 0.75 while the parameter involved in the computation of the number of cycles (ratioC ) for each phase was set to 0.3. The configuration of the DMO-RST-FS (DMO + RST to feature selection) has been defined as follows: a mesh with 30 nodes is used, 9 of them regarded as initial nodes (which means that it is necessary to generate 21 nodes per cycle, just the same number of particles than in the PSO-based models) and the computations lasted for 90 iterations. Table 7 reports the experimental results obtained after applying the above methods over the Breast Cancer, Heart and Dermatology data sets coming from the UCI Repository. Each table entry holds the average number of reducts found, the average length (number of attributes) of the reducts in addition to the length of the shortest reduct and the number of times it was found with regards to the number of runs performed by the algorithm. Every algorithm was executed six times per data set. From the information in Table 7 we notice, for instance, that the DMO-RST-FS algorithm discovered 18.3 reducts on average for the Breast Cancer data set, the reducts having average length of 5.1 and the shortest reduct found is composed of four attributes, having a reduct of such length always (100%) been found throughout the different runs of the algorithm. From the outlook of the computational cost, one may notice that the DMORST-FS, TS-PSO-RST-FS and PSO-RST-FS algorithms have a very similar performance. This is clearly understood if we keep in mind that the greater the number of times expression (1) is computed, the more time-consuming

24

Rafael Bello et al.

Table 7: Quality of the reducts found by different evolutionary algorithms. First datum is the average number of reducts found, followed by their average length, the length of the shortest reduct and, finally, the percentage of times a reduct of the same length was found throughout the different executions of the algorithm. Method

BreastCancer

Heart

Dermatology

DMO-RST-FS TS-PSO-RST-FS PSO-RST-FS TS-ACS-RST-FS ACS-RST-FS

18.3/5.1/4,100% 11/4.6/4,100% 14/4.95/4,100% 12.7/4.74/4,100% 11.75/4.94/4,100%

14.8/8.29/6, 83% 3/6.8/6,100% 6/7.97/6,67% 7/7/6,67% 14.3/7.53/6,100%

179.5/20.9/9,50% 39.3/12.6/9, 50% 78.2/15.3/9, 50% 249/13/9,33% 300/14.17/10,66%

the algorithm turns into. While PSO-based and DMO approaches compute this indicator roughly P × Q times (P being the number of cycles and Q the number of agents engaged in the search process, viz particles in PSO and nodes in DMO), the ACO-based models evaluate this function a far greater number of times, i.e. roughly P × Q × k (Q being the number of ants and k the average length of the reducts found, since every time an ant adds a node to the solution, it must evaluate all possible alternatives at hand, namely, all attributes still not considered so far). Regarding the average amount of times the fitness function was calculated by all approaches under discussion, Table 8 presents the corresponding magnitudes. Table 8: Average number of evaluations of the fitness function in each algorithm Algorithm DMO-RST-FS TS-PSO-RST-FS PSO-RST-FS TS-ACS-RST-FS ACS-RST-FS

Avg. number of times 2530 2542 2968 17222 13487

8 Conclusions An study on the performance of several evolutionary techniques for tackling the feature selection problem has been outlined. The common denominator has been the pivotal role played by rough set theory in assessing the quality of a feature subset as a prospective reduct of the system under consideration.

RST and Evolutionary Computation to Feature Selection

25

Therefore this criterion has been successfully incorporated to the fitness function of all the studied algorithms and the preliminary results allow to confirm the feasibility and efficiency of this sort of techniques for attribute reduction. Moreover, the introduction of the two-step search paradigm for the swarm intelligence methods translated into a substantial reduction of the computational time needed to find the reducts of the information system. Under empirical evidence we can also conclude that the Dynamic Mesh Optimization approach explores the search space in a similar way to the algorithms based on the Ant Colony Optimization model but with a computational cost very close to that of Particle Swarm Optimization. Acknowledgment The authors would like to thanks VLIR (Vlaamse InterUniversitaire Raad, Flemish Interuniversity Council, Belgium) for supporting this work under the IUC Program VLIR-UCLV.

References 1. Bello R, Nowe A (2005) Using ACO and rough set theory to feature selection. In: WSEAS Trans. on Information Science and Applications 512–517 2. Bello R, Nowe A (2005) A model based on ant colony system and rough set theory to feature selection. In: Proc. of Genetic and Evolutionary Computation Conference (GECCO’05) 275–276 3. Bello R, Puris A, Nowe A, Mart´ınez Y, Garc´ıa M (2006) Two-step ant colony system to solve the feature selection problem. In: Mart´ınez-Trinidad JF, Carrasco JA, Kittler J (eds.) CIARP 2006. LNCS 4225. Springer, Heidelberg 4. Bello R, G´ omez Y, Now´e A, Garc´ıa M (2007) Two-step particle swarm optimization to solve the feature selection problem. In: Proc. of 7th Int’l Conf. on Intelligent Systems Design and Applications, 691–696. IEEE Computer Society, Washington DC 5. Bello R, Puris A, Falc´ on R (2008) Feature selection through dynamic mesh optimization. Accepted for oral presentation at the 13th Iberoamerican Congress on Pattern Recognition (CIARP 2008), Havana, Cuba 6. Blake CL, Merz CJ (1998) UCI repository of machine learning databases http://www.ics.uci.edu/∼mlearn/MLRepository.html. 7. Caballero, Y, Bello R (2006) Two new feature selection algorithms with rough sets theory. In: Bramer M (eds) Artificial Intelligence in Theory and Practice. Springer, Boston 8. Dash M, Liu H (2003) Consistency-based search in feature selection. Artificial Intelligence 151:155–176 9. Dorigo M, St¨ utzle T (2005) Ant colony optimization. Cambridge University Press, New York 10. Goldberg, DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Boston 11. Jensen R, Shen Q (2003) Finding rough set reducts with ant colony optimization. In: Proceedings of 6th Annual UK Workshop on Computational Intelligence, 15–22

26

Rafael Bello et al.

12. Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proc. of IEEE Int’l. Conf. on Neural Networks, 1942–1948. IEEE Service Center, Piscataway 13. Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm optimization algorithm. In: IEEE International Conference on Neural Networks, 4104–4108. 14. Komorowski J, Polkowski L, Skowron A (1999) Rough sets: a tutorial. In: Pal S, Skowron A (eds): Rough-Fuzzy Hybridization: A New Trend in DecisionMaking. Springer-Verlag, New York 15. Kudo M, Sklansky J (2000) Comparison of algorithms that select features for pattern classifiers. Pattern Recognition 33:25–41 naga P, Etxeberria R, Lozano JA, Pe˜ na JM (2000) Optimization in con16. Larra˜ tinuous domains by learning and simulation of Gaussian networks. In: Wu AS (ed) Proceedings of the 2000 Genetic and Evolutionary Computation Conference, 201–204 17. Mitchell TM (1997) Machine learning. McGraw Hill 18. M¨ uhlenbein H, Mahnig T, Ochoa A (1999) Schemata, distributions and graphical models on evolutionary optimization. Journal of Heuristics 5(2):215–247 19. Pawlak Z (1982) Rough sets. International Journal of Information & Computer Sciences 11:341–356 20. Piˆ nero P, Arco L, Garc´ıa M, Caballero Y (2003) Two new metrics for feature selection in pattern recognition. LNCS 2905, 488-497. Springer-Verlag, Berlin Heidelberg 21. Polkowski L (2002) Rough sets: mathematical foundations. Physica-Verlag, Berlin 22. Stefanowski J (2004) An experimental evaluation of improving rule-based classifiers with two approaches that change representations of learning examples. Engineering Applications of Artificial Intelligence 17:439–445 23. Tay FE, Shen L (2002) Economic and financial prediction using rough set model. European Journal of Operational Research 141:641–659 24. Wang X, Yang Y, Peng N, Teng X (2005) Finding minimal rough set reducts with particle swarm optimization. In: Slezak D, Yao J, Peters J, Ziarko W, Xiaohua H (eds): RsFsDGrC 2005. LNCS 3641, 451–460. Springer, Heidelberg 25. Wang X, Yang J, Jensen R, Liu X (2006) Rough set feature selection and rule induction for prediction of malignancy degree in brain glioma. Computer Methods and Programs in Biomedicine 83:147–156 26. Wang X, Yang J, Teng X, Xia W, Jensen R (2007) Feature selection based on rough sets and particle swarm optimization. Pattern Recognition Letters 28:459–471 27. Wroblewski, J (1995) Finding minimal reducts using genetic algorithms. In: Wang PP (ed) Proceedings of the 2nd Annual Joint Conference on Information Sciences, 186-189 28. Xing H, Xu L (2001) Feature space theory -a mathematical foundation for data mining. Knowledge-based systems 14:253-257 29. Xu ZB, Liang J, Dang C, Chin KS (2002) Inclusion degree: a perspective on measures for rough set data analysis. Information Sciences 141:227-236 30. Yuan S, Chu FL (2007) Fault diagnostics based on particle swarm optimization and support vector machines. Mechanical Systems and Signal Processing 21:1787–1798