BPEC: Belief-Peaks Evidential Clustering Zhi-gang Su and Thierry Denoeux

Abstract-This paper introduces a new evidential clustering method based on the notion of "belief peaks" in the framework of belief functions. The basic idea is that all data objects in the neighborhood of each sample provide pieces of evidence that induce belief on the possibility of such sample to become a cluster center. A sample having higher belief than its neighbors and located far away from other local maxima is then characterized as cluster center. Finally, a credal partition is created by minimizing an objective function with the fixed cluster centers. An adaptive distance metric is used to fit for unknown shapes of data structures. We show that the proposed evidential clustering procedure has very good performance with an ability to reveal the data structure in the form of a credal partition, from which hard, fuzzy, possibilistic and rough partitions can be derived. Simulations on synthetic and real-world datasets validate our conclusions.

Index Terms-Dempster-Shafer theory, belief functions, unsupervised learning, soft clustering, density peaks clustering.

I. INTRODUCTION

C LUSTERING is one of the most important tasks in data mining and machine learning. It aims to find groups or clusters of objects that are similar to one another but dissimilar to objects in any other clusters. With different philosophies, distinct clustering techniques have been derived, for example, see [START_REF] Bouveyron | Model-based clustering of high-dimensional data: A review[END_REF]- [START_REF] Saxena | A review of clustering techniques and developments[END_REF] and the literature therein. Among them, partitional clustering has attracted a lot of attention in artificial intelligence communities.

Classical hard partitional clustering intends to assign each object unambiguously to one cluster with full certainty. Recently, Rodriguez and Laio proposed such a hard partitional clustering algorithm by fast search and find of density peaks, called density peaks clustering (DPC) [START_REF] Rodriguez | Clustering by fast search and find of density peaks[END_REF]. In the DPC, a cluster center is defined as an object surrounded by neighbors with lower local densities and far away from any other object with higher local density. In order to detect all the cluster centers, density

ρ i ρ i = j =i χ(d ij , d c ) (1)
is first computed at each data object o i according to distance d ij (between objects o i and o j , i = 1, 2, • • • , n, j = i) using a cutoff or Gaussian kernel χ(•, •) with cutoff distance d c . Next, for each object, the distance δ i separating it from its nearest object with a higher density is computed as By drawing a decision graph with ρ and δ as x-and y-axes, respectively, cluster centers are then defined as the data objects that have both high density and large distance. At last, each of the remaining data objects is assigned heuristically to the same cluster as its nearest neighbor with higher density. One merit of the DPC algorithm is its ability to detect cluster centers without requiring to fix the number of clusters as priori. Therefore, a lot of interesting work on DPC has emerged. See, for example, [START_REF] Courjault-Rade | Improved density peak clustering for large datasets[END_REF]- [START_REF] Xie | Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors[END_REF]. However, the DPC and its variants compute hard partitions: they do not allow ambiguity, uncertainty or doubt (rather than noise) in the assignment of objects to clusters. As illustrated in Fig. 1, the objects between or among different clusters should be considered as ambiguous and/or uncertain. In contrat, evidential clustering [START_REF] Denoeux | Evidential clustering: a review[END_REF], [START_REF] Antonie | CECM: Constrained evidential c-means algorithm[END_REF]- [START_REF] Zhou | Median evidential c-means algorithm and its application to community detection[END_REF] allows us to describes ambiguity and uncertainty in the membership of objects to clusters using Dempster-Shafer mass functions [START_REF] Shafer | A mathematical theory of evidence[END_REF]. Roughly speaking, a mass function can be seen as a collection of sets with corresponding masses. A collection of such mass functions for n objects is called credal partition.

δ i = max 1≤j≤n {d ij }, if i = arg max j {ρ j }, min j:ρj >ρi {d ij }, otherwise. (2)
Furthermore, in DPC algorithms, each object in the neighborhood of a sample provides just a numerical measure (i.e., a cutoff or Gaussian kernel function value of the distance between the object and the sample) supporting such sample to become a cluster center. As a matter of fact, an object in the neighborhood of a sample could provide more useful information on the possibility of such sample to become a cluster center. With this in mind and the theoretic viewpoint of belief functions, we may describe the support degree at each object by a mass function. The belief degree (associated to a mass function) at each data object can then be viewed as an extension of the (local) density in DPC algorithms. As we will see, the cluster centers selected according to belief peaks are usually different from, and more appropriate than those obtained by density peaks. For instance, in Fig. 1, object o 2 can be selected as a cluster center according to density peaks, whereas the object o 1 is preferred by belief peaks, as will be discussed in Section III-A.

Motivating by the above considerations, this paper intends to propose a new evidential clustering method based on finding belief (rather than density) peaks as well as a credal partition in the theoretic framework of belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF]- [START_REF] Smets | The transferable belief model[END_REF]. More precisely, all data objects in the neighborhood of each sample provide pieces of evidence on the possibility of such sample to become a cluster center. Then, by combing these pieces of evidence, a sample having higher belief than its neighbors and located far away from other local maxima will be characterized as a cluster center. Once all the cluster centers have been fixed, a credal partition will finally be created by minimizing an objective function, using an adaptive distance metric to describe non-spherical clusters. In this paper, we call our method Belief-Peaks Evidential Clustering (BPEC). The philosophy of BPEC is distinct from that of the DPC in several respects:

• BPEC selects cluster centers from the viewpoint of information fusion in the theoretic framework of belief functions, considering more useful information on the possibility of a data object to become a cluster center. • BPEC creates a credal partition allowing ambiguity and uncertainty in the assignment of data objects, by solving a constrained optimization problem (with fixed cluster centers) as an alternative to heuristic assignment. • The credal representation in the BPEC provides us a flexible way to reveal the data structure and, in particular, it can produce hard, fuzzy [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithm[END_REF], possibilistic [START_REF] Krishnapuram | A possibilistic approach to clustering[END_REF] and rough [START_REF] Lingras | Applying rough set concepts to clustering[END_REF], [START_REF] Peters | Is there any need for rough clustering?[END_REF] partitions. As will be shown in Section IV, the BPEC procedure has good performances and outperforms the standard DPC algorithm as well as some other evidential clustering algorithms in most cases.

The rest of this paper is organized as follows. The theory of belief functions and the notion of credal partition are first briefly recalled in Section II. The BPEC method is then introduced in Section III. In Section IV, we conduct some experiments to study the performances of BPEC using some synthetic and real-world datasets. The last section concludes the paper.

II. PRELIMINARIES A. Background on belief functions

In this subsection, we briefly recall some basic notions of the theory of belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF]- [START_REF] Smets | The transferable belief model[END_REF], [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]- [START_REF] Shafer | A mathematical theory of evidence turns 40[END_REF] needed in the rest of the paper. Given a frame of discernment

Ω = {ω 1 , ω 2 , • • • , ω c }, a mass function is defined as a mapping from 2 Ω to [0, 1] such that A⊆Ω m Ω (A) = 1. (3)
The subsets A of Ω such that m Ω (A) > 0 are called the focal sets of m Ω . A mass function is said to be

Bel Ω (A) = ∅ =B⊆A m Ω (B), (4)
P l Ω (A) = A∩B =∅ m Ω (B), (5)
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, we have pl Ω (ω) = m Ω ({ω}) for all ω ∈ Ω. In this case, pl Ω is a probability distribution. The combination of mass functions plays a critical role in the theory of belief functions. Let m 1 and m 2 be two mass functions. The conjunctive combination of m 1 and m 2 yields the unnormalized mass function

m Ω 1∩2 (A) = B∩C=A m Ω 1 (B)m Ω 2 (C), ∀A ⊆ Ω. (6)
If necessary, the normality condition m Ω (∅) = 0 may be recovered by dividing each mass m Ω 1∩2 (A) by 1 -m Ω 1∩2 (∅). The resulting operation is noted ⊕ and is called Dempster's rule of combination:

m Ω 1 2 (A) = m Ω 1∩2 (A) 1 -m Ω 1∩2 (∅) , ∅ = A ⊆ Ω. (7)
Both rules are commutative, associative and admit the vacuous mass function as a unique neutral element.

B. Credal partitions

Suppose that we have a set

O = {o 1 , o 2 , • • • , o n } of n objects. Let Ω = {ω 1 , ω 2 , • • • , ω c } be the set of c clusters.
If we know for sure which cluster each object belongs to, we have a hard partition of the dataset O. More precisely, a hard partition may be represented by binary variables u ik such that u ik = 1 if object o i belongs to cluster ω k , and u ik = 0 otherwise.

When objects cannot be assigned to clusters with certainty, one can represent ambiguous and uncertain cluster memberships by mass functions

m Ω i , i = 1, 2, • • • , n. Each mass m Ω i (A)
is interpreted as a degree of support attached to the proposition "the true cluster of object o i is in A", and to no more specific proposition. The n-tuple [START_REF] Denoeux | Evidential clustering: a review[END_REF], [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF].

M Ω = (m Ω 1 , m Ω 2 , • • • , m Ω n ) is called a credal partition
Example 1: The 4-tuple M Ω = (m Ω 1 , m Ω 2 , m Ω 3 , m Ω 4
) in Table I is an example of a credal partition. We can see that objects o 1 and o 3 likely belong to ω 1 and ω 2 , respectively. The notion of credal partition boils down to several other usual clustering structures when the mass functions have some special types [START_REF] Denoeux | Evidential clustering: a review[END_REF].

• Hard partition: We have a hard partition with u ik = 1 if all mass functions m Ω i are certain, i.e., m Ω i ({ω k }) = 1 for some k, and u ik = 0 otherwise.

• Fuzzy partition: We have a fuzzy partition with u ik = m Ω i ({ω k }) if all the mass functions m Ω i are Bayesian. In particular, a fuzzy partition with a noise cluster may be obtained if all the mass functions m Ω i are unnormalized Bayesian, i.e., if

u ik = m Ω i ({ω k }) and u i * = m Ω i∅ = m Ω i (∅) = 1 - c k=1 u ik . • Possibilistic partition: if masses m Ω
i are consonant, the corresponding plausibility function is formally a possibility measure, and the credal partition can be seen as a possibilistic partition, u ik = pl Ω i (ω k ) being interpreted as the possibility that object o i belongs to cluster ω k .

• Rough partition: if masses m Ω i are logical, i.e., we have m Ω i (A i ) = 1 for some ∅ = A i ⊆ Ω, we can then define the lower and upper approximations of cluster ω k as

ω L k = {o i |A i = {ω k }}, ω U k = {o i |{ω k } ⊆ A i }. (8)
The memberships to the lower and upper approximations are then, respectively, u ik = Bel Ω i ({ω k }) and ūik = P l Ω i ({ω k }). In general the credal partition obtained by an evidential clustering algorithm does not belong to any of the previous specific types, but it can be transformed into a simpler representation. A fuzzy partition can be obtained by transforming each mass function m Ω i into a probability distribution p i using the plausibility-probability transformation defined by

p i (ω k ) = pl Ω i (ω k ) c l=1 pl Ω i (ω l ) , k = 1, 2, • • • , c. (9)
By selecting the cluster with maximum probability for each object, we get a hard partition. To obtain a fuzzy partition with a noise cluster, the degree of membership of each object o i to cluster ω k can be defined as

u ik = (1 -m Ω i∅ )p i (ω k
) and the degree of membership to the noise cluster as u i * = m Ω i∅ . To obtain rough partition, for instance, the following interval dominance decision rule [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] can be used to select the set A i of clusters whose plausibility exceeds the degree of belief of any other clusters,

A i = {ω ∈ Ω|∀ω ∈ Ω, pl Ω i (ω) ≥ Bel Ω i ({ω })}, (10)
where pl Ω i and Bel Ω i are the normalized contour and belief functions associated to mass function m Ω i .

III. PROPOSED METHOD: BPEC

Similar to DPC algorithms, the BPEC algorithm also consists of two parts: definition of cluster centers and assignment of the remaining data objects. These two parts will be discussed in Sections III-A and III-B, respectively. In Section III-C, the time complexity of BPEC will be analyzed and a variant with a limited number of informative composite clusters will be introduced. The tuning of parameters will be addressed in Section III-D.

A. Belief peaks

For a given set O of n data objects, a new frame of discernment C = {C, ¬C} is defined to discern whether an object is a cluster center (C) or not (¬C). The basic idea to detect cluster centers can be summarized as follows. Let N K (o i ) denote the set of the K nearest neighbors (KNN) of object o i . Each neighbor o j in N K (o i ) provides a piece of evidence about object o i being a cluster center. This piece of evidence can be represented by a mass function m C ij . By combining these mass functions using Dempster's rule ( 6)-( 7), a normalized mass function m C i can be obtained as well as its associated belief function Bel C

i . An object having higher degree of belief Bel C i ({C}) than its neighbors will be characterized as a cluster center if it is also at a relatively large distance from other objects with higher degrees of belief.

Each neighbor o j in N K (o i ) supports the assumption that o i is a cluster center if the distance d ij between the two objects is small. If this distance is large, the evidence of object o j is inconclusive. Mass function m C ij can, thus, be defined as

m C ij (A) = φ(d 2 ij ), A = {C}, 1 -φ(d 2 ij ), A = C, (11)
where φ(•) is a decreasing function verifying φ(0) = α 0 and lim

d 2 ij →∞ φ(d 2 ij ) = 0 (12)
with a constant α 0 such that 0

< α 0 ≤ 1. A popular choice for φ(•) is [27], [28] φ(d 2 ij ) = α 0 exp(-γ 2 i d 2 ij ), (13)
where γ i is a positive parameter associated to object o i . Using Dempster's rule, the final normal mass function m C i for object o i can be calculated as

m C i = j∈NK (oi) m C ij . (14)
According to [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], we have the following proposition used to calculate belief Bel C i ({C}) at data object o i .

Proposition 1: The degree of belief that object o i is a cluster center is

Bel C i ({C}) = 1 - j∈NK (oi) 1 -φ(d 2 ij ) . ( 15
)
Proof: The combined mass function has two focal sets: C and {C}. The mass on C is the product of the 1 -φ(d ij ), so the mass on {C} is 1 minus this product. Hence, we have

m C i (C) = j∈N K (o i ) 1 -φ(d 2 ij ) (16)
and

m C i ({C}) = 1 - j∈N K (o i ) 1 -φ(d 2 ij ) . ( 17
)
Now,

Bel C i ({C}) = m C i ({C})
, which completes the proof. Proposition 1 provides us with the final belief on the possibility of an object to become a cluster center. According to the basic idea of BPEC, to be a cluster center an object should not only have high degree of belief, but it should also be located far away from other objects with high degrees of belief. Hence, a metric should be defined in order to measure distances among objects, as that done in DPC. Here, we redefine the delta metric δ i in (2), as follow

δ i = min {j:Bel C j ({C})>Bel C i ({C})} d ij (18)
for objects that do not have the highest degree of belief and δ i = max 1≤j≤n {d ij } for the object with the highest degree of belief. Now, we can construct a δ -Bel C ({C}) (δ -Bel for short) decision graph by plotting Bel C ({C}) versus δ. The objects with higher Bel C i ({C}) and larger δ i are identified as cluster centers. As illustrated in Fig. 2, cluster centers usually appear in the upper right corner of the decision graph. For given lower bounds δ min and Bel min , the objects such that δ i > δ min and Bel C i ({C}) > Bel min will be selected as centers. Meanwhile, data objects with small degrees of belief and large deltas can be detected as outliers from the decision graph.

Remark 1: There exist some relationships between the belief (Bel C i ({C})) and the density (ρ i ) in DPC algorithms. Four typical densities ρ i are briefly recalled as follows. With Gaussian kernel, i.e., χ(

d ij , d c ) = φ(d 2 ij ) with α 0 = 1 and γ i = 1/d c , density (1) can be rewritten as ρ i := n j=1 φ(d 2 ij ).
To reduce the influence of data objects far away, the density can be locally defined as

ρ i := j∈NK (oi) φ(d 2 ij
), e.g., see the adaptive DPC (ADPC-KNN) [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF] in which

γ i = 1/(μ K + σ K ) such that μ K = 1 n n i=1 ν K i , σ K = 1 n-1 n i=1 (ν K i -μ K ) 2 and ν K i = max j∈N K (oi) (d ij )
. In [START_REF] Xie | Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors[END_REF], Xie et al. proposed a fuzzy weighted KNN-DPC (FKNN-DPC) in which the local density is defined as ρ i := j∈N K (oi) φ(d ij ) with α 0 = 1, γ i = 1 and non-squared Euclidean distance. In a different way, Du et al. [START_REF] Du | Study on density peaks clustering based on k-nearest neighbors and principal component analysis[END_REF] proposed a DPC-KNN algorithm in which the local density was defined as

ρ i := j∈N K (oi) φ(d 2 ij ) with
Bel C i ({C}) = (-1) K+1 j∈N K (o i ) φ(d 2 ij )+ j∈N K (o i ) φ(d 2 ij ) + l(φ(d 2 ij )) (19)
with a polynomial function l(•). It is evident that the belief Bel C i ({C}) can be viewed as an extension of densities defined in [START_REF] Rodriguez | Clustering by fast search and find of density peaks[END_REF] with K = n, [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF] and [START_REF] Du | Study on density peaks clustering based on k-nearest neighbors and principal component analysis[END_REF]. If one uses a non-squared distance, then Bel C i ({C}) is an extension of the local density in [START_REF] Xie | Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors[END_REF]. The distribution of cluster centers via the BPEC is usually different from and arguably more appropriate than those obtained by these DPC algorithms. To show this, a numerical example is presented as follows, and another synthetic example will be presented later in Example 4.

2 ij ) = φ(d 2 ji ), i, j = 1, 2, • • • , 9. For simplicity, this example considers ρ i = j∈N K (oi) φ(d 2 ij
) with K = 3. We have ρ 1 = 0.45 + 0.9 + 0.3 = 1.65, ρ 2 = 0.7 × 2 + 0.35 = 1.75, ρ 3 = 0.9 + 0.35 + 0.25 = 1.5, ρ 4 , ρ 5 < 0.5 + 0.7 + 0.2 = 1.4, ρ 6 < 0.45 + 0.25 + 0.2 = 0.9, ρ i < 0.2 × 3 = 0.6, i = 7, 8, 9. According to [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF], we can obtain

Bel C 1 ({C}) = 1 -0.1 × 0.55 × 0.7 = 0.9615, Bel C 2 ({C}) = 1 -0.3 2 × 0.65 = 0.9415, Bel C 3 ({C}) = 1 -0.1 × 0.65 × 0.75 = 0.95125, Bel C 4 ({C}), Bel C 5 ({C}) < 1 - 0.3 × 0.5 × 0.8 = 0.88, Bel C 6 ({C}) < 1 -0.55 × 0.75 × 0.8 = 0.67, Bel C i ({C}) < 1 -0.8 3 = 0.488, i = 7, 8, 9. Hence, ρ 2 = max 1≤i≤9 {ρ i } while Bel C 1 ({C}) = max 1≤i≤9 {Bel C i ({C})}.
Consequently, object o 2 is selected as a cluster center by the density peaks method, whereas o 1 , located closer to the center of gravity of these nine data objects, is preferred by the belief peaks method.

Remark 2: In some cases, some prior knowledge may be obtained in the form of mass functions m C i0 , i = 1, 2, . . . , n, representing the initial possibility of each data object to be selected as a cluster center. In this case, the final masses m C i in ( 14) can be recalculated as1

m C i = m C i0   j∈NK (oi) m C ij   . (20)
However, it is not clear how the prior mass functions m C i0 could be obtained in practice. We leave this problem for further research.

B. Construction of the credal partition

In this section, we address the problem of deriving a credal partition

M Ω = (m Ω 1 , m Ω 2 , . . . , m Ω n ) ∈ R n×2 c
for the set of objects O locating at (x 1 , x 2 , . . . , x n ) ∈ R n×p , by minimizing an objective function with the fixed cluster centers v k ∈ R p , k = 1, 2, . . . , c, found in the previous section.

Deriving a credal partition from O implies determining the quantities m Ω ij = m Ω i (A j ), A j ⊆ Ω for each object o i in such a way that m Ω ij is high (respectively, low) when the distance D ij between o i and the focal set A j is small (respectively, large). Suppose each cluster ω k is represented by a center v k . As suggested in the Evidential C-Means algorithm (ECM) [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF], the barycenter vj of the centers associated to the clusters composing nonempty set A j can be defined as

vj = 1 |A j | c k=1 s kj v k , (21)
where s kj = 1 if ω k ∈ A j and s kj = 0 otherwise. Let S k be the p × p symmetric positive definite matrix associated to cluster ω k inducing a norm x 2 S k = x S k x. Similar to (21), we can define the matrix Sj associated to the nonempty subset (i.e., the composite cluster) A j . The distance between object o i and composite cluster A j is then

D 2 ij = x i -vj 2 Sj = (x i -vj ) |A j | -1 c k=1 s kj S k (x i -vj ). (22)
Then, a credal partition M Ω can be derived by minimizing the following objective function:

J BP EC (M Ω , S 1 , • • • , S c ) = n i=1 j:Aj =∅ |A j | α (m Ω ij ) β D 2 ij + n i=1 Δ 2 (m Ω i∅ ) β , (23)
subject to

j:Aj =∅ m Ω ij + m Ω i∅ = 1, i = 1, 2, • • • , n, det(S k ) = 1, k = 1, 2, • • • , c, (24)
where constants α, β and Δ have the same meaning as those in the ECM algorithm, and det(•) denotes the determinant of a matrix. Note that the empty focal set ∅ is treated separately from other nonempty focal sets by using a constant Δ.

To minimize J BP EC , we apply the alternate optimization algorithm as suggested in the constrained ECM [START_REF] Antonie | CECM: Constrained evidential c-means algorithm[END_REF] and get

m Ω ij = |A j | -α/(β-1) D -2/(β-1) ij l:A l =∅ |A l | -α/(β-1) D -2/(β-1) il + Δ -2/(β-1)
, (25a)

m Ω i∅ = 1 - j:A j =∅ m Ω ij , (25b)
for i = 1, 2, • • • , n, j : ∅ = A j ⊆ Ω, and
S k = det(Σ k ) 1/p Σ -1 k , k = 1, 2, • • • , c, (26)
with

Σ k = n i=1 j:Aj =∅ |A j | α-1 (m Ω ij ) β s kj (x i -vj )(x i -vj ) .
For completeness, the calculations of ( 25) and ( 26) are presented in the Appendix A.

The BPEC algorithm can be summarized in Algorithm 1.

Algorithm 1: Belief-peaks evidential clustering Input: K, α 0 , q, α, β, termination threshold ε, Δ, δ min , Bel min , data of objects Remark 3: When selecting cluster centers, BPEC considers the local geometric information of each data object, whereas the ECM algorithm does not. This characteristic may result in more appropriate cluster centers and, thus, a more reasonable credal partition, as shown later in Example 3. Furthermore, when just applying δ -Bel instead of ρ -δ in DPC [START_REF] Rodriguez | Clustering by fast search and find of density peaks[END_REF], namely, selecting cluster centers according to belief peaks and assigning each of the remaining objects to the same cluster as its nearest neighbor with higher belief, we can intuitively induce a belief version of DPC, called Belief peaks clustering (BPC), which is summarized in Algorithm 2 and is presented in Appendix B. The BPC will be implemented under the same initial conditions as those of the BPEC algorithm.

x i ∈ R p , i = 1, 2
Remark 4: The barycenters (21) as defined in ECM may lead to uninformative composite clusters in some cases, as remarked in [START_REF] Liu | Belief C-Means: An extension of fuzzy C-Means algorithm in belief functions framework[END_REF]. To reduce the time complexity of BPEC, an informative BPEC algorithm with a limited number of composite clusters will be discussed in Section III-C.

C. Time complexity analysis and informative BPEC

Using the notations of Algorithm 1, the time complexity of BPEC can be analyzed as follows.

First, the computation cost to obtain the belief peaks in The complexity of BPEC depends heavily on both the number n of objects and the number c of clusters. When c is large, we may have 2 c > n, and the complexity of BPEC becomes prohibitive if the number c of clusters is too large. Moreover, some composite clusters (i.e., focal sets) in the credal partition may be less informative in some cases. For instance, in a two dimensional clustering task as shown in Fig. 3, the composite clusters {ω 1 , ω 3 } and Ω are less informative than the other clusters.

Hence, it is interesting to remove less informative focal sets so as to reduce the time complexity of the BPEC algorithm. In [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], Denoeux proposed to preserve the needed expressivity of the credal partition by considering as focal sets the empty set, the singletons, and optionally the whole frame of discernment, and then to add some informative pairs of clusters. As a result, the number of focal sets is much smaller than 2 c , in particular when the number c is large. In a similar way, the informative BPEC can be described as follows:

1) Step 1: Run the BPEC in the basic configuration with focal sets of cardinalities 0, 1, and optionally, c. An initial credal partition M Ω 0 is then created. The similarity between each pair of clusters (ω j , ω l ) is measured by

S(j, l) = n i=1 pl Ω ij pl Ω il , (27)
where pl Ω ij and pl Ω il are, respectively, the normalized plausibilities that object o i belongs to clusters ω j and ω l . We then can determine the set P K of pairs {ω j , ω l } that are mutual K nearest neighbors according to similarity measure (Note that K should not be confused with K).

2)

Step 2: Run the BPEC again starting from M Ω 0 , and adding as focal sets the pairs of clusters in P K .

D. Tuning of parameters

To implement the BPEC algorithm, some parameters should be selected in advance, including K, α 0 , γ i , δ min , Bel min , α, β, Δ and ε. When implementing the informative BPEC, the number of mutual K nearest pairs of clusters also needs to be determined.

The constant α 0 in the decreasing function φ(•) should be positive and not greater than 1. We suggest α 0 = 1/K in order to avoid "saturated beliefs" if the number of nearest neighbors K is large. (This issue will be discussed later in Remark 6).

Parameters γ i and K together play critical roles on determining the distribution of objects in the decision graph. As shown in Remark 1, most DPC algorithms usually define a unique value of γ i for all objects o i , i = 1, 2, • • • , n. It is interesting to allow "adaptive" γ i (i.e., different cutoff distances) for different data objects. Here, we define γ i as the inverse of a quantile of the distances between object o i and its K nearest neighbors

γ i = 1/ quantile j∈N K (o i ) (d ij , q), ( 28
)
where q is a quantile number such that 0 ≤ q ≤ 1. To fix γ i in an automatic way for simplicity, we set q = 0.9 in this paper.

For KNN-based classification or clustering algorithms, there is no efficient rule to determine the optimal number K of neighbors automatically. For BPEC, a simple approach is to increase K until some objects (i.e., cluster centers and outliers) can be visually separated from the other objects. It will be seen that, for most datasets, a large value of K is preferable. More interestingly, the distribution of cluster centers in the decision graph is not too sensitive to the change of K provided K is large enough. More details will be given with experimental results in Section IV.

In contrast to K and q, it is easy to determine the lower bounds δ min and Bel min , because cluster centers can usually be located far away from other data objects. In fact, we will see that δ min and Bel min are not as crucial as they seem to be and there are many choices for δ min and Bel min . As recommended with most DPC algorithms, we suggest determining δ min and Bel min by visual inspection after drawing the decision graph. The lower bounds δ min and Bel min will be presented together with cluster centers in the decision graph for convenience.

To derive a credal partition, we should preset ε, α, β, K and Δ. We use as default values ε = 10 -3 , α = 1 and β = 2, as in the ECM algorithm [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF]. Furthermore, we just consider at most two mutual nearest pairs of clusters when the number of clusters is large (i.e., K = 1 or 2). Finally, we set Δ 2 equal to a constant smaller than the minimal delta associated to outliers in the decision graph if outliers exist; otherwise, Δ 2 can be a constant larger than the maximum max 1≤i≤n {δ i }.

Remark 5: As a matter of fact, tuning K and q together usually provides a more flexible way to distinguish cluster centers from other regular data objects. In practice, one can alternately increase and/or decrease K and q in their ranges until one gets an interpretable δ -Bel decision graph.

IV. EXPERIMENTAL RESULTS

This section consists of two parts. In Section IV-A, some numerical examples are used to illustrate the behavior of BPEC algorithm. In Section IV-B, we compare the performance of BPEC as to those of some other clustering algorithms.

During the simulations, all the attributes of data objects were normalized into [0, 1] to make the results independent from the units in which these attributes are expressed, according to the following min-max rule:

x ij ← x ij -min(x •j ) max(x •j ) -min(x •j ) , (29)
where x ij denotes the value of attribute j of object o i , and min(x •j ) and max(x •j ) are, respectively, the minimum and maximum values of attribute j.

The Adjust Rand Index (ARI) [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] is a popular choice for a performance index and is suitable to measure the closeness of a hard partition to the truth. To perform comparisons among hard, fuzzy, rough and even credal partitions, Denoeux proposed a credal version of ARI, called Credal Rand Index (CRI) [START_REF] Denoeux | Evaluating and comparing soft partitions: an approach based on Dempster-Shafer theory[END_REF]. In this paper, we use CRI as the performance index when comparing the closeness between two credal partitions. When comparing two hard partitions, CRI and ARI are equivalent. In this case, the criterion will be referred to as "ARI". We refer the reader to [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] and [START_REF] Denoeux | Evaluating and comparing soft partitions: an approach based on Dempster-Shafer theory[END_REF] for the precise definitions of ARI and CRI.

A. Illustrative examples

In the following three examples, we use the notation Bel in place of Bel C i ({C}) for simplicity when there is no risk of confusion.

Example 3: In this example, we consider the famous butterfly dataset [START_REF] Liu | Belief C-Means: An extension of fuzzy C-Means algorithm in belief functions framework[END_REF], [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] to illustrate the results of BPEC. The butterfly dataset is represented by circles in Fig. 4 (top). We set K = 4, q = 0.9 and Δ 2 = 0.1. The δ -Bel decision graph can first be drawn, as shown in Fig. 5. In this graph, objects 3 and 9 have equally high degrees beliefs and are far away from other data objects. Hence, these two data objects can be considered as the centers of two clusters, i.e., c = 2. With the selected cluster centers, outlined by symbol " + " in Fig. 4 (top), a credal partition can then be created and illustrated in Fig. 4 (bottom), from which we can see that the credal partition is meaningful to reveal ambiguity and uncertainty. For instance, object o 6 could be assigned to any of the two detected clusters, whereas object o 12 and o 13 could be better identified as outliers. In contrast, o 6 , o 7 and o 13 were assigned to Ω by ECM, and instead, o 13 was assigned to Ω by the Belief C-Means (BCM) algorithm [START_REF] Liu | Belief C-Means: An extension of fuzzy C-Means algorithm in belief functions framework[END_REF]. More interestingly, BPEC can find the true locations of centers whereas the ECM and BCM cannot.

Example 4: In this example, we consider the strongly overlapping four-class dataset [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] consisting of 100 of data objects in each class. We aim to study the influence of K, q and the locations of centers on the clustering performances. We considered K ∈ {20, 25, • • • , 90}, q ∈ {0.1, 0.2, • • • , 1.0} and Δ 2 = 0.2. In each case, we selected the cluster centers from the decision graph. The credal partition was then created by BPEC. Fig. 6 shows the number of clusters and the ARI as functions of K and q. The ARI was computed after transforming the credal partition into a hard one using the maximum probability rule [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF]. From Fig. 6a, we can see that the true number of clusters can be easily identified in most cases, in particular when K and q take large values simultaneously. Correspondingly, Fig. 6b indicates that better performances (i.e., higher ARI) can be achieved when the true number of clusters has been found, in which case the best performance is achieved with ARI = 0.7398 when K = 75 and q = 0.9. In the best case, the decision graph and the credal partition are illustrated in Figs. 7 and8, respectively. For comparison with this best case, we present in Fig. 9 the cluster centers selected by the degree of belief and the four typical densities mentioned in Remark 1. We can see that some cluster centers selected by belief peaks are different from those obtained by density peaks. To study the influence of cluster centers, we computed the ARI for each group of selected cluster centers, by applying the same assignment strategy as used in DPC. With K = 75, q = 0.9, f = 2%, we get ARI DPC = 0.3258, ARI ADPC-KNN = ARI FKNN-DPC = ARI DPC-KNN = 0.7279 and ARI BPC = 0.7392, which, together with ARI BPEC = 0.7398, shows that the cluster centers selected by belief peaks are better in this case.

Example 5: In this example, we used the dataset S2 in [START_REF] Franti | Iterative shrinking method for clustering problems[END_REF], consisting of 5000 objects and 15 clusters, to illustrate the partition via informative BPEC with a limited number of composite clusters. With K = 80, q = 0.9, Δ = 1 and K = 1, the decision graph is drawn in Fig. 10, and the rough approximations of the initial and final credal partitions are illustrated in Figs. 11 and credal partition obtained via informative BPEC seems to be reasonable.

Remark 6:

As can be seen from the decision graphs in above three examples that, the beliefs Bel C i ({C}) seem to approach an upper bound that is smaller than 1. This is the case because, according to (15), we have

Bel C i ({C}) ≤ 1 -lim dij →0 j∈N K (oi) 1 -φ(d 2 ij ) = 1 -(1 -α 0 ) K . (30)
When choosing α 0 = 1 K we have lim K→∞ (1-1 K ) K = 1 e and thus get the infimum of upper bound, i.e., 1 -1 e . To increase this infimum, α 0 can be redefined in a more general form such as α 0 = 1/K θ with a positive constant θ. With an appropriate choice of θ, correct number of clusters can be selected.

B. Performance evaluation

In this subsection, we aim to evaluate the performances of BPEC based on some synthetic and UCI real-world datasets with characteristics summarized in Table II. As can be seen from Table II, the synthetic datasets have large numbers of clusters, while the real-word datasets have more attributes.

To implement BPEC, some parameters were preset as mentioned in Section III-D and some others were fixed individually as shown in Table III. In the absence of outliers, we suggest Δ = 1 for simplicity. For comparison, several DPC algorithms were also applied to these datasets, including BPC, DPC [START_REF] Rodriguez | Clustering by fast search and find of density peaks[END_REF], DPC-KNN [START_REF] Du | Study on density peaks clustering based on k-nearest neighbors and principal component analysis[END_REF], ADPC-KNN [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF] and FKNN-DPC [START_REF] Xie | Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors[END_REF]. For DPC [START_REF] Rodriguez | Clustering by fast search and find of density peaks[END_REF], the cutoff distance d c was defined according to a proportion f = 2% of the total number of objects in a dataset, i.e., d c = d(i p ), where d is a vector sorting distances d ij , i < j in descending order and i p = round(n•f ). For DPC-KNN [START_REF] Du | Study on density peaks clustering based on k-nearest neighbors and principal component analysis[END_REF], f = 2%. The ARI values are shown in Table IV.

As can be seen from Tables III and IV, BPEC and BPC can find the true number of clusters for most of these datasets, This result shows that cluster centers selected according to belief peaks can usually yield more better clustering performances. As stated in Remark 5, alternately tuning K and q in their ranges can usually induce more distinguishable decision graph and thus better performance. For instance, more appropriate cluster centers with ARI= 0.8176 can be achieved for the WDBC dataset when selecting q = 0.1 and K = 40 in an alternate way. As another example, the true number of clusters can be found for the Pima dataset with ARI= 0.1210 if q = 0.1 and K = 40. To gain further insight into the relative performances of BPEC and alternative evidential clustering algorithms, we compared the closeness of the hard partitions generated from credal partitions according to maximum rule (9) by each algorithm, to the true hard partition for each dataset. Fig. 13 displays the ARI values obtained by BPEC vs. those obtained by ECM, EVCLUS, and EK-NNclus. Fig. 13a shows that BPEC outperforms ECM on these seven real-world datasets. It can be seen from Fig. 13b that BPEC outperforms EVCLUS in most cases except for the Wine dataset, for which BPEC and EVCLUS have comparable performances. We can see from Fig. 13c that EK-NNclus outperforms BPEC on the Wine and Seeds datasets, whereas BPEC outperforms EK-NNclus on the other five real-world datasets. Finally, Fig. 13d shows that the performance of the BPEC algorithm is not deteriorated when limiting the number of composite clusters.

V. CONCLUSIONS

In this paper, we have introduced a clustering procedure, called the Belief-peaks Evidential Clustering (BPEC) algo-rithm, which can find the true number of clusters and create a credal partition for some datasets with good performances. When the number of clusters is small (usually less than ten), the performances of BPEC and its informative variant with a limited number of composite clusters are approximately equal. In contrast, BPEC can be enhanced if less informative composite clusters (i.e., focal sets) when the number of clusters is large. Furthermore, BPEC can provide hard, fuzzy, possibilistic and even rough partitions. Finally, as a byproduct of the BPEC algorithm, we proposed a belief version of DPC, called the Belief Peaks Clustering (BPC) algorithm. We have shown that BPC outperforms DPC in most cases but is outperformed by BPEC (of which it is not merely a crisp version).

There are several avenues for further research, such as combining the belief peak approach with other clustering algorithms instead of ECM, and improving the method to make it applicable to very large datasets.

Fig. 1 .

 1 Fig. 1. Illustration of ambiguity and uncertainty in clustering.

Fig. 2 .

 2 Fig. 2. An example of decision graph δ -Bel α 0 = 1 and γ i = 1/ √ nf , where f is a constant percentage. By expanding (15), we get

Example 2 :

 2 Given data objects o i , i = 1, 2, • • • , 9 as illustrated in Fig. 1. Suppose φ(d 2 12 ) = 0.3, φ(d 2 13 ) = 0.9, φ(d 2 16 ) = 0.45, φ(d 2 23 ) = 0.35, φ(d 2 24 ) = φ(d 2 25 ) = 0.7, φ(d 2 36 ) = 0.25, φ(d 2 45 ) = 0.5, and all φ(•) between any other two objects are smaller than 0.2. Furthermore, we assume φ(d

9 until 10 Output:

 910 M Ω (t) -M Ω (t -1) < ε ; cluster centers v k and credal partition M Ω

Fig. 3 .

 3 Fig. 3. Illustration of less informative composite clusters in a credal partition.

  Step 1 is O(p 2 n(n -1)/2) + O(2 2 Kn). Then, the sorting and assignment processes in Step 2 can be performed in O(n log n) + O(n) operations. Finally, to derive a credal partition in Steps 6-10, we need to perform O(2 c tn)+O(2 c t) operations. The total time complexity of BPEC is, thus, O(p 2 n(n -1)/2 + 2 c t(n + 1) + n(log n + 2 2 K + 1)) ∼ O(p 2 n 2 + 2 c nt).

Fig. 4 .Fig. 5 .

 45 Fig. 4. Butterfly (top) and credal partition (bottom) via BPEC algorithm.

Fig. 6 .

 6 Fig. 6. Number of selected clusters (A) and ARI (b) as functions of K and q for the four-class dataset.

Fig. 7 .

 7 Fig. 7. δ -Bel decision graph for the four-class dataset.

Fig. 8 .

 8 Fig. 8. Contour surfaces of the credal partition (top: singletons and Ω, bottom: empty set and composite clusters with |A j | = 2, 3) obtained by BPEC for the four-class dataset.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Locations of centers selected by different methods for the four-class dataset.

Fig. 11 .

 11 Fig. 11. Lower rough approximations of the initial credal partition M Ω 0 for the S2 dataset.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Lower and (four pairs of) upper rough approximations of the final credal partition M Ω for the S2 dataset.

TABLE I A

 I CREDAL PARTITION ON Ω = {ω 1 , ω 2 }

	m Ω 1	∅ 0	{ω 1 } {ω 2 } 0.7 0.2	Ω 0.1
	m Ω 2	0	0	0	1.0
	m Ω 3	0	0.2	0.8	0
	m Ω 4	1.0	0	0	0
	In contrast, objects o 2 and o 4 correspond to two different
	situations of maximum uncertainty. Object o 2 has a full
	mass assigned to Ω: this reflects total ambiguity in the class
	membership of this object, which means that it might belong
	to ω 1 as well as to ω 2 . For objet o 4 , it has the largest mass
	assigned to the empty set, indicating that this object does not
	seem to belong to any of the two clusters and is an outlier.

TABLE II

 II

		DATASET DESCRIPTION
	Type	Name	Size	# Attributes	c	Source
		A3	7500	2	50	[32]
		D31	3200	2	31	[33]
		DIM1024	1024	1024	16	[34]
	Synthetic	R15	600	2	15	[33]
		S4	5000	2	15	[31]
		S2	5000	2	15	[31]
		Unbalance	650	2	8	[35]
		Iris	150	4	3	[36]
		Parkinsons	195	23	2	[36]
		Pima	768	8	2	[36]
	Real-world Seeds	210	7	3	[36]
		Waveform	5000	21	3	[36]
		WDBC	569	30	2	[36]
		Wine	178	13	3	[36]

TABLE V

 V CRI (mean ± std.) BETWEEN BPEC AND OTHER EVIDENTIAL evidential algorithms. (Note that, for the EK-NNclus we only considered the cases when true number of clusters had been found). The mean CRI and standard deviation (std.) over the ten times are presented in TableV. It can be concluded from TableVthat, on the one hand, the cluster centers found by the BPEC are not the same to those obtained by the ECM, on the other hand, BPEC creates different credal partitions from those generalized by the ECM, EVCLUS and EK-NNclus.

		CLUSTERING ALGORITHMS.
	Datasets	BPEC-ECM	BPEC-EVCLUS	BPEC-EK-NNclus
	Iris Parkinsons 0.8434 ± 0.0001 0.5365 ± 0.0275 0.9436 ± 0.0001 0.7407 ± 0.0222 Pima 0.9331 ± 0.0005 0.6207 ± 0.0022 Seeds 0.9504 ± 0.0002 0.6053 ± 0.0047 Waveform 0.9472 ± 0.0001 0.7157 ± 0.0016 WDBC 0.9596 ± 0.0003 0.6527 ± 0.0123 Wine 0.9616 ± 0.0001 0.7642 ± 0.0074	0.3572 ± 0 -0.1258 ± 0.0203 0.0045 ± 0 0.3834 ± 0.0142 0.3963 ± 0 0.5352 ± 0 0.3423 ± 0

This was suggested by an anonymous referee.

ACKNOWLEDGEMENTS

The authors are grateful to the editor and the referees for the useful comments.

This work is supported in part by the National Natural Science Foundation of China under Grants 51876035, 51676034 and 51476028, and fully by the Key Project of Yunnan Power Grid Co. Ltd. under Grant YNYJ2016043.

Z.-

By comparing BPEC with BPC, it can be concluded that ECM assigns the remaining objects more reliably than BPC, resulting in better performance. Furthermore, we can see that the hard partition obtained from the BPEC algorithm using the maximum plausibility-probability rule [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF] is different from that obtained by the BPC algorithm, which means that BPC is not merely a crisp version of BPEC.

To compare BPEC with some other evidential clustering algorithms, ECM [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF], EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] and EK-NNclus [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential k-nearest neighbor rule[END_REF] were also implemented. When compared with ECM and EVCLUS, the BPEC algorithm was implemented with full focal sets. When compared with EK-NNclus, BPEC was used with singletons and the whole frame of discernment, 1 The ARI values for ADPC-KNN and FKNN-DPC are taken from [START_REF] Liu | Adaptive density peak clustering based on knearest neighbors with aggregating strategy[END_REF] and [START_REF] Xie | Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors[END_REF]. Missing values are indicated by "-". 2 The bold and underlined value(s) in each row indicates the best performance.

as EK-NNclus. For ECM and EVCLUS, the number of clusters was preset to the value found by BPEC, and the Euclidean distance was used in BPEC instead of an adaptive one. In contrast with ECM and EVCLUS, EK-NNclus was run with integer labels randomly generated in the range [1, n], as it does not require number of clusters as priori. Furthermore, the number of nearest neighbors (K nn ) and quantile of these nearest neighbors (q nn ) were set for EK-NNclus as follows, for the seven datasets from Iris to Wine: (50, 0.5), (300, 0.9), (50, 0.9), (500, 0.9), (50, 0.5), (200, 0.5) and (50, 0.9).

For each real-world dataset in Table II, we run ECM, EVCLUS and EK-NNclus ten times, respectively. At each time, we calculated CRI between BPEC and these three 23)-( 24) can be written as

where λ i and η k are Lagrange multipliers. First, we optimize m Ω ij and m Ω i∅ by fixing matrix S k . By calculating the partial derivatives of [START_REF] Franti | Iterative shrinking method for clustering problems[END_REF] with respect to m Ω ij , m Ω i∅ and λ i and setting them to zero, we have for i = 1, 2, . . . , n and all j such that A j ⊆ Ω,

By solving m Ω ij and m Ω i∅ from (32a) and (32b) and inserting them into (32c), we get

, [START_REF] Veenman | A maximum variance cluster algorithm[END_REF] which, inserted in (32a) and (32b), leads to [START_REF]40 years of Dempster-Shafer theory[END_REF].

Next, we consider that m Ω ij and m Ω i∅ are fixed to obtain S k and η k . We have, for k = 1, 2, . . . , c,

Define

From ( 34) and ( 35), it follows that

where I is a p × p identify matrix. Taking the determinant of (36), we get

which leads to

By inserting (38) into (34), we finally get [START_REF] Shafer | A mathematical theory of evidence turns 40[END_REF].

APPENDIX B BPC: BELIEF PEAKS CLUSTERING ALGORITHM

The belief version of DPC algorithm, i.e., belief peaks clustering algorithm (BPC) is summarized as follow.

Algorithm 2: Belief peaks clustering

Input: K, α 0 , q, x i ∈ R p for i = 1, 2


Thierry Denoeux

Prakash P Shenoy
email: pshenoy@ku.edu

An Axiomatic Utility Theory for Dempster-Shafer Belief Functions

Keywords: Dempster-Shafer theory of evidence, von Neumann-Morgenstern's utility theory, Jaffray's linear utility theory, Smets' decision theory

The main goal of this paper is to describe an axiomatic utility theory for Dempster-Shafer belief function lotteries. The axiomatic framework used is analogous to von Neumann-Morgenstern's utility theory for probabilistic lotteries as described by Luce and Raiffa. Unlike the probabilistic case, our axiomatic framework leads to interval-valued utilities, and therefore, to a partial (incomplete) preference order on the set of all belief function lotteries. If the belief function reference lotteries we use are Bayesian belief functions, then our representation theorem coincides with Jaffray's representation theorem for his linear utility theory for belief functions. We illustrate our framework using some examples discussed in the literature. Finally, we compare our decision theory with those proposed by Jaffray and Smets.

Introduction

The main goal of this paper is to propose an axiomatic utility theory for lotteries described by belief functions in the Dempster-Shafer (D-S) theory of evidence [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The axiomatic theory is constructed similar to von Neumann-Morgenstern's (vN-M's) utility theory for probabilistic lotteries [START_REF] John Von Neumann | Theory of Games and Economic Behavior[END_REF][START_REF] Herstein | An axiomatic approach to measurable utility[END_REF][START_REF] Hausner | Multidimensional utilities[END_REF][START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF][START_REF] Jensen | An introduction to Bernoullian utility theory: A discussion[END_REF][START_REF] Fishburn | The Foundations of Expected Utility[END_REF]. Unlike the probabilistic case, our axiomatic theory leads to interval-valued utilities, and therefore to a partial (incomplete) preference order on the set of all belief function lotteries. Also, we compare our decision theory to those proposed by Jaffray [START_REF] Jaffray | Linear utility theory for belief functions[END_REF] and Smets [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF].

In the foreword to Glenn Shafer's 1976 monograph [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], Dempster writes: "... I believe that Bayesian inference will always be a basic tool for practical everyday statistics, if only because questions must be answered and decisions must be taken, so that a statistician must always stand ready to upgrade his vaguer forms of belief into precisely additive probabilities." More than 40 years after these lines were written, a lot of approaches to decision-making have been proposed (see the recent review in [START_REF] Denoeux | Decision-making with belief functions: A review[END_REF]). However, most of these methods lack a strong theoretical basis. The most important steps toward a decision theory in the D-S framework have been made by Jaffray [START_REF] Jaffray | Linear utility theory for belief functions[END_REF], Smets [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF], and Shafer [START_REF] Shafer | Constructive decision theory[END_REF]. However, we argue that these proposals are either not sufficiently justified from the point of view of D-S theory, or not sufficiently developed for practical use. Our goal is to propose and justify a utility theory that is in line with vN-M's utility theory, but adapted to be used with lotteries whose uncertainty is described by D-S belief functions.

In essence, the D-S theory consists of representationsbasic probability assignments (also called mass functions), belief functions, plausibility functions, etc.-together with Dempster's combination rule, and a rule for marginalizing joint belief functions. The representation part of the D-S theory is also used in various other theories of belief functions. For example, in the imprecise probability community, a belief function is viewed as the lower envelope of a convex set of probability mass functions called a credal set. Using these semantics, it makes more sense to use the Fagin-Halpern combination rule [START_REF] Fagin | A new approach to updating beliefs[END_REF], rather than Dempster's combination rule [START_REF] Halpern | Two views of belief: Belief as generalized probability and belief as evidence[END_REF][START_REF] Shafer | Perspectives on the theory and practice of belief functions[END_REF][START_REF] Shafer | Rejoinders to comments on "Perspectives on the theory and practice of belief functions[END_REF]. The utility theory this article proposes is designed specifically for the D-S belief function theory, and not for the other theories of belief functions. This suggests that Dempster's combination rule should be an integral part of our theory, a property that is not satisfied in the proposals by Jaffray and Smets.

There is a large literature on decision making with a (credal) set of probability mass functions motivated by Ellsberg's paradox [START_REF] Ellsberg | Risk, ambiguity and the Savage axioms[END_REF]. An influential work in this area is the axiomatic framework by Gilboa-Schmeidler [START_REF] Gilboa | Maxmin expected utility with a non-unique prior[END_REF], where they use Choquet integration [START_REF] Choquet | Theory of capacities[END_REF][START_REF] Gilboa | Additive representations of non-additive measures and the Choquet integral[END_REF] to compute expected utility. A belief function is a special case of a Choquet capacity. Jaffray's [START_REF] Jaffray | Linear utility theory for belief functions[END_REF] work can also be regarded as belonging to the same line of research, although Jaffray works directly with belief functions without specifying a combination rule. A review of this literature can be found in, e.g., [START_REF] Gajdos | Attitude toward imprecise information[END_REF], where the authors propose a modification of the Gilboa-Schmeidler [START_REF] Gilboa | Maxmin expected utility with a non-unique prior[END_REF] axioms. As we said earlier, our focus here is on decision-making with D-S theory of belief functions, and not on decision-making based in belief functions with a credal set interpretation. As we will see, our interval-valued utility functions lead to intervals that are contained in the Choquet lower and upper expected utility intervals.

The remainder of this article is as follows. In Section 2, we sketch vN-M's axiomatic utility theory for probabilistic lotteries as described by Luce and Raiffa [START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF]. In Section 3, we describe our adaptation of vN-M's utility theory for lotteries in which uncertainty is described by D-S belief functions. Our assumptions lead to an interval-valued utility function, and consequently, to a partial (incomplete) preference order on the set of all belief function lotteries. In Section 4, we illustrate the application of our representation theorem to three examples from the literature. In Section 5, we compare our utility theory with those described by Jaffray [START_REF] Jaffray | Linear utility theory for belief functions[END_REF], and Smets [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF]. Finally, in Section 6, we summarize and conclude.

vN-M's Utility Theory

In this section, we describe vN-M's utility theory for decision under risk. Most of the material in this section is adapted from [START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF]. A decision problem can be seen as a situation in which a decision-maker (DM) has to choose a course of action (or an act) in some set F. An act may have different outcomes, depending on the state of nature X. Exactly one state of nature will obtain, but this state is unknown. Let Ω X = {x 1 , . . . , x n } denote the set of states of nature, and let O = {O 1 , . . . , O r } denote the set of outcomes. 1 An act can be formalized as a mapping f : Ω X → O. In this section, we assume that uncertainty about the state of nature is described by a probability mass function (PMF) p X for X. If the DM select act f , they will get outcome O i with probability

p i = ∑ {x∈Ω X | f (x)=O i } p X (x). (1)
To each act f there corresponds a PMF p = (p 1 , . . . , p r ) for O. We call L = [O, p] a probabilistic lottery. As only one state in Ω X will be realized, a probabilistic lottery will result in exactly one outcome O i (with probability p i ), and we assume that the lottery will not be repeated. Another natural assumption is that two acts that induce the same lottery are equivalent: the problem of expressing preference between acts then boils down to expressing preference between lotteries. We are concerned with a DM who has preferences on L , the set of all probabilistic lotteries on O, and our task is to find a real-valued utility function u : L → R such that the DM strictly prefers L to L if and only if u(L) > u(L ), and the DM is indifferent between L and L if and only if Of course, finding such a utility function is not always possible, unless the DM's preferences satisfy some assumptions. We can then construct a utility function that is linear in the sense that the utility of a lottery L = [O, p] is equal to its expected utility ∑ r i=1 p i u(O i ), where O i is regarded as a degenerate lottery where the only possible outcome is O i with probability 1. In the remainder of this section, we describe the assumptions that lead to the existence of such a linear utility function. Suppose that L = {L (1) , . . . , L (s) } is a set of s lotteries, where each of the s lotteries L j = [O, p ( j) ] are over outcomes in O, with PMFs p ( j) for j = 1, . . . , s. Suppose q = (q 1 , . . . , q s ) is a PMF for L such that q j > 0 for j = 1, . . . , s, and ∑ s j=1 q j = 1. Then [L, q] is called a compound lottery whose outcome is exactly one lottery L (i) (with probability q i ), and lottery L (i) will result in one outcome O j (with probability p (i) j ). Notice that the PMF p (i) is a conditional PMF for O in the second stage given that lottery L (i) is realized (with probability q i > 0) in the first stage (see Figure 1). We can compute the joint PMF for (L, O), and then compute the marginal p of the joint for O. The following assumption states that the resulting lottery [O, p] is indifferent to the compound lottery [L, q]. Assumption 2.2 (Reduction of compound lotteries) Any compound lottery [L, q], where L

u(L) = u(L ). We write O i O j if the DM strictly prefers O i to O j , write O i ∼ O j if
(i) = [O, p (i) ], is indifferent to a simple (non-compound) lottery [O, p], where p i = q 1 p (1) i + . . . + q s p (s) i (2)
for i = 1, . . . , r. PMF (p 1 , . . . , p r ) is the marginal for O of the joint PMF of (L, O).

A simple lottery involving only outcomes O 1 and O r with PMF (u, 1u), where 0 ≤ u ≤ 1, is called a reference lottery, and is denoted by

[{O 1 , O r }, (u, 1 -u)]. Let O 2 denote the set {O 1 , O r }. Assumption 2.3 (Continuity) Each outcome O i is indif- ferent to a reference lottery O i = [O 2 , (u i , 1 -u i )] for some u i , where 0 ≤ u i ≤ 1, i.e., O i ∼ O i .
O i = [O 2 , (u i , 1 -u i )] that is indifferent to O i , then the result is a compound lottery that is indifferent to L.
From Assumptions 2.1-2.5, given any lottery L = [O, p], it is possible to find a reference lottery L = [O 2 , (u, 1u)] that is indifferent to L (see Figure 2). This is expressed by Theorem 1 below. 2 Theorem 1 ( [START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF]) Under Assumptions 2.1-2.5, any lot-

tery L = [O, p] is indifferent to a reference lottery L = [O 2 , (u, 1 -u)] with u = r ∑ i=1 p i u i . ( 3
) Assumption 2.6 (Monotonicity) A reference lottery L = [O 2 , (u, 1-u)] is preferred or indifferent to reference lottery L = [O 2 , (u , 1 -u )] if and only if u ≥ u .
2. For reasons of space, proofs of all results in this paper are omitted and can be found in [START_REF] Denoeux | An interval-valued utility theory for decision making with Dempster-Shafer belief functions[END_REF].

As

O 1 ∼ O 1 = [O, (u 1 , 1 -u 1 )] and O r ∼ O r = [O, (u r , 1 -u r )], Assumptions 2.4 and 2.6 imply that u 1 = 1 and u r = 0. Also, from O 1 O 2 • • • O r , we can deduce that 1 = u 1 ≥ u 2 ≥ • • • ≥ u r = 0.
Assumptions 2.1-2.6 allow us to define the utility of a lottery as the probability of the best outcome O 1 in an indifferent reference lottery, and this utility function for lotteries on O is linear. This is stated by the following theorem.

∑ i=1 p i u i ≥ r ∑ i=1 p i u i . ( 4
)
Thus, we can define the utility of lottery L = [O, p] as u(L) = ∑ r i=1 p i u i , where u i = u(O i ). Also, such a linear utility function is unique up to a strictly increasing affine transformation, i.e., if u i = a u i + b, where a > 0 and b are real constants, then u(L) = ∑ r i=1 p i u i also qualifies as a utility function.

A Utility Theory for D-S Belief Function Theory

In this section, we describe a new utility theory for lotteries where the uncertainty is described by D-S belief functions. 3 These lotteries, called belief function lotteries, 4 will be introduced in Section 3.1. We present and discuss assumptions in Section 3.2, and state a representation theorem in Section 3.3.

Belief function lotteries

We now generalize the decision framework outline in Section 2 by assuming that uncertainty about the state of nature X with state space Ω X is described by a BPA m X for X. The probabilistic framework is recovered as a special case when m X is Bayesian. As before, we define an act as a mapping f :

Ω X → O. Mapping f pushes m X forward from Ω X to O, transferring each mass m X (a) for a ∈ 2 Ω X to b = { f (x) : x ∈ a}.
The resulting BPA m for O is then defined as follows:

m(b) = ∑ {a∈2 Ω X | f [a]=b} m X (a), (5)
for all b ⊆ O, where f [a] denotes the image of subset a by f [START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF]. Eq. ( 5) clearly generalizes Eq. ( 1). The pair [O, m] will 3. We assume the reader is familiar with the fundamentals of D-S belief functions. A brief review appears in [START_REF] Denoeux | An interval-valued utility theory for decision making with Dempster-Shafer belief functions[END_REF]. 4. This notion was previously introduced in [START_REF] Denoeux | Decision-making with belief functions: A review[END_REF] under the name "evidential lottery."

be called a belief function (bf) lottery. As before, we assume that two acts can be compared from what we believe their outcomes will be, irrespective of the evidence on which we base our beliefs. This assumption is a form of what Wakker [START_REF] Wakker | Dempster belief functions are based on the principle of complete ignorance[END_REF] calls the principle of complete ignorance (PCI). It implies that two acts resulting in the same bf lottery are equivalent. The problem of expressing preferences between acts becomes that of expressing preferences between bf lotteries. Thus, we are concerned with a DM who has preferences on L b f , the set of all bf lotteries. We will define our task as finding a utility function u :

L b f → [R], where [R] denotes the set of closed real intervals, such that the u(L) = [u, u + w] is viewed as an interval-valued utility of L.
The interval-valued utility can be interpreted as follows: u and u + w are, respectively, the degrees of belief and plausibility of receiving the best outcome in a bf reference lottery equivalent to L. Given two lotteries L and L , L is preferred to L if and only if u ≥ u and u + w ≥ u + w . This leads to incomplete preferences on the set of all bf lotteries. If we assume w = 0 for all bf lotteries, then we have a realvalued utility function on L b f , and consequently, complete preferences.

Example 1 (Ellsberg's Urn) Ellsberg [START_REF] Ellsberg | Risk, ambiguity and the Savage axioms[END_REF] describes a decision problem that questions the adequacy of the vN-M axiomatic framework. Suppose we have an urn with 90 balls, of which 30 are red, and the remaining 60 are either black or yellow. We draw a ball at random from the urn. Let X denote the color of the ball drawn, with Ω X = {r, b, y}. Notice that the uncertainty of X can be described by a BPA m X for X such that m X ({r}) = 1/3, and m X ({b, y}) = 2/3.

First, we are offered a choice between Lottery L 1 : $100 on red, and Lottery L 2 : $100 on black, i.e., in L 1 , you get $100 if the ball drawn is red, and $0 if the ball drawn is black or yellow, and in L 2 , you get $100 if the ball drawn is black and $0 if the ball drawn is red or yellow. Choice of L 1 can be denoted by alternative f 1 :

Ω X → {$100, $0} such that f 1 (r) = $100, f 1 (b) = f 1 (y) = $0. Similarly, choice of L 2 can be denoted by alternative f 2 : Ω X → {$100, $0} such that f 2 (b) = $100, f 2 (r) = f 2 (y) = $0. L 1 can be represented by the BPA m 1 for O = {$0, $100} as fol- lows: m 1 ({$100}) = 1/3, m 1 ({$0}) = 2/3. L 2 can be rep- resented by BPA m 2 for O as follows: m 2 ({$0}) = 1/3, m 2 ({$0, $100}) = 2/3. Notice that L 1 and L 2 are bf lotter- ies. Ellsberg notes that a frequent pattern of response is L 1 preferred to L 2 .
Second, we are offered a choice between L 3 : $100 on red or yellow, and L 4 : $100 on black or yellow, i.e., in L 3 you get $100 if the ball drawn is red or yellow, and $0 if the ball drawn is black, and in L 4 , you get $100 if the ball drawn is black or yellow, and $0 if the ball drawn is red. L 3 can be represented by BPA m 3 as follows: m 3 ({$100}) = 1/3, and m 3 ({$0, $100}) = 2/3, and L 4 can be represented by the BPA m 4 as follows: m 4 ({$0}) = 1/3, m 4 ({$100}) = 2/3. L 3 and L 4 are also belief function lotteries. Ellsberg notes that L 4 is often strictly preferred to L 3 . Also, the same subjects who prefer L 1 to L 2 , prefer L 4 to L 3 .

Assumptions of our framework

As in the probabilistic case, we will assume that a DM's preferences for bf lotteries are reflexive and transitive. However, unlike the probabilistic case, we do not assume that these preferences are complete. In the probabilistic case, incomplete preferences are studied in [START_REF] Aumann | Utility theory without the completeness axiom[END_REF], and in the case of sets of utility functions, in [START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF].

Our first assumption is identical to Assumption 2.1. This allows us to label the outcomes such that

O 1 O 2 • • • O r , and O 1 O r . (6)
Let L b f denote the set of all bf lotteries on O = {O 1 , . . . O r }, where the outcomes satisfy Eq. ( 6). As every BPA m for O is a bf lottery, L b f is essentially the set of all BPAs for O. As the set of all BPAs include Bayesian BPAs, the set L b f is a superset of L , i.e., every probabilistic lottery on O can be considered a bf lottery.

Consider a compound lottery [L, m], where L = {L 1 , . . . , L s }, m is a BPA for L, and L j = [O, m j ] is a bf lottery on O, where m j is a conditional BPA for O in the second stage given that lottery L j is realized in the first stage. Assumption 3.2 posits that we can reduce the compound lottery to a simple bf lottery on O using the D-S calculus, and that the compound lottery is equally preferred to the reduced simple lottery on O.

and m L j , j is a BPA for (L, O) obtained from m j by conditional embedding, for j = 1, . . . , s.

The following proposition states that Assumption 3.2 generalizes Assumption 2.2.

Proposition 3 Let L = {L 1 , . . . , L s } be a set of bf lotter- ies, with L j = [O, m j ], in which m j is a Bayesian condi- tional BPA for O given L j such that m j ({O i }) = p ( j) i and ∑ r i=1 p ( j)
i = 1 for j = 1, . . . , s. Let [L, m] be a compound lottery in which m is a Bayesian BPA for L such that m({L j } = q j for j = 1, . . . , s with ∑ s j=1 q j = 1. Then BPA m defined by Eq. ( 7) is Bayesian, and it verifies m ({O i }) = s ∑ j=1 q j p ( j) i

m a ({O 1 }) = u a , (9a) m a ({O r }) = v a , and (9b)
m a (O 2 ) = w a , (9c)
where u a , v a , w a ≥ 0, and u a + v a + w a = 1. Furthermore,

w a = 0 if a = {O i } is a singleton. Notice that Bel m a ({O 1 }) = u a , and Pl m a ({O 1 }) = u a + w a = 1 -v a .
For singleton subsets, the equivalent bf reference lottery is Bayesian: this ensures that Assumption 3.3 is a generalization of Assumption 2.3. For non-singleton subsets a of outcomes, we may have w a > 0, i.e., the bf reference lottery may not be Bayesian. In other words, we do not assume that ambiguity can be resolved by selecting an equivalent probabilistic reference lottery.

Example 2 Consider lottery L 2 = [{$100, $0}, m 2 ] in Example 1, where m 2 ({$0}) = 1/3, and m 2 ({$100, $0}) = 2/3. Suppose we wish to assess the utility of focal set {$100, $0} using a probabilistic reference lottery [{$100, $0}, (p, 1p)]. A DM may have the following preferences. For any p ≤ 0.2 she prefers {$100, $0} to the probabilistic reference lottery, and for any p ≥ 0.3, she prefers the probabilistic reference lottery to {$100, $0}. However, she is unable to give us a precise p such that {$100, $0} ∼ [{$100, $0], (p, 1p)]. For such a DM, we can assess a bf reference lottery [{$100, $0}, m a ] such that Bel m a ({$100}) = 0.2 and Pl m a ({$100}) = 0.3, i.e., u {$100,$0} = 0.2, v {$100,$0} = 0.7, and w {$100,$0} = 0.1. Assumption 3.4 (Quasi-order) The preference relation for bf lotteries on L b f is a quasi-order, i.e., it is reflexive and transitive.

In contrast with the probabilistic case (Assumption 2.4), we do not assume that is complete. There are many reasons we may not wish to assume completeness. It is Figure 3: Reducing a bf lottery to a bf reference lottery not descriptive of human behavior. Even from a normative point of view, it is questionable that a DM has complete preferences on all possible lotteries. The assumption of incomplete preferences is consistent with the D-S theory of belief functions where we have non-singleton focal sets. Several authors, such as Aumann [START_REF] Aumann | Utility theory without the completeness axiom[END_REF], and Dubra et al. [START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF] argue why the assumption of complete preferences may not be realistic in many circumstances.

The substitutability assumption is similar to the probabilistic case (Assumption 2.5)-we replace an outcome in the probabilistic case by a focal set of m in the bf case.

({O 1 }) = k ∑ i=1 m(a i ) u a i , (10a)
m({O r }) = k ∑ i=1 m(a i ) v a i , and (10b)
m(O 2 ) = k ∑ i=1 m(a i ) w a i , (10c)
where u a i , v a i , and w a i , are the masses assigned, respectively, to {O 1 }, {O r }, and O 2 , by the bf reference lottery a i equivalent to a i .

Next, we formulate the monotonicity assumption. This is less obvious than it is in the probabilistic case (Assumption 2.6), as there are several ways in which intervals may be ordered. Assumption 3.6 below states that, given two bf reference lotteries L and L , the former will be preferred if and only if it assigns a higher degree of belief to the best consequence O 1 , and a lower degree of belief to the worst consequence O r . and Bel m ({O r }) ≤ Bel m ({O r }), i.e., if and only if outcome O 1 is deemed both more credible and more plausible under L than it is if under L . The corresponding indifference relation is L ∼ L if and only if u = u and w = w . It is clear that as defined in Assumption 3.6 is reflexive and transitive. Also, the preference relation on the set of all bf reference lotteries is obviously incomplete. Thus, two lotteries are incomparable if not L L and not L L, i.e., if one of the intervals [u, u + w] and [u , u + w ] is strictly included in the other.

Assumptions 3.1, 3.3 and 3.6 imply the following consistency constraints between the reference bf lotteries equivalent to single outcomes:

1 = u {O 1 } ≥ u {O 2 } ≥ . . . ≥ u {O r } = 0. ( 11
)
Our final assumption has no counterpart in the vN-M theory. It states that a set a of outcomes is always at least as desirable as the worst outcome in a, and at most as desirable as the best outcome in a.

∑ a i ∈2 O m(a i ) u a i ≥ ∑ a i ∈2 O m (a i ) u a i (13a)
and

∑ a i ∈2 O m(a i ) (u a i + w a i ) ≥ ∑ a i ∈2 O m (a i ) (u a i + w a i ). (13b)
Thus, for a bf lottery L = [O, m], we can define

u(L) = [u, u + w] (14)
as an interval-valued utility of L, with

u = ∑ a i ∈2 O m(a i ) u a i and w = ∑ a i ∈2 O m(a i ) w a i . (15)
Also, such a utility function is unique up to a strictly increasing affine transformation, i.e., if u = a u + b, and w = a w + b, where a > 0, and b are real constants, then

u (L) = [u , u + w ]
also qualifies as an interval-valued utility function.

In the imprecise probability literature, we have lower and upper Choquet integrals as follows [START_REF] Gilboa | Maxmin expected utility with a non-unique prior[END_REF][START_REF] Coletti | Models for pessimistic or optimistic decisions under different uncertain scenarios[END_REF]: Definition 6 (Choquet integrals) Suppose we have a real-valued function u : O → R. The lower and upper Choquet integrals of u with respect to BPA m for O, denoted by u m and u m , are defined as follows:

u m = ∑ a∈2 O m(a) min O i ∈a u(O i ) , (16a)
u m = ∑ a∈2 O m(a) max O i ∈a u(O i ) . (16b)
u m ≤ u ≤ u + w ≤ u m , (17)
where u and w are as in Eq. ( 15). Thus, the interval-valued utility of lottery [O, m] as defined in Theorem 5 is always included in the lower-upper expected utility interval. The lower and upper expectations defined by Eq. ( 16) can thus be seen as lower and upper bounds of the interval utility of a lottery L = [O, m] and could be used as conservative estimates if the equivalent bf reference lotteries a i cannot be elicited.

A special case of Theorem 5 is if we use Bayesian bf reference lotteries for the continuity assumption, i.e., w a = 0 for all focal sets a of m. In this case, Theorem 5 implies Corollary 7 below where we have a real-valued utility function, and consequently, a complete ordering on L b f . as the utility of L. Also, such a utility function is unique up to a strictly increasing affine transformation, i.e., if u a = a u a + b, where a > 0, and b are real constants, then

u (L) = ∑ a∈2 O m(a) u a
also qualifies as a utility function.

The utility function in Eq. ( 18) has exactly the same form as Jaffray's linear utility [START_REF] Jaffray | Linear utility theory for belief functions[END_REF]. This is discussed further in Section 5.1.

Examples

In this section, we illustrate the application of Theorem 5 to three examples: Ellsberg's urn problem described in Example 1, the one red ball problem described in [START_REF] Jiroušek | Ambiguity aversion and a decision-theoretic framework using belief functions[END_REF], and the 1,000 balls urns described in [START_REF] Becker | What price ambiguity? or the role of ambiguity in decision-making[END_REF].

Example 3 (Ellsberg's urn) Consider the four bf lotteries described in Example 1. Given a vacuous bf lottery

[{$100, $0}, m({$100, $0}) = 1]
, what is an indifferent bf reference lottery? For an ambiguity-averse DM,

[{$100, $0}, (1/2, 1/2)] [{$100, $0}, m({$100, $0}) = 1].
For such a DM, we must have u {$100, $0} + w {$100, $0} < 1/2.

For the first choice problem between L 1 ($100 on r), and L 2 ($100 on b), using Eq. ( 14), u(L 1 ) = 1/3, and

u(L 2 ) = 2 3 u {$100, $0} , u {$100, $0} + w {$100, $0} .
Thus, an ambiguity-averse DM would choose L 1 . This result is valid as long as u {$100, $0} + w {$100, $0} < 1/2 and is consistent with Ellsberg's findings. For the second choice problem between L 3 ($100 on r or y), and L 4 ($100 on b or y),

u(L 3 ) = 1 3 (1) + 2 3 u {$100, $0} , u {$100, $0} + w {$100, $0} ,
and u(L 4 ) = 2/3. An ambiguity-averse DM would choose L 4 , as

1 3 + 2 3 u {$100, $0} + w {$100, $0} < 2 3 ,
as long as u {$100, $0} + w {$100, $0} < 1/2, a result that is also consistent with Ellsberg's empirical findings.

Example 4 (One red ball) Consider the following example called 'one red ball' in [START_REF] Jiroušek | Ambiguity aversion and a decision-theoretic framework using belief functions[END_REF]. An urn possibly contains balls of six colors: red (r), blue (b), green (g), orange (o), white (w), and yellow (y). One ball is drawn at random from the urn. We are informed that the urn has a total of n balls, where n is a positive integer, and that there is exactly one red ball in the urn. Suppose random variable X denotes the color of the ball drawn from the urn. Then Ω X = {r, b, g, o, w, y}, and m X is a BPA for X such that m X ({r}) = 1/n, and m X ({b, g, o, w, y}) = (n -1)/n. First, you pick a color, and then you draw a ball at random from the urn. You win $100 if the color of the ball drawn from the urn matches the color you picked and you win $0 if it doesn't. What color do you pick? In [START_REF] Jiroušek | Ambiguity aversion and a decision-theoretic framework using belief functions[END_REF], the authors describe some informal experiments where all respondents chose red for n ≤ 7, and for n ≥ 8, several respondents preferred a color different from red. Suppose you pick r. The bf lottery L r based on m X is as follows: [{$100, $0}, m r ], where m r ({$100}) = 1/n, and m r ({$0}) = (n -1)/n. If the color you pick is b, then the bf lottery L b is [{$100, $0}, m b ], where m b ({$0}) = 1/n, and m b ({$100, $0}) = (n -1)/n. Thus, we have u(L r ) = 1/n, and

u(L b ) = n -1 n u {$100, $0} , u {$100, $0} + w {$100, $0} . So, L b is strictly preferred to L r whenever n -1 n u {$100, $0} > 1 n ,
i.e., whenever u {$100, $0} > 1/(n -1), and L r is strictly preferred to L b whenever

n -1 n u {$100, $0} + w {$100, $0} < 1 n ,
i.e., whenever u {$100, $0} + w {$100, $0} < 1/(n -1). Hence, L b is increasingly preferred to L r when n increases, which is consistent with the findings reported in [START_REF] Jiroušek | Ambiguity aversion and a decision-theoretic framework using belief functions[END_REF]. In our model, when

u {$100, $0} < 1 n -1 < u {$100, $0} + w {$100, $0} ,
the two lotteries L r and L b are incomparable. If forced to choose, the DM might just choose arbitrarily. As the experiment reported in [START_REF] Jiroušek | Ambiguity aversion and a decision-theoretic framework using belief functions[END_REF] did not allow the respondents to express inability to choose between the two lotteries, it does not provide any evidence for or against our model.

Example 5 (Urns with 1,000 balls) The following example is discussed in [START_REF] Becker | What price ambiguity? or the role of ambiguity in decision-making[END_REF], where it is credited to Ellsberg in an oral conversation (with the authors of [START_REF] Becker | What price ambiguity? or the role of ambiguity in decision-making[END_REF]). It is also discussed in [START_REF] Einhorn | Decision making under ambiguity[END_REF]. There are two urns, each with 1,000 balls, numbered from 1 -1, 000. Urn 1 has exactly one ball for each number, and there is no ambiguity. Urn 2 has unknown number of balls of each number, and there is much ambiguity. One ball is to be chosen at random from an urn of your choosing. If the number on the ball matches a specific number, e.g., 687, you win $100, and if not, you win nothing ($0). Which one of the two urns will you choose?

It is reported in [START_REF] Becker | What price ambiguity? or the role of ambiguity in decision-making[END_REF] that many respondents chose Urn 2. Why? Urn 1 has only one ball numbered 687, and therefore, the probability of winning $100 if the choice is Urn 1 is very small, 0.001. Urn 2 could possibly have anywhere from 0 to 1, 000 balls numbered 687. Thus, the choice of Urn 2, although ambiguous, is appealing. Let's analyze this problem using Theorem 5.

Let X 1 denote the number on the ball chosen from Urn 1, and let X 2 denote the number on the ball chosen from Urn 2. Ω

X 1 = Ω X 2 = {1, . . . , 1000}. Function m X 1 is a BPA for X 1 as follows: m X 1 ({1}) = . . . = m X 1 ({1000}) = 0.001. BPA m X 2 is vacuous, i.e., m X 2 (Ω X 2 ) = 1.
Lottery L 1 corresponding to choice of Urn 1 (say, alternative f 1 ) is [{$100, $0}, m 1 ], where m 1 is a BPA for {$100, $0} such that m 1 ({$100}) = 0.001, and m 1 ({$0}) = 0.999. L 1 is a bf reference lottery, and thus, u(L 1 ) = 0.001. Lottery L 2 corresponding to choice of Urn

2 (say, alternative f 2 ) is [{$100, $0}, m 2 ], where m 2 is a vacuous BPA for {$100, $0}. The utility of L 2 is u(L 2 ) = u {$100, $0} , u {$100, $0} + w {$100, $0} .
Consequently, L 2 is preferred to L 1 as long as u {$100, $0} ≥ 0.001, a condition that is easily satisfied. This may explain why many DMs prefer to be ambiguity-seeking in this context, i.e., prefer L 2 to L 1 .

Comparison

In this section, we compare our utility theory to Jaffray's linear utility theory [START_REF] Jaffray | Linear utility theory for belief functions[END_REF], and to Smets' two-level decision theory [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF].

Comparison with Jaffray's Axiomatic Theory

Jaffray's axiomatic theory is based on considering the set of all belief functions for O as a mixture set as follows. Suppose m 1 and m 2 are BPAs for O, and suppose λ ∈ [0, 1]. Then m defined as:

m(a) = λ m 1 (a) + (1 -λ )m 2 (a) (19)
for all a ∈ 2 O , is a BPA for O. BPA m can be written as m = λ m 1 + (1λ )m 2 , and called a mixture of m 1 and m 2 . Using the Jensen-version [START_REF] Jensen | An introduction to Bernoullian utility theory: A discussion[END_REF] of vN-M axiom system, Jaffray uses the following assumptions, all of which are expressed using mixture BPA functions:

[O, λ m 1 + (1 -λ ) m 3 ] [O, m 2 ] [O, µ m 1 + (1 -µ) m 3 ].
Theorem 8 (Jaffray's representation theorem [START_REF] Jaffray | Linear utility theory for belief functions[END_REF])

The preference relation on L b f satisfies Assumptions 5.1-5.3 if and only if there exists a utility function u :

L b f → R such that for any lottery L = [O, m] in L b f , u(L) = ∑ a∈2 O m(a) u a , (20)
where u a = u([O, m d a ]), and m d a is a deterministic BPA for O such that m d a (a) = 1.

Thus, Jaffray's axioms result in the same solution as that of Corollary 7, which is a special case of Theorem 5. As Jaffray's axioms do not use Dempster's rule explicitly, it is not clear whether Eq. ( 20) applies to the D-S framework or not. The mixture BPA m derived from BPAs m 1 and m 2 using Eq. ( 19) is not Dempster's combination rule, although Eq. ( 19) can be derived from a belief function model using Dempster's rule. By deriving this solution from a set of axioms making use of the basic constructs of DS theory (namely, Dempster's combination rule, marginalization, and conditional embedding), we provide additional arguments supporting Eq. ( 20) as a natural definition of the real-valued utility of a bf lottery in the D-S theory.

Also, there is no explicit notion of a bf reference lottery in Jaffray's framework. Thanks to our continuity axiom (Assumption 3.3), the interval-valued utility [u a , u a + w a ] in our framework receives a simple interpretation as an interval-valued probability of a best outcome O 1 , in a bf reference lottery [O 2 , m a ] that is indifferent to a and such that m a ({O 1 }) = u a , m a ({O r }) = 1 -(u a + w a ), and m a (O 2 ) = w a . We believe that this simple interpretation can be very helpful when eliciting utilities from DMs.

Comparison with Smets' Decision Theory

Smets' decision theory [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF] is a two-level framework where beliefs, represented by belief functions, are held at a credal level. When a DM has to make a decision, the marginal belief function for a variable of interest is transformed into a PMF, and the Bayesian expected utility framework is then used to make a decision.

Smets uses a transformation called the pignistic transform to transform belief functions into PMFs. This transform is justified in [START_REF] Smets | Decision making in the TBM: The necessity of the pignistic transformation[END_REF] using a mixture property as follows. Let T denote the belief-PMF transformation. Smets [START_REF] Smets | Decision making in the TBM: The necessity of the pignistic transformation[END_REF] argues that this transformation should be linear, i.e., we should have, for any λ ∈ [0, 1],

T (λ m 1 + (1 -λ ) m 2 ) = λ T (m 1 ) + (1 -λ )T (m 2 ).
for all O ∈ O, where I(•) is the indicator function. The pignistic PMF BetP m is mathematically identical to the Shapley value in cooperative game theory [START_REF] Shapley | A value for n-person games[END_REF]. In [START_REF] Smets | Decision making in the TBM: The necessity of the pignistic transformation[END_REF], Smets attempts to derive Eq. ( 21) from the maximum expected utility principle. The argument, however, is quite technical and unconvincing. Given the definition in Eq. ( 22), the expected utility of a bf lottery L = [O, m] according to the pignistic PMF is

u BetP (L) = ∑ O∈O BetP m (O) u {O} (23a) = ∑ O∈O ∑ a⊆O m(a) |a| I(O ∈ a) u {O} (23b) = ∑ a⊆O m(a) 1 |a| ∑ O∈a u {O} . (23c)
It is a special case of Eq. ( 18), with

u a = 1 |a| ∑ O∈a u {O} .
Smets' decision theory thus amounts to assuming that a DM is indifferent between a bf lottery that gives them an outcome in a for sure, and a bf reference lottery in which the probability of the best outcome is equal to the average utilities of the outcomes in a. This is consistent with our Assumptions 3.1-3.6, but it is inconsistent with Assumption 3.7. Also, this restricted model does not have a parameter to represent a DM's attitude toward ambiguity. As a result, it is unable to explain Ellsberg's paradox and the ambiguity aversion of human DMs as described, e.g., in the examples in Section 4.

Summary and Conclusions

In this section, we summarize our proposal and sketch some future work. We start with Luce and Raiffa's version of the vN-M utility theory for probabilistic lotteries. We then consider bf lotteries, lotteries when our beliefs about the state of the world is described by DS belief functions. We use a similar set of axioms as vN-M, but first we replace each singleton outcome in a probabilistic lottery by a focal set of a BPA. Second, we replace the reduction of compound lotteries with a corresponding axiom that uses Dempster's combination rule and belief function marginalization in place of probabilistic combination (pointwise multiplication followed by normalization) and probabilistic marginalization (addition). Third, we use a bf reference lottery with two independent parameters. The axioms lead to a decision theory that involves assessing the utility of each focal element of a BPA as an interval-valued utility.

Interval-valued utilities lead to a partial preference relation on the set L b f of all bf lotteries. If we use Bayesian bf reference lotteries with a single parameter, then our axiomatic framework leads to a real-valued utility function that is exactly the same as in Jaffray's linear utility theory [START_REF] Jaffray | Linear utility theory for belief functions[END_REF].

The decision theory that results from our axioms is more general than that proposed by Jaffray [START_REF] Jaffray | Linear utility theory for belief functions[END_REF], which can be construed as a decision theory for belief functions interpreted as generalized probabilities. Jaffray's axiomatic theory is based on a set of mixture BPAs. A mixture of two BPAs is not the same as a Dempster's combination of two BPAs, although we could construct a belief function model where the mixture BPA is obtained by Dempster's rule. Thus, it is not clear if Jaffray's linear utility theory is applicable to D-S belief function lotteries or not. Our utility theory confirms that this is indeed the case. Our bf reference lotteries lead to interval-valued utilities, and consequently, a partial preference relation on the set of all bf lotteries.

We also compare our axiomatic theory to Smets' twolevel framework [START_REF] Smets | Decision making in a context where uncertainty is represented by belief functions[END_REF][START_REF] Smets | Decision making in the TBM: The necessity of the pignistic transformation[END_REF], and note that his framework is too constrained to explain ambiguity-aversion or ambiguityseeking behavior of human DMs.

In practice, implementing the most general form of our axiomatic theory may need assessment of 2 k parameters, where k is the number of focal sets of a bf lottery. In the worst case, k can be as large as 2 |O| -1. In [START_REF] Denoeux | An interval-valued utility theory for decision making with Dempster-Shafer belief functions[END_REF], based on additional assumptions, we propose a model based on only two parameters, which can be interpreted as reflecting both the DM's attitude to ambiguity and their indeterminacy. This model, as well as others, will have to be further studied and developed. More generally, a rigorous methodology to elicit interval-valued utilities remains to be designed.

Figure 1 :Figure 2 :

 12 Figure 1: A two-stage compound lottery reduced to an indifferent simple lottery

Theorem 2 (

 2 [START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF])Ifthe preference relation on L satisfies Assumptions 2.1-2.6, then there are numbers u i associated with outcomes O i for i = 1, . . . , r, such that for any two lotteries L = [O, p], and L = [O, p ], L L if and only if r

Assumption 3 . 1 (

 31 Weak ordering of outcomes) The DM's preferences for outcomes in O = {O 1 , . . . , O r } are complete and transitive.

Assumption 3 . 2 (

 32 Reduction of compound lotteries) Suppose [L, m] is a compound lottery as described in the previous paragraph. Then, [L, m] ∼ [O, m ], where m = m ⊕ s j=1 m L j , j ↓O ,

( 8 )

 8 for i = 1, . . . , r. Next, we define a bf reference lottery [O 2 , m] as a bf lottery on O 2 = {O 1 , O r }. A bf reference lottery has three parameters u = m({O 1 }), v = m({O r }), and w = m(O 2 ), which are all non-negative and sum to 1. The following assumption states that any deterministic bf lottery is equally preferred to some bf reference lottery. Assumption 3.3 (Continuity) Any subset of outcomes a ⊆ O (considered as a deterministic bf lottery) is indifferent to a bf reference lottery a = [O 2 , m a ] such that

Assumption 3 . 5 (

 35 Substitutability) In any bf lottery L = [O, m], if we substitute a focal set a of m by an equally preferred bf reference lottery a = [O 2 , m a ], then the result is a compound lottery that is equally preferred to L. It follows from Assumptions 3.1-3.5 that given any bf lottery, we can reduce it to an equally preferred bf reference lottery. This is stated as Theorem 4 below. Theorem 4 (Reducing a bf lottery) Under Assumptions 3.1-3.5, any bf lottery L = [O, m] with focal sets a 1 , . . . , a k is indifferent to a bf reference lottery L = [O 2 , m], such that m

Assumption 3 . 6 (

 36 Monotonicity) Suppose L = [O 2 , m] and L = [O 2 , m ] are bf reference lotteries, with m({O 1 }) = u, m(O) = w, m ({O 1 }) = u , m (O) = w . Then, L L if and only if u ≥ u and u + w ≥ u + w . Thus, L L if and only if Bel m ({O 1 }) ≥ Bel m ({O 1 })

Assumption 3 . 7 (

 37 Consistency) Let a ⊆ O, and let O a and O a denote, respectively, the worst and the best outcome in a. Then we have a O a and O a a. Assumptions 3.6 and 3.7 imply that, for any focal sets a of m, we have u a ≥ min O i ∈a u {O i } , and u a + w a ≤ max O i ∈a u {O i } . (12) 3.3. Representation theorem Theorem 5 (Interval-valued utility function) Suppose L = [O, m] and L = [O, m ] are bf lotteries on O. If the preference relation on L b f satisfies Assumptions 3.1-3.6, then there are intervals [u a i , u a i + w a i ] associated with subsets a i ∈ 2 O such that L L if and only if

  Thus, we can regard the interval [u m , u m ] as an intervalvalued utility of bf lottery [O, m] as defined in the imprecise probability literature. It follows from Theorem 4 and Assumption 3.7 that

Corollary 7 (

 7 Real-valued utility function) Suppose L = [O, m] and L = [O, m ] are bf lotteries on O. If the preference relation on L b f satisfies Assumptions 3.1-3.6 and if w a = 0 for all focal sets a of m and m , then there are numbers u a associated with nonempty subsets a ⊆ O such that L 1 L 2 if and only if

  ∑ a∈2 O m(a) u a ≥ ∑ a∈2 O m (a) u a .Thus, for a bf lottery L = [O, m], we can define u(L) = ∑ a∈2 O m(a) u a[START_REF] Hausner | Multidimensional utilities[END_REF]

Assumption 5 . 1 (

 51 Completeness and transitivity)The relation is complete and transitive over L b f .Assumption 5.2 (Independence) For all L 1 = [O, m 1 ] and L 2 = [O, m 2 ] in L b f , and λ ∈ (0, 1), L 1 L 2 implies [O, λ m 1 + (1λ ) m] [O, λ m 2 + (1λ ) m]. Assumption 5.3 (Continuity) For all L 1 = [O, m 1 ], L 2 = [O, m 2 ], and L 3 = [O, m 3 ] in L b f such that L 1 L 2 L 3 ,there exists λ and µ in (0, 1) such that

( 21 )

 21 The unique transformation T verifying (21) is the pignistic transformation defined as T (m) = BetP m with BetP m (O) = ∑ a⊆O m(a) |a| I(O ∈ a)

  the DM is indifferent between (or equally prefers) O i and O j , and write O i O j if the DM either strictly prefers O i to O j or is indifferent between the two.

  Given Assumption 2.1, without loss of generality, let us assume that the outcomes are labelled such that O 1 O 2 • • • O r , and to avoid trivialities, assume that O 1 O r .

	Assumption 2.1 (Weak ordering of outcomes) For any
	two outcomes O i and O j , either O i O j or O j O i . Also,
	if O i O j and O j O k , then O i O k . Thus, the preference
	relation over O is a weak order, i.e., it is complete and
	transitive.

© T. Denoeux & P.P. Shenoy.

The assumption of finiteness of the sets Ω X and O is only for ease of exposition. It is unnecessary for the proof of the representation theorem in this section.

Acknowledgments

This research was done during a visit by the second author to Université de Technologie de Compiègne (UTC) in Spring 2019. This research was funded partially by a sabbatical from the University of Kansas, and supported by the Labex MS2T, which is funded by the French Government through the program "Investments for the future" by the National Agency for Research (reference ANR-11-IDEX-0004-02). Thanks to Sébastien Destercke for many discussions on the topic of this manuscript, and to Suzanna Emelio for proofreading this manuscript.