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.

π

$\pi$

— 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,

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 $\pi$ 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):

Klasyfikacja / grupowanie szeregów czasowych UCR : strona główna , strona oprogramowania i odpowiedni papier
Klasyfikacja szeregów czasowych i klastrowanie za pomocą Pythona : post na blogu
Capital Bikeshare: Time Series Clustering : kolejny post na blogu
Klasyfikacja i grupowanie szeregów czasowych : notatnik ipython
Dynamiczne dopasowanie czasu za pomocą rpy i Python : kolejny post na blogu
Seria czasowa wyszukiwania z trylionami punktów: Dynamiczne wypaczanie czasu w skali : kolejny post na blogu
Analiza szeregów czasowych i wyszukiwanie w R (aby dodać R do miksu): kolejny wpis na blogu
I na koniec dwa narzędzia implementujące / wspierające DTW , na dodatek : pakiet R i moduł Python

— 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ć

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.
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.
Dla każdej grupy klastrów oblicz całkowitą odległość w obrębie poszczególnych klastrów.
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