Eine metrische Distanzfunktion entspricht dem kürzesten Weg durch einen Datenraum. Bei einfachen Metriken wird die inhärente Struktur der Daten einfach vernachlässigt. Beispielsweise ergibt der euklidische Abstand immer eine gerade Linie.
Wir betrachten nun die Struktur, die sich aus den Datenpunkten selbst ergibt, und ignorieren sie nicht einfach. Dazu verwenden wir einen Satz aus der Informationstheorie. Der gesuchte Abstand stimmt lokal mit dem euklidischen Abstand überein. Umgekehrt gilt: Je stärker der euklidische Abstand verzerrt ist, desto weiter sind zwei Datenpunkte voneinander entfernt. Dieses Phänomen ist als Satz von Bourgain bekannt und entspricht in der Algebra der Approximation einer Funktion durch eine Gerade. In der Nähe der angelegten Tangente ist die Schätzung noch gut, weiter entfernt verursacht die Linearisierung große Abweichungen.
In diesem Zusammenhang folgt, dass ein Datenraum mit beliebiger Metrik immer in einen euklidischen Raum eingebettet werden kann, wenn nur die örtlichen Liegenschaften sollen erhalten bleiben. Theoretisch können diese lokalen Eigenschaften fortlaufend addiert werden, um einen globalen Abstand zu ermitteln, der dann ungefähr dem gesuchten Abstand entspricht, als ob ein Spline aus kleinen, geraden Abschnitten zusammengesetzt oder das Bogenmaß ermittelt wird.
Da Wenn wir nach der kürzesten Entfernung suchen, können wir sie ermitteln, indem wir zunächst einen KNN-Graphen mit euklidischen Metriken für die Datenpunkte erstellen und dann den Dijkstra-Algorithmus verwenden, um den kürzesten Weg durch den Graphen zu finden. Über diesen kürzesten Weg werden dann die lokalen Distanzen zur globalen Distanz addiert.
Das wollen wir allerdings nicht direkt machen, da der Dijkstra-Algorithmus aufgrund seiner hohen Komplexität in der Anzahl der möglichen Datenpunkte sehr begrenzt ist. Dazu passen wir zunächst ein Kohonen-Netz oder eine Mannigfaltigkeit in den Datenraum ein. Auf diese Weise können nahezu beliebig große Datensätze berücksichtigt werden. Der Dijkstra Shortest Path wird nun anhand des virtuellen Kohonen-Netzes anstelle der realen Datenpunkte berechnet.
Für eine globale Einbettung sollte noch definiert werden, wie genau die Datenstruktur beeinflusst werden soll.
Im unten gezeigten Beispieldiagramm führt der kürzeste Weg durch den Bereich mit der geringsten Dichte, als würde er sich hier besonders schnell bewegen, oder umgekehrt, als wäre er bei hoher Dichte irgendwie blockiert. Dies kann auch schnell dazu führen, dass ein Raum mit Leere durchquert wird, der jedoch eigentlich einer Beschränkung unterliegt und daher nicht durchdrungen werden sollte. Im Grenzfall wird somit wieder der euklidische Abstand erreicht.
Um ihn robuster zu machen, kann der Datenraum vor der Anwendung des Kürzestpfad-Algorithmus künstlich verdichtet werden .
Eine weitere Möglichkeit ist eine physikalisch oder quantenmechanisch motivierte Gewichtung. Analog dazu betrachten wir den Weg eines Photons oder Elektrons bzw. dessen Wahrscheinlichkeitsamplitude von einem Ort zum anderen durch ein Widerstands- oder Wahrscheinlichkeitsnetzwerk.
Das Teilchen nimmt nun quasi beliebige Wege, von denen alle zunächst gleich weit entfernt sind weg. Die Wahrscheinlichkeiten der Laufzeit ähnlicher Pfade stabilisieren sich jedoch gegenseitig zu einem Pfad, der den effektivsten und damit kürzesten Pfad darstellt. Umwege oder breite Pfade hingegen heben sich aufgrund ihres symmetrischen Gegenstücks statistisch in der Wahrscheinlichkeitsamplitude auf.
In unendlichen Simulationen eines Zufallswegs von A nach B ist ein Pfad durch den niedrigsten ( (optische) Dichte tritt seltener auf als ein Pfad durch die höchste Dichte. Eine hohe Dichte führt zu einem wahrscheinlicheren Pfad und eine niedrige Dichte zu einem weniger wahrscheinlichen Pfad.
Dieses Phänomen kann (ohne die vielen Zufallswanderungen) simuliert werden, indem der KNN-Graph oder das virtuelle Kohonen-Netz mit a ausgedünnt wird spezieller Algorithmus, sodass die Abstände durch das Netz aus allen Richtungen gleich bleiben. Für jede weggelassene Distanz wird eine andere Distanz addiert, so dass die Wahrscheinlichkeit entweder in zwei gleiche Verbindungen gleicher Teile aufgeteilt wird oder als ein Teil in einer doppelt so langen Verbindung durchgegangen wird. (2*0,1 -> 1*0,2)
Was bedeuten die Ergebnisse in der Praxis?
Wenn es keine Annahme dafür gibt Als Metrik kann der Kohonen-Abstand direkt in einer dieser Versionen verwendet werden. Die Berechnung eines Kohonen-Distanzmodells ist unkompliziert und auch die Berechnung von Distanzen mit diesen Modellen ist unkompliziert.
Das Verfahren kann auch verwendet werden, um numerisch zu überprüfen, wie verzerrt die Annahme einer euklidischen Metrik für einen Datensatz ist . Wenn diese nicht groß ist, kann genauso gut die euklidische Metrik verwendet werden. Die Verzerrung der oben gezeigten Beispiele beträgt 100 %, 104 %, 113 % und 117 %.
Die folgenden Abbildungen zeigen Beispiele der Verzerrung für die NRAIA-Datensätze mit unterschiedlicher Anzahl von Dimensionen.
BOD2: Ergebnis der Verzerrungsschätzung 2,3 %
Chlorid: Verzerrungsschätzungsergebnis 15 %
Blätter: Verzerrungsschätzungsergebnis 11 %
Lipo: Verzerrungsschätzungsergebnis 6 %
Rumford: Ergebnis der Verzerrungsschätzung 3 %
Sacch2: Verzerrungsschätzungsergebnis 8 %
PCB: Ergebnis der Verzerrungsschätzung 22 %
Ethyl: Ergebnis der Verzerrungsschätzung 15 %
Schmiermittel: Verzerrungsschätzungsergebnis 16 %
Nitrit: Verzerrungsschätzungsergebnis 15 %
Saccharin: Verzerrungsschätzungsergebnis 3 %
Isom: Verzerrungsschätzungsergebnis 45 %
O.xylol: Verzerrungsschätzungsergebnis 18 %
Ölschiefer: Verzerrungsschätzungsergebnis 41 %
Pinen: Verzerrungsschätzungsergebnis 8 %
Kohle: Verzerrungsschätzungsergebnis 31 %
Die Berechnungsverzerrung selbst ist quantitativ und hilft bei der Betrachtung großer Datenmengen, da sie ein Maß für die Nichtlinearität des Datensatzes ist. Im Beispieldatensatz wurden zur Veranschaulichung 2D-Punkte ausgewählt. Die Methode funktioniert jedoch für numerische Datensätze beliebiger Komplexität, beispielsweise auch Bilder. Neben der Schätzung der intrinsischen Dimensionalität (https://panda.technology/en/entropy) hilft auch die Kenntnis der Nichtlinearität Wählen Sie einen geeigneten Feature-Encoder aus, um die Dimensionalität zu reduzieren. Beides sind skalare Eigenschaften eines metrischen Raums. Diese skalaren Werte können verwendet werden, um Datensätze mithilfe des Konzepts metrischer Räume zu vergleichen oder um Änderungen in einem Raum zu erkennen.
Solche informationstheoretisch motivierten Aggregationen entsprechen in etwa den Konzept der Entropie oder kinetischen Energie (oder Temperatur) in der Physik, mit dem komplexe Strukturen einfach als Zustände beschrieben werden können.
Und dies ist auch der offensichtlichste praktische Fall, die Zustandsüberwachung an beliebig komplexen und unbekannten Daten setzt.
Wenn also eine Bildaufnahme oder eine mechanische Schwingung im Laufe der Zeit eine Zunahme der Dimensionalität oder Nichtlinearität zeigt, ist dies ein wichtiges Warnsignal.
Daher ist mit diesem Konzept ein eine automatische Zustandsüberwachung möglich.
