Passen Sie stückweise lineare Daten an

Was ist eine robuste Methode, um stückweise lineare, aber verrauschte Daten anzupassen?

Ich messe ein Signal, das aus mehreren fast linearen Segmenten besteht. Ich würde gerne mehrere Zeilen automatisch an die Daten anpassen, um die Übergänge zu erkennen.

Der Datensatz besteht aus einigen tausend Punkten mit 1-10 Segmenten und ich kenne die Anzahl der Segmente.

Dies ist ein Beispiel dafür, was ich automatisch tun möchte.

Ich habe zwei Ansätze versucht, naiv (mit nur 3 Segmenten). Sicherlich würde es ausgefallenere Methoden geben.

RANSAC, soll ein robuster Passmechanismus sein. Es ist einfach, den Algorithmus nach einer Reihe von Segmenten zu stoppen. Es kann jedoch schwierig sein, die Kontinuität zwischen Segmenten - wie in Ihrer Anwendung erforderlich - zumindest mit einer einfachen Implementierung zu erzwingen. Als Proof of Concept habe ich aus den Datenpunkten ein Bild erstellt, damit ich die in , der von Mathematica, verfügbare RANSAC-Engine verwenden kann.$ImageLines$

Passen Sie ein stückweise lineares Modell mit einem universellen Minimierer an. Es ist einfach, die Kontinuität von Segmenten durchzusetzen. Interessanterweise kann das Testen auf Residuen und andere Eigenschaften genügend Informationen liefern, um die Anzahl der Segmente automatisch zu bestimmen - ich habe es jedoch nicht ausprobiert. So sieht es in Mathematica aus:

Ich behaupte nicht, dass die folgende Methode robust ist, aber sie könnte für Sie funktionieren. Gehen Sie mit Tausenden von Punkten und vielleicht zehn oder mehr geraden Segmenten wie folgt vor.$x[n]$

• Verarbeiten Sie die Punkte , um ein Bit-Array wie folgt zu erstellen . Herey [ n ] y [ n ] = { 1 , wenn | ( x [ n + 1 ] - x [ n ] ) - ( x [ n ] - x [ n - 1 ] ) | < ϵ , 0 , $x[n]$$y[n]$

  $$y[n] = \begin{cases}1, &\text{if} ~ |(x[n+1]-x[n]) - (x[n]-x[n-1])| < \epsilon,\\ 0, &\text{otherwise.}\end{cases}$$ $\epsilon$$x[n-1],x[n], x[n+1]$$(n-1, x[n-1])$$(n,x[n])$$(n,x[n])$$(n+1,x[n+1])$

• $y[n]$$1$$0$$1$$1$$\epsilon$

• $y[n]$$x[3]$$x[88]$$x[94]$$x[120]$$x[129]$$\cdots$, und so weiter. Ziehen Sie A nach rechts und B nach links, um herauszufinden, wo sie sich schneiden. Verlängern Sie B nach rechts und C nach links, um herauszufinden, wo sie sich schneiden usw. Herzlichen Glückwunsch, Sie haben jetzt ein kontinuierliches und stückweise lineares Modell für Ihre Daten.

(Jahre später) stückweise lineare Funktionen sind Splines vom Grad 1, was die meisten Spline-Monteure tun müssen. scipy.interpolate.UnivariateSpline kann zum Beispiel mit k=1 einem Glättungsparameter ausgeführt werden s, mit dem Sie spielen müssen - siehe scipy-interpolation-with-univariate-splines .
In Matlab erfahren Sie, wie man Knoten auswählt .

Hinzugefügt: optimale Knoten zu finden ist nicht einfach, da es viele lokale Optima geben kann. Stattdessen geben Sie UnivariateSpline ein Ziel s, eine Fehlersumme ^ 2, und lassen es die Anzahl der Knoten bestimmen. Nach dem Anpassen get_residual()wird die tatsächliche Summe aus Fehler ^ 2 und get_knots()den Knoten ermittelt. Eine kleine Änderung in skann die Knoten stark verändern, insbesondere bei starkem Rauschen (ymmv).
Das Diagramm zeigt Anpassungen an eine zufällige stückweise lineare Funktion + Rauschen für verschiedene s.

Informationen zum Anpassen stückweiser Konstanten finden Sie unter Schritterkennung . Kann das für pw linear verwendet werden? Weiß nicht; Wenn Sie mit der Unterscheidung von verrauschten Daten beginnen, wird das Rauschen erhöht.

Andere Testfunktionen und / oder Links zu Dokumenten oder Code wären willkommen. Ein paar Links:
stückweise-lineare-Regression-mit-Knoten-als-Parametern
$\qquad$Lineare Splines reagieren sehr empfindlich darauf, wo die Knoten platziert werden.
Knotenauswahl für kubische Regressions-Splines
$\qquad$ Dies ist ein heikles Problem und die meisten Leute wählen die Knoten einfach durch Ausprobieren aus.
$\qquad$ Ein Ansatz, der immer beliebter wird, ist die Verwendung von bestraften Regressionssplines.

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

Dynamisches Programmieren ist sehr clever, aber kann es Brute Force + Heuristik für diese Aufgabe übertreffen?
Siehe das hervorragende Skriptum von Erik Demaine unter MIT 6,006 Intro zu Algorithmen
auch google segmentiert lineare Regression
auch John Henry - Syndrom.

Nehmen Sie die Ableitung und suchen Sie nach Bereichen mit nahezu konstantem Wert. Sie müssten den Algorithmus erstellen, um nach Bereichen mit einer idealen Neigung von +/- zu suchen. Dadurch erhalten Sie die Neigung der Linie für diesen Abschnitt. Möglicherweise möchten Sie vor der Schnittklassifizierung eine Glättung durchführen, z. B. einen gleitenden Mittelwert. Der nächste Schritt wäre, den y-Schnittpunkt zu erhalten, der an diesem Punkt trivial sein sollte.

Die Verwendung eines l1-Trendfilters ist eine weitere Idee:

Papier

Online-Beispiel