Ahmed Samet
email: samet@lisic.univ-littoral.fr

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

Ben Sadok
email: sadok.benyahia@fst.rnu.tn

Yahia

Belief function classification with conflict management: application on forest image

Keywords: belief function theory, information fusion, classification, conflict management

Treating imprecise and uncertain data requires an adequate formalism allowing a fit modelization. Several formalisms can be identified such as Bayesian theory, fuzzy set theory and belief function theory. The belief function theory provides an adequate formalism to manipulate those imperfect data. It also allows source fusion thanks to the combination operators that it integrates. The fusion process generates an empty set mass denoted conflict that illustrates the contradiction rate between considered sources. In this work, we tackle the classification of a forest high-resolution remote-sensing image problem. In order to classify this image, we handled imperfect information with the belief function theory. We propose a method for classification based on belief function theory and source fusion. The introduced Redistributing Conflict Classification Approach (RCCA) analyzes the conflict resulting from the fusion and redistributes it to the most pertinent classes. An experimental comparison to well known literature classifiers is provided.

I. INTRODUCTION

The progress known by the image acquisition techniques had an important impact on the precision and the detail in remote-sensing images. This gain in detail in high-resolution images had a negative incidence on the volume of treatment and data complexity. These constraints urged the research community to find solutions to manage the important quantity of information and data. Acquired high-resolution images are crippled with imperfection [START_REF] Samet | Classification of highresolution remote sensing image by adapting the distance belief function estimation model[END_REF]. To handle such type of data, several formalisms exist such that fuzzy [START_REF] Zadeh | Fuzzy sets[END_REF] and belief function theory [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF]. Indeed, the latest theory offers a fit formalism for such type of data and handles multi-source problems thanks to the combination operators that it integrates. Several works have associated the pattern recognition domain to belief function theory [START_REF] Dhiaf | Information sources fusion approach in forest stand classification[END_REF] providing interesting results. In this context, we tackle a problem of high-resolution remote sensing classification of a forest typed images. We benefit from the belief function theory to modelize imperfect sources that exist in the image. In this work, we take on the problem of belief function estimation and we introduce a forest image classification method based on belief distance classifier [START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF]. As shown in [START_REF] Samet | Classification of highresolution remote sensing image by adapting the distance belief function estimation model[END_REF], combining multiple sources could generate a mass assigned to the empty set denoted conflict. The conflict is an alarm about the contradiction existing between sources [START_REF] Smets | The Transferable Belief Model and other Interpretations of Dempster-Shafer's Model[END_REF] but also needs to be managed. In this work, we propose a new method for classification improvement based on conflict redistribution. Indeed, the resulting conflict is treated and redistributed to pertinent classes guided by retrieving weighting factors for the generic framework [START_REF] Lefevre | Belief functions combination and conflict management[END_REF]. The paper is organized as follows. Section II describes the mathematical background of belief function theory for information fusion. It defines various ways to combine opinions. In section III, the proposed approach for tree crown's classification based belief distance classifier is introduced. Section IV sheds light on the proposed conflict management approach that is based on the generic framework. Retrieving the weighting factors needed for conflict redistribution is detailed. Section V reports the encouraging results of the experimental validation by confronting it to the classical approaches of the literature. In Section VI, we conclude and we sketch issues of future work.

II. BELIEF FUNCTION THEORY

The Belief Function Theory was initiated by the work of Dempster [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF] on the upper and lower probabilities. The development of the theory formalism is due to Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] which has shown the benefits of belief functions theory to model uncertain knowledge. In addition, it allows knowledge combination obtained through various sources. The belief function theory is based on several concepts. In the following, we present the main concepts of this theory.

A. Frame of discernment

The frame of discernment is the set of possible answers for a treated problem and generally noted Θ. It is composed of N exhaustive and exclusive hypotheses:

Θ = {H 1 , H 2 , ..., H N }.
The exhaustive assumptions means that the solution of the problem is necessarily one of the hypotheses H i from frame of discernment. The exclusivity condition support the unicity of the solution H i ∩ H j = ∅ ∀i = j. From the frame of discernment Θ, we deduce the set 2 Θ containing all the 2 N subsets A of Θ:

2 Θ = {A, A ⊆ Θ} = {H 1 , H 2 , ..., H N , H 1 ∪ H 2 , ..., Θ}.
This set constitutes a reference to assess the veracity of any proposal.

B. Basic Belief Assignment

A Basic Belief Assignment (BBA) m is the mapping from elements of the power set 2 Θ into [0, 1] such that:

m : 2 Θ -→ [0, 1] such that:    A⊆Θ m(A) = 1 m(∅) = 0. (1)
Each subset X of 2 Θ fulfilling m(X) > 0 is called a focal element.

C. Discounting

Assuming that an information source has a reliability rate equal to (1 -α) where (0 ≤ α ≤ 1), such a meta-knowledge can be taken into account using the discounting operation introduced by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], and defined by:

m α (B) = (1 -α) × m(B) ∀B ⊆ Θ m α (Θ) = (1 -α) × m(Θ) + α. (2)
A discount rate α equal to 1 means that the source is not reliable and the piece of information that it provides cannot be taken into account. On the contrary, a null discount rate indicates that the source is fully reliable and the piece of information it provides is entirely true. Thanks to the discounting, an unreliable source's BBA is transformed into a function assigning a larger mass to Θ.

D. Combination operators

In the following, we present several combination operators allowing sources fusion.

1) Conjunctive sum: Proposed within the Transferable Belief Model [START_REF] Smets | The Transferable Belief Model[END_REF], the conjunctive sum combines several information. For two sources S 1 and S 2 having respectively m 1 and m 2 as BBA, we write the conjunctive sum m ∩ in the following form:

m ∩ = m 1 ∩ m 2 . (3)
For an event m ∩ (A) can be written as follows:

m ∩ (A) = B∩C=A m 1 (B) × m 2 (C) ∀A ⊆ Θ. (4)
A normalized version of conjunctive rule proposed by Dempster [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF] integrates a conflict management approach that redistributes the generated conflictual mass. The Dempster's rule is defined as follows:

m ⊕ (A) = 1 1 -K B∩C=A m 1 (B)×m 2 (C) ∀A ⊆ Θ, A = ∅
(5) where K, representing the conflict mass between m 1 and m 2 , is defined as:

K = B∩C=∅ m 1 (B) × m 2 (C) = m ∩ (∅). (6)
m(∅) is called the conflictual mass. A BBA is called normal whenever the empty set is not a focal element and this corresponds to a closed world assumption [START_REF] Smets | The Transferable Belief Model[END_REF], otherwise it is said subnormal and corresponds to an open world assumption [START_REF] Smets | The Transferable Belief Model[END_REF].

2) Generic framework: Several works tackled grouping conflict operator in order to profit from their complementary contributions [START_REF] Lefevre | Belief functions combination and conflict management[END_REF], [START_REF] Lefevre | Reply to the comments of R. Haenni on the paper "Belief function combination and conflict management[END_REF], [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF], [START_REF] Lefevre | Towards an alarm for opposition conflict in a conjunctive combination of belief functions[END_REF], [START_REF] Lefevre | How to preserve the conflict as an alarm in the combination of belief functions?[END_REF]. From those operators, we distinguish the Generic framework, which generalizes the conflict redistribution and unifies several redistribution rules.

Introduced by Lefevre et al. [START_REF] Lefevre | Belief functions combination and conflict management[END_REF], the generic framework aims at distributing the conflictual mass m ∩ (∅) on a set of propositions P according to a weighting factor W (A, m) (A ⊆ P ) with m = {m 1 , ..., m j , ..., m J }. The final mass after fusion (combination), for a proposition A, is the sum of both masses:

m(A) = m ∩ (A) + m c (A) ∀A ⊆ Θ m(∅) = 0. ( 7
)
m c is part of the conflicting mass and can be written as follows:

m c (A) = W (A, m) • m ∩ (∅) ∀A ⊆ P m c (A) = 0 otherwise (8)
such that:

A⊆P W (A, m) = 1. (9)
The generic framework presents the largest representation for any conflict management approach. In fact, it does not only provide the largest framework for conflict management but also the possibility to customize the empty set mass redistribution using the weighting factors. This characteristic makes the generic framework flexible and suited in case of existence of an additional information.

E. Decision: Pignistic probability

The pignistic probability, denoted BetP , was proposed by Smets and Kennes [START_REF] Smets | The Transferable Belief Model[END_REF] within the Transferable Belief Model (TBM) approach. The pignistic transformation is generally considered as a good basis for a decision rule where it considers even the composite hypothesis in its treatment, formally:

BetP (H n ) = A⊆Θ |H n ∩ A| |A| × m(A) ∀H n ∈ Θ. (10)

III. DISTANCE CLASSIFIER: APPLICATION ON HIGH-RESOLUTION FOREST IMAGE

In the following, we introduce the based distance classifier that was adapted and applied of forest image classification problem. The proposed classifier relies on multi-source fusion. Several belief based classifiers exist such that the likelihood [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] and the tree based classifiers [START_REF] Elouedi | Belief decision trees: theoretical foundations[END_REF]. In our case, we built our classifier on the distance classifier [START_REF] Denoeux | K-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] for its simplicity and combinatorial explosion avoidance. The properties of this classifier is detailed and compared in [START_REF] Vannoorenberghe | Likelihood-based vs. distance-based evidential classifiers[END_REF].

A. Distance estimation model classifier

In order to profit from the large amount of data constituting our learning base, we opted for the Zouhal et al. [START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF] distance BBA estimation model. The presence of a training pattern x i , having the class {H i n }, among the K Nearest Neighbors (KNN) of under classification pattern x is considered as a piece of evidence. Indeed, it influences our belief concerning the class membership of the entity under consideration. This information is represented by a BBA m over the set Θ of classes. A fraction of the unit mass is assigned by m to the singleton {H i n }, and the remaining is assigned to the whole frame of discernment Θ. The mass m({H i n }) is defined as a decreasing function of the distance d between x and x i in the feature space. The K nearest neighbors of x can be regarded as K independent sources of information represented by BBA. These several pieces of evidence can be aggregated by means of Dempster's combination rule to represent our belief concerning x class membership. The adopted strategy consists in modeling the information according to every characteristic x j (with j ∈ [1, J]) of the vector x to classify. A belief function m sj is then defined by [START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF]:

m sj ({H n }) = α s j φ s j (d s j ) m sj (Θ) = 1 -α s j φ s j (d s j ) (11)
where 0 < α s j < 1 is a constant, d s j represents the distance between the j-th component x j of the vector x and its neighboring vector v s (s ∈ [1, K]). The function φ s j can be expressed in the following way:

φ s (d s j ) = exp(-γ s j (d s j ) 2 ). (12)
A learning algorithm was proposed by Zouhal et al. [START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF] for computing the parameters γ s j in the Eq. ( 12) by optimizing an error criterion.

Dempster's combination is used to combine those K belief functions. m j is the resulting belief function and it is equal to:

m j = ⊕ s∈[1,K] m sj . (13)
A unique belief function m is obtained by the application of the same fusion principle on those resulting J BBAs:

m = ⊕ j∈[1,J] m j (14)
with J standing for number of sources.

B. Forest image based belief classifier

In the following, defining a BBA to each extracted tree crown from the forest scene is detailed [START_REF] Samet | Classification of highresolution remote sensing image by adapting the distance belief function estimation model[END_REF]. Since we are dealing with composite sources, the choice of multidimentional model was the most appropriate. Also in order to profit from the large amount of data constituting our learning base, the distance model which integrates the distance measure helpful for BBA construction was chosen. Let us consider Θ the frame of discernment constituted by four classes {Zen Oak, Cork Oak, Arboretum, Conif erous tree}. Those four classes constitute the main tree's type existing in the image. Three different information sources are distinguished in the image. The Spectral, Texture and the Structural sources are used in the source fusing problem and are defined as follows:

• Spectral information: this source study the tree crown relatively to its level of grey mean.

• Texture information: a composite source which analyzes the tree crown by their gray level organization. The studied textural features are Mean, Variance, Energy, Contrast and the Entropy.

• Structural information: a composite source which analyzes the tree crown by their shape. The studied structural features are Area, Diameter, Perimeter and the Wellepsy.

For each one of the three information fusing source, we apply a KNN belief function estimation (Eq. ( 11)). Each feature gives four BBAs (K = 4) which are combined via the Dempster's combination rule (Eq. ( 13)). The result is a single BBA expressing the crown membership from the point of view of the considered composite source. We associate to each composite source BBA a reliability factor. These coefficients are obtained through experiments and by studying each characteristic individually. The percentage of good classification is our discounting coefficients (Table I and II). The same procedure is operated on the three sources. Their discounting coefficients are shown in Table III.

The gathered ten source's BBA are also combined through (Eq. ( 14)) to get the final tree crown's BBA. In the sequel, the described Distance Model Classifier is denoted DMC. In order to observe the concordance between fused sources, we replace the Dempster's rule in Eq. ( 14) by the conjunctive sum (Eq. 4). The resulting conflict is an indicator about contradiction between proposition brought by fused sources and might be in help afterward in classification improvement. Interested reader may refer to [START_REF] Samet | Classification of highresolution remote sensing image by adapting the distance belief function estimation model[END_REF] for further details.

IV. AUTOMATIC SEEK OF WEIGHTING FACTORS FOR CONFLICT MANAGEMENT

In this section, we detail the contribution of interpreting and using the conflict resulting from the conjunctive combination of several information sources. Analysing the conflict and redistribute it on probable classes was studied in [START_REF] Samet | Integration of extra-information for belief function theory conflict management problem through generic association rules[END_REF], [START_REF] Lefevre | Belief functions combination and conflict management[END_REF].

In this paper, we study the origins of the conflict resulting from the combination of tree crown BBAs. Once the origin is identified, we propose a method to redistribute conflict on the probable class through a conflict management approach. This method is called RCCA for Redistributing Conflict Classification Approach. Several operators for the conflict management exist in the literature allowing treating and managing the conflictual mass [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF]. Among these operators, we identify the generic framework which distinguishes by its unifying formalism. In the following, we present a method that aims to seek automatically the weighting factors depending of the analyzed area in the image.

A. Motivation

Several studied regions from the image present a high conflict values generated after the sources' fusion. As it is shown in Table IV, the conflict value exceeds the 0.4 in 74% of tree crown's BBA that could lead afterward to classification errors. This conflict appears with different rates depending the studied tree crown. The highest values of conflict are registered for the Arboretum areas. This means that the fused sources (i.e., spectral, textural and structural) are in contradiction. This conflict highness is interpreted as the result of the similarity existing between the Arboretum class and the other trees in the frame of discernment. This proves the importance of using an adequate conflict management approach in order to differentiate between classes.

B. Region determination of weighting factors for conflict management

Even if the generic framework is able to unify many classical operators of combination, the determination of weighting factors remain a problem that has to be solved. In the following, the Redistributing Conflict Classification Approach (RCCA), that is based on computing the generic framework's weighting factors, is detailed.

1) Conflict inductive class:

This method is based on the existence of a class that generates conflict after the combination phase. This class is denoted C conf lict . The C conf lict class has many resemblances with the other classes (reason for conflict appearance) but it distinguishes by a regional characteristic making it unique and recognizable. Those ascertainment have led us to identify the Arboretum as the C conf lict class. We also studied the image by areas to verify the membership of each region to the C conf lict class. To find correctly the weighting factor needed for the conflict management approach, we study the image following the frame of discernment Ω = {C conf lict , C conf lict }. Our proposed approach relies on studying the membership of each region according to its texture value. For this purpose, we calculate the belief function for each considered region in Ω. The calculated BBA is important to decide how to compute the weighting factors.

2) Region belief function estimation: Let's consider Ω = {C conf lict , C conf lict } the frame of discernment. For each analyzed region R in the image, we create a belief function that summarizes its membership rate to C conf lict class. This BBA can be written as follow:

m Ω R (C conf lict ) = β(d) m Ω R (Ω) = 1 -β(d) (15)
such that β is a function that depends on a distance value d that could be inspired from Eq.12. This BBA is built by adopting the growing region approach to bound regions belonging to C conf lict . The belief mass is found by the use of distance estimation approach (see section III). For each studied region, a BBA is modelized such that Eq.15. If the BBA confirms that the region belongs to the C conf lict class the studied region is expanded. The same principle is done to the expanded region.

The estimation of the BBA requires a distance d between the studied region and a theoretical value (prototype). The theoretical value is provided by a graph that indicates the theoretical texture value for each region size. In this work, we studied the expansion of the energy characteristic (texture information) for different region window size. A region is considered belonging to C conf lict if its granted belief (Eq. 15) is greater than a confidence threshold min conf fixed in the beginning. In case of the studied region belong to C conf lict by verifying the min conf condition, the region is expended. The analysis of the texture of those regions, as shown in the Figure 1, illustrates the highness of the energy. This figure constitutes a learning base that we applied to calculate the belief mass (Eq. 15) using a distance prototyped estimation approach (see section III). The estimation of those belief function is detailed in Algorithm 1. Indeed, seek texture region function computes the texture energy of a region R while euclidean distance function estimates the distance d between the studied region and a theoretical value.

3: m Ω R (C conf lict ) ← exp(-γ q × distance 2 ) 4: m Ω R (Ω) ← 1 -m Ω R (C conf lict )
3) Determination of the weighting factors: The assignment of the weighting factors depends on the studied region BBA. The determination of weighting factors is made only when the size of the analyzed region exceeds a threshold fixed by experiments. In these cases, for m Ω R (C conf lict ) greater than a fixed threshold, this region R will be considered as belonging to C conf lit class. In that case, each tree crown's BBA m in R is assigned the following weighting factors:

W (C conf lict , m) = m Ω R (C conf lict ) W (Θ, m) = m Ω R (Ω) (16)
Otherwise, if m Ω R (C conf lict ) is less than the threshold, this area does not belong to the C conf lit class and assignment of the weighting factors will be as follows:

W (C conf lict , m) = 0 W (Θ, m) = 1 (17)
This distribution is equivalent to transferring the conflict entirely on the assumption ignorance which corresponds to Yager's conflict management approach [START_REF] Yager | On the Dempster-Shafer framework and new combination rule[END_REF]. The Algorithm 2 details the conflict management approach for weighting factors determination.

Algorithm 2 Weighting factors determination

Require: Arboretum trees{A 1 , ..., A n }, T size, min conf Ensure:

weightingf actors{W A 1 , W Ω 1 , ..., W A n , W Ω n } 1: for all A i ∈ Arboretum trees do 2:
R ← Region(A i )

R ← Growing region(R)

5: {m Ω R } ← Belief f unction estimation(R) 6: until (m Ω R (C conf lict ) ≤ min conf or size(R) ≥ T size) 7: if m Ω R (C conf lict ) ≤ min conf then 8: W A i ← m Ω R (C conf lict ) 9:
W

Ω i ← 1 -m Ω R (C conf lict ) 10: else 11: W A i ← 0 12:
W Ω i ← 1 The Algorithm 2 computes the weighting factors, such that for example {W A 1 , W Ω 1 } represents the weighting factors of each tree crown located in the neighborhood of A 1 . The application of the Growing region function increments the size of the studied region to add more tree crowns. The call for Belief f unction estimation function allows to estimate the BBA for the studied region. The growing region process continues until we reach T size or the studied region does not belong anymore to the C conf lict class.

V. EXPERIMENTAL RESULTS

We conducted experiments on the classification applied on a set of QuickBird Near InfraRed (NIR) forest images having 0.6m per pixel as resolution. Indeed, we applied our classification approach in order to classify the tree crowns. Our study zone is a forest region in the administrative district of Jendouba in Tunisia, more specifically the town of Ain-Drahim. The Table VI shows the size of the learning base for each source. For the spectral information source, we have only four elements since we implemented the distance estimation model-prtotype version. It means, rather than using several tree crowns spectral values as learning base, we use their average rate. Each class has its own spectral average value.

A. Classification and conflict management contribution

The image is segmented by the brownian motion approach [START_REF] Erikson | Structure-preserving segmentation of individual tree crowns by brownian motion[END_REF]. The choice of learning zones was based on the information contained in the forest inventory. Indeed, the high resolution image was carved into several images. Some of them will be used to define our learning base and the other will be used to test the classification. In following, we present experimentally an assessment of the proposed RCCA approach contribution. In order to evaluate the contribution of RCCA, we are interested in comparing to a Distance Model Classifier (DMC) based on the distance belief estimation model and Dempster's combination (see Subsection III-A). Both methods rely on belief function theory classification. The proposed Redistribution Conflict Classification Approach (RCCA in Table V) was applied on highly conflictual BBAs gathered from different forest scenes. Those BBAs represent 642 tree crowns. The results were compared to a Distance Model Classifier (DMC) based on the distance belief estimation model and Dempster's combination. The results show the benefits of using the generic framework as conflict manager. All good classification rates of all four classes have been improved drastically. Indeed, singling out the arboretum class and treating it individually has improved the result of other classes comparatively to the distance classifier. In the other hand, the generic framework proves that it is a good asset since it allows the personalize the conflict redistribution for a better classification. The Figure 5, 6, 7 and 8 show the classification improvement for Arboretum. The region containing arboretum's trees is delimited with the growing region approach (see Subsection IV-B) then our redistribution conflict method is applied. As a result, we notice an important improvement in Arboretum classification by comparing Figure 6 and8. Focusing our conflict management approach on the conflict inductive class (Arboretum class) also had an impact on other classes. Indeed, our method can decide whether a studied region belongs to the arboretum class. If it is not the conflict is redistributed to the ignorance Θ which also could improve the results. Indeed, Figure 3, 4, 9 and 10 attest of the cited improvement for the Zen and the coniferous tree classes. Table VII shows that the RCCA provides the best classification results for the Zen oak and the Arboretum comparatively the other methods. This result can be interpreted as the conflict management contribution. Indeed, the RCCA operates a first classification and redistribute the conflict to the pertinent class following a conflict analysis. The learning stage is the the main the difference between the proposed approach and classical ones. In addition, the RCCA is based on uncertainty representation with the belief function theory. Such kind of modelization allows a better representation of the tree crown membership. This assertion can be proved by comparing the KNN results to its belief variant DMC in Table V. On the other hand, we notice that comparing to a Neural Network bassed classifier, RCCA maintain an acceptable good average in the detection of cork oak. The coniferous tree detection rate of Neural Network based classifier is the best.

VI. CONCLUSION

In this work, we proposed a method to classify a forest high resolution image based on belief function theory and conflict redistribution. As a first step, we adapted the belief distance classifier on tree crowns found in the image. The important registered conflict, obtained after source fusion, have led us to redistribute it smartly for classification improvement. Therefore, we adapted the generic framework and we proposed an automatic method to compute the weighting factors required for conflict redistribution that we called RCCA. The determination of the weighting factors is based on region analysis around conflict inductive tree crown class. As illustrated in the experimentation section, the redistribution conflict based approach has improved drastically all good classification rates. Even the comparison of RCCA to well known classifier has provided interesting results. In future works, we study the automatic seek of those weighting factors based on every region spatial characteristics. Indeed, the association between data mining and conflict management could be interesting.

Fig. 1 . 1 R 1 :

 111 Fig. 1. The energy value evolution depending on the image window size

Fig. 2 .

 2 Fig. 2. Zen area.

Fig. 3 .

 3 Fig. 3. Zen area DMC classification.

Fig. 4 .Fig. 5 .Fig. 7 .

 457 Fig. 4. Zen area RCCA classification.

Fig. 8 .

 8 Fig. 8. Arboretum area with RCCA classification.

Fig. 9 .

 9 Fig. 9. Coniferous tree area DMC classification.

Fig. 10 .

 10 Fig. 10.Coniferous tree area RCCA classification.

TABLE I

 I

	.	DISCOUNTING COEFFICIENT FOR TEXTURE SOURCE
			CHARACTERISTICS.
			Mean	Variance	Energy	Contrast	Entropy
	Discounting coefficient	0.4	0.4	0	0	0.5

TABLE II

 II

	.	DISCOUNTING COEFFICIENT FOR STRUCTURE SOURCE
			CHARACTERISTICS.
			Area	Diameter	Perimeter	Wellepsy
	Discounting coefficient	0.4	0.4	0	0

TABLE III

 III

	.	DISCOUNTING COEFFICIENT FOR THE CONSIDERED
			SOURCES.
			Texture	Spectral	Structure
	Discounting coefficient	0.4	0	0.2

TABLE IV

 IV

	.	REGISTERED CONFLICT FOR STUDIED TREE CROWNS
			[0, 0.2)	[0.2, 0.4)	[0.4, 1)
		Conflict rate	12%	14%	74%

TABLE VI

 VI

	.	LEARNING BASE SIZE OF THE USED INFORMATION
			SOURCES
		Spectral base Texture base Structural base
	Size	4	233	264

TABLE VII .

 VII COMPARATIVE RESULTS: RCCA VS KNOWN CLASSIFIERS. K Nearest Neighbour (KNN) Naive Bayes Neural Network Decision Tree RCCA

	Zen oak	55.07%	52.90%	65.21%	62.32% 83.25%
	Cork oak	68.27%	44.71%	86.54%	81.25% 72.11%
	Arboretum	54.86%	68.75%	67.36%	50.69% 81.05%
	Coniferous tree	42.10%	28.29%	55.26%	59.87% 43.43%


Ahmed Samet
email: ahmed.samet@fst.rnu.tn

Imen Hammami
email: imen.hammammi@fst.rnu.tn

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

Atef Hamouda
email: atef.hamouda@fst.rnu.tn

Generic discounting evaluation approach for urban image classification

Keywords: Belief function theory, Discounting, Classification, Conflict management, Source confusion

Belief function theory provides a robust framework for uncertain information modeling. It also offers several fusion tools in order to profit from multi-source context. Nevertheless, fusion is a sensible task where conflictual information may appear especially when sources are unreliable. Therefore, measuring source's reliability has been the center of many research and development. Existing solutions for source's reliability estimation are based on the assumption that distance is the only factor for conflictual situations. Indeed, integrating only distance measures to estimate source's reliability is not sufficient where source's confusion may be also considered as conflict origin. In this paper, we tackle reliability estimation and we introduce a new discounting operator that considers those two possible conflict origins. We propose an automatic method for discounting factor calculation. Those factors are integrated on belief classifier and tested on high-resolution image classification problem.

Introduction

The improvement of image acquisition techniques have led to the treatment of more complex images in terms of details. This detail complexity comes generally from the multi-band nature of the image. The multi-source information is too valuable for decision process but needs an adequate formalism able to manipulate it. In order to synthesize more useful information related to the observed scene, many formalisms were proposed manipulating those multi-source information and allowing to formalize mathematically uncertain and imprecise data as the Bayesian theory, fuzzy set theory,. . . The belief function theory, introduced by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and formalized by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], presents a powerful mathematical background in information fusion domain. It not only allows modelizing mathematically uncertainty and imprecision information but it also integrates many combination tools allowing source fusion. The fusion ability of this formalism is granted by several combination rules; the oldest is the Dempster's rule of combination. However, Zadeh in [START_REF] Zadeh | Review of Shafer's mathematical theory of evidence[END_REF] highlighted its counter-intuitive behavior. Additionally, a lot of studies have been interested on fusing information in the context of image classification [START_REF] Samet | Classification of high-resolution remote sensing image by adapting the distance belief function estimation model[END_REF]. Despite, the fact that belief function theory excels in extracting the most truthful proposition from a multi-source context, it nevertheless presents a major inconvenient that is conflict. The conflict is weight accorded to the empty set proposition and generally appears after source combination. Many works have been done in this domain allowing conflict elimination. In literature, we distinguish two main conflict management family approaches. The first family consists of managing the conflict meaning the combination operator allowing fit conflict redistribution. From those works we can cite [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's model[END_REF][START_REF] Yager | On considerations of credibility of evidence[END_REF]. Some authors tried to unify these combination rules [START_REF] Florea | Crisis management using Dempster Shafer theory: Using dissimilarity measures to characterize sources' reliability, C3I for Crisis[END_REF][START_REF] Ristic | The TBM global distance measure for the association of uncertain combat id declarations[END_REF]. Another method to reduce conflict is the use of discounting factors [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] before combining sources. Indeed, those kinds of approaches rely on the fact that conflict is inducted and generated by the unreliability of at least one source. Many works have been done finding those discounting factors such that [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF][START_REF] Guo | Evaluating sensor reliability in classification problems based on evidence theory[END_REF][START_REF] Klein | Automatic discounting rate computation using a dissent criterion[END_REF]. Shafer in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] has proven that the resulting conflict may not only come from source's contradiction in combination phase. Indeed, the confusion rate of a source may generate conflict. This assumption means that the more the source is less informative, the higher the conflict is. To the best of our knowledge, rare are the discounting based approaches that addressed conflict taking those two conflict origins into consideration. In this paper, we consider two possible factors for conflict and should be taken into consideration. The intrinsic conflict caused by the unreliability of a source to determine certain classes. The second considered conflict origin is the extrinsic conflict which indicates to what extent the obtained sources are in contradiction. In this work, we propose a new conflict management approach denoted Generic Discounting Approach (GDA) based on discounting factors determination. Those discounting factors are found by studying not only the confusion of the source but also its contradiction with the other ones. The GDA discounting approach was experimented on a high-resolution urban image classification problem. We take advantage of the belief function theory in order to modelize imperfect data extracted from the image and benefit from combination rules. Our classification approach is based on two main stages where, in the first phase, we combine multi-source information in order to obtain a reference classification. In the second stage, we try to improve the classification result by adding the GDA discounting approach. This paper is organized as follows: in the second section we briefly introduce the basics of the belief function theory. In section 3, we detail several extrinsic and intrinsic reliability measures developed in the framework of belief function theory. In the following, we introduce our Generic Discounting Approach (GDA) capable of estimating the reliability of a source regarding its two sided conflict measures. In section 5, we experiment our approach on a high resolution urban image providing comparative results with other notable works. Finally, we conclude and we sketch issues of future work.

The belief function theory or the evidence theory was introduced by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] in order to represent some imprecise probabilities with upper and lower probabilities. Then, it was mathematically formalized by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The belief function theory is used for representing imperfect (uncertain, imprecise and/or incomplete) information. In this section, we present the main concepts of this theory.

Frame of discernment

The frame of discernment is the set of possible answers for a treated problem and generally noted θ. It is composed of exhaustive and exclusive hypotheses:

θ = {H 1 , H 2 , ..., H N }.
These elements are assumed to be mutually exclusive and exhaustive. From the frame of discernment θ, we deduce the set 2 θ containing all the 2 N subsets A of θ:

2 θ = {A, A ⊆ θ} = {H 1 , H 2 , ..., H N , H 1 ∪ H 2 , ..., θ}
This set constitutes a reference to assess the veracity of any proposal.

Basic Belief Assignment

A Basic Belief Assignment (BBA) m is the mapping from elements of the power set 2 θ onto [0, 1] such that:

m : 2 θ -→ [0, 1]
having as constraints:

   A⊆θ m(A) = 1 m(∅) = 0. (1)
Each subsets X of 2 θ verifying m(X) > 0 is called focal elements. Constraining m(∅) = 0 is the normalized form of a BBA and this corresponds to a closed-world assumption [START_REF] Smets | Belief functions[END_REF], while allowing m(∅) > 0 corresponds to an open world assumption [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's model[END_REF].

Combination rules

The belief function offers many advantages. One of its proposed asset is the information fusion allowing extracting the more veracious proposition from a multi-source context. This benefit is granted by the combination rules. Several operators were defined such the conjunctive rule allowing fusion without any normalization (conflict management). For two sources S 1 and S 2 having respectively m 1 and m 2 as BBA, the conjunctive rule is defined by:

m ∩ (A) = B∩C=A m 1 (B) × m 2 (C) ∀A ⊆ θ. (2)
A normalized version of conjunctive rule proposed by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] integrates a conflict management approach that redistributes the generated conflictual mass. The Dempster's rule is defined as follows:

m ⊕ (A) = 1 1 -K B∩C=A m 1 (B) × m 2 (C) = 1 1 -K m ∩ (A) ∀A ⊆ θ, A = ∅
(3) where K is defined as:

K = B∩C=∅ m 1 (B) × m 2 (C) = m ∩ (∅). (4)
K represents the conflict mass between m 1 and m 2 .

Decision operators

In literature, among several functions that were proposed, we distinguish the pignistic probability. The pignistic probability noted BetP was proposed by Smets [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's model[END_REF] within his Transferable Belief Model (TBM) approach. TBM is based on the differentiation between the knowledge representation and decision-making level. In the decision phase, the pignistic transformation consists in distributing equiprobably the mass of a proposition A on its contained hypotheses, formally:

BetP (H n ) = A⊆θ |H n ∩ A| |A| × m(A) ∀H n ∈ θ. (5)

Discounting

Assuming that an information source has a reliability rate equal to (1 -α) where (0 ≤ α ≤ 1), such meta-knowledge can be taken into account using the discounting operation introduced by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], and defined by:

m α (B) = (1 -α) × m(B) ∀B ⊆ θ m α (θ) = (1 -α) × m(θ) + α. (6)
A discount rate α equal to 1 means that the source is not reliable and the piece of information it provides cannot be taken into account. On the contrary, a null discount rate indicates that the source is fully reliable and the piece of information it provides is entirely accepted. Thanks to discounting, an unreliable source's BBA is transformed into a function assigning a larger mass to θ.

Empty set mass resulting from the conjunctive rule can be considered as the most obvious conflict measure in the belief function theory. The conflictual mass could be seen as a measure of contradiction between BBA. Shafer in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], has defined the confusion of a source as a possible cause for conflict appearance after combination. The conflictual mass resulting from fusion could be seen as the result of the source confusion and the contradiction between fused BBA. In this part, we distinguish between two possible causes for the conflict. At first, the intrinsic conflict which is the conflict generated by the confusion rate of a source. The extrinsic conflict is the conflict resulting from source contradiction. In this section, we present notable state of art of metrics used to measure those two types of conflict.

Intrinsic conflict

The intrinsic conflict measures the consistency between the different focal elements inside the BBA. Several measures have been proposed in literature. These measures take into account the inclusion relations between the focal elements present in the BBA. Several measures were proposed such that the auto-conflict [START_REF] Osswald | Understanding the large family of Dempster-Shafer theory's fusion operators -a decision-based measure[END_REF]. Nevertheless, auto-conflict is a kind of contradiction measure that depends on order, it was therefore necessarily to define an independent measure that get rid of this constraint. Smarandache et al. [START_REF] Smarandache | Contradiction measures and specificity degrees of basic belief assignments[END_REF] proposed the contradiction measure, defined by:

contr(m) = c X⊆2 θ m(X) • D(m, m X ) (7)
where m X (X) = 1, X ∈ 2 θ is the categorical BBA, c is normalization constant and D is the Jousselme distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] defined for two mass function m 1 and m 2 by:

D(m 1 , m 2 ) = 1 2 • (m 1 -m 2 ) t • D • (m 1 -m 2 ) (8) D(A, B) = 1 if A = B = ∅ |A∩B| |A∪B| if A, B ⊆ 2 θ . (9)
From the other intrinsic distance, we can cite the confusion measure [START_REF] George | Quantification of conflict in Dempster-Shafer framework: A new approach[END_REF], the auto-conflict [START_REF] Osswald | Understanding the large family of Dempster-Shafer theory's fusion operators -a decision-based measure[END_REF], . . .

Extrinsic conflict

Several measures of extrinsic conflict have been studied in order to model the disagreement between sources. Indeed, if one source opinion disagree the other, their fusion will lead to an important conflictual mass. Some authors have defined distance between the mass functions directly, such as Jousselme's distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] (equation 8) which has the advantage of taking into account the cardinality of focal elements. From other distances, we can cite Euclidean distance [8], Tessem's distance [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF], Milan's distance [START_REF] Daniel | Conflicts within and between belief functions[END_REF]. Martin et al. [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF] proposes using a function that quantifies the conflict between BBA. This function, called Conf (., .), is defined as:

Conf (i, E) = 1 M -1 M k=1;i =k Conf (i, k) (10)
with M is the number of belief functions produced respectively by M sources called S 1 , . . . , S M and E is the set of BBA such that {m k |k = 1, . . . , M and k = i}. The function Conf (i, k) is obtained using a BBA distance introduced by Jousselme et al. [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]:

Conf (i, k) = D(m i , m k ). ( 11
)
The value Conf (i, E) quantifies the average conflict between the BBA m i and the BBAs of the set E. Once the conflict measure is obtained, the authors have proposed to compute discounting rates as follows:

α i = f (Conf (i, M )) ( 12
)
where f is a decreasing function. The authors propose to choose the function f as follows:

α i = (1 -Conf (i, M ) λ ) 1/λ (13)
with λ > 0. The authors recommend setting λ to 1.5. Extensions of this work use the idea of sequential discount to manage the conflict when combining belief functions [START_REF] Klein | Automatic discounting rate computation using a dissent criterion[END_REF].

Generic Discounting Approach (GDA) for conflict management

Many works have been proposed for finding discounting factors in order to eliminate conflict. Most of proposed discounting approaches rely on extrinsic measures rather than intrinsic measures. Rare were works that tried to associate those two conflict origins to estimate source reliability. In this section, we propose an automatic method to find those discounting factors depending on the two conflict measures. The GDA is a discounting approach that estimates source's reliability based on the two conflict origins. It is a function f satisfying several constraints:

-f is a increasing function from [0, 1] 2 → [0, 1] -f (1, 1) = 1 and f (0, 0) = 0. f := [0, 1] 2 → [0, 1] (δ, β) → δ (1-β) ( 14
)
where δ is an extrinsic measure and β is an intrinsic measure that can be chosen as follows.

δ = Dist(m) (15)
β = contr(m). (16)
Thus, the GDA is a function f that can be written as follows:

f := [0, 1] 2 → [0, 1] (δ, β) → (Dist(m)) (1-contr(m)) . ( 17
)
where Dist(m) designates the distance between m and other BBA and can be written:

Dist(m) = mi\m,i∈[1..I] D(m, m i ) I -1 . ( 18
)
D is the Jousselme's distance and contr(m) is the contradiction value indicating the confusion rate of the source itself. The discounting can be written as follows:

m GDA (B) = (1 -f (δ, β)) × m(B) ∀B ⊆ θ m GDA (θ) = (1 -f (δ, β)) × m(θ) + f (δ, β) (19)
In [START_REF] Samet | Reliability estimation with extrinsic and intrinsic measure in belief function theory[END_REF], we proposed another version for source discounting regrouping both intrinsic and extrinsic measures. The Table 1 shows the discounting value that could be associated to a BBA depending on the confusion and distance rates.

f (δ, β) = 1 f (δ, β) = D(m, m) Near f (δ, β) = 1 f (δ, β) = 0
Example 1. Let's consider the frame of discernment θ = {H 1 , H 2 } and three sources S 1 , S 2 and S 3 . The belief function values associated to those sources and their discounting values are calculated in Table 2.

We can remark that the distance between a source and the other directly affects the GDA discounting coefficient. The BBA's distance (extrinsic measure) is powered by the confusion (intrinsic measure) that is why the GDA factor is equal to the extrinsic measure when the source is not confused. However, it increases the more confused the source is. As it is shown in Table 2, GDA decreases drastically conflict where comparatively to the conjunctive sum, it fell from 0.717 to 0.0748. GDA also improved {H 1 } and {H 2 } hypothesis credibilities by considering S 1 and S 3 unconfused nature.

Classification optimization by discounting factors determination

In this part, we detail our image classifier and how we managed to integrate the GDA discounting to optimize the result of high-resolution urban image first classification. We experimented our approach on a Quickbird image covering urban areas of Strasbourg, taken in 2008, having four bands, each band with 2.44-2.88m/px. From the variety of object constituting this image, we are interested in finding roads, buildings and vegetation (see figure 1). Those three classes will constitute our frame of discernment θ = {Roads, Building, V egetation}.

In order to extract correctly those classes, we used five different sources. Each source corresponds to a band from the image. The five considered sources are: the R/G/B bands, the NDVI band and the PIR band.

First classification

In belief function estimation and classification, we distinguish two main family approaches. Likehood based approaches [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], rely on density estimation where they assume known the class-conditional probability densities for each class.

The second family, is the distance based approaches introduced by Zouhal and Denoeux [START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF]. Both methods are applicable in our image classification problem, but we have chosen to work with the distance based model for its simplicity of its generated BBA. The distance classifier relies on training base constituted by I vectors x i . Each training vector, belonging to H i n , sufficiently close to the vector to classify x constitutes a piece of evidence and should be taken into consideration. Indeed, this piece of evidence influences our belief concerning the class membership of the entity under consideration. A fraction of the unit mass is assigned by m to the singleton {H i n }, and the rest is assigned to the whole frame of discernment. Denoeux in [START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF], proposed a new alternative to the training base by characterizing each studied class by a prototype (a value that represents the class) rather than using training vectors x i . Two strategies for distance modeling can be differentiated which are the mono-dimensional and multi-dimensional variants. The difference consists in fusion's level where the multi-dimensional strategy considers the vector x as a single information leading to a unique fusion level. In the other hand, the mono-dimensional strategy apply the described distance estimation for each vector x component that lead to a two fusion level. In our case, we studied the mono-dimensional rather than the multi-dimensional variant which is also applicable. As training set we associated the distance estimation to a prototype base. For every x component x j (with j ∈ [1, .., J]), we estimate our BBA following this expression:

m sj ({H n }) = α s j φ s j (d s j ) m sj (θ) = 1 -α s j φ s j (d s j ) (20)
where 0 < α s j < 1 is a constant. φ s j is a decreasing function verifying φ s j (0) = 1 and lim d→∞ φ s j (d) = 0, d s j represent the distance between the constituent x j of the vector x and the component j-th prototype of source s. The φ s j function might be an exponential function following this form:

φ s (d s j ) = exp(-γ s j (d s j ) 2 ). ( 21
)
The use of Dempster combination operator allows merging those J belief functions. m s is the resulting belief function:

m s = ⊕ j∈[1,J] m sj . (22)
A unique belief function m is obtained by the application of the same fusion principle on those resulting S BBA:

m = ⊕ s∈[1,S] m s (23)
with S the number of source. The described method constitutes the Distance Classifier (DC). However, for our first classification, we replace the Dempster's combination rule (equation 23) by the conjunctive sum (equation 2) in order to generate conflict and analyze source's discordance. Those two methods are applied on each pixel of the image following to the studied sources.

Classification optimization

After a first classification, a high amount of conflict is generated making the results more or less acceptable. As it is shown in Table 3, more than 70 percent of our BBA present a conflict rate exceeding 0.6. This result means that 70 percent of the obtained BBA can be potentially attributed to another suited class. A conflict management approach is needed in order to improve results. In this section, we present how we managed to optimize and improve our classification results by adding an extra process which is conflict management. The pixels (BBA) that present a conflict rate superior to a threshold are reanalyzed by a new combination phase. In this new fusion step, we aim to discard unreliable sources following GDA discounting factors (equation 19). belief function framework. This classification is improved and optimized with a new conflict management approach. The conflict management is based on an automatic discounting factor calculation. The discounting factors are found using not only the BBA distance measure but also the confusion rate of belief function.

The first classification result has improved thanks to the discounting factors determination. In future work, we will try to propose a complete classification approach based on fusion discounted pieces of evidence. This discounting will also associate an intrinsic and extrinsic measures for more adequate combination.

Even if the results are satisfying on image classification, tests can be extended to UCI benchmarks to verify GDA contribution.

Fig. 1 .Fig. 2 .Fig. 3 . 4 .

 1234 Fig. 1. Strasbourg high-resultion urban image Fig. 2. GDA classification results

Table 1 .

 1 The GDA discounting value for the extremum cases

	Source With Confusion Without Confusion
	Distant

Table 2 .

 2 Evaluation of discounting approach on an example

		S1	S2	S3	m ∩ m GDA ∩
	{H1}	0.7	0.6	0.2 0.187 0.3061
	{H2}	0.1	0.3	0.7 0.0.094 0.1613
	θ	0.2	0.1	0.1 0.002 0.4578
	∅	0	0	0	0.717 0.0748
	δ	0.5845 0.7891 0.6904	-	-
	β	0.3452 0.2691 0.4562	-	-
	f (δ, β) 0.6428 0.7581 0.7842	-	-

ConclusionIn this paper, we presented a classification approach for urban high-resolution image. This method is based on two stages, a first classification based on the

Conflict rate < 0.4 < 0.6 > 0.6 5.006% 24.195% 70.779%

Application and results

In order to test our approach we compared it to the DC approach (described in section 5.1) based on distance estimation where conflict management is operated thanks to the Dempster's combination rule. The comparison were also conducted to Martin discounting approach [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF]. The test has been done 8458 images pixel where 1825 represent building points, 1666 road points and 4967 vegetation pixels. As it is shown in the Table 4, the proposed discounting factor approach (GDA) presents quite satisfying results. The versatility of the proposed discounting factors associated to the confused nature of the BBA have improved results. By comparing our approach to the DC approach, we can notice that we did improve all class detection. We can conclude that we did optimize the first classification.

The Figure 4 represents the classification of the original image (Figure 1) with DC approach. A first classification is applied as announced in section and instead of using the conjunctive combination rule, we apply Dempster's rule that integrates a conflict manager. The Figure 3 represents the initial image classification with Martin discounting approach.

The Figure 2 represents the same urban image classified using the proposed conflict manager. For each pixel in this image, we apply the first classification. For each high conflict pixel (BBA with high conflict rate), we calculate the discounting factor using the BBA's extrinsic and intrinsic rate.


Ahmed Samet
email: ahmed.samet@fst.rnu.tn

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

Sadok Ben Yahia
email: sadok.benyahia@fst.rnu.tn

Mining frequent itemsets in evidential database

Keywords: Evidential database, Support, Frequent evidential item, Evidential Apriori

Mining frequent patterns is widely used to discover knowledge from a database. It was originally applied on Market Basket Analysis (MBA) problem which represents the Boolean databases. In those databases, only the existence of an article (item) in a transaction is defined. However, in real-world application, the gathered information generally suffer from imperfections. In fact, a piece of information may contain two types of imperfection: imprecision and uncertainty. Recently, a new database representing and integrating those two types of imperfection were introduced: Evidential Database. Only few works have tackled those databases from a data mining point of view. In this work, we aim to discuss evidential itemset's support. We improve the complexity of state of art methods for support's estimation. We also introduce a new support measure gathering fastness and precision. The proposed methods are tested on several constructed evidential databases showing performance improvement.

Introduction

The majority of data mining algorithms were applied on precise and certain data constituting Boolean databases. This type of databases does only indicate if the considered item I exists or not. However, in real life, gathered information are suffering from imperfection due to many factors such as acquisition reliability, human errors, information absence, etc. In [START_REF] Lee | Imprecise and uncertain information in databases: an evidential approach[END_REF], Lee detailed the two sides of imperfection that could manifest in a database. Indeed, we may encounter databases containing imprecise and uncertain information. The imprecision is relevant to the content of an attribute value of a data object, while the concept of uncertainty is relevant to the degree of truth of its attribute value. Due to its adequate imprecision representation, the fuzzy theory [START_REF] Zadeh | Fuzzy sets[END_REF] was largely used to extract fuzzy frequent patterns and association rules such that [START_REF] Hong | A fuzzy AprioriTid mining algorithm with reduced computational time[END_REF][START_REF] Chen | Mining association rules from imprecise ordinal data[END_REF][START_REF] Lee | Mining fuzzy association rules with multiple minimum supports using maximum constraints[END_REF]. In [START_REF] Lee | Imprecise and uncertain information in databases: an evidential approach[END_REF], the author introduced a new type of databases that handle both imprecise and uncertain information. This database was modeled via the evidence theory [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], which offers a certain level of flexibility in imperfect information representation.

Those types of databases were denoted as the Evidential database. The Evidential database has brought flexibility in handling those imperfect knowledge but also added complexity in their treatment. Indeed, the number of patterns increases exponentially as far as the number of attributes arises in the database. Even the literature methodologies for estimating itemset's support are time consumer, since they rely on Cartesian product. In addition to the time limit, the proposed support functions such as those introduced in [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF][START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF], are not that precise in their estimation. The support computing do not explore all information that exist in the Basic Belief Assignment. This constraint makes from literature methods limited in their manner of support estimation and do not extract all existing frequent patterns within the evidential database. In this work, evidential data mining problem is tackled by putting our focus on the support estimation. Existing methods for support estimation are highlighted and we propose a ramification that considerably improves their original performance. We also introduce a new measure for evidential pattern's support estimation. This new measure improves the support computation where all pieces of information in a Basic Belief Assignment are considered. This method also presents an interesting performance comparatively to literature methods. We introduce the Evidential Data mining Algorithm (EDMA) that mines all frequent patterns in an evidential database. This paper is organized as follows: in section 2, the main principles of the evidence theory and Smets's TBM [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's Model[END_REF] interpretation are presented. In section 3, several state of art works are scrutinized and we highlight their limits. We present a ramification for their method that improves the performance. In section 4, we introduce a new method for evidential itemsets' support computing providing more precision in its estimation. Evidential Data Mining Apriori (EDMA) algorithm for mining frequent evidential patterns is introduced in section 5. The performance of this algorithm is studied in section 6. Finally, we conclude and we sketch issues of future work.

Evidence database

In this section, evidential database concepts based on evidence theory formalism are presented. In the following, we define evidence theory main concepts based on a Transferable Belief Model interpretation [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's Model[END_REF].

Evidence theory

The evidence theory or Dempster-Shafer theory proposes a robust formalism for modeling uncertainty. In the following, the evidence theory from a Smets's Transferable Belief Model (TBM) interpretation is presented. The TBM model represents quantified beliefs following two distinct levels: (i) a credal level where beliefs are entertained and quantified by belief functions; (ii) a pignistic level where beliefs can be used to make decisions and are quantified by probability functions. The evidence theory is based on several fundamentals such as the Basic Belief Assignment (BBA). A BBA m is the mapping from elements of the power set 2 θ onto [0, 1]:

m : 2 θ -→ [0, 1]
where θ is the frame of discernment. It is the set of possible answers for a treated problem and is composed of N exhaustive and exclusive hypotheses:

θ = {H 1 , H 2 , ..., H N }.
A BBA m do have some constraints such that:

A⊆θ m(A) = 1 (1)
Each subset X of 2 θ fulfilling m(X) > 0 is called focal element. Constraining m(∅) = 0 is the normalized form of a BBA and this corresponds to a closedworld assumption [START_REF] Smets | Belief functions[END_REF], while allowing m(∅) > 0 corresponds to an open world assumption [START_REF] Smets | The Transferable Belief Model[END_REF].

From a BBA another function is commonly defined from 2 θ to [0, 1]: Bel(A) is interpreted as the degree of justified support given to the proposition A by the available evidence.

Bel(A) = ∅ =B⊆A m(B) (2)
Generally, in an information fusion problem, not all considered sources share the same domain (frame of discernment). This constraint prevents from using usual combination tools [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF].

In this case, the Cartesian product allows the combination. Let it be two belief function m 1 and m 2 defined respectively in θ 1 and θ 2 , the Cartesian product is expressed as follows:

m θ 1×2 (A × B) = m θ1 1 (A) × m θ2 2 (B). (3)
After source's combination which integrates the credal stage of the TBM model, taking decision is necessarily. In [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's Model[END_REF], the pignistic probability is introduced allowing probabilistic decision from BBA following this formula:

BetP (H n ) = A⊆θ |H n ∩ A| |A| × m(A) ∀H n ∈ θ (4)
where |•| is the cardinality operator.

Evidence database concept

An evidential database stores data that could be perfect or imperfect. Uncertainty in such database is expressed via the evidence theory. An evidential database, denoted by EDB, with n columns and d lines where each column i (1 ≤ i ≤ n) has a domain θ i of discrete values. Cell of line j and column i contains a normalized BBA as follows:

m ij : 2 θi → [0, 1] with    m ij (∅) = 0 A⊆θi m ij (A) = 1. ( 5
)
Table 1. Evidential transaction database EDB

Transaction Attribute A Attribute B T1 m(A1) = 0.7 m(B1) = 0.4 m(θA) = 0.3 m(B2) = 0.2 m(θB) = 0.4 T2 m(A2) = 0.3 m(B1) = 1 m(θA) = 0.7
In an evidential database, as shown in Table 1, an item corresponds to a focal element. An itemset corresponds to a conjunction of focal elements having different domains. Two different itemsets can be related via the inclusion or intersection operator. Indeed, the inclusion operator for evidential itemsets is defined as follows, let X and Y be two evidential itemsets:

X ⊆ Y ⇐⇒ ∀x i ∈ X, x i ⊆ y i .
where x i and y i are the i th element of X and Y . For the same evidential itemsets X and Y , the intersection operator is defined as follows:

X ∩ Y = Z ⇐⇒ ∀z i ∈ Z, z i ⊆ x i and z i ⊆ y i . Example 1. In Table 1, A 1 is an item and {θ A B 1 } is an itemset such that A 1 ⊂ {θ A B 1 } and A 1 ∩ {θ A B 1 } = A 1 .

Evidential patterns' Cartesian based support

In this section, we present related works in support estimation for evidential databases. Afterwards, we sketch with an improvement that we propose to improve support's performance.

State of art

Evidential data mining does not grasp so much attention. In [START_REF] Hewawasam | Rule mining and classification in the presence of feature level and class label ambiguities[END_REF], Hewawasam et al. proposed a methodology to estimate itemsets' support and modelize them in a tree representation: Belief Itemset Tree (BIT). The BIT representation brings easiness and rapidity for the estimation of the associative rule's confidence. In [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF], the authors introduced a new approach for itemset support computing and applied on a Frequent Itemset Maintenance (FIM) problem. All methods [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF][START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF] were based on Cartesian product between BBAs.

Let's study the support of an itemset

X = i∈[1...n]
x i such that x i is an evidential item belonging to the frame of discernment θ i . Since the items do not share the same discernment frame, any fusion rule cannot be applied. In the following, we study the belief support introduced by [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF] computed by the following equation:

m j (X) = xi∈X m ij (x i ) (6)
where m j (X) is the Cartesian product of all BBA in the transaction T j . Thus, the BBA of the itemset X expressed in the entire EDB database becomes:

m EDB (X) = 1 d d j=1 m j (X). (7)
Then, the support of X in the EDB database becomes:

Support EDB (X) = Bel EDB (X). (8)
The Cartesian product based support, presented above, fulfills several properties such that the anti-monotony property. A support measure satisfying the anti-monotony property consists in the fact that an itemset that contains an infrequent itemset is also infrequent. The opposite is true, all itemsets constituting a frequent one are also frequent. With this satisfied property, the construction of an Apriori based algorithm becomes straightforward [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF].

Cartesian support ramification

The support measure, proposed by [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF][START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF] works (shown in equation 6), relies on Cartesian product. Indeed, the Cartesian product is the suited solution in case of combining BBAs with different frame of discernment. However, such solution waste execution time because of its exponential complexity. In this section, we focus our interest in simplifying the Cartesian based method for performance requirements. Let us consider the evidential database EDB and the itemset

X = x 1 × • • • × x n constituted by the product of items (focal elements) x i (1 ≤ i ≤ n) of the exclusive frame of discernment θ i .
For a transaction T j , we have:

Support Tj (X) = i∈[1...n] Support Tj (x i ) = i∈[1...n] Bel(x i ) (9) Support EDB (X) = 1 d d j=1
Support Tj (X) [START_REF] Smets | The Transferable Belief Model and other interpretations of Dempster-Shafer's Model[END_REF] Proof. Let us consider two evidential items and focal elements x 1 and x 2 belonging respectively to m 1 and m 2 BBA such that m = m 1 × m 2 .

Bel(

xi∈θi,1≤i≤n

x i ) = a⊆x1ו••×xn m 1ו••×n (a)
Bel(

xi∈θi,1≤i≤n

x i ) = y1⊆x1,...,y2⊆xn

m 1 (y 1 ) × • • • × m n (y 2 )
Bel(

xi∈θi,1≤i≤n

x i ) = y1⊆x1 m 1 (y 1 ) × • • • × yn⊆xn m n (y n ) Bel( xi∈θi,1≤i≤n x i ) = Bel(x 1 ) × • • • × Bel(x n ) = i∈[1...n]
Bel(x i )

In this section, the support is estimated with the Bel(.) function which generates several limits. In the following, we highlight those limits and we propose a new support alternative: The precise support.

Precise Evidential support estimation

The evidential database relies on representing information's imperfection with BBAs. A BBA does not only represent belief accorded to a single hypothesis but also to their disjunction. As shown in section 2, from a piece of evidence (BBA), several functions exist allowing the pertinence's estimation of each hypothesis. The Bel(.) (see equation 2), used for support definition in section 3, is not the only function that estimates the degree of veracity of each hypothesis in the superset 2 θ . In addition, Bel(.) estimates the belief by referring only to a small subset of the superset. This limits make from belief based support measures imprecise. In the following, we propose a new alternative to the Cartesian support estimation allowing a precise support computing and a reasonable time scale performance.

Support Definition

Let us consider an evidential database EDB and the itemset X = x 1 × • • • × x n constituted by the product of items (focal elements) x i (1 ≤ i ≤ n) of the exclusive frame of discernment θ i . The degree of presence of an item x i in a transaction T j (BBA) can be measured as follow:

P r : 2 θ → [0, 1] ( 11
) P r(x i ) = x⊆θi |x i ∩ x| |x| × m(x) ∀x i ∈ 2 θi . ( 12
)
As illustrated above, the P r(.) measure allows to compute x i presence in a single BBA. The P r measure is equal to the pignistic probability if

x i ∈ θ i . The evidential support of an itemset X = i∈[1...n]
x i is then computed as follows:

Support P r Tj (X) = Xi∈θi,i∈[1...n] P r(x i ) ( 13
)
Support EDB (X) = 1 d d j=1 Support P r Tj (X). ( 14
)
The presented approach for estimating itemset evidential support is similar to the support ramification given subsection 3.2. However, our approach presents several assets where our support inclusion is larger than those given in respectively [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF][START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF]. Indeed, in the previous cited works, the authors evaluate support of X by considering only subsets included in it. The P r(.) function does not only consider all subsets of X but also those having intersection with it. In addition, our support estimation provides an interesting performance since we get rid of the Cartesian product. The proposed support function sustains previous works on fuzzy [START_REF] Hong | A fuzzy AprioriTid mining algorithm with reduced computational time[END_REF] in case of dealing with consonant BBA3 . It also sustains previous data mining works on binary databases [START_REF] Agrawal | Fast algorithm for mining association rules[END_REF] when BBA are certain 4 . Indeed, previous works have adopted a probabilistic orientation in support measure in those databases. Support generally represents the frequency of appearance of an itemset therefore it can be assimilated to an apriori probability. Interestingly enough, the precise support estimation function keeps the interesting anti-monotony property useful in infrequent itemsets removal. This fulfilled condition is proven in the proof given below.

Proof. Assuming an evidential database EDB, let's consider two evidential itemsets A and A × X where A ⊂ A × X such that ∀x ∈ A, x ∈ A × X. We aim to prove that considering this condition Support(A × X) ≤ Support(A). Support Tj (A × X) = P r(A) × P r(X) Support Tj (A × X) ≤ Support Tj (A) Since P r(X) ∈ [0, 1] then Support EDB (A × X) ≤ Support EDB (A)

Pr Table

Let us consider be the evidential database EDB containing n attributes and d transactions. The Pr Table is a table having d rows (j ∈ [1, d]) where each one contains the P r(.) measure of all items (focal elements) found in the j th transaction of EDB. Since the support function can be written as a simple product, the storage of item's P r measure in a table became a need. Table 2 shows the Pr Table extracted from the evidential database EDB presented in Table 1. 1 Transaction Transactional Support T1 P r θ A (A1) = 0.85 P r θ A (A2) = 0.15 P r θ A (θA) = 1.00 P r θ B (B1) = 0.60 P r θ B (B2) = 0.40 P r θ B (θB) = 1.00 T2 P r θ A (A1) = 0.35 P r θ A (A2) = 0.65 P r θ A (θA) = 1.00 P r θ B (B1) = 1.00 P r θ B (B2) = 0.00 P r θ B (θB) = 1.00

Evidential Data Mining Apriori: EDMA

In this section, we introduce the Evidential Data Mining Apriori (EDMA) algorithm that allows the extraction of all frequent itemsets. Each itemset having a support greater than a threshold minsup is considered as frequent and is retained. The proposed algorithm relies on Apriori algorithm basics [START_REF] Agrawal | Fast algorithm for mining association rules[END_REF].

Apriori exploits this assumption by generating frequents in a level-wise manner. First of all, it generates frequent items (level 1) by removing those candidates (items) that do not fulfill the minsup constraint. From the generated frequent, it seeks to find the frequent of the next level by composing those of the precedent level. The treatment comes to an end when no further frequent itemset can be generated.

Algorithm 1 sketches the EDMA algorithm where it generates EIF F the set of all evidential frequent itemset. Their determination is based on support measure and minsup constraint fulfillment. This test is performed by Frequent itemset function. The support is computed through the Support estimation function. As it is shown, the support estimation does not rely anymore on calculating the Cartesian product of BBAs but on stored item's precise measure (Pr Table ). Since the algorithm sweeps the search space in breadth first manner, EDMA generates candidates (i.e., candidate apriori gen function) from the frequent itemset of the previous level. EDMA is an Apriori based algorithm that extract frequent evidential itemsets. It also generalizes several other known mining algorithms. In case of having only categorical items (categorical BBA), the database can be viewed as a binary transaction database. In this case, the proposed EDMA approach for evidential databases matches the original Apriori algorithm for binary databases [START_REF] Agrawal | Fast algorithm for mining association rules[END_REF]. Since Evidential database represents imprecision and uncertainty, it assimilates fuzzy databases via consonant BBA. The EDMA approach also assimilates other fuzzy Apriori algorithms as [START_REF] Hong | A fuzzy AprioriTid mining algorithm with reduced computational time[END_REF].

Algorithm 1 Evidential Data Mining Apriori (EDMA) algorithm

Require: EDB, minsup, P T, Size EDB Ensure: EIFF 1: function Support estimation(P T , I, d) 2:

SupI ← 0 3: for j=1 to d do 4:

SupT rans ← 1 5:

for all i ∈ P r(j).f ocal element do 6:

if P r(j).f ocal element ∈ I then 7:

SupT rans ← SupT rans× P r(j

Experimentation and results

In this section, we present how we managed to conduct our experiments and we discuss comparative results.

Evidential database construction

No doubt the evidential database is a real life need where opinions are perfectly modeled via BBAs. Despite their real contribution, evidential databases are really hard to find. In [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF], tests were conducted on synthetic database. Even in [START_REF] Bach Tobji | Frequent itemset mining from databases including one evidential attribute[END_REF], the constructed BBA includes only one evidential attributes. In [START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF], the authors worked on a simplified naval anti-surface warfare scenario. In the following, we propose a method that allows to construct an evidential database from a numerical dataset. We based our evidential database construction on the ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] clustering approach. It is an FCM-like algorithm based on the concept of credal partition, extending those of hard, fuzzy, and possibilistic ones. To derive such a structure, we minimized the proposed objective function:

J ECM (M, V ) d i=1 {j/Aj =∅,Aj ⊆Ω} c α j m β ij dist 2 ij + n i=1 δ 2 m β i∅ ( 15
)
subject to:

{j/Aj =∅,Aj ⊆Ω} m ij + m i∅ = 1 ∀i = 1, d (16)
where m i∅ and m ij denote respectively m i (∅) and m i (A j ). M is the credal partition M = (m 1 , . . . , m d ) and V is a cluster centers matrix. c α j is a weighting coefficient and dist ij is the Euclidean distance. In our case, the parameters α, β and δ were fixed to 1, 2 and 10. In order to obtain evidential databases, this approach was applied on several UCI benchmarks [START_REF] Frank | UCI machine learning repository[END_REF]. The studied datasets are summarized on Table 3 in terms of number of instances and attributes. For each dataset, the number of focal elements after ECM application was addressed. The number of focal element is related to the objective function J ECM that was minimized.

Comparative results

We compared the precise support measure integrated into the EDMA algorithm to [START_REF] Bach Tobji | Incremental maintenance of frequent itemsets in evidential databases[END_REF][START_REF] Hewawasam | Rule mining and classification in a situation assessment application: A belief-theoretic approach for handling data imperfections[END_REF] support metric. As it is shown in Table 4, the EDM A -P r attribute concerns the introduced precise support and EDM A -Bel refers to the definition given in section 3. For our experimentation, we integrated the ramification support (subsection 3. Table 4 illustrates the number of extracted frequent patterns from the evidential databases. As is it demonstrated, the Precise support extracts more frequent pattern than do the based belief method. This result is expected since the precise metric study all subsets of the superset and considers those having an intersection with the considered itemset. In addition, the number of patterns increases normally as far as the considered minsup threshold decreases.

We also conducted performance test on our proposed algorithm which we compared to an exhaustive approach. This approach consists in the Cartesian based algorithm (Cart-Bel in Table 5). The Cartesian algorithm computes all possible BBAs needed for support measure. The complexity of such approach is exponential with respect to the number of focal elements. Indeed, for an evidential database with k attributes each one has n focal elements and d transactions. The arithmetic complexity of a Cartesian product is: Table 5 illustrates a comparative performance tests between EDMA and Cartesian based algorithm. The proposed algorithm has drastically improved the results. The extraction performance of the EDMA-Bel is better than those of EDMA-Pr. This observation can be explained by the number of extracted patterns. The more frequent candidates are generated, the more time consumed is.

C = d × n k = O(n k ).

Conclusion

In this paper, we tackled data mining problem in evidential databases. We focused on evidential itemsets' support estimation. We detailed state of art evidential support metric. To drop the original complexity, we proposed a simplification for their methods by reducing the Cartesian product to a simple belief product. We also introduced a new support measure that brings precision by analyzing deeply the BBA's frame of discernment. The proposed precise measure extracts more hidden frequent patterns than the usual method. The precise measure was applied on an Apriori based algorithm and was tested on evidential databases obtained from transformed datasets. As illustrated in the experimentation section, despite the huge item's number that evidential database contains, EDMA generates all frequent itemsets in a reasonable execution time. This problem can be recovered in future works by tackling compact evidential itemset representation. Indeed, estimating the support exactly from a compact set had never been more challenging. In addition, quality test for the generated frequent patterns is a need. In future work, we plan to study the developpement of a new method to estimate the confidence of evidential associative rules based on our support measure.

Table 2 .

 2 Pr Table deduced from the evidential database EDB presented in Table

  While (candidate = ∅) 27: f req ← F requent itemset (candidate, minsup, P T, Size EDB) 28: size ← size + 1 29: EIFF ← EIFF ∪ f req 30: candidate ← candidate apriori gen(EDB, size, f req) 31: End While

			14: function Frequent itemset(candidate,
				minsup, P T , Size EDB)
			15:	f requent ← ∅
			16:	for all x in candidate do
			17:	if Support estimation(P T, x, Size EDB) ≥
				minsup then
			18:	f requent ← f requent∪{x}
			19:	end if
			20:	end for
			21:	return f requent
			22: end function
			23: EIFF ← ∅
		).value	24: size ← 1
	8:	end if	25: candidate ← candidate apriori gen(EDB, size)
	9:	end for	26:
	10:	SupI ← SupI + SupT rans
	11:	end for
	12:	return Sup I d
	13: end function

Table 3 .

 3 Data set characteristics

	Data set	#Instances #Attributes #Focal elements
	Iris	150	4	32
	Vertebral Column	310	6	64
	Diabetes	767	9	144
	Abalone	4177	9	40

  2) into EDMA algorithm. Since EDMA relies on a table that contains all item's metric values, we created the Belief Table (BT). The Belief Table has the same structure as that of Pr Table (c.f., subsection 4.2) and in which we stored all item's belief. The different approaches were tested on the obtained evidential database as illustrated in subsection 6.1.

Table 4 .

 4 Comparative results in terms of the number of frequent pattern number

	Support	Iris	Diabete	Vertebral Column	Abalone
		EDMA-Pr	EDMA-Bel	EDMA-Pr	EDMA-Bel	EDMA-Pr	EDMA-Bel	EDMA-Pr	EDMA-Bel
	0.9	15	15	319	191	63	63	767	511
	0.8	23	15	1503	319	95	63	767	511
	0.7	47	15	5055	671	415	63	767	511
	0.6	95	31	9074	1407	799	95	1919	511

Table 5 .

 5 Comparative results in terms of execution time (seconds)

	Support		Iris			Diabete	Vertebral Column	Abalone
		EDMA-Pr EDMA-Bel Cart-Bel ≈	EDMA-Pr	EDMA-Bel Cart-Bel ≈ EDMA-Pr EDMA-Bel Cart-Bel ≈ EDMA-Pr EDMA-Bel Cart-Bel ≈
	0.9	0.13	0.10	96172	4.72	1.65 6.43E+48 0.74	0.24 3.96E+24 79.71	16.35 9.13E+41
	0.8	0.13	0.11	96172	175.94	3.00 6.43E+48 1.11	0.24 3.96E+24 75.77	16.18 9.13E+41
	0.7	0.35	0.15	96172	21188	12.69 6.43E+48 15.21	0.24 3.96E+24 77.23	16.24 9.13E+41
	0.6	1.01	0.25	96172 12.21E+4 100.56 6.43E+48 116.32	0.33 3.96E+24 337.87 16.21 9.13E+41

A BBA is said consonant if focal elements are nested.

A BBA with only one focal element A is said to be certain and is denoted m(A) = 1.