[PYTHON] Trouvez un tournant! [Extraction des points de modification dans les séries chronologiques avec l'outil de recherche de modifications]

Contexte

J'aime les livres d'histoire et je les lis de temps en temps. Récemment, j'ai lu Essence of Failure. Ce livre était très intéressant car il parlait de ce qui se passait au tournant de la guerre du Pacifique du point de vue de la théorie organisationnelle. En lisant ce livre, je me demandais: "Le tournant est-il quelque chose qui peut être regardé en arrière et saisi quantitativement?" Puis il y avait. Un algorithme qui extrait les changements dans les séries chronologiques.

17c1dfeb.jpg

Types de problèmes de détection d'anomalies / de détection de changement

En premier lieu, quel type de problème y a-t-il dans la détection d'anomalies / détection de changement? Introduction à la détection des anomalies J'ai essayé de classer en 3 en référence à la page 12 de.

tâche Aperçu
Problème de détection des valeurs aberrantes statique. Un point de données est-il significativement hors de la distribution?
Problème de détection de point de changement dynamique. Que le sujet ait changé ou non, où est le point
Détection d'état anormal dynamique. L'état actuel de la cible est-il anormal ou normal?

Si vous commencez à écrire plus concrètement, ce sera une très longue phrase, donc je vais la sauter cette fois. Pour ceux qui veulent connaître les grandes lignes de la détection des anomalies / détection des changements, l'article Résumé de la détection des anomalies et détection des changements, pas de formule est recommandé.

Cette fois, à propos de la "détection du point de changement", nous avons introduit l'algorithme utilisé pour la détection du point de changement des données de séries temporelles et l'avons essayé car il y a un module en python.

Algorithme d'extraction des points de changement de séries chronologiques

Algorithme de détection des points de changement proposé de manière conventionnelle

L'idée qui a été défendue dans le passé est très simple. (1) Modèle de série chronologique (modèle AR, etc.) construit à partir de l'ensemble des données de la série chronologique (2) Modèle de séries temporelles construit en divisant à un certain point t Préparez les deux

① Calculez les futures valeurs prévues avec les modèles de chacun (2) Calculez l'erreur quadratique avec la valeur réelle en comparant la valeur prédite et la valeur mesurée avec le modèle de l'autre. Et

Extrait de "Erreur carrée du modèle de série chronologique construit à l'aide de l'ensemble des données de la série chronologique" Soustraire "Erreur carrée du modèle de série chronologique construit en divisant à un certain point t" Si ça devient assez gros Il est défini comme "un changement se produit en t".

図4.png

(Référence) Modèle AR chronologique

Pour référence, seule la formule du modèle AR est décrite. Veuillez consulter d'autres documents et sites Web pour des explications détaillées. Le modèle AR en d dimensions peut être écrit comme suit.

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

$ A_i $ est la matrice de coefficients, $ \ varepsilon $ est le 0 moyen et la matrice de variance-co-distribution est $ \ Sigma $.

Problèmes avec les algorithmes conventionnels

L'algorithme ci-dessus présentait les problèmes suivants.

① Temps de calcul énorme

図3.png

(2) Impossible de gérer les données non stationnaires

Change Finder, l'une des méthodes de détection des points de changement

Afin de résoudre les problèmes ci-dessus, une méthode appelée "Change Finder" a été créée à l'aide de l'algorithme SDAR (Sequentially Discounting Auto Regressive), qui effectue le traitement en ligne des paramètres et d'autres calculs pour construire un modèle AR.

(1) Calculez le score de changement pour chaque donnée de série chronologique et considérez la partie avec le score le plus élevé comme «changement» (2) Le calcul des paramètres est simplement calculé par la méthode d'estimation la plus probable (un peu appliquée). (3) Les paramètres lorsque les données sont mises à jour sont obtenus à partir des paramètres passés et des données mises à jour. ――Par ② et ③, la quantité de calcul est réduite par rapport à la méthode conventionnelle. (4) Lors du calcul des paramètres du modèle, définissez des "paramètres oubliés" qui réduisent l'influence des données passées. ―― En définissant correctement ce qui précède, même si les propriétés des données de séries chronologiques antérieures sont différentes, l'influence peut être réduite et il devient possible de traiter dans une certaine mesure des données non stationnaires. ④ Extraire en distinguant les valeurs aberrantes et les points de changement

En bref, cela signifie "plus rapide et plus précis qu'avant!"

Modèle SDAR

Dans le modèle SDAR, la fonction de densité de probabilité basée sur le modèle AR est obtenue à partir des données de la série chronologique et la fonction de vraisemblance logarithmique est approximée (dans cet article, la fonction de vraisemblance logarithmique est omise. Si vous voulez savoir, cliquez ici](http: Veuillez vérifier //www.viewcom.or.jp/seika/report0703.pdf).) Pour les paramètres du modèle, estimez la valeur lorsque la valeur obtenue en multipliant la fonction de vraisemblance logarithmique obtenue par le coefficient d'oubli est maximisée. Faire.

Plus précisément, c'est comme suit. Considérer la fonction de densité conditionnelle de $ x_t $ qui donne $ x ^ {t-1} = x_1, x_2,…, x_ {t-1} $ pour le processus stochastique $ p $, $ p (x_t | Lorsque vous utilisez une notation telle que x ^ {t-1}) $, les paramètres du modèle SDAR $ A $, $ \ mu $, $ \ Sigma $ utilisent la valeur lorsque $ I $ est maximisé. ..

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

Où $ r $ est le paramètre d'oubli, $ A $ est le paramètre du modèle AR, $ k $ est l'ordre du modèle AR et $ \ Sigma $ est la matrice distribuée co-distribuée.

De plus, dans cet article, nous omettons la dérivation de la fonction de vraisemblance logarithmique et la dérivation des paramètres à l'aide de l'équation de Yulewalker. Si vous souhaitez en savoir plus, veuillez consulter la partie correspondante de l'article ici.

Résumé de la méthode de calcul des points de changement dans Change Finder

Apprentissage de la première étape

(1) Construire un modèle de série chronologique (= fonction de densité de probabilité basée sur les données jusqu'à chaque point temporel) à chaque point temporel avec le modèle SDAR (2) En vous basant sur le modèle construit en (1), trouvez la probabilité que la valeur mesurée la prochaine fois sortira. ③ Trouvez la perte logarithmique de cette probabilité et utilisez-la comme score aberrant.

Le score aberrant est calculé comme suit.

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

Lissage du score

Définissez la largeur $ W> 0 $ pour lisser le score aberrant dans cette largeur. En lissant, il est possible de déterminer si l'état a continué pendant une longue période (= s'il a changé), et non l'état de la valeur aberrante.

Exprimé dans une formule mathématique, si le score lissé au point t est $ y_t $, il peut être calculé comme suit.

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

Apprentissage de deuxième étape

(1) Apprendre davantage le score obtenu en lissant avec le modèle SDAR (2) Sur la base du modèle construit en (1), trouvez la "probabilité" (ajustée par le coefficient d'oubli) que la valeur mesurée à la prochaine fois sortira. ③ Trouvez la perte logarithmique de cette probabilité et utilisez-la comme score du point de changement.

Exemple de code

J'ai cité l'exemple de code de ici tel quel. Nous générons des nombres aléatoires qui suivent trois types de distributions normales et examinons leurs changements.

# -*- 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()

Le résultat est le suivant. La ligne rouge correspond aux données d'origine et la ligne bleue correspond au score du point de changement. SDAR.png

Paramètres définis par Changefinder

Dans l'exemple de code ci-dessus, j'ai défini le paramètre changefinder.ChangeFinder (r = 0,01, order = 1, smooth = 7). Une brève explication de chaque paramètre est donnée.

$ r $: paramètre Oblivion Indique le degré d'influence passé contrôlé lors du calcul de la fonction de densité de probabilité. Comme vous pouvez le voir dans la formule du modèle SDAR, si cette valeur est rendue petite, l'influence du passé sera grande et la variation du point de changement sera grande.

order: Ordre du modèle AR Définissez à quelle distance les valeurs passées sont incluses dans le modèle Je n'ai pas encore répondu comment comprendre comment déterminer ce paramètre. (Le simple fait de déterminer l'ordre en fonction de l'AIC ou du BIC n'a pas beaucoup de sens s'il s'agit de données non stationnaires, et les données de série temporelle elles-mêmes auxquelles ce modèle est appliqué ne sont pas stationnaires lorsque l'ordre est estimé après traitement pour avoir une constance. C'est régulier ...)

smooth: Gamme de lissage Plus celle-ci est longue, plus le «changement» est capturé au lieu de la valeur aberrante, mais s'il est trop important, le changement lui-même sera difficile à capturer en premier lieu.

Extraction des variations du cours de l'action d'une certaine société

Les exemples de données ci-dessus ont créé et extrait les points de changement, Je me suis demandé s'il serait possible de visualiser le tournant d'une entreprise à partir du cours de l'action de cette entreprise. Ci-dessous, j'ai vérifié l'évolution du cours de l'action d'une «certaine société» dont l'activité principale est l'analyse de données et la fourniture de systèmes d'analyse.

Tout d'abord, importez les bibliothèques requises.

# -*- coding: utf-

##La bibliothèque a utilisé cette fois et la magie
#Ce dont vous avez besoin autour de Changefinder

import changefinder
#Si nécessaire:pip install changefinder
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
from statsmodels.tsa import ar_model

#Ce dont vous avez besoin pour gratter

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

Ensuite, récupérez les données sur le cours de l'action. Cette fois, j'ai obtenu les données de ce site.

##L'acquisition des données

dates = []
stock = []

for i in xrange(1,7):
    #Cette fois, une certaine entreprise 2011-Obtenez le cours de l'action de 2016
    url = urllib2.urlopen('http://k-db.com/stocks/3655-T/1d/201' + str(i))
    #Endors-toi pour le moment
    time.sleep(5)
    soup = BeautifulSoup(url)
    #Obtenez le nombre de dates
    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)

Visualisons les données acquises.

##Visualisation

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

kabuka.png

Cette société a eu un cours de bourse élevé de 2011 à 2012, puis a chuté à partir de là. À partir de là, il semble qu'il bouge régulièrement (quoique légèrement vers le bas).

Maintenant, calculons enfin le score de changement avec changefinder.

## 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)

Le résultat est le suivant.

株価+変化点.png

C'est un changement continu de 2011 à 2012. Après cela, il semble qu'il y aura des changements vers janvier 2014. En fait, cette société a été cotée à la première section de la Bourse de Tokyo en septembre 2011. Vous pouvez donc voir que le cours de l'action n'était pas stable au début. Aussi, vers janvier 2014, je créais une joint-venture avec une certaine entreprise, était-ce donc assez agressif en termes de management? On peut dire qu'il est temps. Après cela, le point de changement est bas. Fondamentalement, on peut dire que c'est une entreprise stable sans cliquetis en raison d'un changement aussi radical. ??

Ce que je ne comprends pas encore

(1) Avec cet algorithme, lorsque vous le déplacez réellement, vous pouvez voir que le point de changement change dès que vous modifiez les paramètres. Cependant, je ne savais pas comment décider correctement chaque paramètre, donc cette fois j'ai décidé des paramètres en vérifiant les résultats "exploratoires". Je vous serais reconnaissant si vous pouviez m'apprendre comment faire de bons ajustements ici. (2) Est-il vraiment possible de dire qu'il est "compatible" avec des données non stationnaires? Il est vrai que l'influence du passé est faible en fonction du paramètre de l'oubli, mais on n'est pas encore convaincu pourquoi on peut dire que "ça va même si c'est non stationnaire".

Autre

De plus, cette fois, nous avons extrait les points de changement basés sur le modèle AR, mais dans le changefinder Il existe également une méthode pour calculer le score de changement basé sur le modèle ARIMA. Je n'ai pas encore examiné la théorie, alors je l'écrirai si j'en ai envie à l'avenir.

Résumé

Recommended Posts

Trouvez un tournant! [Extraction des points de modification dans les séries chronologiques avec l'outil de recherche de modifications]
Agrégation pratique de séries chronologiques avec TimeGrouper de pandas
Modifier le fuseau horaire dans Oracle Database Docker
Le point addictif du "raisonnement de Bayes expérimenté en Python"
J'ai créé un package pour filtrer les séries chronologiques avec python
<Pandas> Comment gérer les données de séries chronologiques dans le tableau croisé dynamique