Learning Decision Rules by Means of Hybrid-Encoded Evolutionary Algorithms

Summary. HI DE R 12.1 Introduction 12 Learning Decision Rules by Means of Hybrid-Encoded Evolutionary Algorithms This paper describes an approach based on evolutionary algorithms, HIDER ( erarchical cision ules), for learning rules in continuous and discrete domains. The algorithm produces a hierarchical set of rules, that is, the rules are sequentially obtained and must be therefore tried in order until one is found whose conditions are satised. In addition, the algorithm tries to obtain more understandable rules by minimizing the number of attributes involved. The evolutionary algorithm uses binary coding for discrete attributes and integer coding for continuous attributes. The integer coding consists in dening indexes to the values that have greater probability of being used as boundaries in the conditions of the rules. Thus, the individuals handles these indexes instead of the real values. We have tested our system on real data from the UCI Repository, and the results of a 10-fold cross-validation are compared to C4.5s and C4.5Rules. The experiments show that HIDER works well in practice. J.C. Riquelme and J.S. Aguilar-Ruiz Evolutionary Algorithms (EA) are a family of computational models inspired by the concept of evolution. These algorithms employ a randomized search method to nd solutions to a particular problem [25]. This search is quite different from the other learning methods mentioned above. An EA is any population-based model that uses selection and recombination operators to generate new sample examples in a search space [22]. EAs have been used in a wide variety of optimization tasks [13] including numerical optimization and combinatorial optimization problems, although the range of problems to which EAs have been applied is quite broad. The main task in applying EAs to any problem consists of selecting an appropriate representation (coding) and an adequate evaluation function (tness). Genetic-based searching algorithms for supervised learning, as GABIL [7] or GIL [11], do not handle easily numeric attributes because the method of encoding all possible values would lead to very long rules in the case or 12.2 Motivation generalization pure Figure 12.1. Figure 12.2. 160 J.C. Riquelme, J.S. Aguilar-Ruiz C4.5. HIDER. real-valued attributes. Concretely, GABIL and GIL are so-called concept learners because they are designed for discrete domains. Other approaches, as SIA [19], have been motivated by a real-world data analysis task in a complex domain (continuous and discrete attributes). The aim of our research was to obtain a set of rules by means of an evolutionary algorithm to classify new examples in the context of supervised learning. With our approach, HIDER, we try to handle efficiently continuous and discrete attributes. The justication of this method will be discussed in Section 12.2. The characteristics of our approach are presented in section 12.3, where the coding, the algorithm, the selected tness function, and a particular aspect named , are detailed. Section 12.4 shows the experiments, the results and the analysis of them. In Section 12.5 the conclusions are summarized, some of which motivates the future works presented in Section 15.7. Two articial twodimensional databases will be used to clarify the motivation of our approach. The way in which C4.5 splits the space is depicted in Figure 12.1. The gures within the circles describe the level on the tree where the tests (nodes) over these attributes are placed. See the region labeled as B on the bottom left corner of Figure 12.1. C4.5 divides the region into two parts, however, we thought that the region should be completely covered by only one rule. This fact motivates us to design an algorithm able to discover such rule. HIDER is quite different because it does not divide the space by an attribute, but it extracts sequentially regions from the space. This permits us to obtain regions, i.e., all examples belong to the same category. As illustrated in Figure 12.2, the region labeled as B on the bottom left corner is discovered by HIDER. (1) i ii i i i a lu R i 12.3 HIDER decision list Figure 12.3. Figure 12.4. 12 Learning Decision Rules with Hybrid-Encoded EAs 161 C4.5 HIDER For another articial twodimensional database, Figure 12.3 shows the classication that C4.5 gives. Nevertheless, the quality of the rule set would be improved if the algorithm nds rules within others. The most evident feature, graphically observed in Figure 12.4, is the reduction of the number of rules because of the rules overlapping. This characteristic motivates us to use hierarchical decision rules instead of independent (unordered) decision rules. In short, the obtaining of larger regions (without damaging the prediction accuracy) and the discovery of regions within others are the two main goals that have motivated the development of HIDER. HIDER (HIerarchical DEcision Rules) uses an EA to search for the best solutions and produces a hierarchical set of rules. According to the hierarchy, an example will be classied by the th rule if it does not match the conditions of the th preceding rules. The rules are obtained sequentially until the space is totally covered. The behavior is similar to a [17]. As mentioned in [6], the meaning of any single rule is dependent on all the other rules that precede it in the rule list, so that it might be a problem for the expert in understanding the rules (if there are many). When we want to learn rules in the context of continuous attributes, we need to extend the concept of decision list in two ways: rst, for adapting the Boolean functions to interval functions; and second, for representing many classes instead of the true and false values (positives and negatives examples). For each continuous (real) attribute we obtain the boundaries values, called and (lower and upper bounds, respectively), which dene the space (range of the attribute ). These intervals allow us to include continuous attributes in a decision list. Our decision list does not have the last constant function true. However, we could interpret the last function as an unknown 12.3.1 Coding if then else if then else if then else Figure 12.5. coding tness function selected recombined offspring 162 J.C. Riquelme, J.S. Aguilar-Ruiz conditions class conditions class conditions class ............................................... unknown class Hierarchical set of rules. function, that is, we do not know which class the example belongs to. Therefore, it may be advisable to say unknown class instead of making an erroneous decision. From the viewpoint of the experiments, when no induced rules are satised, unknown class will be considered as an error. The structure of the set of rules will be as shown in Figure 12.5. As mentioned in [8] one of the primary motivation for using real-coded EAs is the precision with which attribute values can be represented and another is the ability to exploit the continuous nature of functions of continuous attributes. We implemented our rst versions with binary-coded GAs, but we realized that real-coded EAs were more efficient (time and quality of results). Before an EA can be run, a suitable for the problem must be devised. We also require a , which assigns a gure of merit to each coded solution. During the run, parents are for reproduction and to generate . These aspects are described below. In order to apply EAs to a learning problem, we need to select an internal representation of the space to be searched. These components are critical for the successful application of the EAs to the problem of interest. Information on the environment comes from a data le, where each example has a class and a number of attributes. We have to codify that information to dene the search space, which normally will be dimensionally greater. Each attribute will be formed by several components in the search space, depending on the specic representation. To nd out an appropriate coding for the problem is very difficult, but it is almost impossible to get the perfect one. There exist two basic principles for choosing the coding: the principle of meaningful building blocks and the principle of minimal alphabets [25]. In our rst approaches, we studied other EA-based classiers [7, 11] with binary coding. These are generally used as concept learners, where coding assigns a bit to each value of the attribute, i.e., every attribute is symbolic (GABIL and GIL are two well-known systems). For example, an attribute with three possible values would be represented by three bits. A value of one in a bit indicates that the value of the attribute is present so that several bits could be active for the same attribute. This coding is appropriate for symbolic ii i i ii k lu  i error  error lu b Figure 12.6. Figure 12.7. 12 Learning Decision Rules with Hybrid-Encoded EAs 163 Continuous (left) and discrete (right) attributes. Example of coding. domains. However, it is very difficult to use it in continuous domains, because the number of elements in the alphabet is very large, prohibiting a complete search. Using binary encoding in continuous domains requires transformations from binary to real for every attribute in order to apply the evaluation function. Moreover, when we convert binary into real, the precision is being lost, so that we have to nd the exact number of bits to eliminate the difference between any two values of an attribute. This ensures that a mutation of the less signicant bit of an attribute should include or exclude at least one example from the training set. Let and be the lower and upper bounds of an attribute. Let be the least absolute difference between any two values of the attribute . The allowed for this attribute must be less than . Thus, the length of an attribute will depend on that . Nevertheless, the real coding is more appropriate with real domains, simply because it is more natural to the domain. A number of authors have investigated nonbinary evolutionary algorithms theoretically [3, 4, 12, 20, 21]. The representation for continuous and discrete attributes is best explained by referring to Figure 12.6, where and are values representing an interval for the continuous attribute; are binary values indicating that the value of the discrete attribute is active or not. A last value (omitted in the gure) is for the class. For example, for a database with two attributes, one continuous and one discrete, an individual of the population could be as that depicted in Figure 12.7.  1 12 ii ii   {}    ||    12.3.2 Algorithm ii ii i r ii ii im iul Niul N examples pruning factor 01234 = min( ) = max( ) [] [] [] ([ ]) () + 164 J.C. Riquelme, J.S. Aguilar-Ruiz ,,,, la ua a ,v v, v , , R RE n E E r epf epf epf lu iul a ,...,a,...,a ,class ...,a  ,a  ,...,class The number of classes determines the set of values to which it belongs, i.e., if there are ve classes, the value will belong to the set . Each rule will be obtained from this representation, but when or , where is an attribute, the rule will not have that value. For example, in the rst case the rule would be and in the second case , being any value within the range of the attribute (see Figure 12.7). If both values are equal to the boundaries, then the rule arises for that attribute, which means that it is not relevant because either of the attributes values will be covered by the whole range of that attribute . Under these assumptions, some attributes might not appear in the set of rules. In the same way, when every discrete value is active, that attribute does not appear in the rule. The algorithm is a typical sequential covering EA [14]. It chooses the best individual of the evolutionary process, transforming it into a rule used to eliminate data from the training le [19]. In this way, the training le is reduced for the following iteration. HIDER searches for only one rule among the possible solutions, that compared to the algorithms based on the Michigan and Pittsburgh approaches, reduces the search space, even if several searches must be performed if several rules are to be learned. An overview of HIDER is shown in Figure 12.8. The algorithm is divided in two parts: the procedure HIDER, which constructs the hierarchical set of rules, and the function EvoAlg, which obtains one rule every time is called. Initially, the set of rules is empty, but in each iteration a rule is included (operator ) in ; is the training le, and is the number of remainder examples that have not been covered yet (exactly at the begining). In each iteration the training le is reduced (operator ), eliminating those examples that have been covered by the description of the rule ( ), i.e., the left-hand side of the rule, independently of its class. A parameter , called , controls the number of examples that will not be covered during the process (ranging from 0% to 5%). This factor ensures that rules covering few examples are not generated. Some authors have pointed out that these rules are undesirable, especially with noise in the domain [6, 10]. The termination criterion is reached when more examples to cover do not exist, depending on . For the trials, we have set to 0. The evolutionary algorithm is run each time to discover one rule. The method of generating the initial population (Initialize) consists of randomly selecting an example from the training le for each individual of the population. Afterwards, an interval to which the example belongs is obtained. For example, in one dimension, let and be the lower and upper bounds of the attribute ; then, the range of the attribute is ; next, we randomly choose an example from the training le; could be an individual of the N C 12    0 0 1 1 1 r i i ii i i i ∅ || ||  { } { ∈ |  } ∈{ | |} := := := := := := 0 := := + 1 1 := := +  [0 ] =(76 0) =(5882100100) [5 8 8 2] (1 0 0 1 0) =1  ,N C class e .,blue, ind .,.,,,,,, .,. ,,,, blue white j ER R nE E > n epf rE RRr EEeEe E i P P,i i < num generations ii j ,..., P xP,i,j P P x, P , i, j P,i P Procedure while end while end Function while for end for end while return end Figure 12.8. 12 Learning Decision Rules with Hybrid-Encoded EAs 165 HIDER( , ) EvoAlg( ) HIDER EvoAlg( ) Initialize() Evaluation( ) Selection( ) Recombination( ) Evaluation( ) best_of( ) EvoAlg Pseudocode of HIDER. population where and are random values belonging to ( is the size of the training data; is the number of different classes; and is the same of the example). For discrete attributes, we ensure that the individual has the same active value as the example. The remainder binary values are randomly set to 0 or 1. For example, let the database be the one used in the Figure 12.7. A possible individual for the initial population is obtained from a randomly selected example . The individual could be . The interval is for the continuous attribute and the values is for the discrete one. Notice that the value is active and other value ( ) has been randomly set to 1. The individual keeps the same class that of the example. Sometimes, the examples very near to the boundaries are hard to cover during the evolutionary process. To solve this problem, the search space is increased (currently, the lower bound is decreased by 5%, and the upper bound is increased by 5%), for continuous attributes. The evolutionary module incorporates elitism: the best individual of every generation is replicated to the next one ( , see in Figure 12.8 the loop i i 1 1   || ||  ||  ∈ ∈ Crossover 2 21 12 3 211 221 213 22 Figure 12.9. Figure 12.10. P Pi j i j ik ik i j i k i j i k i j i k i j i k i =2 = =+1= + 01 01 00 [] [] [] [( ) ( )] [( ) ( )] [] 166 J.C. Riquelme, J.S. Aguilar-Ruiz Crossover situation 1. Crossover situation 2. jjj jjP pp pp pp BLX   BLX . .I BLX . l,u l,u j k il,u l min l , l , max l , l u min u , u , max u , u l, u lu controlled by the variable ). A set of children (from to ) is obtained from copies of randomly selected parents, generated by their tness values and using the roulette wheel selection method. The remainder individuals (from to ) are formed by means of crossovers (recombination). As half of the new population is created by applying the crossover operator, the probability of selecting an individual for crossing depends on its tness value. These individuals could be mutated (recombination) later (only the individual from the elite will not be mutated). The evaluation function (evaluation) assigns a value of merit to each individual, which will be further used in the next generation. Wrights linear crossover operator [24] creates three offspring: treating two parents as two points and , one child is the midpoint of both, and the other two lie on a line determined by and . Radcliffes at crossover [16] chooses values for an offspring by uniformly picking values between (inclusively) the two parents values. Eshelman and Schaffer [8] use a crossover operator that is a generalization of Radcliffes which is called the blend crossover ( - ). It uniformly picks values that lie between two points that contain the two parents, but it may extend equally on either side determined by a user specied EA-parameter . For example, - picks values from points that lie on an interval that extends on either side of the interval I between the parents. Logically, - is the Radcliffes at crossover. Our crossover operator is an extension of Radcliffess to parents coded as intervals. Let and be the intervals of two parents and for the same attribute . From these parents one children is generated by selecting values that satisfy the expression: and . This type of crossover could produce two situations, which are illustrated in Figures 12.9 and 12.10. When the intersection of two intervals is not empty, as it is shown in Figure 12.9, the new interval is clearly obtained. However, a different situation is produced when the intersection is empty, because could be greater than . In this case, the offspring is rejected. 1 1 ii na ndv lu na ndv RC RC RC RC RC RC Mutation 12.3.3 Generalization 12 Learning Decision Rules with Hybrid-Encoded EAs 167 When the attribute is discrete, the crossover operator is like uniform crossover [18]. Mutation is applied to continuous attributes as follows: if the randomly selected location (gen) is or , then a quantity is subtracted or added, depending on whether it is the lower or the upper bound, respectively (the quantity is currently the smaller Heterogeneous Overlap-Euclidean Metric (HOEM, [23]) between any two examples). In case of discrete attributes, mutation changes the value from 0 to 1, or viceversa, and it is applied with low probability. We introduce a specic mutation operator to generalize the attribute when nearly all values are 1. In this case, the attribute does not appear in the rule. Mutation is always applied with probabilities 0.1 (individual) and (attribute), where is the number of attributes. If the attribute is discrete, the probability of mutating a value is , where is the number of discrete values of that attribute. Databases used as training les do not have clearly differentiated areas, so that to obtain a totally coherent rule system (without error from the training le) involves a high number of rules. In [1] a system capable of producing a rule set exempt from error (with respect to the training le)is shown; however, sometimes it is interesting to reduce the number of rules in order to get a rule set that may be used like a comprehensible linguistic model. In this way, it could be better to have a system with fewer rules despite some errors than too many rules and no errors. When databases present a distribution of examples very hard to classify, it may be interesting to introduce the relaxing coefficient ( ) for understanding the behavior of databases by decreasing the number of rules [2]. indicates what percentage of examples within a rule can have a different class than the rule has. behaves like the upper bound of the error with respect to the training le, that is, as an allowed error rate. To deal efficiently with noise and nd a good value for , the expert should have an estimate of the noise percentage in its data. For example, if a database produces too many rules when is 0, we could set to 5 to decrease the number of rules and, possibly, the error rate might be very similar. When an individual tries to expand and it always reaches examples of a different Class, its tness value cannot be higher, unless a few errors were allowed. In this case, depending on the tness function, such a value might increase. In Figure 12.11 (right) the individual cannot get bigger, unless one error is allowed, in which case the individual will have four new examples (left), increasing its tness value. v 2 12.7 Acknowledgment References Another aspect being studied is the way in which the evaluation function analyzes each example from the database. Normally, the information is loaded in a vector, and for each individual of the population the whole vector is processed. Research on improvements to the data structure as input of EAs in order to reduce the time complexity is currently being conducted. The research was supported by the Spanish Research Agency CICYT under grant TIC20011143C0302. Progress in Articial Intelligence IBERAMIA98. Lecture Notes in Articial Intelligence 1484. Springer-Verlag Lecture Notes in Articial Intelligence 1415. Springer-Verlag Third International Conference on Genetic Algorithms Complex Systems Machine Learning: Proceedings of the Fifth European Conference (EWSL-91) Machine Learning Foundations of Genetic Algorithms-2 Genetic Algorithms in Search, Optimization and Machine Learning Machine learning Machine Learning Evolutionary Computation Genetic Algorithms + Data Structures = Evolution Programs Machine Learning 174 J.C. Riquelme, J.S. Aguilar-Ruiz 1. J. S. Aguilar, J. C. Riquelme, and M. Toro (1998) Decision queue classier for supervised learning using rotated hyperboxes. In , pages 326336. 2. J. S. Aguilar, J. C. Riquelme, and M. Toro (1998) A tool to obtain a hierarchical qualitative set of rules from quantitative data. In , pages 336346. 3. J. Antonisse (1989) A new interpretation of schema notation that overturns the binary encoding constraint. In , pages 8697. Morgan Kaufmann. 4. S. Bhattacharyya and G.J. Koehler (1994) An analysis of non-binary genetic algorithms with cardinality . , 8:227256. 5. C. Blake and E. K. Merz (1998) UCI repository of machine learning databases, 1998. 6. P. Clark and R. Boswell (1991) Rule induction with cn2: Some recents improvements. In , pages 151163. 7. K. A. DeJong, W. M. Spears, and D. F. Gordon (1993) Using genetic algorithms for concept learning. , 1(13):161188. 8. L. J. Eshelman and J. D. Schaffer (1993) Real-coded genetic algorithms and interval-schemata. , pages 187202. 9. D. E. Goldberg (1989) . Addison-Wesley. 10. R. C. Holte (1993) Very simple classication rules perform well on most commonly used datasets. , 11:6391. 11. C. Z. Janikow (1993) A knowledge-intensive genetic algorithm for supervised learning. , 1(13):169228. 12. G.J. Koehler, S. Bhattacharyya, and M.D. Vose (1998) General cardinality genetic algorithms. , 5(4):439459. 13. Z. Michalewicz (1996) . Springer-Verlag, 3 ed.. 14. T. Mitchell (1997) . McGraw Hill. Journal of Articial Intelligence Research Genetic Neural Networks on MIMD Computers Machine Learning Proceedings of the Third International Conference on Genetic Algorithms Proceedings of European Conference on Machine Learning Evolutionary Computation Evolutionary Computation Journal of Articial Intelligence Research Foundations of Genetic Algorithms-1 12 Learning Decision Rules with Hybrid-Encoded EAs 175 15. J. R. Quinlan (1996) Improved use of continuous attributes in c4.5. , 4:7790. 16. N. J. Radcliffe (1990) . Ph. d., University of Edinburgh. 17. R. L. Rivest (1987) Learning decision lists. , 1(2):229246. 18. G. Syswerda (1989) Uniform crossover in genetic algorithms. In , pages 29. 19. G. Venturini (1993) Sia: a supervised inductive algorithm with genetic search for learning attributes based concepts. In , pages 281296. 20. M.D. Vose and A.H. Wright (1998) The simple genetic algorithm and the walsh transform: Part i, theory. , 6(3):253273. 21. M.D. Vose and A.H. Wright (1998) The simple genetic algorithm and the walsh transform: Part ii, the inverse. , 6(3):275289. 22. D. Whitley (1993) A genetic algorithm tutorial. Technical Report CS-93-103, Colorado State University, Fort Collins, CO 80523. 23. D. R. Wilson and T. R. Martinez (1997) Improved heterogeneous distance functions. , 6(1):134. 24. A. H. Wright (1991) Genetic algorithms for real parameter optimization. , pages 205218.