Jak znaleźć wartości szczytowe w zbiorze danych?

47

Jeśli mam zestaw danych, który tworzy wykres, taki jak poniżej, w jaki sposób algorytmicznie określiłbym wartości x pokazanych pików (w tym przypadku trzech z nich):

wprowadź opis zdjęcia tutaj

nietoksyczne
źródło
13
Widzę sześć lokalnych maksimów. Do których trzech masz na myśli? :-). (Oczywiście, że to oczywiste - sedno mojej uwagi ma zachęcić cię do dokładniejszego zdefiniowania „szczytu”, ponieważ jest to klucz do stworzenia dobrego algorytmu.)
whuber
3
Jeśli dane są czysto okresowymi szeregami czasowymi z dodanym składnikiem szumu losowego, możesz dopasować funkcję regresji harmonicznej, w której okres i amplituda są parametrami szacowanymi na podstawie danych. Powstały model byłby funkcją okresową, która jest gładka (tj. Funkcją kilku sinusów i cosinusów), a zatem będzie miał jednoznacznie identyfikowalne punkty czasowe, gdy pierwsza pochodna jest zerowa, a druga pochodna jest ujemna. To byłyby szczyty. Miejsca, w których pierwsza pochodna wynosi zero, a druga pochodna jest dodatnia, będą to, co nazywamy dolinami.
Michael Chernick,
2
Dodałem tag trybu, sprawdź kilka z tych pytań, będą one miały interesujące odpowiedzi.
Andy W
Dziękujemy wszystkim za odpowiedzi i komentarze, bardzo to doceniamy! Zajmie mi trochę czasu zrozumienie i wdrożenie sugerowanych algorytmów związanych z moimi danymi, ale upewnię się, że zaktualizuję później informacje zwrotne.
nonxiomatic
Może dlatego, że moje dane są naprawdę hałaśliwe, ale nie udało mi się uzyskać odpowiedzi z odpowiedzią poniżej. Chociaż odniosłem sukces dzięki tej odpowiedzi: stackoverflow.com/a/16350373/84873
Daniel,

Odpowiedzi:

35

Ogólne podejście polega na wygładzeniu danych, a następnie znalezieniu pików poprzez porównanie lokalnego filtru maksymalnego z wygładzeniem . W R:

argmax <- function(x, y, w=1, ...) {
  require(zoo)
  n <- length(y)
  y.smooth <- loess(y ~ x, ...)$fitted
  y.max <- rollapply(zoo(y.smooth), 2*w+1, max, align="center")
  delta <- y.max - y.smooth[-c(1:w, n+1-1:w)]
  i.max <- which(delta <= 0) + w
  list(x=x[i.max], i=i.max, y.hat=y.smooth)
}

Zwracana wartość zawiera argumenty lokalnej maksima ( x) - która odpowiada na pytanie - oraz indeksy do tablic x i y, w których występują te lokalne maksima ( i).

Istnieją dwa parametry, które należy dostosować do okoliczności: w jest to połowa szerokości okna używanego do obliczania lokalnego maksimum. (Jego wartość powinna być znacznie mniejsza niż połowa długości tablicy danych.) Małe wartości wychwycą małe lokalne nierówności, podczas gdy większe wartości przejdą nad nimi. Kolejnym - nieprecyzyjnym w tym kodzie - jest spanargument loesswygładzacza. (Zazwyczaj ma wartość od zera do jednego; odzwierciedla szerokość okna jako proporcję zakresu wartości x.) Większe wartości wygładzą dane bardziej agresywnie, powodując całkowite zniknięcie lokalnych nierówności.

Aby zobaczyć, jak działa to strojenie, utwórzmy małą funkcję testową, aby wykreślić wyniki:

test <- function(w, span) {
  peaks <- argmax(x, y, w=w, span=span)

  plot(x, y, cex=0.75, col="Gray", main=paste("w = ", w, ", span = ", span, sep=""))
  lines(x, peaks$y.hat,  lwd=2) #$
  y.min <- min(y)
  sapply(peaks$i, function(i) lines(c(x[i],x[i]), c(y.min, peaks$y.hat[i]),
         col="Red", lty=2))
  points(x[peaks$i], peaks$y.hat[peaks$i], col="Red", pch=19, cex=1.25)
}

Oto kilka eksperymentów zastosowanych do niektórych syntetycznych, nieco zaszumionych danych.

x <- 1:1000 / 100 - 5
y <- exp(abs(x)/20) * sin(2 * x + (x/5)^2) + cos(10*x) / 5 + rnorm(length(x), sd=0.05)
par(mfrow=c(3,1))
test(2, 0.05)
test(30, 0.05)
test(2, 0.2)

Działki

Szerokie okno (środkowy wykres) lub bardziej agresywna gładka (dolny wykres) eliminuje lokalne maksima wykryte na górnym wykresie. Najlepszą kombinacją tutaj jest prawdopodobnie szerokie okno i tylko delikatne wygładzanie, ponieważ agresywne wygładzanie wydaje się przesuwać te szczyty (patrz środkowy i prawy punkt na dolnym wykresie i porównuj ich położenia z widocznymi szczytami surowych danych). W tym przykładzie w=50i span=0.05robi świetną robotę (nie pokazano).

Zauważ, że lokalne maksima w punktach końcowych nie są wykrywane. Można je sprawdzić osobno. (Aby to obsłużyć, argmaxzwraca wygładzone wartości y).


To podejście ma kilka zalet w porównaniu z bardziej formalnym modelowaniem do celów ogólnego zastosowania:

  • Nie przyjmuje żadnego z góry przyjętego modelu danych.

  • Można go dostosować do charakterystyki danych.

  • Można go dostosować do wykrywania rodzajów pików, które są zainteresowane.

Whuber
źródło
3
Przeciwnie, @Michael: Nie zakładam nic o okresowości. Rzeczywiście, przykład wygląda okresowo, ale nie jest: zwróć uwagę na kwadratowy termin. Regresja harmoniczna zawiedzie w tym przykładzie (i w wielu innych takich seriach). Co więcej, nie wybieram niczego „wizualnie”: wszystko odbywa się za pomocą algorytmu. (Dlaczego mam wrażenie, że tak naprawdę nie przeczytałeś tej odpowiedzi?)
whuber
1
Potrafię znaleźć szczyty algorytmicznie w pierwszym i drugim teście pochodnym, podczas gdy musisz użyć innych środków (być może czegoś w rodzaju wyszukiwania numerycznego). Nie chciałem twierdzić, że jedno podejście jest lepsze od drugiego, ani też nie krytykowałem twojej odpowiedzi. Po prostu widzę wiele podobieństw i kilka różnic i starałem się lepiej zrozumieć, w jaki sposób identyfikujesz swoje szczyty.
Michael Chernick,
3
@Michael Szczyty to lokalizacje, które nie przekraczają ruchomego maksimum; dzięki temu są szybkie i łatwe do obliczenia: nie ma wyszukiwania numerycznego, wystarczy prosty skan . Zaletą korzystania z gładkiego różniczkowalnego jest to, że może interpolować piki między podanymi wartościami x: jest to przydatne w przypadku grubszych lub nierównych rozdzielczości x. O(n)
whuber
4
@Michael, jeśli „nie masz czasu” na przeczytanie odpowiedzi / komentarza, możesz rozważyć powstrzymanie się od odpowiadania na / asercji na temat postu. Jest to coś, co robiłeś wielokrotnie i często prowadzi to do niekonstruktywnych wymian i / lub do wydawania nieprawidłowych instrukcji, które później wycofujesz. Wydaje się to stratą czasu i innych, których angażujesz się w takie rozmowy. Na przykład cały ten wątek komentarza z pewnością zajął więcej czasu niż samo przeczytanie odpowiedzi na początek. Dlaczego decydujesz się na korzystanie ze strony w ten sposób, nadal mnie zagadasz. Nie rozumiem, jak to komukolwiek się przyda.
Makro
2
Dzięki za ciekawe podejście. Myślę również uzyskać punkt Michael sięgał: trzeba było zobaczyć wykresy zdecydować najlepsze wartości wi span, a także dowiedzieć się, że wyższe wartości spanbyły przesunięcia pików. Wydaje się, że nawet te kroki można zautomatyzować. Np. W przypadku pierwszego wydania, jeśli moglibyśmy ocenić jakość wykrytych pików, moglibyśmy uruchomić optimizeparametry! W przypadku drugiego problemu, np. Wybierz okno po obu stronach odkrytego piku i poszukaj wyższych wartości.
Darren Cook
1

Jak wspomniałem w komentarzu, jeśli szeregi czasowe wydają się okresowo dopasowywać, model regresji harmonicznej zapewnia sposób na wygładzenie funkcji i identyfikację piku poprzez zastosowanie testów pierwszej i drugiej pochodnej. Huber wskazał na test nieparametryczny, który ma zalety, gdy występuje wiele pików, a funkcja niekoniecznie jest okresowa. Ale nie ma darmowego lunchu. Chociaż jego metoda ma zalety, o których wspomina, mogą istnieć wady, jeśli model parametryczny jest odpowiedni. Jest to zawsze druga strona stosowania technik nieparametrycznych. Mimo że unika się założeń parametrycznych, podejście parametryczne jest lepsze, gdy założenia parametryczne są odpowiednie. Jego procedura nie wykorzystuje również w pełni struktury szeregów czasowych w danych.

Uważam, że chociaż wskazane są zalety sugerowanej procedury, ważne jest również wskazanie potencjalnych wad. Zarówno moje podejście, jak i Huber znajdują szczyty w efektywny sposób. Myślę jednak, że jego procedura wymaga nieco więcej pracy, gdy lokalne maksimum jest niższe niż wcześniej ustalony najwyższy szczyt.

Michael Chernick
źródło
2
Czy mógłbyś zademonstrować „efektywny sposób” swojego podejścia? Część wyzwania polega na opracowaniu algorytmu znajdowania wielu pików - co w twoim przypadku oznacza znalezienie wszystkich zer (kosztownie obliczonej) pochodnej, a nie tylko jednego zera - i wyraźne określenie, które z tych punktów krytycznych sklasyfikujesz jako „szczyty”, a które nie. Również pewne poparcie lub wzmocnienie twojego twierdzenia, że ​​„podejście parametryczne jest lepsze, gdy założenia parametryczne są odpowiednie” byłoby dobre, ponieważ jak wszyscy wiemy, założenia parametryczne nigdy nie są dokładnie poprawne.
whuber
@ whuber Powiedziałem, że pasowałbyś do modelu, ponieważ ponieważ moduł jest sumą sinusów i cosinusów, funkcja jest okresowa, szczyty pojawiają się, gdy zarówno pierwsza pochodna wynosi zero, a druga pochodna w punkcie zerowym maleje. Właśnie to miałem na myśli, gdy powiedziałem, że bierzesz pierwszą i drugą pochodną. Teraz możesz rozwiązać, aby znaleźć wszystkie rozwiązania, ale jeśli masz jeden szczyt, pozostałe są o jeden okres i wiele okresów od rozwiązania, które masz. Nie chcę twierdzić, że metoda ma wyższość. Chcę tylko zaznaczyć, że nie ma darmowego lunchu.
Michael Chernick,
Zaletą metod nieparametrycznych jest brak wymogu modelowania, w tym przypadku brak założenia okresowości. Moje stwierdzenie o tym, że podejścia parametryczne są lepsze niż podejścia nieparametryczne, gdy utrzymują się założenia modelowania, powinno być wam bardzo znane. Nie muszę kłócić się o założenia parametryczne, które nigdy się nie sprawdzą. Z tą opinią zasadniczo się zgadzam. Ale mówię o wydajności Pitmana. Szacunki nieparametryczne nie są tak wydajne jak szacunki parametryczne, gdy model jest „poprawny”.
Michael Chernick,
To jest teoria. W praktyce modele parametryczne mogą być dobrym przybliżeniem do rzeczywistości. W takim przypadku oszacowanie parametryczne (powiedzmy mle) jest bardziej wydajne niż oszacowanie nieparametryczne. Także parametryczne przedziały ufności będą lepsze, ponieważ będą ściślejsze. Ale wiele razy nie wiesz, jak dobry jest model parametryczny dla twojego przykładu. W takich przypadkach musisz zdecydować między konserwatyzmem (bezpieczeństwo) z podejściem nieparametrycznym a byciem odważnym (i być może błędnym) przy użyciu podejścia parametrycznego.
Michael Chernick,
1
Próbuję zasugerować, Michael, że w tym przypadku podejście nieparametryczne będzie prawdopodobnie znacznie lepsze niż jakiekolwiek podejście parametryczne, z wyjątkiem sytuacji, gdy dane będą się ściśle przenosić do modelu - i nawet wtedy będą działały dobrze. Zakładając, że okresowość jest doskonałym przykładem: Twój algorytm będzie popełnił błędy tego samego rzędu wielkości, co odstępy od okresowości w danych. Możliwość popełnienia takich błędów niweczy wszelkie korzyści wynikające z większej skuteczności asymptotycznej. Zastosowanie takiej procedury bez uprzedniego przeprowadzenia obszernych testów GoF byłoby złym pomysłem.
whuber
1

Klasyczne podejście do wykrywania pików w przetwarzaniu sygnału jest następujące:

  1. Filtruj sygnał do rozsądnego rozsądnego zakresu, w zależności od częstotliwości próbkowania i właściwości sygnału, np. W przypadku EKG, filtra pasmowego IIR @ 0,5-20 Hz, filtr zerowej fazy zapewni, że nie zostanie wprowadzone przesunięcie fazowe (i powiązane opóźnienie czasowe)
  2. Następnie można zastosować transformację Hilberta lub podejście falkowe, aby podkreślić szczyty
  3. Następnie można zastosować próg statyczny lub dynamiczny, w którym wszystkie próbki powyżej progu są uważane za wartości szczytowe. W przypadku progu dynamicznego jest zwykle definiowany jako próg N odchyleń standardowych powyżej lub poniżej estymacji średniej ruchomej średniej.

Innym podejściem, które działa, jest porównanie ostro filtrowanego sygnału górnoprzepustowego z silnie wygładzonym (filtr dolnoprzepustowy lub filtr mediany) i zastosowanie kroku 3.

Mam nadzieję że to pomoże.

BGreene
źródło