Jak mogę programowo wykryć segmenty serii danych, aby pasowały do ​​różnych krzywych?

14

Czy istnieją udokumentowane algorytmy rozdzielające sekcje danego zestawu danych na różne krzywe najlepszego dopasowania?

Na przykład większość ludzi patrząc na ten wykres danych z łatwością podzieliłby go na 3 części: odcinek sinusoidalny, odcinek liniowy i odwrotny odcinek wykładniczy. W rzeczywistości zrobiłem ten konkretny z sinusoidą, linią i prostą formułą wykładniczą.

Tabela danych z widocznymi trzema odrębnymi częściami

Czy istnieją algorytmy wyszukiwania takich części, które można następnie osobno dopasować do różnych krzywych / linii, aby stworzyć rodzaj złożonej serii najlepiej dopasowanych podzbiorów danych?

Zauważ, że chociaż przykład ma końce segmentów prawie w jednej linii, niekoniecznie tak będzie; może również nastąpić nagły wstrząs wartości przy odcięciu segmentu. Być może te przypadki będą łatwiejsze do wykrycia.

Aktualizacja: Oto obraz niewielkiej ilości rzeczywistych danych: Wykres świata rzeczywistego

Aktualizacja 2: oto niezwykle mały zbiór danych w świecie rzeczywistym (tylko 509 punktów danych):

4,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235

Oto, na wykresie, z przybliżoną pozycją niektórych znanych krawędzi elementów w świecie rzeczywistym zaznaczonych kropkowanymi liniami, luksus, którego normalnie nie będziemy mieć:

wprowadź opis zdjęcia tutaj

Jedną z naszych luksusów jest jednak spojrzenie z perspektywy czasu: dane w moim przypadku nie są szeregami czasowymi, ale są raczej powiązane przestrzennie; sensowne jest analizowanie całego zestawu danych (zwykle 5000–15000 punktów danych) jednocześnie, a nie w sposób ciągły.

dlaczego?
źródło
1
ps pierwszy post do CV; Jestem programistą i zwykle spędzam więcej czasu na SO. Przepraszamy za naruszenie lokalnych tabu. Wiele moich poszukiwań odpowiedzi doprowadziło tutaj, więc pomyślałem, że będzie to najlepsze miejsce do zapytania.
dlaczego ptak
Dlaczego nie opublikujesz danych, a ja postaram się odpowiedzieć na twoje pytanie przez przykład.
IrishStat
Jedną z możliwości byłoby dopasowanie całej rodziny krzywych jednocześnie, przy użyciu meta-modelu. Aby wszystko było bardziej precyzyjne, załóżmy, że twoim ostatecznym celem jest wygładzenie tego histogramu, powiedzmy, używając KDE. Następnie płynne oszacowanie z KDE będzie bardziej precyzyjne, jeśli użyjesz modelu, w którym szerokość jądra może się zmieniać w zakresie wartości jak w stosowanym tutaj modelu , równania (2) - (3)x
user603
1
Zbudowałeś ten przykład, aby pomysł miał sens: jak dotąd, tak dobrze. W przypadku prawdziwych histogramów o wiele bardziej powszechny jest fakt, że skomplikowany kształt odzwierciedla mieszaninę nakładających się rozkładów: wówczas zainteresowanie nie pojawia się w punktach zmiennych na obserwowanym histogramie, które na ogół nie istnieją przekonująco lub nie są właściwym sposobem myślenia o mieszaninach. Możliwe jest jednak, że używasz „histogramu” w znacznie szerszym zakresie niż jest to standardowe w nauce statystycznej, gdzie oznacza wykres słupkowy rozkładu częstotliwości lub prawdopodobieństwa (tylko).
Nick Cox,
@IrishStat - zwykłe zestawy danych zawierają od 5000 do 15000 wpisów. Próbowałem przygotować tutaj prawdziwy podsumowany, ale okazał się to zły przykład i musiałem zacząć od nowa. Z drugiej strony, zrobienie tego sugerowało mi częściową odpowiedź w zakresie prostego wygładzania i uśredniania grup danych za początkowe poszukiwanie wzorców, które zostaną później skończone, więc dzięki za to :) Mam prawdziwy, który ma tylko 509 szerokości, że wygląda na to, że może być dobrze; Dodam to do pytania, kiedy będę mógł.
dlaczego ptak

Odpowiedzi:

2

Moją interpretacją tego pytania jest to, że PO szuka metodologii, które pasowałyby do kształtu (przykładów) podanych przykładów, a nie resztek HAC. Ponadto pożądane są zautomatyzowane procedury, które nie wymagają znaczącej interwencji człowieka ani analityka. Box-Jenkins może nie być odpowiedni, pomimo nacisku w tym wątku, ponieważ wymagają znacznego zaangażowania analityków.

Istnieją moduły R dla tego typu dopasowywania wzorców bez opartego na momencie. Grupowanie dystrybucji permutacji jest techniką dopasowywania wzorców opracowaną przez naukowca z Instytutu Maxa Plancka, która spełnia określone przez ciebie kryteria. Jego zastosowanie dotyczy danych szeregów czasowych, ale nie ogranicza się do tego. Oto cytat dotyczący opracowanego modułu R:

pdc: Pakiet R dla opartego na złożoności grupowania szeregów czasowych przez Andreasa Brandmaiera

Oprócz PDC istnieje również metoda uczenia maszynowego, procedura iSax opracowana przez Eamona Keogha z UC Irvine, która również jest warta porównania.

Na koniec jest ten artykuł na temat niszczenia danych: Odkrywanie czającego się porządku w danychprzez Chattopadhyay i Lipson. Poza sprytnym tytułem, praca ma poważny cel. Oto streszczenie: „Od automatycznego rozpoznawania mowy po odkrywanie niezwykłych gwiazd, u podstaw prawie wszystkich zadań automatycznego odkrywania leży zdolność do porównywania i kontrastowania strumieni danych między sobą, w celu identyfikacji połączeń i określania wartości odstających. Jednak pomimo powszechności danych, zautomatyzowane metody nie nadążają. Kluczowym wąskim gardłem jest to, że większość algorytmów porównywania danych polega obecnie na ludzkim ekspercie, który określa, jakie „cechy” danych są istotne dla porównania. W tym miejscu proponujemy nową zasadę szacowania podobieństwa między źródłami arbitralności strumienie danych, nie wykorzystując ani wiedzy w dziedzinie, ani uczenia się. Pokazujemy zastosowanie tej zasady do analizy danych z wielu trudnych problemów w świecie rzeczywistym, w tym ujednoznacznienie wzorców elektro-encefalograficznych dotyczących napadów padaczkowych, wykrywanie anomalnej aktywności serca z nagrań dźwiękowych serca i klasyfikacja obiektów astronomicznych z surowej fotometrii. We wszystkich tych przypadkach i bez dostępu do wiedzy o domenach, wykazujemy wydajność na równi z dokładnością osiągniętą dzięki specjalistycznym algorytmom i heurystykom opracowanym przez ekspertów w dziedzinie. Sugerujemy, że zasady niszczenia danych mogą otworzyć drzwi do zrozumienia coraz bardziej złożonych obserwacji, zwłaszcza gdy eksperci nie wiedzą, czego szukać ”. We wszystkich tych przypadkach i bez dostępu do wiedzy o domenach, wykazujemy wydajność na równi z dokładnością osiągniętą dzięki specjalistycznym algorytmom i heurystykom opracowanym przez ekspertów w dziedzinie. Sugerujemy, że zasady niszczenia danych mogą otworzyć drzwi do zrozumienia coraz bardziej złożonych obserwacji, zwłaszcza gdy eksperci nie wiedzą, czego szukać ”. We wszystkich tych przypadkach i bez dostępu do wiedzy o domenach, wykazujemy wydajność na równi z dokładnością osiągniętą dzięki specjalistycznym algorytmom i heurystykom opracowanym przez ekspertów w dziedzinie. Sugerujemy, że zasady niszczenia danych mogą otworzyć drzwi do zrozumienia coraz bardziej złożonych obserwacji, zwłaszcza gdy eksperci nie wiedzą, czego szukać ”.

To podejście wykracza daleko poza krzywoliniowe dopasowanie. Warto to sprawdzić.

Mike Hunter
źródło
Dziękuję - masz rację, że chcę znaleźć klastry automatycznie, bez interwencji analityka. Do tego, co chcę zrobić, będę musiał rozbić zestawy danych 5000-15000 punktów danych na klastry, z których każdy dobrze odpowiada prostym formułom (w tym powtarzalnym) bez interwencji człowieka w grupy około 50000 takich zestawów danych w dopuszczalnym terminie przez ludzi na sprzęcie domowym.
Whybird
Jeśli chodzi o to, która krzywa pasuje do każdej grupy, po wykryciu granic w jakikolwiek sposób, jest dość proste, myślę, że po prostu wypróbuję różne modele (sinusoida, wielomian, wykładniczy) i zobaczę, która daje lepszą zwykłą r ^ 2.
Whybird
2
OK, myślę, że z tego wynika nieporozumienie: Sax i iSax to formaty reprezentacji do przechowywania i przetwarzania szeregów czasowych, nie są to algorytmy grupowania ani wykrywania segmentów / wzorców (według postu PO). Z twojej odpowiedzi rozumiem, że Keogh opracował algorytm oparty na formacie reprezentacji SAX, który rozwiązuje problem PO. Ale myślę, że nie o to ci chodziło?
Zhubarb,
2
OK, nie trzeba kontaktować się z Keogh, wiem o iSax i Sax , są to formaty reprezentacji do wydajnego wyszukiwania szeregów czasowych. Linki wyjaśniają je. iSax to nowsza wersja. Byłem podekscytowany moim niezrozumieniem twojej odpowiedzi, stąd pytania (nie próbuję być pedantyczny) :).
Zhubarb,
2
nie próbowałem niczego ukrywać, zinterpretowałem „procedurę isax” jako algorytm działający na isaxie. Sugeruję, że twoja odpowiedź wymaga ponownego sformułowania / modyfikacji po wyjaśnieniu.
Zhubarb,
2

Wykrywanie punktów zmiany w szeregu czasowym wymaga zbudowania solidnego globalnego modelu ARIMA (z pewnością wadliwego w przypadku zmian modelu i zmian parametrów w czasie w twoim przypadku), a następnie zidentyfikowania najbardziej znaczącego punktu zmiany w parametrach tego modelu. Używając twoich wartości 509, najbardziej znaczącym punktem zmiany był okres około 353. Użyłem zastrzeżonych algorytmów dostępnych w AUTOBOX (które pomogłem opracować), które mogłyby być licencjonowane dla twojej spersonalizowanej aplikacji. Podstawową ideą jest podzielenie danych na dwie części i po znalezieniu najważniejszego punktu zmiany należy ponownie przeanalizować każdy z dwóch zakresów czasowych osobno (1-352; 353-509) w celu ustalenia dalszych punktów zmiany w każdym z dwóch zestawów. Jest to powtarzane, dopóki nie pojawi się k podzbiorów. Pierwszy krok załączyłem, stosując to podejście.wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

IrishStat
źródło
Dlaczego 353 zostaje oflagowany, gdy 153 i 173 mają niższe wartości P?
Nick Cox,
@NickCox Dobre pytanie! Świetny komentarz Do celów prognozowania cały pomysł polega na oddzieleniu najnowszego (znaczącego) podzbioru od starszego podzbioru, dlatego 353 wygrało ... Dla celów tutaj rzeczywiście wybrałby 173.
IrishStat
Tytuł „NAJNOWSZEJ ISTOTNEJ PUNKTU PRZERWY” próbuje opowiedzieć historię
IrishStat,
Dziękuję Ci! To jest naprawdę interesujące i bardzo doceniane. Mogę się z tobą skontaktować w celu uzyskania dalszych szczegółów.
Whybird
Dzięki za wyjaśnienie: pomysł jest rzeczywiście wyraźny w ostatniej notatce. (nawiasem mówiąc, nie widziałem tak dużej GÓRNEJ PRZYPADKU w wynikach programu od wczesnych lat 90. Zalecałbym zmianę „95% poziomu ufności” na „5% poziom istotności”, zakładając, że o to chodzi.)
Nick Cox
2

Myślę, że tytuł wątku wprowadza w błąd: nie chcesz porównywać funkcji gęstości, ale tak naprawdę szukasz przerw strukturalnych w szeregu czasowym. Nie określa się jednak, czy te pęknięcia strukturalne powinny zostać wykryte w oknie kroczącym, czy z perspektywy czasu, patrząc na całą historię szeregów czasowych. W tym sensie twoje pytanie jest w rzeczywistości duplikatem tego: jaka metoda wykrywania pęknięć strukturalnych w szeregach czasowych?

Jak wspomniano w tym linku Rob Hyndman, R oferuje do tego celu pakiet strucchange. Bawiłem się twoimi danymi, ale muszę powiedzieć, że wyniki są rozczarowujące [czy pierwszy punkt danych to naprawdę 4, czy powinien mieć 54?]:

raw = c(54,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235)
raw = log(raw+1)
d = as.ts(raw,frequency = 12)
dd = ts.intersect(d = d, d1 = lag(d, -1),d2 = lag(d, -2),d3 = lag(d, -3),d4 = lag(d, -4),d5 = lag(d, -5),d6 = lag(d, -6),d7 = lag(d, -7),d8 = lag(d, -8),d9 = lag(d, -9),d10 = lag(d, -10),d11 = lag(d, -11),d12 = lag(d, -12))

(breakpoints(d ~d1 + d2+ d3+ d4+ d5+ d6+ d7+ d8+ d9+ d10+ d11+ d12, data = dd))
>Breakpoints at observation number:
>151 
>Corresponding to breakdates:
>163 

(breakpoints(d ~d1 + d2, data = dd))
>Breakpoints at observation number:
>95 178 
>Corresponding to breakdates:
>107 190 

Nie jestem zwykłym użytkownikiem pakietu. Jak widać, zależy to od modelu dopasowanego do danych. Możesz eksperymentować z

library(forecast)
auto.arima(raw)

co daje ci najlepiej dopasowany model ARIMA.

HOSS_JFL
źródło
Dziękuję Ci! Zredagowałem słowo „histogram” z tytułu; Początkowo niewłaściwie go wykorzystałem i zapomniałem edytować tytuł, gdy usunąłem go z ciała w poprzedniej edycji w odpowiedzi na komentarz.
Whybird
Moje dane są właściwie serią powiązanych przestrzennie danych, nie są oparte na czasie i zwykle nie będą istnieć wystarczająco często na linii prostej, a nawet na płaszczyźnie - ale masz rację, że na pewnym podstawowym poziomie można je rozpatrywać w ten sam sposób sposób; Myślę, że może to wynikać z tego, że moje wcześniejsze wyszukiwania nie znalazły odpowiedzi, których oczekiwałem.
Whybird
Pierwszym punktem danych w tym przykładzie jest tak naprawdę 4, ale może się zdarzyć, że trafiliśmy na koniec poprzedniej struktury, a może to był hałas; Byłbym szczęśliwy, mogąc to pominąć, ale każdy system, który wymyślę, będzie musiał poradzić sobie z takimi rzeczami.
Whybird
Aha, a analiza jest z perspektywy czasu. Przeredaguję pytanie, aby wyjaśnić.
Whybird