Fuzzy rule-based systems are raising great interest in the last years in eXpalianable Artificial Intelligence. These systems represents knowledge easily understood by humans but they are not interpretable per se. They, in fact, must remain simple and understandable, and the rule base must be compactness. In this work a fuzzy rule base minimization approach based on rough sets theory and a greedy algorithm is proposed. The reduction of the fuzzy rules makes the rule base simpler, and thus easier to produce explainable inference systems (e.g., decision support systems and recommenders). Encouraging results are obtained validating and comparing the methodology on data of UCI benchmark.
obtain FRBSs that represent knowledge easily understood by humans. Among others, the rule
base compactness or the semantic comprehensibility of the fuzzy partitions must be stressed
[
The paper is organized as follows. In Section 2 we present the proposed methodology and the used methods. Furthermore, in Section 3 the results of experiments on benchmark data are presented. Finally, the authors draw conclusions in Section 4.
The problem of finding the useless attributes for the correct classification is intractable when
the number of attributes is large and algorithms that provide suboptimal approximated
solutions must be explored. The Reducing Rules and Conditions (RRC) algorithm provides a greedy
approximated solution to the problem of identifying and deleting in a set of fuzzy rules the
attributes that are irrelevant for the correct classification. RRC approach is composed by five
steps as described in Figure 1. In order to evaluate a rule pattern in the algorithm search, a
property, i.e., eficiency , is associated to each rule pattern (see [
In this stage each rule of the a fuzzy knowledge base, ℱ is represented into a decision system model, labeling antecedents and consequents of the fuzzy rule as the condition and decision attributes, respectively. Firstly, a label is associated to each pair (Linguistic Variable, Value) and then, each pair in fuzzy rules is replaced with the respective labels (e.g., High → H).
In this phase, the relevance for each attribute (i.e., for each fuzzy relation) is computed. To this
purpose the attributes relevance is measured by its significance by using rough sets theory [
The construction of the prefix tree takes processing one rule at a time. In particular, for each attribute, a node is generated, which becomes the child of the node of the previous attribute and the parent of the node of the next attribute. The first attribute, becomes the child node of the root tree, which, not having any attribute, is an empty node. The tree has the property that all the descendants of a node shares the prefix associated with the node. This implies that two rules with the same initial condition share the same node associated with that condition.
The search algorithm uses the prefix tree, constructed in the previous stage, as a decision tree
and carries out a left-to-right depth-first search (DFS) visit of the tree for each decision [
The final result of rule pattern searching is a list of candidate rule patterns which is usually oversized compared with the initial knowledge base. Therefore, in these stage it is extracted only a subset of candidate rule patterns, that can cover all the decisions produced by the initial knowledge base and, at the same time, minimize the number of rules and conditions. The set of ifrst rule patterns that cover all the decisions produced by the initial knowledge base.
The proposed algorithm has been validated on two UCI benchmarks, i.e., mushroom [12], breastcancer [13] 1, and was compared with Ripper [14], Part [15], Lem2 [16] algorithms. Benchmark characteristics are summarized in Table 1. The performance of the algorithms have been measured in terms of number of rules extracted, Coverage, Accuracy2. In Tables 2 and 3 we describe the results obtained on mushroom and breast cancer benchmarks, respectively. We observe that the proposed methodology permits to obtain a low number of rules and attributes maintaining high accuracy and coverage.
benchmark
Mushroom Breast-Cancer number of rules 8214 286 number of attributes 178728 2574 1informations about the other benchmarks can be found on http:∖∖ archive.ics.uci.edu/ml/datasets.php
2Coverage: percentage of the rules of initial knowledge base that are covered by the set of rules generated by compressing algorithm; Accuracy: percentage of the correct classification of the set of the rules generated by the compressing algorithm.
In this work a fuzzy rule base minimization approach based on rough sets theory and a greedy algorithm has been introduced. Rough sets theory has been used for ordering significance of the attributes and greedy approach for building a prefix tree used as a decision tree carrying out left-to-right depth-first search visit. The proposed approach is validated and compared on UCI benchmarks resulting encouraging results. In the next future the authors will focus on the theoretic background of the methodology (e.g., eficiency measures and optimal path demonstration). Further experiments and comparisons will be conducted on diferent data and for addressing the explainability of the obtained fuzzy rules.
Part of work was developed by Salvatore Sposato during M. Sc. in Applied Computer Science at University of Naples Parthenope. [12] J. Schlimmer, Concept Acquisition through representation adjustment, Technical Report,
University of California, Irvine, PhD Thesis, 1987. [13] R. Michalski, I. Mozetic, J. Hong, J. N. Lavrac, The multi-purpose incremental learning system aq15 and its testing application to three medical domains, in: Proceedings of the Fifth National Conference on Artificial Intelligence, Morgan Kaufman, 1986, pp. 1041–1045. [14] W. Cohen, Fast efective rule induction, in: Machine Learning Proceedings 1995, Morgan
Kaufman, 1995, pp. 115–123. [15] E. Frank, I. Witten, Generating accurate rulesets without global optimization, in: 1998
Working Papers, University of Waikato, Department of Computer Science, 1998, pp. 1–15. [16] J. Grzymala-Busse, Lers-a system for learning from examples based on rough sets, in: Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory, Dordrecht: Springer Netherlands, 1992, pp. 3–18.