Rule Simplification Method Based on Covering Indexes for Fuzzy Classifiers

Depósito de investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of an article published by IEEE in IEEE International Conference on Fuzzy Systems on 05 August 2021, available at: https://doi.org/10.1109/FUZZ45933.2021.9494545 “© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other Works” Abstract— A large number of rules increases the complexity of fuzzy classifiers and reduces the linguistic interpretability of the classification. A tabular rule simplification method that extends the Quine-McCluskey algorithm of Boolean design to fuzzy logic is analyzed in detail in this paper. The method obtains a few compound rules from many initial atomic rules. The influence of membership functions as well as t-norms and s-norms operands, which can be even null if many atomic rules are used, becomes apparent in the classification regions (decision boundaries) induced by the compound rules. Since the compound rules can be ordered according to the covering indexes that measure the number of atomic rules covered, more or less generic classification rules and rules with particular indexes can be further identified, which could ease subsequent classification or decision-making. Keywords—fuzzy systems, rule base simplification, fuzzy classifiers I. INTRODUCTION In the field of fuzzy system design, enormous efforts have been made to achieve the minimum set of fuzzy rules (especially to improve their interpretability) [1]-[2]. In [3], the trade-off between a reduced set of rules and its efficiency is analyzed in the context of information theory and neural networks. To apply that approach in the context of fuzzy logic, the existence of cost metrics must be assumed for each rule set to be minimized. Many authors have focused on the simplification of the fuzzy sets to simplify subsequently the redundancies appearing in the rule bases [4]-[6]. Concerning the simplification of the rule base itself, a technique widely followed by several authors is to apply orthogonal transformation methods to identify the most important rules [7]. The firsts to apply these techniques in the field of fuzzy logic were Wang and Mendel in [8], proposing an orthogonal least squares algorithm. In that work, they introduced the concept of "fuzzy basis functions" and demonstrated that, given certain parameters, a fuzzy system can be represented by a series expansion of these basis functions. The reason why fuzzy basis functions are used instead of other basis functions (such as polynomial, radial, etc.) is because the rules of the system can be naturally related to these basis functions. They apply the classical Gram-Schmidt *Research supported by the Projects TEC2017-83557-R and RTC-2017- 6595-7 (AEI/FEDER UE), and AT17_5926_USE and US-1265146 (FEDER UE/ Consejería de Economía, Conocimiento, Empresas y Universidad de la Junta de Andalucía). A. Gersnoviez is with the Department of Electronic and Computer Engineering, Universidad de Córdoba, 14071 Córdoba, Spain (phone: +34 957212224; e-mail: andre[email protected]). I. Baturone is with the Instituto de Microelectrónica de Sevilla (IMSECNM), Universidad de Sevilla, CSIC, 41092 Seville, Spain (e-mail: [email protected]). orthogonalization procedure to determine the most significant fuzzy basis functions and select the most important rules based on the contribution of them to the output variance. The problem with the latter consideration is that a low variance does not necessarily mean that the corresponding rule is unimportant. Therefore, several works appeared later to improve the application of the orthogonal least squares method [9]-[10]. Among them, the proposal in [11] obtains zero-order Takagi-Sugeno-Kang fuzzy systems from data, with interpretable rule bases. The authors apply the least squares algorithm twice. The first time to select the most important rules, and the second time to optimize the consequents of the rules. Then, using the Hard C-means algorithm, they reduce the number of consequents. More recently, the authors in [12] propose a new rule reduction method for fuzzy modelling by the fusion of similar rules into a single rule, redefining the membership functions for the new rules. Once the number of rules is reduced, they apply a space projection mechanism, where low-dimensional space features are projected to a higher-dimensional space, transforming non-linear into linear relationships. Another method for the simplification of fuzzy rule bases was proposed in [13]. In that work, since fuzzy systems can be viewed as an extension of Boolean systems, a tabular simplification of the rules is presented as an extension of the Quine-McCluskey algorithm of Boolean design. The tabular simplification is applied to every consequent and the simplest set of rules for each consequent is obtained from the best prime implicants of the minimization table. Finally, linguistic hedges are employed to improve the linguistic interpretability of the rules. The method was applied in [14] to extract fuzzy rules describing linguistically the low-level features (such as color, texture, etc.) of images. It can be carried out with the CAD tools of the Xfuzzy environment. This paper analyzes in detail the rule simplification method presented in [13] for classification systems. The method starts from a complete rule base of atomic rules, without any fuzziness, and finishes with a simpler rule base of compound rules whose antecedent parts cover more than one fuzzy set in at least one of the input variables. It is illustrated that the use of compound rules not only make the classifier simpler and more interpretable, but also introduces fuzzy features even to classifiers with complete rule bases. The covering index of a compound rule is employed to measure how many atomic rules not covered by other rules can be represented by the compound rule. Once the rules are ordered according to the covering indexes, the resulting classifier can be simplified even further. The paper is organized as follows. Section II summarizes first the proposal for simplifying rules by covering indexes and then details the fuzziness introduced by using a small Rule Simplification Method Based on Covering Indexes for Fuzzy Classifiers Andrés Gersnoviez and Iluminada Baturone number of compound rules instead of all the possible atomic rules. Section III illustrates the results obtained by applying the proposal to application examples that differ in the objective of the classification, more generic in one example and more particular in the other. Finally, Section IV presents the conclusions. II. RULE SIMPLIFICATION BASED ON COVERING INDEXES FOR FUZZY CLASSIFIERS Fuzzy classifiers are usually fuzzy not because of the categories they employ, which can be crisp, but mainly because of the way input variables are described, which is usually fuzzy. The defuzzification method used mainly by fuzzy classifiers provides as output the consequent (category) of the rule with the highest activation degree. This method will be called MaxLabel in this work (as it is so named in the Xfuzzy environment). Let us consider a fuzzy classifier whose rule base has a grid structure and contains all the atomic rules defined by its grid partition, i.e. it has a complete rule base. If the MaxLabel defuzzification method is used, then it is equivalent to a system with a non-fuzzy rule base, i.e. a rule base whose antecedents can be represented by crisp instead of fuzzy sets. Actually, the shape of the membership functions has no influence on the result, only the point of intersection between the membership functions matters, i.e. the value at which a function starts to have a higher degree of membership than its neighboring functions (for that reason they can be rectangular). The t-norm applied to connect the antecedents has no influence on the result either, because a t-norm is a monotonic function. One could say that a complete rule base with atomic rules for classification contains so much information that there is no place for ambiguity or uncertainty. Hence, it is not necessary to use fuzzy sets in the antecedents. In this sense, classifier systems with a complete set of atomic rules should not be called "fuzzy". However, let us analyze what happens when using compound rules that include several atomic rules. In the tabular simplification technique described in [13], the atomic rules are considered as the minterms in Quine McCluskey method, and the compound rules as the prime implicants. The covering index of a compound rule (prime implicant) measures the number of atomic rules (minterms) only represented by the compound rule. The latter with the highest covering index is the one that covers the maximum number of atomic rules. The next compound rule with the highest covering index is the one that covers the largest number of uncovered atomic rules and so on. In this way, the implicants (and the rules associated with them) resulting from the tabular simplification in [13] can be ordered according to their covering index. Depending on the features of the categories considered by the classifier, a condition for each category can be set for the covering indexes. For example, if the category to classify has generic features, the rules with covering indexes above a threshold can be selected, and the others are eliminated. In the other side, if the category responds to a particular description, then the rules with particular covering indexes are selected, and the others are not considered. Let us consider an example of classification rule base consisting of 6 x 6 = 36 atomic rules, as shown in Fig. 1(a). For simplicity, it considers two categories represented by “black” and “not black” in a two-dimensional input space defined by the variables  and . As noted above, since the rule base is complete, it is in principle not necessary to define a fuzzy system with membership functions to describe the antecedents and a t-norm for connecting them, since the same result can be obtained with a non-fuzzy system. Using a complete rule base, the region in which a rule has a higher degree of activation than the others (classification region) has a square shape and the frontiers of squares (decision boundaries) are given by the values at which the membership degrees of  and  to one fuzzy or non-fuzzy set, , and its neighbor, , are equal. This is also explained in [15]. Let us see how the tabular simplification technique changes the classification regions (and decision boundaries) of the fuzzy classifier. The simplification applies to rules having as consequent "black" on the one hand, and applies to rules having as consequent "not black" on the other hand. Following the steps described in [13], 4 compound rules with the consequent "black" (Fig. 1(a)) and 6 compound rules with the consequent "not black" (Fig. 1(b)) are obtained. By ordering them from higher to lower covering indexes (rules with one consequent are independent of those with the other), Figure 1. (a) Tabular simplification applied to the consequent "black"; (b) Tabular simplification applied to the consequent "not black"; (c) Classification regions after tabular simplification using the product as t-norm. the following rule base is obtained (the linguistic hedges “smaller than or equal to” and “greater than or equal to” are represented by the symbols “≤” and “≥”, respectively): [1a.] If ( is ≤  and  is ≥ ), then there is black; [2a.] If ( is ≥  and  is ≤ ), then there is black; [3a.] If (( is ≥  and ≤ ) and ( is ≥ and is ≤ )), then there is black; [4a.] If (( is ≥  and ≤ ) and ( is ≥  and is ≤ )), then there is black; [1b.] If ( is ≥  and  is ≥ ), then there is not black; [2b.] If ( is ≤  and  is ≤ ), then there is not black; [3b.] If ( is ≥  and  is ≥  ), then there is not black; [4b.] If ( is ≥   and  is ≥ ), then there is not black; [5b.] If ( is  and  is ≤ ), then there is not black; [6b.] If ( is ≤  and  is ), then there is not black; Among the rules with the consequent "there is black", rules 1a and 2a have the same covering index, since both group 6 atomic rules not covered by other ones. The next rule with the highest covering index can be either rule 3a or 4a, since both group 4 rules of which 3 are not covered (one of the rules of rule 3a is already covered by rule 1a and one of rule 4a is already covered by rule 2a). By choosing rule 3a as the next in order, rule 4a has a lower covering index, since, although it groups 4 rules, only 2 of them are not covered (one of them covered by rule 2a and one by rule 3a). In the case of the rules corresponding to the consequent "there is not black", rule 1b is the one with the highest covering index, since it groups 9 rules and none of them is covered. The next in order is rule 2b, since it groups 4 rules and none is covered. Rules 3b and 4b have the same covering index, since they both group 8 rules, of which 2 are uncovered (in both cases, rule 1b covers 6 of its rules). The rules with the lowest covering index for this consequent are rules 5b and 6b, which also have the same index, since both group 3 rules, of which only one is uncovered (since, in both cases, rule 2b covers 2 of its rules). Rules grouping a larger number of rules may have a lower covering index than other rules grouping fewer rules. This is the case of rules 3b and 4b which, grouping 8 rules, have a lower covering index than rule 2b, which groups 4. A. Fuzziness introduced by compound rules Tabular simplification produces compound rules that consider a range between one linguistic label and another for each antecedent (making some linguistic labels unused). This affects the classification regions depending on whether one tnorm or another is used to connect the antecedents. If the minimum is used as the t-norm, the regions (shown in Fig. 1(a) and Fig. 1(b)) are the same independently of the atomic or compound nature of the rules. In this case, the shape of the membership functions does not modify the decision boundaries but only the point of intersection between them is influential. However, if the product is used as t-norm, the classification regions change, as can be seen in Fig. 1(c). Therefore, the behavior of the simplified system changes with respect to the initial one. In addition, if the rules with the same consequent are connected with an s-norm, the behavior of the simplified classifier depends on the s-norm employed. If the minimum is used as t-norm and the maximum as s-norm, the same result is obtained as without grouping rules. However, if the product is used as t-norm and the bounded sum as s-norm, the result is shown in Fig. 2(a), where the bounded sum is defined by the expression: , = 1,  +  (1) Using t-norms other than the minimum and/or s-norms other than the maximum, the behavior does depend on the membership functions chosen to cover the antecedents. For example, using the product as t-norm and the maximum as snorm, if instead of using families of triangles in Fig. 1, Gaussians are used, the final behavior is shown in Fig. 2(b). The behavior offered by this system is highly similar to that shown in Fig. 1(c), but changing the decision boundaries, Figure 2. Final behavior of the fuzzy system in Fig. 1(a) after tabular simplification: (a) Using triangular functions to cover the antecedents, product as t-norm and bounded sum as s-norm; (b) Using Gaussian functions to cover the antecedents, product as t-norm, and maximum as s-norm; (c) Using Gaussian functions to cover the antecedents, product as t-norm and bounded sum as s-norm. from polygonal to curved. Similarly, if the bounded sum is applied to the latter system as s-norm, the behavior obtained is shown in Fig. 2(c). Therefore, tabular simplification not only reduces the number of rules, but also restores to the classifiers a degree of fuzziness that they lacked before being simplified. B. Fuzziness introduced by removing rules Returning to the complete rule base example in Fig. 1(a), if the atomic rule 21 were removed and the system were nonfuzzy (the membership functions covering the inputs were rectangular), then the region determined by that rule would not provide any category. However, using fuzzy membership functions, such as those in Fig. 3(a), the neighboring rules have a non-zero activation degree in that area. The closest rules (i.e., rules 15, 20, 22 and 27) share the region equally in this example, as illustrated in Fig. 3(b). Hence, the final behavior of the classifier is illustrated in Fig. 3(c). Consider now that, instead of one, four rules (rules 15, 16, 21 and 22) are eliminated. If the membership functions in the inputs are triangular, as shown in Fig. 3, in a large part of the gap left by those rules, the twelve neighboring rules have non-zero activation degree. However, the whole gap left by the four rules is not covered by the neighboring rules, leaving an undefined space in the center. This occurs because the membership functions used are triangular. If, instead of triangular, Gaussian functions are used, there is no undefined zone, since, even if the activation degree of a rule is very small, it is sufficient to dominate over smaller ones and provide its category as the output value. In this sense, fuzzy classifiers with incomplete rule bases are truly "fuzzy", since, depending on the membership function used, different results are obtained. Let us know see what happens when compound rules obtained after tabular simplification are eliminated. After ordering the rules according to their covering index, among all the rules corresponding to the consequent "there is black", rule 4a is the one with the lowest covering index. If this rule is removed (Fig. 4 (a)), the neighboring rules (rules 2a, 3a, 1b, 2b, 4b and 6b) have a non-zero activation degree in the gap left by this rule. The regions in which the neighboring rules have a higher activation degree than the rest in the gap left by rule 4a are shown in Fig. 4(b). The resulting classification regions can be seen in Fig. 4(c). In this example the t-norm product is used. III. APPLICATION EXAMPLES The advantages of using rule simplification based on covering indexes is illustrated in the following with two Figure 4. (a) Elimination of the rule with the lowest covering index with the consequent "there is black" in Fig. 1(c); (b) Regions of higher activation of neighboring rules; (c) Final behavior of the fuzzy system with one rule less. Figure 3. (a) Elimination of one of the atomic rules shown in Fig. 1(a); (b) Regions of higher activation of neighboring rules; (c) Final behavior of the fuzzy system with one rule less. examples. In one of them, it is desirable to select rules with a high covering index, while in the other, the objective is to select rules with a low index. The first example considers the image shown in Fig. 5(a), which shows a crack in the asphalt of a road. By applying a texture filter to this image, it is possible to determine which points of the image belong to the crack and which do not. Specifically, the filter returns an image whose dark points correspond to the crack and light points to the background. The image can be understood as a set of numerical data corresponding to the vertical () and horizontal () position of the pixel, each pixel with an associated category (in this case, the existence or not of a crack). Hence, the fuzzy classifier has two inputs (vertical and horizontal position of the pixel) and an output indicating whether or not there is a crack at that position. Let us consider an application context in which the classifier is used as part of the navigation system of an unmanned vehicle that wants to avoid the crack. In order to reduce the complexity of the navigation system, the objective is to design a classifier with a small number of generic rules (with high covering indexes). Let us consider an initial system with 625 rules (25 membership functions for each of the inputs). The result obtained is shown in Fig. 5(b). The area highlighted in red in Fig. 5(b) are the 36 rules of the example in Section II. Applying the tabular simplification technique, the rules are reduced from 625 to 39 (16 modeling the crack and 23 modeling the background). Once the rules are grouped, different behaviors can be obtained according to the membership functions chosen to cover the antecedents as well as the t-norms and s-norms operators employed. Specifically, using triangular membership functions, the product as t-norm, and the bounded sum as s-norm, the behavior is shown in Fig. 5(c). If the same t-norm and s-norm are used, but Gaussian membership functions are employed, the result is that of Fig. 5(d). Using the minimum as t-norm and the maximum as s-norm, the result is identical to that obtained without grouping the rules, regardless of the membership functions chosen. If the 39 rules are ordered according to their covering indexes, the rules with the highest covering indexes can be selected for modeling the crack and the background. Specifically, Fig. 5(e) and 5(f) highlight the 7 most important rules for modeling the crack and the 9 most important rules for modeling the background, respectively. One way to achieve a fairly simplified classifier is to select the 7 rules that best represent the crack and determine the background with an "otherwise" rule (i.e., if none of the 7 rules are activated, then it is the background). This can only be applied in situations with only two categories, like in this example. The initial number of rules is reduced in a 98.72%. As a result, the squared behavior shown in Fig. 5(g) is obtained. This behavior is highly similar to that obtained with a system with rectangular functions to cover the background but the corners present some roundness due to the Gaussians. Another approach is to opt for a fuzzy classifier with an incomplete rule base. By selecting the 7 most important rules to model the crack and the 9 most important rules to model the background, the rule base with 39 rules is further simplified to 16 rules. The initial number of rules is reduced in a 97.44%. The gap generated by rule elimination is large enough so that triangular membership functions give poor results, and Gaussian functions are better chosen. The system with the incomplete rule base of 16 compound rules and the product as t-norm presents the behavior of Fig. 5(h). This simplification offers a smooth classification with high linguistic interpretability. The second example considers the image shown in Fig. 6(a), in which several elements can be seen on the ground, like a piece of wood, an almond, and several woodlice. In the same way as in the previous example, using a texture filter, Figure 5. (a) Image of a crack in the asphalt; (b) Behavior of a fuzzy classifier with 625 rules (36 of them are highlighted); (c) Simplified system with 39 (instead of 625) rules, triangular membership functions to cover the background, product as t-norm, and the bounded sum as s-norm; (d) System with 39 rules, Gaussian membership functions to cover the background, product as t-norm, and the bounded sum as s-norm; (e) The 7 most important rules for the crack; (f) The 9 most important rules for the background; (g) System with 7 rules to describe the crack and an "otherwise" rule for the background; (h) Further simplified system with an incomplete rule base of 16 rules with the highest covering indexes. an image is obtained whose dark pixels belong to the elements and light pixels to the background. The fuzzy classifier has two inputs (vertical and horizontal position of the pixel) and an output indicating whether or not there is something on the ground at that position. Let us consider an application context in which the classifier is used by an unmanned aerial mini drone that wants to find the woodlice. In this case, the objective is to design a classifier with a small number of particular rules (with low covering indexes). Again, a fuzzy classifier with 625 rules (25 Gaussian membership functions for each input) is created, obtaining the behavior shown in Fig. 6(b). By applying the tabular simplification technique to this system, the 625 rules are reduced to 35 (14 for modeling the elements and 21 for modeling the background). Sorting the 35 obtained rules according to their covering indexes, the 3 rules with the lowest index are highlighted in Fig. 6(c). As can be seen, each of them belongs to a different woodlouse. Therefore, a system can be created with these 3 rules and an "otherwise" rule to describe the rest of the image. The resulting classifier locates the 3 woodlice in the image. The behavior of this system is illustrated in Fig. 6(d). The initial number of rules is reduced in a 99.36%. IV. CONCLUSIONS In this work, the tabular simplification algorithm based on the Quine-McCluskey algorithm of Boolean logic expanded to fuzzy logic has been analyzed to simplify the rule bases of fuzzy classifiers. The simplification method allows reducing the number of rules by not only merging several atomic rules into compound rules but also eliminating rules according to their covering indexes. The use of compound rules introduces fuzziness into classifiers with complete rule bases, and rule elimination further increases fuzziness. Since the tabular simplification method allows ranking the rules according to their covering index, the method facilitates the choice of rules to be selected or removed (rules with intermediate indexes, above, and below particular threshold values). This is illustrated with two application examples with opposite objectives: one looking for generic classification rules and the other interested in particular rules. In both cases, the method allows designing efficient classifiers with a significant reduction (from 97.44% to 99.36%) of the initial number of rules. REFERENCES [1] S.-M. Zhou, J.Q. Gan, “Low-level interpretability and high-level interpretability: A unified view of data-driven interpretable fuzzy system modelling”, Fuzzy Sets and Syst., vol. 159, no. 23, pp. 3091- 3131, 2008. [2] M.J. Gacto, R. Alcalá, F. Herrera, “Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures”, Inf. Sciences, vol. 181, no. 20, pp. 4340-4360, 2011. [3] R.M. Goodman, C.M. Higgins, J.W. Miller, P. Smyth, “Rule-based neural networks for classification and probability estimation”, Neural Comp., vol. 4, no. 6, pp. 781-804, 1992. [4] C. Fuchs, A. Wilbik, S. van Loon, A.-K. Boer, U. Kaymak, “An enhanced approach to rule base simplification of first-order Takagi- Sugeno fuzzy inference systems,” in Adv. in Fuzzy Logic and Tech. 2017, pp. 92–103, Springer, 2017. [5] C. Fuchs, S. Spolaor, M.S. Nobile, U. Kaymak, “A graph theory approach to fuzzy rule base simplification”, in: M.J. Lesot et al. (Eds.), Int. Conf. Inf. Process. Manage. Uncertain. in Knowledge- Based Syst. (IPMU’20), pp. 387–401, 2020. [6] S. Rajab, “Rule base simplification and constrained learning for interpretability in TSK neuro-fuzzy modelling”, Int. J. Fuzzy Appl., vol. 9, no. 2, pp. 31-58, 2020. [7] J. Yen, L. Wang, “Simplifying fuzzy rule-based models using orthogonal transformation methods”, IEEE Trans. Syst.,Man.,Cybern. B, Cybern., vol. 29, no. 1, pp. 13–24, Feb. 1999. [8] L.-X. Wang, J.M. Mendel, “Fuzzy basis functions, universal approximation, and orthogonal least-squares learning”, IEEE Trans. Neural Netw., vol. 3, no. 5, pp. 807-814, 1992. [9] M. Setnes, H. Hellendroon, “Orthogonal transforms for ordering and reduction of fuzzy rules”, in Proc. of the 9th IEEE Int. Conf. Fuzzy Syst. (FUZZ-IEEE'00), vol. 2, pp. 700-705, 2000. [10] P.A. Mastorocostas, J.B. Theocharis, V.S. Petridis, “A constrained ortogonal least-squares method for generating TSK fuzzy models: Application to short-term load forecasting”, Fuzzy Sets and Syst., vol. 118, no. 2, pp. 215-233, 2001. [11] S. Destercke, S. Guillaume, B. Charnomordic, “Building an interpretable fuzzy rule base from data using ortogonal least squares - Application to a depollution problem”, Fuzzy Sets and Syst., vol. 158, no. 18, pp. 2078-2094, 2007. [12] X. Lu, Y. Bai, “A new rule reduction method for fuzzy modelling”, IEEE Trans. Fuzzy Syst., vol. 28, no. 11, pp. 3023-3031, 2020. [13] I. Baturone, F. J. Moreno-Velo, A. Gersnoviez, “A CAD approach to simplify fuzzy system descriptions”. In Proc. IEEE Int. Conf. Fuzzy Syst. (FUZZ-IEEE’06), 2006. [14] I. Baturone, A. Gersnoviez, “Automatic extraction of linguistic models for image description”. In Proc. IEEE Int. Conf. Fuzzy Syst. (FUZZ-IEEE’10), 2010. [15] H. Ishibuchi, T. Nakashima, “Effect of rule weights in fuzzy rulebased classification systems”, IEEE Trans. Fuzzy Syst., vol. 9, no. 4, pp. 506-515, 2001. Figure 6. (a) Several elements on the ground; .(b) Behavior of a fuzzy classifier with 625 rules; (c) The 3 rules with the lowest covering indexes for describing the elements; (d) System with 3 rules to describe the location of the woodlice and an "otherwise" rule for the background;