Klaster dynamicznego dopasowywania w czasie

40

Jakie byłoby podejście do korzystania z dynamicznego dopasowania czasu (DTW) w celu grupowania szeregów czasowych?

Czytałem o DTW jako sposobie znajdowania podobieństwa między dwoma szeregami czasowymi, podczas gdy można je przesunąć w czasie. Czy mogę użyć tej metody jako miary podobieństwa dla algorytmu grupowania, takiego jak k-średnie?

time-series clustering Marko
źródło
2
tak, można użyć miary podobieństwa jako danych wejściowych do k oznacza grupowanie, a następnie określić grupy w swoich danych.
przepowiednia
Dziękuję za odpowiedź Sir. Zgaduję, że dla każdej iteracji musiałbym utworzyć macierz odległości dla każdej pary (centroid, punkt skupienia) i ponownie obliczyć centroidy w standardowy sposób, jako średnią ze wszystkich serii należących do gromady?
Marko
1
Aleksandr Blekh w odpowiedzi poniżej zamieszcza post na blogu, który zawiera szczegółowy przykład tego, jak to zrobić w R.
prezenter
2
@forecaster nie używaj k-średnich z DTW. K-średnie minimalizuje wariancję, a nie odległości. Wariancja jest kwadratem euklidesowym, ale to nie znaczy, że k-średnie może zoptymalizować inne odległości. Średnia nie, aw DTW konstruowanie kontrprzykładów powinno być raczej łatwe, jak przesunięcie fali sinusoidalnej o : obie są bardzo podobne przez DTW, ale ich średnia jest stała zero - bardzo różna od obu. π
Anony-Mousse,
1
Średnie K nie jest odpowiednim algorytmem dla grupowania szeregów czasowych. Odpowiednie są ukryte modele markowa dla dyskretnych danych podłużnych. Obecnie dostępnych jest kilka książek na ten temat, a także kluczowe wypowiedzi Oded Netzer (Columbia) i Steve Scott (Google). Innym podejściem byłaby metoda teoretyczno-informacyjna opracowana przez Andreasa Brandmaiera z Maxa Plancka, zwana klastrowaniem rozkładu permutacji. Napisał również moduł R. Porównanie rozwiązań klastrowych to inna kwestia. Najlepszy jest artykuł Mariny Meili, „Porównywanie klastrów”, U z Washington Statistics Tech Report 418.
Mike Hunter,

Odpowiedzi:

33

Czy nie używać k-średnich dla timeseries.

Średnia DTW nie jest minimalizowana; średnie k mogą się nie zbiegać, a nawet jeśli się zbiegają, nie dają bardzo dobrego wyniku. Średnia to estymator najmniejszych kwadratów na współrzędnych. Minimalizuje wariancję, a nie dowolne odległości, a k-średnie służy do minimalizacji wariancji, a nie arbitralnych odległości .

Załóżmy, że masz dwie serie czasowe. Dwie fale sinusoidalne o tej samej częstotliwości i dość długi okres próbkowania; ale są one kompensowane przez . Ponieważ DTW dopasowuje czas, może je wyrównać, aby idealnie pasowały, z wyjątkiem początku i końca. DTW przypisze raczej niewielką odległość do tych dwóch serii. Jeśli jednak obliczysz średnią z dwóch serii, będzie to płaskie 0 - anulują się. Średni ma nie robić dynamicznego dopasowania czasu, i traci wszystkie wartości, które DTW GOT. W przypadku takich danych k-średnich może się nie zbiegać , a wyniki będą bez znaczenia. Średnie K naprawdę należy stosować tylko z wariancją (= kwadratowy euklides) lub w niektórych przypadkach, które są równoważne (jak cosinus, na znormalizowanych danych L2, gdzie podobieństwo cosinus jestπto samo co kwadratowa odległość euklidesowa)2)-

Zamiast tego oblicz macierz odległości za pomocą DTW, a następnie uruchom hierarchiczne grupowanie, takie jak pojedyncze łącze. W przeciwieństwie do k-średnich, seria może mieć nawet inną długość.

Anony-Mus
źródło
4
Jest oczywiście PAM (K-medoidy), który działa z dowolnymi odległościami. Jeden z wielu algorytmów, które obsługują dowolne odległości - k-średnich nie. Inne opcje to DBSCAN, OPTYKA, CLARANS, HAC, ...
Anony-Mousse
1
Prawdopodobnie. Ponieważ k-medoidy wykorzystują medoid DTW do znalezienia centrum skupienia, a nie średniej L2. Nie znam żadnego udanego grupowania szeregów czasowych w świecie rzeczywistym. Wydaje mi się, że widziałem papiery, ale żaden z nich tak naprawdę nie wykorzystał tego wyniku. Tylko weryfikacja koncepcji.
Anony-Mousse,
1
@Aleksandr Blekh podał to jako jeden ze swoich przykładów nbviewer.ipython.org/github/alexminnaar/… Co o tym sądzisz ?
Marko
1
Problemy z zabawkami. Bezużyteczne w prawdziwym świecie. Rzeczywiste dane mają dużo szumu, który będzie bolał bardziej niż gładkie krzywe sinusoidalne i wzorce przedstawione w tych danych.
Anony-Mousse
1
Myślę, że lepszym wyborem jest klastrowanie hierarchiczne. Zresztą i tak nie będziesz w stanie przetworzyć dużej liczby serii.
Anony-Mousse
49

Tak, można zastosować podejście DTW do klasyfikacji i grupowania szeregów czasowych . Skompilowałem następujące zasoby , które koncentrują się na tym właśnie temacie (ostatnio odpowiedziałem na podobne pytanie, ale nie na tej stronie, więc kopiuję tutaj zawartość dla wygody wszystkich):

Aleksandr Blekh
źródło
2
+1 doskonała kolekcja artykułów i blogów. Bardzo dobre referencje.
przepowiednia
@forecaster: Dziękujemy za entuzjazm i miłe słowa! Cieszę się, że podoba Ci się kolekcja. To bardzo smutne, że obecnie nie mam czasu na naukę prognozowania i wielu innych dziedzin statystyki i nauki danych poważniej, ale wykorzystuję każdą okazję, aby nauczyć się czegoś nowego.
Aleksandr Blekh
1
@AleksandrBlekh Dziękuję bardzo za odpowiedź, rozmawiałem z Anony-Mousse o tym podejściu, ponieważ jestem szczególnie zainteresowany DTW jako miarą podobieństwa dla średnich K, dzięki czemu mogłem uzyskać centroidy jako wynik. Jakie jest Twoje zdanie i doświadczenie? Jak widać, Anony-Mousse podała kilka argumentów, że wyniki mogą nie być tak dobre w tym przypadku ... Może jakieś osobiste doświadczenie w praktycznej sprawie?
Marko,
1
Ok, jeszcze raz dziękuję. Masz ode mnie +1, a on otrzymuje odpowiedź zaakceptowaną, ponieważ moje pytanie jest bardziej zorientowane na k-średnich i DTW.
Marko
1
@pera: Cała przyjemność po mojej stronie. Dzięki za głosowanie. Całkowicie rozumiem i zgadzam się na akceptację, bez problemu.
Aleksandr Blekh
1

Petitjean i in. Zaproponowali najnowszą metodę DTW Barycenter Averaging (DBA) . do średnich szeregów czasowych. W innym artykule udowodnili empirycznie i teoretycznie, jak można go wykorzystać do grupowania szeregów czasowych za pomocą k-średnich. Implementacja jest udostępniana na GitHub przez autorów ( link do kodu ).

1 F. Petitjean, G. Forestier, GI Webb, AE Nicholson, Y. Chen i E. Keogh, „Dynamiczne uśpienie czasowe szeregów czasowych pozwala na szybszą i dokładniejszą klasyfikację”, Międzynarodowa konferencja IEEE 2014, Data Mining, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Podsumowanie zbioru szeregów czasowych przez uśrednienie: Od sekwencji Steinera do kompaktowego wielokrotnego wyrównania, Theoretical Computer Science, Tom 414, Is.1, 2012

Hassan ISMAIL FAWAZ
źródło
2
podaj pełne referencje zamiast linków. Linki mogą umrzeć
Antoine
1

Dynamic Time Warp porównuje zrealizowane punkty danych, które mogą, ale nie muszą, działać. Bardziej rygorystycznym podejściem jest porównanie rozkładu szeregów czasowych za pomocą miernika zwanego odległością teleskopu .

Fajną rzeczą w tej metodzie jest to, że obliczenia empiryczne są wykonywane przez dopasowanie szeregu binarnych klasyfikatorów, takich jak SVM.

Aby uzyskać krótkie wyjaśnienie, zobacz to .

W przypadku szeregów czasowych klastrowania wykazano, że przewyższa DTW; patrz Tabela 1 w oryginalnej pracy [1].

[1] Ryabko, D. i Mary, J. (2013). Metryka oparta na klasyfikacji binarnej między rozkładami szeregów czasowych a jej wykorzystaniem w problemach statystycznych i uczących się. The Journal of Machine Learning Research, 14 (1), 2837-2856.

horaceT
źródło
2
Notatka redaktora: „Jérémie Mary (współautor) ma stronę internetową omawiającą algorytm z implementacją R.
Gung - Przywróć Monikę
@gung Wow, doskonale! Miałem korespondencję z pierwszym autorem i on nie wspomniał o tym.
horaceT
Właśnie kopiuję od kogoś, kto próbował edytować to w twojej odpowiedzi, @horaceT. Nie wiem za dużo o tym.
Gung - Przywróć Monikę
0

Tak. Naiwnym i potencjalnie wolnym podejściem może być

  1. Utwórz wszystkie kombinacje klastrów. k oznacza liczbę skupień, a n liczbę serii. Powinna być zwrócona liczba elementów n! / k! / (n-k)!. Byłyby to potencjalne centra.
  2. Dla każdej serii obliczyć odległości za pomocą DTW dla każdego centrum w każdej grupie klastrów i przypisać ją do minimum.
  3. Dla każdej grupy klastrów oblicz całkowitą odległość w obrębie poszczególnych klastrów.
  4. Wybierz minimum.

Użyłem tego do małego projektu. Oto moje repozytorium dotyczące grupowania szeregów czasowych i moja inna odpowiedź na ten temat.

Dogan Askan
źródło