# an evidence clustering dsmt approximate reasoning method

Post on 23-Jul-2016

218 views

Embed Size (px)

DESCRIPTION

With the increasing number of focal elements in frame of discernment, computational complexity ofDSmT(Dezert-Smarandache Theory) increases exponentially, which blocks the wide application and development of DSmT. To solve this problem, a new evidence clustering DSmT approximate reasoning method is proposed in this paper based on convex functions analysis. The computational complexity of the method in this paper increases linearly instead of exponentially with the increasing number of focal elements in discernment framework. First, the method clusters the belief masses of focal elements in each evidence. Then, the first step results are obtained by the proposed DSmT approximate convex functions formula.TRANSCRIPT

An Evidence Clustering DSmT Approximate Reasoning

Method Based on Convex Functions Analysis

GUO Qiang1, HE You

1 , GUAN Xin

2 , DENG Li

3, PAN Lina

4, JIAN Tao

1

(1. Research Institute of Information Fusion , Naval Aeronautical and Astronautical University ,Yantai Shandong 264001,China;

2. Electronics and Information Department, Naval Aeronautical And Astronautical University ,Yantai Shandong 264001,China;

3. Department of Armament Science and Technology, Naval Aeronautical and Astronautical University ,Yantai Shandong

264001,China;

4. Department of Basic Science, Naval Aeronautical and Astronautical University ,Yantai Shandong 264001,China)

Corresponding author: GUO Qiang,

Tel numbers: +8615098689289,

E-mail address: gq19860209@163.com.

Abstract

With the increasing number of focal elements in frame of discernment, computational complexity of

DSmT(Dezert-Smarandache Theory) increases exponentially, which blocks the wide application and development of

DSmT. To solve this problem, a new evidence clustering DSmT approximate reasoning method is proposed in this

paper based on convex functions analysis. The computational complexity of the method in this paper increases

linearly instead of exponentially with the increasing number of focal elements in discernment framework. First, the

method clusters the belief masses of focal elements in each evidence. Then, the first step results are obtained by the

proposed DSmT approximate convex functions formula. Finally, the method gets the approximate fusion results by

normalization method. The results of simulation show that the approximate fusion results of the method in this paper

has higher Euclidean similarity with the exact fusion results of DSmT+PCR5, and need less computational

complexity than the existing approximate methods. Especially, in the case of large data and complex fusion

problems, the method in this paper can get highly accurate results and need low computation complexity.

Keywords: Evidence clustering; Approximate reasoning; Information fusion; Convex functions analysis;

Dezert-Smarandache Theory

1. Introduction1

As a novel key technologe with vigorous development, information fusion can integrat multiple-source incomplete

information and reduce uncertainty of information which always has the contradiction and redundancy. Information

fusion can improve rapid correct decision capacity of intelligent systems and has been successfully used in the

military and economy fields, thus great attention has been paid to its development and application by scholars in

recent years1-6

. As information evironment becomes more and more complex, greater demands for efficient fusion of

highly conflict evidence are being placed on information fusion. DSmT is a new effective method for the fusion

problem of uncertain, imprecise and highly conflict evidence, jointly proposed by French scientist Dr. Jean Dezert

and American mathematician Florentin6. DSmT can be considered as an extension of the classical Dempster-Shafer.

*ManuscriptClick here to view linked References

DSmT is able to solve complex static or dynamic fusion problems beyond the limits of the DST framework, specially

when conflicts between sources become large and when the refinement of the frame of the problem under

consideration, denoted , becomes inaccessible because of the vague, relative and imprecise nature of elements of

6-8. Recently, DSmT has been applied to many fields, such as, image processing, Robots Map Reconstruction,

Target Type Tracking, Sonar imagery and Radar targets classification and so on6,9-12

. The bottleneck problem to block

the wide application and development of DSmT is that with the increment of focal element number in frame of

discernment, computational complexity increases exponentially.

In order to solve this problem, many scholars presents approximate reasoning method of evidence combination in

D-S framework13-15

. But these methods almost can not satisfy the small amount of computational complexity and less

loss of information requirements at the same time. Dr. Li Xinde and other scholars proposed a fast approximate

reasoning method in hierarchical DSmT16-18

. However, when processing highly conflict evidence by the method, the

belief assignments of correct main focal elements transfer to the other focal elements, which leads to low Euclidean

similarity of the results in this case.

Aiming at reducing the computational complexity of DSmT and obtaining accurate results in any case, a new

evidence clustering DSmT approximate reasoning method is proposed in this paper. In section 2, information fusion

method of DSmT+PCR5 is introduced briefly. In section 3, Mathematical analysis of DSmc+PCR5 formula is

conducted, which discovers every conflict mass product satisfies the properties of convex function, obtains the

approximate convex function formula of DSmT+PCR5 and analyses approximate convex function formula errors.

Then a new approximate reasoning DSmT method is proposed by analysis of approximate convex function formula

errors in section 4. In section 5, analysis of computation complexity of DSmT+PCR5 and the method in this paper is

carried out. The results of simulation show that the results of the method proposed in this paper have higher

Euclidean similarity with the exact fusion results of DSmT+PCR5, and lower computational complexity than

existing DSmT approximate method18

in section 6.

2. Information fusion method of DSmT+PCR5

Instead of applying a direct transfer of partial conflicts onto partial uncertainties as with DSmH, the idea behind

the Proportional Conflict Redistribution(PCR) rule19

is to transfer (total or partial) conflicting masses to non-empty

sets involved in the conflicts proportionally with respect to the masses assigned to them by sources as follows6:

1. calculation the conjunctive rule of the belief masses of sources;

2. calculation the total or partial conflicting masses;

3. redistribution of the (total or partial) conflicting masses to the non-empty sets involved in the conflicts

proportionally with respect to their masses assigned by the sources.

The way the conflicting mass is redistributed yields actually several versions of PCR rules. PCR5 is the most

mathematically exact redistribution method of conflicting mass. This rule redistributes the partial conflicting mass to

the elements involved in the partial conflict, considering the conjunctive normal form of the partial conflict. It does a

better redistribution of the conflicting mass than Dempsters rule since PCR5 goes backwards on the tracks of the

conjunctive rule and redistributes the conflicting mass only to the sets involved in the conflict and proportionally to

their masses put in the conflict.

The PCR5 formula for the combination of two sources (s = 2) is given by6:

PCR5[ ] 0, \m X G X

2 2

1 2 2 1PCR5 12

\ 1 2 2 1

( ) ( ) ( ) ( )[ ] ( ) [ ]

( ) ( ) ( ) ( )Y G XX Y

m X m Y m X m Ym X m X

m X m Y m X m Y

(1)

where all sets involved in formulas are in canonical form and where G corresponds to classical power set 2 if

Shafers model is used, or to a constrained hyper-power set D if any other hybrid DSm model is used instead,or to

the super-power set S if the minimal refinement ref of is used; 12 ( ) ( )m X m X corresponds to the

conjunctive consensus on X between the 2S sources and where all denominators are different from zero. If a

denominator is zero, that fraction is discarded.

3. Mathematical analysis of DSmc+PCR5 formula

As shown in formula (1), 2 2

1 2 2 1

\ 1 2 2 1

( ) ( ) ( ) ( )[ ]

( ) ( ) ( ) ( )Y G XX Y

m X m Y m X m Y

m X m Y m X m Y

has symmetry.

Due to the symmetry, analyse one item2

1 2

1 2

( ) ( )

( ) ( )

m X m Y

m X m Y.

Let 1 2( ) , ( )m X a m Y b ,

get 2 2

21 2

1 2

( ) ( ) 1[1 ( )]

( ) ( )

m X m Y a ba a

m X m Y a b a b

, then

2

21 21 2

/ 1 2 1 2

( ) ( ) 1 1 1[ ] [ ( )], , ,

( ) ( )n

Y G X nX Y

m X m Ya n a b b b Y

m X m Y a b a b a b

(2)

Let 1

( )f xa x

, due to ( )f x is continuous function on [0,1], has second order derivatives on (0,1), and ''( ) 0f x on (0,1),

( )f x is a convex function.

So 1 21 21

( ( ) ( ) ( )) ( )nnx x x

f x f x f x fn n

, the equality holds iff 1 2 nx x x .

The approximate convex function formula is given by:

1 2 1 2

1 1 1

( ) /n n

n

a x a x a x a x x x n

(3)

Let 1 2 i nx x x x , carry out analysis of convex function formula errors.

1 1 2

2 1 2 1 2

1 1[ ]

( ) /

1 1 1 1[ ] [ ]

( ) / ( ) /

n

n n n

a x a x x x n

a x a x x x n a x a x x x n

(4)

analysis of the i item in equality(4).

Let 1 2 0( ) /nx x x n x , then 1 2 0

1 1 1 1

( ) /i n ia x a x x x n a x a x

.

By taylor expansion theorem,

2 30

0 0 0 0 0 0

0

''( )1 1 '''( )'( )( ) ( ) ( ) , ( , ) ( , )

2 3!i i i i i

i

f x ff x