Natural Coding: A More Efficient Representation for Evolutionary Learning

Natural Coding: A More Efficient Representation for Evolutionary Learning Ra´ul Gir´aldez, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Department of Computer Science, University of Seville Avenida Reina Mercedes s/n, 41012 Sevilla, Spain {giraldez,aguilar,riquelme}@lsi.us.es Abstract. To select an adequate coding is one of the main problems in applications based on Evolutionary Algorithms. Many codings have been proposed to represent the search space for obtaining decision rules. A suitable representation of the individuals of the genetic population can reduce the search space, so that the learning process is accelerated by decreasing the number of necessary generations to complete the task. In this sense, natural coding achieves such reduction and improves the results obtained by other codings. This paper justifies the use of natural coding by comparing it with hybrid coding that joins well-known binary and real representations. We have tested both codings on a heterogeneous subset of databases from the UCI Machine Learning Repository. The experiments’ results show that natural coding improves the quality of the obtained knowledge-model using only one third of the generations that hybrid coding needs as well as a smaller population. Keywords: Evolutionary Algorithms, Coding, Supervised Learning 1 Introduction Machine Learning is used when we want to build a knowledge model from a training dataset and predict the outcome of a new unseen instance. Normally, the instances of the dataset are named examples and each example is formed by attributes. These attributes can be classified by different criteria according to the kind of values that they take. The most common classification is in continuous and discrete attributes. If an attribute takes values in a real and infinite domain, we say that it is continuous. On the contrary, if the domain is a finite set of values, we name it as a discrete attribute. Usually, one of these attributes is selected as a decision attribute or class. Thus, the knowledge model is built to predict the value that the class takes in new examples depending on the other attributes values. When the class of the training data is known (labeled dataset), we work in the Supervised Learning field. This research was supported by the Spanish Research Agency CICYT under grant TIC2001-1143-C03-02. E. Cant´u-Paz et al. (Eds.): GECCO 2003, LNCS 2723, pp. 979–990, 2003. c Springer-Verlag Berlin Heidelberg 2003 980 R. Gir´aldez, J.S. Aguilar-Ruiz, and J.C. Riquelme The knowledge model can be represented by different structures: decision rules, association rules, decision trees, etc. In Supervised Learning, the structures generated are usually decision rules or trees. The databases have a set of attributes or characteristics that define each example. A decision rule establishes conditions which the examples must fulfil in order to be classified by this rule. These conditions affect the values that the attributes can take in that if the attributes of an example meet all the conditions that a rule establishes then we say that the rule covers the example, independent of whether it classifies such example correctly or not. The usual representation of rules generated by learning systems is shown in Figure 1. If Cond1and Cond2and...and CondMthen Class =C Fig. 1. Decision Rule. where Condiis the condition that the ith attribute of an example has to satisfy in order to be classified with class C, and Mis the number of attributes in the database. Logically, the case can arise where an attribute does not appear in the rule, from which we assume that the condition concerning the attribute is always evaluated as true. When an attribute (ai) is continuous, the condition (Condi) takes the form ai∈[li,u i], restricting the range of values of the attribute to the interval defined by the lower (li) and the upper (ui) bound. On the other hand, when the attribute is discrete, the condition takes the form ai∈{v1,v 2,...,v k}, where the values {v1,v 2,...,v k}are not necessarily all those the attribute can take. In literature, there are many methods that acquire the inherent knowledge from a labeled dataset and generate a structure that represents it: CN2 [6,7], AQ-based systems [13],OC1 [15], C4.5 [16], SEE5.0 [17], SIA [20], among others. This work is focused on those methods that apply Evolutionary Algorithms (henceforth EA) in the training phase, and specifically in the tool Hider (Hierarchical Decision Rules) [2]. This tool generates a set of hierarchical decision rules by applying an EA whose population is a set of encoded rules. Thus, each individual is a decision rule where each attribute is coded by one or several genes. Different versions of Hider have used different codings for the individuals of population: binary, real and hybrid. This work is focused on a new version of this tool, called Hider*, which applies the natural coding [1] to represent the individuals. Thus, we compare the two last versions, Hider and Hider*, that use the hybrid and natural coding respectively. Both codings can treat continuous and discrete attributes. Hybrid coding applies binary coding for discrete attributes and real coding for continuous. Natural is an original coding that represents both kinds of attributes by means of a simple natural number. As it is explained later, the main advantage of natural coding is the reduction of the search space. Our goal in this paper is to present the advantages of natural coding against hybrid coding. Hider and Hider* were run and their performances measured. The results show that Hider* finds solutions before Hider, since natural coding Natural Coding: A More Efficient Representation for Evolutionary Learning 981 reduces the number of candidate solutions. Thus, Hider* can be run with fewer generations and with a smaller population size than Hider. The rest of this paper is organized into the following: Section 2 describes the EA used by Hider and Hider*. The characteristics of hybrid coding and natural coding are presented in Sections 3 and 4 respectively. The experimental results of our research are presented in Section 5. Finally, in Section 6, the conclusions of this work are summarized. 2 Algorithm Hider is a tool that produces a hierarchical set of rules. When a new example needs to be classified, the set of rules is sequentially evaluated according to its hierarchy, so if the example does not fulfil a rule, the next one in the hierarchy order is evaluated. This process is repeated until the example matches every condition of a rule and is classified with the class that such rule establishes. Hider uses an EA to search for the best solutions. Since the aim is to obtain a set of decision rules, the population of the EA is formed by some possible solutions. Each genetic individual is a rule that evolves by applying the mutation and crossover operators. In each generation, some individuals are selected according to their goodness of fit and they are included in the next population along with their offspring. Thus, the performance of the tool is influenced by two factors: the fitness function and the coding. The fitness function used in this research is f(r)=N−CE(r)+G(r)+coverage(r) (1) where ris an individual; Nis the number of examples being processed; CE(r) is the class error, i.e. the number of examples belonging to the region defined by the rule rbut they do not have the same class; G(r) is the number of examples correctly classified by r; and coverage(r) gives the proportion of the search space covered by the rule. This fitness function is described in detail in [2]. The goal of our work is focused on the coding, so the another factor is not analyzed in detail. In fact, Hider and Hider* use the same EA and the same fitness function. The difference between both is in the coding. Hider applies hybrid coding, whereas Hider* uses natural coding. The pseudocode of Hider is shown in Figure 2. The main algorithm is a typical sequential covering method [14], where the algorithmic function that produces the rules is an EA. Each call for this function (line 8) generates only one rule that is inserted into the final set of rules (line 9) and is used to eliminate examples from the training data (line 10). The evolutionary function is started again with the reduced training data. This loop is repeated until the set of training data is empty. The function EvoAlg has a set of examples as an input parameter. It returns a rule which is the best individual of the last generation. The initial population is built randomly by the function InitializePopulation. Some examples are randomly selected and individuals that cover such examples are generated. After 982 R. Gir´aldez, J.S. Aguilar-Ruiz, and J.C. Riquelme 1Procedure Hider 2Input: T: File of examples (Training file) 3Output: R: Set of rules (Sorted set) 4begin 5R:= ∅ 6initialSize := |T| 7while |T|> initialSize 8r:=EvoAlg(T) 9R:=R ⊕r 10 DeleteCoveredExamples(T,r) 11 end while 12 end Hider 13 Function EvoAlg (T: File of encoded-examples) ret(r: Rule) 14 begin 15 InitializePopulation(P) 16 For i:=1 to num generations 17 Evaluate(P) 18 next P:=SelectTheBestOf(P) 19 next P:=next P+Replicate(P) 20 next P:=next P+Recombine(P) 21 P:=next P 22 end for 23 Evaluate(P) 24 return SelectTheBestOf(P) 25 end EvoAlg Fig. 2. Pseudocode of Hider. initializing the population, the for-loop repeats the evolutionary process a number of times which is determined by the parameter num generations. In each iteration, the individuals of the population are evaluated according to a defined fitness function, thus each individual acquires a “goodness” (function Evaluate). The best individual of every generation is replicated to the next one (elitism). Later, a set of individuals are selected through the roulette wheel method and replicated to the next generation. Finally, another set of individuals are recombined and the offspring is included in the next generation. The selection of these individuals is also carried out by means of the roulette wheel. Once the loop finishes, the best individual of the last generation is returned. 3 Hybrid Coding After studying other EA-based approaches proposed in the bibliography, we deduced that a combination of binary coding and real coding would be suitable for our problem. First, we analyzed two well-known systems: GABIL [8] and GIL [11]. These concept learners use binary coding, assigning a bit to each value of an attribute. A value of one, in a bit, implicates that the value is present, so that several bits could be active for the same attribute. This implies that binary coding is a good election for encoding symbolic attributes. Nevertheless, it is not suitable for continuous attributes, because the size of their alphabet is very large (theoretically infinite) and this aspect does not allow a complete search. Non-binary codings have been widely researched in literature [3,4,12, Natural Coding: A More Efficient Representation for Evolutionary Learning 983 l i u i Continuous Attribute Discrete Attribute Class . . .b 1 b 2 b k c j Binary ValuesReal Values Fig. 3. An hybrid individual with a continuous attribute and a discrete one. 21,22]. These jobs show that real coding is more appropriate than binary in continuous domains. Hybrid coding tries to profit from the advantages of binary and real coding. Thus, it mixes both codings by using the real to represent the boundaries of the intervals in continuous domains, and the binary to encode the discrete attributes. Figure 3 explains the representation for continuous and discrete attributes in hybrid coding. The continuous attribute is encoded by two real values being the lower (li) and the upper bound (ui) of the interval that the rule establishes for such attribute. The discrete attribute is represented by a number kof bits, where each of them denotes the presence or absence of a discrete value in the condition of the rule. The last value is the class, which is not usually encoded. Each class is represented as a integer, so that for a number nof classes, the value cjwill belong to the set {0, 1, 2, ..., n-1}. With regard to the genetic operators, crossover and mutation for hybrid coding are described in detail in [2]. The crossover for continuous attributes is an extension of Radcliffe’s [18] to parents coded as intervals. If two parents, a and b, establish the intervals [la i,u a i] and [lb i,u b i] respectively for the attribute ai, then the interval of the offspring ([lo i,u o i]) fulfils expressions in Equation 2. In case of discrete attributes, the uniform crossover is carried out [19]. lo i∈[min(la i,lb i), max(la i,lb i)] uo i∈[min(ua i,u b i), max(ua i,u b i)] (2) In order to apply the mutation to a continuous attribute, a gene (gi)is randomly selected. Such gene can be the lower bound (li) or the upper (ui) bound of the interval. The mutation consist in replacing the gene giwith gi±δ, where δis the smaller HOEM (Heterogeneous Overlap-Euclidean Metric [23]) between two examples of the training dataset. Thus, an interval is expanded (li−δor ui+δ) or contracted (li+δor ui−δ). When the attribute is discrete, the mutation changes the gene (a bit) depending on the discrete-value mutation probability, so that some values are included or excluded from the condition. 4 Natural Coding The ideal coding must fulfil the following properties: completeness, coherence, uniformity (uniqueness), simplicity, locality, consistency and minimality. To find 984 R. Gir´aldez, J.S. Aguilar-Ruiz, and J.C. Riquelme Table 1. Coding for a continuous attribute. Cutpoints 2.5 3.9 4.7 5.0 6.2 1.4 1≡[1.4,2.5] 2≡[1.4,3.9] 3≡[1.4,4.7] 4≡[1.4,5.0] 5≡[1.4,6.2] 2.5 −7≡[2.5,3.9] 8≡[2.5,4.7] 9≡[2.5,5.0] 10 ≡[2.5,6.2] 3.9 −−13 ≡[3.9,4.7] 14 ≡[3.9,5.0] 15 ≡[3.9,6.2] 4.7 −− −19 ≡[4.7,5.0] 20 ≡[4.7,6.2] 5.0 −− − −25 ≡[5.0,6.2] a suitable representation is very difficult but to find one that fulfils every aforementioned property is practically impossible. Thus, we try to design a coding that keeps at least two well-known principles proposed by Goldberg in [10]: the principle of meaningful building blocks and the principle of minimal alphabets. After analyzing the problem, we developed a coding, named “natural” [1], which only uses natural numbers to represent the set of values that can take part of the decision rules, independently of the kind of attributes (continuous or discrete). In particular, natural coding encode each condition of a rule with only one gene that is a natural number. Thus, this coding fulfils two aforementioned properties: uniqueness (every individual has an unique representation) and minimality (the length of coding must be as short as possible). Although continuous and discrete values are encoded as natural numbers, the meaning of this number is different in both cases. As in regards to continuous attributes, a method that calculates the cutpoints in range of values for each continuous attribute is applied. The cutpoints are the possible bounds of intervals that a condition can set. In principle, these cutpoints can all be of values the attribute takes in the training dataset. However, this choice generates too many cutpoints. In order to reduce the number of cutpoints, we apply the method named USD [9]. This method produces a set of bounds that maximize the goodness of the possible intervals. Such an aspect has a favorable influence on the rules that Hider* is going to obtain later. Once the cutpoints are calculated, a natural number is assigned to each possible combination of bounds, so every possible interval is represented by a natural number. Table 1 shows an example of coding for a continuous attribute where the set of cutpoints generated by USD is {1.4, 2.5, 3.9, 4.7, 5.0, 6.2}. In general, if kis the number of cutpoints, the rows are labeled from the first one to (k−1)th and the column are labeled from the second one to kth cutpoint. Thus, each element of the table is a natural number that encodes the interval defined by its row and column. In case the attributes are discrete, the natural coding is obtained from a binary coding similar to that used in GABIL and GIL. In decision rules, a condition can establish a set of discrete values that the attribute must take to classify an example. Each gene that represents a condition for a discrete attribute is also a natural number. The binary representation of this gene is a number where there is a bit for each different discrete value that an attribute can take. Thus, if Ωis the set of possible values for a discrete attribute, then the natural number that encodes the corresponding condition of the rule is in interval [0, 2|Ω|−1]. If a value is included in the condition, its corresponding bit Natural Coding: A More Efficient Representation for Evolutionary Learning 985 Table 2. Coding for a discrete attribute. Discrete values Natural white red green blue black Coding 000 0 0 − 000 0 1 1 000 1 0 2 000 1 1 3 . . . . . . . . . . . . . . . . . . 010 1 1 11 . . . . . . . . . . . . . . . . . . 111 1 0 30 111 1 1 31 is equal to 1, otherwise it is 0. The natural coding for this gene is the conversion of the binary number into a natural one. Table 2 shows an example for a discrete attribute with five different values: white,red,green,blue and black. The mutation and crossover operators are described in detail in [1]. For continuous attributes, mutation is a shift (up, down, left or right) in the coding table (see Table 1). Such shift mutates the gene changing the bounds of the interval. The crossover consists in calculating the intersection of the rows and columns of both parents, so that the obtained set of natural numbers is the offspring. For discrete attributes, the mutation is a transformation of the value that encodes the gene, by changing some bits of the binary code associated with the natural number. The crossover is based on the mutation. Each gene that take part in the crossover provides a set of candidates obtained from its possible mutations joined to itself. The offspring of two genes is a random selection of numbers from the intersection of both sets of candidates. Although the natural operators seem to be very complex processes, in fact, they are very simple algebraic operations. They do not imply any conversion between binary and natural numbers and do not need any operation with arrays. As shown in [1], the natural operators are algebraic operations with a low computational cost. Figure 4 illustrates the differences between natural and hybrid coding. It shows two individuals that encode the same rule. The attribute AT1is continuous whereas AT2is discrete. Both attributes are encoded according to Tables 1 and 2. We can see that natural coding is simpler, since the hybrid needs eight genes to code the rule whereas the natural encodes it with only three genes. Natural coding minimizes the size of individuals, assigning only one gene for each attribute. Hybrid uses two genes for continuous attributes and —Ω— for discrete, where —Ω— is the number of different values that an attribute can take. 5 Results In order to show the quality of natural coding, we applied Hider and Hider*to a set of databases from UCI Repository [5]. As we mentioned in Section 2, both tools use the same EA, although Hider uses hybrid coding, to the contrary of 986 R. Gir´aldez, J.S. Aguilar-Ruiz, and J.C. Riquelme Rule: If AT 1 [3.9, 5.0] and AT 2 {red, blue, black} Then Class 0 3.9 5.0 101100 AT 1 AT 2 Class 14 11 0 AT 1 AT 2 Class AT 1 (Continuous): [1.4, 6.2] AT 2 (Discrete): {white, red, green, blue, black} Domains Hybrid Coding Natural Coding Fig. 4. Hybrid individual vs. Natural individual. Table 3. Parameter of Hider. Parameter Hider (hybrid) Hider* (natural) Population Size 100 70 Number of Generations 300 100 Replication 20% 20% Recombination 80% 80% Individual Mutation Probability 0.5 0.5 Gen Mutation Probability 1 attributes 1 attributes Discrete-value Mutation Probability 1 values 1 values Hider* which uses natural coding. Both were run with the same crossover and mutation parameters, but with a different number of individuals and generations. Table 3 shows the parameters used in each case. The lower values that Hider* needs for the population size and number of generations are due to the reduction of the search space by natural coding. Thus, Hider* used only 100 generations and 70 individuals to obtain similar numbers to those obtained by Hider, which needed 300 and 100 respectively (see Table 4). The databases used in the experiments were 16, some of which contain only continuous attributes, others contain only discrete attributes and the remainder include both types of attributes. Thus, we can compare the behaviour of natural and hybrid coding with both types of attributes. To measure the performance of each method, a 10-fold cross-validation was achieved with each database. The values that represent the performance are the error rate (ER) and the number of rules (NR) obtained. The ER is the average number of misclassified examples expressed as a percentage and the NR is the average number of rules for the 10-fold cross-validation. The algorithms were run on the same training sets and the knowledge structures tested using the same test sets, so the results were comparable. With these conditions and the aforementioned parameters for the EAs, the results obtained by applying both codings are given in Table 4. In Table 4, the first column shows the databases used in the experiments; the next two columns give the ER and NR obtained respectively by Hider with hybrid coding for each database. Likewise, the fourth and fifth columns give the ER and NR for Hider* with natural coding. The last two columns show a Natural Coding: A More Efficient Representation for Evolutionary Learning 987 Table 4. Comparing Hider and Hider*. Hider (hybrid) Hider* (natural) Improvement Database ER NR ER NR er nr breast-c 4.3 2.6 4.06 2 1.06 1.3 bupa 35.7 11.3 37.35 4.2 0.96 2.69 cleve 20.5 7.9 25.33 5.9 0.81 1.34 german 29.1 13.3 27.4 8 1.06 1.66 glass 29.4 19 35.24 11.7 0.83 1.62 heart 22.3 9.2 21.85 4.3 1.02 2.14 hepatiti 19.4 4.5 16.67 3.7 1.16 1.22 horse-co 17.6 6 20 11.1 0.88 0.54 Iris 3.3 4.8 3.33 3.2 0.99 1.5 Lenses 25 6.5 25 4.5 1 1.44 mushroom 0.8 3.1 1.18 3.5 0.68 0.89 pima 25.9 16.6 25.66 5.1 1.01 3.25 vehicle 30.6 36.2 33.81 19.7 0.91 1.84 vote 6.4 4 4.42 2.2 1.45 1.82 wine 3.9 3.3 8.82 5.6 0.44 0.59 zoo 8 7.2 4 7.9 2 0.91 Average 17,64 9,72 18,38 6,41 1,02 1,55 measure of improvement for the error rate (er) and the number of rules (nr). The er coefficient was calculated by dividing the error rate for Hider by the corresponding error rate for Hider*. The same operation was carried out to obtain nr, but by using the number of rules for both tools. Finally, the last row shows the average results for each column. As we can observe, Hider*doesnot attain a reduction in ER for 8 out of 16 datasets. Nevertheless, on average, it improves on Hider, although this improvement is very small (2%). As regards to number of rules, the results are more significant, since Hider* obtains a smaller number of rules in 12 out of 16 cases, with an average improvement of 55%. Although the results show that Hider* has a better performance, we must not forget that those numbers were obtained using a smaller number of generations and individuals of a genetic population. In particular, Hider* needed one third of the generations and fewer than three quarters of the population size invested by Hider. The reduction of the search space that natural coding gets, allows Hider* to obtain these results with such parameters. In Table 5, the length of individuals of the genetic population for the hybrid and natural coding are shown. The first column contains the databases. The second shows the number of continuous attributes (NC), if any, for each database. Likewise, the next column gives the number of discrete attributes (ND) along with the total number of different values in brackets (NV). The column labeled as “Hybrid” gives the length of individuals (number of genes) with hybrid coding. Finally, the last one shows the length of individuals encoded with natural coding. These lengths were calculated easily from the second and third column. Hybrid