Validation BRB Belief Rule Base BRM Belief Reasoning Method BRBCS Belief Rule-Based Classification System DBRB Data-driven Belief Rule Base EkNN Evidential k-Nearest Neighbor EEkNN Evidential Editing k-Nearest Neighbor FRBCS Fuzzy Rule-Based Classification System GBT Generalized Bayes Theorem HBRB Hybrid Belief Rule Base HBRBCS Hybrid Belief Rule-Based Classification System kNN k-Nearest Neighbor KBRB Knowledge-driven Belief Rule Base LCP Least Commitment Principle PkNN Pairwise k-Nearest Neighbor RLA Relative Loss of Accuracy TBM Transferable Belief Model

Keywords: Data classification, Information fusion, Uncertainty management, Theory of belief functions, k-nearest neighbor rule, rule-based classification system vii

In many classification problems, data are inherently uncertain. The available training data might be imprecise, incomplete, even unreliable. Besides, partial expert knowledge characterizing the classification problem may also be available. These different types of uncertainty bring great challenges to classifier design. The theory of belief functions provides a well-founded and elegant framework to represent and combine a large variety of uncertain information. In this thesis, we use this theory to address the uncertain data classification problems based on two popular approaches, i.e., the k-nearest neighbor rule (kNN) and rule-based classification systems.

For the kNN rule, one concern is that the imprecise training data in class overlapping regions may greatly affect its performance. An evidential editing version of the kNN rule was developed based on the theory of belief functions in order to well model the imprecise information for those samples in overlapping regions. Another consideration is that, sometimes, only an incomplete training data set is available, in which case the ideal behaviors of the kNN rule degrade dramatically. Motivated by this problem, we designed an evidential fusion scheme for combining a group of pairwise kNN classifiers developed based on locally learned pairwise distance metrics.

For rule-based classification systems, in order to improving their performance in complex applications, we extended the traditional fuzzy rule-based classification system in the framework of belief functions and develop a belief rule-based classification system to address uncertain information in complex classification problems. Further, considering that in some applications, apart from training data collected by sensors, partial expert knowledge can also be available, a hybrid belief rule-based classification system was developed to make use of these two types of information jointly for classification.

Résumé

Dans de nombreux problèmes de classification, les données sont intrinsèquement incertaines. Les données d'apprentissage disponibles peuvent être imprécises, incomplètes, ou même peu fiables. En outre, des connaissances spécialisées partielles qui caractérisent le problème de classification peuvent également être disponibles. Ces différents types d'incertitude posent de grands défis pour la conception de classifieurs. La théorie des fonctions de croyance fournit un cadre rigoureux et élégant pour la représentation et la combinaison d'une grande variété d'informations incertaines. Dans cette thèse, nous utilisons cette théorie pour résoudre les problèmes de classification des données incertaines sur la base de deux approches courantes, à savoir, la méthode des k plus proches voisins (kNN) et la méthode à base de règles.

Pour la méthode kNN, une préoccupation est que les données d'apprentissage imprécises dans les régions où les classes de chevauchent peuvent affecter ses performances de manière importante. Une méthode d'édition a été développée dans le cadre de la théorie des fonctions de croyance pour modéliser l'information imprécise apportée par les échantillons dans les régions qui se chevauchent. Une autre considération est que, parfois, seul un ensemble de données d'apprentissage incomplet est disponible, auquel cas les performances de la méthode kNN se dégradent considérablement. Motivé par ce problème, nous avons développé une méthode de fusion efficace pour combiner un ensemble de classifieurs kNN couplés utilisant des métriques couplées apprises localement.

Pour la méthode à base de règles, afin d'améliorer sa performance dans les applications complexes, nous étendons la méthode traditionnelle dans le cadre des fonctions de croyance.

Nous développons un système de classification fondé sur des règles de croyance pour traiter des informations incertains dans les problèmes de classification complexes. En outre, dans certaines applications, en plus de données d'apprentissage, des connaissances expertes peuvent également être disponibles. Nous avons donc développé un système de classification hybride fondé sur des règles de croyance permettant d'utiliser ces deux types d'information pour la classification.

Mots-clés Classification, Fusion d'informations, Gestion de l'incertitude, Théorie des fonctions de croyance, k plus proches voisins, classification à base de règles ix constructive comments. I have also learned a great deal from his instructions for developing a rigorous way of research. I would also like to gratefully thank my supervisor at NPU, Prof. Quan Pan. I have been working with him since my Master program and he has led me into this interesting research field. He provided me with great support for my overseas study, as well as attending national and international conferences. When I encountered difficulties in work or in life, he always provided me great help and encouragement. His supervision is quit important and useful for me to finish this thesis successfully.

My thanks also go to the researchers at UTC and NPU, Sébastian Destercke, Yves Grandvalet, Philippe Xu, Yongmei Cheng, Yan Liang, Feng Yang and Zhunga Liu, with whom I had many insightful discussions about many aspects of research. I also wish to thank all the friends with whom I shared much wonderful time both in Xi'an and Compiène. activities. In many real-world applications, data contains inherent uncertainty [START_REF] Das | High-Level Data Fusion[END_REF][START_REF] Smets | Varieties of ignorance and the need for well-founded theories[END_REF]. For example, the data may be incomplete, which refers to cases where the value of a variable is missing. Sometimes, the data may be imprecise, when the value of a variable is given, but not with enough precision. In addition, the data may be unreliable, i.e., the obtained values might be wrong. The above types of uncertainty can be caused by a variety of factors, such as the random nature of the physical data generation and collection processes, measurement and decision errors, insufficient knowledge, etc. [START_REF] Montero | Modelling uncertainty (editorial)[END_REF]. These widely existed uncertainties present great challenges to classifier design.

As a research field closely related to real-world applications, in the past several decades, a wide variety of approaches have been proposed to cope with data classification problem.

Among them, the k-nearest neighbor rule, first developed by Fix and Hodges [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF], has become one of the most popular statistical classification techniques. As a non-parametric lazy learning algorithm, its classification process is quite simple and it does not depend on the underlying data distribution. Apart from the traditional statistical approaches, some computational intelligence-based classification approaches have also been developed

to mimic the human reasoning process. One of the most representative approaches is rulebased classification [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], which classifies a new instance based on a set of rules learnt from training samples or expert knowledge. The most useful characteristic of this approach is high interpretability due to the used linguistic model. In this thesis, our work mainly focuses on these two approaches, i.e., the k-nearest neighbor rule and rule-based classification system.

For the k-nearest neighbor (kNN) rule, it has been proved that its error rate approaches the optimal Bayes error rate asymptotically. However, in the finite sample case, its performance may greatly affected by the imperfect training data. One consideration is that the patterns from different classes overlap largely. Though the training samples in overlapping regions are assigned with precise labels, they actually cannot be seen as truly representatives of their corresponding clusters. Therefore, there is a need for well modeling the imprecise information for those samples in overlapping regions. Another consideration is that sometimes only an incomplete training data set is available. In these situations,

INTRODUCTION

the ideal performances of the kNN rule degrade dramatically. Therefore, obtaining good performances based on incomplete training data set is also a critical issue for classifier design.

For rule-based classification systems, the used linguistic model makes this approach interpretable to users. However, every coin has two sides. The rule-based classification systems may face lack of accuracy in some complex applications, due to the lack of flexibility of the linguistic model. Therefore, there is a real need for improving the performance of the rule-based classification systems in complex classification problems. In additions, in some real-world classification problems, apart from training data collected by sensors, partial expert knowledge provided by humans may also be available. These two types of information are usually independent but complementary. Thus, we need a hybrid classification model that can make use of these two types of uncertain information jointly.

The traditional classification approaches usually work within the probabilistic framework. However, probability theory only captures the randomness aspect of the data, but neither imprecision, nor incompleteness which are inherent in uncertain data. Therefore, many theories have been developed during the last decades to construct more powerful representations. In this thesis, we focus on the theory of belief functions, also known as Dempster-Shafer theory [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], to address the uncertain data classification problems. As a generalization of probability theory, it offers a well-founded and workable framework to represent and combine a large variety of uncertain information. We consider data classification from an information fusion point of view by combining the evidence constructed from uncertain training data or expert knowledge.

This thesis is structured in three parts:

Part I introduces the theoretical background that supports the thesis and provides a literature review for related work. Chapter 1 recalls fundamental aspects of belief functions.

We describe how information is represented and combined in the framework of belief functions. Some useful operations as well as decision rules are also presented. Chapter 2 presents general aspects of classification for uncertain data. After a discussion about the inherent properties of uncertain data, we formulate four critical issues concerning the uncertainty in data classification field, which are the main concerns of this thesis. Then, we provide a literature review for related work, emphasizing on nearest-neighbor-based and rule-based approaches.

Part II focuses on classification of uncertain data using nearest-neighbor-based approaches. Chapter 3 is oriented to performance enhancement of the kNN rule for cases in which patterns from different classes overlap strongly. In contrast, in Chapter 4, we are mainly concerned the classification problems based on incomplete training data sets, which is a key issue for nearest-neighbor-based approaches.

Part I

Theoretical background and literature review

The purpose of this fist part is to introduce the theoretical background and to provide a literature review for related work.

Chapter 1 is intended to provide a detailed introduction about the theory of belief functions, including some basic concepts and some useful operations.

Chapter 2 is designed to formulate the uncertain data classification problems considered in this thesis, and to introduce some existed work for classification of uncertain data using nearest-neighbor-based and rule-based approaches.

Chapter 1

Theory of belief functions

Uncertain data classification tasks require powerful tools to represent and combine different types of uncertain information. The theory of belief functions [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], also known as Dempster-Shafer theory or evidence theory, is a generalization of probability theory. It offers a well-founded and workable framework to represent and combine a large variety of uncertain information [START_REF] Xu | Information Fusion for Scene Understanding[END_REF]. It is also a generalization of possibility theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] and is closely linked to other theories including fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF], random sets [START_REF] Nguyen | An Introduction to Random Sets[END_REF] and imprecise probability [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF].

In this chapter, we first describe in Section 1.1 how different types of information can be represented in the framework of belief functions. In Section 1.2, we discuss the combination of mass functions and present some widely-used combination rules. Next, we describe in Section 1.3 some operations over the frame of discernment, such as conditioning, deconditioning and discounting. Then, in Section 1.4, we consider the issue of decision making using belief functions. Finally, Section 1.5 concludes this chapter.

Representation of evidence

The prerequisite of reasoning in the framework of belief functions is the representation of the available information, which is usually called evidence. This is done based on some basic functions used to represent our knowledge about the considered problem. At a glance, there are three main functions: mass, belief and plausibility functions. The mass function is the most basic and intuitive way of expressing someone's degrees of belief. The belief and plausibility functions are often used to compute intervals in order to bound the uncertainty.

We will see their usefulness and their expressive power in the following sections.

Mass function

In the theory of belief functions, a problem domain is represented by a finite set Ω = {ω 1 , ω 2 , • • • , ω n } of mutually exclusive and exhaustive hypotheses called the frame of discernment. Given a piece of evidence held by an agent, the state of belief about the CHAPTER 1. THEORY OF BELIEF FUNCTIONS truth of the problem is represented by a mass function or basic belief assignment (BBA) defined as follows [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. Each number m(A) represents the part of belief assigned to the hypothesis that the truth ω lies in the subset A (i.e., the hypothesis ω ∈ A). It is important to understand that the hypothesis ω ∈ A does not support the membership of ω to any subset B A. The belief assigned to Ω, or m(Ω), is referred to as the degree of ignorance. Definition 1.1 imposes that the empty set cannot be a focal set. For the open-world assumption [START_REF] Smets | The transferable belief model[END_REF], the quantity m(∅) is interpreted as the degree of support of the hypothesis that the truth ω is actually outside of the frame Ω. In this thesis, the closed-world assumption is used, i.e., the frame of discernment is considered exhaustive.

To interpret how the formalism of mass function can be used to represent a piece of evidence, we provide the following murder example [START_REF] Denoeux | Introduction to Belief Functions[END_REF] for illustration. ). This can be interpreted as being certain that the truth lies in A.

• Bayesian, if all of its focal sets are singletons (i.e., sets with cardinality equal to one).

In this case, the mass function reduces to the precise probability distribution.

• dogmatic, if Ω is not a focal set. In this case, there is no ignorance about the state of belief for the truth of the problem.

• vacuous, if Ω is the only focal set (denoted as m Ω ). This situation corresponds to complete ignorance as the closed-world assumption implies that hypothesis ω ∈ Ω is always true.

• simple, if it has at most two focal sets and one of them is Ω if it has two. It is denoted by A w , A being the focal set different from Ω and 1w the confidence that the truth lies in A. The vacuous mass function can thus be noted as A 1 for any A ⊂ Ω, and a categorical mass function can be noted as A 0 for some A = Ω.

In Table 1.1, we show some examples of these special mass functions and the types of information that are encoded.

m({ω 1 , ω 2 }) = 1 Certain information Bayesian m({ω 1 }) = m({ω 2 }) = m({ω 3 }) = 1/3 Precise information Dogmatic m({ω 1 }) = 1/2, m({ω 2 , ω 3 }) = 1/2 Information without ignorance Vacuous m(Ω) = 1 Complete ignorance Simple m({ω 1 }) = 1/2, m(Ω) = 1/2
Unique hypothesis with partial confidence

Belief and plausibility functions

In addition to mass function, there are two other important functions to represent evidence:

the belief function Bel and the plausibility function P l [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF].

Definition 1.2 (belief and plausibility functions). The belief and plausibility functions, over a frame of discernment Ω, are defined, respectively, as

Bel(A) = B⊆A m(B), ∀A ⊆ Ω. (1.2) P l(A) = B∩A =∅ m(B), ∀A ⊆ Ω. (1.
3)

The degree of belief Bel(A) quantifies the amount of justified specific support to be given to A. It can be interpreted as the degree of belief that the truth lies in A. Note that this definition is close to that of a mass function. The difference lies in the fact that the degree of belief Bel(A) can be further divided between some subsets of A. The degree of plausibility P l(A) quantifies the maximum amount of potential specific support that could be given to A. It can be interpreted as the belief that fails to doubt A. The interval [Bel(A), P l(A)] can be seen as the lower and upper bounds of support to A.

Properties

1. Bel(A) ≤ P l(A), ∀A ⊆ Ω;
2. Bel and P l are related by:

Bel(A) = 1 -P l(A), ∀A ⊆ Ω, (1.4)
P l(A) = 1 -Bel(A), ∀A ⊆ Ω; (1.5)
3. A mass function m can be expressed in terms of Bel and P l in the following way:

m(A) = B⊆A (-1) |A|-|B| Bel(B), ∀A ⊆ Ω, (1.6)
m(A) = B⊆A (-1) |A|-|B|+1 P l(B), ∀A ⊆ Ω. (1.7)
From the definitions and properties of the belief and plausibility functions, we can see that there exists a one-to-one correspondence between mass, belief and plausibility functions as shown in Figure 1.1. To provide a graphical explanation of belief and plausibility functions and their relation to the mass function, we consider the following example.

m Bel Pl E q . ( 1 . 2 ) E q . ( 1 .
3 )

Eq.(1.5)

Eq.(1.4)

E q . ( 1 . 6 ) E q . ( 1 . 7 )
B i , i = 1, 2, 3, 4, 5.
Then, the degree of belief in A is

Bel(A) = m(B 1 ) + m(B 2 ),
whereas the plausibility of A is

P l(A) = m(B 1 ) + m(B 2 ) + m(B 3 ) + m(B 4 ).
The degree of belief in the complement of A is

Bel(A) = m(B 5 ),
which is clearly equal to 1 -P l(A). The plausibility in the complement of A is

P l(A) = m(B 3 ) + m(B 4 ) + m(B 5 ), which is clearly equal to 1 -Bel(A). ◇ B 1 B 2 B 3 B 4 B 5 A

Distance between mass functions

With two sources of evidence S 1 and S 2 characterizing the same considered problem, sometimes we need to know the dissimilarity between them. It can be characterized by the distance between their corresponding mass functions. Since the introduction of Dempster's conflict measure [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF], many distance measures between mass functions have been defined in the literature [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.

d J (m 1 , m 2 ) = 1 2 ( - → m 1 -- → m 2 ) T D( - → m 1 -- → m 2 ), (1.8)
where -→ m 1 and -→ m 2 are column vectors composed of the mass for all of the 2 n subsets of Ω, and D is a 2 n × 2 n matrix with elements given by D

i,j = |A i ∩ B j | |A i ∪ B j | , A i , B j ∈ 2 Ω . The factor 1/2 is used to normalize d J so that 0 ≤ d J (m 1 , m 2 ) ≤ 1.
From the above definition, another way to write d J is:

d J (m 1 , m 2 ) = 1 2 ( - → m 1 2 + - → m 2 2 ) -- → m 1 , - → m 2 , (1.9)
where -→ m 2 is the square norm of -→ m, and -→ m 1 , -→ m 2 is the scalar product defined by

- → m 1 , - → m 2 = 2 n i=1 2 n j=1 m 1 (A i )m 2 (B j ) |A i ∩ B j | |A i ∪ B j | , with A i , B j ∈ 2 Ω for i, j = 1, 2, • • • , 2 n .

Combination of evidence

In the preceding section, we have presented some functions that allow us to represent the available pieces of evidence. The next step of the reasoning process is to combine these information to obtain a single mass function. In this section, we will introduce some popular combination rules that allow us to aggregate knowledge held by several pieces of evidence into a single one. The differences between these combination rules mainly depend on two issues: the reliability of the sources of information and the degree of dependence between them.

Dempster's rule

Given two mass functions m 1 and m 2 induced from two sources of information, a combination rule yields a new mass function that represents our new state of knowledge after taking into consideration both sources of information. Dempster's rule is the most popular alternative to combine several distinct bodies of evidence [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF].

Definition 1.4 (Dempster's rule). Let m 1 and m 2 be two cognitively independent mass functions defined over the same frame of discernment Ω. One can combine them using Dempster's rule to compute a new mass function defined by

(m 1 ⊕ m 2 )(A) =      0, for A = ∅ 1 1 -κ B∩C=A m 1 (B)m 2 (C), for A ⊆ Ω, A = ∅, (1.10
)

with κ = B∩C=∅ m 1 (B)m 2 (C). (1.11)
The quantity κ measures the conflict between the two mass functions m 1 and m 2 . The combination rule is valid only if κ < 1, otherwise, m 1 and m 2 are inconsistent and cannot be combined.

Properties

1. Commutativity: m 1 ⊕ m 2 = m 2 ⊕ m 1 ; 2. Associativity: (m 1 ⊕ m 2 ) ⊕ m 3 = m 1 ⊕ (m 2 ⊕ m 3 );
3. It has the vacuous mass function m Ω as the unique neutral element:

m ⊕ m Ω = m Ω ⊕ m = m;
Next, let us come back to the murder example studied in Example 1.1 and illustrate how Dempster's rule works to combine distinct bodies of evidence.

Exemple 1.3 (murder continued). Remember that the first item of evidence gave us the following mass function:

m 1 ({P eter, John}) = 0.8, m 1 (Ω) = 0.2,
concerning the murderer over the frame Ω = {P eter, John, M ary}. Let us now assume that we have a new piece of evidence: a blond hair has been found. This new evidence supports the hypothesis that the murderer is either John or Mary, as they are blond while Peter is not. However, this piece of evidence is reliable only if the room has been cleaned before the crime. If we judge that there is 60% chance that it was the case, then our second piece of evidence is modeled by the following mass function:

m 2 ({John, M ary}) = 0.6, m 2 (Ω) = 0.4.
With the above two distinct pieces of evidence, Dempster's rule can be used to combine them into an integrated mass function as m({John}) = 0.48, m({P eter, John}) = 0.32, m({John, M ary}) = 0.12, m(Ω) = 0.08.

From the above combination results, we can see that each focal set of m is obtained by

intersecting one focal set of m 1 and one focal set of m 2 . Consequently, the integrated mass function m is more focussed than both m 1 and m 2 . Therefore, after combination, we can obtain a more precise answer about the considered problem.

Cautious rule

A strong assumption of Dempster's rule is that the pieces of evidence to be combined are independent. However, this is not always verified in practice. In cases where this independence assumption is not reasonable, Denoeux [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] proposed to use the cautious rule. Before defining the cautious rule, let us first show the canonical decomposition of a mass function.

Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] defined a separable mass function as the result of the ⊕ combination of simple mass functions. If this separable mass function m is non-dogmatic, it can be uniquely represented by

m = ∅ =A⊂Ω A w(A) , (1.12)
with w(A) ∈ [0, 1] for all A ⊂ Ω, A = ∅. This representation is called the canonical decomposition of m. The weights w(A) can be obtained from the commonalities as follows:

w(A) = B⊇A q(B) (-1) |B|-|A|+1 , ∀A ⊂ Ω, (1.13)
where the commonalities q(B) = C⊇B m(C), ∀B ⊆ Ω. The above general formula for calculating weights w(A) seems complicated. In [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF], Denoeux provided a simple analytical formula for the weight function associated to the following special mass function. Let

A 1 , A 2 , • • • , A n be n subsets of Ω such that A i ∩ A j = ∅, for all i, j ∈ {1, 2, • • • , n}
w(A) =    m(Ω) m(A k ) + m(Ω) , if A = A k 1, otherwise.
(1.14) Definition 1.5 (cautious rule). Let m 1 and m 2 be two non-dogmatic mass functions defined over the same frame of discernment Ω, and w 1 and w 2 the associated weight functions from their respective canonical decompositions. Their combination using the cautious rule is defined as

m 1 m 2 = ∅ =A⊂Ω A w 1 (A)∧w 2 (A) , (1.15)
where ∧ denotes the minimum operator.

Compared to Dempster's rule, besides the commutativity and associativity, the cautious rule is also idempotent (i.e., m m = m), which is a natural requirement for a rule allowing the combination of dependent pieces of evidence.

Triangular norm-based rules

It is possible to formulate both Dempster's rule and the cautious rule with a triangular norm-based combination rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF]. The combination of two non-dogmatic mass functions m 1 and m 2 with Dempster's rule can be written as an expression similar to Eq. (1.15):

m 1 ⊕ m 2 = ∅ =A⊂Ω A w 1 (A)w 2 (A) . (1.16)
With Dempster's rule, the weights w 1 (A) and w 2 (A) are multiplied, whereas with the cautious rule, the minimum operator is used. Frank's parameterized family of t-norms [START_REF] Klement | Triangular Norms[END_REF] generalizing these two operators is defined as

a⊤ s b =          a ∧ b, if s = 0 ab, if s = 1 log s 1 + (s a -1)(s b -1) s -1 , otherwise, (1.17
m 1 ⊛ s m 2 = ∅ =A⊂Ω A w 1 (A)⊤sw 2 (A) , (1.18)
where ⊤ s is Frank's parameterized family of t-norms with s ∈ [0, 1].

Obviously, when s = 0, the triangular norm-based rule corresponds to the cautious rule (i.e., ⊛ 0 = ), and when s = 1, it corresponds to Dempster's rule (i.e., ⊛ 1 = ⊕). All these rules inherit important properties from t-norms: they are commutative and associative, and they admit the vacuous mass function as neutral element.

Other alternative combination rules

For the above reviewed combination rules, the sources of evidence to be combined are assumed to be reliable. We could, however, make different assumptions about the reliability of the two sources. For instance, we could assume that at least one of them is reliable.

This assumption results in the following binary operation, called the disjunctive rule of combination [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF]:

(m 1 ∪ m 2 )(A) = B∪C=A m 1 (B)m 2 (C), for A ⊆ Ω. (1.19)
This operation is clearly commutative and associative, and it does not have a neutral element. Combining mass functions disjunctively can be seen as a conservative strategy, as the disjunctive rule relies on a weaker assumption about the reliability of the sources, as compared to Dempster's rule. However, mass functions become less and less focussed as more pieces of evidence are combined using the disjunctive rule. In general, the disjunctive rule may be preferred in case of heavy conflict between the different pieces of evidence.

CHAPTER 1. THEORY OF BELIEF FUNCTIONS

An alternative rule, which is somehow intermediate between the disjunctive rule and Dempster's rule, has been proposed by Dubois and Prade [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF]. It is defined as:

(m 1 ⋆m 2 )(A) =      0, for A = ∅ B∩C=A m 1 (B)m 2 (C) + B∩C=∅,B∪C=A m 1 (B)m 2 (C), for A ⊆ Ω, A = ∅.
(1.20)

This rule boils down to Dempster's rule and disjunctive rule when, respectively, the degree of conflict equals to zero and one. In other cases, it has some intermediate behavior.

Many other alternatives to Dempster's rule can be found in the literature [START_REF] Jøsang | The consensus operator for combining beliefs[END_REF][START_REF] Lefevre | Belief functions combination and conflict management[END_REF][START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF][START_REF] Smets | The combination of evidence in the transferable belief model[END_REF][START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF], which were mainly proposed to address the issue of combining conflicting information.

These alternative rules allow the combination of contradictory information but prevent the representation of certain types of information. In particular, categorical, Bayesian and dogmatic mass functions can often not be properly handled by these alternative combination rules. The use of these alternative rules thus limits the power of belief functions to represent a large variety of information. In this thesis, we adopt the same point of view as Haenni [START_REF] Haenni | Are alternatives to Dempster's rule of combination real alternatives[END_REF] who agreed that the so-called counter-intuitive results that may be obtained from Dempster's rule are often due to erroneous modeling of the pieces of evidence to be combined. Efforts should thus be put on properly representing the information at hand rather than on modifying the combination rule. For instance, in combining unreliable sources of evidence, one can first discount those original pieces of evidence using Shafer's discounting operation [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] (to be introduced in next section) with refined modeling of the reliability. In such a way, the conflict between different pieces of evidence can be greatly reduced and Dempster's rule can be selected as a preferred combination rule.

Operations over the frame of discernment

In order to manipulate the belief functions more effectively, the conditioning and deconditioning operations are introduced to the framework of belief functions. In addition, we also give an introduction for the discounting operation, which makes it possible to handle partially reliable sources of information.

Conditioning operation

In Bayesian probability theory, conditioning is the fundamental mechanism for updating a probability measure P with new evidence of the form ω ∈ B for some B ⊆ Ω such that P (B) = 0. The conditional probability measure is defined as

P (A | B) = P (A ∩ B) P (B) , ∀A ⊆ Ω.
(1.21)

OPERATIONS OVER THE FRAME OF DISCERNMENT

In a similar way, a conditioning operation can also be defined for mass functions in the framework of belief function [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF].

Definition 1.7 (conditioning operation). Let m Ω be a mass function defined over the frame of discernment Ω. The conditioning of m Ω with respect to B ⊆ Ω is defined as

m Ω [B] = m Ω ⊕ m Ω B , (1.22)
where m Ω B is the categorical mass function with unique focal set B.

From the above definition, we can see that the conditioning operation for mass functions is just a special case of Dempster's rule, in which an arbitrary mass function m Ω is combined with a categorical mass function m Ω B .

Deconditioning operation

In this section, we focus on the inverse question studied in the preceding section. Assume that a source of evidence gives us a mass function representing evidence about some problem defined over the frame Ω, assuming that some proposition B ⊆ Ω holds. This with respect to B is defined as

m Ω (A) = m Ω [B](C), if A = C ∪ B for some C ⊆ Ω 0, otherwise, (1.23)
where B denotes the complement of set B with respect to set Ω.

Note that the above deconditioning operation usually cannot recover the original unconditioned mass function. It only gives the least committed mass function according to the Least Commitment Principle (LCP) [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF], which indicates that, given several mass functions compatible with a set of constraints, the most appropriate is the least informative.

In the following, we provide an example to show how the operations of conditioning and deconditioning work to manipulate mass functions.

Exemple 1.4. We consider the following mass function m defined over the frame Ω = {ω 1 , ω 2 , ω 3 }:

m({ω 1 }) = 0.4, m({ω 2 }) = 0.3, m({ω 3 }) = 0.2, m(Ω) = 0.1.
Suppose we know that the truth ω lies in B = {ω 1 , ω 2 }. With this hypothesis, the above mass function can be updated using the conditioning operation (1.22) with respect to B as:

m[B]({ω 1 }) = 0.5, m[B]({ω 2 }) = 3/8, m[B](B) = 1/8.
Then, with the above conditioned mass function m[B], we intend to recover the original mass function using the deconditioning operation (1.23) with respect to B as:

m ′ ({ω 1 , ω 3 }) = 0.5, m ′ ({ω 2 , ω 3 }) = 3/8, m ′ (Ω) = 1/8.
We can see that the recovered mass function m ′ is different from the original mass function m. Therefore, the conditioning and deconditioning operations are not strictly mutually reversible. In addition, the recovered mass function m ′ becomes less informative than the original mass function m, which indicates that some information is lost in these operations.

Discounting operation

Let us assume that we receive a piece of evidence from a source S, describing some information about the truth ω over the frame of discernment Ω. However, this information is not fully reliable or not fully relevant because, e.g., it is provided by a possible faulty sensor, the measurement was performed in unfavorable experimental condition, or the information is related to a situation that only has some similarity with the situation considered. By considering the information about the reliability of the source, we get a new, less informative mass function. This operation is called discounting [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF].

Definition 1.9 (discounting operation). Given a mass function m defined over the frame of discernment Ω and a coefficient α ∈ [0, 1], the discounting of m with discount rate 1α yields a new mass function α m defined by:

α m(A) = αm(A), for A = Ω αm(Ω) + (1 -α), for A = Ω. ( 1

Decision making

In the preceding sections, we have presented some functions and operations that allow us to represent the available uncertain sources of information and to reason with them. The final step is to make a decision about the considered problem based on the reasoning results. In this section, we introduce some decision rules in the framework of belief functions.

Maximum belief/plausibility rule

Let

Ω = {ω 1 , ω 2 , • • • , ω n } be the frame of discernment, A = {a 1 , a 2 , • • • , a n } the set of
acts, where a i is the act of selecting ω i . Define a loss function L:

A × Ω → R such that L(a i , ω j ) = 0, if i = j, 1, otherwise.
Define the risk of each act a i as the expected loss if a i is selected:

R P (a i ) = E P [L(a i , •)] = ω∈Ω L(a i , ω)P ({ω}), ∀a i ∈ A,
where P is a probability measure defined on Ω. With the above notions, the decision making problem is formalized to select an act with minimal risk.

In the framework of belief functions, the uncertainty on Ω is described by an interval [Bel(A), P l(A)], ∀A ⊆ Ω, and the lower and upper expected risk of each act a i can be defined, respectively, as [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF][START_REF] Smets | The degree of belief in a fuzzy event[END_REF]:

R(a i ) = E[L(a i , •)] = A⊆Ω m(A) min ω∈A L(a i , ω) = 1 -P l({ω i }), ∀a i ∈ A, R(a i ) = E[L(a i , •)] = A⊆Ω m(A) max ω∈A L(a i , ω) = 1 -Bel({ω i }), ∀a i ∈ A.
Minimizing the lower risk R and the upper risk R result in two decision rules: the maximum plausibility rule (optimistic strategy) and the maximum belief rule (pessimistic strategy), respectively.

In practice, the maximum plausibility rule is more widely used because it is computationally efficient [START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF]: suppose m = m 1 ⊕ m 2 , then

P l({ω i }) ∝ P l 1 ({ω i })P l 2 ({ω i }), ∀ω i ∈ Ω. (1.25)
That is, when combining several mass functions, we do not need to compute the combined mass function using Dempster's rule. Instead, we can compute the combined plausibility using Eq. (1.25) to make the decision according to the maximum plausibility rule.

Maximum pignistic probability rule

In the preceding section, a pessimistic strategy and an optimistic one were derived by minimizing the upper and lower expected risk, respectively. In this section, we introduce another decision rule that finds a compromise between the pessimistic and the optimistic strategies. It is based on the Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF], which postulates that uncertain reasoning and decision making are two fundamentally different operations occurring at two different levels: uncertain reasoning is performed at the credal level using the formalism of belief functions, while decision making is performed at the pignistic level, after the mass function has been transformed into a probability measure. This transformation is called the pignistic transformation.

Definition 1.10 (pignistic transformation). Given a mass function m defined over the frame of discernment Ω, the pignistic transformation from the mass function m to a probability measure BetP is defined by:

BetP (A) = B⊆Ω |A ∩ B| |B| m(B), ∀A ⊆ Ω, (1.26)
where |X| denotes the cardinality of set X.

The pignistic probability BetP (A) (from the Latin word pignus, meaning a bet) approximates the unknown probability in [Bel(A), P l(A)]:

Bel(A) ≤ BetP (A) ≤ P l(A), ∀A ⊆ Ω.
Accordingly, the expected risk based on the pignistic probability is

R BetP (a i ) = E BetP [L(a i , •)] = ω∈Ω L(a i , ω)BetP ({ω}) = 1 -BetP ({ω i }), ∀a i ∈ A.
Consequently, the expected risk based on the pignistic probability lies in the interval of the lower and upper expected risk:

R(a i ) ≤ R BetP (a i ) ≤ R(a i ), ∀a i ∈ A.
Minimizing

Conclusion

As a generalization of probability theory, the theory of belief functions can be used to model and reason with many types of uncertain information. This chapter provided a detailed introduction for the theory of belief functions. Several basic functions that are commonly used to represent uncertain information have been described. Some combination rules and several other operations (i.e., conditioning, deconditioning and discounting) over the frame of discernment have been introduced. Finally, some decision rules concerning the uncertainty quantified by belief functions have been presented. This theory will be used in the following chapters to model different types of uncertain information encountered in data classification problems.

Chapter 2

Classification of uncertain data

Automatic classification of data is an important problem in a variety of engineering and scientific disciplines such as biology, psychology, medicine, marketing, computer vision, military affairs, etc. [START_REF] Jain | Statistical pattern recognition: A review[END_REF]. In the past several decades, a wide variety of approaches have been developed towards this task. For traditional classification algorithms, the available data are often assumed to be exact or perfect. In many emerging applications, however, the data are inherently uncertain, which brings new challenges to classifier design [START_REF] Aggarwal | A survey of uncertain data algorithms and applications[END_REF][START_REF] Liu | Credal classification of uncertain data based on belief function theory[END_REF][START_REF] Qin | A rule-based classification algorithm for uncertain data[END_REF][START_REF] Ren | Naive Bayes classification of uncertain data[END_REF][START_REF] Tsang | Decision trees for uncertain data[END_REF].

In this chapter, we first describe in Section 2.1 the definition of classification and some popular classification methods. In Section 2.2, we discuss the uncertainty in data classification field. Then, we give brief reviews about classification of uncertain data with nearest-neighbor-based approaches in Section 2.3 and rule-based approaches in Section 2.4, respectively. Finally, Section 2.5 concludes this chapter.

Data classification problem

Before addressing the more advanced issues in data classification field, we first define what we mean by classification, and then introduce some popular classification methods.

What is classification?

The classification task occurs in a wide range of human activities. In its wider sense, the term could cover any context in which some decision or forecast is made on the basis of currently available information, and a classification procedure is then some formal method for repeatedly making such judgments in new situations [START_REF] Michie | Machine Learning, Neural and Statistical Classification[END_REF]. In this thesis we consider a more restricted interpretation. We assume that the problem concerns the construction of a procedure that will be applied to a continuing sequence of cases, in which each new case must be assigned to one of a set of pre-defined classes on the basis of observed features. The construction of a classification procedure from a set of labeled samples has also been termed supervised learning (in order to distinguish it from unsupervised learning or clustering in which the classes are inferred from the data).

Generally, the classification problem considered in this thesis can be formulated as follows.

• Given a set of M pre-defined classes:

Ω = {ω 1 , • • • , ω M }, and
a set of N labeled training samples: T = {(x 1 , ω (1) ), • • • , (x N , ω (N ) )}, with each sample described by a feature vector x ∈ R P and a class label ω ∈ Ω,

• the classification problem is to assign a new instance y ∈ R P to one of the pre-defined classes in Ω based on the available training set T .

Overview of some of the more common classification methods

As a research field closely related to real-world applications, the study of data classification has developed significantly in the past several decades, and a wide variety of approaches have been taken towards this task. According to the used theoretical tools, three main historical strands of research can be identified: statistical approaches, logic-based approaches and perceptron-based approaches [START_REF] Kotsiantis | Machine learning: A review of classification and combining techniques[END_REF]. possible. New patterns are then mapped into that same space and predicted to belong to a class based on which side of the gap they fall on. The SVM approach has a sound theoretical foundation, performs well with small datasets, and is insensitive to the number of dimensions.

2

Logic-based approaches

Logic-based approaches aim to mimic the human reasoning process, and to generate classification expressions simple enough to be easily understood [START_REF] Michie | Machine Learning, Neural and Statistical Classification[END_REF]. Under this category of classification approaches, one can find decision trees and rule-based classification systems.

Decision trees [START_REF] Quinlan | Induction of decision trees[END_REF] A decision tree is a flowchart-like structure in which each internal node represents a test on an feature (e.g., whether a coin flip comes up head or tail), each branch represents the outcome of the test, and each leaf node represents a class label (decision taken after computing all features). The paths from root to leaf represent classification rules. First, the training samples are used to build a decision tree, and then new patterns are classified starting at the root node and sorted based on their feature values. One of the most useful characteristics of decision trees is their comprehensibility.

People can easily understand why a decision tree classifies a pattern as belonging to a specific class.

Rule-based classification systems [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF] Decision trees can be translated into a set of rules by creating a separate rule for each path from the root to a leaf in the tree.

However, rules can also be directly induced from training data using a variety of rule generation algorithms. Generally, a rule-based classification system (RBCS) works in two stages, i.e., to learn a rule base that establishes an association between the feature space and the class space based on the training data, and to classify a query pattern based on the learned rule base with a reasoning method. The RBCS is widely employed in real-world applications 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.

Perceptron-based approaches

In the data classification field, some well-known algorithms are based on the notion of perceptron [START_REF] Rosenblatt | The perceptron: a probabilistic model for information storage and organization in the brain[END_REF]. According to the number of perceptron layers used in modeling, these approaches can be further divided as single-layer perceptrons and multi-layer perceptrons.

Single-layer perceptrons [START_REF] Gallant | Perceptron-based learning algorithms[END_REF] A perceptron is an algorithm for supervised classification of an input into one of several possible non-binary outputs. It is a type of linear classifier, i.e., a classification algorithm that makes its predictions based on a linear predictor function combining a set of weights with the feature vector. The single-layer perceptrons (SLP) algorithm for learning from a batch of training samples iterates until it finds a prediction vector that is correct on all of the training samples. This prediction rule is then used for predicting the labels on the query patterns. The SLP can have lower time complexity when dealing with irrelevant features. However, as a linear classifier, the SLP can only classify linearly separable sets of patterns.

Multi-layer perceptrons [89]

A Multi-layer perceptrons (MLP) model has been proposed to solve the nonlinearly separable problem. A MLP consists of large number of units (neurons) joined together in a pattern of network. First, the network is trained on a set of training data to determine input-output mapping. The weights of the connections between neurons are then fixed, and the network is used to determine the class labels of new patterns. MLP has been applied to many real-world problems. However, it is a black-box method: its conclusion cannot be easily interpreted.

Data classification under uncertainty

In many applications, data contains inherent uncertainty. A number of factors contribute to the uncertainty, such as the random nature of the physical data generation and collection processes, measurement and decision errors, insufficient knowledge, etc. [START_REF] Montero | Modelling uncertainty (editorial)[END_REF]. In this section, we first provide a brief survey for different categories of uncertainty emerging in realworld applications, and then talk about some issues concerning the uncertainty in data classification field, which are the targets of this thesis.

Types of uncertainty

Uncertainty can be generally characterized as lack of information. Different types of information may be lacking in data and knowledge bases, and consequently give rise to different kinds of uncertainty. As discussed in [START_REF] Das | High-Level Data Fusion[END_REF][START_REF] Smets | Varieties of ignorance and the need for well-founded theories[END_REF], uncertainty can broadly be divided into the following three categories:

• Incompleteness: Incomplete information refers to cases where the states of a variable or an event are missing. Consider a database of battlefield reports that should include information about detected unit position (latitude and longitude), category (friendly, neutral, or hostile), and type (tank, armored personnel carrier, or Humvee) for each report. The incomplete information can arise in the following two levels. First, if, for example, the state of the variable representing the type of a detected hostile unit at a specific position is missing from a report, then the information in the report becomes incomplete. Second, if, for example, some reports representing the state of battlefield in one period of time are missing from the database, then the information in the database also becomes incomplete.

• Imprecision: Imprecise information refers to cases where the value of a variable is given, but not with enough precision. Suppose the value of the variable representing the type of a detected hostile unit at a certain location is "tank" or "Humvee". The information is complete because the values of each of the three variables representing the unit's position, category, and type are given, but the information is imprecise because there is some ambiguity as to the exact type of the detected unit.

• Unreliability: Unreliable information refers to cases where the information is complete, precise, but uncertain since it might be wrong. This type of uncertainty appears when the observer (human or sensor) is taken into account. It is the observer that is not reliable about the available information.

The above descriptions broadly categorize different types of uncertainty according to the types of information lacking in data and knowledge bases. This partition is not unique and each type of uncertainty can be further subdivided into several subtypes. One can refer to Chapter 3 of [START_REF] Das | High-Level Data Fusion[END_REF] for more information.

Uncertainty in data classification

Different types of uncertainty described in the preceding section exist widely in data classification problems. In this thesis, we confine to the following four critical issues concerning the uncertainty in data classification field. provided by human may be available. These two types of information are usually independent but complementary for classification.

As reviewed in Chapter 1, the theory of belief functions is an effective tool to model and reason with uncertain information. The use of belief function theory in pattern classification fields is not new, and some classifiers have already been developed based on belief functions in the past. For instance, Smets [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF] and Appriou [START_REF] Appriou | Uncertain data aggregation in classification and tracking processes[END_REF] have proposed model-based classifiers based on the generalized Bayes theorem (GBT) [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF] which is an extension of Bayes theorem in transferable belief model (TBM) [START_REF] Smets | The transferable belief model[END_REF]. There are some other case-based evidential classifiers based on k-nearest neighbors [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[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][START_REF] Zouhal | An evidence-theoretic k-NN rule with parameter optimization[END_REF], support vector machines [START_REF] Laanaya | Support vector regression of membership functions and belief functions -application for pattern recognition[END_REF],

decision trees [START_REF] Vannoorenbergue | Handling uncertain labels in multiclass problems using belief decision trees[END_REF], and neural network [START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF]. In essence, these methods are devoted to addressing different types of uncertainty based on different classification models.

In this thesis, we aim to solve the above listed four uncertain data classification problems in the framework of belief functions. As pointed out in the title, our work mainly focuses on two popular classification approaches: nearest-neighbor-based classification and rulebased classification. Specifically, we study the first two issues in nearest-neighbor-based classification, and the last two issues in rule-based classification. We will give a review of related work in the following two sections.

Nearest-neighbor-based classification

In classification problems, complete statistical knowledge regarding the conditional density of each class is rarely available, which precludes applications of the optimal Bayes classification procedure. In these cases, a good solution is to classify each new pattern using the evidence of nearby sample observations. One such non-parametric procedure has been introduced by Fix and Hodges [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF], and has since become well-known in the pattern recognition field as the k-nearest neighbor (kNN) rule. It is one of those algorithms that are very simple to understand but work quite well in practice. In this section, we first describe the main principle of the kNN rule, and then emphasize on two issues that affect the performance of the kNN rule.

k-nearest neighbor rule

The kNN rule is based on a simple method of density estimation. The idea is very similar to kernel density estimation [START_REF] Terrell | Variable kernel density estimation[END_REF]. Instead of using kernel functions, here the estimation is made in a simple way. For estimating the density at a point x, place a hypercube centered at x and keep increasing its size till k neighbors are captured. Then the estimate of the density at point x is given by

p(x) = k N V , (2.1)
where N is the number of total samples and V is the volume of the hypercube.

Having obtained an expression for a density estimate, we can now use this in a decision rule. Suppose that in the first k samples there are k m samples from class ω m (so that

M m=1 k m = k).
Let the total number of samples in class ω m be N m (so that

M m=1 N m = N ).
Then, the class-conditional density can be estimated as

p(x | ω m ) = k m N m V , (2.2)
and the prior probability as

p(ω m ) = N m N . (2.3)
Then the decision rule is to assign

x to ω m , if p(ω m | x) ≥ p(ω i | x), for all i = 1, 2, • • • , M, (2.4)
or, using Bayes' theorem,

k m N m V N m N ≥ k i N i V N i N , for all i = 1, 2, • • • , M, (2.5)
that is, assign x to ω m , if

k m ≥ k i , for all i = 1, 2, • • • , M. (2.6)
Thus, the decision rule is to assign x to the class that receives the largest vote amongst the k nearest neighbors.

The kNN rule is an non-parametric lazy learning algorithm. First, it is non-parametric, which means that it does not make any assumptions on the underlying data distribution.

This is quite useful, as in the real world, most of the practical data does not obey the typical theoretical assumptions made (e.g., Gaussian mixtures, linearly separable, etc.).

Second, it is a lazy algorithm, which means that there is no explicit training phase, or it is very minimal. In addition, Cover and Hart [START_REF] Cover | Nearest neighbor pattern classification[END_REF] have provided a statistical justification of this procedure by showing that, as the numbers N and k both tend to infinity in such a way that k/N → 0, the error rate of the kNN rule approaches the optimal Bayes error rate. Beyond these remarkable properties, the kNN rule owes much of its popularity in the pattern recognition community to its good performance in practical applications.

However, in the finite sample case, the classical k-NN rule is not guaranteed to be the optimal way of using the information contained in the neighborhood of unclassified patterns. This is the reason why the improvement of this rule has remained an active research topic in the past 60 years. There are several key issues that affect the performance of the kNN rule. One of the problems encountered in using the voting kNN rule is that the distances from different nearest neighbors are neglected in the decision. To address this problem, several variants have been proposed [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF][START_REF] Dudani | The distance-weighted k-nearest-neighbor rule[END_REF][START_REF] Morin | A reappraisal of distance-weighted k-nearest-neighbor classification for pattem recognition with missing data[END_REF]. Particularly, an evidential version of k-nearest neighbor rule (EkNN) has been proposed based on the theory of belief functions in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]. In EkNN, each neighbor of a sample to be classified is considered as an item of evidence supporting certain hypotheses concerning the class membership of that sample. The evidence of the k nearest neighbors is then pooled by means of Dempster's rule of combination. This approach provides a well treatment for the uncertainty caused by the distance issue.

In this thesis, we focus on another two major issues in the kNN rule. One is that in using the kNN rule, each of the training samples is considered equally important in the assignment of the class label to the query pattern. This limitation frequently causes difficulty in regions where the data sets from different classes overlap. Atypical samples in overlapping regions are given as much weight as those that are truly representatives of the clusters. In order to overcome this difficulty, the sample editing procedure [START_REF] Wilson | Asymptotic properties of nearest neighbor rules using edited data sets[END_REF] was proposed to preprocess the original training samples. Besides, the choice of the distance metric [START_REF] Yang | Distance metric learning: a comprehensive survey[END_REF] is another important consideration, especially in small data set situations.

Although various metrics can be used to compute the distance between two points, the most desirable distance metric is one for which a smaller distance between two samples implies a greater likelihood of having the same class. In the following two sections, we will provide brief reviews for the existing sample editing methods and distance metrics.

Sample editing methods

In order to address the uncertain information in overlapping regions, several editing procedures have been proposed to preprocess the original training samples [START_REF] Keller | A fuzzy k-nearest neighbor algorithm[END_REF][START_REF] Koplowitz | On the relation of performance to editing in nearest neighbor rules[END_REF][START_REF] Nanni | Prototype reduction techniques: A comparison among different approaches[END_REF][START_REF] Tomek | An experiment with the edited nearest neighbor[END_REF][START_REF] Vazquez | A stochastic approach to Wilson's editing algorithm[END_REF][START_REF] Wilson | Asymptotic properties of nearest neighbor rules using edited data sets[END_REF]. According to the structure of the edited labels, the editing procedures can be divided into two categories: crisp editing and soft editing.

In [START_REF] Wilson | Asymptotic properties of nearest neighbor rules using edited data sets[END_REF], Wilson proposed a simple editing procedure to preprocess the training set.

This procedure classifies a training sample x i using the kNN rule with the remainder of the training set, and deletes it from the original training set if its original label ω (i) does not agree with the classification result. Later, concerned with the possibility of large amounts of samples being removed from the training set, Koplowitz and Brown [START_REF] Koplowitz | On the relation of performance to editing in nearest neighbor rules[END_REF] developed a modification of the simple editing technique. For a given value of k, another parameter k ′ is defined such that

(k + 1)/2 ≤ k ′ ≤ k.
Instead of deleting all of the conflicting samples, if a particular class (excluding the original class) has at least k ′ representatives among these k nearest neighbors, then x i is labeled according to that majority class (see Algorithm 1).

Essentially, both the simple editing procedure and its modification belong to the category of crisp editing procedures, in which each edited sample is either removed or assigned to a single class.

Algorithm 1: Modified simple editing algorithm Require: the original training set T composed of N labeled samples, two parameters k

and k ′ with (k + 1)/2 ≤ k ′ ≤ k T ′ ← T for i = 1 to N do Find k nearest neighbors of x i in T \ {x i , ω (i) } if a class label, say c, is held by at least k ′ neighbors then set the label of x i in T ′ to c else remove {x i , ω (i) } from T ′ end if end for return the edited training set T ′
In order to overcome the weakness of the crisp editing method, a fuzzy editing procedure was proposed that reassigns fuzzy membership to each training sample x i based on its k edit nearest neighbors according to the following equation [START_REF] Keller | A fuzzy k-nearest neighbor algorithm[END_REF]:

u j (x i ) = 0.51 + (k j /k edit ) * 0.49, if ω j = ω (i) (k j /k edit ) * 0.49, if ω j = ω (i) , (2.7)
where the value k j is the number of the neighbors found which belong to class ω j . This fuzzy editing procedure belongs to the soft editing category, in which each edited sample can be assigned to several classes. It provides more detailed information about the samples' membership than the crisp editing procedures.

Distance metrics

As the core of the kNN rule, the distance metric plays a crucial role in determining the classification performance, especially in small data set situations. To overcome the limitations of the original Euclidean (L2) distance metric, a number of methods have been proposed. According to the structure of the metric, these methods can be mainly divided into two categories: global distance metric learning [START_REF] Bar-Hillel | Learning distance functions using equivalence relations[END_REF][START_REF] Eick | Using clustering to learn distance functions for supervised similarity assessment[END_REF][START_REF] Wang | An information geometry approach for distance metric learning[END_REF][START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF], and local distance metric learning [START_REF] Jahromi | A method of learning weighted similarity function to improve the performance of nearest neighbor[END_REF][START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF][START_REF] Paredes | Learning weighted metrics to minimize nearest-neighbor classification error[END_REF][START_REF] Wang | Improving nearest neighbor rule with a simple adaptive distance measure[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF][START_REF] Ying | Distance metric learning with eigenvalue optimization[END_REF].

The global distance metric learning approach learns the distance metric in a global sense, i.e., the same global weighted (GW) distance metric is defined for all of the patterns:

d GW (x, y) = P j=1 λ 2 j (x j -y j ) 2 , (2.8)
where x is a sample in the training set, y is a query pattern to be classified, and λ j is the weight of the j-th feature. Although the above global distance metric is intuitively appealing, it is too coarse as the feature weights of the distance metric are irrelevant with the class labels of the patterns. For classification problems with a large number of classes, it is hard to learn a GW distance metric that can simultaneously separate all of the class pairs well.

In contrast, the local distance metric learning approach can learn a local distance metric for some specific patterns. According to the types of the used local information, this approach can be further subdivided into two categories: geometry-based local distance metric learning and label-based local distance metric learning. For the geometry-based local distance metric learning, the aim is to learn a locally adaptive distance metric in the neighborhood of each query pattern. Recently, Paredes et al. [START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF][START_REF] Paredes | Learning weighted metrics to minimize nearest-neighbor classification error[END_REF] provided another idea to learn the locally adaptive distance metric, i.e., the local distance metric is relevant to the class labels of the training samples. In their work, a class-dependent weighted (CDW) distance metric was defined as

d CDW (x, y) = P j=1 λ j c 2 (x j -y j ) 2 , (2.9)
where λ j c is the weight of the j-th feature and c is the class index of training sample x. The CDW distance metric provides more freedom than the GW distance metric and can be learnt adaptively for different classes of the training samples. However, as illustrated in the following example, this distance metric is insufficient to reflect the local specificities in feature space for query patterns from different classes. x 1 [START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF][START_REF] Angiulli | Fast condensed nearest neighbor rule[END_REF] x 2 [START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF][START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF] x 3 [START_REF] Buchanan | Rule-based Expert Systems[END_REF][START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF] y 1 [START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF][START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF] • y 2 [START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF][START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF] Figure 2.1: A three-class classification example

Rule-based classification

Rules are one of the most common forms for representing various kinds of knowledge. Rulebased systems, usually constructed from human knowledge in forms of IF-THEN rules, are often applied to inference problems [START_REF] Buchanan | Rule-based Expert Systems[END_REF]. However, for most classification problems, the available information is in the format of a collection of training data. If rules can be learnt from the training data, the rule-based systems can be used for classification purpose. One such learning procedure has been introduced by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], and has since become well-known in the pattern recognition field as the fuzzy rule-based classification system (FRBCS). Due to its capability of building linguistic models interpretable to users, the FRBCS has been successfully applied to different real-world classification tasks, including image processing [START_REF] Stavrakoudis | A genetic fuzzy-rulebased 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], 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]. In this section, we first describe the main principle of the FRBCS developed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], and then provide a brief review for different improved FRBCSs in order to get better accuracy and robustness. Finally, we discuss the possibility and necessity of combining partial training data and expert knowledge based on the rule-based systems to perform classification.

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 consequence is C q with rule weight θ q , q = 1, 2, • • • , Q, (2.10)
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,np } 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 FRB. 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. Construction 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 fuzzy grids is usually employed [START_REF] Ishibuchi | Distributed representation of fuzzy rules and its application to pattern classification[END_REF]. Figure 2.2 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. (a) To calculate its matching degree µ(x i ) with different fuzzy regions using the geometric mean operator

Generation of a fuzzy rule for each training pattern. Assume that

N labeled P - dimensional training patterns x i = (x i1 , • • • , x iP ), i = 1, 2, • • • , N are available. For
µ A q (x i ) = P P p=1 µ A q p (x ip ), (2.11)
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, the consequent class determined by the class label of the training pattern, and the rule weight determined by the greatest matching degree.

3. Reduction of the generated FRB. 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, and the other ones are removed.

Once the FRB has been constructed, the query patterns can be classified by the following single winner FRM [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF]. 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 }. (2.12)
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].

As one of the computational intelligence-based classification approaches, the most useful characteristic of the FRBCS is high interpretability. In contrast with statistical machine learning approaches, which are based on complicated statistical models and perceptronbased approaches, which are based on black-box models, the FRBCS can build a linguistic model interpretable to users. In addition, due to the use of fuzzy sets, the FRBCS can use 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].

However, 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. Besides, the fuzzy rule structure is not robust to pattern noise and wrong rules may be generated in noisy conditions, which hinders its applications in harsh working conditions (e.g., battlefield target recognition). Therefore, plenty of work has been done in the past two decades in order to improve the accuracy and robustness of the FRBCS. In the following section, we will give a brief review of different improved FRBCSs.

Improved FRBCSs

In the past two decades, many researchers have proposed variants of the original FRBCS developed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], in order to improve its accuracy and robustness. These approaches can be mainly divided into two categories: learning an optimized rule base with sophisticated methods, and changing the rule structure to make it more flexible to characterize the input-output mapping.

Approaches in the first category are motivated by the fact that unsatisfactory classification results may be due to defects of the rule generation method. The original fuzzy rule structure displayed as Eq. (2.10) is still used, but optimized rule bases are learnt with sophisticated methods. For example, in [START_REF] Chen | Support vector learning for fuzzy rule-based classification systems[END_REF], the rule base was built from the given training samples based on a support vector learning approach; in [START_REF] Alcala-Fdez | A fuzzy association rule-based classification model for high-dimensional problems with genetic rule selection and lateral tuning[END_REF][START_REF] Cordon | Genetic Fuzzy Systems[END_REF], the genetic algorithms were used for designing fuzzy rule bases and determining an appropriate combination of antecedent and consequent linguistic values of each fuzzy rule.

In contrast, work in the second category is mainly based on the claim that the original fuzzy rule structure is insufficient to characterize the complex input-output mapping. The original fuzzy rule structure is extended in different ways to become more flexible (e.g., by extending the consequent part or the antecedent part). In [START_REF] Cordón | A proposal on reasoning methods in fuzzy rule-based classification systmes[END_REF], the following fuzzy rule structure with certainty degrees for all classes in the consequent part was provided:

R q : If x 1 is A q 1 and • • • and x P is A q P , then (θ q 1 , • • • , θ q M ), q = 1, 2, • • • , Q, (2.13)
where θ 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. This type of rule extends the original fuzzy rule using different values for the consequent part

(θ q 1 , • • • , θ q M ). Considering θ q j = θ q , if ω j = C q 0, otherwise,
we get the original fuzzy rule. Accordingly, based on this new extended fuzzy rule structure, an additive combination reasoning method is employed to classify a query pattern y as follows:

ω = arg max ω j ∈Ω Q q=1 µ A q (y) • θ q j . (2.14)
A different approach was proposed in [START_REF] Liu | A novel belief rule base representation, generation and its inference methodology[END_REF], where the antecedent part of the original fuzzy rule is extended with belief degrees embedded in each antecedent terms as follows:

R q : If x 1 is {(A 1,j , α q 1,j )} n 1
j=1 and • • • and x P is {(A P,j , α q P,j )} n P j=1 , then consequence is C q , with rule weight θ q , q = 1, 2,

• • • , Q, (2.15)
where the antecedent term for each feature {(A p,j , α q p,j )} np j=1 is in belief distribution. Considering

α q p,j = 1, if A p,j = A q p 0, otherwise , p = 1, • • • , P,
we get the original fuzzy rule. Accordingly, based on this rule structure, each training sample is developed as a rule to model the input-output relationship. The query pattern is then classified by the additive combination of the weighted consequences of all of the generated rules.

Classification with partial training data and expert knowledge

According to the type of information used in modeling, pattern classification methods can be categorized into data-driven and knowledge-driven [START_REF] Tang | Adaptive fuzzy rule-based classification system integrating both expert knowledge and data[END_REF]. Data-driven models are based on learning from the training data characterizing the problem at hand. These data are usually collected by sensors observing the environment. In the previous part of this chapter, we mainly focused on data-driven models. In contrast, knowledge-driven models are based on the expert knowledge understanding a particular domain or problem. Expert knowledge is often encoded into rules or relations, based on which an inference is made [START_REF] Markman | Knowledge Representation[END_REF]. Examples of the most popular systems using knowledge-driven models are expert systems [START_REF] Jackson | Introduction to Expert Systems[END_REF][START_REF] Rychener | Expert Systems for Engineering Design[END_REF] and decision support systems [START_REF] Bonczek | Foundations of Decision Support Systems[END_REF][START_REF] Holsapple | Decision Support Systems: A Knowledge-Based Approach[END_REF].

In some real-world pattern classification applications, both training data and expert knowledge may be available. For example, for target recognition [START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF][START_REF] Dasgupta | A multiagent swarming system for distributed automatic target recognition using unmanned aerial vehicles[END_REF], historical measurements from a long period of collection by sensors can be used to train the target recognition system. In addition, the expert knowledge about target characteristics obtained from the manufacturers or intelligence also provides important information for target recognition. In the classification process, training data and expert knowledge are usually complementary.

The training data trends to provide a relatively fine estimate for the real class-conditional distribution, but they may be unreliable in some specific regions of feature space, due to limited training patterns and the potential measurement noise. In contrast, the expert knowledge usually provides a relatively rough but overall reliable estimate for the real class-conditional distribution.

In the past, several methods have been proposed to address the classification problem based on both training data and expert knowledge. For instance, Zhou et al.

Introduction

As one of the most well-known classification methods, the k-nearest neighbor (kNN) rule [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF] provides a simple non-parametric procedure for the assignment of a class label to the query pattern based on its k nearest neighbors. In this decision rule, the class label represented by each neighbor is considered equally important, regardless of their typicality.

This rule may have difficulty for cases where the data sets from different classes overlap strongly. It may be argued that the atypical samples in overlapping regions should not be given as much weight as those that are truly representatives of the clusters. In order to overcome this difficulty, the editing procedure was proposed to preprocess the original training samples and the kNN rule was used to classify the query pattern based on the edited training samples.

As reviewed in Section 2.3.2, according to the structure of the edited labels, the editing procedures can be divided into crisp editing and soft editing. A fuzzy editing procedure, proposed by Keller et al. [START_REF] Keller | A fuzzy k-nearest neighbor algorithm[END_REF], as a type of soft editing techniques, can provide more detailed information about the sample membership than the crisp editing procedures. However, different types of uncertainty may coexist in real-world classification problems, e.g., fuzziness may coexist with imprecision. The fuzzy editing procedure, which is based on fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF], cannot address imprecise information effectively in the modeling and reasoning processes. In contrast, the theory of belief functions can well model imprecise information thanks to the belief functions defined on the power set of the frame of discernment. The

Evidential editing k-nearest neighbor classifier

Let us consider an M -class classification problem and let

Ω = {ω 1 , • • • , ω M } be the set of classes. Assuming that a set of N labeled training samples T = {(x 1 , ω (1) ), • • • , (x N , ω (N ) )}
with input vectors x i ∈ R P and class labels ω (i) ∈ Ω are available, the problem is to classify a query pattern y ∈ R P based on the training set T .

The proposed evidential editing k-nearest neighbor (EEkNN) procedure is composed of the following two stages:

1. Preprocessing (evidential editing): The evidential editing algorithm assigns evidential labels to each labeled sample.

Classification:

The class of the query pattern is decided based on the distance to the sample's k nearest neighbors and these k nearest neighbors evidential membership information.

Evidential editing

The goal of the evidential editing stage is to assign to each sample in the training set T a new soft label with an evidential structure as follows:

T ′ = {(x 1 , m 1 ), (x 2 , m 2 ), • • • , (x N , m N )}, (3.1)
where The problem is now to compute an evidential label for each training sample. In [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF],

m i , i = 1, 2, • • • , N ,
an evidential k-nearest neighbor (EkNN) rule was proposed based on the theory of belief functions, where the classification result of the query pattern is a mass function. In the following part, we use the EkNN rule to carry out the evidential editing.

For each training sample

x i , i = 1, 2, • • • , N , we denote the leave-it-out training set as T i = T \ {(x i , ω (i) )}, i = 1, 2, • • • , N
. Now, we consider the evidential editing for one training sample x i on the basis of the information contained in T i . For the training sample

x i , each neighbor x j (j = i) provides an item of evidence regarding the class membership

of x i as follows        m i ({ω q } | x j ) = αφ q (d ij ) m i (Ω | x j ) = 1 -αφ q (d ij ) m i (A | x j ) = 0, ∀A ∈ 2 Ω \ {Ω, {ω q }}, (3.2)
where d ij = d(x i , x j ), ω q is the class label of x j (that is, ω (j) = ω q ), and α is a parameter such that 0 < α < 1. As suggested in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], α = 0.95 can be used to obtain good results on average. When d is the Euclidean distance, a good choice for φ q is

φ q (d) = exp(-γ q d 2 ), (3.3)
where γ q is a positive parameter associated to class ω q , which can be heuristically set to the inverse of the mean squared Euclidean distance between training samples belonging to class ω q .

Based on the distance d(x i , x j ), we select the k edit nearest neighbors of x i in training set T i and calculate the corresponding k edit mass functions in the above way. As the items of evidence from different neighbors are independent (because the training samples are usually measured or collected independently), the k edit mass functions are combined using Dempster's rule defined by Eq. (1.10) to form a resulting mass function m i , synthesizing the final evidential membership regarding the label of x i as

m i = m i (• | x i 1 ) ⊕ m i (• | x i 2 ) ⊕ • • • ⊕ m i (• | x i k edit ), (3.4)
where i 1 , i 2 , • • • , i k edit are the indices of the k edit nearest neighbors of x i in T i . Generally, the selection of parameter k edit depends on the specific classification problem. In practice, we can use cross-validation to search for the best value.

Classification

After the evidential editing procedure introduced in Section 3.2.1, the problem now turns into classifying a query pattern y ∈ R P based on the new edited training set T ′ as shown in Eq. (3.1). In this section, we extend the evidential k-nearest neighbor (EkNN) rule [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] to handle the more general situation in which the edited training samples are assigned dependent evidential labels. This classification procedure is composed of the following two steps: first, the mass functions from the k nearest neighbors of the query pattern are computed; then, the k mass functions are combined to obtain the final result.

Determination of the mass functions

Consider the k nearest neighbors of the query pattern y. If one training sample x i is very close to y, generally, it means that x i is a very reliable piece of evidence for the classification of y. In contrast, if x i if far from y, then it provides only little reliable evidence. In the theory of belief functions, Shafer's discounting operation defined by Eq. (1.24) can be used to discount the unreliable evidence before combination.

Denote as m i the class membership of the training sample x i , and β i the confidence degree of the class membership of y with respect to the training sample x i . The evidence provided by x i for the class membership of y is represented with a discounted mass function β i m i by discounting m i with a discount rate 1β i as follows:

β i m i ({ω q }) = β i m i ({ω q }), q = 1, 2, • • • , M β i m i (Ω) = β i m i (Ω) + (1 -β i ). (3.5)
The confidence degree β i is determined based on the distance d i between x i and y, in such a way that a larger distance results in a smaller confidence degree. Thus, β i should be a decreasing function of d i . We use a similar decreasing function with Eq. (3.3) to define the confidence degree β i ∈ (0, 1] as

β i = exp(-λ i d 2 i ), (3.6)
where λ i is a positive parameter associated to the training sample x i and is defined as

λ i =   M q=1 m i ({ω q })d q + m i (Ω)d   -2 , (3.7)
where d is the mean distance between all training samples, and d q is the mean distance between training samples belonging to each class ω q , q = 1, 2, • • • , M .

Remark 3.2. In calculating the confidence degree, parameter λ i is designed by extending the parameter γ q in Eq. (3.3) to the evidential membership structure. In Eq. (3.7), suppose that the label of the training sample x i is crisp with ω q , i.e., m i ({ω q }) = 1, m i ({ω j }) = 0,

for j = 1, 2, • • • , M , j = q, m i (Ω) = 0.
Then, the parameter λ i reduces to γ q in the case of crisp labels. With this design for parameter λ i , the confidence degree β i defined in Eq. (3.6) is not independent with the mass function m i any longer. Considering that the dependence between them is quite weak (because distance d i is more influential than m i in determining β i ), we still use Shafer's discounting operation to obtain the discounted mass function approximately.

Combination of the mass functions

To make a decision about the class of the query pattern y, the generated k mass functions should be combined to obtain the final fusion result. For combination, Dempster's rule relies on the assumption that the items of evidence combined are independent. However, as illustrated in the following example, in the editing process, common training samples may be used for calculating the class membership of different edited samples. Therefore, the items of evidence from different edited samples to classify the query pattern y cannot be regarded as independent.

Exemple 3.1.

m = β i 1 m i 1 ⊛ s β i 2 m i 2 ⊛ s • • • ⊛ s β i k m i k , (3.8)
where

i 1 , i 2 , • • • , i k are

Experiments

The performance of the proposed evidential editing k-nearest neighbor (EEkNN) classifier was evaluated in four different experiments. In the first experiment, the combination rule used in the EEkNN classifier was evaluated under different dependence degrees of the edited samples. In the second experiment, the effects of the two main parameters k edit and k in the EEkNN classifier were analyzed. In the last two experiments, the performance of the EEkNN classifier was compared with those of other nearest-neighbor-based methods (the modified simple editing kNN (SEkNN) [START_REF] Koplowitz | On the relation of performance to editing in nearest neighbor rules[END_REF], the fuzzy editing kNN (FEkNN) [START_REF] Keller | A fuzzy k-nearest neighbor algorithm[END_REF] and the evidential kNN (EkNN) [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]) using synthetic data sets and real data sets.

Evaluation of the combination rules

Parameter analysis

This experiment was designed to analyze the effect of parameters k edit and k for the proposed EEkNN method. The same training and test samples with the previous experiment were used. The difference is that in the preprocessing stage, k edit = 3, 6, 9, 12, 15, 18, 21, 24 were selected and the optimal t-norms based combination rule for each specific k edit value was used to make the classification. Average classification accuracy over the 30 trials with values of k ranging from 1 to 25 has been investigated. Furthermore, the EEkNN method is less sensitive to the value of k and it performs well even with a small value of k.

k edit =3 k edit =6 k edit =9 k edit =12 k edit =15 k edit =18 k edit =21 k edit =24

Synthetic data test

1 Computed as p -u 1-α 2 S √ Nt , p + u 1-α 2 S √ Nt , where p = 1 Nt N t i=1 pi, S = 1 Nt -1 N t i=1 (pi -p) 2 , with pi, i = 1, 2, • • • , Nt,

Real data test

This experiment was designed to compare the proposed EEkNN with other nearest-neighborbased methods using some 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]. The main characteristics of the 10 real data sets used in this experiment are summarized in Table 3.1, where "# Instances" is the number of instances in the data set, "# Features" is the number of features, and "# Classes" is the number of classes. To assess the results, we considered the resampled paired test. A series of 30 trials was conducted. In each trials, the available samples were randomly divided into a training set and a test set (with equal sizes). For each data set, we calculated the average classification rate of the 30 trials and the corresponding 95% confidence interval. For the proposed EEkNN method, the best values for the parameters k edit and s were determined with the same procedure used in the previous experiment. For all of the considered method, values of k ranging from 1 to 25 have been investigated. It can be seen that, for data sets with high overlapping ratios, such as Balance, Haberman, Ionosphere, Liver, Pima, Transfusion, Waveform and Yeast, the EEkNN method provides better classification performance than other nearest-neighbor-based methods, especially for small value of k. In contrast, for those data sets with relatively low overlapping ratios, such as Glass and Vertebral, the classification performances of different methods were quite similar. The reason is that, for these two data sets, the best classification performance was obtained when k took a small value and, under this circumstance, the evidential editing cannot improve the classification performance. We can also see that, different from other nearest-neighbor based methods, the EEkNN method is less sensitive to the value of k and it usually performs well even with a small value of k.

Conclusion

An evidential editing k-nearest neighbor (EEkNN) classifier has been developed based on an evidential editing procedure that reassigns the original training samples with new labels represented by an evidential membership structure. Thanks to this procedure, patterns situated in overlapping regions have less influence on the decisions. Our results show that the proposed EEkNN classifier achieves better performance than other considered nearestneighbor-based methods, especially for data sets with high overlapping ratios. In particular, the proposed EEkNN classifier is not too sensitive to the value of k and it can gain a quite good performance even with a small value of k. This is an advantage in time or spacecritical applications, in which only a small value of k is permitted in the classification process.

Chapter 4

Evidential fusion of pairwise k-nearest neighbor classifiers

The performance of the k-nearest neighbor (kNN) classifier is known to be very sensitive to the distance metric used in classifying a query pattern, especially in small training data set cases. In this chapter, a pairwise distance metric related to pairs of class labels is proposed.

Compared with the existing distance metrics, it provides greater flexibility to design the feature weights so that the local specificities in feature space can be well characterized.

Based on the proposed pairwise distance metric, a polychotomous classification problem is solved by combining a group of pairwise kNN (PkNN) classifiers in the framework of belief functions to deal with the uncertain output information.

In this chapter, we first describe the background and motivations in Section 4.1. In Section 4.2, a pairwise distance metric is defined and a parameter optimization procedure is designed based on maximum likelihood principle. Using the proposed pairwise distance metric, the corresponding PkNN classifiers are combined in the framework of belief functions in Section 4.3. Two experiments to evaluate the performance of the proposed method are reported in Section 4.4. Finally, Section 4.5 concludes this chapter.

Introduction

The k-nearest neighbor (kNN) rule is known to have good performance for large training data set [START_REF] Cover | Nearest neighbor pattern classification[END_REF]. However, in many practical pattern classification applications, the training data set is incomplete, and the real class-conditional probability distributions cannot be well characterized using the limited training samples. In such small training data set situations (relative to the intrinsic dimensionality of the data involved), the ideal asymptotical behavior of the kNN classifier degrades dramatically [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]. This observation motivates the growing interest in finding variants of the kNN rule and adequate distance metrics that potentially improve the kNN classification performance in small data set situations.

As the core of the kNN rule, the distance metric plays a crucial role in determining the classification performance. To overcome the limitations of the original Euclidean (L2) distance metric, a number of methods have been proposed to address the distance metric learning issue. As reviewed in Section 2.3.3, according to the structure of the metric, these methods can be mainly divided into global distance metric learning and local distance metric learning. The main drawback of the global learning approach is that the learned single distance metric usually cannot separates all of the class pairs well. As one representative label-based local distance metric learning method, Paredes et al. [START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF] proposed to learn a class-dependent weighted (CDW) distance metric adaptively for each class. However, as illustrated in Example 2.1, as the learned CDW distance metric is only relevant to the class labels of the training samples, it is insufficient to reflect the local specificities in feature space for query patterns in different classes.

In this chapter, we focus on the label-based local distance metric learning problem. To overcome the limitations of the CDW distance metric, a pairwise distance metric related to the labels of the class pairs to be classified is defined. For a polychotomous classification problem, instead of learning a global distance metric, we decompose it into learning a group of pairwise distance metrics. Because only two classes are involved for each pairwise distance metric, the feature weights can be learnt in a more local way. Based on each learned pairwise distance metric, a pairwise kNN (PkNN) classifier can be designed to separate two classes. Then, a polychotomous kNN classification problem can be solved by fusing several PkNN classifiers. A variety of schemes have been proposed for deriving a combined decision from individual ones, such as voting rule [START_REF] Friedman | Another approach to polychotomous classification[END_REF], Bayes combination [START_REF] Kuncheva | Decision templates for multiple classifier fusion: an experimental comparison[END_REF], multilayered perceptrons [START_REF] Suen | The combination of multiple classifiers by a neural network approach[END_REF], etc. Considering that the output of each PkNN classifier may have high uncertainty, the PkNN classifiers are combined in the framework of belief functions due to its well capability of modeling and combining uncertain information.

Pairwise distance metric learning

To better characterize the local specificities in feature space, in Section 4.2.1, we define a pairwise weighted distance metric and design a parameter optimization procedure to learn it based on the maximum likelihood principle. Then, in Section 4.2.2, we extend the pairwise weighted distance metric to further consider the potential correlation between different features.

Pairwise weighted distance metric learning

Definition 4.1 (Pairwise weighted distance metric). Suppose x and y are two P -dimensional patterns whose labels belong to class pair Ω p,q = {ω p , ω q }. The pairwise weighted (PW) distance metric between x and y is defined as

d P W (x, y) = P j=1 λ j p,q 2 (x j -y j ) 2 , (4.1)
where λ j p,q is a constant that weights the role of the j-th feature in the distance metric concerning class pair Ω p,q . This definition includes, as particular cases, the distance metrics reviewed in Section

2.3.3. If λ j p,q = 1 for all p = 1, • • • , M , q = 1, • • • , M , j = 1,
• • • , P , the above defined PW distance metric reduces to the L2 distance metric. In addition, the GW and CDW distance metrics correspond to the cases where the metric weights do not depend on the class labels or are only dependent on the class label of the first pattern, respectively. Therefore, the PW distance metric provides a more general dissimilarity measure than the L2, GW or CDW distance metrics. x 1 [START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF][START_REF] Angiulli | Fast condensed nearest neighbor rule[END_REF] x 2 [START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF][START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF] x 3 [START_REF] Buchanan | Rule-based Expert Systems[END_REF][START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF] y 1 [START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF][START_REF] Aziz | A new multiple decisions fusion rule for targets detection in multiple sensors distributed detection systems with data fusion[END_REF] • y 2 [START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF][START_REF] Barnett | Calculating Dempster-Shafer plausibility[END_REF] In the above defined PW distance metric, the only free parameters are the feature weights related to the labels of the two considered classes. In the following part, we aim to learn feature weights λ j p,q (1 ≤ p < q ≤ M , j = 1, • • • , P ) from the training data by optimizing some criteria. A simple way of defining the criteria for the desired metric is to keep the data pairs from the same class close to each other while separating those data pairs from different classes far from each other [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF].

We divide training set T into M subsets T k , k = 1, • • • , M , with each T k containing all of the N k training data belonging to class ω k :

T k = {(x i , ω k ) | i ∈ I k },
where I k is the set of indices for training data x i belonging to class ω k .

We now consider learning feature weights λ j p,q (j = 1, • • • , P ) from training subsets T p and T q . Let us denote the set of data pairs from the same class as

S = {(x m , x n ) | m, n ∈ I p ; m < n} ∪ {(x m , x n ) | m, n ∈ I q ; m < n} ,
and the set of data pairs from different classes as

D = {(x m , x n ) | m ∈ I p ; n ∈ I q } .
Following the idea presented in [START_REF] Yang | Distance metric learning: a comprehensive survey[END_REF], a logistic regression model can be assumed when estimating the probability for any data pair (x m , x n ) to share the same class,

Pr(+ | (x m , x n )) = 1 1 + exp d 2 P W (x m , x n ) -µ p,q , (4.2)
and then the probability for any data pair

(x m , x n ) to share different classes is Pr(-| (x m , x n )) = 1 - 1 1 + exp d 2 P W (x m , x n ) -µ p,q = 1 1 + exp -d 2 P W (x m , x n ) + µ p,q , (4.3)
where "+" and "-" denote data pair (x m , x n ) belonging to the same class and different classes, respectively. Parameter µ p,q is the threshold. The data pair (x m , x n ) will be assigned higher probability to be in the same class when their square PW distance is much smaller than threshold µ p,q . In contrast, if their square PW distance is much larger than threshold µ p,q , they will be given more probability to have different classes.

Then, the overall log-likelihood for both the data pairs in S and D can be written as

L g {λ j p,q } P j=1 , µ p,q = log Pr(+ | S) + log Pr(-| D) = - (xm,xn)∈S log 1 + exp d 2 P W (x m , x n ) -µ p,q - (xm,xn)∈D log 1 + exp -d 2 P W (x m , x n ) + µ p,q = - (xm,xn)∈S log   1 + exp   P j=1 λ j p,q 2 (x mj -x nj ) 2 -µ p,q     - (xm,xn)∈D log   1 + exp   - P j=1 λ j p,q 2 (x mj -x nj ) 2 + µ p,q     . (4.4)
With the maximum likelihood estimation, the PW distance metric learning can be formulated as the following optimization problem max {λ j p,q } P j=1 ,µp,q L g {λ j p,q } P j=1 , µ p,q s.t. λ j p,q ≥ 0, j = 1, • • • , P, and µ p,q ≥ 0.

(4.5)
This is a convex programming problem, which can be solved using Newton's method [START_REF] Avriel | Nonlinear Programming: Analysis and Methods[END_REF].

Extension to pairwise Mahalanobis distance metric learning

In the previous section, the distance metric was learnt under the assumption that the P considered features are independent. However, in many real-world applications, this assumption is hardly tenable [START_REF] Webb | Statistical Pattern Recognition[END_REF]. Therefore, in the following, we extend the PW distance metric to further consider the correlation between different features.

Definition 4.2 (Pairwise Mahalanobis distance metric). Suppose x and y are two Pdimensional patterns whose labels belong to class pair Ω p,q = {ω p , ω q }. The pairwise Mahalanobis (PM) distance metric between x and y is defined as

d P M (x, y) = (x -y) T A p,q (x -y), (4.6)
where A p,q ∈ R P ×P is a positive semi-definite matrix (i.e., A p,q 0) that weights the role of features in the distance metric concerning class pair Ω p,q . If we restrict A p,q to be diagonal, the defined PM distance metric reduces to the PW distance metric.

In a similar way as described in the previous section, the PM distance metric learning can also be formulated as a nonlinear optimization problem. However, in the case of learning a full matrix A p,q , the constraint that A p,q be positive semi-definite becomes difficult to enforce, and Newton's method often becomes prohibitively expensive (requiring O(P 6 ) time to invert the Hessian over P 2 parameters). To simplify the computation, we model the matrix A p,q using the eigenspace of the training samples [START_REF] Yang | Distance metric learning: a comprehensive survey[END_REF]. Based on training subsets T p and T q , the covariance matrix between any two features is computed as

M p,q = 1 n p,q -1 i∈Ip,q (x i -x)(x i -x) T , (4.7)
where I p,q is the set of indices for training sample x i belonging to class ω p or ω q , n p,q is the number of training samples, and x is the mean feature vector over the n p,q training samples. Let v k p,q , k = 1, 2, • • • , K, are the top K (K ≤ P ) eigenvectors of matrix M p,q . We then assume that A p,q is a linear combination of the top K eigenvectors:

A p,q = K k=1 γ k p,q v k p,q v k p,q T , (4.8)
where γ k p,q , k = 1, 2, • • • , K, are the non-negative weights for linear combination.

Then, with the above matrix A p,q , the overall log-likelihood for both the data pairs in S and D can be written as

L g {γ k p,q } K k=1 , µ p,q = log Pr(+ | S) + log Pr(-| D) = - (xm,xn)∈S log 1 + exp d 2 P M (x m , x n ) -µ p,q - (xm,xn)∈D log 1 + exp -d 2 P M (x m , x n ) + µ p,q = - (xm,xn)∈S log 1 + exp K k=1 γ k p,q ν k m,n -µ p,q - (xm,xn)∈D log 1 + exp - K k=1 γ k p,q ν k m,n + µ p,q , (4.9
)

with ν k m,n = (x m -x n ) T v k p,q v k p,q T (x m -x n ).
With the maximum likelihood estimation, the PM distance metric learning can be formulated as the following optimization problem

max {γ k p,q } K k=1 ,µp,q L g {γ k p,q } K k=1 , µ p,q s.t. γ k p,q ≥ 0, k = 1, • • • , K, and µ p,q ≥ 0, (4.10)
which is similar to the optimization problem for the PW distance metric learning, and can be solved using the same optimization method.

Fusion of PkNN classifiers in the framework of belief functions

With the proposed pairwise distance metric concerning class pair Ω p,q , a pairwise kNN (PkNN) classifier can be designed to separate the two classes Ω p and Ω q based on the training subset T p ∪T q . For an M -class classification problem, M (M -1)/2 PkNN classifiers C p,q (1 ≤ p < q ≤ M ) can be designed and the final classification result can be obtained by combining the outputs of these PkNN classifiers. A popular method of combining the outputs of pairwise classifiers is the voting rule [START_REF] Friedman | Another approach to polychotomous classification[END_REF], where each classifier gives a vote for the predicted class and the class with the largest number of votes is predicted. However, a classifier C p,q is trained to distinguish only between classes Ω p and Ω q , thus its vote for a query pattern from a different class should be taken with care. In this section, we aim to overcome this difficulty by modeling the uncertainty related to the outputs of PkNN classifiers in the framework of belief functions. Our aim is to use the belief function theory to model the uncertainty inherent in the pairwise classification. Now, with a set of PkNN classifiers C p,q (1 ≤ p < q ≤ M ), we first study the representation of their outputs in terms of belief functions.

For the output of each PkNN classifier C p,q , there are two types of uncertainty. The first one is related to the fact that the real class label of query pattern y may actually not belong to class pair Ω p,q (called outer-pair uncertainty). The second one is that even the real class label of query pattern y belongs to class pair Ω p,q , affected by the noise of the training patterns, the result of the classifier is not always accurate (called inner-pair uncertainty). Therefore, the frame of discernment should be set as

Ω = {ω 1 , • • • , ω M },
which can characterize both kinds of uncertainty.

For the PkNN classifier C p,q , suppose x j is one of the k nearest neighbors of query pattern y in the training subset T p ∪ T q , and its class label is ω i ∈ Ω p,q . It can be seen as a piece of evidence that supports the query pattern y belongs to ω i . However, considering the outer-pair uncertainty, this piece of evidence is conditioned on hypothesis ω i ∈ Ω p,q :

m Ω [Ω p,q ]({ω i } | x j ) = 1. (4.11)
Further, due to the inner-pair uncertainty, this piece of evidence does not by itself provide 100% reliability. In the formalism of belief functions, this can be expressed by saying that only some part of the belief is committed to

ω i m Ω [Ω p,q ]({ω i } | x j ) = α j m Ω [Ω p,q ]({Ω p,q } | x j ) = 1 -α j , (4.12)
where α j ∈ [0, 1] is the probability that sample x j and query pattern y share the same class, and can be determined using the logistic regression model in Eq. (4.2) as

α j = 1 1 + exp d 2 P W (x j , y) -µ p,q . (4.13)
For the PkNN classifier C p,q , based on the k nearest neighbors of query pattern y,

we can calculate all the corresponding k mass functions in the above way. As the items of evidence from different neighbors are independent, the k mass functions are combined using Dempster's rule defined by Eq. (1.10) to form a resulting mass function synthesizing the overall conditional belief regarding the label of y as

m Ω [Ω p,q ] = m Ω [Ω p,q ](• | x i 1 ) ⊕ m Ω [Ω p,q ](• | x i 2 ) ⊕ • • • ⊕ m Ω [Ω p,q ](• | x i k ), (4.14)
where i 1 , i 2 , • • • , i k are the indices of the k nearest neighbors of y.

In a similar way, based on the outputs of the M (M -1)/2 PkNN classifiers C p,q (1 ≤ p < q ≤ M ), we can calculate all the corresponding M (M -1)/2 conditional mass functions. In order to combine these conditional mass functions in a uniform framework, the conditional mass function constructed as Eq. (4.14) should be deconditioned using Eq. (1.23) as

       m Ω p,q ({ω q }) = m Ω [Ω p,q ]({ω p }) m Ω p,q ({ω p }) = m Ω [Ω p,q ]({ω q }) m Ω p,q (Ω) = m Ω [Ω p,q ](Ω p,q ). (4.15)
where {ω p } and {ω q } denote the complement of set {ω p } and {ω q } with respect to set Ω, respectively.

Because the mass and plausibility functions are in one-to-one correspondence, we can compute the plausibility function P l p,q from the above constructed and deconditioned mass function m Ω p,q using Eq. (1.3) as

P l p,q ({ω i }) =        1 -m Ω [Ω p,q ]({ω q }), if i = p 1 -m Ω [Ω p,q ]({ω p }), if i = q 1, otherwise . (4.16)
In order to decrease the computation complexity, instead of combining the M (M -1)/2 mass functions m Ω p,q (1 ≤ p < q ≤ M ) using Dempster's rule of combination, we can compute the combined plausibility function P l directly using Eq. (1.25) to make the decision as follows

P l({ω i }) ∝ P l ′ ({ω i }) = 1≤p<q≤M P l p,q ({ω i }), ∀ω i ∈ Ω.
(4.17)

Note that the combined plausibility function P l is proportional to P l ′ , so the maximum plausibility rule can be used for P l ′ equivalently to make a decision. The class label of query pattern y is assigned to the class with maximum plausibility. the total number of the computed samples is about N (M -1), which is just M -1 times larger than the original kNN classifier. For most classification problems, such as the benchmark data sets studied in next section, the number of considered classes is not very large, so the computation cost of the proposed method is not a big problem.

Experiments

The performance of the proposed kNN classification method based on the pairwise distance metric and the belief function theory (denoted as PkNN-BF) was assessed by two different types of experiments. In the first experiment, a synthetic data set was used to show the behavior of the proposed method in a controlled setting. In the second one, several real data sets from the well-known UCI Repository of Machine Learning Databases [START_REF] Merz | UCI repository of machine learning databases[END_REF] were considered, with the aim to show that the proposed technique is adequate for a variety of real tasks involving different data conditions: large vs. small size, high vs. low dimension, etc.

Synthetic data test

A two-dimensional three-class classification problem was used to compare our method with the-state-of-art methods reviewed in Section 2.3.3, including the original kNN classifier based on L2 distance metric (L2-kNN) [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF], the kNN classifier based on GW distance metric (GW-kNN) [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF] and the kNN classifier based on CDW distance metric (CDW-kNN) [START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF]. The following class-conditional normal distributions were assumed.

µ A = (6, 6) T , µ B = (14, 6) T , µ C = (14, 14) T ,

Σ A = 3I, Σ B = 3I, Σ C = 3I.
Training sets of 60, 120 and 240 samples were generated using equal prior probabilities.

A test set of 3000 samples was used for classification accuracy estimation. For each case, 30 trials were performed with independent training sets. The average classification accuracy and the corresponding 95% confidence interval were calculated. For the proposed PkNN-BF method, as the features are independent from each other in this study, we used the PW distance metric. For all of the considered methods, values of k ranging from 1 to 25 have been investigated.

P l A,B ({A}) = 0.17, P l A,B ({B}) = 1, P l A,B ({C}) = 1; P l A,C ({A}) = 1, P l A,C ({B}) = 1, P l A,C ({C}) = 0.42; P l B,C ({A}) = 1, P l B,C ({B}) = 1, P l B,C ({C}) = 0.22.
Then, after the fusion of multiple PkNN sub-classifiers in the framework of belief functions, we get the combined result: P l ′ ({A}) = 0.17, P l ′ ({B}) = 1, P l ′ ({C}) = 0.09.

Finally, based on the maximum plausibility rule, we get Class B as the final classification.

Real data test

In this second experiment, ten well-known real data sets from the UCI repository were used to evaluate the performance of the PkNN-BF classifier. The main characteristics of the data sets are summarized in Table 4.1. In order to evaluate the effectiveness of the combination process using the belief functions, apart from the above compared methods, we also considered the method of combining the PkNN sub-classifiers using the voting rule (denoted as PkNN-VOTE). As for these real data sets, the feature correlations are unknown, the PM distance metric has been used for the PkNN sub-classifiers, and the extension of GW-kNN in Mahalanobis distance (denoted as GM-kNN) [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF] was instead for comparison. For all these kNN-based methods, the results for the optimal value of k ranging from 1 to 25, observed in each method were reported.

The classification results of the ten benchmark data sets are shown in Table 4.2. The significance of the differences between results is evaluated using a Mc Nemar test [START_REF] Dietterich | Approximate statistical tests for comparing supervised classification learning algorithms[END_REF] at a level of significance of α = 0.05. For each data set, the best classification accuracy is underlined, and those that are significantly improved than the baseline L2-kNN method are printed in bold. As can be seen from these results, the PkNN-BF method, presented in this chapter, outperforms the L2-kNN, GM-kNN and CDW-kNN methods for most of the classification performance for these small-size and high-dimension cases. In addition, the PkNN-BF method always performs better than PkNN-VOTE, especially for those data sets with small number of classes, because the voting rule will take great adventure when the total number of votes (M (M -1)/2, with M be the number of classes) is small. a The results underlined correspond to the best accuracy.

b The results typeset in boldface are significantly better than the baseline L2-kNN method at level α = 0.05.

Conclusion

In order to improve the performance of the kNN-based classifier in incomplete data set situations, a new distance metric called pairwise distance metric, has been proposed in this chapter. Compared with the existing distance metrics, the pairwise distance metric provides greater flexibility to design the feature weights so that the local specificities in feature space can be well characterized. A parameter optimization procedure was designed to learn the pairwise distance metric from the training data set. Based on the pairwise distance metric, a PkNN-BF classifier was developed, which combines the outputs of PkNN classifiers in the framework of belief functions. From the results reported in the last section, we can conclude that the proposed method achieved a uniformly good performance when applied to a variety of classification tasks, including those with high dimension and small sample size, in which cases the training data set is not rich enough to well characterize the real class-conditional probability distributions.

may coexist in real-world complex systems. The FRBCS, which is based on fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF], cannot effectively address imprecise or incomplete information in the modeling and reasoning processes. The theory of belief functions, 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], has become one of the most powerful frameworks for uncertain modeling and reasoning. As the fuzzy set theory is well suited to dealing with fuzziness, and the belief function theory provides an ideal framework for handling imprecision and incompleteness, many researchers have investigated the relationship between fuzzy set theory and belief function 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 the framework of belief functions 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], fault diagnosis [START_REF] Zhou | Online updating belief rule based system for pipeline leak detection under expert intervention[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].

In this chapter, we aim 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 high uncertainty. Based on the belief rule structure, a belief rule-based classification system (BRBCS) is developed as an extension of the FRBCS in the framework of belief functions.

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 the belief function 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 samples assigned to the corresponding antecedent fuzzy region. In this way, the adverse effects of the noisy training samples 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.

Belief rule-based classification system

Considering the advantages of belief functions for representing and reasoning with uncertain information, in this section we extend the classical FRBCS in the framework of belief functions and develop a belief rule-based classification system (BRBCS). As shown in Figure 5.1, the proposed BRBCS is composed of two components: the belief rule base, which establishes an association between the feature space and the class space, and the belief reasoning method which provides a mechanism to classify a query pattern based on the constructed rule base. In Section 5.

Belief rule structure

The fuzzy rule structure expressed in Eq. (2.10) 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. 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. (2.10) 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 consequence is C q = {(ω 1 , β q 1 ), • • • , (ω M , β q M )} with rule weight θ q and feature weights δ 1 , • • • , δ P , q = 1, 2, • • • , Q, (5.1)
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 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 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.

δ 1 , • • • , δ P with 0 ≤ δ 1 , • • • , δ P ≤

Belief rule base 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 the framework of belief functions.

As displayed in Eq. (5.1), 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 5.2.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 sample x i with the antecedent part A q using Eq. (2.11). In FRB, the consequent class is directly specified as the class label of the training sample 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 samples assigned to the corresponding antecedent fuzzy region to get the consequence in a belief distribution form.

Denote as T q the set of training samples assigned to the antecedent fuzzy region A q .

From the view of belief functions, the class set Ω = {ω 1 , • • • , ω M } can be regarded as the frame of discernment of the problem. For any training sample 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 the framework of belief functions, 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 ignorance. Therefore, this item of evidence can be represented by a mass function 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 }}, (5.2) with 0 < µ A q (x i ) ≤ 1.
For each x i ∈ T q , a mass function 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 mass functions can be combined using Dempster's rule. As shown in Eq. (5.2), only two focal elements are involved in each mass function. Because of the particular structure of the mass function, 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 )), (5.3)
where T q m is a subset of T q , corresponding to those training samples 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 )).
(5.4)

Therefore, the belief degrees of consequence of rule R q can be obtained as

β q m = m q ({ω m }), m = 1, 2, • • • , M, β q Ω = m q (Ω), (5.5)
where β q Ω is the belief degree unassigned to any individual class. 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 5.3. The idea to generate the belief degrees of consequence in this chapter is inspired by the EkNN 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 pattern is considered as an item of evidence that supports certain hypotheses regarding the class membership of that training sample. The corresponding relations of the two methods are as follows: a) the training samples assigned to the corresponding antecedent fuzzy region correspond to the k nearest neighbors of the query pattern in EkNN, and b) the validity of each training sample is measured by the matching degree with the antecedent part, and in EkNN, 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 reviewed in Section 2.4.1 has a similar idea to the voting kNN 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 EkNN classifier can obtain much better performance than the voting kNN 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. ( 5.1) 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 samples assigned to the antecedent fuzzy region A q . It is believed that if the items of evidence involved are in conflict with each other (e.g., if the items of evidence assign different classes with the highest belief), then the consequence has low validity. In the framework of belief functions, 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 , (5.6)
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. (5.7)
where |T q | is the number of training samples 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 samples are available for rule generation, whereas 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 . (5.8)
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 (e.g., if only one training sample 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 (e.g., if a large number of training samples 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 ). (5.9)
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.
(5.10)

Generation of feature weights

In the belief rule displayed as Eq. (5.1), the feature weights reflect the relative importance of the antecedent features with respect to their influence on the consequence. 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 between each feature and the consequence.

Suppose n p fuzzy partitions {A p,1 , A p,2 , • • • , A p,np } are established for feature A p . Now, we will derive the weight of feature A p by 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,np }, 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 . (5.11)
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 Ω , (5.12)
where β q m , m = 1, 2, • • • , M , and β q Ω are the belief degrees of consequence of rule R q generated in Section 5.2.2.1, and θ q is the rule weight of R q generated in Section 5.2.2.2.

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 ), (5.13)
where d J is Jousselme's distance, as defined by Eq. (1.8).

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

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

CF p = ∆C p . (5.15)
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. (5.16)

Belief reasoning method

As reviewed in Section 2.4.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 in the framework of belief functions 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).

Association degree with the consequence of a belief rule

Denote as y = (y 1 , y 2 , • • • , y P ) 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 p=1 µ A q p (y p ) δp , (5.17)
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. (5.16).

Remark 5.4. In Eq. (5.17), the contribution of a feature towards the matching degree is positively related to the weight of the feature. 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} .
(

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, and 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 ′ .

(5.19)

Remark 5.5. As a result of limitation due to the number of training samples, 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 .

Reasoning using belief functions

In the previous part, the association degrees of the query pattern y with the consequences of the activated belief rules are calculated. In essence, the association degree is a measure of the reliability of the corresponding consequence regarding the class of the query pattern.

Therefore, in the consequence combining process, the reliability of consequence of each activated belief rule should be taken into account. In the framework of belief functions, Shafer's discounting operation, defined by Eq. (1.24), is usually used to discount the unreliable evidence before combination. Regarding association degree α in Eq. (5.19) as the reliability factor, the consequence of one activated belief rule in Eq. (5.5) is discounted using Shafer's discounting operation as

α m({ω m }) = αβ m , m = 1, 2, • • • , M α m(Ω) = αβ Ω + (1 -α). (5.20)
For all of the |S ′ | = L activated belief rules, with 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 mass functions 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 mass function are all singletons except the ignorance set Ω.

Define I(i) as the index set of the former i mass functions. Let m I(i) be the mass function after combining all of the former i mass functions 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, (5.21)
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 mass function. Accordingly, as the recursive index i reaches L -1, the final results m I(L) ({ω q }),

q = 1, 2, • • • , M and m I(L) (Ω) (m({ω q }
) and m(Ω) for short, respectively) are obtained by combining all of the L mass functions. This combination result is the basis for the later decision process.

For decision making based on the combined mass function m calculated with Eq. (5.21), the belief function Bel, plausibility function P l and pignistic probability BetP are common alternatives. As the focal elements of the combined mass function 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 }),

P l({ω q }) = m({ω q }) + m(Ω), BetP ({ω q }) = m({ω q }) + m(Ω) M , q = 1, 2, • • • , M. (5.22)
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 mass function (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∈Ω P l({ω q }) = arg max ωq∈Ω BetP ({ω q }) = arg max ωq∈Ω m({ω q }).
(5.23)

That is, the strategies maximizing the three criteria Bel, P l, and BetP in Eq. (5.22) lead to the same decision: the query pattern is assigned to the class with maximum basic belief assignment.

Remark 5.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 5.2.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 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 was empirically assessed by 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 were used to evaluate the classification accuracy of the proposed BRBCS. In the second one, the noise was 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 last experiment, we provided an analysis for its time complexity.

Data sets and experimental conditions

Twenty well-known benchmark data sets from the UCI repository were selected to evaluate the performance of the BRBCS. The main characteristics of the 20 data sets are summarized in Table 5.1, 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 considered 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 was divided into B blocks, with B -1 blocks as a training set and the remaining block as a test set. Therefore, each block was used exactly once as a test set. We used 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 considered the average results of the five partitions.

For the first and the third experiments, the original data sets described above were used directly, whereas for the second, some additional processes were needed. As discussed in [91,[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 managed 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 was unknown, we used 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 was only added in the training sets, and the test sets remained unchanged. Based on the type of noise, as in [91], different schemes of noise introduction were designed as follows.

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

RLA x% = Acc 0% -Acc x% Acc 0% , (5.24)
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 adopted 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 were 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 used α = 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], and two improved FRBCSs (denoted as EFRBCS [START_REF] Cordón | A proposal on reasoning methods in fuzzy rule-based classification systmes[END_REF] and EBRB [START_REF] Liu | A novel belief rule base representation, generation and its inference methodology[END_REF], respectively) reviewed in Section 2.4.2. The settings of the considered methods are summarized in Table 5.2. As for the considered data sets no prior knowledge about the establishment of the fuzzy regions was available, and the fuzzy grids were used to partition the feature space. We normalized each feature value into a real number in the unit interval [0, 1]. Once the number of partitions for each feature was determined, the fuzzy partitions can be easily computed. Here, different numbers of partitions (C = 3, 5, 7) were employed to make the comparison. To compare the results statistically, we used nonparametric tests for multiple comparisons to find the best method, considering the average ranks obtained over the test data. First, we used the Friedman test to determine whether significant differences exist among all of the mean values. Table 5.4 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 applied the Bonferroni-Dunn test to compare the best ranking method (i.e., BRBCS) with the remaining methods. Table 5.5 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 5.4 and To analyze the effect of partition numbers on classification performance, in Table 5.3, the best accuracy 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 5.3.4, a larger partition number usually means a greater computation burden. Therefore, in practice, for those data sets with fewer features (P < 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 [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF] introduced in Section 2.4.1, the following two robust classifiers were 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 [91]: 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 [91], BagC4.5 is a good noise-robust multiple classifier system.

The settings of the considered methods are summarized in 5.7 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 5.7, the Friedman test was conducted to evaluate whether significant differences exist among the different methods. Table 5.8 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 used the Bonferroni-Dunn test to compare the best ranking method (i.e., BRBCS) with the remaining methods. Table 5.9 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 N L = 10%. This means that there is no significant difference only between BRBCS and BagC4.5 at noise level N L = 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 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 5.10 shows the RLA of our proposed BRBCS in comparison with other robust methods at different feature noise levels. In a similar manner, we first used the Friedman test to evaluate whether significant differences exist among the different methods. Table 5.11 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 used the Bonferroni-Dunn test to compare the best ranking method (i.e., BRBCS) with the remaining methods. As shown in Table 5.12, 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 N L = 10% and N L = 30%. In other words, there is no significant difference between BRBCS and BagC4.5 at noise levels N L = 10%

and N L = 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.

Time complexity analysis

Conclusion

In this chapter, we have extended the traditional FRBCS in the framework of belief functions and developed a belief rule-based classification system (BRBCS) to address uncertain information in complex classification problems. In Section 6.1, we first describe the background and motivations. The details of the proposed hybrid belief rule-based classification system are presented in Section 6.2. An airborne target classification problem in the air surveillance system is studied in Section 6.3 to demonstrate the performance of the proposed method for combining both uncertain training data and expert knowledge to make classification. Finally, Section 6.4 concludes this chapter.

Introduction

In the previous chapter, we have developed a belief rule-based classification system to learn from uncertain training data in complex classification problems. However, in some real-world pattern classification applications, apart from the training data, some expert knowledge from humans may also be available. As discussed in Section 2.4.3, these two types of information are usually independent and complementary, and both are useful for classification. Therefore, there is a need for an effective modeling method that can make good use of both training data and expert knowledge, and integrate the best aspects of these two types of information for classification.

belief rule base and a belief reasoning method. Compared with the BRBCS developed in Chapter 5, two modules are added, i.e., a knowledge-driven belief rule base (KBRB), and a hybrid belief rule base (HBRB). As the construction of data-driven belief rule base (DBRB) and the belief reasoning method have already been developed in Chapter 5, in this section, we focus on how to learn a KBRB from expert knowledge with the belief rule structure and how to obtain an optimal HBRB by combining the DBRB and KBRB.

Knowledge-driven belief rule base

In knowledge-based system development, knowledge representation is the task of encoding expert knowledge into a knowledge base. Based on different types of applications, many knowledge representation schemes have been proposed, such as logical representations, production rules, semantic networks and structured frames [START_REF] Helbig | Knowledge Representation and the Semantics of Natural Language[END_REF]. For production rules, as knowledge is represented in the form of condition/action pairs, they provide a natural way to characterize the association between feature space and class space for classification problems. Thus, in this section, we select the production rules (specially, the fuzzy IF-THEN rules) to represent expert knowledge.

Based on the fuzzy IF-THEN rules representation, the expert knowledge is acquired from experts using the structured interview technique [START_REF] Mcgraw | Knowledge Acquisition, Principles and Guidelines[END_REF]. That is, experts are asked to assign fuzzy regions to each class and to give corresponding certainty grades. Accordingly, for an M -class (denoted as Ω {ω 1 , ω With the above M pieces of expert knowledge e j , j = 1, 2, • • • , M , the problem now is how to generate a belief rule base with the belief rule structure as Eq. (5.1) from the expert knowledge. The knowledge-driven belief rule base is constructed in the following two stages: first, we expand the expert knowledge e j , j = 1, 2, • • • , M , into belief rules by enumerating all of the possible antecedent conditions; then, we combine expanded rules having the same antecedent part.

Expansion of expert knowledge

For the belief rule as Eq. (5.1), each feature is associated with a single fuzzy partition, whereas for the expert knowledge in Eq. (6.1), each feature is associated with a set of fuzzy partitions. Thus, one piece of expert knowledge e j can be expanded into some belief rules with the same consequent part and rule weight by enumerating all of the possible antecedent conditions as follows.

Belief Rule R 1

j : If x 1 is A 1 1 and x 2 is A 1 2 and • • • and x P is A 1 P , then consequence is C 1 = {(ω j , 1)} , with rule weight θ j , . . . Belief Rule R q j : If x 1 is A q 1 and x 2 is A q 2 and • • • and x P is A q P , then consequence is C q = {(ω j , 1)} , with rule weight θ j , . . . Belief Rule R Q j j : If x 1 is A Q j 1 and x 2 is A Q j 2 and • • • and x P is A Q j P , then consequence is C Q j = {(ω j , 1)} , with rule weight θ j , (6.2)
where the antecedent parts

(A q 1 , A q 2 , • • • , A q P ), q = 1, 2, • • • , Q j ,
are all the possible combinations of different partitions for A j 1 , A j 2 , • • • , A j P , and Q j is the number of belief rules generated from expert knowledge e j , with

Q j = P p=1 |A j p |.
In the same way, the M pieces of expert knowledge e j , j = 1, 2, • • • , M , can be expanded to generate M j=1 Q j belief rules. However, as different classes may overlap in feature space, the belief rules generated from different pieces of expert knowledge may have the same antecedent part but different consequent parts. These rules are in conflict with each other. In the following, we provide a method to combine these conflicting rules considering their rule weights.

Combination of conflicting rules

Suppose R q 1 j 1 , • • • , R q M ′ j M ′ (2 ≤ M ′ ≤ M ) are M ′ generated rules with the same antecedent part but different consequent parts {(ω j 1 , 1)} , • • • , (ω j M ′ , 1
) . In order to generate a compact KBRB, these M ′ rules should be fused into a new rule. The antecedent part of this new rule keeps the same, and its consequent part is obtained by combining those of the M ′ conflicting rules.

Each conflicting rule R qm jm provides a piece of evidence that supports the class ω jm as the consequent part of the new fused rule. Considering that this rule has a certainty grade θ jm , this piece of evidence can be represented by a mass function m qm verifying:

       m qm ({ω jm }) = θ jm m qm (Ω) = 1 -θ jm m qm (A) = 0, ∀A ∈ 2 Ω \ {Ω, {ω jm }}, (6.3)
where

Ω = {ω 1 , • • • , ω M } is the frame of discernment.
In a similar way, M ′ pieces of evidence m q 1 , • • • , m q M ′ can be constructed from the M ′ conflicting rules. These pieces of evidence are combined using Dempster's rule as follows:

           m({ω jm }) = θ jm 1 -K r =m (1 -θ jr ), m = 1, • • • , M ′ m(Ω) = 1 1 -K M ′ r=1
(1θ jr ), (6.4) where K is the total conflicting belief mass,

K = 1 - M ′ r=1 (1 -θ jr ) - M ′ m=1 θ jm r =m (1 -θ jr ). (6.5)
In addition, as the weights of the M ′ conflicting rules have already been considered in the combination process, the weight of the new fused rule is set to 1. Consequently, the M ′ conflicting rules can be replaced by a new fused rule with the same antecedent part and full weight but a different consequent part as (ω j 1 , m({ω

j 1 })), • • • , (ω j M ′ , m({ω j M ′ }))
. In a similar way, all other sets of conflicting rules can be replaced by a series of new fused rules and then a compact KBRB is obtained to encode the expert knowledge about the classification problem.

Hybrid belief rule base

In the previous section, a KBRB, dependent from the DBRB, is constructed based on expert knowledge. In this section, we aim to fuse these two different belief rule bases into a new hybrid belief rule base for classification. In real-world classification problems, both training data and expert knowledge may be uncertain. The uncertainty of training data comes from measurement noise, data entry errors, or small size of samples. The uncertainty of expert knowledge is mainly due to limited or incorrect assessment for the considered problem.

Consequently, both the DBRB and KBRB only provide partially reliable information for the classification problem. Thus, in order to get a more powerful hybrid belief rule base, we should take into account the weights of these two rule bases, which reflect their different roles in the fusion process.

Fusion of DBRB and KBRB

Assuming the DBRB is β (β > 0) times as important as the KBRB, the weights of these two BRBs are set to β/(1 + β) and 1/(1 + β), respectively. For notational convenience, we write λ = β/(1+β). Accordingly, the weight of the DBRB is λ and the weight of the KBRB is 1λ with 0 < λ < 1. The adjustment factor λ plays an important role in adjusting the hybrid decision boundaries. With a large value of λ, the hybrid boundaries tend toward the DBRB boundaries. In contrast, with a small value of λ, the hybrid boundaries tend toward the KBRB boundaries.

With the above defined weights, we now fuse the

Q D data-driven belief rules (R i D , i = 1, 2, • • • , Q D ) in the DBRB with the Q K knowledge-driven belief rules (R j K , j = 1, 2, • • • , Q K )
in the KBRB. As illustrated in Figure 6.2, due to the partial information provided by both training data and expert knowledge, the generated rules in both the DBRB and KBRB may only cover partial fuzzy regions. Furthermore, because of the independence between training data and expert knowledge, the fuzzy regions covered by the DBRB and the KBRB may not fully overlap. Thus, the rules in the integrated HBRB can be divided into the following three categories: rules with fuzzy regions only covered by the DBRB, rules with fuzzy regions only covered by the KBRB, and rules with fuzzy regions covered by both the DBRB and KBRB.

Let S = {(i, j) | R i D and R j K have the same antecedent part, i = 1, 2, • • • , Q D , j = 1, 2, • • • , Q K }, S D = {i | (i, j) ∈ S, j = 1, 2, • • • , Q K } and S K = {j | (i, j) ∈ S, i = 1, 2, • • • , Q D }.
The rules in the integrated HBRB are generated as follows.

• The rules with fuzzy regions only covered by the DBRB are generated by assigning the corresponding rules in the DBRB with new weights λθ

i , i ∈ {1, 2, • • • , Q D } \ S D ;
• The rules with fuzzy regions only covered by the KBRB are generated by assigning the corresponding rules in the KBRB with new weights

(1-λ)θ j , j ∈ {1, 2, • • • , Q K }\S K ;
• The rules with fuzzy regions covered by both the DBRB and KBRB are generated by assigning the corresponding rules in both the DBRB and KBRB with new weights λθ i + (1λ)θ j and new consequences m ij calculated by

m ij = λ m i ⊕ (1-λ) m j , (i, j) ∈ S, (6.6)
where λ m i denotes the discounted mass function for the consequence of the corresponding rule in DBRB with reliability factor λ, (1-λ) m j denotes the discounted mass function for the consequence of the corresponding rule in KBRB with reliability factor (1λ), and ⊕ is Dempster's rule of combination.

Proposition 6.1. The generated HBRB reduces to DBRB and KBRB when the adjustment factor λ takes 1 and 0, respectively.

Proof. Suppose the adjustment factor λ = 1. First, for those rules with fuzzy regions only covered by the DBRB, the new assigned weights λθ

i = θ i , i ∈ {1, 2, • • • , Q D } \ S D . Thus,
this category of rules is kept unchanged.

Second, for those rules with fuzzy regions only covered by the KBRB, the new assigned

weights (1 -λ)θ j = 0, j ∈ {1, 2, • • • , Q K } \ S K .
Thus, this category of rules are excluded from the generated HBRB. Third, for those rules with fuzzy regions covered by both the DBRB and KBRB, the new assigned weights λθ i + (1λ)θ j = θ i and new consequences

m ij = λ m i ⊕ (1-λ) m j = 1 m i ⊕ 0 m j , (i, j) ∈ S. (6.7)
From the definition of Shafer's discounting operation in Eq. (1.24), it is easy to see that 1 m i = m i , and 0 m j becomes to a vacuous mass function. Further, from the definition of Dempster's rule of combination in Eq. (1.10), the combination of any mass function with a vacuous mass function is equal to itself. Therefore, the new consequences m ij = m i , (i, j) ∈ S. Thus, those rules in overlapping fuzzy regions inherit directly from the corresponding rules in the DBRB.

Consequently, it can be concluded that the generated HBRB reduces to DBRB when the adjustment factor λ = 1. In a similar way, we can prove that the generated HBRB reduces to KBRB when the adjustment factor λ = 0.

Optimization of the adjustment factor

In the above HBRB generation process, the rules from the DBRB and KBRB are combined to get an integrated HBRB that can make use of the information from both training data and expert knowledge. In this combination process, the adjustment factor λ is used to adjust the weights of these two types of information. The adjustment factor λ can be specified by the user by evaluating the relative reliability of these two types of information.

However, due to the ignorance about the quality of training data or expert knowledge, it may be difficult for the user to specify a proper value for λ. In the following, we propose to search an optimal value for λ by optimizing the average leave-one-out test error.

Let us consider a training sample x i belonging to class ω m . Take x i as a test sample, and T i = T \ {(x i , ω m )} as the new training set. A HBRB can be generated based on the new training set T i and the expert knowledge. Using the belief reasoning method developed in Chapter 5, one can get the leave-one-out test output

P i = (BetP i ({ω 1 }), • • • , BetP i ({ω M })).
Ideally, the classification output vector P i should be as close as possible to the real class

vector t i = (t i1 , • • • , t iM ) (each binary indicator variable t ij is defined by t ij = 1, if j = m
and t ij = 0, otherwise), with closeness being defined according to the following squared error:

E λ (x i ) = (P i -t i )(P i -t i ) T = M j=1 (BetP i ({ω j }) -t ij ) 2 .
(6.8)

The mean squared error over the whole training set T of size N is finally equal to

E λ = 1 N N i=1 E λ (x i ). (6.9)
Therefore, the optimal value for λ is chosen with minimum leave-one-out test error, i.e., λ = arg min 0≤λ≤1 E λ . (6.10)

As the minimization of E λ is performed with respect to a single parameter in a bounded domain, a simple search procedure can be used.

Numerical study

In order to present the implementation of the proposed HBRBCS and demonstrate its capacity of combining both uncertain training data and expert knowledge for classification, we provide a numerical study for an airborne target classification in the air surveillance system.

Problem description

For air surveillance systems [START_REF] Ristic | Target classification approach based on the belief function theory[END_REF], one of the most important tasks is to correctly recognize noncooperative flying objects within their surveillance volume. In general, target classification is based on a set of features or attributes that distinguish targets according to their shapes or kinematic behaviors. To fully exploit the feature space, a surveillance system often consists of multiple sensors. For example, a radar can provide kinematic features (e.g., speed, acceleration) and an infrared sensor can supply shape features such as the length. In this study, we consider the classification of targets in predefined categories {Commercial plane, Bomber, F ighter}, based on their average speed (AveSpeed ), maximum acceleration (MaxAcc) and average length (AveLength) measured by a multi-sensor system composed of a land-based radar and an airborne infrared sensor.

In this numerical study, we simulated the feature measurements using the Gaussiandistributed class-conditional probability functions. We used Gaussian densities, with the parameters selected in such a way that P {s min < x < s max } = 0.95, where [s min , s max ]

is the feature interval given in Table 6.1. Figure 6.3 shows the distributions of the three features conditioned on the class.

Implementation of the hybrid belief rule base

In this study, assume that 120 labeled training samples x i = (x i1 , x i2 , x i3 ), i = 1, 2, • • • , 120, were collected by the multi-sensor system according to the above class-conditional probability distributions with equal prior probabilities. Further, assume the available training samples are not fully reliable, i.e., some of them have wrong class labels. We simulated this scenario by adding class noise with noise level of x% indicating x% of the samples in the training set are mislabeled. The class labels of these samples were randomly changed to different ones within the domain of the class. Apart from the uncertain training data, suppose three pieces of partially reliable expert knowledge e j , j = 1, 2, • • • , 3, were obtained by structured interview. These two types of information were used to construct the HBRB using the proposed method. The processes of constructing the HBRB concerning the airborne target classification problem were implemented as follows.

Step 1: Preprocess: fuzzification of the feature space The prerequisite step to generate a BRB is to fuzzify the feature space. We use the fuzzy grid partition method [START_REF] Ishibuchi | Distributed representation of fuzzy rules and its application to pattern classification[END_REF] to fuzzify the feature space. Suppose according to the a priori knowledge, it is known that the three features AveSpeed, MaxAcc, and AveLength, change in the intervals [400, 1000], [0, 6] and [START_REF] Bar-Hillel | Learning distance functions using equivalence relations[END_REF][START_REF] Markman | Knowledge Representation[END_REF], respectively. The partition number for each feature is set to three. As only a few training samples are available, a large partition number may result in over-fitting. Moreover, a relatively small partition number makes it easier for the experts to assign fuzzy regions to each class. Based on the fuzzy grid partition method, the fuzzification of the three features is shown in Figure 6.4. Fortunately, the developed rule weight generation method only assigns this rule a small weight, which decreases its effect in the reasoning process. As shown in Table 6.3, each piece of expert knowledge covers several fuzzy regions. We can further see that one fuzzy region {M ∧ L ∧ M } is covered by both the expert knowledge e 1 and e 2 , and two fuzzy regions {M ∧L∧L} and {M ∧M ∧L} are covered by both the expert knowledge e 2 and e 3 . For these three regions, the consequences are obtained by combing the conflicting pieces of expert knowledge considering their certainty grades with Eqs.(6.3-6.5). For those non-overlapping regions, the consequences are kept unchanged. Table 6.4

shows the KBRB containing 13 belief rules constructed from the expert knowledge. In the constructed KBRB, rule R 6 K is obtained by combining the conflicting items e 1 and e 2 , and rules R 5 K and R 8 K are obtained by combining the conflicting items e 2 and e 3 . We can see that for the three new fused rules, the consequences are not complete (i.e., the sum of the belief for all of the three classes is less than one), with the left belief characterizing the ignorance induced by the partially reliable expert knowledge. Due to partially available expert knowledge, the generated KBRB only covers part of the fuzzy regions of the feature space. In addition, due to the insufficiency of the expert knowledge, the consequences of some rules may be unreliable. For example, in the constructed KBRB, the rule R 1 K assigns full belief to ω 2 . However, according to the real class-conditional distributions shown in Figure 6.3, the samples from class ω 3 also have a large possibility to fall into the corresponding fuzzy region {L ∧ L ∧ L}. Step 4: Construction of HBRB In this stage, the rules from the DBRB (Table 6.2) and the KBRB (Table 6.4) are combined based on the fusion algorithm developed in Section 6.2.2. Table 6.5 shows the optimal HBRB containing 14 belief rules by optimizing the average leave-one-out test error. Compared to the previous generated DBRB and KBRB, the integrated HBRB has the following two main advantages:

1. It covers more fuzzy regions than both the DBRB and the KBRB, so that it is more powerful to classify those patterns uncovered by either the DBRB or the KBRB.

2. In the overlapping fuzzy regions of the DBRB and the KBRB, through combination, the rules in HBRB reduced the potential unreliability existing in the corresponding rules of DBRB or KBRB. For example, as indicated in Step 2, the rule R 3 D generated from the uncertain training data is unreliable, but after combination with the corresponding rule R 3 K , the consequence of the combined rule R 3 H has better representation for the real class distributions in the fuzzy region {L ∧ M ∧ L}. Similarly, as indicated in Step 3, the rule R 1 K generated from the uncertain expert knowledge is unreliable, but after combination with the corresponding rule R 1 D , a better rule R 1 H is generated for the fuzzy region {L ∧ L ∧ L}.

Comparative study

The HBRBCS was compared to the DBRBCS (λ = 1, which only considers the uncertain training data) and the KBRBCS (λ = 0, which only considers the uncertain expert knowledge) under different noise levels for the training data. A test set of 3000 samples drawn from the original class-conditional probability distributions were used for error estimation. For the HBRBCS, the optimal adjustment factor λ by optimizing the average leave-one-out test error was used to get the integrated HBRB. In addition, two well-known robust data-based classifiers, C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] and FRBCS [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], as well as a representative hybrid classifier AFRBCS [START_REF] Tang | Adaptive fuzzy rule-based classification system integrating both expert knowledge and data[END_REF] reviewed in Section 2.4.3 were also considered in the comparison. In order to find out whether significant differences exist among different methods, error estimation confidence intervals (with confidence level A = 95%) 1 for the best method 1 Computed by numerically solving the equations: classification.

Table 6.7 compares the estimated value of λ by optimizing the average leave-one-out test error with the tested optimal value of λ indicated in Figure 6.5. It can be seen that the parameter optimization method provides a good estimation for the optimal value of λ. Accordingly, the classification error rate with the estimated optimal value of λ is very close to the tested optimal error rate. In addition, the estimation is more accurate with low noise levels, because in these cases the training data has a good representation of the real class-conditional distributions.

Conclusion

In order to make use of the information from both uncertain training data and expert knowledge for classification, a hybrid belief rule-based classification system (HBRBCS) has been developed based on the belief rule structure. The proposed HBRBCS offers complementary advantages from data-driven models and knowledge-driven models. This system can be useful for many real-world applications where both uncertain training data and expert knowledge are available. An airborne target classification in the air surveillance system has been studied to present the implementation of the proposed HBRBCS and to demonstrate its capacity of combining both uncertain training data and expert knowledge for classification. The experiment results show that the HBRBCS can make good use of these two types of independent and complementary information and achieve better performance.

Conclusions and future research directions

Future research directions

The work presented in this thesis can be continued in many directions. In the following paragraphs, we sketch a few of them.

For short-term perspectives, some of the methods developed in this thesis can be further extended. Our first concern is the distance metric leaning problem in kNN rule. In Chapter In the long term, we will focus on some other important uncertain data classification problems. One such challenging problem emerging in machine learning field is sequence labeling. For the classification problems considered in this thesis, the samples are assumed to be collected independently. However, for some real-world applications, such as speech

Finally 1 . 1 9 1. 2 21 3. 1 53 4. 1 87 5. 3 88 5. 4 89 5. 6 92 5. 8 10 1. 2 49 3. 3 50 3. 4 52 3. 5 59 4. 2 63 4. 3 66 4. 4 68 5. 1 75 5. 2 95 xxi 6 . 1

 11922115318738848969281024935045255926336646817529561 , I wish to express my deepest appreciation to my parents, my girlfriend Xiaoxue, my brother and sister, for their love, support and encouragement throughout the long journey of my study. Examples of mass functions defined over Ω = {ω 1 , ω 2 , ω 3 } . . . . . . . . . . . The belief, plausibility and pignistic probability with regard to each suspect . Description of the benchmark data sets employed in the study . . . . . . . . . Statistics of the benchmark data sets used in the experiment . . . . . . . . . . 69 4.2 Classification accuracy rate (in %) of our proposed method compared with other kNN-based methods for real data . . . . . . . . . . . . . . . . . . . . . . 69 5.1 Description of the benchmark data sets employed in the study . . . . . . . . . 85 5.2 Settings of considered methods for classification accuracy evaluation . . . . . Classification accuracy rate (in %) of our proposed BRBCS in comparison with other rule-based methods for different numbers of partitions . . . . . . . Friedman test of the accuracy for the considered methods (α = 0.05) . . . . . 89 5.5 Bonferroni-Dunn test of the accuracy for comparing BRBCS with other methods (α = 0.05) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Settings of considered methods for classification robustness evaluation . . . . 90 5.7 RLA (in %) of our proposed BRBCS in comparison with other robust methods at different class noise levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . Friedman test of RLA for considered methods at different class noise levels (α = 0.05) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.9 Bonferroni-Dunn test of RLA for comparing BRBCS with other methods at different class noise levels (α = 0.05) . . . . . . . . . . . . . . . . . . . . . . . 93 5.10 RLA (in %) of our proposed BRBCS in comparison with other robust methods at different feature noise levels . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.11 Friedman test of RLA for considered methods at different feature noise levels (α = 0.05) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.12 Bonferroni-Dunn test of RLA for comparing BRBCS with other methods at different feature noise levels (α = 0.05) . . . . . . . . . . . . . . . . . . . . . . 96 5.13 Average runtime (in s) of our proposed BRBCS for different data sets and different partition numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.1 Feature intervals for three airborne target classes . . . . . . . . . . . . . . . . 107 6.2 DBRB constructed based on the uncertain training data . . . . . . . . . . . . 109 6.3 Fuzzy regions covered by each piece of expert knowledge . . . . . . . . . . . . 110 6.4 KBRB constructed based on the expert knowledge . . . . . . . . . . . . . . . 110 xix 6.5 HBRB constructed based on the uncertain training data and expert knowledge 6.6 Classification error rates (in %) for considered methods with different noise levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Comparison of the estimated and tested optimal λ as well as their corresponding classification error rates (in %) with different noise levels . . . . . . . . . . xx List of Figures 1.1 One-to-one correspondence between mass (m), belief (Bel) and plausibility (P l) functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graphical example of mass, belief and plausibility functions . . . . . . . . . . 11 2.1 A three-class classification example . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2 An example of the fuzzy partition of a two-dimensional pattern space by fuzzy grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1 Illustration of dependence between edited training samples . . . . . . . . . . . 48 3.2 Classification results for different combination rules and different k edit values with values of k ranging from 1 to 25 . . . . . . . . . . . . . . . . . . . . . . . Classification results of the EEkNN method for different k edit and k . . . . . . Classification results for synthetic data sets with different overlapping ratios (SEkNN: modified simple editing kNN, FEkNN: fuzzy editing kNN, EkNN: evidential kNN, EEkNN: evidential editing kNN) . . . . . . . . . . . . . . . . Classification results of different methods for benchmark data sets . . . . . . . 55 4.1 A three-class classification example . . . . . . . . . . . . . . . . . . . . . . . . Fusion scheme of the PkNN classifiers in the framework of belief functions . . Classification accuracy rate (in %) for synthetic data with different training set sizes (L2-kNN: kNN based on L2 distance metric, GW-kNN: kNN based on GW distance metric, CDW-kNN: kNN based on CDW distance metric, PkNN-BF: kNN based on pairwise distance metric and the belief function theory) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Classification results of test sample y for different methods with 60 training samples (with '•' for class A, ' ' for class B and '△' for class C, respectively) Belief rule-based classification system . . . . . . . . . . . . . . . . . . . . . . . Classification accuracy rate (in %) of our proposed BRBCS in comparison with other methods at different class noise levels (The symbol ′ △ ′ denotes the FRBCS, ′ • ′ denotes the C4.5, ′ * ′ denotes the BagC4.5, and ′ ′ denotes the BRBCS.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3 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.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hybrid belief rule-based classification system . . . . . . . . . . . . . . . . . . 6.2 An example of the fuzzy regions covered by the DBRB and KBRB for a twodimensional feature space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Distributions of the three features conditioned on the class . . . . . . . . . . . 6.4 Fuzzification of the feature space . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Classification error rate of the HBRBCS with the adjustment factor λ ranging from 0 to 1 under different noise levels . . . . . . . . . . . . . . . . . . . . . . xxii Introduction Data classification, also called supervised learning, is the process of predicting the class label of a new instance based on a set of labeled samples. It occurs in a wide range of human

Definition 1 . 1 (

 11 mass function). A mass function, over a frame of discernment Ω, is a mapping function m: 2 Ω → [0, 1], such that m(∅) = 0 and A⊆Ω m(A) = 1. (1.1) Elements A ⊆ Ω having m(A) > 0 are called the focal sets of the mass function m.

Figure 1 . 1 :Exemple 1 . 2 .

 1112 Figure 1.1: One-to-one correspondence between mass (m), belief (Bel) and plausibility (P l) functions

Figure 1 . 2 :

 12 Figure 1.2: Graphical example of mass, belief and plausibility functions

Definition 1 . 3 (

 13 Jousselme's distance). Let m 1 and m 2 be two mass functions defined over the same frame of discernment Ω, containing n mutually exclusive and exhaustive hypotheses. The Jousselme's distance between m 1 and m 2 is

  , and let m be a mass function on Ω with focal sets A 1 , A 2 , • • • , A n , and Ω. The weight function associated to m is

  ) for all a, b ∈ [0, 1], where s is a positive parameter. For any s ∈ (0, 1), a⊤ s b returns a value between ab and a ∧ b. Definition 1.6 (triangular norm-based rules). Let m 1 and m 2 be two non-dogmatic mass functions defined over the same frame of discernment Ω, and w 1 and w 2 the associated weight functions from their respective canonical decompositions. Their combination using the Frank's family of triangular norm-based rules is defined as

  mass function can be interpreted as a conditional mass function m Ω [B] obtained by conditioning some unknown mass function m Ω by B. However, there will usually exist several mass functions m Ω verifying this property. In the following, a deconditioning operation is introduced to give the least committed mass function, whose conditioning on B yields m Ω [B] [101]. Definition 1.8 (deconditioning operation). Let m Ω [B] be a mass function obtained by conditioning some unknown mass function m Ω by B ⊆ Ω. The deconditioning of m Ω [B]

1 . 2 . 3 . 4 .

 1234 Imprecise information in overlapping regions: For most real-world classification problems, the patterns from different classes usually partly overlap. Though the training samples in overlapping regions are assigned with precise labels, they actually cannot be seen as truly representatives of their corresponding clusters. Incomplete training data set: Incomplete training data set refers to cases where the training data set is non-exhaustive. Generally, if the training data set is exhaustive enough to characterize the real class-conditional probability distributions, data classification is easy to do for any classifier. However, in small data set situations, the ideal behaviors of many traditional classifiers degrade dramatically. Unreliable training data set: Unreliable training data set refers to cases where the training data have noisy class labels or feature values. The class noise, also known as labeling error, occurs when a sample is assigned to an incorrect class. 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. Partial training data and expert knowledge: In some real-world classification problems, both partial training data collected by sensors and partial expert knowledge

Exemple 2 . 1 .

 21

Figure 2 .

 2 1 illustrates a simple three-class classification problem, where the data in each class are uniformly distributed. (x 1 , A), (x 2 , B) and (x 3 , C) are twodimensional data points in training set T . y 1 and y 2 are the query data to be classified. Considering the classification of data y 1 between Class A and Class B, when calculating the distance of y 1 to x 1 and x 2 , intuitively, to avoid classifying it as Class B mistakenly, feature X should be assigned a larger weight. However, when classifying data y 2 as Class B or Class C, feature Y should be assigned a larger weight to determine the distance of y 2 to x 2 and x 3 . However, as indicated in Eq. (2.9), the CDW distance is only relevant to the class labels of the training samples, it lacks the flexibility of designing local feature weights for query patterns from different classes.

Figure 2 . 2 :

 22 Figure 2.2: An example of the fuzzy partition of a two-dimensional pattern space by fuzzy grids

  [START_REF] Zhou | A sequential learning algorithm for online constructing belief-rule-based systems[END_REF] proposed to build an initial rule base from the available expert knowledge, and then to optimize the rule base by adding or pruning rules based on training data. In[START_REF] Tang | Target classification using knowledge-based probabilistic model[END_REF], Tang et al. developed a knowledge-based naive Bayes classifier, which uses training data to estimate the involved conditional probabilities. Later, in[START_REF] Tang | Adaptive fuzzy rule-based classification system integrating both expert knowledge and data[END_REF], they proposed another similar method, which builds a fuzzy rule-based system based on expert knowledge and then uses training data to optimize the involved fuzzy membership functions. In essence, these methods follow the same idea that first building a base model from expert knowledge and then optimizing this model based on training data. However, one major disadvantage of this idea is that the weights of training data and expert knowledge cannot be adjusted according to the qualities of these two types of information. To overcome this limitation, we intend to address the hybrid classification problem with a different idea. That is, to build a data-driven model and a knowledge-driven model independently, and then to combine them into an adaptive hybrid classification model by taking into account their weights.In order to integrate training data and expert knowledge for classification, we need to find a common representation model that can make use of both the two types of information. The IF-THEN rule is a good representation model because, on the one hand, as reviewed in the previous section, the IF-THEN rules can be learnt from training data and, on the other hand, expert knowledge is also easily coded into IF-THEN rules. Many rule-based systems have been proposed to deal with the classification problems using either training data or expert knowledge[START_REF] Ishibuchi | Distributed representation of fuzzy rules and its application to pattern classification[END_REF][START_REF] Quteishat | A modified fuzzy minĺcmax neural network with a genetic-algorithm-based rule extractor for pattern classification[END_REF][START_REF] Sanz | A genetic tuning to improve the performance of fuzzy rule-based classification systems with interval-valued fuzzy sets: degree of ignorance and lateral position[END_REF][START_REF] Tsang | A systematic fuzzy rule based approach for fault classification in transmission lines[END_REF]. Therefore, it is a natural way to combine partial training data and expert knowledge based on the rule-based systems.

2. 5 Conclusion 3

 53 Different types of uncertainty may exist in real-world data classification problems. In this chapter, we discussed four critical issues concerning the uncertainty in data classification field, i.e., imprecise information in overlapping regions, incomplete training data set, unreliable training data set, and incomplete training data and expert knowledge, which are the targets of this thesis. In the following four chapters, we will solve the above uncertain data classification problems in the framework of belief functions based on two classification approaches: nearest-neighbor-based classification and rule-based classification. Part II Nearest-neighbor-based classification This part focuses on classification of uncertain data using nearest-neighbor-based approaches. Chapter 3 focuses on improving the performance of the kNN rule for cases in which patterns from different classes overlap strongly. An evidential editing version of the kNN rule is developed based on the theory of belief functions in order to well model the imprecise information for those samples in overlapping regions. Chapter 4 concerns the classification problems based on incomplete training data sets. A polychotomous classification problem is solved by combining a group of locally learned pairwise kNN classifiers in the framework of belief functions to deal with the uncertain output information.ChapterEvidential editing k-nearest neighbor classifierOne of the difficulties that arise when using the k-nearest neighbor rule is that each of the labeled training samples is given equal importance in deciding the class of the query pattern to be classified, regardless of their typicality. In this chapter, the theory of belief functions is introduced into the k-nearest neighbor rule to develop an evidential editing version of this algorithm. An evidential editing procedure is proposed to reassign the original training samples with new labels represented by an evidential membership structure. With the introduction of the evidential editing procedure, the imprecise information in overlapping regions can be well characterized. After the evidential editing, a classification procedure is developed to handle the more general situation in which the edited training samples are assigned dependent evidential labels.In this chapter, we first describe in Section 3.1 the background and motivations. The details of the proposed evidential editing k-nearest neighbor classifier are presented in Section 3.2. Four experiments are performed in Section 3.3 to evaluate the performance of the proposed method. Finally, Section 3.4 concludes this chapter.

  theory of belief functions has already been used in the kNN rule[START_REF] Denoeux | A k-nearest neighbor classification rule 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][START_REF] Zouhal | An evidence-theoretic k-NN rule with parameter optimization[END_REF]. However, these methods mainly focus on modeling the uncertainty in the classification process, none of them considers any editing procedure and the original training set is used to make classification.In this chapter, an evidential editing k-nearest neighbor (EEkNN) is proposed based on the theory of belief functions. The proposed EEkNN classifier contains two stages: evidential editing and classification. First, an evidential editing procedure reassigns the original training samples with new labels represented by an evidential membership structure. Compared with the fuzzy membership used in fuzzy editing, the evidential labels provide more expressiveness to characterize the imprecision for those samples in overlapping regions. After the evidential editing procedure, a classification procedure is developed to classify a query pattern based on the edited training samples.

Figure 3 . 4 Figure 3 . 1 :

 3431 Figure 3.1: Illustration of dependence between edited training samples

  the indices of the k nearest neighbors of y in T ′ . The selection of parameter s depends on the potential dependence degrees of the edited samples. In practice, we can use the cross-validation to search for the optimal t-norms based combination rule. For making decisions based on the above combined mass function m, the pignistic probability BetP shown in Eq. (1.26) is used and the query pattern y is assigned to the class with the maximum pignistic probability.

  This experiment was designed to evaluate the combination rules used in the proposed EEkNN method. A two-dimensional three-class classification problem was considered. The following class-conditional normal distributions were assumed:Class A: µ A = (6, 6) T , Σ A = 4I; Class B: µ B = (14, 6) T , Σ B = 4I; Class C: µ C = (14, 14) T , Σ C = 4I.A training set of 150 samples and a test set of 3000 samples were generated from the above distributions using equal prior probabilities. For each case, 30 trials were performed with 30 independent training sets. The average test classification rate over the 30 trials was calculated. In the preprocessing stage, k edit = 3, 9, 15, 21 were selected. For classification, values of k ranging from 1 to 25 have been investigated. The t-norms based combination rules (TR) with parameter s ranging from 0 to 1 have been evaluated. Note that the cautious rule (CR) is retrieved when s = 0, and the Dempster's rule (DR) is retrieved when s = 1. k edit = 21

Figure 3 . 2 : 25 Figure 3 .

 32253 Figure 3.2: Classification results for different combination rules and different k edit values with values of k ranging from 1 to 25

Figure 3 . 3 :

 33 Figure 3.3: Classification results of the EEkNN method for different k edit and k

Case 1 Case 2 Case 3

 123 This experiment was designed to compare the proposed EEkNN with other nearest-neighborbased methods using synthetic data sets with different class overlapping ratios, defined as the number of training samples in the overlapping region divided by the total number of training samples. A training sample x i is considered to be in the overlapping region if its corresponding maximum plausibility P l max i after evidential editing is less than a set upper bound P l * , namely, P l * = 0.9. A two-dimensional three-class classification problem was considered. The following class-conditional normal distributions were assumed. For comparisons, we changed the variance of each distribution to control the class overlapping ratio. Class A: µ A = (6, 6) T , Σ A = 3I; Class B: µ B = (14, 6) T , Σ B = 3I; Class C: µ C = (14, 14) T , Σ C = 3I. Overlapping ratio ρ = 6.67% Class A: µ A = (6, 6) T , Σ A = 4I; Class B: µ B = (14, 6) T , Σ B = 4I; Class C: µ C = (14, 14) T , Σ C = 4I. Overlapping ratio ρ = 10.00% Class A: µ A = (6, 6) T , Σ A = 5I; Class B: µ B = (14, 6) T , Σ B = 5I; Class C: µ C = (14, 14) T , Σ C = 5I. Overlapping ratio ρ = 21.33%A training set of 150 samples and a test set of 3000 samples were generated from the above distributions using equal prior probabilities. For each case, 30 trials were performed with 30 independent training sets. The average classification accuracy and the corresponding 95% confidence interval 1 were calculated. For each trial, the best values for the parameters k edit and s in the EEkNN method were determined in the sets {3, 6, 9, 12, 15, 18, 21, 24} and {1, 10 -1 , 10 -2 , 10 -3 , 10 -4 , 10 -5 , 0}, respectively, by cross-validation. For all of the considered method, values of k ranging from 1 to 25 have been investigated.

Figure 3 .

 3 Figure 3.4 shows the classification results for synthetic data sets with different overlapping ratios. It can be seen that, for the three cases, the EEkNN method provides better classification performance than other nearest-neighbor-based methods. With the increase of the class overlapping ratio, the performance improvement becomes more important.

  being the classification accuracy rates for the Nt trials.

  Case 3: ρ = 21.33%

Figure 3 . 4 :

 34 Figure 3.4: Classification results for synthetic data sets with different overlapping ratios (SEkNN: modified simple editing kNN, FEkNN: fuzzy editing kNN, EkNN: evidential kNN, EEkNN: evidential editing kNN)

Figure 3 .

 3 Figure 3.5 shows the classification results of different methods for benchmark data sets.

Figure 3 . 5 :

 35 Figure 3.5: Classification results of different methods for benchmark data sets

Remark 4 . 1 .

 41 Compared with the above mentioned distance metrics, the PW distance metric provides greater flexibility to design the feature weights so that the local specificities in feature space can be well characterized. We study the three-class classification problem illustrated in Example 2.1 again. In Figure 4.1, using the PW distance metric, to discriminate Class B and Class A, λ X B,A (the two subscripts denote the class labels, the superscript denotes the feature index) can take much larger value than λ Y B,A . In contrast, one can assign smaller value to λ X B,C than to λ Y B,C to discriminate Class B and Class C.

Figure 4 . 1 :

 41 Figure 4.1: A three-class classification example

Figure 4 .

 4 2 shows the evidential fusion scheme of the PkNN classifiers in the framework of belief functions.

Figure 4 . 2 :

 42 Figure 4.2: Fusion scheme of the PkNN classifiers in the framework of belief functions

Remark 4 . 2 .

 42 As can be seen from above, the fusion process of PkNN classifiers is quite time-efficient. Therefore, when classifying a query pattern, the time is mainly consumed in the classification process of multiple PkNN classifiers. Even though the number of PkNN classifiers is of M 2 order (with M (M -1)/2 classifiers), each classifier only uses the training samples from the corresponding classes (about 2N/M samples averagely). Hence

Figure 4 .

 4 [START_REF] Akbarzadeh-Totonchi | A hierarchical fuzzy rule-based approach to aphasia diagnosis[END_REF] shows the classification accuracy of the considered methods with different training set sizes. As can be seen from the results, the GW-kNN classifier shows similar performance as compared to the original L2-kNN classifier, because the learned GW distance metric has almost the same weights for the two involved features.The CDW-kNN classifier, which is based on the CDW distance metric, is just slightly

Figure 4 . 3 :

 43 Figure 4.3: Classification accuracy rate (in %) for synthetic data with different training set sizes (L2-kNN: kNN based on L2 distance metric, GW-kNN: kNN based on GW distance metric, CDW-kNN: kNN based on CDW distance metric, PkNN-BF: kNN based on pairwise distance metric and the belief function theory)

Figure 4 . 4 :

 44 Figure 4.4: Classification results of test sample y for different methods with 60 training samples (with '•' for class A, ' ' for class B and '△' for class C, respectively)

Figure 5 . 1 :

 51 Figure 5.1: Belief rule-based classification system

  1 describe the importance of different features in determining the consequent class. Remark 5.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, the belief structure makes the rule more appropriate to characterize the uncertain information. In generating each rule, only limited training samples are available, and each training sample 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 ignorance about the class label induced by the limited training samples. b) With the introduction of feature weights, the importance of different features to the consequence can be well characterized, which is closer to reality.

Remark 5 . 2 .

 52 In the classical FRBCS reviewed in Section 2.4.1, the consequence of each rule is only determined by the class label of the training sample 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 samples assigned to the corresponding antecedent fuzzy region. Thus, it can effectively reduce the adverse effects of some noisy training samples.

  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 • 2 BagC4. 5 • 3 Figure 5 . 2

 53525352 Figure 5.2 shows the classification accuracy 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, Table5.7 gives the RLA of our proposed BRBCS in comparison with other

Figure 5 . 2 :Figure 5 . 3

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

  In this section, a time complexity analysis of the proposed BRBCS was 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 real-world 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 Table5.1 were considered for evaluation. Three different numbers of partitions, C = 3, 5, 7, were tested, and the 5-CV model was used to calculate the average runtime. The numerical experiments were executed by MATLAB 7.12 on an HP EliteBook

  the belief rule structure, a data-driven belief rule base (DBRB) and a knowledge-driven belief rule base (KBRB) are learnt from uncertain training data and expert knowledge, respectively. A fusion algorithm is proposed to combine the DBRB and KBRB to obtain an optimal hybrid belief rule base (HBRB), based on which a query pattern is classified by taking into the uncertain information from both training data and expert knowledge.

Figure 6 . 2 :

 62 Figure 6.2: An example of the fuzzy regions covered by the DBRB and KBRB for a two-dimensional feature space

Figure 6 . 3 :

 63 Figure 6.3: Distributions of the three features conditioned on the class

Figure 6 . 4 :

 64 Figure 6.4: Fuzzification of the feature space

9 0. 69 MStep 3 : 1 :e 2 :e 3 :

 693123 ∧ M ∧ M {(ω 1 , 0), (ω 2 , 0.8998), (ω 3 , 0)} 10 0.63 H ∧ L ∧ L {(ω 1 , 0.2007), (ω 2 , 0), (ω 3 , 0.7591)} 11 0.43 H ∧ M ∧ L {(ω 1 , 0.1171), (ω 2 , 0), (ω 3 , 0.8295)} 12 0.36 H ∧ M ∧ M {(ω 1 , 0), (ω 2 , 0), (ω 3 , 0.6657)} Construction of KBRBSuppose the following three pieces of expert knowledge e j , j = 1, 2, • • • , 3, were obtained by asking the experts to assign the fuzzy regions to each target class and to give the corresponding certainty grades:e If x 1 is {M } and x 2 is {L} and x 3 is {M, H}, then consequence is ω 1 , with certainty grade 0.9;If x 1 is {L, M } and x 2 is {L, M } and x 3 is {L, M }, then consequence is ω 2 ,with certainty grade 0.7; If x 1 is {M, H} and x 2 is {L, M, H} and x 3 is {L}, then consequence is ω 3 , with certainty grade 0.8.

e 2 70 L

 270 {L ∧ L ∧ L}, {L ∧ M ∧ L}, {L ∧ L ∧ M }, {L ∧ M ∧ M }, {M ∧ L ∧ L}, {M ∧ M ∧ L}, {M ∧ L ∧ M}, {M ∧ M ∧ M } e 3 {M ∧ L ∧ L}, {M ∧ M ∧ L}, {M ∧ H ∧ L}, {H ∧ L ∧ L}, {H ∧ M ∧ L}, {H ∧ H ∧ L} Table 6.4: KBRB constructed based on the expert knowledge Rule ∧ L ∧ L {(ω 1 , 0), (ω 2 , 1), (ω 3 , 0)} 2 0.70 L ∧ L ∧ M {(ω 1 , 0), (ω 2 , 1), (ω 3 , 0)} 3 0.70 L ∧ M ∧ L {(ω 1 , 0), (ω 2 , 1), (ω 3 , 0)} 4 0.70 L ∧ M ∧ M {(ω 1 , 0), (ω 2 , 1), (ω 3 , 0)} 5 1.00 M ∧ L ∧ L {(ω 1 , 0), (ω 2 , 0.3182), (ω 3 , 0.5455)} 6 1.00 M ∧ L ∧ M {(ω 1 , 0.7297), (ω 2 , 0.1892), (ω 3 , 0)} 7 0.90 M ∧ L ∧ H {(ω 1 , 1), (ω 2 , 0), (ω 3 , 0)} 8 1.00 M ∧ M ∧ L {(ω 1 , 0), (ω 2 , 0.3182), (ω 3 , 0.5455)} 9 0.70 M ∧ M ∧ M {(ω 1 , 0), (ω 2 , 1), (ω 3 , 0)} 10 0.80 M ∧ H ∧ L {(ω 1 , 0), (ω 2 , 0), (ω 3 , 1)} 11 0.80 H ∧ L ∧ L {(ω 1 , 0), (ω 2 , 0), (ω 3 , 1)} 12 0.80 H ∧ M ∧ L {(ω 1 ,0), (ω 2 , 0), (ω 3 , 1)} 13 0.80 H ∧ H ∧ L {(ω 1 , 0), (ω 2 , 0), (ω 3 , 1)}

Table 6 . 5 : 52 L 69 L 45 L 60 L 93 Ma

 655269456093 HBRB constructed based on the uncertain training data and expert knowledge∧ L ∧ L {(ω 1 , 0), (ω 2 , 0.3853), (ω 3 , 0.2833)} ∧ L ∧ M {(ω 1 , 0.0022), (ω 2 , 0.7346), (ω 3 , 0.0614)} ∧ M ∧ L {(ω 1 , 0), (ω 2 , 0.2146), (ω 3 , 0.2053)} ∧ M ∧ M {(ω 1 , 0), (ω 2 , 0.6263), (ω 3 , ∧ L ∧ L {(ω 1 , 0), (ω 2 , 0.0930), (ω 3 , 0.6786)} 6 (R 6 D ,R 6 K ) 1.00 M ∧ L ∧ M {(ω 1 , 0.6873), (ω 2 , 0.0918), (ω 3 , 0)} 7 (R 7 D ,R 7 K ) 0.63 M ∧ L ∧ H {(ω 1 , 0.7976), (ω 2 , 0.0025), (ω 3 , 0.0018)} 8 (R 8 D ,R 8 K ) 0.59 M ∧ M ∧ L {(ω 1 , 0), (ω 2 , 0.5153), (ω 3 , 0.2084)} 9 (R 9 D ,R 9 K ) 0.69 M ∧ M ∧ M {(ω 1 , 0), (ω 2 , 0.8028), (ω 3 , 0)} 10 (--,R10K ) 0.22 M ∧ H ∧ L {(ω 1 , 0), (ω 2 , 0), (ω 3 , 1)} 11 (R 10 D ,R11K ) 0.68 H ∧ L ∧ L {(ω 1 , 0.0004), (ω 2 , 0), (ω 3 , 0.8024)} 12 (R 11 D ,R12K ) 0.53 H ∧ M ∧ L {(ω 1 , 0.6039), (ω 2 , 0), (ω 3 , 0.7052)} 13 (R 12 D ,--) 0.26 H ∧ M ∧ M {(ω 1 , 0), (ω 2 , 0), (ω 3 , 0.6657)} 14 (--,R13K ) 0.22 H ∧ H ∧ L {(ω 1 , 0), (ω 2 , 0), (ω 3 ,1)} The corresponding rules in DBRB and KBRB with the same antecedent parts are shown in brackets.

Table 6 .

 6 6 shows the classification error rates for different methods with different noise levels. With the increase of the class noise in the training data set, the performance of all of the three data-based classifiers C4.5, FRBCS, and DBRBCS, decrease, whereas the DBRBCS shows more robust to class noise due to the utilized belief rule structure and belief reasoning method. The KBRBCS, which classifies query patterns only based on the expert knowledge, always yields a moderate performance. Interestingly, the HBRBCS outperforms both the DBRBCS and the KBRBCS with any noise level. The reason is that, on the one hand, the fused HBRB covers more fuzzy regions than do the partial DBRB and KBRB and, on the other hand, for the overlapping fuzzy regions, thanks to combination, the rules in HBRB reduced the potential unreliability existing in the corresponding rules of DBRB or KBRB. Besides, by comparing the two hybrid classifiers AFRBCS and HBRBCS, it can be seen that the proposed HBRBCS yields better performance, especially for cases with high data noise levels. It is because in HBRBCS the weights of training data and expert knowledge are adjusted adaptively according to the qualities of these two types of information. Whereas, the AFRBCS always uses training data to update the knowledgebased model, no matter the available training data set is reliable or not.

k≥KP

  (k, N, p) = (1 -A)/2 and k≤K P (k, N, p) = (1 -A)/2, where P (k, N, p) is the binomial distribution, N is the number of test patterns, K is the number of patterns misclassified, A is the confidence level, and [p, p] is the confidence interval.

Conclusions

  This thesis has tackled uncertain data classification problems in nearest-neighbor-based and rule-based approaches, by introducing belief functions to model the uncertainty in training data or expert knowledge. The following four main contributions were exposed in this thesis.First, in order to model the imprecise information in class overlapping regions, an evidential editing procedure was designed to reassign the original training samples with new labels represented by an evidential membership structure. Based on the evidential editing procedure, we have developed an evidential editing version of the k-nearest neighbor rule (EEkNN). Experiments have shown that the proposed EEkNN classifier can achieve better performance than other considered nearest-neighbor-based methods, especially for data sets with high overlapping ratios. In addition, the proposed EEkNN classifier is not too sensitive to the value of k, which is very useful for those time or space-critical applications in which only a small value of k is permitted in the classification process.Second, in order to improve the performance of the kNN-based classifier based on incomplete training data set, we have designed an evidential fusion scheme for combining a group of pairwise kNN classifiers in the framework of belief functions (PkNN-BF). Each pairwise kNN classifier was locally learned based on a pairwise distance metric, which provides greater flexibility to design the feature weights so that the local specificities in feature space can be well characterized. From the reported experiment results, we can conclude that the proposed PkNN-BF classifier can successfully improve the performance for those tasks with high dimension and small sample size, in which cases the training data set is not rich enough to well characterize the real class-conditional probability distributions.Third, we have extended the traditional fuzzy rule-based classification system in the framework of belief functions and developed a belief rule-based classification system (BR-BCS) to address uncertain information in complex classification problems. The two components of the proposed BRBCS, i.e., the belief rule base and the belief reasoning method, have been designed specifically by taking into account the possible pattern noise in many real-world data sets. The delivered experiments have shown that the proposed BRBCS can get better classification accuracy and robustness than other rule-based methods for a variety of real-world classification problems. This allows us to conclude that the introduction of belief functions have improved the behavior of the rule-based classification system. Fourth, a hybrid belief rule-based classification system (HBRBCS) has been developed based on the belief rule structure in order to make use of the information from both uncertain training data and expert knowledge jointly for classification. The proposed HBR-BCS can inherit the complementary advantages from data-driven models and knowledgedriven models, and so it is quite useful for many real-world applications where both uncertain training data and expert knowledge are available. We have studied an airborne target classification problem, in which both training data collected by sensors and expert knowledge are available. The experiment results have shown that the HBRBCS can make good use of these two types of independent and complementary information and achieve better performance.

4 ,

 4 we have proposed a pairwise distance metric related to pairs of class labels. However, as reviewed in Section 2.3.3, there is another way to learn local distance metric, which is based on the geometric location of patterns. Both the geometric location and class label are important local information for the available patterns. Therefore, if we further consider the location information of patterns in our proposed pairwise distance metric, the behavior of kNN rule may be further improved. Another concern is the membership function in rule-based classification systems. For our proposed belief rule-based classification system in Chapter 5, we have used the traditional triangular membership function for the antecedent fuzzy partitions of each rule. As reviewed in Section 2.4.2, recently, there were some proposals to learn optimized membership functions with genetic algorithms. These optimized membership functions may further improve the performance of our proposed belief rule-based classification system.

Table 1 .

 1

1: Examples of mass functions defined over Ω = {ω 1 , ω 2 , ω 3 } Mass function Example Type of information Categorical

  the pignistic probability-based risk R BetP results in another decision rule: the

	maximum pignistic probability rule, which is a compromise between the maximum belief
	rule and the maximum plausibility rule. Next, let us come back to the murder example
	studied in Example 1.3 and illustrate how these three decision rules work to judge who is
	the murderer.
	Exemple 1.6 (murder continued). Remember that with the two available pieces of evidence,
	based on Dempster's rule, we obtain the following combined mass function:
	m({John}) = 0.48, m({P eter, John}) = 0.32, m({John, M ary}) = 0.12, m(Ω) = 0.08,
	concerning the murderer over the frame Ω = {P eter, John, M ary}. To judge who is the
	most likely to be the murderer based on the above combined mass function, we compute
	the belief, plausibility and pignistic probability for each suspect using Eqs. (1.2,1.3,1.26),
	as shown in Table 1.2. The belief Bel and the plausibility P l for each suspect provide
	its lower and upper probabilities to be the murderer, respectively. The pignistic probability
	BetP provides an approximate estimate between the lower and upper probabilities. For this
	example the same decision is made by maximizing Bel, P l and BetP : John is most likely
	to be the murderer.
	Table 1.2: The belief, plausibility and pignistic probability with regard to each suspect
	Suspects	Bel	P l	BetP
	Peter	0	0.4	0.19
	John	0.48	1	0.73
	Mary	0	0.2	0.09

  are mass functions defined on the frame of discernment Ω.

	Remark 3.1. The above evidential membership structure provides a more general rep-
	resentation model than the traditional crisp label or fuzzy membership. For one training
	sample x

i , if there is no imprecision among the frame of discernment Ω, the evidential membership just reduces to fuzzy membership as a special case. Further, if there is also no probability uncertainty, it finally reduces to crisp label.

Table 3 . 1 :

 31 Description of the benchmark data sets employed in the study

	Data set	# Instances	# Features	# Classes	Overlapping ratio
	Balance	625	4	3	19.23%
	Glass	214	9	6	11.04%
	Haberman	306	3	2	18.59%
	Ionosphere	214	9	6	18.29%
	Liver	345	6	2	19.19%
	Pima a	336	8	2	19.05%
	Transfusion	748	4	2	20.60%
	Vertebral	310	6	3	11.20%
	Waveform	5,000	21	3	19.60%
	Yeast	1,484	8	10	22.74%

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

Table 4 .

 4 1: Statistics of the benchmark data sets used in the experiment

	Data set	# Instances	# Features	# Classes	# Training	# Testing
	Balance	625	4	3	500	125
	Ecoli	336	7	8	200	136
	Glass	214	9	6	139	75
	Satimage	6,435	36	6	4,435	2,000
	Segment	2,310	19	7	1,400	910
	Vehicle	846	18	4	646	200
	Vertebral	310	6	3	150	160
	Waveform	5,000	21	3	3,500	1,500
	Wine	178	13	3	75	103
	Yeast	1,484	8	10	1,000	484

data sets. Additionally, for Ecoli, Glass, Satimage, Segment, Vehicle, Waveform and Wine data sets, the improvements are statistically significant than the baseline L2-kNN method, because the local distance metric plays more crucial role in determining the kNN-based

Table 4 .

 4

	2: Classification accuracy rate (in %) of our proposed method compared with other kNN-
	based methods for real data
	Data set	L2-kNN	GM-kNN	CDW-kNN	PkNN-VOTE PkNN-BF
	Balance	88.40	89.60	91.20 a	89.60	90.40
	Ecoli	84.56	84.56	85.29	87.50 b	88.24
	Glass	69.33	70.67	70.67	72.00	74.67
	Satimage	89.45	91.55	89.30	91.95	92.55
	Segment	95.05	96.15	94.51	96.70	96.92
	Vehicle	69.50	70.50	69.50	72.00	74.50
	Vertebral	83.88	83.25	84.50	83.88	85.12
	Waveform	80.67	81.07	84.07	84.53	85.93
	Wine	77.67	78.64	89.32	88.35	93.20
	Yeast	56.82	55.58	55.79	57.02	57.23

  2.1, we first describe the belief rule structure for classification applications, which extends the traditional fuzzy rule structure in the framework of belief functions. Based on the belief rule structure, we learn the belief rule base from the training data in Section 5.2.2, and then the belief reasoning method is developed in Section 5.2.3.

		Training
		Data
		Belief Rule Base
		(BRB)
	Query Pattern	Belief Reasoning Method (BRM)	Class
	Input	BRBCS	Output

Table 5 .

 5

		1: 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 5 .

 5 2: Settings of considered methods for classification accuracy evaluation

	Method		Setting
		Rule structure	Reasoning method	Membership function Partition number
	FRBCS	Eq. (2.10)	Single winner	Triangular	C = 3,5,7
	EFRBCS	Eq. (2.13)	Additive combination	Triangular	C = 3,5,7
	EBRB	Eq. (2.15)	Additive combination	Triangular	C = 3,5,7
	BRBCS	Eq. (5.1)	Belief reasoning	Triangular	C = 3,5,7

Table 5 .

 5 [START_REF] Akbarzadeh-Totonchi | A hierarchical fuzzy rule-based approach to aphasia diagnosis[END_REF] show the classification accuracy of our proposed BRBCS in comparison with other rule-based methods over the test data. The numbers in brackets represent the rank of each method. It can be seen that, the proposed BRBCS outperforms other methods for most of the data sets.

Table 5 .

 5 3: Classification accuracy rate (in %) of our proposed BRBCS in comparison with other rule-based methods for different numbers of partitions , 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.

	C = 3		C = 5		C = 7
	FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS	FRBCS EFRBCS EBRB	BRBCS

Table 5 .

 5

	4: Friedman test of the accuracy 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 5.5: Bonferroni-Dunn test of the accuracy 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 5

 5

	.6. In this experiment,

Table 5 .

 5 6: Settings of considered methods for classification robustness evaluation Method Setting

Table 5 .

 5

		7: RLA (in %) of our proposed BRBCS in comparison with other robust methods at different class noise levels
			NL = 10%			NL = 30%			NL = 50%
		FRBCS C4.5	BagC4.5 BRBCS	FRBCS C4.5	BagC4.5 BRBCS	FRBCS C4.5	BagC4.5 BRBCS
	Banknote	2.89(4)	1.40(1)	2.67(3)	1.58(2)	10.04(4) 6.40(2)	8.78(3)	5.71(1)	26.34(4) 15.13(2) 16.32(3) 14.74(1)
	Breast	6.41(4)	3.75(2)	4.93(3)	3.34(1)	17.33(2) 22.63(4) 13.87(1) 17.80(3)	32.52(4) 29.61(3) 25.14(2) 24.40(1)
	Cancer	5.19(4)	2.64(3)	2.50(2)	1.07(1)	11.27(4) 9.47(3)	8.69(2)	6.48(1)	23.12(4) 21.50(3) 11.10(1) 14.57(2)
	Diabetes	12.28(4) 5.00(3)	3.27(1)	3.86(2)	14.04(4) 11.67(3) 9.97(2)	7.74(1)	15.79(3) 38.33(4) 14.50(2) 10.28(1)
	Ecoli	6.93(4)	3.77(2)	4.07(3)	1.69(1)	16.71(2) 37.74(4) 18.34(3) 8.47(1)	22.41(2) 45.28(4) 29.83(3) 15.24(1)
	Glass	5.48(2)	9.22(3)	9.85(4)	4.08(1)	16.45(3) 20.07(4) 14.98(2) 8.26(1)	26.05(3) 29.56(4) 18.99(2) 17.78(1)
	Haberman	1.47(1)	3.34(3)	4.85(4)	2.72(2)	13.98(3) 8.27(1)	17.57(4) 11.77(2)	24.41(4) 19.25(2) 22.61(3) 16.29(1)
	Iris	3.11(2)	4.20(4)	3.53(3)	2.89(1)	6.57(2)	19.23(4) 10.03(3) 1.73(1)	23.88(3) 38.46(4) 17.30(2) 13.50(1)
	Knowledge	3.85(2)	7.04(4)	5.66(3)	3.47(1)	10.45(3) 9.86(2)	11.05(4) 8.53(1)	22.25(3) 25.35(4) 21.70(2) 20.00(1)
	Letter	6.06(4)	3.46(3)	1.74(1)	2.26(2)	12.86(4) 10.26(2) 12.03(3) 9.09(1)	28.69(4) 27.97(3) 23.31(2) 22.23(1)
	Liver	5.79(2)	8.70(3)	10.87(4) 4.51(1)	15.53(3) 15.22(2) 17.40(4) 15.03(1)	14.98(1) 17.39(3) 18.37(4) 17.04(2)
	Magic	5.22(3)	5.97(4)	3.88(2)	3.49(1)	16.40(4) 15.27(3) 9.41(1)	9.94(2)	25.46(4) 25.38(3) 13.64(1) 15.89(2)
	Pageblocks	4.09(2)	4.78(4)	3.33(1)	4.63(3)	10.99(3) 14.60(4) 9.05(2)	8.93(1)	20.04(2) 23.61(4) 20.99(3) 16.16(1)
	Pima	3.00(2)	3.67(4)	3.25(3)	2.68(1)	9.00(3)	8.26(2)	6.96(1)	12.10(4)	24.30(3) 30.28(4) 17.06(2) 12.60(1)
	Satimage	4.49(3)	5.13(4)	2.76(1)	3.16(2)	12.79(3) 17.30(4) 8.27(1)	12.10(2)	28.28(4) 25.62(3) 16.73(1) 19.40(2)
	Seeds	5.91(3)	6.72(4)	4.23(1)	5.26(2)	11.29(1) 19.03(3) 19.58(4) 15.29(2)	37.63(4) 32.77(3) 31.67(2) 28.95(1)
	Transfusion	1.71(3)	0.59(2)	0.25(1)	3.71(4)	6.00(2)	8.89(3)	10.85(4) 4.95(1)	49.91(4) 47.01(3) 12.68(2) 8.24(1)
	Vehicle	8.10(4)	3.66(3)	2.88(1)	3.26(2)	17.67(3) 16.52(2) 18.62(4) 12.70(1)	28.76(4) 25.07(2) 28.20(3) 23.85(1)
	Vertebral	7.45(4)	6.09(3)	4.32(2)	1.11(1)	20.00(4) 19.34(3) 14.68(2) 10.78(1)	37.26(4) 32.54(3) 30.39(2) 22.60(1)
	Yeast	6.14(4)	0.83(1)	4.10(2)	4.22(3)	17.34(4) 12.03(3) 11.30(2) 9.91(1)	24.41(3) 27.95(4) 15.89(2) 13.33(1)
	Av. rank	3.05	3.00	2.25	1.70	3.05	2.90	2.60	1.45	3.35	3.25	2.20	1.20

Table 5 .

 5 8: 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 5.9: 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) a 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

a k is the number of considered methods.

Table 5 .

 5 10: RLA (in %) of our proposed BRBCS in comparison with other robust methods at different feature noise levels

			NL = 10%			NL = 30%			NL = 50%
		FRBCS C4.5	BagC4.5 BRBCS	FRBCS C4.5	BagC4.5 BRBCS	FRBCS C4.5	BagC4.5 BRBCS
	Banknote	3.44(3)	2.71(2)	4.06(4)	1.05(1)	8.79(4)	8.53(3)	7.02(2)	4.62(1)	12.48(3) 15.60(4) 11.40(2) 8.27(1)
	Breast	5.34(4)	4.48(3)	3.33(2)	2.26(1)	12.34(1) 16.79(3) 20.00(4) 13.91(2)	20.46(2) 21.42(3) 26.67(4) 17.99(1)
	Cancer	4.91(3)	5.52(4)	1.17(1)	4.38(2)	8.81(3)	9.63(4)	7.95(1)	8.38(2)	16.22(4) 12.78(2) 15.94(3) 12.44(1)
	Diabetes	0.36(1)	6.67(4)	3.92(3)	1.15(2)	7.20(1)	12.23(4) 11.03(3) 9.39(2)	14.04(4) 12.23(2) 13.27(3) 9.39(1)
	Ecoli	8.62(3)	9.44(4)	4.69(2)	2.82(1)	13.78(4) 13.21(3) 10.72(2) 5.09(1)	24.14(4) 17.63(3) 17.35(2) 10.18(1)
	Glass	5.48(4)	1.08(1)	3.07(3)	1.30(2)	8.23(3)	10.58(4) 7.70(2)	4.08(1)	15.08(3) 16.00(4) 14.03(2) 7.53(1)
	Haberman	0.38(1)	6.22(4)	0.79(2)	1.59(3)	11.19(4) 10.15(3) 7.56(2)	7.35(1)	20.62(4) 18.20(3) 11.28(1) 12.90(2)
	Iris	0.70(1)	1.77(3)	3.45(4)	1.39(2)	2.45(2)	4.90(3)	5.52(4)	2.08(1)	3.85(2)	9.09(4)	7.59(3)	2.78(1)
	Knowledge	3.85(3)	4.69(4)	2.14(1)	2.66(2)	9.26(2)	9.40(3)	9.89(4)	7.99(1)	14.84(1) 16.73(3) 17.15(4) 15.13(2)
	Letter	4.00(4)	0.73(1)	2.64(2)	3.31(3)	9.34(3)	8.58(2)	9.44(4)	7.28(1)	16.21(4) 14.36(3) 13.35(2) 11.56(1)
	Liver	0.33(1)	2.17(4)	1.55(3)	0.67(2)	5.79(1)	15.22(3) 15.51(4) 7.72(2)	12.68(1) 26.09(4) 20.22(3) 15.68(2)
	Magic	3.55(4)	1.77(3)	1.30(2)	1.01(1)	6.82(3)	9.63(4)	3.58(1)	5.27(2)	12.88(2) 13.63(4) 13.45(3) 12.72(1)
	Pageblocks	3.86(3)	2.99(2)	4.55(4)	2.73(1)	10.22(3) 12.43(4) 9.48(2)	7.07(1)	14.07(2) 18.98(4) 15.24(3) 11.15(1)
	Pima	1.00(1)	3.67(3)	5.22(4)	1.14(2)	4.18(1)	9.28(2)	12.28(4) 9.89(3)	10.70(1) 12.09(2) 19.50(4) 16.17(3)
	Satimage	4.85(3)	5.20(4)	0.90(1)	1.02(2)	7.63(3)	11.01(4) 4.74(1)	6.14(2)	14.93(3) 16.03(4) 9.91(1)	10.41(2)
	Seeds	4.30(4)	4.08(3)	3.04(2)	2.63(1)	8.60(3)	12.70(4) 5.66(1)	5.98(2)	13.28(3) 16.79(4) 11.92(2) 10.84(1)
	Transfusion	1.84(2)	0.85(1)	5.71(4)	5.35(3)	7.05(3)	4.33(1)	7.80(4)	6.19(2)	10.70(3) 9.40(2)	12.02(4) 6.19(1)
	Vehicle	4.82(3)	5.29(4)	1.30(1)	2.06(2)	10.40(4) 10.12(3) 7.99(2)	6.47(1)	20.00(4) 19.58(3) 17.34(2) 15.34(1)
	Vertebral	2.58(4)	2.13(3)	1.18(1)	1.68(2)	9.02(4)	7.35(3)	6.03(1)	6.95(2)	13.88(4) 10.61(1) 12.40(3) 12.08(2)
	Yeast	6.14(4)	5.71(3)	1.94(2)	0.22(1)	17.34(4) 12.03(3) 8.14(2)	5.52(1)	24.41(4) 20.40(3) 14.17(2) 8.20(1)
	Av. rank	2.80	3.00	2.40	1.80	2.80	3.15	2.50	1.55	2.90	3.10	2.65	1.35

Table 5 .

 5 12: Bonferroni-Dunn test of RLA for comparing BRBCS with other methods at different feature noise levels (α = 0.05) k is the number of considered methods.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.

	Noise level	Method	z value	p value	Critical value α/(k -1) a 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

a

  can effectively address the class or feature noise in the training data set. This allows us to conclude that the introduction of belief functions improves the behavior of the rule-based classification system.In some real-world pattern classification applications, both training data collected by sensors and expert knowledge may be available. In this chapter, a hybrid belief rulebased classification system (HBRBCS) is developed to make use of these two types of information jointly. The belief rule structure, which is capable of capturing fuzzy, imprecise, and incomplete causal relationships, is used as the common representation model. With

						Chapter 6
			Hybrid belief rule-based
			classification system
	Letter	16,000	1354.6	7.025	8.4E-2	3593	11.963	2.0E-1	6939	17.708	3.7E-1
	Liver	276	42.8	0.053	2.4E-3	112.6	0.078	5.7E-3	171.6	0.106	8.2E-3
	Magic	15,216	346.2	4.034	2.8E-2	1854.8	5.123	5.7E-2	4573.2	6.933	8.2E-2
	Pageblocks	4,379	55.4	0.642	4.7E-3	162	0.950	1.1E-2	286.6	1.542	2.2E-2
	Pima	615	104.6	0.149	6.9E-3	190.8	0.231	2.4E-2	340.8	0.303	3.2E-2
	Satimage	5,148	1443.2	1.857	1.6E-1	2046.6	5.997	2.5E-1	2531.6	6.730	3.1E-1
	Seeds	168	53.2	0.041	3.2E-3	96.8	0.062	5.9E-3	121.8	0.078	7.7E-3
	Transfusion	599	12.6	0.081	5.1E-4	28.6	0.112	1.1E-3	56	0.147	2.0E-3
	Vehicle	677	288.2	0.374	5.2E-2	334	0.577	8.0E-2	370.8	0.633	8.5E-2
	Vertebral	248	34	0.049	1.9E-3	93.2	0.066	4.7E-3	142.2	0.094	6.9E-3
	Yeast	1,188	96	0.312	6.6E-3	208	0.515	1.3E-2	462	0.608	2.8E-2

The two components of the proposed BRBCS, i.e., the belief rule base and the belief reasoning method, have been designed specifically by taking into account the possible pattern noise in many realworld data sets. The experiments have shown that the proposed BRBCS achieves better classification accuracy compared with other rule-based methods. Moreover, this method

  [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]

  If x 1 is A j 1 and x 2 is A j 2 and • • • and x P is A j P , then consequence is ω j , with certainty grade θ j , j = 1, 2, • • • , M,

	(6.1)
	where A j

, • • • , ω M }) pattern classification problem with P features, each piece of expert knowledge e j can be represented as Expert Knowledge e j : p is subset of fuzzy partitions {A p,1 , A p,2 , • • • , A p,np } associated with the p-th feature, p = 1, 2, • • • , P .

Table 6 .

 6

		1: Feature intervals for three airborne target classes
	Class	AveSpeed (km/h)	MaxAcc (g)	AveLength (m)
	Commercial (ω 1 )	[600, 800]	[0, 1]	[25, 65]
	Bomber (ω 2 )	[400, 700]	[0, 4]	[15, 45]
	Fighter (ω 3 )	[500, 1000]	[0, 6]	[10, 30]

Table 6 .

 6 , 0), (ω 2 , 0.1011), (ω 3 , 0.8879)} 6 1.00 M ∧ L ∧ M {(ω 1 , 0.8632), (ω 2 , 0.1245), (ω 3 , 0)} 7 0.54 M ∧ L ∧ H {(ω 1 , 0.7906), (ω 2 , 0.1047), (ω 3 , 0.1035)} 8 0.44 M ∧ M ∧ L {(ω 1 , 0), (ω 2 , 0.7084), (ω 3 , 0.2119)}

		2: DBRB constructed based on the uncertain training data
	Rule number	Rule weight	Antecedent	Consequent
	1	0.45	L ∧ L ∧ L	{(ω 1 , 0), (ω 2 , 0.3257), (ω 3 , 0.4812)}
	2	0.69	L ∧ L ∧ M	{(ω 1 , 0.0041), (ω 2 , 0.8833), (ω 3 , 0.1126)}
	3	0.36	L ∧ M ∧ L	{(ω 1 , 0), (ω 2 , 0), (ω 3 , 0.3581)}
	4	0.56	L ∧ M ∧ M	{(ω 1 , 0), (ω 2 , 0.6687), (ω 3 , 0)}
	5	0.90	M ∧ L ∧ L	{(ω 1

Table 6 .

 6 3: Fuzzy regions covered by each piece of expert knowledge

	Expert knowledge	Covered fuzzy regions
	e 1

{M ∧ L ∧ M}, {M ∧ L ∧ H}

Table 6 .

 6 6: Classification error rates (in %) for considered methods with different noise levels

	NL	C4.5	FRBCS	DBRBCS KBRBCS AFRBCS HBRBCS CI a

Table 6 .

 6 7: Comparison of the estimated and tested optimal λ as well as their corresponding classification error rates (in %) with different noise levels

	Noise Level	0%	10%	20%	30%	40%	50%
	Est. λ	0.80	0.77	0.78	0.73	0.68	0.56
	Tes. λ	0.82	0.79	0.75	0.71	0.64	0.51
	Error rate with Est. λ	17.30	17.83	18.47	18.83	19.47	20.40
	Error rate with Tes. λ	17.27	17.80	18.40	18.73	19.16	19.69

As the CDW distance metric does not satisfy the symmetry property, it is impossible to rescale the data to apply the standard Euclidean metric, so we did not visualize the result of the CDW-kNN in this illustration.

Acknowledgements

This thesis was carried out at the Heudiasyc laboratory of Université de Technologie de Compiègne (UTC) and the Information Fusion Technology laboratory of Northwestern Polytechnical University (NPU), under the support of the China Scholarship Council.

I would like to express my sincere gratitude to my supervisor at UTC, Prof. Thierry Denoeux, for his help and encouragement throughout this Ph.D. research. As an expert in the fields of belief functions and machine learning, he provided me many useful ideas for my Ph.D. work. I always discussed with him about my research and I was inspired by his recognition and handwriting recognition, the samples are collected sequentially and there exist potential relations between nearby observations. It is expected that these uncertain constraints are helpful for classification. We plan to build hidden Markov models in the framework of belief functions to model the uncertain relationship for the labels of nearby observations.

Part III

Rule-based classification

This part focuses on classification of uncertain data using rule-based approaches.

Chapter 5 focuses on improving the performance of the rule-based classification system in complex applications. We extend the traditional rule-based classification system in the framework of belief functions and develop a belief rule-based classification system to address uncertain information in complex classification problems.

Chapter 6 concerns the classification problems based on partially available training data and expert knowledge. A hybrid belief rule-based classification system is developed to make use of these two types of information jointly for classification.

Chapter 5

Belief rule-based classification system 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, because the inflexibility of the concept of the linguistic variable imposes hard restrictions on the fuzzy rule structure. In this chapter, we extend the FRBCS with a belief rule structure and develop a belief rule-based classification system (BRBCS) to address the uncertain information in complex classification problems. The two components of the proposed BRBCS, i.e., the belief rule base and the belief reasoning method, are designed specifically by taking into account the pattern noise that exists in many realworld data sets.

In this chapter, we first give an introduction about the background and motivations in Section 5.1. Then, the belief rule-based classification system is developed within the framework of belief functions in Section 5.2. Three experiments are then performed in Section 5.3 to evaluate the accuracy, robustness, and time complexity of the proposed method. Finally, Section 5.4 concludes this chapter.

Introduction

The fuzzy rule-based classification system (FRBCS), first developed by Chi et al. [START_REF] Chi | Fuzzy Algorithms with Applications to Image Processing and Pattern Recognition[END_REF], has become a popular framework for classifier design due to its capability of building a linguistic model interpretable to users. However, the FRBCS may have low 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]. Besides, the fuzzy rule structure is also not robust to pattern noise, which hinders its applications in harsh working conditions. As reviewed in Section 2.4.2, plenty of work has been done in the past two decades in order to improve the accuracy and robustness of the FRBCS.

In fact, different types of uncertainty, such as fuzziness, imprecision and incompleteness, 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. By analyzing the results presented in Table 5. [START_REF] Bonczek | Foundations of Decision Support Systems[END_REF], we can see that the runtimes for both (i.e., HBRBCS) are shown in the last column. It is interesting to note that only when the noise level is quite low (0% and 10%), the error rate of the second best method is within the corresponding confidence interval. When the class noise increases, the best HBRBCS method shows a statistically significant advantage. Therefore, the classification performance can improve greatly by making use of the complementary information from uncertain training data and expert knowledge based on belief function theory, especially when both sources of information have high uncertainty.

Parameter analysis

The adjustment factor λ plays an important role in determining the classification performance of the HBRBCS. In this section, we take an analysis for the effect of the adjustment factor λ and evaluate whether the optimization method developed in Section 6.