An information-based approach to handle various types of uncertainty in fuzzy bodies of evidence

Summary

Fuzzy evidence theory, or fuzzy Dempster-Shafer Theory captures all three types of uncertainty, i.e. fuzziness, non-specificity, and conflict, which are usually contained in a piece of information within one framework. Therefore, it is known as one of the most promising approaches for practical applications. Quantifying the difference between two fuzzy bodies of evidence becomes important when this framework is used in applications. This work is motivated by the fact that while dissimilarity measures have been surveyed in the fields of evidence theory and fuzzy set theory, no comprehensive survey is yet available for fuzzy evidence theory. We proposed a modification to a set of the most discriminative dissimilarity measures (smDDM)-as the minimum set of dissimilarity with the maximal power of discrimination in evidence theory- to handle all types of uncertainty in fuzzy evidence theory. The generalized smDDM (FsmDDM) together with the one previously introduced as fuzzy measures make up a set of measures that is comprehensive enough to collectively address all aspects of information conveyed by the fuzzy bodies of evidence. Experimental results are presented to validate the method and to show the efficiency of the proposed method.

Keywords:

Algorithms – Surveys – Decision making – Entropy – Reasoning – Information theory – Decision theory – Monte Carlo method

1. Introduction

Dempster-Shafer theory (DST) or evidence theory is accepted as a flexible framework to model various processes of quantitative reasoning and decision making under uncertainty [1] [2] [3]. It is widely used in practical applications such as belief function approximation [4] [5], regression analysis [6] [7], sensor reliability evaluation [8] [9], risk analysis [10], sensor fusion [11], pattern classification [12] [13], and evidential clustering [14], where DST framework could handle different types of non-specificity, and conflict during modeling under uncertainty.

In order to effectively manage DST to handle fuzzy information in evidential reasoning, several generalization methods of DST to fuzzy sets have been proposed [15] [16] [17] [18] [19] [20]. Computing a Fuzzy Body of Evidence (FBoE) can quantify different sort of uncertainties, such as imprecision, discord and degree of confidence [21].

In all applications, measuring the difference is embedded in the body of the respective algorithms in one way or another. By choosing a suitable set of dissimilarity measures, the overall performance of the algorithm is improved. In our previous study, [22], we proposed a set measures to handle non-specificity and conflict, and we employed it for two applications. However, the measuring of fuzziness was not included, and it could not use for fuzzy framework. Thus, measuring the difference between the two FBoEs is a challenging task as the dissimilarity measures have a central role in the body of the algorithms.

In fuzzy set theory, Bloch proposed a detailed survey of distances between fuzzy sets, where they were used in image processing applications [23]. Also, de Campos et al. proposed a method to find distances between fuzzy measures based on associated probability distributions [24]. In DST, many works on measuring the distance between belief functions have emerged. In our previous study [22], we proposed a framework for comprehensive assessment of dissimilarity between two BoEs. The outcome was the set of most discriminative dissimilarity measures (smDDM) representing the minimal set of dissimilarity measures needed for an overall evaluation of the differences between two BoEs. Although dissimilarity measures in the field of both evidence theory and fuzzy set theory have been studied separately, no comprehensive survey is yet available for fuzzy evidence theory to handle all types of uncertainties.

Motivated by this fact, we investigate a method to comprehensively address all types of uncertainty. By modifying the set of discriminative dissimilarity measures (smDDM), we follow an information-based approach to propose such a method. To validate the proposed approach, it is tested through experimentation which shows a good agreement with experimental data.

2. Background

Dempster-Shafer Theory (DST) has been applied to quantitative reasoning and decision-making cases under uncertainty. Whereas the fuzzy DST as an extension to DST, is used to manage imprecise and vague information in evidential reasoning. In the following we review the general concepts of the two aforementioned theories and their corresponding basis.

2.1 Dempster-Shafer Theory (DST)

DST, or evidence theory, assigns mass values to the subsets of Frame of Discernment (FoD), instead of its elements. Let Θ be the FoD as a finite discrete set with N hypotheses, Θ = {ω₁, …, ω_N}, a mass function m(.), so called a Basic Probability Assignment (BPA), is defined as:

Given the mass functions of a BPA, a belief function Bel, and a plausibility function, Pl are introduced as [1] [2]:

To aggregate several pieces of evidence, the combination rule plays a crucial role. Combination of the two independent bodies of evidence with their corresponding mass functions m₁(.) and m₂(.) is given by the Dempster’s rule of combination as defined in [1].

However, if the conflict is high [25], a counter-intuitive result may occur during a combination [12]. As the modification, two main approaches have been introduced: conflict redistributing [26], and discounting unreliable approaches [12], where in our previous study, we had a review on the main discounting approaches [9].

2.2 Fuzzy Dempster-Shafer Theory

Since proposal of the concept of fuzzy set by Zadeh [27], the analysis of fuzzy-valued data have rapidly paved a progressive trend due to its importance [28]. To manage imprecise and vague information in evidential reasoning, researchers have tried to generalize the DST in order to deal with fuzzy sets [16] [18] [20] [29]. Fuzzy evidence theory extends DST allowing the assignment of degrees of belief to ambiguous propositions such as those typically expressed in verbal statements which are represented by fuzzy subsets of the FoD.

A fuzzy body of evidence can be defined by the following set:

Combining multiple fuzzy evidence structures can be extended through the Dempster’s rule if the intersection of crisp sets is replaced by the intersection of fuzzy sets. Following this idea, several rules have been proposed by extending the Dempster’s rule to belief structure through various modalities; Ishizuka et al. considered the intersection degree of two fuzzy sets [16], Yen used two operators with a cross-product operation and normalization process [30], and Yang et al. constructed a weighted variable as follows [31]:

3. Information-based dissimilarity assessment in DST

Dissimilarity assessment is a main problem in DST where quantifying the difference between two BoEs has a central role in many practical algorithms. More than 60 dissimilarity measures have been used for DST in different applications. The idea of multi-dimension dissimilarity measures was first proposed by Liu as a one-dimensional measure is inadequate to quantify the conflict between BoEs [32]. With a focus on different formal properties of dissimilarity measures, Jousselme and Maupin reviewed various dissimilarity measures in DST and selected 15 dissimilarity measures. They classified them into four categories that are metric, pseudo-metric, semi-pseudo-metric and non-metric classes [33]. However, they could not introduce one dissimilarity measure as a sole representor of a class, rather the dissimilarity measures belong to each proposed class were found highly correlated. We developed a methodology that selects a set of dissimilarity measures with the most discrimination power [22]. We investigated almost all studied measures, following a proposed criterion, we used a forward selection procedure to obtain a set of measures that were maximally uncorrelated, while keeping the discrimination as high as possible. The Outcome was the set of most Discriminative Dissimilarity Measures (smDDM) as:

These members are classified into two classes: 1) intrinsic class, enlisting the imperfection of information provided by the sources of evidence ({d_G, d_E, d_TC, d_N, d_C}), and 2) extrinsic class, enlisting the conflict/contradiction between BoEs ({d_CS, d_Int, d_T}), where the dissimilarities are measured based on the following criteria [34] [35] [1] [36] [37] [36] [4] [38]:

The results in [22], [5], and [9] showed that the smDDM can be an appropriate and justifiable disagreement measure for various applications. A more efficient description of the difference between two BoEs is obtained when these measures are considered simultaneously. However, they could just handle different types of non-specificity, and conflict (i.e. strife, imprecision, and disparity). In following (Section 4), we extend the smDDM to compare all aspects of information (i.e. fuzziness, non-specificity, and conflict) conveyed by fuzzy bodies of evidence.

4. Motivation of the work

The aim of our approach is to find a set of measures of handling different types of uncertainty between two FBoEs, i.e. fuzziness, non-specificity, and conflict. Although the smDDM can appropriately address non-specificity and conflict, the measuring of fuzziness has not been included in it. Moreover, it cannot be used for fuzzy framework. To tackle these challenges, first, we introduce the measures in the fuzzy evidence framework (Section 4.1), then extend the smDDM to apply for the FBoEs (Section 4.2), and add these extended measures to the previously introduced ones to ultimately find a set that could handle different types of uncertainty. However, there exist some redundant information content among these criteria. To find the most important criteria, a backward elimination procedure is proposed which will be discussed subsequently (Section 4.3).

4.1. Uncertainty measure in the fuzzy evidence framework

For the fuzzy evidence framework, two main measures have been proposed [39]. The first measure is the General Uncertainty Measure (GM) was introduced by Liu [31].

The second one is the Hybrid Entropy (FH), proposed by Zhu and Basir [40]. It is defined as a measure which quantifies the overall uncertainty contained in a fuzzy evidence structure:

The smaller is F(A˜), the less fuzzy is the fuzzy set A˜. In Eq (17) and Eq (18), S(A˜j)—the support of a fuzzy set A˜j- means a crisp set that contains all such points x∈Θ for which μA˜j(x)>0.

These two measures are considered as the extension of the ambiguity measures (i.e. non-specificity and conflict) to fuzzy set. Therefore, they could only handle types of non-specificity and conflict in fuzzy evidence theory.

Moreover, these measures have been studied through a Monte Carlo simulation [39]. The results have previously revealed while GM behaves with more stability, the FH has counter-intuitive behavior in reflecting the changes in the conflict in FBoEs. Although both GM and FH claimed that quantified aggregate uncertainty is an extension of the ambiguity measure (non-specificity and conflict) to fuzzy set, the differentiation of the quantity of the three types of uncertainty, i.e. fuzziness, non-specificity, and discord is not possible.

There are also some criteria which try to measure fuzziness in an FBoE. A brief summary about fuzziness measures of fuzzy sets has been provided in [41]. The fuzziness of an FBoE is estimated as a weighted sum of fuzziness over all different FEs of FBoE as follows:

4.2. Generalizing the smDDM to fuzzy DST (FsmDDM)

To extend the smDDM for an FBoE, the FBoE should be replaced by BoE. A natural way to link a piece of fuzzy evidence with crisp evidence is to represent the fuzzy set by its α-cuts using the resolution identity principle [35], and then distribute A˜j’s mass (m(A˜j)) to its α-cuts. This process can be described as follows:

• Decompose the fuzzy FE to its α-cuts.

  For each α∈[0,1],

  

• Distribute the mass of fuzzy FE to its α-cuts.

  

  which ensures that m(A˜j)=∑km(A˜jαk)

Using smDDM in classical DST, dissimilarity measures can be calculated yielding to have a collection of them for FsmDDM. Taking the average of these measures, a FsmDDM will eventually be obtained which measure all aspects of information between two FBoEs.

4.3. Finding the most important criteria

Up to now, we separately estimated the ambiguity and fuzziness with a given FBoE. We add these extended measures to the previously introduced ones (i.e. GM in Eq (17), and FH in Eq (18)) to find a more riche set of measures. Moreover, the addition of the fuzziness measure (i.e. FM in Eq (19)), results a vector which could better handle different types of uncertainty. However, among these criteria, some may have redundant information content.

To find the most important criteria, a backward elimination procedure is proposed to eliminate the lower significant criterion. The advantage of backward elimination is that it gives the opportunity to look at all criteria before removing the least salient one. Finally, we opt a comprehensive set of criteria.

To apply backward elimination, a sample of possible values used on all criteria should be selected. In the first step, 1000 random FBoEs is generated by adapted algorithm which is proposed in [39] based on Tessem’s idea [4]. ‎Algorithm I summarize the generating procedure.

Algorithm I. Generatinging a random FBoE

Definition

    f: Number of Focal Elements (FEs)

    Θ: Frame of Discernment (FoD)

while f > 0,

    rest = 1

    for i = 1 to f-1 do

        Generate a random number X

        Generate a normal convex fuzzy set A˜i with μA˜i on Θ

    m(A˜i)=P(Y≤X).rest

    rest = rest -m(A˜i)

    end

    Generate a normal convex fuzzy set A˜f with μA˜f on Θ

    m(A˜f)=rest

end while

Then, we assess each FBoE based on all criteria (i.e. FsmDDM, GM, FH, and FM). As a result, a source value is obtained. The backward elimination starts with 4 criteria and removes the criterion with least information in each step as follows:

In each step of backward elimination, the normalized distance between the jth criterion and its orthogonal projection on the kth criterion, since the jth criterion has more independent information content related to other criteria, the scoring criterion increases. In the worst case, the minimum of this scoring criterion for all criteria is taken in J(j).

Fig 1 shows the score of selection in order of removal, where 4 criteria (i.e. FsmDDM, GM, FH, and FM) are considered. After removing FH, and GM, the graph increases. This means that choosing the first two removed criteria does not convey much more information. As a result, the FsmDDM along with the fuzzy measure (i.e. FM) result a vector which could better handle different types of uncertainty.

5. Result and discussion

Due to lack of available experimental data from real application in the literature for the fuzzy DST framework, we evaluate the FsmDDM as well as FH, and GH through a simulation-based analysis. The obtained results for the measures are compared and their accuracy and reliability are being discussed in the following.

5.1. Difference between measures through simple examples

In order to examine the behavior of the dissimilarity measures, we first generate simple numerical examples of FBoEs, which allow us to predict changing of the content of information and to compare the corresponding values obtained by different measures.

Assuming three fuzzy bodies of evidence as follows:

It can be seen that the fuzziness is slightly smaller in FBOE₁ as compared to the other two, but remains the same for the two others. The discord, however, is almost the same for FBOE₁ and FBOE₂ while it dramatically changes from FBOE₂ to FBOE₃. Here are the values of measures for these BoEs.

As observed, the results show that the FsmDDM could be a better measure in reflecting changes in all types of information.

5.2. Difference between measures through average behavior during combination of EBoEs

We use a Monte Carlo simulation, as previously used in similar works [39], in a combination procedure. The process of combining can reflect the uncertainty decrease when the multiple FBoEs are combined sequentially. Fig 2 shows the procedure of combination process and information-based comparison in general.

A random FBoE is generated by adapted algorithm which is proposed in ‎Algorithm I. In our experiment, |Θ| = 16, four fuzzy FEs for each new incoming FBoE are considered. Fig 3 illustrates one FBoE with four normal trapezoidal fuzzy numbers as its FEs, which is randomly generated through Algorithm I.

During the experiment, 20 combinations are assumed. In order to combine the information provided by each piece of evidence in fuzzy DST, we use the Yang et al. combination’ rule as Eq (7). To compute the FsmDDM, the new combined FBoE has to be normalized fuzzy set. Here, we used the normalization method proposed by Yager and Filev [46]. Their method is based on the scaling up. The normalization process is presented in Algorithm II.

Algorithm II. Normalization process

    Definition

    FBoE: {<A˜j,m(A˜j),μA˜j>}j=1:f, T = 1;

    for i = 1 to f do

        vi=maxxμA˜i(x)

        ui=m(A˜i)vi

        T = T−u_i

        ∀x∈Θ,μA˜i(x)=μA˜i(x)vi

    end

    for i = 1 to f do

        m(A˜i)=ui1−T

    end

In each combination step, the difference between combined FBoE with the previous FBoE is measured as follows:

6. Conclusion

Fuzzy evidence theory captures all three types of uncertainty; fuzziness, non-specificity, and conflict, that are usually contained in a piece of information within one framework. Quantifying the difference between two FBoEs plays a central important role when this framework is used in applications.

In this paper, we have proposed a method to compare two FBoEs comprehensively. Although our previously proposed smDDM could be an appropriate approach to handle non-specificity and conflict, the measuring of fuzziness was not included in it. Moreover, the smDDM could not be used for fuzzy framework. In our approach, the smDDM has been extended to apply for FBoEs, then it has been added to the previously introduced ones, in order to find a rich set of measures capable of handling different types of uncertainty. To eliminate the redundant information, a backward elimination process has been employed to find the most important criteria. In the proposed backward selection procedure, a scoring criterion has been designed to gradually remove unimportant DMs. Eventually, a set of most important ones has been selected and its effectively has been discussed in details. Consequently, we have obtained a set of dissimilarity measure which can measure all three types of uncertainty: fuzziness, non-specificity, and conflict.

The ability and stability of the proposed measure through a Monte-Carlo simulation have been investigated extensively. The results show that the trend curves have an excellent acceptable behavior when the FsmDDM is used.