Wie finde ich Peaks in einem Datensatz?

47

Wenn ich einen Datensatz habe, der eine Grafik wie die folgende erzeugt, wie würde ich algorithmisch die x-Werte der angezeigten Peaks bestimmen (in diesem Fall drei davon):

Bildbeschreibung hier eingeben

nichtaxiomatisch
quelle
13
Ich sehe sechs lokale Maxima. Auf welche drei beziehen Sie sich? :-). (Natürlich ist es offensichtlich - der Kern meiner Bemerkung besteht darin, Sie zu ermutigen, einen "Peak" genauer zu definieren, da dies der Schlüssel zur Erstellung eines guten Algorithmus ist.)
whuber
3
Wenn es sich bei den Daten um rein periodische Zeitreihen mit einer zufälligen Rauschkomponente handelt, können Sie eine harmonische Regressionsfunktion anpassen, bei der Periode und Amplitude Parameter sind, die aus den Daten geschätzt werden. Das resultierende Modell wäre eine periodische Funktion, die glatt ist (dh eine Funktion einiger Sinus- und Cosinus-Werte) und daher eindeutig identifizierbare Zeitpunkte aufweist, zu denen die erste Ableitung Null und die zweite Ableitung negativ ist. Das wären die Gipfel. Die Stellen, an denen die erste Ableitung Null und die zweite Ableitung positiv ist, werden als Täler bezeichnet.
Michael Chernick
2
Ich habe den Modus-Tag hinzugefügt. Schauen Sie sich einige dieser Fragen an. Sie werden interessante Antworten haben.
Andy W
Vielen Dank für Ihre Antworten und Kommentare, es wird sehr geschätzt! Es wird einige Zeit dauern, bis ich die vorgeschlagenen Algorithmen in Bezug auf meine Daten verstanden und implementiert habe. Ich stelle jedoch sicher, dass ich sie später mit Feedback aktualisiere.
Nichtaxiomatische
Vielleicht liegt es daran, dass meine Daten sehr verrauscht sind, aber mit der Antwort unten hatte ich keinen Erfolg. Mit dieser Antwort hatte ich allerdings Erfolg: stackoverflow.com/a/16350373/84873
Daniel,

Antworten:

35

Ein allgemeiner Ansatz besteht darin, die Daten zu glätten und dann Peaks zu finden, indem ein lokaler Maximalfilter mit dem Glättungsfilter verglichen wird . In R:

argmax <- function(x, y, w=1, ...) {
  require(zoo)
  n <- length(y)
  y.smooth <- loess(y ~ x, ...)$fitted
  y.max <- rollapply(zoo(y.smooth), 2*w+1, max, align="center")
  delta <- y.max - y.smooth[-c(1:w, n+1-1:w)]
  i.max <- which(delta <= 0) + w
  list(x=x[i.max], i=i.max, y.hat=y.smooth)
}

Sein Rückgabewert enthält die Argumente der lokalen Maxima ( x) - die die Frage beantworten - und die Indizes in den x- und y-Arrays, in denen diese lokalen Maxima auftreten ( i).

Es gibt zwei Parameter, die auf die Umstände abgestimmt werden müssen: w Ist die halbe Fensterbreite, die zur Berechnung des lokalen Maximums verwendet wird. (Sein Wert sollte wesentlich kleiner als die Hälfte des Datenfelds sein.) Kleine Werte nehmen kleine lokale Unebenheiten auf, während größere Werte direkt über diese hinweggehen. Ein anderes - in diesem Code nicht explizit - ist das spanArgument des loessGlätters. (Sie liegt normalerweise zwischen null und eins. Sie gibt die Fensterbreite als Anteil des Bereichs der x-Werte wieder.) Größere Werte glätten die Daten aggressiver und lassen lokale Unebenheiten vollständig verschwinden.

Um zu sehen, wie sich diese Optimierung auswirkt, erstellen wir eine kleine Testfunktion, um die Ergebnisse zu zeichnen:

test <- function(w, span) {
  peaks <- argmax(x, y, w=w, span=span)

  plot(x, y, cex=0.75, col="Gray", main=paste("w = ", w, ", span = ", span, sep=""))
  lines(x, peaks$y.hat,  lwd=2) #$
  y.min <- min(y)
  sapply(peaks$i, function(i) lines(c(x[i],x[i]), c(y.min, peaks$y.hat[i]),
         col="Red", lty=2))
  points(x[peaks$i], peaks$y.hat[peaks$i], col="Red", pch=19, cex=1.25)
}

Im Folgenden werden einige Experimente mit synthetischen, leicht verrauschten Daten durchgeführt.

x <- 1:1000 / 100 - 5
y <- exp(abs(x)/20) * sin(2 * x + (x/5)^2) + cos(10*x) / 5 + rnorm(length(x), sd=0.05)
par(mfrow=c(3,1))
test(2, 0.05)
test(30, 0.05)
test(2, 0.2)

Grundstücke

Entweder ein breites Fenster (mittleres Diagramm) oder ein aggressiveres glattes Fenster (unteres Diagramm) eliminieren die lokalen Maxima, die im oberen Diagramm erkannt wurden. Die beste Kombination ist hier wahrscheinlich ein breites Fenster und nur eine sanfte Glättung, da eine aggressive Glättung diese Peaks zu verschieben scheint (sehen Sie die mittleren und rechten Punkte in der unteren Darstellung und vergleichen Sie ihre Positionen mit den scheinbaren Peaks der Rohdaten). In diesem Beispiel w=50und span=0.05macht einen tollen Job (nicht gezeigt).

Beachten Sie, dass die lokalen Maxima an den Endpunkten nicht erkannt werden. Diese können separat eingesehen werden. (Um dies zu unterstützen, werden argmaxdie geglätteten y-Werte zurückgegeben.)


Dieser Ansatz hat mehrere Vorteile gegenüber einer formaleren Modellierung für allgemeine Zwecke:

  • Es wird kein vorgefasstes Modell der Daten übernommen.

  • Es kann an die Dateneigenschaften angepasst werden.

  • Es kann angepasst werden, um die Arten von Peaks zu erkennen, an denen man interessiert ist.

whuber
quelle
3
Im Gegenteil, @Michael: Ich gehe nicht von Periodizität aus. Das Beispiel sieht zwar periodisch aus, ist es aber nicht: Beachten Sie den quadratischen Ausdruck. Die harmonische Regression wird mit diesem Beispiel (und mit vielen anderen derartigen Reihen) fehlschlagen. Außerdem nehme ich "visuell" nichts heraus: alles wird mit dem Algorithmus erledigt. (Warum habe ich den starken Eindruck, dass Sie diese Antwort nicht gelesen haben?)
whuber
1
Ich kann die Peaks algorithmisch durch den ersten und den zweiten Ableitungstest finden, während Sie andere Mittel verwenden müssen (möglicherweise so etwas wie eine numerische Suche). Es ging mir nicht darum, zu behaupten, ein Ansatz sei besser als der andere, und ich habe Ihre Antwort überhaupt nicht kritisiert. Ich sehe nur viele Gemeinsamkeiten und einige Unterschiede und habe versucht, ein klareres Verständnis dafür zu bekommen, wie Sie Ihre Peaks identifizieren.
Michael Chernick
3
O(n)
4
@Michael, wenn du keine Zeit zum Lesen einer Antwort / eines Kommentars hast, kannst du in Betracht ziehen, nicht auf Aussagen über den Beitrag zu antworten / diese zu machen. Dies haben Sie wiederholt getan und es kommt häufig zu unkonstruktivem Austausch und / oder Sie machen falsche Aussagen, die Sie später zurückziehen. Es scheint eine Zeitverschwendung zu sein und die anderen, die Sie in solche Gespräche verwickeln. Zum Beispiel hat dieser gesamte Kommentarthread sicherlich mehr Zeit in Anspruch genommen, als nur die Antwort zu lesen. Warum Sie die Site auf diese Weise nutzen, rätselt mich immer wieder. Ich verstehe nicht, wie es jemandem nützt.
Makro
2
Danke für den interessanten Ansatz. Ich glaube, ich verstehe auch, worauf Michael abzielte: Sie mussten die Diagramme anzeigen, um die besten Werte für wund zu ermitteln spanund um festzustellen, dass höhere Werte von spandie Spitzen verschoben haben. Es scheint, als könnten auch diese Schritte automatisiert werden. Wenn wir zum Beispiel für die erste Ausgabe die Qualität der entdeckten Peaks bewerten könnten, könnten wir optimizemit den Parametern arbeiten! Wählen Sie für die zweite Ausgabe z. B. ein Fenster zu beiden Seiten des erkannten Peaks aus und suchen Sie nach höheren Werten.
Darren Cook
1

Wie ich im Kommentar erwähnt habe, bietet ein harmonisches Regressionsmodell eine Möglichkeit, die Funktion zu glätten und den Peak zu identifizieren, indem der erste und der zweite Ableitungstest angewendet werden, wenn die Zeitreihe periodisch angepasst zu sein scheinen. Huber hat auf einen nichtparametrischen Test hingewiesen, der Vorteile hat, wenn es mehrere Peaks gibt und die Funktion nicht unbedingt periodisch ist. Es gibt aber kein kostenloses Mittagessen. Obwohl seine Methode die Vorteile aufweist, die er erwähnt, kann es Nachteile geben, wenn ein parametrisches Modell geeignet ist. Das ist immer die Kehrseite der Verwendung nichtparametrischer Techniken. Obwohl parametrische Annahmen vermieden werden, ist der parametrische Ansatz besser, wenn die parametrischen Annahmen angemessen sind. Sein Verfahren nutzt auch die Zeitreihenstruktur in den Daten nicht in vollem Umfang aus.

Ich denke, dass es zwar angebracht ist, die Vorteile eines vorgeschlagenen Verfahrens herauszustellen, es aber auch wichtig ist, die möglichen Nachteile herauszustellen. Sowohl mein Ansatz als auch der von Huber finden die Peaks auf effiziente Weise. Ich denke jedoch, dass sein Verfahren ein wenig mehr Arbeit erfordert, wenn ein lokales Maximum unter dem zuvor bestimmten höchsten Peak liegt.

Michael Chernick
quelle
2
Könnten Sie bitte die "effiziente Art" Ihres Ansatzes demonstrieren? Ein Teil der Herausforderung besteht darin, einen Algorithmus zu entwickeln, um mehrere Peaks zu finden - was in Ihrem Fall bedeutet, dass Sie alle Nullen einer (teuer berechneten) Ableitung und nicht nur eine Null finden - und genau anzugeben, welchen dieser kritischen Punkte Sie klassifizieren als "Peaks" und welche nicht. Eine gewisse Unterstützung oder Verstärkung Ihrer Behauptung, dass "der parametrische Ansatz besser ist, wenn die parametrischen Annahmen angemessen sind", wäre auch gut, denn wie wir alle wissen, sind parametrische Annahmen niemals genau richtig.
Whuber
@whuber Ich sagte, dass Sie das Modell dann passen würden, da das Modell eine Summe von Sinus und Cosinus ist, die Funktion periodisch ist, treten die Spitzen auf, wenn sowohl die erste Ableitung Null ist als auch die zweite Ableitung am Nullpunkt abnimmt. Das habe ich gemeint, als ich sagte, dass Sie den ersten und den zweiten Ableitungstest machen. Jetzt können Sie lösen, um alle Lösungen zu finden. Wenn Sie jedoch einen Peak haben, sind die anderen Perioden eine und mehrere Perioden von der Lösung entfernt, die Sie haben. Mein Punkt ist, keine Überlegenheit der Methode zu behaupten. Ich möchte nur darauf hinweisen, dass es kein kostenloses Mittagessen gibt.
Michael Chernick
Nichtparametrische Verfahren haben den Vorteil, dass keine Modellannahme erforderlich ist, in diesem Fall keine Annahme der Periodizität. Meine Aussage, dass parametrische Ansätze besser sind als nichtparametrische Ansätze, wenn die Modellierungsannahmen zutreffen, sollte Ihnen sehr vertraut sein. Ich muss mich nicht über parametrische Annahmen streiten, die nie genau zutreffen. Das ist eine Meinung, der ich grundsätzlich zustimme. Aber ich spreche von Pitman-Effizienz. Nichtparametrische Schätzungen sind nicht so effizient wie parametrische Schätzungen, wenn das Modell "korrekt" ist.
Michael Chernick
Das ist theorie In der Praxis können parametrische Modelle gute Annäherungen an die Realität sein. In diesem Fall ist die parametrische Schätzung (z. B. mle) effizienter als die nichtparametrische Schätzung. Auch die parametrischen Konfidenzintervalle sind besser, weil sie enger sind. Aber oft wissen Sie nicht, wie gut das parametrische Modell für Ihr Beispiel ist. In solchen Fällen muss man sich entscheiden, ob man konservativ (sicher) mit dem nichtparametrischen Ansatz oder mutig (und möglicherweise falsch) mit dem parametrischen Ansatz vorgeht.
Michael Chernick
1
Ich möchte vorschlagen, Michael, dass in diesem Fall der nichtparametrische Ansatz wahrscheinlich weitaus besser ist als jeder parametrische Ansatz, es sei denn, die Daten stimmen besonders gut mit dem Modell überein - und selbst dann wird er eine gute Leistung erbringen. Angenommen, die Periodizität ist ein gutes Beispiel: Ihr Algorithmus macht Fehler in derselben Größenordnung wie die Abweichungen von der Periodizität innerhalb der Daten. Die Möglichkeit, solche Fehler zu machen, hebt alle Vorteile auf, die sich aus einer höheren asymptotischen Effizienz ergeben. Ein solches Verfahren zu verwenden, ohne zuvor umfangreiche GoF-Tests durchzuführen, wäre eine schlechte Idee.
whuber
1

Ein klassischer Ansatz zur Erkennung von Spitzenwerten in der Signalverarbeitung lautet wie folgt:

  1. Filtern Sie das Signal auf einen angemessenen, angemessenen Bereich, abhängig von der Abtastrate und den Signaleigenschaften, z. B. für EKG, ein IIR-Bandpassfilter bei 0,5 bis 20 Hz. Ein Nullphasenfilter stellt sicher, dass keine Phasenverschiebung (und die damit verbundene Zeitverzögerung) eingeführt wird
  2. Eine Hilbert-Transformation oder ein Wavelet-Ansatz kann dann verwendet werden, um die Peaks hervorzuheben
  3. Dann kann ein statischer oder dynamischer Schwellenwert angewendet werden, bei dem alle Abtastwerte über dem Schwellenwert als Spitzenwerte gelten. Im Falle einer dynamischen Schwelle wird sie üblicherweise als eine Schwelle N von Standardabweichungen über oder unter einer Schätzung des gleitenden Durchschnitts des Mittelwerts definiert.

Ein anderer Ansatz, der funktioniert, besteht darin, ein scharf hochpassgefiltertes Signal mit einem stark geglätteten (tiefpass- oder mediangefilterten) Signal zu vergleichen und Schritt 3 anzuwenden.

Hoffe das hilft.

BGreene
quelle