Dopasuj częściowe dane liniowe

18

Jaki jest solidny sposób na dopasowanie danych liniowych, ale hałaśliwych?

Mierzę sygnał, który składa się z kilku prawie liniowych segmentów. Chciałbym atomatycznie dopasować kilka linii do danych, aby wykryć przejścia.

Zestaw danych składa się z kilku tysięcy punktów, z 1-10 segmentami i znam liczbę segmentów.

To jest przykład tego, co chciałbym zrobić automatycznie.

wprowadź opis zdjęcia tutaj

P3trus
źródło
Nie sądzę, aby można było odpowiedzieć na to pytanie rozsądnie, chyba że powiesz nam, jak dokładnie chcesz znać lokalizacje punktów przerwania, jaka jest Twoja prognoza dla najkrótszej długości odcinka liniowego i ile próbek jest w typowym region przejściowy. Jeśli etykiety osi poziomej na rysunku są liczbami przykładowymi, wówczas przy dwóch przejściach w zakresie od do zadanie jest trudniejsze niż w przypadku dłuższych odcinków linii prostych (w próbki). x[5]x[0]
Dilip Sarwate,
@DilipSarwate Zaktualizowałem pytanie o wymagania (między innymi, że xaxis to pole magnetyczne w tesli)
P3trus
Możesz wypróbować ten zestaw narzędzi, jeśli pracujesz z zestawem narzędzi do dopasowywania krzywej
Rhei

Odpowiedzi:

12

Wypróbowałem dwa podejścia, naiwnie (używając tylko 3 segmentów). Z pewnością byłyby tam bardziej wyszukane metody.

    RANSAC, ma być solidnym mechanizmem dopasowania. Po kilku segmentach łatwo jest zatrzymać algorytm. Wymuszanie ciągłości między segmentami może być jednak trudne - co wydaje się wymagane w Twojej aplikacji - przynajmniej za pomocą prostej implementacji. Jako dowód koncepcji, że utworzony obraz z punktami pomiarowymi, tak aby można używać silnik RANSAC dostępne w , funkcja wykrywania linii Mathematicą.ImageLines

wprowadź opis zdjęcia tutaj

    Zamontuj częściowy model liniowy za pomocą minimalizatora ogólnego przeznaczenia. Egzekwowanie ciągłości segmentów jest łatwe. Co ciekawe, testowanie pozostałości i innych właściwości może dostarczyć informacji wystarczających do automatycznego określenia liczby segmentów - jednak tego nie próbowałem. Tak to wygląda w Mathematica:

wprowadź opis zdjęcia tutaj

Matthias Odisio
źródło
Wygląda na świetną odpowiedź. Dzięki za wkład.
Jason R
7

Nie twierdzę, że poniższa metoda jest solidna, ale może działać dla Ciebie. Przy tysiącach punktów i być może około dziesięciu segmentach prostych postępuj w następujący sposób.x[n]

  • Przetwórz punkty aby utworzyć tablicę bitów y [ n ] w następujący sposób. y [ n ] = { 1 , jeśli | ( x [ n + 1 ] - x [ n ] ) - ( x [ n ] - x [ n - 1 ] ) | < ϵ , 0 , w przeciwnym razie. Tutajx[n]y[n]

    y[n]={1,if |(x[n+1]x[n])(x[n]x[n1])|<ϵ,0,Inaczej.
    jest małą liczbą wybraną, aby dopasować się do twojego pojęcia, jak blisko linii prostej chcesz punkty x [ n - 1 ] , x [ n ] , x [ n + 1 ] . Kryterium zostanie rozpoznane przez cognoscenti jako wymagające, aby linia prosta przez ( n - 1 , x [ n - 1 ] ) i ( n , x [ n ] )ϵx[n1],x[n],x[n+1](n1,x[n1])(n,x[n])ma prawie takie samo nachylenie jak linia prosta przez i ( n + 1 , x [ n + 1 ] ) .(n,x[n])(n+1,x[n+1])
  • Jeśli to tablica dziesięciu lub tak długich przebiegów 1 s oddzielonych biegami 0 s ze sporadycznymi zbłąkanymi 1 s tu i tam, aby niszczyć piękno, zrelaksować się, jesteś na dobrej drodze. W przeciwnym razie, jeśli jest zbyt mało przebiegów lub zbyt wiele przebiegów trwających 1 s, powtórz poprzedni krok z innym ϵ .y[n]1011ϵ

  • y[n]x[3]x[88]x[94]x[120]x[129], i tak dalej. Rozciągnij A w prawo i B w lewo, aby dowiedzieć się, gdzie się przecinają; rozciągnij B w prawo, a C w lewo, aby dowiedzieć się, gdzie się przecinają itp. Gratulacje, masz teraz ciągły i częściowy model danych.

Dilip Sarwate
źródło
Całkowicie ukradłem moją odpowiedź! =)
Phonon
Ciekawy pomysł, ale niestety ze względu na szum na sygnale nie osiągam dobrych wyników.
P3trus
1
To wyrażenie, którego magnitium jest porównywane do epsilon, jest w rzeczywistości przybliżeniem do drugiej pochodnej danych. Istnieją inne sposoby obliczenia tego przy użyciu więcej niż trzech punktów, które nie reagują tak bardzo na hałas. Spójrz w górę Savitzky-Golay.
DarenW,
4

(Lata później) częściowo-liniowe funkcje to splajny stopnia 1, co można powiedzieć większości monterów splajnu. Na przykład scipy.interpolate.UnivariateSpline może być uruchamiany z k=1 parametrem wygładzania s, z którym będziesz musiał grać - patrz scipy-interpolacja-z-splajnami-zmiennymi .
W Matlab zobacz, jak wybrać węzły .

Dodano: znalezienie optymalnych węzłów nie jest łatwe, ponieważ może istnieć wiele lokalnych optymów. Zamiast tego podajesz UnivariateSpline cel s, sumę błędu ^ 2, i pozwalasz określić liczbę węzłów. Po dopasowaniu get_residual()otrzymasz rzeczywistą sumę błędu ^ 2 i get_knots()węzłów. Niewielka zmiana smoże bardzo zmienić węzły, szczególnie w dużym hałasie - ymmv.
Wykres pokazuje dopasowanie do losowej funkcji liniowo-częściowej + szum dla różnych s.

Aby dopasować stałe częściowe, zobacz Wykrywanie kroków . Czy można tego użyć do pw liniowego? Nie wiem; rozpoczęcie od różnicowania zaszumionych danych zwiększy hałas, źle.

Mile widziane są inne funkcje testowe i / lub linki do dokumentów lub kodu. Kilka linków:
kawałek-regresja-liniowa-z-węzłami-jako-parametry
Splajny liniowe są bardzo wrażliwe na to, gdzie są umieszczone węzły,
wybór węzłów-dla-regresji sześciennych
Jest to trudny problem i większość ludzi wybiera węzły metodą prób i błędów.
Jedną z metod, która zyskuje na popularności, jest stosowanie splajnów z regresją karną.


Dodano marzec 2014: Programowanie dynamiczne to ogólna metoda rozwiązywania problemów z zagnieżdżonymi podproblemami:

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

Programowanie dynamiczne jest bardzo sprytne, ale czy można pokonać brutalną siłę + heurystykę w tym zadaniu?
Zobacz doskonałe notatki kursu Erika Demaine'a pod MIT 6.006 Wprowadzenie do algorytmów, regresja liniowa segmentowana w
Google, także zespół Johna Henry'ego.


wprowadź opis zdjęcia tutaj

denis
źródło
Problemem, przynajmniej w przypadku zwięzłego, jest ustawienie węzłów. scipy używa jednakowo rozmieszczonych węzłów.
P3trus,
@ P3trus, tak na początek, ale potem mogą się poruszać - zobacz fabułę. W każdym razie celuje w całkowity błąd, a nie w węzły.
denis
@ P3trus Czy próbowałeś użyć metody wielowymiarowych splajnów regresji, która automatycznie wybiera punkty przerwania iteracyjnie? cs.rtu.lv/jekabsons/regression.html
Atul Ingle
@Atul Ingle, afaik wybór punktu przerwania / węzła to ten sam problem, niezależnie od montera splajnu. Jeśli znasz inne algorytmy od osób z regresją / regresją, czy mógłbyś zamieścić link?
denis
Szukasz pakietów w R / Matlab, które wykonują splajny regresji adaptacyjnej? Tutaj: cran.r-project.org/web/packages/earth/index.html cran.r-project.org/web/packages/mda/index.html, a także ARESLab w Matlabie, dla którego już opublikowałem link.
Atul Ingle
0

Weź pochodną i poszukaj obszarów o niemal stałej wartości. Będziesz musiał stworzyć algorytm, aby wyszukać te obszary o idealnie pewnym poziomie nachylenia +/-, a to da ci nachylenie linii dla tej sekcji. Przed dokonaniem klasyfikacji przekrojowej może być konieczne wykonanie wygładzenia, na przykład średniej ruchomej. Następnym krokiem byłoby uzyskanie przecięcia y, które w tym momencie powinno być trywialne.

porten
źródło
pochodna może być głośna. nie sądzę, żebym polecił to.
Robert Bristol-Johnson
0

Innym pomysłem jest użycie filtru trendu L1:

Papier

Przykład online

SeanVN
źródło
1
Twoja odpowiedź jest trochę za krótka, aby była konstruktywna! Proszę rozważyć wysiłek rozszerzenia go w sposób pedagogiczny.
sansuiso