Dempster-Shafer clustering, Potts spins and graph optimization
Publiceringsdatum: 1999-11-17
Rapportnummer: FOA-R--99-01248-505, 616
Sidor: 22
Skriven på: Engelska
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.