Natural Encoding for Evolutionary Supervised Learning

Natural Encoding for Evolutionary Supervised Learning Jesús S. Aguilar-Ruiz, Raúl Giráldez, and José C. Riquelme Abstract—Some of the most influential factors in the quality of the solutions found by an evolutionary algorithm (EA) are a correct coding of the search space and an appropriate evaluation function of the potential solutions. EAs are often used to learn decision rules from datasets, which are encoded as individuals in the genetic population. In this paper, the coding of the search space for the obtaining of those decision rules is approached, i.e., the representation of the individuals of the genetic population and also the design of specific genetic operators. Our approach, called “natural coding,” uses one gene per feature in the dataset (continuous or discrete). The examples from the datasets are also encoded into the search space, where the genetic population evolves, and therefore the evaluation process is improved substantially. Genetic operators for the natural coding are formally defined as algebraic expressions. Experiments with several datasets from the University of California at Irvine (UCI) machine learning repository show that as the genetic operators are better guided through the search space, the number of rules decreases considerably while maintaining the accuracy, similar to that of hybrid coding, which joins the well-known binary and real representations to encode discrete and continuous attributes, respectively. The computational cost associated with the natural coding is also reduced with regard to the hybrid representation. Our algorithm, HIDER*, has been statistically tested against C4.5 and C4.5 Rules, and performed well. The knowledge models obtained are simpler, with very few decision rules, and therefore easier to understand, which is an advantage in many domains. The experiments with high-dimensional datasets showed the same good behavior, maintaining the quality of the knowledge model with respect to prediction accuracy. Index Terms—Decision rules, evolutionary encoding, supervised learning. I. INTRODUCTION DECISION RULES are especially relevant in problems related to supervised learning. Given a dataset with continuous and discrete features or attributes, and a class label, we try to find a rule set that describes the knowledge within data or classifies new unseen data. When the feature is discrete, the rules take the form of “if , then class,” where the values are not necessarily all those that the feature can take. When the feature is continuous, typically the rules take the form of “if then class,” where This work was supported in part by the Spanish Research Agency CICYT under Grant TIN2004-00159 and in part by Junta de Andalucía (III Research Plan).J. S. Aguilar-Ruiz and R. Giráldez are with the School of Engineering, Pablo de Olavide University, 41013 Seville, Spain (e-mail: [email protected]; [email protected]). J. C. Riquelme is with the Department of Computer Science, University of Seville, 41004 Seville, Spain (e-mail: [email protected]). and are two real values belonging to the range of the feature and . For example, let us assume that we have a synthetic dataset that associates the weight (in kilograms) and eye color of a person with whether or not she/he will have a paper accepted in a relevant conference. The dataset is a sequence of tuples such as (60, green, no), (70, black, yes), etc. A rule describing the relationship among attribute values and class might be The search for these rules can be tackled with many different techniques, however, evolutionary algorithms (EAs) present particularly good performance when the search space is complex. Two critical factors influence the decision rules obtained by an EA: the selection of an internal representation of the search space (encoding) and the definition of an external function that assigns a value of goodness to the potential solutions (evaluation). In this work, a particular emphasis is placed on the physical representation of the encoding (the genotype: string of genes possessed by an individual) as compared with the features of the supervised learning problem to be optimized by the EA (the phenotype). The mapping operation between these two representations is also very important to define the search space and to guide the specific genetic operators. In principle, a single gene can affect several features in the phenotype (mapping one-to-m) or one feature in the phenotype can be controlled by multiple genes (mapping m-to-one). These two situations, named pleiotropy and poligeny [1], respectively, have a strong presence in naturally evolved systems. However, the one-to-one mapping is the most common in evolutionary systems, which represents a simplification of natural evolution. Winston [2] suggests that good generators of solutions in a search space should possess the following properties. • Completeness: they eventually produce all positions in a search space. • Nonredundancy: they never damage efficiency by proposing the same solution twice. • Informedness: they use possibility limiting information to restrict the solutions they propose accordingly. Moreover, a good evolutionary encoding should satisfy the following properties. • Coherence: it should not be possible to encode an element that has no semantic meaning. • Uniformity: every element will be represented by the same number of encodings and, if possible, will be unique (uniqueness). •Simplicity: the coding function must have easy application in both directions. •Locality: small modifications to the values (phenotype) should correspond to small modifications to the hypothetical solutions (genotype). •Consistency: futile or unproductive codings should not exist . •Minimality: the length of the coding should be as short as possible. On the other hand, internal redundancy should be avoided. A representation is said to contain internal redundancy when not all of the genetic information contained in a chromosome is strictly necessary in order to identify uniquely the solution to which it corresponds. It is also very common to find degeneracy in representations. A representation is said to exhibit degeneracy when more than one chromosome can represent the same solution. Degeneracy is often detrimental to genetic search [3], because it means that isomorphic forms are allowed. In some problems, the effect of one gene suppresses the action of one or more other genes. This feature of interdependency, called epistasis, should also be controlled and minimized. Therefore, the design of a new representation for EAs is not simple if we wish it to have a good performance. In fact, not only should the encoding preserve most of the properties mentioned above, but new genetic operators should also provide some advantages when the new encodings are used. In this work, we present a new evolutionary encoding to produce decision rules. Our approach, named “natural coding,”is a one-to-one mapping, and it only uses natural numbers to encode continuous and discrete features. This coding needs a new definition for the genetic operators in order to avoid the conversion from natural numbers to the values in the original space. These definitions are presented, and as it is shown in this paper, the EA can work directly with the natural coding until the end, when the individuals will be decoded to decision rules. This paper is organized as follows: in Section II, the work related to binary, integer, and real codings is presented; the motivation of our approach is described in Section III; the natural coding is presented in Section IV, together with the genetic operators associated with continuous and discrete attributes; the algorithm is illustrated in Section V, discussing the new evaluation method and the length of individuals; later, we compare our approach to the hybrid coding regarding the length of individuals and to C4.5 and C4.5 Rules to search for statistical differences about the error rate and the number of rules in Section VI; finally, the most interesting conclusions are summarized in Section VII. II. RELATED WORK Choosing a good genetic representation is critical for the EA to find a good solution for the problem because the encoding will have much influence on achieving an effective search. Binary, Gray, and floating-point chromosome encodings have been widely used in the literature because they have provided generally satisfactory results. Thus, few alternatives have been analyzed. Nevertheless, there are many ways of associating feature values to genes, which should be discussed in light of finding the best one for specific problems. Taking the aforementioned properties into account, we are going to analyze the most common representations for EAs, from the perspective of supervised learning. To our knowledge, little theoretical work has been developed in the field of evolutionary encoding. Many authors have approached several codings for specific applications, most of them for optimization or scheduling tasks, clustering, and feature selection. However, in supervised learning, the binary, real and hybrid (binary coding for discrete features and real for continuous) codings have commanded the attention of many researchers. A number of studies dedicated to EAs, beginning with Holland’s [4] made use of binary coding. The simplicity and, above all, the similarity with the concept of Darwinian analogy, have advanced its theoretical use and practical application. Several genetic algorithms-based concept learners apply binary coding to encode features with symbolic domains in order to induce decision rules in either propositional (GABIL [5], GIL [6], COGIN [7]) or first-order form (REGAL [8], [9], and DOGMA [10]). However, binary coding is not the most appropriate for continuous domains. In general, binary coding has been widely used, for instance, for feature selection [11] and data reduction [12]. In general, assuming that the interaction among attributes is not linear, in principle, the size of the search space is related to the number of genes used. For an individual with genes, the size of the search space is , where is the alphabet for the th gene. Traditionally, the same alphabet has been used for every gene, mostly the binary alphabet, so that . However, for a continuous feature with range , if we decide to use length to encode it, the error in the precision of that attribute would be (1) Therefore, if , the minimum encoding length, to ensure the precision is maintained, would be (2) Taking into account (2), the quantum defined by error will assure that the length is the least that guarantees a good precision for the mutation operator. However, the locality problem is not solved for binary representation. Gray encoding, where two individuals next to each other in the search space differ by only one bit, has been studied in depth [13], [14] and offers some advantages in this realm [15], although it suffers from the same lack of precision as binary coding. Both binary and Gray representations have some drawbacks when applied to multidimensional, high-precision problems. For example, for ten attributes with domains in the range [0,1], where a precision of three digits after the decimal point is required, the length of an individual is about 100. This, in turn, generates a search space size of about . For many problems, binary and Gray encoding are not appropriate because a value of 1 bit may suppress the fitness contributions of other bits in the genotype (epistasis) and genetic operators may produce illegal solutions (inconsistency). Some examples of other specific encodings are: Prüfer numbers to represent spanning trees [16] and integer numbers to obtain hierarchical clusters [17]. In real-valued coding [18], the chromosome is encoded as a vector of floating-point numbers of the same length as the solution vector. Each attribute is forced to be within a desired range and the operators are carefully designed to preserve this requirement. The motivation behind floating-point codings is to move the EA closer to the problem space. This coding is capable of representing quite large domains. On the contrary, its main theoretical problem is the size of the search space. Since the size of the alphabet is infinite, the number of possible schemes is also infinite and, therefore, many schemes that are syntactically different but semantically similar will coexist (degeneracy). In principle, any value can be encoded with an only (real) gene, but this could be avoided by using a discrete search space, where the mapping is one-to-one. However, instead of mapping real values to real values, we will map natural numbers to real intervals. For continuous domains, the intervals can precisely define a range of values within the domain. With this solution, the size of the search space is finite, and therefore so is the number of schemes as well. However, this search space reduction requires a prior discretization of continuous attributes, so the choice of the discretization method is critical. This idea will be explained in detail in Section IV-B. The approaches gathered in the bibliography, some of them based on evolutionary strategies, use real coding for machine learning tasks [19] or for multiobjective problems [20]. In SIA [21], real coding is applied to a real-world data analysis task in a complex domain. Finally, a combination of binary and real coding is used in [22] in order to benefit from the advantages of both codings by using the binary approach in discrete domains and real coding for continuous attributes. Fuzzy coding is another alternative for representing a chromosome. Every attribute consists of a fuzzy set and a set of degrees of membership to each fuzzy set [23]. Some other encoding strategies have been used in EAs. These include trees, matrix encodings, permutation encodings, and structured heterogeneous encodings to name a few. III. MOTIVATION The main shortcoming of using real coding to produce decision rules is that any value in the range of the attribute could be used as lower or upper bound of the interval for that attribute condition. For example, the C4.5 tool [25] only takes as possible values for the nodes of the decision trees the midpoints among two consecutive values of an attribute. This idea might be used to encode an individual of the genetic population so that only hypothetically good values will be allowed as conditions over an attribute in the rules. In a similar way, Bonissone et al. show in [24] some real-world applications where the knowledge of the problem domain benefits the use of EAs. To clarify this idea, we will use the dataset shown in Fig. 1, whose features are described in Section I. Observing the attribute weight (the first one), C4.5 would investigate as possible values: 56, 58, 59.5, 61, 63, 66, and 69. In other words, C4.5 is applying a local unsupervised method of discretization [26] Fig. 1. Labeled dataset with one continuous and one discrete attribute. since the class label is not taken into account in this process. The reduction of the number of values is only determined by the number of equal values for the attribute being considered. This unsupervised discretization is not a good choice to analyze possible limit values (either using entropy or any other criterion) for the intervals [27]. A number of remarkable supervised discretization methods have been included in the bibliography, including Holte’s1R [28] and the method of Fayyad and Irani [29]. In [30], a supervised discretization method, named unparametrized supervised discretization (USD) is presented. This method is very similar to 1R, although it does not need any input parameter. However, as the aim of this method is not to find intervals but cutpoints to be used as limits of further decision rules, we assume that any supervised discretization method would be appropriate for this purpose. As we will see below, if the discretization method produces cutpoints, then there will be possible intervals for the decision rules. Our goal consists in observing the class along with the discretization method and decreasing the alphabet size. Following the example in Fig. 1, we can note that it is only necessary to investigate the values 56, 61, 63, and 66, because they are values which produce a change of class. Therefore, this coding allows the use of all the possible intervals defined by every pair of cutpoints obtained by means of discretization, together with the feature range bounds. In short, if we are able to encode every possible interval and every possible combination of discrete values in such a way that the genetic operators make an efficient search of potential solutions, then the proposed representation will be appropriate for our purpose. Next, we are going to present and discuss this new encoding method, which will disclose interesting properties. The natural coding leads to a reduction of the search space size, which has a positive influence on the convergence of the EA with respect to the hybrid coding HIerarchical DEcision Rules (HIDER [22]). The prediction accuracy is maintained, while the number of rules is decreased, therefore using less computational resources. IV. NATURAL CODING In this section, we propose a new encoding for EAs in order to find decision rules in the context of supervised learning, together with their genetic operators, which will be presented in two independent subsections: discrete and continuous features, respectively. This coding has been named “natural”because it Fig. 2. Hybrid individual versus natural individual. only uses natural numbers to represent the set of intervals for continuous features and the set of values for discrete ones, which might take part in the decision rules. Regarding the properties mentioned in Section I, natural coding is complete, nonredundant, and informed. The internal redundancy and degeneracy properties are especially taken into account to perform an effective search for solutions. Moreover, it is coherent, unique, simple, consistent, and minimal. Locality is also satisfied as small variations of the natural numbers correspond to small modifications of the intervals they represent. Through the text, we will use a very simple dataset in order to explain the application of the genetic operators. This dataset (see Fig. 1) has a continuous attribute (weight in kilograms) with range [55, 70], a discrete attribute (eye color) with values black, green, blue , and a class (she/he is a candidate to have a paper accepted in a relevant conference) with values yes, no . Although the semantics of the natural coding have not yet been detailed, Fig. 2 illustrates the length of natural versus hybrid representations. It shows two individuals that represent the same rule. The method to encode these values will be shown later. Hybrid coding represents a rule comprising the union of two types of genotypes: real coding for the continuous attributes and binary coding for the discrete ones. Each condition associated with a continuous attribute is encoded by two real numbers representing the bounds of the interval for that attribute. Each condition related to a discrete feature is encoded by a vector of binary values. The size of this vector is equal to the number of distinct values of the attribute, so that 1 means that attribute value is present in the condition, and 0, absent. For instance, the rule in Fig. 2 is encoded by using the hybrid coding (left). The main problem of this encoding is that the search space is very large, since for each continuous feature we have to find two values in the range of the attribute. Another drawback is the length of the individuals, which might be very large when the discrete attributes take many distinct values. Our proposal tries to minimize the search space size and the length of the individuals by assigning only one natural number to each condition regardless of the type of the attributes. Thus, we attempt to limit the search space of valid genotypes and reduce the length of the individuals. When the attributes are discrete, this natural number is the conversion of the aforementioned binary string from the hybrid coding into a decimal number. For continuous features, the natural number is obtained by numbering all the possible intervals the condition can represent in an effective manner. In Fig. 2, a rule is encoded by the natural encoding (right), in contrast with the hybrid encoding (left). In this genotype, the meaning of 8 is the number assigned to the interval [56, 63] in the set of all valid intervals for , and the number 5 is the integer that represents the binary string 101 for . We can note that the natural coding is simpler, since the hybrid coding needs six genes to encode the rule, whereas the natural one encodes it with only three genes. In general, the hybrid one uses two genes for continuous features and for discrete ones, where is the number of different values that the feature can take. The natural coding gets to minimize the size of individuals, assigning only one gene to each feature. In general, to choose an encoding and a suitable set of genetic operators is not an easy task. An unacceptable amount of disruption can be introduced to the phenotype as a result of the inappropriate design of genetic operators or the choice of the encoding strategy. Sometimes degeneracy is seen as a beneficial effect to incorporate additional information. However, it is not always a positive phenomenon since the genetic operators might not increase the level of diversity of the next generation. In this case, the implicit parallelism would also be reduced. As a norm, encodings should be designed to naturally suppress redundant encoding forms, and genetic operators should be implemented in such a way that redundant forms do not benefit the operators. A. Discrete Features Several systems exist that learn concepts (concept learners) and use binary coding for discrete features. When the set of attribute values has many different values, the length of the individual is very high so that a reduction in length might have a positive effect on speeding the algorithm. In the following discussions, we will assume that a discrete feature is encoded by a single natural number (one gene), and we will analyze how to apply the crossover and mutation operators such that the new values retain the meaning that they would have had with a binary coding. The new value will belong to the interval , where is the number of different values of the attribute. With the natural coding for discrete attributes, a reduction of the size of the search space is not obtained by itself, but the individuals are better guided through the search space to look for solutions when the specifically designed “natural genetic operators”are applied. 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 feature must satisfy for an example to be classified. If a value is included in the condition, its corresponding bit is equal to 1, otherwise, it is 0. The natural coding for this gene is the conversion of the binary number into a natural number. Table I shows an example for a discrete feature with three different values: black, green, and blue. 1) Natural Mutation: Following the example in Table I, when a value is selected for mutation, for example, 3 , there are three options: 111, 001, and 010, equivalent to the numbers 7, 1, and 2, respectively. First, we assign the natural number corresponding to each binary number. The mutation of each value would have to be TABLE I CODING FOR A DISCRETE ATTRIBUTE TABLE II MUTATION VALUES FOR DISCRETE ATTRIBUTES some of the values shown in Table II. For example, possible mutations of 0 are the values 1, 2, and 4. Definition 1 (Natural Mutation): Let be the value of a gene of an individual, then the natural mutation of the th bit of , denoted by , is the natural number produced by changing that th bit % (3) where is the number of values of the attribute; are the possible mutated values from ;%is the rest of the integer division; and is the integer part. Example 1: For example, according to Table II, the possible mutation values for will be 4, 7, and 1 % % % It is worth noting that we do not need to know the binary values, as (3) takes a natural number and provides its natural mutations. Definition 2 (Mutation Set): Let be the value of a gene, we define mutation set, , as the set of all valid mutations for a natural value (4) where is the natural mutation of the th binary bit. Example 2: From Example 1, . Note that every discrete feature value set represented by a natural number can be mutated by using (4), generating a set of natural numbers which represents new discrete feature value sets. Therefore, binary values do not appear in the population. As shown in Example 2, from the value , the possible values are and . 2) Natural Crossover: Definition 3 ( -Order Mutation): Let be a set of natural numbers, let us define the -order mutation, and it will be denoted as , as follows: . . . (5) Definition 4 (Natural Crossover): Let and be the values of two genes from two individuals for the same feature. The gene of the offspring will be obtained from the values belonging to the first nonempty intersection between the -order mutations. Let , and , then (6) Example 3: Let us assume that we have the values 6(110) and 3(011). We include the current values into the mutation set since the offspring could be similar to the parents. Thus, 6 mutates to and 3 mutates to . As both genes share 2(010) and 7(111), any of them could be the offspring from 6 and 3. It is possible that the intersection is the parents (for example, for 1 and 3, as the schema is the same for both, 0*1). Example 4: Lets assume that we have the worst case, the values 1(001) and 6(110), which have no bits in common. The intersection between the first two mutation sets is empty. The process is shown next The intersection will be , and any of them will be the valid offspring for . Fig. 3 shows a more explanatory example of the natural genetic operators for the discrete attribute with values . The gene encoded as 11 has the binary code 01011. The block on the right gives the possible mutations, where the changed bit is shown in bold. The gene encoded as 19 follows the same scheme. Therefore, the set of mutations of both 11 and 19 are and , respectively. The crossover between these two genes is taken from the set . Fig. 3. Example of mutation and crossover operators for a discrete attribute with five values f white, red, green blue, black g . TABLE III INTERVALS CALCULATED FOR THE CONTINUOUS ATTRIBUTE WITH RANGE [55,70]. THE BOUNDARY POINTS ARE f 55 ; 56 ; 61 ; 63 ; 66 ; 70 g .ANATURAL NUMBER ISASSOCIATED WITH EVERY CORRECT INTERVAL B. Continuous Features Using binary encoding in continuous domains requires transformations from binary to real for every feature in order to apply the evaluation function. Moreover, when we convert binary into real, the precision might be affected. Ideally, the mutation of the less significant bit of an attribute should include or exclude at least one example from the training set. The real coding seems more appropriate with real domains, simply because it is more natural to the domain. A number of authors have investigated nonbinary EAs theoretically [31]–[35]. In this sense, each gene would be encoded with a float value. Two float values would be needed to express the interval of a continuous feature. As the range of continuous attributes is infinite, it would be interesting to reduce the search space size, as the computational cost should be lower. This reduction should not have negative influence on the prediction accuracy of the solutions (decision rules) found by the EA. The first step, therefore, consists in diminishing the cardinality of the set of values of the attribute. 1) Reducing the Cardinality: First, we will analyze what intervals inside the range of the attribute tend to appear as intervals for a potential decision rule obtained from the natural coding. As mentioned before, this task could be solved by any supervised discretization algorithm. In [27], it is carried out via an experimental evaluation of various discretization schemes in different evolutionary systems for inductive concept learning, where our tool with natural coding, named HIDER*, was also analyzed. This study showed that HIDER* was robust for any discretization method [27, Table II], although USD [30] turned out to be the most stable discretizer used in that experiment (the last column in [27, Table IV]). Once the vector indicating the boundaries for the intervals is obtained (vector of cutpoints), we assign natural numbers to any possible combination, as shown in Table III. Example 5: Let us assume from the dataset in Fig. 1 that the output of the discretization algorithm is the vector of cutpoints for the attribute weight (note that the upper and lower bounds of the feature range are also included: 55 and 70). We just need to observe the changes of labels when the examples are ordered by the attribute weight (particular situations of this strategy are discussed in [30]). The possible intervals to be generated from those values are shown in Table III. Each interval is identified by a natural number, for example, the interval [61,66] will be referenced by the natural number 14. Table III shows 6 cutpoints, which can generate 15 possible intervals. The number of intervals defines the size of the alphabet for such attribute and depends on the number of cuts k, exactly k k . In Table III, a natural number (in bold), beginning by 1, from left to right and from top to bottom, is assigned to each interval. These “natural”numbers will help us to identify such intervals later. 2) Transitions: Once the necessary number of cutpoints has been calculated, we know the elements of the new alphabet . From now, we will analyze the mutation and crossover operators for this encoding. Table III defines the new alphabet . Definition 5 (Row and Column): Let be the value of the gene, and let row and col be the row and the column, respectively, where is located in Table III. The way in which row and col are calculated is: (% is the remainder of the integer division) k %k(7) Example 6: Let and , and k. Then Therefore, as we can see in Table III, 3 is in row 1 and column 3, and 20 is in row 4 and column 5. Definition 6 (Boundaries): Let be the value of the gene, we name boundaries of to those values from Table III that limits the four possible shifts (one by direction): left, right, up and down, and they will be denoted as leftb (left bound), rightb (right bound), upperb (upper bound), and lowerb (lower bound), respectively, and they will be calculated as k k k k k k k (8) Example 7: The number 9 could reach up to 7 to the left, up to 10 to the right, up to 4 to the top and up to 19 to the bottom (see Table III) Definition 7 (Shifts): The left, right, upper, and lower adjacent shifts for a value will be obtained (if possible) as follows: k k(9) We define horizontal and vertical shifts as all the possible shifts for a given row and column, respectively, including itself k k(10) k k(11) Fig. 4. Mutation and crossover for continuous attributes. Example 8: From Example 7, the adjacent shifts of 9 will be and the horizontal and vertical shifts of 9 will be 3) Natural Mutation: A mutation consists in selecting a near interval to the one that contains the value . For example, observing Table III, if the number of cutpoints is k, and , there are four possible mutations ;if , there are three possible mutations ;if , there are two possible mutations ; and finally, if , there is only one possible mutation . Definition 8 (Natural Mutation): Let be the value of the gene, the natural mutation of , denoted by , is any near value to by using the shifts and distinct from (12) where . Example 9: Thus, , i.e., . Now, one out of the three values could be selected as mutation. When a gene encodes a continuous feature, the mutation consists in selecting an interval close to it. This is easy to see in Fig. 4, which shows the same example as Table III. For example, gene 14 is the interval [61, 66] and it can be mutated into another interval belonging to the set and (genes 9, 13, 15, and 19). However, gene 5 can only be transformed into 4 and 10, because there are no genes above or to the right of it. 4) Natural Crossover: Given two parents, the crossover should ideally produce a valid offspring, sharing the genetic material of both parents. Definition 9 (Natural Crossover): The natural crossover between two values and , denoted by is obtained as follows: (13) We can observe in Table III that the interesting values are in the intersection between the row and the column where both values being crossed are placed. Only when the values and are located in the same row or column, the interval will be inside the other. Example 10: Thus The general case of crossover between two parents is illustrated in Fig. 4. The possible offspring is formed by those numbers in the intersection between the row and the column of both parents. For example, the crossover between genes 5 and 14 (within squares) generates as offspring genes 4 and 15 (within circles). In Table III, we can see that this offspring makes sense because it uses every boundary from the parents. V. ALGORITHM HIDER is a tool that produces a hierarchical set of rules [22]. When a new example is to be classified, the set of rules is sequentially evaluated according to the hierarchy. 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 it 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 applying the mutation and crossover operators. In each generation, some individuals are selected according to their goodness and they are included in the next population along with their offspring. The pseudocode of HIDER is shown in Fig. 5. The main algorithm is a typical sequential covering method [36], where the function that produces each rule is an EA. Each call to this function (line 8) generates only one rule that is included in the final set of rules (line 9) and 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 or a percentage of the training set has been already covered . The function EvoAlg has a set of examples as its input parameter. It returns a rule that 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 initializing the population, the for-loop repeats the evolutionary process a number of times that 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 generation (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 Fig. 5. Pseudocode of HIDER. method. Once the loop finishes, the best individual of the last generation is returned. Equation (14) gives the fitness function used by HIDER during the evaluation process. The greater the value, the better the individual is (14) where is an individual; is the number of examples being processed; is the class error, i.e., the number of examples belonging to the region defined by the rule , which do not have the same class; is the number of examples correctly classified by ; and gives the size proportion of the search space covered by the rule. A description about the coverage factor and its positive influence on the results can be found in [22]. A. Evaluation A very important aspect of our approach is that the examples of the training file (dataset) are also encoded with natural coding, so that each example of the dataset has the same structure as a rule. If an attribute is continuous, the gene that represents it in an encoded example is the smallest interval that includes the value of the attribute in such example. For example, according to Table III, if the attribute takes the value 64, then the gene is 19, since the smallest interval that includes 64 is [63,66]. However, if the attribute takes the value 65, it will be encoded with the number 19 as well. This means that the original dataset Fig. 6. Example of evaluation. is reduced before applying the EA, only associating a weight to each example. Thus, a gene that represents a continuous attribute can take only a natural number belonging to the main diagonal of the coding table. For discrete attributes, we will use Table I to encode the values of examples. For example, if the attribute takes the value “blue,”then the gene is 1. Thus, the example (64, blue, no) is encoded as (19,1,0) (see Fig. 6). The encoding of examples is carried out to speed up the evaluation process, since to decode all of the rules in each evaluation implies higher computational cost. For instance, let be the condition (encoded interval) that a rule establishes for a continuous attribute , and let be the encoded value that such attribute takes in an example. The row and column of and are and , respectively, in the coding table, and the value fulfils the condition if “”and “.”Therefore, to know whether or not an example is covered by a rule only consists in comparing four numbers. For discrete attributes, the evaluation is even easier. A condition covers a discrete value (both encoded) if “,”“&”being the binary conjunction operator. In short, an example is covered by a rule if for each feature , the example value is covered by the rule value, ,as shown in the equation at the bottom of this page. For example, in Fig. 6, we can see that has the value 10, so observing Table III, the values 7, 8, 9, 10, 13, 14, 15, 19, 20, and 25 would correspond to intervals that are inside the interval whose associated value is 10. For the , with value 5, the values 1, 4, and 5 would satisfy the binary conjunction operation with the value 5. Regarding the encoded examples, Fig. 6 shows that different original examples are encoded to the same encoded example, for instance, (7,2,0) and (25,4,1). This makes faster the evaluation as the examples (7,2,0) and (25,4,1) would have weight equal to 2. B. Length of Individuals A set of datasets from the UCI Repository [37] has been chosen to run the experiments. In Table IV, the length of individuals of the genetic population for the hybrid and natural coding are shown. The first and second columns are the dataset’s identifiers and names, respectively. The third shows the number of continuous attributes (NC), if any, for each dataset. Likewise, the next column gives the number of discrete features (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 third and fourth column. The hybrid coding uses two genes to represent continuous attributes and a number of genes for discrete ones, being the number of different values of the attribute. On the other hand, the natural coding uses only one gene for each attribute, regardless of its type (continuous or discrete). Thus, the length for hybrid individuals is , whereas for natural individuals is . As we can see, the natural coding noticeably decreases the length of individuals. On average, it obtains a reduction greater than 63% with respect to hybrid individuals, which also leads to a search space size reduction. However, the space size reduction is not due to the length, but to the discretization of continuous