Supervised learning by means of accuracy-aware evolutionary algorithms

Supervised learning by means of accuracy-aware evolutionary algorithms Josee C. Riquelme, Jesu us S. Aguilar-Ruiz , Carmelo Del Valle Departamento de Lenguajes y Sistemas Informaaticos, Universidad de Sevilla, Avda, Reina Mercedes s/n, 41012 Sevilla, Spain Abstract This paper describes a new approach, HIerarchical DEcision Rules (HIDER), for learning generalizable rules in continuous and discrete domains based on evolutionary algorithms. The main contributions of our approach are the integration of both binary and real evolutionary coding; the use of specific operators; the relaxing coefficient to construct more flexible classifiers by indicating how general, with respect to the errors, decision rules must be; the coverage factor in the fitness function, which makes possible a quick expansion of the rule size; and the implicit hierarchy when rules are being obtained. HIDER is accuracy-aware since it can control the maximum allowed error for each decision rule. 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 a significant improvement with respect to the number of rules and the error rate. Keywords: Evolutionary algorithms; Supervised learning; Decision trees The research was supported by the Spanish Research Agency CICYT under grant TIC2001– 1143–C03–02. * Corresponding author. Tel.: +34954553871; fax: +34954557139. E-mail addresses: [email protected] (J.C. Riquelme), [email protected] (J.S. Aguilar-Ruiz), 1. Introduction 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 (classification) and it can produce knowledge by using a suitable and understandable representation. 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. However, other techniques produce sets of rules with a specific 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. Decision trees are a particularly useful tool in the context of supervised learning because they perform classification by a sequence of tests whose semantics is intuitively clear and easy to understand. Some techniques, like C4.5 [14], construct decision trees selecting the best attribute by using a statistical test to determine how well it alone classifies the training examples. This sort of decision tree may be called axis-parallel, because the tests at each node are equivalent to axis-parallel hyperplanes in space. On the other hand, other techniques build oblique decision trees, such as OC1 [13], that tests a linear combination of the internal attributes at each node, so that, these tests are equivalent to hyperplanes at an oblique orientation to the coordinate axes. To find out the smallest decision tree (axis-parallel or oblique) is a NP-hard problem [5]. Genetic Algorithms (GA) are a family of computational models inspired by the concept of evolution. These algorithms employ a randomized search method to find solutions to a particular problem [9]. This search is quite different from the other learning methods mentioned above. A GA is any population-based model that uses selection and recombination operators to generate new sample examples in a search space [20]. 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 [8,11] including numerical optimization and combinatorial optimization problems, although the range of problems to which GAs have been applied is mbroad. The main tasks in applying GAs to any problem consists in selecting an appropriate representation (coding) and an adequate evaluation function (fitness). In classical GAs the members of the population (typically maintaining a constant-sized) are represented as fixed-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’s 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 fitness function, which determines how good an individual within the population in each generation is. 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. First approaches searched for rules without errors, so the number of rules was very high. Later we controlled the error a rule could make, introducing the relaxing coefficient, i.e. an allowed error for the ruleset. This parameter provides accuracy-awareness to the system, allowing some experimentation to select an appropriate number of rules for the task in consideration. As we will see below, this parameter has no great influence on the average error rate. In previous works, we presented a system to classify databases using binary coding [2]; afterwards, we adopted real coding to handle continuous domains and axis-parallel representation efficiently. (In addition, we explored other representations such as rotated hyperrectangles and hyperellipses [3]). Then, new genetic operators were introduced for real coding. In order to indicate that a GA is being implemented with real coding and genetic operators based on this coding, several authors use the term Evolutionary Algorithms (EA) instead of GA. HIerarchical DEcision Rules (HIDER) uses an EA to search for the best solutions and produces a hierarchical set of rules. According to the hierarchy, an example will try to be classified by the ith rule if it does not match the conditions of the ði1Þth preceding rules. The rules are obtained sequentially until all the examples from the dataset are covered. The behavior is similar to a decision list [17]. 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: first, for adapting the boolean functions to interval functions; and second, for representing classes instead of true and false values (positives and negatives examples). For each continuous (real) attribute aiwe obtain the boundaries values, called Liand Ui(lower and upper bounds, respectively) which define the space Ri(range of the attribute i). 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 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. From the point of view of the experiments, ‘‘unknown class’’ will be considered as an error. The structure of the set of rules will be as shown in Fig. 1. A more descriptive example of rule will appear in Fig. 6, where the different sorts of conditions are shown. The way in which C4.5 splits the space is depicted in Fig. 2. The numbers within the circles describe the level on the tree where these attributes are placed. HIDER is quite different because it does not divide the space by an attribute, Fig. 1. Hierarchical set of rules. A B C A B 1 2 2 43 B Fig. 2. Splitting the search space using C4.5. Numbers within circles indicate the level of the condition on the decision tree. A B C A B Fig. 3. Splitting the search space using HIDER. but it extracts sequentially a region from the space. This permits obtaining entire regions with the same class, as illustrated in Fig. 3. See the region labelled as B on the bottom-left corner of the Figs. 2 and 3. In Fig. 2, C4.5 divides the region into two parts. However, HIDER will obtain the complete region. For another artificial two-dimensional database, Fig. 4 shows the classification that C4.5 gives. Nevertheless, as illustrated in Fig. 5, rules inside of another one could improve the quality of the rule set. The most evident feature, graphically observed in Fig. 5, 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 decision rules. As mentioned in [7] one of the primary motivation for using real-coded EAs is the precision to represent attributes values and the other is the ability to exploit the gradualness of functions of continuous attributes. We implemented our first versions with binary-coded GAs, but we could show that real-coded EAs are more efficient in time and quality of results. A B B A B A A A A AA A A B B B A Fig. 4. Division of the search space done by C4.5. A B B A B Fig. 5. Hierarchical division of the search space done by HIDER. 2. Principles Before an EA can be run, a suitable coding for the problem must be devised. We also require a fitness function, which assigns a figure 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 define an external function that assigns fitness to candidate solutions. Both components are critical to the successful application of the EAs to the problem of interest. Information on the environment comes from a data file, where each example has a class and a number of attributes. We have to codify that information to define the search space, which normally will be dimensionally greater. Each attribute will be formed by several components in the search space, depending on the specific representation. Two basic principles exist for choosing the coding: the principle of meaningful building blocks and the principle of minimal alphabets [9]. In first approaches, we studied GA-based classifier [6,10] 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. 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 infinite. 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 in order to apply the evaluation function. Moreover, when we convert binary to real, we are loosing precision. For that reason, we have to find the exact number of bits in order to eliminate the difference between any two values of an attribute. This ensures that a mutation of the less significant bit of an attribute should include or exclude at least one example from the training set [16]. The representation for continuous and discrete attributes is best explained by referring to Fig. 6, 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 (internal disjunction). A last omitted value is for the class. The number of classes determines the set of values to which it belongs, i.e., if there are five classes, the value will belong to the set 0, 1, 2, 3 and 4. Every rule will be obtained from this representation, but when li¼minðaiÞor ui¼maxðaiÞthe rule will not have that value. For example, in the first case the rule would be ½;vand in the second one ½v;. If both values are equal to the boundaries then the rule appears ½; for that attribute, which means it is not relevant because whichever of the attribute’s values will be covered by the whole range of that attribute ð½;Þ. Under these assumptions, some attributes could not appear in the rule set. In the same way, when every discrete value is active, that attribute does not appear in the rule. 2.2. Algorithm The algorithm is a typical sequential covering EA [12]. An overview of the EA-based classifier is shown in the Fig. 7. It chooses the best individual in the evolutionary process, transforming it into a rule which is used to eliminate data from the training file [19]. In this way, the training file is reduced for the following iteration. A termination criterion might be reached when more examples to cover do not exist. The method of generating the initial population consists in randomly selecting an example from the training file for each individual of the population, and afterwards, an interval to which the example belongs is obtained. For example, let Liand Uibe the lower and upper bounds 1.4 0102.6 11 attribute continuous attribute discrete at 1 : [1.4,6.2] at2: {white, red, green, blue, black} if at 1 [-,2.6] and at 2 {red,blue,black} then Class 0 0 Fig. 6. Continuous (left) and discrete (right) attributes. Fig. 7. Pseudocode. of the attribute i; then, the range of the attribute is UiLi; next, we randomly choose an example ðva1;...;vai;...;vam;classÞfrom the training file, where mis the number of attributes; for the last, a possible individual of the population could thus be ð...;vaið UiLi NÞk1;vaiþð UiLi NÞk2;...;classÞ, where vaiis a value for the attribute i;k1and k2are random values belonging to ½0; N C(Nis the size of the training data; Cis the number of different classes; and class is the same of that of the example). For discrete attributes, the individual has as many positions as different values for the attribute, although we assure that at least the same active value of the example will remain active in the individual. For instance, let the dataset be the one used in Fig. 6. A possible individual for the initial population is obtained from a randomly selected example e¼ð1:8;blue;0Þ. The individual could be ind ¼ð1:4;2:6;0;1;0;1;1;0Þ. The interval [1.4, 2.6] is for the continuous attribute and the values (0,1,0,1,1) is for the discrete one. Notice that the value blue is active and other values (red and black) have also been randomly set to 1. The individual keeps the same class that of the example. Sometimes, the examples very near 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%). This value is calculated from experimentation and when invalid offspring is generated, those values are adjusted to the boundaries of the attribute. 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 fitness values and using the roulette wheel selection. The remainder is formed through crossovers. Since half of the new population is created by applying the crossover operator, the probability of crossover is 0.5 and the probability of selecting an individual for crossing depends on its fitness value. These individuals could be mutated later (only the individual from the elite will not be mutated). Wright’s linear crossover operator [22] 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 2p2and 1 2p1þ3 2p2. Radcliffe’s flat crossover [15] chooses values for an offspring by uniformly picking values between the two parents values inclusively. Eshelman and Schaffer [7] use a crossover operator that is a generalization of Radcliffe’s which is called blend crossover ðBLX –aÞ. 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 specified EA-parameter a. For example, BLX –0:1 picks values from points that lie on an interval that extends 0.1Ion either side of the interval Ibetween the parents. Logically, BLX –0:0 is the Radcliffe’s flat crossover. Our crossover operator is like Radcliffes’s most of the time, but sometimes the value is slightly varied to approximate it to the boundary. Let ½lj i;uj iand ½lk i;uk ibe the intervals of two parents jand kfor the same attribute i. 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 operator to the two parents jand k, and let Land Ube the boundaries of the attribute i being treated, where Land Udefine the range of the attribute. Once the crossover operator is selected, one of the four alternatives is applied depending on the probability denoted in brackets in Fig. 8. When the attribute is discrete, the crossover operator is like a uniform crossover [18]. Mutation is applied for continuous attributes as follows: if the location (gen) corresponds to a value of the interval (lior ui), then a small value is subtracted or added, depending on whether it is the lower or the upper boundary, respectively. The small value is currently the smaller heterogeneous overlap- Euclidean metric (HOEM, [21]) between any two examples. In the case of discrete attributes, mutation changes the value from 0 to 1 or viceversa and it is applied with low probability. We introduce a specific mutation operator to generalize the attribute when almost all values are 1. In this case, the attribute does not appear in the rule. For example in Fig. 12b, the attribute sex is not in the rule R1. For both kinds of attributes, if the location (gen) corresponds to the class, the mutation generates a new value from C, the set of classes, randomly. 2.3. Generalization Databases used as training files do not have clearly differentiated areas, so that obtaining a rule system without errors from the training file involves a high number of rules. We showed in previous papers [1] a system capable of producing a rule set exempt from error with respect to the training file. 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 may be advisable to have a system with fewer rules despite some errors, than too many rules and no errors. In fact, the generalization can produce a decrease in the number of rules, although this has a slight effect on the accuracy of the rule set. Due to the allowance some errors during the obtaining of the first rules, the number of rules becomes lower because a further generation of Fig. 8. Crossover operator: four alternatives. [21] D.R. Wilson, T.R. Martinez, Improved heterogeneous distance functions, Journal of Artificial Intelligence Research 6 (1) (1997) 1–34. [22] A.H. Wright, Genetic algorithms for real parameter optimization, Foundations of Genetic Algorithms 1 (1991) 205–218.