Przybliżenie punktu z kilku pomiarów

[Jajcenty 314]

Cześć!

Mam kilka punktów (x_i,y_i) jak to najlepiej uśrednić? Wydaje się, że metoda najmniejszych kwadratów ( znaleźc punkt P(s,t), taki  że Suma kwadratów odległości  |PX_i| jest najmniejsza ) lepiej przybliża niż jakieś tam średnie arytmetyczne. Niestety nie mogę (kurde! nie umiem) dojść do analitycznego rozwiązania. Mogę potraktować to siłowo i wyliczyć prostą regresji, wziąć z niej odcinek od min(x) do max(x) pobrać punkt ze środka, ale to mało eleganckie.

Oryginalny problem wziął się z GPS. Urządzenie jest w bezruchu, ale pokazuje że jest w pewnym okręgu - każdy kolejny pomiar różni się o kilka lub kilkanaście metrów od poprzedniego.

Zatem problem brzmi: uśrednić położenie GPS wiedząc, że odbiornik jest nieruchomy. Liczba pomiarów do 10.

 

[ex nihilo 225]

A jak to wygląda na układzie wsp. albo kracie jakiejś?

[Jajcenty 314]

1 godzinę temu, ex nihilo napisał:

A jak to wygląda na układzie wsp. albo kracie jakiejś?

Zwykły układ kartezjański wielokąt: (1, 1) (2, 2) (3, 3) (4, 7) (5, 3) ; Gdzie jest środek? 

Zastanawiam się nad skorzystaniem z wyznaczania środków ciężkości. Najcześciej mam 6 pomiarów, 6!/(3!*3!) = 20 trójkątów

 

[ex nihilo 225]

Czyli chodzi Ci nie o konkretny przypadek, a ogólną metodę?
Środek ciężkości może być ok. Ale najpierw by chyba warto sprawdzić, czy jest jakaś regularność odchyłek w kolejnych pomiarach lub w całości.

To co podałeś, to uporządkowane po "x", czy kolejne pomiary? I przykład z czapy, czy konkretny?

[Jajcenty 314]

Przykład jest z czapy, ale tożsamy z rzeczywistym problemem. W praktyce mam pomiar pozycji GPS, (długość, szerokość) w postaci długich liczb zmiennoprzecinkowych. Tak, chodzi o ogólną metodę. Mam uśrednić kilka, kilkanaście pomiarów pozycji GPS. Zwykła średnia arytmetyczna nie wydaje się dobra.

Oto faktyczne kilkaset pozycji, kwadrat o boku 100 metrów. Gdzie był odbiornik gps ? Dla ułatwienia dodam, że nie jest to ten pusty kwadrat 2x2piksele w środku :). Akurat ten GPS ma stały błąd +10 metrów na południe. Aha, i nie mam mapy na tyle dokładnej by zrobić "snap to road".

Edytowane 20 stycznia 2019 przez Jajcenty

[ex nihilo 225]

49 minutes ago, Jajcenty said:

w postaci długich liczb zmiennoprzecinkowych

Zbędne można wyrzucić.

Z tym obrazkiem zrobiłem sobie zabawę - do graficznego, rozmycie Gaussa 130/130 (tak akurat wrzuciłem), skala szarości i pomiar nasycenia. Wygląda na to, że dokładność może być całkiem przyzwoita. No ale to kilkaset.

Dla kilku/kilkunastu środek ciężkości chyba byłby ok. Wszystko zresztą zależy jaka dokładność Ci jest potrzebna.

Muszę się przespać trochę, bo zmarzłem dzisiaj co nieco i jeszcze mi nie przeszło... brrr, nie lubię tego.

[ex nihilo 225]

To na szybko z Twojego obrazka. Start od rozmycia 250/250, bez czyszczenia tła.

Od ok. 20 pomiarów może by już można próbować.

[Jajcenty 314]

2 godziny temu, ex nihilo napisał:

To na szybko z Twojego obrazka. Start od rozmycia 250/250, bez czyszczenia tła.

Dzięki, spróbuje coś pokombinować.

BTW, środek ciężkości to zwykła średnia ważona, dla punktów bezmasowych (lub jednakowej masie) to redukuje się do średniej arytmetycznej której chciałem uniknąć

The coordinates R of the center of mass of a two-particle system, P₁ and P₂, with masses m₁ and m₂ is given by

 

Edytowane 21 stycznia 2019 przez Jajcenty

[Afordancja 57]

Jeśli chodzi o ten punkt jako najmniejsza metoda kwadratów, to bym poczytał o algorytmie na gradient descending.

A tak łopatologicznie.

To ja bym wziął policzył dla każdego punktu, wynik. Potem odrzucił najdalsze, i jeszcze raz policzył, i znów odrzucił najdalsze aż zostaną 3 punkty i dla nich wyliczył bym centroid   [edit, można to oczywiście zoptymalizować to odrzucanie i nie trzeba ciągle przeliczać tego samego)

Ale to łopatologicznie, chyba gradiend descending było by najlepsze.

Edytowane 21 stycznia 2019 przez Afordancja

[thikim 119]

1 godzinę temu, Jajcenty napisał:

do średniej arytmetycznej której chciałem uniknąć

Ale co chciałbyś zamiast niej jeśli ona do tego akurat służy?

Cytat

Zwykła średnia arytmetyczna nie wydaje się dobra.

To już kwestia założenia że część punktów obarczona jest większymi błędami niż pozostałe i że te punkty jesteśmy w stanie zidentyfikować.

Jeśli jesteś w stanie określić ważność (masę) poszczególnych punktów to możesz to zrobić średnią ważoną.

Jeśli zakładasz że punkty w środku ze względu na skupienie są bardziej istotne to musisz po prostu nadać im większą masę. Co możesz osiągnąć robiąc najpierw średnią arytmetyczną a potem nadając punktom masę odwrotnie proporcjonalnie do odległości od środka geometrycznego.

W ten sposób skoncentrujesz punkty w środku jeszcze bardziej do środka

Ale czy to warte świeczki jest? Różnice nie powinny być duże.
No i to powyżej dotyczy błędów przypadkowych a nie stałych. Stałe możesz wyeliminować tylko porównaniem z wzorcem.

Edytowane 21 stycznia 2019 przez thikim

[Jajcenty 314]

2 godziny temu, Afordancja napisał:

Ale to łopatologicznie, chyba gradiend descending było by najlepsze.

Dzięki! Doczytam, może coś urodzę. Oczywiście brałem pod uwagę odrzucanie najbardziej odstających punktów. Tylko nie wiadomo jak je wyselekcjonować. Znaleźć najmniejszy okrąg zawierający wszystkie punkty i odrzucić dwa najdalsze od środka okręgu? Może rzeczywiście policzyć średnią (jaką? geometryczną? harmoniczną?) odrzucić jeden najdalszy od średniej i policzyć średnią znowu

 

2 godziny temu, thikim napisał:

Ale co chciałbyś zamiast niej jeśli ona do tego akurat służy?

No nie średnich jest kilka, a każda ma wady. Zirytowało mnie, że nie mam analitycznego rozwiązania metody najmniejszych kwadratów dla PUNKTU choć istnieje takowe dla PROSTEJ. Jestem pewien że powinno istnieć. Wystarczy rozwiązać zadanie: znaleźć punkt (s,t) taki że: d²/dtds (Suma((s-x_i)² + (t-y_i)²) = 0;

Jako ćwiczenie pozostawiam sobie dowód, że średnia arytmetyczna jest również najmniejszą sumą kwadratów. Dla trójkąta łatwo pokazać. Przypadek ogólny -wielokąt wklęsły -jest trudniejszy.

Faktyczny problem nie jest bardzo złożony obliczeniowo - 10 punktów. Śledzę samochód, GPS nadaje nie więcej niż 10 pozycji co 1 minutę. Ideałem byłoby wyznaczenie numeru miejsca parkingowego - prostokąt 4x8m Nie mogę użyć "snap to road" bo to plac parkingowy.

Wszystkim wielkie dzięki za wsparcie. Jak dojdę do czegoś interesującego to dam znać.

[ex nihilo 225]

2 hours ago, Jajcenty said:

Oczywiście brałem pod uwagę odrzucanie najbardziej odstających punktów. Tylko nie wiadomo jak je wyselekcjonować. Znaleźć najmniejszy okrąg zawierający wszystkie punkty i odrzucić dwa najdalsze od środka okręgu? Może rzeczywiście policzyć średnią (jaką? geometryczną? harmoniczną?) odrzucić jeden najdalszy od średniej i policzyć średnią znowu

Rozmycie Gaussa robi to automatycznie Im punkt jest bardziej "odstający", tym jego wkład do gluta jest mniejszy. W sumie dostaje się, "kwantologicznie" rzecz biorąc, rozkład gęstości pdp dla stanu przed pomiarami.
Wychodzi mi na to, że można to zrobić nawet dla kilku pomiarów, tylko trzeba rozywać 2x. Pierwsze rozmycie, mniejsze, żeby punkty zamienić na rozkłady, To trzeba proporcjonalnie skontrastować i wrzucić silne rozmycie, które da ostateczny rozkład. Przy takiej procedurze 10 pomiarów powinno dać bdb wynik. Analityczne można zrobić podobnie, tylko będzie to bardziej upierdliwe, bo w zależności od konkretnych danych mogą być potrzebne różne rozmycia.

[thikim 119]

3 godziny temu, Jajcenty napisał:

No nie średnich jest kilka, a każda ma wady

W Twoim wypadku nie znasz jakości pomiarów - więc jak sam zauważyłeś średnia ważona znika bo nie masz wagi i przechodzi w średnią arytmetyczną.

Są oczywiście różne średnie ale dla Twojego przypadku służy średnia arytmetyczna.
Co najwyżej jeśli uważasz że jednak pewne wyniki Ci nie pasują to możesz wprowadzić własną uznaniową wagę i powrócić do średniej ważonej.
Ale czy to ma sens? Minimalny.
Przy takim czymś to już znaczenie mają błędy stałe.

[Afordancja 57]

Tak sobie z ciekawości policzyłem po prostu licząc średnią (czyli algorytm centroidów i tak często widziałem liczyli dla danych kartograficznych),  i ta średnia z moim odrzucaniem wygrywa w większości przypadków.(ponad 80%)  (robiłem rozrzut punktów wg. rozkładu normalnego ). A im więcej punktów tym lepszy wynik ( w sumie oczywiste  ).

Potem porównałem z medianą geometryczną i przy tym rozkładzie dla 10 punktów znów, ta średnia wygrałą (tym razem w ponad 60% przypadków) i właśnie coś mi się wydaje, że gradien descent będzie dawał ten sam wynik co średnia.

 

Więc Twoja niechciana średnia chyba będzie najlepsza  

[Jajcenty 314]

8 minut temu, Afordancja napisał:

Więc Twoja niechciana średnia chyba będzie najlepsza

Narobiłem sobie kłopotu, dostawca obiecał nowy firmware i teraz będzie z pozycją słał jakość sygnału i jakość określenia pozycji - dwustanowe: normalna(czyli niska) | wysoka. Zatem średnia będzie ważona. Kwestia dobrania wagi. Postawię jeden GPS w dobrze znanej pozycji +- 1 m pozbieram dane i spróbuję dostroić wagę dla pozycji z wysoką dokładnością. Potem puszczę na tym znajdowanie minimum sumy i porównam, ale to już dla własnej przyjemności  

[Afordancja 57]

6 minut temu, Jajcenty napisał:

Zatem średnia będzie ważona. Kwestia dobrania wagi. Postawię jeden GPS w dobrze znanej pozycji +- 1 m pozbieram dane i spróbuję dostroić wagę dla pozycji z wysoką dokładnością. Potem puszczę na tym znajdowanie minimum sumy i porównam, ale to już dla własnej przyjemności   

Jak by Ci się chciało to z chęcią zobaczył bym wyniki.

Bo wg. moich symulacji wyszło, że to najlepsze ba może nawet ważenia nie trzeba(bo w końcu rozkład normalny i to sie jakoś powinno znieść), no ale jestem ciekaw wyniku

[mankomaniak 4]

Jeżeli punkty są nieskorelowane, to dla rozkładu normalnego należy stosować średnią arytmetyczną (albo metodę najmniejszych kwadratów, co wyjdzie na to samo). Gdy punkty są nieskorelowane, ale w rozkładzie nie-normalnym, np. z wartościami odstającymi, należy stosować medianę (albo metodę najmniejszych wartości bezwzględnych co wyjdzie na to samo).

Edytowane 25 stycznia 2019 przez mankomaniak

[mankomaniak 4]

1 hour ago, mankomaniak said:

albo metodę najmniejszych wartości bezwzględnych co wyjdzie na to samo

Poprawka, chodziło o metodę najmniejszych odchyleń bezwzględnych.

On 1/21/2019 at 1:19 PM, Jajcenty said:

Jako ćwiczenie pozostawiam sobie dowód, że średnia arytmetyczna jest również najmniejszą sumą kwadratów.

Wystarczy mieć podstawową wiedzę na temat MNK. Przecież wystarczy zauważyć, że jeśli punkty nie tworzą pewnej linii, tylko układają się losowo wokół pewnego punktu, to znaczy, że jeden wymiar nie zależy od drugiego, czyli punkty są niezależne od siebie. Dalej, MNK to regresja, a więc funkcja liniowa, a więc ma postać y = a + bx, gdzie a to stała, b to nachylenie funkcji, x to zmienna niezalezna, y to zmienna zależna. Skoro wiemy, że punkty są niezależne, to znaczy, że b = 0. Czyli y = a. Potrzeba więc tylko wzoru na a. A jaki jest wzór na parametry regresji MNK? Tutaj http://www.naukowiec.org/wiedza/statystyka/metoda-najmniejszych-kwadratow_733.html  mamy pokazane. 

a = średnia y - b*średnia x. 

Skoro b = 0, to:

a = średnia y.

Czyli y = średnia y.

Koniec banalnego dowodu.

[Jajcenty 314]

W dniu 25.01.2019 o 14:45, mankomaniak napisał:

Skoro wiemy, że punkty są niezależne, to znaczy, że b = 0. Czyli y = a. Potrzeba więc tylko wzoru na a. A jaki jest wzór na parametry regresji MNK? 

Nie sądzę by arbitralne przyjmowanie współczynników w równaniu regresji miało sens. Zróbmy to inaczej:  dane są punkty (xi,yi) szukamy punktu P(x,y) takiego że S = Suma[(x-xi)2 +(y-yi)2] jest najmniejsza.  W takim punkcie musi być dS/dx = 0 i dS/dy = 0; Po banalnych przekształceniach ( policzę pochodną cząstkową dla x bo rozumowanie dla y będzie identyczne):

d/dx Suma((x² -2xxi +xi²) + (y-yi)²) -> Suma(2x - 2xi) -> 2Suma(x) - 2Suma(xi) -> 2nx - 2suma(xi) = 0 ===>  x= suma(xi)/n czyli średnia arytmetyczna. Identycznie liczymy dla y.

Wszystko gra z dokładnością do rzędu pochodnej. Uważam, że w tym konkretnym przypadku powinienem szukać zera pochodnej d²/dxdy. Pierwszy sposób znajduje minimum ze względu na X, potem minimum ze względu na Y i uważa, że suma tych dwóch minimów jest również minimum funkcji. To oczywiste nadużycie pochodnej cząstkowej. d²/dxdy - to jest to co zaproponował Afordancja, tylko numerycznie

Edytowane 1 lutego 2019 przez Jajcenty

[mankomaniak 4]

14 minutes ago, Jajcenty said:

Nie sądzę by arbitralne przyjmowanie współczynników w równaniu regresji miało sens.

Ma logiczny sens. Chciałeś znaleźć środek czy średnią wokół punktów, no to Ci podałem wzór. Stosujesz średnią (dla rozkładu normalnego albo zbliżonego do niego) albo medianę (dla bardzo nie-normalnego rozkładu). Robisz to zarówno dla funkcji y = a1, jak i x = a2. Punkt (a1, a2) to Twoje rozwiązanie.

36 minutes ago, Jajcenty said:

Zróbmy to inaczej:  dane są punkty (xi,yi) szukamy punktu P(x,y) takiego że S = Suma[(x-xi)2 +(y-yi)2] jest najmniejsza.  W takim punkcie musi być dS/dx = 0 i dS/dy = 0; Po banalnych przekształceniach ( policzę pochodną cząstkową dla x bo rozumowanie dla y będzie identyczne):

d/dx Suma((x² -2xxi +xi²) + (y-yi)²) -> Suma(2x - 2xi) -> 2Suma(x) - 2Suma(xi) -> 2nx - 2suma(xi) = 0 ===>  x= suma(xi)/n czyli średnia arytmetyczna. Identycznie liczymy dla y.

To co pokazujesz, to właściwie nie jest MNK. Ale można pokazać, że to prowadzi do szczególnego przypadku MNK - właśnie wtedy, gdy x i y są niezależne od siebie. Czyli tego sposobu nie możesz użyć dla linii regresji. Mówiąc inaczej i tak zakładasz w sposób ukryty, że punkty są niezależne. Tak więc Twoje zdanie, że "nie sądzisz, by arbitralne przyjmowanie współczynników w równaniu regresji miało sens" jest sprzeczne z tym, co sam za chwilę pokazujesz, bo zwyczajnie zakładasz, że b = 0, tylko o tym nie wiesz.

 

[Jajcenty 314]

3 godziny temu, mankomaniak napisał:

To co pokazujesz, to właściwie nie jest MNK.

Sumuję kwadraty odległości i szukam minimum tej sumy. także tego... z definicji. Nie sądzę bym miał obowiązek stosować NMK razem z regresją i to w dodatku liniową jednej zmiennej. 

Co do sensu arbitralnego ustalania współczników w y = ax +b; Nie akceptuję rozumowania w którym z y=a wynika że zmienne są niezależne, bowiem wystarczy obrócić układ współrzędnych o pi/4 i zmienne staja się nagle zależne, a wsp korelacji wynosi silne 1.

@Afordancja Jeszcze się pisze kod do gradientu

[mankomaniak 4]

4 hours ago, Jajcenty said:

Sumuję kwadraty odległości i szukam minimum tej sumy. także tego... z definicji. Nie sądzę bym miał obowiązek stosować NMK razem z regresją i to w dodatku liniową jednej zmiennej.

,Przecież napisałem Ci, że to co robisz, to szczególny przypadek MNK właśnie, dla zmiennych niezależnych. Nie wierzysz czy nie możesz tego zrozumieć? Przecież Ty stosujesz twierdzenie Pitagorasa, czyli dla trójkąta prostokątnego, tj. zmiennych niezależnych. Jeśli jednak kąt nie będzie równy 90 stopni, to zmienne zaczną ze sobą korelować i wtedy nie dostaniesz już tego twierdzenia, zmieni się w twierdzenie cosinusów a^2 + b^2 - 2ab*cos(kąt). Cosinus z minusem to współczynnik korelacji zmiennych, więc dostaniesz a^2+b^2+2ab corr(ab) = a^2+b^2+2cov(a, b), gdzie corr(ab) to wsp korelacji między a i b; i cov to kowariancja. Stąd wychodzi wzór Var(a + b) = (a+b)^2 = a^2+b^2+2cov(a, b), gdzie Var(a, b) to wariancja zmiennej a+b. 

Zresztą skoro wyszła Ci tym sposobem średnia arytmetyczna, to logicznie biorąc musi to właśnie być MNK dla zmiennych niezależnych

4 hours ago, Jajcenty said:

Co do sensu arbitralnego ustalania współczników w y = ax +b; Nie akceptuję rozumowania w którym z y=a wynika że zmienne są niezależne, bowiem wystarczy obrócić układ współrzędnych o pi/4 i zmienne staja się nagle zależne, a wsp korelacji wynosi silne 1.

To zrób MNK to dla każdego obrotu o pi/4 i wyciągnij średnią z tego. Albo po prostu oblicz medianę, to obrót nie będzie miał wpływu, bo obracasz zawsze wokół punktu środkowego - nie może się więc zmienić.

Edytowane 1 lutego 2019 przez mankomaniak

[Jajcenty 314]

1 godzinę temu, mankomaniak napisał:

Przecież Ty stosujesz twierdzenie Pitagorasa, czyli dla trójkąta prostokątnego, tj. zmiennych niezależnych.

Nie ma sensu wikłać tu jeszcze metryki i sposobu liczenia odległości. W rzeczywistości punkty leżą na powierzchni kuli i metryka "euklidesowa" de facto nie obowiązuje. I mimo to, pomiary długości i szerokości geo. są niezależne. O to właśnie od początku chodzi? Gdyby były zależne mógłbym po prostu policzyć NMK bo f:x -> y, ale tak nie jest! Dlatego zamiast d/dx trzeba liczyć d²/dxdy. A d2/dxdy jest różne d/dx + d/dy

1 godzinę temu, mankomaniak napisał:

To zrób MNK to dla każdego obrotu o pi/4 i wyciągnij średnią z tego. Albo po prostu oblicz medianę, to obrót nie będzie miał wpływu, bo obracasz zawsze wokół punktu środkowego - nie może się więc zmienić.

Poza jednym: po obrocie zmienne do tej pory niezależne stały się zależne. Dla mnie czyni to rozumowanie nie do przyjęcia

Dzięki za  dyskusję. Z mojej strony to chyba wszystko co zdołam z siebie wycisnąć na ten temat.

 

[mankomaniak 4]

3 hours ago, Jajcenty said:

Nie ma sensu wikłać tu jeszcze metryki i sposobu liczenia odległości. W rzeczywistości punkty leżą na powierzchni kuli i metryka "euklidesowa" de facto nie obowiązuje. I mimo to, pomiary długości i szerokości geo. są niezależne.

Ja mówię o zwykłym układzie współrzędnych, nie żadnych kulach. Zwykłe proste y->x , na krzyż, bez żadnych udziwnień, topologii czy czego tam jeszcze. Zwróć po prostu uwagę na to, że jak rozdzielasz dane na osi poziomej od danych na osi pionowej, to już wtedy traktujesz punkty jako niezależne od siebie: (a1, b1) nie ma związku z (a2, b2). W momencie gdy zaczynasz bezpośrednio analizować odległości między punktami, to nie nakładasz takich założeń. Np. jeśli utworzysz długi trójkąt, wewnątrz którego będzie poszukiwany punkt środkowy, to analizując każdy punkt oddzielnie jako odległość od tego środka, dostaniesz rozwiązanie, które wyżej pokazałeś, w konsekwencji średnią. Ale jeśli nie będziesz rozdzielał punktów, ale minimalizował od razu odległości od środkowego punktu/linii, to dojdziesz jak by nie patrzeć do MNK (ewentualnie możesz zastosować uogólnioną MNK, jest pełno programów do tego, może nawet online), a więc ten długi trójkąt może zostać przedstawiony jako skorelowane ze sobą punkty, tworzące pewną linię.  

3 hours ago, Jajcenty said:

Poza jednym: po obrocie zmienne do tej pory niezależne stały się zależne.

Ale sam chciałeś dostać takie. Bo przecież dla zmiennych niezależnych stosuje się właśnie średnią arytmetyczną albo medianę, może są jeszcze jakieś inne miary, ale z tego co wiem dla zwykłych punktów stosuje się właśnie te dwie.

Edytowane 1 lutego 2019 przez mankomaniak

[Jajcenty 314]

@Afordancja

Naiwny optymalizator -  szukanie minimum sumy kwadratów odległości przez przemiatanie x+dx, y+dy (dwie zagnieżdżone pętle) znajduje minimum identyczne ze średnią arytmetyczną.

W końcu zrobiłem też dowód ANALITYCZNY, że tak właśnie jest. Posiłkując się tym https://www.matemaks.pl/ekstrema-lokalne-funkcji-dwoch-zmiennych.html  łatwo to pokazać. Gdyby ktoś chciał skontrolować rachunki: wyznacznik  4n² > 0 => istnieje ekstremum, druga pochodna po  f_xx" = 2n > 0 => minimum lokalne.

Co prawda Wszyscy tak mówiliście, ale teraz mam to na piśmie i zdołałem sam siebie przekonać.

Jeszcze raz dziki wszystkim za wsparcie.

<piwo>