Könnten alle heuristischen Ansätze, wie UPGMA, in wiederholten Analysen unterschiedliche Ergebnisse liefern?

Question

Ich würde gerne wissen, ob alle heuristischen Ansätze, aber konkret UPGMA oder Affinitätspropagierung unterschiedliche Ergebnisse in wiederholten Analysen liefern, wenn die Gruppen nicht hoch definiert sind.

Ich meine, als heuristische Ansätze sind praktische Methoden, die nicht eine optimale gewährleisten können, ist es möglich, dass in jeder wiederholten Analysen können wir verschiedene Lösungen erhalten, wenn es kein klares Optimum gibt, ist es richtig?

Daher möchte ich bestätigen, dass dies für alle heuristischen Ansätze passieren kann.

Vielen Dank im Voraus

Answer 1

Was ist ein heuristischer Ansatz?

Ich würde UPGMA nicht eine Heuristik aufrufen. Es ist eine Definition von Cluster-Ähnlichkeit, und da es eine Definition ist, ist es genau. Aber es kann schwierig sein, das globale Optimum für dieses Problem mit heuristischen Algorithmen zu finden. Genauso wie Lloyds Algorithmus das globale Optimum für k-means nicht finden kann.

Single-Link ist die einzige HAC-Methode, bei der Sie sicherstellen können, dass Sie das Optimum finden, da es darauf hinausläuft, den minimalen Spannbaum zu finden. Dennoch kann die MST nicht eindeutig definiert sein (und dann geben zwei Permutationen desselben Datensatzes nicht das gleiche Ergebnis). Und eine winzige Änderung des Datensatzes (oder z. B. Entfernen oder Hinzufügen eines Punktes) kann eine ganz andere Lösung ergeben. Also würde ich lieber über Stabilität oder Robustheit sprechen. Ich glaube nicht, dass wir einen der Clustering-Algorithmen als "robuste" Statistiken bezeichnen können. Das wahrscheinlich robusteste ist k-median, da der Median bekanntermaßen robuster ist als der Mittelwert.