Topologische Analyse großer Datenmengen ist diesen Monat das Thema im monatlichen Mathe-Essay der AMS: Finding holes in data

Worum es geht: Man hat eine Menge von Daten, die durch irgendwelche Zahlentupel dargestellt werden. Die Punktwolke unten zeigt Daten, die einfach Zahlenpaare sind und sich demzufolge als Punkte in der 2-dimensionalen Ebene repräsentieren lassen. In der Regel werden die Daten aber natürlich aus mehr als nur 2 Zahlenwerten bestehen und dementsprechend wird man sie dann auch nicht in der 2-dimensionalen Ebene, sondern in einem höherdimensionalen Raum darstellen.

IMG_0459
Bei dem Bild oben fällt auf, dass es die Punktwolke sich um einen Kreis herum zu häufen scheint.

Bei der persistenten Homologie geht es genau darum, einen formalen Zugang zu einem solchen Phänomen (“die Punktwolke häuft sich um einen Kreis herum”) zu finden. Die formale Definition findet man im Artikel gut beschrieben. Für Topologen kurz zusammengefasst: aus der Punktwolke baut man einen Simplizialkomplex indem man (zu einem festen ε) alle Simplizes hinzufügt, deren Ecken paarweise Abstand kleiner ε haben. Das gibt zu jedem ε einen Simplizialkomplex Xε mit Homologiegruppen H*(Xε) und man kann für ε<ε' schauen, was das Bild von H*(Xε) in H*(Xε’) ist. Aus diesen Informationen gewinnt man den sogenannten “Barcode” der peristenten Homologie.

IMG_0458

Als Beispiel wird dann eine Arbeit von Carlsson, Ishkhanov, de Silva und Zomorodian “On the local behavior of spaces of natural images” besprochen, die die in Naturphotos vorkommenden 3×3-Pixel analysiert. (Mathematisch liegen die Helligkeitswerte der 3×3-Pixel in einem 9-dimensionalen Raum, mit zwei Normalisierungen kann man annehmen, dass sie in einer 7-dimensionalen Sphäre liegen.)

Die Autoren nahmen eine Datenbank mit 4167 Photos und analysierten eine Auswahl von insgesamt 4 Millionen in diesen Photos vorkommenden 3×3-Pixel. (Man braucht wohl nicht begründen, warum nur 3×3-Pixel statt der aus 1532×1020 Pixeln bestehenden Gesamtbilder analysiert wurden. Die Auswahl der 4 Millionen 3×3-Pixel war nicht bloß zufällig, es wurden nur solche mit stärkeren Kontrasten ausgewählt.)

Die Analyse zeigt letztlich, dass die Helligkeitswerte sich um eine (in der 7-dimensionalen Sphäre liegende) Kleinsche Flasche herum häufen. Die Erklärung dafür findet man in Kapitel 7 der unten verlinkten Arbeit. Sicherlich ein überraschendes Vorkommen der Kleinschen Flasche in der “Natur”.

Carlsson, G., Ishkhanov, T., de Silva, V., & Zomorodian, A. (2007). On the Local Behavior of Spaces of Natural Images International Journal of Computer Vision, 76 (1), 1-12 DOI: 10.1007/s11263-007-0056-x

Kommentare (8)

  1. #1 tomtoo
    20. Dezember 2016

    @thilo
    Sry doofe frage halt mal wieder.
    Aber bei diesen Naturaufnahmen könnte sich die resultierende Toplogie aus ihrer Fraktalen Natur ergeben ?

  2. #2 Czentovic
    20. Dezember 2016

    Musstest Du für den Artikel bezahlen?

  3. #3 Thilo
    20. Dezember 2016

    Nein, aber wahrscheinlich ist er nicht überall frei zugänglich. Eine frei zugängliche Version ist hier: http://math.uchicago.edu/~shmuel/AAT-readings/Data%20Analysis%20/mumford-carlsson%20et%20al.pdf

  4. #4 Thilo
    20. Dezember 2016

    @tomtoo: Das wäre jetzt ein weites Feld, wieweit die Verteilung der Helligkeitskontraste solcher Pixel von der fraktalen Struktur abhängt. Keine Ahnung.

  5. #5 Dr. Webbaer
    20. Dezember 2016

    Bildersuche im Internet, Gesichtserkennung etc. fallen hier als topologische Anwendungen -die Topologie könnte insofern dank Web wichtiger geworden sein, wie auch im dankenswerterweise (doppelt) bereit gestellten Webverweis angedeutet- ein.
    Insofern keine schlechte Nachricht, jedenfalls für Sie, Herr Dr. Kuessner.

    Ansonsten müsste hier Datenhomogenisierung vorliegen, grundsätzlich ein “heißes Eisen”, aber bei den oben skizzierten Anwendungen eher nicht.

    BTW, spiel(t)en Topologen eigentlich bei der Entwicklung von Computerspielen [1] eine Rolle, auch sog. Physics-Engines meinend?

    MFG + schöne Weihnachtstage in SK,
    Dr. Webbaer

    [1]
    ‘Doom’ und ‘Counterstrike’ und so, die CS-Physics-Engine ist seinerzeit, also vor ca. 20 Jahren, sehr gelobt worden und wird wohl auch bis heute weiter gepflegt.

  6. #6 tomtoo
    24. Dezember 2016

    @Thilo
    Ich wünsch dir ein frohes Fest.

    Aber immer wenn ich denke ich hätte wenigstens so ein winzig, kleines bischen verstanden was Mathematiker so denken. Werde ich mir in Zukunft den Artikel nochmal durchlesen. Weil dann, bin ich mir absolut sicher, das ich absolut keinen Plan habe.
    Aber ist ok. 😉

  7. #7 Frank
    Bellem
    25. Dezember 2016

    Allen Freunden dieses Blogs (Den Anderen natürlich auch…), wünsche ich schöne Feiertage und ein gutes neues Jahr.
    Frank

  8. […] Beitrag Löcher in Daten hat Thilo Kuessner auf einen Artikel von Gunnar Carlsson et al. hingewiesen. Diese Mathematiker […]