Basic belief assignment approximations using degree of non-redundancy for focal element

Yi YANG, Deqing HAN, Jen DEZERT

a SKLSVMS, School of Aerospace, Xi’an Jiaotong University, Xi’an 710049, China

b Center for Information Engineering Science Research, Xi’an Jiaotong University, Xi’an 710049, China

c ONERA, The French Aerospace Lab, Chemin de la Hunie`re, Palaiseau F-91761, France

KEYWORDS

Abstract Dempster-Shafer evidence theory,also called the theory of belief function,is widely used for uncertainty modeling and reasoning.However,when the size and number of focal elements are large, the evidence combination will bring a high computational complexity. To address this issue,various methods have been proposed including the implementation of more efficient combination rules and the simplifications or approximations of Basic Belief Assignments (BBAs). In this paper,a novel principle for approximating a BBA into a simpler one is proposed, which is based on the degree of non-redundancy for focal elements. More non-redundant focal elements are kept in the approximation while more redundant focal elements in the original BBA are removed first. Three types of degree of non-redundancy are defined based on three different definitions of focal element distance,respectively.Two different implementations of this principle for BBA approximations are proposed including a batch and an iterative type.Examples, experiments,comparisons and related analyses are provided to validate proposed approximation approaches.

1. Introduction

Dempster-Shafer Theory (DST),1which is also called the theory of belief function, has been widely used in many uncertainty modeling and reasoning related application fields including information fusion,2pattern classification3and Multiple Attributes Decision Making (MADM).4However,DST was criticized because of its limitations.5One limitation is its computational complexity6in evidence combination,which is influenced by the cardinality of the frame of discernment and the number of focal elements in BBAs to combine.The high computational cost brings a big challenge to the practical use of belief functions.

To reduce the computational cost encountered in evidence combination, many approaches were proposed, which can be in general categorized into the following types. The first type is to design efficient combination algorithms. The representatives of this type include Kennes’ method,7Barnett’s approach,8and Shafer and Logan’s implementation for hierarchical evidence.9The second type is to simplify the original Basic Belief Assignment(BBA),i.e.,to obtain a corresponding approximated BBA.Two major types can be found in the prevailing BBA approximations:(A)To use a BBA with a simpler and special structure to approximate the original one. For example, one can use the Bayesian BBA10and the consonant approximation of a BBA11; (B) To limit the quantity or size of focal elements by removing some focal elements by following some criteria (focal elements’ size or mass value, or both).Tessem’s k-l-x method,12Lowrance et al’s summarization approach,13Bauer’s D1 approximation,14Den?ux’ inner and outer approximations,15Monte-Carlo approximation,16etc.are representatives. They remove focal elements and redistribute the corresponding mass assignment values. In our previous works in recent years, a hierarchical proportional redistribution approach,17rank-level based BBA approximation,18and optimization based approximations19were proposed. Shou et al proposed a BBA approximation based on the correlation coefficient.20

The work in current paper focuses on reducing the computational cost of evidence combination with BBA approximations. As aforementioned, one can limit the number of focal elements according to some criteria. Intuitively, the rational criterion should relate to the importance or non-redundancy of the focal elements. A focal element with more ‘‘common”or ‘‘shared information” with other focal elements is more redundant and should be removed first if possible. However,the available criterion is either the focal element’s size(i.e.,cardinality) or its mass assignment, which has no direct and logical relation with the focal elements’ importance or the nonredundancy. Therefore, criteria related to the focal elements’non-redundancy are required for proposing more reliable and efficient BBA approximation approaches.This is the motivation of our work in this paper.

We use the average distance between a given focal element and all other focal elements to define the non-redundancy.Smaller average distance means that the given focal element carries more similar information compared with the others,i.e., it is less non-redundant and should be removed earlier.Different definitions of the distance between focal elements are used in this paper to define different non-redundancies of focal elements. Two strategies of removal (including a batch and an iterative mode) are proposed in the sequel, followed by the re-normalization or redistribution.Numerical examples,simulations and related analyses are provided to show the rationality and interest of the novel BBA approximation approaches.

This paper extends our previous ideas briefly introduced in Ref.21,where the non-redundancy for focal elements was preliminarily proposed. Comparatively, more definitions for distance of focal element are used to define the non-redundancy of focal elements and different distance definitions are analyzed and compared in this extended version. We also provide more experiments and analyses to provide a precise evaluation of these new approximation methods.These are all added values. The rest of the paper is organized as follows. Section 2 provides the essentials of DST. Some limitations, especially the computational cost, are pointed out. A brief review of the available works on BBA approximations is provided in Section 3.Section 3 then proposes the non-redundancy of focal elements based on three different types of distance of focal elements.Numerical examples are provided to illustrate and compare different definitions of non-redundancy. Simulations and related analyses are provided in Section 4 to verify and evaluate our proposed non-redundancy of focal elements and their performance in BBA approximations. Comparisons between the new proposed approaches and some typical existing ones are also provided. Section 5 concludes this paper.

2. Preliminaries of BBA approximation

2.1. Basics of Dempster-Shafer evidence theory

In Dempster Shafer evidence theory,1those elements in the Frame of Discernment (FOD) Θ are mutually exclusive and exhaustive. A basic belief assignment (BBA, also called mass function) on a FOD is defined by a mapping m（·）:2Θ?［0,1］satisfying m（?）=0 and

If m（A）＞0, A is a focal element. Two Bodies of Evidence(BOEs) can be combined using Dempster’s rule as

To reduce the high computational cost caused by the evidence combination,one can try to design simpler combination rules,attempt to develop efficient implementations for prevailing rules,or try to simplify(approximate)the original BBA by a simpler one with less focal elements. In this paper, we focus on the BBA approximation,which is deemed more intuitive for human beings to catch the meaning.24

2.2. Brief review of available BBA approximation approaches

An approximation f（·）of BBA aims to find a simpler BBA mSto represent the original BBA m,i.e.,mS=f（m）.The available approaches can be categorized into the following two types:using the BBA with a special structure and reducing the number of focal elements.

2.2.1. Using BBA with special structure

(1) Bayesian BBA approximation

A Bayesian BBA approximation outputs a Bayesian BBA with a special structure where all focal elements are singletons.The most representative Bayesian approximation of a BBA is the pignistic probability transformation proposed by Smets6and Kennes.7Voorbraak10uses the normalization of the plausibility for singletons to approximate the original BBA.Sudano25-27proposed a series of Bayesian approximations based on the proportion between plausibilities or beliefs including the batch mode and the iterative mode. Cuzzolin28proposed an intersection approximation for BBA using the proportional repartition of the total non-specific mass assignment for each contribution of the non-specific mass assignments involved. Smarandache and Dezert23proposed a Bayesian BBA approximation in the framework of Dezert-Smarandache Theory (DSmT), i.e., the Dezert-Smarandache Probability transformation(DSmP),which can also be applied in DST model. In our previous work,29a hierarchical DSmP was proposed. More analyses, comparisons and evaluations on these Bayesian approximations can be found in Ref.30.

Note that the Bayesian approximation is usually used for the probabilistic decision but not reducing the computational cost in evidence combination,since any Bayesian BBA approximation makes too lossy approximations.

(2) Consonant approximations

Here the special structure for an approximated BBA is assumed to be consonant support, i.e., the available focal elements are nested in order.The representative works of the consonant approximation include Refs.11,31.

2.2.2. Removing focal elements according to some criteria

(1) Limiting the maximum allowed cardinality of remaining focal elements

In k-additive approximations,32the maximum cardinality of available focal elements is no greater than a predefined size k. In Ref.32, the mass assignments of focal elements with cardinality larger than k are redistributed to those with cardinality no larger than k. Such a redistribution mass assignments is done according to the proportions designed based on the average cardinality. In our previous work,19such a redistribution of mass assignments is implemented via an optimization approach.In our another previous work,17a BBA approximation with the hierarchical redistribution was proposed. These methods aim to remove the focal elements with larger cardinalities since they bring more computational cost in the combination in general.

(2) Limiting the maximum allowed number of remaining focal elements

In this type of approaches, the number of focal elements is reduced by removing some focal elements according to some criteria until the predefined quantity of remaining focal elements is reached.

(A) k-l-x method12

A simplified BBA is obtained according to rules:one should keep no less than k focal elements; one should keep no more than l focal elements; one should delete the masses being no greater than x.

In the k-l-x method, all focal elements in the original BBA are sorted in a descending order based on their mass assignment values. Then, choose the first p focal elements such that k ≤p ≤l and the summation of mass values of those first p focal elements is no less than 1-x. The removed mass values are redistributed to remaining focal elements (renormalization).

(B) Summarization method13

Summarization method is similar to the classical k-l-x,where focal elements with the highest mass values are kept.The removed mass values are accumulated and assigned to the union set of corresponding focal elements. Suppose that k is the number of focal elements in the desired simplified BBA mS·（）of an original BBA m ·（）.Let M denotes the collection(or set)of k-1 focal elements with the highest mass values.One can obtain the simplified BBA according to

(C) D1 method14

Let m(·) be the original BBA and mS（·） denote the simplified BBA. The desired number of remaining focal elements is k. Let M denote the set including k-1 focal elements with the highest mass assignment values in m(·), and M-be the set including all the other focal elements of m(·). D1 method aims to keep all the members of M and to assign the mass values of those focal elements in set M-among the focal elements in M. The set re-assignment is implemented as follows.

For A ∈M-,find all the supersets of A in M to form the set MA. If MA≠?, m（A） will be uniformly re-assigned among those focal elements with smallest size in MA. When

More details on D1 method with examples can be found in Ref.14.

(D)Joint use of cardinality and mass assignment with ranklevel fusion

In our previous work,18we jointly use the cardinality and the mass values of focal element to design a rank-level fusion based BBA approximation approach, which is briefly recalled below.

Step 1.Sort all the focal elements of an original BBA(with L focal elements) in an ascending order according to the mass assignment values (an underlying assumption: the focal element with small mass should be deleted first).The rank vector can be obtained as

Here rm(i) is the rank position of the ith focal element(i=1, 2, ..., L) in the original BBA based on mass values.

Step 2. Sort all focal elements of the original BBA in a descending order according to the cardinalities (an underlying assumption: the focal element with big cardinality should be deleted first). The rank vector can be obtained as

Here rc(i) denotes the rank position of the ith focal elements in the original BBA based on the focal element size.

Step 3. By using the rank-level fusion (weighted average),one can obtain a fused rank vector as

where rf（i）=αrm（i）+（1-α）rc（i） and α ∈［0,1］ denotes the preference of two different criteria. Such a fused rank can be considered as a relatively comprehensive criterion reflecting both the information of mass values and cardinality.

Step 4. Sort rfin an ascending order and find out the focal element with the smallest rfvalue, i.e., rf(j)=min rf(i). Then remove the jth focal element in the original BBA.

Step 5.Repeat Steps 1-4 until k focal elements are left.Renormalize the remaining k focal elements, and output the approximated BBA in the final.

Step 6. Correlation coefficient based BBA approximation(CR-based approximation)

The correlation coefficient is defined as

where

is used for BBA approximation. Suppose that original BBA has L focal elements, and the quantity of desired remaining focal elements is k.

iii) Reassign the mass values of removed focal elements to the remaining focal elements according to the redistribution strategy based on singleton relation proposed in Ref.20. Then, one obtain the approximated BBA.

Besides the above BBA approximations with a preset quantity of remaining focal elements, Den?ux’s BBA approximations by the outer and inner approximations15using distance between focal elements also preset such a quantity in the approximations. See Ref.15for details.

Note that the Monte-Carlo based BBA approximation can also be classified into the approximation approaches using the strategy of removing focal elements. See Ref.16for details.

In this paper, we focus on the BBA approximations through presetting the quantity of remaining focal elements.As aforementioned, existing BBA approximations of this type proposed to remove some focal elements that have smaller mass assignment values,larger cardinalities,or both.Although they have some rational justifications,it is quite dangerous(or risky)to remove those focal elements with small mass values or larger sizes.It may also be unconvincing to remove those focal elements with large cardinality justified only by their bringing possible high computational cost to the combination. Therefore, one should be prudent when using a technique of BBA approximation. It is more convincing to remove those ‘‘unimportant” focal elements. The very redundant focal elements can reasonably be considered as ‘‘unimportant” (carry duplicate information) and the relatively non-redundant focal elements can reasonably be deemed as important; therefore, we propose to define the degree of non-redundancy for a focal element at first.From this degree of non-redundancy,we can then develop new BBA approximation methods by removing focal elements according to the degree of non-redundancy,and intuitively,the loss of information in terms of distance of evidence might be smaller.

3. BBA approximations based on non-redundancy of focal elements

In this section, we define the degree of non-redundancy for focal elements based on the distance of focal elements first.Then, we design BBA approximations based on the degree of non-redundancy.

3.1. Non-redundancy of focal elements

Suppose that a BBA m（·） has l ＞2 focal elements. If a focal element Aihas the largest average distance with other focal elements Aj?Θ j≠i（ ）,then Aishares the least common information with other focal elements in the BBA m（·）,i.e.,Aiis the most non-redundant one.Therefore,one can define the degree of non-redundancy using the average focal distance between a focal element and the others.Suppose that dF（Ai,Aj）is the distance between two focal elements Aiand Aj.First,we can compute the distance matrix for all focal elements in BBA m（·） as

Since dFis a distance,at least there should exist dF（Ai,Ai）=0 and dF（Ai,Aj）=dF（Aj,Ai） where i=1,2,..., l. That is, the matrix MatFEis symmetric. Therefore, it is not necessary to compute all elements in MatFE.

For focal element Ai, we can then define its degree of nonredundancy as

When nRd(Ai) is larger, Aihas a larger non-redundancy (less redundancy);when nRd(Ai)takes a smaller value,Aihas a less non-redundancy (larger redundancy). Then, the problem is how to describe the distance between focal elements. To be more strictly, the ‘‘distance” used here should be ‘‘dissimilarity”, since the distance metric should satisfy all the four requirements including non-degeneracy, symmetry, nonnegativity,and the triangular inequality.When there is no confusion raised, we still use the distance in the sequel.

3.2. Distance between focal elements

In general,the distance between two focal elements should use the two aspects of information in focal elements including the mass assignment and focal element (set) as

The available distances between focal elements are introduced below.

(1) Erkmen’s distance.

This definition is far from robustness and can bring counterintuitive results as shown in the following cases.

(2) Den?ux’s union distance.

Den?ux15proposed a union-operation based distance as

(3) Den?ux’s intersection distance.

Den?ux15also proposed an intersection-operation based distance as

Actually, both δ∪and δ∩can be considered as a weighted sum of the Hamming distance.15It is not difficult to verify that both δ∪and δ∩have no counter-intuitive results for aforementioned Cases I and II.Therefore,we choose δ∪and δ∩to define the degrees of non-redundancy for the focal element. Here we give further analyses on the two distance definitions δ∪and δ∩.

3.3. Analyses on δ∪and δ∩

3.3.1. Focal elements’ relation: A1?A2

In such a case, for δ∩, one gets

As shown in Eq. (17), if m A1（ ） is fixed, δ∩becomes larger with the enlargement of the difference between focal elements’cardinalities|A2|-|A1|. This makes sense. If the difference of cardinalities i.e., |A2|-|A1| is fixed, δ∩becomes smaller with the increase of mass assignment of A1(which is contained byA2).

For δ∪, one gets

As shown in Eq. (18), if m(A1) is fixed, δ∪becomes larger with the enlargement of the difference between focal elements’cardinalities |A2|-|A1|. This makes sense. If the difference of cardinalities i.e.,|A2|-|A1|is fixed,δ∪becomes lager with the increase of mass assignment ofA1(contained by A2). That is,when A1?A2and |A2|-|A1| are fixed, δ∪is positively correlated to the mass of focal element with smaller cardinality(A1),while δ∩is positively correlated to the mass of focal element with larger cardinality (A2).

The analyses above can be supported by Example 1 below.

Example 1. (Focal elements are nested) Suppose that the FOD is Θ=｛θ1,θ2,...,θ5｝. Four BBAs are defined on Θ and each has two focal elements as listed in Table 1.

For each BBA, the mass value of A1changes from 0.01 to 0.95 with an increase of 0.01 at each step.The values of δ∩and δ∪are shown in Fig.1.As shown in Fig.1,δ∪is positively correlated to the mass of focal element with smaller cardinality(A1) while δ∩is positively correlated to the mass of focal element with larger cardinality (A2). Given a fixed m(A1), with the increase of A1, i.e., the decrease of |A2|-|A1|, both δ∩and δ∪become smaller.

3.3.2. Focal elements’ relation: A1∩A2=?

When A1∩A2≠?, for δ∩, one gets

Table 1 Four BBAs in Example 1.

Fig.1 Two distances in Example 1.

For δ∪, one gets

It can be seen that when A1∩A2=?, if |A1| is closer to|A2|, both δ∩and δ∪are smaller (It means that ｛θ1｝ is farther from ｛θ2,θ3｝ than from ｛θ2｝, which makes some sense). This can be shown in Example 2 below.

Example 2. (focal elements have no intersect) Suppose that the FOD is Θ=｛θ1,θ2,...,θ5｝.Three BBAs are defined on Θ,and each has two focal elements as listed in Table 2.

In each BBA, the two focal elements have an empty intersection. For each BBA, the mass assignment of A1changes from 0.01 to 0.95 with an increase of 0.01 at each step.The values of δ∩and δ∪are shown in Fig.2.

As shown in Fig.2,when|A1|=|A2|and A1| |is fixed,both δ∩and δ∪remain unchanged. Given a fixed m（A1）, when the difference |A2|-|A1| becomes larger, both δ∩and δ∪become larger.When the|A2|-|A1|is fixed,δ∪is positively correlated to the mass of focal element with smaller cardinality (A1),while δ∩is positively correlated to the mass of the focal element with larger cardinality (A2), i.e., negatively correlated to the mass of the focal element with smaller cardinality.

Fig.2 Two distances in Example 2.

3.3.3. Focal elements’ relation: A1∩A2≠?

Here A1∩A2≠?. Furthermore, A1cannot be contained by A2,and A2cannot be contained by A1.We provide an example to show δ∩and δ∪’s behaviors in this situation.

Example 3.(focal elements intersect)Suppose that the FOD is Θ=｛θ1,θ2,...,θ6｝. Four BBAs are defined on Θ and each has two focal elements as listed in Table 3.

For each BBA, the mass assignment of A1changes from 0.01 to 0.95 with an increase of 0.01 at each step. The values of δ∩and δ∪are shown in Fig.3.

As we see in Fig.3, when |A1|=|A2|, δ∩and δ∪=1, and they remain unchanged. This is because when|A1|=|A2|=2, one has δ∪（A1,A2）=|A1∪A2|-|A2| and δ∩（A1,A2）=|A2|-|A1∩A2|. So, δ∩and δ∪=1.

Given a fixed m（A1）, when the difference |A2|-|A1|becomes larger, both δ∩and δ∪become larger as shown in Fig.3. This makes sense, because the uncommon part of A1and A2becomes large.When the difference|A2|-|A1|is fixed,δ∪is positively correlated to the mass of focal element with A1having a smaller cardinality,while δ∩is positively correlated to the mass of the focal element A2having a larger cardinality,i.e.,negatively correlated to the mass of the focal element with smaller cardinality.

3.4. Implementation of BBA approximation using degree of redundancy for focal elements

Based on the degree of non-redundancy in Eq. (12),new BBA approximation methods are proposed in this paper, where themore non-redundant focal elements are kept and the more redundant ones will be removed earlier.

Table 2 Four BBAs in Example 2.

Table 3 Four BBAs in Example 3.

Fig.3 Two distances in Example 3.

3.4.1. Batch-mode approximation method

Given an original BBA m(·) with l focal elements, in the approximation, we want to keep k ＜l focal elements. The batch-mode means that the focal elements quantity is reduced from l to k in one run as follows.

Step 1. Compute the matrix MatFEfirst, and then for each Ai（i=1,2,...,l）, compute its non-redundancy value nRd(Ai).

Step 2. Sort all nRd(Ai) （i=1,2,...,l ） in a descending order.

Step 3.Remove the focal elements with ranking positions of bottom l-k.

3.4.2. Iterative-mode approximation method

Here, we propose to remove iteratively the most redundant focal element (with the least nRd value) in each step until k focal elements are kept. This method consists of the following steps:

Step 1. Compute the matrix MatFEand the nRd vaues for each focal elementAi（i=1,2,...,l）.

Step 2. Sort all nRd(Ai) （i=1,2,...,l ） in a descending order.

Step 3. Remove the bottom focal element Ar.

Step 4. If the quantity of the kept focal elements is larger than k, re-compute nRd(Ai) of the kept focal elements where i≠r and go back to Step 3. Otherwise, switch to Step 5.

In the iterative-mode, the matrix and degrees of nonredundancy are re-computed in each step after removing a focal element in the precedent step. That is to say, only the non-redundancy values of the current remaining focal elements are involved in each step.

3.5. Illustrative examples

Illustrative examples for presenting the procedure of our proposed non-redundancy degree based BBA approximation approaches are provided here. The specific calculation steps of other major BBA approximation approaches with presetting the number of focal elements are also provided here for comparisons.

Example 4 Let us consider a BBA m(·) defined on Θ=｛θ1,θ2,...,θ5｝ as listed in Table 4.

(1) Using k-l-x12

(2) Using summarization13

(3) Using D114

(4) Using Den?ux’ inner and outer approximations15

As one sees in Table 8,the empty set is generated as a focal element, which is not allowed in the classical DST under the closed-world assumption.

Table 4 Focal elements and mass assignments.

Table 5 using k-l-x for Example 4.

Table 5 using k-l-x for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.5556 A2 =｛θ1,θ3,θ4｝ 0.3333 A3 =｛θ3｝ 0.1111

Table 6 using summarization for Example 4.

Table 6 using summarization for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.50 A2 =｛θ1,θ3,θ4｝ 0.30 A3 =｛θ3,θ4,θ5｝ 0.20

Table 7 using D1 for Example 4.

Table 7 using D1 for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.500 A2 =｛θ1,θ3,θ4｝ 0.475 A3 =Θ 0.025

Table 8 using Inner approximation for Example 4.

Table 8 using Inner approximation for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.5 A2 =｛θ1,θ3,θ4｝ 0.3 A3 =? 0.2

(5) Using rank-level fusion based method18

The rank of focal elements in m(·) according to the mass assignments is [1,2,3,4,4] (in a descending order). Here[1,2,3,4,4] means that A1takes the 1st place; A2take the 2nd place; A3takes the 3rd place; and A4and A5both take the 4th place due to their equal mass values.

(6) Using CR-based approximation

Using the CR-based approximation, the correlation coefficient values are

Table 9 using outer approximation for Example 4.

Table 9 using outer approximation for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.50 A2 =｛θ1,θ3,θ4｝ 0.45 A3 =｛θ4,θ5｝ 0.05

Table 10 using rank-level fusion based approximation for Example 4.

Table 10 using rank-level fusion based approximation for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.7692 A2 =｛θ3｝ 0.1538 A3 =｛θ1,θ3,θ4｝ 0.0769

(7) Using the non-redundancy based batch-mode approximation

We want to keep three focal elements,i.e.,k=3.Calculate the distance matrix MatFEas

Using this matrix, the degree of non-redundancy for each focal elements in m(·) are obtained as listed in Table 12.

(8) Using the redundancy-based iterative approximation

Here k=3, and then two focal elements should be removed. In the iterative mode, we only remove one focal element in each step. Therefore, two steps are required in this example.

In Step 1,we obtain the same degrees of non-redundancy as listed in Table 11. Then, A4is removed.

In Step 2, nRd for Ai=（i=1,2,...,5;i≠4） is recalculated according to

The results are

nRd（A1）=1.1000,nRd（A2）=0.7833

nRd（A3）=0.6333,nRd（A5）=0.6500

Table 11 using rank-level fusion based approximation for Example 4.

Table 11 using rank-level fusion based approximation for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.5083 A2 =｛θ3｝ 0.1208 A3 =｛θ1,θ3,θ4｝ 0.3709

Table 12 Non-redundancy for different focal elements.

Table 13 using batch approximation based on redundancy for Example 4.

Table 13 using batch approximation based on redundancy for Example 4.

Focal element Mass value A1 =｛θ1,θ2｝ 0.5882 A2 =｛θ1,θ3,θ4｝ 0.3530 A3 =｛θ4,θ5｝ 0.0588

Example 5 Assume that the FOD is Θ= ｛θ1,θ2,θ3｝. An original BBA is listed in Table 14,and the quantity of remaining focal elements is set to k=3.

Using δ∩, we can obtain the distance matrix:

All focal elements’ degrees of non-redundancy are

nRd（A1）=0.3255,nRd（A2）=0.2718

nRd（A3）=0.2915,nRd（A4）=0.3800,nRd（A5）=0.2493

Using the batch mode method, focal elements A2and A5are removed. The approximated BBA is shown in Table 15.

By using the iterative mode method, the degrees of nonredundancy obtained in Step 1 are

nRdI（A1）=0.3255,nRdI（A2）=0.2718

nRdI（A3）=0.2915,nRdI（A4）=0.3800,nRdI（A5）=0.2493

Then,we first remove the focal element A5since nRd(A5)is the least one. Then recalculate nRd values for remaining focal elementsA1,A2,A3and A4:

nRdII（A1）=0.3785,nRdII（A2）=0.3070

nRdII（A3）=0.2779,nRdII（A4）=0.3959

iterative approximation as shown in Table 16.

Using δ∪, the distance matrix is

The degrees of non-redundancy are

nRdI（A1）=0.3414,nRdI（A2）=0.2705

nRdI（A3）=0.3342,nRdI（A4）=0.3664,nRdI（A5）=0.3105

By using the batch mode method,the focal elements A2and A5are removed. After applying the normalization, we obtain the approximated BBA as shown in Table 17.

Using the iterative mode method, degrees of nonredundancy obtained in Step 1 are

nRdI（A1）=0.3414,nRdI（A2）=0.2705

nRdI（A3）=0.3342,nRdI（A4）=0.3664,nRdI（A5）=0.3105

Table 14 Focal elements and mass values.

Table 15 using batch approximation based on redundancy with δ∩.

Focal element Mass value A1 =｛θ1,θ2｝ 0.5882 A2 =｛θ2｝ 0.3530 A3 =｛θ3｝ 0.0588

Table 16 using batch approximation based on redundancy with δ∩.

Table 16 using batch approximation based on redundancy with δ∩.

Focal element Mass value A1 =｛θ1,θ2｝ 0.2959 A2 =｛θ2,θ3｝ 0.4117 A3 =｛θ3｝ 0.2924

Table 17 mBRdS （·） using batch approximation based on redundancy with δ∪.

Table 18 mIRdS （·） using iterative approximation based on redundancy with δ∪.

The focal element A2is removed first,since it has the smallest nRd value. Then recalculate all nRd values for remaining focal elements A1, A3, A4and A5:

nRdII（A1）=0.3133,nRdII（A2）=0.3682

nRdII（A3）=0.4299,nRdII（A4）=0.3314

As we can see in Example 5, the results of the batch mode and iterative mode approximations are different. In the next section, we provide experiments and simulations to evaluate our proposed BBA approximation approaches and those available ones.

4. Simulations for evaluation

We use the computational cost caused by the evidence combination and the closeness between the approximated BBA and the original one in average to evaluate the performance of approximations. An approximation with less computational cost and larger closeness is desirable.To describe the closeness between BBAs, we use a strict distance of evidence, which is Jousselme’s distance (dJ).34One can also use other types of strict distance in evidence theory e.g.,belief interval based distance of evidence35

Suppose that m1,m2are two BBAs defined on Θ(Θ| |=n).If m1and m2are considered as two vectors denoted bym1and m2, respectively, Jousselme’s distance of evidence is defined as

where Jac is the so-called Jaccard’s weighting matrix whose elements Jij=Jac（Ai,Bj） are defined by

It is a most widely used distance of evidence,and it has been proven to be a strict distance metric.36

In our simulations, the cardinality of the FOD Θ is 4. In each random generation, there are 24-1=15 focal elements in the original BBA. The number of remaining focal elements for all the approaches used here is set to from 14 down to 2.We randomly generate BBA using Algorithm 137in Table 19 below.

The average(over 200 runs)combination time and average(over 200 runs) distance values (dJ) between the original BBA and the approximated BBA’s obtained using different approaches given different remaining focal elements’ numbers are shown in Figs. 4 and 5, respectively. The average (over all runs and all numbers of remaining focal elements) computation time and distance values are shown in Table 20.

Note that the computer for the experiments is with i7-8550CPU, 16 GB LPDDRIII RAM, WINDOWS 10 OS and MATLAB 2013B.

It can be shown from Table 20,Figs.4 and 5 that for all the approximations compared here including our proposed four types of approximations based on degree of redundancy for focal elements, the computational time are significantly reduced when compared with original computation time. At the same time, our focal element redundancy based approxi-mations have smaller distance (less loss of information)according to all the distances of evidence used here.In our four new approximations, the iterative mode with δ∩performs the best.

Table 19 Algorithm 1: Random generation of BBA.

Fig.4 Comparisons between different approximations in terms of computation time.

Table 20 Comparisons between different BBA approximations in terms of combination time and closeness.

Here we also provide the comparisons of computational cost of different approximation approaches themselves. Toobtain the approximation computation time, in each run for different approximation approaches, the average time of approximation with remaining focal elements numbers from 2 to 14 is calculated. Then, each approximation approach’s averaging computation time over 200 runs is listed in Table 21.The computational complexity of each approach listed is also listed in Table 21.

Table 21 Comparison between different BBA approximations in terms of combination complexity.

As shown in Fig.5,the approximated BBA obtained using CR-based method can have smaller distance to the original BBA when the number of remaining focal elements are not so small (from 14 down to 9). However, it is at the price of computational cost. Its computation time is about 102times of other approaches compared.

CR-based method use a way like the traversal when selecting the focal elements to remove. Actually, it is not a real traversal, since it removes the L-k focal elements in a batch,but not one by one. Therefore, when the remaining focal elements number is small, its distance becomes not so small.

Comparatively, according to the experimental results, our proposed approximation approach can achieve smaller distance and at the same time, its time cost is accepted.

Note that with the improvement of the computer’s computing capability,the importance of the mass function approximation will be decreased. However, there still exists some resource-restricted environment or platforms, for example,the embedded system for real time tasks, where the computational resource including the CPU and the RAM are not so adequate and the approximation, which can save computational time, is still important.

On the other hand, the BBA approximation could be considered as a preprocessing of ‘‘data”, which can reduce the computational cost. Even if the computational resource is enough, to further reduce the computational cost is still desirable, especially for those real-time applications.

Note that our current performance evaluation on different approximation approaches is based on the experimental results in terms of the statistical averaging combination computational time, and the distance between the approximated BBA and the original one. This makes sense from the engineering or application viewpoints.To comprehensively evaluate different approximation approaches, theoretical analysis and proof are needed, which is also one of the research focuses in our work in the future.

5. Conclusions

Novel methods for BBA approximations are proposed in this paper, where the most redundant focal elements are removed at first.The degree of non-redundancy is defined based on distance between focal elements.Batch and iterative implementations of the BBA approximations are provided. It is experimentally shown that our new BBA approximations can reduce the computational cost of evidence combination with less loss of information, which is described by the distance of evidence. At the same time, the computation time of approximations in our proposed approaches is acceptable.

In our future work, we will focus on designing more comprehensive and rational distance of focal elements, based on which, the degree of focal elements can be calculated. In fact,the non-redundancy represents a type of ‘‘importance” for focal elements. We will also try to define some new type of‘‘importance”, based on which the removal of focal elements can be done more rationally executed.As shown in this paper,we evaluate the performance of different BBA approximations using the computation time and the distance of evidence. In future work, we will also explore more comprehensive evaluation criteria and theoretical evaluation in mathematics for the BBA approximation approaches. This is crucial for the design of more effective BBA approximations.

When we use some criterion(e.g.,the non-redundancy proposed in this paper)to determine those‘‘unimportant”or‘‘redundant”focal elements, we can combine these focal elements to a new one(with intersection or union operation of these elements) besides removing them. For example, we can combine the most two redundant focal elements to a new focal element by using the operations like intersection,union and other ways to replace the current the removal of redundant focal elements.Furthermore,we can use the method like PCA in the design of BBA approximations for the combination of focal elements to expect a better approximation performance in the future research work.

Acknowledgments

The authors would like to thank the support on this research by the National Natural Science Foundation of China (Nos.61671370, 61573275), Postdoctoral Science Foundation of China (No. 2016M592790), Postdoctoral Science Research Foundation of Shaanxi Province, China (No.2016BSHEDZZ46) and Fundamental Research Funds for the Central Universities, China (No. xjj201066).