key: cord-1024239-txdznmix
authors: Petry, Fred; Yager, Ronald
title: Evidence approach imprecise intervals: extensions and evaluation measures
date: 2021-02-20
journal: J Ambient Intell Humaniz Comput
DOI: 10.1007/s12652-021-02953-z
sha: e82bbe70ba98a804d893d9aac7ebf646b4d9ab0c
doc_id: 1024239
cord_uid: txdznmix

In a number of applications the data will be represented in an interval format. We consider here a nested representation of uncertain information in intervals using Dempster–Shafer evidence approaches. These representations can be used in variety of applications including spatial and temporal reasoning and economic cost valuations. Two representations of nested intervals, RP1 and RP2, are defined and used in the paper. Basically an inner interval represents the more certain data and is nested in the outer less certain interval. We illustrate how the specificity measure could be used to evaluate such nested Dempster–Shafer intervals. We then consider Gini information measures applicable to the RP1 representation. We describe an example using our interval approach to COVID contact tracing in epidemiology. Finally examples of aggregation of intervals are provided. It is seen that an aggregated result can be evaluated and shown to increase the specificity of the result. Additionally, it is not always the case that aggregation increases specificity. An example is given illustrating such a case.

Uncertainty problems and issues arise in almost all domains of human interests. This was realized commonly by the developments of statistics and probability modeling to managing uncertainty. However some information and data are often represented by human language like "about 50 km", "roughly 39 °C", "approximately 100 lbs.", "young", and "large". There are many other approaches for representing linguistic, subjective uncertainty in particular in the computational intelligence domain (Kruse et al. 2016 ). These can include fuzzy sets and possibility theory (Parsons 2001) , rough sets (Zhang et al. 2016 ) and evidence (Dempster-Shafer) theory (Liu and Yager 2008) .

There are many areas for which subjective interpretation of intervals can use Dempster-Shafer approaches, such as, for example, expert estimates of the ranges for potential prices of real estate property. Also in large commodity trading markets such as in Chicago, issues of the ranges of values of various commodities involve essential uncertainty issues (Varangis and Larson 1996) and can be modeled by these sorts of intervals. Also spatial and temporal data has been represented by such intervals (Elmore et al. 2017a, b) .

In this paper we are treating uncertainty in data representation by nested intervals, I j , corresponding to focal elements in evidence theory. The uncertainty is modeled using evidence theory (Dempster-Shafer theory) (Shafer 1987 ) by basic probability assignment, bp j , associated to each interval. These bp values are typically subjective judgments as to the probability of a variable of interest's value lying in a particular interval.

In the paper's organization, we first provide a background of Dempster-Shafer theory and specificity and information measures. Next there is an overview of the basics of the interval approach and alternative representations. We then show how to use specificity measures and information theory based metrics to assess the uncertainty in the nested intervals (Yager 1983 (Yager , 2018 ). An application in the area of epidemiology for infection contact tracing is described. Finally we describe an approach to aggregation of Dempster-Shafer intervals and use measures to determine if an aggregated interval lowers uncertainty, i.e. is more specific.

Our objective is to continue our investigations of representations and processing of uncertainty in data. We have previously carried out research with fuzzy sets, possibility theory and Dempster-Shafer evidence approaches. In particular we want to explore ways to measure and quantify such uncertainty.

So in this paper our contribution is the development of nested representations of uncertain information in intervals using Dempster-Shafer evidence approaches. Two representations of nested intervals, RP1 and RP2, are defined and used in the paper. Basically an inner interval represents the more certain data and is nested in the outer less certain interval. We illustrate how specificity measures could be used to evaluate such nested Dempster-Shafer intervals. We then consider Gini information measures applicable to the RP1 representation. An application in the area of epidemiology for infection contact tracing is also described. Contact tracing has been used extensively during the Covid pandemic and our nested interval representations can provide consistency for these efforts as the uncertainty is specifically captured. Finally examples of aggregation of intervals are developed. It is seen that an aggregated result can be evaluated and shown to increase the specificity of the result. Additionally, it is not always the case that aggregation increases specificity and this is illustrated as it affects decision-making (Yager and Petry 2016 ).

Dempster-Shafer (D-S) theory is a well-known approach to modeling uncertainty (Liu and Yager 2008) , providing representation of non-specific forms of uncertainty. A Dempster-Shafer belief structure consists of a collection of nonempty crisp subsets of a space X called focal elements: R 1 , …, R q . The mass or basic probability, bp, is used to assign a belief to each element of the power set:

Thus our knowledge of the value of a variable is inexact. For focal set, R i ⊂ X, however, bp(R i ) indicates the bp ∶ 2 X → [0, 1].

probability that the value is in R i . Two important properties of bp are: 1. basic probability of the empty set is zero, and 2. the bps of the remaining elements of the power set sum to 1, Two commonly used measures for a Dempster-Shafer belief structure are measures of belief (best case) and plausibility (worst case). The belief for a specific set S, Bel (S), is the sum of the basic probabilities of all subsets of S:

The plausibility, Pl(S), is the sum of the bps of the sets R i that intersect S:

Our methodology for uncertainty evaluation is to use measures such as the Shannon entropy, the Gini index and specificity as extended to Dempster-Shafer uncertainty (Yager 2018) in order to judge the usefulness of interval-based uncertain information.

The Shannon measure of information, or Shannon entropy S sh (P) is a well-known and widely used measure of information content (Cover and Thomas 2006) . For a probability distribution, P = (p 1 , p 2 , …., p n ), Another measure related to information content is a dispersion measure, the Gini index, G(P). It has been widely used in economics (Giorgi and Gigliarano 2017; Berger and Balay 2019) and for decision trees in machine learning techniques such as random forests (Breiman 2001) . This index can be given by:

G(P) is functionally related to S sh (P) (Yager 1995) . G(P), may be used instead of S sh (P) more conveniently in analysis since it does not involve logarithms as does S sh (P).

For possibility theory, the concept of specificity has a measure that is analogous to probability entropy measures. One approach uses a linear measure that can be viewed as an intuitive measure for a possibility distribution's specificity (Pedrycz and Gomide 1996; Dubois 2006) . Consider possibility distribution Π = π 1 , … π n ). If π m = n Max k = 1 π k , then specificity is formulated as the max value, π m , minus the average of the rest of the possibility distribution (Yager 1992 ), Specificity has also been extended and can be used for Dempster-Shafer evidence theory (Yager 1983 ).

Now we must realize that, in representing uncertainty of information such as spatial or temporal data, we are really interested in an interval representation as opposed to a set representation. Intervals can be used to represent such data ranges, so we provide approaches to the use of data intervals (Moore et al. 2009 ; Kreinovich and Shary 2016) as needed. Interval arithmetic has been used previously for Dempster-Shafer applications (Lee and Zhu 1992; Auer et al., 2010) and was used in our previous approaches for calculations with spatial and temporal relations.

Let X be the space which forms a frame of discernment. Intervals, I, will be represented by the lower and upper bounds, y * , y*:

We have previously considered D-S intervals for both spatial and temporal data. Interval representations are described as a basic approach to represent such uncertainty for data. With spatial data (Elmore et al. 2017a) , basic definitions of imprecise coordinates, points and lines were developed. Dempster Shafer spatial representations can be applied to location recommendations based on users' needs (Kosmides et al. 2016) . Temporal uncertain events were represented by nested intervals (Elmore et al. 2017b ). This allows computation of interesting factors such as durations and time between events.

In this section our general methodology is to consider possible alternative interval structures using Dempster-Shafer uncertainty approaches. In particular an interval I will have a structure in which an inner interval is considered as the more certain data. The outer parts of the interval are then considered as possible but not as certain as the inner interval (Fig. 1) .

The inner interval is denoted as I 1 , and its certainty as bp 1 . The rest of the interval I ( I-I 1 ) is denoted as I 2 and has associated basic probability bp 2 and is called the outer interval.

With this approach, we can treat uncertainty in data representation by nested intervals, using evidence theory as basic probability assignment, bp j , associated to each interval. These bp values are typically subjective judgments as to the probability of a variable of interest's value lying in a particular interval; these intervals correspond to focal elements in evidence theory.

Here we consider two representations for our Dempster-Shafer interval structure. The end points are labeled in Fig. 1 , so the entire interval I is [a, d] . Depending on the application semantics, the inner and outer interval can be treated differently. First we consider the potential interpretation that the inner interval I 1 is strictly considered to be a subset of the outer interval I 2 :

The second the possibility we can allow is that the outer interval I 2 is disjoint from the inner interval I 1 :

Representation 1(RP1) ∶ I 1 = [b, c] and I 2 = [a, d] so I 1 ⊆ I 2 .

Representation 2 (RP2) ∶ I 2 = [a, b) (c, d], so I 2 ∩ I 1 = �. 

In the following section our methodology is to consider approaches to evaluate each alternative representation using specificity and then information theoretic measures (Xiao 2018) . A number of approaches to specificity have developed (Pedrycz and Gomide 1996; Song et al. 2016) including measures of discord and non-specificity. In particular, here, we use (Yager 1983 ) for a belief structure B, Sp B , given by For the nested interval belief structure, we will use the length of an interval to be equivalent to the set cardinality for our discrete domains, |I j | = Length (I j ). Then, we have

In RP1 the total length of the uncertain outer interval, I 2 , is greater than the inner interval I 1 . But for RP2 it is quite possible that |I 2 | ≤ |I 1 |, and we will have to consider all such possibilities.

To be semantically meaningful as a discrete interval, we assume |I 1 |≥ 1, i.e. there is a most certain interval, bp 1 > 0.5. For the outer interval as well |I 2 |≥ 1 except where for the inner interval bp 1 = 1, is totally certain, then bp 2 = 0, i.e. there is no outer possible interval. First for RP1 we have and Note where R = 1, Sp B = (1 + bp 1 ( 1-1))/1|I 1 | = 1/|I 1 |. That is, there is only the one certain interval so the specificity is just dependent on that.

Next we can analyze cases for Sp B as a function of the basic probability using bp 1 + bp 2 = 1.

Case 1: bp 1 → 1. So we have

That is as the inner interval becomes more certain then the specificity depends only on the extent of that interval and not the outer one since bp 2 → 0. As the inner interval

narrows the specificity increases and is 1 when |I 1 | = 1, i.e. we know the exact value. Case 2: The other extreme case is for bp 1 ≈ bp 2 = 1/2. Then So now we must take into account the outer interval as well since it has an almost equal basic probability. For example if the outer interval is twice as large, |I 2 | = 2 * |I 1 |, R = 2, then Then as |I 2 | becomes larger, R → ∞, Sp B → 1/2 (1/|I 1 |).

For representation 2, we must consider the possible relationships between the inner and outer intervals, i.e. R > 1 or R < 1. To illustrate we consider an example for each case a: R = 2 as above (|I 1 | = 1/2|I 2 |), and b: R = 1/2 (|I 1 | = 2| I 2 |). a. Sp B = (1 + bp 1 ( 2-1))/2| I 1 | (1 + bp 1 )/2|I 1 | b. Sp B = (1 + bp 1 ( 1/2-1)/(|I 1 |/2) = 2(1 − 1/2 bp 1 )/|I 1 | (2 − bp 1 )/|I 1 | Now we consider as before the bounding case for bp 1 = 1 a. Sp B = (1 + 1)/2|I 1 |1/|I 1 | b. Sp B = (2 − 1)/|I 1 | /|I 1 | Then for bp 1 = 1/2 a. Sp B = (1 + 1/2)/2|I 1 |3/4|I 1 | b. Sp B = (2 − bp 1 )/|I 1 |3/2|I 1 |

We have used information theory for uncertainty of information in fuzzy and rough databases (Buckles and Petry 1983; Beaubouef et al. 1998 ). Information measures have also been developed for Dempster-Shafer belief structures (Deng et al. 2016; Jiang and Wang 2017;  Jiroušek and Shenoy 2018). In particular Yager (2018) considers the case of a consonant belief structure in which the focal elements form a nested subset structure. Now for RP1 we have a nested subset structure, I 1 ⊆ I 2 and so using the Gini entropy for this belief structure has the following bounds on information value

The Dempster Shafer information model of Klir (2006) , G*, has a formulation that considers the size of the nested intervals. G* lies in the Yager's interval G (Yager 2018) and so we demonstrate how this occurs for our given belief structure with the inner and outer intervals Since I 1 ⊆ I 2, |I 1 ∩ I 1 | = |I 1 ∩ I 2 | = |I 2 ∩ I 1 | = |I 1 | and |I 2 ∩ I 2 | = |I 2 |. So where Now we assess if the range of G* satisfies the interval G = [0, 1 − (bp 1 2 + bp 2 2 )]. First for complete certainty for I 1 , bp 1 = 1, bp 2 = 0 and H = 1 so G* = 0. Next we note H > bp 1 2 + bp 1 2 so 1 − H < 1 − (bp 1 2 + bp 2 2 ). Clearly then G* ⊆ G.

In this section we will show how our D-S intervals approach can be used in the area of epidemiology for contact tracing. Then we will discuss how we use aggregation of these sort of intervals to enhance decision-making.

Now we describe the epidemiology problem involving disease contact tracing and how our intervals can be used for this problem. Epidemiology involves analysis of disease distribution (who, when, and where) and patterns (Porta 2014; Fos et al. 2018) . It is basic to public health, and informs health policy decisions and evidence-based practice by specifying risk factors of diseases and objectives of disease prevention. In particular we consider the uncertainties involved in contact tracing, the process of identifying persons who may have come into contact with a person who is infected. This will involve both spatial and temporal determinations and has been used extensively in disease spread such as the recent SARS and COVID pandemics. For COVID in particular the CDC (Center for Disease Control and Prevention 2020) gives the guidelines

as being within 6 ft of a person who was infectious for a 15 or more total minutes over a 24-h period. It furthermore specifies that it is difficult to precisely define close contact. The basic approach starts with the infected individual who is interviewed to learn about their recent activities, and with whom they may have been in close contact. Depending on the disease and the context of the infection, family members, health care providers, and anyone else who may have knowledge of the case's contacts may also be interviewed (Hellewell et al. 2020) . We can illustrate this with a generalized example of a specification of distance and time when it was not possible to exactly determine the exact distance and the information was even possibly solicited from multiple sources or persons. Obviously it is important to make this decision as carefully as possible. If we commit to no close contact then we may face a false negative and consequently risk further infectious exposures. However a false positive also comes with costs, as by requiring isolation because of exposure, an individual may not be able to work which can be an impact economically.

Here are two examples in which we use normalized distance ranges. Let the max range here be 10 ft past which consideration of exposure is irrelevant. The core exposure range of concern is then half of this so that distances below 5 ft may be of most concern. An example is shown in Fig. 2 .

In the following we consider two sources of information obtained by the contact tracing. We analyse these two cases and compare their specificity.

Case A:

So for case A the total specificity is 0.225. Case B:

Case B gives a total specificity is 0.20 which is less than the contact information specificity in Case A. This can be interpreted to conclude that the first case is more appropriate for making a decision about exposure and isolation. We note that we will be considering in Sect. 5.2 regarding how to aggregate these sort of intervals in order to provide a uniform approach. We believe that representations like those in the two cases above can then provide a consistent approach to contact tracing efforts as the uncertainty is specifically captured. Furthermore such representations can then eventually provide a data set to guide future decisions.

As discussed for contact tracing there may be more than just one specification of the data in the intervals. In this section we discuss how to deal with this using aggregation approaches.

There are many fusion and aggregation techniques for uncertainty that have been developed and studied (Beliakov et al. 2007; Ribeiro et al. 2014; Dubois et al. 2016 ) However while effective decision-making should be able to make use of all the available, relevant information about such combined uncertainty, assessment of the value of an aggregation result is critical. Does the aggregation produce an interesting or valuable result? We have previously developed a number approaches to aggregations of uncertain information-probability and possibility distributions (Petry et al. 2015; Anderson et al. 2016) . To assess the effectiveness of these aggregation results we applied information and specificity measures (Elmore et al. 2020; Petry et al. 2015) . Here, in order to use these measures for nested interval aggregations, we have to consider restricted cases to illustrate that the specificity metric can determine if an aggregation produces a more specific and potentially useful result.

We consider a scenario in which contact tracing has occurred and the information may be from more than one source. Our aggregation approach for these evaluations has two components, first an average of the basic probabilities and then the computation of the aggregate inner interval location.

To be well defined in the aggregation, we only consider the case where one inner interval is contained in the other. Otherwise partial overlapping would entail intersection overlap with the outer intervals, which have different basic probabilities. Our aggregation result then uses the smaller of the inner intervals, as it is most specific in the sense of size.

Next we will illustrate an example in which this sort of aggregation can produce a more specific result such as would be desired for contact tracing.

Case 1: bp1 1 = 0.6; |I1 1 | 4; Sp B = 0.6/4 = 0.15 Case 2: bp2 1 = 0.9;|I2 1 |8; Sp B = 0.9/8 = 0.1125

Now we use our aggregation approach. Since we are considering the case where I1 1 ⊆ I2 1 then |Iagg 1 | = |I1 1 |4. Then taking the average of the basic probabilities we can determine the specificity of the aggregated inner interval structure:

So the specificity of the aggregated inner interval is greater than either Case 1 or Case 2. However we must evaluate the overall specificity of the interval I being evaluated by also computing the specificity of the outer intervals. We will let the size of the overall interval be, |I| 10. Then |I1 2 |6, |I2 2 |2, |Iagg 2 |6. So we have Then the overall specificities for I are:

Thus for this example an aggregation as described can produce a more specific result. This is a desirable outcome, however, this is not true in general. If we have an example case that is already fairly specific then aggregation may not be an improvement and indeed can be worse. Consider in the above example if bp1 1 = 0.9 (so more specific) and bp2 1 = 0.6. Then the aggregation specificity would not change but the specificity of Case1 would be greater This result means that aggregation is not an improvement; based on the specificity measure, case 1 should be used.

We have considered issues related to evaluation of uncertain information as captured by Dempster-Shafer nested intervals. Two representations of nested intervals, RP1 and RP2, were defined and used in the paper. We illustrated how the specificity measure could be used to evaluate such nested Dempster-Shafer intervals.

We then considered Gini information measures applicable to these representations. Finally examples of aggregation bpagg 1 = bp1 1 + bp2 1 ∕2 = (6. + .9) ∕2 = .75 of intervals were provided. It was seen that an aggregated result could be evaluated and shown to increase the specificity of the result. Additionally it is not always the case that aggregation increases specificity, and an example was given illustrating this case.

In our future research we will explore other health care applications for our approaches. In particular in collaboration with colleagues in the public health area (Fos and Petry 1995) , the economic problems of decision making under uncertainty for limited health care resources in underserved populations and developing countries are being explored.

We also will explore new extensions to our interval approaches (Xiao 2020) . In particular Dempster-Shafer theory allows the specific representation of ignorance. As opposed to probability theory the sum of the basic probabilities can be less than one and this difference is considered as the degree of ignorance. Using this can potentially permit greater flexibility in many applications.

Fuzzy Choquet integration of homogenous possibility and probability distributions

A verified MATLAB toolbox for the Dempster-Shafer theory

Information-theoretic measures of uncertainty for rough sets and rough relational databases

Aggregation functions: a guide for practitioners

Confidence intervals of Gini coefficient under unequal probability sampling

Random forests

Information theoretic characterization of fuzzy relational data bases

Centers for disease control and prevention

Elements of information theory

An improved distance-based total uncertainty measure in belief function theory

Possibility theory and statistical reasoning

The basic principles of uncertain information fusion

Geospatial modeling using Dempster-Shafer theory

Dempster-Shafer approach to temporal uncertainty

Evaluation of heterogeneous uncertain information fusion

A decision support system for hospital bed assignment

Managerial epidemiology for health care organizations

The Gini concentration index: a review of the inference literature

Feasibility of controlling COVID-19 outbreaks by isolation of cases and contacts

An uncertainty measure for interval valued evidences

A new definition of entropy of belief functions in the Dempster-Shafer theory

Providing recommendations on location-based social networks

Interval methods for data fitting under uncertainty: a probabilistic treatment

Computational intelligence: a methodological introduction

An interval Dempster-Shafer approach

Classic works of the Dempster-Shafer theory of belief functions: an introduction

Introduction to interval analysis

Qualitative methods for reasoning under uncertainty

An introduction to fuzzy sets: analysis and design

Combining uncertain information of differing modalities

FIF: a fuzzy information fusion algorithm based on multi-criteria decision making

Belief functions and possibility measures. In: Bezdek J (ed) The analysis of fuzzy information

Uncertainty measure for interval-valued belief structures

Dealing with commodity price uncertainty. Policy research working paper 1667, Commodity Policy and Analysis Unit

An improved method for combining conflicting evidences based on the similarity measure and belief function entropy

Generalization of Dempster-Shafer theory: a complex mass function

Entropy and specificity in a mathematical theory of evidence

On the specificity of a possibility distribution

Measures of entropy and fuzziness related to aggregation operators

Interval valued entropies for Dempster Shafer structures

An intelligent quality based approach to fusing multi-source probabilistic information

A survey on rough set theory and its applications

Petry would like to thank the Naval Research Laboratory's Base Program for sponsoring this research.Author contributions FP-developed basic interval approach and wrote paper. RY-contributed to use of specificity and information measures in paper.Funding Petry would like to thank the Naval Research Laboratory's Base Program for sponsoring this research.

The author(s) declare no competing interests.