Thierry Denoeux

Maximum likelihood estimation from Uncertain Data in the Belief Function Framework

Keywords: Uncertain data Mining, Dempster-Shafer theory, Evidence theory, Clustering, EM Algorithm, Mixture Models. !

We consider the problem of parameter estimation in statistical models in the case where data are uncertain and represented as belief functions. The proposed method is based on the maximization of a generalized likelihood criterion, which can be interpreted as a degree of agreement between the statistical model and the uncertain observations. We propose a variant of the EM algorithm that iteratively maximizes this criterion. As an illustration, the method is applied to uncertain data clustering using finite mixture models, in the cases of categorical and continuous attributes.

INTRODUCTION

Recent years have seen a surge of interest in methods for managing and mining uncertain data [START_REF] Aggarwal | A survey of uncertain data algorithms and applications[END_REF], [START_REF] Aggarwal | Managing and Mining Uncertain Data, ser. Advances in database systems[END_REF], [START_REF] Cheng | Guest editors' introduction: Special section on mining large uncertain and probabilistic databases[END_REF]. As noted in [START_REF] Aggarwal | A survey of uncertain data algorithms and applications[END_REF], [START_REF] Cheema | Probabilistic reverse nearest neighbor queries on uncertain data[END_REF], [START_REF] Tsang | Decision trees for uncertain data[END_REF], uncertain data arise in many applications due to limitations of the underlying equipment (e.g., unreliable sensors or sensor networks), use of imputation, interpolation or extrapolation techniques (to estimate, e.g., the position of moving objects), partial or uncertain responses in surveys, etc.

In recent work on uncertain data mining, probability theory has often been adopted as a formal framework for representing data uncertainty. Typically, an object is represented as a probability density function (pdf) over the attribute space, rather than as a single point as usually assumed when uncertainty is neglected. Mining techniques that have been proposed for such data include clustering algorithms [START_REF] Kriegel | Density-based clustering of uncertain data[END_REF], [START_REF] Ngai | Efficient clustering of uncertain data[END_REF], [START_REF] Kao | Clustering uncertain data using voronoi diagrams and r-tree index[END_REF], [START_REF] Kremer | Subspace clustering for uncertain data[END_REF], density estimation techniques [START_REF] Aggarwal | On density based transforms for uncertain data mining[END_REF], outlier detection [START_REF] Aggarwal | Outlier detection with uncertain data[END_REF], support vector classification [START_REF] Bi | Support vector classification with input data uncertainty[END_REF], decision trees [START_REF] Tsang | Decision trees for uncertain data[END_REF], etc.

Beside this recent body of literature, a lot of work has been devoted to the analysis of interval-valued or fuzzy data, in which ill-known attributes are represented, respectively, by intervals [START_REF] Billard | Symbolic Data Analysis[END_REF] and possibility distributions [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF], [START_REF] Gebhardt | Fuzzy set-theoretic methods in statistics[END_REF]. As examples of techniques developed for such data, we may mention principal component analysis [START_REF] Cazes | Extension de l'analyse en composantes principales à des données de type intervalle[END_REF], [START_REF] Denoeux | Principal component analysis of fuzzy data using autoassociative neural networks[END_REF], [START_REF] Giordani | A comparison of three methods for principal component analysis of fuzzy interval data[END_REF], clustering [START_REF] Gowda | Symbolic clustering using a new similarity measure[END_REF], [START_REF] Urso | A weighted fuzzy c-means clustering model for fuzzy data[END_REF], [START_REF] Carvalho | Partitional clustering algorithms for symbolic interval data based on single adaptive distances[END_REF], linear regression [START_REF] Tanaka | Fuzzy data analysis by possibilistic linear models[END_REF], [START_REF] Coppi | Management of uncertainty in statistical reasoning: The case of regression[END_REF], [START_REF] Ferraro | A linear regression model for imprecise response[END_REF] and multidimensional scaling [START_REF] Denoeux | Multidimensional scaling of interval-valued dissimilarity data[END_REF], [START_REF] Masson | Multidimensional scaling of fuzzy dissimilarity data[END_REF], [START_REF] Hébert | Fuzzy multidimensional scaling[END_REF].

Probability distributions, intervals and possibility distributions may be seen as three instances of a more general model, in which data uncertainty is expressed by means of belief functions. The theory of belief functions, also known as Dempster-Shafer theory or Evidence theory, was developed by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], [START_REF]Upper and lower probabilities generated by a random closed interval[END_REF] and Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF], and was further elaborated by Smets [START_REF] Smets | The combination of evidence in the Transferable Belief Model[END_REF], [START_REF] Smets | The Transferable Belief Model[END_REF]. A belief function may be seen both as a generalized T. Denoeux is with Heudiasyc, Université de Technologie de Compiègne, CNRS, Compiègne, France.

set and as a non-additive measure, i.e., a generalized probability distribution. The theory of belief functions thus includes extensions of set-theoretic operations, such as intersection and union, and extensions of probabilistic operations, such as conditioning and marginalization.

Until now, the use of belief functions for representing data uncertainty has been mostly confined to classification. In [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], a k-nearest neighbor rule based on Dempster-Shafer theory was introduced. This rule makes it possible to handle partially supervised data, in which uncertain class labels are represented by belief functions (see also [START_REF] Denoeux | Handling possibilistic labels in pattern classification using evidential reasoning[END_REF], [START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF]). This rule was applied to regression problems with uncertain dependent variable in [START_REF] Petit-Renaud | Nonparametric regression analysis of uncertain and imprecise data using belief functions[END_REF]. Methods for building decision trees from partially supervised data were proposed in [START_REF] Denoeux | Induction of decision trees for partially classified data[END_REF], [START_REF] Elouedi | Belief decision trees: Theoretical foundations[END_REF], [START_REF] Trabelsi | Pruning belief decision tree methods in averaging and conjunctive approaches[END_REF]. An extension of the k-mode clustering algorithm to data with uncertain attributes was introduced in [START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF]. Following preliminary work presented in [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF] and [START_REF] Jraidi | Belief classification approach based on generalized credal EM[END_REF], C ôme et al. [START_REF] Mellouli | Learning from partially supervised data using mixture models and belief functions[END_REF] proposed another approach to the partially supervised learning problem based on mixture models and a variant of the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] maximizing a generalized likelihood criterion. A similar method was used in [START_REF] Ramasso | Contribution of belief functions to hidden Markov models with an application to fault diagnosis[END_REF] for partially supervised learning in hidden Markov models.

In this paper, we extend the approach introduced in [START_REF] Mellouli | Learning from partially supervised data using mixture models and belief functions[END_REF], by allowing uncertainty to be expressed not only on class labels in classification problems, but on any continuous or discrete attribute, in any learning problem based on a parametric statistical model 1 . The contribution of this paper is threefold:

1) We propose an uncertain data model in which data uncertainty is represented by belief functions; this model encompasses probabilistic data, intervalvalued data and fuzzy data as special cases; 2) We introduce an extension of the EM algorithm, called the evidential EM (E 2 M) algorithm, allowing 1. A preliminary version of some of the ideas introduced here was presented in [START_REF] Denoeux | Maximum likelihood from evidential data: an extension of the EM algorithm[END_REF]. The present paper is a deeply revised and extended version of this work, with several new results. us to estimate parameters in parametric statistical models based on uncertain data. 3) We demonstrate the application of this algorithm for handling partially supervised clustering problems with uncertain attributes using finite mixture models. The rest of this paper is organized as follows. The main concepts of the theory of belief functions useful for our purpose are recalled in Section 2. The proposed data model is then presented in Section 3 and the E 2 M algorithm is introduced in Section 4. Applications to clustering of discrete and continuous data using finite mixture models are presented in Section 5 and 6, respectively. Finally, Section 7 summarizes our main results and presents some research challenges and ongoing work.

THEORY OF BELIEF FUNCTIONS

This section recalls the necessary background notions related to Dempster-Shafer theory. Belief functions on discrete domains and Dempster's rule of combination are first recalled in Subsections 2.1 and 2.2, respectively. The notion of cognitive independence is then introduced in Subsection 2.3. Finally, some notions regarding the definition and manipulation of belief functions on the real line are recalled in Subsection 2.4.

Belief functions on discrete domains

Let X be a variable taking values in a finite domain Ω, called the frame of discernment. Uncertain information about X may be represented by a mass function m on Ω, defined as a function from the powerset of Ω, denoted as 2 Ω , to the interval [0, 1], such that A⊆Ω m(A) = 1.

(

) 1
Function m is said to be normalized if m(∅) = 0, a condition that will be assumed in the rest of this paper. Any subset A of Ω such that m(A) > 0 is called a focal element of m. Two special cases are of interest: 1) If m has a single focal element A, it is said to be categorical and denoted as m A . Such a mass function encodes a piece of evidence that tells us that X ∈ A, and nothing else. There is a one-toone correspondence between subsets A of Ω and categorical mass functions m A : categorical mass functions are thus equivalent to sets. 2) If all focal elements of m are singletons, then m is said to be Bayesian. There is a one-to-one correspondence between probability distributions p : Ω → [0, 1] and Bayesian mass functions m such that m({ω}) = p(ω), for all ω ∈ Ω: Bayesian mass functions are thus equivalent to probability distributions. To each normalized mass function m, we may associate belief and plausibility functions from 2 Ω to [0, 1] defined as follows:

Bel(A) = B⊆A m(B) (2a) P l(A) = B∩A =∅ m(B), (2b)
for all A ⊆ Ω. These two functions are linked by the relation P l(A) = 1 -Bel(A), for all A ⊆ Ω. Each quantity Bel(A) may be interpreted as the degree to which the evidence supports A, while P l(A) can be interpreted as an upper bound on the degree of support that could be assigned to A if more specific information became available [START_REF] Smets | The Transferable Belief Model[END_REF]. The following inequalities always hold:

Bel(A) ≤ P l(A), for all A ⊆ Ω. The function pl : Ω → [0, 1] such that pl(ω) = P l({ω}) is called the contour function associated to m.
If m is Bayesian, then functions Bel is identical to P l and it is a probability measure. Another special case of interest is that where m is consonant, i.e., its focal elements are nested. The following properties then hold [START_REF] Shafer | A mathematical theory of evidence[END_REF]:

P l(A ∪ B) = max (P l(A), P l(B)) (3a)
and

Bel(A ∩ B) = min (Bel(A), Bel(B)) , (3b)
for all A, B ⊆ Ω. The plausibility function is thus a possibility measure, and Bel is the dual necessity measure [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF], [START_REF] Dubois | Possibility Theory: An approach to computerized processing of uncertainty[END_REF]. The contour function pl is then the associated possibility distribution. Consequently, the theory of belief functions can be considered as having greater expressive power than possibility theory.

Dempster's rule

Let m 1 and m 2 be two mass functions induced by independent items of evidence. They can be combined using Dempster's rule [START_REF] Shafer | A mathematical theory of evidence[END_REF] to form a new mass function defined as:

(m 1 ⊕ m 2 )(A) = 1 1 -κ B∩C=A m 1 (B)m 2 (C) (4)
for all A ⊆ Ω, A = ∅ and (m 1 ⊕ m 2 )(∅) = 0, where

κ = B∩C=∅ m 1 (B)m 2 (C) (5)
is the degree of conflict between m 1 and m 2 . If κ = 1, there is a logical contradiction between the two pieces of evidence and they cannot be combined. Dempster's rule is commutative, associative, and it admits as neutral element the vacuous mass function defined as m(Ω) = 1.

Let us now assume that m 1 is Bayesian. Its contour function is a probability distribution p 1 defined by p 1 (ω) = m 1 ({ω}) for all ω ∈ Ω. Combining m 1 with an arbitrary mass function m 2 with contour function pl 2 yields a Bayesian mass function m 1 ⊕ m 2 with contour function p 1 ⊕ pl 2 defined by

(p 1 ⊕ pl 2 )(ω) = p 1 (ω)pl 2 (ω) ω ∈Ω p 1 (ω )pl 2 (ω ) . (6)
(We note that, without ambiguity, the same symbol ⊕ is used for mass functions and contour functions). The degree of conflict between p 1 and pl 2 is

κ = 1 - ω ∈Ω p 1 (ω )pl 2 (ω ). (7)
It is equal to one minus the mathematical expectation of pl 2 with respect to p 1 . Finally, we may also note that, if m 2 is categorical and such that m 2 (A) = 1, then p 1 ⊕ pl 2 is the probability distribution obtained by conditioning p 1 with respect to A.

Cognitive independence

Let X and Y be two variables defined on finite frames of discernment Ω X and Ω Y , and let m XY be a mass function on the product frame Ω X × Ω Y , expressing evidence on (X, Y ). The marginal mass function on Ω X is defined as

m XY ↓X (A) = C↓Ω X =A m XY (C), (8)
for all A ⊆ Ω X , where C ↓ Ω X denotes the projection of

C ⊆ Ω X × Ω Y on Ω X .
Let m X and m Y denote, respectively, the marginal mass functions on Ω X and Ω Y , and let pl X and pl Y denote the corresponding plausibility functions. Variables X and Y are said to be cognitively independent [30, page 149] with respect to m XY if the following equalities hold:

P l XY (A × B) = P l X (A)P l Y (B), (9)
for all A ⊆ Ω X and B ⊆ Ω Y . As shown by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF], this property means that new evidence on one variable does not affect our beliefs in the other variable. It is clear that cognitive independence reduces to stochastic independence when m X and m Y are Bayesian.

Belief functions on the real line

The theory of belief function can be extended to a continuous frame Ω by replacing the mass function m by a density function over a suitable family of subsets of Ω. We will only need to address the simplest case in which Ω = R (see, e.g., [START_REF]Upper and lower probabilities generated by a random closed interval[END_REF], [START_REF] Smets | Belief functions on real numbers[END_REF], [START_REF] Denoeux | Extending stochastic ordering to belief functions on the real line[END_REF]). In this case, a mass density function can be defined as a function m from the set of closed real intervals to

[0, +∞) such that m([u, v]) = f (u, v) for all u ≤ v, where f is a two-dimensional probability density function (pdf) with support in {(u, v) ∈ R 2 |u ≤ v}. Intervals [u, v] such that m([u, v]) > 0 are called focal intervals of m.
The contour function pl corresponding to m is defined by the following integral:

pl(x) = x -∞ +∞ x f (u, v)dvdu. (10)
Two important special cases of continuous belief functions are Bayesian belief function, for which focal intervals are reduced to points, and consonant belief functions, for which focal intervals are nested. The twodimensional pdf corresponding to a Bayesian belief function has the following form: f (u, v) = p(u)δ(u-v), where p is a univariate pdf and δ is the Dirac delta function. As in the discrete case, a consonant belief function on R corresponds to a possibility measure, the contour function being equal to the corresponding possibility distribution.

The reader is referred to [START_REF] Smets | Belief functions on real numbers[END_REF] for a detailed exposition of different notions pertaining to belief functions on the real line. We will only recall here the following result that will be needed in the sequel. Let m 1 be a Bayesian mass density function defined by the univariate pdf p 1 , and let m 2 be an arbitrary mass density function with contour function pl 2 . The degree of conflict between m 1 and m 2 is:

κ = 1 - +∞ -∞ p 1 (x)pl 2 (x)dx. (11)
Assuming that κ < 1, the combination of m 1 and m 2 is Bayesian with corresponding pdf:

(p 1 ⊕ pl 2 )(x) = p 1 (x)pl 2 (x) 1 -κ . ( 12
)
We note the similarity between ( 12) and ( 6)- [START_REF] Ngai | Efficient clustering of uncertain data[END_REF].

Example 1 Let φ(•; µ, σ 2 ) denote the univariate Gaussian pdf with mean µ and variance σ 2 . Let us assume that p 1 (x) = φ(x; µ 1 , σ 2 1 ) and that pl 2 is a normalized Gaussian, taking values in [0, 1]:

pl 2 (x) = φ(x; µ 2 , σ 2
2 )σ 2 √ 2π. Application of Eq. ( 12) can be shown [START_REF] Smith | Spectral Audio Signal Processing[END_REF] to give

p 1 (x)pl 2 (x) = cφ(x; µ 12 , σ 2 12 ) (13a)
with

µ 12 = µ1σ 2 2 +µ2σ 2 1 σ 2 1 +σ 2 2 , σ 2 12 = σ 2 1 σ 2 2 σ 2 1 +σ 2 2 and c = φ(µ 1 ; µ 2 , σ 2 1 + σ 2 2 )σ 2 √ 2π. (13b)
Consequently, p 1 ⊕ pl 2 is the Gaussian pdf φ •; µ 12 , σ 2 12 and the degree of conflict is

κ = 1 -φ(µ 1 ; µ 2 , σ 2 1 + σ 2 2 )σ 2 √ 2π. ( 14
)

DATA MODEL

The data model and the generalized likelihood criterion will now first be described in the discrete case in Subsection 3.1. The interpretation of the criterion will then be discussed in Subsection 3.2 and independence assumptions allowing us to simplify its expression will be introduced in Subsection 3.3. These notions will be illustrated using a simple example in Subsection 3.4. Finally, the continuous case will be addressed in Subsection 3.5.

Discrete case

To simplify the exposition, our data model will first be introduced in the discrete setting. The extension to the continuous setting will be postponed until Subsection 3.5. Let X be a discrete random vector taking values in Ω X , with probability mass function p X (•; θ) depending on an unknown parameter θ ∈ Θ. Let x denote a realization of X, referred to as the complete data. If x was perfectly observed, then the likelihood function given x would be defined as the function from Θ to [0, 1] such that:

L(θ; x) = p X (x; θ), ∀θ ∈ Θ. (15)
Let us now assume that x is not precisely observed, but it is known for sure that x ∈ A for some A ⊆ Ω X . The likelihood function given such imprecise data is now:

L(θ; A) = p X (A; θ) = x∈A p X (x; θ), ∀θ ∈ Θ. ( 16
)
More generally, our knowledge of x may be not only imprecise, but also uncertain; it can then be described by a mass function m on Ω X with focal elements A 1 , . . . , A r and corresponding masses m(A 1 ), . . . , m(A r ). To extend the likelihood function [START_REF] Cazes | Extension de l'analyse en composantes principales à des données de type intervalle[END_REF] given such uncertain data, we may simply compute the weighted sum of the terms L(θ; A i ) with coefficients m(A i ), which leads to the following expression:

L(θ; m) = r i=1 m(A i )L(θ; A i ). ( 17
)
This extension of the classical likelihood criterion will be adopted in the rest of this paper. As will be shown, this criterion has a simple interpretation in terms of conflict between the model and the observations, and it admits a simple expression under independence assumptions. Before discussing the interpretation of this criterion, it must be emphasized that, in our model, the probability mass function p X (•, θ) and the Dempster-Shafer mass function m represent two different pieces of knowledge:

• p X (•, θ) represents generic knowledge about the data generating process or, equivalently, about the underlying population; it corresponds to random uncertainty; • m represents specific knowledge (or factual evidence 2 ) about a given realization x of X; this knowledge is only partial because the observation process is imperfect; function m captures epistemic uncertainty, i.e., uncertainty due to lack of knowledge. The uncertain data m is thus not assumed to be produced by a random experiment, which is in sharp contrast with alternative approaches based on random set (see, e.g. [START_REF] Nguyen | An Introduction to Random Sets[END_REF], [START_REF] Cattaneo | Regression with imprecise data: A robust approach[END_REF]) or fuzzy random variables (see, e.g., [START_REF] Gil | Overview on the development of fuzzy random variables[END_REF], [START_REF] González-Rodríguez | Multi-sample test-based clustering for fuzzy random variables[END_REF], [START_REF] Ferraro | A linear regression model for imprecise response[END_REF]).

Interpretation

To better understand the meaning of ( 17), let us rewrite L(θ; m) as:

L(θ; m) = r i=1 m(A i ) x∈Ai p X (x; θ) (18a) = x∈Ω X p X (x; θ) Ai x m(A i ) (18b)
2. See, e.g., [START_REF] Dubois | Focusing vs. belief revision: A fundamental distinction when dealing with generic knowledge[END_REF] for discussion on the distinction between generic and specific information.

= x∈Ω X p X (x; θ)pl(x). (18c)
The likelihood L(θ; m) thus only depends on m through its associated contour function pl. For this reason, we will write indifferently L(θ; m) or L(θ; pl). By comparing (18c) with ( 7), we can see that L(θ; m) equals one minus the degree of conflict (7) between p X (•; θ) and m. Consequently, maximizing L(θ; m) with respect to θ amounts to minimizing the conflict between the parametric model and the uncertain observations. Alternatively, L(θ; m) can be regarded as a degree of agreement [START_REF] Qi | Measuring conflict and agreement between two prioritized belief bases[END_REF] between the model and the observations. We may also observe from (18c) that L(θ; m) can be alternatively defined as the mathematical expectation of pl(X), given θ:

L(θ; pl) = E θ [pl(X)] (19)
The above expression suggests an interesting link with Zadeh's notion of probability of a fuzzy event [START_REF] Zadeh | Probability measures of fuzzy events[END_REF]. Assume that m is consonant. Then, as recalled in Subsection 2.1, its contour function pl is a possibility distribution: it can thus be considered as fuzzy data. The generalized likelihood L(θ; m) is then the probability of the fuzzy data, given the parameter value θ (see [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF], [START_REF] Quost | Clustering fuzzy data using the fuzzy EM algorithm[END_REF]).

Independence assumptions

Let us assume that the random vector X can be written as X = (X 1 , . . . , X n ), where each X i is a p-dimensional random vector taking values in Ω Xi . Similarly, its realization can be written as x = (x 1 , . . . , x n ) ∈ Ω X . Two different independence assumptions can then be made: 1) Under the stochastic independence of the random variables X 1 , . . . , X n , the probability mass function p X (•; θ) of X can be decomposed as:

p X (x; θ) = n i=1 p Xi (x i ; θ), ∀x = (x 1 , . . . , x n ) ∈ Ω X (20) 2)
Under the cognitive independence of x 1 , . . . , x n with respect to m (see Subsection 2.3), we can write:

pl(x) = n i=1 pl i (x i ), ∀x = (x 1 , . . . , x n ) ∈ Ω X , (21)
where pl i is the contour function corresponding to the mass function m i obtained by marginalizing m on Ω Xi . We can remark here that the two assumptions above are totally unrelated as they are of different natures: stochastic independence of the random variables X i is an objective property of the random data generating process, whereas cognitive independence pertains to our state of knowledge about the unknown realization x of X.

If both assumptions hold, the likelihood criterion (19) can be written as a product of n terms:

L(θ; pl) = n i=1 E θ [pl i (X i )] . (22)

Illustrative example

As an illustrative example, let us consider a medical study in which n patients are taken at random from some population, in which some disease is present in proportion θ. Let X i be the Bernoulli variable such that X i = 1 if patient i has the disease, X i = 0 otherwise. Assuming the random sample X = (X 1 , . . . , X n ) to be independent and identically distributed (iid), we have

p X (x; θ) = n i=1 θ xi (1 -θ) 1-xi , (23)
for all x = (x 1 , . . . , x n ) ∈ Ω X = {0, 1} n . After the n patients have been sampled from the population, the complete data consists in the vector x = (x 1 , . . . , x n ) describing the states of the n patients. However, assume that these states are only partially known from the opinions of a physician, who provides a mass function m on Ω X . Let m i be the marginal mass function concerning the state of patient i and pl i the corresponding contour function. Using [START_REF] Tanaka | Fuzzy data analysis by possibilistic linear models[END_REF], we get the following expression for the log-likelihood given m under the cognitive independence assumption [START_REF] Carvalho | Partitional clustering algorithms for symbolic interval data based on single adaptive distances[END_REF]:

log L(θ; pl) = n i=1 log [(1 -θ)pl i (0) + θpl i (1)] . (24)

Continuous case

The above definitions can be straightforwardly transposed to the continuous case. Assume that X is a continuous random vector with pdf p X (•; θ) and let pl : Ω X → [0, 1] be the contour function of a continuous mass function m on Ω X . Similarly to (18c), the likelihood function given pl can be defined in this case from [START_REF] Gowda | Symbolic clustering using a new similarity measure[END_REF] as

L(θ; pl) = Ω X p X (x; θ)pl(x)dx, (25)
assuming this integral to exist and to be nonzero. According to [START_REF] Aggarwal | Outlier detection with uncertain data[END_REF], the interpretation of L(θ; pl) as a degree of agreement between p X (•; θ) and m is still valid in this case. Equation ( 22) also holds under the assumptions of stochastic and cognitive independence.

EVIDENTIAL EM ALGORITHM

In this section, the classical EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], [START_REF] Mclachlan | EM Algorithm Extensions[END_REF] will first be recalled in Subsection 4.1. A version of this algorithm, called the evidential EM (E 2 M) algorithm, which maximizes the generalized criterion introduced in the previous section will then be described in Subsection 4.2. Finally, the application of this algorithm to solve the Bernoulli example of Subsection 3.4 will be presented in Subsection 4.3.

EM algorithm

The EM algorithm is a broadly applicable mechanism for computing maximum likelihood estimates (MLEs) from incomplete data, in situations where maximum likelihood estimation would be straightforward if complete data were available [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF].

With the same notations as in Section 2.1, let us assume that we have a (discrete or continuous) random vector X with probability mass function or pdf p X (x; θ). A realization x has been drawn from X, but it is incompletely observed. The observed data consists in a subset A ⊂ Ω X such that x ∈ A. The likelihood function knowing that X ∈ A is given by [START_REF] Cazes | Extension de l'analyse en composantes principales à des données de type intervalle[END_REF].

The EM algorithm approaches the problem of maximizing the observed-data log likelihood log L(θ; A) by proceeding iteratively with the complete-data loglikelihood log L(θ; x) = log p X (x; θ). Each iteration of the algorithm involves two steps called the expectation step (E-step) and the maximization step (M-step).

The E-step requires the calculation of

Q(θ, θ (q) ) = E θ (q) [log L(θ; X) | A] , (26)
where θ (q) denotes the current fit of θ at iteration q and E θ (q) [•|A] denotes expectation with respect to the conditional distribution of X given A, using the parameter vector θ (q) . The M-step then consists in maximizing Q(θ, θ (q) ) with respect to θ over the parameter space Θ, i.e., finding θ (q+1) such that Q(θ (q+1) , θ (q) ) ≥ Q(θ, θ (q) ) for all θ ∈ Θ. The E-and M-steps are iterated until the difference L(θ (q+1) ; A)-L(θ (q) ; A) becomes smaller than some arbitrarily small amount.

It is proved in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] that the observed-data likelihood L(θ; A) is not decreased after an EM iteration, that is, L(θ (q+1) ; A) ≥ L(θ (q) ; A) for q = 0, 1, 2, . . .. Hence, convergence to some value L * is ensured as long as the sequence L(θ (q) ; A) for q = 0, 1, 2, . . . is bounded from above. As noted in [60, page 85], L * is, in most practical applications and except in pathological cases, a local maximum of the observed data log-likelihood L(θ; A).

Extension to uncertain data

To maximize the likelihood function L(θ; m) given uncertain data m, as introduced in Section 3, we propose to adapt the EM algorithm as follows.

In the E-step, the conditional expectation (26) of log L(θ; X) is now replaced by the expectation with respect to p X (•; θ (q) ) ⊕ pl, which will be denoted as p X (•|pl; θ (q) ). We may remark that conditional expectation is recovered in the special case where m is a categorical mass function. Using [START_REF] Kriegel | Density-based clustering of uncertain data[END_REF], the probability mass function p X (•|pl; θ (q) ) has the following expression:

p X (x|pl; θ (q) ) = p X (x; θ (q) )pl(x) L(θ (q) ; pl) , (27)
where L(θ (q) ; pl) is given by (18c) in the discrete case, and (25) in the continuous case. At iteration q, the following function is thus computed:

Q(θ, θ (q) ) = x∈Ω X log(L(θ; x))p X (x; θ (q) )pl(x) L(θ (q) ; pl) (28)
in the discrete case, or

Q(θ, θ (q) ) = Ω X log(L(θ; x))p X (x; θ (q) )pl(x)dx L(θ (q) ; pl) (29)
in the continuous case.

The M-step is unchanged and requires the maximization of Q(θ, θ (q) ) with respect to θ. The E 2 M algorithm alternately repeats the E-and M-steps above until the increase of observed-data likelihood becomes smaller than some threshold.

The E 2 M algorithm inherits the monotonicity property of the EM algorithm, as shown by the following theorem.

Theorem 1 Any sequence L(θ (q) ; m) for q = 0, 1, 2, . . . of likelihood values obtained using the E 2 M algorithm is non decreasing, i.e., it verifies

L(θ (q+1) ; pl) ≥ L(θ (q) ; pl) (30)
for all q.

The proof of Theorem 1 is very similar to that given in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. It is given in Appendix A for completeness.

To conclude this section, we may note that the probability mass or density function p X (x|θ) ⊕ pl and, consequently, the E 2 M algorithm depend only on the contour function pl and are unchanged if pl is multiplied by a constant. Consequently, the results are unchanged if m is converted into a probability distribution by normalizing the contour function, as suggested in [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF], or if pl is viewed as a possibility distribution. However, we may observe that Dempster's rule, which plays a fundamental role in our approach, can only be justified within the theory of belief functions as a rule to combine independent items of evidence (see, e.g., [START_REF] Shafer | Constructive probability[END_REF] for a comparison between the Dempster-Shafer and Bayesian semantics for "probability judgements"). Consequently, there seems to be no easy way to cast our approach in a more restricted framework such as possibility theory or probability theory.

Example

Let us come back to the example introduced in Subsection 3.4. The oberved-data likelihood to be maximized is given by [START_REF] Ferraro | A linear regression model for imprecise response[END_REF]. The complete-data log-likelihood is obtained by taking the logarithm of [START_REF] Coppi | Management of uncertainty in statistical reasoning: The case of regression[END_REF]: Fig. 1. Observed-data likelihood function for the data of Table 1 and ten equally spaced values of α ranging from 0 to 1.

log L(θ; x) = n log(1 -θ) + log θ 1 -θ n i=1 x i . (31)
As it is a linear function of the x i , the expectation of this quantity with respect to p X (•; θ (q) ) ⊕ pl can be computed in the E-step at iteration q as

Q(θ, θ (q) ) = n log(1 -θ) + log θ 1 -θ n i=1 ξ (q) i , (32)
where ξ (q) i is the expectation of X i with respect to p X (•|pl i ; θ (q) ) = p X (•; θ (q) ) ⊕ pl i :

ξ (q) i = E[X i |pl i ; θ (q) ] = θ (q) pl i (1) (1 -θ (q) )pl i (0) + θ (q) pl i (1)
.

The maximum of (32) computed at the M-step is obtained for:

θ (q+1) = 1 n n i=1 ξ (q) i , (34)
which is the estimate of θ at iteration q.

The above algorithm was applied to the data shown in Table 1. This dataset is composed of n = 6 observations, one of which (for i = 4) is uncertain and depends on a coefficient α. In that special case it is assumed that pl 4 (0) + pl 4 (1) = 1, i.e., the corresponding mass function m i is Bayesian. Figure 1 shows the observeddata likelihood function L(θ; m) for ten different values of α ranging from 0 to 1. In the special cases where α = 0 and α = 1 there is no data uncertainty and the MLEs are, respectively, θ = 0.5 and θ = 2/3. The E 2 M algorithm was applied to the data with α = 0.5. The results are shown in Table 2. The algorithm was stopped when the relative increase of the likelihood between two iterations was less than 10 -6 . Starting from the initial value θ (0) = 0.3, this condition was met after 5 iterations. The final MLE is θ = 0.6. This is the value of θ that minimizes the conflict between the uncertain data given in Table 1 and the parametric model [START_REF] Coppi | Management of uncertainty in statistical reasoning: The case of regression[END_REF].

TABLE 2

Intermediate and final results for the E 2 M algorithm applied to the data of Table 1 with α = 0.5. q θ (q) L(θ (q) ; pl) × 10

CLUSTERING OF CATEGORICAL DATA

In this section, we demonstrate the application of the E 2 M algorithm to the clustering of uncertain categorical data based on a latent class model [START_REF] Goodman | Exploratory latent structure analysis using both identifiable and unidentifiable models[END_REF], [START_REF] Celeux | Clustering criteria for discrete data and latent class models[END_REF]. The notations and the model will first be described in Subsection 5.1. The estimation algorithm for this problem will then be given in Subsection 5.2 and experimental results will be reported in Subsection 5.3.

Problem description and generative model

Let us consider a dataset composed of n objects described by p categorical attributes and a class attribute taking values in a set of g classes. Let w i = (w 1 i , . . . , w p i ) be the attribute vector for object i, and w j i the value of attribute j for object i. Each attribute j will be assumed to have r j modalities and we will denote w jh i = 1 if attribute j takes modality h for object i and w jh i = 0 otherwise. Similarly, the class of object i will be described by a vector z i = (z i1 , . . . , z ig ) of binary variables z ik such that z ik = 1 if object i belongs to class k, and z ik = 0 otherwise.

The complete data x = {(w 1 , z 1 ), . . . , (w n , z n )} will be assumed to be a realization from an iid random sample X = (X 1 , . . . , X n ), with X i = (W i , Z i ). We will further assume the attributes W j i to be conditionally independent given the class Z i . Denoting by α jh k the probability that attribute j takes modality h given class k and by π k the prior probability of class k, we thus have:

p(x; θ) = n i=1 p(w i , z i ; θ), (35)
where θ = ({α jh k }, {π k }) is the vector of all parameters, and

p(w i , z i ; θ) = p(z i ; θ)p(w i |z i ; θ) (36a) = g k=1 π z ik k g k=1 p(w i |z ik = 1; θ) z ik (36b) = g k=1   π k p j=1 rj h=1 (α jh k ) w jh i   z ik . (36c)
The complete data x will be assumed to be imperfectly observed, and partial knowledge about x will be assumed to be described by a mass function m on the domain of x. Assuming cognitive independence [START_REF] Carvalho | Partitional clustering algorithms for symbolic interval data based on single adaptive distances[END_REF] between all variables according to m, the contour function associated to m is

pl(x) = n i=1 pl(z i )pl(w i ) (37a) = n i=1   pl(z i ) p j=1 pl(w j i )   (37b) = n i=1   g k=1 (pl ik ) z ik p j=1 rj h=1 (pl jh i ) w jh i   , (37c)
where pl ik is the plausibility that object i belongs to class k, and pl jh i is the plausibility that attribute j takes modality h for object i.

The observed-data likelihood for this model has the following expression:

L(θ; pl) = n i=1 E θ [pl(X i )] (38a) = n i=1 E θ [pl(W i )pl(Z i )] (38b) = n i=1 g k=1 E θ [pl(W i )pl(Z i )|Z ik = 1] π k (38c) = n i=1 g k=1 π k pl ik p j=1 rj h=1 pl jh i α jh k . (38d)

Solution

The derivation of the E 2 M algorithm for the above model 3 is detailed in Appendix B. Only the main equations are given here without proof. E-step: The expectation of the complete-data loglikelihood log L(θ; x) with respect to p(•|pl; θ (q) ) = p(•; θ (q) ) ⊕ pl, where θ (q) is the current estimate of θ at iteration q, is:

Q(θ, θ (q) ) = i,k t (q) ik log π k + i,j,k,h β jh(q) ik log α jh k , (39)
where t (q) ik and β jh(q) ik are, respectively, the expectations of Z ik and W jh i Z ik with respect to p(•|pl; θ (q) ). They are given by the following equations:

t (q) ik = π (q) k pl ik j h α jh(q) k pl jh i π (q) pl i j h α jh(q) pl jh i ( 40
)
and

β jh(q) ik = γ jh(q) ik t (q) ik (41)
with

γ jh(q) ik = α jh(q) k pl jh i h α jh (q) k pl jh i . ( 42
)
3. Matlab source code for all the algorithms described in this paper can be downloaded from the author's web page at http://www.hds.utc.fr/˜tdenoeux.

TABLE 3

Conditional probability vectors for each attribute j given each class k for the simulated categorical data. M-step: The maximum of Q(θ, θ (q) ) is then obtained at the M-step for the following parameter estimates:

α j k k = 1 k = 2 k = 3 j = 1 (.1, .
π (q+1) k = 1 n n i=1 t (q) ik (43)
and

α jh(q+1) k = n i=1 γ jh(q) ik t (q) ik n i=1 t (q) ik . ( 44
)

Experimental results

The above approach was first applied to simulated data with g = 3 equiprobable classes and p = 3 attributes (with r j = 4 modalities each). The conditional probability distributions of attributes given each class are shown in Table 3.

A dataset of size n = 500 was generated from this distribution. To simulate uncertainty on attributes and class labels, we proceeded as follows. For each object i and each attribute j, an error probability q j i was drawn randomly from a beta distribution with mean ρ and standard deviation 0.2. With probability q j i , the value w j i of attribute j for object i was then replaced by a completely random value w j i (with a uniform distribution over the four modalities). The plausibilities pl jh i were then determined as

pl jh i = P (w jh i = 1| w jh i ) = q j i /4 if w jh i = 0, q j i /4 + 1 -q j i if w jh i = 1.
Similarly, class labels z i were replaced with noisy versions z i with probabilities q i drawn from the same distributions as the q j i s, and plausibilities pl ik were computed in a similar way.

The whole experiment (generation of initial and noisy data) was repeated 20 times. For each obtained data set, the E 2 M algorithm was applied to 1) Uncertain labels pl ik and uncertain attributes pl jh i ; 2) Noisy labels z ik and noisy attributes w jh i ; 3) Uncertain attributes pl jh i and no information on class labels; 4) Noisy attributes w jh i and no information on class labels.

In each case, the E 2 M algorithm was run 5 times with random initial conditions, and the best solution according to the observed-data likelihood was retained. Each object was then assigned to the class with the largest estimated posterior probability, and the obtained partition was compared to the true partition using the adjusted Rand index [START_REF] Hubert | Comparing partitions[END_REF]. We recall that this commonly used clustering performance measure is a corrected-for-chance version of the Rand index, which equals 0 on average for a random partition, and 1 when comparing two identical partitions.

The results are shown graphically in Figure 2. As expected, a degradation of the clustering performances is observed when the mean error probability ρ increases, with the adjusted rand index tending to zero as ρ tends to 1. More importantly, Figure 2 shows that the use of uncertain labels and/or uncertain attribute values (in the form of plausibilities) allows us to reach better clustering results than those obtained using noisy labels and/or attributes. These results show that our method is able to exploit additional information on data uncertainty, when such information is available.

We may remark here that, in the previous experiment, uncertain labels and attributes had to be generated by a random process. One could object that this random process, if known, could be incorporated in the generative model, and the standard EM algorithm could be used. It must be emphasized, however, that mass or plausibility functions in our model introduced in Section 3 represent epistemic uncertainty, which cannot be represented within a random generative model. They are only generated randomly here for the purpose of the experiment.

Our approach was also tested on the Breast Cancer dataset available from the UCI Machine Learning Repository 4 . This is a two-class dataset with 201 instances of one class and 85 instances of the other class. The instances are described by 9 discrete attributes treated as categorical. Noisy attributes w jh i and uncertain attributes pl jh i were generated in exactly the same way as in the previous experiment. We considered a semi-supervised learning task, in which a proportion δ of the objects is labeled. As before, we estimated the model parameters, assigned each unlabeled object to the class with the largest estimated posterior probability, and evaluated the result using the adjusted Rand index. The experiment was repeated 20 times. Figures 3 and4 show the average values of the adjusted Rand index as a function of the mean error probability ρ, for noisy and uncertain attributes, with proportions of labeled data equal to δ = 20% and δ = 30%, respectively. Once again, better results are obtained when taking into account attribute uncertainty, which demonstrates the usefulness of our approach.

CLUSTERING OF CONTINUOUS DATA

Gaussian mixture models are commonly used for clustering continuous data (see, e.g., [START_REF] Banfield | Model-based Gaussian and non-Gaussian clustering[END_REF], [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF]). In this section, we investigate the estimation of parameters in such models, when uncertainty on attributes is represented by belief functions with Gaussian contour functions, and partial information on class labels may also be available in the form of arbitrary mass functions. As in the previous section the model will first be introduced in Subsection 6.1. The estimation algorithm will then be described in Subsection 6.2 and simulation results will be presented in Subsection 6.3.

Problem description and generative model

The notations and assumptions are basically the same as those in Subsection 5.1, except that the attribute vector W i = (W 1 i , . . . , W p i ) for object i is now assumed to be normally distributed conditionally on z ik = 1, with mean

µ k = (µ 1 k , . . . , µ p k ) and diagonal covariance matrix Σ k = diag[(σ 1 k ) 2 , . . . , (σ p k ) 2 ]: p(w i |z ik = 1; µ k , Σ k ) = φ(w i ; µ k , Σ k ) = p j=1 φ(w j i ; µ j k , (σ j k ) 2 ). (45)
Denoting by θ = ({µ k }, {Σ k }, {π k }) the vector of all parameters, the complete data pdf is

p(x; θ) = n i=1 p(z i ; θ)p(w i |z i ; θ) (46a) = n i=1 g k=1 (π k φ(w i ; µ k , Σ k )) z ik . (46b)
As before, assuming cognitive independence [START_REF] Carvalho | Partitional clustering algorithms for symbolic interval data based on single adaptive distances[END_REF], partial knowledge about x will be assumed to be represented by a mass function m with contour function

pl(x) = n i=1 pl(z i )pl(w i ) (47a) = n i=1   g k=1 (pl ik ) z ik p j=1 pl(w j i )   . (47b)
Assuming the marginal contour function pl(w j i ) on w j i to be a normalized Gaussian with mean m j i and standard deviation s j i : pl(

w j i ) = φ(w j i ; m j i , (s j i ) 2 )s j i √ 2π, we can write pl(x i ) = (2π) p/2   j s j i   × g k=1 (pl ik ) z ik φ(w i ; m i , S i ), (48)
with m i = (m 1 i , . . . , m p i ) and

S i = diag[(s 1 i ) 2 , . . . , (s p i ) 2 ]
. Using the same derivation as in (38a)-(38d), we get the following expression for the observed-data likelihood:

L(θ; pl) = n i=1 g k=1 π k pl ik E θ [pl(W i )|Z ik = 1] , (49)
with (using (13b) and the conditional independence of the attributes W j i given Z ik = 1):

E θ [pl(W i )|Z ik = 1] = (2π) p/2 p j=1 φ j ik s j i ( 50
)
and φ j ik = φ(m j i ; µ j k , (σ j k ) 2 + (s j i ) 2 ).

Solution

A before, only the main equations of the E 2 M algorithm for the above model will be given in this section. The derivation of these equations is detailed in Appendix C. E-step: The expectation of the complete-data loglikelihood log L(θ; x) with respect to p(•; θ (q) )⊕pl is then

Q(θ; θ (q) ) = g k=1 log π k n i=1 t (q) ik - np 2 log(2π) - i,k t (q) ik j log σ j k - 1 2 i,k t (q) ik j ξ j(q) ik -2µ j(q) ik µ j k + (µ j k ) 2 (σ j k ) 2 , (51)
where

µ j(q) ik = µ j(q) k (s j i ) 2 + m j i (σ j(q) k ) 2 (s j i ) 2 + (σ j(q) k ) 2 , ( 52
) (σ j(q) ik ) 2 = (σ j(q) k ) 2 (s j i ) 2 (s j i ) 2 + (σ j(q) k ) 2 , ( 53
)
ξ j(q) ik = (µ j(q) ik ) 2 + (σ j(q) ik ) 2 (54)
and

t j(q) ik = π (q) k pl ik j φ j(q) ik π (q) pl i j φ j(q) i (55)
with

φ j(q) ik = φ(m j i ; µ j(q)
k , (σ

j(q) k ) 2 + (s j i ) 2 ). (56)
M-step: Maximizing (51) yields the following parameter estimates at iteration q + 1:

π (q+1) k = 1 n n i=1 t j(q) ik , (57)
µ j(q+1) k = n i=1 t j(q) ik µ j(q) ik n i=1 t j(q) ik , (58)
(σ j(q+1) k ) 2 = n i=1 t j(q) ik (ξ j(q) ik -2µ j(q+1) k µ j(q) ik + (µ j(q+1) k ) 2 ) n i=1 t j(q) ik . (59)

Experimental results

The above algorithm was applied to simulated Gaussian data with n = 200 instances and the following parameter values:

µ 1 = (3, 0, 0) , µ 2 = (0, 3, 0) , µ 3 = (0, 0, 3) ,

Σ 1 = Σ 2 = Σ 3 = I, π 1 = π 2 = π 3 = 1/3.
We first considered the unsupervised learning situation in which no information on class labels is available, i.e., pl ik = 1 for all i and k. To simulate uncertainty on attributes, we randomly generated for each object i and each attribute j a standard deviation s j i from the uniform distribution in [0, s max ]. The value w j i of attribute j for object i was then replaced by a random value w j i drawn from a Gaussian distribution with mean w j i and standard deviation s j i . We then set m j i = w j i . The whole experiment (generation of initial and noisy data) was repeated 20 times. For each obtained dataset, the E 2 M algorithm was applied to the noisy attributes w j i and to the uncertain attributes (m j i , s j i ). In each case, the E 2 M algorithm was run 5 times with random initial conditions, and the best solution according to the observed-data likelihood was retained. Each object was then assigned to the class with the largest estimated posterior probability, and the obtained partition was compared to the true partition using the adjusted Rand index. The results are shown in Figure 5. As we can see, the algorithm successfully exploits the additional information about attribute uncertainty, which allows us to better recover the true partition of the data.

To investigate the influence of class label uncertainty, we generated noisy class labels z ik and plausibilities pl ik as explained in Subsection 5.3. Attribute uncertainty was also simulated as above, with s max = 2. Figure 6 shows the adjusted Rand index as a function of the mean error probability ρ on class labels, for the E 2 M algorithm applied to data with uncertain and noisy labels, as well as to unsupervised data. Here again, uncertainty on class labels appears to be successfully exploited by the algorithm. Remarkably, the results with uncertain labels never get worse than those obtained without label information, even for error probabilities close to 1. This finding confirms a similar result reported in [START_REF] Mellouli | Learning from partially supervised data using mixture models and belief functions[END_REF].

To corroborate the above results with real data, similar experiments were carried out with the well-known Iris dataset 5 . We recall that this dataset is composed of 150 4-dimensional attribute vectors partitioned in 3 classes, corresponding to three species of Iris. Unsupervised learning with attribute uncertainty generated as above was first carried out. The results, shown in Figure 7, are very similar to those obtained with simulated Gaussian data. Finally, results with both attribute uncertainty (with s max = 2) and label uncertainty (generated as 5. This data set is available at http://archive.ics.uci.edu/ml. above) are shown in Figure 8. Again, these results are very similar to those obtained with simulated data, as shown in Figure 6.

CONCLUSION

A method for estimating parameters in statistical models in the case of uncertain observations has been introduced. The proposed formalism combines aleatory uncertainty captured by a parametric statistical model with epistemic uncertainty induced by an imperfect observation process and represented by belief functions. Our method then seeks the value of the unknown parameter that maximizes a generalized likelihood criterion, which can be interpreted as a degree of agreement between the parametric model and the uncertain data. This is achieved using the evidential EM algorithm, which is a simple extension of the classical EM algorithm with proved convergence properties.

As an illustration, the method has been applied to clustering problems with partial knowledge of class labels and attributes, based on latent class and Gaussian mixture models. In these problems, our approach has been shown to successfully exploit the additional information about data uncertainty, resulting in improved performances in the clustering task.

More generally, the approach introduced in this paper is applicable to any uncertain data mining problem in which a parametric statistical model can be postulated and data uncertainty arises form an imperfect observation process. This includes a wide range of problems such as classification, regression, feature extraction and time series prediction.

APPENDIX A PROOF OF THEOREM 1

Let g(x|pl; θ) be defined using the following expression:

g(x|pl; θ) = L(θ; x) L(θ; pl) = p X (•|pl; θ) pl(x) , (60)
where the rightmost expression is derived from [START_REF] Hébert | Fuzzy multidimensional scaling[END_REF]. We thus have log L(θ; pl) = log L(θ; x) -log g(x|pl; θ).

Taking the expectation of both sides with respect to p X (•|pl; θ (q) ), we get

log L(θ; pl) = E θ (q) [log L(θ; X)|pl] -E θ (q) [log g(X|pl; θ)|pl] = Q(θ, θ (q) ) -H(θ, θ (q) ) (62)
with

H(θ, θ (q) ) = E θ (q) [log g(X|pl; θ)|pl] . (63)
We thus have log L(θ (q+1) ; pl) -log L(θ (q) ; pl)

= Q(θ (q+1) , θ (q) ) -Q(θ (q) , θ (q) ) -H(θ (q+1) , θ (q) ) -H(θ (q) , θ (q) ) . ( 64
)
The first difference on the right-hand side of ( 64) is nonnegative as θ (q+1) has been chosen to maximize Q(θ, θ (q) ) with respect to θ. It thus remains to check that the second difference on the right-hand side of ( 64) is non-positive; that is, we need to verify that the following inequality holds: H(θ (q+1) , θ (q) )-H(θ (q) , θ (q) ) ≤ 0. Now for any θ,

H(θ, θ (q) ) -H(θ (q) , θ (q) ) = E θ (q) log g(X|pl; θ) g(X|pl; θ (q) ) |pl ≤ log E θ (q) g(X|pl; θ) g(X|pl; θ (q) ) |pl (65)
and

log E θ (q) g(X|pl; θ) g(X|pl; θ (q) ) |pl = log g(x|pl; θ) g(x|pl; θ (q) ) pl(x)g(x|pl; θ (q) )dx = log g(x|pl; θ)pl(x)dx = log p X (x|pl; θ (q) )dx = 0, (66)
where the inequality in ( 65) is a consequence of Jensen's inequality.

APPENDIX B DERIVATION OF THE E 2 M ALGORITHM FOR THE CATEGORICAL DATA CLUSTERING PROBLEM

From ( 35) and (36c), the complete-data log-likelihood is

log L(θ; x) = i,k z ik log π k + i,j,k,h w jh i z ik log α jh k . (67)
By taking its expectation with respect to p(•|pl; θ (q) ) = p(•; θ (q) ) ⊕ pl, where θ (q) is the current estimate of θ at iteration q, we get expression [START_REF] Trabelsi | Pruning belief decision tree methods in averaging and conjunctive approaches[END_REF] for Q(θ, θ (q) ). To compute this expression, we may first observe that, from [START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF] and ( 21):

p(x|pl; θ (q) ) = n i=1 p(w i , z i |pl; θ (q) ).

(68)

Then, using (36c) and (37c), we get: p(w i , z ik = 1|pl; θ (q) ) = π (q) k pl ik j,h (α jh(q) k pl jh i ) w jh i π (q) pl i j h α jh(q) pl jh i .

Marginalizing out w i leads to the following expression for p(Z ik = 1|pl; θ (q) ):

p(Z ik = 1|pl; θ (q) ) = π (q)
k pl ik j h α jh(q) k pl jh i π (q) pl i j h α jh(q) pl jh i , (70) from which we get [START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF]. Conditioning (69) on z ik = 1, we get:

p(w i |z ik = 1, pl; θ (q) ) = p(w i , z ik = 1|pl; θ (q) ) p(z ik = 1|pl; θ (q) ) =

Now, β jh(q) ik = E θ (q) [W jh i Z ik |pl] can be written as β jh(q) ik = p(W jh i = 1, Z ik = 1|pl; θ (q) ) = p(W jh i = 1|Z ik = 1, pl; θ (q) )p(Z ik = 1|pl; θ (q) ), (72) from which we obtain [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF] and [START_REF] Jraidi | Belief classification approach based on generalized credal EM[END_REF]. The update equations ( 43) and ( 44) at the M-step are obtained by maximizing Q(θ, θ (q) ) with respect to parameters π k and α jh k , taking into account the equality constraints k π k = 1 and h α jh k = 1. The calculations are the same as in the classical latent class model without data uncertainty.

APPENDIX C DERIVATION OF

z ik j (w j i ) 2 -2w j i µ j k + (µ j k ) 2 (σ j k ) 2 . ( 76
)
To compute the expectation Q(θ; θ (q) ) of log L(θ; x) with respect to p(•|pl, θ (q) ) = p(•; θ (q) ) ⊕ pl, where θ (q) is the current estimate of θ at iteration q, we need to compute the expectations of Z ik , Z ik (W j i ) 2 and Z ik W j i . For that purpose, we may first observe that, similarly to the previous model: p(x|pl; θ (q) ) = n i=1 p(w i , z i |pl; θ (q) ).

(77)

Then, using (46b) and ( 48), we get: p(w i , z ik = 1|pl; θ (q) ) = π (q) k pl ik φ(w i ; µ

(q) k , Σ (q)
k )φ(w i ; m i , S i ) π (q) pl i φ(w i ; µ (q) , Σ (q) )φ(w i ; m i , S i )dw i . (78)

From (13a)-(13b), this expression may be simplified as p(w i , z ik = 1|pl; θ (q) ) = π (q) k pl ik j φ j(q) ik φ(w j i ; µ j(q) ik , (σ j(q) ik ) 2 ) π (q) pl i j φ j(q) i , (79) with µ j(q) ik , (σ j(q) ik ) 2 and φ j(q) ik given, respectively, by ( 52), ( 53) and [START_REF] Qi | Measuring conflict and agreement between two prioritized belief bases[END_REF].

Marginalizing out w i in (79), we obtain

P (Z ik = 1|pl, θ (q) ) = π (q)
k pl ik j φ j(q) ik π (q) pl i j φ j(q) i .

(80) from which we get the expression of t j(q) ik = E θ (q) [Z ik |pl] as [START_REF] González-Rodríguez | Multi-sample test-based clustering for fuzzy random variables[END_REF]. Conditioning (79) by z ik = 1 leads to the following conditional pdf: p(w i |z ik = 1, pl; θ (q) ) = π (q) k pl ik j φ j(q) ik φ(w j i ; µ j(q) ik , (σ

j(q) ik ) 2 ) π (q)
k pl ik j φ j(q) ik = j φ(w j i ; µ j(q) ik , (σ

j(q) ik ) 2 ). (81)
Consequently, E θ (q) [Z ik (W j i ) 2 |pl] = E θ (q) [(W j i ) 2 |Z ik = 1, pl]P (Z ik = 1|pl; θ (q) ) = ξ j(q) ik t j(q) ik (82) with ξ j(q) ik defined by ( 54) and E θ (q) [Z ik W j i |pl] = E θ (q) [W j i |Z ik = 1, pl]P (Z ik = 1|pl; θ (q) ) = µ j(q) ik t j(q)

ik . (83)

The update equations ( 57)-( 59) are obtained as in the standard Gaussian mixture model by maximizing Q(θ; θ (q) ) with respect to parameters π k , µ j k and σ j k under the equality constraint k π k = 1.

Fig. 2 .

 2 Fig. 2. Average values (plus and minus one standard deviation) of the adjusted Rand index over the 20 repetitions, as a function of the mean error probability ρ for the simulated categorical data.

Fig. 3 .

 3 Fig. 3. Average values (plus and minus one standard deviation) of the adjusted Rand index over 20 repetitions, as a function of the mean error probability ρ for the Breast Cancer data with δ = 20%.

Fig. 4 .

 4 Fig. 4. Average values (plus and minus one standard deviation) of the adjusted Rand index over 20 repetitions, as a function of the mean error probability ρ for the Breast Cancer data with δ = 30%.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Average values (plus and minus one standard deviation) of the adjusted Rand index over 20 repetitions, as a function of the maximal standard deviation s max for the simulated Gaussian data, with no information on class labels.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Average values (plus and minus one standard deviation) of the adjusted Rand index over 20 repetitions, as a function of the maximal standard deviation s max for the Iris data, with no information on class labels.

THE E 2 M

 2 ALGORITHM FOR THECONTINUOUS DATA CLUSTERING PROBLEMUsing (46b), the complete-data log-likelihood is obtained as: log L(θ; x) =

TABLE 1

 1 Dataset for the Bernoulli example of Subsection 4.3.

This data set is available at http://archive.ics.uci.edu/ml. It was obtained from the University Medical Centre, Institute of Oncology, Ljubljana, Yugoslavia.

BIOGRAPHY

Thierry Denoeux graduated in 1985 from the Ecole Nationale des Ponts et Chaussées in Paris, and received a doctorate from the same institution in 1989. Currently, he is a Full Professor with the Department of Information Processing Engineering at the Université de Technologie de Compiègne, France. His research interests concern belief functions theory, fuzzy data analysis and, more generally, the management of imprecision and uncertainty in data analysis, pattern recognition and information fusion. He is the Editor-in-Chief of the International Journal of Approximate Reasoning, and a member of the editorial board of Fuzzy Sets and Systems.