Minimalizowanie sumy absolutnego odchylenia (odległość

15

Mam zestaw danych x1,x2),,xk i chcę znaleźć parametr m taki, aby minimalizował sumę

ja=1k|m-xja|.
to jest

minmi=1k|mxi|.
Mayenew
źródło
2
Czy mógłbyś trochę rozwinąć?
Geoff Oxberry
Czy w takim przypadku rozwiązaniem nie byłby środek między wartościami maksymalnymi i minimalnymi?
Paweł
@Paul mediana może zminimalizować sumę, ale chce wiedzieć, jak można to zrobić analitycznie, szczególnie minimalizację
L1
@kadu to prawda, mediana jest rozwiązaniem. Obliczenie mediany analitycznie jest trywialne; wystarczy posortować, a następnie przyjąć średnią wartość.
David Ketcheson

Odpowiedzi:

22

Prawdopodobnie poprosisz o dowód, że mediana rozwiązuje problem? Cóż, można to zrobić w następujący sposób:

Celem jest odcinkowo liniowy i tym samym różniczkowalną wyjątkiem punktów . Jakie nachylenie celu ma jakiś punkt m x i ? Cóż, nachylenie jest sumą nachyleń odwzorowań m | m - x j | i jest to + 1 (dla m > x j ) lub - 1 (dla m < x j ). Stąd nachylenie wskazuje, ile x i jest mniejsze niż mm=ximxim|m-xjot|+1m>xjot-1m<xjotxjam. Widzisz, że nachylenie wynosi zero, jeśli istnieje równie wiele mniejszych i większych niż m (dla i parzystej liczby x i ). Jeśli jest nieparzysta liczba x i , to nachylenie wynosi - 1 na lewo od „środkowego” i + 1 na prawo od niego, stąd środkowa jest minimalna.xjamxjaxja-1+1

Sztylet
źródło
16

Uogólnienie tego problemu na wiele wymiarów nazywa się problemem geometrycznej mediany . Jak zauważa David, mediana jest rozwiązaniem dla przypadku 1-D; tam można użyć algorytmów wyboru wyszukiwania mediany , które są bardziej wydajne niż sortowanie. Sortowanie to podczas gdy algorytmy wyboru to O ( n ) ; sortowanie jest bardziej wydajne tylko wtedy, gdy potrzebnych jest wiele selekcji, w którym to przypadku można sortować (kosztownie) jeden raz, a następnie wielokrotnie wybierać z posortowanej listy.O(nlogn)O(n)

Link do problemu geometrycznej mediany wspomina o rozwiązaniach dla przypadków wielowymiarowych.

Geoff Oxberry
źródło
6

Wyraźne rozwiązanie w zakresie mediany jest poprawne, ale w odpowiedzi na komentarz Mayenew oto inne podejście.

Powszechnie wiadomo, że problemów minimalizacji ogólnie, a pisał problemem w szczególności, może być rozwiązany przez programowania liniowego.1

Poniższe sformułowanie LP wykona dla danego ćwiczenia z niewiadomymi :zja,m

takie, że: z im - x i z ix i - m

mjanzja
zjam-xja
zjaxja-m

Wyraźnie musi równać | x i - m | co najmniej, więc wymaga to zminimalizowania sumy bezwzględnych wartości błędów.zja|xja-m|

matematyka
źródło
2

Nadmiernie zasilony wypukły sposób analizy, aby to pokazać, wystarczy wziąć podgrupy. W rzeczywistości jest to równoważne z rozumowaniem zastosowanym w niektórych innych odpowiedziach dotyczących zboczy.

|m-xja|

m<xja

m=xja

m>xja

mx1,xk

cjordan1
źródło
0

argminmja=1N.|m-xja|

re|x|rex=znak(x)L.1
ja=1N.znak(m-xja)
m=mediana{x1,x2),,xN.}

Należy zauważyć, że mediangrupa dyskretna nie jest jednoznacznie zdefiniowana.
Co więcej, niekoniecznie jest to element w grupie.

Royi
źródło