Benjamin Quost
email: benjamin.quost@hds.utc.fr

Thierry Denoeux

Clustering and classification of fuzzy data using the fuzzy EM algorithm

Clustering and classification of fuzzy data using the fuzzy EM algorithm

Introduction

Gaussian mixture models (GMMs) are very powerful tools for modeling multivariate distributions [START_REF] Redner | Mixture densities, maximum likelihood and the em algorithm[END_REF]. This model assumes the data to arise from a random sample, whose distribution is a finite mixture of Gaussians. The major difficulty is to estimate the parameters of the model. Generally, these estimates are computed using the maximum-likelihood (ML) approach, through an iterative procedure known as the expectation-maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. Once the parameter values are known, the posterior probabilities of each data point may be computed, thus giving a fuzzy partition of the data. Then, a crisp partition may be obtained by assigning a label to each instance according to the Maximum A Posteriori (MAP) rule.

In some applications, the precise value taken by the variables may be difficult or even impossible to assess. For example, in acoustical engineering, flaws can be detected on storage tanks by pressurizing the device and measuring the resulting acoustical emissions; this technique provides locations of acoustic events associated with imprecision degrees [START_REF] Hamdan | CEM algorithm for imprecise data. application to flaw diagnosis using acoustic emission[END_REF]. As stressed in [START_REF] Jacquez | Disease cluster statistics for imprecise space-time locations[END_REF], epidemiological data, such as address of the patients, hospital admission times, etc, often suffer from imprecision. The interest of taking into account the uncertainty of the measurements has been demonstrated [START_REF] Mauris | Expression of measurement uncertainty in a very limited knowledge context: a possibility theory-based approach[END_REF]. For this purpose, various formalisms allowing to quantify and propagate imprecision have been proposed, among which fuzzy sets [START_REF] Gebhardt | Fuzzy set-theoretic methods in statistics[END_REF][START_REF] Gil | Overview on the development of fuzzy random variables[END_REF][START_REF] Kruse | Statistics with vague data[END_REF][START_REF] Viertl | Univariate statistical analysis with fuzzy data[END_REF]. Some consider that the data at hand are intrinsically fuzzy, a position that has been known as the physical or ontic interpretation of fuzziness [START_REF] Dubois | Ontic vs. epistemic fuzzy sets in modeling and data processing tasks[END_REF][START_REF] Couso | Statistical reasoning with set-valued information: Ontic vs. epistemic views[END_REF]. Here, we rather adopt an epistemic interpretation, in which a fuzzy number "imperfectly specifies a value that is existing and precise, but not measurable with exactitude under the given observation conditions" [START_REF] Gebhardt | Fuzzy set-theoretic methods in statistics[END_REF]. In this setting, partial knowledge of the actual precise value taken by a random variable of interest is represented by a possibility distribution.

Several recent papers have addressed the problem of clustering imprecise data, for which both the attributes and the class information may be partially known. For instance, in [START_REF] Chaudhuri | An approach of clustering data with noisy or imprecise feature measurement[END_REF], the imprecise data at hand are represented by hyperspheres, and the clustering is achieved using a K-means-based procedure. In [START_REF] Irpino | Clustering reduced interval data using Hausdorff distance[END_REF], the imprecision of the data is represented by convex hulls, and hierarchical clustering is used to partition the data. In [START_REF] Habich | Error-aware densitybased clustering of imprecise measurement values[END_REF], a density-based clustering algorithm, DBSCAN, is employed to cluster data in presence of noise. The work presented in [START_REF] Hamdan | Mixture model clustering of uncertain data[END_REF] is of notable importance: it addresses the problem of clustering interval-valued data in the probabilistic setting of GMM parameter estimation. It should be stressed that the EM algorithm is particularly wellsuited to this kind of imprecision. Indeed, handling such censored data dates back to the seminal article by Dempster et al [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], and is still the subject of investigations [START_REF] Lee | EM algorithms for multivariate gaussian mixture models with truncated and censored data[END_REF]. Many articles also address handling probabilistic uncertainty over the attributes: the partial knowledge of the value of a variable of interest is described by a probability density function (pdf). The data may then be partitioned in various ways, such as hierarchical clustering [START_REF] Kriegel | Hierarchical density-based clustering of uncertain data[END_REF], or (non-parametric) density-based clustering [START_REF] Kriegel | Density-based clustering of uncertain data[END_REF]. Some authors introduced an extension of the Kmeans algorithm, called Uncertain K-means (UK-means) [START_REF] Chau | Uncertain data mining: An example in clustering location data[END_REF][START_REF] Ngai | Efficient clustering of uncertain data[END_REF][START_REF] Kao | Clustering uncertain data using clustering uncertain data using Voronoi diagrams and Rtree index[END_REF]. In [START_REF] Cormode | Approximation algorithms for clustering uncertain data[END_REF], K-means, K-median, and K-centre strategies are used. We may also mention the work in [START_REF] Aggarwal | On density based transforms for uncertain data mining[END_REF], which considers micro-clustering for compressing data, and [START_REF] Günnemann | Subspace clustering for uncertain data[END_REF], which addresses the problem of subspace clustering from imprecise data. Reviews may be found in [START_REF] Zhang | Managing uncertain data: Probabilistic approaches[END_REF][START_REF] Aggarwal | Managing and Mining Uncertain Data[END_REF][START_REF] Aggarwal | A survey of uncertain data algorithms and applications[END_REF]. Eventually, many authors considered clustering uncertain data described by fuzzy numbers or belief functions. Almost all of them [START_REF] Sato | Fuzzy clustering model for fuzzy data[END_REF][START_REF] Hathaway | A parametric model fusing heterogeneous fuzzy data[END_REF][START_REF] Pedrycz | Two nonparametric models for fusing heterogeneous fuzzy data[END_REF][START_REF] Takata | Clustering of data with uncertainties using hausdorff distance[END_REF][START_REF] Takata | Fuzzy clustering of data with uncertainties using minimum and maximum distances based on l1 metric[END_REF][START_REF] Yang | Fuzzy clustering procedures for conical fuzzy vector data[END_REF][START_REF] Yang | Fuzzy clustering algorithms for mixed feature variables[END_REF][START_REF] Coppi | Three-way fuzzy clustering models for lr fuzzy time trajectories[END_REF][START_REF] Urso | A weighted fuzzy c-means clustering model for fuzzy data[END_REF][START_REF] Hung | Fuzzy clustering on lr-type fuzzy numbers with an application in Taiwanese tea evaluation fuzzy clustering on lr-type fuzzy numbers with an application in taiwanese tea evaluation[END_REF][START_REF] Zarandi | A fuzzy clustering model for fuzzy data with outliers[END_REF][START_REF] Coppi | Fuzzy and possibilistic clustering for fuzzy data[END_REF] perform clustering using a geometric approach related to the Fuzzy C-means (FCM) algorithm. The centers of the model and the membership degrees of the data to the clusters are computed iteratively so as to optimize a within-cluster variance criterion. In [START_REF] Hariz | Clustering approach using belief function theory[END_REF], an approach referred to as Belief K-modes was proposed in the belief functions framework. A notable exception is [START_REF] Jacquez | Disease cluster statistics for imprecise space-time locations[END_REF], where the author considers statistical tests to partition the data. Clustering multivariate fuzzy data using mixtures of distributions has been addressed in [START_REF] Quost | Clustering fuzzy data using the fuzzy em algorithm[END_REF].

Additionally, the related problem of learning from imprecisely labeled instances has been widely addressed in the literature. Semi-supervised learning [START_REF] Hosmer | A comparison of iterative maximum likelihood estimates of the parameters of a mixture of two normal distributions under three different types of samples[END_REF][START_REF] Mclachlan | Estimating the linear discriminant function from initial samples containing a small number of unclassified observations[END_REF] considers that a subset of instances have been associated with a (precise) label, the labels of the other instances being unknown. Partially supervised learning [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempstershafer theory[END_REF][START_REF] Ambroise | EM algorithm for partially known labels[END_REF][START_REF] Ambroise | Learning from an imprecise teacher: probabilistic and evidential approaches[END_REF][START_REF] Grandvalet | Logistic regression for partial labels[END_REF][START_REF] Hüllermeier | Learning from ambiguously labeled examples[END_REF] encompasses this approach, by making it possible to associate each instance with a set of (equally) plausible labels. Besides, the problem of noisy labels has been addressed in a probabilistic framework [START_REF] Lawrence | Estimating a kernel fisher discriminant in the presence of label noise[END_REF][START_REF] Amini | Semi-supervised learning with an imperfect supervisor[END_REF][START_REF] Karmaker | A boosting approach to remove class label noise[END_REF]. More recently, the general framework of belief functions has been successfully employed to estimate GMMs from imprecise and uncertain labels [START_REF] Vannoorenberghe | Partially supervised learning by a credal em approach[END_REF][START_REF] Vannoorenberghe | Estimation de modèles de mélanges finis par un algorithm em crédibiliste[END_REF][START_REF] Jraidi | Belief classification approach based on generalized credal em[END_REF][START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF]. Finally, it should be stressed out that the literature dedicated to fuzzy GMM estimation, or more generally imprecise or uncertain clustering, actually refers to associating precise instances with several classes in a imprecise way. For example, [START_REF] Caillol | Estimation of fuzzy Gaussian mixture and unsupervised statistical image segmentation[END_REF] addresses the problem of image segmentation where pixels may be mixed (e.g., in ground segmentation, the pixel may belong to both "water" and "forest" categories). As well, [START_REF] Ju | Fuzzy Gaussian mixture models[END_REF] proposes to make GMM estimation more flexible in order to fit curve manifolds, by using a trade-off between GMM and fuzzy C-means estimation according to the geometric shape of the dataset considered. Again, this work does not address the case where the data at hand are uncertain. In [START_REF] Maalel | Belief hierarchical clustering[END_REF], an algorithm for performing hierarchical clustering of a set of precise instances is developed in the framework of belief functions. Finally, in [START_REF] Zeng | Type-2 fuzzy Gaussian mixture models[END_REF], the authors consider parameter uncertainty, rather than attribute or class uncertainty. Once a GMM has been estimated using the precise data, membership functions are defined on the corresponding parameters, and the instances are linked to the classes by sets of likelihoods instead of probabilities.

In this paper, we propose to fit a GMM defined by precise parameters to uncertain data, where both the attribute vector and the class information may be partially known. This paper distinguishes thus from most of the works mentioned above in that the approach is parametric: we postulate a probabilistic model underlying the data, the parameters of which have to be estimated. Flexibility is a notable advantage of the method: in presence of scarce or lowquality data (or when it is justified by background knowledge), the model may be simplified via additional assumptions on the parameters to estimate, such as explained in [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF]. We adopt here possibility distributions as mathematical tools for representing partial knowledge of the instance values or weak class information. In this case, the likelihood of the sample may be computed using Zadeh's definition of the probability of a fuzzy event [START_REF] Zadeh | Fuzzy sets[END_REF]. Then, the fuzzy EM algorithm may be used to estimate the parameters maximizing this likelihood. This procedure was recently proposed by Denoeux as an extension of the EM algorithm for imprecise data represented by fuzzy numbers [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF] and by belief functions [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF] 2 . Thus, unlike in [START_REF] Vannoorenberghe | Partially supervised learning by a credal em approach[END_REF][START_REF] Vannoorenberghe | Estimation de modèles de mélanges finis par un algorithm em crédibiliste[END_REF][START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF], we consider here both attribute and class uncertainty in our estimation process. Note that [START_REF] Hamdan | Mixture model clustering of uncertain data[END_REF] considered uncertain attribute values represented by intervals; besides, the approach described in [START_REF] Jraidi | Belief classification approach based on generalized credal em[END_REF] made it possible to take into account the fact that some attribute information were missing. In our approach, we propose instead a generic strategy for incorporating partial attribute information and class information. Any kind of partial knowledge may thus be integrated in the estimation process, as long as the appropriate possibility function is specified. Under the epistemic interpretation of uncertainty adopted here, fuzzy numbers represent information that should have been precise under ideal conditions in the measurement process. Then, two philosophies may be considered. Following [START_REF] Zeng | Type-2 fuzzy Gaussian mixture models[END_REF], the uncertainty may be propagated through the estimation process. In this case, the range of the family of models estimated accounts for the imperfection of the data. Alternatively, one may look for the best model, according to a particular criterion, given the data at hand [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF]. This is the approach considered in this paper, where a generalized likelihood is used to measure the agreement between the model and the fuzzy observations available.

The article is organized as follows. Section 2 recalls the model. Then, we show how the FEM algorithm may be used in order to estimate the parameters of a GMM. In Section 3, we first concentrate on the particular case of multivariate Gaussian possibility distributions: then, closed forms may be obtained for the update equations of the model parameters. For computational reasons however, this may not be possible in the general case (e.g., for trapezoidal possibility distributions). Then, we present in Section 4 an efficient and versatile Monte-Carlo approximation procedure to overcome this problem. Section 5 addresses the problem of avoiding degenerate parameter estimates using Bayesian priors. Section 6 presents various experiments on synthetic and real data, in both clustering and classification settings. Eventually, Section 7 concludes the paper.

Model

In this section, we recall basic knowledge on Gaussian mixture models. Then, we formalize the estimation problem when the data at hand are fuzzy.

Data and generative model

From now on, we assume the existence of a random vector Y ∈ Y, referred to as the complete data vector, which describes the result of a random experiment. In our case, it takes the form of an iid sample: y = (y 1 , . . . , y n ). The ith element y i = (x i , z i ) of this sample is composed of two pieces of information:

• an attribute vector x i , supposed to be the realization of a random vector X ∈ R p drawn from a mixture of K Gaussian distributions with proportions π 1 , . . . , π g . The marginal distribution of the attribute vectors thus writes

g X (x 1 , . . . , x n , Ψ) = n i=1 K k=1 π k g(x i ; ν k , Σ k ), (1a)
g(•; ν k , Σ k ) being the pdf of the multivariate Gaussian distribution with mean vector ν k and covariance matrix Σ k :

g(x; ν k , Σ k ) = (2π) p/2 |Σ k | -1 2 exp - 1 2 (x -ν k ) t Σ -1 k (x -ν k ) . (1b)
In the following, for the sake of clarity, we will write g k (•) = g(•; ν k , Σ k ).

• a vector z i of realizations of Bernoulli random variables Z ik , indicating which component of the GMM generated x i (z ik = 1 if x i was drawn from the component ω k of the mixture, and z ik = 0 otherwise). Note that in clustering problems, these variables are typically unknown and must be estimated. In discriminant analysis, however, the class indicators are known, in which case the joint density of the sample can be written as

f (y) = n i=1 K k=1 (π k g k (x i )) z ik . (1c)
In the latter case, the ML estimates of the model parameters can be easily computed by maximizing the complete likelihood defined by Equation (1c).

In the former case, however, proceeding with the observed likelihood (1a) is difficult; the EM algorithm [START_REF] Redner | Mixture densities, maximum likelihood and the em algorithm[END_REF][START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] may then be used for this purpose.

In this paper, we address the case where the realizations are not precisely observed. We only have a partial knowledge of the actual values x i and z i , in the form of fuzzy subsets ỹi = (x i , zi ) with possibility distribution µ xi ,zi = µ xi (x)µ zi (z). The value µ xi (x) may be interpreted as a degree of possibility that the actual realization of the random vector X is x. For example, assuming a Gaussian possibility distribution with mean vector m i and covariance matrix S i for x i gives:

µ xi (x) = exp - 1 2 (x -m i ) t S -1 i (x -m i ) . (2)
The imprecise class information is represented by a vector zi = (δ i1 , . . . , δ ig ), where δ ik ∈ [0, 1] is the degree of possibility that x i was actually drawn from ω k . Thus, the degree of possibility that z i represents the actual component from which x i was generated is

µ zi (z i ) = K k=1 (δ ik ) z ik . (3)
Note that complete ignorance of the actual class of an instance corresponds to δ ik = 1 for all k = 1, . . . , K; while full certainty that its actual class of x i is ω k corresponds to δ ik = 1 and δ iℓ = 0 for all ℓ = k.

Generalized likelihood of fuzzy data

Let us assume that a fuzzy sample ỹ = (ỹ 1 , . . . , ỹn ) has been observed. According to Zadeh's definition of the probability of a fuzzy event [START_REF] Zadeh | Probability measures of fuzzy events[END_REF], the probability of this fuzzy sample is the expectation of its possibility distribution:

P(ỹ; Ψ) = E Ψ [µ ỹ(y)] = Y µ ỹ(y)g Y (y; Ψ)dy. ( 4
)
We assume here that the fuzzy observations are cognitively independent:

µ ỹ(y) = n i=1 µ ỹi (y i ). (5)
Thus, the likelihood of the imprecisely observed data is [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF]:

L(Ψ; ỹ1 , . . . , ỹn ) = P(ỹ 1 , . . . , ỹn ; Ψ) = n i=1 E Ψ [µ xi (x) µ zi (z)] , (6a)
= n i=1 K k=1 P(Z ik = 1)E Ψ [µ xi (x) µ zi (z)|Z ik = 1] , (6b) = n i=1 K k=1 π k δ ik E Ψ [µ xi (x)|Z ik = 1] . (6c)
Maximizing this observed log-likelihood in order to compute an estimate of the parameter vector Ψ is difficult. As mentioned in Section 2, computing these estimates would be straightforward, should the data at hand be precise and complete. Then, the model may be easily estimated by maximizing the complete likelihood (1c), or equivalently the complete log-likelihood :

log L(Ψ; y 1 , . . . , y n ) = K k=1 log π k n i=1 z ik - p 2 log(2π) K k=1 n i=1 z ik - 1 2 K k=1 n i=1 z ik log |Σ k | + (x i -ν k ) t Σ -1 k (x i -ν k ) . (7)

Gaussian fuzzy numbers: estimation via the FEM algorithm

As mentioned in Section 2.2, computing parameter estimates by maximizing the observed likelihood is difficult. It is possible to overcome this problem by using an extension of the expectation-maximization (EM) algorithm for fuzzy data, known as the fuzzy EM (FEM) algorithm [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF], which we briefly recall. Then, we assume that fuzzy instances are described by Gaussian possibility distributions. Although any kind of distribution may be used, in this particular case, closed forms may be obtained for the update equations of the parameters in the FEM algorithm.

The FEM algorithm

The FEM algorithm proceeds iteratively with the complete log-likelihood log L c (Ψ), alternating between two steps. At iteration q, the E-step consists in computing the expectation Q(Ψ; Ψ (q) ) of the complete log-likelihood with respect to the imprecisely observed data. The M-step is similar to that of the classical EM algorithm, and requires the maximization of Q(Ψ; Ψ (q) ) with respect to Ψ. The FEM algorithm alternatively repeats the E-and M-steps until the relative increase of the log-likelihood becomes smaller than some threshold. In [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF], it is shown that the FEM algorithm converges towards a local maximum of the observed log-likelihood. The proof is similar to that used in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] for assessing the convergence of the EM algorithm.

E-step

At iteration q, the E-step of the FEM algorithm consists in computing the expectation Q(Ψ; Ψ (q) ) of the complete log-likelihood [START_REF] Gil | Overview on the development of fuzzy random variables[END_REF] with respect to the imprecisely observed data:

Q(Ψ; Ψ (q) ) = E Ψ (q) [log L(Ψ; y 1 , . . . , y n )|ỹ 1 , . . . , ỹn ], (8)
where Ψ (q) is the current estimate of the parameter vector Ψ. We may remark that this expectation needs to be computed with respect to the imprecise observations of both the instances and class labels. For this purpose, we recall the following definitions of the conditional density g X (•|x) and conditional expectation E [X|x] of a random vector X with respect to a fuzzy event x:

g X (x|x) = µ x(x)g X (x) P(x) , (9a)
E [X|x] = x g X (x|x) dx. (9b)
Using Equations (9a)-(9b) in Equation (1b) gives

Q(Ψ, Ψ (q) ) = K k=1 log π k n i=1 t (q) ik - 1 2 K k=1 log |Σ k | n i=1 t (q) ik - np 2 log(2π) - 1 2 n i=1 K k=1 t (q) ik E Ψ (q) [(x i -ν k ) t Σ -1 k (x i -ν k )|x i , zi , Z ik = 1] EQF (q) . (10)
Let us define

p (q) ik = P Ψ (q) (x i , zi |Z ik = 1) = γ (q) ik δ (q) ik , (11a) p
(q) i = P Ψ (q) (x i , zi ) = K k=1 π (q) k p (q) ik , (11b)
where γ

(q) ik = P Ψ (q) (x i |Z ik = 1) and δ (q) ik = P Ψ (q) (z i |x i , Z ik = 1). Then, the quantity t (q)
ik in Equation ( 10) may be computed using Bayes' theorem:

t (q) ik = E Ψ (q) [Z ik |x i , zi ] = P Ψ (q) (Z ik = 1|x i , zi ), (12a)
= P Ψ (q) (Z ik = 1)P Ψ (q) (x i , zi |Z ik = 1) P Ψ (q) (x i , zi ) , (12b) = π (q) k γ (q) ik δ (q) ik p (q) i = π (q) k γ (q) ik δ (q) ik K l=1 π (q) l γ (q) il δ (q) il . ( 12c
)
Equation ( 10) explicitly involves the expression of the possibility distributions describing our imprecise knowledge of the instances at hand. In this section, we assume these fuzzy numbers to be Gaussian (Equation ( 2)). Let us adopt the following notations:

A (x i ) = µ xi (x)dx, (13a)
µ * xi (x) = µ xi (x) A (x i ) . ( 13b
)
It is obvious that µ * xi is a pdf, provided that A (x i ) is finite: it is positive, and its integral equals 1 by construction. Moreover, if µ xi satisfies (2), then µ * xi is the pdf of a multivariate Gaussian, and

A (x i ) = (2π) p/2 |S i | 1 2 µ * xi (x)dx = (2π) p/2 |S i | 1 2 . ( 14
)
Based on these quantities, we may provide simple expressions for γ (q) ik and t (q) ik , using Equation (4) and the key property that the product of two Gaussians is itself a Gaussian up to a normalization factor [66, page 200]:

µ * xi (x)g k (x) = κ ik g ik (x), (15a)
where g ik stands for the multivariate Gaussian pdf with mean vector m ik and covariance matrix Σ ik , and where these parameters, as well as the normalization term κ ik , are defined by

Σ ik = S -1 i + Σ -1 k -1 , (15b)
m ik = Σ ik S -1 i m i + Σ -1 k ν k , (15c)
κ ik = |2π (S i + Σ k )| -1 2 exp(- 1 2 (m i -ν k ) t (S i + Σ k ) -1 (m i -ν k )).(15d) Let g (q) k
stand for the estimate of g k obtained using the current fits ν

(q) k and Σ (q) k . Then, γ (q) ik = A (x i ) µ * xi (x)g (q) k (x)dx = A (x i ) κ (q) ik g (q) ik (x)dx = A (x i ) κ (q)
ik , (16a) whence:

t (q) ik = π (q) k δ (q) ik κ (q) ik l π (q) l δ (q) il κ (q) il . ( 16b
)
In the following, the current fits of these quantities at iteration q will be indicated by the adequate superscript as before.

A closed form for the conditional expectation of the quadratic form, denoted as EQF (q) in Equation [START_REF] Dubois | Ontic vs. epistemic fuzzy sets in modeling and data processing tasks[END_REF], may also be computed. First, note that this expectation needs only be conditioned with respect to xi , since it is conditional to the event Z ik = 1. Then, according to Equations (9a)-(9b),

EQF (q) = 1 γ (q) ik (x i -ν (q) k ) t Σ (q) k -1 (x i -ν (q) k )µ xi (x)g (q) k (x)dx, (17a)
which we may rewrite using Equations (13a-16a) as

EQF (q) = (x -ν (q) k ) t Σ (q) k -1 (x -ν (q) k ) g (q) ik (x)dx. (17b)
Thus, EQF (q) is the expectation of a quadratic function of a random vector X following a multivariate Gaussian distribution g

(q)
ik with expectation m (q) ik and covariance matrix Σ

(q)
ik (note that these values are computed by using the current fits for π

(q) k , ν (q)
k ,and Σ (q) k in the appropriate equations). Therefore:

EQF (q) = (m (q) ik -ν k ) t Σ (q) k -1 (m (q) ik -ν k ) + trace Σ -1 k Σ (q) ik . ( 18
)
Using this new expression, we may give an explicit formulation for Equation [START_REF] Dubois | Ontic vs. epistemic fuzzy sets in modeling and data processing tasks[END_REF]:

Q(Ψ, Ψ (q) ) = K k=1 log π k n i=1 t (q) ik - 1 2 K k=1 log |Σ k | n i=1 t (q) ik - np 2 log(2π) - 1 2 n i=1 K k=1 t (q) ik (m (q) ik -ν k ) t Σ -1 k (m (q) ik -ν k ) + trace(Σ -1 k Σ (q) ik ) . ( 19
)

M-step

In the M-step, new estimates of the parameters are computed so as to maximize the expectation [START_REF] Chau | Uncertain data mining: An example in clustering location data[END_REF]. The update equation of the parameters are obtained by setting the corresponding partial derivatives of [START_REF] Chau | Uncertain data mining: An example in clustering location data[END_REF] to zero. We detail hereafter the computation of these update equations.

Prior probabilities π k

The first-order derivative of Q(Ψ, Ψ (q) ) with respect to π k is:

∂Q(Ψ, Ψ (q) ) ∂π k = 1 π k n i=1 t (q) ik . (20a)
Thus, taking into account the constraint that the proportions π k sum to 1, it may easily be shown that

π (q+1) k = 1 n n i=1 t (q) ik . ( 20b
)
Expectations ν k Taking the derivative of Equation ( 19) with respect to ν k and setting it equal to zero, we get:

n i=1 Σ -1 k t (q) ik (m (q) ik -ν k ) = 0, (21a)
whence the update equation for the parameter ν k :

ν (q+1) k = n i=1 t (q) ik m (q) ik n i=1 t (q) ik . ( 21b
)
Covariance matrices Σ k Let us first recall some background notions of derivation with respect to elements of matrices. Let A be a matrix with entries a ij (i, j ∈ {1, . . . , p}), and let f (A) be a function of A. For convenience, we will define the derivative of f (A) with respect to A, written ∂f (A)/∂A, as the matrix with (i, j) th entry (∂f (A)/∂a ij ). First, let us recall that x t Ax = trace(AB), with B = xx t , which makes it possible to re-write Equation [START_REF] Chau | Uncertain data mining: An example in clustering location data[END_REF]:

Q(Ψ, Ψ (q) ) = K k=1 log π k n i=1 t (q) ik + 1 2 K k=1 log |Σ -1 k | n i=1 t (q) ik - np 2 log(2π) - 1 2 n i=1 K k=1 t (q) ik trace Σ -1 k B (q) ik , (22)
where

B (q) ik = (m (q) ik -ν k )(m (q) ik -ν k ) t + Σ (q) ik . (23)
Furthermore, we have:

∂ trace(AB) ∂A = B, (24a)
∂ log |A| ∂A = (A -1 ) t . ( 24b
)
Taking the derivative of Equation ( 22) with respect to Σ -1 k thus gives:

∂Q(Ψ, Ψ (q) ) ∂Σ -1 k = 1 2 Σ k n i=1 t (q) ik - 1 2 n i=1 t (q) ik B (q) ik . (25a)
Setting this partial derivative to zero gives the following update equation for the covariance matrix Σ k :

Σ (q+1) k = n i=1 t (q) ik B (q) ik n i=1 t (q) ik .
(25b)

Computational complexity

We conclude this section with a brief discussion on the computational complexity of our approach. More particularly, we compare our algorithm to the classical EM algorithm for GMM estimation. Let us stress out that at each iteration, both algorithms estimate the same parameters. However, for this purpose, the FEM algorithm requires to perform some additional computations, that we list below.

First of all, taking into account the partial class information when computing the posterior probability estimates t (q) ik necessits to perform n × K additional multiplications. The FEM algorithm also requires to compute the parameters m (q) ik and Σ (q) ik . The former necessits K inversions of a p×p matrix and (n+1)×K multiplications of a p × 1 vector by a p × p matrix. The latter involves K inversions and K additions of a p × p matrix. Note that the quantities S -1 i and S -1 i m i may be computed outside the main loop of the optimization procedure of the FEM algorithm and stored.

The complexity of these additional operations is O(K × p 2 × (n + p)), and can be further reduced if optimized algorithms are used for performing matrix inversions. This is comparable to the complexity of computing the n × K multivariate Gaussian densities. Overall, the computational complexities of the EM and FEM procedures thus have the same order of magnitude.

General case: the Monte-Carlo FEM algorithm

In this section, we address the case where the possibility distributions representing the partial knowledge of the instance values are not Gaussian. In this general case, computing EQF (q) (Equation ( 10)) may be intractable: thus, it may not be possible to obtain closed-forms for the update equations of the parameters. Therefore, we propose an efficient Monte-Carlo estimation technique to approximate this quantity, making it possible to proceed with any kind of weak knowledge of the instance values.

Monte-Carlo strategy

Monte-Carlo estimation consists in replacing the expectation of a function ϕ(X) by an average of M terms ϕ(x (ℓ) ), ℓ = 1, . . . , M , where x (1) , . . . , x (M) are sampled according to the distribution of X. In our case, a straightforward application of this principle would lead, at iteration q, to sample the data according to g

(q)
k , yielding the following estimate for EQF (q) :

EQF (q) = 1 γ ik (q) 1 M M ℓ=1 (x (ℓ) -ν k ) t Σ -1 k (x (ℓ) -ν k ) µ xi (x (ℓ) ), (26a) γ ik (q) = 1 M M ℓ=1 µ xi (x (ℓ) ). ( 26b
)
However, we may remark the following points. First, the support of each possibility distribution µ xi is likely to cover a very small part of the input space. Hence, the number M of terms generated according to g (q) k should be large enough to ensure that a sufficient amount of these terms belong to this support; otherwise, the Monte-Carlo strategy would yield poor estimates of the parameters. This strategy thus becomes intractable in high dimension, due to the curse of dimensionality. 3 In addition, we may remark that, since the vector of parameters Ψ is updated at each iteration of the EM algorithm, so should be the sample.

Therefore, from a computational point of view, it seems much more efficient to sample the data according to the normalized possibility distributions µ * xi characterizing the fuzzy observations. Indeed, with such a strategy, data are sampled only once, before the parameter estimates are iteratively computed. The Monte-Carlo strategy thus defined is also generic: the sampling step being dissociated from the estimation step, any kind of possibility distribution may be used, provided that the adequate sampler is available. Finally, all the data points generated in this fashion obviously fall within the support of the densities g k . This Monte-Carlo strategy, applied to the FEM algorithm, will hereafter be referred to as the MCFEM algorithm.

GMM estimation via the MCFEM algorithm E-step

Our goal here is to estimate the integral in Equation (17a), which is generally intractable. For this purpose, let us rewrite Equation (10) using Equations (13a) and (13b):

Q(Ψ, Ψ (q) ) = K k=1 log π k n i=1 t (q) ik - 1 2 K k=1 log |Σ k | n i=1 t (q) ik - np 2 log(2π) - 1 2 K k=1 n i=1 t (q) ik A (x i ) γ (q) ik (x -ν k ) t Σ -1 k (x -ν k ) µ * xi (x) g (q) k (x) dx. ( 27
)
As stressed in Section 3, the normalized possibility distributions µ * xi satisfy the requirements of a probability distribution. Thus, they may be used to sample data, which makes it possible to estimate EQF (q) by EQF

(q) ≃ 1 M M ℓ=1 (x i -ν k ) t Σ (q) k -1 (x i -ν k ) g (q) k (x (ℓ) i ), (28)
where the M instances x

i , . . . , x

i , . . . , x (M) i are sampled according to µ * xi . This leads to the following Monte-Carlo approximation to Equation [START_REF] Dubois | Ontic vs. epistemic fuzzy sets in modeling and data processing tasks[END_REF]:

Q(Ψ, Ψ (q) ) ≃ K k=1 log π k n i=1 t (q) ik - 1 2 K k=1 log |Σ k | n i=1 t (q) ik - np 2 log(2π) - 1 2 K k=1 n i=1 t (q) ik A (x i ) γ (q) ik 1 M M ℓ=1 (x (ℓ) i -ν k ) t Σ -1 k (x (ℓ) i -ν k ) g (q) k (x (ℓ) i ). ( 29
)
Note that this expression may be further simplified using the following approximation to γ ik :

γ ik A (x i ) = A (x i ) µ * xi (x) g (q) k (x)dx ≃ 1 M M f ℓ=1 g k (x (ℓ) i ). ( 30
)
By dividing both the numerator and denominator in Equation (12c) by A (x i ), and using Equation (30), we get the following update equation for t ik :

t (q) ik ≃ π (q) k δ ik M ℓ=1 g (q) k (x (ℓ) i ) k π (q) k δ ik M ℓ=1 g (q) k (x (ℓ) i ) . ( 31
)

M-step: update equations of the parameters

The M-step is the same as in the case of Gaussian fuzzy numbers. Setting the partial derivatives of Equation ( 29) with respect to the parameters to zero gives the same update equations of the parameters, defined by Equations (20b), (21b) and (25b):

π (q+1) k = 1 n n i=1 t (q) ik , ν (q+1) k = n i=1 t (q) ik m (q) ik n i=1 t (q) ik , Σ (q+1) k = n i=1 t (q) ik B (q) ik n i=1 t (q) ik , (32a) with m (q)
ik and B (q) ik being now defined by:

m (q) ik = M ℓ=1 g (q) k (x (ℓ) i ) x (ℓ) i M ℓ=1 g (q) k (x (ℓ) i ) , (32b)
B (q) ik = M ℓ=1 g (q) k (x (ℓ) i ) (x (ℓ) i -ν (q+1) k )(x (ℓ) i -ν (q+1) k ) t M ℓ=1 g (q) k (x (ℓ) i )
.

(32c)

Bayesian priors

Motivations

As mentioned previously, the convergence of the FEM algorithm to a local maximum for the observed log-likelihood has been proved in [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF]. Under some conditions on the initial values of the parameters, L is bounded from above. Since the observed log-likelihood increases at each iteration of the algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], the convergence is ensured. In practice, the algorithm is stopped when the relative increase of the observed likelihood is less than a given threshold ǫ. As noted in [68, page 85], in many practical applications, the EM algorithm converges to a local maximizer of the observed log-likelihood. However, it is underlined that this convergence towards nontrivial solutions relies on the compactness of the parameter space. This assumption may not hold in certain cases. For example, when computing ML estimators of the parameters in a mixture of Gaussians, setting the mean of a class to be one of the data points and letting its variance tend to zero will let L(Ψ) tend to infinity. In practice, such a behaviour may be observed particularly when few data are available. It is interesting to note that in our case, this behaviour will more generally depend on the informational content of the data at hand. Indeed, the instances that are characterized by a high degree of imprecision (e.g., Gaussian fuzzy numbers with a large covariance matrix) will carry little information: the actual value for this instance may be located in a large area of the input space. Our experiments showed that a sample composed mostly of such imprecise instances is comparable to a sample with few precise instances.

To avoid degenerate solutions in the estimation process, we propose to integrate prior knowledge on the actual values of the parameters, using an adequate distribution p(Ψ) [START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF][START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF]. Then, the maximum a posteriori (MAP) estimate of the vector parameter Ψ may be computed so as to maximize the log (incomplete) posterior density log p(Ψ|ỹ 1 , . . . , ỹn ) = log L(Ψ|ỹ 1 , . . . , ỹn ) + log p(Ψ).

(

) 33
The log posterior density may be maximized using the FEM algorithm. The E-step consists in computing the expectation of Equation ( 33) with respect to the imprecisely observed data, using the current fits of the parameters. Since p(Ψ) does not depend on ỹ1 , . . . , ỹn , we have

E Ψ (q) [log p(Ψ|ỹ 1 , . . . , ỹn )] = Q(Ψ; Ψ (q) ) + log p(Ψ). (34)
In the M-step, new estimates are computed by setting the partial derivatives of this expectation to zero.

Conjugate priors

The analytic formulation for the update equations of the parameter estimates is simpler if p(Ψ) is a conjugate prior for the distribution of the model. Indeed, in this case, the derivatives of the log posterior density with respect to the parameters lead to simple update equations for the parameters.

In the case of a mixture of Gaussians, the normal-inverse-Wishart prior is commonly used to integrate background knowledge on the expectation vectors and on the covariance matrices [START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF]. More particularly, for the kth component, we have

log p(ν k , Σ k |ν k0 , n (1) k0 , Σ k0 , n (2) k0 ) = log g(ν k |ν k0 , Σ k /n (1) k0 ) + log h(Σ k |Σ k0 , n (2)
k0 ), (35a) where g is given by Equation (1b); and where h is defined, for any p×p symmetric positive-definite matrix, by:

h(Σ; Φ, τ ) = |Φ| τ 2 2 τ p 2 Γ p (τ /2) |Σ| -τ +p+1 2 exp - 1 2 trace ΦΣ -1 , (35b)
with Φ and τ being the parameters of this density function, and Γ p the multivariate Gamma function. Thus, in our case, a Gaussian prior g with mean ν k0 and covariance matrix Σ k /n [START_REF] Redner | Mixture densities, maximum likelihood and the em algorithm[END_REF] k0 is put on the expectation vector m k , and an inverse-Wishart prior h with scale matrix Σ k0 and parameter n

(2) k0 is put on the covariance matrix Σ k . Here, n

(1) k0 and n

(2) k0 are the numbers of degrees of freedom associated with the Gaussian and inverse-Wishart distributions, respectively. Note that Bayesian regularization for multivariate GMM is discussed in [START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF][START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF], in which many details on the calculation of the parameter estimates may be found.

Update equations

The log priors write

log g(ν k |ν k0 , Σ k /n (1) k0 ) = - p 2 log(2 π) + p 2 log n (1) k0 + 1 2 log |Σ -1 k | - n (1) k0 2 (ν k -ν k0 ) t Σ -1 k (ν k -ν k0 ) , (36a) log h(Σ k |Σ k0 , n (2) k0 ) = n (2) k0 2 log |Σ k0 | + n (2) k0 + p + 1 2 log |Σ -1 k | - 1 2 trace Σ k0 Σ -1 k - n (2) k0 p 2 log(2) -log Γ p ( n (2) k0 2 ). ( 36b
)
Expectations m k Since the inverse-Wishart distribution does not depend on ν k , the partial derivative of the overall log prior with respect to ν k is

∂ log g(ν k |ν k0 , Σ k /n (1) k0 ) ∂ν k = n (1) k0 2 Σ -1 k (ν k -ν k0 ) . ( 37a
)
Thus, adding this term to the partial derivative of Q(Ψ; Ψ (q) ) with respect to ν k gives the following update equation for the expectation vector when a Gaussian prior is employed:

ν (q+1) k = n i=1 t (q) ik m (q) ik + n (1) k0 ν k0 n i=1 t (q) ik + n (1) k0 , ( 37b
) with m (q)
ik being defined either by Equation (15c) in the case of Gaussian fuzzy numbers, or by Equation (32b) when using the MCFEM algorithm.

Covariance matrices Σ k

The partial derivative of the overall log prior with respect to Σ -1 k writes as

∂ log p(ν k , Σ k |ν k0 , n (1)
k0 , Σ k0 , n (2)
k0 ) ∂Σ -1 k = 1 2 Σ k - n (1) k0 2 (ν k -ν k0 ) (ν k -ν k0 ) t + n (2) k0 + p + 1 2 Σ k - 1 2 Σ k0 . (38a)
This leads to the following update equation for the covariance matrix Σ k , when the likelihood is regularized using a normal-inverse-Wishart prior:

Σ (q+1) k = n i=1 t (q) ik B (q) ik + n (1) k0 ν (q+1) k -ν k0 ν (q+1) k -ν k0 t + Σ k0 n i=1 t (q) ik + n (2) k0 + p + 2 , (38b)
where

B (q)
ik is defined by Equation [START_REF] Aggarwal | On density based transforms for uncertain data mining[END_REF] when the data at hand are Gaussian fuzzy numbers, or by Equation (32c) for the MCFEM algorithm.

Experiments

In this section, we first present results obtained by clustering synthetic data, in order to assess the robustness of our algorithm to noise and to the lack of information. Then, we present experiments realized on classical real datasets, in which quadratic discriminant analysis is used in presence of corrupted data. (2, 1) t (0, -2) t (-2, 1) t Σ k 2 0 0 1 1 0.5 0.5 1.25 1.5 0.75 0.75 1.5

Synthetic data Noisy instances

First, we ran an experiment using synthetic two-dimensional data in order to evaluate the performance of our algorithms in presence of data with corrupted instance values. More precisely, we generated the data so that the level of imprecision on the instances depends on the magnitude of the instance values. First, we drew a sample of n = 1000 realizations x 1 , . . . , x n of a Gaussian mixture of K = 3 components with the parameters given in Table 1. Then, we introduced noise in the data as follows. For each instance x i , we randomly generated a covariance matrix W i according to an inverse-Wishart distribution with 4 degrees of freedom, and we set then S i = λW i . The scalar λ ∈ {2, 4, . . . , 20} makes it possible to set the degree of imprecision introduced in the data. For each instance x i , a noisy value m i was then generated from a multivariate Gaussian with mean x i and covariance matrix S i .

We thus created a set of Gaussian fuzzy numbers with mean value m i and covariance matrix S i . We also defined a set of trapezoidal fuzzy numbers, such that the support and the core of the ith element are the squares containing respectively 95% and 50% of the Gaussian distribution with mean w i and covariance matrix S i . The parameters (a ij , d ij ) and (b ij , c ij ), that respectively define the support and the core along the jth dimension (j ∈ {1, 2}), are thus

a ij = wij + σi Φ -1 ( 1- √ 0. 95 2
),

d ij = wij + σi Φ -1 ( 1+ √ 0.95 2 ), b ij = wij + σi Φ -1 ( 1- √ 0.5 2 ), c ij = wij + σi Φ -1 ( 1+ √ 0. 5 2
);

(39) where wij denotes the jth component of w i , and where Φ stands for the cumulative distribution function of the centered and scaled Gaussian distribution.

We estimated the parameters of a GMM with three components as follows. The original (precise, uncorrupted) data and the precise corrupted ones were processed using the EM algorithm. The Gaussian fuzzy instances were clustered using the Gaussian FEM algorithm. The MCFEM algorithm was used in the case of trapezoidal fuzzy instances: for this purpose, M = 200 instances were generated according to each trapezoidal distribution using the procedure described in AppendixA. For each value of λ, we ran each algorithm five times. The starting values were computed using 10% of randomly selected instances in each class (the same for all the algorithms). The labels of these instances were considered as known throughout the estimation process. We stopped iterating when the relative increase of the log-likelihood becomes small, i.e. log L(Ψ (q) ) -log L(Ψ (q-1) )

| log L(Ψ (q-1) )| ≤ 10 -5 .

Then, for each algorithm, we kept the best solution over the five trials in terms of observed log-likelihood. Each instance x i was classified so as to maximize the estimated posterior probabilities t (q)

ik . The adjusted Rand index (ARI) [START_REF] Hubert | Comparing partitions[END_REF] was then computed in order to assess the accuracy of the partition thus obtained. We recall here that the ARI is a corrected-for-chance version of the Rand index, a popular measure frequently employed to compare two partitions. This whole procedure (data generation and corruption, model estimation, and assessment of the accuracy of the partition thus obtained) was repeated 50 times, so that averages of the ARI may be computed.

Figure 1 displays the evolution of the average ARI as a function of the degree of noise λ introduced in the instances. Without surprise, the partitions computed from noisy data exhibit a poor accuracy when the amount of noise increases. However, taking into account the uncertainty on the attribute values improves the robustness of the model, and the partition thus obtained is closer to the actual partition of the data. that the parameters (and in particular the covariance matrices) computed using the crisp EM algorithm are sensitive to the presence of noisy data. However, taking into account the attribute uncertainty using the FEM algorithm yields more robust parameter estimates.

Corrupted labels

We realized an experiment on data with corrupted labels. We generated data as before, with λ = 2. Then, we introduced noise in the labeling: the actual labels were replaced by a random label with probability η. The probability η ∈ {0.1, 0.2, . . . , 1} thus allowed us to control the level of noise introduced in the labels. Then, we compared the results obtained with two kinds of labeling:

• crisp labeling, which corresponds to a semi-supervised approach, where an instance x i is associated with a vector z i indicating its (possibly corrupted) associated label;

• imprecise labeling, where the partial knowledge of the actual class of an instance is represented using a possibility distribution.

In this last case, we followed [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF][START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF] and gave the observed label ω k a degree of possibility δ ik = 1, and the other plausible labels ω k ′ , k ′ = k a degree of possibility pl ik ′ = η.

As previously, we computed the average ARI over 50 randomly generated datasets. The data without label information and the data with noisy labels were clustered via the EM algorithm. The FEM and MCFEM algorithm were used to process the Gaussian and the trapezoidal fuzzy instances with plausibilistic labels, respectively. Figure 3 ing a semi-supervised labeling gives good results when the amount η of noise is low. As η increases, the accuracy of the obtained partition decreases. The results obtained using imprecise labels via the FEM and MCFEM algorithms are almost identical, and always better than those in the semi-supervised case. Remarkably, their poorest performance is achieved for η = 1: then, all the components being equally plausible, their accuracy is similar to that of the unsupervised EM algorithm.

Robustness to lack of data

We produce here the results of an experiment which purpose is to demonstrate how Bayesian priors may ameliorate the estimation of the parameters, as explained in Section 5. First of all, it should be pointed out that the amount of information contained in a fuzzy sample is directly related to the degree of imprecision of the data. Figure 4 displays the GMM estimated using the FEM algorithm on Gaussian fuzzy data with two levels of imprecision. The data were generated as before, with λ = 2 in one case and λ = 20 in the other case (the instances having the same mean values m i ). It may be observed that a high amount of imprecision results in a decrease of the trace of the estimated covariance matrices. To show the interest of using Bayesian priors, we generated Gaussian fuzzy data as previously, except that the mean m i of each Gaussian fuzzy number xi was set to x i : the data at hand are thus imprecise, but not noisy. Then, we clustered the imprecise data at hand using three different versions of the Gaussian FEM algorithm:

• without setting any prior on the model parameters;

• using the actual parameter values as prior: in this case, the degrees of freedom n

(1) k0 and n

k0 were set to n

k0 = 1e6 and n

(2) k0 = 1e -6 -2, respectively;

• using estimated priors obtained as follows: for each class ω k , we randomly selected a number n k of precise instances, corresponding to 25% of the instances in the class, which were used to compute estimates ν k and Σ k of the class parameters. Then, we set a Gaussian-inverse-Wishart prior on the kth component of the GMM, with mean ν k0 = ν k , covariance matrix Σ k0 = n Figure 5 displays the evolution of the average ARI, computed over 100 experiments, as a function of the degree of imprecision of the instances. We may notice that the ARI decreases while the level of imprecision λ increases, which shows that the accuracy of the model highly depends on the informational content of the data at hand. However, using Bayesian priors makes it possible to guide the algorithm towards more robust parameter estimates.

Real data

In this Section, we report the results obtained by applying GMM estimation to classification problems. We considered seven real datasets described in Table 2. For each dataset, we randomly selected 66% of the data for learning the parameters of a GMM. Note that in some datasets, one or several variables may be constant; such uninformative variables were suppressed to avoid numerical problems. The remaining variables were then centered and scaled. We introduced noise in the instance values as explained before, using a parameter value λ = 1 (note that the labels were left unchanged). Then, the parameters of each class were estimated from the noisy training instances, and from the fuzzy instances using the FEM algorithm. The remaining test instances were classified using quadratic discriminant analysis (QDA): no additional assumption was made on the covariance matrices of the classes. Conditional densities and then posterior probabilities were computed for each test instance using the parameters estimated, using Equation (16b) in the case of fuzzy instances. Since the imprecision of the instances may not be known for test labels, we performed two series of experiments. A first estimation of the posterior probabilities was performed using Equation (16b) using the actual covariance matrices generated to corrupt the data. Besides, we also estimated these covariance matrices, by averaging the ones used for the fuzzy training data.

This whole procedure (random selection of training and test sets, introduction of noise, estimation of the parameters, and classification of the test data) was repeated 25 times. Figures 6 to 11 present the classification accuracy obtained. The results obtained by classifying the uncorrupted and noisy test instances with the quadratic classifier trained from noisy data (boxplots 1 and 2, respectively) are referred to as "crisp QDA"; while "fuzzy QDA" refers to processing fuzzy test instances with a classifier estimated from fuzzy training data (boxplot 3 when the actual uncertainty of the test instances is used, and boxplot 4 for the estimated uncertainty). The results clearly assess the interest of our approach for estimating the parameters of the model. Indeed, taking into account the uncertainty on the training and test data makes it possible to achieve better results than ignoring this information. In addition, the results obtained with the fuzzy GMM with estimated covariance matrices is significantly better than the results obtained via the crisp GMM in three cases over six. This clearly advocates taking into account the uncertainty when processing data pervaded with noise.

Conclusion

In this paper, we addressed the problem of estimating the parameters of a GMM from imprecisely observed data. Our approach is based on an extention of the EM algorithm for fuzzy data proposed by Denoeux [START_REF] Denoeux | Maximum likelihood estimation from fuzzy data using the fuzzy EM algorithm[END_REF][START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF]. Given a sample of fuzzy numbers, the likelihood of a mixture of Gaussians is computed using Zadeh's definition of the probability of a fuzzy event. Then, the estimates maximizing this likelihood is estimated using an iterative procedure. At each iteration, the expectation of the log-likelihood with respect to the fuzzy sample is first computed. In a second step, the parameters of the model are updated so as to maximize this expectation.

We presented two main results. First, we showed that when the data are represented by Gaussian fuzzy numbers, closed-forms of the parameter estimates may be computed. Furthermore, we proposed a Monte-Carlo approach to estimate the parameters in the general case. This Monte-Carlo approach is generic, since it is suitable to any kind of possibility distribution, provided that an adequate sampler be available. It is also computationally efficient, since the sampling step is made only once, and outside of the estimation procedure.

We conducted experiments on synthetic and real data. The results show that our algorithm makes it possible to estimate accurately the distribution of imprecisely known data. In particular, taking into account all the available information on the data uncertainty makes it possible to compute robust estimates of the parameters in presence of noisy attributes and corrupted labels. When applied to the classification of noisy data via quadratic discriminant analysis, taking into account the uncertainty on the instance values makes it possible to improve the classification accuracy, even when the uncertainty on the test data is estimated from the training set. In conclusion, the results clearly shows the interest of our approach for performing clustering or classification in the presence of noisy or uncertain information.

Figure 1 :

 1 Figure 1: Evolution of the average adjusted Rand index as a function of the degree of noise λ in the data. The values of the average Rand index and the 95% confidence intervals are computed over 50 experiments.

Figure 2

 2 Figure 2 presents the results obtained for one experiment with λ = 20. The instances are printed with a color depending on the component from which they were generated. The mean vectors thus obtained are displayed, along with the

Figure 2 :

 2 Figure 2: Original data (top left), noisy data (top right), Gaussian (bottom left) and trapezoidal (bottom right) fuzzy data, along with the parameters estimated using the EM algorithm (top) and the fuzzy EM algorithm (bottom).

  displays the ARI as a function of the degree of noise η introduced in the labels. Estimating the parameters of the model us-

Figure 3 :

 3 Figure 3: Evolution of the adjusted Rand index as a function of the degree of noise η in the labels. The values of the average Rand index and the 95% confidence intervals are computed over 50 experiments.

Figure 4 :

 4 Figure 4: Parameters estimated using the FEM algorithm on Gaussian fuzzy data, for a low (left) and a high (right) amount of imprecision λ in the data. The trace of the estimated covariance matrices decreases when the level of imprecision increases.

( 2 ) 1 )k0 = n k and n ( 2 )

 212 k0 Σ k , and degrees of freedom n(k0 = n k -2, respectively.

Figure 5 :

 5 Figure 5: Evolution of the adjusted Rand index as a function of the level of imprecision λ in the instances. The values of the average Rand index and the 95% confidence intervals are computed over 50 experiments.

Figure

  Figure 6: Classification accuracy, Iris dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty.

Table 1 :

 1 Parameters of the components of the Gaussian mixture.

		comp. 1	comp. 2	comp. 3
	π k	0.4	0.25	0.35
	ν k

Table 2 :

 2 Characteristics of the real datasets processed.

	dataset	number of number of number of
		instances	classes	variables
	Iris	150	3	4
	Letter	18200	26	16
	Pageblocks	5473	5	10
	Pendigits	10992	10	16
	Satimage	6435	6	36
	Waveform	5000	3	21

  6: Classification accuracy, Iris dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty. Figure 7: Classification accuracy, Letter dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty. Figure 8: Classification accuracy, Pageblocks dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty. Figure 9: Classification accuracy, Satimage dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty. Figure 10: Classification accuracy, Pendigits dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty. Figure 11: Classification accuracy, Waveform dataset. Boxplot 1: crisp QDA, uncorrupted test data; boxplot 2: crisp QDA, noisy test data; boxplot 3: fuzzy QDA, test data with actual uncertainty; boxplot 4: fuzzy QDA, test data with estimated uncertainty.

		0.21
		0.24 0.19 0.2
		0.22 0.19
	classification error rate classification error rate classification error rate	0.16 0.18 0.2 0.16 0.17 0.18 0.16 0.17 0.18
		0.15
		0.14 0.15
		0.14 0.14
		0.12
			1	2	3	4
		0.13
			1 1	2 2	3 3	4 4
		0.065
		0.09
		0.06
		0.085
		0.055
		0.08
	classification error rate classification error rate	0.065 0.07 0.075 0.035 0.04 0.045 0.05
		0.06
		0.03
		0.055
		0.05 0.025
		0.02 0.045	1 1	2 2	3 3	4 4

It should be noted that, due to the strong relationships between both formalisms, the work presented in the fuzzy case may be straightforwardly extended to the credal case.

Note that we may restrict the sampling process to regions of the space where the fuzzy instances lie, e.g., using truncated multivariate Gaussian distributions[START_REF] Chopin | Fast simulation of truncated Gaussian distributions[END_REF]. However, the use of such distributions with reasonable complexity is still an open problem. Besides, when the number of features p is arbitrary, computing a closed-form of the support of the possibility distributions (in order to truncate the Gaussians) is also intractable.

Acknowledgements

This work was carried out in the framework of the Labex MS2T, which was funded by the French Government, through the program "Investments for the future" by the National Agency for Research (reference ANR-11-IDEX-0004-02).

AppendixA. Sampling according to trapezoidal possibility distributions

We provide here details about sampling according to trapezoidal-based multivariate fuzzy numbers. We assume here that each multivariate possibility distribution µ xi associated with xi may be expressed as the product of the unidimensional possibility distributions µ xij of its components xij :

Thus, data may be sampled feature-wise and aggregated. Let us denote by x following the multivariate distribution µ xi may then be obtained by concatenating these one-dimensional samples: we obtain x

To obtain an univariate sample x (1) , . . . , x (M) from a parent variable according to a univariate trapezoidal distribution, we propose the following procedure. Let F be the cumulative distribution function of the trapezoidal distribution. First, a random sample u (1) , . . . , u (M) is generated according to an uniform distribution U [0;1] . Then, the inverse cdf F -1 is applied to these numbers to obtain the univariate sample:

We provide below the expression of the cumulative distribution function F x associated with an univariate trapezoidal fuzzy number x with support [a; d] and core [b; c], as well as of its inverse F -1

x . Details may be found in [START_REF] Kacker | Trapezoidal and triangular distributions for Type B evaluation of standard uncertainty[END_REF].

Thus, the inverse cdf F -1

x is defined, for all u ∈ [0; 1], by:

(A.5)