[PYTHON] So vergleichen Sie Zeitreihendaten-Derivative DTW, DTW-
einpacken
- Zweck: Messen Sie die Ähnlichkeit verschiedener Zeitreihendaten
- Schlüsselwörter: Dynamic Time Warping (DTW), Derivative Dynamic Time Warping (DDTW)
- Referenz 1: Derivative DTW ~ Methode zur Berechnung der Ähnlichkeit von Zeitreihenmustern ~ von Tech Blog
- Referenz 2: [DTW (Dynamic Time Warping) Dynamisches Zeit Warping durch S-Analyse](https://data-analysis-stats.jp/%E6%A9%9F%E6%A2%B0%E5% AD% A6% E7% BF% 92 / dtwdynamic-time-Warping% E5% 8B% 95% E7% 9A% 84% E6% 99% 82% E9% 96% 93% E4% BC% B8% E7% B8% AE% E6% B3% 95 /)
- Referenz 3: Implementierung von DTW (Dynamic Time Stretching Method) durch ksknw
- Referenz 4: Verwendung von fastdtw
DTW
** So finden Sie DTW **
-
Erstellen Sie eine (Kosten-) Matrix, die den Abstand zwischen jedem Punkt in den beiden Zeitreihen berechnet (diesmal ist dies ein absoluter Wert, abhängig von der Dimension der Daten).
\begin{align} time\ series\ T&:t_0,t_1,...,t_N,\\ time\ series\ S&:s_0,s_1,...,s_M,\\ \boldsymbol{W}&:=(\delta(i,j)) ,\\ where\ \delta(t_i,s_j)&:=|t_i-s_j|,i \in \{0,1,...,N\},j\in\{0,1,...,M\} \end{align} -
Betrachten Sie einen Pfad, der auf dieser Matrix von (0,0) nach (N, M) verläuft und den monotonen Anstieg erfüllt.
\begin{align} path\ \tau :\tau(0)=(0,0),\tau(1),...,\tau(p)=(p_i,p_j),...,\tau(K),\\ where\ p_i \in \{0,1,...,N\},p_j\in\{0,1,...,M\}. \end{align}
Betrachten Sie insbesondere etwas, das den monotonen Anstieg mit diesem $ path \ \ tau $ befriedigt.
```math
\tau(p) \leq \tau(q) \Longleftrightarrow^{def} p_i\leq q_i\ or\ p_j\leq q_j.\\
if\ p\leq q,then\ \tau(p) \leq \tau(q).
```
-
Die DTW-Kosten seien der kleinste Wert in der Summe der Elemente der Matrix $ \ boldsymbol {W} $, die dieser $ Pfad $ durchläuft.
\begin{align} cost(\tau)&:=\sum_{p}\delta(p_i,p_j)\\ Dist(T,S)&:=min_{\tau}cost(\tau) \end{align}
Die folgende Abbildung stammt aus Derivative Dynamic Time Warping von Eamonn.
Es unterscheidet sich von der offiziellen Formel, aber es sieht so aus. Testcode: Referenz 3
#Vorbereitung
pip install fastdtw # <=pip ist eigentlich nur dieser
pip install numpy
pip install scipy
##code##
import numpy as np
from scipy.spatial.distance import euclidean
from fastdtw import fastdtw
A = np.sin(np.array(range(T)) / 10)
B = np.sin((np.array(range(T)) / 10 + t * np.pi))
C = np.zeros((T))
distance, path = fastdtw(A, B, dist=euclidean)
print(distance)
plt.plot(A)
plt.plot(B)
for i, j in path:
plt.plot([i, j], [A[i], B[j]],color='gray', linestyle='dotted')
plt.legend(["sin(θ)", "sin(θ+150*pi)"], fontsize=10, loc=2)
plt.show()
##Ergebnis##
sin(θ)-sin(θ+150*pi): 0.6639470476737607
sin(θ)-constant: 0.5150026855435942
DTW(sin(θ), sin(θ+150*pi)): 16.720461687388624
DTW(sin(θ), constant): 97.26964355198544
** Vorteile der DTW **
Ähnlichkeit kann erhalten werden, selbst wenn die Längen und Zyklen der Zeitreihen unterschiedlich sind.
** Nachteile von DTW **
Eine nicht intuitive Ausrichtung wird für Zeitreihendaten durchgeführt, bei denen Teile auf der Zeitachse lokal beschleunigt und abgebremst wurden:
Referenz: Derivative Dynamic Time Warping von Eamonn usw.
Wenn beispielsweise einer von ihnen s hoch wird, ignoriert DTW die Datenform und richtet sie aus. Die Ursache ist daher, dass der Datenpunkt mit der Höhe dem Datenpunkt vor der Höhe zugeordnet ist.
DDTW
Erhalten Sie DTW und messen Sie den Ähnlichkeitsgrad, indem Sie Informationen hinzufügen, die die Form erfassen. Nach der Verarbeitung der Zeitreihendaten $ time \ series \ T: t_0, t_1, ..., t_N $ wie folgt, DTW:
T^*:t^*_0,t^*_1,...,t^*_N,\\
where\ t^*_i := \frac{t_i-t_{i-1}+\frac{t_{i+1}-t_{i-1}}{2}}{2}= \frac{t_i-t_{i-1}+\frac{(t_{i+1}-t_i)+(t_i-t_{i-1})}{2}}{2}
Dieser Prozess ist der Durchschnitt des linken Differentials $ t_i-t_ {i-1} $ und des rechten Differentials $ t_ {i + 1} -t_i $ und der Durchschnitt des linken Differentials für den interessierenden Punkt $ t_i $. .. DDTW ist das DTW für diese Verarbeitung.
** Vorteile von DDTW **
Die Ähnlichkeit kann unter Berücksichtigung von Formen wie Aufwärtstrend und Abwärtstrend berechnet werden
** Nachteile von DDTW **
Ist der Durchschnitt der Pisten gut?
code
from concurrent.futures import ProcessPoolExecutor
from concurrent.futures import ThreadPoolExecutor
import time
import numpy as np
import pylab as plt
import seaborn as sns
from fastdtw import fastdtw
from scipy.spatial.distance import euclidean
def get_test_curves(view=False):
T = 150
t = .4
A = np.sin(np.array(range(T)) / 10)
B = np.sin((np.array(range(T)) / 10 + t * np.pi))
C = np.zeros((T))
if view:
plt.plot(A)
plt.plot(B)
plt.plot(C)
plt.legend(['sin(θ)', 'sin(θ+150*pi)', 'constant'], fontsize=10, loc=2)
plt.show()
return {'name': 'sin(θ)', 'data': A}, {'name': 'sin(θ+150*pi)', 'data': B}, {'name': 'constant', 'data': C}
def mse(a, b):
return ((a-b)**2).mean()
def get_DWT_results(T, S, skip=1, view=False):
T_data, S_data = T['data'], S['data']
T_name, S_name = T['name'], S['name']
distance, path = fastdtw(T_data, S_data, dist=euclidean)
print("DTW({}, {}):".format(T_name, S_name), distance)
if view:
plt.plot(T_data)
plt.plot(S_data)
k = -1
for i, j in path:
k += 1
if k % skip == 0:
plt.plot([i, j], [T_data[i], S_data[j]],
color='gray', linestyle='dotted')
plt.legend([T_name, S_name], fontsize=10, loc=2)
plt.title('DWT plot result')
plt.show()
return distance, path
def get_derivative(T):
diff = np.diff(T)
next_diff = np.append(np.delete(diff, 0), 0)
avg = (next_diff + diff) / 2
avg += diff
avg /= 2
return np.delete(avg, -1)
def get_DDWT_results(T, S, skip=1, view=False):
T_data, S_data = T['data'], S['data']
dT_data = get_derivative(T_data)
dS_data = get_derivative(S_data)
T_name, S_name = T['name'], S['name']
distance, path = fastdtw(dT_data, dS_data, dist=euclidean)
print("DDTW({}, {}):".format(T_name, S_name), distance)
if view:
plt.plot(T_data)
plt.plot(S_data)
k = -1
for i, j in path:
k += 1
if k % skip == 0:
plt.plot([i+1, j+1], [T_data[i+1], S_data[j+1]],
color='gray', linestyle='dotted')
plt.legend([T_name, S_name], fontsize=10, loc=2)
plt.title('DDWT plot result')
plt.show()
return distance, path
def get_test_curves_DDTWvsDWT(view=False):
T = 150
t = .4
A = np.zeros((T))
B = np.zeros((T))
# A = np.sin(np.array(range(T)) / 10)
# B = np.sin(np.array(range(T)) / 10+2)+50
s_i = 50
e_i = 60
for i in range(s_i, e_i, 1):
A[i] = np.sin(np.pi*(i-s_i)/(e_i-s_i))
# B[i] = -2.2
if view:
plt.plot(A)
plt.plot(B)
plt.legend(['sin(θ)', 'sin(θ+150*pi)'], fontsize=10, loc=2)
plt.show()
return {'name': 'down', 'data': A}, {'name': 'up', 'data': B}
def main():
print("=== main ===")
# A, B, C = get_test_curves()
A, B = get_test_curves_DDTWvsDWT()
# A["data"] = np.array([2, 0, 1, 1, 2, 4, 2, 1, 2, 0])
# B["data"] = np.array([1, 1, 2, 4, 2, 1, 2, 0])
print("{}-{}:".format(A['name'], B['name']), mse(A['data'], B['data']))
# print("{}-{}:".format(A['name'], C['name']), mse(A['data'], C['data']))
#DTW berechnen
get_DWT_results(A, B, skip=5)
get_DDWT_results(A, B, skip=5)
if __name__ == "__main__":
main()
** Angewandter Artikel **
Clustering von Aktienkursschwankungen von 2.940 japanischen Unternehmen in DTW (Dynamic Time Warping) - Dynamic Time Warping von Kimiaki Shirahama Vergleichen Sie den Unterschied in den Ergebnissen mit DTW und DDTW. Die verwendeten Daten sind "Thomson Reuters Data Stream". Wir schließen durch qualitative Bewertung (visuell), dass DTW + DDTW das optimale Ähnlichkeitsmaß für die Klassifizierung und Analyse von Aktienkursdaten ist.
Referenz 3 ist sowohl bei Code als auch bei Experimenten sehr hilfreich. Gilt für Temperaturdaten.
Außerdem scheint es etwas zu geben, das [k-Form] genannt wird (http://www1.cs.columbia.edu/~jopa/Papers/PaparrizosSIGMOD2015.pdf). Ich habe das nicht gelesen, aber ich benutze Distanz als gegenseitige Korrelation und Cluster mit k-Mitteln.
** Eindruck **
Ich habe tatsächlich versucht, die Zeitreihendaten mit DTW / DDTW zu gruppieren, aber es hat nicht funktioniert. Die Ursache ist, dass ich nicht viel verstehe. Wenn Sie Vorschläge haben, zögern Sie bitte nicht, uns zu kontaktieren.
Recommended Posts