Dempster-Shafer clustering, Potts spins and graph optimization

Authors:

  • Bengtsson Mats
  • Schubert Johan

Publish date: 1999-11-17

Report number: FOA-R--99-01248-505, 616

Pages: 22

Written in: English

Abstract

This article investigates problems within the Dempster-Shafer theory, both from a practical numerical side and a theoretical side. The practical part deals with clustering of 2 -1 pieces of evidence into K clusters. We demonstrate that the Dempster-Shafer measure for the weight of conflict of evidence can as an approximation be linearized, and be mapped to an antiferromagnetic Potts spin model. This facilitates efficient numerical solutions, even for large problem sizes. Optimal or nearly optimal solutions are found for Dempster-Shafer clustering benchmark tests with a time complexity of O(N 2 log2N). Furthermore, an isomorphism between the antiferromagnetic Potts spin model and a graph optimization problem is shown. The graph model has dynamic variables living on the links, which have a priori given probabilities that are directly related to the pairwise conflict between evidence. Hence, the relations between three different models are demonstrated.