Lianmeng Jiao
email: jiaolianmeng@mail.nwpu.edu.cn

Quan Pan
email: panquannpu@gmail.com

Thierry Denoeux
email: thierry.denoeux@hds.utc.fr

Yan Liang
email: liangyan@nwpu.edu.cn

Xiaoxue Feng
email: fengxiaoxue@mail.nwpu.edu.cn

Belief rule-based classification system: extension of FRBCS in belief functions framework

Keywords: Pattern classification, Fuzzy rule-based classification system, Belief rule-based classification system, Belief functions theory, Pattern noise

Among the computational intelligence techniques employed to solve classification problems, the fuzzy rule-based classification system (FRBCS) is a popular tool capable of building a linguistic model interpretable to users. However, it may face lack of accuracy in some complex applications, by the fact that the inflexibility of the concept of the linguistic variable imposes hard restrictions on the fuzzy rule structure. In this paper, we extend the fuzzy rule in FRBCS with a belief rule structure and develop a belief rule-based classification system (BRBCS) to address imprecise or incomplete information in complex classification problems. The two components of the proposed BRBCS, i.e., the belief rule base (BRB) and the belief reasoning method (BRM), are designed specifically by taking into account the pattern noise that existes in many real-world data sets. Four experiments based on benchmark data sets are carried out to evaluate the classification accuracy, robustness, interpretability and time complexity of the proposed method.

Introduction

The fuzzy rule-based classification system (FRBCS) [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF][START_REF] Ishibuchi | Distributed representation of fuzzy rules and its application to pattern classification[END_REF][START_REF] Sun | Rule-base structure identification in an adaptive-network based fuzzy inference system[END_REF] is a useful tool to address classification problems, and it has become a popular framework for classifier design. It is widely employed due to its capability of building a linguistic model interpretable to users and addressing both quantitative and qualitative information coming from expert knowledge, mathematical models or empirical measures [START_REF] Sanz | Improving the performance of fuzzy rule-based classification systems with interval-valued fuzzy sets and genetic amplitude tuning[END_REF]. The FRBCS has been successfully applied to different real world classification tasks, including, but not limited to, image processing [START_REF] Stavrakoudis | A genetic fuzzy-rule-based classifier for land cover classification from hyperspectral imagery[END_REF], intrusion detection [START_REF] Tsang | A systematic fuzzy rule based approach for fault classification in transmission lines[END_REF],

fault classification [START_REF] Samantaray | Genetic-fuzzy rule mining approach and evaluation of feature selection techniques for anomaly intrusion detection[END_REF], target recognition [START_REF] Wu | Classification of battlefield ground vehicles using acoustic features and fuzzy logic rule-based classifiers[END_REF], and medical applications [START_REF] Akbarzadeh-Totonchi | A hierarchical fuzzy rule-based approach to aphasia diagnosis[END_REF][START_REF] Vinterbo | Small, fuzzy and interpretable gene expression based classifiers[END_REF]. However, on one hand, the FRBCS may face lack of accuracy when dealing with some complex applications, due to the inflexibility of the concept of the linguistic variable, which imposes hard restrictions on the fuzzy rule structure [START_REF] Alonso | Special issue on interpretable fuzzy systems[END_REF]. For example, when the input-output mapping varies in complexity within the space, homogeneous partitioning using linguistic variables for the input and output spaces becomes inefficient. Moreover, as the size of the rule base directly depends on the number of fuzzy partitions for each feature, the derivation of an accurate FRBCS causes the number of rules to rise significantly, which may make the system lose the capability of being interpretable to the users.

As both the interpretability (depends on several factors, mainly the rule structure, the number of rules, the number of features, the number of fuzzy partitions, and the shape of the fuzzy sets [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF]) and the accuracy are important in system modeling, two ways of improving the accuracy of an interpretable FRBCS have been developed. One is learning an optimized rule base with sophisticated methods, such as FURIA [START_REF] Hühn | FURIA: an algorithm for unordered fuzzy rule induction[END_REF], PDFC [START_REF] Chen | Support vector learning for fuzzy rule-based classification systems[END_REF], or FARC-HD [START_REF] Alcala-Fdez | A fuzzy association rule-based classification model for high-dimensional problems with genetic rule selection and lateral tuning[END_REF]. The other, as our main focus in this paper, is changing the rule structure to make it more flexible to characterize the input-output mapping, for example through introducing probability distribution [START_REF] Cordón | A proposal on reasoning methods in fuzzy rule-based classification systmes[END_REF] or interval-valued fuzzy sets [START_REF] Sanz | Improving the performance of fuzzy rule-based classification systems with interval-valued fuzzy sets and genetic amplitude tuning[END_REF].

In fact, different types of uncertainty, such as fuzziness, imprecision and incompleteness, may coexist in realworld complex systems. The FRBCS, which is based on fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF], cannot effectively address imprecise or incomplete information in the modeling and reasoning processes. The belief functions theory, also called Dempster-Shafer theory, proposed and developed by Dempster [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF] and Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] et al., has become one of the most powerful frameworks for uncertain modeling and reasoning. As fuzzy sets theory is well suited to dealing with fuzziness, and belief functions theory provides an ideal framework for handling imprecision and incompleteness, many researchers have investigated the relationship between fuzzy sets theory and belief functions theory and suggested different methods of integrating them [START_REF] Binaghi | Fuzzy Dempster-Shafer reasoning for rule-based classifiers[END_REF][START_REF] Chen | An extended rule-based inference for general decision-making problems[END_REF][START_REF] Liu | Fuzzy rule based evidential reasoning approach for safety analysis[END_REF][START_REF] Yager | Including probabilistic uncertainty in fuzzy logic controller modeling using Dempster-Shafer theory[END_REF][START_REF] Yang | Belief rule-based inference methodology using the evidential reasoning approach-RIMER[END_REF]. Among these methods, Yang et al. [START_REF] Yang | Belief rule-based inference methodology using the evidential reasoning approach-RIMER[END_REF] extended the fuzzy rule in belief functions theory and proposed a new knowledge representation scheme in a belief rule structure, which is capable of capturing fuzzy, imprecise, and incomplete causal relationships. The belief rule structure has been successfully applied in clinical risk assessment [START_REF] Kong | A belief rule-based decision support system for clinical risk assessment of cardiac chest pain[END_REF], inventory control [START_REF] Li | A belief-rule-based inventory control method under nonstationary and uncertain demand[END_REF], and new product development [START_REF] Tang | A methodology to generate a belief rule base for customer perception risk analysis in new product development[END_REF][START_REF] Yang | Belief rule-based methodology for mapping consumer preferences and setting product targets[END_REF]. This paper aims to extend the fuzzy rule in FRBCS with the belief rule structure developed in [START_REF] Yang | Belief rule-based inference methodology using the evidential reasoning approach-RIMER[END_REF] for classification applications. Compared with the fuzzy rule, the consequence part of the belief rule is in a belief distribution form, which is more informative and can characterize the uncertain information (i.e., fuzziness, imprecision, and incompleteness) existing in the training set. In addition, feature weights are introduced in the belief rule to characterize the different degrees of importance of features to the consequence. Therefore, the belief rule is more suitable for modeling those complex classification problems with great uncertainty. Based on the belief rule structure, a belief rule-based classification system (BRBCS) is developed as an extension of FRBCS in belief functions framework. In the proposed BRBCS, a data-driven belief rule base (BRB) generation method is developed to establish the uncertain association between the feature space and the class space. This BRB generation method enables the automatic generation of belief rules from the training data without the requirement of a priori expert knowledge. Then, to classify a query pattern based on the BRB, a belief reasoning method (BRM) is developed based on belief functions theory.

This BRM can well address the uncertainty existing in the consequences of activated belief rules for a query pattern.

To handle the pattern noise commonly existing in many real-world data sets, two techniques are developed in the BRB generation and BRM design processes. First, the consequence part of each belief rule in BRB is generated by fusing the information coming from all of the training patterns assigned to the corresponding antecedent fuzzy region.

In this way, the adverse effects of the noisy training patterns on the consequence of the belief rule can be reduced to some extent. Furthermore, in BRM, the final consequent class of a query pattern is obtained by combining the consequence parts of all of the belief rules activated by the query pattern. Thus, even if some unreliable belief rules are generated in noisy conditions, this procedure can further reduce the risk of misclassification.

Using belief functions theory to solve classification problems is not new, and some proposals have been introduced [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF][START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF][START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF][START_REF] Liu | A new belief-based k-nearest neighbor classification method[END_REF][START_REF] Liu | Credal classification rule for uncertain data based on belief functions[END_REF]. In [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], an evidential K-nearest neighbor (EK-NN) classification rule was proposed by extending the classical K-NN rule within the framework of belief functions theory. Liu et al. [START_REF] Liu | A new belief-based k-nearest neighbor classification method[END_REF][START_REF] Liu | Credal classification rule for uncertain data based on belief functions[END_REF] further extended the EK-NN method considering the belief assigned to meta-classes. These methods mainly focus on the uncertainty modeling and reasoning in K-nearest neighbor classification, whereas the BRBCS proposed in this paper aims to use the belief functions theory in the rule-based classification system, so these two schemes are different in nature.

Recently, Chen et al. [START_REF] Chen | A data driven rule-base inference approach for classification systems[END_REF] started to study the possibility of using belief functions theory in the rule-based classification system, but although the belief rule structure was introduced, the authors did not provide a method to derive the belief rule base from the data sets, and only the traditional fuzzy rule base was used in the experiment for illustration.

Later, a belief rule base representation, generation and inference method was proposed in [START_REF] Liu | A novel belief rule base representation, generation and its inference methodology[END_REF], where each training sample was developed as a rule with belief degrees embedded in the antecedent terms to model the input-output relationship. Although it has a similar theoretical foundation, the BRBCS proposed in our paper is developed in a quite different way. First, we use the rule structure considering belief distribution in the consequence part to well characterize the incompleteness induced by the limited training patterns. Second, we construct a belief rule associated with each activated fuzzy region by fusing all of the training samples assigned to this fuzzy region. In this manner, the constructed belief rules are more reliable, and the number of rules can be reduced greatly.

The rest of this paper is organized as follows. In Section 2, the basics of the fuzzy rule-based classification system and belief functions theory are introduced. The belief rule-based classification system (BRBCS) is developed in Section 3, and then four experiments are performed to evaluate the accuracy, robustness, interpretability and time complexity of the proposed BRBCS in Section 4. At last, Section 5 concludes the paper.

Preliminaries: fuzzy rule-based classification system and belief functions theory

In this section, we provide some preliminaries of the fuzzy rule-based classification system (FRBCS) and the belief functions theory. In Section 2.1, we describe the classical fuzzy rule structure followed by one of the most popular FRBCSs developed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF]. In Section 2.2, we introduce some basic concepts of belief functions theory that are necessary for developing the belief rule-based classification system.

Fuzzy rule-based classification system

A fuzzy rule-based classification system (FRBCS) is composed of two main conceptual components, the fuzzy rule base (FRB) and the fuzzy reasoning method (FRM). The FRB establishes an association between the space of pattern features and the space of consequent classes. The FRM provides a mechanism to classify a query pattern based on the FRB.

The fuzzy rule in the FRB for an M-class (denoted as Ω {ω 1 , ω 2 , • • • , ω M }) pattern classification problem with P features has the following structure [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF]:

Fuzzy Rule R q : If x 1 is A q
1 and • • • and x P is A q P , then the consequence is C q with rule weight θ q , q = 1, 2,

• • • , Q, (1)
where x = (x 1 , x 2 , • • • , x P ) is the pattern feature vector and A q = (A q 1 , • • • , A q P ) is the antecedent part, with each A q p belonging to fuzzy partitions {A p,1 , A p,2 , • • • , A p,n p } associated with the p-th feature. C q ∈ Ω is the label of the consequent class, and Q is the number of fuzzy rules in the FBR. The rule weight θ q , characterizing the certainty grade of the fuzzy rule R q , is used as the strength of R q in fuzzy reasoning.

Based on the above fuzzy rule structure, several FRB generation methods have been proposed [START_REF] Chen | Support vector learning for fuzzy rule-based classification systems[END_REF][START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF][START_REF] Ishibuchi | Hybridization of fuzzy GBML approaches for pattern classification problems[END_REF]. Here, we introduce the one proposed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF] because it is one of the most widely used algorithms. To generate the FRB, this method uses the following steps:

1. Establishment of the fuzzy regions. Usually, the partition of the pattern space is related to the specific classification problem. If no prior knowledge is available, the method based on simple fuzzy grids is usually employed [START_REF] Ishibuchi | Distributed representation of fuzzy rules and its application to pattern classification[END_REF]. Fig. 1 shows an example of the fuzzy partition of a two-dimensional pattern space with triangular fuzzy sets. Based on this method, once the domain interval and the partition number for each feature are determined, the fuzzy regions are easily computed.

x i = (x i1 , • • • , x iP ), i = 1, 2, • • • , N are available.
For each training pattern x i , the following steps are necessary (a) To calculate its matching degree µ(x i ) with different fuzzy regions using the product operator

µ A q (x i ) = P ∏ p=1 µ A q p (x ip ), (2)
where µ A q p (•) is the membership function of the fuzzy set A q p , (b) To assign the training pattern x i to the fuzzy region with the greatest matching degree, (c) To generate a rule for this training pattern, with the antecedent part determined by the selected fuzzy region and the consequent class equal to the class label of the training pattern, and (d) To compute the rule weight θ q .

Rules with the same antecedent part may be generated during the learning process. In this case, only the one having the maximum rule weight is maintained, whereas the remainder are removed.

Once the FRB is constructed, the query patterns can be classified by the following single winner FRM. Let S be the set of Q constructed fuzzy rules. A query pattern y = (y 1 , y 2 , • • • , y P ) is classified by a single winner rule R w , which is chosen from rule set S as

R w = arg max R q ∈S {µ A q (y) • θ q }. (3)
That is, the winner rule R w has the maximum product of the matching degree µ A q (y) and the rule weight θ q in S .

Because it is limited by the number of training patterns, the query pattern may not always be covered by any rule in the FRB, in which case the classification is rejected. To avoid the non-covering problem, several techniques have been proposed, such as using bell-shaped fuzzy sets instead of the triangular fuzzy sets [START_REF] Nozaki | Adaptive fuzzy rule-based classification systems[END_REF] or stretching a rule by deleting one or more of its antecedent terms [START_REF] Hühn | FURIA: an algorithm for unordered fuzzy rule induction[END_REF].

Basics of belief functions theory

In belief functions theory, a problem domain is represented by a finite set Θ = {θ 1 , θ 2 , • • • , θ n } of mutually exclusive and exhaustive hypotheses called the frame of discernment. A mass function or basic belief assignment (BBA)

expressing the belief committed to the elements of 2 Θ by a given source of evidence is a mapping function m(•):

2 Θ → [0, 1], such that m(∅) = 0 and ∑ A∈2 Θ m(A) = 1. (4)
Elements A ∈ 2 Θ having m(A) > 0 are called the focal elements of the BBA m(•). The BBA m(A) measures the degree of belief exactly assigned to a proposition A and represents how strongly the proposition is supported by evidence. The belief assigned to Θ, or m(Θ), is referred to as the degree of global ignorance. The probability assigned to any subset of 2 Θ , except for any individual proposition θ i (i = 1, • • • , n) and Θ, is referred to as the degree of local ignorance.

If there is no local or global ignorance, a belief function reduces to a conventional probability function, and the BBA m(•) is said to be Bayesian.

Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] also defines the belief function and plausibility function of A ∈ 2 Θ as follows

Bel(A) = ∑ B⊆A m(B) and Pl(A) = ∑ B∩A ∅ m(B). (5)
Bel(A) represents the exact support to A and its subsets, and Pl(A) represents the total possible support to A and its subsets. The interval [Bel(A), Pl(A)] can be seen as the lower and upper bounds of support to A. The belief functions m(•), Bel(•) and Pl(•) are in one-to-one correspondence.

For decision-making support, Smets [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF] proposed the pignistic probability BetP(A) (from the Latin word pignus, meaning a bet) to approximate the unknown probability in [Bel(A), Pl(A)] as follows

BetP(A) = ∑ B⊆Θ A∩B ∅ |A ∩ B| |B| m(B), ( 6
)
where |X| is the cardinality of set X.

m α (A) =          αm(A), for A Θ αm(Θ) + (1 -α), for A = Θ. (7)
Several distinct bodies of evidence characterized by different BBAs can be combined using Dempster's rule. Mathematically, Dempster's rule of combination of two BBAs m 1 (•) and m 2 (•) defined on the same frame of discernment (C) , for A ∈ 2 Θ and A ∅. Sometimes, the dissimilarity measure between two sources of evidence is needed, which is characterized by the distance between two BBAs. The choice for a well-adapted distance is not easy, and many distances have been defined, as shown in [START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF]. Here, we present the definition of Jousselme's distance d J [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], which is one of the most commonly used distances. The d J between two BBAs m 1 (•) m 1 and m 2 (•) m 2 defined on the same frame of discernment Θ is

Θ is m(A) =            0, for A = ∅ ∑ B∩C=A m 1 (B)m 2 (C) 1- ∑ B∩C=∅ m 1 (B)m 2
d J (m 1 , m 2 ) = √ 1 2 (m 1 -m 2 )D(m 1 -m 2 ) T , ( 9
)
where D is a 2 |Θ| × 2 |Θ| matrix with elements given by D i, j =

|A i ∩B j | |A i ∪B j | , A i , B j ∈ 2 Θ .
To interpret the belief functions theory in a more obvious way and to demonstrate its capacity for representing and reasoning with uncertain information, we provide the following murder example [START_REF] Denoeux | Introduction to belief functions[END_REF] for illustration.

Example 1. Suppose a murder has been committed. There are three suspects: Peter, John, and Mary. In the belief functions framework, the set Θ = {Peter, John, Mary} can be seen as the frame of discernment of the considered problem.

Suppose a witness saw the murderer going away, but he is short-sighted, and he only saw that it was a man. Based on this evidence, the following BBA can be constructed for the murderer m 1 ({Peter, John}) = 1.

(10)

Further, we know that the witness is drunk 20% of the time. This means that the above evidence holds with probability α = 0.8. Thus, Shafer's discounting operation in Eq. ( 7) can be used to obtain the corresponding BBA as

m α 1 ({Peter, John}) = 0.8, m α 1 (Θ) = 0.2. ( 11
)
Suppose when investigating the scene of the crime, a blond hair has been found, and we know there is a probability α = 0.6 that the room has been cleaned before the crime. In a similar way, we can obtain the second BBA as

m α 2 ({John, Mary}) = 0.6, m α 2 (Θ) = 0.4. ( 12
)
With the above two distinct pieces of evidence, Dempster's rule of combination can be used to fuse them into a final BBA as m({John}) = 0.48, m({Peter, John}) = 0.32, m({John, Mary}) = 0.12, m(Θ) = 0.08.

To judge who is most likely to be the murderer based on the above final BBA, we compute the belief Bel(•), the plausibility Pl(•) and the pignistic probability BetP(•) for each suspect using Eqs. [START_REF] Angiulli | Fast condensed nearest neighbor rule[END_REF][START_REF] Binaghi | Fuzzy Dempster-Shafer reasoning for rule-based classifiers[END_REF], as shown in Table 1. The belief Bel(•) and the plausibility Pl(•) for each suspect provide its lower and upper probabilities to be the murderer, respectively. The pignistic probability BetP(•) provides an approximate estimation between the lower and upper probabilities. For this example the same decision is made by maximizing Bel(•), Pl(•) and BetP(•): John is most likely to be the murderer. From the above example, it can be seen that the belief functions theory can adequately deal with uncertainty induced by partial evidence. As a generalized probability distribution, the mass function can represent local ignorance (such as the belief assigned to {John, Mary} and {Peter, John}) as well as global ignorance (the belief assigned to the frame of discernment Θ). In addition, belief functions theory provides effective tools (such as Dempster's rule of combination) for uncertain reasoning at the credal level using the formalism of mass function. At last, the final mass function is transformed into a probability measure (pignistic probability) to support the decision making at the pignistic level.

Belief rule-based classification system (BRBCS)

Considering the advantages of belief functions theory for representing and reasoning with uncertain information, in this section we extend the classical FRBCS in belief functions framework and develop the belief rule-based classification system (BRBCS). As in Fig. 2, the proposed BRBCS is composed of two components: the belief rule base (BRB) that establishes an association between the feature space and the class space and the belief reasoning method (BRM) that provides a mechanism to classify a query pattern based on the BRB. In Section 3.1, we first describe the belief rule structure for classification applications, which extends the traditional fuzzy rule structure in belief functions framework. Based on the belief rule structure, we learn the belief rule base from the training patterns in Section 3.2, and then the belief reasoning method is developed in Section 3.3.

Query Pattern Class

Training Patterns

Belief Rule Base (BRB)

Belief Reasoning Method (BRM)

Belief rule structure

The fuzzy rule structure expressed in Eq. ( 1) is relatively simple in that it does not consider the distribution of consequence and the relative importance of each feature. To take the above aspects into consideration, two concepts are introduced [START_REF] Yang | Belief rule-based inference methodology using the evidential reasoning approach-RIMER[END_REF]:

• Belief degrees of consequence. For a complex classification problem, it is likely that the consequence of a rule may take a few values with different belief degrees. Suppose the consequence may have

M different classes, ω 1 , ω 2 , • • • , ω M ,
and the corresponding belief degrees are represented by

β i (i = 1, 2, • • • , M), then the consequence with a belief structure can be represented by {(ω 1 , β 1 ), (ω 2 , β 2 ), • • • , (ω M , β M )}.
• Feature weights. As indicated in [START_REF] Jiao | Multi-hypothesis nearest-neighbor classifier based on class-conditional weighted distance metric[END_REF][START_REF] Jiao | An evidential k-nearest neighbor classification method with weighted attributes[END_REF], in real-world classification problems, different features may behave distinctly in determining the consequent class. Thus, there is a need to assign a weight to each feature to describe such degrees of importance.

To take into account the belief degrees of consequence and the feature weights, the fuzzy rule structure expressed in Eq. ( 1) can be extended to the following belief rule structure for classification purposes:

Belief Rule R q : If x 1 is A q 1 and • • • and x P is A q P , then the consequence is C q = {(ω 1 , β q 1 ), • • • , (ω M , β q M )} with rule weight θ q and feature weights δ 1 , • • • , δ P , q = 1, 2, • • • , Q, ( 14
)
where β q m is the belief degree to which ω m is believed to be the consequent class for the q-th belief rule. In the belief structure, the consequence may be incomplete, i.e., ∑ M m=1 β q m < 1, and the left belief 1 -∑ M m=1 β q m denotes the degree of global ignorance about the class label. The rule weight θ q with 0 ≤ θ q ≤ 1 characterizes the certainty grade of the belief rule R q and the feature weights

δ 1 , • • • , δ P with 0 ≤ δ 1 , • • • , δ P ≤ 1 describe the importance of different features in determining the consequent class.
Remark 1. Compared with the fuzzy rule structure, the belief rule structure has some advantages for classification problems as follows. a) In the belief rule structure, the consequence is in a belief distribution form. On the one hand, with the distribution form, any difference in the antecedent part can be clearly reflected in the consequence, whereas in a traditional fuzzy rule, different antecedents may lead to the same consequence. On the other hand, by introducing belief functions theory, the belief structure makes the rule more appropriate to characterize the uncertain information.

In generating each rule, only limited training patterns are available, and each training pattern only provides partial evidence about the consequence of this rule. Thus, the corresponding consequence of this rule should not be complete.

The belief rule structure can well characterize this incompleteness, with the remained belief 1 -∑ M m=1 β q m denoting the degree of global ignorance about the class label induced by the limited training patterns. b) With the introduction of feature weights, the importance of different features to the consequence can be well characterized, which is closer to reality. In summary, compared with the traditional fuzzy rule, the belief rule is more informative, more flexible and thus more suitable for modeling those complex classification problems.

Belief rule base (BRB) generation

To make a classification with BRBCS, the first step is to generate a BRB from the training set. The FRB generation method given by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF] is used as a base model in this section to develop the BRB generation method in belief functions framework. As displayed in Eq. ( 14), each belief rule is composed of four components, namely, the antecedent part, the belief degrees of consequence, the rule weight and the feature weights. Because the antecedent part in the belief rule is the same as that in the fuzzy rule, here we only focus on the generation of the latter three components, i.e., the belief degrees of consequence, the rule weight and the feature weights.

Generation of belief degrees of consequence

In this part, with the symbols defined in Section 2.1 and Section 3.1, we develop an algorithm to generate the belief degrees of consequence in BRB.

Similar to the generation of the consequent class in FRB in the first step, we also need to calculate the matching degree µ A q (x i ) of each training pattern x i with the antecedent part A q using Eq. ( 2). In FRB, the consequent class is directly specified as the class label of the training pattern having the greatest matching degree with the antecedent part A q . However, this procedure may entail great risk, especially when class noise exists in the training set. In BRB, we fuse the class information of all of the training patterns assigned to the corresponding antecedent fuzzy region to get the consequence in a belief distribution form. Denote as T q the set of training patterns assigned to the antecedent fuzzy region A q . From the view of belief functions theory, the class set Ω = {ω 1 , • • • , ω M } can be regarded as the frame of discernment of the problem. For any training pattern x i ∈ T q , the class label Class(x i ) = ω m can be regarded as a piece of evidence that increases the belief that the consequent class belongs to ω m . However, this piece of evidence does not by itself provide 100% certainty. In belief functions theory, this can be expressed by saying that only some part of the belief (measured by the matching degree µ A q (x i )) is committed to ω m . Because Class(x i ) = ω m does not point to any other particular class, the rest of the belief should be assigned to the frame of discernment Ω representing global ignorance. Therefore, this item of evidence can be represented by a BBA m q i (•) verifying:

               m q i ({ω m }) = µ A q (x i ) m q i (Ω) = 1 -µ A q (x i ) m q i (A) = 0, ∀A ∈ 2 Ω \ {Ω, {ω m }}, (15)
with 0 < µ A q (x i ) ≤ 1.

For each x i ∈ T q , a BBA depending on both its class label and its matching degree with the antecedent part can therefore be defined. To obtain the consequence associated with the antecedent part A q in a belief distribution form, these BBAs can be combined using Dempster's rule. As shown in Eq. ( 15), only two focal elements are involved in each BBA. Because of the particular structure of the BBA, the computational burden of Dempster's rule can be greatly reduced, and the analytical formulas can be derived as

m q ({ω m }) = 1 1-K q        1 - ∏ x i ∈T q m (1 -µ A q (x i ))        • ∏ r m ∏ x i ∈T q r (1 -µ A q (x i )), m = 1, 2, • • • , M, m q (Ω) = 1 1-K q M ∏ r=1 ∏ x i ∈T q r (1 -µ A q (x i )), (16)
where T q m is a subset of T q , corresponding to those training patterns belong to class ω m , and K q is the total conflicting belief mass

K q = 1 + (M -1) M ∏ r=1 ∏ x i ∈T q r (1 -µ A q (x i )) - M ∑ m=1 ∏ r m ∏ x i ∈T q r (1 -µ A q (x i )). ( 17
)
Therefore, the belief degrees of consequence of rule R q can be given by

β q m = m q ({ω m }), m = 1, 2, • • • , M, β q Ω = m q (Ω), (18)
where β q Ω is the belief degree unassigned to any individual class.

Remark 2. In the classical FRBCS reviewed in Section 2.1, the consequence of each rule is only determined by the class label of the training pattern having the greatest matching degree with the antecedent part, whereas the consequence in the belief rule fuses information that comes from all of the training patterns assigned to the corresponding antecedent fuzzy region. Thus, it can effectively reduce the adverse effects of some noisy training patterns. The method to generate the consequence is similar to some data-cleaning approaches [START_REF] Angiulli | Fast condensed nearest neighbor rule[END_REF][START_REF] Dasarathy | Noising around the neighbourhood: a new system structure and classification rule for recognition in partially exposed environments[END_REF]. The difference is that the data-cleaning approaches remove the unreliable training samples, whereas our method retains all training samples and generates the consequence in a belief distribution form, which can be considered as soft labels. Compared with the data cleaning approaches, the belief distribution form maintains more information from the training samples and can be further combined with the consequences of other rules in later processing.

Remark 3. The idea to generate the belief degrees of consequence in this paper is inspired by the EK-NN classification method developed by Denoeux [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], in which each of the k nearest neighbors of the query sample is considered as an item of evidence that supports certain hypotheses regarding the class membership of that pattern. The corresponding relations of the two methods are as follows: a) the training patterns assigned to the corresponding antecedent fuzzy region correspond to the k nearest neighbors of the query pattern in EK-NN, and b) the importance of each training pattern is measured by the matching degree with the antecedent part, and in EK-NN, that is measured by the distance from the query pattern. With the above relationship, it can be further deduced that the consequence generation method in FRB revisited in Section 2.1 has a similar idea to the voting K-NN classification method [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF]. As illustrated in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], the EK-NN classifier can obtain much better performance than the voting K-NN classifier, especially in noisy conditions. Thus, it is expected that the belief distribution form of consequence in the BRB can handle the class noise more effectively than the single class form of consequence in the FRB.

Generation of rule weights

In the area of data mining, two measures called confidence and support have often been used for evaluating association rules [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. Our belief rule R q in Eq. ( 14) can be viewed as a type of association rule of the form A q ⇒ C q .

The main difference from the standard formulation of the association rule is that in our belief if-then rule, the input variable is in fuzzy form and the output variable is in belief distribution form. In this part, we will draw the rule weight θ q from the concepts of confidence and support.

The confidence is defined as a measure of the validity of one association rule [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. For our belief if-then rule, the consequence part C q is obtained by combining the items of evidence coming from all of the training patterns assigned to the antecedent fuzzy region A q . It is believed that if the items of evidence involved are in conflict with each other (for example, if the items of evidence assign different classes with the highest belief), then the consequence has low validity. In belief functions theory, several models are proposed to measure the conflict among different items of evidence [START_REF] Liu | Analyzing the degree of conflict among belief functions[END_REF][START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF]. The conflict factor ∑ B∩C=∅ m 1 (B)m 2 (C) derived in Dempster's rule is employed here for its simplicity and convenience. The confidence of the belief rule R q is hence defined as

c(R q ) = 1 -K q , ( 19
)
with the average conflict factor 0 ≤ K q ≤ 1 calculated by

K q =            0, if |T q | = 1, 1 |T q |(|T q |-1) ∑ x i ,x j ∈T q ;i< j ∑ B∩C=∅ m q i (B)m q j (C), otherwise. ( 20
)
where |T q | is the number of training patterns assigned to the fuzzy region A q .

On the other hand, as described in [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF], the support indicates the grade of the coverage by one association rule.

For our belief if-then rule, N training patterns are available for rule generation, while only those assigned to the corresponding antecedent fuzzy region are used to generate the consequence. Therefore, the support of the belief rule R q is defined as

s(R q ) = |T q | N . ( 21
)
As defined above, the confidence and support characterize the weight of the belief rule in two distinct aspects and should therefore be considered jointly. On the one hand, if the belief rule R q has high confidence but low support (for example, if only one training pattern is assigned to the antecedent fuzzy region A q ), the belief rule weight should be decreased, as the consequence may be easily affected by the class noise. On the other hand, if the belief rule R q has high support but low confidence (for example, if a large number of training patterns are contained in T q but with great divergence in the class label), the belief rule weight should also be decreased, considering the great conflicts. The product of the confidence c(R q ) and the support s(R q ) is used to characterize the weight of the belief rule R q as

θ q ∝ c(R q ) • s(R q ). ( 22
)
Following a normalization process, we obtain the weights of all of the belief rules as

θ q = c(R q ) • s(R q ) max q {c(R q ) • s(R q ), q = 1, • • • , Q} , q = 1, 2, • • • , Q. ( 23
)

Generation of feature weights

In the belief rule displayed as Eq. ( 14), the feature weights reflect the relative importance of the antecedent features with respect to their influence on the consequence of the rule. In other words, an antecedent feature with a higher weight is more influential on the consequence. Therefore, to determine a feature weight is to find a way to measure the relative intensity of the influence that this antecedent feature imposes on the consequence in comparison with others. In this part, such a measurement is quantified by a so-called correlation factor (CF) between each feature and the consequence.

Suppose n p fuzzy partitions {A p,1 , A p,2 , • • • , A p,n p } are established for feature A p . Now, we will derive the weight of feature A p through correlation analysis with the corresponding consequence. Specifically, we use the relationship between the changes of different fuzzy partitions that A p takes and the changes of the consequence to determine the correlation between A p and the consequence.

As Q belief rules with different antecedent parts are available in the BRB, in the first place, for feature A p , according to its n p fuzzy partitions

{A p,1 , A p,2 , • • • , A p,n p }, we divide the BRB into n p sub-BRBs B k , k = 1, 2, • • • , n p ,
with each sub-BRB B k containing all of the belief rules using the fuzzy partition A p,k for feature A p :

B k = { R q | A q p = A p,k , q = 1, 2, • • • , Q } , k = 1, 2, • • • , n p . (24)
Then, for each sub-BRB B k , the consequence parts of all of the contained belief rules are combined to obtain the integrated consequence m k (•) with the weighted averaging operation:

m k ({ω m }) = 1 ∑ R q ∈B k θ q ∑ R q ∈B k θ q • β q m , m = 1, 2, • • • , M, m k ({Ω}) = 1 ∑ R q ∈B k θ q ∑ R q ∈B k θ q • β q Ω , (25)
where andβ q Ω are the belief degrees of consequence of rule R q generated in Section 3.2.1, and θ q is the rule weight of R q generated in Section 3.2.2.

β q m , m = 1, 2, • • • , M,

Thus, when A p changes its fuzzy partition from

A p,k to A p,k+1 , k = 1, 2, • • • , n p -1, the change of the consequence is ∆C p,k = d J (m k , m k+1 ), (26)
where m k = m k (•), and d J is Jousselme's distance, as displayed in Eq. ( 9).

Then, the average change of the consequence for k changing from 1 to n p -1 is given by

∆C p = n p -1 ∑ k=1 ∆C p,k n p -1 . (27)
In this paper, we define ∆C p as the correlation factor (CF) between feature A p and the consequence, i.e.,

CF p = ∆C p . (28)
In a similar way, we obtain the correlation factors CF p , p = 1, 2, • • • , P for all features. Further, δ p , the weight of feature A p , can be generated from the normalized CF p as follows

δ p = CF p max p {CF p , p = 1, 2, • • • , P} , p = 1, 2, • • • , P. ( 29
)

Belief reasoning method (BRM)

As revisited in Section 2.1, in FRBCS, the single winner FRM is used to classify a new query pattern. However, when excessive noise exists in the training set, this method may have a great risk of misclassification. In this section, we will fuse the consequences of all of the rules activated by the query pattern within the framework of belief functions theory to get a more robust classification. The main idea is firstly calculating the association degrees of the query pattern with the consequences of the activated belief rules and then combining these consequences with respect to their reliability (characterized by the association degrees) based on belief functions theory.

Association degree with the consequence of a belief rule

Denote y = (y 1 , y 2 , • • • , y P ) as a query pattern to be classified. In the first place, the matching degree of the query pattern with the antecedent part of each rule is calculated. As the feature weights are complemented in the belief rule, we use the following simple weighted multiplicative aggregation function to calculate the matching degree

µ A q (y) =         P ∏ p=1 [ µ A q p (y p ) ] δ p         1/P , (30)
where µ A q p (•) is the membership function of the antecedent fuzzy set A q p , and δ p is the weight of the p-th feature given in Eq. ( 29).

Remark 4. In Eq. ( 30), the contribution of a feature towards the matching degree is positively related to the weight of the feature. In other words, a more important feature plays a greater role in determining the matching degree.

Particularly, if δ p = 0, then

[ µ A q p (y p )
] δ p = 1, which shows that a feature with zero importance does not have any impact on the matching degree; if δ p = 1, then

[ µ A q p (y p ) ] δ p = µ A q
p (y p ), which shows that the most important feature has the largest impact on the matching degree.

Let S be the set of Q constructed belief rules in the BRB. Denote as S ′ ⊆ S the set of belief rules activated by query pattern y:

S ′ = {R q | µ A q (y) 0, q = 1, 2, • • • , Q} . (31)
The association degree of query pattern y with the consequence of one activated belief rule R q ∈ S ′ is determined by two factors, the matching degree and the rule weight. The matching degree reflects the similarity between the query pattern and the antecedent part of the belief rule, while the rule weight characterizes the reliability of the belief rule.

Thus, the association degree is defined as

α q = µ A q (y) • θ q , for R q ∈ S ′ . ( 32
)
Remark 5. As a result of limitation due to the number of training patterns, in some applications, there may be no rule activated by query pattern y. In such a case, we classify the non-covered query pattern based on the generated rule which has the nearest distance with it. For a non-covered query pattern y, we first find the fuzzy region

A * = (A * 1 , A * 2 , • • • , A * P )
that has the greatest matching degree with it. The distance between a non-covered query pattern y and one generated rule R q is defined as d(y, R q ) = ∥A * -A q ∥ 2 , where A q is the antecedent fuzzy region of rule R q . Further, if several generated rules have the same nearest distance to the non-covered query pattern, the consequences of these rules are combined using belief functions theory in the following section, considering the rule weight as the reliability factor α.

Reasoning using belief functions theory

In the previous part, the association degrees of query pattern y with the consequences of the activated belief rules are calculated. In [START_REF] Yang | Belief rule-based inference methodology using the evidential reasoning approach-RIMER[END_REF], an evidential reasoning (ER) method was used to combine different rules, considering their association degrees (or weights). As the ER method was first proposed for multi-attribute decision making problems [START_REF] Yang | On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty[END_REF], it considers the weights as the importance factors representing the decision maker's subjective preference in the fusion process. However, for pattern classification problems, the weights should be considered as the reliability factors representing the rules' capability to provide a correct assessment of the input query pattern [START_REF] Jiao | Combining sources of evidence with reliability and importance for decision making[END_REF]. Therefore, the ER method is not reasonable for the pattern classification problems, and in the following, a belief reasoning method (BRM) is developed to combine the belief rules activated by the query pattern.

In belief functions theory, Shafer's discounting operation, displayed as Eq. ( 7), is usually used to discount the unreliable evidence before combination. Regarding association degree α in Eq. ( 32) as the reliability factor, the consequence of one activated belief rule in Eq. ( 18) is discounted using Shafer's discounting operation as

m α ({ω m }) = α • β m , m = 1, 2, • • • , M, m α (Ω) = α • β Ω + (1 -α) (33)
For all of the |S ′ | = L activated belief rules, through the above formula, we can get the corresponding discounted

consequences m α i (•), i = 1, 2, • • • , L.
To make a decision regarding the discounted consequences of activated belief rules, the corresponding BBAs can be combined using Dempster's rule. However, as indicated in [START_REF] Denoeux | Approximating the combination of belief functions using the fast möbius transform in a coarsened frame[END_REF][START_REF] Wilson | Algorithms for Dempster-Shafer theory[END_REF], the direct use of Dempster's rule will result in an exponential increase in computational complexity for the reason of enumerating all subsets or supersets of a given subset A of Ω, and the operation becomes impractical when the frame of discernment has more than 15 to 20 elements. The following part is intended to develop an operational algorithm for evidence combination with linear computational complexity, considering the fact that the focal elements of each associated BBA are all singletons except the ignorance set Ω.

Define I(i) as the index set of the former i BBAs. Let m I(i) (•) be the BBA after combining all of the former i BBAs associated with I(i). Given the above definitions, a recursive evidence combination algorithm can be developed as

follows m I(i+1) ({ω q }) = K I(i+1) [ m I(i) ({ω q }) • m α i+1 ({ω q }) + m I(i) (Ω) • m α i+1 ({ω q }) +m I(i) ({ω q }) • m α i+1 (Ω) ] , q = 1, 2, • • • , M m I(i+1) (Ω) = K I(i+1) [ m I(i) (Ω) • m α i+1 (Ω) ] K I(i+1) = [ 1 - M ∑ j=1 M ∑ p=1,p j m I(i) ({ω j }) • m α i+1 ({ω p }) ] -1 i = 1, 2, • • • , L -1, (34)
where K I(i+1) is a normalizing factor, so that

M ∑ q=1 m I(i+1) ({ω q }) + m I(i+1) (Ω) = 1.
Note that m I(1) ({ω q }) = m α 1 ({ω q }) for q = 1, 2, • • • , M and m I(1) (Ω) = m α 1 (Ω). Thus, this recursive evidence combination algorithm can initiate with the first BBA. Accordingly, as the recursive index i reaches L -1, the final results m I(L) ({ω q }) and m I(L) (Ω) (m({ω q }) and m(Ω) for short, respectively) are obtained by combining all of the L BBAs. This combination result is the basis for the later decision process.

For decision making based on the combined BBA m(•) calculated with Eq. ( 34), the belief function Bel(•), plausi-bility function Pl(•) and pignistic probability BetP(•) are common alternatives. As the focal elements of the combined BBA m(•) are all singletons except the ignorance set Ω, the credibility, plausibility and pignistic probability of each class ω q are calculated as follows

Bel({ω q }) = m({ω q }) Pl({ω q }) = m({ω q }) + m(Ω) BetP({ω q }) = m({ω q }) + m(Ω) M q = 1, 2, • • • , M. ( 35
)
It is supposed that based on this evidential body, a decision has to be made in assigning query pattern y to one of the classes in Ω. Because of the particular structure of the combined BBA (i.e., the focal elements are either singletons or the whole frame Ω), it can be easily discovered that ω = arg max

ω q ∈Ω Bel({ω q }) = arg max ω q ∈Ω Pl({ω q }) = arg max ω q ∈Ω BetP({ω q }) = arg max ω q ∈Ω m({ω q }). ( 36
)
That is, the strategies maximizing the three criteria Bel(•), Pl(•), and BetP(•) in Eq. ( 35) lead to the same decision: the pattern is assigned to the class with maximum basic belief assignment m(•).

Remark 6. For some classification applications under harsh working conditions (e.g., battlefield target recognition), significant noise may exist in the training set. Though the consequence generation method proposed in Section 3.2.1 can reduce the adverse effects from pattern noise, the consequence of one rule may still be unreliable in excessively noisy conditions. The BRM developed within the framework of belief functions theory combines the consequences of all of the activated rules to obtain the final consequent class. Therefore, compared with the single winner FRM, the BRM can further reduce the risk of misclassification.

Experiments

The performance of the proposed BRBCS will be empirically assessed through three different experiments with 20 real-world classification problems from the well-known UCI Repository of Machine Learning Databases [START_REF] Merz | UCI Repository of Machine Learning Databases[END_REF]. In the first experiment, the original data sets are used to evaluate the classification accuracy of the proposed BRBCS.

In the second one, the noise is added to the data sets artificially in controlled settings to evaluate the classification robustness of the proposed BRBCS in noisy training set conditions. In the latter two experiments, we will provide an analysis of its interpretability and time complexity, respectively.

Data sets and experiment conditions

Twenty well-known benchmark data sets from the UCI repository are selected to evaluate the performance of the BRBCS. The main characteristics of the 20 data sets are summarized in Table 2, where "# Instances" is the number of instances in the data set, "# Features" is the number of features, and "# Classes" is the number of classes. Notice that for the data sets Cancer, Diabetes and Pima, we have removed the instances with missing feature values. To develop the different experiments, we consider the B-Fold Cross-Validation (B-CV) model [START_REF] Raudys | Small sample effects in statistical pattern recognition: recommendations for practitioners[END_REF]. Each data set is divided into B blocks, with B -1 blocks as a training set and the remaining block as a test set. Therefore, each block is used exactly once as a test set. We use the 5-CV here, i.e., five random partitions of the original data set, with four of them (80%) as the training set and the remainder (20%) as the test set. For each data set, we consider the average results of the five partitions.

For the first, third and fourth experiments, the original data sets described above are used directly, while for the second, some additional processes are needed. As discussed in [START_REF] Sáez | Tackling the problem of classification with noisy data using Multiple Classifier Systems: Analysis of the performance and robustness[END_REF][START_REF] Sáez | On the suitability of fuzzy rule-based classification systems with noisy data[END_REF][START_REF] Zhu | Class noise vs. attribute noise: a quantitative study[END_REF], the pattern noise in the data set can be distinguished into two categories: class noise and feature noise. The class noise, also known as labeling error, occurs when a sample is assigned to an incorrect class. It can be attributed to several causes, including subjectivity during the labeling process, data entry errors, or limitations of the equipped measure instrument. In contrast, the feature noise is used to refer to corruptions in the values of one or more features of samples in a data set, which is often encountered in harsh working conditions. With the above consideration, in the second experiment, we will manage the robustness evaluation under two types of noise scenarios, class noise and feature noise.

As the initial amount of noise present in the original data sets is unknown, we use manual mechanisms to independently add noise to each data set to control the noise level for comparison. Additionally, to observe how noise affects the accuracy of the classifiers, the noise is only added in the training sets, while the test sets remain unchanged. Based on the type of noise, as in [START_REF] Sáez | Tackling the problem of classification with noisy data using Multiple Classifier Systems: Analysis of the performance and robustness[END_REF], different schemes of noise introduction are designed as follows.

• To evaluate the performance of the difference methods, in the first experiment, the classification accuracy rate criterion is utilized. In the second experiment, apart from the classification accuracy rate under each level of induced noise, we also take into account the following relative loss of accuracy (RLA) to observe the form in which the accuracy of one algorithm is affected when increasing the level of noise with respect to the case without noise.

RLA x% = Acc 0% -Acc x% Acc 0% , (37)
where RLA x% is the relative loss of accuracy at noise level x%, Acc 0% is the classification accuracy in the test with the original data set, and Acc x% is the classification accuracy when testing the data set with noise level x%.

To assess whether significant differences exist among different methods, we adopt a nonparametric statistical analysis. For conducting multiple statistical comparisons over multiple data sets, as suggested in [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF][START_REF] García | Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power[END_REF], the Friedman test and the corresponding post hoc Bonferroni-Dunn test are employed. For performing multiple comparisons, it is necessary to check whether the results obtained by different methods present any significant difference (Friedman test), and in the case of finding one, we can find out by using a post hoc test to compare the control method with the remaining methods (Bonferroni-Dunn test). We use α = 0.05 as the level of significance in all cases. For a detailed description of these tests, one can refer to [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF][START_REF] García | Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power[END_REF].

Classification accuracy evaluation

In the first experiment, we aim to compare the classification accuracy of our proposed BRBCS with the classical FRBCS proposed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], as reviewed in Section 2.1, and the following two methods improved through changing the rule structure to make it more flexible to characterize the input-output mapping.

1. FRBCS extended by Cordón et al. [START_REF] Cordón | A proposal on reasoning methods in fuzzy rule-based classification systmes[END_REF] (EFRBCS): Compared with the basic fuzzy rule structure in Eq. ( 1), in this method, a fuzzy rule with certainty degrees for all classes in the consequent part is considered.

R q : If x 1 is A q 1 and • • • and x P is A q P , then (r q 1 , • • • , r q M ), for q = 1, 2, • • • , Q, ( 38
)
where r q j is the certainty degree for rule R q to predict class ω j for a pattern belonging to the fuzzy region represented by the antecedent part of the rule. Different from the belief rule structure employed in our proposed BRBCS, the consequence of this rule is in probability distribution, i.e., the sum of certainty degrees for all classes equals one. Accordingly the additive combination reasoning method is employed to classify a query pattern.

2. EBRB method proposed by Liu et al. [START_REF] Liu | A novel belief rule base representation, generation and its inference methodology[END_REF]: In this method, a rule base is designed with belief degrees embedded in the consequence part as well as in all of the antecedent terms of each rule for expert inference. However, when using for classification, the consequence part of each rule degenerates into a signal class label.

R q : If x 1 is { (A 1, j , α q 1, j ), j = 1, • • • , n 1 } and • • • and x P is { (A P, j , α q P, j ), j = 1, • • • , n P } , then the consequence is C q with rule weight θ q , q = 1, 2, • • • , Q, ( 39
)
where the antecedent term for each feature

{ (A p, j , α q p, j ), j = 1, • • • , n p } is in belief distribution.
Based on the above rule structure, each training sample is developed as a rule to model the input-output relationship, and accordingly, the query pattern is classified by the additive combination of the weighted consequences of all of the rules.

The settings of the considered methods are summarized in Table 3. As for the considered data sets no prior knowledge about the establishment of the fuzzy regions is available, and the simple fuzzy grids are used to partition the feature space. We normalize each feature value into a real number in the unit interval [0, 1]. Once the number of partitions for each feature is determined, the fuzzy partitions can be easily computed. Here, different numbers of partitions (C = 3, 5, 7) are employed to make the comparison. Table 4 and Table 5 show the classification accuracy rates of our proposed BRBCS in comparison with other rule-based methods over the training data and the test data, respectively. The numbers in brackets represent the rank of each method. It can be seen that in both cases, the proposed BRBCS outperforms other methods for most of the data sets. To compare the results statistically, we use nonparametric tests for multiple comparisons to find the best method, considering the average ranks obtained over the test data. First, we use the Friedman test to determine whether significant differences exist among all of the mean values. Table 6 shows the Friedman statistic F F for each number of partitions, and it relates them to the corresponding critical values by using a level of significance of α = 0.05. Given that the Friedman statistics are clearly greater than their associated critical values, there are significant differences among the observed results with a level of significance α = 0.05 for all of the three partition numbers. Then, we apply the Bonferroni-Dunn test to compare the best ranking method (BRBCS) with the remaining methods. Table 7 presents these results. We can see that the Bonferroni-Dunn test rejects all of the hypotheses of equality with the rest of the methods with p < α/(k -1). Therefore, by the analysis of the statistical study shown in Tables 6 and7, we conclude that our BRBCS is a solid model for classifier design, as it has shown itself to be the best accuracy method when compared with the other rule-based methods applied in this study. analyze the effect of partition numbers on classification performance, in Table 4 and Table 5, the best accuracy rate for each data set is underlined. It can be seen that the classification accuracy is not always ideally improving according to the increase of partition number, especially for those data sets with relatively more features, which is caused by the limited number of training samples. Additionally, as will be shown in Section 4.5, a larger partition number usually means a greater computation burden. Therefore, in practice, for those data sets with fewer features (M < 10), we suggest using a partition number C = 5; otherwise, a partition number C = 3 is suggested to get a better trade-off between accuracy and complexity.

Classification robustness evaluation

In the second experiment, we aim to analyze the classification robustness of our proposed BRBCS when noise is present in the training sets. Apart from the classical FRBCS introduced in Section 2.1, the following two robust classifiers are also considered for comparison.

1. C4.5 [START_REF] Quinlan | C4.5: programs for machine learning[END_REF]: C4.5 is considered to be a robust learner tolerant to noisy data. It iteratively builds a decision tree that correctly classifies the largest number of examples. Additionally, a pruning strategy is used to reduce the chances of the classifier being affected by noisy data from the training set.

2. BagC4. 5 [42]: This is a multiple classifier system that considers C4.5 as the base classifier. In this method, the bagging technique is used to resample the original training set, and then the base classifier is trained with different data sets. As experimentally analyzed in [START_REF] Sáez | Tackling the problem of classification with noisy data using Multiple Classifier Systems: Analysis of the performance and robustness[END_REF], BagC4.5 is a good noise-robust multiple classifier system.

The settings of the considered methods are summarized in Table 8. In the following, different types of noise (class noise and feature noise) with different noise levels (NL = 10%, 20%, 30%, 40%, 50%) are tested for comparison. Fig. 3 shows the classification accuracy rate of each data set at different class noise levels. It may be observed that for most data sets, the proposed BRBCS outperforms the other methods at any class noise level. To verify the robustness of the proposed method more specifically, Table 9 gives the RLA of our proposed BRBCS in comparison with other robust methods at different class noise levels. The numbers in brackets represents the rank of each method.

For nonparametric statistical analysis, firstly, based on the average ranks of the different methods in Table 9, the Friedman test is conducted to evaluate whether significant differences exist among the different methods. Table 10 shows the Friedman test result of RLA for the considered methods at different class noise levels. Given that the Friedman statistics are clearly greater than their associated critical values, there are significant differences among the observed results with a level of significance of α = 0.05 at all class noise levels. Then, we use the Bonferroni-Dunn test to compare the best ranking method (BRBCS) with the remaining methods. Table 11 presents these results.

We can see that the Bonferroni-Dunn test rejects all of the hypotheses of equality with the rest of the methods with p < α/(k -1), except for the BagC4.5 method at noise level NL = 10%. This means that there is no significant difference only between BRBCS and BagC4.5 at noise level NL = 10% with significance level α = 0.05. With the increase of the noise level, the p value associated with each of the remaining methods becomes much lower. Thus, the RLA differences are more significant at higher noise levels, showing the superior robustness of the proposed BRBCS in disruptive class noise conditions. Fig. 4 shows the classification accuracy rate of each data set with different feature noise levels. Similar to the results under class noise conditions, for most data sets, the test accuracy is always higher for BRBCS than for the other robust methods under the feature noise scheme. Table 12 shows the RLA of our proposed BRBCS in comparison with other robust methods at different feature noise levels. In a similar manner, we first use the Friedman test to evaluate whether significant differences exist among the different methods. Table 13 shows the Friedman test result of RLA for the considered methods at different feature noise levels. It can be seen that the Friedman statistics are clearly greater than their associated critical values at all feature noise levels, which means that there are significant differences among the observed results with a level of significance of α = 0.05. Then, we use the Bonferroni-Dunn test to compare the best ranking method (BRBCS) with the remaining methods. As shown in Table 14, the Bonferroni-Dunn test rejects all of the hypotheses of equality with the rest of the methods with p < α/(k -1), except for the BagC4.5 method at noise levels NL = 10% and NL = 30%. In other words, there is no significant difference between BRBCS and BagC4.5 at noise levels NL = 10% and NL = 30% with significance level α = 0.05. This is mainly because the feature noise is not very disruptive at relatively lower noise levels. With the increase of the noise level, the p value associated with each of the remaining methods becomes much lower. Thus, the RLA differences are more significant at higher noise levels, which shows the superior robustness of the proposed BRBCS in disruptive feature noise conditions.

Interpretability analysis

As mentioned in the introduction, in addition to accuracy, interpretability is also an important criterion for rulebased systems. In [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF], the authors presented an overview of the interpretability measures of rule-based systems. In this experiment, the following three widely accepted interpretability measures recommended in [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF] are utilized to make a quantitative analysis.

• Number of rules (# Rule): According to the principle of Occam's razor (the best model is the simplest one fitting the system behavior well), the set of fuzzy rules should be as small as possible under conditions in which the model performance is preserved to a satisfactory level.

• Number of conditions (# Conditions):

The number of conditions should be as small as possible in order to ease the readability of the rules.

• Number of fired rules for a given input (# Fired rule):

The number of rules used for the reasoning of a given input should be as small as possible in order to control the semantic interpretability.

Based on the above three interpretability measures, we test the four rule-based methods shown in Table 3. Twenty real-world problems shown in Table 2 are considered for evaluation, and the 5-CV model is used to calculate the average results. For those data sets with few features (M < 10), we use the partition number C = 5; otherwise the partition number C = 3 is selected. Table 15 shows the results of the three interpretability measures for different methods.

requirements. The accuracy improvement of the proposed BRBCS is achieved at the expense of a slight decrease in interpretability.

Time complexity analysis

In this section, a time complexity analysis of the proposed BRBCS is provided to show to what extent the runtime depends on factors such as the number of instances, the number of features and the number of partitions. Twenty realworld problems (with the numbers of training instances ranging from 85 to 16, 000 and the numbers of features ranging from 3 to 36) shown in Table 2 are considered for evaluation. Three different numbers of partitions, C = 3, 5, 7, are tested, and the 5-CV model is used to calculate the average runtime. The numerical experiments are executed by MATLAB 7.12 on an HP EliteBook 8570p with an Intel(R) Core(TM) i7-3540 M CPU @3.00 GHz and 8 GB memory. By analyzing the results presented in Table 16, we can see that the runtimes for both the training and testing phases mainly depend on the number of generated rules. More rules usually means more time to train the BRB and also more time to classify a pattern based on the generated BRB. Thus, we can instead analyze how the factors affect the number of rules. First, for each data set, the number of rules always increases with increases in the partition number. However, the number of rules cannot increase indefinitely, as it is constrained by the number of training instances. Second, by comparing different data sets, we can see that a larger number of features usually results in a larger number of rules (e.g., the data sets Letter and Satimage). However, this tendency is also constrained by the number of training instances. For example, although the data set Vehicle has a larger number of features than Magic, it has a relatively smaller number of rules under any partition condition, mainly because its number of training instances is quite small. In brief, with the growth in the numbers of partitions and features, the runtime of the proposed BRBCS will increase, but this increase is constrained by the number of available training instances.

Conclusion

This paper extends the traditional FRBCS in belief functions framework and develops a belief rule-based classification system (BRBCS) to address imprecise or incomplete information in complex classification problems. The two components of the proposed BRBCS, i.e., the belief rule base (BRB) and the belief reasoning method (BRM),

Figure 1 : 2 .

 12 Figure 1: An example of the fuzzy partition of a two-dimensional pattern space by simple fuzzy grids

( 8 )

 8 In Dempster's rule, the total conflicting belief mass ∑ B∩C=∅ m 1 (B)m 2 (C) is redistributed back to all of the focal elements through normalization.

Figure 2 :

 2 Figure 2: Belief rule-based classification system

  Introduction of class noise. In this scheme, a class noise level of x% indicates that x% of the samples in the training set are mislabeled. The class labels of these samples are randomly changed to different ones within the domain of the class. • Introduction of feature noise. In this scheme, a feature noise level of x% indicates that x% of the feature values in the training set are erroneous. The corrupted feature is assigned a random value between the minimum and maximum of the domain of that feature, following a uniform distribution.

FRBCS • C = 5 3 C4. 5 • 5 •

 5355 for feature number M < 10, otherwise C = Confidence level c = 0.25; • Minimal instances per leaf i = 2; • Prune after the tree building BagC4.Replicate number T = 10; • Majority vote combination BRBCS • C = 5 for feature number M < 10, otherwise C = 3

Figure 4 :

 4 Figure 4: Classification accuracy rate (in %) of our proposed BRBCS in comparison with other methods at different feature noise levels. The symbol ′ △ ′ denotes the FRBCS, ′ • ′ denotes the C4.5, ′ * ′ denotes the BagC4.5, and ′ ′ denotes the BRBCS.

  are designed specifically by taking into account the possible pattern noise in many real-world data sets. The experiments show that the proposed BRBCS achieves better classification accuracy compared with other rule-based methods. Moreover, this method can effectively address the class or feature noise in the training data set. This allows us to conclude that the introduction of the belief rule structure improves the behavior of the rule-based classification system.

Table 1 :

 1 The belief, plausibility and pignistic probability with regard to each suspect

	Suspects	Bel	Pl	BetP
	Peter	0	0.4	0.19
	John	0.48	1	0.73
	Mary	0	0.2	0.09

Table 2 :

 2 Description of the benchmark data sets employed in the study

	Data set	# Instances	# Features	# Classes
	Banknote	1,372	4	2
	Breast	106	9	6
	Cancer a	683	9	2
	Diabetes a	393	8	2
	Ecoli	336	7	8
	Glass	214	9	6
	Haberman	306	3	2
	Iris	150	4	3
	Knowledge	403	5	4
	Letter	20,000	16	26
	Liver	345	6	2
	Magic	19,020	10	2
	Pageblocks	5,473	10	4
	Pima a	336	8	2
	Satimage	6,435	36	6
	Seeds	210	7	3
	Transfusion	748	4	2
	Vehicle	846	18	4
	Vertebral	310	6	3
	Yeast	1,484	8	10

a For the data sets containing missing values, instances with missing feature values are removed.

Table 3 :

 3 Settings of considered methods for classification accuracy evaluation

	Method

Table 4 :

 4 Classification accuracy rate (in %) of our proposed BRBCS in comparison with other rule-based methods for different numbers of partitions

	(over the training data)
				C = 3				C = 5				C = 7
		FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS
	Banknote	95.63(3) 96.27(2) 93.40(4) 96.54(1)	98.36(3) 99.27(2) 97.45(4) 99.64(1)	99.64(3) 99.73(2) 97.08(4) 99.82(1)
	Breast	70.59(4) 76.47(3) 80.00(2) 89.41(1)	71.76(4) 77.65(3) 89.41(2) 94.12(1)	63.53(4) 75.29(3) 81.18(2) 90.59(1)
	Cancer	93.24(4) 96.89(2) 95.98(3) 97.44(1)	96.53(3) 96.89(2) 95.06(4) 99.82(1)	93.78(3) 94.88(2) 93.59(4) 98.35(1)
	Diabetes	88.25(4) 91.11(2) 88.89(3) 92.06(1)	95.24(3) 93.65(4) 95.87(2) 96.83(1)	91.11(4) 95.56(3) 99.05(1) 97.46(2)
	Ecoli	89.22(4) 92.94(1) 89.59(3) 91.08(2)	94.42(2) 92.19(3) 89.96(4) 98.88(1)	92.94(2) 89.59(3) 88.10(4) 94.80(1)
	Glass	73.84(3) 73.26(4) 75.58(2) 83.14(1)	93.02(2) 87.21(3) 85.47(4) 94.77(1)	85.47(3) 86.05(2) 81.40(4) 90.12(1)
	Haberman 72.65(4) 76.73(1) 73.47(3) 75.51(2)	80.82(1) 74.29(3) 73.47(4) 78.78(2)	78.78(3) 80.00(2) 73.47(4) 81.22(1)
	Iris	95.00(2) 90.00(4) 95.83(1) 94.17(3)	93.33(4) 96.67(1) 95.83(2) 95.00(3)	95.83(4) 96.00(3) 99.17(1) 96.67(2)
	Knowledge 89.16(4) 90.40(2) 89.78(3) 91.64(1)	92.88(2) 92.26(3) 91.33(4) 94.74(1)	96.59(3) 97.21(2) 95.05(4) 99.07(1)
	Letter	93.75(3) 96.88(2) 93.06(4) 97.50(1)	92.19(4) 95.94(2) 92.81(3) 96.56(1)	91.19(3) 93.44(1) 89.32(4) 93.06(2)
	Liver	63.77(2) 58.70(4) 62.68(3) 67.03(1)	71.74(2) 67.75(4) 70.29(3) 76.81(1)	86.96(2) 77.17(4) 79.71(3) 88.04(1)
	Magic	82.81(3) 82.94(2) 82.28(4) 83.60(1)	82.81(2) 82.15(3) 81.49(4) 85.44(1)	81.49(4) 82.02(3) 82.68(2) 84.25(1)
	Pageblocks 91.35(4) 95.46(2) 93.17(3) 96.37(1)	92.72(4) 95.00(2) 93.63(3) 96.83(1)	89.29(4) 91.57(3) 93.40(2) 94.09(1)
	Pima	78.05(4) 79.67(3) 81.30(2) 86.18(1)	82.93(4) 91.71(2) 86.18(3) 94.15(1)	78.54(4) 81.14(3) 84.55(1) 82.76(2)
	Satimage	88.75(3) 87.98(4) 90.52(2) 92.64(1)	88.58(4) 91.30(3) 92.46(2) 93.24(1)	89.72(4) 91.28(2) 90.89(3) 91.86(1)
	Seeds	89.29(4) 89.88(3) 92.86(2) 94.05(1)	92.86(4) 94.05(3) 97.62(1) 97.02(2)	88.10(4) 90.48(3) 94.05(1) 93.45(2)
	Transfusion 77.13(3) 77.30(2) 75.57(4) 78.46(1)	76.96(2) 76.46(3) 73.46(4) 81.80(1)	79.13(3) 79.47(2) 74.79(4) 84.97(1)
	Vehicle	79.91(4) 81.24(3) 82.72(2) 84.49(1)	78.43(4) 79.03(3) 79.91(2) 80.85(1)	74.59(4) 77.55(2) 78.43(1) 75.04(3)
	Vertebral	74.60(4) 80.65(2) 76.61(3) 81.45(1)	82.26(3) 87.10(2) 79.44(4) 89.11(1)	82.66(2) 81.05(3) 79.71(4) 85.89(1)
	Yeast	55.56(3) 52.02(4) 59.85(2) 65.74(1)	58.92(4) 59.68(3) 60.69(2) 69.63(1)	58.08(3) 53.73(4) 66.67(1) 64.31(2)
	Av. Rank	3.45	2.60	2.75	1.20	3.05	2.70	3.05	1.20	3.30	2.60	2.70	1.40

Table 5 :

 5 Classification accuracy rate (in %) of our proposed BRBCS in comparison with other rule-based methods for different numbers of partitions

	(over the test data)
	C = 3		C = 5		C = 7
	FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS

Table 6 :

 6 Friedman test of the accuracy rate for the considered methods (α = 0.05)

	Partition number	Statistic F F	Critical value	Hypothesis
	C = 3	27.005	2.490	Rejected
	C = 5	21.000	2.490	Rejected
	C = 7	7.798	2.490	Rejected

Table 7 :

 7 Bonferroni-Dunn test of the accuracy rate for comparing BRBCS with other methods (α = 0.05)

	Partition number	Method	z value	p value	Critical value α/(k -1) a	Hypothesis
		FRBCS	5.88	4.13E-9	0.0167	Rejected
	C = 3	EFRBCS	3.55	3.83E-4	0.0167	Rejected
		EBRB	2.82	0.0048	0.0167	Rejected
		FRBCS	4.65	3.26E-6	0.0167	Rejected
	C = 5	EFRBCS	3.55	3.83E-4	0.0167	Rejected
		EBRB	5.02	5.13E-7	0.0167	Rejected
		FRBCS	3.55	3.83E-4	0.0167	Rejected
	C = 7	EFRBCS	2.57	0.0101	0.0167	Rejected
		EBRB	3.67	2.39E-4	0.0167	Rejected

a k is the number of considered methods.

Table 8 :

 8 Settings of considered methods for classification robustness evaluation

	Method

Table 9 :

 9 RLA (in %) of our proposed BRBCS in comparison with other robust methods at different class noise levels.

	NL = 10%	NL = 30%	NL = 50%

Table 10 :

 10 Friedman test of RLA for considered methods at different class noise levels (α = 0.05)

	Noise level	Statistic F F	Critical value	Hypothesis
	NL = 10%	6.3672	2.490	Rejected
	NL = 30%	8.7372	2.490	Rejected
	NL = 50%	30.096	2.490	Rejected

Table 11 :

 11 Bonferroni-Dunn test of RLA for comparing BRBCS with other methods at different class noise levels (α = 0.05)

	Noise level	Method	z value	p value	Critical value α/(k -1)	Hypothesis
		FRBCS	3.31	9.44E-4	0.0167	Rejected
	NL = 10%	C4.5	3.18	0.0015	0.0167	Rejected
		BagC4.5	1.35	0.1779	0.0167	Accepted
		FRBCS	3.92	8.88E-5	0.0167	Rejected
	NL = 30%	C4.5	3.55	3.83E-4	0.0167	Rejected
		BagC4.5	2.82	0.0048	0.0167	Rejected
		FRBCS	5.27	1.39E-7	0.0167	Rejected
	NL = 50%	C4.5	5.02	5.13E-7	0.0167	Rejected
		BagC4.5	2.45	0.0143	0.0167	Rejected

Table 12 :

 12 RLA (in %) of our proposed BRBCS in comparison with other robust methods at different feature noise levels.

	NL = 10%	NL = 30%	NL = 50%

Table 13 :

 13 Friedman test of RLA for considered methods at different feature noise levels (α = 0.05)

	Noise level	Statistic F F	Critical value	Hypothesis
	NL = 10%	3.8365	2.490	Rejected
	NL = 30%	7.4993	2.490	Rejected
	NL = 50%	11.303	2.490	Rejected

Table 14 :

 14 Bonferroni-Dunn test of RLA for comparing BRBCS with other methods at different feature noise levels (α = 0.05)

	Noise level	Method	z value	p value	Critical value α/(k -1)	Hypothesis
		FRBCS	2.45	0.0143	0.0167	Rejected
	NL = 10%	C4.5	2.94	0.0033	0.0167	Rejected
		BagC4.5	1.47	0.1416	0.0167	Accepted
		FRBCS	3.06	0.0022	0.0167	Rejected
	NL = 30%	C4.5	3.92	8.89E-5	0.0167	Rejected
		BagC4.5	2.33	0.0200	0.0167	Accepted
		FRBCS	3.80	1.47E-4	0.0167	Rejected
	NL = 50%	C4.5	4.29	1.81E-5	0.0167	Rejected
		BagC4.5	3.18	0.0015	0.0167	Rejected

Table 16

 16 shows the average runtime of the proposed BRBCS in the training and testing phases for different data sets and different partition numbers, where "# Tra." is the number of training instances in the data set, "# Fea." is the number of features, and "# Rule" is the number of generated rules. "T. Tra." and "T. Tes." are the average runtimes in the training phase and testing phase (classifying one pattern), respectively.

Table 16 :

 16 Average runtime (in s) of our proposed BRBCS for different data sets and different partition numbers

	C = 3	C = 5	C = 7

Acknowledgments

The authors would like to thank the anonymous reviewers for their careful reading and in-depth criticisms and suggestions. This work is partially supported by China Natural Science Foundation (Nos. 61135001, 61374159, 61403310) and the Doctorate Foundation of Northwestern Polytechnical University (No. CX201319).

Data sets

By the analysis of the results presented in Table 15, we can draw the following conclusions.

1. According to the measure # Rule, the proposed BRBCS and the other two fuzzy rule-based methods, FRBCS and EFRBCS, have higher interpretability than the EBRB method. As the same fuzzy partition approach of the feature space is used for the FRBCS, EFRBCS and BRBCS methods, the three methods generate the same number of rules. However, for the EBRB method, as each training pattern is used to generate a rule, the number of generated rules equals the number of training patterns.

2. According to the measure # Conditions, the four considered methods show the same interpretability. All of the four methods do not take into account the selection of features, and so all features are considered as conditions in the antecedent part of a rule.

3. According to the measure # Fired rule, the proposed BRBCS has higher interpretability than the EBRB method but a lower interpretability than the FRBCS method. This is because for the FRBCS method, the single winner rule is used to classify a query pattern, while for the proposed BRBCS method, all of the activated rules are combined to obtain the final result.

Considering the above three measures, the proposed BRBCS shows a slight decrease in interpretability compared with the classical FRBCS. As declared in [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF], accuracy and interpretability are always two contradictory