domain: spi phys math info

text:
Qing Wei
email: qingwei@seu.edu.cn

Xinde Li
email: xindeli@seu.edu.cn

Jean Dezert
email: jean.dezert@onera.fr

Approximation of Basic Belief Assignment Based on Focal Element Compatibility

Keywords: Information fusion, Belief functions, Basic belief assignment, Approximation

The theory of belief functions is an important tool in the field of information fusion. However, the fusion of Basic Belief Assignments (BBAs) requires high computational cost and long computing time when a large number of focal elements are involved in the fusion rules. This problem becomes a bottleneck of application of Belief Functions (BF) in high-dimensional real problems. To overcome this drawback, many approaches were proposed to approximate BBAs to reduce the computational complexity in the fusion process. In this paper, we present a novel method based on the compatibility of focal elements to approximate a BBA by removing some focal elements of the original BBA. Besides, a new mass assignment strategy based on the distance of focal elements is proposed. Several examples, simulations and related analyses are provided to illustrate the interest and efficiency of the proposed method.

I. INTRODUCTION

The evidence theory was proposed by Dempster in the study of multivalued mapping in 1967 [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and later promoted by Shafer in 1976 [START_REF] Shafer | A mathematical theory of evidence[END_REF] with the introduction of Belief Functions (BF). The theory of belief functions is named also Dempster-Shafer Theory (DST) in the literature. Belief Functions provide an effective method for dealing with the expression and synthesis of uncertain information and they have been widely used in many fields such as image processing [START_REF] Pohl | Multisensor image fusion in remote sensing: concepts, methods and applications[END_REF][START_REF] Yang | Fusion of infrared polarization and intensity images using support value transform and fuzzy combination rules[END_REF], target tracking [START_REF] Shen | Sensor selection based on generalized information gain for target tracking in large sensor networks[END_REF], and fault diagnosis [START_REF] Yuan | Modeling sensor reliability in fault diagnosis based on evidence theory[END_REF][START_REF] Jiang | An evidential sensor fusion method in fault diagnosis[END_REF].

However, the evidence combination will encounter high computational cost when the frame of discernment (FoD) is large. To overcome this drawback, one effective approach to reduce the computational complexity is the BBA approximation. The BBA approximation aims to obtain a simpler BBA by removing some focal elements according to different simplification criteria. In existing works, the simplification criteria can be divided into the following three categories:

1) Simplification based on the mass assignment of a focal element. The focal elements with smaller mass assignments are deemed unimportant, which should be removed firstly. klx [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF], Summarization [START_REF] Lowrance | A framework for evidential-reasoning systems[END_REF] and D1 [START_REF] Bauer | Approximations for decision making in the Dempster-Shafer theory of evidence[END_REF] are representatives of this criterion. 2) Simplification based on the cardinality of a focal element. The focal elements with larger cardinalities may cause more computational cost. k-additive approach [START_REF] Grabisch | Upper approximation of non-additive measures by k-additive measures-the case of belief functions[END_REF] and hierarchical proportional redistribution approach [START_REF] Dezert | Hierarchical proportional redistribution for BBA approximation[END_REF] accomplish the simplification according to this criterion. 3) Hybrid simplification mixing the two previous ones.

Use the previous two criteria jointly to determine which focal elements should be removed at first. Methods like inner and outer approximation [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF], rank-level fusion approximation [START_REF] Yang | A novel approximation of basic probability assignment based on ranklevel fusion[END_REF], non-redundancy approximation [START_REF] Han | Two novel methods for BBA approximation based on focal element redundancy[END_REF], iterative approximation based on distance of evidence [START_REF] Yang | Iterative approximation of basic belief assignment based on distance of evidence[END_REF] and correlation coefficient approximation [START_REF] Shou | Approximation of basic probability assignment in dempstershafer theory based on correlation coefficient[END_REF] enter in this hybrid simplification strategy. In general, the hybrid simplification is the right direction to approximate a BBA due to the one-sidedness of the first and the second simplification criterion.

In this paper, we propose a novel approach using the notion of focal element compatibility. In our method, each focal element has a compatible focal element which can be replaced by it due to the compatibility (based on a similarity measure) between them. To quantify the notion of compatibility, we use the mass value and the cardinality of the set which contains all the focal elements which can replace the given focal element jointly. The focal element with the highest degree of compatibility should be removed at first. Users can preset the number of remaining focal elements. After removing a focal element, the removed mass is redistributed to remaining focal elements to execute the next iteration according to our new mass assignment strategy. Experimental results based on the comparisons with other approximation strategies and related analyses justify that our approach is rational and effective.

This paper is organized as follows. After brief preliminaries on Belief Functions in Section II and classical BBA approximation methods in Section III, we will present the new approximation method based on focal element compatibility in Section IV. Evaluation of it and comparative analysis will be done in Section V with concluding remarks in Section VI.

II. PRELIMINARIES

A. Basics of Belief Functions

We consider a frame of discernment (FoD) Θ = {θ 1 , ..., θ n } whose elements are mutually exclusive and exhausive. A basic belief assignment (BBA) over the FoD Θ is defined as

A⊆Θ m(A) = 1, m(∅) = 0 (1)
If m(A) > 0 holds, A is called a Focal Element (FE). The belief function and plausibility function are defined as follows [START_REF] Shafer | A mathematical theory of evidence[END_REF].

Bel(A) = B⊆A m(B); P l(A) = A∩B =∅ m(B) (2)
In DST, two independent bodies of evidence (BOEs) are combined by Dempster's rule as follows. ∀A ∈ 2 Θ :

m(A) = ⎧ ⎨ ⎩ 0, A = ∅ 1 1-K Ai∩Bj =A m 1 (A i )m 2 (B j ), A = ∅ ( 3
)
where

K = Ai∩Bj =∅ m 1 (A i )m 2 (B j )
is the conflict coefficient, which represents the total degree of conflict. Other rules of combinations have also been proposed to combine BBAs in the literature [START_REF] Smarandache | Advances and applications of dsmt for information fusion-collected worksvolume 3[END_REF] but they will be not detailed in this paper since this is out of its scope.

B. Distance of Focal Elements

We use the definition proposed by Denoeux [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF] to measure the distance between two focal elements, which is defined as

δ ∩ (A i , A j ) =m(A i )|A i | + m(A j )|A j | -[m(A i ) + m(A j )]|A i ∩ A j | (4)
For a given focal element A i , if δ ∩ (A i , A j ) = min j =i δ ∩ (A i , A j ), we will say that A j has the highest compatibility degree with A i , and A j shares the most similar information with A i .

III. BRIEF REVIEW OF BBA APPROXIMATIONS

Some existing BBA approximation approaches are briefly reviewed in this section for the purpose of comparisons with our new method.

1) k-l-x approximation [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF]. This method involves three parameters and the approximated BBA is obtained by

• keeping no less than k focal elements;

• keeping no more than l focal elements; • deleting the masses which are no greater than x. In klx algorithm, all original focal elements are sorted according to the mass assignments in a decreasing order. Then, the first p focal elements are selected such that k ≤ p ≤ l and such that the sum of the mass assignments of these p focal elements is no less than 1-x. The removed mass assignments are redistributed to remaining focal elements by a classical normalization procedure.

2) Summarization approximation [START_REF] Lowrance | A framework for evidential-reasoning systems[END_REF]. This method also keeps focal elements having largest mass values which is similar to the klx method. The only difference is that the removed mass values are redistributed to their union set. Suppose that m(•) is the original BBA and k is the desired number of remaining focal elements in the approximated BBA m(•). Let M denote the set of k-1 focal elements with largest mass values in m(•). Then m(•) is obtained from m(•) by

m(A) = ⎧ ⎪ ⎨ ⎪ ⎩ m(A), A ∈ M A ⊆A,A / ∈M m(A ), A = A 0 0, otherwise (5)
where

A 0 is A 0 A / ∈M,m(A )>0 A (6)
3) D1 approximation [START_REF] Bauer | Approximations for decision making in the Dempster-Shafer theory of evidence[END_REF]. Suppose that m(•) is the original BBA and k is the desired number of remaining focal elements in the approximated BBA m(•). Let M denote the set of k -1 focal elements with largest mass values in m(•) and M -be the set including all the other focal elements of m(•). D1 method is to keep all the members of M as the focal elements of m(•) and to assign the mass values of the focal elements in M - among the focal elements in M according to the following procedure.

For a focal element A ∈ M -, in M , find all the supersets of A to construct a collection M A . If M A is not empty, the mass value of A is uniformly assigned among the focal elements having smallest cardinality in M A . When M A is empty, then construct M A as

M A = {B ∈ M ||B| ≥ |A|, B ∩ A = ∅} (7)
Then, if M A is not empty, m(A) is assigned among the focal elements with smallest cardinality in M A . The value assigned to a focal element B depends on the value of |B ∩ A|. Such a procedure is iteratively executed until all m(A) have been assigned to the focal elements in M .

If M A is empty, there are two possible cases:

• If the total set Θ ∈ M , the sum of mass values of the focal elements in M -will be added to Θ; • If Θ / ∈ M , then let Θ be a focal element of m(•) and assign the sum of mass values of the focal elements in M -to m(Θ).

Note that the number of remaining focal elements is

k -1, if Θ ∈ M .
4) Rank-level fusion approximation [START_REF] Yang | A novel approximation of basic probability assignment based on ranklevel fusion[END_REF]. This method uses jointly the mass assignments and cardinalities of focal elements to make the simplification. The specific procedure is listed as follows.

• Sort all the focal elements of the original BBA (with L focal elements) according to the mass assignments (in ascending order which is due to the assumption that the focal element with smallest mass should be removed at first). The rank vector obtained is

r m = [r m (1), r m (2), ..., r m (L)] (8)
• Sort all the focal elements of the original BBA according to the cardinalities (in descending order which is due to the assumption that the focal element with large cardinality should be removed at first). The rank vector obtained is

r c = [r c (1), r c (2), ..., r c (L)] (9)
• Execute the rank-level fusion and the comprehensive rank vector is

r f = [r f (1), r f (2), ..., r f (L)] (10)
where

r f (i) = α • r m (i) + (1 -α) • r c (i) (11)
The parameter α ∈ [0, 1] is to weight the two different criteria. Finally, we remove the focal element with the smallest r f value and do the renormalization of remaining focal elements.

Repeat the above steps until only k focal elements remain and the total mass assignments value to be deleted is no greater than x. 5) Correlation coefficient approximation [START_REF] Shou | Approximation of basic probability assignment in dempstershafer theory based on correlation coefficient[END_REF]. The correlation coefficient proposed by Jiang [START_REF] Jiang | A correlation coefficient for belief functions[END_REF] can measure the similarity between two BBAs. In this approximation approach, we remove a focal element A i from the original BBA m(•) and the mass of A i is redistributed to remaining focal elements to generate a new BBA mi (•). Then, we calculate the correlation coefficient between m and mi . We perform the same operation for each focal element and sort all the focal elements in ascending order according to the correlation coefficient. Finally, we remove the largest k focal elements from the original BBA and do the normalization according to a new assignment strategy.

6) Iterative approximation based on distance of evidence [START_REF] Yang | Iterative approximation of basic belief assignment based on distance of evidence[END_REF]. In this algorithm, we remove at first a focal element A i from the original BBA m(•) and we normalize the remaining focal elements to generate a new BBA mi (•). Then, we calculate Jousselme's distance between m and mi . We perform the same operation for each focal element. Finally, we remove the focal element which generates the new BBA having the closest distance with the original BBA and after a normalization we proceed the next iteration. The above steps are performed iteratively until only k focal elements remain.

IV. NEW BBA APPROXIMATION BASED ON FOCAL

ELEMENT COMPATIBILITY In this section, a novel method for approximating a BBA is proposed. As briefly shown in the previous section, the existing approaches remove some focal elements according to the mass assignment, the cardinality or both two criteria. Here we adopt a different standpoint in which a specific focal element can be removed if there exists a number of other focal elements compatible with it, i.e., its degree of incompatibility is small. Now the focus is how to define the degree of incompatibility of a focal element. We define the incompatibility degree for a focal element at first.

A. Degree of Incompatibility of Focal Elements

As mentioned before, the distance between two focal elements is given by Eq.( 4). The compatible focal element A C i 1 1 We use the notation "C" as the upper index because it is the first letter of word "Compatible". of a given focal element A i ⊆ Θ for a BBA m(•) (with l focal elements) is defined by

A C i arg min Aj δ ∩ (A i , A j ) s.t. A j ⊆ Θ j = 1, 2, ..., l, j = i (12)
A C i has the smallest distance with the focal element A i , i.e., among all focal elements, A C i is the most compatible with A i . It should be noted that A C i can be replaced by A i , but the reverse may not be true.

We define the degree of incompatibility of the focal element A i by

ICP (A i ) m(Ai) |M C i | , M C i = ∅ ∞, M C i = ∅ ( 13
)
where

M C i = A j |A C j = A i , j = 1, 2, ..., l, j = i ( 14
)
The set M C i contains all the focal elements which can replace A i . The ICP (A i ) value describes the average effect on the

|M C i | (M C i = ∅
) focal elements after removing A i . The smaller ICP (A i ) value, the smaller the effect, which is preferred. From another perspective, the effect can be explained as the incompatibility degree of A i . The smaller the effect, the smaller the incompatibility degree and the more it can be removed. M C i = ∅ means that no focal elements can replace A i , so its degree of incompatibility is infinite.

Here we provide a simple example to show how M C i and ICP (A i ) are computed. m(A 1 ) = 0.5, m(A 2 ) = 0.28 m(A 3 ) = 0.17, m(A 4 ) = 0.05 1) We calculate the distance between any two focal elements and find the compatible focal element for each focal element.

δ ∩ (A 1 , A 2 ) = 0.78, δ ∩ (A 1 , A 3 ) = 0.84 δ ∩ (A 1 , A 4 ) = 0.1, δ ∩ (A 2 , A 3 ) = 0.17 δ ∩ (A 2 , A 4 ) = 0.1, δ ∩ (A 3 , A 4 ) = 0.05 A C 1 = A C 2 = A C 3 = A 4 , A C 4 = A 3 2) We compute M C i for each focal element. M C 1 = M C 2 = ∅ M C 3 = {A 4 } , M C 4 = {A 1 , A 2 , A 3 } 3) We compute ICP (A i ) for each focal element. ICP (A 1 ) = ICP (A 2 ) = ∞ ICP (A 3 ) = m(A 3 ) |M C 3 | = 0
.17 1 = 0.17

ICP (A 4 ) = m(A 4 ) |M C 4 | = 0.05 3 = 0.0167 So, A 4 = {θ 1 , θ 2 ,
m(A i ) = m(A i ) + m(Ar) D•δ∩(A i ,Ar) , A i = ∅ 0, A i = ∅ ( 15
)
where

D = l-1 i=1 1 δ ∩ (A i , A r ) , A i = ∅ ( 16
)
The proof that m(•) is a true normalized BBA is given in Appendix.

From Eq.( 15) and ( 16), we can see that the mass of each removed focal element A r is redistributed to remaining focal elements A j according to their distances to A r . The smaller the distance, the more mass is committed to A j . Based on the compatibility of the focal elements and the new mass assignment strategy, we propose a novel BBA approximation approach described in the next subsection.

C. New BBA Approximation Algorithm

Let m(•) denote the original BBA with l focal elements. In the approximation, we want to keep k (k < l) focal elements and remove the focal elements one by one iteratively. The detailed steps of this new BBA approximation method are as follows.

• Here we provide an illustrative example to show how our approximation method works and we compare it with other methods.

TABLE I FOCAL ELEMENTS AND MASS VALUES OF m(•).

Focal Elements Mass Values

A 1 = {θ 1 } 0.13 A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } 0.06 A 3 = {θ 4 , θ 5 } 0.3 A 4 = {θ 3 , θ 5 } 0.15 A 5 = {θ 1 , θ 2 } 0.14 A 6 = {θ 2 , θ 4 , θ 5 } 0.12 A 7 = {θ 2 , θ 5 } 0.1 in k -l-x.
II mklx (•) OBTAINED USING k -l -x.

Focal Elements Mass Values

A 1 = {θ 1 } 0.1548 A 2 = {θ 4 , θ 5 } 0.357 A 3 = {θ 3 , θ 5 } 0.1786 A 4 = {θ 1 , θ 2 } 0.1667 A 5 = {θ 2 , θ 4 , θ 5 } 0.1429
2) Summarization approximation. Here k is set to 5. According to the summarization method, the focal elements

A 2 = {θ 2 , θ 3 , θ 4 , θ 5 }, A 7 = {θ 2 ,

Focal Elements Mass Values

A 1 = {θ 1 } 0.13 A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } 0.28 A 3 = {θ 4 , θ 5 } 0.3 A 4 = {θ 3 , θ 5 } 0.15 A 5 = {θ 1 , θ 2 } 0. 14
3) D1 approximation. Here k is set to 5. It can be obtained that A 3 , A 4 , A 5 , A 1 belong to M , and A 6 , A 7 , A 2 belong to M -. For A 6 and A 2 , there are no supersets of them in M , i.e., M A = ∅, and we can not construct the set M A , i.e., M A = ∅. So the mass values of A 6 and A 2 are assigned to the total set Θ. For A 7 , we can construct the set M A = {A 3 , A 4 , A 5 }. The parameter ratio and number are calculated to be 1 and 3. Therefore, m(A 7 )/3 = 0.0333 is added to the mass value of A 3 , A 4 and A 5 respectively. The approximated BBA mD1 (•) is listed in Table IV.

Focal Elements Mass Values

A 1 = {θ 1 } 0.13 A 2 = {θ 4 , θ 5 } 0.3334 A 3 = {θ 3 , θ 5 } 0.1833 A 4 = {θ 1 , θ 2 } 0.1733 A 5 = Θ 0. 18
4) Rank-level fusion approximation.

Here k and l are set to 5 and x is 0.2. The parameter α is set to 0.5. At the first iteration, we calculate the comprehensive vector r f = [r f (A 1 ), r f (A 2 ), ..., r f (A 7 )] = [5.5, 1, 5, 4.5, 4, 2.5, 2.5]. Then we remove A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } at first and do the normalization of remaining focal elements. At the second iteration, we obtain the comprehensive vector 5, 4, 3.5, 3, 1.5, 1.5]. Then, we remove A 6 = {θ 2 , θ 4 , θ 5 } (or A 7 ) and normalize the remaining focal elements to obtain the final approximated BBA mRank (•) listed in Table V.

r f = [r f (A 1 ), r f (A 3 ), r f (A 4 ), r f (A 5 ), r f (A 6 ), r f (A 7 )] = [4.

Focal Elements Mass Values

A 1 = {θ 1 } 0.1585 A 2 = {θ 4 , θ 5 } 0.3659 A 3 = {θ 3 , θ 5 } 0.1829 A 4 = {θ 1 , θ 2 } 0.1707 A 5 = {θ 2 , θ 5 } 0.122

5) Correlation coefficient approximation.

Here k is set to 2, i.e., we have to remove two focal elements. The correlation coefficients between the remaining BBA mi (•), i = 1, 2, ..., 7 and the original BBA m(•) are 0.9805, 0.9981, 0.9274, 0.9778, 0.9842, 0.9946 and 0.9927. We sort all the focal elements in ascending order according to the correlation coefficient and remove the two bottom focal elements A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } and A 6 = {θ 2 , θ 4 , θ 5 } from the original BBA. Then, we redistribute the removed mass to remaining focal elements to obtain the final approximated BBA mCC (•) listed in Table VI.

Focal Elements Mass Values

A 1 = {θ 1 } 0.13 A 2 = {θ 4 , θ 5 } 0.3718 A 3 = {θ 3 , θ 5 } 0.1839 A 4 = {θ 1 , θ 2 } 0.1677 A 5 = {θ 2 , θ 5 } 0.1466 6
) Iterative approximation based on distance of evidence. Here k is set to 2, i.e., we have to remove two focal elements. At the first iteration, Jousselme's distances between the remaining BBA mi (•), i = 1, 2, ..., 7 and the original BBA m(•) are 0.1053, 0.0315, 0.1932, 0.1049, 0.105, 0.05981 and 0.05982. We remove A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } at first. Then, we normalize the remaining focal elements and assign m = m2 to execute the next iteration. At the second iteration, Jousselme's distances between the remaining BBA mi (•), i = 1, 3, 4, 5, 6, 7 and m(•) are 0.1113, 0.2101, 0.114, 0.1118, 0.0644 and 0.0663. So we remove A 6 = {θ 2 , θ 4 , θ 5 } and normalize the remaining focal elements to obtain the final approximated BBA mDis (•) listed in Table VII.

Focal Elements Mass Values

A 1 = {θ 1 } 0.1585 A 2 = {θ 4 , θ 5 } 0.3659 A 3 = {θ 3 , θ 5 } 0.1829 A 4 = {θ 1 , θ 2 } 0.1707 A 5 = {θ 2 , θ 5 } 0.122 7
) ICP method (Our approximation method). The desired remaining focal elements is set to k = 5 and we obtain the final approximated BBA in two iterations as follows.

• The first iteration: We first calculate

ICP (A i ), i = 1,
C i | ICP (A i ) A 3 = {θ 4 , θ 5 } 0.3 M C 3 = ∅ ∞ A 4 = {θ 3 , θ 5 } 0.15 M C 4 = ∅ ∞ A 7 = {θ 2 , θ 5 } 0.1 M C 7 = ∅ ∞ A 5 = {θ 1 , θ 2 } 0.14 1 0.14 A 1 = {θ 1 } 0.13 1 0.13 A 6 = {θ 2 , θ 4 , θ 5 } 0.12 1 0.12 A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } 0.06 4 0.015
The Second Iteration Focal Elements Mass Values

|M C i | ICP (A i ) A 3 = {θ 4 , θ 5 } 0.3105 M C 3 = ∅ ∞ A 4 = {θ 3 , θ 5 } 0.1605 M C 4 = ∅ ∞ A 5 = {θ 1 , θ 2 } 0.

V. EXPERIMENTS AND ANALYSIS

In this section, we compare all the aforementioned BBA approximation methods to demonstrate the effectiveness and interest of our method in terms of three Measures of Performance (MoP): 1) closeness, 2) computational efficiency, and 3) decision-making.

A. MoP of Closeness and Computational Efficiency

The smaller the distance between the new approximated BBA and the original BBA, the less information is lost, which is preferred. We use d E BI distance [START_REF] Han | New distance measures of evidence based on belief intervals[END_REF] to describe the degree of closeness between two pieces of evidence, which is defined as

d E BI (m 1 , m 2 ) = N c • 2 n -1 i=1 [d I (BI 1 (A i ), BI 2 (A i ))] 2 (17)
Here N c = 1/2 The strict distance between interval numbers [a

1 , b 1 ] and [a 2 , b 2 ](b i ≥ a i , i = 1, 2) is defined by d I ([a 1 , b 1 ], [a 2 , b 2 ]) = a 1 + b 1 2 - a 2 + b 2 2 2 + 1 3 b 1 -a 1 2 - b 2 -a 2 2 2 (18)
Our comparative analysis is based on a Monte Carlo simulation using M = 200 random runs. The cardinality of the FoD is |Θ| = 5. In the j-th simulation run, a BBA m j (•) is randomly generated according to Algorithm 1 [START_REF] Burger | Random generation of mass functions: A short howto[END_REF] of Table X. The number j of remaining focal elements for all the approaches are set to from 2 to 30 and then the different approximation results mj i (•) can be obtained using different methods, where i denotes the i-th approximation approach. We record the computational time of the original BBA combination of m j (•) ⊕ m j (•) with Dempster's rule and the computational time of using Dempster's rule for each approximated BBA mj i (•) ⊕ mj i (•). The average (over 200 runs) computational time for the original and approximated combination are shown in Fig. 2. The average (over 200 runs) distance between the original BBAs and the approximated BBAs obtained using different approaches given different remaining focal elements' number are shown in Fig. 3.

As we can see in Fig. 2, all the BBA approximation approaches permit to reduce the computational time with respect to the original computational time due to the removal of focal elements. Besides, from Fig. 3 we observe that, the approximated BBAs using our new proposed approach are globally closer to the original one when compared with other approaches, which represents the least loss of information. Note that when the number of remaining focal elements is small, there are no data points for the curve of klx and rank-level fusion methods because they can not remove a certain number of focal elements like other methods due to the constraint that the removed masses are no greater than x = 0.2.

B. MoP of Decision-making

In this work we use the DSmP Transformation [START_REF] Smarandache | Advances and applications of dsmt for information fusion-collected worksvolume 3[END_REF] to make the final decision by selecting the θ i with the maxi- mum DSmP (θ i ) value. The DSmP (θ i ) probability of any elements θ i , i = 1, 2, ..., |Θ| of the FoD Θ can be obtained by

DSmP (θ i ) =m(θ i )+ [m(θ i ) + ] X∈2 Θ X⊃θi |X|≥2 m(X) Y ∈2 Θ X⊃Y |Y |=1 m(Y ) + • |X| (19)
where ≥ 0 is a tuning parameter.

In our simulations, all the approximation approaches are compared from the aspect of the accuracy of decision-making. The cardinality of the FoD is |Θ| = 5 and the parameter has been set to 0.001. Firstly, 1000 BBAs are randomly generated according to Algorithm 1 [START_REF] Burger | Random generation of mass functions: A short howto[END_REF] of Table X. Then, use the DSmP Transformation to make the final decision for the original BBAs. After that, 1000 approximated BBAs are generated and 1000 decisions are made for each approximation method. Finally, the accuracy of decision-making is counted for each method and the results with different number of remaining focal elements are shown in Fig. 4.

As we can see in Fig. 4, although ICP method is not the best, it presents a stable and good performance, especially when the number of remaining focal elements is small, which represents the less loss of information from our standpoint. It should be noted that there are no data points for the curve of klx and rank-level fusion methods due to the constraint mentioned before, when the number of remaining focal elements is small.

VI. CONCLUSION

With the increase of cardinality of the FoD, evidence combination exhibits a large computational cost. In this paper, a novel BBA approximation approach based on focal element compatibility is proposed based on a new mass assignment strategy. This new method offers a good balance between the computational time and the loss of information. Simulations and comparative analyses show the interest and efficiency of our new method. In future, we will consider other BBA approximation approaches based on the removal of focal elements to solve the bottleneck of BBA combination for different rules of combination.

APPENDIX

The proof that m(•) which is obtained by the new mass assignment strategy is a true normalized BBA is as follows.

Proof: 1) m(∅) = 0.

2) δ ∩ (A i , A r ) > 0 for any focal element A i = ∅.

δ ∩ (A i , A r ) =m(A i )|A i | + m(A r )|A r | -[m(A i ) + m(A r )]|A i ∩ A r | ≥m(A i )|A i | + m(A r )|A r | -[m(A i ) + m(A r )]min {|A i |, |A r |} Suppose that min {|A i |, |A r |} = |A r |. δ ∩ (A i , A r ) ≥m(A i )|A i | + m(A r )|A r | -[m(A i ) + m(A r )]|A r | =m(A i )(|A i | -|A r |) > 0 3) l-1 i=1 m(A i ) = 1. l-1 i=1 m(A i ) = l-1 i=1 m(A i ) + m(A r ) D • δ ∩ (A i , A r ) = l-1 i=1 m(A i ) + m(A r ) D l-1 i=1 1 δ ∩ (A i , A r ) = l-1 i=1 m(A i ) + m(A r ) D D = l-1 i=1 m(A i ) + m(A r ) = 1

Example 1 :

 1 Consider the BBA m(•) defined over the FoD Θ = {θ 1 , θ 2 , θ 3 }. The mass assignments of focal elements A 1 = {θ 1 }, A 2 = {θ 2 }, A 3 = {θ 2 , θ 3 } and A 4 = {θ 1 , θ 2 , θ 3 } are as follows.

θ 3 }

 3 should be removed at first when approximating the original BBA m(•).B. New Mass Assignment StrategyHere, we propose a new mass assignment strategy based on distance of focal elements. Let m(•) denote the original BBA with l focal elements and m(•) denote the remaining BBA after removing the focal element A r , where A i , i = 1, 2, ..., l -1 are the focal elements of m(•). Then m(•) is obtained by

Step 1 :

 1 Calculate ICP (A i ) for each remaining focal element; • Step 2: Sort all the focal elements in descending order according to their incompatibility degree to obtain the sorted list of focal elements; • Step 3: Remove the last focal element A r of the sorted list of focal elements, and redistribute its mass value to the mass of focal elements upper it in the sorted list to generate an approximated BBA m according to our new mass assignment strategy. Reduce the number of focal elements by one, i.e., l ← l -1; • Step 4: Assign m = m. If the number of removed focal elements is not reached, go to Step 1, otherwise output m as the final approximated BBA. The whole procedure is illustrated in Fig.1.

Example 2 :mFig. 1 .

 21 Fig. 1. Scheme of the new BBA approximation.

Fig. 3 .

 3 Fig. 3. Closeness comparisons.

Fig. 4 .

 4 Fig. 4. Accuracy of decision-making comparisons.

TABLE

  θ 5 } and A 6 = {θ 2 , θ 4 , θ 5 } are removed and their union set {θ 2 , θ 3 , θ 4 , θ 5 } is generated as a new focal element (existed already) with mass value m(A 2 ) + m(A 7 ) + m(A 6 ) = 0.28. The approximated BBA mSum (•) is listed in TableIII.

TABLE V

 V mRank (•) OBTAINED USING RANK-LEVEL FUSION.

  2, ..., 7 and sort all the focal elements in descending order according to ICP (A i ) value. The result of the first iteration is listed in Table VIII. Because ICP (A 2 ) is the smallest and the focal element A 2 = {θ 2 , θ 3 , θ 4 , θ 5 } is removed at first, then we redistribute the mass of A 2 to remaining focal elements to proceed the next iteration. • The second iteration: We recalculate ICP (A i ), i = 1, 3, 4, 5, 6, 7 and sort all the remaining focal elements. The result of the second iteration is listed in Table VIII. Because ICP (A 7 ) is the smallest value, the focal element A 7 = {θ 2 , θ 5 } is removed at this iteration. Now the number of remaining focal elements is five and we redistribute the mass of A 7 to remaining focal elements to obtain the final approximated BBA mICP (•) listed in Table IX.

TABLE VIII THE

 VIII RESULTS OF TWO ITERATIONS USING ICP.

		The First Iteration
	Focal Elements	Mass Values	|M

  n-1 is the normalization factor. BI 1 (A i ) and BI 2 (A i ) are belief intervals of A i for m 1 (•) and m 2 (•), which are denoted by [Bel 1 (A i ), P l 1 (A i )] and [Bel 2 (A i ), P l 2 (A i )].

TABLE X ALGORITHM 1 :

 X1 RANDOM GENERATION OF BBA. Generate an integer between 1 and Nmax → l; FOReach First k elements of R(Θ) do Generate a value within [0, 1] → m i , i = 1, 2, ..., l; END Normalize the vector m = [m 1 , m 2 , ..., m l ] → m ;

	Input: Θ: Frame of Discernment;
	Nmax: Maximum number of focal elements
	Output: m(•): BBA
	Generate P(Θ), which is the power set of Θ;
	Generate a random permutation of P(Θ) → R(Θ);

ACKNOWLEDGMENT This work was supported in part by the National Natural Science Foundation of China under Grant 61573097 and 91748106, in part by Key Laboratory of Integrated Automation of Process Industry (PAL-N201704), the Fundamental Research Funds for the Central Universities (3208008401), the Qing Lan Project and Six Major Top-talent Plan, and in part by the Priority Academic Program Development of Jiangsu Higher Education Institutions.