Fuzzy modeling by hierarchically built fuzzy rule bases

Fuzzy modeling by hierarchically built fuzzy rule bases Oscar Cord on a , Francisco Herrera a,* , Igor Zwir b a Department of Computer Science and Arti®cial Intelligence, ETS de Ingeniera Informatica, University of Granada, Avda. Andalucia 38, 18071 Granada, Spain b Department of Computer Science, University of Buenos Aires, 1428 Buenos Aires, Argentina Received 1 August 2000; accepted 1 March 2001 Abstract Although Mamdani-type fuzzy rule-based systems (FRBSs) became successfully performing clearly interpretable fuzzy models, they still have some lacks related to their accuracy when solving complex problems. A variant of these kinds of systems, which allows to perform a more accurate model representation, are the so-called approximate FRBSs. This alternative representation still cannot avoid the problems concerning the fuzzy rule learning methods, which as prototype identi®cation algorithms, try to extract those approximate rules from the object problem space. In this paper we deal with the previous problems, viewing fuzzy models as a class of local modeling approaches which attempt to solve a complex problem by decomposing it into a number of simpler subproblems with smooth transitions between them. In order to develop this class of models, we ®rst propose a common framework to characterize available approximate fuzzy rule learning methods, and later we modify it by introducing a fuzzy rule base hierarchical learning methodology (FRB-HLM). This methodology is based on the extension of the simple building process of the fuzzy rule base of FRBSs in a hierarchical way, in order to make the system more accurate. This ¯exibilization will allow us to have fuzzy rules with dierent degrees of speci®city, and thus to improve the modeling of those problem subspaces where the former models have bad performance, as a re®nement. This approach allows us not to have to assume a ®xed number of rules and to integrate the good local behavior of the hierarchical model with the global model, ensuring a good global performance. Ó2001 Elsevier Science Inc. All rights reserved. International Journal of Approximate Reasoning 27 (2001) 61±93 www.elsevier.com/locate/ijar * Corresponding author. Tel.: +34-58-24-40-19; fax: +34-58-24-33-17. E-mail addresses: [email protected] (O. Cord on), [email protected] (F. Herrera), [email protected] (I. Zwir). 0888-613X/01/$ - see front matter Ó2001 Elsevier Science Inc. All rights reserved. PII: S 0 8 8 8 - 613X(01)00034-2 Keywords: Fuzzy modeling; Mamdani-type fuzzy rule-based systems; Fuzzy rule base; Genetic algorithms; Hierarchical fuzzy clustering; Approximate fuzzy rules 1. Introduction Nowadays, one of the most important areas for the application of fuzzy set theory as developed by Zadeh [35] are fuzzy rule-based systems (FRBSs). These kinds of systems constitute an extension of classical rule-based systems, because they deal with fuzzy rules instead of classical logic rules. Thanks to this, they have been successfully applied to a wide range of problems from dierent areas presenting uncertainty and vagueness in dierent ways [3,21,24,26]. There are at least two dierent kinds of FRBSs in the literature, the Mamdani and Takagi±Sugeno±Kang (TSK), which dier on the composition of the rule consequent. The use of one or the other depends on the fact that the main requirement is the interpretability or the accuracy of the model, respectively. Although the Mamdani-type FRBS presents the maximum description level, it is not as accurate as desired in some cases. Therefore, at least two things could be done to improve the accuracy of this model type. On the one hand, we can preserve the linguistic representation of this model and perform successive re®nements on it, improving its accuracy without losing interpretability to a high degree [13,15]. On the other hand, we can improve the model by using a more accurate representation. To do so, we focus our attention on a variant of Mamdani-type, the so-called approximate FRBSs [1,2]. These kinds of FRBSs are the ones that have fuzzy rules composed of fuzzy variables ± with a fuzzy set associated de®ning their meaning ± that do not take as a value a linguistic term, like in the case of linguistic variables [36±38], but a real fuzzy set. Even though a great deal of research activity has focused on the development of methods to build or re®ne approximate FRBSs from numerical data, they still present some problems. To deal with these kinds of models and methods, in this paper we ®rst propose a common framework to group and characterize fuzzy rule generation methods (FRG-methods), i.e., methods for learning approximate rules. Later, we introduce a modi®cation of this framework in order to solve many of the former problems by designing a fuzzy rule base hierarchical learning methodology (FRB-HLM). The main purpose of this methodology is to automatically generate more accurate approximate fuzzy models by performing successive re®nements of initial models generated by FRG-methods. To do so, we introduce the concept of layers, which was previously applied to descriptive models in [13,15]. In this extension, the fuzzy rule base (FRB) is constructed by the development of set of layers or FRBs, each one containing 62 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 fuzzy rules with a dierent speci®city level, i.e. dierent fuzzinesses. These kinds of rules are called hierarchically generated fuzzy rules. In order to do that, this paper is set up as follows. In Section 2, a description of the approximate FRBS model is introduced, as well as its advantages and drawbacks. In this section, we also consider some problems associated with the FRG-methods, and propose a common framework for dealing with them. In Section 3, we introduce the FRB-HLM as a solution to many of the previous problems and perform a description of the hierarchically built FRB philosophy and the relation between its components. Next, the algorithm is explained in detail. In Section 4, the fuzzy modeling process obtained from FRBHLM and well-known inductive FRG-methods is applied to solve three different applications. Finally, in Section 5, some concluding remarks are pointed out. 2. Approximate FRBSs In this section we ®rst compare the approximate FRBSs with the linguistic ones, highlighting their advantages and lacks. Next, we characterize the FRGmethods, which built approximate FRBSs, providing a common framework to deal with them. Finally, the drawbacks of the FRG-methods are also discussed. 2.1. Approximate versus linguistic FRBSs As we have said, there are at least two dierent forms of fuzzy modeling: Mamdani-type and TSK FRBSs. The former presents the maximum description and interpretability level, but it is not as accurate as desired in some complex problems. In opposite, the second approach performs the more accurate approximation with the drawback of losing interpretability in their consequents. The lack of accuracy of Mamdani-type models is due to some problems related to the linguistic rule structure considered, which are a consequence of the in¯exibility of the concept of linguistic variable [36±38]. A summary of these problems may be found in [1,4,8], and is brie¯y enumerated as follows: ·There is a lack of ¯exibility in the FRBS because of the rigid partitioning of the input and output spaces. ·When the system input variables are dependent themselves, it is very hard to fuzzy partition the input spaces. ·The homogenous partitioning of the input and output spaces when the input±output mapping varies in complexity within the space is inecient and does not scale to high-dimensional spaces. ·The size of the FRB directly depends on the number of variables and linguistic terms in the system. Obtaining an accurate FRBS requires a signi®cant O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 63 granularity amount, i.e., it needs the creation of new linguistic terms. This granularity increase causes the number of rules to rise signi®cantly, which may take the system to lose the capability of being interpretable for human beings. A variant of these Mamdani-type FRBS-based modeling approaches has been proposed in the last few years, the approximate FRBS [1,4]. It is based on the former approach but considers the lack of accuracy as a major drawback. While the former descriptive FRBSs have associated a knowledge base composed of a database ± containing linguistic partitions ± and a rule base ± composed of linguistic rules which make use of these linguistic partitions ±, the approximate ones only have to de®ne an FRB. This happens because their aproximate fuzzy rules contain variables which are dierent locally de®ned fuzzy values. In order to distinguish between the type of modeling performed to obtain Mamdani-type and approximate FRBSs, we are going to refer to the former as linguistic modeling, and to the latter as fuzzy modeling. That is, linguistic models are performed by descriptive Mamdani-type rules or linguistic rules, and fuzzy models are developed by approximate Mamdani-type rules or fuzzy rules. In the following some distinctions between both types of modeling are given: ·Linguistic modeling makes use of fuzzy rules composed of linguistic variables that take values in a term set with real-world meaning (linguistic rules). These kinds of models are characterized by the fact that their main requirement is the system interpretability. ·In fuzzy modeling, the fuzzy rules are composed of fuzzy predicates without a linguistic meaning, i.e., the variables forming the rules do not take as a value a linguistic term with a fuzzy set associated de®ning their meaning, but a real fuzzy set. These models pretend to be more accurate than the former ones. The choice between how interpretable and how accurate the model must be, usually depends on the user's needs for a speci®c problem and will condition the kind of FRBS selected to model it. As well as that, in this paper we will focus on developing more accurate fuzzy models by an FRB-HLM, which provides approximate solutions to dierent problems, especially real-world problems. 2.2. Approximate FRBS features Approximate FRBSs have some interesting advantages that get them to be very suitable for fuzzy modeling purposes in many cases [8]: ·The expressive power of the rules, that present their own speci®city in terms of the fuzzy sets involved in them, thus introducing additional degrees of freedom in the system. ·The number of rules is adapted to the complexity of the problem, needing less rules in simple problems, and being able to use more rules if it is neces64 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 sary. This is likely to be of bene®t in tackling the course of dimensionality when scaling to multidimensional systems. These facts, which allow approximate FRBSs to be more accurate in complex problems, have unfortunately some drawbacks associated [1]: ·The FRB readability is lost because there is no global interpretation of the variables considered. In spite of this, approximate FRBSs locally describe the system behavior in a similar way to other models like neural networks, but in a more descriptive way. ·The approximation capability causes an excessive speci®city with bad generalization, sometimes obtaining an unwanted over®tting. Although fuzzy and linguistic modeling are not incompatible, but complementary, in this paper we focus our attention in the former, and consequently on the model accuracy. 2.3. Approximate FRBSs learning methods (FRG-methods) as prototypeidenti®cation algorithms Some automatic techniques have been proposed to learn a proper FRB for an approximate FRBS to solve a speci®c problem. The accuracy of the FRBS in solving this problem will depend on the intrinsic characteristics of the problem and on the mentioned learning tasks. In spite of these dependences, we will attempt to characterize these learning methods which we have labeled as FRG-methods. Regarding [29,40], we can say that basically an FRG-method does its job as a prototype-identi®cation algorithm, which performs the optimization of a functional QF;Modelc that measures the extent by which the parameterized model Modelc®ts the subset Fof the object being described (see Fig. 1). From this perspective, the problem is formulated as a clustering problem in the sense that extracted subsets meet, to some extent, the requirements imposed by the model collection in the same way that elements of a clustering partition satisfy the constraint that their members be as similar as possible [29,40]. This point of view follows the original ideas of Ruspini [28], later expanded by Bezdek introducing various methods centered upon the notion of prototype [5]. The basic idea of summarizing a dataset by a number of representative prototypes ± objects lying in the same space as the sample points ± was later extended in many signi®cant directions by relaxing this concept in a variety of ways, for example, line segments, ellipsoids, etc. [7]. In this paper we particularize this concept by considering these prototypes as being fuzzy rules [2,17,18]. Having these concepts in mind, FRG-methods can be seen as identi®cation algorithms with fuzzy rule prototypes, i.e., fuzzy model builders whose main purpose is to extract the most suitable set of fuzzy rules from an object (input± output data) according to an optimization measure, which evaluates the quality of the approximation. Additionally, they organize results and O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 65 summarize them by an interestingness criterion, in order to provide a more compact and useful representation of the salient structures. In order to illustrate this situation, consider for example the Weighted Counting Algorithm introduced by Bardossy and Duckstein [3] which, as can be seen in Appendix A, identi®es approximate fuzzy rules from a set of input± output data (object F) for an approximate fuzzy model Modelc. The quality of identi®ed candidate substructures (rule premises) is measured in base of its degree of ful®llment, i.e., a covering criterion (QF;Modelc). These extracted rules could also be summarized by, for example, a user-based relation of interest which imposes a maximum acceptable number of rules. 2.4. Drawbacks of the FRG-methods All of these models generated by FRG-methods have the same drawbacks that prototype identi®cation methods have, and all of them try to give their dierent own solutions, which become particular to the corresponding method: ·Simple formulation of the prototype-identi®cation problem as an optimization of a functional would simply result in a large collection of very speci®c rules with small extent and high accuracy, but with poor generalization. Smaller rather than larger signi®cative sets with high generalization power would be preferred. ·The determination of a complete clustering or a partition of the dataset into a ®xed number of prototypes becomes a big deal for a long time. Approximate Fuzzy Rules : 3 R IF x is THEN y is : 2 R IF x is THEN y is : 1 R IF x is THEN y is MODEL STRUCTURE PROTOTYPE OBJECTS RELATIONS OF INTEREST SUMMARIZATION MODEL IDENTIFIED (Rules) Final Rule Set Model FRB-HLM IDENTIFICATION ALGORITHM Fig. 1. FRG-methods as prototype-identi®cation algorithms. 66 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 To deal with these problems, in the following section we will present an FRBHLM in order to build a FRB with the purpose of solving some of the above drawbacks. 3. Fuzzy rule base hierarchical learning methodology To overcome some of the drawbacks of the approximate FRBSs (Section 2.4) and of the FRG-methods (Section 2.3), we propose a FRB-HLM which, as a meta-method, modi®es the framework shown in Fig. 1 and considers the following points: ·On the one hand, we would like to implement a sort of trade-o between the extensionality and the accuracy of the models generated, having in mind that rules which perform good explanations tend to be limited in extent while those that, conversely, are capable of describing large subsets of the dataset, do it so poorly. ·On the other hand, we will adopt a more general treatment than that of a typical clustering problem, emphasizing the sequential isolation of individual clusters [23] rather than determination of a full clustering. Furthermore, we do not want to assume a priori knowledge of the total number of clusters ± rule prototypes ± requiring that the set of all clusters be an exhaustive partition of the complete object. To do so, the FRB-HLM will modify the initial model identi®ed by a FRGmethod in an iterative way, performing a gradual re®nement of it. Moreover, it will also modify the summarization process seen in Fig. 1, by adding a rule selection process to obtain a compact set of rules that have good cooperation between them and to remove the unnecessary ones. 3.1. Keypoints of the FRB-HLM Our approach owes much to those clustering generalizations mentioned in Section 2.3 and to the notion of hierarchical clusters [17,19]. It is also closely related to other modeling techniques which work with fuzzy granules, fuzzy graphs, etc. [27,39]. As them, we should also answer some important questions which concern the structures (clusters, rules, granules, etc.) used by the former techniques: How can rules, granules, clusters, etc. be partitioned? This question is related to some aspects like the compactness of a cluster, measures inside the cluster, measures between clusters, granule perimeters, rule scopes, etc. O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 67 How many rules, granules, clusters, etc. could exist? This is concerned with system comprehension, accuracy, over®tting, etc. In order to give an answer to these questions, and to previous problems, in the following we list some keypoints of the FRB-HLM: ·Dynamic rule expansion or partition depending on the FRG-method used, in order to take advantage of its intrinsic capabilities. These methods sometimes perform this task in a more static or dynamic way according to their philosophy. ·Iterative methodology which, as is done by hierarchical clustering techniques, emphasizes the sequential isolation of clusters rather than a full clustering. Hence, we do not have to assume an a priori ®xed number of rules. ·Gradual localized re®nements on bad modeled zones rather than in the whole problem domain, as a regulation among extensionality and precision. This task is controlled by an expansion factor, which also acts as an over®tting foreseer. ·Summarization by rule selection, in order to integrate the local behavior of the hierarchically built model with the global one of the whole model, ensuring a good performance. We should note that there are many proposals in order to answer each one of the former questions or to solve the said problems [2,27,29,39]. Some of their skills will be considered as extensions of the present methodology in future works. In the following subsections, the composition of the hierarchically built FRB and the methodology will be described in detail. 3.2. Hierarchically built fuzzy rule base In this section we present a ¯exible hierarchical process to de®ne the FRB structure ± based on previous keypoints ± that allows us to solve some of the lacks described in Sections 2.2 and 2.4, and consequently to improve the approximate fuzzy models performance/accuracy. The hierarchical process is based on the generation of a set of layers, each one becoming an FRB which contains fuzzy rules with a dierent degree of speci®city or extent, i.e., fuzziness layertFRBt[ i Rt i with FRBtbeing the FRB built in iteration tformed by approximate fuzzy rules Rt i, according to the present methodology. From now on and for the sake of simplicity, we are going to refer to the components of a FRBtas t-fuzzy rules. These t-fuzzy rules are organized as a hierarchy, where the order is given by increasingly more speci®c input subspaces, i.e., the input support extent covered by the antecedents of the approximate fuzzy rules. This can be regarded as 68 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 a kind of information quantization included in the fuzzy variables of the rules, i.e., their fuzziness. For example, given two successive layers tand t1, the fuzzy input subspace covered by a t-fuzzy rule is more general (larger) than the ones embraced by each one of the (t1)-fuzzy rules derived from it [25]. From this point of view, the successive approximate fuzzy rules generated can be seen as an input subspace re®nement of previous layer fuzzy rules. This structure is illustrated in Fig. 2. As is seen, the representation takes the form of a tree, where the root represents the entire problem domain space, and the nodes represent good performance t-fuzzy rules (light grey rectangles), which model fuzzy input subspaces that do not require further decomposition, or more speci®c (t1)- fuzzy rules that model decomposed subspaces from a bad performance t-fuzzy rule (black rectangles). This process is performed in an iterative way. Thus, good t-fuzzy rules and new generated (t1)-fuzzy rules compose the new level of the tree generated in iteration t1, i.e., layer (t1). How can we develop a FRBt1from a FRBtin order to create the ®nal more accurate FRB? Each FRBtis formed by a collection of approximate Mamdani-type fuzzy rules Rt i:IF x1is St i1and ... and xmis St im THEN yis Bt i with x1;...;xmand ybeing the input fuzzy variables and the output one, respectively; and with St i1;...;St im,Bt ibeing the fuzzy sets. As has been said, each individual fuzzy rule directly contains the meaning describing it, i.e., each variable has a fuzzy set associated as shown in Fig. 3. Layer 1 - 1 FRB Layer 2 - 2 FRB Layer 3 - 3 FRB . . . Layer t - t FRB + Fuzziness - Specificity - Fuzziness + Specificity 1 i R 2 2, i R 3 1,1, i R3 2,1, i R3 2, i R t i R1,...,1,1, t Li R,...,2,1, t i R1,...,2,1, t i R2,..,2, t i R1,..,2, 2 1, i R Fig. 2. Hierarchically built FRB. O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 69 with CFRRt ibeing the image of the expanded fuzzy rule Rt i, i.e., the candidate fuzzy rules to be in the FRBt1from rule Rt i,ANTRt ibeing the product of the support set of each antecedent fuzzy term of the rule Rt i ANTRt isuppSt i1suppSt im and CONRt ibeing the support set of the consequents which in case of using CCS is de®ned as CONRt isuppBt i and in case of using UCS as CONRt iV with Vbeing the domain where the consequent is de®ned. Step 2. Summarization process. Obtain a joined set of candidate fuzzy rules (JCFR) performing the union of the group of the new generated (t1)-fuzzy rules and the former good performance t-fuzzy rules: JCFR FRBt good [[ i CFRRt i ! with Rt i2FRBt bad. Step 3. FRB selection process. Simplify the set JCFR by removing the unnecessary rules from it, in order to generate an FRBt1with good cooperation. In this paper we consider a genetic process [11,20,22] to put this task into eect, but any other technique could be considered FRBt1SelectionJCFR: In the JCFR ± where there are coexisting rules generated in dierent layers ± it may happen that a complete set of (t1)-fuzzy rules, which replaces an expanded t-fuzzy rule, does not produce good results. However, a subset of this set of (t1)-fuzzy rules may work properly, with less rules that have good cooperation between them and with the good rules from the previous layer. Thus, the JCFR set of rules generated may present redundant or unnecessary rules making the model using this FRB less accurate. The genetic rule selection process [11,20] is based on a binary coded genetic algorithm (GA) in which the selection of the individuals is performed using the stochastic universal sampling procedure together with an elitist selection scheme, and the generation of the ospring population is put into eect by using the classical binary multipoint crossover (performed at two points) and uniform mutation operators. 76 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 The coding scheme generates ®xed-length chromosomes. Considering the rules contained in JCFR counted from 1 to z,anz-bit string Cc1;...;cz represents a subset of rules for the FRBt1, such that IF ci1 THEN Ri2FRBt1ELSE Ri62 FRBt1: The initial population is generated by introducing a chromosome representing the complete previously obtained rule set, i.e., with all ci1. The remaining chromosomes are selected at random. As regards the ®tness function FCj, it is based on a global error measure that determines the accuracy of the FRBS encoded in the chromosome, which depends on the cooperation level of the rules existing in the JCFR. We usually work with the MSE over a training data set, as was previously de®ned, although other measures may be used. Step 4. Model validation process. The ®nal model is either accepted as proper for the given purpose or it is rejected generating another iteration of the process. Although many indexes can be used to measure the quality of linear or nonlinear systems after an identi®cation loop [2,7], we consider a monotonic MSE measure on the training and test sets, combined with a previously de®ned maximum number of iterations Tmax, which is based on a trade-o between the complexity and the accuracy of the model generated. This measure is computed as: IF MSEFRBt1ETDS 6MSEFRBtETDS and MSEFRBt1ETST 6MSEFRBtETST and t<Tmax THEN t t1; Goto Step 1 ELSE FRBfinal FRBtor FRBt1: We should note that for the sake of simplicity in the present implementation, we only keep the last two layers of the FRB in order to allow the validation of the algorithm output model. Therefore, at last we only select as FRBfinal one of these two FRBs , i.e., FRBtor FRBt1, the one with better performance. 4. Examples of application: experiments and analysis of results With the aim of analyzing the behavior of the proposed methodology, two dierent FRG-methods aligned with the characteristics presented in this paper have been chosen. The ®rst is the one proposed by Bardossy and Duckstein [3], Weighted Counting Algorithm (WCA), and the second is a well-known fuzzy clustering method based on Bezdek's work, the Fuzzy C-means (FCM) [5±7]. Both methods are brie¯y described in Appendix A. O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 77 In this section, FRB-HLM will be combined with the former FRG-methods to model three dierent applications: twothree-dimensional functions [9,11] and a real-world electrical engineering distribution problem in Spain [12,30,31]. In order to do this, we have organized this Section in three parts: a ®rst part of notation and parameters, a second of experiments and a ®nal one with an analysis of results for the experimental study. 4.1. Notation and parameters For the sake of simplicity, in the following applications we are going to refer to those experiments produced by the FRB-HLM by the following notation: FRB-HLMFRG-method;CS;t; where tis the number of layers or iterations with rule expansions performed by the methodology, and CS represents the type of consequent scope selected, i.e., CCS or UCS, e.g., FRB-HLM (FRG-method, CCS, 3). Two FRG-methods, WCA and FCM, will be used for the experimentation. The WCA is considered with two dierent interval initializations, both based on the extraction of the support set from fuzzy partitions [1]. The ®rst one, static initialization (S-WCA), is built based on a symmetrical and uniformly distributed fuzzy partition of three and ®ve fuzzy terms for initial and subsequent iterations of the algorithms [13], respectively. The second one, dynamic initialization (D-WCA), is performed by the use of a fuzzy clustering-developed fuzzy partition. To do so, in this paper we use FCM combined with a validation index which measures the partition quality and iteratively detects a good number of clusters [32]. Both methods are brie¯y described in Appendix A and summarized in Table 1. The general parameters used in all of these experiments are listed in Table 2. Table 1 Summarization of WCA and FCM tasks WCA FCM S-WCA D-WCA Symmetrical, uniformly distributed fuzzy partition Incremental application of FCM and validation index Incremental application of FCM and validation index Cluster center projections on the antecedent domains Clusters projection on antecedent and consequent variable domains Partition construction with a 0.5 cross level between adjacent fuzzy sets Support set extraction and intervals de®nition Rule construction by WCA philosophy Rule construction 78 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 In this contribution, we will use the minimum t-norm in the role of conjunctive and implication operator and the center of gravity weighted by the matching degree [10] as defuzzi®cation strategy. The results obtained in the experiments developed are collected in tables where MSEtra and MSEtst stand for the values obtained in the MSE measure computed over the training and test data sets, respectively, and % indicates the percentage in which the FRG-method models in the table are improved by the hierarchically built FRB-based models. #Rstands for the number of rules of the corresponding FRB. 4.2. Experiments We will show results comparing the eectiveness of the hierarchical learning methodology with both original FRG-methods (WCA and FCM) on the said three problems. We should note that the hierarchically built FRBs are initialized with the FRG-methods output, in order to allow the former comparison. In all cases we show examples applying CCS and UCS consequent scope. Additionally, in the real-world electrical problem we will also compare the results obtained by FRB-HLM with other techniques: classical regressions, multilayer perceptron and a linguistic modeling hierarchical learning methodology HSLR-LM [13,16]. Finally, we will analyze the eect of using dierent expansion factors a, showing the robustness of the FRB-HLM and its role as an accuracy-complexity regulator and over®ting controller. 4.2.1. Fuzzy modeling of an intermediate complexity multimodal three-dimensional function (F1) The expression of the selected function is shown as follows, along with the universes of discourse considered for the variables [9]. Its graphical representation is shown in Fig. 7. As may be seen, F1is an intermediate complexity multimodal function whose expression is shown as follows: Table 2 Parameter values Parameter Decision Generation arule expansion factor 0:5;0:9;1:1 spositive examples 0:5;0:3 GA selection Number of generations 500, 1500 Population size 61, 81 Mutation probability 0:1, 0:21 Crossover probability 0:6 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 79 F1x1;x2ex1sin2x2ex2sin2x1; x1;x228;8;F1x1;x220;5836: In order to model the F1function, a training data set composed of 1089 data uniformly distributed in the three-dimensional de®nition space has been obtained experimentally. On the other hand, another data set has been generated for its use as a test set for evaluating the performance of the design methods, avoiding any possible bias related to the data in the training set. The size of this data set is a percentage of the training set one, ten percent to be precise. The data are obtained by generating at random the state variable values in the speci®c universes of discourse for each one of them, and computing the associated output variable value. Hence the test set, formed by 108 data, is used to measure the accuracy of the dierent models designed by computing the MSE for them. 4.2.1.1. Experiments with FRG-methods. The results obtained with our FRBHLM for WCA and FCM are shown in Table 3 and a graphical illustration of the modeling obtained can be seen in Fig. 8 (FRB-HLM (S-WCA, UCS, 3)). Table 3 Results obtained in the fuzzy modeling of the function F1 Method a#RMSEtra MSEtst %tra %tst S-WCA 9 244,632 257,047 FRB-HLM (S-WCA, CCS, 3) 0.5 316 3876 6140 98.41 97.61 FRB-HLM (S-WCA, UCS, 3) 0.5 201 2406 3634 99.01 98.58 D-WCA 570 116,992 59,878 FRB-HLM (D-WCA, CCS, 2) 0.5 718 60,142 27,947 48.59 53.32 FRB-HLM (D-WCA, UCS, 2) 0.5 838 4984 4036 95.73 93.25 FCM 6 447,584 430,713 FRB-HLM (FCM, CCS, 1) 0.5 5 123,984 88,494 72.29 79.45 FRB-HLM (FCM, UCS, 1) 0.5 9 110,210 55,404 75.37 87.13 -5 0 5-5 0 5 0 1000 2000 3000 4000 5000 6000 Fig. 7. Exact graphical representation of the function F1. 80 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 4.2.1.2. Experiments with dierent values for the expansion factor a. The results obtained with FRB-HLM with dierent values for the expansion factor aare shown in Table 4. We should note that we only present experiments with values of athat become representative, even though other values could have been used. Besides this, Table 4 shows experiments that have been done up to the same iterations in order to allow the comparison among dierent values of a. Anyway, almost all of these values can be overcome in more iterations. 4.2.2. Fuzzy modeling of a very complex multimodal three-dimensional function (F2) In the following, we present a very complex multimodal three-dimensional function, F2[9,11]. Its graphical representation is shown in Fig. 9. Its expression, along with the universes of discourse considered for the variables, is also shown as follows: Table 4 Results obtained in the fuzzy modeling of the function F1considering dierent values of the expansion factor a aCCS UCS #RMSEtra MSEtst #RMSEtra MSEtra (a) S-WCA 0.5 316 3876 6140 201 2406 3634 0.9 214 5012 6248 239 3897 3123 1.1 218 3780 5979 168 3614 4036 (b) D-WCA 0.5 718 60,142 27,944 838 4984 4036 0.9 424 73,408 79,082 668 27,476 39,463 1.1 371 94,682 69,347 571 28,771 43,508 (c) FCM 0.5 5 123,984 88,494 9 110,210 55,404 0.9 5 123,984 88,494 9 110,210 55,404 1.1 4 112,871 90,068 9 110,210 55,404 -5 0 5-5 0 5 0 1000 2000 3000 4000 5000 6000 Fig. 8. F1modeled with 201 rules. O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 81 F2x1;x2x2 1x2 2cos18x1cos18x2; x1;x221;1;F2x1;x222;3:5231: The second function, F2, has been modeled using a training data set composed of 1681 data uniformly distributed in the three-dimensional de®nition space. A test set of 167 data, generated in the same way that was done in function F1, was selected for evaluating the performance of the design methods. 4.2.2.1. Experiments with FRG-methods. The results obtained with our FRBHLM for WCA and FCM methods are shown in Table 5 and also illustrated in Fig. 10 (FRB-HLM (S-WCA, CCS, 3)). 4.2.2.2. Experiments with dierent values for the expansion factor a. The results obtained with our FRB-HLM with dierent values for the expansion factor a are shown in Tables 6 and 7. The assumptions made in the previous experiment remain for the present one. Empty boxes mean that the value of ais too high to expand rules. Table 5 Results obtained in the fuzzy modeling of the function F2 Method a#RMSEtra MSEtst %tra %tst S-WCA 9 0.580 0.660 FRB-HLM (S-WCA, CCS, 3) 0.9 486 0.106 0.129 81.72 80.45 FRB-HLM (S-WCA, UCS, 3) 0.9 379 0.178 0.195 69.31 70.45 D-WCA 49 0.516 0.578 FRB-HLM (D-WCA, CCS, 2) 0.5 1657 0.094 0.084 81.78 85.46 FRB-HLM (D-WCA, UCS, 2) 0.5 2296 0.073 0.072 85.85 87.54 FCM 7 0.553 0.579 FRB-HLM (FCM, CCS, 4) 0.5 146 0.324 0.331 41.41 42.83 FRB-HLM (FCM, UCS, 3) 0.5 15 0.506 0.541 8.49 6.56 -1 -0.5 0 0.5 1-1 -0.5 0 0.5 1 -2 -1 0 1 2 3 4 Fig. 9. Exact graphical representation of the function F2. 82 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 4.2.3. The electrical engineering distribution problems Sometimes, there is a need to measure the amount of electricity lines that an electric company owns. This measurement may be useful for several aspects such us the estimation of the maintenance costs of the network, which was the main goal of the problem presented in Spain [12,31]. High and medium voltage lines can be easily measured, but low voltage line is contained in cities and Table 6 Results obtained in the fuzzy modeling of the function F2considering dierent values of the expansion factor a aCCS UCS #RMSEtra MSEtst #RMSEtra MSEtra (a) S-WCA 0.5 710 0.100 0.121 699 0.171 0.195 0.9 486 0.106 0.129 379 0.178 0.195 1.1 (b) D-WCA 0.5 2296 0.094 0.084 1657 0.073 0.072 0.9 697 0.163 0.169 587 0.138 0.184 1.1 213 0.297 0.299 210 0.290 0.275 (c) FCM 0.5 127 0.374 0.388 15 0.506 0.541 0.9 66 0.385 0.421 1.1 -1 -0.5 0 0.5 1-1 -0.5 0 0.5 1 -2 -1 0 1 2 3 4 Fig. 10. F2modeled with 486 rules. Table 7 Results obtained in the fuzzy modeling of the function F2comparing results with two dierent values of aand a dierent number of iterations Method a#RMSEtra MSEtst FRB-HLM (D-WCA, CCS, 2) 0.5 1657 0.094 0.084 FRB-HLM (D-WCA, CCS, 4) 1.1 750 0.129 0.133 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 83 villages, and it would be very expensive to measure it. This kind of line used to be very convoluted and, in some cases, one company may serve more than 10,000 small nuclei. An indirect method to determine the length of line is needed. Therefore, a relationship must be found between some characteristics of the population and the length of line installed on it, making use of some known data, that may be employed to predict the real length of line in any other village. We will try to solve this problem by generating dierent kinds of models determining the unknown relationship: fuzzy, classical regression and neural models. To do so, we were provided with the measured line length, the number of inhabitants and the mean distance from the center of the town to the three furthest clients, considered as the radius of population iin a sample of 495 rural nuclei [30,31]. Our variables are named as shown in Table 8. To design the dierent models we have randomly divided the sample into two sets comprising 396 and 99 samples, labeled training and test, respectively. 4.2.3.1. Experiments with dierent prede®ned types of FRG-methods. The results obtained with our FRB-HLM with the two said FRG-methods are shown in Table 9. 4.2.3.2. Experiments with dierent values for the expansion factor a. The results obtained with our FRB-HLM with dierent values for the expansion factor a Table 8 Notation considered for the problem variables Symbol Meaning x1Number of clients in population x2Radius of ith population in the sample yLine length, population i Table 9 Results obtained in the low voltage electrical application Method a#RMSEtra MSEtst %tra %tst S-WCA 9 777,306 717,472 FRB-HLM (S-WCA, CCS, 2) 0.5 60 154,109 184,178 80.17 74.32 FRB-HLM (S-WCA, UCS, 2) 0.5 40 158,879 186,819 79.56 73.96 D-WCA 25 192,818 202,095 FRB-HLM (D-WCA, CCS, 1) 1.1 115 97,187 144,865 49.59 28.31 FRB-HLM (D-WCA, UCS, 1) 1.1 136 87,675 146,155 54.52 27.68 FCM 5 508,426 464,130 FRB-HLM (FCM, CCS, 4) 0.5 27 181,196 158,312 64.36 55.01 FRB-HLM (FCM, UCS, 2) 0.9 8 208,777 171,379 58.93 63.07 84 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 are shown in Table 10. The assumptions made in previous experiments remain for the present one. 4.2.3.3. Experiment comparing models from FRB-HLM with other techniques. Once we have analyzed the behavior of the fuzzy models designed individually, we are going to compare their accuracy with the remaining techniques considered. Table 11 shows the results obtained by them and the best ones obtained by our FRB-HLM as well. To apply classical regression, the parameters of the polynomial models were ®t by Levenberg±Marquardt, while exponential and linear models were ®t by linear least squares. The multilayer perceptron was trained with the QuickPropagation algorithm. The number of neurons in the hidden layer was chosen to minimize the test error [12,31]. We also compare the obtained results with a linguistic model obtained by means of a hierarchical approach described in [13,15,16], i.e., a hierarchical system of linguistic rules Table 10 Results obtained in the low voltage electrical application considering dierent values of the expansion factor a aCCS UCS #RMSEtra MSEtst #RMSEtra MSEtra (a) S-WCA 0.5 60 154,109 184,178 40 158,879 186,819 0.9 38 186,343 207,585 39 168,988 189,795 1.1 23 359,169 320,839 31 228,388 235,460 (b) D-WCA 0.5 205 80,840 206,961 209 70,903 158,572 0.9 132 87,091 163,687 151 78,857 169,366 1.1 115 97,187 144,865 136 87,675 146,155 (c) FCM 0.5 14 191,441 181,375 11 211,719 177,138 0.9 10 205,221 189,842 8 208,777 171,379 1.1 7 229,559 206,363 8 231,280 207,120 Table 11 Results obtained in the low voltage electrical application compared with other techniques Method MSEtra MSEtst Complexity Linear 287,775 209,656 7 nodes, 2 par. Exponential 232,743 197,004 7 nodes, 2 par Second-order polynomial 235,948 203,232 25 nodes, 2 par. Third-order polynomial 235,934 202,991 49 nodes, 2 par. Three-layer perceptron 2-25-1 169,399 167,092 102 par. HSLR-LM 154,411 156,197 25 rules FRB-HLM (D-WCA, UCS, 1) 97,187 144,865 115 rules FRB-HLM (D-WCA, CCS, 1) 87,675 146,155 136 rules O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 85 [14] O. Cord on, F. Herrera, P. Villar, Analysis and guidelines to obtain a good uniform fuzzy partition granularity for FRBSs using simulated annealing, International Journal of Approximate Reasoning 25 (3) (2000) 187±215. [15] O. Cord on, F. Herrera, I. Zwir, A hierarchical knowledge-based environment for linguistic modeling: models and methodology, #DECSAI-000106, Department of Computer Science and Arti®cial Intelligence, University of Granada, Spain, 2000. [16] O. Cord on, F. Herrera, I. Zwir, Hierarchical knowledge bases for fuzzy rule-based systems, in: Proceedings of the 8th Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU), Madrid, Spain, 2000, pp. 1770±1777. [17] M. Delgado, A.F. G omez-Skarmeta, A. Vila, On the use of hierarchical clustering in fuzzy modeling, International Journal of Approximate Reasoning 14 (1996) 237±257. [18] M. Delgado, A.F. G omez-Skarmeta, F. Mar õn, A fuzzy clustering-based rapid prototyping for fuzzy rule-based modeling, IEEE Transactions on Fuzzy Systems 5 (2) (1997) 223±232. [19] D.J. Hand, Discrimination and Classi®cation, Wiley, New York, 1992. [20] F. Herrera, M. Lozano, J.L. Verdegay, A learning process for fuzzy control rules using genetic algorithms, Fuzzy Sets and Systems 100 (1998) 143±158. [21] K. Hirota (Ed.), Industrial Applications of Fuzzy Technology, Springer, Berlin, 1993. [22] H. Ishibuchi, K. Nozaki, N. Yamamoto, H. Tanaka, Selecting fuzzy if±then rules for classi®cation problems using genetic algorithms, IEEE Transactions on Fuzzy Systems 3 (3) (1995) 260±270. [23] R. Krishnapuram, J. Keller, A possibilistic approach to clustering, IEEE Transactions on Fuzzy Systems (1993) 98±110. [24] C.T. Leondes (Ed.), Fuzzy Theory Systems, Techniques and Applications, Academic Press, New York, 2000. [25] T. Mitchell, Machine Learning, McGraw-Hill, New York, 1997. [26] W. Pedrycz (Ed.), Fuzzy Modelling: Paradigms and Practice, Kluwer Academic Press, Dordrecht, 1996. [27] W. Pedrycz, A.V. Vasilakos, Linguistic models and linguistic modeling, IEEE Transactions on Systems, Man, and Cybernetics 29 (6) (1999). [28] E.H. Ruspini, A new approach to clustering, Information and Control 15 (1) (1969) 22±32. [29] E.H. Ruspini, I.S. Zwir, Automated qualitative description of measurements, in: Proceedings of the 16th IEEE Instrumentation and Measurement Technology Conference, Venice, Italy, 1999. [30] L. S anchez, Study of the Asturias rural and urban low voltage network, Technical Report, Hidroel ectrica del Cant abrico Research and Development Department (in spanish), Asturias, Spain, 1997. [31] L. S anchez, Interval-valued GA-P algorithms, IEEE Transactions on Evolutionary Computation 4 (1) (2000) 64±72. [32] M. Sugeno, T. Yasukawa, A fuzzy-logic-based approach to qualitative modeling, IEEE Transactions on Fuzzy Systems 1 (1) (1993) 7±31. [33] L.X. Wang, J.M. Mendel, Generating fuzzy rules by learning from examples, IEEE Transactions on Systems, Man, and Cybernetics 22 (1992) 1414±1427. [34] J. Yen, L. Wang, C. Wayne Gillespie, Improving the interpretability of TSK fuzzy models by combining global learning and local learning, IEEE Transactions on Fuzzy Systems 6 (4) (1998) 530±537. [35] L.A. Zadeh, Fuzzy sets, Information and Control 8 (1965) 338±353. [36] L.A. Zadeh, The concept of a linguistic variable and its application to approximate reasoning, Information Science Part I 8 (1975) 199±249. [37] L.A. Zadeh, The concept of a linguistic variable and its application to approximate reasoning, Information Science (Part II) 8 (1975) 301±357. 92 O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 [38] L.A. Zadeh, The concept of a linguistic variable and its application to approximate reasoning, Information Science (Part III) 9 (1975) 43±80. [39] L.A. Zadeh, Toward a theory of information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems 90 (1997) 111±127. [40] I. Zwir, E.H. Ruspini, Qualitative object description: initial reports of the exploration of the frontier, in: Proceedings of the EUROFUSE-SIC '99, Budapest, Hungary, 1999, pp. 485±490. O. Cordon et al. / Internat. J. Approx. Reason. 27 (2001) 61±93 93