algorytm.org

Metoda najmniejszych kwadratów

Praca
Interesuje Cię praca przy weryfikacji oprogramowania do samolotów?
Sprawdź to!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda najmniejszych kwadratów
Ocena użytkowników:***** / 23
SłabyŚwietny 
Wpisany przez Andrzej Borucki, 06 grudnia 2011 20:09

Mamy zbiór n punktów (xi, yi) dla których chcielibyśmy dopasować funkcję liniową y = ax + b.
Należy znaleźć takie dwie liczby rzeczywiste a oraz b aby jak najwięcej punktów leżało blisko tej prostej. Jako kryterium przyjmujemy minimalizację sumy kwadratów różnic między punktami yi a wyliczonym y = axi + b.
Suma kwadratów różnic charakteryzuje się tym że:
Przykładowy wynik metody:

metoda najmniejszych kwadratów - przykład


Mamy wyliczyć i zminimalizować:
(y_1 - ax_1 - b)^2 + (y_2 - ax_2 - b)^2 + ... + (y_n - ax_n - b)^2 = f(a, b)
Suma kwadratów różnic zawsze będzie ≥ 0 a równa zero tylko w przypadku gdy wszystkie punkty leżą na prostej y = ax + b, Funkcja ma jedno ekstremum i jest to minimum.
Punkt minimum osiągany jest dla (a, b) takiego, że obie pochodne cząstkowe
\frac{\partial f(a,b)}{\partial a}\\ \frac{\partial f(a,b)}{\partial b}
są zerowe.
f(a,b)=(y_{1}-ax_{1}-b)^{2}+(y_{2}-ax_{2}-b)^{2}+...+(y_{n}-ax_{n}-b)^{2}=\sum_{i=1}^{n}{(y_{i}-ax_{i}-b)^{2}}\\ \frac{\partial f(a,b)}{\partial a}=-2\sum_{i=1}^{n}{x_{i}(y_{i}-ax_{i}-b)}\\ \frac{\partial f(a,b)}{\partial b}=-2\sum_{i=1}^{n}{(y_{i}-ax_{i}-b)}
Dla większej czytelności wprowadzamy wartości stałe niezależne od a oraz b:
S_{x} = x_{1} + x_{2} + ... + x_{n} = \sum_{i=1}^{n}{x_{i}}\\ S_{y} = y_{1} + y_{2} + ... + y_{n} = \sum_{i=1}^{n}{y_{i}}\\ S_{xx} = x_{1}^{2} + x_{2}^{2} + ... + x_{n}^{2} = \sum_{i=1}^{n}{x_{i}^{2}}\\ S_{xy} = x_{1}y_{1} + x_{2}y_{2} + ... + x_{n}y_{y} = \sum_{i=1}^{n}{x_{i}y_{i}}
Pierwsze równanie ma postać:
\frac{\partial f(a,b)}{\partial a}=0\\ \sum_{i=1}^{n}{x_{i}(y_{i}-ax_{i}-b)=0}\\ \sum_{i=1}^{n}{x_{i}y_{i}-ax_{i}^{2}-bx_{i}=0}\\ \sum_{i=1}^{n}{x_{i}y_{i}}-a\sum_{i=1}^{n}{x_{i}^{2}}-b\sum_{i=1}^{n}{x_{i}}=0
Używając wprowadzonych stałych:
\mathbf{(1) S_{xy} - aS_{xx} - bS_x = 0}
Podobnie wyprowadzamy drugie równanie:
\frac{\partial f(a,b)}{\partial b}=0\\ \sum_{i=1}^{n}{y_{i}-ax_{i}-b=0}\\ \sum_{i=1}^{n}{y_{i}}-a\sum_{i=1}^{n}{x_{i}}-n*b=0
Używając wprowadzonych stałych:
\mathbf{(2) S_y - aS_x - n*b = 0}
Równania (1) i (2) stanowią układ dwóch równań liniowych z dwiema niewiadomymi a i b Z (2) wyznaczamy b = (Sy - aSx) / n i wstawiamy do (1).
S_{xy}-aS_{xx}-\frac{S_{y}-aS_{x}}{n}S_{x}=0\\\\ \frac{S_{xy}n-aS_{xx}n-S_{x}S_{y}+aS_{x}^{2}}{n}=0\\\\ S_{xy}n-aS_{xx}n-S_{x}S_{y}+aS_{x}^{2}=0\\\\ a(S_{x}^{2}-S_{xx}n)=S_{x}S_{y}-S_{xy}n\\\\ \mathbf{(3)a=\frac{S_{x}S_{y}-S_{xy}n}{S_{x}^{2}-S_{xx}n}}\\\\\\ b=\frac{S_{y}-aS_{x}}{n}=\\\\ \frac{S_{y}}{n}-\frac{S_{x}a}{n}=\\\\ \frac{S_{y}}{n}-\frac{S_{x}(S_{x}S_{y}-S_{xy}n)}{n(S_{x}^{2}-S_{xx}n)}=\\\\ \frac{S_{y}(S_{x}^{2}-S_{xx}n)-S_{x}(S_{x}S_{y}-S_{xy}n)}{n(S_{x}^{2}-S_{xx}n)}=\\\\ \frac{S_{x}^{2}S_{y}-S_{xx}S_{y}n-S_{x}^{2}S_{y}-S_{x}S_{xy}n}{n(S_{x}^{2}-S_{xx}n)}\\\\ \mathbf{(4)b=\frac{S_{x}S_{xy}-S_{xx}S_{y}}{S_{x}^{2}-S_{xx}n}}
Otrzymane a i b w mianowniku mają to samo wyrażenie, więc zastąpmy je przez:
delta = S_x^2 - S_xxn
Ostatecznie:
a = \frac{S_xS_y - S_{xy}n}{delta}\\ b = \frac{S_xS_{xy} - S_{xx}S_y}{delta}

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Andrzej BoruckiDelphi/Pascal
.pas
.pas
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 02 października 2012 19:36
Komentarze
photo
0 # Enymay 2015-01-18 21:18
Czemu pomijasz potem -2, które wyszło Ci na początku?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2015-09-07 08:06
Bo chodzi o to, że mamy obliczyć wartość dla której pochodne cząstkowe są równe zero. Jeżeli pochodna ma postać -2 * x, to wartość zero będzie miała wówczas gdy x będzie zero, wartość -2 nie ma na to wpływu dlatego się ją pomija.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz