Dimensionsreduktion - IsoMap

Einführung

Isomap steht für isometrisches Mapping. Isomap ist eine nichtlineare Dimensionsreduktionsmethode, die auf der Spektraltheorie basiert und versucht, geodätische Distanzen in der niedrigeren Dimension zu erhalten. Es beginnt mit der Erstellung eines Nachbarschaftsnetzwerks, verwendet dann Graph-Distanzen, um die geodätischen Distanzen zwischen allen Punktpaaren zu approximieren, und findet schließlich die niedrigdimensionale Einbettung des Datensatzes durch Eigenwertzerlegung der geodätischen Distanzmatrix.

In nichtlinearen Mannigfaltigkeiten gilt die euklidische Metrik nur, wenn die Nachbarschaftsstruktur als linear angenähert werden kann. Enthält die Nachbarschaft Löcher, können euklidische Distanzen irreführend sein. Die Messung der Distanz entlang der Mannigfaltigkeit liefert eine bessere Annäherung, wie weit zwei Punkte voneinander entfernt sind. Lassen Sie uns dieses Konzept anhand eines einfachen 2D-Beispiels erkunden.

Voraussetzungen für die Dimensionsreduktion

• Erfahrung mit Python-Code und grundlegendes Verständnis von Deep Learning.
• Zugriff auf leistungsstarke Maschinen oder GPUs, die man über Cloud-Anbieter wie DigitalOcean GPU Droplets mieten kann.
• Vertrautheit mit der Einrichtung von Python-Umgebungen und der Ausführung von Tutorials für Anfänger.

Warum geodätische Distanzen für Dimensionsreduktion besser sind

Geodätische Distanzen approximieren Beziehungen in nichtlinearen Mannigfaltigkeiten besser. Punkte, die weit voneinander entfernt sind, wie a und b, werden mit euklidischen Metriken schlecht abgebildet. Geodätische Distanzen hingegen bewahren die lokale und globale Nachbarschaftstreue. Isomap wendet dieses Prinzip an, indem es eine Ähnlichkeitsmatrix für die Eigenwertzerlegung erstellt. Im Gegensatz zu anderen Methoden wie LLE oder LPP verwendet Isomap sowohl lokale als auch globale Informationen für die Abbildung.

Dimensionsreduktion: Schritte des IsoMap-Algorithmus

Nachbarschaftsgraph

Erstellen Sie einen Nachbarschaftsgraphen und eine Adjazenzmatrix aus dem Datensatz. Stellen Sie sicher, dass der resultierende Graph eine einzige zusammenhängende Komponente bildet, um inkohärente Ergebnisse zu vermeiden.

Unähnlichkeitsmatrix

Verwenden Sie die GraphX-Bibliothek von Spark, um geodätische Distanzen zu berechnen. Iterieren Sie über Nachbarschaftsparameter, um einen vollständig verbundenen Graphen zu erhalten. Implementieren Sie kürzeste Pfadberechnungen für gewichtete Graphen mit einer Pregel-ähnlichen API.

      def ShortestPath(Verts, Edges, landmarks): ...
    

Eigenwertzerlegung

Quadratieren Sie die Distanzmatrix und zentrieren Sie sie doppelt, bevor Sie die Eigenwertzerlegung durchführen. Wählen Sie die obersten K Eigenvektoren aus, die den höchsten Eigenwerten entsprechen.

Landmark IsoMap

Landmark IsoMap adressiert die rechnerischen Herausforderungen großer Datensätze, indem es Landmarkenpunkte und klassische MDS darauf angewendet. Übrige Punkte bettet es durch Triangulation ein.

Schwächen von Isomap

Isomap hat Schwierigkeiten, wenn die Mannigfaltigkeit nicht gut abgetastet ist oder Löcher enthält. Die Erstellung von Nachbarschaftsgraphen erfordert eine sorgfältige Parametereinstellung, um schlechte Ergebnisse zu vermeiden.

Fazit zur Dimensionsreduktion

Dieser Artikel führte IsoMap, einen Algorithmus für Mannigfaltigkeitslernen, ein und untersuchte seine Anwendungsfälle und Einschränkungen. Wir diskutierten seine theoretischen Grundlagen, implementierten ihn mit der GraphX-Bibliothek von Spark und hoben seine Vorteile für nichtlineare Dimensionsreduktion hervor.