[PYTHON] Finde einen Wendepunkt! [Extrahieren von Änderungspunkten in Zeitreihen mit dem Änderungsfinder]

Hintergrund

Ich mag Geschichtsbücher und lese sie gelegentlich. Kürzlich habe ich [Essence of Failure] gelesen (https://www.amazon.co.jp/dp/4122018331). Dieses Buch war sehr interessant, weil es darüber sprach, was am Wendepunkt des Pazifikkrieges aus Sicht der Organisationstheorie geschah. Während ich dieses Buch las, fragte ich mich: "Ist der Wendepunkt etwas, das zurückgeschaut und quantitativ erfasst werden kann?" Dann war da. Ein Algorithmus, der Änderungen in Zeitreihen extrahiert.

17c1dfeb.jpg

Arten von Anomalieerkennungs- / Änderungserkennungsproblemen

Was für ein Problem gibt es überhaupt bei der Erkennung von Anomalien / Änderungen? Einführung in die Erkennung von Anomalien Ich habe versucht, mit Bezug auf Seite 12 von in 3 zu klassifizieren.

Aufgabe Überblick
Ausreißererkennungsproblem statisch. Ist ein Datenpunkt signifikant außerhalb der Verteilung?
Änderungspunkterkennungsproblem dynamisch. Ob sich das Thema geändert hat oder nicht, wo ist der Punkt?
Erkennung abnormaler Zustände dynamisch. Ist der aktuelle Zustand des Ziels abnormal oder normal?

Wenn Sie anfangen, konkreter zu schreiben, wird es ein super langer Satz sein, also werde ich ihn dieses Mal überspringen. Für diejenigen, die die Umrisse der Anomalieerkennung / Änderungserkennung kennen möchten, wird der Artikel Zusammenfassung der Anomalieerkennung und Änderungserkennung, keine Formel empfohlen.

Dieses Mal haben wir über die "Änderungspunkterkennung" den Algorithmus eingeführt, der für die Änderungspunkterkennung von Zeitreihendaten verwendet wird, und ihn tatsächlich ausprobiert, da es in Python ein Modul gibt.

Algorithmus zur Extraktion von Zeitreihenänderungspunkten

Herkömmlich vorgeschlagener Änderungspunkterkennungsalgorithmus

Die Idee, die in der Vergangenheit vertreten wurde, ist sehr einfach. (1) Zeitreihenmodell (AR-Modell usw.), das unter Verwendung der gesamten Zeitreihendaten erstellt wurde (2) Zeitreihenmodell, konstruiert durch Teilen an einem bestimmten Punkt t Bereiten Sie beide vor

① Berechnen Sie zukünftige vorhergesagte Werte mit den Modellen des jeweils anderen (2) Berechnen Sie den quadratischen Fehler mit dem tatsächlichen Wert, indem Sie den vorhergesagten Wert und den gemessenen Wert mit dem Modell des anderen vergleichen. Und

Aus "Quadratischer Fehler des Zeitreihenmodells, das unter Verwendung der gesamten Zeitreihendaten erstellt wurde" Subtrahieren Sie "Quadratischer Fehler des Zeitreihenmodells, das durch Teilen an einem bestimmten Punkt t konstruiert wurde" Wenn es groß genug wird Es ist definiert als "eine Änderung tritt bei t auf".

図4.png

(Referenz) Zeitreihen-AR-Modell

Als Referenz wird nur die Formel des AR-Modells beschrieben. Bitte überprüfen Sie andere Dokumente und Websites für detaillierte Erklärungen. Das d-dimensionale AR-Modell kann wie folgt geschrieben werden.

z_t = \sum_{i=1}^{k}A_iz_{t-i}+\varepsilon

$ A_i $ ist die Koeffizientenmatrix, $ \ varepsilon $ ist die durchschnittliche 0 und die Varianz-Co-Verteilungsmatrix ist $ \ Sigma $.

Probleme mit herkömmlichen Algorithmen

Der obige Algorithmus hatte die folgenden Probleme.

① Riesige Rechenzeit

図3.png

(2) Nicht stationäre Daten können nicht verarbeitet werden

Change Finder, eine der Methoden zum Erkennen von Änderungspunkten

Um die oben genannten Probleme zu lösen, wurde eine Methode namens "Change Finder" unter Verwendung des SDAR-Algorithmus (Sequential Discounting Auto Regressive) erstellt, der die Online-Verarbeitung von Parametern und anderen Berechnungen zum Erstellen eines AR-Modells durchführt.

(1) Berechnen Sie die Änderungsbewertung für jede Zeitreihendaten und betrachten Sie den Teil mit der hohen Bewertung als "Änderung". (2) Die Parameterberechnung wird einfach nach der wahrscheinlichsten (etwas angewandten) Schätzmethode berechnet. (3) Die Parameter, wenn die Daten aktualisiert werden, werden aus den vergangenen Parametern und den aktualisierten Daten erhalten. ――Bei ② und ③ wird der Rechenaufwand gegenüber der herkömmlichen Methode reduziert. (4) Stellen Sie bei der Berechnung der Modellparameter "Vergissmeinnicht-Parameter" ein, die den Einfluss vergangener Daten verringern. ――Bei entsprechender Einstellung kann der Einfluss verringert werden, auch wenn die Eigenschaften vergangener Zeitreihendaten unterschiedlich sind, und es wird möglich, mit instationären Daten in gewissem Umfang umzugehen. ④ Extrahieren Sie durch Unterscheiden von Ausreißern und Änderungspunkten

Kurz gesagt bedeutet es "schneller und genauer als zuvor!"

SDAR-Modell

Im SDAR-Modell wird die auf dem AR-Modell basierende Wahrscheinlichkeitsdichtefunktion aus den Zeitreihendaten erhalten und die logarithmische Wahrscheinlichkeitsfunktion wird angenähert (in diesem Artikel wird die logarithmische Wahrscheinlichkeitsfunktion weggelassen. Wenn Sie dies wissen möchten, klicken Sie hier](http: Bitte überprüfen Sie //www.viewcom.or.jp/seika/report0703.pdf).) Schätzen Sie für die Modellparameter den Wert, wenn der durch Multiplizieren der erhaltenen logarithmischen Wahrscheinlichkeitsfunktion mit dem Vergessenheitskoeffizienten erhaltene Wert maximiert wird. Machen.

Insbesondere ist es wie folgt. Um die bedingte Dichtefunktion von $ x_t $ zu betrachten, die $ x ^ {t-1} = x_1, x_2, ..., x_ {t-1} $ für den stochastischen Prozess $ p $, $ p (x_t | ergibt Bei Verwendung einer Notation wie x ^ {t-1}) $ verwenden die SDAR-Modellparameter $ A $, $ \ mu $, $ \ Sigma $ den Wert, wenn $ I $ maximiert ist. ..

I = \sum_{i=1}^{t}(1-r)^{t-i}\log P(x_i|x^{i-1},A_1,…,A_k,\mu,\Sigma)

Dabei ist $ r $ der Vergessenheitsparameter, $ A $ der AR-Modellparameter, $ k $ die AR-Modellreihenfolge und $ \ Sigma $ die verteilte, gemeinsam verteilte Matrix.

In diesem Artikel werden wir auch die Ableitung der logarithmischen Wahrscheinlichkeitsfunktion und die Ableitung von Parametern unter Verwendung der Yulewalker-Gleichung weglassen. Wenn Sie es wissen möchten, lesen Sie bitte den entsprechenden Teil des Artikels hier.

Zusammenfassung der Berechnungsmethode für Änderungspunkte im Änderungsfinder

Lernen in der ersten Stufe

(1) Erstellen Sie zu jedem Zeitpunkt mit dem SDAR-Modell ein Zeitreihenmodell (= Wahrscheinlichkeitsdichtefunktion basierend auf Daten bis zu jedem Zeitpunkt) (2) Bestimmen Sie anhand des in (1) konstruierten Modells die Wahrscheinlichkeit, dass der gemessene Wert beim nächsten Mal herauskommt. ③ Ermitteln Sie den logarithmischen Verlust dieser Wahrscheinlichkeit und verwenden Sie ihn als Ausreißer.

Die Ausreißerbewertung wird wie folgt berechnet.

Score(x_t) = -\log P_{t-1}(x_t|x^{t-1})

Glättung der Punktzahl

Stellen Sie die Breite $ W> 0 $ ein, um die Ausreißerbewertung innerhalb dieser Breite zu glätten. Durch Glätten kann festgestellt werden, ob der Zustand lange anhält (= ob er sich geändert hat), nicht der Zustand des Ausreißers.

In einer mathematischen Formel ausgedrückt, kann die geglättete Punktzahl am Punkt t $ y_t $ wie folgt berechnet werden.

y_t = \frac{1}{W}\sum_{t=t-W+1}^{t}Score(x_i)

Lernen in der zweiten Stufe

(1) Lernen Sie die durch Glätten mit dem SDAR-Modell erzielte Punktzahl weiter (2) Bestimmen Sie anhand des in (1) konstruierten Modells die "Wahrscheinlichkeit" (angepasst durch den Vergessenheitskoeffizienten), dass der gemessene Wert beim nächsten Mal herauskommt. ③ Ermitteln Sie den logarithmischen Verlust dieser Wahrscheinlichkeit und verwenden Sie ihn als Änderungspunktzahl.

Beispielcode

Ich habe den Beispielcode von hier so zitiert, wie er ist. Wir generieren Zufallszahlen, die drei Arten von Normalverteilungen folgen, und untersuchen deren Änderungen.

# -*- coding: utf-
import matplotlib.pyplot as plt
import changefinder
import numpy as np
data=np.concatenate([np.random.normal(0.7, 0.05, 300), 
np.random.normal(1.5, 0.05, 300),
np.random.normal(0.6, 0.05, 300),
np.random.normal(1.3, 0.05, 300)])

cf = changefinder.ChangeFinder(r=0.01, order=1, smooth=7)

ret = []
for i in data:
    score = cf.update(i)
    ret.append(score)

fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(ret)
ax2 = ax.twinx()
ax2.plot(data,'r')
plt.show()

Das Ergebnis ist wie folgt. Die rote Linie ist die Originaldaten und die blaue Linie ist die Änderungspunktzahl. SDAR.png

Vom Wechsler eingestellte Parameter

Im obigen Beispielcode habe ich den Parameter changefinder.ChangeFinder eingestellt (r = 0,01, order = 1, glatt = 7). Es wird eine kurze Erläuterung der einzelnen Parameter gegeben.

$ r $: Oblivion-Parameter Zeigt an, wie viel Einfluss in der Vergangenheit bei der Berechnung der Wahrscheinlichkeitsdichtefunktion gesteuert wird. Wie Sie der Formel des SDAR-Modells entnehmen können, ist der Einfluss der Vergangenheit groß und die Variation des Änderungspunkts groß, wenn dieser Wert klein gemacht wird.

Bestellung: Bestellung des AR-Modells Legen Sie fest, wie weit vergangene Werte im Modell enthalten sind. Ich habe noch nicht geantwortet, wie ich diesen Parameter bestimmen soll. (Das einfache Bestimmen der Reihenfolge basierend auf AIC oder BIC ist wenig sinnvoll, wenn es sich um nicht stationäre Daten handelt, und die Zeitreihendaten selbst, auf die dieses Modell angewendet wird, sind nicht stationär, wenn die Reihenfolge nach der Verarbeitung auf Konstanz geschätzt wird. Es ist stabil ...)

glatt: Bereich der Glättung Je länger dies dauert, desto mehr "Änderungen" werden anstelle der Ausreißer erfasst. Wenn sie jedoch zu groß sind, ist es schwierig, die Änderungen selbst zu erfassen.

Extraktion von Änderungen des Aktienkurses eines bestimmten Unternehmens

Die oben erstellten Beispieldaten und extrahierten die Änderungspunkte, Ich fragte mich, ob es möglich wäre, den Wendepunkt eines Unternehmens anhand des Aktienkurses dieses Unternehmens zu visualisieren. Im Folgenden habe ich die Änderungen des Aktienkurses eines "bestimmten Unternehmens" überprüft, dessen Hauptgeschäft die Datenanalyse und die Bereitstellung von Analysesystemen ist.

Importieren Sie zunächst die erforderlichen Bibliotheken.

# -*- coding: utf-

##Die Bibliothek nutzte diese Zeit und die Magie
#Was Sie rund um den Sucher brauchen

import changefinder
#Im Bedarfsfall:pip install changefinder
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
from statsmodels.tsa import ar_model

#Was Sie zum Schaben brauchen

import urllib2
import requests
import lxml
from bs4 import BeautifulSoup
import time

Als nächstes erhalten Sie die Aktienkursdaten. Dieses Mal habe ich die Daten von dieser Site erhalten.

##Datenerfassung

dates = []
stock = []

for i in xrange(1,7):
    #Diesmal eine bestimmte Firma 2011-Holen Sie sich den Aktienkurs von 2016
    url = urllib2.urlopen('http://k-db.com/stocks/3655-T/1d/201' + str(i))
    #Schlaf vorerst
    time.sleep(5)
    soup = BeautifulSoup(url)
    #Holen Sie sich die Anzahl der Daten
    n_dates = len(soup.find_all("td",{"class": "b"}))
    for j in range(n_dates):
        date = str(soup.find_all("td",{"class": "l"})[j].text)
        stock_day = float(soup.find_all("td",{"class": "b"})[j].text)
        dates.append(date)
        stock.append(stock_day)

stock_pd = pd.Series(stock,index=dates).sort_index()
print stock_pd.head(10)

Lassen Sie uns die erfassten Daten visualisieren.

##Visualisierung

plt.style.use('ggplot')
stock_pd.plot(figsize = (12,4),alpha = 0.5,color = 'b')
plt.title('stockprice', size=14)

kabuka.png

Dieses bestimmte Unternehmen hatte von 2011 bis 2012 einen hohen Aktienkurs und fiel dann von dort aus. Von dort aus sieht es so aus, als würde es sich stetig bewegen (wenn auch leicht nach unten).

Lassen Sie uns nun endlich den Änderungswert mit dem Änderungsfinder berechnen.

## change finder

cf = changefinder.ChangeFinder(r = 0.01, order = 3, smooth = 14)

change = []
for i in stock_pd:
    score = cf.update(i)
    change.append(score)

change_pd = pd.Series(change,index=dates)

stock_price = stock_pd.plot(figsize = (12,4), alpha = 0.5, color = 'b',x_compat=True)
ax2 = stock_price.twinx()
ax2.plot(change_pd, alpha=0.5, color = 'r')
plt.title('stockprice(blue) & changescore(red)', size=14)

Das Ergebnis ist wie folgt.

株価+変化点.png

Es ist ein kontinuierlicher Wandel von 2011 bis 2012. Danach scheint es um Januar 2014 Änderungen zu geben. Tatsächlich wurde dieses Unternehmen im September 2011 an der ersten Sektion der Tokioter Börse notiert. Sie sehen also, dass der Aktienkurs zunächst nicht stabil war. Außerdem habe ich im Januar 2014 ein Joint Venture mit einem bestimmten Unternehmen gegründet. War es also ziemlich aggressiv in Bezug auf das Management? Man kann sagen, dass es Zeit ist. Danach ist der Änderungspunkt niedrig. Grundsätzlich kann gesagt werden, dass es sich um ein stabiles Unternehmen handelt, das aufgrund einer solch drastischen Veränderung nicht klappert. ??

Was ich noch nicht verstehe

(1) Mit diesem Algorithmus können Sie beim tatsächlichen Verschieben feststellen, dass sich der Änderungspunkt ändert, sobald Sie die Parameter ändern. Ich wusste jedoch nicht, wie ich jeden Parameter richtig bestimmen sollte, also entschied ich mich diesmal für die Parameter, während ich die Ergebnisse "explorativ" überprüfte. Ich würde mich freuen, wenn Sie mir beibringen könnten, wie man hier gute Anpassungen vornimmt. (2) Kann man wirklich sagen, dass es mit instationären Daten "kompatibel" ist? Es ist wahr, dass der Einfluss der Vergangenheit in Abhängigkeit vom Vergessenheitsparameter gering ist, aber es ist noch nicht überzeugt, warum gesagt werden kann, dass "es in Ordnung ist, auch wenn es nicht stationär ist".

Andere

Auch dieses Mal haben wir die Änderungspunkte basierend auf dem AR-Modell extrahiert, jedoch im Änderungsfinder Es gibt auch eine Methode zur Berechnung des Änderungswerts basierend auf dem ARIMA-Modell. Ich habe mir die Theorie noch nicht angesehen, also werde ich sie schreiben, wenn ich in Zukunft Lust dazu habe.

Zusammenfassung

Recommended Posts

Finde einen Wendepunkt! [Extrahieren von Änderungspunkten in Zeitreihen mit dem Änderungsfinder]
Bequeme Zeitreihenaggregation mit TimeGrouper von Pandas
Ändern Sie die Zeitzone in Oracle Database Docker
Der süchtig machende Punkt des "Bayes-Denkens in Python"
Ich habe ein Paket erstellt, um Zeitreihen mit Python zu filtern
<Pandas> Umgang mit Zeitreihendaten in der Pivot-Tabelle