Wie kann ich programmgesteuert Segmente einer Datenreihe erkennen, um sie an verschiedene Kurven anzupassen?

14

Gibt es dokumentierte Algorithmen, um Abschnitte eines bestimmten Datensatzes in verschiedene Kurven mit der besten Anpassung zu unterteilen?

Zum Beispiel würden die meisten Menschen, die diese Datentabelle betrachten, sie leicht in drei Teile aufteilen: ein sinusförmiges Segment, ein lineares Segment und das inverse exponentielle Segment. Tatsächlich habe ich dieses mit einer Sinuswelle, einer Linie und einer einfachen Exponentialformel gemacht.

Diagramm der Daten mit drei verschiedenen sichtbaren Teilen

Gibt es Algorithmen zum Auffinden solcher Teile, die dann separat an verschiedene Kurven / Linien angepasst werden können, um eine Art zusammengesetzte Serie von Best-Fits von Teilmengen der Daten zu erstellen?

Beachten Sie, dass im Beispiel zwar die Enden der Segmente so gut wie in einer Reihe stehen, dies jedoch nicht unbedingt der Fall sein muss. Es kann auch zu einem plötzlichen Ruck in den Werten bei einer Segmentabschaltung kommen. Vielleicht sind diese Fälle leichter zu erkennen.

Update: Hier ist ein Bild eines kleinen Teils der realen Daten: Reale Weltkarte

Update 2: Hier ist ein ungewöhnlich kleiner realer Datensatz (nur 509 Datenpunkte):

4,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235

Hier ist die ungefähre Position einiger bekannter realer Elementkanten, die mit gepunkteten Linien markiert sind, ein Luxus, den wir normalerweise nicht haben werden:

Bildbeschreibung hier eingeben

Ein Luxus, den wir jedoch haben, ist im Nachhinein: Die Daten in meinem Fall sind keine Zeitreihen, sondern eher räumlich verwandt; Es ist nur sinnvoll, einen gesamten Datensatz (normalerweise 5000 - 15000 Datenpunkte) auf einmal zu analysieren, und nicht fortlaufend.

Whybird
quelle
1
ps erster Beitrag zum Lebenslauf; Ich bin ein Softwareentwickler und ich halte normalerweise SO mehr aus. Entschuldigung, wenn ich gegen lokale Tabus verstoßen habe. Viele meiner Suchen nach Antworten führten hierher, daher dachte ich, dies wäre der beste Ort, um zu fragen.
Whybird
Warum posten Sie die Daten nicht und ich werde versuchen, Ihre Frage anhand eines Beispiels zu beantworten.
IrishStat
Eine Möglichkeit wäre, die gesamte Kurvenfamilie mit einem Metamodell auf einmal anzupassen. Nehmen Sie an, Sie möchten das Histogramm beispielsweise mit einem KDE glätten, um es genauer zu machen. Dann wird Ihre glatte Schätzung von KDE genauer, wenn Sie ein Modell verwenden, bei dem die Breite des Kernels über den Wertebereich von variieren darfx
1
Sie haben das Beispiel so konstruiert, dass die Idee Sinn macht: So weit, so gut. Bei realen Histogrammen ist es viel häufiger, dass eine komplizierte Form eine Mischung aus überlappenden Verteilungen widerspiegelt: Es geht dann nicht um Änderungspunkte des beobachteten Histogramms, die im Allgemeinen nicht überzeugend existieren oder nicht die richtige Art sind, über Mischungen nachzudenken. Es ist jedoch möglich, dass Sie das "Histogramm" auf eine viel breitere Art und Weise verwenden als es in der Statistikwissenschaft üblich ist. Dabei handelt es sich (nur) um ein Balkendiagramm der Häufigkeit oder der Wahrscheinlichkeitsverteilung.
Nick Cox
@IrishStat - Die üblichen Datensätze haben 5000 bis 15000 Einträge. Ich habe versucht, hier eine Zusammenfassung der wahren Umstände zu erstellen, aber es stellte sich als schlechtes Beispiel heraus, und ich musste von vorne anfangen. Auf der anderen Seite hat mir dies eine teilweise Antwort in Form von Glätten und Mitteln von Datenklumpen für die anfängliche Suche nach Mustern nahegelegt, um später verfeinert zu werden. Danke dafür sieht so aus, als könnte es gut sein; Ich werde das zu der Frage hinzufügen, wenn ich kann.
Whybird

Antworten:

2

Meine Interpretation der Frage ist, dass das OP nach Methoden sucht, die zu den Formen der angegebenen Beispiele passen, nicht zu den HAC-Residuen. Darüber hinaus sind automatisierte Routinen erwünscht, die keine nennenswerten Eingriffe von Menschen oder Analysten erfordern. Box-Jenkins sind trotz ihrer Betonung in diesem Thread möglicherweise nicht geeignet, da sie eine erhebliche Beteiligung von Analysten erfordern.

Es gibt R-Module für diese Art von nicht momentbasiertem Pattern Matching. Permutationsverteilungsclustering ist ein solches Mustervergleichsverfahren, das von einem Wissenschaftler des Max-Planck-Instituts entwickelt wurde und die von Ihnen genannten Kriterien erfüllt. Ihre Anwendung betrifft Zeitreihendaten, ist aber nicht darauf beschränkt. Hier ist ein Zitat für das R-Modul, das entwickelt wurde:

pdc: Ein R-Paket zum komplexitätsbasierten Clustering von Zeitreihen von Andreas Brandmaier

Neben PDC gibt es das maschinelle Lernen, die von Eamon Keogh an der UC Irvine entwickelte iSax-Routine, die ebenfalls einen Vergleich wert ist.

Schließlich gibt es dieses Papier über Data Smashing: Aufdecken der lauernden Ordnung in Datenvon Chattopadhyay und Lipson. Über den cleveren Titel hinaus gibt es einen ernsthaften Zweck bei der Arbeit. Hier die Zusammenfassung: "Von der automatischen Spracherkennung bis zur Entdeckung ungewöhnlicher Sterne: Fast alle automatisierten Entdeckungsaufgaben beruhen auf der Fähigkeit, Datenströme miteinander zu vergleichen und gegenüberzustellen, Verbindungen zu identifizieren und Ausreißer zu erkennen. Trotz der Verbreitung von Daten sind jedoch automatisierte Methoden erforderlich Ein wesentlicher Engpass besteht darin, dass die meisten Datenvergleichsalgorithmen heutzutage von einem Experten ausgeführt werden, um zu bestimmen, welche "Merkmale" der Daten für den Vergleich relevant sind. Hier schlagen wir ein neues Prinzip zur Schätzung der Ähnlichkeit zwischen den Quellen willkürlicher Daten vor Datenströme, bei denen weder Domänenwissen noch Lernen zum Einsatz kommen. Wir demonstrieren die Anwendung dieses Prinzips auf die Analyse von Daten aus einer Reihe von realen, herausfordernden Problemen. einschließlich der Disambiguierung von elektroenzephalografischen Mustern im Zusammenhang mit epileptischen Anfällen, der Erkennung anomaler Herzaktivität anhand von Herztonaufzeichnungen und der Klassifizierung astronomischer Objekte anhand der Rohphotometrie. In all diesen Fällen und ohne Zugriff auf Domänenwissen zeigen wir eine Leistung, die der Genauigkeit von speziellen Algorithmen und Heuristiken entspricht, die von Domänenexperten entwickelt wurden. Wir schlagen vor, dass Data Smashing-Prinzipien die Tür zum Verständnis immer komplexerer Beobachtungen öffnen können, insbesondere wenn Experten nicht wissen, wonach sie suchen sollen. " In all diesen Fällen und ohne Zugriff auf Domänenwissen zeigen wir eine Leistung, die der Genauigkeit von speziellen Algorithmen und Heuristiken entspricht, die von Domänenexperten entwickelt wurden. Wir schlagen vor, dass Data Smashing-Prinzipien die Tür zum Verständnis immer komplexerer Beobachtungen öffnen können, insbesondere wenn Experten nicht wissen, wonach sie suchen sollen. " In all diesen Fällen und ohne Zugriff auf Domänenwissen zeigen wir eine Leistung, die der Genauigkeit von speziellen Algorithmen und Heuristiken entspricht, die von Domänenexperten entwickelt wurden. Wir schlagen vor, dass Data Smashing-Prinzipien die Tür zum Verständnis immer komplexerer Beobachtungen öffnen können, insbesondere wenn Experten nicht wissen, wonach sie suchen sollen. "

Dieser Ansatz geht weit über die krummlinige Anpassung hinaus. Es lohnt sich auszuprobieren.

Mike Hunter
quelle
Vielen Dank - Sie haben Recht, ich möchte Cluster automatisch finden, ohne dass der Analyst eingreift. Für das, was ich tun möchte, muss ich Datensätze von 5000-15000 Datenpunkten in Cluster aufteilen, die jeweils einfachen Formeln (einschließlich sich wiederholender Formeln) gut entsprechen, ohne dass ein menschliches Eingreifen über Gruppen von etwa 50000 solcher Datensätze in einem tolerierbaren Zeitrahmen erfolgt von Menschen auf heimischer Computerhardware.
Whybird
Was die Kurve betrifft, die zu jedem Cluster passt, ist es meiner Meinung nach einfach genug, wenn ich die Grenzen mit welchen Mitteln erkannt habe, verschiedene Modelle (Sinuswelle, Polynom, Exponential) auszuprobieren und zu sehen, welche ein besseres gewöhnliches r ^ 2 ergeben.
Whybird
2
OK, ich denke, die Fehlkommunikation ergibt sich daraus: Sax und iSax sind Darstellungsformate zum Speichern und Verarbeiten von Zeitreihen, sie sind keine Clustering- oder Segment- / Mustererkennungsalgorithmen (pro OP-Beitrag). Aus Ihrer Antwort ging hervor, dass Keogh einen Algorithmus entwickelt hat, der auf dem SAX-Darstellungsformat basiert und sich mit dem Problem des OP befasst. Aber ich denke, das hast du nicht gemeint?
Zhubarb
2
OK, ich muss mich nicht an Keogh wenden , ich weiß über iSax und Sax Bescheid , sie sind Darstellungsformate für ein effizientes Mining von Zeitreihen. Die Links erklären sie. iSax ist die neuere Version. Ich war begeistert von meinem Missverständnis Ihrer Antwort, daher die Fragen (nicht umständlich) :).
Zhubarb,
2
ich habe nicht versucht, etwas zu verbergen, ich habe 'isax routine' als einen Algorithmus interpretiert, der mit isax arbeitet. Ich schlage vor, dass Ihre Antwort nach der Klarstellung umformuliert / geändert werden muss.
Zhubarb
2

Das Ermitteln von Änderungspunkten in einer Zeitreihe erfordert die Erstellung eines robusten globalen ARIMA-Modells (zweifellos fehlerhaft durch Modelländerungen und Parameteränderungen im Laufe der Zeit in Ihrem Fall) und anschließendes Ermitteln des wichtigsten Änderungspunkts in den Parametern dieses Modells. Bei Verwendung Ihrer 509-Werte lag der signifikanteste Änderungspunkt um den Zeitraum 353. Ich habe einige proprietäre Algorithmen in AUTOBOX verwendet (die ich mitentwickelt habe), die möglicherweise für Ihre angepasste Anwendung lizenziert werden könnten. Die Grundidee besteht darin, die Daten in zwei Teile zu unterteilen und nach dem Auffinden des wichtigsten Änderungspunkts jeden der beiden Zeitbereiche separat erneut zu analysieren (1-352; 353-509), um weitere Änderungspunkte in jedem der beiden Sätze zu bestimmen. Dies wird wiederholt, bis Sie k Teilmengen haben. Ich habe den ersten Schritt mit diesem Ansatz angehängt.Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

IrishStat
quelle
Warum wird 353 markiert, wenn 153 und 173 niedrigere P-Werte haben?
Nick Cox
@ NickCox Gute Frage! Großartiger Kommentar Für Prognosezwecke besteht die ganze Idee darin, die neueste (signifikante) Teilmenge von der älteren Teilmenge zu trennen, weshalb 353 gewonnen wurden. Für die Zwecke hier würde man tatsächlich 173 auswählen.
IrishStat
Der Titel "MOST RECENT SIGNIFICANT BREAK POINT" versucht, die Geschichte zu erzählen
IrishStat
Vielen Dank! Das ist wirklich interessant und wird sehr geschätzt. Ich kann Sie für weitere Details kontaktieren.
Whybird
Vielen Dank für die Erklärung: Die Idee ist in der Tat in der letzten Note explizit. (Übrigens habe ich seit Anfang der 90er Jahre nicht mehr so ​​viel UPPER CASE in der Programmausgabe gesehen. Ich würde empfehlen, "95% Konfidenzniveau" in "5% Signifikanzniveau" zu ändern, vorausgesetzt, das ist gemeint.)
Nick Cox
2

Ich denke, dass der Titel des Threads irreführend ist: Sie möchten keine Dichtefunktionen vergleichen, sondern tatsächlich nach Strukturbrüchen in einer Zeitreihe suchen. Sie geben jedoch nicht an, ob diese strukturellen Brüche in einem rollierenden Zeitfenster oder im Nachhinein gefunden werden sollen, indem Sie den gesamten Verlauf der Zeitreihe betrachten. In diesem Sinne handelt es sich bei Ihrer Frage tatsächlich um ein Duplikat dieser Frage: Welche Methode zum Erkennen von Strukturbrüchen in Zeitreihen?

Wie von Rob Hyndman in diesem Link erwähnt, bietet R das Strukturänderungspaket für diesen Zweck an. Ich habe mit Ihren Daten herumgespielt, aber ich muss sagen, dass die Ergebnisse enttäuschend sind [ist der erste Datenpunkt wirklich 4 oder sollte es 54 sein?]:

raw = c(54,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235)
raw = log(raw+1)
d = as.ts(raw,frequency = 12)
dd = ts.intersect(d = d, d1 = lag(d, -1),d2 = lag(d, -2),d3 = lag(d, -3),d4 = lag(d, -4),d5 = lag(d, -5),d6 = lag(d, -6),d7 = lag(d, -7),d8 = lag(d, -8),d9 = lag(d, -9),d10 = lag(d, -10),d11 = lag(d, -11),d12 = lag(d, -12))

(breakpoints(d ~d1 + d2+ d3+ d4+ d5+ d6+ d7+ d8+ d9+ d10+ d11+ d12, data = dd))
>Breakpoints at observation number:
>151 
>Corresponding to breakdates:
>163 

(breakpoints(d ~d1 + d2, data = dd))
>Breakpoints at observation number:
>95 178 
>Corresponding to breakdates:
>107 190 

Ich bin kein regelmäßiger Benutzer des Pakets. Wie Sie sehen, hängt es von dem Modell ab, das Sie in die Daten einpassen. Sie können damit experimentieren

library(forecast)
auto.arima(raw)

das gibt Ihnen das am besten passende ARIMA-Modell.

HOSS_JFL
quelle
Vielen Dank! Ich habe das Wort "Histogramm" aus dem Titel herausgeschnitten. Ich hatte es anfangs falsch benutzt und vergessen, den Titel zu bearbeiten, als ich ihn in einer früheren Bearbeitung als Antwort auf einen Kommentar aus dem Text entfernt habe.
Whybird
Meine Daten sind tatsächlich eine Reihe von räumlich verwandten Daten, sie sind nicht zeitbasiert und werden normalerweise nicht oft genug auf einer geraden Linie oder sogar in einer Ebene vorhanden sein - aber Sie haben Recht, dass sie auf einer fundamentalen Ebene in derselben berücksichtigt werden können Weg; Ich vermute, das könnte ein Grund dafür sein, dass meine früheren Suchanfragen nicht die erwarteten Antworten gefunden haben.
Whybird
Der erste Datenpunkt in diesem Beispiel ist wirklich eine 4, aber es könnte sein, dass wir zufällig das Ende einer vorherigen Struktur erreicht haben oder dass es sich um Rauschen handelte. Ich würde es gerne als Ausreißer auslassen, aber jedes System, das ich mir ausgedacht habe, muss auch mit solchen Dingen fertig werden.
Whybird
Oh, und die Analyse ist im Nachhinein. Ich werde die Frage bearbeiten, um sie zu klären.
Whybird