Jag accepterar att kakor lagras på min dator

Läs mer

Dempster-Shafer clustering, Potts spins and graph optimization.

Dempster-Shafer clustering, Potts spins and graph optimization. Beställ tryckt exemplar Lägg i kundvagnen
Författare: Bengtsson Mats, Schubert Johan
Ort: Linköping
Sidor: 22
Utgivningsår: 1999
Publiceringsdatum: 1999-11-17
Rapportnummer: (FOA-R--99-01248-505, 616)
Nyckelord beslutsteori, Demspter-Shafer, klustring, potts spinn, decision theory, Dempster-Shafer, clustering, potts spins, 73, E14362
Sammanfattning Denna artikel undersöker problem inom Dempster-Shafer teori, från såväl en praktisk numerisk sida som en teoretisk sida. Den praktiska delen omfattar klustring av 2 K -I evidenser i K kluster. Vi visar att Dempster-Shafer måttet på viktfunktionen för konflikten mellan evidenser kan approximeras med en linearisering, och att detta mått kan avbildas på en antiferromagnetisk Potts spinn model. Detta möjliggör effektiva numeriska lösningar också för stora problem. Optimala eller nära optimala lösningar hittas för Dempster-Shafer klustringsproblem i en benchmarking studie med en tidskomplexitet O)N2 log2 N). Dessutom visas en isomorfism mellan den antiferromagnetiska Potts modellen och ett grafoptimeringsproblem. Grafmodellen har dynamiska variabler på länkarna som också har a priori sannolikheter som är direkt relaterade till den parvisa konflikten mellan evidenser. Följaktligen visas relationer mellan tre olika modeller.
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.

Kundvagn

Inga rapporter i kundvagnen

FOI, Totalförsvarets forskningsinstitut

FOI
Totalförsvarets forskningsinstitut
164 90 Stockholm

Tel: 08-555 030 00
Fax: 08-555 031 00

Orgnr: 202100-5182