Matching Distanz

Rechner zur Berechnung der topologischen Matching Distanz mit ausführlichen Formeln und Beispielen

Matching Distanz Rechner

Was wird berechnet?

Die Matching Distanz ist eine topologische Metrik zur Messung der Ähnlichkeit zwischen Persistenz-Diagrammen. Sie wird in der Topological Data Analysis (TDA) verwendet.

Eingabedaten

Werte durch Leerzeichen getrennt

Gleiche Anzahl Werte wie X

Ergebnis
Matching Distanz:
Topologische Distanz für Persistenz-Diagramme

Matching Info

Eigenschaften

Matching Distanz:

  • Topologische Metrik
  • Für Persistenz-Diagramme
  • Optimal matching basiert
  • Bottleneck-Distanz verwandt

TDA: Fundamental für Topological Data Analysis zur Analyse der "Form" von Daten.

Anwendungen
Formanalyse:
Topologische Eigenschaften von Daten
Bildverarbeitung:
Strukturelle Ähnlichkeiten
Netzwerkanalyse:
Topologische Netzwerkvergleiche
Verwandte Konzepte

Bottleneck Distanz: Verwandte TDA-Metrik
Wasserstein Distanz: Optimaler Transport
Persistenz Homologie: Grundlagen

Formeln der Matching Distanz

Grunddefinition
\[d_M(X,Y) = \inf_{\phi} \max_{x \in X} d(x, \phi(x))\] Optimales Matching φ
Persistenz-Diagramme
\[d_M(D_1, D_2) = \inf_{\eta} \|\eta\|_\infty\] Über alle Bijektionen η
Bottleneck Form
\[d_B(X,Y) = \inf_{\gamma} \sup_{x \in X} d(x, \gamma(x))\] Bottleneck-Distanz
Partielle Matching
\[d_{PM}(X,Y) = \min(\text{cost}(\text{match}) + \delta \cdot |\text{unmatched}|)\] Mit Strafterm δ
Wasserstein-p
\[W_p(X,Y) = \left(\inf_{\gamma} \int d(x,\gamma(x))^p d\mu(x)\right)^{1/p}\] Wasserstein p-Distanz
Stabilität
\[d_M(D_f, D_g) \leq \|f - g\|_\infty\] Stabilitätssatz

Topological Data Analysis (TDA)

Grundkonzepte der TDA

Persistenz-Homologie:

Erfasst topologische Eigenschaften (Löcher, Hohlräume) von Daten über verschiedene Skalen hinweg.

Persistenz-Diagramm:

Visualisierung der Persistenz als Punkte (birth, death) in der Ebene.

Simplicial Complex:

Mathematische Struktur zur Darstellung von Datenformen durch Simplices (Punkte, Kanten, Dreiecke).

Filtration:

Sequenz von Komplexen, die die Datenstruktur bei verschiedenen Auflösungen zeigt.

Beispiel: Punkt-Wolken Matching

Beispiel: Matching zweier Punkt-Wolken

Punkt-Wolke A:



Koordinaten: [(1,2), (3,1), (2,3), (4,2)]

Punkt-Wolke B:



Koordinaten: [(1.1,2.1), (2.9,1.1), (2.1,2.9)]

Optimales Matching:

Matching-Kosten: max(0.14, 0.14, 0.14, ∞) für ungematchten Punkt
Matching Distanz ≈ 0.14 (ohne Strafterm für ungematchten Punkt)

Interpretation: Die Matching-Distanz erfasst die beste Übereinstimmung zwischen den Strukturen.

Praktische Anwendungen

Bildverarbeitung
  • Formenerkennung
  • Objektvergleich
  • Medizinische Bildanalyse
  • Strukturelle Ähnlichkeit
Bioinformatik
  • Proteinstruktur-Vergleich
  • Phylogenetische Analyse
  • Molekülform-Analyse
  • Evolutionäre Distanzen
Netzwerkanalyse
  • Soziale Netzwerke
  • Biologische Netzwerke
  • Topologische Robustheit
  • Netzwerk-Evolution

Mathematische Eigenschaften

Metrische Eigenschaften
  • Nicht-Negativität: d_M(X,Y) ≥ 0
  • Symmetrie: d_M(X,Y) = d_M(Y,X)
  • Identität: d_M(X,X) = 0
  • Dreiecksungleichung: d_M(X,Z) ≤ d_M(X,Y) + d_M(Y,Z)
Topologische Eigenschaften
  • Stabilität: Robust gegen Störungen
  • Isometrie-Invarianz: Unveränderlich unter Isometrien
  • Filtration-kompatibel: Respektiert Filtrations-Strukturen
  • Approximierbar: Effizient berechenbar
Stabilitätssatz

Hauptresultat: Die Matching-Distanz ist stabil bezüglich Funktionsstörungen

Bedeutung: Kleine Änderungen in den Daten führen zu kleinen Änderungen in der Distanz

Algorithmische Aspekte

Berechnung der Matching Distanz

Exakte Algorithmen:

  • Hungarian Algorithm: O(n³) für bipartites Matching
  • Geometric Matching: Speziell für geometrische Probleme
  • Linear Programming: Allgemeine Formulierung

Approximationsalgorithmen:

  • Heuristische Methoden: Schnelle Näherungen
  • Sampling-basiert: Für große Datensätze
  • GPU-Beschleunigung: Parallele Implementierungen
Software und Tools

TDA Libraries: GUDHI, Dionysus, javaPlex, TDA-Mapper

Programmiersprachen: Python (scikit-tda), R (TDA), C++ (CGAL)

Verwandte Distanzen

Andere topologische Distanzen

Bottleneck-Distanz:

Spezialfall der Matching-Distanz für Persistenz-Diagramme. Misst die größte notwendige Bewegung.

Wasserstein-Distanz:

Optimaler Transport zwischen Persistenz-Diagrammen. Berücksichtigt die Gesamtkosten der Bewegung.

Interleaving-Distanz:

Kategorie-theoretische Distanz zwischen Filtrationen. Fundamentaler für TDA-Theorie.

Weiterführende Literatur

Empfohlene Quellen

Grundlagen:

Angewandte TDA:

  • Topological Data Analysis (Wasserman)
  • Persistence Theory (Cohen-Steiner et al.)
  • Applied Topology (Ghrist)

Distanz Funktionen

Bray Curtis Distanz  •  Canberra Distanz  •  Euklidischer Abstand  •  Korrelationskoeffizient  •  Kosinus Ähnlichkeit  •  Levenshtein Distanz  •  Manhattan Distanz  •  Minkowski Distanz  •  Maximumsnorm  •