Information and Combination: the Conflicting Relationships
Informations et Combinaison: Les Liaisons Conflictuelles
OPEN ACCESS
Within the framework of the Dempster-Shafer theory of evidence, data fusion is based on the building of single belief mass by combination of several mass functions resulting from distinct information sources. This combination, called Dempster’s rule of combination, or orthogonal sum, has several interesting mathematical properties, like commutativity or associativity. Unfortunately, it badly manages the existing conflict between the various information sources at the normalization step. The management of conflict is a major issue, especially during the fusion of many information sources. Indeed, the conflict increases with the number of information sources. That is why a strategy of conflict redistribution is essential. In this paper, we define a formalism to describe a family of combination operators. We propose to develop a generic framework in order to unify several operators. We introduce,within this generic framework, traditional combination operators used within the evidence theory. We propose other operators allowing a less arbitrary redistribution of the conflicting mass on the propositions. These various combinations operators were tested on sets of synthetic belief masses and real data.
Résumé
Dans le cadre de la théorie de l’évidence ou théorie de Dempster-Shafer, la fusion de données est basée sur la construction d’une masse de croyance unique résultant de la combinaison de plusieurs fonctions de masse issues de sources d’information distinctes. Cette combinaison, appelée règle de combinaison de Dempster, ou somme orthogonale, possède différentes propriétés mathématiques intéressantes telle que la commutativité ou l’associativité. Cependant, cette combinaison, à cause de l’étape de normalisation, gère mal le conflit existant entre différentes sources d’information. La gestion du conflit n’est pas mineure, particulièrement lorsqu’il s’agit de fusionner de nombreuses sources d’information. En effet, le conflit a tendance à croître avec le nombre de sources d’information à fusionner. C’est pourquoi une stratégie de redistribution de ce conflit est indispensable. L’idée de cet article est de définir un formalisme permettant de décrire une famille d’opérateurs de combinaison. Pour cela, nous proposons un cadre générique afin d’unifier plusieurs opérateurs. Nous présentons, au sein de ce cadre de travail, les opérateurs de combinaison classiques utilisés dans le cadre de la théorie de l’évidence. Nous proposons ensuite d’autres opérateurs permettant une redistribution moins arbitraire de la masse conflictuelle sur les propositions. Ces opérateurs seront testés et comparés aux opérateurs classiques sur des fonctions de croyance synthétiques et des données réelles.
Data fusion, Dempster-Shafer theory of evidence, combination rules, conflict.
Mots clés
Fusion d’informations, théorie de Dempster-Shafer, règles de combinaison, conflit.
[1] « Numéro spécial : Fusion de données », Revue Traitement du signal, vol. 11, n°6, 1994.
[2] « Numéro spécial : Fusion de données », Revue Traitement du signal, vol. 14, n°5, 1997.
[3] I. Bloch, « Incertitude, imprécision et additivité en fusion de données : point de vue historique », Revue Traitement du signal, vol. 13, n°4, pp. 267-288, 1996.
[4] I. Bloch, « Information combinaison operators for data fusion : A comparative review with classification », IEEE Transactions on Systems, Man and Cybernetics, vol. 26, n°1, pp. 52-67, 1996.
[5] A. Appriou, « Probabilités et incertitude en fusion de données multi-senseurs », Revue Scientifique et Technique de la Défense, vol.11, pp. 27-40, 1991.
[6] I. Bloch and H. Maître, « Fusion de Données en traitement d'images : modèles d’informations et décisions », Revue Traitement du Signal, vol.11 (Numéro Spécial : Fusion de données), n°6, pp. 435-446, 1994.
[7] I. Bloch, « Some aspects of Dempster-Shafer evidence theory for classification of multi-modality medical images taking partial volume effect into account », Pattern Recognition Letters, vol.17, pp. 905-919, 1996.
[8] L. A. Zadeh, On the Validity of Dempster’Rule of Combination of Evidence, Univ. of California, Berkeley, 1979.
[9] R. Yager, « On the Dempster-Shafer framework and new combinaison rules », Information Sciences, vol. 41, pp. 93-138, 1987.
[10] D. Dubois and H. Prade, « Representation and combination of uncertainty with belief functions and possibility measures », Comput. Intell., vol. 4, pp.244-264, 1988.
[11] P. Smets, « The Combination of Evidence in the Transferable Belief Model », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.12, n°2, pp. 447-458, 1990.
[12] A. Dempster, « Upper and Lower Probabilities Induced by Multivalued Mapping », Annals of Mathematical Statistics, vol. AMS-38, pp.325-339, 1967.
[13] G. Shafer, A Mathematical Theory of Evidence, Princeton, New Jersey University Press, 1976.
[14] P. Smets, « What is Dempster-Shafer's Model ? », in Advances in the Dempster-Shafer Theory of Evidence (R.R. Yager and M. Fedrizzi and J. Kacprzyk, eds.), pp.5-34, Wiley, 1994.
[15] P. Smets and R. Kennes, « The Transferable Belief Model », Artificial Intelligence, vol.66, n°2, pp.191-234, 1994.
[16] P. Smets, « Belief Functions : The Disjonctive Rule of Combination and the Generalized Bayesian Theorem », International Journal of Approximate Reasoning, vol. 9, pp. 1-35, 1993.
[17] E. Lefevre and P. Vannoorenberghe and O. Colot, « Using information criteria in Dempster-Shafer's basic belief assignment », in Proceeding of Fuzz'ieee 99, pp.173-178, 1999.
[18] P. Walley and S. Moral, « Upper probabilities based only on the likelihood function », Journal of Royal Statistical Society, Serie B, vol.61, n° Part 4, pp. 831-847, 1999.
[19] T. Denoeux, « A k-nearest neighbour classification rule based on Dempster-Shafer Theory », IEEE Transactions on Systems, Man and Cybernetics, vol.25, n°5, pp.804-813, 1995.
[20] L. M. Zouhal and T. Denoeux, « An evidence-theoretic K-NN rule with parameter optimization », IEEE Transactions on Systems, Man and Cybernetics-Part C, vol. 28, n°2, pp. 263-271, 1998.
[21] T. Denoeux, « A neural network classifier based on Demspter-Shafer theory », IEEE Transactions on Systems, Man and Cybernetics Part A, vol.30, n°2, pp. 131-150, 2000.
[22] T. Denoeux and L. M. Zouhal, « Handling possibilistic labels in pattern classification using evidential reasoning », Fuzzy Sets and Systems, vol.122, n°3, pp. 47-62, 2001.
[23] D. Dubois and H. Prade, « On the unicity of Dempster rule of combination », International Journal of Intelligent System, vol. 1, pp.133-142, 1986.
[24] F. Klawonn and E. Schwecke, « On the axiomatic justification of Dempster’s rule combination », International Journal of Intelligent Systems, vol.7, pp. 469-478, 1992.
[25] F. Voorbraak, « On the justification of Dempster’s rule of combinations », Artificial Intelligence, vol.48, pp.171-197, 1991.
[26] R. R. Yager, « Hedging in the combination of evidence », Journal of Information and Optimization Sciences, vol. 4, n°1, pp. 73-81, 1983.
[27] E. Lefevre and O. Colot and P. Vannoorenberghe, « Contribution des mesures d’informations à la modélisation crédibiliste des connaissances », Revue Traitement du signal, vol. 2, pp. 87-97, 2000.
[28] S. Fabre and A. Appriou and X. Briottet, « Presentation and description of two classification methods using data fusion based on sensor management », Information Fusion, vol. 2, pp. 49-71, 2001.
[29] C. Royère and D. Gruyer and V. Cherfaoui, « Identification d’objets par la combinaison d’experts à l’aide de la théorie de l’évidence », Rencontre Francophone sur la Logique Floue et Ses Applications LFA’2000, pp. 237-244, Octobre 2000.
[30] Ph. Smets, Qualitative and Quantitative Practical Reasoning, ch. The Alpha-Junctions : Combination Operators Applicable to Belief Functions., pp.131-153, Springer Verlag, Kruse R. and Nonengart A. and Ohlbach H. J. ed., Berlin, 1997.
[31] E. Lefebvre, O. Colot, P. Vannoorenberghe, and D. de Brucq, « A generic framework for resolving the conflict in the combinaison of belief structures », in Thrid International Conference on Information Fusion (FUSION’2000), pp. MOD4 11-14, July 2000.
[32] P. Smets, « Constructing the pignistic probability function in a context of uncertainty », Uncertainty in Artificial Intelligence 5, (M. Henrion and R. D. Schachter and L.N. Kanal and J.F. Lemmer, eds.) (Amsterdam), pp. 29-40, North-Holland, 1990,
[33] D. Michie and D.J. Spiegelhalter and C.T. (Eds.), Machine Learning, Neural and Statistical Classification, Ellis Horwood Serie in Artificial Intelligence, Chichester, U.K. : Ellis Horwood, 1994.
[34] D. Dubois and M. Grabisch and H. Prade and P. Smets, « Using the transferable belief model and a qualitative possibility theory approach on an illustrative example : the assessment of the value of a candidate », International Journal of Intelligent Systems (To appear), 2001.