Ist es möglich, eine algebraische Kurveanpassung mit nur einem einzigen Durchgang der Beispieldaten durchzuführen?

https://stackoverflow.com/questions/1716874

19-09-2019
|

Frage

Ich würde gerne eine machen algebraisch Kurvenanpassung von 2D -Datenpunkten, aber aus verschiedenen Gründen - es ist nicht wirklich möglich, einen Großteil der Beispieldaten gleichzeitig im Speicher zu haben, und das Iterieren durch alles ist ein teurer Prozess.

(Der Grund dafür ist, dass ich eigentlich Tausende von Kurven gleichzeitig auf der Grundlage von Gigabyte von Daten passen muss, die ich ablies und daher slooooooow ist).

Beachten Sie, dass die Anzahl der Polynomkoeffizienten begrenzt ist (möglicherweise 5-10). Eine genaue Anpassung ist daher äußerst unwahrscheinlich, aber dies ist in Ordnung, da ich versuche, ein zugrunde liegendes Muster in Daten mit einem zu finden viel von zufälligem Rauschen. Ich verstehe, wie man einen genetischen Algorithmus verwenden kann, um eine Kurve in einen Datensatz anzupassen, aber dies erfordert viele Durchgänge durch die Beispieldaten und ist daher für meine Anwendung nicht praktisch.

Gibt es eine Möglichkeit, eine Kurve mit einem einzelnen Datenpass anzupassen, in dem der Zustand, der von der Probe zu Probe aufrechterhalten werden muss, minimal ist?

Ich sollte hinzufügen, dass die Art der Daten lautet, dass die Punkte überall auf der x -Achse zwischen 0,0 und 1,0 liegen können, aber die Y -Werte werden immer entweder 1,0 oder 0,0 betragen.

In Java suche ich also nach einer Klasse mit der folgenden Schnittstelle:

public interface CurveFit {
   public void addData(double x, double y);
   public List<Double> getBestFit(); // Returns the polynomial coefficients
}

Die Klasse, die dies implementiert, muss nicht viele Daten in ihren Instanzfeldern behalten, nicht mehr als einen Kilobyte, selbst für Millionen von Datenpunkten. Dies bedeutet, dass Sie die Daten nicht einfach speichern können, da Sie sie später mehrere Pässe durchführen lassen.

bearbeiten: Einige haben vorgeschlagen, dass das Finden einer optimalen Kurve in einem einzigen Pass möglicherweise unmöglich ist, eine optimale Anpassung ist jedoch nicht erforderlich, genauso nah wie wir in einem einzigen Pass erhalten können.

Die nackten Knochen eines Ansatzes könnten sein, wenn wir eine Möglichkeit haben, mit einer Kurve zu beginnen, und dann eine Möglichkeit, ihn zu ändern, um sie bei der Einführung neuer Datenpunkte etwas näher zu bringen - effektiv eine Form des Gradientenabstiegs. Es ist zu hoffen, dass wir mit ausreichenden Daten (und die Daten reichlich sein werden) eine ziemlich gute Kurve erhalten. Vielleicht inspiriert dies jemanden zu einer Lösung.

Lösung 8

Ich glaube, ich habe die Antwort auf meine eigene Frage gefunden, basierend auf einer geänderten Version von Dies Code. Für Interessierte ist mein Java -Code hier.

Andere Tipps

Ja, es ist eine Projektion. Zum

y = X beta + error

Wenn niedrigere Begriffe Vektoren sind und x eine Matrix ist, haben Sie den Lösungsvektor

\hat{beta} = inverse(X'X) X' y

gemäß OLS Seite. Du fast nie Ich möchte dies direkt berechnen, sondern LR-, QR- oder SVD -Zerlegungen verwenden. Referenzen sind in der Statistikliteratur reichlich vorhanden.

Wenn Ihr Problem nur einen Parameter hat (und X ist daher auch ein Vektor), reduziert sich dies auf die Summe von Querprodukten zwischen y und x.

Wenn es Ihnen nichts ausmacht, dass Sie eine geradlinige "Kurve" erhalten, benötigen Sie nur sechs Variablen für eine beliebige Datenmenge. Hier ist der Quellcode, der in mein bevorstehendes Buch eingeht. Ich bin sicher, dass Sie herausfinden können, wie die Datenpunktklasse funktioniert:

Interpolation.h:

#ifndef __INTERPOLATION_H
#define __INTERPOLATION_H

#include "DataPoint.h"

class Interpolation
{
private:
  int m_count;
  double m_sumX;
  double m_sumXX;  /* sum of X*X */
  double m_sumXY;  /* sum of X*Y */
  double m_sumY;
  double m_sumYY;  /* sum of Y*Y */

public:
  Interpolation();

  void addData(const DataPoint& dp);

  double slope() const;
  double intercept() const;

  double interpolate(double x) const;
  double correlate() const;
};

#endif // __INTERPOLATION_H

Interpolation.cpp:

#include <cmath>

#include "Interpolation.h"

Interpolation::Interpolation()
{
  m_count = 0;
  m_sumX = 0.0;
  m_sumXX = 0.0;
  m_sumXY = 0.0;
  m_sumY = 0.0;
  m_sumYY = 0.0;
}

void Interpolation::addData(const DataPoint& dp)
{
  m_count++;
  m_sumX += dp.getX();
  m_sumXX += dp.getX() * dp.getX();
  m_sumXY += dp.getX() * dp.getY();
  m_sumY += dp.getY();
  m_sumYY += dp.getY() * dp.getY();
}

double Interpolation::slope() const
{
  return (m_sumXY - (m_sumX * m_sumY / m_count)) /
    (m_sumXX - (m_sumX * m_sumX / m_count));
}

double Interpolation::intercept() const
{
  return (m_sumY / m_count) - slope() * (m_sumX / m_count);
}


double Interpolation::interpolate(double X) const
{
  return intercept() + slope() * X;
}


double Interpolation::correlate() const
{
  return m_sumXY / sqrt(m_sumXX * m_sumYY);
}

Warum nicht einen Ringpuffer mit einer festen Größe (z. B. den letzten 1000 Punkten) verwenden und eine Standard-Quadrate mit Standard-QR-Zersetzungen an den gepufferten Daten passen? Sobald der Puffer gefüllt ist, ersetzen Sie jedes Mal, wenn Sie einen neuen Punkt erhalten, das älteste und fit. Auf diese Weise haben Sie einen begrenzten Arbeitssatz, der immer noch einige Datenlokalität hat, ohne alle Herausforderungen der Live -Stream -Verarbeitung (maßstabslose).

Beschränken Sie die Anzahl der Polynomkoeffizienten (dh passend zu einer maximalen Leistung von X in Ihrem Polynom)?

Wenn nicht, benötigen Sie keinen "Best Fit" -Algorithmus - Sie können immer genau an ein Polynom von N -Koeffizienten passen.

Verwenden Sie einfach Matrizen, um N -gleichzeitige Gleichungen für n Unbekannte (die N -Koeffizienten des Polynoms) zu lösen.

Wenn Sie eine maximale Anzahl von Koeffizienten einschränken, was ist Ihr Maximum?

Befolgen Sie Ihre Kommentare und bearbeiten:

Was Sie wollen, ist ein Tiefpassfilter, um das Geräusch herauszufiltern und nicht in ein Polynom an das Rauschen zu passen.

Angesichts der Art Ihrer Daten:

Die Punkte können überall auf der x -Achse zwischen 0,0 und 1,0 liegen, aber die Y -Werte betragen immer entweder 1,0 oder 0,0.

Dann brauchen Sie nicht einmal einen einzigen Pass, da diese beiden Zeilen genau durch jeden Punkt gehen:

X = [0,0 ... 1,0], y = 0,0
X = [0,0 ... 1,0], y = 1,0

Zwei kurze Leitungssegmente, Einheitenlänge und jeder Punkt fällt auf die eine oder andere Linie.

Zugegeben, ein Algorithmus, der eine gute Kurve für willkürliche Punkte in einem einzigen Pass findet, ist interessant, aber (basierend auf Ihrer Frage) ist dies nicht das, was Sie brauchen.

Angenommen, Sie wissen nicht, welcher Punkt zu welcher Kurve gehören sollte, so etwas wie a Hough -Transformation könnte liefern, was Sie brauchen.

Die Hough -Transformation ist eine Technik, mit der Sie die Struktur innerhalb eines Datensatzes identifizieren können. Eine Verwendung ist für Computer Vision, wo es eine einfache Identifizierung von Linien und Grenzen im Sichtfeld ermöglicht.

Vorteile für diese Situation:

Jeder Punkt muss nur einmal berücksichtigt werden
Sie müssen keine Datenstruktur für jede Kandidatenlinie aufbewahren, nur eine (komplexe, mehrdimensionale) Struktur
Die Verarbeitung jeder Zeile ist einfach
Sie können an jedem Punkt anhalten und eine Reihe guter Übereinstimmungen ausgeben
Sie verwerfen nie Daten, daher hängt dies nicht auf eine zufällige Lokalität von Referenzen ab
Sie können zwischen Genauigkeit und Gedächtnisanforderungen eingehen
Ist nicht auf genaue Übereinstimmungen beschränkt, wird aber auch teilweise Matches hervorheben.

Ein Ansatz

Um kubische Anpassungen zu finden, bauen Sie einen vierdimensionalen Hough-Raum, in den Sie jeden Ihrer Datenpunkte projizieren würden. Hotspots im Hough -Raum geben Ihnen die Parameter für den Kubikum durch diese Punkte.

Sie benötigen die Lösung für ein überbestimmtes lineares System. Die beliebten Methoden sind normale Gleichungen (normalerweise nicht empfohlen), QR -Faktorisierung und Singularwert -Zersetzung (SVD). Wikipedia hat anständige Erklärungen, Trefethen und Bau ist sehr gut. Deine Optionen:

Out-of-Core-Implementierung über die normalen Gleichungen. Dies erfordert das Produkt A'A wo A hat viel mehr Zeilen als Spalten (also ist das Ergebnis sehr klein). Die Matrix A ist vollständig durch die Beispielstellen definiert A'A ist einigermaßen billig (sehr billig, wenn Sie für die Knotenorte nicht den Speicher treffen müssen). Einmal A'A wird berechnet, Sie erhalten die Lösung in einem Pass durch Ihre Eingabedaten, die Methode kann jedoch instabil sein.
Implementieren Sie eine Out-of-Core-QR-Faktorisierung. Das klassische Gramm-Schmidt wird am schnellsten sein, aber Sie müssen vorsichtig mit der Stabilität sein.
Machen Sie es mit verteiltem Speicher in Kern (wenn Sie die Hardware verfügbar haben). Bibliotheken wie Plapack und Scalapack können dies tun, die Leistung sollte viel besser sein als 1. Die parallele Skalierbarkeit ist nicht fantastisch, wird aber in Ordnung sein, wenn es eine Problemgröße ist, über die Sie sogar in der Serie denken würden.
Verwenden Sie iterative Methoden, um eine SVD zu berechnen. Abhängig von den spektralen Eigenschaften Ihres Systems (möglicherweise nach der Vorkonditionierung) kann dies sehr schnell konvergieren und benötigt keinen Speicher für die Matrix (was in Ihrem Fall 5-10 Spalten von jeweils die Größe Ihrer Eingabedaten enthält. Eine gute Bibliothek Denn dies ist Slepc, Sie müssen nur ein Produkt der Vandermonde -Matrix mit einem Vektor finden (Sie müssen daher nur die Beispielorte speichern). Dies ist parallel sehr skalierbar.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow