MST - distanta pe manifold

Vizualizare 2D a unei benzi spiralate. Linia rosie punctata = distanta euclidiana directa. Linia galbena = drumul unic A-B prin MST.

Selectare A si B

Poti da click pe orice punct. Primul click selecteaza A, al doilea selecteaza B. Apoi selectia reincepe cu A. Butonul „Exemplu contraintuitiv” alege doua puncte apropiate geometric, dar separate de mai multe ture ale spiralei.

Numar puncte 220

Mai multe puncte descriu mai fin manifoldul. MST foloseste toate punctele pentru a construi o structura conexa fara cicluri.

Zgomot 0.025

Zgomotul indeparteaza punctele de pe curba ideala. La zgomot mare pot aparea legaturi MST care scurteaza accidental drumul si arata o limita a metodei.

Spatiere intre ture 0.075

Controleaza distanta dintre bratele spiralei. Cand turele sunt apropiate, doua puncte pot avea distanta euclidiana mica desi sunt departe de-a lungul manifoldului.

-distanta euclidiana

-distanta prin MST

-raport MST / Euclid

-muchii pe drum

De ce sunt distantele diferite?

Distanta euclidiana ignora forma datelor si traseaza o scurtatura directa prin spatiu. Distanta MST obliga traseul sa urmeze legaturile arborelui. Este o aproximare didactica a ideii de distanta geodezica, dar nu este in general egala cu geodezica reala.

Apasa „Exemplu contraintuitiv”. Intuitia euclidiana poate spune „aproape”, in timp ce structura manifoldului spune „departe”.

Atentie metodologica: MST este foarte sensibil la o singura legatura scurta intre doua brate apropiate. In metode precum Isomap se foloseste de regula un graf local k-NN si drumuri minime, nu MST ca estimator universal al distantei geodezice.