Discovering hierarchical decision rules with evolutive algorithms in supervised learning

IJCSS, Vol.1, No.1, 2000 73 DISCOVERING HIERARCHICAL DECISION RULES WITH EVOLUTIVE ALGORITHMS IN SUPERVISED LEARNING José C. Riquelme, Jesús S. Aguilar and Miguel Toro Departamento de Lenguajes y Sistemas Informáticos. Facultad de Informática y Estadística. Avenida Reina Mercedes s/n 41012 Sevilla Spain e-mail: riquel[email protected]s, [email protected], [email protected] Accepted in the Þnal form: 15 November, 2000 Abstract.This paper describes a new approach, HIDER (HIerarchical DEcision Rules), for learning rules in continuous and discrete domains based on evolutive algorithms. The algorithm produces a hierarchical set of rules, that is, the rules must be applied in a speciÞc order. With this policy, the number of rules may be reduced because the rules could be one inside of another. The evolutive algorithm uses both real and binary codiÞcation for the individuals of the population and introduces several new genetic operators. In addition, this paper discusses the capability of learning systems based on an evolutive algorithm to reduce both the number of rules and the number of attributes involved in the rule set. We have tested our system on real data from the UCI repository. The results of a 10-fold cross validation are compared to C4.5’s and they show an important improvement. Keywords: Evolutive Algorithms, Supervised learning, Decision Lists. 1Introduction Supervised learning is used when the user knows the outcomes of the data samples and wants to predict the outcome of a new unseen instance. An algorithm carries out the prediction (classiÞcation) and it can produce knowledge by using a suitable data structure. Some techniques, like nearest neighbour searching or neural networks, can classify an instance, but cannot obtain the knowledge from the information stored in the database. This sort of learning is called “lazy learning” because the algorithm does not generate a model of knowledge for the database. However, other techniques produce sets of rules with a speciÞc structure: decision trees, decision lists, or simply, set of rules. In general, when a rule-based framework is used to express the acquired knowledge, this is often called decision rules. Such rules can subsequently be used both to infer properties of the corresponding categories and to classify other, previously unseen, examples from the original space. The algorithm is ran once to produce the set of rules that classify many new instances. Other techniques as nearest neighbour classiÞers need one execution every time we want to predict the class of an unseen new example. Therefore, the difference between the techniques that can produce knowledge and those that cannot is very important from the point of view of the number of executions. Supervised learning algorithms tend to emulate the human behaviour, since from input conditions try to predict the action to be taken, based upon experience with similar situations. Such experience 74 IJCSS, Vol.1, No.1, 2000 is collected in a database and knowledge is inferred by means of heuristics or algorithms. Decision trees are a particularly useful tool in the context of supervised learning because they perform classiÞcation by a sequence of tests whose semantics is intuitively clear and easy to understand. Some techniques, like C4.5 [1], construct decision trees selecting the best attribute by using a statistical test to determine how well it alone classiÞes the training examples. This sort of decision trees may be called axis-parallel, because the tests at each node are equivalent to axis-parallel hyperplanes in the space. On the contrary, other techniques build oblique decision trees, as OC1[2], that tests a linear combination of the internal attributes at each node, for that, these tests are equivalent to hyperplanes at an oblique orientation to the coordinate axes. To Þnd out the smallest decision tree (axis-parallel or oblique) is a NP-hard problem [3]. Both methods use hill-climbing, that is, the algorithm never backtracks; therefore, it could be converging to locally optimal solutions that are not globally optimal. Simpson [4] introduced the idea of using hyperrectangles to cluster or classify spatial data. Each hyperrectangle is viewed as a fuzzy cluster, a fuzzy set in which all of the elements within the hyperrectangle have membership 1, and examples outside the hyperrectangle can have a positive membership in the set depending on a fuzzy membership function. Simpson used a deterministic procedure to place and appropriately size hyperrectangles to describe data. Genetic Algorithms (GA) are a family of computational models inspired by evolution. These algorithms employ a randomized search method to Þnd solutions to a particular problem [5]. This search is quite different from the other learning methods mentioned above. A GA is any populationbased model that uses selection and recombination operators to generate new sample examples in a search space [6]. The GA search can move much more abruptly, replacing a parent individual with an offspring less likely to fall into the same kind of local minima that can happen with the other methods. GAs have been used in a wide variety of optimization tasks [7, 8] including numerical optimization and combinatorial optimization problems, although the range of problems to which GAs have been applied is quite broad. The main tasks in applying GAs to any problem are selecting an appropriate representation (coding) and an adequate evaluation function (Þtness). In classical GAs the members of the population (typically maintaining a constant-sized) are represented as Þxed-length strings of binary digits. The length of the strings and the population size Pare completely dependent on the problem. The population simulates the nature behavior since the relatively “good” solutions produce offspring, which replace the relatively “worse” ones, retaining many of the features of their parents. The estimate of the quality of a solution is based on a Þtness function, which determines how good an individual is within the population in each generation. New individuals (offspring) for the next generation are formed by using (normally) two genetic operators: crossover and mutation. Crossover combines the features of two individuals to create several (commonly two) individuals. Mutation operates by randomly changing several components of a selected individual. The aim of our research was to obtain a set of rules to classify a database in the context of supervised learning. In previous works, we presented a system to classify databases using binary coding [9]; afterwards, we adopted real codiÞcation to handle efficiently continuous domains and axis-parallel representations. (In addition, we explored other representations such as rotated hyperrectangles and hyperellipses). Then, new genetic operators were introduced for real codiÞcation. This method is conceptually nearer to evolutionary algorithms (EA) than GA. This new system used an EA to search the best solutions and produced a hierarchical set of rules. The hierarchy follows that an example will be classiÞed by the ith-rule if it does not match the conditions of the (i−1)th precedent rules. The rules are sequentially obtained until the space is totally covered.The behavior is similar to a decision list [10]. A decision list DL is a list of pairs (f1,v 1),...,(fr,v r)where each fjis a term in Cn k,eachvi is a value in {0,1},andthelastfunctionfris the constant function true.(Cn kdenotes the set of all terms (conjunctions) of size at most k with literals drawn from Ln={x1, x1,...,x n, xn}, therefore, |Cn k|= k X i=0 Ã2n i!(1) IJCSS, Vol.1, No.1, 2000 75 If conditions Then class Else If conditions Then class Else If conditions Then class ............................................ Else "unknown class" Figure 1: Hierarchical set of rules. A decision list DL deÞnes a boolean function as follows: for any assignment x∈Xn,DL(x)is deÞned to be equal to vjwhere jis the least index such that fj(x)=1(such an item always exists, since the last function is always true). It is very important to note that decision rules are not the same thing as decision lists. The concept of decision rules is more general than decision lists, because a decision list is a linearly ordered set of decision rules [10]. We extend the concept of decision list to continuous domains. Decision lists work well with objects that are described as concepts, so it can represent boolean attributes (positives or negatives examples). However, 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 classes instead of true and false values (positives and negatives examples). We let Cdenote the set of classes (labels) of a database. For each continuous (real) attribute aiwe obtain the boundary values, called liand ui(lower and upper boundaries, respectively) which deÞne the space Ri(range of the attribute i). Let Hibe an interval [l, u]where l<uand l, u ∈Ri, for the attribute i.Then,anextended decision list EDL is a list of pairs (f1,v 1),...,(fr,v r)(2) where each fiis a function in H1×H2×···Hm,viis a value in Cand misthenumberofattributes. Our EDL does not have the last constant function true as DL has. However, we could interpret the last function as an unknown 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. The structure of the set of rules will be as shown in Þgure 1. Decision list policy is applied in order to reduce the number of rules. For an artiÞcial twodimensional database, Þgure 2 shows the classiÞcation that C4.5 gives. Nevertheless, as illustrated in Þgure 3, rules inside of another one could improve the quality of the rule set. A B B A B A A A A A A A A B B B A Figure 2: C4.5 The most evident feature, graphically observed in Þgure 3, is the reduction of the number of rules because of the rules overlapping. As mentioned in [11] one of the primary motivations for using real-coded EAs is the precision to represent attributes values and another is the ability to exploit the gradualness of functions of 76 IJCSS, Vol.1, No.1, 2000 A B B A B Figure 3: HIDER continuous attributes. We implemented our Þrst versions with binary-coded GAs, but we could prove that real-coded EAs are more efficient (time and quality of results). In addition, HIDER reduces the number of attributes involved in a rule, making its comprehension by humans easier. 2 Principles Before an EA can be run, a suitable coding for the problem must be devised. We also require a Þtness function, which assigns a Þgure of merit to each coded solution. During the run, parents are selected for reproduction, and recombined to generate offspring. These aspects are described below. 2.1 Coding In order to apply EAs to a learning problem, we need to select an internal representation of the space to be searched and deÞne an external function that assigns Þtness to candidate solutions. Both components are critical to the successful application of the EAs to the problem of interest. Information of 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 [5]. In Þrst approaches, we studied several GA-based classiÞer [12, 13] with binary coding. These are generally used as concept learners, which coding assigns a bit to each value of the attribute, i.e., every attribute is symbolic (GABIL and GIL are two very 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. Several bits could be active. This coding is appropriate for symbolic domains. However, it is very difficult to use in continuous domains, because the number of possible values of an attribute is inÞnity. The length of an individual is determined by the sum of the number of values of each attribute. Using binary encoding in continuous domains requires transformations from binary to real for every attribute. To apply the evaluation function is necessary to convert the binary to real encoding. This process increases the computation time by a factor of m(number of attributes). Moreover, when we convert binary to real, we are loosing precision. For that reason, 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 least signiÞcant bit of an attribute will not include or exclude more than one example from the training set in a single step. Let liand uibe the lower and upper bounds of IJCSS, Vol.1, No.1, 2000 77 an attribute. Let mibe the least absolute difference of any two values of the attribute i.Theallowed error for this attribute must be less than mi. Then, the length of an attribute would be as follows: Li=»log2µ1+ui−li errori¶¼ (3) However, in this paper, to eliminate the problem we use the real codiÞcation. Thisimpliesto redeÞne the genetic operators for it as we see below. The representation for continuous and discrete attributes is best explained by referring to Þgure 4, where liand uiare values representing an interval for the continuous attribute; biare binary values indicating that the value of the discrete attribute is active or not. A last value (omitted) is for the class. continuous discrete attribute b 1 b 2 b k ... Binary values l i u i attribute Real values Figure 4: Continuous (left) and discrete (right) attributes. The number of classes determines the set of values to which an example belongs, i.e., if there are Þve classes, the value of a class will belong to the set {0,1,2,3,4}. Every rule will be obtained from this representation, but when li=min(ai)or ui=max(ai)therulewillnothavedeÞned that value in the interval. For example, in the Þrst case the rule would be [−,v](the left value of the interval is equal to the minimum value of the range of the attribute) and in the second one [v,−](the right value of the interval is equal to the maximum value of the range of the attribute). If both values are equal to the boundaries then the rule appears [−,−]for that attribute, which means that it is not relevant. Under these assumptions, some continuous attributes may not appear in the rule set. In addition, when every discrete value is active, that attribute does not appear in the rule. 2.2 Algorithm The algorithm is a typical sequential covering GA [14]. It chooses the best individual of the evolutionary process, transforming the individual into a rule, which is used to eliminate data from the training Þle [15]. In this way, the training Þle is reduced for the following iteration. A termination criterion could be reached when more examples to cover do not exist. The method of generating the initial population consists of randomly selecting an example from the training Þle for every individual of the population. Then, an interval to which the example belongs is obtained by adding and subtracting a random quantity from the values of the example. Sometimes, the examples very near to the boundaries are hard to cover during the evolutionary process. To resolve this problem, the search space is increased (actually, the lower bound is decreased by 5%, and the upper bound is increased by 5%). For example in one dimension, let aand bbe the lower and upper bounds of the attribute; then, the range of the attribute is b−a; next, we randomly choose an example (x1,class)from the training Þle; for last, a possible individual of the population could thus be (x1−range ×k1,x 1+range ×k2,class)where k1and k2are random values belonging to [0,range N](Nis the size of the training data, and class is the same of that of the example). For discrete attributes, this is not a problem because the individual has the same active values as the example. The evolution module includes elitism: the best individual of every generation is replicated to the next one. A set of children (50%) is obtained from copies of randomly selected parents, generated by their Þtness values and using the roulette wheel selection. These individuals could be mutated later (only the individual from the elite will not be mutated). The remainder is formed through crossovers. Afterwards, mutation is applied depending on a probability. An overview of the EA-based classiÞerisshownintheÞgure 5. 78 IJCSS, Vol.1, No.1, 2000 While exists examples in training file Step 1. Initialize population Step 2. Repeat num generations times Step 2.1. Evaluation Step 2.2. Select the best Step 2.3. Replication Step 2.4. Crossover and Mutation Step 3. Put the best one in Decision List Step 4. Eliminate examples covered by best Figure 5: Pseudocode. Wright’s linear crossover operator [16] creates three offspring: treating two parents as two points p1and p2, one child is the midpoint of both, and the other two lie on a line determined by 3 2p1−1 2p2 and −1 2p1+3 2p2. Radcliffe’s ßatcrossover[17]choosesvaluesforanoffspring by uniformly picking values between (inclusively) the two parents values. Eshelman and Schaffer use a crossover operator that is a generalization of Radcliffe’s which is called blend crossover (BLX-α). It uniformly picks values that lie between two points that contain the two parents, but may extend equally on either side determined by a user speciÞed EA-parameter α.Forexample,BLX-0.1picks values from points that lie on an interval that extends 0.1Ion either side of the interval I between the parents. Logically, BLX-0.0is the Radcliffe’s ßat crossover. Our crossover operator is like Radcliffes’s most of the time, and sometimes the value is perturbed to approximate it to the boundary. Let [l1,u 1]and [l2,u 2]be the intervals of two parents for the same attribute. In the Þgure 6 the parents are in the Þrst two segments. From these parents we can generate four possible children selecting values as follows: let [l, u]be the interval we want to obtain after applying the crossover to two parents and let Land Ube the boundaries of the attribute being treated. We have four possibilities (the percentages of application are to the right): l∈[l1,l 2]u∈[u1,u 2] 85% l∈[L, min(l1,l 2)] u∈[max(u1,u 2),U]5% l∈[l1,l 2]u∈[max(u1,u 2),U]5% l∈[L, min(l1,l 2)] u∈[u1,u 2]5% 1 1 u 1 1 2 u 2 (1) (2) Figure 6: Axis-Parallel crossover operator. Mutation is applied in two different ways: if the randomly chosen location corresponds to a value of the interval, then a quantity is subtracted or added, depending on whether it is the lower or the upper bound, respectively (the quantity actually is the lower Euclidean distance between any two examples); if the location corresponds to the class, a new value is randomly generated. When the attribute is discrete, the crossover operator is like uniform crossover [18] and mutation is applied with low probability. We introduce a speciÞc mutation operator to generalize the attribute IJCSS, Vol.1, No.1, 2000 79 when almost all values are 1. In this case, the attribute does not appear in the rule. For example in Þgure 10, the attribute sex is not in the rule R1. 2.3 Relaxing coefficient DatabasesusedastrainingÞles do not have clearly differentiated areas. Therefore, to obtain a rule system totally coherent (without error from the training Þle) involves a high number of rules. We showed in previous papers [19] a system capable of producing a rule set exempt from error; however sometimes, it is interesting to reduce the number of rules for having a rule set which 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 (RC)for understanding the behavior of databases by decreasing the number of rules [20]. RC indicates what percentage of examples inside of a rule can have a different class than what the rule has. RC 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 RC, the expert should have an estimate of the noise percentage in its data. For example, if database X produces too many rules when RC is 0, we could set RC to 5 to decrease the number of rules and, possibly, the error rate might be the same as before. 2.4 Fitness function The Þtness function must be able to discriminate between correct and incorrect classiÞcation of examples. Finding an appropriate function is not a trivial task, due to the noisy nature of most databases. The evolutionary algorithm minimizes the Þtness function ffor each individual. It is given by f(i)=2(N−CE(i)) + G(i)+Coverage(i) where the rule coverage is the value of the side of a k-dimensional hypercube which volume is equivalent to the volume of the k-dimensional region covered by the rule; CE(i)is the class error, which are produced when the example ibelongs to the region deÞned by the rule, but does not have the same class; G(i)is the number of goals of the rule. Every rule can be quickly expanded for Þnding more examples due to the rule coverage in the Þtness function. The reason why f(i)is not N−CE(i)+ G(i)+Coverage(i)is as follows: for example, when CE(i)=7and G(i)=9we will have the same Þtness value as when CE(i)=15and G(i)=17(the difference is 2; assuming the same coverage for both). Therefore, we decided to penalty the second case (9 7is greater than 17 15 ). 3 Application The experiments described in this section are from the UCI repository [21]. To measure the performance of the method, a 10-fold cross validation was realized with each dataset. It is very important to note that every execution has been carried out with a population size of as little as 100 individuals and 300 generations for the EA. These are very low numbers considering the number the examples and the dimensionality of some databases. HIDER needed about 8hours to complete the 10-fold cross validation for the 18 databases on a Pentium 400Mhz with 64Mb of RAM. However, C4.5 only needed about 8minutes on the same machine. C4.5 is an extremely robust algorithm that performs well on many domains. It is very difficult to consistently outperform C4.5 on a variety of datasets. Thus, improving C4.5 should yield an interesting learning algorithm. The results of these trials appear in tables 1, 2 and 3. Table 1 gives a 10-fold cross validation of the error rates for the C4.5 and HIDER algorithms on the selected domains. Table 2 compares the number of rules generated by the two approaches. From the point of view of the comprehension of the knowledge inside the database, HIDER is much better than C4.5 since the number of rules is very much lower. 80 IJCSS, Vol.1, No.1, 2000 Table 1: Comparing error rates. Database C4.5R8 HIDER Bupa 34.73 35.71 Breast Cancer 6.28 4.29 Cleveland 26.77 20.49 German 32.1 29.1 Glass 32.73 29.41 Heart 21.83 22.32 Hepatitis 21.42 19.41 Horse Colic 19.0 17.64 Iris 4.67 3.33 Lenses 29.99 25.0 Mushroom 0.01 0.76 Pima 32.06 25.9 Sonar 30.31 43.07 Tic-Tac-Toe 14.2 3.85 Vehicle 30.6 30.6 Vote 6.19 6.42 Wine 6.71 3.95 Zoo 7.0 8.0 Average 19.81 18.29 The set of rules generated for the Wine database is presented in Þgures 7 and 8. The exact same folds were used for both algorithms so that the ten resulting performance numbers for HIDER and C4.5 are pairwaise comparable. HIDER produced an error rate of 0%, however, that of C4.5 was 22.2%. c12<=2.15: | c4 <= 17.5 : 2 (6.0) | c4 > 17.5 : 3 (45.0/2.0) c12 > 2.15 : | c13 <= 725 : 2 (54.0/1.0) | c13 > 725 : | |c10 <= 3.4 : 2 (4.0) | | c10 > 3.4 : 1 (51.0) Figure 7: Decision Tree generated by C4.5 for Wine database. Table 3 shows a measure of improvement (²) for the error rate (Þrst column: (²er)) and the number of rules (second column: (²nr)). To calculate those coefficient (²er and ²nr, respectively) the error rate (number of rules) of C4.5 has been divided by the error rate (number of rules) of HIDER. The last row contains the average of every column. On average, HIDER found solutions that had less than half of the rules output by C4.5. Surprisingly, C4.5 generated a number of rules Þve times greater than HIDER for one third of the databases. Figures 9 and 10 illustrate an example a little more complex (Hepatitis database), which shows that when the number of rules is large, the number of attributes involved in the rule set is also reduced. Thus, in the example, C4.5 uses 63 conditions and HIDER uses 30 conditions. Morover, the error rate was 31.2% for C4.5, in contrast with 12.5% for HIDER (using the same fold). IJCSS, Vol.1, No.1, 2000 81 Table 2: Comparing number of rules. Database C4.5R8 HIDER Bupa 28.6 11.3 Breast Cancer 21.9 2.6 Cleveland 35.2 7.9 German 181.5 13.3 Glass 29.0 19.0 Heart 29.2 9.2 Hepatitis 13.8 4.5 Horse Colic 39.3 6.0 Iris 5.5 4.8 Lenses 4.1 6.5 Mushroom 15.5 3.1 Pima 93.6 16.6 Sonar 16.8 2.8 Tic-Tac-Toe 93.9 11.9 Vehicle 102.3 36.2 Vote 14.7 4.0 Wine 5.4 3.3 Zoo 9.9 7.2 Average 41.12 9.46 IF R1: c7 [1.08,-] and c10 [3.82,-] and c13 [741.80,-] : 1(51|0) ELSE IF R2: c7 [1.14,-] and c11 [0.68,-] and c12 [1.61,-] : 2(64|1) ELSE IF R3: c4 [11.57,-] : 3(43|0) ELSE unknown Figure 8: Hierarchical Decision List generated by HIDER for Wine database. 4 Conclusions A supervised learning tool to classify databases is presented in this paper. It produces a hierarchical set of decision rules where the conditions of each rule indicate if an example belongs to a region. The number of rules is reduced with regard to other systems, like C4.5, and improves the ßexibility to construct a classiÞer varying the relaxing coefficient. We also have explored several types of crossover and mutation operators. Finally, real-coded genetic algorithms are more efficient Þnding rule sets than binary-coded ones on supervised learning with continuous domains. The tables show how effective HIDER is, particularly, with respect to the number of rules. The error rate provided by C4.5 is about 20% greater. Likewise, the number of rules provided by C4.5 is about a factor of four greater than HIDER produces. In addition, the number of attributes involves in the rule set is reduced too. Therefore, HIDER would be considered an approach of great quality. Acknowledgements The research was supported by the Spanish research agency CICYT under grant TIC99-0351.