Spitzensignalerkennung in Echtzeit-Zeitreihendaten

242

Update: Der beste Ergebnis erzielt Algorithmus so weit ist dies ein .


In dieser Frage werden robuste Algorithmen zum Erkennen plötzlicher Spitzen in Echtzeit-Zeitreihendaten untersucht.

Betrachten Sie den folgenden Datensatz:

p = [1 1 1.1 1 0.9 1 1 1.1 1 0.9 1 1.1 1 1 0.9 1 1 1.1 1 1 1 1 1.1 0.9 1 1.1 1 1 0.9 1, ...
     1.1 1 1 1.1 1 0.8 0.9 1 1.2 0.9 1 1 1.1 1.2 1 1.5 1 3 2 5 3 2 1 1 1 0.9 1 1 3, ... 
     2.6 4 3 3.2 2 1 1 0.8 4 4 2 2.5 1 1 1];

(Matlab-Format, aber es geht nicht um die Sprache, sondern um den Algorithmus)

Plot von Daten

Sie können deutlich sehen, dass es drei große und einige kleine Gipfel gibt. Dieser Datensatz ist ein spezifisches Beispiel für die Klasse von Zeitreihen-Datensätzen, um die es in der Frage geht. Diese Klasse von Datensätzen weist zwei allgemeine Merkmale auf:

  1. Es gibt Grundgeräusche mit einem allgemeinen Mittelwert
  2. Es gibt große " Spitzen " oder " höhere Datenpunkte ", die erheblich vom Rauschen abweichen.

Nehmen wir auch Folgendes an:

  • Die Breite der Peaks kann nicht vorher bestimmt werden
  • Die Höhe der Peaks weicht deutlich und deutlich von den anderen Werten ab
  • Der verwendete Algorithmus muss Echtzeit berechnen (also mit jedem neuen Datenpunkt ändern).

Für eine solche Situation muss ein Grenzwert konstruiert werden, der Signale auslöst. Der Grenzwert kann jedoch nicht statisch sein und muss in Echtzeit anhand eines Algorithmus ermittelt werden.


Meine Frage: Was ist ein guter Algorithmus, um solche Schwellenwerte in Echtzeit zu berechnen? Gibt es spezielle Algorithmen für solche Situationen? Was sind die bekanntesten Algorithmen?


Robuste Algorithmen oder nützliche Erkenntnisse werden sehr geschätzt. (kann in jeder Sprache antworten: es geht um den Algorithmus)

Jean Paul
quelle
5
Es müssen einige absolute Höhe Voraussetzung sein für eine Spitze zusätzlich zu den Anforderungen sein , die Sie bereits gegeben. Andernfalls sollte der Peak zum Zeitpunkt 13 als Peak betrachtet werden. (Gleichwertig: Wenn in Zukunft die Peaks auf etwa 1000
gestiegen sind,
Genau. Nehmen wir an, diese Peaks müssen nur berücksichtigt werden.
Jean-Paul
Möglicherweise stellen Sie die falsche Frage. Anstatt zu fragen, wie Sie ohne Verzögerung erkennen können, können Sie sich fragen, ob es möglich ist, einen bestimmten Signaltyp ohne Verzögerung zu erkennen, wenn nur das bekannt ist, was vor diesem Zeitpunkt bekannt war, oder was über ein Signal bekannt sein muss, um etwas mit einem bestimmten Signal zu erkennen verzögern.
hotpaw2
2
Ich habe dies getan, um eine abrupte Änderung der Lichtintensität auf einem Photosensor zu erkennen. Dazu habe ich den Durchschnitt verschoben und alle Datenpunkte ignoriert, die größer als ein Schwellenwert sind. Beachten Sie, dass sich dieser Schwellenwert von dem Schwellenwert unterscheidet, der einen Peak bestimmt. Angenommen, Sie schließen nur Datenpunkte ein, die innerhalb eines Standardwerts zu Ihrem gleitenden Durchschnitt liegen, und betrachten diese Datenpunkte mit mehr als drei Standardwerten als Spitzenwerte. Dieser Algorithmus hat sich damals für unseren Anwendungskontext sehr gut bewährt.
halb
1
Ah ich sehe. Ich hatte es nicht im Codeformular erwartet. Wenn ich diese Frage früher gesehen hätte, würden Sie diese Antwort wahrscheinlich viel schneller erhalten = D. Wie auch immer, meine damalige Anwendung bestand darin, festzustellen, ob der Photosensor von der Umgebungslichtquelle blockiert ist (aus diesem Grund benötigen wir den gleitenden Durchschnitt, da sich die Umgebungslichtquelle im Laufe der Zeit allmählich ändern kann). Wir haben dies als ein Spiel erstellt, bei dem Sie Ihre Hand nach einem bestimmten Muster über die Sensoren bewegen sollten. = D
halb

Antworten:

334

Robuster Peak-Erkennungsalgorithmus (unter Verwendung von Z-Scores)

Ich habe einen Algorithmus entwickelt, der für diese Arten von Datensätzen sehr gut funktioniert. Es basiert auf dem Prinzip der Dispersion : Wenn ein neuer Datenpunkt eine gegebene x Anzahl von Standardabweichungen von einem sich bewegenden Mittelwert entfernt ist, signalisiert der Algorithmus (auch als Z-Score bezeichnet ). Der Algorithmus ist sehr robust, da er einen separaten gleitenden Mittelwert und eine separate Abweichung erstellt, sodass Signale den Schwellenwert nicht verfälschen. Zukünftige Signale werden daher unabhängig von der Anzahl der vorherigen Signale mit ungefähr derselben Genauigkeit identifiziert. Der Algorithmus benötigt 3 Eingaben : lag = the lag of the moving window, threshold = the z-score at which the algorithm signalsund influence = the influence (between 0 and 1) of new signals on the mean and standard deviation. Zum Beispiel verwendet a lagvon 5 die letzten 5 Beobachtungen, um die Daten zu glätten. EINthresholdvon 3,5 signalisiert, wenn ein Datenpunkt 3,5 Standardabweichungen vom gleitenden Mittelwert entfernt ist. Und ein Wert influencevon 0,5 gibt Signalen die Hälfte des Einflusses, den normale Datenpunkte haben. Ebenso influenceignoriert ein von 0 Signale vollständig, um den neuen Schwellenwert neu zu berechnen. Ein Einfluss von 0 ist daher die robusteste Option (setzt jedoch Stationarität voraus ); Die Einflussoption auf 1 zu setzen ist am wenigsten robust. Bei instationären Daten sollte die Einflussoption daher irgendwo zwischen 0 und 1 liegen.

Es funktioniert wie folgt:

Pseudocode

# Let y be a vector of timeseries data of at least length lag+2
# Let mean() be a function that calculates the mean
# Let std() be a function that calculates the standard deviaton
# Let absolute() be the absolute value function

# Settings (the ones below are examples: choose what is best for your data)
set lag to 5;          # lag 5 for the smoothing functions
set threshold to 3.5;  # 3.5 standard deviations for signal
set influence to 0.5;  # between 0 and 1, where 1 is normal influence, 0.5 is half

# Initialize variables
set signals to vector 0,...,0 of length of y;   # Initialize signal results
set filteredY to y(1),...,y(lag)                # Initialize filtered series
set avgFilter to null;                          # Initialize average filter
set stdFilter to null;                          # Initialize std. filter
set avgFilter(lag) to mean(y(1),...,y(lag));    # Initialize first value
set stdFilter(lag) to std(y(1),...,y(lag));     # Initialize first value

for i=lag+1,...,t do
  if absolute(y(i) - avgFilter(i-1)) > threshold*stdFilter(i-1) then
    if y(i) > avgFilter(i-1) then
      set signals(i) to +1;                     # Positive signal
    else
      set signals(i) to -1;                     # Negative signal
    end
    # Reduce influence of signal
    set filteredY(i) to influence*y(i) + (1-influence)*filteredY(i-1);
  else
    set signals(i) to 0;                        # No signal
    set filteredY(i) to y(i);
  end
  # Adjust the filters
  set avgFilter(i) to mean(filteredY(i-lag),...,filteredY(i));
  set stdFilter(i) to std(filteredY(i-lag),...,filteredY(i));
end

Faustregeln für die Auswahl guter Parameter für Ihre Daten finden Sie unten.


Demo

Demonstration eines robusten Schwellenwertalgorithmus

Den Matlab-Code für diese Demo finden Sie hier . Um die Demo zu verwenden, führen Sie sie einfach aus und erstellen Sie selbst eine Zeitreihe, indem Sie auf das obere Diagramm klicken. Der Algorithmus beginnt zu arbeiten, nachdem die lagAnzahl der Beobachtungen gezeichnet wurde .


Ergebnis

Für die ursprüngliche Frage, wird dieser Algorithmus die folgende Ausgabe geben , wenn die folgenden Einstellungen: lag = 30, threshold = 5, influence = 0:

Beispiel für einen Schwellenwertalgorithmus


Implementierungen in verschiedenen Programmiersprachen:


Faustregeln zur Konfiguration des Algorithmus

lag: Der Lag-Parameter bestimmt, wie stark Ihre Daten geglättet werden und wie anpassungsfähig der Algorithmus an Änderungen im langfristigen Durchschnitt der Daten ist. Je stationärer Ihre Daten sind, desto mehr Verzögerungen sollten Sie berücksichtigen (dies sollte die Robustheit des Algorithmus verbessern). Wenn Ihre Daten zeitlich variierende Trends enthalten, sollten Sie überlegen, wie schnell sich der Algorithmus an diese Trends anpassen soll. Das heißt, wenn Sie lagauf 10 setzen, dauert es 10 'Perioden', bis der Schwellenwert des Algorithmus an systematische Änderungen des langfristigen Durchschnitts angepasst wird. Wählen Sie den lagParameter also basierend auf dem Trendverhalten Ihrer Daten und der Anpassungsfähigkeit des Algorithmus.

influence: Dieser Parameter bestimmt den Einfluss von Signalen auf die Erkennungsschwelle des Algorithmus. Bei 0 haben Signale keinen Einfluss auf den Schwellenwert, sodass zukünftige Signale basierend auf einem Schwellenwert erfasst werden, der mit einem Mittelwert und einer Standardabweichung berechnet wird, die nicht durch vergangene Signale beeinflusst werden. Eine andere Möglichkeit, darüber nachzudenken, besteht darin, dass Sie implizit Stationarität annehmen, wenn Sie den Einfluss auf 0 setzen (dh unabhängig von der Anzahl der Signale kehrt die Zeitreihe langfristig immer zum gleichen Durchschnitt zurück). Ist dies nicht der Fall, sollten Sie den Einflussparameter irgendwo zwischen 0 und 1 setzen, je nachdem, inwieweit Signale den zeitlich variierenden Trend der Daten systematisch beeinflussen können. ZB wenn Signale zu einem Strukturbruch führen Im Langzeitdurchschnitt der Zeitreihen sollte der Einflussparameter hoch (nahe 1) gesetzt werden, damit sich der Schwellenwert schnell an diese Änderungen anpassen kann.

threshold: Der Schwellenwertparameter ist die Anzahl der Standardabweichungen vom gleitenden Mittelwert, über denen der Algorithmus einen neuen Datenpunkt als Signal klassifiziert. Wenn beispielsweise ein neuer Datenpunkt 4,0 Standardabweichungen über dem gleitenden Mittelwert liegt und der Schwellenwertparameter auf 3,5 eingestellt ist, identifiziert der Algorithmus den Datenpunkt als Signal. Dieser Parameter sollte basierend auf der Anzahl der erwarteten Signale eingestellt werden. Wenn Ihre Daten beispielsweise normal verteilt sind, entspricht ein Schwellenwert (oder: Z-Score) von 3,5 einer Signalisierungswahrscheinlichkeit von 0,00047 (aus dieser Tabelle)), was bedeutet, dass Sie alle 2128 Datenpunkte (1 / 0,00047) einmal ein Signal erwarten. Die Schwelle beeinflusst daher direkt, wie empfindlich der Algorithmus ist und damit auch, wie oft der Algorithmus signalisiert. Untersuchen Sie Ihre eigenen Daten und bestimmen Sie einen vernünftigen Schwellenwert, der den Algorithmus signalisiert, wann Sie dies möchten (hier ist möglicherweise ein Versuch und Irrtum erforderlich, um einen für Ihren Zweck geeigneten Schwellenwert zu erreichen).


WARNUNG: Der obige Code durchläuft bei jeder Ausführung immer alle Datenpunkte. Stellen Sie bei der Implementierung dieses Codes sicher, dass Sie die Berechnung des Signals in eine separate Funktion (ohne Schleife) aufteilen. Dann , wenn ein neuer Datenpunkt ankommt, zu aktualisieren filteredY, avgFilterund stdFiltereinmal. Berechnen Sie die Signale nicht jedes Mal neu, wenn ein neuer Datenpunkt vorhanden ist (wie im obigen Beispiel). Dies wäre äußerst ineffizient und langsam!

Andere Möglichkeiten zum Ändern des Algorithmus (für mögliche Verbesserungen) sind:

  1. Verwenden Sie den Median anstelle des Mittelwerts
  2. Verwenden Sie anstelle der Standardabweichung ein robustes Maß für die Skalierung , z. B. das MAD
  3. Verwenden Sie einen Signalisierungsspielraum, damit das Signal nicht zu oft umschaltet
  4. Ändern Sie die Funktionsweise des Einflussparameters
  5. Saures up und unten Signale unterschiedlich (asymmetrisch Behandlung)
  6. Erstellen Sie einen separaten influenceParameter für den Mittelwert und den Standard ( wie in dieser Swift-Übersetzung beschrieben ).

(Bekannte) akademische Zitate zu dieser StackOverflow-Antwort:

Andere arbeiten mit dem Algorithmus

Andere Anwendungen dieses Algorithmus

Links zu anderen Algorithmen zur Peakerkennung


Wenn Sie diese Funktion irgendwo verwenden, schreiben Sie mir oder dieser Antwort gut. Wenn Sie Fragen zu diesem Algorithmus haben, posten Sie diese in den Kommentaren unten oder wenden Sie sich an mich auf LinkedIn .


Jean Paul
quelle
Die Verbindung zu movestd ist unterbrochen, aber eine Beschreibung finden Sie hier
Phylliida
@reasra Es stellt sich heraus, dass die Funktion nach dem Umschreiben keine bewegliche Standardabweichung benötigt. Es kann jetzt mit einfachen eingebauten Matlab-Funktionen verwendet werden :)
Jean-Paul
1
Ich versuche den Matlab-Code für einige Beschleunigungsmesserdaten, aber aus irgendeinem Grund wird das thresholdDiagramm nach einer großen Spitze von bis zu 20 in den Daten nur zu einer flachen grünen Linie, und es bleibt für den Rest des Diagramms so ... Wenn Ich entferne das Sike, das passiert nicht, also scheint es durch den Spike in den Daten verursacht zu werden. Irgendeine Idee, was los sein könnte? Ich bin ein Neuling in Matlab, also kann ich es nicht herausfinden ...
Magnus W
@BadCash Können Sie ein Beispiel (mit den Daten) liefern? Vielleicht stellen Sie Ihre eigene Frage hier auf SO und sagen Sie mir den Link?
Jean-Paul
2
Es gibt viele Möglichkeiten, dieses Algo zu verbessern. Seien Sie also kreativ (unterschiedliche Behandlung nach oben / unten; Median statt Mittelwert; robuster Standard; Schreiben des Codes als speichereffiziente Funktion; Schwellenwert, damit das Signal nicht zu oft umschaltet usw. .).
Jean-Paul
41

Hier ist die Python/ numpyImplementierung des geglätteten Z-Score-Algorithmus (siehe Antwort oben ). Das Wesentliche finden Sie hier .

#!/usr/bin/env python
# Implementation of algorithm from https://stackoverflow.com/a/22640362/6029703
import numpy as np
import pylab

def thresholding_algo(y, lag, threshold, influence):
    signals = np.zeros(len(y))
    filteredY = np.array(y)
    avgFilter = [0]*len(y)
    stdFilter = [0]*len(y)
    avgFilter[lag - 1] = np.mean(y[0:lag])
    stdFilter[lag - 1] = np.std(y[0:lag])
    for i in range(lag, len(y)):
        if abs(y[i] - avgFilter[i-1]) > threshold * stdFilter [i-1]:
            if y[i] > avgFilter[i-1]:
                signals[i] = 1
            else:
                signals[i] = -1

            filteredY[i] = influence * y[i] + (1 - influence) * filteredY[i-1]
            avgFilter[i] = np.mean(filteredY[(i-lag+1):i+1])
            stdFilter[i] = np.std(filteredY[(i-lag+1):i+1])
        else:
            signals[i] = 0
            filteredY[i] = y[i]
            avgFilter[i] = np.mean(filteredY[(i-lag+1):i+1])
            stdFilter[i] = np.std(filteredY[(i-lag+1):i+1])

    return dict(signals = np.asarray(signals),
                avgFilter = np.asarray(avgFilter),
                stdFilter = np.asarray(stdFilter))

Unten sehen Sie den Test für denselben Datensatz, der das gleiche Diagramm wie in der ursprünglichen Antwort für R/ ergibtMatlab

# Data
y = np.array([1,1,1.1,1,0.9,1,1,1.1,1,0.9,1,1.1,1,1,0.9,1,1,1.1,1,1,1,1,1.1,0.9,1,1.1,1,1,0.9,
       1,1.1,1,1,1.1,1,0.8,0.9,1,1.2,0.9,1,1,1.1,1.2,1,1.5,1,3,2,5,3,2,1,1,1,0.9,1,1,3,
       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1])

# Settings: lag = 30, threshold = 5, influence = 0
lag = 30
threshold = 5
influence = 0

# Run algo with settings from above
result = thresholding_algo(y, lag=lag, threshold=threshold, influence=influence)

# Plot result
pylab.subplot(211)
pylab.plot(np.arange(1, len(y)+1), y)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"], color="cyan", lw=2)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"] + threshold * result["stdFilter"], color="green", lw=2)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"] - threshold * result["stdFilter"], color="green", lw=2)

pylab.subplot(212)
pylab.step(np.arange(1, len(y)+1), result["signals"], color="red", lw=2)
pylab.ylim(-1.5, 1.5)
pylab.show()
R Kiselev
quelle
Hier ist 'y' eigentlich das Signal und 'Signale' ist der Satz von Datenpunkten. Bin ich im Verständnis richtig?
TheTank
1
@TheTank yist das Datenarray, das Sie übergeben. Es signalsist das +1oder das -1Ausgabearray, das für jeden Datenpunkt angibt, y[i]ob dieser Datenpunkt angesichts der von Ihnen verwendeten Einstellungen ein "signifikanter Peak" ist.
Jean-Paul
23

Ein Ansatz besteht darin, Peaks basierend auf der folgenden Beobachtung zu erfassen:

  • Die Zeit t ist eine Spitze, wenn (y (t)> y (t-1)) && (y (t)> y (t + 1))

Es vermeidet Fehlalarme, indem es wartet, bis der Aufwärtstrend vorbei ist. Es ist nicht gerade "Echtzeit" in dem Sinne, dass es den Peak um einen dt verfehlt. Die Empfindlichkeit kann gesteuert werden, indem zum Vergleich ein Spielraum benötigt wird. Es gibt einen Kompromiss zwischen verrauschter Erkennung und zeitlicher Verzögerung der Erkennung. Sie können das Modell erweitern, indem Sie weitere Parameter hinzufügen:

  • Peak, wenn (y (t) - y (t - dt)> m) && (y (t) - y (t + dt)> m)

Dabei sind dt und m Parameter zur Steuerung der Empfindlichkeit gegenüber der Zeitverzögerung

Folgendes erhalten Sie mit dem genannten Algorithmus: Geben Sie hier die Bildbeschreibung ein

Hier ist der Code zum Reproduzieren der Handlung in Python:

import numpy as np
import matplotlib.pyplot as plt
input = np.array([ 1. ,  1. ,  1. ,  1. ,  1. ,  1. ,  1. ,  1.1,  1. ,  0.8,  0.9,
    1. ,  1.2,  0.9,  1. ,  1. ,  1.1,  1.2,  1. ,  1.5,  1. ,  3. ,
    2. ,  5. ,  3. ,  2. ,  1. ,  1. ,  1. ,  0.9,  1. ,  1. ,  3. ,
    2.6,  4. ,  3. ,  3.2,  2. ,  1. ,  1. ,  1. ,  1. ,  1. ])
signal = (input > np.roll(input,1)) & (input > np.roll(input,-1))
plt.plot(input)
plt.plot(signal.nonzero()[0], input[signal], 'ro')
plt.show()

Durch Einstellen m = 0.5können Sie ein saubereres Signal mit nur einem falsch positiven Ergebnis erhalten: Geben Sie hier die Bildbeschreibung ein

Aha
quelle
Früher = besser, damit alle Peaks signifikant sind. Vielen Dank! Sehr cool!
Jean-Paul
Wie würde ich die Empfindlichkeit ändern?
Jean-Paul
Ich kann mir zwei Ansätze vorstellen: 1: Setzen Sie m auf einen größeren Wert, damit nur größere Peaks erkannt werden. 2: Anstatt y (t) - y (t-dt) (und y (t) - y (t + dt)) zu berechnen, integrieren Sie von t-dt nach t (und t nach t + dt).
Aha
2
Nach welchen Kriterien lehnen Sie die anderen 7 Peaks ab?
hotpaw2
4
Es gibt ein Problem mit flachen Spitzen, da Sie im Grunde genommen eine 1-D-Kantenerkennung durchführen (wie das Falten des Signals mit [1 0 -1])
ben
18

Bei der Signalverarbeitung erfolgt die Spitzenwerterfassung häufig über eine Wavelet-Transformation. Grundsätzlich führen Sie eine diskrete Wavelet-Transformation Ihrer Zeitreihendaten durch. Nulldurchgänge in den zurückgegebenen Detailkoeffizienten entsprechen Spitzen im Zeitreihensignal. Sie erhalten unterschiedliche Spitzenamplituden bei unterschiedlichen Detailkoeffizienten, wodurch Sie eine Auflösung von mehreren Ebenen erhalten.

cklin
quelle
1
Ihre Antwort lässt mich zu diesem Artikel und dieser Antwort, die mir helfen wird, einen guten Algorithmus für meine Implementierung zu konstruieren. Vielen Dank!
Jean-Paul
@cklin Können Sie erklären, wie Sie die Nulldurchgänge von Wavelet-Cofs berechnen, da diese nicht auf derselben Zeitskala wie die ursprüngliche Zeitreihe liegen? Irgendein Hinweis auf diese Verwendung?
HoraceT
11

Wir haben versucht, den geglätteten Z-Score-Algorithmus für unseren Datensatz zu verwenden, der entweder zu Überempfindlichkeit oder zu Unterempfindlichkeit führt (abhängig davon, wie die Parameter eingestellt sind), mit wenig Mittelweg. In der Verkehrsampel unserer Site haben wir eine niederfrequente Basislinie beobachtet, die den täglichen Zyklus darstellt, und selbst mit den bestmöglichen Parametern (siehe unten) ist sie insbesondere am 4. Tag immer noch abgeklungen, da die meisten Datenpunkte als Anomalie erkannt werden .

Aufbauend auf dem ursprünglichen Z-Score-Algorithmus haben wir einen Weg gefunden, dieses Problem durch umgekehrte Filterung zu lösen. Die Details des modifizierten Algorithmus und seine Anwendung auf die Verkehrszuweisung von TV-Werbung werden in unserem Team-Blog veröffentlicht .

Geben Sie hier die Bildbeschreibung ein

jbm
quelle
Es ist cool zu sehen, dass der Algorithmus ein Ausgangspunkt für Ihre fortgeschrittenere Version war. Ihre Daten haben ein ganz bestimmtes Muster, daher wäre es in der Tat sinnvoller, das Muster zuerst mit einer anderen Technik zu entfernen und dann das Algo auf die Residuen anzuwenden. Alternativ können Sie ein zentriertes anstelle eines verzögerten Fensters verwenden, um den Durchschnitt / st.dev zu berechnen. Noch ein Kommentar: Ihre Lösung bewegt sich von rechts nach links, um Spitzen zu identifizieren. Dies ist jedoch in Echtzeitanwendungen nicht möglich (deshalb ist das ursprüngliche Algo so einfach, weil auf zukünftige Informationen nicht zugegriffen werden kann).
Jean-Paul
10

In der Computertopologie führt die Idee der persistenten Homologie zu einer effizienten - so sortierschnellen - Lösung. Es erkennt nicht nur Peaks, sondern quantifiziert auf natürliche Weise die "Signifikanz" der Peaks, sodass Sie die für Sie signifikanten Peaks auswählen können.

Zusammenfassung des Algorithmus. In einer eindimensionalen Einstellung (Zeitreihen, reelles Signal) kann der Algorithmus leicht durch die folgende Abbildung beschrieben werden:

Die meisten anhaltenden Spitzen

Stellen Sie sich das Funktionsdiagramm (oder seine untergeordnete Ebene) als Landschaft vor und betrachten Sie einen abnehmenden Wasserstand ab Stufe unendlich (oder 1,8 in diesem Bild). Während der Pegel abnimmt, tauchen bei lokalen Maxima Inseln auf. Bei lokalen Minima verschmelzen diese Inseln miteinander. Ein Detail dieser Idee ist, dass die später erscheinende Insel mit der älteren Insel verschmolzen wird. Die "Persistenz" einer Insel ist ihre Geburtszeit abzüglich ihrer Todeszeit. Die Längen der blauen Balken zeigen die Persistenz, die die oben erwähnte "Bedeutung" eines Peaks ist.

Effizienz. Es ist nicht allzu schwer, eine Implementierung zu finden, die in linearer Zeit ausgeführt wird - tatsächlich handelt es sich um eine einzelne, einfache Schleife -, nachdem die Funktionswerte sortiert wurden. Daher sollte diese Implementierung in der Praxis schnell sein und ist auch leicht zu implementieren.

Verweise. Eine Zusammenfassung der gesamten Geschichte und Hinweise auf die Motivation aus persistenter Homologie (ein Feld in der rechnergestützten algebraischen Topologie) finden Sie hier: https://www.sthu.org/blog/13-perstopology-peakdetection/index.html

S. Huber
quelle
Dieser Algorithmus ist viel schneller und genauer als beispielsweise scipy.signal.find_peaks. Für eine "echte" Zeitreihe mit 1053896 Datenpunkten wurden 137516 Peaks (13%) festgestellt. Die Reihenfolge der Peaks (höchstwertig zuerst) ermöglicht die Extraktion der höchstwertigen Peaks. Es liefert den Anfang, die Spitze und das Ende jeder Spitze. Funktioniert gut mit verrauschten Daten.
Vinh
Mit Echtzeitdaten ist ein sogenannter Online-Algorithmus gemeint, bei dem Datenpunkte immer wieder empfangen werden. Die Bedeutung eines Peaks könnte in Zukunft durch Werte bestimmt werden. Es wäre schön, den Algorithmus so zu erweitern, dass er online ist, indem die Ergebnisse der Vergangenheit geändert werden, ohne die zeitliche Komplexität zu stark zu beeinträchtigen.
S. Huber
9

Fand einen anderen Algorithmus von GH Palshikar in einfachen Algorithmen zur Peakerkennung in Zeitreihen .

Der Algorithmus sieht folgendermaßen aus:

algorithm peak1 // one peak detection algorithms that uses peak function S1 

input T = x1, x2, …, xN, N // input time-series of N points 
input k // window size around the peak 
input h // typically 1 <= h <= 3 
output O // set of peaks detected in T 

begin 
O = empty set // initially empty 

    for (i = 1; i < n; i++) do
        // compute peak function value for each of the N points in T 
        a[i] = S1(k,i,xi,T); 
    end for 

    Compute the mean m' and standard deviation s' of all positive values in array a; 

    for (i = 1; i < n; i++) do // remove local peaks which are “small” in global context 
        if (a[i] > 0 && (a[i] – m') >( h * s')) then O = O + {xi}; 
        end if 
    end for 

    Order peaks in O in terms of increasing index in T 

    // retain only one peak out of any set of peaks within distance k of each other 

    for every adjacent pair of peaks xi and xj in O do 
        if |j – i| <= k then remove the smaller value of {xi, xj} from O 
        end if 
    end for 
end

Vorteile

  • Das Papier bietet 5 verschiedene Algorithmen zur Peakerkennung
  • Die Algorithmen arbeiten mit den rohen Zeitreihendaten (keine Glättung erforderlich).

Nachteile

  • Schwer zu bestimmen kund hvorher
  • Peaks können nicht flach sein (wie der dritte Peak in meinen Testdaten)

Beispiel:

Geben Sie hier die Bildbeschreibung ein

Jean Paul
quelle
Eigentlich interessantes Papier. S4 scheint seiner Meinung nach eine bessere Funktion zu sein. Wichtiger ist jedoch zu klären, wann k <i <Nk nicht wahr ist. Wie würde man die Funktion S1 (S2, ..) für i = 0 definieren? Ich habe einfach nicht durch 2 geteilt und den ersten Operanden ignoriert. Für jeden anderen habe ich beide Operanden eingeschlossen, aber für i <= k gab es links weniger Operanden dann rechts
daniels_pa
8

Hier ist eine Implementierung des Smoothed Z-Score-Algorithmus (oben) in Golang. Es wird ein Slice von []int16(PCM 16bit Samples) angenommen. Einen Kern finden Sie hier .

/*
Settings (the ones below are examples: choose what is best for your data)
set lag to 5;          # lag 5 for the smoothing functions
set threshold to 3.5;  # 3.5 standard deviations for signal
set influence to 0.5;  # between 0 and 1, where 1 is normal influence, 0.5 is half
*/

// ZScore on 16bit WAV samples
func ZScore(samples []int16, lag int, threshold float64, influence float64) (signals []int16) {
    //lag := 20
    //threshold := 3.5
    //influence := 0.5

    signals = make([]int16, len(samples))
    filteredY := make([]int16, len(samples))
    for i, sample := range samples[0:lag] {
        filteredY[i] = sample
    }
    avgFilter := make([]int16, len(samples))
    stdFilter := make([]int16, len(samples))

    avgFilter[lag] = Average(samples[0:lag])
    stdFilter[lag] = Std(samples[0:lag])

    for i := lag + 1; i < len(samples); i++ {

        f := float64(samples[i])

        if float64(Abs(samples[i]-avgFilter[i-1])) > threshold*float64(stdFilter[i-1]) {
            if samples[i] > avgFilter[i-1] {
                signals[i] = 1
            } else {
                signals[i] = -1
            }
            filteredY[i] = int16(influence*f + (1-influence)*float64(filteredY[i-1]))
            avgFilter[i] = Average(filteredY[(i - lag):i])
            stdFilter[i] = Std(filteredY[(i - lag):i])
        } else {
            signals[i] = 0
            filteredY[i] = samples[i]
            avgFilter[i] = Average(filteredY[(i - lag):i])
            stdFilter[i] = Std(filteredY[(i - lag):i])
        }
    }

    return
}

// Average a chunk of values
func Average(chunk []int16) (avg int16) {
    var sum int64
    for _, sample := range chunk {
        if sample < 0 {
            sample *= -1
        }
        sum += int64(sample)
    }
    return int16(sum / int64(len(chunk)))
}
Xeoncross
quelle
@ Jean-Paul Ich bin mir nicht ganz sicher, ob alles korrekt ist, daher kann es zu Fehlern kommen.
Xeoncross
1
Haben Sie versucht, die Demo-Beispielausgabe von Matlab / R zu replizieren? Das sollte eine gute Bestätigung der Qualität sein.
Jean-Paul
7

Hier ist eine C ++ - Implementierung des geglätteten Z-Score-Algorithmus aus dieser Antwort

std::vector<int> smoothedZScore(std::vector<float> input)
{   
    //lag 5 for the smoothing functions
    int lag = 5;
    //3.5 standard deviations for signal
    float threshold = 3.5;
    //between 0 and 1, where 1 is normal influence, 0.5 is half
    float influence = .5;

    if (input.size() <= lag + 2)
    {
        std::vector<int> emptyVec;
        return emptyVec;
    }

    //Initialise variables
    std::vector<int> signals(input.size(), 0.0);
    std::vector<float> filteredY(input.size(), 0.0);
    std::vector<float> avgFilter(input.size(), 0.0);
    std::vector<float> stdFilter(input.size(), 0.0);
    std::vector<float> subVecStart(input.begin(), input.begin() + lag);
    avgFilter[lag] = mean(subVecStart);
    stdFilter[lag] = stdDev(subVecStart);

    for (size_t i = lag + 1; i < input.size(); i++)
    {
        if (std::abs(input[i] - avgFilter[i - 1]) > threshold * stdFilter[i - 1])
        {
            if (input[i] > avgFilter[i - 1])
            {
                signals[i] = 1; //# Positive signal
            }
            else
            {
                signals[i] = -1; //# Negative signal
            }
            //Make influence lower
            filteredY[i] = influence* input[i] + (1 - influence) * filteredY[i - 1];
        }
        else
        {
            signals[i] = 0; //# No signal
            filteredY[i] = input[i];
        }
        //Adjust the filters
        std::vector<float> subVec(filteredY.begin() + i - lag, filteredY.begin() + i);
        avgFilter[i] = mean(subVec);
        stdFilter[i] = stdDev(subVec);
    }
    return signals;
}
Brad
quelle
2
Vorsichtsmaßnahme: Diese Implementierung bietet keine Methode zur Berechnung des Mittelwerts und der Standardabweichung. Für C ++ 11 finden Sie eine einfache Methode hier: stackoverflow.com/a/12405793/3250829
rayryeng
6

Dieses Problem ähnelt dem, das ich in einem Kurs über Hybrid- / Embedded-Systeme festgestellt habe, aber es hing mit der Erkennung von Fehlern zusammen, wenn die Eingabe von einem Sensor verrauscht ist. Wir haben einen Kalman-Filter verwendet , um den verborgenen Zustand des Systems abzuschätzen / vorherzusagen, und dann statistische Analysen verwendet, um die Wahrscheinlichkeit zu bestimmen, dass ein Fehler aufgetreten ist . Wir haben mit linearen Systemen gearbeitet, aber es gibt nichtlineare Varianten. Ich erinnere mich, dass der Ansatz überraschend anpassungsfähig war, aber ein Modell der Dynamik des Systems erforderte.

Peter G.
quelle
Der Kalman-Filter ist interessant, aber ich kann anscheinend keinen geeigneten Algorithmus für meinen Zweck finden. Ich schätze die Antwort sehr und werde in einigen Papieren zur Spitzenerkennung wie diesem nachsehen , ob ich von einem der Algorithmen lernen kann. Vielen Dank!
Jean-Paul
6

C ++ Implementierung

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iterator>
#include <numeric>

using namespace std;

typedef long double ld;
typedef unsigned int uint;
typedef std::vector<ld>::iterator vec_iter_ld;

/**
 * Overriding the ostream operator for pretty printing vectors.
 */
template<typename T>
std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {
    os << "[";
    if (vec.size() != 0) {
        std::copy(vec.begin(), vec.end() - 1, std::ostream_iterator<T>(os, " "));
        os << vec.back();
    }
    os << "]";
    return os;
}

/**
 * This class calculates mean and standard deviation of a subvector.
 * This is basically stats computation of a subvector of a window size qual to "lag".
 */
class VectorStats {
public:
    /**
     * Constructor for VectorStats class.
     *
     * @param start - This is the iterator position of the start of the window,
     * @param end   - This is the iterator position of the end of the window,
     */
    VectorStats(vec_iter_ld start, vec_iter_ld end) {
        this->start = start;
        this->end = end;
        this->compute();
    }

    /**
     * This method calculates the mean and standard deviation using STL function.
     * This is the Two-Pass implementation of the Mean & Variance calculation.
     */
    void compute() {
        ld sum = std::accumulate(start, end, 0.0);
        uint slice_size = std::distance(start, end);
        ld mean = sum / slice_size;
        std::vector<ld> diff(slice_size);
        std::transform(start, end, diff.begin(), [mean](ld x) { return x - mean; });
        ld sq_sum = std::inner_product(diff.begin(), diff.end(), diff.begin(), 0.0);
        ld std_dev = std::sqrt(sq_sum / slice_size);

        this->m1 = mean;
        this->m2 = std_dev;
    }

    ld mean() {
        return m1;
    }

    ld standard_deviation() {
        return m2;
    }

private:
    vec_iter_ld start;
    vec_iter_ld end;
    ld m1;
    ld m2;
};

/**
 * This is the implementation of the Smoothed Z-Score Algorithm.
 * This is direction translation of https://stackoverflow.com/a/22640362/1461896.
 *
 * @param input - input signal
 * @param lag - the lag of the moving window
 * @param threshold - the z-score at which the algorithm signals
 * @param influence - the influence (between 0 and 1) of new signals on the mean and standard deviation
 * @return a hashmap containing the filtered signal and corresponding mean and standard deviation.
 */
unordered_map<string, vector<ld>> z_score_thresholding(vector<ld> input, int lag, ld threshold, ld influence) {
    unordered_map<string, vector<ld>> output;

    uint n = (uint) input.size();
    vector<ld> signals(input.size());
    vector<ld> filtered_input(input.begin(), input.end());
    vector<ld> filtered_mean(input.size());
    vector<ld> filtered_stddev(input.size());

    VectorStats lag_subvector_stats(input.begin(), input.begin() + lag);
    filtered_mean[lag - 1] = lag_subvector_stats.mean();
    filtered_stddev[lag - 1] = lag_subvector_stats.standard_deviation();

    for (int i = lag; i < n; i++) {
        if (abs(input[i] - filtered_mean[i - 1]) > threshold * filtered_stddev[i - 1]) {
            signals[i] = (input[i] > filtered_mean[i - 1]) ? 1.0 : -1.0;
            filtered_input[i] = influence * input[i] + (1 - influence) * filtered_input[i - 1];
        } else {
            signals[i] = 0.0;
            filtered_input[i] = input[i];
        }
        VectorStats lag_subvector_stats(filtered_input.begin() + (i - lag), filtered_input.begin() + i);
        filtered_mean[i] = lag_subvector_stats.mean();
        filtered_stddev[i] = lag_subvector_stats.standard_deviation();
    }

    output["signals"] = signals;
    output["filtered_mean"] = filtered_mean;
    output["filtered_stddev"] = filtered_stddev;

    return output;
};

int main() {
    vector<ld> input = {1.0, 1.0, 1.1, 1.0, 0.9, 1.0, 1.0, 1.1, 1.0, 0.9, 1.0, 1.1, 1.0, 1.0, 0.9, 1.0, 1.0, 1.1, 1.0,
                        1.0, 1.0, 1.0, 1.1, 0.9, 1.0, 1.1, 1.0, 1.0, 0.9, 1.0, 1.1, 1.0, 1.0, 1.1, 1.0, 0.8, 0.9, 1.0,
                        1.2, 0.9, 1.0, 1.0, 1.1, 1.2, 1.0, 1.5, 1.0, 3.0, 2.0, 5.0, 3.0, 2.0, 1.0, 1.0, 1.0, 0.9, 1.0,
                        1.0, 3.0, 2.6, 4.0, 3.0, 3.2, 2.0, 1.0, 1.0, 0.8, 4.0, 4.0, 2.0, 2.5, 1.0, 1.0, 1.0};

    int lag = 30;
    ld threshold = 5.0;
    ld influence = 0.0;
    unordered_map<string, vector<ld>> output = z_score_thresholding(input, lag, threshold, influence);
    cout << output["signals"] << endl;
}
Animesh Pandey
quelle
6

In Anlehnung an die von @ Jean-Paul vorgeschlagene Lösung habe ich seinen Algorithmus in C # implementiert

public class ZScoreOutput
{
    public List<double> input;
    public List<int> signals;
    public List<double> avgFilter;
    public List<double> filtered_stddev;
}

public static class ZScore
{
    public static ZScoreOutput StartAlgo(List<double> input, int lag, double threshold, double influence)
    {
        // init variables!
        int[] signals = new int[input.Count];
        double[] filteredY = new List<double>(input).ToArray();
        double[] avgFilter = new double[input.Count];
        double[] stdFilter = new double[input.Count];

        var initialWindow = new List<double>(filteredY).Skip(0).Take(lag).ToList();

        avgFilter[lag - 1] = Mean(initialWindow);
        stdFilter[lag - 1] = StdDev(initialWindow);

        for (int i = lag; i < input.Count; i++)
        {
            if (Math.Abs(input[i] - avgFilter[i - 1]) > threshold * stdFilter[i - 1])
            {
                signals[i] = (input[i] > avgFilter[i - 1]) ? 1 : -1;
                filteredY[i] = influence * input[i] + (1 - influence) * filteredY[i - 1];
            }
            else
            {
                signals[i] = 0;
                filteredY[i] = input[i];
            }

            // Update rolling average and deviation
            var slidingWindow = new List<double>(filteredY).Skip(i - lag).Take(lag+1).ToList();

            var tmpMean = Mean(slidingWindow);
            var tmpStdDev = StdDev(slidingWindow);

            avgFilter[i] = Mean(slidingWindow);
            stdFilter[i] = StdDev(slidingWindow);
        }

        // Copy to convenience class 
        var result = new ZScoreOutput();
        result.input = input;
        result.avgFilter       = new List<double>(avgFilter);
        result.signals         = new List<int>(signals);
        result.filtered_stddev = new List<double>(stdFilter);

        return result;
    }

    private static double Mean(List<double> list)
    {
        // Simple helper function! 
        return list.Average();
    }

    private static double StdDev(List<double> values)
    {
        double ret = 0;
        if (values.Count() > 0)
        {
            double avg = values.Average();
            double sum = values.Sum(d => Math.Pow(d - avg, 2));
            ret = Math.Sqrt((sum) / (values.Count() - 1));
        }
        return ret;
    }
}

Anwendungsbeispiel:

var input = new List<double> {1.0, 1.0, 1.1, 1.0, 0.9, 1.0, 1.0, 1.1, 1.0, 0.9, 1.0,
    1.1, 1.0, 1.0, 0.9, 1.0, 1.0, 1.1, 1.0, 1.0, 1.0, 1.0, 1.1, 0.9, 1.0, 1.1, 1.0, 1.0, 0.9,
    1.0, 1.1, 1.0, 1.0, 1.1, 1.0, 0.8, 0.9, 1.0, 1.2, 0.9, 1.0, 1.0, 1.1, 1.2, 1.0, 1.5, 1.0,
    3.0, 2.0, 5.0, 3.0, 2.0, 1.0, 1.0, 1.0, 0.9, 1.0, 1.0, 3.0, 2.6, 4.0, 3.0, 3.2, 2.0, 1.0,
    1.0, 0.8, 4.0, 4.0, 2.0, 2.5, 1.0, 1.0, 1.0};

int lag = 30;
double threshold = 5.0;
double influence = 0.0;

var output = ZScore.StartAlgo(input, lag, threshold, influence);
Ocean Airdrop
quelle
1
Hey @ Jean-Paul. Prost. Ja, ich habe die Ausgabe mit Ihrer R-Version getestet, um sicherzustellen, dass sie übereinstimmt. Nochmals vielen Dank für Ihre Lösung für dieses Problem.
Ocean Airdrop
Hallo, ich denke, es gibt einen Fehler in diesem Code. In der Methode StdDev nehmen Sie Werte an. Count () - 1, sollte es -1 geben? Ich denke, Sie möchten die Anzahl der Elemente und das erhalten Sie von values.Count ().
Viktor
1
Hmm .. Guter Ort. Obwohl ich den Algorithmus ursprünglich auf C # portiert habe, habe ich ihn nie verwendet. Ich würde wahrscheinlich diese ganze Funktion durch einen Aufruf der Nuget-Bibliothek MathNet ersetzen. "Install-Package MathNet.Numerics" Es verfügt über vorgefertigte Funktionen für PopulationStandardDeviation () und StandardDeviation (). z.B. var populationsStdDev = neue Liste <double> (1,2,3,4) .PopulationStandardDeviation (); var sampleStdDev = neue Liste <double> (1,2,3,4) .StandardDeviation ();
Ocean Airdrop
6

Hier ist eine C-Implementierung von @ Jean-Pauls Smoothed Z-Score für den Arduino-Mikrocontroller, mit dem Beschleunigungsmesser abgelesen und entschieden werden, ob die Richtung eines Aufpralls von links oder rechts stammt. Dies funktioniert sehr gut, da dieses Gerät ein zurückgeworfenes Signal zurückgibt. Hier ist diese Eingabe für diesen Spitzenerkennungsalgorithmus vom Gerät - zeigt einen Aufprall von rechts, gefolgt von und einen Aufprall von links. Sie können die anfängliche Spitze und dann die Schwingung des Sensors sehen.

Geben Sie hier die Bildbeschreibung ein

#include <stdio.h>
#include <math.h>
#include <string.h>


#define SAMPLE_LENGTH 1000

float stddev(float data[], int len);
float mean(float data[], int len);
void thresholding(float y[], int signals[], int lag, float threshold, float influence);


void thresholding(float y[], int signals[], int lag, float threshold, float influence) {
    memset(signals, 0, sizeof(float) * SAMPLE_LENGTH);
    float filteredY[SAMPLE_LENGTH];
    memcpy(filteredY, y, sizeof(float) * SAMPLE_LENGTH);
    float avgFilter[SAMPLE_LENGTH];
    float stdFilter[SAMPLE_LENGTH];

    avgFilter[lag - 1] = mean(y, lag);
    stdFilter[lag - 1] = stddev(y, lag);

    for (int i = lag; i < SAMPLE_LENGTH; i++) {
        if (fabsf(y[i] - avgFilter[i-1]) > threshold * stdFilter[i-1]) {
            if (y[i] > avgFilter[i-1]) {
                signals[i] = 1;
            } else {
                signals[i] = -1;
            }
            filteredY[i] = influence * y[i] + (1 - influence) * filteredY[i-1];
        } else {
            signals[i] = 0;
        }
        avgFilter[i] = mean(filteredY + i-lag, lag);
        stdFilter[i] = stddev(filteredY + i-lag, lag);
    }
}

float mean(float data[], int len) {
    float sum = 0.0, mean = 0.0;

    int i;
    for(i=0; i<len; ++i) {
        sum += data[i];
    }

    mean = sum/len;
    return mean;


}

float stddev(float data[], int len) {
    float the_mean = mean(data, len);
    float standardDeviation = 0.0;

    int i;
    for(i=0; i<len; ++i) {
        standardDeviation += pow(data[i] - the_mean, 2);
    }

    return sqrt(standardDeviation/len);
}

int main() {
    printf("Hello, World!\n");
    int lag = 100;
    float threshold = 5;
    float influence = 0;
    float y[]=  {1,1,1.1,1,0.9,1,1,1.1,1,0.9,1,1.1,1,1,0.9,1,1,1.1,1,1,1,1,1.1,0.9,1,1.1,1,1,0.9,
  ....
1,1.1,1,1,1.1,1,0.8,0.9,1,1.2,0.9,1,1,1.1,1.2,1,1.5,1,3,2,5,3,2,1,1,1,0.9,1,1,3,       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1,1.2,1,1.5,1,3,2,5,3,2,1,1,1,0.9,1,1,3,
       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1}

    int signal[SAMPLE_LENGTH];

    thresholding(y, signal,  lag, threshold, influence);

    return 0;
}

Ihr Ergebnis mit Einfluss = 0

Geben Sie hier die Bildbeschreibung ein

Nicht großartig, aber hier mit Einfluss = 1

Geben Sie hier die Bildbeschreibung ein

das ist sehr gut.

DavidC
quelle
5

Hier ist eine aktuelle Java-Implementierung, die auf der Groovy-Antwort basiert . (Ich weiß, dass bereits Groovy- und Kotlin-Implementierungen veröffentlicht wurden, aber für jemanden wie mich, der nur Java ausgeführt hat, ist es ein echtes Problem, herauszufinden, wie man zwischen anderen Sprachen und Java konvertiert.)

(Die Ergebnisse stimmen mit den Grafiken anderer Personen überein.)

Implementierung des Algorithmus

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

import org.apache.commons.math3.stat.descriptive.SummaryStatistics;

public class SignalDetector {

    public HashMap<String, List> analyzeDataForSignals(List<Double> data, int lag, Double threshold, Double influence) {

        // init stats instance
        SummaryStatistics stats = new SummaryStatistics();

        // the results (peaks, 1 or -1) of our algorithm
        List<Integer> signals = new ArrayList<Integer>(Collections.nCopies(data.size(), 0));

        // filter out the signals (peaks) from our original list (using influence arg)
        List<Double> filteredData = new ArrayList<Double>(data);

        // the current average of the rolling window
        List<Double> avgFilter = new ArrayList<Double>(Collections.nCopies(data.size(), 0.0d));

        // the current standard deviation of the rolling window
        List<Double> stdFilter = new ArrayList<Double>(Collections.nCopies(data.size(), 0.0d));

        // init avgFilter and stdFilter
        for (int i = 0; i < lag; i++) {
            stats.addValue(data.get(i));
        }
        avgFilter.set(lag - 1, stats.getMean());
        stdFilter.set(lag - 1, Math.sqrt(stats.getPopulationVariance())); // getStandardDeviation() uses sample variance
        stats.clear();

        // loop input starting at end of rolling window
        for (int i = lag; i < data.size(); i++) {

            // if the distance between the current value and average is enough standard deviations (threshold) away
            if (Math.abs((data.get(i) - avgFilter.get(i - 1))) > threshold * stdFilter.get(i - 1)) {

                // this is a signal (i.e. peak), determine if it is a positive or negative signal
                if (data.get(i) > avgFilter.get(i - 1)) {
                    signals.set(i, 1);
                } else {
                    signals.set(i, -1);
                }

                // filter this signal out using influence
                filteredData.set(i, (influence * data.get(i)) + ((1 - influence) * filteredData.get(i - 1)));
            } else {
                // ensure this signal remains a zero
                signals.set(i, 0);
                // ensure this value is not filtered
                filteredData.set(i, data.get(i));
            }

            // update rolling average and deviation
            for (int j = i - lag; j < i; j++) {
                stats.addValue(filteredData.get(j));
            }
            avgFilter.set(i, stats.getMean());
            stdFilter.set(i, Math.sqrt(stats.getPopulationVariance()));
            stats.clear();
        }

        HashMap<String, List> returnMap = new HashMap<String, List>();
        returnMap.put("signals", signals);
        returnMap.put("filteredData", filteredData);
        returnMap.put("avgFilter", avgFilter);
        returnMap.put("stdFilter", stdFilter);

        return returnMap;

    } // end
}

Hauptmethode

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {
        DecimalFormat df = new DecimalFormat("#0.000");

        ArrayList<Double> data = new ArrayList<Double>(Arrays.asList(1d, 1d, 1.1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 0.9d, 1d,
                1.1d, 1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 1d, 1d, 1d, 1.1d, 0.9d, 1d, 1.1d, 1d, 1d, 0.9d, 1d, 1.1d, 1d, 1d,
                1.1d, 1d, 0.8d, 0.9d, 1d, 1.2d, 0.9d, 1d, 1d, 1.1d, 1.2d, 1d, 1.5d, 1d, 3d, 2d, 5d, 3d, 2d, 1d, 1d, 1d,
                0.9d, 1d, 1d, 3d, 2.6d, 4d, 3d, 3.2d, 2d, 1d, 1d, 0.8d, 4d, 4d, 2d, 2.5d, 1d, 1d, 1d));

        SignalDetector signalDetector = new SignalDetector();
        int lag = 30;
        double threshold = 5;
        double influence = 0;

        HashMap<String, List> resultsMap = signalDetector.analyzeDataForSignals(data, lag, threshold, influence);
        // print algorithm params
        System.out.println("lag: " + lag + "\t\tthreshold: " + threshold + "\t\tinfluence: " + influence);

        System.out.println("Data size: " + data.size());
        System.out.println("Signals size: " + resultsMap.get("signals").size());

        // print data
        System.out.print("Data:\t\t");
        for (double d : data) {
            System.out.print(df.format(d) + "\t");
        }
        System.out.println();

        // print signals
        System.out.print("Signals:\t");
        List<Integer> signalsList = resultsMap.get("signals");
        for (int i : signalsList) {
            System.out.print(df.format(i) + "\t");
        }
        System.out.println();

        // print filtered data
        System.out.print("Filtered Data:\t");
        List<Double> filteredDataList = resultsMap.get("filteredData");
        for (double d : filteredDataList) {
            System.out.print(df.format(d) + "\t");
        }
        System.out.println();

        // print running average
        System.out.print("Avg Filter:\t");
        List<Double> avgFilterList = resultsMap.get("avgFilter");
        for (double d : avgFilterList) {
            System.out.print(df.format(d) + "\t");
        }
        System.out.println();

        // print running std
        System.out.print("Std filter:\t");
        List<Double> stdFilterList = resultsMap.get("stdFilter");
        for (double d : stdFilterList) {
            System.out.print(df.format(d) + "\t");
        }
        System.out.println();

        System.out.println();
        for (int i = 0; i < signalsList.size(); i++) {
            if (signalsList.get(i) != 0) {
                System.out.println("Point " + i + " gave signal " + signalsList.get(i));
            }
        }
    }
}

Ergebnisse

lag: 30     threshold: 5.0      influence: 0.0
Data size: 74
Signals size: 74
Data:           1.000   1.000   1.100   1.000   0.900   1.000   1.000   1.100   1.000   0.900   1.000   1.100   1.000   1.000   0.900   1.000   1.000   1.100   1.000   1.000   1.000   1.000   1.100   0.900   1.000   1.100   1.000   1.000   0.900   1.000   1.100   1.000   1.000   1.100   1.000   0.800   0.900   1.000   1.200   0.900   1.000   1.000   1.100   1.200   1.000   1.500   1.000   3.000   2.000   5.000   3.000   2.000   1.000   1.000   1.000   0.900   1.000   1.000   3.000   2.600   4.000   3.000   3.200   2.000   1.000   1.000   0.800   4.000   4.000   2.000   2.500   1.000   1.000   1.000   
Signals:        0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   1.000   0.000   1.000   1.000   1.000   1.000   1.000   0.000   0.000   0.000   0.000   0.000   0.000   1.000   1.000   1.000   1.000   1.000   1.000   0.000   0.000   0.000   1.000   1.000   1.000   1.000   0.000   0.000   0.000   
Filtered Data:  1.000   1.000   1.100   1.000   0.900   1.000   1.000   1.100   1.000   0.900   1.000   1.100   1.000   1.000   0.900   1.000   1.000   1.100   1.000   1.000   1.000   1.000   1.100   0.900   1.000   1.100   1.000   1.000   0.900   1.000   1.100   1.000   1.000   1.100   1.000   0.800   0.900   1.000   1.200   0.900   1.000   1.000   1.100   1.200   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   0.900   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   1.000   0.800   0.800   0.800   0.800   0.800   1.000   1.000   1.000   
Avg Filter:     0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   1.003   1.003   1.007   1.007   1.003   1.007   1.010   1.003   1.000   0.997   1.003   1.003   1.003   1.000   1.003   1.010   1.013   1.013   1.013   1.010   1.010   1.010   1.010   1.010   1.007   1.010   1.010   1.003   1.003   1.003   1.007   1.007   1.003   1.003   1.003   1.000   1.000   1.007   1.003   0.997   0.983   0.980   0.973   0.973   0.970   
Std filter:     0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.060   0.060   0.063   0.063   0.060   0.063   0.060   0.071   0.073   0.071   0.080   0.080   0.080   0.077   0.080   0.087   0.085   0.085   0.085   0.083   0.083   0.083   0.083   0.083   0.081   0.079   0.079   0.080   0.080   0.080   0.077   0.077   0.075   0.075   0.075   0.073   0.073   0.063   0.071   0.080   0.078   0.083   0.089   0.089   0.086   

Point 45 gave signal 1
Point 47 gave signal 1
Point 48 gave signal 1
Point 49 gave signal 1
Point 50 gave signal 1
Point 51 gave signal 1
Point 58 gave signal 1
Point 59 gave signal 1
Point 60 gave signal 1
Point 61 gave signal 1
Point 62 gave signal 1
Point 63 gave signal 1
Point 67 gave signal 1
Point 68 gave signal 1
Point 69 gave signal 1
Point 70 gave signal 1

Diagramme mit Daten und Ergebnissen der Java-Ausführung

takanuva15
quelle
5

Anhang 1 zur ursprünglichen Antwort: Matlabund RÜbersetzungen

Matlab-Code

function [signals,avgFilter,stdFilter] = ThresholdingAlgo(y,lag,threshold,influence)
% Initialise signal results
signals = zeros(length(y),1);
% Initialise filtered series
filteredY = y(1:lag+1);
% Initialise filters
avgFilter(lag+1,1) = mean(y(1:lag+1));
stdFilter(lag+1,1) = std(y(1:lag+1));
% Loop over all datapoints y(lag+2),...,y(t)
for i=lag+2:length(y)
    % If new value is a specified number of deviations away
    if abs(y(i)-avgFilter(i-1)) > threshold*stdFilter(i-1)
        if y(i) > avgFilter(i-1)
            % Positive signal
            signals(i) = 1;
        else
            % Negative signal
            signals(i) = -1;
        end
        % Make influence lower
        filteredY(i) = influence*y(i)+(1-influence)*filteredY(i-1);
    else
        % No signal
        signals(i) = 0;
        filteredY(i) = y(i);
    end
    % Adjust the filters
    avgFilter(i) = mean(filteredY(i-lag:i));
    stdFilter(i) = std(filteredY(i-lag:i));
end
% Done, now return results
end

Beispiel:

% Data
y = [1 1 1.1 1 0.9 1 1 1.1 1 0.9 1 1.1 1 1 0.9 1 1 1.1 1 1,...
    1 1 1.1 0.9 1 1.1 1 1 0.9 1 1.1 1 1 1.1 1 0.8 0.9 1 1.2 0.9 1,...
    1 1.1 1.2 1 1.5 1 3 2 5 3 2 1 1 1 0.9 1,...
    1 3 2.6 4 3 3.2 2 1 1 0.8 4 4 2 2.5 1 1 1];

% Settings
lag = 30;
threshold = 5;
influence = 0;

% Get results
[signals,avg,dev] = ThresholdingAlgo(y,lag,threshold,influence);

figure; subplot(2,1,1); hold on;
x = 1:length(y); ix = lag+1:length(y);
area(x(ix),avg(ix)+threshold*dev(ix),'FaceColor',[0.9 0.9 0.9],'EdgeColor','none');
area(x(ix),avg(ix)-threshold*dev(ix),'FaceColor',[1 1 1],'EdgeColor','none');
plot(x(ix),avg(ix),'LineWidth',1,'Color','cyan','LineWidth',1.5);
plot(x(ix),avg(ix)+threshold*dev(ix),'LineWidth',1,'Color','green','LineWidth',1.5);
plot(x(ix),avg(ix)-threshold*dev(ix),'LineWidth',1,'Color','green','LineWidth',1.5);
plot(1:length(y),y,'b');
subplot(2,1,2);
stairs(signals,'r','LineWidth',1.5); ylim([-1.5 1.5]);

R-Code

ThresholdingAlgo <- function(y,lag,threshold,influence) {
  signals <- rep(0,length(y))
  filteredY <- y[0:lag]
  avgFilter <- NULL
  stdFilter <- NULL
  avgFilter[lag] <- mean(y[0:lag], na.rm=TRUE)
  stdFilter[lag] <- sd(y[0:lag], na.rm=TRUE)
  for (i in (lag+1):length(y)){
    if (abs(y[i]-avgFilter[i-1]) > threshold*stdFilter[i-1]) {
      if (y[i] > avgFilter[i-1]) {
        signals[i] <- 1;
      } else {
        signals[i] <- -1;
      }
      filteredY[i] <- influence*y[i]+(1-influence)*filteredY[i-1]
    } else {
      signals[i] <- 0
      filteredY[i] <- y[i]
    }
    avgFilter[i] <- mean(filteredY[(i-lag):i], na.rm=TRUE)
    stdFilter[i] <- sd(filteredY[(i-lag):i], na.rm=TRUE)
  }
  return(list("signals"=signals,"avgFilter"=avgFilter,"stdFilter"=stdFilter))
}

Beispiel:

# Data
y <- c(1,1,1.1,1,0.9,1,1,1.1,1,0.9,1,1.1,1,1,0.9,1,1,1.1,1,1,1,1,1.1,0.9,1,1.1,1,1,0.9,
       1,1.1,1,1,1.1,1,0.8,0.9,1,1.2,0.9,1,1,1.1,1.2,1,1.5,1,3,2,5,3,2,1,1,1,0.9,1,1,3,
       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1)

lag       <- 30
threshold <- 5
influence <- 0

# Run algo with lag = 30, threshold = 5, influence = 0
result <- ThresholdingAlgo(y,lag,threshold,influence)

# Plot result
par(mfrow = c(2,1),oma = c(2,2,0,0) + 0.1,mar = c(0,0,2,1) + 0.2)
plot(1:length(y),y,type="l",ylab="",xlab="") 
lines(1:length(y),result$avgFilter,type="l",col="cyan",lwd=2)
lines(1:length(y),result$avgFilter+threshold*result$stdFilter,type="l",col="green",lwd=2)
lines(1:length(y),result$avgFilter-threshold*result$stdFilter,type="l",col="green",lwd=2)
plot(result$signals,type="S",col="red",ylab="",xlab="",ylim=c(-1.5,1.5),lwd=2)

Dieser Code (beide Sprachen) liefert das folgende Ergebnis für die Daten der ursprünglichen Frage:

Schwellenbeispiel aus Matlab-Code


Anhang 2 zur ursprünglichen Antwort: MatlabDemonstrationscode

(Klicken, um Daten zu erstellen)

Matlab-Demo

function [] = RobustThresholdingDemo()

%% SPECIFICATIONS
lag         = 5;       % lag for the smoothing
threshold   = 3.5;     % number of st.dev. away from the mean to signal
influence   = 0.3;     % when signal: how much influence for new data? (between 0 and 1)
                       % 1 is normal influence, 0.5 is half      
%% START DEMO
DemoScreen(30,lag,threshold,influence);

end

function [signals,avgFilter,stdFilter] = ThresholdingAlgo(y,lag,threshold,influence)
signals = zeros(length(y),1);
filteredY = y(1:lag+1);
avgFilter(lag+1,1) = mean(y(1:lag+1));
stdFilter(lag+1,1) = std(y(1:lag+1));
for i=lag+2:length(y)
    if abs(y(i)-avgFilter(i-1)) > threshold*stdFilter(i-1)
        if y(i) > avgFilter(i-1)
            signals(i) = 1;
        else
            signals(i) = -1;
        end
        filteredY(i) = influence*y(i)+(1-influence)*filteredY(i-1);
    else
        signals(i) = 0;
        filteredY(i) = y(i);
    end
    avgFilter(i) = mean(filteredY(i-lag:i));
    stdFilter(i) = std(filteredY(i-lag:i));
end
end

% Demo screen function
function [] = DemoScreen(n,lag,threshold,influence)
figure('Position',[200 100,1000,500]);
subplot(2,1,1);
title(sprintf(['Draw data points (%.0f max)      [settings: lag = %.0f, '...
    'threshold = %.2f, influence = %.2f]'],n,lag,threshold,influence));
ylim([0 5]); xlim([0 50]);
H = gca; subplot(2,1,1);
set(H, 'YLimMode', 'manual'); set(H, 'XLimMode', 'manual');
set(H, 'YLim', get(H,'YLim')); set(H, 'XLim', get(H,'XLim'));
xg = []; yg = [];
for i=1:n
    try
        [xi,yi] = ginput(1);
    catch
        return;
    end
    xg = [xg xi]; yg = [yg yi];
    if i == 1
        subplot(2,1,1); hold on;
        plot(H, xg(i),yg(i),'r.'); 
        text(xg(i),yg(i),num2str(i),'FontSize',7);
    end
    if length(xg) > lag
        [signals,avg,dev] = ...
            ThresholdingAlgo(yg,lag,threshold,influence);
        area(xg(lag+1:end),avg(lag+1:end)+threshold*dev(lag+1:end),...
            'FaceColor',[0.9 0.9 0.9],'EdgeColor','none');
        area(xg(lag+1:end),avg(lag+1:end)-threshold*dev(lag+1:end),...
            'FaceColor',[1 1 1],'EdgeColor','none');
        plot(xg(lag+1:end),avg(lag+1:end),'LineWidth',1,'Color','cyan');
        plot(xg(lag+1:end),avg(lag+1:end)+threshold*dev(lag+1:end),...
            'LineWidth',1,'Color','green');
        plot(xg(lag+1:end),avg(lag+1:end)-threshold*dev(lag+1:end),...
            'LineWidth',1,'Color','green');
        subplot(2,1,2); hold on; title('Signal output');
        stairs(xg(lag+1:end),signals(lag+1:end),'LineWidth',2,'Color','blue');
        ylim([-2 2]); xlim([0 50]); hold off;
    end
    subplot(2,1,1); hold on;
    for j=2:i
        plot(xg([j-1:j]),yg([j-1:j]),'r'); plot(H,xg(j),yg(j),'r.');
        text(xg(j),yg(j),num2str(j),'FontSize',7);
    end
end
end

Jean Paul
quelle
4

Hier ist mein Versuch, aus der akzeptierten Antwort eine Ruby-Lösung für das "Smoothed Z-Score Algo" zu erstellen:

module ThresholdingAlgoMixin
  def mean(array)
    array.reduce(&:+) / array.size.to_f
  end

  def stddev(array)
    array_mean = mean(array)
    Math.sqrt(array.reduce(0.0) { |a, b| a.to_f + ((b.to_f - array_mean) ** 2) } / array.size.to_f)
  end

  def thresholding_algo(lag: 5, threshold: 3.5, influence: 0.5)
    return nil if size < lag * 2
    Array.new(size, 0).tap do |signals|
      filtered = Array.new(self)

      initial_slice = take(lag)
      avg_filter = Array.new(lag - 1, 0.0) + [mean(initial_slice)]
      std_filter = Array.new(lag - 1, 0.0) + [stddev(initial_slice)]
      (lag..size-1).each do |idx|
        prev = idx - 1
        if (fetch(idx) - avg_filter[prev]).abs > threshold * std_filter[prev]
          signals[idx] = fetch(idx) > avg_filter[prev] ? 1 : -1
          filtered[idx] = (influence * fetch(idx)) + ((1-influence) * filtered[prev])
        end

        filtered_slice = filtered[idx-lag..prev]
        avg_filter[idx] = mean(filtered_slice)
        std_filter[idx] = stddev(filtered_slice)
      end
    end
  end
end

Und Anwendungsbeispiel:

test_data = [
  1, 1, 1.1, 1, 0.9, 1, 1, 1.1, 1, 0.9, 1, 1.1, 1, 1, 0.9, 1,
  1, 1.1, 1, 1, 1, 1, 1.1, 0.9, 1, 1.1, 1, 1, 0.9, 1, 1.1, 1,
  1, 1.1, 1, 0.8, 0.9, 1, 1.2, 0.9, 1, 1, 1.1, 1.2, 1, 1.5,
  1, 3, 2, 5, 3, 2, 1, 1, 1, 0.9, 1, 1, 3, 2.6, 4, 3, 3.2, 2,
  1, 1, 0.8, 4, 4, 2, 2.5, 1, 1, 1
].extend(ThresholdingAlgoMixin)

puts test_data.thresholding_algo.inspect

# Output: [
#   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
#   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0,
#   0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
#   1, 1, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0
# ]
Kimmo Lehto
quelle
Super, danke fürs Teilen! Ich werde dich zur Liste hinzufügen. Stellen Sie sicher, dass Sie für Echtzeitanwendungen eine separate Funktion erstellen, um die Signale zu aktualisieren, wenn ein neuer Datenpunkt eintrifft (anstatt jedes Mal alle Datenpunkte zu schleifen).
Jean-Paul
4

Eine iterative Version in Python / Numpy zur Beantwortung https://stackoverflow.com/a/22640362/6029703 finden Sie hier. Dieser Code ist schneller als die Berechnung des Durchschnitts und der Standardabweichung bei jeder Verzögerung für große Datenmengen (100000+).

def peak_detection_smoothed_zscore_v2(x, lag, threshold, influence):
    '''
    iterative smoothed z-score algorithm
    Implementation of algorithm from https://stackoverflow.com/a/22640362/6029703
    '''
    import numpy as np
    labels = np.zeros(len(x))
    filtered_y = np.array(x)
    avg_filter = np.zeros(len(x))
    std_filter = np.zeros(len(x))
    var_filter = np.zeros(len(x))

    avg_filter[lag - 1] = np.mean(x[0:lag])
    std_filter[lag - 1] = np.std(x[0:lag])
    var_filter[lag - 1] = np.var(x[0:lag])
    for i in range(lag, len(x)):
        if abs(x[i] - avg_filter[i - 1]) > threshold * std_filter[i - 1]:
            if x[i] > avg_filter[i - 1]:
                labels[i] = 1
            else:
                labels[i] = -1
            filtered_y[i] = influence * x[i] + (1 - influence) * filtered_y[i - 1]
        else:
            labels[i] = 0
            filtered_y[i] = x[i]
        # update avg, var, std
        avg_filter[i] = avg_filter[i - 1] + 1. / lag * (filtered_y[i] - filtered_y[i - lag])
        var_filter[i] = var_filter[i - 1] + 1. / lag * ((filtered_y[i] - avg_filter[i - 1]) ** 2 - (
            filtered_y[i - lag] - avg_filter[i - 1]) ** 2 - (filtered_y[i] - filtered_y[i - lag]) ** 2 / lag)
        std_filter[i] = np.sqrt(var_filter[i])

    return dict(signals=labels,
                avgFilter=avg_filter,
                stdFilter=std_filter)
Transfer Will
quelle
4

Ich dachte, ich würde meine Julia-Implementierung des Algorithmus für andere bereitstellen. Das Wesentliche finden Sie hier

using Statistics
using Plots
function SmoothedZscoreAlgo(y, lag, threshold, influence)
    # Julia implimentation of http://stackoverflow.com/a/22640362/6029703
    n = length(y)
    signals = zeros(n) # init signal results
    filteredY = copy(y) # init filtered series
    avgFilter = zeros(n) # init average filter
    stdFilter = zeros(n) # init std filter
    avgFilter[lag - 1] = mean(y[1:lag]) # init first value
    stdFilter[lag - 1] = std(y[1:lag]) # init first value

    for i in range(lag, stop=n-1)
        if abs(y[i] - avgFilter[i-1]) > threshold*stdFilter[i-1]
            if y[i] > avgFilter[i-1]
                signals[i] += 1 # postive signal
            else
                signals[i] += -1 # negative signal
            end
            # Make influence lower
            filteredY[i] = influence*y[i] + (1-influence)*filteredY[i-1]
        else
            signals[i] = 0
            filteredY[i] = y[i]
        end
        avgFilter[i] = mean(filteredY[i-lag+1:i])
        stdFilter[i] = std(filteredY[i-lag+1:i])
    end
    return (signals = signals, avgFilter = avgFilter, stdFilter = stdFilter)
end


# Data
y = [1,1,1.1,1,0.9,1,1,1.1,1,0.9,1,1.1,1,1,0.9,1,1,1.1,1,1,1,1,1.1,0.9,1,1.1,1,1,0.9,
       1,1.1,1,1,1.1,1,0.8,0.9,1,1.2,0.9,1,1,1.1,1.2,1,1.5,1,3,2,5,3,2,1,1,1,0.9,1,1,3,
       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1]

# Settings: lag = 30, threshold = 5, influence = 0
lag = 30
threshold = 5
influence = 0

results = SmoothedZscoreAlgo(y, lag, threshold, influence)
upper_bound = results[:avgFilter] + threshold * results[:stdFilter]
lower_bound = results[:avgFilter] - threshold * results[:stdFilter]
x = 1:length(y)

yplot = plot(x,y,color="blue", label="Y",legend=:topleft)
yplot = plot!(x,upper_bound, color="green", label="Upper Bound",legend=:topleft)
yplot = plot!(x,results[:avgFilter], color="cyan", label="Average Filter",legend=:topleft)
yplot = plot!(x,lower_bound, color="green", label="Lower Bound",legend=:topleft)
signalplot = plot(x,results[:signals],color="red",label="Signals",legend=:topleft)
plot(yplot,signalplot,layout=(2,1),legend=:topleft)

Ergebnisse

Matt Camp
quelle
3

Hier ist eine Groovy (Java) -Implementierung des geglätteten Z-Score-Algorithmus ( siehe Antwort oben ).

/**
 * "Smoothed zero-score alogrithm" shamelessly copied from https://stackoverflow.com/a/22640362/6029703
 *  Uses a rolling mean and a rolling deviation (separate) to identify peaks in a vector
 *
 * @param y - The input vector to analyze
 * @param lag - The lag of the moving window (i.e. how big the window is)
 * @param threshold - The z-score at which the algorithm signals (i.e. how many standard deviations away from the moving mean a peak (or signal) is)
 * @param influence - The influence (between 0 and 1) of new signals on the mean and standard deviation (how much a peak (or signal) should affect other values near it)
 * @return - The calculated averages (avgFilter) and deviations (stdFilter), and the signals (signals)
 */

public HashMap<String, List<Object>> thresholdingAlgo(List<Double> y, Long lag, Double threshold, Double influence) {
    //init stats instance
    SummaryStatistics stats = new SummaryStatistics()

    //the results (peaks, 1 or -1) of our algorithm
    List<Integer> signals = new ArrayList<Integer>(Collections.nCopies(y.size(), 0))
    //filter out the signals (peaks) from our original list (using influence arg)
    List<Double> filteredY = new ArrayList<Double>(y)
    //the current average of the rolling window
    List<Double> avgFilter = new ArrayList<Double>(Collections.nCopies(y.size(), 0.0d))
    //the current standard deviation of the rolling window
    List<Double> stdFilter = new ArrayList<Double>(Collections.nCopies(y.size(), 0.0d))
    //init avgFilter and stdFilter
    (0..lag-1).each { stats.addValue(y[it as int]) }
    avgFilter[lag - 1 as int] = stats.getMean()
    stdFilter[lag - 1 as int] = Math.sqrt(stats.getPopulationVariance()) //getStandardDeviation() uses sample variance (not what we want)
    stats.clear()
    //loop input starting at end of rolling window
    (lag..y.size()-1).each { i ->
        //if the distance between the current value and average is enough standard deviations (threshold) away
        if (Math.abs((y[i as int] - avgFilter[i - 1 as int]) as Double) > threshold * stdFilter[i - 1 as int]) {
            //this is a signal (i.e. peak), determine if it is a positive or negative signal
            signals[i as int] = (y[i as int] > avgFilter[i - 1 as int]) ? 1 : -1
            //filter this signal out using influence
            filteredY[i as int] = (influence * y[i as int]) + ((1-influence) * filteredY[i - 1 as int])
        } else {
            //ensure this signal remains a zero
            signals[i as int] = 0
            //ensure this value is not filtered
            filteredY[i as int] = y[i as int]
        }
        //update rolling average and deviation
        (i - lag..i-1).each { stats.addValue(filteredY[it as int] as Double) }
        avgFilter[i as int] = stats.getMean()
        stdFilter[i as int] = Math.sqrt(stats.getPopulationVariance()) //getStandardDeviation() uses sample variance (not what we want)
        stats.clear()
    }

    return [
        signals  : signals,
        avgFilter: avgFilter,
        stdFilter: stdFilter
    ]
}

Im Folgenden finden Sie einen Test für denselben Datensatz, der dieselben Ergebnisse wie die obige Python / Numpy-Implementierung liefert .

    // Data
    def y = [1d, 1d, 1.1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 0.9d, 1d, 1.1d, 1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 1d,
         1d, 1d, 1.1d, 0.9d, 1d, 1.1d, 1d, 1d, 0.9d, 1d, 1.1d, 1d, 1d, 1.1d, 1d, 0.8d, 0.9d, 1d, 1.2d, 0.9d, 1d,
         1d, 1.1d, 1.2d, 1d, 1.5d, 1d, 3d, 2d, 5d, 3d, 2d, 1d, 1d, 1d, 0.9d, 1d,
         1d, 3d, 2.6d, 4d, 3d, 3.2d, 2d, 1d, 1d, 0.8d, 4d, 4d, 2d, 2.5d, 1d, 1d, 1d]

    // Settings
    def lag = 30
    def threshold = 5
    def influence = 0


    def thresholdingResults = thresholdingAlgo((List<Double>) y, (Long) lag, (Double) threshold, (Double) influence)

    println y.size()
    println thresholdingResults.signals.size()
    println thresholdingResults.signals

    thresholdingResults.signals.eachWithIndex { x, idx ->
        if (x) {
            println y[idx]
        }
    }
JoshuaCWebDeveloper
quelle
3

Hier ist eine (nicht idiomatische) Scala-Version des geglätteten Z-Score-Algorithmus :

/**
  * Smoothed zero-score alogrithm shamelessly copied from https://stackoverflow.com/a/22640362/6029703
  * Uses a rolling mean and a rolling deviation (separate) to identify peaks in a vector
  *
  * @param y - The input vector to analyze
  * @param lag - The lag of the moving window (i.e. how big the window is)
  * @param threshold - The z-score at which the algorithm signals (i.e. how many standard deviations away from the moving mean a peak (or signal) is)
  * @param influence - The influence (between 0 and 1) of new signals on the mean and standard deviation (how much a peak (or signal) should affect other values near it)
  * @return - The calculated averages (avgFilter) and deviations (stdFilter), and the signals (signals)
  */
private def smoothedZScore(y: Seq[Double], lag: Int, threshold: Double, influence: Double): Seq[Int] = {
  val stats = new SummaryStatistics()

  // the results (peaks, 1 or -1) of our algorithm
  val signals = mutable.ArrayBuffer.fill(y.length)(0)

  // filter out the signals (peaks) from our original list (using influence arg)
  val filteredY = y.to[mutable.ArrayBuffer]

  // the current average of the rolling window
  val avgFilter = mutable.ArrayBuffer.fill(y.length)(0d)

  // the current standard deviation of the rolling window
  val stdFilter = mutable.ArrayBuffer.fill(y.length)(0d)

  // init avgFilter and stdFilter
  y.take(lag).foreach(s => stats.addValue(s))

  avgFilter(lag - 1) = stats.getMean
  stdFilter(lag - 1) = Math.sqrt(stats.getPopulationVariance) // getStandardDeviation() uses sample variance (not what we want)

  // loop input starting at end of rolling window
  y.zipWithIndex.slice(lag, y.length - 1).foreach {
    case (s: Double, i: Int) =>
      // if the distance between the current value and average is enough standard deviations (threshold) away
      if (Math.abs(s - avgFilter(i - 1)) > threshold * stdFilter(i - 1)) {
        // this is a signal (i.e. peak), determine if it is a positive or negative signal
        signals(i) = if (s > avgFilter(i - 1)) 1 else -1
        // filter this signal out using influence
        filteredY(i) = (influence * s) + ((1 - influence) * filteredY(i - 1))
      } else {
        // ensure this signal remains a zero
        signals(i) = 0
        // ensure this value is not filtered
        filteredY(i) = s
      }

      // update rolling average and deviation
      stats.clear()
      filteredY.slice(i - lag, i).foreach(s => stats.addValue(s))
      avgFilter(i) = stats.getMean
      stdFilter(i) = Math.sqrt(stats.getPopulationVariance) // getStandardDeviation() uses sample variance (not what we want)
  }

  println(y.length)
  println(signals.length)
  println(signals)

  signals.zipWithIndex.foreach {
    case(x: Int, idx: Int) =>
      if (x == 1) {
        println(idx + " " + y(idx))
      }
  }

  val data =
    y.zipWithIndex.map { case (s: Double, i: Int) => Map("x" -> i, "y" -> s, "name" -> "y", "row" -> "data") } ++
    avgFilter.zipWithIndex.map { case (s: Double, i: Int) => Map("x" -> i, "y" -> s, "name" -> "avgFilter", "row" -> "data") } ++
    avgFilter.zipWithIndex.map { case (s: Double, i: Int) => Map("x" -> i, "y" -> (s - threshold * stdFilter(i)), "name" -> "lower", "row" -> "data") } ++
    avgFilter.zipWithIndex.map { case (s: Double, i: Int) => Map("x" -> i, "y" -> (s + threshold * stdFilter(i)), "name" -> "upper", "row" -> "data") } ++
    signals.zipWithIndex.map { case (s: Int, i: Int) => Map("x" -> i, "y" -> s, "name" -> "signal", "row" -> "signal") }

  Vegas("Smoothed Z")
    .withData(data)
    .mark(Line)
    .encodeX("x", Quant)
    .encodeY("y", Quant)
    .encodeColor(
      field="name",
      dataType=Nominal
    )
    .encodeRow("row", Ordinal)
    .show

  return signals
}

Hier ist ein Test, der dieselben Ergebnisse wie die Versionen Python und Groovy liefert:

val y = List(1d, 1d, 1.1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 0.9d, 1d, 1.1d, 1d, 1d, 0.9d, 1d, 1d, 1.1d, 1d, 1d,
  1d, 1d, 1.1d, 0.9d, 1d, 1.1d, 1d, 1d, 0.9d, 1d, 1.1d, 1d, 1d, 1.1d, 1d, 0.8d, 0.9d, 1d, 1.2d, 0.9d, 1d,
  1d, 1.1d, 1.2d, 1d, 1.5d, 1d, 3d, 2d, 5d, 3d, 2d, 1d, 1d, 1d, 0.9d, 1d,
  1d, 3d, 2.6d, 4d, 3d, 3.2d, 2d, 1d, 1d, 0.8d, 4d, 4d, 2d, 2.5d, 1d, 1d, 1d)

val lag = 30
val threshold = 5d
val influence = 0d

smoothedZScore(y, lag, threshold, influence)

Vegas Diagramm des Ergebnisses

Kern hier

Mike Roberts
quelle
1 steht für Spitzen, -1 für Täler.
Mike Roberts
3

Ich brauchte so etwas in meinem Android-Projekt. Ich dachte, ich könnte die Kotlin- Implementierung zurückgeben.

/**
* Smoothed zero-score alogrithm shamelessly copied from https://stackoverflow.com/a/22640362/6029703
* Uses a rolling mean and a rolling deviation (separate) to identify peaks in a vector
*
* @param y - The input vector to analyze
* @param lag - The lag of the moving window (i.e. how big the window is)
* @param threshold - The z-score at which the algorithm signals (i.e. how many standard deviations away from the moving mean a peak (or signal) is)
* @param influence - The influence (between 0 and 1) of new signals on the mean and standard deviation (how much a peak (or signal) should affect other values near it)
* @return - The calculated averages (avgFilter) and deviations (stdFilter), and the signals (signals)
*/
fun smoothedZScore(y: List<Double>, lag: Int, threshold: Double, influence: Double): Triple<List<Int>, List<Double>, List<Double>> {
    val stats = SummaryStatistics()
    // the results (peaks, 1 or -1) of our algorithm
    val signals = MutableList<Int>(y.size, { 0 })
    // filter out the signals (peaks) from our original list (using influence arg)
    val filteredY = ArrayList<Double>(y)
    // the current average of the rolling window
    val avgFilter = MutableList<Double>(y.size, { 0.0 })
    // the current standard deviation of the rolling window
    val stdFilter = MutableList<Double>(y.size, { 0.0 })
    // init avgFilter and stdFilter
    y.take(lag).forEach { s -> stats.addValue(s) }
    avgFilter[lag - 1] = stats.mean
    stdFilter[lag - 1] = Math.sqrt(stats.populationVariance) // getStandardDeviation() uses sample variance (not what we want)
    stats.clear()
    //loop input starting at end of rolling window
    (lag..y.size - 1).forEach { i ->
        //if the distance between the current value and average is enough standard deviations (threshold) away
        if (Math.abs(y[i] - avgFilter[i - 1]) > threshold * stdFilter[i - 1]) {
            //this is a signal (i.e. peak), determine if it is a positive or negative signal
            signals[i] = if (y[i] > avgFilter[i - 1]) 1 else -1
            //filter this signal out using influence
            filteredY[i] = (influence * y[i]) + ((1 - influence) * filteredY[i - 1])
        } else {
            //ensure this signal remains a zero
            signals[i] = 0
            //ensure this value is not filtered
            filteredY[i] = y[i]
        }
        //update rolling average and deviation
        (i - lag..i - 1).forEach { stats.addValue(filteredY[it]) }
        avgFilter[i] = stats.getMean()
        stdFilter[i] = Math.sqrt(stats.getPopulationVariance()) //getStandardDeviation() uses sample variance (not what we want)
        stats.clear()
    }
    return Triple(signals, avgFilter, stdFilter)
}

Ein Beispielprojekt mit Verifizierungsdiagrammen finden Sie bei github .

Geben Sie hier die Bildbeschreibung ein

leonardkraemer
quelle
Genial! Danke für das Teilen. Stellen Sie für Echtzeitanwendungen sicher, dass Sie eine separate Funktion erstellen, die das neue Signal mit jedem eingehenden Datenpunkt berechnet. Schleifen Sie nicht jedes Mal die vollständigen Daten, wenn ein neuer Datenpunkt eintrifft, das wäre äußerst ineffizient :)
Jean-Paul
1
Guter Punkt, habe nicht darüber nachgedacht, weil sich die Fenster, die ich benutze, nicht überlappen.
Leonardkraemer
3

Hier ist eine geänderte Fortran-Version des Z-Score-Algorithmus . Es wurde speziell für die Spitzen- (Resonanz-) Erkennung in Übertragungsfunktionen im Frequenzraum geändert (jede Änderung hat einen kleinen Kommentar im Code).

Die erste Änderung warnt den Benutzer, wenn in der Nähe der Untergrenze des Eingabevektors eine Resonanz vorliegt, die durch eine Standardabweichung angezeigt wird, die über einem bestimmten Schwellenwert liegt (in diesem Fall 10%). Dies bedeutet einfach, dass das Signal nicht flach genug ist, um die Filter ordnungsgemäß zu initialisieren.

Die zweite Modifikation besteht darin, dass nur der höchste Wert eines Peaks zu den gefundenen Peaks addiert wird. Dies wird erreicht, indem jeder gefundene Spitzenwert mit der Größe seiner (Verzögerungs-) Vorgänger und seiner (Verzögerungs-) Nachfolger verglichen wird.

Die dritte Änderung besteht darin, zu berücksichtigen, dass Resonanzspitzen normalerweise irgendeine Form von Symmetrie um die Resonanzfrequenz zeigen. Daher ist es natürlich, den Mittelwert und den Standard symmetrisch um den aktuellen Datenpunkt zu berechnen (und nicht nur für die Vorgänger). Dies führt zu einem besseren Peakerkennungsverhalten.

Die Modifikationen haben zur Folge, dass das gesamte Signal der Funktion vorher bekannt sein muss, was bei der Resonanzerkennung üblich ist (so etwas wie das Matlab-Beispiel von Jean-Paul, bei dem die Datenpunkte im laufenden Betrieb erzeugt werden, funktioniert nicht).

function PeakDetect(y,lag,threshold, influence)
    implicit none
    ! Declaring part
    real, dimension(:), intent(in) :: y
    integer, dimension(size(y)) :: PeakDetect
    real, dimension(size(y)) :: filteredY, avgFilter, stdFilter
    integer :: lag, ii
    real :: threshold, influence

    ! Executing part
    PeakDetect = 0
    filteredY = 0.0
    filteredY(1:lag+1) = y(1:lag+1)
    avgFilter = 0.0
    avgFilter(lag+1) = mean(y(1:2*lag+1))
    stdFilter = 0.0
    stdFilter(lag+1) = std(y(1:2*lag+1))

    if (stdFilter(lag+1)/avgFilter(lag+1)>0.1) then ! If the coefficient of variation exceeds 10%, the signal is too uneven at the start, possibly because of a peak.
        write(unit=*,fmt=1001)
1001        format(1X,'Warning: Peak detection might have failed, as there may be a peak at the edge of the frequency range.',/)
    end if
    do ii = lag+2, size(y)
        if (abs(y(ii) - avgFilter(ii-1)) > threshold * stdFilter(ii-1)) then
            ! Find only the largest outstanding value which is only the one greater than its predecessor and its successor
            if (y(ii) > avgFilter(ii-1) .AND. y(ii) > y(ii-1) .AND. y(ii) > y(ii+1)) then
                PeakDetect(ii) = 1
            end if
            filteredY(ii) = influence * y(ii) + (1 - influence) * filteredY(ii-1)
        else
            filteredY(ii) = y(ii)
        end if
        ! Modified with respect to the original code. Mean and standard deviation are calculted symmetrically around the current point
        avgFilter(ii) = mean(filteredY(ii-lag:ii+lag))
        stdFilter(ii) = std(filteredY(ii-lag:ii+lag))
    end do
end function PeakDetect

real function mean(y)
    !> @brief Calculates the mean of vector y
    implicit none
    ! Declaring part
    real, dimension(:), intent(in) :: y
    integer :: N
    ! Executing part
    N = max(1,size(y))
    mean = sum(y)/N
end function mean

real function std(y)
    !> @brief Calculates the standard deviation of vector y
    implicit none
    ! Declaring part
    real, dimension(:), intent(in) :: y
    integer :: N
    ! Executing part
    N = max(1,size(y))
    std = sqrt((N*dot_product(y,y) - sum(y)**2) / (N*(N-1)))
end function std

Für meine Anwendung funktioniert der Algorithmus wie ein Zauber! Geben Sie hier die Bildbeschreibung ein

THo
quelle
3

Wenn Sie Ihre Daten in einer Datenbanktabelle gespeichert haben, finden Sie hier eine SQL-Version eines einfachen Z-Score-Algorithmus:

with data_with_zscore as (
    select
        date_time,
        value,
        value / (avg(value) over ()) as pct_of_mean,
        (value - avg(value) over ()) / (stdev(value) over ()) as z_score
    from {{tablename}}  where datetime > '2018-11-26' and datetime < '2018-12-03'
)


-- select all
select * from data_with_zscore 

-- select only points greater than a certain threshold
select * from data_with_zscore where z_score > abs(2)
Ocean Airdrop
quelle
Ihr Code macht etwas anderes als den von mir vorgeschlagenen Algorithmus. Ihre Abfrage berechnet einfach Z-Scores ([Datenpunkt - Mittelwert] / Standard), enthält jedoch nicht die Logik meines Algorithmus, der vergangene Signale bei der Berechnung neuer Signalschwellen ignoriert. Sie ignorieren auch die drei Parameter (Verzögerung, Einfluss, Schwelle). Könnten Sie Ihre Antwort überarbeiten, um die eigentliche Logik aufzunehmen?
Jean-Paul
1
Ja du hast Recht. Zuerst dachte ich, ich könnte mit der oben genannten vereinfachten Version durchkommen. Seitdem habe ich Ihre vollständige Lösung genommen und auf C # portiert. Siehe meine Antwort unten. Wenn ich mehr Zeit habe, werde ich diese SQL-Version erneut besuchen und Ihren Algorithmus einbeziehen. Übrigens, danke für diese großartige Antwort und visuelle Erklärung.
Ocean Airdrop
Kein Problem und froh, dass der Algorithmus Ihnen helfen konnte! Vielen Dank für Ihre C # -Einreichung, die noch fehlte. Ich werde es der Liste der Übersetzungen hinzufügen!
Jean-Paul
3

Python-Version, die mit Echtzeit-Streams arbeitet (berechnet nicht alle Datenpunkte bei Ankunft jedes neuen Datenpunkts neu). Vielleicht möchten Sie die Rückgabe der Klassenfunktion optimieren - für meine Zwecke brauchte ich nur die Signale.

import numpy as np

class real_time_peak_detection():
    def __init__(self, array, lag, threshold, influence):
        self.y = list(array)
        self.length = len(self.y)
        self.lag = lag
        self.threshold = threshold
        self.influence = influence
        self.signals = [0] * len(self.y)
        self.filteredY = np.array(self.y).tolist()
        self.avgFilter = [0] * len(self.y)
        self.stdFilter = [0] * len(self.y)
        self.avgFilter[self.lag - 1] = np.mean(self.y[0:self.lag]).tolist()
        self.stdFilter[self.lag - 1] = np.std(self.y[0:self.lag]).tolist()

    def thresholding_algo(self, new_value):
        self.y.append(new_value)
        i = len(self.y) - 1
        self.length = len(self.y)
        if i < self.lag:
            return 0
        elif i == self.lag:
            self.signals = [0] * len(self.y)
            self.filteredY = np.array(self.y).tolist()
            self.avgFilter = [0] * len(self.y)
            self.stdFilter = [0] * len(self.y)
            self.avgFilter[self.lag - 1] = np.mean(self.y[0:self.lag]).tolist()
            self.stdFilter[self.lag - 1] = np.std(self.y[0:self.lag]).tolist()
            return 0

        self.signals += [0]
        self.filteredY += [0]
        self.avgFilter += [0]
        self.stdFilter += [0]

        if abs(self.y[i] - self.avgFilter[i - 1]) > self.threshold * self.stdFilter[i - 1]:
            if self.y[i] > self.avgFilter[i - 1]:
                self.signals[i] = 1
            else:
                self.signals[i] = -1

            self.filteredY[i] = self.influence * self.y[i] + (1 - self.influence) * self.filteredY[i - 1]
            self.avgFilter[i] = np.mean(self.filteredY[(i - self.lag):i])
            self.stdFilter[i] = np.std(self.filteredY[(i - self.lag):i])
        else:
            self.signals[i] = 0
            self.filteredY[i] = self.y[i]
            self.avgFilter[i] = np.mean(self.filteredY[(i - self.lag):i])
            self.stdFilter[i] = np.std(self.filteredY[(i - self.lag):i])

        return self.signals[i]
Delica
quelle
Vielen Dank für die Veröffentlichung, ich habe Ihre Übersetzung zur Liste hinzugefügt.
Jean-Paul
3

Ich habe mir erlaubt, eine Javascript-Version davon zu erstellen. Könnte es hilfreich sein. Das Javascript sollte eine direkte Transkription des oben angegebenen Pseudocodes sein. Verfügbar als npm-Paket und Github-Repo:

Javascript Übersetzung:

// javascript port of: /programming/22583391/peak-signal-detection-in-realtime-timeseries-data/48895639#48895639

function sum(a) {
    return a.reduce((acc, val) => acc + val)
}

function mean(a) {
    return sum(a) / a.length
}

function stddev(arr) {
    const arr_mean = mean(arr)
    const r = function(acc, val) {
        return acc + ((val - arr_mean) * (val - arr_mean))
    }
    return Math.sqrt(arr.reduce(r, 0.0) / arr.length)
}

function smoothed_z_score(y, params) {
    var p = params || {}
    // init cooefficients
    const lag = p.lag || 5
    const threshold = p.threshold || 3.5
    const influence = p.influece || 0.5

    if (y === undefined || y.length < lag + 2) {
        throw ` ## y data array to short(${y.length}) for given lag of ${lag}`
    }
    //console.log(`lag, threshold, influence: ${lag}, ${threshold}, ${influence}`)

    // init variables
    var signals = Array(y.length).fill(0)
    var filteredY = y.slice(0)
    const lead_in = y.slice(0, lag)
    //console.log("1: " + lead_in.toString())

    var avgFilter = []
    avgFilter[lag - 1] = mean(lead_in)
    var stdFilter = []
    stdFilter[lag - 1] = stddev(lead_in)
    //console.log("2: " + stdFilter.toString())

    for (var i = lag; i < y.length; i++) {
        //console.log(`${y[i]}, ${avgFilter[i-1]}, ${threshold}, ${stdFilter[i-1]}`)
        if (Math.abs(y[i] - avgFilter[i - 1]) > (threshold * stdFilter[i - 1])) {
            if (y[i] > avgFilter[i - 1]) {
                signals[i] = +1 // positive signal
            } else {
                signals[i] = -1 // negative signal
            }
            // make influence lower
            filteredY[i] = influence * y[i] + (1 - influence) * filteredY[i - 1]
        } else {
            signals[i] = 0 // no signal
            filteredY[i] = y[i]
        }

        // adjust the filters
        const y_lag = filteredY.slice(i - lag, i)
        avgFilter[i] = mean(y_lag)
        stdFilter[i] = stddev(y_lag)
    }

    return signals
}

module.exports = smoothed_z_score
Dirk Lüsebrink
quelle
Vielen Dank für die Veröffentlichung Ihrer Übersetzung. Ich habe Ihren Code zu Ihrer Antwort hinzugefügt, damit die Leute ihn schnell sehen können. Ich werde Ihre Übersetzung zur Liste hinzufügen.
Jean-Paul
Inzwischen habe ich einen anderen Algorithmus auf Javascript portiert. Diesmal von numercial pyhon, das mir mehr Kontrolle gibt und besser für mich funktioniert. Auch in npm verpackt und Sie können mehr Informationen über die Algo von der Washington State University auf ihrer Jupyter-Seite finden, die Sie dafür haben. npmjs.com/package/@joe_six/duarte-watanabe-peak-detection
Dirk Lüsebrink
2

Wenn der Grenzwert oder andere Kriterien von zukünftigen Werten abhängen, besteht die einzige Lösung (ohne Zeitmaschine oder andere Kenntnis zukünftiger Werte) darin, eine Entscheidung zu verzögern, bis genügend zukünftige Werte vorliegen. Wenn Sie ein Niveau über einem Mittelwert von beispielsweise 20 Punkten wünschen, müssen Sie warten, bis Sie mindestens 19 Punkte vor einer Spitzenentscheidung haben. Andernfalls könnte der nächste neue Punkt Ihre Schwelle vor 19 Punkten vollständig überschreiten .

Ihr aktuelles Diagramm weist keine Spitzen auf ... es sei denn, Sie wissen im Voraus, dass der nächste Punkt nicht 1e99 ist, was nach einer Neuskalierung der Y-Dimension Ihres Diagramms bis zu diesem Punkt flach wäre.

hotpaw2
quelle
Wie ich bereits sagte, können wir davon ausgehen, dass ein Peak, der auftritt, so groß ist wie die Peaks im Bild und erheblich von den „normalen“ Werten abweicht.
Jean-Paul
Wenn Sie im Voraus wissen, wie groß die Peaks sein werden, stellen Sie Ihren Mittelwert und / oder Schwellenwert auf knapp unter diesen Wert ein.
hotpaw2
1
Und genau das weiß ich nicht im Voraus.
Jean-Paul
1
Sie haben sich nur widersprochen und geschrieben, dass die Spitzen bekanntermaßen die Größe auf dem Bild haben. Entweder du weißt das oder du weißt es nicht.
hotpaw2
2
Ich versuche es dir zu erklären. Sie haben jetzt die richtige Idee? "Wie man signifikant große Peaks identifiziert". Sie können das Problem entweder statistisch oder mit einem intelligenten Algorithmus angehen. Mit .. As large as in the picturemeinte ich: für ähnliche Situationen, in denen es signifikante Spitzen und Grundgeräusche gibt.
Jean-Paul
2

Und hier kommt die PHP-Implementierung des ZSCORE-Algo:

<?php
$y = array(1,7,1.1,1,0.9,1,1,1.1,1,0.9,1,1.1,1,1,0.9,1,1,1.1,1,1,1,1,1.1,0.9,1,1.1,1,1,0.9,
       1,1.1,1,1,1.1,1,0.8,0.9,1,1.2,0.9,1,1,1.1,1.2,1,1.5,10,3,2,5,3,2,1,1,1,0.9,1,1,3,
       2.6,4,3,3.2,2,1,1,0.8,4,4,2,2.5,1,1,1);

function mean($data, $start, $len) {
    $avg = 0;
    for ($i = $start; $i < $start+ $len; $i ++)
        $avg += $data[$i];
    return $avg / $len;
}

function stddev($data, $start,$len) {
    $mean = mean($data,$start,$len);
    $dev = 0;
    for ($i = $start; $i < $start+$len; $i++) 
        $dev += (($data[$i] - $mean) * ($data[$i] - $mean));
    return sqrt($dev / $len);
}

function zscore($data, $len, $lag= 20, $threshold = 1, $influence = 1) {

    $signals = array();
    $avgFilter = array();
    $stdFilter = array();
    $filteredY = array();
    $avgFilter[$lag - 1] = mean($data, 0, $lag);
    $stdFilter[$lag - 1] = stddev($data, 0, $lag);

    for ($i = 0; $i < $len; $i++) {
        $filteredY[$i] = $data[$i];
        $signals[$i] = 0;
    }


    for ($i=$lag; $i < $len; $i++) {
        if (abs($data[$i] - $avgFilter[$i-1]) > $threshold * $stdFilter[$lag - 1]) {
            if ($data[$i] > $avgFilter[$i-1]) {
                $signals[$i] = 1;
            }
            else {
                $signals[$i] = -1;
            }
            $filteredY[$i] = $influence * $data[$i] + (1 - $influence) * $filteredY[$i-1];
        } 
        else {
            $signals[$i] = 0;
            $filteredY[$i] = $data[$i];
        }

        $avgFilter[$i] = mean($filteredY, $i - $lag, $lag);
        $stdFilter[$i] = stddev($filteredY, $i - $lag, $lag);
    }
    return $signals;
}

$sig = zscore($y, count($y));

print_r($y); echo "<br><br>";
print_r($sig); echo "<br><br>";

for ($i = 0; $i < count($y); $i++) echo $i. " " . $y[$i]. " ". $sig[$i]."<br>";

?>
Radhoo
quelle
Vielen Dank für die Veröffentlichung, ich habe Ihre Übersetzung zur Liste hinzugefügt.
Jean-Paul
1
Ein Kommentar: Da dieser Algorithmus wird meist auf abgetasteten Daten verwendet werden, empfehle ich Ihnen die Umsetzung Probenstandardabweichung durch , indem man ($len - 1)statt $leninstddev()
Jean-Paul
1

Anstatt ein Maximum mit dem Mittelwert zu vergleichen, kann man die Maxima auch mit benachbarten Minima vergleichen, wobei die Minima nur oberhalb einer Rauschschwelle definiert sind. Wenn das lokale Maximum> 3-mal (oder ein anderer Konfidenzfaktor) eines der benachbarten Minima ist, dann ist dieses Maximum ein Peak. Die Peakbestimmung ist bei breiteren beweglichen Fenstern genauer. Das obige verwendet übrigens eine Berechnung, die in der Mitte des Fensters zentriert ist, und keine Berechnung am Ende des Fensters (== Verzögerung).

Beachten Sie, dass ein Maximum als Zunahme des Signals vor und Abnahme nach dem Signal gesehen werden muss.

Nichole
quelle
1

Die Funktion ist scipy.signal.find_peaks, wie der Name schon sagt, hierfür nützlich. Aber es ist wichtig , gut seine Parameter zu verstehen width, threshold, distance und vor allemprominence eine gute Spitzen Extraktion zu erhalten.

Nach meinen Tests und der Dokumentation ist das Konzept der Bekanntheit "das nützliche Konzept", um die guten Spitzen beizubehalten und die lauten Spitzen zu verwerfen.

Was ist (topografische) Bedeutung ? Es ist "die Mindesthöhe, die erforderlich ist, um vom Gipfel in ein höheres Gelände zu gelangen" , wie hier zu sehen ist:

Die Idee ist:

Je höher der Bekanntheitsgrad, desto "wichtiger" ist der Peak.

mrk
quelle
1

Objektorientierte Version des Z-Score-Algorithmus mit moderner C +++

template<typename T>
class FindPeaks{
private:
    std::vector<T> m_input_signal;                      // stores input vector
    std::vector<T> m_array_peak_positive;               
    std::vector<T> m_array_peak_negative;               

public:
    FindPeaks(const std::vector<T>& t_input_signal): m_input_signal{t_input_signal}{ }

    void estimate(){
        int lag{5};
        T threshold{ 5 };                                                                                       // set a threshold
        T influence{ 0.5 };                                                                                    // value between 0 to 1, 1 is normal influence and 0.5 is half the influence

        std::vector<T> filtered_signal(m_input_signal.size(), 0.0);                                             // placeholdered for smooth signal, initialie with all zeros
        std::vector<int> signal(m_input_signal.size(), 0);                                                          // vector that stores where the negative and positive located
        std::vector<T> avg_filtered(m_input_signal.size(), 0.0);                                                // moving averages
        std::vector<T> std_filtered(m_input_signal.size(), 0.0);                                                // moving standard deviation

        avg_filtered[lag] = findMean(m_input_signal.begin(), m_input_signal.begin() + lag);                         // pass the iteartor to vector
        std_filtered[lag] = findStandardDeviation(m_input_signal.begin(), m_input_signal.begin() + lag);

        for (size_t iLag = lag + 1; iLag < m_input_signal.size(); ++iLag) {                                         // start index frm 
            if (std::abs(m_input_signal[iLag] - avg_filtered[iLag - 1]) > threshold * std_filtered[iLag - 1]) {     // check if value is above threhold             
                if ((m_input_signal[iLag]) > avg_filtered[iLag - 1]) {
                    signal[iLag] = 1;                                                                               // assign positive signal
                }
                else {
                    signal[iLag] = -1;                                                                                  // assign negative signal
                }
                filtered_signal[iLag] = influence * m_input_signal[iLag] + (1 - influence) * filtered_signal[iLag - 1];        // exponential smoothing
            }
            else {
                signal[iLag] = 0;                                                                                         // no signal
                filtered_signal[iLag] = m_input_signal[iLag];
            }

            avg_filtered[iLag] = findMean(filtered_signal.begin() + (iLag - lag), filtered_signal.begin() + iLag);
            std_filtered[iLag] = findStandardDeviation(filtered_signal.begin() + (iLag - lag), filtered_signal.begin() + iLag);

        }

        for (size_t iSignal = 0; iSignal < m_input_signal.size(); ++iSignal) {
            if (signal[iSignal] == 1) {
                m_array_peak_positive.emplace_back(m_input_signal[iSignal]);                                        // store the positive peaks
            }
            else if (signal[iSignal] == -1) {
                m_array_peak_negative.emplace_back(m_input_signal[iSignal]);                                         // store the negative peaks
            }
        }
        printVoltagePeaks(signal, m_input_signal);

    }

    std::pair< std::vector<T>, std::vector<T> > get_peaks()
    {
        return std::make_pair(m_array_peak_negative, m_array_peak_negative);
    }

};


template<typename T1, typename T2 >
void printVoltagePeaks(std::vector<T1>& m_signal, std::vector<T2>& m_input_signal) {
    std::ofstream output_file("./voltage_peak.csv");
    std::ostream_iterator<T2> output_iterator_voltage(output_file, ",");
    std::ostream_iterator<T1> output_iterator_signal(output_file, ",");
    std::copy(m_input_signal.begin(), m_input_signal.end(), output_iterator_voltage);
    output_file << "\n";
    std::copy(m_signal.begin(), m_signal.end(), output_iterator_signal);
}

template<typename iterator_type>
typename std::iterator_traits<iterator_type>::value_type findMean(iterator_type it, iterator_type end)
{
    /* function that receives iterator to*/
    typename std::iterator_traits<iterator_type>::value_type sum{ 0.0 };
    int counter = 0;
    while (it != end) {
        sum += *(it++);
        counter++;
    }
    return sum / counter;
}

template<typename iterator_type>
typename std::iterator_traits<iterator_type>::value_type findStandardDeviation(iterator_type it, iterator_type end)
{
    auto mean = findMean(it, end);
    typename std::iterator_traits<iterator_type>::value_type sum_squared_error{ 0.0 };
    int counter{ 0 };
    while (it != end) {
        sum_squared_error += std::pow((*(it++) - mean), 2);
        counter++;
    }
    auto standard_deviation = std::sqrt(sum_squared_error / (counter - 1));
    return standard_deviation;
}
Spandyie
quelle
2
Schöne Übersetzung. Es wäre etwas besser aus, wenn das Objekt speichert auch die filtered_signal, signal, avg_filteredund std_filteredals private Variablen und aktualisiert nur die Arrays einmal , wenn ein neuer Datenpunkt kommt (jetzt die Code Schleifen über alle Datenpunkte jedes Mal sie genannt wird). Das würde die Leistung Ihres Codes verbessern und passt noch besser zur OOP-Struktur.
Jean-Paul