Filtern eines Datensatzes, um eine gleichmäßigere Verteilung für das Training neuronaler Netze zu erhalten

8

Ich möchte künstliche neuronale Netze (ANN) verwenden, um die Reaktionsgeschwindigkeiten in meiner Flüssigkeit vorherzusagen, anstatt das gesamte System steifer ODEs zu lösen. Einige Leute aus meinem Labor haben bereits daran gearbeitet, damit ich nicht bei Null anfange, sondern Probleme mit meinen Anwendungen habe. Eine davon bezieht sich meiner Meinung nach auf die Qualität meines Datensatzes für das Training. Normalerweise extrahieren wir Trainingsdaten aus CFD-Simulationen, die entweder 1D / 2D / 3D sind. Egal was passiert, wir erhalten ein mehrdimensionales Datenarray, das dem neuronalen Netzwerk zugeführt werden kann. Um Ihnen eine Vorstellung von der Größe des Problems zu geben, möchte ich 8 Netze mit jeweils 10 Eingängen und 1 Ausgang trainieren. Ich denke, ein Trainingssatz von ungefähr 100.000 Punkten wäre vernünftig, aber das Problem ist, dass diese 100.000 Punkte einen bestimmten Bereich meines mehrdimensionalen Raums abdecken müssen.

  • Für jeden Schnappschuss liegt nur ein kleiner Teil der Punkte in der Region, in der ich eine hohe Stichprobe benötige, um sicherzustellen, dass mein Training korrekt ist
  • Wenn ich Schnappschüsse zusammenstelle, erhalte ich viele nahezu doppelte Punkte, die sich (glaube ich) negativ auf mein ANN-Training auswirken, indem a) das Training durch mehr Gewicht auf diese Regionen verzerrt wird, b) unnötige Punkte hinzugefügt werden.

Daher habe ich versucht, die von mir aufgezeichneten Punkte zu filtern, bevor ich sie in mein Trainingsset aufgenommen habe. Aus meiner Sicht bedeutet dies, zu überprüfen, ob sich ein neuer Punkt innerhalb eines bestimmten n-dimensionalen Radius von jedem Punkt meines Datensatzes befindet. Dieser Brute-Force-Ansatz, der bis auf ein paar Tricks wie n ^ 2 skaliert, funktioniert so lala, um 10.000 von 100.000 Punkten zu extrahieren (dauert etwa 30 Minuten), bricht jedoch zusammen, wenn ich die Größe und Anzahl der Schnappschüsse vergrößere ... Klar Es muss einen klügeren Weg geben, aber ich bin mir nicht sicher, in welche Richtung ich anfangen soll. Ich habe es zuerst mit Python versucht und konnte zu FORTRAN wechseln, um die Dinge zu beschleunigen, aber ich denke, ich sollte zuerst nach einer besseren Strategie suchen. Ist meine einzige Hoffnung eine Art KD-Baum? Ich habe wenig bis gar keine Erfahrung mit ihnen und das Problem, das ich sehe, ist, dass mein Baum beim Erstellen meines Datensatzes wächst und dies nur die Komplexität erhöhen kann. Würde eine Python-KD-Baumbibliothek meinen Anforderungen entsprechen? Sollte ich angesichts der Größe meines Problems zu FORTRAN wechseln? Jeder Rat wird geschätzt, danke!

FrenchKheldar
quelle

Antworten:

5

rcrcO(n)rcd3d1rc

rcO(n)O(1)O(1)rc

Der gesamte Vorgang wird hier beschrieben . Wenn Sie weitere Informationen wünschen, googeln Sie nach "Zellenverknüpfte Liste" oder "Zellenliste".

O(log2n)n

Pedro
quelle
Danke, ich werde das untersuchen, obwohl ich befürchte, dass meine Hochdimensionalität ein Hindernis sein könnte. Wenn man d = 10 und ungefähr 100 Punkte pro "Seite" betrachtet (und ich bin nicht sicher, ob dies eine zu niedrige Zahl ist), ist das ein Gitter mit 10 ^ 20 Zellen, nein? Selbst mit 10 Punkten pro "Seite" sind das immer noch 10 ^ 10 Zellen und ich habe 59000 Nachbarn für jede Zelle :) Aber ich werde mir Ihre Links ansehen. Vielen Dank !
FrenchKheldar
Tatsächlich hängt die Anzahl der Zellen von Ihrer Punktdichte im Verhältnis zum Grenzabstand ab. Sie sollten niemals mehr Zellen als Punkte haben! Die Anzahl der Nachbarn ist ein Problem in hohen Dimensionen, aber dann würde ich zu kd-Bäumen wechseln.
Pedro
Ich meinte 59000 benachbarte Zellen, sorry. Ich habe einen gut dokumentierten kdtree-Suchalgorithmus für den nächsten Nachbarn gefunden. Cs.umd.edu/~mount/ANN Ich werde es versuchen .
FrenchKheldar
3

Das von Ihnen angegebene Problem ist ein klassisches Problem in Computational Geometry: Range Queries. Das ist:

Eingabe: eine Teilmenge S des n-dimensionalen euklidischen Raums und eine Menge von Punkten in diesem Raum P.
Ausgabe: die Teilmenge von P, die S schneidet.

O(n11/d+r)O(n)O(n11d+r)O(n)

Der Algorithmus beinhaltet eine Divide and Conquer-Strategie (Rekursion) und eine spezielle Datenstruktur (kd-tree). Hier ist ein Überblick über den Algorithmus:

Begin MainProgram

    results = a new SET   (a kd-tree)
    search(space,root,results)
    return results
endMainProgram

Subroutine search(space,node,results)
    if (space contains node.region) then
        add node.point to the results
        for each descendant of node
            add d.point to results
        return
    if (space contains node.point) then 
        add node.point to results
    if (space extends below node.coordinate) then
        search(space,node.below,results)
    if (space extends above node.coordinate) then
        search(space,node.above,results)
endsubroutine

-Quelle: Algorithmen auf den Punkt gebracht, S. 298

Der Schlüssel zum rechteckigen Fall ist, dass wir die Datenstruktur einfach so definieren können, dass wir eine ganze Teilmenge auf einmal einschließen können ... daher der KD-Baum. Der KD-Baum teilt Ihren n-dimensionalen Raum einfach auf, indem er ihn nacheinander durch Hyperebenen schneidet, ähnlich wie ein 3D-Raum durch Ebenen geteilt werden kann.

Für Ihr spezielles Problem mit Bereichsabfragen in radialer Richtung (keine rechteckigen Kästchen) können Sie möglicherweise eine ähnliche rekursive Raumaufteilung auf der Basis von n Kugeln finden ... Es gibt eine ähnliche Datenstruktur, die als vp-Baum bezeichnet wird zur Implementierung der Raumaufteilung in hyper-sphärischen Koordinaten. Vielleicht möchten Sie sehen

"> diese Veröffentlichung für weitere Details zur Theorie der vp-Bäume.

Natürlich kann das Codieren ein Problem sein, wenn Ihr Ziel wirklich darin besteht, den Algorithmus als Werkzeug für die Durchführung von Wissenschaft zu verwenden. In diesem Fall würde ich vorschlagen, Bibliotheken zu untersuchen, die diese Datenstrukturen, die Sie verwenden können, bereits implementieren. Eine rechnergestützte Geometriebibliothek wäre in dieser Situation sehr nützlich. Die CGAL- Bibliothek verfügt über Unterprogramme für die Suche nach d-dimensionalen Bereichen, die für Sie von Interesse sein können. Hier ist eine weitere Liste von Bibliotheken mit Unterprogrammen für Bereichsabfragen.

Wenn Sie in der Lage sind, die meisten Punkte in dem von Ihnen gesuchten sphärischen Bereich (aber nicht genau alle) zu erhalten, sollten Sie alternativ einen Näherungsalgorithmus wie den in diesem Dokument beschriebenen in Betracht ziehen .

Paul
quelle
@ Gansub: behoben!
Paul